1
# Copyright (C) 2007 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23
from bzrlib.revision import NULL_REVISION
24
from bzrlib.tests import TestCaseWithMemoryTransport
38
ancestry_1 = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
39
'rev3': ['rev2a'], 'rev4': ['rev3', 'rev2b']}
53
ancestry_2 = {'rev1a': [NULL_REVISION], 'rev2a': ['rev1a'],
54
'rev1b': [NULL_REVISION], 'rev3a': ['rev2a'], 'rev4a': ['rev3a']}
57
# Criss cross ancestry
68
criss_cross = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
69
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2a']}
83
criss_cross2 = {'rev1a': [NULL_REVISION], 'rev1b': [NULL_REVISION],
84
'rev2a': ['rev1a', 'rev1b'], 'rev2b': ['rev1b', 'rev1a']}
96
mainline = {'rev1': [NULL_REVISION], 'rev2a': ['rev1', 'rev2b'],
109
feature_branch = {'rev1': [NULL_REVISION],
110
'rev2b': ['rev1'], 'rev3b': ['rev2b']}
121
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
122
'rev2b': ['rev1'], 'rev2c': ['rev1'],
123
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
125
# Extended history shortcut
137
extended_history_shortcut = {'a': [NULL_REVISION],
146
# Both sides will see 'A' first, even though it is actually a decendent of a
147
# different common revision.
161
double_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
162
'd':['c'], 'e':['c'], 'f':['a', 'd'],
166
# This has a failure mode in that a shortcut will find some nodes in common,
167
# but the common searcher won't have time to find that one branch is actually
168
# in common. The extra nodes at the beginning are because we want to avoid
169
# walking off the graph. Specifically, node G should be considered common, but
170
# is likely to be seen by M long before the common searcher finds it.
193
complex_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
194
'e':['d'], 'f':['d'], 'g':['f'], 'h':['f'],
195
'i':['e', 'g'], 'j':['g'], 'k':['j'],
196
'l':['k'], 'm':['i', 'l'], 'n':['l', 'h']}
236
complex_shortcut2 = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
237
'e':['d'], 'f':['e'], 'g':['f'], 'h':['d'], 'i':['g'],
238
'j':['h'], 'k':['h', 'i'], 'l':['k'], 'm':['l'], 'n':['m'],
239
'o':['n'], 'p':['o'], 'q':['p'], 'r':['q'], 's':['r'],
240
't':['i', 's'], 'u':['s', 'j'],
243
# Graph where different walkers will race to find the common and uncommon
286
# y is found to be common right away, but is the start of a long series of
288
# o is actually common, but the i-j shortcut makes it look like it is actually
289
# unique to j at first, you have to traverse all of y->o to find it.
290
# q,n give the walker from j a common point to stop searching, as does p,f.
291
# k-n exists so that the second pass still has nodes that are worth searching,
292
# rather than instantly cancelling the extra walker.
294
racing_shortcuts = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
295
'e':['d'], 'f':['e'], 'g':['f'], 'h':['g'], 'i':['h', 'o'], 'j':['i', 'y'],
296
'k':['d'], 'l':['k'], 'm':['l'], 'n':['m'], 'o':['n', 'g'], 'p':['f'],
297
'q':['p', 'm'], 'r':['o'], 's':['r'], 't':['s'], 'u':['t'], 'v':['u'],
298
'w':['v'], 'x':['w'], 'y':['x'], 'z':['x', 'q']}
301
# A graph with multiple nodes unique to one side.
340
multiple_interesting_unique = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
341
'd':['c'], 'e':['d'], 'f':['d'], 'g':['e'], 'h':['e'], 'i':['f'],
342
'j':['g'], 'k':['g'], 'l':['h'], 'm':['i'], 'n':['k', 'l'],
343
'o':['m'], 'p':['m', 'l'], 'q':['n', 'o'], 'r':['q'], 's':['r'],
344
't':['s'], 'u':['t'], 'v':['u'], 'w':['v'], 'x':['w'],
345
'y':['j', 'x'], 'z':['x', 'p']}
348
# Shortcut with extra root
349
# We have a long history shortcut, and an extra root, which is why we can't
350
# stop searchers based on seeing NULL_REVISION
362
shortcut_extra_root = {'a': [NULL_REVISION],
367
'f': ['a', 'd', 'g'],
368
'g': [NULL_REVISION],
381
boundary = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e'], 'e': ['f'],
385
# A graph that contains a ghost
396
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
397
'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
401
class InstrumentedParentsProvider(object):
403
def __init__(self, parents_provider):
405
self._real_parents_provider = parents_provider
407
def get_parent_map(self, nodes):
408
self.calls.extend(nodes)
409
return self._real_parents_provider.get_parent_map(nodes)
412
class TestGraph(TestCaseWithMemoryTransport):
414
def make_graph(self, ancestors):
415
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
417
def prepare_memory_tree(self, location):
418
tree = self.make_branch_and_memory_tree(location)
423
def build_ancestry(self, tree, ancestors):
424
"""Create an ancestry as specified by a graph dict
426
:param tree: A tree to use
427
:param ancestors: a dict of {node: [node_parent, ...]}
429
pending = [NULL_REVISION]
431
for descendant, parents in ancestors.iteritems():
432
for parent in parents:
433
descendants.setdefault(parent, []).append(descendant)
434
while len(pending) > 0:
435
cur_node = pending.pop()
436
for descendant in descendants.get(cur_node, []):
437
if tree.branch.repository.has_revision(descendant):
439
parents = [p for p in ancestors[descendant] if p is not
441
if len([p for p in parents if not
442
tree.branch.repository.has_revision(p)]) > 0:
444
tree.set_parent_ids(parents)
446
left_parent = parents[0]
448
left_parent = NULL_REVISION
449
tree.branch.set_last_revision_info(
450
len(tree.branch._lefthand_history(left_parent)),
452
tree.commit(descendant, rev_id=descendant)
453
pending.append(descendant)
456
"""Test finding least common ancestor.
458
ancestry_1 should always have a single common ancestor
460
graph = self.make_graph(ancestry_1)
461
self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
462
self.assertEqual(set([NULL_REVISION]),
463
graph.find_lca(NULL_REVISION, NULL_REVISION))
464
self.assertEqual(set([NULL_REVISION]),
465
graph.find_lca(NULL_REVISION, 'rev1'))
466
self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
467
self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
469
def test_no_unique_lca(self):
470
"""Test error when one revision is not in the graph"""
471
graph = self.make_graph(ancestry_1)
472
self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
475
def test_lca_criss_cross(self):
476
"""Test least-common-ancestor after a criss-cross merge."""
477
graph = self.make_graph(criss_cross)
478
self.assertEqual(set(['rev2a', 'rev2b']),
479
graph.find_lca('rev3a', 'rev3b'))
480
self.assertEqual(set(['rev2b']),
481
graph.find_lca('rev3a', 'rev3b', 'rev2b'))
483
def test_lca_shortcut(self):
484
"""Test least-common ancestor on this history shortcut"""
485
graph = self.make_graph(history_shortcut)
486
self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
488
def test_recursive_unique_lca(self):
489
"""Test finding a unique least common ancestor.
491
ancestry_1 should always have a single common ancestor
493
graph = self.make_graph(ancestry_1)
494
self.assertEqual(NULL_REVISION,
495
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
496
self.assertEqual(NULL_REVISION,
497
graph.find_unique_lca(NULL_REVISION, 'rev1'))
498
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
499
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
500
self.assertEqual(('rev1', 1,),
501
graph.find_unique_lca('rev2a', 'rev2b',
504
def assertRemoveDescendants(self, expected, graph, revisions):
505
parents = graph.get_parent_map(revisions)
506
self.assertEqual(expected,
507
graph._remove_simple_descendants(revisions, parents))
509
def test__remove_simple_descendants(self):
510
graph = self.make_graph(ancestry_1)
511
self.assertRemoveDescendants(set(['rev1']), graph,
512
set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']))
514
def test__remove_simple_descendants_disjoint(self):
515
graph = self.make_graph(ancestry_1)
516
self.assertRemoveDescendants(set(['rev1', 'rev3']), graph,
517
set(['rev1', 'rev3']))
519
def test__remove_simple_descendants_chain(self):
520
graph = self.make_graph(ancestry_1)
521
self.assertRemoveDescendants(set(['rev1']), graph,
522
set(['rev1', 'rev2a', 'rev3']))
524
def test__remove_simple_descendants_siblings(self):
525
graph = self.make_graph(ancestry_1)
526
self.assertRemoveDescendants(set(['rev2a', 'rev2b']), graph,
527
set(['rev2a', 'rev2b', 'rev3']))
529
def test_unique_lca_criss_cross(self):
530
"""Ensure we don't pick non-unique lcas in a criss-cross"""
531
graph = self.make_graph(criss_cross)
532
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
533
lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
534
self.assertEqual('rev1', lca)
535
self.assertEqual(2, steps)
537
def test_unique_lca_null_revision(self):
538
"""Ensure we pick NULL_REVISION when necessary"""
539
graph = self.make_graph(criss_cross2)
540
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
541
self.assertEqual(NULL_REVISION,
542
graph.find_unique_lca('rev2a', 'rev2b'))
544
def test_unique_lca_null_revision2(self):
545
"""Ensure we pick NULL_REVISION when necessary"""
546
graph = self.make_graph(ancestry_2)
547
self.assertEqual(NULL_REVISION,
548
graph.find_unique_lca('rev4a', 'rev1b'))
550
def test_lca_double_shortcut(self):
551
graph = self.make_graph(double_shortcut)
552
self.assertEqual('c', graph.find_unique_lca('f', 'g'))
554
def test_common_ancestor_two_repos(self):
555
"""Ensure we do unique_lca using data from two repos"""
556
mainline_tree = self.prepare_memory_tree('mainline')
557
self.build_ancestry(mainline_tree, mainline)
558
self.addCleanup(mainline_tree.unlock)
560
# This is cheating, because the revisions in the graph are actually
561
# different revisions, despite having the same revision-id.
562
feature_tree = self.prepare_memory_tree('feature')
563
self.build_ancestry(feature_tree, feature_branch)
564
self.addCleanup(feature_tree.unlock)
566
graph = mainline_tree.branch.repository.get_graph(
567
feature_tree.branch.repository)
568
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
570
def test_graph_difference(self):
571
graph = self.make_graph(ancestry_1)
572
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
573
self.assertEqual((set(), set(['rev1'])),
574
graph.find_difference(NULL_REVISION, 'rev1'))
575
self.assertEqual((set(['rev1']), set()),
576
graph.find_difference('rev1', NULL_REVISION))
577
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
578
graph.find_difference('rev3', 'rev2b'))
579
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
580
graph.find_difference('rev4', 'rev2b'))
582
def test_graph_difference_separate_ancestry(self):
583
graph = self.make_graph(ancestry_2)
584
self.assertEqual((set(['rev1a']), set(['rev1b'])),
585
graph.find_difference('rev1a', 'rev1b'))
586
self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
588
graph.find_difference('rev4a', 'rev1b'))
590
def test_graph_difference_criss_cross(self):
591
graph = self.make_graph(criss_cross)
592
self.assertEqual((set(['rev3a']), set(['rev3b'])),
593
graph.find_difference('rev3a', 'rev3b'))
594
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
595
graph.find_difference('rev2a', 'rev3b'))
597
def test_graph_difference_extended_history(self):
598
graph = self.make_graph(extended_history_shortcut)
599
self.assertEqual((set(['e']), set(['f'])),
600
graph.find_difference('e', 'f'))
601
self.assertEqual((set(['f']), set(['e'])),
602
graph.find_difference('f', 'e'))
604
def test_graph_difference_double_shortcut(self):
605
graph = self.make_graph(double_shortcut)
606
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
607
graph.find_difference('f', 'g'))
609
def test_graph_difference_complex_shortcut(self):
610
graph = self.make_graph(complex_shortcut)
611
self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
612
graph.find_difference('m', 'n'))
614
def test_graph_difference_complex_shortcut2(self):
615
graph = self.make_graph(complex_shortcut2)
616
self.assertEqual((set(['t']), set(['j', 'u'])),
617
graph.find_difference('t', 'u'))
619
def test_graph_difference_shortcut_extra_root(self):
620
graph = self.make_graph(shortcut_extra_root)
621
self.assertEqual((set(['e']), set(['f', 'g'])),
622
graph.find_difference('e', 'f'))
624
def test_stacked_parents_provider(self):
625
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
626
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
627
stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
628
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
629
stacked.get_parent_map(['rev1', 'rev2']))
630
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
631
stacked.get_parent_map(['rev2', 'rev1']))
632
self.assertEqual({'rev2':['rev3']},
633
stacked.get_parent_map(['rev2', 'rev2']))
634
self.assertEqual({'rev1':['rev4']},
635
stacked.get_parent_map(['rev1', 'rev1']))
637
def test_iter_topo_order(self):
638
graph = self.make_graph(ancestry_1)
639
args = ['rev2a', 'rev3', 'rev1']
640
topo_args = list(graph.iter_topo_order(args))
641
self.assertEqual(set(args), set(topo_args))
642
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
643
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
645
def test_is_ancestor(self):
646
graph = self.make_graph(ancestry_1)
647
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
648
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
649
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
650
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
651
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
652
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
653
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
654
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
655
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
656
instrumented_provider = InstrumentedParentsProvider(graph)
657
instrumented_graph = _mod_graph.Graph(instrumented_provider)
658
instrumented_graph.is_ancestor('rev2a', 'rev2b')
659
self.assertTrue('null:' not in instrumented_provider.calls)
661
def test_is_ancestor_boundary(self):
662
"""Ensure that we avoid searching the whole graph.
664
This requires searching through b as a common ancestor, so we
665
can identify that e is common.
667
graph = self.make_graph(boundary)
668
instrumented_provider = InstrumentedParentsProvider(graph)
669
graph = _mod_graph.Graph(instrumented_provider)
670
self.assertFalse(graph.is_ancestor('a', 'c'))
671
self.assertTrue('null:' not in instrumented_provider.calls)
673
def test_iter_ancestry(self):
674
nodes = boundary.copy()
675
nodes[NULL_REVISION] = ()
676
graph = self.make_graph(nodes)
677
expected = nodes.copy()
678
expected.pop('a') # 'a' is not in the ancestry of 'c', all the
680
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
681
self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
683
def test_iter_ancestry_with_ghost(self):
684
graph = self.make_graph(with_ghost)
685
expected = with_ghost.copy()
686
# 'a' is not in the ancestry of 'c', and 'g' is a ghost
688
self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
690
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
692
def test_filter_candidate_lca(self):
693
"""Test filter_candidate_lca for a corner case
695
This tests the case where we encounter the end of iteration for 'e'
696
in the same pass as we discover that 'd' is an ancestor of 'e', and
697
therefore 'e' can't be an lca.
699
To compensate for different dict orderings on other Python
700
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
702
# This test is sensitive to the iteration order of dicts. It will
703
# pass incorrectly if 'e' and 'a' sort before 'c'
712
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
713
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
714
self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
716
def test_heads_null(self):
717
graph = self.make_graph(ancestry_1)
718
self.assertEqual(set(['null:']), graph.heads(['null:']))
719
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
720
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
721
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
722
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
724
def test_heads_one(self):
725
# A single node will always be a head
726
graph = self.make_graph(ancestry_1)
727
self.assertEqual(set(['null:']), graph.heads(['null:']))
728
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
729
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
730
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
731
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
732
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
734
def test_heads_single(self):
735
graph = self.make_graph(ancestry_1)
736
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
737
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
738
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
739
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
740
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
741
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
742
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
743
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
745
def test_heads_two_heads(self):
746
graph = self.make_graph(ancestry_1)
747
self.assertEqual(set(['rev2a', 'rev2b']),
748
graph.heads(['rev2a', 'rev2b']))
749
self.assertEqual(set(['rev3', 'rev2b']),
750
graph.heads(['rev3', 'rev2b']))
752
def test_heads_criss_cross(self):
753
graph = self.make_graph(criss_cross)
754
self.assertEqual(set(['rev2a']),
755
graph.heads(['rev2a', 'rev1']))
756
self.assertEqual(set(['rev2b']),
757
graph.heads(['rev2b', 'rev1']))
758
self.assertEqual(set(['rev3a']),
759
graph.heads(['rev3a', 'rev1']))
760
self.assertEqual(set(['rev3b']),
761
graph.heads(['rev3b', 'rev1']))
762
self.assertEqual(set(['rev2a', 'rev2b']),
763
graph.heads(['rev2a', 'rev2b']))
764
self.assertEqual(set(['rev3a']),
765
graph.heads(['rev3a', 'rev2a']))
766
self.assertEqual(set(['rev3a']),
767
graph.heads(['rev3a', 'rev2b']))
768
self.assertEqual(set(['rev3a']),
769
graph.heads(['rev3a', 'rev2a', 'rev2b']))
770
self.assertEqual(set(['rev3b']),
771
graph.heads(['rev3b', 'rev2a']))
772
self.assertEqual(set(['rev3b']),
773
graph.heads(['rev3b', 'rev2b']))
774
self.assertEqual(set(['rev3b']),
775
graph.heads(['rev3b', 'rev2a', 'rev2b']))
776
self.assertEqual(set(['rev3a', 'rev3b']),
777
graph.heads(['rev3a', 'rev3b']))
778
self.assertEqual(set(['rev3a', 'rev3b']),
779
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
781
def test_heads_shortcut(self):
782
graph = self.make_graph(history_shortcut)
784
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
785
graph.heads(['rev2a', 'rev2b', 'rev2c']))
786
self.assertEqual(set(['rev3a', 'rev3b']),
787
graph.heads(['rev3a', 'rev3b']))
788
self.assertEqual(set(['rev3a', 'rev3b']),
789
graph.heads(['rev2a', 'rev3a', 'rev3b']))
790
self.assertEqual(set(['rev2a', 'rev3b']),
791
graph.heads(['rev2a', 'rev3b']))
792
self.assertEqual(set(['rev2c', 'rev3a']),
793
graph.heads(['rev2c', 'rev3a']))
795
def _run_heads_break_deeper(self, graph_dict, search):
796
"""Run heads on a graph-as-a-dict.
798
If the search asks for the parents of 'deeper' the test will fail.
802
def get_parent_map(keys):
806
self.fail('key deeper was accessed')
807
result[key] = graph_dict[key]
810
an_obj.get_parent_map = get_parent_map
811
graph = _mod_graph.Graph(an_obj)
812
return graph.heads(search)
814
def test_heads_limits_search(self):
815
# test that a heads query does not search all of history
821
self.assertEqual(set(['left', 'right']),
822
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
824
def test_heads_limits_search_assymetric(self):
825
# test that a heads query does not search all of history
828
'midleft':['common'],
830
'common':['aftercommon'],
831
'aftercommon':['deeper'],
833
self.assertEqual(set(['left', 'right']),
834
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
836
def test_heads_limits_search_common_search_must_continue(self):
837
# test that common nodes are still queried, preventing
838
# all-the-way-to-origin behaviour in the following graph:
840
'h1':['shortcut', 'common1'],
842
'shortcut':['common2'],
843
'common1':['common2'],
844
'common2':['deeper'],
846
self.assertEqual(set(['h1', 'h2']),
847
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
849
def test_breadth_first_search_start_ghosts(self):
850
graph = self.make_graph({})
851
# with_ghosts reports the ghosts
852
search = graph._make_breadth_first_searcher(['a-ghost'])
853
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
854
self.assertRaises(StopIteration, search.next_with_ghosts)
856
search = graph._make_breadth_first_searcher(['a-ghost'])
857
self.assertEqual(set(['a-ghost']), search.next())
858
self.assertRaises(StopIteration, search.next)
860
def test_breadth_first_search_deep_ghosts(self):
861
graph = self.make_graph({
863
'present':['child', 'ghost'],
866
# with_ghosts reports the ghosts
867
search = graph._make_breadth_first_searcher(['head'])
868
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
869
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
870
self.assertEqual((set(['child']), set(['ghost'])),
871
search.next_with_ghosts())
872
self.assertRaises(StopIteration, search.next_with_ghosts)
874
search = graph._make_breadth_first_searcher(['head'])
875
self.assertEqual(set(['head']), search.next())
876
self.assertEqual(set(['present']), search.next())
877
self.assertEqual(set(['child', 'ghost']),
879
self.assertRaises(StopIteration, search.next)
881
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
882
# To make the API robust, we allow calling both next() and
883
# next_with_ghosts() on the same searcher.
884
graph = self.make_graph({
886
'present':['child', 'ghost'],
889
# start with next_with_ghosts
890
search = graph._make_breadth_first_searcher(['head'])
891
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
892
self.assertEqual(set(['present']), search.next())
893
self.assertEqual((set(['child']), set(['ghost'])),
894
search.next_with_ghosts())
895
self.assertRaises(StopIteration, search.next)
897
search = graph._make_breadth_first_searcher(['head'])
898
self.assertEqual(set(['head']), search.next())
899
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
900
self.assertEqual(set(['child', 'ghost']),
902
self.assertRaises(StopIteration, search.next_with_ghosts)
904
def test_breadth_first_change_search(self):
905
# Changing the search should work with both next and next_with_ghosts.
906
graph = self.make_graph({
908
'present':['stopped'],
912
search = graph._make_breadth_first_searcher(['head'])
913
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
914
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
915
self.assertEqual(set(['present']),
916
search.stop_searching_any(['present']))
917
self.assertEqual((set(['other']), set(['other_ghost'])),
918
search.start_searching(['other', 'other_ghost']))
919
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
920
self.assertRaises(StopIteration, search.next_with_ghosts)
922
search = graph._make_breadth_first_searcher(['head'])
923
self.assertEqual(set(['head']), search.next())
924
self.assertEqual(set(['present']), search.next())
925
self.assertEqual(set(['present']),
926
search.stop_searching_any(['present']))
927
search.start_searching(['other', 'other_ghost'])
928
self.assertEqual(set(['other_2']), search.next())
929
self.assertRaises(StopIteration, search.next)
931
def assertSeenAndResult(self, instructions, search, next):
932
"""Check the results of .seen and get_result() for a seach.
934
:param instructions: A list of tuples:
935
(seen, recipe, included_keys, starts, stops).
936
seen, recipe and included_keys are results to check on the search
937
and the searches get_result(). starts and stops are parameters to
938
pass to start_searching and stop_searching_any during each
939
iteration, if they are not None.
940
:param search: The search to use.
941
:param next: A callable to advance the search.
943
for seen, recipe, included_keys, starts, stops in instructions:
945
if starts is not None:
946
search.start_searching(starts)
947
if stops is not None:
948
search.stop_searching_any(stops)
949
result = search.get_result()
950
self.assertEqual(recipe, result.get_recipe())
951
self.assertEqual(set(included_keys), result.get_keys())
952
self.assertEqual(seen, search.seen)
954
def test_breadth_first_get_result_excludes_current_pending(self):
955
graph = self.make_graph({
957
'child':[NULL_REVISION],
960
search = graph._make_breadth_first_searcher(['head'])
961
# At the start, nothing has been seen, to its all excluded:
962
result = search.get_result()
963
self.assertEqual((set(['head']), set(['head']), 0),
965
self.assertEqual(set(), result.get_keys())
966
self.assertEqual(set(), search.seen)
969
(set(['head']), (set(['head']), set(['child']), 1),
970
['head'], None, None),
971
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
972
['head', 'child'], None, None),
973
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
974
['head', 'child', NULL_REVISION], None, None),
976
self.assertSeenAndResult(expected, search, search.next)
977
# using next_with_ghosts:
978
search = graph._make_breadth_first_searcher(['head'])
979
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
981
def test_breadth_first_get_result_starts_stops(self):
982
graph = self.make_graph({
984
'child':[NULL_REVISION],
985
'otherhead':['otherchild'],
986
'otherchild':['excluded'],
987
'excluded':[NULL_REVISION],
990
search = graph._make_breadth_first_searcher([])
991
# Starting with nothing and adding a search works:
992
search.start_searching(['head'])
993
# head has been seen:
994
result = search.get_result()
995
self.assertEqual((set(['head']), set(['child']), 1),
997
self.assertEqual(set(['head']), result.get_keys())
998
self.assertEqual(set(['head']), search.seen)
1001
# stop at child, and start a new search at otherhead:
1002
# - otherhead counts as seen immediately when start_searching is
1004
(set(['head', 'child', 'otherhead']),
1005
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1006
['head', 'otherhead'], ['otherhead'], ['child']),
1007
(set(['head', 'child', 'otherhead', 'otherchild']),
1008
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1009
['head', 'otherhead', 'otherchild'], None, None),
1010
# stop searching excluded now
1011
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1012
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1013
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1015
self.assertSeenAndResult(expected, search, search.next)
1016
# using next_with_ghosts:
1017
search = graph._make_breadth_first_searcher([])
1018
search.start_searching(['head'])
1019
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1021
def test_breadth_first_stop_searching_not_queried(self):
1022
# A client should be able to say 'stop node X' even if X has not been
1023
# returned to the client.
1024
graph = self.make_graph({
1025
'head':['child', 'ghost1'],
1026
'child':[NULL_REVISION],
1029
search = graph._make_breadth_first_searcher(['head'])
1031
# NULL_REVISION and ghost1 have not been returned
1032
(set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
1033
['head'], None, [NULL_REVISION, 'ghost1']),
1034
# ghost1 has been returned, NULL_REVISION is to be returned in the
1036
(set(['head', 'child', 'ghost1']),
1037
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1038
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1040
self.assertSeenAndResult(expected, search, search.next)
1041
# using next_with_ghosts:
1042
search = graph._make_breadth_first_searcher(['head'])
1043
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1045
def test_breadth_first_get_result_ghosts_are_excluded(self):
1046
graph = self.make_graph({
1047
'head':['child', 'ghost'],
1048
'child':[NULL_REVISION],
1051
search = graph._make_breadth_first_searcher(['head'])
1055
(set(['head']), set(['ghost', 'child']), 1),
1056
['head'], None, None),
1057
(set(['head', 'child', 'ghost']),
1058
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1059
['head', 'child'], None, None),
1061
self.assertSeenAndResult(expected, search, search.next)
1062
# using next_with_ghosts:
1063
search = graph._make_breadth_first_searcher(['head'])
1064
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1066
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1067
graph = self.make_graph({
1069
'child':[NULL_REVISION],
1072
search = graph._make_breadth_first_searcher(['head'])
1075
(set(['head', 'ghost']),
1076
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1077
['head'], ['ghost'], None),
1078
(set(['head', 'child', 'ghost']),
1079
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1080
['head', 'child'], None, None),
1082
self.assertSeenAndResult(expected, search, search.next)
1083
# using next_with_ghosts:
1084
search = graph._make_breadth_first_searcher(['head'])
1085
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1087
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1088
graph = self.make_graph({
1089
'head':[NULL_REVISION],
1092
search = graph._make_breadth_first_searcher(['head'])
1096
(set(['head']), set([NULL_REVISION]), 1),
1097
['head'], None, None),
1098
(set(['head', NULL_REVISION]),
1099
(set(['head']), set([]), 2),
1100
['head', NULL_REVISION], None, None),
1102
self.assertSeenAndResult(expected, search, search.next)
1103
# using next_with_ghosts:
1104
search = graph._make_breadth_first_searcher(['head'])
1105
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1107
def test_breadth_first_search_get_result_after_StopIteration(self):
1108
# StopIteration should not invalid anything..
1109
graph = self.make_graph({
1110
'head':[NULL_REVISION],
1113
search = graph._make_breadth_first_searcher(['head'])
1117
(set(['head']), set([NULL_REVISION]), 1),
1118
['head'], None, None),
1119
(set(['head', 'ghost', NULL_REVISION]),
1120
(set(['head', 'ghost']), set(['ghost']), 2),
1121
['head', NULL_REVISION], ['ghost'], None),
1123
self.assertSeenAndResult(expected, search, search.next)
1124
self.assertRaises(StopIteration, search.next)
1125
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1126
result = search.get_result()
1127
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1128
result.get_recipe())
1129
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1130
# using next_with_ghosts:
1131
search = graph._make_breadth_first_searcher(['head'])
1132
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1133
self.assertRaises(StopIteration, search.next)
1134
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1135
result = search.get_result()
1136
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1137
result.get_recipe())
1138
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1141
class TestFindUniqueAncestors(tests.TestCase):
1143
def make_graph(self, ancestors):
1144
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
1146
def make_breaking_graph(self, ancestors, break_on):
1147
"""Make a Graph that raises an exception if we hit a node."""
1148
g = self.make_graph(ancestors)
1149
orig_parent_map = g.get_parent_map
1150
def get_parent_map(keys):
1151
bad_keys = set(keys).intersection(break_on)
1153
self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
1154
return orig_parent_map(keys)
1155
g.get_parent_map = get_parent_map
1158
def assertFindUniqueAncestors(self, graph, expected, node, common):
1159
actual = graph.find_unique_ancestors(node, common)
1160
self.assertEqual(expected, sorted(actual))
1162
def test_empty_set(self):
1163
graph = self.make_graph(ancestry_1)
1164
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1165
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1166
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1168
def test_single_node(self):
1169
graph = self.make_graph(ancestry_1)
1170
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1171
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1172
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1174
def test_minimal_ancestry(self):
1175
graph = self.make_breaking_graph(extended_history_shortcut,
1176
[NULL_REVISION, 'a', 'b'])
1177
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1179
graph = self.make_breaking_graph(extended_history_shortcut,
1181
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1183
graph = self.make_breaking_graph(complex_shortcut,
1185
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1186
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1187
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1188
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1190
def test_in_ancestry(self):
1191
graph = self.make_graph(ancestry_1)
1192
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1193
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1195
def test_multiple_revisions(self):
1196
graph = self.make_graph(ancestry_1)
1197
self.assertFindUniqueAncestors(graph,
1198
['rev4'], 'rev4', ['rev3', 'rev2b'])
1199
self.assertFindUniqueAncestors(graph,
1200
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1202
def test_complex_shortcut(self):
1203
graph = self.make_graph(complex_shortcut)
1204
self.assertFindUniqueAncestors(graph,
1205
['h', 'n'], 'n', ['m'])
1206
self.assertFindUniqueAncestors(graph,
1207
['e', 'i', 'm'], 'm', ['n'])
1209
def test_complex_shortcut2(self):
1210
graph = self.make_graph(complex_shortcut2)
1211
self.assertFindUniqueAncestors(graph,
1212
['j', 'u'], 'u', ['t'])
1213
self.assertFindUniqueAncestors(graph,
1216
def test_multiple_interesting_unique(self):
1217
graph = self.make_graph(multiple_interesting_unique)
1218
self.assertFindUniqueAncestors(graph,
1219
['j', 'y'], 'y', ['z'])
1220
self.assertFindUniqueAncestors(graph,
1221
['p', 'z'], 'z', ['y'])
1223
def test_racing_shortcuts(self):
1224
graph = self.make_graph(racing_shortcuts)
1225
self.assertFindUniqueAncestors(graph,
1226
['p', 'q', 'z'], 'z', ['y'])
1227
self.assertFindUniqueAncestors(graph,
1228
['h', 'i', 'j', 'y'], 'j', ['z'])
1231
class TestCachingParentsProvider(tests.TestCase):
1234
super(TestCachingParentsProvider, self).setUp()
1235
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1236
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1237
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1239
def test_get_parent_map(self):
1240
"""Requesting the same revision should be returned from cache"""
1241
self.assertEqual({}, self.caching_pp._cache)
1242
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1243
self.assertEqual(['a'], self.inst_pp.calls)
1244
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1245
# No new call, as it should have been returned from the cache
1246
self.assertEqual(['a'], self.inst_pp.calls)
1247
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1249
def test_get_parent_map_not_present(self):
1250
"""The cache should also track when a revision doesn't exist"""
1251
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1252
self.assertEqual(['b'], self.inst_pp.calls)
1253
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1255
self.assertEqual(['b'], self.inst_pp.calls)
1256
self.assertEqual({'b':None}, self.caching_pp._cache)
1258
def test_get_parent_map_mixed(self):
1259
"""Anything that can be returned from cache, should be"""
1260
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1261
self.assertEqual(['b'], self.inst_pp.calls)
1262
self.assertEqual({'a':('b',)},
1263
self.caching_pp.get_parent_map(['a', 'b']))
1264
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1266
def test_get_parent_map_repeated(self):
1267
"""Asking for the same parent 2x will only forward 1 request."""
1268
self.assertEqual({'a':('b',)},
1269
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1270
# Use sorted because we don't care about the order, just that each is
1271
# only present 1 time.
1272
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
added
removed
bzrlib/tests/test_graph.py
