/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 breezy/tests/test_tsort.py

  • Committer: Jelmer Vernooij
  • Date: 2019-05-29 03:22:34 UTC
  • mfrom: (7303 work)
  • mto: This revision was merged to the branch mainline in revision 7306.
  • Revision ID: jelmer@jelmer.uk-20190529032234-mt3fuws8gq03tapi
Merge trunk.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/tests/test_tsort.py
34
34
                         list(TopoSorter(graph).iter_topo_order()))
35
35
 
36
36
    def assertSortAndIterateRaise(self, exception_type, graph):
37
 
        """Try both iterating and topo_sorting graph and expect an exception."""
 
37
        """Try iterating and topo_sorting graph and expect an exception."""
38
38
        self.assertRaises(exception_type, topo_sort, graph)
39
39
        self.assertRaises(exception_type,
40
40
                          list,
99
99
    def test_tsort_partial(self):
100
100
        """Topological sort with partial ordering.
101
101
 
102
 
        Multiple correct orderings are possible, so test for 
 
102
        Multiple correct orderings are possible, so test for
103
103
        correctness, not for exact match on the resulting list.
104
104
        """
105
105
        self.assertSortAndIterateOrder([(0, []),
106
 
                                   (1, [0]),
107
 
                                   (2, [0]),
108
 
                                   (3, [0]),
109
 
                                   (4, [1, 2, 3]),
110
 
                                   (5, [1, 2]),
111
 
                                   (6, [1, 2]),
112
 
                                   (7, [2, 3]),
113
 
                                   (8, [0, 1, 4, 5, 6])])
 
106
                                        (1, [0]),
 
107
                                        (2, [0]),
 
108
                                        (3, [0]),
 
109
                                        (4, [1, 2, 3]),
 
110
                                        (5, [1, 2]),
 
111
                                        (6, [1, 2]),
 
112
                                        (7, [2, 3]),
 
113
                                        (8, [0, 1, 4, 5, 6])])
114
114
 
115
115
    def test_tsort_unincluded_parent(self):
116
116
        """Sort nodes, but don't include some parents in the output"""
117
117
        self.assertSortAndIterate([(0, [1]),
118
118
                                   (1, [2])],
119
 
                                   [1, 0])
 
119
                                  [1, 0])
120
120
 
121
121
 
122
122
class MergeSortTests(TestCase):
123
123
 
124
124
    def assertSortAndIterate(self, graph, branch_tip, result_list,
125
 
            generate_revno, mainline_revisions=None):
126
 
        """Check that merge based sorting and iter_topo_order on graph works."""
 
125
                             generate_revno, mainline_revisions=None):
 
126
        """Check that merge based sort and iter_topo_order on graph works."""
127
127
        value = merge_sort(graph, branch_tip,
128
128
                           mainline_revisions=mainline_revisions,
129
129
                           generate_revno=generate_revno)
131
131
            self.assertEqualDiff(pprint.pformat(result_list),
132
132
                                 pprint.pformat(value))
133
133
        self.assertEqual(result_list,
134
 
            list(MergeSorter(
135
 
                graph,
136
 
                branch_tip,
137
 
                mainline_revisions=mainline_revisions,
138
 
                generate_revno=generate_revno,
139
 
                ).iter_topo_order()))
 
134
                         list(MergeSorter(
 
135
                             graph,
 
136
                             branch_tip,
 
137
                             mainline_revisions=mainline_revisions,
 
138
                             generate_revno=generate_revno,
 
139
                             ).iter_topo_order()))
140
140
 
141
141
    def test_merge_sort_empty(self):
142
142
        # sorting of an emptygraph does not error
231
231
                 'F': ['B', 'D'],
232
232
                 }
233
233
        self.assertSortAndIterate(graph, 'F',
234
 
            [(0, 'F', 0, (3,), False),
235
 
             (1, 'D', 1, (2, 2, 1), False),
236
 
             (2, 'C', 2, (2, 1, 1), True),
237
 
             (3, 'B', 0, (2,), False),
238
 
             (4, 'A', 0, (1,), True),
239
 
             ], True)
 
234
                                  [(0, 'F', 0, (3,), False),
 
235
                                   (1, 'D', 1, (2, 2, 1), False),
 
236
                                      (2, 'C', 2, (2, 1, 1), True),
 
237
                                      (3, 'B', 0, (2,), False),
 
238
                                      (4, 'A', 0, (1,), True),
 
239
                                   ], True)
240
240
        # A
241
241
        # |
242
242
        # B-.
254
254
                 'F': ['B', 'D'],
255
255
                 }
256
256
        self.assertSortAndIterate(graph, 'F',
257
 
            [(0, 'F', 0, (3,), False),
258
 
             (1, 'D', 1, (2, 1, 2), False),
259
 
             (2, 'C', 2, (2, 2, 1), True),
260
 
             (3, 'X', 1, (2, 1, 1), True),
261
 
             (4, 'B', 0, (2,), False),
262
 
             (5, 'A', 0, (1,), True),
263
 
             ], True)
 
257
                                  [(0, 'F', 0, (3,), False),
 
258
                                   (1, 'D', 1, (2, 1, 2), False),
 
259
                                      (2, 'C', 2, (2, 2, 1), True),
 
260
                                      (3, 'X', 1, (2, 1, 1), True),
 
261
                                      (4, 'B', 0, (2,), False),
 
262
                                      (5, 'A', 0, (1,), True),
 
263
                                   ], True)
264
264
 
265
265
    def test_merge_depth_with_nested_merges(self):
266
266
        # the merge depth marker should reflect the depth of the revision
307
307
             'H': []
308
308
             }.items(),
309
309
            'A',
310
 
            [(0, 'A', 0, (3,),  False),
 
310
            [(0, 'A', 0, (3,), False),
311
311
             (1, 'B', 1, (1, 3, 2), False),
312
312
             (2, 'C', 1, (1, 3, 1), True),
313
313
             (3, 'D', 0, (2,), False),
344
344
             'J': ['G', 'H'],
345
345
             'K': ['I'],
346
346
             'L': ['J', 'K'],
347
 
            }.items(),
 
347
             }.items(),
348
348
            'L',
349
349
            [(0, 'L', 0, (6,), False),
350
350
             (1, 'K', 1, (1, 3, 2), False),
357
357
             (8, 'C', 1, (1, 1, 1), True),
358
358
             (9, 'D', 0, (3,), False),
359
359
             (10, 'B', 0, (2,), False),
360
 
             (11, 'A', 0, (1,),  True),
 
360
             (11, 'A', 0, (1,), True),
361
361
             ],
362
362
            True
363
363
            )
378
378
             'L': ['J', 'K'],
379
379
             'M': ['A'],
380
380
             'N': ['L', 'M'],
381
 
            }.items(),
 
381
             }.items(),
382
382
            'N',
383
383
            [(0, 'N', 0, (7,), False),
384
384
             (1, 'M', 1, (1, 4, 1), True),
393
393
             (10, 'C', 1, (1, 1, 1), True),
394
394
             (11, 'D', 0, (3,), False),
395
395
             (12, 'B', 0, (2,), False),
396
 
             (13, 'A', 0, (1,),  True),
 
396
             (13, 'A', 0, (1,), True),
397
397
             ],
398
398
            True
399
399
            )
494
494
        # C 2 [D]
495
495
        # D 1 [E]
496
496
        # E 0
497
 
        # with a mainline of NONE,E,A (the inferred one) this will show the merge
498
 
        # depths above.
 
497
        # with a mainline of NONE,E,A (the inferred one) this will show the
 
498
        # merge depths above.
499
499
        # with a overriden mainline of NONE,E,D,B,A it should show:
500
500
        # A 0
501
501
        # B 0
567
567
        # The graph that is passed to tsort has had ghosts filtered out, but
568
568
        # the mainline history has not.
569
569
        self.assertSortAndIterate(
570
 
            {'B':[],
571
 
             'C':['B']}.items(),
 
570
            {'B': [],
 
571
             'C': ['B']}.items(),
572
572
            'C',
573
573
            [(0, 'C', 0, (2,), False),
574
574
             (1, 'B', 0, (1,), True),
575
575
             ],
576
 
             True, mainline_revisions=['A', 'B', 'C'])
 
576
            True, mainline_revisions=['A', 'B', 'C'])
577
577
 
578
578
    def test_parallel_root_sequence_numbers_increase_with_merges(self):
579
579
        """When there are parallel roots, check their revnos."""
610
610
        # root: A: []
611
611
        self.assertSortAndIterate(
612
612
            {'J': ['G', 'I'],
613
 
             'I': ['H',],
 
613
             'I': ['H', ],
614
614
             'H': ['A'],
615
615
             'G': ['D', 'F'],
616
616
             'F': ['E'],
670
670
             'P': ['N'],
671
671
             'Q': ['O', 'P'],
672
672
             'R': ['J', 'Q'],
673
 
            }.items(),
 
673
             }.items(),
674
674
            'R',
675
 
            [( 0, 'R', 0, (6,), False),
676
 
             ( 1, 'Q', 1, (0, 4, 5), False),
677
 
             ( 2, 'P', 2, (0, 6, 1), True),
678
 
             ( 3, 'O', 1, (0, 4, 4), False),
679
 
             ( 4, 'N', 1, (0, 4, 3), False),
680
 
             ( 5, 'M', 2, (0, 5, 1), True),
681
 
             ( 6, 'L', 1, (0, 4, 2), False),
682
 
             ( 7, 'K', 1, (0, 4, 1), True),
683
 
             ( 8, 'J', 0, (5,), False),
684
 
             ( 9, 'I', 1, (0, 3, 1), True),
 
675
            [(0, 'R', 0, (6,), False),
 
676
             (1, 'Q', 1, (0, 4, 5), False),
 
677
             (2, 'P', 2, (0, 6, 1), True),
 
678
             (3, 'O', 1, (0, 4, 4), False),
 
679
             (4, 'N', 1, (0, 4, 3), False),
 
680
             (5, 'M', 2, (0, 5, 1), True),
 
681
             (6, 'L', 1, (0, 4, 2), False),
 
682
             (7, 'K', 1, (0, 4, 1), True),
 
683
             (8, 'J', 0, (5,), False),
 
684
             (9, 'I', 1, (0, 3, 1), True),
685
685
             (10, 'H', 0, (4,), False),
686
686
             (11, 'G', 1, (0, 1, 3), False),
687
687
             (12, 'F', 2, (0, 2, 1), True),