← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_index.py

Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_index.py
29
29
        contents = stream.read()
30
30
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n\n", contents)
31
31
 
 
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)
 
37
 
32
38
    def test_build_index_one_reference_list_empty(self):
33
39
        builder = GraphIndexBuilder(reference_lists=1)
34
40
        stream = builder.finish()
57
63
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n"
58
64
            "akey\x00\x00\x00data\n\n", contents)
59
65
 
 
66
    def test_build_index_one_node_2_element_keys(self):
 
67
        builder = GraphIndexBuilder(key_elements=2)
 
68
        builder.add_node(('akey', 'secondpart'), 'data')
 
69
        stream = builder.finish()
 
70
        contents = stream.read()
 
71
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\n"
 
72
            "akey\x00secondpart\x00\x00\x00data\n\n", contents)
 
73
 
60
74
    def test_add_node_empty_value(self):
61
75
        builder = GraphIndexBuilder()
62
76
        builder.add_node(('akey', ), '')
65
79
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n"
66
80
            "akey\x00\x00\x00\n\n", contents)
67
81
 
68
 
    def test_build_index_two_nodes_sorted(self):
 
82
    def test_build_index_nodes_sorted(self):
69
83
        # the highest sorted node comes first.
70
84
        builder = GraphIndexBuilder()
71
85
        # use three to have a good chance of glitching dictionary hash
82
96
            "2002\x00\x00\x00data\n"
83
97
            "\n", contents)
84
98
 
 
99
    def test_build_index_2_element_key_nodes_sorted(self):
 
100
        # multiple element keys are sorted first-key, second-key.
 
101
        builder = GraphIndexBuilder(key_elements=2)
 
102
        # use three values of each key element, to have a good chance of
 
103
        # glitching dictionary hash lookups etc. Insert in randomish order that
 
104
        # is not correct and not the reverse of the correct order.
 
105
        builder.add_node(('2002', '2002'), 'data')
 
106
        builder.add_node(('2002', '2000'), 'data')
 
107
        builder.add_node(('2002', '2001'), 'data')
 
108
        builder.add_node(('2000', '2002'), 'data')
 
109
        builder.add_node(('2000', '2000'), 'data')
 
110
        builder.add_node(('2000', '2001'), 'data')
 
111
        builder.add_node(('2001', '2002'), 'data')
 
112
        builder.add_node(('2001', '2000'), 'data')
 
113
        builder.add_node(('2001', '2001'), 'data')
 
114
        stream = builder.finish()
 
115
        contents = stream.read()
 
116
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\n"
 
117
            "2000\x002000\x00\x00\x00data\n"
 
118
            "2000\x002001\x00\x00\x00data\n"
 
119
            "2000\x002002\x00\x00\x00data\n"
 
120
            "2001\x002000\x00\x00\x00data\n"
 
121
            "2001\x002001\x00\x00\x00data\n"
 
122
            "2001\x002002\x00\x00\x00data\n"
 
123
            "2002\x002000\x00\x00\x00data\n"
 
124
            "2002\x002001\x00\x00\x00data\n"
 
125
            "2002\x002002\x00\x00\x00data\n"
 
126
            "\n", contents)
 
127
 
85
128
    def test_build_index_reference_lists_are_included_one(self):
86
129
        builder = GraphIndexBuilder(reference_lists=1)
87
130
        builder.add_node(('key', ), 'data', ([], ))
91
134
            "key\x00\x00\x00data\n"
92
135
            "\n", contents)
93
136
 
 
137
    def test_build_index_reference_lists_with_2_element_keys(self):
 
138
        builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
 
139
        builder.add_node(('key', 'key2'), 'data', ([], ))
 
140
        stream = builder.finish()
 
141
        contents = stream.read()
 
142
        self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=2\n"
 
143
            "key\x00key2\x00\x00\x00data\n"
 
144
            "\n", contents)
 
145
 
94
146
    def test_build_index_reference_lists_are_included_two(self):
95
147
        builder = GraphIndexBuilder(reference_lists=2)
96
148
        builder.add_node(('key', ), 'data', ([], []))
194
246
        # too long
195
247
        self.assertRaises(errors.BadIndexKey, builder.add_node,
196
248
                ('primary', 'secondary'), 'data')
 
249
        # secondary key elements get checked too:
 
250
        builder = GraphIndexBuilder(key_elements=2)
 
251
        for bad_char in '\t\n\x0b\x0c\r\x00 ':
 
252
            self.assertRaises(errors.BadIndexKey, builder.add_node,
 
253
                ('prefix', 'a%skey' % bad_char), 'data')
197
254
 
198
255
    def test_add_node_bad_data(self):
199
256
        builder = GraphIndexBuilder()
250
307
        self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node, ('key', ),
251
308
            'data')
252
309
 
 
310
    def test_add_duplicate_key_2_elements(self):
 
311
        builder = GraphIndexBuilder(key_elements=2)
 
312
        builder.add_node(('key', 'key'), 'data')
 
313
        self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node,
 
314
            ('key', 'key'), 'data')
 
315
 
253
316
    def test_add_key_after_referencing_key(self):
254
317
        builder = GraphIndexBuilder(reference_lists=1)
255
318
        builder.add_node(('key', ), 'data', ([('reference', )], ))
256
319
        builder.add_node(('reference', ), 'data', ([],))
257
320
 
 
321
    def test_add_key_after_referencing_key_2_elements(self):
 
322
        builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
 
323
        builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
 
324
        builder.add_node(('reference', 'tokey'), 'data', ([],))
 
325
 
258
326
 
259
327
class TestGraphIndex(TestCaseWithMemoryTransport):
260
328
 
261
 
    def make_index(self, ref_lists=0, nodes=[]):
262
 
        builder = GraphIndexBuilder(ref_lists)
 
329
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
 
330
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
263
331
        for node, value, references in nodes:
264
332
            builder.add_node(node, value, references)
265
333
        stream = builder.finish()
281
349
        self.assertEqual([(('name', ), 'data')],
282
350
            list(index.iter_all_entries()))
283
351
 
 
352
    def test_iter_all_entries_simple_2_elements(self):
 
353
        index = self.make_index(key_elements=2,
 
354
            nodes=[(('name', 'surname'), 'data', ())])
 
355
        self.assertEqual([(('name', 'surname'), 'data')],
 
356
            list(index.iter_all_entries()))
 
357
 
284
358
    def test_iter_all_entries_references_resolved(self):
285
359
        index = self.make_index(1, nodes=[
286
360
            (('name', ), 'data', ([('ref', )], )),
298
372
            set(index.iter_entries([('name', )])))
299
373
        self.assertEqual([], list(index.iter_entries([('ref', )])))
300
374
 
 
375
    def test_iteration_absent_skipped_2_element_keys(self):
 
376
        index = self.make_index(1, key_elements=2, nodes=[
 
377
            (('name', 'fin'), 'data', ([('ref', 'erence')], ))])
 
378
        self.assertEqual(set([(('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
 
379
            set(index.iter_all_entries()))
 
380
        self.assertEqual(set([(('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
 
381
            set(index.iter_entries([('name', 'fin')])))
 
382
        self.assertEqual([], list(index.iter_entries([('ref', 'erence')])))
 
383
 
301
384
    def test_iter_all_keys(self):
302
385
        index = self.make_index(1, nodes=[
303
386
            (('name', ), 'data', ([('ref', )], )),
314
397
        index = self.make_index()
315
398
        self.assertEqual([], list(index.iter_entries([('a', )])))
316
399
 
 
400
    def test_iter_key_prefix_1_element_key_None(self):
 
401
        index = self.make_index()
 
402
        self.assertRaises(errors.BadIndexKey, list,
 
403
            index.iter_entries_prefix([(None, )]))
 
404
 
 
405
    def test_iter_key_prefix_wrong_length(self):
 
406
        index = self.make_index()
 
407
        self.assertRaises(errors.BadIndexKey, list,
 
408
            index.iter_entries_prefix([('foo', None)]))
 
409
        index = self.make_index(key_elements=2)
 
410
        self.assertRaises(errors.BadIndexKey, list,
 
411
            index.iter_entries_prefix([('foo', )]))
 
412
        self.assertRaises(errors.BadIndexKey, list,
 
413
            index.iter_entries_prefix([('foo', None, None)]))
 
414
 
 
415
    def test_iter_key_prefix_1_key_element_no_refs(self):
 
416
        index = self.make_index( nodes=[
 
417
            (('name', ), 'data', ()),
 
418
            (('ref', ), 'refdata', ())])
 
419
        self.assertEqual(set([(('name', ), 'data'),
 
420
            (('ref', ), 'refdata')]),
 
421
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
 
422
 
 
423
    def test_iter_key_prefix_1_key_element_refs(self):
 
424
        index = self.make_index(1, nodes=[
 
425
            (('name', ), 'data', ([('ref', )], )),
 
426
            (('ref', ), 'refdata', ([], ))])
 
427
        self.assertEqual(set([(('name', ), 'data', ((('ref',),),)),
 
428
            (('ref', ), 'refdata', ((), ))]),
 
429
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
 
430
 
 
431
    def test_iter_key_prefix_2_key_element_no_refs(self):
 
432
        index = self.make_index(key_elements=2, nodes=[
 
433
            (('name', 'fin1'), 'data', ()),
 
434
            (('name', 'fin2'), 'beta', ()),
 
435
            (('ref', 'erence'), 'refdata', ())])
 
436
        self.assertEqual(set([(('name', 'fin1'), 'data'),
 
437
            (('ref', 'erence'), 'refdata')]),
 
438
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
 
439
        self.assertEqual(set([(('name', 'fin1'), 'data'),
 
440
            (('name', 'fin2'), 'beta')]),
 
441
            set(index.iter_entries_prefix([('name', None)])))
 
442
 
 
443
    def test_iter_key_prefix_2_key_element_refs(self):
 
444
        index = self.make_index(1, key_elements=2, nodes=[
 
445
            (('name', 'fin1'), 'data', ([('ref', 'erence')], )),
 
446
            (('name', 'fin2'), 'beta', ([], )),
 
447
            (('ref', 'erence'), 'refdata', ([], ))])
 
448
        self.assertEqual(set([(('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
449
            (('ref', 'erence'), 'refdata', ((), ))]),
 
450
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
 
451
        self.assertEqual(set([(('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
452
            (('name', 'fin2'), 'beta', ((), ))]),
 
453
            set(index.iter_entries_prefix([('name', None)])))
 
454
 
317
455
    def test_validate_bad_index_errors(self):
318
456
        trans = self.get_transport()
319
457
        trans.put_bytes('name', "not an index\n")
338
476
        self.assertRaises(errors.BadIndexData, index.validate)
339
477
 
340
478
    def test_validate_missing_end_line_nonempty(self):
341
 
        index = self.make_index(2, [(('key', ), '', ([], []))])
 
479
        index = self.make_index(2, nodes=[(('key', ), '', ([], []))])
342
480
        trans = self.get_transport()
343
481
        content = trans.get_bytes('index')
344
482
        # truncate the last byte
356
494
 
357
495
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
358
496
 
359
 
    def make_index(self, name, ref_lists=0, nodes=[]):
360
 
        builder = GraphIndexBuilder(ref_lists)
 
497
    def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
 
498
        builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
361
499
        for node, value, references in nodes:
362
500
            builder.add_node(node, value, references)
363
501
        stream = builder.finish()
413
551
        self.assertEqual([(('name', ), 'data')],
414
552
            list(index.iter_all_entries()))
415
553
 
 
554
    def test_iter_key_prefix_2_key_element_refs(self):
 
555
        index1 = self.make_index('1', 1, key_elements=2, nodes=[
 
556
            (('name', 'fin1'), 'data', ([('ref', 'erence')], ))])
 
557
        index2 = self.make_index('2', 1, key_elements=2, nodes=[
 
558
            (('name', 'fin2'), 'beta', ([], )),
 
559
            (('ref', 'erence'), 'refdata', ([], ))])
 
560
        index = CombinedGraphIndex([index1, index2])
 
561
        self.assertEqual(set([(('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
562
            (('ref', 'erence'), 'refdata', ((), ))]),
 
563
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
 
564
        self.assertEqual(set([(('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
565
            (('name', 'fin2'), 'beta', ((), ))]),
 
566
            set(index.iter_entries_prefix([('name', None)])))
 
567
 
416
568
    def test_iter_nothing_empty(self):
417
569
        index = CombinedGraphIndex([])
418
570
        self.assertEqual([], list(index.iter_entries([])))