1
# Copyright (C) 2007, 2009 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
"""Tests for indices."""
19
from bzrlib import errors
20
from bzrlib.index import *
21
from bzrlib.tests import TestCaseWithMemoryTransport
22
from bzrlib.transport import get_transport
25
class TestGraphIndexBuilder(TestCaseWithMemoryTransport):
27
def test_build_index_empty(self):
28
builder = GraphIndexBuilder()
29
stream = builder.finish()
30
contents = stream.read()
32
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=0\n\n",
35
def test_build_index_empty_two_element_keys(self):
36
builder = GraphIndexBuilder(key_elements=2)
37
stream = builder.finish()
38
contents = stream.read()
40
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=0\n\n",
43
def test_build_index_one_reference_list_empty(self):
44
builder = GraphIndexBuilder(reference_lists=1)
45
stream = builder.finish()
46
contents = stream.read()
48
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=0\n\n",
51
def test_build_index_two_reference_list_empty(self):
52
builder = GraphIndexBuilder(reference_lists=2)
53
stream = builder.finish()
54
contents = stream.read()
56
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=0\n\n",
59
def test_build_index_one_node_no_refs(self):
60
builder = GraphIndexBuilder()
61
builder.add_node(('akey', ), 'data')
62
stream = builder.finish()
63
contents = stream.read()
65
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
66
"akey\x00\x00\x00data\n\n", contents)
68
def test_build_index_one_node_no_refs_accepts_empty_reflist(self):
69
builder = GraphIndexBuilder()
70
builder.add_node(('akey', ), 'data', ())
71
stream = builder.finish()
72
contents = stream.read()
74
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
75
"akey\x00\x00\x00data\n\n", contents)
77
def test_build_index_one_node_2_element_keys(self):
78
# multipart keys are separated by \x00 - because they are fixed length,
79
# not variable this does not cause any issues, and seems clearer to the
81
builder = GraphIndexBuilder(key_elements=2)
82
builder.add_node(('akey', 'secondpart'), 'data')
83
stream = builder.finish()
84
contents = stream.read()
86
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=1\n"
87
"akey\x00secondpart\x00\x00\x00data\n\n", contents)
89
def test_add_node_empty_value(self):
90
builder = GraphIndexBuilder()
91
builder.add_node(('akey', ), '')
92
stream = builder.finish()
93
contents = stream.read()
95
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
96
"akey\x00\x00\x00\n\n", contents)
98
def test_build_index_nodes_sorted(self):
99
# the highest sorted node comes first.
100
builder = GraphIndexBuilder()
101
# use three to have a good chance of glitching dictionary hash
102
# lookups etc. Insert in randomish order that is not correct
103
# and not the reverse of the correct order.
104
builder.add_node(('2002', ), 'data')
105
builder.add_node(('2000', ), 'data')
106
builder.add_node(('2001', ), 'data')
107
stream = builder.finish()
108
contents = stream.read()
110
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=3\n"
111
"2000\x00\x00\x00data\n"
112
"2001\x00\x00\x00data\n"
113
"2002\x00\x00\x00data\n"
116
def test_build_index_2_element_key_nodes_sorted(self):
117
# multiple element keys are sorted first-key, second-key.
118
builder = GraphIndexBuilder(key_elements=2)
119
# use three values of each key element, to have a good chance of
120
# glitching dictionary hash lookups etc. Insert in randomish order that
121
# is not correct and not the reverse of the correct order.
122
builder.add_node(('2002', '2002'), 'data')
123
builder.add_node(('2002', '2000'), 'data')
124
builder.add_node(('2002', '2001'), 'data')
125
builder.add_node(('2000', '2002'), 'data')
126
builder.add_node(('2000', '2000'), 'data')
127
builder.add_node(('2000', '2001'), 'data')
128
builder.add_node(('2001', '2002'), 'data')
129
builder.add_node(('2001', '2000'), 'data')
130
builder.add_node(('2001', '2001'), 'data')
131
stream = builder.finish()
132
contents = stream.read()
134
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=9\n"
135
"2000\x002000\x00\x00\x00data\n"
136
"2000\x002001\x00\x00\x00data\n"
137
"2000\x002002\x00\x00\x00data\n"
138
"2001\x002000\x00\x00\x00data\n"
139
"2001\x002001\x00\x00\x00data\n"
140
"2001\x002002\x00\x00\x00data\n"
141
"2002\x002000\x00\x00\x00data\n"
142
"2002\x002001\x00\x00\x00data\n"
143
"2002\x002002\x00\x00\x00data\n"
146
def test_build_index_reference_lists_are_included_one(self):
147
builder = GraphIndexBuilder(reference_lists=1)
148
builder.add_node(('key', ), 'data', ([], ))
149
stream = builder.finish()
150
contents = stream.read()
152
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
153
"key\x00\x00\x00data\n"
156
def test_build_index_reference_lists_with_2_element_keys(self):
157
builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
158
builder.add_node(('key', 'key2'), 'data', ([], ))
159
stream = builder.finish()
160
contents = stream.read()
162
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=2\nlen=1\n"
163
"key\x00key2\x00\x00\x00data\n"
166
def test_build_index_reference_lists_are_included_two(self):
167
builder = GraphIndexBuilder(reference_lists=2)
168
builder.add_node(('key', ), 'data', ([], []))
169
stream = builder.finish()
170
contents = stream.read()
172
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
173
"key\x00\x00\t\x00data\n"
176
def test_node_references_are_byte_offsets(self):
177
builder = GraphIndexBuilder(reference_lists=1)
178
builder.add_node(('reference', ), 'data', ([], ))
179
builder.add_node(('key', ), 'data', ([('reference', )], ))
180
stream = builder.finish()
181
contents = stream.read()
183
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=2\n"
184
"key\x00\x0072\x00data\n"
185
"reference\x00\x00\x00data\n"
188
def test_node_references_are_cr_delimited(self):
189
builder = GraphIndexBuilder(reference_lists=1)
190
builder.add_node(('reference', ), 'data', ([], ))
191
builder.add_node(('reference2', ), 'data', ([], ))
192
builder.add_node(('key', ), 'data', ([('reference', ), ('reference2', )], ))
193
stream = builder.finish()
194
contents = stream.read()
196
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=3\n"
197
"key\x00\x00077\r094\x00data\n"
198
"reference\x00\x00\x00data\n"
199
"reference2\x00\x00\x00data\n"
202
def test_multiple_reference_lists_are_tab_delimited(self):
203
builder = GraphIndexBuilder(reference_lists=2)
204
builder.add_node(('keference', ), 'data', ([], []))
205
builder.add_node(('rey', ), 'data', ([('keference', )], [('keference', )]))
206
stream = builder.finish()
207
contents = stream.read()
209
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=2\n"
210
"keference\x00\x00\t\x00data\n"
211
"rey\x00\x0059\t59\x00data\n"
214
def test_add_node_referencing_missing_key_makes_absent(self):
215
builder = GraphIndexBuilder(reference_lists=1)
216
builder.add_node(('rey', ), 'data', ([('beference', ), ('aeference2', )], ))
217
stream = builder.finish()
218
contents = stream.read()
220
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
221
"aeference2\x00a\x00\x00\n"
222
"beference\x00a\x00\x00\n"
223
"rey\x00\x00074\r059\x00data\n"
226
def test_node_references_three_digits(self):
227
# test the node digit expands as needed.
228
builder = GraphIndexBuilder(reference_lists=1)
229
references = [(str(val), ) for val in reversed(range(9))]
230
builder.add_node(('2-key', ), '', (references, ))
231
stream = builder.finish()
232
contents = stream.read()
234
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
238
"2-key\x00\x00151\r145\r139\r133\r127\r121\r071\r065\r059\x00\n"
247
def test_absent_has_no_reference_overhead(self):
248
# the offsets after an absent record should be correct when there are
249
# >1 reference lists.
250
builder = GraphIndexBuilder(reference_lists=2)
251
builder.add_node(('parent', ), '', ([('aail', ), ('zther', )], []))
252
stream = builder.finish()
253
contents = stream.read()
255
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
256
"aail\x00a\x00\x00\n"
257
"parent\x00\x0059\r84\t\x00\n"
258
"zther\x00a\x00\x00\n"
261
def test_add_node_bad_key(self):
262
builder = GraphIndexBuilder()
263
for bad_char in '\t\n\x0b\x0c\r\x00 ':
264
self.assertRaises(errors.BadIndexKey, builder.add_node,
265
('a%skey' % bad_char, ), 'data')
266
self.assertRaises(errors.BadIndexKey, builder.add_node,
268
self.assertRaises(errors.BadIndexKey, builder.add_node,
269
'not-a-tuple', 'data')
271
self.assertRaises(errors.BadIndexKey, builder.add_node,
274
self.assertRaises(errors.BadIndexKey, builder.add_node,
275
('primary', 'secondary'), 'data')
276
# secondary key elements get checked too:
277
builder = GraphIndexBuilder(key_elements=2)
278
for bad_char in '\t\n\x0b\x0c\r\x00 ':
279
self.assertRaises(errors.BadIndexKey, builder.add_node,
280
('prefix', 'a%skey' % bad_char), 'data')
282
def test_add_node_bad_data(self):
283
builder = GraphIndexBuilder()
284
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
286
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
289
def test_add_node_bad_mismatched_ref_lists_length(self):
290
builder = GraphIndexBuilder()
291
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
293
builder = GraphIndexBuilder(reference_lists=1)
294
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
296
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
298
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
300
builder = GraphIndexBuilder(reference_lists=2)
301
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
303
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
305
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
306
'data aa', ([], [], []))
308
def test_add_node_bad_key_in_reference_lists(self):
309
# first list, first key - trivial
310
builder = GraphIndexBuilder(reference_lists=1)
311
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
312
'data aa', ([('a key', )], ))
313
# references keys must be tuples too
314
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
315
'data aa', (['not-a-tuple'], ))
317
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
320
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
321
'data aa', ([('primary', 'secondary')], ))
322
# need to check more than the first key in the list
323
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
324
'data aa', ([('agoodkey', ), ('that is a bad key', )], ))
325
# and if there is more than one list it should be getting checked
327
builder = GraphIndexBuilder(reference_lists=2)
328
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
329
'data aa', ([], ['a bad key']))
331
def test_add_duplicate_key(self):
332
builder = GraphIndexBuilder()
333
builder.add_node(('key', ), 'data')
334
self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node, ('key', ),
337
def test_add_duplicate_key_2_elements(self):
338
builder = GraphIndexBuilder(key_elements=2)
339
builder.add_node(('key', 'key'), 'data')
340
self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node,
341
('key', 'key'), 'data')
343
def test_add_key_after_referencing_key(self):
344
builder = GraphIndexBuilder(reference_lists=1)
345
builder.add_node(('key', ), 'data', ([('reference', )], ))
346
builder.add_node(('reference', ), 'data', ([],))
348
def test_add_key_after_referencing_key_2_elements(self):
349
builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
350
builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
351
builder.add_node(('reference', 'tokey'), 'data', ([],))
353
def test_set_optimize(self):
354
builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
355
builder.set_optimize(for_size=True)
356
self.assertTrue(builder._optimize_for_size)
357
builder.set_optimize(for_size=False)
358
self.assertFalse(builder._optimize_for_size)
361
class TestGraphIndex(TestCaseWithMemoryTransport):
363
def make_key(self, number):
364
return (str(number) + 'X'*100,)
366
def make_value(self, number):
367
return str(number) + 'Y'*100
369
def make_nodes(self, count=64):
370
# generate a big enough index that we only read some of it on a typical
373
for counter in range(count):
374
nodes.append((self.make_key(counter), self.make_value(counter), ()))
377
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
378
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
379
for key, value, references in nodes:
380
builder.add_node(key, value, references)
381
stream = builder.finish()
382
trans = get_transport('trace+' + self.get_url())
383
size = trans.put_file('index', stream)
384
return GraphIndex(trans, 'index', size)
386
def test_clear_cache(self):
387
index = self.make_index()
388
# For now, we just want to make sure the api is available. As this is
389
# old code, we don't really worry if it *does* anything.
392
def test_open_bad_index_no_error(self):
393
trans = self.get_transport()
394
trans.put_bytes('name', "not an index\n")
395
index = GraphIndex(trans, 'name', 13)
397
def test_open_sets_parsed_map_empty(self):
398
index = self.make_index()
399
self.assertEqual([], index._parsed_byte_map)
400
self.assertEqual([], index._parsed_key_map)
402
def test_key_count_buffers(self):
403
index = self.make_index(nodes=self.make_nodes(2))
404
# reset the transport log
405
del index._transport._activity[:]
406
self.assertEqual(2, index.key_count())
407
# We should have requested reading the header bytes
409
('readv', 'index', [(0, 200)], True, index._size),
411
index._transport._activity)
412
# And that should have been enough to trigger reading the whole index
414
self.assertIsNot(None, index._nodes)
416
def test_lookup_key_via_location_buffers(self):
417
index = self.make_index()
418
# reset the transport log
419
del index._transport._activity[:]
420
# do a _lookup_keys_via_location call for the middle of the file, which
421
# is what bisection uses.
422
result = index._lookup_keys_via_location(
423
[(index._size // 2, ('missing', ))])
424
# this should have asked for a readv request, with adjust_for_latency,
425
# and two regions: the header, and half-way into the file.
427
('readv', 'index', [(30, 30), (0, 200)], True, 60),
429
index._transport._activity)
430
# and the result should be that the key cannot be present, because this
431
# is a trivial index.
432
self.assertEqual([((index._size // 2, ('missing', )), False)],
434
# And this should have caused the file to be fully buffered
435
self.assertIsNot(None, index._nodes)
436
self.assertEqual([], index._parsed_byte_map)
438
def test_first_lookup_key_via_location(self):
439
# We need enough data so that the _HEADER_READV doesn't consume the
440
# whole file. We always read 800 bytes for every key, and the local
441
# transport natural expansion is 4096 bytes. So we have to have >8192
442
# bytes or we will trigger "buffer_all".
443
# We also want the 'missing' key to fall within the range that *did*
446
index = self.make_index(nodes=self.make_nodes(64))
447
# reset the transport log
448
del index._transport._activity[:]
449
# do a _lookup_keys_via_location call for the middle of the file, which
450
# is what bisection uses.
451
start_lookup = index._size // 2
452
result = index._lookup_keys_via_location(
453
[(start_lookup, ('40missing', ))])
454
# this should have asked for a readv request, with adjust_for_latency,
455
# and two regions: the header, and half-way into the file.
458
[(start_lookup, 800), (0, 200)], True, index._size),
460
index._transport._activity)
461
# and the result should be that the key cannot be present, because this
462
# is a trivial index.
463
self.assertEqual([((start_lookup, ('40missing', )), False)],
465
# And this should not have caused the file to be fully buffered
466
self.assertIs(None, index._nodes)
467
# And the regions of the file that have been parsed should be in the
468
# parsed_byte_map and the parsed_key_map
469
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
470
self.assertEqual([(None, self.make_key(26)),
471
(self.make_key(31), self.make_key(48))],
472
index._parsed_key_map)
474
def test_parsing_non_adjacent_data_trims(self):
475
index = self.make_index(nodes=self.make_nodes(64))
476
result = index._lookup_keys_via_location(
477
[(index._size // 2, ('40', ))])
478
# and the result should be that the key cannot be present, because key is
479
# in the middle of the observed data from a 4K read - the smallest transport
480
# will do today with this api.
481
self.assertEqual([((index._size // 2, ('40', )), False)],
483
# and we should have a parse map that includes the header and the
484
# region that was parsed after trimming.
485
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
486
self.assertEqual([(None, self.make_key(26)),
487
(self.make_key(31), self.make_key(48))],
488
index._parsed_key_map)
490
def test_parsing_data_handles_parsed_contained_regions(self):
491
# the following patten creates a parsed region that is wholly within a
492
# single result from the readv layer:
493
# .... single-read (readv-minimum-size) ...
494
# which then trims the start and end so the parsed size is < readv
496
# then a dual lookup (or a reference lookup for that matter) which
497
# abuts or overlaps the parsed region on both sides will need to
498
# discard the data in the middle, but parse the end as well.
500
# we test this by doing a single lookup to seed the data, then
501
# a lookup for two keys that are present, and adjacent -
502
# we except both to be found, and the parsed byte map to include the
503
# locations of both keys.
504
index = self.make_index(nodes=self.make_nodes(128))
505
result = index._lookup_keys_via_location(
506
[(index._size // 2, ('40', ))])
507
# and we should have a parse map that includes the header and the
508
# region that was parsed after trimming.
509
self.assertEqual([(0, 4045), (11759, 15707)], index._parsed_byte_map)
510
self.assertEqual([(None, self.make_key(116)),
511
(self.make_key(35), self.make_key(51))],
512
index._parsed_key_map)
513
# now ask for two keys, right before and after the parsed region
514
result = index._lookup_keys_via_location(
515
[(11450, self.make_key(34)), (15707, self.make_key(52))])
517
((11450, self.make_key(34)),
518
(index, self.make_key(34), self.make_value(34))),
519
((15707, self.make_key(52)),
520
(index, self.make_key(52), self.make_value(52))),
523
self.assertEqual([(0, 4045), (9889, 17993)], index._parsed_byte_map)
525
def test_lookup_missing_key_answers_without_io_when_map_permits(self):
526
# generate a big enough index that we only read some of it on a typical
528
index = self.make_index(nodes=self.make_nodes(64))
529
# lookup the keys in the middle of the file
530
result =index._lookup_keys_via_location(
531
[(index._size // 2, ('40', ))])
532
# check the parse map, this determines the test validity
533
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
534
self.assertEqual([(None, self.make_key(26)),
535
(self.make_key(31), self.make_key(48))],
536
index._parsed_key_map)
537
# reset the transport log
538
del index._transport._activity[:]
539
# now looking up a key in the portion of the file already parsed should
540
# not create a new transport request, and should return False (cannot
541
# be in the index) - even when the byte location we ask for is outside
543
result = index._lookup_keys_via_location(
545
self.assertEqual([((4000, ('40', )), False)],
547
self.assertEqual([], index._transport._activity)
549
def test_lookup_present_key_answers_without_io_when_map_permits(self):
550
# generate a big enough index that we only read some of it on a typical
552
index = self.make_index(nodes=self.make_nodes(64))
553
# lookup the keys in the middle of the file
554
result =index._lookup_keys_via_location(
555
[(index._size // 2, ('40', ))])
556
# check the parse map, this determines the test validity
557
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
558
self.assertEqual([(None, self.make_key(26)),
559
(self.make_key(31), self.make_key(48))],
560
index._parsed_key_map)
561
# reset the transport log
562
del index._transport._activity[:]
563
# now looking up a key in the portion of the file already parsed should
564
# not create a new transport request, and should return False (cannot
565
# be in the index) - even when the byte location we ask for is outside
568
result = index._lookup_keys_via_location([(4000, self.make_key(40))])
570
[((4000, self.make_key(40)),
571
(index, self.make_key(40), self.make_value(40)))],
573
self.assertEqual([], index._transport._activity)
575
def test_lookup_key_below_probed_area(self):
576
# generate a big enough index that we only read some of it on a typical
578
index = self.make_index(nodes=self.make_nodes(64))
579
# ask for the key in the middle, but a key that is located in the
580
# unparsed region before the middle.
581
result =index._lookup_keys_via_location(
582
[(index._size // 2, ('30', ))])
583
# check the parse map, this determines the test validity
584
self.assertEqual([(0, 4008), (5046, 8996)], index._parsed_byte_map)
585
self.assertEqual([(None, self.make_key(26)),
586
(self.make_key(31), self.make_key(48))],
587
index._parsed_key_map)
588
self.assertEqual([((index._size // 2, ('30', )), -1)],
591
def test_lookup_key_above_probed_area(self):
592
# generate a big enough index that we only read some of it on a typical
594
index = self.make_index(nodes=self.make_nodes(64))
595
# ask for the key in the middle, but a key that is located in the
596
# unparsed region after the middle.
597
result =index._lookup_keys_via_location(
598
[(index._size // 2, ('50', ))])
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
self.assertEqual([((index._size // 2, ('50', )), +1)],
607
def test_lookup_key_resolves_references(self):
608
# generate a big enough index that we only read some of it on a typical
611
for counter in range(99):
612
nodes.append((self.make_key(counter), self.make_value(counter),
613
((self.make_key(counter + 20),),) ))
614
index = self.make_index(ref_lists=1, nodes=nodes)
615
# lookup a key in the middle that does not exist, so that when we can
616
# check that the referred-to-keys are not accessed automatically.
617
index_size = index._size
618
index_center = index_size // 2
619
result = index._lookup_keys_via_location(
620
[(index_center, ('40', ))])
621
# check the parse map - only the start and middle should have been
623
self.assertEqual([(0, 4027), (10198, 14028)], index._parsed_byte_map)
624
self.assertEqual([(None, self.make_key(17)),
625
(self.make_key(44), self.make_key(5))],
626
index._parsed_key_map)
627
# and check the transport activity likewise.
629
[('readv', 'index', [(index_center, 800), (0, 200)], True,
631
index._transport._activity)
632
# reset the transport log for testing the reference lookup
633
del index._transport._activity[:]
634
# now looking up a key in the portion of the file already parsed should
635
# only perform IO to resolve its key references.
636
result = index._lookup_keys_via_location([(11000, self.make_key(45))])
638
[((11000, self.make_key(45)),
639
(index, self.make_key(45), self.make_value(45),
640
((self.make_key(65),),)))],
642
self.assertEqual([('readv', 'index', [(15093, 800)], True, index_size)],
643
index._transport._activity)
645
def test_lookup_key_can_buffer_all(self):
647
for counter in range(64):
648
nodes.append((self.make_key(counter), self.make_value(counter),
649
((self.make_key(counter + 20),),) ))
650
index = self.make_index(ref_lists=1, nodes=nodes)
651
# lookup a key in the middle that does not exist, so that when we can
652
# check that the referred-to-keys are not accessed automatically.
653
index_size = index._size
654
index_center = index_size // 2
655
result = index._lookup_keys_via_location([(index_center, ('40', ))])
656
# check the parse map - only the start and middle should have been
658
self.assertEqual([(0, 3890), (6444, 10274)], index._parsed_byte_map)
659
self.assertEqual([(None, self.make_key(25)),
660
(self.make_key(37), self.make_key(52))],
661
index._parsed_key_map)
662
# and check the transport activity likewise.
664
[('readv', 'index', [(index_center, 800), (0, 200)], True,
666
index._transport._activity)
667
# reset the transport log for testing the reference lookup
668
del index._transport._activity[:]
669
# now looking up a key in the portion of the file already parsed should
670
# only perform IO to resolve its key references.
671
result = index._lookup_keys_via_location([(7000, self.make_key(40))])
673
[((7000, self.make_key(40)),
674
(index, self.make_key(40), self.make_value(40),
675
((self.make_key(60),),)))],
677
# Resolving the references would have required more data read, and we
678
# are already above the 50% threshold, so it triggered a _buffer_all
679
self.assertEqual([('get', 'index')], index._transport._activity)
681
def test_iter_all_entries_empty(self):
682
index = self.make_index()
683
self.assertEqual([], list(index.iter_all_entries()))
685
def test_iter_all_entries_simple(self):
686
index = self.make_index(nodes=[(('name', ), 'data', ())])
687
self.assertEqual([(index, ('name', ), 'data')],
688
list(index.iter_all_entries()))
690
def test_iter_all_entries_simple_2_elements(self):
691
index = self.make_index(key_elements=2,
692
nodes=[(('name', 'surname'), 'data', ())])
693
self.assertEqual([(index, ('name', 'surname'), 'data')],
694
list(index.iter_all_entries()))
696
def test_iter_all_entries_references_resolved(self):
697
index = self.make_index(1, nodes=[
698
(('name', ), 'data', ([('ref', )], )),
699
(('ref', ), 'refdata', ([], ))])
700
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
701
(index, ('ref', ), 'refdata', ((), ))]),
702
set(index.iter_all_entries()))
704
def test_iter_entries_buffers_once(self):
705
index = self.make_index(nodes=self.make_nodes(2))
706
# reset the transport log
707
del index._transport._activity[:]
708
self.assertEqual(set([(index, self.make_key(1), self.make_value(1))]),
709
set(index.iter_entries([self.make_key(1)])))
710
# We should have requested reading the header bytes
711
# But not needed any more than that because it would have triggered a
714
('readv', 'index', [(0, 200)], True, index._size),
716
index._transport._activity)
717
# And that should have been enough to trigger reading the whole index
719
self.assertIsNot(None, index._nodes)
721
def test_iter_entries_buffers_by_bytes_read(self):
722
index = self.make_index(nodes=self.make_nodes(64))
723
list(index.iter_entries([self.make_key(10)]))
724
# The first time through isn't enough to trigger a buffer all
725
self.assertIs(None, index._nodes)
726
self.assertEqual(4096, index._bytes_read)
727
# Grabbing a key in that same page won't trigger a buffer all, as we
728
# still haven't read 50% of the file
729
list(index.iter_entries([self.make_key(11)]))
730
self.assertIs(None, index._nodes)
731
self.assertEqual(4096, index._bytes_read)
732
# We haven't read more data, so reading outside the range won't trigger
733
# a buffer all right away
734
list(index.iter_entries([self.make_key(40)]))
735
self.assertIs(None, index._nodes)
736
self.assertEqual(8192, index._bytes_read)
737
# On the next pass, we will not trigger buffer all if the key is
738
# available without reading more
739
list(index.iter_entries([self.make_key(32)]))
740
self.assertIs(None, index._nodes)
741
# But if we *would* need to read more to resolve it, then we will
743
list(index.iter_entries([self.make_key(60)]))
744
self.assertIsNot(None, index._nodes)
746
def test_iter_entries_references_resolved(self):
747
index = self.make_index(1, nodes=[
748
(('name', ), 'data', ([('ref', ), ('ref', )], )),
749
(('ref', ), 'refdata', ([], ))])
750
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),('ref',)),)),
751
(index, ('ref', ), 'refdata', ((), ))]),
752
set(index.iter_entries([('name',), ('ref',)])))
754
def test_iter_entries_references_2_refs_resolved(self):
755
index = self.make_index(2, nodes=[
756
(('name', ), 'data', ([('ref', )], [('ref', )])),
757
(('ref', ), 'refdata', ([], []))])
758
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),), (('ref',),))),
759
(index, ('ref', ), 'refdata', ((), ()))]),
760
set(index.iter_entries([('name',), ('ref',)])))
762
def test_iteration_absent_skipped(self):
763
index = self.make_index(1, nodes=[
764
(('name', ), 'data', ([('ref', )], ))])
765
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
766
set(index.iter_all_entries()))
767
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
768
set(index.iter_entries([('name', )])))
769
self.assertEqual([], list(index.iter_entries([('ref', )])))
771
def test_iteration_absent_skipped_2_element_keys(self):
772
index = self.make_index(1, key_elements=2, nodes=[
773
(('name', 'fin'), 'data', ([('ref', 'erence')], ))])
774
self.assertEqual(set([(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
775
set(index.iter_all_entries()))
776
self.assertEqual(set([(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
777
set(index.iter_entries([('name', 'fin')])))
778
self.assertEqual([], list(index.iter_entries([('ref', 'erence')])))
780
def test_iter_all_keys(self):
781
index = self.make_index(1, nodes=[
782
(('name', ), 'data', ([('ref', )], )),
783
(('ref', ), 'refdata', ([], ))])
784
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
785
(index, ('ref', ), 'refdata', ((), ))]),
786
set(index.iter_entries([('name', ), ('ref', )])))
788
def test_iter_nothing_empty(self):
789
index = self.make_index()
790
self.assertEqual([], list(index.iter_entries([])))
792
def test_iter_missing_entry_empty(self):
793
index = self.make_index()
794
self.assertEqual([], list(index.iter_entries([('a', )])))
796
def test_iter_missing_entry_empty_no_size(self):
797
index = self.make_index()
798
index = GraphIndex(index._transport, 'index', None)
799
self.assertEqual([], list(index.iter_entries([('a', )])))
801
def test_iter_key_prefix_1_element_key_None(self):
802
index = self.make_index()
803
self.assertRaises(errors.BadIndexKey, list,
804
index.iter_entries_prefix([(None, )]))
806
def test_iter_key_prefix_wrong_length(self):
807
index = self.make_index()
808
self.assertRaises(errors.BadIndexKey, list,
809
index.iter_entries_prefix([('foo', None)]))
810
index = self.make_index(key_elements=2)
811
self.assertRaises(errors.BadIndexKey, list,
812
index.iter_entries_prefix([('foo', )]))
813
self.assertRaises(errors.BadIndexKey, list,
814
index.iter_entries_prefix([('foo', None, None)]))
816
def test_iter_key_prefix_1_key_element_no_refs(self):
817
index = self.make_index( nodes=[
818
(('name', ), 'data', ()),
819
(('ref', ), 'refdata', ())])
820
self.assertEqual(set([(index, ('name', ), 'data'),
821
(index, ('ref', ), 'refdata')]),
822
set(index.iter_entries_prefix([('name', ), ('ref', )])))
824
def test_iter_key_prefix_1_key_element_refs(self):
825
index = self.make_index(1, nodes=[
826
(('name', ), 'data', ([('ref', )], )),
827
(('ref', ), 'refdata', ([], ))])
828
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
829
(index, ('ref', ), 'refdata', ((), ))]),
830
set(index.iter_entries_prefix([('name', ), ('ref', )])))
832
def test_iter_key_prefix_2_key_element_no_refs(self):
833
index = self.make_index(key_elements=2, nodes=[
834
(('name', 'fin1'), 'data', ()),
835
(('name', 'fin2'), 'beta', ()),
836
(('ref', 'erence'), 'refdata', ())])
837
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
838
(index, ('ref', 'erence'), 'refdata')]),
839
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
840
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
841
(index, ('name', 'fin2'), 'beta')]),
842
set(index.iter_entries_prefix([('name', None)])))
844
def test_iter_key_prefix_2_key_element_refs(self):
845
index = self.make_index(1, key_elements=2, nodes=[
846
(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
847
(('name', 'fin2'), 'beta', ([], )),
848
(('ref', 'erence'), 'refdata', ([], ))])
849
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
850
(index, ('ref', 'erence'), 'refdata', ((), ))]),
851
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
852
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
853
(index, ('name', 'fin2'), 'beta', ((), ))]),
854
set(index.iter_entries_prefix([('name', None)])))
856
def test_key_count_empty(self):
857
index = self.make_index()
858
self.assertEqual(0, index.key_count())
860
def test_key_count_one(self):
861
index = self.make_index(nodes=[(('name', ), '', ())])
862
self.assertEqual(1, index.key_count())
864
def test_key_count_two(self):
865
index = self.make_index(nodes=[
866
(('name', ), '', ()), (('foo', ), '', ())])
867
self.assertEqual(2, index.key_count())
869
def test_read_and_parse_tracks_real_read_value(self):
870
index = self.make_index(nodes=self.make_nodes(10))
871
del index._transport._activity[:]
872
index._read_and_parse([(0, 200)])
874
('readv', 'index', [(0, 200)], True, index._size),
876
index._transport._activity)
877
# The readv expansion code will expand the initial request to 4096
878
# bytes, which is more than enough to read the entire index, and we
879
# will track the fact that we read that many bytes.
880
self.assertEqual(index._size, index._bytes_read)
882
def test_read_and_parse_triggers_buffer_all(self):
883
index = self.make_index(key_elements=2, nodes=[
884
(('name', 'fin1'), 'data', ()),
885
(('name', 'fin2'), 'beta', ()),
886
(('ref', 'erence'), 'refdata', ())])
887
self.assertTrue(index._size > 0)
888
self.assertIs(None, index._nodes)
889
index._read_and_parse([(0, index._size)])
890
self.assertIsNot(None, index._nodes)
892
def test_validate_bad_index_errors(self):
893
trans = self.get_transport()
894
trans.put_bytes('name', "not an index\n")
895
index = GraphIndex(trans, 'name', 13)
896
self.assertRaises(errors.BadIndexFormatSignature, index.validate)
898
def test_validate_bad_node_refs(self):
899
index = self.make_index(2)
900
trans = self.get_transport()
901
content = trans.get_bytes('index')
902
# change the options line to end with a rather than a parseable number
903
new_content = content[:-2] + 'a\n\n'
904
trans.put_bytes('index', new_content)
905
self.assertRaises(errors.BadIndexOptions, index.validate)
907
def test_validate_missing_end_line_empty(self):
908
index = self.make_index(2)
909
trans = self.get_transport()
910
content = trans.get_bytes('index')
911
# truncate the last byte
912
trans.put_bytes('index', content[:-1])
913
self.assertRaises(errors.BadIndexData, index.validate)
915
def test_validate_missing_end_line_nonempty(self):
916
index = self.make_index(2, nodes=[(('key', ), '', ([], []))])
917
trans = self.get_transport()
918
content = trans.get_bytes('index')
919
# truncate the last byte
920
trans.put_bytes('index', content[:-1])
921
self.assertRaises(errors.BadIndexData, index.validate)
923
def test_validate_empty(self):
924
index = self.make_index()
927
def test_validate_no_refs_content(self):
928
index = self.make_index(nodes=[(('key', ), 'value', ())])
931
# XXX: external_references tests are duplicated in test_btree_index. We
932
# probably should have per_graph_index tests...
933
def test_external_references_no_refs(self):
934
index = self.make_index(ref_lists=0, nodes=[])
935
self.assertRaises(ValueError, index.external_references, 0)
937
def test_external_references_no_results(self):
938
index = self.make_index(ref_lists=1, nodes=[
939
(('key',), 'value', ([],))])
940
self.assertEqual(set(), index.external_references(0))
942
def test_external_references_missing_ref(self):
943
missing_key = ('missing',)
944
index = self.make_index(ref_lists=1, nodes=[
945
(('key',), 'value', ([missing_key],))])
946
self.assertEqual(set([missing_key]), index.external_references(0))
948
def test_external_references_multiple_ref_lists(self):
949
missing_key = ('missing',)
950
index = self.make_index(ref_lists=2, nodes=[
951
(('key',), 'value', ([], [missing_key]))])
952
self.assertEqual(set([]), index.external_references(0))
953
self.assertEqual(set([missing_key]), index.external_references(1))
955
def test_external_references_two_records(self):
956
index = self.make_index(ref_lists=1, nodes=[
957
(('key-1',), 'value', ([('key-2',)],)),
958
(('key-2',), 'value', ([],)),
960
self.assertEqual(set([]), index.external_references(0))
962
def test__find_ancestors(self):
965
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
966
(key1, 'value', ([key2],)),
967
(key2, 'value', ([],)),
971
search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
972
self.assertEqual({key1: (key2,)}, parent_map)
973
self.assertEqual(set(), missing_keys)
974
self.assertEqual(set([key2]), search_keys)
975
search_keys = index._find_ancestors(search_keys, 0, parent_map,
977
self.assertEqual({key1: (key2,), key2: ()}, parent_map)
978
self.assertEqual(set(), missing_keys)
979
self.assertEqual(set(), search_keys)
981
def test__find_ancestors_w_missing(self):
985
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
986
(key1, 'value', ([key2],)),
987
(key2, 'value', ([],)),
991
search_keys = index._find_ancestors([key2, key3], 0, parent_map,
993
self.assertEqual({key2: ()}, parent_map)
994
self.assertEqual(set([key3]), missing_keys)
995
self.assertEqual(set(), search_keys)
997
def test__find_ancestors_dont_search_known(self):
1001
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1002
(key1, 'value', ([key2],)),
1003
(key2, 'value', ([key3],)),
1004
(key3, 'value', ([],)),
1006
# We already know about key2, so we won't try to search for key3
1007
parent_map = {key2: (key3,)}
1008
missing_keys = set()
1009
search_keys = index._find_ancestors([key1], 0, parent_map,
1011
self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1012
self.assertEqual(set(), missing_keys)
1013
self.assertEqual(set(), search_keys)
1015
def test_supports_unlimited_cache(self):
1016
builder = GraphIndexBuilder(0, key_elements=1)
1017
stream = builder.finish()
1018
trans = get_transport(self.get_url())
1019
size = trans.put_file('index', stream)
1020
# It doesn't matter what unlimited_cache does here, just that it can be
1022
index = GraphIndex(trans, 'index', size, unlimited_cache=True)
1025
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
1027
def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
1028
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
1029
for key, value, references in nodes:
1030
builder.add_node(key, value, references)
1031
stream = builder.finish()
1032
trans = self.get_transport()
1033
size = trans.put_file(name, stream)
1034
return GraphIndex(trans, name, size)
1036
def make_combined_index_with_missing(self, missing=['1', '2']):
1037
"""Create a CombinedGraphIndex which will have missing indexes.
1039
This creates a CGI which thinks it has 2 indexes, however they have
1040
been deleted. If CGI._reload_func() is called, then it will repopulate
1043
:param missing: The underlying indexes to delete
1044
:return: (CombinedGraphIndex, reload_counter)
1046
index1 = self.make_index('1', nodes=[(('1',), '', ())])
1047
index2 = self.make_index('2', nodes=[(('2',), '', ())])
1048
index3 = self.make_index('3', nodes=[
1052
# total_reloads, num_changed, num_unchanged
1053
reload_counter = [0, 0, 0]
1055
reload_counter[0] += 1
1056
new_indices = [index3]
1057
if index._indices == new_indices:
1058
reload_counter[2] += 1
1060
reload_counter[1] += 1
1061
index._indices[:] = new_indices
1063
index = CombinedGraphIndex([index1, index2], reload_func=reload)
1064
trans = self.get_transport()
1065
for fname in missing:
1067
return index, reload_counter
1069
def test_open_missing_index_no_error(self):
1070
trans = self.get_transport()
1071
index1 = GraphIndex(trans, 'missing', 100)
1072
index = CombinedGraphIndex([index1])
1074
def test_add_index(self):
1075
index = CombinedGraphIndex([])
1076
index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1077
index.insert_index(0, index1)
1078
self.assertEqual([(index1, ('key', ), '')], list(index.iter_all_entries()))
1080
def test_clear_cache(self):
1083
class ClearCacheProxy(object):
1085
def __init__(self, index):
1088
def __getattr__(self, name):
1089
return getattr(self._index)
1091
def clear_cache(self):
1092
log.append(self._index)
1093
return self._index.clear_cache()
1095
index = CombinedGraphIndex([])
1096
index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1097
index.insert_index(0, ClearCacheProxy(index1))
1098
index2 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
1099
index.insert_index(1, ClearCacheProxy(index2))
1100
# CombinedGraphIndex should call 'clear_cache()' on all children
1102
self.assertEqual(sorted([index1, index2]), sorted(log))
1104
def test_iter_all_entries_empty(self):
1105
index = CombinedGraphIndex([])
1106
self.assertEqual([], list(index.iter_all_entries()))
1108
def test_iter_all_entries_children_empty(self):
1109
index1 = self.make_index('name')
1110
index = CombinedGraphIndex([index1])
1111
self.assertEqual([], list(index.iter_all_entries()))
1113
def test_iter_all_entries_simple(self):
1114
index1 = self.make_index('name', nodes=[(('name', ), 'data', ())])
1115
index = CombinedGraphIndex([index1])
1116
self.assertEqual([(index1, ('name', ), 'data')],
1117
list(index.iter_all_entries()))
1119
def test_iter_all_entries_two_indices(self):
1120
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1121
index2 = self.make_index('name2', nodes=[(('2', ), '', ())])
1122
index = CombinedGraphIndex([index1, index2])
1123
self.assertEqual([(index1, ('name', ), 'data'),
1124
(index2, ('2', ), '')],
1125
list(index.iter_all_entries()))
1127
def test_iter_entries_two_indices_dup_key(self):
1128
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1129
index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
1130
index = CombinedGraphIndex([index1, index2])
1131
self.assertEqual([(index1, ('name', ), 'data')],
1132
list(index.iter_entries([('name', )])))
1134
def test_iter_all_entries_two_indices_dup_key(self):
1135
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
1136
index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
1137
index = CombinedGraphIndex([index1, index2])
1138
self.assertEqual([(index1, ('name', ), 'data')],
1139
list(index.iter_all_entries()))
1141
def test_iter_key_prefix_2_key_element_refs(self):
1142
index1 = self.make_index('1', 1, key_elements=2, nodes=[
1143
(('name', 'fin1'), 'data', ([('ref', 'erence')], ))])
1144
index2 = self.make_index('2', 1, key_elements=2, nodes=[
1145
(('name', 'fin2'), 'beta', ([], )),
1146
(('ref', 'erence'), 'refdata', ([], ))])
1147
index = CombinedGraphIndex([index1, index2])
1148
self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1149
(index2, ('ref', 'erence'), 'refdata', ((), ))]),
1150
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
1151
self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1152
(index2, ('name', 'fin2'), 'beta', ((), ))]),
1153
set(index.iter_entries_prefix([('name', None)])))
1155
def test_iter_nothing_empty(self):
1156
index = CombinedGraphIndex([])
1157
self.assertEqual([], list(index.iter_entries([])))
1159
def test_iter_nothing_children_empty(self):
1160
index1 = self.make_index('name')
1161
index = CombinedGraphIndex([index1])
1162
self.assertEqual([], list(index.iter_entries([])))
1164
def test_iter_all_keys(self):
1165
index1 = self.make_index('1', 1, nodes=[
1166
(('name', ), 'data', ([('ref', )], ))])
1167
index2 = self.make_index('2', 1, nodes=[
1168
(('ref', ), 'refdata', ((), ))])
1169
index = CombinedGraphIndex([index1, index2])
1170
self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),
1171
(index2, ('ref', ), 'refdata', ((), ))]),
1172
set(index.iter_entries([('name', ), ('ref', )])))
1174
def test_iter_all_keys_dup_entry(self):
1175
index1 = self.make_index('1', 1, nodes=[
1176
(('name', ), 'data', ([('ref', )], )),
1177
(('ref', ), 'refdata', ([], ))])
1178
index2 = self.make_index('2', 1, nodes=[
1179
(('ref', ), 'refdata', ([], ))])
1180
index = CombinedGraphIndex([index1, index2])
1181
self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),
1182
(index1, ('ref', ), 'refdata', ((), ))]),
1183
set(index.iter_entries([('name', ), ('ref', )])))
1185
def test_iter_missing_entry_empty(self):
1186
index = CombinedGraphIndex([])
1187
self.assertEqual([], list(index.iter_entries([('a', )])))
1189
def test_iter_missing_entry_one_index(self):
1190
index1 = self.make_index('1')
1191
index = CombinedGraphIndex([index1])
1192
self.assertEqual([], list(index.iter_entries([('a', )])))
1194
def test_iter_missing_entry_two_index(self):
1195
index1 = self.make_index('1')
1196
index2 = self.make_index('2')
1197
index = CombinedGraphIndex([index1, index2])
1198
self.assertEqual([], list(index.iter_entries([('a', )])))
1200
def test_iter_entry_present_one_index_only(self):
1201
index1 = self.make_index('1', nodes=[(('key', ), '', ())])
1202
index2 = self.make_index('2', nodes=[])
1203
index = CombinedGraphIndex([index1, index2])
1204
self.assertEqual([(index1, ('key', ), '')],
1205
list(index.iter_entries([('key', )])))
1206
# and in the other direction
1207
index = CombinedGraphIndex([index2, index1])
1208
self.assertEqual([(index1, ('key', ), '')],
1209
list(index.iter_entries([('key', )])))
1211
def test_key_count_empty(self):
1212
index1 = self.make_index('1', nodes=[])
1213
index2 = self.make_index('2', nodes=[])
1214
index = CombinedGraphIndex([index1, index2])
1215
self.assertEqual(0, index.key_count())
1217
def test_key_count_sums_index_keys(self):
1218
index1 = self.make_index('1', nodes=[
1221
index2 = self.make_index('2', nodes=[(('1',), '', ())])
1222
index = CombinedGraphIndex([index1, index2])
1223
self.assertEqual(3, index.key_count())
1225
def test_validate_bad_child_index_errors(self):
1226
trans = self.get_transport()
1227
trans.put_bytes('name', "not an index\n")
1228
index1 = GraphIndex(trans, 'name', 13)
1229
index = CombinedGraphIndex([index1])
1230
self.assertRaises(errors.BadIndexFormatSignature, index.validate)
1232
def test_validate_empty(self):
1233
index = CombinedGraphIndex([])
1236
def test_key_count_reloads(self):
1237
index, reload_counter = self.make_combined_index_with_missing()
1238
self.assertEqual(2, index.key_count())
1239
self.assertEqual([1, 1, 0], reload_counter)
1241
def test_key_count_no_reload(self):
1242
index, reload_counter = self.make_combined_index_with_missing()
1243
index._reload_func = None
1244
# Without a _reload_func we just raise the exception
1245
self.assertRaises(errors.NoSuchFile, index.key_count)
1247
def test_key_count_reloads_and_fails(self):
1248
# We have deleted all underlying indexes, so we will try to reload, but
1249
# still fail. This is mostly to test we don't get stuck in an infinite
1250
# loop trying to reload
1251
index, reload_counter = self.make_combined_index_with_missing(
1253
self.assertRaises(errors.NoSuchFile, index.key_count)
1254
self.assertEqual([2, 1, 1], reload_counter)
1256
def test_iter_entries_reloads(self):
1257
index, reload_counter = self.make_combined_index_with_missing()
1258
result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1259
index3 = index._indices[0]
1260
self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
1262
self.assertEqual([1, 1, 0], reload_counter)
1264
def test_iter_entries_reloads_midway(self):
1265
# The first index still looks present, so we get interrupted mid-way
1267
index, reload_counter = self.make_combined_index_with_missing(['2'])
1268
index1, index2 = index._indices
1269
result = list(index.iter_entries([('1',), ('2',), ('3',)]))
1270
index3 = index._indices[0]
1271
# We had already yielded '1', so we just go on to the next, we should
1272
# not yield '1' twice.
1273
self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1275
self.assertEqual([1, 1, 0], reload_counter)
1277
def test_iter_entries_no_reload(self):
1278
index, reload_counter = self.make_combined_index_with_missing()
1279
index._reload_func = None
1280
# Without a _reload_func we just raise the exception
1281
self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1283
def test_iter_entries_reloads_and_fails(self):
1284
index, reload_counter = self.make_combined_index_with_missing(
1286
self.assertListRaises(errors.NoSuchFile, index.iter_entries, [('3',)])
1287
self.assertEqual([2, 1, 1], reload_counter)
1289
def test_iter_all_entries_reloads(self):
1290
index, reload_counter = self.make_combined_index_with_missing()
1291
result = list(index.iter_all_entries())
1292
index3 = index._indices[0]
1293
self.assertEqual([(index3, ('1',), ''), (index3, ('2',), '')],
1295
self.assertEqual([1, 1, 0], reload_counter)
1297
def test_iter_all_entries_reloads_midway(self):
1298
index, reload_counter = self.make_combined_index_with_missing(['2'])
1299
index1, index2 = index._indices
1300
result = list(index.iter_all_entries())
1301
index3 = index._indices[0]
1302
# We had already yielded '1', so we just go on to the next, we should
1303
# not yield '1' twice.
1304
self.assertEqual([(index1, ('1',), ''), (index3, ('2',), '')],
1306
self.assertEqual([1, 1, 0], reload_counter)
1308
def test_iter_all_entries_no_reload(self):
1309
index, reload_counter = self.make_combined_index_with_missing()
1310
index._reload_func = None
1311
self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1313
def test_iter_all_entries_reloads_and_fails(self):
1314
index, reload_counter = self.make_combined_index_with_missing(
1316
self.assertListRaises(errors.NoSuchFile, index.iter_all_entries)
1318
def test_iter_entries_prefix_reloads(self):
1319
index, reload_counter = self.make_combined_index_with_missing()
1320
result = list(index.iter_entries_prefix([('1',)]))
1321
index3 = index._indices[0]
1322
self.assertEqual([(index3, ('1',), '')], result)
1323
self.assertEqual([1, 1, 0], reload_counter)
1325
def test_iter_entries_prefix_reloads_midway(self):
1326
index, reload_counter = self.make_combined_index_with_missing(['2'])
1327
index1, index2 = index._indices
1328
result = list(index.iter_entries_prefix([('1',)]))
1329
index3 = index._indices[0]
1330
# We had already yielded '1', so we just go on to the next, we should
1331
# not yield '1' twice.
1332
self.assertEqual([(index1, ('1',), '')], result)
1333
self.assertEqual([1, 1, 0], reload_counter)
1335
def test_iter_entries_prefix_no_reload(self):
1336
index, reload_counter = self.make_combined_index_with_missing()
1337
index._reload_func = None
1338
self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1341
def test_iter_entries_prefix_reloads_and_fails(self):
1342
index, reload_counter = self.make_combined_index_with_missing(
1344
self.assertListRaises(errors.NoSuchFile, index.iter_entries_prefix,
1347
def test_validate_reloads(self):
1348
index, reload_counter = self.make_combined_index_with_missing()
1350
self.assertEqual([1, 1, 0], reload_counter)
1352
def test_validate_reloads_midway(self):
1353
index, reload_counter = self.make_combined_index_with_missing(['2'])
1356
def test_validate_no_reload(self):
1357
index, reload_counter = self.make_combined_index_with_missing()
1358
index._reload_func = None
1359
self.assertRaises(errors.NoSuchFile, index.validate)
1361
def test_validate_reloads_and_fails(self):
1362
index, reload_counter = self.make_combined_index_with_missing(
1364
self.assertRaises(errors.NoSuchFile, index.validate)
1366
def test_find_ancestors_across_indexes(self):
1371
index1 = self.make_index('12', ref_lists=1, nodes=[
1372
(key1, 'value', ([],)),
1373
(key2, 'value', ([key1],)),
1375
index2 = self.make_index('34', ref_lists=1, nodes=[
1376
(key3, 'value', ([key2],)),
1377
(key4, 'value', ([key3],)),
1379
c_index = CombinedGraphIndex([index1, index2])
1380
parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1381
self.assertEqual({key1: ()}, parent_map)
1382
self.assertEqual(set(), missing_keys)
1383
# Now look for a key from index2 which requires us to find the key in
1384
# the second index, and then continue searching for parents in the
1386
parent_map, missing_keys = c_index.find_ancestry([key3], 0)
1387
self.assertEqual({key1: (), key2: (key1,), key3: (key2,)}, parent_map)
1388
self.assertEqual(set(), missing_keys)
1390
def test_find_ancestors_missing_keys(self):
1395
index1 = self.make_index('12', ref_lists=1, nodes=[
1396
(key1, 'value', ([],)),
1397
(key2, 'value', ([key1],)),
1399
index2 = self.make_index('34', ref_lists=1, nodes=[
1400
(key3, 'value', ([key2],)),
1402
c_index = CombinedGraphIndex([index1, index2])
1403
# Searching for a key which is actually not present at all should
1404
# eventually converge
1405
parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1406
self.assertEqual({}, parent_map)
1407
self.assertEqual(set([key4]), missing_keys)
1409
def test_find_ancestors_no_indexes(self):
1410
c_index = CombinedGraphIndex([])
1412
parent_map, missing_keys = c_index.find_ancestry([key1], 0)
1413
self.assertEqual({}, parent_map)
1414
self.assertEqual(set([key1]), missing_keys)
1416
def test_find_ancestors_ghost_parent(self):
1421
index1 = self.make_index('12', ref_lists=1, nodes=[
1422
(key1, 'value', ([],)),
1423
(key2, 'value', ([key1],)),
1425
index2 = self.make_index('34', ref_lists=1, nodes=[
1426
(key4, 'value', ([key2, key3],)),
1428
c_index = CombinedGraphIndex([index1, index2])
1429
# Searching for a key which is actually not present at all should
1430
# eventually converge
1431
parent_map, missing_keys = c_index.find_ancestry([key4], 0)
1432
self.assertEqual({key4: (key2, key3), key2: (key1,), key1: ()},
1434
self.assertEqual(set([key3]), missing_keys)
1436
def test__find_ancestors_empty_index(self):
1437
index = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
1439
missing_keys = set()
1440
search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
1442
self.assertEqual(set(), search_keys)
1443
self.assertEqual({}, parent_map)
1444
self.assertEqual(set([('one',), ('two',)]), missing_keys)
1447
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
1449
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
1450
result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1451
result.add_nodes(nodes)
1454
def test_add_nodes_no_refs(self):
1455
index = self.make_index(0)
1456
index.add_nodes([(('name', ), 'data')])
1457
index.add_nodes([(('name2', ), ''), (('name3', ), '')])
1458
self.assertEqual(set([
1459
(index, ('name', ), 'data'),
1460
(index, ('name2', ), ''),
1461
(index, ('name3', ), ''),
1462
]), set(index.iter_all_entries()))
1464
def test_add_nodes(self):
1465
index = self.make_index(1)
1466
index.add_nodes([(('name', ), 'data', ([],))])
1467
index.add_nodes([(('name2', ), '', ([],)), (('name3', ), '', ([('r', )],))])
1468
self.assertEqual(set([
1469
(index, ('name', ), 'data', ((),)),
1470
(index, ('name2', ), '', ((),)),
1471
(index, ('name3', ), '', ((('r', ), ), )),
1472
]), set(index.iter_all_entries()))
1474
def test_iter_all_entries_empty(self):
1475
index = self.make_index()
1476
self.assertEqual([], list(index.iter_all_entries()))
1478
def test_iter_all_entries_simple(self):
1479
index = self.make_index(nodes=[(('name', ), 'data')])
1480
self.assertEqual([(index, ('name', ), 'data')],
1481
list(index.iter_all_entries()))
1483
def test_iter_all_entries_references(self):
1484
index = self.make_index(1, nodes=[
1485
(('name', ), 'data', ([('ref', )], )),
1486
(('ref', ), 'refdata', ([], ))])
1487
self.assertEqual(set([(index, ('name', ), 'data', ((('ref', ),),)),
1488
(index, ('ref', ), 'refdata', ((), ))]),
1489
set(index.iter_all_entries()))
1491
def test_iteration_absent_skipped(self):
1492
index = self.make_index(1, nodes=[
1493
(('name', ), 'data', ([('ref', )], ))])
1494
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
1495
set(index.iter_all_entries()))
1496
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
1497
set(index.iter_entries([('name', )])))
1498
self.assertEqual([], list(index.iter_entries([('ref', )])))
1500
def test_iter_all_keys(self):
1501
index = self.make_index(1, nodes=[
1502
(('name', ), 'data', ([('ref', )], )),
1503
(('ref', ), 'refdata', ([], ))])
1504
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
1505
(index, ('ref', ), 'refdata', ((), ))]),
1506
set(index.iter_entries([('name', ), ('ref', )])))
1508
def test_iter_key_prefix_1_key_element_no_refs(self):
1509
index = self.make_index( nodes=[
1510
(('name', ), 'data'),
1511
(('ref', ), 'refdata')])
1512
self.assertEqual(set([(index, ('name', ), 'data'),
1513
(index, ('ref', ), 'refdata')]),
1514
set(index.iter_entries_prefix([('name', ), ('ref', )])))
1516
def test_iter_key_prefix_1_key_element_refs(self):
1517
index = self.make_index(1, nodes=[
1518
(('name', ), 'data', ([('ref', )], )),
1519
(('ref', ), 'refdata', ([], ))])
1520
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
1521
(index, ('ref', ), 'refdata', ((), ))]),
1522
set(index.iter_entries_prefix([('name', ), ('ref', )])))
1524
def test_iter_key_prefix_2_key_element_no_refs(self):
1525
index = self.make_index(key_elements=2, nodes=[
1526
(('name', 'fin1'), 'data'),
1527
(('name', 'fin2'), 'beta'),
1528
(('ref', 'erence'), 'refdata')])
1529
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
1530
(index, ('ref', 'erence'), 'refdata')]),
1531
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
1532
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
1533
(index, ('name', 'fin2'), 'beta')]),
1534
set(index.iter_entries_prefix([('name', None)])))
1536
def test_iter_key_prefix_2_key_element_refs(self):
1537
index = self.make_index(1, key_elements=2, nodes=[
1538
(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
1539
(('name', 'fin2'), 'beta', ([], )),
1540
(('ref', 'erence'), 'refdata', ([], ))])
1541
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1542
(index, ('ref', 'erence'), 'refdata', ((), ))]),
1543
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
1544
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1545
(index, ('name', 'fin2'), 'beta', ((), ))]),
1546
set(index.iter_entries_prefix([('name', None)])))
1548
def test_iter_nothing_empty(self):
1549
index = self.make_index()
1550
self.assertEqual([], list(index.iter_entries([])))
1552
def test_iter_missing_entry_empty(self):
1553
index = self.make_index()
1554
self.assertEqual([], list(index.iter_entries(['a'])))
1556
def test_key_count_empty(self):
1557
index = self.make_index()
1558
self.assertEqual(0, index.key_count())
1560
def test_key_count_one(self):
1561
index = self.make_index(nodes=[(('name', ), '')])
1562
self.assertEqual(1, index.key_count())
1564
def test_key_count_two(self):
1565
index = self.make_index(nodes=[(('name', ), ''), (('foo', ), '')])
1566
self.assertEqual(2, index.key_count())
1568
def test_validate_empty(self):
1569
index = self.make_index()
1572
def test_validate_no_refs_content(self):
1573
index = self.make_index(nodes=[(('key', ), 'value')])
1577
class TestGraphIndexPrefixAdapter(TestCaseWithMemoryTransport):
1579
def make_index(self, ref_lists=1, key_elements=2, nodes=[], add_callback=False):
1580
result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
1581
result.add_nodes(nodes)
1583
add_nodes_callback = result.add_nodes
1585
add_nodes_callback = None
1586
adapter = GraphIndexPrefixAdapter(result, ('prefix', ), key_elements - 1,
1587
add_nodes_callback=add_nodes_callback)
1588
return result, adapter
1590
def test_add_node(self):
1591
index, adapter = self.make_index(add_callback=True)
1592
adapter.add_node(('key',), 'value', ((('ref',),),))
1593
self.assertEqual(set([(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))]),
1594
set(index.iter_all_entries()))
1596
def test_add_nodes(self):
1597
index, adapter = self.make_index(add_callback=True)
1599
(('key',), 'value', ((('ref',),),)),
1600
(('key2',), 'value2', ((),)),
1602
self.assertEqual(set([
1603
(index, ('prefix', 'key2'), 'value2', ((),)),
1604
(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))
1606
set(index.iter_all_entries()))
1608
def test_construct(self):
1609
index = InMemoryGraphIndex()
1610
adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1)
1612
def test_construct_with_callback(self):
1613
index = InMemoryGraphIndex()
1614
adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1, index.add_nodes)
1616
def test_iter_all_entries_cross_prefix_map_errors(self):
1617
index, adapter = self.make_index(nodes=[
1618
(('prefix', 'key1'), 'data1', ((('prefixaltered', 'key2'),),))])
1619
self.assertRaises(errors.BadIndexData, list, adapter.iter_all_entries())
1621
def test_iter_all_entries(self):
1622
index, adapter = self.make_index(nodes=[
1623
(('notprefix', 'key1'), 'data', ((), )),
1624
(('prefix', 'key1'), 'data1', ((), )),
1625
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1626
self.assertEqual(set([(index, ('key1', ), 'data1', ((),)),
1627
(index, ('key2', ), 'data2', ((('key1',),),))]),
1628
set(adapter.iter_all_entries()))
1630
def test_iter_entries(self):
1631
index, adapter = self.make_index(nodes=[
1632
(('notprefix', 'key1'), 'data', ((), )),
1633
(('prefix', 'key1'), 'data1', ((), )),
1634
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1635
# ask for many - get all
1636
self.assertEqual(set([(index, ('key1', ), 'data1', ((),)),
1637
(index, ('key2', ), 'data2', ((('key1', ),),))]),
1638
set(adapter.iter_entries([('key1', ), ('key2', )])))
1639
# ask for one, get one
1640
self.assertEqual(set([(index, ('key1', ), 'data1', ((),))]),
1641
set(adapter.iter_entries([('key1', )])))
1642
# ask for missing, get none
1643
self.assertEqual(set(),
1644
set(adapter.iter_entries([('key3', )])))
1646
def test_iter_entries_prefix(self):
1647
index, adapter = self.make_index(key_elements=3, nodes=[
1648
(('notprefix', 'foo', 'key1'), 'data', ((), )),
1649
(('prefix', 'prefix2', 'key1'), 'data1', ((), )),
1650
(('prefix', 'prefix2', 'key2'), 'data2', ((('prefix', 'prefix2', 'key1'),),))])
1651
# ask for a prefix, get the results for just that prefix, adjusted.
1652
self.assertEqual(set([(index, ('prefix2', 'key1', ), 'data1', ((),)),
1653
(index, ('prefix2', 'key2', ), 'data2', ((('prefix2', 'key1', ),),))]),
1654
set(adapter.iter_entries_prefix([('prefix2', None)])))
1656
def test_key_count_no_matching_keys(self):
1657
index, adapter = self.make_index(nodes=[
1658
(('notprefix', 'key1'), 'data', ((), ))])
1659
self.assertEqual(0, adapter.key_count())
1661
def test_key_count_some_keys(self):
1662
index, adapter = self.make_index(nodes=[
1663
(('notprefix', 'key1'), 'data', ((), )),
1664
(('prefix', 'key1'), 'data1', ((), )),
1665
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
1666
self.assertEqual(2, adapter.key_count())
1668
def test_validate(self):
1669
index, adapter = self.make_index()
1672
calls.append('called')
1673
index.validate = validate
1675
self.assertEqual(['called'], calls)
added
removed
bzrlib/tests/test_index.py
