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
1084
(set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1085
['head'], None, [NULL_REVISION, 'ghost1']),
1086
# ghost1 has been returned, NULL_REVISION is to be returned in the
1088
(set(['head', 'child', 'ghost1']),
1089
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1090
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1092
self.assertSeenAndResult(expected, search, search.next)
1093
# using next_with_ghosts:
1094
search = graph._make_breadth_first_searcher(['head'])
1095
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1097
def test_breadth_first_stop_searching_late(self):
1098
# A client should be able to say 'stop node X' and have it excluded
1099
# from the result even if X was seen in an older iteration of the
1101
graph = self.make_graph({
1104
'child':[NULL_REVISION],
1107
search = graph._make_breadth_first_searcher(['head'])
1109
(set(['head']), (set(['head']), set(['middle']), 1),
1110
['head'], None, None),
1111
(set(['head', 'middle']), (set(['head']), set(['child']), 2),
1112
['head', 'middle'], None, None),
1113
# 'middle' came from the previous iteration, but we don't stop
1114
# searching it until *after* advancing the searcher.
1115
(set(['head', 'middle', 'child']),
1116
(set(['head']), set(['middle', 'child']), 1),
1117
['head'], None, ['middle', 'child']),
1119
self.assertSeenAndResult(expected, search, search.next)
1120
# using next_with_ghosts:
1121
search = graph._make_breadth_first_searcher(['head'])
1122
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1124
def test_breadth_first_get_result_ghosts_are_excluded(self):
1125
graph = self.make_graph({
1126
'head':['child', 'ghost'],
1127
'child':[NULL_REVISION],
1130
search = graph._make_breadth_first_searcher(['head'])
1134
(set(['head']), set(['ghost', 'child']), 1),
1135
['head'], None, None),
1136
(set(['head', 'child', 'ghost']),
1137
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1138
['head', 'child'], None, None),
1140
self.assertSeenAndResult(expected, search, search.next)
1141
# using next_with_ghosts:
1142
search = graph._make_breadth_first_searcher(['head'])
1143
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1145
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1146
graph = self.make_graph({
1148
'child':[NULL_REVISION],
1151
search = graph._make_breadth_first_searcher(['head'])
1154
(set(['head', 'ghost']),
1155
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1156
['head'], ['ghost'], None),
1157
(set(['head', 'child', 'ghost']),
1158
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1159
['head', 'child'], None, None),
1161
self.assertSeenAndResult(expected, search, search.next)
1162
# using next_with_ghosts:
1163
search = graph._make_breadth_first_searcher(['head'])
1164
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1166
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1167
graph = self.make_graph({
1168
'head':[NULL_REVISION],
1171
search = graph._make_breadth_first_searcher(['head'])
1175
(set(['head']), set([NULL_REVISION]), 1),
1176
['head'], None, None),
1177
(set(['head', NULL_REVISION]),
1178
(set(['head']), set([]), 2),
1179
['head', NULL_REVISION], None, None),
1181
self.assertSeenAndResult(expected, search, search.next)
1182
# using next_with_ghosts:
1183
search = graph._make_breadth_first_searcher(['head'])
1184
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1186
def test_breadth_first_search_get_result_after_StopIteration(self):
1187
# StopIteration should not invalid anything..
1188
graph = self.make_graph({
1189
'head':[NULL_REVISION],
1192
search = graph._make_breadth_first_searcher(['head'])
1196
(set(['head']), set([NULL_REVISION]), 1),
1197
['head'], None, None),
1198
(set(['head', 'ghost', NULL_REVISION]),
1199
(set(['head', 'ghost']), set(['ghost']), 2),
1200
['head', NULL_REVISION], ['ghost'], None),
1202
self.assertSeenAndResult(expected, search, search.next)
1203
self.assertRaises(StopIteration, search.next)
1204
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1205
result = search.get_result()
1206
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1207
result.get_recipe())
1208
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1209
# using next_with_ghosts:
1210
search = graph._make_breadth_first_searcher(['head'])
1211
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1212
self.assertRaises(StopIteration, search.next)
1213
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1214
result = search.get_result()
1215
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1216
result.get_recipe())
1217
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1220
class TestFindUniqueAncestors(TestGraphBase):
1222
def assertFindUniqueAncestors(self, graph, expected, node, common):
1223
actual = graph.find_unique_ancestors(node, common)
1224
self.assertEqual(expected, sorted(actual))
1226
def test_empty_set(self):
1227
graph = self.make_graph(ancestry_1)
1228
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1229
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1230
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1232
def test_single_node(self):
1233
graph = self.make_graph(ancestry_1)
1234
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1235
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1236
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1238
def test_minimal_ancestry(self):
1239
graph = self.make_breaking_graph(extended_history_shortcut,
1240
[NULL_REVISION, 'a', 'b'])
1241
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1243
graph = self.make_breaking_graph(extended_history_shortcut,
1245
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1247
graph = self.make_breaking_graph(complex_shortcut,
1249
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1250
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1251
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1252
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1254
def test_in_ancestry(self):
1255
graph = self.make_graph(ancestry_1)
1256
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1257
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1259
def test_multiple_revisions(self):
1260
graph = self.make_graph(ancestry_1)
1261
self.assertFindUniqueAncestors(graph,
1262
['rev4'], 'rev4', ['rev3', 'rev2b'])
1263
self.assertFindUniqueAncestors(graph,
1264
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1266
def test_complex_shortcut(self):
1267
graph = self.make_graph(complex_shortcut)
1268
self.assertFindUniqueAncestors(graph,
1269
['h', 'n'], 'n', ['m'])
1270
self.assertFindUniqueAncestors(graph,
1271
['e', 'i', 'm'], 'm', ['n'])
1273
def test_complex_shortcut2(self):
1274
graph = self.make_graph(complex_shortcut2)
1275
self.assertFindUniqueAncestors(graph,
1276
['j', 'u'], 'u', ['t'])
1277
self.assertFindUniqueAncestors(graph,
1280
def test_multiple_interesting_unique(self):
1281
graph = self.make_graph(multiple_interesting_unique)
1282
self.assertFindUniqueAncestors(graph,
1283
['j', 'y'], 'y', ['z'])
1284
self.assertFindUniqueAncestors(graph,
1285
['p', 'z'], 'z', ['y'])
1287
def test_racing_shortcuts(self):
1288
graph = self.make_graph(racing_shortcuts)
1289
self.assertFindUniqueAncestors(graph,
1290
['p', 'q', 'z'], 'z', ['y'])
1291
self.assertFindUniqueAncestors(graph,
1292
['h', 'i', 'j', 'y'], 'j', ['z'])
1295
class TestGraphFindDistanceToNull(TestGraphBase):
1296
"""Test an api that should be able to compute a revno"""
1298
def assertFindDistance(self, revno, graph, target_id, known_ids):
1299
"""Assert the output of Graph.find_distance_to_null()"""
1300
actual = graph.find_distance_to_null(target_id, known_ids)
1301
self.assertEqual(revno, actual)
1303
def test_nothing_known(self):
1304
graph = self.make_graph(ancestry_1)
1305
self.assertFindDistance(0, graph, NULL_REVISION, [])
1306
self.assertFindDistance(1, graph, 'rev1', [])
1307
self.assertFindDistance(2, graph, 'rev2a', [])
1308
self.assertFindDistance(2, graph, 'rev2b', [])
1309
self.assertFindDistance(3, graph, 'rev3', [])
1310
self.assertFindDistance(4, graph, 'rev4', [])
1312
def test_rev_is_ghost(self):
1313
graph = self.make_graph(ancestry_1)
1314
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1315
graph.find_distance_to_null, 'rev_missing', [])
1316
self.assertEqual('rev_missing', e.revision_id)
1317
self.assertEqual('rev_missing', e.ghost_revision_id)
1319
def test_ancestor_is_ghost(self):
1320
graph = self.make_graph({'rev':['parent']})
1321
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1322
graph.find_distance_to_null, 'rev', [])
1323
self.assertEqual('rev', e.revision_id)
1324
self.assertEqual('parent', e.ghost_revision_id)
1326
def test_known_in_ancestry(self):
1327
graph = self.make_graph(ancestry_1)
1328
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1329
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1331
def test_known_in_ancestry_limits(self):
1332
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1333
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1335
def test_target_is_ancestor(self):
1336
graph = self.make_graph(ancestry_1)
1337
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1339
def test_target_is_ancestor_limits(self):
1340
"""We shouldn't search all history if we run into ourselves"""
1341
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1342
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1344
def test_target_parallel_to_known_limits(self):
1345
# Even though the known revision isn't part of the other ancestry, they
1346
# eventually converge
1347
graph = self.make_breaking_graph(with_tail, ['a'])
1348
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1349
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1350
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1351
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1354
class TestFindMergeOrder(TestGraphBase):
1356
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1357
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1359
def test_parents(self):
1360
graph = self.make_graph(ancestry_1)
1361
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1363
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1366
def test_ancestors(self):
1367
graph = self.make_graph(ancestry_1)
1368
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1370
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1373
def test_shortcut_one_ancestor(self):
1374
# When we have enough info, we can stop searching
1375
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1376
# Single ancestors shortcut right away
1377
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1379
def test_shortcut_after_one_ancestor(self):
1380
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1381
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1384
class TestCachingParentsProvider(tests.TestCase):
1387
super(TestCachingParentsProvider, self).setUp()
1388
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1389
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1390
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1392
def test_get_parent_map(self):
1393
"""Requesting the same revision should be returned from cache"""
1394
self.assertEqual({}, self.caching_pp._cache)
1395
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1396
self.assertEqual(['a'], self.inst_pp.calls)
1397
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1398
# No new call, as it should have been returned from the cache
1399
self.assertEqual(['a'], self.inst_pp.calls)
1400
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1402
def test_get_parent_map_not_present(self):
1403
"""The cache should also track when a revision doesn't exist"""
1404
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1405
self.assertEqual(['b'], self.inst_pp.calls)
1406
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1408
self.assertEqual(['b'], self.inst_pp.calls)
1409
self.assertEqual({'b':None}, self.caching_pp._cache)
1411
def test_get_parent_map_mixed(self):
1412
"""Anything that can be returned from cache, should be"""
1413
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1414
self.assertEqual(['b'], self.inst_pp.calls)
1415
self.assertEqual({'a':('b',)},
1416
self.caching_pp.get_parent_map(['a', 'b']))
1417
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1419
def test_get_parent_map_repeated(self):
1420
"""Asking for the same parent 2x will only forward 1 request."""
1421
self.assertEqual({'a':('b',)},
1422
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1423
# Use sorted because we don't care about the order, just that each is
1424
# only present 1 time.
1425
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1428
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1429
"""Test the behaviour when parents are provided that were not requested."""
1432
super(TestCachingParentsProviderExtras, self).setUp()
1433
class ExtraParentsProvider(object):
1435
def get_parent_map(self, keys):
1436
return {'rev1': [], 'rev2': ['rev1',]}
1438
self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1439
self.caching_pp = _mod_graph.CachingParentsProvider(
1440
get_parent_map=self.inst_pp.get_parent_map)
1442
def test_uncached(self):
1443
self.caching_pp.disable_cache()
1444
self.assertEqual({'rev1': []},
1445
self.caching_pp.get_parent_map(['rev1']))
1446
self.assertEqual(['rev1'], self.inst_pp.calls)
1447
self.assertIs(None, self.caching_pp._cache)
1449
def test_cache_initially_empty(self):
1450
self.assertEqual({}, self.caching_pp._cache)
1452
def test_cached(self):
1453
self.assertEqual({'rev1': []},
1454
self.caching_pp.get_parent_map(['rev1']))
1455
self.assertEqual(['rev1'], self.inst_pp.calls)
1456
self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1457
self.caching_pp._cache)
1458
self.assertEqual({'rev1': []},
1459
self.caching_pp.get_parent_map(['rev1']))
1460
self.assertEqual(['rev1'], self.inst_pp.calls)
1462
def test_disable_cache_clears_cache(self):
1463
# Put something in the cache
1464
self.caching_pp.get_parent_map(['rev1'])
1465
self.assertEqual(2, len(self.caching_pp._cache))
1466
self.caching_pp.disable_cache()
1467
self.assertIs(None, self.caching_pp._cache)
1469
def test_enable_cache_raises(self):
1470
e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1471
self.assertEqual('Cache enabled when already enabled.', str(e))
1473
def test_cache_misses(self):
1474
self.caching_pp.get_parent_map(['rev3'])
1475
self.caching_pp.get_parent_map(['rev3'])
1476
self.assertEqual(['rev3'], self.inst_pp.calls)
1478
def test_no_cache_misses(self):
1479
self.caching_pp.disable_cache()
1480
self.caching_pp.enable_cache(cache_misses=False)
1481
self.caching_pp.get_parent_map(['rev3'])
1482
self.caching_pp.get_parent_map(['rev3'])
1483
self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1485
def test_cache_extras(self):
1486
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1487
self.assertEqual({'rev2': ['rev1']},
1488
self.caching_pp.get_parent_map(['rev2']))
1489
self.assertEqual(['rev3'], self.inst_pp.calls)
1492
class TestCollapseLinearRegions(tests.TestCase):
1494
def assertCollapsed(self, collapsed, original):
1495
self.assertEqual(collapsed,
1496
_mod_graph.collapse_linear_regions(original))
1498
def test_collapse_nothing(self):
1499
d = {1:[2, 3], 2:[], 3:[]}
1500
self.assertCollapsed(d, d)
1501
d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1502
self.assertCollapsed(d, d)
1504
def test_collapse_chain(self):
1505
# Any time we have a linear chain, we should be able to collapse
1506
d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1507
self.assertCollapsed({1:[5], 5:[]}, d)
1508
d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1509
self.assertCollapsed({5:[1], 1:[]}, d)
1510
d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1511
self.assertCollapsed({5:[2], 2:[]}, d)
1513
def test_collapse_with_multiple_children(self):
1524
# 4 and 5 cannot be removed because 6 has 2 children
1525
# 2 and 3 cannot be removed because 1 has 2 parents
1526
d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1527
self.assertCollapsed(d, d)
added
removed
bzrlib/tests/test_graph.py
