← 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: Canonical.com Patch Queue Manager
  • Date: 2008-03-16 16:58:03 UTC
  • mfrom: (3224.3.1 news-typo)
  • Revision ID: pqm@pqm.ubuntu.com-20080316165803-tisoc9mpob9z544o
(Matt Nordhoff) Trivial NEWS typo fix

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 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
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()
175
173
            "key\x00\x00\t\x00data\n"
176
174
            "\n", contents)
177
175
 
178
 
    def test_clear_cache(self):
179
 
        builder = index.GraphIndexBuilder(reference_lists=2)
180
 
        # This is a no-op, but the api should exist
181
 
        builder.clear_cache()
182
 
 
183
176
    def test_node_references_are_byte_offsets(self):
184
 
        builder = index.GraphIndexBuilder(reference_lists=1)
 
177
        builder = GraphIndexBuilder(reference_lists=1)
185
178
        builder.add_node(('reference', ), 'data', ([], ))
186
179
        builder.add_node(('key', ), 'data', ([('reference', )], ))
187
180
        stream = builder.finish()
193
186
            "\n", contents)
194
187
 
195
188
    def test_node_references_are_cr_delimited(self):
196
 
        builder = index.GraphIndexBuilder(reference_lists=1)
 
189
        builder = GraphIndexBuilder(reference_lists=1)
197
190
        builder.add_node(('reference', ), 'data', ([], ))
198
191
        builder.add_node(('reference2', ), 'data', ([], ))
199
 
        builder.add_node(('key', ), 'data',
200
 
                         ([('reference', ), ('reference2', )], ))
 
192
        builder.add_node(('key', ), 'data', ([('reference', ), ('reference2', )], ))
201
193
        stream = builder.finish()
202
194
        contents = stream.read()
203
195
        self.assertEqual(
208
200
            "\n", contents)
209
201
 
210
202
    def test_multiple_reference_lists_are_tab_delimited(self):
211
 
        builder = index.GraphIndexBuilder(reference_lists=2)
 
203
        builder = GraphIndexBuilder(reference_lists=2)
212
204
        builder.add_node(('keference', ), 'data', ([], []))
213
 
        builder.add_node(('rey', ), 'data',
214
 
                         ([('keference', )], [('keference', )]))
 
205
        builder.add_node(('rey', ), 'data', ([('keference', )], [('keference', )]))
215
206
        stream = builder.finish()
216
207
        contents = stream.read()
217
208
        self.assertEqual(
221
212
            "\n", contents)
222
213
 
223
214
    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', )], ))
 
215
        builder = GraphIndexBuilder(reference_lists=1)
 
216
        builder.add_node(('rey', ), 'data', ([('beference', ), ('aeference2', )], ))
227
217
        stream = builder.finish()
228
218
        contents = stream.read()
229
219
        self.assertEqual(
235
225
 
236
226
    def test_node_references_three_digits(self):
237
227
        # test the node digit expands as needed.
238
 
        builder = index.GraphIndexBuilder(reference_lists=1)
 
228
        builder = GraphIndexBuilder(reference_lists=1)
239
229
        references = [(str(val), ) for val in reversed(range(9))]
240
230
        builder.add_node(('2-key', ), '', (references, ))
241
231
        stream = builder.finish()
242
232
        contents = stream.read()
243
 
        self.assertEqualDiff(
 
233
        self.assertEqual(
244
234
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
245
235
            "0\x00a\x00\x00\n"
246
236
            "1\x00a\x00\x00\n"
257
247
    def test_absent_has_no_reference_overhead(self):
258
248
        # the offsets after an absent record should be correct when there are
259
249
        # >1 reference lists.
260
 
        builder = index.GraphIndexBuilder(reference_lists=2)
 
250
        builder = GraphIndexBuilder(reference_lists=2)
261
251
        builder.add_node(('parent', ), '', ([('aail', ), ('zther', )], []))
262
252
        stream = builder.finish()
263
253
        contents = stream.read()
269
259
            "\n", contents)
270
260
 
271
261
    def test_add_node_bad_key(self):
272
 
        builder = index.GraphIndexBuilder()
 
262
        builder = GraphIndexBuilder()
273
263
        for bad_char in '\t\n\x0b\x0c\r\x00 ':
274
264
            self.assertRaises(errors.BadIndexKey, builder.add_node,
275
265
                ('a%skey' % bad_char, ), 'data')
284
274
        self.assertRaises(errors.BadIndexKey, builder.add_node,
285
275
                ('primary', 'secondary'), 'data')
286
276
        # secondary key elements get checked too:
287
 
        builder = index.GraphIndexBuilder(key_elements=2)
 
277
        builder = GraphIndexBuilder(key_elements=2)
288
278
        for bad_char in '\t\n\x0b\x0c\r\x00 ':
289
279
            self.assertRaises(errors.BadIndexKey, builder.add_node,
290
280
                ('prefix', 'a%skey' % bad_char), 'data')
291
281
 
292
282
    def test_add_node_bad_data(self):
293
 
        builder = index.GraphIndexBuilder()
 
283
        builder = GraphIndexBuilder()
294
284
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
295
285
            'data\naa')
296
286
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
297
287
            'data\x00aa')
298
288
 
299
289
    def test_add_node_bad_mismatched_ref_lists_length(self):
300
 
        builder = index.GraphIndexBuilder()
 
290
        builder = GraphIndexBuilder()
301
291
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
302
292
            'data aa', ([], ))
303
 
        builder = index.GraphIndexBuilder(reference_lists=1)
 
293
        builder = GraphIndexBuilder(reference_lists=1)
304
294
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
305
295
            'data aa')
306
296
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
307
297
            'data aa', (), )
308
298
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
309
299
            'data aa', ([], []))
310
 
        builder = index.GraphIndexBuilder(reference_lists=2)
 
300
        builder = GraphIndexBuilder(reference_lists=2)
311
301
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
312
302
            'data aa')
313
303
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
317
307
 
318
308
    def test_add_node_bad_key_in_reference_lists(self):
319
309
        # first list, first key - trivial
320
 
        builder = index.GraphIndexBuilder(reference_lists=1)
 
310
        builder = GraphIndexBuilder(reference_lists=1)
321
311
        self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
322
312
            'data aa', ([('a key', )], ))
323
313
        # references keys must be tuples too
334
324
            'data aa', ([('agoodkey', ), ('that is a bad key', )], ))
335
325
        # and if there is more than one list it should be getting checked
336
326
        # too
337
 
        builder = index.GraphIndexBuilder(reference_lists=2)
 
327
        builder = GraphIndexBuilder(reference_lists=2)
338
328
        self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
339
329
            'data aa', ([], ['a bad key']))
340
330
 
341
331
    def test_add_duplicate_key(self):
342
 
        builder = index.GraphIndexBuilder()
 
332
        builder = GraphIndexBuilder()
343
333
        builder.add_node(('key', ), 'data')
344
 
        self.assertRaises(errors.BadIndexDuplicateKey,
345
 
                          builder.add_node, ('key', ), 'data')
 
334
        self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node, ('key', ),
 
335
            'data')
346
336
 
347
337
    def test_add_duplicate_key_2_elements(self):
348
 
        builder = index.GraphIndexBuilder(key_elements=2)
 
338
        builder = GraphIndexBuilder(key_elements=2)
349
339
        builder.add_node(('key', 'key'), 'data')
350
340
        self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node,
351
341
            ('key', 'key'), 'data')
352
342
 
353
343
    def test_add_key_after_referencing_key(self):
354
 
        builder = index.GraphIndexBuilder(reference_lists=1)
 
344
        builder = GraphIndexBuilder(reference_lists=1)
355
345
        builder.add_node(('key', ), 'data', ([('reference', )], ))
356
346
        builder.add_node(('reference', ), 'data', ([],))
357
347
 
358
348
    def test_add_key_after_referencing_key_2_elements(self):
359
 
        builder = index.GraphIndexBuilder(reference_lists=1, key_elements=2)
 
349
        builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
360
350
        builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
361
351
        builder.add_node(('reference', 'tokey'), 'data', ([],))
362
352
 
363
 
    def test_set_optimize(self):
364
 
        builder = index.GraphIndexBuilder(reference_lists=1, key_elements=2)
365
 
        builder.set_optimize(for_size=True)
366
 
        self.assertTrue(builder._optimize_for_size)
367
 
        builder.set_optimize(for_size=False)
368
 
        self.assertFalse(builder._optimize_for_size)
369
 
 
370
 
 
371
 
class TestGraphIndex(tests.TestCaseWithMemoryTransport):
372
 
 
373
 
    def make_key(self, number):
374
 
        return (str(number) + 'X'*100,)
375
 
 
376
 
    def make_value(self, number):
377
 
            return str(number) + 'Y'*100
378
 
 
379
 
    def make_nodes(self, count=64):
380
 
        # generate a big enough index that we only read some of it on a typical
381
 
        # bisection lookup.
382
 
        nodes = []
383
 
        for counter in range(count):
384
 
            nodes.append((self.make_key(counter), self.make_value(counter), ()))
385
 
        return nodes
 
353
 
 
354
class TestGraphIndex(TestCaseWithMemoryTransport):
386
355
 
387
356
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
388
 
        builder = index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
 
357
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
389
358
        for key, value, references in nodes:
390
359
            builder.add_node(key, value, references)
391
360
        stream = builder.finish()
392
 
        trans = transport.get_transport_from_url('trace+' + self.get_url())
 
361
        trans = get_transport('trace+' + self.get_url())
393
362
        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)
406
 
 
407
 
    def test_clear_cache(self):
408
 
        index = self.make_index()
409
 
        # For now, we just want to make sure the api is available. As this is
410
 
        # old code, we don't really worry if it *does* anything.
411
 
        index.clear_cache()
 
363
        return GraphIndex(trans, 'index', size)
412
364
 
413
365
    def test_open_bad_index_no_error(self):
414
366
        trans = self.get_transport()
415
367
        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())
 
368
        index = GraphIndex(trans, 'name', 13)
437
369
 
438
370
    def test_open_sets_parsed_map_empty(self):
439
371
        index = self.make_index()
440
372
        self.assertEqual([], index._parsed_byte_map)
441
373
        self.assertEqual([], index._parsed_key_map)
442
374
 
443
 
    def test_key_count_buffers(self):
444
 
        index = self.make_index(nodes=self.make_nodes(2))
445
 
        # reset the transport log
446
 
        del index._transport._activity[:]
447
 
        self.assertEqual(2, index.key_count())
448
 
        # We should have requested reading the header bytes
449
 
        self.assertEqual([
450
 
            ('readv', 'index', [(0, 200)], True, index._size),
451
 
            ],
452
 
            index._transport._activity)
453
 
        # And that should have been enough to trigger reading the whole index
454
 
        # with buffering
455
 
        self.assertIsNot(None, index._nodes)
456
 
 
457
 
    def test_lookup_key_via_location_buffers(self):
 
375
    def test_first_lookup_key_via_location(self):
458
376
        index = self.make_index()
459
377
        # reset the transport log
460
378
        del index._transport._activity[:]
472
390
        # is a trivial index.
473
391
        self.assertEqual([((index._size // 2, ('missing', )), False)],
474
392
            result)
475
 
        # And this should have caused the file to be fully buffered
476
 
        self.assertIsNot(None, index._nodes)
477
 
        self.assertEqual([], index._parsed_byte_map)
 
393
        # And the regions of the file that have been parsed - in this case the
 
394
        # entire file - should be in the parsed region map.
 
395
        self.assertEqual([(0, 60)], index._parsed_byte_map)
 
396
        self.assertEqual([(None, None)], index._parsed_key_map)
478
397
 
479
 
    def test_first_lookup_key_via_location(self):
480
 
        # We need enough data so that the _HEADER_READV doesn't consume the
481
 
        # whole file. We always read 800 bytes for every key, and the local
482
 
        # transport natural expansion is 4096 bytes. So we have to have >8192
483
 
        # bytes or we will trigger "buffer_all".
484
 
        # We also want the 'missing' key to fall within the range that *did*
485
 
        # read
486
 
        nodes = []
487
 
        index = self.make_index(nodes=self.make_nodes(64))
 
398
    def test_parsing_parses_data_adjacent_to_parsed_regions(self):
 
399
        # we trim data we recieve to remove the first and trailing
 
400
        # partial lines, except when they start at the end/finish at the start
 
401
        # of a region we've alread parsed/ the end of the file. The trivial
 
402
        # test for this is an index with 1 key.
 
403
        index = self.make_index(nodes=[(('name', ), 'data', ())])
488
404
        # reset the transport log
489
405
        del index._transport._activity[:]
490
 
        # do a _lookup_keys_via_location call for the middle of the file, which
491
 
        # is what bisection uses.
492
 
        start_lookup = index._size // 2
493
406
        result = index._lookup_keys_via_location(
494
 
            [(start_lookup, ('40missing', ))])
 
407
            [(index._size // 2, ('missing', ))])
495
408
        # this should have asked for a readv request, with adjust_for_latency,
496
409
        # and two regions: the header, and half-way into the file.
497
410
        self.assertEqual([
498
 
            ('readv', 'index',
499
 
             [(start_lookup, 800), (0, 200)], True, index._size),
 
411
            ('readv', 'index', [(36, 36), (0, 200)], True, 72),
500
412
            ],
501
413
            index._transport._activity)
502
414
        # and the result should be that the key cannot be present, because this
503
 
        # is a trivial index.
504
 
        self.assertEqual([((start_lookup, ('40missing', )), False)],
 
415
        # is a trivial index and we should not have to do more round trips.
 
416
        self.assertEqual([((index._size // 2, ('missing', )), False)],
505
417
            result)
506
 
        # And this should not have caused the file to be fully buffered
507
 
        self.assertIs(None, index._nodes)
508
 
        # And the regions of the file that have been parsed should be in the
509
 
        # parsed_byte_map and the parsed_key_map
510
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
511
 
        self.assertEqual([(None, self.make_key(26)),
512
 
                          (self.make_key(31), self.make_key(48))],
513
 
                         index._parsed_key_map)
 
418
        # The whole file should be parsed at this point.
 
419
        self.assertEqual([(0, 72)], index._parsed_byte_map)
 
420
        self.assertEqual([(None, ('name',))], index._parsed_key_map)
514
421
 
515
422
    def test_parsing_non_adjacent_data_trims(self):
516
 
        index = self.make_index(nodes=self.make_nodes(64))
 
423
        # generate a big enough index that we only read some of it on a typical
 
424
        # bisection lookup.
 
425
        nodes = []
 
426
        def make_key(number):
 
427
            return (str(number) + 'X'*100,)
 
428
        for counter in range(64):
 
429
            nodes.append((make_key(counter), 'Y'*100, ()))
 
430
        index = self.make_index(nodes=nodes)
517
431
        result = index._lookup_keys_via_location(
518
432
            [(index._size // 2, ('40', ))])
519
433
        # and the result should be that the key cannot be present, because key is
523
437
            result)
524
438
        # and we should have a parse map that includes the header and the
525
439
        # region that was parsed after trimming.
526
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
527
 
        self.assertEqual([(None, self.make_key(26)),
528
 
                          (self.make_key(31), self.make_key(48))],
 
440
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
 
441
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
529
442
            index._parsed_key_map)
530
443
 
531
444
    def test_parsing_data_handles_parsed_contained_regions(self):
535
448
        # which then trims the start and end so the parsed size is < readv
536
449
        # miniumum.
537
450
        # then a dual lookup (or a reference lookup for that matter) which
538
 
        # abuts or overlaps the parsed region on both sides will need to
 
451
        # abuts or overlaps the parsed region on both sides will need to 
539
452
        # discard the data in the middle, but parse the end as well.
540
453
        #
541
 
        # we test this by doing a single lookup to seed the data, then
542
 
        # a lookup for two keys that are present, and adjacent -
 
454
        # we test this by doing a single lookup to seed the data, then 
 
455
        # a lookup for two keys that are present, and adjacent - 
543
456
        # we except both to be found, and the parsed byte map to include the
544
457
        # locations of both keys.
545
 
        index = self.make_index(nodes=self.make_nodes(128))
 
458
        nodes = []
 
459
        def make_key(number):
 
460
            return (str(number) + 'X'*100,)
 
461
        def make_value(number):
 
462
            return 'Y'*100
 
463
        for counter in range(128):
 
464
            nodes.append((make_key(counter), make_value(counter), ()))
 
465
        index = self.make_index(nodes=nodes)
546
466
        result = index._lookup_keys_via_location(
547
467
            [(index._size // 2, ('40', ))])
548
468
        # and we should have a parse map that includes the header and the
549
469
        # region that was parsed after trimming.
550
 
        self.assertEqual([(0, 4045), (11759, 15707)], index._parsed_byte_map)
551
 
        self.assertEqual([(None, self.make_key(116)),
552
 
                          (self.make_key(35), self.make_key(51))],
 
470
        self.assertEqual([(0, 3991), (11622, 15534)], index._parsed_byte_map)
 
471
        self.assertEqual([(None, make_key(116)), (make_key(35), make_key(51))],
553
472
            index._parsed_key_map)
554
473
        # now ask for two keys, right before and after the parsed region
555
474
        result = index._lookup_keys_via_location(
556
 
            [(11450, self.make_key(34)), (15707, self.make_key(52))])
 
475
            [(11450, make_key(34)), (15534, make_key(52))])
557
476
        self.assertEqual([
558
 
            ((11450, self.make_key(34)),
559
 
             (index, self.make_key(34), self.make_value(34))),
560
 
            ((15707, self.make_key(52)),
561
 
             (index, self.make_key(52), self.make_value(52))),
 
477
            ((11450, make_key(34)), (index, make_key(34), make_value(34))),
 
478
            ((15534, make_key(52)), (index, make_key(52), make_value(52))),
562
479
            ],
563
480
            result)
564
 
        self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)
 
481
        self.assertEqual([(0, 3991), (9975, 17799)], index._parsed_byte_map)
565
482
 
566
483
    def test_lookup_missing_key_answers_without_io_when_map_permits(self):
567
484
        # generate a big enough index that we only read some of it on a typical
568
485
        # bisection lookup.
569
 
        index = self.make_index(nodes=self.make_nodes(64))
 
486
        nodes = []
 
487
        def make_key(number):
 
488
            return (str(number) + 'X'*100,)
 
489
        for counter in range(64):
 
490
            nodes.append((make_key(counter), 'Y'*100, ()))
 
491
        index = self.make_index(nodes=nodes)
570
492
        # lookup the keys in the middle of the file
571
493
        result =index._lookup_keys_via_location(
572
494
            [(index._size // 2, ('40', ))])
573
495
        # check the parse map, this determines the test validity
574
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
575
 
        self.assertEqual([(None, self.make_key(26)),
576
 
                          (self.make_key(31), self.make_key(48))],
 
496
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
 
497
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
577
498
            index._parsed_key_map)
578
499
        # reset the transport log
579
500
        del index._transport._activity[:]
581
502
        # not create a new transport request, and should return False (cannot
582
503
        # be in the index) - even when the byte location we ask for is outside
583
504
        # the parsed region
 
505
        # 
584
506
        result = index._lookup_keys_via_location(
585
507
            [(4000, ('40', ))])
586
508
        self.assertEqual([((4000, ('40', )), False)],
590
512
    def test_lookup_present_key_answers_without_io_when_map_permits(self):
591
513
        # generate a big enough index that we only read some of it on a typical
592
514
        # bisection lookup.
593
 
        index = self.make_index(nodes=self.make_nodes(64))
 
515
        nodes = []
 
516
        def make_key(number):
 
517
            return (str(number) + 'X'*100,)
 
518
        def make_value(number):
 
519
            return str(number) + 'Y'*100
 
520
        for counter in range(64):
 
521
            nodes.append((make_key(counter), make_value(counter), ()))
 
522
        index = self.make_index(nodes=nodes)
594
523
        # lookup the keys in the middle of the file
595
524
        result =index._lookup_keys_via_location(
596
525
            [(index._size // 2, ('40', ))])
597
526
        # check the parse map, this determines the test validity
598
527
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
599
 
        self.assertEqual([(None, self.make_key(26)),
600
 
                          (self.make_key(31), self.make_key(48))],
 
528
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
601
529
            index._parsed_key_map)
602
530
        # reset the transport log
603
531
        del index._transport._activity[:]
605
533
        # not create a new transport request, and should return False (cannot
606
534
        # be in the index) - even when the byte location we ask for is outside
607
535
        # the parsed region
608
 
        #
609
 
        result = index._lookup_keys_via_location([(4000, self.make_key(40))])
 
536
        # 
 
537
        result = index._lookup_keys_via_location([(4000, make_key(40))])
610
538
        self.assertEqual(
611
 
            [((4000, self.make_key(40)),
612
 
              (index, self.make_key(40), self.make_value(40)))],
 
539
            [((4000, make_key(40)), (index, make_key(40), make_value(40)))],
613
540
            result)
614
541
        self.assertEqual([], index._transport._activity)
615
542
 
616
543
    def test_lookup_key_below_probed_area(self):
617
544
        # generate a big enough index that we only read some of it on a typical
618
545
        # bisection lookup.
619
 
        index = self.make_index(nodes=self.make_nodes(64))
 
546
        nodes = []
 
547
        def make_key(number):
 
548
            return (str(number) + 'X'*100,)
 
549
        for counter in range(64):
 
550
            nodes.append((make_key(counter), 'Y'*100, ()))
 
551
        index = self.make_index(nodes=nodes)
620
552
        # ask for the key in the middle, but a key that is located in the
621
553
        # unparsed region before the middle.
622
554
        result =index._lookup_keys_via_location(
623
555
            [(index._size // 2, ('30', ))])
624
556
        # check the parse map, this determines the test validity
625
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
626
 
        self.assertEqual([(None, self.make_key(26)),
627
 
                          (self.make_key(31), self.make_key(48))],
 
557
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
 
558
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
628
559
            index._parsed_key_map)
629
560
        self.assertEqual([((index._size // 2, ('30', )), -1)],
630
561
            result)
632
563
    def test_lookup_key_above_probed_area(self):
633
564
        # generate a big enough index that we only read some of it on a typical
634
565
        # bisection lookup.
635
 
        index = self.make_index(nodes=self.make_nodes(64))
 
566
        nodes = []
 
567
        def make_key(number):
 
568
            return (str(number) + 'X'*100,)
 
569
        for counter in range(64):
 
570
            nodes.append((make_key(counter), 'Y'*100, ()))
 
571
        index = self.make_index(nodes=nodes)
636
572
        # ask for the key in the middle, but a key that is located in the
637
573
        # unparsed region after the middle.
638
574
        result =index._lookup_keys_via_location(
639
575
            [(index._size // 2, ('50', ))])
640
576
        # check the parse map, this determines the test validity
641
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
642
 
        self.assertEqual([(None, self.make_key(26)),
643
 
                          (self.make_key(31), self.make_key(48))],
 
577
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
 
578
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
644
579
            index._parsed_key_map)
645
580
        self.assertEqual([((index._size // 2, ('50', )), +1)],
646
581
            result)
649
584
        # generate a big enough index that we only read some of it on a typical
650
585
        # bisection lookup.
651
586
        nodes = []
652
 
        for counter in range(99):
653
 
            nodes.append((self.make_key(counter), self.make_value(counter),
654
 
                ((self.make_key(counter + 20),),)  ))
655
 
        index = self.make_index(ref_lists=1, nodes=nodes)
656
 
        # lookup a key in the middle that does not exist, so that when we can
657
 
        # check that the referred-to-keys are not accessed automatically.
658
 
        index_size = index._size
659
 
        index_center = index_size // 2
660
 
        result = index._lookup_keys_via_location(
661
 
            [(index_center, ('40', ))])
662
 
        # check the parse map - only the start and middle should have been
663
 
        # parsed.
664
 
        self.assertEqual([(0, 4027), (10198, 14028)], index._parsed_byte_map)
665
 
        self.assertEqual([(None, self.make_key(17)),
666
 
                          (self.make_key(44), self.make_key(5))],
667
 
            index._parsed_key_map)
668
 
        # and check the transport activity likewise.
669
 
        self.assertEqual(
670
 
            [('readv', 'index', [(index_center, 800), (0, 200)], True,
671
 
                                  index_size)],
672
 
            index._transport._activity)
673
 
        # reset the transport log for testing the reference lookup
674
 
        del index._transport._activity[:]
675
 
        # now looking up a key in the portion of the file already parsed should
676
 
        # only perform IO to resolve its key references.
677
 
        result = index._lookup_keys_via_location([(11000, self.make_key(45))])
678
 
        self.assertEqual(
679
 
            [((11000, self.make_key(45)),
680
 
              (index, self.make_key(45), self.make_value(45),
681
 
               ((self.make_key(65),),)))],
682
 
            result)
683
 
        self.assertEqual([('readv', 'index', [(15093, 800)], True, index_size)],
684
 
            index._transport._activity)
685
 
 
686
 
    def test_lookup_key_can_buffer_all(self):
687
 
        nodes = []
 
587
        def make_key(number):
 
588
            return (str(number) + 'X'*100,)
 
589
        def make_value(number):
 
590
            return str(number) + 'Y'*100
688
591
        for counter in range(64):
689
 
            nodes.append((self.make_key(counter), self.make_value(counter),
690
 
                ((self.make_key(counter + 20),),)  ))
 
592
            nodes.append((make_key(counter), make_value(counter),
 
593
                ((make_key(counter + 20),),)  ))
691
594
        index = self.make_index(ref_lists=1, nodes=nodes)
692
595
        # lookup a key in the middle that does not exist, so that when we can
693
596
        # check that the referred-to-keys are not accessed automatically.
694
 
        index_size = index._size
695
 
        index_center = index_size // 2
696
 
        result = index._lookup_keys_via_location([(index_center, ('40', ))])
 
597
        result =index._lookup_keys_via_location(
 
598
            [(index._size // 2, ('40', ))])
697
599
        # check the parse map - only the start and middle should have been
698
600
        # parsed.
699
601
        self.assertEqual([(0, 3890), (6444, 10274)], index._parsed_byte_map)
700
 
        self.assertEqual([(None, self.make_key(25)),
701
 
                          (self.make_key(37), self.make_key(52))],
 
602
        self.assertEqual([(None, make_key(25)), (make_key(37), make_key(52))],
702
603
            index._parsed_key_map)
703
604
        # and check the transport activity likewise.
704
605
        self.assertEqual(
705
 
            [('readv', 'index', [(index_center, 800), (0, 200)], True,
706
 
                                  index_size)],
 
606
            [('readv', 'index', [(7906, 800), (0, 200)], True, 15813)],
707
607
            index._transport._activity)
708
608
        # reset the transport log for testing the reference lookup
709
609
        del index._transport._activity[:]
710
610
        # now looking up a key in the portion of the file already parsed should
711
611
        # only perform IO to resolve its key references.
712
 
        result = index._lookup_keys_via_location([(7000, self.make_key(40))])
 
612
        result = index._lookup_keys_via_location([(4000, make_key(40))])
713
613
        self.assertEqual(
714
 
            [((7000, self.make_key(40)),
715
 
              (index, self.make_key(40), self.make_value(40),
716
 
               ((self.make_key(60),),)))],
 
614
            [((4000, make_key(40)),
 
615
              (index, make_key(40), make_value(40), ((make_key(60),),)))],
717
616
            result)
718
 
        # Resolving the references would have required more data read, and we
719
 
        # are already above the 50% threshold, so it triggered a _buffer_all
720
 
        self.assertEqual([('get', 'index')], index._transport._activity)
 
617
        self.assertEqual([('readv', 'index', [(11976, 800)], True, 15813)],
 
618
            index._transport._activity)
721
619
 
722
620
    def test_iter_all_entries_empty(self):
723
621
        index = self.make_index()
742
640
            (index, ('ref', ), 'refdata', ((), ))]),
743
641
            set(index.iter_all_entries()))
744
642
 
745
 
    def test_iter_entries_buffers_once(self):
746
 
        index = self.make_index(nodes=self.make_nodes(2))
747
 
        # reset the transport log
748
 
        del index._transport._activity[:]
749
 
        self.assertEqual(set([(index, self.make_key(1), self.make_value(1))]),
750
 
                         set(index.iter_entries([self.make_key(1)])))
751
 
        # We should have requested reading the header bytes
752
 
        # But not needed any more than that because it would have triggered a
753
 
        # buffer all
754
 
        self.assertEqual([
755
 
            ('readv', 'index', [(0, 200)], True, index._size),
756
 
            ],
757
 
            index._transport._activity)
758
 
        # And that should have been enough to trigger reading the whole index
759
 
        # with buffering
760
 
        self.assertIsNot(None, index._nodes)
761
 
 
762
 
    def test_iter_entries_buffers_by_bytes_read(self):
763
 
        index = self.make_index(nodes=self.make_nodes(64))
764
 
        list(index.iter_entries([self.make_key(10)]))
765
 
        # The first time through isn't enough to trigger a buffer all
766
 
        self.assertIs(None, index._nodes)
767
 
        self.assertEqual(4096, index._bytes_read)
768
 
        # Grabbing a key in that same page won't trigger a buffer all, as we
769
 
        # still haven't read 50% of the file
770
 
        list(index.iter_entries([self.make_key(11)]))
771
 
        self.assertIs(None, index._nodes)
772
 
        self.assertEqual(4096, index._bytes_read)
773
 
        # We haven't read more data, so reading outside the range won't trigger
774
 
        # a buffer all right away
775
 
        list(index.iter_entries([self.make_key(40)]))
776
 
        self.assertIs(None, index._nodes)
777
 
        self.assertEqual(8192, index._bytes_read)
778
 
        # On the next pass, we will not trigger buffer all if the key is
779
 
        # available without reading more
780
 
        list(index.iter_entries([self.make_key(32)]))
781
 
        self.assertIs(None, index._nodes)
782
 
        # But if we *would* need to read more to resolve it, then we will
783
 
        # buffer all.
784
 
        list(index.iter_entries([self.make_key(60)]))
785
 
        self.assertIsNot(None, index._nodes)
786
 
 
787
643
    def test_iter_entries_references_resolved(self):
788
644
        index = self.make_index(1, nodes=[
789
645
            (('name', ), 'data', ([('ref', ), ('ref', )], )),
835
691
        self.assertEqual([], list(index.iter_entries([('a', )])))
836
692
 
837
693
    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', )])))
 
694
        index = self.make_index()
 
695
        index = GraphIndex(index._transport, 'index', None)
 
696
        self.assertEqual([], list(index.iter_entries([('a', )])))
841
697
 
842
698
    def test_iter_key_prefix_1_element_key_None(self):
843
699
        index = self.make_index()
907
763
            (('name', ), '', ()), (('foo', ), '', ())])
908
764
        self.assertEqual(2, index.key_count())
909
765
 
910
 
    def test_read_and_parse_tracks_real_read_value(self):
911
 
        index = self.make_index(nodes=self.make_nodes(10))
912
 
        del index._transport._activity[:]
913
 
        index._read_and_parse([(0, 200)])
914
 
        self.assertEqual([
915
 
            ('readv', 'index', [(0, 200)], True, index._size),
916
 
            ],
917
 
            index._transport._activity)
918
 
        # The readv expansion code will expand the initial request to 4096
919
 
        # bytes, which is more than enough to read the entire index, and we
920
 
        # will track the fact that we read that many bytes.
921
 
        self.assertEqual(index._size, index._bytes_read)
922
 
 
923
 
    def test_read_and_parse_triggers_buffer_all(self):
924
 
        index = self.make_index(key_elements=2, nodes=[
925
 
            (('name', 'fin1'), 'data', ()),
926
 
            (('name', 'fin2'), 'beta', ()),
927
 
            (('ref', 'erence'), 'refdata', ())])
928
 
        self.assertTrue(index._size > 0)
929
 
        self.assertIs(None, index._nodes)
930
 
        index._read_and_parse([(0, index._size)])
931
 
        self.assertIsNot(None, index._nodes)
932
 
 
933
766
    def test_validate_bad_index_errors(self):
934
767
        trans = self.get_transport()
935
768
        trans.put_bytes('name', "not an index\n")
936
 
        idx = index.GraphIndex(trans, 'name', 13)
937
 
        self.assertRaises(errors.BadIndexFormatSignature, idx.validate)
 
769
        index = GraphIndex(trans, 'name', 13)
 
770
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
938
771
 
939
772
    def test_validate_bad_node_refs(self):
940
 
        idx = self.make_index(2)
 
773
        index = self.make_index(2)
941
774
        trans = self.get_transport()
942
775
        content = trans.get_bytes('index')
943
776
        # change the options line to end with a rather than a parseable number
944
777
        new_content = content[:-2] + 'a\n\n'
945
778
        trans.put_bytes('index', new_content)
946
 
        self.assertRaises(errors.BadIndexOptions, idx.validate)
 
779
        self.assertRaises(errors.BadIndexOptions, index.validate)
947
780
 
948
781
    def test_validate_missing_end_line_empty(self):
949
782
        index = self.make_index(2)
969
802
        index = self.make_index(nodes=[(('key', ), 'value', ())])
970
803
        index.validate()
971
804
 
972
 
    # XXX: external_references tests are duplicated in test_btree_index.  We
973
 
    # probably should have per_graph_index tests...
974
 
    def test_external_references_no_refs(self):
975
 
        index = self.make_index(ref_lists=0, nodes=[])
976
 
        self.assertRaises(ValueError, index.external_references, 0)
977
 
 
978
 
    def test_external_references_no_results(self):
979
 
        index = self.make_index(ref_lists=1, nodes=[
980
 
            (('key',), 'value', ([],))])
981
 
        self.assertEqual(set(), index.external_references(0))
982
 
 
983
 
    def test_external_references_missing_ref(self):
984
 
        missing_key = ('missing',)
985
 
        index = self.make_index(ref_lists=1, nodes=[
986
 
            (('key',), 'value', ([missing_key],))])
987
 
        self.assertEqual(set([missing_key]), index.external_references(0))
988
 
 
989
 
    def test_external_references_multiple_ref_lists(self):
990
 
        missing_key = ('missing',)
991
 
        index = self.make_index(ref_lists=2, nodes=[
992
 
            (('key',), 'value', ([], [missing_key]))])
993
 
        self.assertEqual(set([]), index.external_references(0))
994
 
        self.assertEqual(set([missing_key]), index.external_references(1))
995
 
 
996
 
    def test_external_references_two_records(self):
997
 
        index = self.make_index(ref_lists=1, nodes=[
998
 
            (('key-1',), 'value', ([('key-2',)],)),
999
 
            (('key-2',), 'value', ([],)),
1000
 
            ])
1001
 
        self.assertEqual(set([]), index.external_references(0))
1002
 
 
1003
 
    def test__find_ancestors(self):
1004
 
        key1 = ('key-1',)
1005
 
        key2 = ('key-2',)
1006
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1007
 
            (key1, 'value', ([key2],)),
1008
 
            (key2, 'value', ([],)),
1009
 
            ])
1010
 
        parent_map = {}
1011
 
        missing_keys = set()
1012
 
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
1013
 
        self.assertEqual({key1: (key2,)}, parent_map)
1014
 
        self.assertEqual(set(), missing_keys)
1015
 
        self.assertEqual(set([key2]), search_keys)
1016
 
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
1017
 
                                            missing_keys)
1018
 
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
1019
 
        self.assertEqual(set(), missing_keys)
1020
 
        self.assertEqual(set(), search_keys)
1021
 
 
1022
 
    def test__find_ancestors_w_missing(self):
1023
 
        key1 = ('key-1',)
1024
 
        key2 = ('key-2',)
1025
 
        key3 = ('key-3',)
1026
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1027
 
            (key1, 'value', ([key2],)),
1028
 
            (key2, 'value', ([],)),
1029
 
            ])
1030
 
        parent_map = {}
1031
 
        missing_keys = set()
1032
 
        search_keys = index._find_ancestors([key2, key3], 0, parent_map,
1033
 
                                            missing_keys)
1034
 
        self.assertEqual({key2: ()}, parent_map)
1035
 
        self.assertEqual(set([key3]), missing_keys)
1036
 
        self.assertEqual(set(), search_keys)
1037
 
 
1038
 
    def test__find_ancestors_dont_search_known(self):
1039
 
        key1 = ('key-1',)
1040
 
        key2 = ('key-2',)
1041
 
        key3 = ('key-3',)
1042
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1043
 
            (key1, 'value', ([key2],)),
1044
 
            (key2, 'value', ([key3],)),
1045
 
            (key3, 'value', ([],)),
1046
 
            ])
1047
 
        # We already know about key2, so we won't try to search for key3
1048
 
        parent_map = {key2: (key3,)}
1049
 
        missing_keys = set()
1050
 
        search_keys = index._find_ancestors([key1], 0, parent_map,
1051
 
                                            missing_keys)
1052
 
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1053
 
        self.assertEqual(set(), missing_keys)
1054
 
        self.assertEqual(set(), search_keys)
1055
 
 
1056
 
    def test_supports_unlimited_cache(self):
1057
 
        builder = index.GraphIndexBuilder(0, key_elements=1)
1058
 
        stream = builder.finish()
1059
 
        trans = self.get_transport()
1060
 
        size = trans.put_file('index', stream)
1061
 
        # It doesn't matter what unlimited_cache does here, just that it can be
1062
 
        # passed
1063
 
        idx = index.GraphIndex(trans, 'index', size, unlimited_cache=True)
1064
 
 
1065
 
 
1066
 
class TestCombinedGraphIndex(tests.TestCaseWithMemoryTransport):
 
805
 
 
806
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
1067
807
 
1068
808
    def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
1069
 
        builder = index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
 
809
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
1070
810
        for key, value, references in nodes:
1071
811
            builder.add_node(key, value, references)
1072
812
        stream = builder.finish()
1073
813
        trans = self.get_transport()
1074
814
        size = trans.put_file(name, stream)
1075
 
        return index.GraphIndex(trans, name, size)
1076
 
 
1077
 
    def make_combined_index_with_missing(self, missing=['1', '2']):
1078
 
        """Create a CombinedGraphIndex which will have missing indexes.
1079
 
 
1080
 
        This creates a CGI which thinks it has 2 indexes, however they have
1081
 
        been deleted. If CGI._reload_func() is called, then it will repopulate
1082
 
        with a new index.
1083
 
 
1084
 
        :param missing: The underlying indexes to delete
1085
 
        :return: (CombinedGraphIndex, reload_counter)
1086
 
        """
1087
 
        idx1 = self.make_index('1', nodes=[(('1',), '', ())])
1088
 
        idx2 = self.make_index('2', nodes=[(('2',), '', ())])
1089
 
        idx3 = self.make_index('3', nodes=[
1090
 
            (('1',), '', ()),
1091
 
            (('2',), '', ())])
1092
 
 
1093
 
        # total_reloads, num_changed, num_unchanged
1094
 
        reload_counter = [0, 0, 0]
1095
 
        def reload():
1096
 
            reload_counter[0] += 1
1097
 
            new_indices = [idx3]
1098
 
            if idx._indices == new_indices:
1099
 
                reload_counter[2] += 1
1100
 
                return False
1101
 
            reload_counter[1] += 1
1102
 
            idx._indices[:] = new_indices
1103
 
            return True
1104
 
        idx = index.CombinedGraphIndex([idx1, idx2], reload_func=reload)
1105
 
        trans = self.get_transport()
1106
 
        for fname in missing:
1107
 
            trans.delete(fname)
1108
 
        return idx, reload_counter
 
815
        return GraphIndex(trans, name, size)
1109
816
 
1110
817
    def test_open_missing_index_no_error(self):
1111
818
        trans = self.get_transport()
1112
 
        idx1 = index.GraphIndex(trans, 'missing', 100)
1113
 
        idx = index.CombinedGraphIndex([idx1])
 
819
        index1 = GraphIndex(trans, 'missing', 100)
 
820
        index = CombinedGraphIndex([index1])
1114
821
 
1115
822
    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()))
1121
 
 
1122
 
    def test_clear_cache(self):
1123
 
        log = []
1124
 
 
1125
 
        class ClearCacheProxy(object):
1126
 
 
1127
 
            def __init__(self, index):
1128
 
                self._index = index
1129
 
 
1130
 
            def __getattr__(self, name):
1131
 
                return getattr(self._index)
1132
 
 
1133
 
            def clear_cache(self):
1134
 
                log.append(self._index)
1135
 
                return self._index.clear_cache()
1136
 
 
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))
1142
 
        # CombinedGraphIndex should call 'clear_cache()' on all children
1143
 
        idx.clear_cache()
1144
 
        self.assertEqual(sorted([idx1, idx2]), sorted(log))
 
823
        index = CombinedGraphIndex([])
 
824
        index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
 
825
        index.insert_index(0, index1)
 
826
        self.assertEqual([(index1, ('key', ), '')], list(index.iter_all_entries()))
1145
827
 
1146
828
    def test_iter_all_entries_empty(self):
1147
 
        idx = index.CombinedGraphIndex([])
1148
 
        self.assertEqual([], list(idx.iter_all_entries()))
 
829
        index = CombinedGraphIndex([])
 
830
        self.assertEqual([], list(index.iter_all_entries()))
1149
831
 
1150
832
    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()))
 
833
        index1 = self.make_index('name')
 
834
        index = CombinedGraphIndex([index1])
 
835
        self.assertEqual([], list(index.iter_all_entries()))
1154
836
 
1155
837
    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()))
 
838
        index1 = self.make_index('name', nodes=[(('name', ), 'data', ())])
 
839
        index = CombinedGraphIndex([index1])
 
840
        self.assertEqual([(index1, ('name', ), 'data')],
 
841
            list(index.iter_all_entries()))
1160
842
 
1161
843
    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()))
 
844
        index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
 
845
        index2 = self.make_index('name2', nodes=[(('2', ), '', ())])
 
846
        index = CombinedGraphIndex([index1, index2])
 
847
        self.assertEqual([(index1, ('name', ), 'data'),
 
848
            (index2, ('2', ), '')],
 
849
            list(index.iter_all_entries()))
1168
850
 
1169
851
    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', )])))
 
852
        index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
 
853
        index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
 
854
        index = CombinedGraphIndex([index1, index2])
 
855
        self.assertEqual([(index1, ('name', ), 'data')],
 
856
            list(index.iter_entries([('name', )])))
1175
857
 
1176
858
    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()))
 
859
        index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
 
860
        index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
 
861
        index = CombinedGraphIndex([index1, index2])
 
862
        self.assertEqual([(index1, ('name', ), 'data')],
 
863
            list(index.iter_all_entries()))
1182
864
 
1183
865
    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)])))
 
866
        index1 = self.make_index('1', 1, key_elements=2, nodes=[
 
867
            (('name', 'fin1'), 'data', ([('ref', 'erence')], ))])
 
868
        index2 = self.make_index('2', 1, key_elements=2, nodes=[
 
869
            (('name', 'fin2'), 'beta', ([], )),
 
870
            (('ref', 'erence'), 'refdata', ([], ))])
 
871
        index = CombinedGraphIndex([index1, index2])
 
872
        self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
873
            (index2, ('ref', 'erence'), 'refdata', ((), ))]),
 
874
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
 
875
        self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
876
            (index2, ('name', 'fin2'), 'beta', ((), ))]),
 
877
            set(index.iter_entries_prefix([('name', None)])))
1199
878
 
1200
879
    def test_iter_nothing_empty(self):
1201
 
        idx = index.CombinedGraphIndex([])
1202
 
        self.assertEqual([], list(idx.iter_entries([])))
 
880
        index = CombinedGraphIndex([])
 
881
        self.assertEqual([], list(index.iter_entries([])))
1203
882
 
1204
883
    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([])))
 
884
        index1 = self.make_index('name')
 
885
        index = CombinedGraphIndex([index1])
 
886
        self.assertEqual([], list(index.iter_entries([])))
1208
887
 
1209
888
    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', )])))
1217
 
 
 
889
        index1 = self.make_index('1', 1, nodes=[
 
890
            (('name', ), 'data', ([('ref', )], ))])
 
891
        index2 = self.make_index('2', 1, nodes=[
 
892
            (('ref', ), 'refdata', ((), ))])
 
893
        index = CombinedGraphIndex([index1, index2])
 
894
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),
 
895
            (index2, ('ref', ), 'refdata', ((), ))]),
 
896
            set(index.iter_entries([('name', ), ('ref', )])))
 
897
 
1218
898
    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', )])))
1227
 
 
 
899
        index1 = self.make_index('1', 1, nodes=[
 
900
            (('name', ), 'data', ([('ref', )], )),
 
901
            (('ref', ), 'refdata', ([], ))])
 
902
        index2 = self.make_index('2', 1, nodes=[
 
903
            (('ref', ), 'refdata', ([], ))])
 
904
        index = CombinedGraphIndex([index1, index2])
 
905
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),
 
906
            (index1, ('ref', ), 'refdata', ((), ))]),
 
907
            set(index.iter_entries([('name', ), ('ref', )])))
 
908
 
1228
909
    def test_iter_missing_entry_empty(self):
1229
 
        idx = index.CombinedGraphIndex([])
1230
 
        self.assertEqual([], list(idx.iter_entries([('a', )])))
 
910
        index = CombinedGraphIndex([])
 
911
        self.assertEqual([], list(index.iter_entries([('a', )])))
1231
912
 
1232
913
    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', )])))
 
914
        index1 = self.make_index('1')
 
915
        index = CombinedGraphIndex([index1])
 
916
        self.assertEqual([], list(index.iter_entries([('a', )])))
1236
917
 
1237
918
    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', )])))
1242
 
 
 
919
        index1 = self.make_index('1')
 
920
        index2 = self.make_index('2')
 
921
        index = CombinedGraphIndex([index1, index2])
 
922
        self.assertEqual([], list(index.iter_entries([('a', )])))
 
923
 
1243
924
    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', )])))
 
925
        index1 = self.make_index('1', nodes=[(('key', ), '', ())])
 
926
        index2 = self.make_index('2', nodes=[])
 
927
        index = CombinedGraphIndex([index1, index2])
 
928
        self.assertEqual([(index1, ('key', ), '')],
 
929
            list(index.iter_entries([('key', )])))
1249
930
        # and in the other direction
1250
 
        idx = index.CombinedGraphIndex([idx2, idx1])
1251
 
        self.assertEqual([(idx1, ('key', ), '')],
1252
 
                         list(idx.iter_entries([('key', )])))
 
931
        index = CombinedGraphIndex([index2, index1])
 
932
        self.assertEqual([(index1, ('key', ), '')],
 
933
            list(index.iter_entries([('key', )])))
1253
934
 
1254
935
    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())
 
936
        index1 = self.make_index('1', nodes=[])
 
937
        index2 = self.make_index('2', nodes=[])
 
938
        index = CombinedGraphIndex([index1, index2])
 
939
        self.assertEqual(0, index.key_count())
1259
940
 
1260
941
    def test_key_count_sums_index_keys(self):
1261
 
        idx1 = self.make_index('1', nodes=[
 
942
        index1 = self.make_index('1', nodes=[
1262
943
            (('1',), '', ()),
1263
944
            (('2',), '', ())])
1264
 
        idx2 = self.make_index('2', nodes=[(('1',), '', ())])
1265
 
        idx = index.CombinedGraphIndex([idx1, idx2])
1266
 
        self.assertEqual(3, idx.key_count())
 
945
        index2 = self.make_index('2', nodes=[(('1',), '', ())])
 
946
        index = CombinedGraphIndex([index1, index2])
 
947
        self.assertEqual(3, index.key_count())
1267
948
 
1268
949
    def test_validate_bad_child_index_errors(self):
1269
950
        trans = self.get_transport()
1270
951
        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)
 
952
        index1 = GraphIndex(trans, 'name', 13)
 
953
        index = CombinedGraphIndex([index1])
 
954
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
1274
955
 
1275
956
    def test_validate_empty(self):
1276
 
        idx = index.CombinedGraphIndex([])
1277
 
        idx.validate()
1278
 
 
1279
 
    def test_key_count_reloads(self):
1280
 
        idx, reload_counter = self.make_combined_index_with_missing()
1281
 
        self.assertEqual(2, idx.key_count())
1282
 
        self.assertEqual([1, 1, 0], reload_counter)
1283
 
 
1284
 
    def test_key_count_no_reload(self):
1285
 
        idx, reload_counter = self.make_combined_index_with_missing()
1286
 
        idx._reload_func = None
1287
 
        # Without a _reload_func we just raise the exception
1288
 
        self.assertRaises(errors.NoSuchFile, idx.key_count)
1289
 
 
1290
 
    def test_key_count_reloads_and_fails(self):
1291
 
        # We have deleted all underlying indexes, so we will try to reload, but
1292
 
        # still fail. This is mostly to test we don't get stuck in an infinite
1293
 
        # 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)
1297
 
        self.assertEqual([2, 1, 1], reload_counter)
1298
 
 
1299
 
    def test_iter_entries_reloads(self):
1300
 
        index, reload_counter = self.make_combined_index_with_missing()
1301
 
        result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1302
 
        index3 = index._indices[0]
1303
 
        self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
1304
 
                         result)
1305
 
        self.assertEqual([1, 1, 0], reload_counter)
1306
 
 
1307
 
    def test_iter_entries_reloads_midway(self):
1308
 
        # The first index still looks present, so we get interrupted mid-way
1309
 
        # through
1310
 
        index, reload_counter = self.make_combined_index_with_missing(['2'])
1311
 
        index1, index2 = index._indices
1312
 
        result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1313
 
        index3 = index._indices[0]
1314
 
        # We had already yielded '1', so we just go on to the next, we should
1315
 
        # not yield '1' twice.
1316
 
        self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1317
 
                         result)
1318
 
        self.assertEqual([1, 1, 0], reload_counter)
1319
 
 
1320
 
    def test_iter_entries_no_reload(self):
1321
 
        index, reload_counter = self.make_combined_index_with_missing()
1322
 
        index._reload_func = None
1323
 
        # Without a _reload_func we just raise the exception
1324
 
        self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1325
 
 
1326
 
    def test_iter_entries_reloads_and_fails(self):
1327
 
        index, reload_counter = self.make_combined_index_with_missing(
1328
 
                                    ['1', '2', '3'])
1329
 
        self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1330
 
        self.assertEqual([2, 1, 1], reload_counter)
1331
 
 
1332
 
    def test_iter_all_entries_reloads(self):
1333
 
        index, reload_counter = self.make_combined_index_with_missing()
1334
 
        result = list(index.iter_all_entries())
1335
 
        index3 = index._indices[0]
1336
 
        self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
1337
 
                         result)
1338
 
        self.assertEqual([1, 1, 0], reload_counter)
1339
 
 
1340
 
    def test_iter_all_entries_reloads_midway(self):
1341
 
        index, reload_counter = self.make_combined_index_with_missing(['2'])
1342
 
        index1, index2 = index._indices
1343
 
        result = list(index.iter_all_entries())
1344
 
        index3 = index._indices[0]
1345
 
        # We had already yielded '1', so we just go on to the next, we should
1346
 
        # not yield '1' twice.
1347
 
        self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1348
 
                         result)
1349
 
        self.assertEqual([1, 1, 0], reload_counter)
1350
 
 
1351
 
    def test_iter_all_entries_no_reload(self):
1352
 
        index, reload_counter = self.make_combined_index_with_missing()
1353
 
        index._reload_func = None
1354
 
        self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1355
 
 
1356
 
    def test_iter_all_entries_reloads_and_fails(self):
1357
 
        index, reload_counter = self.make_combined_index_with_missing(
1358
 
                                    ['1', '2', '3'])
1359
 
        self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1360
 
 
1361
 
    def test_iter_entries_prefix_reloads(self):
1362
 
        index, reload_counter = self.make_combined_index_with_missing()
1363
 
        result = list(index.iter_entries_prefix([('1',)]))
1364
 
        index3 = index._indices[0]
1365
 
        self.assertEqual([(index3, ('1',), '')], result)
1366
 
        self.assertEqual([1, 1, 0], reload_counter)
1367
 
 
1368
 
    def test_iter_entries_prefix_reloads_midway(self):
1369
 
        index, reload_counter = self.make_combined_index_with_missing(['2'])
1370
 
        index1, index2 = index._indices
1371
 
        result = list(index.iter_entries_prefix([('1',)]))
1372
 
        index3 = index._indices[0]
1373
 
        # We had already yielded '1', so we just go on to the next, we should
1374
 
        # not yield '1' twice.
1375
 
        self.assertEqual([(index1, ('1',), '')], result)
1376
 
        self.assertEqual([1, 1, 0], reload_counter)
1377
 
 
1378
 
    def test_iter_entries_prefix_no_reload(self):
1379
 
        index, reload_counter = self.make_combined_index_with_missing()
1380
 
        index._reload_func = None
1381
 
        self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1382
 
                                                 [('1',)])
1383
 
 
1384
 
    def test_iter_entries_prefix_reloads_and_fails(self):
1385
 
        index, reload_counter = self.make_combined_index_with_missing(
1386
 
                                    ['1', '2', '3'])
1387
 
        self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1388
 
                                                 [('1',)])
1389
 
 
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
 
    def test_validate_reloads(self):
1435
 
        idx, reload_counter = self.make_combined_index_with_missing()
1436
 
        idx.validate()
1437
 
        self.assertEqual([1, 1, 0], reload_counter)
1438
 
 
1439
 
    def test_validate_reloads_midway(self):
1440
 
        idx, reload_counter = self.make_combined_index_with_missing(['2'])
1441
 
        idx.validate()
1442
 
 
1443
 
    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)
1447
 
 
1448
 
    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)
1452
 
 
1453
 
    def test_find_ancestors_across_indexes(self):
1454
 
        key1 = ('key-1',)
1455
 
        key2 = ('key-2',)
1456
 
        key3 = ('key-3',)
1457
 
        key4 = ('key-4',)
1458
 
        index1 = self.make_index('12', ref_lists=1, nodes=[
1459
 
            (key1, 'value', ([],)),
1460
 
            (key2, 'value', ([key1],)),
1461
 
            ])
1462
 
        index2 = self.make_index('34', ref_lists=1, nodes=[
1463
 
            (key3, 'value', ([key2],)),
1464
 
            (key4, 'value', ([key3],)),
1465
 
            ])
1466
 
        c_index = index.CombinedGraphIndex([index1, index2])
1467
 
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1468
 
        self.assertEqual({key1: ()}, parent_map)
1469
 
        self.assertEqual(set(), missing_keys)
1470
 
        # Now look for a key from index2 which requires us to find the key in
1471
 
        # the second index, and then continue searching for parents in the
1472
 
        # first index
1473
 
        parent_map, missing_keys = c_index.find_ancestry([key3], 0)
1474
 
        self.assertEqual({key1: (), key2: (key1,), key3: (key2,)}, parent_map)
1475
 
        self.assertEqual(set(), missing_keys)
1476
 
 
1477
 
    def test_find_ancestors_missing_keys(self):
1478
 
        key1 = ('key-1',)
1479
 
        key2 = ('key-2',)
1480
 
        key3 = ('key-3',)
1481
 
        key4 = ('key-4',)
1482
 
        index1 = self.make_index('12', ref_lists=1, nodes=[
1483
 
            (key1, 'value', ([],)),
1484
 
            (key2, 'value', ([key1],)),
1485
 
            ])
1486
 
        index2 = self.make_index('34', ref_lists=1, nodes=[
1487
 
            (key3, 'value', ([key2],)),
1488
 
            ])
1489
 
        c_index = index.CombinedGraphIndex([index1, index2])
1490
 
        # Searching for a key which is actually not present at all should
1491
 
        # eventually converge
1492
 
        parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1493
 
        self.assertEqual({}, parent_map)
1494
 
        self.assertEqual(set([key4]), missing_keys)
1495
 
 
1496
 
    def test_find_ancestors_no_indexes(self):
1497
 
        c_index = index.CombinedGraphIndex([])
1498
 
        key1 = ('key-1',)
1499
 
        parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1500
 
        self.assertEqual({}, parent_map)
1501
 
        self.assertEqual(set([key1]), missing_keys)
1502
 
 
1503
 
    def test_find_ancestors_ghost_parent(self):
1504
 
        key1 = ('key-1',)
1505
 
        key2 = ('key-2',)
1506
 
        key3 = ('key-3',)
1507
 
        key4 = ('key-4',)
1508
 
        index1 = self.make_index('12', ref_lists=1, nodes=[
1509
 
            (key1, 'value', ([],)),
1510
 
            (key2, 'value', ([key1],)),
1511
 
            ])
1512
 
        index2 = self.make_index('34', ref_lists=1, nodes=[
1513
 
            (key4, 'value', ([key2, key3],)),
1514
 
            ])
1515
 
        c_index = index.CombinedGraphIndex([index1, index2])
1516
 
        # Searching for a key which is actually not present at all should
1517
 
        # eventually converge
1518
 
        parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1519
 
        self.assertEqual({key4: (key2, key3), key2: (key1,), key1: ()},
1520
 
                         parent_map)
1521
 
        self.assertEqual(set([key3]), missing_keys)
1522
 
 
1523
 
    def test__find_ancestors_empty_index(self):
1524
 
        idx = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
1525
 
        parent_map = {}
1526
 
        missing_keys = set()
1527
 
        search_keys = idx._find_ancestors([('one',), ('two',)], 0, parent_map,
1528
 
                                          missing_keys)
1529
 
        self.assertEqual(set(), search_keys)
1530
 
        self.assertEqual({}, parent_map)
1531
 
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
1532
 
 
1533
 
 
1534
 
class TestInMemoryGraphIndex(tests.TestCaseWithMemoryTransport):
 
957
        index = CombinedGraphIndex([])
 
958
        index.validate()
 
959
 
 
960
 
 
961
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
1535
962
 
1536
963
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
1537
 
        result = index.InMemoryGraphIndex(ref_lists, key_elements=key_elements)
 
964
        result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1538
965
        result.add_nodes(nodes)
1539
966
        return result
1540
967
 
1661
1088
        index.validate()
1662
1089
 
1663
1090
 
1664
 
class TestGraphIndexPrefixAdapter(tests.TestCaseWithMemoryTransport):
 
1091
class TestGraphIndexPrefixAdapter(TestCaseWithMemoryTransport):
1665
1092
 
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)
 
1093
    def make_index(self, ref_lists=1, key_elements=2, nodes=[], add_callback=False):
 
1094
        result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1669
1095
        result.add_nodes(nodes)
1670
1096
        if add_callback:
1671
1097
            add_nodes_callback = result.add_nodes
1672
1098
        else:
1673
1099
            add_nodes_callback = None
1674
 
        adapter = index.GraphIndexPrefixAdapter(
1675
 
            result, ('prefix', ), key_elements - 1,
 
1100
        adapter = GraphIndexPrefixAdapter(result, ('prefix', ), key_elements - 1,
1676
1101
            add_nodes_callback=add_nodes_callback)
1677
1102
        return result, adapter
1678
1103
 
1679
1104
    def test_add_node(self):
1680
1105
        index, adapter = self.make_index(add_callback=True)
1681
1106
        adapter.add_node(('key',), 'value', ((('ref',),),))
1682
 
        self.assertEqual(set([(index, ('prefix', 'key'), 'value',
1683
 
                               ((('prefix', 'ref'),),))]),
 
1107
        self.assertEqual(set([(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))]),
1684
1108
            set(index.iter_all_entries()))
1685
1109
 
1686
1110
    def test_add_nodes(self):
1696
1120
            set(index.iter_all_entries()))
1697
1121
 
1698
1122
    def test_construct(self):
1699
 
        idx = index.InMemoryGraphIndex()
1700
 
        adapter = index.GraphIndexPrefixAdapter(idx, ('prefix', ), 1)
 
1123
        index = InMemoryGraphIndex()
 
1124
        adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1)
1701
1125
 
1702
1126
    def test_construct_with_callback(self):
1703
 
        idx = index.InMemoryGraphIndex()
1704
 
        adapter = index.GraphIndexPrefixAdapter(idx, ('prefix', ), 1,
1705
 
                                                idx.add_nodes)
 
1127
        index = InMemoryGraphIndex()
 
1128
        adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1, index.add_nodes)
1706
1129
 
1707
1130
    def test_iter_all_entries_cross_prefix_map_errors(self):
1708
1131
        index, adapter = self.make_index(nodes=[