897
652
self.assertEqual(set(['h1', 'h2']),
898
653
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
900
def test_breadth_first_search_start_ghosts(self):
901
graph = self.make_graph({})
902
# with_ghosts reports the ghosts
903
search = graph._make_breadth_first_searcher(['a-ghost'])
904
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
905
self.assertRaises(StopIteration, search.next_with_ghosts)
907
search = graph._make_breadth_first_searcher(['a-ghost'])
908
self.assertEqual(set(['a-ghost']), search.next())
909
self.assertRaises(StopIteration, search.next)
911
def test_breadth_first_search_deep_ghosts(self):
912
graph = self.make_graph({
914
'present':['child', 'ghost'],
917
# with_ghosts reports the ghosts
918
search = graph._make_breadth_first_searcher(['head'])
919
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
920
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
921
self.assertEqual((set(['child']), set(['ghost'])),
922
search.next_with_ghosts())
923
self.assertRaises(StopIteration, search.next_with_ghosts)
925
search = graph._make_breadth_first_searcher(['head'])
926
self.assertEqual(set(['head']), search.next())
927
self.assertEqual(set(['present']), search.next())
928
self.assertEqual(set(['child', 'ghost']),
930
self.assertRaises(StopIteration, search.next)
932
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
933
# To make the API robust, we allow calling both next() and
934
# next_with_ghosts() on the same searcher.
935
graph = self.make_graph({
937
'present':['child', 'ghost'],
940
# start with next_with_ghosts
941
search = graph._make_breadth_first_searcher(['head'])
942
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
943
self.assertEqual(set(['present']), search.next())
944
self.assertEqual((set(['child']), set(['ghost'])),
945
search.next_with_ghosts())
946
self.assertRaises(StopIteration, search.next)
948
search = graph._make_breadth_first_searcher(['head'])
949
self.assertEqual(set(['head']), search.next())
950
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
951
self.assertEqual(set(['child', 'ghost']),
953
self.assertRaises(StopIteration, search.next_with_ghosts)
955
def test_breadth_first_change_search(self):
956
# Changing the search should work with both next and next_with_ghosts.
957
graph = self.make_graph({
959
'present':['stopped'],
963
search = graph._make_breadth_first_searcher(['head'])
964
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
965
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
966
self.assertEqual(set(['present']),
967
search.stop_searching_any(['present']))
968
self.assertEqual((set(['other']), set(['other_ghost'])),
969
search.start_searching(['other', 'other_ghost']))
970
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
971
self.assertRaises(StopIteration, search.next_with_ghosts)
973
search = graph._make_breadth_first_searcher(['head'])
974
self.assertEqual(set(['head']), search.next())
975
self.assertEqual(set(['present']), search.next())
976
self.assertEqual(set(['present']),
977
search.stop_searching_any(['present']))
978
search.start_searching(['other', 'other_ghost'])
979
self.assertEqual(set(['other_2']), search.next())
980
self.assertRaises(StopIteration, search.next)
982
def assertSeenAndResult(self, instructions, search, next):
983
"""Check the results of .seen and get_result() for a seach.
985
:param instructions: A list of tuples:
986
(seen, recipe, included_keys, starts, stops).
987
seen, recipe and included_keys are results to check on the search
988
and the searches get_result(). starts and stops are parameters to
989
pass to start_searching and stop_searching_any during each
990
iteration, if they are not None.
991
:param search: The search to use.
992
:param next: A callable to advance the search.
994
for seen, recipe, included_keys, starts, stops in instructions:
995
# Adjust for recipe contract changes that don't vary for all the
997
recipe = ('search',) + recipe
999
if starts is not None:
1000
search.start_searching(starts)
1001
if stops is not None:
1002
search.stop_searching_any(stops)
1003
result = search.get_result()
1004
self.assertEqual(recipe, result.get_recipe())
1005
self.assertEqual(set(included_keys), result.get_keys())
1006
self.assertEqual(seen, search.seen)
1008
def test_breadth_first_get_result_excludes_current_pending(self):
1009
graph = self.make_graph({
1011
'child':[NULL_REVISION],
1014
search = graph._make_breadth_first_searcher(['head'])
1015
# At the start, nothing has been seen, to its all excluded:
1016
result = search.get_result()
1017
self.assertEqual(('search', set(['head']), set(['head']), 0),
1018
result.get_recipe())
1019
self.assertEqual(set(), result.get_keys())
1020
self.assertEqual(set(), search.seen)
1023
(set(['head']), (set(['head']), set(['child']), 1),
1024
['head'], None, None),
1025
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
1026
['head', 'child'], None, None),
1027
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
1028
['head', 'child', NULL_REVISION], None, None),
1030
self.assertSeenAndResult(expected, search, search.next)
1031
# using next_with_ghosts:
1032
search = graph._make_breadth_first_searcher(['head'])
1033
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1035
def test_breadth_first_get_result_starts_stops(self):
1036
graph = self.make_graph({
1038
'child':[NULL_REVISION],
1039
'otherhead':['otherchild'],
1040
'otherchild':['excluded'],
1041
'excluded':[NULL_REVISION],
1044
search = graph._make_breadth_first_searcher([])
1045
# Starting with nothing and adding a search works:
1046
search.start_searching(['head'])
1047
# head has been seen:
1048
result = search.get_result()
1049
self.assertEqual(('search', set(['head']), set(['child']), 1),
1050
result.get_recipe())
1051
self.assertEqual(set(['head']), result.get_keys())
1052
self.assertEqual(set(['head']), search.seen)
1055
# stop at child, and start a new search at otherhead:
1056
# - otherhead counts as seen immediately when start_searching is
1058
(set(['head', 'child', 'otherhead']),
1059
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1060
['head', 'otherhead'], ['otherhead'], ['child']),
1061
(set(['head', 'child', 'otherhead', 'otherchild']),
1062
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1063
['head', 'otherhead', 'otherchild'], None, None),
1064
# stop searching excluded now
1065
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1066
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1067
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1069
self.assertSeenAndResult(expected, search, search.next)
1070
# using next_with_ghosts:
1071
search = graph._make_breadth_first_searcher([])
1072
search.start_searching(['head'])
1073
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1075
def test_breadth_first_stop_searching_not_queried(self):
1076
# A client should be able to say 'stop node X' even if X has not been
1077
# returned to the client.
1078
graph = self.make_graph({
1079
'head':['child', 'ghost1'],
1080
'child':[NULL_REVISION],
1083
search = graph._make_breadth_first_searcher(['head'])
1085
# NULL_REVISION and ghost1 have not been returned
1087
(set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1088
['head'], None, [NULL_REVISION, 'ghost1']),
1089
# ghost1 has been returned, NULL_REVISION is to be returned in the
1091
(set(['head', 'child', 'ghost1']),
1092
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1093
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1095
self.assertSeenAndResult(expected, search, search.next)
1096
# using next_with_ghosts:
1097
search = graph._make_breadth_first_searcher(['head'])
1098
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1100
def test_breadth_first_stop_searching_late(self):
1101
# A client should be able to say 'stop node X' and have it excluded
1102
# from the result even if X was seen in an older iteration of the
1104
graph = self.make_graph({
1107
'child':[NULL_REVISION],
1110
search = graph._make_breadth_first_searcher(['head'])
1112
(set(['head']), (set(['head']), set(['middle']), 1),
1113
['head'], None, None),
1114
(set(['head', 'middle']), (set(['head']), set(['child']), 2),
1115
['head', 'middle'], None, None),
1116
# 'middle' came from the previous iteration, but we don't stop
1117
# searching it until *after* advancing the searcher.
1118
(set(['head', 'middle', 'child']),
1119
(set(['head']), set(['middle', 'child']), 1),
1120
['head'], None, ['middle', 'child']),
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_get_result_ghosts_are_excluded(self):
1128
graph = self.make_graph({
1129
'head':['child', 'ghost'],
1130
'child':[NULL_REVISION],
1133
search = graph._make_breadth_first_searcher(['head'])
1137
(set(['head']), set(['ghost', 'child']), 1),
1138
['head'], None, None),
1139
(set(['head', 'child', 'ghost']),
1140
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1141
['head', 'child'], None, None),
1143
self.assertSeenAndResult(expected, search, search.next)
1144
# using next_with_ghosts:
1145
search = graph._make_breadth_first_searcher(['head'])
1146
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1148
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1149
graph = self.make_graph({
1151
'child':[NULL_REVISION],
1154
search = graph._make_breadth_first_searcher(['head'])
1157
(set(['head', 'ghost']),
1158
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1159
['head'], ['ghost'], None),
1160
(set(['head', 'child', 'ghost']),
1161
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1162
['head', 'child'], None, None),
1164
self.assertSeenAndResult(expected, search, search.next)
1165
# using next_with_ghosts:
1166
search = graph._make_breadth_first_searcher(['head'])
1167
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1169
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1170
graph = self.make_graph({
1171
'head':[NULL_REVISION],
1174
search = graph._make_breadth_first_searcher(['head'])
1178
(set(['head']), set([NULL_REVISION]), 1),
1179
['head'], None, None),
1180
(set(['head', NULL_REVISION]),
1181
(set(['head']), set([]), 2),
1182
['head', NULL_REVISION], None, None),
1184
self.assertSeenAndResult(expected, search, search.next)
1185
# using next_with_ghosts:
1186
search = graph._make_breadth_first_searcher(['head'])
1187
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1189
def test_breadth_first_search_get_result_after_StopIteration(self):
1190
# StopIteration should not invalid anything..
1191
graph = self.make_graph({
1192
'head':[NULL_REVISION],
1195
search = graph._make_breadth_first_searcher(['head'])
1199
(set(['head']), set([NULL_REVISION]), 1),
1200
['head'], None, None),
1201
(set(['head', 'ghost', NULL_REVISION]),
1202
(set(['head', 'ghost']), set(['ghost']), 2),
1203
['head', NULL_REVISION], ['ghost'], None),
1205
self.assertSeenAndResult(expected, search, search.next)
1206
self.assertRaises(StopIteration, search.next)
1207
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1208
result = search.get_result()
1209
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1210
result.get_recipe())
1211
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1212
# using next_with_ghosts:
1213
search = graph._make_breadth_first_searcher(['head'])
1214
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1215
self.assertRaises(StopIteration, search.next)
1216
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1217
result = search.get_result()
1218
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1219
result.get_recipe())
1220
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1223
class TestFindUniqueAncestors(TestGraphBase):
1225
def assertFindUniqueAncestors(self, graph, expected, node, common):
1226
actual = graph.find_unique_ancestors(node, common)
1227
self.assertEqual(expected, sorted(actual))
1229
def test_empty_set(self):
1230
graph = self.make_graph(ancestry_1)
1231
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1232
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1233
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1235
def test_single_node(self):
1236
graph = self.make_graph(ancestry_1)
1237
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1238
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1239
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1241
def test_minimal_ancestry(self):
1242
graph = self.make_breaking_graph(extended_history_shortcut,
1243
[NULL_REVISION, 'a', 'b'])
1244
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1246
graph = self.make_breaking_graph(extended_history_shortcut,
1248
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1250
graph = self.make_breaking_graph(complex_shortcut,
1252
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1253
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1254
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1255
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1257
def test_in_ancestry(self):
1258
graph = self.make_graph(ancestry_1)
1259
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1260
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1262
def test_multiple_revisions(self):
1263
graph = self.make_graph(ancestry_1)
1264
self.assertFindUniqueAncestors(graph,
1265
['rev4'], 'rev4', ['rev3', 'rev2b'])
1266
self.assertFindUniqueAncestors(graph,
1267
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1269
def test_complex_shortcut(self):
1270
graph = self.make_graph(complex_shortcut)
1271
self.assertFindUniqueAncestors(graph,
1272
['h', 'n'], 'n', ['m'])
1273
self.assertFindUniqueAncestors(graph,
1274
['e', 'i', 'm'], 'm', ['n'])
1276
def test_complex_shortcut2(self):
1277
graph = self.make_graph(complex_shortcut2)
1278
self.assertFindUniqueAncestors(graph,
1279
['j', 'u'], 'u', ['t'])
1280
self.assertFindUniqueAncestors(graph,
1283
def test_multiple_interesting_unique(self):
1284
graph = self.make_graph(multiple_interesting_unique)
1285
self.assertFindUniqueAncestors(graph,
1286
['j', 'y'], 'y', ['z'])
1287
self.assertFindUniqueAncestors(graph,
1288
['p', 'z'], 'z', ['y'])
1290
def test_racing_shortcuts(self):
1291
graph = self.make_graph(racing_shortcuts)
1292
self.assertFindUniqueAncestors(graph,
1293
['p', 'q', 'z'], 'z', ['y'])
1294
self.assertFindUniqueAncestors(graph,
1295
['h', 'i', 'j', 'y'], 'j', ['z'])
1298
class TestGraphFindDistanceToNull(TestGraphBase):
1299
"""Test an api that should be able to compute a revno"""
1301
def assertFindDistance(self, revno, graph, target_id, known_ids):
1302
"""Assert the output of Graph.find_distance_to_null()"""
1303
actual = graph.find_distance_to_null(target_id, known_ids)
1304
self.assertEqual(revno, actual)
1306
def test_nothing_known(self):
1307
graph = self.make_graph(ancestry_1)
1308
self.assertFindDistance(0, graph, NULL_REVISION, [])
1309
self.assertFindDistance(1, graph, 'rev1', [])
1310
self.assertFindDistance(2, graph, 'rev2a', [])
1311
self.assertFindDistance(2, graph, 'rev2b', [])
1312
self.assertFindDistance(3, graph, 'rev3', [])
1313
self.assertFindDistance(4, graph, 'rev4', [])
1315
def test_rev_is_ghost(self):
1316
graph = self.make_graph(ancestry_1)
1317
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1318
graph.find_distance_to_null, 'rev_missing', [])
1319
self.assertEqual('rev_missing', e.revision_id)
1320
self.assertEqual('rev_missing', e.ghost_revision_id)
1322
def test_ancestor_is_ghost(self):
1323
graph = self.make_graph({'rev':['parent']})
1324
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1325
graph.find_distance_to_null, 'rev', [])
1326
self.assertEqual('rev', e.revision_id)
1327
self.assertEqual('parent', e.ghost_revision_id)
1329
def test_known_in_ancestry(self):
1330
graph = self.make_graph(ancestry_1)
1331
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1332
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1334
def test_known_in_ancestry_limits(self):
1335
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1336
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1338
def test_target_is_ancestor(self):
1339
graph = self.make_graph(ancestry_1)
1340
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1342
def test_target_is_ancestor_limits(self):
1343
"""We shouldn't search all history if we run into ourselves"""
1344
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1345
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1347
def test_target_parallel_to_known_limits(self):
1348
# Even though the known revision isn't part of the other ancestry, they
1349
# eventually converge
1350
graph = self.make_breaking_graph(with_tail, ['a'])
1351
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1352
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1353
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1354
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1357
class TestFindMergeOrder(TestGraphBase):
1359
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1360
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1362
def test_parents(self):
1363
graph = self.make_graph(ancestry_1)
1364
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1366
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1369
def test_ancestors(self):
1370
graph = self.make_graph(ancestry_1)
1371
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1373
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1376
def test_shortcut_one_ancestor(self):
1377
# When we have enough info, we can stop searching
1378
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1379
# Single ancestors shortcut right away
1380
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1382
def test_shortcut_after_one_ancestor(self):
1383
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1384
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1387
656
class TestCachingParentsProvider(tests.TestCase):
1388
"""These tests run with:
1390
self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1392
self.caching_pp, a CachingParentsProvider layered on inst_pp.
1395
658
def setUp(self):
1396
659
super(TestCachingParentsProvider, self).setUp()
1431
695
# Use sorted because we don't care about the order, just that each is
1432
696
# only present 1 time.
1433
697
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1435
def test_note_missing_key(self):
1436
"""After noting that a key is missing it is cached."""
1437
self.caching_pp.note_missing_key('b')
1438
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1439
self.assertEqual([], self.inst_pp.calls)
1440
self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1443
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1444
"""Test the behaviour when parents are provided that were not requested."""
1447
super(TestCachingParentsProviderExtras, self).setUp()
1448
class ExtraParentsProvider(object):
1450
def get_parent_map(self, keys):
1451
return {'rev1': [], 'rev2': ['rev1',]}
1453
self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1454
self.caching_pp = _mod_graph.CachingParentsProvider(
1455
get_parent_map=self.inst_pp.get_parent_map)
1457
def test_uncached(self):
1458
self.caching_pp.disable_cache()
1459
self.assertEqual({'rev1': []},
1460
self.caching_pp.get_parent_map(['rev1']))
1461
self.assertEqual(['rev1'], self.inst_pp.calls)
1462
self.assertIs(None, self.caching_pp._cache)
1464
def test_cache_initially_empty(self):
1465
self.assertEqual({}, self.caching_pp._cache)
1467
def test_cached(self):
1468
self.assertEqual({'rev1': []},
1469
self.caching_pp.get_parent_map(['rev1']))
1470
self.assertEqual(['rev1'], self.inst_pp.calls)
1471
self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1472
self.caching_pp._cache)
1473
self.assertEqual({'rev1': []},
1474
self.caching_pp.get_parent_map(['rev1']))
1475
self.assertEqual(['rev1'], self.inst_pp.calls)
1477
def test_disable_cache_clears_cache(self):
1478
# Put something in the cache
1479
self.caching_pp.get_parent_map(['rev1'])
1480
self.assertEqual(2, len(self.caching_pp._cache))
1481
self.caching_pp.disable_cache()
1482
self.assertIs(None, self.caching_pp._cache)
1484
def test_enable_cache_raises(self):
1485
e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1486
self.assertEqual('Cache enabled when already enabled.', str(e))
1488
def test_cache_misses(self):
1489
self.caching_pp.get_parent_map(['rev3'])
1490
self.caching_pp.get_parent_map(['rev3'])
1491
self.assertEqual(['rev3'], self.inst_pp.calls)
1493
def test_no_cache_misses(self):
1494
self.caching_pp.disable_cache()
1495
self.caching_pp.enable_cache(cache_misses=False)
1496
self.caching_pp.get_parent_map(['rev3'])
1497
self.caching_pp.get_parent_map(['rev3'])
1498
self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1500
def test_cache_extras(self):
1501
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1502
self.assertEqual({'rev2': ['rev1']},
1503
self.caching_pp.get_parent_map(['rev2']))
1504
self.assertEqual(['rev3'], self.inst_pp.calls)
1507
class TestCollapseLinearRegions(tests.TestCase):
1509
def assertCollapsed(self, collapsed, original):
1510
self.assertEqual(collapsed,
1511
_mod_graph.collapse_linear_regions(original))
1513
def test_collapse_nothing(self):
1514
d = {1:[2, 3], 2:[], 3:[]}
1515
self.assertCollapsed(d, d)
1516
d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1517
self.assertCollapsed(d, d)
1519
def test_collapse_chain(self):
1520
# Any time we have a linear chain, we should be able to collapse
1521
d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1522
self.assertCollapsed({1:[5], 5:[]}, d)
1523
d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1524
self.assertCollapsed({5:[1], 1:[]}, d)
1525
d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1526
self.assertCollapsed({5:[2], 2:[]}, d)
1528
def test_collapse_with_multiple_children(self):
1539
# 4 and 5 cannot be removed because 6 has 2 children
1540
# 2 and 3 cannot be removed because 1 has 2 parents
1541
d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1542
self.assertCollapsed(d, d)
1545
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1546
"""Tests for bzrlib.graph.PendingAncestryResult."""
1548
def test_get_keys(self):
1549
builder = self.make_branch_builder('b')
1550
builder.start_series()
1551
builder.build_snapshot('rev-1', None, [
1552
('add', ('', 'root-id', 'directory', ''))])
1553
builder.build_snapshot('rev-2', ['rev-1'], [])
1554
builder.finish_series()
1555
repo = builder.get_branch().repository
1557
self.addCleanup(repo.unlock)
1558
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1559
self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1561
def test_get_keys_excludes_null(self):
1562
# Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1563
# somewhere other than the last element, which can happen in real
1565
class StubGraph(object):
1566
def iter_ancestry(self, keys):
1567
return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1568
result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1569
result_keys = result._get_keys(StubGraph())
1570
# Only the non-null keys from the ancestry appear.
1571
self.assertEqual(set(['foo']), set(result_keys))
1574
class TestPendingAncestryResultRefine(TestGraphBase):
1576
def test_refine(self):
1577
# Used when pulling from a stacked repository, so test some revisions
1578
# being satisfied from the stacking branch.
1579
g = self.make_graph(
1580
{"tip":["mid"], "mid":["base"], "tag":["base"],
1581
"base":[NULL_REVISION], NULL_REVISION:[]})
1582
result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1583
result = result.refine(set(['tip']), set(['mid']))
1584
self.assertEqual(set(['mid', 'tag']), result.heads)
1585
result = result.refine(set(['mid', 'tag', 'base']),
1586
set([NULL_REVISION]))
1587
self.assertEqual(set([NULL_REVISION]), result.heads)
1588
self.assertTrue(result.is_empty())
1591
class TestSearchResultRefine(TestGraphBase):
1593
def test_refine(self):
1594
# Used when pulling from a stacked repository, so test some revisions
1595
# being satisfied from the stacking branch.
1596
g = self.make_graph(
1597
{"tip":["mid"], "mid":["base"], "tag":["base"],
1598
"base":[NULL_REVISION], NULL_REVISION:[]})
1599
result = _mod_graph.SearchResult(set(['tip', 'tag']),
1600
set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1601
result = result.refine(set(['tip']), set(['mid']))
1602
recipe = result.get_recipe()
1603
# We should be starting from tag (original head) and mid (seen ref)
1604
self.assertEqual(set(['mid', 'tag']), recipe[1])
1605
# We should be stopping at NULL (original stop) and tip (seen head)
1606
self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1607
self.assertEqual(3, recipe[3])
1608
result = result.refine(set(['mid', 'tag', 'base']),
1609
set([NULL_REVISION]))
1610
recipe = result.get_recipe()
1611
# We should be starting from nothing (NULL was known as a cut point)
1612
self.assertEqual(set([]), recipe[1])
1613
# We should be stopping at NULL (original stop) and tip (seen head) and
1614
# tag (seen head) and mid(seen mid-point head). We could come back and
1615
# define this as not including mid, for minimal results, but it is
1616
# still 'correct' to include mid, and simpler/easier.
1617
self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1618
self.assertEqual(0, recipe[3])
1619
self.assertTrue(result.is_empty())
added
removed
bzrlib/tests/test_graph.py
