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_get_result_ghosts_are_excluded(self):
1086
graph = self.make_graph({
1087
'head':['child', 'ghost'],
1088
'child':[NULL_REVISION],
1091
search = graph._make_breadth_first_searcher(['head'])
1095
(set(['head']), set(['ghost', 'child']), 1),
1096
['head'], None, None),
1097
(set(['head', 'child', 'ghost']),
1098
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1099
['head', 'child'], None, None),
1101
self.assertSeenAndResult(expected, search, search.next)
1102
# using next_with_ghosts:
1103
search = graph._make_breadth_first_searcher(['head'])
1104
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1106
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1107
graph = self.make_graph({
1109
'child':[NULL_REVISION],
1112
search = graph._make_breadth_first_searcher(['head'])
1115
(set(['head', 'ghost']),
1116
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1117
['head'], ['ghost'], None),
1118
(set(['head', 'child', 'ghost']),
1119
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1120
['head', 'child'], None, None),
1122
self.assertSeenAndResult(expected, search, search.next)
1123
# using next_with_ghosts:
1124
search = graph._make_breadth_first_searcher(['head'])
1125
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1127
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1128
graph = self.make_graph({
1129
'head':[NULL_REVISION],
1132
search = graph._make_breadth_first_searcher(['head'])
1136
(set(['head']), set([NULL_REVISION]), 1),
1137
['head'], None, None),
1138
(set(['head', NULL_REVISION]),
1139
(set(['head']), set([]), 2),
1140
['head', NULL_REVISION], None, None),
1142
self.assertSeenAndResult(expected, search, search.next)
1143
# using next_with_ghosts:
1144
search = graph._make_breadth_first_searcher(['head'])
1145
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1147
def test_breadth_first_search_get_result_after_StopIteration(self):
1148
# StopIteration should not invalid anything..
1149
graph = self.make_graph({
1150
'head':[NULL_REVISION],
1153
search = graph._make_breadth_first_searcher(['head'])
1157
(set(['head']), set([NULL_REVISION]), 1),
1158
['head'], None, None),
1159
(set(['head', 'ghost', NULL_REVISION]),
1160
(set(['head', 'ghost']), set(['ghost']), 2),
1161
['head', NULL_REVISION], ['ghost'], None),
1163
self.assertSeenAndResult(expected, search, search.next)
1164
self.assertRaises(StopIteration, search.next)
1165
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1166
result = search.get_result()
1167
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1168
result.get_recipe())
1169
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1170
# using next_with_ghosts:
1171
search = graph._make_breadth_first_searcher(['head'])
1172
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1173
self.assertRaises(StopIteration, search.next)
1174
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1175
result = search.get_result()
1176
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1177
result.get_recipe())
1178
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1181
class TestFindUniqueAncestors(TestGraphBase):
1183
def assertFindUniqueAncestors(self, graph, expected, node, common):
1184
actual = graph.find_unique_ancestors(node, common)
1185
self.assertEqual(expected, sorted(actual))
1187
def test_empty_set(self):
1188
graph = self.make_graph(ancestry_1)
1189
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1190
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1191
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1193
def test_single_node(self):
1194
graph = self.make_graph(ancestry_1)
1195
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1196
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1197
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1199
def test_minimal_ancestry(self):
1200
graph = self.make_breaking_graph(extended_history_shortcut,
1201
[NULL_REVISION, 'a', 'b'])
1202
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1204
graph = self.make_breaking_graph(extended_history_shortcut,
1206
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1208
graph = self.make_breaking_graph(complex_shortcut,
1210
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1211
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1212
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1213
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1215
def test_in_ancestry(self):
1216
graph = self.make_graph(ancestry_1)
1217
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1218
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1220
def test_multiple_revisions(self):
1221
graph = self.make_graph(ancestry_1)
1222
self.assertFindUniqueAncestors(graph,
1223
['rev4'], 'rev4', ['rev3', 'rev2b'])
1224
self.assertFindUniqueAncestors(graph,
1225
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1227
def test_complex_shortcut(self):
1228
graph = self.make_graph(complex_shortcut)
1229
self.assertFindUniqueAncestors(graph,
1230
['h', 'n'], 'n', ['m'])
1231
self.assertFindUniqueAncestors(graph,
1232
['e', 'i', 'm'], 'm', ['n'])
1234
def test_complex_shortcut2(self):
1235
graph = self.make_graph(complex_shortcut2)
1236
self.assertFindUniqueAncestors(graph,
1237
['j', 'u'], 'u', ['t'])
1238
self.assertFindUniqueAncestors(graph,
1241
def test_multiple_interesting_unique(self):
1242
graph = self.make_graph(multiple_interesting_unique)
1243
self.assertFindUniqueAncestors(graph,
1244
['j', 'y'], 'y', ['z'])
1245
self.assertFindUniqueAncestors(graph,
1246
['p', 'z'], 'z', ['y'])
1248
def test_racing_shortcuts(self):
1249
graph = self.make_graph(racing_shortcuts)
1250
self.assertFindUniqueAncestors(graph,
1251
['p', 'q', 'z'], 'z', ['y'])
1252
self.assertFindUniqueAncestors(graph,
1253
['h', 'i', 'j', 'y'], 'j', ['z'])
1256
class TestGraphFindDistanceToNull(TestGraphBase):
1257
"""Test an api that should be able to compute a revno"""
1259
def assertFindDistance(self, revno, graph, target_id, known_ids):
1260
"""Assert the output of Graph.find_distance_to_null()"""
1261
actual = graph.find_distance_to_null(target_id, known_ids)
1262
self.assertEqual(revno, actual)
1264
def test_nothing_known(self):
1265
graph = self.make_graph(ancestry_1)
1266
self.assertFindDistance(0, graph, NULL_REVISION, [])
1267
self.assertFindDistance(1, graph, 'rev1', [])
1268
self.assertFindDistance(2, graph, 'rev2a', [])
1269
self.assertFindDistance(2, graph, 'rev2b', [])
1270
self.assertFindDistance(3, graph, 'rev3', [])
1271
self.assertFindDistance(4, graph, 'rev4', [])
1273
def test_rev_is_ghost(self):
1274
graph = self.make_graph(ancestry_1)
1275
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1276
graph.find_distance_to_null, 'rev_missing', [])
1277
self.assertEqual('rev_missing', e.revision_id)
1278
self.assertEqual('rev_missing', e.ghost_revision_id)
1280
def test_ancestor_is_ghost(self):
1281
graph = self.make_graph({'rev':['parent']})
1282
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1283
graph.find_distance_to_null, 'rev', [])
1284
self.assertEqual('rev', e.revision_id)
1285
self.assertEqual('parent', e.ghost_revision_id)
1287
def test_known_in_ancestry(self):
1288
graph = self.make_graph(ancestry_1)
1289
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1290
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1292
def test_known_in_ancestry_limits(self):
1293
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1294
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1296
def test_target_is_ancestor(self):
1297
graph = self.make_graph(ancestry_1)
1298
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1300
def test_target_is_ancestor_limits(self):
1301
"""We shouldn't search all history if we run into ourselves"""
1302
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1303
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1305
def test_target_parallel_to_known_limits(self):
1306
# Even though the known revision isn't part of the other ancestry, they
1307
# eventually converge
1308
graph = self.make_breaking_graph(with_tail, ['a'])
1309
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1310
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1311
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1312
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1315
class TestFindMergeOrder(TestGraphBase):
1317
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1318
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1320
def test_parents(self):
1321
graph = self.make_graph(ancestry_1)
1322
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1324
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1327
def test_ancestors(self):
1328
graph = self.make_graph(ancestry_1)
1329
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1331
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1334
def test_shortcut_one_ancestor(self):
1335
# When we have enough info, we can stop searching
1336
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1337
# Single ancestors shortcut right away
1338
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1340
def test_shortcut_after_one_ancestor(self):
1341
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1342
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1345
class TestCachingParentsProvider(tests.TestCase):
1348
super(TestCachingParentsProvider, self).setUp()
1349
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1350
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1351
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1353
def test_get_parent_map(self):
1354
"""Requesting the same revision should be returned from cache"""
1355
self.assertEqual({}, self.caching_pp._cache)
1356
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1357
self.assertEqual(['a'], self.inst_pp.calls)
1358
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1359
# No new call, as it should have been returned from the cache
1360
self.assertEqual(['a'], self.inst_pp.calls)
1361
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1363
def test_get_parent_map_not_present(self):
1364
"""The cache should also track when a revision doesn't exist"""
1365
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1366
self.assertEqual(['b'], self.inst_pp.calls)
1367
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1369
self.assertEqual(['b'], self.inst_pp.calls)
1370
self.assertEqual({'b':None}, self.caching_pp._cache)
1372
def test_get_parent_map_mixed(self):
1373
"""Anything that can be returned from cache, should be"""
1374
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1375
self.assertEqual(['b'], self.inst_pp.calls)
1376
self.assertEqual({'a':('b',)},
1377
self.caching_pp.get_parent_map(['a', 'b']))
1378
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1380
def test_get_parent_map_repeated(self):
1381
"""Asking for the same parent 2x will only forward 1 request."""
1382
self.assertEqual({'a':('b',)},
1383
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1384
# Use sorted because we don't care about the order, just that each is
1385
# only present 1 time.
1386
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1389
class TestCollapseLinearRegions(tests.TestCase):
1391
def assertCollapsed(self, collapsed, original):
1392
self.assertEqual(collapsed,
1393
_mod_graph.collapse_linear_regions(original))
1395
def test_collapse_nothing(self):
1396
d = {1:[2, 3], 2:[], 3:[]}
1397
self.assertCollapsed(d, d)
1398
d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1399
self.assertCollapsed(d, d)
1401
def test_collapse_chain(self):
1402
# Any time we have a linear chain, we should be able to collapse
1403
d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1404
self.assertCollapsed({1:[5], 5:[]}, d)
1405
d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1406
self.assertCollapsed({5:[1], 1:[]}, d)
1407
d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1408
self.assertCollapsed({5:[2], 2:[]}, d)
1410
def test_collapse_with_multiple_children(self):
1421
# 4 and 5 cannot be removed because 6 has 2 children
1422
# 2 and 3 cannot be removed because 1 has 2 parents
1423
d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1424
self.assertCollapsed(d, d)
added
removed
bzrlib/tests/test_graph.py
