← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

Update to bzr.dev.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
283
283
#     |/
284
284
#     j
285
285
#
286
 
# y is found to be common right away, but is the start of a long series of
 
286
# x is found to be common right away, but is the start of a long series of
287
287
# common commits.
288
288
# o is actually common, but the i-j shortcut makes it look like it is actually
289
 
# unique to j at first, you have to traverse all of y->o to find it.
290
 
# q,n give the walker from j a common point to stop searching, as does p,f.
 
289
# unique to j at first, you have to traverse all of x->o to find it.
 
290
# q,m gives the walker from j a common point to stop searching, as does p,f.
291
291
# k-n exists so that the second pass still has nodes that are worth searching,
292
292
# rather than instantly cancelling the extra walker.
293
293
 
396
396
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
397
397
              'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
398
398
 
 
399
# A graph that shows we can shortcut finding revnos when reaching them from the
 
400
# side.
 
401
#  NULL_REVISION
 
402
#       |
 
403
#       a
 
404
#       |
 
405
#       b
 
406
#       |
 
407
#       c
 
408
#       |
 
409
#       d
 
410
#       |
 
411
#       e
 
412
#      / \
 
413
#     f   g
 
414
#     |
 
415
#     h
 
416
#     |
 
417
#     i
 
418
 
 
419
with_tail = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'], 'e':['d'],
 
420
             'f':['e'], 'g':['e'], 'h':['f'], 'i':['h']}
399
421
 
400
422
 
401
423
class InstrumentedParentsProvider(object):
409
431
        return self._real_parents_provider.get_parent_map(nodes)
410
432
 
411
433
 
 
434
class TestGraphBase(tests.TestCase):
 
435
 
 
436
    def make_graph(self, ancestors):
 
437
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
 
438
 
 
439
    def make_breaking_graph(self, ancestors, break_on):
 
440
        """Make a Graph that raises an exception if we hit a node."""
 
441
        g = self.make_graph(ancestors)
 
442
        orig_parent_map = g.get_parent_map
 
443
        def get_parent_map(keys):
 
444
            bad_keys = set(keys).intersection(break_on)
 
445
            if bad_keys:
 
446
                self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
 
447
            return orig_parent_map(keys)
 
448
        g.get_parent_map = get_parent_map
 
449
        return g
 
450
 
 
451
 
412
452
class TestGraph(TestCaseWithMemoryTransport):
413
453
 
414
454
    def make_graph(self, ancestors):
1138
1178
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1139
1179
 
1140
1180
 
1141
 
class TestFindUniqueAncestors(tests.TestCase):
1142
 
 
1143
 
    def make_graph(self, ancestors):
1144
 
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
1145
 
 
1146
 
    def make_breaking_graph(self, ancestors, break_on):
1147
 
        """Make a Graph that raises an exception if we hit a node."""
1148
 
        g = self.make_graph(ancestors)
1149
 
        orig_parent_map = g.get_parent_map
1150
 
        def get_parent_map(keys):
1151
 
            bad_keys = set(keys).intersection(break_on)
1152
 
            if bad_keys:
1153
 
                self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
1154
 
            return orig_parent_map(keys)
1155
 
        g.get_parent_map = get_parent_map
1156
 
        return g
 
1181
class TestFindUniqueAncestors(TestGraphBase):
1157
1182
 
1158
1183
    def assertFindUniqueAncestors(self, graph, expected, node, common):
1159
1184
        actual = graph.find_unique_ancestors(node, common)
1228
1253
            ['h', 'i', 'j', 'y'], 'j', ['z'])
1229
1254
 
1230
1255
 
 
1256
class TestGraphFindDistanceToNull(TestGraphBase):
 
1257
    """Test an api that should be able to compute a revno"""
 
1258
 
 
1259
    def assertFindDistance(self, revno, graph, target_id, known_ids):
 
1260
        """Assert the output of Graph.find_distance_to_null()"""
 
1261
        actual = graph.find_distance_to_null(target_id, known_ids)
 
1262
        self.assertEqual(revno, actual)
 
1263
 
 
1264
    def test_nothing_known(self):
 
1265
        graph = self.make_graph(ancestry_1)
 
1266
        self.assertFindDistance(0, graph, NULL_REVISION, [])
 
1267
        self.assertFindDistance(1, graph, 'rev1', [])
 
1268
        self.assertFindDistance(2, graph, 'rev2a', [])
 
1269
        self.assertFindDistance(2, graph, 'rev2b', [])
 
1270
        self.assertFindDistance(3, graph, 'rev3', [])
 
1271
        self.assertFindDistance(4, graph, 'rev4', [])
 
1272
 
 
1273
    def test_rev_is_ghost(self):
 
1274
        graph = self.make_graph(ancestry_1)
 
1275
        e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
 
1276
                              graph.find_distance_to_null, 'rev_missing', [])
 
1277
        self.assertEqual('rev_missing', e.revision_id)
 
1278
        self.assertEqual('rev_missing', e.ghost_revision_id)
 
1279
 
 
1280
    def test_ancestor_is_ghost(self):
 
1281
        graph = self.make_graph({'rev':['parent']})
 
1282
        e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
 
1283
                              graph.find_distance_to_null, 'rev', [])
 
1284
        self.assertEqual('rev', e.revision_id)
 
1285
        self.assertEqual('parent', e.ghost_revision_id)
 
1286
 
 
1287
    def test_known_in_ancestry(self):
 
1288
        graph = self.make_graph(ancestry_1)
 
1289
        self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
 
1290
        self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
 
1291
 
 
1292
    def test_known_in_ancestry_limits(self):
 
1293
        graph = self.make_breaking_graph(ancestry_1, ['rev1'])
 
1294
        self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
 
1295
 
 
1296
    def test_target_is_ancestor(self):
 
1297
        graph = self.make_graph(ancestry_1)
 
1298
        self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
 
1299
 
 
1300
    def test_target_is_ancestor_limits(self):
 
1301
        """We shouldn't search all history if we run into ourselves"""
 
1302
        graph = self.make_breaking_graph(ancestry_1, ['rev1'])
 
1303
        self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
 
1304
 
 
1305
    def test_target_parallel_to_known_limits(self):
 
1306
        # Even though the known revision isn't part of the other ancestry, they
 
1307
        # eventually converge
 
1308
        graph = self.make_breaking_graph(with_tail, ['a'])
 
1309
        self.assertFindDistance(6, graph, 'f', [('g', 6)])
 
1310
        self.assertFindDistance(7, graph, 'h', [('g', 6)])
 
1311
        self.assertFindDistance(8, graph, 'i', [('g', 6)])
 
1312
        self.assertFindDistance(6, graph, 'g', [('i', 8)])
 
1313
 
 
1314
 
1231
1315
class TestCachingParentsProvider(tests.TestCase):
1232
1316
 
1233
1317
    def setUp(self):