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'],
238
'g':['f'], 'h':['d'], 'k':['h', 'i'], 'j':['h'],
239
'i':['g'], 'l':['k'], 'm':['l'],
240
'n':['m'], 't':['i', 's'], 'u':['s', 'j'],
241
'o':['n'], 'p':['o'], 'q':['p'],
242
'r':['q'], 's':['r'],
245
# Graph where different walkers will race to find the common and uncommon
288
# y is found to be common right away, but is the start of a long series of
290
# o is actually common, but the i-j shortcut makes it look like it is actually
291
# unique to j at first, you have to traverse all of y->o to find it.
292
# q,n give the walker from j a common point to stop searching, as does p,f.
293
# k-n exists so that the second pass still has nodes that are worth searching,
294
# rather than instantly cancelling the extra walker.
296
racing_shortcuts = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
297
'e':['d'], 'f':['e'], 'g':['f'], 'h':['g'], 'i':['h', 'o'], 'j':['i', 'y'],
298
'k':['d'], 'l':['k'], 'm':['l'], 'n':['m'], 'o':['n', 'g'], 'p':['f'],
299
'q':['p', 'm'], 'r':['o'], 's':['r'], 't':['s'], 'u':['t'], 'v':['u'],
300
'w':['v'], 'x':['w'], 'y':['x'], 'z':['x', 'q']}
303
# A graph with multiple nodes unique to one side.
342
multiple_interesting_unique = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
343
'd':['c'], 'e':['d'], 'f':['d'], 'g':['e'], 'h':['e'], 'i':['f'],
344
'j':['g'], 'k':['g'], 'l':['h'], 'm':['i'], 'n':['k', 'l'],
345
'o':['m'], 'p':['m', 'l'], 'q':['n', 'o'], 'r':['q'], 's':['r'],
346
't':['s'], 'u':['t'], 'v':['u'], 'w':['v'], 'x':['w'],
347
'y':['j', 'x'], 'z':['x', 'p']}
350
# Shortcut with extra root
351
# We have a long history shortcut, and an extra root, which is why we can't
352
# stop searchers based on seeing NULL_REVISION
364
shortcut_extra_root = {'a': [NULL_REVISION],
369
'f': ['a', 'd', 'g'],
370
'g': [NULL_REVISION],
383
boundary = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e'], 'e': ['f'],
387
# A graph that contains a ghost
398
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
399
'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
403
class InstrumentedParentsProvider(object):
405
def __init__(self, parents_provider):
407
self._real_parents_provider = parents_provider
409
def get_parent_map(self, nodes):
410
self.calls.extend(nodes)
411
return self._real_parents_provider.get_parent_map(nodes)
413
def get_parent_map(self, nodes):
414
self.calls.extend(nodes)
415
return self._real_parents_provider.get_parent_map(nodes)
418
class TestGraph(TestCaseWithMemoryTransport):
420
def make_graph(self, ancestors):
421
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
423
def prepare_memory_tree(self, location):
424
tree = self.make_branch_and_memory_tree(location)
429
def build_ancestry(self, tree, ancestors):
430
"""Create an ancestry as specified by a graph dict
432
:param tree: A tree to use
433
:param ancestors: a dict of {node: [node_parent, ...]}
435
pending = [NULL_REVISION]
437
for descendant, parents in ancestors.iteritems():
438
for parent in parents:
439
descendants.setdefault(parent, []).append(descendant)
440
while len(pending) > 0:
441
cur_node = pending.pop()
442
for descendant in descendants.get(cur_node, []):
443
if tree.branch.repository.has_revision(descendant):
445
parents = [p for p in ancestors[descendant] if p is not
447
if len([p for p in parents if not
448
tree.branch.repository.has_revision(p)]) > 0:
450
tree.set_parent_ids(parents)
452
left_parent = parents[0]
454
left_parent = NULL_REVISION
455
tree.branch.set_last_revision_info(
456
len(tree.branch._lefthand_history(left_parent)),
458
tree.commit(descendant, rev_id=descendant)
459
pending.append(descendant)
462
"""Test finding least common ancestor.
464
ancestry_1 should always have a single common ancestor
466
graph = self.make_graph(ancestry_1)
467
self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
468
self.assertEqual(set([NULL_REVISION]),
469
graph.find_lca(NULL_REVISION, NULL_REVISION))
470
self.assertEqual(set([NULL_REVISION]),
471
graph.find_lca(NULL_REVISION, 'rev1'))
472
self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
473
self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
475
def test_no_unique_lca(self):
476
"""Test error when one revision is not in the graph"""
477
graph = self.make_graph(ancestry_1)
478
self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
481
def test_lca_criss_cross(self):
482
"""Test least-common-ancestor after a criss-cross merge."""
483
graph = self.make_graph(criss_cross)
484
self.assertEqual(set(['rev2a', 'rev2b']),
485
graph.find_lca('rev3a', 'rev3b'))
486
self.assertEqual(set(['rev2b']),
487
graph.find_lca('rev3a', 'rev3b', 'rev2b'))
489
def test_lca_shortcut(self):
490
"""Test least-common ancestor on this history shortcut"""
491
graph = self.make_graph(history_shortcut)
492
self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
494
def test_recursive_unique_lca(self):
495
"""Test finding a unique least common ancestor.
497
ancestry_1 should always have a single common ancestor
499
graph = self.make_graph(ancestry_1)
500
self.assertEqual(NULL_REVISION,
501
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
502
self.assertEqual(NULL_REVISION,
503
graph.find_unique_lca(NULL_REVISION, 'rev1'))
504
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
505
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
506
self.assertEqual(('rev1', 1,),
507
graph.find_unique_lca('rev2a', 'rev2b',
510
def assertRemoveDescendants(self, expected, graph, revisions):
511
parents = graph.get_parent_map(revisions)
512
self.assertEqual(expected,
513
graph._remove_simple_descendants(revisions, parents))
515
def test__remove_simple_descendants(self):
516
graph = self.make_graph(ancestry_1)
517
self.assertRemoveDescendants(set(['rev1']), graph,
518
set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']))
520
def test__remove_simple_descendants_disjoint(self):
521
graph = self.make_graph(ancestry_1)
522
self.assertRemoveDescendants(set(['rev1', 'rev3']), graph,
523
set(['rev1', 'rev3']))
525
def test__remove_simple_descendants_chain(self):
526
graph = self.make_graph(ancestry_1)
527
self.assertRemoveDescendants(set(['rev1']), graph,
528
set(['rev1', 'rev2a', 'rev3']))
530
def test__remove_simple_descendants_siblings(self):
531
graph = self.make_graph(ancestry_1)
532
self.assertRemoveDescendants(set(['rev2a', 'rev2b']), graph,
533
set(['rev2a', 'rev2b', 'rev3']))
535
def test_unique_lca_criss_cross(self):
536
"""Ensure we don't pick non-unique lcas in a criss-cross"""
537
graph = self.make_graph(criss_cross)
538
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
539
lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
540
self.assertEqual('rev1', lca)
541
self.assertEqual(2, steps)
543
def test_unique_lca_null_revision(self):
544
"""Ensure we pick NULL_REVISION when necessary"""
545
graph = self.make_graph(criss_cross2)
546
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
547
self.assertEqual(NULL_REVISION,
548
graph.find_unique_lca('rev2a', 'rev2b'))
550
def test_unique_lca_null_revision2(self):
551
"""Ensure we pick NULL_REVISION when necessary"""
552
graph = self.make_graph(ancestry_2)
553
self.assertEqual(NULL_REVISION,
554
graph.find_unique_lca('rev4a', 'rev1b'))
556
def test_lca_double_shortcut(self):
557
graph = self.make_graph(double_shortcut)
558
self.assertEqual('c', graph.find_unique_lca('f', 'g'))
560
def test_common_ancestor_two_repos(self):
561
"""Ensure we do unique_lca using data from two repos"""
562
mainline_tree = self.prepare_memory_tree('mainline')
563
self.build_ancestry(mainline_tree, mainline)
564
self.addCleanup(mainline_tree.unlock)
566
# This is cheating, because the revisions in the graph are actually
567
# different revisions, despite having the same revision-id.
568
feature_tree = self.prepare_memory_tree('feature')
569
self.build_ancestry(feature_tree, feature_branch)
570
self.addCleanup(feature_tree.unlock)
572
graph = mainline_tree.branch.repository.get_graph(
573
feature_tree.branch.repository)
574
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
576
def test_graph_difference(self):
577
graph = self.make_graph(ancestry_1)
578
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
579
self.assertEqual((set(), set(['rev1'])),
580
graph.find_difference(NULL_REVISION, 'rev1'))
581
self.assertEqual((set(['rev1']), set()),
582
graph.find_difference('rev1', NULL_REVISION))
583
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
584
graph.find_difference('rev3', 'rev2b'))
585
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
586
graph.find_difference('rev4', 'rev2b'))
588
def test_graph_difference_separate_ancestry(self):
589
graph = self.make_graph(ancestry_2)
590
self.assertEqual((set(['rev1a']), set(['rev1b'])),
591
graph.find_difference('rev1a', 'rev1b'))
592
self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
594
graph.find_difference('rev4a', 'rev1b'))
596
def test_graph_difference_criss_cross(self):
597
graph = self.make_graph(criss_cross)
598
self.assertEqual((set(['rev3a']), set(['rev3b'])),
599
graph.find_difference('rev3a', 'rev3b'))
600
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
601
graph.find_difference('rev2a', 'rev3b'))
603
def test_graph_difference_extended_history(self):
604
graph = self.make_graph(extended_history_shortcut)
605
self.assertEqual((set(['e']), set(['f'])),
606
graph.find_difference('e', 'f'))
607
self.assertEqual((set(['f']), set(['e'])),
608
graph.find_difference('f', 'e'))
610
def test_graph_difference_double_shortcut(self):
611
graph = self.make_graph(double_shortcut)
612
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
613
graph.find_difference('f', 'g'))
615
def test_graph_difference_complex_shortcut(self):
616
graph = self.make_graph(complex_shortcut)
617
self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
618
graph.find_difference('m', 'n'))
620
def test_graph_difference_complex_shortcut2(self):
621
graph = self.make_graph(complex_shortcut2)
622
self.assertEqual((set(['t']), set(['j', 'u'])),
623
graph.find_difference('t', 'u'))
625
def test_graph_difference_shortcut_extra_root(self):
626
graph = self.make_graph(shortcut_extra_root)
627
self.assertEqual((set(['e']), set(['f', 'g'])),
628
graph.find_difference('e', 'f'))
630
def test_stacked_parents_provider(self):
631
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
632
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
633
stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
634
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
635
stacked.get_parent_map(['rev1', 'rev2']))
636
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
637
stacked.get_parent_map(['rev2', 'rev1']))
638
self.assertEqual({'rev2':['rev3']},
639
stacked.get_parent_map(['rev2', 'rev2']))
640
self.assertEqual({'rev1':['rev4']},
641
stacked.get_parent_map(['rev1', 'rev1']))
643
def test_iter_topo_order(self):
644
graph = self.make_graph(ancestry_1)
645
args = ['rev2a', 'rev3', 'rev1']
646
topo_args = list(graph.iter_topo_order(args))
647
self.assertEqual(set(args), set(topo_args))
648
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
649
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
651
def test_is_ancestor(self):
652
graph = self.make_graph(ancestry_1)
653
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
654
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
655
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
656
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
657
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
658
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
659
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
660
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
661
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
662
instrumented_provider = InstrumentedParentsProvider(graph)
663
instrumented_graph = _mod_graph.Graph(instrumented_provider)
664
instrumented_graph.is_ancestor('rev2a', 'rev2b')
665
self.assertTrue('null:' not in instrumented_provider.calls)
667
def test_is_ancestor_boundary(self):
668
"""Ensure that we avoid searching the whole graph.
670
This requires searching through b as a common ancestor, so we
671
can identify that e is common.
673
graph = self.make_graph(boundary)
674
instrumented_provider = InstrumentedParentsProvider(graph)
675
graph = _mod_graph.Graph(instrumented_provider)
676
self.assertFalse(graph.is_ancestor('a', 'c'))
677
self.assertTrue('null:' not in instrumented_provider.calls)
679
def test_iter_ancestry(self):
680
nodes = boundary.copy()
681
nodes[NULL_REVISION] = ()
682
graph = self.make_graph(nodes)
683
expected = nodes.copy()
684
expected.pop('a') # 'a' is not in the ancestry of 'c', all the
686
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
687
self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
689
def test_iter_ancestry_with_ghost(self):
690
graph = self.make_graph(with_ghost)
691
expected = with_ghost.copy()
692
# 'a' is not in the ancestry of 'c', and 'g' is a ghost
694
self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
696
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
698
def test_filter_candidate_lca(self):
699
"""Test filter_candidate_lca for a corner case
701
This tests the case where we encounter the end of iteration for 'e'
702
in the same pass as we discover that 'd' is an ancestor of 'e', and
703
therefore 'e' can't be an lca.
705
To compensate for different dict orderings on other Python
706
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
708
# This test is sensitive to the iteration order of dicts. It will
709
# pass incorrectly if 'e' and 'a' sort before 'c'
718
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
719
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
720
self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
722
def test_heads_null(self):
723
graph = self.make_graph(ancestry_1)
724
self.assertEqual(set(['null:']), graph.heads(['null:']))
725
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
726
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
727
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
728
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
730
def test_heads_one(self):
731
# A single node will always be a head
732
graph = self.make_graph(ancestry_1)
733
self.assertEqual(set(['null:']), graph.heads(['null:']))
734
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
735
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
736
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
737
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
738
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
740
def test_heads_single(self):
741
graph = self.make_graph(ancestry_1)
742
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
743
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
744
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
745
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
746
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
747
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
748
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
749
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
751
def test_heads_two_heads(self):
752
graph = self.make_graph(ancestry_1)
753
self.assertEqual(set(['rev2a', 'rev2b']),
754
graph.heads(['rev2a', 'rev2b']))
755
self.assertEqual(set(['rev3', 'rev2b']),
756
graph.heads(['rev3', 'rev2b']))
758
def test_heads_criss_cross(self):
759
graph = self.make_graph(criss_cross)
760
self.assertEqual(set(['rev2a']),
761
graph.heads(['rev2a', 'rev1']))
762
self.assertEqual(set(['rev2b']),
763
graph.heads(['rev2b', 'rev1']))
764
self.assertEqual(set(['rev3a']),
765
graph.heads(['rev3a', 'rev1']))
766
self.assertEqual(set(['rev3b']),
767
graph.heads(['rev3b', 'rev1']))
768
self.assertEqual(set(['rev2a', 'rev2b']),
769
graph.heads(['rev2a', 'rev2b']))
770
self.assertEqual(set(['rev3a']),
771
graph.heads(['rev3a', 'rev2a']))
772
self.assertEqual(set(['rev3a']),
773
graph.heads(['rev3a', 'rev2b']))
774
self.assertEqual(set(['rev3a']),
775
graph.heads(['rev3a', 'rev2a', 'rev2b']))
776
self.assertEqual(set(['rev3b']),
777
graph.heads(['rev3b', 'rev2a']))
778
self.assertEqual(set(['rev3b']),
779
graph.heads(['rev3b', 'rev2b']))
780
self.assertEqual(set(['rev3b']),
781
graph.heads(['rev3b', 'rev2a', 'rev2b']))
782
self.assertEqual(set(['rev3a', 'rev3b']),
783
graph.heads(['rev3a', 'rev3b']))
784
self.assertEqual(set(['rev3a', 'rev3b']),
785
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
787
def test_heads_shortcut(self):
788
graph = self.make_graph(history_shortcut)
790
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
791
graph.heads(['rev2a', 'rev2b', 'rev2c']))
792
self.assertEqual(set(['rev3a', 'rev3b']),
793
graph.heads(['rev3a', 'rev3b']))
794
self.assertEqual(set(['rev3a', 'rev3b']),
795
graph.heads(['rev2a', 'rev3a', 'rev3b']))
796
self.assertEqual(set(['rev2a', 'rev3b']),
797
graph.heads(['rev2a', 'rev3b']))
798
self.assertEqual(set(['rev2c', 'rev3a']),
799
graph.heads(['rev2c', 'rev3a']))
801
def _run_heads_break_deeper(self, graph_dict, search):
802
"""Run heads on a graph-as-a-dict.
804
If the search asks for the parents of 'deeper' the test will fail.
808
def get_parent_map(keys):
812
self.fail('key deeper was accessed')
813
result[key] = graph_dict[key]
816
an_obj.get_parent_map = get_parent_map
817
graph = _mod_graph.Graph(an_obj)
818
return graph.heads(search)
820
def test_heads_limits_search(self):
821
# test that a heads query does not search all of history
827
self.assertEqual(set(['left', 'right']),
828
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
830
def test_heads_limits_search_assymetric(self):
831
# test that a heads query does not search all of history
834
'midleft':['common'],
836
'common':['aftercommon'],
837
'aftercommon':['deeper'],
839
self.assertEqual(set(['left', 'right']),
840
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
842
def test_heads_limits_search_common_search_must_continue(self):
843
# test that common nodes are still queried, preventing
844
# all-the-way-to-origin behaviour in the following graph:
846
'h1':['shortcut', 'common1'],
848
'shortcut':['common2'],
849
'common1':['common2'],
850
'common2':['deeper'],
852
self.assertEqual(set(['h1', 'h2']),
853
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
855
def test_breadth_first_search_start_ghosts(self):
856
graph = self.make_graph({})
857
# with_ghosts reports the ghosts
858
search = graph._make_breadth_first_searcher(['a-ghost'])
859
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
860
self.assertRaises(StopIteration, search.next_with_ghosts)
862
search = graph._make_breadth_first_searcher(['a-ghost'])
863
self.assertEqual(set(['a-ghost']), search.next())
864
self.assertRaises(StopIteration, search.next)
866
def test_breadth_first_search_deep_ghosts(self):
867
graph = self.make_graph({
869
'present':['child', 'ghost'],
872
# with_ghosts reports the ghosts
873
search = graph._make_breadth_first_searcher(['head'])
874
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
875
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
876
self.assertEqual((set(['child']), set(['ghost'])),
877
search.next_with_ghosts())
878
self.assertRaises(StopIteration, search.next_with_ghosts)
880
search = graph._make_breadth_first_searcher(['head'])
881
self.assertEqual(set(['head']), search.next())
882
self.assertEqual(set(['present']), search.next())
883
self.assertEqual(set(['child', 'ghost']),
885
self.assertRaises(StopIteration, search.next)
887
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
888
# To make the API robust, we allow calling both next() and
889
# next_with_ghosts() on the same searcher.
890
graph = self.make_graph({
892
'present':['child', 'ghost'],
895
# start with next_with_ghosts
896
search = graph._make_breadth_first_searcher(['head'])
897
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
898
self.assertEqual(set(['present']), search.next())
899
self.assertEqual((set(['child']), set(['ghost'])),
900
search.next_with_ghosts())
901
self.assertRaises(StopIteration, search.next)
903
search = graph._make_breadth_first_searcher(['head'])
904
self.assertEqual(set(['head']), search.next())
905
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
906
self.assertEqual(set(['child', 'ghost']),
908
self.assertRaises(StopIteration, search.next_with_ghosts)
910
def test_breadth_first_change_search(self):
911
# Changing the search should work with both next and next_with_ghosts.
912
graph = self.make_graph({
914
'present':['stopped'],
918
search = graph._make_breadth_first_searcher(['head'])
919
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
920
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
921
self.assertEqual(set(['present']),
922
search.stop_searching_any(['present']))
923
self.assertEqual((set(['other']), set(['other_ghost'])),
924
search.start_searching(['other', 'other_ghost']))
925
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
926
self.assertRaises(StopIteration, search.next_with_ghosts)
928
search = graph._make_breadth_first_searcher(['head'])
929
self.assertEqual(set(['head']), search.next())
930
self.assertEqual(set(['present']), search.next())
931
self.assertEqual(set(['present']),
932
search.stop_searching_any(['present']))
933
search.start_searching(['other', 'other_ghost'])
934
self.assertEqual(set(['other_2']), search.next())
935
self.assertRaises(StopIteration, search.next)
937
def assertSeenAndResult(self, instructions, search, next):
938
"""Check the results of .seen and get_result() for a seach.
940
:param instructions: A list of tuples:
941
(seen, recipe, included_keys, starts, stops).
942
seen, recipe and included_keys are results to check on the search
943
and the searches get_result(). starts and stops are parameters to
944
pass to start_searching and stop_searching_any during each
945
iteration, if they are not None.
946
:param search: The search to use.
947
:param next: A callable to advance the search.
949
for seen, recipe, included_keys, starts, stops in instructions:
951
if starts is not None:
952
search.start_searching(starts)
953
if stops is not None:
954
search.stop_searching_any(stops)
955
result = search.get_result()
956
self.assertEqual(recipe, result.get_recipe())
957
self.assertEqual(set(included_keys), result.get_keys())
958
self.assertEqual(seen, search.seen)
960
def test_breadth_first_get_result_excludes_current_pending(self):
961
graph = self.make_graph({
963
'child':[NULL_REVISION],
966
search = graph._make_breadth_first_searcher(['head'])
967
# At the start, nothing has been seen, to its all excluded:
968
result = search.get_result()
969
self.assertEqual((set(['head']), set(['head']), 0),
971
self.assertEqual(set(), result.get_keys())
972
self.assertEqual(set(), search.seen)
975
(set(['head']), (set(['head']), set(['child']), 1),
976
['head'], None, None),
977
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
978
['head', 'child'], None, None),
979
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
980
['head', 'child', NULL_REVISION], None, None),
982
self.assertSeenAndResult(expected, search, search.next)
983
# using next_with_ghosts:
984
search = graph._make_breadth_first_searcher(['head'])
985
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
987
def test_breadth_first_get_result_starts_stops(self):
988
graph = self.make_graph({
990
'child':[NULL_REVISION],
991
'otherhead':['otherchild'],
992
'otherchild':['excluded'],
993
'excluded':[NULL_REVISION],
996
search = graph._make_breadth_first_searcher([])
997
# Starting with nothing and adding a search works:
998
search.start_searching(['head'])
999
# head has been seen:
1000
result = search.get_result()
1001
self.assertEqual((set(['head']), set(['child']), 1),
1002
result.get_recipe())
1003
self.assertEqual(set(['head']), result.get_keys())
1004
self.assertEqual(set(['head']), search.seen)
1007
# stop at child, and start a new search at otherhead:
1008
# - otherhead counts as seen immediately when start_searching is
1010
(set(['head', 'child', 'otherhead']),
1011
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
1012
['head', 'otherhead'], ['otherhead'], ['child']),
1013
(set(['head', 'child', 'otherhead', 'otherchild']),
1014
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1015
['head', 'otherhead', 'otherchild'], None, None),
1016
# stop searching excluded now
1017
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1018
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
1019
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1021
self.assertSeenAndResult(expected, search, search.next)
1022
# using next_with_ghosts:
1023
search = graph._make_breadth_first_searcher([])
1024
search.start_searching(['head'])
1025
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1027
def test_breadth_first_stop_searching_not_queried(self):
1028
# A client should be able to say 'stop node X' even if X has not been
1029
# returned to the client.
1030
graph = self.make_graph({
1031
'head':['child', 'ghost1'],
1032
'child':[NULL_REVISION],
1035
search = graph._make_breadth_first_searcher(['head'])
1037
# NULL_REVISION and ghost1 have not been returned
1038
(set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
1039
['head'], None, [NULL_REVISION, 'ghost1']),
1040
# ghost1 has been returned, NULL_REVISION is to be returned in the
1042
(set(['head', 'child', 'ghost1']),
1043
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
1044
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1046
self.assertSeenAndResult(expected, search, search.next)
1047
# using next_with_ghosts:
1048
search = graph._make_breadth_first_searcher(['head'])
1049
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1051
def test_breadth_first_get_result_ghosts_are_excluded(self):
1052
graph = self.make_graph({
1053
'head':['child', 'ghost'],
1054
'child':[NULL_REVISION],
1057
search = graph._make_breadth_first_searcher(['head'])
1061
(set(['head']), set(['ghost', 'child']), 1),
1062
['head'], None, None),
1063
(set(['head', 'child', 'ghost']),
1064
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
1065
['head', 'child'], None, None),
1067
self.assertSeenAndResult(expected, search, search.next)
1068
# using next_with_ghosts:
1069
search = graph._make_breadth_first_searcher(['head'])
1070
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1072
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1073
graph = self.make_graph({
1075
'child':[NULL_REVISION],
1078
search = graph._make_breadth_first_searcher(['head'])
1081
(set(['head', 'ghost']),
1082
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
1083
['head'], ['ghost'], None),
1084
(set(['head', 'child', 'ghost']),
1085
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
1086
['head', 'child'], None, None),
1088
self.assertSeenAndResult(expected, search, search.next)
1089
# using next_with_ghosts:
1090
search = graph._make_breadth_first_searcher(['head'])
1091
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1093
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1094
graph = self.make_graph({
1095
'head':[NULL_REVISION],
1098
search = graph._make_breadth_first_searcher(['head'])
1102
(set(['head']), set([NULL_REVISION]), 1),
1103
['head'], None, None),
1104
(set(['head', NULL_REVISION]),
1105
(set(['head']), set([]), 2),
1106
['head', NULL_REVISION], None, None),
1108
self.assertSeenAndResult(expected, search, search.next)
1109
# using next_with_ghosts:
1110
search = graph._make_breadth_first_searcher(['head'])
1111
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1113
def test_breadth_first_search_get_result_after_StopIteration(self):
1114
# StopIteration should not invalid anything..
1115
graph = self.make_graph({
1116
'head':[NULL_REVISION],
1119
search = graph._make_breadth_first_searcher(['head'])
1123
(set(['head']), set([NULL_REVISION]), 1),
1124
['head'], None, None),
1125
(set(['head', 'ghost', NULL_REVISION]),
1126
(set(['head', 'ghost']), set(['ghost']), 2),
1127
['head', NULL_REVISION], ['ghost'], None),
1129
self.assertSeenAndResult(expected, search, search.next)
1130
self.assertRaises(StopIteration, search.next)
1131
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1132
result = search.get_result()
1133
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1134
result.get_recipe())
1135
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1136
# using next_with_ghosts:
1137
search = graph._make_breadth_first_searcher(['head'])
1138
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1139
self.assertRaises(StopIteration, search.next)
1140
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1141
result = search.get_result()
1142
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1143
result.get_recipe())
1144
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1147
class TestFindUniqueAncestors(tests.TestCase):
1149
def make_graph(self, ancestors):
1150
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
1152
def make_breaking_graph(self, ancestors, break_on):
1153
"""Make a Graph that raises an exception if we hit a node."""
1154
g = self.make_graph(ancestors)
1155
orig_parent_map = g.get_parent_map
1156
def get_parent_map(keys):
1157
bad_keys = set(keys).intersection(break_on)
1159
self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
1160
return orig_parent_map(keys)
1161
g.get_parent_map = get_parent_map
1164
def assertFindUniqueAncestors(self, graph, expected, node, common):
1165
actual = graph.find_unique_ancestors(node, common)
1166
self.assertEqual(expected, sorted(actual))
1168
def test_empty_set(self):
1169
graph = self.make_graph(ancestry_1)
1170
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1171
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1172
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1174
def test_single_node(self):
1175
graph = self.make_graph(ancestry_1)
1176
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1177
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1178
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1180
def test_minimal_ancestry(self):
1181
graph = self.make_breaking_graph(extended_history_shortcut,
1182
[NULL_REVISION, 'a', 'b'])
1183
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1185
graph = self.make_breaking_graph(extended_history_shortcut,
1187
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1189
graph = self.make_breaking_graph(complex_shortcut,
1191
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1192
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1193
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1194
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1196
def test_in_ancestry(self):
1197
graph = self.make_graph(ancestry_1)
1198
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1199
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1201
def test_multiple_revisions(self):
1202
graph = self.make_graph(ancestry_1)
1203
self.assertFindUniqueAncestors(graph,
1204
['rev4'], 'rev4', ['rev3', 'rev2b'])
1205
self.assertFindUniqueAncestors(graph,
1206
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1208
def test_complex_shortcut(self):
1209
graph = self.make_graph(complex_shortcut)
1210
self.assertFindUniqueAncestors(graph,
1211
['h', 'n'], 'n', ['m'])
1212
self.assertFindUniqueAncestors(graph,
1213
['e', 'i', 'm'], 'm', ['n'])
1215
def test_complex_shortcut2(self):
1216
graph = self.make_graph(complex_shortcut2)
1217
self.assertFindUniqueAncestors(graph,
1218
['j', 'u'], 'u', ['t'])
1219
self.assertFindUniqueAncestors(graph,
1222
def test_multiple_interesting_unique(self):
1223
graph = self.make_graph(multiple_interesting_unique)
1224
self.assertFindUniqueAncestors(graph,
1225
['j', 'y'], 'y', ['z'])
1226
self.assertFindUniqueAncestors(graph,
1227
['p', 'z'], 'z', ['y'])
1229
def test_racing_shortcuts(self):
1230
graph = self.make_graph(racing_shortcuts)
1231
self.assertFindUniqueAncestors(graph,
1232
['p', 'q', 'z'], 'z', ['y'])
1233
import pdb; pdb.set_trace()
1234
self.assertFindUniqueAncestors(graph,
1235
['h', 'i', 'j', 'y'], 'j', ['z'])
1238
class TestCachingParentsProvider(tests.TestCase):
1241
super(TestCachingParentsProvider, self).setUp()
1242
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1243
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1244
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1246
def test_get_parent_map(self):
1247
"""Requesting the same revision should be returned from cache"""
1248
self.assertEqual({}, self.caching_pp._cache)
1249
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1250
self.assertEqual(['a'], self.inst_pp.calls)
1251
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1252
# No new call, as it should have been returned from the cache
1253
self.assertEqual(['a'], self.inst_pp.calls)
1254
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1256
def test_get_parent_map_not_present(self):
1257
"""The cache should also track when a revision doesn't exist"""
1258
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1259
self.assertEqual(['b'], self.inst_pp.calls)
1260
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1262
self.assertEqual(['b'], self.inst_pp.calls)
1263
self.assertEqual({'b':None}, self.caching_pp._cache)
1265
def test_get_parent_map_mixed(self):
1266
"""Anything that can be returned from cache, should be"""
1267
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1268
self.assertEqual(['b'], self.inst_pp.calls)
1269
self.assertEqual({'a':('b',)},
1270
self.caching_pp.get_parent_map(['a', 'b']))
1271
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1273
def test_get_parent_map_repeated(self):
1274
"""Asking for the same parent 2x will only forward 1 request."""
1275
self.assertEqual({'a':('b',)},
1276
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1277
# Use sorted because we don't care about the order, just that each is
1278
# only present 1 time.
1279
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
added
removed
bzrlib/tests/test_graph.py
