← 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

  • Committer: John Arbash Meinel
  • Date: 2009-06-12 18:05:15 UTC
  • mto: (4371.4.5 vila-better-heads)
  • mto: This revision was merged to the branch mainline in revision 4449.
  • Revision ID: john@arbash-meinel.com-20090612180515-t0cwbjsnve094oik
Add a failing test for handling nodes that are in the same linear chain.

It fails because the ancestry skipping causes us to miss the fact that the two nodes
are actually directly related. We could check at the beginning, as the 
code used to do, but I think that will be incomplete for the more-than-two
heads cases.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
1
 
# Copyright (C) 2008-2011 Canonical Ltd
 
1
# Copyright (C) 2008 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,
28
 
    osutils,
29
26
    tests,
30
 
    transport,
31
27
    )
32
28
from bzrlib.tests import (
33
29
    TestCaseWithTransport,
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():
 
30
    condition_isinstance,
 
31
    multiply_tests,
 
32
    split_suite_by_condition,
 
33
    )
 
34
from bzrlib.transport import get_transport
 
35
 
 
36
 
 
37
def load_tests(standard_tests, module, loader):
 
38
    # parameterise the TestBTreeNodes tests
 
39
    node_tests, others = split_suite_by_condition(standard_tests,
 
40
        condition_isinstance(TestBTreeNodes))
45
41
    import bzrlib._btree_serializer_py as py_module
46
42
    scenarios = [('python', {'parse_btree': py_module})]
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')
 
43
    if CompiledBtreeParserFeature.available():
 
44
        # Is there a way to do this that gets missing feature failures rather
 
45
        # than no indication to the user?
 
46
        import bzrlib._btree_serializer_c as c_module
 
47
        scenarios.append(('C', {'parse_btree': c_module}))
 
48
    return multiply_tests(node_tests, scenarios, others)
 
49
 
 
50
 
 
51
class _CompiledBtreeParserFeature(tests.Feature):
 
52
    def _probe(self):
 
53
        try:
 
54
            import bzrlib._btree_serializer_c
 
55
        except ImportError:
 
56
            return False
 
57
        return True
 
58
 
 
59
    def feature_name(self):
 
60
        return 'bzrlib._btree_serializer_c'
 
61
 
 
62
CompiledBtreeParserFeature = _CompiledBtreeParserFeature()
55
63
 
56
64
 
57
65
class BTreeTestCase(TestCaseWithTransport):
60
68
 
61
69
    def setUp(self):
62
70
        TestCaseWithTransport.setUp(self)
63
 
        self.overrideAttr(btree_index, '_RESERVED_HEADER_BYTES', 100)
 
71
        self._original_header = btree_index._RESERVED_HEADER_BYTES
 
72
        def restore():
 
73
            btree_index._RESERVED_HEADER_BYTES = self._original_header
 
74
        self.addCleanup(restore)
 
75
        btree_index._RESERVED_HEADER_BYTES = 100
64
76
 
65
77
    def make_nodes(self, count, key_elements, reference_lists):
66
78
        """Generate count*key_elements sample nodes."""
100
112
 
101
113
    def shrink_page_size(self):
102
114
        """Shrink the default page size so that less fits in a page."""
103
 
        self.overrideAttr(btree_index, '_PAGE_SIZE')
 
115
        old_page_size = btree_index._PAGE_SIZE
 
116
        def cleanup():
 
117
            btree_index._PAGE_SIZE = old_page_size
 
118
        self.addCleanup(cleanup)
104
119
        btree_index._PAGE_SIZE = 2048
105
120
 
106
121
 
107
122
class TestBTreeBuilder(BTreeTestCase):
108
123
 
109
 
    def test_clear_cache(self):
110
 
        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)
111
 
        # This is a no-op, but we need the api to be consistent with other
112
 
        # BTreeGraphIndex apis.
113
 
        builder.clear_cache()
114
 
 
115
124
    def test_empty_1_0(self):
116
125
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
117
126
        # NamedTemporaryFile dies on builder.finish().read(). weird.
143
152
        temp_file = builder.finish()
144
153
        content = temp_file.read()
145
154
        del temp_file
146
 
        self.assertEqual(131, len(content))
 
155
        self.assertEqual(158, len(content))
147
156
        self.assertEqual(
148
157
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"
149
158
            "row_lengths=1\n",
167
176
        temp_file = builder.finish()
168
177
        content = temp_file.read()
169
178
        del temp_file
170
 
        self.assertEqual(238, len(content))
 
179
        self.assertEqual(264, len(content))
171
180
        self.assertEqual(
172
181
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"
173
182
            "row_lengths=1\n",
217
226
        leaf1_bytes = zlib.decompress(leaf1)
218
227
        sorted_node_keys = sorted(node[0] for node in nodes)
219
228
        node = btree_index._LeafNode(leaf1_bytes, 1, 0)
220
 
        self.assertEqual(231, len(node))
221
 
        self.assertEqual(sorted_node_keys[:231], node.all_keys())
 
229
        self.assertEqual(231, len(node.keys))
 
230
        self.assertEqual(sorted_node_keys[:231], sorted(node.keys))
222
231
        leaf2_bytes = zlib.decompress(leaf2)
223
232
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
224
 
        self.assertEqual(400 - 231, len(node))
225
 
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
 
233
        self.assertEqual(400 - 231, len(node.keys))
 
234
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
226
235
 
227
236
    def test_last_page_rounded_1_layer(self):
228
237
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
233
242
        temp_file = builder.finish()
234
243
        content = temp_file.read()
235
244
        del temp_file
236
 
        self.assertEqual(155, len(content))
 
245
        self.assertEqual(181, len(content))
237
246
        self.assertEqual(
238
247
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
239
248
            "row_lengths=1\n",
242
251
        leaf2 = content[74:]
243
252
        leaf2_bytes = zlib.decompress(leaf2)
244
253
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
245
 
        self.assertEqual(10, len(node))
 
254
        self.assertEqual(10, len(node.keys))
246
255
        sorted_node_keys = sorted(node[0] for node in nodes)
247
 
        self.assertEqual(sorted_node_keys, node.all_keys())
 
256
        self.assertEqual(sorted_node_keys, sorted(node.keys))
248
257
 
249
258
    def test_last_page_not_rounded_2_layer(self):
250
259
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
264
273
        leaf2 = content[8192:]
265
274
        leaf2_bytes = zlib.decompress(leaf2)
266
275
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
267
 
        self.assertEqual(400 - 231, len(node))
 
276
        self.assertEqual(400 - 231, len(node.keys))
268
277
        sorted_node_keys = sorted(node[0] for node in nodes)
269
 
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
 
278
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
270
279
 
271
280
    def test_three_level_tree_details(self):
272
281
        # The left most pointer in the second internal node in a row should
281
290
 
282
291
        for node in nodes:
283
292
            builder.add_node(*node)
284
 
        t = transport.get_transport('trace+' + self.get_url(''))
285
 
        size = t.put_file('index', self.time(builder.finish))
 
293
        transport = get_transport('trace+' + self.get_url(''))
 
294
        size = transport.put_file('index', self.time(builder.finish))
286
295
        del builder
287
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
296
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
288
297
        # Seed the metadata, we're using internal calls now.
289
298
        index.key_count()
290
299
        self.assertEqual(3, len(index._row_lengths),
303
312
        # in the second node it points at
304
313
        pos = index._row_offsets[2] + internal_node2.offset + 1
305
314
        leaf = index._get_leaf_nodes([pos])[pos]
306
 
        self.assertTrue(internal_node2.keys[0] in leaf)
 
315
        self.assertTrue(internal_node2.keys[0] in leaf.keys)
307
316
 
308
317
    def test_2_leaves_2_2(self):
309
318
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
341
350
        # Test the parts of the index that take up memory are doing so
342
351
        # predictably.
343
352
        self.assertEqual(1, len(builder._nodes))
 
353
        self.assertEqual(1, len(builder._keys))
344
354
        self.assertIs(None, builder._nodes_by_key)
345
355
        builder.add_node(*nodes[1])
346
356
        self.assertEqual(0, len(builder._nodes))
 
357
        self.assertEqual(0, len(builder._keys))
347
358
        self.assertIs(None, builder._nodes_by_key)
348
359
        self.assertEqual(1, len(builder._backing_indices))
349
360
        self.assertEqual(2, builder._backing_indices[0].key_count())
350
361
        # now back to memory
351
362
        builder.add_node(*nodes[2])
352
363
        self.assertEqual(1, len(builder._nodes))
 
364
        self.assertEqual(1, len(builder._keys))
353
365
        self.assertIs(None, builder._nodes_by_key)
354
366
        # And spills to a second backing index combing all
355
367
        builder.add_node(*nodes[3])
356
368
        self.assertEqual(0, len(builder._nodes))
 
369
        self.assertEqual(0, len(builder._keys))
357
370
        self.assertIs(None, builder._nodes_by_key)
358
371
        self.assertEqual(2, len(builder._backing_indices))
359
372
        self.assertEqual(None, builder._backing_indices[0])
362
375
        builder.add_node(*nodes[4])
363
376
        builder.add_node(*nodes[5])
364
377
        self.assertEqual(0, len(builder._nodes))
 
378
        self.assertEqual(0, len(builder._keys))
365
379
        self.assertIs(None, builder._nodes_by_key)
366
380
        self.assertEqual(2, len(builder._backing_indices))
367
381
        self.assertEqual(2, builder._backing_indices[0].key_count())
410
424
        self.assertEqual(None, builder._backing_indices[2])
411
425
        self.assertEqual(16, builder._backing_indices[3].key_count())
412
426
        # Now finish, and check we got a correctly ordered tree
413
 
        t = self.get_transport('')
414
 
        size = t.put_file('index', builder.finish())
415
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
427
        transport = self.get_transport('')
 
428
        size = transport.put_file('index', builder.finish())
 
429
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
416
430
        nodes = list(index.iter_all_entries())
417
431
        self.assertEqual(sorted(nodes), nodes)
418
432
        self.assertEqual(16, len(nodes))
425
439
        # Test the parts of the index that take up memory are doing so
426
440
        # predictably.
427
441
        self.assertEqual(1, len(builder._nodes))
 
442
        self.assertEqual(1, len(builder._keys))
428
443
        self.assertIs(None, builder._nodes_by_key)
429
444
        builder.add_node(*nodes[1])
430
445
        self.assertEqual(0, len(builder._nodes))
 
446
        self.assertEqual(0, len(builder._keys))
431
447
        self.assertIs(None, builder._nodes_by_key)
432
448
        self.assertEqual(1, len(builder._backing_indices))
433
449
        self.assertEqual(2, builder._backing_indices[0].key_count())
434
450
        # now back to memory
435
451
        builder.add_node(*nodes[2])
436
452
        self.assertEqual(1, len(builder._nodes))
 
453
        self.assertEqual(1, len(builder._keys))
437
454
        self.assertIs(None, builder._nodes_by_key)
438
455
        # And spills to a second backing index but doesn't combine
439
456
        builder.add_node(*nodes[3])
440
457
        self.assertEqual(0, len(builder._nodes))
 
458
        self.assertEqual(0, len(builder._keys))
441
459
        self.assertIs(None, builder._nodes_by_key)
442
460
        self.assertEqual(2, len(builder._backing_indices))
443
461
        for backing_index in builder._backing_indices:
446
464
        builder.add_node(*nodes[4])
447
465
        builder.add_node(*nodes[5])
448
466
        self.assertEqual(0, len(builder._nodes))
 
467
        self.assertEqual(0, len(builder._keys))
449
468
        self.assertIs(None, builder._nodes_by_key)
450
469
        self.assertEqual(3, len(builder._backing_indices))
451
470
        for backing_index in builder._backing_indices:
510
529
        builder.add_node(*nodes[0])
511
530
        # Test the parts of the index that take up memory are doing so
512
531
        # predictably.
 
532
        self.assertEqual(1, len(builder._keys))
513
533
        self.assertEqual(1, len(builder._nodes))
514
534
        self.assertIs(None, builder._nodes_by_key)
515
535
        builder.add_node(*nodes[1])
 
536
        self.assertEqual(0, len(builder._keys))
516
537
        self.assertEqual(0, len(builder._nodes))
517
538
        self.assertIs(None, builder._nodes_by_key)
518
539
        self.assertEqual(1, len(builder._backing_indices))
521
542
        old = dict(builder._get_nodes_by_key()) #Build up the nodes by key dict
522
543
        builder.add_node(*nodes[2])
523
544
        self.assertEqual(1, len(builder._nodes))
 
545
        self.assertEqual(1, len(builder._keys))
524
546
        self.assertIsNot(None, builder._nodes_by_key)
525
547
        self.assertNotEqual({}, builder._nodes_by_key)
526
548
        # We should have a new entry
528
550
        # And spills to a second backing index combing all
529
551
        builder.add_node(*nodes[3])
530
552
        self.assertEqual(0, len(builder._nodes))
 
553
        self.assertEqual(0, len(builder._keys))
531
554
        self.assertIs(None, builder._nodes_by_key)
532
555
        self.assertEqual(2, len(builder._backing_indices))
533
556
        self.assertEqual(None, builder._backing_indices[0])
536
559
        builder.add_node(*nodes[4])
537
560
        builder.add_node(*nodes[5])
538
561
        self.assertEqual(0, len(builder._nodes))
 
562
        self.assertEqual(0, len(builder._keys))
539
563
        self.assertIs(None, builder._nodes_by_key)
540
564
        self.assertEqual(2, len(builder._backing_indices))
541
565
        self.assertEqual(2, builder._backing_indices[0].key_count())
608
632
        for key, value, references in nodes:
609
633
            builder.add_node(key, value, references)
610
634
        stream = builder.finish()
611
 
        trans = transport.get_transport('trace+' + self.get_url())
 
635
        trans = get_transport('trace+' + self.get_url())
612
636
        size = trans.put_file('index', stream)
613
637
        return btree_index.BTreeGraphIndex(trans, 'index', size)
614
638
 
615
 
    def make_index_with_offset(self, ref_lists=1, key_elements=1, nodes=[],
616
 
                               offset=0):
617
 
        builder = btree_index.BTreeBuilder(key_elements=key_elements,
618
 
                                           reference_lists=ref_lists)
619
 
        builder.add_nodes(nodes)
620
 
        transport = self.get_transport('')
621
 
        # NamedTemporaryFile dies on builder.finish().read(). weird.
622
 
        temp_file = builder.finish()
623
 
        content = temp_file.read()
624
 
        del temp_file
625
 
        size = len(content)
626
 
        transport.put_bytes('index', (' '*offset)+content)
627
 
        return btree_index.BTreeGraphIndex(transport, 'index', size=size,
628
 
                                           offset=offset)
629
 
 
630
 
    def test_clear_cache(self):
631
 
        nodes = self.make_nodes(160, 2, 2)
632
 
        index = self.make_index(ref_lists=2, key_elements=2, nodes=nodes)
633
 
        self.assertEqual(1, len(list(index.iter_entries([nodes[30][0]]))))
634
 
        self.assertEqual([1, 4], index._row_lengths)
635
 
        self.assertIsNot(None, index._root_node)
636
 
        internal_node_pre_clear = index._internal_node_cache.keys()
637
 
        self.assertTrue(len(index._leaf_node_cache) > 0)
638
 
        index.clear_cache()
639
 
        # We don't touch _root_node or _internal_node_cache, both should be
640
 
        # small, and can save a round trip or two
641
 
        self.assertIsNot(None, index._root_node)
642
 
        # NOTE: We don't want to affect the _internal_node_cache, as we expect
643
 
        #       it will be small, and if we ever do touch this index again, it
644
 
        #       will save round-trips.  This assertion isn't very strong,
645
 
        #       becuase without a 3-level index, we don't have any internal
646
 
        #       nodes cached.
647
 
        self.assertEqual(internal_node_pre_clear,
648
 
                         index._internal_node_cache.keys())
649
 
        self.assertEqual(0, len(index._leaf_node_cache))
650
 
 
651
639
    def test_trivial_constructor(self):
652
 
        t = transport.get_transport('trace+' + self.get_url(''))
653
 
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
640
        transport = get_transport('trace+' + self.get_url(''))
 
641
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
654
642
        # Checks the page size at load, but that isn't logged yet.
655
 
        self.assertEqual([], t._activity)
 
643
        self.assertEqual([], transport._activity)
656
644
 
657
645
    def test_with_size_constructor(self):
658
 
        t = transport.get_transport('trace+' + self.get_url(''))
659
 
        index = btree_index.BTreeGraphIndex(t, 'index', 1)
 
646
        transport = get_transport('trace+' + self.get_url(''))
 
647
        index = btree_index.BTreeGraphIndex(transport, 'index', 1)
660
648
        # Checks the page size at load, but that isn't logged yet.
661
 
        self.assertEqual([], t._activity)
 
649
        self.assertEqual([], transport._activity)
662
650
 
663
651
    def test_empty_key_count_no_size(self):
664
652
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
665
 
        t = transport.get_transport('trace+' + self.get_url(''))
666
 
        t.put_file('index', builder.finish())
667
 
        index = btree_index.BTreeGraphIndex(t, 'index', None)
668
 
        del t._activity[:]
669
 
        self.assertEqual([], t._activity)
 
653
        transport = get_transport('trace+' + self.get_url(''))
 
654
        transport.put_file('index', builder.finish())
 
655
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
 
656
        del transport._activity[:]
 
657
        self.assertEqual([], transport._activity)
670
658
        self.assertEqual(0, index.key_count())
671
659
        # The entire index should have been requested (as we generally have the
672
660
        # size available, and doing many small readvs is inappropriate).
673
661
        # We can't tell how much was actually read here, but - check the code.
674
 
        self.assertEqual([('get', 'index')], t._activity)
 
662
        self.assertEqual([('get', 'index')], transport._activity)
675
663
 
676
664
    def test_empty_key_count(self):
677
665
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
678
 
        t = transport.get_transport('trace+' + self.get_url(''))
679
 
        size = t.put_file('index', builder.finish())
 
666
        transport = get_transport('trace+' + self.get_url(''))
 
667
        size = transport.put_file('index', builder.finish())
680
668
        self.assertEqual(72, size)
681
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
682
 
        del t._activity[:]
683
 
        self.assertEqual([], t._activity)
 
669
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
670
        del transport._activity[:]
 
671
        self.assertEqual([], transport._activity)
684
672
        self.assertEqual(0, index.key_count())
685
673
        # The entire index should have been read, as 4K > size
686
674
        self.assertEqual([('readv', 'index', [(0, 72)], False, None)],
687
 
                         t._activity)
 
675
            transport._activity)
688
676
 
689
677
    def test_non_empty_key_count_2_2(self):
690
678
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
691
679
        nodes = self.make_nodes(35, 2, 2)
692
680
        for node in nodes:
693
681
            builder.add_node(*node)
694
 
        t = transport.get_transport('trace+' + self.get_url(''))
695
 
        size = t.put_file('index', builder.finish())
696
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
697
 
        del t._activity[:]
698
 
        self.assertEqual([], t._activity)
 
682
        transport = get_transport('trace+' + self.get_url(''))
 
683
        size = transport.put_file('index', builder.finish())
 
684
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
685
        del transport._activity[:]
 
686
        self.assertEqual([], transport._activity)
699
687
        self.assertEqual(70, index.key_count())
700
688
        # The entire index should have been read, as it is one page long.
701
689
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
702
 
            t._activity)
703
 
        self.assertEqual(1173, size)
704
 
 
705
 
    def test_with_offset_no_size(self):
706
 
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
707
 
                                            offset=1234,
708
 
                                            nodes=self.make_nodes(200, 1, 1))
709
 
        index._size = None # throw away the size info
710
 
        self.assertEqual(200, index.key_count())
711
 
 
712
 
    def test_with_small_offset(self):
713
 
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
714
 
                                            offset=1234,
715
 
                                            nodes=self.make_nodes(200, 1, 1))
716
 
        self.assertEqual(200, index.key_count())
717
 
 
718
 
    def test_with_large_offset(self):
719
 
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
720
 
                                            offset=123456,
721
 
                                            nodes=self.make_nodes(200, 1, 1))
722
 
        self.assertEqual(200, index.key_count())
 
690
            transport._activity)
 
691
        self.assertEqual(1199, size)
723
692
 
724
693
    def test__read_nodes_no_size_one_page_reads_once(self):
725
694
        self.make_index(nodes=[(('key',), 'value', ())])
726
 
        trans = transport.get_transport('trace+' + self.get_url())
 
695
        trans = get_transport('trace+' + self.get_url())
727
696
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
728
697
        del trans._activity[:]
729
698
        nodes = dict(index._read_nodes([0]))
730
699
        self.assertEqual([0], nodes.keys())
731
700
        node = nodes[0]
732
 
        self.assertEqual([('key',)], node.all_keys())
 
701
        self.assertEqual([('key',)], node.keys.keys())
733
702
        self.assertEqual([('get', 'index')], trans._activity)
734
703
 
735
704
    def test__read_nodes_no_size_multiple_pages(self):
737
706
        index.key_count()
738
707
        num_pages = index._row_offsets[-1]
739
708
        # Reopen with a traced transport and no size
740
 
        trans = transport.get_transport('trace+' + self.get_url())
 
709
        trans = get_transport('trace+' + self.get_url())
741
710
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
742
711
        del trans._activity[:]
743
712
        nodes = dict(index._read_nodes([0]))
748
717
        nodes = self.make_nodes(160, 2, 2)
749
718
        for node in nodes:
750
719
            builder.add_node(*node)
751
 
        t = transport.get_transport('trace+' + self.get_url(''))
752
 
        size = t.put_file('index', builder.finish())
 
720
        transport = get_transport('trace+' + self.get_url(''))
 
721
        size = transport.put_file('index', builder.finish())
753
722
        self.assertEqual(17692, size)
754
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
755
 
        del t._activity[:]
756
 
        self.assertEqual([], t._activity)
 
723
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
724
        del transport._activity[:]
 
725
        self.assertEqual([], transport._activity)
757
726
        self.assertEqual(320, index.key_count())
758
727
        # The entire index should not have been read.
759
728
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None)],
760
 
                         t._activity)
 
729
            transport._activity)
761
730
 
762
731
    def test_validate_one_page(self):
763
732
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
764
733
        nodes = self.make_nodes(45, 2, 2)
765
734
        for node in nodes:
766
735
            builder.add_node(*node)
767
 
        t = transport.get_transport('trace+' + self.get_url(''))
768
 
        size = t.put_file('index', builder.finish())
769
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
770
 
        del t._activity[:]
771
 
        self.assertEqual([], t._activity)
 
736
        transport = get_transport('trace+' + self.get_url(''))
 
737
        size = transport.put_file('index', builder.finish())
 
738
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
739
        del transport._activity[:]
 
740
        self.assertEqual([], transport._activity)
772
741
        index.validate()
773
742
        # The entire index should have been read linearly.
774
743
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
775
 
                         t._activity)
776
 
        self.assertEqual(1488, size)
 
744
            transport._activity)
 
745
        self.assertEqual(1514, size)
777
746
 
778
747
    def test_validate_two_pages(self):
779
748
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
780
749
        nodes = self.make_nodes(80, 2, 2)
781
750
        for node in nodes:
782
751
            builder.add_node(*node)
783
 
        t = transport.get_transport('trace+' + self.get_url(''))
784
 
        size = t.put_file('index', builder.finish())
 
752
        transport = get_transport('trace+' + self.get_url(''))
 
753
        size = transport.put_file('index', builder.finish())
785
754
        # Root page, 2 leaf pages
786
755
        self.assertEqual(9339, size)
787
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
788
 
        del t._activity[:]
789
 
        self.assertEqual([], t._activity)
 
756
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
757
        del transport._activity[:]
 
758
        self.assertEqual([], transport._activity)
790
759
        index.validate()
791
760
        # The entire index should have been read linearly.
792
 
        self.assertEqual(
793
 
            [('readv', 'index', [(0, 4096)], False, None),
794
 
             ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
795
 
            t._activity)
 
761
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
 
762
            ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
 
763
            transport._activity)
796
764
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
797
765
        # node and make validate find them.
798
766
 
799
767
    def test_eq_ne(self):
800
768
        # two indices are equal when constructed with the same parameters:
801
 
        t1 = transport.get_transport('trace+' + self.get_url(''))
802
 
        t2 = self.get_transport()
803
 
        self.assertTrue(
804
 
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
805
 
            btree_index.BTreeGraphIndex(t1, 'index', None))
806
 
        self.assertTrue(
807
 
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
808
 
            btree_index.BTreeGraphIndex(t1, 'index', 20))
809
 
        self.assertFalse(
810
 
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
811
 
            btree_index.BTreeGraphIndex(t2, 'index', 20))
812
 
        self.assertFalse(
813
 
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) ==
814
 
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
815
 
        self.assertFalse(
816
 
            btree_index.BTreeGraphIndex(t1, 'index', 10) ==
817
 
            btree_index.BTreeGraphIndex(t1, 'index', 20))
818
 
        self.assertFalse(
819
 
            btree_index.BTreeGraphIndex(t1, 'index', None) !=
820
 
            btree_index.BTreeGraphIndex(t1, 'index', None))
821
 
        self.assertFalse(
822
 
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
823
 
            btree_index.BTreeGraphIndex(t1, 'index', 20))
824
 
        self.assertTrue(
825
 
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
826
 
            btree_index.BTreeGraphIndex(t2, 'index', 20))
827
 
        self.assertTrue(
828
 
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) !=
829
 
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
830
 
        self.assertTrue(
831
 
            btree_index.BTreeGraphIndex(t1, 'index', 10) !=
832
 
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
769
        transport1 = get_transport('trace+' + self.get_url(''))
 
770
        transport2 = get_transport(self.get_url(''))
 
771
        self.assertTrue(
 
772
            btree_index.BTreeGraphIndex(transport1, 'index', None) ==
 
773
            btree_index.BTreeGraphIndex(transport1, 'index', None))
 
774
        self.assertTrue(
 
775
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
 
776
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
 
777
        self.assertFalse(
 
778
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
 
779
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
 
780
        self.assertFalse(
 
781
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) ==
 
782
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
 
783
        self.assertFalse(
 
784
            btree_index.BTreeGraphIndex(transport1, 'index', 10) ==
 
785
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
 
786
        self.assertFalse(
 
787
            btree_index.BTreeGraphIndex(transport1, 'index', None) !=
 
788
            btree_index.BTreeGraphIndex(transport1, 'index', None))
 
789
        self.assertFalse(
 
790
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
 
791
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
 
792
        self.assertTrue(
 
793
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
 
794
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
 
795
        self.assertTrue(
 
796
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) !=
 
797
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
 
798
        self.assertTrue(
 
799
            btree_index.BTreeGraphIndex(transport1, 'index', 10) !=
 
800
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
833
801
 
834
802
    def test_iter_all_only_root_no_size(self):
835
803
        self.make_index(nodes=[(('key',), 'value', ())])
836
 
        t = transport.get_transport('trace+' + self.get_url(''))
837
 
        index = btree_index.BTreeGraphIndex(t, 'index', None)
838
 
        del t._activity[:]
 
804
        trans = get_transport('trace+' + self.get_url(''))
 
805
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
 
806
        del trans._activity[:]
839
807
        self.assertEqual([(('key',), 'value')],
840
808
                         [x[1:] for x in index.iter_all_entries()])
841
 
        self.assertEqual([('get', 'index')], t._activity)
 
809
        self.assertEqual([('get', 'index')], trans._activity)
842
810
 
843
811
    def test_iter_all_entries_reads(self):
844
812
        # iterating all entries reads the header, then does a linear
850
818
        nodes = self.make_nodes(10000, 2, 2)
851
819
        for node in nodes:
852
820
            builder.add_node(*node)
853
 
        t = transport.get_transport('trace+' + self.get_url(''))
854
 
        size = t.put_file('index', builder.finish())
 
821
        transport = get_transport('trace+' + self.get_url(''))
 
822
        size = transport.put_file('index', builder.finish())
855
823
        self.assertEqual(1303220, size, 'number of expected bytes in the'
856
824
                                        ' output changed')
857
825
        page_size = btree_index._PAGE_SIZE
858
826
        del builder
859
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
860
 
        del t._activity[:]
861
 
        self.assertEqual([], t._activity)
 
827
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
828
        del transport._activity[:]
 
829
        self.assertEqual([], transport._activity)
862
830
        found_nodes = self.time(list, index.iter_all_entries())
863
831
        bare_nodes = []
864
832
        for node in found_nodes:
885
853
        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
886
854
        expected = [('readv', 'index', [(0, page_size)], False, None),
887
855
             ('readv',  'index', readv_request, False, None)]
888
 
        if expected != t._activity:
 
856
        if expected != transport._activity:
889
857
            self.assertEqualDiff(pprint.pformat(expected),
890
858
                                 pprint.pformat(transport._activity))
891
859
 
905
873
        nodes = self.make_nodes(160, 2, 2)
906
874
        for node in nodes:
907
875
            builder.add_node(*node)
908
 
        t = transport.get_transport('trace+' + self.get_url(''))
909
 
        size = t.put_file('index', builder.finish())
 
876
        transport = get_transport('trace+' + self.get_url(''))
 
877
        size = transport.put_file('index', builder.finish())
910
878
        del builder
911
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
912
 
        del t._activity[:]
913
 
        self.assertEqual([], t._activity)
 
879
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
880
        del transport._activity[:]
 
881
        self.assertEqual([], transport._activity)
914
882
        # search for one key
915
883
        found_nodes = list(index.iter_entries([nodes[30][0]]))
916
884
        bare_nodes = []
924
892
        # Should have read the root node, then one leaf page:
925
893
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
926
894
             ('readv',  'index', [(8192, 4096), ], False, None)],
927
 
            t._activity)
 
895
            transport._activity)
928
896
 
929
897
    def test_iter_key_prefix_1_element_key_None(self):
930
898
        index = self.make_index()
1012
980
            ])
1013
981
        self.assertEqual(set([]), index.external_references(0))
1014
982
 
1015
 
    def test__find_ancestors_one_page(self):
1016
 
        key1 = ('key-1',)
1017
 
        key2 = ('key-2',)
1018
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1019
 
            (key1, 'value', ([key2],)),
1020
 
            (key2, 'value', ([],)),
1021
 
            ])
1022
 
        parent_map = {}
1023
 
        missing_keys = set()
1024
 
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
1025
 
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
1026
 
        self.assertEqual(set(), missing_keys)
1027
 
        self.assertEqual(set(), search_keys)
1028
 
 
1029
 
    def test__find_ancestors_one_page_w_missing(self):
1030
 
        key1 = ('key-1',)
1031
 
        key2 = ('key-2',)
1032
 
        key3 = ('key-3',)
1033
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1034
 
            (key1, 'value', ([key2],)),
1035
 
            (key2, 'value', ([],)),
1036
 
            ])
1037
 
        parent_map = {}
1038
 
        missing_keys = set()
1039
 
        search_keys = index._find_ancestors([key2, key3], 0, parent_map,
1040
 
                                            missing_keys)
1041
 
        self.assertEqual({key2: ()}, parent_map)
1042
 
        # we know that key3 is missing because we read the page that it would
1043
 
        # otherwise be on
1044
 
        self.assertEqual(set([key3]), missing_keys)
1045
 
        self.assertEqual(set(), search_keys)
1046
 
 
1047
 
    def test__find_ancestors_one_parent_missing(self):
1048
 
        key1 = ('key-1',)
1049
 
        key2 = ('key-2',)
1050
 
        key3 = ('key-3',)
1051
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1052
 
            (key1, 'value', ([key2],)),
1053
 
            (key2, 'value', ([key3],)),
1054
 
            ])
1055
 
        parent_map = {}
1056
 
        missing_keys = set()
1057
 
        search_keys = index._find_ancestors([key1], 0, parent_map,
1058
 
                                            missing_keys)
1059
 
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1060
 
        self.assertEqual(set(), missing_keys)
1061
 
        # all we know is that key3 wasn't present on the page we were reading
1062
 
        # but if you look, the last key is key2 which comes before key3, so we
1063
 
        # don't know whether key3 would land on this page or not.
1064
 
        self.assertEqual(set([key3]), search_keys)
1065
 
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
1066
 
                                            missing_keys)
1067
 
        # passing it back in, we are sure it is 'missing'
1068
 
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1069
 
        self.assertEqual(set([key3]), missing_keys)
1070
 
        self.assertEqual(set([]), search_keys)
1071
 
 
1072
 
    def test__find_ancestors_dont_search_known(self):
1073
 
        key1 = ('key-1',)
1074
 
        key2 = ('key-2',)
1075
 
        key3 = ('key-3',)
1076
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1077
 
            (key1, 'value', ([key2],)),
1078
 
            (key2, 'value', ([key3],)),
1079
 
            (key3, 'value', ([],)),
1080
 
            ])
1081
 
        # We already know about key2, so we won't try to search for key3
1082
 
        parent_map = {key2: (key3,)}
1083
 
        missing_keys = set()
1084
 
        search_keys = index._find_ancestors([key1], 0, parent_map,
1085
 
                                            missing_keys)
1086
 
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1087
 
        self.assertEqual(set(), missing_keys)
1088
 
        self.assertEqual(set(), search_keys)
1089
 
 
1090
 
    def test__find_ancestors_multiple_pages(self):
1091
 
        # We need to use enough keys that we actually cause a split
1092
 
        start_time = 1249671539
1093
 
        email = "joebob@example.com"
1094
 
        nodes = []
1095
 
        ref_lists = ((),)
1096
 
        rev_keys = []
1097
 
        for i in xrange(400):
1098
 
            rev_id = '%s-%s-%s' % (email,
1099
 
                                   osutils.compact_date(start_time + i),
1100
 
                                   osutils.rand_chars(16))
1101
 
            rev_key = (rev_id,)
1102
 
            nodes.append((rev_key, 'value', ref_lists))
1103
 
            # We have a ref 'list' of length 1, with a list of parents, with 1
1104
 
            # parent which is a key
1105
 
            ref_lists = ((rev_key,),)
1106
 
            rev_keys.append(rev_key)
1107
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=nodes)
1108
 
        self.assertEqual(400, index.key_count())
1109
 
        self.assertEqual(3, len(index._row_offsets))
1110
 
        nodes = dict(index._read_nodes([1, 2]))
1111
 
        l1 = nodes[1]
1112
 
        l2 = nodes[2]
1113
 
        min_l2_key = l2.min_key
1114
 
        max_l1_key = l1.max_key
1115
 
        self.assertTrue(max_l1_key < min_l2_key)
1116
 
        parents_min_l2_key = l2[min_l2_key][1][0]
1117
 
        self.assertEqual((l1.max_key,), parents_min_l2_key)
1118
 
        # Now, whatever key we select that would fall on the second page,
1119
 
        # should give us all the parents until the page break
1120
 
        key_idx = rev_keys.index(min_l2_key)
1121
 
        next_key = rev_keys[key_idx+1]
1122
 
        # So now when we get the parent map, we should get the key we are
1123
 
        # looking for, min_l2_key, and then a reference to go look for the
1124
 
        # parent of that key
1125
 
        parent_map = {}
1126
 
        missing_keys = set()
1127
 
        search_keys = index._find_ancestors([next_key], 0, parent_map,
1128
 
                                            missing_keys)
1129
 
        self.assertEqual([min_l2_key, next_key], sorted(parent_map))
1130
 
        self.assertEqual(set(), missing_keys)
1131
 
        self.assertEqual(set([max_l1_key]), search_keys)
1132
 
        parent_map = {}
1133
 
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
1134
 
                                            missing_keys)
1135
 
        self.assertEqual(l1.all_keys(), sorted(parent_map))
1136
 
        self.assertEqual(set(), missing_keys)
1137
 
        self.assertEqual(set(), search_keys)
1138
 
 
1139
 
    def test__find_ancestors_empty_index(self):
1140
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[])
1141
 
        parent_map = {}
1142
 
        missing_keys = set()
1143
 
        search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
1144
 
                                            missing_keys)
1145
 
        self.assertEqual(set(), search_keys)
1146
 
        self.assertEqual({}, parent_map)
1147
 
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
1148
 
 
1149
 
    def test_supports_unlimited_cache(self):
1150
 
        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)
1151
 
        # We need enough nodes to cause a page split (so we have both an
1152
 
        # internal node and a couple leaf nodes. 500 seems to be enough.)
1153
 
        nodes = self.make_nodes(500, 1, 0)
1154
 
        for node in nodes:
1155
 
            builder.add_node(*node)
1156
 
        stream = builder.finish()
1157
 
        trans = self.get_transport()
1158
 
        size = trans.put_file('index', stream)
1159
 
        index = btree_index.BTreeGraphIndex(trans, 'index', size)
1160
 
        self.assertEqual(500, index.key_count())
1161
 
        # We have an internal node
1162
 
        self.assertEqual(2, len(index._row_lengths))
1163
 
        # We have at least 2 leaf nodes
1164
 
        self.assertTrue(index._row_lengths[-1] >= 2)
1165
 
        self.assertIsInstance(index._leaf_node_cache, lru_cache.LRUCache)
1166
 
        self.assertEqual(btree_index._NODE_CACHE_SIZE,
1167
 
                         index._leaf_node_cache._max_cache)
1168
 
        self.assertIsInstance(index._internal_node_cache, fifo_cache.FIFOCache)
1169
 
        self.assertEqual(100, index._internal_node_cache._max_cache)
1170
 
        # No change if unlimited_cache=False is passed
1171
 
        index = btree_index.BTreeGraphIndex(trans, 'index', size,
1172
 
                                            unlimited_cache=False)
1173
 
        self.assertIsInstance(index._leaf_node_cache, lru_cache.LRUCache)
1174
 
        self.assertEqual(btree_index._NODE_CACHE_SIZE,
1175
 
                         index._leaf_node_cache._max_cache)
1176
 
        self.assertIsInstance(index._internal_node_cache, fifo_cache.FIFOCache)
1177
 
        self.assertEqual(100, index._internal_node_cache._max_cache)
1178
 
        index = btree_index.BTreeGraphIndex(trans, 'index', size,
1179
 
                                            unlimited_cache=True)
1180
 
        self.assertIsInstance(index._leaf_node_cache, dict)
1181
 
        self.assertIs(type(index._internal_node_cache), dict)
1182
 
        # Exercise the lookup code
1183
 
        entries = set(index.iter_entries([n[0] for n in nodes]))
1184
 
        self.assertEqual(500, len(entries))
1185
 
 
1186
983
 
1187
984
class TestBTreeNodes(BTreeTestCase):
1188
985
 
1189
 
    scenarios = btreeparser_scenarios()
 
986
    def restore_parser(self):
 
987
        btree_index._btree_serializer = self.saved_parser
1190
988
 
1191
989
    def setUp(self):
1192
990
        BTreeTestCase.setUp(self)
1193
 
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
 
991
        self.saved_parser = btree_index._btree_serializer
 
992
        self.addCleanup(self.restore_parser)
 
993
        btree_index._btree_serializer = self.parse_btree
1194
994
 
1195
995
    def test_LeafNode_1_0(self):
1196
996
        node_bytes = ("type=leaf\n"
1208
1008
            ("2222222222222222222222222222222222222222",): ("value:2", ()),
1209
1009
            ("3333333333333333333333333333333333333333",): ("value:3", ()),
1210
1010
            ("4444444444444444444444444444444444444444",): ("value:4", ()),
1211
 
            }, dict(node.all_items()))
 
1011
            }, node.keys)
1212
1012
 
1213
1013
    def test_LeafNode_2_2(self):
1214
1014
        node_bytes = ("type=leaf\n"
1228
1028
            ('11', '33'): ('value:3',
1229
1029
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1230
1030
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1231
 
            }, dict(node.all_items()))
 
1031
            }, node.keys)
1232
1032
 
1233
1033
    def test_InternalNode_1(self):
1234
1034
        node_bytes = ("type=internal\n"
1269
1069
            ('11', '33'): ('value:3',
1270
1070
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1271
1071
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1272
 
            }, dict(node.all_items()))
 
1072
            }, node.keys)
1273
1073
 
1274
1074
    def assertFlattened(self, expected, key, value, refs):
1275
1075
        flat_key, flat_line = self.parse_btree._flatten_node(
1307
1107
    def test_exists(self):
1308
1108
        # This is just to let the user know if they don't have the feature
1309
1109
        # available
1310
 
        self.requireFeature(compiled_btreeparser_feature)
 
1110
        self.requireFeature(CompiledBtreeParserFeature)
1311
1111
 
1312
1112
 
1313
1113
class TestMultiBisectRight(tests.TestCase):
1353
1153
        This doesn't actually create anything on disk, it just primes a
1354
1154
        BTreeGraphIndex with the recommended information.
1355
1155
        """
1356
 
        index = btree_index.BTreeGraphIndex(
1357
 
            transport.get_transport('memory:///'), 'test-index', size=size)
 
1156
        index = btree_index.BTreeGraphIndex(get_transport('memory:///'),
 
1157
                                            'test-index', size=size)
1358
1158
        if recommended_pages is not None:
1359
1159
            index._recommended_pages = recommended_pages
1360
1160
        return index