← 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: Patch Queue Manager
  • Date: 2016-02-01 19:13:13 UTC
  • mfrom: (6614.2.2 trunk)
  • Revision ID: pqm@pqm.ubuntu.com-20160201191313-wdfvmfff1djde6oq
(vila) Release 2.7.0 (Vincent Ladeuil)

Show diffs side-by-side

added added

removed removed

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