620
648
graph = mainline_tree.branch.repository.get_graph(
621
649
feature_tree.branch.repository)
622
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
650
self.assertEqual(b'rev2b', graph.find_unique_lca(b'rev2a', b'rev3b'))
624
652
def test_graph_difference(self):
625
653
graph = self.make_graph(ancestry_1)
626
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
627
self.assertEqual((set(), set(['rev1'])),
628
graph.find_difference(NULL_REVISION, 'rev1'))
629
self.assertEqual((set(['rev1']), set()),
630
graph.find_difference('rev1', NULL_REVISION))
631
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
632
graph.find_difference('rev3', 'rev2b'))
633
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
634
graph.find_difference('rev4', 'rev2b'))
654
self.assertEqual((set(), set()), graph.find_difference(b'rev1', b'rev1'))
655
self.assertEqual((set(), {b'rev1'}),
656
graph.find_difference(NULL_REVISION, b'rev1'))
657
self.assertEqual(({b'rev1'}, set()),
658
graph.find_difference(b'rev1', NULL_REVISION))
659
self.assertEqual(({b'rev2a', b'rev3'}, {b'rev2b'}),
660
graph.find_difference(b'rev3', b'rev2b'))
661
self.assertEqual(({b'rev4', b'rev3', b'rev2a'}, set()),
662
graph.find_difference(b'rev4', b'rev2b'))
636
664
def test_graph_difference_separate_ancestry(self):
637
665
graph = self.make_graph(ancestry_2)
638
self.assertEqual((set(['rev1a']), set(['rev1b'])),
639
graph.find_difference('rev1a', 'rev1b'))
640
self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
642
graph.find_difference('rev4a', 'rev1b'))
666
self.assertEqual(({b'rev1a'}, {b'rev1b'}),
667
graph.find_difference(b'rev1a', b'rev1b'))
668
self.assertEqual(({b'rev1a', b'rev2a', b'rev3a', b'rev4a'},
670
graph.find_difference(b'rev4a', b'rev1b'))
644
672
def test_graph_difference_criss_cross(self):
645
673
graph = self.make_graph(criss_cross)
646
self.assertEqual((set(['rev3a']), set(['rev3b'])),
647
graph.find_difference('rev3a', 'rev3b'))
648
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
649
graph.find_difference('rev2a', 'rev3b'))
674
self.assertEqual(({b'rev3a'}, {b'rev3b'}),
675
graph.find_difference(b'rev3a', b'rev3b'))
676
self.assertEqual((set([]), {b'rev3b', b'rev2b'}),
677
graph.find_difference(b'rev2a', b'rev3b'))
651
679
def test_graph_difference_extended_history(self):
652
680
graph = self.make_graph(extended_history_shortcut)
653
self.assertEqual((set(['e']), set(['f'])),
654
graph.find_difference('e', 'f'))
655
self.assertEqual((set(['f']), set(['e'])),
656
graph.find_difference('f', 'e'))
681
self.assertEqual(({b'e'}, {b'f'}),
682
graph.find_difference(b'e', b'f'))
683
self.assertEqual(({b'f'}, {b'e'}),
684
graph.find_difference(b'f', b'e'))
658
686
def test_graph_difference_double_shortcut(self):
659
687
graph = self.make_graph(double_shortcut)
660
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
661
graph.find_difference('f', 'g'))
688
self.assertEqual(({b'd', b'f'}, {b'e', b'g'}),
689
graph.find_difference(b'f', b'g'))
663
691
def test_graph_difference_complex_shortcut(self):
664
692
graph = self.make_graph(complex_shortcut)
665
self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
666
graph.find_difference('m', 'n'))
693
self.assertEqual(({b'm', b'i', b'e'}, {b'n', b'h'}),
694
graph.find_difference(b'm', b'n'))
668
696
def test_graph_difference_complex_shortcut2(self):
669
697
graph = self.make_graph(complex_shortcut2)
670
self.assertEqual((set(['t']), set(['j', 'u'])),
671
graph.find_difference('t', 'u'))
698
self.assertEqual(({b't'}, {b'j', b'u'}),
699
graph.find_difference(b't', b'u'))
673
701
def test_graph_difference_shortcut_extra_root(self):
674
702
graph = self.make_graph(shortcut_extra_root)
675
self.assertEqual((set(['e']), set(['f', 'g'])),
676
graph.find_difference('e', 'f'))
679
def test_stacked_parents_provider(self):
680
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
681
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
682
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
683
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
684
stacked.get_parent_map(['rev1', 'rev2']))
685
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
686
stacked.get_parent_map(['rev2', 'rev1']))
687
self.assertEqual({'rev2':['rev3']},
688
stacked.get_parent_map(['rev2', 'rev2']))
689
self.assertEqual({'rev1':['rev4']},
690
stacked.get_parent_map(['rev1', 'rev1']))
692
def test_stacked_parents_provider_overlapping(self):
693
# rev2 is availible in both providers.
697
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
698
parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
699
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
700
self.assertEqual({'rev2': ['rev1']},
701
stacked.get_parent_map(['rev2']))
703
def test__stacked_parents_provider_deprecated(self):
704
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
705
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
706
stacked = self.applyDeprecated(deprecated_in((1, 16, 0)),
707
_mod_graph._StackedParentsProvider, [parents1, parents2])
708
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
709
stacked.get_parent_map(['rev1', 'rev2']))
710
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
711
stacked.get_parent_map(['rev2', 'rev1']))
712
self.assertEqual({'rev2':['rev3']},
713
stacked.get_parent_map(['rev2', 'rev2']))
714
self.assertEqual({'rev1':['rev4']},
715
stacked.get_parent_map(['rev1', 'rev1']))
703
self.assertEqual(({b'e'}, {b'f', b'g'}),
704
graph.find_difference(b'e', b'f'))
717
706
def test_iter_topo_order(self):
718
707
graph = self.make_graph(ancestry_1)
719
args = ['rev2a', 'rev3', 'rev1']
708
args = [b'rev2a', b'rev3', b'rev1']
720
709
topo_args = list(graph.iter_topo_order(args))
721
710
self.assertEqual(set(args), set(topo_args))
722
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
723
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
711
self.assertTrue(topo_args.index(b'rev2a') > topo_args.index(b'rev1'))
712
self.assertTrue(topo_args.index(b'rev2a') < topo_args.index(b'rev3'))
725
714
def test_is_ancestor(self):
726
715
graph = self.make_graph(ancestry_1)
727
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
728
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
729
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
730
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
731
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
732
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
733
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
734
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
735
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
716
self.assertEqual(True, graph.is_ancestor(b'null:', b'null:'))
717
self.assertEqual(True, graph.is_ancestor(b'null:', b'rev1'))
718
self.assertEqual(False, graph.is_ancestor(b'rev1', b'null:'))
719
self.assertEqual(True, graph.is_ancestor(b'null:', b'rev4'))
720
self.assertEqual(False, graph.is_ancestor(b'rev4', b'null:'))
721
self.assertEqual(False, graph.is_ancestor(b'rev4', b'rev2b'))
722
self.assertEqual(True, graph.is_ancestor(b'rev2b', b'rev4'))
723
self.assertEqual(False, graph.is_ancestor(b'rev2b', b'rev3'))
724
self.assertEqual(False, graph.is_ancestor(b'rev3', b'rev2b'))
736
725
instrumented_provider = InstrumentedParentsProvider(graph)
737
726
instrumented_graph = _mod_graph.Graph(instrumented_provider)
738
instrumented_graph.is_ancestor('rev2a', 'rev2b')
739
self.assertTrue('null:' not in instrumented_provider.calls)
727
instrumented_graph.is_ancestor(b'rev2a', b'rev2b')
728
self.assertTrue(b'null:' not in instrumented_provider.calls)
741
730
def test_is_between(self):
742
731
graph = self.make_graph(ancestry_1)
743
self.assertEqual(True, graph.is_between('null:', 'null:', 'null:'))
744
self.assertEqual(True, graph.is_between('rev1', 'null:', 'rev1'))
745
self.assertEqual(True, graph.is_between('rev1', 'rev1', 'rev4'))
746
self.assertEqual(True, graph.is_between('rev4', 'rev1', 'rev4'))
747
self.assertEqual(True, graph.is_between('rev3', 'rev1', 'rev4'))
748
self.assertEqual(False, graph.is_between('rev4', 'rev1', 'rev3'))
749
self.assertEqual(False, graph.is_between('rev1', 'rev2a', 'rev4'))
750
self.assertEqual(False, graph.is_between('null:', 'rev1', 'rev4'))
732
self.assertEqual(True, graph.is_between(b'null:', b'null:', b'null:'))
733
self.assertEqual(True, graph.is_between(b'rev1', b'null:', b'rev1'))
734
self.assertEqual(True, graph.is_between(b'rev1', b'rev1', b'rev4'))
735
self.assertEqual(True, graph.is_between(b'rev4', b'rev1', b'rev4'))
736
self.assertEqual(True, graph.is_between(b'rev3', b'rev1', b'rev4'))
737
self.assertEqual(False, graph.is_between(b'rev4', b'rev1', b'rev3'))
738
self.assertEqual(False, graph.is_between(b'rev1', b'rev2a', b'rev4'))
739
self.assertEqual(False, graph.is_between(b'null:', b'rev1', b'rev4'))
752
741
def test_is_ancestor_boundary(self):
753
742
"""Ensure that we avoid searching the whole graph.
803
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
804
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
805
self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
792
graph = self.make_graph({b'c': [b'b', b'd'], b'd': [b'e'], b'b': [b'a'],
793
b'a': [NULL_REVISION], b'e': [NULL_REVISION]})
794
self.assertEqual({b'c'}, graph.heads([b'a', b'c', b'e']))
807
796
def test_heads_null(self):
808
797
graph = self.make_graph(ancestry_1)
809
self.assertEqual(set(['null:']), graph.heads(['null:']))
810
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
811
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
812
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
813
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
798
self.assertEqual({b'null:'}, graph.heads([b'null:']))
799
self.assertEqual({b'rev1'}, graph.heads([b'null:', b'rev1']))
800
self.assertEqual({b'rev1'}, graph.heads([b'rev1', b'null:']))
801
self.assertEqual({b'rev1'}, graph.heads({b'rev1', b'null:'}))
802
self.assertEqual({b'rev1'}, graph.heads((b'rev1', b'null:')))
815
804
def test_heads_one(self):
816
805
# A single node will always be a head
817
806
graph = self.make_graph(ancestry_1)
818
self.assertEqual(set(['null:']), graph.heads(['null:']))
819
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
820
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
821
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
822
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
823
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
807
self.assertEqual({b'null:'}, graph.heads([b'null:']))
808
self.assertEqual({b'rev1'}, graph.heads([b'rev1']))
809
self.assertEqual({b'rev2a'}, graph.heads([b'rev2a']))
810
self.assertEqual({b'rev2b'}, graph.heads([b'rev2b']))
811
self.assertEqual({b'rev3'}, graph.heads([b'rev3']))
812
self.assertEqual({b'rev4'}, graph.heads([b'rev4']))
825
814
def test_heads_single(self):
826
815
graph = self.make_graph(ancestry_1)
827
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
828
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
829
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
830
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
831
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
832
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
833
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
834
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
816
self.assertEqual({b'rev4'}, graph.heads([b'null:', b'rev4']))
817
self.assertEqual({b'rev2a'}, graph.heads([b'rev1', b'rev2a']))
818
self.assertEqual({b'rev2b'}, graph.heads([b'rev1', b'rev2b']))
819
self.assertEqual({b'rev3'}, graph.heads([b'rev1', b'rev3']))
820
self.assertEqual({b'rev4'}, graph.heads([b'rev1', b'rev4']))
821
self.assertEqual({b'rev4'}, graph.heads([b'rev2a', b'rev4']))
822
self.assertEqual({b'rev4'}, graph.heads([b'rev2b', b'rev4']))
823
self.assertEqual({b'rev4'}, graph.heads([b'rev3', b'rev4']))
836
825
def test_heads_two_heads(self):
837
826
graph = self.make_graph(ancestry_1)
838
self.assertEqual(set(['rev2a', 'rev2b']),
839
graph.heads(['rev2a', 'rev2b']))
840
self.assertEqual(set(['rev3', 'rev2b']),
841
graph.heads(['rev3', 'rev2b']))
827
self.assertEqual({b'rev2a', b'rev2b'},
828
graph.heads([b'rev2a', b'rev2b']))
829
self.assertEqual({b'rev3', b'rev2b'},
830
graph.heads([b'rev3', b'rev2b']))
843
832
def test_heads_criss_cross(self):
844
833
graph = self.make_graph(criss_cross)
845
self.assertEqual(set(['rev2a']),
846
graph.heads(['rev2a', 'rev1']))
847
self.assertEqual(set(['rev2b']),
848
graph.heads(['rev2b', 'rev1']))
849
self.assertEqual(set(['rev3a']),
850
graph.heads(['rev3a', 'rev1']))
851
self.assertEqual(set(['rev3b']),
852
graph.heads(['rev3b', 'rev1']))
853
self.assertEqual(set(['rev2a', 'rev2b']),
854
graph.heads(['rev2a', 'rev2b']))
855
self.assertEqual(set(['rev3a']),
856
graph.heads(['rev3a', 'rev2a']))
857
self.assertEqual(set(['rev3a']),
858
graph.heads(['rev3a', 'rev2b']))
859
self.assertEqual(set(['rev3a']),
860
graph.heads(['rev3a', 'rev2a', 'rev2b']))
861
self.assertEqual(set(['rev3b']),
862
graph.heads(['rev3b', 'rev2a']))
863
self.assertEqual(set(['rev3b']),
864
graph.heads(['rev3b', 'rev2b']))
865
self.assertEqual(set(['rev3b']),
866
graph.heads(['rev3b', 'rev2a', 'rev2b']))
867
self.assertEqual(set(['rev3a', 'rev3b']),
868
graph.heads(['rev3a', 'rev3b']))
869
self.assertEqual(set(['rev3a', 'rev3b']),
870
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
834
self.assertEqual({b'rev2a'},
835
graph.heads([b'rev2a', b'rev1']))
836
self.assertEqual({b'rev2b'},
837
graph.heads([b'rev2b', b'rev1']))
838
self.assertEqual({b'rev3a'},
839
graph.heads([b'rev3a', b'rev1']))
840
self.assertEqual({b'rev3b'},
841
graph.heads([b'rev3b', b'rev1']))
842
self.assertEqual({b'rev2a', b'rev2b'},
843
graph.heads([b'rev2a', b'rev2b']))
844
self.assertEqual({b'rev3a'},
845
graph.heads([b'rev3a', b'rev2a']))
846
self.assertEqual({b'rev3a'},
847
graph.heads([b'rev3a', b'rev2b']))
848
self.assertEqual({b'rev3a'},
849
graph.heads([b'rev3a', b'rev2a', b'rev2b']))
850
self.assertEqual({b'rev3b'},
851
graph.heads([b'rev3b', b'rev2a']))
852
self.assertEqual({b'rev3b'},
853
graph.heads([b'rev3b', b'rev2b']))
854
self.assertEqual({b'rev3b'},
855
graph.heads([b'rev3b', b'rev2a', b'rev2b']))
856
self.assertEqual({b'rev3a', b'rev3b'},
857
graph.heads([b'rev3a', b'rev3b']))
858
self.assertEqual({b'rev3a', b'rev3b'},
859
graph.heads([b'rev3a', b'rev3b', b'rev2a', b'rev2b']))
872
861
def test_heads_shortcut(self):
873
862
graph = self.make_graph(history_shortcut)
875
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
876
graph.heads(['rev2a', 'rev2b', 'rev2c']))
877
self.assertEqual(set(['rev3a', 'rev3b']),
878
graph.heads(['rev3a', 'rev3b']))
879
self.assertEqual(set(['rev3a', 'rev3b']),
880
graph.heads(['rev2a', 'rev3a', 'rev3b']))
881
self.assertEqual(set(['rev2a', 'rev3b']),
882
graph.heads(['rev2a', 'rev3b']))
883
self.assertEqual(set(['rev2c', 'rev3a']),
884
graph.heads(['rev2c', 'rev3a']))
864
self.assertEqual({b'rev2a', b'rev2b', b'rev2c'},
865
graph.heads([b'rev2a', b'rev2b', b'rev2c']))
866
self.assertEqual({b'rev3a', b'rev3b'},
867
graph.heads([b'rev3a', b'rev3b']))
868
self.assertEqual({b'rev3a', b'rev3b'},
869
graph.heads([b'rev2a', b'rev3a', b'rev3b']))
870
self.assertEqual({b'rev2a', b'rev3b'},
871
graph.heads([b'rev2a', b'rev3b']))
872
self.assertEqual({b'rev2c', b'rev3a'},
873
graph.heads([b'rev2c', b'rev3a']))
886
875
def _run_heads_break_deeper(self, graph_dict, search):
887
876
"""Run heads on a graph-as-a-dict.
889
If the search asks for the parents of 'deeper' the test will fail.
878
If the search asks for the parents of b'deeper' the test will fail.
891
880
class stub(object):
893
882
def get_parent_map(keys):
897
886
self.fail('key deeper was accessed')
898
887
result[key] = graph_dict[key]
905
894
def test_heads_limits_search(self):
906
895
# test that a heads query does not search all of history
897
b'left': [b'common'],
898
b'right': [b'common'],
899
b'common': [b'deeper'],
912
self.assertEqual(set(['left', 'right']),
913
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
901
self.assertEqual({b'left', b'right'},
902
self._run_heads_break_deeper(graph_dict, [b'left', b'right']))
915
904
def test_heads_limits_search_assymetric(self):
916
905
# test that a heads query does not search all of history
919
'midleft':['common'],
921
'common':['aftercommon'],
922
'aftercommon':['deeper'],
907
b'left': [b'midleft'],
908
b'midleft': [b'common'],
909
b'right': [b'common'],
910
b'common': [b'aftercommon'],
911
b'aftercommon': [b'deeper'],
924
self.assertEqual(set(['left', 'right']),
925
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
913
self.assertEqual({b'left', b'right'},
914
self._run_heads_break_deeper(graph_dict, [b'left', b'right']))
927
916
def test_heads_limits_search_common_search_must_continue(self):
928
917
# test that common nodes are still queried, preventing
929
918
# all-the-way-to-origin behaviour in the following graph:
931
'h1':['shortcut', 'common1'],
933
'shortcut':['common2'],
934
'common1':['common2'],
935
'common2':['deeper'],
920
b'h1': [b'shortcut', b'common1'],
922
b'shortcut': [b'common2'],
923
b'common1': [b'common2'],
924
b'common2': [b'deeper'],
937
self.assertEqual(set(['h1', 'h2']),
938
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
926
self.assertEqual({b'h1', b'h2'},
927
self._run_heads_break_deeper(graph_dict, [b'h1', b'h2']))
940
929
def test_breadth_first_search_start_ghosts(self):
941
930
graph = self.make_graph({})
942
931
# with_ghosts reports the ghosts
943
search = graph._make_breadth_first_searcher(['a-ghost'])
944
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
932
search = graph._make_breadth_first_searcher([b'a-ghost'])
933
self.assertEqual((set(), {b'a-ghost'}), search.next_with_ghosts())
945
934
self.assertRaises(StopIteration, search.next_with_ghosts)
946
935
# next includes them
947
search = graph._make_breadth_first_searcher(['a-ghost'])
948
self.assertEqual(set(['a-ghost']), search.next())
949
self.assertRaises(StopIteration, search.next)
936
search = graph._make_breadth_first_searcher([b'a-ghost'])
937
self.assertEqual({b'a-ghost'}, next(search))
938
self.assertRaises(StopIteration, next, search)
951
940
def test_breadth_first_search_deep_ghosts(self):
952
941
graph = self.make_graph({
954
'present':['child', 'ghost'],
942
b'head': [b'present'],
943
b'present': [b'child', b'ghost'],
957
946
# with_ghosts reports the ghosts
958
search = graph._make_breadth_first_searcher(['head'])
959
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
960
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
961
self.assertEqual((set(['child']), set(['ghost'])),
947
search = graph._make_breadth_first_searcher([b'head'])
948
self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
949
self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
950
self.assertEqual(({b'child'}, {b'ghost'}),
962
951
search.next_with_ghosts())
963
952
self.assertRaises(StopIteration, search.next_with_ghosts)
964
953
# next includes them
965
search = graph._make_breadth_first_searcher(['head'])
966
self.assertEqual(set(['head']), search.next())
967
self.assertEqual(set(['present']), search.next())
968
self.assertEqual(set(['child', 'ghost']),
970
self.assertRaises(StopIteration, search.next)
954
search = graph._make_breadth_first_searcher([b'head'])
955
self.assertEqual({b'head'}, next(search))
956
self.assertEqual({b'present'}, next(search))
957
self.assertEqual({b'child', b'ghost'},
959
self.assertRaises(StopIteration, next, search)
972
961
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
973
962
# To make the API robust, we allow calling both next() and
974
963
# next_with_ghosts() on the same searcher.
975
964
graph = self.make_graph({
977
'present':['child', 'ghost'],
965
b'head': [b'present'],
966
b'present': [b'child', b'ghost'],
980
969
# start with next_with_ghosts
981
search = graph._make_breadth_first_searcher(['head'])
982
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
983
self.assertEqual(set(['present']), search.next())
984
self.assertEqual((set(['child']), set(['ghost'])),
970
search = graph._make_breadth_first_searcher([b'head'])
971
self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
972
self.assertEqual({b'present'}, next(search))
973
self.assertEqual(({b'child'}, {b'ghost'}),
985
974
search.next_with_ghosts())
986
self.assertRaises(StopIteration, search.next)
975
self.assertRaises(StopIteration, next, search)
987
976
# start with next
988
search = graph._make_breadth_first_searcher(['head'])
989
self.assertEqual(set(['head']), search.next())
990
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
991
self.assertEqual(set(['child', 'ghost']),
977
search = graph._make_breadth_first_searcher([b'head'])
978
self.assertEqual({b'head'}, next(search))
979
self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
980
self.assertEqual({b'child', b'ghost'},
993
982
self.assertRaises(StopIteration, search.next_with_ghosts)
995
984
def test_breadth_first_change_search(self):
996
985
# Changing the search should work with both next and next_with_ghosts.
997
986
graph = self.make_graph({
999
'present':['stopped'],
1000
'other':['other_2'],
987
b'head': [b'present'],
988
b'present': [b'stopped'],
989
b'other': [b'other_2'],
1003
search = graph._make_breadth_first_searcher(['head'])
1004
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
1005
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
1006
self.assertEqual(set(['present']),
1007
search.stop_searching_any(['present']))
1008
self.assertEqual((set(['other']), set(['other_ghost'])),
1009
search.start_searching(['other', 'other_ghost']))
1010
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
992
search = graph._make_breadth_first_searcher([b'head'])
993
self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
994
self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
995
self.assertEqual({b'present'},
996
search.stop_searching_any([b'present']))
997
self.assertEqual(({b'other'}, {b'other_ghost'}),
998
search.start_searching([b'other', b'other_ghost']))
999
self.assertEqual(({b'other_2'}, set()), search.next_with_ghosts())
1011
1000
self.assertRaises(StopIteration, search.next_with_ghosts)
1012
1001
# next includes them
1013
search = graph._make_breadth_first_searcher(['head'])
1014
self.assertEqual(set(['head']), search.next())
1015
self.assertEqual(set(['present']), search.next())
1016
self.assertEqual(set(['present']),
1017
search.stop_searching_any(['present']))
1018
search.start_searching(['other', 'other_ghost'])
1019
self.assertEqual(set(['other_2']), search.next())
1020
self.assertRaises(StopIteration, search.next)
1002
search = graph._make_breadth_first_searcher([b'head'])
1003
self.assertEqual({b'head'}, next(search))
1004
self.assertEqual({b'present'}, next(search))
1005
self.assertEqual({b'present'},
1006
search.stop_searching_any([b'present']))
1007
search.start_searching([b'other', b'other_ghost'])
1008
self.assertEqual({b'other_2'}, next(search))
1009
self.assertRaises(StopIteration, next, search)
1022
1011
def assertSeenAndResult(self, instructions, search, next):
1023
1012
"""Check the results of .seen and get_result() for a seach.
1040
1029
search.start_searching(starts)
1041
1030
if stops is not None:
1042
1031
search.stop_searching_any(stops)
1043
result = search.get_result()
1044
self.assertEqual(recipe, result.get_recipe())
1045
self.assertEqual(set(included_keys), result.get_keys())
1032
state = search.get_state()
1033
self.assertEqual(set(included_keys), state[2])
1046
1034
self.assertEqual(seen, search.seen)
1048
1036
def test_breadth_first_get_result_excludes_current_pending(self):
1049
1037
graph = self.make_graph({
1051
'child':[NULL_REVISION],
1038
b'head': [b'child'],
1039
b'child': [NULL_REVISION],
1054
search = graph._make_breadth_first_searcher(['head'])
1042
search = graph._make_breadth_first_searcher([b'head'])
1055
1043
# At the start, nothing has been seen, to its all excluded:
1056
result = search.get_result()
1057
self.assertEqual(('search', set(['head']), set(['head']), 0),
1058
result.get_recipe())
1059
self.assertEqual(set(), result.get_keys())
1044
state = search.get_state()
1045
self.assertEqual(({b'head'}, {b'head'}, set()),
1060
1047
self.assertEqual(set(), search.seen)
1063
(set(['head']), (set(['head']), set(['child']), 1),
1064
['head'], None, None),
1065
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
1066
['head', 'child'], None, None),
1067
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
1068
['head', 'child', NULL_REVISION], None, None),
1050
({b'head'}, ({b'head'}, {b'child'}, 1),
1051
[b'head'], None, None),
1052
({b'head', b'child'}, ({b'head'}, {NULL_REVISION}, 2),
1053
[b'head', b'child'], None, None),
1054
({b'head', b'child', NULL_REVISION}, ({b'head'}, set(), 3),
1055
[b'head', b'child', NULL_REVISION], None, None),
1070
self.assertSeenAndResult(expected, search, search.next)
1057
self.assertSeenAndResult(expected, search, search.__next__)
1071
1058
# using next_with_ghosts:
1072
search = graph._make_breadth_first_searcher(['head'])
1059
search = graph._make_breadth_first_searcher([b'head'])
1073
1060
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1075
1062
def test_breadth_first_get_result_starts_stops(self):
1076
1063
graph = self.make_graph({
1078
'child':[NULL_REVISION],
1079
'otherhead':['otherchild'],
1080
'otherchild':['excluded'],
1081
'excluded':[NULL_REVISION],
1065
b'child':[NULL_REVISION],
1066
b'otherhead':[b'otherchild'],
1067
b'otherchild':[b'excluded'],
1068
b'excluded':[NULL_REVISION],
1082
1069
NULL_REVISION:[]
1084
1071
search = graph._make_breadth_first_searcher([])
1085
1072
# Starting with nothing and adding a search works:
1086
search.start_searching(['head'])
1073
search.start_searching([b'head'])
1087
1074
# head has been seen:
1088
result = search.get_result()
1089
self.assertEqual(('search', set(['head']), set(['child']), 1),
1090
result.get_recipe())
1091
self.assertEqual(set(['head']), result.get_keys())
1092
self.assertEqual(set(['head']), search.seen)
1075
state = search.get_state()
1076
self.assertEqual(({b'head'}, {b'child'}, {b'head'}),
1078
self.assertEqual({b'head'}, search.seen)
1095
1081
# stop at child, and start a new search at otherhead:
1096
1082
# - otherhead counts as seen immediately when start_searching is
1098
(set(['head', 'child', 'otherhead']),
1099
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1100
['head', 'otherhead'], ['otherhead'], ['child']),
1101
(set(['head', 'child', 'otherhead', 'otherchild']),
1102
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1103
['head', 'otherhead', 'otherchild'], None, None),
1084
({b'head', b'child', b'otherhead'},
1085
({b'head', b'otherhead'}, {b'child', b'otherchild'}, 2),
1086
[b'head', b'otherhead'], [b'otherhead'], [b'child']),
1087
({b'head', b'child', b'otherhead', b'otherchild'},
1088
({b'head', b'otherhead'}, {b'child', b'excluded'}, 3),
1089
[b'head', b'otherhead', b'otherchild'], None, None),
1104
1090
# stop searching excluded now
1105
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1106
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1107
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1091
({b'head', b'child', b'otherhead', b'otherchild', b'excluded'},
1092
({b'head', b'otherhead'}, {b'child', b'excluded'}, 3),
1093
[b'head', b'otherhead', b'otherchild'], None, [b'excluded']),
1109
self.assertSeenAndResult(expected, search, search.next)
1095
self.assertSeenAndResult(expected, search, search.__next__)
1110
1096
# using next_with_ghosts:
1111
1097
search = graph._make_breadth_first_searcher([])
1112
search.start_searching(['head'])
1098
search.start_searching([b'head'])
1113
1099
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1115
1101
def test_breadth_first_stop_searching_not_queried(self):
1116
# A client should be able to say 'stop node X' even if X has not been
1102
# A client should be able to say b'stop node X' even if X has not been
1117
1103
# returned to the client.
1118
1104
graph = self.make_graph({
1119
'head':['child', 'ghost1'],
1120
'child':[NULL_REVISION],
1105
b'head': [b'child', b'ghost1'],
1106
b'child': [NULL_REVISION],
1123
search = graph._make_breadth_first_searcher(['head'])
1109
search = graph._make_breadth_first_searcher([b'head'])
1125
1111
# NULL_REVISION and ghost1 have not been returned
1127
(set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1128
['head'], None, [NULL_REVISION, 'ghost1']),
1113
({b'head'}, {b'child', NULL_REVISION, b'ghost1'}, 1),
1114
[b'head'], None, [NULL_REVISION, b'ghost1']),
1129
1115
# ghost1 has been returned, NULL_REVISION is to be returned in the
1130
1116
# next iteration.
1131
(set(['head', 'child', 'ghost1']),
1132
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1133
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1117
({b'head', b'child', b'ghost1'},
1118
({b'head'}, {b'ghost1', NULL_REVISION}, 2),
1119
[b'head', b'child'], None, [NULL_REVISION, b'ghost1']),
1135
self.assertSeenAndResult(expected, search, search.next)
1121
self.assertSeenAndResult(expected, search, search.__next__)
1136
1122
# using next_with_ghosts:
1137
search = graph._make_breadth_first_searcher(['head'])
1123
search = graph._make_breadth_first_searcher([b'head'])
1138
1124
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1140
1126
def test_breadth_first_stop_searching_late(self):
1141
# A client should be able to say 'stop node X' and have it excluded
1127
# A client should be able to say b'stop node X' and have it excluded
1142
1128
# from the result even if X was seen in an older iteration of the
1144
1130
graph = self.make_graph({
1147
'child':[NULL_REVISION],
1131
b'head': [b'middle'],
1132
b'middle': [b'child'],
1133
b'child': [NULL_REVISION],
1150
search = graph._make_breadth_first_searcher(['head'])
1136
search = graph._make_breadth_first_searcher([b'head'])
1152
(set(['head']), (set(['head']), set(['middle']), 1),
1153
['head'], None, None),
1154
(set(['head', 'middle']), (set(['head']), set(['child']), 2),
1155
['head', 'middle'], None, None),
1156
# 'middle' came from the previous iteration, but we don't stop
1138
({b'head'}, ({b'head'}, {b'middle'}, 1),
1139
[b'head'], None, None),
1140
({b'head', b'middle'}, ({b'head'}, {b'child'}, 2),
1141
[b'head', b'middle'], None, None),
1142
# b'middle' came from the previous iteration, but we don't stop
1157
1143
# searching it until *after* advancing the searcher.
1158
(set(['head', 'middle', 'child']),
1159
(set(['head']), set(['middle', 'child']), 1),
1160
['head'], None, ['middle', 'child']),
1144
({b'head', b'middle', b'child'},
1145
({b'head'}, {b'middle', b'child'}, 1),
1146
[b'head'], None, [b'middle', b'child']),
1162
self.assertSeenAndResult(expected, search, search.next)
1148
self.assertSeenAndResult(expected, search, search.__next__)
1163
1149
# using next_with_ghosts:
1164
search = graph._make_breadth_first_searcher(['head'])
1150
search = graph._make_breadth_first_searcher([b'head'])
1165
1151
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1167
1153
def test_breadth_first_get_result_ghosts_are_excluded(self):
1168
1154
graph = self.make_graph({
1169
'head':['child', 'ghost'],
1170
'child':[NULL_REVISION],
1155
b'head': [b'child', b'ghost'],
1156
b'child': [NULL_REVISION],
1173
search = graph._make_breadth_first_searcher(['head'])
1159
search = graph._make_breadth_first_searcher([b'head'])
1177
(set(['head']), set(['ghost', 'child']), 1),
1178
['head'], None, None),
1179
(set(['head', 'child', 'ghost']),
1180
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1181
['head', 'child'], None, None),
1163
({b'head'}, {b'ghost', b'child'}, 1),
1164
[b'head'], None, None),
1165
({b'head', b'child', b'ghost'},
1166
({b'head'}, {NULL_REVISION, b'ghost'}, 2),
1167
[b'head', b'child'], None, None),
1183
self.assertSeenAndResult(expected, search, search.next)
1169
self.assertSeenAndResult(expected, search, search.__next__)
1184
1170
# using next_with_ghosts:
1185
search = graph._make_breadth_first_searcher(['head'])
1171
search = graph._make_breadth_first_searcher([b'head'])
1186
1172
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1188
1174
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1189
1175
graph = self.make_graph({
1191
'child':[NULL_REVISION],
1176
b'head': [b'child'],
1177
b'child': [NULL_REVISION],
1194
search = graph._make_breadth_first_searcher(['head'])
1180
search = graph._make_breadth_first_searcher([b'head'])
1197
(set(['head', 'ghost']),
1198
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1199
['head'], ['ghost'], None),
1200
(set(['head', 'child', 'ghost']),
1201
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1202
['head', 'child'], None, None),
1183
({b'head', b'ghost'},
1184
({b'head', b'ghost'}, {b'child', b'ghost'}, 1),
1185
[b'head'], [b'ghost'], None),
1186
({b'head', b'child', b'ghost'},
1187
({b'head', b'ghost'}, {NULL_REVISION, b'ghost'}, 2),
1188
[b'head', b'child'], None, None),
1204
self.assertSeenAndResult(expected, search, search.next)
1190
self.assertSeenAndResult(expected, search, search.__next__)
1205
1191
# using next_with_ghosts:
1206
search = graph._make_breadth_first_searcher(['head'])
1192
search = graph._make_breadth_first_searcher([b'head'])
1207
1193
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1209
1195
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1210
1196
graph = self.make_graph({
1211
'head':[NULL_REVISION],
1197
b'head': [NULL_REVISION],
1214
search = graph._make_breadth_first_searcher(['head'])
1200
search = graph._make_breadth_first_searcher([b'head'])
1218
(set(['head']), set([NULL_REVISION]), 1),
1219
['head'], None, None),
1220
(set(['head', NULL_REVISION]),
1221
(set(['head']), set([]), 2),
1222
['head', NULL_REVISION], None, None),
1204
({b'head'}, {NULL_REVISION}, 1),
1205
[b'head'], None, None),
1206
({b'head', NULL_REVISION},
1207
({b'head'}, set([]), 2),
1208
[b'head', NULL_REVISION], None, None),
1224
self.assertSeenAndResult(expected, search, search.next)
1210
self.assertSeenAndResult(expected, search, search.__next__)
1225
1211
# using next_with_ghosts:
1226
search = graph._make_breadth_first_searcher(['head'])
1212
search = graph._make_breadth_first_searcher([b'head'])
1227
1213
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1229
1215
def test_breadth_first_search_get_result_after_StopIteration(self):
1230
1216
# StopIteration should not invalid anything..
1231
1217
graph = self.make_graph({
1232
'head':[NULL_REVISION],
1218
b'head': [NULL_REVISION],
1235
search = graph._make_breadth_first_searcher(['head'])
1221
search = graph._make_breadth_first_searcher([b'head'])
1239
(set(['head']), set([NULL_REVISION]), 1),
1240
['head'], None, None),
1241
(set(['head', 'ghost', NULL_REVISION]),
1242
(set(['head', 'ghost']), set(['ghost']), 2),
1243
['head', NULL_REVISION], ['ghost'], None),
1225
({b'head'}, {NULL_REVISION}, 1),
1226
[b'head'], None, None),
1227
({b'head', b'ghost', NULL_REVISION},
1228
({b'head', b'ghost'}, {b'ghost'}, 2),
1229
[b'head', NULL_REVISION], [b'ghost'], None),
1245
self.assertSeenAndResult(expected, search, search.next)
1246
self.assertRaises(StopIteration, search.next)
1247
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1248
result = search.get_result()
1249
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1250
result.get_recipe())
1251
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1231
self.assertSeenAndResult(expected, search, search.__next__)
1232
self.assertRaises(StopIteration, next, search)
1233
self.assertEqual({b'head', b'ghost', NULL_REVISION}, search.seen)
1234
state = search.get_state()
1236
({b'ghost', b'head'}, {b'ghost'},
1237
{b'head', NULL_REVISION}),
1252
1239
# using next_with_ghosts:
1253
search = graph._make_breadth_first_searcher(['head'])
1240
search = graph._make_breadth_first_searcher([b'head'])
1254
1241
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1255
self.assertRaises(StopIteration, search.next)
1256
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1257
result = search.get_result()
1258
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1259
result.get_recipe())
1260
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1242
self.assertRaises(StopIteration, next, search)
1243
self.assertEqual({b'head', b'ghost', NULL_REVISION}, search.seen)
1244
state = search.get_state()
1246
({b'ghost', b'head'}, {b'ghost'},
1247
{b'head', NULL_REVISION}),
1263
1251
class TestFindUniqueAncestors(TestGraphBase):
1269
1257
def test_empty_set(self):
1270
1258
graph = self.make_graph(ancestry_1)
1271
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1272
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1273
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1259
self.assertFindUniqueAncestors(graph, [], b'rev1', [b'rev1'])
1260
self.assertFindUniqueAncestors(graph, [], b'rev2b', [b'rev2b'])
1261
self.assertFindUniqueAncestors(graph, [], b'rev3', [b'rev1', b'rev3'])
1275
1263
def test_single_node(self):
1276
1264
graph = self.make_graph(ancestry_1)
1277
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1278
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1279
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1265
self.assertFindUniqueAncestors(graph, [b'rev2a'], b'rev2a', [b'rev1'])
1266
self.assertFindUniqueAncestors(graph, [b'rev2b'], b'rev2b', [b'rev1'])
1267
self.assertFindUniqueAncestors(graph, [b'rev3'], b'rev3', [b'rev2a'])
1281
1269
def test_minimal_ancestry(self):
1282
1270
graph = self.make_breaking_graph(extended_history_shortcut,
1283
[NULL_REVISION, 'a', 'b'])
1284
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1271
[NULL_REVISION, b'a', b'b'])
1272
self.assertFindUniqueAncestors(graph, [b'e'], b'e', [b'd'])
1286
1274
graph = self.make_breaking_graph(extended_history_shortcut,
1288
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1276
self.assertFindUniqueAncestors(graph, [b'f'], b'f', [b'a', b'd'])
1290
1278
graph = self.make_breaking_graph(complex_shortcut,
1292
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1293
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1294
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1295
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1280
self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'i'])
1281
self.assertFindUniqueAncestors(graph, [b'e', b'g', b'i'], b'i', [b'h'])
1282
self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'g'])
1283
self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'j'])
1297
1285
def test_in_ancestry(self):
1298
1286
graph = self.make_graph(ancestry_1)
1299
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1300
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1287
self.assertFindUniqueAncestors(graph, [], b'rev1', [b'rev3'])
1288
self.assertFindUniqueAncestors(graph, [], b'rev2b', [b'rev4'])
1302
1290
def test_multiple_revisions(self):
1303
1291
graph = self.make_graph(ancestry_1)
1304
1292
self.assertFindUniqueAncestors(graph,
1305
['rev4'], 'rev4', ['rev3', 'rev2b'])
1293
[b'rev4'], b'rev4', [b'rev3', b'rev2b'])
1306
1294
self.assertFindUniqueAncestors(graph,
1307
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1295
[b'rev2a', b'rev3', b'rev4'], b'rev4', [b'rev2b'])
1309
1297
def test_complex_shortcut(self):
1310
1298
graph = self.make_graph(complex_shortcut)
1311
1299
self.assertFindUniqueAncestors(graph,
1312
['h', 'n'], 'n', ['m'])
1300
[b'h', b'n'], b'n', [b'm'])
1313
1301
self.assertFindUniqueAncestors(graph,
1314
['e', 'i', 'm'], 'm', ['n'])
1302
[b'e', b'i', b'm'], b'm', [b'n'])
1316
1304
def test_complex_shortcut2(self):
1317
1305
graph = self.make_graph(complex_shortcut2)
1318
1306
self.assertFindUniqueAncestors(graph,
1319
['j', 'u'], 'u', ['t'])
1307
[b'j', b'u'], b'u', [b't'])
1320
1308
self.assertFindUniqueAncestors(graph,
1309
[b't'], b't', [b'u'])
1323
1311
def test_multiple_interesting_unique(self):
1324
1312
graph = self.make_graph(multiple_interesting_unique)
1325
1313
self.assertFindUniqueAncestors(graph,
1326
['j', 'y'], 'y', ['z'])
1314
[b'j', b'y'], b'y', [b'z'])
1327
1315
self.assertFindUniqueAncestors(graph,
1328
['p', 'z'], 'z', ['y'])
1316
[b'p', b'z'], b'z', [b'y'])
1330
1318
def test_racing_shortcuts(self):
1331
1319
graph = self.make_graph(racing_shortcuts)
1332
1320
self.assertFindUniqueAncestors(graph,
1333
['p', 'q', 'z'], 'z', ['y'])
1321
[b'p', b'q', b'z'], b'z', [b'y'])
1334
1322
self.assertFindUniqueAncestors(graph,
1335
['h', 'i', 'j', 'y'], 'j', ['z'])
1323
[b'h', b'i', b'j', b'y'], b'j', [b'z'])
1338
1326
class TestGraphFindDistanceToNull(TestGraphBase):
1346
1334
def test_nothing_known(self):
1347
1335
graph = self.make_graph(ancestry_1)
1348
1336
self.assertFindDistance(0, graph, NULL_REVISION, [])
1349
self.assertFindDistance(1, graph, 'rev1', [])
1350
self.assertFindDistance(2, graph, 'rev2a', [])
1351
self.assertFindDistance(2, graph, 'rev2b', [])
1352
self.assertFindDistance(3, graph, 'rev3', [])
1353
self.assertFindDistance(4, graph, 'rev4', [])
1337
self.assertFindDistance(1, graph, b'rev1', [])
1338
self.assertFindDistance(2, graph, b'rev2a', [])
1339
self.assertFindDistance(2, graph, b'rev2b', [])
1340
self.assertFindDistance(3, graph, b'rev3', [])
1341
self.assertFindDistance(4, graph, b'rev4', [])
1355
1343
def test_rev_is_ghost(self):
1356
1344
graph = self.make_graph(ancestry_1)
1357
1345
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1358
graph.find_distance_to_null, 'rev_missing', [])
1359
self.assertEqual('rev_missing', e.revision_id)
1360
self.assertEqual('rev_missing', e.ghost_revision_id)
1346
graph.find_distance_to_null, b'rev_missing', [])
1347
self.assertEqual(b'rev_missing', e.revision_id)
1348
self.assertEqual(b'rev_missing', e.ghost_revision_id)
1362
1350
def test_ancestor_is_ghost(self):
1363
graph = self.make_graph({'rev':['parent']})
1351
graph = self.make_graph({b'rev': [b'parent']})
1364
1352
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1365
graph.find_distance_to_null, 'rev', [])
1366
self.assertEqual('rev', e.revision_id)
1367
self.assertEqual('parent', e.ghost_revision_id)
1353
graph.find_distance_to_null, b'rev', [])
1354
self.assertEqual(b'rev', e.revision_id)
1355
self.assertEqual(b'parent', e.ghost_revision_id)
1369
1357
def test_known_in_ancestry(self):
1370
1358
graph = self.make_graph(ancestry_1)
1371
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1372
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1359
self.assertFindDistance(2, graph, b'rev2a', [(b'rev1', 1)])
1360
self.assertFindDistance(3, graph, b'rev3', [(b'rev2a', 2)])
1374
1362
def test_known_in_ancestry_limits(self):
1375
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1376
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1363
graph = self.make_breaking_graph(ancestry_1, [b'rev1'])
1364
self.assertFindDistance(4, graph, b'rev4', [(b'rev3', 3)])
1378
1366
def test_target_is_ancestor(self):
1379
1367
graph = self.make_graph(ancestry_1)
1380
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1368
self.assertFindDistance(2, graph, b'rev2a', [(b'rev3', 3)])
1382
1370
def test_target_is_ancestor_limits(self):
1383
1371
"""We shouldn't search all history if we run into ourselves"""
1384
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1385
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1372
graph = self.make_breaking_graph(ancestry_1, [b'rev1'])
1373
self.assertFindDistance(3, graph, b'rev3', [(b'rev4', 4)])
1387
1375
def test_target_parallel_to_known_limits(self):
1388
1376
# Even though the known revision isn't part of the other ancestry, they
1389
1377
# eventually converge
1390
graph = self.make_breaking_graph(with_tail, ['a'])
1391
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1392
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1393
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1394
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1378
graph = self.make_breaking_graph(with_tail, [b'a'])
1379
self.assertFindDistance(6, graph, b'f', [(b'g', 6)])
1380
self.assertFindDistance(7, graph, b'h', [(b'g', 6)])
1381
self.assertFindDistance(8, graph, b'i', [(b'g', 6)])
1382
self.assertFindDistance(6, graph, b'g', [(b'i', 8)])
1397
1385
class TestFindMergeOrder(TestGraphBase):
1402
1390
def test_parents(self):
1403
1391
graph = self.make_graph(ancestry_1)
1404
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1406
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1392
self.assertMergeOrder([b'rev3', b'rev2b'], graph, b'rev4',
1393
[b'rev3', b'rev2b'])
1394
self.assertMergeOrder([b'rev3', b'rev2b'], graph, b'rev4',
1395
[b'rev2b', b'rev3'])
1409
1397
def test_ancestors(self):
1410
1398
graph = self.make_graph(ancestry_1)
1411
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1413
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1399
self.assertMergeOrder([b'rev1', b'rev2b'], graph, b'rev4',
1400
[b'rev1', b'rev2b'])
1401
self.assertMergeOrder([b'rev1', b'rev2b'], graph, b'rev4',
1402
[b'rev2b', b'rev1'])
1416
1404
def test_shortcut_one_ancestor(self):
1417
1405
# When we have enough info, we can stop searching
1418
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1406
graph = self.make_breaking_graph(ancestry_1, [b'rev3', b'rev2b', b'rev4'])
1419
1407
# Single ancestors shortcut right away
1420
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1408
self.assertMergeOrder([b'rev3'], graph, b'rev4', [b'rev3'])
1422
1410
def test_shortcut_after_one_ancestor(self):
1423
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1424
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1411
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'])
1415
class TestFindDescendants(TestGraphBase):
1417
def test_find_descendants_rev1_rev3(self):
1418
graph = self.make_graph(ancestry_1)
1419
descendants = graph.find_descendants(b'rev1', b'rev3')
1420
self.assertEqual({b'rev1', b'rev2a', b'rev3'}, descendants)
1422
def test_find_descendants_rev1_rev4(self):
1423
graph = self.make_graph(ancestry_1)
1424
descendants = graph.find_descendants(b'rev1', b'rev4')
1425
self.assertEqual({b'rev1', b'rev2a', b'rev2b', b'rev3', b'rev4'},
1428
def test_find_descendants_rev2a_rev4(self):
1429
graph = self.make_graph(ancestry_1)
1430
descendants = graph.find_descendants(b'rev2a', b'rev4')
1431
self.assertEqual({b'rev2a', b'rev3', b'rev4'}, descendants)
1433
class TestFindLefthandMerger(TestGraphBase):
1435
def check_merger(self, result, ancestry, merged, tip):
1436
graph = self.make_graph(ancestry)
1437
self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
1439
def test_find_lefthand_merger_rev2b(self):
1440
self.check_merger(b'rev4', ancestry_1, b'rev2b', b'rev4')
1442
def test_find_lefthand_merger_rev2a(self):
1443
self.check_merger(b'rev2a', ancestry_1, b'rev2a', b'rev4')
1445
def test_find_lefthand_merger_rev4(self):
1446
self.check_merger(None, ancestry_1, b'rev4', b'rev2a')
1448
def test_find_lefthand_merger_f(self):
1449
self.check_merger(b'i', complex_shortcut, b'f', b'm')
1451
def test_find_lefthand_merger_g(self):
1452
self.check_merger(b'i', complex_shortcut, b'g', b'm')
1454
def test_find_lefthand_merger_h(self):
1455
self.check_merger(b'n', complex_shortcut, b'h', b'n')
1458
class TestGetChildMap(TestGraphBase):
1460
def test_get_child_map(self):
1461
graph = self.make_graph(ancestry_1)
1462
child_map = graph.get_child_map([b'rev4', b'rev3', b'rev2a', b'rev2b'])
1463
self.assertEqual({b'rev1': [b'rev2a', b'rev2b'],
1464
b'rev2a': [b'rev3'],
1465
b'rev2b': [b'rev4'],
1466
b'rev3': [b'rev4']},
1427
1470
class TestCachingParentsProvider(tests.TestCase):
1435
1478
def setUp(self):
1436
1479
super(TestCachingParentsProvider, self).setUp()
1437
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1480
dict_pp = _mod_graph.DictParentsProvider({b'a': (b'b',)})
1438
1481
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1439
1482
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1441
1484
def test_get_parent_map(self):
1442
1485
"""Requesting the same revision should be returned from cache"""
1443
1486
self.assertEqual({}, self.caching_pp._cache)
1444
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1445
self.assertEqual(['a'], self.inst_pp.calls)
1446
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1487
self.assertEqual({b'a':(b'b',)}, self.caching_pp.get_parent_map([b'a']))
1488
self.assertEqual([b'a'], self.inst_pp.calls)
1489
self.assertEqual({b'a':(b'b',)}, self.caching_pp.get_parent_map([b'a']))
1447
1490
# No new call, as it should have been returned from the cache
1448
self.assertEqual(['a'], self.inst_pp.calls)
1449
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1491
self.assertEqual([b'a'], self.inst_pp.calls)
1492
self.assertEqual({b'a':(b'b',)}, self.caching_pp._cache)
1451
1494
def test_get_parent_map_not_present(self):
1452
1495
"""The cache should also track when a revision doesn't exist"""
1453
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1454
self.assertEqual(['b'], self.inst_pp.calls)
1455
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1496
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1497
self.assertEqual([b'b'], self.inst_pp.calls)
1498
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1457
self.assertEqual(['b'], self.inst_pp.calls)
1500
self.assertEqual([b'b'], self.inst_pp.calls)
1459
1502
def test_get_parent_map_mixed(self):
1460
1503
"""Anything that can be returned from cache, should be"""
1461
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1462
self.assertEqual(['b'], self.inst_pp.calls)
1463
self.assertEqual({'a':('b',)},
1464
self.caching_pp.get_parent_map(['a', 'b']))
1465
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1504
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1505
self.assertEqual([b'b'], self.inst_pp.calls)
1506
self.assertEqual({b'a':(b'b',)},
1507
self.caching_pp.get_parent_map([b'a', b'b']))
1508
self.assertEqual([b'b', b'a'], self.inst_pp.calls)
1467
1510
def test_get_parent_map_repeated(self):
1468
1511
"""Asking for the same parent 2x will only forward 1 request."""
1469
self.assertEqual({'a':('b',)},
1470
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1512
self.assertEqual({b'a':(b'b',)},
1513
self.caching_pp.get_parent_map([b'b', b'a', b'b']))
1471
1514
# Use sorted because we don't care about the order, just that each is
1472
1515
# only present 1 time.
1473
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1516
self.assertEqual([b'a', b'b'], sorted(self.inst_pp.calls))
1475
1518
def test_note_missing_key(self):
1476
1519
"""After noting that a key is missing it is cached."""
1477
self.caching_pp.note_missing_key('b')
1478
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1479
self.assertEqual([], self.inst_pp.calls)
1480
self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1520
self.caching_pp.note_missing_key(b'b')
1521
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1522
self.assertEqual([], self.inst_pp.calls)
1523
self.assertEqual({b'b'}, self.caching_pp.missing_keys)
1525
def test_get_cached_parent_map(self):
1526
self.assertEqual({}, self.caching_pp.get_cached_parent_map([b'a']))
1527
self.assertEqual([], self.inst_pp.calls)
1528
self.assertEqual({b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a']))
1529
self.assertEqual([b'a'], self.inst_pp.calls)
1530
self.assertEqual({b'a': (b'b',)},
1531
self.caching_pp.get_cached_parent_map([b'a']))
1483
1534
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1593
d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1594
('B',): [('A',)], ('A',): []}
1652
d = {(b'D',): [(b'B',), (b'C',)], (b'C',):[(b'A',)],
1653
(b'B',): [(b'A',)], (b'A',): []}
1595
1654
g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1596
1655
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1597
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
1598
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
1599
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1600
self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1603
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1604
"""Tests for bzrlib.graph.PendingAncestryResult."""
1606
def test_get_keys(self):
1607
builder = self.make_branch_builder('b')
1608
builder.start_series()
1609
builder.build_snapshot('rev-1', None, [
1610
('add', ('', 'root-id', 'directory', ''))])
1611
builder.build_snapshot('rev-2', ['rev-1'], [])
1612
builder.finish_series()
1613
repo = builder.get_branch().repository
1615
self.addCleanup(repo.unlock)
1616
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1617
self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1619
def test_get_keys_excludes_ghosts(self):
1620
builder = self.make_branch_builder('b')
1621
builder.start_series()
1622
builder.build_snapshot('rev-1', None, [
1623
('add', ('', 'root-id', 'directory', ''))])
1624
builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
1625
builder.finish_series()
1626
repo = builder.get_branch().repository
1628
self.addCleanup(repo.unlock)
1629
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1630
self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
1632
def test_get_keys_excludes_null(self):
1633
# Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1634
# somewhere other than the last element, which can happen in real
1636
class StubGraph(object):
1637
def iter_ancestry(self, keys):
1638
return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1639
result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1640
result_keys = result._get_keys(StubGraph())
1641
# Only the non-null keys from the ancestry appear.
1642
self.assertEqual(set(['foo']), set(result_keys))
1645
class TestPendingAncestryResultRefine(TestGraphBase):
1647
def test_refine(self):
1648
# Used when pulling from a stacked repository, so test some revisions
1649
# being satisfied from the stacking branch.
1650
g = self.make_graph(
1651
{"tip":["mid"], "mid":["base"], "tag":["base"],
1652
"base":[NULL_REVISION], NULL_REVISION:[]})
1653
result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1654
result = result.refine(set(['tip']), set(['mid']))
1655
self.assertEqual(set(['mid', 'tag']), result.heads)
1656
result = result.refine(set(['mid', 'tag', 'base']),
1657
set([NULL_REVISION]))
1658
self.assertEqual(set([NULL_REVISION]), result.heads)
1659
self.assertTrue(result.is_empty())
1662
class TestSearchResultRefine(TestGraphBase):
1664
def test_refine(self):
1665
# Used when pulling from a stacked repository, so test some revisions
1666
# being satisfied from the stacking branch.
1667
g = self.make_graph(
1668
{"tip":["mid"], "mid":["base"], "tag":["base"],
1669
"base":[NULL_REVISION], NULL_REVISION:[]})
1670
result = _mod_graph.SearchResult(set(['tip', 'tag']),
1671
set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1672
result = result.refine(set(['tip']), set(['mid']))
1673
recipe = result.get_recipe()
1674
# We should be starting from tag (original head) and mid (seen ref)
1675
self.assertEqual(set(['mid', 'tag']), recipe[1])
1676
# We should be stopping at NULL (original stop) and tip (seen head)
1677
self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1678
self.assertEqual(3, recipe[3])
1679
result = result.refine(set(['mid', 'tag', 'base']),
1680
set([NULL_REVISION]))
1681
recipe = result.get_recipe()
1682
# We should be starting from nothing (NULL was known as a cut point)
1683
self.assertEqual(set([]), recipe[1])
1684
# We should be stopping at NULL (original stop) and tip (seen head) and
1685
# tag (seen head) and mid(seen mid-point head). We could come back and
1686
# define this as not including mid, for minimal results, but it is
1687
# still 'correct' to include mid, and simpler/easier.
1688
self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1689
self.assertEqual(0, recipe[3])
1690
self.assertTrue(result.is_empty())
1656
self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'A'])))
1657
self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'B'])))
1658
self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'C'])))
1659
self.assertEqual([b'B', b'C'], sorted(graph_thunk.heads([b'B', b'C'])))
1661
def test_add_node(self):
1662
d = {(b'C',):[(b'A',)], (b'B',): [(b'A',)], (b'A',): []}
1663
g = _mod_graph.KnownGraph(d)
1664
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1665
graph_thunk.add_node(b"D", [b"A", b"C"])
1666
self.assertEqual([b'B', b'D'],
1667
sorted(graph_thunk.heads([b'D', b'B', b'A'])))
1669
def test_merge_sort(self):
1670
d = {(b'C',):[(b'A',)], (b'B',): [(b'A',)], (b'A',): []}
1671
g = _mod_graph.KnownGraph(d)
1672
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1673
graph_thunk.add_node(b"D", [b"A", b"C"])
1674
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')])
1679
class TestStackedParentsProvider(tests.TestCase):
1682
super(TestStackedParentsProvider, self).setUp()
1685
def get_shared_provider(self, info, ancestry, has_cached):
1686
pp = _mod_graph.DictParentsProvider(ancestry)
1688
pp.get_cached_parent_map = pp.get_parent_map
1689
return SharedInstrumentedParentsProvider(pp, self.calls, info)
1691
def test_stacked_parents_provider(self):
1692
parents1 = _mod_graph.DictParentsProvider({b'rev2': [b'rev3']})
1693
parents2 = _mod_graph.DictParentsProvider({b'rev1': [b'rev4']})
1694
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1695
self.assertEqual({b'rev1':[b'rev4'], b'rev2':[b'rev3']},
1696
stacked.get_parent_map([b'rev1', b'rev2']))
1697
self.assertEqual({b'rev2':[b'rev3'], b'rev1':[b'rev4']},
1698
stacked.get_parent_map([b'rev2', b'rev1']))
1699
self.assertEqual({b'rev2':[b'rev3']},
1700
stacked.get_parent_map([b'rev2', b'rev2']))
1701
self.assertEqual({b'rev1':[b'rev4']},
1702
stacked.get_parent_map([b'rev1', b'rev1']))
1704
def test_stacked_parents_provider_overlapping(self):
1705
# rev2 is availible in both providers.
1709
parents1 = _mod_graph.DictParentsProvider({b'rev2': [b'rev1']})
1710
parents2 = _mod_graph.DictParentsProvider({b'rev2': [b'rev1']})
1711
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1712
self.assertEqual({b'rev2': [b'rev1']},
1713
stacked.get_parent_map([b'rev2']))
1715
def test_handles_no_get_cached_parent_map(self):
1716
# this shows that we both handle when a provider doesn't implement
1717
# get_cached_parent_map
1718
pp1 = self.get_shared_provider(b'pp1', {b'rev2': (b'rev1',)},
1720
pp2 = self.get_shared_provider(b'pp2', {b'rev2': (b'rev1',)},
1722
stacked = _mod_graph.StackedParentsProvider([pp1, pp2])
1723
self.assertEqual({b'rev2': (b'rev1',)}, stacked.get_parent_map([b'rev2']))
1724
# No call on b'pp1' because it doesn't provide get_cached_parent_map
1725
self.assertEqual([(b'pp2', 'cached', [b'rev2'])], self.calls)
1727
def test_query_order(self):
1728
# We should call get_cached_parent_map on all providers before we call
1729
# get_parent_map. Further, we should track what entries we have found,
1730
# and not re-try them.
1731
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)
1734
stacked = _mod_graph.StackedParentsProvider([pp1, pp2, pp3])
1735
self.assertEqual({b'a': (), b'b': (b'a',), b'c': (b'b',)},
1736
stacked.get_parent_map([b'a', b'b', b'c', b'd']))
1737
self.assertEqual([(b'pp1', 'cached', [b'a', b'b', b'c', b'd']),
1738
# No call to pp2, because it doesn't have cached
1739
(b'pp3', 'cached', [b'b', b'c', b'd']),
1740
(b'pp1', [b'c', b'd']),
1741
(b'pp2', [b'c', b'd']),
added
removed
breezy/tests/test_graph.py
