937
508
self.assertEqual(set(['h1', 'h2']),
938
509
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
940
def test_breadth_first_search_start_ghosts(self):
941
graph = self.make_graph({})
942
# with_ghosts reports the ghosts
943
search = graph._make_breadth_first_searcher(['a-ghost'])
944
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
945
self.assertRaises(StopIteration, search.next_with_ghosts)
947
search = graph._make_breadth_first_searcher(['a-ghost'])
948
self.assertEqual(set(['a-ghost']), search.next())
949
self.assertRaises(StopIteration, search.next)
951
def test_breadth_first_search_deep_ghosts(self):
952
graph = self.make_graph({
954
'present':['child', 'ghost'],
957
# with_ghosts reports the ghosts
958
search = graph._make_breadth_first_searcher(['head'])
959
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
960
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
961
self.assertEqual((set(['child']), set(['ghost'])),
962
search.next_with_ghosts())
963
self.assertRaises(StopIteration, search.next_with_ghosts)
965
search = graph._make_breadth_first_searcher(['head'])
966
self.assertEqual(set(['head']), search.next())
967
self.assertEqual(set(['present']), search.next())
968
self.assertEqual(set(['child', 'ghost']),
970
self.assertRaises(StopIteration, search.next)
972
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
973
# To make the API robust, we allow calling both next() and
974
# next_with_ghosts() on the same searcher.
975
graph = self.make_graph({
977
'present':['child', 'ghost'],
980
# start with next_with_ghosts
981
search = graph._make_breadth_first_searcher(['head'])
982
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
983
self.assertEqual(set(['present']), search.next())
984
self.assertEqual((set(['child']), set(['ghost'])),
985
search.next_with_ghosts())
986
self.assertRaises(StopIteration, search.next)
988
search = graph._make_breadth_first_searcher(['head'])
989
self.assertEqual(set(['head']), search.next())
990
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
991
self.assertEqual(set(['child', 'ghost']),
993
self.assertRaises(StopIteration, search.next_with_ghosts)
995
def test_breadth_first_change_search(self):
996
# Changing the search should work with both next and next_with_ghosts.
997
graph = self.make_graph({
999
'present':['stopped'],
1000
'other':['other_2'],
1003
search = graph._make_breadth_first_searcher(['head'])
1004
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
1005
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
1006
self.assertEqual(set(['present']),
1007
search.stop_searching_any(['present']))
1008
self.assertEqual((set(['other']), set(['other_ghost'])),
1009
search.start_searching(['other', 'other_ghost']))
1010
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
1011
self.assertRaises(StopIteration, search.next_with_ghosts)
1012
# next includes them
1013
search = graph._make_breadth_first_searcher(['head'])
1014
self.assertEqual(set(['head']), search.next())
1015
self.assertEqual(set(['present']), search.next())
1016
self.assertEqual(set(['present']),
1017
search.stop_searching_any(['present']))
1018
search.start_searching(['other', 'other_ghost'])
1019
self.assertEqual(set(['other_2']), search.next())
1020
self.assertRaises(StopIteration, search.next)
1022
def assertSeenAndResult(self, instructions, search, next):
1023
"""Check the results of .seen and get_result() for a seach.
1025
:param instructions: A list of tuples:
1026
(seen, recipe, included_keys, starts, stops).
1027
seen, recipe and included_keys are results to check on the search
1028
and the searches get_result(). starts and stops are parameters to
1029
pass to start_searching and stop_searching_any during each
1030
iteration, if they are not None.
1031
:param search: The search to use.
1032
:param next: A callable to advance the search.
1034
for seen, recipe, included_keys, starts, stops in instructions:
1035
# Adjust for recipe contract changes that don't vary for all the
1037
recipe = ('search',) + recipe
1039
if starts is not None:
1040
search.start_searching(starts)
1041
if stops is not None:
1042
search.stop_searching_any(stops)
1043
result = search.get_result()
1044
self.assertEqual(recipe, result.get_recipe())
1045
self.assertEqual(set(included_keys), result.get_keys())
1046
self.assertEqual(seen, search.seen)
1048
def test_breadth_first_get_result_excludes_current_pending(self):
1049
graph = self.make_graph({
1051
'child':[NULL_REVISION],
1054
search = graph._make_breadth_first_searcher(['head'])
1055
# At the start, nothing has been seen, to its all excluded:
1056
result = search.get_result()
1057
self.assertEqual(('search', set(['head']), set(['head']), 0),
1058
result.get_recipe())
1059
self.assertEqual(set(), result.get_keys())
1060
self.assertEqual(set(), search.seen)
1063
(set(['head']), (set(['head']), set(['child']), 1),
1064
['head'], None, None),
1065
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
1066
['head', 'child'], None, None),
1067
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
1068
['head', 'child', NULL_REVISION], None, None),
1070
self.assertSeenAndResult(expected, search, search.next)
1071
# using next_with_ghosts:
1072
search = graph._make_breadth_first_searcher(['head'])
1073
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1075
def test_breadth_first_get_result_starts_stops(self):
1076
graph = self.make_graph({
1078
'child':[NULL_REVISION],
1079
'otherhead':['otherchild'],
1080
'otherchild':['excluded'],
1081
'excluded':[NULL_REVISION],
1084
search = graph._make_breadth_first_searcher([])
1085
# Starting with nothing and adding a search works:
1086
search.start_searching(['head'])
1087
# head has been seen:
1088
result = search.get_result()
1089
self.assertEqual(('search', set(['head']), set(['child']), 1),
1090
result.get_recipe())
1091
self.assertEqual(set(['head']), result.get_keys())
1092
self.assertEqual(set(['head']), search.seen)
1095
# stop at child, and start a new search at otherhead:
1096
# - otherhead counts as seen immediately when start_searching is
1098
(set(['head', 'child', 'otherhead']),
1099
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1100
['head', 'otherhead'], ['otherhead'], ['child']),
1101
(set(['head', 'child', 'otherhead', 'otherchild']),
1102
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1103
['head', 'otherhead', 'otherchild'], None, None),
1104
# stop searching excluded now
1105
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1106
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1107
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1109
self.assertSeenAndResult(expected, search, search.next)
1110
# using next_with_ghosts:
1111
search = graph._make_breadth_first_searcher([])
1112
search.start_searching(['head'])
1113
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1115
def test_breadth_first_stop_searching_not_queried(self):
1116
# A client should be able to say 'stop node X' even if X has not been
1117
# returned to the client.
1118
graph = self.make_graph({
1119
'head':['child', 'ghost1'],
1120
'child':[NULL_REVISION],
1123
search = graph._make_breadth_first_searcher(['head'])
1125
# NULL_REVISION and ghost1 have not been returned
1127
(set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1128
['head'], None, [NULL_REVISION, 'ghost1']),
1129
# ghost1 has been returned, NULL_REVISION is to be returned in the
1131
(set(['head', 'child', 'ghost1']),
1132
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1133
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1135
self.assertSeenAndResult(expected, search, search.next)
1136
# using next_with_ghosts:
1137
search = graph._make_breadth_first_searcher(['head'])
1138
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1140
def test_breadth_first_stop_searching_late(self):
1141
# A client should be able to say 'stop node X' and have it excluded
1142
# from the result even if X was seen in an older iteration of the
1144
graph = self.make_graph({
1147
'child':[NULL_REVISION],
1150
search = graph._make_breadth_first_searcher(['head'])
1152
(set(['head']), (set(['head']), set(['middle']), 1),
1153
['head'], None, None),
1154
(set(['head', 'middle']), (set(['head']), set(['child']), 2),
1155
['head', 'middle'], None, None),
1156
# 'middle' came from the previous iteration, but we don't stop
1157
# searching it until *after* advancing the searcher.
1158
(set(['head', 'middle', 'child']),
1159
(set(['head']), set(['middle', 'child']), 1),
1160
['head'], None, ['middle', 'child']),
1162
self.assertSeenAndResult(expected, search, search.next)
1163
# using next_with_ghosts:
1164
search = graph._make_breadth_first_searcher(['head'])
1165
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1167
def test_breadth_first_get_result_ghosts_are_excluded(self):
1168
graph = self.make_graph({
1169
'head':['child', 'ghost'],
1170
'child':[NULL_REVISION],
1173
search = graph._make_breadth_first_searcher(['head'])
1177
(set(['head']), set(['ghost', 'child']), 1),
1178
['head'], None, None),
1179
(set(['head', 'child', 'ghost']),
1180
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1181
['head', 'child'], None, None),
1183
self.assertSeenAndResult(expected, search, search.next)
1184
# using next_with_ghosts:
1185
search = graph._make_breadth_first_searcher(['head'])
1186
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1188
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1189
graph = self.make_graph({
1191
'child':[NULL_REVISION],
1194
search = graph._make_breadth_first_searcher(['head'])
1197
(set(['head', 'ghost']),
1198
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1199
['head'], ['ghost'], None),
1200
(set(['head', 'child', 'ghost']),
1201
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1202
['head', 'child'], None, None),
1204
self.assertSeenAndResult(expected, search, search.next)
1205
# using next_with_ghosts:
1206
search = graph._make_breadth_first_searcher(['head'])
1207
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1209
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1210
graph = self.make_graph({
1211
'head':[NULL_REVISION],
1214
search = graph._make_breadth_first_searcher(['head'])
1218
(set(['head']), set([NULL_REVISION]), 1),
1219
['head'], None, None),
1220
(set(['head', NULL_REVISION]),
1221
(set(['head']), set([]), 2),
1222
['head', NULL_REVISION], None, None),
1224
self.assertSeenAndResult(expected, search, search.next)
1225
# using next_with_ghosts:
1226
search = graph._make_breadth_first_searcher(['head'])
1227
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1229
def test_breadth_first_search_get_result_after_StopIteration(self):
1230
# StopIteration should not invalid anything..
1231
graph = self.make_graph({
1232
'head':[NULL_REVISION],
1235
search = graph._make_breadth_first_searcher(['head'])
1239
(set(['head']), set([NULL_REVISION]), 1),
1240
['head'], None, None),
1241
(set(['head', 'ghost', NULL_REVISION]),
1242
(set(['head', 'ghost']), set(['ghost']), 2),
1243
['head', NULL_REVISION], ['ghost'], None),
1245
self.assertSeenAndResult(expected, search, search.next)
1246
self.assertRaises(StopIteration, search.next)
1247
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1248
result = search.get_result()
1249
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1250
result.get_recipe())
1251
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1252
# using next_with_ghosts:
1253
search = graph._make_breadth_first_searcher(['head'])
1254
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1255
self.assertRaises(StopIteration, search.next)
1256
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1257
result = search.get_result()
1258
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1259
result.get_recipe())
1260
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1263
class TestFindUniqueAncestors(TestGraphBase):
1265
def assertFindUniqueAncestors(self, graph, expected, node, common):
1266
actual = graph.find_unique_ancestors(node, common)
1267
self.assertEqual(expected, sorted(actual))
1269
def test_empty_set(self):
1270
graph = self.make_graph(ancestry_1)
1271
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1272
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1273
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1275
def test_single_node(self):
1276
graph = self.make_graph(ancestry_1)
1277
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1278
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1279
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1281
def test_minimal_ancestry(self):
1282
graph = self.make_breaking_graph(extended_history_shortcut,
1283
[NULL_REVISION, 'a', 'b'])
1284
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1286
graph = self.make_breaking_graph(extended_history_shortcut,
1288
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1290
graph = self.make_breaking_graph(complex_shortcut,
1292
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1293
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1294
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1295
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1297
def test_in_ancestry(self):
1298
graph = self.make_graph(ancestry_1)
1299
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1300
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1302
def test_multiple_revisions(self):
1303
graph = self.make_graph(ancestry_1)
1304
self.assertFindUniqueAncestors(graph,
1305
['rev4'], 'rev4', ['rev3', 'rev2b'])
1306
self.assertFindUniqueAncestors(graph,
1307
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1309
def test_complex_shortcut(self):
1310
graph = self.make_graph(complex_shortcut)
1311
self.assertFindUniqueAncestors(graph,
1312
['h', 'n'], 'n', ['m'])
1313
self.assertFindUniqueAncestors(graph,
1314
['e', 'i', 'm'], 'm', ['n'])
1316
def test_complex_shortcut2(self):
1317
graph = self.make_graph(complex_shortcut2)
1318
self.assertFindUniqueAncestors(graph,
1319
['j', 'u'], 'u', ['t'])
1320
self.assertFindUniqueAncestors(graph,
1323
def test_multiple_interesting_unique(self):
1324
graph = self.make_graph(multiple_interesting_unique)
1325
self.assertFindUniqueAncestors(graph,
1326
['j', 'y'], 'y', ['z'])
1327
self.assertFindUniqueAncestors(graph,
1328
['p', 'z'], 'z', ['y'])
1330
def test_racing_shortcuts(self):
1331
graph = self.make_graph(racing_shortcuts)
1332
self.assertFindUniqueAncestors(graph,
1333
['p', 'q', 'z'], 'z', ['y'])
1334
self.assertFindUniqueAncestors(graph,
1335
['h', 'i', 'j', 'y'], 'j', ['z'])
1338
class TestGraphFindDistanceToNull(TestGraphBase):
1339
"""Test an api that should be able to compute a revno"""
1341
def assertFindDistance(self, revno, graph, target_id, known_ids):
1342
"""Assert the output of Graph.find_distance_to_null()"""
1343
actual = graph.find_distance_to_null(target_id, known_ids)
1344
self.assertEqual(revno, actual)
1346
def test_nothing_known(self):
1347
graph = self.make_graph(ancestry_1)
1348
self.assertFindDistance(0, graph, NULL_REVISION, [])
1349
self.assertFindDistance(1, graph, 'rev1', [])
1350
self.assertFindDistance(2, graph, 'rev2a', [])
1351
self.assertFindDistance(2, graph, 'rev2b', [])
1352
self.assertFindDistance(3, graph, 'rev3', [])
1353
self.assertFindDistance(4, graph, 'rev4', [])
1355
def test_rev_is_ghost(self):
1356
graph = self.make_graph(ancestry_1)
1357
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1358
graph.find_distance_to_null, 'rev_missing', [])
1359
self.assertEqual('rev_missing', e.revision_id)
1360
self.assertEqual('rev_missing', e.ghost_revision_id)
1362
def test_ancestor_is_ghost(self):
1363
graph = self.make_graph({'rev':['parent']})
1364
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1365
graph.find_distance_to_null, 'rev', [])
1366
self.assertEqual('rev', e.revision_id)
1367
self.assertEqual('parent', e.ghost_revision_id)
1369
def test_known_in_ancestry(self):
1370
graph = self.make_graph(ancestry_1)
1371
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1372
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1374
def test_known_in_ancestry_limits(self):
1375
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1376
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1378
def test_target_is_ancestor(self):
1379
graph = self.make_graph(ancestry_1)
1380
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1382
def test_target_is_ancestor_limits(self):
1383
"""We shouldn't search all history if we run into ourselves"""
1384
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1385
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1387
def test_target_parallel_to_known_limits(self):
1388
# Even though the known revision isn't part of the other ancestry, they
1389
# eventually converge
1390
graph = self.make_breaking_graph(with_tail, ['a'])
1391
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1392
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1393
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1394
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1397
class TestFindMergeOrder(TestGraphBase):
1399
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1400
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1402
def test_parents(self):
1403
graph = self.make_graph(ancestry_1)
1404
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1406
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1409
def test_ancestors(self):
1410
graph = self.make_graph(ancestry_1)
1411
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1413
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1416
def test_shortcut_one_ancestor(self):
1417
# When we have enough info, we can stop searching
1418
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1419
# Single ancestors shortcut right away
1420
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1422
def test_shortcut_after_one_ancestor(self):
1423
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1424
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1427
class TestCachingParentsProvider(tests.TestCase):
1428
"""These tests run with:
1430
self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1432
self.caching_pp, a CachingParentsProvider layered on inst_pp.
1436
super(TestCachingParentsProvider, self).setUp()
1437
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1438
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1439
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1441
def test_get_parent_map(self):
1442
"""Requesting the same revision should be returned from cache"""
1443
self.assertEqual({}, self.caching_pp._cache)
1444
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1445
self.assertEqual(['a'], self.inst_pp.calls)
1446
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1447
# No new call, as it should have been returned from the cache
1448
self.assertEqual(['a'], self.inst_pp.calls)
1449
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1451
def test_get_parent_map_not_present(self):
1452
"""The cache should also track when a revision doesn't exist"""
1453
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1454
self.assertEqual(['b'], self.inst_pp.calls)
1455
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1457
self.assertEqual(['b'], self.inst_pp.calls)
1459
def test_get_parent_map_mixed(self):
1460
"""Anything that can be returned from cache, should be"""
1461
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1462
self.assertEqual(['b'], self.inst_pp.calls)
1463
self.assertEqual({'a':('b',)},
1464
self.caching_pp.get_parent_map(['a', 'b']))
1465
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1467
def test_get_parent_map_repeated(self):
1468
"""Asking for the same parent 2x will only forward 1 request."""
1469
self.assertEqual({'a':('b',)},
1470
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1471
# Use sorted because we don't care about the order, just that each is
1472
# only present 1 time.
1473
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1475
def test_note_missing_key(self):
1476
"""After noting that a key is missing it is cached."""
1477
self.caching_pp.note_missing_key('b')
1478
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1479
self.assertEqual([], self.inst_pp.calls)
1480
self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1483
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1484
"""Test the behaviour when parents are provided that were not requested."""
1487
super(TestCachingParentsProviderExtras, self).setUp()
1488
class ExtraParentsProvider(object):
1490
def get_parent_map(self, keys):
1491
return {'rev1': [], 'rev2': ['rev1',]}
1493
self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1494
self.caching_pp = _mod_graph.CachingParentsProvider(
1495
get_parent_map=self.inst_pp.get_parent_map)
1497
def test_uncached(self):
1498
self.caching_pp.disable_cache()
1499
self.assertEqual({'rev1': []},
1500
self.caching_pp.get_parent_map(['rev1']))
1501
self.assertEqual(['rev1'], self.inst_pp.calls)
1502
self.assertIs(None, self.caching_pp._cache)
1504
def test_cache_initially_empty(self):
1505
self.assertEqual({}, self.caching_pp._cache)
1507
def test_cached(self):
1508
self.assertEqual({'rev1': []},
1509
self.caching_pp.get_parent_map(['rev1']))
1510
self.assertEqual(['rev1'], self.inst_pp.calls)
1511
self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1512
self.caching_pp._cache)
1513
self.assertEqual({'rev1': []},
1514
self.caching_pp.get_parent_map(['rev1']))
1515
self.assertEqual(['rev1'], self.inst_pp.calls)
1517
def test_disable_cache_clears_cache(self):
1518
# Put something in the cache
1519
self.caching_pp.get_parent_map(['rev1'])
1520
self.assertEqual(2, len(self.caching_pp._cache))
1521
self.caching_pp.disable_cache()
1522
self.assertIs(None, self.caching_pp._cache)
1524
def test_enable_cache_raises(self):
1525
e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1526
self.assertEqual('Cache enabled when already enabled.', str(e))
1528
def test_cache_misses(self):
1529
self.caching_pp.get_parent_map(['rev3'])
1530
self.caching_pp.get_parent_map(['rev3'])
1531
self.assertEqual(['rev3'], self.inst_pp.calls)
1533
def test_no_cache_misses(self):
1534
self.caching_pp.disable_cache()
1535
self.caching_pp.enable_cache(cache_misses=False)
1536
self.caching_pp.get_parent_map(['rev3'])
1537
self.caching_pp.get_parent_map(['rev3'])
1538
self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1540
def test_cache_extras(self):
1541
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1542
self.assertEqual({'rev2': ['rev1']},
1543
self.caching_pp.get_parent_map(['rev2']))
1544
self.assertEqual(['rev3'], self.inst_pp.calls)
1547
class TestCollapseLinearRegions(tests.TestCase):
1549
def assertCollapsed(self, collapsed, original):
1550
self.assertEqual(collapsed,
1551
_mod_graph.collapse_linear_regions(original))
1553
def test_collapse_nothing(self):
1554
d = {1:[2, 3], 2:[], 3:[]}
1555
self.assertCollapsed(d, d)
1556
d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1557
self.assertCollapsed(d, d)
1559
def test_collapse_chain(self):
1560
# Any time we have a linear chain, we should be able to collapse
1561
d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1562
self.assertCollapsed({1:[5], 5:[]}, d)
1563
d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1564
self.assertCollapsed({5:[1], 1:[]}, d)
1565
d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1566
self.assertCollapsed({5:[2], 2:[]}, d)
1568
def test_collapse_with_multiple_children(self):
1579
# 4 and 5 cannot be removed because 6 has 2 children
1580
# 2 and 3 cannot be removed because 1 has 2 parents
1581
d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1582
self.assertCollapsed(d, d)
1585
class TestGraphThunkIdsToKeys(tests.TestCase):
1587
def test_heads(self):
1593
d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1594
('B',): [('A',)], ('A',): []}
1595
g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1596
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1597
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
1598
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
1599
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1600
self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1603
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1604
"""Tests for bzrlib.graph.PendingAncestryResult."""
1606
def test_get_keys(self):
1607
builder = self.make_branch_builder('b')
1608
builder.start_series()
1609
builder.build_snapshot('rev-1', None, [
1610
('add', ('', 'root-id', 'directory', ''))])
1611
builder.build_snapshot('rev-2', ['rev-1'], [])
1612
builder.finish_series()
1613
repo = builder.get_branch().repository
1615
self.addCleanup(repo.unlock)
1616
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1617
self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1619
def test_get_keys_excludes_ghosts(self):
1620
builder = self.make_branch_builder('b')
1621
builder.start_series()
1622
builder.build_snapshot('rev-1', None, [
1623
('add', ('', 'root-id', 'directory', ''))])
1624
builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
1625
builder.finish_series()
1626
repo = builder.get_branch().repository
1628
self.addCleanup(repo.unlock)
1629
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1630
self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
1632
def test_get_keys_excludes_null(self):
1633
# Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1634
# somewhere other than the last element, which can happen in real
1636
class StubGraph(object):
1637
def iter_ancestry(self, keys):
1638
return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1639
result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1640
result_keys = result._get_keys(StubGraph())
1641
# Only the non-null keys from the ancestry appear.
1642
self.assertEqual(set(['foo']), set(result_keys))
1645
class TestPendingAncestryResultRefine(TestGraphBase):
1647
def test_refine(self):
1648
# Used when pulling from a stacked repository, so test some revisions
1649
# being satisfied from the stacking branch.
1650
g = self.make_graph(
1651
{"tip":["mid"], "mid":["base"], "tag":["base"],
1652
"base":[NULL_REVISION], NULL_REVISION:[]})
1653
result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1654
result = result.refine(set(['tip']), set(['mid']))
1655
self.assertEqual(set(['mid', 'tag']), result.heads)
1656
result = result.refine(set(['mid', 'tag', 'base']),
1657
set([NULL_REVISION]))
1658
self.assertEqual(set([NULL_REVISION]), result.heads)
1659
self.assertTrue(result.is_empty())
1662
class TestSearchResultRefine(TestGraphBase):
1664
def test_refine(self):
1665
# Used when pulling from a stacked repository, so test some revisions
1666
# being satisfied from the stacking branch.
1667
g = self.make_graph(
1668
{"tip":["mid"], "mid":["base"], "tag":["base"],
1669
"base":[NULL_REVISION], NULL_REVISION:[]})
1670
result = _mod_graph.SearchResult(set(['tip', 'tag']),
1671
set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1672
result = result.refine(set(['tip']), set(['mid']))
1673
recipe = result.get_recipe()
1674
# We should be starting from tag (original head) and mid (seen ref)
1675
self.assertEqual(set(['mid', 'tag']), recipe[1])
1676
# We should be stopping at NULL (original stop) and tip (seen head)
1677
self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1678
self.assertEqual(3, recipe[3])
1679
result = result.refine(set(['mid', 'tag', 'base']),
1680
set([NULL_REVISION]))
1681
recipe = result.get_recipe()
1682
# We should be starting from nothing (NULL was known as a cut point)
1683
self.assertEqual(set([]), recipe[1])
1684
# We should be stopping at NULL (original stop) and tip (seen head) and
1685
# tag (seen head) and mid(seen mid-point head). We could come back and
1686
# define this as not including mid, for minimal results, but it is
1687
# still 'correct' to include mid, and simpler/easier.
1688
self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1689
self.assertEqual(0, recipe[3])
1690
self.assertTrue(result.is_empty())
added
removed
bzrlib/tests/test_graph.py
