← 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: Andrew Bennetts
  • Date: 2010-10-08 08:15:14 UTC
  • mto: This revision was merged to the branch mainline in revision 5498.
  • Revision ID: andrew.bennetts@canonical.com-20101008081514-dviqzrdfwyzsqbz2
Split NEWS into per-release doc/en/release-notes/bzr-*.txt

Show diffs side-by-side

added added

removed removed

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