1
# Copyright (C) 2007 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
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
17
"""Tests for indices."""
19
from bzrlib import errors
20
from bzrlib.index import *
21
from bzrlib.tests import TestCaseWithMemoryTransport
22
from bzrlib.transport import get_transport
25
class TestGraphIndexBuilder(TestCaseWithMemoryTransport):
27
def test_build_index_empty(self):
28
builder = GraphIndexBuilder()
29
stream = builder.finish()
30
contents = stream.read()
32
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=0\n\n",
35
def test_build_index_empty_two_element_keys(self):
36
builder = GraphIndexBuilder(key_elements=2)
37
stream = builder.finish()
38
contents = stream.read()
40
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=0\n\n",
43
def test_build_index_one_reference_list_empty(self):
44
builder = GraphIndexBuilder(reference_lists=1)
45
stream = builder.finish()
46
contents = stream.read()
48
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=0\n\n",
51
def test_build_index_two_reference_list_empty(self):
52
builder = GraphIndexBuilder(reference_lists=2)
53
stream = builder.finish()
54
contents = stream.read()
56
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=0\n\n",
59
def test_build_index_one_node_no_refs(self):
60
builder = GraphIndexBuilder()
61
builder.add_node(('akey', ), 'data')
62
stream = builder.finish()
63
contents = stream.read()
65
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
66
"akey\x00\x00\x00data\n\n", contents)
68
def test_build_index_one_node_no_refs_accepts_empty_reflist(self):
69
builder = GraphIndexBuilder()
70
builder.add_node(('akey', ), 'data', ())
71
stream = builder.finish()
72
contents = stream.read()
74
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
75
"akey\x00\x00\x00data\n\n", contents)
77
def test_build_index_one_node_2_element_keys(self):
78
# multipart keys are separated by \x00 - because they are fixed length,
79
# not variable this does not cause any issues, and seems clearer to the
81
builder = GraphIndexBuilder(key_elements=2)
82
builder.add_node(('akey', 'secondpart'), 'data')
83
stream = builder.finish()
84
contents = stream.read()
86
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=1\n"
87
"akey\x00secondpart\x00\x00\x00data\n\n", contents)
89
def test_add_node_empty_value(self):
90
builder = GraphIndexBuilder()
91
builder.add_node(('akey', ), '')
92
stream = builder.finish()
93
contents = stream.read()
95
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
96
"akey\x00\x00\x00\n\n", contents)
98
def test_build_index_nodes_sorted(self):
99
# the highest sorted node comes first.
100
builder = GraphIndexBuilder()
101
# use three to have a good chance of glitching dictionary hash
102
# lookups etc. Insert in randomish order that is not correct
103
# and not the reverse of the correct order.
104
builder.add_node(('2002', ), 'data')
105
builder.add_node(('2000', ), 'data')
106
builder.add_node(('2001', ), 'data')
107
stream = builder.finish()
108
contents = stream.read()
110
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=3\n"
111
"2000\x00\x00\x00data\n"
112
"2001\x00\x00\x00data\n"
113
"2002\x00\x00\x00data\n"
116
def test_build_index_2_element_key_nodes_sorted(self):
117
# multiple element keys are sorted first-key, second-key.
118
builder = GraphIndexBuilder(key_elements=2)
119
# use three values of each key element, to have a good chance of
120
# glitching dictionary hash lookups etc. Insert in randomish order that
121
# is not correct and not the reverse of the correct order.
122
builder.add_node(('2002', '2002'), 'data')
123
builder.add_node(('2002', '2000'), 'data')
124
builder.add_node(('2002', '2001'), 'data')
125
builder.add_node(('2000', '2002'), 'data')
126
builder.add_node(('2000', '2000'), 'data')
127
builder.add_node(('2000', '2001'), 'data')
128
builder.add_node(('2001', '2002'), 'data')
129
builder.add_node(('2001', '2000'), 'data')
130
builder.add_node(('2001', '2001'), 'data')
131
stream = builder.finish()
132
contents = stream.read()
134
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=9\n"
135
"2000\x002000\x00\x00\x00data\n"
136
"2000\x002001\x00\x00\x00data\n"
137
"2000\x002002\x00\x00\x00data\n"
138
"2001\x002000\x00\x00\x00data\n"
139
"2001\x002001\x00\x00\x00data\n"
140
"2001\x002002\x00\x00\x00data\n"
141
"2002\x002000\x00\x00\x00data\n"
142
"2002\x002001\x00\x00\x00data\n"
143
"2002\x002002\x00\x00\x00data\n"
146
def test_build_index_reference_lists_are_included_one(self):
147
builder = GraphIndexBuilder(reference_lists=1)
148
builder.add_node(('key', ), 'data', ([], ))
149
stream = builder.finish()
150
contents = stream.read()
152
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
153
"key\x00\x00\x00data\n"
156
def test_build_index_reference_lists_with_2_element_keys(self):
157
builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
158
builder.add_node(('key', 'key2'), 'data', ([], ))
159
stream = builder.finish()
160
contents = stream.read()
162
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=2\nlen=1\n"
163
"key\x00key2\x00\x00\x00data\n"
166
def test_build_index_reference_lists_are_included_two(self):
167
builder = GraphIndexBuilder(reference_lists=2)
168
builder.add_node(('key', ), 'data', ([], []))
169
stream = builder.finish()
170
contents = stream.read()
172
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
173
"key\x00\x00\t\x00data\n"
176
def test_node_references_are_byte_offsets(self):
177
builder = GraphIndexBuilder(reference_lists=1)
178
builder.add_node(('reference', ), 'data', ([], ))
179
builder.add_node(('key', ), 'data', ([('reference', )], ))
180
stream = builder.finish()
181
contents = stream.read()
183
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=2\n"
184
"key\x00\x0072\x00data\n"
185
"reference\x00\x00\x00data\n"
188
def test_node_references_are_cr_delimited(self):
189
builder = GraphIndexBuilder(reference_lists=1)
190
builder.add_node(('reference', ), 'data', ([], ))
191
builder.add_node(('reference2', ), 'data', ([], ))
192
builder.add_node(('key', ), 'data', ([('reference', ), ('reference2', )], ))
193
stream = builder.finish()
194
contents = stream.read()
196
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=3\n"
197
"key\x00\x00077\r094\x00data\n"
198
"reference\x00\x00\x00data\n"
199
"reference2\x00\x00\x00data\n"
202
def test_multiple_reference_lists_are_tab_delimited(self):
203
builder = GraphIndexBuilder(reference_lists=2)
204
builder.add_node(('keference', ), 'data', ([], []))
205
builder.add_node(('rey', ), 'data', ([('keference', )], [('keference', )]))
206
stream = builder.finish()
207
contents = stream.read()
209
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=2\n"
210
"keference\x00\x00\t\x00data\n"
211
"rey\x00\x0059\t59\x00data\n"
214
def test_add_node_referencing_missing_key_makes_absent(self):
215
builder = GraphIndexBuilder(reference_lists=1)
216
builder.add_node(('rey', ), 'data', ([('beference', ), ('aeference2', )], ))
217
stream = builder.finish()
218
contents = stream.read()
220
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
221
"aeference2\x00a\x00\x00\n"
222
"beference\x00a\x00\x00\n"
223
"rey\x00\x00074\r059\x00data\n"
226
def test_node_references_three_digits(self):
227
# test the node digit expands as needed.
228
builder = GraphIndexBuilder(reference_lists=1)
229
references = [(str(val), ) for val in reversed(range(9))]
230
builder.add_node(('2-key', ), '', (references, ))
231
stream = builder.finish()
232
contents = stream.read()
234
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
238
"2-key\x00\x00151\r145\r139\r133\r127\r121\r071\r065\r059\x00\n"
247
def test_absent_has_no_reference_overhead(self):
248
# the offsets after an absent record should be correct when there are
249
# >1 reference lists.
250
builder = GraphIndexBuilder(reference_lists=2)
251
builder.add_node(('parent', ), '', ([('aail', ), ('zther', )], []))
252
stream = builder.finish()
253
contents = stream.read()
255
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
256
"aail\x00a\x00\x00\n"
257
"parent\x00\x0059\r84\t\x00\n"
258
"zther\x00a\x00\x00\n"
261
def test_add_node_bad_key(self):
262
builder = GraphIndexBuilder()
263
for bad_char in '\t\n\x0b\x0c\r\x00 ':
264
self.assertRaises(errors.BadIndexKey, builder.add_node,
265
('a%skey' % bad_char, ), 'data')
266
self.assertRaises(errors.BadIndexKey, builder.add_node,
268
self.assertRaises(errors.BadIndexKey, builder.add_node,
269
'not-a-tuple', 'data')
271
self.assertRaises(errors.BadIndexKey, builder.add_node,
274
self.assertRaises(errors.BadIndexKey, builder.add_node,
275
('primary', 'secondary'), 'data')
276
# secondary key elements get checked too:
277
builder = GraphIndexBuilder(key_elements=2)
278
for bad_char in '\t\n\x0b\x0c\r\x00 ':
279
self.assertRaises(errors.BadIndexKey, builder.add_node,
280
('prefix', 'a%skey' % bad_char), 'data')
282
def test_add_node_bad_data(self):
283
builder = GraphIndexBuilder()
284
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
286
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
289
def test_add_node_bad_mismatched_ref_lists_length(self):
290
builder = GraphIndexBuilder()
291
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
293
builder = GraphIndexBuilder(reference_lists=1)
294
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
296
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
298
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
300
builder = GraphIndexBuilder(reference_lists=2)
301
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
303
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
305
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
306
'data aa', ([], [], []))
308
def test_add_node_bad_key_in_reference_lists(self):
309
# first list, first key - trivial
310
builder = GraphIndexBuilder(reference_lists=1)
311
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
312
'data aa', ([('a key', )], ))
313
# references keys must be tuples too
314
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
315
'data aa', (['not-a-tuple'], ))
317
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
320
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
321
'data aa', ([('primary', 'secondary')], ))
322
# need to check more than the first key in the list
323
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
324
'data aa', ([('agoodkey', ), ('that is a bad key', )], ))
325
# and if there is more than one list it should be getting checked
327
builder = GraphIndexBuilder(reference_lists=2)
328
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
329
'data aa', ([], ['a bad key']))
331
def test_add_duplicate_key(self):
332
builder = GraphIndexBuilder()
333
builder.add_node(('key', ), 'data')
334
self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node, ('key', ),
337
def test_add_duplicate_key_2_elements(self):
338
builder = GraphIndexBuilder(key_elements=2)
339
builder.add_node(('key', 'key'), 'data')
340
self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node,
341
('key', 'key'), 'data')
343
def test_add_key_after_referencing_key(self):
344
builder = GraphIndexBuilder(reference_lists=1)
345
builder.add_node(('key', ), 'data', ([('reference', )], ))
346
builder.add_node(('reference', ), 'data', ([],))
348
def test_add_key_after_referencing_key_2_elements(self):
349
builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
350
builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
351
builder.add_node(('reference', 'tokey'), 'data', ([],))
354
class TestGraphIndex(TestCaseWithMemoryTransport):
356
def make_key(self, number):
357
return (str(number) + 'X'*100,)
359
def make_value(self, number):
360
return str(number) + 'Y'*100
362
def make_nodes(self, count=64):
363
# generate a big enough index that we only read some of it on a typical
366
for counter in range(count):
367
nodes.append((self.make_key(counter), self.make_value(counter), ()))
370
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
371
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
372
for key, value, references in nodes:
373
builder.add_node(key, value, references)
374
stream = builder.finish()
375
trans = get_transport('trace+' + self.get_url())
376
size = trans.put_file('index', stream)
377
return GraphIndex(trans, 'index', size)
379
def test_open_bad_index_no_error(self):
380
trans = self.get_transport()
381
trans.put_bytes('name', "not an index\n")
382
index = GraphIndex(trans, 'name', 13)
384
def test_open_sets_parsed_map_empty(self):
385
index = self.make_index()
386
self.assertEqual([], index._parsed_byte_map)
387
self.assertEqual([], index._parsed_key_map)
389
def test_key_count_buffers(self):
390
index = self.make_index(nodes=self.make_nodes(2))
391
# reset the transport log
392
del index._transport._activity[:]
393
self.assertEqual(2, index.key_count())
394
# We should have requested reading the header bytes
396
('readv', 'index', [(0, 200)], True, index._size),
398
index._transport._activity)
399
# And that should have been enough to trigger reading the whole index
401
self.assertIsNot(None, index._nodes)
403
def test_lookup_key_via_location_buffers(self):
404
index = self.make_index()
405
# reset the transport log
406
del index._transport._activity[:]
407
# do a _lookup_keys_via_location call for the middle of the file, which
408
# is what bisection uses.
409
result = index._lookup_keys_via_location(
410
[(index._size // 2, ('missing', ))])
411
# this should have asked for a readv request, with adjust_for_latency,
412
# and two regions: the header, and half-way into the file.
414
('readv', 'index', [(30, 30), (0, 200)], True, 60),
416
index._transport._activity)
417
# and the result should be that the key cannot be present, because this
418
# is a trivial index.
419
self.assertEqual([((index._size // 2, ('missing', )), False)],
421
# And this should have caused the file to be fully buffered
422
self.assertIsNot(None, index._nodes)
423
self.assertEqual([], index._parsed_byte_map)
425
def test_first_lookup_key_via_location(self):
426
# We need enough data so that the _HEADER_READV doesn't consume the
427
# whole file. We always read 800 bytes for every key, and the local
428
# transport natural expansion is 4096 bytes. So we have to have >8192
429
# bytes or we will trigger "buffer_all".
430
# We also want the 'missing' key to fall within the range that *did*
433
index = self.make_index(nodes=self.make_nodes(64))
434
# reset the transport log
435
del index._transport._activity[:]
436
# do a _lookup_keys_via_location call for the middle of the file, which
437
# is what bisection uses.
438
start_lookup = index._size // 2
439
result = index._lookup_keys_via_location(
440
[(start_lookup, ('40missing', ))])
441
# this should have asked for a readv request, with adjust_for_latency,
442
# and two regions: the header, and half-way into the file.
445
[(start_lookup, 800), (0, 200)], True, index._size),
447
index._transport._activity)
448
# and the result should be that the key cannot be present, because this
449
# is a trivial index.
450
self.assertEqual([((start_lookup, ('40missing', )), False)],
452
# And this should not have caused the file to be fully buffered
453
self.assertIs(None, index._nodes)
454
# And the regions of the file that have been parsed should be in the
455
# parsed_byte_map and the parsed_key_map
456
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
457
self.assertEqual([(None, self.make_key(26)),
458
(self.make_key(31), self.make_key(48))],
459
index._parsed_key_map)
461
def test_parsing_non_adjacent_data_trims(self):
462
index = self.make_index(nodes=self.make_nodes(64))
463
result = index._lookup_keys_via_location(
464
[(index._size // 2, ('40', ))])
465
# and the result should be that the key cannot be present, because key is
466
# in the middle of the observed data from a 4K read - the smallest transport
467
# will do today with this api.
468
self.assertEqual([((index._size // 2, ('40', )), False)],
470
# and we should have a parse map that includes the header and the
471
# region that was parsed after trimming.
472
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
473
self.assertEqual([(None, self.make_key(26)),
474
(self.make_key(31), self.make_key(48))],
475
index._parsed_key_map)
477
def test_parsing_data_handles_parsed_contained_regions(self):
478
# the following patten creates a parsed region that is wholly within a
479
# single result from the readv layer:
480
# .... single-read (readv-minimum-size) ...
481
# which then trims the start and end so the parsed size is < readv
483
# then a dual lookup (or a reference lookup for that matter) which
484
# abuts or overlaps the parsed region on both sides will need to
485
# discard the data in the middle, but parse the end as well.
487
# we test this by doing a single lookup to seed the data, then
488
# a lookup for two keys that are present, and adjacent -
489
# we except both to be found, and the parsed byte map to include the
490
# locations of both keys.
491
index = self.make_index(nodes=self.make_nodes(128))
492
result = index._lookup_keys_via_location(
493
[(index._size // 2, ('40', ))])
494
# and we should have a parse map that includes the header and the
495
# region that was parsed after trimming.
496
self.assertEqual([(0, 4045), (11759, 15707)], index._parsed_byte_map)
497
self.assertEqual([(None, self.make_key(116)),
498
(self.make_key(35), self.make_key(51))],
499
index._parsed_key_map)
500
# now ask for two keys, right before and after the parsed region
501
result = index._lookup_keys_via_location(
502
[(11450, self.make_key(34)), (15707, self.make_key(52))])
504
((11450, self.make_key(34)),
505
(index, self.make_key(34), self.make_value(34))),
506
((15707, self.make_key(52)),
507
(index, self.make_key(52), self.make_value(52))),
510
self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)
512
def test_lookup_missing_key_answers_without_io_when_map_permits(self):
513
# generate a big enough index that we only read some of it on a typical
515
index = self.make_index(nodes=self.make_nodes(64))
516
# lookup the keys in the middle of the file
517
result =index._lookup_keys_via_location(
518
[(index._size // 2, ('40', ))])
519
# check the parse map, this determines the test validity
520
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
521
self.assertEqual([(None, self.make_key(26)),
522
(self.make_key(31), self.make_key(48))],
523
index._parsed_key_map)
524
# reset the transport log
525
del index._transport._activity[:]
526
# now looking up a key in the portion of the file already parsed should
527
# not create a new transport request, and should return False (cannot
528
# be in the index) - even when the byte location we ask for is outside
530
result = index._lookup_keys_via_location(
532
self.assertEqual([((4000, ('40', )), False)],
534
self.assertEqual([], index._transport._activity)
536
def test_lookup_present_key_answers_without_io_when_map_permits(self):
537
# generate a big enough index that we only read some of it on a typical
539
index = self.make_index(nodes=self.make_nodes(64))
540
# lookup the keys in the middle of the file
541
result =index._lookup_keys_via_location(
542
[(index._size // 2, ('40', ))])
543
# check the parse map, this determines the test validity
544
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
545
self.assertEqual([(None, self.make_key(26)),
546
(self.make_key(31), self.make_key(48))],
547
index._parsed_key_map)
548
# reset the transport log
549
del index._transport._activity[:]
550
# now looking up a key in the portion of the file already parsed should
551
# not create a new transport request, and should return False (cannot
552
# be in the index) - even when the byte location we ask for is outside
555
result = index._lookup_keys_via_location([(4000, self.make_key(40))])
557
[((4000, self.make_key(40)),
558
(index, self.make_key(40), self.make_value(40)))],
560
self.assertEqual([], index._transport._activity)
562
def test_lookup_key_below_probed_area(self):
563
# generate a big enough index that we only read some of it on a typical
565
index = self.make_index(nodes=self.make_nodes(64))
566
# ask for the key in the middle, but a key that is located in the
567
# unparsed region before the middle.
568
result =index._lookup_keys_via_location(
569
[(index._size // 2, ('30', ))])
570
# check the parse map, this determines the test validity
571
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
572
self.assertEqual([(None, self.make_key(26)),
573
(self.make_key(31), self.make_key(48))],
574
index._parsed_key_map)
575
self.assertEqual([((index._size // 2, ('30', )), -1)],
578
def test_lookup_key_above_probed_area(self):
579
# generate a big enough index that we only read some of it on a typical
581
index = self.make_index(nodes=self.make_nodes(64))
582
# ask for the key in the middle, but a key that is located in the
583
# unparsed region after the middle.
584
result =index._lookup_keys_via_location(
585
[(index._size // 2, ('50', ))])
586
# check the parse map, this determines the test validity
587
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
588
self.assertEqual([(None, self.make_key(26)),
589
(self.make_key(31), self.make_key(48))],
590
index._parsed_key_map)
591
self.assertEqual([((index._size // 2, ('50', )), +1)],
594
def test_lookup_key_resolves_references(self):
595
# generate a big enough index that we only read some of it on a typical
598
for counter in range(99):
599
nodes.append((self.make_key(counter), self.make_value(counter),
600
((self.make_key(counter + 20),),) ))
601
index = self.make_index(ref_lists=1, nodes=nodes)
602
# lookup a key in the middle that does not exist, so that when we can
603
# check that the referred-to-keys are not accessed automatically.
604
index_size = index._size
605
index_center = index_size // 2
606
result = index._lookup_keys_via_location(
607
[(index_center, ('40', ))])
608
# check the parse map - only the start and middle should have been
610
self.assertEqual([(0, 4027), (10198, 14028)], index._parsed_byte_map)
611
self.assertEqual([(None, self.make_key(17)),
612
(self.make_key(44), self.make_key(5))],
613
index._parsed_key_map)
614
# and check the transport activity likewise.
616
[('readv', 'index', [(index_center, 800), (0, 200)], True,
618
index._transport._activity)
619
# reset the transport log for testing the reference lookup
620
del index._transport._activity[:]
621
# now looking up a key in the portion of the file already parsed should
622
# only perform IO to resolve its key references.
623
result = index._lookup_keys_via_location([(11000, self.make_key(45))])
625
[((11000, self.make_key(45)),
626
(index, self.make_key(45), self.make_value(45),
627
((self.make_key(65),),)))],
629
self.assertEqual([('readv', 'index', [(15093, 800)], True, index_size)],
630
index._transport._activity)
632
def test_lookup_key_can_buffer_all(self):
634
for counter in range(64):
635
nodes.append((self.make_key(counter), self.make_value(counter),
636
((self.make_key(counter + 20),),) ))
637
index = self.make_index(ref_lists=1, nodes=nodes)
638
# lookup a key in the middle that does not exist, so that when we can
639
# check that the referred-to-keys are not accessed automatically.
640
index_size = index._size
641
index_center = index_size // 2
642
result = index._lookup_keys_via_location([(index_center, ('40', ))])
643
# check the parse map - only the start and middle should have been
645
self.assertEqual([(0, 3890), (6444, 10274)], index._parsed_byte_map)
646
self.assertEqual([(None, self.make_key(25)),
647
(self.make_key(37), self.make_key(52))],
648
index._parsed_key_map)
649
# and check the transport activity likewise.
651
[('readv', 'index', [(index_center, 800), (0, 200)], True,
653
index._transport._activity)
654
# reset the transport log for testing the reference lookup
655
del index._transport._activity[:]
656
# now looking up a key in the portion of the file already parsed should
657
# only perform IO to resolve its key references.
658
result = index._lookup_keys_via_location([(7000, self.make_key(40))])
660
[((7000, self.make_key(40)),
661
(index, self.make_key(40), self.make_value(40),
662
((self.make_key(60),),)))],
664
# Resolving the references would have required more data read, and we
665
# are already above the 50% threshold, so it triggered a _buffer_all
666
self.assertEqual([('get', 'index')], index._transport._activity)
668
def test_iter_all_entries_empty(self):
669
index = self.make_index()
670
self.assertEqual([], list(index.iter_all_entries()))
672
def test_iter_all_entries_simple(self):
673
index = self.make_index(nodes=[(('name', ), 'data', ())])
674
self.assertEqual([(index, ('name', ), 'data')],
675
list(index.iter_all_entries()))
677
def test_iter_all_entries_simple_2_elements(self):
678
index = self.make_index(key_elements=2,
679
nodes=[(('name', 'surname'), 'data', ())])
680
self.assertEqual([(index, ('name', 'surname'), 'data')],
681
list(index.iter_all_entries()))
683
def test_iter_all_entries_references_resolved(self):
684
index = self.make_index(1, nodes=[
685
(('name', ), 'data', ([('ref', )], )),
686
(('ref', ), 'refdata', ([], ))])
687
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
688
(index, ('ref', ), 'refdata', ((), ))]),
689
set(index.iter_all_entries()))
691
def test_iter_entries_buffers_once(self):
692
index = self.make_index(nodes=self.make_nodes(2))
693
# reset the transport log
694
del index._transport._activity[:]
695
self.assertEqual(set([(index, self.make_key(1), self.make_value(1))]),
696
set(index.iter_entries([self.make_key(1)])))
697
# We should have requested reading the header bytes
698
# But not needed any more than that because it would have triggered a
701
('readv', 'index', [(0, 200)], True, index._size),
703
index._transport._activity)
704
# And that should have been enough to trigger reading the whole index
706
self.assertIsNot(None, index._nodes)
708
def test_iter_entries_buffers_by_bytes_read(self):
709
index = self.make_index(nodes=self.make_nodes(64))
710
list(index.iter_entries([self.make_key(10)]))
711
# The first time through isn't enough to trigger a buffer all
712
self.assertIs(None, index._nodes)
713
self.assertEqual(4096, index._bytes_read)
714
# Grabbing a key in that same page won't trigger a buffer all, as we
715
# still haven't read 50% of the file
716
list(index.iter_entries([self.make_key(11)]))
717
self.assertIs(None, index._nodes)
718
self.assertEqual(4096, index._bytes_read)
719
# We haven't read more data, so reading outside the range won't trigger
720
# a buffer all right away
721
list(index.iter_entries([self.make_key(40)]))
722
self.assertIs(None, index._nodes)
723
self.assertEqual(8192, index._bytes_read)
724
# On the next pass, we will not trigger buffer all if the key is
725
# available without reading more
726
list(index.iter_entries([self.make_key(32)]))
727
self.assertIs(None, index._nodes)
728
# But if we *would* need to read more to resolve it, then we will
730
list(index.iter_entries([self.make_key(60)]))
731
self.assertIsNot(None, index._nodes)
733
def test_iter_entries_references_resolved(self):
734
index = self.make_index(1, nodes=[
735
(('name', ), 'data', ([('ref', ), ('ref', )], )),
736
(('ref', ), 'refdata', ([], ))])
737
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),('ref',)),)),
738
(index, ('ref', ), 'refdata', ((), ))]),
739
set(index.iter_entries([('name',), ('ref',)])))
741
def test_iter_entries_references_2_refs_resolved(self):
742
index = self.make_index(2, nodes=[
743
(('name', ), 'data', ([('ref', )], [('ref', )])),
744
(('ref', ), 'refdata', ([], []))])
745
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),), (('ref',),))),
746
(index, ('ref', ), 'refdata', ((), ()))]),
747
set(index.iter_entries([('name',), ('ref',)])))
749
def test_iteration_absent_skipped(self):
750
index = self.make_index(1, nodes=[
751
(('name', ), 'data', ([('ref', )], ))])
752
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
753
set(index.iter_all_entries()))
754
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
755
set(index.iter_entries([('name', )])))
756
self.assertEqual([], list(index.iter_entries([('ref', )])))
758
def test_iteration_absent_skipped_2_element_keys(self):
759
index = self.make_index(1, key_elements=2, nodes=[
760
(('name', 'fin'), 'data', ([('ref', 'erence')], ))])
761
self.assertEqual(set([(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
762
set(index.iter_all_entries()))
763
self.assertEqual(set([(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
764
set(index.iter_entries([('name', 'fin')])))
765
self.assertEqual([], list(index.iter_entries([('ref', 'erence')])))
767
def test_iter_all_keys(self):
768
index = self.make_index(1, nodes=[
769
(('name', ), 'data', ([('ref', )], )),
770
(('ref', ), 'refdata', ([], ))])
771
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
772
(index, ('ref', ), 'refdata', ((), ))]),
773
set(index.iter_entries([('name', ), ('ref', )])))
775
def test_iter_nothing_empty(self):
776
index = self.make_index()
777
self.assertEqual([], list(index.iter_entries([])))
779
def test_iter_missing_entry_empty(self):
780
index = self.make_index()
781
self.assertEqual([], list(index.iter_entries([('a', )])))
783
def test_iter_missing_entry_empty_no_size(self):
784
index = self.make_index()
785
index = GraphIndex(index._transport, 'index', None)
786
self.assertEqual([], list(index.iter_entries([('a', )])))
788
def test_iter_key_prefix_1_element_key_None(self):
789
index = self.make_index()
790
self.assertRaises(errors.BadIndexKey, list,
791
index.iter_entries_prefix([(None, )]))
793
def test_iter_key_prefix_wrong_length(self):
794
index = self.make_index()
795
self.assertRaises(errors.BadIndexKey, list,
796
index.iter_entries_prefix([('foo', None)]))
797
index = self.make_index(key_elements=2)
798
self.assertRaises(errors.BadIndexKey, list,
799
index.iter_entries_prefix([('foo', )]))
800
self.assertRaises(errors.BadIndexKey, list,
801
index.iter_entries_prefix([('foo', None, None)]))
803
def test_iter_key_prefix_1_key_element_no_refs(self):
804
index = self.make_index( nodes=[
805
(('name', ), 'data', ()),
806
(('ref', ), 'refdata', ())])
807
self.assertEqual(set([(index, ('name', ), 'data'),
808
(index, ('ref', ), 'refdata')]),
809
set(index.iter_entries_prefix([('name', ), ('ref', )])))
811
def test_iter_key_prefix_1_key_element_refs(self):
812
index = self.make_index(1, nodes=[
813
(('name', ), 'data', ([('ref', )], )),
814
(('ref', ), 'refdata', ([], ))])
815
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
816
(index, ('ref', ), 'refdata', ((), ))]),
817
set(index.iter_entries_prefix([('name', ), ('ref', )])))
819
def test_iter_key_prefix_2_key_element_no_refs(self):
820
index = self.make_index(key_elements=2, nodes=[
821
(('name', 'fin1'), 'data', ()),
822
(('name', 'fin2'), 'beta', ()),
823
(('ref', 'erence'), 'refdata', ())])
824
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
825
(index, ('ref', 'erence'), 'refdata')]),
826
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
827
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
828
(index, ('name', 'fin2'), 'beta')]),
829
set(index.iter_entries_prefix([('name', None)])))
831
def test_iter_key_prefix_2_key_element_refs(self):
832
index = self.make_index(1, key_elements=2, nodes=[
833
(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
834
(('name', 'fin2'), 'beta', ([], )),
835
(('ref', 'erence'), 'refdata', ([], ))])
836
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
837
(index, ('ref', 'erence'), 'refdata', ((), ))]),
838
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
839
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
840
(index, ('name', 'fin2'), 'beta', ((), ))]),
841
set(index.iter_entries_prefix([('name', None)])))
843
def test_key_count_empty(self):
844
index = self.make_index()
845
self.assertEqual(0, index.key_count())
847
def test_key_count_one(self):
848
index = self.make_index(nodes=[(('name', ), '', ())])
849
self.assertEqual(1, index.key_count())
851
def test_key_count_two(self):
852
index = self.make_index(nodes=[
853
(('name', ), '', ()), (('foo', ), '', ())])
854
self.assertEqual(2, index.key_count())
856
def test_read_and_parse_tracks_real_read_value(self):
857
index = self.make_index(nodes=self.make_nodes(10))
858
del index._transport._activity[:]
859
index._read_and_parse([(0, 200)])
861
('readv', 'index', [(0, 200)], True, index._size),
863
index._transport._activity)
864
# The readv expansion code will expand the initial request to 4096
865
# bytes, which is more than enough to read the entire index, and we
866
# will track the fact that we read that many bytes.
867
self.assertEqual(index._size, index._bytes_read)
869
def test_read_and_parse_triggers_buffer_all(self):
870
index = self.make_index(key_elements=2, nodes=[
871
(('name', 'fin1'), 'data', ()),
872
(('name', 'fin2'), 'beta', ()),
873
(('ref', 'erence'), 'refdata', ())])
874
self.assertTrue(index._size > 0)
875
self.assertIs(None, index._nodes)
876
index._read_and_parse([(0, index._size)])
877
self.assertIsNot(None, index._nodes)
879
def test_validate_bad_index_errors(self):
880
trans = self.get_transport()
881
trans.put_bytes('name', "not an index\n")
882
index = GraphIndex(trans, 'name', 13)
883
self.assertRaises(errors.BadIndexFormatSignature, index.validate)
885
def test_validate_bad_node_refs(self):
886
index = self.make_index(2)
887
trans = self.get_transport()
888
content = trans.get_bytes('index')
889
# change the options line to end with a rather than a parseable number
890
new_content = content[:-2] + 'a\n\n'
891
trans.put_bytes('index', new_content)
892
self.assertRaises(errors.BadIndexOptions, index.validate)
894
def test_validate_missing_end_line_empty(self):
895
index = self.make_index(2)
896
trans = self.get_transport()
897
content = trans.get_bytes('index')
898
# truncate the last byte
899
trans.put_bytes('index', content[:-1])
900
self.assertRaises(errors.BadIndexData, index.validate)
902
def test_validate_missing_end_line_nonempty(self):
903
index = self.make_index(2, nodes=[(('key', ), '', ([], []))])
904
trans = self.get_transport()
905
content = trans.get_bytes('index')
906
# truncate the last byte
907
trans.put_bytes('index', content[:-1])
908
self.assertRaises(errors.BadIndexData, index.validate)
910
def test_validate_empty(self):
911
index = self.make_index()
914
def test_validate_no_refs_content(self):
915
index = self.make_index(nodes=[(('key', ), 'value', ())])
919
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
921
def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
922
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
923
for key, value, references in nodes:
924
builder.add_node(key, value, references)
925
stream = builder.finish()
926
trans = self.get_transport()
927
size = trans.put_file(name, stream)
928
return GraphIndex(trans, name, size)
930
def test_open_missing_index_no_error(self):
931
trans = self.get_transport()
932
index1 = GraphIndex(trans, 'missing', 100)
933
index = CombinedGraphIndex([index1])
935
def test_add_index(self):
936
index = CombinedGraphIndex([])
937
index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
938
index.insert_index(0, index1)
939
self.assertEqual([(index1, ('key', ), '')], list(index.iter_all_entries()))
941
def test_iter_all_entries_empty(self):
942
index = CombinedGraphIndex([])
943
self.assertEqual([], list(index.iter_all_entries()))
945
def test_iter_all_entries_children_empty(self):
946
index1 = self.make_index('name')
947
index = CombinedGraphIndex([index1])
948
self.assertEqual([], list(index.iter_all_entries()))
950
def test_iter_all_entries_simple(self):
951
index1 = self.make_index('name', nodes=[(('name', ), 'data', ())])
952
index = CombinedGraphIndex([index1])
953
self.assertEqual([(index1, ('name', ), 'data')],
954
list(index.iter_all_entries()))
956
def test_iter_all_entries_two_indices(self):
957
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
958
index2 = self.make_index('name2', nodes=[(('2', ), '', ())])
959
index = CombinedGraphIndex([index1, index2])
960
self.assertEqual([(index1, ('name', ), 'data'),
961
(index2, ('2', ), '')],
962
list(index.iter_all_entries()))
964
def test_iter_entries_two_indices_dup_key(self):
965
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
966
index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
967
index = CombinedGraphIndex([index1, index2])
968
self.assertEqual([(index1, ('name', ), 'data')],
969
list(index.iter_entries([('name', )])))
971
def test_iter_all_entries_two_indices_dup_key(self):
972
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
973
index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
974
index = CombinedGraphIndex([index1, index2])
975
self.assertEqual([(index1, ('name', ), 'data')],
976
list(index.iter_all_entries()))
978
def test_iter_key_prefix_2_key_element_refs(self):
979
index1 = self.make_index('1', 1, key_elements=2, nodes=[
980
(('name', 'fin1'), 'data', ([('ref', 'erence')], ))])
981
index2 = self.make_index('2', 1, key_elements=2, nodes=[
982
(('name', 'fin2'), 'beta', ([], )),
983
(('ref', 'erence'), 'refdata', ([], ))])
984
index = CombinedGraphIndex([index1, index2])
985
self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
986
(index2, ('ref', 'erence'), 'refdata', ((), ))]),
987
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
988
self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
989
(index2, ('name', 'fin2'), 'beta', ((), ))]),
990
set(index.iter_entries_prefix([('name', None)])))
992
def test_iter_nothing_empty(self):
993
index = CombinedGraphIndex([])
994
self.assertEqual([], list(index.iter_entries([])))
996
def test_iter_nothing_children_empty(self):
997
index1 = self.make_index('name')
998
index = CombinedGraphIndex([index1])
999
self.assertEqual([], list(index.iter_entries([])))
1001
def test_iter_all_keys(self):
1002
index1 = self.make_index('1', 1, nodes=[
1003
(('name', ), 'data', ([('ref', )], ))])
1004
index2 = self.make_index('2', 1, nodes=[
1005
(('ref', ), 'refdata', ((), ))])
1006
index = CombinedGraphIndex([index1, index2])
1007
self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),
1008
(index2, ('ref', ), 'refdata', ((), ))]),
1009
set(index.iter_entries([('name', ), ('ref', )])))
1011
def test_iter_all_keys_dup_entry(self):
1012
index1 = self.make_index('1', 1, nodes=[
1013
(('name', ), 'data', ([('ref', )], )),
1014
(('ref', ), 'refdata', ([], ))])
1015
index2 = self.make_index('2', 1, nodes=[
1016
(('ref', ), 'refdata', ([], ))])
1017
index = CombinedGraphIndex([index1, index2])
1018
self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),
1019
(index1, ('ref', ), 'refdata', ((), ))]),
1020
set(index.iter_entries([('name', ), ('ref', )])))
1022
def test_iter_missing_entry_empty(self):
1023
index = CombinedGraphIndex([])
1024
self.assertEqual([], list(index.iter_entries([('a', )])))
1026
def test_iter_missing_entry_one_index(self):
1027
index1 = self.make_index('1')
1028
index = CombinedGraphIndex([index1])
1029
self.assertEqual([], list(index.iter_entries([('a', )])))
1031
def test_iter_missing_entry_two_index(self):
1032
index1 = self.make_index('1')
1033
index2 = self.make_index('2')
1034
index = CombinedGraphIndex([index1, index2])
1035
self.assertEqual([], list(index.iter_entries([('a', )])))
1037
def test_iter_entry_present_one_index_only(self):
1038
index1 = self.make_index('1', nodes=[(('key', ), '', ())])
1039
index2 = self.make_index('2', nodes=[])
1040
index = CombinedGraphIndex([index1, index2])
1041
self.assertEqual([(index1, ('key', ), '')],
1042
list(index.iter_entries([('key', )])))
1043
# and in the other direction
1044
index = CombinedGraphIndex([index2, index1])
1045
self.assertEqual([(index1, ('key', ), '')],
1046
list(index.iter_entries([('key', )])))
1048
def test_key_count_empty(self):
1049
index1 = self.make_index('1', nodes=[])
1050
index2 = self.make_index('2', nodes=[])
1051
index = CombinedGraphIndex([index1, index2])
1052
self.assertEqual(0, index.key_count())
1054
def test_key_count_sums_index_keys(self):
1055
index1 = self.make_index('1', nodes=[
1058
index2 = self.make_index('2', nodes=[(('1',), '', ())])
1059
index = CombinedGraphIndex([index1, index2])
1060
self.assertEqual(3, index.key_count())
1062
def test_validate_bad_child_index_errors(self):
1063
trans = self.get_transport()
1064
trans.put_bytes('name', "not an index\n")
1065
index1 = GraphIndex(trans, 'name', 13)
1066
index = CombinedGraphIndex([index1])
1067
self.assertRaises(errors.BadIndexFormatSignature, index.validate)
1069
def test_validate_empty(self):
1070
index = CombinedGraphIndex([])
1074
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
1076
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
1077
result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1078
result.add_nodes(nodes)
1081
def test_add_nodes_no_refs(self):
1082
index = self.make_index(0)
1083
index.add_nodes([(('name', ), 'data')])
1084
index.add_nodes([(('name2', ), ''), (('name3', ), '')])
1085
self.assertEqual(set([
1086
(index, ('name', ), 'data'),
1087
(index, ('name2', ), ''),
1088
(index, ('name3', ), ''),
1089
]), set(index.iter_all_entries()))
1091
def test_add_nodes(self):
1092
index = self.make_index(1)
1093
index.add_nodes([(('name', ), 'data', ([],))])
1094
index.add_nodes([(('name2', ), '', ([],)), (('name3', ), '', ([('r', )],))])
1095
self.assertEqual(set([
1096
(index, ('name', ), 'data', ((),)),
1097
(index, ('name2', ), '', ((),)),
1098
(index, ('name3', ), '', ((('r', ), ), )),
1099
]), set(index.iter_all_entries()))
1101
def test_iter_all_entries_empty(self):
1102
index = self.make_index()
1103
self.assertEqual([], list(index.iter_all_entries()))
1105
def test_iter_all_entries_simple(self):
1106
index = self.make_index(nodes=[(('name', ), 'data')])
1107
self.assertEqual([(index, ('name', ), 'data')],
1108
list(index.iter_all_entries()))
1110
def test_iter_all_entries_references(self):
1111
index = self.make_index(1, nodes=[
1112
(('name', ), 'data', ([('ref', )], )),
1113
(('ref', ), 'refdata', ([], ))])
1114
self.assertEqual(set([(index, ('name', ), 'data', ((('ref', ),),)),
1115
(index, ('ref', ), 'refdata', ((), ))]),
1116
set(index.iter_all_entries()))
1118
def test_iteration_absent_skipped(self):
1119
index = self.make_index(1, nodes=[
1120
(('name', ), 'data', ([('ref', )], ))])
1121
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
1122
set(index.iter_all_entries()))
1123
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
1124
set(index.iter_entries([('name', )])))
1125
self.assertEqual([], list(index.iter_entries([('ref', )])))
1127
def test_iter_all_keys(self):
1128
index = self.make_index(1, nodes=[
1129
(('name', ), 'data', ([('ref', )], )),
1130
(('ref', ), 'refdata', ([], ))])
1131
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
1132
(index, ('ref', ), 'refdata', ((), ))]),
1133
set(index.iter_entries([('name', ), ('ref', )])))
1135
def test_iter_key_prefix_1_key_element_no_refs(self):
1136
index = self.make_index( nodes=[
1137
(('name', ), 'data'),
1138
(('ref', ), 'refdata')])
1139
self.assertEqual(set([(index, ('name', ), 'data'),
1140
(index, ('ref', ), 'refdata')]),
1141
set(index.iter_entries_prefix([('name', ), ('ref', )])))
1143
def test_iter_key_prefix_1_key_element_refs(self):
1144
index = self.make_index(1, nodes=[
1145
(('name', ), 'data', ([('ref', )], )),
1146
(('ref', ), 'refdata', ([], ))])
1147
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
1148
(index, ('ref', ), 'refdata', ((), ))]),
1149
set(index.iter_entries_prefix([('name', ), ('ref', )])))
1151
def test_iter_key_prefix_2_key_element_no_refs(self):
1152
index = self.make_index(key_elements=2, nodes=[
1153
(('name', 'fin1'), 'data'),
1154
(('name', 'fin2'), 'beta'),
1155
(('ref', 'erence'), 'refdata')])
1156
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
1157
(index, ('ref', 'erence'), 'refdata')]),
1158
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
1159
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
1160
(index, ('name', 'fin2'), 'beta')]),
1161
set(index.iter_entries_prefix([('name', None)])))
1163
def test_iter_key_prefix_2_key_element_refs(self):
1164
index = self.make_index(1, key_elements=2, nodes=[
1165
(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
1166
(('name', 'fin2'), 'beta', ([], )),
1167
(('ref', 'erence'), 'refdata', ([], ))])
1168
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1169
(index, ('ref', 'erence'), 'refdata', ((), ))]),
1170
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
1171
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1172
(index, ('name', 'fin2'), 'beta', ((), ))]),
1173
set(index.iter_entries_prefix([('name', None)])))
1175
def test_iter_nothing_empty(self):
1176
index = self.make_index()
1177
self.assertEqual([], list(index.iter_entries([])))
1179
def test_iter_missing_entry_empty(self):
1180
index = self.make_index()
1181
self.assertEqual([], list(index.iter_entries(['a'])))
1183
def test_key_count_empty(self):
1184
index = self.make_index()
1185
self.assertEqual(0, index.key_count())
1187
def test_key_count_one(self):
1188
index = self.make_index(nodes=[(('name', ), '')])
1189
self.assertEqual(1, index.key_count())
1191
def test_key_count_two(self):
1192
index = self.make_index(nodes=[(('name', ), ''), (('foo', ), '')])
1193
self.assertEqual(2, index.key_count())
1195
def test_validate_empty(self):
1196
index = self.make_index()
1199
def test_validate_no_refs_content(self):
1200
index = self.make_index(nodes=[(('key', ), 'value')])
1204
class TestGraphIndexPrefixAdapter(TestCaseWithMemoryTransport):
1206
def make_index(self, ref_lists=1, key_elements=2, nodes=[], add_callback=False):
1207
result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1208
result.add_nodes(nodes)
1210
add_nodes_callback = result.add_nodes
1212
add_nodes_callback = None
1213
adapter = GraphIndexPrefixAdapter(result, ('prefix', ), key_elements - 1,
1214
add_nodes_callback=add_nodes_callback)
1215
return result, adapter
1217
def test_add_node(self):
1218
index, adapter = self.make_index(add_callback=True)
1219
adapter.add_node(('key',), 'value', ((('ref',),),))
1220
self.assertEqual(set([(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))]),
1221
set(index.iter_all_entries()))
1223
def test_add_nodes(self):
1224
index, adapter = self.make_index(add_callback=True)
1226
(('key',), 'value', ((('ref',),),)),
1227
(('key2',), 'value2', ((),)),
1229
self.assertEqual(set([
1230
(index, ('prefix', 'key2'), 'value2', ((),)),
1231
(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))
1233
set(index.iter_all_entries()))
1235
def test_construct(self):
1236
index = InMemoryGraphIndex()
1237
adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1)
1239
def test_construct_with_callback(self):
1240
index = InMemoryGraphIndex()
1241
adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1, index.add_nodes)
1243
def test_iter_all_entries_cross_prefix_map_errors(self):
1244
index, adapter = self.make_index(nodes=[
1245
(('prefix', 'key1'), 'data1', ((('prefixaltered', 'key2'),),))])
1246
self.assertRaises(errors.BadIndexData, list, adapter.iter_all_entries())
1248
def test_iter_all_entries(self):
1249
index, adapter = self.make_index(nodes=[
1250
(('notprefix', 'key1'), 'data', ((), )),
1251
(('prefix', 'key1'), 'data1', ((), )),
1252
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1253
self.assertEqual(set([(index, ('key1', ), 'data1', ((),)),
1254
(index, ('key2', ), 'data2', ((('key1',),),))]),
1255
set(adapter.iter_all_entries()))
1257
def test_iter_entries(self):
1258
index, adapter = self.make_index(nodes=[
1259
(('notprefix', 'key1'), 'data', ((), )),
1260
(('prefix', 'key1'), 'data1', ((), )),
1261
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1262
# ask for many - get all
1263
self.assertEqual(set([(index, ('key1', ), 'data1', ((),)),
1264
(index, ('key2', ), 'data2', ((('key1', ),),))]),
1265
set(adapter.iter_entries([('key1', ), ('key2', )])))
1266
# ask for one, get one
1267
self.assertEqual(set([(index, ('key1', ), 'data1', ((),))]),
1268
set(adapter.iter_entries([('key1', )])))
1269
# ask for missing, get none
1270
self.assertEqual(set(),
1271
set(adapter.iter_entries([('key3', )])))
1273
def test_iter_entries_prefix(self):
1274
index, adapter = self.make_index(key_elements=3, nodes=[
1275
(('notprefix', 'foo', 'key1'), 'data', ((), )),
1276
(('prefix', 'prefix2', 'key1'), 'data1', ((), )),
1277
(('prefix', 'prefix2', 'key2'), 'data2', ((('prefix', 'prefix2', 'key1'),),))])
1278
# ask for a prefix, get the results for just that prefix, adjusted.
1279
self.assertEqual(set([(index, ('prefix2', 'key1', ), 'data1', ((),)),
1280
(index, ('prefix2', 'key2', ), 'data2', ((('prefix2', 'key1', ),),))]),
1281
set(adapter.iter_entries_prefix([('prefix2', None)])))
1283
def test_key_count_no_matching_keys(self):
1284
index, adapter = self.make_index(nodes=[
1285
(('notprefix', 'key1'), 'data', ((), ))])
1286
self.assertEqual(0, adapter.key_count())
1288
def test_key_count_some_keys(self):
1289
index, adapter = self.make_index(nodes=[
1290
(('notprefix', 'key1'), 'data', ((), )),
1291
(('prefix', 'key1'), 'data1', ((), )),
1292
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1293
self.assertEqual(2, adapter.key_count())
1295
def test_validate(self):
1296
index, adapter = self.make_index()
1299
calls.append('called')
1300
index.validate = validate
1302
self.assertEqual(['called'], calls)
added
removed
bzrlib/tests/test_index.py
