/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: Robert Collins
  • Date: 2010-05-06 23:41:35 UTC
  • mto: This revision was merged to the branch mainline in revision 5223.
  • Revision ID: robertc@robertcollins.net-20100506234135-yivbzczw1sejxnxc
Lock methods on ``Tree``, ``Branch`` and ``Repository`` are now
expected to return an object which can be used to unlock them. This reduces
duplicate code when using cleanups. The previous 'tokens's returned by
``Branch.lock_write`` and ``Repository.lock_write`` are now attributes
on the result of the lock_write. ``repository.RepositoryWriteLockResult``
and ``branch.BranchWriteLockResult`` document this. (Robert Collins)

``log._get_info_for_log_files`` now takes an add_cleanup callable.
(Robert Collins)

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