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
class InstrumentedParentsProvider(object):
243
def __init__(self, parents_provider):
245
self._real_parents_provider = parents_provider
247
def get_parent_map(self, nodes):
248
self.calls.extend(nodes)
249
return self._real_parents_provider.get_parent_map(nodes)
252
class TestGraph(TestCaseWithMemoryTransport):
254
def make_graph(self, ancestors):
255
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
257
def prepare_memory_tree(self, location):
258
tree = self.make_branch_and_memory_tree(location)
263
def build_ancestry(self, tree, ancestors):
264
"""Create an ancestry as specified by a graph dict
266
:param tree: A tree to use
267
:param ancestors: a dict of {node: [node_parent, ...]}
269
pending = [NULL_REVISION]
271
for descendant, parents in ancestors.iteritems():
272
for parent in parents:
273
descendants.setdefault(parent, []).append(descendant)
274
while len(pending) > 0:
275
cur_node = pending.pop()
276
for descendant in descendants.get(cur_node, []):
277
if tree.branch.repository.has_revision(descendant):
279
parents = [p for p in ancestors[descendant] if p is not
281
if len([p for p in parents if not
282
tree.branch.repository.has_revision(p)]) > 0:
284
tree.set_parent_ids(parents)
286
left_parent = parents[0]
288
left_parent = NULL_REVISION
289
tree.branch.set_last_revision_info(
290
len(tree.branch._lefthand_history(left_parent)),
292
tree.commit(descendant, rev_id=descendant)
293
pending.append(descendant)
296
"""Test finding least common ancestor.
298
ancestry_1 should always have a single common ancestor
300
graph = self.make_graph(ancestry_1)
301
self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
302
self.assertEqual(set([NULL_REVISION]),
303
graph.find_lca(NULL_REVISION, NULL_REVISION))
304
self.assertEqual(set([NULL_REVISION]),
305
graph.find_lca(NULL_REVISION, 'rev1'))
306
self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
307
self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
309
def test_no_unique_lca(self):
310
"""Test error when one revision is not in the graph"""
311
graph = self.make_graph(ancestry_1)
312
self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
315
def test_lca_criss_cross(self):
316
"""Test least-common-ancestor after a criss-cross merge."""
317
graph = self.make_graph(criss_cross)
318
self.assertEqual(set(['rev2a', 'rev2b']),
319
graph.find_lca('rev3a', 'rev3b'))
320
self.assertEqual(set(['rev2b']),
321
graph.find_lca('rev3a', 'rev3b', 'rev2b'))
323
def test_lca_shortcut(self):
324
"""Test least-common ancestor on this history shortcut"""
325
graph = self.make_graph(history_shortcut)
326
self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
328
def test_recursive_unique_lca(self):
329
"""Test finding a unique least common ancestor.
331
ancestry_1 should always have a single common ancestor
333
graph = self.make_graph(ancestry_1)
334
self.assertEqual(NULL_REVISION,
335
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
336
self.assertEqual(NULL_REVISION,
337
graph.find_unique_lca(NULL_REVISION, 'rev1'))
338
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
339
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
340
self.assertEqual(('rev1', 1,),
341
graph.find_unique_lca('rev2a', 'rev2b',
344
def test_unique_lca_criss_cross(self):
345
"""Ensure we don't pick non-unique lcas in a criss-cross"""
346
graph = self.make_graph(criss_cross)
347
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
348
lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
349
self.assertEqual('rev1', lca)
350
self.assertEqual(2, steps)
352
def test_unique_lca_null_revision(self):
353
"""Ensure we pick NULL_REVISION when necessary"""
354
graph = self.make_graph(criss_cross2)
355
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
356
self.assertEqual(NULL_REVISION,
357
graph.find_unique_lca('rev2a', 'rev2b'))
359
def test_unique_lca_null_revision2(self):
360
"""Ensure we pick NULL_REVISION when necessary"""
361
graph = self.make_graph(ancestry_2)
362
self.assertEqual(NULL_REVISION,
363
graph.find_unique_lca('rev4a', 'rev1b'))
365
def test_lca_double_shortcut(self):
366
graph = self.make_graph(double_shortcut)
367
self.assertEqual('c', graph.find_unique_lca('f', 'g'))
369
def test_common_ancestor_two_repos(self):
370
"""Ensure we do unique_lca using data from two repos"""
371
mainline_tree = self.prepare_memory_tree('mainline')
372
self.build_ancestry(mainline_tree, mainline)
373
self.addCleanup(mainline_tree.unlock)
375
# This is cheating, because the revisions in the graph are actually
376
# different revisions, despite having the same revision-id.
377
feature_tree = self.prepare_memory_tree('feature')
378
self.build_ancestry(feature_tree, feature_branch)
379
self.addCleanup(feature_tree.unlock)
381
graph = mainline_tree.branch.repository.get_graph(
382
feature_tree.branch.repository)
383
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
385
def test_graph_difference(self):
386
graph = self.make_graph(ancestry_1)
387
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
388
self.assertEqual((set(), set(['rev1'])),
389
graph.find_difference(NULL_REVISION, 'rev1'))
390
self.assertEqual((set(['rev1']), set()),
391
graph.find_difference('rev1', NULL_REVISION))
392
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
393
graph.find_difference('rev3', 'rev2b'))
394
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
395
graph.find_difference('rev4', 'rev2b'))
397
def test_graph_difference_separate_ancestry(self):
398
graph = self.make_graph(ancestry_2)
399
self.assertEqual((set(['rev1a']), set(['rev1b'])),
400
graph.find_difference('rev1a', 'rev1b'))
401
self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
403
graph.find_difference('rev4a', 'rev1b'))
405
def test_graph_difference_criss_cross(self):
406
graph = self.make_graph(criss_cross)
407
self.assertEqual((set(['rev3a']), set(['rev3b'])),
408
graph.find_difference('rev3a', 'rev3b'))
409
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
410
graph.find_difference('rev2a', 'rev3b'))
412
def test_graph_difference_extended_history(self):
413
graph = self.make_graph(extended_history_shortcut)
414
self.expectFailure('find_difference cannot handle shortcuts',
415
self.assertEqual, (set(['e']), set(['f'])),
416
graph.find_difference('e', 'f'))
417
self.assertEqual((set(['e']), set(['f'])),
418
graph.find_difference('e', 'f'))
419
self.assertEqual((set(['f']), set(['e'])),
420
graph.find_difference('f', 'e'))
422
def test_graph_difference_double_shortcut(self):
423
graph = self.make_graph(double_shortcut)
424
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
425
graph.find_difference('f', 'g'))
427
def test_graph_difference_complex_shortcut(self):
428
graph = self.make_graph(complex_shortcut)
429
self.expectFailure('find_difference cannot handle shortcuts',
430
self.assertEqual, (set(['m']), set(['h', 'n'])),
431
graph.find_difference('m', 'n'))
432
self.assertEqual((set(['m']), set(['h', 'n'])),
433
graph.find_difference('m', 'n'))
435
def test_graph_difference_shortcut_extra_root(self):
436
graph = self.make_graph(shortcut_extra_root)
437
self.expectFailure('find_difference cannot handle shortcuts',
438
self.assertEqual, (set(['e']), set(['f', 'g'])),
439
graph.find_difference('e', 'f'))
440
self.assertEqual((set(['e']), set(['f', 'g'])),
441
graph.find_difference('e', 'f'))
443
def test_stacked_parents_provider(self):
444
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
445
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
446
stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
447
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
448
stacked.get_parent_map(['rev1', 'rev2']))
449
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
450
stacked.get_parent_map(['rev2', 'rev1']))
451
self.assertEqual({'rev2':['rev3']},
452
stacked.get_parent_map(['rev2', 'rev2']))
453
self.assertEqual({'rev1':['rev4']},
454
stacked.get_parent_map(['rev1', 'rev1']))
456
def test_iter_topo_order(self):
457
graph = self.make_graph(ancestry_1)
458
args = ['rev2a', 'rev3', 'rev1']
459
topo_args = list(graph.iter_topo_order(args))
460
self.assertEqual(set(args), set(topo_args))
461
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
462
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
464
def test_is_ancestor(self):
465
graph = self.make_graph(ancestry_1)
466
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
467
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
468
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
469
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
470
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
471
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
472
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
473
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
474
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
475
instrumented_provider = InstrumentedParentsProvider(graph)
476
instrumented_graph = _mod_graph.Graph(instrumented_provider)
477
instrumented_graph.is_ancestor('rev2a', 'rev2b')
478
self.assertTrue('null:' not in instrumented_provider.calls)
480
def test_is_ancestor_boundary(self):
481
"""Ensure that we avoid searching the whole graph.
483
This requires searching through b as a common ancestor, so we
484
can identify that e is common.
486
graph = self.make_graph(boundary)
487
instrumented_provider = InstrumentedParentsProvider(graph)
488
graph = _mod_graph.Graph(instrumented_provider)
489
self.assertFalse(graph.is_ancestor('a', 'c'))
490
self.assertTrue('null:' not in instrumented_provider.calls)
492
def test_filter_candidate_lca(self):
493
"""Test filter_candidate_lca for a corner case
495
This tests the case where we encounter the end of iteration for 'e'
496
in the same pass as we discover that 'd' is an ancestor of 'e', and
497
therefore 'e' can't be an lca.
499
To compensate for different dict orderings on other Python
500
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
502
# This test is sensitive to the iteration order of dicts. It will
503
# pass incorrectly if 'e' and 'a' sort before 'c'
512
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
513
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
514
self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
516
def test_heads_null(self):
517
graph = self.make_graph(ancestry_1)
518
self.assertEqual(set(['null:']), graph.heads(['null:']))
519
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
520
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
521
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
522
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
524
def test_heads_one(self):
525
# A single node will always be a head
526
graph = self.make_graph(ancestry_1)
527
self.assertEqual(set(['null:']), graph.heads(['null:']))
528
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
529
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
530
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
531
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
532
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
534
def test_heads_single(self):
535
graph = self.make_graph(ancestry_1)
536
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
537
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
538
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
539
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
540
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
541
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
542
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
543
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
545
def test_heads_two_heads(self):
546
graph = self.make_graph(ancestry_1)
547
self.assertEqual(set(['rev2a', 'rev2b']),
548
graph.heads(['rev2a', 'rev2b']))
549
self.assertEqual(set(['rev3', 'rev2b']),
550
graph.heads(['rev3', 'rev2b']))
552
def test_heads_criss_cross(self):
553
graph = self.make_graph(criss_cross)
554
self.assertEqual(set(['rev2a']),
555
graph.heads(['rev2a', 'rev1']))
556
self.assertEqual(set(['rev2b']),
557
graph.heads(['rev2b', 'rev1']))
558
self.assertEqual(set(['rev3a']),
559
graph.heads(['rev3a', 'rev1']))
560
self.assertEqual(set(['rev3b']),
561
graph.heads(['rev3b', 'rev1']))
562
self.assertEqual(set(['rev2a', 'rev2b']),
563
graph.heads(['rev2a', 'rev2b']))
564
self.assertEqual(set(['rev3a']),
565
graph.heads(['rev3a', 'rev2a']))
566
self.assertEqual(set(['rev3a']),
567
graph.heads(['rev3a', 'rev2b']))
568
self.assertEqual(set(['rev3a']),
569
graph.heads(['rev3a', 'rev2a', 'rev2b']))
570
self.assertEqual(set(['rev3b']),
571
graph.heads(['rev3b', 'rev2a']))
572
self.assertEqual(set(['rev3b']),
573
graph.heads(['rev3b', 'rev2b']))
574
self.assertEqual(set(['rev3b']),
575
graph.heads(['rev3b', 'rev2a', 'rev2b']))
576
self.assertEqual(set(['rev3a', 'rev3b']),
577
graph.heads(['rev3a', 'rev3b']))
578
self.assertEqual(set(['rev3a', 'rev3b']),
579
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
581
def test_heads_shortcut(self):
582
graph = self.make_graph(history_shortcut)
584
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
585
graph.heads(['rev2a', 'rev2b', 'rev2c']))
586
self.assertEqual(set(['rev3a', 'rev3b']),
587
graph.heads(['rev3a', 'rev3b']))
588
self.assertEqual(set(['rev3a', 'rev3b']),
589
graph.heads(['rev2a', 'rev3a', 'rev3b']))
590
self.assertEqual(set(['rev2a', 'rev3b']),
591
graph.heads(['rev2a', 'rev3b']))
592
self.assertEqual(set(['rev2c', 'rev3a']),
593
graph.heads(['rev2c', 'rev3a']))
595
def _run_heads_break_deeper(self, graph_dict, search):
596
"""Run heads on a graph-as-a-dict.
598
If the search asks for the parents of 'deeper' the test will fail.
602
def get_parent_map(keys):
606
self.fail('key deeper was accessed')
607
result[key] = graph_dict[key]
610
an_obj.get_parent_map = get_parent_map
611
graph = _mod_graph.Graph(an_obj)
612
return graph.heads(search)
614
def test_heads_limits_search(self):
615
# test that a heads query does not search all of history
621
self.assertEqual(set(['left', 'right']),
622
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
624
def test_heads_limits_search_assymetric(self):
625
# test that a heads query does not search all of history
628
'midleft':['common'],
630
'common':['aftercommon'],
631
'aftercommon':['deeper'],
633
self.assertEqual(set(['left', 'right']),
634
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
636
def test_heads_limits_search_common_search_must_continue(self):
637
# test that common nodes are still queried, preventing
638
# all-the-way-to-origin behaviour in the following graph:
640
'h1':['shortcut', 'common1'],
642
'shortcut':['common2'],
643
'common1':['common2'],
644
'common2':['deeper'],
646
self.assertEqual(set(['h1', 'h2']),
647
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
649
def test_breadth_first_search_start_ghosts(self):
650
graph = self.make_graph({})
651
# with_ghosts reports the ghosts
652
search = graph._make_breadth_first_searcher(['a-ghost'])
653
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
654
self.assertRaises(StopIteration, search.next_with_ghosts)
656
search = graph._make_breadth_first_searcher(['a-ghost'])
657
self.assertEqual(set(['a-ghost']), search.next())
658
self.assertRaises(StopIteration, search.next)
660
def test_breadth_first_search_deep_ghosts(self):
661
graph = self.make_graph({
663
'present':['child', 'ghost'],
666
# with_ghosts reports the ghosts
667
search = graph._make_breadth_first_searcher(['head'])
668
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
669
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
670
self.assertEqual((set(['child']), set(['ghost'])),
671
search.next_with_ghosts())
672
self.assertRaises(StopIteration, search.next_with_ghosts)
674
search = graph._make_breadth_first_searcher(['head'])
675
self.assertEqual(set(['head']), search.next())
676
self.assertEqual(set(['present']), search.next())
677
self.assertEqual(set(['child', 'ghost']),
679
self.assertRaises(StopIteration, search.next)
681
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
682
# To make the API robust, we allow calling both next() and
683
# next_with_ghosts() on the same searcher.
684
graph = self.make_graph({
686
'present':['child', 'ghost'],
689
# start with next_with_ghosts
690
search = graph._make_breadth_first_searcher(['head'])
691
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
692
self.assertEqual(set(['present']), search.next())
693
self.assertEqual((set(['child']), set(['ghost'])),
694
search.next_with_ghosts())
695
self.assertRaises(StopIteration, search.next)
697
search = graph._make_breadth_first_searcher(['head'])
698
self.assertEqual(set(['head']), search.next())
699
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
700
self.assertEqual(set(['child', 'ghost']),
702
self.assertRaises(StopIteration, search.next_with_ghosts)
704
def test_breadth_first_change_search(self):
705
# Changing the search should work with both next and next_with_ghosts.
706
graph = self.make_graph({
708
'present':['stopped'],
712
search = graph._make_breadth_first_searcher(['head'])
713
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
714
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
715
self.assertEqual(set(['present']),
716
search.stop_searching_any(['present']))
717
self.assertEqual((set(['other']), set(['other_ghost'])),
718
search.start_searching(['other', 'other_ghost']))
719
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
720
self.assertRaises(StopIteration, search.next_with_ghosts)
722
search = graph._make_breadth_first_searcher(['head'])
723
self.assertEqual(set(['head']), search.next())
724
self.assertEqual(set(['present']), search.next())
725
self.assertEqual(set(['present']),
726
search.stop_searching_any(['present']))
727
search.start_searching(['other', 'other_ghost'])
728
self.assertEqual(set(['other_2']), search.next())
729
self.assertRaises(StopIteration, search.next)
731
def assertSeenAndResult(self, instructions, search, next):
732
"""Check the results of .seen and get_result() for a seach.
734
:param instructions: A list of tuples:
735
(seen, recipe, included_keys, starts, stops).
736
seen, recipe and included_keys are results to check on the search
737
and the searches get_result(). starts and stops are parameters to
738
pass to start_searching and stop_searching_any during each
739
iteration, if they are not None.
740
:param search: The search to use.
741
:param next: A callable to advance the search.
743
for seen, recipe, included_keys, starts, stops in instructions:
745
if starts is not None:
746
search.start_searching(starts)
747
if stops is not None:
748
search.stop_searching_any(stops)
749
result = search.get_result()
750
self.assertEqual(recipe, result.get_recipe())
751
self.assertEqual(set(included_keys), result.get_keys())
752
self.assertEqual(seen, search.seen)
754
def test_breadth_first_get_result_excludes_current_pending(self):
755
graph = self.make_graph({
757
'child':[NULL_REVISION],
760
search = graph._make_breadth_first_searcher(['head'])
761
# At the start, nothing has been seen, to its all excluded:
762
result = search.get_result()
763
self.assertEqual((set(['head']), set(['head']), 0),
765
self.assertEqual(set(), result.get_keys())
766
self.assertEqual(set(), search.seen)
769
(set(['head']), (set(['head']), set(['child']), 1),
770
['head'], None, None),
771
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
772
['head', 'child'], None, None),
773
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
774
['head', 'child', NULL_REVISION], None, None),
776
self.assertSeenAndResult(expected, search, search.next)
777
# using next_with_ghosts:
778
search = graph._make_breadth_first_searcher(['head'])
779
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
781
def test_breadth_first_get_result_starts_stops(self):
782
graph = self.make_graph({
784
'child':[NULL_REVISION],
785
'otherhead':['otherchild'],
786
'otherchild':['excluded'],
787
'excluded':[NULL_REVISION],
790
search = graph._make_breadth_first_searcher([])
791
# Starting with nothing and adding a search works:
792
search.start_searching(['head'])
793
# head has been seen:
794
result = search.get_result()
795
self.assertEqual((set(['head']), set(['child']), 1),
797
self.assertEqual(set(['head']), result.get_keys())
798
self.assertEqual(set(['head']), search.seen)
801
# stop at child, and start a new search at otherhead:
802
# - otherhead counts as seen immediately when start_searching is
804
(set(['head', 'child', 'otherhead']),
805
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
806
['head', 'otherhead'], ['otherhead'], ['child']),
807
(set(['head', 'child', 'otherhead', 'otherchild']),
808
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
809
['head', 'otherhead', 'otherchild'], None, None),
810
# stop searching excluded now
811
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
812
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
813
['head', 'otherhead', 'otherchild'], None, ['excluded']),
815
self.assertSeenAndResult(expected, search, search.next)
816
# using next_with_ghosts:
817
search = graph._make_breadth_first_searcher([])
818
search.start_searching(['head'])
819
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
821
def test_breadth_first_stop_searching_not_queried(self):
822
# A client should be able to say 'stop node X' even if X has not been
823
# returned to the client.
824
graph = self.make_graph({
825
'head':['child', 'ghost1'],
826
'child':[NULL_REVISION],
829
search = graph._make_breadth_first_searcher(['head'])
831
# NULL_REVISION and ghost1 have not been returned
832
(set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
833
['head'], None, [NULL_REVISION, 'ghost1']),
834
# ghost1 has been returned, NULL_REVISION is to be returned in the
836
(set(['head', 'child', 'ghost1']),
837
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
838
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
840
self.assertSeenAndResult(expected, search, search.next)
841
# using next_with_ghosts:
842
search = graph._make_breadth_first_searcher(['head'])
843
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
845
def test_breadth_first_get_result_ghosts_are_excluded(self):
846
graph = self.make_graph({
847
'head':['child', 'ghost'],
848
'child':[NULL_REVISION],
851
search = graph._make_breadth_first_searcher(['head'])
855
(set(['head']), set(['ghost', 'child']), 1),
856
['head'], None, None),
857
(set(['head', 'child', 'ghost']),
858
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
859
['head', 'child'], None, None),
861
self.assertSeenAndResult(expected, search, search.next)
862
# using next_with_ghosts:
863
search = graph._make_breadth_first_searcher(['head'])
864
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
866
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
867
graph = self.make_graph({
869
'child':[NULL_REVISION],
872
search = graph._make_breadth_first_searcher(['head'])
875
(set(['head', 'ghost']),
876
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
877
['head'], ['ghost'], None),
878
(set(['head', 'child', 'ghost']),
879
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
880
['head', 'child'], None, None),
882
self.assertSeenAndResult(expected, search, search.next)
883
# using next_with_ghosts:
884
search = graph._make_breadth_first_searcher(['head'])
885
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
887
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
888
graph = self.make_graph({
889
'head':[NULL_REVISION],
892
search = graph._make_breadth_first_searcher(['head'])
896
(set(['head']), set([NULL_REVISION]), 1),
897
['head'], None, None),
898
(set(['head', NULL_REVISION]),
899
(set(['head']), set([]), 2),
900
['head', NULL_REVISION], None, None),
902
self.assertSeenAndResult(expected, search, search.next)
903
# using next_with_ghosts:
904
search = graph._make_breadth_first_searcher(['head'])
905
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
907
def test_breadth_first_search_get_result_after_StopIteration(self):
908
# StopIteration should not invalid anything..
909
graph = self.make_graph({
910
'head':[NULL_REVISION],
913
search = graph._make_breadth_first_searcher(['head'])
917
(set(['head']), set([NULL_REVISION]), 1),
918
['head'], None, None),
919
(set(['head', 'ghost', NULL_REVISION]),
920
(set(['head', 'ghost']), set(['ghost']), 2),
921
['head', NULL_REVISION], ['ghost'], None),
923
self.assertSeenAndResult(expected, search, search.next)
924
self.assertRaises(StopIteration, search.next)
925
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
926
result = search.get_result()
927
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
929
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
930
# using next_with_ghosts:
931
search = graph._make_breadth_first_searcher(['head'])
932
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
933
self.assertRaises(StopIteration, search.next)
934
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
935
result = search.get_result()
936
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
938
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
941
class TestCachingParentsProvider(tests.TestCase):
944
super(TestCachingParentsProvider, self).setUp()
945
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
946
self.inst_pp = InstrumentedParentsProvider(dict_pp)
947
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
949
def test_get_parent_map(self):
950
"""Requesting the same revision should be returned from cache"""
951
self.assertEqual({}, self.caching_pp._cache)
952
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
953
self.assertEqual(['a'], self.inst_pp.calls)
954
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
955
# No new call, as it should have been returned from the cache
956
self.assertEqual(['a'], self.inst_pp.calls)
957
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
959
def test_get_parent_map_not_present(self):
960
"""The cache should also track when a revision doesn't exist"""
961
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
962
self.assertEqual(['b'], self.inst_pp.calls)
963
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
965
self.assertEqual(['b'], self.inst_pp.calls)
966
self.assertEqual({'b':None}, self.caching_pp._cache)
968
def test_get_parent_map_mixed(self):
969
"""Anything that can be returned from cache, should be"""
970
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
971
self.assertEqual(['b'], self.inst_pp.calls)
972
self.assertEqual({'a':('b',)},
973
self.caching_pp.get_parent_map(['a', 'b']))
974
self.assertEqual(['b', 'a'], self.inst_pp.calls)
976
def test_get_parent_map_repeated(self):
977
"""Asking for the same parent 2x will only forward 1 request."""
978
self.assertEqual({'a':('b',)},
979
self.caching_pp.get_parent_map(['b', 'a', 'b']))
980
# Use sorted because we don't care about the order, just that each is
981
# only present 1 time.
982
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
added
removed
bzrlib/tests/test_graph.py
