116
118
# rev2a rev2b rev2c
119
121
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
120
122
'rev2b': ['rev1'], 'rev2c': ['rev1'],
121
123
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
125
# Extended history shortcut
137
extended_history_shortcut = {'a': [NULL_REVISION],
146
# Both sides will see 'A' first, even though it is actually a decendent of a
147
# different common revision.
161
double_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
162
'd':['c'], 'e':['c'], 'f':['a', 'd'],
166
# This has a failure mode in that a shortcut will find some nodes in common,
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
169
# walking off the graph. Specifically, node G should be considered common, but
170
# is likely to be seen by M long before the common searcher finds it.
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'],
204
# Shortcut with extra root
205
# We have a long history shortcut, and an extra root, which is why we can't
206
# stop searchers based on seeing NULL_REVISION
218
shortcut_extra_root = {'a': [NULL_REVISION],
223
'f': ['a', 'd', 'g'],
224
'g': [NULL_REVISION],
144
248
self.calls.extend(nodes)
145
249
return self._real_parents_provider.get_parents(nodes)
148
class DictParentsProvider(object):
150
def __init__(self, ancestry):
151
self.ancestry = ancestry
154
return 'DictParentsProvider(%r)' % self.ancestry
156
def get_parents(self, revisions):
157
return [self.ancestry.get(r, None) for r in revisions]
251
def get_parent_map(self, nodes):
252
self.calls.extend(nodes)
253
return self._real_parents_provider.get_parent_map(nodes)
160
256
class TestGraph(TestCaseWithMemoryTransport):
162
258
def make_graph(self, ancestors):
259
# XXX: This seems valid, is there a reason to actually create a
260
# repository and put things in it?
261
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
163
262
tree = self.prepare_memory_tree('.')
164
263
self.build_ancestry(tree, ancestors)
264
self.addCleanup(tree.unlock)
166
265
return tree.branch.repository.get_graph()
168
267
def prepare_memory_tree(self, location):
248
347
graph.find_unique_lca(NULL_REVISION, 'rev1'))
249
348
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
250
349
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
350
self.assertEqual(('rev1', 1,),
351
graph.find_unique_lca('rev2a', 'rev2b',
252
354
def test_unique_lca_criss_cross(self):
253
355
"""Ensure we don't pick non-unique lcas in a criss-cross"""
254
356
graph = self.make_graph(criss_cross)
255
357
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
358
lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
359
self.assertEqual('rev1', lca)
360
self.assertEqual(2, steps)
257
362
def test_unique_lca_null_revision(self):
258
363
"""Ensure we pick NULL_REVISION when necessary"""
267
372
self.assertEqual(NULL_REVISION,
268
373
graph.find_unique_lca('rev4a', 'rev1b'))
375
def test_lca_double_shortcut(self):
376
graph = self.make_graph(double_shortcut)
377
self.assertEqual('c', graph.find_unique_lca('f', 'g'))
270
379
def test_common_ancestor_two_repos(self):
271
380
"""Ensure we do unique_lca using data from two repos"""
272
381
mainline_tree = self.prepare_memory_tree('mainline')
273
382
self.build_ancestry(mainline_tree, mainline)
274
mainline_tree.unlock()
383
self.addCleanup(mainline_tree.unlock)
276
385
# This is cheating, because the revisions in the graph are actually
277
386
# different revisions, despite having the same revision-id.
278
387
feature_tree = self.prepare_memory_tree('feature')
279
388
self.build_ancestry(feature_tree, feature_branch)
280
feature_tree.unlock()
389
self.addCleanup(feature_tree.unlock)
281
391
graph = mainline_tree.branch.repository.get_graph(
282
392
feature_tree.branch.repository)
283
393
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
294
404
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
295
405
graph.find_difference('rev4', 'rev2b'))
407
def test_graph_difference_separate_ancestry(self):
408
graph = self.make_graph(ancestry_2)
409
self.assertEqual((set(['rev1a']), set(['rev1b'])),
410
graph.find_difference('rev1a', 'rev1b'))
411
self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
413
graph.find_difference('rev4a', 'rev1b'))
297
415
def test_graph_difference_criss_cross(self):
298
416
graph = self.make_graph(criss_cross)
299
417
self.assertEqual((set(['rev3a']), set(['rev3b'])),
301
419
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
302
420
graph.find_difference('rev2a', 'rev3b'))
304
def test_stacked_parents_provider(self):
306
parents1 = DictParentsProvider({'rev2': ['rev3']})
307
parents2 = DictParentsProvider({'rev1': ['rev4']})
422
def test_graph_difference_extended_history(self):
423
graph = self.make_graph(extended_history_shortcut)
424
self.expectFailure('find_difference cannot handle shortcuts',
425
self.assertEqual, (set(['e']), set(['f'])),
426
graph.find_difference('e', 'f'))
427
self.assertEqual((set(['e']), set(['f'])),
428
graph.find_difference('e', 'f'))
429
self.assertEqual((set(['f']), set(['e'])),
430
graph.find_difference('f', 'e'))
432
def test_graph_difference_double_shortcut(self):
433
graph = self.make_graph(double_shortcut)
434
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
435
graph.find_difference('f', 'g'))
437
def test_graph_difference_complex_shortcut(self):
438
graph = self.make_graph(complex_shortcut)
439
self.expectFailure('find_difference cannot handle shortcuts',
440
self.assertEqual, (set(['m']), set(['h', 'n'])),
441
graph.find_difference('m', 'n'))
442
self.assertEqual((set(['m']), set(['h', 'n'])),
443
graph.find_difference('m', 'n'))
445
def test_graph_difference_shortcut_extra_root(self):
446
graph = self.make_graph(shortcut_extra_root)
447
self.expectFailure('find_difference cannot handle shortcuts',
448
self.assertEqual, (set(['e']), set(['f', 'g'])),
449
graph.find_difference('e', 'f'))
450
self.assertEqual((set(['e']), set(['f', 'g'])),
451
graph.find_difference('e', 'f'))
453
def test_stacked_parents_provider_get_parents(self):
454
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
455
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
308
456
stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
309
457
self.assertEqual([['rev4',], ['rev3']],
310
stacked.get_parents(['rev1', 'rev2']))
458
self.applyDeprecated(symbol_versioning.one_one,
459
stacked.get_parents, ['rev1', 'rev2']))
311
460
self.assertEqual([['rev3',], ['rev4']],
312
stacked.get_parents(['rev2', 'rev1']))
461
self.applyDeprecated(symbol_versioning.one_one,
462
stacked.get_parents, ['rev2', 'rev1']))
313
463
self.assertEqual([['rev3',], ['rev3']],
314
stacked.get_parents(['rev2', 'rev2']))
464
self.applyDeprecated(symbol_versioning.one_one,
465
stacked.get_parents, ['rev2', 'rev2']))
315
466
self.assertEqual([['rev4',], ['rev4']],
316
stacked.get_parents(['rev1', 'rev1']))
467
self.applyDeprecated(symbol_versioning.one_one,
468
stacked.get_parents, ['rev1', 'rev1']))
470
def test_stacked_parents_provider(self):
471
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
472
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
473
stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
474
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
475
stacked.get_parent_map(['rev1', 'rev2']))
476
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
477
stacked.get_parent_map(['rev2', 'rev1']))
478
self.assertEqual({'rev2':['rev3']},
479
stacked.get_parent_map(['rev2', 'rev2']))
480
self.assertEqual({'rev1':['rev4']},
481
stacked.get_parent_map(['rev1', 'rev1']))
318
483
def test_iter_topo_order(self):
319
484
graph = self.make_graph(ancestry_1)
508
681
self.assertEqual(set(['h1', 'h2']),
509
682
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
685
class TestCachingParentsProvider(tests.TestCase):
688
super(TestCachingParentsProvider, self).setUp()
689
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
690
self.inst_pp = InstrumentedParentsProvider(dict_pp)
691
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
693
def test_get_parents(self):
694
"""Requesting the same revision should be returned from cache"""
695
self.assertEqual({}, self.caching_pp._cache)
696
self.assertEqual([('b',)],
697
self.applyDeprecated(symbol_versioning.one_one,
698
self.caching_pp.get_parents, ['a']))
699
self.assertEqual(['a'], self.inst_pp.calls)
700
self.assertEqual([('b',)],
701
self.applyDeprecated(symbol_versioning.one_one,
702
self.caching_pp.get_parents, ['a']))
703
# No new call, as it should have been returned from the cache
704
self.assertEqual(['a'], self.inst_pp.calls)
705
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
707
def test_get_parent_map(self):
708
"""Requesting the same revision should be returned from cache"""
709
self.assertEqual({}, self.caching_pp._cache)
710
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
711
self.assertEqual(['a'], self.inst_pp.calls)
712
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
713
# No new call, as it should have been returned from the cache
714
self.assertEqual(['a'], self.inst_pp.calls)
715
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
717
def test_get_parent_map_not_present(self):
718
"""The cache should also track when a revision doesn't exist"""
719
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
720
self.assertEqual(['b'], self.inst_pp.calls)
721
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
723
self.assertEqual(['b'], self.inst_pp.calls)
724
self.assertEqual({'b':None}, self.caching_pp._cache)
726
def test_get_parent_map_mixed(self):
727
"""Anything that can be returned from cache, should be"""
728
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
729
self.assertEqual(['b'], self.inst_pp.calls)
730
self.assertEqual({'a':('b',)},
731
self.caching_pp.get_parent_map(['a', 'b']))
732
self.assertEqual(['b', 'a'], self.inst_pp.calls)
734
def test_get_parent_map_repeated(self):
735
"""Asking for the same parent 2x will only forward 1 request."""
736
self.assertEqual({'a':('b',)},
737
self.caching_pp.get_parent_map(['b', 'a', 'b']))
738
# Use sorted because we don't care about the order, just that each is
739
# only present 1 time.
740
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
added
removed
bzrlib/tests/test_graph.py
