~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: 2007-08-09 15:19:06 UTC
  • mfrom: (2681.1.7 send-bundle)
  • Revision ID: pqm@pqm.ubuntu.com-20070809151906-hdn9oyslf2qib2op
Allow omitting -o for bundle, add --format

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
19
from bzrlib import errors
20
20
from bzrlib.index import *
21
21
from bzrlib.tests import TestCaseWithMemoryTransport
22
 
from bzrlib.transport import get_transport
23
22
 
24
23
 
25
24
class TestGraphIndexBuilder(TestCaseWithMemoryTransport):
28
27
        builder = GraphIndexBuilder()
29
28
        stream = builder.finish()
30
29
        contents = stream.read()
31
 
        self.assertEqual(
32
 
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=0\n\n",
33
 
            contents)
 
30
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n\n", contents)
34
31
 
35
32
    def test_build_index_empty_two_element_keys(self):
36
33
        builder = GraphIndexBuilder(key_elements=2)
37
34
        stream = builder.finish()
38
35
        contents = stream.read()
39
 
        self.assertEqual(
40
 
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=0\n\n",
41
 
            contents)
 
36
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\n\n", contents)
42
37
 
43
38
    def test_build_index_one_reference_list_empty(self):
44
39
        builder = GraphIndexBuilder(reference_lists=1)
45
40
        stream = builder.finish()
46
41
        contents = stream.read()
47
 
        self.assertEqual(
48
 
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=0\n\n",
49
 
            contents)
 
42
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n\n", contents)
50
43
 
51
44
    def test_build_index_two_reference_list_empty(self):
52
45
        builder = GraphIndexBuilder(reference_lists=2)
53
46
        stream = builder.finish()
54
47
        contents = stream.read()
55
 
        self.assertEqual(
56
 
            "Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=0\n\n",
57
 
            contents)
 
48
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\n\n", contents)
58
49
 
59
50
    def test_build_index_one_node_no_refs(self):
60
51
        builder = GraphIndexBuilder()
61
52
        builder.add_node(('akey', ), 'data')
62
53
        stream = builder.finish()
63
54
        contents = stream.read()
64
 
        self.assertEqual(
65
 
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
 
55
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n"
66
56
            "akey\x00\x00\x00data\n\n", contents)
67
57
 
68
58
    def test_build_index_one_node_no_refs_accepts_empty_reflist(self):
70
60
        builder.add_node(('akey', ), 'data', ())
71
61
        stream = builder.finish()
72
62
        contents = stream.read()
73
 
        self.assertEqual(
74
 
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
 
63
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n"
75
64
            "akey\x00\x00\x00data\n\n", contents)
76
65
 
77
66
    def test_build_index_one_node_2_element_keys(self):
82
71
        builder.add_node(('akey', 'secondpart'), 'data')
83
72
        stream = builder.finish()
84
73
        contents = stream.read()
85
 
        self.assertEqual(
86
 
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=1\n"
 
74
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\n"
87
75
            "akey\x00secondpart\x00\x00\x00data\n\n", contents)
88
76
 
89
77
    def test_add_node_empty_value(self):
91
79
        builder.add_node(('akey', ), '')
92
80
        stream = builder.finish()
93
81
        contents = stream.read()
94
 
        self.assertEqual(
95
 
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
 
82
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n"
96
83
            "akey\x00\x00\x00\n\n", contents)
97
84
 
98
85
    def test_build_index_nodes_sorted(self):
106
93
        builder.add_node(('2001', ), 'data')
107
94
        stream = builder.finish()
108
95
        contents = stream.read()
109
 
        self.assertEqual(
110
 
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=3\n"
 
96
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n"
111
97
            "2000\x00\x00\x00data\n"
112
98
            "2001\x00\x00\x00data\n"
113
99
            "2002\x00\x00\x00data\n"
130
116
        builder.add_node(('2001', '2001'), 'data')
131
117
        stream = builder.finish()
132
118
        contents = stream.read()
133
 
        self.assertEqual(
134
 
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=9\n"
 
119
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\n"
135
120
            "2000\x002000\x00\x00\x00data\n"
136
121
            "2000\x002001\x00\x00\x00data\n"
137
122
            "2000\x002002\x00\x00\x00data\n"
148
133
        builder.add_node(('key', ), 'data', ([], ))
149
134
        stream = builder.finish()
150
135
        contents = stream.read()
151
 
        self.assertEqual(
152
 
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
 
136
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n"
153
137
            "key\x00\x00\x00data\n"
154
138
            "\n", contents)
155
139
 
158
142
        builder.add_node(('key', 'key2'), 'data', ([], ))
159
143
        stream = builder.finish()
160
144
        contents = stream.read()
161
 
        self.assertEqual(
162
 
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=2\nlen=1\n"
 
145
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=2\n"
163
146
            "key\x00key2\x00\x00\x00data\n"
164
147
            "\n", contents)
165
148
 
168
151
        builder.add_node(('key', ), 'data', ([], []))
169
152
        stream = builder.finish()
170
153
        contents = stream.read()
171
 
        self.assertEqual(
172
 
            "Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
 
154
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\n"
173
155
            "key\x00\x00\t\x00data\n"
174
156
            "\n", contents)
175
157
 
179
161
        builder.add_node(('key', ), 'data', ([('reference', )], ))
180
162
        stream = builder.finish()
181
163
        contents = stream.read()
182
 
        self.assertEqual(
183
 
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=2\n"
184
 
            "key\x00\x0072\x00data\n"
 
164
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n"
 
165
            "key\x00\x0066\x00data\n"
185
166
            "reference\x00\x00\x00data\n"
186
167
            "\n", contents)
187
168
 
192
173
        builder.add_node(('key', ), 'data', ([('reference', ), ('reference2', )], ))
193
174
        stream = builder.finish()
194
175
        contents = stream.read()
195
 
        self.assertEqual(
196
 
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=3\n"
197
 
            "key\x00\x00077\r094\x00data\n"
 
176
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n"
 
177
            "key\x00\x00071\r088\x00data\n"
198
178
            "reference\x00\x00\x00data\n"
199
179
            "reference2\x00\x00\x00data\n"
200
180
            "\n", contents)
205
185
        builder.add_node(('rey', ), 'data', ([('keference', )], [('keference', )]))
206
186
        stream = builder.finish()
207
187
        contents = stream.read()
208
 
        self.assertEqual(
209
 
            "Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=2\n"
 
188
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\n"
210
189
            "keference\x00\x00\t\x00data\n"
211
 
            "rey\x00\x0059\t59\x00data\n"
 
190
            "rey\x00\x0053\t53\x00data\n"
212
191
            "\n", contents)
213
192
 
214
193
    def test_add_node_referencing_missing_key_makes_absent(self):
216
195
        builder.add_node(('rey', ), 'data', ([('beference', ), ('aeference2', )], ))
217
196
        stream = builder.finish()
218
197
        contents = stream.read()
219
 
        self.assertEqual(
220
 
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
 
198
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n"
221
199
            "aeference2\x00a\x00\x00\n"
222
200
            "beference\x00a\x00\x00\n"
223
 
            "rey\x00\x00074\r059\x00data\n"
 
201
            "rey\x00\x0068\r53\x00data\n"
224
202
            "\n", contents)
225
203
 
226
204
    def test_node_references_three_digits(self):
230
208
        builder.add_node(('2-key', ), '', (references, ))
231
209
        stream = builder.finish()
232
210
        contents = stream.read()
233
 
        self.assertEqual(
234
 
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
 
211
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n"
235
212
            "0\x00a\x00\x00\n"
236
213
            "1\x00a\x00\x00\n"
237
214
            "2\x00a\x00\x00\n"
238
 
            "2-key\x00\x00151\r145\r139\r133\r127\r121\r071\r065\r059\x00\n"
 
215
            "2-key\x00\x00145\r139\r133\r127\r121\r115\r065\r059\r053\x00\n"
239
216
            "3\x00a\x00\x00\n"
240
217
            "4\x00a\x00\x00\n"
241
218
            "5\x00a\x00\x00\n"
251
228
        builder.add_node(('parent', ), '', ([('aail', ), ('zther', )], []))
252
229
        stream = builder.finish()
253
230
        contents = stream.read()
254
 
        self.assertEqual(
255
 
            "Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
 
231
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\n"
256
232
            "aail\x00a\x00\x00\n"
257
 
            "parent\x00\x0059\r84\t\x00\n"
 
233
            "parent\x00\x0053\r78\t\x00\n"
258
234
            "zther\x00a\x00\x00\n"
259
235
            "\n", contents)
260
236
 
350
326
        builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
351
327
        builder.add_node(('reference', 'tokey'), 'data', ([],))
352
328
 
353
 
    def test_set_optimize(self):
354
 
        builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
355
 
        builder.set_optimize(for_size=True)
356
 
        self.assertTrue(builder._optimize_for_size)
357
 
        builder.set_optimize(for_size=False)
358
 
        self.assertFalse(builder._optimize_for_size)
359
 
 
360
329
 
361
330
class TestGraphIndex(TestCaseWithMemoryTransport):
362
331
 
363
 
    def make_key(self, number):
364
 
        return (str(number) + 'X'*100,)
365
 
 
366
 
    def make_value(self, number):
367
 
            return str(number) + 'Y'*100
368
 
 
369
 
    def make_nodes(self, count=64):
370
 
        # generate a big enough index that we only read some of it on a typical
371
 
        # bisection lookup.
372
 
        nodes = []
373
 
        for counter in range(count):
374
 
            nodes.append((self.make_key(counter), self.make_value(counter), ()))
375
 
        return nodes
376
 
 
377
332
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
378
333
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
379
 
        for key, value, references in nodes:
380
 
            builder.add_node(key, value, references)
 
334
        for node, value, references in nodes:
 
335
            builder.add_node(node, value, references)
381
336
        stream = builder.finish()
382
 
        trans = get_transport('trace+' + self.get_url())
383
 
        size = trans.put_file('index', stream)
384
 
        return GraphIndex(trans, 'index', size)
 
337
        trans = self.get_transport()
 
338
        trans.put_file('index', stream)
 
339
        return GraphIndex(trans, 'index')
385
340
 
386
341
    def test_open_bad_index_no_error(self):
387
342
        trans = self.get_transport()
388
343
        trans.put_bytes('name', "not an index\n")
389
 
        index = GraphIndex(trans, 'name', 13)
390
 
 
391
 
    def test_open_sets_parsed_map_empty(self):
392
 
        index = self.make_index()
393
 
        self.assertEqual([], index._parsed_byte_map)
394
 
        self.assertEqual([], index._parsed_key_map)
395
 
 
396
 
    def test_key_count_buffers(self):
397
 
        index = self.make_index(nodes=self.make_nodes(2))
398
 
        # reset the transport log
399
 
        del index._transport._activity[:]
400
 
        self.assertEqual(2, index.key_count())
401
 
        # We should have requested reading the header bytes
402
 
        self.assertEqual([
403
 
            ('readv', 'index', [(0, 200)], True, index._size),
404
 
            ],
405
 
            index._transport._activity)
406
 
        # And that should have been enough to trigger reading the whole index
407
 
        # with buffering
408
 
        self.assertIsNot(None, index._nodes)
409
 
 
410
 
    def test_lookup_key_via_location_buffers(self):
411
 
        index = self.make_index()
412
 
        # reset the transport log
413
 
        del index._transport._activity[:]
414
 
        # do a _lookup_keys_via_location call for the middle of the file, which
415
 
        # is what bisection uses.
416
 
        result = index._lookup_keys_via_location(
417
 
            [(index._size // 2, ('missing', ))])
418
 
        # this should have asked for a readv request, with adjust_for_latency,
419
 
        # and two regions: the header, and half-way into the file.
420
 
        self.assertEqual([
421
 
            ('readv', 'index', [(30, 30), (0, 200)], True, 60),
422
 
            ],
423
 
            index._transport._activity)
424
 
        # and the result should be that the key cannot be present, because this
425
 
        # is a trivial index.
426
 
        self.assertEqual([((index._size // 2, ('missing', )), False)],
427
 
            result)
428
 
        # And this should have caused the file to be fully buffered
429
 
        self.assertIsNot(None, index._nodes)
430
 
        self.assertEqual([], index._parsed_byte_map)
431
 
 
432
 
    def test_first_lookup_key_via_location(self):
433
 
        # We need enough data so that the _HEADER_READV doesn't consume the
434
 
        # whole file. We always read 800 bytes for every key, and the local
435
 
        # transport natural expansion is 4096 bytes. So we have to have >8192
436
 
        # bytes or we will trigger "buffer_all".
437
 
        # We also want the 'missing' key to fall within the range that *did*
438
 
        # read
439
 
        nodes = []
440
 
        index = self.make_index(nodes=self.make_nodes(64))
441
 
        # reset the transport log
442
 
        del index._transport._activity[:]
443
 
        # do a _lookup_keys_via_location call for the middle of the file, which
444
 
        # is what bisection uses.
445
 
        start_lookup = index._size // 2
446
 
        result = index._lookup_keys_via_location(
447
 
            [(start_lookup, ('40missing', ))])
448
 
        # this should have asked for a readv request, with adjust_for_latency,
449
 
        # and two regions: the header, and half-way into the file.
450
 
        self.assertEqual([
451
 
            ('readv', 'index',
452
 
             [(start_lookup, 800), (0, 200)], True, index._size),
453
 
            ],
454
 
            index._transport._activity)
455
 
        # and the result should be that the key cannot be present, because this
456
 
        # is a trivial index.
457
 
        self.assertEqual([((start_lookup, ('40missing', )), False)],
458
 
            result)
459
 
        # And this should not have caused the file to be fully buffered
460
 
        self.assertIs(None, index._nodes)
461
 
        # And the regions of the file that have been parsed should be in the
462
 
        # parsed_byte_map and the parsed_key_map
463
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
464
 
        self.assertEqual([(None, self.make_key(26)),
465
 
                          (self.make_key(31), self.make_key(48))],
466
 
                         index._parsed_key_map)
467
 
 
468
 
    def test_parsing_non_adjacent_data_trims(self):
469
 
        index = self.make_index(nodes=self.make_nodes(64))
470
 
        result = index._lookup_keys_via_location(
471
 
            [(index._size // 2, ('40', ))])
472
 
        # and the result should be that the key cannot be present, because key is
473
 
        # in the middle of the observed data from a 4K read - the smallest transport
474
 
        # will do today with this api.
475
 
        self.assertEqual([((index._size // 2, ('40', )), False)],
476
 
            result)
477
 
        # and we should have a parse map that includes the header and the
478
 
        # region that was parsed after trimming.
479
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
480
 
        self.assertEqual([(None, self.make_key(26)),
481
 
                          (self.make_key(31), self.make_key(48))],
482
 
            index._parsed_key_map)
483
 
 
484
 
    def test_parsing_data_handles_parsed_contained_regions(self):
485
 
        # the following patten creates a parsed region that is wholly within a
486
 
        # single result from the readv layer:
487
 
        # .... single-read (readv-minimum-size) ...
488
 
        # which then trims the start and end so the parsed size is < readv
489
 
        # miniumum.
490
 
        # then a dual lookup (or a reference lookup for that matter) which
491
 
        # abuts or overlaps the parsed region on both sides will need to
492
 
        # discard the data in the middle, but parse the end as well.
493
 
        #
494
 
        # we test this by doing a single lookup to seed the data, then
495
 
        # a lookup for two keys that are present, and adjacent -
496
 
        # we except both to be found, and the parsed byte map to include the
497
 
        # locations of both keys.
498
 
        index = self.make_index(nodes=self.make_nodes(128))
499
 
        result = index._lookup_keys_via_location(
500
 
            [(index._size // 2, ('40', ))])
501
 
        # and we should have a parse map that includes the header and the
502
 
        # region that was parsed after trimming.
503
 
        self.assertEqual([(0, 4045), (11759, 15707)], index._parsed_byte_map)
504
 
        self.assertEqual([(None, self.make_key(116)),
505
 
                          (self.make_key(35), self.make_key(51))],
506
 
            index._parsed_key_map)
507
 
        # now ask for two keys, right before and after the parsed region
508
 
        result = index._lookup_keys_via_location(
509
 
            [(11450, self.make_key(34)), (15707, self.make_key(52))])
510
 
        self.assertEqual([
511
 
            ((11450, self.make_key(34)),
512
 
             (index, self.make_key(34), self.make_value(34))),
513
 
            ((15707, self.make_key(52)),
514
 
             (index, self.make_key(52), self.make_value(52))),
515
 
            ],
516
 
            result)
517
 
        self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)
518
 
 
519
 
    def test_lookup_missing_key_answers_without_io_when_map_permits(self):
520
 
        # generate a big enough index that we only read some of it on a typical
521
 
        # bisection lookup.
522
 
        index = self.make_index(nodes=self.make_nodes(64))
523
 
        # lookup the keys in the middle of the file
524
 
        result =index._lookup_keys_via_location(
525
 
            [(index._size // 2, ('40', ))])
526
 
        # check the parse map, this determines the test validity
527
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
528
 
        self.assertEqual([(None, self.make_key(26)),
529
 
                          (self.make_key(31), self.make_key(48))],
530
 
            index._parsed_key_map)
531
 
        # reset the transport log
532
 
        del index._transport._activity[:]
533
 
        # now looking up a key in the portion of the file already parsed should
534
 
        # not create a new transport request, and should return False (cannot
535
 
        # be in the index) - even when the byte location we ask for is outside
536
 
        # the parsed region
537
 
        result = index._lookup_keys_via_location(
538
 
            [(4000, ('40', ))])
539
 
        self.assertEqual([((4000, ('40', )), False)],
540
 
            result)
541
 
        self.assertEqual([], index._transport._activity)
542
 
 
543
 
    def test_lookup_present_key_answers_without_io_when_map_permits(self):
544
 
        # generate a big enough index that we only read some of it on a typical
545
 
        # bisection lookup.
546
 
        index = self.make_index(nodes=self.make_nodes(64))
547
 
        # lookup the keys in the middle of the file
548
 
        result =index._lookup_keys_via_location(
549
 
            [(index._size // 2, ('40', ))])
550
 
        # check the parse map, this determines the test validity
551
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
552
 
        self.assertEqual([(None, self.make_key(26)),
553
 
                          (self.make_key(31), self.make_key(48))],
554
 
            index._parsed_key_map)
555
 
        # reset the transport log
556
 
        del index._transport._activity[:]
557
 
        # now looking up a key in the portion of the file already parsed should
558
 
        # not create a new transport request, and should return False (cannot
559
 
        # be in the index) - even when the byte location we ask for is outside
560
 
        # the parsed region
561
 
        #
562
 
        result = index._lookup_keys_via_location([(4000, self.make_key(40))])
563
 
        self.assertEqual(
564
 
            [((4000, self.make_key(40)),
565
 
              (index, self.make_key(40), self.make_value(40)))],
566
 
            result)
567
 
        self.assertEqual([], index._transport._activity)
568
 
 
569
 
    def test_lookup_key_below_probed_area(self):
570
 
        # generate a big enough index that we only read some of it on a typical
571
 
        # bisection lookup.
572
 
        index = self.make_index(nodes=self.make_nodes(64))
573
 
        # ask for the key in the middle, but a key that is located in the
574
 
        # unparsed region before the middle.
575
 
        result =index._lookup_keys_via_location(
576
 
            [(index._size // 2, ('30', ))])
577
 
        # check the parse map, this determines the test validity
578
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
579
 
        self.assertEqual([(None, self.make_key(26)),
580
 
                          (self.make_key(31), self.make_key(48))],
581
 
            index._parsed_key_map)
582
 
        self.assertEqual([((index._size // 2, ('30', )), -1)],
583
 
            result)
584
 
 
585
 
    def test_lookup_key_above_probed_area(self):
586
 
        # generate a big enough index that we only read some of it on a typical
587
 
        # bisection lookup.
588
 
        index = self.make_index(nodes=self.make_nodes(64))
589
 
        # ask for the key in the middle, but a key that is located in the
590
 
        # unparsed region after the middle.
591
 
        result =index._lookup_keys_via_location(
592
 
            [(index._size // 2, ('50', ))])
593
 
        # check the parse map, this determines the test validity
594
 
        self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
595
 
        self.assertEqual([(None, self.make_key(26)),
596
 
                          (self.make_key(31), self.make_key(48))],
597
 
            index._parsed_key_map)
598
 
        self.assertEqual([((index._size // 2, ('50', )), +1)],
599
 
            result)
600
 
 
601
 
    def test_lookup_key_resolves_references(self):
602
 
        # generate a big enough index that we only read some of it on a typical
603
 
        # bisection lookup.
604
 
        nodes = []
605
 
        for counter in range(99):
606
 
            nodes.append((self.make_key(counter), self.make_value(counter),
607
 
                ((self.make_key(counter + 20),),)  ))
608
 
        index = self.make_index(ref_lists=1, nodes=nodes)
609
 
        # lookup a key in the middle that does not exist, so that when we can
610
 
        # check that the referred-to-keys are not accessed automatically.
611
 
        index_size = index._size
612
 
        index_center = index_size // 2
613
 
        result = index._lookup_keys_via_location(
614
 
            [(index_center, ('40', ))])
615
 
        # check the parse map - only the start and middle should have been
616
 
        # parsed.
617
 
        self.assertEqual([(0, 4027), (10198, 14028)], index._parsed_byte_map)
618
 
        self.assertEqual([(None, self.make_key(17)),
619
 
                          (self.make_key(44), self.make_key(5))],
620
 
            index._parsed_key_map)
621
 
        # and check the transport activity likewise.
622
 
        self.assertEqual(
623
 
            [('readv', 'index', [(index_center, 800), (0, 200)], True,
624
 
                                  index_size)],
625
 
            index._transport._activity)
626
 
        # reset the transport log for testing the reference lookup
627
 
        del index._transport._activity[:]
628
 
        # now looking up a key in the portion of the file already parsed should
629
 
        # only perform IO to resolve its key references.
630
 
        result = index._lookup_keys_via_location([(11000, self.make_key(45))])
631
 
        self.assertEqual(
632
 
            [((11000, self.make_key(45)),
633
 
              (index, self.make_key(45), self.make_value(45),
634
 
               ((self.make_key(65),),)))],
635
 
            result)
636
 
        self.assertEqual([('readv', 'index', [(15093, 800)], True, index_size)],
637
 
            index._transport._activity)
638
 
 
639
 
    def test_lookup_key_can_buffer_all(self):
640
 
        nodes = []
641
 
        for counter in range(64):
642
 
            nodes.append((self.make_key(counter), self.make_value(counter),
643
 
                ((self.make_key(counter + 20),),)  ))
644
 
        index = self.make_index(ref_lists=1, nodes=nodes)
645
 
        # lookup a key in the middle that does not exist, so that when we can
646
 
        # check that the referred-to-keys are not accessed automatically.
647
 
        index_size = index._size
648
 
        index_center = index_size // 2
649
 
        result = index._lookup_keys_via_location([(index_center, ('40', ))])
650
 
        # check the parse map - only the start and middle should have been
651
 
        # parsed.
652
 
        self.assertEqual([(0, 3890), (6444, 10274)], index._parsed_byte_map)
653
 
        self.assertEqual([(None, self.make_key(25)),
654
 
                          (self.make_key(37), self.make_key(52))],
655
 
            index._parsed_key_map)
656
 
        # and check the transport activity likewise.
657
 
        self.assertEqual(
658
 
            [('readv', 'index', [(index_center, 800), (0, 200)], True,
659
 
                                  index_size)],
660
 
            index._transport._activity)
661
 
        # reset the transport log for testing the reference lookup
662
 
        del index._transport._activity[:]
663
 
        # now looking up a key in the portion of the file already parsed should
664
 
        # only perform IO to resolve its key references.
665
 
        result = index._lookup_keys_via_location([(7000, self.make_key(40))])
666
 
        self.assertEqual(
667
 
            [((7000, self.make_key(40)),
668
 
              (index, self.make_key(40), self.make_value(40),
669
 
               ((self.make_key(60),),)))],
670
 
            result)
671
 
        # Resolving the references would have required more data read, and we
672
 
        # are already above the 50% threshold, so it triggered a _buffer_all
673
 
        self.assertEqual([('get', 'index')], index._transport._activity)
 
344
        index = GraphIndex(trans, 'name')
674
345
 
675
346
    def test_iter_all_entries_empty(self):
676
347
        index = self.make_index()
695
366
            (index, ('ref', ), 'refdata', ((), ))]),
696
367
            set(index.iter_all_entries()))
697
368
 
698
 
    def test_iter_entries_buffers_once(self):
699
 
        index = self.make_index(nodes=self.make_nodes(2))
700
 
        # reset the transport log
701
 
        del index._transport._activity[:]
702
 
        self.assertEqual(set([(index, self.make_key(1), self.make_value(1))]),
703
 
                         set(index.iter_entries([self.make_key(1)])))
704
 
        # We should have requested reading the header bytes
705
 
        # But not needed any more than that because it would have triggered a
706
 
        # buffer all
707
 
        self.assertEqual([
708
 
            ('readv', 'index', [(0, 200)], True, index._size),
709
 
            ],
710
 
            index._transport._activity)
711
 
        # And that should have been enough to trigger reading the whole index
712
 
        # with buffering
713
 
        self.assertIsNot(None, index._nodes)
714
 
 
715
 
    def test_iter_entries_buffers_by_bytes_read(self):
716
 
        index = self.make_index(nodes=self.make_nodes(64))
717
 
        list(index.iter_entries([self.make_key(10)]))
718
 
        # The first time through isn't enough to trigger a buffer all
719
 
        self.assertIs(None, index._nodes)
720
 
        self.assertEqual(4096, index._bytes_read)
721
 
        # Grabbing a key in that same page won't trigger a buffer all, as we
722
 
        # still haven't read 50% of the file
723
 
        list(index.iter_entries([self.make_key(11)]))
724
 
        self.assertIs(None, index._nodes)
725
 
        self.assertEqual(4096, index._bytes_read)
726
 
        # We haven't read more data, so reading outside the range won't trigger
727
 
        # a buffer all right away
728
 
        list(index.iter_entries([self.make_key(40)]))
729
 
        self.assertIs(None, index._nodes)
730
 
        self.assertEqual(8192, index._bytes_read)
731
 
        # On the next pass, we will not trigger buffer all if the key is
732
 
        # available without reading more
733
 
        list(index.iter_entries([self.make_key(32)]))
734
 
        self.assertIs(None, index._nodes)
735
 
        # But if we *would* need to read more to resolve it, then we will
736
 
        # buffer all.
737
 
        list(index.iter_entries([self.make_key(60)]))
738
 
        self.assertIsNot(None, index._nodes)
739
 
 
740
 
    def test_iter_entries_references_resolved(self):
741
 
        index = self.make_index(1, nodes=[
742
 
            (('name', ), 'data', ([('ref', ), ('ref', )], )),
743
 
            (('ref', ), 'refdata', ([], ))])
744
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),('ref',)),)),
745
 
            (index, ('ref', ), 'refdata', ((), ))]),
746
 
            set(index.iter_entries([('name',), ('ref',)])))
747
 
 
748
 
    def test_iter_entries_references_2_refs_resolved(self):
749
 
        index = self.make_index(2, nodes=[
750
 
            (('name', ), 'data', ([('ref', )], [('ref', )])),
751
 
            (('ref', ), 'refdata', ([], []))])
752
 
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),), (('ref',),))),
753
 
            (index, ('ref', ), 'refdata', ((), ()))]),
754
 
            set(index.iter_entries([('name',), ('ref',)])))
755
 
 
756
369
    def test_iteration_absent_skipped(self):
757
370
        index = self.make_index(1, nodes=[
758
371
            (('name', ), 'data', ([('ref', )], ))])
787
400
        index = self.make_index()
788
401
        self.assertEqual([], list(index.iter_entries([('a', )])))
789
402
 
790
 
    def test_iter_missing_entry_empty_no_size(self):
791
 
        index = self.make_index()
792
 
        index = GraphIndex(index._transport, 'index', None)
793
 
        self.assertEqual([], list(index.iter_entries([('a', )])))
794
 
 
795
403
    def test_iter_key_prefix_1_element_key_None(self):
796
404
        index = self.make_index()
797
405
        self.assertRaises(errors.BadIndexKey, list,
847
455
            (index, ('name', 'fin2'), 'beta', ((), ))]),
848
456
            set(index.iter_entries_prefix([('name', None)])))
849
457
 
850
 
    def test_key_count_empty(self):
851
 
        index = self.make_index()
852
 
        self.assertEqual(0, index.key_count())
853
 
 
854
 
    def test_key_count_one(self):
855
 
        index = self.make_index(nodes=[(('name', ), '', ())])
856
 
        self.assertEqual(1, index.key_count())
857
 
 
858
 
    def test_key_count_two(self):
859
 
        index = self.make_index(nodes=[
860
 
            (('name', ), '', ()), (('foo', ), '', ())])
861
 
        self.assertEqual(2, index.key_count())
862
 
 
863
 
    def test_read_and_parse_tracks_real_read_value(self):
864
 
        index = self.make_index(nodes=self.make_nodes(10))
865
 
        del index._transport._activity[:]
866
 
        index._read_and_parse([(0, 200)])
867
 
        self.assertEqual([
868
 
            ('readv', 'index', [(0, 200)], True, index._size),
869
 
            ],
870
 
            index._transport._activity)
871
 
        # The readv expansion code will expand the initial request to 4096
872
 
        # bytes, which is more than enough to read the entire index, and we
873
 
        # will track the fact that we read that many bytes.
874
 
        self.assertEqual(index._size, index._bytes_read)
875
 
 
876
 
    def test_read_and_parse_triggers_buffer_all(self):
877
 
        index = self.make_index(key_elements=2, nodes=[
878
 
            (('name', 'fin1'), 'data', ()),
879
 
            (('name', 'fin2'), 'beta', ()),
880
 
            (('ref', 'erence'), 'refdata', ())])
881
 
        self.assertTrue(index._size > 0)
882
 
        self.assertIs(None, index._nodes)
883
 
        index._read_and_parse([(0, index._size)])
884
 
        self.assertIsNot(None, index._nodes)
885
 
 
886
458
    def test_validate_bad_index_errors(self):
887
459
        trans = self.get_transport()
888
460
        trans.put_bytes('name', "not an index\n")
889
 
        index = GraphIndex(trans, 'name', 13)
 
461
        index = GraphIndex(trans, 'name')
890
462
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
891
463
 
892
464
    def test_validate_bad_node_refs(self):
922
494
        index = self.make_index(nodes=[(('key', ), 'value', ())])
923
495
        index.validate()
924
496
 
925
 
    # XXX: external_references tests are duplicated in test_btree_index.  We
926
 
    # probably should have per_graph_index tests...
927
 
    def test_external_references_no_refs(self):
928
 
        index = self.make_index(ref_lists=0, nodes=[])
929
 
        self.assertRaises(ValueError, index.external_references, 0)
930
 
 
931
 
    def test_external_references_no_results(self):
932
 
        index = self.make_index(ref_lists=1, nodes=[
933
 
            (('key',), 'value', ([],))])
934
 
        self.assertEqual(set(), index.external_references(0))
935
 
 
936
 
    def test_external_references_missing_ref(self):
937
 
        missing_key = ('missing',)
938
 
        index = self.make_index(ref_lists=1, nodes=[
939
 
            (('key',), 'value', ([missing_key],))])
940
 
        self.assertEqual(set([missing_key]), index.external_references(0))
941
 
 
942
 
    def test_external_references_multiple_ref_lists(self):
943
 
        missing_key = ('missing',)
944
 
        index = self.make_index(ref_lists=2, nodes=[
945
 
            (('key',), 'value', ([], [missing_key]))])
946
 
        self.assertEqual(set([]), index.external_references(0))
947
 
        self.assertEqual(set([missing_key]), index.external_references(1))
948
 
 
949
 
    def test_external_references_two_records(self):
950
 
        index = self.make_index(ref_lists=1, nodes=[
951
 
            (('key-1',), 'value', ([('key-2',)],)),
952
 
            (('key-2',), 'value', ([],)),
953
 
            ])
954
 
        self.assertEqual(set([]), index.external_references(0))
955
 
 
956
497
 
957
498
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
958
499
 
959
500
    def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
960
501
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
961
 
        for key, value, references in nodes:
962
 
            builder.add_node(key, value, references)
 
502
        for node, value, references in nodes:
 
503
            builder.add_node(node, value, references)
963
504
        stream = builder.finish()
964
505
        trans = self.get_transport()
965
 
        size = trans.put_file(name, stream)
966
 
        return GraphIndex(trans, name, size)
967
 
 
968
 
    def make_combined_index_with_missing(self, missing=['1', '2']):
969
 
        """Create a CombinedGraphIndex which will have missing indexes.
970
 
 
971
 
        This creates a CGI which thinks it has 2 indexes, however they have
972
 
        been deleted. If CGI._reload_func() is called, then it will repopulate
973
 
        with a new index.
974
 
 
975
 
        :param missing: The underlying indexes to delete
976
 
        :return: (CombinedGraphIndex, reload_counter)
977
 
        """
978
 
        index1 = self.make_index('1', nodes=[(('1',), '', ())])
979
 
        index2 = self.make_index('2', nodes=[(('2',), '', ())])
980
 
        index3 = self.make_index('3', nodes=[
981
 
            (('1',), '', ()),
982
 
            (('2',), '', ())])
983
 
 
984
 
        # total_reloads, num_changed, num_unchanged
985
 
        reload_counter = [0, 0, 0]
986
 
        def reload():
987
 
            reload_counter[0] += 1
988
 
            new_indices = [index3]
989
 
            if index._indices == new_indices:
990
 
                reload_counter[2] += 1
991
 
                return False
992
 
            reload_counter[1] += 1
993
 
            index._indices[:] = new_indices
994
 
            return True
995
 
        index = CombinedGraphIndex([index1, index2], reload_func=reload)
996
 
        trans = self.get_transport()
997
 
        for fname in missing:
998
 
            trans.delete(fname)
999
 
        return index, reload_counter
 
506
        trans.put_file(name, stream)
 
507
        return GraphIndex(trans, name)
1000
508
 
1001
509
    def test_open_missing_index_no_error(self):
1002
510
        trans = self.get_transport()
1003
 
        index1 = GraphIndex(trans, 'missing', 100)
 
511
        index1 = GraphIndex(trans, 'missing')
1004
512
        index = CombinedGraphIndex([index1])
1005
513
 
1006
514
    def test_add_index(self):
1078
586
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),
1079
587
            (index2, ('ref', ), 'refdata', ((), ))]),
1080
588
            set(index.iter_entries([('name', ), ('ref', )])))
1081
 
 
 
589
 
1082
590
    def test_iter_all_keys_dup_entry(self):
1083
591
        index1 = self.make_index('1', 1, nodes=[
1084
592
            (('name', ), 'data', ([('ref', )], )),
1089
597
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),
1090
598
            (index1, ('ref', ), 'refdata', ((), ))]),
1091
599
            set(index.iter_entries([('name', ), ('ref', )])))
1092
 
 
 
600
 
1093
601
    def test_iter_missing_entry_empty(self):
1094
602
        index = CombinedGraphIndex([])
1095
603
        self.assertEqual([], list(index.iter_entries([('a', )])))
1104
612
        index2 = self.make_index('2')
1105
613
        index = CombinedGraphIndex([index1, index2])
1106
614
        self.assertEqual([], list(index.iter_entries([('a', )])))
1107
 
 
 
615
 
1108
616
    def test_iter_entry_present_one_index_only(self):
1109
617
        index1 = self.make_index('1', nodes=[(('key', ), '', ())])
1110
618
        index2 = self.make_index('2', nodes=[])
1116
624
        self.assertEqual([(index1, ('key', ), '')],
1117
625
            list(index.iter_entries([('key', )])))
1118
626
 
1119
 
    def test_key_count_empty(self):
1120
 
        index1 = self.make_index('1', nodes=[])
1121
 
        index2 = self.make_index('2', nodes=[])
1122
 
        index = CombinedGraphIndex([index1, index2])
1123
 
        self.assertEqual(0, index.key_count())
1124
 
 
1125
 
    def test_key_count_sums_index_keys(self):
1126
 
        index1 = self.make_index('1', nodes=[
1127
 
            (('1',), '', ()),
1128
 
            (('2',), '', ())])
1129
 
        index2 = self.make_index('2', nodes=[(('1',), '', ())])
1130
 
        index = CombinedGraphIndex([index1, index2])
1131
 
        self.assertEqual(3, index.key_count())
1132
 
 
1133
627
    def test_validate_bad_child_index_errors(self):
1134
628
        trans = self.get_transport()
1135
629
        trans.put_bytes('name', "not an index\n")
1136
 
        index1 = GraphIndex(trans, 'name', 13)
 
630
        index1 = GraphIndex(trans, 'name')
1137
631
        index = CombinedGraphIndex([index1])
1138
632
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
1139
633
 
1141
635
        index = CombinedGraphIndex([])
1142
636
        index.validate()
1143
637
 
1144
 
    def test_key_count_reloads(self):
1145
 
        index, reload_counter = self.make_combined_index_with_missing()
1146
 
        self.assertEqual(2, index.key_count())
1147
 
        self.assertEqual([1, 1, 0], reload_counter)
1148
 
 
1149
 
    def test_key_count_no_reload(self):
1150
 
        index, reload_counter = self.make_combined_index_with_missing()
1151
 
        index._reload_func = None
1152
 
        # Without a _reload_func we just raise the exception
1153
 
        self.assertRaises(errors.NoSuchFile, index.key_count)
1154
 
 
1155
 
    def test_key_count_reloads_and_fails(self):
1156
 
        # We have deleted all underlying indexes, so we will try to reload, but
1157
 
        # still fail. This is mostly to test we don't get stuck in an infinite
1158
 
        # loop trying to reload
1159
 
        index, reload_counter = self.make_combined_index_with_missing(
1160
 
                                    ['1', '2', '3'])
1161
 
        self.assertRaises(errors.NoSuchFile, index.key_count)
1162
 
        self.assertEqual([2, 1, 1], reload_counter)
1163
 
 
1164
 
    def test_iter_entries_reloads(self):
1165
 
        index, reload_counter = self.make_combined_index_with_missing()
1166
 
        result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1167
 
        index3 = index._indices[0]
1168
 
        self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
1169
 
                         result)
1170
 
        self.assertEqual([1, 1, 0], reload_counter)
1171
 
 
1172
 
    def test_iter_entries_reloads_midway(self):
1173
 
        # The first index still looks present, so we get interrupted mid-way
1174
 
        # through
1175
 
        index, reload_counter = self.make_combined_index_with_missing(['2'])
1176
 
        index1, index2 = index._indices
1177
 
        result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1178
 
        index3 = index._indices[0]
1179
 
        # We had already yielded '1', so we just go on to the next, we should
1180
 
        # not yield '1' twice.
1181
 
        self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1182
 
                         result)
1183
 
        self.assertEqual([1, 1, 0], reload_counter)
1184
 
 
1185
 
    def test_iter_entries_no_reload(self):
1186
 
        index, reload_counter = self.make_combined_index_with_missing()
1187
 
        index._reload_func = None
1188
 
        # Without a _reload_func we just raise the exception
1189
 
        self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1190
 
 
1191
 
    def test_iter_entries_reloads_and_fails(self):
1192
 
        index, reload_counter = self.make_combined_index_with_missing(
1193
 
                                    ['1', '2', '3'])
1194
 
        self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1195
 
        self.assertEqual([2, 1, 1], reload_counter)
1196
 
 
1197
 
    def test_iter_all_entries_reloads(self):
1198
 
        index, reload_counter = self.make_combined_index_with_missing()
1199
 
        result = list(index.iter_all_entries())
1200
 
        index3 = index._indices[0]
1201
 
        self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
1202
 
                         result)
1203
 
        self.assertEqual([1, 1, 0], reload_counter)
1204
 
 
1205
 
    def test_iter_all_entries_reloads_midway(self):
1206
 
        index, reload_counter = self.make_combined_index_with_missing(['2'])
1207
 
        index1, index2 = index._indices
1208
 
        result = list(index.iter_all_entries())
1209
 
        index3 = index._indices[0]
1210
 
        # We had already yielded '1', so we just go on to the next, we should
1211
 
        # not yield '1' twice.
1212
 
        self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1213
 
                         result)
1214
 
        self.assertEqual([1, 1, 0], reload_counter)
1215
 
 
1216
 
    def test_iter_all_entries_no_reload(self):
1217
 
        index, reload_counter = self.make_combined_index_with_missing()
1218
 
        index._reload_func = None
1219
 
        self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1220
 
 
1221
 
    def test_iter_all_entries_reloads_and_fails(self):
1222
 
        index, reload_counter = self.make_combined_index_with_missing(
1223
 
                                    ['1', '2', '3'])
1224
 
        self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1225
 
 
1226
 
    def test_iter_entries_prefix_reloads(self):
1227
 
        index, reload_counter = self.make_combined_index_with_missing()
1228
 
        result = list(index.iter_entries_prefix([('1',)]))
1229
 
        index3 = index._indices[0]
1230
 
        self.assertEqual([(index3, ('1',), '')], result)
1231
 
        self.assertEqual([1, 1, 0], reload_counter)
1232
 
 
1233
 
    def test_iter_entries_prefix_reloads_midway(self):
1234
 
        index, reload_counter = self.make_combined_index_with_missing(['2'])
1235
 
        index1, index2 = index._indices
1236
 
        result = list(index.iter_entries_prefix([('1',)]))
1237
 
        index3 = index._indices[0]
1238
 
        # We had already yielded '1', so we just go on to the next, we should
1239
 
        # not yield '1' twice.
1240
 
        self.assertEqual([(index1, ('1',), '')], result)
1241
 
        self.assertEqual([1, 1, 0], reload_counter)
1242
 
 
1243
 
    def test_iter_entries_prefix_no_reload(self):
1244
 
        index, reload_counter = self.make_combined_index_with_missing()
1245
 
        index._reload_func = None
1246
 
        self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1247
 
                                                 [('1',)])
1248
 
 
1249
 
    def test_iter_entries_prefix_reloads_and_fails(self):
1250
 
        index, reload_counter = self.make_combined_index_with_missing(
1251
 
                                    ['1', '2', '3'])
1252
 
        self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1253
 
                                                 [('1',)])
1254
 
 
1255
 
    def test_validate_reloads(self):
1256
 
        index, reload_counter = self.make_combined_index_with_missing()
1257
 
        index.validate()
1258
 
        self.assertEqual([1, 1, 0], reload_counter)
1259
 
 
1260
 
    def test_validate_reloads_midway(self):
1261
 
        index, reload_counter = self.make_combined_index_with_missing(['2'])
1262
 
        index.validate()
1263
 
 
1264
 
    def test_validate_no_reload(self):
1265
 
        index, reload_counter = self.make_combined_index_with_missing()
1266
 
        index._reload_func = None
1267
 
        self.assertRaises(errors.NoSuchFile, index.validate)
1268
 
 
1269
 
    def test_validate_reloads_and_fails(self):
1270
 
        index, reload_counter = self.make_combined_index_with_missing(
1271
 
                                    ['1', '2', '3'])
1272
 
        self.assertRaises(errors.NoSuchFile, index.validate)
1273
 
 
1274
638
 
1275
639
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
1276
640
 
1381
745
        index = self.make_index()
1382
746
        self.assertEqual([], list(index.iter_entries(['a'])))
1383
747
 
1384
 
    def test_key_count_empty(self):
1385
 
        index = self.make_index()
1386
 
        self.assertEqual(0, index.key_count())
1387
 
 
1388
 
    def test_key_count_one(self):
1389
 
        index = self.make_index(nodes=[(('name', ), '')])
1390
 
        self.assertEqual(1, index.key_count())
1391
 
 
1392
 
    def test_key_count_two(self):
1393
 
        index = self.make_index(nodes=[(('name', ), ''), (('foo', ), '')])
1394
 
        self.assertEqual(2, index.key_count())
1395
 
 
1396
748
    def test_validate_empty(self):
1397
749
        index = self.make_index()
1398
750
        index.validate()
1408
760
        result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1409
761
        result.add_nodes(nodes)
1410
762
        if add_callback:
1411
 
            add_nodes_callback = result.add_nodes
 
763
            add_nodes_callback=result.add_nodes
1412
764
        else:
1413
 
            add_nodes_callback = None
 
765
            add_nodes_callback=None
1414
766
        adapter = GraphIndexPrefixAdapter(result, ('prefix', ), key_elements - 1,
1415
767
            add_nodes_callback=add_nodes_callback)
1416
768
        return result, adapter
1481
833
            (index, ('prefix2', 'key2', ), 'data2', ((('prefix2', 'key1', ),),))]),
1482
834
            set(adapter.iter_entries_prefix([('prefix2', None)])))
1483
835
 
1484
 
    def test_key_count_no_matching_keys(self):
1485
 
        index, adapter = self.make_index(nodes=[
1486
 
            (('notprefix', 'key1'), 'data', ((), ))])
1487
 
        self.assertEqual(0, adapter.key_count())
1488
 
 
1489
 
    def test_key_count_some_keys(self):
1490
 
        index, adapter = self.make_index(nodes=[
1491
 
            (('notprefix', 'key1'), 'data', ((), )),
1492
 
            (('prefix', 'key1'), 'data1', ((), )),
1493
 
            (('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1494
 
        self.assertEqual(2, adapter.key_count())
1495
 
 
1496
836
    def test_validate(self):
1497
837
        index, adapter = self.make_index()
1498
838
        calls = []