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