← 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: Jelmer Vernooij
  • Date: 2012-01-27 21:28:56 UTC
  • mto: This revision was merged to the branch mainline in revision 6460.
  • Revision ID: jelmer@samba.org-20120127212856-ewnjgn7fyblphcqw
Migrate mail_client to config stacks.

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
 
100
103
        self.overrideAttr(btree_index, '_PAGE_SIZE')
101
104
        btree_index._PAGE_SIZE = 2048
102
105
 
103
 
    def assertEqualsApproxCompressed(self, expected, actual, slop=6):
104
 
        """Check a count of compressed bytes is approximately as expected
105
 
 
106
 
        Relying on compressed length being stable even with fixed inputs is
107
 
        slightly bogus, but zlib is stable enough that this mostly works.
108
 
        """
109
 
        if not expected - slop < actual < expected + slop:
110
 
            self.fail("Expected around %d bytes compressed but got %d" %
111
 
                (expected, actual))
112
 
 
113
106
 
114
107
class TestBTreeBuilder(BTreeTestCase):
115
108
 
206
199
        temp_file = builder.finish()
207
200
        content = temp_file.read()
208
201
        del temp_file
209
 
        self.assertEqualsApproxCompressed(9283, len(content))
 
202
        self.assertEqual(9283, len(content))
210
203
        self.assertEqual(
211
204
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
212
205
            "row_lengths=1,2\n",
240
233
        temp_file = builder.finish()
241
234
        content = temp_file.read()
242
235
        del temp_file
243
 
        self.assertEqualsApproxCompressed(155, len(content))
 
236
        self.assertEqual(155, len(content))
244
237
        self.assertEqual(
245
238
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
246
239
            "row_lengths=1\n",
262
255
        temp_file = builder.finish()
263
256
        content = temp_file.read()
264
257
        del temp_file
265
 
        self.assertEqualsApproxCompressed(9283, len(content))
 
258
        self.assertEqual(9283, len(content))
266
259
        self.assertEqual(
267
260
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
268
261
            "row_lengths=1,2\n",
288
281
 
289
282
        for node in nodes:
290
283
            builder.add_node(*node)
291
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
284
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
292
285
        size = t.put_file('index', self.time(builder.finish))
293
286
        del builder
294
287
        index = btree_index.BTreeGraphIndex(t, 'index', size)
321
314
        temp_file = builder.finish()
322
315
        content = temp_file.read()
323
316
        del temp_file
324
 
        self.assertEqualsApproxCompressed(12643, len(content))
 
317
        self.assertEqual(12643, len(content))
325
318
        self.assertEqual(
326
319
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
327
320
            "row_lengths=1,3\n",
615
608
        for key, value, references in nodes:
616
609
            builder.add_node(key, value, references)
617
610
        stream = builder.finish()
618
 
        trans = transport.get_transport('trace+' + self.get_url())
 
611
        trans = transport.get_transport_from_url('trace+' + self.get_url())
619
612
        size = trans.put_file('index', stream)
620
613
        return btree_index.BTreeGraphIndex(trans, 'index', size)
621
614
 
656
649
        self.assertEqual(0, len(index._leaf_node_cache))
657
650
 
658
651
    def test_trivial_constructor(self):
659
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
652
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
660
653
        index = btree_index.BTreeGraphIndex(t, 'index', None)
661
654
        # Checks the page size at load, but that isn't logged yet.
662
655
        self.assertEqual([], t._activity)
663
656
 
664
657
    def test_with_size_constructor(self):
665
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
658
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
666
659
        index = btree_index.BTreeGraphIndex(t, 'index', 1)
667
660
        # Checks the page size at load, but that isn't logged yet.
668
661
        self.assertEqual([], t._activity)
669
662
 
670
663
    def test_empty_key_count_no_size(self):
671
664
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
672
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
665
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
673
666
        t.put_file('index', builder.finish())
674
667
        index = btree_index.BTreeGraphIndex(t, 'index', None)
675
668
        del t._activity[:]
682
675
 
683
676
    def test_empty_key_count(self):
684
677
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
685
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
678
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
686
679
        size = t.put_file('index', builder.finish())
687
680
        self.assertEqual(72, size)
688
681
        index = btree_index.BTreeGraphIndex(t, 'index', size)
698
691
        nodes = self.make_nodes(35, 2, 2)
699
692
        for node in nodes:
700
693
            builder.add_node(*node)
701
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
694
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
702
695
        size = t.put_file('index', builder.finish())
703
696
        index = btree_index.BTreeGraphIndex(t, 'index', size)
704
697
        del t._activity[:]
707
700
        # The entire index should have been read, as it is one page long.
708
701
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
709
702
            t._activity)
710
 
        self.assertEqualsApproxCompressed(1173, size)
 
703
        self.assertEqual(1173, size)
711
704
 
712
705
    def test_with_offset_no_size(self):
713
706
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
730
723
 
731
724
    def test__read_nodes_no_size_one_page_reads_once(self):
732
725
        self.make_index(nodes=[(('key',), 'value', ())])
733
 
        trans = transport.get_transport('trace+' + self.get_url())
 
726
        trans = transport.get_transport_from_url('trace+' + self.get_url())
734
727
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
735
728
        del trans._activity[:]
736
729
        nodes = dict(index._read_nodes([0]))
744
737
        index.key_count()
745
738
        num_pages = index._row_offsets[-1]
746
739
        # Reopen with a traced transport and no size
747
 
        trans = transport.get_transport('trace+' + self.get_url())
 
740
        trans = transport.get_transport_from_url('trace+' + self.get_url())
748
741
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
749
742
        del trans._activity[:]
750
743
        nodes = dict(index._read_nodes([0]))
755
748
        nodes = self.make_nodes(160, 2, 2)
756
749
        for node in nodes:
757
750
            builder.add_node(*node)
758
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
751
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
759
752
        size = t.put_file('index', builder.finish())
760
 
        self.assertEqualsApproxCompressed(17692, size)
 
753
        self.assertEqual(17692, size)
761
754
        index = btree_index.BTreeGraphIndex(t, 'index', size)
762
755
        del t._activity[:]
763
756
        self.assertEqual([], t._activity)
771
764
        nodes = self.make_nodes(45, 2, 2)
772
765
        for node in nodes:
773
766
            builder.add_node(*node)
774
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
767
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
775
768
        size = t.put_file('index', builder.finish())
776
769
        index = btree_index.BTreeGraphIndex(t, 'index', size)
777
770
        del t._activity[:]
780
773
        # The entire index should have been read linearly.
781
774
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
782
775
                         t._activity)
783
 
        self.assertEqualsApproxCompressed(1488, size)
 
776
        self.assertEqual(1488, size)
784
777
 
785
778
    def test_validate_two_pages(self):
786
779
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
787
780
        nodes = self.make_nodes(80, 2, 2)
788
781
        for node in nodes:
789
782
            builder.add_node(*node)
790
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
783
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
791
784
        size = t.put_file('index', builder.finish())
792
785
        # Root page, 2 leaf pages
793
 
        self.assertEqualsApproxCompressed(9339, size)
 
786
        self.assertEqual(9339, size)
794
787
        index = btree_index.BTreeGraphIndex(t, 'index', size)
795
788
        del t._activity[:]
796
789
        self.assertEqual([], t._activity)
797
790
        index.validate()
798
 
        rem = size - 8192 # Number of remaining bytes after second block
799
791
        # The entire index should have been read linearly.
800
792
        self.assertEqual(
801
793
            [('readv', 'index', [(0, 4096)], False, None),
802
 
             ('readv', 'index', [(4096, 4096), (8192, rem)], False, None)],
 
794
             ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
803
795
            t._activity)
804
796
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
805
797
        # node and make validate find them.
806
798
 
807
799
    def test_eq_ne(self):
808
800
        # two indices are equal when constructed with the same parameters:
809
 
        t1 = transport.get_transport('trace+' + self.get_url(''))
 
801
        t1 = transport.get_transport_from_url('trace+' + self.get_url(''))
810
802
        t2 = self.get_transport()
811
803
        self.assertTrue(
812
804
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
839
831
            btree_index.BTreeGraphIndex(t1, 'index', 10) !=
840
832
            btree_index.BTreeGraphIndex(t1, 'index', 20))
841
833
 
 
834
    def test_key_too_big(self):
 
835
        # the size that matters here is the _compressed_ size of the key, so we can't
 
836
        # do a simple character repeat.
 
837
        bigKey = ''.join(map(repr, xrange(btree_index._PAGE_SIZE)))
 
838
        self.assertRaises(errors.BadIndexKey,
 
839
                          self.make_index,
 
840
                          nodes=[((bigKey,), 'value', ())])
 
841
        
842
842
    def test_iter_all_only_root_no_size(self):
843
843
        self.make_index(nodes=[(('key',), 'value', ())])
844
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
844
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
845
845
        index = btree_index.BTreeGraphIndex(t, 'index', None)
846
846
        del t._activity[:]
847
847
        self.assertEqual([(('key',), 'value')],
858
858
        nodes = self.make_nodes(10000, 2, 2)
859
859
        for node in nodes:
860
860
            builder.add_node(*node)
861
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
861
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
862
862
        size = t.put_file('index', builder.finish())
 
863
        self.assertEqual(1303220, size, 'number of expected bytes in the'
 
864
                                        ' output changed')
863
865
        page_size = btree_index._PAGE_SIZE
864
866
        del builder
865
867
        index = btree_index.BTreeGraphIndex(t, 'index', size)
881
883
        # The entire index should have been read
882
884
        total_pages = sum(index._row_lengths)
883
885
        self.assertEqual(total_pages, index._row_offsets[-1])
884
 
        self.assertEqualsApproxCompressed(1303220, size)
 
886
        self.assertEqual(1303220, size)
885
887
        # The start of the leaves
886
888
        first_byte = index._row_offsets[-2] * page_size
887
889
        readv_request = []
888
890
        for offset in range(first_byte, size, page_size):
889
891
            readv_request.append((offset, page_size))
890
892
        # The last page is truncated
891
 
        readv_request[-1] = (readv_request[-1][0], size % page_size)
 
893
        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
892
894
        expected = [('readv', 'index', [(0, page_size)], False, None),
893
895
             ('readv',  'index', readv_request, False, None)]
894
896
        if expected != t._activity:
895
897
            self.assertEqualDiff(pprint.pformat(expected),
896
 
                                 pprint.pformat(t._activity))
 
898
                                 pprint.pformat(transport._activity))
897
899
 
898
900
    def _test_iter_entries_references_resolved(self):
899
901
        index = self.make_index(1, nodes=[
911
913
        nodes = self.make_nodes(160, 2, 2)
912
914
        for node in nodes:
913
915
            builder.add_node(*node)
914
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
916
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
915
917
        size = t.put_file('index', builder.finish())
916
918
        del builder
917
919
        index = btree_index.BTreeGraphIndex(t, 'index', size)
1360
1362
        BTreeGraphIndex with the recommended information.
1361
1363
        """
1362
1364
        index = btree_index.BTreeGraphIndex(
1363
 
            transport.get_transport('memory:///'), 'test-index', size=size)
 
1365
            transport.get_transport_from_url('memory:///'),
 
1366
            'test-index', size=size)
1364
1367
        if recommended_pages is not None:
1365
1368
            index._recommended_pages = recommended_pages
1366
1369
        return index