/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

  • Committer: Robert Collins
  • Date: 2007-08-22 00:00:26 UTC
  • mfrom: (2739 +trunk)
  • mto: (2592.3.96 repository)
  • mto: This revision was merged to the branch mainline in revision 2742.
  • Revision ID: robertc@robertcollins.net-20070822000026-kvufiqhlreokb1en
Merge bzr.dev

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,
 
19
    graph as _mod_graph,
20
20
    )
21
21
from bzrlib.revision import NULL_REVISION
22
22
from bzrlib.tests import TestCaseWithMemoryTransport
120
120
                    'rev2b': ['rev1'], 'rev2c': ['rev1'],
121
121
                    'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
122
122
 
 
123
#  NULL_REVISION
 
124
#       |
 
125
#       f
 
126
#       |
 
127
#       e
 
128
#      / \
 
129
#     b   d
 
130
#     | \ |
 
131
#     a   c
 
132
 
 
133
boundary = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e'], 'e': ['f'],
 
134
            'f':[NULL_REVISION]}
 
135
 
 
136
 
 
137
class InstrumentedParentsProvider(object):
 
138
 
 
139
    def __init__(self, parents_provider):
 
140
        self.calls = []
 
141
        self._real_parents_provider = parents_provider
 
142
 
 
143
    def get_parents(self, nodes):
 
144
        self.calls.extend(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]
 
158
 
123
159
 
124
160
class TestGraph(TestCaseWithMemoryTransport):
125
161
 
267
303
 
268
304
    def test_stacked_parents_provider(self):
269
305
 
270
 
        class ParentsProvider(object):
271
 
 
272
 
            def __init__(self, ancestry):
273
 
                self.ancestry = ancestry
274
 
 
275
 
            def get_parents(self, revisions):
276
 
                return [self.ancestry.get(r, None) for r in revisions]
277
 
 
278
 
        parents1 = ParentsProvider({'rev2': ['rev3']})
279
 
        parents2 = ParentsProvider({'rev1': ['rev4']})
280
 
        stacked = graph._StackedParentsProvider([parents1, parents2])
 
306
        parents1 = DictParentsProvider({'rev2': ['rev3']})
 
307
        parents2 = DictParentsProvider({'rev1': ['rev4']})
 
308
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
281
309
        self.assertEqual([['rev4',], ['rev3']],
282
310
                         stacked.get_parents(['rev1', 'rev2']))
283
311
        self.assertEqual([['rev3',], ['rev4']],
294
322
        self.assertEqual(set(args), set(topo_args))
295
323
        self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
296
324
        self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
 
325
 
 
326
    def test_is_ancestor(self):
 
327
        graph = self.make_graph(ancestry_1)
 
328
        self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
 
329
        self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
 
330
        self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
 
331
        self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
 
332
        self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
 
333
        self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
 
334
        self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
 
335
        self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
 
336
        self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
 
337
        instrumented_provider = InstrumentedParentsProvider(graph)
 
338
        instrumented_graph = _mod_graph.Graph(instrumented_provider)
 
339
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
 
340
        self.assertTrue('null:' not in instrumented_provider.calls)
 
341
 
 
342
    def test_is_ancestor_boundary(self):
 
343
        """Ensure that we avoid searching the whole graph.
 
344
        
 
345
        This requires searching through b as a common ancestor, so we
 
346
        can identify that e is common.
 
347
        """
 
348
        graph = self.make_graph(boundary)
 
349
        instrumented_provider = InstrumentedParentsProvider(graph)
 
350
        graph = _mod_graph.Graph(instrumented_provider)
 
351
        self.assertFalse(graph.is_ancestor('a', 'c'))
 
352
        self.assertTrue('null:' not in instrumented_provider.calls)
 
353
 
 
354
    def test_filter_candidate_lca(self):
 
355
        """Test filter_candidate_lca for a corner case
 
356
 
 
357
        This tests the case where we encounter the end of iteration for 'e'
 
358
        in the same pass as we discover that 'd' is an ancestor of 'e', and
 
359
        therefore 'e' can't be an lca.
 
360
 
 
361
        To compensate for different dict orderings on other Python
 
362
        implementations, we mirror 'd' and 'e' with 'b' and 'a'.
 
363
        """
 
364
        # This test is sensitive to the iteration order of dicts.  It will
 
365
        # pass incorrectly if 'e' and 'a' sort before 'c'
 
366
        #
 
367
        # NULL_REVISION
 
368
        #     / \
 
369
        #    a   e
 
370
        #    |   |
 
371
        #    b   d
 
372
        #     \ /
 
373
        #      c
 
374
        graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
 
375
                                 'a': [NULL_REVISION], 'e': [NULL_REVISION]})
 
376
        self.assertEqual(['c'], graph._filter_candidate_lca(['a', 'c', 'e']))