1
# Copyright (C) 2007 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23
from bzrlib.revision import NULL_REVISION
24
from bzrlib.tests import TestCaseWithMemoryTransport
38
ancestry_1 = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
39
'rev3': ['rev2a'], 'rev4': ['rev3', 'rev2b']}
53
ancestry_2 = {'rev1a': [NULL_REVISION], 'rev2a': ['rev1a'],
54
'rev1b': [NULL_REVISION], 'rev3a': ['rev2a'], 'rev4a': ['rev3a']}
57
# Criss cross ancestry
68
criss_cross = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
69
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2a']}
83
criss_cross2 = {'rev1a': [NULL_REVISION], 'rev1b': [NULL_REVISION],
84
'rev2a': ['rev1a', 'rev1b'], 'rev2b': ['rev1b', 'rev1a']}
96
mainline = {'rev1': [NULL_REVISION], 'rev2a': ['rev1', 'rev2b'],
109
feature_branch = {'rev1': [NULL_REVISION],
110
'rev2b': ['rev1'], 'rev3b': ['rev2b']}
121
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
122
'rev2b': ['rev1'], 'rev2c': ['rev1'],
123
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
125
# Extended history shortcut
137
extended_history_shortcut = {'a': [NULL_REVISION],
146
# Both sides will see 'A' first, even though it is actually a decendent of a
147
# different common revision.
161
double_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
162
'd':['c'], 'e':['c'], 'f':['a', 'd'],
166
# This has a failure mode in that a shortcut will find some nodes in common,
167
# but the common searcher won't have time to find that one branch is actually
168
# in common. The extra nodes at the 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:
996
if starts is not None:
997
search.start_searching(starts)
998
if stops is not None:
999
search.stop_searching_any(stops)
1000
result = search.get_result()
1001
self.assertEqual(recipe, result.get_recipe())
1002
self.assertEqual(set(included_keys), result.get_keys())
1003
self.assertEqual(seen, search.seen)
1005
def test_breadth_first_get_result_excludes_current_pending(self):
1006
graph = self.make_graph({
1008
'child':[NULL_REVISION],
1011
search = graph._make_breadth_first_searcher(['head'])
1012
# At the start, nothing has been seen, to its all excluded:
1013
result = search.get_result()
1014
self.assertEqual((set(['head']), set(['head']), 0),
1015
result.get_recipe())
1016
self.assertEqual(set(), result.get_keys())
1017
self.assertEqual(set(), search.seen)
1020
(set(['head']), (set(['head']), set(['child']), 1),
1021
['head'], None, None),
1022
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
1023
['head', 'child'], None, None),
1024
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
1025
['head', 'child', NULL_REVISION], None, None),
1027
self.assertSeenAndResult(expected, search, search.next)
1028
# using next_with_ghosts:
1029
search = graph._make_breadth_first_searcher(['head'])
1030
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1032
def test_breadth_first_get_result_starts_stops(self):
1033
graph = self.make_graph({
1035
'child':[NULL_REVISION],
1036
'otherhead':['otherchild'],
1037
'otherchild':['excluded'],
1038
'excluded':[NULL_REVISION],
1041
search = graph._make_breadth_first_searcher([])
1042
# Starting with nothing and adding a search works:
1043
search.start_searching(['head'])
1044
# head has been seen:
1045
result = search.get_result()
1046
self.assertEqual((set(['head']), set(['child']), 1),
1047
result.get_recipe())
1048
self.assertEqual(set(['head']), result.get_keys())
1049
self.assertEqual(set(['head']), search.seen)
1052
# stop at child, and start a new search at otherhead:
1053
# - otherhead counts as seen immediately when start_searching is
1055
(set(['head', 'child', 'otherhead']),
1056
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1057
['head', 'otherhead'], ['otherhead'], ['child']),
1058
(set(['head', 'child', 'otherhead', 'otherchild']),
1059
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1060
['head', 'otherhead', 'otherchild'], None, None),
1061
# stop searching excluded now
1062
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1063
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1064
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1066
self.assertSeenAndResult(expected, search, search.next)
1067
# using next_with_ghosts:
1068
search = graph._make_breadth_first_searcher([])
1069
search.start_searching(['head'])
1070
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1072
def test_breadth_first_stop_searching_not_queried(self):
1073
# A client should be able to say 'stop node X' even if X has not been
1074
# returned to the client.
1075
graph = self.make_graph({
1076
'head':['child', 'ghost1'],
1077
'child':[NULL_REVISION],
1080
search = graph._make_breadth_first_searcher(['head'])
1082
# NULL_REVISION and ghost1 have not been returned
1083
(set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
1084
['head'], None, [NULL_REVISION, 'ghost1']),
1085
# ghost1 has been returned, NULL_REVISION is to be returned in the
1087
(set(['head', 'child', 'ghost1']),
1088
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1089
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1091
self.assertSeenAndResult(expected, search, search.next)
1092
# using next_with_ghosts:
1093
search = graph._make_breadth_first_searcher(['head'])
1094
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1096
def test_breadth_first_stop_searching_late(self):
1097
# A client should be able to say 'stop node X' and have it excluded
1098
# from the result even if X was seen in an older iteration of the
1100
graph = self.make_graph({
1103
'child':[NULL_REVISION],
1106
search = graph._make_breadth_first_searcher(['head'])
1108
(set(['head']), (set(['head']), set(['middle']), 1),
1109
['head'], None, None),
1110
(set(['head', 'middle']), (set(['head']), set(['child']), 2),
1111
['head', 'middle'], None, None),
1112
# 'middle' came from the previous iteration, but we don't stop
1113
# searching it until *after* advancing the searcher.
1114
(set(['head', 'middle', 'child']),
1115
(set(['head']), set(['middle', 'child']), 1),
1116
['head'], None, ['middle', 'child']),
1118
self.assertSeenAndResult(expected, search, search.next)
1119
# using next_with_ghosts:
1120
search = graph._make_breadth_first_searcher(['head'])
1121
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1123
def test_breadth_first_get_result_ghosts_are_excluded(self):
1124
graph = self.make_graph({
1125
'head':['child', 'ghost'],
1126
'child':[NULL_REVISION],
1129
search = graph._make_breadth_first_searcher(['head'])
1133
(set(['head']), set(['ghost', 'child']), 1),
1134
['head'], None, None),
1135
(set(['head', 'child', 'ghost']),
1136
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1137
['head', 'child'], None, None),
1139
self.assertSeenAndResult(expected, search, search.next)
1140
# using next_with_ghosts:
1141
search = graph._make_breadth_first_searcher(['head'])
1142
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1144
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1145
graph = self.make_graph({
1147
'child':[NULL_REVISION],
1150
search = graph._make_breadth_first_searcher(['head'])
1153
(set(['head', 'ghost']),
1154
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1155
['head'], ['ghost'], None),
1156
(set(['head', 'child', 'ghost']),
1157
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1158
['head', 'child'], None, None),
1160
self.assertSeenAndResult(expected, search, search.next)
1161
# using next_with_ghosts:
1162
search = graph._make_breadth_first_searcher(['head'])
1163
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1165
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1166
graph = self.make_graph({
1167
'head':[NULL_REVISION],
1170
search = graph._make_breadth_first_searcher(['head'])
1174
(set(['head']), set([NULL_REVISION]), 1),
1175
['head'], None, None),
1176
(set(['head', NULL_REVISION]),
1177
(set(['head']), set([]), 2),
1178
['head', NULL_REVISION], None, None),
1180
self.assertSeenAndResult(expected, search, search.next)
1181
# using next_with_ghosts:
1182
search = graph._make_breadth_first_searcher(['head'])
1183
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1185
def test_breadth_first_search_get_result_after_StopIteration(self):
1186
# StopIteration should not invalid anything..
1187
graph = self.make_graph({
1188
'head':[NULL_REVISION],
1191
search = graph._make_breadth_first_searcher(['head'])
1195
(set(['head']), set([NULL_REVISION]), 1),
1196
['head'], None, None),
1197
(set(['head', 'ghost', NULL_REVISION]),
1198
(set(['head', 'ghost']), set(['ghost']), 2),
1199
['head', NULL_REVISION], ['ghost'], None),
1201
self.assertSeenAndResult(expected, search, search.next)
1202
self.assertRaises(StopIteration, search.next)
1203
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1204
result = search.get_result()
1205
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1206
result.get_recipe())
1207
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1208
# using next_with_ghosts:
1209
search = graph._make_breadth_first_searcher(['head'])
1210
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1211
self.assertRaises(StopIteration, search.next)
1212
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1213
result = search.get_result()
1214
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1215
result.get_recipe())
1216
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1219
class TestFindUniqueAncestors(TestGraphBase):
1221
def assertFindUniqueAncestors(self, graph, expected, node, common):
1222
actual = graph.find_unique_ancestors(node, common)
1223
self.assertEqual(expected, sorted(actual))
1225
def test_empty_set(self):
1226
graph = self.make_graph(ancestry_1)
1227
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1228
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1229
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1231
def test_single_node(self):
1232
graph = self.make_graph(ancestry_1)
1233
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1234
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1235
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1237
def test_minimal_ancestry(self):
1238
graph = self.make_breaking_graph(extended_history_shortcut,
1239
[NULL_REVISION, 'a', 'b'])
1240
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1242
graph = self.make_breaking_graph(extended_history_shortcut,
1244
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1246
graph = self.make_breaking_graph(complex_shortcut,
1248
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1249
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1250
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1251
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1253
def test_in_ancestry(self):
1254
graph = self.make_graph(ancestry_1)
1255
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1256
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1258
def test_multiple_revisions(self):
1259
graph = self.make_graph(ancestry_1)
1260
self.assertFindUniqueAncestors(graph,
1261
['rev4'], 'rev4', ['rev3', 'rev2b'])
1262
self.assertFindUniqueAncestors(graph,
1263
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1265
def test_complex_shortcut(self):
1266
graph = self.make_graph(complex_shortcut)
1267
self.assertFindUniqueAncestors(graph,
1268
['h', 'n'], 'n', ['m'])
1269
self.assertFindUniqueAncestors(graph,
1270
['e', 'i', 'm'], 'm', ['n'])
1272
def test_complex_shortcut2(self):
1273
graph = self.make_graph(complex_shortcut2)
1274
self.assertFindUniqueAncestors(graph,
1275
['j', 'u'], 'u', ['t'])
1276
self.assertFindUniqueAncestors(graph,
1279
def test_multiple_interesting_unique(self):
1280
graph = self.make_graph(multiple_interesting_unique)
1281
self.assertFindUniqueAncestors(graph,
1282
['j', 'y'], 'y', ['z'])
1283
self.assertFindUniqueAncestors(graph,
1284
['p', 'z'], 'z', ['y'])
1286
def test_racing_shortcuts(self):
1287
graph = self.make_graph(racing_shortcuts)
1288
self.assertFindUniqueAncestors(graph,
1289
['p', 'q', 'z'], 'z', ['y'])
1290
self.assertFindUniqueAncestors(graph,
1291
['h', 'i', 'j', 'y'], 'j', ['z'])
1294
class TestGraphFindDistanceToNull(TestGraphBase):
1295
"""Test an api that should be able to compute a revno"""
1297
def assertFindDistance(self, revno, graph, target_id, known_ids):
1298
"""Assert the output of Graph.find_distance_to_null()"""
1299
actual = graph.find_distance_to_null(target_id, known_ids)
1300
self.assertEqual(revno, actual)
1302
def test_nothing_known(self):
1303
graph = self.make_graph(ancestry_1)
1304
self.assertFindDistance(0, graph, NULL_REVISION, [])
1305
self.assertFindDistance(1, graph, 'rev1', [])
1306
self.assertFindDistance(2, graph, 'rev2a', [])
1307
self.assertFindDistance(2, graph, 'rev2b', [])
1308
self.assertFindDistance(3, graph, 'rev3', [])
1309
self.assertFindDistance(4, graph, 'rev4', [])
1311
def test_rev_is_ghost(self):
1312
graph = self.make_graph(ancestry_1)
1313
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1314
graph.find_distance_to_null, 'rev_missing', [])
1315
self.assertEqual('rev_missing', e.revision_id)
1316
self.assertEqual('rev_missing', e.ghost_revision_id)
1318
def test_ancestor_is_ghost(self):
1319
graph = self.make_graph({'rev':['parent']})
1320
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1321
graph.find_distance_to_null, 'rev', [])
1322
self.assertEqual('rev', e.revision_id)
1323
self.assertEqual('parent', e.ghost_revision_id)
1325
def test_known_in_ancestry(self):
1326
graph = self.make_graph(ancestry_1)
1327
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1328
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1330
def test_known_in_ancestry_limits(self):
1331
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1332
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1334
def test_target_is_ancestor(self):
1335
graph = self.make_graph(ancestry_1)
1336
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1338
def test_target_is_ancestor_limits(self):
1339
"""We shouldn't search all history if we run into ourselves"""
1340
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1341
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1343
def test_target_parallel_to_known_limits(self):
1344
# Even though the known revision isn't part of the other ancestry, they
1345
# eventually converge
1346
graph = self.make_breaking_graph(with_tail, ['a'])
1347
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1348
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1349
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1350
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1353
class TestFindMergeOrder(TestGraphBase):
1355
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1356
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1358
def test_parents(self):
1359
graph = self.make_graph(ancestry_1)
1360
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1362
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1365
def test_ancestors(self):
1366
graph = self.make_graph(ancestry_1)
1367
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1369
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1372
def test_shortcut_one_ancestor(self):
1373
# When we have enough info, we can stop searching
1374
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1375
# Single ancestors shortcut right away
1376
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1378
def test_shortcut_after_one_ancestor(self):
1379
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1380
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1383
class TestCachingParentsProvider(tests.TestCase):
1386
super(TestCachingParentsProvider, self).setUp()
1387
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1388
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1389
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1391
def test_get_parent_map(self):
1392
"""Requesting the same revision should be returned from cache"""
1393
self.assertEqual({}, self.caching_pp._cache)
1394
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1395
self.assertEqual(['a'], self.inst_pp.calls)
1396
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1397
# No new call, as it should have been returned from the cache
1398
self.assertEqual(['a'], self.inst_pp.calls)
1399
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1401
def test_get_parent_map_not_present(self):
1402
"""The cache should also track when a revision doesn't exist"""
1403
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1404
self.assertEqual(['b'], self.inst_pp.calls)
1405
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1407
self.assertEqual(['b'], self.inst_pp.calls)
1408
self.assertEqual({'b':None}, self.caching_pp._cache)
1410
def test_get_parent_map_mixed(self):
1411
"""Anything that can be returned from cache, should be"""
1412
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1413
self.assertEqual(['b'], self.inst_pp.calls)
1414
self.assertEqual({'a':('b',)},
1415
self.caching_pp.get_parent_map(['a', 'b']))
1416
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1418
def test_get_parent_map_repeated(self):
1419
"""Asking for the same parent 2x will only forward 1 request."""
1420
self.assertEqual({'a':('b',)},
1421
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1422
# Use sorted because we don't care about the order, just that each is
1423
# only present 1 time.
1424
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1427
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1428
"""Test the behaviour when parents are provided that were not requested."""
1431
super(TestCachingParentsProviderExtras, self).setUp()
1432
class ExtraParentsProvider(object):
1434
def get_parent_map(self, keys):
1435
return {'rev1': [], 'rev2': ['rev1',]}
1437
self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1438
self.caching_pp = _mod_graph.CachingParentsProvider(
1439
get_parent_map=self.inst_pp.get_parent_map)
1441
def test_uncached(self):
1442
self.caching_pp.disable_cache()
1443
self.assertEqual({'rev1': []},
1444
self.caching_pp.get_parent_map(['rev1']))
1445
self.assertEqual(['rev1'], self.inst_pp.calls)
1446
self.assertIs(None, self.caching_pp._cache)
1448
def test_cache_initially_empty(self):
1449
self.assertEqual({}, self.caching_pp._cache)
1451
def test_cached(self):
1452
self.assertEqual({'rev1': []},
1453
self.caching_pp.get_parent_map(['rev1']))
1454
self.assertEqual(['rev1'], self.inst_pp.calls)
1455
self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1456
self.caching_pp._cache)
1457
self.assertEqual({'rev1': []},
1458
self.caching_pp.get_parent_map(['rev1']))
1459
self.assertEqual(['rev1'], self.inst_pp.calls)
1461
def test_disable_cache_clears_cache(self):
1462
# Put something in the cache
1463
self.caching_pp.get_parent_map(['rev1'])
1464
self.assertEqual(2, len(self.caching_pp._cache))
1465
self.caching_pp.disable_cache()
1466
self.assertIs(None, self.caching_pp._cache)
1468
def test_enable_cache_raises(self):
1469
e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1470
self.assertEqual('Cache enabled when already enabled.', str(e))
1472
def test_cache_misses(self):
1473
self.caching_pp.get_parent_map(['rev3'])
1474
self.caching_pp.get_parent_map(['rev3'])
1475
self.assertEqual(['rev3'], self.inst_pp.calls)
1477
def test_no_cache_misses(self):
1478
self.caching_pp.disable_cache()
1479
self.caching_pp.enable_cache(cache_misses=False)
1480
self.caching_pp.get_parent_map(['rev3'])
1481
self.caching_pp.get_parent_map(['rev3'])
1482
self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1484
def test_cache_extras(self):
1485
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1486
self.assertEqual({'rev2': ['rev1']},
1487
self.caching_pp.get_parent_map(['rev2']))
1488
self.assertEqual(['rev3'], self.inst_pp.calls)
1491
class TestCollapseLinearRegions(tests.TestCase):
1493
def assertCollapsed(self, collapsed, original):
1494
self.assertEqual(collapsed,
1495
_mod_graph.collapse_linear_regions(original))
1497
def test_collapse_nothing(self):
1498
d = {1:[2, 3], 2:[], 3:[]}
1499
self.assertCollapsed(d, d)
1500
d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1501
self.assertCollapsed(d, d)
1503
def test_collapse_chain(self):
1504
# Any time we have a linear chain, we should be able to collapse
1505
d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1506
self.assertCollapsed({1:[5], 5:[]}, d)
1507
d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1508
self.assertCollapsed({5:[1], 1:[]}, d)
1509
d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1510
self.assertCollapsed({5:[2], 2:[]}, d)
1512
def test_collapse_with_multiple_children(self):
1523
# 4 and 5 cannot be removed because 6 has 2 children
1524
# 2 and 3 cannot be removed because 1 has 2 parents
1525
d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1526
self.assertCollapsed(d, d)
added
removed
bzrlib/tests/test_graph.py
