← 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-07-28 01:33:05 UTC
  • mfrom: (2653.2.7 kill-ancestry)
  • Revision ID: pqm@pqm.ubuntu.com-20070728013305-u91kdx3px9ytdyok
Add Graph.is_ancestor, update code to use it

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
 
123
147
 
124
148
class TestGraph(TestCaseWithMemoryTransport):
125
149
 
277
301
 
278
302
        parents1 = ParentsProvider({'rev2': ['rev3']})
279
303
        parents2 = ParentsProvider({'rev1': ['rev4']})
280
 
        stacked = graph._StackedParentsProvider([parents1, parents2])
 
304
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
281
305
        self.assertEqual([['rev4',], ['rev3']],
282
306
                         stacked.get_parents(['rev1', 'rev2']))
283
307
        self.assertEqual([['rev3',], ['rev4']],
294
318
        self.assertEqual(set(args), set(topo_args))
295
319
        self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
296
320
        self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
 
321
 
 
322
    def test_is_ancestor(self):
 
323
        graph = self.make_graph(ancestry_1)
 
324
        self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
 
325
        self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
 
326
        self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
 
327
        self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
 
328
        self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
 
329
        self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
 
330
        self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
 
331
        self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
 
332
        self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
 
333
        instrumented_provider = InstrumentedParentsProvider(graph)
 
334
        instrumented_graph = _mod_graph.Graph(instrumented_provider)
 
335
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
 
336
        self.assertTrue('null:' not in instrumented_provider.calls)
 
337
 
 
338
    def test_is_ancestor_boundary(self):
 
339
        """Ensure that we avoid searching the whole graph.
 
340
        
 
341
        This requires searching through b as a common ancestor, so we
 
342
        can identify that e is common.
 
343
        """
 
344
        graph = self.make_graph(boundary)
 
345
        instrumented_provider = InstrumentedParentsProvider(graph)
 
346
        graph = _mod_graph.Graph(instrumented_provider)
 
347
        self.assertFalse(graph.is_ancestor('a', 'c'))
 
348
        self.assertTrue('null:' not in instrumented_provider.calls)