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."""
24
from ..sixish import int2byte
30
class ErrorTests(tests.TestCase):
32
def test_bad_index_format_signature(self):
33
error = _mod_index.BadIndexFormatSignature("foo", "bar")
34
self.assertEqual("foo is not an index of type bar.",
37
def test_bad_index_data(self):
38
error = _mod_index.BadIndexData("foo")
39
self.assertEqual("Error in data for index foo.",
42
def test_bad_index_duplicate_key(self):
43
error = _mod_index.BadIndexDuplicateKey("foo", "bar")
44
self.assertEqual("The key 'foo' is already in index 'bar'.",
47
def test_bad_index_key(self):
48
error = _mod_index.BadIndexKey("foo")
49
self.assertEqual("The key 'foo' is not a valid key.",
52
def test_bad_index_options(self):
53
error = _mod_index.BadIndexOptions("foo")
54
self.assertEqual("Could not parse options for index foo.",
57
def test_bad_index_value(self):
58
error = _mod_index.BadIndexValue("foo")
59
self.assertEqual("The value 'foo' is not a valid value.",
63
class TestGraphIndexBuilder(tests.TestCaseWithMemoryTransport):
65
def test_build_index_empty(self):
66
builder = _mod_index.GraphIndexBuilder()
67
stream = builder.finish()
68
contents = stream.read()
70
b"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=0\n\n",
73
def test_build_index_empty_two_element_keys(self):
74
builder = _mod_index.GraphIndexBuilder(key_elements=2)
75
stream = builder.finish()
76
contents = stream.read()
78
b"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=0\n\n",
81
def test_build_index_one_reference_list_empty(self):
82
builder = _mod_index.GraphIndexBuilder(reference_lists=1)
83
stream = builder.finish()
84
contents = stream.read()
86
b"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=0\n\n",
89
def test_build_index_two_reference_list_empty(self):
90
builder = _mod_index.GraphIndexBuilder(reference_lists=2)
91
stream = builder.finish()
92
contents = stream.read()
94
b"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=0\n\n",
97
def test_build_index_one_node_no_refs(self):
98
builder = _mod_index.GraphIndexBuilder()
99
builder.add_node((b'akey', ), b'data')
100
stream = builder.finish()
101
contents = stream.read()
103
b"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
104
b"akey\x00\x00\x00data\n\n", contents)
106
def test_build_index_one_node_no_refs_accepts_empty_reflist(self):
107
builder = _mod_index.GraphIndexBuilder()
108
builder.add_node((b'akey', ), b'data', ())
109
stream = builder.finish()
110
contents = stream.read()
112
b"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
113
b"akey\x00\x00\x00data\n\n", contents)
115
def test_build_index_one_node_2_element_keys(self):
116
# multipart keys are separated by \x00 - because they are fixed length,
117
# not variable this does not cause any issues, and seems clearer to the
119
builder = _mod_index.GraphIndexBuilder(key_elements=2)
120
builder.add_node((b'akey', b'secondpart'), b'data')
121
stream = builder.finish()
122
contents = stream.read()
124
b"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=1\n"
125
b"akey\x00secondpart\x00\x00\x00data\n\n", contents)
127
def test_add_node_empty_value(self):
128
builder = _mod_index.GraphIndexBuilder()
129
builder.add_node((b'akey', ), b'')
130
stream = builder.finish()
131
contents = stream.read()
133
b"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
134
b"akey\x00\x00\x00\n\n", contents)
136
def test_build_index_nodes_sorted(self):
137
# the highest sorted node comes first.
138
builder = _mod_index.GraphIndexBuilder()
139
# use three to have a good chance of glitching dictionary hash
140
# lookups etc. Insert in randomish order that is not correct
141
# and not the reverse of the correct order.
142
builder.add_node((b'2002', ), b'data')
143
builder.add_node((b'2000', ), b'data')
144
builder.add_node((b'2001', ), b'data')
145
stream = builder.finish()
146
contents = stream.read()
148
b"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=3\n"
149
b"2000\x00\x00\x00data\n"
150
b"2001\x00\x00\x00data\n"
151
b"2002\x00\x00\x00data\n"
154
def test_build_index_2_element_key_nodes_sorted(self):
155
# multiple element keys are sorted first-key, second-key.
156
builder = _mod_index.GraphIndexBuilder(key_elements=2)
157
# use three values of each key element, to have a good chance of
158
# glitching dictionary hash lookups etc. Insert in randomish order that
159
# is not correct and not the reverse of the correct order.
160
builder.add_node((b'2002', b'2002'), b'data')
161
builder.add_node((b'2002', b'2000'), b'data')
162
builder.add_node((b'2002', b'2001'), b'data')
163
builder.add_node((b'2000', b'2002'), b'data')
164
builder.add_node((b'2000', b'2000'), b'data')
165
builder.add_node((b'2000', b'2001'), b'data')
166
builder.add_node((b'2001', b'2002'), b'data')
167
builder.add_node((b'2001', b'2000'), b'data')
168
builder.add_node((b'2001', b'2001'), b'data')
169
stream = builder.finish()
170
contents = stream.read()
172
b"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=9\n"
173
b"2000\x002000\x00\x00\x00data\n"
174
b"2000\x002001\x00\x00\x00data\n"
175
b"2000\x002002\x00\x00\x00data\n"
176
b"2001\x002000\x00\x00\x00data\n"
177
b"2001\x002001\x00\x00\x00data\n"
178
b"2001\x002002\x00\x00\x00data\n"
179
b"2002\x002000\x00\x00\x00data\n"
180
b"2002\x002001\x00\x00\x00data\n"
181
b"2002\x002002\x00\x00\x00data\n"
184
def test_build_index_reference_lists_are_included_one(self):
185
builder = _mod_index.GraphIndexBuilder(reference_lists=1)
186
builder.add_node((b'key', ), b'data', ([], ))
187
stream = builder.finish()
188
contents = stream.read()
190
b"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
191
b"key\x00\x00\x00data\n"
194
def test_build_index_reference_lists_with_2_element_keys(self):
195
builder = _mod_index.GraphIndexBuilder(reference_lists=1, key_elements=2)
196
builder.add_node((b'key', b'key2'), b'data', ([], ))
197
stream = builder.finish()
198
contents = stream.read()
200
b"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=2\nlen=1\n"
201
b"key\x00key2\x00\x00\x00data\n"
204
def test_build_index_reference_lists_are_included_two(self):
205
builder = _mod_index.GraphIndexBuilder(reference_lists=2)
206
builder.add_node((b'key', ), b'data', ([], []))
207
stream = builder.finish()
208
contents = stream.read()
210
b"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
211
b"key\x00\x00\t\x00data\n"
214
def test_clear_cache(self):
215
builder = _mod_index.GraphIndexBuilder(reference_lists=2)
216
# This is a no-op, but the api should exist
217
builder.clear_cache()
219
def test_node_references_are_byte_offsets(self):
220
builder = _mod_index.GraphIndexBuilder(reference_lists=1)
221
builder.add_node((b'reference', ), b'data', ([], ))
222
builder.add_node((b'key', ), b'data', ([(b'reference', )], ))
223
stream = builder.finish()
224
contents = stream.read()
226
b"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=2\n"
227
b"key\x00\x0072\x00data\n"
228
b"reference\x00\x00\x00data\n"
231
def test_node_references_are_cr_delimited(self):
232
builder = _mod_index.GraphIndexBuilder(reference_lists=1)
233
builder.add_node((b'reference', ), b'data', ([], ))
234
builder.add_node((b'reference2', ), b'data', ([], ))
235
builder.add_node((b'key', ), b'data',
236
([(b'reference', ), (b'reference2', )], ))
237
stream = builder.finish()
238
contents = stream.read()
240
b"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=3\n"
241
b"key\x00\x00077\r094\x00data\n"
242
b"reference\x00\x00\x00data\n"
243
b"reference2\x00\x00\x00data\n"
246
def test_multiple_reference_lists_are_tab_delimited(self):
247
builder = _mod_index.GraphIndexBuilder(reference_lists=2)
248
builder.add_node((b'keference', ), b'data', ([], []))
249
builder.add_node((b'rey', ), b'data',
250
([(b'keference', )], [(b'keference', )]))
251
stream = builder.finish()
252
contents = stream.read()
254
b"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=2\n"
255
b"keference\x00\x00\t\x00data\n"
256
b"rey\x00\x0059\t59\x00data\n"
259
def test_add_node_referencing_missing_key_makes_absent(self):
260
builder = _mod_index.GraphIndexBuilder(reference_lists=1)
261
builder.add_node((b'rey', ), b'data',
262
([(b'beference', ), (b'aeference2', )], ))
263
stream = builder.finish()
264
contents = stream.read()
266
b"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
267
b"aeference2\x00a\x00\x00\n"
268
b"beference\x00a\x00\x00\n"
269
b"rey\x00\x00074\r059\x00data\n"
272
def test_node_references_three_digits(self):
273
# test the node digit expands as needed.
274
builder = _mod_index.GraphIndexBuilder(reference_lists=1)
275
references = [((b"%d" % val), ) for val in range(8, -1, -1)]
276
builder.add_node((b'2-key', ), b'', (references, ))
277
stream = builder.finish()
278
contents = stream.read()
279
self.assertEqualDiff(
280
b"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
284
b"2-key\x00\x00151\r145\r139\r133\r127\r121\r071\r065\r059\x00\n"
293
def test_absent_has_no_reference_overhead(self):
294
# the offsets after an absent record should be correct when there are
295
# >1 reference lists.
296
builder = _mod_index.GraphIndexBuilder(reference_lists=2)
297
builder.add_node((b'parent', ), b'', ([(b'aail', ), (b'zther', )], []))
298
stream = builder.finish()
299
contents = stream.read()
301
b"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
302
b"aail\x00a\x00\x00\n"
303
b"parent\x00\x0059\r84\t\x00\n"
304
b"zther\x00a\x00\x00\n"
307
def test_add_node_bad_key(self):
308
builder = _mod_index.GraphIndexBuilder()
309
for bad_char in bytearray(b'\t\n\x0b\x0c\r\x00 '):
310
self.assertRaises(_mod_index.BadIndexKey, builder.add_node,
311
(b'a%skey' % int2byte(bad_char), ), b'data')
312
self.assertRaises(_mod_index.BadIndexKey, builder.add_node,
314
self.assertRaises(_mod_index.BadIndexKey, builder.add_node,
315
b'not-a-tuple', b'data')
317
self.assertRaises(_mod_index.BadIndexKey, builder.add_node,
320
self.assertRaises(_mod_index.BadIndexKey, builder.add_node,
321
(b'primary', b'secondary'), b'data')
322
# secondary key elements get checked too:
323
builder = _mod_index.GraphIndexBuilder(key_elements=2)
324
for bad_char in bytearray(b'\t\n\x0b\x0c\r\x00 '):
325
self.assertRaises(_mod_index.BadIndexKey, builder.add_node,
326
(b'prefix', b'a%skey' % int2byte(bad_char)), b'data')
328
def test_add_node_bad_data(self):
329
builder = _mod_index.GraphIndexBuilder()
330
self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
332
self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
335
def test_add_node_bad_mismatched_ref_lists_length(self):
336
builder = _mod_index.GraphIndexBuilder()
337
self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
339
builder = _mod_index.GraphIndexBuilder(reference_lists=1)
340
self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
342
self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
344
self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
345
b'data aa', ([], []))
346
builder = _mod_index.GraphIndexBuilder(reference_lists=2)
347
self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
349
self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
351
self.assertRaises(_mod_index.BadIndexValue, builder.add_node, (b'akey', ),
352
b'data aa', ([], [], []))
354
def test_add_node_bad_key_in_reference_lists(self):
355
# first list, first key - trivial
356
builder = _mod_index.GraphIndexBuilder(reference_lists=1)
357
self.assertRaises(_mod_index.BadIndexKey, builder.add_node, (b'akey', ),
358
b'data aa', ([(b'a key', )], ))
359
# references keys must be tuples too
360
self.assertRaises(_mod_index.BadIndexKey, builder.add_node, (b'akey', ),
361
b'data aa', (['not-a-tuple'], ))
363
self.assertRaises(_mod_index.BadIndexKey, builder.add_node, (b'akey', ),
364
b'data aa', ([()], ))
366
self.assertRaises(_mod_index.BadIndexKey, builder.add_node, (b'akey', ),
367
b'data aa', ([(b'primary', b'secondary')], ))
368
# need to check more than the first key in the list
369
self.assertRaises(_mod_index.BadIndexKey, builder.add_node, (b'akey', ),
370
b'data aa', ([(b'agoodkey', ), (b'that is a bad key', )], ))
371
# and if there is more than one list it should be getting checked
373
builder = _mod_index.GraphIndexBuilder(reference_lists=2)
374
self.assertRaises(_mod_index.BadIndexKey, builder.add_node, (b'akey', ),
375
b'data aa', ([], ['a bad key']))
377
def test_add_duplicate_key(self):
378
builder = _mod_index.GraphIndexBuilder()
379
builder.add_node((b'key', ), b'data')
380
self.assertRaises(_mod_index.BadIndexDuplicateKey,
381
builder.add_node, (b'key', ), b'data')
383
def test_add_duplicate_key_2_elements(self):
384
builder = _mod_index.GraphIndexBuilder(key_elements=2)
385
builder.add_node((b'key', b'key'), b'data')
386
self.assertRaises(_mod_index.BadIndexDuplicateKey, builder.add_node,
387
(b'key', b'key'), b'data')
389
def test_add_key_after_referencing_key(self):
390
builder = _mod_index.GraphIndexBuilder(reference_lists=1)
391
builder.add_node((b'key', ), b'data', ([(b'reference', )], ))
392
builder.add_node((b'reference', ), b'data', ([],))
394
def test_add_key_after_referencing_key_2_elements(self):
395
builder = _mod_index.GraphIndexBuilder(reference_lists=1, key_elements=2)
396
builder.add_node((b'k', b'ey'), b'data', ([(b'reference', b'tokey')], ))
397
builder.add_node((b'reference', b'tokey'), b'data', ([],))
399
def test_set_optimize(self):
400
builder = _mod_index.GraphIndexBuilder(reference_lists=1, key_elements=2)
401
builder.set_optimize(for_size=True)
402
self.assertTrue(builder._optimize_for_size)
403
builder.set_optimize(for_size=False)
404
self.assertFalse(builder._optimize_for_size)
407
class TestGraphIndex(tests.TestCaseWithMemoryTransport):
409
def make_key(self, number):
410
return ((b'%d' % number) + b'X'*100,)
412
def make_value(self, number):
413
return (b'%d' % number) + b'Y'*100
415
def make_nodes(self, count=64):
416
# generate a big enough index that we only read some of it on a typical
419
for counter in range(count):
420
nodes.append((self.make_key(counter), self.make_value(counter), ()))
423
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
424
builder = _mod_index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
425
for key, value, references in nodes:
426
builder.add_node(key, value, references)
427
stream = builder.finish()
428
trans = transport.get_transport_from_url('trace+' + self.get_url())
429
size = trans.put_file('index', stream)
430
return _mod_index.GraphIndex(trans, 'index', size)
432
def make_index_with_offset(self, ref_lists=0, key_elements=1, nodes=[],
434
builder = _mod_index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
435
for key, value, references in nodes:
436
builder.add_node(key, value, references)
437
content = builder.finish().read()
439
trans = self.get_transport()
440
trans.put_bytes('index', (b' '*offset) + content)
441
return _mod_index.GraphIndex(trans, 'index', size, offset=offset)
443
def test_clear_cache(self):
444
index = self.make_index()
445
# For now, we just want to make sure the api is available. As this is
446
# old code, we don't really worry if it *does* anything.
449
def test_open_bad_index_no_error(self):
450
trans = self.get_transport()
451
trans.put_bytes('name', b"not an index\n")
452
idx = _mod_index.GraphIndex(trans, 'name', 13)
454
def test_with_offset(self):
455
nodes = self.make_nodes(200)
456
idx = self.make_index_with_offset(offset=1234567, nodes=nodes)
457
self.assertEqual(200, idx.key_count())
459
def test_buffer_all_with_offset(self):
460
nodes = self.make_nodes(200)
461
idx = self.make_index_with_offset(offset=1234567, nodes=nodes)
463
self.assertEqual(200, idx.key_count())
465
def test_side_effect_buffering_with_offset(self):
466
nodes = self.make_nodes(20)
467
index = self.make_index_with_offset(offset=1234567, nodes=nodes)
468
index._transport.recommended_page_size = lambda:64*1024
469
subset_nodes = [nodes[0][0], nodes[10][0], nodes[19][0]]
470
entries = [n[1] for n in index.iter_entries(subset_nodes)]
471
self.assertEqual(sorted(subset_nodes), sorted(entries))
472
self.assertEqual(20, index.key_count())
474
def test_open_sets_parsed_map_empty(self):
475
index = self.make_index()
476
self.assertEqual([], index._parsed_byte_map)
477
self.assertEqual([], index._parsed_key_map)
479
def test_key_count_buffers(self):
480
index = self.make_index(nodes=self.make_nodes(2))
481
# reset the transport log
482
del index._transport._activity[:]
483
self.assertEqual(2, index.key_count())
484
# We should have requested reading the header bytes
486
('readv', 'index', [(0, 200)], True, index._size),
488
index._transport._activity)
489
# And that should have been enough to trigger reading the whole index
491
self.assertIsNot(None, index._nodes)
493
def test_lookup_key_via_location_buffers(self):
494
index = self.make_index()
495
# reset the transport log
496
del index._transport._activity[:]
497
# do a _lookup_keys_via_location call for the middle of the file, which
498
# is what bisection uses.
499
result = index._lookup_keys_via_location(
500
[(index._size // 2, (b'missing', ))])
501
# this should have asked for a readv request, with adjust_for_latency,
502
# and two regions: the header, and half-way into the file.
504
('readv', 'index', [(30, 30), (0, 200)], True, 60),
506
index._transport._activity)
507
# and the result should be that the key cannot be present, because this
508
# is a trivial index.
509
self.assertEqual([((index._size // 2, (b'missing', )), False)],
511
# And this should have caused the file to be fully buffered
512
self.assertIsNot(None, index._nodes)
513
self.assertEqual([], index._parsed_byte_map)
515
def test_first_lookup_key_via_location(self):
516
# We need enough data so that the _HEADER_READV doesn't consume the
517
# whole file. We always read 800 bytes for every key, and the local
518
# transport natural expansion is 4096 bytes. So we have to have >8192
519
# bytes or we will trigger "buffer_all".
520
# We also want the 'missing' key to fall within the range that *did*
523
index = self.make_index(nodes=self.make_nodes(64))
524
# reset the transport log
525
del index._transport._activity[:]
526
# do a _lookup_keys_via_location call for the middle of the file, which
527
# is what bisection uses.
528
start_lookup = index._size // 2
529
result = index._lookup_keys_via_location(
530
[(start_lookup, (b'40missing', ))])
531
# this should have asked for a readv request, with adjust_for_latency,
532
# and two regions: the header, and half-way into the file.
535
[(start_lookup, 800), (0, 200)], True, index._size),
537
index._transport._activity)
538
# and the result should be that the key cannot be present, because this
539
# is a trivial index.
540
self.assertEqual([((start_lookup, (b'40missing', )), False)],
542
# And this should not have caused the file to be fully buffered
543
self.assertIs(None, index._nodes)
544
# And the regions of the file that have been parsed should be in the
545
# parsed_byte_map and the parsed_key_map
546
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
547
self.assertEqual([(None, self.make_key(26)),
548
(self.make_key(31), self.make_key(48))],
549
index._parsed_key_map)
551
def test_parsing_non_adjacent_data_trims(self):
552
index = self.make_index(nodes=self.make_nodes(64))
553
result = index._lookup_keys_via_location(
554
[(index._size // 2, (b'40', ))])
555
# and the result should be that the key cannot be present, because key is
556
# in the middle of the observed data from a 4K read - the smallest transport
557
# will do today with this api.
558
self.assertEqual([((index._size // 2, (b'40', )), False)],
560
# and we should have a parse map that includes the header and the
561
# region that was parsed after trimming.
562
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
563
self.assertEqual([(None, self.make_key(26)),
564
(self.make_key(31), self.make_key(48))],
565
index._parsed_key_map)
567
def test_parsing_data_handles_parsed_contained_regions(self):
568
# the following patten creates a parsed region that is wholly within a
569
# single result from the readv layer:
570
# .... single-read (readv-minimum-size) ...
571
# which then trims the start and end so the parsed size is < readv
573
# then a dual lookup (or a reference lookup for that matter) which
574
# abuts or overlaps the parsed region on both sides will need to
575
# discard the data in the middle, but parse the end as well.
577
# we test this by doing a single lookup to seed the data, then
578
# a lookup for two keys that are present, and adjacent -
579
# we except both to be found, and the parsed byte map to include the
580
# locations of both keys.
581
index = self.make_index(nodes=self.make_nodes(128))
582
result = index._lookup_keys_via_location(
583
[(index._size // 2, (b'40', ))])
584
# and we should have a parse map that includes the header and the
585
# region that was parsed after trimming.
586
self.assertEqual([(0, 4045), (11759, 15707)], index._parsed_byte_map)
587
self.assertEqual([(None, self.make_key(116)),
588
(self.make_key(35), self.make_key(51))],
589
index._parsed_key_map)
590
# now ask for two keys, right before and after the parsed region
591
result = index._lookup_keys_via_location(
592
[(11450, self.make_key(34)), (15707, self.make_key(52))])
594
((11450, self.make_key(34)),
595
(index, self.make_key(34), self.make_value(34))),
596
((15707, self.make_key(52)),
597
(index, self.make_key(52), self.make_value(52))),
600
self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)
602
def test_lookup_missing_key_answers_without_io_when_map_permits(self):
603
# generate a big enough index that we only read some of it on a typical
605
index = self.make_index(nodes=self.make_nodes(64))
606
# lookup the keys in the middle of the file
607
result =index._lookup_keys_via_location(
608
[(index._size // 2, (b'40', ))])
609
# check the parse map, this determines the test validity
610
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
611
self.assertEqual([(None, self.make_key(26)),
612
(self.make_key(31), self.make_key(48))],
613
index._parsed_key_map)
614
# reset the transport log
615
del index._transport._activity[:]
616
# now looking up a key in the portion of the file already parsed should
617
# not create a new transport request, and should return False (cannot
618
# be in the index) - even when the byte location we ask for is outside
620
result = index._lookup_keys_via_location(
622
self.assertEqual([((4000, (b'40', )), False)],
624
self.assertEqual([], index._transport._activity)
626
def test_lookup_present_key_answers_without_io_when_map_permits(self):
627
# generate a big enough index that we only read some of it on a typical
629
index = self.make_index(nodes=self.make_nodes(64))
630
# lookup the keys in the middle of the file
631
result =index._lookup_keys_via_location(
632
[(index._size // 2, (b'40', ))])
633
# check the parse map, this determines the test validity
634
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
635
self.assertEqual([(None, self.make_key(26)),
636
(self.make_key(31), self.make_key(48))],
637
index._parsed_key_map)
638
# reset the transport log
639
del index._transport._activity[:]
640
# now looking up a key in the portion of the file already parsed should
641
# not create a new transport request, and should return False (cannot
642
# be in the index) - even when the byte location we ask for is outside
645
result = index._lookup_keys_via_location([(4000, self.make_key(40))])
647
[((4000, self.make_key(40)),
648
(index, self.make_key(40), self.make_value(40)))],
650
self.assertEqual([], index._transport._activity)
652
def test_lookup_key_below_probed_area(self):
653
# generate a big enough index that we only read some of it on a typical
655
index = self.make_index(nodes=self.make_nodes(64))
656
# ask for the key in the middle, but a key that is located in the
657
# unparsed region before the middle.
658
result =index._lookup_keys_via_location(
659
[(index._size // 2, (b'30', ))])
660
# check the parse map, this determines the test validity
661
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
662
self.assertEqual([(None, self.make_key(26)),
663
(self.make_key(31), self.make_key(48))],
664
index._parsed_key_map)
665
self.assertEqual([((index._size // 2, ('30', )), -1)],
668
def test_lookup_key_above_probed_area(self):
669
# generate a big enough index that we only read some of it on a typical
671
index = self.make_index(nodes=self.make_nodes(64))
672
# ask for the key in the middle, but a key that is located in the
673
# unparsed region after the middle.
674
result =index._lookup_keys_via_location(
675
[(index._size // 2, (b'50', ))])
676
# check the parse map, this determines the test validity
677
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
678
self.assertEqual([(None, self.make_key(26)),
679
(self.make_key(31), self.make_key(48))],
680
index._parsed_key_map)
681
self.assertEqual([((index._size // 2, (b'50', )), +1)],
684
def test_lookup_key_resolves_references(self):
685
# generate a big enough index that we only read some of it on a typical
688
for counter in range(99):
689
nodes.append((self.make_key(counter), self.make_value(counter),
690
((self.make_key(counter + 20),),) ))
691
index = self.make_index(ref_lists=1, nodes=nodes)
692
# lookup a key in the middle that does not exist, so that when we can
693
# check that the referred-to-keys are not accessed automatically.
694
index_size = index._size
695
index_center = index_size // 2
696
result = index._lookup_keys_via_location(
697
[(index_center, (b'40', ))])
698
# check the parse map - only the start and middle should have been
700
self.assertEqual([(0, 4027), (10198, 14028)], index._parsed_byte_map)
701
self.assertEqual([(None, self.make_key(17)),
702
(self.make_key(44), self.make_key(5))],
703
index._parsed_key_map)
704
# and check the transport activity likewise.
706
[('readv', 'index', [(index_center, 800), (0, 200)], True,
708
index._transport._activity)
709
# reset the transport log for testing the reference lookup
710
del index._transport._activity[:]
711
# now looking up a key in the portion of the file already parsed should
712
# only perform IO to resolve its key references.
713
result = index._lookup_keys_via_location([(11000, self.make_key(45))])
715
[((11000, self.make_key(45)),
716
(index, self.make_key(45), self.make_value(45),
717
((self.make_key(65),),)))],
719
self.assertEqual([('readv', 'index', [(15093, 800)], True, index_size)],
720
index._transport._activity)
722
def test_lookup_key_can_buffer_all(self):
724
for counter in range(64):
725
nodes.append((self.make_key(counter), self.make_value(counter),
726
((self.make_key(counter + 20),),) ))
727
index = self.make_index(ref_lists=1, nodes=nodes)
728
# lookup a key in the middle that does not exist, so that when we can
729
# check that the referred-to-keys are not accessed automatically.
730
index_size = index._size
731
index_center = index_size // 2
732
result = index._lookup_keys_via_location([(index_center, (b'40', ))])
733
# check the parse map - only the start and middle should have been
735
self.assertEqual([(0, 3890), (6444, 10274)], index._parsed_byte_map)
736
self.assertEqual([(None, self.make_key(25)),
737
(self.make_key(37), self.make_key(52))],
738
index._parsed_key_map)
739
# and check the transport activity likewise.
741
[('readv', 'index', [(index_center, 800), (0, 200)], True,
743
index._transport._activity)
744
# reset the transport log for testing the reference lookup
745
del index._transport._activity[:]
746
# now looking up a key in the portion of the file already parsed should
747
# only perform IO to resolve its key references.
748
result = index._lookup_keys_via_location([(7000, self.make_key(40))])
750
[((7000, self.make_key(40)),
751
(index, self.make_key(40), self.make_value(40),
752
((self.make_key(60),),)))],
754
# Resolving the references would have required more data read, and we
755
# are already above the 50% threshold, so it triggered a _buffer_all
756
self.assertEqual([('get', 'index')], index._transport._activity)
758
def test_iter_all_entries_empty(self):
759
index = self.make_index()
760
self.assertEqual([], list(index.iter_all_entries()))
762
def test_iter_all_entries_simple(self):
763
index = self.make_index(nodes=[((b'name', ), b'data', ())])
764
self.assertEqual([(index, (b'name', ), b'data')],
765
list(index.iter_all_entries()))
767
def test_iter_all_entries_simple_2_elements(self):
768
index = self.make_index(key_elements=2,
769
nodes=[((b'name', b'surname'), b'data', ())])
770
self.assertEqual([(index, (b'name', b'surname'), b'data')],
771
list(index.iter_all_entries()))
773
def test_iter_all_entries_references_resolved(self):
774
index = self.make_index(1, nodes=[
775
((b'name', ), b'data', ([(b'ref', )], )),
776
((b'ref', ), b'refdata', ([], ))])
777
self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),)),
778
(index, (b'ref', ), b'refdata', ((), ))},
779
set(index.iter_all_entries()))
781
def test_iter_entries_buffers_once(self):
782
index = self.make_index(nodes=self.make_nodes(2))
783
# reset the transport log
784
del index._transport._activity[:]
785
self.assertEqual({(index, self.make_key(1), self.make_value(1))},
786
set(index.iter_entries([self.make_key(1)])))
787
# We should have requested reading the header bytes
788
# But not needed any more than that because it would have triggered a
791
('readv', 'index', [(0, 200)], True, index._size),
793
index._transport._activity)
794
# And that should have been enough to trigger reading the whole index
796
self.assertIsNot(None, index._nodes)
798
def test_iter_entries_buffers_by_bytes_read(self):
799
index = self.make_index(nodes=self.make_nodes(64))
800
list(index.iter_entries([self.make_key(10)]))
801
# The first time through isn't enough to trigger a buffer all
802
self.assertIs(None, index._nodes)
803
self.assertEqual(4096, index._bytes_read)
804
# Grabbing a key in that same page won't trigger a buffer all, as we
805
# still haven't read 50% of the file
806
list(index.iter_entries([self.make_key(11)]))
807
self.assertIs(None, index._nodes)
808
self.assertEqual(4096, index._bytes_read)
809
# We haven't read more data, so reading outside the range won't trigger
810
# a buffer all right away
811
list(index.iter_entries([self.make_key(40)]))
812
self.assertIs(None, index._nodes)
813
self.assertEqual(8192, index._bytes_read)
814
# On the next pass, we will not trigger buffer all if the key is
815
# available without reading more
816
list(index.iter_entries([self.make_key(32)]))
817
self.assertIs(None, index._nodes)
818
# But if we *would* need to read more to resolve it, then we will
820
list(index.iter_entries([self.make_key(60)]))
821
self.assertIsNot(None, index._nodes)
823
def test_iter_entries_references_resolved(self):
824
index = self.make_index(1, nodes=[
825
((b'name', ), b'data', ([(b'ref', ), (b'ref', )], )),
826
((b'ref', ), b'refdata', ([], ))])
827
self.assertEqual({(index, (b'name', ), b'data', (((b'ref',), (b'ref',)),)),
828
(index, (b'ref', ), b'refdata', ((), ))},
829
set(index.iter_entries([(b'name',), (b'ref',)])))
831
def test_iter_entries_references_2_refs_resolved(self):
832
index = self.make_index(2, nodes=[
833
((b'name', ), b'data', ([(b'ref', )], [(b'ref', )])),
834
((b'ref', ), b'refdata', ([], []))])
835
self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),), ((b'ref',),))),
836
(index, (b'ref', ), b'refdata', ((), ()))},
837
set(index.iter_entries([(b'name',), (b'ref',)])))
839
def test_iteration_absent_skipped(self):
840
index = self.make_index(1, nodes=[
841
((b'name', ), b'data', ([(b'ref', )], ))])
842
self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),))},
843
set(index.iter_all_entries()))
844
self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),))},
845
set(index.iter_entries([(b'name', )])))
846
self.assertEqual([], list(index.iter_entries([(b'ref', )])))
848
def test_iteration_absent_skipped_2_element_keys(self):
849
index = self.make_index(1, key_elements=2, nodes=[
850
((b'name', b'fin'), b'data', ([(b'ref', b'erence')], ))])
851
self.assertEqual([(index, (b'name', b'fin'), b'data', (((b'ref', b'erence'),),))],
852
list(index.iter_all_entries()))
853
self.assertEqual([(index, (b'name', b'fin'), b'data', (((b'ref', b'erence'),),))],
854
list(index.iter_entries([(b'name', b'fin')])))
855
self.assertEqual([], list(index.iter_entries([(b'ref', b'erence')])))
857
def test_iter_all_keys(self):
858
index = self.make_index(1, nodes=[
859
((b'name', ), b'data', ([(b'ref', )], )),
860
((b'ref', ), b'refdata', ([], ))])
861
self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),)),
862
(index, (b'ref', ), b'refdata', ((), ))},
863
set(index.iter_entries([(b'name', ), (b'ref', )])))
865
def test_iter_nothing_empty(self):
866
index = self.make_index()
867
self.assertEqual([], list(index.iter_entries([])))
869
def test_iter_missing_entry_empty(self):
870
index = self.make_index()
871
self.assertEqual([], list(index.iter_entries([(b'a', )])))
873
def test_iter_missing_entry_empty_no_size(self):
874
idx = self.make_index()
875
idx = _mod_index.GraphIndex(idx._transport, 'index', None)
876
self.assertEqual([], list(idx.iter_entries([(b'a', )])))
878
def test_iter_key_prefix_1_element_key_None(self):
879
index = self.make_index()
880
self.assertRaises(_mod_index.BadIndexKey, list,
881
index.iter_entries_prefix([(None, )]))
883
def test_iter_key_prefix_wrong_length(self):
884
index = self.make_index()
885
self.assertRaises(_mod_index.BadIndexKey, list,
886
index.iter_entries_prefix([(b'foo', None)]))
887
index = self.make_index(key_elements=2)
888
self.assertRaises(_mod_index.BadIndexKey, list,
889
index.iter_entries_prefix([(b'foo', )]))
890
self.assertRaises(_mod_index.BadIndexKey, list,
891
index.iter_entries_prefix([(b'foo', None, None)]))
893
def test_iter_key_prefix_1_key_element_no_refs(self):
894
index = self.make_index( nodes=[
895
((b'name', ), b'data', ()),
896
((b'ref', ), b'refdata', ())])
897
self.assertEqual({(index, (b'name', ), b'data'),
898
(index, (b'ref', ), b'refdata')},
899
set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
901
def test_iter_key_prefix_1_key_element_refs(self):
902
index = self.make_index(1, nodes=[
903
((b'name', ), b'data', ([(b'ref', )], )),
904
((b'ref', ), b'refdata', ([], ))])
905
self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),)),
906
(index, (b'ref', ), b'refdata', ((), ))},
907
set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
909
def test_iter_key_prefix_2_key_element_no_refs(self):
910
index = self.make_index(key_elements=2, nodes=[
911
((b'name', b'fin1'), b'data', ()),
912
((b'name', b'fin2'), b'beta', ()),
913
((b'ref', b'erence'), b'refdata', ())])
914
self.assertEqual({(index, (b'name', b'fin1'), b'data'),
915
(index, (b'ref', b'erence'), b'refdata')},
916
set(index.iter_entries_prefix([(b'name', b'fin1'), (b'ref', b'erence')])))
917
self.assertEqual({(index, (b'name', b'fin1'), b'data'),
918
(index, (b'name', b'fin2'), b'beta')},
919
set(index.iter_entries_prefix([(b'name', None)])))
921
def test_iter_key_prefix_2_key_element_refs(self):
922
index = self.make_index(1, key_elements=2, nodes=[
923
((b'name', b'fin1'), b'data', ([(b'ref', b'erence')], )),
924
((b'name', b'fin2'), b'beta', ([], )),
925
((b'ref', b'erence'), b'refdata', ([], ))])
926
self.assertEqual({(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
927
(index, (b'ref', b'erence'), b'refdata', ((), ))},
928
set(index.iter_entries_prefix([(b'name', b'fin1'), (b'ref', b'erence')])))
929
self.assertEqual({(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
930
(index, (b'name', b'fin2'), b'beta', ((), ))},
931
set(index.iter_entries_prefix([(b'name', None)])))
933
def test_key_count_empty(self):
934
index = self.make_index()
935
self.assertEqual(0, index.key_count())
937
def test_key_count_one(self):
938
index = self.make_index(nodes=[((b'name', ), b'', ())])
939
self.assertEqual(1, index.key_count())
941
def test_key_count_two(self):
942
index = self.make_index(nodes=[
943
((b'name', ), b'', ()), ((b'foo', ), b'', ())])
944
self.assertEqual(2, index.key_count())
946
def test_read_and_parse_tracks_real_read_value(self):
947
index = self.make_index(nodes=self.make_nodes(10))
948
del index._transport._activity[:]
949
index._read_and_parse([(0, 200)])
951
('readv', 'index', [(0, 200)], True, index._size),
953
index._transport._activity)
954
# The readv expansion code will expand the initial request to 4096
955
# bytes, which is more than enough to read the entire index, and we
956
# will track the fact that we read that many bytes.
957
self.assertEqual(index._size, index._bytes_read)
959
def test_read_and_parse_triggers_buffer_all(self):
960
index = self.make_index(key_elements=2, nodes=[
961
((b'name', b'fin1'), b'data', ()),
962
((b'name', b'fin2'), b'beta', ()),
963
((b'ref', b'erence'), b'refdata', ())])
964
self.assertTrue(index._size > 0)
965
self.assertIs(None, index._nodes)
966
index._read_and_parse([(0, index._size)])
967
self.assertIsNot(None, index._nodes)
969
def test_validate_bad_index_errors(self):
970
trans = self.get_transport()
971
trans.put_bytes('name', b"not an index\n")
972
idx = _mod_index.GraphIndex(trans, 'name', 13)
973
self.assertRaises(_mod_index.BadIndexFormatSignature, idx.validate)
975
def test_validate_bad_node_refs(self):
976
idx = self.make_index(2)
977
trans = self.get_transport()
978
content = trans.get_bytes('index')
979
# change the options line to end with a rather than a parseable number
980
new_content = content[:-2] + b'a\n\n'
981
trans.put_bytes('index', new_content)
982
self.assertRaises(_mod_index.BadIndexOptions, idx.validate)
984
def test_validate_missing_end_line_empty(self):
985
index = self.make_index(2)
986
trans = self.get_transport()
987
content = trans.get_bytes('index')
988
# truncate the last byte
989
trans.put_bytes('index', content[:-1])
990
self.assertRaises(_mod_index.BadIndexData, index.validate)
992
def test_validate_missing_end_line_nonempty(self):
993
index = self.make_index(2, nodes=[((b'key', ), b'', ([], []))])
994
trans = self.get_transport()
995
content = trans.get_bytes('index')
996
# truncate the last byte
997
trans.put_bytes('index', content[:-1])
998
self.assertRaises(_mod_index.BadIndexData, index.validate)
1000
def test_validate_empty(self):
1001
index = self.make_index()
1004
def test_validate_no_refs_content(self):
1005
index = self.make_index(nodes=[((b'key', ), b'value', ())])
1008
# XXX: external_references tests are duplicated in test_btree_index. We
1009
# probably should have per_graph_index tests...
1010
def test_external_references_no_refs(self):
1011
index = self.make_index(ref_lists=0, nodes=[])
1012
self.assertRaises(ValueError, index.external_references, 0)
1014
def test_external_references_no_results(self):
1015
index = self.make_index(ref_lists=1, nodes=[
1016
((b'key',), b'value', ([],))])
1017
self.assertEqual(set(), index.external_references(0))
1019
def test_external_references_missing_ref(self):
1020
missing_key = (b'missing',)
1021
index = self.make_index(ref_lists=1, nodes=[
1022
((b'key',), b'value', ([missing_key],))])
1023
self.assertEqual({missing_key}, index.external_references(0))
1025
def test_external_references_multiple_ref_lists(self):
1026
missing_key = (b'missing',)
1027
index = self.make_index(ref_lists=2, nodes=[
1028
((b'key',), b'value', ([], [missing_key]))])
1029
self.assertEqual(set([]), index.external_references(0))
1030
self.assertEqual({missing_key}, index.external_references(1))
1032
def test_external_references_two_records(self):
1033
index = self.make_index(ref_lists=1, nodes=[
1034
((b'key-1',), b'value', ([(b'key-2',)],)),
1035
((b'key-2',), b'value', ([],)),
1037
self.assertEqual(set([]), index.external_references(0))
1039
def test__find_ancestors(self):
1042
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1043
(key1, b'value', ([key2],)),
1044
(key2, b'value', ([],)),
1047
missing_keys = set()
1048
search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
1049
self.assertEqual({key1: (key2,)}, parent_map)
1050
self.assertEqual(set(), missing_keys)
1051
self.assertEqual({key2}, search_keys)
1052
search_keys = index._find_ancestors(search_keys, 0, parent_map,
1054
self.assertEqual({key1: (key2,), key2: ()}, parent_map)
1055
self.assertEqual(set(), missing_keys)
1056
self.assertEqual(set(), search_keys)
1058
def test__find_ancestors_w_missing(self):
1062
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1063
(key1, b'value', ([key2],)),
1064
(key2, b'value', ([],)),
1067
missing_keys = set()
1068
search_keys = index._find_ancestors([key2, key3], 0, parent_map,
1070
self.assertEqual({key2: ()}, parent_map)
1071
self.assertEqual({key3}, missing_keys)
1072
self.assertEqual(set(), search_keys)
1074
def test__find_ancestors_dont_search_known(self):
1078
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1079
(key1, b'value', ([key2],)),
1080
(key2, b'value', ([key3],)),
1081
(key3, b'value', ([],)),
1083
# We already know about key2, so we won't try to search for key3
1084
parent_map = {key2: (key3,)}
1085
missing_keys = set()
1086
search_keys = index._find_ancestors([key1], 0, parent_map,
1088
self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1089
self.assertEqual(set(), missing_keys)
1090
self.assertEqual(set(), search_keys)
1092
def test_supports_unlimited_cache(self):
1093
builder = _mod_index.GraphIndexBuilder(0, key_elements=1)
1094
stream = builder.finish()
1095
trans = self.get_transport()
1096
size = trans.put_file('index', stream)
1097
# It doesn't matter what unlimited_cache does here, just that it can be
1099
idx = _mod_index.GraphIndex(trans, 'index', size, unlimited_cache=True)
1102
class TestCombinedGraphIndex(tests.TestCaseWithMemoryTransport):
1104
def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
1105
builder = _mod_index.GraphIndexBuilder(ref_lists, key_elements=key_elements)
1106
for key, value, references in nodes:
1107
builder.add_node(key, value, references)
1108
stream = builder.finish()
1109
trans = self.get_transport()
1110
size = trans.put_file(name, stream)
1111
return _mod_index.GraphIndex(trans, name, size)
1113
def make_combined_index_with_missing(self, missing=['1', '2']):
1114
"""Create a CombinedGraphIndex which will have missing indexes.
1116
This creates a CGI which thinks it has 2 indexes, however they have
1117
been deleted. If CGI._reload_func() is called, then it will repopulate
1120
:param missing: The underlying indexes to delete
1121
:return: (CombinedGraphIndex, reload_counter)
1123
idx1 = self.make_index('1', nodes=[((b'1',), b'', ())])
1124
idx2 = self.make_index('2', nodes=[((b'2',), b'', ())])
1125
idx3 = self.make_index('3', nodes=[
1127
((b'2',), b'', ())])
1129
# total_reloads, num_changed, num_unchanged
1130
reload_counter = [0, 0, 0]
1132
reload_counter[0] += 1
1133
new_indices = [idx3]
1134
if idx._indices == new_indices:
1135
reload_counter[2] += 1
1137
reload_counter[1] += 1
1138
idx._indices[:] = new_indices
1140
idx = _mod_index.CombinedGraphIndex([idx1, idx2], reload_func=reload)
1141
trans = self.get_transport()
1142
for fname in missing:
1144
return idx, reload_counter
1146
def test_open_missing_index_no_error(self):
1147
trans = self.get_transport()
1148
idx1 = _mod_index.GraphIndex(trans, 'missing', 100)
1149
idx = _mod_index.CombinedGraphIndex([idx1])
1151
def test_add_index(self):
1152
idx = _mod_index.CombinedGraphIndex([])
1153
idx1 = self.make_index('name', 0, nodes=[((b'key', ), b'', ())])
1154
idx.insert_index(0, idx1)
1155
self.assertEqual([(idx1, (b'key', ), b'')],
1156
list(idx.iter_all_entries()))
1158
def test_clear_cache(self):
1161
class ClearCacheProxy(object):
1163
def __init__(self, index):
1166
def __getattr__(self, name):
1167
return getattr(self._index)
1169
def clear_cache(self):
1170
log.append(self._index)
1171
return self._index.clear_cache()
1173
idx = _mod_index.CombinedGraphIndex([])
1174
idx1 = self.make_index('name', 0, nodes=[((b'key', ), b'', ())])
1175
idx.insert_index(0, ClearCacheProxy(idx1))
1176
idx2 = self.make_index('name', 0, nodes=[((b'key', ), b'', ())])
1177
idx.insert_index(1, ClearCacheProxy(idx2))
1178
# CombinedGraphIndex should call 'clear_cache()' on all children
1180
self.assertEqual(sorted([idx1, idx2]), sorted(log))
1182
def test_iter_all_entries_empty(self):
1183
idx = _mod_index.CombinedGraphIndex([])
1184
self.assertEqual([], list(idx.iter_all_entries()))
1186
def test_iter_all_entries_children_empty(self):
1187
idx1 = self.make_index('name')
1188
idx = _mod_index.CombinedGraphIndex([idx1])
1189
self.assertEqual([], list(idx.iter_all_entries()))
1191
def test_iter_all_entries_simple(self):
1192
idx1 = self.make_index('name', nodes=[((b'name', ), b'data', ())])
1193
idx = _mod_index.CombinedGraphIndex([idx1])
1194
self.assertEqual([(idx1, (b'name', ), b'data')],
1195
list(idx.iter_all_entries()))
1197
def test_iter_all_entries_two_indices(self):
1198
idx1 = self.make_index('name1', nodes=[((b'name', ), b'data', ())])
1199
idx2 = self.make_index('name2', nodes=[((b'2', ), b'', ())])
1200
idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1201
self.assertEqual([(idx1, (b'name', ), b'data'),
1202
(idx2, (b'2', ), b'')],
1203
list(idx.iter_all_entries()))
1205
def test_iter_entries_two_indices_dup_key(self):
1206
idx1 = self.make_index('name1', nodes=[((b'name', ), b'data', ())])
1207
idx2 = self.make_index('name2', nodes=[((b'name', ), b'data', ())])
1208
idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1209
self.assertEqual([(idx1, (b'name', ), b'data')],
1210
list(idx.iter_entries([(b'name', )])))
1212
def test_iter_all_entries_two_indices_dup_key(self):
1213
idx1 = self.make_index('name1', nodes=[((b'name', ), b'data', ())])
1214
idx2 = self.make_index('name2', nodes=[((b'name', ), b'data', ())])
1215
idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1216
self.assertEqual([(idx1, (b'name', ), b'data')],
1217
list(idx.iter_all_entries()))
1219
def test_iter_key_prefix_2_key_element_refs(self):
1220
idx1 = self.make_index('1', 1, key_elements=2, nodes=[
1221
((b'name', b'fin1'), b'data', ([(b'ref', b'erence')], ))])
1222
idx2 = self.make_index('2', 1, key_elements=2, nodes=[
1223
((b'name', b'fin2'), b'beta', ([], )),
1224
((b'ref', b'erence'), b'refdata', ([], ))])
1225
idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1226
self.assertEqual({(idx1, (b'name', b'fin1'), b'data',
1227
(((b'ref', b'erence'),),)),
1228
(idx2, (b'ref', b'erence'), b'refdata', ((), ))},
1229
set(idx.iter_entries_prefix([(b'name', b'fin1'),
1230
(b'ref', b'erence')])))
1231
self.assertEqual({(idx1, (b'name', b'fin1'), b'data',
1232
(((b'ref', b'erence'),),)),
1233
(idx2, (b'name', b'fin2'), b'beta', ((), ))},
1234
set(idx.iter_entries_prefix([(b'name', None)])))
1236
def test_iter_nothing_empty(self):
1237
idx = _mod_index.CombinedGraphIndex([])
1238
self.assertEqual([], list(idx.iter_entries([])))
1240
def test_iter_nothing_children_empty(self):
1241
idx1 = self.make_index('name')
1242
idx = _mod_index.CombinedGraphIndex([idx1])
1243
self.assertEqual([], list(idx.iter_entries([])))
1245
def test_iter_all_keys(self):
1246
idx1 = self.make_index('1', 1, nodes=[((b'name', ), b'data',
1248
idx2 = self.make_index('2', 1, nodes=[((b'ref', ), b'refdata', ((), ))])
1249
idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1250
self.assertEqual({(idx1, (b'name', ), b'data', (((b'ref', ), ), )),
1251
(idx2, (b'ref', ), b'refdata', ((), ))},
1252
set(idx.iter_entries([(b'name', ), (b'ref', )])))
1254
def test_iter_all_keys_dup_entry(self):
1255
idx1 = self.make_index('1', 1, nodes=[((b'name', ), b'data',
1257
((b'ref', ), b'refdata', ([], ))])
1258
idx2 = self.make_index('2', 1, nodes=[((b'ref', ), b'refdata', ([], ))])
1259
idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1260
self.assertEqual({(idx1, (b'name', ), b'data', (((b'ref',),),)),
1261
(idx1, (b'ref', ), b'refdata', ((), ))},
1262
set(idx.iter_entries([(b'name', ), (b'ref', )])))
1264
def test_iter_missing_entry_empty(self):
1265
idx = _mod_index.CombinedGraphIndex([])
1266
self.assertEqual([], list(idx.iter_entries([('a', )])))
1268
def test_iter_missing_entry_one_index(self):
1269
idx1 = self.make_index('1')
1270
idx = _mod_index.CombinedGraphIndex([idx1])
1271
self.assertEqual([], list(idx.iter_entries([(b'a', )])))
1273
def test_iter_missing_entry_two_index(self):
1274
idx1 = self.make_index('1')
1275
idx2 = self.make_index('2')
1276
idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1277
self.assertEqual([], list(idx.iter_entries([('a', )])))
1279
def test_iter_entry_present_one_index_only(self):
1280
idx1 = self.make_index('1', nodes=[((b'key', ), b'', ())])
1281
idx2 = self.make_index('2', nodes=[])
1282
idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1283
self.assertEqual([(idx1, (b'key', ), b'')],
1284
list(idx.iter_entries([(b'key', )])))
1285
# and in the other direction
1286
idx = _mod_index.CombinedGraphIndex([idx2, idx1])
1287
self.assertEqual([(idx1, (b'key', ), b'')],
1288
list(idx.iter_entries([(b'key', )])))
1290
def test_key_count_empty(self):
1291
idx1 = self.make_index('1', nodes=[])
1292
idx2 = self.make_index('2', nodes=[])
1293
idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1294
self.assertEqual(0, idx.key_count())
1296
def test_key_count_sums_index_keys(self):
1297
idx1 = self.make_index('1', nodes=[
1299
((b'2',), b'', ())])
1300
idx2 = self.make_index('2', nodes=[((b'1',), b'', ())])
1301
idx = _mod_index.CombinedGraphIndex([idx1, idx2])
1302
self.assertEqual(3, idx.key_count())
1304
def test_validate_bad_child_index_errors(self):
1305
trans = self.get_transport()
1306
trans.put_bytes('name', b"not an index\n")
1307
idx1 = _mod_index.GraphIndex(trans, 'name', 13)
1308
idx = _mod_index.CombinedGraphIndex([idx1])
1309
self.assertRaises(_mod_index.BadIndexFormatSignature, idx.validate)
1311
def test_validate_empty(self):
1312
idx = _mod_index.CombinedGraphIndex([])
1315
def test_key_count_reloads(self):
1316
idx, reload_counter = self.make_combined_index_with_missing()
1317
self.assertEqual(2, idx.key_count())
1318
self.assertEqual([1, 1, 0], reload_counter)
1320
def test_key_count_no_reload(self):
1321
idx, reload_counter = self.make_combined_index_with_missing()
1322
idx._reload_func = None
1323
# Without a _reload_func we just raise the exception
1324
self.assertRaises(errors.NoSuchFile, idx.key_count)
1326
def test_key_count_reloads_and_fails(self):
1327
# We have deleted all underlying indexes, so we will try to reload, but
1328
# still fail. This is mostly to test we don't get stuck in an infinite
1329
# loop trying to reload
1330
idx, reload_counter = self.make_combined_index_with_missing(
1332
self.assertRaises(errors.NoSuchFile, idx.key_count)
1333
self.assertEqual([2, 1, 1], reload_counter)
1335
def test_iter_entries_reloads(self):
1336
index, reload_counter = self.make_combined_index_with_missing()
1337
result = list(index.iter_entries([(b'1',), (b'2',), (b'3',)]))
1338
index3 = index._indices[0]
1339
self.assertEqual([(index3, (b'1',), b''), (index3, (b'2',), b'')],
1341
self.assertEqual([1, 1, 0], reload_counter)
1343
def test_iter_entries_reloads_midway(self):
1344
# The first index still looks present, so we get interrupted mid-way
1346
index, reload_counter = self.make_combined_index_with_missing(['2'])
1347
index1, index2 = index._indices
1348
result = list(index.iter_entries([(b'1',), (b'2',), (b'3',)]))
1349
index3 = index._indices[0]
1350
# We had already yielded b'1', so we just go on to the next, we should
1351
# not yield b'1' twice.
1352
self.assertEqual([(index1, (b'1',), b''), (index3, (b'2',), b'')],
1354
self.assertEqual([1, 1, 0], reload_counter)
1356
def test_iter_entries_no_reload(self):
1357
index, reload_counter = self.make_combined_index_with_missing()
1358
index._reload_func = None
1359
# Without a _reload_func we just raise the exception
1360
self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1362
def test_iter_entries_reloads_and_fails(self):
1363
index, reload_counter = self.make_combined_index_with_missing(
1365
self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1366
self.assertEqual([2, 1, 1], reload_counter)
1368
def test_iter_all_entries_reloads(self):
1369
index, reload_counter = self.make_combined_index_with_missing()
1370
result = list(index.iter_all_entries())
1371
index3 = index._indices[0]
1372
self.assertEqual([(index3, (b'1',), b''), (index3, (b'2',), b'')],
1374
self.assertEqual([1, 1, 0], reload_counter)
1376
def test_iter_all_entries_reloads_midway(self):
1377
index, reload_counter = self.make_combined_index_with_missing(['2'])
1378
index1, index2 = index._indices
1379
result = list(index.iter_all_entries())
1380
index3 = index._indices[0]
1381
# We had already yielded '1', so we just go on to the next, we should
1382
# not yield '1' twice.
1383
self.assertEqual([(index1, (b'1',), b''), (index3, (b'2',), b'')],
1385
self.assertEqual([1, 1, 0], reload_counter)
1387
def test_iter_all_entries_no_reload(self):
1388
index, reload_counter = self.make_combined_index_with_missing()
1389
index._reload_func = None
1390
self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1392
def test_iter_all_entries_reloads_and_fails(self):
1393
index, reload_counter = self.make_combined_index_with_missing(
1395
self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1397
def test_iter_entries_prefix_reloads(self):
1398
index, reload_counter = self.make_combined_index_with_missing()
1399
result = list(index.iter_entries_prefix([(b'1',)]))
1400
index3 = index._indices[0]
1401
self.assertEqual([(index3, (b'1',), b'')], result)
1402
self.assertEqual([1, 1, 0], reload_counter)
1404
def test_iter_entries_prefix_reloads_midway(self):
1405
index, reload_counter = self.make_combined_index_with_missing(['2'])
1406
index1, index2 = index._indices
1407
result = list(index.iter_entries_prefix([(b'1',)]))
1408
index3 = index._indices[0]
1409
# We had already yielded b'1', so we just go on to the next, we should
1410
# not yield b'1' twice.
1411
self.assertEqual([(index1, (b'1',), b'')], result)
1412
self.assertEqual([1, 1, 0], reload_counter)
1414
def test_iter_entries_prefix_no_reload(self):
1415
index, reload_counter = self.make_combined_index_with_missing()
1416
index._reload_func = None
1417
self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1420
def test_iter_entries_prefix_reloads_and_fails(self):
1421
index, reload_counter = self.make_combined_index_with_missing(
1423
self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1427
def make_index_with_simple_nodes(self, name, num_nodes=1):
1428
"""Make an index named after 'name', with keys named after 'name' too.
1430
Nodes will have a value of '' and no references.
1433
((('index-%s-key-%s' % (name, n)).encode('ascii'),), b'', ())
1434
for n in range(1, num_nodes+1)]
1435
return self.make_index('index-%s' % name, 0, nodes=nodes)
1437
def test_reorder_after_iter_entries(self):
1438
# Four indices: [key1] in idx1, [key2,key3] in idx2, [] in idx3,
1440
idx = _mod_index.CombinedGraphIndex([])
1441
idx.insert_index(0, self.make_index_with_simple_nodes('1'), b'1')
1442
idx.insert_index(1, self.make_index_with_simple_nodes('2'), b'2')
1443
idx.insert_index(2, self.make_index_with_simple_nodes('3'), b'3')
1444
idx.insert_index(3, self.make_index_with_simple_nodes('4'), b'4')
1445
idx1, idx2, idx3, idx4 = idx._indices
1446
# Query a key from idx4 and idx2.
1447
self.assertLength(2, list(idx.iter_entries(
1448
[(b'index-4-key-1',), (b'index-2-key-1',)])))
1449
# Now idx2 and idx4 should be moved to the front (and idx1 should
1450
# still be before idx3).
1451
self.assertEqual([idx2, idx4, idx1, idx3], idx._indices)
1452
self.assertEqual([b'2', b'4', b'1', b'3'], idx._index_names)
1454
def test_reorder_propagates_to_siblings(self):
1455
# Two CombinedGraphIndex objects, with the same number of indicies with
1457
cgi1 = _mod_index.CombinedGraphIndex([])
1458
cgi2 = _mod_index.CombinedGraphIndex([])
1459
cgi1.insert_index(0, self.make_index_with_simple_nodes('1-1'), 'one')
1460
cgi1.insert_index(1, self.make_index_with_simple_nodes('1-2'), 'two')
1461
cgi2.insert_index(0, self.make_index_with_simple_nodes('2-1'), 'one')
1462
cgi2.insert_index(1, self.make_index_with_simple_nodes('2-2'), 'two')
1463
index2_1, index2_2 = cgi2._indices
1464
cgi1.set_sibling_indices([cgi2])
1465
# Trigger a reordering in cgi1. cgi2 will be reordered as well.
1466
list(cgi1.iter_entries([('index-1-2-key-1',)]))
1467
self.assertEqual([index2_2, index2_1], cgi2._indices)
1468
self.assertEqual(['two', 'one'], cgi2._index_names)
1470
def test_validate_reloads(self):
1471
idx, reload_counter = self.make_combined_index_with_missing()
1473
self.assertEqual([1, 1, 0], reload_counter)
1475
def test_validate_reloads_midway(self):
1476
idx, reload_counter = self.make_combined_index_with_missing(['2'])
1479
def test_validate_no_reload(self):
1480
idx, reload_counter = self.make_combined_index_with_missing()
1481
idx._reload_func = None
1482
self.assertRaises(errors.NoSuchFile, idx.validate)
1484
def test_validate_reloads_and_fails(self):
1485
idx, reload_counter = self.make_combined_index_with_missing(
1487
self.assertRaises(errors.NoSuchFile, idx.validate)
1489
def test_find_ancestors_across_indexes(self):
1494
index1 = self.make_index('12', ref_lists=1, nodes=[
1495
(key1, b'value', ([],)),
1496
(key2, b'value', ([key1],)),
1498
index2 = self.make_index('34', ref_lists=1, nodes=[
1499
(key3, b'value', ([key2],)),
1500
(key4, b'value', ([key3],)),
1502
c_index = _mod_index.CombinedGraphIndex([index1, index2])
1503
parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1504
self.assertEqual({key1: ()}, parent_map)
1505
self.assertEqual(set(), missing_keys)
1506
# Now look for a key from index2 which requires us to find the key in
1507
# the second index, and then continue searching for parents in the
1509
parent_map, missing_keys = c_index.find_ancestry([key3], 0)
1510
self.assertEqual({key1: (), key2: (key1,), key3: (key2,)}, parent_map)
1511
self.assertEqual(set(), missing_keys)
1513
def test_find_ancestors_missing_keys(self):
1518
index1 = self.make_index('12', ref_lists=1, nodes=[
1519
(key1, b'value', ([],)),
1520
(key2, b'value', ([key1],)),
1522
index2 = self.make_index('34', ref_lists=1, nodes=[
1523
(key3, b'value', ([key2],)),
1525
c_index = _mod_index.CombinedGraphIndex([index1, index2])
1526
# Searching for a key which is actually not present at all should
1527
# eventually converge
1528
parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1529
self.assertEqual({}, parent_map)
1530
self.assertEqual({key4}, missing_keys)
1532
def test_find_ancestors_no_indexes(self):
1533
c_index = _mod_index.CombinedGraphIndex([])
1535
parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1536
self.assertEqual({}, parent_map)
1537
self.assertEqual({key1}, missing_keys)
1539
def test_find_ancestors_ghost_parent(self):
1544
index1 = self.make_index('12', ref_lists=1, nodes=[
1545
(key1, b'value', ([],)),
1546
(key2, b'value', ([key1],)),
1548
index2 = self.make_index('34', ref_lists=1, nodes=[
1549
(key4, b'value', ([key2, key3],)),
1551
c_index = _mod_index.CombinedGraphIndex([index1, index2])
1552
# Searching for a key which is actually not present at all should
1553
# eventually converge
1554
parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1555
self.assertEqual({key4: (key2, key3), key2: (key1,), key1: ()},
1557
self.assertEqual({key3}, missing_keys)
1559
def test__find_ancestors_empty_index(self):
1560
idx = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
1562
missing_keys = set()
1563
search_keys = idx._find_ancestors([(b'one',), (b'two',)], 0, parent_map,
1565
self.assertEqual(set(), search_keys)
1566
self.assertEqual({}, parent_map)
1567
self.assertEqual({(b'one',), (b'two',)}, missing_keys)
1570
class TestInMemoryGraphIndex(tests.TestCaseWithMemoryTransport):
1572
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
1573
result = _mod_index.InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1574
result.add_nodes(nodes)
1577
def test_add_nodes_no_refs(self):
1578
index = self.make_index(0)
1579
index.add_nodes([((b'name', ), b'data')])
1580
index.add_nodes([((b'name2', ), b''), ((b'name3', ), b'')])
1582
(index, (b'name', ), b'data'),
1583
(index, (b'name2', ), b''),
1584
(index, (b'name3', ), b''),
1585
}, set(index.iter_all_entries()))
1587
def test_add_nodes(self):
1588
index = self.make_index(1)
1589
index.add_nodes([((b'name', ), b'data', ([],))])
1590
index.add_nodes([((b'name2', ), b'', ([],)), ((b'name3', ), b'', ([(b'r', )],))])
1592
(index, (b'name', ), b'data', ((),)),
1593
(index, (b'name2', ), b'', ((),)),
1594
(index, (b'name3', ), b'', (((b'r', ), ), )),
1595
}, set(index.iter_all_entries()))
1597
def test_iter_all_entries_empty(self):
1598
index = self.make_index()
1599
self.assertEqual([], list(index.iter_all_entries()))
1601
def test_iter_all_entries_simple(self):
1602
index = self.make_index(nodes=[((b'name', ), b'data')])
1603
self.assertEqual([(index, (b'name', ), b'data')],
1604
list(index.iter_all_entries()))
1606
def test_iter_all_entries_references(self):
1607
index = self.make_index(1, nodes=[
1608
((b'name', ), b'data', ([(b'ref', )], )),
1609
((b'ref', ), b'refdata', ([], ))])
1610
self.assertEqual({(index, (b'name', ), b'data', (((b'ref', ),),)),
1611
(index, (b'ref', ), b'refdata', ((), ))},
1612
set(index.iter_all_entries()))
1614
def test_iteration_absent_skipped(self):
1615
index = self.make_index(1, nodes=[
1616
((b'name', ), b'data', ([(b'ref', )], ))])
1617
self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),))},
1618
set(index.iter_all_entries()))
1619
self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),))},
1620
set(index.iter_entries([(b'name', )])))
1621
self.assertEqual([], list(index.iter_entries([(b'ref', )])))
1623
def test_iter_all_keys(self):
1624
index = self.make_index(1, nodes=[
1625
((b'name', ), b'data', ([(b'ref', )], )),
1626
((b'ref', ), b'refdata', ([], ))])
1627
self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),)),
1628
(index, (b'ref', ), b'refdata', ((), ))},
1629
set(index.iter_entries([(b'name', ), (b'ref', )])))
1631
def test_iter_key_prefix_1_key_element_no_refs(self):
1632
index = self.make_index( nodes=[
1633
((b'name', ), b'data'),
1634
((b'ref', ), b'refdata')])
1635
self.assertEqual({(index, (b'name', ), b'data'),
1636
(index, (b'ref', ), b'refdata')},
1637
set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
1639
def test_iter_key_prefix_1_key_element_refs(self):
1640
index = self.make_index(1, nodes=[
1641
((b'name', ), b'data', ([(b'ref', )], )),
1642
((b'ref', ), b'refdata', ([], ))])
1643
self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),)),
1644
(index, (b'ref', ), b'refdata', ((), ))},
1645
set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
1647
def test_iter_key_prefix_2_key_element_no_refs(self):
1648
index = self.make_index(key_elements=2, nodes=[
1649
((b'name', b'fin1'), b'data'),
1650
((b'name', b'fin2'), b'beta'),
1651
((b'ref', b'erence'), b'refdata')])
1652
self.assertEqual({(index, (b'name', b'fin1'), b'data'),
1653
(index, (b'ref', b'erence'), b'refdata')},
1654
set(index.iter_entries_prefix([(b'name', b'fin1'), (b'ref', b'erence')])))
1655
self.assertEqual({(index, (b'name', b'fin1'), b'data'),
1656
(index, (b'name', b'fin2'), b'beta')},
1657
set(index.iter_entries_prefix([(b'name', None)])))
1659
def test_iter_key_prefix_2_key_element_refs(self):
1660
index = self.make_index(1, key_elements=2, nodes=[
1661
((b'name', b'fin1'), b'data', ([(b'ref', b'erence')], )),
1662
((b'name', b'fin2'), b'beta', ([], )),
1663
((b'ref', b'erence'), b'refdata', ([], ))])
1664
self.assertEqual({(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
1665
(index, (b'ref', b'erence'), b'refdata', ((), ))},
1666
set(index.iter_entries_prefix([(b'name', b'fin1'), (b'ref', b'erence')])))
1667
self.assertEqual({(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
1668
(index, (b'name', b'fin2'), b'beta', ((), ))},
1669
set(index.iter_entries_prefix([(b'name', None)])))
1671
def test_iter_nothing_empty(self):
1672
index = self.make_index()
1673
self.assertEqual([], list(index.iter_entries([])))
1675
def test_iter_missing_entry_empty(self):
1676
index = self.make_index()
1677
self.assertEqual([], list(index.iter_entries([b'a'])))
1679
def test_key_count_empty(self):
1680
index = self.make_index()
1681
self.assertEqual(0, index.key_count())
1683
def test_key_count_one(self):
1684
index = self.make_index(nodes=[((b'name', ), b'')])
1685
self.assertEqual(1, index.key_count())
1687
def test_key_count_two(self):
1688
index = self.make_index(nodes=[((b'name', ), b''), ((b'foo', ), b'')])
1689
self.assertEqual(2, index.key_count())
1691
def test_validate_empty(self):
1692
index = self.make_index()
1695
def test_validate_no_refs_content(self):
1696
index = self.make_index(nodes=[((b'key', ), b'value')])
1700
class TestGraphIndexPrefixAdapter(tests.TestCaseWithMemoryTransport):
1702
def make_index(self, ref_lists=1, key_elements=2, nodes=[],
1703
add_callback=False):
1704
result = _mod_index.InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1705
result.add_nodes(nodes)
1707
add_nodes_callback = result.add_nodes
1709
add_nodes_callback = None
1710
adapter = _mod_index.GraphIndexPrefixAdapter(
1711
result, (b'prefix', ), key_elements - 1,
1712
add_nodes_callback=add_nodes_callback)
1713
return result, adapter
1715
def test_add_node(self):
1716
index, adapter = self.make_index(add_callback=True)
1717
adapter.add_node((b'key',), b'value', (((b'ref',),),))
1718
self.assertEqual({(index, (b'prefix', b'key'), b'value',
1719
(((b'prefix', b'ref'),),))},
1720
set(index.iter_all_entries()))
1722
def test_add_nodes(self):
1723
index, adapter = self.make_index(add_callback=True)
1725
((b'key',), b'value', (((b'ref',),),)),
1726
((b'key2',), b'value2', ((),)),
1729
(index, (b'prefix', b'key2'), b'value2', ((),)),
1730
(index, (b'prefix', b'key'), b'value', (((b'prefix', b'ref'),),))
1732
set(index.iter_all_entries()))
1734
def test_construct(self):
1735
idx = _mod_index.InMemoryGraphIndex()
1736
adapter = _mod_index.GraphIndexPrefixAdapter(idx, (b'prefix', ), 1)
1738
def test_construct_with_callback(self):
1739
idx = _mod_index.InMemoryGraphIndex()
1740
adapter = _mod_index.GraphIndexPrefixAdapter(idx, (b'prefix', ), 1,
1743
def test_iter_all_entries_cross_prefix_map_errors(self):
1744
index, adapter = self.make_index(nodes=[
1745
((b'prefix', b'key1'), b'data1', (((b'prefixaltered', b'key2'),),))])
1746
self.assertRaises(_mod_index.BadIndexData, list, adapter.iter_all_entries())
1748
def test_iter_all_entries(self):
1749
index, adapter = self.make_index(nodes=[
1750
((b'notprefix', b'key1'), b'data', ((), )),
1751
((b'prefix', b'key1'), b'data1', ((), )),
1752
((b'prefix', b'key2'), b'data2', (((b'prefix', b'key1'),),))])
1753
self.assertEqual({(index, (b'key1', ), b'data1', ((),)),
1754
(index, (b'key2', ), b'data2', (((b'key1',),),))},
1755
set(adapter.iter_all_entries()))
1757
def test_iter_entries(self):
1758
index, adapter = self.make_index(nodes=[
1759
((b'notprefix', b'key1'), b'data', ((), )),
1760
((b'prefix', b'key1'), b'data1', ((), )),
1761
((b'prefix', b'key2'), b'data2', (((b'prefix', b'key1'),),))])
1762
# ask for many - get all
1763
self.assertEqual({(index, (b'key1', ), b'data1', ((),)),
1764
(index, (b'key2', ), b'data2', (((b'key1', ),),))},
1765
set(adapter.iter_entries([(b'key1', ), (b'key2', )])))
1766
# ask for one, get one
1767
self.assertEqual({(index, (b'key1', ), b'data1', ((),))},
1768
set(adapter.iter_entries([(b'key1', )])))
1769
# ask for missing, get none
1770
self.assertEqual(set(),
1771
set(adapter.iter_entries([(b'key3', )])))
1773
def test_iter_entries_prefix(self):
1774
index, adapter = self.make_index(key_elements=3, nodes=[
1775
((b'notprefix', b'foo', b'key1'), b'data', ((), )),
1776
((b'prefix', b'prefix2', b'key1'), b'data1', ((), )),
1777
((b'prefix', b'prefix2', b'key2'), b'data2', (((b'prefix', b'prefix2', b'key1'),),))])
1778
# ask for a prefix, get the results for just that prefix, adjusted.
1779
self.assertEqual({(index, (b'prefix2', b'key1', ), b'data1', ((),)),
1780
(index, (b'prefix2', b'key2', ), b'data2', (((b'prefix2', b'key1', ),),))},
1781
set(adapter.iter_entries_prefix([(b'prefix2', None)])))
1783
def test_key_count_no_matching_keys(self):
1784
index, adapter = self.make_index(nodes=[
1785
((b'notprefix', b'key1'), b'data', ((), ))])
1786
self.assertEqual(0, adapter.key_count())
1788
def test_key_count_some_keys(self):
1789
index, adapter = self.make_index(nodes=[
1790
((b'notprefix', b'key1'), b'data', ((), )),
1791
((b'prefix', b'key1'), b'data1', ((), )),
1792
((b'prefix', b'key2'), b'data2', (((b'prefix', b'key1'),),))])
1793
self.assertEqual(2, adapter.key_count())
1795
def test_validate(self):
1796
index, adapter = self.make_index()
1799
calls.append('called')
1800
index.validate = validate
1802
self.assertEqual(['called'], calls)
added
removed
breezy/tests/test_index.py
