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
state = search.get_state()
1033
self.assertEqual(set(included_keys), state[2])
1034
self.assertEqual(seen, search.seen)
1036
def test_breadth_first_get_result_excludes_current_pending(self):
1037
graph = self.make_graph({
1039
'child':[NULL_REVISION],
1042
search = graph._make_breadth_first_searcher(['head'])
1043
# At the start, nothing has been seen, to its all excluded:
1044
state = search.get_state()
1045
self.assertEqual((set(['head']), set(['head']), set()),
1047
self.assertEqual(set(), search.seen)
1050
(set(['head']), (set(['head']), set(['child']), 1),
1051
['head'], None, None),
1052
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
1053
['head', 'child'], None, None),
1054
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
1055
['head', 'child', NULL_REVISION], None, None),
1057
self.assertSeenAndResult(expected, search, search.next)
1058
# using next_with_ghosts:
1059
search = graph._make_breadth_first_searcher(['head'])
1060
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1062
def test_breadth_first_get_result_starts_stops(self):
1063
graph = self.make_graph({
1065
'child':[NULL_REVISION],
1066
'otherhead':['otherchild'],
1067
'otherchild':['excluded'],
1068
'excluded':[NULL_REVISION],
1071
search = graph._make_breadth_first_searcher([])
1072
# Starting with nothing and adding a search works:
1073
search.start_searching(['head'])
1074
# head has been seen:
1075
state = search.get_state()
1076
self.assertEqual((set(['head']), set(['child']), set(['head'])),
1078
self.assertEqual(set(['head']), search.seen)
1081
# stop at child, and start a new search at otherhead:
1082
# - otherhead counts as seen immediately when start_searching is
1084
(set(['head', 'child', 'otherhead']),
1085
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1086
['head', 'otherhead'], ['otherhead'], ['child']),
1087
(set(['head', 'child', 'otherhead', 'otherchild']),
1088
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1089
['head', 'otherhead', 'otherchild'], None, None),
1090
# stop searching excluded now
1091
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1092
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1093
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1095
self.assertSeenAndResult(expected, search, search.next)
1096
# using next_with_ghosts:
1097
search = graph._make_breadth_first_searcher([])
1098
search.start_searching(['head'])
1099
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1101
def test_breadth_first_stop_searching_not_queried(self):
1102
# A client should be able to say 'stop node X' even if X has not been
1103
# returned to the client.
1104
graph = self.make_graph({
1105
'head':['child', 'ghost1'],
1106
'child':[NULL_REVISION],
1109
search = graph._make_breadth_first_searcher(['head'])
1111
# NULL_REVISION and ghost1 have not been returned
1113
(set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1114
['head'], None, [NULL_REVISION, 'ghost1']),
1115
# ghost1 has been returned, NULL_REVISION is to be returned in the
1117
(set(['head', 'child', 'ghost1']),
1118
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1119
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1121
self.assertSeenAndResult(expected, search, search.next)
1122
# using next_with_ghosts:
1123
search = graph._make_breadth_first_searcher(['head'])
1124
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1126
def test_breadth_first_stop_searching_late(self):
1127
# A client should be able to say 'stop node X' and have it excluded
1128
# from the result even if X was seen in an older iteration of the
1130
graph = self.make_graph({
1133
'child':[NULL_REVISION],
1136
search = graph._make_breadth_first_searcher(['head'])
1138
(set(['head']), (set(['head']), set(['middle']), 1),
1139
['head'], None, None),
1140
(set(['head', 'middle']), (set(['head']), set(['child']), 2),
1141
['head', 'middle'], None, None),
1142
# 'middle' came from the previous iteration, but we don't stop
1143
# searching it until *after* advancing the searcher.
1144
(set(['head', 'middle', 'child']),
1145
(set(['head']), set(['middle', 'child']), 1),
1146
['head'], None, ['middle', 'child']),
1148
self.assertSeenAndResult(expected, search, search.next)
1149
# using next_with_ghosts:
1150
search = graph._make_breadth_first_searcher(['head'])
1151
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1153
def test_breadth_first_get_result_ghosts_are_excluded(self):
1154
graph = self.make_graph({
1155
'head':['child', 'ghost'],
1156
'child':[NULL_REVISION],
1159
search = graph._make_breadth_first_searcher(['head'])
1163
(set(['head']), set(['ghost', 'child']), 1),
1164
['head'], None, None),
1165
(set(['head', 'child', 'ghost']),
1166
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1167
['head', 'child'], None, None),
1169
self.assertSeenAndResult(expected, search, search.next)
1170
# using next_with_ghosts:
1171
search = graph._make_breadth_first_searcher(['head'])
1172
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1174
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1175
graph = self.make_graph({
1177
'child':[NULL_REVISION],
1180
search = graph._make_breadth_first_searcher(['head'])
1183
(set(['head', 'ghost']),
1184
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1185
['head'], ['ghost'], None),
1186
(set(['head', 'child', 'ghost']),
1187
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1188
['head', 'child'], None, None),
1190
self.assertSeenAndResult(expected, search, search.next)
1191
# using next_with_ghosts:
1192
search = graph._make_breadth_first_searcher(['head'])
1193
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1195
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1196
graph = self.make_graph({
1197
'head':[NULL_REVISION],
1200
search = graph._make_breadth_first_searcher(['head'])
1204
(set(['head']), set([NULL_REVISION]), 1),
1205
['head'], None, None),
1206
(set(['head', NULL_REVISION]),
1207
(set(['head']), set([]), 2),
1208
['head', NULL_REVISION], None, None),
1210
self.assertSeenAndResult(expected, search, search.next)
1211
# using next_with_ghosts:
1212
search = graph._make_breadth_first_searcher(['head'])
1213
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1215
def test_breadth_first_search_get_result_after_StopIteration(self):
1216
# StopIteration should not invalid anything..
1217
graph = self.make_graph({
1218
'head':[NULL_REVISION],
1221
search = graph._make_breadth_first_searcher(['head'])
1225
(set(['head']), set([NULL_REVISION]), 1),
1226
['head'], None, None),
1227
(set(['head', 'ghost', NULL_REVISION]),
1228
(set(['head', 'ghost']), set(['ghost']), 2),
1229
['head', NULL_REVISION], ['ghost'], None),
1231
self.assertSeenAndResult(expected, search, search.next)
1232
self.assertRaises(StopIteration, search.next)
1233
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1234
state = search.get_state()
1236
(set(['ghost', 'head']), set(['ghost']),
1237
set(['head', NULL_REVISION])),
1239
# using next_with_ghosts:
1240
search = graph._make_breadth_first_searcher(['head'])
1241
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1242
self.assertRaises(StopIteration, search.next)
1243
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1244
state = search.get_state()
1246
(set(['ghost', 'head']), set(['ghost']),
1247
set(['head', NULL_REVISION])),
1251
class TestFindUniqueAncestors(TestGraphBase):
1253
def assertFindUniqueAncestors(self, graph, expected, node, common):
1254
actual = graph.find_unique_ancestors(node, common)
1255
self.assertEqual(expected, sorted(actual))
1257
def test_empty_set(self):
1258
graph = self.make_graph(ancestry_1)
1259
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1260
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1261
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1263
def test_single_node(self):
1264
graph = self.make_graph(ancestry_1)
1265
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1266
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1267
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1269
def test_minimal_ancestry(self):
1270
graph = self.make_breaking_graph(extended_history_shortcut,
1271
[NULL_REVISION, 'a', 'b'])
1272
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1274
graph = self.make_breaking_graph(extended_history_shortcut,
1276
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1278
graph = self.make_breaking_graph(complex_shortcut,
1280
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1281
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1282
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1283
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1285
def test_in_ancestry(self):
1286
graph = self.make_graph(ancestry_1)
1287
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1288
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1290
def test_multiple_revisions(self):
1291
graph = self.make_graph(ancestry_1)
1292
self.assertFindUniqueAncestors(graph,
1293
['rev4'], 'rev4', ['rev3', 'rev2b'])
1294
self.assertFindUniqueAncestors(graph,
1295
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1297
def test_complex_shortcut(self):
1298
graph = self.make_graph(complex_shortcut)
1299
self.assertFindUniqueAncestors(graph,
1300
['h', 'n'], 'n', ['m'])
1301
self.assertFindUniqueAncestors(graph,
1302
['e', 'i', 'm'], 'm', ['n'])
1304
def test_complex_shortcut2(self):
1305
graph = self.make_graph(complex_shortcut2)
1306
self.assertFindUniqueAncestors(graph,
1307
['j', 'u'], 'u', ['t'])
1308
self.assertFindUniqueAncestors(graph,
1311
def test_multiple_interesting_unique(self):
1312
graph = self.make_graph(multiple_interesting_unique)
1313
self.assertFindUniqueAncestors(graph,
1314
['j', 'y'], 'y', ['z'])
1315
self.assertFindUniqueAncestors(graph,
1316
['p', 'z'], 'z', ['y'])
1318
def test_racing_shortcuts(self):
1319
graph = self.make_graph(racing_shortcuts)
1320
self.assertFindUniqueAncestors(graph,
1321
['p', 'q', 'z'], 'z', ['y'])
1322
self.assertFindUniqueAncestors(graph,
1323
['h', 'i', 'j', 'y'], 'j', ['z'])
1326
class TestGraphFindDistanceToNull(TestGraphBase):
1327
"""Test an api that should be able to compute a revno"""
1329
def assertFindDistance(self, revno, graph, target_id, known_ids):
1330
"""Assert the output of Graph.find_distance_to_null()"""
1331
actual = graph.find_distance_to_null(target_id, known_ids)
1332
self.assertEqual(revno, actual)
1334
def test_nothing_known(self):
1335
graph = self.make_graph(ancestry_1)
1336
self.assertFindDistance(0, graph, NULL_REVISION, [])
1337
self.assertFindDistance(1, graph, 'rev1', [])
1338
self.assertFindDistance(2, graph, 'rev2a', [])
1339
self.assertFindDistance(2, graph, 'rev2b', [])
1340
self.assertFindDistance(3, graph, 'rev3', [])
1341
self.assertFindDistance(4, graph, 'rev4', [])
1343
def test_rev_is_ghost(self):
1344
graph = self.make_graph(ancestry_1)
1345
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1346
graph.find_distance_to_null, 'rev_missing', [])
1347
self.assertEqual('rev_missing', e.revision_id)
1348
self.assertEqual('rev_missing', e.ghost_revision_id)
1350
def test_ancestor_is_ghost(self):
1351
graph = self.make_graph({'rev':['parent']})
1352
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1353
graph.find_distance_to_null, 'rev', [])
1354
self.assertEqual('rev', e.revision_id)
1355
self.assertEqual('parent', e.ghost_revision_id)
1357
def test_known_in_ancestry(self):
1358
graph = self.make_graph(ancestry_1)
1359
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1360
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1362
def test_known_in_ancestry_limits(self):
1363
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1364
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1366
def test_target_is_ancestor(self):
1367
graph = self.make_graph(ancestry_1)
1368
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1370
def test_target_is_ancestor_limits(self):
1371
"""We shouldn't search all history if we run into ourselves"""
1372
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1373
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1375
def test_target_parallel_to_known_limits(self):
1376
# Even though the known revision isn't part of the other ancestry, they
1377
# eventually converge
1378
graph = self.make_breaking_graph(with_tail, ['a'])
1379
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1380
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1381
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1382
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1385
class TestFindMergeOrder(TestGraphBase):
1387
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1388
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1390
def test_parents(self):
1391
graph = self.make_graph(ancestry_1)
1392
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1394
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1397
def test_ancestors(self):
1398
graph = self.make_graph(ancestry_1)
1399
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1401
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1404
def test_shortcut_one_ancestor(self):
1405
# When we have enough info, we can stop searching
1406
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1407
# Single ancestors shortcut right away
1408
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1410
def test_shortcut_after_one_ancestor(self):
1411
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1412
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1415
class TestFindDescendants(TestGraphBase):
1417
def test_find_descendants_rev1_rev3(self):
1418
graph = self.make_graph(ancestry_1)
1419
descendants = graph.find_descendants('rev1', 'rev3')
1420
self.assertEqual(set(['rev1', 'rev2a', 'rev3']), descendants)
1422
def test_find_descendants_rev1_rev4(self):
1423
graph = self.make_graph(ancestry_1)
1424
descendants = graph.find_descendants('rev1', 'rev4')
1425
self.assertEqual(set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']),
1428
def test_find_descendants_rev2a_rev4(self):
1429
graph = self.make_graph(ancestry_1)
1430
descendants = graph.find_descendants('rev2a', 'rev4')
1431
self.assertEqual(set(['rev2a', 'rev3', 'rev4']), descendants)
1433
class TestFindLefthandMerger(TestGraphBase):
1435
def check_merger(self, result, ancestry, merged, tip):
1436
graph = self.make_graph(ancestry)
1437
self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
1439
def test_find_lefthand_merger_rev2b(self):
1440
self.check_merger('rev4', ancestry_1, 'rev2b', 'rev4')
1442
def test_find_lefthand_merger_rev2a(self):
1443
self.check_merger('rev2a', ancestry_1, 'rev2a', 'rev4')
1445
def test_find_lefthand_merger_rev4(self):
1446
self.check_merger(None, ancestry_1, 'rev4', 'rev2a')
1448
def test_find_lefthand_merger_f(self):
1449
self.check_merger('i', complex_shortcut, 'f', 'm')
1451
def test_find_lefthand_merger_g(self):
1452
self.check_merger('i', complex_shortcut, 'g', 'm')
1454
def test_find_lefthand_merger_h(self):
1455
self.check_merger('n', complex_shortcut, 'h', 'n')
1458
class TestGetChildMap(TestGraphBase):
1460
def test_get_child_map(self):
1461
graph = self.make_graph(ancestry_1)
1462
child_map = graph.get_child_map(['rev4', 'rev3', 'rev2a', 'rev2b'])
1463
self.assertEqual({'rev1': ['rev2a', 'rev2b'],
1470
class TestCachingParentsProvider(tests.TestCase):
1471
"""These tests run with:
1473
self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1475
self.caching_pp, a CachingParentsProvider layered on inst_pp.
1479
super(TestCachingParentsProvider, self).setUp()
1480
dict_pp = _mod_graph.DictParentsProvider({'a': ('b',)})
1481
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1482
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1484
def test_get_parent_map(self):
1485
"""Requesting the same revision should be returned from cache"""
1486
self.assertEqual({}, self.caching_pp._cache)
1487
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1488
self.assertEqual(['a'], self.inst_pp.calls)
1489
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1490
# No new call, as it should have been returned from the cache
1491
self.assertEqual(['a'], self.inst_pp.calls)
1492
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1494
def test_get_parent_map_not_present(self):
1495
"""The cache should also track when a revision doesn't exist"""
1496
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1497
self.assertEqual(['b'], self.inst_pp.calls)
1498
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1500
self.assertEqual(['b'], self.inst_pp.calls)
1502
def test_get_parent_map_mixed(self):
1503
"""Anything that can be returned from cache, should be"""
1504
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1505
self.assertEqual(['b'], self.inst_pp.calls)
1506
self.assertEqual({'a':('b',)},
1507
self.caching_pp.get_parent_map(['a', 'b']))
1508
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1510
def test_get_parent_map_repeated(self):
1511
"""Asking for the same parent 2x will only forward 1 request."""
1512
self.assertEqual({'a':('b',)},
1513
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1514
# Use sorted because we don't care about the order, just that each is
1515
# only present 1 time.
1516
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1518
def test_note_missing_key(self):
1519
"""After noting that a key is missing it is cached."""
1520
self.caching_pp.note_missing_key('b')
1521
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1522
self.assertEqual([], self.inst_pp.calls)
1523
self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1525
def test_get_cached_parent_map(self):
1526
self.assertEqual({}, self.caching_pp.get_cached_parent_map(['a']))
1527
self.assertEqual([], self.inst_pp.calls)
1528
self.assertEqual({'a': ('b',)}, self.caching_pp.get_parent_map(['a']))
1529
self.assertEqual(['a'], self.inst_pp.calls)
1530
self.assertEqual({'a': ('b',)},
1531
self.caching_pp.get_cached_parent_map(['a']))
1534
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1535
"""Test the behaviour when parents are provided that were not requested."""
1538
super(TestCachingParentsProviderExtras, self).setUp()
1539
class ExtraParentsProvider(object):
1541
def get_parent_map(self, keys):
1542
return {'rev1': [], 'rev2': ['rev1',]}
1544
self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1545
self.caching_pp = _mod_graph.CachingParentsProvider(
1546
get_parent_map=self.inst_pp.get_parent_map)
1548
def test_uncached(self):
1549
self.caching_pp.disable_cache()
1550
self.assertEqual({'rev1': []},
1551
self.caching_pp.get_parent_map(['rev1']))
1552
self.assertEqual(['rev1'], self.inst_pp.calls)
1553
self.assertIs(None, self.caching_pp._cache)
1555
def test_cache_initially_empty(self):
1556
self.assertEqual({}, self.caching_pp._cache)
1558
def test_cached(self):
1559
self.assertEqual({'rev1': []},
1560
self.caching_pp.get_parent_map(['rev1']))
1561
self.assertEqual(['rev1'], self.inst_pp.calls)
1562
self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1563
self.caching_pp._cache)
1564
self.assertEqual({'rev1': []},
1565
self.caching_pp.get_parent_map(['rev1']))
1566
self.assertEqual(['rev1'], self.inst_pp.calls)
1568
def test_disable_cache_clears_cache(self):
1569
# Put something in the cache
1570
self.caching_pp.get_parent_map(['rev1'])
1571
self.assertEqual(2, len(self.caching_pp._cache))
1572
self.caching_pp.disable_cache()
1573
self.assertIs(None, self.caching_pp._cache)
1575
def test_enable_cache_raises(self):
1576
e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1577
self.assertEqual('Cache enabled when already enabled.', str(e))
1579
def test_cache_misses(self):
1580
self.caching_pp.get_parent_map(['rev3'])
1581
self.caching_pp.get_parent_map(['rev3'])
1582
self.assertEqual(['rev3'], self.inst_pp.calls)
1584
def test_no_cache_misses(self):
1585
self.caching_pp.disable_cache()
1586
self.caching_pp.enable_cache(cache_misses=False)
1587
self.caching_pp.get_parent_map(['rev3'])
1588
self.caching_pp.get_parent_map(['rev3'])
1589
self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1591
def test_cache_extras(self):
1592
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1593
self.assertEqual({'rev2': ['rev1']},
1594
self.caching_pp.get_parent_map(['rev2']))
1595
self.assertEqual(['rev3'], self.inst_pp.calls)
1597
def test_extras_using_cached(self):
1598
self.assertEqual({}, self.caching_pp.get_cached_parent_map(['rev3']))
1599
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1600
self.assertEqual({'rev2': ['rev1']},
1601
self.caching_pp.get_cached_parent_map(['rev2']))
1602
self.assertEqual(['rev3'], self.inst_pp.calls)
1606
class TestCollapseLinearRegions(tests.TestCase):
1608
def assertCollapsed(self, collapsed, original):
1609
self.assertEqual(collapsed,
1610
_mod_graph.collapse_linear_regions(original))
1612
def test_collapse_nothing(self):
1613
d = {1:[2, 3], 2:[], 3:[]}
1614
self.assertCollapsed(d, d)
1615
d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1616
self.assertCollapsed(d, d)
1618
def test_collapse_chain(self):
1619
# Any time we have a linear chain, we should be able to collapse
1620
d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1621
self.assertCollapsed({1:[5], 5:[]}, d)
1622
d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1623
self.assertCollapsed({5:[1], 1:[]}, d)
1624
d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1625
self.assertCollapsed({5:[2], 2:[]}, d)
1627
def test_collapse_with_multiple_children(self):
1638
# 4 and 5 cannot be removed because 6 has 2 children
1639
# 2 and 3 cannot be removed because 1 has 2 parents
1640
d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1641
self.assertCollapsed(d, d)
1644
class TestGraphThunkIdsToKeys(tests.TestCase):
1646
def test_heads(self):
1652
d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1653
('B',): [('A',)], ('A',): []}
1654
g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1655
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1656
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
1657
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
1658
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1659
self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1661
def test_add_node(self):
1662
d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1663
g = _mod_graph.KnownGraph(d)
1664
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1665
graph_thunk.add_node("D", ["A", "C"])
1666
self.assertEqual(['B', 'D'],
1667
sorted(graph_thunk.heads(['D', 'B', 'A'])))
1669
def test_merge_sort(self):
1670
d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1671
g = _mod_graph.KnownGraph(d)
1672
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1673
graph_thunk.add_node("D", ["A", "C"])
1674
self.assertEqual([('C', 0, (2,), False), ('A', 0, (1,), True)],
1675
[(n.key, n.merge_depth, n.revno, n.end_of_merge)
1676
for n in graph_thunk.merge_sort('C')])
1679
class TestStackedParentsProvider(tests.TestCase):
1682
super(TestStackedParentsProvider, self).setUp()
1685
def get_shared_provider(self, info, ancestry, has_cached):
1686
pp = _mod_graph.DictParentsProvider(ancestry)
1688
pp.get_cached_parent_map = pp.get_parent_map
1689
return SharedInstrumentedParentsProvider(pp, self.calls, info)
1691
def test_stacked_parents_provider(self):
1692
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
1693
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
1694
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1695
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
1696
stacked.get_parent_map(['rev1', 'rev2']))
1697
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
1698
stacked.get_parent_map(['rev2', 'rev1']))
1699
self.assertEqual({'rev2':['rev3']},
1700
stacked.get_parent_map(['rev2', 'rev2']))
1701
self.assertEqual({'rev1':['rev4']},
1702
stacked.get_parent_map(['rev1', 'rev1']))
1704
def test_stacked_parents_provider_overlapping(self):
1705
# rev2 is availible in both providers.
1709
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
1710
parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
1711
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1712
self.assertEqual({'rev2': ['rev1']},
1713
stacked.get_parent_map(['rev2']))
1715
def test_handles_no_get_cached_parent_map(self):
1716
# this shows that we both handle when a provider doesn't implement
1717
# get_cached_parent_map
1718
pp1 = self.get_shared_provider('pp1', {'rev2': ('rev1',)},
1720
pp2 = self.get_shared_provider('pp2', {'rev2': ('rev1',)},
1722
stacked = _mod_graph.StackedParentsProvider([pp1, pp2])
1723
self.assertEqual({'rev2': ('rev1',)}, stacked.get_parent_map(['rev2']))
1724
# No call on 'pp1' because it doesn't provide get_cached_parent_map
1725
self.assertEqual([('pp2', 'cached', ['rev2'])], self.calls)
1727
def test_query_order(self):
1728
# We should call get_cached_parent_map on all providers before we call
1729
# get_parent_map. Further, we should track what entries we have found,
1730
# and not re-try them.
1731
pp1 = self.get_shared_provider('pp1', {'a': ()}, has_cached=True)
1732
pp2 = self.get_shared_provider('pp2', {'c': ('b',)}, has_cached=False)
1733
pp3 = self.get_shared_provider('pp3', {'b': ('a',)}, has_cached=True)
1734
stacked = _mod_graph.StackedParentsProvider([pp1, pp2, pp3])
1735
self.assertEqual({'a': (), 'b': ('a',), 'c': ('b',)},
1736
stacked.get_parent_map(['a', 'b', 'c', 'd']))
1737
self.assertEqual([('pp1', 'cached', ['a', 'b', 'c', 'd']),
1738
# No call to pp2, because it doesn't have cached
1739
('pp3', 'cached', ['b', 'c', 'd']),
1740
('pp1', ['c', 'd']),
1741
('pp2', ['c', 'd']),
added
removed
bzrlib/tests/test_graph.py
