← 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: Vincent Ladeuil
  • Date: 2013-07-27 12:53:28 UTC
  • mto: This revision was merged to the branch mainline in revision 6583.
  • Revision ID: v.ladeuil+lp@free.fr-20130727125328-b5e0mzrfrpmnmy9t
Open trunk again as 2.7b1

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
1
 
# Copyright (C) 2008, 2009, 2010 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
31
31
    )
32
32
from bzrlib.tests import (
33
33
    TestCaseWithTransport,
34
 
    condition_isinstance,
35
 
    multiply_tests,
36
 
    split_suite_by_condition,
37
 
    )
38
 
 
39
 
 
40
 
def load_tests(standard_tests, module, loader):
41
 
    # parameterise the TestBTreeNodes tests
42
 
    node_tests, others = split_suite_by_condition(standard_tests,
43
 
        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():
44
45
    import bzrlib._btree_serializer_py as py_module
45
46
    scenarios = [('python', {'parse_btree': py_module})]
46
47
    if compiled_btreeparser_feature.available():
47
 
        scenarios.append(('C', {'parse_btree':
48
 
                                compiled_btreeparser_feature.module}))
49
 
    return multiply_tests(node_tests, scenarios, others)
50
 
 
51
 
 
52
 
compiled_btreeparser_feature = tests.ModuleAvailableFeature(
53
 
                                'bzrlib._btree_serializer_pyx')
 
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')
54
55
 
55
56
 
56
57
class BTreeTestCase(TestCaseWithTransport):
58
59
    # that they test.
59
60
 
60
61
    def setUp(self):
61
 
        TestCaseWithTransport.setUp(self)
 
62
        super(BTreeTestCase, self).setUp()
62
63
        self.overrideAttr(btree_index, '_RESERVED_HEADER_BYTES', 100)
63
64
 
64
65
    def make_nodes(self, count, key_elements, reference_lists):
102
103
        self.overrideAttr(btree_index, '_PAGE_SIZE')
103
104
        btree_index._PAGE_SIZE = 2048
104
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
 
105
116
 
106
117
class TestBTreeBuilder(BTreeTestCase):
107
118
 
198
209
        temp_file = builder.finish()
199
210
        content = temp_file.read()
200
211
        del temp_file
201
 
        self.assertEqual(9283, len(content))
 
212
        self.assertEqualsApproxCompressed(9283, len(content))
202
213
        self.assertEqual(
203
214
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
204
215
            "row_lengths=1,2\n",
232
243
        temp_file = builder.finish()
233
244
        content = temp_file.read()
234
245
        del temp_file
235
 
        self.assertEqual(155, len(content))
 
246
        self.assertEqualsApproxCompressed(155, len(content))
236
247
        self.assertEqual(
237
248
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
238
249
            "row_lengths=1\n",
254
265
        temp_file = builder.finish()
255
266
        content = temp_file.read()
256
267
        del temp_file
257
 
        self.assertEqual(9283, len(content))
 
268
        self.assertEqualsApproxCompressed(9283, len(content))
258
269
        self.assertEqual(
259
270
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
260
271
            "row_lengths=1,2\n",
280
291
 
281
292
        for node in nodes:
282
293
            builder.add_node(*node)
283
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
294
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
284
295
        size = t.put_file('index', self.time(builder.finish))
285
296
        del builder
286
297
        index = btree_index.BTreeGraphIndex(t, 'index', size)
313
324
        temp_file = builder.finish()
314
325
        content = temp_file.read()
315
326
        del temp_file
316
 
        self.assertEqual(12643, len(content))
 
327
        self.assertEqualsApproxCompressed(12643, len(content))
317
328
        self.assertEqual(
318
329
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
319
330
            "row_lengths=1,3\n",
607
618
        for key, value, references in nodes:
608
619
            builder.add_node(key, value, references)
609
620
        stream = builder.finish()
610
 
        trans = transport.get_transport('trace+' + self.get_url())
 
621
        trans = transport.get_transport_from_url('trace+' + self.get_url())
611
622
        size = trans.put_file('index', stream)
612
623
        return btree_index.BTreeGraphIndex(trans, 'index', size)
613
624
 
648
659
        self.assertEqual(0, len(index._leaf_node_cache))
649
660
 
650
661
    def test_trivial_constructor(self):
651
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
662
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
652
663
        index = btree_index.BTreeGraphIndex(t, 'index', None)
653
664
        # Checks the page size at load, but that isn't logged yet.
654
665
        self.assertEqual([], t._activity)
655
666
 
656
667
    def test_with_size_constructor(self):
657
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
668
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
658
669
        index = btree_index.BTreeGraphIndex(t, 'index', 1)
659
670
        # Checks the page size at load, but that isn't logged yet.
660
671
        self.assertEqual([], t._activity)
661
672
 
662
673
    def test_empty_key_count_no_size(self):
663
674
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
664
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
675
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
665
676
        t.put_file('index', builder.finish())
666
677
        index = btree_index.BTreeGraphIndex(t, 'index', None)
667
678
        del t._activity[:]
674
685
 
675
686
    def test_empty_key_count(self):
676
687
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
677
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
688
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
678
689
        size = t.put_file('index', builder.finish())
679
690
        self.assertEqual(72, size)
680
691
        index = btree_index.BTreeGraphIndex(t, 'index', size)
690
701
        nodes = self.make_nodes(35, 2, 2)
691
702
        for node in nodes:
692
703
            builder.add_node(*node)
693
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
704
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
694
705
        size = t.put_file('index', builder.finish())
695
706
        index = btree_index.BTreeGraphIndex(t, 'index', size)
696
707
        del t._activity[:]
699
710
        # The entire index should have been read, as it is one page long.
700
711
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
701
712
            t._activity)
702
 
        self.assertEqual(1173, size)
 
713
        self.assertEqualsApproxCompressed(1173, size)
703
714
 
704
715
    def test_with_offset_no_size(self):
705
716
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
722
733
 
723
734
    def test__read_nodes_no_size_one_page_reads_once(self):
724
735
        self.make_index(nodes=[(('key',), 'value', ())])
725
 
        trans = transport.get_transport('trace+' + self.get_url())
 
736
        trans = transport.get_transport_from_url('trace+' + self.get_url())
726
737
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
727
738
        del trans._activity[:]
728
739
        nodes = dict(index._read_nodes([0]))
736
747
        index.key_count()
737
748
        num_pages = index._row_offsets[-1]
738
749
        # Reopen with a traced transport and no size
739
 
        trans = transport.get_transport('trace+' + self.get_url())
 
750
        trans = transport.get_transport_from_url('trace+' + self.get_url())
740
751
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
741
752
        del trans._activity[:]
742
753
        nodes = dict(index._read_nodes([0]))
747
758
        nodes = self.make_nodes(160, 2, 2)
748
759
        for node in nodes:
749
760
            builder.add_node(*node)
750
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
761
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
751
762
        size = t.put_file('index', builder.finish())
752
 
        self.assertEqual(17692, size)
 
763
        self.assertEqualsApproxCompressed(17692, size)
753
764
        index = btree_index.BTreeGraphIndex(t, 'index', size)
754
765
        del t._activity[:]
755
766
        self.assertEqual([], t._activity)
763
774
        nodes = self.make_nodes(45, 2, 2)
764
775
        for node in nodes:
765
776
            builder.add_node(*node)
766
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
777
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
767
778
        size = t.put_file('index', builder.finish())
768
779
        index = btree_index.BTreeGraphIndex(t, 'index', size)
769
780
        del t._activity[:]
772
783
        # The entire index should have been read linearly.
773
784
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
774
785
                         t._activity)
775
 
        self.assertEqual(1488, size)
 
786
        self.assertEqualsApproxCompressed(1488, size)
776
787
 
777
788
    def test_validate_two_pages(self):
778
789
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
779
790
        nodes = self.make_nodes(80, 2, 2)
780
791
        for node in nodes:
781
792
            builder.add_node(*node)
782
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
793
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
783
794
        size = t.put_file('index', builder.finish())
784
795
        # Root page, 2 leaf pages
785
 
        self.assertEqual(9339, size)
 
796
        self.assertEqualsApproxCompressed(9339, size)
786
797
        index = btree_index.BTreeGraphIndex(t, 'index', size)
787
798
        del t._activity[:]
788
799
        self.assertEqual([], t._activity)
789
800
        index.validate()
 
801
        rem = size - 8192 # Number of remaining bytes after second block
790
802
        # The entire index should have been read linearly.
791
803
        self.assertEqual(
792
804
            [('readv', 'index', [(0, 4096)], False, None),
793
 
             ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
 
805
             ('readv', 'index', [(4096, 4096), (8192, rem)], False, None)],
794
806
            t._activity)
795
807
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
796
808
        # node and make validate find them.
797
809
 
798
810
    def test_eq_ne(self):
799
811
        # two indices are equal when constructed with the same parameters:
800
 
        t1 = transport.get_transport('trace+' + self.get_url(''))
801
 
        t2 = transport.get_transport(self.get_url(''))
 
812
        t1 = transport.get_transport_from_url('trace+' + self.get_url(''))
 
813
        t2 = self.get_transport()
802
814
        self.assertTrue(
803
815
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
804
816
            btree_index.BTreeGraphIndex(t1, 'index', None))
830
842
            btree_index.BTreeGraphIndex(t1, 'index', 10) !=
831
843
            btree_index.BTreeGraphIndex(t1, 'index', 20))
832
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
        
833
853
    def test_iter_all_only_root_no_size(self):
834
854
        self.make_index(nodes=[(('key',), 'value', ())])
835
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
855
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
836
856
        index = btree_index.BTreeGraphIndex(t, 'index', None)
837
857
        del t._activity[:]
838
858
        self.assertEqual([(('key',), 'value')],
849
869
        nodes = self.make_nodes(10000, 2, 2)
850
870
        for node in nodes:
851
871
            builder.add_node(*node)
852
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
872
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
853
873
        size = t.put_file('index', builder.finish())
854
 
        self.assertEqual(1303220, size, 'number of expected bytes in the'
855
 
                                        ' output changed')
856
874
        page_size = btree_index._PAGE_SIZE
857
875
        del builder
858
876
        index = btree_index.BTreeGraphIndex(t, 'index', size)
874
892
        # The entire index should have been read
875
893
        total_pages = sum(index._row_lengths)
876
894
        self.assertEqual(total_pages, index._row_offsets[-1])
877
 
        self.assertEqual(1303220, size)
 
895
        self.assertEqualsApproxCompressed(1303220, size)
878
896
        # The start of the leaves
879
897
        first_byte = index._row_offsets[-2] * page_size
880
898
        readv_request = []
881
899
        for offset in range(first_byte, size, page_size):
882
900
            readv_request.append((offset, page_size))
883
901
        # The last page is truncated
884
 
        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
 
902
        readv_request[-1] = (readv_request[-1][0], size % page_size)
885
903
        expected = [('readv', 'index', [(0, page_size)], False, None),
886
904
             ('readv',  'index', readv_request, False, None)]
887
905
        if expected != t._activity:
888
906
            self.assertEqualDiff(pprint.pformat(expected),
889
 
                                 pprint.pformat(transport._activity))
 
907
                                 pprint.pformat(t._activity))
890
908
 
891
909
    def _test_iter_entries_references_resolved(self):
892
910
        index = self.make_index(1, nodes=[
904
922
        nodes = self.make_nodes(160, 2, 2)
905
923
        for node in nodes:
906
924
            builder.add_node(*node)
907
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
925
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
908
926
        size = t.put_file('index', builder.finish())
909
927
        del builder
910
928
        index = btree_index.BTreeGraphIndex(t, 'index', size)
1153
1171
        for node in nodes:
1154
1172
            builder.add_node(*node)
1155
1173
        stream = builder.finish()
1156
 
        trans = transport.get_transport(self.get_url())
 
1174
        trans = self.get_transport()
1157
1175
        size = trans.put_file('index', stream)
1158
1176
        index = btree_index.BTreeGraphIndex(trans, 'index', size)
1159
1177
        self.assertEqual(500, index.key_count())
1185
1203
 
1186
1204
class TestBTreeNodes(BTreeTestCase):
1187
1205
 
 
1206
    scenarios = btreeparser_scenarios()
 
1207
 
1188
1208
    def setUp(self):
1189
 
        BTreeTestCase.setUp(self)
 
1209
        super(TestBTreeNodes, self).setUp()
1190
1210
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
1191
1211
 
1192
1212
    def test_LeafNode_1_0(self):
1351
1371
        BTreeGraphIndex with the recommended information.
1352
1372
        """
1353
1373
        index = btree_index.BTreeGraphIndex(
1354
 
            transport.get_transport('memory:///'), 'test-index', size=size)
 
1374
            transport.get_transport_from_url('memory:///'),
 
1375
            'test-index', size=size)
1355
1376
        if recommended_pages is not None:
1356
1377
            index._recommended_pages = recommended_pages
1357
1378
        return index