1
# Copyright (C) 2007-2011 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
22
from bzrlib.revision import NULL_REVISION
23
from bzrlib.tests import TestCaseWithMemoryTransport
24
from bzrlib.symbol_versioning import deprecated_in
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_lefthand_distance_smoke(self):
529
"""A simple does it work test for graph.lefthand_distance(keys)."""
530
graph = self.make_graph(history_shortcut)
531
distance_graph = graph.find_lefthand_distances(['rev3b', 'rev2a'])
532
self.assertEqual({'rev2a': 2, 'rev3b': 3}, distance_graph)
534
def test_lefthand_distance_ghosts(self):
535
"""A simple does it work test for graph.lefthand_distance(keys)."""
536
nodes = {'nonghost':[NULL_REVISION], 'toghost':['ghost']}
537
graph = self.make_graph(nodes)
538
distance_graph = graph.find_lefthand_distances(['nonghost', 'toghost'])
539
self.assertEqual({'nonghost': 1, 'toghost': -1}, distance_graph)
541
def test_recursive_unique_lca(self):
542
"""Test finding a unique least common ancestor.
544
ancestry_1 should always have a single common ancestor
546
graph = self.make_graph(ancestry_1)
547
self.assertEqual(NULL_REVISION,
548
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
549
self.assertEqual(NULL_REVISION,
550
graph.find_unique_lca(NULL_REVISION, 'rev1'))
551
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
552
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
553
self.assertEqual(('rev1', 1,),
554
graph.find_unique_lca('rev2a', 'rev2b',
557
def assertRemoveDescendants(self, expected, graph, revisions):
558
parents = graph.get_parent_map(revisions)
559
self.assertEqual(expected,
560
graph._remove_simple_descendants(revisions, parents))
562
def test__remove_simple_descendants(self):
563
graph = self.make_graph(ancestry_1)
564
self.assertRemoveDescendants(set(['rev1']), graph,
565
set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']))
567
def test__remove_simple_descendants_disjoint(self):
568
graph = self.make_graph(ancestry_1)
569
self.assertRemoveDescendants(set(['rev1', 'rev3']), graph,
570
set(['rev1', 'rev3']))
572
def test__remove_simple_descendants_chain(self):
573
graph = self.make_graph(ancestry_1)
574
self.assertRemoveDescendants(set(['rev1']), graph,
575
set(['rev1', 'rev2a', 'rev3']))
577
def test__remove_simple_descendants_siblings(self):
578
graph = self.make_graph(ancestry_1)
579
self.assertRemoveDescendants(set(['rev2a', 'rev2b']), graph,
580
set(['rev2a', 'rev2b', 'rev3']))
582
def test_unique_lca_criss_cross(self):
583
"""Ensure we don't pick non-unique lcas in a criss-cross"""
584
graph = self.make_graph(criss_cross)
585
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
586
lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
587
self.assertEqual('rev1', lca)
588
self.assertEqual(2, steps)
590
def test_unique_lca_null_revision(self):
591
"""Ensure we pick NULL_REVISION when necessary"""
592
graph = self.make_graph(criss_cross2)
593
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
594
self.assertEqual(NULL_REVISION,
595
graph.find_unique_lca('rev2a', 'rev2b'))
597
def test_unique_lca_null_revision2(self):
598
"""Ensure we pick NULL_REVISION when necessary"""
599
graph = self.make_graph(ancestry_2)
600
self.assertEqual(NULL_REVISION,
601
graph.find_unique_lca('rev4a', 'rev1b'))
603
def test_lca_double_shortcut(self):
604
graph = self.make_graph(double_shortcut)
605
self.assertEqual('c', graph.find_unique_lca('f', 'g'))
607
def test_common_ancestor_two_repos(self):
608
"""Ensure we do unique_lca using data from two repos"""
609
mainline_tree = self.prepare_memory_tree('mainline')
610
self.build_ancestry(mainline_tree, mainline)
611
self.addCleanup(mainline_tree.unlock)
613
# This is cheating, because the revisions in the graph are actually
614
# different revisions, despite having the same revision-id.
615
feature_tree = self.prepare_memory_tree('feature')
616
self.build_ancestry(feature_tree, feature_branch)
617
self.addCleanup(feature_tree.unlock)
619
graph = mainline_tree.branch.repository.get_graph(
620
feature_tree.branch.repository)
621
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
623
def test_graph_difference(self):
624
graph = self.make_graph(ancestry_1)
625
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
626
self.assertEqual((set(), set(['rev1'])),
627
graph.find_difference(NULL_REVISION, 'rev1'))
628
self.assertEqual((set(['rev1']), set()),
629
graph.find_difference('rev1', NULL_REVISION))
630
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
631
graph.find_difference('rev3', 'rev2b'))
632
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
633
graph.find_difference('rev4', 'rev2b'))
635
def test_graph_difference_separate_ancestry(self):
636
graph = self.make_graph(ancestry_2)
637
self.assertEqual((set(['rev1a']), set(['rev1b'])),
638
graph.find_difference('rev1a', 'rev1b'))
639
self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
641
graph.find_difference('rev4a', 'rev1b'))
643
def test_graph_difference_criss_cross(self):
644
graph = self.make_graph(criss_cross)
645
self.assertEqual((set(['rev3a']), set(['rev3b'])),
646
graph.find_difference('rev3a', 'rev3b'))
647
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
648
graph.find_difference('rev2a', 'rev3b'))
650
def test_graph_difference_extended_history(self):
651
graph = self.make_graph(extended_history_shortcut)
652
self.assertEqual((set(['e']), set(['f'])),
653
graph.find_difference('e', 'f'))
654
self.assertEqual((set(['f']), set(['e'])),
655
graph.find_difference('f', 'e'))
657
def test_graph_difference_double_shortcut(self):
658
graph = self.make_graph(double_shortcut)
659
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
660
graph.find_difference('f', 'g'))
662
def test_graph_difference_complex_shortcut(self):
663
graph = self.make_graph(complex_shortcut)
664
self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
665
graph.find_difference('m', 'n'))
667
def test_graph_difference_complex_shortcut2(self):
668
graph = self.make_graph(complex_shortcut2)
669
self.assertEqual((set(['t']), set(['j', 'u'])),
670
graph.find_difference('t', 'u'))
672
def test_graph_difference_shortcut_extra_root(self):
673
graph = self.make_graph(shortcut_extra_root)
674
self.assertEqual((set(['e']), set(['f', 'g'])),
675
graph.find_difference('e', 'f'))
678
def test_stacked_parents_provider(self):
679
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
680
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
681
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
682
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
683
stacked.get_parent_map(['rev1', 'rev2']))
684
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
685
stacked.get_parent_map(['rev2', 'rev1']))
686
self.assertEqual({'rev2':['rev3']},
687
stacked.get_parent_map(['rev2', 'rev2']))
688
self.assertEqual({'rev1':['rev4']},
689
stacked.get_parent_map(['rev1', 'rev1']))
691
def test_stacked_parents_provider_overlapping(self):
692
# rev2 is availible in both providers.
696
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
697
parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
698
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
699
self.assertEqual({'rev2': ['rev1']},
700
stacked.get_parent_map(['rev2']))
702
def test_iter_topo_order(self):
703
graph = self.make_graph(ancestry_1)
704
args = ['rev2a', 'rev3', 'rev1']
705
topo_args = list(graph.iter_topo_order(args))
706
self.assertEqual(set(args), set(topo_args))
707
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
708
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
710
def test_is_ancestor(self):
711
graph = self.make_graph(ancestry_1)
712
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
713
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
714
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
715
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
716
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
717
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
718
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
719
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
720
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
721
instrumented_provider = InstrumentedParentsProvider(graph)
722
instrumented_graph = _mod_graph.Graph(instrumented_provider)
723
instrumented_graph.is_ancestor('rev2a', 'rev2b')
724
self.assertTrue('null:' not in instrumented_provider.calls)
726
def test_is_between(self):
727
graph = self.make_graph(ancestry_1)
728
self.assertEqual(True, graph.is_between('null:', 'null:', 'null:'))
729
self.assertEqual(True, graph.is_between('rev1', 'null:', 'rev1'))
730
self.assertEqual(True, graph.is_between('rev1', 'rev1', 'rev4'))
731
self.assertEqual(True, graph.is_between('rev4', 'rev1', 'rev4'))
732
self.assertEqual(True, graph.is_between('rev3', 'rev1', 'rev4'))
733
self.assertEqual(False, graph.is_between('rev4', 'rev1', 'rev3'))
734
self.assertEqual(False, graph.is_between('rev1', 'rev2a', 'rev4'))
735
self.assertEqual(False, graph.is_between('null:', 'rev1', 'rev4'))
737
def test_is_ancestor_boundary(self):
738
"""Ensure that we avoid searching the whole graph.
740
This requires searching through b as a common ancestor, so we
741
can identify that e is common.
743
graph = self.make_graph(boundary)
744
instrumented_provider = InstrumentedParentsProvider(graph)
745
graph = _mod_graph.Graph(instrumented_provider)
746
self.assertFalse(graph.is_ancestor('a', 'c'))
747
self.assertTrue('null:' not in instrumented_provider.calls)
749
def test_iter_ancestry(self):
750
nodes = boundary.copy()
751
nodes[NULL_REVISION] = ()
752
graph = self.make_graph(nodes)
753
expected = nodes.copy()
754
expected.pop('a') # 'a' is not in the ancestry of 'c', all the
756
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
757
self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
759
def test_iter_ancestry_with_ghost(self):
760
graph = self.make_graph(with_ghost)
761
expected = with_ghost.copy()
762
# 'a' is not in the ancestry of 'c', and 'g' is a ghost
764
self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
766
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
768
def test_filter_candidate_lca(self):
769
"""Test filter_candidate_lca for a corner case
771
This tests the case where we encounter the end of iteration for 'e'
772
in the same pass as we discover that 'd' is an ancestor of 'e', and
773
therefore 'e' can't be an lca.
775
To compensate for different dict orderings on other Python
776
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
778
# This test is sensitive to the iteration order of dicts. It will
779
# pass incorrectly if 'e' and 'a' sort before 'c'
788
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
789
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
790
self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
792
def test_heads_null(self):
793
graph = self.make_graph(ancestry_1)
794
self.assertEqual(set(['null:']), graph.heads(['null:']))
795
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
796
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
797
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
798
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
800
def test_heads_one(self):
801
# A single node will always be a head
802
graph = self.make_graph(ancestry_1)
803
self.assertEqual(set(['null:']), graph.heads(['null:']))
804
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
805
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
806
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
807
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
808
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
810
def test_heads_single(self):
811
graph = self.make_graph(ancestry_1)
812
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
813
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
814
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
815
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
816
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
817
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
818
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
819
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
821
def test_heads_two_heads(self):
822
graph = self.make_graph(ancestry_1)
823
self.assertEqual(set(['rev2a', 'rev2b']),
824
graph.heads(['rev2a', 'rev2b']))
825
self.assertEqual(set(['rev3', 'rev2b']),
826
graph.heads(['rev3', 'rev2b']))
828
def test_heads_criss_cross(self):
829
graph = self.make_graph(criss_cross)
830
self.assertEqual(set(['rev2a']),
831
graph.heads(['rev2a', 'rev1']))
832
self.assertEqual(set(['rev2b']),
833
graph.heads(['rev2b', 'rev1']))
834
self.assertEqual(set(['rev3a']),
835
graph.heads(['rev3a', 'rev1']))
836
self.assertEqual(set(['rev3b']),
837
graph.heads(['rev3b', 'rev1']))
838
self.assertEqual(set(['rev2a', 'rev2b']),
839
graph.heads(['rev2a', 'rev2b']))
840
self.assertEqual(set(['rev3a']),
841
graph.heads(['rev3a', 'rev2a']))
842
self.assertEqual(set(['rev3a']),
843
graph.heads(['rev3a', 'rev2b']))
844
self.assertEqual(set(['rev3a']),
845
graph.heads(['rev3a', 'rev2a', 'rev2b']))
846
self.assertEqual(set(['rev3b']),
847
graph.heads(['rev3b', 'rev2a']))
848
self.assertEqual(set(['rev3b']),
849
graph.heads(['rev3b', 'rev2b']))
850
self.assertEqual(set(['rev3b']),
851
graph.heads(['rev3b', 'rev2a', 'rev2b']))
852
self.assertEqual(set(['rev3a', 'rev3b']),
853
graph.heads(['rev3a', 'rev3b']))
854
self.assertEqual(set(['rev3a', 'rev3b']),
855
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
857
def test_heads_shortcut(self):
858
graph = self.make_graph(history_shortcut)
860
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
861
graph.heads(['rev2a', 'rev2b', 'rev2c']))
862
self.assertEqual(set(['rev3a', 'rev3b']),
863
graph.heads(['rev3a', 'rev3b']))
864
self.assertEqual(set(['rev3a', 'rev3b']),
865
graph.heads(['rev2a', 'rev3a', 'rev3b']))
866
self.assertEqual(set(['rev2a', 'rev3b']),
867
graph.heads(['rev2a', 'rev3b']))
868
self.assertEqual(set(['rev2c', 'rev3a']),
869
graph.heads(['rev2c', 'rev3a']))
871
def _run_heads_break_deeper(self, graph_dict, search):
872
"""Run heads on a graph-as-a-dict.
874
If the search asks for the parents of 'deeper' the test will fail.
878
def get_parent_map(keys):
882
self.fail('key deeper was accessed')
883
result[key] = graph_dict[key]
886
an_obj.get_parent_map = get_parent_map
887
graph = _mod_graph.Graph(an_obj)
888
return graph.heads(search)
890
def test_heads_limits_search(self):
891
# test that a heads query does not search all of history
897
self.assertEqual(set(['left', 'right']),
898
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
900
def test_heads_limits_search_assymetric(self):
901
# test that a heads query does not search all of history
904
'midleft':['common'],
906
'common':['aftercommon'],
907
'aftercommon':['deeper'],
909
self.assertEqual(set(['left', 'right']),
910
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
912
def test_heads_limits_search_common_search_must_continue(self):
913
# test that common nodes are still queried, preventing
914
# all-the-way-to-origin behaviour in the following graph:
916
'h1':['shortcut', 'common1'],
918
'shortcut':['common2'],
919
'common1':['common2'],
920
'common2':['deeper'],
922
self.assertEqual(set(['h1', 'h2']),
923
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
925
def test_breadth_first_search_start_ghosts(self):
926
graph = self.make_graph({})
927
# with_ghosts reports the ghosts
928
search = graph._make_breadth_first_searcher(['a-ghost'])
929
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
930
self.assertRaises(StopIteration, search.next_with_ghosts)
932
search = graph._make_breadth_first_searcher(['a-ghost'])
933
self.assertEqual(set(['a-ghost']), search.next())
934
self.assertRaises(StopIteration, search.next)
936
def test_breadth_first_search_deep_ghosts(self):
937
graph = self.make_graph({
939
'present':['child', 'ghost'],
942
# with_ghosts reports the ghosts
943
search = graph._make_breadth_first_searcher(['head'])
944
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
945
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
946
self.assertEqual((set(['child']), set(['ghost'])),
947
search.next_with_ghosts())
948
self.assertRaises(StopIteration, search.next_with_ghosts)
950
search = graph._make_breadth_first_searcher(['head'])
951
self.assertEqual(set(['head']), search.next())
952
self.assertEqual(set(['present']), search.next())
953
self.assertEqual(set(['child', 'ghost']),
955
self.assertRaises(StopIteration, search.next)
957
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
958
# To make the API robust, we allow calling both next() and
959
# next_with_ghosts() on the same searcher.
960
graph = self.make_graph({
962
'present':['child', 'ghost'],
965
# start with next_with_ghosts
966
search = graph._make_breadth_first_searcher(['head'])
967
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
968
self.assertEqual(set(['present']), search.next())
969
self.assertEqual((set(['child']), set(['ghost'])),
970
search.next_with_ghosts())
971
self.assertRaises(StopIteration, search.next)
973
search = graph._make_breadth_first_searcher(['head'])
974
self.assertEqual(set(['head']), search.next())
975
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
976
self.assertEqual(set(['child', 'ghost']),
978
self.assertRaises(StopIteration, search.next_with_ghosts)
980
def test_breadth_first_change_search(self):
981
# Changing the search should work with both next and next_with_ghosts.
982
graph = self.make_graph({
984
'present':['stopped'],
988
search = graph._make_breadth_first_searcher(['head'])
989
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
990
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
991
self.assertEqual(set(['present']),
992
search.stop_searching_any(['present']))
993
self.assertEqual((set(['other']), set(['other_ghost'])),
994
search.start_searching(['other', 'other_ghost']))
995
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
996
self.assertRaises(StopIteration, search.next_with_ghosts)
998
search = graph._make_breadth_first_searcher(['head'])
999
self.assertEqual(set(['head']), search.next())
1000
self.assertEqual(set(['present']), search.next())
1001
self.assertEqual(set(['present']),
1002
search.stop_searching_any(['present']))
1003
search.start_searching(['other', 'other_ghost'])
1004
self.assertEqual(set(['other_2']), search.next())
1005
self.assertRaises(StopIteration, search.next)
1007
def assertSeenAndResult(self, instructions, search, next):
1008
"""Check the results of .seen and get_result() for a seach.
1010
:param instructions: A list of tuples:
1011
(seen, recipe, included_keys, starts, stops).
1012
seen, recipe and included_keys are results to check on the search
1013
and the searches get_result(). starts and stops are parameters to
1014
pass to start_searching and stop_searching_any during each
1015
iteration, if they are not None.
1016
:param search: The search to use.
1017
:param next: A callable to advance the search.
1019
for seen, recipe, included_keys, starts, stops in instructions:
1020
# Adjust for recipe contract changes that don't vary for all the
1022
recipe = ('search',) + recipe
1024
if starts is not None:
1025
search.start_searching(starts)
1026
if stops is not None:
1027
search.stop_searching_any(stops)
1028
result = search.get_result()
1029
self.assertEqual(recipe, result.get_recipe())
1030
self.assertEqual(set(included_keys), result.get_keys())
1031
self.assertEqual(seen, search.seen)
1033
def test_breadth_first_get_result_excludes_current_pending(self):
1034
graph = self.make_graph({
1036
'child':[NULL_REVISION],
1039
search = graph._make_breadth_first_searcher(['head'])
1040
# At the start, nothing has been seen, to its all excluded:
1041
result = search.get_result()
1042
self.assertEqual(('search', set(['head']), set(['head']), 0),
1043
result.get_recipe())
1044
self.assertEqual(set(), result.get_keys())
1045
self.assertEqual(set(), search.seen)
1048
(set(['head']), (set(['head']), set(['child']), 1),
1049
['head'], None, None),
1050
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
1051
['head', 'child'], None, None),
1052
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
1053
['head', 'child', NULL_REVISION], None, None),
1055
self.assertSeenAndResult(expected, search, search.next)
1056
# using next_with_ghosts:
1057
search = graph._make_breadth_first_searcher(['head'])
1058
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1060
def test_breadth_first_get_result_starts_stops(self):
1061
graph = self.make_graph({
1063
'child':[NULL_REVISION],
1064
'otherhead':['otherchild'],
1065
'otherchild':['excluded'],
1066
'excluded':[NULL_REVISION],
1069
search = graph._make_breadth_first_searcher([])
1070
# Starting with nothing and adding a search works:
1071
search.start_searching(['head'])
1072
# head has been seen:
1073
result = search.get_result()
1074
self.assertEqual(('search', set(['head']), set(['child']), 1),
1075
result.get_recipe())
1076
self.assertEqual(set(['head']), result.get_keys())
1077
self.assertEqual(set(['head']), search.seen)
1080
# stop at child, and start a new search at otherhead:
1081
# - otherhead counts as seen immediately when start_searching is
1083
(set(['head', 'child', 'otherhead']),
1084
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1085
['head', 'otherhead'], ['otherhead'], ['child']),
1086
(set(['head', 'child', 'otherhead', 'otherchild']),
1087
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1088
['head', 'otherhead', 'otherchild'], None, None),
1089
# stop searching excluded now
1090
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1091
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1092
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1094
self.assertSeenAndResult(expected, search, search.next)
1095
# using next_with_ghosts:
1096
search = graph._make_breadth_first_searcher([])
1097
search.start_searching(['head'])
1098
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1100
def test_breadth_first_stop_searching_not_queried(self):
1101
# A client should be able to say 'stop node X' even if X has not been
1102
# returned to the client.
1103
graph = self.make_graph({
1104
'head':['child', 'ghost1'],
1105
'child':[NULL_REVISION],
1108
search = graph._make_breadth_first_searcher(['head'])
1110
# NULL_REVISION and ghost1 have not been returned
1112
(set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1113
['head'], None, [NULL_REVISION, 'ghost1']),
1114
# ghost1 has been returned, NULL_REVISION is to be returned in the
1116
(set(['head', 'child', 'ghost1']),
1117
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1118
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1120
self.assertSeenAndResult(expected, search, search.next)
1121
# using next_with_ghosts:
1122
search = graph._make_breadth_first_searcher(['head'])
1123
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1125
def test_breadth_first_stop_searching_late(self):
1126
# A client should be able to say 'stop node X' and have it excluded
1127
# from the result even if X was seen in an older iteration of the
1129
graph = self.make_graph({
1132
'child':[NULL_REVISION],
1135
search = graph._make_breadth_first_searcher(['head'])
1137
(set(['head']), (set(['head']), set(['middle']), 1),
1138
['head'], None, None),
1139
(set(['head', 'middle']), (set(['head']), set(['child']), 2),
1140
['head', 'middle'], None, None),
1141
# 'middle' came from the previous iteration, but we don't stop
1142
# searching it until *after* advancing the searcher.
1143
(set(['head', 'middle', 'child']),
1144
(set(['head']), set(['middle', 'child']), 1),
1145
['head'], None, ['middle', 'child']),
1147
self.assertSeenAndResult(expected, search, search.next)
1148
# using next_with_ghosts:
1149
search = graph._make_breadth_first_searcher(['head'])
1150
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1152
def test_breadth_first_get_result_ghosts_are_excluded(self):
1153
graph = self.make_graph({
1154
'head':['child', 'ghost'],
1155
'child':[NULL_REVISION],
1158
search = graph._make_breadth_first_searcher(['head'])
1162
(set(['head']), set(['ghost', 'child']), 1),
1163
['head'], None, None),
1164
(set(['head', 'child', 'ghost']),
1165
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1166
['head', 'child'], None, None),
1168
self.assertSeenAndResult(expected, search, search.next)
1169
# using next_with_ghosts:
1170
search = graph._make_breadth_first_searcher(['head'])
1171
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1173
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1174
graph = self.make_graph({
1176
'child':[NULL_REVISION],
1179
search = graph._make_breadth_first_searcher(['head'])
1182
(set(['head', 'ghost']),
1183
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1184
['head'], ['ghost'], None),
1185
(set(['head', 'child', 'ghost']),
1186
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1187
['head', 'child'], None, None),
1189
self.assertSeenAndResult(expected, search, search.next)
1190
# using next_with_ghosts:
1191
search = graph._make_breadth_first_searcher(['head'])
1192
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1194
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1195
graph = self.make_graph({
1196
'head':[NULL_REVISION],
1199
search = graph._make_breadth_first_searcher(['head'])
1203
(set(['head']), set([NULL_REVISION]), 1),
1204
['head'], None, None),
1205
(set(['head', NULL_REVISION]),
1206
(set(['head']), set([]), 2),
1207
['head', NULL_REVISION], None, None),
1209
self.assertSeenAndResult(expected, search, search.next)
1210
# using next_with_ghosts:
1211
search = graph._make_breadth_first_searcher(['head'])
1212
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1214
def test_breadth_first_search_get_result_after_StopIteration(self):
1215
# StopIteration should not invalid anything..
1216
graph = self.make_graph({
1217
'head':[NULL_REVISION],
1220
search = graph._make_breadth_first_searcher(['head'])
1224
(set(['head']), set([NULL_REVISION]), 1),
1225
['head'], None, None),
1226
(set(['head', 'ghost', NULL_REVISION]),
1227
(set(['head', 'ghost']), set(['ghost']), 2),
1228
['head', NULL_REVISION], ['ghost'], None),
1230
self.assertSeenAndResult(expected, search, search.next)
1231
self.assertRaises(StopIteration, search.next)
1232
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1233
result = search.get_result()
1234
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1235
result.get_recipe())
1236
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1237
# using next_with_ghosts:
1238
search = graph._make_breadth_first_searcher(['head'])
1239
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1240
self.assertRaises(StopIteration, search.next)
1241
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1242
result = search.get_result()
1243
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1244
result.get_recipe())
1245
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1248
class TestFindUniqueAncestors(TestGraphBase):
1250
def assertFindUniqueAncestors(self, graph, expected, node, common):
1251
actual = graph.find_unique_ancestors(node, common)
1252
self.assertEqual(expected, sorted(actual))
1254
def test_empty_set(self):
1255
graph = self.make_graph(ancestry_1)
1256
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1257
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1258
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1260
def test_single_node(self):
1261
graph = self.make_graph(ancestry_1)
1262
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1263
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1264
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1266
def test_minimal_ancestry(self):
1267
graph = self.make_breaking_graph(extended_history_shortcut,
1268
[NULL_REVISION, 'a', 'b'])
1269
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1271
graph = self.make_breaking_graph(extended_history_shortcut,
1273
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1275
graph = self.make_breaking_graph(complex_shortcut,
1277
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1278
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1279
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1280
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1282
def test_in_ancestry(self):
1283
graph = self.make_graph(ancestry_1)
1284
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1285
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1287
def test_multiple_revisions(self):
1288
graph = self.make_graph(ancestry_1)
1289
self.assertFindUniqueAncestors(graph,
1290
['rev4'], 'rev4', ['rev3', 'rev2b'])
1291
self.assertFindUniqueAncestors(graph,
1292
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1294
def test_complex_shortcut(self):
1295
graph = self.make_graph(complex_shortcut)
1296
self.assertFindUniqueAncestors(graph,
1297
['h', 'n'], 'n', ['m'])
1298
self.assertFindUniqueAncestors(graph,
1299
['e', 'i', 'm'], 'm', ['n'])
1301
def test_complex_shortcut2(self):
1302
graph = self.make_graph(complex_shortcut2)
1303
self.assertFindUniqueAncestors(graph,
1304
['j', 'u'], 'u', ['t'])
1305
self.assertFindUniqueAncestors(graph,
1308
def test_multiple_interesting_unique(self):
1309
graph = self.make_graph(multiple_interesting_unique)
1310
self.assertFindUniqueAncestors(graph,
1311
['j', 'y'], 'y', ['z'])
1312
self.assertFindUniqueAncestors(graph,
1313
['p', 'z'], 'z', ['y'])
1315
def test_racing_shortcuts(self):
1316
graph = self.make_graph(racing_shortcuts)
1317
self.assertFindUniqueAncestors(graph,
1318
['p', 'q', 'z'], 'z', ['y'])
1319
self.assertFindUniqueAncestors(graph,
1320
['h', 'i', 'j', 'y'], 'j', ['z'])
1323
class TestGraphFindDistanceToNull(TestGraphBase):
1324
"""Test an api that should be able to compute a revno"""
1326
def assertFindDistance(self, revno, graph, target_id, known_ids):
1327
"""Assert the output of Graph.find_distance_to_null()"""
1328
actual = graph.find_distance_to_null(target_id, known_ids)
1329
self.assertEqual(revno, actual)
1331
def test_nothing_known(self):
1332
graph = self.make_graph(ancestry_1)
1333
self.assertFindDistance(0, graph, NULL_REVISION, [])
1334
self.assertFindDistance(1, graph, 'rev1', [])
1335
self.assertFindDistance(2, graph, 'rev2a', [])
1336
self.assertFindDistance(2, graph, 'rev2b', [])
1337
self.assertFindDistance(3, graph, 'rev3', [])
1338
self.assertFindDistance(4, graph, 'rev4', [])
1340
def test_rev_is_ghost(self):
1341
graph = self.make_graph(ancestry_1)
1342
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1343
graph.find_distance_to_null, 'rev_missing', [])
1344
self.assertEqual('rev_missing', e.revision_id)
1345
self.assertEqual('rev_missing', e.ghost_revision_id)
1347
def test_ancestor_is_ghost(self):
1348
graph = self.make_graph({'rev':['parent']})
1349
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1350
graph.find_distance_to_null, 'rev', [])
1351
self.assertEqual('rev', e.revision_id)
1352
self.assertEqual('parent', e.ghost_revision_id)
1354
def test_known_in_ancestry(self):
1355
graph = self.make_graph(ancestry_1)
1356
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1357
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1359
def test_known_in_ancestry_limits(self):
1360
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1361
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1363
def test_target_is_ancestor(self):
1364
graph = self.make_graph(ancestry_1)
1365
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1367
def test_target_is_ancestor_limits(self):
1368
"""We shouldn't search all history if we run into ourselves"""
1369
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1370
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1372
def test_target_parallel_to_known_limits(self):
1373
# Even though the known revision isn't part of the other ancestry, they
1374
# eventually converge
1375
graph = self.make_breaking_graph(with_tail, ['a'])
1376
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1377
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1378
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1379
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1382
class TestFindMergeOrder(TestGraphBase):
1384
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1385
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1387
def test_parents(self):
1388
graph = self.make_graph(ancestry_1)
1389
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1391
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1394
def test_ancestors(self):
1395
graph = self.make_graph(ancestry_1)
1396
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1398
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1401
def test_shortcut_one_ancestor(self):
1402
# When we have enough info, we can stop searching
1403
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1404
# Single ancestors shortcut right away
1405
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1407
def test_shortcut_after_one_ancestor(self):
1408
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1409
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1412
class TestFindDescendants(TestGraphBase):
1414
def test_find_descendants_rev1_rev3(self):
1415
graph = self.make_graph(ancestry_1)
1416
descendants = graph.find_descendants('rev1', 'rev3')
1417
self.assertEqual(set(['rev1', 'rev2a', 'rev3']), descendants)
1419
def test_find_descendants_rev1_rev4(self):
1420
graph = self.make_graph(ancestry_1)
1421
descendants = graph.find_descendants('rev1', 'rev4')
1422
self.assertEqual(set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']),
1425
def test_find_descendants_rev2a_rev4(self):
1426
graph = self.make_graph(ancestry_1)
1427
descendants = graph.find_descendants('rev2a', 'rev4')
1428
self.assertEqual(set(['rev2a', 'rev3', 'rev4']), descendants)
1430
class TestFindLefthandMerger(TestGraphBase):
1432
def check_merger(self, result, ancestry, merged, tip):
1433
graph = self.make_graph(ancestry)
1434
self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
1436
def test_find_lefthand_merger_rev2b(self):
1437
self.check_merger('rev4', ancestry_1, 'rev2b', 'rev4')
1439
def test_find_lefthand_merger_rev2a(self):
1440
self.check_merger('rev2a', ancestry_1, 'rev2a', 'rev4')
1442
def test_find_lefthand_merger_rev4(self):
1443
self.check_merger(None, ancestry_1, 'rev4', 'rev2a')
1445
def test_find_lefthand_merger_f(self):
1446
self.check_merger('i', complex_shortcut, 'f', 'm')
1448
def test_find_lefthand_merger_g(self):
1449
self.check_merger('i', complex_shortcut, 'g', 'm')
1451
def test_find_lefthand_merger_h(self):
1452
self.check_merger('n', complex_shortcut, 'h', 'n')
1455
class TestGetChildMap(TestGraphBase):
1457
def test_get_child_map(self):
1458
graph = self.make_graph(ancestry_1)
1459
child_map = graph.get_child_map(['rev4', 'rev3', 'rev2a', 'rev2b'])
1460
self.assertEqual({'rev1': ['rev2a', 'rev2b'],
1467
class TestCachingParentsProvider(tests.TestCase):
1468
"""These tests run with:
1470
self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1472
self.caching_pp, a CachingParentsProvider layered on inst_pp.
1476
super(TestCachingParentsProvider, self).setUp()
1477
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1478
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1479
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1481
def test_get_parent_map(self):
1482
"""Requesting the same revision should be returned from cache"""
1483
self.assertEqual({}, self.caching_pp._cache)
1484
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1485
self.assertEqual(['a'], self.inst_pp.calls)
1486
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1487
# No new call, as it should have been returned from the cache
1488
self.assertEqual(['a'], self.inst_pp.calls)
1489
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1491
def test_get_parent_map_not_present(self):
1492
"""The cache should also track when a revision doesn't exist"""
1493
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1494
self.assertEqual(['b'], self.inst_pp.calls)
1495
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1497
self.assertEqual(['b'], self.inst_pp.calls)
1499
def test_get_parent_map_mixed(self):
1500
"""Anything that can be returned from cache, should be"""
1501
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1502
self.assertEqual(['b'], self.inst_pp.calls)
1503
self.assertEqual({'a':('b',)},
1504
self.caching_pp.get_parent_map(['a', 'b']))
1505
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1507
def test_get_parent_map_repeated(self):
1508
"""Asking for the same parent 2x will only forward 1 request."""
1509
self.assertEqual({'a':('b',)},
1510
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1511
# Use sorted because we don't care about the order, just that each is
1512
# only present 1 time.
1513
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1515
def test_note_missing_key(self):
1516
"""After noting that a key is missing it is cached."""
1517
self.caching_pp.note_missing_key('b')
1518
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1519
self.assertEqual([], self.inst_pp.calls)
1520
self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1523
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1524
"""Test the behaviour when parents are provided that were not requested."""
1527
super(TestCachingParentsProviderExtras, self).setUp()
1528
class ExtraParentsProvider(object):
1530
def get_parent_map(self, keys):
1531
return {'rev1': [], 'rev2': ['rev1',]}
1533
self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1534
self.caching_pp = _mod_graph.CachingParentsProvider(
1535
get_parent_map=self.inst_pp.get_parent_map)
1537
def test_uncached(self):
1538
self.caching_pp.disable_cache()
1539
self.assertEqual({'rev1': []},
1540
self.caching_pp.get_parent_map(['rev1']))
1541
self.assertEqual(['rev1'], self.inst_pp.calls)
1542
self.assertIs(None, self.caching_pp._cache)
1544
def test_cache_initially_empty(self):
1545
self.assertEqual({}, self.caching_pp._cache)
1547
def test_cached(self):
1548
self.assertEqual({'rev1': []},
1549
self.caching_pp.get_parent_map(['rev1']))
1550
self.assertEqual(['rev1'], self.inst_pp.calls)
1551
self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1552
self.caching_pp._cache)
1553
self.assertEqual({'rev1': []},
1554
self.caching_pp.get_parent_map(['rev1']))
1555
self.assertEqual(['rev1'], self.inst_pp.calls)
1557
def test_disable_cache_clears_cache(self):
1558
# Put something in the cache
1559
self.caching_pp.get_parent_map(['rev1'])
1560
self.assertEqual(2, len(self.caching_pp._cache))
1561
self.caching_pp.disable_cache()
1562
self.assertIs(None, self.caching_pp._cache)
1564
def test_enable_cache_raises(self):
1565
e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1566
self.assertEqual('Cache enabled when already enabled.', str(e))
1568
def test_cache_misses(self):
1569
self.caching_pp.get_parent_map(['rev3'])
1570
self.caching_pp.get_parent_map(['rev3'])
1571
self.assertEqual(['rev3'], self.inst_pp.calls)
1573
def test_no_cache_misses(self):
1574
self.caching_pp.disable_cache()
1575
self.caching_pp.enable_cache(cache_misses=False)
1576
self.caching_pp.get_parent_map(['rev3'])
1577
self.caching_pp.get_parent_map(['rev3'])
1578
self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1580
def test_cache_extras(self):
1581
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1582
self.assertEqual({'rev2': ['rev1']},
1583
self.caching_pp.get_parent_map(['rev2']))
1584
self.assertEqual(['rev3'], self.inst_pp.calls)
1587
class TestCollapseLinearRegions(tests.TestCase):
1589
def assertCollapsed(self, collapsed, original):
1590
self.assertEqual(collapsed,
1591
_mod_graph.collapse_linear_regions(original))
1593
def test_collapse_nothing(self):
1594
d = {1:[2, 3], 2:[], 3:[]}
1595
self.assertCollapsed(d, d)
1596
d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1597
self.assertCollapsed(d, d)
1599
def test_collapse_chain(self):
1600
# Any time we have a linear chain, we should be able to collapse
1601
d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1602
self.assertCollapsed({1:[5], 5:[]}, d)
1603
d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1604
self.assertCollapsed({5:[1], 1:[]}, d)
1605
d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1606
self.assertCollapsed({5:[2], 2:[]}, d)
1608
def test_collapse_with_multiple_children(self):
1619
# 4 and 5 cannot be removed because 6 has 2 children
1620
# 2 and 3 cannot be removed because 1 has 2 parents
1621
d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1622
self.assertCollapsed(d, d)
1625
class TestGraphThunkIdsToKeys(tests.TestCase):
1627
def test_heads(self):
1633
d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1634
('B',): [('A',)], ('A',): []}
1635
g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1636
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1637
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
1638
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
1639
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1640
self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1642
def test_add_node(self):
1643
d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1644
g = _mod_graph.KnownGraph(d)
1645
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1646
graph_thunk.add_node("D", ["A", "C"])
1647
self.assertEqual(['B', 'D'],
1648
sorted(graph_thunk.heads(['D', 'B', 'A'])))
1651
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1652
"""Tests for bzrlib.graph.PendingAncestryResult."""
1654
def test_get_keys(self):
1655
builder = self.make_branch_builder('b')
1656
builder.start_series()
1657
builder.build_snapshot('rev-1', None, [
1658
('add', ('', 'root-id', 'directory', ''))])
1659
builder.build_snapshot('rev-2', ['rev-1'], [])
1660
builder.finish_series()
1661
repo = builder.get_branch().repository
1663
self.addCleanup(repo.unlock)
1664
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1665
self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1667
def test_get_keys_excludes_ghosts(self):
1668
builder = self.make_branch_builder('b')
1669
builder.start_series()
1670
builder.build_snapshot('rev-1', None, [
1671
('add', ('', 'root-id', 'directory', ''))])
1672
builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
1673
builder.finish_series()
1674
repo = builder.get_branch().repository
1676
self.addCleanup(repo.unlock)
1677
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1678
self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
1680
def test_get_keys_excludes_null(self):
1681
# Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1682
# somewhere other than the last element, which can happen in real
1684
class StubGraph(object):
1685
def iter_ancestry(self, keys):
1686
return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1687
result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1688
result_keys = result._get_keys(StubGraph())
1689
# Only the non-null keys from the ancestry appear.
1690
self.assertEqual(set(['foo']), set(result_keys))
1693
class TestPendingAncestryResultRefine(TestGraphBase):
1695
def test_refine(self):
1696
# Used when pulling from a stacked repository, so test some revisions
1697
# being satisfied from the stacking branch.
1698
g = self.make_graph(
1699
{"tip":["mid"], "mid":["base"], "tag":["base"],
1700
"base":[NULL_REVISION], NULL_REVISION:[]})
1701
result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1702
result = result.refine(set(['tip']), set(['mid']))
1703
self.assertEqual(set(['mid', 'tag']), result.heads)
1704
result = result.refine(set(['mid', 'tag', 'base']),
1705
set([NULL_REVISION]))
1706
self.assertEqual(set([NULL_REVISION]), result.heads)
1707
self.assertTrue(result.is_empty())
1710
class TestSearchResultRefine(TestGraphBase):
1712
def test_refine(self):
1713
# Used when pulling from a stacked repository, so test some revisions
1714
# being satisfied from the stacking branch.
1715
g = self.make_graph(
1716
{"tip":["mid"], "mid":["base"], "tag":["base"],
1717
"base":[NULL_REVISION], NULL_REVISION:[]})
1718
result = _mod_graph.SearchResult(set(['tip', 'tag']),
1719
set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1720
result = result.refine(set(['tip']), set(['mid']))
1721
recipe = result.get_recipe()
1722
# We should be starting from tag (original head) and mid (seen ref)
1723
self.assertEqual(set(['mid', 'tag']), recipe[1])
1724
# We should be stopping at NULL (original stop) and tip (seen head)
1725
self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1726
self.assertEqual(3, recipe[3])
1727
result = result.refine(set(['mid', 'tag', 'base']),
1728
set([NULL_REVISION]))
1729
recipe = result.get_recipe()
1730
# We should be starting from nothing (NULL was known as a cut point)
1731
self.assertEqual(set([]), recipe[1])
1732
# We should be stopping at NULL (original stop) and tip (seen head) and
1733
# tag (seen head) and mid(seen mid-point head). We could come back and
1734
# define this as not including mid, for minimal results, but it is
1735
# still 'correct' to include mid, and simpler/easier.
1736
self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1737
self.assertEqual(0, recipe[3])
1738
self.assertTrue(result.is_empty())
added
removed
bzrlib/tests/test_graph.py
