1
# Copyright (C) 2007-2010 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_clear_cache(self):
177
builder = GraphIndexBuilder(reference_lists=2)
178
# This is a no-op, but the api should exist
179
builder.clear_cache()
181
def test_node_references_are_byte_offsets(self):
182
builder = GraphIndexBuilder(reference_lists=1)
183
builder.add_node(('reference', ), 'data', ([], ))
184
builder.add_node(('key', ), 'data', ([('reference', )], ))
185
stream = builder.finish()
186
contents = stream.read()
188
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=2\n"
189
"key\x00\x0072\x00data\n"
190
"reference\x00\x00\x00data\n"
193
def test_node_references_are_cr_delimited(self):
194
builder = GraphIndexBuilder(reference_lists=1)
195
builder.add_node(('reference', ), 'data', ([], ))
196
builder.add_node(('reference2', ), 'data', ([], ))
197
builder.add_node(('key', ), 'data', ([('reference', ), ('reference2', )], ))
198
stream = builder.finish()
199
contents = stream.read()
201
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=3\n"
202
"key\x00\x00077\r094\x00data\n"
203
"reference\x00\x00\x00data\n"
204
"reference2\x00\x00\x00data\n"
207
def test_multiple_reference_lists_are_tab_delimited(self):
208
builder = GraphIndexBuilder(reference_lists=2)
209
builder.add_node(('keference', ), 'data', ([], []))
210
builder.add_node(('rey', ), 'data', ([('keference', )], [('keference', )]))
211
stream = builder.finish()
212
contents = stream.read()
214
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=2\n"
215
"keference\x00\x00\t\x00data\n"
216
"rey\x00\x0059\t59\x00data\n"
219
def test_add_node_referencing_missing_key_makes_absent(self):
220
builder = GraphIndexBuilder(reference_lists=1)
221
builder.add_node(('rey', ), 'data', ([('beference', ), ('aeference2', )], ))
222
stream = builder.finish()
223
contents = stream.read()
225
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
226
"aeference2\x00a\x00\x00\n"
227
"beference\x00a\x00\x00\n"
228
"rey\x00\x00074\r059\x00data\n"
231
def test_node_references_three_digits(self):
232
# test the node digit expands as needed.
233
builder = GraphIndexBuilder(reference_lists=1)
234
references = [(str(val), ) for val in reversed(range(9))]
235
builder.add_node(('2-key', ), '', (references, ))
236
stream = builder.finish()
237
contents = stream.read()
238
self.assertEqualDiff(
239
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
243
"2-key\x00\x00151\r145\r139\r133\r127\r121\r071\r065\r059\x00\n"
252
def test_absent_has_no_reference_overhead(self):
253
# the offsets after an absent record should be correct when there are
254
# >1 reference lists.
255
builder = GraphIndexBuilder(reference_lists=2)
256
builder.add_node(('parent', ), '', ([('aail', ), ('zther', )], []))
257
stream = builder.finish()
258
contents = stream.read()
260
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
261
"aail\x00a\x00\x00\n"
262
"parent\x00\x0059\r84\t\x00\n"
263
"zther\x00a\x00\x00\n"
266
def test_add_node_bad_key(self):
267
builder = GraphIndexBuilder()
268
for bad_char in '\t\n\x0b\x0c\r\x00 ':
269
self.assertRaises(errors.BadIndexKey, builder.add_node,
270
('a%skey' % bad_char, ), 'data')
271
self.assertRaises(errors.BadIndexKey, builder.add_node,
273
self.assertRaises(errors.BadIndexKey, builder.add_node,
274
'not-a-tuple', 'data')
276
self.assertRaises(errors.BadIndexKey, builder.add_node,
279
self.assertRaises(errors.BadIndexKey, builder.add_node,
280
('primary', 'secondary'), 'data')
281
# secondary key elements get checked too:
282
builder = GraphIndexBuilder(key_elements=2)
283
for bad_char in '\t\n\x0b\x0c\r\x00 ':
284
self.assertRaises(errors.BadIndexKey, builder.add_node,
285
('prefix', 'a%skey' % bad_char), 'data')
287
def test_add_node_bad_data(self):
288
builder = GraphIndexBuilder()
289
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
291
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
294
def test_add_node_bad_mismatched_ref_lists_length(self):
295
builder = GraphIndexBuilder()
296
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
298
builder = GraphIndexBuilder(reference_lists=1)
299
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
301
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
303
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
305
builder = GraphIndexBuilder(reference_lists=2)
306
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
308
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
310
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
311
'data aa', ([], [], []))
313
def test_add_node_bad_key_in_reference_lists(self):
314
# first list, first key - trivial
315
builder = GraphIndexBuilder(reference_lists=1)
316
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
317
'data aa', ([('a key', )], ))
318
# references keys must be tuples too
319
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
320
'data aa', (['not-a-tuple'], ))
322
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
325
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
326
'data aa', ([('primary', 'secondary')], ))
327
# need to check more than the first key in the list
328
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
329
'data aa', ([('agoodkey', ), ('that is a bad key', )], ))
330
# and if there is more than one list it should be getting checked
332
builder = GraphIndexBuilder(reference_lists=2)
333
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
334
'data aa', ([], ['a bad key']))
336
def test_add_duplicate_key(self):
337
builder = GraphIndexBuilder()
338
builder.add_node(('key', ), 'data')
339
self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node, ('key', ),
342
def test_add_duplicate_key_2_elements(self):
343
builder = GraphIndexBuilder(key_elements=2)
344
builder.add_node(('key', 'key'), 'data')
345
self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node,
346
('key', 'key'), 'data')
348
def test_add_key_after_referencing_key(self):
349
builder = GraphIndexBuilder(reference_lists=1)
350
builder.add_node(('key', ), 'data', ([('reference', )], ))
351
builder.add_node(('reference', ), 'data', ([],))
353
def test_add_key_after_referencing_key_2_elements(self):
354
builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
355
builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
356
builder.add_node(('reference', 'tokey'), 'data', ([],))
358
def test_set_optimize(self):
359
builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
360
builder.set_optimize(for_size=True)
361
self.assertTrue(builder._optimize_for_size)
362
builder.set_optimize(for_size=False)
363
self.assertFalse(builder._optimize_for_size)
366
class TestGraphIndex(TestCaseWithMemoryTransport):
368
def make_key(self, number):
369
return (str(number) + 'X'*100,)
371
def make_value(self, number):
372
return str(number) + 'Y'*100
374
def make_nodes(self, count=64):
375
# generate a big enough index that we only read some of it on a typical
378
for counter in range(count):
379
nodes.append((self.make_key(counter), self.make_value(counter), ()))
382
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
383
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
384
for key, value, references in nodes:
385
builder.add_node(key, value, references)
386
stream = builder.finish()
387
trans = get_transport('trace+' + self.get_url())
388
size = trans.put_file('index', stream)
389
return GraphIndex(trans, 'index', size)
391
def make_index_with_offset(self, ref_lists=0, key_elements=1, nodes=[],
393
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
394
for key, value, references in nodes:
395
builder.add_node(key, value, references)
396
content = builder.finish().read()
398
trans = self.get_transport()
399
trans.put_bytes('index', (' '*offset) + content)
400
return GraphIndex(trans, 'index', size, offset=offset)
402
def test_clear_cache(self):
403
index = self.make_index()
404
# For now, we just want to make sure the api is available. As this is
405
# old code, we don't really worry if it *does* anything.
408
def test_open_bad_index_no_error(self):
409
trans = self.get_transport()
410
trans.put_bytes('name', "not an index\n")
411
index = GraphIndex(trans, 'name', 13)
413
def test_with_offset(self):
414
nodes = self.make_nodes(200)
415
index = self.make_index_with_offset(offset=1234567, nodes=nodes)
416
self.assertEqual(200, index.key_count())
418
def test_buffer_all_with_offset(self):
419
nodes = self.make_nodes(200)
420
index = self.make_index_with_offset(offset=1234567, nodes=nodes)
422
self.assertEqual(200, index.key_count())
424
def test_side_effect_buffering_with_offset(self):
425
nodes = self.make_nodes(20)
426
index = self.make_index_with_offset(offset=1234567, nodes=nodes)
427
index._transport.recommended_page_size = lambda:64*1024
428
subset_nodes = [nodes[0][0], nodes[10][0], nodes[19][0]]
429
entries = [n[1] for n in index.iter_entries(subset_nodes)]
430
self.assertEqual(sorted(subset_nodes), sorted(entries))
431
self.assertEqual(20, index.key_count())
433
def test_open_sets_parsed_map_empty(self):
434
index = self.make_index()
435
self.assertEqual([], index._parsed_byte_map)
436
self.assertEqual([], index._parsed_key_map)
438
def test_key_count_buffers(self):
439
index = self.make_index(nodes=self.make_nodes(2))
440
# reset the transport log
441
del index._transport._activity[:]
442
self.assertEqual(2, index.key_count())
443
# We should have requested reading the header bytes
445
('readv', 'index', [(0, 200)], True, index._size),
447
index._transport._activity)
448
# And that should have been enough to trigger reading the whole index
450
self.assertIsNot(None, index._nodes)
452
def test_lookup_key_via_location_buffers(self):
453
index = self.make_index()
454
# reset the transport log
455
del index._transport._activity[:]
456
# do a _lookup_keys_via_location call for the middle of the file, which
457
# is what bisection uses.
458
result = index._lookup_keys_via_location(
459
[(index._size // 2, ('missing', ))])
460
# this should have asked for a readv request, with adjust_for_latency,
461
# and two regions: the header, and half-way into the file.
463
('readv', 'index', [(30, 30), (0, 200)], True, 60),
465
index._transport._activity)
466
# and the result should be that the key cannot be present, because this
467
# is a trivial index.
468
self.assertEqual([((index._size // 2, ('missing', )), False)],
470
# And this should have caused the file to be fully buffered
471
self.assertIsNot(None, index._nodes)
472
self.assertEqual([], index._parsed_byte_map)
474
def test_first_lookup_key_via_location(self):
475
# We need enough data so that the _HEADER_READV doesn't consume the
476
# whole file. We always read 800 bytes for every key, and the local
477
# transport natural expansion is 4096 bytes. So we have to have >8192
478
# bytes or we will trigger "buffer_all".
479
# We also want the 'missing' key to fall within the range that *did*
482
index = self.make_index(nodes=self.make_nodes(64))
483
# reset the transport log
484
del index._transport._activity[:]
485
# do a _lookup_keys_via_location call for the middle of the file, which
486
# is what bisection uses.
487
start_lookup = index._size // 2
488
result = index._lookup_keys_via_location(
489
[(start_lookup, ('40missing', ))])
490
# this should have asked for a readv request, with adjust_for_latency,
491
# and two regions: the header, and half-way into the file.
494
[(start_lookup, 800), (0, 200)], True, index._size),
496
index._transport._activity)
497
# and the result should be that the key cannot be present, because this
498
# is a trivial index.
499
self.assertEqual([((start_lookup, ('40missing', )), False)],
501
# And this should not have caused the file to be fully buffered
502
self.assertIs(None, index._nodes)
503
# And the regions of the file that have been parsed should be in the
504
# parsed_byte_map and the parsed_key_map
505
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
506
self.assertEqual([(None, self.make_key(26)),
507
(self.make_key(31), self.make_key(48))],
508
index._parsed_key_map)
510
def test_parsing_non_adjacent_data_trims(self):
511
index = self.make_index(nodes=self.make_nodes(64))
512
result = index._lookup_keys_via_location(
513
[(index._size // 2, ('40', ))])
514
# and the result should be that the key cannot be present, because key is
515
# in the middle of the observed data from a 4K read - the smallest transport
516
# will do today with this api.
517
self.assertEqual([((index._size // 2, ('40', )), False)],
519
# and we should have a parse map that includes the header and the
520
# region that was parsed after trimming.
521
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
522
self.assertEqual([(None, self.make_key(26)),
523
(self.make_key(31), self.make_key(48))],
524
index._parsed_key_map)
526
def test_parsing_data_handles_parsed_contained_regions(self):
527
# the following patten creates a parsed region that is wholly within a
528
# single result from the readv layer:
529
# .... single-read (readv-minimum-size) ...
530
# which then trims the start and end so the parsed size is < readv
532
# then a dual lookup (or a reference lookup for that matter) which
533
# abuts or overlaps the parsed region on both sides will need to
534
# discard the data in the middle, but parse the end as well.
536
# we test this by doing a single lookup to seed the data, then
537
# a lookup for two keys that are present, and adjacent -
538
# we except both to be found, and the parsed byte map to include the
539
# locations of both keys.
540
index = self.make_index(nodes=self.make_nodes(128))
541
result = index._lookup_keys_via_location(
542
[(index._size // 2, ('40', ))])
543
# and we should have a parse map that includes the header and the
544
# region that was parsed after trimming.
545
self.assertEqual([(0, 4045), (11759, 15707)], index._parsed_byte_map)
546
self.assertEqual([(None, self.make_key(116)),
547
(self.make_key(35), self.make_key(51))],
548
index._parsed_key_map)
549
# now ask for two keys, right before and after the parsed region
550
result = index._lookup_keys_via_location(
551
[(11450, self.make_key(34)), (15707, self.make_key(52))])
553
((11450, self.make_key(34)),
554
(index, self.make_key(34), self.make_value(34))),
555
((15707, self.make_key(52)),
556
(index, self.make_key(52), self.make_value(52))),
559
self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)
561
def test_lookup_missing_key_answers_without_io_when_map_permits(self):
562
# generate a big enough index that we only read some of it on a typical
564
index = self.make_index(nodes=self.make_nodes(64))
565
# lookup the keys in the middle of the file
566
result =index._lookup_keys_via_location(
567
[(index._size // 2, ('40', ))])
568
# check the parse map, this determines the test validity
569
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
570
self.assertEqual([(None, self.make_key(26)),
571
(self.make_key(31), self.make_key(48))],
572
index._parsed_key_map)
573
# reset the transport log
574
del index._transport._activity[:]
575
# now looking up a key in the portion of the file already parsed should
576
# not create a new transport request, and should return False (cannot
577
# be in the index) - even when the byte location we ask for is outside
579
result = index._lookup_keys_via_location(
581
self.assertEqual([((4000, ('40', )), False)],
583
self.assertEqual([], index._transport._activity)
585
def test_lookup_present_key_answers_without_io_when_map_permits(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
# lookup the keys in the middle of the file
590
result =index._lookup_keys_via_location(
591
[(index._size // 2, ('40', ))])
592
# check the parse map, this determines the test validity
593
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
594
self.assertEqual([(None, self.make_key(26)),
595
(self.make_key(31), self.make_key(48))],
596
index._parsed_key_map)
597
# reset the transport log
598
del index._transport._activity[:]
599
# now looking up a key in the portion of the file already parsed should
600
# not create a new transport request, and should return False (cannot
601
# be in the index) - even when the byte location we ask for is outside
604
result = index._lookup_keys_via_location([(4000, self.make_key(40))])
606
[((4000, self.make_key(40)),
607
(index, self.make_key(40), self.make_value(40)))],
609
self.assertEqual([], index._transport._activity)
611
def test_lookup_key_below_probed_area(self):
612
# generate a big enough index that we only read some of it on a typical
614
index = self.make_index(nodes=self.make_nodes(64))
615
# ask for the key in the middle, but a key that is located in the
616
# unparsed region before the middle.
617
result =index._lookup_keys_via_location(
618
[(index._size // 2, ('30', ))])
619
# check the parse map, this determines the test validity
620
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
621
self.assertEqual([(None, self.make_key(26)),
622
(self.make_key(31), self.make_key(48))],
623
index._parsed_key_map)
624
self.assertEqual([((index._size // 2, ('30', )), -1)],
627
def test_lookup_key_above_probed_area(self):
628
# generate a big enough index that we only read some of it on a typical
630
index = self.make_index(nodes=self.make_nodes(64))
631
# ask for the key in the middle, but a key that is located in the
632
# unparsed region after the middle.
633
result =index._lookup_keys_via_location(
634
[(index._size // 2, ('50', ))])
635
# check the parse map, this determines the test validity
636
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
637
self.assertEqual([(None, self.make_key(26)),
638
(self.make_key(31), self.make_key(48))],
639
index._parsed_key_map)
640
self.assertEqual([((index._size // 2, ('50', )), +1)],
643
def test_lookup_key_resolves_references(self):
644
# generate a big enough index that we only read some of it on a typical
647
for counter in range(99):
648
nodes.append((self.make_key(counter), self.make_value(counter),
649
((self.make_key(counter + 20),),) ))
650
index = self.make_index(ref_lists=1, nodes=nodes)
651
# lookup a key in the middle that does not exist, so that when we can
652
# check that the referred-to-keys are not accessed automatically.
653
index_size = index._size
654
index_center = index_size // 2
655
result = index._lookup_keys_via_location(
656
[(index_center, ('40', ))])
657
# check the parse map - only the start and middle should have been
659
self.assertEqual([(0, 4027), (10198, 14028)], index._parsed_byte_map)
660
self.assertEqual([(None, self.make_key(17)),
661
(self.make_key(44), self.make_key(5))],
662
index._parsed_key_map)
663
# and check the transport activity likewise.
665
[('readv', 'index', [(index_center, 800), (0, 200)], True,
667
index._transport._activity)
668
# reset the transport log for testing the reference lookup
669
del index._transport._activity[:]
670
# now looking up a key in the portion of the file already parsed should
671
# only perform IO to resolve its key references.
672
result = index._lookup_keys_via_location([(11000, self.make_key(45))])
674
[((11000, self.make_key(45)),
675
(index, self.make_key(45), self.make_value(45),
676
((self.make_key(65),),)))],
678
self.assertEqual([('readv', 'index', [(15093, 800)], True, index_size)],
679
index._transport._activity)
681
def test_lookup_key_can_buffer_all(self):
683
for counter in range(64):
684
nodes.append((self.make_key(counter), self.make_value(counter),
685
((self.make_key(counter + 20),),) ))
686
index = self.make_index(ref_lists=1, nodes=nodes)
687
# lookup a key in the middle that does not exist, so that when we can
688
# check that the referred-to-keys are not accessed automatically.
689
index_size = index._size
690
index_center = index_size // 2
691
result = index._lookup_keys_via_location([(index_center, ('40', ))])
692
# check the parse map - only the start and middle should have been
694
self.assertEqual([(0, 3890), (6444, 10274)], index._parsed_byte_map)
695
self.assertEqual([(None, self.make_key(25)),
696
(self.make_key(37), self.make_key(52))],
697
index._parsed_key_map)
698
# and check the transport activity likewise.
700
[('readv', 'index', [(index_center, 800), (0, 200)], True,
702
index._transport._activity)
703
# reset the transport log for testing the reference lookup
704
del index._transport._activity[:]
705
# now looking up a key in the portion of the file already parsed should
706
# only perform IO to resolve its key references.
707
result = index._lookup_keys_via_location([(7000, self.make_key(40))])
709
[((7000, self.make_key(40)),
710
(index, self.make_key(40), self.make_value(40),
711
((self.make_key(60),),)))],
713
# Resolving the references would have required more data read, and we
714
# are already above the 50% threshold, so it triggered a _buffer_all
715
self.assertEqual([('get', 'index')], index._transport._activity)
717
def test_iter_all_entries_empty(self):
718
index = self.make_index()
719
self.assertEqual([], list(index.iter_all_entries()))
721
def test_iter_all_entries_simple(self):
722
index = self.make_index(nodes=[(('name', ), 'data', ())])
723
self.assertEqual([(index, ('name', ), 'data')],
724
list(index.iter_all_entries()))
726
def test_iter_all_entries_simple_2_elements(self):
727
index = self.make_index(key_elements=2,
728
nodes=[(('name', 'surname'), 'data', ())])
729
self.assertEqual([(index, ('name', 'surname'), 'data')],
730
list(index.iter_all_entries()))
732
def test_iter_all_entries_references_resolved(self):
733
index = self.make_index(1, nodes=[
734
(('name', ), 'data', ([('ref', )], )),
735
(('ref', ), 'refdata', ([], ))])
736
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
737
(index, ('ref', ), 'refdata', ((), ))]),
738
set(index.iter_all_entries()))
740
def test_iter_entries_buffers_once(self):
741
index = self.make_index(nodes=self.make_nodes(2))
742
# reset the transport log
743
del index._transport._activity[:]
744
self.assertEqual(set([(index, self.make_key(1), self.make_value(1))]),
745
set(index.iter_entries([self.make_key(1)])))
746
# We should have requested reading the header bytes
747
# But not needed any more than that because it would have triggered a
750
('readv', 'index', [(0, 200)], True, index._size),
752
index._transport._activity)
753
# And that should have been enough to trigger reading the whole index
755
self.assertIsNot(None, index._nodes)
757
def test_iter_entries_buffers_by_bytes_read(self):
758
index = self.make_index(nodes=self.make_nodes(64))
759
list(index.iter_entries([self.make_key(10)]))
760
# The first time through isn't enough to trigger a buffer all
761
self.assertIs(None, index._nodes)
762
self.assertEqual(4096, index._bytes_read)
763
# Grabbing a key in that same page won't trigger a buffer all, as we
764
# still haven't read 50% of the file
765
list(index.iter_entries([self.make_key(11)]))
766
self.assertIs(None, index._nodes)
767
self.assertEqual(4096, index._bytes_read)
768
# We haven't read more data, so reading outside the range won't trigger
769
# a buffer all right away
770
list(index.iter_entries([self.make_key(40)]))
771
self.assertIs(None, index._nodes)
772
self.assertEqual(8192, index._bytes_read)
773
# On the next pass, we will not trigger buffer all if the key is
774
# available without reading more
775
list(index.iter_entries([self.make_key(32)]))
776
self.assertIs(None, index._nodes)
777
# But if we *would* need to read more to resolve it, then we will
779
list(index.iter_entries([self.make_key(60)]))
780
self.assertIsNot(None, index._nodes)
782
def test_iter_entries_references_resolved(self):
783
index = self.make_index(1, nodes=[
784
(('name', ), 'data', ([('ref', ), ('ref', )], )),
785
(('ref', ), 'refdata', ([], ))])
786
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),('ref',)),)),
787
(index, ('ref', ), 'refdata', ((), ))]),
788
set(index.iter_entries([('name',), ('ref',)])))
790
def test_iter_entries_references_2_refs_resolved(self):
791
index = self.make_index(2, nodes=[
792
(('name', ), 'data', ([('ref', )], [('ref', )])),
793
(('ref', ), 'refdata', ([], []))])
794
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),), (('ref',),))),
795
(index, ('ref', ), 'refdata', ((), ()))]),
796
set(index.iter_entries([('name',), ('ref',)])))
798
def test_iteration_absent_skipped(self):
799
index = self.make_index(1, nodes=[
800
(('name', ), 'data', ([('ref', )], ))])
801
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
802
set(index.iter_all_entries()))
803
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
804
set(index.iter_entries([('name', )])))
805
self.assertEqual([], list(index.iter_entries([('ref', )])))
807
def test_iteration_absent_skipped_2_element_keys(self):
808
index = self.make_index(1, key_elements=2, nodes=[
809
(('name', 'fin'), 'data', ([('ref', 'erence')], ))])
810
self.assertEqual(set([(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
811
set(index.iter_all_entries()))
812
self.assertEqual(set([(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
813
set(index.iter_entries([('name', 'fin')])))
814
self.assertEqual([], list(index.iter_entries([('ref', 'erence')])))
816
def test_iter_all_keys(self):
817
index = self.make_index(1, nodes=[
818
(('name', ), 'data', ([('ref', )], )),
819
(('ref', ), 'refdata', ([], ))])
820
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
821
(index, ('ref', ), 'refdata', ((), ))]),
822
set(index.iter_entries([('name', ), ('ref', )])))
824
def test_iter_nothing_empty(self):
825
index = self.make_index()
826
self.assertEqual([], list(index.iter_entries([])))
828
def test_iter_missing_entry_empty(self):
829
index = self.make_index()
830
self.assertEqual([], list(index.iter_entries([('a', )])))
832
def test_iter_missing_entry_empty_no_size(self):
833
index = self.make_index()
834
index = GraphIndex(index._transport, 'index', None)
835
self.assertEqual([], list(index.iter_entries([('a', )])))
837
def test_iter_key_prefix_1_element_key_None(self):
838
index = self.make_index()
839
self.assertRaises(errors.BadIndexKey, list,
840
index.iter_entries_prefix([(None, )]))
842
def test_iter_key_prefix_wrong_length(self):
843
index = self.make_index()
844
self.assertRaises(errors.BadIndexKey, list,
845
index.iter_entries_prefix([('foo', None)]))
846
index = self.make_index(key_elements=2)
847
self.assertRaises(errors.BadIndexKey, list,
848
index.iter_entries_prefix([('foo', )]))
849
self.assertRaises(errors.BadIndexKey, list,
850
index.iter_entries_prefix([('foo', None, None)]))
852
def test_iter_key_prefix_1_key_element_no_refs(self):
853
index = self.make_index( nodes=[
854
(('name', ), 'data', ()),
855
(('ref', ), 'refdata', ())])
856
self.assertEqual(set([(index, ('name', ), 'data'),
857
(index, ('ref', ), 'refdata')]),
858
set(index.iter_entries_prefix([('name', ), ('ref', )])))
860
def test_iter_key_prefix_1_key_element_refs(self):
861
index = self.make_index(1, nodes=[
862
(('name', ), 'data', ([('ref', )], )),
863
(('ref', ), 'refdata', ([], ))])
864
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
865
(index, ('ref', ), 'refdata', ((), ))]),
866
set(index.iter_entries_prefix([('name', ), ('ref', )])))
868
def test_iter_key_prefix_2_key_element_no_refs(self):
869
index = self.make_index(key_elements=2, nodes=[
870
(('name', 'fin1'), 'data', ()),
871
(('name', 'fin2'), 'beta', ()),
872
(('ref', 'erence'), 'refdata', ())])
873
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
874
(index, ('ref', 'erence'), 'refdata')]),
875
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
876
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
877
(index, ('name', 'fin2'), 'beta')]),
878
set(index.iter_entries_prefix([('name', None)])))
880
def test_iter_key_prefix_2_key_element_refs(self):
881
index = self.make_index(1, key_elements=2, nodes=[
882
(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
883
(('name', 'fin2'), 'beta', ([], )),
884
(('ref', 'erence'), 'refdata', ([], ))])
885
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
886
(index, ('ref', 'erence'), 'refdata', ((), ))]),
887
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
888
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
889
(index, ('name', 'fin2'), 'beta', ((), ))]),
890
set(index.iter_entries_prefix([('name', None)])))
892
def test_key_count_empty(self):
893
index = self.make_index()
894
self.assertEqual(0, index.key_count())
896
def test_key_count_one(self):
897
index = self.make_index(nodes=[(('name', ), '', ())])
898
self.assertEqual(1, index.key_count())
900
def test_key_count_two(self):
901
index = self.make_index(nodes=[
902
(('name', ), '', ()), (('foo', ), '', ())])
903
self.assertEqual(2, index.key_count())
905
def test_read_and_parse_tracks_real_read_value(self):
906
index = self.make_index(nodes=self.make_nodes(10))
907
del index._transport._activity[:]
908
index._read_and_parse([(0, 200)])
910
('readv', 'index', [(0, 200)], True, index._size),
912
index._transport._activity)
913
# The readv expansion code will expand the initial request to 4096
914
# bytes, which is more than enough to read the entire index, and we
915
# will track the fact that we read that many bytes.
916
self.assertEqual(index._size, index._bytes_read)
918
def test_read_and_parse_triggers_buffer_all(self):
919
index = self.make_index(key_elements=2, nodes=[
920
(('name', 'fin1'), 'data', ()),
921
(('name', 'fin2'), 'beta', ()),
922
(('ref', 'erence'), 'refdata', ())])
923
self.assertTrue(index._size > 0)
924
self.assertIs(None, index._nodes)
925
index._read_and_parse([(0, index._size)])
926
self.assertIsNot(None, index._nodes)
928
def test_validate_bad_index_errors(self):
929
trans = self.get_transport()
930
trans.put_bytes('name', "not an index\n")
931
index = GraphIndex(trans, 'name', 13)
932
self.assertRaises(errors.BadIndexFormatSignature, index.validate)
934
def test_validate_bad_node_refs(self):
935
index = self.make_index(2)
936
trans = self.get_transport()
937
content = trans.get_bytes('index')
938
# change the options line to end with a rather than a parseable number
939
new_content = content[:-2] + 'a\n\n'
940
trans.put_bytes('index', new_content)
941
self.assertRaises(errors.BadIndexOptions, index.validate)
943
def test_validate_missing_end_line_empty(self):
944
index = self.make_index(2)
945
trans = self.get_transport()
946
content = trans.get_bytes('index')
947
# truncate the last byte
948
trans.put_bytes('index', content[:-1])
949
self.assertRaises(errors.BadIndexData, index.validate)
951
def test_validate_missing_end_line_nonempty(self):
952
index = self.make_index(2, nodes=[(('key', ), '', ([], []))])
953
trans = self.get_transport()
954
content = trans.get_bytes('index')
955
# truncate the last byte
956
trans.put_bytes('index', content[:-1])
957
self.assertRaises(errors.BadIndexData, index.validate)
959
def test_validate_empty(self):
960
index = self.make_index()
963
def test_validate_no_refs_content(self):
964
index = self.make_index(nodes=[(('key', ), 'value', ())])
967
# XXX: external_references tests are duplicated in test_btree_index. We
968
# probably should have per_graph_index tests...
969
def test_external_references_no_refs(self):
970
index = self.make_index(ref_lists=0, nodes=[])
971
self.assertRaises(ValueError, index.external_references, 0)
973
def test_external_references_no_results(self):
974
index = self.make_index(ref_lists=1, nodes=[
975
(('key',), 'value', ([],))])
976
self.assertEqual(set(), index.external_references(0))
978
def test_external_references_missing_ref(self):
979
missing_key = ('missing',)
980
index = self.make_index(ref_lists=1, nodes=[
981
(('key',), 'value', ([missing_key],))])
982
self.assertEqual(set([missing_key]), index.external_references(0))
984
def test_external_references_multiple_ref_lists(self):
985
missing_key = ('missing',)
986
index = self.make_index(ref_lists=2, nodes=[
987
(('key',), 'value', ([], [missing_key]))])
988
self.assertEqual(set([]), index.external_references(0))
989
self.assertEqual(set([missing_key]), index.external_references(1))
991
def test_external_references_two_records(self):
992
index = self.make_index(ref_lists=1, nodes=[
993
(('key-1',), 'value', ([('key-2',)],)),
994
(('key-2',), 'value', ([],)),
996
self.assertEqual(set([]), index.external_references(0))
998
def test__find_ancestors(self):
1001
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1002
(key1, 'value', ([key2],)),
1003
(key2, 'value', ([],)),
1006
missing_keys = set()
1007
search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
1008
self.assertEqual({key1: (key2,)}, parent_map)
1009
self.assertEqual(set(), missing_keys)
1010
self.assertEqual(set([key2]), search_keys)
1011
search_keys = index._find_ancestors(search_keys, 0, parent_map,
1013
self.assertEqual({key1: (key2,), key2: ()}, parent_map)
1014
self.assertEqual(set(), missing_keys)
1015
self.assertEqual(set(), search_keys)
1017
def test__find_ancestors_w_missing(self):
1021
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1022
(key1, 'value', ([key2],)),
1023
(key2, 'value', ([],)),
1026
missing_keys = set()
1027
search_keys = index._find_ancestors([key2, key3], 0, parent_map,
1029
self.assertEqual({key2: ()}, parent_map)
1030
self.assertEqual(set([key3]), missing_keys)
1031
self.assertEqual(set(), search_keys)
1033
def test__find_ancestors_dont_search_known(self):
1037
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1038
(key1, 'value', ([key2],)),
1039
(key2, 'value', ([key3],)),
1040
(key3, 'value', ([],)),
1042
# We already know about key2, so we won't try to search for key3
1043
parent_map = {key2: (key3,)}
1044
missing_keys = set()
1045
search_keys = index._find_ancestors([key1], 0, parent_map,
1047
self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1048
self.assertEqual(set(), missing_keys)
1049
self.assertEqual(set(), search_keys)
1051
def test_supports_unlimited_cache(self):
1052
builder = GraphIndexBuilder(0, key_elements=1)
1053
stream = builder.finish()
1054
trans = get_transport(self.get_url())
1055
size = trans.put_file('index', stream)
1056
# It doesn't matter what unlimited_cache does here, just that it can be
1058
index = GraphIndex(trans, 'index', size, unlimited_cache=True)
1061
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
1063
def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
1064
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
1065
for key, value, references in nodes:
1066
builder.add_node(key, value, references)
1067
stream = builder.finish()
1068
trans = self.get_transport()
1069
size = trans.put_file(name, stream)
1070
return GraphIndex(trans, name, size)
1072
def make_combined_index_with_missing(self, missing=['1', '2']):
1073
"""Create a CombinedGraphIndex which will have missing indexes.
1075
This creates a CGI which thinks it has 2 indexes, however they have
1076
been deleted. If CGI._reload_func() is called, then it will repopulate
1079
:param missing: The underlying indexes to delete
1080
:return: (CombinedGraphIndex, reload_counter)
1082
index1 = self.make_index('1', nodes=[(('1',), '', ())])
1083
index2 = self.make_index('2', nodes=[(('2',), '', ())])
1084
index3 = self.make_index('3', nodes=[
1088
# total_reloads, num_changed, num_unchanged
1089
reload_counter = [0, 0, 0]
1091
reload_counter[0] += 1
1092
new_indices = [index3]
1093
if index._indices == new_indices:
1094
reload_counter[2] += 1
1096
reload_counter[1] += 1
1097
index._indices[:] = new_indices
1099
index = CombinedGraphIndex([index1, index2], reload_func=reload)
1100
trans = self.get_transport()
1101
for fname in missing:
1103
return index, reload_counter
1105
def test_open_missing_index_no_error(self):
1106
trans = self.get_transport()
1107
index1 = GraphIndex(trans, 'missing', 100)
1108
index = CombinedGraphIndex([index1])
1110
def test_add_index(self):
1111
index = CombinedGraphIndex([])
1112
index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1113
index.insert_index(0, index1)
1114
self.assertEqual([(index1, ('key', ), '')], list(index.iter_all_entries()))
1116
def test_clear_cache(self):
1119
class ClearCacheProxy(object):
1121
def __init__(self, index):
1124
def __getattr__(self, name):
1125
return getattr(self._index)
1127
def clear_cache(self):
1128
log.append(self._index)
1129
return self._index.clear_cache()
1131
index = CombinedGraphIndex([])
1132
index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1133
index.insert_index(0, ClearCacheProxy(index1))
1134
index2 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1135
index.insert_index(1, ClearCacheProxy(index2))
1136
# CombinedGraphIndex should call 'clear_cache()' on all children
1138
self.assertEqual(sorted([index1, index2]), sorted(log))
1140
def test_iter_all_entries_empty(self):
1141
index = CombinedGraphIndex([])
1142
self.assertEqual([], list(index.iter_all_entries()))
1144
def test_iter_all_entries_children_empty(self):
1145
index1 = self.make_index('name')
1146
index = CombinedGraphIndex([index1])
1147
self.assertEqual([], list(index.iter_all_entries()))
1149
def test_iter_all_entries_simple(self):
1150
index1 = self.make_index('name', nodes=[(('name', ), 'data', ())])
1151
index = CombinedGraphIndex([index1])
1152
self.assertEqual([(index1, ('name', ), 'data')],
1153
list(index.iter_all_entries()))
1155
def test_iter_all_entries_two_indices(self):
1156
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1157
index2 = self.make_index('name2', nodes=[(('2', ), '', ())])
1158
index = CombinedGraphIndex([index1, index2])
1159
self.assertEqual([(index1, ('name', ), 'data'),
1160
(index2, ('2', ), '')],
1161
list(index.iter_all_entries()))
1163
def test_iter_entries_two_indices_dup_key(self):
1164
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1165
index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
1166
index = CombinedGraphIndex([index1, index2])
1167
self.assertEqual([(index1, ('name', ), 'data')],
1168
list(index.iter_entries([('name', )])))
1170
def test_iter_all_entries_two_indices_dup_key(self):
1171
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1172
index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
1173
index = CombinedGraphIndex([index1, index2])
1174
self.assertEqual([(index1, ('name', ), 'data')],
1175
list(index.iter_all_entries()))
1177
def test_iter_key_prefix_2_key_element_refs(self):
1178
index1 = self.make_index('1', 1, key_elements=2, nodes=[
1179
(('name', 'fin1'), 'data', ([('ref', 'erence')], ))])
1180
index2 = self.make_index('2', 1, key_elements=2, nodes=[
1181
(('name', 'fin2'), 'beta', ([], )),
1182
(('ref', 'erence'), 'refdata', ([], ))])
1183
index = CombinedGraphIndex([index1, index2])
1184
self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1185
(index2, ('ref', 'erence'), 'refdata', ((), ))]),
1186
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
1187
self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1188
(index2, ('name', 'fin2'), 'beta', ((), ))]),
1189
set(index.iter_entries_prefix([('name', None)])))
1191
def test_iter_nothing_empty(self):
1192
index = CombinedGraphIndex([])
1193
self.assertEqual([], list(index.iter_entries([])))
1195
def test_iter_nothing_children_empty(self):
1196
index1 = self.make_index('name')
1197
index = CombinedGraphIndex([index1])
1198
self.assertEqual([], list(index.iter_entries([])))
1200
def test_iter_all_keys(self):
1201
index1 = self.make_index('1', 1, nodes=[
1202
(('name', ), 'data', ([('ref', )], ))])
1203
index2 = self.make_index('2', 1, nodes=[
1204
(('ref', ), 'refdata', ((), ))])
1205
index = CombinedGraphIndex([index1, index2])
1206
self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),
1207
(index2, ('ref', ), 'refdata', ((), ))]),
1208
set(index.iter_entries([('name', ), ('ref', )])))
1210
def test_iter_all_keys_dup_entry(self):
1211
index1 = self.make_index('1', 1, nodes=[
1212
(('name', ), 'data', ([('ref', )], )),
1213
(('ref', ), 'refdata', ([], ))])
1214
index2 = self.make_index('2', 1, nodes=[
1215
(('ref', ), 'refdata', ([], ))])
1216
index = CombinedGraphIndex([index1, index2])
1217
self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),
1218
(index1, ('ref', ), 'refdata', ((), ))]),
1219
set(index.iter_entries([('name', ), ('ref', )])))
1221
def test_iter_missing_entry_empty(self):
1222
index = CombinedGraphIndex([])
1223
self.assertEqual([], list(index.iter_entries([('a', )])))
1225
def test_iter_missing_entry_one_index(self):
1226
index1 = self.make_index('1')
1227
index = CombinedGraphIndex([index1])
1228
self.assertEqual([], list(index.iter_entries([('a', )])))
1230
def test_iter_missing_entry_two_index(self):
1231
index1 = self.make_index('1')
1232
index2 = self.make_index('2')
1233
index = CombinedGraphIndex([index1, index2])
1234
self.assertEqual([], list(index.iter_entries([('a', )])))
1236
def test_iter_entry_present_one_index_only(self):
1237
index1 = self.make_index('1', nodes=[(('key', ), '', ())])
1238
index2 = self.make_index('2', nodes=[])
1239
index = CombinedGraphIndex([index1, index2])
1240
self.assertEqual([(index1, ('key', ), '')],
1241
list(index.iter_entries([('key', )])))
1242
# and in the other direction
1243
index = CombinedGraphIndex([index2, index1])
1244
self.assertEqual([(index1, ('key', ), '')],
1245
list(index.iter_entries([('key', )])))
1247
def test_key_count_empty(self):
1248
index1 = self.make_index('1', nodes=[])
1249
index2 = self.make_index('2', nodes=[])
1250
index = CombinedGraphIndex([index1, index2])
1251
self.assertEqual(0, index.key_count())
1253
def test_key_count_sums_index_keys(self):
1254
index1 = self.make_index('1', nodes=[
1257
index2 = self.make_index('2', nodes=[(('1',), '', ())])
1258
index = CombinedGraphIndex([index1, index2])
1259
self.assertEqual(3, index.key_count())
1261
def test_validate_bad_child_index_errors(self):
1262
trans = self.get_transport()
1263
trans.put_bytes('name', "not an index\n")
1264
index1 = GraphIndex(trans, 'name', 13)
1265
index = CombinedGraphIndex([index1])
1266
self.assertRaises(errors.BadIndexFormatSignature, index.validate)
1268
def test_validate_empty(self):
1269
index = CombinedGraphIndex([])
1272
def test_key_count_reloads(self):
1273
index, reload_counter = self.make_combined_index_with_missing()
1274
self.assertEqual(2, index.key_count())
1275
self.assertEqual([1, 1, 0], reload_counter)
1277
def test_key_count_no_reload(self):
1278
index, reload_counter = self.make_combined_index_with_missing()
1279
index._reload_func = None
1280
# Without a _reload_func we just raise the exception
1281
self.assertRaises(errors.NoSuchFile, index.key_count)
1283
def test_key_count_reloads_and_fails(self):
1284
# We have deleted all underlying indexes, so we will try to reload, but
1285
# still fail. This is mostly to test we don't get stuck in an infinite
1286
# loop trying to reload
1287
index, reload_counter = self.make_combined_index_with_missing(
1289
self.assertRaises(errors.NoSuchFile, index.key_count)
1290
self.assertEqual([2, 1, 1], reload_counter)
1292
def test_iter_entries_reloads(self):
1293
index, reload_counter = self.make_combined_index_with_missing()
1294
result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1295
index3 = index._indices[0]
1296
self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
1298
self.assertEqual([1, 1, 0], reload_counter)
1300
def test_iter_entries_reloads_midway(self):
1301
# The first index still looks present, so we get interrupted mid-way
1303
index, reload_counter = self.make_combined_index_with_missing(['2'])
1304
index1, index2 = index._indices
1305
result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1306
index3 = index._indices[0]
1307
# We had already yielded '1', so we just go on to the next, we should
1308
# not yield '1' twice.
1309
self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1311
self.assertEqual([1, 1, 0], reload_counter)
1313
def test_iter_entries_no_reload(self):
1314
index, reload_counter = self.make_combined_index_with_missing()
1315
index._reload_func = None
1316
# Without a _reload_func we just raise the exception
1317
self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1319
def test_iter_entries_reloads_and_fails(self):
1320
index, reload_counter = self.make_combined_index_with_missing(
1322
self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1323
self.assertEqual([2, 1, 1], reload_counter)
1325
def test_iter_all_entries_reloads(self):
1326
index, reload_counter = self.make_combined_index_with_missing()
1327
result = list(index.iter_all_entries())
1328
index3 = index._indices[0]
1329
self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
1331
self.assertEqual([1, 1, 0], reload_counter)
1333
def test_iter_all_entries_reloads_midway(self):
1334
index, reload_counter = self.make_combined_index_with_missing(['2'])
1335
index1, index2 = index._indices
1336
result = list(index.iter_all_entries())
1337
index3 = index._indices[0]
1338
# We had already yielded '1', so we just go on to the next, we should
1339
# not yield '1' twice.
1340
self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1342
self.assertEqual([1, 1, 0], reload_counter)
1344
def test_iter_all_entries_no_reload(self):
1345
index, reload_counter = self.make_combined_index_with_missing()
1346
index._reload_func = None
1347
self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1349
def test_iter_all_entries_reloads_and_fails(self):
1350
index, reload_counter = self.make_combined_index_with_missing(
1352
self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1354
def test_iter_entries_prefix_reloads(self):
1355
index, reload_counter = self.make_combined_index_with_missing()
1356
result = list(index.iter_entries_prefix([('1',)]))
1357
index3 = index._indices[0]
1358
self.assertEqual([(index3, ('1',), '')], result)
1359
self.assertEqual([1, 1, 0], reload_counter)
1361
def test_iter_entries_prefix_reloads_midway(self):
1362
index, reload_counter = self.make_combined_index_with_missing(['2'])
1363
index1, index2 = index._indices
1364
result = list(index.iter_entries_prefix([('1',)]))
1365
index3 = index._indices[0]
1366
# We had already yielded '1', so we just go on to the next, we should
1367
# not yield '1' twice.
1368
self.assertEqual([(index1, ('1',), '')], result)
1369
self.assertEqual([1, 1, 0], reload_counter)
1371
def test_iter_entries_prefix_no_reload(self):
1372
index, reload_counter = self.make_combined_index_with_missing()
1373
index._reload_func = None
1374
self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1377
def test_iter_entries_prefix_reloads_and_fails(self):
1378
index, reload_counter = self.make_combined_index_with_missing(
1380
self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1384
def make_index_with_simple_nodes(self, name, num_nodes=1):
1385
"""Make an index named after 'name', with keys named after 'name' too.
1387
Nodes will have a value of '' and no references.
1390
(('index-%s-key-%s' % (name, n),), '', ())
1391
for n in range(1, num_nodes+1)]
1392
return self.make_index('index-%s' % name, 0, nodes=nodes)
1394
def test_reorder_after_iter_entries(self):
1395
# Four indices: [key1] in index1, [key2,key3] in index2, [] in index3,
1397
index = CombinedGraphIndex([])
1398
index.insert_index(0, self.make_index_with_simple_nodes('1'), '1')
1399
index.insert_index(1, self.make_index_with_simple_nodes('2'), '2')
1400
index.insert_index(2, self.make_index_with_simple_nodes('3'), '3')
1401
index.insert_index(3, self.make_index_with_simple_nodes('4'), '4')
1402
index1, index2, index3, index4 = index._indices
1403
# Query a key from index4 and index2.
1404
self.assertLength(2, list(index.iter_entries(
1405
[('index-4-key-1',), ('index-2-key-1',)])))
1406
# Now index2 and index4 should be moved to the front (and index1 should
1407
# still be before index3).
1408
self.assertEqual([index2, index4, index1, index3], index._indices)
1409
self.assertEqual(['2', '4', '1', '3'], index._index_names)
1411
def test_reorder_propagates_to_siblings(self):
1412
# Two CombinedGraphIndex objects, with the same number of indicies with
1414
cgi1 = CombinedGraphIndex([])
1415
cgi2 = CombinedGraphIndex([])
1416
cgi1.insert_index(0, self.make_index_with_simple_nodes('1-1'), 'one')
1417
cgi1.insert_index(1, self.make_index_with_simple_nodes('1-2'), 'two')
1418
cgi2.insert_index(0, self.make_index_with_simple_nodes('2-1'), 'one')
1419
cgi2.insert_index(1, self.make_index_with_simple_nodes('2-2'), 'two')
1420
index2_1, index2_2 = cgi2._indices
1421
cgi1.set_sibling_indices([cgi2])
1422
# Trigger a reordering in cgi1. cgi2 will be reordered as well.
1423
list(cgi1.iter_entries([('index-1-2-key-1',)]))
1424
self.assertEqual([index2_2, index2_1], cgi2._indices)
1425
self.assertEqual(['two', 'one'], cgi2._index_names)
1427
def test_validate_reloads(self):
1428
index, reload_counter = self.make_combined_index_with_missing()
1430
self.assertEqual([1, 1, 0], reload_counter)
1432
def test_validate_reloads_midway(self):
1433
index, reload_counter = self.make_combined_index_with_missing(['2'])
1436
def test_validate_no_reload(self):
1437
index, reload_counter = self.make_combined_index_with_missing()
1438
index._reload_func = None
1439
self.assertRaises(errors.NoSuchFile, index.validate)
1441
def test_validate_reloads_and_fails(self):
1442
index, reload_counter = self.make_combined_index_with_missing(
1444
self.assertRaises(errors.NoSuchFile, index.validate)
1446
def test_find_ancestors_across_indexes(self):
1451
index1 = self.make_index('12', ref_lists=1, nodes=[
1452
(key1, 'value', ([],)),
1453
(key2, 'value', ([key1],)),
1455
index2 = self.make_index('34', ref_lists=1, nodes=[
1456
(key3, 'value', ([key2],)),
1457
(key4, 'value', ([key3],)),
1459
c_index = CombinedGraphIndex([index1, index2])
1460
parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1461
self.assertEqual({key1: ()}, parent_map)
1462
self.assertEqual(set(), missing_keys)
1463
# Now look for a key from index2 which requires us to find the key in
1464
# the second index, and then continue searching for parents in the
1466
parent_map, missing_keys = c_index.find_ancestry([key3], 0)
1467
self.assertEqual({key1: (), key2: (key1,), key3: (key2,)}, parent_map)
1468
self.assertEqual(set(), missing_keys)
1470
def test_find_ancestors_missing_keys(self):
1475
index1 = self.make_index('12', ref_lists=1, nodes=[
1476
(key1, 'value', ([],)),
1477
(key2, 'value', ([key1],)),
1479
index2 = self.make_index('34', ref_lists=1, nodes=[
1480
(key3, 'value', ([key2],)),
1482
c_index = CombinedGraphIndex([index1, index2])
1483
# Searching for a key which is actually not present at all should
1484
# eventually converge
1485
parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1486
self.assertEqual({}, parent_map)
1487
self.assertEqual(set([key4]), missing_keys)
1489
def test_find_ancestors_no_indexes(self):
1490
c_index = CombinedGraphIndex([])
1492
parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1493
self.assertEqual({}, parent_map)
1494
self.assertEqual(set([key1]), missing_keys)
1496
def test_find_ancestors_ghost_parent(self):
1501
index1 = self.make_index('12', ref_lists=1, nodes=[
1502
(key1, 'value', ([],)),
1503
(key2, 'value', ([key1],)),
1505
index2 = self.make_index('34', ref_lists=1, nodes=[
1506
(key4, 'value', ([key2, key3],)),
1508
c_index = CombinedGraphIndex([index1, index2])
1509
# Searching for a key which is actually not present at all should
1510
# eventually converge
1511
parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1512
self.assertEqual({key4: (key2, key3), key2: (key1,), key1: ()},
1514
self.assertEqual(set([key3]), missing_keys)
1516
def test__find_ancestors_empty_index(self):
1517
index = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
1519
missing_keys = set()
1520
search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
1522
self.assertEqual(set(), search_keys)
1523
self.assertEqual({}, parent_map)
1524
self.assertEqual(set([('one',), ('two',)]), missing_keys)
1527
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
1529
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
1530
result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1531
result.add_nodes(nodes)
1534
def test_add_nodes_no_refs(self):
1535
index = self.make_index(0)
1536
index.add_nodes([(('name', ), 'data')])
1537
index.add_nodes([(('name2', ), ''), (('name3', ), '')])
1538
self.assertEqual(set([
1539
(index, ('name', ), 'data'),
1540
(index, ('name2', ), ''),
1541
(index, ('name3', ), ''),
1542
]), set(index.iter_all_entries()))
1544
def test_add_nodes(self):
1545
index = self.make_index(1)
1546
index.add_nodes([(('name', ), 'data', ([],))])
1547
index.add_nodes([(('name2', ), '', ([],)), (('name3', ), '', ([('r', )],))])
1548
self.assertEqual(set([
1549
(index, ('name', ), 'data', ((),)),
1550
(index, ('name2', ), '', ((),)),
1551
(index, ('name3', ), '', ((('r', ), ), )),
1552
]), set(index.iter_all_entries()))
1554
def test_iter_all_entries_empty(self):
1555
index = self.make_index()
1556
self.assertEqual([], list(index.iter_all_entries()))
1558
def test_iter_all_entries_simple(self):
1559
index = self.make_index(nodes=[(('name', ), 'data')])
1560
self.assertEqual([(index, ('name', ), 'data')],
1561
list(index.iter_all_entries()))
1563
def test_iter_all_entries_references(self):
1564
index = self.make_index(1, nodes=[
1565
(('name', ), 'data', ([('ref', )], )),
1566
(('ref', ), 'refdata', ([], ))])
1567
self.assertEqual(set([(index, ('name', ), 'data', ((('ref', ),),)),
1568
(index, ('ref', ), 'refdata', ((), ))]),
1569
set(index.iter_all_entries()))
1571
def test_iteration_absent_skipped(self):
1572
index = self.make_index(1, nodes=[
1573
(('name', ), 'data', ([('ref', )], ))])
1574
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
1575
set(index.iter_all_entries()))
1576
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
1577
set(index.iter_entries([('name', )])))
1578
self.assertEqual([], list(index.iter_entries([('ref', )])))
1580
def test_iter_all_keys(self):
1581
index = self.make_index(1, nodes=[
1582
(('name', ), 'data', ([('ref', )], )),
1583
(('ref', ), 'refdata', ([], ))])
1584
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
1585
(index, ('ref', ), 'refdata', ((), ))]),
1586
set(index.iter_entries([('name', ), ('ref', )])))
1588
def test_iter_key_prefix_1_key_element_no_refs(self):
1589
index = self.make_index( nodes=[
1590
(('name', ), 'data'),
1591
(('ref', ), 'refdata')])
1592
self.assertEqual(set([(index, ('name', ), 'data'),
1593
(index, ('ref', ), 'refdata')]),
1594
set(index.iter_entries_prefix([('name', ), ('ref', )])))
1596
def test_iter_key_prefix_1_key_element_refs(self):
1597
index = self.make_index(1, nodes=[
1598
(('name', ), 'data', ([('ref', )], )),
1599
(('ref', ), 'refdata', ([], ))])
1600
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
1601
(index, ('ref', ), 'refdata', ((), ))]),
1602
set(index.iter_entries_prefix([('name', ), ('ref', )])))
1604
def test_iter_key_prefix_2_key_element_no_refs(self):
1605
index = self.make_index(key_elements=2, nodes=[
1606
(('name', 'fin1'), 'data'),
1607
(('name', 'fin2'), 'beta'),
1608
(('ref', 'erence'), 'refdata')])
1609
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
1610
(index, ('ref', 'erence'), 'refdata')]),
1611
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
1612
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
1613
(index, ('name', 'fin2'), 'beta')]),
1614
set(index.iter_entries_prefix([('name', None)])))
1616
def test_iter_key_prefix_2_key_element_refs(self):
1617
index = self.make_index(1, key_elements=2, nodes=[
1618
(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
1619
(('name', 'fin2'), 'beta', ([], )),
1620
(('ref', 'erence'), 'refdata', ([], ))])
1621
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1622
(index, ('ref', 'erence'), 'refdata', ((), ))]),
1623
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
1624
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1625
(index, ('name', 'fin2'), 'beta', ((), ))]),
1626
set(index.iter_entries_prefix([('name', None)])))
1628
def test_iter_nothing_empty(self):
1629
index = self.make_index()
1630
self.assertEqual([], list(index.iter_entries([])))
1632
def test_iter_missing_entry_empty(self):
1633
index = self.make_index()
1634
self.assertEqual([], list(index.iter_entries(['a'])))
1636
def test_key_count_empty(self):
1637
index = self.make_index()
1638
self.assertEqual(0, index.key_count())
1640
def test_key_count_one(self):
1641
index = self.make_index(nodes=[(('name', ), '')])
1642
self.assertEqual(1, index.key_count())
1644
def test_key_count_two(self):
1645
index = self.make_index(nodes=[(('name', ), ''), (('foo', ), '')])
1646
self.assertEqual(2, index.key_count())
1648
def test_validate_empty(self):
1649
index = self.make_index()
1652
def test_validate_no_refs_content(self):
1653
index = self.make_index(nodes=[(('key', ), 'value')])
1657
class TestGraphIndexPrefixAdapter(TestCaseWithMemoryTransport):
1659
def make_index(self, ref_lists=1, key_elements=2, nodes=[], add_callback=False):
1660
result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1661
result.add_nodes(nodes)
1663
add_nodes_callback = result.add_nodes
1665
add_nodes_callback = None
1666
adapter = GraphIndexPrefixAdapter(result, ('prefix', ), key_elements - 1,
1667
add_nodes_callback=add_nodes_callback)
1668
return result, adapter
1670
def test_add_node(self):
1671
index, adapter = self.make_index(add_callback=True)
1672
adapter.add_node(('key',), 'value', ((('ref',),),))
1673
self.assertEqual(set([(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))]),
1674
set(index.iter_all_entries()))
1676
def test_add_nodes(self):
1677
index, adapter = self.make_index(add_callback=True)
1679
(('key',), 'value', ((('ref',),),)),
1680
(('key2',), 'value2', ((),)),
1682
self.assertEqual(set([
1683
(index, ('prefix', 'key2'), 'value2', ((),)),
1684
(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))
1686
set(index.iter_all_entries()))
1688
def test_construct(self):
1689
index = InMemoryGraphIndex()
1690
adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1)
1692
def test_construct_with_callback(self):
1693
index = InMemoryGraphIndex()
1694
adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1, index.add_nodes)
1696
def test_iter_all_entries_cross_prefix_map_errors(self):
1697
index, adapter = self.make_index(nodes=[
1698
(('prefix', 'key1'), 'data1', ((('prefixaltered', 'key2'),),))])
1699
self.assertRaises(errors.BadIndexData, list, adapter.iter_all_entries())
1701
def test_iter_all_entries(self):
1702
index, adapter = self.make_index(nodes=[
1703
(('notprefix', 'key1'), 'data', ((), )),
1704
(('prefix', 'key1'), 'data1', ((), )),
1705
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1706
self.assertEqual(set([(index, ('key1', ), 'data1', ((),)),
1707
(index, ('key2', ), 'data2', ((('key1',),),))]),
1708
set(adapter.iter_all_entries()))
1710
def test_iter_entries(self):
1711
index, adapter = self.make_index(nodes=[
1712
(('notprefix', 'key1'), 'data', ((), )),
1713
(('prefix', 'key1'), 'data1', ((), )),
1714
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1715
# ask for many - get all
1716
self.assertEqual(set([(index, ('key1', ), 'data1', ((),)),
1717
(index, ('key2', ), 'data2', ((('key1', ),),))]),
1718
set(adapter.iter_entries([('key1', ), ('key2', )])))
1719
# ask for one, get one
1720
self.assertEqual(set([(index, ('key1', ), 'data1', ((),))]),
1721
set(adapter.iter_entries([('key1', )])))
1722
# ask for missing, get none
1723
self.assertEqual(set(),
1724
set(adapter.iter_entries([('key3', )])))
1726
def test_iter_entries_prefix(self):
1727
index, adapter = self.make_index(key_elements=3, nodes=[
1728
(('notprefix', 'foo', 'key1'), 'data', ((), )),
1729
(('prefix', 'prefix2', 'key1'), 'data1', ((), )),
1730
(('prefix', 'prefix2', 'key2'), 'data2', ((('prefix', 'prefix2', 'key1'),),))])
1731
# ask for a prefix, get the results for just that prefix, adjusted.
1732
self.assertEqual(set([(index, ('prefix2', 'key1', ), 'data1', ((),)),
1733
(index, ('prefix2', 'key2', ), 'data2', ((('prefix2', 'key1', ),),))]),
1734
set(adapter.iter_entries_prefix([('prefix2', None)])))
1736
def test_key_count_no_matching_keys(self):
1737
index, adapter = self.make_index(nodes=[
1738
(('notprefix', 'key1'), 'data', ((), ))])
1739
self.assertEqual(0, adapter.key_count())
1741
def test_key_count_some_keys(self):
1742
index, adapter = self.make_index(nodes=[
1743
(('notprefix', 'key1'), 'data', ((), )),
1744
(('prefix', 'key1'), 'data1', ((), )),
1745
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1746
self.assertEqual(2, adapter.key_count())
1748
def test_validate(self):
1749
index, adapter = self.make_index()
1752
calls.append('called')
1753
index.validate = validate
1755
self.assertEqual(['called'], calls)
added
removed
bzrlib/tests/test_index.py
