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\n\n", contents)
32
def test_build_index_one_reference_list_empty(self):
33
builder = GraphIndexBuilder(reference_lists=1)
34
stream = builder.finish()
35
contents = stream.read()
36
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\n\n", contents)
38
def test_build_index_two_reference_list_empty(self):
39
builder = GraphIndexBuilder(reference_lists=2)
40
stream = builder.finish()
41
contents = stream.read()
42
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\n\n", contents)
44
def test_build_index_one_node_no_refs(self):
45
builder = GraphIndexBuilder()
46
builder.add_node('akey', 'data')
47
stream = builder.finish()
48
contents = stream.read()
49
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\n"
50
"akey\x00\x00\x00data\n\n", contents)
52
def test_build_index_one_node_no_refs_accepts_empty_reflist(self):
53
builder = GraphIndexBuilder()
54
builder.add_node('akey', 'data', ())
55
stream = builder.finish()
56
contents = stream.read()
57
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\n"
58
"akey\x00\x00\x00data\n\n", contents)
60
def test_add_node_empty_value(self):
61
builder = GraphIndexBuilder()
62
builder.add_node('akey', '')
63
stream = builder.finish()
64
contents = stream.read()
65
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\n"
66
"akey\x00\x00\x00\n\n", contents)
68
def test_build_index_two_nodes_sorted(self):
69
# the highest sorted node comes first.
70
builder = GraphIndexBuilder()
71
# use three to have a good chance of glitching dictionary hash
72
# lookups etc. Insert in randomish order that is not correct
73
# and not the reverse of the correct order.
74
builder.add_node('2002', 'data')
75
builder.add_node('2000', 'data')
76
builder.add_node('2001', 'data')
77
stream = builder.finish()
78
contents = stream.read()
79
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\n"
80
"2000\x00\x00\x00data\n"
81
"2001\x00\x00\x00data\n"
82
"2002\x00\x00\x00data\n"
85
def test_build_index_reference_lists_are_included_one(self):
86
builder = GraphIndexBuilder(reference_lists=1)
87
builder.add_node('key', 'data', ([], ))
88
stream = builder.finish()
89
contents = stream.read()
90
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\n"
91
"key\x00\x00\x00data\n"
94
def test_build_index_reference_lists_are_included_two(self):
95
builder = GraphIndexBuilder(reference_lists=2)
96
builder.add_node('key', 'data', ([], []))
97
stream = builder.finish()
98
contents = stream.read()
99
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\n"
100
"key\x00\x00\t\x00data\n"
103
def test_node_references_are_byte_offsets(self):
104
builder = GraphIndexBuilder(reference_lists=1)
105
builder.add_node('reference', 'data', ([], ))
106
builder.add_node('key', 'data', (['reference'], ))
107
stream = builder.finish()
108
contents = stream.read()
109
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\n"
110
"key\x00\x0051\x00data\n"
111
"reference\x00\x00\x00data\n"
114
def test_node_references_are_cr_delimited(self):
115
builder = GraphIndexBuilder(reference_lists=1)
116
builder.add_node('reference', 'data', ([], ))
117
builder.add_node('reference2', 'data', ([], ))
118
builder.add_node('key', 'data', (['reference', 'reference2'], ))
119
stream = builder.finish()
120
contents = stream.read()
121
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\n"
122
"key\x00\x0054\r71\x00data\n"
123
"reference\x00\x00\x00data\n"
124
"reference2\x00\x00\x00data\n"
127
def test_multiple_reference_lists_are_tab_delimited(self):
128
builder = GraphIndexBuilder(reference_lists=2)
129
builder.add_node('keference', 'data', ([], []))
130
builder.add_node('rey', 'data', (['keference'], ['keference']))
131
stream = builder.finish()
132
contents = stream.read()
133
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\n"
134
"keference\x00\x00\t\x00data\n"
135
"rey\x00\x0038\t38\x00data\n"
138
def test_add_node_referencing_missing_key_makes_absent(self):
139
builder = GraphIndexBuilder(reference_lists=1)
140
builder.add_node('rey', 'data', (['beference', 'aeference2'], ))
141
stream = builder.finish()
142
contents = stream.read()
143
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\n"
144
"aeference2\x00a\x00\x00\n"
145
"beference\x00a\x00\x00\n"
146
"rey\x00\x0053\r38\x00data\n"
149
def test_node_references_three_digits(self):
150
# test the node digit expands as needed.
151
builder = GraphIndexBuilder(reference_lists=1)
152
references = map(str, reversed(range(9)))
153
builder.add_node('2-key', '', (references, ))
154
stream = builder.finish()
155
contents = stream.read()
156
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\n"
160
"2-key\x00\x00130\r124\r118\r112\r106\r100\r050\r044\r038\x00\n"
169
def test_absent_has_no_reference_overhead(self):
170
# the offsets after an absent record should be correct when there are
171
# >1 reference lists.
172
builder = GraphIndexBuilder(reference_lists=2)
173
builder.add_node('parent', '', (['aail', 'zther'], []))
174
stream = builder.finish()
175
contents = stream.read()
176
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\n"
177
"aail\x00a\x00\x00\n"
178
"parent\x00\x0038\r63\t\x00\n"
179
"zther\x00a\x00\x00\n"
182
def test_add_node_bad_key(self):
183
builder = GraphIndexBuilder()
184
for bad_char in '\t\n\x0b\x0c\r\x00 ':
185
self.assertRaises(errors.BadIndexKey, builder.add_node,
186
'a%skey' % bad_char, 'data')
187
self.assertRaises(errors.BadIndexKey, builder.add_node,
190
def test_add_node_bad_data(self):
191
builder = GraphIndexBuilder()
192
self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',
194
self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',
197
def test_add_node_bad_mismatched_ref_lists_length(self):
198
builder = GraphIndexBuilder()
199
self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',
201
builder = GraphIndexBuilder(reference_lists=1)
202
self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',
204
self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',
206
self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',
208
builder = GraphIndexBuilder(reference_lists=2)
209
self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',
211
self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',
213
self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',
214
'data aa', ([], [], []))
216
def test_add_node_bad_key_in_reference_lists(self):
217
# first list, first key - trivial
218
builder = GraphIndexBuilder(reference_lists=1)
219
self.assertRaises(errors.BadIndexKey, builder.add_node, 'akey',
220
'data aa', (['a key'], ))
221
# need to check more than the first key in the list
222
self.assertRaises(errors.BadIndexKey, builder.add_node, 'akey',
223
'data aa', (['agoodkey', 'this is a bad key'], ))
224
# and if there is more than one list it should be getting checked
226
builder = GraphIndexBuilder(reference_lists=2)
227
self.assertRaises(errors.BadIndexKey, builder.add_node, 'akey',
228
'data aa', ([], ['a bad key']))
230
def test_add_duplicate_key(self):
231
builder = GraphIndexBuilder()
232
builder.add_node('key', 'data')
233
self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node, 'key',
236
def test_add_key_after_referencing_key(self):
237
builder = GraphIndexBuilder(reference_lists=1)
238
builder.add_node('key', 'data', (['reference'], ))
239
builder.add_node('reference', 'data', ([],))
242
class TestGraphIndex(TestCaseWithMemoryTransport):
244
def make_index(self, ref_lists=0, nodes=[]):
245
builder = GraphIndexBuilder(ref_lists)
246
for node, value, references in nodes:
247
builder.add_node(node, value, references)
248
stream = builder.finish()
249
trans = self.get_transport()
250
trans.put_file('index', stream)
251
return GraphIndex(trans, 'index')
253
def test_open_bad_index_no_error(self):
254
trans = self.get_transport()
255
trans.put_bytes('name', "not an index\n")
256
index = GraphIndex(trans, 'name')
258
def test_iter_all_entries_empty(self):
259
index = self.make_index()
260
self.assertEqual([], list(index.iter_all_entries()))
262
def test_iter_all_entries_simple(self):
263
index = self.make_index(nodes=[('name', 'data', ())])
264
self.assertEqual([('name', 'data')],
265
list(index.iter_all_entries()))
267
def test_iter_all_entries_references_resolved(self):
268
index = self.make_index(1, nodes=[
269
('name', 'data', (['ref'], )),
270
('ref', 'refdata', ([], ))])
271
self.assertEqual(set([('name', 'data', (('ref',),)),
272
('ref', 'refdata', ((), ))]),
273
set(index.iter_all_entries()))
275
def test_iteration_absent_skipped(self):
276
index = self.make_index(1, nodes=[
277
('name', 'data', (['ref'], ))])
278
self.assertEqual(set([('name', 'data', (('ref',),))]),
279
set(index.iter_all_entries()))
280
self.assertEqual(set([('name', 'data', (('ref',),))]),
281
set(index.iter_entries(['name'])))
282
self.assertEqual([], list(index.iter_entries(['ref'])))
284
def test_iter_all_keys(self):
285
index = self.make_index(1, nodes=[
286
('name', 'data', (['ref'], )),
287
('ref', 'refdata', ([], ))])
288
self.assertEqual(set([('name', 'data', (('ref',),)),
289
('ref', 'refdata', ((), ))]),
290
set(index.iter_entries(['name', 'ref'])))
292
def test_iter_nothing_empty(self):
293
index = self.make_index()
294
self.assertEqual([], list(index.iter_entries([])))
296
def test_iter_missing_entry_empty(self):
297
index = self.make_index()
298
self.assertEqual([], list(index.iter_entries(['a'])))
300
def test_validate_bad_index_errors(self):
301
trans = self.get_transport()
302
trans.put_bytes('name', "not an index\n")
303
index = GraphIndex(trans, 'name')
304
self.assertRaises(errors.BadIndexFormatSignature, index.validate)
306
def test_validate_bad_node_refs(self):
307
index = self.make_index(2)
308
trans = self.get_transport()
309
content = trans.get_bytes('index')
310
# change the options line to end with a rather than a parseable number
311
new_content = content[:-2] + 'a\n\n'
312
trans.put_bytes('index', new_content)
313
self.assertRaises(errors.BadIndexOptions, index.validate)
315
def test_validate_missing_end_line_empty(self):
316
index = self.make_index(2)
317
trans = self.get_transport()
318
content = trans.get_bytes('index')
319
# truncate the last byte
320
trans.put_bytes('index', content[:-1])
321
self.assertRaises(errors.BadIndexData, index.validate)
323
def test_validate_missing_end_line_nonempty(self):
324
index = self.make_index(2, [('key', '', ([], []))])
325
trans = self.get_transport()
326
content = trans.get_bytes('index')
327
# truncate the last byte
328
trans.put_bytes('index', content[:-1])
329
self.assertRaises(errors.BadIndexData, index.validate)
331
def test_validate_empty(self):
332
index = self.make_index()
335
def test_validate_no_refs_content(self):
336
index = self.make_index(nodes=[('key', 'value', ())])
340
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
342
def make_index(self, name, ref_lists=0, nodes=[]):
343
builder = GraphIndexBuilder(ref_lists)
344
for node, value, references in nodes:
345
builder.add_node(node, value, references)
346
stream = builder.finish()
347
trans = self.get_transport()
348
trans.put_file(name, stream)
349
return GraphIndex(trans, name)
351
def test_open_missing_index_no_error(self):
352
trans = self.get_transport()
353
index1 = GraphIndex(trans, 'missing')
354
index = CombinedGraphIndex([index1])
356
def test_add_index(self):
357
index = CombinedGraphIndex([])
358
index1 = self.make_index('name', 0, nodes=[('key', '', ())])
359
index.insert_index(0, index1)
360
self.assertEqual([('key', '')], list(index.iter_all_entries()))
362
def test_iter_all_entries_empty(self):
363
index = CombinedGraphIndex([])
364
self.assertEqual([], list(index.iter_all_entries()))
366
def test_iter_all_entries_children_empty(self):
367
index1 = self.make_index('name')
368
index = CombinedGraphIndex([index1])
369
self.assertEqual([], list(index.iter_all_entries()))
371
def test_iter_all_entries_simple(self):
372
index1 = self.make_index('name', nodes=[('name', 'data', ())])
373
index = CombinedGraphIndex([index1])
374
self.assertEqual([('name', 'data')],
375
list(index.iter_all_entries()))
377
def test_iter_all_entries_two_indices(self):
378
index1 = self.make_index('name1', nodes=[('name', 'data', ())])
379
index2 = self.make_index('name2', nodes=[('2', '', ())])
380
index = CombinedGraphIndex([index1, index2])
381
self.assertEqual([('name', 'data'),
383
list(index.iter_all_entries()))
385
def test_iter_entries_two_indices_dup_key(self):
386
index1 = self.make_index('name1', nodes=[('name', 'data', ())])
387
index2 = self.make_index('name2', nodes=[('name', 'data', ())])
388
index = CombinedGraphIndex([index1, index2])
389
self.assertEqual([('name', 'data')],
390
list(index.iter_entries(['name'])))
392
def test_iter_all_entries_two_indices_dup_key(self):
393
index1 = self.make_index('name1', nodes=[('name', 'data', ())])
394
index2 = self.make_index('name2', nodes=[('name', 'data', ())])
395
index = CombinedGraphIndex([index1, index2])
396
self.assertEqual([('name', 'data')],
397
list(index.iter_all_entries()))
399
def test_iter_nothing_empty(self):
400
index = CombinedGraphIndex([])
401
self.assertEqual([], list(index.iter_entries([])))
403
def test_iter_nothing_children_empty(self):
404
index1 = self.make_index('name')
405
index = CombinedGraphIndex([index1])
406
self.assertEqual([], list(index.iter_entries([])))
408
def test_iter_all_keys(self):
409
index1 = self.make_index('1', 1, nodes=[
410
('name', 'data', (['ref'], ))])
411
index2 = self.make_index('2', 1, nodes=[
412
('ref', 'refdata', ((), ))])
413
index = CombinedGraphIndex([index1, index2])
414
self.assertEqual(set([('name', 'data', (('ref', ), )),
415
('ref', 'refdata', ((), ))]),
416
set(index.iter_entries(['name', 'ref'])))
418
def test_iter_all_keys_dup_entry(self):
419
index1 = self.make_index('1', 1, nodes=[
420
('name', 'data', (['ref'], )),
421
('ref', 'refdata', ([], ))])
422
index2 = self.make_index('2', 1, nodes=[
423
('ref', 'refdata', ([], ))])
424
index = CombinedGraphIndex([index1, index2])
425
self.assertEqual(set([('name', 'data', (('ref',),)),
426
('ref', 'refdata', ((), ))]),
427
set(index.iter_entries(['name', 'ref'])))
429
def test_iter_missing_entry_empty(self):
430
index = CombinedGraphIndex([])
431
self.assertEqual([], list(index.iter_entries(['a'])))
433
def test_iter_missing_entry_one_index(self):
434
index1 = self.make_index('1')
435
index = CombinedGraphIndex([index1])
436
self.assertEqual([], list(index.iter_entries(['a'])))
438
def test_iter_missing_entry_two_index(self):
439
index1 = self.make_index('1')
440
index2 = self.make_index('2')
441
index = CombinedGraphIndex([index1, index2])
442
self.assertEqual([], list(index.iter_entries(['a'])))
444
def test_iter_entry_present_one_index_only(self):
445
index1 = self.make_index('1', nodes=[('key', '', ())])
446
index2 = self.make_index('2', nodes=[])
447
index = CombinedGraphIndex([index1, index2])
448
self.assertEqual([('key', '')],
449
list(index.iter_entries(['key'])))
450
# and in the other direction
451
index = CombinedGraphIndex([index2, index1])
452
self.assertEqual([('key', '')],
453
list(index.iter_entries(['key'])))
455
def test_validate_bad_child_index_errors(self):
456
trans = self.get_transport()
457
trans.put_bytes('name', "not an index\n")
458
index1 = GraphIndex(trans, 'name')
459
index = CombinedGraphIndex([index1])
460
self.assertRaises(errors.BadIndexFormatSignature, index.validate)
462
def test_validate_empty(self):
463
index = CombinedGraphIndex([])
467
class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):
469
def make_index(self, ref_lists=0, nodes=[]):
470
result = InMemoryGraphIndex(ref_lists)
471
result.add_nodes(nodes)
474
def test_add_nodes(self):
475
index = self.make_index(1)
476
index.add_nodes([('name', 'data', ([],))])
477
index.add_nodes([('name2', '', ([],)), ('name3', '', (['r'],))])
478
self.assertEqual(set([
479
('name', 'data', ((),)),
480
('name2', '', ((),)),
481
('name3', '', (('r',),)),
482
]), set(index.iter_all_entries()))
484
def test_iter_all_entries_empty(self):
485
index = self.make_index()
486
self.assertEqual([], list(index.iter_all_entries()))
488
def test_iter_all_entries_simple(self):
489
index = self.make_index(nodes=[('name', 'data', ())])
490
self.assertEqual([('name', 'data')],
491
list(index.iter_all_entries()))
493
def test_iter_all_entries_references(self):
494
index = self.make_index(1, nodes=[
495
('name', 'data', (['ref'], )),
496
('ref', 'refdata', ([], ))])
497
self.assertEqual(set([('name', 'data', (('ref',),)),
498
('ref', 'refdata', ((), ))]),
499
set(index.iter_all_entries()))
501
def test_iteration_absent_skipped(self):
502
index = self.make_index(1, nodes=[
503
('name', 'data', (['ref'], ))])
504
self.assertEqual(set([('name', 'data', (('ref',),))]),
505
set(index.iter_all_entries()))
506
self.assertEqual(set([('name', 'data', (('ref',),))]),
507
set(index.iter_entries(['name'])))
508
self.assertEqual([], list(index.iter_entries(['ref'])))
510
def test_iter_all_keys(self):
511
index = self.make_index(1, nodes=[
512
('name', 'data', (['ref'], )),
513
('ref', 'refdata', ([], ))])
514
self.assertEqual(set([('name', 'data', (('ref',),)),
515
('ref', 'refdata', ((), ))]),
516
set(index.iter_entries(['name', 'ref'])))
518
def test_iter_nothing_empty(self):
519
index = self.make_index()
520
self.assertEqual([], list(index.iter_entries([])))
522
def test_iter_missing_entry_empty(self):
523
index = self.make_index()
524
self.assertEqual([], list(index.iter_entries(['a'])))
526
def test_validate_empty(self):
527
index = self.make_index()
530
def test_validate_no_refs_content(self):
531
index = self.make_index(nodes=[('key', 'value', ())])
added
removed
bzrlib/tests/test_index.py
