886
681
self.assertEqual(set(['h1', 'h2']),
887
682
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
889
def test_breadth_first_search_start_ghosts(self):
890
graph = self.make_graph({})
891
# with_ghosts reports the ghosts
892
search = graph._make_breadth_first_searcher(['a-ghost'])
893
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
894
self.assertRaises(StopIteration, search.next_with_ghosts)
896
search = graph._make_breadth_first_searcher(['a-ghost'])
897
self.assertEqual(set(['a-ghost']), search.next())
898
self.assertRaises(StopIteration, search.next)
900
def test_breadth_first_search_deep_ghosts(self):
901
graph = self.make_graph({
903
'present':['child', 'ghost'],
906
# with_ghosts reports the ghosts
907
search = graph._make_breadth_first_searcher(['head'])
908
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
909
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
910
self.assertEqual((set(['child']), set(['ghost'])),
911
search.next_with_ghosts())
912
self.assertRaises(StopIteration, search.next_with_ghosts)
914
search = graph._make_breadth_first_searcher(['head'])
915
self.assertEqual(set(['head']), search.next())
916
self.assertEqual(set(['present']), search.next())
917
self.assertEqual(set(['child', 'ghost']),
919
self.assertRaises(StopIteration, search.next)
921
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
922
# To make the API robust, we allow calling both next() and
923
# next_with_ghosts() on the same searcher.
924
graph = self.make_graph({
926
'present':['child', 'ghost'],
929
# start with next_with_ghosts
930
search = graph._make_breadth_first_searcher(['head'])
931
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
932
self.assertEqual(set(['present']), search.next())
933
self.assertEqual((set(['child']), set(['ghost'])),
934
search.next_with_ghosts())
935
self.assertRaises(StopIteration, search.next)
937
search = graph._make_breadth_first_searcher(['head'])
938
self.assertEqual(set(['head']), search.next())
939
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
940
self.assertEqual(set(['child', 'ghost']),
942
self.assertRaises(StopIteration, search.next_with_ghosts)
944
def test_breadth_first_change_search(self):
945
# Changing the search should work with both next and next_with_ghosts.
946
graph = self.make_graph({
948
'present':['stopped'],
952
search = graph._make_breadth_first_searcher(['head'])
953
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
954
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
955
self.assertEqual(set(['present']),
956
search.stop_searching_any(['present']))
957
self.assertEqual((set(['other']), set(['other_ghost'])),
958
search.start_searching(['other', 'other_ghost']))
959
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
960
self.assertRaises(StopIteration, search.next_with_ghosts)
962
search = graph._make_breadth_first_searcher(['head'])
963
self.assertEqual(set(['head']), search.next())
964
self.assertEqual(set(['present']), search.next())
965
self.assertEqual(set(['present']),
966
search.stop_searching_any(['present']))
967
search.start_searching(['other', 'other_ghost'])
968
self.assertEqual(set(['other_2']), search.next())
969
self.assertRaises(StopIteration, search.next)
971
def assertSeenAndResult(self, instructions, search, next):
972
"""Check the results of .seen and get_result() for a seach.
974
:param instructions: A list of tuples:
975
(seen, recipe, included_keys, starts, stops).
976
seen, recipe and included_keys are results to check on the search
977
and the searches get_result(). starts and stops are parameters to
978
pass to start_searching and stop_searching_any during each
979
iteration, if they are not None.
980
:param search: The search to use.
981
:param next: A callable to advance the search.
983
for seen, recipe, included_keys, starts, stops in instructions:
985
if starts is not None:
986
search.start_searching(starts)
987
if stops is not None:
988
search.stop_searching_any(stops)
989
result = search.get_result()
990
self.assertEqual(recipe, result.get_recipe())
991
self.assertEqual(set(included_keys), result.get_keys())
992
self.assertEqual(seen, search.seen)
994
def test_breadth_first_get_result_excludes_current_pending(self):
995
graph = self.make_graph({
997
'child':[NULL_REVISION],
1000
search = graph._make_breadth_first_searcher(['head'])
1001
# At the start, nothing has been seen, to its all excluded:
1002
result = search.get_result()
1003
self.assertEqual((set(['head']), set(['head']), 0),
1004
result.get_recipe())
1005
self.assertEqual(set(), result.get_keys())
1006
self.assertEqual(set(), search.seen)
1009
(set(['head']), (set(['head']), set(['child']), 1),
1010
['head'], None, None),
1011
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
1012
['head', 'child'], None, None),
1013
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
1014
['head', 'child', NULL_REVISION], None, None),
1016
self.assertSeenAndResult(expected, search, search.next)
1017
# using next_with_ghosts:
1018
search = graph._make_breadth_first_searcher(['head'])
1019
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1021
def test_breadth_first_get_result_starts_stops(self):
1022
graph = self.make_graph({
1024
'child':[NULL_REVISION],
1025
'otherhead':['otherchild'],
1026
'otherchild':['excluded'],
1027
'excluded':[NULL_REVISION],
1030
search = graph._make_breadth_first_searcher([])
1031
# Starting with nothing and adding a search works:
1032
search.start_searching(['head'])
1033
# head has been seen:
1034
result = search.get_result()
1035
self.assertEqual((set(['head']), set(['child']), 1),
1036
result.get_recipe())
1037
self.assertEqual(set(['head']), result.get_keys())
1038
self.assertEqual(set(['head']), search.seen)
1041
# stop at child, and start a new search at otherhead:
1042
# - otherhead counts as seen immediately when start_searching is
1044
(set(['head', 'child', 'otherhead']),
1045
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1046
['head', 'otherhead'], ['otherhead'], ['child']),
1047
(set(['head', 'child', 'otherhead', 'otherchild']),
1048
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1049
['head', 'otherhead', 'otherchild'], None, None),
1050
# stop searching excluded now
1051
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1052
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1053
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1055
self.assertSeenAndResult(expected, search, search.next)
1056
# using next_with_ghosts:
1057
search = graph._make_breadth_first_searcher([])
1058
search.start_searching(['head'])
1059
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1061
def test_breadth_first_stop_searching_not_queried(self):
1062
# A client should be able to say 'stop node X' even if X has not been
1063
# returned to the client.
1064
graph = self.make_graph({
1065
'head':['child', 'ghost1'],
1066
'child':[NULL_REVISION],
1069
search = graph._make_breadth_first_searcher(['head'])
1071
# NULL_REVISION and ghost1 have not been returned
1072
(set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
1073
['head'], None, [NULL_REVISION, 'ghost1']),
1074
# ghost1 has been returned, NULL_REVISION is to be returned in the
1076
(set(['head', 'child', 'ghost1']),
1077
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1078
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1080
self.assertSeenAndResult(expected, search, search.next)
1081
# using next_with_ghosts:
1082
search = graph._make_breadth_first_searcher(['head'])
1083
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1085
def test_breadth_first_get_result_ghosts_are_excluded(self):
1086
graph = self.make_graph({
1087
'head':['child', 'ghost'],
1088
'child':[NULL_REVISION],
1091
search = graph._make_breadth_first_searcher(['head'])
1095
(set(['head']), set(['ghost', 'child']), 1),
1096
['head'], None, None),
1097
(set(['head', 'child', 'ghost']),
1098
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1099
['head', 'child'], None, None),
1101
self.assertSeenAndResult(expected, search, search.next)
1102
# using next_with_ghosts:
1103
search = graph._make_breadth_first_searcher(['head'])
1104
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1106
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1107
graph = self.make_graph({
1109
'child':[NULL_REVISION],
1112
search = graph._make_breadth_first_searcher(['head'])
1115
(set(['head', 'ghost']),
1116
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1117
['head'], ['ghost'], None),
1118
(set(['head', 'child', 'ghost']),
1119
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1120
['head', 'child'], None, None),
1122
self.assertSeenAndResult(expected, search, search.next)
1123
# using next_with_ghosts:
1124
search = graph._make_breadth_first_searcher(['head'])
1125
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1127
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1128
graph = self.make_graph({
1129
'head':[NULL_REVISION],
1132
search = graph._make_breadth_first_searcher(['head'])
1136
(set(['head']), set([NULL_REVISION]), 1),
1137
['head'], None, None),
1138
(set(['head', NULL_REVISION]),
1139
(set(['head']), set([]), 2),
1140
['head', NULL_REVISION], None, None),
1142
self.assertSeenAndResult(expected, search, search.next)
1143
# using next_with_ghosts:
1144
search = graph._make_breadth_first_searcher(['head'])
1145
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1147
def test_breadth_first_search_get_result_after_StopIteration(self):
1148
# StopIteration should not invalid anything..
1149
graph = self.make_graph({
1150
'head':[NULL_REVISION],
1153
search = graph._make_breadth_first_searcher(['head'])
1157
(set(['head']), set([NULL_REVISION]), 1),
1158
['head'], None, None),
1159
(set(['head', 'ghost', NULL_REVISION]),
1160
(set(['head', 'ghost']), set(['ghost']), 2),
1161
['head', NULL_REVISION], ['ghost'], None),
1163
self.assertSeenAndResult(expected, search, search.next)
1164
self.assertRaises(StopIteration, search.next)
1165
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1166
result = search.get_result()
1167
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1168
result.get_recipe())
1169
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1170
# using next_with_ghosts:
1171
search = graph._make_breadth_first_searcher(['head'])
1172
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1173
self.assertRaises(StopIteration, search.next)
1174
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1175
result = search.get_result()
1176
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1177
result.get_recipe())
1178
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1181
class TestFindUniqueAncestors(TestGraphBase):
1183
def assertFindUniqueAncestors(self, graph, expected, node, common):
1184
actual = graph.find_unique_ancestors(node, common)
1185
self.assertEqual(expected, sorted(actual))
1187
def test_empty_set(self):
1188
graph = self.make_graph(ancestry_1)
1189
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1190
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1191
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1193
def test_single_node(self):
1194
graph = self.make_graph(ancestry_1)
1195
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1196
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1197
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1199
def test_minimal_ancestry(self):
1200
graph = self.make_breaking_graph(extended_history_shortcut,
1201
[NULL_REVISION, 'a', 'b'])
1202
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1204
graph = self.make_breaking_graph(extended_history_shortcut,
1206
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1208
graph = self.make_breaking_graph(complex_shortcut,
1210
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1211
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1212
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1213
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1215
def test_in_ancestry(self):
1216
graph = self.make_graph(ancestry_1)
1217
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1218
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1220
def test_multiple_revisions(self):
1221
graph = self.make_graph(ancestry_1)
1222
self.assertFindUniqueAncestors(graph,
1223
['rev4'], 'rev4', ['rev3', 'rev2b'])
1224
self.assertFindUniqueAncestors(graph,
1225
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1227
def test_complex_shortcut(self):
1228
graph = self.make_graph(complex_shortcut)
1229
self.assertFindUniqueAncestors(graph,
1230
['h', 'n'], 'n', ['m'])
1231
self.assertFindUniqueAncestors(graph,
1232
['e', 'i', 'm'], 'm', ['n'])
1234
def test_complex_shortcut2(self):
1235
graph = self.make_graph(complex_shortcut2)
1236
self.assertFindUniqueAncestors(graph,
1237
['j', 'u'], 'u', ['t'])
1238
self.assertFindUniqueAncestors(graph,
1241
def test_multiple_interesting_unique(self):
1242
graph = self.make_graph(multiple_interesting_unique)
1243
self.assertFindUniqueAncestors(graph,
1244
['j', 'y'], 'y', ['z'])
1245
self.assertFindUniqueAncestors(graph,
1246
['p', 'z'], 'z', ['y'])
1248
def test_racing_shortcuts(self):
1249
graph = self.make_graph(racing_shortcuts)
1250
self.assertFindUniqueAncestors(graph,
1251
['p', 'q', 'z'], 'z', ['y'])
1252
self.assertFindUniqueAncestors(graph,
1253
['h', 'i', 'j', 'y'], 'j', ['z'])
1256
class TestGraphFindDistanceToNull(TestGraphBase):
1257
"""Test an api that should be able to compute a revno"""
1259
def assertFindDistance(self, revno, graph, target_id, known_ids):
1260
"""Assert the output of Graph.find_distance_to_null()"""
1261
actual = graph.find_distance_to_null(target_id, known_ids)
1262
self.assertEqual(revno, actual)
1264
def test_nothing_known(self):
1265
graph = self.make_graph(ancestry_1)
1266
self.assertFindDistance(0, graph, NULL_REVISION, [])
1267
self.assertFindDistance(1, graph, 'rev1', [])
1268
self.assertFindDistance(2, graph, 'rev2a', [])
1269
self.assertFindDistance(2, graph, 'rev2b', [])
1270
self.assertFindDistance(3, graph, 'rev3', [])
1271
self.assertFindDistance(4, graph, 'rev4', [])
1273
def test_rev_is_ghost(self):
1274
graph = self.make_graph(ancestry_1)
1275
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1276
graph.find_distance_to_null, 'rev_missing', [])
1277
self.assertEqual('rev_missing', e.revision_id)
1278
self.assertEqual('rev_missing', e.ghost_revision_id)
1280
def test_ancestor_is_ghost(self):
1281
graph = self.make_graph({'rev':['parent']})
1282
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1283
graph.find_distance_to_null, 'rev', [])
1284
self.assertEqual('rev', e.revision_id)
1285
self.assertEqual('parent', e.ghost_revision_id)
1287
def test_known_in_ancestry(self):
1288
graph = self.make_graph(ancestry_1)
1289
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1290
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1292
def test_known_in_ancestry_limits(self):
1293
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1294
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1296
def test_target_is_ancestor(self):
1297
graph = self.make_graph(ancestry_1)
1298
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1300
def test_target_is_ancestor_limits(self):
1301
"""We shouldn't search all history if we run into ourselves"""
1302
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1303
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1305
def test_target_parallel_to_known_limits(self):
1306
# Even though the known revision isn't part of the other ancestry, they
1307
# eventually converge
1308
graph = self.make_breaking_graph(with_tail, ['a'])
1309
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1310
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1311
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1312
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1315
class TestFindMergeOrder(TestGraphBase):
1317
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1318
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1320
def test_parents(self):
1321
graph = self.make_graph(ancestry_1)
1322
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1324
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1327
def test_ancestors(self):
1328
graph = self.make_graph(ancestry_1)
1329
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1331
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1334
def test_shortcut_one_ancestor(self):
1335
# When we have enough info, we can stop searching
1336
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1337
# Single ancestors shortcut right away
1338
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1340
def test_shortcut_after_one_ancestor(self):
1341
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1342
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1345
685
class TestCachingParentsProvider(tests.TestCase):
added
removed
bzrlib/tests/test_graph.py
