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()
30
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n\n", contents)
32
def test_build_index_empty_two_element_keys(self):
33
builder = GraphIndexBuilder(key_elements=2)
34
stream = builder.finish()
35
contents = stream.read()
36
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\n\n", contents)
38
def test_build_index_one_reference_list_empty(self):
39
builder = GraphIndexBuilder(reference_lists=1)
40
stream = builder.finish()
41
contents = stream.read()
42
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n\n", contents)
44
def test_build_index_two_reference_list_empty(self):
45
builder = GraphIndexBuilder(reference_lists=2)
46
stream = builder.finish()
47
contents = stream.read()
48
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\n\n", contents)
50
def test_build_index_one_node_no_refs(self):
51
builder = GraphIndexBuilder()
52
builder.add_node(('akey', ), 'data')
53
stream = builder.finish()
54
contents = stream.read()
55
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n"
56
"akey\x00\x00\x00data\n\n", contents)
58
def test_build_index_one_node_no_refs_accepts_empty_reflist(self):
59
builder = GraphIndexBuilder()
60
builder.add_node(('akey', ), 'data', ())
61
stream = builder.finish()
62
contents = stream.read()
63
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n"
64
"akey\x00\x00\x00data\n\n", contents)
66
def test_build_index_one_node_2_element_keys(self):
67
# multipart keys are separated by \x00 - because they are fixed length,
68
# not variable this does not cause any issues, and seems clearer to the
70
builder = GraphIndexBuilder(key_elements=2)
71
builder.add_node(('akey', 'secondpart'), 'data')
72
stream = builder.finish()
73
contents = stream.read()
74
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\n"
75
"akey\x00secondpart\x00\x00\x00data\n\n", contents)
77
def test_add_node_empty_value(self):
78
builder = GraphIndexBuilder()
79
builder.add_node(('akey', ), '')
80
stream = builder.finish()
81
contents = stream.read()
82
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n"
83
"akey\x00\x00\x00\n\n", contents)
85
def test_build_index_nodes_sorted(self):
86
# the highest sorted node comes first.
87
builder = GraphIndexBuilder()
88
# use three to have a good chance of glitching dictionary hash
89
# lookups etc. Insert in randomish order that is not correct
90
# and not the reverse of the correct order.
91
builder.add_node(('2002', ), 'data')
92
builder.add_node(('2000', ), 'data')
93
builder.add_node(('2001', ), 'data')
94
stream = builder.finish()
95
contents = stream.read()
96
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n"
97
"2000\x00\x00\x00data\n"
98
"2001\x00\x00\x00data\n"
99
"2002\x00\x00\x00data\n"
102
def test_build_index_2_element_key_nodes_sorted(self):
103
# multiple element keys are sorted first-key, second-key.
104
builder = GraphIndexBuilder(key_elements=2)
105
# use three values of each key element, to have a good chance of
106
# glitching dictionary hash lookups etc. Insert in randomish order that
107
# is not correct and not the reverse of the correct order.
108
builder.add_node(('2002', '2002'), 'data')
109
builder.add_node(('2002', '2000'), 'data')
110
builder.add_node(('2002', '2001'), 'data')
111
builder.add_node(('2000', '2002'), 'data')
112
builder.add_node(('2000', '2000'), 'data')
113
builder.add_node(('2000', '2001'), 'data')
114
builder.add_node(('2001', '2002'), 'data')
115
builder.add_node(('2001', '2000'), 'data')
116
builder.add_node(('2001', '2001'), 'data')
117
stream = builder.finish()
118
contents = stream.read()
119
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\n"
120
"2000\x002000\x00\x00\x00data\n"
121
"2000\x002001\x00\x00\x00data\n"
122
"2000\x002002\x00\x00\x00data\n"
123
"2001\x002000\x00\x00\x00data\n"
124
"2001\x002001\x00\x00\x00data\n"
125
"2001\x002002\x00\x00\x00data\n"
126
"2002\x002000\x00\x00\x00data\n"
127
"2002\x002001\x00\x00\x00data\n"
128
"2002\x002002\x00\x00\x00data\n"
131
def test_build_index_reference_lists_are_included_one(self):
132
builder = GraphIndexBuilder(reference_lists=1)
133
builder.add_node(('key', ), 'data', ([], ))
134
stream = builder.finish()
135
contents = stream.read()
136
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n"
137
"key\x00\x00\x00data\n"
140
def test_build_index_reference_lists_with_2_element_keys(self):
141
builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
142
builder.add_node(('key', 'key2'), 'data', ([], ))
143
stream = builder.finish()
144
contents = stream.read()
145
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=2\n"
146
"key\x00key2\x00\x00\x00data\n"
149
def test_build_index_reference_lists_are_included_two(self):
150
builder = GraphIndexBuilder(reference_lists=2)
151
builder.add_node(('key', ), 'data', ([], []))
152
stream = builder.finish()
153
contents = stream.read()
154
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\n"
155
"key\x00\x00\t\x00data\n"
158
def test_node_references_are_byte_offsets(self):
159
builder = GraphIndexBuilder(reference_lists=1)
160
builder.add_node(('reference', ), 'data', ([], ))
161
builder.add_node(('key', ), 'data', ([('reference', )], ))
162
stream = builder.finish()
163
contents = stream.read()
164
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n"
165
"key\x00\x0066\x00data\n"
166
"reference\x00\x00\x00data\n"
169
def test_node_references_are_cr_delimited(self):
170
builder = GraphIndexBuilder(reference_lists=1)
171
builder.add_node(('reference', ), 'data', ([], ))
172
builder.add_node(('reference2', ), 'data', ([], ))
173
builder.add_node(('key', ), 'data', ([('reference', ), ('reference2', )], ))
174
stream = builder.finish()
175
contents = stream.read()
176
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n"
177
"key\x00\x00071\r088\x00data\n"
178
"reference\x00\x00\x00data\n"
179
"reference2\x00\x00\x00data\n"
182
def test_multiple_reference_lists_are_tab_delimited(self):
183
builder = GraphIndexBuilder(reference_lists=2)
184
builder.add_node(('keference', ), 'data', ([], []))
185
builder.add_node(('rey', ), 'data', ([('keference', )], [('keference', )]))
186
stream = builder.finish()
187
contents = stream.read()
188
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\n"
189
"keference\x00\x00\t\x00data\n"
190
"rey\x00\x0053\t53\x00data\n"
193
def test_add_node_referencing_missing_key_makes_absent(self):
194
builder = GraphIndexBuilder(reference_lists=1)
195
builder.add_node(('rey', ), 'data', ([('beference', ), ('aeference2', )], ))
196
stream = builder.finish()
197
contents = stream.read()
198
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n"
199
"aeference2\x00a\x00\x00\n"
200
"beference\x00a\x00\x00\n"
201
"rey\x00\x0068\r53\x00data\n"
204
def test_node_references_three_digits(self):
205
# test the node digit expands as needed.
206
builder = GraphIndexBuilder(reference_lists=1)
207
references = [(str(val), ) for val in reversed(range(9))]
208
builder.add_node(('2-key', ), '', (references, ))
209
stream = builder.finish()
210
contents = stream.read()
211
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=1\n"
215
"2-key\x00\x00145\r139\r133\r127\r121\r115\r065\r059\r053\x00\n"
224
def test_absent_has_no_reference_overhead(self):
225
# the offsets after an absent record should be correct when there are
226
# >1 reference lists.
227
builder = GraphIndexBuilder(reference_lists=2)
228
builder.add_node(('parent', ), '', ([('aail', ), ('zther', )], []))
229
stream = builder.finish()
230
contents = stream.read()
231
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\nkey_elements=1\n"
232
"aail\x00a\x00\x00\n"
233
"parent\x00\x0053\r78\t\x00\n"
234
"zther\x00a\x00\x00\n"
237
def test_add_node_bad_key(self):
238
builder = GraphIndexBuilder()
239
for bad_char in '\t\n\x0b\x0c\r\x00 ':
240
self.assertRaises(errors.BadIndexKey, builder.add_node,
241
('a%skey' % bad_char, ), 'data')
242
self.assertRaises(errors.BadIndexKey, builder.add_node,
244
self.assertRaises(errors.BadIndexKey, builder.add_node,
245
'not-a-tuple', 'data')
247
self.assertRaises(errors.BadIndexKey, builder.add_node,
250
self.assertRaises(errors.BadIndexKey, builder.add_node,
251
('primary', 'secondary'), 'data')
252
# secondary key elements get checked too:
253
builder = GraphIndexBuilder(key_elements=2)
254
for bad_char in '\t\n\x0b\x0c\r\x00 ':
255
self.assertRaises(errors.BadIndexKey, builder.add_node,
256
('prefix', 'a%skey' % bad_char), 'data')
258
def test_add_node_bad_data(self):
259
builder = GraphIndexBuilder()
260
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
262
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
265
def test_add_node_bad_mismatched_ref_lists_length(self):
266
builder = GraphIndexBuilder()
267
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
269
builder = GraphIndexBuilder(reference_lists=1)
270
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
272
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
274
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
276
builder = GraphIndexBuilder(reference_lists=2)
277
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
279
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
281
self.assertRaises(errors.BadIndexValue, builder.add_node, ('akey', ),
282
'data aa', ([], [], []))
284
def test_add_node_bad_key_in_reference_lists(self):
285
# first list, first key - trivial
286
builder = GraphIndexBuilder(reference_lists=1)
287
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
288
'data aa', ([('a key', )], ))
289
# references keys must be tuples too
290
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
291
'data aa', (['not-a-tuple'], ))
293
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
296
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
297
'data aa', ([('primary', 'secondary')], ))
298
# need to check more than the first key in the list
299
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
300
'data aa', ([('agoodkey', ), ('that is a bad key', )], ))
301
# and if there is more than one list it should be getting checked
303
builder = GraphIndexBuilder(reference_lists=2)
304
self.assertRaises(errors.BadIndexKey, builder.add_node, ('akey', ),
305
'data aa', ([], ['a bad key']))
307
def test_add_duplicate_key(self):
308
builder = GraphIndexBuilder()
309
builder.add_node(('key', ), 'data')
310
self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node, ('key', ),
313
def test_add_duplicate_key_2_elements(self):
314
builder = GraphIndexBuilder(key_elements=2)
315
builder.add_node(('key', 'key'), 'data')
316
self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node,
317
('key', 'key'), 'data')
319
def test_add_key_after_referencing_key(self):
320
builder = GraphIndexBuilder(reference_lists=1)
321
builder.add_node(('key', ), 'data', ([('reference', )], ))
322
builder.add_node(('reference', ), 'data', ([],))
324
def test_add_key_after_referencing_key_2_elements(self):
325
builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
326
builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
327
builder.add_node(('reference', 'tokey'), 'data', ([],))
330
class TestGraphIndex(TestCaseWithMemoryTransport):
332
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
333
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
334
for node, value, references in nodes:
335
builder.add_node(node, value, references)
336
stream = builder.finish()
337
trans = self.get_transport()
338
trans.put_file('index', stream)
339
return GraphIndex(trans, 'index')
341
def test_open_bad_index_no_error(self):
342
trans = self.get_transport()
343
trans.put_bytes('name', "not an index\n")
344
index = GraphIndex(trans, 'name')
346
def test_iter_all_entries_empty(self):
347
index = self.make_index()
348
self.assertEqual([], list(index.iter_all_entries()))
350
def test_iter_all_entries_simple(self):
351
index = self.make_index(nodes=[(('name', ), 'data', ())])
352
self.assertEqual([(index, ('name', ), 'data')],
353
list(index.iter_all_entries()))
355
def test_iter_all_entries_simple_2_elements(self):
356
index = self.make_index(key_elements=2,
357
nodes=[(('name', 'surname'), 'data', ())])
358
self.assertEqual([(index, ('name', 'surname'), 'data')],
359
list(index.iter_all_entries()))
361
def test_iter_all_entries_references_resolved(self):
362
index = self.make_index(1, nodes=[
363
(('name', ), 'data', ([('ref', )], )),
364
(('ref', ), 'refdata', ([], ))])
365
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
366
(index, ('ref', ), 'refdata', ((), ))]),
367
set(index.iter_all_entries()))
369
def test_iteration_absent_skipped(self):
370
index = self.make_index(1, nodes=[
371
(('name', ), 'data', ([('ref', )], ))])
372
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
373
set(index.iter_all_entries()))
374
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
375
set(index.iter_entries([('name', )])))
376
self.assertEqual([], list(index.iter_entries([('ref', )])))
378
def test_iteration_absent_skipped_2_element_keys(self):
379
index = self.make_index(1, key_elements=2, nodes=[
380
(('name', 'fin'), 'data', ([('ref', 'erence')], ))])
381
self.assertEqual(set([(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
382
set(index.iter_all_entries()))
383
self.assertEqual(set([(index, ('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
384
set(index.iter_entries([('name', 'fin')])))
385
self.assertEqual([], list(index.iter_entries([('ref', 'erence')])))
387
def test_iter_all_keys(self):
388
index = self.make_index(1, nodes=[
389
(('name', ), 'data', ([('ref', )], )),
390
(('ref', ), 'refdata', ([], ))])
391
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
392
(index, ('ref', ), 'refdata', ((), ))]),
393
set(index.iter_entries([('name', ), ('ref', )])))
395
def test_iter_nothing_empty(self):
396
index = self.make_index()
397
self.assertEqual([], list(index.iter_entries([])))
399
def test_iter_missing_entry_empty(self):
400
index = self.make_index()
401
self.assertEqual([], list(index.iter_entries([('a', )])))
403
def test_iter_key_prefix_1_element_key_None(self):
404
index = self.make_index()
405
self.assertRaises(errors.BadIndexKey, list,
406
index.iter_entries_prefix([(None, )]))
408
def test_iter_key_prefix_wrong_length(self):
409
index = self.make_index()
410
self.assertRaises(errors.BadIndexKey, list,
411
index.iter_entries_prefix([('foo', None)]))
412
index = self.make_index(key_elements=2)
413
self.assertRaises(errors.BadIndexKey, list,
414
index.iter_entries_prefix([('foo', )]))
415
self.assertRaises(errors.BadIndexKey, list,
416
index.iter_entries_prefix([('foo', None, None)]))
418
def test_iter_key_prefix_1_key_element_no_refs(self):
419
index = self.make_index( nodes=[
420
(('name', ), 'data', ()),
421
(('ref', ), 'refdata', ())])
422
self.assertEqual(set([(index, ('name', ), 'data'),
423
(index, ('ref', ), 'refdata')]),
424
set(index.iter_entries_prefix([('name', ), ('ref', )])))
426
def test_iter_key_prefix_1_key_element_refs(self):
427
index = self.make_index(1, nodes=[
428
(('name', ), 'data', ([('ref', )], )),
429
(('ref', ), 'refdata', ([], ))])
430
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
431
(index, ('ref', ), 'refdata', ((), ))]),
432
set(index.iter_entries_prefix([('name', ), ('ref', )])))
434
def test_iter_key_prefix_2_key_element_no_refs(self):
435
index = self.make_index(key_elements=2, nodes=[
436
(('name', 'fin1'), 'data', ()),
437
(('name', 'fin2'), 'beta', ()),
438
(('ref', 'erence'), 'refdata', ())])
439
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
440
(index, ('ref', 'erence'), 'refdata')]),
441
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
442
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
443
(index, ('name', 'fin2'), 'beta')]),
444
set(index.iter_entries_prefix([('name', None)])))
446
def test_iter_key_prefix_2_key_element_refs(self):
447
index = self.make_index(1, key_elements=2, nodes=[
448
(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
449
(('name', 'fin2'), 'beta', ([], )),
450
(('ref', 'erence'), 'refdata', ([], ))])
451
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
452
(index, ('ref', 'erence'), 'refdata', ((), ))]),
453
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
454
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
455
(index, ('name', 'fin2'), 'beta', ((), ))]),
456
set(index.iter_entries_prefix([('name', None)])))
458
def test_validate_bad_index_errors(self):
459
trans = self.get_transport()
460
trans.put_bytes('name', "not an index\n")
461
index = GraphIndex(trans, 'name')
462
self.assertRaises(errors.BadIndexFormatSignature, index.validate)
464
def test_validate_bad_node_refs(self):
465
index = self.make_index(2)
466
trans = self.get_transport()
467
content = trans.get_bytes('index')
468
# change the options line to end with a rather than a parseable number
469
new_content = content[:-2] + 'a\n\n'
470
trans.put_bytes('index', new_content)
471
self.assertRaises(errors.BadIndexOptions, index.validate)
473
def test_validate_missing_end_line_empty(self):
474
index = self.make_index(2)
475
trans = self.get_transport()
476
content = trans.get_bytes('index')
477
# truncate the last byte
478
trans.put_bytes('index', content[:-1])
479
self.assertRaises(errors.BadIndexData, index.validate)
481
def test_validate_missing_end_line_nonempty(self):
482
index = self.make_index(2, nodes=[(('key', ), '', ([], []))])
483
trans = self.get_transport()
484
content = trans.get_bytes('index')
485
# truncate the last byte
486
trans.put_bytes('index', content[:-1])
487
self.assertRaises(errors.BadIndexData, index.validate)
489
def test_validate_empty(self):
490
index = self.make_index()
493
def test_validate_no_refs_content(self):
494
index = self.make_index(nodes=[(('key', ), 'value', ())])
498
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
500
def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
501
builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
502
for node, value, references in nodes:
503
builder.add_node(node, value, references)
504
stream = builder.finish()
505
trans = self.get_transport()
506
trans.put_file(name, stream)
507
return GraphIndex(trans, name)
509
def test_open_missing_index_no_error(self):
510
trans = self.get_transport()
511
index1 = GraphIndex(trans, 'missing')
512
index = CombinedGraphIndex([index1])
514
def test_add_index(self):
515
index = CombinedGraphIndex([])
516
index1 = self.make_index('name', 0, nodes=[(('key', ), '', ())])
517
index.insert_index(0, index1)
518
self.assertEqual([(index1, ('key', ), '')], list(index.iter_all_entries()))
520
def test_iter_all_entries_empty(self):
521
index = CombinedGraphIndex([])
522
self.assertEqual([], list(index.iter_all_entries()))
524
def test_iter_all_entries_children_empty(self):
525
index1 = self.make_index('name')
526
index = CombinedGraphIndex([index1])
527
self.assertEqual([], list(index.iter_all_entries()))
529
def test_iter_all_entries_simple(self):
530
index1 = self.make_index('name', nodes=[(('name', ), 'data', ())])
531
index = CombinedGraphIndex([index1])
532
self.assertEqual([(index1, ('name', ), 'data')],
533
list(index.iter_all_entries()))
535
def test_iter_all_entries_two_indices(self):
536
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
537
index2 = self.make_index('name2', nodes=[(('2', ), '', ())])
538
index = CombinedGraphIndex([index1, index2])
539
self.assertEqual([(index1, ('name', ), 'data'),
540
(index2, ('2', ), '')],
541
list(index.iter_all_entries()))
543
def test_iter_entries_two_indices_dup_key(self):
544
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
545
index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
546
index = CombinedGraphIndex([index1, index2])
547
self.assertEqual([(index1, ('name', ), 'data')],
548
list(index.iter_entries([('name', )])))
550
def test_iter_all_entries_two_indices_dup_key(self):
551
index1 = self.make_index('name1', nodes=[(('name', ), 'data', ())])
552
index2 = self.make_index('name2', nodes=[(('name', ), 'data', ())])
553
index = CombinedGraphIndex([index1, index2])
554
self.assertEqual([(index1, ('name', ), 'data')],
555
list(index.iter_all_entries()))
557
def test_iter_key_prefix_2_key_element_refs(self):
558
index1 = self.make_index('1', 1, key_elements=2, nodes=[
559
(('name', 'fin1'), 'data', ([('ref', 'erence')], ))])
560
index2 = self.make_index('2', 1, key_elements=2, nodes=[
561
(('name', 'fin2'), 'beta', ([], )),
562
(('ref', 'erence'), 'refdata', ([], ))])
563
index = CombinedGraphIndex([index1, index2])
564
self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
565
(index2, ('ref', 'erence'), 'refdata', ((), ))]),
566
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
567
self.assertEqual(set([(index1, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
568
(index2, ('name', 'fin2'), 'beta', ((), ))]),
569
set(index.iter_entries_prefix([('name', None)])))
571
def test_iter_nothing_empty(self):
572
index = CombinedGraphIndex([])
573
self.assertEqual([], list(index.iter_entries([])))
575
def test_iter_nothing_children_empty(self):
576
index1 = self.make_index('name')
577
index = CombinedGraphIndex([index1])
578
self.assertEqual([], list(index.iter_entries([])))
580
def test_iter_all_keys(self):
581
index1 = self.make_index('1', 1, nodes=[
582
(('name', ), 'data', ([('ref', )], ))])
583
index2 = self.make_index('2', 1, nodes=[
584
(('ref', ), 'refdata', ((), ))])
585
index = CombinedGraphIndex([index1, index2])
586
self.assertEqual(set([(index1, ('name', ), 'data', ((('ref', ), ), )),
587
(index2, ('ref', ), 'refdata', ((), ))]),
588
set(index.iter_entries([('name', ), ('ref', )])))
590
def test_iter_all_keys_dup_entry(self):
591
index1 = self.make_index('1', 1, nodes=[
592
(('name', ), 'data', ([('ref', )], )),
593
(('ref', ), 'refdata', ([], ))])
594
index2 = self.make_index('2', 1, nodes=[
595
(('ref', ), 'refdata', ([], ))])
596
index = CombinedGraphIndex([index1, index2])
597
self.assertEqual(set([(index1, ('name', ), 'data', ((('ref',),),)),
598
(index1, ('ref', ), 'refdata', ((), ))]),
599
set(index.iter_entries([('name', ), ('ref', )])))
601
def test_iter_missing_entry_empty(self):
602
index = CombinedGraphIndex([])
603
self.assertEqual([], list(index.iter_entries([('a', )])))
605
def test_iter_missing_entry_one_index(self):
606
index1 = self.make_index('1')
607
index = CombinedGraphIndex([index1])
608
self.assertEqual([], list(index.iter_entries([('a', )])))
610
def test_iter_missing_entry_two_index(self):
611
index1 = self.make_index('1')
612
index2 = self.make_index('2')
613
index = CombinedGraphIndex([index1, index2])
614
self.assertEqual([], list(index.iter_entries([('a', )])))
616
def test_iter_entry_present_one_index_only(self):
617
index1 = self.make_index('1', nodes=[(('key', ), '', ())])
618
index2 = self.make_index('2', nodes=[])
619
index = CombinedGraphIndex([index1, index2])
620
self.assertEqual([(index1, ('key', ), '')],
621
list(index.iter_entries([('key', )])))
622
# and in the other direction
623
index = CombinedGraphIndex([index2, index1])
624
self.assertEqual([(index1, ('key', ), '')],
625
list(index.iter_entries([('key', )])))
627
def test_validate_bad_child_index_errors(self):
628
trans = self.get_transport()
629
trans.put_bytes('name', "not an index\n")
630
index1 = GraphIndex(trans, 'name')
631
index = CombinedGraphIndex([index1])
632
self.assertRaises(errors.BadIndexFormatSignature, index.validate)
634
def test_validate_empty(self):
635
index = CombinedGraphIndex([])
639
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
641
def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
642
result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
643
result.add_nodes(nodes)
646
def test_add_nodes_no_refs(self):
647
index = self.make_index(0)
648
index.add_nodes([(('name', ), 'data')])
649
index.add_nodes([(('name2', ), ''), (('name3', ), '')])
650
self.assertEqual(set([
651
(index, ('name', ), 'data'),
652
(index, ('name2', ), ''),
653
(index, ('name3', ), ''),
654
]), set(index.iter_all_entries()))
656
def test_add_nodes(self):
657
index = self.make_index(1)
658
index.add_nodes([(('name', ), 'data', ([],))])
659
index.add_nodes([(('name2', ), '', ([],)), (('name3', ), '', ([('r', )],))])
660
self.assertEqual(set([
661
(index, ('name', ), 'data', ((),)),
662
(index, ('name2', ), '', ((),)),
663
(index, ('name3', ), '', ((('r', ), ), )),
664
]), set(index.iter_all_entries()))
666
def test_iter_all_entries_empty(self):
667
index = self.make_index()
668
self.assertEqual([], list(index.iter_all_entries()))
670
def test_iter_all_entries_simple(self):
671
index = self.make_index(nodes=[(('name', ), 'data')])
672
self.assertEqual([(index, ('name', ), 'data')],
673
list(index.iter_all_entries()))
675
def test_iter_all_entries_references(self):
676
index = self.make_index(1, nodes=[
677
(('name', ), 'data', ([('ref', )], )),
678
(('ref', ), 'refdata', ([], ))])
679
self.assertEqual(set([(index, ('name', ), 'data', ((('ref', ),),)),
680
(index, ('ref', ), 'refdata', ((), ))]),
681
set(index.iter_all_entries()))
683
def test_iteration_absent_skipped(self):
684
index = self.make_index(1, nodes=[
685
(('name', ), 'data', ([('ref', )], ))])
686
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
687
set(index.iter_all_entries()))
688
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),))]),
689
set(index.iter_entries([('name', )])))
690
self.assertEqual([], list(index.iter_entries([('ref', )])))
692
def test_iter_all_keys(self):
693
index = self.make_index(1, nodes=[
694
(('name', ), 'data', ([('ref', )], )),
695
(('ref', ), 'refdata', ([], ))])
696
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
697
(index, ('ref', ), 'refdata', ((), ))]),
698
set(index.iter_entries([('name', ), ('ref', )])))
700
def test_iter_key_prefix_1_key_element_no_refs(self):
701
index = self.make_index( nodes=[
702
(('name', ), 'data'),
703
(('ref', ), 'refdata')])
704
self.assertEqual(set([(index, ('name', ), 'data'),
705
(index, ('ref', ), 'refdata')]),
706
set(index.iter_entries_prefix([('name', ), ('ref', )])))
708
def test_iter_key_prefix_1_key_element_refs(self):
709
index = self.make_index(1, nodes=[
710
(('name', ), 'data', ([('ref', )], )),
711
(('ref', ), 'refdata', ([], ))])
712
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
713
(index, ('ref', ), 'refdata', ((), ))]),
714
set(index.iter_entries_prefix([('name', ), ('ref', )])))
716
def test_iter_key_prefix_2_key_element_no_refs(self):
717
index = self.make_index(key_elements=2, nodes=[
718
(('name', 'fin1'), 'data'),
719
(('name', 'fin2'), 'beta'),
720
(('ref', 'erence'), 'refdata')])
721
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
722
(index, ('ref', 'erence'), 'refdata')]),
723
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
724
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
725
(index, ('name', 'fin2'), 'beta')]),
726
set(index.iter_entries_prefix([('name', None)])))
728
def test_iter_key_prefix_2_key_element_refs(self):
729
index = self.make_index(1, key_elements=2, nodes=[
730
(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
731
(('name', 'fin2'), 'beta', ([], )),
732
(('ref', 'erence'), 'refdata', ([], ))])
733
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
734
(index, ('ref', 'erence'), 'refdata', ((), ))]),
735
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
736
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
737
(index, ('name', 'fin2'), 'beta', ((), ))]),
738
set(index.iter_entries_prefix([('name', None)])))
740
def test_iter_nothing_empty(self):
741
index = self.make_index()
742
self.assertEqual([], list(index.iter_entries([])))
744
def test_iter_missing_entry_empty(self):
745
index = self.make_index()
746
self.assertEqual([], list(index.iter_entries(['a'])))
748
def test_validate_empty(self):
749
index = self.make_index()
752
def test_validate_no_refs_content(self):
753
index = self.make_index(nodes=[(('key', ), 'value')])
757
class TestGraphIndexPrefixAdapter(TestCaseWithMemoryTransport):
759
def make_index(self, ref_lists=1, key_elements=2, nodes=[], add_callback=False):
760
result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
761
result.add_nodes(nodes)
763
add_nodes_callback=result.add_nodes
765
add_nodes_callback=None
766
adapter = GraphIndexPrefixAdapter(result, ('prefix', ), key_elements - 1,
767
add_nodes_callback=add_nodes_callback)
768
return result, adapter
770
def test_add_node(self):
771
index, adapter = self.make_index(add_callback=True)
772
adapter.add_node(('key',), 'value', ((('ref',),),))
773
self.assertEqual(set([(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))]),
774
set(index.iter_all_entries()))
776
def test_add_nodes(self):
777
index, adapter = self.make_index(add_callback=True)
779
(('key',), 'value', ((('ref',),),)),
780
(('key2',), 'value2', ((),)),
782
self.assertEqual(set([
783
(index, ('prefix', 'key2'), 'value2', ((),)),
784
(index, ('prefix', 'key'), 'value', ((('prefix', 'ref'),),))
786
set(index.iter_all_entries()))
788
def test_construct(self):
789
index = InMemoryGraphIndex()
790
adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1)
792
def test_construct_with_callback(self):
793
index = InMemoryGraphIndex()
794
adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1, index.add_nodes)
796
def test_iter_all_entries_cross_prefix_map_errors(self):
797
index, adapter = self.make_index(nodes=[
798
(('prefix', 'key1'), 'data1', ((('prefixaltered', 'key2'),),))])
799
self.assertRaises(errors.BadIndexData, list, adapter.iter_all_entries())
801
def test_iter_all_entries(self):
802
index, adapter = self.make_index(nodes=[
803
(('notprefix', 'key1'), 'data', ((), )),
804
(('prefix', 'key1'), 'data1', ((), )),
805
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
806
self.assertEqual(set([(index, ('key1', ), 'data1', ((),)),
807
(index, ('key2', ), 'data2', ((('key1',),),))]),
808
set(adapter.iter_all_entries()))
810
def test_iter_entries(self):
811
index, adapter = self.make_index(nodes=[
812
(('notprefix', 'key1'), 'data', ((), )),
813
(('prefix', 'key1'), 'data1', ((), )),
814
(('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
815
# ask for many - get all
816
self.assertEqual(set([(index, ('key1', ), 'data1', ((),)),
817
(index, ('key2', ), 'data2', ((('key1', ),),))]),
818
set(adapter.iter_entries([('key1', ), ('key2', )])))
819
# ask for one, get one
820
self.assertEqual(set([(index, ('key1', ), 'data1', ((),))]),
821
set(adapter.iter_entries([('key1', )])))
822
# ask for missing, get none
823
self.assertEqual(set(),
824
set(adapter.iter_entries([('key3', )])))
826
def test_iter_entries_prefix(self):
827
index, adapter = self.make_index(key_elements=3, nodes=[
828
(('notprefix', 'foo', 'key1'), 'data', ((), )),
829
(('prefix', 'prefix2', 'key1'), 'data1', ((), )),
830
(('prefix', 'prefix2', 'key2'), 'data2', ((('prefix', 'prefix2', 'key1'),),))])
831
# ask for a prefix, get the results for just that prefix, adjusted.
832
self.assertEqual(set([(index, ('prefix2', 'key1', ), 'data1', ((),)),
833
(index, ('prefix2', 'key2', ), 'data2', ((('prefix2', 'key1', ),),))]),
834
set(adapter.iter_entries_prefix([('prefix2', None)])))
836
def test_validate(self):
837
index, adapter = self.make_index()
840
calls.append('called')
841
index.validate = validate
843
self.assertEqual(['called'], calls)
added
removed
bzrlib/tests/test_index.py
