← 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: 2010-08-13 19:08:57 UTC
  • mto: (5050.17.7 2.2)
  • mto: This revision was merged to the branch mainline in revision 5379.
  • Revision ID: john@arbash-meinel.com-20100813190857-mvzwnimrxvm0zimp
Lots of documentation updates.

We had a lot of http links pointing to the old domain. They should
all now be properly updated to the new domain. (only bazaar-vcs.org
entry left is for pqm, which seems to still reside at the old url.)

Also removed one 'TODO' doc entry about switching to binary xdelta, since
we basically did just that with groupcompress.

Show diffs side-by-side

added added

removed removed

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