620
651
graph = mainline_tree.branch.repository.get_graph(
621
652
feature_tree.branch.repository)
622
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
653
self.assertEqual(b'rev2b', graph.find_unique_lca(b'rev2a', b'rev3b'))
624
655
def test_graph_difference(self):
625
656
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'))
658
(set(), set()), graph.find_difference(b'rev1', b'rev1'))
659
self.assertEqual((set(), {b'rev1'}),
660
graph.find_difference(NULL_REVISION, b'rev1'))
661
self.assertEqual(({b'rev1'}, set()),
662
graph.find_difference(b'rev1', NULL_REVISION))
663
self.assertEqual(({b'rev2a', b'rev3'}, {b'rev2b'}),
664
graph.find_difference(b'rev3', b'rev2b'))
665
self.assertEqual(({b'rev4', b'rev3', b'rev2a'}, set()),
666
graph.find_difference(b'rev4', b'rev2b'))
636
668
def test_graph_difference_separate_ancestry(self):
637
669
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'))
670
self.assertEqual(({b'rev1a'}, {b'rev1b'}),
671
graph.find_difference(b'rev1a', b'rev1b'))
672
self.assertEqual(({b'rev1a', b'rev2a', b'rev3a', b'rev4a'},
674
graph.find_difference(b'rev4a', b'rev1b'))
644
676
def test_graph_difference_criss_cross(self):
645
677
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'))
678
self.assertEqual(({b'rev3a'}, {b'rev3b'}),
679
graph.find_difference(b'rev3a', b'rev3b'))
680
self.assertEqual((set([]), {b'rev3b', b'rev2b'}),
681
graph.find_difference(b'rev2a', b'rev3b'))
651
683
def test_graph_difference_extended_history(self):
652
684
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'))
685
self.assertEqual(({b'e'}, {b'f'}),
686
graph.find_difference(b'e', b'f'))
687
self.assertEqual(({b'f'}, {b'e'}),
688
graph.find_difference(b'f', b'e'))
658
690
def test_graph_difference_double_shortcut(self):
659
691
graph = self.make_graph(double_shortcut)
660
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
661
graph.find_difference('f', 'g'))
692
self.assertEqual(({b'd', b'f'}, {b'e', b'g'}),
693
graph.find_difference(b'f', b'g'))
663
695
def test_graph_difference_complex_shortcut(self):
664
696
graph = self.make_graph(complex_shortcut)
665
self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
666
graph.find_difference('m', 'n'))
697
self.assertEqual(({b'm', b'i', b'e'}, {b'n', b'h'}),
698
graph.find_difference(b'm', b'n'))
668
700
def test_graph_difference_complex_shortcut2(self):
669
701
graph = self.make_graph(complex_shortcut2)
670
self.assertEqual((set(['t']), set(['j', 'u'])),
671
graph.find_difference('t', 'u'))
702
self.assertEqual(({b't'}, {b'j', b'u'}),
703
graph.find_difference(b't', b'u'))
673
705
def test_graph_difference_shortcut_extra_root(self):
674
706
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']))
707
self.assertEqual(({b'e'}, {b'f', b'g'}),
708
graph.find_difference(b'e', b'f'))
717
710
def test_iter_topo_order(self):
718
711
graph = self.make_graph(ancestry_1)
719
args = ['rev2a', 'rev3', 'rev1']
712
args = [b'rev2a', b'rev3', b'rev1']
720
713
topo_args = list(graph.iter_topo_order(args))
721
714
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'))
715
self.assertTrue(topo_args.index(b'rev2a') > topo_args.index(b'rev1'))
716
self.assertTrue(topo_args.index(b'rev2a') < topo_args.index(b'rev3'))
725
718
def test_is_ancestor(self):
726
719
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'))
720
self.assertEqual(True, graph.is_ancestor(b'null:', b'null:'))
721
self.assertEqual(True, graph.is_ancestor(b'null:', b'rev1'))
722
self.assertEqual(False, graph.is_ancestor(b'rev1', b'null:'))
723
self.assertEqual(True, graph.is_ancestor(b'null:', b'rev4'))
724
self.assertEqual(False, graph.is_ancestor(b'rev4', b'null:'))
725
self.assertEqual(False, graph.is_ancestor(b'rev4', b'rev2b'))
726
self.assertEqual(True, graph.is_ancestor(b'rev2b', b'rev4'))
727
self.assertEqual(False, graph.is_ancestor(b'rev2b', b'rev3'))
728
self.assertEqual(False, graph.is_ancestor(b'rev3', b'rev2b'))
736
729
instrumented_provider = InstrumentedParentsProvider(graph)
737
730
instrumented_graph = _mod_graph.Graph(instrumented_provider)
738
instrumented_graph.is_ancestor('rev2a', 'rev2b')
739
self.assertTrue('null:' not in instrumented_provider.calls)
731
instrumented_graph.is_ancestor(b'rev2a', b'rev2b')
732
self.assertTrue(b'null:' not in instrumented_provider.calls)
741
734
def test_is_between(self):
742
735
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'))
736
self.assertEqual(True, graph.is_between(b'null:', b'null:', b'null:'))
737
self.assertEqual(True, graph.is_between(b'rev1', b'null:', b'rev1'))
738
self.assertEqual(True, graph.is_between(b'rev1', b'rev1', b'rev4'))
739
self.assertEqual(True, graph.is_between(b'rev4', b'rev1', b'rev4'))
740
self.assertEqual(True, graph.is_between(b'rev3', b'rev1', b'rev4'))
741
self.assertEqual(False, graph.is_between(b'rev4', b'rev1', b'rev3'))
742
self.assertEqual(False, graph.is_between(b'rev1', b'rev2a', b'rev4'))
743
self.assertEqual(False, graph.is_between(b'null:', b'rev1', b'rev4'))
752
745
def test_is_ancestor_boundary(self):
753
746
"""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']))
796
graph = self.make_graph({b'c': [b'b', b'd'], b'd': [b'e'], b'b': [b'a'],
797
b'a': [NULL_REVISION], b'e': [NULL_REVISION]})
798
self.assertEqual({b'c'}, graph.heads([b'a', b'c', b'e']))
807
800
def test_heads_null(self):
808
801
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:')))
802
self.assertEqual({b'null:'}, graph.heads([b'null:']))
803
self.assertEqual({b'rev1'}, graph.heads([b'null:', b'rev1']))
804
self.assertEqual({b'rev1'}, graph.heads([b'rev1', b'null:']))
805
self.assertEqual({b'rev1'}, graph.heads({b'rev1', b'null:'}))
806
self.assertEqual({b'rev1'}, graph.heads((b'rev1', b'null:')))
815
808
def test_heads_one(self):
816
809
# A single node will always be a head
817
810
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']))
811
self.assertEqual({b'null:'}, graph.heads([b'null:']))
812
self.assertEqual({b'rev1'}, graph.heads([b'rev1']))
813
self.assertEqual({b'rev2a'}, graph.heads([b'rev2a']))
814
self.assertEqual({b'rev2b'}, graph.heads([b'rev2b']))
815
self.assertEqual({b'rev3'}, graph.heads([b'rev3']))
816
self.assertEqual({b'rev4'}, graph.heads([b'rev4']))
825
818
def test_heads_single(self):
826
819
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']))
820
self.assertEqual({b'rev4'}, graph.heads([b'null:', b'rev4']))
821
self.assertEqual({b'rev2a'}, graph.heads([b'rev1', b'rev2a']))
822
self.assertEqual({b'rev2b'}, graph.heads([b'rev1', b'rev2b']))
823
self.assertEqual({b'rev3'}, graph.heads([b'rev1', b'rev3']))
824
self.assertEqual({b'rev4'}, graph.heads([b'rev1', b'rev4']))
825
self.assertEqual({b'rev4'}, graph.heads([b'rev2a', b'rev4']))
826
self.assertEqual({b'rev4'}, graph.heads([b'rev2b', b'rev4']))
827
self.assertEqual({b'rev4'}, graph.heads([b'rev3', b'rev4']))
836
829
def test_heads_two_heads(self):
837
830
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']))
831
self.assertEqual({b'rev2a', b'rev2b'},
832
graph.heads([b'rev2a', b'rev2b']))
833
self.assertEqual({b'rev3', b'rev2b'},
834
graph.heads([b'rev3', b'rev2b']))
843
836
def test_heads_criss_cross(self):
844
837
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']))
838
self.assertEqual({b'rev2a'},
839
graph.heads([b'rev2a', b'rev1']))
840
self.assertEqual({b'rev2b'},
841
graph.heads([b'rev2b', b'rev1']))
842
self.assertEqual({b'rev3a'},
843
graph.heads([b'rev3a', b'rev1']))
844
self.assertEqual({b'rev3b'},
845
graph.heads([b'rev3b', b'rev1']))
846
self.assertEqual({b'rev2a', b'rev2b'},
847
graph.heads([b'rev2a', b'rev2b']))
848
self.assertEqual({b'rev3a'},
849
graph.heads([b'rev3a', b'rev2a']))
850
self.assertEqual({b'rev3a'},
851
graph.heads([b'rev3a', b'rev2b']))
852
self.assertEqual({b'rev3a'},
853
graph.heads([b'rev3a', b'rev2a', b'rev2b']))
854
self.assertEqual({b'rev3b'},
855
graph.heads([b'rev3b', b'rev2a']))
856
self.assertEqual({b'rev3b'},
857
graph.heads([b'rev3b', b'rev2b']))
858
self.assertEqual({b'rev3b'},
859
graph.heads([b'rev3b', b'rev2a', b'rev2b']))
860
self.assertEqual({b'rev3a', b'rev3b'},
861
graph.heads([b'rev3a', b'rev3b']))
862
self.assertEqual({b'rev3a', b'rev3b'},
863
graph.heads([b'rev3a', b'rev3b', b'rev2a', b'rev2b']))
872
865
def test_heads_shortcut(self):
873
866
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']))
868
self.assertEqual({b'rev2a', b'rev2b', b'rev2c'},
869
graph.heads([b'rev2a', b'rev2b', b'rev2c']))
870
self.assertEqual({b'rev3a', b'rev3b'},
871
graph.heads([b'rev3a', b'rev3b']))
872
self.assertEqual({b'rev3a', b'rev3b'},
873
graph.heads([b'rev2a', b'rev3a', b'rev3b']))
874
self.assertEqual({b'rev2a', b'rev3b'},
875
graph.heads([b'rev2a', b'rev3b']))
876
self.assertEqual({b'rev2c', b'rev3a'},
877
graph.heads([b'rev2c', b'rev3a']))
886
879
def _run_heads_break_deeper(self, graph_dict, search):
887
880
"""Run heads on a graph-as-a-dict.
889
If the search asks for the parents of 'deeper' the test will fail.
882
If the search asks for the parents of b'deeper' the test will fail.
891
884
class stub(object):
893
887
def get_parent_map(keys):
897
891
self.fail('key deeper was accessed')
898
892
result[key] = graph_dict[key]
905
899
def test_heads_limits_search(self):
906
900
# test that a heads query does not search all of history
902
b'left': [b'common'],
903
b'right': [b'common'],
904
b'common': [b'deeper'],
912
self.assertEqual(set(['left', 'right']),
913
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
906
self.assertEqual({b'left', b'right'},
907
self._run_heads_break_deeper(graph_dict, [b'left', b'right']))
915
909
def test_heads_limits_search_assymetric(self):
916
910
# test that a heads query does not search all of history
919
'midleft':['common'],
921
'common':['aftercommon'],
922
'aftercommon':['deeper'],
912
b'left': [b'midleft'],
913
b'midleft': [b'common'],
914
b'right': [b'common'],
915
b'common': [b'aftercommon'],
916
b'aftercommon': [b'deeper'],
924
self.assertEqual(set(['left', 'right']),
925
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
918
self.assertEqual({b'left', b'right'},
919
self._run_heads_break_deeper(graph_dict, [b'left', b'right']))
927
921
def test_heads_limits_search_common_search_must_continue(self):
928
922
# test that common nodes are still queried, preventing
929
923
# all-the-way-to-origin behaviour in the following graph:
931
'h1':['shortcut', 'common1'],
933
'shortcut':['common2'],
934
'common1':['common2'],
935
'common2':['deeper'],
925
b'h1': [b'shortcut', b'common1'],
927
b'shortcut': [b'common2'],
928
b'common1': [b'common2'],
929
b'common2': [b'deeper'],
937
self.assertEqual(set(['h1', 'h2']),
938
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
931
self.assertEqual({b'h1', b'h2'},
932
self._run_heads_break_deeper(graph_dict, [b'h1', b'h2']))
940
934
def test_breadth_first_search_start_ghosts(self):
941
935
graph = self.make_graph({})
942
936
# 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())
937
search = graph._make_breadth_first_searcher([b'a-ghost'])
938
self.assertEqual((set(), {b'a-ghost'}), search.next_with_ghosts())
945
939
self.assertRaises(StopIteration, search.next_with_ghosts)
946
940
# 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)
941
search = graph._make_breadth_first_searcher([b'a-ghost'])
942
self.assertEqual({b'a-ghost'}, next(search))
943
self.assertRaises(StopIteration, next, search)
951
945
def test_breadth_first_search_deep_ghosts(self):
952
946
graph = self.make_graph({
954
'present':['child', 'ghost'],
947
b'head': [b'present'],
948
b'present': [b'child', b'ghost'],
957
951
# 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'])),
962
search.next_with_ghosts())
952
search = graph._make_breadth_first_searcher([b'head'])
953
self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
954
self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
955
self.assertEqual(({b'child'}, {b'ghost'}),
956
search.next_with_ghosts())
963
957
self.assertRaises(StopIteration, search.next_with_ghosts)
964
958
# 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)
959
search = graph._make_breadth_first_searcher([b'head'])
960
self.assertEqual({b'head'}, next(search))
961
self.assertEqual({b'present'}, next(search))
962
self.assertEqual({b'child', b'ghost'},
964
self.assertRaises(StopIteration, next, search)
972
966
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
973
967
# To make the API robust, we allow calling both next() and
974
968
# next_with_ghosts() on the same searcher.
975
969
graph = self.make_graph({
977
'present':['child', 'ghost'],
970
b'head': [b'present'],
971
b'present': [b'child', b'ghost'],
980
974
# 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'])),
985
search.next_with_ghosts())
986
self.assertRaises(StopIteration, search.next)
975
search = graph._make_breadth_first_searcher([b'head'])
976
self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
977
self.assertEqual({b'present'}, next(search))
978
self.assertEqual(({b'child'}, {b'ghost'}),
979
search.next_with_ghosts())
980
self.assertRaises(StopIteration, next, search)
987
981
# 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']),
982
search = graph._make_breadth_first_searcher([b'head'])
983
self.assertEqual({b'head'}, next(search))
984
self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
985
self.assertEqual({b'child', b'ghost'},
993
987
self.assertRaises(StopIteration, search.next_with_ghosts)
995
989
def test_breadth_first_change_search(self):
996
990
# Changing the search should work with both next and next_with_ghosts.
997
991
graph = self.make_graph({
999
'present':['stopped'],
1000
'other':['other_2'],
992
b'head': [b'present'],
993
b'present': [b'stopped'],
994
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())
997
search = graph._make_breadth_first_searcher([b'head'])
998
self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
999
self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
1000
self.assertEqual({b'present'},
1001
search.stop_searching_any([b'present']))
1002
self.assertEqual(({b'other'}, {b'other_ghost'}),
1003
search.start_searching([b'other', b'other_ghost']))
1004
self.assertEqual(({b'other_2'}, set()), search.next_with_ghosts())
1011
1005
self.assertRaises(StopIteration, search.next_with_ghosts)
1012
1006
# 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)
1007
search = graph._make_breadth_first_searcher([b'head'])
1008
self.assertEqual({b'head'}, next(search))
1009
self.assertEqual({b'present'}, next(search))
1010
self.assertEqual({b'present'},
1011
search.stop_searching_any([b'present']))
1012
search.start_searching([b'other', b'other_ghost'])
1013
self.assertEqual({b'other_2'}, next(search))
1014
self.assertRaises(StopIteration, next, search)
1022
1016
def assertSeenAndResult(self, instructions, search, next):
1023
1017
"""Check the results of .seen and get_result() for a seach.
1040
1034
search.start_searching(starts)
1041
1035
if stops is not None:
1042
1036
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())
1037
state = search.get_state()
1038
self.assertEqual(set(included_keys), state[2])
1046
1039
self.assertEqual(seen, search.seen)
1048
1041
def test_breadth_first_get_result_excludes_current_pending(self):
1049
1042
graph = self.make_graph({
1051
'child':[NULL_REVISION],
1043
b'head': [b'child'],
1044
b'child': [NULL_REVISION],
1054
search = graph._make_breadth_first_searcher(['head'])
1047
search = graph._make_breadth_first_searcher([b'head'])
1055
1048
# 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())
1049
state = search.get_state()
1050
self.assertEqual(({b'head'}, {b'head'}, set()),
1060
1052
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),
1055
({b'head'}, ({b'head'}, {b'child'}, 1),
1056
[b'head'], None, None),
1057
({b'head', b'child'}, ({b'head'}, {NULL_REVISION}, 2),
1058
[b'head', b'child'], None, None),
1059
({b'head', b'child', NULL_REVISION}, ({b'head'}, set(), 3),
1060
[b'head', b'child', NULL_REVISION], None, None),
1070
self.assertSeenAndResult(expected, search, search.next)
1062
self.assertSeenAndResult(expected, search, search.__next__)
1071
1063
# using next_with_ghosts:
1072
search = graph._make_breadth_first_searcher(['head'])
1064
search = graph._make_breadth_first_searcher([b'head'])
1073
1065
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1075
1067
def test_breadth_first_get_result_starts_stops(self):
1076
1068
graph = self.make_graph({
1078
'child':[NULL_REVISION],
1079
'otherhead':['otherchild'],
1080
'otherchild':['excluded'],
1081
'excluded':[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],
1084
1076
search = graph._make_breadth_first_searcher([])
1085
1077
# Starting with nothing and adding a search works:
1086
search.start_searching(['head'])
1078
search.start_searching([b'head'])
1087
1079
# 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)
1080
state = search.get_state()
1081
self.assertEqual(({b'head'}, {b'child'}, {b'head'}),
1083
self.assertEqual({b'head'}, search.seen)
1095
1086
# stop at child, and start a new search at otherhead:
1096
1087
# - 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),
1089
({b'head', b'child', b'otherhead'},
1090
({b'head', b'otherhead'}, {b'child', b'otherchild'}, 2),
1091
[b'head', b'otherhead'], [b'otherhead'], [b'child']),
1092
({b'head', b'child', b'otherhead', b'otherchild'},
1093
({b'head', b'otherhead'}, {b'child', b'excluded'}, 3),
1094
[b'head', b'otherhead', b'otherchild'], None, None),
1104
1095
# 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']),
1096
({b'head', b'child', b'otherhead', b'otherchild', b'excluded'},
1097
({b'head', b'otherhead'}, {b'child', b'excluded'}, 3),
1098
[b'head', b'otherhead', b'otherchild'], None, [b'excluded']),
1109
self.assertSeenAndResult(expected, search, search.next)
1100
self.assertSeenAndResult(expected, search, search.__next__)
1110
1101
# using next_with_ghosts:
1111
1102
search = graph._make_breadth_first_searcher([])
1112
search.start_searching(['head'])
1103
search.start_searching([b'head'])
1113
1104
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1115
1106
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
1107
# A client should be able to say b'stop node X' even if X has not been
1117
1108
# returned to the client.
1118
1109
graph = self.make_graph({
1119
'head':['child', 'ghost1'],
1120
'child':[NULL_REVISION],
1110
b'head': [b'child', b'ghost1'],
1111
b'child': [NULL_REVISION],
1123
search = graph._make_breadth_first_searcher(['head'])
1114
search = graph._make_breadth_first_searcher([b'head'])
1125
1116
# NULL_REVISION and ghost1 have not been returned
1127
(set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1128
['head'], None, [NULL_REVISION, 'ghost1']),
1118
({b'head'}, {b'child', NULL_REVISION, b'ghost1'}, 1),
1119
[b'head'], None, [NULL_REVISION, b'ghost1']),
1129
1120
# ghost1 has been returned, NULL_REVISION is to be returned in the
1130
1121
# next iteration.
1131
(set(['head', 'child', 'ghost1']),
1132
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1133
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1122
({b'head', b'child', b'ghost1'},
1123
({b'head'}, {b'ghost1', NULL_REVISION}, 2),
1124
[b'head', b'child'], None, [NULL_REVISION, b'ghost1']),
1135
self.assertSeenAndResult(expected, search, search.next)
1126
self.assertSeenAndResult(expected, search, search.__next__)
1136
1127
# using next_with_ghosts:
1137
search = graph._make_breadth_first_searcher(['head'])
1128
search = graph._make_breadth_first_searcher([b'head'])
1138
1129
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1140
1131
def test_breadth_first_stop_searching_late(self):
1141
# A client should be able to say 'stop node X' and have it excluded
1132
# A client should be able to say b'stop node X' and have it excluded
1142
1133
# from the result even if X was seen in an older iteration of the
1144
1135
graph = self.make_graph({
1147
'child':[NULL_REVISION],
1136
b'head': [b'middle'],
1137
b'middle': [b'child'],
1138
b'child': [NULL_REVISION],
1150
search = graph._make_breadth_first_searcher(['head'])
1141
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
1143
({b'head'}, ({b'head'}, {b'middle'}, 1),
1144
[b'head'], None, None),
1145
({b'head', b'middle'}, ({b'head'}, {b'child'}, 2),
1146
[b'head', b'middle'], None, None),
1147
# b'middle' came from the previous iteration, but we don't stop
1157
1148
# searching it until *after* advancing the searcher.
1158
(set(['head', 'middle', 'child']),
1159
(set(['head']), set(['middle', 'child']), 1),
1160
['head'], None, ['middle', 'child']),
1149
({b'head', b'middle', b'child'},
1150
({b'head'}, {b'middle', b'child'}, 1),
1151
[b'head'], None, [b'middle', b'child']),
1162
self.assertSeenAndResult(expected, search, search.next)
1153
self.assertSeenAndResult(expected, search, search.__next__)
1163
1154
# using next_with_ghosts:
1164
search = graph._make_breadth_first_searcher(['head'])
1155
search = graph._make_breadth_first_searcher([b'head'])
1165
1156
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1167
1158
def test_breadth_first_get_result_ghosts_are_excluded(self):
1168
1159
graph = self.make_graph({
1169
'head':['child', 'ghost'],
1170
'child':[NULL_REVISION],
1160
b'head': [b'child', b'ghost'],
1161
b'child': [NULL_REVISION],
1173
search = graph._make_breadth_first_searcher(['head'])
1164
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),
1168
({b'head'}, {b'ghost', b'child'}, 1),
1169
[b'head'], None, None),
1170
({b'head', b'child', b'ghost'},
1171
({b'head'}, {NULL_REVISION, b'ghost'}, 2),
1172
[b'head', b'child'], None, None),
1183
self.assertSeenAndResult(expected, search, search.next)
1174
self.assertSeenAndResult(expected, search, search.__next__)
1184
1175
# using next_with_ghosts:
1185
search = graph._make_breadth_first_searcher(['head'])
1176
search = graph._make_breadth_first_searcher([b'head'])
1186
1177
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1188
1179
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1189
1180
graph = self.make_graph({
1191
'child':[NULL_REVISION],
1181
b'head': [b'child'],
1182
b'child': [NULL_REVISION],
1194
search = graph._make_breadth_first_searcher(['head'])
1185
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),
1188
({b'head', b'ghost'},
1189
({b'head', b'ghost'}, {b'child', b'ghost'}, 1),
1190
[b'head'], [b'ghost'], None),
1191
({b'head', b'child', b'ghost'},
1192
({b'head', b'ghost'}, {NULL_REVISION, b'ghost'}, 2),
1193
[b'head', b'child'], None, None),
1204
self.assertSeenAndResult(expected, search, search.next)
1195
self.assertSeenAndResult(expected, search, search.__next__)
1205
1196
# using next_with_ghosts:
1206
search = graph._make_breadth_first_searcher(['head'])
1197
search = graph._make_breadth_first_searcher([b'head'])
1207
1198
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1209
1200
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1210
1201
graph = self.make_graph({
1211
'head':[NULL_REVISION],
1202
b'head': [NULL_REVISION],
1214
search = graph._make_breadth_first_searcher(['head'])
1205
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),
1209
({b'head'}, {NULL_REVISION}, 1),
1210
[b'head'], None, None),
1211
({b'head', NULL_REVISION},
1212
({b'head'}, set([]), 2),
1213
[b'head', NULL_REVISION], None, None),
1224
self.assertSeenAndResult(expected, search, search.next)
1215
self.assertSeenAndResult(expected, search, search.__next__)
1225
1216
# using next_with_ghosts:
1226
search = graph._make_breadth_first_searcher(['head'])
1217
search = graph._make_breadth_first_searcher([b'head'])
1227
1218
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1229
1220
def test_breadth_first_search_get_result_after_StopIteration(self):
1230
1221
# StopIteration should not invalid anything..
1231
1222
graph = self.make_graph({
1232
'head':[NULL_REVISION],
1223
b'head': [NULL_REVISION],
1235
search = graph._make_breadth_first_searcher(['head'])
1226
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),
1230
({b'head'}, {NULL_REVISION}, 1),
1231
[b'head'], None, None),
1232
({b'head', b'ghost', NULL_REVISION},
1233
({b'head', b'ghost'}, {b'ghost'}, 2),
1234
[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())
1236
self.assertSeenAndResult(expected, search, search.__next__)
1237
self.assertRaises(StopIteration, next, search)
1238
self.assertEqual({b'head', b'ghost', NULL_REVISION}, search.seen)
1239
state = search.get_state()
1241
({b'ghost', b'head'}, {b'ghost'},
1242
{b'head', NULL_REVISION}),
1252
1244
# using next_with_ghosts:
1253
search = graph._make_breadth_first_searcher(['head'])
1245
search = graph._make_breadth_first_searcher([b'head'])
1254
1246
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())
1247
self.assertRaises(StopIteration, next, search)
1248
self.assertEqual({b'head', b'ghost', NULL_REVISION}, search.seen)
1249
state = search.get_state()
1251
({b'ghost', b'head'}, {b'ghost'},
1252
{b'head', NULL_REVISION}),
1263
1256
class TestFindUniqueAncestors(TestGraphBase):
1269
1262
def test_empty_set(self):
1270
1263
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'])
1264
self.assertFindUniqueAncestors(graph, [], b'rev1', [b'rev1'])
1265
self.assertFindUniqueAncestors(graph, [], b'rev2b', [b'rev2b'])
1266
self.assertFindUniqueAncestors(graph, [], b'rev3', [b'rev1', b'rev3'])
1275
1268
def test_single_node(self):
1276
1269
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'])
1270
self.assertFindUniqueAncestors(graph, [b'rev2a'], b'rev2a', [b'rev1'])
1271
self.assertFindUniqueAncestors(graph, [b'rev2b'], b'rev2b', [b'rev1'])
1272
self.assertFindUniqueAncestors(graph, [b'rev3'], b'rev3', [b'rev2a'])
1281
1274
def test_minimal_ancestry(self):
1282
1275
graph = self.make_breaking_graph(extended_history_shortcut,
1283
[NULL_REVISION, 'a', 'b'])
1284
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1276
[NULL_REVISION, b'a', b'b'])
1277
self.assertFindUniqueAncestors(graph, [b'e'], b'e', [b'd'])
1286
1279
graph = self.make_breaking_graph(extended_history_shortcut,
1288
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1281
self.assertFindUniqueAncestors(graph, [b'f'], b'f', [b'a', b'd'])
1290
1283
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'])
1285
self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'i'])
1286
self.assertFindUniqueAncestors(graph, [b'e', b'g', b'i'], b'i', [b'h'])
1287
self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'g'])
1288
self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'j'])
1297
1290
def test_in_ancestry(self):
1298
1291
graph = self.make_graph(ancestry_1)
1299
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1300
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1292
self.assertFindUniqueAncestors(graph, [], b'rev1', [b'rev3'])
1293
self.assertFindUniqueAncestors(graph, [], b'rev2b', [b'rev4'])
1302
1295
def test_multiple_revisions(self):
1303
1296
graph = self.make_graph(ancestry_1)
1304
1297
self.assertFindUniqueAncestors(graph,
1305
['rev4'], 'rev4', ['rev3', 'rev2b'])
1298
[b'rev4'], b'rev4', [b'rev3', b'rev2b'])
1306
1299
self.assertFindUniqueAncestors(graph,
1307
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1300
[b'rev2a', b'rev3', b'rev4'], b'rev4', [b'rev2b'])
1309
1302
def test_complex_shortcut(self):
1310
1303
graph = self.make_graph(complex_shortcut)
1311
1304
self.assertFindUniqueAncestors(graph,
1312
['h', 'n'], 'n', ['m'])
1305
[b'h', b'n'], b'n', [b'm'])
1313
1306
self.assertFindUniqueAncestors(graph,
1314
['e', 'i', 'm'], 'm', ['n'])
1307
[b'e', b'i', b'm'], b'm', [b'n'])
1316
1309
def test_complex_shortcut2(self):
1317
1310
graph = self.make_graph(complex_shortcut2)
1318
1311
self.assertFindUniqueAncestors(graph,
1319
['j', 'u'], 'u', ['t'])
1312
[b'j', b'u'], b'u', [b't'])
1320
1313
self.assertFindUniqueAncestors(graph,
1314
[b't'], b't', [b'u'])
1323
1316
def test_multiple_interesting_unique(self):
1324
1317
graph = self.make_graph(multiple_interesting_unique)
1325
1318
self.assertFindUniqueAncestors(graph,
1326
['j', 'y'], 'y', ['z'])
1319
[b'j', b'y'], b'y', [b'z'])
1327
1320
self.assertFindUniqueAncestors(graph,
1328
['p', 'z'], 'z', ['y'])
1321
[b'p', b'z'], b'z', [b'y'])
1330
1323
def test_racing_shortcuts(self):
1331
1324
graph = self.make_graph(racing_shortcuts)
1332
1325
self.assertFindUniqueAncestors(graph,
1333
['p', 'q', 'z'], 'z', ['y'])
1326
[b'p', b'q', b'z'], b'z', [b'y'])
1334
1327
self.assertFindUniqueAncestors(graph,
1335
['h', 'i', 'j', 'y'], 'j', ['z'])
1328
[b'h', b'i', b'j', b'y'], b'j', [b'z'])
1338
1331
class TestGraphFindDistanceToNull(TestGraphBase):
1346
1339
def test_nothing_known(self):
1347
1340
graph = self.make_graph(ancestry_1)
1348
1341
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', [])
1342
self.assertFindDistance(1, graph, b'rev1', [])
1343
self.assertFindDistance(2, graph, b'rev2a', [])
1344
self.assertFindDistance(2, graph, b'rev2b', [])
1345
self.assertFindDistance(3, graph, b'rev3', [])
1346
self.assertFindDistance(4, graph, b'rev4', [])
1355
1348
def test_rev_is_ghost(self):
1356
1349
graph = self.make_graph(ancestry_1)
1357
1350
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)
1351
graph.find_distance_to_null, b'rev_missing', [])
1352
self.assertEqual(b'rev_missing', e.revision_id)
1353
self.assertEqual(b'rev_missing', e.ghost_revision_id)
1362
1355
def test_ancestor_is_ghost(self):
1363
graph = self.make_graph({'rev':['parent']})
1356
graph = self.make_graph({b'rev': [b'parent']})
1364
1357
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)
1358
graph.find_distance_to_null, b'rev', [])
1359
self.assertEqual(b'rev', e.revision_id)
1360
self.assertEqual(b'parent', e.ghost_revision_id)
1369
1362
def test_known_in_ancestry(self):
1370
1363
graph = self.make_graph(ancestry_1)
1371
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1372
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1364
self.assertFindDistance(2, graph, b'rev2a', [(b'rev1', 1)])
1365
self.assertFindDistance(3, graph, b'rev3', [(b'rev2a', 2)])
1374
1367
def test_known_in_ancestry_limits(self):
1375
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1376
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1368
graph = self.make_breaking_graph(ancestry_1, [b'rev1'])
1369
self.assertFindDistance(4, graph, b'rev4', [(b'rev3', 3)])
1378
1371
def test_target_is_ancestor(self):
1379
1372
graph = self.make_graph(ancestry_1)
1380
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1373
self.assertFindDistance(2, graph, b'rev2a', [(b'rev3', 3)])
1382
1375
def test_target_is_ancestor_limits(self):
1383
1376
"""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)])
1377
graph = self.make_breaking_graph(ancestry_1, [b'rev1'])
1378
self.assertFindDistance(3, graph, b'rev3', [(b'rev4', 4)])
1387
1380
def test_target_parallel_to_known_limits(self):
1388
1381
# Even though the known revision isn't part of the other ancestry, they
1389
1382
# 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)])
1383
graph = self.make_breaking_graph(with_tail, [b'a'])
1384
self.assertFindDistance(6, graph, b'f', [(b'g', 6)])
1385
self.assertFindDistance(7, graph, b'h', [(b'g', 6)])
1386
self.assertFindDistance(8, graph, b'i', [(b'g', 6)])
1387
self.assertFindDistance(6, graph, b'g', [(b'i', 8)])
1397
1390
class TestFindMergeOrder(TestGraphBase):
1402
1395
def test_parents(self):
1403
1396
graph = self.make_graph(ancestry_1)
1404
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1406
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1397
self.assertMergeOrder([b'rev3', b'rev2b'], graph, b'rev4',
1398
[b'rev3', b'rev2b'])
1399
self.assertMergeOrder([b'rev3', b'rev2b'], graph, b'rev4',
1400
[b'rev2b', b'rev3'])
1409
1402
def test_ancestors(self):
1410
1403
graph = self.make_graph(ancestry_1)
1411
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1413
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1404
self.assertMergeOrder([b'rev1', b'rev2b'], graph, b'rev4',
1405
[b'rev1', b'rev2b'])
1406
self.assertMergeOrder([b'rev1', b'rev2b'], graph, b'rev4',
1407
[b'rev2b', b'rev1'])
1416
1409
def test_shortcut_one_ancestor(self):
1417
1410
# When we have enough info, we can stop searching
1418
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1411
graph = self.make_breaking_graph(
1412
ancestry_1, [b'rev3', b'rev2b', b'rev4'])
1419
1413
# Single ancestors shortcut right away
1420
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1414
self.assertMergeOrder([b'rev3'], graph, b'rev4', [b'rev3'])
1422
1416
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'])
1417
graph = self.make_breaking_graph(ancestry_1, [b'rev2a', b'rev2b'])
1418
self.assertMergeOrder([b'rev3', b'rev1'], graph,
1419
b'rev4', [b'rev1', b'rev3'])
1422
class TestFindDescendants(TestGraphBase):
1424
def test_find_descendants_rev1_rev3(self):
1425
graph = self.make_graph(ancestry_1)
1426
descendants = graph.find_descendants(b'rev1', b'rev3')
1427
self.assertEqual({b'rev1', b'rev2a', b'rev3'}, descendants)
1429
def test_find_descendants_rev1_rev4(self):
1430
graph = self.make_graph(ancestry_1)
1431
descendants = graph.find_descendants(b'rev1', b'rev4')
1432
self.assertEqual({b'rev1', b'rev2a', b'rev2b', b'rev3', b'rev4'},
1435
def test_find_descendants_rev2a_rev4(self):
1436
graph = self.make_graph(ancestry_1)
1437
descendants = graph.find_descendants(b'rev2a', b'rev4')
1438
self.assertEqual({b'rev2a', b'rev3', b'rev4'}, descendants)
1441
class TestFindLefthandMerger(TestGraphBase):
1443
def check_merger(self, result, ancestry, merged, tip):
1444
graph = self.make_graph(ancestry)
1445
self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
1447
def test_find_lefthand_merger_rev2b(self):
1448
self.check_merger(b'rev4', ancestry_1, b'rev2b', b'rev4')
1450
def test_find_lefthand_merger_rev2a(self):
1451
self.check_merger(b'rev2a', ancestry_1, b'rev2a', b'rev4')
1453
def test_find_lefthand_merger_rev4(self):
1454
self.check_merger(None, ancestry_1, b'rev4', b'rev2a')
1456
def test_find_lefthand_merger_f(self):
1457
self.check_merger(b'i', complex_shortcut, b'f', b'm')
1459
def test_find_lefthand_merger_g(self):
1460
self.check_merger(b'i', complex_shortcut, b'g', b'm')
1462
def test_find_lefthand_merger_h(self):
1463
self.check_merger(b'n', complex_shortcut, b'h', b'n')
1466
class TestGetChildMap(TestGraphBase):
1468
def test_get_child_map(self):
1469
graph = self.make_graph(ancestry_1)
1470
child_map = graph.get_child_map([b'rev4', b'rev3', b'rev2a', b'rev2b'])
1471
self.assertEqual({b'rev1': [b'rev2a', b'rev2b'],
1472
b'rev2a': [b'rev3'],
1473
b'rev2b': [b'rev4'],
1474
b'rev3': [b'rev4']},
1427
1478
class TestCachingParentsProvider(tests.TestCase):
1435
1486
def setUp(self):
1436
1487
super(TestCachingParentsProvider, self).setUp()
1437
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1488
dict_pp = _mod_graph.DictParentsProvider({b'a': (b'b',)})
1438
1489
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1439
1490
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1441
1492
def test_get_parent_map(self):
1442
1493
"""Requesting the same revision should be returned from cache"""
1443
1494
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']))
1496
{b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a']))
1497
self.assertEqual([b'a'], self.inst_pp.calls)
1499
{b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a']))
1447
1500
# 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)
1501
self.assertEqual([b'a'], self.inst_pp.calls)
1502
self.assertEqual({b'a': (b'b',)}, self.caching_pp._cache)
1451
1504
def test_get_parent_map_not_present(self):
1452
1505
"""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']))
1506
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1507
self.assertEqual([b'b'], self.inst_pp.calls)
1508
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1457
self.assertEqual(['b'], self.inst_pp.calls)
1510
self.assertEqual([b'b'], self.inst_pp.calls)
1459
1512
def test_get_parent_map_mixed(self):
1460
1513
"""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)
1514
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1515
self.assertEqual([b'b'], self.inst_pp.calls)
1516
self.assertEqual({b'a': (b'b',)},
1517
self.caching_pp.get_parent_map([b'a', b'b']))
1518
self.assertEqual([b'b', b'a'], self.inst_pp.calls)
1467
1520
def test_get_parent_map_repeated(self):
1468
1521
"""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']))
1522
self.assertEqual({b'a': (b'b',)},
1523
self.caching_pp.get_parent_map([b'b', b'a', b'b']))
1471
1524
# Use sorted because we don't care about the order, just that each is
1472
1525
# only present 1 time.
1473
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1526
self.assertEqual([b'a', b'b'], sorted(self.inst_pp.calls))
1475
1528
def test_note_missing_key(self):
1476
1529
"""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)
1530
self.caching_pp.note_missing_key(b'b')
1531
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1532
self.assertEqual([], self.inst_pp.calls)
1533
self.assertEqual({b'b'}, self.caching_pp.missing_keys)
1535
def test_get_cached_parent_map(self):
1536
self.assertEqual({}, self.caching_pp.get_cached_parent_map([b'a']))
1537
self.assertEqual([], self.inst_pp.calls)
1539
{b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a']))
1540
self.assertEqual([b'a'], self.inst_pp.calls)
1541
self.assertEqual({b'a': (b'b',)},
1542
self.caching_pp.get_cached_parent_map([b'a']))
1483
1545
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1593
d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1594
('B',): [('A',)], ('A',): []}
1663
d = {(b'D',): [(b'B',), (b'C',)], (b'C',): [(b'A',)],
1664
(b'B',): [(b'A',)], (b'A',): []}
1595
1665
g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1596
1666
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())
1667
self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'A'])))
1668
self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'B'])))
1669
self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'C'])))
1670
self.assertEqual([b'B', b'C'], sorted(graph_thunk.heads([b'B', b'C'])))
1672
def test_add_node(self):
1673
d = {(b'C',): [(b'A',)], (b'B',): [(b'A',)], (b'A',): []}
1674
g = _mod_graph.KnownGraph(d)
1675
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1676
graph_thunk.add_node(b"D", [b"A", b"C"])
1677
self.assertEqual([b'B', b'D'],
1678
sorted(graph_thunk.heads([b'D', b'B', b'A'])))
1680
def test_merge_sort(self):
1681
d = {(b'C',): [(b'A',)], (b'B',): [(b'A',)], (b'A',): []}
1682
g = _mod_graph.KnownGraph(d)
1683
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1684
graph_thunk.add_node(b"D", [b"A", b"C"])
1685
self.assertEqual([(b'C', 0, (2,), False), (b'A', 0, (1,), True)],
1686
[(n.key, n.merge_depth, n.revno, n.end_of_merge)
1687
for n in graph_thunk.merge_sort(b'C')])
1690
class TestStackedParentsProvider(tests.TestCase):
1693
super(TestStackedParentsProvider, self).setUp()
1696
def get_shared_provider(self, info, ancestry, has_cached):
1697
pp = _mod_graph.DictParentsProvider(ancestry)
1699
pp.get_cached_parent_map = pp.get_parent_map
1700
return SharedInstrumentedParentsProvider(pp, self.calls, info)
1702
def test_stacked_parents_provider(self):
1703
parents1 = _mod_graph.DictParentsProvider({b'rev2': [b'rev3']})
1704
parents2 = _mod_graph.DictParentsProvider({b'rev1': [b'rev4']})
1705
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1706
self.assertEqual({b'rev1': [b'rev4'], b'rev2': [b'rev3']},
1707
stacked.get_parent_map([b'rev1', b'rev2']))
1708
self.assertEqual({b'rev2': [b'rev3'], b'rev1': [b'rev4']},
1709
stacked.get_parent_map([b'rev2', b'rev1']))
1710
self.assertEqual({b'rev2': [b'rev3']},
1711
stacked.get_parent_map([b'rev2', b'rev2']))
1712
self.assertEqual({b'rev1': [b'rev4']},
1713
stacked.get_parent_map([b'rev1', b'rev1']))
1715
def test_stacked_parents_provider_overlapping(self):
1716
# rev2 is availible in both providers.
1720
parents1 = _mod_graph.DictParentsProvider({b'rev2': [b'rev1']})
1721
parents2 = _mod_graph.DictParentsProvider({b'rev2': [b'rev1']})
1722
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1723
self.assertEqual({b'rev2': [b'rev1']},
1724
stacked.get_parent_map([b'rev2']))
1726
def test_handles_no_get_cached_parent_map(self):
1727
# this shows that we both handle when a provider doesn't implement
1728
# get_cached_parent_map
1729
pp1 = self.get_shared_provider(b'pp1', {b'rev2': (b'rev1',)},
1731
pp2 = self.get_shared_provider(b'pp2', {b'rev2': (b'rev1',)},
1733
stacked = _mod_graph.StackedParentsProvider([pp1, pp2])
1734
self.assertEqual({b'rev2': (b'rev1',)},
1735
stacked.get_parent_map([b'rev2']))
1736
# No call on b'pp1' because it doesn't provide get_cached_parent_map
1737
self.assertEqual([(b'pp2', 'cached', [b'rev2'])], self.calls)
1739
def test_query_order(self):
1740
# We should call get_cached_parent_map on all providers before we call
1741
# get_parent_map. Further, we should track what entries we have found,
1742
# and not re-try them.
1743
pp1 = self.get_shared_provider(b'pp1', {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)
1748
stacked = _mod_graph.StackedParentsProvider([pp1, pp2, pp3])
1749
self.assertEqual({b'a': (), b'b': (b'a',), b'c': (b'b',)},
1750
stacked.get_parent_map([b'a', b'b', b'c', b'd']))
1751
self.assertEqual([(b'pp1', 'cached', [b'a', b'b', b'c', b'd']),
1752
# No call to pp2, because it doesn't have cached
1753
(b'pp3', 'cached', [b'b', b'c', b'd']),
1754
(b'pp1', [b'c', b'd']),
1755
(b'pp2', [b'c', b'd']),
added
removed
breezy/tests/test_graph.py
