/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_index.py

merge bzr.dev.

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., 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
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
22
23
 
23
24
 
24
25
class TestGraphIndexBuilder(TestCaseWithMemoryTransport):
27
28
        builder = GraphIndexBuilder()
28
29
        stream = builder.finish()
29
30
        contents = stream.read()
30
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n\n", contents)
 
31
        self.assertEqual(
 
32
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=0\n\n",
 
33
            contents)
31
34
 
32
35
    def test_build_index_empty_two_element_keys(self):
33
36
        builder = GraphIndexBuilder(key_elements=2)
34
37
        stream = builder.finish()
35
38
        contents = stream.read()
36
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\n\n", contents)
 
39
        self.assertEqual(
 
40
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=0\n\n",
 
41
            contents)
37
42
 
38
43
    def test_build_index_one_reference_list_empty(self):
39
44
        builder = GraphIndexBuilder(reference_lists=1)
40
45
        stream = builder.finish()
41
46
        contents = stream.read()
42
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n\n", contents)
 
47
        self.assertEqual(
 
48
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=0\n\n",
 
49
            contents)
43
50
 
44
51
    def test_build_index_two_reference_list_empty(self):
45
52
        builder = GraphIndexBuilder(reference_lists=2)
46
53
        stream = builder.finish()
47
54
        contents = stream.read()
48
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\n\n", contents)
 
55
        self.assertEqual(
 
56
            "Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=0\n\n",
 
57
            contents)
49
58
 
50
59
    def test_build_index_one_node_no_refs(self):
51
60
        builder = GraphIndexBuilder()
52
61
        builder.add_node(('akey', ), 'data')
53
62
        stream = builder.finish()
54
63
        contents = stream.read()
55
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n"
 
64
        self.assertEqual(
 
65
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
56
66
            "akey\x00\x00\x00data\n\n", contents)
57
67
 
58
68
    def test_build_index_one_node_no_refs_accepts_empty_reflist(self):
60
70
        builder.add_node(('akey', ), 'data', ())
61
71
        stream = builder.finish()
62
72
        contents = stream.read()
63
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n"
 
73
        self.assertEqual(
 
74
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
64
75
            "akey\x00\x00\x00data\n\n", contents)
65
76
 
66
77
    def test_build_index_one_node_2_element_keys(self):
71
82
        builder.add_node(('akey', 'secondpart'), 'data')
72
83
        stream = builder.finish()
73
84
        contents = stream.read()
74
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\n"
 
85
        self.assertEqual(
 
86
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=1\n"
75
87
            "akey\x00secondpart\x00\x00\x00data\n\n", contents)
76
88
 
77
89
    def test_add_node_empty_value(self):
79
91
        builder.add_node(('akey', ), '')
80
92
        stream = builder.finish()
81
93
        contents = stream.read()
82
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n"
 
94
        self.assertEqual(
 
95
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
83
96
            "akey\x00\x00\x00\n\n", contents)
84
97
 
85
98
    def test_build_index_nodes_sorted(self):
93
106
        builder.add_node(('2001', ), 'data')
94
107
        stream = builder.finish()
95
108
        contents = stream.read()
96
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n"
 
109
        self.assertEqual(
 
110
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=3\n"
97
111
            "2000\x00\x00\x00data\n"
98
112
            "2001\x00\x00\x00data\n"
99
113
            "2002\x00\x00\x00data\n"
116
130
        builder.add_node(('2001', '2001'), 'data')
117
131
        stream = builder.finish()
118
132
        contents = stream.read()
119
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\n"
 
133
        self.assertEqual(
 
134
            "Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=9\n"
120
135
            "2000\x002000\x00\x00\x00data\n"
121
136
            "2000\x002001\x00\x00\x00data\n"
122
137
            "2000\x002002\x00\x00\x00data\n"
133
148
        builder.add_node(('key', ), 'data', ([], ))
134
149
        stream = builder.finish()
135
150
        contents = stream.read()
136
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n"
 
151
        self.assertEqual(
 
152
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
137
153
            "key\x00\x00\x00data\n"
138
154
            "\n", contents)
139
155
 
142
158
        builder.add_node(('key', 'key2'), 'data', ([], ))
143
159
        stream = builder.finish()
144
160
        contents = stream.read()
145
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=2\n"
 
161
        self.assertEqual(
 
162
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=2\nlen=1\n"
146
163
            "key\x00key2\x00\x00\x00data\n"
147
164
            "\n", contents)
148
165
 
151
168
        builder.add_node(('key', ), 'data', ([], []))
152
169
        stream = builder.finish()
153
170
        contents = stream.read()
154
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\n"
 
171
        self.assertEqual(
 
172
            "Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
155
173
            "key\x00\x00\t\x00data\n"
156
174
            "\n", contents)
157
175
 
161
179
        builder.add_node(('key', ), 'data', ([('reference', )], ))
162
180
        stream = builder.finish()
163
181
        contents = stream.read()
164
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n"
165
 
            "key\x00\x0066\x00data\n"
 
182
        self.assertEqual(
 
183
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=2\n"
 
184
            "key\x00\x0072\x00data\n"
166
185
            "reference\x00\x00\x00data\n"
167
186
            "\n", contents)
168
187
 
173
192
        builder.add_node(('key', ), 'data', ([('reference', ), ('reference2', )], ))
174
193
        stream = builder.finish()
175
194
        contents = stream.read()
176
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n"
177
 
            "key\x00\x00071\r088\x00data\n"
 
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"
178
198
            "reference\x00\x00\x00data\n"
179
199
            "reference2\x00\x00\x00data\n"
180
200
            "\n", contents)
185
205
        builder.add_node(('rey', ), 'data', ([('keference', )], [('keference', )]))
186
206
        stream = builder.finish()
187
207
        contents = stream.read()
188
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\n"
 
208
        self.assertEqual(
 
209
            "Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=2\n"
189
210
            "keference\x00\x00\t\x00data\n"
190
 
            "rey\x00\x0053\t53\x00data\n"
 
211
            "rey\x00\x0059\t59\x00data\n"
191
212
            "\n", contents)
192
213
 
193
214
    def test_add_node_referencing_missing_key_makes_absent(self):
195
216
        builder.add_node(('rey', ), 'data', ([('beference', ), ('aeference2', )], ))
196
217
        stream = builder.finish()
197
218
        contents = stream.read()
198
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n"
 
219
        self.assertEqual(
 
220
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
199
221
            "aeference2\x00a\x00\x00\n"
200
222
            "beference\x00a\x00\x00\n"
201
 
            "rey\x00\x0068\r53\x00data\n"
 
223
            "rey\x00\x00074\r059\x00data\n"
202
224
            "\n", contents)
203
225
 
204
226
    def test_node_references_three_digits(self):
208
230
        builder.add_node(('2-key', ), '', (references, ))
209
231
        stream = builder.finish()
210
232
        contents = stream.read()
211
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n"
 
233
        self.assertEqual(
 
234
            "Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
212
235
            "0\x00a\x00\x00\n"
213
236
            "1\x00a\x00\x00\n"
214
237
            "2\x00a\x00\x00\n"
215
 
            "2-key\x00\x00145\r139\r133\r127\r121\r115\r065\r059\r053\x00\n"
 
238
            "2-key\x00\x00151\r145\r139\r133\r127\r121\r071\r065\r059\x00\n"
216
239
            "3\x00a\x00\x00\n"
217
240
            "4\x00a\x00\x00\n"
218
241
            "5\x00a\x00\x00\n"
228
251
        builder.add_node(('parent', ), '', ([('aail', ), ('zther', )], []))
229
252
        stream = builder.finish()
230
253
        contents = stream.read()
231
 
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\n"
 
254
        self.assertEqual(
 
255
            "Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
232
256
            "aail\x00a\x00\x00\n"
233
 
            "parent\x00\x0053\r78\t\x00\n"
 
257
            "parent\x00\x0059\r84\t\x00\n"
234
258
            "zther\x00a\x00\x00\n"
235
259
            "\n", contents)
236
260
 
326
350
        builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
327
351
        builder.add_node(('reference', 'tokey'), 'data', ([],))
328
352
 
 
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
 
329
360
 
330
361
class TestGraphIndex(TestCaseWithMemoryTransport):
331
362
 
 
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
 
332
377
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
333
378
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
334
 
        for node, value, references in nodes:
335
 
            builder.add_node(node, value, references)
 
379
        for key, value, references in nodes:
 
380
            builder.add_node(key, value, references)
336
381
        stream = builder.finish()
337
 
        trans = self.get_transport()
338
 
        trans.put_file('index', stream)
339
 
        return GraphIndex(trans, 'index')
 
382
        trans = get_transport('trace+' + self.get_url())
 
383
        size = trans.put_file('index', stream)
 
384
        return GraphIndex(trans, 'index', size)
340
385
 
341
386
    def test_open_bad_index_no_error(self):
342
387
        trans = self.get_transport()
343
388
        trans.put_bytes('name', "not an index\n")
344
 
        index = GraphIndex(trans, 'name')
 
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)
345
674
 
346
675
    def test_iter_all_entries_empty(self):
347
676
        index = self.make_index()
366
695
            (index, ('ref', ), 'refdata', ((), ))]),
367
696
            set(index.iter_all_entries()))
368
697
 
 
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
 
369
756
    def test_iteration_absent_skipped(self):
370
757
        index = self.make_index(1, nodes=[
371
758
            (('name', ), 'data', ([('ref', )], ))])
400
787
        index = self.make_index()
401
788
        self.assertEqual([], list(index.iter_entries([('a', )])))
402
789
 
 
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
 
403
795
    def test_iter_key_prefix_1_element_key_None(self):
404
796
        index = self.make_index()
405
797
        self.assertRaises(errors.BadIndexKey, list,
455
847
            (index, ('name', 'fin2'), 'beta', ((), ))]),
456
848
            set(index.iter_entries_prefix([('name', None)])))
457
849
 
 
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
 
458
886
    def test_validate_bad_index_errors(self):
459
887
        trans = self.get_transport()
460
888
        trans.put_bytes('name', "not an index\n")
461
 
        index = GraphIndex(trans, 'name')
 
889
        index = GraphIndex(trans, 'name', 13)
462
890
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
463
891
 
464
892
    def test_validate_bad_node_refs(self):
494
922
        index = self.make_index(nodes=[(('key', ), 'value', ())])
495
923
        index.validate()
496
924
 
 
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
 
497
956
 
498
957
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
499
958
 
500
959
    def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
501
960
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
502
 
        for node, value, references in nodes:
503
 
            builder.add_node(node, value, references)
 
961
        for key, value, references in nodes:
 
962
            builder.add_node(key, value, references)
504
963
        stream = builder.finish()
505
964
        trans = self.get_transport()
506
 
        trans.put_file(name, stream)
507
 
        return GraphIndex(trans, name)
 
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
508
1000
 
509
1001
    def test_open_missing_index_no_error(self):
510
1002
        trans = self.get_transport()
511
 
        index1 = GraphIndex(trans, 'missing')
 
1003
        index1 = GraphIndex(trans, 'missing', 100)
512
1004
        index = CombinedGraphIndex([index1])
513
1005
 
514
1006
    def test_add_index(self):
586
1078
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),
587
1079
            (index2, ('ref', ), 'refdata', ((), ))]),
588
1080
            set(index.iter_entries([('name', ), ('ref', )])))
589
 
 
 
1081
 
590
1082
    def test_iter_all_keys_dup_entry(self):
591
1083
        index1 = self.make_index('1', 1, nodes=[
592
1084
            (('name', ), 'data', ([('ref', )], )),
597
1089
        self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),
598
1090
            (index1, ('ref', ), 'refdata', ((), ))]),
599
1091
            set(index.iter_entries([('name', ), ('ref', )])))
600
 
 
 
1092
 
601
1093
    def test_iter_missing_entry_empty(self):
602
1094
        index = CombinedGraphIndex([])
603
1095
        self.assertEqual([], list(index.iter_entries([('a', )])))
612
1104
        index2 = self.make_index('2')
613
1105
        index = CombinedGraphIndex([index1, index2])
614
1106
        self.assertEqual([], list(index.iter_entries([('a', )])))
615
 
 
 
1107
 
616
1108
    def test_iter_entry_present_one_index_only(self):
617
1109
        index1 = self.make_index('1', nodes=[(('key', ), '', ())])
618
1110
        index2 = self.make_index('2', nodes=[])
624
1116
        self.assertEqual([(index1, ('key', ), '')],
625
1117
            list(index.iter_entries([('key', )])))
626
1118
 
 
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
 
627
1133
    def test_validate_bad_child_index_errors(self):
628
1134
        trans = self.get_transport()
629
1135
        trans.put_bytes('name', "not an index\n")
630
 
        index1 = GraphIndex(trans, 'name')
 
1136
        index1 = GraphIndex(trans, 'name', 13)
631
1137
        index = CombinedGraphIndex([index1])
632
1138
        self.assertRaises(errors.BadIndexFormatSignature, index.validate)
633
1139
 
635
1141
        index = CombinedGraphIndex([])
636
1142
        index.validate()
637
1143
 
 
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
 
638
1274
 
639
1275
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
640
1276
 
745
1381
        index = self.make_index()
746
1382
        self.assertEqual([], list(index.iter_entries(['a'])))
747
1383
 
 
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
 
748
1396
    def test_validate_empty(self):
749
1397
        index = self.make_index()
750
1398
        index.validate()
760
1408
        result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
761
1409
        result.add_nodes(nodes)
762
1410
        if add_callback:
763
 
            add_nodes_callback=result.add_nodes
 
1411
            add_nodes_callback = result.add_nodes
764
1412
        else:
765
 
            add_nodes_callback=None
 
1413
            add_nodes_callback = None
766
1414
        adapter = GraphIndexPrefixAdapter(result, ('prefix', ), key_elements - 1,
767
1415
            add_nodes_callback=add_nodes_callback)
768
1416
        return result, adapter
833
1481
            (index, ('prefix2', 'key2', ), 'data2', ((('prefix2', 'key1', ),),))]),
834
1482
            set(adapter.iter_entries_prefix([('prefix2', None)])))
835
1483
 
 
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
 
836
1496
    def test_validate(self):
837
1497
        index, adapter = self.make_index()
838
1498
        calls = []