/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_graph.py

  • Committer: Jelmer Vernooij
  • Date: 2018-11-16 23:15:15 UTC
  • mfrom: (7180 work)
  • mto: This revision was merged to the branch mainline in revision 7183.
  • Revision ID: jelmer@jelmer.uk-20181116231515-zqd2yn6kj8lfydyp
Merge trunk.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/tests/test_graph.py
139
139
                             b'd': [b'c'],
140
140
                             b'e': [b'd'],
141
141
                             b'f': [b'a', b'd'],
142
 
                            }
 
142
                             }
143
143
 
144
144
# Double shortcut
145
145
# Both sides will see b'A' first, even though it is actually a decendent of a
157
157
#   |/     \|
158
158
#   f       g
159
159
 
160
 
double_shortcut = {b'a':[NULL_REVISION], b'b':[b'a'], b'c':[b'b'],
161
 
                   b'd':[b'c'], b'e':[b'c'], b'f':[b'a', b'd'],
162
 
                   b'g':[b'a', b'e']}
 
160
double_shortcut = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'],
 
161
                   b'd': [b'c'], b'e': [b'c'], b'f': [b'a', b'd'],
 
162
                   b'g': [b'a', b'e']}
163
163
 
164
164
# Complex shortcut
165
165
# This has a failure mode in that a shortcut will find some nodes in common,
189
189
#     | l |
190
190
#     |/|/
191
191
#     m n
192
 
complex_shortcut = {b'a':[NULL_REVISION], b'b':[b'a'], b'c':[b'b'], b'd':[b'c'],
193
 
                    b'e':[b'd'], b'f':[b'd'], b'g':[b'f'], b'h':[b'f'],
194
 
                    b'i':[b'e', b'g'], b'j':[b'g'], b'k':[b'j'],
195
 
                    b'l':[b'k'], b'm':[b'i', b'l'], b'n':[b'l', b'h']}
 
192
complex_shortcut = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'],
 
193
                    b'e': [b'd'], b'f': [b'd'], b'g': [b'f'], b'h': [b'f'],
 
194
                    b'i': [b'e', b'g'], b'j': [b'g'], b'k': [b'j'],
 
195
                    b'l': [b'k'], b'm': [b'i', b'l'], b'n': [b'l', b'h']}
196
196
 
197
197
# NULL_REVISION
198
198
#     |
233
233
#     |/|/
234
234
#     t u
235
235
complex_shortcut2 = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'],
236
 
                    b'e': [b'd'], b'f': [b'e'], b'g': [b'f'], b'h': [b'd'], b'i': [b'g'],
237
 
                    b'j': [b'h'], b'k': [b'h', b'i'], b'l': [b'k'], b'm': [b'l'], b'n': [b'm'],
238
 
                    b'o': [b'n'], b'p': [b'o'], b'q': [b'p'], b'r': [b'q'], b's': [b'r'],
239
 
                    b't': [b'i', b's'], b'u': [b's', b'j'],
240
 
                    }
 
236
                     b'e': [b'd'], b'f': [b'e'], b'g': [b'f'], b'h': [b'd'], b'i': [b'g'],
 
237
                     b'j': [b'h'], b'k': [b'h', b'i'], b'l': [b'k'], b'm': [b'l'], b'n': [b'm'],
 
238
                     b'o': [b'n'], b'p': [b'o'], b'q': [b'p'], b'r': [b'q'], b's': [b'r'],
 
239
                     b't': [b'i', b's'], b'u': [b's', b'j'],
 
240
                     }
241
241
 
242
242
# Graph where different walkers will race to find the common and uncommon
243
243
# nodes.
290
290
# k-n exists so that the second pass still has nodes that are worth searching,
291
291
# rather than instantly cancelling the extra walker.
292
292
 
293
 
racing_shortcuts = {b'a':[NULL_REVISION], b'b':[b'a'], b'c':[b'b'], b'd':[b'c'],
294
 
    b'e':[b'd'], b'f':[b'e'], b'g':[b'f'], b'h':[b'g'], b'i':[b'h', b'o'], b'j':[b'i', b'y'],
295
 
    b'k':[b'd'], b'l':[b'k'], b'm':[b'l'], b'n':[b'm'], b'o':[b'n', b'g'], b'p':[b'f'],
296
 
    b'q':[b'p', b'm'], b'r':[b'o'], b's':[b'r'], b't':[b's'], b'u':[b't'], b'v':[b'u'],
297
 
    b'w':[b'v'], b'x':[b'w'], b'y':[b'x'], b'z':[b'x', b'q']}
 
293
racing_shortcuts = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'],
 
294
                    b'e': [b'd'], b'f': [b'e'], b'g': [b'f'], b'h': [b'g'], b'i': [b'h', b'o'], b'j': [b'i', b'y'],
 
295
                    b'k': [b'd'], b'l': [b'k'], b'm': [b'l'], b'n': [b'm'], b'o': [b'n', b'g'], b'p': [b'f'],
 
296
                    b'q': [b'p', b'm'], b'r': [b'o'], b's': [b'r'], b't': [b's'], b'u': [b't'], b'v': [b'u'],
 
297
                    b'w': [b'v'], b'x': [b'w'], b'y': [b'x'], b'z': [b'x', b'q']}
298
298
 
299
299
 
300
300
# A graph with multiple nodes unique to one side.
336
336
#     y   z
337
337
#
338
338
 
339
 
multiple_interesting_unique = {b'a':[NULL_REVISION], b'b':[b'a'], b'c':[b'b'],
340
 
    b'd':[b'c'], b'e':[b'd'], b'f':[b'd'], b'g':[b'e'], b'h':[b'e'], b'i':[b'f'],
341
 
    b'j':[b'g'], b'k':[b'g'], b'l':[b'h'], b'm':[b'i'], b'n':[b'k', b'l'],
342
 
    b'o':[b'm'], b'p':[b'm', b'l'], b'q':[b'n', b'o'], b'r':[b'q'], b's':[b'r'],
343
 
    b't':[b's'], b'u':[b't'], b'v':[b'u'], b'w':[b'v'], b'x':[b'w'],
344
 
    b'y':[b'j', b'x'], b'z':[b'x', b'p']}
 
339
multiple_interesting_unique = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'],
 
340
                               b'd': [b'c'], b'e': [b'd'], b'f': [b'd'], b'g': [b'e'], b'h': [b'e'], b'i': [b'f'],
 
341
                               b'j': [b'g'], b'k': [b'g'], b'l': [b'h'], b'm': [b'i'], b'n': [b'k', b'l'],
 
342
                               b'o': [b'm'], b'p': [b'm', b'l'], b'q': [b'n', b'o'], b'r': [b'q'], b's': [b'r'],
 
343
                               b't': [b's'], b'u': [b't'], b'v': [b'u'], b'w': [b'v'], b'x': [b'w'],
 
344
                               b'y': [b'j', b'x'], b'z': [b'x', b'p']}
345
345
 
346
346
 
347
347
# Shortcut with extra root
365
365
                       b'e': [b'd'],
366
366
                       b'f': [b'a', b'd', b'g'],
367
367
                       b'g': [NULL_REVISION],
368
 
                      }
 
368
                       }
369
369
 
370
370
#  NULL_REVISION
371
371
#       |
377
377
#     | \ |
378
378
#     a   c
379
379
 
380
 
boundary = {b'a': [b'b'], b'c': [b'b', b'd'], b'b':[b'e'], b'd':[b'e'], b'e': [b'f'],
381
 
            b'f':[NULL_REVISION]}
 
380
boundary = {b'a': [b'b'], b'c': [b'b', b'd'], b'b': [b'e'], b'd': [b'e'], b'e': [b'f'],
 
381
            b'f': [NULL_REVISION]}
382
382
 
383
383
 
384
384
# A graph that contains a ghost
392
392
#     | \ |
393
393
#     a   c
394
394
 
395
 
with_ghost = {b'a': [b'b'], b'c': [b'b', b'd'], b'b':[b'e'], b'd':[b'e', b'g'],
396
 
              b'e': [b'f'], b'f':[NULL_REVISION], NULL_REVISION:()}
 
395
with_ghost = {b'a': [b'b'], b'c': [b'b', b'd'], b'b': [b'e'], b'd': [b'e', b'g'],
 
396
              b'e': [b'f'], b'f': [NULL_REVISION], NULL_REVISION: ()}
397
397
 
398
398
# A graph that shows we can shortcut finding revnos when reaching them from the
399
399
# side.
415
415
#     |
416
416
#     i
417
417
 
418
 
with_tail = {b'a':[NULL_REVISION], b'b':[b'a'], b'c':[b'b'], b'd':[b'c'], b'e':[b'd'],
419
 
             b'f':[b'e'], b'g':[b'e'], b'h':[b'f'], b'i':[b'h']}
 
418
with_tail = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'], b'e': [b'd'],
 
419
             b'f': [b'e'], b'g': [b'e'], b'h': [b'f'], b'i': [b'h']}
420
420
 
421
421
 
422
422
class InstrumentedParentsProvider(object):
469
469
        """Make a Graph that raises an exception if we hit a node."""
470
470
        g = self.make_graph(ancestors)
471
471
        orig_parent_map = g.get_parent_map
 
472
 
472
473
        def get_parent_map(keys):
473
474
            bad_keys = set(keys).intersection(break_on)
474
475
            if bad_keys:
508
509
                parents = [p for p in ancestors[descendant] if p is not
509
510
                           NULL_REVISION]
510
511
                if len([p for p in parents if not
511
 
                    tree.branch.repository.has_revision(p)]) > 0:
 
512
                        tree.branch.repository.has_revision(p)]) > 0:
512
513
                    continue
513
514
                tree.set_parent_ids(parents)
514
515
                if len(parents) > 0:
564
565
        """A simple does it work test for graph.lefthand_distance(keys)."""
565
566
        nodes = {b'nonghost': [NULL_REVISION], b'toghost': [b'ghost']}
566
567
        graph = self.make_graph(nodes)
567
 
        distance_graph = graph.find_lefthand_distances([b'nonghost', b'toghost'])
 
568
        distance_graph = graph.find_lefthand_distances(
 
569
            [b'nonghost', b'toghost'])
568
570
        self.assertEqual({b'nonghost': 1, b'toghost': -1}, distance_graph)
569
571
 
570
572
    def test_recursive_unique_lca(self):
581
583
        self.assertEqual(b'rev1', graph.find_unique_lca(b'rev2a', b'rev2b'))
582
584
        self.assertEqual((b'rev1', 1,),
583
585
                         graph.find_unique_lca(b'rev2a', b'rev2b',
584
 
                         count_steps=True))
 
586
                                               count_steps=True))
585
587
 
586
588
    def assertRemoveDescendants(self, expected, graph, revisions):
587
589
        parents = graph.get_parent_map(revisions)
591
593
    def test__remove_simple_descendants(self):
592
594
        graph = self.make_graph(ancestry_1)
593
595
        self.assertRemoveDescendants({b'rev1'}, graph,
594
 
            {b'rev1', b'rev2a', b'rev2b', b'rev3', b'rev4'})
 
596
                                     {b'rev1', b'rev2a', b'rev2b', b'rev3', b'rev4'})
595
597
 
596
598
    def test__remove_simple_descendants_disjoint(self):
597
599
        graph = self.make_graph(ancestry_1)
598
600
        self.assertRemoveDescendants({b'rev1', b'rev3'}, graph,
599
 
            {b'rev1', b'rev3'})
 
601
                                     {b'rev1', b'rev3'})
600
602
 
601
603
    def test__remove_simple_descendants_chain(self):
602
604
        graph = self.make_graph(ancestry_1)
603
605
        self.assertRemoveDescendants({b'rev1'}, graph,
604
 
            {b'rev1', b'rev2a', b'rev3'})
 
606
                                     {b'rev1', b'rev2a', b'rev3'})
605
607
 
606
608
    def test__remove_simple_descendants_siblings(self):
607
609
        graph = self.make_graph(ancestry_1)
608
610
        self.assertRemoveDescendants({b'rev2a', b'rev2b'}, graph,
609
 
            {b'rev2a', b'rev2b', b'rev3'})
 
611
                                     {b'rev2a', b'rev2b', b'rev3'})
610
612
 
611
613
    def test_unique_lca_criss_cross(self):
612
614
        """Ensure we don't pick non-unique lcas in a criss-cross"""
613
615
        graph = self.make_graph(criss_cross)
614
616
        self.assertEqual(b'rev1', graph.find_unique_lca(b'rev3a', b'rev3b'))
615
 
        lca, steps = graph.find_unique_lca(b'rev3a', b'rev3b', count_steps=True)
 
617
        lca, steps = graph.find_unique_lca(
 
618
            b'rev3a', b'rev3b', count_steps=True)
616
619
        self.assertEqual(b'rev1', lca)
617
620
        self.assertEqual(2, steps)
618
621
 
651
654
 
652
655
    def test_graph_difference(self):
653
656
        graph = self.make_graph(ancestry_1)
654
 
        self.assertEqual((set(), set()), graph.find_difference(b'rev1', b'rev1'))
 
657
        self.assertEqual(
 
658
            (set(), set()), graph.find_difference(b'rev1', b'rev1'))
655
659
        self.assertEqual((set(), {b'rev1'}),
656
660
                         graph.find_difference(NULL_REVISION, b'rev1'))
657
661
        self.assertEqual(({b'rev1'}, set()),
755
759
        nodes[NULL_REVISION] = ()
756
760
        graph = self.make_graph(nodes)
757
761
        expected = nodes.copy()
758
 
        expected.pop(b'a') # b'a' is not in the ancestry of b'c', all the
759
 
                          # other nodes are
 
762
        expected.pop(b'a')  # b'a' is not in the ancestry of b'c', all the
 
763
        # other nodes are
760
764
        self.assertEqual(expected, dict(graph.iter_ancestry([b'c'])))
761
765
        self.assertEqual(nodes, dict(graph.iter_ancestry([b'a', b'c'])))
762
766
 
879
883
        """
880
884
        class stub(object):
881
885
            pass
 
886
 
882
887
        def get_parent_map(keys):
883
888
            result = {}
884
889
            for key in keys:
899
904
            b'common': [b'deeper'],
900
905
        }
901
906
        self.assertEqual({b'left', b'right'},
902
 
            self._run_heads_break_deeper(graph_dict, [b'left', b'right']))
 
907
                         self._run_heads_break_deeper(graph_dict, [b'left', b'right']))
903
908
 
904
909
    def test_heads_limits_search_assymetric(self):
905
910
        # test that a heads query does not search all of history
911
916
            b'aftercommon': [b'deeper'],
912
917
        }
913
918
        self.assertEqual({b'left', b'right'},
914
 
            self._run_heads_break_deeper(graph_dict, [b'left', b'right']))
 
919
                         self._run_heads_break_deeper(graph_dict, [b'left', b'right']))
915
920
 
916
921
    def test_heads_limits_search_common_search_must_continue(self):
917
922
        # test that common nodes are still queried, preventing
924
929
            b'common2': [b'deeper'],
925
930
        }
926
931
        self.assertEqual({b'h1', b'h2'},
927
 
            self._run_heads_break_deeper(graph_dict, [b'h1', b'h2']))
 
932
                         self._run_heads_break_deeper(graph_dict, [b'h1', b'h2']))
928
933
 
929
934
    def test_breadth_first_search_start_ghosts(self):
930
935
        graph = self.make_graph({})
948
953
        self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
949
954
        self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
950
955
        self.assertEqual(({b'child'}, {b'ghost'}),
951
 
            search.next_with_ghosts())
 
956
                         search.next_with_ghosts())
952
957
        self.assertRaises(StopIteration, search.next_with_ghosts)
953
958
        # next includes them
954
959
        search = graph._make_breadth_first_searcher([b'head'])
955
960
        self.assertEqual({b'head'}, next(search))
956
961
        self.assertEqual({b'present'}, next(search))
957
962
        self.assertEqual({b'child', b'ghost'},
958
 
            next(search))
 
963
                         next(search))
959
964
        self.assertRaises(StopIteration, next, search)
960
965
 
961
966
    def test_breadth_first_search_change_next_to_next_with_ghosts(self):
971
976
        self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
972
977
        self.assertEqual({b'present'}, next(search))
973
978
        self.assertEqual(({b'child'}, {b'ghost'}),
974
 
            search.next_with_ghosts())
 
979
                         search.next_with_ghosts())
975
980
        self.assertRaises(StopIteration, next, search)
976
981
        # start with next
977
982
        search = graph._make_breadth_first_searcher([b'head'])
978
983
        self.assertEqual({b'head'}, next(search))
979
984
        self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
980
985
        self.assertEqual({b'child', b'ghost'},
981
 
            next(search))
 
986
                         next(search))
982
987
        self.assertRaises(StopIteration, search.next_with_ghosts)
983
988
 
984
989
    def test_breadth_first_change_search(self):
993
998
        self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
994
999
        self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
995
1000
        self.assertEqual({b'present'},
996
 
            search.stop_searching_any([b'present']))
 
1001
                         search.stop_searching_any([b'present']))
997
1002
        self.assertEqual(({b'other'}, {b'other_ghost'}),
998
 
            search.start_searching([b'other', b'other_ghost']))
 
1003
                         search.start_searching([b'other', b'other_ghost']))
999
1004
        self.assertEqual(({b'other_2'}, set()), search.next_with_ghosts())
1000
1005
        self.assertRaises(StopIteration, search.next_with_ghosts)
1001
1006
        # next includes them
1003
1008
        self.assertEqual({b'head'}, next(search))
1004
1009
        self.assertEqual({b'present'}, next(search))
1005
1010
        self.assertEqual({b'present'},
1006
 
            search.stop_searching_any([b'present']))
 
1011
                         search.stop_searching_any([b'present']))
1007
1012
        search.start_searching([b'other', b'other_ghost'])
1008
1013
        self.assertEqual({b'other_2'}, next(search))
1009
1014
        self.assertRaises(StopIteration, next, search)
1043
1048
        # At the start, nothing has been seen, to its all excluded:
1044
1049
        state = search.get_state()
1045
1050
        self.assertEqual(({b'head'}, {b'head'}, set()),
1046
 
            state)
 
1051
                         state)
1047
1052
        self.assertEqual(set(), search.seen)
1048
1053
        # using next:
1049
1054
        expected = [
1061
1066
 
1062
1067
    def test_breadth_first_get_result_starts_stops(self):
1063
1068
        graph = self.make_graph({
1064
 
            b'head':[b'child'],
1065
 
            b'child':[NULL_REVISION],
1066
 
            b'otherhead':[b'otherchild'],
1067
 
            b'otherchild':[b'excluded'],
1068
 
            b'excluded':[NULL_REVISION],
1069
 
            NULL_REVISION:[]
 
1069
            b'head': [b'child'],
 
1070
            b'child': [NULL_REVISION],
 
1071
            b'otherhead': [b'otherchild'],
 
1072
            b'otherchild': [b'excluded'],
 
1073
            b'excluded': [NULL_REVISION],
 
1074
            NULL_REVISION: []
1070
1075
            })
1071
1076
        search = graph._make_breadth_first_searcher([])
1072
1077
        # Starting with nothing and adding a search works:
1074
1079
        # head has been seen:
1075
1080
        state = search.get_state()
1076
1081
        self.assertEqual(({b'head'}, {b'child'}, {b'head'}),
1077
 
            state)
 
1082
                         state)
1078
1083
        self.assertEqual({b'head'}, search.seen)
1079
1084
        # using next:
1080
1085
        expected = [
1290
1295
    def test_multiple_revisions(self):
1291
1296
        graph = self.make_graph(ancestry_1)
1292
1297
        self.assertFindUniqueAncestors(graph,
1293
 
            [b'rev4'], b'rev4', [b'rev3', b'rev2b'])
 
1298
                                       [b'rev4'], b'rev4', [b'rev3', b'rev2b'])
1294
1299
        self.assertFindUniqueAncestors(graph,
1295
 
            [b'rev2a', b'rev3', b'rev4'], b'rev4', [b'rev2b'])
 
1300
                                       [b'rev2a', b'rev3', b'rev4'], b'rev4', [b'rev2b'])
1296
1301
 
1297
1302
    def test_complex_shortcut(self):
1298
1303
        graph = self.make_graph(complex_shortcut)
1299
1304
        self.assertFindUniqueAncestors(graph,
1300
 
            [b'h', b'n'], b'n', [b'm'])
 
1305
                                       [b'h', b'n'], b'n', [b'm'])
1301
1306
        self.assertFindUniqueAncestors(graph,
1302
 
            [b'e', b'i', b'm'], b'm', [b'n'])
 
1307
                                       [b'e', b'i', b'm'], b'm', [b'n'])
1303
1308
 
1304
1309
    def test_complex_shortcut2(self):
1305
1310
        graph = self.make_graph(complex_shortcut2)
1306
1311
        self.assertFindUniqueAncestors(graph,
1307
 
            [b'j', b'u'], b'u', [b't'])
 
1312
                                       [b'j', b'u'], b'u', [b't'])
1308
1313
        self.assertFindUniqueAncestors(graph,
1309
 
            [b't'], b't', [b'u'])
 
1314
                                       [b't'], b't', [b'u'])
1310
1315
 
1311
1316
    def test_multiple_interesting_unique(self):
1312
1317
        graph = self.make_graph(multiple_interesting_unique)
1313
1318
        self.assertFindUniqueAncestors(graph,
1314
 
            [b'j', b'y'], b'y', [b'z'])
 
1319
                                       [b'j', b'y'], b'y', [b'z'])
1315
1320
        self.assertFindUniqueAncestors(graph,
1316
 
            [b'p', b'z'], b'z', [b'y'])
 
1321
                                       [b'p', b'z'], b'z', [b'y'])
1317
1322
 
1318
1323
    def test_racing_shortcuts(self):
1319
1324
        graph = self.make_graph(racing_shortcuts)
1320
1325
        self.assertFindUniqueAncestors(graph,
1321
 
            [b'p', b'q', b'z'], b'z', [b'y'])
 
1326
                                       [b'p', b'q', b'z'], b'z', [b'y'])
1322
1327
        self.assertFindUniqueAncestors(graph,
1323
 
            [b'h', b'i', b'j', b'y'], b'j', [b'z'])
 
1328
                                       [b'h', b'i', b'j', b'y'], b'j', [b'z'])
1324
1329
 
1325
1330
 
1326
1331
class TestGraphFindDistanceToNull(TestGraphBase):
1390
1395
    def test_parents(self):
1391
1396
        graph = self.make_graph(ancestry_1)
1392
1397
        self.assertMergeOrder([b'rev3', b'rev2b'], graph, b'rev4',
1393
 
                                                        [b'rev3', b'rev2b'])
 
1398
                              [b'rev3', b'rev2b'])
1394
1399
        self.assertMergeOrder([b'rev3', b'rev2b'], graph, b'rev4',
1395
 
                                                        [b'rev2b', b'rev3'])
 
1400
                              [b'rev2b', b'rev3'])
1396
1401
 
1397
1402
    def test_ancestors(self):
1398
1403
        graph = self.make_graph(ancestry_1)
1399
1404
        self.assertMergeOrder([b'rev1', b'rev2b'], graph, b'rev4',
1400
 
                                                        [b'rev1', b'rev2b'])
 
1405
                              [b'rev1', b'rev2b'])
1401
1406
        self.assertMergeOrder([b'rev1', b'rev2b'], graph, b'rev4',
1402
 
                                                        [b'rev2b', b'rev1'])
 
1407
                              [b'rev2b', b'rev1'])
1403
1408
 
1404
1409
    def test_shortcut_one_ancestor(self):
1405
1410
        # When we have enough info, we can stop searching
1406
 
        graph = self.make_breaking_graph(ancestry_1, [b'rev3', b'rev2b', b'rev4'])
 
1411
        graph = self.make_breaking_graph(
 
1412
            ancestry_1, [b'rev3', b'rev2b', b'rev4'])
1407
1413
        # Single ancestors shortcut right away
1408
1414
        self.assertMergeOrder([b'rev3'], graph, b'rev4', [b'rev3'])
1409
1415
 
1410
1416
    def test_shortcut_after_one_ancestor(self):
1411
1417
        graph = self.make_breaking_graph(ancestry_1, [b'rev2a', b'rev2b'])
1412
 
        self.assertMergeOrder([b'rev3', b'rev1'], graph, b'rev4', [b'rev1', b'rev3'])
 
1418
        self.assertMergeOrder([b'rev3', b'rev1'], graph,
 
1419
                              b'rev4', [b'rev1', b'rev3'])
1413
1420
 
1414
1421
 
1415
1422
class TestFindDescendants(TestGraphBase):
1430
1437
        descendants = graph.find_descendants(b'rev2a', b'rev4')
1431
1438
        self.assertEqual({b'rev2a', b'rev3', b'rev4'}, descendants)
1432
1439
 
 
1440
 
1433
1441
class TestFindLefthandMerger(TestGraphBase):
1434
1442
 
1435
1443
    def check_merger(self, result, ancestry, merged, tip):
1464
1472
                          b'rev2a': [b'rev3'],
1465
1473
                          b'rev2b': [b'rev4'],
1466
1474
                          b'rev3': [b'rev4']},
1467
 
                          child_map)
 
1475
                         child_map)
1468
1476
 
1469
1477
 
1470
1478
class TestCachingParentsProvider(tests.TestCase):
1484
1492
    def test_get_parent_map(self):
1485
1493
        """Requesting the same revision should be returned from cache"""
1486
1494
        self.assertEqual({}, self.caching_pp._cache)
1487
 
        self.assertEqual({b'a':(b'b',)}, self.caching_pp.get_parent_map([b'a']))
 
1495
        self.assertEqual(
 
1496
            {b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a']))
1488
1497
        self.assertEqual([b'a'], self.inst_pp.calls)
1489
 
        self.assertEqual({b'a':(b'b',)}, self.caching_pp.get_parent_map([b'a']))
 
1498
        self.assertEqual(
 
1499
            {b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a']))
1490
1500
        # No new call, as it should have been returned from the cache
1491
1501
        self.assertEqual([b'a'], self.inst_pp.calls)
1492
 
        self.assertEqual({b'a':(b'b',)}, self.caching_pp._cache)
 
1502
        self.assertEqual({b'a': (b'b',)}, self.caching_pp._cache)
1493
1503
 
1494
1504
    def test_get_parent_map_not_present(self):
1495
1505
        """The cache should also track when a revision doesn't exist"""
1503
1513
        """Anything that can be returned from cache, should be"""
1504
1514
        self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1505
1515
        self.assertEqual([b'b'], self.inst_pp.calls)
1506
 
        self.assertEqual({b'a':(b'b',)},
 
1516
        self.assertEqual({b'a': (b'b',)},
1507
1517
                         self.caching_pp.get_parent_map([b'a', b'b']))
1508
1518
        self.assertEqual([b'b', b'a'], self.inst_pp.calls)
1509
1519
 
1510
1520
    def test_get_parent_map_repeated(self):
1511
1521
        """Asking for the same parent 2x will only forward 1 request."""
1512
 
        self.assertEqual({b'a':(b'b',)},
 
1522
        self.assertEqual({b'a': (b'b',)},
1513
1523
                         self.caching_pp.get_parent_map([b'b', b'a', b'b']))
1514
1524
        # Use sorted because we don't care about the order, just that each is
1515
1525
        # only present 1 time.
1525
1535
    def test_get_cached_parent_map(self):
1526
1536
        self.assertEqual({}, self.caching_pp.get_cached_parent_map([b'a']))
1527
1537
        self.assertEqual([], self.inst_pp.calls)
1528
 
        self.assertEqual({b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a']))
 
1538
        self.assertEqual(
 
1539
            {b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a']))
1529
1540
        self.assertEqual([b'a'], self.inst_pp.calls)
1530
1541
        self.assertEqual({b'a': (b'b',)},
1531
1542
                         self.caching_pp.get_cached_parent_map([b'a']))
1536
1547
 
1537
1548
    def setUp(self):
1538
1549
        super(TestCachingParentsProviderExtras, self).setUp()
 
1550
 
1539
1551
        class ExtraParentsProvider(object):
1540
1552
 
1541
1553
            def get_parent_map(self, keys):
1542
 
                return {b'rev1': [], b'rev2': [b'rev1',]}
 
1554
                return {b'rev1': [], b'rev2': [b'rev1', ]}
1543
1555
 
1544
1556
        self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1545
1557
        self.caching_pp = _mod_graph.CachingParentsProvider(
1562
1574
        self.assertEqual({b'rev1': [], b'rev2': [b'rev1']},
1563
1575
                         self.caching_pp._cache)
1564
1576
        self.assertEqual({b'rev1': []},
1565
 
                          self.caching_pp.get_parent_map([b'rev1']))
 
1577
                         self.caching_pp.get_parent_map([b'rev1']))
1566
1578
        self.assertEqual([b'rev1'], self.inst_pp.calls)
1567
1579
 
1568
1580
    def test_disable_cache_clears_cache(self):
1602
1614
        self.assertEqual([b'rev3'], self.inst_pp.calls)
1603
1615
 
1604
1616
 
1605
 
 
1606
1617
class TestCollapseLinearRegions(tests.TestCase):
1607
1618
 
1608
1619
    def assertCollapsed(self, collapsed, original):
1610
1621
                         _mod_graph.collapse_linear_regions(original))
1611
1622
 
1612
1623
    def test_collapse_nothing(self):
1613
 
        d = {1:[2, 3], 2:[], 3:[]}
 
1624
        d = {1: [2, 3], 2: [], 3: []}
1614
1625
        self.assertCollapsed(d, d)
1615
 
        d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
 
1626
        d = {1: [2], 2: [3, 4], 3: [5], 4: [5], 5: []}
1616
1627
        self.assertCollapsed(d, d)
1617
1628
 
1618
1629
    def test_collapse_chain(self):
1619
1630
        # Any time we have a linear chain, we should be able to collapse
1620
 
        d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1621
 
        self.assertCollapsed({1:[5], 5:[]}, d)
1622
 
        d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1623
 
        self.assertCollapsed({5:[1], 1:[]}, d)
1624
 
        d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1625
 
        self.assertCollapsed({5:[2], 2:[]}, d)
 
1631
        d = {1: [2], 2: [3], 3: [4], 4: [5], 5: []}
 
1632
        self.assertCollapsed({1: [5], 5: []}, d)
 
1633
        d = {5: [4], 4: [3], 3: [2], 2: [1], 1: []}
 
1634
        self.assertCollapsed({5: [1], 1: []}, d)
 
1635
        d = {5: [3], 3: [4], 4: [1], 1: [2], 2: []}
 
1636
        self.assertCollapsed({5: [2], 2: []}, d)
1626
1637
 
1627
1638
    def test_collapse_with_multiple_children(self):
1628
1639
        #    7
1637
1648
        #
1638
1649
        # 4 and 5 cannot be removed because 6 has 2 children
1639
1650
        # 2 and 3 cannot be removed because 1 has 2 parents
1640
 
        d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
 
1651
        d = {1: [2, 3], 2: [4], 4: [6], 3: [5], 5: [6], 6: [7], 7: []}
1641
1652
        self.assertCollapsed(d, d)
1642
1653
 
1643
1654
 
1649
1660
        # B C
1650
1661
        # |/
1651
1662
        # D
1652
 
        d = {(b'D',): [(b'B',), (b'C',)], (b'C',):[(b'A',)],
 
1663
        d = {(b'D',): [(b'B',), (b'C',)], (b'C',): [(b'A',)],
1653
1664
             (b'B',): [(b'A',)], (b'A',): []}
1654
1665
        g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1655
1666
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1659
1670
        self.assertEqual([b'B', b'C'], sorted(graph_thunk.heads([b'B', b'C'])))
1660
1671
 
1661
1672
    def test_add_node(self):
1662
 
        d = {(b'C',):[(b'A',)], (b'B',): [(b'A',)], (b'A',): []}
 
1673
        d = {(b'C',): [(b'A',)], (b'B',): [(b'A',)], (b'A',): []}
1663
1674
        g = _mod_graph.KnownGraph(d)
1664
1675
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1665
1676
        graph_thunk.add_node(b"D", [b"A", b"C"])
1666
1677
        self.assertEqual([b'B', b'D'],
1667
 
            sorted(graph_thunk.heads([b'D', b'B', b'A'])))
 
1678
                         sorted(graph_thunk.heads([b'D', b'B', b'A'])))
1668
1679
 
1669
1680
    def test_merge_sort(self):
1670
 
        d = {(b'C',):[(b'A',)], (b'B',): [(b'A',)], (b'A',): []}
 
1681
        d = {(b'C',): [(b'A',)], (b'B',): [(b'A',)], (b'A',): []}
1671
1682
        g = _mod_graph.KnownGraph(d)
1672
1683
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1673
1684
        graph_thunk.add_node(b"D", [b"A", b"C"])
1674
1685
        self.assertEqual([(b'C', 0, (2,), False), (b'A', 0, (1,), True)],
1675
 
            [(n.key, n.merge_depth, n.revno, n.end_of_merge)
1676
 
                 for n in graph_thunk.merge_sort(b'C')])
 
1686
                         [(n.key, n.merge_depth, n.revno, n.end_of_merge)
 
1687
                          for n in graph_thunk.merge_sort(b'C')])
1677
1688
 
1678
1689
 
1679
1690
class TestStackedParentsProvider(tests.TestCase):
1692
1703
        parents1 = _mod_graph.DictParentsProvider({b'rev2': [b'rev3']})
1693
1704
        parents2 = _mod_graph.DictParentsProvider({b'rev1': [b'rev4']})
1694
1705
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1695
 
        self.assertEqual({b'rev1':[b'rev4'], b'rev2':[b'rev3']},
 
1706
        self.assertEqual({b'rev1': [b'rev4'], b'rev2': [b'rev3']},
1696
1707
                         stacked.get_parent_map([b'rev1', b'rev2']))
1697
 
        self.assertEqual({b'rev2':[b'rev3'], b'rev1':[b'rev4']},
 
1708
        self.assertEqual({b'rev2': [b'rev3'], b'rev1': [b'rev4']},
1698
1709
                         stacked.get_parent_map([b'rev2', b'rev1']))
1699
 
        self.assertEqual({b'rev2':[b'rev3']},
 
1710
        self.assertEqual({b'rev2': [b'rev3']},
1700
1711
                         stacked.get_parent_map([b'rev2', b'rev2']))
1701
 
        self.assertEqual({b'rev1':[b'rev4']},
 
1712
        self.assertEqual({b'rev1': [b'rev4']},
1702
1713
                         stacked.get_parent_map([b'rev1', b'rev1']))
1703
1714
 
1704
1715
    def test_stacked_parents_provider_overlapping(self):
1720
1731
        pp2 = self.get_shared_provider(b'pp2', {b'rev2': (b'rev1',)},
1721
1732
                                       has_cached=True)
1722
1733
        stacked = _mod_graph.StackedParentsProvider([pp1, pp2])
1723
 
        self.assertEqual({b'rev2': (b'rev1',)}, stacked.get_parent_map([b'rev2']))
 
1734
        self.assertEqual({b'rev2': (b'rev1',)},
 
1735
                         stacked.get_parent_map([b'rev2']))
1724
1736
        # No call on b'pp1' because it doesn't provide get_cached_parent_map
1725
1737
        self.assertEqual([(b'pp2', 'cached', [b'rev2'])], self.calls)
1726
1738
 
1729
1741
        # get_parent_map. Further, we should track what entries we have found,
1730
1742
        # and not re-try them.
1731
1743
        pp1 = self.get_shared_provider(b'pp1', {b'a': ()}, has_cached=True)
1732
 
        pp2 = self.get_shared_provider(b'pp2', {b'c': (b'b',)}, has_cached=False)
1733
 
        pp3 = self.get_shared_provider(b'pp3', {b'b': (b'a',)}, has_cached=True)
 
1744
        pp2 = self.get_shared_provider(
 
1745
            b'pp2', {b'c': (b'b',)}, has_cached=False)
 
1746
        pp3 = self.get_shared_provider(
 
1747
            b'pp3', {b'b': (b'a',)}, has_cached=True)
1734
1748
        stacked = _mod_graph.StackedParentsProvider([pp1, pp2, pp3])
1735
1749
        self.assertEqual({b'a': (), b'b': (b'a',), b'c': (b'b',)},
1736
1750
                         stacked.get_parent_map([b'a', b'b', b'c', b'd']))
1740
1754
                          (b'pp1', [b'c', b'd']),
1741
1755
                          (b'pp2', [b'c', b'd']),
1742
1756
                          (b'pp3', [b'd']),
1743
 
                         ], self.calls)
 
1757
                          ], self.calls)