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_ancestor_boundary(self):
702
"""Ensure that we avoid searching the whole graph.
704
This requires searching through b as a common ancestor, so we
705
can identify that e is common.
707
graph = self.make_graph(boundary)
708
instrumented_provider = InstrumentedParentsProvider(graph)
709
graph = _mod_graph.Graph(instrumented_provider)
710
self.assertFalse(graph.is_ancestor('a', 'c'))
711
self.assertTrue('null:' not in instrumented_provider.calls)
713
def test_iter_ancestry(self):
714
nodes = boundary.copy()
715
nodes[NULL_REVISION] = ()
716
graph = self.make_graph(nodes)
717
expected = nodes.copy()
718
expected.pop('a') # 'a' is not in the ancestry of 'c', all the
720
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
721
self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
723
def test_iter_ancestry_with_ghost(self):
724
graph = self.make_graph(with_ghost)
725
expected = with_ghost.copy()
726
# 'a' is not in the ancestry of 'c', and 'g' is a ghost
728
self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
730
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
732
def test_filter_candidate_lca(self):
733
"""Test filter_candidate_lca for a corner case
735
This tests the case where we encounter the end of iteration for 'e'
736
in the same pass as we discover that 'd' is an ancestor of 'e', and
737
therefore 'e' can't be an lca.
739
To compensate for different dict orderings on other Python
740
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
742
# This test is sensitive to the iteration order of dicts. It will
743
# pass incorrectly if 'e' and 'a' sort before 'c'
752
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
753
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
754
self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
756
def test_heads_null(self):
757
graph = self.make_graph(ancestry_1)
758
self.assertEqual(set(['null:']), graph.heads(['null:']))
759
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
760
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
761
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
762
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
764
def test_heads_one(self):
765
# A single node will always be a head
766
graph = self.make_graph(ancestry_1)
767
self.assertEqual(set(['null:']), graph.heads(['null:']))
768
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
769
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
770
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
771
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
772
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
774
def test_heads_single(self):
775
graph = self.make_graph(ancestry_1)
776
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
777
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
778
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
779
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
780
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
781
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
782
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
783
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
785
def test_heads_two_heads(self):
786
graph = self.make_graph(ancestry_1)
787
self.assertEqual(set(['rev2a', 'rev2b']),
788
graph.heads(['rev2a', 'rev2b']))
789
self.assertEqual(set(['rev3', 'rev2b']),
790
graph.heads(['rev3', 'rev2b']))
792
def test_heads_criss_cross(self):
793
graph = self.make_graph(criss_cross)
794
self.assertEqual(set(['rev2a']),
795
graph.heads(['rev2a', 'rev1']))
796
self.assertEqual(set(['rev2b']),
797
graph.heads(['rev2b', 'rev1']))
798
self.assertEqual(set(['rev3a']),
799
graph.heads(['rev3a', 'rev1']))
800
self.assertEqual(set(['rev3b']),
801
graph.heads(['rev3b', 'rev1']))
802
self.assertEqual(set(['rev2a', 'rev2b']),
803
graph.heads(['rev2a', 'rev2b']))
804
self.assertEqual(set(['rev3a']),
805
graph.heads(['rev3a', 'rev2a']))
806
self.assertEqual(set(['rev3a']),
807
graph.heads(['rev3a', 'rev2b']))
808
self.assertEqual(set(['rev3a']),
809
graph.heads(['rev3a', 'rev2a', 'rev2b']))
810
self.assertEqual(set(['rev3b']),
811
graph.heads(['rev3b', 'rev2a']))
812
self.assertEqual(set(['rev3b']),
813
graph.heads(['rev3b', 'rev2b']))
814
self.assertEqual(set(['rev3b']),
815
graph.heads(['rev3b', 'rev2a', 'rev2b']))
816
self.assertEqual(set(['rev3a', 'rev3b']),
817
graph.heads(['rev3a', 'rev3b']))
818
self.assertEqual(set(['rev3a', 'rev3b']),
819
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
821
def test_heads_shortcut(self):
822
graph = self.make_graph(history_shortcut)
824
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
825
graph.heads(['rev2a', 'rev2b', 'rev2c']))
826
self.assertEqual(set(['rev3a', 'rev3b']),
827
graph.heads(['rev3a', 'rev3b']))
828
self.assertEqual(set(['rev3a', 'rev3b']),
829
graph.heads(['rev2a', 'rev3a', 'rev3b']))
830
self.assertEqual(set(['rev2a', 'rev3b']),
831
graph.heads(['rev2a', 'rev3b']))
832
self.assertEqual(set(['rev2c', 'rev3a']),
833
graph.heads(['rev2c', 'rev3a']))
835
def _run_heads_break_deeper(self, graph_dict, search):
836
"""Run heads on a graph-as-a-dict.
838
If the search asks for the parents of 'deeper' the test will fail.
842
def get_parent_map(keys):
846
self.fail('key deeper was accessed')
847
result[key] = graph_dict[key]
850
an_obj.get_parent_map = get_parent_map
851
graph = _mod_graph.Graph(an_obj)
852
return graph.heads(search)
854
def test_heads_limits_search(self):
855
# test that a heads query does not search all of history
861
self.assertEqual(set(['left', 'right']),
862
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
864
def test_heads_limits_search_assymetric(self):
865
# test that a heads query does not search all of history
868
'midleft':['common'],
870
'common':['aftercommon'],
871
'aftercommon':['deeper'],
873
self.assertEqual(set(['left', 'right']),
874
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
876
def test_heads_limits_search_common_search_must_continue(self):
877
# test that common nodes are still queried, preventing
878
# all-the-way-to-origin behaviour in the following graph:
880
'h1':['shortcut', 'common1'],
882
'shortcut':['common2'],
883
'common1':['common2'],
884
'common2':['deeper'],
886
self.assertEqual(set(['h1', 'h2']),
887
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
889
def test_breadth_first_search_start_ghosts(self):
890
graph = self.make_graph({})
891
# with_ghosts reports the ghosts
892
search = graph._make_breadth_first_searcher(['a-ghost'])
893
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
894
self.assertRaises(StopIteration, search.next_with_ghosts)
896
search = graph._make_breadth_first_searcher(['a-ghost'])
897
self.assertEqual(set(['a-ghost']), search.next())
898
self.assertRaises(StopIteration, search.next)
900
def test_breadth_first_search_deep_ghosts(self):
901
graph = self.make_graph({
903
'present':['child', 'ghost'],
906
# with_ghosts reports the ghosts
907
search = graph._make_breadth_first_searcher(['head'])
908
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
909
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
910
self.assertEqual((set(['child']), set(['ghost'])),
911
search.next_with_ghosts())
912
self.assertRaises(StopIteration, search.next_with_ghosts)
914
search = graph._make_breadth_first_searcher(['head'])
915
self.assertEqual(set(['head']), search.next())
916
self.assertEqual(set(['present']), search.next())
917
self.assertEqual(set(['child', 'ghost']),
919
self.assertRaises(StopIteration, search.next)
921
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
922
# To make the API robust, we allow calling both next() and
923
# next_with_ghosts() on the same searcher.
924
graph = self.make_graph({
926
'present':['child', 'ghost'],
929
# start with next_with_ghosts
930
search = graph._make_breadth_first_searcher(['head'])
931
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
932
self.assertEqual(set(['present']), search.next())
933
self.assertEqual((set(['child']), set(['ghost'])),
934
search.next_with_ghosts())
935
self.assertRaises(StopIteration, search.next)
937
search = graph._make_breadth_first_searcher(['head'])
938
self.assertEqual(set(['head']), search.next())
939
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
940
self.assertEqual(set(['child', 'ghost']),
942
self.assertRaises(StopIteration, search.next_with_ghosts)
944
def test_breadth_first_change_search(self):
945
# Changing the search should work with both next and next_with_ghosts.
946
graph = self.make_graph({
948
'present':['stopped'],
952
search = graph._make_breadth_first_searcher(['head'])
953
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
954
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
955
self.assertEqual(set(['present']),
956
search.stop_searching_any(['present']))
957
self.assertEqual((set(['other']), set(['other_ghost'])),
958
search.start_searching(['other', 'other_ghost']))
959
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
960
self.assertRaises(StopIteration, search.next_with_ghosts)
962
search = graph._make_breadth_first_searcher(['head'])
963
self.assertEqual(set(['head']), search.next())
964
self.assertEqual(set(['present']), search.next())
965
self.assertEqual(set(['present']),
966
search.stop_searching_any(['present']))
967
search.start_searching(['other', 'other_ghost'])
968
self.assertEqual(set(['other_2']), search.next())
969
self.assertRaises(StopIteration, search.next)
971
def assertSeenAndResult(self, instructions, search, next):
972
"""Check the results of .seen and get_result() for a seach.
974
:param instructions: A list of tuples:
975
(seen, recipe, included_keys, starts, stops).
976
seen, recipe and included_keys are results to check on the search
977
and the searches get_result(). starts and stops are parameters to
978
pass to start_searching and stop_searching_any during each
979
iteration, if they are not None.
980
:param search: The search to use.
981
:param next: A callable to advance the search.
983
for seen, recipe, included_keys, starts, stops in instructions:
985
if starts is not None:
986
search.start_searching(starts)
987
if stops is not None:
988
search.stop_searching_any(stops)
989
result = search.get_result()
990
self.assertEqual(recipe, result.get_recipe())
991
self.assertEqual(set(included_keys), result.get_keys())
992
self.assertEqual(seen, search.seen)
994
def test_breadth_first_get_result_excludes_current_pending(self):
995
graph = self.make_graph({
997
'child':[NULL_REVISION],
1000
search = graph._make_breadth_first_searcher(['head'])
1001
# At the start, nothing has been seen, to its all excluded:
1002
result = search.get_result()
1003
self.assertEqual((set(['head']), set(['head']), 0),
1004
result.get_recipe())
1005
self.assertEqual(set(), result.get_keys())
1006
self.assertEqual(set(), search.seen)
1009
(set(['head']), (set(['head']), set(['child']), 1),
1010
['head'], None, None),
1011
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
1012
['head', 'child'], None, None),
1013
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
1014
['head', 'child', NULL_REVISION], None, None),
1016
self.assertSeenAndResult(expected, search, search.next)
1017
# using next_with_ghosts:
1018
search = graph._make_breadth_first_searcher(['head'])
1019
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1021
def test_breadth_first_get_result_starts_stops(self):
1022
graph = self.make_graph({
1024
'child':[NULL_REVISION],
1025
'otherhead':['otherchild'],
1026
'otherchild':['excluded'],
1027
'excluded':[NULL_REVISION],
1030
search = graph._make_breadth_first_searcher([])
1031
# Starting with nothing and adding a search works:
1032
search.start_searching(['head'])
1033
# head has been seen:
1034
result = search.get_result()
1035
self.assertEqual((set(['head']), set(['child']), 1),
1036
result.get_recipe())
1037
self.assertEqual(set(['head']), result.get_keys())
1038
self.assertEqual(set(['head']), search.seen)
1041
# stop at child, and start a new search at otherhead:
1042
# - otherhead counts as seen immediately when start_searching is
1044
(set(['head', 'child', 'otherhead']),
1045
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1046
['head', 'otherhead'], ['otherhead'], ['child']),
1047
(set(['head', 'child', 'otherhead', 'otherchild']),
1048
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1049
['head', 'otherhead', 'otherchild'], None, None),
1050
# stop searching excluded now
1051
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1052
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1053
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1055
self.assertSeenAndResult(expected, search, search.next)
1056
# using next_with_ghosts:
1057
search = graph._make_breadth_first_searcher([])
1058
search.start_searching(['head'])
1059
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1061
def test_breadth_first_stop_searching_not_queried(self):
1062
# A client should be able to say 'stop node X' even if X has not been
1063
# returned to the client.
1064
graph = self.make_graph({
1065
'head':['child', 'ghost1'],
1066
'child':[NULL_REVISION],
1069
search = graph._make_breadth_first_searcher(['head'])
1071
# NULL_REVISION and ghost1 have not been returned
1072
(set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
1073
['head'], None, [NULL_REVISION, 'ghost1']),
1074
# ghost1 has been returned, NULL_REVISION is to be returned in the
1076
(set(['head', 'child', 'ghost1']),
1077
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1078
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1080
self.assertSeenAndResult(expected, search, search.next)
1081
# using next_with_ghosts:
1082
search = graph._make_breadth_first_searcher(['head'])
1083
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1085
def test_breadth_first_stop_searching_late(self):
1086
# A client should be able to say 'stop node X' and have it excluded
1087
# from the result even if X was seen in an older iteration of the
1089
graph = self.make_graph({
1092
'child':[NULL_REVISION],
1095
search = graph._make_breadth_first_searcher(['head'])
1097
(set(['head']), (set(['head']), set(['middle']), 1),
1098
['head'], None, None),
1099
(set(['head', 'middle']), (set(['head']), set(['child']), 2),
1100
['head', 'middle'], None, None),
1101
# 'middle' came from the previous iteration, but we don't stop
1102
# searching it until *after* advancing the searcher.
1103
(set(['head', 'middle', 'child']),
1104
(set(['head']), set(['middle', 'child']), 1),
1105
['head'], None, ['middle', 'child']),
1107
self.assertSeenAndResult(expected, search, search.next)
1108
# using next_with_ghosts:
1109
search = graph._make_breadth_first_searcher(['head'])
1110
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1112
def test_breadth_first_get_result_ghosts_are_excluded(self):
1113
graph = self.make_graph({
1114
'head':['child', 'ghost'],
1115
'child':[NULL_REVISION],
1118
search = graph._make_breadth_first_searcher(['head'])
1122
(set(['head']), set(['ghost', 'child']), 1),
1123
['head'], None, None),
1124
(set(['head', 'child', 'ghost']),
1125
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1126
['head', 'child'], None, None),
1128
self.assertSeenAndResult(expected, search, search.next)
1129
# using next_with_ghosts:
1130
search = graph._make_breadth_first_searcher(['head'])
1131
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1133
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1134
graph = self.make_graph({
1136
'child':[NULL_REVISION],
1139
search = graph._make_breadth_first_searcher(['head'])
1142
(set(['head', 'ghost']),
1143
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1144
['head'], ['ghost'], None),
1145
(set(['head', 'child', 'ghost']),
1146
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1147
['head', 'child'], None, None),
1149
self.assertSeenAndResult(expected, search, search.next)
1150
# using next_with_ghosts:
1151
search = graph._make_breadth_first_searcher(['head'])
1152
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1154
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1155
graph = self.make_graph({
1156
'head':[NULL_REVISION],
1159
search = graph._make_breadth_first_searcher(['head'])
1163
(set(['head']), set([NULL_REVISION]), 1),
1164
['head'], None, None),
1165
(set(['head', NULL_REVISION]),
1166
(set(['head']), set([]), 2),
1167
['head', NULL_REVISION], None, None),
1169
self.assertSeenAndResult(expected, search, search.next)
1170
# using next_with_ghosts:
1171
search = graph._make_breadth_first_searcher(['head'])
1172
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1174
def test_breadth_first_search_get_result_after_StopIteration(self):
1175
# StopIteration should not invalid anything..
1176
graph = self.make_graph({
1177
'head':[NULL_REVISION],
1180
search = graph._make_breadth_first_searcher(['head'])
1184
(set(['head']), set([NULL_REVISION]), 1),
1185
['head'], None, None),
1186
(set(['head', 'ghost', NULL_REVISION]),
1187
(set(['head', 'ghost']), set(['ghost']), 2),
1188
['head', NULL_REVISION], ['ghost'], None),
1190
self.assertSeenAndResult(expected, search, search.next)
1191
self.assertRaises(StopIteration, search.next)
1192
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1193
result = search.get_result()
1194
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1195
result.get_recipe())
1196
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1197
# using next_with_ghosts:
1198
search = graph._make_breadth_first_searcher(['head'])
1199
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1200
self.assertRaises(StopIteration, search.next)
1201
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1202
result = search.get_result()
1203
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1204
result.get_recipe())
1205
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1208
class TestFindUniqueAncestors(TestGraphBase):
1210
def assertFindUniqueAncestors(self, graph, expected, node, common):
1211
actual = graph.find_unique_ancestors(node, common)
1212
self.assertEqual(expected, sorted(actual))
1214
def test_empty_set(self):
1215
graph = self.make_graph(ancestry_1)
1216
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1217
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1218
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1220
def test_single_node(self):
1221
graph = self.make_graph(ancestry_1)
1222
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1223
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1224
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1226
def test_minimal_ancestry(self):
1227
graph = self.make_breaking_graph(extended_history_shortcut,
1228
[NULL_REVISION, 'a', 'b'])
1229
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1231
graph = self.make_breaking_graph(extended_history_shortcut,
1233
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1235
graph = self.make_breaking_graph(complex_shortcut,
1237
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1238
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1239
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1240
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1242
def test_in_ancestry(self):
1243
graph = self.make_graph(ancestry_1)
1244
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1245
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1247
def test_multiple_revisions(self):
1248
graph = self.make_graph(ancestry_1)
1249
self.assertFindUniqueAncestors(graph,
1250
['rev4'], 'rev4', ['rev3', 'rev2b'])
1251
self.assertFindUniqueAncestors(graph,
1252
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1254
def test_complex_shortcut(self):
1255
graph = self.make_graph(complex_shortcut)
1256
self.assertFindUniqueAncestors(graph,
1257
['h', 'n'], 'n', ['m'])
1258
self.assertFindUniqueAncestors(graph,
1259
['e', 'i', 'm'], 'm', ['n'])
1261
def test_complex_shortcut2(self):
1262
graph = self.make_graph(complex_shortcut2)
1263
self.assertFindUniqueAncestors(graph,
1264
['j', 'u'], 'u', ['t'])
1265
self.assertFindUniqueAncestors(graph,
1268
def test_multiple_interesting_unique(self):
1269
graph = self.make_graph(multiple_interesting_unique)
1270
self.assertFindUniqueAncestors(graph,
1271
['j', 'y'], 'y', ['z'])
1272
self.assertFindUniqueAncestors(graph,
1273
['p', 'z'], 'z', ['y'])
1275
def test_racing_shortcuts(self):
1276
graph = self.make_graph(racing_shortcuts)
1277
self.assertFindUniqueAncestors(graph,
1278
['p', 'q', 'z'], 'z', ['y'])
1279
self.assertFindUniqueAncestors(graph,
1280
['h', 'i', 'j', 'y'], 'j', ['z'])
1283
class TestGraphFindDistanceToNull(TestGraphBase):
1284
"""Test an api that should be able to compute a revno"""
1286
def assertFindDistance(self, revno, graph, target_id, known_ids):
1287
"""Assert the output of Graph.find_distance_to_null()"""
1288
actual = graph.find_distance_to_null(target_id, known_ids)
1289
self.assertEqual(revno, actual)
1291
def test_nothing_known(self):
1292
graph = self.make_graph(ancestry_1)
1293
self.assertFindDistance(0, graph, NULL_REVISION, [])
1294
self.assertFindDistance(1, graph, 'rev1', [])
1295
self.assertFindDistance(2, graph, 'rev2a', [])
1296
self.assertFindDistance(2, graph, 'rev2b', [])
1297
self.assertFindDistance(3, graph, 'rev3', [])
1298
self.assertFindDistance(4, graph, 'rev4', [])
1300
def test_rev_is_ghost(self):
1301
graph = self.make_graph(ancestry_1)
1302
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1303
graph.find_distance_to_null, 'rev_missing', [])
1304
self.assertEqual('rev_missing', e.revision_id)
1305
self.assertEqual('rev_missing', e.ghost_revision_id)
1307
def test_ancestor_is_ghost(self):
1308
graph = self.make_graph({'rev':['parent']})
1309
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1310
graph.find_distance_to_null, 'rev', [])
1311
self.assertEqual('rev', e.revision_id)
1312
self.assertEqual('parent', e.ghost_revision_id)
1314
def test_known_in_ancestry(self):
1315
graph = self.make_graph(ancestry_1)
1316
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1317
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1319
def test_known_in_ancestry_limits(self):
1320
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1321
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1323
def test_target_is_ancestor(self):
1324
graph = self.make_graph(ancestry_1)
1325
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1327
def test_target_is_ancestor_limits(self):
1328
"""We shouldn't search all history if we run into ourselves"""
1329
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1330
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1332
def test_target_parallel_to_known_limits(self):
1333
# Even though the known revision isn't part of the other ancestry, they
1334
# eventually converge
1335
graph = self.make_breaking_graph(with_tail, ['a'])
1336
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1337
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1338
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1339
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1342
class TestFindMergeOrder(TestGraphBase):
1344
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1345
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1347
def test_parents(self):
1348
graph = self.make_graph(ancestry_1)
1349
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1351
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1354
def test_ancestors(self):
1355
graph = self.make_graph(ancestry_1)
1356
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1358
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1361
def test_shortcut_one_ancestor(self):
1362
# When we have enough info, we can stop searching
1363
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1364
# Single ancestors shortcut right away
1365
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1367
def test_shortcut_after_one_ancestor(self):
1368
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1369
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1372
class TestCachingParentsProvider(tests.TestCase):
1375
super(TestCachingParentsProvider, self).setUp()
1376
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1377
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1378
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1380
def test_get_parent_map(self):
1381
"""Requesting the same revision should be returned from cache"""
1382
self.assertEqual({}, self.caching_pp._cache)
1383
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1384
self.assertEqual(['a'], self.inst_pp.calls)
1385
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1386
# No new call, as it should have been returned from the cache
1387
self.assertEqual(['a'], self.inst_pp.calls)
1388
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1390
def test_get_parent_map_not_present(self):
1391
"""The cache should also track when a revision doesn't exist"""
1392
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1393
self.assertEqual(['b'], self.inst_pp.calls)
1394
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1396
self.assertEqual(['b'], self.inst_pp.calls)
1397
self.assertEqual({'b':None}, self.caching_pp._cache)
1399
def test_get_parent_map_mixed(self):
1400
"""Anything that can be returned from cache, should be"""
1401
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1402
self.assertEqual(['b'], self.inst_pp.calls)
1403
self.assertEqual({'a':('b',)},
1404
self.caching_pp.get_parent_map(['a', 'b']))
1405
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1407
def test_get_parent_map_repeated(self):
1408
"""Asking for the same parent 2x will only forward 1 request."""
1409
self.assertEqual({'a':('b',)},
1410
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1411
# Use sorted because we don't care about the order, just that each is
1412
# only present 1 time.
1413
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1416
class TestCollapseLinearRegions(tests.TestCase):
1418
def assertCollapsed(self, collapsed, original):
1419
self.assertEqual(collapsed,
1420
_mod_graph.collapse_linear_regions(original))
1422
def test_collapse_nothing(self):
1423
d = {1:[2, 3], 2:[], 3:[]}
1424
self.assertCollapsed(d, d)
1425
d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1426
self.assertCollapsed(d, d)
1428
def test_collapse_chain(self):
1429
# Any time we have a linear chain, we should be able to collapse
1430
d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1431
self.assertCollapsed({1:[5], 5:[]}, d)
1432
d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1433
self.assertCollapsed({5:[1], 1:[]}, d)
1434
d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1435
self.assertCollapsed({5:[2], 2:[]}, d)
1437
def test_collapse_with_multiple_children(self):
1448
# 4 and 5 cannot be removed because 6 has 2 children
1449
# 2 and 3 cannot be removed because 1 has 2 parents
1450
d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1451
self.assertCollapsed(d, d)
added
removed
bzrlib/tests/test_graph.py
