1
# Copyright (C) 2007-2010 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
23
from bzrlib.revision import NULL_REVISION
24
from bzrlib.tests import TestCaseWithMemoryTransport
25
from bzrlib.symbol_versioning import deprecated_in
39
ancestry_1 = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
40
'rev3': ['rev2a'], 'rev4': ['rev3', 'rev2b']}
54
ancestry_2 = {'rev1a': [NULL_REVISION], 'rev2a': ['rev1a'],
55
'rev1b': [NULL_REVISION], 'rev3a': ['rev2a'], 'rev4a': ['rev3a']}
58
# Criss cross ancestry
69
criss_cross = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
70
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2a']}
84
criss_cross2 = {'rev1a': [NULL_REVISION], 'rev1b': [NULL_REVISION],
85
'rev2a': ['rev1a', 'rev1b'], 'rev2b': ['rev1b', 'rev1a']}
97
mainline = {'rev1': [NULL_REVISION], 'rev2a': ['rev1', 'rev2b'],
110
feature_branch = {'rev1': [NULL_REVISION],
111
'rev2b': ['rev1'], 'rev3b': ['rev2b']}
122
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
123
'rev2b': ['rev1'], 'rev2c': ['rev1'],
124
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
126
# Extended history shortcut
138
extended_history_shortcut = {'a': [NULL_REVISION],
147
# Both sides will see 'A' first, even though it is actually a decendent of a
148
# different common revision.
162
double_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
163
'd':['c'], 'e':['c'], 'f':['a', 'd'],
167
# This has a failure mode in that a shortcut will find some nodes in common,
168
# but the common searcher won't have time to find that one branch is actually
169
# in common. The extra nodes at the beginning are because we want to avoid
170
# walking off the graph. Specifically, node G should be considered common, but
171
# is likely to be seen by M long before the common searcher finds it.
194
complex_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
195
'e':['d'], 'f':['d'], 'g':['f'], 'h':['f'],
196
'i':['e', 'g'], 'j':['g'], 'k':['j'],
197
'l':['k'], 'm':['i', 'l'], 'n':['l', 'h']}
237
complex_shortcut2 = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
238
'e':['d'], 'f':['e'], 'g':['f'], 'h':['d'], 'i':['g'],
239
'j':['h'], 'k':['h', 'i'], 'l':['k'], 'm':['l'], 'n':['m'],
240
'o':['n'], 'p':['o'], 'q':['p'], 'r':['q'], 's':['r'],
241
't':['i', 's'], 'u':['s', 'j'],
244
# Graph where different walkers will race to find the common and uncommon
287
# x is found to be common right away, but is the start of a long series of
289
# o is actually common, but the i-j shortcut makes it look like it is actually
290
# unique to j at first, you have to traverse all of x->o to find it.
291
# q,m gives the walker from j a common point to stop searching, as does p,f.
292
# k-n exists so that the second pass still has nodes that are worth searching,
293
# rather than instantly cancelling the extra walker.
295
racing_shortcuts = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
296
'e':['d'], 'f':['e'], 'g':['f'], 'h':['g'], 'i':['h', 'o'], 'j':['i', 'y'],
297
'k':['d'], 'l':['k'], 'm':['l'], 'n':['m'], 'o':['n', 'g'], 'p':['f'],
298
'q':['p', 'm'], 'r':['o'], 's':['r'], 't':['s'], 'u':['t'], 'v':['u'],
299
'w':['v'], 'x':['w'], 'y':['x'], 'z':['x', 'q']}
302
# A graph with multiple nodes unique to one side.
341
multiple_interesting_unique = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
342
'd':['c'], 'e':['d'], 'f':['d'], 'g':['e'], 'h':['e'], 'i':['f'],
343
'j':['g'], 'k':['g'], 'l':['h'], 'm':['i'], 'n':['k', 'l'],
344
'o':['m'], 'p':['m', 'l'], 'q':['n', 'o'], 'r':['q'], 's':['r'],
345
't':['s'], 'u':['t'], 'v':['u'], 'w':['v'], 'x':['w'],
346
'y':['j', 'x'], 'z':['x', 'p']}
349
# Shortcut with extra root
350
# We have a long history shortcut, and an extra root, which is why we can't
351
# stop searchers based on seeing NULL_REVISION
363
shortcut_extra_root = {'a': [NULL_REVISION],
368
'f': ['a', 'd', 'g'],
369
'g': [NULL_REVISION],
382
boundary = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e'], 'e': ['f'],
386
# A graph that contains a ghost
397
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
398
'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
400
# A graph that shows we can shortcut finding revnos when reaching them from the
420
with_tail = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'], 'e':['d'],
421
'f':['e'], 'g':['e'], 'h':['f'], 'i':['h']}
424
class InstrumentedParentsProvider(object):
426
def __init__(self, parents_provider):
428
self._real_parents_provider = parents_provider
430
def get_parent_map(self, nodes):
431
self.calls.extend(nodes)
432
return self._real_parents_provider.get_parent_map(nodes)
435
class TestGraphBase(tests.TestCase):
437
def make_graph(self, ancestors):
438
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
440
def make_breaking_graph(self, ancestors, break_on):
441
"""Make a Graph that raises an exception if we hit a node."""
442
g = self.make_graph(ancestors)
443
orig_parent_map = g.get_parent_map
444
def get_parent_map(keys):
445
bad_keys = set(keys).intersection(break_on)
447
self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
448
return orig_parent_map(keys)
449
g.get_parent_map = get_parent_map
453
class TestGraph(TestCaseWithMemoryTransport):
455
def make_graph(self, ancestors):
456
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
458
def prepare_memory_tree(self, location):
459
tree = self.make_branch_and_memory_tree(location)
464
def build_ancestry(self, tree, ancestors):
465
"""Create an ancestry as specified by a graph dict
467
:param tree: A tree to use
468
:param ancestors: a dict of {node: [node_parent, ...]}
470
pending = [NULL_REVISION]
472
for descendant, parents in ancestors.iteritems():
473
for parent in parents:
474
descendants.setdefault(parent, []).append(descendant)
475
while len(pending) > 0:
476
cur_node = pending.pop()
477
for descendant in descendants.get(cur_node, []):
478
if tree.branch.repository.has_revision(descendant):
480
parents = [p for p in ancestors[descendant] if p is not
482
if len([p for p in parents if not
483
tree.branch.repository.has_revision(p)]) > 0:
485
tree.set_parent_ids(parents)
487
left_parent = parents[0]
489
left_parent = NULL_REVISION
490
tree.branch.set_last_revision_info(
491
len(tree.branch._lefthand_history(left_parent)),
493
tree.commit(descendant, rev_id=descendant)
494
pending.append(descendant)
497
"""Test finding least common ancestor.
499
ancestry_1 should always have a single common ancestor
501
graph = self.make_graph(ancestry_1)
502
self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
503
self.assertEqual(set([NULL_REVISION]),
504
graph.find_lca(NULL_REVISION, NULL_REVISION))
505
self.assertEqual(set([NULL_REVISION]),
506
graph.find_lca(NULL_REVISION, 'rev1'))
507
self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
508
self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
510
def test_no_unique_lca(self):
511
"""Test error when one revision is not in the graph"""
512
graph = self.make_graph(ancestry_1)
513
self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
516
def test_lca_criss_cross(self):
517
"""Test least-common-ancestor after a criss-cross merge."""
518
graph = self.make_graph(criss_cross)
519
self.assertEqual(set(['rev2a', 'rev2b']),
520
graph.find_lca('rev3a', 'rev3b'))
521
self.assertEqual(set(['rev2b']),
522
graph.find_lca('rev3a', 'rev3b', 'rev2b'))
524
def test_lca_shortcut(self):
525
"""Test least-common ancestor on this history shortcut"""
526
graph = self.make_graph(history_shortcut)
527
self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
529
def test_lefthand_distance_smoke(self):
530
"""A simple does it work test for graph.lefthand_distance(keys)."""
531
graph = self.make_graph(history_shortcut)
532
distance_graph = graph.find_lefthand_distances(['rev3b', 'rev2a'])
533
self.assertEqual({'rev2a': 2, 'rev3b': 3}, distance_graph)
535
def test_lefthand_distance_ghosts(self):
536
"""A simple does it work test for graph.lefthand_distance(keys)."""
537
nodes = {'nonghost':[NULL_REVISION], 'toghost':['ghost']}
538
graph = self.make_graph(nodes)
539
distance_graph = graph.find_lefthand_distances(['nonghost', 'toghost'])
540
self.assertEqual({'nonghost': 1, 'toghost': -1}, distance_graph)
542
def test_recursive_unique_lca(self):
543
"""Test finding a unique least common ancestor.
545
ancestry_1 should always have a single common ancestor
547
graph = self.make_graph(ancestry_1)
548
self.assertEqual(NULL_REVISION,
549
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
550
self.assertEqual(NULL_REVISION,
551
graph.find_unique_lca(NULL_REVISION, 'rev1'))
552
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
553
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
554
self.assertEqual(('rev1', 1,),
555
graph.find_unique_lca('rev2a', 'rev2b',
558
def assertRemoveDescendants(self, expected, graph, revisions):
559
parents = graph.get_parent_map(revisions)
560
self.assertEqual(expected,
561
graph._remove_simple_descendants(revisions, parents))
563
def test__remove_simple_descendants(self):
564
graph = self.make_graph(ancestry_1)
565
self.assertRemoveDescendants(set(['rev1']), graph,
566
set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']))
568
def test__remove_simple_descendants_disjoint(self):
569
graph = self.make_graph(ancestry_1)
570
self.assertRemoveDescendants(set(['rev1', 'rev3']), graph,
571
set(['rev1', 'rev3']))
573
def test__remove_simple_descendants_chain(self):
574
graph = self.make_graph(ancestry_1)
575
self.assertRemoveDescendants(set(['rev1']), graph,
576
set(['rev1', 'rev2a', 'rev3']))
578
def test__remove_simple_descendants_siblings(self):
579
graph = self.make_graph(ancestry_1)
580
self.assertRemoveDescendants(set(['rev2a', 'rev2b']), graph,
581
set(['rev2a', 'rev2b', 'rev3']))
583
def test_unique_lca_criss_cross(self):
584
"""Ensure we don't pick non-unique lcas in a criss-cross"""
585
graph = self.make_graph(criss_cross)
586
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
587
lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
588
self.assertEqual('rev1', lca)
589
self.assertEqual(2, steps)
591
def test_unique_lca_null_revision(self):
592
"""Ensure we pick NULL_REVISION when necessary"""
593
graph = self.make_graph(criss_cross2)
594
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
595
self.assertEqual(NULL_REVISION,
596
graph.find_unique_lca('rev2a', 'rev2b'))
598
def test_unique_lca_null_revision2(self):
599
"""Ensure we pick NULL_REVISION when necessary"""
600
graph = self.make_graph(ancestry_2)
601
self.assertEqual(NULL_REVISION,
602
graph.find_unique_lca('rev4a', 'rev1b'))
604
def test_lca_double_shortcut(self):
605
graph = self.make_graph(double_shortcut)
606
self.assertEqual('c', graph.find_unique_lca('f', 'g'))
608
def test_common_ancestor_two_repos(self):
609
"""Ensure we do unique_lca using data from two repos"""
610
mainline_tree = self.prepare_memory_tree('mainline')
611
self.build_ancestry(mainline_tree, mainline)
612
self.addCleanup(mainline_tree.unlock)
614
# This is cheating, because the revisions in the graph are actually
615
# different revisions, despite having the same revision-id.
616
feature_tree = self.prepare_memory_tree('feature')
617
self.build_ancestry(feature_tree, feature_branch)
618
self.addCleanup(feature_tree.unlock)
620
graph = mainline_tree.branch.repository.get_graph(
621
feature_tree.branch.repository)
622
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
624
def test_graph_difference(self):
625
graph = self.make_graph(ancestry_1)
626
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
627
self.assertEqual((set(), set(['rev1'])),
628
graph.find_difference(NULL_REVISION, 'rev1'))
629
self.assertEqual((set(['rev1']), set()),
630
graph.find_difference('rev1', NULL_REVISION))
631
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
632
graph.find_difference('rev3', 'rev2b'))
633
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
634
graph.find_difference('rev4', 'rev2b'))
636
def test_graph_difference_separate_ancestry(self):
637
graph = self.make_graph(ancestry_2)
638
self.assertEqual((set(['rev1a']), set(['rev1b'])),
639
graph.find_difference('rev1a', 'rev1b'))
640
self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
642
graph.find_difference('rev4a', 'rev1b'))
644
def test_graph_difference_criss_cross(self):
645
graph = self.make_graph(criss_cross)
646
self.assertEqual((set(['rev3a']), set(['rev3b'])),
647
graph.find_difference('rev3a', 'rev3b'))
648
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
649
graph.find_difference('rev2a', 'rev3b'))
651
def test_graph_difference_extended_history(self):
652
graph = self.make_graph(extended_history_shortcut)
653
self.assertEqual((set(['e']), set(['f'])),
654
graph.find_difference('e', 'f'))
655
self.assertEqual((set(['f']), set(['e'])),
656
graph.find_difference('f', 'e'))
658
def test_graph_difference_double_shortcut(self):
659
graph = self.make_graph(double_shortcut)
660
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
661
graph.find_difference('f', 'g'))
663
def test_graph_difference_complex_shortcut(self):
664
graph = self.make_graph(complex_shortcut)
665
self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
666
graph.find_difference('m', 'n'))
668
def test_graph_difference_complex_shortcut2(self):
669
graph = self.make_graph(complex_shortcut2)
670
self.assertEqual((set(['t']), set(['j', 'u'])),
671
graph.find_difference('t', 'u'))
673
def test_graph_difference_shortcut_extra_root(self):
674
graph = self.make_graph(shortcut_extra_root)
675
self.assertEqual((set(['e']), set(['f', 'g'])),
676
graph.find_difference('e', 'f'))
679
def test_stacked_parents_provider(self):
680
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
681
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
682
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
683
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
684
stacked.get_parent_map(['rev1', 'rev2']))
685
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
686
stacked.get_parent_map(['rev2', 'rev1']))
687
self.assertEqual({'rev2':['rev3']},
688
stacked.get_parent_map(['rev2', 'rev2']))
689
self.assertEqual({'rev1':['rev4']},
690
stacked.get_parent_map(['rev1', 'rev1']))
692
def test_stacked_parents_provider_overlapping(self):
693
# rev2 is availible in both providers.
697
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
698
parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
699
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
700
self.assertEqual({'rev2': ['rev1']},
701
stacked.get_parent_map(['rev2']))
703
def test__stacked_parents_provider_deprecated(self):
704
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
705
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
706
stacked = self.applyDeprecated(deprecated_in((1, 16, 0)),
707
_mod_graph._StackedParentsProvider, [parents1, parents2])
708
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
709
stacked.get_parent_map(['rev1', 'rev2']))
710
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
711
stacked.get_parent_map(['rev2', 'rev1']))
712
self.assertEqual({'rev2':['rev3']},
713
stacked.get_parent_map(['rev2', 'rev2']))
714
self.assertEqual({'rev1':['rev4']},
715
stacked.get_parent_map(['rev1', 'rev1']))
717
def test_iter_topo_order(self):
718
graph = self.make_graph(ancestry_1)
719
args = ['rev2a', 'rev3', 'rev1']
720
topo_args = list(graph.iter_topo_order(args))
721
self.assertEqual(set(args), set(topo_args))
722
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
723
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
725
def test_is_ancestor(self):
726
graph = self.make_graph(ancestry_1)
727
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
728
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
729
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
730
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
731
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
732
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
733
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
734
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
735
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
736
instrumented_provider = InstrumentedParentsProvider(graph)
737
instrumented_graph = _mod_graph.Graph(instrumented_provider)
738
instrumented_graph.is_ancestor('rev2a', 'rev2b')
739
self.assertTrue('null:' not in instrumented_provider.calls)
741
def test_is_between(self):
742
graph = self.make_graph(ancestry_1)
743
self.assertEqual(True, graph.is_between('null:', 'null:', 'null:'))
744
self.assertEqual(True, graph.is_between('rev1', 'null:', 'rev1'))
745
self.assertEqual(True, graph.is_between('rev1', 'rev1', 'rev4'))
746
self.assertEqual(True, graph.is_between('rev4', 'rev1', 'rev4'))
747
self.assertEqual(True, graph.is_between('rev3', 'rev1', 'rev4'))
748
self.assertEqual(False, graph.is_between('rev4', 'rev1', 'rev3'))
749
self.assertEqual(False, graph.is_between('rev1', 'rev2a', 'rev4'))
750
self.assertEqual(False, graph.is_between('null:', 'rev1', 'rev4'))
752
def test_is_ancestor_boundary(self):
753
"""Ensure that we avoid searching the whole graph.
755
This requires searching through b as a common ancestor, so we
756
can identify that e is common.
758
graph = self.make_graph(boundary)
759
instrumented_provider = InstrumentedParentsProvider(graph)
760
graph = _mod_graph.Graph(instrumented_provider)
761
self.assertFalse(graph.is_ancestor('a', 'c'))
762
self.assertTrue('null:' not in instrumented_provider.calls)
764
def test_iter_ancestry(self):
765
nodes = boundary.copy()
766
nodes[NULL_REVISION] = ()
767
graph = self.make_graph(nodes)
768
expected = nodes.copy()
769
expected.pop('a') # 'a' is not in the ancestry of 'c', all the
771
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
772
self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
774
def test_iter_ancestry_with_ghost(self):
775
graph = self.make_graph(with_ghost)
776
expected = with_ghost.copy()
777
# 'a' is not in the ancestry of 'c', and 'g' is a ghost
779
self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
781
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
783
def test_filter_candidate_lca(self):
784
"""Test filter_candidate_lca for a corner case
786
This tests the case where we encounter the end of iteration for 'e'
787
in the same pass as we discover that 'd' is an ancestor of 'e', and
788
therefore 'e' can't be an lca.
790
To compensate for different dict orderings on other Python
791
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
793
# This test is sensitive to the iteration order of dicts. It will
794
# pass incorrectly if 'e' and 'a' sort before 'c'
803
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
804
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
805
self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
807
def test_heads_null(self):
808
graph = self.make_graph(ancestry_1)
809
self.assertEqual(set(['null:']), graph.heads(['null:']))
810
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
811
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
812
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
813
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
815
def test_heads_one(self):
816
# A single node will always be a head
817
graph = self.make_graph(ancestry_1)
818
self.assertEqual(set(['null:']), graph.heads(['null:']))
819
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
820
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
821
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
822
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
823
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
825
def test_heads_single(self):
826
graph = self.make_graph(ancestry_1)
827
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
828
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
829
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
830
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
831
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
832
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
833
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
834
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
836
def test_heads_two_heads(self):
837
graph = self.make_graph(ancestry_1)
838
self.assertEqual(set(['rev2a', 'rev2b']),
839
graph.heads(['rev2a', 'rev2b']))
840
self.assertEqual(set(['rev3', 'rev2b']),
841
graph.heads(['rev3', 'rev2b']))
843
def test_heads_criss_cross(self):
844
graph = self.make_graph(criss_cross)
845
self.assertEqual(set(['rev2a']),
846
graph.heads(['rev2a', 'rev1']))
847
self.assertEqual(set(['rev2b']),
848
graph.heads(['rev2b', 'rev1']))
849
self.assertEqual(set(['rev3a']),
850
graph.heads(['rev3a', 'rev1']))
851
self.assertEqual(set(['rev3b']),
852
graph.heads(['rev3b', 'rev1']))
853
self.assertEqual(set(['rev2a', 'rev2b']),
854
graph.heads(['rev2a', 'rev2b']))
855
self.assertEqual(set(['rev3a']),
856
graph.heads(['rev3a', 'rev2a']))
857
self.assertEqual(set(['rev3a']),
858
graph.heads(['rev3a', 'rev2b']))
859
self.assertEqual(set(['rev3a']),
860
graph.heads(['rev3a', 'rev2a', 'rev2b']))
861
self.assertEqual(set(['rev3b']),
862
graph.heads(['rev3b', 'rev2a']))
863
self.assertEqual(set(['rev3b']),
864
graph.heads(['rev3b', 'rev2b']))
865
self.assertEqual(set(['rev3b']),
866
graph.heads(['rev3b', 'rev2a', 'rev2b']))
867
self.assertEqual(set(['rev3a', 'rev3b']),
868
graph.heads(['rev3a', 'rev3b']))
869
self.assertEqual(set(['rev3a', 'rev3b']),
870
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
872
def test_heads_shortcut(self):
873
graph = self.make_graph(history_shortcut)
875
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
876
graph.heads(['rev2a', 'rev2b', 'rev2c']))
877
self.assertEqual(set(['rev3a', 'rev3b']),
878
graph.heads(['rev3a', 'rev3b']))
879
self.assertEqual(set(['rev3a', 'rev3b']),
880
graph.heads(['rev2a', 'rev3a', 'rev3b']))
881
self.assertEqual(set(['rev2a', 'rev3b']),
882
graph.heads(['rev2a', 'rev3b']))
883
self.assertEqual(set(['rev2c', 'rev3a']),
884
graph.heads(['rev2c', 'rev3a']))
886
def _run_heads_break_deeper(self, graph_dict, search):
887
"""Run heads on a graph-as-a-dict.
889
If the search asks for the parents of 'deeper' the test will fail.
893
def get_parent_map(keys):
897
self.fail('key deeper was accessed')
898
result[key] = graph_dict[key]
901
an_obj.get_parent_map = get_parent_map
902
graph = _mod_graph.Graph(an_obj)
903
return graph.heads(search)
905
def test_heads_limits_search(self):
906
# test that a heads query does not search all of history
912
self.assertEqual(set(['left', 'right']),
913
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
915
def test_heads_limits_search_assymetric(self):
916
# test that a heads query does not search all of history
919
'midleft':['common'],
921
'common':['aftercommon'],
922
'aftercommon':['deeper'],
924
self.assertEqual(set(['left', 'right']),
925
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
927
def test_heads_limits_search_common_search_must_continue(self):
928
# test that common nodes are still queried, preventing
929
# all-the-way-to-origin behaviour in the following graph:
931
'h1':['shortcut', 'common1'],
933
'shortcut':['common2'],
934
'common1':['common2'],
935
'common2':['deeper'],
937
self.assertEqual(set(['h1', 'h2']),
938
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
940
def test_breadth_first_search_start_ghosts(self):
941
graph = self.make_graph({})
942
# with_ghosts reports the ghosts
943
search = graph._make_breadth_first_searcher(['a-ghost'])
944
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
945
self.assertRaises(StopIteration, search.next_with_ghosts)
947
search = graph._make_breadth_first_searcher(['a-ghost'])
948
self.assertEqual(set(['a-ghost']), search.next())
949
self.assertRaises(StopIteration, search.next)
951
def test_breadth_first_search_deep_ghosts(self):
952
graph = self.make_graph({
954
'present':['child', 'ghost'],
957
# with_ghosts reports the ghosts
958
search = graph._make_breadth_first_searcher(['head'])
959
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
960
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
961
self.assertEqual((set(['child']), set(['ghost'])),
962
search.next_with_ghosts())
963
self.assertRaises(StopIteration, search.next_with_ghosts)
965
search = graph._make_breadth_first_searcher(['head'])
966
self.assertEqual(set(['head']), search.next())
967
self.assertEqual(set(['present']), search.next())
968
self.assertEqual(set(['child', 'ghost']),
970
self.assertRaises(StopIteration, search.next)
972
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
973
# To make the API robust, we allow calling both next() and
974
# next_with_ghosts() on the same searcher.
975
graph = self.make_graph({
977
'present':['child', 'ghost'],
980
# start with next_with_ghosts
981
search = graph._make_breadth_first_searcher(['head'])
982
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
983
self.assertEqual(set(['present']), search.next())
984
self.assertEqual((set(['child']), set(['ghost'])),
985
search.next_with_ghosts())
986
self.assertRaises(StopIteration, search.next)
988
search = graph._make_breadth_first_searcher(['head'])
989
self.assertEqual(set(['head']), search.next())
990
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
991
self.assertEqual(set(['child', 'ghost']),
993
self.assertRaises(StopIteration, search.next_with_ghosts)
995
def test_breadth_first_change_search(self):
996
# Changing the search should work with both next and next_with_ghosts.
997
graph = self.make_graph({
999
'present':['stopped'],
1000
'other':['other_2'],
1003
search = graph._make_breadth_first_searcher(['head'])
1004
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
1005
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
1006
self.assertEqual(set(['present']),
1007
search.stop_searching_any(['present']))
1008
self.assertEqual((set(['other']), set(['other_ghost'])),
1009
search.start_searching(['other', 'other_ghost']))
1010
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
1011
self.assertRaises(StopIteration, search.next_with_ghosts)
1012
# next includes them
1013
search = graph._make_breadth_first_searcher(['head'])
1014
self.assertEqual(set(['head']), search.next())
1015
self.assertEqual(set(['present']), search.next())
1016
self.assertEqual(set(['present']),
1017
search.stop_searching_any(['present']))
1018
search.start_searching(['other', 'other_ghost'])
1019
self.assertEqual(set(['other_2']), search.next())
1020
self.assertRaises(StopIteration, search.next)
1022
def assertSeenAndResult(self, instructions, search, next):
1023
"""Check the results of .seen and get_result() for a seach.
1025
:param instructions: A list of tuples:
1026
(seen, recipe, included_keys, starts, stops).
1027
seen, recipe and included_keys are results to check on the search
1028
and the searches get_result(). starts and stops are parameters to
1029
pass to start_searching and stop_searching_any during each
1030
iteration, if they are not None.
1031
:param search: The search to use.
1032
:param next: A callable to advance the search.
1034
for seen, recipe, included_keys, starts, stops in instructions:
1035
# Adjust for recipe contract changes that don't vary for all the
1037
recipe = ('search',) + recipe
1039
if starts is not None:
1040
search.start_searching(starts)
1041
if stops is not None:
1042
search.stop_searching_any(stops)
1043
result = search.get_result()
1044
self.assertEqual(recipe, result.get_recipe())
1045
self.assertEqual(set(included_keys), result.get_keys())
1046
self.assertEqual(seen, search.seen)
1048
def test_breadth_first_get_result_excludes_current_pending(self):
1049
graph = self.make_graph({
1051
'child':[NULL_REVISION],
1054
search = graph._make_breadth_first_searcher(['head'])
1055
# At the start, nothing has been seen, to its all excluded:
1056
result = search.get_result()
1057
self.assertEqual(('search', set(['head']), set(['head']), 0),
1058
result.get_recipe())
1059
self.assertEqual(set(), result.get_keys())
1060
self.assertEqual(set(), search.seen)
1063
(set(['head']), (set(['head']), set(['child']), 1),
1064
['head'], None, None),
1065
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
1066
['head', 'child'], None, None),
1067
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
1068
['head', 'child', NULL_REVISION], None, None),
1070
self.assertSeenAndResult(expected, search, search.next)
1071
# using next_with_ghosts:
1072
search = graph._make_breadth_first_searcher(['head'])
1073
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1075
def test_breadth_first_get_result_starts_stops(self):
1076
graph = self.make_graph({
1078
'child':[NULL_REVISION],
1079
'otherhead':['otherchild'],
1080
'otherchild':['excluded'],
1081
'excluded':[NULL_REVISION],
1084
search = graph._make_breadth_first_searcher([])
1085
# Starting with nothing and adding a search works:
1086
search.start_searching(['head'])
1087
# head has been seen:
1088
result = search.get_result()
1089
self.assertEqual(('search', set(['head']), set(['child']), 1),
1090
result.get_recipe())
1091
self.assertEqual(set(['head']), result.get_keys())
1092
self.assertEqual(set(['head']), search.seen)
1095
# stop at child, and start a new search at otherhead:
1096
# - otherhead counts as seen immediately when start_searching is
1098
(set(['head', 'child', 'otherhead']),
1099
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1100
['head', 'otherhead'], ['otherhead'], ['child']),
1101
(set(['head', 'child', 'otherhead', 'otherchild']),
1102
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1103
['head', 'otherhead', 'otherchild'], None, None),
1104
# stop searching excluded now
1105
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1106
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1107
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1109
self.assertSeenAndResult(expected, search, search.next)
1110
# using next_with_ghosts:
1111
search = graph._make_breadth_first_searcher([])
1112
search.start_searching(['head'])
1113
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1115
def test_breadth_first_stop_searching_not_queried(self):
1116
# A client should be able to say 'stop node X' even if X has not been
1117
# returned to the client.
1118
graph = self.make_graph({
1119
'head':['child', 'ghost1'],
1120
'child':[NULL_REVISION],
1123
search = graph._make_breadth_first_searcher(['head'])
1125
# NULL_REVISION and ghost1 have not been returned
1127
(set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1128
['head'], None, [NULL_REVISION, 'ghost1']),
1129
# ghost1 has been returned, NULL_REVISION is to be returned in the
1131
(set(['head', 'child', 'ghost1']),
1132
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1133
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1135
self.assertSeenAndResult(expected, search, search.next)
1136
# using next_with_ghosts:
1137
search = graph._make_breadth_first_searcher(['head'])
1138
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1140
def test_breadth_first_stop_searching_late(self):
1141
# A client should be able to say 'stop node X' and have it excluded
1142
# from the result even if X was seen in an older iteration of the
1144
graph = self.make_graph({
1147
'child':[NULL_REVISION],
1150
search = graph._make_breadth_first_searcher(['head'])
1152
(set(['head']), (set(['head']), set(['middle']), 1),
1153
['head'], None, None),
1154
(set(['head', 'middle']), (set(['head']), set(['child']), 2),
1155
['head', 'middle'], None, None),
1156
# 'middle' came from the previous iteration, but we don't stop
1157
# searching it until *after* advancing the searcher.
1158
(set(['head', 'middle', 'child']),
1159
(set(['head']), set(['middle', 'child']), 1),
1160
['head'], None, ['middle', 'child']),
1162
self.assertSeenAndResult(expected, search, search.next)
1163
# using next_with_ghosts:
1164
search = graph._make_breadth_first_searcher(['head'])
1165
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1167
def test_breadth_first_get_result_ghosts_are_excluded(self):
1168
graph = self.make_graph({
1169
'head':['child', 'ghost'],
1170
'child':[NULL_REVISION],
1173
search = graph._make_breadth_first_searcher(['head'])
1177
(set(['head']), set(['ghost', 'child']), 1),
1178
['head'], None, None),
1179
(set(['head', 'child', 'ghost']),
1180
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1181
['head', 'child'], None, None),
1183
self.assertSeenAndResult(expected, search, search.next)
1184
# using next_with_ghosts:
1185
search = graph._make_breadth_first_searcher(['head'])
1186
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1188
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1189
graph = self.make_graph({
1191
'child':[NULL_REVISION],
1194
search = graph._make_breadth_first_searcher(['head'])
1197
(set(['head', 'ghost']),
1198
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1199
['head'], ['ghost'], None),
1200
(set(['head', 'child', 'ghost']),
1201
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1202
['head', 'child'], None, None),
1204
self.assertSeenAndResult(expected, search, search.next)
1205
# using next_with_ghosts:
1206
search = graph._make_breadth_first_searcher(['head'])
1207
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1209
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1210
graph = self.make_graph({
1211
'head':[NULL_REVISION],
1214
search = graph._make_breadth_first_searcher(['head'])
1218
(set(['head']), set([NULL_REVISION]), 1),
1219
['head'], None, None),
1220
(set(['head', NULL_REVISION]),
1221
(set(['head']), set([]), 2),
1222
['head', NULL_REVISION], None, None),
1224
self.assertSeenAndResult(expected, search, search.next)
1225
# using next_with_ghosts:
1226
search = graph._make_breadth_first_searcher(['head'])
1227
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1229
def test_breadth_first_search_get_result_after_StopIteration(self):
1230
# StopIteration should not invalid anything..
1231
graph = self.make_graph({
1232
'head':[NULL_REVISION],
1235
search = graph._make_breadth_first_searcher(['head'])
1239
(set(['head']), set([NULL_REVISION]), 1),
1240
['head'], None, None),
1241
(set(['head', 'ghost', NULL_REVISION]),
1242
(set(['head', 'ghost']), set(['ghost']), 2),
1243
['head', NULL_REVISION], ['ghost'], None),
1245
self.assertSeenAndResult(expected, search, search.next)
1246
self.assertRaises(StopIteration, search.next)
1247
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1248
result = search.get_result()
1249
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1250
result.get_recipe())
1251
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1252
# using next_with_ghosts:
1253
search = graph._make_breadth_first_searcher(['head'])
1254
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1255
self.assertRaises(StopIteration, search.next)
1256
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1257
result = search.get_result()
1258
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1259
result.get_recipe())
1260
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1263
class TestFindUniqueAncestors(TestGraphBase):
1265
def assertFindUniqueAncestors(self, graph, expected, node, common):
1266
actual = graph.find_unique_ancestors(node, common)
1267
self.assertEqual(expected, sorted(actual))
1269
def test_empty_set(self):
1270
graph = self.make_graph(ancestry_1)
1271
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1272
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1273
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1275
def test_single_node(self):
1276
graph = self.make_graph(ancestry_1)
1277
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1278
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1279
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1281
def test_minimal_ancestry(self):
1282
graph = self.make_breaking_graph(extended_history_shortcut,
1283
[NULL_REVISION, 'a', 'b'])
1284
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1286
graph = self.make_breaking_graph(extended_history_shortcut,
1288
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1290
graph = self.make_breaking_graph(complex_shortcut,
1292
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1293
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1294
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1295
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1297
def test_in_ancestry(self):
1298
graph = self.make_graph(ancestry_1)
1299
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1300
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1302
def test_multiple_revisions(self):
1303
graph = self.make_graph(ancestry_1)
1304
self.assertFindUniqueAncestors(graph,
1305
['rev4'], 'rev4', ['rev3', 'rev2b'])
1306
self.assertFindUniqueAncestors(graph,
1307
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1309
def test_complex_shortcut(self):
1310
graph = self.make_graph(complex_shortcut)
1311
self.assertFindUniqueAncestors(graph,
1312
['h', 'n'], 'n', ['m'])
1313
self.assertFindUniqueAncestors(graph,
1314
['e', 'i', 'm'], 'm', ['n'])
1316
def test_complex_shortcut2(self):
1317
graph = self.make_graph(complex_shortcut2)
1318
self.assertFindUniqueAncestors(graph,
1319
['j', 'u'], 'u', ['t'])
1320
self.assertFindUniqueAncestors(graph,
1323
def test_multiple_interesting_unique(self):
1324
graph = self.make_graph(multiple_interesting_unique)
1325
self.assertFindUniqueAncestors(graph,
1326
['j', 'y'], 'y', ['z'])
1327
self.assertFindUniqueAncestors(graph,
1328
['p', 'z'], 'z', ['y'])
1330
def test_racing_shortcuts(self):
1331
graph = self.make_graph(racing_shortcuts)
1332
self.assertFindUniqueAncestors(graph,
1333
['p', 'q', 'z'], 'z', ['y'])
1334
self.assertFindUniqueAncestors(graph,
1335
['h', 'i', 'j', 'y'], 'j', ['z'])
1338
class TestGraphFindDistanceToNull(TestGraphBase):
1339
"""Test an api that should be able to compute a revno"""
1341
def assertFindDistance(self, revno, graph, target_id, known_ids):
1342
"""Assert the output of Graph.find_distance_to_null()"""
1343
actual = graph.find_distance_to_null(target_id, known_ids)
1344
self.assertEqual(revno, actual)
1346
def test_nothing_known(self):
1347
graph = self.make_graph(ancestry_1)
1348
self.assertFindDistance(0, graph, NULL_REVISION, [])
1349
self.assertFindDistance(1, graph, 'rev1', [])
1350
self.assertFindDistance(2, graph, 'rev2a', [])
1351
self.assertFindDistance(2, graph, 'rev2b', [])
1352
self.assertFindDistance(3, graph, 'rev3', [])
1353
self.assertFindDistance(4, graph, 'rev4', [])
1355
def test_rev_is_ghost(self):
1356
graph = self.make_graph(ancestry_1)
1357
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1358
graph.find_distance_to_null, 'rev_missing', [])
1359
self.assertEqual('rev_missing', e.revision_id)
1360
self.assertEqual('rev_missing', e.ghost_revision_id)
1362
def test_ancestor_is_ghost(self):
1363
graph = self.make_graph({'rev':['parent']})
1364
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1365
graph.find_distance_to_null, 'rev', [])
1366
self.assertEqual('rev', e.revision_id)
1367
self.assertEqual('parent', e.ghost_revision_id)
1369
def test_known_in_ancestry(self):
1370
graph = self.make_graph(ancestry_1)
1371
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1372
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1374
def test_known_in_ancestry_limits(self):
1375
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1376
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1378
def test_target_is_ancestor(self):
1379
graph = self.make_graph(ancestry_1)
1380
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1382
def test_target_is_ancestor_limits(self):
1383
"""We shouldn't search all history if we run into ourselves"""
1384
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1385
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1387
def test_target_parallel_to_known_limits(self):
1388
# Even though the known revision isn't part of the other ancestry, they
1389
# eventually converge
1390
graph = self.make_breaking_graph(with_tail, ['a'])
1391
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1392
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1393
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1394
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1397
class TestFindMergeOrder(TestGraphBase):
1399
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1400
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1402
def test_parents(self):
1403
graph = self.make_graph(ancestry_1)
1404
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1406
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1409
def test_ancestors(self):
1410
graph = self.make_graph(ancestry_1)
1411
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1413
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1416
def test_shortcut_one_ancestor(self):
1417
# When we have enough info, we can stop searching
1418
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1419
# Single ancestors shortcut right away
1420
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1422
def test_shortcut_after_one_ancestor(self):
1423
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1424
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1427
class TestFindDescendants(TestGraphBase):
1429
def test_find_descendants_rev1_rev3(self):
1430
graph = self.make_graph(ancestry_1)
1431
descendants = graph.find_descendants('rev1', 'rev3')
1432
self.assertEqual(set(['rev1', 'rev2a', 'rev3']), descendants)
1434
def test_find_descendants_rev1_rev4(self):
1435
graph = self.make_graph(ancestry_1)
1436
descendants = graph.find_descendants('rev1', 'rev4')
1437
self.assertEqual(set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']),
1440
def test_find_descendants_rev2a_rev4(self):
1441
graph = self.make_graph(ancestry_1)
1442
descendants = graph.find_descendants('rev2a', 'rev4')
1443
self.assertEqual(set(['rev2a', 'rev3', 'rev4']), descendants)
1445
class TestFindLefthandMerger(TestGraphBase):
1447
def check_merger(self, result, ancestry, merged, tip):
1448
graph = self.make_graph(ancestry)
1449
self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
1451
def test_find_lefthand_merger_rev2b(self):
1452
self.check_merger('rev4', ancestry_1, 'rev2b', 'rev4')
1454
def test_find_lefthand_merger_rev2a(self):
1455
self.check_merger('rev2a', ancestry_1, 'rev2a', 'rev4')
1457
def test_find_lefthand_merger_rev4(self):
1458
self.check_merger(None, ancestry_1, 'rev4', 'rev2a')
1460
def test_find_lefthand_merger_f(self):
1461
self.check_merger('i', complex_shortcut, 'f', 'm')
1463
def test_find_lefthand_merger_g(self):
1464
self.check_merger('i', complex_shortcut, 'g', 'm')
1466
def test_find_lefthand_merger_h(self):
1467
self.check_merger('n', complex_shortcut, 'h', 'n')
1470
class TestGetChildMap(TestGraphBase):
1472
def test_get_child_map(self):
1473
graph = self.make_graph(ancestry_1)
1474
child_map = graph.get_child_map(['rev4', 'rev3', 'rev2a', 'rev2b'])
1475
self.assertEqual({'rev1': ['rev2a', 'rev2b'],
1482
class TestCachingParentsProvider(tests.TestCase):
1483
"""These tests run with:
1485
self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1487
self.caching_pp, a CachingParentsProvider layered on inst_pp.
1491
super(TestCachingParentsProvider, self).setUp()
1492
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1493
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1494
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1496
def test_get_parent_map(self):
1497
"""Requesting the same revision should be returned from cache"""
1498
self.assertEqual({}, self.caching_pp._cache)
1499
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1500
self.assertEqual(['a'], self.inst_pp.calls)
1501
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1502
# No new call, as it should have been returned from the cache
1503
self.assertEqual(['a'], self.inst_pp.calls)
1504
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1506
def test_get_parent_map_not_present(self):
1507
"""The cache should also track when a revision doesn't exist"""
1508
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1509
self.assertEqual(['b'], self.inst_pp.calls)
1510
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1512
self.assertEqual(['b'], self.inst_pp.calls)
1514
def test_get_parent_map_mixed(self):
1515
"""Anything that can be returned from cache, should be"""
1516
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1517
self.assertEqual(['b'], self.inst_pp.calls)
1518
self.assertEqual({'a':('b',)},
1519
self.caching_pp.get_parent_map(['a', 'b']))
1520
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1522
def test_get_parent_map_repeated(self):
1523
"""Asking for the same parent 2x will only forward 1 request."""
1524
self.assertEqual({'a':('b',)},
1525
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1526
# Use sorted because we don't care about the order, just that each is
1527
# only present 1 time.
1528
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1530
def test_note_missing_key(self):
1531
"""After noting that a key is missing it is cached."""
1532
self.caching_pp.note_missing_key('b')
1533
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1534
self.assertEqual([], self.inst_pp.calls)
1535
self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1538
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1539
"""Test the behaviour when parents are provided that were not requested."""
1542
super(TestCachingParentsProviderExtras, self).setUp()
1543
class ExtraParentsProvider(object):
1545
def get_parent_map(self, keys):
1546
return {'rev1': [], 'rev2': ['rev1',]}
1548
self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1549
self.caching_pp = _mod_graph.CachingParentsProvider(
1550
get_parent_map=self.inst_pp.get_parent_map)
1552
def test_uncached(self):
1553
self.caching_pp.disable_cache()
1554
self.assertEqual({'rev1': []},
1555
self.caching_pp.get_parent_map(['rev1']))
1556
self.assertEqual(['rev1'], self.inst_pp.calls)
1557
self.assertIs(None, self.caching_pp._cache)
1559
def test_cache_initially_empty(self):
1560
self.assertEqual({}, self.caching_pp._cache)
1562
def test_cached(self):
1563
self.assertEqual({'rev1': []},
1564
self.caching_pp.get_parent_map(['rev1']))
1565
self.assertEqual(['rev1'], self.inst_pp.calls)
1566
self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1567
self.caching_pp._cache)
1568
self.assertEqual({'rev1': []},
1569
self.caching_pp.get_parent_map(['rev1']))
1570
self.assertEqual(['rev1'], self.inst_pp.calls)
1572
def test_disable_cache_clears_cache(self):
1573
# Put something in the cache
1574
self.caching_pp.get_parent_map(['rev1'])
1575
self.assertEqual(2, len(self.caching_pp._cache))
1576
self.caching_pp.disable_cache()
1577
self.assertIs(None, self.caching_pp._cache)
1579
def test_enable_cache_raises(self):
1580
e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1581
self.assertEqual('Cache enabled when already enabled.', str(e))
1583
def test_cache_misses(self):
1584
self.caching_pp.get_parent_map(['rev3'])
1585
self.caching_pp.get_parent_map(['rev3'])
1586
self.assertEqual(['rev3'], self.inst_pp.calls)
1588
def test_no_cache_misses(self):
1589
self.caching_pp.disable_cache()
1590
self.caching_pp.enable_cache(cache_misses=False)
1591
self.caching_pp.get_parent_map(['rev3'])
1592
self.caching_pp.get_parent_map(['rev3'])
1593
self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1595
def test_cache_extras(self):
1596
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1597
self.assertEqual({'rev2': ['rev1']},
1598
self.caching_pp.get_parent_map(['rev2']))
1599
self.assertEqual(['rev3'], self.inst_pp.calls)
1602
class TestCollapseLinearRegions(tests.TestCase):
1604
def assertCollapsed(self, collapsed, original):
1605
self.assertEqual(collapsed,
1606
_mod_graph.collapse_linear_regions(original))
1608
def test_collapse_nothing(self):
1609
d = {1:[2, 3], 2:[], 3:[]}
1610
self.assertCollapsed(d, d)
1611
d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1612
self.assertCollapsed(d, d)
1614
def test_collapse_chain(self):
1615
# Any time we have a linear chain, we should be able to collapse
1616
d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1617
self.assertCollapsed({1:[5], 5:[]}, d)
1618
d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1619
self.assertCollapsed({5:[1], 1:[]}, d)
1620
d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1621
self.assertCollapsed({5:[2], 2:[]}, d)
1623
def test_collapse_with_multiple_children(self):
1634
# 4 and 5 cannot be removed because 6 has 2 children
1635
# 2 and 3 cannot be removed because 1 has 2 parents
1636
d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1637
self.assertCollapsed(d, d)
1640
class TestGraphThunkIdsToKeys(tests.TestCase):
1642
def test_heads(self):
1648
d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1649
('B',): [('A',)], ('A',): []}
1650
g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1651
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1652
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
1653
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
1654
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1655
self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1658
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1659
"""Tests for bzrlib.graph.PendingAncestryResult."""
1661
def test_get_keys(self):
1662
builder = self.make_branch_builder('b')
1663
builder.start_series()
1664
builder.build_snapshot('rev-1', None, [
1665
('add', ('', 'root-id', 'directory', ''))])
1666
builder.build_snapshot('rev-2', ['rev-1'], [])
1667
builder.finish_series()
1668
repo = builder.get_branch().repository
1670
self.addCleanup(repo.unlock)
1671
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1672
self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1674
def test_get_keys_excludes_ghosts(self):
1675
builder = self.make_branch_builder('b')
1676
builder.start_series()
1677
builder.build_snapshot('rev-1', None, [
1678
('add', ('', 'root-id', 'directory', ''))])
1679
builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
1680
builder.finish_series()
1681
repo = builder.get_branch().repository
1683
self.addCleanup(repo.unlock)
1684
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1685
self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
1687
def test_get_keys_excludes_null(self):
1688
# Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1689
# somewhere other than the last element, which can happen in real
1691
class StubGraph(object):
1692
def iter_ancestry(self, keys):
1693
return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1694
result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1695
result_keys = result._get_keys(StubGraph())
1696
# Only the non-null keys from the ancestry appear.
1697
self.assertEqual(set(['foo']), set(result_keys))
1700
class TestPendingAncestryResultRefine(TestGraphBase):
1702
def test_refine(self):
1703
# Used when pulling from a stacked repository, so test some revisions
1704
# being satisfied from the stacking branch.
1705
g = self.make_graph(
1706
{"tip":["mid"], "mid":["base"], "tag":["base"],
1707
"base":[NULL_REVISION], NULL_REVISION:[]})
1708
result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1709
result = result.refine(set(['tip']), set(['mid']))
1710
self.assertEqual(set(['mid', 'tag']), result.heads)
1711
result = result.refine(set(['mid', 'tag', 'base']),
1712
set([NULL_REVISION]))
1713
self.assertEqual(set([NULL_REVISION]), result.heads)
1714
self.assertTrue(result.is_empty())
1717
class TestSearchResultRefine(TestGraphBase):
1719
def test_refine(self):
1720
# Used when pulling from a stacked repository, so test some revisions
1721
# being satisfied from the stacking branch.
1722
g = self.make_graph(
1723
{"tip":["mid"], "mid":["base"], "tag":["base"],
1724
"base":[NULL_REVISION], NULL_REVISION:[]})
1725
result = _mod_graph.SearchResult(set(['tip', 'tag']),
1726
set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1727
result = result.refine(set(['tip']), set(['mid']))
1728
recipe = result.get_recipe()
1729
# We should be starting from tag (original head) and mid (seen ref)
1730
self.assertEqual(set(['mid', 'tag']), recipe[1])
1731
# We should be stopping at NULL (original stop) and tip (seen head)
1732
self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1733
self.assertEqual(3, recipe[3])
1734
result = result.refine(set(['mid', 'tag', 'base']),
1735
set([NULL_REVISION]))
1736
recipe = result.get_recipe()
1737
# We should be starting from nothing (NULL was known as a cut point)
1738
self.assertEqual(set([]), recipe[1])
1739
# We should be stopping at NULL (original stop) and tip (seen head) and
1740
# tag (seen head) and mid(seen mid-point head). We could come back and
1741
# define this as not including mid, for minimal results, but it is
1742
# still 'correct' to include mid, and simpler/easier.
1743
self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1744
self.assertEqual(0, recipe[3])
1745
self.assertTrue(result.is_empty())
added
removed
bzrlib/tests/test_graph.py
