~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_index.py

  • Committer: Vincent Ladeuil
  • Date: 2010-02-10 15:46:03 UTC
  • mfrom: (4985.3.21 update)
  • mto: This revision was merged to the branch mainline in revision 5021.
  • Revision ID: v.ladeuil+lp@free.fr-20100210154603-k4no1gvfuqpzrw7p
Update performs two merges in a more logical order but stop on conflicts

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2007 Canonical Ltd
 
1
# Copyright (C) 2007, 2009 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
"""Tests for indices."""
18
18
 
173
173
            "key\x00\x00\t\x00data\n"
174
174
            "\n", contents)
175
175
 
 
176
    def test_clear_cache(self):
 
177
        builder = GraphIndexBuilder(reference_lists=2)
 
178
        # This is a no-op, but the api should exist
 
179
        builder.clear_cache()
 
180
 
176
181
    def test_node_references_are_byte_offsets(self):
177
182
        builder = GraphIndexBuilder(reference_lists=1)
178
183
        builder.add_node(('reference', ), 'data', ([], ))
230
235
        builder.add_node(('2-key', ), '', (references, ))
231
236
        stream = builder.finish()
232
237
        contents = stream.read()
233
 
        self.assertEqual(
 
238
        self.assertEqualDiff(
234
239
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
235
240
            "0\x00a\x00\x00\n"
236
241
            "1\x00a\x00\x00\n"
383
388
        size = trans.put_file('index', stream)
384
389
        return GraphIndex(trans, 'index', size)
385
390
 
 
391
    def test_clear_cache(self):
 
392
        index = self.make_index()
 
393
        # For now, we just want to make sure the api is available. As this is
 
394
        # old code, we don't really worry if it *does* anything.
 
395
        index.clear_cache()
 
396
 
386
397
    def test_open_bad_index_no_error(self):
387
398
        trans = self.get_transport()
388
399
        trans.put_bytes('name', "not an index\n")
558
569
        # not create a new transport request, and should return False (cannot
559
570
        # be in the index) - even when the byte location we ask for is outside
560
571
        # the parsed region
561
 
        # 
 
572
        #
562
573
        result = index._lookup_keys_via_location([(4000, self.make_key(40))])
563
574
        self.assertEqual(
564
575
            [((4000, self.make_key(40)),
922
933
        index = self.make_index(nodes=[(('key', ), 'value', ())])
923
934
        index.validate()
924
935
 
 
936
    # XXX: external_references tests are duplicated in test_btree_index.  We
 
937
    # probably should have per_graph_index tests...
 
938
    def test_external_references_no_refs(self):
 
939
        index = self.make_index(ref_lists=0, nodes=[])
 
940
        self.assertRaises(ValueError, index.external_references, 0)
 
941
 
 
942
    def test_external_references_no_results(self):
 
943
        index = self.make_index(ref_lists=1, nodes=[
 
944
            (('key',), 'value', ([],))])
 
945
        self.assertEqual(set(), index.external_references(0))
 
946
 
 
947
    def test_external_references_missing_ref(self):
 
948
        missing_key = ('missing',)
 
949
        index = self.make_index(ref_lists=1, nodes=[
 
950
            (('key',), 'value', ([missing_key],))])
 
951
        self.assertEqual(set([missing_key]), index.external_references(0))
 
952
 
 
953
    def test_external_references_multiple_ref_lists(self):
 
954
        missing_key = ('missing',)
 
955
        index = self.make_index(ref_lists=2, nodes=[
 
956
            (('key',), 'value', ([], [missing_key]))])
 
957
        self.assertEqual(set([]), index.external_references(0))
 
958
        self.assertEqual(set([missing_key]), index.external_references(1))
 
959
 
 
960
    def test_external_references_two_records(self):
 
961
        index = self.make_index(ref_lists=1, nodes=[
 
962
            (('key-1',), 'value', ([('key-2',)],)),
 
963
            (('key-2',), 'value', ([],)),
 
964
            ])
 
965
        self.assertEqual(set([]), index.external_references(0))
 
966
 
 
967
    def test__find_ancestors(self):
 
968
        key1 = ('key-1',)
 
969
        key2 = ('key-2',)
 
970
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
971
            (key1, 'value', ([key2],)),
 
972
            (key2, 'value', ([],)),
 
973
            ])
 
974
        parent_map = {}
 
975
        missing_keys = set()
 
976
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
 
977
        self.assertEqual({key1: (key2,)}, parent_map)
 
978
        self.assertEqual(set(), missing_keys)
 
979
        self.assertEqual(set([key2]), search_keys)
 
980
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
 
981
                                            missing_keys)
 
982
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
 
983
        self.assertEqual(set(), missing_keys)
 
984
        self.assertEqual(set(), search_keys)
 
985
 
 
986
    def test__find_ancestors_w_missing(self):
 
987
        key1 = ('key-1',)
 
988
        key2 = ('key-2',)
 
989
        key3 = ('key-3',)
 
990
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
991
            (key1, 'value', ([key2],)),
 
992
            (key2, 'value', ([],)),
 
993
            ])
 
994
        parent_map = {}
 
995
        missing_keys = set()
 
996
        search_keys = index._find_ancestors([key2, key3], 0, parent_map,
 
997
                                            missing_keys)
 
998
        self.assertEqual({key2: ()}, parent_map)
 
999
        self.assertEqual(set([key3]), missing_keys)
 
1000
        self.assertEqual(set(), search_keys)
 
1001
 
 
1002
    def test__find_ancestors_dont_search_known(self):
 
1003
        key1 = ('key-1',)
 
1004
        key2 = ('key-2',)
 
1005
        key3 = ('key-3',)
 
1006
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1007
            (key1, 'value', ([key2],)),
 
1008
            (key2, 'value', ([key3],)),
 
1009
            (key3, 'value', ([],)),
 
1010
            ])
 
1011
        # We already know about key2, so we won't try to search for key3
 
1012
        parent_map = {key2: (key3,)}
 
1013
        missing_keys = set()
 
1014
        search_keys = index._find_ancestors([key1], 0, parent_map,
 
1015
                                            missing_keys)
 
1016
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1017
        self.assertEqual(set(), missing_keys)
 
1018
        self.assertEqual(set(), search_keys)
 
1019
 
 
1020
    def test_supports_unlimited_cache(self):
 
1021
        builder = GraphIndexBuilder(0, key_elements=1)
 
1022
        stream = builder.finish()
 
1023
        trans = get_transport(self.get_url())
 
1024
        size = trans.put_file('index', stream)
 
1025
        # It doesn't matter what unlimited_cache does here, just that it can be
 
1026
        # passed
 
1027
        index = GraphIndex(trans, 'index', size, unlimited_cache=True)
 
1028
 
925
1029
 
926
1030
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
927
1031
 
978
1082
        index.insert_index(0, index1)
979
1083
        self.assertEqual([(index1, ('key', ), '')], list(index.iter_all_entries()))
980
1084
 
 
1085
    def test_clear_cache(self):
 
1086
        log = []
 
1087
 
 
1088
        class ClearCacheProxy(object):
 
1089
 
 
1090
            def __init__(self, index):
 
1091
                self._index = index
 
1092
 
 
1093
            def __getattr__(self, name):
 
1094
                return getattr(self._index)
 
1095
 
 
1096
            def clear_cache(self):
 
1097
                log.append(self._index)
 
1098
                return self._index.clear_cache()
 
1099
 
 
1100
        index = CombinedGraphIndex([])
 
1101
        index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
 
1102
        index.insert_index(0, ClearCacheProxy(index1))
 
1103
        index2 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
 
1104
        index.insert_index(1, ClearCacheProxy(index2))
 
1105
        # CombinedGraphIndex should call 'clear_cache()' on all children
 
1106
        index.clear_cache()
 
1107
        self.assertEqual(sorted([index1, index2]), sorted(log))
 
1108
 
981
1109
    def test_iter_all_entries_empty(self):
982
1110
        index = CombinedGraphIndex([])
983
1111
        self.assertEqual([], list(index.iter_all_entries()))
1047
1175
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),
1048
1176
            (index2, ('ref', ), 'refdata', ((), ))]),
1049
1177
            set(index.iter_entries([('name', ), ('ref', )])))
1050
 
 
 
1178
 
1051
1179
    def test_iter_all_keys_dup_entry(self):
1052
1180
        index1 = self.make_index('1', 1, nodes=[
1053
1181
            (('name', ), 'data', ([('ref', )], )),
1058
1186
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),
1059
1187
            (index1, ('ref', ), 'refdata', ((), ))]),
1060
1188
            set(index.iter_entries([('name', ), ('ref', )])))
1061
 
 
 
1189
 
1062
1190
    def test_iter_missing_entry_empty(self):
1063
1191
        index = CombinedGraphIndex([])
1064
1192
        self.assertEqual([], list(index.iter_entries([('a', )])))
1073
1201
        index2 = self.make_index('2')
1074
1202
        index = CombinedGraphIndex([index1, index2])
1075
1203
        self.assertEqual([], list(index.iter_entries([('a', )])))
1076
 
 
 
1204
 
1077
1205
    def test_iter_entry_present_one_index_only(self):
1078
1206
        index1 = self.make_index('1', nodes=[(('key', ), '', ())])
1079
1207
        index2 = self.make_index('2', nodes=[])
1240
1368
                                    ['1', '2', '3'])
1241
1369
        self.assertRaises(errors.NoSuchFile, index.validate)
1242
1370
 
 
1371
    def test_find_ancestors_across_indexes(self):
 
1372
        key1 = ('key-1',)
 
1373
        key2 = ('key-2',)
 
1374
        key3 = ('key-3',)
 
1375
        key4 = ('key-4',)
 
1376
        index1 = self.make_index('12', ref_lists=1, nodes=[
 
1377
            (key1, 'value', ([],)),
 
1378
            (key2, 'value', ([key1],)),
 
1379
            ])
 
1380
        index2 = self.make_index('34', ref_lists=1, nodes=[
 
1381
            (key3, 'value', ([key2],)),
 
1382
            (key4, 'value', ([key3],)),
 
1383
            ])
 
1384
        c_index = CombinedGraphIndex([index1, index2])
 
1385
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
 
1386
        self.assertEqual({key1: ()}, parent_map)
 
1387
        self.assertEqual(set(), missing_keys)
 
1388
        # Now look for a key from index2 which requires us to find the key in
 
1389
        # the second index, and then continue searching for parents in the
 
1390
        # first index
 
1391
        parent_map, missing_keys = c_index.find_ancestry([key3], 0)
 
1392
        self.assertEqual({key1: (), key2: (key1,), key3: (key2,)}, parent_map)
 
1393
        self.assertEqual(set(), missing_keys)
 
1394
 
 
1395
    def test_find_ancestors_missing_keys(self):
 
1396
        key1 = ('key-1',)
 
1397
        key2 = ('key-2',)
 
1398
        key3 = ('key-3',)
 
1399
        key4 = ('key-4',)
 
1400
        index1 = self.make_index('12', ref_lists=1, nodes=[
 
1401
            (key1, 'value', ([],)),
 
1402
            (key2, 'value', ([key1],)),
 
1403
            ])
 
1404
        index2 = self.make_index('34', ref_lists=1, nodes=[
 
1405
            (key3, 'value', ([key2],)),
 
1406
            ])
 
1407
        c_index = CombinedGraphIndex([index1, index2])
 
1408
        # Searching for a key which is actually not present at all should
 
1409
        # eventually converge
 
1410
        parent_map, missing_keys = c_index.find_ancestry([key4], 0)
 
1411
        self.assertEqual({}, parent_map)
 
1412
        self.assertEqual(set([key4]), missing_keys)
 
1413
 
 
1414
    def test_find_ancestors_no_indexes(self):
 
1415
        c_index = CombinedGraphIndex([])
 
1416
        key1 = ('key-1',)
 
1417
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
 
1418
        self.assertEqual({}, parent_map)
 
1419
        self.assertEqual(set([key1]), missing_keys)
 
1420
 
 
1421
    def test_find_ancestors_ghost_parent(self):
 
1422
        key1 = ('key-1',)
 
1423
        key2 = ('key-2',)
 
1424
        key3 = ('key-3',)
 
1425
        key4 = ('key-4',)
 
1426
        index1 = self.make_index('12', ref_lists=1, nodes=[
 
1427
            (key1, 'value', ([],)),
 
1428
            (key2, 'value', ([key1],)),
 
1429
            ])
 
1430
        index2 = self.make_index('34', ref_lists=1, nodes=[
 
1431
            (key4, 'value', ([key2, key3],)),
 
1432
            ])
 
1433
        c_index = CombinedGraphIndex([index1, index2])
 
1434
        # Searching for a key which is actually not present at all should
 
1435
        # eventually converge
 
1436
        parent_map, missing_keys = c_index.find_ancestry([key4], 0)
 
1437
        self.assertEqual({key4: (key2, key3), key2: (key1,), key1: ()},
 
1438
                         parent_map)
 
1439
        self.assertEqual(set([key3]), missing_keys)
 
1440
 
 
1441
    def test__find_ancestors_empty_index(self):
 
1442
        index = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
 
1443
        parent_map = {}
 
1444
        missing_keys = set()
 
1445
        search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
 
1446
                                            missing_keys)
 
1447
        self.assertEqual(set(), search_keys)
 
1448
        self.assertEqual({}, parent_map)
 
1449
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
 
1450
 
1243
1451
 
1244
1452
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
1245
1453