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."""
29
class TestGraphIndexBuilder(tests.TestCaseWithMemoryTransport):
31
def test_build_index_empty(self):
32
builder = index.GraphIndexBuilder()
33
stream = builder.finish()
34
contents = stream.read()
36
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=0\n\n",
39
def test_build_index_empty_two_element_keys(self):
40
builder = index.GraphIndexBuilder(key_elements=2)
41
stream = builder.finish()
42
contents = stream.read()
44
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=0\n\n",
47
def test_build_index_one_reference_list_empty(self):
48
builder = index.GraphIndexBuilder(reference_lists=1)
49
stream = builder.finish()
50
contents = stream.read()
52
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=0\n\n",
55
def test_build_index_two_reference_list_empty(self):
56
builder = index.GraphIndexBuilder(reference_lists=2)
57
stream = builder.finish()
58
contents = stream.read()
60
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=0\n\n",
63
def test_build_index_one_node_no_refs(self):
64
builder = index.GraphIndexBuilder()
65
builder.add_node(('akey', ), 'data')
66
stream = builder.finish()
67
contents = stream.read()
69
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
70
"akey\x00\x00\x00data\n\n", contents)
72
def test_build_index_one_node_no_refs_accepts_empty_reflist(self):
73
builder = index.GraphIndexBuilder()
74
builder.add_node(('akey', ), 'data', ())
75
stream = builder.finish()
76
contents = stream.read()
78
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
79
"akey\x00\x00\x00data\n\n", contents)
81
def test_build_index_one_node_2_element_keys(self):
82
# multipart keys are separated by \x00 - because they are fixed length,
83
# not variable this does not cause any issues, and seems clearer to the
85
builder = index.GraphIndexBuilder(key_elements=2)
86
builder.add_node(('akey', 'secondpart'), 'data')
87
stream = builder.finish()
88
contents = stream.read()
90
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=1\n"
91
"akey\x00secondpart\x00\x00\x00data\n\n", contents)
93
def test_add_node_empty_value(self):
94
builder = index.GraphIndexBuilder()
95
builder.add_node(('akey', ), '')
96
stream = builder.finish()
97
contents = stream.read()
99
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
100
"akey\x00\x00\x00\n\n", contents)
102
def test_build_index_nodes_sorted(self):
103
# the highest sorted node comes first.
104
builder = index.GraphIndexBuilder()
105
# use three to have a good chance of glitching dictionary hash
106
# lookups etc. Insert in randomish order that is not correct
107
# and not the reverse of the correct order.
108
builder.add_node(('2002', ), 'data')
109
builder.add_node(('2000', ), 'data')
110
builder.add_node(('2001', ), 'data')
111
stream = builder.finish()
112
contents = stream.read()
114
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=3\n"
115
"2000\x00\x00\x00data\n"
116
"2001\x00\x00\x00data\n"
117
"2002\x00\x00\x00data\n"
120
def test_build_index_2_element_key_nodes_sorted(self):
121
# multiple element keys are sorted first-key, second-key.
122
builder = index.GraphIndexBuilder(key_elements=2)
123
# use three values of each key element, to have a good chance of
124
# glitching dictionary hash lookups etc. Insert in randomish order that
125
# is not correct and not the reverse of the correct order.
126
builder.add_node(('2002', '2002'), 'data')
127
builder.add_node(('2002', '2000'), 'data')
128
builder.add_node(('2002', '2001'), 'data')
129
builder.add_node(('2000', '2002'), 'data')
130
builder.add_node(('2000', '2000'), 'data')
131
builder.add_node(('2000', '2001'), 'data')
132
builder.add_node(('2001', '2002'), 'data')
133
builder.add_node(('2001', '2000'), 'data')
134
builder.add_node(('2001', '2001'), 'data')
135
stream = builder.finish()
136
contents = stream.read()
138
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=9\n"
139
"2000\x002000\x00\x00\x00data\n"
140
"2000\x002001\x00\x00\x00data\n"
141
"2000\x002002\x00\x00\x00data\n"
142
"2001\x002000\x00\x00\x00data\n"
143
"2001\x002001\x00\x00\x00data\n"
144
"2001\x002002\x00\x00\x00data\n"
145
"2002\x002000\x00\x00\x00data\n"
146
"2002\x002001\x00\x00\x00data\n"
147
"2002\x002002\x00\x00\x00data\n"
150
def test_build_index_reference_lists_are_included_one(self):
151
builder = index.GraphIndexBuilder(reference_lists=1)
152
builder.add_node(('key', ), 'data', ([], ))
153
stream = builder.finish()
154
contents = stream.read()
156
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
157
"key\x00\x00\x00data\n"
160
def test_build_index_reference_lists_with_2_element_keys(self):
161
builder = index.GraphIndexBuilder(reference_lists=1, key_elements=2)
162
builder.add_node(('key', 'key2'), 'data', ([], ))
163
stream = builder.finish()
164
contents = stream.read()
166
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=2\nlen=1\n"
167
"key\x00key2\x00\x00\x00data\n"
170
def test_build_index_reference_lists_are_included_two(self):
171
builder = index.GraphIndexBuilder(reference_lists=2)
172
builder.add_node(('key', ), 'data', ([], []))
173
stream = builder.finish()
174
contents = stream.read()
176
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
177
"key\x00\x00\t\x00data\n"
180
def test_clear_cache(self):
181
builder = index.GraphIndexBuilder(reference_lists=2)
182
# This is a no-op, but the api should exist
183
builder.clear_cache()
185
def test_node_references_are_byte_offsets(self):
186
builder = index.GraphIndexBuilder(reference_lists=1)
187
builder.add_node(('reference', ), 'data', ([], ))
188
builder.add_node(('key', ), 'data', ([('reference', )], ))
189
stream = builder.finish()
190
contents = stream.read()
192
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=2\n"
193
"key\x00\x0072\x00data\n"
194
"reference\x00\x00\x00data\n"
197
def test_node_references_are_cr_delimited(self):
198
builder = index.GraphIndexBuilder(reference_lists=1)
199
builder.add_node(('reference', ), 'data', ([], ))
200
builder.add_node(('reference2', ), 'data', ([], ))
201
builder.add_node(('key', ), 'data',
202
([('reference', ), ('reference2', )], ))
203
stream = builder.finish()
204
contents = stream.read()
206
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=3\n"
207
"key\x00\x00077\r094\x00data\n"
208
"reference\x00\x00\x00data\n"
209
"reference2\x00\x00\x00data\n"
212
def test_multiple_reference_lists_are_tab_delimited(self):
213
builder = index.GraphIndexBuilder(reference_lists=2)
214
builder.add_node(('keference', ), 'data', ([], []))
215
builder.add_node(('rey', ), 'data',
216
([('keference', )], [('keference', )]))
217
stream = builder.finish()
218
contents = stream.read()
220
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=2\n"
221
"keference\x00\x00\t\x00data\n"
222
"rey\x00\x0059\t59\x00data\n"
225
def test_add_node_referencing_missing_key_makes_absent(self):
226
builder = index.GraphIndexBuilder(reference_lists=1)
227
builder.add_node(('rey', ), 'data',
228
([('beference', ), ('aeference2', )], ))
229
stream = builder.finish()
230
contents = stream.read()
232
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
233
"aeference2\x00a\x00\x00\n"
234
"beference\x00a\x00\x00\n"
235
"rey\x00\x00074\r059\x00data\n"
238
def test_node_references_three_digits(self):
239
# test the node digit expands as needed.
240
builder = index.GraphIndexBuilder(reference_lists=1)
241
references = [(str(val), ) for val in range(8, -1, -1)]
242
builder.add_node(('2-key', ), '', (references, ))
243
stream = builder.finish()
244
contents = stream.read()
245
self.assertEqualDiff(
246
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
250
"2-key\x00\x00151\r145\r139\r133\r127\r121\r071\r065\r059\x00\n"
259
def test_absent_has_no_reference_overhead(self):
260
# the offsets after an absent record should be correct when there are
261
# >1 reference lists.
262
builder = index.GraphIndexBuilder(reference_lists=2)
263
builder.add_node(('parent', ), '', ([('aail', ), ('zther', )], []))
264
stream = builder.finish()
265
contents = stream.read()
267
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
268
"aail\x00a\x00\x00\n"
269
"parent\x00\x0059\r84\t\x00\n"
270
"zther\x00a\x00\x00\n"
273
def test_add_node_bad_key(self):
274
builder = index.GraphIndexBuilder()
275
for bad_char in '\t\n\x0b\x0c\r\x00 ':
276
self.assertRaises(errors.BadIndexKey, builder.add_node,
277
('a%skey' % bad_char, ), 'data')
278
self.assertRaises(errors.BadIndexKey, builder.add_node,
280
self.assertRaises(errors.BadIndexKey, builder.add_node,
281
'not-a-tuple', 'data')
283
self.assertRaises(errors.BadIndexKey, builder.add_node,
286
self.assertRaises(errors.BadIndexKey, builder.add_node,
287
('primary', 'secondary'), 'data')
288
# secondary key elements get checked too:
289
builder = index.GraphIndexBuilder(key_elements=2)
290
for bad_char in '\t\n\x0b\x0c\r\x00 ':
291
self.assertRaises(errors.BadIndexKey, builder.add_node,
292
('prefix', 'a%skey' % bad_char), 'data')
294
def test_add_node_bad_data(self):
295
builder = index.GraphIndexBuilder()
296
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
298
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
301
def test_add_node_bad_mismatched_ref_lists_length(self):
302
builder = index.GraphIndexBuilder()
303
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
305
builder = index.GraphIndexBuilder(reference_lists=1)
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', ),
312
builder = index.GraphIndexBuilder(reference_lists=2)
313
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
315
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
317
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
318
'data aa', ([], [], []))
320
def test_add_node_bad_key_in_reference_lists(self):
321
# first list, first key - trivial
322
builder = index.GraphIndexBuilder(reference_lists=1)
323
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
324
'data aa', ([('a key', )], ))
325
# references keys must be tuples too
326
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
327
'data aa', (['not-a-tuple'], ))
329
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
332
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
333
'data aa', ([('primary', 'secondary')], ))
334
# need to check more than the first key in the list
335
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
336
'data aa', ([('agoodkey', ), ('that is a bad key', )], ))
337
# and if there is more than one list it should be getting checked
339
builder = index.GraphIndexBuilder(reference_lists=2)
340
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
341
'data aa', ([], ['a bad key']))
343
def test_add_duplicate_key(self):
344
builder = index.GraphIndexBuilder()
345
builder.add_node(('key', ), 'data')
346
self.assertRaises(errors.BadIndexDuplicateKey,
347
builder.add_node, ('key', ), 'data')
349
def test_add_duplicate_key_2_elements(self):
350
builder = index.GraphIndexBuilder(key_elements=2)
351
builder.add_node(('key', 'key'), 'data')
352
self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node,
353
('key', 'key'), 'data')
355
def test_add_key_after_referencing_key(self):
356
builder = index.GraphIndexBuilder(reference_lists=1)
357
builder.add_node(('key', ), 'data', ([('reference', )], ))
358
builder.add_node(('reference', ), 'data', ([],))
360
def test_add_key_after_referencing_key_2_elements(self):
361
builder = index.GraphIndexBuilder(reference_lists=1, key_elements=2)
362
builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
363
builder.add_node(('reference', 'tokey'), 'data', ([],))
365
def test_set_optimize(self):
366
builder = index.GraphIndexBuilder(reference_lists=1, key_elements=2)
367
builder.set_optimize(for_size=True)
368
self.assertTrue(builder._optimize_for_size)
369
builder.set_optimize(for_size=False)
370
self.assertFalse(builder._optimize_for_size)
373
class TestGraphIndex(tests.TestCaseWithMemoryTransport):
375
def make_key(self, number):
376
return (str(number) + 'X'*100,)
378
def make_value(self, number):
379
return str(number) + 'Y'*100
381
def make_nodes(self, count=64):
382
# generate a big enough index that we only read some of it on a typical
385
for counter in range(count):
386
nodes.append((self.make_key(counter), self.make_value(counter), ()))
389
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
390
builder = index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
391
for key, value, references in nodes:
392
builder.add_node(key, value, references)
393
stream = builder.finish()
394
trans = transport.get_transport_from_url('trace+' + self.get_url())
395
size = trans.put_file('index', stream)
396
return index.GraphIndex(trans, 'index', size)
398
def make_index_with_offset(self, ref_lists=0, key_elements=1, nodes=[],
400
builder = index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
401
for key, value, references in nodes:
402
builder.add_node(key, value, references)
403
content = builder.finish().read()
405
trans = self.get_transport()
406
trans.put_bytes('index', (' '*offset) + content)
407
return index.GraphIndex(trans, 'index', size, offset=offset)
409
def test_clear_cache(self):
410
index = self.make_index()
411
# For now, we just want to make sure the api is available. As this is
412
# old code, we don't really worry if it *does* anything.
415
def test_open_bad_index_no_error(self):
416
trans = self.get_transport()
417
trans.put_bytes('name', "not an index\n")
418
idx = index.GraphIndex(trans, 'name', 13)
420
def test_with_offset(self):
421
nodes = self.make_nodes(200)
422
idx = self.make_index_with_offset(offset=1234567, nodes=nodes)
423
self.assertEqual(200, idx.key_count())
425
def test_buffer_all_with_offset(self):
426
nodes = self.make_nodes(200)
427
idx = self.make_index_with_offset(offset=1234567, nodes=nodes)
429
self.assertEqual(200, idx.key_count())
431
def test_side_effect_buffering_with_offset(self):
432
nodes = self.make_nodes(20)
433
index = self.make_index_with_offset(offset=1234567, nodes=nodes)
434
index._transport.recommended_page_size = lambda:64*1024
435
subset_nodes = [nodes[0][0], nodes[10][0], nodes[19][0]]
436
entries = [n[1] for n in index.iter_entries(subset_nodes)]
437
self.assertEqual(sorted(subset_nodes), sorted(entries))
438
self.assertEqual(20, index.key_count())
440
def test_open_sets_parsed_map_empty(self):
441
index = self.make_index()
442
self.assertEqual([], index._parsed_byte_map)
443
self.assertEqual([], index._parsed_key_map)
445
def test_key_count_buffers(self):
446
index = self.make_index(nodes=self.make_nodes(2))
447
# reset the transport log
448
del index._transport._activity[:]
449
self.assertEqual(2, index.key_count())
450
# We should have requested reading the header bytes
452
('readv', 'index', [(0, 200)], True, index._size),
454
index._transport._activity)
455
# And that should have been enough to trigger reading the whole index
457
self.assertIsNot(None, index._nodes)
459
def test_lookup_key_via_location_buffers(self):
460
index = self.make_index()
461
# reset the transport log
462
del index._transport._activity[:]
463
# do a _lookup_keys_via_location call for the middle of the file, which
464
# is what bisection uses.
465
result = index._lookup_keys_via_location(
466
[(index._size // 2, ('missing', ))])
467
# this should have asked for a readv request, with adjust_for_latency,
468
# and two regions: the header, and half-way into the file.
470
('readv', 'index', [(30, 30), (0, 200)], True, 60),
472
index._transport._activity)
473
# and the result should be that the key cannot be present, because this
474
# is a trivial index.
475
self.assertEqual([((index._size // 2, ('missing', )), False)],
477
# And this should have caused the file to be fully buffered
478
self.assertIsNot(None, index._nodes)
479
self.assertEqual([], index._parsed_byte_map)
481
def test_first_lookup_key_via_location(self):
482
# We need enough data so that the _HEADER_READV doesn't consume the
483
# whole file. We always read 800 bytes for every key, and the local
484
# transport natural expansion is 4096 bytes. So we have to have >8192
485
# bytes or we will trigger "buffer_all".
486
# We also want the 'missing' key to fall within the range that *did*
489
index = self.make_index(nodes=self.make_nodes(64))
490
# reset the transport log
491
del index._transport._activity[:]
492
# do a _lookup_keys_via_location call for the middle of the file, which
493
# is what bisection uses.
494
start_lookup = index._size // 2
495
result = index._lookup_keys_via_location(
496
[(start_lookup, ('40missing', ))])
497
# this should have asked for a readv request, with adjust_for_latency,
498
# and two regions: the header, and half-way into the file.
501
[(start_lookup, 800), (0, 200)], True, index._size),
503
index._transport._activity)
504
# and the result should be that the key cannot be present, because this
505
# is a trivial index.
506
self.assertEqual([((start_lookup, ('40missing', )), False)],
508
# And this should not have caused the file to be fully buffered
509
self.assertIs(None, index._nodes)
510
# And the regions of the file that have been parsed should be in the
511
# parsed_byte_map and the parsed_key_map
512
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
513
self.assertEqual([(None, self.make_key(26)),
514
(self.make_key(31), self.make_key(48))],
515
index._parsed_key_map)
517
def test_parsing_non_adjacent_data_trims(self):
518
index = self.make_index(nodes=self.make_nodes(64))
519
result = index._lookup_keys_via_location(
520
[(index._size // 2, ('40', ))])
521
# and the result should be that the key cannot be present, because key is
522
# in the middle of the observed data from a 4K read - the smallest transport
523
# will do today with this api.
524
self.assertEqual([((index._size // 2, ('40', )), False)],
526
# and we should have a parse map that includes the header and the
527
# region that was parsed after trimming.
528
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
529
self.assertEqual([(None, self.make_key(26)),
530
(self.make_key(31), self.make_key(48))],
531
index._parsed_key_map)
533
def test_parsing_data_handles_parsed_contained_regions(self):
534
# the following patten creates a parsed region that is wholly within a
535
# single result from the readv layer:
536
# .... single-read (readv-minimum-size) ...
537
# which then trims the start and end so the parsed size is < readv
539
# then a dual lookup (or a reference lookup for that matter) which
540
# abuts or overlaps the parsed region on both sides will need to
541
# discard the data in the middle, but parse the end as well.
543
# we test this by doing a single lookup to seed the data, then
544
# a lookup for two keys that are present, and adjacent -
545
# we except both to be found, and the parsed byte map to include the
546
# locations of both keys.
547
index = self.make_index(nodes=self.make_nodes(128))
548
result = index._lookup_keys_via_location(
549
[(index._size // 2, ('40', ))])
550
# and we should have a parse map that includes the header and the
551
# region that was parsed after trimming.
552
self.assertEqual([(0, 4045), (11759, 15707)], index._parsed_byte_map)
553
self.assertEqual([(None, self.make_key(116)),
554
(self.make_key(35), self.make_key(51))],
555
index._parsed_key_map)
556
# now ask for two keys, right before and after the parsed region
557
result = index._lookup_keys_via_location(
558
[(11450, self.make_key(34)), (15707, self.make_key(52))])
560
((11450, self.make_key(34)),
561
(index, self.make_key(34), self.make_value(34))),
562
((15707, self.make_key(52)),
563
(index, self.make_key(52), self.make_value(52))),
566
self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)
568
def test_lookup_missing_key_answers_without_io_when_map_permits(self):
569
# generate a big enough index that we only read some of it on a typical
571
index = self.make_index(nodes=self.make_nodes(64))
572
# lookup the keys in the middle of the file
573
result =index._lookup_keys_via_location(
574
[(index._size // 2, ('40', ))])
575
# check the parse map, this determines the test validity
576
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
577
self.assertEqual([(None, self.make_key(26)),
578
(self.make_key(31), self.make_key(48))],
579
index._parsed_key_map)
580
# reset the transport log
581
del index._transport._activity[:]
582
# now looking up a key in the portion of the file already parsed should
583
# not create a new transport request, and should return False (cannot
584
# be in the index) - even when the byte location we ask for is outside
586
result = index._lookup_keys_via_location(
588
self.assertEqual([((4000, ('40', )), False)],
590
self.assertEqual([], index._transport._activity)
592
def test_lookup_present_key_answers_without_io_when_map_permits(self):
593
# generate a big enough index that we only read some of it on a typical
595
index = self.make_index(nodes=self.make_nodes(64))
596
# lookup the keys in the middle of the file
597
result =index._lookup_keys_via_location(
598
[(index._size // 2, ('40', ))])
599
# check the parse map, this determines the test validity
600
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
601
self.assertEqual([(None, self.make_key(26)),
602
(self.make_key(31), self.make_key(48))],
603
index._parsed_key_map)
604
# reset the transport log
605
del index._transport._activity[:]
606
# now looking up a key in the portion of the file already parsed should
607
# not create a new transport request, and should return False (cannot
608
# be in the index) - even when the byte location we ask for is outside
611
result = index._lookup_keys_via_location([(4000, self.make_key(40))])
613
[((4000, self.make_key(40)),
614
(index, self.make_key(40), self.make_value(40)))],
616
self.assertEqual([], index._transport._activity)
618
def test_lookup_key_below_probed_area(self):
619
# generate a big enough index that we only read some of it on a typical
621
index = self.make_index(nodes=self.make_nodes(64))
622
# ask for the key in the middle, but a key that is located in the
623
# unparsed region before the middle.
624
result =index._lookup_keys_via_location(
625
[(index._size // 2, ('30', ))])
626
# check the parse map, this determines the test validity
627
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
628
self.assertEqual([(None, self.make_key(26)),
629
(self.make_key(31), self.make_key(48))],
630
index._parsed_key_map)
631
self.assertEqual([((index._size // 2, ('30', )), -1)],
634
def test_lookup_key_above_probed_area(self):
635
# generate a big enough index that we only read some of it on a typical
637
index = self.make_index(nodes=self.make_nodes(64))
638
# ask for the key in the middle, but a key that is located in the
639
# unparsed region after the middle.
640
result =index._lookup_keys_via_location(
641
[(index._size // 2, ('50', ))])
642
# check the parse map, this determines the test validity
643
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
644
self.assertEqual([(None, self.make_key(26)),
645
(self.make_key(31), self.make_key(48))],
646
index._parsed_key_map)
647
self.assertEqual([((index._size // 2, ('50', )), +1)],
650
def test_lookup_key_resolves_references(self):
651
# generate a big enough index that we only read some of it on a typical
654
for counter in range(99):
655
nodes.append((self.make_key(counter), self.make_value(counter),
656
((self.make_key(counter + 20),),) ))
657
index = self.make_index(ref_lists=1, nodes=nodes)
658
# lookup a key in the middle that does not exist, so that when we can
659
# check that the referred-to-keys are not accessed automatically.
660
index_size = index._size
661
index_center = index_size // 2
662
result = index._lookup_keys_via_location(
663
[(index_center, ('40', ))])
664
# check the parse map - only the start and middle should have been
666
self.assertEqual([(0, 4027), (10198, 14028)], index._parsed_byte_map)
667
self.assertEqual([(None, self.make_key(17)),
668
(self.make_key(44), self.make_key(5))],
669
index._parsed_key_map)
670
# and check the transport activity likewise.
672
[('readv', 'index', [(index_center, 800), (0, 200)], True,
674
index._transport._activity)
675
# reset the transport log for testing the reference lookup
676
del index._transport._activity[:]
677
# now looking up a key in the portion of the file already parsed should
678
# only perform IO to resolve its key references.
679
result = index._lookup_keys_via_location([(11000, self.make_key(45))])
681
[((11000, self.make_key(45)),
682
(index, self.make_key(45), self.make_value(45),
683
((self.make_key(65),),)))],
685
self.assertEqual([('readv', 'index', [(15093, 800)], True, index_size)],
686
index._transport._activity)
688
def test_lookup_key_can_buffer_all(self):
690
for counter in range(64):
691
nodes.append((self.make_key(counter), self.make_value(counter),
692
((self.make_key(counter + 20),),) ))
693
index = self.make_index(ref_lists=1, nodes=nodes)
694
# lookup a key in the middle that does not exist, so that when we can
695
# check that the referred-to-keys are not accessed automatically.
696
index_size = index._size
697
index_center = index_size // 2
698
result = index._lookup_keys_via_location([(index_center, ('40', ))])
699
# check the parse map - only the start and middle should have been
701
self.assertEqual([(0, 3890), (6444, 10274)], index._parsed_byte_map)
702
self.assertEqual([(None, self.make_key(25)),
703
(self.make_key(37), self.make_key(52))],
704
index._parsed_key_map)
705
# and check the transport activity likewise.
707
[('readv', 'index', [(index_center, 800), (0, 200)], True,
709
index._transport._activity)
710
# reset the transport log for testing the reference lookup
711
del index._transport._activity[:]
712
# now looking up a key in the portion of the file already parsed should
713
# only perform IO to resolve its key references.
714
result = index._lookup_keys_via_location([(7000, self.make_key(40))])
716
[((7000, self.make_key(40)),
717
(index, self.make_key(40), self.make_value(40),
718
((self.make_key(60),),)))],
720
# Resolving the references would have required more data read, and we
721
# are already above the 50% threshold, so it triggered a _buffer_all
722
self.assertEqual([('get', 'index')], index._transport._activity)
724
def test_iter_all_entries_empty(self):
725
index = self.make_index()
726
self.assertEqual([], list(index.iter_all_entries()))
728
def test_iter_all_entries_simple(self):
729
index = self.make_index(nodes=[(('name', ), 'data', ())])
730
self.assertEqual([(index, ('name', ), 'data')],
731
list(index.iter_all_entries()))
733
def test_iter_all_entries_simple_2_elements(self):
734
index = self.make_index(key_elements=2,
735
nodes=[(('name', 'surname'), 'data', ())])
736
self.assertEqual([(index, ('name', 'surname'), 'data')],
737
list(index.iter_all_entries()))
739
def test_iter_all_entries_references_resolved(self):
740
index = self.make_index(1, nodes=[
741
(('name', ), 'data', ([('ref', )], )),
742
(('ref', ), 'refdata', ([], ))])
743
self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
744
(index, ('ref', ), 'refdata', ((), ))},
745
set(index.iter_all_entries()))
747
def test_iter_entries_buffers_once(self):
748
index = self.make_index(nodes=self.make_nodes(2))
749
# reset the transport log
750
del index._transport._activity[:]
751
self.assertEqual({(index, self.make_key(1), self.make_value(1))},
752
set(index.iter_entries([self.make_key(1)])))
753
# We should have requested reading the header bytes
754
# But not needed any more than that because it would have triggered a
757
('readv', 'index', [(0, 200)], True, index._size),
759
index._transport._activity)
760
# And that should have been enough to trigger reading the whole index
762
self.assertIsNot(None, index._nodes)
764
def test_iter_entries_buffers_by_bytes_read(self):
765
index = self.make_index(nodes=self.make_nodes(64))
766
list(index.iter_entries([self.make_key(10)]))
767
# The first time through isn't enough to trigger a buffer all
768
self.assertIs(None, index._nodes)
769
self.assertEqual(4096, index._bytes_read)
770
# Grabbing a key in that same page won't trigger a buffer all, as we
771
# still haven't read 50% of the file
772
list(index.iter_entries([self.make_key(11)]))
773
self.assertIs(None, index._nodes)
774
self.assertEqual(4096, index._bytes_read)
775
# We haven't read more data, so reading outside the range won't trigger
776
# a buffer all right away
777
list(index.iter_entries([self.make_key(40)]))
778
self.assertIs(None, index._nodes)
779
self.assertEqual(8192, index._bytes_read)
780
# On the next pass, we will not trigger buffer all if the key is
781
# available without reading more
782
list(index.iter_entries([self.make_key(32)]))
783
self.assertIs(None, index._nodes)
784
# But if we *would* need to read more to resolve it, then we will
786
list(index.iter_entries([self.make_key(60)]))
787
self.assertIsNot(None, index._nodes)
789
def test_iter_entries_references_resolved(self):
790
index = self.make_index(1, nodes=[
791
(('name', ), 'data', ([('ref', ), ('ref', )], )),
792
(('ref', ), 'refdata', ([], ))])
793
self.assertEqual({(index, ('name', ), 'data', ((('ref',),('ref',)),)),
794
(index, ('ref', ), 'refdata', ((), ))},
795
set(index.iter_entries([('name',), ('ref',)])))
797
def test_iter_entries_references_2_refs_resolved(self):
798
index = self.make_index(2, nodes=[
799
(('name', ), 'data', ([('ref', )], [('ref', )])),
800
(('ref', ), 'refdata', ([], []))])
801
self.assertEqual({(index, ('name', ), 'data', ((('ref',),), (('ref',),))),
802
(index, ('ref', ), 'refdata', ((), ()))},
803
set(index.iter_entries([('name',), ('ref',)])))
805
def test_iteration_absent_skipped(self):
806
index = self.make_index(1, nodes=[
807
(('name', ), 'data', ([('ref', )], ))])
808
self.assertEqual({(index, ('name', ), 'data', ((('ref',),),))},
809
set(index.iter_all_entries()))
810
self.assertEqual({(index, ('name', ), 'data', ((('ref',),),))},
811
set(index.iter_entries([('name', )])))
812
self.assertEqual([], list(index.iter_entries([('ref', )])))
814
def test_iteration_absent_skipped_2_element_keys(self):
815
index = self.make_index(1, key_elements=2, nodes=[
816
(('name', 'fin'), 'data', ([('ref', 'erence')], ))])
817
self.assertEqual({(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))},
818
set(index.iter_all_entries()))
819
self.assertEqual({(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))},
820
set(index.iter_entries([('name', 'fin')])))
821
self.assertEqual([], list(index.iter_entries([('ref', 'erence')])))
823
def test_iter_all_keys(self):
824
index = self.make_index(1, nodes=[
825
(('name', ), 'data', ([('ref', )], )),
826
(('ref', ), 'refdata', ([], ))])
827
self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
828
(index, ('ref', ), 'refdata', ((), ))},
829
set(index.iter_entries([('name', ), ('ref', )])))
831
def test_iter_nothing_empty(self):
832
index = self.make_index()
833
self.assertEqual([], list(index.iter_entries([])))
835
def test_iter_missing_entry_empty(self):
836
index = self.make_index()
837
self.assertEqual([], list(index.iter_entries([('a', )])))
839
def test_iter_missing_entry_empty_no_size(self):
840
idx = self.make_index()
841
idx = index.GraphIndex(idx._transport, 'index', None)
842
self.assertEqual([], list(idx.iter_entries([('a', )])))
844
def test_iter_key_prefix_1_element_key_None(self):
845
index = self.make_index()
846
self.assertRaises(errors.BadIndexKey, list,
847
index.iter_entries_prefix([(None, )]))
849
def test_iter_key_prefix_wrong_length(self):
850
index = self.make_index()
851
self.assertRaises(errors.BadIndexKey, list,
852
index.iter_entries_prefix([('foo', None)]))
853
index = self.make_index(key_elements=2)
854
self.assertRaises(errors.BadIndexKey, list,
855
index.iter_entries_prefix([('foo', )]))
856
self.assertRaises(errors.BadIndexKey, list,
857
index.iter_entries_prefix([('foo', None, None)]))
859
def test_iter_key_prefix_1_key_element_no_refs(self):
860
index = self.make_index( nodes=[
861
(('name', ), 'data', ()),
862
(('ref', ), 'refdata', ())])
863
self.assertEqual({(index, ('name', ), 'data'),
864
(index, ('ref', ), 'refdata')},
865
set(index.iter_entries_prefix([('name', ), ('ref', )])))
867
def test_iter_key_prefix_1_key_element_refs(self):
868
index = self.make_index(1, nodes=[
869
(('name', ), 'data', ([('ref', )], )),
870
(('ref', ), 'refdata', ([], ))])
871
self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
872
(index, ('ref', ), 'refdata', ((), ))},
873
set(index.iter_entries_prefix([('name', ), ('ref', )])))
875
def test_iter_key_prefix_2_key_element_no_refs(self):
876
index = self.make_index(key_elements=2, nodes=[
877
(('name', 'fin1'), 'data', ()),
878
(('name', 'fin2'), 'beta', ()),
879
(('ref', 'erence'), 'refdata', ())])
880
self.assertEqual({(index, ('name', 'fin1'), 'data'),
881
(index, ('ref', 'erence'), 'refdata')},
882
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
883
self.assertEqual({(index, ('name', 'fin1'), 'data'),
884
(index, ('name', 'fin2'), 'beta')},
885
set(index.iter_entries_prefix([('name', None)])))
887
def test_iter_key_prefix_2_key_element_refs(self):
888
index = self.make_index(1, key_elements=2, nodes=[
889
(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
890
(('name', 'fin2'), 'beta', ([], )),
891
(('ref', 'erence'), 'refdata', ([], ))])
892
self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
893
(index, ('ref', 'erence'), 'refdata', ((), ))},
894
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
895
self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
896
(index, ('name', 'fin2'), 'beta', ((), ))},
897
set(index.iter_entries_prefix([('name', None)])))
899
def test_key_count_empty(self):
900
index = self.make_index()
901
self.assertEqual(0, index.key_count())
903
def test_key_count_one(self):
904
index = self.make_index(nodes=[(('name', ), '', ())])
905
self.assertEqual(1, index.key_count())
907
def test_key_count_two(self):
908
index = self.make_index(nodes=[
909
(('name', ), '', ()), (('foo', ), '', ())])
910
self.assertEqual(2, index.key_count())
912
def test_read_and_parse_tracks_real_read_value(self):
913
index = self.make_index(nodes=self.make_nodes(10))
914
del index._transport._activity[:]
915
index._read_and_parse([(0, 200)])
917
('readv', 'index', [(0, 200)], True, index._size),
919
index._transport._activity)
920
# The readv expansion code will expand the initial request to 4096
921
# bytes, which is more than enough to read the entire index, and we
922
# will track the fact that we read that many bytes.
923
self.assertEqual(index._size, index._bytes_read)
925
def test_read_and_parse_triggers_buffer_all(self):
926
index = self.make_index(key_elements=2, nodes=[
927
(('name', 'fin1'), 'data', ()),
928
(('name', 'fin2'), 'beta', ()),
929
(('ref', 'erence'), 'refdata', ())])
930
self.assertTrue(index._size > 0)
931
self.assertIs(None, index._nodes)
932
index._read_and_parse([(0, index._size)])
933
self.assertIsNot(None, index._nodes)
935
def test_validate_bad_index_errors(self):
936
trans = self.get_transport()
937
trans.put_bytes('name', "not an index\n")
938
idx = index.GraphIndex(trans, 'name', 13)
939
self.assertRaises(errors.BadIndexFormatSignature, idx.validate)
941
def test_validate_bad_node_refs(self):
942
idx = self.make_index(2)
943
trans = self.get_transport()
944
content = trans.get_bytes('index')
945
# change the options line to end with a rather than a parseable number
946
new_content = content[:-2] + 'a\n\n'
947
trans.put_bytes('index', new_content)
948
self.assertRaises(errors.BadIndexOptions, idx.validate)
950
def test_validate_missing_end_line_empty(self):
951
index = self.make_index(2)
952
trans = self.get_transport()
953
content = trans.get_bytes('index')
954
# truncate the last byte
955
trans.put_bytes('index', content[:-1])
956
self.assertRaises(errors.BadIndexData, index.validate)
958
def test_validate_missing_end_line_nonempty(self):
959
index = self.make_index(2, nodes=[(('key', ), '', ([], []))])
960
trans = self.get_transport()
961
content = trans.get_bytes('index')
962
# truncate the last byte
963
trans.put_bytes('index', content[:-1])
964
self.assertRaises(errors.BadIndexData, index.validate)
966
def test_validate_empty(self):
967
index = self.make_index()
970
def test_validate_no_refs_content(self):
971
index = self.make_index(nodes=[(('key', ), 'value', ())])
974
# XXX: external_references tests are duplicated in test_btree_index. We
975
# probably should have per_graph_index tests...
976
def test_external_references_no_refs(self):
977
index = self.make_index(ref_lists=0, nodes=[])
978
self.assertRaises(ValueError, index.external_references, 0)
980
def test_external_references_no_results(self):
981
index = self.make_index(ref_lists=1, nodes=[
982
(('key',), 'value', ([],))])
983
self.assertEqual(set(), index.external_references(0))
985
def test_external_references_missing_ref(self):
986
missing_key = ('missing',)
987
index = self.make_index(ref_lists=1, nodes=[
988
(('key',), 'value', ([missing_key],))])
989
self.assertEqual({missing_key}, index.external_references(0))
991
def test_external_references_multiple_ref_lists(self):
992
missing_key = ('missing',)
993
index = self.make_index(ref_lists=2, nodes=[
994
(('key',), 'value', ([], [missing_key]))])
995
self.assertEqual(set([]), index.external_references(0))
996
self.assertEqual({missing_key}, index.external_references(1))
998
def test_external_references_two_records(self):
999
index = self.make_index(ref_lists=1, nodes=[
1000
(('key-1',), 'value', ([('key-2',)],)),
1001
(('key-2',), 'value', ([],)),
1003
self.assertEqual(set([]), index.external_references(0))
1005
def test__find_ancestors(self):
1008
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1009
(key1, 'value', ([key2],)),
1010
(key2, 'value', ([],)),
1013
missing_keys = set()
1014
search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
1015
self.assertEqual({key1: (key2,)}, parent_map)
1016
self.assertEqual(set(), missing_keys)
1017
self.assertEqual({key2}, search_keys)
1018
search_keys = index._find_ancestors(search_keys, 0, parent_map,
1020
self.assertEqual({key1: (key2,), key2: ()}, parent_map)
1021
self.assertEqual(set(), missing_keys)
1022
self.assertEqual(set(), search_keys)
1024
def test__find_ancestors_w_missing(self):
1028
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1029
(key1, 'value', ([key2],)),
1030
(key2, 'value', ([],)),
1033
missing_keys = set()
1034
search_keys = index._find_ancestors([key2, key3], 0, parent_map,
1036
self.assertEqual({key2: ()}, parent_map)
1037
self.assertEqual({key3}, missing_keys)
1038
self.assertEqual(set(), search_keys)
1040
def test__find_ancestors_dont_search_known(self):
1044
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1045
(key1, 'value', ([key2],)),
1046
(key2, 'value', ([key3],)),
1047
(key3, 'value', ([],)),
1049
# We already know about key2, so we won't try to search for key3
1050
parent_map = {key2: (key3,)}
1051
missing_keys = set()
1052
search_keys = index._find_ancestors([key1], 0, parent_map,
1054
self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1055
self.assertEqual(set(), missing_keys)
1056
self.assertEqual(set(), search_keys)
1058
def test_supports_unlimited_cache(self):
1059
builder = index.GraphIndexBuilder(0, key_elements=1)
1060
stream = builder.finish()
1061
trans = self.get_transport()
1062
size = trans.put_file('index', stream)
1063
# It doesn't matter what unlimited_cache does here, just that it can be
1065
idx = index.GraphIndex(trans, 'index', size, unlimited_cache=True)
1068
class TestCombinedGraphIndex(tests.TestCaseWithMemoryTransport):
1070
def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
1071
builder = index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
1072
for key, value, references in nodes:
1073
builder.add_node(key, value, references)
1074
stream = builder.finish()
1075
trans = self.get_transport()
1076
size = trans.put_file(name, stream)
1077
return index.GraphIndex(trans, name, size)
1079
def make_combined_index_with_missing(self, missing=['1', '2']):
1080
"""Create a CombinedGraphIndex which will have missing indexes.
1082
This creates a CGI which thinks it has 2 indexes, however they have
1083
been deleted. If CGI._reload_func() is called, then it will repopulate
1086
:param missing: The underlying indexes to delete
1087
:return: (CombinedGraphIndex, reload_counter)
1089
idx1 = self.make_index('1', nodes=[(('1',), '', ())])
1090
idx2 = self.make_index('2', nodes=[(('2',), '', ())])
1091
idx3 = self.make_index('3', nodes=[
1095
# total_reloads, num_changed, num_unchanged
1096
reload_counter = [0, 0, 0]
1098
reload_counter[0] += 1
1099
new_indices = [idx3]
1100
if idx._indices == new_indices:
1101
reload_counter[2] += 1
1103
reload_counter[1] += 1
1104
idx._indices[:] = new_indices
1106
idx = index.CombinedGraphIndex([idx1, idx2], reload_func=reload)
1107
trans = self.get_transport()
1108
for fname in missing:
1110
return idx, reload_counter
1112
def test_open_missing_index_no_error(self):
1113
trans = self.get_transport()
1114
idx1 = index.GraphIndex(trans, 'missing', 100)
1115
idx = index.CombinedGraphIndex([idx1])
1117
def test_add_index(self):
1118
idx = index.CombinedGraphIndex([])
1119
idx1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1120
idx.insert_index(0, idx1)
1121
self.assertEqual([(idx1, ('key', ), '')],
1122
list(idx.iter_all_entries()))
1124
def test_clear_cache(self):
1127
class ClearCacheProxy(object):
1129
def __init__(self, index):
1132
def __getattr__(self, name):
1133
return getattr(self._index)
1135
def clear_cache(self):
1136
log.append(self._index)
1137
return self._index.clear_cache()
1139
idx = index.CombinedGraphIndex([])
1140
idx1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1141
idx.insert_index(0, ClearCacheProxy(idx1))
1142
idx2 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1143
idx.insert_index(1, ClearCacheProxy(idx2))
1144
# CombinedGraphIndex should call 'clear_cache()' on all children
1146
self.assertEqual(sorted([idx1, idx2]), sorted(log))
1148
def test_iter_all_entries_empty(self):
1149
idx = index.CombinedGraphIndex([])
1150
self.assertEqual([], list(idx.iter_all_entries()))
1152
def test_iter_all_entries_children_empty(self):
1153
idx1 = self.make_index('name')
1154
idx = index.CombinedGraphIndex([idx1])
1155
self.assertEqual([], list(idx.iter_all_entries()))
1157
def test_iter_all_entries_simple(self):
1158
idx1 = self.make_index('name', nodes=[(('name', ), 'data', ())])
1159
idx = index.CombinedGraphIndex([idx1])
1160
self.assertEqual([(idx1, ('name', ), 'data')],
1161
list(idx.iter_all_entries()))
1163
def test_iter_all_entries_two_indices(self):
1164
idx1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1165
idx2 = self.make_index('name2', nodes=[(('2', ), '', ())])
1166
idx = index.CombinedGraphIndex([idx1, idx2])
1167
self.assertEqual([(idx1, ('name', ), 'data'),
1168
(idx2, ('2', ), '')],
1169
list(idx.iter_all_entries()))
1171
def test_iter_entries_two_indices_dup_key(self):
1172
idx1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1173
idx2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
1174
idx = index.CombinedGraphIndex([idx1, idx2])
1175
self.assertEqual([(idx1, ('name', ), 'data')],
1176
list(idx.iter_entries([('name', )])))
1178
def test_iter_all_entries_two_indices_dup_key(self):
1179
idx1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1180
idx2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
1181
idx = index.CombinedGraphIndex([idx1, idx2])
1182
self.assertEqual([(idx1, ('name', ), 'data')],
1183
list(idx.iter_all_entries()))
1185
def test_iter_key_prefix_2_key_element_refs(self):
1186
idx1 = self.make_index('1', 1, key_elements=2, nodes=[
1187
(('name', 'fin1'), 'data', ([('ref', 'erence')], ))])
1188
idx2 = self.make_index('2', 1, key_elements=2, nodes=[
1189
(('name', 'fin2'), 'beta', ([], )),
1190
(('ref', 'erence'), 'refdata', ([], ))])
1191
idx = index.CombinedGraphIndex([idx1, idx2])
1192
self.assertEqual({(idx1, ('name', 'fin1'), 'data',
1193
((('ref', 'erence'),),)),
1194
(idx2, ('ref', 'erence'), 'refdata', ((), ))},
1195
set(idx.iter_entries_prefix([('name', 'fin1'),
1196
('ref', 'erence')])))
1197
self.assertEqual({(idx1, ('name', 'fin1'), 'data',
1198
((('ref', 'erence'),),)),
1199
(idx2, ('name', 'fin2'), 'beta', ((), ))},
1200
set(idx.iter_entries_prefix([('name', None)])))
1202
def test_iter_nothing_empty(self):
1203
idx = index.CombinedGraphIndex([])
1204
self.assertEqual([], list(idx.iter_entries([])))
1206
def test_iter_nothing_children_empty(self):
1207
idx1 = self.make_index('name')
1208
idx = index.CombinedGraphIndex([idx1])
1209
self.assertEqual([], list(idx.iter_entries([])))
1211
def test_iter_all_keys(self):
1212
idx1 = self.make_index('1', 1, nodes=[(('name', ), 'data',
1214
idx2 = self.make_index('2', 1, nodes=[(('ref', ), 'refdata', ((), ))])
1215
idx = index.CombinedGraphIndex([idx1, idx2])
1216
self.assertEqual({(idx1, ('name', ), 'data', ((('ref', ), ), )),
1217
(idx2, ('ref', ), 'refdata', ((), ))},
1218
set(idx.iter_entries([('name', ), ('ref', )])))
1220
def test_iter_all_keys_dup_entry(self):
1221
idx1 = self.make_index('1', 1, nodes=[(('name', ), 'data',
1223
(('ref', ), 'refdata', ([], ))])
1224
idx2 = self.make_index('2', 1, nodes=[(('ref', ), 'refdata', ([], ))])
1225
idx = index.CombinedGraphIndex([idx1, idx2])
1226
self.assertEqual({(idx1, ('name', ), 'data', ((('ref',),),)),
1227
(idx1, ('ref', ), 'refdata', ((), ))},
1228
set(idx.iter_entries([('name', ), ('ref', )])))
1230
def test_iter_missing_entry_empty(self):
1231
idx = index.CombinedGraphIndex([])
1232
self.assertEqual([], list(idx.iter_entries([('a', )])))
1234
def test_iter_missing_entry_one_index(self):
1235
idx1 = self.make_index('1')
1236
idx = index.CombinedGraphIndex([idx1])
1237
self.assertEqual([], list(idx.iter_entries([('a', )])))
1239
def test_iter_missing_entry_two_index(self):
1240
idx1 = self.make_index('1')
1241
idx2 = self.make_index('2')
1242
idx = index.CombinedGraphIndex([idx1, idx2])
1243
self.assertEqual([], list(idx.iter_entries([('a', )])))
1245
def test_iter_entry_present_one_index_only(self):
1246
idx1 = self.make_index('1', nodes=[(('key', ), '', ())])
1247
idx2 = self.make_index('2', nodes=[])
1248
idx = index.CombinedGraphIndex([idx1, idx2])
1249
self.assertEqual([(idx1, ('key', ), '')],
1250
list(idx.iter_entries([('key', )])))
1251
# and in the other direction
1252
idx = index.CombinedGraphIndex([idx2, idx1])
1253
self.assertEqual([(idx1, ('key', ), '')],
1254
list(idx.iter_entries([('key', )])))
1256
def test_key_count_empty(self):
1257
idx1 = self.make_index('1', nodes=[])
1258
idx2 = self.make_index('2', nodes=[])
1259
idx = index.CombinedGraphIndex([idx1, idx2])
1260
self.assertEqual(0, idx.key_count())
1262
def test_key_count_sums_index_keys(self):
1263
idx1 = self.make_index('1', nodes=[
1266
idx2 = self.make_index('2', nodes=[(('1',), '', ())])
1267
idx = index.CombinedGraphIndex([idx1, idx2])
1268
self.assertEqual(3, idx.key_count())
1270
def test_validate_bad_child_index_errors(self):
1271
trans = self.get_transport()
1272
trans.put_bytes('name', "not an index\n")
1273
idx1 = index.GraphIndex(trans, 'name', 13)
1274
idx = index.CombinedGraphIndex([idx1])
1275
self.assertRaises(errors.BadIndexFormatSignature, idx.validate)
1277
def test_validate_empty(self):
1278
idx = index.CombinedGraphIndex([])
1281
def test_key_count_reloads(self):
1282
idx, reload_counter = self.make_combined_index_with_missing()
1283
self.assertEqual(2, idx.key_count())
1284
self.assertEqual([1, 1, 0], reload_counter)
1286
def test_key_count_no_reload(self):
1287
idx, reload_counter = self.make_combined_index_with_missing()
1288
idx._reload_func = None
1289
# Without a _reload_func we just raise the exception
1290
self.assertRaises(errors.NoSuchFile, idx.key_count)
1292
def test_key_count_reloads_and_fails(self):
1293
# We have deleted all underlying indexes, so we will try to reload, but
1294
# still fail. This is mostly to test we don't get stuck in an infinite
1295
# loop trying to reload
1296
idx, reload_counter = self.make_combined_index_with_missing(
1298
self.assertRaises(errors.NoSuchFile, idx.key_count)
1299
self.assertEqual([2, 1, 1], reload_counter)
1301
def test_iter_entries_reloads(self):
1302
index, reload_counter = self.make_combined_index_with_missing()
1303
result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1304
index3 = index._indices[0]
1305
self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
1307
self.assertEqual([1, 1, 0], reload_counter)
1309
def test_iter_entries_reloads_midway(self):
1310
# The first index still looks present, so we get interrupted mid-way
1312
index, reload_counter = self.make_combined_index_with_missing(['2'])
1313
index1, index2 = index._indices
1314
result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1315
index3 = index._indices[0]
1316
# We had already yielded '1', so we just go on to the next, we should
1317
# not yield '1' twice.
1318
self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1320
self.assertEqual([1, 1, 0], reload_counter)
1322
def test_iter_entries_no_reload(self):
1323
index, reload_counter = self.make_combined_index_with_missing()
1324
index._reload_func = None
1325
# Without a _reload_func we just raise the exception
1326
self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1328
def test_iter_entries_reloads_and_fails(self):
1329
index, reload_counter = self.make_combined_index_with_missing(
1331
self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1332
self.assertEqual([2, 1, 1], reload_counter)
1334
def test_iter_all_entries_reloads(self):
1335
index, reload_counter = self.make_combined_index_with_missing()
1336
result = list(index.iter_all_entries())
1337
index3 = index._indices[0]
1338
self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
1340
self.assertEqual([1, 1, 0], reload_counter)
1342
def test_iter_all_entries_reloads_midway(self):
1343
index, reload_counter = self.make_combined_index_with_missing(['2'])
1344
index1, index2 = index._indices
1345
result = list(index.iter_all_entries())
1346
index3 = index._indices[0]
1347
# We had already yielded '1', so we just go on to the next, we should
1348
# not yield '1' twice.
1349
self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1351
self.assertEqual([1, 1, 0], reload_counter)
1353
def test_iter_all_entries_no_reload(self):
1354
index, reload_counter = self.make_combined_index_with_missing()
1355
index._reload_func = None
1356
self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1358
def test_iter_all_entries_reloads_and_fails(self):
1359
index, reload_counter = self.make_combined_index_with_missing(
1361
self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1363
def test_iter_entries_prefix_reloads(self):
1364
index, reload_counter = self.make_combined_index_with_missing()
1365
result = list(index.iter_entries_prefix([('1',)]))
1366
index3 = index._indices[0]
1367
self.assertEqual([(index3, ('1',), '')], result)
1368
self.assertEqual([1, 1, 0], reload_counter)
1370
def test_iter_entries_prefix_reloads_midway(self):
1371
index, reload_counter = self.make_combined_index_with_missing(['2'])
1372
index1, index2 = index._indices
1373
result = list(index.iter_entries_prefix([('1',)]))
1374
index3 = index._indices[0]
1375
# We had already yielded '1', so we just go on to the next, we should
1376
# not yield '1' twice.
1377
self.assertEqual([(index1, ('1',), '')], result)
1378
self.assertEqual([1, 1, 0], reload_counter)
1380
def test_iter_entries_prefix_no_reload(self):
1381
index, reload_counter = self.make_combined_index_with_missing()
1382
index._reload_func = None
1383
self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1386
def test_iter_entries_prefix_reloads_and_fails(self):
1387
index, reload_counter = self.make_combined_index_with_missing(
1389
self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1393
def make_index_with_simple_nodes(self, name, num_nodes=1):
1394
"""Make an index named after 'name', with keys named after 'name' too.
1396
Nodes will have a value of '' and no references.
1399
(('index-%s-key-%s' % (name, n),), '', ())
1400
for n in range(1, num_nodes+1)]
1401
return self.make_index('index-%s' % name, 0, nodes=nodes)
1403
def test_reorder_after_iter_entries(self):
1404
# Four indices: [key1] in idx1, [key2,key3] in idx2, [] in idx3,
1406
idx = index.CombinedGraphIndex([])
1407
idx.insert_index(0, self.make_index_with_simple_nodes('1'), '1')
1408
idx.insert_index(1, self.make_index_with_simple_nodes('2'), '2')
1409
idx.insert_index(2, self.make_index_with_simple_nodes('3'), '3')
1410
idx.insert_index(3, self.make_index_with_simple_nodes('4'), '4')
1411
idx1, idx2, idx3, idx4 = idx._indices
1412
# Query a key from idx4 and idx2.
1413
self.assertLength(2, list(idx.iter_entries(
1414
[('index-4-key-1',), ('index-2-key-1',)])))
1415
# Now idx2 and idx4 should be moved to the front (and idx1 should
1416
# still be before idx3).
1417
self.assertEqual([idx2, idx4, idx1, idx3], idx._indices)
1418
self.assertEqual(['2', '4', '1', '3'], idx._index_names)
1420
def test_reorder_propagates_to_siblings(self):
1421
# Two CombinedGraphIndex objects, with the same number of indicies with
1423
cgi1 = index.CombinedGraphIndex([])
1424
cgi2 = index.CombinedGraphIndex([])
1425
cgi1.insert_index(0, self.make_index_with_simple_nodes('1-1'), 'one')
1426
cgi1.insert_index(1, self.make_index_with_simple_nodes('1-2'), 'two')
1427
cgi2.insert_index(0, self.make_index_with_simple_nodes('2-1'), 'one')
1428
cgi2.insert_index(1, self.make_index_with_simple_nodes('2-2'), 'two')
1429
index2_1, index2_2 = cgi2._indices
1430
cgi1.set_sibling_indices([cgi2])
1431
# Trigger a reordering in cgi1. cgi2 will be reordered as well.
1432
list(cgi1.iter_entries([('index-1-2-key-1',)]))
1433
self.assertEqual([index2_2, index2_1], cgi2._indices)
1434
self.assertEqual(['two', 'one'], cgi2._index_names)
1436
def test_validate_reloads(self):
1437
idx, reload_counter = self.make_combined_index_with_missing()
1439
self.assertEqual([1, 1, 0], reload_counter)
1441
def test_validate_reloads_midway(self):
1442
idx, reload_counter = self.make_combined_index_with_missing(['2'])
1445
def test_validate_no_reload(self):
1446
idx, reload_counter = self.make_combined_index_with_missing()
1447
idx._reload_func = None
1448
self.assertRaises(errors.NoSuchFile, idx.validate)
1450
def test_validate_reloads_and_fails(self):
1451
idx, reload_counter = self.make_combined_index_with_missing(
1453
self.assertRaises(errors.NoSuchFile, idx.validate)
1455
def test_find_ancestors_across_indexes(self):
1460
index1 = self.make_index('12', ref_lists=1, nodes=[
1461
(key1, 'value', ([],)),
1462
(key2, 'value', ([key1],)),
1464
index2 = self.make_index('34', ref_lists=1, nodes=[
1465
(key3, 'value', ([key2],)),
1466
(key4, 'value', ([key3],)),
1468
c_index = index.CombinedGraphIndex([index1, index2])
1469
parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1470
self.assertEqual({key1: ()}, parent_map)
1471
self.assertEqual(set(), missing_keys)
1472
# Now look for a key from index2 which requires us to find the key in
1473
# the second index, and then continue searching for parents in the
1475
parent_map, missing_keys = c_index.find_ancestry([key3], 0)
1476
self.assertEqual({key1: (), key2: (key1,), key3: (key2,)}, parent_map)
1477
self.assertEqual(set(), missing_keys)
1479
def test_find_ancestors_missing_keys(self):
1484
index1 = self.make_index('12', ref_lists=1, nodes=[
1485
(key1, 'value', ([],)),
1486
(key2, 'value', ([key1],)),
1488
index2 = self.make_index('34', ref_lists=1, nodes=[
1489
(key3, 'value', ([key2],)),
1491
c_index = index.CombinedGraphIndex([index1, index2])
1492
# Searching for a key which is actually not present at all should
1493
# eventually converge
1494
parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1495
self.assertEqual({}, parent_map)
1496
self.assertEqual({key4}, missing_keys)
1498
def test_find_ancestors_no_indexes(self):
1499
c_index = index.CombinedGraphIndex([])
1501
parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1502
self.assertEqual({}, parent_map)
1503
self.assertEqual({key1}, missing_keys)
1505
def test_find_ancestors_ghost_parent(self):
1510
index1 = self.make_index('12', ref_lists=1, nodes=[
1511
(key1, 'value', ([],)),
1512
(key2, 'value', ([key1],)),
1514
index2 = self.make_index('34', ref_lists=1, nodes=[
1515
(key4, 'value', ([key2, key3],)),
1517
c_index = index.CombinedGraphIndex([index1, index2])
1518
# Searching for a key which is actually not present at all should
1519
# eventually converge
1520
parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1521
self.assertEqual({key4: (key2, key3), key2: (key1,), key1: ()},
1523
self.assertEqual({key3}, missing_keys)
1525
def test__find_ancestors_empty_index(self):
1526
idx = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
1528
missing_keys = set()
1529
search_keys = idx._find_ancestors([('one',), ('two',)], 0, parent_map,
1531
self.assertEqual(set(), search_keys)
1532
self.assertEqual({}, parent_map)
1533
self.assertEqual({('one',), ('two',)}, missing_keys)
1536
class TestInMemoryGraphIndex(tests.TestCaseWithMemoryTransport):
1538
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
1539
result = index.InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1540
result.add_nodes(nodes)
1543
def test_add_nodes_no_refs(self):
1544
index = self.make_index(0)
1545
index.add_nodes([(('name', ), 'data')])
1546
index.add_nodes([(('name2', ), ''), (('name3', ), '')])
1548
(index, ('name', ), 'data'),
1549
(index, ('name2', ), ''),
1550
(index, ('name3', ), ''),
1551
}, set(index.iter_all_entries()))
1553
def test_add_nodes(self):
1554
index = self.make_index(1)
1555
index.add_nodes([(('name', ), 'data', ([],))])
1556
index.add_nodes([(('name2', ), '', ([],)), (('name3', ), '', ([('r', )],))])
1558
(index, ('name', ), 'data', ((),)),
1559
(index, ('name2', ), '', ((),)),
1560
(index, ('name3', ), '', ((('r', ), ), )),
1561
}, set(index.iter_all_entries()))
1563
def test_iter_all_entries_empty(self):
1564
index = self.make_index()
1565
self.assertEqual([], list(index.iter_all_entries()))
1567
def test_iter_all_entries_simple(self):
1568
index = self.make_index(nodes=[(('name', ), 'data')])
1569
self.assertEqual([(index, ('name', ), 'data')],
1570
list(index.iter_all_entries()))
1572
def test_iter_all_entries_references(self):
1573
index = self.make_index(1, nodes=[
1574
(('name', ), 'data', ([('ref', )], )),
1575
(('ref', ), 'refdata', ([], ))])
1576
self.assertEqual({(index, ('name', ), 'data', ((('ref', ),),)),
1577
(index, ('ref', ), 'refdata', ((), ))},
1578
set(index.iter_all_entries()))
1580
def test_iteration_absent_skipped(self):
1581
index = self.make_index(1, nodes=[
1582
(('name', ), 'data', ([('ref', )], ))])
1583
self.assertEqual({(index, ('name', ), 'data', ((('ref',),),))},
1584
set(index.iter_all_entries()))
1585
self.assertEqual({(index, ('name', ), 'data', ((('ref',),),))},
1586
set(index.iter_entries([('name', )])))
1587
self.assertEqual([], list(index.iter_entries([('ref', )])))
1589
def test_iter_all_keys(self):
1590
index = self.make_index(1, nodes=[
1591
(('name', ), 'data', ([('ref', )], )),
1592
(('ref', ), 'refdata', ([], ))])
1593
self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
1594
(index, ('ref', ), 'refdata', ((), ))},
1595
set(index.iter_entries([('name', ), ('ref', )])))
1597
def test_iter_key_prefix_1_key_element_no_refs(self):
1598
index = self.make_index( nodes=[
1599
(('name', ), 'data'),
1600
(('ref', ), 'refdata')])
1601
self.assertEqual({(index, ('name', ), 'data'),
1602
(index, ('ref', ), 'refdata')},
1603
set(index.iter_entries_prefix([('name', ), ('ref', )])))
1605
def test_iter_key_prefix_1_key_element_refs(self):
1606
index = self.make_index(1, nodes=[
1607
(('name', ), 'data', ([('ref', )], )),
1608
(('ref', ), 'refdata', ([], ))])
1609
self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
1610
(index, ('ref', ), 'refdata', ((), ))},
1611
set(index.iter_entries_prefix([('name', ), ('ref', )])))
1613
def test_iter_key_prefix_2_key_element_no_refs(self):
1614
index = self.make_index(key_elements=2, nodes=[
1615
(('name', 'fin1'), 'data'),
1616
(('name', 'fin2'), 'beta'),
1617
(('ref', 'erence'), 'refdata')])
1618
self.assertEqual({(index, ('name', 'fin1'), 'data'),
1619
(index, ('ref', 'erence'), 'refdata')},
1620
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
1621
self.assertEqual({(index, ('name', 'fin1'), 'data'),
1622
(index, ('name', 'fin2'), 'beta')},
1623
set(index.iter_entries_prefix([('name', None)])))
1625
def test_iter_key_prefix_2_key_element_refs(self):
1626
index = self.make_index(1, key_elements=2, nodes=[
1627
(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
1628
(('name', 'fin2'), 'beta', ([], )),
1629
(('ref', 'erence'), 'refdata', ([], ))])
1630
self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1631
(index, ('ref', 'erence'), 'refdata', ((), ))},
1632
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
1633
self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1634
(index, ('name', 'fin2'), 'beta', ((), ))},
1635
set(index.iter_entries_prefix([('name', None)])))
1637
def test_iter_nothing_empty(self):
1638
index = self.make_index()
1639
self.assertEqual([], list(index.iter_entries([])))
1641
def test_iter_missing_entry_empty(self):
1642
index = self.make_index()
1643
self.assertEqual([], list(index.iter_entries(['a'])))
1645
def test_key_count_empty(self):
1646
index = self.make_index()
1647
self.assertEqual(0, index.key_count())
1649
def test_key_count_one(self):
1650
index = self.make_index(nodes=[(('name', ), '')])
1651
self.assertEqual(1, index.key_count())
1653
def test_key_count_two(self):
1654
index = self.make_index(nodes=[(('name', ), ''), (('foo', ), '')])
1655
self.assertEqual(2, index.key_count())
1657
def test_validate_empty(self):
1658
index = self.make_index()
1661
def test_validate_no_refs_content(self):
1662
index = self.make_index(nodes=[(('key', ), 'value')])
1666
class TestGraphIndexPrefixAdapter(tests.TestCaseWithMemoryTransport):
1668
def make_index(self, ref_lists=1, key_elements=2, nodes=[],
1669
add_callback=False):
1670
result = index.InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1671
result.add_nodes(nodes)
1673
add_nodes_callback = result.add_nodes
1675
add_nodes_callback = None
1676
adapter = index.GraphIndexPrefixAdapter(
1677
result, ('prefix', ), key_elements - 1,
1678
add_nodes_callback=add_nodes_callback)
1679
return result, adapter
1681
def test_add_node(self):
1682
index, adapter = self.make_index(add_callback=True)
1683
adapter.add_node(('key',), 'value', ((('ref',),),))
1684
self.assertEqual({(index, ('prefix', 'key'), 'value',
1685
((('prefix', 'ref'),),))},
1686
set(index.iter_all_entries()))
1688
def test_add_nodes(self):
1689
index, adapter = self.make_index(add_callback=True)
1691
(('key',), 'value', ((('ref',),),)),
1692
(('key2',), 'value2', ((),)),
1695
(index, ('prefix', 'key2'), 'value2', ((),)),
1696
(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))
1698
set(index.iter_all_entries()))
1700
def test_construct(self):
1701
idx = index.InMemoryGraphIndex()
1702
adapter = index.GraphIndexPrefixAdapter(idx, ('prefix', ), 1)
1704
def test_construct_with_callback(self):
1705
idx = index.InMemoryGraphIndex()
1706
adapter = index.GraphIndexPrefixAdapter(idx, ('prefix', ), 1,
1709
def test_iter_all_entries_cross_prefix_map_errors(self):
1710
index, adapter = self.make_index(nodes=[
1711
(('prefix', 'key1'), 'data1', ((('prefixaltered', 'key2'),),))])
1712
self.assertRaises(errors.BadIndexData, list, adapter.iter_all_entries())
1714
def test_iter_all_entries(self):
1715
index, adapter = self.make_index(nodes=[
1716
(('notprefix', 'key1'), 'data', ((), )),
1717
(('prefix', 'key1'), 'data1', ((), )),
1718
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1719
self.assertEqual({(index, ('key1', ), 'data1', ((),)),
1720
(index, ('key2', ), 'data2', ((('key1',),),))},
1721
set(adapter.iter_all_entries()))
1723
def test_iter_entries(self):
1724
index, adapter = self.make_index(nodes=[
1725
(('notprefix', 'key1'), 'data', ((), )),
1726
(('prefix', 'key1'), 'data1', ((), )),
1727
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1728
# ask for many - get all
1729
self.assertEqual({(index, ('key1', ), 'data1', ((),)),
1730
(index, ('key2', ), 'data2', ((('key1', ),),))},
1731
set(adapter.iter_entries([('key1', ), ('key2', )])))
1732
# ask for one, get one
1733
self.assertEqual({(index, ('key1', ), 'data1', ((),))},
1734
set(adapter.iter_entries([('key1', )])))
1735
# ask for missing, get none
1736
self.assertEqual(set(),
1737
set(adapter.iter_entries([('key3', )])))
1739
def test_iter_entries_prefix(self):
1740
index, adapter = self.make_index(key_elements=3, nodes=[
1741
(('notprefix', 'foo', 'key1'), 'data', ((), )),
1742
(('prefix', 'prefix2', 'key1'), 'data1', ((), )),
1743
(('prefix', 'prefix2', 'key2'), 'data2', ((('prefix', 'prefix2', 'key1'),),))])
1744
# ask for a prefix, get the results for just that prefix, adjusted.
1745
self.assertEqual({(index, ('prefix2', 'key1', ), 'data1', ((),)),
1746
(index, ('prefix2', 'key2', ), 'data2', ((('prefix2', 'key1', ),),))},
1747
set(adapter.iter_entries_prefix([('prefix2', None)])))
1749
def test_key_count_no_matching_keys(self):
1750
index, adapter = self.make_index(nodes=[
1751
(('notprefix', 'key1'), 'data', ((), ))])
1752
self.assertEqual(0, adapter.key_count())
1754
def test_key_count_some_keys(self):
1755
index, adapter = self.make_index(nodes=[
1756
(('notprefix', 'key1'), 'data', ((), )),
1757
(('prefix', 'key1'), 'data1', ((), )),
1758
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1759
self.assertEqual(2, adapter.key_count())
1761
def test_validate(self):
1762
index, adapter = self.make_index()
1765
calls.append('called')
1766
index.validate = validate
1768
self.assertEqual(['called'], calls)
added
removed
breezy/tests/test_index.py
