← 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: Canonical.com Patch Queue Manager
  • Date: 2007-12-18 23:41:30 UTC
  • mfrom: (3099.3.7 graph_optimization)
  • Revision ID: pqm@pqm.ubuntu.com-20071218234130-061grgxsaf1g7bao
(jam) Implement ParentProviders.get_parent_map() and deprecate
        get_parents()

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,
20
22
    )
21
23
from bzrlib.revision import NULL_REVISION
22
24
from bzrlib.tests import TestCaseWithMemoryTransport
115
117
#     /  \      \
116
118
#  rev2a rev2b rev2c
117
119
#    |  /   \   /
118
 
#  rev3a    reveb
 
120
#  rev3a    rev3b
119
121
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
120
122
                    'rev2b': ['rev1'], 'rev2c': ['rev1'],
121
123
                    'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
122
124
 
 
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
 
123
227
#  NULL_REVISION
124
228
#       |
125
229
#       f
144
248
        self.calls.extend(nodes)
145
249
        return self._real_parents_provider.get_parents(nodes)
146
250
 
 
251
    def get_parent_map(self, nodes):
 
252
        self.calls.extend(nodes)
 
253
        return self._real_parents_provider.get_parent_map(nodes)
 
254
 
147
255
 
148
256
class TestGraph(TestCaseWithMemoryTransport):
149
257
 
150
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))
151
262
        tree = self.prepare_memory_tree('.')
152
263
        self.build_ancestry(tree, ancestors)
153
264
        self.addCleanup(tree.unlock)
261
372
        self.assertEqual(NULL_REVISION,
262
373
                         graph.find_unique_lca('rev4a', 'rev1b'))
263
374
 
 
375
    def test_lca_double_shortcut(self):
 
376
        graph = self.make_graph(double_shortcut)
 
377
        self.assertEqual('c', graph.find_unique_lca('f', 'g'))
 
378
 
264
379
    def test_common_ancestor_two_repos(self):
265
380
        """Ensure we do unique_lca using data from two repos"""
266
381
        mainline_tree = self.prepare_memory_tree('mainline')
289
404
        self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
290
405
                         graph.find_difference('rev4', 'rev2b'))
291
406
 
 
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']),
 
412
                          set(['rev1b'])),
 
413
                         graph.find_difference('rev4a', 'rev1b'))
 
414
 
292
415
    def test_graph_difference_criss_cross(self):
293
416
        graph = self.make_graph(criss_cross)
294
417
        self.assertEqual((set(['rev3a']), set(['rev3b'])),
296
419
        self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
297
420
                         graph.find_difference('rev2a', 'rev3b'))
298
421
 
299
 
    def test_stacked_parents_provider(self):
300
 
 
 
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'))
 
431
 
 
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'))
 
436
 
 
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'))
 
444
 
 
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'))
 
452
 
 
453
    def test_stacked_parents_provider_get_parents(self):
301
454
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
302
455
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
303
456
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
304
457
        self.assertEqual([['rev4',], ['rev3']],
305
 
                         stacked.get_parents(['rev1', 'rev2']))
 
458
             self.applyDeprecated(symbol_versioning.one_one,
 
459
                                  stacked.get_parents, ['rev1', 'rev2']))
306
460
        self.assertEqual([['rev3',], ['rev4']],
307
 
                         stacked.get_parents(['rev2', 'rev1']))
 
461
             self.applyDeprecated(symbol_versioning.one_one,
 
462
                                  stacked.get_parents, ['rev2', 'rev1']))
308
463
        self.assertEqual([['rev3',], ['rev3']],
309
 
                         stacked.get_parents(['rev2', 'rev2']))
 
464
             self.applyDeprecated(symbol_versioning.one_one,
 
465
                         stacked.get_parents, ['rev2', 'rev2']))
310
466
        self.assertEqual([['rev4',], ['rev4']],
311
 
                         stacked.get_parents(['rev1', 'rev1']))
 
467
             self.applyDeprecated(symbol_versioning.one_one,
 
468
                         stacked.get_parents, ['rev1', 'rev1']))
 
469
 
 
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']))
312
482
 
313
483
    def test_iter_topo_order(self):
314
484
        graph = self.make_graph(ancestry_1)
463
633
                    self.fail('key deeper was accessed')
464
634
                result.append(graph_dict[key])
465
635
            return result
 
636
        def get_parent_map(keys):
 
637
            result = {}
 
638
            for key in keys:
 
639
                if key == 'deeper':
 
640
                    self.fail('key deeper was accessed')
 
641
                result[key] = graph_dict[key]
 
642
            return result
466
643
        an_obj = stub()
467
644
        an_obj.get_parents = get_parents
 
645
        an_obj.get_parent_map = get_parent_map
468
646
        graph = _mod_graph.Graph(an_obj)
469
647
        return graph.heads(search)
470
648
 
502
680
        }
503
681
        self.assertEqual(set(['h1', 'h2']),
504
682
            self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
 
683
 
 
684
 
 
685
class TestCachingParentsProvider(tests.TestCase):
 
686
 
 
687
    def setUp(self):
 
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)
 
692
 
 
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)
 
706
 
 
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)
 
716
 
 
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']))
 
722
        # No new calls
 
723
        self.assertEqual(['b'], self.inst_pp.calls)
 
724
        self.assertEqual({'b':None}, self.caching_pp._cache)
 
725
 
 
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)
 
733
 
 
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))