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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 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 beginning 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.
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']}
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'],
243
# Graph where different walkers will race to find the common and uncommon
286
# x is found to be common right away, but is the start of a long series of
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.
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']}
301
# A graph with multiple nodes unique to one side.
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']}
348
# Shortcut with extra root
349
# We have a long history shortcut, and an extra root, which is why we can't
350
# stop searchers based on seeing NULL_REVISION
362
shortcut_extra_root = {'a': [NULL_REVISION],
367
'f': ['a', 'd', 'g'],
368
'g': [NULL_REVISION],
381
boundary = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e'], 'e': ['f'],
385
# A graph that contains a ghost
396
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
397
'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
399
# A graph that shows we can shortcut finding revnos when reaching them from the
419
with_tail = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'], 'e':['d'],
420
'f':['e'], 'g':['e'], 'h':['f'], 'i':['h']}
423
class InstrumentedParentsProvider(object):
425
def __init__(self, parents_provider):
427
self._real_parents_provider = parents_provider
429
def get_parent_map(self, nodes):
430
self.calls.extend(nodes)
431
return self._real_parents_provider.get_parent_map(nodes)
434
class TestGraphBase(tests.TestCase):
436
def make_graph(self, ancestors):
437
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
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)
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
452
class TestGraph(TestCaseWithMemoryTransport):
454
def make_graph(self, ancestors):
455
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
457
def prepare_memory_tree(self, location):
458
tree = self.make_branch_and_memory_tree(location)
463
def build_ancestry(self, tree, ancestors):
464
"""Create an ancestry as specified by a graph dict
466
:param tree: A tree to use
467
:param ancestors: a dict of {node: [node_parent, ...]}
469
pending = [NULL_REVISION]
471
for descendant, parents in ancestors.iteritems():
472
for parent in parents:
473
descendants.setdefault(parent, []).append(descendant)
474
while len(pending) > 0:
475
cur_node = pending.pop()
476
for descendant in descendants.get(cur_node, []):
477
if tree.branch.repository.has_revision(descendant):
479
parents = [p for p in ancestors[descendant] if p is not
481
if len([p for p in parents if not
482
tree.branch.repository.has_revision(p)]) > 0:
484
tree.set_parent_ids(parents)
486
left_parent = parents[0]
488
left_parent = NULL_REVISION
489
tree.branch.set_last_revision_info(
490
len(tree.branch._lefthand_history(left_parent)),
492
tree.commit(descendant, rev_id=descendant)
493
pending.append(descendant)
496
"""Test finding least common ancestor.
498
ancestry_1 should always have a single common ancestor
500
graph = self.make_graph(ancestry_1)
501
self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
502
self.assertEqual(set([NULL_REVISION]),
503
graph.find_lca(NULL_REVISION, NULL_REVISION))
504
self.assertEqual(set([NULL_REVISION]),
505
graph.find_lca(NULL_REVISION, 'rev1'))
506
self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
507
self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
509
def test_no_unique_lca(self):
510
"""Test error when one revision is not in the graph"""
511
graph = self.make_graph(ancestry_1)
512
self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
515
def test_lca_criss_cross(self):
516
"""Test least-common-ancestor after a criss-cross merge."""
517
graph = self.make_graph(criss_cross)
518
self.assertEqual(set(['rev2a', 'rev2b']),
519
graph.find_lca('rev3a', 'rev3b'))
520
self.assertEqual(set(['rev2b']),
521
graph.find_lca('rev3a', 'rev3b', 'rev2b'))
523
def test_lca_shortcut(self):
524
"""Test least-common ancestor on this history shortcut"""
525
graph = self.make_graph(history_shortcut)
526
self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
528
def test_recursive_unique_lca(self):
529
"""Test finding a unique least common ancestor.
531
ancestry_1 should always have a single common ancestor
533
graph = self.make_graph(ancestry_1)
534
self.assertEqual(NULL_REVISION,
535
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
536
self.assertEqual(NULL_REVISION,
537
graph.find_unique_lca(NULL_REVISION, 'rev1'))
538
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
539
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
540
self.assertEqual(('rev1', 1,),
541
graph.find_unique_lca('rev2a', 'rev2b',
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))
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']))
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']))
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']))
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']))
569
def test_unique_lca_criss_cross(self):
570
"""Ensure we don't pick non-unique lcas in a criss-cross"""
571
graph = self.make_graph(criss_cross)
572
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
573
lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
574
self.assertEqual('rev1', lca)
575
self.assertEqual(2, steps)
577
def test_unique_lca_null_revision(self):
578
"""Ensure we pick NULL_REVISION when necessary"""
579
graph = self.make_graph(criss_cross2)
580
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
581
self.assertEqual(NULL_REVISION,
582
graph.find_unique_lca('rev2a', 'rev2b'))
584
def test_unique_lca_null_revision2(self):
585
"""Ensure we pick NULL_REVISION when necessary"""
586
graph = self.make_graph(ancestry_2)
587
self.assertEqual(NULL_REVISION,
588
graph.find_unique_lca('rev4a', 'rev1b'))
590
def test_lca_double_shortcut(self):
591
graph = self.make_graph(double_shortcut)
592
self.assertEqual('c', graph.find_unique_lca('f', 'g'))
594
def test_common_ancestor_two_repos(self):
595
"""Ensure we do unique_lca using data from two repos"""
596
mainline_tree = self.prepare_memory_tree('mainline')
597
self.build_ancestry(mainline_tree, mainline)
598
self.addCleanup(mainline_tree.unlock)
600
# This is cheating, because the revisions in the graph are actually
601
# different revisions, despite having the same revision-id.
602
feature_tree = self.prepare_memory_tree('feature')
603
self.build_ancestry(feature_tree, feature_branch)
604
self.addCleanup(feature_tree.unlock)
606
graph = mainline_tree.branch.repository.get_graph(
607
feature_tree.branch.repository)
608
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
610
def test_graph_difference(self):
611
graph = self.make_graph(ancestry_1)
612
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
613
self.assertEqual((set(), set(['rev1'])),
614
graph.find_difference(NULL_REVISION, 'rev1'))
615
self.assertEqual((set(['rev1']), set()),
616
graph.find_difference('rev1', NULL_REVISION))
617
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
618
graph.find_difference('rev3', 'rev2b'))
619
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
620
graph.find_difference('rev4', 'rev2b'))
622
def test_graph_difference_separate_ancestry(self):
623
graph = self.make_graph(ancestry_2)
624
self.assertEqual((set(['rev1a']), set(['rev1b'])),
625
graph.find_difference('rev1a', 'rev1b'))
626
self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
628
graph.find_difference('rev4a', 'rev1b'))
630
def test_graph_difference_criss_cross(self):
631
graph = self.make_graph(criss_cross)
632
self.assertEqual((set(['rev3a']), set(['rev3b'])),
633
graph.find_difference('rev3a', 'rev3b'))
634
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
635
graph.find_difference('rev2a', 'rev3b'))
637
def test_graph_difference_extended_history(self):
638
graph = self.make_graph(extended_history_shortcut)
639
self.assertEqual((set(['e']), set(['f'])),
640
graph.find_difference('e', 'f'))
641
self.assertEqual((set(['f']), set(['e'])),
642
graph.find_difference('f', 'e'))
644
def test_graph_difference_double_shortcut(self):
645
graph = self.make_graph(double_shortcut)
646
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
647
graph.find_difference('f', 'g'))
649
def test_graph_difference_complex_shortcut(self):
650
graph = self.make_graph(complex_shortcut)
651
self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
652
graph.find_difference('m', 'n'))
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'))
659
def test_graph_difference_shortcut_extra_root(self):
660
graph = self.make_graph(shortcut_extra_root)
661
self.assertEqual((set(['e']), set(['f', 'g'])),
662
graph.find_difference('e', 'f'))
664
def test_stacked_parents_provider(self):
665
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
666
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
667
stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
668
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
669
stacked.get_parent_map(['rev1', 'rev2']))
670
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
671
stacked.get_parent_map(['rev2', 'rev1']))
672
self.assertEqual({'rev2':['rev3']},
673
stacked.get_parent_map(['rev2', 'rev2']))
674
self.assertEqual({'rev1':['rev4']},
675
stacked.get_parent_map(['rev1', 'rev1']))
677
def test_iter_topo_order(self):
678
graph = self.make_graph(ancestry_1)
679
args = ['rev2a', 'rev3', 'rev1']
680
topo_args = list(graph.iter_topo_order(args))
681
self.assertEqual(set(args), set(topo_args))
682
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
683
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
685
def test_is_ancestor(self):
686
graph = self.make_graph(ancestry_1)
687
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
688
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
689
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
690
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
691
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
692
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
693
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
694
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
695
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
696
instrumented_provider = InstrumentedParentsProvider(graph)
697
instrumented_graph = _mod_graph.Graph(instrumented_provider)
698
instrumented_graph.is_ancestor('rev2a', 'rev2b')
699
self.assertTrue('null:' not in instrumented_provider.calls)
701
def test_is_between(self):
702
graph = self.make_graph(ancestry_1)
703
self.assertEqual(True, graph.is_between('null:', 'null:', 'null:'))
704
self.assertEqual(True, graph.is_between('rev1', 'null:', 'rev1'))
705
self.assertEqual(True, graph.is_between('rev1', 'rev1', 'rev4'))
706
self.assertEqual(True, graph.is_between('rev4', 'rev1', 'rev4'))
707
self.assertEqual(True, graph.is_between('rev3', 'rev1', 'rev4'))
708
self.assertEqual(False, graph.is_between('rev4', 'rev1', 'rev3'))
709
self.assertEqual(False, graph.is_between('rev1', 'rev2a', 'rev4'))
710
self.assertEqual(False, graph.is_between('null:', 'rev1', 'rev4'))
712
def test_is_ancestor_boundary(self):
713
"""Ensure that we avoid searching the whole graph.
715
This requires searching through b as a common ancestor, so we
716
can identify that e is common.
718
graph = self.make_graph(boundary)
719
instrumented_provider = InstrumentedParentsProvider(graph)
720
graph = _mod_graph.Graph(instrumented_provider)
721
self.assertFalse(graph.is_ancestor('a', 'c'))
722
self.assertTrue('null:' not in instrumented_provider.calls)
724
def test_iter_ancestry(self):
725
nodes = boundary.copy()
726
nodes[NULL_REVISION] = ()
727
graph = self.make_graph(nodes)
728
expected = nodes.copy()
729
expected.pop('a') # 'a' is not in the ancestry of 'c', all the
731
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
732
self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
734
def test_iter_ancestry_with_ghost(self):
735
graph = self.make_graph(with_ghost)
736
expected = with_ghost.copy()
737
# 'a' is not in the ancestry of 'c', and 'g' is a ghost
739
self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
741
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
743
def test_filter_candidate_lca(self):
744
"""Test filter_candidate_lca for a corner case
746
This tests the case where we encounter the end of iteration for 'e'
747
in the same pass as we discover that 'd' is an ancestor of 'e', and
748
therefore 'e' can't be an lca.
750
To compensate for different dict orderings on other Python
751
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
753
# This test is sensitive to the iteration order of dicts. It will
754
# pass incorrectly if 'e' and 'a' sort before 'c'
763
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
764
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
765
self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
767
def test_heads_null(self):
768
graph = self.make_graph(ancestry_1)
769
self.assertEqual(set(['null:']), graph.heads(['null:']))
770
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
771
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
772
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
773
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
775
def test_heads_one(self):
776
# A single node will always be a head
777
graph = self.make_graph(ancestry_1)
778
self.assertEqual(set(['null:']), graph.heads(['null:']))
779
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
780
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
781
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
782
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
783
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
785
def test_heads_single(self):
786
graph = self.make_graph(ancestry_1)
787
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
788
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
789
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
790
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
791
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
792
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
793
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
794
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
796
def test_heads_two_heads(self):
797
graph = self.make_graph(ancestry_1)
798
self.assertEqual(set(['rev2a', 'rev2b']),
799
graph.heads(['rev2a', 'rev2b']))
800
self.assertEqual(set(['rev3', 'rev2b']),
801
graph.heads(['rev3', 'rev2b']))
803
def test_heads_criss_cross(self):
804
graph = self.make_graph(criss_cross)
805
self.assertEqual(set(['rev2a']),
806
graph.heads(['rev2a', 'rev1']))
807
self.assertEqual(set(['rev2b']),
808
graph.heads(['rev2b', 'rev1']))
809
self.assertEqual(set(['rev3a']),
810
graph.heads(['rev3a', 'rev1']))
811
self.assertEqual(set(['rev3b']),
812
graph.heads(['rev3b', 'rev1']))
813
self.assertEqual(set(['rev2a', 'rev2b']),
814
graph.heads(['rev2a', 'rev2b']))
815
self.assertEqual(set(['rev3a']),
816
graph.heads(['rev3a', 'rev2a']))
817
self.assertEqual(set(['rev3a']),
818
graph.heads(['rev3a', 'rev2b']))
819
self.assertEqual(set(['rev3a']),
820
graph.heads(['rev3a', 'rev2a', 'rev2b']))
821
self.assertEqual(set(['rev3b']),
822
graph.heads(['rev3b', 'rev2a']))
823
self.assertEqual(set(['rev3b']),
824
graph.heads(['rev3b', 'rev2b']))
825
self.assertEqual(set(['rev3b']),
826
graph.heads(['rev3b', 'rev2a', 'rev2b']))
827
self.assertEqual(set(['rev3a', 'rev3b']),
828
graph.heads(['rev3a', 'rev3b']))
829
self.assertEqual(set(['rev3a', 'rev3b']),
830
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
832
def test_heads_shortcut(self):
833
graph = self.make_graph(history_shortcut)
835
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
836
graph.heads(['rev2a', 'rev2b', 'rev2c']))
837
self.assertEqual(set(['rev3a', 'rev3b']),
838
graph.heads(['rev3a', 'rev3b']))
839
self.assertEqual(set(['rev3a', 'rev3b']),
840
graph.heads(['rev2a', 'rev3a', 'rev3b']))
841
self.assertEqual(set(['rev2a', 'rev3b']),
842
graph.heads(['rev2a', 'rev3b']))
843
self.assertEqual(set(['rev2c', 'rev3a']),
844
graph.heads(['rev2c', 'rev3a']))
846
def _run_heads_break_deeper(self, graph_dict, search):
847
"""Run heads on a graph-as-a-dict.
849
If the search asks for the parents of 'deeper' the test will fail.
853
def get_parent_map(keys):
857
self.fail('key deeper was accessed')
858
result[key] = graph_dict[key]
861
an_obj.get_parent_map = get_parent_map
862
graph = _mod_graph.Graph(an_obj)
863
return graph.heads(search)
865
def test_heads_limits_search(self):
866
# test that a heads query does not search all of history
872
self.assertEqual(set(['left', 'right']),
873
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
875
def test_heads_limits_search_assymetric(self):
876
# test that a heads query does not search all of history
879
'midleft':['common'],
881
'common':['aftercommon'],
882
'aftercommon':['deeper'],
884
self.assertEqual(set(['left', 'right']),
885
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
887
def test_heads_limits_search_common_search_must_continue(self):
888
# test that common nodes are still queried, preventing
889
# all-the-way-to-origin behaviour in the following graph:
891
'h1':['shortcut', 'common1'],
893
'shortcut':['common2'],
894
'common1':['common2'],
895
'common2':['deeper'],
897
self.assertEqual(set(['h1', 'h2']),
898
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
900
def test_breadth_first_search_start_ghosts(self):
901
graph = self.make_graph({})
902
# with_ghosts reports the ghosts
903
search = graph._make_breadth_first_searcher(['a-ghost'])
904
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
905
self.assertRaises(StopIteration, search.next_with_ghosts)
907
search = graph._make_breadth_first_searcher(['a-ghost'])
908
self.assertEqual(set(['a-ghost']), search.next())
909
self.assertRaises(StopIteration, search.next)
911
def test_breadth_first_search_deep_ghosts(self):
912
graph = self.make_graph({
914
'present':['child', 'ghost'],
917
# with_ghosts reports the ghosts
918
search = graph._make_breadth_first_searcher(['head'])
919
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
920
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
921
self.assertEqual((set(['child']), set(['ghost'])),
922
search.next_with_ghosts())
923
self.assertRaises(StopIteration, search.next_with_ghosts)
925
search = graph._make_breadth_first_searcher(['head'])
926
self.assertEqual(set(['head']), search.next())
927
self.assertEqual(set(['present']), search.next())
928
self.assertEqual(set(['child', 'ghost']),
930
self.assertRaises(StopIteration, search.next)
932
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
933
# To make the API robust, we allow calling both next() and
934
# next_with_ghosts() on the same searcher.
935
graph = self.make_graph({
937
'present':['child', 'ghost'],
940
# start with next_with_ghosts
941
search = graph._make_breadth_first_searcher(['head'])
942
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
943
self.assertEqual(set(['present']), search.next())
944
self.assertEqual((set(['child']), set(['ghost'])),
945
search.next_with_ghosts())
946
self.assertRaises(StopIteration, search.next)
948
search = graph._make_breadth_first_searcher(['head'])
949
self.assertEqual(set(['head']), search.next())
950
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
951
self.assertEqual(set(['child', 'ghost']),
953
self.assertRaises(StopIteration, search.next_with_ghosts)
955
def test_breadth_first_change_search(self):
956
# Changing the search should work with both next and next_with_ghosts.
957
graph = self.make_graph({
959
'present':['stopped'],
963
search = graph._make_breadth_first_searcher(['head'])
964
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
965
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
966
self.assertEqual(set(['present']),
967
search.stop_searching_any(['present']))
968
self.assertEqual((set(['other']), set(['other_ghost'])),
969
search.start_searching(['other', 'other_ghost']))
970
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
971
self.assertRaises(StopIteration, search.next_with_ghosts)
973
search = graph._make_breadth_first_searcher(['head'])
974
self.assertEqual(set(['head']), search.next())
975
self.assertEqual(set(['present']), search.next())
976
self.assertEqual(set(['present']),
977
search.stop_searching_any(['present']))
978
search.start_searching(['other', 'other_ghost'])
979
self.assertEqual(set(['other_2']), search.next())
980
self.assertRaises(StopIteration, search.next)
982
def assertSeenAndResult(self, instructions, search, next):
983
"""Check the results of .seen and get_result() for a seach.
985
:param instructions: A list of tuples:
986
(seen, recipe, included_keys, starts, stops).
987
seen, recipe and included_keys are results to check on the search
988
and the searches get_result(). starts and stops are parameters to
989
pass to start_searching and stop_searching_any during each
990
iteration, if they are not None.
991
:param search: The search to use.
992
:param next: A callable to advance the search.
994
for seen, recipe, included_keys, starts, stops in instructions:
995
# Adjust for recipe contract changes that don't vary for all the
997
recipe = ('search',) + recipe
999
if starts is not None:
1000
search.start_searching(starts)
1001
if stops is not None:
1002
search.stop_searching_any(stops)
1003
result = search.get_result()
1004
self.assertEqual(recipe, result.get_recipe())
1005
self.assertEqual(set(included_keys), result.get_keys())
1006
self.assertEqual(seen, search.seen)
1008
def test_breadth_first_get_result_excludes_current_pending(self):
1009
graph = self.make_graph({
1011
'child':[NULL_REVISION],
1014
search = graph._make_breadth_first_searcher(['head'])
1015
# At the start, nothing has been seen, to its all excluded:
1016
result = search.get_result()
1017
self.assertEqual(('search', set(['head']), set(['head']), 0),
1018
result.get_recipe())
1019
self.assertEqual(set(), result.get_keys())
1020
self.assertEqual(set(), search.seen)
1023
(set(['head']), (set(['head']), set(['child']), 1),
1024
['head'], None, None),
1025
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
1026
['head', 'child'], None, None),
1027
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
1028
['head', 'child', NULL_REVISION], None, None),
1030
self.assertSeenAndResult(expected, search, search.next)
1031
# using next_with_ghosts:
1032
search = graph._make_breadth_first_searcher(['head'])
1033
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1035
def test_breadth_first_get_result_starts_stops(self):
1036
graph = self.make_graph({
1038
'child':[NULL_REVISION],
1039
'otherhead':['otherchild'],
1040
'otherchild':['excluded'],
1041
'excluded':[NULL_REVISION],
1044
search = graph._make_breadth_first_searcher([])
1045
# Starting with nothing and adding a search works:
1046
search.start_searching(['head'])
1047
# head has been seen:
1048
result = search.get_result()
1049
self.assertEqual(('search', set(['head']), set(['child']), 1),
1050
result.get_recipe())
1051
self.assertEqual(set(['head']), result.get_keys())
1052
self.assertEqual(set(['head']), search.seen)
1055
# stop at child, and start a new search at otherhead:
1056
# - otherhead counts as seen immediately when start_searching is
1058
(set(['head', 'child', 'otherhead']),
1059
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1060
['head', 'otherhead'], ['otherhead'], ['child']),
1061
(set(['head', 'child', 'otherhead', 'otherchild']),
1062
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1063
['head', 'otherhead', 'otherchild'], None, None),
1064
# stop searching excluded now
1065
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1066
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1067
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1069
self.assertSeenAndResult(expected, search, search.next)
1070
# using next_with_ghosts:
1071
search = graph._make_breadth_first_searcher([])
1072
search.start_searching(['head'])
1073
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1075
def test_breadth_first_stop_searching_not_queried(self):
1076
# A client should be able to say 'stop node X' even if X has not been
1077
# returned to the client.
1078
graph = self.make_graph({
1079
'head':['child', 'ghost1'],
1080
'child':[NULL_REVISION],
1083
search = graph._make_breadth_first_searcher(['head'])
1085
# NULL_REVISION and ghost1 have not been returned
1087
(set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1088
['head'], None, [NULL_REVISION, 'ghost1']),
1089
# ghost1 has been returned, NULL_REVISION is to be returned in the
1091
(set(['head', 'child', 'ghost1']),
1092
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1093
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1095
self.assertSeenAndResult(expected, search, search.next)
1096
# using next_with_ghosts:
1097
search = graph._make_breadth_first_searcher(['head'])
1098
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1100
def test_breadth_first_stop_searching_late(self):
1101
# A client should be able to say 'stop node X' and have it excluded
1102
# from the result even if X was seen in an older iteration of the
1104
graph = self.make_graph({
1107
'child':[NULL_REVISION],
1110
search = graph._make_breadth_first_searcher(['head'])
1112
(set(['head']), (set(['head']), set(['middle']), 1),
1113
['head'], None, None),
1114
(set(['head', 'middle']), (set(['head']), set(['child']), 2),
1115
['head', 'middle'], None, None),
1116
# 'middle' came from the previous iteration, but we don't stop
1117
# searching it until *after* advancing the searcher.
1118
(set(['head', 'middle', 'child']),
1119
(set(['head']), set(['middle', 'child']), 1),
1120
['head'], None, ['middle', 'child']),
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_get_result_ghosts_are_excluded(self):
1128
graph = self.make_graph({
1129
'head':['child', 'ghost'],
1130
'child':[NULL_REVISION],
1133
search = graph._make_breadth_first_searcher(['head'])
1137
(set(['head']), set(['ghost', 'child']), 1),
1138
['head'], None, None),
1139
(set(['head', 'child', 'ghost']),
1140
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1141
['head', 'child'], None, None),
1143
self.assertSeenAndResult(expected, search, search.next)
1144
# using next_with_ghosts:
1145
search = graph._make_breadth_first_searcher(['head'])
1146
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1148
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1149
graph = self.make_graph({
1151
'child':[NULL_REVISION],
1154
search = graph._make_breadth_first_searcher(['head'])
1157
(set(['head', 'ghost']),
1158
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1159
['head'], ['ghost'], None),
1160
(set(['head', 'child', 'ghost']),
1161
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1162
['head', 'child'], None, None),
1164
self.assertSeenAndResult(expected, search, search.next)
1165
# using next_with_ghosts:
1166
search = graph._make_breadth_first_searcher(['head'])
1167
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1169
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1170
graph = self.make_graph({
1171
'head':[NULL_REVISION],
1174
search = graph._make_breadth_first_searcher(['head'])
1178
(set(['head']), set([NULL_REVISION]), 1),
1179
['head'], None, None),
1180
(set(['head', NULL_REVISION]),
1181
(set(['head']), set([]), 2),
1182
['head', NULL_REVISION], None, None),
1184
self.assertSeenAndResult(expected, search, search.next)
1185
# using next_with_ghosts:
1186
search = graph._make_breadth_first_searcher(['head'])
1187
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1189
def test_breadth_first_search_get_result_after_StopIteration(self):
1190
# StopIteration should not invalid anything..
1191
graph = self.make_graph({
1192
'head':[NULL_REVISION],
1195
search = graph._make_breadth_first_searcher(['head'])
1199
(set(['head']), set([NULL_REVISION]), 1),
1200
['head'], None, None),
1201
(set(['head', 'ghost', NULL_REVISION]),
1202
(set(['head', 'ghost']), set(['ghost']), 2),
1203
['head', NULL_REVISION], ['ghost'], None),
1205
self.assertSeenAndResult(expected, search, search.next)
1206
self.assertRaises(StopIteration, search.next)
1207
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1208
result = search.get_result()
1209
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1210
result.get_recipe())
1211
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1212
# using next_with_ghosts:
1213
search = graph._make_breadth_first_searcher(['head'])
1214
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1215
self.assertRaises(StopIteration, search.next)
1216
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1217
result = search.get_result()
1218
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1219
result.get_recipe())
1220
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1223
class TestFindUniqueAncestors(TestGraphBase):
1225
def assertFindUniqueAncestors(self, graph, expected, node, common):
1226
actual = graph.find_unique_ancestors(node, common)
1227
self.assertEqual(expected, sorted(actual))
1229
def test_empty_set(self):
1230
graph = self.make_graph(ancestry_1)
1231
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1232
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1233
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1235
def test_single_node(self):
1236
graph = self.make_graph(ancestry_1)
1237
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1238
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1239
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1241
def test_minimal_ancestry(self):
1242
graph = self.make_breaking_graph(extended_history_shortcut,
1243
[NULL_REVISION, 'a', 'b'])
1244
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1246
graph = self.make_breaking_graph(extended_history_shortcut,
1248
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1250
graph = self.make_breaking_graph(complex_shortcut,
1252
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1253
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1254
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1255
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1257
def test_in_ancestry(self):
1258
graph = self.make_graph(ancestry_1)
1259
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1260
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1262
def test_multiple_revisions(self):
1263
graph = self.make_graph(ancestry_1)
1264
self.assertFindUniqueAncestors(graph,
1265
['rev4'], 'rev4', ['rev3', 'rev2b'])
1266
self.assertFindUniqueAncestors(graph,
1267
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1269
def test_complex_shortcut(self):
1270
graph = self.make_graph(complex_shortcut)
1271
self.assertFindUniqueAncestors(graph,
1272
['h', 'n'], 'n', ['m'])
1273
self.assertFindUniqueAncestors(graph,
1274
['e', 'i', 'm'], 'm', ['n'])
1276
def test_complex_shortcut2(self):
1277
graph = self.make_graph(complex_shortcut2)
1278
self.assertFindUniqueAncestors(graph,
1279
['j', 'u'], 'u', ['t'])
1280
self.assertFindUniqueAncestors(graph,
1283
def test_multiple_interesting_unique(self):
1284
graph = self.make_graph(multiple_interesting_unique)
1285
self.assertFindUniqueAncestors(graph,
1286
['j', 'y'], 'y', ['z'])
1287
self.assertFindUniqueAncestors(graph,
1288
['p', 'z'], 'z', ['y'])
1290
def test_racing_shortcuts(self):
1291
graph = self.make_graph(racing_shortcuts)
1292
self.assertFindUniqueAncestors(graph,
1293
['p', 'q', 'z'], 'z', ['y'])
1294
self.assertFindUniqueAncestors(graph,
1295
['h', 'i', 'j', 'y'], 'j', ['z'])
1298
class TestGraphFindDistanceToNull(TestGraphBase):
1299
"""Test an api that should be able to compute a revno"""
1301
def assertFindDistance(self, revno, graph, target_id, known_ids):
1302
"""Assert the output of Graph.find_distance_to_null()"""
1303
actual = graph.find_distance_to_null(target_id, known_ids)
1304
self.assertEqual(revno, actual)
1306
def test_nothing_known(self):
1307
graph = self.make_graph(ancestry_1)
1308
self.assertFindDistance(0, graph, NULL_REVISION, [])
1309
self.assertFindDistance(1, graph, 'rev1', [])
1310
self.assertFindDistance(2, graph, 'rev2a', [])
1311
self.assertFindDistance(2, graph, 'rev2b', [])
1312
self.assertFindDistance(3, graph, 'rev3', [])
1313
self.assertFindDistance(4, graph, 'rev4', [])
1315
def test_rev_is_ghost(self):
1316
graph = self.make_graph(ancestry_1)
1317
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1318
graph.find_distance_to_null, 'rev_missing', [])
1319
self.assertEqual('rev_missing', e.revision_id)
1320
self.assertEqual('rev_missing', e.ghost_revision_id)
1322
def test_ancestor_is_ghost(self):
1323
graph = self.make_graph({'rev':['parent']})
1324
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1325
graph.find_distance_to_null, 'rev', [])
1326
self.assertEqual('rev', e.revision_id)
1327
self.assertEqual('parent', e.ghost_revision_id)
1329
def test_known_in_ancestry(self):
1330
graph = self.make_graph(ancestry_1)
1331
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1332
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1334
def test_known_in_ancestry_limits(self):
1335
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1336
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1338
def test_target_is_ancestor(self):
1339
graph = self.make_graph(ancestry_1)
1340
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1342
def test_target_is_ancestor_limits(self):
1343
"""We shouldn't search all history if we run into ourselves"""
1344
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1345
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1347
def test_target_parallel_to_known_limits(self):
1348
# Even though the known revision isn't part of the other ancestry, they
1349
# eventually converge
1350
graph = self.make_breaking_graph(with_tail, ['a'])
1351
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1352
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1353
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1354
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1357
class TestFindMergeOrder(TestGraphBase):
1359
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1360
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1362
def test_parents(self):
1363
graph = self.make_graph(ancestry_1)
1364
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1366
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1369
def test_ancestors(self):
1370
graph = self.make_graph(ancestry_1)
1371
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1373
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1376
def test_shortcut_one_ancestor(self):
1377
# When we have enough info, we can stop searching
1378
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1379
# Single ancestors shortcut right away
1380
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1382
def test_shortcut_after_one_ancestor(self):
1383
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1384
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1387
class TestCachingParentsProvider(tests.TestCase):
1388
"""These tests run with:
1390
self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1392
self.caching_pp, a CachingParentsProvider layered on inst_pp.
1396
super(TestCachingParentsProvider, self).setUp()
1397
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1398
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1399
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1401
def test_get_parent_map(self):
1402
"""Requesting the same revision should be returned from cache"""
1403
self.assertEqual({}, self.caching_pp._cache)
1404
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1405
self.assertEqual(['a'], self.inst_pp.calls)
1406
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1407
# No new call, as it should have been returned from the cache
1408
self.assertEqual(['a'], self.inst_pp.calls)
1409
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1411
def test_get_parent_map_not_present(self):
1412
"""The cache should also track when a revision doesn't exist"""
1413
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1414
self.assertEqual(['b'], self.inst_pp.calls)
1415
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1417
self.assertEqual(['b'], self.inst_pp.calls)
1419
def test_get_parent_map_mixed(self):
1420
"""Anything that can be returned from cache, should be"""
1421
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1422
self.assertEqual(['b'], self.inst_pp.calls)
1423
self.assertEqual({'a':('b',)},
1424
self.caching_pp.get_parent_map(['a', 'b']))
1425
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1427
def test_get_parent_map_repeated(self):
1428
"""Asking for the same parent 2x will only forward 1 request."""
1429
self.assertEqual({'a':('b',)},
1430
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1431
# Use sorted because we don't care about the order, just that each is
1432
# only present 1 time.
1433
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1435
def test_note_missing_key(self):
1436
"""After noting that a key is missing it is cached."""
1437
self.caching_pp.note_missing_key('b')
1438
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1439
self.assertEqual([], self.inst_pp.calls)
1440
self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1443
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1444
"""Test the behaviour when parents are provided that were not requested."""
1447
super(TestCachingParentsProviderExtras, self).setUp()
1448
class ExtraParentsProvider(object):
1450
def get_parent_map(self, keys):
1451
return {'rev1': [], 'rev2': ['rev1',]}
1453
self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1454
self.caching_pp = _mod_graph.CachingParentsProvider(
1455
get_parent_map=self.inst_pp.get_parent_map)
1457
def test_uncached(self):
1458
self.caching_pp.disable_cache()
1459
self.assertEqual({'rev1': []},
1460
self.caching_pp.get_parent_map(['rev1']))
1461
self.assertEqual(['rev1'], self.inst_pp.calls)
1462
self.assertIs(None, self.caching_pp._cache)
1464
def test_cache_initially_empty(self):
1465
self.assertEqual({}, self.caching_pp._cache)
1467
def test_cached(self):
1468
self.assertEqual({'rev1': []},
1469
self.caching_pp.get_parent_map(['rev1']))
1470
self.assertEqual(['rev1'], self.inst_pp.calls)
1471
self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1472
self.caching_pp._cache)
1473
self.assertEqual({'rev1': []},
1474
self.caching_pp.get_parent_map(['rev1']))
1475
self.assertEqual(['rev1'], self.inst_pp.calls)
1477
def test_disable_cache_clears_cache(self):
1478
# Put something in the cache
1479
self.caching_pp.get_parent_map(['rev1'])
1480
self.assertEqual(2, len(self.caching_pp._cache))
1481
self.caching_pp.disable_cache()
1482
self.assertIs(None, self.caching_pp._cache)
1484
def test_enable_cache_raises(self):
1485
e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1486
self.assertEqual('Cache enabled when already enabled.', str(e))
1488
def test_cache_misses(self):
1489
self.caching_pp.get_parent_map(['rev3'])
1490
self.caching_pp.get_parent_map(['rev3'])
1491
self.assertEqual(['rev3'], self.inst_pp.calls)
1493
def test_no_cache_misses(self):
1494
self.caching_pp.disable_cache()
1495
self.caching_pp.enable_cache(cache_misses=False)
1496
self.caching_pp.get_parent_map(['rev3'])
1497
self.caching_pp.get_parent_map(['rev3'])
1498
self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1500
def test_cache_extras(self):
1501
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1502
self.assertEqual({'rev2': ['rev1']},
1503
self.caching_pp.get_parent_map(['rev2']))
1504
self.assertEqual(['rev3'], self.inst_pp.calls)
1507
class TestCollapseLinearRegions(tests.TestCase):
1509
def assertCollapsed(self, collapsed, original):
1510
self.assertEqual(collapsed,
1511
_mod_graph.collapse_linear_regions(original))
1513
def test_collapse_nothing(self):
1514
d = {1:[2, 3], 2:[], 3:[]}
1515
self.assertCollapsed(d, d)
1516
d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1517
self.assertCollapsed(d, d)
1519
def test_collapse_chain(self):
1520
# Any time we have a linear chain, we should be able to collapse
1521
d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1522
self.assertCollapsed({1:[5], 5:[]}, d)
1523
d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1524
self.assertCollapsed({5:[1], 1:[]}, d)
1525
d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1526
self.assertCollapsed({5:[2], 2:[]}, d)
1528
def test_collapse_with_multiple_children(self):
1539
# 4 and 5 cannot be removed because 6 has 2 children
1540
# 2 and 3 cannot be removed because 1 has 2 parents
1541
d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1542
self.assertCollapsed(d, d)
1545
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1546
"""Tests for bzrlib.graph.PendingAncestryResult."""
1548
def test_get_keys(self):
1549
builder = self.make_branch_builder('b')
1550
builder.start_series()
1551
builder.build_snapshot('rev-1', None, [
1552
('add', ('', 'root-id', 'directory', ''))])
1553
builder.build_snapshot('rev-2', ['rev-1'], [])
1554
builder.finish_series()
1555
repo = builder.get_branch().repository
1557
self.addCleanup(repo.unlock)
1558
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1559
self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1561
def test_get_keys_excludes_null(self):
1562
# Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1563
# somewhere other than the last element, which can happen in real
1565
class StubGraph(object):
1566
def iter_ancestry(self, keys):
1567
return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1568
result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1569
result_keys = result._get_keys(StubGraph())
1570
# Only the non-null keys from the ancestry appear.
1571
self.assertEqual(set(['foo']), set(result_keys))
1574
class TestPendingAncestryResultRefine(TestGraphBase):
1576
def test_refine(self):
1577
# Used when pulling from a stacked repository, so test some revisions
1578
# being satisfied from the stacking branch.
1579
g = self.make_graph(
1580
{"tip":["mid"], "mid":["base"], "tag":["base"],
1581
"base":[NULL_REVISION], NULL_REVISION:[]})
1582
result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1583
result = result.refine(set(['tip']), set(['mid']))
1584
self.assertEqual(set(['mid', 'tag']), result.heads)
1585
result = result.refine(set(['mid', 'tag', 'base']),
1586
set([NULL_REVISION]))
1587
self.assertEqual(set([NULL_REVISION]), result.heads)
1588
self.assertTrue(result.is_empty())
1591
class TestSearchResultRefine(TestGraphBase):
1593
def test_refine(self):
1594
# Used when pulling from a stacked repository, so test some revisions
1595
# being satisfied from the stacking branch.
1596
g = self.make_graph(
1597
{"tip":["mid"], "mid":["base"], "tag":["base"],
1598
"base":[NULL_REVISION], NULL_REVISION:[]})
1599
result = _mod_graph.SearchResult(set(['tip', 'tag']),
1600
set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1601
result = result.refine(set(['tip']), set(['mid']))
1602
recipe = result.get_recipe()
1603
# We should be starting from tag (original head) and mid (seen ref)
1604
self.assertEqual(set(['mid', 'tag']), recipe[1])
1605
# We should be stopping at NULL (original stop) and tip (seen head)
1606
self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1607
self.assertEqual(3, recipe[3])
1608
result = result.refine(set(['mid', 'tag', 'base']),
1609
set([NULL_REVISION]))
1610
recipe = result.get_recipe()
1611
# We should be starting from nothing (NULL was known as a cut point)
1612
self.assertEqual(set([]), recipe[1])
1613
# We should be stopping at NULL (original stop) and tip (seen head) and
1614
# tag (seen head) and mid(seen mid-point head). We could come back and
1615
# define this as not including mid, for minimal results, but it is
1616
# still 'correct' to include mid, and simpler/easier.
1617
self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1618
self.assertEqual(0, recipe[3])
1619
self.assertTrue(result.is_empty())
added
removed
bzrlib/tests/test_graph.py
