/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 breezy/tests/test_btree_index.py

  • Committer: Jelmer Vernooij
  • Date: 2020-04-05 19:11:34 UTC
  • mto: (7490.7.16 work)
  • mto: This revision was merged to the branch mainline in revision 7501.
  • Revision ID: jelmer@jelmer.uk-20200405191134-0aebh8ikiwygxma5
Populate the .gitignore file.

Show diffs side-by-side

added added

removed removed

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