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_parents(self, nodes):
248
self.calls.extend(nodes)
249
return self._real_parents_provider.get_parents(nodes)
251
def get_parent_map(self, nodes):
252
self.calls.extend(nodes)
253
return self._real_parents_provider.get_parent_map(nodes)
256
class TestGraph(TestCaseWithMemoryTransport):
258
def make_graph(self, ancestors):
259
# XXX: This seems valid, is there a reason to actually create a
260
# repository and put things in it?
261
return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
262
tree = self.prepare_memory_tree('.')
263
self.build_ancestry(tree, ancestors)
264
self.addCleanup(tree.unlock)
265
return tree.branch.repository.get_graph()
267
def prepare_memory_tree(self, location):
268
tree = self.make_branch_and_memory_tree(location)
273
def build_ancestry(self, tree, ancestors):
274
"""Create an ancestry as specified by a graph dict
276
:param tree: A tree to use
277
:param ancestors: a dict of {node: [node_parent, ...]}
279
pending = [NULL_REVISION]
281
for descendant, parents in ancestors.iteritems():
282
for parent in parents:
283
descendants.setdefault(parent, []).append(descendant)
284
while len(pending) > 0:
285
cur_node = pending.pop()
286
for descendant in descendants.get(cur_node, []):
287
if tree.branch.repository.has_revision(descendant):
289
parents = [p for p in ancestors[descendant] if p is not
291
if len([p for p in parents if not
292
tree.branch.repository.has_revision(p)]) > 0:
294
tree.set_parent_ids(parents)
296
left_parent = parents[0]
298
left_parent = NULL_REVISION
299
tree.branch.set_last_revision_info(
300
len(tree.branch._lefthand_history(left_parent)),
302
tree.commit(descendant, rev_id=descendant)
303
pending.append(descendant)
306
"""Test finding least common ancestor.
308
ancestry_1 should always have a single common ancestor
310
graph = self.make_graph(ancestry_1)
311
self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
312
self.assertEqual(set([NULL_REVISION]),
313
graph.find_lca(NULL_REVISION, NULL_REVISION))
314
self.assertEqual(set([NULL_REVISION]),
315
graph.find_lca(NULL_REVISION, 'rev1'))
316
self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
317
self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
319
def test_no_unique_lca(self):
320
"""Test error when one revision is not in the graph"""
321
graph = self.make_graph(ancestry_1)
322
self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
325
def test_lca_criss_cross(self):
326
"""Test least-common-ancestor after a criss-cross merge."""
327
graph = self.make_graph(criss_cross)
328
self.assertEqual(set(['rev2a', 'rev2b']),
329
graph.find_lca('rev3a', 'rev3b'))
330
self.assertEqual(set(['rev2b']),
331
graph.find_lca('rev3a', 'rev3b', 'rev2b'))
333
def test_lca_shortcut(self):
334
"""Test least-common ancestor on this history shortcut"""
335
graph = self.make_graph(history_shortcut)
336
self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
338
def test_recursive_unique_lca(self):
339
"""Test finding a unique least common ancestor.
341
ancestry_1 should always have a single common ancestor
343
graph = self.make_graph(ancestry_1)
344
self.assertEqual(NULL_REVISION,
345
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
346
self.assertEqual(NULL_REVISION,
347
graph.find_unique_lca(NULL_REVISION, 'rev1'))
348
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
349
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
350
self.assertEqual(('rev1', 1,),
351
graph.find_unique_lca('rev2a', 'rev2b',
354
def test_unique_lca_criss_cross(self):
355
"""Ensure we don't pick non-unique lcas in a criss-cross"""
356
graph = self.make_graph(criss_cross)
357
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
358
lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
359
self.assertEqual('rev1', lca)
360
self.assertEqual(2, steps)
362
def test_unique_lca_null_revision(self):
363
"""Ensure we pick NULL_REVISION when necessary"""
364
graph = self.make_graph(criss_cross2)
365
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
366
self.assertEqual(NULL_REVISION,
367
graph.find_unique_lca('rev2a', 'rev2b'))
369
def test_unique_lca_null_revision2(self):
370
"""Ensure we pick NULL_REVISION when necessary"""
371
graph = self.make_graph(ancestry_2)
372
self.assertEqual(NULL_REVISION,
373
graph.find_unique_lca('rev4a', 'rev1b'))
375
def test_lca_double_shortcut(self):
376
graph = self.make_graph(double_shortcut)
377
self.assertEqual('c', graph.find_unique_lca('f', 'g'))
379
def test_common_ancestor_two_repos(self):
380
"""Ensure we do unique_lca using data from two repos"""
381
mainline_tree = self.prepare_memory_tree('mainline')
382
self.build_ancestry(mainline_tree, mainline)
383
self.addCleanup(mainline_tree.unlock)
385
# This is cheating, because the revisions in the graph are actually
386
# different revisions, despite having the same revision-id.
387
feature_tree = self.prepare_memory_tree('feature')
388
self.build_ancestry(feature_tree, feature_branch)
389
self.addCleanup(feature_tree.unlock)
391
graph = mainline_tree.branch.repository.get_graph(
392
feature_tree.branch.repository)
393
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
395
def test_graph_difference(self):
396
graph = self.make_graph(ancestry_1)
397
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
398
self.assertEqual((set(), set(['rev1'])),
399
graph.find_difference(NULL_REVISION, 'rev1'))
400
self.assertEqual((set(['rev1']), set()),
401
graph.find_difference('rev1', NULL_REVISION))
402
self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
403
graph.find_difference('rev3', 'rev2b'))
404
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
405
graph.find_difference('rev4', 'rev2b'))
407
def test_graph_difference_separate_ancestry(self):
408
graph = self.make_graph(ancestry_2)
409
self.assertEqual((set(['rev1a']), set(['rev1b'])),
410
graph.find_difference('rev1a', 'rev1b'))
411
self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
413
graph.find_difference('rev4a', 'rev1b'))
415
def test_graph_difference_criss_cross(self):
416
graph = self.make_graph(criss_cross)
417
self.assertEqual((set(['rev3a']), set(['rev3b'])),
418
graph.find_difference('rev3a', 'rev3b'))
419
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
420
graph.find_difference('rev2a', 'rev3b'))
422
def test_graph_difference_extended_history(self):
423
graph = self.make_graph(extended_history_shortcut)
424
self.expectFailure('find_difference cannot handle shortcuts',
425
self.assertEqual, (set(['e']), set(['f'])),
426
graph.find_difference('e', 'f'))
427
self.assertEqual((set(['e']), set(['f'])),
428
graph.find_difference('e', 'f'))
429
self.assertEqual((set(['f']), set(['e'])),
430
graph.find_difference('f', 'e'))
432
def test_graph_difference_double_shortcut(self):
433
graph = self.make_graph(double_shortcut)
434
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
435
graph.find_difference('f', 'g'))
437
def test_graph_difference_complex_shortcut(self):
438
graph = self.make_graph(complex_shortcut)
439
self.expectFailure('find_difference cannot handle shortcuts',
440
self.assertEqual, (set(['m']), set(['h', 'n'])),
441
graph.find_difference('m', 'n'))
442
self.assertEqual((set(['m']), set(['h', 'n'])),
443
graph.find_difference('m', 'n'))
445
def test_graph_difference_shortcut_extra_root(self):
446
graph = self.make_graph(shortcut_extra_root)
447
self.expectFailure('find_difference cannot handle shortcuts',
448
self.assertEqual, (set(['e']), set(['f', 'g'])),
449
graph.find_difference('e', 'f'))
450
self.assertEqual((set(['e']), set(['f', 'g'])),
451
graph.find_difference('e', 'f'))
453
def test_stacked_parents_provider_get_parents(self):
454
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
455
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
456
stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
457
self.assertEqual([['rev4',], ['rev3']],
458
self.applyDeprecated(symbol_versioning.one_one,
459
stacked.get_parents, ['rev1', 'rev2']))
460
self.assertEqual([['rev3',], ['rev4']],
461
self.applyDeprecated(symbol_versioning.one_one,
462
stacked.get_parents, ['rev2', 'rev1']))
463
self.assertEqual([['rev3',], ['rev3']],
464
self.applyDeprecated(symbol_versioning.one_one,
465
stacked.get_parents, ['rev2', 'rev2']))
466
self.assertEqual([['rev4',], ['rev4']],
467
self.applyDeprecated(symbol_versioning.one_one,
468
stacked.get_parents, ['rev1', 'rev1']))
470
def test_stacked_parents_provider(self):
471
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
472
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
473
stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
474
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
475
stacked.get_parent_map(['rev1', 'rev2']))
476
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
477
stacked.get_parent_map(['rev2', 'rev1']))
478
self.assertEqual({'rev2':['rev3']},
479
stacked.get_parent_map(['rev2', 'rev2']))
480
self.assertEqual({'rev1':['rev4']},
481
stacked.get_parent_map(['rev1', 'rev1']))
483
def test_iter_topo_order(self):
484
graph = self.make_graph(ancestry_1)
485
args = ['rev2a', 'rev3', 'rev1']
486
topo_args = list(graph.iter_topo_order(args))
487
self.assertEqual(set(args), set(topo_args))
488
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
489
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
491
def test_is_ancestor(self):
492
graph = self.make_graph(ancestry_1)
493
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
494
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
495
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
496
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
497
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
498
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
499
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
500
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
501
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
502
instrumented_provider = InstrumentedParentsProvider(graph)
503
instrumented_graph = _mod_graph.Graph(instrumented_provider)
504
instrumented_graph.is_ancestor('rev2a', 'rev2b')
505
self.assertTrue('null:' not in instrumented_provider.calls)
507
def test_is_ancestor_boundary(self):
508
"""Ensure that we avoid searching the whole graph.
510
This requires searching through b as a common ancestor, so we
511
can identify that e is common.
513
graph = self.make_graph(boundary)
514
instrumented_provider = InstrumentedParentsProvider(graph)
515
graph = _mod_graph.Graph(instrumented_provider)
516
self.assertFalse(graph.is_ancestor('a', 'c'))
517
self.assertTrue('null:' not in instrumented_provider.calls)
519
def test_filter_candidate_lca(self):
520
"""Test filter_candidate_lca for a corner case
522
This tests the case where we encounter the end of iteration for 'e'
523
in the same pass as we discover that 'd' is an ancestor of 'e', and
524
therefore 'e' can't be an lca.
526
To compensate for different dict orderings on other Python
527
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
529
# This test is sensitive to the iteration order of dicts. It will
530
# pass incorrectly if 'e' and 'a' sort before 'c'
539
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
540
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
541
self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
543
def test_heads_null(self):
544
graph = self.make_graph(ancestry_1)
545
self.assertEqual(set(['null:']), graph.heads(['null:']))
546
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
547
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
548
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
549
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
551
def test_heads_one(self):
552
# A single node will always be a head
553
graph = self.make_graph(ancestry_1)
554
self.assertEqual(set(['null:']), graph.heads(['null:']))
555
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
556
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
557
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
558
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
559
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
561
def test_heads_single(self):
562
graph = self.make_graph(ancestry_1)
563
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
564
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
565
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
566
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
567
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
568
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
569
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
570
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
572
def test_heads_two_heads(self):
573
graph = self.make_graph(ancestry_1)
574
self.assertEqual(set(['rev2a', 'rev2b']),
575
graph.heads(['rev2a', 'rev2b']))
576
self.assertEqual(set(['rev3', 'rev2b']),
577
graph.heads(['rev3', 'rev2b']))
579
def test_heads_criss_cross(self):
580
graph = self.make_graph(criss_cross)
581
self.assertEqual(set(['rev2a']),
582
graph.heads(['rev2a', 'rev1']))
583
self.assertEqual(set(['rev2b']),
584
graph.heads(['rev2b', 'rev1']))
585
self.assertEqual(set(['rev3a']),
586
graph.heads(['rev3a', 'rev1']))
587
self.assertEqual(set(['rev3b']),
588
graph.heads(['rev3b', 'rev1']))
589
self.assertEqual(set(['rev2a', 'rev2b']),
590
graph.heads(['rev2a', 'rev2b']))
591
self.assertEqual(set(['rev3a']),
592
graph.heads(['rev3a', 'rev2a']))
593
self.assertEqual(set(['rev3a']),
594
graph.heads(['rev3a', 'rev2b']))
595
self.assertEqual(set(['rev3a']),
596
graph.heads(['rev3a', 'rev2a', 'rev2b']))
597
self.assertEqual(set(['rev3b']),
598
graph.heads(['rev3b', 'rev2a']))
599
self.assertEqual(set(['rev3b']),
600
graph.heads(['rev3b', 'rev2b']))
601
self.assertEqual(set(['rev3b']),
602
graph.heads(['rev3b', 'rev2a', 'rev2b']))
603
self.assertEqual(set(['rev3a', 'rev3b']),
604
graph.heads(['rev3a', 'rev3b']))
605
self.assertEqual(set(['rev3a', 'rev3b']),
606
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
608
def test_heads_shortcut(self):
609
graph = self.make_graph(history_shortcut)
611
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
612
graph.heads(['rev2a', 'rev2b', 'rev2c']))
613
self.assertEqual(set(['rev3a', 'rev3b']),
614
graph.heads(['rev3a', 'rev3b']))
615
self.assertEqual(set(['rev3a', 'rev3b']),
616
graph.heads(['rev2a', 'rev3a', 'rev3b']))
617
self.assertEqual(set(['rev2a', 'rev3b']),
618
graph.heads(['rev2a', 'rev3b']))
619
self.assertEqual(set(['rev2c', 'rev3a']),
620
graph.heads(['rev2c', 'rev3a']))
622
def _run_heads_break_deeper(self, graph_dict, search):
623
"""Run heads on a graph-as-a-dict.
625
If the search asks for the parents of 'deeper' the test will fail.
629
def get_parents(keys):
633
self.fail('key deeper was accessed')
634
result.append(graph_dict[key])
636
def get_parent_map(keys):
640
self.fail('key deeper was accessed')
641
result[key] = graph_dict[key]
644
an_obj.get_parents = get_parents
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']))
685
class TestCachingParentsProvider(tests.TestCase):
688
super(TestCachingParentsProvider, self).setUp()
689
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
690
self.inst_pp = InstrumentedParentsProvider(dict_pp)
691
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
693
def test_get_parents(self):
694
"""Requesting the same revision should be returned from cache"""
695
self.assertEqual({}, self.caching_pp._cache)
696
self.assertEqual([('b',)],
697
self.applyDeprecated(symbol_versioning.one_one,
698
self.caching_pp.get_parents, ['a']))
699
self.assertEqual(['a'], self.inst_pp.calls)
700
self.assertEqual([('b',)],
701
self.applyDeprecated(symbol_versioning.one_one,
702
self.caching_pp.get_parents, ['a']))
703
# No new call, as it should have been returned from the cache
704
self.assertEqual(['a'], self.inst_pp.calls)
705
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
707
def test_get_parent_map(self):
708
"""Requesting the same revision should be returned from cache"""
709
self.assertEqual({}, self.caching_pp._cache)
710
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
711
self.assertEqual(['a'], self.inst_pp.calls)
712
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
713
# No new call, as it should have been returned from the cache
714
self.assertEqual(['a'], self.inst_pp.calls)
715
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
717
def test_get_parent_map_not_present(self):
718
"""The cache should also track when a revision doesn't exist"""
719
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
720
self.assertEqual(['b'], self.inst_pp.calls)
721
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
723
self.assertEqual(['b'], self.inst_pp.calls)
724
self.assertEqual({'b':None}, self.caching_pp._cache)
726
def test_get_parent_map_mixed(self):
727
"""Anything that can be returned from cache, should be"""
728
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
729
self.assertEqual(['b'], self.inst_pp.calls)
730
self.assertEqual({'a':('b',)},
731
self.caching_pp.get_parent_map(['a', 'b']))
732
self.assertEqual(['b', 'a'], self.inst_pp.calls)
734
def test_get_parent_map_repeated(self):
735
"""Asking for the same parent 2x will only forward 1 request."""
736
self.assertEqual({'a':('b',)},
737
self.caching_pp.get_parent_map(['b', 'a', 'b']))
738
# Use sorted because we don't care about the order, just that each is
739
# only present 1 time.
740
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
added
removed
bzrlib/tests/test_graph.py
