← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_btree_index.py

(vila) Fix test failures blocking package builds. (Vincent Ladeuil)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
1
 
# Copyright (C) 2008, 2009 Canonical Ltd
 
1
# Copyright (C) 2008-2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
23
23
from bzrlib import (
24
24
    btree_index,
25
25
    errors,
 
26
    fifo_cache,
 
27
    lru_cache,
26
28
    osutils,
27
29
    tests,
 
30
    transport,
28
31
    )
29
32
from bzrlib.tests import (
30
33
    TestCaseWithTransport,
31
 
    condition_isinstance,
32
 
    multiply_tests,
33
 
    split_suite_by_condition,
34
 
    )
35
 
from bzrlib.transport import get_transport
36
 
 
37
 
 
38
 
def load_tests(standard_tests, module, loader):
39
 
    # parameterise the TestBTreeNodes tests
40
 
    node_tests, others = split_suite_by_condition(standard_tests,
41
 
        condition_isinstance(TestBTreeNodes))
 
34
    scenarios,
 
35
    )
 
36
from bzrlib.tests import (
 
37
    features,
 
38
    )
 
39
 
 
40
 
 
41
load_tests = scenarios.load_tests_apply_scenarios
 
42
 
 
43
 
 
44
def btreeparser_scenarios():
42
45
    import bzrlib._btree_serializer_py as py_module
43
46
    scenarios = [('python', {'parse_btree': py_module})]
44
 
    if CompiledBtreeParserFeature.available():
45
 
        # Is there a way to do this that gets missing feature failures rather
46
 
        # than no indication to the user?
47
 
        import bzrlib._btree_serializer_pyx as c_module
48
 
        scenarios.append(('C', {'parse_btree': c_module}))
49
 
    return multiply_tests(node_tests, scenarios, others)
50
 
 
51
 
 
52
 
class _CompiledBtreeParserFeature(tests.Feature):
53
 
    def _probe(self):
54
 
        try:
55
 
            import bzrlib._btree_serializer_pyx
56
 
        except ImportError:
57
 
            return False
58
 
        return True
59
 
 
60
 
    def feature_name(self):
61
 
        return 'bzrlib._btree_serializer_pyx'
62
 
 
63
 
CompiledBtreeParserFeature = _CompiledBtreeParserFeature()
 
47
    if compiled_btreeparser_feature.available():
 
48
        scenarios.append(('C', 
 
49
            {'parse_btree': compiled_btreeparser_feature.module}))
 
50
    return scenarios
 
51
 
 
52
 
 
53
compiled_btreeparser_feature = features.ModuleAvailableFeature(
 
54
    'bzrlib._btree_serializer_pyx')
64
55
 
65
56
 
66
57
class BTreeTestCase(TestCaseWithTransport):
68
59
    # that they test.
69
60
 
70
61
    def setUp(self):
71
 
        TestCaseWithTransport.setUp(self)
72
 
        self._original_header = btree_index._RESERVED_HEADER_BYTES
73
 
        def restore():
74
 
            btree_index._RESERVED_HEADER_BYTES = self._original_header
75
 
        self.addCleanup(restore)
76
 
        btree_index._RESERVED_HEADER_BYTES = 100
 
62
        super(BTreeTestCase, self).setUp()
 
63
        self.overrideAttr(btree_index, '_RESERVED_HEADER_BYTES', 100)
77
64
 
78
65
    def make_nodes(self, count, key_elements, reference_lists):
79
66
        """Generate count*key_elements sample nodes."""
113
100
 
114
101
    def shrink_page_size(self):
115
102
        """Shrink the default page size so that less fits in a page."""
116
 
        old_page_size = btree_index._PAGE_SIZE
117
 
        def cleanup():
118
 
            btree_index._PAGE_SIZE = old_page_size
119
 
        self.addCleanup(cleanup)
 
103
        self.overrideAttr(btree_index, '_PAGE_SIZE')
120
104
        btree_index._PAGE_SIZE = 2048
121
105
 
 
106
    def assertEqualsApproxCompressed(self, expected, actual, slop=6):
 
107
        """Check a count of compressed bytes is approximately as expected
 
108
 
 
109
        Relying on compressed length being stable even with fixed inputs is
 
110
        slightly bogus, but zlib is stable enough that this mostly works.
 
111
        """
 
112
        if not expected - slop < actual < expected + slop:
 
113
            self.fail("Expected around %d bytes compressed but got %d" %
 
114
                (expected, actual))
 
115
 
122
116
 
123
117
class TestBTreeBuilder(BTreeTestCase):
124
118
 
 
119
    def test_clear_cache(self):
 
120
        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)
 
121
        # This is a no-op, but we need the api to be consistent with other
 
122
        # BTreeGraphIndex apis.
 
123
        builder.clear_cache()
 
124
 
125
125
    def test_empty_1_0(self):
126
126
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
127
127
        # NamedTemporaryFile dies on builder.finish().read(). weird.
153
153
        temp_file = builder.finish()
154
154
        content = temp_file.read()
155
155
        del temp_file
156
 
        self.assertEqual(158, len(content))
 
156
        self.assertEqual(131, len(content))
157
157
        self.assertEqual(
158
158
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"
159
159
            "row_lengths=1\n",
177
177
        temp_file = builder.finish()
178
178
        content = temp_file.read()
179
179
        del temp_file
180
 
        self.assertEqual(264, len(content))
 
180
        self.assertEqual(238, len(content))
181
181
        self.assertEqual(
182
182
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"
183
183
            "row_lengths=1\n",
209
209
        temp_file = builder.finish()
210
210
        content = temp_file.read()
211
211
        del temp_file
212
 
        self.assertEqual(9283, len(content))
 
212
        self.assertEqualsApproxCompressed(9283, len(content))
213
213
        self.assertEqual(
214
214
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
215
215
            "row_lengths=1,2\n",
227
227
        leaf1_bytes = zlib.decompress(leaf1)
228
228
        sorted_node_keys = sorted(node[0] for node in nodes)
229
229
        node = btree_index._LeafNode(leaf1_bytes, 1, 0)
230
 
        self.assertEqual(231, len(node.keys))
231
 
        self.assertEqual(sorted_node_keys[:231], sorted(node.keys))
 
230
        self.assertEqual(231, len(node))
 
231
        self.assertEqual(sorted_node_keys[:231], node.all_keys())
232
232
        leaf2_bytes = zlib.decompress(leaf2)
233
233
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
234
 
        self.assertEqual(400 - 231, len(node.keys))
235
 
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
 
234
        self.assertEqual(400 - 231, len(node))
 
235
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
236
236
 
237
237
    def test_last_page_rounded_1_layer(self):
238
238
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
243
243
        temp_file = builder.finish()
244
244
        content = temp_file.read()
245
245
        del temp_file
246
 
        self.assertEqual(181, len(content))
 
246
        self.assertEqualsApproxCompressed(155, len(content))
247
247
        self.assertEqual(
248
248
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
249
249
            "row_lengths=1\n",
252
252
        leaf2 = content[74:]
253
253
        leaf2_bytes = zlib.decompress(leaf2)
254
254
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
255
 
        self.assertEqual(10, len(node.keys))
 
255
        self.assertEqual(10, len(node))
256
256
        sorted_node_keys = sorted(node[0] for node in nodes)
257
 
        self.assertEqual(sorted_node_keys, sorted(node.keys))
 
257
        self.assertEqual(sorted_node_keys, node.all_keys())
258
258
 
259
259
    def test_last_page_not_rounded_2_layer(self):
260
260
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
265
265
        temp_file = builder.finish()
266
266
        content = temp_file.read()
267
267
        del temp_file
268
 
        self.assertEqual(9283, len(content))
 
268
        self.assertEqualsApproxCompressed(9283, len(content))
269
269
        self.assertEqual(
270
270
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
271
271
            "row_lengths=1,2\n",
274
274
        leaf2 = content[8192:]
275
275
        leaf2_bytes = zlib.decompress(leaf2)
276
276
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
277
 
        self.assertEqual(400 - 231, len(node.keys))
 
277
        self.assertEqual(400 - 231, len(node))
278
278
        sorted_node_keys = sorted(node[0] for node in nodes)
279
 
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
 
279
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
280
280
 
281
281
    def test_three_level_tree_details(self):
282
282
        # The left most pointer in the second internal node in a row should
291
291
 
292
292
        for node in nodes:
293
293
            builder.add_node(*node)
294
 
        transport = get_transport('trace+' + self.get_url(''))
295
 
        size = transport.put_file('index', self.time(builder.finish))
 
294
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
295
        size = t.put_file('index', self.time(builder.finish))
296
296
        del builder
297
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
297
        index = btree_index.BTreeGraphIndex(t, 'index', size)
298
298
        # Seed the metadata, we're using internal calls now.
299
299
        index.key_count()
300
300
        self.assertEqual(3, len(index._row_lengths),
313
313
        # in the second node it points at
314
314
        pos = index._row_offsets[2] + internal_node2.offset + 1
315
315
        leaf = index._get_leaf_nodes([pos])[pos]
316
 
        self.assertTrue(internal_node2.keys[0] in leaf.keys)
 
316
        self.assertTrue(internal_node2.keys[0] in leaf)
317
317
 
318
318
    def test_2_leaves_2_2(self):
319
319
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
324
324
        temp_file = builder.finish()
325
325
        content = temp_file.read()
326
326
        del temp_file
327
 
        self.assertEqual(12643, len(content))
 
327
        self.assertEqualsApproxCompressed(12643, len(content))
328
328
        self.assertEqual(
329
329
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
330
330
            "row_lengths=1,3\n",
351
351
        # Test the parts of the index that take up memory are doing so
352
352
        # predictably.
353
353
        self.assertEqual(1, len(builder._nodes))
354
 
        self.assertEqual(1, len(builder._keys))
355
354
        self.assertIs(None, builder._nodes_by_key)
356
355
        builder.add_node(*nodes[1])
357
356
        self.assertEqual(0, len(builder._nodes))
358
 
        self.assertEqual(0, len(builder._keys))
359
357
        self.assertIs(None, builder._nodes_by_key)
360
358
        self.assertEqual(1, len(builder._backing_indices))
361
359
        self.assertEqual(2, builder._backing_indices[0].key_count())
362
360
        # now back to memory
363
361
        builder.add_node(*nodes[2])
364
362
        self.assertEqual(1, len(builder._nodes))
365
 
        self.assertEqual(1, len(builder._keys))
366
363
        self.assertIs(None, builder._nodes_by_key)
367
364
        # And spills to a second backing index combing all
368
365
        builder.add_node(*nodes[3])
369
366
        self.assertEqual(0, len(builder._nodes))
370
 
        self.assertEqual(0, len(builder._keys))
371
367
        self.assertIs(None, builder._nodes_by_key)
372
368
        self.assertEqual(2, len(builder._backing_indices))
373
369
        self.assertEqual(None, builder._backing_indices[0])
376
372
        builder.add_node(*nodes[4])
377
373
        builder.add_node(*nodes[5])
378
374
        self.assertEqual(0, len(builder._nodes))
379
 
        self.assertEqual(0, len(builder._keys))
380
375
        self.assertIs(None, builder._nodes_by_key)
381
376
        self.assertEqual(2, len(builder._backing_indices))
382
377
        self.assertEqual(2, builder._backing_indices[0].key_count())
425
420
        self.assertEqual(None, builder._backing_indices[2])
426
421
        self.assertEqual(16, builder._backing_indices[3].key_count())
427
422
        # Now finish, and check we got a correctly ordered tree
428
 
        transport = self.get_transport('')
429
 
        size = transport.put_file('index', builder.finish())
430
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
423
        t = self.get_transport('')
 
424
        size = t.put_file('index', builder.finish())
 
425
        index = btree_index.BTreeGraphIndex(t, 'index', size)
431
426
        nodes = list(index.iter_all_entries())
432
427
        self.assertEqual(sorted(nodes), nodes)
433
428
        self.assertEqual(16, len(nodes))
440
435
        # Test the parts of the index that take up memory are doing so
441
436
        # predictably.
442
437
        self.assertEqual(1, len(builder._nodes))
443
 
        self.assertEqual(1, len(builder._keys))
444
438
        self.assertIs(None, builder._nodes_by_key)
445
439
        builder.add_node(*nodes[1])
446
440
        self.assertEqual(0, len(builder._nodes))
447
 
        self.assertEqual(0, len(builder._keys))
448
441
        self.assertIs(None, builder._nodes_by_key)
449
442
        self.assertEqual(1, len(builder._backing_indices))
450
443
        self.assertEqual(2, builder._backing_indices[0].key_count())
451
444
        # now back to memory
452
445
        builder.add_node(*nodes[2])
453
446
        self.assertEqual(1, len(builder._nodes))
454
 
        self.assertEqual(1, len(builder._keys))
455
447
        self.assertIs(None, builder._nodes_by_key)
456
448
        # And spills to a second backing index but doesn't combine
457
449
        builder.add_node(*nodes[3])
458
450
        self.assertEqual(0, len(builder._nodes))
459
 
        self.assertEqual(0, len(builder._keys))
460
451
        self.assertIs(None, builder._nodes_by_key)
461
452
        self.assertEqual(2, len(builder._backing_indices))
462
453
        for backing_index in builder._backing_indices:
465
456
        builder.add_node(*nodes[4])
466
457
        builder.add_node(*nodes[5])
467
458
        self.assertEqual(0, len(builder._nodes))
468
 
        self.assertEqual(0, len(builder._keys))
469
459
        self.assertIs(None, builder._nodes_by_key)
470
460
        self.assertEqual(3, len(builder._backing_indices))
471
461
        for backing_index in builder._backing_indices:
530
520
        builder.add_node(*nodes[0])
531
521
        # Test the parts of the index that take up memory are doing so
532
522
        # predictably.
533
 
        self.assertEqual(1, len(builder._keys))
534
523
        self.assertEqual(1, len(builder._nodes))
535
524
        self.assertIs(None, builder._nodes_by_key)
536
525
        builder.add_node(*nodes[1])
537
 
        self.assertEqual(0, len(builder._keys))
538
526
        self.assertEqual(0, len(builder._nodes))
539
527
        self.assertIs(None, builder._nodes_by_key)
540
528
        self.assertEqual(1, len(builder._backing_indices))
543
531
        old = dict(builder._get_nodes_by_key()) #Build up the nodes by key dict
544
532
        builder.add_node(*nodes[2])
545
533
        self.assertEqual(1, len(builder._nodes))
546
 
        self.assertEqual(1, len(builder._keys))
547
534
        self.assertIsNot(None, builder._nodes_by_key)
548
535
        self.assertNotEqual({}, builder._nodes_by_key)
549
536
        # We should have a new entry
551
538
        # And spills to a second backing index combing all
552
539
        builder.add_node(*nodes[3])
553
540
        self.assertEqual(0, len(builder._nodes))
554
 
        self.assertEqual(0, len(builder._keys))
555
541
        self.assertIs(None, builder._nodes_by_key)
556
542
        self.assertEqual(2, len(builder._backing_indices))
557
543
        self.assertEqual(None, builder._backing_indices[0])
560
546
        builder.add_node(*nodes[4])
561
547
        builder.add_node(*nodes[5])
562
548
        self.assertEqual(0, len(builder._nodes))
563
 
        self.assertEqual(0, len(builder._keys))
564
549
        self.assertIs(None, builder._nodes_by_key)
565
550
        self.assertEqual(2, len(builder._backing_indices))
566
551
        self.assertEqual(2, builder._backing_indices[0].key_count())
633
618
        for key, value, references in nodes:
634
619
            builder.add_node(key, value, references)
635
620
        stream = builder.finish()
636
 
        trans = get_transport('trace+' + self.get_url())
 
621
        trans = transport.get_transport_from_url('trace+' + self.get_url())
637
622
        size = trans.put_file('index', stream)
638
623
        return btree_index.BTreeGraphIndex(trans, 'index', size)
639
624
 
 
625
    def make_index_with_offset(self, ref_lists=1, key_elements=1, nodes=[],
 
626
                               offset=0):
 
627
        builder = btree_index.BTreeBuilder(key_elements=key_elements,
 
628
                                           reference_lists=ref_lists)
 
629
        builder.add_nodes(nodes)
 
630
        transport = self.get_transport('')
 
631
        # NamedTemporaryFile dies on builder.finish().read(). weird.
 
632
        temp_file = builder.finish()
 
633
        content = temp_file.read()
 
634
        del temp_file
 
635
        size = len(content)
 
636
        transport.put_bytes('index', (' '*offset)+content)
 
637
        return btree_index.BTreeGraphIndex(transport, 'index', size=size,
 
638
                                           offset=offset)
 
639
 
 
640
    def test_clear_cache(self):
 
641
        nodes = self.make_nodes(160, 2, 2)
 
642
        index = self.make_index(ref_lists=2, key_elements=2, nodes=nodes)
 
643
        self.assertEqual(1, len(list(index.iter_entries([nodes[30][0]]))))
 
644
        self.assertEqual([1, 4], index._row_lengths)
 
645
        self.assertIsNot(None, index._root_node)
 
646
        internal_node_pre_clear = index._internal_node_cache.keys()
 
647
        self.assertTrue(len(index._leaf_node_cache) > 0)
 
648
        index.clear_cache()
 
649
        # We don't touch _root_node or _internal_node_cache, both should be
 
650
        # small, and can save a round trip or two
 
651
        self.assertIsNot(None, index._root_node)
 
652
        # NOTE: We don't want to affect the _internal_node_cache, as we expect
 
653
        #       it will be small, and if we ever do touch this index again, it
 
654
        #       will save round-trips.  This assertion isn't very strong,
 
655
        #       becuase without a 3-level index, we don't have any internal
 
656
        #       nodes cached.
 
657
        self.assertEqual(internal_node_pre_clear,
 
658
                         index._internal_node_cache.keys())
 
659
        self.assertEqual(0, len(index._leaf_node_cache))
 
660
 
640
661
    def test_trivial_constructor(self):
641
 
        transport = get_transport('trace+' + self.get_url(''))
642
 
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
 
662
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
663
        index = btree_index.BTreeGraphIndex(t, 'index', None)
643
664
        # Checks the page size at load, but that isn't logged yet.
644
 
        self.assertEqual([], transport._activity)
 
665
        self.assertEqual([], t._activity)
645
666
 
646
667
    def test_with_size_constructor(self):
647
 
        transport = get_transport('trace+' + self.get_url(''))
648
 
        index = btree_index.BTreeGraphIndex(transport, 'index', 1)
 
668
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
669
        index = btree_index.BTreeGraphIndex(t, 'index', 1)
649
670
        # Checks the page size at load, but that isn't logged yet.
650
 
        self.assertEqual([], transport._activity)
 
671
        self.assertEqual([], t._activity)
651
672
 
652
673
    def test_empty_key_count_no_size(self):
653
674
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
654
 
        transport = get_transport('trace+' + self.get_url(''))
655
 
        transport.put_file('index', builder.finish())
656
 
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
657
 
        del transport._activity[:]
658
 
        self.assertEqual([], transport._activity)
 
675
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
676
        t.put_file('index', builder.finish())
 
677
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
678
        del t._activity[:]
 
679
        self.assertEqual([], t._activity)
659
680
        self.assertEqual(0, index.key_count())
660
681
        # The entire index should have been requested (as we generally have the
661
682
        # size available, and doing many small readvs is inappropriate).
662
683
        # We can't tell how much was actually read here, but - check the code.
663
 
        self.assertEqual([('get', 'index')], transport._activity)
 
684
        self.assertEqual([('get', 'index')], t._activity)
664
685
 
665
686
    def test_empty_key_count(self):
666
687
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
667
 
        transport = get_transport('trace+' + self.get_url(''))
668
 
        size = transport.put_file('index', builder.finish())
 
688
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
689
        size = t.put_file('index', builder.finish())
669
690
        self.assertEqual(72, size)
670
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
671
 
        del transport._activity[:]
672
 
        self.assertEqual([], transport._activity)
 
691
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
692
        del t._activity[:]
 
693
        self.assertEqual([], t._activity)
673
694
        self.assertEqual(0, index.key_count())
674
695
        # The entire index should have been read, as 4K > size
675
696
        self.assertEqual([('readv', 'index', [(0, 72)], False, None)],
676
 
            transport._activity)
 
697
                         t._activity)
677
698
 
678
699
    def test_non_empty_key_count_2_2(self):
679
700
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
680
701
        nodes = self.make_nodes(35, 2, 2)
681
702
        for node in nodes:
682
703
            builder.add_node(*node)
683
 
        transport = get_transport('trace+' + self.get_url(''))
684
 
        size = transport.put_file('index', builder.finish())
685
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
686
 
        del transport._activity[:]
687
 
        self.assertEqual([], transport._activity)
 
704
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
705
        size = t.put_file('index', builder.finish())
 
706
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
707
        del t._activity[:]
 
708
        self.assertEqual([], t._activity)
688
709
        self.assertEqual(70, index.key_count())
689
710
        # The entire index should have been read, as it is one page long.
690
711
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
691
 
            transport._activity)
692
 
        self.assertEqual(1199, size)
 
712
            t._activity)
 
713
        self.assertEqualsApproxCompressed(1173, size)
 
714
 
 
715
    def test_with_offset_no_size(self):
 
716
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
 
717
                                            offset=1234,
 
718
                                            nodes=self.make_nodes(200, 1, 1))
 
719
        index._size = None # throw away the size info
 
720
        self.assertEqual(200, index.key_count())
 
721
 
 
722
    def test_with_small_offset(self):
 
723
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
 
724
                                            offset=1234,
 
725
                                            nodes=self.make_nodes(200, 1, 1))
 
726
        self.assertEqual(200, index.key_count())
 
727
 
 
728
    def test_with_large_offset(self):
 
729
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
 
730
                                            offset=123456,
 
731
                                            nodes=self.make_nodes(200, 1, 1))
 
732
        self.assertEqual(200, index.key_count())
693
733
 
694
734
    def test__read_nodes_no_size_one_page_reads_once(self):
695
735
        self.make_index(nodes=[(('key',), 'value', ())])
696
 
        trans = get_transport('trace+' + self.get_url())
 
736
        trans = transport.get_transport_from_url('trace+' + self.get_url())
697
737
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
698
738
        del trans._activity[:]
699
739
        nodes = dict(index._read_nodes([0]))
700
740
        self.assertEqual([0], nodes.keys())
701
741
        node = nodes[0]
702
 
        self.assertEqual([('key',)], node.keys.keys())
 
742
        self.assertEqual([('key',)], node.all_keys())
703
743
        self.assertEqual([('get', 'index')], trans._activity)
704
744
 
705
745
    def test__read_nodes_no_size_multiple_pages(self):
707
747
        index.key_count()
708
748
        num_pages = index._row_offsets[-1]
709
749
        # Reopen with a traced transport and no size
710
 
        trans = get_transport('trace+' + self.get_url())
 
750
        trans = transport.get_transport_from_url('trace+' + self.get_url())
711
751
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
712
752
        del trans._activity[:]
713
753
        nodes = dict(index._read_nodes([0]))
718
758
        nodes = self.make_nodes(160, 2, 2)
719
759
        for node in nodes:
720
760
            builder.add_node(*node)
721
 
        transport = get_transport('trace+' + self.get_url(''))
722
 
        size = transport.put_file('index', builder.finish())
723
 
        self.assertEqual(17692, size)
724
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
725
 
        del transport._activity[:]
726
 
        self.assertEqual([], transport._activity)
 
761
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
762
        size = t.put_file('index', builder.finish())
 
763
        self.assertEqualsApproxCompressed(17692, size)
 
764
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
765
        del t._activity[:]
 
766
        self.assertEqual([], t._activity)
727
767
        self.assertEqual(320, index.key_count())
728
768
        # The entire index should not have been read.
729
769
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None)],
730
 
            transport._activity)
 
770
                         t._activity)
731
771
 
732
772
    def test_validate_one_page(self):
733
773
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
734
774
        nodes = self.make_nodes(45, 2, 2)
735
775
        for node in nodes:
736
776
            builder.add_node(*node)
737
 
        transport = get_transport('trace+' + self.get_url(''))
738
 
        size = transport.put_file('index', builder.finish())
739
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
740
 
        del transport._activity[:]
741
 
        self.assertEqual([], transport._activity)
 
777
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
778
        size = t.put_file('index', builder.finish())
 
779
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
780
        del t._activity[:]
 
781
        self.assertEqual([], t._activity)
742
782
        index.validate()
743
783
        # The entire index should have been read linearly.
744
784
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
745
 
            transport._activity)
746
 
        self.assertEqual(1514, size)
 
785
                         t._activity)
 
786
        self.assertEqualsApproxCompressed(1488, size)
747
787
 
748
788
    def test_validate_two_pages(self):
749
789
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
750
790
        nodes = self.make_nodes(80, 2, 2)
751
791
        for node in nodes:
752
792
            builder.add_node(*node)
753
 
        transport = get_transport('trace+' + self.get_url(''))
754
 
        size = transport.put_file('index', builder.finish())
 
793
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
794
        size = t.put_file('index', builder.finish())
755
795
        # Root page, 2 leaf pages
756
 
        self.assertEqual(9339, size)
757
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
758
 
        del transport._activity[:]
759
 
        self.assertEqual([], transport._activity)
 
796
        self.assertEqualsApproxCompressed(9339, size)
 
797
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
798
        del t._activity[:]
 
799
        self.assertEqual([], t._activity)
760
800
        index.validate()
 
801
        rem = size - 8192 # Number of remaining bytes after second block
761
802
        # The entire index should have been read linearly.
762
 
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
763
 
            ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
764
 
            transport._activity)
 
803
        self.assertEqual(
 
804
            [('readv', 'index', [(0, 4096)], False, None),
 
805
             ('readv', 'index', [(4096, 4096), (8192, rem)], False, None)],
 
806
            t._activity)
765
807
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
766
808
        # node and make validate find them.
767
809
 
768
810
    def test_eq_ne(self):
769
811
        # two indices are equal when constructed with the same parameters:
770
 
        transport1 = get_transport('trace+' + self.get_url(''))
771
 
        transport2 = get_transport(self.get_url(''))
772
 
        self.assertTrue(
773
 
            btree_index.BTreeGraphIndex(transport1, 'index', None) ==
774
 
            btree_index.BTreeGraphIndex(transport1, 'index', None))
775
 
        self.assertTrue(
776
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
777
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
778
 
        self.assertFalse(
779
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
780
 
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
781
 
        self.assertFalse(
782
 
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) ==
783
 
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
784
 
        self.assertFalse(
785
 
            btree_index.BTreeGraphIndex(transport1, 'index', 10) ==
786
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
787
 
        self.assertFalse(
788
 
            btree_index.BTreeGraphIndex(transport1, 'index', None) !=
789
 
            btree_index.BTreeGraphIndex(transport1, 'index', None))
790
 
        self.assertFalse(
791
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
792
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
793
 
        self.assertTrue(
794
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
795
 
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
796
 
        self.assertTrue(
797
 
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) !=
798
 
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
799
 
        self.assertTrue(
800
 
            btree_index.BTreeGraphIndex(transport1, 'index', 10) !=
801
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
 
812
        t1 = transport.get_transport_from_url('trace+' + self.get_url(''))
 
813
        t2 = self.get_transport()
 
814
        self.assertTrue(
 
815
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
 
816
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
817
        self.assertTrue(
 
818
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
819
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
820
        self.assertFalse(
 
821
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
822
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
823
        self.assertFalse(
 
824
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) ==
 
825
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
826
        self.assertFalse(
 
827
            btree_index.BTreeGraphIndex(t1, 'index', 10) ==
 
828
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
829
        self.assertFalse(
 
830
            btree_index.BTreeGraphIndex(t1, 'index', None) !=
 
831
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
832
        self.assertFalse(
 
833
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
834
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
835
        self.assertTrue(
 
836
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
837
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
838
        self.assertTrue(
 
839
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) !=
 
840
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
841
        self.assertTrue(
 
842
            btree_index.BTreeGraphIndex(t1, 'index', 10) !=
 
843
            btree_index.BTreeGraphIndex(t1, 'index', 20))
802
844
 
 
845
    def test_key_too_big(self):
 
846
        # the size that matters here is the _compressed_ size of the key, so we can't
 
847
        # do a simple character repeat.
 
848
        bigKey = ''.join(map(repr, xrange(btree_index._PAGE_SIZE)))
 
849
        self.assertRaises(errors.BadIndexKey,
 
850
                          self.make_index,
 
851
                          nodes=[((bigKey,), 'value', ())])
 
852
        
803
853
    def test_iter_all_only_root_no_size(self):
804
854
        self.make_index(nodes=[(('key',), 'value', ())])
805
 
        trans = get_transport('trace+' + self.get_url(''))
806
 
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
807
 
        del trans._activity[:]
 
855
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
856
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
857
        del t._activity[:]
808
858
        self.assertEqual([(('key',), 'value')],
809
859
                         [x[1:] for x in index.iter_all_entries()])
810
 
        self.assertEqual([('get', 'index')], trans._activity)
 
860
        self.assertEqual([('get', 'index')], t._activity)
811
861
 
812
862
    def test_iter_all_entries_reads(self):
813
863
        # iterating all entries reads the header, then does a linear
819
869
        nodes = self.make_nodes(10000, 2, 2)
820
870
        for node in nodes:
821
871
            builder.add_node(*node)
822
 
        transport = get_transport('trace+' + self.get_url(''))
823
 
        size = transport.put_file('index', builder.finish())
824
 
        self.assertEqual(1303220, size, 'number of expected bytes in the'
825
 
                                        ' output changed')
 
872
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
873
        size = t.put_file('index', builder.finish())
826
874
        page_size = btree_index._PAGE_SIZE
827
875
        del builder
828
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
829
 
        del transport._activity[:]
830
 
        self.assertEqual([], transport._activity)
 
876
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
877
        del t._activity[:]
 
878
        self.assertEqual([], t._activity)
831
879
        found_nodes = self.time(list, index.iter_all_entries())
832
880
        bare_nodes = []
833
881
        for node in found_nodes:
844
892
        # The entire index should have been read
845
893
        total_pages = sum(index._row_lengths)
846
894
        self.assertEqual(total_pages, index._row_offsets[-1])
847
 
        self.assertEqual(1303220, size)
 
895
        self.assertEqualsApproxCompressed(1303220, size)
848
896
        # The start of the leaves
849
897
        first_byte = index._row_offsets[-2] * page_size
850
898
        readv_request = []
851
899
        for offset in range(first_byte, size, page_size):
852
900
            readv_request.append((offset, page_size))
853
901
        # The last page is truncated
854
 
        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
 
902
        readv_request[-1] = (readv_request[-1][0], size % page_size)
855
903
        expected = [('readv', 'index', [(0, page_size)], False, None),
856
904
             ('readv',  'index', readv_request, False, None)]
857
 
        if expected != transport._activity:
 
905
        if expected != t._activity:
858
906
            self.assertEqualDiff(pprint.pformat(expected),
859
 
                                 pprint.pformat(transport._activity))
 
907
                                 pprint.pformat(t._activity))
860
908
 
861
909
    def _test_iter_entries_references_resolved(self):
862
910
        index = self.make_index(1, nodes=[
874
922
        nodes = self.make_nodes(160, 2, 2)
875
923
        for node in nodes:
876
924
            builder.add_node(*node)
877
 
        transport = get_transport('trace+' + self.get_url(''))
878
 
        size = transport.put_file('index', builder.finish())
 
925
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
926
        size = t.put_file('index', builder.finish())
879
927
        del builder
880
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
881
 
        del transport._activity[:]
882
 
        self.assertEqual([], transport._activity)
 
928
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
929
        del t._activity[:]
 
930
        self.assertEqual([], t._activity)
883
931
        # search for one key
884
932
        found_nodes = list(index.iter_entries([nodes[30][0]]))
885
933
        bare_nodes = []
893
941
        # Should have read the root node, then one leaf page:
894
942
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
895
943
             ('readv',  'index', [(8192, 4096), ], False, None)],
896
 
            transport._activity)
 
944
            t._activity)
897
945
 
898
946
    def test_iter_key_prefix_1_element_key_None(self):
899
947
        index = self.make_index()
1082
1130
        min_l2_key = l2.min_key
1083
1131
        max_l1_key = l1.max_key
1084
1132
        self.assertTrue(max_l1_key < min_l2_key)
1085
 
        parents_min_l2_key = l2.keys[min_l2_key][1][0]
 
1133
        parents_min_l2_key = l2[min_l2_key][1][0]
1086
1134
        self.assertEqual((l1.max_key,), parents_min_l2_key)
1087
1135
        # Now, whatever key we select that would fall on the second page,
1088
1136
        # should give us all the parents until the page break
1101
1149
        parent_map = {}
1102
1150
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
1103
1151
                                            missing_keys)
1104
 
        self.assertEqual(sorted(l1.keys), sorted(parent_map))
 
1152
        self.assertEqual(l1.all_keys(), sorted(parent_map))
1105
1153
        self.assertEqual(set(), missing_keys)
1106
1154
        self.assertEqual(set(), search_keys)
1107
1155
 
1115
1163
        self.assertEqual({}, parent_map)
1116
1164
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
1117
1165
 
 
1166
    def test_supports_unlimited_cache(self):
 
1167
        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)
 
1168
        # We need enough nodes to cause a page split (so we have both an
 
1169
        # internal node and a couple leaf nodes. 500 seems to be enough.)
 
1170
        nodes = self.make_nodes(500, 1, 0)
 
1171
        for node in nodes:
 
1172
            builder.add_node(*node)
 
1173
        stream = builder.finish()
 
1174
        trans = self.get_transport()
 
1175
        size = trans.put_file('index', stream)
 
1176
        index = btree_index.BTreeGraphIndex(trans, 'index', size)
 
1177
        self.assertEqual(500, index.key_count())
 
1178
        # We have an internal node
 
1179
        self.assertEqual(2, len(index._row_lengths))
 
1180
        # We have at least 2 leaf nodes
 
1181
        self.assertTrue(index._row_lengths[-1] >= 2)
 
1182
        self.assertIsInstance(index._leaf_node_cache, lru_cache.LRUCache)
 
1183
        self.assertEqual(btree_index._NODE_CACHE_SIZE,
 
1184
                         index._leaf_node_cache._max_cache)
 
1185
        self.assertIsInstance(index._internal_node_cache, fifo_cache.FIFOCache)
 
1186
        self.assertEqual(100, index._internal_node_cache._max_cache)
 
1187
        # No change if unlimited_cache=False is passed
 
1188
        index = btree_index.BTreeGraphIndex(trans, 'index', size,
 
1189
                                            unlimited_cache=False)
 
1190
        self.assertIsInstance(index._leaf_node_cache, lru_cache.LRUCache)
 
1191
        self.assertEqual(btree_index._NODE_CACHE_SIZE,
 
1192
                         index._leaf_node_cache._max_cache)
 
1193
        self.assertIsInstance(index._internal_node_cache, fifo_cache.FIFOCache)
 
1194
        self.assertEqual(100, index._internal_node_cache._max_cache)
 
1195
        index = btree_index.BTreeGraphIndex(trans, 'index', size,
 
1196
                                            unlimited_cache=True)
 
1197
        self.assertIsInstance(index._leaf_node_cache, dict)
 
1198
        self.assertIs(type(index._internal_node_cache), dict)
 
1199
        # Exercise the lookup code
 
1200
        entries = set(index.iter_entries([n[0] for n in nodes]))
 
1201
        self.assertEqual(500, len(entries))
 
1202
 
1118
1203
 
1119
1204
class TestBTreeNodes(BTreeTestCase):
1120
1205
 
1121
 
    def restore_parser(self):
1122
 
        btree_index._btree_serializer = self.saved_parser
 
1206
    scenarios = btreeparser_scenarios()
1123
1207
 
1124
1208
    def setUp(self):
1125
 
        BTreeTestCase.setUp(self)
1126
 
        self.saved_parser = btree_index._btree_serializer
1127
 
        self.addCleanup(self.restore_parser)
1128
 
        btree_index._btree_serializer = self.parse_btree
 
1209
        super(TestBTreeNodes, self).setUp()
 
1210
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
1129
1211
 
1130
1212
    def test_LeafNode_1_0(self):
1131
1213
        node_bytes = ("type=leaf\n"
1143
1225
            ("2222222222222222222222222222222222222222",): ("value:2", ()),
1144
1226
            ("3333333333333333333333333333333333333333",): ("value:3", ()),
1145
1227
            ("4444444444444444444444444444444444444444",): ("value:4", ()),
1146
 
            }, node.keys)
 
1228
            }, dict(node.all_items()))
1147
1229
 
1148
1230
    def test_LeafNode_2_2(self):
1149
1231
        node_bytes = ("type=leaf\n"
1163
1245
            ('11', '33'): ('value:3',
1164
1246
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1165
1247
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1166
 
            }, node.keys)
 
1248
            }, dict(node.all_items()))
1167
1249
 
1168
1250
    def test_InternalNode_1(self):
1169
1251
        node_bytes = ("type=internal\n"
1204
1286
            ('11', '33'): ('value:3',
1205
1287
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1206
1288
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1207
 
            }, node.keys)
 
1289
            }, dict(node.all_items()))
1208
1290
 
1209
1291
    def assertFlattened(self, expected, key, value, refs):
1210
1292
        flat_key, flat_line = self.parse_btree._flatten_node(
1242
1324
    def test_exists(self):
1243
1325
        # This is just to let the user know if they don't have the feature
1244
1326
        # available
1245
 
        self.requireFeature(CompiledBtreeParserFeature)
 
1327
        self.requireFeature(compiled_btreeparser_feature)
1246
1328
 
1247
1329
 
1248
1330
class TestMultiBisectRight(tests.TestCase):
1288
1370
        This doesn't actually create anything on disk, it just primes a
1289
1371
        BTreeGraphIndex with the recommended information.
1290
1372
        """
1291
 
        index = btree_index.BTreeGraphIndex(get_transport('memory:///'),
1292
 
                                            'test-index', size=size)
 
1373
        index = btree_index.BTreeGraphIndex(
 
1374
            transport.get_transport_from_url('memory:///'),
 
1375
            'test-index', size=size)
1293
1376
        if recommended_pages is not None:
1294
1377
            index._recommended_pages = recommended_pages
1295
1378
        return index