/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

Merge bzr.dev and resolve conflicts.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
165
165
# Complex shortcut
166
166
# This has a failure mode in that a shortcut will find some nodes in common,
167
167
# but the common searcher won't have time to find that one branch is actually
168
 
# in common. The extra nodes at the top are because we want to avoid
 
168
# in common. The extra nodes at the beginning are because we want to avoid
169
169
# walking off the graph. Specifically, node G should be considered common, but
170
170
# is likely to be seen by M long before the common searcher finds it.
171
171
#
181
181
#     |\
182
182
#     e f
183
183
#     | |\
184
 
#     i | h
185
 
#     |\| |
186
 
#     | g |
187
 
#     | | |
188
 
#     | j |
 
184
#     | g h
 
185
#     |/| |
 
186
#     i j |
189
187
#     | | |
190
188
#     | k |
191
189
#     | | |
192
190
#     | l |
193
191
#     |/|/
194
192
#     m n
195
 
complex_shortcut = {'d':[NULL_REVISION],
196
 
                    'x':['d'], 'y':['x'],
197
 
                    'e':['y'], 'f':['d'], 'g':['f', 'i'], 'h':['f'],
198
 
                    'i':['e'], 'j':['g'], 'k':['j'],
199
 
                    'l':['k'], 'm':['i', 's'], 'n':['s', 'h'],
200
 
                    'o':['l'], 'p':['o'], 'q':['p'],
201
 
                    'r':['q'], 's':['r'],
 
193
complex_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
 
194
                    'e':['d'], 'f':['d'], 'g':['f'], 'h':['f'],
 
195
                    'i':['e', 'g'], 'j':['g'], 'k':['j'],
 
196
                    'l':['k'], 'm':['i', 'l'], 'n':['l', 'h']}
 
197
 
 
198
# NULL_REVISION
 
199
#     |
 
200
#     a
 
201
#     |
 
202
#     b
 
203
#     |
 
204
#     c
 
205
#     |
 
206
#     d
 
207
#     |\
 
208
#     e |
 
209
#     | |
 
210
#     f |
 
211
#     | |
 
212
#     g h
 
213
#     | |\
 
214
#     i | j
 
215
#     |\| |
 
216
#     | k |
 
217
#     | | |
 
218
#     | l |
 
219
#     | | |
 
220
#     | m |
 
221
#     | | |
 
222
#     | n |
 
223
#     | | |
 
224
#     | o |
 
225
#     | | |
 
226
#     | p |
 
227
#     | | |
 
228
#     | q |
 
229
#     | | |
 
230
#     | r |
 
231
#     | | |
 
232
#     | s |
 
233
#     | | |
 
234
#     |/|/
 
235
#     t u
 
236
complex_shortcut2 = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
 
237
                    'e':['d'], 'f':['e'], 'g':['f'], 'h':['d'], 'i':['g'],
 
238
                    'j':['h'], 'k':['h', 'i'], 'l':['k'], 'm':['l'], 'n':['m'],
 
239
                    'o':['n'], 'p':['o'], 'q':['p'], 'r':['q'], 's':['r'],
 
240
                    't':['i', 's'], 'u':['s', 'j'], 
202
241
                    }
203
242
 
 
243
# Graph where different walkers will race to find the common and uncommon
 
244
# nodes.
 
245
#
 
246
# NULL_REVISION
 
247
#     |
 
248
#     a
 
249
#     |
 
250
#     b
 
251
#     |
 
252
#     c
 
253
#     |
 
254
#     d
 
255
#     |\
 
256
#     e k
 
257
#     | |
 
258
#     f-+-p
 
259
#     | | |
 
260
#     | l |
 
261
#     | | |
 
262
#     | m |
 
263
#     | |\|
 
264
#     g n q
 
265
#     |\| |
 
266
#     h o |
 
267
#     |/| |
 
268
#     i r |
 
269
#     | | |
 
270
#     | s |
 
271
#     | | |
 
272
#     | t |
 
273
#     | | |
 
274
#     | u |
 
275
#     | | |
 
276
#     | v |
 
277
#     | | |
 
278
#     | w |
 
279
#     | | |
 
280
#     | x |
 
281
#     | |\|
 
282
#     | y z
 
283
#     |/
 
284
#     j
 
285
#
 
286
# x is found to be common right away, but is the start of a long series of
 
287
# common commits.
 
288
# o is actually common, but the i-j shortcut makes it look like it is actually
 
289
# unique to j at first, you have to traverse all of x->o to find it.
 
290
# q,m gives the walker from j a common point to stop searching, as does p,f.
 
291
# k-n exists so that the second pass still has nodes that are worth searching,
 
292
# rather than instantly cancelling the extra walker.
 
293
 
 
294
racing_shortcuts = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
 
295
    'e':['d'], 'f':['e'], 'g':['f'], 'h':['g'], 'i':['h', 'o'], 'j':['i', 'y'],
 
296
    'k':['d'], 'l':['k'], 'm':['l'], 'n':['m'], 'o':['n', 'g'], 'p':['f'],
 
297
    'q':['p', 'm'], 'r':['o'], 's':['r'], 't':['s'], 'u':['t'], 'v':['u'],
 
298
    'w':['v'], 'x':['w'], 'y':['x'], 'z':['x', 'q']}
 
299
 
 
300
 
 
301
# A graph with multiple nodes unique to one side.
 
302
#
 
303
# NULL_REVISION
 
304
#     |
 
305
#     a
 
306
#     |
 
307
#     b
 
308
#     |
 
309
#     c
 
310
#     |
 
311
#     d
 
312
#     |\
 
313
#     e f
 
314
#     |\ \
 
315
#     g h i
 
316
#     |\ \ \
 
317
#     j k l m
 
318
#     | |/ x|
 
319
#     | n o p
 
320
#     | |/  |
 
321
#     | q   |
 
322
#     | |   |
 
323
#     | r   |
 
324
#     | |   |
 
325
#     | s   |
 
326
#     | |   |
 
327
#     | t   |
 
328
#     | |   |
 
329
#     | u   |
 
330
#     | |   |
 
331
#     | v   |
 
332
#     | |   |
 
333
#     | w   |
 
334
#     | |   |
 
335
#     | x   |
 
336
#     |/ \ /
 
337
#     y   z
 
338
#
 
339
 
 
340
multiple_interesting_unique = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
 
341
    'd':['c'], 'e':['d'], 'f':['d'], 'g':['e'], 'h':['e'], 'i':['f'],
 
342
    'j':['g'], 'k':['g'], 'l':['h'], 'm':['i'], 'n':['k', 'l'],
 
343
    'o':['m'], 'p':['m', 'l'], 'q':['n', 'o'], 'r':['q'], 's':['r'],
 
344
    't':['s'], 'u':['t'], 'v':['u'], 'w':['v'], 'x':['w'],
 
345
    'y':['j', 'x'], 'z':['x', 'p']}
 
346
 
 
347
 
204
348
# Shortcut with extra root
205
349
# We have a long history shortcut, and an extra root, which is why we can't
206
350
# stop searchers based on seeing NULL_REVISION
252
396
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
253
397
              'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
254
398
 
 
399
# A graph that shows we can shortcut finding revnos when reaching them from the
 
400
# side.
 
401
#  NULL_REVISION
 
402
#       |
 
403
#       a
 
404
#       |
 
405
#       b
 
406
#       |
 
407
#       c
 
408
#       |
 
409
#       d
 
410
#       |
 
411
#       e
 
412
#      / \
 
413
#     f   g
 
414
#     |
 
415
#     h
 
416
#     |
 
417
#     i
 
418
 
 
419
with_tail = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'], 'e':['d'],
 
420
             'f':['e'], 'g':['e'], 'h':['f'], 'i':['h']}
255
421
 
256
422
 
257
423
class InstrumentedParentsProvider(object):
265
431
        return self._real_parents_provider.get_parent_map(nodes)
266
432
 
267
433
 
 
434
class TestGraphBase(tests.TestCase):
 
435
 
 
436
    def make_graph(self, ancestors):
 
437
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
 
438
 
 
439
    def make_breaking_graph(self, ancestors, break_on):
 
440
        """Make a Graph that raises an exception if we hit a node."""
 
441
        g = self.make_graph(ancestors)
 
442
        orig_parent_map = g.get_parent_map
 
443
        def get_parent_map(keys):
 
444
            bad_keys = set(keys).intersection(break_on)
 
445
            if bad_keys:
 
446
                self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
 
447
            return orig_parent_map(keys)
 
448
        g.get_parent_map = get_parent_map
 
449
        return g
 
450
 
 
451
 
268
452
class TestGraph(TestCaseWithMemoryTransport):
269
453
 
270
454
    def make_graph(self, ancestors):
357
541
                         graph.find_unique_lca('rev2a', 'rev2b',
358
542
                         count_steps=True))
359
543
 
 
544
    def assertRemoveDescendants(self, expected, graph, revisions):
 
545
        parents = graph.get_parent_map(revisions)
 
546
        self.assertEqual(expected,
 
547
                         graph._remove_simple_descendants(revisions, parents))
 
548
 
 
549
    def test__remove_simple_descendants(self):
 
550
        graph = self.make_graph(ancestry_1)
 
551
        self.assertRemoveDescendants(set(['rev1']), graph,
 
552
            set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']))
 
553
 
 
554
    def test__remove_simple_descendants_disjoint(self):
 
555
        graph = self.make_graph(ancestry_1)
 
556
        self.assertRemoveDescendants(set(['rev1', 'rev3']), graph,
 
557
            set(['rev1', 'rev3']))
 
558
 
 
559
    def test__remove_simple_descendants_chain(self):
 
560
        graph = self.make_graph(ancestry_1)
 
561
        self.assertRemoveDescendants(set(['rev1']), graph,
 
562
            set(['rev1', 'rev2a', 'rev3']))
 
563
 
 
564
    def test__remove_simple_descendants_siblings(self):
 
565
        graph = self.make_graph(ancestry_1)
 
566
        self.assertRemoveDescendants(set(['rev2a', 'rev2b']), graph,
 
567
            set(['rev2a', 'rev2b', 'rev3']))
 
568
 
360
569
    def test_unique_lca_criss_cross(self):
361
570
        """Ensure we don't pick non-unique lcas in a criss-cross"""
362
571
        graph = self.make_graph(criss_cross)
427
636
 
428
637
    def test_graph_difference_extended_history(self):
429
638
        graph = self.make_graph(extended_history_shortcut)
430
 
        self.expectFailure('find_difference cannot handle shortcuts',
431
 
            self.assertEqual, (set(['e']), set(['f'])),
432
 
                graph.find_difference('e', 'f'))
433
639
        self.assertEqual((set(['e']), set(['f'])),
434
640
                         graph.find_difference('e', 'f'))
435
641
        self.assertEqual((set(['f']), set(['e'])),
442
648
 
443
649
    def test_graph_difference_complex_shortcut(self):
444
650
        graph = self.make_graph(complex_shortcut)
445
 
        self.expectFailure('find_difference cannot handle shortcuts',
446
 
            self.assertEqual, (set(['m']), set(['h', 'n'])),
447
 
                graph.find_difference('m', 'n'))
448
 
        self.assertEqual((set(['m']), set(['h', 'n'])),
 
651
        self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
449
652
                         graph.find_difference('m', 'n'))
450
653
 
 
654
    def test_graph_difference_complex_shortcut2(self):
 
655
        graph = self.make_graph(complex_shortcut2)
 
656
        self.assertEqual((set(['t']), set(['j', 'u'])),
 
657
                         graph.find_difference('t', 'u'))
 
658
 
451
659
    def test_graph_difference_shortcut_extra_root(self):
452
660
        graph = self.make_graph(shortcut_extra_root)
453
 
        self.expectFailure('find_difference cannot handle shortcuts',
454
 
            self.assertEqual, (set(['e']), set(['f', 'g'])),
455
 
                graph.find_difference('e', 'f'))
456
661
        self.assertEqual((set(['e']), set(['f', 'g'])),
457
662
                         graph.find_difference('e', 'f'))
458
663
 
973
1178
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
974
1179
 
975
1180
 
 
1181
class TestFindUniqueAncestors(TestGraphBase):
 
1182
 
 
1183
    def assertFindUniqueAncestors(self, graph, expected, node, common):
 
1184
        actual = graph.find_unique_ancestors(node, common)
 
1185
        self.assertEqual(expected, sorted(actual))
 
1186
 
 
1187
    def test_empty_set(self):
 
1188
        graph = self.make_graph(ancestry_1)
 
1189
        self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
 
1190
        self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
 
1191
        self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
 
1192
 
 
1193
    def test_single_node(self):
 
1194
        graph = self.make_graph(ancestry_1)
 
1195
        self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
 
1196
        self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
 
1197
        self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
 
1198
 
 
1199
    def test_minimal_ancestry(self):
 
1200
        graph = self.make_breaking_graph(extended_history_shortcut,
 
1201
                                         [NULL_REVISION, 'a', 'b'])
 
1202
        self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
 
1203
 
 
1204
        graph = self.make_breaking_graph(extended_history_shortcut,
 
1205
                                         ['b'])
 
1206
        self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
 
1207
 
 
1208
        graph = self.make_breaking_graph(complex_shortcut,
 
1209
                                         ['a', 'b'])
 
1210
        self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
 
1211
        self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
 
1212
        self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
 
1213
        self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
 
1214
 
 
1215
    def test_in_ancestry(self):
 
1216
        graph = self.make_graph(ancestry_1)
 
1217
        self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
 
1218
        self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
 
1219
 
 
1220
    def test_multiple_revisions(self):
 
1221
        graph = self.make_graph(ancestry_1)
 
1222
        self.assertFindUniqueAncestors(graph,
 
1223
            ['rev4'], 'rev4', ['rev3', 'rev2b'])
 
1224
        self.assertFindUniqueAncestors(graph,
 
1225
            ['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
 
1226
 
 
1227
    def test_complex_shortcut(self):
 
1228
        graph = self.make_graph(complex_shortcut)
 
1229
        self.assertFindUniqueAncestors(graph,
 
1230
            ['h', 'n'], 'n', ['m'])
 
1231
        self.assertFindUniqueAncestors(graph,
 
1232
            ['e', 'i', 'm'], 'm', ['n'])
 
1233
 
 
1234
    def test_complex_shortcut2(self):
 
1235
        graph = self.make_graph(complex_shortcut2)
 
1236
        self.assertFindUniqueAncestors(graph,
 
1237
            ['j', 'u'], 'u', ['t'])
 
1238
        self.assertFindUniqueAncestors(graph,
 
1239
            ['t'], 't', ['u'])
 
1240
 
 
1241
    def test_multiple_interesting_unique(self):
 
1242
        graph = self.make_graph(multiple_interesting_unique)
 
1243
        self.assertFindUniqueAncestors(graph,
 
1244
            ['j', 'y'], 'y', ['z'])
 
1245
        self.assertFindUniqueAncestors(graph,
 
1246
            ['p', 'z'], 'z', ['y'])
 
1247
 
 
1248
    def test_racing_shortcuts(self):
 
1249
        graph = self.make_graph(racing_shortcuts)
 
1250
        self.assertFindUniqueAncestors(graph,
 
1251
            ['p', 'q', 'z'], 'z', ['y'])
 
1252
        self.assertFindUniqueAncestors(graph,
 
1253
            ['h', 'i', 'j', 'y'], 'j', ['z'])
 
1254
 
 
1255
 
 
1256
class TestGraphFindDistanceToNull(TestGraphBase):
 
1257
    """Test an api that should be able to compute a revno"""
 
1258
 
 
1259
    def assertFindDistance(self, revno, graph, target_id, known_ids):
 
1260
        """Assert the output of Graph.find_distance_to_null()"""
 
1261
        actual = graph.find_distance_to_null(target_id, known_ids)
 
1262
        self.assertEqual(revno, actual)
 
1263
 
 
1264
    def test_nothing_known(self):
 
1265
        graph = self.make_graph(ancestry_1)
 
1266
        self.assertFindDistance(0, graph, NULL_REVISION, [])
 
1267
        self.assertFindDistance(1, graph, 'rev1', [])
 
1268
        self.assertFindDistance(2, graph, 'rev2a', [])
 
1269
        self.assertFindDistance(2, graph, 'rev2b', [])
 
1270
        self.assertFindDistance(3, graph, 'rev3', [])
 
1271
        self.assertFindDistance(4, graph, 'rev4', [])
 
1272
 
 
1273
    def test_rev_is_ghost(self):
 
1274
        graph = self.make_graph(ancestry_1)
 
1275
        e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
 
1276
                              graph.find_distance_to_null, 'rev_missing', [])
 
1277
        self.assertEqual('rev_missing', e.revision_id)
 
1278
        self.assertEqual('rev_missing', e.ghost_revision_id)
 
1279
 
 
1280
    def test_ancestor_is_ghost(self):
 
1281
        graph = self.make_graph({'rev':['parent']})
 
1282
        e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
 
1283
                              graph.find_distance_to_null, 'rev', [])
 
1284
        self.assertEqual('rev', e.revision_id)
 
1285
        self.assertEqual('parent', e.ghost_revision_id)
 
1286
 
 
1287
    def test_known_in_ancestry(self):
 
1288
        graph = self.make_graph(ancestry_1)
 
1289
        self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
 
1290
        self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
 
1291
 
 
1292
    def test_known_in_ancestry_limits(self):
 
1293
        graph = self.make_breaking_graph(ancestry_1, ['rev1'])
 
1294
        self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
 
1295
 
 
1296
    def test_target_is_ancestor(self):
 
1297
        graph = self.make_graph(ancestry_1)
 
1298
        self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
 
1299
 
 
1300
    def test_target_is_ancestor_limits(self):
 
1301
        """We shouldn't search all history if we run into ourselves"""
 
1302
        graph = self.make_breaking_graph(ancestry_1, ['rev1'])
 
1303
        self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
 
1304
 
 
1305
    def test_target_parallel_to_known_limits(self):
 
1306
        # Even though the known revision isn't part of the other ancestry, they
 
1307
        # eventually converge
 
1308
        graph = self.make_breaking_graph(with_tail, ['a'])
 
1309
        self.assertFindDistance(6, graph, 'f', [('g', 6)])
 
1310
        self.assertFindDistance(7, graph, 'h', [('g', 6)])
 
1311
        self.assertFindDistance(8, graph, 'i', [('g', 6)])
 
1312
        self.assertFindDistance(6, graph, 'g', [('i', 8)])
 
1313
 
 
1314
 
976
1315
class TestCachingParentsProvider(tests.TestCase):
977
1316
 
978
1317
    def setUp(self):