1
# Copyright (C) 2007 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23
from bzrlib.revision import NULL_REVISION
24
from bzrlib.tests import TestCaseWithMemoryTransport
38
ancestry_1 = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
39
'rev3': ['rev2a'], 'rev4': ['rev3', 'rev2b']}
53
ancestry_2 = {'rev1a': [NULL_REVISION], 'rev2a': ['rev1a'],
54
'rev1b': [NULL_REVISION], 'rev3a': ['rev2a'], 'rev4a': ['rev3a']}
57
# Criss cross ancestry
68
criss_cross = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
69
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2a']}
83
criss_cross2 = {'rev1a': [NULL_REVISION], 'rev1b': [NULL_REVISION],
84
'rev2a': ['rev1a', 'rev1b'], 'rev2b': ['rev1b', 'rev1a']}
96
mainline = {'rev1': [NULL_REVISION], 'rev2a': ['rev1', 'rev2b'],
109
feature_branch = {'rev1': [NULL_REVISION],
110
'rev2b': ['rev1'], 'rev3b': ['rev2b']}
121
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
122
'rev2b': ['rev1'], 'rev2c': ['rev1'],
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],
237
boundary = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e'], 'e': ['f'],
241
class InstrumentedParentsProvider(object):
243
def __init__(self, parents_provider):
245
self._real_parents_provider = parents_provider
247
def get_parent_map(self, nodes):
248
self.calls.extend(nodes)
249
return self._real_parents_provider.get_parent_map(nodes)
252
class TestGraph(TestCaseWithMemoryTransport):
254
def make_graph(self, ancestors):
255
# XXX: This seems valid, is there a reason to actually create a
256
# repository and put things in it?
257
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
258
tree = self.prepare_memory_tree('.')
259
self.build_ancestry(tree, ancestors)
260
self.addCleanup(tree.unlock)
261
return tree.branch.repository.get_graph()
263
def prepare_memory_tree(self, location):
264
tree = self.make_branch_and_memory_tree(location)
269
def build_ancestry(self, tree, ancestors):
270
"""Create an ancestry as specified by a graph dict
272
:param tree: A tree to use
273
:param ancestors: a dict of {node: [node_parent, ...]}
275
pending = [NULL_REVISION]
277
for descendant, parents in ancestors.iteritems():
278
for parent in parents:
279
descendants.setdefault(parent, []).append(descendant)
280
while len(pending) > 0:
281
cur_node = pending.pop()
282
for descendant in descendants.get(cur_node, []):
283
if tree.branch.repository.has_revision(descendant):
285
parents = [p for p in ancestors[descendant] if p is not
287
if len([p for p in parents if not
288
tree.branch.repository.has_revision(p)]) > 0:
290
tree.set_parent_ids(parents)
292
left_parent = parents[0]
294
left_parent = NULL_REVISION
295
tree.branch.set_last_revision_info(
296
len(tree.branch._lefthand_history(left_parent)),
298
tree.commit(descendant, rev_id=descendant)
299
pending.append(descendant)
302
"""Test finding least common ancestor.
304
ancestry_1 should always have a single common ancestor
306
graph = self.make_graph(ancestry_1)
307
self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
308
self.assertEqual(set([NULL_REVISION]),
309
graph.find_lca(NULL_REVISION, NULL_REVISION))
310
self.assertEqual(set([NULL_REVISION]),
311
graph.find_lca(NULL_REVISION, 'rev1'))
312
self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
313
self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
315
def test_no_unique_lca(self):
316
"""Test error when one revision is not in the graph"""
317
graph = self.make_graph(ancestry_1)
318
self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
321
def test_lca_criss_cross(self):
322
"""Test least-common-ancestor after a criss-cross merge."""
323
graph = self.make_graph(criss_cross)
324
self.assertEqual(set(['rev2a', 'rev2b']),
325
graph.find_lca('rev3a', 'rev3b'))
326
self.assertEqual(set(['rev2b']),
327
graph.find_lca('rev3a', 'rev3b', 'rev2b'))
329
def test_lca_shortcut(self):
330
"""Test least-common ancestor on this history shortcut"""
331
graph = self.make_graph(history_shortcut)
332
self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
334
def test_recursive_unique_lca(self):
335
"""Test finding a unique least common ancestor.
337
ancestry_1 should always have a single common ancestor
339
graph = self.make_graph(ancestry_1)
340
self.assertEqual(NULL_REVISION,
341
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
342
self.assertEqual(NULL_REVISION,
343
graph.find_unique_lca(NULL_REVISION, 'rev1'))
344
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
345
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
346
self.assertEqual(('rev1', 1,),
347
graph.find_unique_lca('rev2a', 'rev2b',
350
def test_unique_lca_criss_cross(self):
351
"""Ensure we don't pick non-unique lcas in a criss-cross"""
352
graph = self.make_graph(criss_cross)
353
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
354
lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
355
self.assertEqual('rev1', lca)
356
self.assertEqual(2, steps)
358
def test_unique_lca_null_revision(self):
359
"""Ensure we pick NULL_REVISION when necessary"""
360
graph = self.make_graph(criss_cross2)
361
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
362
self.assertEqual(NULL_REVISION,
363
graph.find_unique_lca('rev2a', 'rev2b'))
365
def test_unique_lca_null_revision2(self):
366
"""Ensure we pick NULL_REVISION when necessary"""
367
graph = self.make_graph(ancestry_2)
368
self.assertEqual(NULL_REVISION,
369
graph.find_unique_lca('rev4a', 'rev1b'))
371
def test_lca_double_shortcut(self):
372
graph = self.make_graph(double_shortcut)
373
self.assertEqual('c', graph.find_unique_lca('f', 'g'))
375
def test_common_ancestor_two_repos(self):
376
"""Ensure we do unique_lca using data from two repos"""
377
mainline_tree = self.prepare_memory_tree('mainline')
378
self.build_ancestry(mainline_tree, mainline)
379
self.addCleanup(mainline_tree.unlock)
381
# This is cheating, because the revisions in the graph are actually
382
# different revisions, despite having the same revision-id.
383
feature_tree = self.prepare_memory_tree('feature')
384
self.build_ancestry(feature_tree, feature_branch)
385
self.addCleanup(feature_tree.unlock)
387
graph = mainline_tree.branch.repository.get_graph(
388
feature_tree.branch.repository)
389
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
391
def test_graph_difference(self):
392
graph = self.make_graph(ancestry_1)
393
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
394
self.assertEqual((set(), set(['rev1'])),
395
graph.find_difference(NULL_REVISION, 'rev1'))
396
self.assertEqual((set(['rev1']), set()),
397
graph.find_difference('rev1', NULL_REVISION))
398
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
399
graph.find_difference('rev3', 'rev2b'))
400
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
401
graph.find_difference('rev4', 'rev2b'))
403
def test_graph_difference_separate_ancestry(self):
404
graph = self.make_graph(ancestry_2)
405
self.assertEqual((set(['rev1a']), set(['rev1b'])),
406
graph.find_difference('rev1a', 'rev1b'))
407
self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
409
graph.find_difference('rev4a', 'rev1b'))
411
def test_graph_difference_criss_cross(self):
412
graph = self.make_graph(criss_cross)
413
self.assertEqual((set(['rev3a']), set(['rev3b'])),
414
graph.find_difference('rev3a', 'rev3b'))
415
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
416
graph.find_difference('rev2a', 'rev3b'))
418
def test_graph_difference_extended_history(self):
419
graph = self.make_graph(extended_history_shortcut)
420
self.expectFailure('find_difference cannot handle shortcuts',
421
self.assertEqual, (set(['e']), set(['f'])),
422
graph.find_difference('e', 'f'))
423
self.assertEqual((set(['e']), set(['f'])),
424
graph.find_difference('e', 'f'))
425
self.assertEqual((set(['f']), set(['e'])),
426
graph.find_difference('f', 'e'))
428
def test_graph_difference_double_shortcut(self):
429
graph = self.make_graph(double_shortcut)
430
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
431
graph.find_difference('f', 'g'))
433
def test_graph_difference_complex_shortcut(self):
434
graph = self.make_graph(complex_shortcut)
435
self.expectFailure('find_difference cannot handle shortcuts',
436
self.assertEqual, (set(['m']), set(['h', 'n'])),
437
graph.find_difference('m', 'n'))
438
self.assertEqual((set(['m']), set(['h', 'n'])),
439
graph.find_difference('m', 'n'))
441
def test_graph_difference_shortcut_extra_root(self):
442
graph = self.make_graph(shortcut_extra_root)
443
self.expectFailure('find_difference cannot handle shortcuts',
444
self.assertEqual, (set(['e']), set(['f', 'g'])),
445
graph.find_difference('e', 'f'))
446
self.assertEqual((set(['e']), set(['f', 'g'])),
447
graph.find_difference('e', 'f'))
449
def test_stacked_parents_provider(self):
450
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
451
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
452
stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
453
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
454
stacked.get_parent_map(['rev1', 'rev2']))
455
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
456
stacked.get_parent_map(['rev2', 'rev1']))
457
self.assertEqual({'rev2':['rev3']},
458
stacked.get_parent_map(['rev2', 'rev2']))
459
self.assertEqual({'rev1':['rev4']},
460
stacked.get_parent_map(['rev1', 'rev1']))
462
def test_iter_topo_order(self):
463
graph = self.make_graph(ancestry_1)
464
args = ['rev2a', 'rev3', 'rev1']
465
topo_args = list(graph.iter_topo_order(args))
466
self.assertEqual(set(args), set(topo_args))
467
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
468
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
470
def test_is_ancestor(self):
471
graph = self.make_graph(ancestry_1)
472
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
473
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
474
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
475
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
476
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
477
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
478
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
479
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
480
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
481
instrumented_provider = InstrumentedParentsProvider(graph)
482
instrumented_graph = _mod_graph.Graph(instrumented_provider)
483
instrumented_graph.is_ancestor('rev2a', 'rev2b')
484
self.assertTrue('null:' not in instrumented_provider.calls)
486
def test_is_ancestor_boundary(self):
487
"""Ensure that we avoid searching the whole graph.
489
This requires searching through b as a common ancestor, so we
490
can identify that e is common.
492
graph = self.make_graph(boundary)
493
instrumented_provider = InstrumentedParentsProvider(graph)
494
graph = _mod_graph.Graph(instrumented_provider)
495
self.assertFalse(graph.is_ancestor('a', 'c'))
496
self.assertTrue('null:' not in instrumented_provider.calls)
498
def test_filter_candidate_lca(self):
499
"""Test filter_candidate_lca for a corner case
501
This tests the case where we encounter the end of iteration for 'e'
502
in the same pass as we discover that 'd' is an ancestor of 'e', and
503
therefore 'e' can't be an lca.
505
To compensate for different dict orderings on other Python
506
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
508
# This test is sensitive to the iteration order of dicts. It will
509
# pass incorrectly if 'e' and 'a' sort before 'c'
518
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
519
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
520
self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
522
def test_heads_null(self):
523
graph = self.make_graph(ancestry_1)
524
self.assertEqual(set(['null:']), graph.heads(['null:']))
525
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
526
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
527
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
528
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
530
def test_heads_one(self):
531
# A single node will always be a head
532
graph = self.make_graph(ancestry_1)
533
self.assertEqual(set(['null:']), graph.heads(['null:']))
534
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
535
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
536
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
537
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
538
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
540
def test_heads_single(self):
541
graph = self.make_graph(ancestry_1)
542
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
543
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
544
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
545
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
546
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
547
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
548
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
549
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
551
def test_heads_two_heads(self):
552
graph = self.make_graph(ancestry_1)
553
self.assertEqual(set(['rev2a', 'rev2b']),
554
graph.heads(['rev2a', 'rev2b']))
555
self.assertEqual(set(['rev3', 'rev2b']),
556
graph.heads(['rev3', 'rev2b']))
558
def test_heads_criss_cross(self):
559
graph = self.make_graph(criss_cross)
560
self.assertEqual(set(['rev2a']),
561
graph.heads(['rev2a', 'rev1']))
562
self.assertEqual(set(['rev2b']),
563
graph.heads(['rev2b', 'rev1']))
564
self.assertEqual(set(['rev3a']),
565
graph.heads(['rev3a', 'rev1']))
566
self.assertEqual(set(['rev3b']),
567
graph.heads(['rev3b', 'rev1']))
568
self.assertEqual(set(['rev2a', 'rev2b']),
569
graph.heads(['rev2a', 'rev2b']))
570
self.assertEqual(set(['rev3a']),
571
graph.heads(['rev3a', 'rev2a']))
572
self.assertEqual(set(['rev3a']),
573
graph.heads(['rev3a', 'rev2b']))
574
self.assertEqual(set(['rev3a']),
575
graph.heads(['rev3a', 'rev2a', 'rev2b']))
576
self.assertEqual(set(['rev3b']),
577
graph.heads(['rev3b', 'rev2a']))
578
self.assertEqual(set(['rev3b']),
579
graph.heads(['rev3b', 'rev2b']))
580
self.assertEqual(set(['rev3b']),
581
graph.heads(['rev3b', 'rev2a', 'rev2b']))
582
self.assertEqual(set(['rev3a', 'rev3b']),
583
graph.heads(['rev3a', 'rev3b']))
584
self.assertEqual(set(['rev3a', 'rev3b']),
585
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
587
def test_heads_shortcut(self):
588
graph = self.make_graph(history_shortcut)
590
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
591
graph.heads(['rev2a', 'rev2b', 'rev2c']))
592
self.assertEqual(set(['rev3a', 'rev3b']),
593
graph.heads(['rev3a', 'rev3b']))
594
self.assertEqual(set(['rev3a', 'rev3b']),
595
graph.heads(['rev2a', 'rev3a', 'rev3b']))
596
self.assertEqual(set(['rev2a', 'rev3b']),
597
graph.heads(['rev2a', 'rev3b']))
598
self.assertEqual(set(['rev2c', 'rev3a']),
599
graph.heads(['rev2c', 'rev3a']))
601
def _run_heads_break_deeper(self, graph_dict, search):
602
"""Run heads on a graph-as-a-dict.
604
If the search asks for the parents of 'deeper' the test will fail.
608
def get_parent_map(keys):
612
self.fail('key deeper was accessed')
613
result[key] = graph_dict[key]
616
an_obj.get_parent_map = get_parent_map
617
graph = _mod_graph.Graph(an_obj)
618
return graph.heads(search)
620
def test_heads_limits_search(self):
621
# test that a heads query does not search all of history
627
self.assertEqual(set(['left', 'right']),
628
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
630
def test_heads_limits_search_assymetric(self):
631
# test that a heads query does not search all of history
634
'midleft':['common'],
636
'common':['aftercommon'],
637
'aftercommon':['deeper'],
639
self.assertEqual(set(['left', 'right']),
640
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
642
def test_heads_limits_search_common_search_must_continue(self):
643
# test that common nodes are still queried, preventing
644
# all-the-way-to-origin behaviour in the following graph:
646
'h1':['shortcut', 'common1'],
648
'shortcut':['common2'],
649
'common1':['common2'],
650
'common2':['deeper'],
652
self.assertEqual(set(['h1', 'h2']),
653
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
656
class TestCachingParentsProvider(tests.TestCase):
659
super(TestCachingParentsProvider, self).setUp()
660
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
661
self.inst_pp = InstrumentedParentsProvider(dict_pp)
662
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
664
def test_get_parent_map(self):
665
"""Requesting the same revision should be returned from cache"""
666
self.assertEqual({}, self.caching_pp._cache)
667
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
668
self.assertEqual(['a'], self.inst_pp.calls)
669
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
670
# No new call, as it should have been returned from the cache
671
self.assertEqual(['a'], self.inst_pp.calls)
672
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
674
def test_get_parent_map_not_present(self):
675
"""The cache should also track when a revision doesn't exist"""
676
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
677
self.assertEqual(['b'], self.inst_pp.calls)
678
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
680
self.assertEqual(['b'], self.inst_pp.calls)
681
self.assertEqual({'b':None}, self.caching_pp._cache)
683
def test_get_parent_map_mixed(self):
684
"""Anything that can be returned from cache, should be"""
685
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
686
self.assertEqual(['b'], self.inst_pp.calls)
687
self.assertEqual({'a':('b',)},
688
self.caching_pp.get_parent_map(['a', 'b']))
689
self.assertEqual(['b', 'a'], self.inst_pp.calls)
691
def test_get_parent_map_repeated(self):
692
"""Asking for the same parent 2x will only forward 1 request."""
693
self.assertEqual({'a':('b',)},
694
self.caching_pp.get_parent_map(['b', 'a', 'b']))
695
# Use sorted because we don't care about the order, just that each is
696
# only present 1 time.
697
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
added
removed
bzrlib/tests/test_graph.py
