← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

  • Committer: Aaron Bentley
  • Date: 2007-07-11 19:44:51 UTC
  • mto: This revision was merged to the branch mainline in revision 2606.
  • Revision ID: abentley@panoramicfeedback.com-20070711194451-3jqhye1nnd02a9uv
Restore original Branch.last_revision behavior, fix bits that care

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
16
16
 
17
17
from bzrlib import (
18
18
    errors,
19
 
    graph as _mod_graph,
20
 
    symbol_versioning,
21
 
    tests,
 
19
    graph,
22
20
    )
23
21
from bzrlib.revision import NULL_REVISION
24
22
from bzrlib.tests import TestCaseWithMemoryTransport
117
115
#     /  \      \
118
116
#  rev2a rev2b rev2c
119
117
#    |  /   \   /
120
 
#  rev3a    rev3b
 
118
#  rev3a    reveb
121
119
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
122
120
                    'rev2b': ['rev1'], 'rev2c': ['rev1'],
123
121
                    'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
124
122
 
125
 
# Extended history shortcut
126
 
#  NULL_REVISION
127
 
#       |
128
 
#       a
129
 
#       |\
130
 
#       b |
131
 
#       | |
132
 
#       c |
133
 
#       | |
134
 
#       d |
135
 
#       |\|
136
 
#       e f
137
 
extended_history_shortcut = {'a': [NULL_REVISION],
138
 
                             'b': ['a'],
139
 
                             'c': ['b'],
140
 
                             'd': ['c'],
141
 
                             'e': ['d'],
142
 
                             'f': ['a', 'd'],
143
 
                            }
144
 
 
145
 
# Double shortcut
146
 
# Both sides will see 'A' first, even though it is actually a decendent of a
147
 
# different common revision.
148
 
#
149
 
#  NULL_REVISION
150
 
#       |
151
 
#       a
152
 
#      /|\
153
 
#     / b \
154
 
#    /  |  \
155
 
#   |   c   |
156
 
#   |  / \  |
157
 
#   | d   e |
158
 
#   |/     \|
159
 
#   f       g
160
 
 
161
 
double_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
162
 
                   'd':['c'], 'e':['c'], 'f':['a', 'd'],
163
 
                   'g':['a', 'e']}
164
 
 
165
 
# Complex shortcut
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.
171
 
#
172
 
# NULL_REVISION
173
 
#     |
174
 
#     a
175
 
#     |
176
 
#     b
177
 
#     |
178
 
#     c
179
 
#     |
180
 
#     d
181
 
#     |\
182
 
#     e f
183
 
#     | |\
184
 
#     i | h
185
 
#     |\| |
186
 
#     | g |
187
 
#     | | |
188
 
#     | j |
189
 
#     | | |
190
 
#     | k |
191
 
#     | | |
192
 
#     | l |
193
 
#     |/|/
194
 
#     m n
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'],
202
 
                    }
203
 
 
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
207
 
#  NULL_REVISION
208
 
#       |   |
209
 
#       a   |
210
 
#       |\  |
211
 
#       b | |
212
 
#       | | |
213
 
#       c | |
214
 
#       | | |
215
 
#       d | g
216
 
#       |\|/
217
 
#       e f
218
 
shortcut_extra_root = {'a': [NULL_REVISION],
219
 
                       'b': ['a'],
220
 
                       'c': ['b'],
221
 
                       'd': ['c'],
222
 
                       'e': ['d'],
223
 
                       'f': ['a', 'd', 'g'],
224
 
                       'g': [NULL_REVISION],
225
 
                      }
226
 
 
227
 
#  NULL_REVISION
228
 
#       |
229
 
#       f
230
 
#       |
231
 
#       e
232
 
#      / \
233
 
#     b   d
234
 
#     | \ |
235
 
#     a   c
236
 
 
237
 
boundary = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e'], 'e': ['f'],
238
 
            'f':[NULL_REVISION]}
239
 
 
240
 
 
241
 
class InstrumentedParentsProvider(object):
242
 
 
243
 
    def __init__(self, parents_provider):
244
 
        self.calls = []
245
 
        self._real_parents_provider = parents_provider
246
 
 
247
 
    def get_parent_map(self, nodes):
248
 
        self.calls.extend(nodes)
249
 
        return self._real_parents_provider.get_parent_map(nodes)
250
 
 
251
123
 
252
124
class TestGraph(TestCaseWithMemoryTransport):
253
125
 
254
126
    def make_graph(self, ancestors):
255
 
        # XXX: This seems valid, is there a reason to actually create a
256
 
        # repository and put things in it?
257
 
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
258
127
        tree = self.prepare_memory_tree('.')
259
128
        self.build_ancestry(tree, ancestors)
260
 
        self.addCleanup(tree.unlock)
 
129
        tree.unlock()
261
130
        return tree.branch.repository.get_graph()
262
131
 
263
132
    def prepare_memory_tree(self, location):
312
181
        self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
313
182
        self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
314
183
 
315
 
    def test_no_unique_lca(self):
316
 
        """Test error when one revision is not in the graph"""
317
 
        graph = self.make_graph(ancestry_1)
318
 
        self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
319
 
                          'rev1', '1rev')
320
 
 
321
184
    def test_lca_criss_cross(self):
322
185
        """Test least-common-ancestor after a criss-cross merge."""
323
186
        graph = self.make_graph(criss_cross)
343
206
                         graph.find_unique_lca(NULL_REVISION, 'rev1'))
344
207
        self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
345
208
        self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
346
 
        self.assertEqual(('rev1', 1,),
347
 
                         graph.find_unique_lca('rev2a', 'rev2b',
348
 
                         count_steps=True))
349
209
 
350
210
    def test_unique_lca_criss_cross(self):
351
211
        """Ensure we don't pick non-unique lcas in a criss-cross"""
352
212
        graph = self.make_graph(criss_cross)
353
213
        self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
354
 
        lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
355
 
        self.assertEqual('rev1', lca)
356
 
        self.assertEqual(2, steps)
357
214
 
358
215
    def test_unique_lca_null_revision(self):
359
216
        """Ensure we pick NULL_REVISION when necessary"""
368
225
        self.assertEqual(NULL_REVISION,
369
226
                         graph.find_unique_lca('rev4a', 'rev1b'))
370
227
 
371
 
    def test_lca_double_shortcut(self):
372
 
        graph = self.make_graph(double_shortcut)
373
 
        self.assertEqual('c', graph.find_unique_lca('f', 'g'))
374
 
 
375
228
    def test_common_ancestor_two_repos(self):
376
229
        """Ensure we do unique_lca using data from two repos"""
377
230
        mainline_tree = self.prepare_memory_tree('mainline')
378
231
        self.build_ancestry(mainline_tree, mainline)
379
 
        self.addCleanup(mainline_tree.unlock)
 
232
        mainline_tree.unlock()
380
233
 
381
234
        # This is cheating, because the revisions in the graph are actually
382
235
        # different revisions, despite having the same revision-id.
383
236
        feature_tree = self.prepare_memory_tree('feature')
384
237
        self.build_ancestry(feature_tree, feature_branch)
385
 
        self.addCleanup(feature_tree.unlock)
386
 
 
 
238
        feature_tree.unlock()
387
239
        graph = mainline_tree.branch.repository.get_graph(
388
240
            feature_tree.branch.repository)
389
241
        self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
400
252
        self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
401
253
                         graph.find_difference('rev4', 'rev2b'))
402
254
 
403
 
    def test_graph_difference_separate_ancestry(self):
404
 
        graph = self.make_graph(ancestry_2)
405
 
        self.assertEqual((set(['rev1a']), set(['rev1b'])),
406
 
                         graph.find_difference('rev1a', 'rev1b'))
407
 
        self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
408
 
                          set(['rev1b'])),
409
 
                         graph.find_difference('rev4a', 'rev1b'))
410
 
 
411
255
    def test_graph_difference_criss_cross(self):
412
256
        graph = self.make_graph(criss_cross)
413
257
        self.assertEqual((set(['rev3a']), set(['rev3b'])),
415
259
        self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
416
260
                         graph.find_difference('rev2a', 'rev3b'))
417
261
 
418
 
    def test_graph_difference_extended_history(self):
419
 
        graph = self.make_graph(extended_history_shortcut)
420
 
        self.expectFailure('find_difference cannot handle shortcuts',
421
 
            self.assertEqual, (set(['e']), set(['f'])),
422
 
                graph.find_difference('e', 'f'))
423
 
        self.assertEqual((set(['e']), set(['f'])),
424
 
                         graph.find_difference('e', 'f'))
425
 
        self.assertEqual((set(['f']), set(['e'])),
426
 
                         graph.find_difference('f', 'e'))
427
 
 
428
 
    def test_graph_difference_double_shortcut(self):
429
 
        graph = self.make_graph(double_shortcut)
430
 
        self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
431
 
                         graph.find_difference('f', 'g'))
432
 
 
433
 
    def test_graph_difference_complex_shortcut(self):
434
 
        graph = self.make_graph(complex_shortcut)
435
 
        self.expectFailure('find_difference cannot handle shortcuts',
436
 
            self.assertEqual, (set(['m']), set(['h', 'n'])),
437
 
                graph.find_difference('m', 'n'))
438
 
        self.assertEqual((set(['m']), set(['h', 'n'])),
439
 
                         graph.find_difference('m', 'n'))
440
 
 
441
 
    def test_graph_difference_shortcut_extra_root(self):
442
 
        graph = self.make_graph(shortcut_extra_root)
443
 
        self.expectFailure('find_difference cannot handle shortcuts',
444
 
            self.assertEqual, (set(['e']), set(['f', 'g'])),
445
 
                graph.find_difference('e', 'f'))
446
 
        self.assertEqual((set(['e']), set(['f', 'g'])),
447
 
                         graph.find_difference('e', 'f'))
448
 
 
449
262
    def test_stacked_parents_provider(self):
450
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
451
 
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
452
 
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
453
 
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
454
 
                         stacked.get_parent_map(['rev1', 'rev2']))
455
 
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
456
 
                         stacked.get_parent_map(['rev2', 'rev1']))
457
 
        self.assertEqual({'rev2':['rev3']},
458
 
                         stacked.get_parent_map(['rev2', 'rev2']))
459
 
        self.assertEqual({'rev1':['rev4']},
460
 
                         stacked.get_parent_map(['rev1', 'rev1']))
 
263
 
 
264
        class ParentsProvider(object):
 
265
 
 
266
            def __init__(self, ancestry):
 
267
                self.ancestry = ancestry
 
268
 
 
269
            def get_parents(self, revisions):
 
270
                return [self.ancestry.get(r, None) for r in revisions]
 
271
 
 
272
        parents1 = ParentsProvider({'rev2': ['rev3']})
 
273
        parents2 = ParentsProvider({'rev1': ['rev4']})
 
274
        stacked = graph._StackedParentsProvider([parents1, parents2])
 
275
        self.assertEqual([['rev4',], ['rev3']],
 
276
                         stacked.get_parents(['rev1', 'rev2']))
 
277
        self.assertEqual([['rev3',], ['rev4']],
 
278
                         stacked.get_parents(['rev2', 'rev1']))
 
279
        self.assertEqual([['rev3',], ['rev3']],
 
280
                         stacked.get_parents(['rev2', 'rev2']))
 
281
        self.assertEqual([['rev4',], ['rev4']],
 
282
                         stacked.get_parents(['rev1', 'rev1']))
461
283
 
462
284
    def test_iter_topo_order(self):
463
285
        graph = self.make_graph(ancestry_1)
466
288
        self.assertEqual(set(args), set(topo_args))
467
289
        self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
468
290
        self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
469
 
 
470
 
    def test_is_ancestor(self):
471
 
        graph = self.make_graph(ancestry_1)
472
 
        self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
473
 
        self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
474
 
        self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
475
 
        self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
476
 
        self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
477
 
        self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
478
 
        self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
479
 
        self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
480
 
        self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
481
 
        instrumented_provider = InstrumentedParentsProvider(graph)
482
 
        instrumented_graph = _mod_graph.Graph(instrumented_provider)
483
 
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
484
 
        self.assertTrue('null:' not in instrumented_provider.calls)
485
 
 
486
 
    def test_is_ancestor_boundary(self):
487
 
        """Ensure that we avoid searching the whole graph.
488
 
        
489
 
        This requires searching through b as a common ancestor, so we
490
 
        can identify that e is common.
491
 
        """
492
 
        graph = self.make_graph(boundary)
493
 
        instrumented_provider = InstrumentedParentsProvider(graph)
494
 
        graph = _mod_graph.Graph(instrumented_provider)
495
 
        self.assertFalse(graph.is_ancestor('a', 'c'))
496
 
        self.assertTrue('null:' not in instrumented_provider.calls)
497
 
 
498
 
    def test_filter_candidate_lca(self):
499
 
        """Test filter_candidate_lca for a corner case
500
 
 
501
 
        This tests the case where we encounter the end of iteration for 'e'
502
 
        in the same pass as we discover that 'd' is an ancestor of 'e', and
503
 
        therefore 'e' can't be an lca.
504
 
 
505
 
        To compensate for different dict orderings on other Python
506
 
        implementations, we mirror 'd' and 'e' with 'b' and 'a'.
507
 
        """
508
 
        # This test is sensitive to the iteration order of dicts.  It will
509
 
        # pass incorrectly if 'e' and 'a' sort before 'c'
510
 
        #
511
 
        # NULL_REVISION
512
 
        #     / \
513
 
        #    a   e
514
 
        #    |   |
515
 
        #    b   d
516
 
        #     \ /
517
 
        #      c
518
 
        graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
519
 
                                 'a': [NULL_REVISION], 'e': [NULL_REVISION]})
520
 
        self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
521
 
 
522
 
    def test_heads_null(self):
523
 
        graph = self.make_graph(ancestry_1)
524
 
        self.assertEqual(set(['null:']), graph.heads(['null:']))
525
 
        self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
526
 
        self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
527
 
        self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
528
 
        self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
529
 
 
530
 
    def test_heads_one(self):
531
 
        # A single node will always be a head
532
 
        graph = self.make_graph(ancestry_1)
533
 
        self.assertEqual(set(['null:']), graph.heads(['null:']))
534
 
        self.assertEqual(set(['rev1']), graph.heads(['rev1']))
535
 
        self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
536
 
        self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
537
 
        self.assertEqual(set(['rev3']), graph.heads(['rev3']))
538
 
        self.assertEqual(set(['rev4']), graph.heads(['rev4']))
539
 
 
540
 
    def test_heads_single(self):
541
 
        graph = self.make_graph(ancestry_1)
542
 
        self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
543
 
        self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
544
 
        self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
545
 
        self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
546
 
        self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
547
 
        self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
548
 
        self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
549
 
        self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
550
 
 
551
 
    def test_heads_two_heads(self):
552
 
        graph = self.make_graph(ancestry_1)
553
 
        self.assertEqual(set(['rev2a', 'rev2b']),
554
 
                         graph.heads(['rev2a', 'rev2b']))
555
 
        self.assertEqual(set(['rev3', 'rev2b']),
556
 
                         graph.heads(['rev3', 'rev2b']))
557
 
 
558
 
    def test_heads_criss_cross(self):
559
 
        graph = self.make_graph(criss_cross)
560
 
        self.assertEqual(set(['rev2a']),
561
 
                         graph.heads(['rev2a', 'rev1']))
562
 
        self.assertEqual(set(['rev2b']),
563
 
                         graph.heads(['rev2b', 'rev1']))
564
 
        self.assertEqual(set(['rev3a']),
565
 
                         graph.heads(['rev3a', 'rev1']))
566
 
        self.assertEqual(set(['rev3b']),
567
 
                         graph.heads(['rev3b', 'rev1']))
568
 
        self.assertEqual(set(['rev2a', 'rev2b']),
569
 
                         graph.heads(['rev2a', 'rev2b']))
570
 
        self.assertEqual(set(['rev3a']),
571
 
                         graph.heads(['rev3a', 'rev2a']))
572
 
        self.assertEqual(set(['rev3a']),
573
 
                         graph.heads(['rev3a', 'rev2b']))
574
 
        self.assertEqual(set(['rev3a']),
575
 
                         graph.heads(['rev3a', 'rev2a', 'rev2b']))
576
 
        self.assertEqual(set(['rev3b']),
577
 
                         graph.heads(['rev3b', 'rev2a']))
578
 
        self.assertEqual(set(['rev3b']),
579
 
                         graph.heads(['rev3b', 'rev2b']))
580
 
        self.assertEqual(set(['rev3b']),
581
 
                         graph.heads(['rev3b', 'rev2a', 'rev2b']))
582
 
        self.assertEqual(set(['rev3a', 'rev3b']),
583
 
                         graph.heads(['rev3a', 'rev3b']))
584
 
        self.assertEqual(set(['rev3a', 'rev3b']),
585
 
                         graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
586
 
 
587
 
    def test_heads_shortcut(self):
588
 
        graph = self.make_graph(history_shortcut)
589
 
 
590
 
        self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
591
 
                         graph.heads(['rev2a', 'rev2b', 'rev2c']))
592
 
        self.assertEqual(set(['rev3a', 'rev3b']),
593
 
                         graph.heads(['rev3a', 'rev3b']))
594
 
        self.assertEqual(set(['rev3a', 'rev3b']),
595
 
                         graph.heads(['rev2a', 'rev3a', 'rev3b']))
596
 
        self.assertEqual(set(['rev2a', 'rev3b']),
597
 
                         graph.heads(['rev2a', 'rev3b']))
598
 
        self.assertEqual(set(['rev2c', 'rev3a']),
599
 
                         graph.heads(['rev2c', 'rev3a']))
600
 
 
601
 
    def _run_heads_break_deeper(self, graph_dict, search):
602
 
        """Run heads on a graph-as-a-dict.
603
 
        
604
 
        If the search asks for the parents of 'deeper' the test will fail.
605
 
        """
606
 
        class stub(object):
607
 
            pass
608
 
        def get_parent_map(keys):
609
 
            result = {}
610
 
            for key in keys:
611
 
                if key == 'deeper':
612
 
                    self.fail('key deeper was accessed')
613
 
                result[key] = graph_dict[key]
614
 
            return result
615
 
        an_obj = stub()
616
 
        an_obj.get_parent_map = get_parent_map
617
 
        graph = _mod_graph.Graph(an_obj)
618
 
        return graph.heads(search)
619
 
 
620
 
    def test_heads_limits_search(self):
621
 
        # test that a heads query does not search all of history
622
 
        graph_dict = {
623
 
            'left':['common'],
624
 
            'right':['common'],
625
 
            'common':['deeper'],
626
 
        }
627
 
        self.assertEqual(set(['left', 'right']),
628
 
            self._run_heads_break_deeper(graph_dict, ['left', 'right']))
629
 
 
630
 
    def test_heads_limits_search_assymetric(self):
631
 
        # test that a heads query does not search all of history
632
 
        graph_dict = {
633
 
            'left':['midleft'],
634
 
            'midleft':['common'],
635
 
            'right':['common'],
636
 
            'common':['aftercommon'],
637
 
            'aftercommon':['deeper'],
638
 
        }
639
 
        self.assertEqual(set(['left', 'right']),
640
 
            self._run_heads_break_deeper(graph_dict, ['left', 'right']))
641
 
 
642
 
    def test_heads_limits_search_common_search_must_continue(self):
643
 
        # test that common nodes are still queried, preventing
644
 
        # all-the-way-to-origin behaviour in the following graph:
645
 
        graph_dict = {
646
 
            'h1':['shortcut', 'common1'],
647
 
            'h2':['common1'],
648
 
            'shortcut':['common2'],
649
 
            'common1':['common2'],
650
 
            'common2':['deeper'],
651
 
        }
652
 
        self.assertEqual(set(['h1', 'h2']),
653
 
            self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
654
 
 
655
 
 
656
 
class TestCachingParentsProvider(tests.TestCase):
657
 
 
658
 
    def setUp(self):
659
 
        super(TestCachingParentsProvider, self).setUp()
660
 
        dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
661
 
        self.inst_pp = InstrumentedParentsProvider(dict_pp)
662
 
        self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
663
 
 
664
 
    def test_get_parent_map(self):
665
 
        """Requesting the same revision should be returned from cache"""
666
 
        self.assertEqual({}, self.caching_pp._cache)
667
 
        self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
668
 
        self.assertEqual(['a'], self.inst_pp.calls)
669
 
        self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
670
 
        # No new call, as it should have been returned from the cache
671
 
        self.assertEqual(['a'], self.inst_pp.calls)
672
 
        self.assertEqual({'a':('b',)}, self.caching_pp._cache)
673
 
 
674
 
    def test_get_parent_map_not_present(self):
675
 
        """The cache should also track when a revision doesn't exist"""
676
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
677
 
        self.assertEqual(['b'], self.inst_pp.calls)
678
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
679
 
        # No new calls
680
 
        self.assertEqual(['b'], self.inst_pp.calls)
681
 
        self.assertEqual({'b':None}, self.caching_pp._cache)
682
 
 
683
 
    def test_get_parent_map_mixed(self):
684
 
        """Anything that can be returned from cache, should be"""
685
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
686
 
        self.assertEqual(['b'], self.inst_pp.calls)
687
 
        self.assertEqual({'a':('b',)},
688
 
                         self.caching_pp.get_parent_map(['a', 'b']))
689
 
        self.assertEqual(['b', 'a'], self.inst_pp.calls)
690
 
 
691
 
    def test_get_parent_map_repeated(self):
692
 
        """Asking for the same parent 2x will only forward 1 request."""
693
 
        self.assertEqual({'a':('b',)},
694
 
                         self.caching_pp.get_parent_map(['b', 'a', 'b']))
695
 
        # Use sorted because we don't care about the order, just that each is
696
 
        # only present 1 time.
697
 
        self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))