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
427
get_cached = getattr(parents_provider, 'get_cached_parent_map', None)
428
if get_cached is not None:
429
# Only expose the underlying 'get_cached_parent_map' function if
430
# the wrapped provider has it.
431
self.get_cached_parent_map = self._get_cached_parent_map
433
def get_parent_map(self, nodes):
434
self.calls.extend(nodes)
435
return self._real_parents_provider.get_parent_map(nodes)
437
def _get_cached_parent_map(self, nodes):
438
self.calls.append(('cached', sorted(nodes)))
439
return self._real_parents_provider.get_cached_parent_map(nodes)
442
class SharedInstrumentedParentsProvider(object):
444
def __init__(self, parents_provider, calls, info):
447
self._real_parents_provider = parents_provider
448
get_cached = getattr(parents_provider, 'get_cached_parent_map', None)
449
if get_cached is not None:
450
# Only expose the underlying 'get_cached_parent_map' function if
451
# the wrapped provider has it.
452
self.get_cached_parent_map = self._get_cached_parent_map
454
def get_parent_map(self, nodes):
455
self.calls.append((self.info, sorted(nodes)))
456
return self._real_parents_provider.get_parent_map(nodes)
458
def _get_cached_parent_map(self, nodes):
459
self.calls.append((self.info, 'cached', sorted(nodes)))
460
return self._real_parents_provider.get_cached_parent_map(nodes)
463
class TestGraphBase(tests.TestCase):
465
def make_graph(self, ancestors):
466
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
468
def make_breaking_graph(self, ancestors, break_on):
469
"""Make a Graph that raises an exception if we hit a node."""
470
g = self.make_graph(ancestors)
471
orig_parent_map = g.get_parent_map
472
def get_parent_map(keys):
473
bad_keys = set(keys).intersection(break_on)
475
self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
476
return orig_parent_map(keys)
477
g.get_parent_map = get_parent_map
481
class TestGraph(TestCaseWithMemoryTransport):
483
def make_graph(self, ancestors):
484
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
486
def prepare_memory_tree(self, location):
487
tree = self.make_branch_and_memory_tree(location)
492
def build_ancestry(self, tree, ancestors):
493
"""Create an ancestry as specified by a graph dict
495
:param tree: A tree to use
496
:param ancestors: a dict of {node: [node_parent, ...]}
498
pending = [NULL_REVISION]
500
for descendant, parents in ancestors.iteritems():
501
for parent in parents:
502
descendants.setdefault(parent, []).append(descendant)
503
while len(pending) > 0:
504
cur_node = pending.pop()
505
for descendant in descendants.get(cur_node, []):
506
if tree.branch.repository.has_revision(descendant):
508
parents = [p for p in ancestors[descendant] if p is not
510
if len([p for p in parents if not
511
tree.branch.repository.has_revision(p)]) > 0:
513
tree.set_parent_ids(parents)
515
left_parent = parents[0]
517
left_parent = NULL_REVISION
518
tree.branch.set_last_revision_info(
519
len(tree.branch._lefthand_history(left_parent)),
521
tree.commit(descendant, rev_id=descendant)
522
pending.append(descendant)
525
"""Test finding least common ancestor.
527
ancestry_1 should always have a single common ancestor
529
graph = self.make_graph(ancestry_1)
530
self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
531
self.assertEqual(set([NULL_REVISION]),
532
graph.find_lca(NULL_REVISION, NULL_REVISION))
533
self.assertEqual(set([NULL_REVISION]),
534
graph.find_lca(NULL_REVISION, 'rev1'))
535
self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
536
self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
538
def test_no_unique_lca(self):
539
"""Test error when one revision is not in the graph"""
540
graph = self.make_graph(ancestry_1)
541
self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
544
def test_lca_criss_cross(self):
545
"""Test least-common-ancestor after a criss-cross merge."""
546
graph = self.make_graph(criss_cross)
547
self.assertEqual(set(['rev2a', 'rev2b']),
548
graph.find_lca('rev3a', 'rev3b'))
549
self.assertEqual(set(['rev2b']),
550
graph.find_lca('rev3a', 'rev3b', 'rev2b'))
552
def test_lca_shortcut(self):
553
"""Test least-common ancestor on this history shortcut"""
554
graph = self.make_graph(history_shortcut)
555
self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
557
def test_lefthand_distance_smoke(self):
558
"""A simple does it work test for graph.lefthand_distance(keys)."""
559
graph = self.make_graph(history_shortcut)
560
distance_graph = graph.find_lefthand_distances(['rev3b', 'rev2a'])
561
self.assertEqual({'rev2a': 2, 'rev3b': 3}, distance_graph)
563
def test_lefthand_distance_ghosts(self):
564
"""A simple does it work test for graph.lefthand_distance(keys)."""
565
nodes = {'nonghost':[NULL_REVISION], 'toghost':['ghost']}
566
graph = self.make_graph(nodes)
567
distance_graph = graph.find_lefthand_distances(['nonghost', 'toghost'])
568
self.assertEqual({'nonghost': 1, 'toghost': -1}, distance_graph)
570
def test_recursive_unique_lca(self):
571
"""Test finding a unique least common ancestor.
573
ancestry_1 should always have a single common ancestor
575
graph = self.make_graph(ancestry_1)
576
self.assertEqual(NULL_REVISION,
577
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
578
self.assertEqual(NULL_REVISION,
579
graph.find_unique_lca(NULL_REVISION, 'rev1'))
580
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
581
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
582
self.assertEqual(('rev1', 1,),
583
graph.find_unique_lca('rev2a', 'rev2b',
586
def assertRemoveDescendants(self, expected, graph, revisions):
587
parents = graph.get_parent_map(revisions)
588
self.assertEqual(expected,
589
graph._remove_simple_descendants(revisions, parents))
591
def test__remove_simple_descendants(self):
592
graph = self.make_graph(ancestry_1)
593
self.assertRemoveDescendants(set(['rev1']), graph,
594
set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']))
596
def test__remove_simple_descendants_disjoint(self):
597
graph = self.make_graph(ancestry_1)
598
self.assertRemoveDescendants(set(['rev1', 'rev3']), graph,
599
set(['rev1', 'rev3']))
601
def test__remove_simple_descendants_chain(self):
602
graph = self.make_graph(ancestry_1)
603
self.assertRemoveDescendants(set(['rev1']), graph,
604
set(['rev1', 'rev2a', 'rev3']))
606
def test__remove_simple_descendants_siblings(self):
607
graph = self.make_graph(ancestry_1)
608
self.assertRemoveDescendants(set(['rev2a', 'rev2b']), graph,
609
set(['rev2a', 'rev2b', 'rev3']))
611
def test_unique_lca_criss_cross(self):
612
"""Ensure we don't pick non-unique lcas in a criss-cross"""
613
graph = self.make_graph(criss_cross)
614
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
615
lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
616
self.assertEqual('rev1', lca)
617
self.assertEqual(2, steps)
619
def test_unique_lca_null_revision(self):
620
"""Ensure we pick NULL_REVISION when necessary"""
621
graph = self.make_graph(criss_cross2)
622
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
623
self.assertEqual(NULL_REVISION,
624
graph.find_unique_lca('rev2a', 'rev2b'))
626
def test_unique_lca_null_revision2(self):
627
"""Ensure we pick NULL_REVISION when necessary"""
628
graph = self.make_graph(ancestry_2)
629
self.assertEqual(NULL_REVISION,
630
graph.find_unique_lca('rev4a', 'rev1b'))
632
def test_lca_double_shortcut(self):
633
graph = self.make_graph(double_shortcut)
634
self.assertEqual('c', graph.find_unique_lca('f', 'g'))
636
def test_common_ancestor_two_repos(self):
637
"""Ensure we do unique_lca using data from two repos"""
638
mainline_tree = self.prepare_memory_tree('mainline')
639
self.build_ancestry(mainline_tree, mainline)
640
self.addCleanup(mainline_tree.unlock)
642
# This is cheating, because the revisions in the graph are actually
643
# different revisions, despite having the same revision-id.
644
feature_tree = self.prepare_memory_tree('feature')
645
self.build_ancestry(feature_tree, feature_branch)
646
self.addCleanup(feature_tree.unlock)
648
graph = mainline_tree.branch.repository.get_graph(
649
feature_tree.branch.repository)
650
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
652
def test_graph_difference(self):
653
graph = self.make_graph(ancestry_1)
654
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
655
self.assertEqual((set(), set(['rev1'])),
656
graph.find_difference(NULL_REVISION, 'rev1'))
657
self.assertEqual((set(['rev1']), set()),
658
graph.find_difference('rev1', NULL_REVISION))
659
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
660
graph.find_difference('rev3', 'rev2b'))
661
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
662
graph.find_difference('rev4', 'rev2b'))
664
def test_graph_difference_separate_ancestry(self):
665
graph = self.make_graph(ancestry_2)
666
self.assertEqual((set(['rev1a']), set(['rev1b'])),
667
graph.find_difference('rev1a', 'rev1b'))
668
self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
670
graph.find_difference('rev4a', 'rev1b'))
672
def test_graph_difference_criss_cross(self):
673
graph = self.make_graph(criss_cross)
674
self.assertEqual((set(['rev3a']), set(['rev3b'])),
675
graph.find_difference('rev3a', 'rev3b'))
676
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
677
graph.find_difference('rev2a', 'rev3b'))
679
def test_graph_difference_extended_history(self):
680
graph = self.make_graph(extended_history_shortcut)
681
self.assertEqual((set(['e']), set(['f'])),
682
graph.find_difference('e', 'f'))
683
self.assertEqual((set(['f']), set(['e'])),
684
graph.find_difference('f', 'e'))
686
def test_graph_difference_double_shortcut(self):
687
graph = self.make_graph(double_shortcut)
688
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
689
graph.find_difference('f', 'g'))
691
def test_graph_difference_complex_shortcut(self):
692
graph = self.make_graph(complex_shortcut)
693
self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
694
graph.find_difference('m', 'n'))
696
def test_graph_difference_complex_shortcut2(self):
697
graph = self.make_graph(complex_shortcut2)
698
self.assertEqual((set(['t']), set(['j', 'u'])),
699
graph.find_difference('t', 'u'))
701
def test_graph_difference_shortcut_extra_root(self):
702
graph = self.make_graph(shortcut_extra_root)
703
self.assertEqual((set(['e']), set(['f', 'g'])),
704
graph.find_difference('e', 'f'))
706
def test_iter_topo_order(self):
707
graph = self.make_graph(ancestry_1)
708
args = ['rev2a', 'rev3', 'rev1']
709
topo_args = list(graph.iter_topo_order(args))
710
self.assertEqual(set(args), set(topo_args))
711
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
712
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
714
def test_is_ancestor(self):
715
graph = self.make_graph(ancestry_1)
716
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
717
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
718
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
719
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
720
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
721
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
722
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
723
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
724
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
725
instrumented_provider = InstrumentedParentsProvider(graph)
726
instrumented_graph = _mod_graph.Graph(instrumented_provider)
727
instrumented_graph.is_ancestor('rev2a', 'rev2b')
728
self.assertTrue('null:' not in instrumented_provider.calls)
730
def test_is_between(self):
731
graph = self.make_graph(ancestry_1)
732
self.assertEqual(True, graph.is_between('null:', 'null:', 'null:'))
733
self.assertEqual(True, graph.is_between('rev1', 'null:', 'rev1'))
734
self.assertEqual(True, graph.is_between('rev1', 'rev1', 'rev4'))
735
self.assertEqual(True, graph.is_between('rev4', 'rev1', 'rev4'))
736
self.assertEqual(True, graph.is_between('rev3', 'rev1', 'rev4'))
737
self.assertEqual(False, graph.is_between('rev4', 'rev1', 'rev3'))
738
self.assertEqual(False, graph.is_between('rev1', 'rev2a', 'rev4'))
739
self.assertEqual(False, graph.is_between('null:', 'rev1', 'rev4'))
741
def test_is_ancestor_boundary(self):
742
"""Ensure that we avoid searching the whole graph.
744
This requires searching through b as a common ancestor, so we
745
can identify that e is common.
747
graph = self.make_graph(boundary)
748
instrumented_provider = InstrumentedParentsProvider(graph)
749
graph = _mod_graph.Graph(instrumented_provider)
750
self.assertFalse(graph.is_ancestor('a', 'c'))
751
self.assertTrue('null:' not in instrumented_provider.calls)
753
def test_iter_ancestry(self):
754
nodes = boundary.copy()
755
nodes[NULL_REVISION] = ()
756
graph = self.make_graph(nodes)
757
expected = nodes.copy()
758
expected.pop('a') # 'a' is not in the ancestry of 'c', all the
760
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
761
self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
763
def test_iter_ancestry_with_ghost(self):
764
graph = self.make_graph(with_ghost)
765
expected = with_ghost.copy()
766
# 'a' is not in the ancestry of 'c', and 'g' is a ghost
768
self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
770
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
772
def test_filter_candidate_lca(self):
773
"""Test filter_candidate_lca for a corner case
775
This tests the case where we encounter the end of iteration for 'e'
776
in the same pass as we discover that 'd' is an ancestor of 'e', and
777
therefore 'e' can't be an lca.
779
To compensate for different dict orderings on other Python
780
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
782
# This test is sensitive to the iteration order of dicts. It will
783
# pass incorrectly if 'e' and 'a' sort before 'c'
792
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
793
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
794
self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
796
def test_heads_null(self):
797
graph = self.make_graph(ancestry_1)
798
self.assertEqual(set(['null:']), graph.heads(['null:']))
799
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
800
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
801
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
802
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
804
def test_heads_one(self):
805
# A single node will always be a head
806
graph = self.make_graph(ancestry_1)
807
self.assertEqual(set(['null:']), graph.heads(['null:']))
808
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
809
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
810
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
811
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
812
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
814
def test_heads_single(self):
815
graph = self.make_graph(ancestry_1)
816
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
817
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
818
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
819
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
820
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
821
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
822
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
823
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
825
def test_heads_two_heads(self):
826
graph = self.make_graph(ancestry_1)
827
self.assertEqual(set(['rev2a', 'rev2b']),
828
graph.heads(['rev2a', 'rev2b']))
829
self.assertEqual(set(['rev3', 'rev2b']),
830
graph.heads(['rev3', 'rev2b']))
832
def test_heads_criss_cross(self):
833
graph = self.make_graph(criss_cross)
834
self.assertEqual(set(['rev2a']),
835
graph.heads(['rev2a', 'rev1']))
836
self.assertEqual(set(['rev2b']),
837
graph.heads(['rev2b', 'rev1']))
838
self.assertEqual(set(['rev3a']),
839
graph.heads(['rev3a', 'rev1']))
840
self.assertEqual(set(['rev3b']),
841
graph.heads(['rev3b', 'rev1']))
842
self.assertEqual(set(['rev2a', 'rev2b']),
843
graph.heads(['rev2a', 'rev2b']))
844
self.assertEqual(set(['rev3a']),
845
graph.heads(['rev3a', 'rev2a']))
846
self.assertEqual(set(['rev3a']),
847
graph.heads(['rev3a', 'rev2b']))
848
self.assertEqual(set(['rev3a']),
849
graph.heads(['rev3a', 'rev2a', 'rev2b']))
850
self.assertEqual(set(['rev3b']),
851
graph.heads(['rev3b', 'rev2a']))
852
self.assertEqual(set(['rev3b']),
853
graph.heads(['rev3b', 'rev2b']))
854
self.assertEqual(set(['rev3b']),
855
graph.heads(['rev3b', 'rev2a', 'rev2b']))
856
self.assertEqual(set(['rev3a', 'rev3b']),
857
graph.heads(['rev3a', 'rev3b']))
858
self.assertEqual(set(['rev3a', 'rev3b']),
859
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
861
def test_heads_shortcut(self):
862
graph = self.make_graph(history_shortcut)
864
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
865
graph.heads(['rev2a', 'rev2b', 'rev2c']))
866
self.assertEqual(set(['rev3a', 'rev3b']),
867
graph.heads(['rev3a', 'rev3b']))
868
self.assertEqual(set(['rev3a', 'rev3b']),
869
graph.heads(['rev2a', 'rev3a', 'rev3b']))
870
self.assertEqual(set(['rev2a', 'rev3b']),
871
graph.heads(['rev2a', 'rev3b']))
872
self.assertEqual(set(['rev2c', 'rev3a']),
873
graph.heads(['rev2c', 'rev3a']))
875
def _run_heads_break_deeper(self, graph_dict, search):
876
"""Run heads on a graph-as-a-dict.
878
If the search asks for the parents of 'deeper' the test will fail.
882
def get_parent_map(keys):
886
self.fail('key deeper was accessed')
887
result[key] = graph_dict[key]
890
an_obj.get_parent_map = get_parent_map
891
graph = _mod_graph.Graph(an_obj)
892
return graph.heads(search)
894
def test_heads_limits_search(self):
895
# test that a heads query does not search all of history
901
self.assertEqual(set(['left', 'right']),
902
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
904
def test_heads_limits_search_assymetric(self):
905
# test that a heads query does not search all of history
908
'midleft':['common'],
910
'common':['aftercommon'],
911
'aftercommon':['deeper'],
913
self.assertEqual(set(['left', 'right']),
914
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
916
def test_heads_limits_search_common_search_must_continue(self):
917
# test that common nodes are still queried, preventing
918
# all-the-way-to-origin behaviour in the following graph:
920
'h1':['shortcut', 'common1'],
922
'shortcut':['common2'],
923
'common1':['common2'],
924
'common2':['deeper'],
926
self.assertEqual(set(['h1', 'h2']),
927
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
929
def test_breadth_first_search_start_ghosts(self):
930
graph = self.make_graph({})
931
# with_ghosts reports the ghosts
932
search = graph._make_breadth_first_searcher(['a-ghost'])
933
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
934
self.assertRaises(StopIteration, search.next_with_ghosts)
936
search = graph._make_breadth_first_searcher(['a-ghost'])
937
self.assertEqual(set(['a-ghost']), search.next())
938
self.assertRaises(StopIteration, search.next)
940
def test_breadth_first_search_deep_ghosts(self):
941
graph = self.make_graph({
943
'present':['child', 'ghost'],
946
# with_ghosts reports the ghosts
947
search = graph._make_breadth_first_searcher(['head'])
948
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
949
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
950
self.assertEqual((set(['child']), set(['ghost'])),
951
search.next_with_ghosts())
952
self.assertRaises(StopIteration, search.next_with_ghosts)
954
search = graph._make_breadth_first_searcher(['head'])
955
self.assertEqual(set(['head']), search.next())
956
self.assertEqual(set(['present']), search.next())
957
self.assertEqual(set(['child', 'ghost']),
959
self.assertRaises(StopIteration, search.next)
961
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
962
# To make the API robust, we allow calling both next() and
963
# next_with_ghosts() on the same searcher.
964
graph = self.make_graph({
966
'present':['child', 'ghost'],
969
# start with next_with_ghosts
970
search = graph._make_breadth_first_searcher(['head'])
971
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
972
self.assertEqual(set(['present']), search.next())
973
self.assertEqual((set(['child']), set(['ghost'])),
974
search.next_with_ghosts())
975
self.assertRaises(StopIteration, search.next)
977
search = graph._make_breadth_first_searcher(['head'])
978
self.assertEqual(set(['head']), search.next())
979
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
980
self.assertEqual(set(['child', 'ghost']),
982
self.assertRaises(StopIteration, search.next_with_ghosts)
984
def test_breadth_first_change_search(self):
985
# Changing the search should work with both next and next_with_ghosts.
986
graph = self.make_graph({
988
'present':['stopped'],
992
search = graph._make_breadth_first_searcher(['head'])
993
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
994
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
995
self.assertEqual(set(['present']),
996
search.stop_searching_any(['present']))
997
self.assertEqual((set(['other']), set(['other_ghost'])),
998
search.start_searching(['other', 'other_ghost']))
999
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
1000
self.assertRaises(StopIteration, search.next_with_ghosts)
1001
# next includes them
1002
search = graph._make_breadth_first_searcher(['head'])
1003
self.assertEqual(set(['head']), search.next())
1004
self.assertEqual(set(['present']), search.next())
1005
self.assertEqual(set(['present']),
1006
search.stop_searching_any(['present']))
1007
search.start_searching(['other', 'other_ghost'])
1008
self.assertEqual(set(['other_2']), search.next())
1009
self.assertRaises(StopIteration, search.next)
1011
def assertSeenAndResult(self, instructions, search, next):
1012
"""Check the results of .seen and get_result() for a seach.
1014
:param instructions: A list of tuples:
1015
(seen, recipe, included_keys, starts, stops).
1016
seen, recipe and included_keys are results to check on the search
1017
and the searches get_result(). starts and stops are parameters to
1018
pass to start_searching and stop_searching_any during each
1019
iteration, if they are not None.
1020
:param search: The search to use.
1021
:param next: A callable to advance the search.
1023
for seen, recipe, included_keys, starts, stops in instructions:
1024
# Adjust for recipe contract changes that don't vary for all the
1026
recipe = ('search',) + recipe
1028
if starts is not None:
1029
search.start_searching(starts)
1030
if stops is not None:
1031
search.stop_searching_any(stops)
1032
result = search.get_result()
1033
self.assertEqual(recipe, result.get_recipe())
1034
self.assertEqual(set(included_keys), result.get_keys())
1035
self.assertEqual(seen, search.seen)
1037
def test_breadth_first_get_result_excludes_current_pending(self):
1038
graph = self.make_graph({
1040
'child':[NULL_REVISION],
1043
search = graph._make_breadth_first_searcher(['head'])
1044
# At the start, nothing has been seen, to its all excluded:
1045
result = search.get_result()
1046
self.assertEqual(('search', set(['head']), set(['head']), 0),
1047
result.get_recipe())
1048
self.assertEqual(set(), result.get_keys())
1049
self.assertEqual(set(), search.seen)
1052
(set(['head']), (set(['head']), set(['child']), 1),
1053
['head'], None, None),
1054
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
1055
['head', 'child'], None, None),
1056
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
1057
['head', 'child', NULL_REVISION], None, None),
1059
self.assertSeenAndResult(expected, search, search.next)
1060
# using next_with_ghosts:
1061
search = graph._make_breadth_first_searcher(['head'])
1062
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1064
def test_breadth_first_get_result_starts_stops(self):
1065
graph = self.make_graph({
1067
'child':[NULL_REVISION],
1068
'otherhead':['otherchild'],
1069
'otherchild':['excluded'],
1070
'excluded':[NULL_REVISION],
1073
search = graph._make_breadth_first_searcher([])
1074
# Starting with nothing and adding a search works:
1075
search.start_searching(['head'])
1076
# head has been seen:
1077
result = search.get_result()
1078
self.assertEqual(('search', set(['head']), set(['child']), 1),
1079
result.get_recipe())
1080
self.assertEqual(set(['head']), result.get_keys())
1081
self.assertEqual(set(['head']), search.seen)
1084
# stop at child, and start a new search at otherhead:
1085
# - otherhead counts as seen immediately when start_searching is
1087
(set(['head', 'child', 'otherhead']),
1088
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1089
['head', 'otherhead'], ['otherhead'], ['child']),
1090
(set(['head', 'child', 'otherhead', 'otherchild']),
1091
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1092
['head', 'otherhead', 'otherchild'], None, None),
1093
# stop searching excluded now
1094
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1095
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1096
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1098
self.assertSeenAndResult(expected, search, search.next)
1099
# using next_with_ghosts:
1100
search = graph._make_breadth_first_searcher([])
1101
search.start_searching(['head'])
1102
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1104
def test_breadth_first_stop_searching_not_queried(self):
1105
# A client should be able to say 'stop node X' even if X has not been
1106
# returned to the client.
1107
graph = self.make_graph({
1108
'head':['child', 'ghost1'],
1109
'child':[NULL_REVISION],
1112
search = graph._make_breadth_first_searcher(['head'])
1114
# NULL_REVISION and ghost1 have not been returned
1116
(set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1117
['head'], None, [NULL_REVISION, 'ghost1']),
1118
# ghost1 has been returned, NULL_REVISION is to be returned in the
1120
(set(['head', 'child', 'ghost1']),
1121
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1122
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1124
self.assertSeenAndResult(expected, search, search.next)
1125
# using next_with_ghosts:
1126
search = graph._make_breadth_first_searcher(['head'])
1127
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1129
def test_breadth_first_stop_searching_late(self):
1130
# A client should be able to say 'stop node X' and have it excluded
1131
# from the result even if X was seen in an older iteration of the
1133
graph = self.make_graph({
1136
'child':[NULL_REVISION],
1139
search = graph._make_breadth_first_searcher(['head'])
1141
(set(['head']), (set(['head']), set(['middle']), 1),
1142
['head'], None, None),
1143
(set(['head', 'middle']), (set(['head']), set(['child']), 2),
1144
['head', 'middle'], None, None),
1145
# 'middle' came from the previous iteration, but we don't stop
1146
# searching it until *after* advancing the searcher.
1147
(set(['head', 'middle', 'child']),
1148
(set(['head']), set(['middle', 'child']), 1),
1149
['head'], None, ['middle', 'child']),
1151
self.assertSeenAndResult(expected, search, search.next)
1152
# using next_with_ghosts:
1153
search = graph._make_breadth_first_searcher(['head'])
1154
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1156
def test_breadth_first_get_result_ghosts_are_excluded(self):
1157
graph = self.make_graph({
1158
'head':['child', 'ghost'],
1159
'child':[NULL_REVISION],
1162
search = graph._make_breadth_first_searcher(['head'])
1166
(set(['head']), set(['ghost', 'child']), 1),
1167
['head'], None, None),
1168
(set(['head', 'child', 'ghost']),
1169
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1170
['head', 'child'], None, None),
1172
self.assertSeenAndResult(expected, search, search.next)
1173
# using next_with_ghosts:
1174
search = graph._make_breadth_first_searcher(['head'])
1175
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1177
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1178
graph = self.make_graph({
1180
'child':[NULL_REVISION],
1183
search = graph._make_breadth_first_searcher(['head'])
1186
(set(['head', 'ghost']),
1187
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1188
['head'], ['ghost'], None),
1189
(set(['head', 'child', 'ghost']),
1190
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1191
['head', 'child'], None, None),
1193
self.assertSeenAndResult(expected, search, search.next)
1194
# using next_with_ghosts:
1195
search = graph._make_breadth_first_searcher(['head'])
1196
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1198
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1199
graph = self.make_graph({
1200
'head':[NULL_REVISION],
1203
search = graph._make_breadth_first_searcher(['head'])
1207
(set(['head']), set([NULL_REVISION]), 1),
1208
['head'], None, None),
1209
(set(['head', NULL_REVISION]),
1210
(set(['head']), set([]), 2),
1211
['head', NULL_REVISION], None, None),
1213
self.assertSeenAndResult(expected, search, search.next)
1214
# using next_with_ghosts:
1215
search = graph._make_breadth_first_searcher(['head'])
1216
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1218
def test_breadth_first_search_get_result_after_StopIteration(self):
1219
# StopIteration should not invalid anything..
1220
graph = self.make_graph({
1221
'head':[NULL_REVISION],
1224
search = graph._make_breadth_first_searcher(['head'])
1228
(set(['head']), set([NULL_REVISION]), 1),
1229
['head'], None, None),
1230
(set(['head', 'ghost', NULL_REVISION]),
1231
(set(['head', 'ghost']), set(['ghost']), 2),
1232
['head', NULL_REVISION], ['ghost'], None),
1234
self.assertSeenAndResult(expected, search, search.next)
1235
self.assertRaises(StopIteration, search.next)
1236
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1237
result = search.get_result()
1238
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1239
result.get_recipe())
1240
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1241
# using next_with_ghosts:
1242
search = graph._make_breadth_first_searcher(['head'])
1243
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1244
self.assertRaises(StopIteration, search.next)
1245
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1246
result = search.get_result()
1247
self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1248
result.get_recipe())
1249
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1252
class TestFindUniqueAncestors(TestGraphBase):
1254
def assertFindUniqueAncestors(self, graph, expected, node, common):
1255
actual = graph.find_unique_ancestors(node, common)
1256
self.assertEqual(expected, sorted(actual))
1258
def test_empty_set(self):
1259
graph = self.make_graph(ancestry_1)
1260
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1261
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1262
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1264
def test_single_node(self):
1265
graph = self.make_graph(ancestry_1)
1266
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1267
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1268
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1270
def test_minimal_ancestry(self):
1271
graph = self.make_breaking_graph(extended_history_shortcut,
1272
[NULL_REVISION, 'a', 'b'])
1273
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1275
graph = self.make_breaking_graph(extended_history_shortcut,
1277
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1279
graph = self.make_breaking_graph(complex_shortcut,
1281
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1282
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1283
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1284
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1286
def test_in_ancestry(self):
1287
graph = self.make_graph(ancestry_1)
1288
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1289
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1291
def test_multiple_revisions(self):
1292
graph = self.make_graph(ancestry_1)
1293
self.assertFindUniqueAncestors(graph,
1294
['rev4'], 'rev4', ['rev3', 'rev2b'])
1295
self.assertFindUniqueAncestors(graph,
1296
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1298
def test_complex_shortcut(self):
1299
graph = self.make_graph(complex_shortcut)
1300
self.assertFindUniqueAncestors(graph,
1301
['h', 'n'], 'n', ['m'])
1302
self.assertFindUniqueAncestors(graph,
1303
['e', 'i', 'm'], 'm', ['n'])
1305
def test_complex_shortcut2(self):
1306
graph = self.make_graph(complex_shortcut2)
1307
self.assertFindUniqueAncestors(graph,
1308
['j', 'u'], 'u', ['t'])
1309
self.assertFindUniqueAncestors(graph,
1312
def test_multiple_interesting_unique(self):
1313
graph = self.make_graph(multiple_interesting_unique)
1314
self.assertFindUniqueAncestors(graph,
1315
['j', 'y'], 'y', ['z'])
1316
self.assertFindUniqueAncestors(graph,
1317
['p', 'z'], 'z', ['y'])
1319
def test_racing_shortcuts(self):
1320
graph = self.make_graph(racing_shortcuts)
1321
self.assertFindUniqueAncestors(graph,
1322
['p', 'q', 'z'], 'z', ['y'])
1323
self.assertFindUniqueAncestors(graph,
1324
['h', 'i', 'j', 'y'], 'j', ['z'])
1327
class TestGraphFindDistanceToNull(TestGraphBase):
1328
"""Test an api that should be able to compute a revno"""
1330
def assertFindDistance(self, revno, graph, target_id, known_ids):
1331
"""Assert the output of Graph.find_distance_to_null()"""
1332
actual = graph.find_distance_to_null(target_id, known_ids)
1333
self.assertEqual(revno, actual)
1335
def test_nothing_known(self):
1336
graph = self.make_graph(ancestry_1)
1337
self.assertFindDistance(0, graph, NULL_REVISION, [])
1338
self.assertFindDistance(1, graph, 'rev1', [])
1339
self.assertFindDistance(2, graph, 'rev2a', [])
1340
self.assertFindDistance(2, graph, 'rev2b', [])
1341
self.assertFindDistance(3, graph, 'rev3', [])
1342
self.assertFindDistance(4, graph, 'rev4', [])
1344
def test_rev_is_ghost(self):
1345
graph = self.make_graph(ancestry_1)
1346
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1347
graph.find_distance_to_null, 'rev_missing', [])
1348
self.assertEqual('rev_missing', e.revision_id)
1349
self.assertEqual('rev_missing', e.ghost_revision_id)
1351
def test_ancestor_is_ghost(self):
1352
graph = self.make_graph({'rev':['parent']})
1353
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1354
graph.find_distance_to_null, 'rev', [])
1355
self.assertEqual('rev', e.revision_id)
1356
self.assertEqual('parent', e.ghost_revision_id)
1358
def test_known_in_ancestry(self):
1359
graph = self.make_graph(ancestry_1)
1360
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1361
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1363
def test_known_in_ancestry_limits(self):
1364
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1365
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1367
def test_target_is_ancestor(self):
1368
graph = self.make_graph(ancestry_1)
1369
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1371
def test_target_is_ancestor_limits(self):
1372
"""We shouldn't search all history if we run into ourselves"""
1373
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1374
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1376
def test_target_parallel_to_known_limits(self):
1377
# Even though the known revision isn't part of the other ancestry, they
1378
# eventually converge
1379
graph = self.make_breaking_graph(with_tail, ['a'])
1380
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1381
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1382
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1383
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1386
class TestFindMergeOrder(TestGraphBase):
1388
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1389
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1391
def test_parents(self):
1392
graph = self.make_graph(ancestry_1)
1393
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1395
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1398
def test_ancestors(self):
1399
graph = self.make_graph(ancestry_1)
1400
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1402
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1405
def test_shortcut_one_ancestor(self):
1406
# When we have enough info, we can stop searching
1407
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1408
# Single ancestors shortcut right away
1409
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1411
def test_shortcut_after_one_ancestor(self):
1412
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1413
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1416
class TestFindDescendants(TestGraphBase):
1418
def test_find_descendants_rev1_rev3(self):
1419
graph = self.make_graph(ancestry_1)
1420
descendants = graph.find_descendants('rev1', 'rev3')
1421
self.assertEqual(set(['rev1', 'rev2a', 'rev3']), descendants)
1423
def test_find_descendants_rev1_rev4(self):
1424
graph = self.make_graph(ancestry_1)
1425
descendants = graph.find_descendants('rev1', 'rev4')
1426
self.assertEqual(set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']),
1429
def test_find_descendants_rev2a_rev4(self):
1430
graph = self.make_graph(ancestry_1)
1431
descendants = graph.find_descendants('rev2a', 'rev4')
1432
self.assertEqual(set(['rev2a', 'rev3', 'rev4']), descendants)
1434
class TestFindLefthandMerger(TestGraphBase):
1436
def check_merger(self, result, ancestry, merged, tip):
1437
graph = self.make_graph(ancestry)
1438
self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
1440
def test_find_lefthand_merger_rev2b(self):
1441
self.check_merger('rev4', ancestry_1, 'rev2b', 'rev4')
1443
def test_find_lefthand_merger_rev2a(self):
1444
self.check_merger('rev2a', ancestry_1, 'rev2a', 'rev4')
1446
def test_find_lefthand_merger_rev4(self):
1447
self.check_merger(None, ancestry_1, 'rev4', 'rev2a')
1449
def test_find_lefthand_merger_f(self):
1450
self.check_merger('i', complex_shortcut, 'f', 'm')
1452
def test_find_lefthand_merger_g(self):
1453
self.check_merger('i', complex_shortcut, 'g', 'm')
1455
def test_find_lefthand_merger_h(self):
1456
self.check_merger('n', complex_shortcut, 'h', 'n')
1459
class TestGetChildMap(TestGraphBase):
1461
def test_get_child_map(self):
1462
graph = self.make_graph(ancestry_1)
1463
child_map = graph.get_child_map(['rev4', 'rev3', 'rev2a', 'rev2b'])
1464
self.assertEqual({'rev1': ['rev2a', 'rev2b'],
1471
class TestCachingParentsProvider(tests.TestCase):
1472
"""These tests run with:
1474
self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1476
self.caching_pp, a CachingParentsProvider layered on inst_pp.
1480
super(TestCachingParentsProvider, self).setUp()
1481
dict_pp = _mod_graph.DictParentsProvider({'a': ('b',)})
1482
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1483
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1485
def test_get_parent_map(self):
1486
"""Requesting the same revision should be returned from cache"""
1487
self.assertEqual({}, self.caching_pp._cache)
1488
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1489
self.assertEqual(['a'], self.inst_pp.calls)
1490
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1491
# No new call, as it should have been returned from the cache
1492
self.assertEqual(['a'], self.inst_pp.calls)
1493
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1495
def test_get_parent_map_not_present(self):
1496
"""The cache should also track when a revision doesn't exist"""
1497
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1498
self.assertEqual(['b'], self.inst_pp.calls)
1499
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1501
self.assertEqual(['b'], self.inst_pp.calls)
1503
def test_get_parent_map_mixed(self):
1504
"""Anything that can be returned from cache, should be"""
1505
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1506
self.assertEqual(['b'], self.inst_pp.calls)
1507
self.assertEqual({'a':('b',)},
1508
self.caching_pp.get_parent_map(['a', 'b']))
1509
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1511
def test_get_parent_map_repeated(self):
1512
"""Asking for the same parent 2x will only forward 1 request."""
1513
self.assertEqual({'a':('b',)},
1514
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1515
# Use sorted because we don't care about the order, just that each is
1516
# only present 1 time.
1517
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1519
def test_note_missing_key(self):
1520
"""After noting that a key is missing it is cached."""
1521
self.caching_pp.note_missing_key('b')
1522
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1523
self.assertEqual([], self.inst_pp.calls)
1524
self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1526
def test_get_cached_parent_map(self):
1527
self.assertEqual({}, self.caching_pp.get_cached_parent_map(['a']))
1528
self.assertEqual([], self.inst_pp.calls)
1529
self.assertEqual({'a': ('b',)}, self.caching_pp.get_parent_map(['a']))
1530
self.assertEqual(['a'], self.inst_pp.calls)
1531
self.assertEqual({'a': ('b',)},
1532
self.caching_pp.get_cached_parent_map(['a']))
1535
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1536
"""Test the behaviour when parents are provided that were not requested."""
1539
super(TestCachingParentsProviderExtras, self).setUp()
1540
class ExtraParentsProvider(object):
1542
def get_parent_map(self, keys):
1543
return {'rev1': [], 'rev2': ['rev1',]}
1545
self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1546
self.caching_pp = _mod_graph.CachingParentsProvider(
1547
get_parent_map=self.inst_pp.get_parent_map)
1549
def test_uncached(self):
1550
self.caching_pp.disable_cache()
1551
self.assertEqual({'rev1': []},
1552
self.caching_pp.get_parent_map(['rev1']))
1553
self.assertEqual(['rev1'], self.inst_pp.calls)
1554
self.assertIs(None, self.caching_pp._cache)
1556
def test_cache_initially_empty(self):
1557
self.assertEqual({}, self.caching_pp._cache)
1559
def test_cached(self):
1560
self.assertEqual({'rev1': []},
1561
self.caching_pp.get_parent_map(['rev1']))
1562
self.assertEqual(['rev1'], self.inst_pp.calls)
1563
self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1564
self.caching_pp._cache)
1565
self.assertEqual({'rev1': []},
1566
self.caching_pp.get_parent_map(['rev1']))
1567
self.assertEqual(['rev1'], self.inst_pp.calls)
1569
def test_disable_cache_clears_cache(self):
1570
# Put something in the cache
1571
self.caching_pp.get_parent_map(['rev1'])
1572
self.assertEqual(2, len(self.caching_pp._cache))
1573
self.caching_pp.disable_cache()
1574
self.assertIs(None, self.caching_pp._cache)
1576
def test_enable_cache_raises(self):
1577
e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1578
self.assertEqual('Cache enabled when already enabled.', str(e))
1580
def test_cache_misses(self):
1581
self.caching_pp.get_parent_map(['rev3'])
1582
self.caching_pp.get_parent_map(['rev3'])
1583
self.assertEqual(['rev3'], self.inst_pp.calls)
1585
def test_no_cache_misses(self):
1586
self.caching_pp.disable_cache()
1587
self.caching_pp.enable_cache(cache_misses=False)
1588
self.caching_pp.get_parent_map(['rev3'])
1589
self.caching_pp.get_parent_map(['rev3'])
1590
self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1592
def test_cache_extras(self):
1593
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1594
self.assertEqual({'rev2': ['rev1']},
1595
self.caching_pp.get_parent_map(['rev2']))
1596
self.assertEqual(['rev3'], self.inst_pp.calls)
1598
def test_extras_using_cached(self):
1599
self.assertEqual({}, self.caching_pp.get_cached_parent_map(['rev3']))
1600
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1601
self.assertEqual({'rev2': ['rev1']},
1602
self.caching_pp.get_cached_parent_map(['rev2']))
1603
self.assertEqual(['rev3'], self.inst_pp.calls)
1607
class TestCollapseLinearRegions(tests.TestCase):
1609
def assertCollapsed(self, collapsed, original):
1610
self.assertEqual(collapsed,
1611
_mod_graph.collapse_linear_regions(original))
1613
def test_collapse_nothing(self):
1614
d = {1:[2, 3], 2:[], 3:[]}
1615
self.assertCollapsed(d, d)
1616
d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1617
self.assertCollapsed(d, d)
1619
def test_collapse_chain(self):
1620
# Any time we have a linear chain, we should be able to collapse
1621
d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1622
self.assertCollapsed({1:[5], 5:[]}, d)
1623
d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1624
self.assertCollapsed({5:[1], 1:[]}, d)
1625
d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1626
self.assertCollapsed({5:[2], 2:[]}, d)
1628
def test_collapse_with_multiple_children(self):
1639
# 4 and 5 cannot be removed because 6 has 2 children
1640
# 2 and 3 cannot be removed because 1 has 2 parents
1641
d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1642
self.assertCollapsed(d, d)
1645
class TestGraphThunkIdsToKeys(tests.TestCase):
1647
def test_heads(self):
1653
d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1654
('B',): [('A',)], ('A',): []}
1655
g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1656
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1657
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
1658
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
1659
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1660
self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1662
def test_add_node(self):
1663
d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1664
g = _mod_graph.KnownGraph(d)
1665
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1666
graph_thunk.add_node("D", ["A", "C"])
1667
self.assertEqual(['B', 'D'],
1668
sorted(graph_thunk.heads(['D', 'B', 'A'])))
1670
def test_merge_sort(self):
1671
d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1672
g = _mod_graph.KnownGraph(d)
1673
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1674
graph_thunk.add_node("D", ["A", "C"])
1675
self.assertEqual([('C', 0, (2,), False), ('A', 0, (1,), True)],
1676
[(n.key, n.merge_depth, n.revno, n.end_of_merge)
1677
for n in graph_thunk.merge_sort('C')])
1680
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1681
"""Tests for bzrlib.graph.PendingAncestryResult."""
1683
def test_get_keys(self):
1684
builder = self.make_branch_builder('b')
1685
builder.start_series()
1686
builder.build_snapshot('rev-1', None, [
1687
('add', ('', 'root-id', 'directory', ''))])
1688
builder.build_snapshot('rev-2', ['rev-1'], [])
1689
builder.finish_series()
1690
repo = builder.get_branch().repository
1692
self.addCleanup(repo.unlock)
1693
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1694
self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1696
def test_get_keys_excludes_ghosts(self):
1697
builder = self.make_branch_builder('b')
1698
builder.start_series()
1699
builder.build_snapshot('rev-1', None, [
1700
('add', ('', 'root-id', 'directory', ''))])
1701
builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
1702
builder.finish_series()
1703
repo = builder.get_branch().repository
1705
self.addCleanup(repo.unlock)
1706
result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1707
self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
1709
def test_get_keys_excludes_null(self):
1710
# Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1711
# somewhere other than the last element, which can happen in real
1713
class StubGraph(object):
1714
def iter_ancestry(self, keys):
1715
return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1716
result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1717
result_keys = result._get_keys(StubGraph())
1718
# Only the non-null keys from the ancestry appear.
1719
self.assertEqual(set(['foo']), set(result_keys))
1722
class TestPendingAncestryResultRefine(TestGraphBase):
1724
def test_refine(self):
1725
# Used when pulling from a stacked repository, so test some revisions
1726
# being satisfied from the stacking branch.
1727
g = self.make_graph(
1728
{"tip":["mid"], "mid":["base"], "tag":["base"],
1729
"base":[NULL_REVISION], NULL_REVISION:[]})
1730
result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1731
result = result.refine(set(['tip']), set(['mid']))
1732
self.assertEqual(set(['mid', 'tag']), result.heads)
1733
result = result.refine(set(['mid', 'tag', 'base']),
1734
set([NULL_REVISION]))
1735
self.assertEqual(set([NULL_REVISION]), result.heads)
1736
self.assertTrue(result.is_empty())
1739
class TestSearchResultRefine(TestGraphBase):
1741
def test_refine(self):
1742
# Used when pulling from a stacked repository, so test some revisions
1743
# being satisfied from the stacking branch.
1744
g = self.make_graph(
1745
{"tip":["mid"], "mid":["base"], "tag":["base"],
1746
"base":[NULL_REVISION], NULL_REVISION:[]})
1747
result = _mod_graph.SearchResult(set(['tip', 'tag']),
1748
set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1749
result = result.refine(set(['tip']), set(['mid']))
1750
recipe = result.get_recipe()
1751
# We should be starting from tag (original head) and mid (seen ref)
1752
self.assertEqual(set(['mid', 'tag']), recipe[1])
1753
# We should be stopping at NULL (original stop) and tip (seen head)
1754
self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1755
self.assertEqual(3, recipe[3])
1756
result = result.refine(set(['mid', 'tag', 'base']),
1757
set([NULL_REVISION]))
1758
recipe = result.get_recipe()
1759
# We should be starting from nothing (NULL was known as a cut point)
1760
self.assertEqual(set([]), recipe[1])
1761
# We should be stopping at NULL (original stop) and tip (seen head) and
1762
# tag (seen head) and mid(seen mid-point head). We could come back and
1763
# define this as not including mid, for minimal results, but it is
1764
# still 'correct' to include mid, and simpler/easier.
1765
self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1766
self.assertEqual(0, recipe[3])
1767
self.assertTrue(result.is_empty())
1770
class TestSearchResultFromParentMap(TestGraphBase):
1772
def assertSearchResult(self, start_keys, stop_keys, key_count, parent_map,
1774
(start, stop, count) = _mod_graph.search_result_from_parent_map(
1775
parent_map, missing_keys)
1776
self.assertEqual((sorted(start_keys), sorted(stop_keys), key_count),
1777
(sorted(start), sorted(stop), count))
1779
def test_no_parents(self):
1780
self.assertSearchResult([], [], 0, {})
1781
self.assertSearchResult([], [], 0, None)
1783
def test_ancestry_1(self):
1784
self.assertSearchResult(['rev4'], [NULL_REVISION], len(ancestry_1),
1787
def test_ancestry_2(self):
1788
self.assertSearchResult(['rev1b', 'rev4a'], [NULL_REVISION],
1789
len(ancestry_2), ancestry_2)
1790
self.assertSearchResult(['rev1b', 'rev4a'], [],
1791
len(ancestry_2)+1, ancestry_2,
1792
missing_keys=[NULL_REVISION])
1794
def test_partial_search(self):
1795
parent_map = dict((k,extended_history_shortcut[k])
1796
for k in ['e', 'f'])
1797
self.assertSearchResult(['e', 'f'], ['d', 'a'], 2,
1799
parent_map.update((k,extended_history_shortcut[k])
1800
for k in ['d', 'a'])
1801
self.assertSearchResult(['e', 'f'], ['c', NULL_REVISION], 4,
1803
parent_map['c'] = extended_history_shortcut['c']
1804
self.assertSearchResult(['e', 'f'], ['b'], 6,
1805
parent_map, missing_keys=[NULL_REVISION])
1806
parent_map['b'] = extended_history_shortcut['b']
1807
self.assertSearchResult(['e', 'f'], [], 7,
1808
parent_map, missing_keys=[NULL_REVISION])
1811
class TestLimitedSearchResultFromParentMap(TestGraphBase):
1813
def assertSearchResult(self, start_keys, stop_keys, key_count, parent_map,
1814
missing_keys, tip_keys, depth):
1815
(start, stop, count) = _mod_graph.limited_search_result_from_parent_map(
1816
parent_map, missing_keys, tip_keys, depth)
1817
self.assertEqual((sorted(start_keys), sorted(stop_keys), key_count),
1818
(sorted(start), sorted(stop), count))
1820
def test_empty_ancestry(self):
1821
self.assertSearchResult([], [], 0, {}, (), ['tip-rev-id'], 10)
1823
def test_ancestry_1(self):
1824
self.assertSearchResult(['rev4'], ['rev1'], 4,
1825
ancestry_1, (), ['rev1'], 10)
1826
self.assertSearchResult(['rev2a', 'rev2b'], ['rev1'], 2,
1827
ancestry_1, (), ['rev1'], 1)
1830
def test_multiple_heads(self):
1831
self.assertSearchResult(['e', 'f'], ['a'], 5,
1832
extended_history_shortcut, (), ['a'], 10)
1833
# Note that even though we only take 1 step back, we find 'f', which
1834
# means the described search will still find d and c.
1835
self.assertSearchResult(['f'], ['a'], 4,
1836
extended_history_shortcut, (), ['a'], 1)
1837
self.assertSearchResult(['f'], ['a'], 4,
1838
extended_history_shortcut, (), ['a'], 2)
1841
class TestStackedParentsProvider(tests.TestCase):
1844
super(TestStackedParentsProvider, self).setUp()
1847
def get_shared_provider(self, info, ancestry, has_cached):
1848
pp = _mod_graph.DictParentsProvider(ancestry)
1850
pp.get_cached_parent_map = pp.get_parent_map
1851
return SharedInstrumentedParentsProvider(pp, self.calls, info)
1853
def test_stacked_parents_provider(self):
1854
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
1855
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
1856
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1857
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
1858
stacked.get_parent_map(['rev1', 'rev2']))
1859
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
1860
stacked.get_parent_map(['rev2', 'rev1']))
1861
self.assertEqual({'rev2':['rev3']},
1862
stacked.get_parent_map(['rev2', 'rev2']))
1863
self.assertEqual({'rev1':['rev4']},
1864
stacked.get_parent_map(['rev1', 'rev1']))
1866
def test_stacked_parents_provider_overlapping(self):
1867
# rev2 is availible in both providers.
1871
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
1872
parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
1873
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1874
self.assertEqual({'rev2': ['rev1']},
1875
stacked.get_parent_map(['rev2']))
1877
def test_handles_no_get_cached_parent_map(self):
1878
# this shows that we both handle when a provider doesn't implement
1879
# get_cached_parent_map
1880
pp1 = self.get_shared_provider('pp1', {'rev2': ('rev1',)},
1882
pp2 = self.get_shared_provider('pp2', {'rev2': ('rev1',)},
1884
stacked = _mod_graph.StackedParentsProvider([pp1, pp2])
1885
self.assertEqual({'rev2': ('rev1',)}, stacked.get_parent_map(['rev2']))
1886
# No call on 'pp1' because it doesn't provide get_cached_parent_map
1887
self.assertEqual([('pp2', 'cached', ['rev2'])], self.calls)
1889
def test_query_order(self):
1890
# We should call get_cached_parent_map on all providers before we call
1891
# get_parent_map. Further, we should track what entries we have found,
1892
# and not re-try them.
1893
pp1 = self.get_shared_provider('pp1', {'a': ()}, has_cached=True)
1894
pp2 = self.get_shared_provider('pp2', {'c': ('b',)}, has_cached=False)
1895
pp3 = self.get_shared_provider('pp3', {'b': ('a',)}, has_cached=True)
1896
stacked = _mod_graph.StackedParentsProvider([pp1, pp2, pp3])
1897
self.assertEqual({'a': (), 'b': ('a',), 'c': ('b',)},
1898
stacked.get_parent_map(['a', 'b', 'c', 'd']))
1899
self.assertEqual([('pp1', 'cached', ['a', 'b', 'c', 'd']),
1900
# No call to pp2, because it doesn't have cached
1901
('pp3', 'cached', ['b', 'c', 'd']),
1902
('pp1', ['c', 'd']),
1903
('pp2', ['c', 'd']),
added
removed
bzrlib/tests/test_graph.py
