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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 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', ([],))
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)
361
class TestGraphIndex(TestCaseWithMemoryTransport):
363
def make_key(self, number):
364
return (str(number) + 'X'*100,)
366
def make_value(self, number):
367
return str(number) + 'Y'*100
369
def make_nodes(self, count=64):
370
# generate a big enough index that we only read some of it on a typical
373
for counter in range(count):
374
nodes.append((self.make_key(counter), self.make_value(counter), ()))
377
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
378
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
379
for key, value, references in nodes:
380
builder.add_node(key, value, references)
381
stream = builder.finish()
382
trans = get_transport('trace+' + self.get_url())
383
size = trans.put_file('index', stream)
384
return GraphIndex(trans, 'index', size)
386
def test_open_bad_index_no_error(self):
387
trans = self.get_transport()
388
trans.put_bytes('name', "not an index\n")
389
index = GraphIndex(trans, 'name', 13)
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)
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
403
('readv', 'index', [(0, 200)], True, index._size),
405
index._transport._activity)
406
# And that should have been enough to trigger reading the whole index
408
self.assertIsNot(None, index._nodes)
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.
421
('readv', 'index', [(30, 30), (0, 200)], True, 60),
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)],
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)
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*
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.
452
[(start_lookup, 800), (0, 200)], True, index._size),
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)],
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)
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)],
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)
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
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.
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))])
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))),
517
self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)
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
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
537
result = index._lookup_keys_via_location(
539
self.assertEqual([((4000, ('40', )), False)],
541
self.assertEqual([], index._transport._activity)
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
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
562
result = index._lookup_keys_via_location([(4000, self.make_key(40))])
564
[((4000, self.make_key(40)),
565
(index, self.make_key(40), self.make_value(40)))],
567
self.assertEqual([], index._transport._activity)
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
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)],
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
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)],
601
def test_lookup_key_resolves_references(self):
602
# generate a big enough index that we only read some of it on a typical
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
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.
623
[('readv', 'index', [(index_center, 800), (0, 200)], True,
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))])
632
[((11000, self.make_key(45)),
633
(index, self.make_key(45), self.make_value(45),
634
((self.make_key(65),),)))],
636
self.assertEqual([('readv', 'index', [(15093, 800)], True, index_size)],
637
index._transport._activity)
639
def test_lookup_key_can_buffer_all(self):
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
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.
658
[('readv', 'index', [(index_center, 800), (0, 200)], True,
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))])
667
[((7000, self.make_key(40)),
668
(index, self.make_key(40), self.make_value(40),
669
((self.make_key(60),),)))],
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)
675
def test_iter_all_entries_empty(self):
676
index = self.make_index()
677
self.assertEqual([], list(index.iter_all_entries()))
679
def test_iter_all_entries_simple(self):
680
index = self.make_index(nodes=[(('name', ), 'data', ())])
681
self.assertEqual([(index, ('name', ), 'data')],
682
list(index.iter_all_entries()))
684
def test_iter_all_entries_simple_2_elements(self):
685
index = self.make_index(key_elements=2,
686
nodes=[(('name', 'surname'), 'data', ())])
687
self.assertEqual([(index, ('name', 'surname'), 'data')],
688
list(index.iter_all_entries()))
690
def test_iter_all_entries_references_resolved(self):
691
index = self.make_index(1, nodes=[
692
(('name', ), 'data', ([('ref', )], )),
693
(('ref', ), 'refdata', ([], ))])
694
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
695
(index, ('ref', ), 'refdata', ((), ))]),
696
set(index.iter_all_entries()))
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
708
('readv', 'index', [(0, 200)], True, index._size),
710
index._transport._activity)
711
# And that should have been enough to trigger reading the whole index
713
self.assertIsNot(None, index._nodes)
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
737
list(index.iter_entries([self.make_key(60)]))
738
self.assertIsNot(None, index._nodes)
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',)])))
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',)])))
756
def test_iteration_absent_skipped(self):
757
index = self.make_index(1, nodes=[
758
(('name', ), 'data', ([('ref', )], ))])
759
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
760
set(index.iter_all_entries()))
761
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
762
set(index.iter_entries([('name', )])))
763
self.assertEqual([], list(index.iter_entries([('ref', )])))
765
def test_iteration_absent_skipped_2_element_keys(self):
766
index = self.make_index(1, key_elements=2, nodes=[
767
(('name', 'fin'), 'data', ([('ref', 'erence')], ))])
768
self.assertEqual(set([(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
769
set(index.iter_all_entries()))
770
self.assertEqual(set([(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
771
set(index.iter_entries([('name', 'fin')])))
772
self.assertEqual([], list(index.iter_entries([('ref', 'erence')])))
774
def test_iter_all_keys(self):
775
index = self.make_index(1, nodes=[
776
(('name', ), 'data', ([('ref', )], )),
777
(('ref', ), 'refdata', ([], ))])
778
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
779
(index, ('ref', ), 'refdata', ((), ))]),
780
set(index.iter_entries([('name', ), ('ref', )])))
782
def test_iter_nothing_empty(self):
783
index = self.make_index()
784
self.assertEqual([], list(index.iter_entries([])))
786
def test_iter_missing_entry_empty(self):
787
index = self.make_index()
788
self.assertEqual([], list(index.iter_entries([('a', )])))
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', )])))
795
def test_iter_key_prefix_1_element_key_None(self):
796
index = self.make_index()
797
self.assertRaises(errors.BadIndexKey, list,
798
index.iter_entries_prefix([(None, )]))
800
def test_iter_key_prefix_wrong_length(self):
801
index = self.make_index()
802
self.assertRaises(errors.BadIndexKey, list,
803
index.iter_entries_prefix([('foo', None)]))
804
index = self.make_index(key_elements=2)
805
self.assertRaises(errors.BadIndexKey, list,
806
index.iter_entries_prefix([('foo', )]))
807
self.assertRaises(errors.BadIndexKey, list,
808
index.iter_entries_prefix([('foo', None, None)]))
810
def test_iter_key_prefix_1_key_element_no_refs(self):
811
index = self.make_index( nodes=[
812
(('name', ), 'data', ()),
813
(('ref', ), 'refdata', ())])
814
self.assertEqual(set([(index, ('name', ), 'data'),
815
(index, ('ref', ), 'refdata')]),
816
set(index.iter_entries_prefix([('name', ), ('ref', )])))
818
def test_iter_key_prefix_1_key_element_refs(self):
819
index = self.make_index(1, nodes=[
820
(('name', ), 'data', ([('ref', )], )),
821
(('ref', ), 'refdata', ([], ))])
822
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
823
(index, ('ref', ), 'refdata', ((), ))]),
824
set(index.iter_entries_prefix([('name', ), ('ref', )])))
826
def test_iter_key_prefix_2_key_element_no_refs(self):
827
index = self.make_index(key_elements=2, nodes=[
828
(('name', 'fin1'), 'data', ()),
829
(('name', 'fin2'), 'beta', ()),
830
(('ref', 'erence'), 'refdata', ())])
831
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
832
(index, ('ref', 'erence'), 'refdata')]),
833
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
834
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
835
(index, ('name', 'fin2'), 'beta')]),
836
set(index.iter_entries_prefix([('name', None)])))
838
def test_iter_key_prefix_2_key_element_refs(self):
839
index = self.make_index(1, key_elements=2, nodes=[
840
(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
841
(('name', 'fin2'), 'beta', ([], )),
842
(('ref', 'erence'), 'refdata', ([], ))])
843
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
844
(index, ('ref', 'erence'), 'refdata', ((), ))]),
845
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
846
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
847
(index, ('name', 'fin2'), 'beta', ((), ))]),
848
set(index.iter_entries_prefix([('name', None)])))
850
def test_key_count_empty(self):
851
index = self.make_index()
852
self.assertEqual(0, index.key_count())
854
def test_key_count_one(self):
855
index = self.make_index(nodes=[(('name', ), '', ())])
856
self.assertEqual(1, index.key_count())
858
def test_key_count_two(self):
859
index = self.make_index(nodes=[
860
(('name', ), '', ()), (('foo', ), '', ())])
861
self.assertEqual(2, index.key_count())
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)])
868
('readv', 'index', [(0, 200)], True, index._size),
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)
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)
886
def test_validate_bad_index_errors(self):
887
trans = self.get_transport()
888
trans.put_bytes('name', "not an index\n")
889
index = GraphIndex(trans, 'name', 13)
890
self.assertRaises(errors.BadIndexFormatSignature, index.validate)
892
def test_validate_bad_node_refs(self):
893
index = self.make_index(2)
894
trans = self.get_transport()
895
content = trans.get_bytes('index')
896
# change the options line to end with a rather than a parseable number
897
new_content = content[:-2] + 'a\n\n'
898
trans.put_bytes('index', new_content)
899
self.assertRaises(errors.BadIndexOptions, index.validate)
901
def test_validate_missing_end_line_empty(self):
902
index = self.make_index(2)
903
trans = self.get_transport()
904
content = trans.get_bytes('index')
905
# truncate the last byte
906
trans.put_bytes('index', content[:-1])
907
self.assertRaises(errors.BadIndexData, index.validate)
909
def test_validate_missing_end_line_nonempty(self):
910
index = self.make_index(2, nodes=[(('key', ), '', ([], []))])
911
trans = self.get_transport()
912
content = trans.get_bytes('index')
913
# truncate the last byte
914
trans.put_bytes('index', content[:-1])
915
self.assertRaises(errors.BadIndexData, index.validate)
917
def test_validate_empty(self):
918
index = self.make_index()
921
def test_validate_no_refs_content(self):
922
index = self.make_index(nodes=[(('key', ), 'value', ())])
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)
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))
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))
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))
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', ([],)),
954
self.assertEqual(set([]), index.external_references(0))
957
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
959
def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
960
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
961
for key, value, references in nodes:
962
builder.add_node(key, value, references)
963
stream = builder.finish()
964
trans = self.get_transport()
965
size = trans.put_file(name, stream)
966
return GraphIndex(trans, name, size)
968
def make_combined_index_with_missing(self, missing=['1', '2']):
969
"""Create a CombinedGraphIndex which will have missing indexes.
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
975
:param missing: The underlying indexes to delete
976
:return: (CombinedGraphIndex, reload_counter)
978
index1 = self.make_index('1', nodes=[(('1',), '', ())])
979
index2 = self.make_index('2', nodes=[(('2',), '', ())])
980
index3 = self.make_index('3', nodes=[
984
# total_reloads, num_changed, num_unchanged
985
reload_counter = [0, 0, 0]
987
reload_counter[0] += 1
988
new_indices = [index3]
989
if index._indices == new_indices:
990
reload_counter[2] += 1
992
reload_counter[1] += 1
993
index._indices[:] = new_indices
995
index = CombinedGraphIndex([index1, index2], reload_func=reload)
996
trans = self.get_transport()
997
for fname in missing:
999
return index, reload_counter
1001
def test_open_missing_index_no_error(self):
1002
trans = self.get_transport()
1003
index1 = GraphIndex(trans, 'missing', 100)
1004
index = CombinedGraphIndex([index1])
1006
def test_add_index(self):
1007
index = CombinedGraphIndex([])
1008
index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1009
index.insert_index(0, index1)
1010
self.assertEqual([(index1, ('key', ), '')], list(index.iter_all_entries()))
1012
def test_iter_all_entries_empty(self):
1013
index = CombinedGraphIndex([])
1014
self.assertEqual([], list(index.iter_all_entries()))
1016
def test_iter_all_entries_children_empty(self):
1017
index1 = self.make_index('name')
1018
index = CombinedGraphIndex([index1])
1019
self.assertEqual([], list(index.iter_all_entries()))
1021
def test_iter_all_entries_simple(self):
1022
index1 = self.make_index('name', nodes=[(('name', ), 'data', ())])
1023
index = CombinedGraphIndex([index1])
1024
self.assertEqual([(index1, ('name', ), 'data')],
1025
list(index.iter_all_entries()))
1027
def test_iter_all_entries_two_indices(self):
1028
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1029
index2 = self.make_index('name2', nodes=[(('2', ), '', ())])
1030
index = CombinedGraphIndex([index1, index2])
1031
self.assertEqual([(index1, ('name', ), 'data'),
1032
(index2, ('2', ), '')],
1033
list(index.iter_all_entries()))
1035
def test_iter_entries_two_indices_dup_key(self):
1036
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1037
index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
1038
index = CombinedGraphIndex([index1, index2])
1039
self.assertEqual([(index1, ('name', ), 'data')],
1040
list(index.iter_entries([('name', )])))
1042
def test_iter_all_entries_two_indices_dup_key(self):
1043
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1044
index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
1045
index = CombinedGraphIndex([index1, index2])
1046
self.assertEqual([(index1, ('name', ), 'data')],
1047
list(index.iter_all_entries()))
1049
def test_iter_key_prefix_2_key_element_refs(self):
1050
index1 = self.make_index('1', 1, key_elements=2, nodes=[
1051
(('name', 'fin1'), 'data', ([('ref', 'erence')], ))])
1052
index2 = self.make_index('2', 1, key_elements=2, nodes=[
1053
(('name', 'fin2'), 'beta', ([], )),
1054
(('ref', 'erence'), 'refdata', ([], ))])
1055
index = CombinedGraphIndex([index1, index2])
1056
self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1057
(index2, ('ref', 'erence'), 'refdata', ((), ))]),
1058
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
1059
self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1060
(index2, ('name', 'fin2'), 'beta', ((), ))]),
1061
set(index.iter_entries_prefix([('name', None)])))
1063
def test_iter_nothing_empty(self):
1064
index = CombinedGraphIndex([])
1065
self.assertEqual([], list(index.iter_entries([])))
1067
def test_iter_nothing_children_empty(self):
1068
index1 = self.make_index('name')
1069
index = CombinedGraphIndex([index1])
1070
self.assertEqual([], list(index.iter_entries([])))
1072
def test_iter_all_keys(self):
1073
index1 = self.make_index('1', 1, nodes=[
1074
(('name', ), 'data', ([('ref', )], ))])
1075
index2 = self.make_index('2', 1, nodes=[
1076
(('ref', ), 'refdata', ((), ))])
1077
index = CombinedGraphIndex([index1, index2])
1078
self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),
1079
(index2, ('ref', ), 'refdata', ((), ))]),
1080
set(index.iter_entries([('name', ), ('ref', )])))
1082
def test_iter_all_keys_dup_entry(self):
1083
index1 = self.make_index('1', 1, nodes=[
1084
(('name', ), 'data', ([('ref', )], )),
1085
(('ref', ), 'refdata', ([], ))])
1086
index2 = self.make_index('2', 1, nodes=[
1087
(('ref', ), 'refdata', ([], ))])
1088
index = CombinedGraphIndex([index1, index2])
1089
self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),
1090
(index1, ('ref', ), 'refdata', ((), ))]),
1091
set(index.iter_entries([('name', ), ('ref', )])))
1093
def test_iter_missing_entry_empty(self):
1094
index = CombinedGraphIndex([])
1095
self.assertEqual([], list(index.iter_entries([('a', )])))
1097
def test_iter_missing_entry_one_index(self):
1098
index1 = self.make_index('1')
1099
index = CombinedGraphIndex([index1])
1100
self.assertEqual([], list(index.iter_entries([('a', )])))
1102
def test_iter_missing_entry_two_index(self):
1103
index1 = self.make_index('1')
1104
index2 = self.make_index('2')
1105
index = CombinedGraphIndex([index1, index2])
1106
self.assertEqual([], list(index.iter_entries([('a', )])))
1108
def test_iter_entry_present_one_index_only(self):
1109
index1 = self.make_index('1', nodes=[(('key', ), '', ())])
1110
index2 = self.make_index('2', nodes=[])
1111
index = CombinedGraphIndex([index1, index2])
1112
self.assertEqual([(index1, ('key', ), '')],
1113
list(index.iter_entries([('key', )])))
1114
# and in the other direction
1115
index = CombinedGraphIndex([index2, index1])
1116
self.assertEqual([(index1, ('key', ), '')],
1117
list(index.iter_entries([('key', )])))
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())
1125
def test_key_count_sums_index_keys(self):
1126
index1 = self.make_index('1', nodes=[
1129
index2 = self.make_index('2', nodes=[(('1',), '', ())])
1130
index = CombinedGraphIndex([index1, index2])
1131
self.assertEqual(3, index.key_count())
1133
def test_validate_bad_child_index_errors(self):
1134
trans = self.get_transport()
1135
trans.put_bytes('name', "not an index\n")
1136
index1 = GraphIndex(trans, 'name', 13)
1137
index = CombinedGraphIndex([index1])
1138
self.assertRaises(errors.BadIndexFormatSignature, index.validate)
1140
def test_validate_empty(self):
1141
index = CombinedGraphIndex([])
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)
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)
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(
1161
self.assertRaises(errors.NoSuchFile, index.key_count)
1162
self.assertEqual([2, 1, 1], reload_counter)
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',), '')],
1170
self.assertEqual([1, 1, 0], reload_counter)
1172
def test_iter_entries_reloads_midway(self):
1173
# The first index still looks present, so we get interrupted mid-way
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',), '')],
1183
self.assertEqual([1, 1, 0], reload_counter)
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',)])
1191
def test_iter_entries_reloads_and_fails(self):
1192
index, reload_counter = self.make_combined_index_with_missing(
1194
self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1195
self.assertEqual([2, 1, 1], reload_counter)
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',), '')],
1203
self.assertEqual([1, 1, 0], reload_counter)
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',), '')],
1214
self.assertEqual([1, 1, 0], reload_counter)
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)
1221
def test_iter_all_entries_reloads_and_fails(self):
1222
index, reload_counter = self.make_combined_index_with_missing(
1224
self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
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)
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)
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,
1249
def test_iter_entries_prefix_reloads_and_fails(self):
1250
index, reload_counter = self.make_combined_index_with_missing(
1252
self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1255
def test_validate_reloads(self):
1256
index, reload_counter = self.make_combined_index_with_missing()
1258
self.assertEqual([1, 1, 0], reload_counter)
1260
def test_validate_reloads_midway(self):
1261
index, reload_counter = self.make_combined_index_with_missing(['2'])
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)
1269
def test_validate_reloads_and_fails(self):
1270
index, reload_counter = self.make_combined_index_with_missing(
1272
self.assertRaises(errors.NoSuchFile, index.validate)
1275
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
1277
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
1278
result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1279
result.add_nodes(nodes)
1282
def test_add_nodes_no_refs(self):
1283
index = self.make_index(0)
1284
index.add_nodes([(('name', ), 'data')])
1285
index.add_nodes([(('name2', ), ''), (('name3', ), '')])
1286
self.assertEqual(set([
1287
(index, ('name', ), 'data'),
1288
(index, ('name2', ), ''),
1289
(index, ('name3', ), ''),
1290
]), set(index.iter_all_entries()))
1292
def test_add_nodes(self):
1293
index = self.make_index(1)
1294
index.add_nodes([(('name', ), 'data', ([],))])
1295
index.add_nodes([(('name2', ), '', ([],)), (('name3', ), '', ([('r', )],))])
1296
self.assertEqual(set([
1297
(index, ('name', ), 'data', ((),)),
1298
(index, ('name2', ), '', ((),)),
1299
(index, ('name3', ), '', ((('r', ), ), )),
1300
]), set(index.iter_all_entries()))
1302
def test_iter_all_entries_empty(self):
1303
index = self.make_index()
1304
self.assertEqual([], list(index.iter_all_entries()))
1306
def test_iter_all_entries_simple(self):
1307
index = self.make_index(nodes=[(('name', ), 'data')])
1308
self.assertEqual([(index, ('name', ), 'data')],
1309
list(index.iter_all_entries()))
1311
def test_iter_all_entries_references(self):
1312
index = self.make_index(1, nodes=[
1313
(('name', ), 'data', ([('ref', )], )),
1314
(('ref', ), 'refdata', ([], ))])
1315
self.assertEqual(set([(index, ('name', ), 'data', ((('ref', ),),)),
1316
(index, ('ref', ), 'refdata', ((), ))]),
1317
set(index.iter_all_entries()))
1319
def test_iteration_absent_skipped(self):
1320
index = self.make_index(1, nodes=[
1321
(('name', ), 'data', ([('ref', )], ))])
1322
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
1323
set(index.iter_all_entries()))
1324
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
1325
set(index.iter_entries([('name', )])))
1326
self.assertEqual([], list(index.iter_entries([('ref', )])))
1328
def test_iter_all_keys(self):
1329
index = self.make_index(1, nodes=[
1330
(('name', ), 'data', ([('ref', )], )),
1331
(('ref', ), 'refdata', ([], ))])
1332
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
1333
(index, ('ref', ), 'refdata', ((), ))]),
1334
set(index.iter_entries([('name', ), ('ref', )])))
1336
def test_iter_key_prefix_1_key_element_no_refs(self):
1337
index = self.make_index( nodes=[
1338
(('name', ), 'data'),
1339
(('ref', ), 'refdata')])
1340
self.assertEqual(set([(index, ('name', ), 'data'),
1341
(index, ('ref', ), 'refdata')]),
1342
set(index.iter_entries_prefix([('name', ), ('ref', )])))
1344
def test_iter_key_prefix_1_key_element_refs(self):
1345
index = self.make_index(1, nodes=[
1346
(('name', ), 'data', ([('ref', )], )),
1347
(('ref', ), 'refdata', ([], ))])
1348
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
1349
(index, ('ref', ), 'refdata', ((), ))]),
1350
set(index.iter_entries_prefix([('name', ), ('ref', )])))
1352
def test_iter_key_prefix_2_key_element_no_refs(self):
1353
index = self.make_index(key_elements=2, nodes=[
1354
(('name', 'fin1'), 'data'),
1355
(('name', 'fin2'), 'beta'),
1356
(('ref', 'erence'), 'refdata')])
1357
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
1358
(index, ('ref', 'erence'), 'refdata')]),
1359
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
1360
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
1361
(index, ('name', 'fin2'), 'beta')]),
1362
set(index.iter_entries_prefix([('name', None)])))
1364
def test_iter_key_prefix_2_key_element_refs(self):
1365
index = self.make_index(1, key_elements=2, nodes=[
1366
(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
1367
(('name', 'fin2'), 'beta', ([], )),
1368
(('ref', 'erence'), 'refdata', ([], ))])
1369
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1370
(index, ('ref', 'erence'), 'refdata', ((), ))]),
1371
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
1372
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1373
(index, ('name', 'fin2'), 'beta', ((), ))]),
1374
set(index.iter_entries_prefix([('name', None)])))
1376
def test_iter_nothing_empty(self):
1377
index = self.make_index()
1378
self.assertEqual([], list(index.iter_entries([])))
1380
def test_iter_missing_entry_empty(self):
1381
index = self.make_index()
1382
self.assertEqual([], list(index.iter_entries(['a'])))
1384
def test_key_count_empty(self):
1385
index = self.make_index()
1386
self.assertEqual(0, index.key_count())
1388
def test_key_count_one(self):
1389
index = self.make_index(nodes=[(('name', ), '')])
1390
self.assertEqual(1, index.key_count())
1392
def test_key_count_two(self):
1393
index = self.make_index(nodes=[(('name', ), ''), (('foo', ), '')])
1394
self.assertEqual(2, index.key_count())
1396
def test_validate_empty(self):
1397
index = self.make_index()
1400
def test_validate_no_refs_content(self):
1401
index = self.make_index(nodes=[(('key', ), 'value')])
1405
class TestGraphIndexPrefixAdapter(TestCaseWithMemoryTransport):
1407
def make_index(self, ref_lists=1, key_elements=2, nodes=[], add_callback=False):
1408
result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1409
result.add_nodes(nodes)
1411
add_nodes_callback = result.add_nodes
1413
add_nodes_callback = None
1414
adapter = GraphIndexPrefixAdapter(result, ('prefix', ), key_elements - 1,
1415
add_nodes_callback=add_nodes_callback)
1416
return result, adapter
1418
def test_add_node(self):
1419
index, adapter = self.make_index(add_callback=True)
1420
adapter.add_node(('key',), 'value', ((('ref',),),))
1421
self.assertEqual(set([(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))]),
1422
set(index.iter_all_entries()))
1424
def test_add_nodes(self):
1425
index, adapter = self.make_index(add_callback=True)
1427
(('key',), 'value', ((('ref',),),)),
1428
(('key2',), 'value2', ((),)),
1430
self.assertEqual(set([
1431
(index, ('prefix', 'key2'), 'value2', ((),)),
1432
(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))
1434
set(index.iter_all_entries()))
1436
def test_construct(self):
1437
index = InMemoryGraphIndex()
1438
adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1)
1440
def test_construct_with_callback(self):
1441
index = InMemoryGraphIndex()
1442
adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1, index.add_nodes)
1444
def test_iter_all_entries_cross_prefix_map_errors(self):
1445
index, adapter = self.make_index(nodes=[
1446
(('prefix', 'key1'), 'data1', ((('prefixaltered', 'key2'),),))])
1447
self.assertRaises(errors.BadIndexData, list, adapter.iter_all_entries())
1449
def test_iter_all_entries(self):
1450
index, adapter = self.make_index(nodes=[
1451
(('notprefix', 'key1'), 'data', ((), )),
1452
(('prefix', 'key1'), 'data1', ((), )),
1453
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1454
self.assertEqual(set([(index, ('key1', ), 'data1', ((),)),
1455
(index, ('key2', ), 'data2', ((('key1',),),))]),
1456
set(adapter.iter_all_entries()))
1458
def test_iter_entries(self):
1459
index, adapter = self.make_index(nodes=[
1460
(('notprefix', 'key1'), 'data', ((), )),
1461
(('prefix', 'key1'), 'data1', ((), )),
1462
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1463
# ask for many - get all
1464
self.assertEqual(set([(index, ('key1', ), 'data1', ((),)),
1465
(index, ('key2', ), 'data2', ((('key1', ),),))]),
1466
set(adapter.iter_entries([('key1', ), ('key2', )])))
1467
# ask for one, get one
1468
self.assertEqual(set([(index, ('key1', ), 'data1', ((),))]),
1469
set(adapter.iter_entries([('key1', )])))
1470
# ask for missing, get none
1471
self.assertEqual(set(),
1472
set(adapter.iter_entries([('key3', )])))
1474
def test_iter_entries_prefix(self):
1475
index, adapter = self.make_index(key_elements=3, nodes=[
1476
(('notprefix', 'foo', 'key1'), 'data', ((), )),
1477
(('prefix', 'prefix2', 'key1'), 'data1', ((), )),
1478
(('prefix', 'prefix2', 'key2'), 'data2', ((('prefix', 'prefix2', 'key1'),),))])
1479
# ask for a prefix, get the results for just that prefix, adjusted.
1480
self.assertEqual(set([(index, ('prefix2', 'key1', ), 'data1', ((),)),
1481
(index, ('prefix2', 'key2', ), 'data2', ((('prefix2', 'key1', ),),))]),
1482
set(adapter.iter_entries_prefix([('prefix2', None)])))
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())
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())
1496
def test_validate(self):
1497
index, adapter = self.make_index()
1500
calls.append('called')
1501
index.validate = validate
1503
self.assertEqual(['called'], calls)
added
removed
bzrlib/tests/test_index.py
