346
749
graph = _mod_graph.Graph(instrumented_provider)
347
750
self.assertFalse(graph.is_ancestor('a', 'c'))
348
751
self.assertTrue('null:' not in instrumented_provider.calls)
753
def test_iter_ancestry(self):
754
nodes = boundary.copy()
755
nodes[NULL_REVISION] = ()
756
graph = self.make_graph(nodes)
757
expected = nodes.copy()
758
expected.pop('a') # 'a' is not in the ancestry of 'c', all the
760
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
761
self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
763
def test_iter_ancestry_with_ghost(self):
764
graph = self.make_graph(with_ghost)
765
expected = with_ghost.copy()
766
# 'a' is not in the ancestry of 'c', and 'g' is a ghost
768
self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
770
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
772
def test_filter_candidate_lca(self):
773
"""Test filter_candidate_lca for a corner case
775
This tests the case where we encounter the end of iteration for 'e'
776
in the same pass as we discover that 'd' is an ancestor of 'e', and
777
therefore 'e' can't be an lca.
779
To compensate for different dict orderings on other Python
780
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
782
# This test is sensitive to the iteration order of dicts. It will
783
# pass incorrectly if 'e' and 'a' sort before 'c'
792
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
793
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
794
self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
796
def test_heads_null(self):
797
graph = self.make_graph(ancestry_1)
798
self.assertEqual(set(['null:']), graph.heads(['null:']))
799
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
800
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
801
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
802
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
804
def test_heads_one(self):
805
# A single node will always be a head
806
graph = self.make_graph(ancestry_1)
807
self.assertEqual(set(['null:']), graph.heads(['null:']))
808
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
809
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
810
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
811
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
812
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
814
def test_heads_single(self):
815
graph = self.make_graph(ancestry_1)
816
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
817
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
818
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
819
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
820
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
821
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
822
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
823
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
825
def test_heads_two_heads(self):
826
graph = self.make_graph(ancestry_1)
827
self.assertEqual(set(['rev2a', 'rev2b']),
828
graph.heads(['rev2a', 'rev2b']))
829
self.assertEqual(set(['rev3', 'rev2b']),
830
graph.heads(['rev3', 'rev2b']))
832
def test_heads_criss_cross(self):
833
graph = self.make_graph(criss_cross)
834
self.assertEqual(set(['rev2a']),
835
graph.heads(['rev2a', 'rev1']))
836
self.assertEqual(set(['rev2b']),
837
graph.heads(['rev2b', 'rev1']))
838
self.assertEqual(set(['rev3a']),
839
graph.heads(['rev3a', 'rev1']))
840
self.assertEqual(set(['rev3b']),
841
graph.heads(['rev3b', 'rev1']))
842
self.assertEqual(set(['rev2a', 'rev2b']),
843
graph.heads(['rev2a', 'rev2b']))
844
self.assertEqual(set(['rev3a']),
845
graph.heads(['rev3a', 'rev2a']))
846
self.assertEqual(set(['rev3a']),
847
graph.heads(['rev3a', 'rev2b']))
848
self.assertEqual(set(['rev3a']),
849
graph.heads(['rev3a', 'rev2a', 'rev2b']))
850
self.assertEqual(set(['rev3b']),
851
graph.heads(['rev3b', 'rev2a']))
852
self.assertEqual(set(['rev3b']),
853
graph.heads(['rev3b', 'rev2b']))
854
self.assertEqual(set(['rev3b']),
855
graph.heads(['rev3b', 'rev2a', 'rev2b']))
856
self.assertEqual(set(['rev3a', 'rev3b']),
857
graph.heads(['rev3a', 'rev3b']))
858
self.assertEqual(set(['rev3a', 'rev3b']),
859
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
861
def test_heads_shortcut(self):
862
graph = self.make_graph(history_shortcut)
864
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
865
graph.heads(['rev2a', 'rev2b', 'rev2c']))
866
self.assertEqual(set(['rev3a', 'rev3b']),
867
graph.heads(['rev3a', 'rev3b']))
868
self.assertEqual(set(['rev3a', 'rev3b']),
869
graph.heads(['rev2a', 'rev3a', 'rev3b']))
870
self.assertEqual(set(['rev2a', 'rev3b']),
871
graph.heads(['rev2a', 'rev3b']))
872
self.assertEqual(set(['rev2c', 'rev3a']),
873
graph.heads(['rev2c', 'rev3a']))
875
def _run_heads_break_deeper(self, graph_dict, search):
876
"""Run heads on a graph-as-a-dict.
878
If the search asks for the parents of 'deeper' the test will fail.
882
def get_parent_map(keys):
886
self.fail('key deeper was accessed')
887
result[key] = graph_dict[key]
890
an_obj.get_parent_map = get_parent_map
891
graph = _mod_graph.Graph(an_obj)
892
return graph.heads(search)
894
def test_heads_limits_search(self):
895
# test that a heads query does not search all of history
901
self.assertEqual(set(['left', 'right']),
902
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
904
def test_heads_limits_search_assymetric(self):
905
# test that a heads query does not search all of history
908
'midleft':['common'],
910
'common':['aftercommon'],
911
'aftercommon':['deeper'],
913
self.assertEqual(set(['left', 'right']),
914
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
916
def test_heads_limits_search_common_search_must_continue(self):
917
# test that common nodes are still queried, preventing
918
# all-the-way-to-origin behaviour in the following graph:
920
'h1':['shortcut', 'common1'],
922
'shortcut':['common2'],
923
'common1':['common2'],
924
'common2':['deeper'],
926
self.assertEqual(set(['h1', 'h2']),
927
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
929
def test_breadth_first_search_start_ghosts(self):
930
graph = self.make_graph({})
931
# with_ghosts reports the ghosts
932
search = graph._make_breadth_first_searcher(['a-ghost'])
933
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
934
self.assertRaises(StopIteration, search.next_with_ghosts)
936
search = graph._make_breadth_first_searcher(['a-ghost'])
937
self.assertEqual(set(['a-ghost']), search.next())
938
self.assertRaises(StopIteration, search.next)
940
def test_breadth_first_search_deep_ghosts(self):
941
graph = self.make_graph({
943
'present':['child', 'ghost'],
946
# with_ghosts reports the ghosts
947
search = graph._make_breadth_first_searcher(['head'])
948
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
949
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
950
self.assertEqual((set(['child']), set(['ghost'])),
951
search.next_with_ghosts())
952
self.assertRaises(StopIteration, search.next_with_ghosts)
954
search = graph._make_breadth_first_searcher(['head'])
955
self.assertEqual(set(['head']), search.next())
956
self.assertEqual(set(['present']), search.next())
957
self.assertEqual(set(['child', 'ghost']),
959
self.assertRaises(StopIteration, search.next)
961
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
962
# To make the API robust, we allow calling both next() and
963
# next_with_ghosts() on the same searcher.
964
graph = self.make_graph({
966
'present':['child', 'ghost'],
969
# start with next_with_ghosts
970
search = graph._make_breadth_first_searcher(['head'])
971
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
972
self.assertEqual(set(['present']), search.next())
973
self.assertEqual((set(['child']), set(['ghost'])),
974
search.next_with_ghosts())
975
self.assertRaises(StopIteration, search.next)
977
search = graph._make_breadth_first_searcher(['head'])
978
self.assertEqual(set(['head']), search.next())
979
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
980
self.assertEqual(set(['child', 'ghost']),
982
self.assertRaises(StopIteration, search.next_with_ghosts)
984
def test_breadth_first_change_search(self):
985
# Changing the search should work with both next and next_with_ghosts.
986
graph = self.make_graph({
988
'present':['stopped'],
992
search = graph._make_breadth_first_searcher(['head'])
993
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
994
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
995
self.assertEqual(set(['present']),
996
search.stop_searching_any(['present']))
997
self.assertEqual((set(['other']), set(['other_ghost'])),
998
search.start_searching(['other', 'other_ghost']))
999
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
1000
self.assertRaises(StopIteration, search.next_with_ghosts)
1001
# next includes them
1002
search = graph._make_breadth_first_searcher(['head'])
1003
self.assertEqual(set(['head']), search.next())
1004
self.assertEqual(set(['present']), search.next())
1005
self.assertEqual(set(['present']),
1006
search.stop_searching_any(['present']))
1007
search.start_searching(['other', 'other_ghost'])
1008
self.assertEqual(set(['other_2']), search.next())
1009
self.assertRaises(StopIteration, search.next)
1011
def assertSeenAndResult(self, instructions, search, next):
1012
"""Check the results of .seen and get_result() for a seach.
1014
:param instructions: A list of tuples:
1015
(seen, recipe, included_keys, starts, stops).
1016
seen, recipe and included_keys are results to check on the search
1017
and the searches get_result(). starts and stops are parameters to
1018
pass to start_searching and stop_searching_any during each
1019
iteration, if they are not None.
1020
:param search: The search to use.
1021
:param next: A callable to advance the search.
1023
for seen, recipe, included_keys, starts, stops in instructions:
1024
# Adjust for recipe contract changes that don't vary for all the
1026
recipe = ('search',) + recipe
1028
if starts is not None:
1029
search.start_searching(starts)
1030
if stops is not None:
1031
search.stop_searching_any(stops)
1032
state = search.get_state()
1033
self.assertEqual(set(included_keys), state[2])
1034
self.assertEqual(seen, search.seen)
1036
def test_breadth_first_get_result_excludes_current_pending(self):
1037
graph = self.make_graph({
1039
'child':[NULL_REVISION],
1042
search = graph._make_breadth_first_searcher(['head'])
1043
# At the start, nothing has been seen, to its all excluded:
1044
state = search.get_state()
1045
self.assertEqual((set(['head']), set(['head']), set()),
1047
self.assertEqual(set(), search.seen)
1050
(set(['head']), (set(['head']), set(['child']), 1),
1051
['head'], None, None),
1052
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
1053
['head', 'child'], None, None),
1054
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
1055
['head', 'child', NULL_REVISION], None, None),
1057
self.assertSeenAndResult(expected, search, search.next)
1058
# using next_with_ghosts:
1059
search = graph._make_breadth_first_searcher(['head'])
1060
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1062
def test_breadth_first_get_result_starts_stops(self):
1063
graph = self.make_graph({
1065
'child':[NULL_REVISION],
1066
'otherhead':['otherchild'],
1067
'otherchild':['excluded'],
1068
'excluded':[NULL_REVISION],
1071
search = graph._make_breadth_first_searcher([])
1072
# Starting with nothing and adding a search works:
1073
search.start_searching(['head'])
1074
# head has been seen:
1075
state = search.get_state()
1076
self.assertEqual((set(['head']), set(['child']), set(['head'])),
1078
self.assertEqual(set(['head']), search.seen)
1081
# stop at child, and start a new search at otherhead:
1082
# - otherhead counts as seen immediately when start_searching is
1084
(set(['head', 'child', 'otherhead']),
1085
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1086
['head', 'otherhead'], ['otherhead'], ['child']),
1087
(set(['head', 'child', 'otherhead', 'otherchild']),
1088
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1089
['head', 'otherhead', 'otherchild'], None, None),
1090
# stop searching excluded now
1091
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1092
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1093
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1095
self.assertSeenAndResult(expected, search, search.next)
1096
# using next_with_ghosts:
1097
search = graph._make_breadth_first_searcher([])
1098
search.start_searching(['head'])
1099
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1101
def test_breadth_first_stop_searching_not_queried(self):
1102
# A client should be able to say 'stop node X' even if X has not been
1103
# returned to the client.
1104
graph = self.make_graph({
1105
'head':['child', 'ghost1'],
1106
'child':[NULL_REVISION],
1109
search = graph._make_breadth_first_searcher(['head'])
1111
# NULL_REVISION and ghost1 have not been returned
1113
(set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1114
['head'], None, [NULL_REVISION, 'ghost1']),
1115
# ghost1 has been returned, NULL_REVISION is to be returned in the
1117
(set(['head', 'child', 'ghost1']),
1118
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1119
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1121
self.assertSeenAndResult(expected, search, search.next)
1122
# using next_with_ghosts:
1123
search = graph._make_breadth_first_searcher(['head'])
1124
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1126
def test_breadth_first_stop_searching_late(self):
1127
# A client should be able to say 'stop node X' and have it excluded
1128
# from the result even if X was seen in an older iteration of the
1130
graph = self.make_graph({
1133
'child':[NULL_REVISION],
1136
search = graph._make_breadth_first_searcher(['head'])
1138
(set(['head']), (set(['head']), set(['middle']), 1),
1139
['head'], None, None),
1140
(set(['head', 'middle']), (set(['head']), set(['child']), 2),
1141
['head', 'middle'], None, None),
1142
# 'middle' came from the previous iteration, but we don't stop
1143
# searching it until *after* advancing the searcher.
1144
(set(['head', 'middle', 'child']),
1145
(set(['head']), set(['middle', 'child']), 1),
1146
['head'], None, ['middle', 'child']),
1148
self.assertSeenAndResult(expected, search, search.next)
1149
# using next_with_ghosts:
1150
search = graph._make_breadth_first_searcher(['head'])
1151
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1153
def test_breadth_first_get_result_ghosts_are_excluded(self):
1154
graph = self.make_graph({
1155
'head':['child', 'ghost'],
1156
'child':[NULL_REVISION],
1159
search = graph._make_breadth_first_searcher(['head'])
1163
(set(['head']), set(['ghost', 'child']), 1),
1164
['head'], None, None),
1165
(set(['head', 'child', 'ghost']),
1166
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1167
['head', 'child'], None, None),
1169
self.assertSeenAndResult(expected, search, search.next)
1170
# using next_with_ghosts:
1171
search = graph._make_breadth_first_searcher(['head'])
1172
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1174
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1175
graph = self.make_graph({
1177
'child':[NULL_REVISION],
1180
search = graph._make_breadth_first_searcher(['head'])
1183
(set(['head', 'ghost']),
1184
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1185
['head'], ['ghost'], None),
1186
(set(['head', 'child', 'ghost']),
1187
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1188
['head', 'child'], None, None),
1190
self.assertSeenAndResult(expected, search, search.next)
1191
# using next_with_ghosts:
1192
search = graph._make_breadth_first_searcher(['head'])
1193
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1195
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1196
graph = self.make_graph({
1197
'head':[NULL_REVISION],
1200
search = graph._make_breadth_first_searcher(['head'])
1204
(set(['head']), set([NULL_REVISION]), 1),
1205
['head'], None, None),
1206
(set(['head', NULL_REVISION]),
1207
(set(['head']), set([]), 2),
1208
['head', NULL_REVISION], None, None),
1210
self.assertSeenAndResult(expected, search, search.next)
1211
# using next_with_ghosts:
1212
search = graph._make_breadth_first_searcher(['head'])
1213
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1215
def test_breadth_first_search_get_result_after_StopIteration(self):
1216
# StopIteration should not invalid anything..
1217
graph = self.make_graph({
1218
'head':[NULL_REVISION],
1221
search = graph._make_breadth_first_searcher(['head'])
1225
(set(['head']), set([NULL_REVISION]), 1),
1226
['head'], None, None),
1227
(set(['head', 'ghost', NULL_REVISION]),
1228
(set(['head', 'ghost']), set(['ghost']), 2),
1229
['head', NULL_REVISION], ['ghost'], None),
1231
self.assertSeenAndResult(expected, search, search.next)
1232
self.assertRaises(StopIteration, search.next)
1233
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1234
state = search.get_state()
1236
(set(['ghost', 'head']), set(['ghost']),
1237
set(['head', NULL_REVISION])),
1239
# using next_with_ghosts:
1240
search = graph._make_breadth_first_searcher(['head'])
1241
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1242
self.assertRaises(StopIteration, search.next)
1243
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1244
state = search.get_state()
1246
(set(['ghost', 'head']), set(['ghost']),
1247
set(['head', NULL_REVISION])),
1251
class TestFindUniqueAncestors(TestGraphBase):
1253
def assertFindUniqueAncestors(self, graph, expected, node, common):
1254
actual = graph.find_unique_ancestors(node, common)
1255
self.assertEqual(expected, sorted(actual))
1257
def test_empty_set(self):
1258
graph = self.make_graph(ancestry_1)
1259
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1260
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1261
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1263
def test_single_node(self):
1264
graph = self.make_graph(ancestry_1)
1265
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1266
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1267
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1269
def test_minimal_ancestry(self):
1270
graph = self.make_breaking_graph(extended_history_shortcut,
1271
[NULL_REVISION, 'a', 'b'])
1272
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1274
graph = self.make_breaking_graph(extended_history_shortcut,
1276
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1278
graph = self.make_breaking_graph(complex_shortcut,
1280
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1281
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1282
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1283
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1285
def test_in_ancestry(self):
1286
graph = self.make_graph(ancestry_1)
1287
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1288
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1290
def test_multiple_revisions(self):
1291
graph = self.make_graph(ancestry_1)
1292
self.assertFindUniqueAncestors(graph,
1293
['rev4'], 'rev4', ['rev3', 'rev2b'])
1294
self.assertFindUniqueAncestors(graph,
1295
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1297
def test_complex_shortcut(self):
1298
graph = self.make_graph(complex_shortcut)
1299
self.assertFindUniqueAncestors(graph,
1300
['h', 'n'], 'n', ['m'])
1301
self.assertFindUniqueAncestors(graph,
1302
['e', 'i', 'm'], 'm', ['n'])
1304
def test_complex_shortcut2(self):
1305
graph = self.make_graph(complex_shortcut2)
1306
self.assertFindUniqueAncestors(graph,
1307
['j', 'u'], 'u', ['t'])
1308
self.assertFindUniqueAncestors(graph,
1311
def test_multiple_interesting_unique(self):
1312
graph = self.make_graph(multiple_interesting_unique)
1313
self.assertFindUniqueAncestors(graph,
1314
['j', 'y'], 'y', ['z'])
1315
self.assertFindUniqueAncestors(graph,
1316
['p', 'z'], 'z', ['y'])
1318
def test_racing_shortcuts(self):
1319
graph = self.make_graph(racing_shortcuts)
1320
self.assertFindUniqueAncestors(graph,
1321
['p', 'q', 'z'], 'z', ['y'])
1322
self.assertFindUniqueAncestors(graph,
1323
['h', 'i', 'j', 'y'], 'j', ['z'])
1326
class TestGraphFindDistanceToNull(TestGraphBase):
1327
"""Test an api that should be able to compute a revno"""
1329
def assertFindDistance(self, revno, graph, target_id, known_ids):
1330
"""Assert the output of Graph.find_distance_to_null()"""
1331
actual = graph.find_distance_to_null(target_id, known_ids)
1332
self.assertEqual(revno, actual)
1334
def test_nothing_known(self):
1335
graph = self.make_graph(ancestry_1)
1336
self.assertFindDistance(0, graph, NULL_REVISION, [])
1337
self.assertFindDistance(1, graph, 'rev1', [])
1338
self.assertFindDistance(2, graph, 'rev2a', [])
1339
self.assertFindDistance(2, graph, 'rev2b', [])
1340
self.assertFindDistance(3, graph, 'rev3', [])
1341
self.assertFindDistance(4, graph, 'rev4', [])
1343
def test_rev_is_ghost(self):
1344
graph = self.make_graph(ancestry_1)
1345
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1346
graph.find_distance_to_null, 'rev_missing', [])
1347
self.assertEqual('rev_missing', e.revision_id)
1348
self.assertEqual('rev_missing', e.ghost_revision_id)
1350
def test_ancestor_is_ghost(self):
1351
graph = self.make_graph({'rev':['parent']})
1352
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1353
graph.find_distance_to_null, 'rev', [])
1354
self.assertEqual('rev', e.revision_id)
1355
self.assertEqual('parent', e.ghost_revision_id)
1357
def test_known_in_ancestry(self):
1358
graph = self.make_graph(ancestry_1)
1359
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1360
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1362
def test_known_in_ancestry_limits(self):
1363
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1364
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1366
def test_target_is_ancestor(self):
1367
graph = self.make_graph(ancestry_1)
1368
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1370
def test_target_is_ancestor_limits(self):
1371
"""We shouldn't search all history if we run into ourselves"""
1372
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1373
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1375
def test_target_parallel_to_known_limits(self):
1376
# Even though the known revision isn't part of the other ancestry, they
1377
# eventually converge
1378
graph = self.make_breaking_graph(with_tail, ['a'])
1379
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1380
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1381
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1382
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1385
class TestFindMergeOrder(TestGraphBase):
1387
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1388
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1390
def test_parents(self):
1391
graph = self.make_graph(ancestry_1)
1392
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1394
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1397
def test_ancestors(self):
1398
graph = self.make_graph(ancestry_1)
1399
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1401
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1404
def test_shortcut_one_ancestor(self):
1405
# When we have enough info, we can stop searching
1406
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1407
# Single ancestors shortcut right away
1408
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1410
def test_shortcut_after_one_ancestor(self):
1411
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1412
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1415
class TestFindDescendants(TestGraphBase):
1417
def test_find_descendants_rev1_rev3(self):
1418
graph = self.make_graph(ancestry_1)
1419
descendants = graph.find_descendants('rev1', 'rev3')
1420
self.assertEqual(set(['rev1', 'rev2a', 'rev3']), descendants)
1422
def test_find_descendants_rev1_rev4(self):
1423
graph = self.make_graph(ancestry_1)
1424
descendants = graph.find_descendants('rev1', 'rev4')
1425
self.assertEqual(set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']),
1428
def test_find_descendants_rev2a_rev4(self):
1429
graph = self.make_graph(ancestry_1)
1430
descendants = graph.find_descendants('rev2a', 'rev4')
1431
self.assertEqual(set(['rev2a', 'rev3', 'rev4']), descendants)
1433
class TestFindLefthandMerger(TestGraphBase):
1435
def check_merger(self, result, ancestry, merged, tip):
1436
graph = self.make_graph(ancestry)
1437
self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
1439
def test_find_lefthand_merger_rev2b(self):
1440
self.check_merger('rev4', ancestry_1, 'rev2b', 'rev4')
1442
def test_find_lefthand_merger_rev2a(self):
1443
self.check_merger('rev2a', ancestry_1, 'rev2a', 'rev4')
1445
def test_find_lefthand_merger_rev4(self):
1446
self.check_merger(None, ancestry_1, 'rev4', 'rev2a')
1448
def test_find_lefthand_merger_f(self):
1449
self.check_merger('i', complex_shortcut, 'f', 'm')
1451
def test_find_lefthand_merger_g(self):
1452
self.check_merger('i', complex_shortcut, 'g', 'm')
1454
def test_find_lefthand_merger_h(self):
1455
self.check_merger('n', complex_shortcut, 'h', 'n')
1458
class TestGetChildMap(TestGraphBase):
1460
def test_get_child_map(self):
1461
graph = self.make_graph(ancestry_1)
1462
child_map = graph.get_child_map(['rev4', 'rev3', 'rev2a', 'rev2b'])
1463
self.assertEqual({'rev1': ['rev2a', 'rev2b'],
1470
class TestCachingParentsProvider(tests.TestCase):
1471
"""These tests run with:
1473
self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1475
self.caching_pp, a CachingParentsProvider layered on inst_pp.
1479
super(TestCachingParentsProvider, self).setUp()
1480
dict_pp = _mod_graph.DictParentsProvider({'a': ('b',)})
1481
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1482
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1484
def test_get_parent_map(self):
1485
"""Requesting the same revision should be returned from cache"""
1486
self.assertEqual({}, self.caching_pp._cache)
1487
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1488
self.assertEqual(['a'], self.inst_pp.calls)
1489
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1490
# No new call, as it should have been returned from the cache
1491
self.assertEqual(['a'], self.inst_pp.calls)
1492
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1494
def test_get_parent_map_not_present(self):
1495
"""The cache should also track when a revision doesn't exist"""
1496
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1497
self.assertEqual(['b'], self.inst_pp.calls)
1498
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1500
self.assertEqual(['b'], self.inst_pp.calls)
1502
def test_get_parent_map_mixed(self):
1503
"""Anything that can be returned from cache, should be"""
1504
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1505
self.assertEqual(['b'], self.inst_pp.calls)
1506
self.assertEqual({'a':('b',)},
1507
self.caching_pp.get_parent_map(['a', 'b']))
1508
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1510
def test_get_parent_map_repeated(self):
1511
"""Asking for the same parent 2x will only forward 1 request."""
1512
self.assertEqual({'a':('b',)},
1513
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1514
# Use sorted because we don't care about the order, just that each is
1515
# only present 1 time.
1516
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1518
def test_note_missing_key(self):
1519
"""After noting that a key is missing it is cached."""
1520
self.caching_pp.note_missing_key('b')
1521
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1522
self.assertEqual([], self.inst_pp.calls)
1523
self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1525
def test_get_cached_parent_map(self):
1526
self.assertEqual({}, self.caching_pp.get_cached_parent_map(['a']))
1527
self.assertEqual([], self.inst_pp.calls)
1528
self.assertEqual({'a': ('b',)}, self.caching_pp.get_parent_map(['a']))
1529
self.assertEqual(['a'], self.inst_pp.calls)
1530
self.assertEqual({'a': ('b',)},
1531
self.caching_pp.get_cached_parent_map(['a']))
1534
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1535
"""Test the behaviour when parents are provided that were not requested."""
1538
super(TestCachingParentsProviderExtras, self).setUp()
1539
class ExtraParentsProvider(object):
1541
def get_parent_map(self, keys):
1542
return {'rev1': [], 'rev2': ['rev1',]}
1544
self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1545
self.caching_pp = _mod_graph.CachingParentsProvider(
1546
get_parent_map=self.inst_pp.get_parent_map)
1548
def test_uncached(self):
1549
self.caching_pp.disable_cache()
1550
self.assertEqual({'rev1': []},
1551
self.caching_pp.get_parent_map(['rev1']))
1552
self.assertEqual(['rev1'], self.inst_pp.calls)
1553
self.assertIs(None, self.caching_pp._cache)
1555
def test_cache_initially_empty(self):
1556
self.assertEqual({}, self.caching_pp._cache)
1558
def test_cached(self):
1559
self.assertEqual({'rev1': []},
1560
self.caching_pp.get_parent_map(['rev1']))
1561
self.assertEqual(['rev1'], self.inst_pp.calls)
1562
self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1563
self.caching_pp._cache)
1564
self.assertEqual({'rev1': []},
1565
self.caching_pp.get_parent_map(['rev1']))
1566
self.assertEqual(['rev1'], self.inst_pp.calls)
1568
def test_disable_cache_clears_cache(self):
1569
# Put something in the cache
1570
self.caching_pp.get_parent_map(['rev1'])
1571
self.assertEqual(2, len(self.caching_pp._cache))
1572
self.caching_pp.disable_cache()
1573
self.assertIs(None, self.caching_pp._cache)
1575
def test_enable_cache_raises(self):
1576
e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1577
self.assertEqual('Cache enabled when already enabled.', str(e))
1579
def test_cache_misses(self):
1580
self.caching_pp.get_parent_map(['rev3'])
1581
self.caching_pp.get_parent_map(['rev3'])
1582
self.assertEqual(['rev3'], self.inst_pp.calls)
1584
def test_no_cache_misses(self):
1585
self.caching_pp.disable_cache()
1586
self.caching_pp.enable_cache(cache_misses=False)
1587
self.caching_pp.get_parent_map(['rev3'])
1588
self.caching_pp.get_parent_map(['rev3'])
1589
self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1591
def test_cache_extras(self):
1592
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1593
self.assertEqual({'rev2': ['rev1']},
1594
self.caching_pp.get_parent_map(['rev2']))
1595
self.assertEqual(['rev3'], self.inst_pp.calls)
1597
def test_extras_using_cached(self):
1598
self.assertEqual({}, self.caching_pp.get_cached_parent_map(['rev3']))
1599
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1600
self.assertEqual({'rev2': ['rev1']},
1601
self.caching_pp.get_cached_parent_map(['rev2']))
1602
self.assertEqual(['rev3'], self.inst_pp.calls)
1606
class TestCollapseLinearRegions(tests.TestCase):
1608
def assertCollapsed(self, collapsed, original):
1609
self.assertEqual(collapsed,
1610
_mod_graph.collapse_linear_regions(original))
1612
def test_collapse_nothing(self):
1613
d = {1:[2, 3], 2:[], 3:[]}
1614
self.assertCollapsed(d, d)
1615
d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1616
self.assertCollapsed(d, d)
1618
def test_collapse_chain(self):
1619
# Any time we have a linear chain, we should be able to collapse
1620
d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1621
self.assertCollapsed({1:[5], 5:[]}, d)
1622
d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1623
self.assertCollapsed({5:[1], 1:[]}, d)
1624
d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1625
self.assertCollapsed({5:[2], 2:[]}, d)
1627
def test_collapse_with_multiple_children(self):
1638
# 4 and 5 cannot be removed because 6 has 2 children
1639
# 2 and 3 cannot be removed because 1 has 2 parents
1640
d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1641
self.assertCollapsed(d, d)
1644
class TestGraphThunkIdsToKeys(tests.TestCase):
1646
def test_heads(self):
1652
d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1653
('B',): [('A',)], ('A',): []}
1654
g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1655
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1656
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
1657
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
1658
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1659
self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1661
def test_add_node(self):
1662
d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1663
g = _mod_graph.KnownGraph(d)
1664
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1665
graph_thunk.add_node("D", ["A", "C"])
1666
self.assertEqual(['B', 'D'],
1667
sorted(graph_thunk.heads(['D', 'B', 'A'])))
1669
def test_merge_sort(self):
1670
d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1671
g = _mod_graph.KnownGraph(d)
1672
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1673
graph_thunk.add_node("D", ["A", "C"])
1674
self.assertEqual([('C', 0, (2,), False), ('A', 0, (1,), True)],
1675
[(n.key, n.merge_depth, n.revno, n.end_of_merge)
1676
for n in graph_thunk.merge_sort('C')])
1679
class TestStackedParentsProvider(tests.TestCase):
1682
super(TestStackedParentsProvider, self).setUp()
1685
def get_shared_provider(self, info, ancestry, has_cached):
1686
pp = _mod_graph.DictParentsProvider(ancestry)
1688
pp.get_cached_parent_map = pp.get_parent_map
1689
return SharedInstrumentedParentsProvider(pp, self.calls, info)
1691
def test_stacked_parents_provider(self):
1692
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
1693
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
1694
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1695
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
1696
stacked.get_parent_map(['rev1', 'rev2']))
1697
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
1698
stacked.get_parent_map(['rev2', 'rev1']))
1699
self.assertEqual({'rev2':['rev3']},
1700
stacked.get_parent_map(['rev2', 'rev2']))
1701
self.assertEqual({'rev1':['rev4']},
1702
stacked.get_parent_map(['rev1', 'rev1']))
1704
def test_stacked_parents_provider_overlapping(self):
1705
# rev2 is availible in both providers.
1709
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
1710
parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
1711
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1712
self.assertEqual({'rev2': ['rev1']},
1713
stacked.get_parent_map(['rev2']))
1715
def test_handles_no_get_cached_parent_map(self):
1716
# this shows that we both handle when a provider doesn't implement
1717
# get_cached_parent_map
1718
pp1 = self.get_shared_provider('pp1', {'rev2': ('rev1',)},
1720
pp2 = self.get_shared_provider('pp2', {'rev2': ('rev1',)},
1722
stacked = _mod_graph.StackedParentsProvider([pp1, pp2])
1723
self.assertEqual({'rev2': ('rev1',)}, stacked.get_parent_map(['rev2']))
1724
# No call on 'pp1' because it doesn't provide get_cached_parent_map
1725
self.assertEqual([('pp2', 'cached', ['rev2'])], self.calls)
1727
def test_query_order(self):
1728
# We should call get_cached_parent_map on all providers before we call
1729
# get_parent_map. Further, we should track what entries we have found,
1730
# and not re-try them.
1731
pp1 = self.get_shared_provider('pp1', {'a': ()}, has_cached=True)
1732
pp2 = self.get_shared_provider('pp2', {'c': ('b',)}, has_cached=False)
1733
pp3 = self.get_shared_provider('pp3', {'b': ('a',)}, has_cached=True)
1734
stacked = _mod_graph.StackedParentsProvider([pp1, pp2, pp3])
1735
self.assertEqual({'a': (), 'b': ('a',), 'c': ('b',)},
1736
stacked.get_parent_map(['a', 'b', 'c', 'd']))
1737
self.assertEqual([('pp1', 'cached', ['a', 'b', 'c', 'd']),
1738
# No call to pp2, because it doesn't have cached
1739
('pp3', 'cached', ['b', 'c', 'd']),
1740
('pp1', ['c', 'd']),
1741
('pp2', ['c', 'd']),
added
removed
bzrlib/tests/test_graph.py
