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 ..revision import NULL_REVISION
23
from . import TestCaseWithMemoryTransport
37
ancestry_1 = {b'rev1': [NULL_REVISION], b'rev2a': [b'rev1'], b'rev2b': [b'rev1'],
38
b'rev3': [b'rev2a'], b'rev4': [b'rev3', b'rev2b']}
52
ancestry_2 = {b'rev1a': [NULL_REVISION], b'rev2a': [b'rev1a'],
53
b'rev1b': [NULL_REVISION], b'rev3a': [b'rev2a'], b'rev4a': [b'rev3a']}
56
# Criss cross ancestry
67
criss_cross = {b'rev1': [NULL_REVISION], b'rev2a': [b'rev1'], b'rev2b': [b'rev1'],
68
b'rev3a': [b'rev2a', b'rev2b'], b'rev3b': [b'rev2b', b'rev2a']}
82
criss_cross2 = {b'rev1a': [NULL_REVISION], b'rev1b': [NULL_REVISION],
83
b'rev2a': [b'rev1a', b'rev1b'], b'rev2b': [b'rev1b', b'rev1a']}
95
mainline = {b'rev1': [NULL_REVISION], b'rev2a': [b'rev1', b'rev2b'],
108
feature_branch = {b'rev1': [NULL_REVISION],
109
b'rev2b': [b'rev1'], b'rev3b': [b'rev2b']}
120
history_shortcut = {b'rev1': [NULL_REVISION], b'rev2a': [b'rev1'],
121
b'rev2b': [b'rev1'], b'rev2c': [b'rev1'],
122
b'rev3a': [b'rev2a', b'rev2b'], b'rev3b': [b'rev2b', b'rev2c']}
124
# Extended history shortcut
136
extended_history_shortcut = {b'a': [NULL_REVISION],
145
# Both sides will see b'A' first, even though it is actually a decendent of a
146
# different common revision.
160
double_shortcut = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'],
161
b'd': [b'c'], b'e': [b'c'], b'f': [b'a', b'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 = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'],
193
b'e': [b'd'], b'f': [b'd'], b'g': [b'f'], b'h': [b'f'],
194
b'i': [b'e', b'g'], b'j': [b'g'], b'k': [b'j'],
195
b'l': [b'k'], b'm': [b'i', b'l'], b'n': [b'l', b'h']}
235
complex_shortcut2 = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'],
236
b'e': [b'd'], b'f': [b'e'], b'g': [b'f'], b'h': [b'd'], b'i': [b'g'],
237
b'j': [b'h'], b'k': [b'h', b'i'], b'l': [b'k'], b'm': [b'l'], b'n': [b'm'],
238
b'o': [b'n'], b'p': [b'o'], b'q': [b'p'], b'r': [b'q'], b's': [b'r'],
239
b't': [b'i', b's'], b'u': [b's', b'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 = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'],
294
b'e': [b'd'], b'f': [b'e'], b'g': [b'f'], b'h': [b'g'], b'i': [b'h', b'o'], b'j': [b'i', b'y'],
295
b'k': [b'd'], b'l': [b'k'], b'm': [b'l'], b'n': [b'm'], b'o': [b'n', b'g'], b'p': [b'f'],
296
b'q': [b'p', b'm'], b'r': [b'o'], b's': [b'r'], b't': [b's'], b'u': [b't'], b'v': [b'u'],
297
b'w': [b'v'], b'x': [b'w'], b'y': [b'x'], b'z': [b'x', b'q']}
300
# A graph with multiple nodes unique to one side.
339
multiple_interesting_unique = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'],
340
b'd': [b'c'], b'e': [b'd'], b'f': [b'd'], b'g': [b'e'], b'h': [b'e'], b'i': [b'f'],
341
b'j': [b'g'], b'k': [b'g'], b'l': [b'h'], b'm': [b'i'], b'n': [b'k', b'l'],
342
b'o': [b'm'], b'p': [b'm', b'l'], b'q': [b'n', b'o'], b'r': [b'q'], b's': [b'r'],
343
b't': [b's'], b'u': [b't'], b'v': [b'u'], b'w': [b'v'], b'x': [b'w'],
344
b'y': [b'j', b'x'], b'z': [b'x', b'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 = {b'a': [NULL_REVISION],
366
b'f': [b'a', b'd', b'g'],
367
b'g': [NULL_REVISION],
380
boundary = {b'a': [b'b'], b'c': [b'b', b'd'], b'b': [b'e'], b'd': [b'e'], b'e': [b'f'],
381
b'f': [NULL_REVISION]}
384
# A graph that contains a ghost
395
with_ghost = {b'a': [b'b'], b'c': [b'b', b'd'], b'b': [b'e'], b'd': [b'e', b'g'],
396
b'e': [b'f'], b'f': [NULL_REVISION], NULL_REVISION: ()}
398
# A graph that shows we can shortcut finding revnos when reaching them from the
418
with_tail = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'], b'e': [b'd'],
419
b'f': [b'e'], b'g': [b'e'], b'h': [b'f'], b'i': [b'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
473
def get_parent_map(keys):
474
bad_keys = set(keys).intersection(break_on)
476
self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
477
return orig_parent_map(keys)
478
g.get_parent_map = get_parent_map
482
class TestGraph(TestCaseWithMemoryTransport):
484
def make_graph(self, ancestors):
485
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
487
def prepare_memory_tree(self, location):
488
tree = self.make_branch_and_memory_tree(location)
493
def build_ancestry(self, tree, ancestors):
494
"""Create an ancestry as specified by a graph dict
496
:param tree: A tree to use
497
:param ancestors: a dict of {node: [node_parent, ...]}
499
pending = [NULL_REVISION]
501
for descendant, parents in ancestors.items():
502
for parent in parents:
503
descendants.setdefault(parent, []).append(descendant)
504
while len(pending) > 0:
505
cur_node = pending.pop()
506
for descendant in descendants.get(cur_node, []):
507
if tree.branch.repository.has_revision(descendant):
509
parents = [p for p in ancestors[descendant] if p is not
511
if len([p for p in parents if not
512
tree.branch.repository.has_revision(p)]) > 0:
514
tree.set_parent_ids(parents)
516
left_parent = parents[0]
518
left_parent = NULL_REVISION
519
tree.branch.set_last_revision_info(
520
len(tree.branch._lefthand_history(left_parent)),
522
tree.commit(descendant, rev_id=descendant)
523
pending.append(descendant)
526
"""Test finding least common ancestor.
528
ancestry_1 should always have a single common ancestor
530
graph = self.make_graph(ancestry_1)
531
self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
532
self.assertEqual({NULL_REVISION},
533
graph.find_lca(NULL_REVISION, NULL_REVISION))
534
self.assertEqual({NULL_REVISION},
535
graph.find_lca(NULL_REVISION, b'rev1'))
536
self.assertEqual({b'rev1'}, graph.find_lca(b'rev1', b'rev1'))
537
self.assertEqual({b'rev1'}, graph.find_lca(b'rev2a', b'rev2b'))
539
def test_no_unique_lca(self):
540
"""Test error when one revision is not in the graph"""
541
graph = self.make_graph(ancestry_1)
542
self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
545
def test_lca_criss_cross(self):
546
"""Test least-common-ancestor after a criss-cross merge."""
547
graph = self.make_graph(criss_cross)
548
self.assertEqual({b'rev2a', b'rev2b'},
549
graph.find_lca(b'rev3a', b'rev3b'))
550
self.assertEqual({b'rev2b'},
551
graph.find_lca(b'rev3a', b'rev3b', b'rev2b'))
553
def test_lca_shortcut(self):
554
"""Test least-common ancestor on this history shortcut"""
555
graph = self.make_graph(history_shortcut)
556
self.assertEqual({b'rev2b'}, graph.find_lca(b'rev3a', b'rev3b'))
558
def test_lefthand_distance_smoke(self):
559
"""A simple does it work test for graph.lefthand_distance(keys)."""
560
graph = self.make_graph(history_shortcut)
561
distance_graph = graph.find_lefthand_distances([b'rev3b', b'rev2a'])
562
self.assertEqual({b'rev2a': 2, b'rev3b': 3}, distance_graph)
564
def test_lefthand_distance_ghosts(self):
565
"""A simple does it work test for graph.lefthand_distance(keys)."""
566
nodes = {b'nonghost': [NULL_REVISION], b'toghost': [b'ghost']}
567
graph = self.make_graph(nodes)
568
distance_graph = graph.find_lefthand_distances(
569
[b'nonghost', b'toghost'])
570
self.assertEqual({b'nonghost': 1, b'toghost': -1}, distance_graph)
572
def test_recursive_unique_lca(self):
573
"""Test finding a unique least common ancestor.
575
ancestry_1 should always have a single common ancestor
577
graph = self.make_graph(ancestry_1)
578
self.assertEqual(NULL_REVISION,
579
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
580
self.assertEqual(NULL_REVISION,
581
graph.find_unique_lca(NULL_REVISION, b'rev1'))
582
self.assertEqual(b'rev1', graph.find_unique_lca(b'rev1', b'rev1'))
583
self.assertEqual(b'rev1', graph.find_unique_lca(b'rev2a', b'rev2b'))
584
self.assertEqual((b'rev1', 1,),
585
graph.find_unique_lca(b'rev2a', b'rev2b',
588
def assertRemoveDescendants(self, expected, graph, revisions):
589
parents = graph.get_parent_map(revisions)
590
self.assertEqual(expected,
591
graph._remove_simple_descendants(revisions, parents))
593
def test__remove_simple_descendants(self):
594
graph = self.make_graph(ancestry_1)
595
self.assertRemoveDescendants({b'rev1'}, graph,
596
{b'rev1', b'rev2a', b'rev2b', b'rev3', b'rev4'})
598
def test__remove_simple_descendants_disjoint(self):
599
graph = self.make_graph(ancestry_1)
600
self.assertRemoveDescendants({b'rev1', b'rev3'}, graph,
603
def test__remove_simple_descendants_chain(self):
604
graph = self.make_graph(ancestry_1)
605
self.assertRemoveDescendants({b'rev1'}, graph,
606
{b'rev1', b'rev2a', b'rev3'})
608
def test__remove_simple_descendants_siblings(self):
609
graph = self.make_graph(ancestry_1)
610
self.assertRemoveDescendants({b'rev2a', b'rev2b'}, graph,
611
{b'rev2a', b'rev2b', b'rev3'})
613
def test_unique_lca_criss_cross(self):
614
"""Ensure we don't pick non-unique lcas in a criss-cross"""
615
graph = self.make_graph(criss_cross)
616
self.assertEqual(b'rev1', graph.find_unique_lca(b'rev3a', b'rev3b'))
617
lca, steps = graph.find_unique_lca(
618
b'rev3a', b'rev3b', count_steps=True)
619
self.assertEqual(b'rev1', lca)
620
self.assertEqual(2, steps)
622
def test_unique_lca_null_revision(self):
623
"""Ensure we pick NULL_REVISION when necessary"""
624
graph = self.make_graph(criss_cross2)
625
self.assertEqual(b'rev1b', graph.find_unique_lca(b'rev2a', b'rev1b'))
626
self.assertEqual(NULL_REVISION,
627
graph.find_unique_lca(b'rev2a', b'rev2b'))
629
def test_unique_lca_null_revision2(self):
630
"""Ensure we pick NULL_REVISION when necessary"""
631
graph = self.make_graph(ancestry_2)
632
self.assertEqual(NULL_REVISION,
633
graph.find_unique_lca(b'rev4a', b'rev1b'))
635
def test_lca_double_shortcut(self):
636
graph = self.make_graph(double_shortcut)
637
self.assertEqual(b'c', graph.find_unique_lca(b'f', b'g'))
639
def test_common_ancestor_two_repos(self):
640
"""Ensure we do unique_lca using data from two repos"""
641
mainline_tree = self.prepare_memory_tree('mainline')
642
self.build_ancestry(mainline_tree, mainline)
643
self.addCleanup(mainline_tree.unlock)
645
# This is cheating, because the revisions in the graph are actually
646
# different revisions, despite having the same revision-id.
647
feature_tree = self.prepare_memory_tree('feature')
648
self.build_ancestry(feature_tree, feature_branch)
649
self.addCleanup(feature_tree.unlock)
651
graph = mainline_tree.branch.repository.get_graph(
652
feature_tree.branch.repository)
653
self.assertEqual(b'rev2b', graph.find_unique_lca(b'rev2a', b'rev3b'))
655
def test_graph_difference(self):
656
graph = self.make_graph(ancestry_1)
658
(set(), set()), graph.find_difference(b'rev1', b'rev1'))
659
self.assertEqual((set(), {b'rev1'}),
660
graph.find_difference(NULL_REVISION, b'rev1'))
661
self.assertEqual(({b'rev1'}, set()),
662
graph.find_difference(b'rev1', NULL_REVISION))
663
self.assertEqual(({b'rev2a', b'rev3'}, {b'rev2b'}),
664
graph.find_difference(b'rev3', b'rev2b'))
665
self.assertEqual(({b'rev4', b'rev3', b'rev2a'}, set()),
666
graph.find_difference(b'rev4', b'rev2b'))
668
def test_graph_difference_separate_ancestry(self):
669
graph = self.make_graph(ancestry_2)
670
self.assertEqual(({b'rev1a'}, {b'rev1b'}),
671
graph.find_difference(b'rev1a', b'rev1b'))
672
self.assertEqual(({b'rev1a', b'rev2a', b'rev3a', b'rev4a'},
674
graph.find_difference(b'rev4a', b'rev1b'))
676
def test_graph_difference_criss_cross(self):
677
graph = self.make_graph(criss_cross)
678
self.assertEqual(({b'rev3a'}, {b'rev3b'}),
679
graph.find_difference(b'rev3a', b'rev3b'))
680
self.assertEqual((set([]), {b'rev3b', b'rev2b'}),
681
graph.find_difference(b'rev2a', b'rev3b'))
683
def test_graph_difference_extended_history(self):
684
graph = self.make_graph(extended_history_shortcut)
685
self.assertEqual(({b'e'}, {b'f'}),
686
graph.find_difference(b'e', b'f'))
687
self.assertEqual(({b'f'}, {b'e'}),
688
graph.find_difference(b'f', b'e'))
690
def test_graph_difference_double_shortcut(self):
691
graph = self.make_graph(double_shortcut)
692
self.assertEqual(({b'd', b'f'}, {b'e', b'g'}),
693
graph.find_difference(b'f', b'g'))
695
def test_graph_difference_complex_shortcut(self):
696
graph = self.make_graph(complex_shortcut)
697
self.assertEqual(({b'm', b'i', b'e'}, {b'n', b'h'}),
698
graph.find_difference(b'm', b'n'))
700
def test_graph_difference_complex_shortcut2(self):
701
graph = self.make_graph(complex_shortcut2)
702
self.assertEqual(({b't'}, {b'j', b'u'}),
703
graph.find_difference(b't', b'u'))
705
def test_graph_difference_shortcut_extra_root(self):
706
graph = self.make_graph(shortcut_extra_root)
707
self.assertEqual(({b'e'}, {b'f', b'g'}),
708
graph.find_difference(b'e', b'f'))
710
def test_iter_topo_order(self):
711
graph = self.make_graph(ancestry_1)
712
args = [b'rev2a', b'rev3', b'rev1']
713
topo_args = list(graph.iter_topo_order(args))
714
self.assertEqual(set(args), set(topo_args))
715
self.assertTrue(topo_args.index(b'rev2a') > topo_args.index(b'rev1'))
716
self.assertTrue(topo_args.index(b'rev2a') < topo_args.index(b'rev3'))
718
def test_is_ancestor(self):
719
graph = self.make_graph(ancestry_1)
720
self.assertEqual(True, graph.is_ancestor(b'null:', b'null:'))
721
self.assertEqual(True, graph.is_ancestor(b'null:', b'rev1'))
722
self.assertEqual(False, graph.is_ancestor(b'rev1', b'null:'))
723
self.assertEqual(True, graph.is_ancestor(b'null:', b'rev4'))
724
self.assertEqual(False, graph.is_ancestor(b'rev4', b'null:'))
725
self.assertEqual(False, graph.is_ancestor(b'rev4', b'rev2b'))
726
self.assertEqual(True, graph.is_ancestor(b'rev2b', b'rev4'))
727
self.assertEqual(False, graph.is_ancestor(b'rev2b', b'rev3'))
728
self.assertEqual(False, graph.is_ancestor(b'rev3', b'rev2b'))
729
instrumented_provider = InstrumentedParentsProvider(graph)
730
instrumented_graph = _mod_graph.Graph(instrumented_provider)
731
instrumented_graph.is_ancestor(b'rev2a', b'rev2b')
732
self.assertTrue(b'null:' not in instrumented_provider.calls)
734
def test_is_between(self):
735
graph = self.make_graph(ancestry_1)
736
self.assertEqual(True, graph.is_between(b'null:', b'null:', b'null:'))
737
self.assertEqual(True, graph.is_between(b'rev1', b'null:', b'rev1'))
738
self.assertEqual(True, graph.is_between(b'rev1', b'rev1', b'rev4'))
739
self.assertEqual(True, graph.is_between(b'rev4', b'rev1', b'rev4'))
740
self.assertEqual(True, graph.is_between(b'rev3', b'rev1', b'rev4'))
741
self.assertEqual(False, graph.is_between(b'rev4', b'rev1', b'rev3'))
742
self.assertEqual(False, graph.is_between(b'rev1', b'rev2a', b'rev4'))
743
self.assertEqual(False, graph.is_between(b'null:', b'rev1', b'rev4'))
745
def test_is_ancestor_boundary(self):
746
"""Ensure that we avoid searching the whole graph.
748
This requires searching through b as a common ancestor, so we
749
can identify that e is common.
751
graph = self.make_graph(boundary)
752
instrumented_provider = InstrumentedParentsProvider(graph)
753
graph = _mod_graph.Graph(instrumented_provider)
754
self.assertFalse(graph.is_ancestor(b'a', b'c'))
755
self.assertTrue(b'null:' not in instrumented_provider.calls)
757
def test_iter_ancestry(self):
758
nodes = boundary.copy()
759
nodes[NULL_REVISION] = ()
760
graph = self.make_graph(nodes)
761
expected = nodes.copy()
762
expected.pop(b'a') # b'a' is not in the ancestry of b'c', all the
764
self.assertEqual(expected, dict(graph.iter_ancestry([b'c'])))
765
self.assertEqual(nodes, dict(graph.iter_ancestry([b'a', b'c'])))
767
def test_iter_ancestry_with_ghost(self):
768
graph = self.make_graph(with_ghost)
769
expected = with_ghost.copy()
770
# b'a' is not in the ancestry of b'c', and b'g' is a ghost
771
expected[b'g'] = None
772
self.assertEqual(expected, dict(graph.iter_ancestry([b'a', b'c'])))
774
self.assertEqual(expected, dict(graph.iter_ancestry([b'c'])))
776
def test_filter_candidate_lca(self):
777
"""Test filter_candidate_lca for a corner case
779
This tests the case where we encounter the end of iteration for b'e'
780
in the same pass as we discover that b'd' is an ancestor of b'e', and
781
therefore b'e' can't be an lca.
783
To compensate for different dict orderings on other Python
784
implementations, we mirror b'd' and b'e' with b'b' and b'a'.
786
# This test is sensitive to the iteration order of dicts. It will
787
# pass incorrectly if b'e' and b'a' sort before b'c'
796
graph = self.make_graph({b'c': [b'b', b'd'], b'd': [b'e'], b'b': [b'a'],
797
b'a': [NULL_REVISION], b'e': [NULL_REVISION]})
798
self.assertEqual({b'c'}, graph.heads([b'a', b'c', b'e']))
800
def test_heads_null(self):
801
graph = self.make_graph(ancestry_1)
802
self.assertEqual({b'null:'}, graph.heads([b'null:']))
803
self.assertEqual({b'rev1'}, graph.heads([b'null:', b'rev1']))
804
self.assertEqual({b'rev1'}, graph.heads([b'rev1', b'null:']))
805
self.assertEqual({b'rev1'}, graph.heads({b'rev1', b'null:'}))
806
self.assertEqual({b'rev1'}, graph.heads((b'rev1', b'null:')))
808
def test_heads_one(self):
809
# A single node will always be a head
810
graph = self.make_graph(ancestry_1)
811
self.assertEqual({b'null:'}, graph.heads([b'null:']))
812
self.assertEqual({b'rev1'}, graph.heads([b'rev1']))
813
self.assertEqual({b'rev2a'}, graph.heads([b'rev2a']))
814
self.assertEqual({b'rev2b'}, graph.heads([b'rev2b']))
815
self.assertEqual({b'rev3'}, graph.heads([b'rev3']))
816
self.assertEqual({b'rev4'}, graph.heads([b'rev4']))
818
def test_heads_single(self):
819
graph = self.make_graph(ancestry_1)
820
self.assertEqual({b'rev4'}, graph.heads([b'null:', b'rev4']))
821
self.assertEqual({b'rev2a'}, graph.heads([b'rev1', b'rev2a']))
822
self.assertEqual({b'rev2b'}, graph.heads([b'rev1', b'rev2b']))
823
self.assertEqual({b'rev3'}, graph.heads([b'rev1', b'rev3']))
824
self.assertEqual({b'rev4'}, graph.heads([b'rev1', b'rev4']))
825
self.assertEqual({b'rev4'}, graph.heads([b'rev2a', b'rev4']))
826
self.assertEqual({b'rev4'}, graph.heads([b'rev2b', b'rev4']))
827
self.assertEqual({b'rev4'}, graph.heads([b'rev3', b'rev4']))
829
def test_heads_two_heads(self):
830
graph = self.make_graph(ancestry_1)
831
self.assertEqual({b'rev2a', b'rev2b'},
832
graph.heads([b'rev2a', b'rev2b']))
833
self.assertEqual({b'rev3', b'rev2b'},
834
graph.heads([b'rev3', b'rev2b']))
836
def test_heads_criss_cross(self):
837
graph = self.make_graph(criss_cross)
838
self.assertEqual({b'rev2a'},
839
graph.heads([b'rev2a', b'rev1']))
840
self.assertEqual({b'rev2b'},
841
graph.heads([b'rev2b', b'rev1']))
842
self.assertEqual({b'rev3a'},
843
graph.heads([b'rev3a', b'rev1']))
844
self.assertEqual({b'rev3b'},
845
graph.heads([b'rev3b', b'rev1']))
846
self.assertEqual({b'rev2a', b'rev2b'},
847
graph.heads([b'rev2a', b'rev2b']))
848
self.assertEqual({b'rev3a'},
849
graph.heads([b'rev3a', b'rev2a']))
850
self.assertEqual({b'rev3a'},
851
graph.heads([b'rev3a', b'rev2b']))
852
self.assertEqual({b'rev3a'},
853
graph.heads([b'rev3a', b'rev2a', b'rev2b']))
854
self.assertEqual({b'rev3b'},
855
graph.heads([b'rev3b', b'rev2a']))
856
self.assertEqual({b'rev3b'},
857
graph.heads([b'rev3b', b'rev2b']))
858
self.assertEqual({b'rev3b'},
859
graph.heads([b'rev3b', b'rev2a', b'rev2b']))
860
self.assertEqual({b'rev3a', b'rev3b'},
861
graph.heads([b'rev3a', b'rev3b']))
862
self.assertEqual({b'rev3a', b'rev3b'},
863
graph.heads([b'rev3a', b'rev3b', b'rev2a', b'rev2b']))
865
def test_heads_shortcut(self):
866
graph = self.make_graph(history_shortcut)
868
self.assertEqual({b'rev2a', b'rev2b', b'rev2c'},
869
graph.heads([b'rev2a', b'rev2b', b'rev2c']))
870
self.assertEqual({b'rev3a', b'rev3b'},
871
graph.heads([b'rev3a', b'rev3b']))
872
self.assertEqual({b'rev3a', b'rev3b'},
873
graph.heads([b'rev2a', b'rev3a', b'rev3b']))
874
self.assertEqual({b'rev2a', b'rev3b'},
875
graph.heads([b'rev2a', b'rev3b']))
876
self.assertEqual({b'rev2c', b'rev3a'},
877
graph.heads([b'rev2c', b'rev3a']))
879
def _run_heads_break_deeper(self, graph_dict, search):
880
"""Run heads on a graph-as-a-dict.
882
If the search asks for the parents of b'deeper' the test will fail.
887
def get_parent_map(keys):
891
self.fail('key deeper was accessed')
892
result[key] = graph_dict[key]
895
an_obj.get_parent_map = get_parent_map
896
graph = _mod_graph.Graph(an_obj)
897
return graph.heads(search)
899
def test_heads_limits_search(self):
900
# test that a heads query does not search all of history
902
b'left': [b'common'],
903
b'right': [b'common'],
904
b'common': [b'deeper'],
906
self.assertEqual({b'left', b'right'},
907
self._run_heads_break_deeper(graph_dict, [b'left', b'right']))
909
def test_heads_limits_search_assymetric(self):
910
# test that a heads query does not search all of history
912
b'left': [b'midleft'],
913
b'midleft': [b'common'],
914
b'right': [b'common'],
915
b'common': [b'aftercommon'],
916
b'aftercommon': [b'deeper'],
918
self.assertEqual({b'left', b'right'},
919
self._run_heads_break_deeper(graph_dict, [b'left', b'right']))
921
def test_heads_limits_search_common_search_must_continue(self):
922
# test that common nodes are still queried, preventing
923
# all-the-way-to-origin behaviour in the following graph:
925
b'h1': [b'shortcut', b'common1'],
927
b'shortcut': [b'common2'],
928
b'common1': [b'common2'],
929
b'common2': [b'deeper'],
931
self.assertEqual({b'h1', b'h2'},
932
self._run_heads_break_deeper(graph_dict, [b'h1', b'h2']))
934
def test_breadth_first_search_start_ghosts(self):
935
graph = self.make_graph({})
936
# with_ghosts reports the ghosts
937
search = graph._make_breadth_first_searcher([b'a-ghost'])
938
self.assertEqual((set(), {b'a-ghost'}), search.next_with_ghosts())
939
self.assertRaises(StopIteration, search.next_with_ghosts)
941
search = graph._make_breadth_first_searcher([b'a-ghost'])
942
self.assertEqual({b'a-ghost'}, next(search))
943
self.assertRaises(StopIteration, next, search)
945
def test_breadth_first_search_deep_ghosts(self):
946
graph = self.make_graph({
947
b'head': [b'present'],
948
b'present': [b'child', b'ghost'],
951
# with_ghosts reports the ghosts
952
search = graph._make_breadth_first_searcher([b'head'])
953
self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
954
self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
955
self.assertEqual(({b'child'}, {b'ghost'}),
956
search.next_with_ghosts())
957
self.assertRaises(StopIteration, search.next_with_ghosts)
959
search = graph._make_breadth_first_searcher([b'head'])
960
self.assertEqual({b'head'}, next(search))
961
self.assertEqual({b'present'}, next(search))
962
self.assertEqual({b'child', b'ghost'},
964
self.assertRaises(StopIteration, next, search)
966
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
967
# To make the API robust, we allow calling both next() and
968
# next_with_ghosts() on the same searcher.
969
graph = self.make_graph({
970
b'head': [b'present'],
971
b'present': [b'child', b'ghost'],
974
# start with next_with_ghosts
975
search = graph._make_breadth_first_searcher([b'head'])
976
self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
977
self.assertEqual({b'present'}, next(search))
978
self.assertEqual(({b'child'}, {b'ghost'}),
979
search.next_with_ghosts())
980
self.assertRaises(StopIteration, next, search)
982
search = graph._make_breadth_first_searcher([b'head'])
983
self.assertEqual({b'head'}, next(search))
984
self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
985
self.assertEqual({b'child', b'ghost'},
987
self.assertRaises(StopIteration, search.next_with_ghosts)
989
def test_breadth_first_change_search(self):
990
# Changing the search should work with both next and next_with_ghosts.
991
graph = self.make_graph({
992
b'head': [b'present'],
993
b'present': [b'stopped'],
994
b'other': [b'other_2'],
997
search = graph._make_breadth_first_searcher([b'head'])
998
self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
999
self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
1000
self.assertEqual({b'present'},
1001
search.stop_searching_any([b'present']))
1002
self.assertEqual(({b'other'}, {b'other_ghost'}),
1003
search.start_searching([b'other', b'other_ghost']))
1004
self.assertEqual(({b'other_2'}, set()), search.next_with_ghosts())
1005
self.assertRaises(StopIteration, search.next_with_ghosts)
1006
# next includes them
1007
search = graph._make_breadth_first_searcher([b'head'])
1008
self.assertEqual({b'head'}, next(search))
1009
self.assertEqual({b'present'}, next(search))
1010
self.assertEqual({b'present'},
1011
search.stop_searching_any([b'present']))
1012
search.start_searching([b'other', b'other_ghost'])
1013
self.assertEqual({b'other_2'}, next(search))
1014
self.assertRaises(StopIteration, next, search)
1016
def assertSeenAndResult(self, instructions, search, next):
1017
"""Check the results of .seen and get_result() for a seach.
1019
:param instructions: A list of tuples:
1020
(seen, recipe, included_keys, starts, stops).
1021
seen, recipe and included_keys are results to check on the search
1022
and the searches get_result(). starts and stops are parameters to
1023
pass to start_searching and stop_searching_any during each
1024
iteration, if they are not None.
1025
:param search: The search to use.
1026
:param next: A callable to advance the search.
1028
for seen, recipe, included_keys, starts, stops in instructions:
1029
# Adjust for recipe contract changes that don't vary for all the
1031
recipe = ('search',) + recipe
1033
if starts is not None:
1034
search.start_searching(starts)
1035
if stops is not None:
1036
search.stop_searching_any(stops)
1037
state = search.get_state()
1038
self.assertEqual(set(included_keys), state[2])
1039
self.assertEqual(seen, search.seen)
1041
def test_breadth_first_get_result_excludes_current_pending(self):
1042
graph = self.make_graph({
1043
b'head': [b'child'],
1044
b'child': [NULL_REVISION],
1047
search = graph._make_breadth_first_searcher([b'head'])
1048
# At the start, nothing has been seen, to its all excluded:
1049
state = search.get_state()
1050
self.assertEqual(({b'head'}, {b'head'}, set()),
1052
self.assertEqual(set(), search.seen)
1055
({b'head'}, ({b'head'}, {b'child'}, 1),
1056
[b'head'], None, None),
1057
({b'head', b'child'}, ({b'head'}, {NULL_REVISION}, 2),
1058
[b'head', b'child'], None, None),
1059
({b'head', b'child', NULL_REVISION}, ({b'head'}, set(), 3),
1060
[b'head', b'child', NULL_REVISION], None, None),
1062
self.assertSeenAndResult(expected, search, search.__next__)
1063
# using next_with_ghosts:
1064
search = graph._make_breadth_first_searcher([b'head'])
1065
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1067
def test_breadth_first_get_result_starts_stops(self):
1068
graph = self.make_graph({
1069
b'head': [b'child'],
1070
b'child': [NULL_REVISION],
1071
b'otherhead': [b'otherchild'],
1072
b'otherchild': [b'excluded'],
1073
b'excluded': [NULL_REVISION],
1076
search = graph._make_breadth_first_searcher([])
1077
# Starting with nothing and adding a search works:
1078
search.start_searching([b'head'])
1079
# head has been seen:
1080
state = search.get_state()
1081
self.assertEqual(({b'head'}, {b'child'}, {b'head'}),
1083
self.assertEqual({b'head'}, search.seen)
1086
# stop at child, and start a new search at otherhead:
1087
# - otherhead counts as seen immediately when start_searching is
1089
({b'head', b'child', b'otherhead'},
1090
({b'head', b'otherhead'}, {b'child', b'otherchild'}, 2),
1091
[b'head', b'otherhead'], [b'otherhead'], [b'child']),
1092
({b'head', b'child', b'otherhead', b'otherchild'},
1093
({b'head', b'otherhead'}, {b'child', b'excluded'}, 3),
1094
[b'head', b'otherhead', b'otherchild'], None, None),
1095
# stop searching excluded now
1096
({b'head', b'child', b'otherhead', b'otherchild', b'excluded'},
1097
({b'head', b'otherhead'}, {b'child', b'excluded'}, 3),
1098
[b'head', b'otherhead', b'otherchild'], None, [b'excluded']),
1100
self.assertSeenAndResult(expected, search, search.__next__)
1101
# using next_with_ghosts:
1102
search = graph._make_breadth_first_searcher([])
1103
search.start_searching([b'head'])
1104
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1106
def test_breadth_first_stop_searching_not_queried(self):
1107
# A client should be able to say b'stop node X' even if X has not been
1108
# returned to the client.
1109
graph = self.make_graph({
1110
b'head': [b'child', b'ghost1'],
1111
b'child': [NULL_REVISION],
1114
search = graph._make_breadth_first_searcher([b'head'])
1116
# NULL_REVISION and ghost1 have not been returned
1118
({b'head'}, {b'child', NULL_REVISION, b'ghost1'}, 1),
1119
[b'head'], None, [NULL_REVISION, b'ghost1']),
1120
# ghost1 has been returned, NULL_REVISION is to be returned in the
1122
({b'head', b'child', b'ghost1'},
1123
({b'head'}, {b'ghost1', NULL_REVISION}, 2),
1124
[b'head', b'child'], None, [NULL_REVISION, b'ghost1']),
1126
self.assertSeenAndResult(expected, search, search.__next__)
1127
# using next_with_ghosts:
1128
search = graph._make_breadth_first_searcher([b'head'])
1129
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1131
def test_breadth_first_stop_searching_late(self):
1132
# A client should be able to say b'stop node X' and have it excluded
1133
# from the result even if X was seen in an older iteration of the
1135
graph = self.make_graph({
1136
b'head': [b'middle'],
1137
b'middle': [b'child'],
1138
b'child': [NULL_REVISION],
1141
search = graph._make_breadth_first_searcher([b'head'])
1143
({b'head'}, ({b'head'}, {b'middle'}, 1),
1144
[b'head'], None, None),
1145
({b'head', b'middle'}, ({b'head'}, {b'child'}, 2),
1146
[b'head', b'middle'], None, None),
1147
# b'middle' came from the previous iteration, but we don't stop
1148
# searching it until *after* advancing the searcher.
1149
({b'head', b'middle', b'child'},
1150
({b'head'}, {b'middle', b'child'}, 1),
1151
[b'head'], None, [b'middle', b'child']),
1153
self.assertSeenAndResult(expected, search, search.__next__)
1154
# using next_with_ghosts:
1155
search = graph._make_breadth_first_searcher([b'head'])
1156
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1158
def test_breadth_first_get_result_ghosts_are_excluded(self):
1159
graph = self.make_graph({
1160
b'head': [b'child', b'ghost'],
1161
b'child': [NULL_REVISION],
1164
search = graph._make_breadth_first_searcher([b'head'])
1168
({b'head'}, {b'ghost', b'child'}, 1),
1169
[b'head'], None, None),
1170
({b'head', b'child', b'ghost'},
1171
({b'head'}, {NULL_REVISION, b'ghost'}, 2),
1172
[b'head', b'child'], None, None),
1174
self.assertSeenAndResult(expected, search, search.__next__)
1175
# using next_with_ghosts:
1176
search = graph._make_breadth_first_searcher([b'head'])
1177
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1179
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1180
graph = self.make_graph({
1181
b'head': [b'child'],
1182
b'child': [NULL_REVISION],
1185
search = graph._make_breadth_first_searcher([b'head'])
1188
({b'head', b'ghost'},
1189
({b'head', b'ghost'}, {b'child', b'ghost'}, 1),
1190
[b'head'], [b'ghost'], None),
1191
({b'head', b'child', b'ghost'},
1192
({b'head', b'ghost'}, {NULL_REVISION, b'ghost'}, 2),
1193
[b'head', b'child'], None, None),
1195
self.assertSeenAndResult(expected, search, search.__next__)
1196
# using next_with_ghosts:
1197
search = graph._make_breadth_first_searcher([b'head'])
1198
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1200
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1201
graph = self.make_graph({
1202
b'head': [NULL_REVISION],
1205
search = graph._make_breadth_first_searcher([b'head'])
1209
({b'head'}, {NULL_REVISION}, 1),
1210
[b'head'], None, None),
1211
({b'head', NULL_REVISION},
1212
({b'head'}, set([]), 2),
1213
[b'head', NULL_REVISION], None, None),
1215
self.assertSeenAndResult(expected, search, search.__next__)
1216
# using next_with_ghosts:
1217
search = graph._make_breadth_first_searcher([b'head'])
1218
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1220
def test_breadth_first_search_get_result_after_StopIteration(self):
1221
# StopIteration should not invalid anything..
1222
graph = self.make_graph({
1223
b'head': [NULL_REVISION],
1226
search = graph._make_breadth_first_searcher([b'head'])
1230
({b'head'}, {NULL_REVISION}, 1),
1231
[b'head'], None, None),
1232
({b'head', b'ghost', NULL_REVISION},
1233
({b'head', b'ghost'}, {b'ghost'}, 2),
1234
[b'head', NULL_REVISION], [b'ghost'], None),
1236
self.assertSeenAndResult(expected, search, search.__next__)
1237
self.assertRaises(StopIteration, next, search)
1238
self.assertEqual({b'head', b'ghost', NULL_REVISION}, search.seen)
1239
state = search.get_state()
1241
({b'ghost', b'head'}, {b'ghost'},
1242
{b'head', NULL_REVISION}),
1244
# using next_with_ghosts:
1245
search = graph._make_breadth_first_searcher([b'head'])
1246
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1247
self.assertRaises(StopIteration, next, search)
1248
self.assertEqual({b'head', b'ghost', NULL_REVISION}, search.seen)
1249
state = search.get_state()
1251
({b'ghost', b'head'}, {b'ghost'},
1252
{b'head', NULL_REVISION}),
1256
class TestFindUniqueAncestors(TestGraphBase):
1258
def assertFindUniqueAncestors(self, graph, expected, node, common):
1259
actual = graph.find_unique_ancestors(node, common)
1260
self.assertEqual(expected, sorted(actual))
1262
def test_empty_set(self):
1263
graph = self.make_graph(ancestry_1)
1264
self.assertFindUniqueAncestors(graph, [], b'rev1', [b'rev1'])
1265
self.assertFindUniqueAncestors(graph, [], b'rev2b', [b'rev2b'])
1266
self.assertFindUniqueAncestors(graph, [], b'rev3', [b'rev1', b'rev3'])
1268
def test_single_node(self):
1269
graph = self.make_graph(ancestry_1)
1270
self.assertFindUniqueAncestors(graph, [b'rev2a'], b'rev2a', [b'rev1'])
1271
self.assertFindUniqueAncestors(graph, [b'rev2b'], b'rev2b', [b'rev1'])
1272
self.assertFindUniqueAncestors(graph, [b'rev3'], b'rev3', [b'rev2a'])
1274
def test_minimal_ancestry(self):
1275
graph = self.make_breaking_graph(extended_history_shortcut,
1276
[NULL_REVISION, b'a', b'b'])
1277
self.assertFindUniqueAncestors(graph, [b'e'], b'e', [b'd'])
1279
graph = self.make_breaking_graph(extended_history_shortcut,
1281
self.assertFindUniqueAncestors(graph, [b'f'], b'f', [b'a', b'd'])
1283
graph = self.make_breaking_graph(complex_shortcut,
1285
self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'i'])
1286
self.assertFindUniqueAncestors(graph, [b'e', b'g', b'i'], b'i', [b'h'])
1287
self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'g'])
1288
self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'j'])
1290
def test_in_ancestry(self):
1291
graph = self.make_graph(ancestry_1)
1292
self.assertFindUniqueAncestors(graph, [], b'rev1', [b'rev3'])
1293
self.assertFindUniqueAncestors(graph, [], b'rev2b', [b'rev4'])
1295
def test_multiple_revisions(self):
1296
graph = self.make_graph(ancestry_1)
1297
self.assertFindUniqueAncestors(graph,
1298
[b'rev4'], b'rev4', [b'rev3', b'rev2b'])
1299
self.assertFindUniqueAncestors(graph,
1300
[b'rev2a', b'rev3', b'rev4'], b'rev4', [b'rev2b'])
1302
def test_complex_shortcut(self):
1303
graph = self.make_graph(complex_shortcut)
1304
self.assertFindUniqueAncestors(graph,
1305
[b'h', b'n'], b'n', [b'm'])
1306
self.assertFindUniqueAncestors(graph,
1307
[b'e', b'i', b'm'], b'm', [b'n'])
1309
def test_complex_shortcut2(self):
1310
graph = self.make_graph(complex_shortcut2)
1311
self.assertFindUniqueAncestors(graph,
1312
[b'j', b'u'], b'u', [b't'])
1313
self.assertFindUniqueAncestors(graph,
1314
[b't'], b't', [b'u'])
1316
def test_multiple_interesting_unique(self):
1317
graph = self.make_graph(multiple_interesting_unique)
1318
self.assertFindUniqueAncestors(graph,
1319
[b'j', b'y'], b'y', [b'z'])
1320
self.assertFindUniqueAncestors(graph,
1321
[b'p', b'z'], b'z', [b'y'])
1323
def test_racing_shortcuts(self):
1324
graph = self.make_graph(racing_shortcuts)
1325
self.assertFindUniqueAncestors(graph,
1326
[b'p', b'q', b'z'], b'z', [b'y'])
1327
self.assertFindUniqueAncestors(graph,
1328
[b'h', b'i', b'j', b'y'], b'j', [b'z'])
1331
class TestGraphFindDistanceToNull(TestGraphBase):
1332
"""Test an api that should be able to compute a revno"""
1334
def assertFindDistance(self, revno, graph, target_id, known_ids):
1335
"""Assert the output of Graph.find_distance_to_null()"""
1336
actual = graph.find_distance_to_null(target_id, known_ids)
1337
self.assertEqual(revno, actual)
1339
def test_nothing_known(self):
1340
graph = self.make_graph(ancestry_1)
1341
self.assertFindDistance(0, graph, NULL_REVISION, [])
1342
self.assertFindDistance(1, graph, b'rev1', [])
1343
self.assertFindDistance(2, graph, b'rev2a', [])
1344
self.assertFindDistance(2, graph, b'rev2b', [])
1345
self.assertFindDistance(3, graph, b'rev3', [])
1346
self.assertFindDistance(4, graph, b'rev4', [])
1348
def test_rev_is_ghost(self):
1349
graph = self.make_graph(ancestry_1)
1350
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1351
graph.find_distance_to_null, b'rev_missing', [])
1352
self.assertEqual(b'rev_missing', e.revision_id)
1353
self.assertEqual(b'rev_missing', e.ghost_revision_id)
1355
def test_ancestor_is_ghost(self):
1356
graph = self.make_graph({b'rev': [b'parent']})
1357
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1358
graph.find_distance_to_null, b'rev', [])
1359
self.assertEqual(b'rev', e.revision_id)
1360
self.assertEqual(b'parent', e.ghost_revision_id)
1362
def test_known_in_ancestry(self):
1363
graph = self.make_graph(ancestry_1)
1364
self.assertFindDistance(2, graph, b'rev2a', [(b'rev1', 1)])
1365
self.assertFindDistance(3, graph, b'rev3', [(b'rev2a', 2)])
1367
def test_known_in_ancestry_limits(self):
1368
graph = self.make_breaking_graph(ancestry_1, [b'rev1'])
1369
self.assertFindDistance(4, graph, b'rev4', [(b'rev3', 3)])
1371
def test_target_is_ancestor(self):
1372
graph = self.make_graph(ancestry_1)
1373
self.assertFindDistance(2, graph, b'rev2a', [(b'rev3', 3)])
1375
def test_target_is_ancestor_limits(self):
1376
"""We shouldn't search all history if we run into ourselves"""
1377
graph = self.make_breaking_graph(ancestry_1, [b'rev1'])
1378
self.assertFindDistance(3, graph, b'rev3', [(b'rev4', 4)])
1380
def test_target_parallel_to_known_limits(self):
1381
# Even though the known revision isn't part of the other ancestry, they
1382
# eventually converge
1383
graph = self.make_breaking_graph(with_tail, [b'a'])
1384
self.assertFindDistance(6, graph, b'f', [(b'g', 6)])
1385
self.assertFindDistance(7, graph, b'h', [(b'g', 6)])
1386
self.assertFindDistance(8, graph, b'i', [(b'g', 6)])
1387
self.assertFindDistance(6, graph, b'g', [(b'i', 8)])
1390
class TestFindMergeOrder(TestGraphBase):
1392
def assertMergeOrder(self, expected, graph, tip, base_revisions):
1393
self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1395
def test_parents(self):
1396
graph = self.make_graph(ancestry_1)
1397
self.assertMergeOrder([b'rev3', b'rev2b'], graph, b'rev4',
1398
[b'rev3', b'rev2b'])
1399
self.assertMergeOrder([b'rev3', b'rev2b'], graph, b'rev4',
1400
[b'rev2b', b'rev3'])
1402
def test_ancestors(self):
1403
graph = self.make_graph(ancestry_1)
1404
self.assertMergeOrder([b'rev1', b'rev2b'], graph, b'rev4',
1405
[b'rev1', b'rev2b'])
1406
self.assertMergeOrder([b'rev1', b'rev2b'], graph, b'rev4',
1407
[b'rev2b', b'rev1'])
1409
def test_shortcut_one_ancestor(self):
1410
# When we have enough info, we can stop searching
1411
graph = self.make_breaking_graph(
1412
ancestry_1, [b'rev3', b'rev2b', b'rev4'])
1413
# Single ancestors shortcut right away
1414
self.assertMergeOrder([b'rev3'], graph, b'rev4', [b'rev3'])
1416
def test_shortcut_after_one_ancestor(self):
1417
graph = self.make_breaking_graph(ancestry_1, [b'rev2a', b'rev2b'])
1418
self.assertMergeOrder([b'rev3', b'rev1'], graph,
1419
b'rev4', [b'rev1', b'rev3'])
1422
class TestFindDescendants(TestGraphBase):
1424
def test_find_descendants_rev1_rev3(self):
1425
graph = self.make_graph(ancestry_1)
1426
descendants = graph.find_descendants(b'rev1', b'rev3')
1427
self.assertEqual({b'rev1', b'rev2a', b'rev3'}, descendants)
1429
def test_find_descendants_rev1_rev4(self):
1430
graph = self.make_graph(ancestry_1)
1431
descendants = graph.find_descendants(b'rev1', b'rev4')
1432
self.assertEqual({b'rev1', b'rev2a', b'rev2b', b'rev3', b'rev4'},
1435
def test_find_descendants_rev2a_rev4(self):
1436
graph = self.make_graph(ancestry_1)
1437
descendants = graph.find_descendants(b'rev2a', b'rev4')
1438
self.assertEqual({b'rev2a', b'rev3', b'rev4'}, descendants)
1441
class TestFindLefthandMerger(TestGraphBase):
1443
def check_merger(self, result, ancestry, merged, tip):
1444
graph = self.make_graph(ancestry)
1445
self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
1447
def test_find_lefthand_merger_rev2b(self):
1448
self.check_merger(b'rev4', ancestry_1, b'rev2b', b'rev4')
1450
def test_find_lefthand_merger_rev2a(self):
1451
self.check_merger(b'rev2a', ancestry_1, b'rev2a', b'rev4')
1453
def test_find_lefthand_merger_rev4(self):
1454
self.check_merger(None, ancestry_1, b'rev4', b'rev2a')
1456
def test_find_lefthand_merger_f(self):
1457
self.check_merger(b'i', complex_shortcut, b'f', b'm')
1459
def test_find_lefthand_merger_g(self):
1460
self.check_merger(b'i', complex_shortcut, b'g', b'm')
1462
def test_find_lefthand_merger_h(self):
1463
self.check_merger(b'n', complex_shortcut, b'h', b'n')
1466
class TestGetChildMap(TestGraphBase):
1468
def test_get_child_map(self):
1469
graph = self.make_graph(ancestry_1)
1470
child_map = graph.get_child_map([b'rev4', b'rev3', b'rev2a', b'rev2b'])
1471
self.assertEqual({b'rev1': [b'rev2a', b'rev2b'],
1472
b'rev2a': [b'rev3'],
1473
b'rev2b': [b'rev4'],
1474
b'rev3': [b'rev4']},
1478
class TestCachingParentsProvider(tests.TestCase):
1479
"""These tests run with:
1481
self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1483
self.caching_pp, a CachingParentsProvider layered on inst_pp.
1487
super(TestCachingParentsProvider, self).setUp()
1488
dict_pp = _mod_graph.DictParentsProvider({b'a': (b'b',)})
1489
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1490
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1492
def test_get_parent_map(self):
1493
"""Requesting the same revision should be returned from cache"""
1494
self.assertEqual({}, self.caching_pp._cache)
1496
{b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a']))
1497
self.assertEqual([b'a'], self.inst_pp.calls)
1499
{b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a']))
1500
# No new call, as it should have been returned from the cache
1501
self.assertEqual([b'a'], self.inst_pp.calls)
1502
self.assertEqual({b'a': (b'b',)}, self.caching_pp._cache)
1504
def test_get_parent_map_not_present(self):
1505
"""The cache should also track when a revision doesn't exist"""
1506
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1507
self.assertEqual([b'b'], self.inst_pp.calls)
1508
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1510
self.assertEqual([b'b'], self.inst_pp.calls)
1512
def test_get_parent_map_mixed(self):
1513
"""Anything that can be returned from cache, should be"""
1514
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1515
self.assertEqual([b'b'], self.inst_pp.calls)
1516
self.assertEqual({b'a': (b'b',)},
1517
self.caching_pp.get_parent_map([b'a', b'b']))
1518
self.assertEqual([b'b', b'a'], self.inst_pp.calls)
1520
def test_get_parent_map_repeated(self):
1521
"""Asking for the same parent 2x will only forward 1 request."""
1522
self.assertEqual({b'a': (b'b',)},
1523
self.caching_pp.get_parent_map([b'b', b'a', b'b']))
1524
# Use sorted because we don't care about the order, just that each is
1525
# only present 1 time.
1526
self.assertEqual([b'a', b'b'], sorted(self.inst_pp.calls))
1528
def test_note_missing_key(self):
1529
"""After noting that a key is missing it is cached."""
1530
self.caching_pp.note_missing_key(b'b')
1531
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1532
self.assertEqual([], self.inst_pp.calls)
1533
self.assertEqual({b'b'}, self.caching_pp.missing_keys)
1535
def test_get_cached_parent_map(self):
1536
self.assertEqual({}, self.caching_pp.get_cached_parent_map([b'a']))
1537
self.assertEqual([], self.inst_pp.calls)
1539
{b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a']))
1540
self.assertEqual([b'a'], self.inst_pp.calls)
1541
self.assertEqual({b'a': (b'b',)},
1542
self.caching_pp.get_cached_parent_map([b'a']))
1545
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1546
"""Test the behaviour when parents are provided that were not requested."""
1549
super(TestCachingParentsProviderExtras, self).setUp()
1551
class ExtraParentsProvider(object):
1553
def get_parent_map(self, keys):
1554
return {b'rev1': [], b'rev2': [b'rev1', ]}
1556
self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1557
self.caching_pp = _mod_graph.CachingParentsProvider(
1558
get_parent_map=self.inst_pp.get_parent_map)
1560
def test_uncached(self):
1561
self.caching_pp.disable_cache()
1562
self.assertEqual({b'rev1': []},
1563
self.caching_pp.get_parent_map([b'rev1']))
1564
self.assertEqual([b'rev1'], self.inst_pp.calls)
1565
self.assertIs(None, self.caching_pp._cache)
1567
def test_cache_initially_empty(self):
1568
self.assertEqual({}, self.caching_pp._cache)
1570
def test_cached(self):
1571
self.assertEqual({b'rev1': []},
1572
self.caching_pp.get_parent_map([b'rev1']))
1573
self.assertEqual([b'rev1'], self.inst_pp.calls)
1574
self.assertEqual({b'rev1': [], b'rev2': [b'rev1']},
1575
self.caching_pp._cache)
1576
self.assertEqual({b'rev1': []},
1577
self.caching_pp.get_parent_map([b'rev1']))
1578
self.assertEqual([b'rev1'], self.inst_pp.calls)
1580
def test_disable_cache_clears_cache(self):
1581
# Put something in the cache
1582
self.caching_pp.get_parent_map([b'rev1'])
1583
self.assertEqual(2, len(self.caching_pp._cache))
1584
self.caching_pp.disable_cache()
1585
self.assertIs(None, self.caching_pp._cache)
1587
def test_enable_cache_raises(self):
1588
e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1589
self.assertEqual('Cache enabled when already enabled.', str(e))
1591
def test_cache_misses(self):
1592
self.caching_pp.get_parent_map([b'rev3'])
1593
self.caching_pp.get_parent_map([b'rev3'])
1594
self.assertEqual([b'rev3'], self.inst_pp.calls)
1596
def test_no_cache_misses(self):
1597
self.caching_pp.disable_cache()
1598
self.caching_pp.enable_cache(cache_misses=False)
1599
self.caching_pp.get_parent_map([b'rev3'])
1600
self.caching_pp.get_parent_map([b'rev3'])
1601
self.assertEqual([b'rev3', b'rev3'], self.inst_pp.calls)
1603
def test_cache_extras(self):
1604
self.assertEqual({}, self.caching_pp.get_parent_map([b'rev3']))
1605
self.assertEqual({b'rev2': [b'rev1']},
1606
self.caching_pp.get_parent_map([b'rev2']))
1607
self.assertEqual([b'rev3'], self.inst_pp.calls)
1609
def test_extras_using_cached(self):
1610
self.assertEqual({}, self.caching_pp.get_cached_parent_map([b'rev3']))
1611
self.assertEqual({}, self.caching_pp.get_parent_map([b'rev3']))
1612
self.assertEqual({b'rev2': [b'rev1']},
1613
self.caching_pp.get_cached_parent_map([b'rev2']))
1614
self.assertEqual([b'rev3'], self.inst_pp.calls)
1617
class TestCollapseLinearRegions(tests.TestCase):
1619
def assertCollapsed(self, collapsed, original):
1620
self.assertEqual(collapsed,
1621
_mod_graph.collapse_linear_regions(original))
1623
def test_collapse_nothing(self):
1624
d = {1: [2, 3], 2: [], 3: []}
1625
self.assertCollapsed(d, d)
1626
d = {1: [2], 2: [3, 4], 3: [5], 4: [5], 5: []}
1627
self.assertCollapsed(d, d)
1629
def test_collapse_chain(self):
1630
# Any time we have a linear chain, we should be able to collapse
1631
d = {1: [2], 2: [3], 3: [4], 4: [5], 5: []}
1632
self.assertCollapsed({1: [5], 5: []}, d)
1633
d = {5: [4], 4: [3], 3: [2], 2: [1], 1: []}
1634
self.assertCollapsed({5: [1], 1: []}, d)
1635
d = {5: [3], 3: [4], 4: [1], 1: [2], 2: []}
1636
self.assertCollapsed({5: [2], 2: []}, d)
1638
def test_collapse_with_multiple_children(self):
1649
# 4 and 5 cannot be removed because 6 has 2 children
1650
# 2 and 3 cannot be removed because 1 has 2 parents
1651
d = {1: [2, 3], 2: [4], 4: [6], 3: [5], 5: [6], 6: [7], 7: []}
1652
self.assertCollapsed(d, d)
1655
class TestGraphThunkIdsToKeys(tests.TestCase):
1657
def test_heads(self):
1663
d = {(b'D',): [(b'B',), (b'C',)], (b'C',): [(b'A',)],
1664
(b'B',): [(b'A',)], (b'A',): []}
1665
g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1666
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1667
self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'A'])))
1668
self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'B'])))
1669
self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'C'])))
1670
self.assertEqual([b'B', b'C'], sorted(graph_thunk.heads([b'B', b'C'])))
1672
def test_add_node(self):
1673
d = {(b'C',): [(b'A',)], (b'B',): [(b'A',)], (b'A',): []}
1674
g = _mod_graph.KnownGraph(d)
1675
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1676
graph_thunk.add_node(b"D", [b"A", b"C"])
1677
self.assertEqual([b'B', b'D'],
1678
sorted(graph_thunk.heads([b'D', b'B', b'A'])))
1680
def test_merge_sort(self):
1681
d = {(b'C',): [(b'A',)], (b'B',): [(b'A',)], (b'A',): []}
1682
g = _mod_graph.KnownGraph(d)
1683
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1684
graph_thunk.add_node(b"D", [b"A", b"C"])
1685
self.assertEqual([(b'C', 0, (2,), False), (b'A', 0, (1,), True)],
1686
[(n.key, n.merge_depth, n.revno, n.end_of_merge)
1687
for n in graph_thunk.merge_sort(b'C')])
1690
class TestStackedParentsProvider(tests.TestCase):
1693
super(TestStackedParentsProvider, self).setUp()
1696
def get_shared_provider(self, info, ancestry, has_cached):
1697
pp = _mod_graph.DictParentsProvider(ancestry)
1699
pp.get_cached_parent_map = pp.get_parent_map
1700
return SharedInstrumentedParentsProvider(pp, self.calls, info)
1702
def test_stacked_parents_provider(self):
1703
parents1 = _mod_graph.DictParentsProvider({b'rev2': [b'rev3']})
1704
parents2 = _mod_graph.DictParentsProvider({b'rev1': [b'rev4']})
1705
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1706
self.assertEqual({b'rev1': [b'rev4'], b'rev2': [b'rev3']},
1707
stacked.get_parent_map([b'rev1', b'rev2']))
1708
self.assertEqual({b'rev2': [b'rev3'], b'rev1': [b'rev4']},
1709
stacked.get_parent_map([b'rev2', b'rev1']))
1710
self.assertEqual({b'rev2': [b'rev3']},
1711
stacked.get_parent_map([b'rev2', b'rev2']))
1712
self.assertEqual({b'rev1': [b'rev4']},
1713
stacked.get_parent_map([b'rev1', b'rev1']))
1715
def test_stacked_parents_provider_overlapping(self):
1716
# rev2 is availible in both providers.
1720
parents1 = _mod_graph.DictParentsProvider({b'rev2': [b'rev1']})
1721
parents2 = _mod_graph.DictParentsProvider({b'rev2': [b'rev1']})
1722
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1723
self.assertEqual({b'rev2': [b'rev1']},
1724
stacked.get_parent_map([b'rev2']))
1726
def test_handles_no_get_cached_parent_map(self):
1727
# this shows that we both handle when a provider doesn't implement
1728
# get_cached_parent_map
1729
pp1 = self.get_shared_provider(b'pp1', {b'rev2': (b'rev1',)},
1731
pp2 = self.get_shared_provider(b'pp2', {b'rev2': (b'rev1',)},
1733
stacked = _mod_graph.StackedParentsProvider([pp1, pp2])
1734
self.assertEqual({b'rev2': (b'rev1',)},
1735
stacked.get_parent_map([b'rev2']))
1736
# No call on b'pp1' because it doesn't provide get_cached_parent_map
1737
self.assertEqual([(b'pp2', 'cached', [b'rev2'])], self.calls)
1739
def test_query_order(self):
1740
# We should call get_cached_parent_map on all providers before we call
1741
# get_parent_map. Further, we should track what entries we have found,
1742
# and not re-try them.
1743
pp1 = self.get_shared_provider(b'pp1', {b'a': ()}, has_cached=True)
1744
pp2 = self.get_shared_provider(
1745
b'pp2', {b'c': (b'b',)}, has_cached=False)
1746
pp3 = self.get_shared_provider(
1747
b'pp3', {b'b': (b'a',)}, has_cached=True)
1748
stacked = _mod_graph.StackedParentsProvider([pp1, pp2, pp3])
1749
self.assertEqual({b'a': (), b'b': (b'a',), b'c': (b'b',)},
1750
stacked.get_parent_map([b'a', b'b', b'c', b'd']))
1751
self.assertEqual([(b'pp1', 'cached', [b'a', b'b', b'c', b'd']),
1752
# No call to pp2, because it doesn't have cached
1753
(b'pp3', 'cached', [b'b', b'c', b'd']),
1754
(b'pp1', [b'c', b'd']),
1755
(b'pp2', [b'c', b'd']),
added
removed
breezy/tests/test_graph.py
