← 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: Jelmer Vernooij
  • Date: 2012-01-27 19:05:43 UTC
  • mto: This revision was merged to the branch mainline in revision 6450.
  • Revision ID: jelmer@samba.org-20120127190543-vk350mv4a0c7aug2
Fix weave test.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_index.py
1
 
# Copyright (C) 2007 Canonical Ltd
 
1
# Copyright (C) 2007-2010 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
"""Tests for indices."""
18
18
 
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()
173
175
            "key\x00\x00\t\x00data\n"
174
176
            "\n", contents)
175
177
 
 
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
 
176
183
    def test_node_references_are_byte_offsets(self):
177
 
        builder = GraphIndexBuilder(reference_lists=1)
 
184
        builder = index.GraphIndexBuilder(reference_lists=1)
178
185
        builder.add_node(('reference', ), 'data', ([], ))
179
186
        builder.add_node(('key', ), 'data', ([('reference', )], ))
180
187
        stream = builder.finish()
186
193
            "\n", contents)
187
194
 
188
195
    def test_node_references_are_cr_delimited(self):
189
 
        builder = GraphIndexBuilder(reference_lists=1)
 
196
        builder = index.GraphIndexBuilder(reference_lists=1)
190
197
        builder.add_node(('reference', ), 'data', ([], ))
191
198
        builder.add_node(('reference2', ), 'data', ([], ))
192
 
        builder.add_node(('key', ), 'data', ([('reference', ), ('reference2', )], ))
 
199
        builder.add_node(('key', ), 'data',
 
200
                         ([('reference', ), ('reference2', )], ))
193
201
        stream = builder.finish()
194
202
        contents = stream.read()
195
203
        self.assertEqual(
200
208
            "\n", contents)
201
209
 
202
210
    def test_multiple_reference_lists_are_tab_delimited(self):
203
 
        builder = GraphIndexBuilder(reference_lists=2)
 
211
        builder = index.GraphIndexBuilder(reference_lists=2)
204
212
        builder.add_node(('keference', ), 'data', ([], []))
205
 
        builder.add_node(('rey', ), 'data', ([('keference', )], [('keference', )]))
 
213
        builder.add_node(('rey', ), 'data',
 
214
                         ([('keference', )], [('keference', )]))
206
215
        stream = builder.finish()
207
216
        contents = stream.read()
208
217
        self.assertEqual(
212
221
            "\n", contents)
213
222
 
214
223
    def test_add_node_referencing_missing_key_makes_absent(self):
215
 
        builder = GraphIndexBuilder(reference_lists=1)
216
 
        builder.add_node(('rey', ), 'data', ([('beference', ), ('aeference2', )], ))
 
224
        builder = index.GraphIndexBuilder(reference_lists=1)
 
225
        builder.add_node(('rey', ), 'data',
 
226
                         ([('beference', ), ('aeference2', )], ))
217
227
        stream = builder.finish()
218
228
        contents = stream.read()
219
229
        self.assertEqual(
225
235
 
226
236
    def test_node_references_three_digits(self):
227
237
        # test the node digit expands as needed.
228
 
        builder = GraphIndexBuilder(reference_lists=1)
 
238
        builder = index.GraphIndexBuilder(reference_lists=1)
229
239
        references = [(str(val), ) for val in reversed(range(9))]
230
240
        builder.add_node(('2-key', ), '', (references, ))
231
241
        stream = builder.finish()
232
242
        contents = stream.read()
233
 
        self.assertEqual(
 
243
        self.assertEqualDiff(
234
244
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
235
245
            "0\x00a\x00\x00\n"
236
246
            "1\x00a\x00\x00\n"
247
257
    def test_absent_has_no_reference_overhead(self):
248
258
        # the offsets after an absent record should be correct when there are
249
259
        # >1 reference lists.
250
 
        builder = GraphIndexBuilder(reference_lists=2)
 
260
        builder = index.GraphIndexBuilder(reference_lists=2)
251
261
        builder.add_node(('parent', ), '', ([('aail', ), ('zther', )], []))
252
262
        stream = builder.finish()
253
263
        contents = stream.read()
259
269
            "\n", contents)
260
270
 
261
271
    def test_add_node_bad_key(self):
262
 
        builder = GraphIndexBuilder()
 
272
        builder = index.GraphIndexBuilder()
263
273
        for bad_char in '\t\n\x0b\x0c\r\x00 ':
264
274
            self.assertRaises(errors.BadIndexKey, builder.add_node,
265
275
                ('a%skey' % bad_char, ), 'data')
274
284
        self.assertRaises(errors.BadIndexKey, builder.add_node,
275
285
                ('primary', 'secondary'), 'data')
276
286
        # secondary key elements get checked too:
277
 
        builder = GraphIndexBuilder(key_elements=2)
 
287
        builder = index.GraphIndexBuilder(key_elements=2)
278
288
        for bad_char in '\t\n\x0b\x0c\r\x00 ':
279
289
            self.assertRaises(errors.BadIndexKey, builder.add_node,
280
290
                ('prefix', 'a%skey' % bad_char), 'data')
281
291
 
282
292
    def test_add_node_bad_data(self):
283
 
        builder = GraphIndexBuilder()
 
293
        builder = index.GraphIndexBuilder()
284
294
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
285
295
            'data\naa')
286
296
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
287
297
            'data\x00aa')
288
298
 
289
299
    def test_add_node_bad_mismatched_ref_lists_length(self):
290
 
        builder = GraphIndexBuilder()
 
300
        builder = index.GraphIndexBuilder()
291
301
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
292
302
            'data aa', ([], ))
293
 
        builder = GraphIndexBuilder(reference_lists=1)
 
303
        builder = index.GraphIndexBuilder(reference_lists=1)
294
304
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
295
305
            'data aa')
296
306
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
297
307
            'data aa', (), )
298
308
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
299
309
            'data aa', ([], []))
300
 
        builder = GraphIndexBuilder(reference_lists=2)
 
310
        builder = index.GraphIndexBuilder(reference_lists=2)
301
311
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
302
312
            'data aa')
303
313
        self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
307
317
 
308
318
    def test_add_node_bad_key_in_reference_lists(self):
309
319
        # first list, first key - trivial
310
 
        builder = GraphIndexBuilder(reference_lists=1)
 
320
        builder = index.GraphIndexBuilder(reference_lists=1)
311
321
        self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
312
322
            'data aa', ([('a key', )], ))
313
323
        # references keys must be tuples too
324
334
            'data aa', ([('agoodkey', ), ('that is a bad key', )], ))
325
335
        # and if there is more than one list it should be getting checked
326
336
        # too
327
 
        builder = GraphIndexBuilder(reference_lists=2)
 
337
        builder = index.GraphIndexBuilder(reference_lists=2)
328
338
        self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
329
339
            'data aa', ([], ['a bad key']))
330
340
 
331
341
    def test_add_duplicate_key(self):
332
 
        builder = GraphIndexBuilder()
 
342
        builder = index.GraphIndexBuilder()
333
343
        builder.add_node(('key', ), 'data')
334
 
        self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node, ('key', ),
335
 
            'data')
 
344
        self.assertRaises(errors.BadIndexDuplicateKey,
 
345
                          builder.add_node, ('key', ), 'data')
336
346
 
337
347
    def test_add_duplicate_key_2_elements(self):
338
 
        builder = GraphIndexBuilder(key_elements=2)
 
348
        builder = index.GraphIndexBuilder(key_elements=2)
339
349
        builder.add_node(('key', 'key'), 'data')
340
350
        self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node,
341
351
            ('key', 'key'), 'data')
342
352
 
343
353
    def test_add_key_after_referencing_key(self):
344
 
        builder = GraphIndexBuilder(reference_lists=1)
 
354
        builder = index.GraphIndexBuilder(reference_lists=1)
345
355
        builder.add_node(('key', ), 'data', ([('reference', )], ))
346
356
        builder.add_node(('reference', ), 'data', ([],))
347
357
 
348
358
    def test_add_key_after_referencing_key_2_elements(self):
349
 
        builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
 
359
        builder = index.GraphIndexBuilder(reference_lists=1, key_elements=2)
350
360
        builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
351
361
        builder.add_node(('reference', 'tokey'), 'data', ([],))
352
362
 
353
 
 
354
 
class TestGraphIndex(TestCaseWithMemoryTransport):
 
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
355
386
 
356
387
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
357
 
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
 
388
        builder = index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
358
389
        for key, value, references in nodes:
359
390
            builder.add_node(key, value, references)
360
391
        stream = builder.finish()
361
 
        trans = get_transport('trace+' + self.get_url())
 
392
        trans = transport.get_transport_from_url('trace+' + self.get_url())
362
393
        size = trans.put_file('index', stream)
363
 
        return GraphIndex(trans, 'index', size)
 
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()
364
412
 
365
413
    def test_open_bad_index_no_error(self):
366
414
        trans = self.get_transport()
367
415
        trans.put_bytes('name', "not an index\n")
368
 
        index = GraphIndex(trans, 'name', 13)
 
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())
369
437
 
370
438
    def test_open_sets_parsed_map_empty(self):
371
439
        index = self.make_index()
372
440
        self.assertEqual([], index._parsed_byte_map)
373
441
        self.assertEqual([], index._parsed_key_map)
374
442
 
 
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):
 
458
        index = self.make_index()
 
459
        # reset the transport log
 
460
        del index._transport._activity[:]
 
461
        # do a _lookup_keys_via_location call for the middle of the file, which
 
462
        # is what bisection uses.
 
463
        result = index._lookup_keys_via_location(
 
464
            [(index._size // 2, ('missing', ))])
 
465
        # this should have asked for a readv request, with adjust_for_latency,
 
466
        # and two regions: the header, and half-way into the file.
 
467
        self.assertEqual([
 
468
            ('readv', 'index', [(30, 30), (0, 200)], True, 60),
 
469
            ],
 
470
            index._transport._activity)
 
471
        # and the result should be that the key cannot be present, because this
 
472
        # is a trivial index.
 
473
        self.assertEqual([((index._size // 2, ('missing', )), False)],
 
474
            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)
 
478
 
375
479
    def test_first_lookup_key_via_location(self):
376
 
        index = self.make_index()
 
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))
377
488
        # reset the transport log
378
489
        del index._transport._activity[:]
379
490
        # do a _lookup_keys_via_location call for the middle of the file, which
380
491
        # is what bisection uses.
 
492
        start_lookup = index._size // 2
381
493
        result = index._lookup_keys_via_location(
382
 
            [(index._size // 2, ('missing', ))])
 
494
            [(start_lookup, ('40missing', ))])
383
495
        # this should have asked for a readv request, with adjust_for_latency,
384
496
        # and two regions: the header, and half-way into the file.
385
497
        self.assertEqual([
386
 
            ('readv', 'index', [(30, 30), (0, 200)], True, 60),
 
498
            ('readv', 'index',
 
499
             [(start_lookup, 800), (0, 200)], True, index._size),
387
500
            ],
388
501
            index._transport._activity)
389
502
        # and the result should be that the key cannot be present, because this
390
503
        # is a trivial index.
391
 
        self.assertEqual([((index._size // 2, ('missing', )), False)],
392
 
            result)
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)
397
 
 
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', ())])
404
 
        # reset the transport log
405
 
        del index._transport._activity[:]
406
 
        result = index._lookup_keys_via_location(
407
 
            [(index._size // 2, ('missing', ))])
408
 
        # this should have asked for a readv request, with adjust_for_latency,
409
 
        # and two regions: the header, and half-way into the file.
410
 
        self.assertEqual([
411
 
            ('readv', 'index', [(36, 36), (0, 200)], True, 72),
412
 
            ],
413
 
            index._transport._activity)
414
 
        # and the result should be that the key cannot be present, because this
415
 
        # is a trivial index and we should not have to do more round trips.
416
 
        self.assertEqual([((index._size // 2, ('missing', )), False)],
417
 
            result)
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)
 
504
        self.assertEqual([((start_lookup, ('40missing', )), False)],
 
505
            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)
421
514
 
422
515
    def test_parsing_non_adjacent_data_trims(self):
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)
 
516
        index = self.make_index(nodes=self.make_nodes(64))
431
517
        result = index._lookup_keys_via_location(
432
518
            [(index._size // 2, ('40', ))])
433
519
        # and the result should be that the key cannot be present, because key is
437
523
            result)
438
524
        # and we should have a parse map that includes the header and the
439
525
        # region that was parsed after trimming.
440
 
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
441
 
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
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))],
442
529
            index._parsed_key_map)
443
530
 
444
531
    def test_parsing_data_handles_parsed_contained_regions(self):
448
535
        # which then trims the start and end so the parsed size is < readv
449
536
        # miniumum.
450
537
        # then a dual lookup (or a reference lookup for that matter) which
451
 
        # abuts or overlaps the parsed region on both sides will need to 
 
538
        # abuts or overlaps the parsed region on both sides will need to
452
539
        # discard the data in the middle, but parse the end as well.
453
540
        #
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 - 
 
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 -
456
543
        # we except both to be found, and the parsed byte map to include the
457
544
        # locations of both keys.
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)
 
545
        index = self.make_index(nodes=self.make_nodes(128))
466
546
        result = index._lookup_keys_via_location(
467
547
            [(index._size // 2, ('40', ))])
468
548
        # and we should have a parse map that includes the header and the
469
549
        # region that was parsed after trimming.
470
 
        self.assertEqual([(0, 3991), (11622, 15534)], index._parsed_byte_map)
471
 
        self.assertEqual([(None, make_key(116)), (make_key(35), make_key(51))],
 
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))],
472
553
            index._parsed_key_map)
473
554
        # now ask for two keys, right before and after the parsed region
474
555
        result = index._lookup_keys_via_location(
475
 
            [(11450, make_key(34)), (15534, make_key(52))])
 
556
            [(11450, self.make_key(34)), (15707, self.make_key(52))])
476
557
        self.assertEqual([
477
 
            ((11450, make_key(34)), (index, make_key(34), make_value(34))),
478
 
            ((15534, make_key(52)), (index, make_key(52), make_value(52))),
 
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))),
479
562
            ],
480
563
            result)
481
 
        self.assertEqual([(0, 3991), (9975, 17799)], index._parsed_byte_map)
 
564
        self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)
482
565
 
483
566
    def test_lookup_missing_key_answers_without_io_when_map_permits(self):
484
567
        # generate a big enough index that we only read some of it on a typical
485
568
        # bisection lookup.
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)
 
569
        index = self.make_index(nodes=self.make_nodes(64))
492
570
        # lookup the keys in the middle of the file
493
571
        result =index._lookup_keys_via_location(
494
572
            [(index._size // 2, ('40', ))])
495
573
        # check the parse map, this determines the test validity
496
 
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
497
 
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
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))],
498
577
            index._parsed_key_map)
499
578
        # reset the transport log
500
579
        del index._transport._activity[:]
502
581
        # not create a new transport request, and should return False (cannot
503
582
        # be in the index) - even when the byte location we ask for is outside
504
583
        # the parsed region
505
 
        # 
506
584
        result = index._lookup_keys_via_location(
507
585
            [(4000, ('40', ))])
508
586
        self.assertEqual([((4000, ('40', )), False)],
512
590
    def test_lookup_present_key_answers_without_io_when_map_permits(self):
513
591
        # generate a big enough index that we only read some of it on a typical
514
592
        # bisection lookup.
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)
 
593
        index = self.make_index(nodes=self.make_nodes(64))
523
594
        # lookup the keys in the middle of the file
524
595
        result =index._lookup_keys_via_location(
525
596
            [(index._size // 2, ('40', ))])
526
597
        # check the parse map, this determines the test validity
527
598
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
528
 
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
599
        self.assertEqual([(None, self.make_key(26)),
 
600
                          (self.make_key(31), self.make_key(48))],
529
601
            index._parsed_key_map)
530
602
        # reset the transport log
531
603
        del index._transport._activity[:]
533
605
        # not create a new transport request, and should return False (cannot
534
606
        # be in the index) - even when the byte location we ask for is outside
535
607
        # the parsed region
536
 
        # 
537
 
        result = index._lookup_keys_via_location([(4000, make_key(40))])
 
608
        #
 
609
        result = index._lookup_keys_via_location([(4000, self.make_key(40))])
538
610
        self.assertEqual(
539
 
            [((4000, make_key(40)), (index, make_key(40), make_value(40)))],
 
611
            [((4000, self.make_key(40)),
 
612
              (index, self.make_key(40), self.make_value(40)))],
540
613
            result)
541
614
        self.assertEqual([], index._transport._activity)
542
615
 
543
616
    def test_lookup_key_below_probed_area(self):
544
617
        # generate a big enough index that we only read some of it on a typical
545
618
        # bisection lookup.
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)
 
619
        index = self.make_index(nodes=self.make_nodes(64))
552
620
        # ask for the key in the middle, but a key that is located in the
553
621
        # unparsed region before the middle.
554
622
        result =index._lookup_keys_via_location(
555
623
            [(index._size // 2, ('30', ))])
556
624
        # check the parse map, this determines the test validity
557
 
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
558
 
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
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))],
559
628
            index._parsed_key_map)
560
629
        self.assertEqual([((index._size // 2, ('30', )), -1)],
561
630
            result)
563
632
    def test_lookup_key_above_probed_area(self):
564
633
        # generate a big enough index that we only read some of it on a typical
565
634
        # bisection lookup.
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)
 
635
        index = self.make_index(nodes=self.make_nodes(64))
572
636
        # ask for the key in the middle, but a key that is located in the
573
637
        # unparsed region after the middle.
574
638
        result =index._lookup_keys_via_location(
575
639
            [(index._size // 2, ('50', ))])
576
640
        # check the parse map, this determines the test validity
577
 
        self.assertEqual([(0, 3972), (5001, 8914)], index._parsed_byte_map)
578
 
        self.assertEqual([(None, make_key(26)), (make_key(31), make_key(48))],
 
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))],
579
644
            index._parsed_key_map)
580
645
        self.assertEqual([((index._size // 2, ('50', )), +1)],
581
646
            result)
584
649
        # generate a big enough index that we only read some of it on a typical
585
650
        # bisection lookup.
586
651
        nodes = []
587
 
        def make_key(number):
588
 
            return (str(number) + 'X'*100,)
589
 
        def make_value(number):
590
 
            return str(number) + 'Y'*100
 
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 = []
591
688
        for counter in range(64):
592
 
            nodes.append((make_key(counter), make_value(counter),
593
 
                ((make_key(counter + 20),),)  ))
 
689
            nodes.append((self.make_key(counter), self.make_value(counter),
 
690
                ((self.make_key(counter + 20),),)  ))
594
691
        index = self.make_index(ref_lists=1, nodes=nodes)
595
692
        # lookup a key in the middle that does not exist, so that when we can
596
693
        # check that the referred-to-keys are not accessed automatically.
597
 
        result =index._lookup_keys_via_location(
598
 
            [(index._size // 2, ('40', ))])
 
694
        index_size = index._size
 
695
        index_center = index_size // 2
 
696
        result = index._lookup_keys_via_location([(index_center, ('40', ))])
599
697
        # check the parse map - only the start and middle should have been
600
698
        # parsed.
601
699
        self.assertEqual([(0, 3890), (6444, 10274)], index._parsed_byte_map)
602
 
        self.assertEqual([(None, make_key(25)), (make_key(37), make_key(52))],
 
700
        self.assertEqual([(None, self.make_key(25)),
 
701
                          (self.make_key(37), self.make_key(52))],
603
702
            index._parsed_key_map)
604
703
        # and check the transport activity likewise.
605
704
        self.assertEqual(
606
 
            [('readv', 'index', [(7906, 800), (0, 200)], True, 15813)],
 
705
            [('readv', 'index', [(index_center, 800), (0, 200)], True,
 
706
                                  index_size)],
607
707
            index._transport._activity)
608
708
        # reset the transport log for testing the reference lookup
609
709
        del index._transport._activity[:]
610
710
        # now looking up a key in the portion of the file already parsed should
611
711
        # only perform IO to resolve its key references.
612
 
        result = index._lookup_keys_via_location([(4000, make_key(40))])
 
712
        result = index._lookup_keys_via_location([(7000, self.make_key(40))])
613
713
        self.assertEqual(
614
 
            [((4000, make_key(40)),
615
 
              (index, make_key(40), make_value(40), ((make_key(60),),)))],
 
714
            [((7000, self.make_key(40)),
 
715
              (index, self.make_key(40), self.make_value(40),
 
716
               ((self.make_key(60),),)))],
616
717
            result)
617
 
        self.assertEqual([('readv', 'index', [(11976, 800)], True, 15813)],
618
 
            index._transport._activity)
 
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)
619
721
 
620
722
    def test_iter_all_entries_empty(self):
621
723
        index = self.make_index()
640
742
            (index, ('ref', ), 'refdata', ((), ))]),
641
743
            set(index.iter_all_entries()))
642
744
 
 
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
 
643
787
    def test_iter_entries_references_resolved(self):
644
788
        index = self.make_index(1, nodes=[
645
789
            (('name', ), 'data', ([('ref', ), ('ref', )], )),
691
835
        self.assertEqual([], list(index.iter_entries([('a', )])))
692
836
 
693
837
    def test_iter_missing_entry_empty_no_size(self):
694
 
        index = self.make_index()
695
 
        index = GraphIndex(index._transport, 'index', None)
696
 
        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', )])))
697
841
 
698
842
    def test_iter_key_prefix_1_element_key_None(self):
699
843
        index = self.make_index()
763
907
            (('name', ), '', ()), (('foo', ), '', ())])
764
908
        self.assertEqual(2, index.key_count())
765
909
 
 
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
 
766
933
    def test_validate_bad_index_errors(self):
767
934
        trans = self.get_transport()
768
935
        trans.put_bytes('name', "not an index\n")
769
 
        index = GraphIndex(trans, 'name', 13)
770
 
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
 
936
        idx = index.GraphIndex(trans, 'name', 13)
 
937
        self.assertRaises(errors.BadIndexFormatSignature, idx.validate)
771
938
 
772
939
    def test_validate_bad_node_refs(self):
773
 
        index = self.make_index(2)
 
940
        idx = self.make_index(2)
774
941
        trans = self.get_transport()
775
942
        content = trans.get_bytes('index')
776
943
        # change the options line to end with a rather than a parseable number
777
944
        new_content = content[:-2] + 'a\n\n'
778
945
        trans.put_bytes('index', new_content)
779
 
        self.assertRaises(errors.BadIndexOptions, index.validate)
 
946
        self.assertRaises(errors.BadIndexOptions, idx.validate)
780
947
 
781
948
    def test_validate_missing_end_line_empty(self):
782
949
        index = self.make_index(2)
802
969
        index = self.make_index(nodes=[(('key', ), 'value', ())])
803
970
        index.validate()
804
971
 
805
 
 
806
 
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
 
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):
807
1067
 
808
1068
    def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
809
 
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
 
1069
        builder = index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
810
1070
        for key, value, references in nodes:
811
1071
            builder.add_node(key, value, references)
812
1072
        stream = builder.finish()
813
1073
        trans = self.get_transport()
814
1074
        size = trans.put_file(name, stream)
815
 
        return GraphIndex(trans, name, size)
 
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
816
1109
 
817
1110
    def test_open_missing_index_no_error(self):
818
1111
        trans = self.get_transport()
819
 
        index1 = GraphIndex(trans, 'missing', 100)
820
 
        index = CombinedGraphIndex([index1])
 
1112
        idx1 = index.GraphIndex(trans, 'missing', 100)
 
1113
        idx = index.CombinedGraphIndex([idx1])
821
1114
 
822
1115
    def test_add_index(self):
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()))
 
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))
827
1145
 
828
1146
    def test_iter_all_entries_empty(self):
829
 
        index = CombinedGraphIndex([])
830
 
        self.assertEqual([], list(index.iter_all_entries()))
 
1147
        idx = index.CombinedGraphIndex([])
 
1148
        self.assertEqual([], list(idx.iter_all_entries()))
831
1149
 
832
1150
    def test_iter_all_entries_children_empty(self):
833
 
        index1 = self.make_index('name')
834
 
        index = CombinedGraphIndex([index1])
835
 
        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()))
836
1154
 
837
1155
    def test_iter_all_entries_simple(self):
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()))
 
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()))
842
1160
 
843
1161
    def test_iter_all_entries_two_indices(self):
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()))
 
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()))
850
1168
 
851
1169
    def test_iter_entries_two_indices_dup_key(self):
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', )])))
 
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', )])))
857
1175
 
858
1176
    def test_iter_all_entries_two_indices_dup_key(self):
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()))
 
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()))
864
1182
 
865
1183
    def test_iter_key_prefix_2_key_element_refs(self):
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)])))
 
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)])))
878
1199
 
879
1200
    def test_iter_nothing_empty(self):
880
 
        index = CombinedGraphIndex([])
881
 
        self.assertEqual([], list(index.iter_entries([])))
 
1201
        idx = index.CombinedGraphIndex([])
 
1202
        self.assertEqual([], list(idx.iter_entries([])))
882
1203
 
883
1204
    def test_iter_nothing_children_empty(self):
884
 
        index1 = self.make_index('name')
885
 
        index = CombinedGraphIndex([index1])
886
 
        self.assertEqual([], list(index.iter_entries([])))
 
1205
        idx1 = self.make_index('name')
 
1206
        idx = index.CombinedGraphIndex([idx1])
 
1207
        self.assertEqual([], list(idx.iter_entries([])))
887
1208
 
888
1209
    def test_iter_all_keys(self):
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
 
 
 
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
 
898
1218
    def test_iter_all_keys_dup_entry(self):
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
 
 
 
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
 
909
1228
    def test_iter_missing_entry_empty(self):
910
 
        index = CombinedGraphIndex([])
911
 
        self.assertEqual([], list(index.iter_entries([('a', )])))
 
1229
        idx = index.CombinedGraphIndex([])
 
1230
        self.assertEqual([], list(idx.iter_entries([('a', )])))
912
1231
 
913
1232
    def test_iter_missing_entry_one_index(self):
914
 
        index1 = self.make_index('1')
915
 
        index = CombinedGraphIndex([index1])
916
 
        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', )])))
917
1236
 
918
1237
    def test_iter_missing_entry_two_index(self):
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
 
 
 
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
 
924
1243
    def test_iter_entry_present_one_index_only(self):
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', )])))
 
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', )])))
930
1249
        # and in the other direction
931
 
        index = CombinedGraphIndex([index2, index1])
932
 
        self.assertEqual([(index1, ('key', ), '')],
933
 
            list(index.iter_entries([('key', )])))
 
1250
        idx = index.CombinedGraphIndex([idx2, idx1])
 
1251
        self.assertEqual([(idx1, ('key', ), '')],
 
1252
                         list(idx.iter_entries([('key', )])))
934
1253
 
935
1254
    def test_key_count_empty(self):
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())
 
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())
940
1259
 
941
1260
    def test_key_count_sums_index_keys(self):
942
 
        index1 = self.make_index('1', nodes=[
 
1261
        idx1 = self.make_index('1', nodes=[
943
1262
            (('1',), '', ()),
944
1263
            (('2',), '', ())])
945
 
        index2 = self.make_index('2', nodes=[(('1',), '', ())])
946
 
        index = CombinedGraphIndex([index1, index2])
947
 
        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())
948
1267
 
949
1268
    def test_validate_bad_child_index_errors(self):
950
1269
        trans = self.get_transport()
951
1270
        trans.put_bytes('name', "not an index\n")
952
 
        index1 = GraphIndex(trans, 'name', 13)
953
 
        index = CombinedGraphIndex([index1])
954
 
        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)
955
1274
 
956
1275
    def test_validate_empty(self):
957
 
        index = CombinedGraphIndex([])
958
 
        index.validate()
959
 
 
960
 
 
961
 
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
 
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):
962
1535
 
963
1536
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
964
 
        result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
 
1537
        result = index.InMemoryGraphIndex(ref_lists, key_elements=key_elements)
965
1538
        result.add_nodes(nodes)
966
1539
        return result
967
1540
 
1088
1661
        index.validate()
1089
1662
 
1090
1663
 
1091
 
class TestGraphIndexPrefixAdapter(TestCaseWithMemoryTransport):
 
1664
class TestGraphIndexPrefixAdapter(tests.TestCaseWithMemoryTransport):
1092
1665
 
1093
 
    def make_index(self, ref_lists=1, key_elements=2, nodes=[], add_callback=False):
1094
 
        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)
1095
1669
        result.add_nodes(nodes)
1096
1670
        if add_callback:
1097
1671
            add_nodes_callback = result.add_nodes
1098
1672
        else:
1099
1673
            add_nodes_callback = None
1100
 
        adapter = GraphIndexPrefixAdapter(result, ('prefix', ), key_elements - 1,
 
1674
        adapter = index.GraphIndexPrefixAdapter(
 
1675
            result, ('prefix', ), key_elements - 1,
1101
1676
            add_nodes_callback=add_nodes_callback)
1102
1677
        return result, adapter
1103
1678
 
1104
1679
    def test_add_node(self):
1105
1680
        index, adapter = self.make_index(add_callback=True)
1106
1681
        adapter.add_node(('key',), 'value', ((('ref',),),))
1107
 
        self.assertEqual(set([(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))]),
 
1682
        self.assertEqual(set([(index, ('prefix', 'key'), 'value',
 
1683
                               ((('prefix', 'ref'),),))]),
1108
1684
            set(index.iter_all_entries()))
1109
1685
 
1110
1686
    def test_add_nodes(self):
1120
1696
            set(index.iter_all_entries()))
1121
1697
 
1122
1698
    def test_construct(self):
1123
 
        index = InMemoryGraphIndex()
1124
 
        adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1)
 
1699
        idx = index.InMemoryGraphIndex()
 
1700
        adapter = index.GraphIndexPrefixAdapter(idx, ('prefix', ), 1)
1125
1701
 
1126
1702
    def test_construct_with_callback(self):
1127
 
        index = InMemoryGraphIndex()
1128
 
        adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1, index.add_nodes)
 
1703
        idx = index.InMemoryGraphIndex()
 
1704
        adapter = index.GraphIndexPrefixAdapter(idx, ('prefix', ), 1,
 
1705
                                                idx.add_nodes)
1129
1706
 
1130
1707
    def test_iter_all_entries_cross_prefix_map_errors(self):
1131
1708
        index, adapter = self.make_index(nodes=[