1
# Copyright (C) 2007, 2008, 2009 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
23
from bzrlib.revision import NULL_REVISION
24
from bzrlib.tests import TestCaseWithMemoryTransport
25
from bzrlib.symbol_versioning import deprecated_in
39
ancestry_1 = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
40
'rev3': ['rev2a'], 'rev4': ['rev3', 'rev2b']}
54
ancestry_2 = {'rev1a': [NULL_REVISION], 'rev2a': ['rev1a'],
55
'rev1b': [NULL_REVISION], 'rev3a': ['rev2a'], 'rev4a': ['rev3a']}
58
# Criss cross ancestry
69
criss_cross = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
70
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2a']}
84
criss_cross2 = {'rev1a': [NULL_REVISION], 'rev1b': [NULL_REVISION],
85
'rev2a': ['rev1a', 'rev1b'], 'rev2b': ['rev1b', 'rev1a']}
97
mainline = {'rev1': [NULL_REVISION], 'rev2a': ['rev1', 'rev2b'],
110
feature_branch = {'rev1': [NULL_REVISION],
111
'rev2b': ['rev1'], 'rev3b': ['rev2b']}
122
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
123
'rev2b': ['rev1'], 'rev2c': ['rev1'],
124
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
126
# Extended history shortcut
138
extended_history_shortcut = {'a': [NULL_REVISION],
147
# Both sides will see 'A' first, even though it is actually a decendent of a
148
# different common revision.
162
double_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
163
'd':['c'], 'e':['c'], 'f':['a', 'd'],
167
# This has a failure mode in that a shortcut will find some nodes in common,
168
# but the common searcher won't have time to find that one branch is actually
169
# in common. The extra nodes at the beginning are because we want to avoid
170
# walking off the graph. Specifically, node G should be considered common, but
171
# is likely to be seen by M long before the common searcher finds it.
194
complex_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
195
'e':['d'], 'f':['d'], 'g':['f'], 'h':['f'],
196
'i':['e', 'g'], 'j':['g'], 'k':['j'],
197
'l':['k'], 'm':['i', 'l'], 'n':['l', 'h']}
237
complex_shortcut2 = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
238
'e':['d'], 'f':['e'], 'g':['f'], 'h':['d'], 'i':['g'],
239
'j':['h'], 'k':['h', 'i'], 'l':['k'], 'm':['l'], 'n':['m'],
240
'o':['n'], 'p':['o'], 'q':['p'], 'r':['q'], 's':['r'],
241
't':['i', 's'], 'u':['s', 'j'],
244
# Graph where different walkers will race to find the common and uncommon
287
# x is found to be common right away, but is the start of a long series of
289
# o is actually common, but the i-j shortcut makes it look like it is actually
290
# unique to j at first, you have to traverse all of x->o to find it.
291
# q,m gives the walker from j a common point to stop searching, as does p,f.
292
# k-n exists so that the second pass still has nodes that are worth searching,
293
# rather than instantly cancelling the extra walker.
295
racing_shortcuts = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
296
'e':['d'], 'f':['e'], 'g':['f'], 'h':['g'], 'i':['h', 'o'], 'j':['i', 'y'],
297
'k':['d'], 'l':['k'], 'm':['l'], 'n':['m'], 'o':['n', 'g'], 'p':['f'],
298
'q':['p', 'm'], 'r':['o'], 's':['r'], 't':['s'], 'u':['t'], 'v':['u'],
299
'w':['v'], 'x':['w'], 'y':['x'], 'z':['x', 'q']}
302
# A graph with multiple nodes unique to one side.
341
multiple_interesting_unique = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
342
'd':['c'], 'e':['d'], 'f':['d'], 'g':['e'], 'h':['e'], 'i':['f'],
343
'j':['g'], 'k':['g'], 'l':['h'], 'm':['i'], 'n':['k', 'l'],
344
'o':['m'], 'p':['m', 'l'], 'q':['n', 'o'], 'r':['q'], 's':['r'],
345
't':['s'], 'u':['t'], 'v':['u'], 'w':['v'], 'x':['w'],
346
'y':['j', 'x'], 'z':['x', 'p']}
349
# Shortcut with extra root
350
# We have a long history shortcut, and an extra root, which is why we can't
351
# stop searchers based on seeing NULL_REVISION
363
shortcut_extra_root = {'a': [NULL_REVISION],
368
'f': ['a', 'd', 'g'],
369
'g': [NULL_REVISION],
382
boundary = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e'], 'e': ['f'],
386
# A graph that contains a ghost
397
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
398
'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
400
# A graph that shows we can shortcut finding revnos when reaching them from the
420
with_tail = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'], 'e':['d'],
421
'f':['e'], 'g':['e'], 'h':['f'], 'i':['h']}
424
class InstrumentedParentsProvider(object):
426
def __init__(self, parents_provider):
428
self._real_parents_provider = parents_provider
430
def get_parent_map(self, nodes):
431
self.calls.extend(nodes)
432
return self._real_parents_provider.get_parent_map(nodes)
435
class TestGraphBase(tests.TestCase):
437
def make_graph(self, ancestors):
438
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
440
def make_breaking_graph(self, ancestors, break_on):
441
"""Make a Graph that raises an exception if we hit a node."""
442
g = self.make_graph(ancestors)
443
orig_parent_map = g.get_parent_map
444
def get_parent_map(keys):
445
bad_keys = set(keys).intersection(break_on)
447
self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
448
return orig_parent_map(keys)
449
g.get_parent_map = get_parent_map
453
class TestGraph(TestCaseWithMemoryTransport):
455
def make_graph(self, ancestors):
456
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
458
def prepare_memory_tree(self, location):
459
tree = self.make_branch_and_memory_tree(location)
464
def build_ancestry(self, tree, ancestors):
465
"""Create an ancestry as specified by a graph dict
467
:param tree: A tree to use
468
:param ancestors: a dict of {node: [node_parent, ...]}
470
pending = [NULL_REVISION]
472
for descendant, parents in ancestors.iteritems():
473
for parent in parents:
474
descendants.setdefault(parent, []).append(descendant)
475
while len(pending) > 0:
476
cur_node = pending.pop()
477
for descendant in descendants.get(cur_node, []):
478
if tree.branch.repository.has_revision(descendant):
480
parents = [p for p in ancestors[descendant] if p is not
482
if len([p for p in parents if not
483
tree.branch.repository.has_revision(p)]) > 0:
485
tree.set_parent_ids(parents)
487
left_parent = parents[0]
489
left_parent = NULL_REVISION
490
tree.branch.set_last_revision_info(
491
len(tree.branch._lefthand_history(left_parent)),
493
tree.commit(descendant, rev_id=descendant)
494
pending.append(descendant)
497
"""Test finding least common ancestor.
499
ancestry_1 should always have a single common ancestor
501
graph = self.make_graph(ancestry_1)
502
self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
503
self.assertEqual(set([NULL_REVISION]),
504
graph.find_lca(NULL_REVISION, NULL_REVISION))
505
self.assertEqual(set([NULL_REVISION]),
506
graph.find_lca(NULL_REVISION, 'rev1'))
507
self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
508
self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
510
def test_no_unique_lca(self):
511
"""Test error when one revision is not in the graph"""
512
graph = self.make_graph(ancestry_1)
513
self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
516
def test_lca_criss_cross(self):
517
"""Test least-common-ancestor after a criss-cross merge."""
518
graph = self.make_graph(criss_cross)
519
self.assertEqual(set(['rev2a', 'rev2b']),
520
graph.find_lca('rev3a', 'rev3b'))
521
self.assertEqual(set(['rev2b']),
522
graph.find_lca('rev3a', 'rev3b', 'rev2b'))
524
def test_lca_shortcut(self):
525
"""Test least-common ancestor on this history shortcut"""
526
graph = self.make_graph(history_shortcut)
527
self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
529
def test_recursive_unique_lca(self):
530
"""Test finding a unique least common ancestor.
532
ancestry_1 should always have a single common ancestor
534
graph = self.make_graph(ancestry_1)
535
self.assertEqual(NULL_REVISION,
536
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
537
self.assertEqual(NULL_REVISION,
538
graph.find_unique_lca(NULL_REVISION, 'rev1'))
539
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
540
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
541
self.assertEqual(('rev1', 1,),
542
graph.find_unique_lca('rev2a', 'rev2b',
545
def assertRemoveDescendants(self, expected, graph, revisions):
546
parents = graph.get_parent_map(revisions)
547
self.assertEqual(expected,
548
graph._remove_simple_descendants(revisions, parents))
550
def test__remove_simple_descendants(self):
551
graph = self.make_graph(ancestry_1)
552
self.assertRemoveDescendants(set(['rev1']), graph,
553
set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']))
555
def test__remove_simple_descendants_disjoint(self):
556
graph = self.make_graph(ancestry_1)
557
self.assertRemoveDescendants(set(['rev1', 'rev3']), graph,
558
set(['rev1', 'rev3']))
560
def test__remove_simple_descendants_chain(self):
561
graph = self.make_graph(ancestry_1)
562
self.assertRemoveDescendants(set(['rev1']), graph,
563
set(['rev1', 'rev2a', 'rev3']))
565
def test__remove_simple_descendants_siblings(self):
566
graph = self.make_graph(ancestry_1)
567
self.assertRemoveDescendants(set(['rev2a', 'rev2b']), graph,
568
set(['rev2a', 'rev2b', 'rev3']))
570
def test_unique_lca_criss_cross(self):
571
"""Ensure we don't pick non-unique lcas in a criss-cross"""
572
graph = self.make_graph(criss_cross)
573
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
574
lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
575
self.assertEqual('rev1', lca)
576
self.assertEqual(2, steps)
578
def test_unique_lca_null_revision(self):
579
"""Ensure we pick NULL_REVISION when necessary"""
580
graph = self.make_graph(criss_cross2)
581
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
582
self.assertEqual(NULL_REVISION,
583
graph.find_unique_lca('rev2a', 'rev2b'))
585
def test_unique_lca_null_revision2(self):
586
"""Ensure we pick NULL_REVISION when necessary"""
587
graph = self.make_graph(ancestry_2)
588
self.assertEqual(NULL_REVISION,
589
graph.find_unique_lca('rev4a', 'rev1b'))
591
def test_lca_double_shortcut(self):
592
graph = self.make_graph(double_shortcut)
593
self.assertEqual('c', graph.find_unique_lca('f', 'g'))
595
def test_common_ancestor_two_repos(self):
596
"""Ensure we do unique_lca using data from two repos"""
597
mainline_tree = self.prepare_memory_tree('mainline')
598
self.build_ancestry(mainline_tree, mainline)
599
self.addCleanup(mainline_tree.unlock)
601
# This is cheating, because the revisions in the graph are actually
602
# different revisions, despite having the same revision-id.
603
feature_tree = self.prepare_memory_tree('feature')
604
self.build_ancestry(feature_tree, feature_branch)
605
self.addCleanup(feature_tree.unlock)
607
graph = mainline_tree.branch.repository.get_graph(
608
feature_tree.branch.repository)
609
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
611
def test_graph_difference(self):
612
graph = self.make_graph(ancestry_1)
613
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
614
self.assertEqual((set(), set(['rev1'])),
615
graph.find_difference(NULL_REVISION, 'rev1'))
616
self.assertEqual((set(['rev1']), set()),
617
graph.find_difference('rev1', NULL_REVISION))
618
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
619
graph.find_difference('rev3', 'rev2b'))
620
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
621
graph.find_difference('rev4', 'rev2b'))
623
def test_graph_difference_separate_ancestry(self):
624
graph = self.make_graph(ancestry_2)
625
self.assertEqual((set(['rev1a']), set(['rev1b'])),
626
graph.find_difference('rev1a', 'rev1b'))
627
self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
629
graph.find_difference('rev4a', 'rev1b'))
631
def test_graph_difference_criss_cross(self):
632
graph = self.make_graph(criss_cross)
633
self.assertEqual((set(['rev3a']), set(['rev3b'])),
634
graph.find_difference('rev3a', 'rev3b'))
635
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
636
graph.find_difference('rev2a', 'rev3b'))
638
def test_graph_difference_extended_history(self):
639
graph = self.make_graph(extended_history_shortcut)
640
self.assertEqual((set(['e']), set(['f'])),
641
graph.find_difference('e', 'f'))
642
self.assertEqual((set(['f']), set(['e'])),
643
graph.find_difference('f', 'e'))
645
def test_graph_difference_double_shortcut(self):
646
graph = self.make_graph(double_shortcut)
647
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
648
graph.find_difference('f', 'g'))
650
def test_graph_difference_complex_shortcut(self):
651
graph = self.make_graph(complex_shortcut)
652
self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
653
graph.find_difference('m', 'n'))
655
def test_graph_difference_complex_shortcut2(self):
656
graph = self.make_graph(complex_shortcut2)
657
self.assertEqual((set(['t']), set(['j', 'u'])),
658
graph.find_difference('t', 'u'))
660
def test_graph_difference_shortcut_extra_root(self):
661
graph = self.make_graph(shortcut_extra_root)
662
self.assertEqual((set(['e']), set(['f', 'g'])),
663
graph.find_difference('e', 'f'))
666
def test_stacked_parents_provider(self):
667
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
668
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
669
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
670
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
671
stacked.get_parent_map(['rev1', 'rev2']))
672
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
673
stacked.get_parent_map(['rev2', 'rev1']))
674
self.assertEqual({'rev2':['rev3']},
675
stacked.get_parent_map(['rev2', 'rev2']))
676
self.assertEqual({'rev1':['rev4']},
677
stacked.get_parent_map(['rev1', 'rev1']))
679
def test_stacked_parents_provider_overlapping(self):
680
# rev2 is availible in both providers.
684
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
685
parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
686
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
687
self.assertEqual({'rev2': ['rev1']},
688
stacked.get_parent_map(['rev2']))
690
def test__stacked_parents_provider_deprecated(self):
691
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
692
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
693
stacked = self.applyDeprecated(deprecated_in((1, 16, 0)),
694
_mod_graph._StackedParentsProvider, [parents1, parents2])
695
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
696
stacked.get_parent_map(['rev1', 'rev2']))
697
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
698
stacked.get_parent_map(['rev2', 'rev1']))
699
self.assertEqual({'rev2':['rev3']},
700
stacked.get_parent_map(['rev2', 'rev2']))
701
self.assertEqual({'rev1':['rev4']},
702
stacked.get_parent_map(['rev1', 'rev1']))
704
def test_iter_topo_order(self):
705
graph = self.make_graph(ancestry_1)
706
args = ['rev2a', 'rev3', 'rev1']
707
topo_args = list(graph.iter_topo_order(args))
708
self.assertEqual(set(args), set(topo_args))
709
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
710
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
712
def test_is_ancestor(self):
713
graph = self.make_graph(ancestry_1)
714
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
715
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
716
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
717
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
718
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
719
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
720
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
721
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
722
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
723
instrumented_provider = InstrumentedParentsProvider(graph)
724
instrumented_graph = _mod_graph.Graph(instrumented_provider)
725
instrumented_graph.is_ancestor('rev2a', 'rev2b')
726
self.assertTrue('null:' not in instrumented_provider.calls)
728
def test_is_between(self):
729
graph = self.make_graph(ancestry_1)
730
self.assertEqual(True, graph.is_between('null:', 'null:', 'null:'))
731
self.assertEqual(True, graph.is_between('rev1', 'null:', 'rev1'))
732
self.assertEqual(True, graph.is_between('rev1', 'rev1', 'rev4'))
733
self.assertEqual(True, graph.is_between('rev4', 'rev1', 'rev4'))
734
self.assertEqual(True, graph.is_between('rev3', 'rev1', 'rev4'))
735
self.assertEqual(False, graph.is_between('rev4', 'rev1', 'rev3'))
736
self.assertEqual(False, graph.is_between('rev1', 'rev2a', 'rev4'))
737
self.assertEqual(False, graph.is_between('null:', 'rev1', 'rev4'))
739
def test_is_ancestor_boundary(self):
740
"""Ensure that we avoid searching the whole graph.
742
This requires searching through b as a common ancestor, so we
743
can identify that e is common.
745
graph = self.make_graph(boundary)
746
instrumented_provider = InstrumentedParentsProvider(graph)
747
graph = _mod_graph.Graph(instrumented_provider)
748
self.assertFalse(graph.is_ancestor('a', 'c'))
749
self.assertTrue('null:' not in instrumented_provider.calls)
751
def test_iter_ancestry(self):
752
nodes = boundary.copy()
753
nodes[NULL_REVISION] = ()
754
graph = self.make_graph(nodes)
755
expected = nodes.copy()
756
expected.pop('a') # 'a' is not in the ancestry of 'c', all the
758
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
759
self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
761
def test_iter_ancestry_with_ghost(self):
762
graph = self.make_graph(with_ghost)
763
expected = with_ghost.copy()
764
# 'a' is not in the ancestry of 'c', and 'g' is a ghost
766
self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
768
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
770
def test_filter_candidate_lca(self):
771
"""Test filter_candidate_lca for a corner case
773
This tests the case where we encounter the end of iteration for 'e'
774
in the same pass as we discover that 'd' is an ancestor of 'e', and
775
therefore 'e' can't be an lca.
777
To compensate for different dict orderings on other Python
778
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
780
# This test is sensitive to the iteration order of dicts. It will
781
# pass incorrectly if 'e' and 'a' sort before 'c'
790
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
791
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
792
self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
794
def test_heads_null(self):
795
graph = self.make_graph(ancestry_1)
796
self.assertEqual(set(['null:']), graph.heads(['null:']))
797
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
798
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
799
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
800
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
802
def test_heads_one(self):
803
# A single node will always be a head
804
graph = self.make_graph(ancestry_1)
805
self.assertEqual(set(['null:']), graph.heads(['null:']))
806
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
807
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
808
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
809
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
810
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
812
def test_heads_single(self):
813
graph = self.make_graph(ancestry_1)
814
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
815
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
816
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
817
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
818
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
819
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
820
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
821
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
823
def test_heads_two_heads(self):
824
graph = self.make_graph(ancestry_1)
825
self.assertEqual(set(['rev2a', 'rev2b']),
826
graph.heads(['rev2a', 'rev2b']))
827
self.assertEqual(set(['rev3', 'rev2b']),
828
graph.heads(['rev3', 'rev2b']))
830
def test_heads_criss_cross(self):
831
graph = self.make_graph(criss_cross)
832
self.assertEqual(set(['rev2a']),
833
graph.heads(['rev2a', 'rev1']))
834
self.assertEqual(set(['rev2b']),
835
graph.heads(['rev2b', 'rev1']))
836
self.assertEqual(set(['rev3a']),
837
graph.heads(['rev3a', 'rev1']))
838
self.assertEqual(set(['rev3b']),
839
graph.heads(['rev3b', 'rev1']))
840
self.assertEqual(set(['rev2a', 'rev2b']),
841
graph.heads(['rev2a', 'rev2b']))
842
self.assertEqual(set(['rev3a']),
843
graph.heads(['rev3a', 'rev2a']))
844
self.assertEqual(set(['rev3a']),
845
graph.heads(['rev3a', 'rev2b']))
846
self.assertEqual(set(['rev3a']),
847
graph.heads(['rev3a', 'rev2a', 'rev2b']))
848
self.assertEqual(set(['rev3b']),
849
graph.heads(['rev3b', 'rev2a']))
850
self.assertEqual(set(['rev3b']),
851
graph.heads(['rev3b', 'rev2b']))
852
self.assertEqual(set(['rev3b']),
853
graph.heads(['rev3b', 'rev2a', 'rev2b']))
854
self.assertEqual(set(['rev3a', 'rev3b']),
855
graph.heads(['rev3a', 'rev3b']))
856
self.assertEqual(set(['rev3a', 'rev3b']),
857
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
859
def test_heads_shortcut(self):
860
graph = self.make_graph(history_shortcut)
862
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
863
graph.heads(['rev2a', 'rev2b', 'rev2c']))
864
self.assertEqual(set(['rev3a', 'rev3b']),
865
graph.heads(['rev3a', 'rev3b']))
866
self.assertEqual(set(['rev3a', 'rev3b']),
867
graph.heads(['rev2a', 'rev3a', 'rev3b']))
868
self.assertEqual(set(['rev2a', 'rev3b']),
869
graph.heads(['rev2a', 'rev3b']))
870
self.assertEqual(set(['rev2c', 'rev3a']),
871
graph.heads(['rev2c', 'rev3a']))
873
def _run_heads_break_deeper(self, graph_dict, search):
874
"""Run heads on a graph-as-a-dict.
876
If the search asks for the parents of 'deeper' the test will fail.
880
def get_parent_map(keys):
884
self.fail('key deeper was accessed')
885
result[key] = graph_dict[key]
888
an_obj.get_parent_map = get_parent_map
889
graph = _mod_graph.Graph(an_obj)
890
return graph.heads(search)
892
def test_heads_limits_search(self):
893
# test that a heads query does not search all of history
899
self.assertEqual(set(['left', 'right']),
900
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
902
def test_heads_limits_search_assymetric(self):
903
# test that a heads query does not search all of history
906
'midleft':['common'],
908
'common':['aftercommon'],
909
'aftercommon':['deeper'],
911
self.assertEqual(set(['left', 'right']),
912
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
914
def test_heads_limits_search_common_search_must_continue(self):
915
# test that common nodes are still queried, preventing
916
# all-the-way-to-origin behaviour in the following graph:
918
'h1':['shortcut', 'common1'],
920
'shortcut':['common2'],
921
'common1':['common2'],
922
'common2':['deeper'],
924
self.assertEqual(set(['h1', 'h2']),
925
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
927
def test_breadth_first_search_start_ghosts(self):
928
graph = self.make_graph({})
929
# with_ghosts reports the ghosts
930
search = graph._make_breadth_first_searcher(['a-ghost'])
931
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
932
self.assertRaises(StopIteration, search.next_with_ghosts)
934
search = graph._make_breadth_first_searcher(['a-ghost'])
935
self.assertEqual(set(['a-ghost']), search.next())
936
self.assertRaises(StopIteration, search.next)
938
def test_breadth_first_search_deep_ghosts(self):
939
graph = self.make_graph({
941
'present':['child', 'ghost'],
944
# with_ghosts reports the ghosts
945
search = graph._make_breadth_first_searcher(['head'])
946
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
947
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
948
self.assertEqual((set(['child']), set(['ghost'])),
949
search.next_with_ghosts())
950
self.assertRaises(StopIteration, search.next_with_ghosts)
952
search = graph._make_breadth_first_searcher(['head'])
953
self.assertEqual(set(['head']), search.next())
954
self.assertEqual(set(['present']), search.next())
955
self.assertEqual(set(['child', 'ghost']),
957
self.assertRaises(StopIteration, search.next)
959
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
960
# To make the API robust, we allow calling both next() and
961
# next_with_ghosts() on the same searcher.
962
graph = self.make_graph({
964
'present':['child', 'ghost'],
967
# start with next_with_ghosts
968
search = graph._make_breadth_first_searcher(['head'])
969
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
970
self.assertEqual(set(['present']), search.next())
971
self.assertEqual((set(['child']), set(['ghost'])),
972
search.next_with_ghosts())
973
self.assertRaises(StopIteration, search.next)
975
search = graph._make_breadth_first_searcher(['head'])
976
self.assertEqual(set(['head']), search.next())
977
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
978
self.assertEqual(set(['child', 'ghost']),
980
self.assertRaises(StopIteration, search.next_with_ghosts)
982
def test_breadth_first_change_search(self):
983
# Changing the search should work with both next and next_with_ghosts.
984
graph = self.make_graph({
986
'present':['stopped'],
990
search = graph._make_breadth_first_searcher(['head'])
991
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
992
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
993
self.assertEqual(set(['present']),
994
search.stop_searching_any(['present']))
995
self.assertEqual((set(['other']), set(['other_ghost'])),
996
search.start_searching(['other', 'other_ghost']))
997
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
998
self.assertRaises(StopIteration, search.next_with_ghosts)
1000
search = graph._make_breadth_first_searcher(['head'])
1001
self.assertEqual(set(['head']), search.next())
1002
self.assertEqual(set(['present']), search.next())
1003
self.assertEqual(set(['present']),
1004
search.stop_searching_any(['present']))
1005
search.start_searching(['other', 'other_ghost'])
1006
self.assertEqual(set(['other_2']), search.next())
1007
self.assertRaises(StopIteration, search.next)
1009
def assertSeenAndResult(self, instructions, search, next):
1010
"""Check the results of .seen and get_result() for a seach.
1012
:param instructions: A list of tuples:
1013
(seen, recipe, included_keys, starts, stops).
1014
seen, recipe and included_keys are results to check on the search
1015
and the searches get_result(). starts and stops are parameters to
1016
pass to start_searching and stop_searching_any during each
1017
iteration, if they are not None.
1018
:param search: The search to use.
1019
:param next: A callable to advance the search.
1021
for seen, recipe, included_keys, starts, stops in instructions:
1022
# Adjust for recipe contract changes that don't vary for all the
1024
recipe = ('search',) + recipe
1026
if starts is not None:
1027
search.start_searching(starts)
1028
if stops is not None:
1029
search.stop_searching_any(stops)
1030
result = search.get_result()
1031
self.assertEqual(recipe, result.get_recipe())
1032
self.assertEqual(set(included_keys), result.get_keys())
1033
self.assertEqual(seen, search.seen)
1035
def test_breadth_first_get_result_excludes_current_pending(self):
1036
graph = self.make_graph({
1038
'child':[NULL_REVISION],
1041
search = graph._make_breadth_first_searcher(['head'])
1042
# At the start, nothing has been seen, to its all excluded:
1043
result = search.get_result()
1044
self.assertEqual(('search', set(['head']), set(['head']), 0),
1045
result.get_recipe())
1046
self.assertEqual(set(), result.get_keys())
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
result = search.get_result()
1076
self.assertEqual(('search', set(['head']), set(['child']), 1),
1077
result.get_recipe())
1078
self.assertEqual(set(['head']), result.get_keys())
1079
self.assertEqual(set(['head']), search.seen)
1082
# stop at child, and start a new search at otherhead:
1083
# - otherhead counts as seen immediately when start_searching is
1085
(set(['head', 'child', 'otherhead']),
1086
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1087
['head', 'otherhead'], ['otherhead'], ['child']),
1088
(set(['head', 'child', 'otherhead', 'otherchild']),
1089
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1090
['head', 'otherhead', 'otherchild'], None, None),
1091
# stop searching excluded now
1092
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1093
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1094
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1096
self.assertSeenAndResult(expected, search, search.next)
1097
# using next_with_ghosts:
1098
search = graph._make_breadth_first_searcher([])
1099
search.start_searching(['head'])
1100
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1102
def test_breadth_first_stop_searching_not_queried(self):
1103
# A client should be able to say 'stop node X' even if X has not been
1104
# returned to the client.
1105
graph = self.make_graph({
1106
'head':['child', 'ghost1'],
1107
'child':[NULL_REVISION],
1110
search = graph._make_breadth_first_searcher(['head'])
1112
# NULL_REVISION and ghost1 have not been returned
1114
(set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1115
['head'], None, [NULL_REVISION, 'ghost1']),
1116
# ghost1 has been returned, NULL_REVISION is to be returned in the
1118
(set(['head', 'child', 'ghost1']),
1119
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1120
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1122
self.assertSeenAndResult(expected, search, search.next)
1123
# using next_with_ghosts:
1124
search = graph._make_breadth_first_searcher(['head'])
1125
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1127
def test_breadth_first_stop_searching_late(self):
1128
# A client should be able to say 'stop node X' and have it excluded
1129
# from the result even if X was seen in an older iteration of the
1131
graph = self.make_graph({
1134
'child':[NULL_REVISION],
1137
search = graph._make_breadth_first_searcher(['head'])
1139
(set(['head']), (set(['head']), set(['middle']), 1),
1140
['head'], None, None),
1141
(set(['head', 'middle']), (set(['head']), set(['child']), 2),
1142
['head', 'middle'], None, None),
1143
# 'middle' came from the previous iteration, but we don't stop
1144
# searching it until *after* advancing the searcher.
1145
(set(['head', 'middle', 'child']),
1146
(set(['head']), set(['middle', 'child']), 1),
1147
['head'], None, ['middle', 'child']),
1149
self.assertSeenAndResult(expected, search, search.next)
1150
# using next_with_ghosts:
1151
search = graph._make_breadth_first_searcher(['head'])
1152
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1154
def test_breadth_first_get_result_ghosts_are_excluded(self):
1155
graph = self.make_graph({
1156
'head':['child', 'ghost'],
1157
'child':[NULL_REVISION],
1160
search = graph._make_breadth_first_searcher(['head'])
1164
(set(['head']), set(['ghost', 'child']), 1),
1165
['head'], None, None),
1166
(set(['head', 'child', 'ghost']),
1167
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1168
['head', 'child'], None, None),
1170
self.assertSeenAndResult(expected, search, search.next)
1171
# using next_with_ghosts:
1172
search = graph._make_breadth_first_searcher(['head'])
1173
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1175
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1176
graph = self.make_graph({
1178
'child':[NULL_REVISION],
1181
search = graph._make_breadth_first_searcher(['head'])
1184
(set(['head', 'ghost']),
1185
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1186
['head'], ['ghost'], None),
1187
(set(['head', 'child', 'ghost']),
1188
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1189
['head', 'child'], None, None),
1191
self.assertSeenAndResult(expected, search, search.next)
1192
# using next_with_ghosts:
1193
search = graph._make_breadth_first_searcher(['head'])
1194
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1196
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1197
graph = self.make_graph({
1198
'head':[NULL_REVISION],
1201
search = graph._make_breadth_first_searcher(['head'])
1205
(set(['head']), set([NULL_REVISION]), 1),
1206
['head'], None, None),
1207
(set(['head', NULL_REVISION]),
1208
(set(['head']), set([]), 2),
1209
['head', NULL_REVISION], None, None),
1211
self.assertSeenAndResult(expected, search, search.next)
1212
# using next_with_ghosts:
1213
search = graph._make_breadth_first_searcher(['head'])
1214
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1216
def test_breadth_first_search_get_result_after_StopIteration(self):
1217
# StopIteration should not invalid anything..
1218
graph = self.make_graph({
1219
'head':[NULL_REVISION],
1222
search = graph._make_breadth_first_searcher(['head'])
1226
(set(['head']), set([NULL_REVISION]), 1),
1227
['head'], None, None),
1228
(set(['head', 'ghost', NULL_REVISION]),
1229
(set(['head', 'ghost']), set(['ghost']), 2),
1230
['head', NULL_REVISION], ['ghost'], None),
1232
self.assertSeenAndResult(expected, search, search.next)
1233
self.assertRaises(StopIteration, search.next)
1234
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1235
result = search.get_result()
1236
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1237
result.get_recipe())
1238
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
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
result = search.get_result()
1245
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1246
result.get_recipe())
1247
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1250
class TestFindUniqueAncestors(TestGraphBase):
1252
def assertFindUniqueAncestors(self, graph, expected, node, common):
1253
actual = graph.find_unique_ancestors(node, common)
1254
self.assertEqual(expected, sorted(actual))
1256
def test_empty_set(self):
1257
graph = self.make_graph(ancestry_1)
1258
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1259
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1260
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1262
def test_single_node(self):
1263
graph = self.make_graph(ancestry_1)
1264
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1265
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1266
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1268
def test_minimal_ancestry(self):
1269
graph = self.make_breaking_graph(extended_history_shortcut,
1270
[NULL_REVISION, 'a', 'b'])
1271
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1273
graph = self.make_breaking_graph(extended_history_shortcut,
1275
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1277
graph = self.make_breaking_graph(complex_shortcut,
1279
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1280
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1281
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1282
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1284
def test_in_ancestry(self):
1285
graph = self.make_graph(ancestry_1)
1286
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1287
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1289
def test_multiple_revisions(self):
1290
graph = self.make_graph(ancestry_1)
1291
self.assertFindUniqueAncestors(graph,
1292
['rev4'], 'rev4', ['rev3', 'rev2b'])
1293
self.assertFindUniqueAncestors(graph,
1294
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1296
def test_complex_shortcut(self):
1297
graph = self.make_graph(complex_shortcut)
1298
self.assertFindUniqueAncestors(graph,
1299
['h', 'n'], 'n', ['m'])
1300
self.assertFindUniqueAncestors(graph,
1301
['e', 'i', 'm'], 'm', ['n'])
1303
def test_complex_shortcut2(self):
1304
graph = self.make_graph(complex_shortcut2)
1305
self.assertFindUniqueAncestors(graph,
1306
['j', 'u'], 'u', ['t'])
1307
self.assertFindUniqueAncestors(graph,
1310
def test_multiple_interesting_unique(self):
1311
graph = self.make_graph(multiple_interesting_unique)
1312
self.assertFindUniqueAncestors(graph,
1313
['j', 'y'], 'y', ['z'])
1314
self.assertFindUniqueAncestors(graph,
1315
['p', 'z'], 'z', ['y'])
1317
def test_racing_shortcuts(self):
1318
graph = self.make_graph(racing_shortcuts)
1319
self.assertFindUniqueAncestors(graph,
1320
['p', 'q', 'z'], 'z', ['y'])
1321
self.assertFindUniqueAncestors(graph,
1322
['h', 'i', 'j', 'y'], 'j', ['z'])
1325
class TestGraphFindDistanceToNull(TestGraphBase):
1326
"""Test an api that should be able to compute a revno"""
1328
def assertFindDistance(self, revno, graph, target_id, known_ids):
1329
"""Assert the output of Graph.find_distance_to_null()"""
1330
actual = graph.find_distance_to_null(target_id, known_ids)
1331
self.assertEqual(revno, actual)
1333
def test_nothing_known(self):
1334
graph = self.make_graph(ancestry_1)
1335
self.assertFindDistance(0, graph, NULL_REVISION, [])
1336
self.assertFindDistance(1, graph, 'rev1', [])
1337
self.assertFindDistance(2, graph, 'rev2a', [])
1338
self.assertFindDistance(2, graph, 'rev2b', [])
1339
self.assertFindDistance(3, graph, 'rev3', [])
1340
self.assertFindDistance(4, graph, 'rev4', [])
1342
def test_rev_is_ghost(self):
1343
graph = self.make_graph(ancestry_1)
1344
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1345
graph.find_distance_to_null, 'rev_missing', [])
1346
self.assertEqual('rev_missing', e.revision_id)
1347
self.assertEqual('rev_missing', e.ghost_revision_id)
1349
def test_ancestor_is_ghost(self):
1350
graph = self.make_graph({'rev':['parent']})
1351
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1352
graph.find_distance_to_null, 'rev', [])
1353
self.assertEqual('rev', e.revision_id)
1354
self.assertEqual('parent', e.ghost_revision_id)
1356
def test_known_in_ancestry(self):
1357
graph = self.make_graph(ancestry_1)
1358
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1359
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1361
def test_known_in_ancestry_limits(self):
1362
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1363
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1365
def test_target_is_ancestor(self):
1366
graph = self.make_graph(ancestry_1)
1367
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1369
def test_target_is_ancestor_limits(self):
1370
"""We shouldn't search all history if we run into ourselves"""
1371
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1372
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1374
def test_target_parallel_to_known_limits(self):
1375
# Even though the known revision isn't part of the other ancestry, they
1376
# eventually converge
1377
graph = self.make_breaking_graph(with_tail, ['a'])
1378
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1379
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1380
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1381
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1384
class TestFindMergeOrder(TestGraphBase):
1386
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1387
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1389
def test_parents(self):
1390
graph = self.make_graph(ancestry_1)
1391
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1393
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1396
def test_ancestors(self):
1397
graph = self.make_graph(ancestry_1)
1398
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1400
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1403
def test_shortcut_one_ancestor(self):
1404
# When we have enough info, we can stop searching
1405
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1406
# Single ancestors shortcut right away
1407
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1409
def test_shortcut_after_one_ancestor(self):
1410
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1411
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1414
class TestCachingParentsProvider(tests.TestCase):
1415
"""These tests run with:
1417
self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1419
self.caching_pp, a CachingParentsProvider layered on inst_pp.
1423
super(TestCachingParentsProvider, self).setUp()
1424
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1425
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1426
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1428
def test_get_parent_map(self):
1429
"""Requesting the same revision should be returned from cache"""
1430
self.assertEqual({}, self.caching_pp._cache)
1431
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1432
self.assertEqual(['a'], self.inst_pp.calls)
1433
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1434
# No new call, as it should have been returned from the cache
1435
self.assertEqual(['a'], self.inst_pp.calls)
1436
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1438
def test_get_parent_map_not_present(self):
1439
"""The cache should also track when a revision doesn't exist"""
1440
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1441
self.assertEqual(['b'], self.inst_pp.calls)
1442
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1444
self.assertEqual(['b'], self.inst_pp.calls)
1446
def test_get_parent_map_mixed(self):
1447
"""Anything that can be returned from cache, should be"""
1448
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1449
self.assertEqual(['b'], self.inst_pp.calls)
1450
self.assertEqual({'a':('b',)},
1451
self.caching_pp.get_parent_map(['a', 'b']))
1452
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1454
def test_get_parent_map_repeated(self):
1455
"""Asking for the same parent 2x will only forward 1 request."""
1456
self.assertEqual({'a':('b',)},
1457
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1458
# Use sorted because we don't care about the order, just that each is
1459
# only present 1 time.
1460
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1462
def test_note_missing_key(self):
1463
"""After noting that a key is missing it is cached."""
1464
self.caching_pp.note_missing_key('b')
1465
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1466
self.assertEqual([], self.inst_pp.calls)
1467
self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1470
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1471
"""Test the behaviour when parents are provided that were not requested."""
1474
super(TestCachingParentsProviderExtras, self).setUp()
1475
class ExtraParentsProvider(object):
1477
def get_parent_map(self, keys):
1478
return {'rev1': [], 'rev2': ['rev1',]}
1480
self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1481
self.caching_pp = _mod_graph.CachingParentsProvider(
1482
get_parent_map=self.inst_pp.get_parent_map)
1484
def test_uncached(self):
1485
self.caching_pp.disable_cache()
1486
self.assertEqual({'rev1': []},
1487
self.caching_pp.get_parent_map(['rev1']))
1488
self.assertEqual(['rev1'], self.inst_pp.calls)
1489
self.assertIs(None, self.caching_pp._cache)
1491
def test_cache_initially_empty(self):
1492
self.assertEqual({}, self.caching_pp._cache)
1494
def test_cached(self):
1495
self.assertEqual({'rev1': []},
1496
self.caching_pp.get_parent_map(['rev1']))
1497
self.assertEqual(['rev1'], self.inst_pp.calls)
1498
self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1499
self.caching_pp._cache)
1500
self.assertEqual({'rev1': []},
1501
self.caching_pp.get_parent_map(['rev1']))
1502
self.assertEqual(['rev1'], self.inst_pp.calls)
1504
def test_disable_cache_clears_cache(self):
1505
# Put something in the cache
1506
self.caching_pp.get_parent_map(['rev1'])
1507
self.assertEqual(2, len(self.caching_pp._cache))
1508
self.caching_pp.disable_cache()
1509
self.assertIs(None, self.caching_pp._cache)
1511
def test_enable_cache_raises(self):
1512
e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1513
self.assertEqual('Cache enabled when already enabled.', str(e))
1515
def test_cache_misses(self):
1516
self.caching_pp.get_parent_map(['rev3'])
1517
self.caching_pp.get_parent_map(['rev3'])
1518
self.assertEqual(['rev3'], self.inst_pp.calls)
1520
def test_no_cache_misses(self):
1521
self.caching_pp.disable_cache()
1522
self.caching_pp.enable_cache(cache_misses=False)
1523
self.caching_pp.get_parent_map(['rev3'])
1524
self.caching_pp.get_parent_map(['rev3'])
1525
self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1527
def test_cache_extras(self):
1528
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1529
self.assertEqual({'rev2': ['rev1']},
1530
self.caching_pp.get_parent_map(['rev2']))
1531
self.assertEqual(['rev3'], self.inst_pp.calls)
1534
class TestCollapseLinearRegions(tests.TestCase):
1536
def assertCollapsed(self, collapsed, original):
1537
self.assertEqual(collapsed,
1538
_mod_graph.collapse_linear_regions(original))
1540
def test_collapse_nothing(self):
1541
d = {1:[2, 3], 2:[], 3:[]}
1542
self.assertCollapsed(d, d)
1543
d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1544
self.assertCollapsed(d, d)
1546
def test_collapse_chain(self):
1547
# Any time we have a linear chain, we should be able to collapse
1548
d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1549
self.assertCollapsed({1:[5], 5:[]}, d)
1550
d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1551
self.assertCollapsed({5:[1], 1:[]}, d)
1552
d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1553
self.assertCollapsed({5:[2], 2:[]}, d)
1555
def test_collapse_with_multiple_children(self):
1566
# 4 and 5 cannot be removed because 6 has 2 children
1567
# 2 and 3 cannot be removed because 1 has 2 parents
1568
d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1569
self.assertCollapsed(d, d)
1572
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1573
"""Tests for bzrlib.graph.PendingAncestryResult."""
1575
def test_get_keys(self):
1576
builder = self.make_branch_builder('b')
1577
builder.start_series()
1578
builder.build_snapshot('rev-1', None, [
1579
('add', ('', 'root-id', 'directory', ''))])
1580
builder.build_snapshot('rev-2', ['rev-1'], [])
1581
builder.finish_series()
1582
repo = builder.get_branch().repository
1584
self.addCleanup(repo.unlock)
1585
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1586
self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1588
def test_get_keys_excludes_ghosts(self):
1589
builder = self.make_branch_builder('b')
1590
builder.start_series()
1591
builder.build_snapshot('rev-1', None, [
1592
('add', ('', 'root-id', 'directory', ''))])
1593
builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
1594
builder.finish_series()
1595
repo = builder.get_branch().repository
1597
self.addCleanup(repo.unlock)
1598
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1599
self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
1601
def test_get_keys_excludes_null(self):
1602
# Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1603
# somewhere other than the last element, which can happen in real
1605
class StubGraph(object):
1606
def iter_ancestry(self, keys):
1607
return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1608
result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1609
result_keys = result._get_keys(StubGraph())
1610
# Only the non-null keys from the ancestry appear.
1611
self.assertEqual(set(['foo']), set(result_keys))
1614
class TestPendingAncestryResultRefine(TestGraphBase):
1616
def test_refine(self):
1617
# Used when pulling from a stacked repository, so test some revisions
1618
# being satisfied from the stacking branch.
1619
g = self.make_graph(
1620
{"tip":["mid"], "mid":["base"], "tag":["base"],
1621
"base":[NULL_REVISION], NULL_REVISION:[]})
1622
result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1623
result = result.refine(set(['tip']), set(['mid']))
1624
self.assertEqual(set(['mid', 'tag']), result.heads)
1625
result = result.refine(set(['mid', 'tag', 'base']),
1626
set([NULL_REVISION]))
1627
self.assertEqual(set([NULL_REVISION]), result.heads)
1628
self.assertTrue(result.is_empty())
1631
class TestSearchResultRefine(TestGraphBase):
1633
def test_refine(self):
1634
# Used when pulling from a stacked repository, so test some revisions
1635
# being satisfied from the stacking branch.
1636
g = self.make_graph(
1637
{"tip":["mid"], "mid":["base"], "tag":["base"],
1638
"base":[NULL_REVISION], NULL_REVISION:[]})
1639
result = _mod_graph.SearchResult(set(['tip', 'tag']),
1640
set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1641
result = result.refine(set(['tip']), set(['mid']))
1642
recipe = result.get_recipe()
1643
# We should be starting from tag (original head) and mid (seen ref)
1644
self.assertEqual(set(['mid', 'tag']), recipe[1])
1645
# We should be stopping at NULL (original stop) and tip (seen head)
1646
self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1647
self.assertEqual(3, recipe[3])
1648
result = result.refine(set(['mid', 'tag', 'base']),
1649
set([NULL_REVISION]))
1650
recipe = result.get_recipe()
1651
# We should be starting from nothing (NULL was known as a cut point)
1652
self.assertEqual(set([]), recipe[1])
1653
# We should be stopping at NULL (original stop) and tip (seen head) and
1654
# tag (seen head) and mid(seen mid-point head). We could come back and
1655
# define this as not including mid, for minimal results, but it is
1656
# still 'correct' to include mid, and simpler/easier.
1657
self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1658
self.assertEqual(0, recipe[3])
1659
self.assertTrue(result.is_empty())
added
removed
bzrlib/tests/test_graph.py
