← 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: 2010-01-29 14:09:05 UTC
  • mto: This revision was merged to the branch mainline in revision 4992.
  • Revision ID: mbp@sourcefrog.net-20100129140905-2uiarb6p8di1ywsr
Correction to url

from review: https://code.edge.launchpad.net/~mbp/bzr/doc/+merge/18250

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_index.py
1
 
# Copyright (C) 2007-2010 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
16
16
 
17
17
"""Tests for indices."""
18
18
 
19
 
from bzrlib import (
20
 
    errors,
21
 
    index,
22
 
    tests,
23
 
    transport,
24
 
    )
25
 
 
26
 
 
27
 
class TestGraphIndexBuilder(tests.TestCaseWithMemoryTransport):
 
19
from bzrlib import errors
 
20
from bzrlib.index import *
 
21
from bzrlib.tests import TestCaseWithMemoryTransport
 
22
from bzrlib.transport import get_transport
 
23
 
 
24
 
 
25
class TestGraphIndexBuilder(TestCaseWithMemoryTransport):
28
26
 
29
27
    def test_build_index_empty(self):
30
 
        builder = index.GraphIndexBuilder()
 
28
        builder = GraphIndexBuilder()
31
29
        stream = builder.finish()
32
30
        contents = stream.read()
33
31
        self.assertEqual(
35
33
            contents)
36
34
 
37
35
    def test_build_index_empty_two_element_keys(self):
38
 
        builder = index.GraphIndexBuilder(key_elements=2)
 
36
        builder = GraphIndexBuilder(key_elements=2)
39
37
        stream = builder.finish()
40
38
        contents = stream.read()
41
39
        self.assertEqual(
43
41
            contents)
44
42
 
45
43
    def test_build_index_one_reference_list_empty(self):
46
 
        builder = index.GraphIndexBuilder(reference_lists=1)
 
44
        builder = GraphIndexBuilder(reference_lists=1)
47
45
        stream = builder.finish()
48
46
        contents = stream.read()
49
47
        self.assertEqual(
51
49
            contents)
52
50
 
53
51
    def test_build_index_two_reference_list_empty(self):
54
 
        builder = index.GraphIndexBuilder(reference_lists=2)
 
52
        builder = GraphIndexBuilder(reference_lists=2)
55
53
        stream = builder.finish()
56
54
        contents = stream.read()
57
55
        self.assertEqual(
59
57
            contents)
60
58
 
61
59
    def test_build_index_one_node_no_refs(self):
62
 
        builder = index.GraphIndexBuilder()
 
60
        builder = GraphIndexBuilder()
63
61
        builder.add_node(('akey', ), 'data')
64
62
        stream = builder.finish()
65
63
        contents = stream.read()
68
66
            "akey\x00\x00\x00data\n\n", contents)
69
67
 
70
68
    def test_build_index_one_node_no_refs_accepts_empty_reflist(self):
71
 
        builder = index.GraphIndexBuilder()
 
69
        builder = GraphIndexBuilder()
72
70
        builder.add_node(('akey', ), 'data', ())
73
71
        stream = builder.finish()
74
72
        contents = stream.read()
80
78
        # multipart keys are separated by \x00 - because they are fixed length,
81
79
        # not variable this does not cause any issues, and seems clearer to the
82
80
        # author.
83
 
        builder = index.GraphIndexBuilder(key_elements=2)
 
81
        builder = GraphIndexBuilder(key_elements=2)
84
82
        builder.add_node(('akey', 'secondpart'), 'data')
85
83
        stream = builder.finish()
86
84
        contents = stream.read()
89
87
            "akey\x00secondpart\x00\x00\x00data\n\n", contents)
90
88
 
91
89
    def test_add_node_empty_value(self):
92
 
        builder = index.GraphIndexBuilder()
 
90
        builder = GraphIndexBuilder()
93
91
        builder.add_node(('akey', ), '')
94
92
        stream = builder.finish()
95
93
        contents = stream.read()
99
97
 
100
98
    def test_build_index_nodes_sorted(self):
101
99
        # the highest sorted node comes first.
102
 
        builder = index.GraphIndexBuilder()
 
100
        builder = GraphIndexBuilder()
103
101
        # use three to have a good chance of glitching dictionary hash
104
102
        # lookups etc. Insert in randomish order that is not correct
105
103
        # and not the reverse of the correct order.
117
115
 
118
116
    def test_build_index_2_element_key_nodes_sorted(self):
119
117
        # multiple element keys are sorted first-key, second-key.
120
 
        builder = index.GraphIndexBuilder(key_elements=2)
 
118
        builder = GraphIndexBuilder(key_elements=2)
121
119
        # use three values of each key element, to have a good chance of
122
120
        # glitching dictionary hash lookups etc. Insert in randomish order that
123
121
        # is not correct and not the reverse of the correct order.
146
144
            "\n", contents)
147
145
 
148
146
    def test_build_index_reference_lists_are_included_one(self):
149
 
        builder = index.GraphIndexBuilder(reference_lists=1)
 
147
        builder = GraphIndexBuilder(reference_lists=1)
150
148
        builder.add_node(('key', ), 'data', ([], ))
151
149
        stream = builder.finish()
152
150
        contents = stream.read()
156
154
            "\n", contents)
157
155
 
158
156
    def test_build_index_reference_lists_with_2_element_keys(self):
159
 
        builder = index.GraphIndexBuilder(reference_lists=1, key_elements=2)
 
157
        builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
160
158
        builder.add_node(('key', 'key2'), 'data', ([], ))
161
159
        stream = builder.finish()
162
160
        contents = stream.read()
166
164
            "\n", contents)
167
165
 
168
166
    def test_build_index_reference_lists_are_included_two(self):
169
 
        builder = index.GraphIndexBuilder(reference_lists=2)
 
167
        builder = GraphIndexBuilder(reference_lists=2)
170
168
        builder.add_node(('key', ), 'data', ([], []))
171
169
        stream = builder.finish()
172
170
        contents = stream.read()
176
174
            "\n", contents)
177
175
 
178
176
    def test_clear_cache(self):
179
 
        builder = index.GraphIndexBuilder(reference_lists=2)
 
177
        builder = GraphIndexBuilder(reference_lists=2)
180
178
        # This is a no-op, but the api should exist
181
179
        builder.clear_cache()
182
180
 
183
181
    def test_node_references_are_byte_offsets(self):
184
 
        builder = index.GraphIndexBuilder(reference_lists=1)
 
182
        builder = GraphIndexBuilder(reference_lists=1)
185
183
        builder.add_node(('reference', ), 'data', ([], ))
186
184
        builder.add_node(('key', ), 'data', ([('reference', )], ))
187
185
        stream = builder.finish()
193
191
            "\n", contents)
194
192
 
195
193
    def test_node_references_are_cr_delimited(self):
196
 
        builder = index.GraphIndexBuilder(reference_lists=1)
 
194
        builder = GraphIndexBuilder(reference_lists=1)
197
195
        builder.add_node(('reference', ), 'data', ([], ))
198
196
        builder.add_node(('reference2', ), 'data', ([], ))
199
 
        builder.add_node(('key', ), 'data',
200
 
                         ([('reference', ), ('reference2', )], ))
 
197
        builder.add_node(('key', ), 'data', ([('reference', ), ('reference2', )], ))
201
198
        stream = builder.finish()
202
199
        contents = stream.read()
203
200
        self.assertEqual(
208
205
            "\n", contents)
209
206
 
210
207
    def test_multiple_reference_lists_are_tab_delimited(self):
211
 
        builder = index.GraphIndexBuilder(reference_lists=2)
 
208
        builder = GraphIndexBuilder(reference_lists=2)
212
209
        builder.add_node(('keference', ), 'data', ([], []))
213
 
        builder.add_node(('rey', ), 'data',
214
 
                         ([('keference', )], [('keference', )]))
 
210
        builder.add_node(('rey', ), 'data', ([('keference', )], [('keference', )]))
215
211
        stream = builder.finish()
216
212
        contents = stream.read()
217
213
        self.assertEqual(
221
217
            "\n", contents)
222
218
 
223
219
    def test_add_node_referencing_missing_key_makes_absent(self):
224
 
        builder = index.GraphIndexBuilder(reference_lists=1)
225
 
        builder.add_node(('rey', ), 'data',
226
 
                         ([('beference', ), ('aeference2', )], ))
 
220
        builder = GraphIndexBuilder(reference_lists=1)
 
221
        builder.add_node(('rey', ), 'data', ([('beference', ), ('aeference2', )], ))
227
222
        stream = builder.finish()
228
223
        contents = stream.read()
229
224
        self.assertEqual(
235
230
 
236
231
    def test_node_references_three_digits(self):
237
232
        # test the node digit expands as needed.
238
 
        builder = index.GraphIndexBuilder(reference_lists=1)
 
233
        builder = GraphIndexBuilder(reference_lists=1)
239
234
        references = [(str(val), ) for val in reversed(range(9))]
240
235
        builder.add_node(('2-key', ), '', (references, ))
241
236
        stream = builder.finish()
257
252
    def test_absent_has_no_reference_overhead(self):
258
253
        # the offsets after an absent record should be correct when there are
259
254
        # >1 reference lists.
260
 
        builder = index.GraphIndexBuilder(reference_lists=2)
 
255
        builder = GraphIndexBuilder(reference_lists=2)
261
256
        builder.add_node(('parent', ), '', ([('aail', ), ('zther', )], []))
262
257
        stream = builder.finish()
263
258
        contents = stream.read()
269
264
            "\n", contents)
270
265
 
271
266
    def test_add_node_bad_key(self):
272
 
        builder = index.GraphIndexBuilder()
 
267
        builder = GraphIndexBuilder()
273
268
        for bad_char in '\t\n\x0b\x0c\r\x00 ':
274
269
            self.assertRaises(errors.BadIndexKey, builder.add_node,
275
270
                ('a%skey' % bad_char, ), 'data')
284
279
        self.assertRaises(errors.BadIndexKey, builder.add_node,
285
280
                ('primary', 'secondary'), 'data')
286
281
        # secondary key elements get checked too:
287
 
        builder = index.GraphIndexBuilder(key_elements=2)
 
282
        builder = GraphIndexBuilder(key_elements=2)
288
283
        for bad_char in '\t\n\x0b\x0c\r\x00 ':
289
284
            self.assertRaises(errors.BadIndexKey, builder.add_node,
290
285
                ('prefix', 'a%skey' % bad_char), 'data')
291
286
 
292
287
    def test_add_node_bad_data(self):
293
 
        builder = index.GraphIndexBuilder()
 
288
        builder = GraphIndexBuilder()
294
289
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
295
290
            'data\naa')
296
291
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
297
292
            'data\x00aa')
298
293
 
299
294
    def test_add_node_bad_mismatched_ref_lists_length(self):
300
 
        builder = index.GraphIndexBuilder()
 
295
        builder = GraphIndexBuilder()
301
296
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
302
297
            'data aa', ([], ))
303
 
        builder = index.GraphIndexBuilder(reference_lists=1)
 
298
        builder = GraphIndexBuilder(reference_lists=1)
304
299
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
305
300
            'data aa')
306
301
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
307
302
            'data aa', (), )
308
303
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
309
304
            'data aa', ([], []))
310
 
        builder = index.GraphIndexBuilder(reference_lists=2)
 
305
        builder = GraphIndexBuilder(reference_lists=2)
311
306
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
312
307
            'data aa')
313
308
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
317
312
 
318
313
    def test_add_node_bad_key_in_reference_lists(self):
319
314
        # first list, first key - trivial
320
 
        builder = index.GraphIndexBuilder(reference_lists=1)
 
315
        builder = GraphIndexBuilder(reference_lists=1)
321
316
        self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
322
317
            'data aa', ([('a key', )], ))
323
318
        # references keys must be tuples too
334
329
            'data aa', ([('agoodkey', ), ('that is a bad key', )], ))
335
330
        # and if there is more than one list it should be getting checked
336
331
        # too
337
 
        builder = index.GraphIndexBuilder(reference_lists=2)
 
332
        builder = GraphIndexBuilder(reference_lists=2)
338
333
        self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
339
334
            'data aa', ([], ['a bad key']))
340
335
 
341
336
    def test_add_duplicate_key(self):
342
 
        builder = index.GraphIndexBuilder()
 
337
        builder = GraphIndexBuilder()
343
338
        builder.add_node(('key', ), 'data')
344
 
        self.assertRaises(errors.BadIndexDuplicateKey,
345
 
                          builder.add_node, ('key', ), 'data')
 
339
        self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node, ('key', ),
 
340
            'data')
346
341
 
347
342
    def test_add_duplicate_key_2_elements(self):
348
 
        builder = index.GraphIndexBuilder(key_elements=2)
 
343
        builder = GraphIndexBuilder(key_elements=2)
349
344
        builder.add_node(('key', 'key'), 'data')
350
345
        self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node,
351
346
            ('key', 'key'), 'data')
352
347
 
353
348
    def test_add_key_after_referencing_key(self):
354
 
        builder = index.GraphIndexBuilder(reference_lists=1)
 
349
        builder = GraphIndexBuilder(reference_lists=1)
355
350
        builder.add_node(('key', ), 'data', ([('reference', )], ))
356
351
        builder.add_node(('reference', ), 'data', ([],))
357
352
 
358
353
    def test_add_key_after_referencing_key_2_elements(self):
359
 
        builder = index.GraphIndexBuilder(reference_lists=1, key_elements=2)
 
354
        builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
360
355
        builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
361
356
        builder.add_node(('reference', 'tokey'), 'data', ([],))
362
357
 
363
358
    def test_set_optimize(self):
364
 
        builder = index.GraphIndexBuilder(reference_lists=1, key_elements=2)
 
359
        builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
365
360
        builder.set_optimize(for_size=True)
366
361
        self.assertTrue(builder._optimize_for_size)
367
362
        builder.set_optimize(for_size=False)
368
363
        self.assertFalse(builder._optimize_for_size)
369
364
 
370
365
 
371
 
class TestGraphIndex(tests.TestCaseWithMemoryTransport):
 
366
class TestGraphIndex(TestCaseWithMemoryTransport):
372
367
 
373
368
    def make_key(self, number):
374
369
        return (str(number) + 'X'*100,)
385
380
        return nodes
386
381
 
387
382
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
388
 
        builder = index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
 
383
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
389
384
        for key, value, references in nodes:
390
385
            builder.add_node(key, value, references)
391
386
        stream = builder.finish()
392
 
        trans = transport.get_transport('trace+' + self.get_url())
 
387
        trans = get_transport('trace+' + self.get_url())
393
388
        size = trans.put_file('index', stream)
394
 
        return index.GraphIndex(trans, 'index', size)
395
 
 
396
 
    def make_index_with_offset(self, ref_lists=0, key_elements=1, nodes=[],
397
 
                               offset=0):
398
 
        builder = index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
399
 
        for key, value, references in nodes:
400
 
            builder.add_node(key, value, references)
401
 
        content = builder.finish().read()
402
 
        size = len(content)
403
 
        trans = self.get_transport()
404
 
        trans.put_bytes('index', (' '*offset) + content)
405
 
        return index.GraphIndex(trans, 'index', size, offset=offset)
 
389
        return GraphIndex(trans, 'index', size)
406
390
 
407
391
    def test_clear_cache(self):
408
392
        index = self.make_index()
413
397
    def test_open_bad_index_no_error(self):
414
398
        trans = self.get_transport()
415
399
        trans.put_bytes('name', "not an index\n")
416
 
        idx = index.GraphIndex(trans, 'name', 13)
417
 
 
418
 
    def test_with_offset(self):
419
 
        nodes = self.make_nodes(200)
420
 
        idx = self.make_index_with_offset(offset=1234567, nodes=nodes)
421
 
        self.assertEqual(200, idx.key_count())
422
 
 
423
 
    def test_buffer_all_with_offset(self):
424
 
        nodes = self.make_nodes(200)
425
 
        idx = self.make_index_with_offset(offset=1234567, nodes=nodes)
426
 
        idx._buffer_all()
427
 
        self.assertEqual(200, idx.key_count())
428
 
 
429
 
    def test_side_effect_buffering_with_offset(self):
430
 
        nodes = self.make_nodes(20)
431
 
        index = self.make_index_with_offset(offset=1234567, nodes=nodes)
432
 
        index._transport.recommended_page_size = lambda:64*1024
433
 
        subset_nodes = [nodes[0][0], nodes[10][0], nodes[19][0]]
434
 
        entries = [n[1] for n in index.iter_entries(subset_nodes)]
435
 
        self.assertEqual(sorted(subset_nodes), sorted(entries))
436
 
        self.assertEqual(20, index.key_count())
 
400
        index = GraphIndex(trans, 'name', 13)
437
401
 
438
402
    def test_open_sets_parsed_map_empty(self):
439
403
        index = self.make_index()
835
799
        self.assertEqual([], list(index.iter_entries([('a', )])))
836
800
 
837
801
    def test_iter_missing_entry_empty_no_size(self):
838
 
        idx = self.make_index()
839
 
        idx = index.GraphIndex(idx._transport, 'index', None)
840
 
        self.assertEqual([], list(idx.iter_entries([('a', )])))
 
802
        index = self.make_index()
 
803
        index = GraphIndex(index._transport, 'index', None)
 
804
        self.assertEqual([], list(index.iter_entries([('a', )])))
841
805
 
842
806
    def test_iter_key_prefix_1_element_key_None(self):
843
807
        index = self.make_index()
933
897
    def test_validate_bad_index_errors(self):
934
898
        trans = self.get_transport()
935
899
        trans.put_bytes('name', "not an index\n")
936
 
        idx = index.GraphIndex(trans, 'name', 13)
937
 
        self.assertRaises(errors.BadIndexFormatSignature, idx.validate)
 
900
        index = GraphIndex(trans, 'name', 13)
 
901
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
938
902
 
939
903
    def test_validate_bad_node_refs(self):
940
 
        idx = self.make_index(2)
 
904
        index = self.make_index(2)
941
905
        trans = self.get_transport()
942
906
        content = trans.get_bytes('index')
943
907
        # change the options line to end with a rather than a parseable number
944
908
        new_content = content[:-2] + 'a\n\n'
945
909
        trans.put_bytes('index', new_content)
946
 
        self.assertRaises(errors.BadIndexOptions, idx.validate)
 
910
        self.assertRaises(errors.BadIndexOptions, index.validate)
947
911
 
948
912
    def test_validate_missing_end_line_empty(self):
949
913
        index = self.make_index(2)
1054
1018
        self.assertEqual(set(), search_keys)
1055
1019
 
1056
1020
    def test_supports_unlimited_cache(self):
1057
 
        builder = index.GraphIndexBuilder(0, key_elements=1)
 
1021
        builder = GraphIndexBuilder(0, key_elements=1)
1058
1022
        stream = builder.finish()
1059
 
        trans = transport.get_transport(self.get_url())
 
1023
        trans = get_transport(self.get_url())
1060
1024
        size = trans.put_file('index', stream)
1061
1025
        # It doesn't matter what unlimited_cache does here, just that it can be
1062
1026
        # passed
1063
 
        idx = index.GraphIndex(trans, 'index', size, unlimited_cache=True)
1064
 
 
1065
 
 
1066
 
class TestCombinedGraphIndex(tests.TestCaseWithMemoryTransport):
 
1027
        index = GraphIndex(trans, 'index', size, unlimited_cache=True)
 
1028
 
 
1029
 
 
1030
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
1067
1031
 
1068
1032
    def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
1069
 
        builder = index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
 
1033
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
1070
1034
        for key, value, references in nodes:
1071
1035
            builder.add_node(key, value, references)
1072
1036
        stream = builder.finish()
1073
1037
        trans = self.get_transport()
1074
1038
        size = trans.put_file(name, stream)
1075
 
        return index.GraphIndex(trans, name, size)
 
1039
        return GraphIndex(trans, name, size)
1076
1040
 
1077
1041
    def make_combined_index_with_missing(self, missing=['1', '2']):
1078
1042
        """Create a CombinedGraphIndex which will have missing indexes.
1084
1048
        :param missing: The underlying indexes to delete
1085
1049
        :return: (CombinedGraphIndex, reload_counter)
1086
1050
        """
1087
 
        idx1 = self.make_index('1', nodes=[(('1',), '', ())])
1088
 
        idx2 = self.make_index('2', nodes=[(('2',), '', ())])
1089
 
        idx3 = self.make_index('3', nodes=[
 
1051
        index1 = self.make_index('1', nodes=[(('1',), '', ())])
 
1052
        index2 = self.make_index('2', nodes=[(('2',), '', ())])
 
1053
        index3 = self.make_index('3', nodes=[
1090
1054
            (('1',), '', ()),
1091
1055
            (('2',), '', ())])
1092
1056
 
1094
1058
        reload_counter = [0, 0, 0]
1095
1059
        def reload():
1096
1060
            reload_counter[0] += 1
1097
 
            new_indices = [idx3]
1098
 
            if idx._indices == new_indices:
 
1061
            new_indices = [index3]
 
1062
            if index._indices == new_indices:
1099
1063
                reload_counter[2] += 1
1100
1064
                return False
1101
1065
            reload_counter[1] += 1
1102
 
            idx._indices[:] = new_indices
 
1066
            index._indices[:] = new_indices
1103
1067
            return True
1104
 
        idx = index.CombinedGraphIndex([idx1, idx2], reload_func=reload)
 
1068
        index = CombinedGraphIndex([index1, index2], reload_func=reload)
1105
1069
        trans = self.get_transport()
1106
1070
        for fname in missing:
1107
1071
            trans.delete(fname)
1108
 
        return idx, reload_counter
 
1072
        return index, reload_counter
1109
1073
 
1110
1074
    def test_open_missing_index_no_error(self):
1111
1075
        trans = self.get_transport()
1112
 
        idx1 = index.GraphIndex(trans, 'missing', 100)
1113
 
        idx = index.CombinedGraphIndex([idx1])
 
1076
        index1 = GraphIndex(trans, 'missing', 100)
 
1077
        index = CombinedGraphIndex([index1])
1114
1078
 
1115
1079
    def test_add_index(self):
1116
 
        idx = index.CombinedGraphIndex([])
1117
 
        idx1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1118
 
        idx.insert_index(0, idx1)
1119
 
        self.assertEqual([(idx1, ('key', ), '')],
1120
 
                         list(idx.iter_all_entries()))
 
1080
        index = CombinedGraphIndex([])
 
1081
        index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
 
1082
        index.insert_index(0, index1)
 
1083
        self.assertEqual([(index1, ('key', ), '')], list(index.iter_all_entries()))
1121
1084
 
1122
1085
    def test_clear_cache(self):
1123
1086
        log = []
1134
1097
                log.append(self._index)
1135
1098
                return self._index.clear_cache()
1136
1099
 
1137
 
        idx = index.CombinedGraphIndex([])
1138
 
        idx1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1139
 
        idx.insert_index(0, ClearCacheProxy(idx1))
1140
 
        idx2 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1141
 
        idx.insert_index(1, ClearCacheProxy(idx2))
 
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))
1142
1105
        # CombinedGraphIndex should call 'clear_cache()' on all children
1143
 
        idx.clear_cache()
1144
 
        self.assertEqual(sorted([idx1, idx2]), sorted(log))
 
1106
        index.clear_cache()
 
1107
        self.assertEqual(sorted([index1, index2]), sorted(log))
1145
1108
 
1146
1109
    def test_iter_all_entries_empty(self):
1147
 
        idx = index.CombinedGraphIndex([])
1148
 
        self.assertEqual([], list(idx.iter_all_entries()))
 
1110
        index = CombinedGraphIndex([])
 
1111
        self.assertEqual([], list(index.iter_all_entries()))
1149
1112
 
1150
1113
    def test_iter_all_entries_children_empty(self):
1151
 
        idx1 = self.make_index('name')
1152
 
        idx = index.CombinedGraphIndex([idx1])
1153
 
        self.assertEqual([], list(idx.iter_all_entries()))
 
1114
        index1 = self.make_index('name')
 
1115
        index = CombinedGraphIndex([index1])
 
1116
        self.assertEqual([], list(index.iter_all_entries()))
1154
1117
 
1155
1118
    def test_iter_all_entries_simple(self):
1156
 
        idx1 = self.make_index('name', nodes=[(('name', ), 'data', ())])
1157
 
        idx = index.CombinedGraphIndex([idx1])
1158
 
        self.assertEqual([(idx1, ('name', ), 'data')],
1159
 
            list(idx.iter_all_entries()))
 
1119
        index1 = self.make_index('name', nodes=[(('name', ), 'data', ())])
 
1120
        index = CombinedGraphIndex([index1])
 
1121
        self.assertEqual([(index1, ('name', ), 'data')],
 
1122
            list(index.iter_all_entries()))
1160
1123
 
1161
1124
    def test_iter_all_entries_two_indices(self):
1162
 
        idx1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1163
 
        idx2 = self.make_index('name2', nodes=[(('2', ), '', ())])
1164
 
        idx = index.CombinedGraphIndex([idx1, idx2])
1165
 
        self.assertEqual([(idx1, ('name', ), 'data'),
1166
 
                          (idx2, ('2', ), '')],
1167
 
                         list(idx.iter_all_entries()))
 
1125
        index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
 
1126
        index2 = self.make_index('name2', nodes=[(('2', ), '', ())])
 
1127
        index = CombinedGraphIndex([index1, index2])
 
1128
        self.assertEqual([(index1, ('name', ), 'data'),
 
1129
            (index2, ('2', ), '')],
 
1130
            list(index.iter_all_entries()))
1168
1131
 
1169
1132
    def test_iter_entries_two_indices_dup_key(self):
1170
 
        idx1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1171
 
        idx2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
1172
 
        idx = index.CombinedGraphIndex([idx1, idx2])
1173
 
        self.assertEqual([(idx1, ('name', ), 'data')],
1174
 
                         list(idx.iter_entries([('name', )])))
 
1133
        index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
 
1134
        index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
 
1135
        index = CombinedGraphIndex([index1, index2])
 
1136
        self.assertEqual([(index1, ('name', ), 'data')],
 
1137
            list(index.iter_entries([('name', )])))
1175
1138
 
1176
1139
    def test_iter_all_entries_two_indices_dup_key(self):
1177
 
        idx1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1178
 
        idx2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
1179
 
        idx = index.CombinedGraphIndex([idx1, idx2])
1180
 
        self.assertEqual([(idx1, ('name', ), 'data')],
1181
 
                         list(idx.iter_all_entries()))
 
1140
        index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
 
1141
        index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
 
1142
        index = CombinedGraphIndex([index1, index2])
 
1143
        self.assertEqual([(index1, ('name', ), 'data')],
 
1144
            list(index.iter_all_entries()))
1182
1145
 
1183
1146
    def test_iter_key_prefix_2_key_element_refs(self):
1184
 
        idx1 = self.make_index('1', 1, key_elements=2, nodes=[
1185
 
                (('name', 'fin1'), 'data', ([('ref', 'erence')], ))])
1186
 
        idx2 = self.make_index('2', 1, key_elements=2, nodes=[
1187
 
                (('name', 'fin2'), 'beta', ([], )),
1188
 
                (('ref', 'erence'), 'refdata', ([], ))])
1189
 
        idx = index.CombinedGraphIndex([idx1, idx2])
1190
 
        self.assertEqual(set([(idx1, ('name', 'fin1'), 'data',
1191
 
                               ((('ref', 'erence'),),)),
1192
 
                              (idx2, ('ref', 'erence'), 'refdata', ((), ))]),
1193
 
                         set(idx.iter_entries_prefix([('name', 'fin1'),
1194
 
                                                        ('ref', 'erence')])))
1195
 
        self.assertEqual(set([(idx1, ('name', 'fin1'), 'data',
1196
 
                               ((('ref', 'erence'),),)),
1197
 
                              (idx2, ('name', 'fin2'), 'beta', ((), ))]),
1198
 
                         set(idx.iter_entries_prefix([('name', None)])))
 
1147
        index1 = self.make_index('1', 1, key_elements=2, nodes=[
 
1148
            (('name', 'fin1'), 'data', ([('ref', 'erence')], ))])
 
1149
        index2 = self.make_index('2', 1, key_elements=2, nodes=[
 
1150
            (('name', 'fin2'), 'beta', ([], )),
 
1151
            (('ref', 'erence'), 'refdata', ([], ))])
 
1152
        index = CombinedGraphIndex([index1, index2])
 
1153
        self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
1154
            (index2, ('ref', 'erence'), 'refdata', ((), ))]),
 
1155
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
 
1156
        self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
1157
            (index2, ('name', 'fin2'), 'beta', ((), ))]),
 
1158
            set(index.iter_entries_prefix([('name', None)])))
1199
1159
 
1200
1160
    def test_iter_nothing_empty(self):
1201
 
        idx = index.CombinedGraphIndex([])
1202
 
        self.assertEqual([], list(idx.iter_entries([])))
 
1161
        index = CombinedGraphIndex([])
 
1162
        self.assertEqual([], list(index.iter_entries([])))
1203
1163
 
1204
1164
    def test_iter_nothing_children_empty(self):
1205
 
        idx1 = self.make_index('name')
1206
 
        idx = index.CombinedGraphIndex([idx1])
1207
 
        self.assertEqual([], list(idx.iter_entries([])))
 
1165
        index1 = self.make_index('name')
 
1166
        index = CombinedGraphIndex([index1])
 
1167
        self.assertEqual([], list(index.iter_entries([])))
1208
1168
 
1209
1169
    def test_iter_all_keys(self):
1210
 
        idx1 = self.make_index('1', 1, nodes=[(('name', ), 'data',
1211
 
                                               ([('ref', )], ))])
1212
 
        idx2 = self.make_index('2', 1, nodes=[(('ref', ), 'refdata', ((), ))])
1213
 
        idx = index.CombinedGraphIndex([idx1, idx2])
1214
 
        self.assertEqual(set([(idx1, ('name', ), 'data', ((('ref', ), ), )),
1215
 
                              (idx2, ('ref', ), 'refdata', ((), ))]),
1216
 
                         set(idx.iter_entries([('name', ), ('ref', )])))
 
1170
        index1 = self.make_index('1', 1, nodes=[
 
1171
            (('name', ), 'data', ([('ref', )], ))])
 
1172
        index2 = self.make_index('2', 1, nodes=[
 
1173
            (('ref', ), 'refdata', ((), ))])
 
1174
        index = CombinedGraphIndex([index1, index2])
 
1175
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),
 
1176
            (index2, ('ref', ), 'refdata', ((), ))]),
 
1177
            set(index.iter_entries([('name', ), ('ref', )])))
1217
1178
 
1218
1179
    def test_iter_all_keys_dup_entry(self):
1219
 
        idx1 = self.make_index('1', 1, nodes=[(('name', ), 'data',
1220
 
                                                 ([('ref', )], )),
1221
 
                                                (('ref', ), 'refdata', ([], ))])
1222
 
        idx2 = self.make_index('2', 1, nodes=[(('ref', ), 'refdata', ([], ))])
1223
 
        idx = index.CombinedGraphIndex([idx1, idx2])
1224
 
        self.assertEqual(set([(idx1, ('name', ), 'data', ((('ref',),),)),
1225
 
                              (idx1, ('ref', ), 'refdata', ((), ))]),
1226
 
                         set(idx.iter_entries([('name', ), ('ref', )])))
 
1180
        index1 = self.make_index('1', 1, nodes=[
 
1181
            (('name', ), 'data', ([('ref', )], )),
 
1182
            (('ref', ), 'refdata', ([], ))])
 
1183
        index2 = self.make_index('2', 1, nodes=[
 
1184
            (('ref', ), 'refdata', ([], ))])
 
1185
        index = CombinedGraphIndex([index1, index2])
 
1186
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),
 
1187
            (index1, ('ref', ), 'refdata', ((), ))]),
 
1188
            set(index.iter_entries([('name', ), ('ref', )])))
1227
1189
 
1228
1190
    def test_iter_missing_entry_empty(self):
1229
 
        idx = index.CombinedGraphIndex([])
1230
 
        self.assertEqual([], list(idx.iter_entries([('a', )])))
 
1191
        index = CombinedGraphIndex([])
 
1192
        self.assertEqual([], list(index.iter_entries([('a', )])))
1231
1193
 
1232
1194
    def test_iter_missing_entry_one_index(self):
1233
 
        idx1 = self.make_index('1')
1234
 
        idx = index.CombinedGraphIndex([idx1])
1235
 
        self.assertEqual([], list(idx.iter_entries([('a', )])))
 
1195
        index1 = self.make_index('1')
 
1196
        index = CombinedGraphIndex([index1])
 
1197
        self.assertEqual([], list(index.iter_entries([('a', )])))
1236
1198
 
1237
1199
    def test_iter_missing_entry_two_index(self):
1238
 
        idx1 = self.make_index('1')
1239
 
        idx2 = self.make_index('2')
1240
 
        idx = index.CombinedGraphIndex([idx1, idx2])
1241
 
        self.assertEqual([], list(idx.iter_entries([('a', )])))
 
1200
        index1 = self.make_index('1')
 
1201
        index2 = self.make_index('2')
 
1202
        index = CombinedGraphIndex([index1, index2])
 
1203
        self.assertEqual([], list(index.iter_entries([('a', )])))
1242
1204
 
1243
1205
    def test_iter_entry_present_one_index_only(self):
1244
 
        idx1 = self.make_index('1', nodes=[(('key', ), '', ())])
1245
 
        idx2 = self.make_index('2', nodes=[])
1246
 
        idx = index.CombinedGraphIndex([idx1, idx2])
1247
 
        self.assertEqual([(idx1, ('key', ), '')],
1248
 
                         list(idx.iter_entries([('key', )])))
 
1206
        index1 = self.make_index('1', nodes=[(('key', ), '', ())])
 
1207
        index2 = self.make_index('2', nodes=[])
 
1208
        index = CombinedGraphIndex([index1, index2])
 
1209
        self.assertEqual([(index1, ('key', ), '')],
 
1210
            list(index.iter_entries([('key', )])))
1249
1211
        # and in the other direction
1250
 
        idx = index.CombinedGraphIndex([idx2, idx1])
1251
 
        self.assertEqual([(idx1, ('key', ), '')],
1252
 
                         list(idx.iter_entries([('key', )])))
 
1212
        index = CombinedGraphIndex([index2, index1])
 
1213
        self.assertEqual([(index1, ('key', ), '')],
 
1214
            list(index.iter_entries([('key', )])))
1253
1215
 
1254
1216
    def test_key_count_empty(self):
1255
 
        idx1 = self.make_index('1', nodes=[])
1256
 
        idx2 = self.make_index('2', nodes=[])
1257
 
        idx = index.CombinedGraphIndex([idx1, idx2])
1258
 
        self.assertEqual(0, idx.key_count())
 
1217
        index1 = self.make_index('1', nodes=[])
 
1218
        index2 = self.make_index('2', nodes=[])
 
1219
        index = CombinedGraphIndex([index1, index2])
 
1220
        self.assertEqual(0, index.key_count())
1259
1221
 
1260
1222
    def test_key_count_sums_index_keys(self):
1261
 
        idx1 = self.make_index('1', nodes=[
 
1223
        index1 = self.make_index('1', nodes=[
1262
1224
            (('1',), '', ()),
1263
1225
            (('2',), '', ())])
1264
 
        idx2 = self.make_index('2', nodes=[(('1',), '', ())])
1265
 
        idx = index.CombinedGraphIndex([idx1, idx2])
1266
 
        self.assertEqual(3, idx.key_count())
 
1226
        index2 = self.make_index('2', nodes=[(('1',), '', ())])
 
1227
        index = CombinedGraphIndex([index1, index2])
 
1228
        self.assertEqual(3, index.key_count())
1267
1229
 
1268
1230
    def test_validate_bad_child_index_errors(self):
1269
1231
        trans = self.get_transport()
1270
1232
        trans.put_bytes('name', "not an index\n")
1271
 
        idx1 = index.GraphIndex(trans, 'name', 13)
1272
 
        idx = index.CombinedGraphIndex([idx1])
1273
 
        self.assertRaises(errors.BadIndexFormatSignature, idx.validate)
 
1233
        index1 = GraphIndex(trans, 'name', 13)
 
1234
        index = CombinedGraphIndex([index1])
 
1235
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
1274
1236
 
1275
1237
    def test_validate_empty(self):
1276
 
        idx = index.CombinedGraphIndex([])
1277
 
        idx.validate()
 
1238
        index = CombinedGraphIndex([])
 
1239
        index.validate()
1278
1240
 
1279
1241
    def test_key_count_reloads(self):
1280
 
        idx, reload_counter = self.make_combined_index_with_missing()
1281
 
        self.assertEqual(2, idx.key_count())
 
1242
        index, reload_counter = self.make_combined_index_with_missing()
 
1243
        self.assertEqual(2, index.key_count())
1282
1244
        self.assertEqual([1, 1, 0], reload_counter)
1283
1245
 
1284
1246
    def test_key_count_no_reload(self):
1285
 
        idx, reload_counter = self.make_combined_index_with_missing()
1286
 
        idx._reload_func = None
 
1247
        index, reload_counter = self.make_combined_index_with_missing()
 
1248
        index._reload_func = None
1287
1249
        # Without a _reload_func we just raise the exception
1288
 
        self.assertRaises(errors.NoSuchFile, idx.key_count)
 
1250
        self.assertRaises(errors.NoSuchFile, index.key_count)
1289
1251
 
1290
1252
    def test_key_count_reloads_and_fails(self):
1291
1253
        # We have deleted all underlying indexes, so we will try to reload, but
1292
1254
        # still fail. This is mostly to test we don't get stuck in an infinite
1293
1255
        # loop trying to reload
1294
 
        idx, reload_counter = self.make_combined_index_with_missing(
1295
 
            ['1', '2', '3'])
1296
 
        self.assertRaises(errors.NoSuchFile, idx.key_count)
 
1256
        index, reload_counter = self.make_combined_index_with_missing(
 
1257
                                    ['1', '2', '3'])
 
1258
        self.assertRaises(errors.NoSuchFile, index.key_count)
1297
1259
        self.assertEqual([2, 1, 1], reload_counter)
1298
1260
 
1299
1261
    def test_iter_entries_reloads(self):
1387
1349
        self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1388
1350
                                                 [('1',)])
1389
1351
 
1390
 
 
1391
 
    def make_index_with_simple_nodes(self, name, num_nodes=1):
1392
 
        """Make an index named after 'name', with keys named after 'name' too.
1393
 
 
1394
 
        Nodes will have a value of '' and no references.
1395
 
        """
1396
 
        nodes = [
1397
 
            (('index-%s-key-%s' % (name, n),), '', ())
1398
 
            for n in range(1, num_nodes+1)]
1399
 
        return self.make_index('index-%s' % name, 0, nodes=nodes)
1400
 
 
1401
 
    def test_reorder_after_iter_entries(self):
1402
 
        # Four indices: [key1] in idx1, [key2,key3] in idx2, [] in idx3,
1403
 
        # [key4] in idx4.
1404
 
        idx = index.CombinedGraphIndex([])
1405
 
        idx.insert_index(0, self.make_index_with_simple_nodes('1'), '1')
1406
 
        idx.insert_index(1, self.make_index_with_simple_nodes('2'), '2')
1407
 
        idx.insert_index(2, self.make_index_with_simple_nodes('3'), '3')
1408
 
        idx.insert_index(3, self.make_index_with_simple_nodes('4'), '4')
1409
 
        idx1, idx2, idx3, idx4 = idx._indices
1410
 
        # Query a key from idx4 and idx2.
1411
 
        self.assertLength(2, list(idx.iter_entries(
1412
 
            [('index-4-key-1',), ('index-2-key-1',)])))
1413
 
        # Now idx2 and idx4 should be moved to the front (and idx1 should
1414
 
        # still be before idx3).
1415
 
        self.assertEqual([idx2, idx4, idx1, idx3], idx._indices)
1416
 
        self.assertEqual(['2', '4', '1', '3'], idx._index_names)
1417
 
 
1418
 
    def test_reorder_propagates_to_siblings(self):
1419
 
        # Two CombinedGraphIndex objects, with the same number of indicies with
1420
 
        # matching names.
1421
 
        cgi1 = index.CombinedGraphIndex([])
1422
 
        cgi2 = index.CombinedGraphIndex([])
1423
 
        cgi1.insert_index(0, self.make_index_with_simple_nodes('1-1'), 'one')
1424
 
        cgi1.insert_index(1, self.make_index_with_simple_nodes('1-2'), 'two')
1425
 
        cgi2.insert_index(0, self.make_index_with_simple_nodes('2-1'), 'one')
1426
 
        cgi2.insert_index(1, self.make_index_with_simple_nodes('2-2'), 'two')
1427
 
        index2_1, index2_2 = cgi2._indices
1428
 
        cgi1.set_sibling_indices([cgi2])
1429
 
        # Trigger a reordering in cgi1.  cgi2 will be reordered as well.
1430
 
        list(cgi1.iter_entries([('index-1-2-key-1',)]))
1431
 
        self.assertEqual([index2_2, index2_1], cgi2._indices)
1432
 
        self.assertEqual(['two', 'one'], cgi2._index_names)
1433
 
 
1434
1352
    def test_validate_reloads(self):
1435
 
        idx, reload_counter = self.make_combined_index_with_missing()
1436
 
        idx.validate()
 
1353
        index, reload_counter = self.make_combined_index_with_missing()
 
1354
        index.validate()
1437
1355
        self.assertEqual([1, 1, 0], reload_counter)
1438
1356
 
1439
1357
    def test_validate_reloads_midway(self):
1440
 
        idx, reload_counter = self.make_combined_index_with_missing(['2'])
1441
 
        idx.validate()
 
1358
        index, reload_counter = self.make_combined_index_with_missing(['2'])
 
1359
        index.validate()
1442
1360
 
1443
1361
    def test_validate_no_reload(self):
1444
 
        idx, reload_counter = self.make_combined_index_with_missing()
1445
 
        idx._reload_func = None
1446
 
        self.assertRaises(errors.NoSuchFile, idx.validate)
 
1362
        index, reload_counter = self.make_combined_index_with_missing()
 
1363
        index._reload_func = None
 
1364
        self.assertRaises(errors.NoSuchFile, index.validate)
1447
1365
 
1448
1366
    def test_validate_reloads_and_fails(self):
1449
 
        idx, reload_counter = self.make_combined_index_with_missing(
1450
 
            ['1', '2', '3'])
1451
 
        self.assertRaises(errors.NoSuchFile, idx.validate)
 
1367
        index, reload_counter = self.make_combined_index_with_missing(
 
1368
                                    ['1', '2', '3'])
 
1369
        self.assertRaises(errors.NoSuchFile, index.validate)
1452
1370
 
1453
1371
    def test_find_ancestors_across_indexes(self):
1454
1372
        key1 = ('key-1',)
1463
1381
            (key3, 'value', ([key2],)),
1464
1382
            (key4, 'value', ([key3],)),
1465
1383
            ])
1466
 
        c_index = index.CombinedGraphIndex([index1, index2])
 
1384
        c_index = CombinedGraphIndex([index1, index2])
1467
1385
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1468
1386
        self.assertEqual({key1: ()}, parent_map)
1469
1387
        self.assertEqual(set(), missing_keys)
1486
1404
        index2 = self.make_index('34', ref_lists=1, nodes=[
1487
1405
            (key3, 'value', ([key2],)),
1488
1406
            ])
1489
 
        c_index = index.CombinedGraphIndex([index1, index2])
 
1407
        c_index = CombinedGraphIndex([index1, index2])
1490
1408
        # Searching for a key which is actually not present at all should
1491
1409
        # eventually converge
1492
1410
        parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1494
1412
        self.assertEqual(set([key4]), missing_keys)
1495
1413
 
1496
1414
    def test_find_ancestors_no_indexes(self):
1497
 
        c_index = index.CombinedGraphIndex([])
 
1415
        c_index = CombinedGraphIndex([])
1498
1416
        key1 = ('key-1',)
1499
1417
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1500
1418
        self.assertEqual({}, parent_map)
1512
1430
        index2 = self.make_index('34', ref_lists=1, nodes=[
1513
1431
            (key4, 'value', ([key2, key3],)),
1514
1432
            ])
1515
 
        c_index = index.CombinedGraphIndex([index1, index2])
 
1433
        c_index = CombinedGraphIndex([index1, index2])
1516
1434
        # Searching for a key which is actually not present at all should
1517
1435
        # eventually converge
1518
1436
        parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1521
1439
        self.assertEqual(set([key3]), missing_keys)
1522
1440
 
1523
1441
    def test__find_ancestors_empty_index(self):
1524
 
        idx = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
 
1442
        index = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
1525
1443
        parent_map = {}
1526
1444
        missing_keys = set()
1527
 
        search_keys = idx._find_ancestors([('one',), ('two',)], 0, parent_map,
1528
 
                                          missing_keys)
 
1445
        search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
 
1446
                                            missing_keys)
1529
1447
        self.assertEqual(set(), search_keys)
1530
1448
        self.assertEqual({}, parent_map)
1531
1449
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
1532
1450
 
1533
1451
 
1534
 
class TestInMemoryGraphIndex(tests.TestCaseWithMemoryTransport):
 
1452
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
1535
1453
 
1536
1454
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
1537
 
        result = index.InMemoryGraphIndex(ref_lists, key_elements=key_elements)
 
1455
        result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1538
1456
        result.add_nodes(nodes)
1539
1457
        return result
1540
1458
 
1661
1579
        index.validate()
1662
1580
 
1663
1581
 
1664
 
class TestGraphIndexPrefixAdapter(tests.TestCaseWithMemoryTransport):
 
1582
class TestGraphIndexPrefixAdapter(TestCaseWithMemoryTransport):
1665
1583
 
1666
 
    def make_index(self, ref_lists=1, key_elements=2, nodes=[],
1667
 
                   add_callback=False):
1668
 
        result = index.InMemoryGraphIndex(ref_lists, key_elements=key_elements)
 
1584
    def make_index(self, ref_lists=1, key_elements=2, nodes=[], add_callback=False):
 
1585
        result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1669
1586
        result.add_nodes(nodes)
1670
1587
        if add_callback:
1671
1588
            add_nodes_callback = result.add_nodes
1672
1589
        else:
1673
1590
            add_nodes_callback = None
1674
 
        adapter = index.GraphIndexPrefixAdapter(
1675
 
            result, ('prefix', ), key_elements - 1,
 
1591
        adapter = GraphIndexPrefixAdapter(result, ('prefix', ), key_elements - 1,
1676
1592
            add_nodes_callback=add_nodes_callback)
1677
1593
        return result, adapter
1678
1594
 
1679
1595
    def test_add_node(self):
1680
1596
        index, adapter = self.make_index(add_callback=True)
1681
1597
        adapter.add_node(('key',), 'value', ((('ref',),),))
1682
 
        self.assertEqual(set([(index, ('prefix', 'key'), 'value',
1683
 
                               ((('prefix', 'ref'),),))]),
 
1598
        self.assertEqual(set([(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))]),
1684
1599
            set(index.iter_all_entries()))
1685
1600
 
1686
1601
    def test_add_nodes(self):
1696
1611
            set(index.iter_all_entries()))
1697
1612
 
1698
1613
    def test_construct(self):
1699
 
        idx = index.InMemoryGraphIndex()
1700
 
        adapter = index.GraphIndexPrefixAdapter(idx, ('prefix', ), 1)
 
1614
        index = InMemoryGraphIndex()
 
1615
        adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1)
1701
1616
 
1702
1617
    def test_construct_with_callback(self):
1703
 
        idx = index.InMemoryGraphIndex()
1704
 
        adapter = index.GraphIndexPrefixAdapter(idx, ('prefix', ), 1,
1705
 
                                                idx.add_nodes)
 
1618
        index = InMemoryGraphIndex()
 
1619
        adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1, index.add_nodes)
1706
1620
 
1707
1621
    def test_iter_all_entries_cross_prefix_map_errors(self):
1708
1622
        index, adapter = self.make_index(nodes=[