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
37
ancestry_1 = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
38
'rev3': ['rev2a'], 'rev4': ['rev3', 'rev2b']}
52
ancestry_2 = {'rev1a': [NULL_REVISION], 'rev2a': ['rev1a'],
53
'rev1b': [NULL_REVISION], 'rev3a': ['rev2a'], 'rev4a': ['rev3a']}
56
# Criss cross ancestry
67
criss_cross = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
68
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2a']}
82
criss_cross2 = {'rev1a': [NULL_REVISION], 'rev1b': [NULL_REVISION],
83
'rev2a': ['rev1a', 'rev1b'], 'rev2b': ['rev1b', 'rev1a']}
95
mainline = {'rev1': [NULL_REVISION], 'rev2a': ['rev1', 'rev2b'],
108
feature_branch = {'rev1': [NULL_REVISION],
109
'rev2b': ['rev1'], 'rev3b': ['rev2b']}
120
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
121
'rev2b': ['rev1'], 'rev2c': ['rev1'],
122
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
124
# Extended history shortcut
136
extended_history_shortcut = {'a': [NULL_REVISION],
145
# Both sides will see 'A' first, even though it is actually a decendent of a
146
# different common revision.
160
double_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
161
'd':['c'], 'e':['c'], 'f':['a', 'd'],
165
# This has a failure mode in that a shortcut will find some nodes in common,
166
# but the common searcher won't have time to find that one branch is actually
167
# in common. The extra nodes at the beginning are because we want to avoid
168
# walking off the graph. Specifically, node G should be considered common, but
169
# is likely to be seen by M long before the common searcher finds it.
192
complex_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
193
'e':['d'], 'f':['d'], 'g':['f'], 'h':['f'],
194
'i':['e', 'g'], 'j':['g'], 'k':['j'],
195
'l':['k'], 'm':['i', 'l'], 'n':['l', 'h']}
235
complex_shortcut2 = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
236
'e':['d'], 'f':['e'], 'g':['f'], 'h':['d'], 'i':['g'],
237
'j':['h'], 'k':['h', 'i'], 'l':['k'], 'm':['l'], 'n':['m'],
238
'o':['n'], 'p':['o'], 'q':['p'], 'r':['q'], 's':['r'],
239
't':['i', 's'], 'u':['s', 'j'],
242
# Graph where different walkers will race to find the common and uncommon
285
# x is found to be common right away, but is the start of a long series of
287
# o is actually common, but the i-j shortcut makes it look like it is actually
288
# unique to j at first, you have to traverse all of x->o to find it.
289
# q,m gives the walker from j a common point to stop searching, as does p,f.
290
# k-n exists so that the second pass still has nodes that are worth searching,
291
# rather than instantly cancelling the extra walker.
293
racing_shortcuts = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
294
'e':['d'], 'f':['e'], 'g':['f'], 'h':['g'], 'i':['h', 'o'], 'j':['i', 'y'],
295
'k':['d'], 'l':['k'], 'm':['l'], 'n':['m'], 'o':['n', 'g'], 'p':['f'],
296
'q':['p', 'm'], 'r':['o'], 's':['r'], 't':['s'], 'u':['t'], 'v':['u'],
297
'w':['v'], 'x':['w'], 'y':['x'], 'z':['x', 'q']}
300
# A graph with multiple nodes unique to one side.
339
multiple_interesting_unique = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
340
'd':['c'], 'e':['d'], 'f':['d'], 'g':['e'], 'h':['e'], 'i':['f'],
341
'j':['g'], 'k':['g'], 'l':['h'], 'm':['i'], 'n':['k', 'l'],
342
'o':['m'], 'p':['m', 'l'], 'q':['n', 'o'], 'r':['q'], 's':['r'],
343
't':['s'], 'u':['t'], 'v':['u'], 'w':['v'], 'x':['w'],
344
'y':['j', 'x'], 'z':['x', 'p']}
347
# Shortcut with extra root
348
# We have a long history shortcut, and an extra root, which is why we can't
349
# stop searchers based on seeing NULL_REVISION
361
shortcut_extra_root = {'a': [NULL_REVISION],
366
'f': ['a', 'd', 'g'],
367
'g': [NULL_REVISION],
380
boundary = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e'], 'e': ['f'],
384
# A graph that contains a ghost
395
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
396
'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
398
# A graph that shows we can shortcut finding revnos when reaching them from the
418
with_tail = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'], 'e':['d'],
419
'f':['e'], 'g':['e'], 'h':['f'], 'i':['h']}
422
class InstrumentedParentsProvider(object):
424
def __init__(self, parents_provider):
426
self._real_parents_provider = parents_provider
428
def get_parent_map(self, nodes):
429
self.calls.extend(nodes)
430
return self._real_parents_provider.get_parent_map(nodes)
433
class TestGraphBase(tests.TestCase):
435
def make_graph(self, ancestors):
436
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
438
def make_breaking_graph(self, ancestors, break_on):
439
"""Make a Graph that raises an exception if we hit a node."""
440
g = self.make_graph(ancestors)
441
orig_parent_map = g.get_parent_map
442
def get_parent_map(keys):
443
bad_keys = set(keys).intersection(break_on)
445
self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
446
return orig_parent_map(keys)
447
g.get_parent_map = get_parent_map
451
class TestGraph(TestCaseWithMemoryTransport):
453
def make_graph(self, ancestors):
454
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
456
def prepare_memory_tree(self, location):
457
tree = self.make_branch_and_memory_tree(location)
462
def build_ancestry(self, tree, ancestors):
463
"""Create an ancestry as specified by a graph dict
465
:param tree: A tree to use
466
:param ancestors: a dict of {node: [node_parent, ...]}
468
pending = [NULL_REVISION]
470
for descendant, parents in ancestors.iteritems():
471
for parent in parents:
472
descendants.setdefault(parent, []).append(descendant)
473
while len(pending) > 0:
474
cur_node = pending.pop()
475
for descendant in descendants.get(cur_node, []):
476
if tree.branch.repository.has_revision(descendant):
478
parents = [p for p in ancestors[descendant] if p is not
480
if len([p for p in parents if not
481
tree.branch.repository.has_revision(p)]) > 0:
483
tree.set_parent_ids(parents)
485
left_parent = parents[0]
487
left_parent = NULL_REVISION
488
tree.branch.set_last_revision_info(
489
len(tree.branch._lefthand_history(left_parent)),
491
tree.commit(descendant, rev_id=descendant)
492
pending.append(descendant)
495
"""Test finding least common ancestor.
497
ancestry_1 should always have a single common ancestor
499
graph = self.make_graph(ancestry_1)
500
self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
501
self.assertEqual(set([NULL_REVISION]),
502
graph.find_lca(NULL_REVISION, NULL_REVISION))
503
self.assertEqual(set([NULL_REVISION]),
504
graph.find_lca(NULL_REVISION, 'rev1'))
505
self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
506
self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
508
def test_no_unique_lca(self):
509
"""Test error when one revision is not in the graph"""
510
graph = self.make_graph(ancestry_1)
511
self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
514
def test_lca_criss_cross(self):
515
"""Test least-common-ancestor after a criss-cross merge."""
516
graph = self.make_graph(criss_cross)
517
self.assertEqual(set(['rev2a', 'rev2b']),
518
graph.find_lca('rev3a', 'rev3b'))
519
self.assertEqual(set(['rev2b']),
520
graph.find_lca('rev3a', 'rev3b', 'rev2b'))
522
def test_lca_shortcut(self):
523
"""Test least-common ancestor on this history shortcut"""
524
graph = self.make_graph(history_shortcut)
525
self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
527
def test_lefthand_distance_smoke(self):
528
"""A simple does it work test for graph.lefthand_distance(keys)."""
529
graph = self.make_graph(history_shortcut)
530
distance_graph = graph.find_lefthand_distances(['rev3b', 'rev2a'])
531
self.assertEqual({'rev2a': 2, 'rev3b': 3}, distance_graph)
533
def test_lefthand_distance_ghosts(self):
534
"""A simple does it work test for graph.lefthand_distance(keys)."""
535
nodes = {'nonghost':[NULL_REVISION], 'toghost':['ghost']}
536
graph = self.make_graph(nodes)
537
distance_graph = graph.find_lefthand_distances(['nonghost', 'toghost'])
538
self.assertEqual({'nonghost': 1, 'toghost': -1}, distance_graph)
540
def test_recursive_unique_lca(self):
541
"""Test finding a unique least common ancestor.
543
ancestry_1 should always have a single common ancestor
545
graph = self.make_graph(ancestry_1)
546
self.assertEqual(NULL_REVISION,
547
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
548
self.assertEqual(NULL_REVISION,
549
graph.find_unique_lca(NULL_REVISION, 'rev1'))
550
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
551
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
552
self.assertEqual(('rev1', 1,),
553
graph.find_unique_lca('rev2a', 'rev2b',
556
def assertRemoveDescendants(self, expected, graph, revisions):
557
parents = graph.get_parent_map(revisions)
558
self.assertEqual(expected,
559
graph._remove_simple_descendants(revisions, parents))
561
def test__remove_simple_descendants(self):
562
graph = self.make_graph(ancestry_1)
563
self.assertRemoveDescendants(set(['rev1']), graph,
564
set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']))
566
def test__remove_simple_descendants_disjoint(self):
567
graph = self.make_graph(ancestry_1)
568
self.assertRemoveDescendants(set(['rev1', 'rev3']), graph,
569
set(['rev1', 'rev3']))
571
def test__remove_simple_descendants_chain(self):
572
graph = self.make_graph(ancestry_1)
573
self.assertRemoveDescendants(set(['rev1']), graph,
574
set(['rev1', 'rev2a', 'rev3']))
576
def test__remove_simple_descendants_siblings(self):
577
graph = self.make_graph(ancestry_1)
578
self.assertRemoveDescendants(set(['rev2a', 'rev2b']), graph,
579
set(['rev2a', 'rev2b', 'rev3']))
581
def test_unique_lca_criss_cross(self):
582
"""Ensure we don't pick non-unique lcas in a criss-cross"""
583
graph = self.make_graph(criss_cross)
584
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
585
lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
586
self.assertEqual('rev1', lca)
587
self.assertEqual(2, steps)
589
def test_unique_lca_null_revision(self):
590
"""Ensure we pick NULL_REVISION when necessary"""
591
graph = self.make_graph(criss_cross2)
592
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
593
self.assertEqual(NULL_REVISION,
594
graph.find_unique_lca('rev2a', 'rev2b'))
596
def test_unique_lca_null_revision2(self):
597
"""Ensure we pick NULL_REVISION when necessary"""
598
graph = self.make_graph(ancestry_2)
599
self.assertEqual(NULL_REVISION,
600
graph.find_unique_lca('rev4a', 'rev1b'))
602
def test_lca_double_shortcut(self):
603
graph = self.make_graph(double_shortcut)
604
self.assertEqual('c', graph.find_unique_lca('f', 'g'))
606
def test_common_ancestor_two_repos(self):
607
"""Ensure we do unique_lca using data from two repos"""
608
mainline_tree = self.prepare_memory_tree('mainline')
609
self.build_ancestry(mainline_tree, mainline)
610
self.addCleanup(mainline_tree.unlock)
612
# This is cheating, because the revisions in the graph are actually
613
# different revisions, despite having the same revision-id.
614
feature_tree = self.prepare_memory_tree('feature')
615
self.build_ancestry(feature_tree, feature_branch)
616
self.addCleanup(feature_tree.unlock)
618
graph = mainline_tree.branch.repository.get_graph(
619
feature_tree.branch.repository)
620
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
622
def test_graph_difference(self):
623
graph = self.make_graph(ancestry_1)
624
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
625
self.assertEqual((set(), set(['rev1'])),
626
graph.find_difference(NULL_REVISION, 'rev1'))
627
self.assertEqual((set(['rev1']), set()),
628
graph.find_difference('rev1', NULL_REVISION))
629
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
630
graph.find_difference('rev3', 'rev2b'))
631
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
632
graph.find_difference('rev4', 'rev2b'))
634
def test_graph_difference_separate_ancestry(self):
635
graph = self.make_graph(ancestry_2)
636
self.assertEqual((set(['rev1a']), set(['rev1b'])),
637
graph.find_difference('rev1a', 'rev1b'))
638
self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
640
graph.find_difference('rev4a', 'rev1b'))
642
def test_graph_difference_criss_cross(self):
643
graph = self.make_graph(criss_cross)
644
self.assertEqual((set(['rev3a']), set(['rev3b'])),
645
graph.find_difference('rev3a', 'rev3b'))
646
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
647
graph.find_difference('rev2a', 'rev3b'))
649
def test_graph_difference_extended_history(self):
650
graph = self.make_graph(extended_history_shortcut)
651
self.assertEqual((set(['e']), set(['f'])),
652
graph.find_difference('e', 'f'))
653
self.assertEqual((set(['f']), set(['e'])),
654
graph.find_difference('f', 'e'))
656
def test_graph_difference_double_shortcut(self):
657
graph = self.make_graph(double_shortcut)
658
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
659
graph.find_difference('f', 'g'))
661
def test_graph_difference_complex_shortcut(self):
662
graph = self.make_graph(complex_shortcut)
663
self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
664
graph.find_difference('m', 'n'))
666
def test_graph_difference_complex_shortcut2(self):
667
graph = self.make_graph(complex_shortcut2)
668
self.assertEqual((set(['t']), set(['j', 'u'])),
669
graph.find_difference('t', 'u'))
671
def test_graph_difference_shortcut_extra_root(self):
672
graph = self.make_graph(shortcut_extra_root)
673
self.assertEqual((set(['e']), set(['f', 'g'])),
674
graph.find_difference('e', 'f'))
677
def test_stacked_parents_provider(self):
678
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
679
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
680
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
681
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
682
stacked.get_parent_map(['rev1', 'rev2']))
683
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
684
stacked.get_parent_map(['rev2', 'rev1']))
685
self.assertEqual({'rev2':['rev3']},
686
stacked.get_parent_map(['rev2', 'rev2']))
687
self.assertEqual({'rev1':['rev4']},
688
stacked.get_parent_map(['rev1', 'rev1']))
690
def test_stacked_parents_provider_overlapping(self):
691
# rev2 is availible in both providers.
695
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
696
parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
697
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
698
self.assertEqual({'rev2': ['rev1']},
699
stacked.get_parent_map(['rev2']))
701
def test_iter_topo_order(self):
702
graph = self.make_graph(ancestry_1)
703
args = ['rev2a', 'rev3', 'rev1']
704
topo_args = list(graph.iter_topo_order(args))
705
self.assertEqual(set(args), set(topo_args))
706
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
707
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
709
def test_is_ancestor(self):
710
graph = self.make_graph(ancestry_1)
711
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
712
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
713
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
714
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
715
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
716
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
717
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
718
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
719
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
720
instrumented_provider = InstrumentedParentsProvider(graph)
721
instrumented_graph = _mod_graph.Graph(instrumented_provider)
722
instrumented_graph.is_ancestor('rev2a', 'rev2b')
723
self.assertTrue('null:' not in instrumented_provider.calls)
725
def test_is_between(self):
726
graph = self.make_graph(ancestry_1)
727
self.assertEqual(True, graph.is_between('null:', 'null:', 'null:'))
728
self.assertEqual(True, graph.is_between('rev1', 'null:', 'rev1'))
729
self.assertEqual(True, graph.is_between('rev1', 'rev1', 'rev4'))
730
self.assertEqual(True, graph.is_between('rev4', 'rev1', 'rev4'))
731
self.assertEqual(True, graph.is_between('rev3', 'rev1', 'rev4'))
732
self.assertEqual(False, graph.is_between('rev4', 'rev1', 'rev3'))
733
self.assertEqual(False, graph.is_between('rev1', 'rev2a', 'rev4'))
734
self.assertEqual(False, graph.is_between('null:', 'rev1', 'rev4'))
736
def test_is_ancestor_boundary(self):
737
"""Ensure that we avoid searching the whole graph.
739
This requires searching through b as a common ancestor, so we
740
can identify that e is common.
742
graph = self.make_graph(boundary)
743
instrumented_provider = InstrumentedParentsProvider(graph)
744
graph = _mod_graph.Graph(instrumented_provider)
745
self.assertFalse(graph.is_ancestor('a', 'c'))
746
self.assertTrue('null:' not in instrumented_provider.calls)
748
def test_iter_ancestry(self):
749
nodes = boundary.copy()
750
nodes[NULL_REVISION] = ()
751
graph = self.make_graph(nodes)
752
expected = nodes.copy()
753
expected.pop('a') # 'a' is not in the ancestry of 'c', all the
755
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
756
self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
758
def test_iter_ancestry_with_ghost(self):
759
graph = self.make_graph(with_ghost)
760
expected = with_ghost.copy()
761
# 'a' is not in the ancestry of 'c', and 'g' is a ghost
763
self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
765
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
767
def test_filter_candidate_lca(self):
768
"""Test filter_candidate_lca for a corner case
770
This tests the case where we encounter the end of iteration for 'e'
771
in the same pass as we discover that 'd' is an ancestor of 'e', and
772
therefore 'e' can't be an lca.
774
To compensate for different dict orderings on other Python
775
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
777
# This test is sensitive to the iteration order of dicts. It will
778
# pass incorrectly if 'e' and 'a' sort before 'c'
787
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
788
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
789
self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
791
def test_heads_null(self):
792
graph = self.make_graph(ancestry_1)
793
self.assertEqual(set(['null:']), graph.heads(['null:']))
794
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
795
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
796
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
797
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
799
def test_heads_one(self):
800
# A single node will always be a head
801
graph = self.make_graph(ancestry_1)
802
self.assertEqual(set(['null:']), graph.heads(['null:']))
803
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
804
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
805
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
806
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
807
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
809
def test_heads_single(self):
810
graph = self.make_graph(ancestry_1)
811
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
812
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
813
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
814
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
815
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
816
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
817
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
818
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
820
def test_heads_two_heads(self):
821
graph = self.make_graph(ancestry_1)
822
self.assertEqual(set(['rev2a', 'rev2b']),
823
graph.heads(['rev2a', 'rev2b']))
824
self.assertEqual(set(['rev3', 'rev2b']),
825
graph.heads(['rev3', 'rev2b']))
827
def test_heads_criss_cross(self):
828
graph = self.make_graph(criss_cross)
829
self.assertEqual(set(['rev2a']),
830
graph.heads(['rev2a', 'rev1']))
831
self.assertEqual(set(['rev2b']),
832
graph.heads(['rev2b', 'rev1']))
833
self.assertEqual(set(['rev3a']),
834
graph.heads(['rev3a', 'rev1']))
835
self.assertEqual(set(['rev3b']),
836
graph.heads(['rev3b', 'rev1']))
837
self.assertEqual(set(['rev2a', 'rev2b']),
838
graph.heads(['rev2a', 'rev2b']))
839
self.assertEqual(set(['rev3a']),
840
graph.heads(['rev3a', 'rev2a']))
841
self.assertEqual(set(['rev3a']),
842
graph.heads(['rev3a', 'rev2b']))
843
self.assertEqual(set(['rev3a']),
844
graph.heads(['rev3a', 'rev2a', 'rev2b']))
845
self.assertEqual(set(['rev3b']),
846
graph.heads(['rev3b', 'rev2a']))
847
self.assertEqual(set(['rev3b']),
848
graph.heads(['rev3b', 'rev2b']))
849
self.assertEqual(set(['rev3b']),
850
graph.heads(['rev3b', 'rev2a', 'rev2b']))
851
self.assertEqual(set(['rev3a', 'rev3b']),
852
graph.heads(['rev3a', 'rev3b']))
853
self.assertEqual(set(['rev3a', 'rev3b']),
854
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
856
def test_heads_shortcut(self):
857
graph = self.make_graph(history_shortcut)
859
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
860
graph.heads(['rev2a', 'rev2b', 'rev2c']))
861
self.assertEqual(set(['rev3a', 'rev3b']),
862
graph.heads(['rev3a', 'rev3b']))
863
self.assertEqual(set(['rev3a', 'rev3b']),
864
graph.heads(['rev2a', 'rev3a', 'rev3b']))
865
self.assertEqual(set(['rev2a', 'rev3b']),
866
graph.heads(['rev2a', 'rev3b']))
867
self.assertEqual(set(['rev2c', 'rev3a']),
868
graph.heads(['rev2c', 'rev3a']))
870
def _run_heads_break_deeper(self, graph_dict, search):
871
"""Run heads on a graph-as-a-dict.
873
If the search asks for the parents of 'deeper' the test will fail.
877
def get_parent_map(keys):
881
self.fail('key deeper was accessed')
882
result[key] = graph_dict[key]
885
an_obj.get_parent_map = get_parent_map
886
graph = _mod_graph.Graph(an_obj)
887
return graph.heads(search)
889
def test_heads_limits_search(self):
890
# test that a heads query does not search all of history
896
self.assertEqual(set(['left', 'right']),
897
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
899
def test_heads_limits_search_assymetric(self):
900
# test that a heads query does not search all of history
903
'midleft':['common'],
905
'common':['aftercommon'],
906
'aftercommon':['deeper'],
908
self.assertEqual(set(['left', 'right']),
909
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
911
def test_heads_limits_search_common_search_must_continue(self):
912
# test that common nodes are still queried, preventing
913
# all-the-way-to-origin behaviour in the following graph:
915
'h1':['shortcut', 'common1'],
917
'shortcut':['common2'],
918
'common1':['common2'],
919
'common2':['deeper'],
921
self.assertEqual(set(['h1', 'h2']),
922
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
924
def test_breadth_first_search_start_ghosts(self):
925
graph = self.make_graph({})
926
# with_ghosts reports the ghosts
927
search = graph._make_breadth_first_searcher(['a-ghost'])
928
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
929
self.assertRaises(StopIteration, search.next_with_ghosts)
931
search = graph._make_breadth_first_searcher(['a-ghost'])
932
self.assertEqual(set(['a-ghost']), search.next())
933
self.assertRaises(StopIteration, search.next)
935
def test_breadth_first_search_deep_ghosts(self):
936
graph = self.make_graph({
938
'present':['child', 'ghost'],
941
# with_ghosts reports the ghosts
942
search = graph._make_breadth_first_searcher(['head'])
943
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
944
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
945
self.assertEqual((set(['child']), set(['ghost'])),
946
search.next_with_ghosts())
947
self.assertRaises(StopIteration, search.next_with_ghosts)
949
search = graph._make_breadth_first_searcher(['head'])
950
self.assertEqual(set(['head']), search.next())
951
self.assertEqual(set(['present']), search.next())
952
self.assertEqual(set(['child', 'ghost']),
954
self.assertRaises(StopIteration, search.next)
956
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
957
# To make the API robust, we allow calling both next() and
958
# next_with_ghosts() on the same searcher.
959
graph = self.make_graph({
961
'present':['child', 'ghost'],
964
# start with next_with_ghosts
965
search = graph._make_breadth_first_searcher(['head'])
966
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
967
self.assertEqual(set(['present']), search.next())
968
self.assertEqual((set(['child']), set(['ghost'])),
969
search.next_with_ghosts())
970
self.assertRaises(StopIteration, search.next)
972
search = graph._make_breadth_first_searcher(['head'])
973
self.assertEqual(set(['head']), search.next())
974
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
975
self.assertEqual(set(['child', 'ghost']),
977
self.assertRaises(StopIteration, search.next_with_ghosts)
979
def test_breadth_first_change_search(self):
980
# Changing the search should work with both next and next_with_ghosts.
981
graph = self.make_graph({
983
'present':['stopped'],
987
search = graph._make_breadth_first_searcher(['head'])
988
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
989
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
990
self.assertEqual(set(['present']),
991
search.stop_searching_any(['present']))
992
self.assertEqual((set(['other']), set(['other_ghost'])),
993
search.start_searching(['other', 'other_ghost']))
994
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
995
self.assertRaises(StopIteration, search.next_with_ghosts)
997
search = graph._make_breadth_first_searcher(['head'])
998
self.assertEqual(set(['head']), search.next())
999
self.assertEqual(set(['present']), search.next())
1000
self.assertEqual(set(['present']),
1001
search.stop_searching_any(['present']))
1002
search.start_searching(['other', 'other_ghost'])
1003
self.assertEqual(set(['other_2']), search.next())
1004
self.assertRaises(StopIteration, search.next)
1006
def assertSeenAndResult(self, instructions, search, next):
1007
"""Check the results of .seen and get_result() for a seach.
1009
:param instructions: A list of tuples:
1010
(seen, recipe, included_keys, starts, stops).
1011
seen, recipe and included_keys are results to check on the search
1012
and the searches get_result(). starts and stops are parameters to
1013
pass to start_searching and stop_searching_any during each
1014
iteration, if they are not None.
1015
:param search: The search to use.
1016
:param next: A callable to advance the search.
1018
for seen, recipe, included_keys, starts, stops in instructions:
1019
# Adjust for recipe contract changes that don't vary for all the
1021
recipe = ('search',) + recipe
1023
if starts is not None:
1024
search.start_searching(starts)
1025
if stops is not None:
1026
search.stop_searching_any(stops)
1027
result = search.get_result()
1028
self.assertEqual(recipe, result.get_recipe())
1029
self.assertEqual(set(included_keys), result.get_keys())
1030
self.assertEqual(seen, search.seen)
1032
def test_breadth_first_get_result_excludes_current_pending(self):
1033
graph = self.make_graph({
1035
'child':[NULL_REVISION],
1038
search = graph._make_breadth_first_searcher(['head'])
1039
# At the start, nothing has been seen, to its all excluded:
1040
result = search.get_result()
1041
self.assertEqual(('search', set(['head']), set(['head']), 0),
1042
result.get_recipe())
1043
self.assertEqual(set(), result.get_keys())
1044
self.assertEqual(set(), search.seen)
1047
(set(['head']), (set(['head']), set(['child']), 1),
1048
['head'], None, None),
1049
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
1050
['head', 'child'], None, None),
1051
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
1052
['head', 'child', NULL_REVISION], None, None),
1054
self.assertSeenAndResult(expected, search, search.next)
1055
# using next_with_ghosts:
1056
search = graph._make_breadth_first_searcher(['head'])
1057
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1059
def test_breadth_first_get_result_starts_stops(self):
1060
graph = self.make_graph({
1062
'child':[NULL_REVISION],
1063
'otherhead':['otherchild'],
1064
'otherchild':['excluded'],
1065
'excluded':[NULL_REVISION],
1068
search = graph._make_breadth_first_searcher([])
1069
# Starting with nothing and adding a search works:
1070
search.start_searching(['head'])
1071
# head has been seen:
1072
result = search.get_result()
1073
self.assertEqual(('search', set(['head']), set(['child']), 1),
1074
result.get_recipe())
1075
self.assertEqual(set(['head']), result.get_keys())
1076
self.assertEqual(set(['head']), search.seen)
1079
# stop at child, and start a new search at otherhead:
1080
# - otherhead counts as seen immediately when start_searching is
1082
(set(['head', 'child', 'otherhead']),
1083
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1084
['head', 'otherhead'], ['otherhead'], ['child']),
1085
(set(['head', 'child', 'otherhead', 'otherchild']),
1086
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1087
['head', 'otherhead', 'otherchild'], None, None),
1088
# stop searching excluded now
1089
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1090
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1091
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1093
self.assertSeenAndResult(expected, search, search.next)
1094
# using next_with_ghosts:
1095
search = graph._make_breadth_first_searcher([])
1096
search.start_searching(['head'])
1097
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1099
def test_breadth_first_stop_searching_not_queried(self):
1100
# A client should be able to say 'stop node X' even if X has not been
1101
# returned to the client.
1102
graph = self.make_graph({
1103
'head':['child', 'ghost1'],
1104
'child':[NULL_REVISION],
1107
search = graph._make_breadth_first_searcher(['head'])
1109
# NULL_REVISION and ghost1 have not been returned
1111
(set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1112
['head'], None, [NULL_REVISION, 'ghost1']),
1113
# ghost1 has been returned, NULL_REVISION is to be returned in the
1115
(set(['head', 'child', 'ghost1']),
1116
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1117
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1119
self.assertSeenAndResult(expected, search, search.next)
1120
# using next_with_ghosts:
1121
search = graph._make_breadth_first_searcher(['head'])
1122
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1124
def test_breadth_first_stop_searching_late(self):
1125
# A client should be able to say 'stop node X' and have it excluded
1126
# from the result even if X was seen in an older iteration of the
1128
graph = self.make_graph({
1131
'child':[NULL_REVISION],
1134
search = graph._make_breadth_first_searcher(['head'])
1136
(set(['head']), (set(['head']), set(['middle']), 1),
1137
['head'], None, None),
1138
(set(['head', 'middle']), (set(['head']), set(['child']), 2),
1139
['head', 'middle'], None, None),
1140
# 'middle' came from the previous iteration, but we don't stop
1141
# searching it until *after* advancing the searcher.
1142
(set(['head', 'middle', 'child']),
1143
(set(['head']), set(['middle', 'child']), 1),
1144
['head'], None, ['middle', 'child']),
1146
self.assertSeenAndResult(expected, search, search.next)
1147
# using next_with_ghosts:
1148
search = graph._make_breadth_first_searcher(['head'])
1149
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1151
def test_breadth_first_get_result_ghosts_are_excluded(self):
1152
graph = self.make_graph({
1153
'head':['child', 'ghost'],
1154
'child':[NULL_REVISION],
1157
search = graph._make_breadth_first_searcher(['head'])
1161
(set(['head']), set(['ghost', 'child']), 1),
1162
['head'], None, None),
1163
(set(['head', 'child', 'ghost']),
1164
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1165
['head', 'child'], None, None),
1167
self.assertSeenAndResult(expected, search, search.next)
1168
# using next_with_ghosts:
1169
search = graph._make_breadth_first_searcher(['head'])
1170
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1172
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1173
graph = self.make_graph({
1175
'child':[NULL_REVISION],
1178
search = graph._make_breadth_first_searcher(['head'])
1181
(set(['head', 'ghost']),
1182
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1183
['head'], ['ghost'], None),
1184
(set(['head', 'child', 'ghost']),
1185
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1186
['head', 'child'], None, None),
1188
self.assertSeenAndResult(expected, search, search.next)
1189
# using next_with_ghosts:
1190
search = graph._make_breadth_first_searcher(['head'])
1191
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1193
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1194
graph = self.make_graph({
1195
'head':[NULL_REVISION],
1198
search = graph._make_breadth_first_searcher(['head'])
1202
(set(['head']), set([NULL_REVISION]), 1),
1203
['head'], None, None),
1204
(set(['head', NULL_REVISION]),
1205
(set(['head']), set([]), 2),
1206
['head', NULL_REVISION], None, None),
1208
self.assertSeenAndResult(expected, search, search.next)
1209
# using next_with_ghosts:
1210
search = graph._make_breadth_first_searcher(['head'])
1211
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1213
def test_breadth_first_search_get_result_after_StopIteration(self):
1214
# StopIteration should not invalid anything..
1215
graph = self.make_graph({
1216
'head':[NULL_REVISION],
1219
search = graph._make_breadth_first_searcher(['head'])
1223
(set(['head']), set([NULL_REVISION]), 1),
1224
['head'], None, None),
1225
(set(['head', 'ghost', NULL_REVISION]),
1226
(set(['head', 'ghost']), set(['ghost']), 2),
1227
['head', NULL_REVISION], ['ghost'], None),
1229
self.assertSeenAndResult(expected, search, search.next)
1230
self.assertRaises(StopIteration, search.next)
1231
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1232
result = search.get_result()
1233
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1234
result.get_recipe())
1235
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1236
# using next_with_ghosts:
1237
search = graph._make_breadth_first_searcher(['head'])
1238
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1239
self.assertRaises(StopIteration, search.next)
1240
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1241
result = search.get_result()
1242
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1243
result.get_recipe())
1244
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1247
class TestFindUniqueAncestors(TestGraphBase):
1249
def assertFindUniqueAncestors(self, graph, expected, node, common):
1250
actual = graph.find_unique_ancestors(node, common)
1251
self.assertEqual(expected, sorted(actual))
1253
def test_empty_set(self):
1254
graph = self.make_graph(ancestry_1)
1255
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1256
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1257
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1259
def test_single_node(self):
1260
graph = self.make_graph(ancestry_1)
1261
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1262
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1263
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1265
def test_minimal_ancestry(self):
1266
graph = self.make_breaking_graph(extended_history_shortcut,
1267
[NULL_REVISION, 'a', 'b'])
1268
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1270
graph = self.make_breaking_graph(extended_history_shortcut,
1272
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1274
graph = self.make_breaking_graph(complex_shortcut,
1276
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1277
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1278
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1279
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1281
def test_in_ancestry(self):
1282
graph = self.make_graph(ancestry_1)
1283
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1284
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1286
def test_multiple_revisions(self):
1287
graph = self.make_graph(ancestry_1)
1288
self.assertFindUniqueAncestors(graph,
1289
['rev4'], 'rev4', ['rev3', 'rev2b'])
1290
self.assertFindUniqueAncestors(graph,
1291
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1293
def test_complex_shortcut(self):
1294
graph = self.make_graph(complex_shortcut)
1295
self.assertFindUniqueAncestors(graph,
1296
['h', 'n'], 'n', ['m'])
1297
self.assertFindUniqueAncestors(graph,
1298
['e', 'i', 'm'], 'm', ['n'])
1300
def test_complex_shortcut2(self):
1301
graph = self.make_graph(complex_shortcut2)
1302
self.assertFindUniqueAncestors(graph,
1303
['j', 'u'], 'u', ['t'])
1304
self.assertFindUniqueAncestors(graph,
1307
def test_multiple_interesting_unique(self):
1308
graph = self.make_graph(multiple_interesting_unique)
1309
self.assertFindUniqueAncestors(graph,
1310
['j', 'y'], 'y', ['z'])
1311
self.assertFindUniqueAncestors(graph,
1312
['p', 'z'], 'z', ['y'])
1314
def test_racing_shortcuts(self):
1315
graph = self.make_graph(racing_shortcuts)
1316
self.assertFindUniqueAncestors(graph,
1317
['p', 'q', 'z'], 'z', ['y'])
1318
self.assertFindUniqueAncestors(graph,
1319
['h', 'i', 'j', 'y'], 'j', ['z'])
1322
class TestGraphFindDistanceToNull(TestGraphBase):
1323
"""Test an api that should be able to compute a revno"""
1325
def assertFindDistance(self, revno, graph, target_id, known_ids):
1326
"""Assert the output of Graph.find_distance_to_null()"""
1327
actual = graph.find_distance_to_null(target_id, known_ids)
1328
self.assertEqual(revno, actual)
1330
def test_nothing_known(self):
1331
graph = self.make_graph(ancestry_1)
1332
self.assertFindDistance(0, graph, NULL_REVISION, [])
1333
self.assertFindDistance(1, graph, 'rev1', [])
1334
self.assertFindDistance(2, graph, 'rev2a', [])
1335
self.assertFindDistance(2, graph, 'rev2b', [])
1336
self.assertFindDistance(3, graph, 'rev3', [])
1337
self.assertFindDistance(4, graph, 'rev4', [])
1339
def test_rev_is_ghost(self):
1340
graph = self.make_graph(ancestry_1)
1341
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1342
graph.find_distance_to_null, 'rev_missing', [])
1343
self.assertEqual('rev_missing', e.revision_id)
1344
self.assertEqual('rev_missing', e.ghost_revision_id)
1346
def test_ancestor_is_ghost(self):
1347
graph = self.make_graph({'rev':['parent']})
1348
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1349
graph.find_distance_to_null, 'rev', [])
1350
self.assertEqual('rev', e.revision_id)
1351
self.assertEqual('parent', e.ghost_revision_id)
1353
def test_known_in_ancestry(self):
1354
graph = self.make_graph(ancestry_1)
1355
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1356
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1358
def test_known_in_ancestry_limits(self):
1359
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1360
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1362
def test_target_is_ancestor(self):
1363
graph = self.make_graph(ancestry_1)
1364
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1366
def test_target_is_ancestor_limits(self):
1367
"""We shouldn't search all history if we run into ourselves"""
1368
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1369
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1371
def test_target_parallel_to_known_limits(self):
1372
# Even though the known revision isn't part of the other ancestry, they
1373
# eventually converge
1374
graph = self.make_breaking_graph(with_tail, ['a'])
1375
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1376
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1377
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1378
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1381
class TestFindMergeOrder(TestGraphBase):
1383
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1384
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1386
def test_parents(self):
1387
graph = self.make_graph(ancestry_1)
1388
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1390
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1393
def test_ancestors(self):
1394
graph = self.make_graph(ancestry_1)
1395
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1397
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1400
def test_shortcut_one_ancestor(self):
1401
# When we have enough info, we can stop searching
1402
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1403
# Single ancestors shortcut right away
1404
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1406
def test_shortcut_after_one_ancestor(self):
1407
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1408
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1411
class TestFindDescendants(TestGraphBase):
1413
def test_find_descendants_rev1_rev3(self):
1414
graph = self.make_graph(ancestry_1)
1415
descendants = graph.find_descendants('rev1', 'rev3')
1416
self.assertEqual(set(['rev1', 'rev2a', 'rev3']), descendants)
1418
def test_find_descendants_rev1_rev4(self):
1419
graph = self.make_graph(ancestry_1)
1420
descendants = graph.find_descendants('rev1', 'rev4')
1421
self.assertEqual(set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']),
1424
def test_find_descendants_rev2a_rev4(self):
1425
graph = self.make_graph(ancestry_1)
1426
descendants = graph.find_descendants('rev2a', 'rev4')
1427
self.assertEqual(set(['rev2a', 'rev3', 'rev4']), descendants)
1429
class TestFindLefthandMerger(TestGraphBase):
1431
def check_merger(self, result, ancestry, merged, tip):
1432
graph = self.make_graph(ancestry)
1433
self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
1435
def test_find_lefthand_merger_rev2b(self):
1436
self.check_merger('rev4', ancestry_1, 'rev2b', 'rev4')
1438
def test_find_lefthand_merger_rev2a(self):
1439
self.check_merger('rev2a', ancestry_1, 'rev2a', 'rev4')
1441
def test_find_lefthand_merger_rev4(self):
1442
self.check_merger(None, ancestry_1, 'rev4', 'rev2a')
1444
def test_find_lefthand_merger_f(self):
1445
self.check_merger('i', complex_shortcut, 'f', 'm')
1447
def test_find_lefthand_merger_g(self):
1448
self.check_merger('i', complex_shortcut, 'g', 'm')
1450
def test_find_lefthand_merger_h(self):
1451
self.check_merger('n', complex_shortcut, 'h', 'n')
1454
class TestGetChildMap(TestGraphBase):
1456
def test_get_child_map(self):
1457
graph = self.make_graph(ancestry_1)
1458
child_map = graph.get_child_map(['rev4', 'rev3', 'rev2a', 'rev2b'])
1459
self.assertEqual({'rev1': ['rev2a', 'rev2b'],
1466
class TestCachingParentsProvider(tests.TestCase):
1467
"""These tests run with:
1469
self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1471
self.caching_pp, a CachingParentsProvider layered on inst_pp.
1475
super(TestCachingParentsProvider, self).setUp()
1476
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1477
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1478
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1480
def test_get_parent_map(self):
1481
"""Requesting the same revision should be returned from cache"""
1482
self.assertEqual({}, self.caching_pp._cache)
1483
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1484
self.assertEqual(['a'], self.inst_pp.calls)
1485
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1486
# No new call, as it should have been returned from the cache
1487
self.assertEqual(['a'], self.inst_pp.calls)
1488
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1490
def test_get_parent_map_not_present(self):
1491
"""The cache should also track when a revision doesn't exist"""
1492
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1493
self.assertEqual(['b'], self.inst_pp.calls)
1494
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1496
self.assertEqual(['b'], self.inst_pp.calls)
1498
def test_get_parent_map_mixed(self):
1499
"""Anything that can be returned from cache, should be"""
1500
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1501
self.assertEqual(['b'], self.inst_pp.calls)
1502
self.assertEqual({'a':('b',)},
1503
self.caching_pp.get_parent_map(['a', 'b']))
1504
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1506
def test_get_parent_map_repeated(self):
1507
"""Asking for the same parent 2x will only forward 1 request."""
1508
self.assertEqual({'a':('b',)},
1509
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1510
# Use sorted because we don't care about the order, just that each is
1511
# only present 1 time.
1512
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1514
def test_note_missing_key(self):
1515
"""After noting that a key is missing it is cached."""
1516
self.caching_pp.note_missing_key('b')
1517
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1518
self.assertEqual([], self.inst_pp.calls)
1519
self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1522
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1523
"""Test the behaviour when parents are provided that were not requested."""
1526
super(TestCachingParentsProviderExtras, self).setUp()
1527
class ExtraParentsProvider(object):
1529
def get_parent_map(self, keys):
1530
return {'rev1': [], 'rev2': ['rev1',]}
1532
self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1533
self.caching_pp = _mod_graph.CachingParentsProvider(
1534
get_parent_map=self.inst_pp.get_parent_map)
1536
def test_uncached(self):
1537
self.caching_pp.disable_cache()
1538
self.assertEqual({'rev1': []},
1539
self.caching_pp.get_parent_map(['rev1']))
1540
self.assertEqual(['rev1'], self.inst_pp.calls)
1541
self.assertIs(None, self.caching_pp._cache)
1543
def test_cache_initially_empty(self):
1544
self.assertEqual({}, self.caching_pp._cache)
1546
def test_cached(self):
1547
self.assertEqual({'rev1': []},
1548
self.caching_pp.get_parent_map(['rev1']))
1549
self.assertEqual(['rev1'], self.inst_pp.calls)
1550
self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1551
self.caching_pp._cache)
1552
self.assertEqual({'rev1': []},
1553
self.caching_pp.get_parent_map(['rev1']))
1554
self.assertEqual(['rev1'], self.inst_pp.calls)
1556
def test_disable_cache_clears_cache(self):
1557
# Put something in the cache
1558
self.caching_pp.get_parent_map(['rev1'])
1559
self.assertEqual(2, len(self.caching_pp._cache))
1560
self.caching_pp.disable_cache()
1561
self.assertIs(None, self.caching_pp._cache)
1563
def test_enable_cache_raises(self):
1564
e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1565
self.assertEqual('Cache enabled when already enabled.', str(e))
1567
def test_cache_misses(self):
1568
self.caching_pp.get_parent_map(['rev3'])
1569
self.caching_pp.get_parent_map(['rev3'])
1570
self.assertEqual(['rev3'], self.inst_pp.calls)
1572
def test_no_cache_misses(self):
1573
self.caching_pp.disable_cache()
1574
self.caching_pp.enable_cache(cache_misses=False)
1575
self.caching_pp.get_parent_map(['rev3'])
1576
self.caching_pp.get_parent_map(['rev3'])
1577
self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1579
def test_cache_extras(self):
1580
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1581
self.assertEqual({'rev2': ['rev1']},
1582
self.caching_pp.get_parent_map(['rev2']))
1583
self.assertEqual(['rev3'], self.inst_pp.calls)
1586
class TestCollapseLinearRegions(tests.TestCase):
1588
def assertCollapsed(self, collapsed, original):
1589
self.assertEqual(collapsed,
1590
_mod_graph.collapse_linear_regions(original))
1592
def test_collapse_nothing(self):
1593
d = {1:[2, 3], 2:[], 3:[]}
1594
self.assertCollapsed(d, d)
1595
d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1596
self.assertCollapsed(d, d)
1598
def test_collapse_chain(self):
1599
# Any time we have a linear chain, we should be able to collapse
1600
d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1601
self.assertCollapsed({1:[5], 5:[]}, d)
1602
d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1603
self.assertCollapsed({5:[1], 1:[]}, d)
1604
d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1605
self.assertCollapsed({5:[2], 2:[]}, d)
1607
def test_collapse_with_multiple_children(self):
1618
# 4 and 5 cannot be removed because 6 has 2 children
1619
# 2 and 3 cannot be removed because 1 has 2 parents
1620
d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1621
self.assertCollapsed(d, d)
1624
class TestGraphThunkIdsToKeys(tests.TestCase):
1626
def test_heads(self):
1632
d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1633
('B',): [('A',)], ('A',): []}
1634
g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1635
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1636
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
1637
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
1638
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1639
self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1641
def test_add_node(self):
1642
d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1643
g = _mod_graph.KnownGraph(d)
1644
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1645
graph_thunk.add_node("D", ["A", "C"])
1646
self.assertEqual(['B', 'D'],
1647
sorted(graph_thunk.heads(['D', 'B', 'A'])))
1649
def test_merge_sort(self):
1650
d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1651
g = _mod_graph.KnownGraph(d)
1652
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1653
graph_thunk.add_node("D", ["A", "C"])
1654
self.assertEqual([('C', 0, (2,), False), ('A', 0, (1,), True)],
1655
[(n.key, n.merge_depth, n.revno, n.end_of_merge)
1656
for n in graph_thunk.merge_sort('C')])
1659
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1660
"""Tests for bzrlib.graph.PendingAncestryResult."""
1662
def test_get_keys(self):
1663
builder = self.make_branch_builder('b')
1664
builder.start_series()
1665
builder.build_snapshot('rev-1', None, [
1666
('add', ('', 'root-id', 'directory', ''))])
1667
builder.build_snapshot('rev-2', ['rev-1'], [])
1668
builder.finish_series()
1669
repo = builder.get_branch().repository
1671
self.addCleanup(repo.unlock)
1672
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1673
self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1675
def test_get_keys_excludes_ghosts(self):
1676
builder = self.make_branch_builder('b')
1677
builder.start_series()
1678
builder.build_snapshot('rev-1', None, [
1679
('add', ('', 'root-id', 'directory', ''))])
1680
builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
1681
builder.finish_series()
1682
repo = builder.get_branch().repository
1684
self.addCleanup(repo.unlock)
1685
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1686
self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
1688
def test_get_keys_excludes_null(self):
1689
# Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1690
# somewhere other than the last element, which can happen in real
1692
class StubGraph(object):
1693
def iter_ancestry(self, keys):
1694
return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1695
result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1696
result_keys = result._get_keys(StubGraph())
1697
# Only the non-null keys from the ancestry appear.
1698
self.assertEqual(set(['foo']), set(result_keys))
1701
class TestPendingAncestryResultRefine(TestGraphBase):
1703
def test_refine(self):
1704
# Used when pulling from a stacked repository, so test some revisions
1705
# being satisfied from the stacking branch.
1706
g = self.make_graph(
1707
{"tip":["mid"], "mid":["base"], "tag":["base"],
1708
"base":[NULL_REVISION], NULL_REVISION:[]})
1709
result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1710
result = result.refine(set(['tip']), set(['mid']))
1711
self.assertEqual(set(['mid', 'tag']), result.heads)
1712
result = result.refine(set(['mid', 'tag', 'base']),
1713
set([NULL_REVISION]))
1714
self.assertEqual(set([NULL_REVISION]), result.heads)
1715
self.assertTrue(result.is_empty())
1718
class TestSearchResultRefine(TestGraphBase):
1720
def test_refine(self):
1721
# Used when pulling from a stacked repository, so test some revisions
1722
# being satisfied from the stacking branch.
1723
g = self.make_graph(
1724
{"tip":["mid"], "mid":["base"], "tag":["base"],
1725
"base":[NULL_REVISION], NULL_REVISION:[]})
1726
result = _mod_graph.SearchResult(set(['tip', 'tag']),
1727
set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1728
result = result.refine(set(['tip']), set(['mid']))
1729
recipe = result.get_recipe()
1730
# We should be starting from tag (original head) and mid (seen ref)
1731
self.assertEqual(set(['mid', 'tag']), recipe[1])
1732
# We should be stopping at NULL (original stop) and tip (seen head)
1733
self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1734
self.assertEqual(3, recipe[3])
1735
result = result.refine(set(['mid', 'tag', 'base']),
1736
set([NULL_REVISION]))
1737
recipe = result.get_recipe()
1738
# We should be starting from nothing (NULL was known as a cut point)
1739
self.assertEqual(set([]), recipe[1])
1740
# We should be stopping at NULL (original stop) and tip (seen head) and
1741
# tag (seen head) and mid(seen mid-point head). We could come back and
1742
# define this as not including mid, for minimal results, but it is
1743
# still 'correct' to include mid, and simpler/easier.
1744
self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1745
self.assertEqual(0, recipe[3])
1746
self.assertTrue(result.is_empty())
added
removed
bzrlib/tests/test_graph.py
