651
620
graph = mainline_tree.branch.repository.get_graph(
652
621
feature_tree.branch.repository)
653
self.assertEqual(b'rev2b', graph.find_unique_lca(b'rev2a', b'rev3b'))
622
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
655
624
def test_graph_difference(self):
656
625
graph = self.make_graph(ancestry_1)
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'))
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'))
668
636
def test_graph_difference_separate_ancestry(self):
669
637
graph = self.make_graph(ancestry_2)
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'))
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'))
676
644
def test_graph_difference_criss_cross(self):
677
645
graph = self.make_graph(criss_cross)
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'))
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'))
683
651
def test_graph_difference_extended_history(self):
684
652
graph = self.make_graph(extended_history_shortcut)
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'))
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'))
690
658
def test_graph_difference_double_shortcut(self):
691
659
graph = self.make_graph(double_shortcut)
692
self.assertEqual(({b'd', b'f'}, {b'e', b'g'}),
693
graph.find_difference(b'f', b'g'))
660
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
661
graph.find_difference('f', 'g'))
695
663
def test_graph_difference_complex_shortcut(self):
696
664
graph = self.make_graph(complex_shortcut)
697
self.assertEqual(({b'm', b'i', b'e'}, {b'n', b'h'}),
698
graph.find_difference(b'm', b'n'))
665
self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
666
graph.find_difference('m', 'n'))
700
668
def test_graph_difference_complex_shortcut2(self):
701
669
graph = self.make_graph(complex_shortcut2)
702
self.assertEqual(({b't'}, {b'j', b'u'}),
703
graph.find_difference(b't', b'u'))
670
self.assertEqual((set(['t']), set(['j', 'u'])),
671
graph.find_difference('t', 'u'))
705
673
def test_graph_difference_shortcut_extra_root(self):
706
674
graph = self.make_graph(shortcut_extra_root)
707
self.assertEqual(({b'e'}, {b'f', b'g'}),
708
graph.find_difference(b'e', b'f'))
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']))
710
717
def test_iter_topo_order(self):
711
718
graph = self.make_graph(ancestry_1)
712
args = [b'rev2a', b'rev3', b'rev1']
719
args = ['rev2a', 'rev3', 'rev1']
713
720
topo_args = list(graph.iter_topo_order(args))
714
721
self.assertEqual(set(args), set(topo_args))
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'))
722
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
723
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
718
725
def test_is_ancestor(self):
719
726
graph = self.make_graph(ancestry_1)
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'))
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'))
729
736
instrumented_provider = InstrumentedParentsProvider(graph)
730
737
instrumented_graph = _mod_graph.Graph(instrumented_provider)
731
instrumented_graph.is_ancestor(b'rev2a', b'rev2b')
732
self.assertTrue(b'null:' not in instrumented_provider.calls)
738
instrumented_graph.is_ancestor('rev2a', 'rev2b')
739
self.assertTrue('null:' not in instrumented_provider.calls)
734
741
def test_is_between(self):
735
742
graph = self.make_graph(ancestry_1)
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'))
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'))
745
752
def test_is_ancestor_boundary(self):
746
753
"""Ensure that we avoid searching the whole graph.
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']))
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']))
800
807
def test_heads_null(self):
801
808
graph = self.make_graph(ancestry_1)
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:')))
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:')))
808
815
def test_heads_one(self):
809
816
# A single node will always be a head
810
817
graph = self.make_graph(ancestry_1)
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']))
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']))
818
825
def test_heads_single(self):
819
826
graph = self.make_graph(ancestry_1)
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']))
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']))
829
836
def test_heads_two_heads(self):
830
837
graph = self.make_graph(ancestry_1)
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']))
838
self.assertEqual(set(['rev2a', 'rev2b']),
839
graph.heads(['rev2a', 'rev2b']))
840
self.assertEqual(set(['rev3', 'rev2b']),
841
graph.heads(['rev3', 'rev2b']))
836
843
def test_heads_criss_cross(self):
837
844
graph = self.make_graph(criss_cross)
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']))
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']))
865
872
def test_heads_shortcut(self):
866
873
graph = self.make_graph(history_shortcut)
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']))
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']))
879
886
def _run_heads_break_deeper(self, graph_dict, search):
880
887
"""Run heads on a graph-as-a-dict.
882
If the search asks for the parents of b'deeper' the test will fail.
889
If the search asks for the parents of 'deeper' the test will fail.
884
891
class stub(object):
887
893
def get_parent_map(keys):
891
897
self.fail('key deeper was accessed')
892
898
result[key] = graph_dict[key]
899
905
def test_heads_limits_search(self):
900
906
# 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'],
906
self.assertEqual({b'left', b'right'},
907
self._run_heads_break_deeper(graph_dict, [b'left', b'right']))
912
self.assertEqual(set(['left', 'right']),
913
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
909
915
def test_heads_limits_search_assymetric(self):
910
916
# test that a heads query does not search all of history
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'],
919
'midleft':['common'],
921
'common':['aftercommon'],
922
'aftercommon':['deeper'],
918
self.assertEqual({b'left', b'right'},
919
self._run_heads_break_deeper(graph_dict, [b'left', b'right']))
924
self.assertEqual(set(['left', 'right']),
925
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
921
927
def test_heads_limits_search_common_search_must_continue(self):
922
928
# test that common nodes are still queried, preventing
923
929
# all-the-way-to-origin behaviour in the following graph:
925
b'h1': [b'shortcut', b'common1'],
927
b'shortcut': [b'common2'],
928
b'common1': [b'common2'],
929
b'common2': [b'deeper'],
931
'h1':['shortcut', 'common1'],
933
'shortcut':['common2'],
934
'common1':['common2'],
935
'common2':['deeper'],
931
self.assertEqual({b'h1', b'h2'},
932
self._run_heads_break_deeper(graph_dict, [b'h1', b'h2']))
937
self.assertEqual(set(['h1', 'h2']),
938
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
934
940
def test_breadth_first_search_start_ghosts(self):
935
941
graph = self.make_graph({})
936
942
# with_ghosts reports the ghosts
937
search = graph._make_breadth_first_searcher([b'a-ghost'])
938
self.assertEqual((set(), {b'a-ghost'}), search.next_with_ghosts())
943
search = graph._make_breadth_first_searcher(['a-ghost'])
944
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
939
945
self.assertRaises(StopIteration, search.next_with_ghosts)
940
946
# next includes them
941
search = graph._make_breadth_first_searcher([b'a-ghost'])
942
self.assertEqual({b'a-ghost'}, next(search))
943
self.assertRaises(StopIteration, next, search)
947
search = graph._make_breadth_first_searcher(['a-ghost'])
948
self.assertEqual(set(['a-ghost']), search.next())
949
self.assertRaises(StopIteration, search.next)
945
951
def test_breadth_first_search_deep_ghosts(self):
946
952
graph = self.make_graph({
947
b'head': [b'present'],
948
b'present': [b'child', b'ghost'],
954
'present':['child', 'ghost'],
951
957
# with_ghosts reports the 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())
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())
957
963
self.assertRaises(StopIteration, search.next_with_ghosts)
958
964
# next includes them
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)
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)
966
972
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
967
973
# To make the API robust, we allow calling both next() and
968
974
# next_with_ghosts() on the same searcher.
969
975
graph = self.make_graph({
970
b'head': [b'present'],
971
b'present': [b'child', b'ghost'],
977
'present':['child', 'ghost'],
974
980
# start with next_with_ghosts
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)
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)
981
987
# start with next
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'},
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']),
987
993
self.assertRaises(StopIteration, search.next_with_ghosts)
989
995
def test_breadth_first_change_search(self):
990
996
# Changing the search should work with both next and next_with_ghosts.
991
997
graph = self.make_graph({
992
b'head': [b'present'],
993
b'present': [b'stopped'],
994
b'other': [b'other_2'],
999
'present':['stopped'],
1000
'other':['other_2'],
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())
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())
1005
1011
self.assertRaises(StopIteration, search.next_with_ghosts)
1006
1012
# next includes them
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)
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)
1016
1022
def assertSeenAndResult(self, instructions, search, next):
1017
1023
"""Check the results of .seen and get_result() for a seach.
1034
1040
search.start_searching(starts)
1035
1041
if stops is not None:
1036
1042
search.stop_searching_any(stops)
1037
state = search.get_state()
1038
self.assertEqual(set(included_keys), state[2])
1043
result = search.get_result()
1044
self.assertEqual(recipe, result.get_recipe())
1045
self.assertEqual(set(included_keys), result.get_keys())
1039
1046
self.assertEqual(seen, search.seen)
1041
1048
def test_breadth_first_get_result_excludes_current_pending(self):
1042
1049
graph = self.make_graph({
1043
b'head': [b'child'],
1044
b'child': [NULL_REVISION],
1051
'child':[NULL_REVISION],
1047
search = graph._make_breadth_first_searcher([b'head'])
1054
search = graph._make_breadth_first_searcher(['head'])
1048
1055
# At the start, nothing has been seen, to its all excluded:
1049
state = search.get_state()
1050
self.assertEqual(({b'head'}, {b'head'}, set()),
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())
1052
1060
self.assertEqual(set(), search.seen)
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),
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),
1062
self.assertSeenAndResult(expected, search, search.__next__)
1070
self.assertSeenAndResult(expected, search, search.next)
1063
1071
# using next_with_ghosts:
1064
search = graph._make_breadth_first_searcher([b'head'])
1072
search = graph._make_breadth_first_searcher(['head'])
1065
1073
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1067
1075
def test_breadth_first_get_result_starts_stops(self):
1068
1076
graph = self.make_graph({
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],
1078
'child':[NULL_REVISION],
1079
'otherhead':['otherchild'],
1080
'otherchild':['excluded'],
1081
'excluded':[NULL_REVISION],
1076
1084
search = graph._make_breadth_first_searcher([])
1077
1085
# Starting with nothing and adding a search works:
1078
search.start_searching([b'head'])
1086
search.start_searching(['head'])
1079
1087
# head has been seen:
1080
state = search.get_state()
1081
self.assertEqual(({b'head'}, {b'child'}, {b'head'}),
1083
self.assertEqual({b'head'}, search.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)
1086
1095
# stop at child, and start a new search at otherhead:
1087
1096
# - otherhead counts as seen immediately when start_searching is
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),
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),
1095
1104
# stop searching excluded now
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']),
1105
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1106
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1107
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1100
self.assertSeenAndResult(expected, search, search.__next__)
1109
self.assertSeenAndResult(expected, search, search.next)
1101
1110
# using next_with_ghosts:
1102
1111
search = graph._make_breadth_first_searcher([])
1103
search.start_searching([b'head'])
1112
search.start_searching(['head'])
1104
1113
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1106
1115
def test_breadth_first_stop_searching_not_queried(self):
1107
# A client should be able to say b'stop node X' even if X has not been
1116
# A client should be able to say 'stop node X' even if X has not been
1108
1117
# returned to the client.
1109
1118
graph = self.make_graph({
1110
b'head': [b'child', b'ghost1'],
1111
b'child': [NULL_REVISION],
1119
'head':['child', 'ghost1'],
1120
'child':[NULL_REVISION],
1114
search = graph._make_breadth_first_searcher([b'head'])
1123
search = graph._make_breadth_first_searcher(['head'])
1116
1125
# NULL_REVISION and ghost1 have not been returned
1118
({b'head'}, {b'child', NULL_REVISION, b'ghost1'}, 1),
1119
[b'head'], None, [NULL_REVISION, b'ghost1']),
1127
(set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1128
['head'], None, [NULL_REVISION, 'ghost1']),
1120
1129
# ghost1 has been returned, NULL_REVISION is to be returned in the
1121
1130
# next iteration.
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']),
1131
(set(['head', 'child', 'ghost1']),
1132
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1133
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1126
self.assertSeenAndResult(expected, search, search.__next__)
1135
self.assertSeenAndResult(expected, search, search.next)
1127
1136
# using next_with_ghosts:
1128
search = graph._make_breadth_first_searcher([b'head'])
1137
search = graph._make_breadth_first_searcher(['head'])
1129
1138
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1131
1140
def test_breadth_first_stop_searching_late(self):
1132
# A client should be able to say b'stop node X' and have it excluded
1141
# A client should be able to say 'stop node X' and have it excluded
1133
1142
# from the result even if X was seen in an older iteration of the
1135
1144
graph = self.make_graph({
1136
b'head': [b'middle'],
1137
b'middle': [b'child'],
1138
b'child': [NULL_REVISION],
1147
'child':[NULL_REVISION],
1141
search = graph._make_breadth_first_searcher([b'head'])
1150
search = graph._make_breadth_first_searcher(['head'])
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
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
1148
1157
# searching it until *after* advancing the searcher.
1149
({b'head', b'middle', b'child'},
1150
({b'head'}, {b'middle', b'child'}, 1),
1151
[b'head'], None, [b'middle', b'child']),
1158
(set(['head', 'middle', 'child']),
1159
(set(['head']), set(['middle', 'child']), 1),
1160
['head'], None, ['middle', 'child']),
1153
self.assertSeenAndResult(expected, search, search.__next__)
1162
self.assertSeenAndResult(expected, search, search.next)
1154
1163
# using next_with_ghosts:
1155
search = graph._make_breadth_first_searcher([b'head'])
1164
search = graph._make_breadth_first_searcher(['head'])
1156
1165
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1158
1167
def test_breadth_first_get_result_ghosts_are_excluded(self):
1159
1168
graph = self.make_graph({
1160
b'head': [b'child', b'ghost'],
1161
b'child': [NULL_REVISION],
1169
'head':['child', 'ghost'],
1170
'child':[NULL_REVISION],
1164
search = graph._make_breadth_first_searcher([b'head'])
1173
search = graph._make_breadth_first_searcher(['head'])
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),
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),
1174
self.assertSeenAndResult(expected, search, search.__next__)
1183
self.assertSeenAndResult(expected, search, search.next)
1175
1184
# using next_with_ghosts:
1176
search = graph._make_breadth_first_searcher([b'head'])
1185
search = graph._make_breadth_first_searcher(['head'])
1177
1186
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1179
1188
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1180
1189
graph = self.make_graph({
1181
b'head': [b'child'],
1182
b'child': [NULL_REVISION],
1191
'child':[NULL_REVISION],
1185
search = graph._make_breadth_first_searcher([b'head'])
1194
search = graph._make_breadth_first_searcher(['head'])
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),
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),
1195
self.assertSeenAndResult(expected, search, search.__next__)
1204
self.assertSeenAndResult(expected, search, search.next)
1196
1205
# using next_with_ghosts:
1197
search = graph._make_breadth_first_searcher([b'head'])
1206
search = graph._make_breadth_first_searcher(['head'])
1198
1207
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1200
1209
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1201
1210
graph = self.make_graph({
1202
b'head': [NULL_REVISION],
1211
'head':[NULL_REVISION],
1205
search = graph._make_breadth_first_searcher([b'head'])
1214
search = graph._make_breadth_first_searcher(['head'])
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),
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),
1215
self.assertSeenAndResult(expected, search, search.__next__)
1224
self.assertSeenAndResult(expected, search, search.next)
1216
1225
# using next_with_ghosts:
1217
search = graph._make_breadth_first_searcher([b'head'])
1226
search = graph._make_breadth_first_searcher(['head'])
1218
1227
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1220
1229
def test_breadth_first_search_get_result_after_StopIteration(self):
1221
1230
# StopIteration should not invalid anything..
1222
1231
graph = self.make_graph({
1223
b'head': [NULL_REVISION],
1232
'head':[NULL_REVISION],
1226
search = graph._make_breadth_first_searcher([b'head'])
1235
search = graph._make_breadth_first_searcher(['head'])
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),
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),
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}),
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())
1244
1252
# using next_with_ghosts:
1245
search = graph._make_breadth_first_searcher([b'head'])
1253
search = graph._make_breadth_first_searcher(['head'])
1246
1254
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
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}),
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())
1256
1263
class TestFindUniqueAncestors(TestGraphBase):
1262
1269
def test_empty_set(self):
1263
1270
graph = self.make_graph(ancestry_1)
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'])
1271
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1272
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1273
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1268
1275
def test_single_node(self):
1269
1276
graph = self.make_graph(ancestry_1)
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'])
1277
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1278
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1279
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1274
1281
def test_minimal_ancestry(self):
1275
1282
graph = self.make_breaking_graph(extended_history_shortcut,
1276
[NULL_REVISION, b'a', b'b'])
1277
self.assertFindUniqueAncestors(graph, [b'e'], b'e', [b'd'])
1283
[NULL_REVISION, 'a', 'b'])
1284
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1279
1286
graph = self.make_breaking_graph(extended_history_shortcut,
1281
self.assertFindUniqueAncestors(graph, [b'f'], b'f', [b'a', b'd'])
1288
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1283
1290
graph = self.make_breaking_graph(complex_shortcut,
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'])
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'])
1290
1297
def test_in_ancestry(self):
1291
1298
graph = self.make_graph(ancestry_1)
1292
self.assertFindUniqueAncestors(graph, [], b'rev1', [b'rev3'])
1293
self.assertFindUniqueAncestors(graph, [], b'rev2b', [b'rev4'])
1299
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1300
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1295
1302
def test_multiple_revisions(self):
1296
1303
graph = self.make_graph(ancestry_1)
1297
1304
self.assertFindUniqueAncestors(graph,
1298
[b'rev4'], b'rev4', [b'rev3', b'rev2b'])
1305
['rev4'], 'rev4', ['rev3', 'rev2b'])
1299
1306
self.assertFindUniqueAncestors(graph,
1300
[b'rev2a', b'rev3', b'rev4'], b'rev4', [b'rev2b'])
1307
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1302
1309
def test_complex_shortcut(self):
1303
1310
graph = self.make_graph(complex_shortcut)
1304
1311
self.assertFindUniqueAncestors(graph,
1305
[b'h', b'n'], b'n', [b'm'])
1312
['h', 'n'], 'n', ['m'])
1306
1313
self.assertFindUniqueAncestors(graph,
1307
[b'e', b'i', b'm'], b'm', [b'n'])
1314
['e', 'i', 'm'], 'm', ['n'])
1309
1316
def test_complex_shortcut2(self):
1310
1317
graph = self.make_graph(complex_shortcut2)
1311
1318
self.assertFindUniqueAncestors(graph,
1312
[b'j', b'u'], b'u', [b't'])
1319
['j', 'u'], 'u', ['t'])
1313
1320
self.assertFindUniqueAncestors(graph,
1314
[b't'], b't', [b'u'])
1316
1323
def test_multiple_interesting_unique(self):
1317
1324
graph = self.make_graph(multiple_interesting_unique)
1318
1325
self.assertFindUniqueAncestors(graph,
1319
[b'j', b'y'], b'y', [b'z'])
1326
['j', 'y'], 'y', ['z'])
1320
1327
self.assertFindUniqueAncestors(graph,
1321
[b'p', b'z'], b'z', [b'y'])
1328
['p', 'z'], 'z', ['y'])
1323
1330
def test_racing_shortcuts(self):
1324
1331
graph = self.make_graph(racing_shortcuts)
1325
1332
self.assertFindUniqueAncestors(graph,
1326
[b'p', b'q', b'z'], b'z', [b'y'])
1333
['p', 'q', 'z'], 'z', ['y'])
1327
1334
self.assertFindUniqueAncestors(graph,
1328
[b'h', b'i', b'j', b'y'], b'j', [b'z'])
1335
['h', 'i', 'j', 'y'], 'j', ['z'])
1331
1338
class TestGraphFindDistanceToNull(TestGraphBase):
1339
1346
def test_nothing_known(self):
1340
1347
graph = self.make_graph(ancestry_1)
1341
1348
self.assertFindDistance(0, graph, NULL_REVISION, [])
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', [])
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', [])
1348
1355
def test_rev_is_ghost(self):
1349
1356
graph = self.make_graph(ancestry_1)
1350
1357
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
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)
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)
1355
1362
def test_ancestor_is_ghost(self):
1356
graph = self.make_graph({b'rev': [b'parent']})
1363
graph = self.make_graph({'rev':['parent']})
1357
1364
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
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)
1365
graph.find_distance_to_null, 'rev', [])
1366
self.assertEqual('rev', e.revision_id)
1367
self.assertEqual('parent', e.ghost_revision_id)
1362
1369
def test_known_in_ancestry(self):
1363
1370
graph = self.make_graph(ancestry_1)
1364
self.assertFindDistance(2, graph, b'rev2a', [(b'rev1', 1)])
1365
self.assertFindDistance(3, graph, b'rev3', [(b'rev2a', 2)])
1371
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1372
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1367
1374
def test_known_in_ancestry_limits(self):
1368
graph = self.make_breaking_graph(ancestry_1, [b'rev1'])
1369
self.assertFindDistance(4, graph, b'rev4', [(b'rev3', 3)])
1375
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1376
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1371
1378
def test_target_is_ancestor(self):
1372
1379
graph = self.make_graph(ancestry_1)
1373
self.assertFindDistance(2, graph, b'rev2a', [(b'rev3', 3)])
1380
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1375
1382
def test_target_is_ancestor_limits(self):
1376
1383
"""We shouldn't search all history if we run into ourselves"""
1377
graph = self.make_breaking_graph(ancestry_1, [b'rev1'])
1378
self.assertFindDistance(3, graph, b'rev3', [(b'rev4', 4)])
1384
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1385
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1380
1387
def test_target_parallel_to_known_limits(self):
1381
1388
# Even though the known revision isn't part of the other ancestry, they
1382
1389
# eventually converge
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)])
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)])
1390
1397
class TestFindMergeOrder(TestGraphBase):
1395
1402
def test_parents(self):
1396
1403
graph = self.make_graph(ancestry_1)
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'])
1404
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1406
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1402
1409
def test_ancestors(self):
1403
1410
graph = self.make_graph(ancestry_1)
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'])
1411
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1413
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1409
1416
def test_shortcut_one_ancestor(self):
1410
1417
# When we have enough info, we can stop searching
1411
graph = self.make_breaking_graph(
1412
ancestry_1, [b'rev3', b'rev2b', b'rev4'])
1418
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1413
1419
# Single ancestors shortcut right away
1414
self.assertMergeOrder([b'rev3'], graph, b'rev4', [b'rev3'])
1420
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1416
1422
def test_shortcut_after_one_ancestor(self):
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']},
1423
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1424
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1478
1427
class TestCachingParentsProvider(tests.TestCase):
1486
1435
def setUp(self):
1487
1436
super(TestCachingParentsProvider, self).setUp()
1488
dict_pp = _mod_graph.DictParentsProvider({b'a': (b'b',)})
1437
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1489
1438
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1490
1439
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1492
1441
def test_get_parent_map(self):
1493
1442
"""Requesting the same revision should be returned from cache"""
1494
1443
self.assertEqual({}, self.caching_pp._cache)
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']))
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']))
1500
1447
# No new call, as it should have been returned from the cache
1501
self.assertEqual([b'a'], self.inst_pp.calls)
1502
self.assertEqual({b'a': (b'b',)}, self.caching_pp._cache)
1448
self.assertEqual(['a'], self.inst_pp.calls)
1449
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1504
1451
def test_get_parent_map_not_present(self):
1505
1452
"""The cache should also track when a revision doesn't exist"""
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']))
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']))
1510
self.assertEqual([b'b'], self.inst_pp.calls)
1457
self.assertEqual(['b'], self.inst_pp.calls)
1512
1459
def test_get_parent_map_mixed(self):
1513
1460
"""Anything that can be returned from cache, should be"""
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)
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)
1520
1467
def test_get_parent_map_repeated(self):
1521
1468
"""Asking for the same parent 2x will only forward 1 request."""
1522
self.assertEqual({b'a': (b'b',)},
1523
self.caching_pp.get_parent_map([b'b', b'a', b'b']))
1469
self.assertEqual({'a':('b',)},
1470
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1524
1471
# Use sorted because we don't care about the order, just that each is
1525
1472
# only present 1 time.
1526
self.assertEqual([b'a', b'b'], sorted(self.inst_pp.calls))
1473
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1528
1475
def test_note_missing_key(self):
1529
1476
"""After noting that a key is missing it is cached."""
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']))
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)
1545
1483
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1663
d = {(b'D',): [(b'B',), (b'C',)], (b'C',): [(b'A',)],
1664
(b'B',): [(b'A',)], (b'A',): []}
1593
d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1594
('B',): [('A',)], ('A',): []}
1665
1595
g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1666
1596
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
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']),
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())
added
removed
bzrlib/tests/test_graph.py
