← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_index.py

  • Committer: Martin Pool
  • Date: 2009-09-14 01:48:28 UTC
  • mfrom: (4685 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4688.
  • Revision ID: mbp@sourcefrog.net-20090914014828-ydr9rlkdfq2sv57z
Merge news

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_index.py
953
953
            ])
954
954
        self.assertEqual(set([]), index.external_references(0))
955
955
 
 
956
    def test__find_ancestors(self):
 
957
        key1 = ('key-1',)
 
958
        key2 = ('key-2',)
 
959
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
960
            (key1, 'value', ([key2],)),
 
961
            (key2, 'value', ([],)),
 
962
            ])
 
963
        parent_map = {}
 
964
        missing_keys = set()
 
965
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
 
966
        self.assertEqual({key1: (key2,)}, parent_map)
 
967
        self.assertEqual(set(), missing_keys)
 
968
        self.assertEqual(set([key2]), search_keys)
 
969
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
 
970
                                            missing_keys)
 
971
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
 
972
        self.assertEqual(set(), missing_keys)
 
973
        self.assertEqual(set(), search_keys)
 
974
 
 
975
    def test__find_ancestors_w_missing(self):
 
976
        key1 = ('key-1',)
 
977
        key2 = ('key-2',)
 
978
        key3 = ('key-3',)
 
979
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
980
            (key1, 'value', ([key2],)),
 
981
            (key2, 'value', ([],)),
 
982
            ])
 
983
        parent_map = {}
 
984
        missing_keys = set()
 
985
        search_keys = index._find_ancestors([key2, key3], 0, parent_map,
 
986
                                            missing_keys)
 
987
        self.assertEqual({key2: ()}, parent_map)
 
988
        self.assertEqual(set([key3]), missing_keys)
 
989
        self.assertEqual(set(), search_keys)
 
990
 
 
991
    def test__find_ancestors_dont_search_known(self):
 
992
        key1 = ('key-1',)
 
993
        key2 = ('key-2',)
 
994
        key3 = ('key-3',)
 
995
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
996
            (key1, 'value', ([key2],)),
 
997
            (key2, 'value', ([key3],)),
 
998
            (key3, 'value', ([],)),
 
999
            ])
 
1000
        # We already know about key2, so we won't try to search for key3
 
1001
        parent_map = {key2: (key3,)}
 
1002
        missing_keys = set()
 
1003
        search_keys = index._find_ancestors([key1], 0, parent_map,
 
1004
                                            missing_keys)
 
1005
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1006
        self.assertEqual(set(), missing_keys)
 
1007
        self.assertEqual(set(), search_keys)
 
1008
 
956
1009
 
957
1010
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
958
1011
 
1271
1324
                                    ['1', '2', '3'])
1272
1325
        self.assertRaises(errors.NoSuchFile, index.validate)
1273
1326
 
 
1327
    def test_find_ancestors_across_indexes(self):
 
1328
        key1 = ('key-1',)
 
1329
        key2 = ('key-2',)
 
1330
        key3 = ('key-3',)
 
1331
        key4 = ('key-4',)
 
1332
        index1 = self.make_index('12', ref_lists=1, nodes=[
 
1333
            (key1, 'value', ([],)),
 
1334
            (key2, 'value', ([key1],)),
 
1335
            ])
 
1336
        index2 = self.make_index('34', ref_lists=1, nodes=[
 
1337
            (key3, 'value', ([key2],)),
 
1338
            (key4, 'value', ([key3],)),
 
1339
            ])
 
1340
        c_index = CombinedGraphIndex([index1, index2])
 
1341
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
 
1342
        self.assertEqual({key1: ()}, parent_map)
 
1343
        self.assertEqual(set(), missing_keys)
 
1344
        # Now look for a key from index2 which requires us to find the key in
 
1345
        # the second index, and then continue searching for parents in the
 
1346
        # first index
 
1347
        parent_map, missing_keys = c_index.find_ancestry([key3], 0)
 
1348
        self.assertEqual({key1: (), key2: (key1,), key3: (key2,)}, parent_map)
 
1349
        self.assertEqual(set(), missing_keys)
 
1350
 
 
1351
    def test_find_ancestors_missing_keys(self):
 
1352
        key1 = ('key-1',)
 
1353
        key2 = ('key-2',)
 
1354
        key3 = ('key-3',)
 
1355
        key4 = ('key-4',)
 
1356
        index1 = self.make_index('12', ref_lists=1, nodes=[
 
1357
            (key1, 'value', ([],)),
 
1358
            (key2, 'value', ([key1],)),
 
1359
            ])
 
1360
        index2 = self.make_index('34', ref_lists=1, nodes=[
 
1361
            (key3, 'value', ([key2],)),
 
1362
            ])
 
1363
        c_index = CombinedGraphIndex([index1, index2])
 
1364
        # Searching for a key which is actually not present at all should
 
1365
        # eventually converge
 
1366
        parent_map, missing_keys = c_index.find_ancestry([key4], 0)
 
1367
        self.assertEqual({}, parent_map)
 
1368
        self.assertEqual(set([key4]), missing_keys)
 
1369
 
 
1370
    def test_find_ancestors_no_indexes(self):
 
1371
        c_index = CombinedGraphIndex([])
 
1372
        key1 = ('key-1',)
 
1373
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
 
1374
        self.assertEqual({}, parent_map)
 
1375
        self.assertEqual(set([key1]), missing_keys)
 
1376
 
 
1377
    def test_find_ancestors_ghost_parent(self):
 
1378
        key1 = ('key-1',)
 
1379
        key2 = ('key-2',)
 
1380
        key3 = ('key-3',)
 
1381
        key4 = ('key-4',)
 
1382
        index1 = self.make_index('12', ref_lists=1, nodes=[
 
1383
            (key1, 'value', ([],)),
 
1384
            (key2, 'value', ([key1],)),
 
1385
            ])
 
1386
        index2 = self.make_index('34', ref_lists=1, nodes=[
 
1387
            (key4, 'value', ([key2, key3],)),
 
1388
            ])
 
1389
        c_index = CombinedGraphIndex([index1, index2])
 
1390
        # Searching for a key which is actually not present at all should
 
1391
        # eventually converge
 
1392
        parent_map, missing_keys = c_index.find_ancestry([key4], 0)
 
1393
        self.assertEqual({key4: (key2, key3), key2: (key1,), key1: ()},
 
1394
                         parent_map)
 
1395
        self.assertEqual(set([key3]), missing_keys)
 
1396
 
 
1397
    def test__find_ancestors_empty_index(self):
 
1398
        index = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
 
1399
        parent_map = {}
 
1400
        missing_keys = set()
 
1401
        search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
 
1402
                                            missing_keys)
 
1403
        self.assertEqual(set(), search_keys)
 
1404
        self.assertEqual({}, parent_map)
 
1405
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
 
1406
 
1274
1407
 
1275
1408
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
1276
1409