1
# Copyright (C) 2007 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
"""Tests for indices."""
19
from bzrlib import errors
20
from bzrlib.index import *
21
from bzrlib.tests import TestCaseWithMemoryTransport
24
class TestGraphIndexBuilder(TestCaseWithMemoryTransport):
26
def test_build_index_empty(self):
27
builder = GraphIndexBuilder()
28
stream = builder.finish()
29
contents = stream.read()
31
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=0\n\n",
34
def test_build_index_empty_two_element_keys(self):
35
builder = GraphIndexBuilder(key_elements=2)
36
stream = builder.finish()
37
contents = stream.read()
39
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=0\n\n",
42
def test_build_index_one_reference_list_empty(self):
43
builder = GraphIndexBuilder(reference_lists=1)
44
stream = builder.finish()
45
contents = stream.read()
47
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=0\n\n",
50
def test_build_index_two_reference_list_empty(self):
51
builder = GraphIndexBuilder(reference_lists=2)
52
stream = builder.finish()
53
contents = stream.read()
55
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=0\n\n",
58
def test_build_index_one_node_no_refs(self):
59
builder = GraphIndexBuilder()
60
builder.add_node(('akey', ), 'data')
61
stream = builder.finish()
62
contents = stream.read()
64
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
65
"akey\x00\x00\x00data\n\n", contents)
67
def test_build_index_one_node_no_refs_accepts_empty_reflist(self):
68
builder = GraphIndexBuilder()
69
builder.add_node(('akey', ), 'data', ())
70
stream = builder.finish()
71
contents = stream.read()
73
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
74
"akey\x00\x00\x00data\n\n", contents)
76
def test_build_index_one_node_2_element_keys(self):
77
# multipart keys are separated by \x00 - because they are fixed length,
78
# not variable this does not cause any issues, and seems clearer to the
80
builder = GraphIndexBuilder(key_elements=2)
81
builder.add_node(('akey', 'secondpart'), 'data')
82
stream = builder.finish()
83
contents = stream.read()
85
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=1\n"
86
"akey\x00secondpart\x00\x00\x00data\n\n", contents)
88
def test_add_node_empty_value(self):
89
builder = GraphIndexBuilder()
90
builder.add_node(('akey', ), '')
91
stream = builder.finish()
92
contents = stream.read()
94
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=1\n"
95
"akey\x00\x00\x00\n\n", contents)
97
def test_build_index_nodes_sorted(self):
98
# the highest sorted node comes first.
99
builder = GraphIndexBuilder()
100
# use three to have a good chance of glitching dictionary hash
101
# lookups etc. Insert in randomish order that is not correct
102
# and not the reverse of the correct order.
103
builder.add_node(('2002', ), 'data')
104
builder.add_node(('2000', ), 'data')
105
builder.add_node(('2001', ), 'data')
106
stream = builder.finish()
107
contents = stream.read()
109
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\nlen=3\n"
110
"2000\x00\x00\x00data\n"
111
"2001\x00\x00\x00data\n"
112
"2002\x00\x00\x00data\n"
115
def test_build_index_2_element_key_nodes_sorted(self):
116
# multiple element keys are sorted first-key, second-key.
117
builder = GraphIndexBuilder(key_elements=2)
118
# use three values of each key element, to have a good chance of
119
# glitching dictionary hash lookups etc. Insert in randomish order that
120
# is not correct and not the reverse of the correct order.
121
builder.add_node(('2002', '2002'), 'data')
122
builder.add_node(('2002', '2000'), 'data')
123
builder.add_node(('2002', '2001'), 'data')
124
builder.add_node(('2000', '2002'), 'data')
125
builder.add_node(('2000', '2000'), 'data')
126
builder.add_node(('2000', '2001'), 'data')
127
builder.add_node(('2001', '2002'), 'data')
128
builder.add_node(('2001', '2000'), 'data')
129
builder.add_node(('2001', '2001'), 'data')
130
stream = builder.finish()
131
contents = stream.read()
133
"Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\nlen=9\n"
134
"2000\x002000\x00\x00\x00data\n"
135
"2000\x002001\x00\x00\x00data\n"
136
"2000\x002002\x00\x00\x00data\n"
137
"2001\x002000\x00\x00\x00data\n"
138
"2001\x002001\x00\x00\x00data\n"
139
"2001\x002002\x00\x00\x00data\n"
140
"2002\x002000\x00\x00\x00data\n"
141
"2002\x002001\x00\x00\x00data\n"
142
"2002\x002002\x00\x00\x00data\n"
145
def test_build_index_reference_lists_are_included_one(self):
146
builder = GraphIndexBuilder(reference_lists=1)
147
builder.add_node(('key', ), 'data', ([], ))
148
stream = builder.finish()
149
contents = stream.read()
151
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
152
"key\x00\x00\x00data\n"
155
def test_build_index_reference_lists_with_2_element_keys(self):
156
builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
157
builder.add_node(('key', 'key2'), 'data', ([], ))
158
stream = builder.finish()
159
contents = stream.read()
161
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=2\nlen=1\n"
162
"key\x00key2\x00\x00\x00data\n"
165
def test_build_index_reference_lists_are_included_two(self):
166
builder = GraphIndexBuilder(reference_lists=2)
167
builder.add_node(('key', ), 'data', ([], []))
168
stream = builder.finish()
169
contents = stream.read()
171
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
172
"key\x00\x00\t\x00data\n"
175
def test_node_references_are_byte_offsets(self):
176
builder = GraphIndexBuilder(reference_lists=1)
177
builder.add_node(('reference', ), 'data', ([], ))
178
builder.add_node(('key', ), 'data', ([('reference', )], ))
179
stream = builder.finish()
180
contents = stream.read()
182
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=2\n"
183
"key\x00\x0072\x00data\n"
184
"reference\x00\x00\x00data\n"
187
def test_node_references_are_cr_delimited(self):
188
builder = GraphIndexBuilder(reference_lists=1)
189
builder.add_node(('reference', ), 'data', ([], ))
190
builder.add_node(('reference2', ), 'data', ([], ))
191
builder.add_node(('key', ), 'data', ([('reference', ), ('reference2', )], ))
192
stream = builder.finish()
193
contents = stream.read()
195
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=3\n"
196
"key\x00\x00077\r094\x00data\n"
197
"reference\x00\x00\x00data\n"
198
"reference2\x00\x00\x00data\n"
201
def test_multiple_reference_lists_are_tab_delimited(self):
202
builder = GraphIndexBuilder(reference_lists=2)
203
builder.add_node(('keference', ), 'data', ([], []))
204
builder.add_node(('rey', ), 'data', ([('keference', )], [('keference', )]))
205
stream = builder.finish()
206
contents = stream.read()
208
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=2\n"
209
"keference\x00\x00\t\x00data\n"
210
"rey\x00\x0059\t59\x00data\n"
213
def test_add_node_referencing_missing_key_makes_absent(self):
214
builder = GraphIndexBuilder(reference_lists=1)
215
builder.add_node(('rey', ), 'data', ([('beference', ), ('aeference2', )], ))
216
stream = builder.finish()
217
contents = stream.read()
219
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
220
"aeference2\x00a\x00\x00\n"
221
"beference\x00a\x00\x00\n"
222
"rey\x00\x00074\r059\x00data\n"
225
def test_node_references_three_digits(self):
226
# test the node digit expands as needed.
227
builder = GraphIndexBuilder(reference_lists=1)
228
references = [(str(val), ) for val in reversed(range(9))]
229
builder.add_node(('2-key', ), '', (references, ))
230
stream = builder.finish()
231
contents = stream.read()
233
"Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\nlen=1\n"
237
"2-key\x00\x00151\r145\r139\r133\r127\r121\r071\r065\r059\x00\n"
246
def test_absent_has_no_reference_overhead(self):
247
# the offsets after an absent record should be correct when there are
248
# >1 reference lists.
249
builder = GraphIndexBuilder(reference_lists=2)
250
builder.add_node(('parent', ), '', ([('aail', ), ('zther', )], []))
251
stream = builder.finish()
252
contents = stream.read()
254
"Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\nlen=1\n"
255
"aail\x00a\x00\x00\n"
256
"parent\x00\x0059\r84\t\x00\n"
257
"zther\x00a\x00\x00\n"
260
def test_add_node_bad_key(self):
261
builder = GraphIndexBuilder()
262
for bad_char in '\t\n\x0b\x0c\r\x00 ':
263
self.assertRaises(errors.BadIndexKey, builder.add_node,
264
('a%skey' % bad_char, ), 'data')
265
self.assertRaises(errors.BadIndexKey, builder.add_node,
267
self.assertRaises(errors.BadIndexKey, builder.add_node,
268
'not-a-tuple', 'data')
270
self.assertRaises(errors.BadIndexKey, builder.add_node,
273
self.assertRaises(errors.BadIndexKey, builder.add_node,
274
('primary', 'secondary'), 'data')
275
# secondary key elements get checked too:
276
builder = GraphIndexBuilder(key_elements=2)
277
for bad_char in '\t\n\x0b\x0c\r\x00 ':
278
self.assertRaises(errors.BadIndexKey, builder.add_node,
279
('prefix', 'a%skey' % bad_char), 'data')
281
def test_add_node_bad_data(self):
282
builder = GraphIndexBuilder()
283
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
285
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
288
def test_add_node_bad_mismatched_ref_lists_length(self):
289
builder = GraphIndexBuilder()
290
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
292
builder = GraphIndexBuilder(reference_lists=1)
293
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
295
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
297
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
299
builder = GraphIndexBuilder(reference_lists=2)
300
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
302
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
304
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
305
'data aa', ([], [], []))
307
def test_add_node_bad_key_in_reference_lists(self):
308
# first list, first key - trivial
309
builder = GraphIndexBuilder(reference_lists=1)
310
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
311
'data aa', ([('a key', )], ))
312
# references keys must be tuples too
313
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
314
'data aa', (['not-a-tuple'], ))
316
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
319
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
320
'data aa', ([('primary', 'secondary')], ))
321
# need to check more than the first key in the list
322
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
323
'data aa', ([('agoodkey', ), ('that is a bad key', )], ))
324
# and if there is more than one list it should be getting checked
326
builder = GraphIndexBuilder(reference_lists=2)
327
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
328
'data aa', ([], ['a bad key']))
330
def test_add_duplicate_key(self):
331
builder = GraphIndexBuilder()
332
builder.add_node(('key', ), 'data')
333
self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node, ('key', ),
336
def test_add_duplicate_key_2_elements(self):
337
builder = GraphIndexBuilder(key_elements=2)
338
builder.add_node(('key', 'key'), 'data')
339
self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node,
340
('key', 'key'), 'data')
342
def test_add_key_after_referencing_key(self):
343
builder = GraphIndexBuilder(reference_lists=1)
344
builder.add_node(('key', ), 'data', ([('reference', )], ))
345
builder.add_node(('reference', ), 'data', ([],))
347
def test_add_key_after_referencing_key_2_elements(self):
348
builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
349
builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
350
builder.add_node(('reference', 'tokey'), 'data', ([],))
353
class TestGraphIndex(TestCaseWithMemoryTransport):
355
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
356
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
357
for key, value, references in nodes:
358
builder.add_node(key, value, references)
359
stream = builder.finish()
360
trans = self.get_transport()
361
trans.put_file('index', stream)
362
return GraphIndex(trans, 'index')
364
def test_open_bad_index_no_error(self):
365
trans = self.get_transport()
366
trans.put_bytes('name', "not an index\n")
367
index = GraphIndex(trans, 'name')
369
def test_iter_all_entries_empty(self):
370
index = self.make_index()
371
self.assertEqual([], list(index.iter_all_entries()))
373
def test_iter_all_entries_simple(self):
374
index = self.make_index(nodes=[(('name', ), 'data', ())])
375
self.assertEqual([(index, ('name', ), 'data')],
376
list(index.iter_all_entries()))
378
def test_iter_all_entries_simple_2_elements(self):
379
index = self.make_index(key_elements=2,
380
nodes=[(('name', 'surname'), 'data', ())])
381
self.assertEqual([(index, ('name', 'surname'), 'data')],
382
list(index.iter_all_entries()))
384
def test_iter_all_entries_references_resolved(self):
385
index = self.make_index(1, nodes=[
386
(('name', ), 'data', ([('ref', )], )),
387
(('ref', ), 'refdata', ([], ))])
388
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
389
(index, ('ref', ), 'refdata', ((), ))]),
390
set(index.iter_all_entries()))
392
def test_iteration_absent_skipped(self):
393
index = self.make_index(1, nodes=[
394
(('name', ), 'data', ([('ref', )], ))])
395
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
396
set(index.iter_all_entries()))
397
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
398
set(index.iter_entries([('name', )])))
399
self.assertEqual([], list(index.iter_entries([('ref', )])))
401
def test_iteration_absent_skipped_2_element_keys(self):
402
index = self.make_index(1, key_elements=2, nodes=[
403
(('name', 'fin'), 'data', ([('ref', 'erence')], ))])
404
self.assertEqual(set([(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
405
set(index.iter_all_entries()))
406
self.assertEqual(set([(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
407
set(index.iter_entries([('name', 'fin')])))
408
self.assertEqual([], list(index.iter_entries([('ref', 'erence')])))
410
def test_iter_all_keys(self):
411
index = self.make_index(1, nodes=[
412
(('name', ), 'data', ([('ref', )], )),
413
(('ref', ), 'refdata', ([], ))])
414
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
415
(index, ('ref', ), 'refdata', ((), ))]),
416
set(index.iter_entries([('name', ), ('ref', )])))
418
def test_iter_nothing_empty(self):
419
index = self.make_index()
420
self.assertEqual([], list(index.iter_entries([])))
422
def test_iter_missing_entry_empty(self):
423
index = self.make_index()
424
self.assertEqual([], list(index.iter_entries([('a', )])))
426
def test_iter_key_prefix_1_element_key_None(self):
427
index = self.make_index()
428
self.assertRaises(errors.BadIndexKey, list,
429
index.iter_entries_prefix([(None, )]))
431
def test_iter_key_prefix_wrong_length(self):
432
index = self.make_index()
433
self.assertRaises(errors.BadIndexKey, list,
434
index.iter_entries_prefix([('foo', None)]))
435
index = self.make_index(key_elements=2)
436
self.assertRaises(errors.BadIndexKey, list,
437
index.iter_entries_prefix([('foo', )]))
438
self.assertRaises(errors.BadIndexKey, list,
439
index.iter_entries_prefix([('foo', None, None)]))
441
def test_iter_key_prefix_1_key_element_no_refs(self):
442
index = self.make_index( nodes=[
443
(('name', ), 'data', ()),
444
(('ref', ), 'refdata', ())])
445
self.assertEqual(set([(index, ('name', ), 'data'),
446
(index, ('ref', ), 'refdata')]),
447
set(index.iter_entries_prefix([('name', ), ('ref', )])))
449
def test_iter_key_prefix_1_key_element_refs(self):
450
index = self.make_index(1, nodes=[
451
(('name', ), 'data', ([('ref', )], )),
452
(('ref', ), 'refdata', ([], ))])
453
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
454
(index, ('ref', ), 'refdata', ((), ))]),
455
set(index.iter_entries_prefix([('name', ), ('ref', )])))
457
def test_iter_key_prefix_2_key_element_no_refs(self):
458
index = self.make_index(key_elements=2, nodes=[
459
(('name', 'fin1'), 'data', ()),
460
(('name', 'fin2'), 'beta', ()),
461
(('ref', 'erence'), 'refdata', ())])
462
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
463
(index, ('ref', 'erence'), 'refdata')]),
464
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
465
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
466
(index, ('name', 'fin2'), 'beta')]),
467
set(index.iter_entries_prefix([('name', None)])))
469
def test_iter_key_prefix_2_key_element_refs(self):
470
index = self.make_index(1, key_elements=2, nodes=[
471
(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
472
(('name', 'fin2'), 'beta', ([], )),
473
(('ref', 'erence'), 'refdata', ([], ))])
474
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
475
(index, ('ref', 'erence'), 'refdata', ((), ))]),
476
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
477
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
478
(index, ('name', 'fin2'), 'beta', ((), ))]),
479
set(index.iter_entries_prefix([('name', None)])))
481
def test_key_count_empty(self):
482
index = self.make_index()
483
self.assertEqual(0, index.key_count())
485
def test_key_count_one(self):
486
index = self.make_index(nodes=[(('name', ), '', ())])
487
self.assertEqual(1, index.key_count())
489
def test_key_count_two(self):
490
index = self.make_index(nodes=[
491
(('name', ), '', ()), (('foo', ), '', ())])
492
self.assertEqual(2, index.key_count())
494
def test_validate_bad_index_errors(self):
495
trans = self.get_transport()
496
trans.put_bytes('name', "not an index\n")
497
index = GraphIndex(trans, 'name')
498
self.assertRaises(errors.BadIndexFormatSignature, index.validate)
500
def test_validate_bad_node_refs(self):
501
index = self.make_index(2)
502
trans = self.get_transport()
503
content = trans.get_bytes('index')
504
# change the options line to end with a rather than a parseable number
505
new_content = content[:-2] + 'a\n\n'
506
trans.put_bytes('index', new_content)
507
self.assertRaises(errors.BadIndexOptions, index.validate)
509
def test_validate_missing_end_line_empty(self):
510
index = self.make_index(2)
511
trans = self.get_transport()
512
content = trans.get_bytes('index')
513
# truncate the last byte
514
trans.put_bytes('index', content[:-1])
515
self.assertRaises(errors.BadIndexData, index.validate)
517
def test_validate_missing_end_line_nonempty(self):
518
index = self.make_index(2, nodes=[(('key', ), '', ([], []))])
519
trans = self.get_transport()
520
content = trans.get_bytes('index')
521
# truncate the last byte
522
trans.put_bytes('index', content[:-1])
523
self.assertRaises(errors.BadIndexData, index.validate)
525
def test_validate_empty(self):
526
index = self.make_index()
529
def test_validate_no_refs_content(self):
530
index = self.make_index(nodes=[(('key', ), 'value', ())])
534
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
536
def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
537
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
538
for key, value, references in nodes:
539
builder.add_node(key, value, references)
540
stream = builder.finish()
541
trans = self.get_transport()
542
trans.put_file(name, stream)
543
return GraphIndex(trans, name)
545
def test_open_missing_index_no_error(self):
546
trans = self.get_transport()
547
index1 = GraphIndex(trans, 'missing')
548
index = CombinedGraphIndex([index1])
550
def test_add_index(self):
551
index = CombinedGraphIndex([])
552
index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
553
index.insert_index(0, index1)
554
self.assertEqual([(index1, ('key', ), '')], list(index.iter_all_entries()))
556
def test_iter_all_entries_empty(self):
557
index = CombinedGraphIndex([])
558
self.assertEqual([], list(index.iter_all_entries()))
560
def test_iter_all_entries_children_empty(self):
561
index1 = self.make_index('name')
562
index = CombinedGraphIndex([index1])
563
self.assertEqual([], list(index.iter_all_entries()))
565
def test_iter_all_entries_simple(self):
566
index1 = self.make_index('name', nodes=[(('name', ), 'data', ())])
567
index = CombinedGraphIndex([index1])
568
self.assertEqual([(index1, ('name', ), 'data')],
569
list(index.iter_all_entries()))
571
def test_iter_all_entries_two_indices(self):
572
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
573
index2 = self.make_index('name2', nodes=[(('2', ), '', ())])
574
index = CombinedGraphIndex([index1, index2])
575
self.assertEqual([(index1, ('name', ), 'data'),
576
(index2, ('2', ), '')],
577
list(index.iter_all_entries()))
579
def test_iter_entries_two_indices_dup_key(self):
580
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
581
index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
582
index = CombinedGraphIndex([index1, index2])
583
self.assertEqual([(index1, ('name', ), 'data')],
584
list(index.iter_entries([('name', )])))
586
def test_iter_all_entries_two_indices_dup_key(self):
587
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
588
index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
589
index = CombinedGraphIndex([index1, index2])
590
self.assertEqual([(index1, ('name', ), 'data')],
591
list(index.iter_all_entries()))
593
def test_iter_key_prefix_2_key_element_refs(self):
594
index1 = self.make_index('1', 1, key_elements=2, nodes=[
595
(('name', 'fin1'), 'data', ([('ref', 'erence')], ))])
596
index2 = self.make_index('2', 1, key_elements=2, nodes=[
597
(('name', 'fin2'), 'beta', ([], )),
598
(('ref', 'erence'), 'refdata', ([], ))])
599
index = CombinedGraphIndex([index1, index2])
600
self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
601
(index2, ('ref', 'erence'), 'refdata', ((), ))]),
602
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
603
self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
604
(index2, ('name', 'fin2'), 'beta', ((), ))]),
605
set(index.iter_entries_prefix([('name', None)])))
607
def test_iter_nothing_empty(self):
608
index = CombinedGraphIndex([])
609
self.assertEqual([], list(index.iter_entries([])))
611
def test_iter_nothing_children_empty(self):
612
index1 = self.make_index('name')
613
index = CombinedGraphIndex([index1])
614
self.assertEqual([], list(index.iter_entries([])))
616
def test_iter_all_keys(self):
617
index1 = self.make_index('1', 1, nodes=[
618
(('name', ), 'data', ([('ref', )], ))])
619
index2 = self.make_index('2', 1, nodes=[
620
(('ref', ), 'refdata', ((), ))])
621
index = CombinedGraphIndex([index1, index2])
622
self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),
623
(index2, ('ref', ), 'refdata', ((), ))]),
624
set(index.iter_entries([('name', ), ('ref', )])))
626
def test_iter_all_keys_dup_entry(self):
627
index1 = self.make_index('1', 1, nodes=[
628
(('name', ), 'data', ([('ref', )], )),
629
(('ref', ), 'refdata', ([], ))])
630
index2 = self.make_index('2', 1, nodes=[
631
(('ref', ), 'refdata', ([], ))])
632
index = CombinedGraphIndex([index1, index2])
633
self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),
634
(index1, ('ref', ), 'refdata', ((), ))]),
635
set(index.iter_entries([('name', ), ('ref', )])))
637
def test_iter_missing_entry_empty(self):
638
index = CombinedGraphIndex([])
639
self.assertEqual([], list(index.iter_entries([('a', )])))
641
def test_iter_missing_entry_one_index(self):
642
index1 = self.make_index('1')
643
index = CombinedGraphIndex([index1])
644
self.assertEqual([], list(index.iter_entries([('a', )])))
646
def test_iter_missing_entry_two_index(self):
647
index1 = self.make_index('1')
648
index2 = self.make_index('2')
649
index = CombinedGraphIndex([index1, index2])
650
self.assertEqual([], list(index.iter_entries([('a', )])))
652
def test_iter_entry_present_one_index_only(self):
653
index1 = self.make_index('1', nodes=[(('key', ), '', ())])
654
index2 = self.make_index('2', nodes=[])
655
index = CombinedGraphIndex([index1, index2])
656
self.assertEqual([(index1, ('key', ), '')],
657
list(index.iter_entries([('key', )])))
658
# and in the other direction
659
index = CombinedGraphIndex([index2, index1])
660
self.assertEqual([(index1, ('key', ), '')],
661
list(index.iter_entries([('key', )])))
663
def test_key_count_empty(self):
664
index1 = self.make_index('1', nodes=[])
665
index2 = self.make_index('2', nodes=[])
666
index = CombinedGraphIndex([index1, index2])
667
self.assertEqual(0, index.key_count())
669
def test_key_count_sums_index_keys(self):
670
index1 = self.make_index('1', nodes=[
673
index2 = self.make_index('2', nodes=[(('1',), '', ())])
674
index = CombinedGraphIndex([index1, index2])
675
self.assertEqual(3, index.key_count())
677
def test_validate_bad_child_index_errors(self):
678
trans = self.get_transport()
679
trans.put_bytes('name', "not an index\n")
680
index1 = GraphIndex(trans, 'name')
681
index = CombinedGraphIndex([index1])
682
self.assertRaises(errors.BadIndexFormatSignature, index.validate)
684
def test_validate_empty(self):
685
index = CombinedGraphIndex([])
689
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
691
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
692
result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
693
result.add_nodes(nodes)
696
def test_add_nodes_no_refs(self):
697
index = self.make_index(0)
698
index.add_nodes([(('name', ), 'data')])
699
index.add_nodes([(('name2', ), ''), (('name3', ), '')])
700
self.assertEqual(set([
701
(index, ('name', ), 'data'),
702
(index, ('name2', ), ''),
703
(index, ('name3', ), ''),
704
]), set(index.iter_all_entries()))
706
def test_add_nodes(self):
707
index = self.make_index(1)
708
index.add_nodes([(('name', ), 'data', ([],))])
709
index.add_nodes([(('name2', ), '', ([],)), (('name3', ), '', ([('r', )],))])
710
self.assertEqual(set([
711
(index, ('name', ), 'data', ((),)),
712
(index, ('name2', ), '', ((),)),
713
(index, ('name3', ), '', ((('r', ), ), )),
714
]), set(index.iter_all_entries()))
716
def test_iter_all_entries_empty(self):
717
index = self.make_index()
718
self.assertEqual([], list(index.iter_all_entries()))
720
def test_iter_all_entries_simple(self):
721
index = self.make_index(nodes=[(('name', ), 'data')])
722
self.assertEqual([(index, ('name', ), 'data')],
723
list(index.iter_all_entries()))
725
def test_iter_all_entries_references(self):
726
index = self.make_index(1, nodes=[
727
(('name', ), 'data', ([('ref', )], )),
728
(('ref', ), 'refdata', ([], ))])
729
self.assertEqual(set([(index, ('name', ), 'data', ((('ref', ),),)),
730
(index, ('ref', ), 'refdata', ((), ))]),
731
set(index.iter_all_entries()))
733
def test_iteration_absent_skipped(self):
734
index = self.make_index(1, nodes=[
735
(('name', ), 'data', ([('ref', )], ))])
736
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
737
set(index.iter_all_entries()))
738
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
739
set(index.iter_entries([('name', )])))
740
self.assertEqual([], list(index.iter_entries([('ref', )])))
742
def test_iter_all_keys(self):
743
index = self.make_index(1, nodes=[
744
(('name', ), 'data', ([('ref', )], )),
745
(('ref', ), 'refdata', ([], ))])
746
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
747
(index, ('ref', ), 'refdata', ((), ))]),
748
set(index.iter_entries([('name', ), ('ref', )])))
750
def test_iter_key_prefix_1_key_element_no_refs(self):
751
index = self.make_index( nodes=[
752
(('name', ), 'data'),
753
(('ref', ), 'refdata')])
754
self.assertEqual(set([(index, ('name', ), 'data'),
755
(index, ('ref', ), 'refdata')]),
756
set(index.iter_entries_prefix([('name', ), ('ref', )])))
758
def test_iter_key_prefix_1_key_element_refs(self):
759
index = self.make_index(1, nodes=[
760
(('name', ), 'data', ([('ref', )], )),
761
(('ref', ), 'refdata', ([], ))])
762
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
763
(index, ('ref', ), 'refdata', ((), ))]),
764
set(index.iter_entries_prefix([('name', ), ('ref', )])))
766
def test_iter_key_prefix_2_key_element_no_refs(self):
767
index = self.make_index(key_elements=2, nodes=[
768
(('name', 'fin1'), 'data'),
769
(('name', 'fin2'), 'beta'),
770
(('ref', 'erence'), 'refdata')])
771
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
772
(index, ('ref', 'erence'), 'refdata')]),
773
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
774
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
775
(index, ('name', 'fin2'), 'beta')]),
776
set(index.iter_entries_prefix([('name', None)])))
778
def test_iter_key_prefix_2_key_element_refs(self):
779
index = self.make_index(1, key_elements=2, nodes=[
780
(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
781
(('name', 'fin2'), 'beta', ([], )),
782
(('ref', 'erence'), 'refdata', ([], ))])
783
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
784
(index, ('ref', 'erence'), 'refdata', ((), ))]),
785
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
786
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
787
(index, ('name', 'fin2'), 'beta', ((), ))]),
788
set(index.iter_entries_prefix([('name', None)])))
790
def test_iter_nothing_empty(self):
791
index = self.make_index()
792
self.assertEqual([], list(index.iter_entries([])))
794
def test_iter_missing_entry_empty(self):
795
index = self.make_index()
796
self.assertEqual([], list(index.iter_entries(['a'])))
798
def test_key_count_empty(self):
799
index = self.make_index()
800
self.assertEqual(0, index.key_count())
802
def test_key_count_one(self):
803
index = self.make_index(nodes=[(('name', ), '')])
804
self.assertEqual(1, index.key_count())
806
def test_key_count_two(self):
807
index = self.make_index(nodes=[(('name', ), ''), (('foo', ), '')])
808
self.assertEqual(2, index.key_count())
810
def test_validate_empty(self):
811
index = self.make_index()
814
def test_validate_no_refs_content(self):
815
index = self.make_index(nodes=[(('key', ), 'value')])
819
class TestGraphIndexPrefixAdapter(TestCaseWithMemoryTransport):
821
def make_index(self, ref_lists=1, key_elements=2, nodes=[], add_callback=False):
822
result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
823
result.add_nodes(nodes)
825
add_nodes_callback = result.add_nodes
827
add_nodes_callback = None
828
adapter = GraphIndexPrefixAdapter(result, ('prefix', ), key_elements - 1,
829
add_nodes_callback=add_nodes_callback)
830
return result, adapter
832
def test_add_node(self):
833
index, adapter = self.make_index(add_callback=True)
834
adapter.add_node(('key',), 'value', ((('ref',),),))
835
self.assertEqual(set([(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))]),
836
set(index.iter_all_entries()))
838
def test_add_nodes(self):
839
index, adapter = self.make_index(add_callback=True)
841
(('key',), 'value', ((('ref',),),)),
842
(('key2',), 'value2', ((),)),
844
self.assertEqual(set([
845
(index, ('prefix', 'key2'), 'value2', ((),)),
846
(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))
848
set(index.iter_all_entries()))
850
def test_construct(self):
851
index = InMemoryGraphIndex()
852
adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1)
854
def test_construct_with_callback(self):
855
index = InMemoryGraphIndex()
856
adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1, index.add_nodes)
858
def test_iter_all_entries_cross_prefix_map_errors(self):
859
index, adapter = self.make_index(nodes=[
860
(('prefix', 'key1'), 'data1', ((('prefixaltered', 'key2'),),))])
861
self.assertRaises(errors.BadIndexData, list, adapter.iter_all_entries())
863
def test_iter_all_entries(self):
864
index, adapter = self.make_index(nodes=[
865
(('notprefix', 'key1'), 'data', ((), )),
866
(('prefix', 'key1'), 'data1', ((), )),
867
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
868
self.assertEqual(set([(index, ('key1', ), 'data1', ((),)),
869
(index, ('key2', ), 'data2', ((('key1',),),))]),
870
set(adapter.iter_all_entries()))
872
def test_iter_entries(self):
873
index, adapter = self.make_index(nodes=[
874
(('notprefix', 'key1'), 'data', ((), )),
875
(('prefix', 'key1'), 'data1', ((), )),
876
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
877
# ask for many - get all
878
self.assertEqual(set([(index, ('key1', ), 'data1', ((),)),
879
(index, ('key2', ), 'data2', ((('key1', ),),))]),
880
set(adapter.iter_entries([('key1', ), ('key2', )])))
881
# ask for one, get one
882
self.assertEqual(set([(index, ('key1', ), 'data1', ((),))]),
883
set(adapter.iter_entries([('key1', )])))
884
# ask for missing, get none
885
self.assertEqual(set(),
886
set(adapter.iter_entries([('key3', )])))
888
def test_iter_entries_prefix(self):
889
index, adapter = self.make_index(key_elements=3, nodes=[
890
(('notprefix', 'foo', 'key1'), 'data', ((), )),
891
(('prefix', 'prefix2', 'key1'), 'data1', ((), )),
892
(('prefix', 'prefix2', 'key2'), 'data2', ((('prefix', 'prefix2', 'key1'),),))])
893
# ask for a prefix, get the results for just that prefix, adjusted.
894
self.assertEqual(set([(index, ('prefix2', 'key1', ), 'data1', ((),)),
895
(index, ('prefix2', 'key2', ), 'data2', ((('prefix2', 'key1', ),),))]),
896
set(adapter.iter_entries_prefix([('prefix2', None)])))
898
def test_key_count_no_matching_keys(self):
899
index, adapter = self.make_index(nodes=[
900
(('notprefix', 'key1'), 'data', ((), ))])
901
self.assertEqual(0, adapter.key_count())
903
def test_key_count_some_keys(self):
904
index, adapter = self.make_index(nodes=[
905
(('notprefix', 'key1'), 'data', ((), )),
906
(('prefix', 'key1'), 'data1', ((), )),
907
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
908
self.assertEqual(2, adapter.key_count())
910
def test_validate(self):
911
index, adapter = self.make_index()
914
calls.append('called')
915
index.validate = validate
917
self.assertEqual(['called'], calls)
added
removed
bzrlib/tests/test_index.py
