← 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: Richard Wilbur
  • Date: 2016-02-04 19:07:28 UTC
  • mto: This revision was merged to the branch mainline in revision 6618.
  • Revision ID: richard.wilbur@gmail.com-20160204190728-p0zvfii6zase0fw7
Update COPYING.txt from the original http://www.gnu.org/licenses/gpl-2.0.txt  (Only differences were in whitespace.)  Thanks to Petr Stodulka for pointing out the discrepancy.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
33
33
    TestCaseWithTransport,
34
34
    scenarios,
35
35
    )
 
36
from bzrlib.tests import (
 
37
    features,
 
38
    )
36
39
 
37
40
 
38
41
load_tests = scenarios.load_tests_apply_scenarios
47
50
    return scenarios
48
51
 
49
52
 
50
 
compiled_btreeparser_feature = tests.ModuleAvailableFeature(
 
53
compiled_btreeparser_feature = features.ModuleAvailableFeature(
51
54
    'bzrlib._btree_serializer_pyx')
52
55
 
53
56
 
56
59
    # that they test.
57
60
 
58
61
    def setUp(self):
59
 
        TestCaseWithTransport.setUp(self)
 
62
        super(BTreeTestCase, self).setUp()
60
63
        self.overrideAttr(btree_index, '_RESERVED_HEADER_BYTES', 100)
61
64
 
62
65
    def make_nodes(self, count, key_elements, reference_lists):
100
103
        self.overrideAttr(btree_index, '_PAGE_SIZE')
101
104
        btree_index._PAGE_SIZE = 2048
102
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
 
103
116
 
104
117
class TestBTreeBuilder(BTreeTestCase):
105
118
 
196
209
        temp_file = builder.finish()
197
210
        content = temp_file.read()
198
211
        del temp_file
199
 
        self.assertEqual(9283, len(content))
 
212
        self.assertEqualsApproxCompressed(9283, len(content))
200
213
        self.assertEqual(
201
214
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
202
215
            "row_lengths=1,2\n",
230
243
        temp_file = builder.finish()
231
244
        content = temp_file.read()
232
245
        del temp_file
233
 
        self.assertEqual(155, len(content))
 
246
        self.assertEqualsApproxCompressed(155, len(content))
234
247
        self.assertEqual(
235
248
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
236
249
            "row_lengths=1\n",
252
265
        temp_file = builder.finish()
253
266
        content = temp_file.read()
254
267
        del temp_file
255
 
        self.assertEqual(9283, len(content))
 
268
        self.assertEqualsApproxCompressed(9283, len(content))
256
269
        self.assertEqual(
257
270
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
258
271
            "row_lengths=1,2\n",
278
291
 
279
292
        for node in nodes:
280
293
            builder.add_node(*node)
281
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
294
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
282
295
        size = t.put_file('index', self.time(builder.finish))
283
296
        del builder
284
297
        index = btree_index.BTreeGraphIndex(t, 'index', size)
311
324
        temp_file = builder.finish()
312
325
        content = temp_file.read()
313
326
        del temp_file
314
 
        self.assertEqual(12643, len(content))
 
327
        self.assertEqualsApproxCompressed(12643, len(content))
315
328
        self.assertEqual(
316
329
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
317
330
            "row_lengths=1,3\n",
605
618
        for key, value, references in nodes:
606
619
            builder.add_node(key, value, references)
607
620
        stream = builder.finish()
608
 
        trans = transport.get_transport('trace+' + self.get_url())
 
621
        trans = transport.get_transport_from_url('trace+' + self.get_url())
609
622
        size = trans.put_file('index', stream)
610
623
        return btree_index.BTreeGraphIndex(trans, 'index', size)
611
624
 
646
659
        self.assertEqual(0, len(index._leaf_node_cache))
647
660
 
648
661
    def test_trivial_constructor(self):
649
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
662
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
650
663
        index = btree_index.BTreeGraphIndex(t, 'index', None)
651
664
        # Checks the page size at load, but that isn't logged yet.
652
665
        self.assertEqual([], t._activity)
653
666
 
654
667
    def test_with_size_constructor(self):
655
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
668
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
656
669
        index = btree_index.BTreeGraphIndex(t, 'index', 1)
657
670
        # Checks the page size at load, but that isn't logged yet.
658
671
        self.assertEqual([], t._activity)
659
672
 
660
673
    def test_empty_key_count_no_size(self):
661
674
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
662
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
675
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
663
676
        t.put_file('index', builder.finish())
664
677
        index = btree_index.BTreeGraphIndex(t, 'index', None)
665
678
        del t._activity[:]
672
685
 
673
686
    def test_empty_key_count(self):
674
687
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
675
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
688
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
676
689
        size = t.put_file('index', builder.finish())
677
690
        self.assertEqual(72, size)
678
691
        index = btree_index.BTreeGraphIndex(t, 'index', size)
688
701
        nodes = self.make_nodes(35, 2, 2)
689
702
        for node in nodes:
690
703
            builder.add_node(*node)
691
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
704
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
692
705
        size = t.put_file('index', builder.finish())
693
706
        index = btree_index.BTreeGraphIndex(t, 'index', size)
694
707
        del t._activity[:]
697
710
        # The entire index should have been read, as it is one page long.
698
711
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
699
712
            t._activity)
700
 
        self.assertEqual(1173, size)
 
713
        self.assertEqualsApproxCompressed(1173, size)
701
714
 
702
715
    def test_with_offset_no_size(self):
703
716
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
720
733
 
721
734
    def test__read_nodes_no_size_one_page_reads_once(self):
722
735
        self.make_index(nodes=[(('key',), 'value', ())])
723
 
        trans = transport.get_transport('trace+' + self.get_url())
 
736
        trans = transport.get_transport_from_url('trace+' + self.get_url())
724
737
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
725
738
        del trans._activity[:]
726
739
        nodes = dict(index._read_nodes([0]))
734
747
        index.key_count()
735
748
        num_pages = index._row_offsets[-1]
736
749
        # Reopen with a traced transport and no size
737
 
        trans = transport.get_transport('trace+' + self.get_url())
 
750
        trans = transport.get_transport_from_url('trace+' + self.get_url())
738
751
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
739
752
        del trans._activity[:]
740
753
        nodes = dict(index._read_nodes([0]))
745
758
        nodes = self.make_nodes(160, 2, 2)
746
759
        for node in nodes:
747
760
            builder.add_node(*node)
748
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
761
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
749
762
        size = t.put_file('index', builder.finish())
750
 
        self.assertEqual(17692, size)
 
763
        self.assertEqualsApproxCompressed(17692, size)
751
764
        index = btree_index.BTreeGraphIndex(t, 'index', size)
752
765
        del t._activity[:]
753
766
        self.assertEqual([], t._activity)
761
774
        nodes = self.make_nodes(45, 2, 2)
762
775
        for node in nodes:
763
776
            builder.add_node(*node)
764
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
777
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
765
778
        size = t.put_file('index', builder.finish())
766
779
        index = btree_index.BTreeGraphIndex(t, 'index', size)
767
780
        del t._activity[:]
770
783
        # The entire index should have been read linearly.
771
784
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
772
785
                         t._activity)
773
 
        self.assertEqual(1488, size)
 
786
        self.assertEqualsApproxCompressed(1488, size)
774
787
 
775
788
    def test_validate_two_pages(self):
776
789
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
777
790
        nodes = self.make_nodes(80, 2, 2)
778
791
        for node in nodes:
779
792
            builder.add_node(*node)
780
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
793
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
781
794
        size = t.put_file('index', builder.finish())
782
795
        # Root page, 2 leaf pages
783
 
        self.assertEqual(9339, size)
 
796
        self.assertEqualsApproxCompressed(9339, size)
784
797
        index = btree_index.BTreeGraphIndex(t, 'index', size)
785
798
        del t._activity[:]
786
799
        self.assertEqual([], t._activity)
787
800
        index.validate()
 
801
        rem = size - 8192 # Number of remaining bytes after second block
788
802
        # The entire index should have been read linearly.
789
803
        self.assertEqual(
790
804
            [('readv', 'index', [(0, 4096)], False, None),
791
 
             ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
 
805
             ('readv', 'index', [(4096, 4096), (8192, rem)], False, None)],
792
806
            t._activity)
793
807
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
794
808
        # node and make validate find them.
795
809
 
796
810
    def test_eq_ne(self):
797
811
        # two indices are equal when constructed with the same parameters:
798
 
        t1 = transport.get_transport('trace+' + self.get_url(''))
 
812
        t1 = transport.get_transport_from_url('trace+' + self.get_url(''))
799
813
        t2 = self.get_transport()
800
814
        self.assertTrue(
801
815
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
828
842
            btree_index.BTreeGraphIndex(t1, 'index', 10) !=
829
843
            btree_index.BTreeGraphIndex(t1, 'index', 20))
830
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
        
831
853
    def test_iter_all_only_root_no_size(self):
832
854
        self.make_index(nodes=[(('key',), 'value', ())])
833
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
855
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
834
856
        index = btree_index.BTreeGraphIndex(t, 'index', None)
835
857
        del t._activity[:]
836
858
        self.assertEqual([(('key',), 'value')],
847
869
        nodes = self.make_nodes(10000, 2, 2)
848
870
        for node in nodes:
849
871
            builder.add_node(*node)
850
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
872
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
851
873
        size = t.put_file('index', builder.finish())
852
 
        self.assertEqual(1303220, size, 'number of expected bytes in the'
853
 
                                        ' output changed')
854
874
        page_size = btree_index._PAGE_SIZE
855
875
        del builder
856
876
        index = btree_index.BTreeGraphIndex(t, 'index', size)
872
892
        # The entire index should have been read
873
893
        total_pages = sum(index._row_lengths)
874
894
        self.assertEqual(total_pages, index._row_offsets[-1])
875
 
        self.assertEqual(1303220, size)
 
895
        self.assertEqualsApproxCompressed(1303220, size)
876
896
        # The start of the leaves
877
897
        first_byte = index._row_offsets[-2] * page_size
878
898
        readv_request = []
879
899
        for offset in range(first_byte, size, page_size):
880
900
            readv_request.append((offset, page_size))
881
901
        # The last page is truncated
882
 
        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
 
902
        readv_request[-1] = (readv_request[-1][0], size % page_size)
883
903
        expected = [('readv', 'index', [(0, page_size)], False, None),
884
904
             ('readv',  'index', readv_request, False, None)]
885
905
        if expected != t._activity:
886
906
            self.assertEqualDiff(pprint.pformat(expected),
887
 
                                 pprint.pformat(transport._activity))
 
907
                                 pprint.pformat(t._activity))
888
908
 
889
909
    def _test_iter_entries_references_resolved(self):
890
910
        index = self.make_index(1, nodes=[
902
922
        nodes = self.make_nodes(160, 2, 2)
903
923
        for node in nodes:
904
924
            builder.add_node(*node)
905
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
925
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
906
926
        size = t.put_file('index', builder.finish())
907
927
        del builder
908
928
        index = btree_index.BTreeGraphIndex(t, 'index', size)
1186
1206
    scenarios = btreeparser_scenarios()
1187
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