← 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: 2011-10-14 16:54:26 UTC
  • mfrom: (6216.1.1 remove-this-file)
  • Revision ID: pqm@pqm.ubuntu.com-20111014165426-tjix4e6idryf1r2z
(jelmer) Remove an accidentally committed .THIS file. (Jelmer Vernooij)

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):
216
217
        leaf1_bytes = zlib.decompress(leaf1)
217
218
        sorted_node_keys = sorted(node[0] for node in nodes)
218
219
        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))
 
220
        self.assertEqual(231, len(node))
 
221
        self.assertEqual(sorted_node_keys[:231], node.all_keys())
221
222
        leaf2_bytes = zlib.decompress(leaf2)
222
223
        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))
 
224
        self.assertEqual(400 - 231, len(node))
 
225
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
225
226
 
226
227
    def test_last_page_rounded_1_layer(self):
227
228
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
241
242
        leaf2 = content[74:]
242
243
        leaf2_bytes = zlib.decompress(leaf2)
243
244
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
244
 
        self.assertEqual(10, len(node.keys))
 
245
        self.assertEqual(10, len(node))
245
246
        sorted_node_keys = sorted(node[0] for node in nodes)
246
 
        self.assertEqual(sorted_node_keys, sorted(node.keys))
 
247
        self.assertEqual(sorted_node_keys, node.all_keys())
247
248
 
248
249
    def test_last_page_not_rounded_2_layer(self):
249
250
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
263
264
        leaf2 = content[8192:]
264
265
        leaf2_bytes = zlib.decompress(leaf2)
265
266
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
266
 
        self.assertEqual(400 - 231, len(node.keys))
 
267
        self.assertEqual(400 - 231, len(node))
267
268
        sorted_node_keys = sorted(node[0] for node in nodes)
268
 
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
 
269
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
269
270
 
270
271
    def test_three_level_tree_details(self):
271
272
        # The left most pointer in the second internal node in a row should
280
281
 
281
282
        for node in nodes:
282
283
            builder.add_node(*node)
283
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
284
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
284
285
        size = t.put_file('index', self.time(builder.finish))
285
286
        del builder
286
287
        index = btree_index.BTreeGraphIndex(t, 'index', size)
302
303
        # in the second node it points at
303
304
        pos = index._row_offsets[2] + internal_node2.offset + 1
304
305
        leaf = index._get_leaf_nodes([pos])[pos]
305
 
        self.assertTrue(internal_node2.keys[0] in leaf.keys)
 
306
        self.assertTrue(internal_node2.keys[0] in leaf)
306
307
 
307
308
    def test_2_leaves_2_2(self):
308
309
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
607
608
        for key, value, references in nodes:
608
609
            builder.add_node(key, value, references)
609
610
        stream = builder.finish()
610
 
        trans = transport.get_transport('trace+' + self.get_url())
 
611
        trans = transport.get_transport_from_url('trace+' + self.get_url())
611
612
        size = trans.put_file('index', stream)
612
613
        return btree_index.BTreeGraphIndex(trans, 'index', size)
613
614
 
648
649
        self.assertEqual(0, len(index._leaf_node_cache))
649
650
 
650
651
    def test_trivial_constructor(self):
651
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
652
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
652
653
        index = btree_index.BTreeGraphIndex(t, 'index', None)
653
654
        # Checks the page size at load, but that isn't logged yet.
654
655
        self.assertEqual([], t._activity)
655
656
 
656
657
    def test_with_size_constructor(self):
657
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
658
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
658
659
        index = btree_index.BTreeGraphIndex(t, 'index', 1)
659
660
        # Checks the page size at load, but that isn't logged yet.
660
661
        self.assertEqual([], t._activity)
661
662
 
662
663
    def test_empty_key_count_no_size(self):
663
664
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
664
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
665
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
665
666
        t.put_file('index', builder.finish())
666
667
        index = btree_index.BTreeGraphIndex(t, 'index', None)
667
668
        del t._activity[:]
674
675
 
675
676
    def test_empty_key_count(self):
676
677
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
677
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
678
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
678
679
        size = t.put_file('index', builder.finish())
679
680
        self.assertEqual(72, size)
680
681
        index = btree_index.BTreeGraphIndex(t, 'index', size)
690
691
        nodes = self.make_nodes(35, 2, 2)
691
692
        for node in nodes:
692
693
            builder.add_node(*node)
693
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
694
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
694
695
        size = t.put_file('index', builder.finish())
695
696
        index = btree_index.BTreeGraphIndex(t, 'index', size)
696
697
        del t._activity[:]
722
723
 
723
724
    def test__read_nodes_no_size_one_page_reads_once(self):
724
725
        self.make_index(nodes=[(('key',), 'value', ())])
725
 
        trans = transport.get_transport('trace+' + self.get_url())
 
726
        trans = transport.get_transport_from_url('trace+' + self.get_url())
726
727
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
727
728
        del trans._activity[:]
728
729
        nodes = dict(index._read_nodes([0]))
729
730
        self.assertEqual([0], nodes.keys())
730
731
        node = nodes[0]
731
 
        self.assertEqual([('key',)], node.keys.keys())
 
732
        self.assertEqual([('key',)], node.all_keys())
732
733
        self.assertEqual([('get', 'index')], trans._activity)
733
734
 
734
735
    def test__read_nodes_no_size_multiple_pages(self):
736
737
        index.key_count()
737
738
        num_pages = index._row_offsets[-1]
738
739
        # Reopen with a traced transport and no size
739
 
        trans = transport.get_transport('trace+' + self.get_url())
 
740
        trans = transport.get_transport_from_url('trace+' + self.get_url())
740
741
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
741
742
        del trans._activity[:]
742
743
        nodes = dict(index._read_nodes([0]))
747
748
        nodes = self.make_nodes(160, 2, 2)
748
749
        for node in nodes:
749
750
            builder.add_node(*node)
750
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
751
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
751
752
        size = t.put_file('index', builder.finish())
752
753
        self.assertEqual(17692, size)
753
754
        index = btree_index.BTreeGraphIndex(t, 'index', size)
763
764
        nodes = self.make_nodes(45, 2, 2)
764
765
        for node in nodes:
765
766
            builder.add_node(*node)
766
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
767
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
767
768
        size = t.put_file('index', builder.finish())
768
769
        index = btree_index.BTreeGraphIndex(t, 'index', size)
769
770
        del t._activity[:]
779
780
        nodes = self.make_nodes(80, 2, 2)
780
781
        for node in nodes:
781
782
            builder.add_node(*node)
782
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
783
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
783
784
        size = t.put_file('index', builder.finish())
784
785
        # Root page, 2 leaf pages
785
786
        self.assertEqual(9339, size)
797
798
 
798
799
    def test_eq_ne(self):
799
800
        # 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(''))
 
801
        t1 = transport.get_transport_from_url('trace+' + self.get_url(''))
 
802
        t2 = self.get_transport()
802
803
        self.assertTrue(
803
804
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
804
805
            btree_index.BTreeGraphIndex(t1, 'index', None))
832
833
 
833
834
    def test_iter_all_only_root_no_size(self):
834
835
        self.make_index(nodes=[(('key',), 'value', ())])
835
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
836
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
836
837
        index = btree_index.BTreeGraphIndex(t, 'index', None)
837
838
        del t._activity[:]
838
839
        self.assertEqual([(('key',), 'value')],
849
850
        nodes = self.make_nodes(10000, 2, 2)
850
851
        for node in nodes:
851
852
            builder.add_node(*node)
852
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
853
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
853
854
        size = t.put_file('index', builder.finish())
854
855
        self.assertEqual(1303220, size, 'number of expected bytes in the'
855
856
                                        ' output changed')
904
905
        nodes = self.make_nodes(160, 2, 2)
905
906
        for node in nodes:
906
907
            builder.add_node(*node)
907
 
        t = transport.get_transport('trace+' + self.get_url(''))
 
908
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
908
909
        size = t.put_file('index', builder.finish())
909
910
        del builder
910
911
        index = btree_index.BTreeGraphIndex(t, 'index', size)
1112
1113
        min_l2_key = l2.min_key
1113
1114
        max_l1_key = l1.max_key
1114
1115
        self.assertTrue(max_l1_key < min_l2_key)
1115
 
        parents_min_l2_key = l2.keys[min_l2_key][1][0]
 
1116
        parents_min_l2_key = l2[min_l2_key][1][0]
1116
1117
        self.assertEqual((l1.max_key,), parents_min_l2_key)
1117
1118
        # Now, whatever key we select that would fall on the second page,
1118
1119
        # should give us all the parents until the page break
1131
1132
        parent_map = {}
1132
1133
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
1133
1134
                                            missing_keys)
1134
 
        self.assertEqual(sorted(l1.keys), sorted(parent_map))
 
1135
        self.assertEqual(l1.all_keys(), sorted(parent_map))
1135
1136
        self.assertEqual(set(), missing_keys)
1136
1137
        self.assertEqual(set(), search_keys)
1137
1138
 
1153
1154
        for node in nodes:
1154
1155
            builder.add_node(*node)
1155
1156
        stream = builder.finish()
1156
 
        trans = transport.get_transport(self.get_url())
 
1157
        trans = self.get_transport()
1157
1158
        size = trans.put_file('index', stream)
1158
1159
        index = btree_index.BTreeGraphIndex(trans, 'index', size)
1159
1160
        self.assertEqual(500, index.key_count())
1185
1186
 
1186
1187
class TestBTreeNodes(BTreeTestCase):
1187
1188
 
 
1189
    scenarios = btreeparser_scenarios()
 
1190
 
1188
1191
    def setUp(self):
1189
1192
        BTreeTestCase.setUp(self)
1190
1193
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
1205
1208
            ("2222222222222222222222222222222222222222",): ("value:2", ()),
1206
1209
            ("3333333333333333333333333333333333333333",): ("value:3", ()),
1207
1210
            ("4444444444444444444444444444444444444444",): ("value:4", ()),
1208
 
            }, node.keys)
 
1211
            }, dict(node.all_items()))
1209
1212
 
1210
1213
    def test_LeafNode_2_2(self):
1211
1214
        node_bytes = ("type=leaf\n"
1225
1228
            ('11', '33'): ('value:3',
1226
1229
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1227
1230
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1228
 
            }, node.keys)
 
1231
            }, dict(node.all_items()))
1229
1232
 
1230
1233
    def test_InternalNode_1(self):
1231
1234
        node_bytes = ("type=internal\n"
1266
1269
            ('11', '33'): ('value:3',
1267
1270
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1268
1271
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1269
 
            }, node.keys)
 
1272
            }, dict(node.all_items()))
1270
1273
 
1271
1274
    def assertFlattened(self, expected, key, value, refs):
1272
1275
        flat_key, flat_line = self.parse_btree._flatten_node(
1351
1354
        BTreeGraphIndex with the recommended information.
1352
1355
        """
1353
1356
        index = btree_index.BTreeGraphIndex(
1354
 
            transport.get_transport('memory:///'), 'test-index', size=size)
 
1357
            transport.get_transport_from_url('memory:///'),
 
1358
            'test-index', size=size)
1355
1359
        if recommended_pages is not None:
1356
1360
            index._recommended_pages = recommended_pages
1357
1361
        return index