← 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: John Arbash Meinel
  • Date: 2007-12-18 17:06:42 UTC
  • mto: This revision was merged to the branch mainline in revision 3126.
  • Revision ID: john@arbash-meinel.com-20071218170642-nls9ory76cmh4r6y
Implement get_parent_map for ParentProviders
Add a CachingParentProvider for PackRepository to use.
Add some XFAIL tests for the find_difference algorithm.

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
    tests,
20
21
    )
21
22
from bzrlib.revision import NULL_REVISION
22
23
from bzrlib.tests import TestCaseWithMemoryTransport
115
116
#     /  \      \
116
117
#  rev2a rev2b rev2c
117
118
#    |  /   \   /
118
 
#  rev3a    reveb
 
119
#  rev3a    rev3b
119
120
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
120
121
                    'rev2b': ['rev1'], 'rev2c': ['rev1'],
121
122
                    'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
122
123
 
 
124
# Extended history shortcut
 
125
#  NULL_REVISION
 
126
#       |
 
127
#       a
 
128
#       |\
 
129
#       b |
 
130
#       | |
 
131
#       c |
 
132
#       | |
 
133
#       d |
 
134
#       |\|
 
135
#       e f
 
136
extended_history_shortcut = {'a': [NULL_REVISION],
 
137
                             'b': ['a'],
 
138
                             'c': ['b'],
 
139
                             'd': ['c'],
 
140
                             'e': ['d'],
 
141
                             'f': ['a', 'd'],
 
142
                            }
 
143
 
 
144
# Double shortcut
 
145
# Both sides will see 'A' first, even though it is actually a decendent of a
 
146
# different common revision.
 
147
#
 
148
#  NULL_REVISION
 
149
#       |
 
150
#       a
 
151
#      /|\
 
152
#     / b \
 
153
#    /  |  \
 
154
#   |   c   |
 
155
#   |  / \  |
 
156
#   | d   e |
 
157
#   |/     \|
 
158
#   f       g
 
159
 
 
160
double_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
 
161
                   'd':['c'], 'e':['c'], 'f':['a', 'd'],
 
162
                   'g':['a', 'e']}
 
163
 
 
164
# Complex shortcut
 
165
# This has a failure mode in that a shortcut will find some nodes in common,
 
166
# but the common searcher won't have time to find that one branch is actually
 
167
# in common. The extra nodes at the top are because we want to avoid
 
168
# walking off the graph. Specifically, node G should be considered common, but
 
169
# is likely to be seen by M long before the common searcher finds it.
 
170
#
 
171
# NULL_REVISION
 
172
#     |
 
173
#     a
 
174
#     |
 
175
#     b
 
176
#     |
 
177
#     c
 
178
#     |
 
179
#     d
 
180
#     |\
 
181
#     e f
 
182
#     | |\
 
183
#     i | h
 
184
#     |\| |
 
185
#     | g |
 
186
#     | | |
 
187
#     | j |
 
188
#     | | |
 
189
#     | k |
 
190
#     | | |
 
191
#     | l |
 
192
#     |/|/
 
193
#     m n
 
194
complex_shortcut = {'d':[NULL_REVISION],
 
195
                    'x':['d'], 'y':['x'],
 
196
                    'e':['y'], 'f':['d'], 'g':['f', 'i'], 'h':['f'],
 
197
                    'i':['e'], 'j':['g'], 'k':['j'],
 
198
                    'l':['k'], 'm':['i', 's'], 'n':['s', 'h'],
 
199
                    'o':['l'], 'p':['o'], 'q':['p'],
 
200
                    'r':['q'], 's':['r'],
 
201
                    }
 
202
 
 
203
# Shortcut with extra root
 
204
# We have a long history shortcut, and an extra root, which is why we can't
 
205
# stop searchers based on seeing NULL_REVISION
 
206
#  NULL_REVISION
 
207
#       |   |
 
208
#       a   |
 
209
#       |\  |
 
210
#       b | |
 
211
#       | | |
 
212
#       c | |
 
213
#       | | |
 
214
#       d | g
 
215
#       |\|/
 
216
#       e f
 
217
shortcut_extra_root = {'a': [NULL_REVISION],
 
218
                       'b': ['a'],
 
219
                       'c': ['b'],
 
220
                       'd': ['c'],
 
221
                       'e': ['d'],
 
222
                       'f': ['a', 'd', 'g'],
 
223
                       'g': [NULL_REVISION],
 
224
                      }
 
225
 
123
226
#  NULL_REVISION
124
227
#       |
125
228
#       f
144
247
        self.calls.extend(nodes)
145
248
        return self._real_parents_provider.get_parents(nodes)
146
249
 
 
250
    def get_parent_map(self, nodes):
 
251
        self.calls.extend(nodes)
 
252
        return self._real_parents_provider.get_parent_map(nodes)
 
253
 
147
254
 
148
255
class TestGraph(TestCaseWithMemoryTransport):
149
256
 
150
257
    def make_graph(self, ancestors):
 
258
        # XXX: This seems valid, is there a reason to actually create a
 
259
        # repository and put things in it?
 
260
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
151
261
        tree = self.prepare_memory_tree('.')
152
262
        self.build_ancestry(tree, ancestors)
153
263
        self.addCleanup(tree.unlock)
261
371
        self.assertEqual(NULL_REVISION,
262
372
                         graph.find_unique_lca('rev4a', 'rev1b'))
263
373
 
 
374
    def test_lca_double_shortcut(self):
 
375
        graph = self.make_graph(double_shortcut)
 
376
        self.assertEqual('c', graph.find_unique_lca('f', 'g'))
 
377
 
264
378
    def test_common_ancestor_two_repos(self):
265
379
        """Ensure we do unique_lca using data from two repos"""
266
380
        mainline_tree = self.prepare_memory_tree('mainline')
289
403
        self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
290
404
                         graph.find_difference('rev4', 'rev2b'))
291
405
 
 
406
    def test_graph_difference_separate_ancestry(self):
 
407
        graph = self.make_graph(ancestry_2)
 
408
        self.assertEqual((set(['rev1a']), set(['rev1b'])),
 
409
                         graph.find_difference('rev1a', 'rev1b'))
 
410
        self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
 
411
                          set(['rev1b'])),
 
412
                         graph.find_difference('rev4a', 'rev1b'))
 
413
 
292
414
    def test_graph_difference_criss_cross(self):
293
415
        graph = self.make_graph(criss_cross)
294
416
        self.assertEqual((set(['rev3a']), set(['rev3b'])),
296
418
        self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
297
419
                         graph.find_difference('rev2a', 'rev3b'))
298
420
 
 
421
    def test_graph_difference_extended_history(self):
 
422
        graph = self.make_graph(extended_history_shortcut)
 
423
        self.expectFailure('find_difference cannot handle shortcuts',
 
424
            self.assertEqual, (set(['e']), set(['f'])),
 
425
                graph.find_difference('e', 'f'))
 
426
        self.assertEqual((set(['e']), set(['f'])),
 
427
                         graph.find_difference('e', 'f'))
 
428
        self.assertEqual((set(['f']), set(['e'])),
 
429
                         graph.find_difference('f', 'e'))
 
430
 
 
431
    def test_graph_difference_double_shortcut(self):
 
432
        graph = self.make_graph(double_shortcut)
 
433
        self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
 
434
                         graph.find_difference('f', 'g'))
 
435
 
 
436
    def test_graph_difference_complex_shortcut(self):
 
437
        graph = self.make_graph(complex_shortcut)
 
438
        self.expectFailure('find_difference cannot handle shortcuts',
 
439
            self.assertEqual, (set(['m']), set(['h', 'n'])),
 
440
                graph.find_difference('m', 'n'))
 
441
        self.assertEqual((set(['m']), set(['h', 'n'])),
 
442
                         graph.find_difference('m', 'n'))
 
443
 
 
444
    def test_graph_difference_shortcut_extra_root(self):
 
445
        graph = self.make_graph(shortcut_extra_root)
 
446
        self.expectFailure('find_difference cannot handle shortcuts',
 
447
            self.assertEqual, (set(['e']), set(['f', 'g'])),
 
448
                graph.find_difference('e', 'f'))
 
449
        self.assertEqual((set(['e']), set(['f', 'g'])),
 
450
                         graph.find_difference('e', 'f'))
 
451
 
299
452
    def test_stacked_parents_provider(self):
300
453
 
301
454
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
463
616
                    self.fail('key deeper was accessed')
464
617
                result.append(graph_dict[key])
465
618
            return result
 
619
        def get_parent_map(keys):
 
620
            result = {}
 
621
            for key in keys:
 
622
                if key == 'deeper':
 
623
                    self.fail('key deeper was accessed')
 
624
                result[key] = graph_dict[key]
 
625
            return result
466
626
        an_obj = stub()
467
627
        an_obj.get_parents = get_parents
 
628
        an_obj.get_parent_map = get_parent_map
468
629
        graph = _mod_graph.Graph(an_obj)
469
630
        return graph.heads(search)
470
631
 
502
663
        }
503
664
        self.assertEqual(set(['h1', 'h2']),
504
665
            self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
 
666
 
 
667
 
 
668
class TestCachingParentsProvider(tests.TestCase):
 
669
 
 
670
    def setUp(self):
 
671
        super(TestCachingParentsProvider, self).setUp()
 
672
        dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
 
673
        self.inst_pp = InstrumentedParentsProvider(dict_pp)
 
674
        self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
 
675
 
 
676
    def test_get_parents(self):
 
677
        """Requesting the same revision should be returned from cache"""
 
678
        self.assertEqual({}, self.caching_pp._cache)
 
679
        self.assertEqual([('b',)], self.caching_pp.get_parents(['a']))
 
680
        self.assertEqual(['a'], self.inst_pp.calls)
 
681
        self.assertEqual([('b',)], self.caching_pp.get_parents(['a']))
 
682
        # No new call, as it should have been returned from the cache
 
683
        self.assertEqual(['a'], self.inst_pp.calls)
 
684
        self.assertEqual({'a':('b',)}, self.caching_pp._cache)
 
685
 
 
686
    def test_get_parents_not_present(self):
 
687
        """The cache should also track when a revision doesn't exist"""
 
688
        self.assertEqual([None], self.caching_pp.get_parents(['b']))
 
689
        self.assertEqual(['b'], self.inst_pp.calls)
 
690
        self.assertEqual([None], self.caching_pp.get_parents(['b']))
 
691
        # No new calls
 
692
        self.assertEqual(['b'], self.inst_pp.calls)
 
693
        self.assertEqual({'b':None}, self.caching_pp._cache)
 
694
 
 
695
    def test_get_parents_mixed(self):
 
696
        """Anything that can be returned from cache, should be"""
 
697
        self.assertEqual([None], self.caching_pp.get_parents(['b']))
 
698
        self.assertEqual(['b'], self.inst_pp.calls)
 
699
        self.assertEqual([('b',), None],
 
700
                         self.caching_pp.get_parents(['a', 'b']))
 
701
        self.assertEqual(['b', 'a'], self.inst_pp.calls)
 
702
 
 
703
    def test_get_parents_repeated(self):
 
704
        """Asking for the same parent 2x will only forward 1 request."""
 
705
        self.assertEqual([None, ('b',), None],
 
706
                         self.caching_pp.get_parents(['b', 'a', 'b']))
 
707
        # Use sorted because we don't care about the order, just that each is
 
708
        # only present 1 time.
 
709
        self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))