/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_tsort.py

  • Committer: Martin von Gagern
  • Date: 2010-04-20 08:47:38 UTC
  • mfrom: (5167 +trunk)
  • mto: This revision was merged to the branch mainline in revision 5195.
  • Revision ID: martin.vgagern@gmx.net-20100420084738-ygymnqmdllzrhpfn
merge trunk

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_tsort.py
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
 
18
18
"""Tests for topological sort."""
19
19
 
 
20
import pprint
20
21
 
21
22
from bzrlib.tests import TestCase
22
23
from bzrlib.tsort import topo_sort, TopoSorter, MergeSorter, merge_sort
39
40
                          list,
40
41
                          TopoSorter(graph).iter_topo_order())
41
42
 
 
43
    def assertSortAndIterateOrder(self, graph):
 
44
        """Check topo_sort and iter_topo_order is genuinely topological order.
 
45
 
 
46
        For every child in the graph, check if it comes after all of it's
 
47
        parents.
 
48
        """
 
49
        sort_result = topo_sort(graph)
 
50
        iter_result = list(TopoSorter(graph).iter_topo_order())
 
51
        for (node, parents) in graph:
 
52
            for parent in parents:
 
53
                if sort_result.index(node) < sort_result.index(parent):
 
54
                    self.fail("parent %s must come before child %s:\n%s"
 
55
                              % (parent, node, sort_result))
 
56
                if iter_result.index(node) < iter_result.index(parent):
 
57
                    self.fail("parent %s must come before child %s:\n%s"
 
58
                              % (parent, node, iter_result))
 
59
 
42
60
    def test_tsort_empty(self):
43
61
        """TopoSort empty list"""
44
62
        self.assertSortAndIterate([], [])
50
68
    def test_tsort_cycle(self):
51
69
        """TopoSort traps graph with cycles"""
52
70
        self.assertSortAndIterateRaise(GraphCycleError,
53
 
                                       {0: [1], 
 
71
                                       {0: [1],
54
72
                                        1: [0]}.items())
55
73
 
56
74
    def test_tsort_cycle_2(self):
57
75
        """TopoSort traps graph with longer cycle"""
58
76
        self.assertSortAndIterateRaise(GraphCycleError,
59
 
                                       {0: [1], 
60
 
                                        1: [2], 
 
77
                                       {0: [1],
 
78
                                        1: [2],
61
79
                                        2: [0]}.items())
62
 
                 
 
80
 
 
81
    def test_topo_sort_cycle_with_tail(self):
 
82
        """TopoSort traps graph with longer cycle"""
 
83
        self.assertSortAndIterateRaise(GraphCycleError,
 
84
                                       {0: [1],
 
85
                                        1: [2],
 
86
                                        2: [3, 4],
 
87
                                        3: [0],
 
88
                                        4: []}.items())
 
89
 
63
90
    def test_tsort_1(self):
64
91
        """TopoSort simple nontrivial graph"""
65
 
        self.assertSortAndIterate({0: [3], 
 
92
        self.assertSortAndIterate({0: [3],
66
93
                                   1: [4],
67
94
                                   2: [1, 4],
68
 
                                   3: [], 
 
95
                                   3: [],
69
96
                                   4: [0, 3]}.items(),
70
97
                                  [3, 0, 4, 1, 2])
71
98
 
72
99
    def test_tsort_partial(self):
73
100
        """Topological sort with partial ordering.
74
101
 
75
 
        If the graph does not give an order between two nodes, they are 
76
 
        returned in lexicographical order.
 
102
        Multiple correct orderings are possible, so test for 
 
103
        correctness, not for exact match on the resulting list.
77
104
        """
78
 
        self.assertSortAndIterate(([(0, []),
 
105
        self.assertSortAndIterateOrder([(0, []),
79
106
                                   (1, [0]),
80
107
                                   (2, [0]),
81
108
                                   (3, [0]),
83
110
                                   (5, [1, 2]),
84
111
                                   (6, [1, 2]),
85
112
                                   (7, [2, 3]),
86
 
                                   (8, [0, 1, 4, 5, 6])]),
87
 
                                  [0, 1, 2, 3, 4, 5, 6, 7, 8])
 
113
                                   (8, [0, 1, 4, 5, 6])])
88
114
 
89
115
    def test_tsort_unincluded_parent(self):
90
116
        """Sort nodes, but don't include some parents in the output"""
102
128
                           mainline_revisions=mainline_revisions,
103
129
                           generate_revno=generate_revno)
104
130
        if result_list != value:
105
 
            import pprint
106
131
            self.assertEqualDiff(pprint.pformat(result_list),
107
132
                                 pprint.pformat(value))
108
 
        self.assertEquals(result_list,
109
 
            merge_sort(graph, branch_tip, mainline_revisions=mainline_revisions,
110
 
                generate_revno=generate_revno))
111
133
        self.assertEqual(result_list,
112
134
            list(MergeSorter(
113
135
                graph,
140
162
                                  'id',
141
163
                                  [(0, 'id', 0, (1,), True)],
142
164
                                  True)
143
 
    
 
165
 
144
166
    def test_sequence_numbers_increase_no_merges(self):
145
167
        # emit a few revisions with no merges to check the sequence
146
168
        # numbering works in trivial cases
211
233
        self.assertSortAndIterate(graph, 'F',
212
234
            [(0, 'F', 0, (3,), False),
213
235
             (1, 'D', 1, (2,2,1), False),
214
 
             (2, 'C', 1, (2,1,1), True), # XXX: Shouldn't it be merge_depth=2?
 
236
             (2, 'C', 2, (2,1,1), True),
215
237
             (3, 'B', 0, (2,), False),
216
238
             (4, 'A', 0, (1,), True),
217
239
             ], True)
244
266
        # the merge depth marker should reflect the depth of the revision
245
267
        # in terms of merges out from the mainline
246
268
        # revid, depth, parents:
247
 
        #  A 0   [D, B]   
248
 
        #  B  1  [C, F]   
249
 
        #  C  1  [H] 
 
269
        #  A 0   [D, B]
 
270
        #  B  1  [C, F]
 
271
        #  C  1  [H]
250
272
        #  D 0   [H, E]
251
273
        #  E  1  [G, F]
252
274
        #  F   2 [G]
403
425
    def test_end_of_merge_multiple_revisions_merged_at_once(self):
404
426
        # when multiple branches are merged at once, both of their
405
427
        # branch-endpoints should be listed as end-of-merge.
406
 
        # Also, the order of the multiple merges should be 
 
428
        # Also, the order of the multiple merges should be
407
429
        # left-right shown top to bottom.
408
430
        # * means end of merge
409
 
        # A 0    [H, B, E] 
 
431
        # A 0    [H, B, E]
410
432
        # B  1   [D, C]
411
433
        # C   2  [D]       *
412
434
        # D  1   [H]       *
483
505
        # and thus when truncated to D,B,A it should show
484
506
        # A 0
485
507
        # B 0
486
 
        # C 1 
 
508
        # C 1
487
509
        # because C is brought in by B in this view and D
488
510
        # is the terminating revision id
489
511
        # this should also preserve revision numbers: C should still be 2.1.1
566
588
             ],
567
589
            True
568
590
            )
569
 
        
 
591
 
570
592
    def test_revnos_are_globally_assigned(self):
571
593
        """revnos are assigned according to the revision they derive from."""
572
 
        # in this test we setup a number of branches that all derive from 
573
 
        # the first revision, and then merge them one at a time, which 
 
594
        # in this test we setup a number of branches that all derive from
 
595
        # the first revision, and then merge them one at a time, which
574
596
        # should give the revisions as they merge numbers still deriving from
575
597
        # the revision were based on.
576
598
        # merge 3: J: ['G', 'I']