← 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: Alexander Belchenko
  • Date: 2007-08-10 09:04:38 UTC
  • mto: This revision was merged to the branch mainline in revision 2694.
  • Revision ID: bialix@ukr.net-20070810090438-0835xdz0rl8825qv
fixes after Ian's review

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
17
17
from bzrlib import (
18
18
    errors,
19
19
    graph as _mod_graph,
20
 
    symbol_versioning,
21
 
    tests,
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
123
#  NULL_REVISION
228
124
#       |
229
125
#       f
238
134
            'f':[NULL_REVISION]}
239
135
 
240
136
 
241
 
# A graph that contains a ghost
242
 
#  NULL_REVISION
243
 
#       |
244
 
#       f
245
 
#       |
246
 
#       e   g
247
 
#      / \ /
248
 
#     b   d
249
 
#     | \ |
250
 
#     a   c
251
 
 
252
 
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
253
 
              'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
254
 
 
255
 
 
256
 
 
257
137
class InstrumentedParentsProvider(object):
258
138
 
259
139
    def __init__(self, parents_provider):
260
140
        self.calls = []
261
141
        self._real_parents_provider = parents_provider
262
142
 
263
 
    def get_parent_map(self, nodes):
 
143
    def get_parents(self, nodes):
264
144
        self.calls.extend(nodes)
265
 
        return self._real_parents_provider.get_parent_map(nodes)
 
145
        return self._real_parents_provider.get_parents(nodes)
 
146
 
 
147
 
 
148
class DictParentsProvider(object):
 
149
 
 
150
    def __init__(self, ancestry):
 
151
        self.ancestry = ancestry
 
152
 
 
153
    def __repr__(self):
 
154
        return 'DictParentsProvider(%r)' % self.ancestry
 
155
 
 
156
    def get_parents(self, revisions):
 
157
        return [self.ancestry.get(r, None) for r in revisions]
266
158
 
267
159
 
268
160
class TestGraph(TestCaseWithMemoryTransport):
269
161
 
270
162
    def make_graph(self, ancestors):
271
 
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
 
163
        tree = self.prepare_memory_tree('.')
 
164
        self.build_ancestry(tree, ancestors)
 
165
        tree.unlock()
 
166
        return tree.branch.repository.get_graph()
272
167
 
273
168
    def prepare_memory_tree(self, location):
274
169
        tree = self.make_branch_and_memory_tree(location)
353
248
                         graph.find_unique_lca(NULL_REVISION, 'rev1'))
354
249
        self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
355
250
        self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
356
 
        self.assertEqual(('rev1', 1,),
357
 
                         graph.find_unique_lca('rev2a', 'rev2b',
358
 
                         count_steps=True))
359
251
 
360
252
    def test_unique_lca_criss_cross(self):
361
253
        """Ensure we don't pick non-unique lcas in a criss-cross"""
362
254
        graph = self.make_graph(criss_cross)
363
255
        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)
367
256
 
368
257
    def test_unique_lca_null_revision(self):
369
258
        """Ensure we pick NULL_REVISION when necessary"""
378
267
        self.assertEqual(NULL_REVISION,
379
268
                         graph.find_unique_lca('rev4a', 'rev1b'))
380
269
 
381
 
    def test_lca_double_shortcut(self):
382
 
        graph = self.make_graph(double_shortcut)
383
 
        self.assertEqual('c', graph.find_unique_lca('f', 'g'))
384
 
 
385
270
    def test_common_ancestor_two_repos(self):
386
271
        """Ensure we do unique_lca using data from two repos"""
387
272
        mainline_tree = self.prepare_memory_tree('mainline')
388
273
        self.build_ancestry(mainline_tree, mainline)
389
 
        self.addCleanup(mainline_tree.unlock)
 
274
        mainline_tree.unlock()
390
275
 
391
276
        # This is cheating, because the revisions in the graph are actually
392
277
        # different revisions, despite having the same revision-id.
393
278
        feature_tree = self.prepare_memory_tree('feature')
394
279
        self.build_ancestry(feature_tree, feature_branch)
395
 
        self.addCleanup(feature_tree.unlock)
396
 
 
 
280
        feature_tree.unlock()
397
281
        graph = mainline_tree.branch.repository.get_graph(
398
282
            feature_tree.branch.repository)
399
283
        self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
410
294
        self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
411
295
                         graph.find_difference('rev4', 'rev2b'))
412
296
 
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']),
418
 
                          set(['rev1b'])),
419
 
                         graph.find_difference('rev4a', 'rev1b'))
420
 
 
421
297
    def test_graph_difference_criss_cross(self):
422
298
        graph = self.make_graph(criss_cross)
423
299
        self.assertEqual((set(['rev3a']), set(['rev3b'])),
425
301
        self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
426
302
                         graph.find_difference('rev2a', 'rev3b'))
427
303
 
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'))
437
 
 
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'))
442
 
 
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'))
450
 
 
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'))
458
 
 
459
304
    def test_stacked_parents_provider(self):
460
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
461
 
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
 
305
 
 
306
        parents1 = DictParentsProvider({'rev2': ['rev3']})
 
307
        parents2 = DictParentsProvider({'rev1': ['rev4']})
462
308
        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']))
 
309
        self.assertEqual([['rev4',], ['rev3']],
 
310
                         stacked.get_parents(['rev1', 'rev2']))
 
311
        self.assertEqual([['rev3',], ['rev4']],
 
312
                         stacked.get_parents(['rev2', 'rev1']))
 
313
        self.assertEqual([['rev3',], ['rev3']],
 
314
                         stacked.get_parents(['rev2', 'rev2']))
 
315
        self.assertEqual([['rev4',], ['rev4']],
 
316
                         stacked.get_parents(['rev1', 'rev1']))
471
317
 
472
318
    def test_iter_topo_order(self):
473
319
        graph = self.make_graph(ancestry_1)
505
351
        self.assertFalse(graph.is_ancestor('a', 'c'))
506
352
        self.assertTrue('null:' not in instrumented_provider.calls)
507
353
 
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
514
 
                          # other nodes are
515
 
        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
516
 
        self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
517
 
 
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
522
 
        expected['g'] = None
523
 
        self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
524
 
        expected.pop('a') 
525
 
        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
526
 
 
527
354
    def test_filter_candidate_lca(self):
528
355
        """Test filter_candidate_lca for a corner case
529
356
 
546
373
        #      c
547
374
        graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
548
375
                                 'a': [NULL_REVISION], 'e': [NULL_REVISION]})
549
 
        self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
550
 
 
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:')))
558
 
 
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']))
568
 
 
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']))
579
 
 
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']))
586
 
 
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']))
615
 
 
616
 
    def test_heads_shortcut(self):
617
 
        graph = self.make_graph(history_shortcut)
618
 
 
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']))
629
 
 
630
 
    def _run_heads_break_deeper(self, graph_dict, search):
631
 
        """Run heads on a graph-as-a-dict.
632
 
        
633
 
        If the search asks for the parents of 'deeper' the test will fail.
634
 
        """
635
 
        class stub(object):
636
 
            pass
637
 
        def get_parent_map(keys):
638
 
            result = {}
639
 
            for key in keys:
640
 
                if key == 'deeper':
641
 
                    self.fail('key deeper was accessed')
642
 
                result[key] = graph_dict[key]
643
 
            return result
644
 
        an_obj = stub()
645
 
        an_obj.get_parent_map = get_parent_map
646
 
        graph = _mod_graph.Graph(an_obj)
647
 
        return graph.heads(search)
648
 
 
649
 
    def test_heads_limits_search(self):
650
 
        # test that a heads query does not search all of history
651
 
        graph_dict = {
652
 
            'left':['common'],
653
 
            'right':['common'],
654
 
            'common':['deeper'],
655
 
        }
656
 
        self.assertEqual(set(['left', 'right']),
657
 
            self._run_heads_break_deeper(graph_dict, ['left', 'right']))
658
 
 
659
 
    def test_heads_limits_search_assymetric(self):
660
 
        # test that a heads query does not search all of history
661
 
        graph_dict = {
662
 
            'left':['midleft'],
663
 
            'midleft':['common'],
664
 
            'right':['common'],
665
 
            'common':['aftercommon'],
666
 
            'aftercommon':['deeper'],
667
 
        }
668
 
        self.assertEqual(set(['left', 'right']),
669
 
            self._run_heads_break_deeper(graph_dict, ['left', 'right']))
670
 
 
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:
674
 
        graph_dict = {
675
 
            'h1':['shortcut', 'common1'],
676
 
            'h2':['common1'],
677
 
            'shortcut':['common2'],
678
 
            'common1':['common2'],
679
 
            'common2':['deeper'],
680
 
        }
681
 
        self.assertEqual(set(['h1', 'h2']),
682
 
            self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
683
 
 
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)
690
 
        # next includes them
691
 
        search = graph._make_breadth_first_searcher(['a-ghost'])
692
 
        self.assertEqual(set(['a-ghost']), search.next())
693
 
        self.assertRaises(StopIteration, search.next)
694
 
 
695
 
    def test_breadth_first_search_deep_ghosts(self):
696
 
        graph = self.make_graph({
697
 
            'head':['present'],
698
 
            'present':['child', 'ghost'],
699
 
            'child':[],
700
 
            })
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)
708
 
        # next includes them
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']),
713
 
            search.next())
714
 
        self.assertRaises(StopIteration, search.next)
715
 
 
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({
720
 
            'head':['present'],
721
 
            'present':['child', 'ghost'],
722
 
            'child':[],
723
 
            })
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)
731
 
        # start with 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']),
736
 
            search.next())
737
 
        self.assertRaises(StopIteration, search.next_with_ghosts)
738
 
 
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({
742
 
            'head':['present'],
743
 
            'present':['stopped'],
744
 
            'other':['other_2'],
745
 
            'other_2':[],
746
 
            })
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)
756
 
        # next includes them
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)
765
 
 
766
 
    def assertSeenAndResult(self, instructions, search, next):
767
 
        """Check the results of .seen and get_result() for a seach.
768
 
 
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.
777
 
        """
778
 
        for seen, recipe, included_keys, starts, stops in instructions:
779
 
            next()
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)
788
 
 
789
 
    def test_breadth_first_get_result_excludes_current_pending(self):
790
 
        graph = self.make_graph({
791
 
            'head':['child'],
792
 
            'child':[NULL_REVISION],
793
 
            NULL_REVISION:[],
794
 
            })
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),
799
 
            result.get_recipe())
800
 
        self.assertEqual(set(), result.get_keys())
801
 
        self.assertEqual(set(), search.seen)
802
 
        # using next:
803
 
        expected = [
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),
810
 
            ]
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)
815
 
 
816
 
    def test_breadth_first_get_result_starts_stops(self):
817
 
        graph = self.make_graph({
818
 
            'head':['child'],
819
 
            'child':[NULL_REVISION],
820
 
            'otherhead':['otherchild'],
821
 
            'otherchild':['excluded'],
822
 
            'excluded':[NULL_REVISION],
823
 
            NULL_REVISION:[]
824
 
            })
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),
831
 
            result.get_recipe())
832
 
        self.assertEqual(set(['head']), result.get_keys())
833
 
        self.assertEqual(set(['head']), search.seen)
834
 
        # using next:
835
 
        expected = [
836
 
            # stop at child, and start a new search at otherhead:
837
 
            # - otherhead counts as seen immediately when start_searching is
838
 
            # called.
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']),
849
 
            ]
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)
855
 
 
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],
862
 
            NULL_REVISION:[],
863
 
            })
864
 
        search = graph._make_breadth_first_searcher(['head'])
865
 
        expected = [
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
870
 
            # next iteration.
871
 
            (set(['head', 'child', 'ghost1']),
872
 
             (set(['head']), set(['ghost1', NULL_REVISION]), 2),
873
 
             ['head', 'child'], None, [NULL_REVISION, 'ghost1']),
874
 
            ]
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)
879
 
 
880
 
    def test_breadth_first_get_result_ghosts_are_excluded(self):
881
 
        graph = self.make_graph({
882
 
            'head':['child', 'ghost'],
883
 
            'child':[NULL_REVISION],
884
 
            NULL_REVISION:[],
885
 
            })
886
 
        search = graph._make_breadth_first_searcher(['head'])
887
 
        # using next:
888
 
        expected = [
889
 
            (set(['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),
895
 
            ]
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)
900
 
 
901
 
    def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
902
 
        graph = self.make_graph({
903
 
            'head':['child'],
904
 
            'child':[NULL_REVISION],
905
 
            NULL_REVISION:[],
906
 
            })
907
 
        search = graph._make_breadth_first_searcher(['head'])
908
 
        # using next:
909
 
        expected = [
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),
916
 
            ]
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)
921
 
 
922
 
    def test_breadth_first_revision_count_includes_NULL_REVISION(self):
923
 
        graph = self.make_graph({
924
 
            'head':[NULL_REVISION],
925
 
            NULL_REVISION:[],
926
 
            })
927
 
        search = graph._make_breadth_first_searcher(['head'])
928
 
        # using next:
929
 
        expected = [
930
 
            (set(['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),
936
 
            ]
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)
941
 
 
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],
946
 
            NULL_REVISION:[],
947
 
            })
948
 
        search = graph._make_breadth_first_searcher(['head'])
949
 
        # using next:
950
 
        expected = [
951
 
            (set(['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),
957
 
            ]
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),
963
 
            result.get_recipe())
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),
972
 
            result.get_recipe())
973
 
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
974
 
 
975
 
 
976
 
class TestCachingParentsProvider(tests.TestCase):
977
 
 
978
 
    def setUp(self):
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)
983
 
 
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)
993
 
 
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']))
999
 
        # No new calls
1000
 
        self.assertEqual(['b'], self.inst_pp.calls)
1001
 
        self.assertEqual({'b':None}, self.caching_pp._cache)
1002
 
 
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)
1010
 
 
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))
 
376
        self.assertEqual(['c'], graph._filter_candidate_lca(['a', 'c', 'e']))