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 top 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.
195
complex_shortcut = {'d':[NULL_REVISION],
196
'x':['d'], 'y':['x'],
197
'e':['y'], 'f':['d'], 'g':['f', 'i'], 'h':['f'],
198
'i':['e'], 'j':['g'], 'k':['j'],
199
'l':['k'], 'm':['i', 's'], 'n':['s', 'h'],
200
'o':['l'], 'p':['o'], 'q':['p'],
201
'r':['q'], 's':['r'],
204
# Shortcut with extra root
205
# We have a long history shortcut, and an extra root, which is why we can't
206
# stop searchers based on seeing NULL_REVISION
218
shortcut_extra_root = {'a': [NULL_REVISION],
223
'f': ['a', 'd', 'g'],
224
'g': [NULL_REVISION],
237
boundary = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e'], 'e': ['f'],
241
# A graph that contains a ghost
252
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
253
'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
257
class InstrumentedParentsProvider(object):
259
def __init__(self, parents_provider):
261
self._real_parents_provider = parents_provider
263
def get_parent_map(self, nodes):
264
self.calls.extend(nodes)
265
return self._real_parents_provider.get_parent_map(nodes)
268
class TestGraph(TestCaseWithMemoryTransport):
270
def make_graph(self, ancestors):
271
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
273
def prepare_memory_tree(self, location):
274
tree = self.make_branch_and_memory_tree(location)
279
def build_ancestry(self, tree, ancestors):
280
"""Create an ancestry as specified by a graph dict
282
:param tree: A tree to use
283
:param ancestors: a dict of {node: [node_parent, ...]}
285
pending = [NULL_REVISION]
287
for descendant, parents in ancestors.iteritems():
288
for parent in parents:
289
descendants.setdefault(parent, []).append(descendant)
290
while len(pending) > 0:
291
cur_node = pending.pop()
292
for descendant in descendants.get(cur_node, []):
293
if tree.branch.repository.has_revision(descendant):
295
parents = [p for p in ancestors[descendant] if p is not
297
if len([p for p in parents if not
298
tree.branch.repository.has_revision(p)]) > 0:
300
tree.set_parent_ids(parents)
302
left_parent = parents[0]
304
left_parent = NULL_REVISION
305
tree.branch.set_last_revision_info(
306
len(tree.branch._lefthand_history(left_parent)),
308
tree.commit(descendant, rev_id=descendant)
309
pending.append(descendant)
312
"""Test finding least common ancestor.
314
ancestry_1 should always have a single common ancestor
316
graph = self.make_graph(ancestry_1)
317
self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
318
self.assertEqual(set([NULL_REVISION]),
319
graph.find_lca(NULL_REVISION, NULL_REVISION))
320
self.assertEqual(set([NULL_REVISION]),
321
graph.find_lca(NULL_REVISION, 'rev1'))
322
self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
323
self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
325
def test_no_unique_lca(self):
326
"""Test error when one revision is not in the graph"""
327
graph = self.make_graph(ancestry_1)
328
self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
331
def test_lca_criss_cross(self):
332
"""Test least-common-ancestor after a criss-cross merge."""
333
graph = self.make_graph(criss_cross)
334
self.assertEqual(set(['rev2a', 'rev2b']),
335
graph.find_lca('rev3a', 'rev3b'))
336
self.assertEqual(set(['rev2b']),
337
graph.find_lca('rev3a', 'rev3b', 'rev2b'))
339
def test_lca_shortcut(self):
340
"""Test least-common ancestor on this history shortcut"""
341
graph = self.make_graph(history_shortcut)
342
self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
344
def test_recursive_unique_lca(self):
345
"""Test finding a unique least common ancestor.
347
ancestry_1 should always have a single common ancestor
349
graph = self.make_graph(ancestry_1)
350
self.assertEqual(NULL_REVISION,
351
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
352
self.assertEqual(NULL_REVISION,
353
graph.find_unique_lca(NULL_REVISION, 'rev1'))
354
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
355
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
356
self.assertEqual(('rev1', 1,),
357
graph.find_unique_lca('rev2a', 'rev2b',
360
def test_unique_lca_criss_cross(self):
361
"""Ensure we don't pick non-unique lcas in a criss-cross"""
362
graph = self.make_graph(criss_cross)
363
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
364
lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
365
self.assertEqual('rev1', lca)
366
self.assertEqual(2, steps)
368
def test_unique_lca_null_revision(self):
369
"""Ensure we pick NULL_REVISION when necessary"""
370
graph = self.make_graph(criss_cross2)
371
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
372
self.assertEqual(NULL_REVISION,
373
graph.find_unique_lca('rev2a', 'rev2b'))
375
def test_unique_lca_null_revision2(self):
376
"""Ensure we pick NULL_REVISION when necessary"""
377
graph = self.make_graph(ancestry_2)
378
self.assertEqual(NULL_REVISION,
379
graph.find_unique_lca('rev4a', 'rev1b'))
381
def test_lca_double_shortcut(self):
382
graph = self.make_graph(double_shortcut)
383
self.assertEqual('c', graph.find_unique_lca('f', 'g'))
385
def test_common_ancestor_two_repos(self):
386
"""Ensure we do unique_lca using data from two repos"""
387
mainline_tree = self.prepare_memory_tree('mainline')
388
self.build_ancestry(mainline_tree, mainline)
389
self.addCleanup(mainline_tree.unlock)
391
# This is cheating, because the revisions in the graph are actually
392
# different revisions, despite having the same revision-id.
393
feature_tree = self.prepare_memory_tree('feature')
394
self.build_ancestry(feature_tree, feature_branch)
395
self.addCleanup(feature_tree.unlock)
397
graph = mainline_tree.branch.repository.get_graph(
398
feature_tree.branch.repository)
399
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
401
def test_graph_difference(self):
402
graph = self.make_graph(ancestry_1)
403
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
404
self.assertEqual((set(), set(['rev1'])),
405
graph.find_difference(NULL_REVISION, 'rev1'))
406
self.assertEqual((set(['rev1']), set()),
407
graph.find_difference('rev1', NULL_REVISION))
408
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
409
graph.find_difference('rev3', 'rev2b'))
410
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
411
graph.find_difference('rev4', 'rev2b'))
413
def test_graph_difference_separate_ancestry(self):
414
graph = self.make_graph(ancestry_2)
415
self.assertEqual((set(['rev1a']), set(['rev1b'])),
416
graph.find_difference('rev1a', 'rev1b'))
417
self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
419
graph.find_difference('rev4a', 'rev1b'))
421
def test_graph_difference_criss_cross(self):
422
graph = self.make_graph(criss_cross)
423
self.assertEqual((set(['rev3a']), set(['rev3b'])),
424
graph.find_difference('rev3a', 'rev3b'))
425
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
426
graph.find_difference('rev2a', 'rev3b'))
428
def test_graph_difference_extended_history(self):
429
graph = self.make_graph(extended_history_shortcut)
430
self.expectFailure('find_difference cannot handle shortcuts',
431
self.assertEqual, (set(['e']), set(['f'])),
432
graph.find_difference('e', 'f'))
433
self.assertEqual((set(['e']), set(['f'])),
434
graph.find_difference('e', 'f'))
435
self.assertEqual((set(['f']), set(['e'])),
436
graph.find_difference('f', 'e'))
438
def test_graph_difference_double_shortcut(self):
439
graph = self.make_graph(double_shortcut)
440
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
441
graph.find_difference('f', 'g'))
443
def test_graph_difference_complex_shortcut(self):
444
graph = self.make_graph(complex_shortcut)
445
self.expectFailure('find_difference cannot handle shortcuts',
446
self.assertEqual, (set(['m']), set(['h', 'n'])),
447
graph.find_difference('m', 'n'))
448
self.assertEqual((set(['m']), set(['h', 'n'])),
449
graph.find_difference('m', 'n'))
451
def test_graph_difference_shortcut_extra_root(self):
452
graph = self.make_graph(shortcut_extra_root)
453
self.expectFailure('find_difference cannot handle shortcuts',
454
self.assertEqual, (set(['e']), set(['f', 'g'])),
455
graph.find_difference('e', 'f'))
456
self.assertEqual((set(['e']), set(['f', 'g'])),
457
graph.find_difference('e', 'f'))
459
def test_stacked_parents_provider(self):
460
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
461
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
462
stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
463
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
464
stacked.get_parent_map(['rev1', 'rev2']))
465
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
466
stacked.get_parent_map(['rev2', 'rev1']))
467
self.assertEqual({'rev2':['rev3']},
468
stacked.get_parent_map(['rev2', 'rev2']))
469
self.assertEqual({'rev1':['rev4']},
470
stacked.get_parent_map(['rev1', 'rev1']))
472
def test_iter_topo_order(self):
473
graph = self.make_graph(ancestry_1)
474
args = ['rev2a', 'rev3', 'rev1']
475
topo_args = list(graph.iter_topo_order(args))
476
self.assertEqual(set(args), set(topo_args))
477
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
478
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
480
def test_is_ancestor(self):
481
graph = self.make_graph(ancestry_1)
482
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
483
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
484
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
485
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
486
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
487
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
488
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
489
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
490
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
491
instrumented_provider = InstrumentedParentsProvider(graph)
492
instrumented_graph = _mod_graph.Graph(instrumented_provider)
493
instrumented_graph.is_ancestor('rev2a', 'rev2b')
494
self.assertTrue('null:' not in instrumented_provider.calls)
496
def test_is_ancestor_boundary(self):
497
"""Ensure that we avoid searching the whole graph.
499
This requires searching through b as a common ancestor, so we
500
can identify that e is common.
502
graph = self.make_graph(boundary)
503
instrumented_provider = InstrumentedParentsProvider(graph)
504
graph = _mod_graph.Graph(instrumented_provider)
505
self.assertFalse(graph.is_ancestor('a', 'c'))
506
self.assertTrue('null:' not in instrumented_provider.calls)
508
def test_iter_ancestry(self):
509
nodes = boundary.copy()
510
nodes[NULL_REVISION] = ()
511
graph = self.make_graph(nodes)
512
expected = nodes.copy()
513
expected.pop('a') # 'a' is not in the ancestry of 'c', all the
515
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
516
self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
518
def test_iter_ancestry_with_ghost(self):
519
graph = self.make_graph(with_ghost)
520
expected = with_ghost.copy()
521
# 'a' is not in the ancestry of 'c', and 'g' is a ghost
523
self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
525
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
527
def test_filter_candidate_lca(self):
528
"""Test filter_candidate_lca for a corner case
530
This tests the case where we encounter the end of iteration for 'e'
531
in the same pass as we discover that 'd' is an ancestor of 'e', and
532
therefore 'e' can't be an lca.
534
To compensate for different dict orderings on other Python
535
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
537
# This test is sensitive to the iteration order of dicts. It will
538
# pass incorrectly if 'e' and 'a' sort before 'c'
547
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
548
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
549
self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
551
def test_heads_null(self):
552
graph = self.make_graph(ancestry_1)
553
self.assertEqual(set(['null:']), graph.heads(['null:']))
554
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
555
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
556
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
557
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
559
def test_heads_one(self):
560
# A single node will always be a head
561
graph = self.make_graph(ancestry_1)
562
self.assertEqual(set(['null:']), graph.heads(['null:']))
563
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
564
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
565
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
566
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
567
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
569
def test_heads_single(self):
570
graph = self.make_graph(ancestry_1)
571
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
572
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
573
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
574
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
575
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
576
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
577
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
578
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
580
def test_heads_two_heads(self):
581
graph = self.make_graph(ancestry_1)
582
self.assertEqual(set(['rev2a', 'rev2b']),
583
graph.heads(['rev2a', 'rev2b']))
584
self.assertEqual(set(['rev3', 'rev2b']),
585
graph.heads(['rev3', 'rev2b']))
587
def test_heads_criss_cross(self):
588
graph = self.make_graph(criss_cross)
589
self.assertEqual(set(['rev2a']),
590
graph.heads(['rev2a', 'rev1']))
591
self.assertEqual(set(['rev2b']),
592
graph.heads(['rev2b', 'rev1']))
593
self.assertEqual(set(['rev3a']),
594
graph.heads(['rev3a', 'rev1']))
595
self.assertEqual(set(['rev3b']),
596
graph.heads(['rev3b', 'rev1']))
597
self.assertEqual(set(['rev2a', 'rev2b']),
598
graph.heads(['rev2a', 'rev2b']))
599
self.assertEqual(set(['rev3a']),
600
graph.heads(['rev3a', 'rev2a']))
601
self.assertEqual(set(['rev3a']),
602
graph.heads(['rev3a', 'rev2b']))
603
self.assertEqual(set(['rev3a']),
604
graph.heads(['rev3a', 'rev2a', 'rev2b']))
605
self.assertEqual(set(['rev3b']),
606
graph.heads(['rev3b', 'rev2a']))
607
self.assertEqual(set(['rev3b']),
608
graph.heads(['rev3b', 'rev2b']))
609
self.assertEqual(set(['rev3b']),
610
graph.heads(['rev3b', 'rev2a', 'rev2b']))
611
self.assertEqual(set(['rev3a', 'rev3b']),
612
graph.heads(['rev3a', 'rev3b']))
613
self.assertEqual(set(['rev3a', 'rev3b']),
614
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
616
def test_heads_shortcut(self):
617
graph = self.make_graph(history_shortcut)
619
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
620
graph.heads(['rev2a', 'rev2b', 'rev2c']))
621
self.assertEqual(set(['rev3a', 'rev3b']),
622
graph.heads(['rev3a', 'rev3b']))
623
self.assertEqual(set(['rev3a', 'rev3b']),
624
graph.heads(['rev2a', 'rev3a', 'rev3b']))
625
self.assertEqual(set(['rev2a', 'rev3b']),
626
graph.heads(['rev2a', 'rev3b']))
627
self.assertEqual(set(['rev2c', 'rev3a']),
628
graph.heads(['rev2c', 'rev3a']))
630
def _run_heads_break_deeper(self, graph_dict, search):
631
"""Run heads on a graph-as-a-dict.
633
If the search asks for the parents of 'deeper' the test will fail.
637
def get_parent_map(keys):
641
self.fail('key deeper was accessed')
642
result[key] = graph_dict[key]
645
an_obj.get_parent_map = get_parent_map
646
graph = _mod_graph.Graph(an_obj)
647
return graph.heads(search)
649
def test_heads_limits_search(self):
650
# test that a heads query does not search all of history
656
self.assertEqual(set(['left', 'right']),
657
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
659
def test_heads_limits_search_assymetric(self):
660
# test that a heads query does not search all of history
663
'midleft':['common'],
665
'common':['aftercommon'],
666
'aftercommon':['deeper'],
668
self.assertEqual(set(['left', 'right']),
669
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
671
def test_heads_limits_search_common_search_must_continue(self):
672
# test that common nodes are still queried, preventing
673
# all-the-way-to-origin behaviour in the following graph:
675
'h1':['shortcut', 'common1'],
677
'shortcut':['common2'],
678
'common1':['common2'],
679
'common2':['deeper'],
681
self.assertEqual(set(['h1', 'h2']),
682
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
684
def test_breadth_first_search_start_ghosts(self):
685
graph = self.make_graph({})
686
# with_ghosts reports the ghosts
687
search = graph._make_breadth_first_searcher(['a-ghost'])
688
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
689
self.assertRaises(StopIteration, search.next_with_ghosts)
691
search = graph._make_breadth_first_searcher(['a-ghost'])
692
self.assertEqual(set(['a-ghost']), search.next())
693
self.assertRaises(StopIteration, search.next)
695
def test_breadth_first_search_deep_ghosts(self):
696
graph = self.make_graph({
698
'present':['child', 'ghost'],
701
# with_ghosts reports the ghosts
702
search = graph._make_breadth_first_searcher(['head'])
703
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
704
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
705
self.assertEqual((set(['child']), set(['ghost'])),
706
search.next_with_ghosts())
707
self.assertRaises(StopIteration, search.next_with_ghosts)
709
search = graph._make_breadth_first_searcher(['head'])
710
self.assertEqual(set(['head']), search.next())
711
self.assertEqual(set(['present']), search.next())
712
self.assertEqual(set(['child', 'ghost']),
714
self.assertRaises(StopIteration, search.next)
716
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
717
# To make the API robust, we allow calling both next() and
718
# next_with_ghosts() on the same searcher.
719
graph = self.make_graph({
721
'present':['child', 'ghost'],
724
# start with next_with_ghosts
725
search = graph._make_breadth_first_searcher(['head'])
726
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
727
self.assertEqual(set(['present']), search.next())
728
self.assertEqual((set(['child']), set(['ghost'])),
729
search.next_with_ghosts())
730
self.assertRaises(StopIteration, search.next)
732
search = graph._make_breadth_first_searcher(['head'])
733
self.assertEqual(set(['head']), search.next())
734
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
735
self.assertEqual(set(['child', 'ghost']),
737
self.assertRaises(StopIteration, search.next_with_ghosts)
739
def test_breadth_first_change_search(self):
740
# Changing the search should work with both next and next_with_ghosts.
741
graph = self.make_graph({
743
'present':['stopped'],
747
search = graph._make_breadth_first_searcher(['head'])
748
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
749
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
750
self.assertEqual(set(['present']),
751
search.stop_searching_any(['present']))
752
self.assertEqual((set(['other']), set(['other_ghost'])),
753
search.start_searching(['other', 'other_ghost']))
754
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
755
self.assertRaises(StopIteration, search.next_with_ghosts)
757
search = graph._make_breadth_first_searcher(['head'])
758
self.assertEqual(set(['head']), search.next())
759
self.assertEqual(set(['present']), search.next())
760
self.assertEqual(set(['present']),
761
search.stop_searching_any(['present']))
762
search.start_searching(['other', 'other_ghost'])
763
self.assertEqual(set(['other_2']), search.next())
764
self.assertRaises(StopIteration, search.next)
766
def assertSeenAndResult(self, instructions, search, next):
767
"""Check the results of .seen and get_result() for a seach.
769
:param instructions: A list of tuples:
770
(seen, recipe, included_keys, starts, stops).
771
seen, recipe and included_keys are results to check on the search
772
and the searches get_result(). starts and stops are parameters to
773
pass to start_searching and stop_searching_any during each
774
iteration, if they are not None.
775
:param search: The search to use.
776
:param next: A callable to advance the search.
778
for seen, recipe, included_keys, starts, stops in instructions:
780
if starts is not None:
781
search.start_searching(starts)
782
if stops is not None:
783
search.stop_searching_any(stops)
784
result = search.get_result()
785
self.assertEqual(recipe, result.get_recipe())
786
self.assertEqual(set(included_keys), result.get_keys())
787
self.assertEqual(seen, search.seen)
789
def test_breadth_first_get_result_excludes_current_pending(self):
790
graph = self.make_graph({
792
'child':[NULL_REVISION],
795
search = graph._make_breadth_first_searcher(['head'])
796
# At the start, nothing has been seen, to its all excluded:
797
result = search.get_result()
798
self.assertEqual((set(['head']), set(['head']), 0),
800
self.assertEqual(set(), result.get_keys())
801
self.assertEqual(set(), search.seen)
804
(set(['head']), (set(['head']), set(['child']), 1),
805
['head'], None, None),
806
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
807
['head', 'child'], None, None),
808
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
809
['head', 'child', NULL_REVISION], None, None),
811
self.assertSeenAndResult(expected, search, search.next)
812
# using next_with_ghosts:
813
search = graph._make_breadth_first_searcher(['head'])
814
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
816
def test_breadth_first_get_result_starts_stops(self):
817
graph = self.make_graph({
819
'child':[NULL_REVISION],
820
'otherhead':['otherchild'],
821
'otherchild':['excluded'],
822
'excluded':[NULL_REVISION],
825
search = graph._make_breadth_first_searcher([])
826
# Starting with nothing and adding a search works:
827
search.start_searching(['head'])
828
# head has been seen:
829
result = search.get_result()
830
self.assertEqual((set(['head']), set(['child']), 1),
832
self.assertEqual(set(['head']), result.get_keys())
833
self.assertEqual(set(['head']), search.seen)
836
# stop at child, and start a new search at otherhead:
837
# - otherhead counts as seen immediately when start_searching is
839
(set(['head', 'child', 'otherhead']),
840
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
841
['head', 'otherhead'], ['otherhead'], ['child']),
842
(set(['head', 'child', 'otherhead', 'otherchild']),
843
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
844
['head', 'otherhead', 'otherchild'], None, None),
845
# stop searching excluded now
846
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
847
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
848
['head', 'otherhead', 'otherchild'], None, ['excluded']),
850
self.assertSeenAndResult(expected, search, search.next)
851
# using next_with_ghosts:
852
search = graph._make_breadth_first_searcher([])
853
search.start_searching(['head'])
854
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
856
def test_breadth_first_stop_searching_not_queried(self):
857
# A client should be able to say 'stop node X' even if X has not been
858
# returned to the client.
859
graph = self.make_graph({
860
'head':['child', 'ghost1'],
861
'child':[NULL_REVISION],
864
search = graph._make_breadth_first_searcher(['head'])
866
# NULL_REVISION and ghost1 have not been returned
867
(set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
868
['head'], None, [NULL_REVISION, 'ghost1']),
869
# ghost1 has been returned, NULL_REVISION is to be returned in the
871
(set(['head', 'child', 'ghost1']),
872
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
873
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
875
self.assertSeenAndResult(expected, search, search.next)
876
# using next_with_ghosts:
877
search = graph._make_breadth_first_searcher(['head'])
878
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
880
def test_breadth_first_get_result_ghosts_are_excluded(self):
881
graph = self.make_graph({
882
'head':['child', 'ghost'],
883
'child':[NULL_REVISION],
886
search = graph._make_breadth_first_searcher(['head'])
890
(set(['head']), set(['ghost', 'child']), 1),
891
['head'], None, None),
892
(set(['head', 'child', 'ghost']),
893
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
894
['head', 'child'], None, None),
896
self.assertSeenAndResult(expected, search, search.next)
897
# using next_with_ghosts:
898
search = graph._make_breadth_first_searcher(['head'])
899
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
901
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
902
graph = self.make_graph({
904
'child':[NULL_REVISION],
907
search = graph._make_breadth_first_searcher(['head'])
910
(set(['head', 'ghost']),
911
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
912
['head'], ['ghost'], None),
913
(set(['head', 'child', 'ghost']),
914
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
915
['head', 'child'], None, None),
917
self.assertSeenAndResult(expected, search, search.next)
918
# using next_with_ghosts:
919
search = graph._make_breadth_first_searcher(['head'])
920
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
922
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
923
graph = self.make_graph({
924
'head':[NULL_REVISION],
927
search = graph._make_breadth_first_searcher(['head'])
931
(set(['head']), set([NULL_REVISION]), 1),
932
['head'], None, None),
933
(set(['head', NULL_REVISION]),
934
(set(['head']), set([]), 2),
935
['head', NULL_REVISION], None, None),
937
self.assertSeenAndResult(expected, search, search.next)
938
# using next_with_ghosts:
939
search = graph._make_breadth_first_searcher(['head'])
940
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
942
def test_breadth_first_search_get_result_after_StopIteration(self):
943
# StopIteration should not invalid anything..
944
graph = self.make_graph({
945
'head':[NULL_REVISION],
948
search = graph._make_breadth_first_searcher(['head'])
952
(set(['head']), set([NULL_REVISION]), 1),
953
['head'], None, None),
954
(set(['head', 'ghost', NULL_REVISION]),
955
(set(['head', 'ghost']), set(['ghost']), 2),
956
['head', NULL_REVISION], ['ghost'], None),
958
self.assertSeenAndResult(expected, search, search.next)
959
self.assertRaises(StopIteration, search.next)
960
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
961
result = search.get_result()
962
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
964
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
965
# using next_with_ghosts:
966
search = graph._make_breadth_first_searcher(['head'])
967
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
968
self.assertRaises(StopIteration, search.next)
969
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
970
result = search.get_result()
971
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
973
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
976
class TestCachingParentsProvider(tests.TestCase):
979
super(TestCachingParentsProvider, self).setUp()
980
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
981
self.inst_pp = InstrumentedParentsProvider(dict_pp)
982
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
984
def test_get_parent_map(self):
985
"""Requesting the same revision should be returned from cache"""
986
self.assertEqual({}, self.caching_pp._cache)
987
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
988
self.assertEqual(['a'], self.inst_pp.calls)
989
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
990
# No new call, as it should have been returned from the cache
991
self.assertEqual(['a'], self.inst_pp.calls)
992
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
994
def test_get_parent_map_not_present(self):
995
"""The cache should also track when a revision doesn't exist"""
996
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
997
self.assertEqual(['b'], self.inst_pp.calls)
998
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1000
self.assertEqual(['b'], self.inst_pp.calls)
1001
self.assertEqual({'b':None}, self.caching_pp._cache)
1003
def test_get_parent_map_mixed(self):
1004
"""Anything that can be returned from cache, should be"""
1005
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1006
self.assertEqual(['b'], self.inst_pp.calls)
1007
self.assertEqual({'a':('b',)},
1008
self.caching_pp.get_parent_map(['a', 'b']))
1009
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1011
def test_get_parent_map_repeated(self):
1012
"""Asking for the same parent 2x will only forward 1 request."""
1013
self.assertEqual({'a':('b',)},
1014
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1015
# Use sorted because we don't care about the order, just that each is
1016
# only present 1 time.
1017
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
added
removed
bzrlib/tests/test_graph.py
