648
259
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
649
260
graph.find_difference('rev2a', 'rev3b'))
651
def test_graph_difference_extended_history(self):
652
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'))
658
def test_graph_difference_double_shortcut(self):
659
graph = self.make_graph(double_shortcut)
660
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
661
graph.find_difference('f', 'g'))
663
def test_graph_difference_complex_shortcut(self):
664
graph = self.make_graph(complex_shortcut)
665
self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
666
graph.find_difference('m', 'n'))
668
def test_graph_difference_complex_shortcut2(self):
669
graph = self.make_graph(complex_shortcut2)
670
self.assertEqual((set(['t']), set(['j', 'u'])),
671
graph.find_difference('t', 'u'))
673
def test_graph_difference_shortcut_extra_root(self):
674
graph = self.make_graph(shortcut_extra_root)
675
self.assertEqual((set(['e']), set(['f', 'g'])),
676
graph.find_difference('e', 'f'))
679
262
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']))
717
def test_iter_topo_order(self):
718
graph = self.make_graph(ancestry_1)
719
args = ['rev2a', 'rev3', 'rev1']
720
topo_args = list(graph.iter_topo_order(args))
721
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'))
725
def test_is_ancestor(self):
726
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'))
736
instrumented_provider = InstrumentedParentsProvider(graph)
737
instrumented_graph = _mod_graph.Graph(instrumented_provider)
738
instrumented_graph.is_ancestor('rev2a', 'rev2b')
739
self.assertTrue('null:' not in instrumented_provider.calls)
741
def test_is_between(self):
742
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'))
752
def test_is_ancestor_boundary(self):
753
"""Ensure that we avoid searching the whole graph.
755
This requires searching through b as a common ancestor, so we
756
can identify that e is common.
758
graph = self.make_graph(boundary)
759
instrumented_provider = InstrumentedParentsProvider(graph)
760
graph = _mod_graph.Graph(instrumented_provider)
761
self.assertFalse(graph.is_ancestor('a', 'c'))
762
self.assertTrue('null:' not in instrumented_provider.calls)
764
def test_iter_ancestry(self):
765
nodes = boundary.copy()
766
nodes[NULL_REVISION] = ()
767
graph = self.make_graph(nodes)
768
expected = nodes.copy()
769
expected.pop('a') # 'a' is not in the ancestry of 'c', all the
771
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
772
self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
774
def test_iter_ancestry_with_ghost(self):
775
graph = self.make_graph(with_ghost)
776
expected = with_ghost.copy()
777
# 'a' is not in the ancestry of 'c', and 'g' is a ghost
779
self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
781
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
783
def test_filter_candidate_lca(self):
784
"""Test filter_candidate_lca for a corner case
786
This tests the case where we encounter the end of iteration for 'e'
787
in the same pass as we discover that 'd' is an ancestor of 'e', and
788
therefore 'e' can't be an lca.
790
To compensate for different dict orderings on other Python
791
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
793
# This test is sensitive to the iteration order of dicts. It will
794
# pass incorrectly if 'e' and 'a' sort before 'c'
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']))
807
def test_heads_null(self):
808
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:')))
815
def test_heads_one(self):
816
# A single node will always be a head
817
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']))
825
def test_heads_single(self):
826
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']))
836
def test_heads_two_heads(self):
837
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']))
843
def test_heads_criss_cross(self):
844
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']))
872
def test_heads_shortcut(self):
873
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']))
886
def _run_heads_break_deeper(self, graph_dict, search):
887
"""Run heads on a graph-as-a-dict.
889
If the search asks for the parents of 'deeper' the test will fail.
893
def get_parent_map(keys):
897
self.fail('key deeper was accessed')
898
result[key] = graph_dict[key]
901
an_obj.get_parent_map = get_parent_map
902
graph = _mod_graph.Graph(an_obj)
903
return graph.heads(search)
905
def test_heads_limits_search(self):
906
# test that a heads query does not search all of history
912
self.assertEqual(set(['left', 'right']),
913
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
915
def test_heads_limits_search_assymetric(self):
916
# test that a heads query does not search all of history
919
'midleft':['common'],
921
'common':['aftercommon'],
922
'aftercommon':['deeper'],
924
self.assertEqual(set(['left', 'right']),
925
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
927
def test_heads_limits_search_common_search_must_continue(self):
928
# test that common nodes are still queried, preventing
929
# all-the-way-to-origin behaviour in the following graph:
931
'h1':['shortcut', 'common1'],
933
'shortcut':['common2'],
934
'common1':['common2'],
935
'common2':['deeper'],
937
self.assertEqual(set(['h1', 'h2']),
938
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
940
def test_breadth_first_search_start_ghosts(self):
941
graph = self.make_graph({})
942
# 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())
945
self.assertRaises(StopIteration, search.next_with_ghosts)
947
search = graph._make_breadth_first_searcher(['a-ghost'])
948
self.assertEqual(set(['a-ghost']), search.next())
949
self.assertRaises(StopIteration, search.next)
951
def test_breadth_first_search_deep_ghosts(self):
952
graph = self.make_graph({
954
'present':['child', 'ghost'],
957
# 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())
963
self.assertRaises(StopIteration, search.next_with_ghosts)
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)
972
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
973
# To make the API robust, we allow calling both next() and
974
# next_with_ghosts() on the same searcher.
975
graph = self.make_graph({
977
'present':['child', 'ghost'],
980
# 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)
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']),
993
self.assertRaises(StopIteration, search.next_with_ghosts)
995
def test_breadth_first_change_search(self):
996
# Changing the search should work with both next and next_with_ghosts.
997
graph = self.make_graph({
999
'present':['stopped'],
1000
'other':['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())
1011
self.assertRaises(StopIteration, search.next_with_ghosts)
1012
# 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)
1022
def assertSeenAndResult(self, instructions, search, next):
1023
"""Check the results of .seen and get_result() for a seach.
1025
:param instructions: A list of tuples:
1026
(seen, recipe, included_keys, starts, stops).
1027
seen, recipe and included_keys are results to check on the search
1028
and the searches get_result(). starts and stops are parameters to
1029
pass to start_searching and stop_searching_any during each
1030
iteration, if they are not None.
1031
:param search: The search to use.
1032
:param next: A callable to advance the search.
1034
for seen, recipe, included_keys, starts, stops in instructions:
1035
# Adjust for recipe contract changes that don't vary for all the
1037
recipe = ('search',) + recipe
1039
if starts is not None:
1040
search.start_searching(starts)
1041
if stops is not None:
1042
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())
1046
self.assertEqual(seen, search.seen)
1048
def test_breadth_first_get_result_excludes_current_pending(self):
1049
graph = self.make_graph({
1051
'child':[NULL_REVISION],
1054
search = graph._make_breadth_first_searcher(['head'])
1055
# 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())
1060
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),
1070
self.assertSeenAndResult(expected, search, search.next)
1071
# using next_with_ghosts:
1072
search = graph._make_breadth_first_searcher(['head'])
1073
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1075
def test_breadth_first_get_result_starts_stops(self):
1076
graph = self.make_graph({
1078
'child':[NULL_REVISION],
1079
'otherhead':['otherchild'],
1080
'otherchild':['excluded'],
1081
'excluded':[NULL_REVISION],
1084
search = graph._make_breadth_first_searcher([])
1085
# Starting with nothing and adding a search works:
1086
search.start_searching(['head'])
1087
# 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)
1095
# stop at child, and start a new search at otherhead:
1096
# - 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),
1104
# 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']),
1109
self.assertSeenAndResult(expected, search, search.next)
1110
# using next_with_ghosts:
1111
search = graph._make_breadth_first_searcher([])
1112
search.start_searching(['head'])
1113
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1115
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
1117
# returned to the client.
1118
graph = self.make_graph({
1119
'head':['child', 'ghost1'],
1120
'child':[NULL_REVISION],
1123
search = graph._make_breadth_first_searcher(['head'])
1125
# NULL_REVISION and ghost1 have not been returned
1127
(set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1128
['head'], None, [NULL_REVISION, 'ghost1']),
1129
# ghost1 has been returned, NULL_REVISION is to be returned in the
1131
(set(['head', 'child', 'ghost1']),
1132
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1133
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1135
self.assertSeenAndResult(expected, search, search.next)
1136
# using next_with_ghosts:
1137
search = graph._make_breadth_first_searcher(['head'])
1138
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1140
def test_breadth_first_stop_searching_late(self):
1141
# A client should be able to say 'stop node X' and have it excluded
1142
# from the result even if X was seen in an older iteration of the
1144
graph = self.make_graph({
1147
'child':[NULL_REVISION],
1150
search = graph._make_breadth_first_searcher(['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
1157
# searching it until *after* advancing the searcher.
1158
(set(['head', 'middle', 'child']),
1159
(set(['head']), set(['middle', 'child']), 1),
1160
['head'], None, ['middle', 'child']),
1162
self.assertSeenAndResult(expected, search, search.next)
1163
# using next_with_ghosts:
1164
search = graph._make_breadth_first_searcher(['head'])
1165
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1167
def test_breadth_first_get_result_ghosts_are_excluded(self):
1168
graph = self.make_graph({
1169
'head':['child', 'ghost'],
1170
'child':[NULL_REVISION],
1173
search = graph._make_breadth_first_searcher(['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),
1183
self.assertSeenAndResult(expected, search, search.next)
1184
# using next_with_ghosts:
1185
search = graph._make_breadth_first_searcher(['head'])
1186
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1188
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1189
graph = self.make_graph({
1191
'child':[NULL_REVISION],
1194
search = graph._make_breadth_first_searcher(['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),
1204
self.assertSeenAndResult(expected, search, search.next)
1205
# using next_with_ghosts:
1206
search = graph._make_breadth_first_searcher(['head'])
1207
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1209
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1210
graph = self.make_graph({
1211
'head':[NULL_REVISION],
1214
search = graph._make_breadth_first_searcher(['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),
1224
self.assertSeenAndResult(expected, search, search.next)
1225
# using next_with_ghosts:
1226
search = graph._make_breadth_first_searcher(['head'])
1227
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1229
def test_breadth_first_search_get_result_after_StopIteration(self):
1230
# StopIteration should not invalid anything..
1231
graph = self.make_graph({
1232
'head':[NULL_REVISION],
1235
search = graph._make_breadth_first_searcher(['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),
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())
1252
# using next_with_ghosts:
1253
search = graph._make_breadth_first_searcher(['head'])
1254
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())
1263
class TestFindUniqueAncestors(TestGraphBase):
1265
def assertFindUniqueAncestors(self, graph, expected, node, common):
1266
actual = graph.find_unique_ancestors(node, common)
1267
self.assertEqual(expected, sorted(actual))
1269
def test_empty_set(self):
1270
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'])
1275
def test_single_node(self):
1276
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'])
1281
def test_minimal_ancestry(self):
1282
graph = self.make_breaking_graph(extended_history_shortcut,
1283
[NULL_REVISION, 'a', 'b'])
1284
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1286
graph = self.make_breaking_graph(extended_history_shortcut,
1288
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1290
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'])
1297
def test_in_ancestry(self):
1298
graph = self.make_graph(ancestry_1)
1299
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1300
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1302
def test_multiple_revisions(self):
1303
graph = self.make_graph(ancestry_1)
1304
self.assertFindUniqueAncestors(graph,
1305
['rev4'], 'rev4', ['rev3', 'rev2b'])
1306
self.assertFindUniqueAncestors(graph,
1307
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1309
def test_complex_shortcut(self):
1310
graph = self.make_graph(complex_shortcut)
1311
self.assertFindUniqueAncestors(graph,
1312
['h', 'n'], 'n', ['m'])
1313
self.assertFindUniqueAncestors(graph,
1314
['e', 'i', 'm'], 'm', ['n'])
1316
def test_complex_shortcut2(self):
1317
graph = self.make_graph(complex_shortcut2)
1318
self.assertFindUniqueAncestors(graph,
1319
['j', 'u'], 'u', ['t'])
1320
self.assertFindUniqueAncestors(graph,
1323
def test_multiple_interesting_unique(self):
1324
graph = self.make_graph(multiple_interesting_unique)
1325
self.assertFindUniqueAncestors(graph,
1326
['j', 'y'], 'y', ['z'])
1327
self.assertFindUniqueAncestors(graph,
1328
['p', 'z'], 'z', ['y'])
1330
def test_racing_shortcuts(self):
1331
graph = self.make_graph(racing_shortcuts)
1332
self.assertFindUniqueAncestors(graph,
1333
['p', 'q', 'z'], 'z', ['y'])
1334
self.assertFindUniqueAncestors(graph,
1335
['h', 'i', 'j', 'y'], 'j', ['z'])
1338
class TestGraphFindDistanceToNull(TestGraphBase):
1339
"""Test an api that should be able to compute a revno"""
1341
def assertFindDistance(self, revno, graph, target_id, known_ids):
1342
"""Assert the output of Graph.find_distance_to_null()"""
1343
actual = graph.find_distance_to_null(target_id, known_ids)
1344
self.assertEqual(revno, actual)
1346
def test_nothing_known(self):
1347
graph = self.make_graph(ancestry_1)
1348
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', [])
1355
def test_rev_is_ghost(self):
1356
graph = self.make_graph(ancestry_1)
1357
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)
1362
def test_ancestor_is_ghost(self):
1363
graph = self.make_graph({'rev':['parent']})
1364
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)
1369
def test_known_in_ancestry(self):
1370
graph = self.make_graph(ancestry_1)
1371
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1372
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1374
def test_known_in_ancestry_limits(self):
1375
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1376
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1378
def test_target_is_ancestor(self):
1379
graph = self.make_graph(ancestry_1)
1380
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1382
def test_target_is_ancestor_limits(self):
1383
"""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)])
1387
def test_target_parallel_to_known_limits(self):
1388
# Even though the known revision isn't part of the other ancestry, they
1389
# 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)])
1397
class TestFindMergeOrder(TestGraphBase):
1399
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1400
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1402
def test_parents(self):
1403
graph = self.make_graph(ancestry_1)
1404
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1406
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1409
def test_ancestors(self):
1410
graph = self.make_graph(ancestry_1)
1411
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1413
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1416
def test_shortcut_one_ancestor(self):
1417
# When we have enough info, we can stop searching
1418
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1419
# Single ancestors shortcut right away
1420
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1422
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'])
1427
class TestCachingParentsProvider(tests.TestCase):
1428
"""These tests run with:
1430
self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1432
self.caching_pp, a CachingParentsProvider layered on inst_pp.
1436
super(TestCachingParentsProvider, self).setUp()
1437
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1438
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1439
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1441
def test_get_parent_map(self):
1442
"""Requesting the same revision should be returned from cache"""
1443
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']))
1447
# 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)
1451
def test_get_parent_map_not_present(self):
1452
"""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']))
1457
self.assertEqual(['b'], self.inst_pp.calls)
1459
def test_get_parent_map_mixed(self):
1460
"""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)
1467
def test_get_parent_map_repeated(self):
1468
"""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']))
1471
# Use sorted because we don't care about the order, just that each is
1472
# only present 1 time.
1473
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1475
def test_note_missing_key(self):
1476
"""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)
1483
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1484
"""Test the behaviour when parents are provided that were not requested."""
1487
super(TestCachingParentsProviderExtras, self).setUp()
1488
class ExtraParentsProvider(object):
1490
def get_parent_map(self, keys):
1491
return {'rev1': [], 'rev2': ['rev1',]}
1493
self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1494
self.caching_pp = _mod_graph.CachingParentsProvider(
1495
get_parent_map=self.inst_pp.get_parent_map)
1497
def test_uncached(self):
1498
self.caching_pp.disable_cache()
1499
self.assertEqual({'rev1': []},
1500
self.caching_pp.get_parent_map(['rev1']))
1501
self.assertEqual(['rev1'], self.inst_pp.calls)
1502
self.assertIs(None, self.caching_pp._cache)
1504
def test_cache_initially_empty(self):
1505
self.assertEqual({}, self.caching_pp._cache)
1507
def test_cached(self):
1508
self.assertEqual({'rev1': []},
1509
self.caching_pp.get_parent_map(['rev1']))
1510
self.assertEqual(['rev1'], self.inst_pp.calls)
1511
self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1512
self.caching_pp._cache)
1513
self.assertEqual({'rev1': []},
1514
self.caching_pp.get_parent_map(['rev1']))
1515
self.assertEqual(['rev1'], self.inst_pp.calls)
1517
def test_disable_cache_clears_cache(self):
1518
# Put something in the cache
1519
self.caching_pp.get_parent_map(['rev1'])
1520
self.assertEqual(2, len(self.caching_pp._cache))
1521
self.caching_pp.disable_cache()
1522
self.assertIs(None, self.caching_pp._cache)
1524
def test_enable_cache_raises(self):
1525
e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1526
self.assertEqual('Cache enabled when already enabled.', str(e))
1528
def test_cache_misses(self):
1529
self.caching_pp.get_parent_map(['rev3'])
1530
self.caching_pp.get_parent_map(['rev3'])
1531
self.assertEqual(['rev3'], self.inst_pp.calls)
1533
def test_no_cache_misses(self):
1534
self.caching_pp.disable_cache()
1535
self.caching_pp.enable_cache(cache_misses=False)
1536
self.caching_pp.get_parent_map(['rev3'])
1537
self.caching_pp.get_parent_map(['rev3'])
1538
self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1540
def test_cache_extras(self):
1541
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1542
self.assertEqual({'rev2': ['rev1']},
1543
self.caching_pp.get_parent_map(['rev2']))
1544
self.assertEqual(['rev3'], self.inst_pp.calls)
1547
class TestCollapseLinearRegions(tests.TestCase):
1549
def assertCollapsed(self, collapsed, original):
1550
self.assertEqual(collapsed,
1551
_mod_graph.collapse_linear_regions(original))
1553
def test_collapse_nothing(self):
1554
d = {1:[2, 3], 2:[], 3:[]}
1555
self.assertCollapsed(d, d)
1556
d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1557
self.assertCollapsed(d, d)
1559
def test_collapse_chain(self):
1560
# Any time we have a linear chain, we should be able to collapse
1561
d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1562
self.assertCollapsed({1:[5], 5:[]}, d)
1563
d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1564
self.assertCollapsed({5:[1], 1:[]}, d)
1565
d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1566
self.assertCollapsed({5:[2], 2:[]}, d)
1568
def test_collapse_with_multiple_children(self):
1579
# 4 and 5 cannot be removed because 6 has 2 children
1580
# 2 and 3 cannot be removed because 1 has 2 parents
1581
d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1582
self.assertCollapsed(d, d)
1585
class TestGraphThunkIdsToKeys(tests.TestCase):
1587
def test_heads(self):
1593
d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1594
('B',): [('A',)], ('A',): []}
1595
g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1596
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())
264
class ParentsProvider(object):
266
def __init__(self, ancestry):
267
self.ancestry = ancestry
269
def get_parents(self, revisions):
270
return [self.ancestry.get(r, None) for r in revisions]
272
parents1 = ParentsProvider({'rev2': ['rev3']})
273
parents2 = ParentsProvider({'rev1': ['rev4']})
274
stacked = graph._StackedParentsProvider([parents1, parents2])
275
self.assertEqual([['rev4',], ['rev3']],
276
stacked.get_parents(['rev1', 'rev2']))
277
self.assertEqual([['rev3',], ['rev4']],
278
stacked.get_parents(['rev2', 'rev1']))
279
self.assertEqual([['rev3',], ['rev3']],
280
stacked.get_parents(['rev2', 'rev2']))
281
self.assertEqual([['rev4',], ['rev4']],
282
stacked.get_parents(['rev1', 'rev1']))
added
removed
bzrlib/tests/test_graph.py
