← 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-08-17 18:13:57 UTC
  • mfrom: (5268.7.29 transport-segments)
  • Revision ID: pqm@pqm.ubuntu.com-20110817181357-y5q5eth1hk8bl3om
(jelmer) Allow specifying the colocated branch to use in the branch URL,
 and retrieving the branch name using ControlDir._get_selected_branch.
 (Jelmer Vernooij)

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