← 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-08-07 20:01:09 UTC
  • mfrom: (1551.15.82 Aaron's integration)
  • Revision ID: pqm@pqm.ubuntu.com-20070807200109-d25wg4bqp97uo9d5
Fix KeyError in Graph.filter_candidate_lca corner case

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
145
145
        return self._real_parents_provider.get_parents(nodes)
146
146
 
147
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
 
 
159
 
148
160
class TestGraph(TestCaseWithMemoryTransport):
149
161
 
150
162
    def make_graph(self, ancestors):
291
303
 
292
304
    def test_stacked_parents_provider(self):
293
305
 
294
 
        class ParentsProvider(object):
295
 
 
296
 
            def __init__(self, ancestry):
297
 
                self.ancestry = ancestry
298
 
 
299
 
            def get_parents(self, revisions):
300
 
                return [self.ancestry.get(r, None) for r in revisions]
301
 
 
302
 
        parents1 = ParentsProvider({'rev2': ['rev3']})
303
 
        parents2 = ParentsProvider({'rev1': ['rev4']})
 
306
        parents1 = DictParentsProvider({'rev2': ['rev3']})
 
307
        parents2 = DictParentsProvider({'rev1': ['rev4']})
304
308
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
305
309
        self.assertEqual([['rev4',], ['rev3']],
306
310
                         stacked.get_parents(['rev1', 'rev2']))
346
350
        graph = _mod_graph.Graph(instrumented_provider)
347
351
        self.assertFalse(graph.is_ancestor('a', 'c'))
348
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 'd'
 
358
        in the same pass as we discover that 'c' is an ancestor of 'd', and
 
359
        therefore 'd' can't be an lca.
 
360
        """
 
361
        # This test is sensitive to the iteration order of dicts.  It will
 
362
        # pass incorrectly if 'e' and 'a' sort before 'c'
 
363
        graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
 
364
                                 'a': [NULL_REVISION], 'e': [NULL_REVISION]})
 
365
        self.assertEqual(['c'], graph._filter_candidate_lca(['a', 'c', 'e']))