← 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: Canonical.com Patch Queue Manager
  • Date: 2011-06-30 18:28:17 UTC
  • mfrom: (5967.10.2 test-cat)
  • Revision ID: pqm@pqm.ubuntu.com-20110630182817-83a5q9r9rxfkdn8r
(mbp) don't use subprocesses for testing cat (Martin Pool)

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