497
922
self.assertEqual(set(['h1', 'h2']),
498
923
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
925
def test_breadth_first_search_start_ghosts(self):
926
graph = self.make_graph({})
927
# with_ghosts reports the ghosts
928
search = graph._make_breadth_first_searcher(['a-ghost'])
929
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
930
self.assertRaises(StopIteration, search.next_with_ghosts)
932
search = graph._make_breadth_first_searcher(['a-ghost'])
933
self.assertEqual(set(['a-ghost']), search.next())
934
self.assertRaises(StopIteration, search.next)
936
def test_breadth_first_search_deep_ghosts(self):
937
graph = self.make_graph({
939
'present':['child', 'ghost'],
942
# with_ghosts reports the ghosts
943
search = graph._make_breadth_first_searcher(['head'])
944
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
945
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
946
self.assertEqual((set(['child']), set(['ghost'])),
947
search.next_with_ghosts())
948
self.assertRaises(StopIteration, search.next_with_ghosts)
950
search = graph._make_breadth_first_searcher(['head'])
951
self.assertEqual(set(['head']), search.next())
952
self.assertEqual(set(['present']), search.next())
953
self.assertEqual(set(['child', 'ghost']),
955
self.assertRaises(StopIteration, search.next)
957
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
958
# To make the API robust, we allow calling both next() and
959
# next_with_ghosts() on the same searcher.
960
graph = self.make_graph({
962
'present':['child', 'ghost'],
965
# start with next_with_ghosts
966
search = graph._make_breadth_first_searcher(['head'])
967
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
968
self.assertEqual(set(['present']), search.next())
969
self.assertEqual((set(['child']), set(['ghost'])),
970
search.next_with_ghosts())
971
self.assertRaises(StopIteration, search.next)
973
search = graph._make_breadth_first_searcher(['head'])
974
self.assertEqual(set(['head']), search.next())
975
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
976
self.assertEqual(set(['child', 'ghost']),
978
self.assertRaises(StopIteration, search.next_with_ghosts)
980
def test_breadth_first_change_search(self):
981
# Changing the search should work with both next and next_with_ghosts.
982
graph = self.make_graph({
984
'present':['stopped'],
988
search = graph._make_breadth_first_searcher(['head'])
989
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
990
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
991
self.assertEqual(set(['present']),
992
search.stop_searching_any(['present']))
993
self.assertEqual((set(['other']), set(['other_ghost'])),
994
search.start_searching(['other', 'other_ghost']))
995
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
996
self.assertRaises(StopIteration, search.next_with_ghosts)
998
search = graph._make_breadth_first_searcher(['head'])
999
self.assertEqual(set(['head']), search.next())
1000
self.assertEqual(set(['present']), search.next())
1001
self.assertEqual(set(['present']),
1002
search.stop_searching_any(['present']))
1003
search.start_searching(['other', 'other_ghost'])
1004
self.assertEqual(set(['other_2']), search.next())
1005
self.assertRaises(StopIteration, search.next)
1007
def assertSeenAndResult(self, instructions, search, next):
1008
"""Check the results of .seen and get_result() for a seach.
1010
:param instructions: A list of tuples:
1011
(seen, recipe, included_keys, starts, stops).
1012
seen, recipe and included_keys are results to check on the search
1013
and the searches get_result(). starts and stops are parameters to
1014
pass to start_searching and stop_searching_any during each
1015
iteration, if they are not None.
1016
:param search: The search to use.
1017
:param next: A callable to advance the search.
1019
for seen, recipe, included_keys, starts, stops in instructions:
1020
# Adjust for recipe contract changes that don't vary for all the
1022
recipe = ('search',) + recipe
1024
if starts is not None:
1025
search.start_searching(starts)
1026
if stops is not None:
1027
search.stop_searching_any(stops)
1028
result = search.get_result()
1029
self.assertEqual(recipe, result.get_recipe())
1030
self.assertEqual(set(included_keys), result.get_keys())
1031
self.assertEqual(seen, search.seen)
1033
def test_breadth_first_get_result_excludes_current_pending(self):
1034
graph = self.make_graph({
1036
'child':[NULL_REVISION],
1039
search = graph._make_breadth_first_searcher(['head'])
1040
# At the start, nothing has been seen, to its all excluded:
1041
result = search.get_result()
1042
self.assertEqual(('search', set(['head']), set(['head']), 0),
1043
result.get_recipe())
1044
self.assertEqual(set(), result.get_keys())
1045
self.assertEqual(set(), search.seen)
1048
(set(['head']), (set(['head']), set(['child']), 1),
1049
['head'], None, None),
1050
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
1051
['head', 'child'], None, None),
1052
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
1053
['head', 'child', NULL_REVISION], None, None),
1055
self.assertSeenAndResult(expected, search, search.next)
1056
# using next_with_ghosts:
1057
search = graph._make_breadth_first_searcher(['head'])
1058
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1060
def test_breadth_first_get_result_starts_stops(self):
1061
graph = self.make_graph({
1063
'child':[NULL_REVISION],
1064
'otherhead':['otherchild'],
1065
'otherchild':['excluded'],
1066
'excluded':[NULL_REVISION],
1069
search = graph._make_breadth_first_searcher([])
1070
# Starting with nothing and adding a search works:
1071
search.start_searching(['head'])
1072
# head has been seen:
1073
result = search.get_result()
1074
self.assertEqual(('search', set(['head']), set(['child']), 1),
1075
result.get_recipe())
1076
self.assertEqual(set(['head']), result.get_keys())
1077
self.assertEqual(set(['head']), search.seen)
1080
# stop at child, and start a new search at otherhead:
1081
# - otherhead counts as seen immediately when start_searching is
1083
(set(['head', 'child', 'otherhead']),
1084
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1085
['head', 'otherhead'], ['otherhead'], ['child']),
1086
(set(['head', 'child', 'otherhead', 'otherchild']),
1087
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1088
['head', 'otherhead', 'otherchild'], None, None),
1089
# stop searching excluded now
1090
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1091
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1092
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1094
self.assertSeenAndResult(expected, search, search.next)
1095
# using next_with_ghosts:
1096
search = graph._make_breadth_first_searcher([])
1097
search.start_searching(['head'])
1098
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1100
def test_breadth_first_stop_searching_not_queried(self):
1101
# A client should be able to say 'stop node X' even if X has not been
1102
# returned to the client.
1103
graph = self.make_graph({
1104
'head':['child', 'ghost1'],
1105
'child':[NULL_REVISION],
1108
search = graph._make_breadth_first_searcher(['head'])
1110
# NULL_REVISION and ghost1 have not been returned
1112
(set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1113
['head'], None, [NULL_REVISION, 'ghost1']),
1114
# ghost1 has been returned, NULL_REVISION is to be returned in the
1116
(set(['head', 'child', 'ghost1']),
1117
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1118
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1120
self.assertSeenAndResult(expected, search, search.next)
1121
# using next_with_ghosts:
1122
search = graph._make_breadth_first_searcher(['head'])
1123
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1125
def test_breadth_first_stop_searching_late(self):
1126
# A client should be able to say 'stop node X' and have it excluded
1127
# from the result even if X was seen in an older iteration of the
1129
graph = self.make_graph({
1132
'child':[NULL_REVISION],
1135
search = graph._make_breadth_first_searcher(['head'])
1137
(set(['head']), (set(['head']), set(['middle']), 1),
1138
['head'], None, None),
1139
(set(['head', 'middle']), (set(['head']), set(['child']), 2),
1140
['head', 'middle'], None, None),
1141
# 'middle' came from the previous iteration, but we don't stop
1142
# searching it until *after* advancing the searcher.
1143
(set(['head', 'middle', 'child']),
1144
(set(['head']), set(['middle', 'child']), 1),
1145
['head'], None, ['middle', 'child']),
1147
self.assertSeenAndResult(expected, search, search.next)
1148
# using next_with_ghosts:
1149
search = graph._make_breadth_first_searcher(['head'])
1150
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1152
def test_breadth_first_get_result_ghosts_are_excluded(self):
1153
graph = self.make_graph({
1154
'head':['child', 'ghost'],
1155
'child':[NULL_REVISION],
1158
search = graph._make_breadth_first_searcher(['head'])
1162
(set(['head']), set(['ghost', 'child']), 1),
1163
['head'], None, None),
1164
(set(['head', 'child', 'ghost']),
1165
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1166
['head', 'child'], None, None),
1168
self.assertSeenAndResult(expected, search, search.next)
1169
# using next_with_ghosts:
1170
search = graph._make_breadth_first_searcher(['head'])
1171
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1173
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1174
graph = self.make_graph({
1176
'child':[NULL_REVISION],
1179
search = graph._make_breadth_first_searcher(['head'])
1182
(set(['head', 'ghost']),
1183
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1184
['head'], ['ghost'], None),
1185
(set(['head', 'child', 'ghost']),
1186
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1187
['head', 'child'], None, None),
1189
self.assertSeenAndResult(expected, search, search.next)
1190
# using next_with_ghosts:
1191
search = graph._make_breadth_first_searcher(['head'])
1192
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1194
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1195
graph = self.make_graph({
1196
'head':[NULL_REVISION],
1199
search = graph._make_breadth_first_searcher(['head'])
1203
(set(['head']), set([NULL_REVISION]), 1),
1204
['head'], None, None),
1205
(set(['head', NULL_REVISION]),
1206
(set(['head']), set([]), 2),
1207
['head', NULL_REVISION], None, None),
1209
self.assertSeenAndResult(expected, search, search.next)
1210
# using next_with_ghosts:
1211
search = graph._make_breadth_first_searcher(['head'])
1212
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1214
def test_breadth_first_search_get_result_after_StopIteration(self):
1215
# StopIteration should not invalid anything..
1216
graph = self.make_graph({
1217
'head':[NULL_REVISION],
1220
search = graph._make_breadth_first_searcher(['head'])
1224
(set(['head']), set([NULL_REVISION]), 1),
1225
['head'], None, None),
1226
(set(['head', 'ghost', NULL_REVISION]),
1227
(set(['head', 'ghost']), set(['ghost']), 2),
1228
['head', NULL_REVISION], ['ghost'], None),
1230
self.assertSeenAndResult(expected, search, search.next)
1231
self.assertRaises(StopIteration, search.next)
1232
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1233
result = search.get_result()
1234
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1235
result.get_recipe())
1236
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1237
# using next_with_ghosts:
1238
search = graph._make_breadth_first_searcher(['head'])
1239
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1240
self.assertRaises(StopIteration, search.next)
1241
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1242
result = search.get_result()
1243
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1244
result.get_recipe())
1245
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1248
class TestFindUniqueAncestors(TestGraphBase):
1250
def assertFindUniqueAncestors(self, graph, expected, node, common):
1251
actual = graph.find_unique_ancestors(node, common)
1252
self.assertEqual(expected, sorted(actual))
1254
def test_empty_set(self):
1255
graph = self.make_graph(ancestry_1)
1256
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1257
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1258
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1260
def test_single_node(self):
1261
graph = self.make_graph(ancestry_1)
1262
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1263
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1264
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1266
def test_minimal_ancestry(self):
1267
graph = self.make_breaking_graph(extended_history_shortcut,
1268
[NULL_REVISION, 'a', 'b'])
1269
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1271
graph = self.make_breaking_graph(extended_history_shortcut,
1273
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1275
graph = self.make_breaking_graph(complex_shortcut,
1277
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1278
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1279
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1280
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1282
def test_in_ancestry(self):
1283
graph = self.make_graph(ancestry_1)
1284
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1285
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1287
def test_multiple_revisions(self):
1288
graph = self.make_graph(ancestry_1)
1289
self.assertFindUniqueAncestors(graph,
1290
['rev4'], 'rev4', ['rev3', 'rev2b'])
1291
self.assertFindUniqueAncestors(graph,
1292
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1294
def test_complex_shortcut(self):
1295
graph = self.make_graph(complex_shortcut)
1296
self.assertFindUniqueAncestors(graph,
1297
['h', 'n'], 'n', ['m'])
1298
self.assertFindUniqueAncestors(graph,
1299
['e', 'i', 'm'], 'm', ['n'])
1301
def test_complex_shortcut2(self):
1302
graph = self.make_graph(complex_shortcut2)
1303
self.assertFindUniqueAncestors(graph,
1304
['j', 'u'], 'u', ['t'])
1305
self.assertFindUniqueAncestors(graph,
1308
def test_multiple_interesting_unique(self):
1309
graph = self.make_graph(multiple_interesting_unique)
1310
self.assertFindUniqueAncestors(graph,
1311
['j', 'y'], 'y', ['z'])
1312
self.assertFindUniqueAncestors(graph,
1313
['p', 'z'], 'z', ['y'])
1315
def test_racing_shortcuts(self):
1316
graph = self.make_graph(racing_shortcuts)
1317
self.assertFindUniqueAncestors(graph,
1318
['p', 'q', 'z'], 'z', ['y'])
1319
self.assertFindUniqueAncestors(graph,
1320
['h', 'i', 'j', 'y'], 'j', ['z'])
1323
class TestGraphFindDistanceToNull(TestGraphBase):
1324
"""Test an api that should be able to compute a revno"""
1326
def assertFindDistance(self, revno, graph, target_id, known_ids):
1327
"""Assert the output of Graph.find_distance_to_null()"""
1328
actual = graph.find_distance_to_null(target_id, known_ids)
1329
self.assertEqual(revno, actual)
1331
def test_nothing_known(self):
1332
graph = self.make_graph(ancestry_1)
1333
self.assertFindDistance(0, graph, NULL_REVISION, [])
1334
self.assertFindDistance(1, graph, 'rev1', [])
1335
self.assertFindDistance(2, graph, 'rev2a', [])
1336
self.assertFindDistance(2, graph, 'rev2b', [])
1337
self.assertFindDistance(3, graph, 'rev3', [])
1338
self.assertFindDistance(4, graph, 'rev4', [])
1340
def test_rev_is_ghost(self):
1341
graph = self.make_graph(ancestry_1)
1342
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1343
graph.find_distance_to_null, 'rev_missing', [])
1344
self.assertEqual('rev_missing', e.revision_id)
1345
self.assertEqual('rev_missing', e.ghost_revision_id)
1347
def test_ancestor_is_ghost(self):
1348
graph = self.make_graph({'rev':['parent']})
1349
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1350
graph.find_distance_to_null, 'rev', [])
1351
self.assertEqual('rev', e.revision_id)
1352
self.assertEqual('parent', e.ghost_revision_id)
1354
def test_known_in_ancestry(self):
1355
graph = self.make_graph(ancestry_1)
1356
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1357
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1359
def test_known_in_ancestry_limits(self):
1360
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1361
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1363
def test_target_is_ancestor(self):
1364
graph = self.make_graph(ancestry_1)
1365
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1367
def test_target_is_ancestor_limits(self):
1368
"""We shouldn't search all history if we run into ourselves"""
1369
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1370
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1372
def test_target_parallel_to_known_limits(self):
1373
# Even though the known revision isn't part of the other ancestry, they
1374
# eventually converge
1375
graph = self.make_breaking_graph(with_tail, ['a'])
1376
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1377
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1378
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1379
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1382
class TestFindMergeOrder(TestGraphBase):
1384
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1385
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1387
def test_parents(self):
1388
graph = self.make_graph(ancestry_1)
1389
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1391
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1394
def test_ancestors(self):
1395
graph = self.make_graph(ancestry_1)
1396
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1398
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1401
def test_shortcut_one_ancestor(self):
1402
# When we have enough info, we can stop searching
1403
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1404
# Single ancestors shortcut right away
1405
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1407
def test_shortcut_after_one_ancestor(self):
1408
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1409
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1412
class TestFindDescendants(TestGraphBase):
1414
def test_find_descendants_rev1_rev3(self):
1415
graph = self.make_graph(ancestry_1)
1416
descendants = graph.find_descendants('rev1', 'rev3')
1417
self.assertEqual(set(['rev1', 'rev2a', 'rev3']), descendants)
1419
def test_find_descendants_rev1_rev4(self):
1420
graph = self.make_graph(ancestry_1)
1421
descendants = graph.find_descendants('rev1', 'rev4')
1422
self.assertEqual(set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']),
1425
def test_find_descendants_rev2a_rev4(self):
1426
graph = self.make_graph(ancestry_1)
1427
descendants = graph.find_descendants('rev2a', 'rev4')
1428
self.assertEqual(set(['rev2a', 'rev3', 'rev4']), descendants)
1430
class TestFindLefthandMerger(TestGraphBase):
1432
def check_merger(self, result, ancestry, merged, tip):
1433
graph = self.make_graph(ancestry)
1434
self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
1436
def test_find_lefthand_merger_rev2b(self):
1437
self.check_merger('rev4', ancestry_1, 'rev2b', 'rev4')
1439
def test_find_lefthand_merger_rev2a(self):
1440
self.check_merger('rev2a', ancestry_1, 'rev2a', 'rev4')
1442
def test_find_lefthand_merger_rev4(self):
1443
self.check_merger(None, ancestry_1, 'rev4', 'rev2a')
1445
def test_find_lefthand_merger_f(self):
1446
self.check_merger('i', complex_shortcut, 'f', 'm')
1448
def test_find_lefthand_merger_g(self):
1449
self.check_merger('i', complex_shortcut, 'g', 'm')
1451
def test_find_lefthand_merger_h(self):
1452
self.check_merger('n', complex_shortcut, 'h', 'n')
1455
class TestGetChildMap(TestGraphBase):
1457
def test_get_child_map(self):
1458
graph = self.make_graph(ancestry_1)
1459
child_map = graph.get_child_map(['rev4', 'rev3', 'rev2a', 'rev2b'])
1460
self.assertEqual({'rev1': ['rev2a', 'rev2b'],
1467
class TestCachingParentsProvider(tests.TestCase):
1468
"""These tests run with:
1470
self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1472
self.caching_pp, a CachingParentsProvider layered on inst_pp.
1476
super(TestCachingParentsProvider, self).setUp()
1477
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1478
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1479
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1481
def test_get_parent_map(self):
1482
"""Requesting the same revision should be returned from cache"""
1483
self.assertEqual({}, self.caching_pp._cache)
1484
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1485
self.assertEqual(['a'], self.inst_pp.calls)
1486
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1487
# No new call, as it should have been returned from the cache
1488
self.assertEqual(['a'], self.inst_pp.calls)
1489
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1491
def test_get_parent_map_not_present(self):
1492
"""The cache should also track when a revision doesn't exist"""
1493
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1494
self.assertEqual(['b'], self.inst_pp.calls)
1495
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1497
self.assertEqual(['b'], self.inst_pp.calls)
1499
def test_get_parent_map_mixed(self):
1500
"""Anything that can be returned from cache, should be"""
1501
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1502
self.assertEqual(['b'], self.inst_pp.calls)
1503
self.assertEqual({'a':('b',)},
1504
self.caching_pp.get_parent_map(['a', 'b']))
1505
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1507
def test_get_parent_map_repeated(self):
1508
"""Asking for the same parent 2x will only forward 1 request."""
1509
self.assertEqual({'a':('b',)},
1510
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1511
# Use sorted because we don't care about the order, just that each is
1512
# only present 1 time.
1513
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1515
def test_note_missing_key(self):
1516
"""After noting that a key is missing it is cached."""
1517
self.caching_pp.note_missing_key('b')
1518
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1519
self.assertEqual([], self.inst_pp.calls)
1520
self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1523
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1524
"""Test the behaviour when parents are provided that were not requested."""
1527
super(TestCachingParentsProviderExtras, self).setUp()
1528
class ExtraParentsProvider(object):
1530
def get_parent_map(self, keys):
1531
return {'rev1': [], 'rev2': ['rev1',]}
1533
self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1534
self.caching_pp = _mod_graph.CachingParentsProvider(
1535
get_parent_map=self.inst_pp.get_parent_map)
1537
def test_uncached(self):
1538
self.caching_pp.disable_cache()
1539
self.assertEqual({'rev1': []},
1540
self.caching_pp.get_parent_map(['rev1']))
1541
self.assertEqual(['rev1'], self.inst_pp.calls)
1542
self.assertIs(None, self.caching_pp._cache)
1544
def test_cache_initially_empty(self):
1545
self.assertEqual({}, self.caching_pp._cache)
1547
def test_cached(self):
1548
self.assertEqual({'rev1': []},
1549
self.caching_pp.get_parent_map(['rev1']))
1550
self.assertEqual(['rev1'], self.inst_pp.calls)
1551
self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1552
self.caching_pp._cache)
1553
self.assertEqual({'rev1': []},
1554
self.caching_pp.get_parent_map(['rev1']))
1555
self.assertEqual(['rev1'], self.inst_pp.calls)
1557
def test_disable_cache_clears_cache(self):
1558
# Put something in the cache
1559
self.caching_pp.get_parent_map(['rev1'])
1560
self.assertEqual(2, len(self.caching_pp._cache))
1561
self.caching_pp.disable_cache()
1562
self.assertIs(None, self.caching_pp._cache)
1564
def test_enable_cache_raises(self):
1565
e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1566
self.assertEqual('Cache enabled when already enabled.', str(e))
1568
def test_cache_misses(self):
1569
self.caching_pp.get_parent_map(['rev3'])
1570
self.caching_pp.get_parent_map(['rev3'])
1571
self.assertEqual(['rev3'], self.inst_pp.calls)
1573
def test_no_cache_misses(self):
1574
self.caching_pp.disable_cache()
1575
self.caching_pp.enable_cache(cache_misses=False)
1576
self.caching_pp.get_parent_map(['rev3'])
1577
self.caching_pp.get_parent_map(['rev3'])
1578
self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1580
def test_cache_extras(self):
1581
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1582
self.assertEqual({'rev2': ['rev1']},
1583
self.caching_pp.get_parent_map(['rev2']))
1584
self.assertEqual(['rev3'], self.inst_pp.calls)
1587
class TestCollapseLinearRegions(tests.TestCase):
1589
def assertCollapsed(self, collapsed, original):
1590
self.assertEqual(collapsed,
1591
_mod_graph.collapse_linear_regions(original))
1593
def test_collapse_nothing(self):
1594
d = {1:[2, 3], 2:[], 3:[]}
1595
self.assertCollapsed(d, d)
1596
d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1597
self.assertCollapsed(d, d)
1599
def test_collapse_chain(self):
1600
# Any time we have a linear chain, we should be able to collapse
1601
d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1602
self.assertCollapsed({1:[5], 5:[]}, d)
1603
d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1604
self.assertCollapsed({5:[1], 1:[]}, d)
1605
d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1606
self.assertCollapsed({5:[2], 2:[]}, d)
1608
def test_collapse_with_multiple_children(self):
1619
# 4 and 5 cannot be removed because 6 has 2 children
1620
# 2 and 3 cannot be removed because 1 has 2 parents
1621
d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1622
self.assertCollapsed(d, d)
1625
class TestGraphThunkIdsToKeys(tests.TestCase):
1627
def test_heads(self):
1633
d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1634
('B',): [('A',)], ('A',): []}
1635
g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1636
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1637
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
1638
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
1639
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1640
self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1642
def test_add_node(self):
1643
d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1644
g = _mod_graph.KnownGraph(d)
1645
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1646
graph_thunk.add_node("D", ["A", "C"])
1647
self.assertEqual(['B', 'D'],
1648
sorted(graph_thunk.heads(['D', 'B', 'A'])))
1651
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1652
"""Tests for bzrlib.graph.PendingAncestryResult."""
1654
def test_get_keys(self):
1655
builder = self.make_branch_builder('b')
1656
builder.start_series()
1657
builder.build_snapshot('rev-1', None, [
1658
('add', ('', 'root-id', 'directory', ''))])
1659
builder.build_snapshot('rev-2', ['rev-1'], [])
1660
builder.finish_series()
1661
repo = builder.get_branch().repository
1663
self.addCleanup(repo.unlock)
1664
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1665
self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1667
def test_get_keys_excludes_ghosts(self):
1668
builder = self.make_branch_builder('b')
1669
builder.start_series()
1670
builder.build_snapshot('rev-1', None, [
1671
('add', ('', 'root-id', 'directory', ''))])
1672
builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
1673
builder.finish_series()
1674
repo = builder.get_branch().repository
1676
self.addCleanup(repo.unlock)
1677
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1678
self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
1680
def test_get_keys_excludes_null(self):
1681
# Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1682
# somewhere other than the last element, which can happen in real
1684
class StubGraph(object):
1685
def iter_ancestry(self, keys):
1686
return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1687
result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1688
result_keys = result._get_keys(StubGraph())
1689
# Only the non-null keys from the ancestry appear.
1690
self.assertEqual(set(['foo']), set(result_keys))
1693
class TestPendingAncestryResultRefine(TestGraphBase):
1695
def test_refine(self):
1696
# Used when pulling from a stacked repository, so test some revisions
1697
# being satisfied from the stacking branch.
1698
g = self.make_graph(
1699
{"tip":["mid"], "mid":["base"], "tag":["base"],
1700
"base":[NULL_REVISION], NULL_REVISION:[]})
1701
result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1702
result = result.refine(set(['tip']), set(['mid']))
1703
self.assertEqual(set(['mid', 'tag']), result.heads)
1704
result = result.refine(set(['mid', 'tag', 'base']),
1705
set([NULL_REVISION]))
1706
self.assertEqual(set([NULL_REVISION]), result.heads)
1707
self.assertTrue(result.is_empty())
1710
class TestSearchResultRefine(TestGraphBase):
1712
def test_refine(self):
1713
# Used when pulling from a stacked repository, so test some revisions
1714
# being satisfied from the stacking branch.
1715
g = self.make_graph(
1716
{"tip":["mid"], "mid":["base"], "tag":["base"],
1717
"base":[NULL_REVISION], NULL_REVISION:[]})
1718
result = _mod_graph.SearchResult(set(['tip', 'tag']),
1719
set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1720
result = result.refine(set(['tip']), set(['mid']))
1721
recipe = result.get_recipe()
1722
# We should be starting from tag (original head) and mid (seen ref)
1723
self.assertEqual(set(['mid', 'tag']), recipe[1])
1724
# We should be stopping at NULL (original stop) and tip (seen head)
1725
self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1726
self.assertEqual(3, recipe[3])
1727
result = result.refine(set(['mid', 'tag', 'base']),
1728
set([NULL_REVISION]))
1729
recipe = result.get_recipe()
1730
# We should be starting from nothing (NULL was known as a cut point)
1731
self.assertEqual(set([]), recipe[1])
1732
# We should be stopping at NULL (original stop) and tip (seen head) and
1733
# tag (seen head) and mid(seen mid-point head). We could come back and
1734
# define this as not including mid, for minimal results, but it is
1735
# still 'correct' to include mid, and simpler/easier.
1736
self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1737
self.assertEqual(0, recipe[3])
1738
self.assertTrue(result.is_empty())
added
removed
bzrlib/tests/test_graph.py
