← 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: Launchpad Translations on behalf of bzr-core
  • Date: 2013-03-29 04:30:34 UTC
  • mto: (6581.1.1 trunk)
  • mto: This revision was merged to the branch mainline in revision 6582.
  • Revision ID: launchpad_translations_on_behalf_of_bzr-core-20130329043034-xbst4001gnhtm0mi
Launchpad automatic translations update.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
1
 
# Copyright (C) 2008, 2009, 2010 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
31
31
    )
32
32
from bzrlib.tests import (
33
33
    TestCaseWithTransport,
34
 
    condition_isinstance,
35
 
    multiply_tests,
36
 
    split_suite_by_condition,
37
 
    )
38
 
 
39
 
 
40
 
def load_tests(standard_tests, module, loader):
41
 
    # parameterise the TestBTreeNodes tests
42
 
    node_tests, others = split_suite_by_condition(standard_tests,
43
 
        condition_isinstance(TestBTreeNodes))
 
34
    scenarios,
 
35
    )
 
36
from bzrlib.tests import (
 
37
    features,
 
38
    )
 
39
 
 
40
 
 
41
load_tests = scenarios.load_tests_apply_scenarios
 
42
 
 
43
 
 
44
def btreeparser_scenarios():
44
45
    import bzrlib._btree_serializer_py as py_module
45
46
    scenarios = [('python', {'parse_btree': py_module})]
46
47
    if compiled_btreeparser_feature.available():
47
 
        scenarios.append(('C', {'parse_btree':
48
 
                                compiled_btreeparser_feature.module}))
49
 
    return multiply_tests(node_tests, scenarios, others)
50
 
 
51
 
 
52
 
compiled_btreeparser_feature = tests.ModuleAvailableFeature(
53
 
                                'bzrlib._btree_serializer_pyx')
 
48
        scenarios.append(('C', 
 
49
            {'parse_btree': compiled_btreeparser_feature.module}))
 
50
    return scenarios
 
51
 
 
52
 
 
53
compiled_btreeparser_feature = features.ModuleAvailableFeature(
 
54
    'bzrlib._btree_serializer_pyx')
54
55
 
55
56
 
56
57
class BTreeTestCase(TestCaseWithTransport):
102
103
        self.overrideAttr(btree_index, '_PAGE_SIZE')
103
104
        btree_index._PAGE_SIZE = 2048
104
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
 
105
116
 
106
117
class TestBTreeBuilder(BTreeTestCase):
107
118
 
198
209
        temp_file = builder.finish()
199
210
        content = temp_file.read()
200
211
        del temp_file
201
 
        self.assertEqual(9283, len(content))
 
212
        self.assertEqualsApproxCompressed(9283, len(content))
202
213
        self.assertEqual(
203
214
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
204
215
            "row_lengths=1,2\n",
216
227
        leaf1_bytes = zlib.decompress(leaf1)
217
228
        sorted_node_keys = sorted(node[0] for node in nodes)
218
229
        node = btree_index._LeafNode(leaf1_bytes, 1, 0)
219
 
        self.assertEqual(231, len(node.keys))
220
 
        self.assertEqual(sorted_node_keys[:231], sorted(node.keys))
 
230
        self.assertEqual(231, len(node))
 
231
        self.assertEqual(sorted_node_keys[:231], node.all_keys())
221
232
        leaf2_bytes = zlib.decompress(leaf2)
222
233
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
223
 
        self.assertEqual(400 - 231, len(node.keys))
224
 
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
 
234
        self.assertEqual(400 - 231, len(node))
 
235
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
225
236
 
226
237
    def test_last_page_rounded_1_layer(self):
227
238
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
232
243
        temp_file = builder.finish()
233
244
        content = temp_file.read()
234
245
        del temp_file
235
 
        self.assertEqual(155, len(content))
 
246
        self.assertEqualsApproxCompressed(155, len(content))
236
247
        self.assertEqual(
237
248
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
238
249
            "row_lengths=1\n",
241
252
        leaf2 = content[74:]
242
253
        leaf2_bytes = zlib.decompress(leaf2)
243
254
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
244
 
        self.assertEqual(10, len(node.keys))
 
255
        self.assertEqual(10, len(node))
245
256
        sorted_node_keys = sorted(node[0] for node in nodes)
246
 
        self.assertEqual(sorted_node_keys, sorted(node.keys))
 
257
        self.assertEqual(sorted_node_keys, node.all_keys())
247
258
 
248
259
    def test_last_page_not_rounded_2_layer(self):
249
260
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
254
265
        temp_file = builder.finish()
255
266
        content = temp_file.read()
256
267
        del temp_file
257
 
        self.assertEqual(9283, len(content))
 
268
        self.assertEqualsApproxCompressed(9283, len(content))
258
269
        self.assertEqual(
259
270
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
260
271
            "row_lengths=1,2\n",
263
274
        leaf2 = content[8192:]
264
275
        leaf2_bytes = zlib.decompress(leaf2)
265
276
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
266
 
        self.assertEqual(400 - 231, len(node.keys))
 
277
        self.assertEqual(400 - 231, len(node))
267
278
        sorted_node_keys = sorted(node[0] for node in nodes)
268
 
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
 
279
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
269
280
 
270
281
    def test_three_level_tree_details(self):
271
282
        # The left most pointer in the second internal node in a row should
280
291
 
281
292
        for node in nodes:
282
293
            builder.add_node(*node)
283
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
294
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
284
295
        size = t.put_file('index', self.time(builder.finish))
285
296
        del builder
286
297
        index = btree_index.BTreeGraphIndex(t, 'index', size)
302
313
        # in the second node it points at
303
314
        pos = index._row_offsets[2] + internal_node2.offset + 1
304
315
        leaf = index._get_leaf_nodes([pos])[pos]
305
 
        self.assertTrue(internal_node2.keys[0] in leaf.keys)
 
316
        self.assertTrue(internal_node2.keys[0] in leaf)
306
317
 
307
318
    def test_2_leaves_2_2(self):
308
319
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
313
324
        temp_file = builder.finish()
314
325
        content = temp_file.read()
315
326
        del temp_file
316
 
        self.assertEqual(12643, len(content))
 
327
        self.assertEqualsApproxCompressed(12643, len(content))
317
328
        self.assertEqual(
318
329
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
319
330
            "row_lengths=1,3\n",
607
618
        for key, value, references in nodes:
608
619
            builder.add_node(key, value, references)
609
620
        stream = builder.finish()
610
 
        trans = transport.get_transport('trace+' + self.get_url())
 
621
        trans = transport.get_transport_from_url('trace+' + self.get_url())
611
622
        size = trans.put_file('index', stream)
612
623
        return btree_index.BTreeGraphIndex(trans, 'index', size)
613
624
 
648
659
        self.assertEqual(0, len(index._leaf_node_cache))
649
660
 
650
661
    def test_trivial_constructor(self):
651
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
662
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
652
663
        index = btree_index.BTreeGraphIndex(t, 'index', None)
653
664
        # Checks the page size at load, but that isn't logged yet.
654
665
        self.assertEqual([], t._activity)
655
666
 
656
667
    def test_with_size_constructor(self):
657
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
668
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
658
669
        index = btree_index.BTreeGraphIndex(t, 'index', 1)
659
670
        # Checks the page size at load, but that isn't logged yet.
660
671
        self.assertEqual([], t._activity)
661
672
 
662
673
    def test_empty_key_count_no_size(self):
663
674
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
664
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
675
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
665
676
        t.put_file('index', builder.finish())
666
677
        index = btree_index.BTreeGraphIndex(t, 'index', None)
667
678
        del t._activity[:]
674
685
 
675
686
    def test_empty_key_count(self):
676
687
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
677
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
688
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
678
689
        size = t.put_file('index', builder.finish())
679
690
        self.assertEqual(72, size)
680
691
        index = btree_index.BTreeGraphIndex(t, 'index', size)
690
701
        nodes = self.make_nodes(35, 2, 2)
691
702
        for node in nodes:
692
703
            builder.add_node(*node)
693
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
704
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
694
705
        size = t.put_file('index', builder.finish())
695
706
        index = btree_index.BTreeGraphIndex(t, 'index', size)
696
707
        del t._activity[:]
699
710
        # The entire index should have been read, as it is one page long.
700
711
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
701
712
            t._activity)
702
 
        self.assertEqual(1173, size)
 
713
        self.assertEqualsApproxCompressed(1173, size)
703
714
 
704
715
    def test_with_offset_no_size(self):
705
716
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
722
733
 
723
734
    def test__read_nodes_no_size_one_page_reads_once(self):
724
735
        self.make_index(nodes=[(('key',), 'value', ())])
725
 
        trans = transport.get_transport('trace+' + self.get_url())
 
736
        trans = transport.get_transport_from_url('trace+' + self.get_url())
726
737
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
727
738
        del trans._activity[:]
728
739
        nodes = dict(index._read_nodes([0]))
729
740
        self.assertEqual([0], nodes.keys())
730
741
        node = nodes[0]
731
 
        self.assertEqual([('key',)], node.keys.keys())
 
742
        self.assertEqual([('key',)], node.all_keys())
732
743
        self.assertEqual([('get', 'index')], trans._activity)
733
744
 
734
745
    def test__read_nodes_no_size_multiple_pages(self):
736
747
        index.key_count()
737
748
        num_pages = index._row_offsets[-1]
738
749
        # Reopen with a traced transport and no size
739
 
        trans = transport.get_transport('trace+' + self.get_url())
 
750
        trans = transport.get_transport_from_url('trace+' + self.get_url())
740
751
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
741
752
        del trans._activity[:]
742
753
        nodes = dict(index._read_nodes([0]))
747
758
        nodes = self.make_nodes(160, 2, 2)
748
759
        for node in nodes:
749
760
            builder.add_node(*node)
750
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
761
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
751
762
        size = t.put_file('index', builder.finish())
752
 
        self.assertEqual(17692, size)
 
763
        self.assertEqualsApproxCompressed(17692, size)
753
764
        index = btree_index.BTreeGraphIndex(t, 'index', size)
754
765
        del t._activity[:]
755
766
        self.assertEqual([], t._activity)
763
774
        nodes = self.make_nodes(45, 2, 2)
764
775
        for node in nodes:
765
776
            builder.add_node(*node)
766
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
777
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
767
778
        size = t.put_file('index', builder.finish())
768
779
        index = btree_index.BTreeGraphIndex(t, 'index', size)
769
780
        del t._activity[:]
772
783
        # The entire index should have been read linearly.
773
784
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
774
785
                         t._activity)
775
 
        self.assertEqual(1488, size)
 
786
        self.assertEqualsApproxCompressed(1488, size)
776
787
 
777
788
    def test_validate_two_pages(self):
778
789
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
779
790
        nodes = self.make_nodes(80, 2, 2)
780
791
        for node in nodes:
781
792
            builder.add_node(*node)
782
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
793
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
783
794
        size = t.put_file('index', builder.finish())
784
795
        # Root page, 2 leaf pages
785
 
        self.assertEqual(9339, size)
 
796
        self.assertEqualsApproxCompressed(9339, size)
786
797
        index = btree_index.BTreeGraphIndex(t, 'index', size)
787
798
        del t._activity[:]
788
799
        self.assertEqual([], t._activity)
789
800
        index.validate()
 
801
        rem = size - 8192 # Number of remaining bytes after second block
790
802
        # The entire index should have been read linearly.
791
803
        self.assertEqual(
792
804
            [('readv', 'index', [(0, 4096)], False, None),
793
 
             ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
 
805
             ('readv', 'index', [(4096, 4096), (8192, rem)], False, None)],
794
806
            t._activity)
795
807
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
796
808
        # node and make validate find them.
797
809
 
798
810
    def test_eq_ne(self):
799
811
        # two indices are equal when constructed with the same parameters:
800
 
        t1 = transport.get_transport('trace+' + self.get_url(''))
801
 
        t2 = transport.get_transport(self.get_url(''))
 
812
        t1 = transport.get_transport_from_url('trace+' + self.get_url(''))
 
813
        t2 = self.get_transport()
802
814
        self.assertTrue(
803
815
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
804
816
            btree_index.BTreeGraphIndex(t1, 'index', None))
830
842
            btree_index.BTreeGraphIndex(t1, 'index', 10) !=
831
843
            btree_index.BTreeGraphIndex(t1, 'index', 20))
832
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
        
833
853
    def test_iter_all_only_root_no_size(self):
834
854
        self.make_index(nodes=[(('key',), 'value', ())])
835
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
855
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
836
856
        index = btree_index.BTreeGraphIndex(t, 'index', None)
837
857
        del t._activity[:]
838
858
        self.assertEqual([(('key',), 'value')],
849
869
        nodes = self.make_nodes(10000, 2, 2)
850
870
        for node in nodes:
851
871
            builder.add_node(*node)
852
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
872
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
853
873
        size = t.put_file('index', builder.finish())
854
 
        self.assertEqual(1303220, size, 'number of expected bytes in the'
855
 
                                        ' output changed')
856
874
        page_size = btree_index._PAGE_SIZE
857
875
        del builder
858
876
        index = btree_index.BTreeGraphIndex(t, 'index', size)
874
892
        # The entire index should have been read
875
893
        total_pages = sum(index._row_lengths)
876
894
        self.assertEqual(total_pages, index._row_offsets[-1])
877
 
        self.assertEqual(1303220, size)
 
895
        self.assertEqualsApproxCompressed(1303220, size)
878
896
        # The start of the leaves
879
897
        first_byte = index._row_offsets[-2] * page_size
880
898
        readv_request = []
881
899
        for offset in range(first_byte, size, page_size):
882
900
            readv_request.append((offset, page_size))
883
901
        # The last page is truncated
884
 
        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
 
902
        readv_request[-1] = (readv_request[-1][0], size % page_size)
885
903
        expected = [('readv', 'index', [(0, page_size)], False, None),
886
904
             ('readv',  'index', readv_request, False, None)]
887
905
        if expected != t._activity:
888
906
            self.assertEqualDiff(pprint.pformat(expected),
889
 
                                 pprint.pformat(transport._activity))
 
907
                                 pprint.pformat(t._activity))
890
908
 
891
909
    def _test_iter_entries_references_resolved(self):
892
910
        index = self.make_index(1, nodes=[
904
922
        nodes = self.make_nodes(160, 2, 2)
905
923
        for node in nodes:
906
924
            builder.add_node(*node)
907
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
925
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
908
926
        size = t.put_file('index', builder.finish())
909
927
        del builder
910
928
        index = btree_index.BTreeGraphIndex(t, 'index', size)
1112
1130
        min_l2_key = l2.min_key
1113
1131
        max_l1_key = l1.max_key
1114
1132
        self.assertTrue(max_l1_key < min_l2_key)
1115
 
        parents_min_l2_key = l2.keys[min_l2_key][1][0]
 
1133
        parents_min_l2_key = l2[min_l2_key][1][0]
1116
1134
        self.assertEqual((l1.max_key,), parents_min_l2_key)
1117
1135
        # Now, whatever key we select that would fall on the second page,
1118
1136
        # should give us all the parents until the page break
1131
1149
        parent_map = {}
1132
1150
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
1133
1151
                                            missing_keys)
1134
 
        self.assertEqual(sorted(l1.keys), sorted(parent_map))
 
1152
        self.assertEqual(l1.all_keys(), sorted(parent_map))
1135
1153
        self.assertEqual(set(), missing_keys)
1136
1154
        self.assertEqual(set(), search_keys)
1137
1155
 
1153
1171
        for node in nodes:
1154
1172
            builder.add_node(*node)
1155
1173
        stream = builder.finish()
1156
 
        trans = transport.get_transport(self.get_url())
 
1174
        trans = self.get_transport()
1157
1175
        size = trans.put_file('index', stream)
1158
1176
        index = btree_index.BTreeGraphIndex(trans, 'index', size)
1159
1177
        self.assertEqual(500, index.key_count())
1185
1203
 
1186
1204
class TestBTreeNodes(BTreeTestCase):
1187
1205
 
 
1206
    scenarios = btreeparser_scenarios()
 
1207
 
1188
1208
    def setUp(self):
1189
1209
        BTreeTestCase.setUp(self)
1190
1210
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
1205
1225
            ("2222222222222222222222222222222222222222",): ("value:2", ()),
1206
1226
            ("3333333333333333333333333333333333333333",): ("value:3", ()),
1207
1227
            ("4444444444444444444444444444444444444444",): ("value:4", ()),
1208
 
            }, node.keys)
 
1228
            }, dict(node.all_items()))
1209
1229
 
1210
1230
    def test_LeafNode_2_2(self):
1211
1231
        node_bytes = ("type=leaf\n"
1225
1245
            ('11', '33'): ('value:3',
1226
1246
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1227
1247
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1228
 
            }, node.keys)
 
1248
            }, dict(node.all_items()))
1229
1249
 
1230
1250
    def test_InternalNode_1(self):
1231
1251
        node_bytes = ("type=internal\n"
1266
1286
            ('11', '33'): ('value:3',
1267
1287
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1268
1288
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1269
 
            }, node.keys)
 
1289
            }, dict(node.all_items()))
1270
1290
 
1271
1291
    def assertFlattened(self, expected, key, value, refs):
1272
1292
        flat_key, flat_line = self.parse_btree._flatten_node(
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