/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_btree_index.py

  • Committer: Martin Pool
  • Date: 2009-07-27 06:28:35 UTC
  • mto: This revision was merged to the branch mainline in revision 4587.
  • Revision ID: mbp@sourcefrog.net-20090727062835-o66p8it658tq1sma
Add CountedLock.get_physical_lock_status

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 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
20
20
import pprint
21
21
import zlib
22
22
 
23
 
from .. import (
 
23
from bzrlib import (
 
24
    btree_index,
24
25
    errors,
25
 
    fifo_cache,
26
 
    lru_cache,
27
 
    osutils,
28
26
    tests,
29
 
    transport,
30
 
    )
31
 
from ..bzr import (
32
 
    btree_index,
33
 
    index as _mod_index,
34
 
    )
35
 
from ..tests import (
 
27
    )
 
28
from bzrlib.tests import (
36
29
    TestCaseWithTransport,
37
 
    scenarios,
38
 
    )
39
 
from ..tests import (
40
 
    features,
41
 
    )
42
 
 
43
 
 
44
 
load_tests = scenarios.load_tests_apply_scenarios
45
 
 
46
 
 
47
 
def btreeparser_scenarios():
48
 
    import breezy.bzr._btree_serializer_py as py_module
 
30
    condition_isinstance,
 
31
    multiply_tests,
 
32
    split_suite_by_condition,
 
33
    )
 
34
from bzrlib.transport import get_transport
 
35
 
 
36
 
 
37
def load_tests(standard_tests, module, loader):
 
38
    # parameterise the TestBTreeNodes tests
 
39
    node_tests, others = split_suite_by_condition(standard_tests,
 
40
        condition_isinstance(TestBTreeNodes))
 
41
    import bzrlib._btree_serializer_py as py_module
49
42
    scenarios = [('python', {'parse_btree': py_module})]
50
 
    if compiled_btreeparser_feature.available():
51
 
        scenarios.append(('C',
52
 
                          {'parse_btree': compiled_btreeparser_feature.module}))
53
 
    return scenarios
54
 
 
55
 
 
56
 
compiled_btreeparser_feature = features.ModuleAvailableFeature(
57
 
    'breezy.bzr._btree_serializer_pyx')
 
43
    if CompiledBtreeParserFeature.available():
 
44
        # Is there a way to do this that gets missing feature failures rather
 
45
        # than no indication to the user?
 
46
        import bzrlib._btree_serializer_pyx as c_module
 
47
        scenarios.append(('C', {'parse_btree': c_module}))
 
48
    return multiply_tests(node_tests, scenarios, others)
 
49
 
 
50
 
 
51
class _CompiledBtreeParserFeature(tests.Feature):
 
52
    def _probe(self):
 
53
        try:
 
54
            import bzrlib._btree_serializer_pyx
 
55
        except ImportError:
 
56
            return False
 
57
        return True
 
58
 
 
59
    def feature_name(self):
 
60
        return 'bzrlib._btree_serializer_pyx'
 
61
 
 
62
CompiledBtreeParserFeature = _CompiledBtreeParserFeature()
58
63
 
59
64
 
60
65
class BTreeTestCase(TestCaseWithTransport):
62
67
    # that they test.
63
68
 
64
69
    def setUp(self):
65
 
        super(BTreeTestCase, self).setUp()
66
 
        self.overrideAttr(btree_index, '_RESERVED_HEADER_BYTES', 100)
 
70
        TestCaseWithTransport.setUp(self)
 
71
        self._original_header = btree_index._RESERVED_HEADER_BYTES
 
72
        def restore():
 
73
            btree_index._RESERVED_HEADER_BYTES = self._original_header
 
74
        self.addCleanup(restore)
 
75
        btree_index._RESERVED_HEADER_BYTES = 100
67
76
 
68
77
    def make_nodes(self, count, key_elements, reference_lists):
69
78
        """Generate count*key_elements sample nodes."""
70
 
        def _pos_to_key(pos, lead=b""):
71
 
            return (lead + (b"%d" % pos) * 40,)
72
79
        keys = []
73
80
        for prefix_pos in range(key_elements):
74
81
            if key_elements - 1:
75
 
                prefix = _pos_to_key(prefix_pos)
 
82
                prefix = (str(prefix_pos) * 40,)
76
83
            else:
77
84
                prefix = ()
78
 
            for pos in range(count):
 
85
            for pos in xrange(count):
79
86
                # TODO: This creates odd keys. When count == 100,000, it
80
87
                #       creates a 240 byte key
81
 
                key = prefix + _pos_to_key(pos)
82
 
                value = b"value:%d" % pos
 
88
                key = prefix + (str(pos) * 40,)
 
89
                value = "value:%s" % pos
83
90
                if reference_lists:
84
91
                    # generate some references
85
92
                    refs = []
92
99
                        for ref_pos in range(list_pos + pos % 2):
93
100
                            if pos % 2:
94
101
                                # refer to a nearby key
95
 
                                refs[-1].append(prefix
96
 
                                                + _pos_to_key(pos - 1, b"ref"))
 
102
                                refs[-1].append(prefix + ("ref" + str(pos - 1) * 40,))
97
103
                            else:
98
104
                                # serial of this ref in the ref list
99
 
                                refs[-1].append(prefix
100
 
                                                + _pos_to_key(ref_pos, b"ref"))
 
105
                                refs[-1].append(prefix + ("ref" + str(ref_pos) * 40,))
101
106
                        refs[-1] = tuple(refs[-1])
102
107
                    refs = tuple(refs)
103
108
                else:
107
112
 
108
113
    def shrink_page_size(self):
109
114
        """Shrink the default page size so that less fits in a page."""
110
 
        self.overrideAttr(btree_index, '_PAGE_SIZE')
 
115
        old_page_size = btree_index._PAGE_SIZE
 
116
        def cleanup():
 
117
            btree_index._PAGE_SIZE = old_page_size
 
118
        self.addCleanup(cleanup)
111
119
        btree_index._PAGE_SIZE = 2048
112
120
 
113
 
    def assertEqualApproxCompressed(self, expected, actual, slop=6):
114
 
        """Check a count of compressed bytes is approximately as expected
115
 
 
116
 
        Relying on compressed length being stable even with fixed inputs is
117
 
        slightly bogus, but zlib is stable enough that this mostly works.
118
 
        """
119
 
        if not expected - slop < actual < expected + slop:
120
 
            self.fail("Expected around %d bytes compressed but got %d" %
121
 
                      (expected, actual))
122
 
 
123
121
 
124
122
class TestBTreeBuilder(BTreeTestCase):
125
123
 
126
 
    def test_clear_cache(self):
127
 
        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)
128
 
        # This is a no-op, but we need the api to be consistent with other
129
 
        # BTreeGraphIndex apis.
130
 
        builder.clear_cache()
131
 
 
132
124
    def test_empty_1_0(self):
133
125
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
134
126
        # NamedTemporaryFile dies on builder.finish().read(). weird.
136
128
        content = temp_file.read()
137
129
        del temp_file
138
130
        self.assertEqual(
139
 
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=0\n"
140
 
            b"row_lengths=\n",
 
131
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=0\n"
 
132
            "row_lengths=\n",
141
133
            content)
142
134
 
143
135
    def test_empty_2_1(self):
147
139
        content = temp_file.read()
148
140
        del temp_file
149
141
        self.assertEqual(
150
 
            b"B+Tree Graph Index 2\nnode_ref_lists=1\nkey_elements=2\nlen=0\n"
151
 
            b"row_lengths=\n",
 
142
            "B+Tree Graph Index 2\nnode_ref_lists=1\nkey_elements=2\nlen=0\n"
 
143
            "row_lengths=\n",
152
144
            content)
153
145
 
154
146
    def test_root_leaf_1_0(self):
160
152
        temp_file = builder.finish()
161
153
        content = temp_file.read()
162
154
        del temp_file
163
 
        self.assertEqual(131, len(content))
 
155
        self.assertEqual(158, len(content))
164
156
        self.assertEqual(
165
 
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"
166
 
            b"row_lengths=1\n",
 
157
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"
 
158
            "row_lengths=1\n",
167
159
            content[:73])
168
160
        node_content = content[73:]
169
161
        node_bytes = zlib.decompress(node_content)
170
 
        expected_node = (b"type=leaf\n"
171
 
                         b"0000000000000000000000000000000000000000\x00\x00value:0\n"
172
 
                         b"1111111111111111111111111111111111111111\x00\x00value:1\n"
173
 
                         b"2222222222222222222222222222222222222222\x00\x00value:2\n"
174
 
                         b"3333333333333333333333333333333333333333\x00\x00value:3\n"
175
 
                         b"4444444444444444444444444444444444444444\x00\x00value:4\n")
 
162
        expected_node = ("type=leaf\n"
 
163
            "0000000000000000000000000000000000000000\x00\x00value:0\n"
 
164
            "1111111111111111111111111111111111111111\x00\x00value:1\n"
 
165
            "2222222222222222222222222222222222222222\x00\x00value:2\n"
 
166
            "3333333333333333333333333333333333333333\x00\x00value:3\n"
 
167
            "4444444444444444444444444444444444444444\x00\x00value:4\n")
176
168
        self.assertEqual(expected_node, node_bytes)
177
169
 
178
170
    def test_root_leaf_2_2(self):
184
176
        temp_file = builder.finish()
185
177
        content = temp_file.read()
186
178
        del temp_file
187
 
        self.assertEqual(238, len(content))
 
179
        self.assertEqual(264, len(content))
188
180
        self.assertEqual(
189
 
            b"B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"
190
 
            b"row_lengths=1\n",
 
181
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"
 
182
            "row_lengths=1\n",
191
183
            content[:74])
192
184
        node_content = content[74:]
193
185
        node_bytes = zlib.decompress(node_content)
194
186
        expected_node = (
195
 
            b"type=leaf\n"
196
 
            b"0000000000000000000000000000000000000000\x000000000000000000000000000000000000000000\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:0\n"
197
 
            b"0000000000000000000000000000000000000000\x001111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\r0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:1\n"
198
 
            b"0000000000000000000000000000000000000000\x002222222222222222222222222222222222222222\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:2\n"
199
 
            b"0000000000000000000000000000000000000000\x003333333333333333333333333333333333333333\x000000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\t0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\r0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\x00value:3\n"
200
 
            b"0000000000000000000000000000000000000000\x004444444444444444444444444444444444444444\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:4\n"
201
 
            b"1111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:0\n"
202
 
            b"1111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\r1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:1\n"
203
 
            b"1111111111111111111111111111111111111111\x002222222222222222222222222222222222222222\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:2\n"
204
 
            b"1111111111111111111111111111111111111111\x003333333333333333333333333333333333333333\x001111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\t1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\r1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\x00value:3\n"
205
 
            b"1111111111111111111111111111111111111111\x004444444444444444444444444444444444444444\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:4\n"
206
 
            b""
 
187
            "type=leaf\n"
 
188
            "0000000000000000000000000000000000000000\x000000000000000000000000000000000000000000\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:0\n"
 
189
            "0000000000000000000000000000000000000000\x001111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\r0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:1\n"
 
190
            "0000000000000000000000000000000000000000\x002222222222222222222222222222222222222222\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:2\n"
 
191
            "0000000000000000000000000000000000000000\x003333333333333333333333333333333333333333\x000000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\t0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\r0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\x00value:3\n"
 
192
            "0000000000000000000000000000000000000000\x004444444444444444444444444444444444444444\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:4\n"
 
193
            "1111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:0\n"
 
194
            "1111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\r1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:1\n"
 
195
            "1111111111111111111111111111111111111111\x002222222222222222222222222222222222222222\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:2\n"
 
196
            "1111111111111111111111111111111111111111\x003333333333333333333333333333333333333333\x001111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\t1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\r1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\x00value:3\n"
 
197
            "1111111111111111111111111111111111111111\x004444444444444444444444444444444444444444\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:4\n"
 
198
            ""
207
199
            )
208
200
        self.assertEqual(expected_node, node_bytes)
209
201
 
216
208
        temp_file = builder.finish()
217
209
        content = temp_file.read()
218
210
        del temp_file
219
 
        self.assertEqualApproxCompressed(9283, len(content))
 
211
        self.assertEqual(9283, len(content))
220
212
        self.assertEqual(
221
 
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
222
 
            b"row_lengths=1,2\n",
 
213
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
 
214
            "row_lengths=1,2\n",
223
215
            content[:77])
224
216
        root = content[77:4096]
225
217
        leaf1 = content[4096:8192]
226
218
        leaf2 = content[8192:]
227
219
        root_bytes = zlib.decompress(root)
228
220
        expected_root = (
229
 
            b"type=internal\n"
230
 
            b"offset=0\n"
231
 
            ) + (b"307" * 40) + b"\n"
 
221
            "type=internal\n"
 
222
            "offset=0\n"
 
223
            ) + ("307" * 40) + "\n"
232
224
        self.assertEqual(expected_root, root_bytes)
233
225
        # We already know serialisation works for leaves, check key selection:
234
226
        leaf1_bytes = zlib.decompress(leaf1)
235
227
        sorted_node_keys = sorted(node[0] for node in nodes)
236
228
        node = btree_index._LeafNode(leaf1_bytes, 1, 0)
237
 
        self.assertEqual(231, len(node))
238
 
        self.assertEqual(sorted_node_keys[:231], node.all_keys())
 
229
        self.assertEqual(231, len(node.keys))
 
230
        self.assertEqual(sorted_node_keys[:231], sorted(node.keys))
239
231
        leaf2_bytes = zlib.decompress(leaf2)
240
232
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
241
 
        self.assertEqual(400 - 231, len(node))
242
 
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
 
233
        self.assertEqual(400 - 231, len(node.keys))
 
234
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
243
235
 
244
236
    def test_last_page_rounded_1_layer(self):
245
237
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
250
242
        temp_file = builder.finish()
251
243
        content = temp_file.read()
252
244
        del temp_file
253
 
        self.assertEqualApproxCompressed(155, len(content))
 
245
        self.assertEqual(181, len(content))
254
246
        self.assertEqual(
255
 
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
256
 
            b"row_lengths=1\n",
 
247
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
 
248
            "row_lengths=1\n",
257
249
            content[:74])
258
250
        # Check thelast page is well formed
259
251
        leaf2 = content[74:]
260
252
        leaf2_bytes = zlib.decompress(leaf2)
261
253
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
262
 
        self.assertEqual(10, len(node))
 
254
        self.assertEqual(10, len(node.keys))
263
255
        sorted_node_keys = sorted(node[0] for node in nodes)
264
 
        self.assertEqual(sorted_node_keys, node.all_keys())
 
256
        self.assertEqual(sorted_node_keys, sorted(node.keys))
265
257
 
266
258
    def test_last_page_not_rounded_2_layer(self):
267
259
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
272
264
        temp_file = builder.finish()
273
265
        content = temp_file.read()
274
266
        del temp_file
275
 
        self.assertEqualApproxCompressed(9283, len(content))
 
267
        self.assertEqual(9283, len(content))
276
268
        self.assertEqual(
277
 
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
278
 
            b"row_lengths=1,2\n",
 
269
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
 
270
            "row_lengths=1,2\n",
279
271
            content[:77])
280
272
        # Check the last page is well formed
281
273
        leaf2 = content[8192:]
282
274
        leaf2_bytes = zlib.decompress(leaf2)
283
275
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
284
 
        self.assertEqual(400 - 231, len(node))
 
276
        self.assertEqual(400 - 231, len(node.keys))
285
277
        sorted_node_keys = sorted(node[0] for node in nodes)
286
 
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
 
278
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
287
279
 
288
280
    def test_three_level_tree_details(self):
289
281
        # The left most pointer in the second internal node in a row should
298
290
 
299
291
        for node in nodes:
300
292
            builder.add_node(*node)
301
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
302
 
        size = t.put_file('index', self.time(builder.finish))
 
293
        transport = get_transport('trace+' + self.get_url(''))
 
294
        size = transport.put_file('index', self.time(builder.finish))
303
295
        del builder
304
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
296
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
305
297
        # Seed the metadata, we're using internal calls now.
306
298
        index.key_count()
307
299
        self.assertEqual(3, len(index._row_lengths),
308
 
                         "Not enough rows: %r" % index._row_lengths)
 
300
            "Not enough rows: %r" % index._row_lengths)
309
301
        self.assertEqual(4, len(index._row_offsets))
310
302
        self.assertEqual(sum(index._row_lengths), index._row_offsets[-1])
311
303
        internal_nodes = index._get_internal_nodes([0, 1, 2])
320
312
        # in the second node it points at
321
313
        pos = index._row_offsets[2] + internal_node2.offset + 1
322
314
        leaf = index._get_leaf_nodes([pos])[pos]
323
 
        self.assertTrue(internal_node2.keys[0] in leaf)
 
315
        self.assertTrue(internal_node2.keys[0] in leaf.keys)
324
316
 
325
317
    def test_2_leaves_2_2(self):
326
318
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
331
323
        temp_file = builder.finish()
332
324
        content = temp_file.read()
333
325
        del temp_file
334
 
        self.assertEqualApproxCompressed(12643, len(content))
 
326
        self.assertEqual(12643, len(content))
335
327
        self.assertEqual(
336
 
            b"B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
337
 
            b"row_lengths=1,3\n",
 
328
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
 
329
            "row_lengths=1,3\n",
338
330
            content[:77])
339
331
        root = content[77:4096]
340
332
        leaf1 = content[4096:8192]
342
334
        leaf3 = content[12288:]
343
335
        root_bytes = zlib.decompress(root)
344
336
        expected_root = (
345
 
            b"type=internal\n"
346
 
            b"offset=0\n" +
347
 
            (b"0" * 40) + b"\x00" + (b"91" * 40) + b"\n" +
348
 
            (b"1" * 40) + b"\x00" + (b"81" * 40) + b"\n"
 
337
            "type=internal\n"
 
338
            "offset=0\n"
 
339
            + ("0" * 40) + "\x00" + ("91" * 40) + "\n"
 
340
            + ("1" * 40) + "\x00" + ("81" * 40) + "\n"
349
341
            )
350
342
        self.assertEqual(expected_root, root_bytes)
351
343
        # We assume the other leaf nodes have been written correctly - layering
358
350
        # Test the parts of the index that take up memory are doing so
359
351
        # predictably.
360
352
        self.assertEqual(1, len(builder._nodes))
 
353
        self.assertEqual(1, len(builder._keys))
361
354
        self.assertIs(None, builder._nodes_by_key)
362
355
        builder.add_node(*nodes[1])
363
356
        self.assertEqual(0, len(builder._nodes))
 
357
        self.assertEqual(0, len(builder._keys))
364
358
        self.assertIs(None, builder._nodes_by_key)
365
359
        self.assertEqual(1, len(builder._backing_indices))
366
360
        self.assertEqual(2, builder._backing_indices[0].key_count())
367
361
        # now back to memory
368
362
        builder.add_node(*nodes[2])
369
363
        self.assertEqual(1, len(builder._nodes))
 
364
        self.assertEqual(1, len(builder._keys))
370
365
        self.assertIs(None, builder._nodes_by_key)
371
366
        # And spills to a second backing index combing all
372
367
        builder.add_node(*nodes[3])
373
368
        self.assertEqual(0, len(builder._nodes))
 
369
        self.assertEqual(0, len(builder._keys))
374
370
        self.assertIs(None, builder._nodes_by_key)
375
371
        self.assertEqual(2, len(builder._backing_indices))
376
372
        self.assertEqual(None, builder._backing_indices[0])
379
375
        builder.add_node(*nodes[4])
380
376
        builder.add_node(*nodes[5])
381
377
        self.assertEqual(0, len(builder._nodes))
 
378
        self.assertEqual(0, len(builder._keys))
382
379
        self.assertIs(None, builder._nodes_by_key)
383
380
        self.assertEqual(2, len(builder._backing_indices))
384
381
        self.assertEqual(2, builder._backing_indices[0].key_count())
407
404
        # Test that memory and disk are both used for query methods; and that
408
405
        # None is skipped over happily.
409
406
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
410
 
                         list(builder.iter_all_entries()))
 
407
            list(builder.iter_all_entries()))
411
408
        # Two nodes - one memory one disk
412
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
413
 
                         set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
409
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
410
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
414
411
        self.assertEqual(13, builder.key_count())
415
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
416
 
                         set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
412
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
413
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
417
414
        builder.add_node(*nodes[13])
418
415
        self.assertEqual(3, len(builder._backing_indices))
419
416
        self.assertEqual(2, builder._backing_indices[0].key_count())
427
424
        self.assertEqual(None, builder._backing_indices[2])
428
425
        self.assertEqual(16, builder._backing_indices[3].key_count())
429
426
        # Now finish, and check we got a correctly ordered tree
430
 
        t = self.get_transport('')
431
 
        size = t.put_file('index', builder.finish())
432
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
427
        transport = self.get_transport('')
 
428
        size = transport.put_file('index', builder.finish())
 
429
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
433
430
        nodes = list(index.iter_all_entries())
434
431
        self.assertEqual(sorted(nodes), nodes)
435
432
        self.assertEqual(16, len(nodes))
442
439
        # Test the parts of the index that take up memory are doing so
443
440
        # predictably.
444
441
        self.assertEqual(1, len(builder._nodes))
 
442
        self.assertEqual(1, len(builder._keys))
445
443
        self.assertIs(None, builder._nodes_by_key)
446
444
        builder.add_node(*nodes[1])
447
445
        self.assertEqual(0, len(builder._nodes))
 
446
        self.assertEqual(0, len(builder._keys))
448
447
        self.assertIs(None, builder._nodes_by_key)
449
448
        self.assertEqual(1, len(builder._backing_indices))
450
449
        self.assertEqual(2, builder._backing_indices[0].key_count())
451
450
        # now back to memory
452
451
        builder.add_node(*nodes[2])
453
452
        self.assertEqual(1, len(builder._nodes))
 
453
        self.assertEqual(1, len(builder._keys))
454
454
        self.assertIs(None, builder._nodes_by_key)
455
455
        # And spills to a second backing index but doesn't combine
456
456
        builder.add_node(*nodes[3])
457
457
        self.assertEqual(0, len(builder._nodes))
 
458
        self.assertEqual(0, len(builder._keys))
458
459
        self.assertIs(None, builder._nodes_by_key)
459
460
        self.assertEqual(2, len(builder._backing_indices))
460
461
        for backing_index in builder._backing_indices:
463
464
        builder.add_node(*nodes[4])
464
465
        builder.add_node(*nodes[5])
465
466
        self.assertEqual(0, len(builder._nodes))
 
467
        self.assertEqual(0, len(builder._keys))
466
468
        self.assertIs(None, builder._nodes_by_key)
467
469
        self.assertEqual(3, len(builder._backing_indices))
468
470
        for backing_index in builder._backing_indices:
481
483
        # Test that memory and disk are both used for query methods; and that
482
484
        # None is skipped over happily.
483
485
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
484
 
                         list(builder.iter_all_entries()))
 
486
            list(builder.iter_all_entries()))
485
487
        # Two nodes - one memory one disk
486
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
487
 
                         set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
488
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
489
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
488
490
        self.assertEqual(13, builder.key_count())
489
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
490
 
                         set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
491
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
492
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
491
493
        builder.add_node(*nodes[13])
492
494
        builder.add_node(*nodes[14])
493
495
        builder.add_node(*nodes[15])
522
524
    def test_spill_index_stress_2_2(self):
523
525
        # test that references and longer keys don't confuse things.
524
526
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2,
525
 
                                           spill_at=2)
 
527
            spill_at=2)
526
528
        nodes = self.make_nodes(16, 2, 2)
527
529
        builder.add_node(*nodes[0])
528
530
        # Test the parts of the index that take up memory are doing so
529
531
        # predictably.
 
532
        self.assertEqual(1, len(builder._keys))
530
533
        self.assertEqual(1, len(builder._nodes))
531
534
        self.assertIs(None, builder._nodes_by_key)
532
535
        builder.add_node(*nodes[1])
 
536
        self.assertEqual(0, len(builder._keys))
533
537
        self.assertEqual(0, len(builder._nodes))
534
538
        self.assertIs(None, builder._nodes_by_key)
535
539
        self.assertEqual(1, len(builder._backing_indices))
536
540
        self.assertEqual(2, builder._backing_indices[0].key_count())
537
541
        # now back to memory
538
 
        # Build up the nodes by key dict
539
 
        old = dict(builder._get_nodes_by_key())
 
542
        old = dict(builder._get_nodes_by_key()) #Build up the nodes by key dict
540
543
        builder.add_node(*nodes[2])
541
544
        self.assertEqual(1, len(builder._nodes))
 
545
        self.assertEqual(1, len(builder._keys))
542
546
        self.assertIsNot(None, builder._nodes_by_key)
543
547
        self.assertNotEqual({}, builder._nodes_by_key)
544
548
        # We should have a new entry
546
550
        # And spills to a second backing index combing all
547
551
        builder.add_node(*nodes[3])
548
552
        self.assertEqual(0, len(builder._nodes))
 
553
        self.assertEqual(0, len(builder._keys))
549
554
        self.assertIs(None, builder._nodes_by_key)
550
555
        self.assertEqual(2, len(builder._backing_indices))
551
556
        self.assertEqual(None, builder._backing_indices[0])
554
559
        builder.add_node(*nodes[4])
555
560
        builder.add_node(*nodes[5])
556
561
        self.assertEqual(0, len(builder._nodes))
 
562
        self.assertEqual(0, len(builder._keys))
557
563
        self.assertIs(None, builder._nodes_by_key)
558
564
        self.assertEqual(2, len(builder._backing_indices))
559
565
        self.assertEqual(2, builder._backing_indices[0].key_count())
582
588
        # Test that memory and disk are both used for query methods; and that
583
589
        # None is skipped over happily.
584
590
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
585
 
                         list(builder.iter_all_entries()))
 
591
            list(builder.iter_all_entries()))
586
592
        # Two nodes - one memory one disk
587
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
588
 
                         set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
593
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
594
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
589
595
        self.assertEqual(13, builder.key_count())
590
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
591
 
                         set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
596
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
597
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
592
598
        builder.add_node(*nodes[13])
593
599
        self.assertEqual(3, len(builder._backing_indices))
594
600
        self.assertEqual(2, builder._backing_indices[0].key_count())
615
621
        builder.add_node(*nodes[0])
616
622
        builder.add_node(*nodes[1])
617
623
        builder.add_node(*nodes[0])
618
 
        self.assertRaises(_mod_index.BadIndexDuplicateKey, builder.finish)
 
624
        self.assertRaises(errors.BadIndexDuplicateKey, builder.finish)
619
625
 
620
626
 
621
627
class TestBTreeIndex(BTreeTestCase):
622
628
 
623
629
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
624
630
        builder = btree_index.BTreeBuilder(reference_lists=ref_lists,
625
 
                                           key_elements=key_elements)
 
631
            key_elements=key_elements)
626
632
        for key, value, references in nodes:
627
633
            builder.add_node(key, value, references)
628
634
        stream = builder.finish()
629
 
        trans = transport.get_transport_from_url('trace+' + self.get_url())
 
635
        trans = get_transport('trace+' + self.get_url())
630
636
        size = trans.put_file('index', stream)
631
637
        return btree_index.BTreeGraphIndex(trans, 'index', size)
632
638
 
633
 
    def make_index_with_offset(self, ref_lists=1, key_elements=1, nodes=[],
634
 
                               offset=0):
635
 
        builder = btree_index.BTreeBuilder(key_elements=key_elements,
636
 
                                           reference_lists=ref_lists)
637
 
        builder.add_nodes(nodes)
638
 
        transport = self.get_transport('')
639
 
        # NamedTemporaryFile dies on builder.finish().read(). weird.
640
 
        temp_file = builder.finish()
641
 
        content = temp_file.read()
642
 
        del temp_file
643
 
        size = len(content)
644
 
        transport.put_bytes('index', (b' ' * offset) + content)
645
 
        return btree_index.BTreeGraphIndex(transport, 'index', size=size,
646
 
                                           offset=offset)
647
 
 
648
 
    def test_clear_cache(self):
649
 
        nodes = self.make_nodes(160, 2, 2)
650
 
        index = self.make_index(ref_lists=2, key_elements=2, nodes=nodes)
651
 
        self.assertEqual(1, len(list(index.iter_entries([nodes[30][0]]))))
652
 
        self.assertEqual([1, 4], index._row_lengths)
653
 
        self.assertIsNot(None, index._root_node)
654
 
        internal_node_pre_clear = set(index._internal_node_cache)
655
 
        self.assertTrue(len(index._leaf_node_cache) > 0)
656
 
        index.clear_cache()
657
 
        # We don't touch _root_node or _internal_node_cache, both should be
658
 
        # small, and can save a round trip or two
659
 
        self.assertIsNot(None, index._root_node)
660
 
        # NOTE: We don't want to affect the _internal_node_cache, as we expect
661
 
        #       it will be small, and if we ever do touch this index again, it
662
 
        #       will save round-trips.  This assertion isn't very strong,
663
 
        #       becuase without a 3-level index, we don't have any internal
664
 
        #       nodes cached.
665
 
        self.assertEqual(internal_node_pre_clear,
666
 
                         set(index._internal_node_cache))
667
 
        self.assertEqual(0, len(index._leaf_node_cache))
668
 
 
669
639
    def test_trivial_constructor(self):
670
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
671
 
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
640
        transport = get_transport('trace+' + self.get_url(''))
 
641
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
672
642
        # Checks the page size at load, but that isn't logged yet.
673
 
        self.assertEqual([], t._activity)
 
643
        self.assertEqual([], transport._activity)
674
644
 
675
645
    def test_with_size_constructor(self):
676
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
677
 
        index = btree_index.BTreeGraphIndex(t, 'index', 1)
 
646
        transport = get_transport('trace+' + self.get_url(''))
 
647
        index = btree_index.BTreeGraphIndex(transport, 'index', 1)
678
648
        # Checks the page size at load, but that isn't logged yet.
679
 
        self.assertEqual([], t._activity)
 
649
        self.assertEqual([], transport._activity)
680
650
 
681
651
    def test_empty_key_count_no_size(self):
682
652
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
683
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
684
 
        t.put_file('index', builder.finish())
685
 
        index = btree_index.BTreeGraphIndex(t, 'index', None)
686
 
        del t._activity[:]
687
 
        self.assertEqual([], t._activity)
 
653
        transport = get_transport('trace+' + self.get_url(''))
 
654
        transport.put_file('index', builder.finish())
 
655
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
 
656
        del transport._activity[:]
 
657
        self.assertEqual([], transport._activity)
688
658
        self.assertEqual(0, index.key_count())
689
659
        # The entire index should have been requested (as we generally have the
690
660
        # size available, and doing many small readvs is inappropriate).
691
661
        # We can't tell how much was actually read here, but - check the code.
692
 
        self.assertEqual([('get', 'index')], t._activity)
 
662
        self.assertEqual([('get', 'index')], transport._activity)
693
663
 
694
664
    def test_empty_key_count(self):
695
665
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
696
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
697
 
        size = t.put_file('index', builder.finish())
 
666
        transport = get_transport('trace+' + self.get_url(''))
 
667
        size = transport.put_file('index', builder.finish())
698
668
        self.assertEqual(72, size)
699
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
700
 
        del t._activity[:]
701
 
        self.assertEqual([], t._activity)
 
669
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
670
        del transport._activity[:]
 
671
        self.assertEqual([], transport._activity)
702
672
        self.assertEqual(0, index.key_count())
703
673
        # The entire index should have been read, as 4K > size
704
674
        self.assertEqual([('readv', 'index', [(0, 72)], False, None)],
705
 
                         t._activity)
 
675
            transport._activity)
706
676
 
707
677
    def test_non_empty_key_count_2_2(self):
708
678
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
709
679
        nodes = self.make_nodes(35, 2, 2)
710
680
        for node in nodes:
711
681
            builder.add_node(*node)
712
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
713
 
        size = t.put_file('index', builder.finish())
714
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
715
 
        del t._activity[:]
716
 
        self.assertEqual([], t._activity)
 
682
        transport = get_transport('trace+' + self.get_url(''))
 
683
        size = transport.put_file('index', builder.finish())
 
684
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
685
        del transport._activity[:]
 
686
        self.assertEqual([], transport._activity)
717
687
        self.assertEqual(70, index.key_count())
718
688
        # The entire index should have been read, as it is one page long.
719
689
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
720
 
                         t._activity)
721
 
        self.assertEqualApproxCompressed(1173, size)
722
 
 
723
 
    def test_with_offset_no_size(self):
724
 
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
725
 
                                            offset=1234,
726
 
                                            nodes=self.make_nodes(200, 1, 1))
727
 
        index._size = None  # throw away the size info
728
 
        self.assertEqual(200, index.key_count())
729
 
 
730
 
    def test_with_small_offset(self):
731
 
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
732
 
                                            offset=1234,
733
 
                                            nodes=self.make_nodes(200, 1, 1))
734
 
        self.assertEqual(200, index.key_count())
735
 
 
736
 
    def test_with_large_offset(self):
737
 
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
738
 
                                            offset=123456,
739
 
                                            nodes=self.make_nodes(200, 1, 1))
740
 
        self.assertEqual(200, index.key_count())
 
690
            transport._activity)
 
691
        self.assertEqual(1199, size)
741
692
 
742
693
    def test__read_nodes_no_size_one_page_reads_once(self):
743
 
        self.make_index(nodes=[((b'key',), b'value', ())])
744
 
        trans = transport.get_transport_from_url('trace+' + self.get_url())
 
694
        self.make_index(nodes=[(('key',), 'value', ())])
 
695
        trans = get_transport('trace+' + self.get_url())
745
696
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
746
697
        del trans._activity[:]
747
698
        nodes = dict(index._read_nodes([0]))
748
 
        self.assertEqual({0}, set(nodes))
 
699
        self.assertEqual([0], nodes.keys())
749
700
        node = nodes[0]
750
 
        self.assertEqual([(b'key',)], node.all_keys())
 
701
        self.assertEqual([('key',)], node.keys.keys())
751
702
        self.assertEqual([('get', 'index')], trans._activity)
752
703
 
753
704
    def test__read_nodes_no_size_multiple_pages(self):
755
706
        index.key_count()
756
707
        num_pages = index._row_offsets[-1]
757
708
        # Reopen with a traced transport and no size
758
 
        trans = transport.get_transport_from_url('trace+' + self.get_url())
 
709
        trans = get_transport('trace+' + self.get_url())
759
710
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
760
711
        del trans._activity[:]
761
712
        nodes = dict(index._read_nodes([0]))
762
 
        self.assertEqual(list(range(num_pages)), sorted(nodes))
 
713
        self.assertEqual(range(num_pages), nodes.keys())
763
714
 
764
715
    def test_2_levels_key_count_2_2(self):
765
716
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
766
717
        nodes = self.make_nodes(160, 2, 2)
767
718
        for node in nodes:
768
719
            builder.add_node(*node)
769
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
770
 
        size = t.put_file('index', builder.finish())
771
 
        self.assertEqualApproxCompressed(17692, size)
772
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
773
 
        del t._activity[:]
774
 
        self.assertEqual([], t._activity)
 
720
        transport = get_transport('trace+' + self.get_url(''))
 
721
        size = transport.put_file('index', builder.finish())
 
722
        self.assertEqual(17692, size)
 
723
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
724
        del transport._activity[:]
 
725
        self.assertEqual([], transport._activity)
775
726
        self.assertEqual(320, index.key_count())
776
727
        # The entire index should not have been read.
777
728
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None)],
778
 
                         t._activity)
 
729
            transport._activity)
779
730
 
780
731
    def test_validate_one_page(self):
781
732
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
782
733
        nodes = self.make_nodes(45, 2, 2)
783
734
        for node in nodes:
784
735
            builder.add_node(*node)
785
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
786
 
        size = t.put_file('index', builder.finish())
787
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
788
 
        del t._activity[:]
789
 
        self.assertEqual([], t._activity)
 
736
        transport = get_transport('trace+' + self.get_url(''))
 
737
        size = transport.put_file('index', builder.finish())
 
738
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
739
        del transport._activity[:]
 
740
        self.assertEqual([], transport._activity)
790
741
        index.validate()
791
742
        # The entire index should have been read linearly.
792
743
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
793
 
                         t._activity)
794
 
        self.assertEqualApproxCompressed(1488, size)
 
744
            transport._activity)
 
745
        self.assertEqual(1514, size)
795
746
 
796
747
    def test_validate_two_pages(self):
797
748
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
798
749
        nodes = self.make_nodes(80, 2, 2)
799
750
        for node in nodes:
800
751
            builder.add_node(*node)
801
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
802
 
        size = t.put_file('index', builder.finish())
 
752
        transport = get_transport('trace+' + self.get_url(''))
 
753
        size = transport.put_file('index', builder.finish())
803
754
        # Root page, 2 leaf pages
804
 
        self.assertEqualApproxCompressed(9339, size)
805
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
806
 
        del t._activity[:]
807
 
        self.assertEqual([], t._activity)
 
755
        self.assertEqual(9339, size)
 
756
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
757
        del transport._activity[:]
 
758
        self.assertEqual([], transport._activity)
808
759
        index.validate()
809
 
        rem = size - 8192  # Number of remaining bytes after second block
810
760
        # The entire index should have been read linearly.
811
 
        self.assertEqual(
812
 
            [('readv', 'index', [(0, 4096)], False, None),
813
 
             ('readv', 'index', [(4096, 4096), (8192, rem)], False, None)],
814
 
            t._activity)
 
761
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
 
762
            ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
 
763
            transport._activity)
815
764
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
816
765
        # node and make validate find them.
817
766
 
818
767
    def test_eq_ne(self):
819
768
        # two indices are equal when constructed with the same parameters:
820
 
        t1 = transport.get_transport_from_url('trace+' + self.get_url(''))
821
 
        t2 = self.get_transport()
822
 
        self.assertTrue(
823
 
            btree_index.BTreeGraphIndex(t1, 'index', None)
824
 
            == btree_index.BTreeGraphIndex(t1, 'index', None))
825
 
        self.assertTrue(
826
 
            btree_index.BTreeGraphIndex(t1, 'index', 20)
827
 
            == btree_index.BTreeGraphIndex(t1, 'index', 20))
828
 
        self.assertFalse(
829
 
            btree_index.BTreeGraphIndex(t1, 'index', 20)
830
 
            == btree_index.BTreeGraphIndex(t2, 'index', 20))
831
 
        self.assertFalse(
832
 
            btree_index.BTreeGraphIndex(t1, 'inde1', 20)
833
 
            == btree_index.BTreeGraphIndex(t1, 'inde2', 20))
834
 
        self.assertFalse(
835
 
            btree_index.BTreeGraphIndex(t1, 'index', 10)
836
 
            == btree_index.BTreeGraphIndex(t1, 'index', 20))
837
 
        self.assertFalse(
838
 
            btree_index.BTreeGraphIndex(t1, 'index', None)
839
 
            != btree_index.BTreeGraphIndex(t1, 'index', None))
840
 
        self.assertFalse(
841
 
            btree_index.BTreeGraphIndex(t1, 'index', 20)
842
 
            != btree_index.BTreeGraphIndex(t1, 'index', 20))
843
 
        self.assertTrue(
844
 
            btree_index.BTreeGraphIndex(t1, 'index', 20)
845
 
            != btree_index.BTreeGraphIndex(t2, 'index', 20))
846
 
        self.assertTrue(
847
 
            btree_index.BTreeGraphIndex(t1, 'inde1', 20)
848
 
            != btree_index.BTreeGraphIndex(t1, 'inde2', 20))
849
 
        self.assertTrue(
850
 
            btree_index.BTreeGraphIndex(t1, 'index', 10)
851
 
            != btree_index.BTreeGraphIndex(t1, 'index', 20))
852
 
 
853
 
    def test_key_too_big(self):
854
 
        # the size that matters here is the _compressed_ size of the key, so we can't
855
 
        # do a simple character repeat.
856
 
        bigKey = b''.join(b'%d' % n for n in range(btree_index._PAGE_SIZE))
857
 
        self.assertRaises(_mod_index.BadIndexKey,
858
 
                          self.make_index,
859
 
                          nodes=[((bigKey,), b'value', ())])
 
769
        transport1 = get_transport('trace+' + self.get_url(''))
 
770
        transport2 = get_transport(self.get_url(''))
 
771
        self.assertTrue(
 
772
            btree_index.BTreeGraphIndex(transport1, 'index', None) ==
 
773
            btree_index.BTreeGraphIndex(transport1, 'index', None))
 
774
        self.assertTrue(
 
775
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
 
776
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
 
777
        self.assertFalse(
 
778
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
 
779
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
 
780
        self.assertFalse(
 
781
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) ==
 
782
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
 
783
        self.assertFalse(
 
784
            btree_index.BTreeGraphIndex(transport1, 'index', 10) ==
 
785
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
 
786
        self.assertFalse(
 
787
            btree_index.BTreeGraphIndex(transport1, 'index', None) !=
 
788
            btree_index.BTreeGraphIndex(transport1, 'index', None))
 
789
        self.assertFalse(
 
790
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
 
791
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
 
792
        self.assertTrue(
 
793
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
 
794
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
 
795
        self.assertTrue(
 
796
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) !=
 
797
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
 
798
        self.assertTrue(
 
799
            btree_index.BTreeGraphIndex(transport1, 'index', 10) !=
 
800
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
860
801
 
861
802
    def test_iter_all_only_root_no_size(self):
862
 
        self.make_index(nodes=[((b'key',), b'value', ())])
863
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
864
 
        index = btree_index.BTreeGraphIndex(t, 'index', None)
865
 
        del t._activity[:]
866
 
        self.assertEqual([((b'key',), b'value')],
 
803
        self.make_index(nodes=[(('key',), 'value', ())])
 
804
        trans = get_transport('trace+' + self.get_url(''))
 
805
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
 
806
        del trans._activity[:]
 
807
        self.assertEqual([(('key',), 'value')],
867
808
                         [x[1:] for x in index.iter_all_entries()])
868
 
        self.assertEqual([('get', 'index')], t._activity)
 
809
        self.assertEqual([('get', 'index')], trans._activity)
869
810
 
870
811
    def test_iter_all_entries_reads(self):
871
812
        # iterating all entries reads the header, then does a linear
877
818
        nodes = self.make_nodes(10000, 2, 2)
878
819
        for node in nodes:
879
820
            builder.add_node(*node)
880
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
881
 
        size = t.put_file('index', builder.finish())
 
821
        transport = get_transport('trace+' + self.get_url(''))
 
822
        size = transport.put_file('index', builder.finish())
 
823
        self.assertEqual(1303220, size, 'number of expected bytes in the'
 
824
                                        ' output changed')
882
825
        page_size = btree_index._PAGE_SIZE
883
826
        del builder
884
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
885
 
        del t._activity[:]
886
 
        self.assertEqual([], t._activity)
 
827
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
828
        del transport._activity[:]
 
829
        self.assertEqual([], transport._activity)
887
830
        found_nodes = self.time(list, index.iter_all_entries())
888
831
        bare_nodes = []
889
832
        for node in found_nodes:
890
833
            self.assertTrue(node[0] is index)
891
834
            bare_nodes.append(node[1:])
892
835
        self.assertEqual(3, len(index._row_lengths),
893
 
                         "Not enough rows: %r" % index._row_lengths)
 
836
            "Not enough rows: %r" % index._row_lengths)
894
837
        # Should be as long as the nodes we supplied
895
838
        self.assertEqual(20000, len(found_nodes))
896
839
        # Should have the same content
900
843
        # The entire index should have been read
901
844
        total_pages = sum(index._row_lengths)
902
845
        self.assertEqual(total_pages, index._row_offsets[-1])
903
 
        self.assertEqualApproxCompressed(1303220, size)
 
846
        self.assertEqual(1303220, size)
904
847
        # The start of the leaves
905
848
        first_byte = index._row_offsets[-2] * page_size
906
849
        readv_request = []
907
850
        for offset in range(first_byte, size, page_size):
908
851
            readv_request.append((offset, page_size))
909
852
        # The last page is truncated
910
 
        readv_request[-1] = (readv_request[-1][0], size % page_size)
 
853
        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
911
854
        expected = [('readv', 'index', [(0, page_size)], False, None),
912
 
                    ('readv', 'index', readv_request, False, None)]
913
 
        if expected != t._activity:
 
855
             ('readv',  'index', readv_request, False, None)]
 
856
        if expected != transport._activity:
914
857
            self.assertEqualDiff(pprint.pformat(expected),
915
 
                                 pprint.pformat(t._activity))
 
858
                                 pprint.pformat(transport._activity))
 
859
 
 
860
    def _test_iter_entries_references_resolved(self):
 
861
        index = self.make_index(1, nodes=[
 
862
            (('name', ), 'data', ([('ref', ), ('ref', )], )),
 
863
            (('ref', ), 'refdata', ([], ))])
 
864
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),('ref',)),)),
 
865
            (index, ('ref', ), 'refdata', ((), ))]),
 
866
            set(index.iter_entries([('name',), ('ref',)])))
916
867
 
917
868
    def test_iter_entries_references_2_refs_resolved(self):
918
869
        # iterating some entries reads just the pages needed. For now, to
922
873
        nodes = self.make_nodes(160, 2, 2)
923
874
        for node in nodes:
924
875
            builder.add_node(*node)
925
 
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
926
 
        size = t.put_file('index', builder.finish())
 
876
        transport = get_transport('trace+' + self.get_url(''))
 
877
        size = transport.put_file('index', builder.finish())
927
878
        del builder
928
 
        index = btree_index.BTreeGraphIndex(t, 'index', size)
929
 
        del t._activity[:]
930
 
        self.assertEqual([], t._activity)
 
879
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
880
        del transport._activity[:]
 
881
        self.assertEqual([], transport._activity)
931
882
        # search for one key
932
883
        found_nodes = list(index.iter_entries([nodes[30][0]]))
933
884
        bare_nodes = []
940
891
        self.assertEqual(nodes[30], bare_nodes[0])
941
892
        # Should have read the root node, then one leaf page:
942
893
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
943
 
                          ('readv', 'index', [(8192, 4096), ], False, None)],
944
 
                         t._activity)
 
894
             ('readv',  'index', [(8192, 4096), ], False, None)],
 
895
            transport._activity)
945
896
 
946
897
    def test_iter_key_prefix_1_element_key_None(self):
947
898
        index = self.make_index()
948
 
        self.assertRaises(_mod_index.BadIndexKey, list,
949
 
                          index.iter_entries_prefix([(None, )]))
 
899
        self.assertRaises(errors.BadIndexKey, list,
 
900
            index.iter_entries_prefix([(None, )]))
950
901
 
951
902
    def test_iter_key_prefix_wrong_length(self):
952
903
        index = self.make_index()
953
 
        self.assertRaises(_mod_index.BadIndexKey, list,
954
 
                          index.iter_entries_prefix([(b'foo', None)]))
 
904
        self.assertRaises(errors.BadIndexKey, list,
 
905
            index.iter_entries_prefix([('foo', None)]))
955
906
        index = self.make_index(key_elements=2)
956
 
        self.assertRaises(_mod_index.BadIndexKey, list,
957
 
                          index.iter_entries_prefix([(b'foo', )]))
958
 
        self.assertRaises(_mod_index.BadIndexKey, list,
959
 
                          index.iter_entries_prefix([(b'foo', None, None)]))
 
907
        self.assertRaises(errors.BadIndexKey, list,
 
908
            index.iter_entries_prefix([('foo', )]))
 
909
        self.assertRaises(errors.BadIndexKey, list,
 
910
            index.iter_entries_prefix([('foo', None, None)]))
960
911
 
961
912
    def test_iter_key_prefix_1_key_element_no_refs(self):
962
 
        index = self.make_index(nodes=[
963
 
            ((b'name', ), b'data', ()),
964
 
            ((b'ref', ), b'refdata', ())])
965
 
        self.assertEqual({(index, (b'name', ), b'data'),
966
 
                          (index, (b'ref', ), b'refdata')},
967
 
                         set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
 
913
        index = self.make_index( nodes=[
 
914
            (('name', ), 'data', ()),
 
915
            (('ref', ), 'refdata', ())])
 
916
        self.assertEqual(set([(index, ('name', ), 'data'),
 
917
            (index, ('ref', ), 'refdata')]),
 
918
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
968
919
 
969
920
    def test_iter_key_prefix_1_key_element_refs(self):
970
921
        index = self.make_index(1, nodes=[
971
 
            ((b'name', ), b'data', ([(b'ref', )], )),
972
 
            ((b'ref', ), b'refdata', ([], ))])
973
 
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),)),
974
 
                          (index, (b'ref', ), b'refdata', ((), ))},
975
 
                         set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
 
922
            (('name', ), 'data', ([('ref', )], )),
 
923
            (('ref', ), 'refdata', ([], ))])
 
924
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
 
925
            (index, ('ref', ), 'refdata', ((), ))]),
 
926
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
976
927
 
977
928
    def test_iter_key_prefix_2_key_element_no_refs(self):
978
929
        index = self.make_index(key_elements=2, nodes=[
979
 
            ((b'name', b'fin1'), b'data', ()),
980
 
            ((b'name', b'fin2'), b'beta', ()),
981
 
            ((b'ref', b'erence'), b'refdata', ())])
982
 
        self.assertEqual({(index, (b'name', b'fin1'), b'data'),
983
 
                          (index, (b'ref', b'erence'), b'refdata')},
984
 
                         set(index.iter_entries_prefix(
985
 
                             [(b'name', b'fin1'), (b'ref', b'erence')])))
986
 
        self.assertEqual({(index, (b'name', b'fin1'), b'data'),
987
 
                          (index, (b'name', b'fin2'), b'beta')},
988
 
                         set(index.iter_entries_prefix([(b'name', None)])))
 
930
            (('name', 'fin1'), 'data', ()),
 
931
            (('name', 'fin2'), 'beta', ()),
 
932
            (('ref', 'erence'), 'refdata', ())])
 
933
        self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
 
934
            (index, ('ref', 'erence'), 'refdata')]),
 
935
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
 
936
        self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
 
937
            (index, ('name', 'fin2'), 'beta')]),
 
938
            set(index.iter_entries_prefix([('name', None)])))
989
939
 
990
940
    def test_iter_key_prefix_2_key_element_refs(self):
991
941
        index = self.make_index(1, key_elements=2, nodes=[
992
 
            ((b'name', b'fin1'), b'data', ([(b'ref', b'erence')], )),
993
 
            ((b'name', b'fin2'), b'beta', ([], )),
994
 
            ((b'ref', b'erence'), b'refdata', ([], ))])
995
 
        self.assertEqual(
996
 
            {(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
997
 
                (index, (b'ref', b'erence'), b'refdata', ((), ))},
998
 
            set(index.iter_entries_prefix(
999
 
                [(b'name', b'fin1'), (b'ref', b'erence')])))
1000
 
        self.assertEqual(
1001
 
            {(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
1002
 
                (index, (b'name', b'fin2'), b'beta', ((), ))},
1003
 
            set(index.iter_entries_prefix([(b'name', None)])))
 
942
            (('name', 'fin1'), 'data', ([('ref', 'erence')], )),
 
943
            (('name', 'fin2'), 'beta', ([], )),
 
944
            (('ref', 'erence'), 'refdata', ([], ))])
 
945
        self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
946
            (index, ('ref', 'erence'), 'refdata', ((), ))]),
 
947
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
 
948
        self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
949
            (index, ('name', 'fin2'), 'beta', ((), ))]),
 
950
            set(index.iter_entries_prefix([('name', None)])))
1004
951
 
1005
952
    # XXX: external_references tests are duplicated in test_index.  We
1006
953
    # probably should have per_graph_index tests...
1010
957
 
1011
958
    def test_external_references_no_results(self):
1012
959
        index = self.make_index(ref_lists=1, nodes=[
1013
 
            ((b'key',), b'value', ([],))])
 
960
            (('key',), 'value', ([],))])
1014
961
        self.assertEqual(set(), index.external_references(0))
1015
962
 
1016
963
    def test_external_references_missing_ref(self):
1017
 
        missing_key = (b'missing',)
 
964
        missing_key = ('missing',)
1018
965
        index = self.make_index(ref_lists=1, nodes=[
1019
 
            ((b'key',), b'value', ([missing_key],))])
1020
 
        self.assertEqual({missing_key}, index.external_references(0))
 
966
            (('key',), 'value', ([missing_key],))])
 
967
        self.assertEqual(set([missing_key]), index.external_references(0))
1021
968
 
1022
969
    def test_external_references_multiple_ref_lists(self):
1023
 
        missing_key = (b'missing',)
 
970
        missing_key = ('missing',)
1024
971
        index = self.make_index(ref_lists=2, nodes=[
1025
 
            ((b'key',), b'value', ([], [missing_key]))])
 
972
            (('key',), 'value', ([], [missing_key]))])
1026
973
        self.assertEqual(set([]), index.external_references(0))
1027
 
        self.assertEqual({missing_key}, index.external_references(1))
 
974
        self.assertEqual(set([missing_key]), index.external_references(1))
1028
975
 
1029
976
    def test_external_references_two_records(self):
1030
977
        index = self.make_index(ref_lists=1, nodes=[
1031
 
            ((b'key-1',), b'value', ([(b'key-2',)],)),
1032
 
            ((b'key-2',), b'value', ([],)),
 
978
            (('key-1',), 'value', ([('key-2',)],)),
 
979
            (('key-2',), 'value', ([],)),
1033
980
            ])
1034
981
        self.assertEqual(set([]), index.external_references(0))
1035
982
 
1036
 
    def test__find_ancestors_one_page(self):
1037
 
        key1 = (b'key-1',)
1038
 
        key2 = (b'key-2',)
1039
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1040
 
            (key1, b'value', ([key2],)),
1041
 
            (key2, b'value', ([],)),
1042
 
            ])
1043
 
        parent_map = {}
1044
 
        missing_keys = set()
1045
 
        search_keys = index._find_ancestors(
1046
 
            [key1], 0, parent_map, missing_keys)
1047
 
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
1048
 
        self.assertEqual(set(), missing_keys)
1049
 
        self.assertEqual(set(), search_keys)
1050
 
 
1051
 
    def test__find_ancestors_one_page_w_missing(self):
1052
 
        key1 = (b'key-1',)
1053
 
        key2 = (b'key-2',)
1054
 
        key3 = (b'key-3',)
1055
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1056
 
            (key1, b'value', ([key2],)),
1057
 
            (key2, b'value', ([],)),
1058
 
            ])
1059
 
        parent_map = {}
1060
 
        missing_keys = set()
1061
 
        search_keys = index._find_ancestors([key2, key3], 0, parent_map,
1062
 
                                            missing_keys)
1063
 
        self.assertEqual({key2: ()}, parent_map)
1064
 
        # we know that key3 is missing because we read the page that it would
1065
 
        # otherwise be on
1066
 
        self.assertEqual({key3}, missing_keys)
1067
 
        self.assertEqual(set(), search_keys)
1068
 
 
1069
 
    def test__find_ancestors_one_parent_missing(self):
1070
 
        key1 = (b'key-1',)
1071
 
        key2 = (b'key-2',)
1072
 
        key3 = (b'key-3',)
1073
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1074
 
            (key1, b'value', ([key2],)),
1075
 
            (key2, b'value', ([key3],)),
1076
 
            ])
1077
 
        parent_map = {}
1078
 
        missing_keys = set()
1079
 
        search_keys = index._find_ancestors([key1], 0, parent_map,
1080
 
                                            missing_keys)
1081
 
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1082
 
        self.assertEqual(set(), missing_keys)
1083
 
        # all we know is that key3 wasn't present on the page we were reading
1084
 
        # but if you look, the last key is key2 which comes before key3, so we
1085
 
        # don't know whether key3 would land on this page or not.
1086
 
        self.assertEqual({key3}, search_keys)
1087
 
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
1088
 
                                            missing_keys)
1089
 
        # passing it back in, we are sure it is 'missing'
1090
 
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1091
 
        self.assertEqual({key3}, missing_keys)
1092
 
        self.assertEqual(set([]), search_keys)
1093
 
 
1094
 
    def test__find_ancestors_dont_search_known(self):
1095
 
        key1 = (b'key-1',)
1096
 
        key2 = (b'key-2',)
1097
 
        key3 = (b'key-3',)
1098
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1099
 
            (key1, b'value', ([key2],)),
1100
 
            (key2, b'value', ([key3],)),
1101
 
            (key3, b'value', ([],)),
1102
 
            ])
1103
 
        # We already know about key2, so we won't try to search for key3
1104
 
        parent_map = {key2: (key3,)}
1105
 
        missing_keys = set()
1106
 
        search_keys = index._find_ancestors([key1], 0, parent_map,
1107
 
                                            missing_keys)
1108
 
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1109
 
        self.assertEqual(set(), missing_keys)
1110
 
        self.assertEqual(set(), search_keys)
1111
 
 
1112
 
    def test__find_ancestors_multiple_pages(self):
1113
 
        # We need to use enough keys that we actually cause a split
1114
 
        start_time = 1249671539
1115
 
        email = "joebob@example.com"
1116
 
        nodes = []
1117
 
        ref_lists = ((),)
1118
 
        rev_keys = []
1119
 
        for i in range(400):
1120
 
            rev_id = ('%s-%s-%s' % (email,
1121
 
                                    osutils.compact_date(start_time + i),
1122
 
                                    osutils.rand_chars(16))).encode('ascii')
1123
 
            rev_key = (rev_id,)
1124
 
            nodes.append((rev_key, b'value', ref_lists))
1125
 
            # We have a ref 'list' of length 1, with a list of parents, with 1
1126
 
            # parent which is a key
1127
 
            ref_lists = ((rev_key,),)
1128
 
            rev_keys.append(rev_key)
1129
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=nodes)
1130
 
        self.assertEqual(400, index.key_count())
1131
 
        self.assertEqual(3, len(index._row_offsets))
1132
 
        nodes = dict(index._read_nodes([1, 2]))
1133
 
        l1 = nodes[1]
1134
 
        l2 = nodes[2]
1135
 
        min_l2_key = l2.min_key
1136
 
        max_l1_key = l1.max_key
1137
 
        self.assertTrue(max_l1_key < min_l2_key)
1138
 
        parents_min_l2_key = l2[min_l2_key][1][0]
1139
 
        self.assertEqual((l1.max_key,), parents_min_l2_key)
1140
 
        # Now, whatever key we select that would fall on the second page,
1141
 
        # should give us all the parents until the page break
1142
 
        key_idx = rev_keys.index(min_l2_key)
1143
 
        next_key = rev_keys[key_idx + 1]
1144
 
        # So now when we get the parent map, we should get the key we are
1145
 
        # looking for, min_l2_key, and then a reference to go look for the
1146
 
        # parent of that key
1147
 
        parent_map = {}
1148
 
        missing_keys = set()
1149
 
        search_keys = index._find_ancestors([next_key], 0, parent_map,
1150
 
                                            missing_keys)
1151
 
        self.assertEqual([min_l2_key, next_key], sorted(parent_map))
1152
 
        self.assertEqual(set(), missing_keys)
1153
 
        self.assertEqual({max_l1_key}, search_keys)
1154
 
        parent_map = {}
1155
 
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
1156
 
                                            missing_keys)
1157
 
        self.assertEqual(l1.all_keys(), sorted(parent_map))
1158
 
        self.assertEqual(set(), missing_keys)
1159
 
        self.assertEqual(set(), search_keys)
1160
 
 
1161
 
    def test__find_ancestors_empty_index(self):
1162
 
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[])
1163
 
        parent_map = {}
1164
 
        missing_keys = set()
1165
 
        search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
1166
 
                                            missing_keys)
1167
 
        self.assertEqual(set(), search_keys)
1168
 
        self.assertEqual({}, parent_map)
1169
 
        self.assertEqual({('one',), ('two',)}, missing_keys)
1170
 
 
1171
 
    def test_supports_unlimited_cache(self):
1172
 
        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)
1173
 
        # We need enough nodes to cause a page split (so we have both an
1174
 
        # internal node and a couple leaf nodes. 500 seems to be enough.)
1175
 
        nodes = self.make_nodes(500, 1, 0)
1176
 
        for node in nodes:
1177
 
            builder.add_node(*node)
1178
 
        stream = builder.finish()
1179
 
        trans = self.get_transport()
1180
 
        size = trans.put_file('index', stream)
1181
 
        index = btree_index.BTreeGraphIndex(trans, 'index', size)
1182
 
        self.assertEqual(500, index.key_count())
1183
 
        # We have an internal node
1184
 
        self.assertEqual(2, len(index._row_lengths))
1185
 
        # We have at least 2 leaf nodes
1186
 
        self.assertTrue(index._row_lengths[-1] >= 2)
1187
 
        self.assertIsInstance(index._leaf_node_cache, lru_cache.LRUCache)
1188
 
        self.assertEqual(btree_index._NODE_CACHE_SIZE,
1189
 
                         index._leaf_node_cache._max_cache)
1190
 
        self.assertIsInstance(index._internal_node_cache, fifo_cache.FIFOCache)
1191
 
        self.assertEqual(100, index._internal_node_cache._max_cache)
1192
 
        # No change if unlimited_cache=False is passed
1193
 
        index = btree_index.BTreeGraphIndex(trans, 'index', size,
1194
 
                                            unlimited_cache=False)
1195
 
        self.assertIsInstance(index._leaf_node_cache, lru_cache.LRUCache)
1196
 
        self.assertEqual(btree_index._NODE_CACHE_SIZE,
1197
 
                         index._leaf_node_cache._max_cache)
1198
 
        self.assertIsInstance(index._internal_node_cache, fifo_cache.FIFOCache)
1199
 
        self.assertEqual(100, index._internal_node_cache._max_cache)
1200
 
        index = btree_index.BTreeGraphIndex(trans, 'index', size,
1201
 
                                            unlimited_cache=True)
1202
 
        self.assertIsInstance(index._leaf_node_cache, dict)
1203
 
        self.assertIs(type(index._internal_node_cache), dict)
1204
 
        # Exercise the lookup code
1205
 
        entries = set(index.iter_entries([n[0] for n in nodes]))
1206
 
        self.assertEqual(500, len(entries))
1207
 
 
1208
983
 
1209
984
class TestBTreeNodes(BTreeTestCase):
1210
985
 
1211
 
    scenarios = btreeparser_scenarios()
 
986
    def restore_parser(self):
 
987
        btree_index._btree_serializer = self.saved_parser
1212
988
 
1213
989
    def setUp(self):
1214
 
        super(TestBTreeNodes, self).setUp()
1215
 
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
 
990
        BTreeTestCase.setUp(self)
 
991
        self.saved_parser = btree_index._btree_serializer
 
992
        self.addCleanup(self.restore_parser)
 
993
        btree_index._btree_serializer = self.parse_btree
1216
994
 
1217
995
    def test_LeafNode_1_0(self):
1218
 
        node_bytes = (b"type=leaf\n"
1219
 
                      b"0000000000000000000000000000000000000000\x00\x00value:0\n"
1220
 
                      b"1111111111111111111111111111111111111111\x00\x00value:1\n"
1221
 
                      b"2222222222222222222222222222222222222222\x00\x00value:2\n"
1222
 
                      b"3333333333333333333333333333333333333333\x00\x00value:3\n"
1223
 
                      b"4444444444444444444444444444444444444444\x00\x00value:4\n")
 
996
        node_bytes = ("type=leaf\n"
 
997
            "0000000000000000000000000000000000000000\x00\x00value:0\n"
 
998
            "1111111111111111111111111111111111111111\x00\x00value:1\n"
 
999
            "2222222222222222222222222222222222222222\x00\x00value:2\n"
 
1000
            "3333333333333333333333333333333333333333\x00\x00value:3\n"
 
1001
            "4444444444444444444444444444444444444444\x00\x00value:4\n")
1224
1002
        node = btree_index._LeafNode(node_bytes, 1, 0)
1225
1003
        # We do direct access, or don't care about order, to leaf nodes most of
1226
1004
        # the time, so a dict is useful:
1227
1005
        self.assertEqual({
1228
 
            (b"0000000000000000000000000000000000000000",): (b"value:0", ()),
1229
 
            (b"1111111111111111111111111111111111111111",): (b"value:1", ()),
1230
 
            (b"2222222222222222222222222222222222222222",): (b"value:2", ()),
1231
 
            (b"3333333333333333333333333333333333333333",): (b"value:3", ()),
1232
 
            (b"4444444444444444444444444444444444444444",): (b"value:4", ()),
1233
 
            }, dict(node.all_items()))
 
1006
            ("0000000000000000000000000000000000000000",): ("value:0", ()),
 
1007
            ("1111111111111111111111111111111111111111",): ("value:1", ()),
 
1008
            ("2222222222222222222222222222222222222222",): ("value:2", ()),
 
1009
            ("3333333333333333333333333333333333333333",): ("value:3", ()),
 
1010
            ("4444444444444444444444444444444444444444",): ("value:4", ()),
 
1011
            }, node.keys)
1234
1012
 
1235
1013
    def test_LeafNode_2_2(self):
1236
 
        node_bytes = (b"type=leaf\n"
1237
 
                      b"00\x0000\x00\t00\x00ref00\x00value:0\n"
1238
 
                      b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
1239
 
                      b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
1240
 
                      b"11\x0044\x00\t11\x00ref00\x00value:4\n"
1241
 
                      b""
1242
 
                      )
 
1014
        node_bytes = ("type=leaf\n"
 
1015
            "00\x0000\x00\t00\x00ref00\x00value:0\n"
 
1016
            "00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
 
1017
            "11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
 
1018
            "11\x0044\x00\t11\x00ref00\x00value:4\n"
 
1019
            ""
 
1020
            )
1243
1021
        node = btree_index._LeafNode(node_bytes, 2, 2)
1244
1022
        # We do direct access, or don't care about order, to leaf nodes most of
1245
1023
        # the time, so a dict is useful:
1246
1024
        self.assertEqual({
1247
 
            (b'00', b'00'): (b'value:0', ((), ((b'00', b'ref00'),))),
1248
 
            (b'00', b'11'): (b'value:1', (((b'00', b'ref00'),),
1249
 
                                          ((b'00', b'ref00'), (b'01', b'ref01')))),
1250
 
            (b'11', b'33'): (b'value:3', (((b'11', b'ref22'),),
1251
 
                                          ((b'11', b'ref22'), (b'11', b'ref22')))),
1252
 
            (b'11', b'44'): (b'value:4', ((), ((b'11', b'ref00'),)))
1253
 
            }, dict(node.all_items()))
 
1025
            ('00', '00'): ('value:0', ((), (('00', 'ref00'),))),
 
1026
            ('00', '11'): ('value:1',
 
1027
                ((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01')))),
 
1028
            ('11', '33'): ('value:3',
 
1029
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
 
1030
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
 
1031
            }, node.keys)
1254
1032
 
1255
1033
    def test_InternalNode_1(self):
1256
 
        node_bytes = (b"type=internal\n"
1257
 
                      b"offset=1\n"
1258
 
                      b"0000000000000000000000000000000000000000\n"
1259
 
                      b"1111111111111111111111111111111111111111\n"
1260
 
                      b"2222222222222222222222222222222222222222\n"
1261
 
                      b"3333333333333333333333333333333333333333\n"
1262
 
                      b"4444444444444444444444444444444444444444\n"
1263
 
                      )
 
1034
        node_bytes = ("type=internal\n"
 
1035
            "offset=1\n"
 
1036
            "0000000000000000000000000000000000000000\n"
 
1037
            "1111111111111111111111111111111111111111\n"
 
1038
            "2222222222222222222222222222222222222222\n"
 
1039
            "3333333333333333333333333333333333333333\n"
 
1040
            "4444444444444444444444444444444444444444\n"
 
1041
            )
1264
1042
        node = btree_index._InternalNode(node_bytes)
1265
1043
        # We want to bisect to find the right children from this node, so a
1266
1044
        # vector is most useful.
1267
1045
        self.assertEqual([
1268
 
            (b"0000000000000000000000000000000000000000",),
1269
 
            (b"1111111111111111111111111111111111111111",),
1270
 
            (b"2222222222222222222222222222222222222222",),
1271
 
            (b"3333333333333333333333333333333333333333",),
1272
 
            (b"4444444444444444444444444444444444444444",),
 
1046
            ("0000000000000000000000000000000000000000",),
 
1047
            ("1111111111111111111111111111111111111111",),
 
1048
            ("2222222222222222222222222222222222222222",),
 
1049
            ("3333333333333333333333333333333333333333",),
 
1050
            ("4444444444444444444444444444444444444444",),
1273
1051
            ], node.keys)
1274
1052
        self.assertEqual(1, node.offset)
1275
1053
 
1276
1054
    def test_LeafNode_2_2(self):
1277
 
        node_bytes = (b"type=leaf\n"
1278
 
                      b"00\x0000\x00\t00\x00ref00\x00value:0\n"
1279
 
                      b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
1280
 
                      b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
1281
 
                      b"11\x0044\x00\t11\x00ref00\x00value:4\n"
1282
 
                      b""
1283
 
                      )
 
1055
        node_bytes = ("type=leaf\n"
 
1056
            "00\x0000\x00\t00\x00ref00\x00value:0\n"
 
1057
            "00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
 
1058
            "11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
 
1059
            "11\x0044\x00\t11\x00ref00\x00value:4\n"
 
1060
            ""
 
1061
            )
1284
1062
        node = btree_index._LeafNode(node_bytes, 2, 2)
1285
1063
        # We do direct access, or don't care about order, to leaf nodes most of
1286
1064
        # the time, so a dict is useful:
1287
1065
        self.assertEqual({
1288
 
            (b'00', b'00'): (b'value:0', ((), ((b'00', b'ref00'),))),
1289
 
            (b'00', b'11'): (b'value:1', (((b'00', b'ref00'),),
1290
 
                                          ((b'00', b'ref00'), (b'01', b'ref01')))),
1291
 
            (b'11', b'33'): (b'value:3', (((b'11', b'ref22'),),
1292
 
                                          ((b'11', b'ref22'), (b'11', b'ref22')))),
1293
 
            (b'11', b'44'): (b'value:4', ((), ((b'11', b'ref00'),)))
1294
 
            }, dict(node.all_items()))
 
1066
            ('00', '00'): ('value:0', ((), (('00', 'ref00'),))),
 
1067
            ('00', '11'): ('value:1',
 
1068
                ((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01')))),
 
1069
            ('11', '33'): ('value:3',
 
1070
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
 
1071
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
 
1072
            }, node.keys)
1295
1073
 
1296
1074
    def assertFlattened(self, expected, key, value, refs):
1297
1075
        flat_key, flat_line = self.parse_btree._flatten_node(
1298
1076
            (None, key, value, refs), bool(refs))
1299
 
        self.assertEqual(b'\x00'.join(key), flat_key)
 
1077
        self.assertEqual('\x00'.join(key), flat_key)
1300
1078
        self.assertEqual(expected, flat_line)
1301
1079
 
1302
1080
    def test__flatten_node(self):
1303
 
        self.assertFlattened(b'key\0\0value\n', (b'key',), b'value', [])
1304
 
        self.assertFlattened(b'key\0tuple\0\0value str\n',
1305
 
                             (b'key', b'tuple'), b'value str', [])
1306
 
        self.assertFlattened(b'key\0tuple\0triple\0\0value str\n',
1307
 
                             (b'key', b'tuple', b'triple'), b'value str', [])
1308
 
        self.assertFlattened(b'k\0t\0s\0ref\0value str\n',
1309
 
                             (b'k', b't', b's'), b'value str', [[(b'ref',)]])
1310
 
        self.assertFlattened(b'key\0tuple\0ref\0key\0value str\n',
1311
 
                             (b'key', b'tuple'), b'value str', [[(b'ref', b'key')]])
1312
 
        self.assertFlattened(b"00\x0000\x00\t00\x00ref00\x00value:0\n",
1313
 
                             (b'00', b'00'), b'value:0', ((), ((b'00', b'ref00'),)))
1314
 
        self.assertFlattened(
1315
 
            b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n",
1316
 
            (b'00', b'11'), b'value:1',
1317
 
            (((b'00', b'ref00'),), ((b'00', b'ref00'), (b'01', b'ref01'))))
1318
 
        self.assertFlattened(
1319
 
            b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n",
1320
 
            (b'11', b'33'), b'value:3',
1321
 
            (((b'11', b'ref22'),), ((b'11', b'ref22'), (b'11', b'ref22'))))
1322
 
        self.assertFlattened(
1323
 
            b"11\x0044\x00\t11\x00ref00\x00value:4\n",
1324
 
            (b'11', b'44'), b'value:4', ((), ((b'11', b'ref00'),)))
 
1081
        self.assertFlattened('key\0\0value\n', ('key',), 'value', [])
 
1082
        self.assertFlattened('key\0tuple\0\0value str\n',
 
1083
                             ('key', 'tuple'), 'value str', [])
 
1084
        self.assertFlattened('key\0tuple\0triple\0\0value str\n',
 
1085
                             ('key', 'tuple', 'triple'), 'value str', [])
 
1086
        self.assertFlattened('k\0t\0s\0ref\0value str\n',
 
1087
                             ('k', 't', 's'), 'value str', [[('ref',)]])
 
1088
        self.assertFlattened('key\0tuple\0ref\0key\0value str\n',
 
1089
                             ('key', 'tuple'), 'value str', [[('ref', 'key')]])
 
1090
        self.assertFlattened("00\x0000\x00\t00\x00ref00\x00value:0\n",
 
1091
            ('00', '00'), 'value:0', ((), (('00', 'ref00'),)))
 
1092
        self.assertFlattened(
 
1093
            "00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n",
 
1094
            ('00', '11'), 'value:1',
 
1095
                ((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01'))))
 
1096
        self.assertFlattened(
 
1097
            "11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n",
 
1098
            ('11', '33'), 'value:3',
 
1099
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22'))))
 
1100
        self.assertFlattened(
 
1101
            "11\x0044\x00\t11\x00ref00\x00value:4\n",
 
1102
            ('11', '44'), 'value:4', ((), (('11', 'ref00'),)))
1325
1103
 
1326
1104
 
1327
1105
class TestCompiledBtree(tests.TestCase):
1329
1107
    def test_exists(self):
1330
1108
        # This is just to let the user know if they don't have the feature
1331
1109
        # available
1332
 
        self.requireFeature(compiled_btreeparser_feature)
 
1110
        self.requireFeature(CompiledBtreeParserFeature)
1333
1111
 
1334
1112
 
1335
1113
class TestMultiBisectRight(tests.TestCase):
1337
1115
    def assertMultiBisectRight(self, offsets, search_keys, fixed_keys):
1338
1116
        self.assertEqual(offsets,
1339
1117
                         btree_index.BTreeGraphIndex._multi_bisect_right(
1340
 
                             search_keys, fixed_keys))
 
1118
                            search_keys, fixed_keys))
1341
1119
 
1342
1120
    def test_after(self):
1343
1121
        self.assertMultiBisectRight([(1, ['b'])], ['b'], ['a'])
1351
1129
 
1352
1130
    def test_exact(self):
1353
1131
        self.assertMultiBisectRight([(1, ['a'])], ['a'], ['a'])
1354
 
        self.assertMultiBisectRight(
1355
 
            [(1, ['a']), (2, ['b'])], ['a', 'b'], ['a', 'b'])
 
1132
        self.assertMultiBisectRight([(1, ['a']), (2, ['b'])], ['a', 'b'], ['a', 'b'])
1356
1133
        self.assertMultiBisectRight([(1, ['a']), (3, ['c'])],
1357
1134
                                    ['a', 'c'], ['a', 'b', 'c'])
1358
1135
 
1376
1153
        This doesn't actually create anything on disk, it just primes a
1377
1154
        BTreeGraphIndex with the recommended information.
1378
1155
        """
1379
 
        index = btree_index.BTreeGraphIndex(
1380
 
            transport.get_transport_from_url('memory:///'),
1381
 
            'test-index', size=size)
 
1156
        index = btree_index.BTreeGraphIndex(get_transport('memory:///'),
 
1157
                                            'test-index', size=size)
1382
1158
        if recommended_pages is not None:
1383
1159
            index._recommended_pages = recommended_pages
1384
1160
        return index
1398
1174
        index._key_count = key_count
1399
1175
        index._row_lengths = row_lengths
1400
1176
        index._compute_row_offsets()
1401
 
        index._root_node = btree_index._InternalNode(b'internal\noffset=0\n')
 
1177
        index._root_node = btree_index._InternalNode('internal\noffset=0\n')
1402
1178
        self.set_cached_offsets(index, cached_offsets)
1403
1179
 
1404
1180
    def make_100_node_index(self):
1405
 
        index = self.make_index(4096 * 100, 6)
 
1181
        index = self.make_index(4096*100, 6)
1406
1182
        # Consider we've already made a single request at the middle
1407
1183
        self.prepare_index(index, node_ref_lists=0, key_length=1,
1408
1184
                           key_count=1000, row_lengths=[1, 99],
1410
1186
        return index
1411
1187
 
1412
1188
    def make_1000_node_index(self):
1413
 
        index = self.make_index(4096 * 1000, 6)
 
1189
        index = self.make_index(4096*1000, 6)
1414
1190
        # Pretend we've already made a single request in the middle
1415
1191
        self.prepare_index(index, node_ref_lists=0, key_length=1,
1416
1192
                           key_count=90000, row_lengths=[1, 9, 990],
1438
1214
        self.assertNumPages(1, index, 4096)
1439
1215
        self.assertNumPages(2, index, 4097)
1440
1216
        self.assertNumPages(2, index, 8192)
1441
 
        self.assertNumPages(76, index, 4096 * 75 + 10)
 
1217
        self.assertNumPages(76, index, 4096*75 + 10)
1442
1218
 
1443
1219
    def test__find_layer_start_and_stop(self):
1444
1220
        index = self.make_1000_node_index()
1456
1232
        self.assertExpandOffsets([1, 4, 9], index, [1, 4, 9])
1457
1233
 
1458
1234
    def test_more_than_recommended(self):
1459
 
        index = self.make_index(4096 * 100, 2)
 
1235
        index = self.make_index(4096*100, 2)
1460
1236
        self.assertExpandOffsets([1, 10], index, [1, 10])
1461
1237
        self.assertExpandOffsets([1, 10, 20], index, [1, 10, 20])
1462
1238
 
1463
1239
    def test_read_all_from_root(self):
1464
 
        index = self.make_index(4096 * 10, 20)
1465
 
        self.assertExpandOffsets(list(range(10)), index, [0])
 
1240
        index = self.make_index(4096*10, 20)
 
1241
        self.assertExpandOffsets(range(10), index, [0])
1466
1242
 
1467
1243
    def test_read_all_when_cached(self):
1468
1244
        # We've read enough that we can grab all the rest in a single request
1469
 
        index = self.make_index(4096 * 10, 5)
 
1245
        index = self.make_index(4096*10, 5)
1470
1246
        self.prepare_index(index, node_ref_lists=0, key_length=1,
1471
1247
                           key_count=1000, row_lengths=[1, 9],
1472
1248
                           cached_offsets=[0, 1, 2, 5, 6])
1476
1252
        self.assertExpandOffsets([3, 4, 7, 8, 9], index, [9])
1477
1253
 
1478
1254
    def test_no_root_node(self):
1479
 
        index = self.make_index(4096 * 10, 5)
 
1255
        index = self.make_index(4096*10, 5)
1480
1256
        self.assertExpandOffsets([0], index, [0])
1481
1257
 
1482
1258
    def test_include_neighbors(self):
1492
1268
        # Requesting many nodes will expand all locations equally
1493
1269
        self.assertExpandOffsets([1, 2, 3, 80, 81, 82], index, [2, 81])
1494
1270
        self.assertExpandOffsets([1, 2, 3, 9, 10, 11, 80, 81, 82], index,
1495
 
                                 [2, 10, 81])
 
1271
                               [2, 10, 81])
1496
1272
 
1497
1273
    def test_stop_at_cached(self):
1498
1274
        index = self.make_100_node_index()