← 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: Vincent Ladeuil
  • Date: 2012-01-18 14:09:19 UTC
  • mto: This revision was merged to the branch mainline in revision 6468.
  • Revision ID: v.ladeuil+lp@free.fr-20120118140919-rlvdrhpc0nq1lbwi
Change set/remove to require a lock for the branch config files.

This means that tests (or any plugin for that matter) do not requires an
explicit lock on the branch anymore to change a single option. This also
means the optimisation becomes "opt-in" and as such won't be as
spectacular as it may be and/or harder to get right (nothing fails
anymore).

This reduces the diff by ~300 lines.

Code/tests that were updating more than one config option is still taking
a lock to at least avoid some IOs and demonstrate the benefits through
the decreased number of hpss calls.

The duplication between BranchStack and BranchOnlyStack will be removed
once the same sharing is in place for local config files, at which point
the Stack class itself may be able to host the changes.

Show diffs side-by-side

added added

removed removed

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