/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: 2018-07-08 14:45:27 UTC
  • mto: This revision was merged to the branch mainline in revision 7036.
  • Revision ID: jelmer@jelmer.uk-20180708144527-codhlvdcdg9y0nji
Fix a bunch of merge tests.

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 + _pos_to_key(pos - 1, b"ref"))
90
96
                            else:
91
97
                                # serial of this ref in the ref list
92
 
                                refs[-1].append(prefix + ("ref" + str(ref_pos) * 40,))
 
98
                                refs[-1].append(prefix + _pos_to_key(ref_pos, b"ref"))
93
99
                        refs[-1] = tuple(refs[-1])
94
100
                    refs = tuple(refs)
95
101
                else:
102
108
        self.overrideAttr(btree_index, '_PAGE_SIZE')
103
109
        btree_index._PAGE_SIZE = 2048
104
110
 
 
111
    def assertEqualApproxCompressed(self, expected, actual, slop=6):
 
112
        """Check a count of compressed bytes is approximately as expected
 
113
 
 
114
        Relying on compressed length being stable even with fixed inputs is
 
115
        slightly bogus, but zlib is stable enough that this mostly works.
 
116
        """
 
117
        if not expected - slop < actual < expected + slop:
 
118
            self.fail("Expected around %d bytes compressed but got %d" %
 
119
                (expected, actual))
 
120
 
105
121
 
106
122
class TestBTreeBuilder(BTreeTestCase):
107
123
 
118
134
        content = temp_file.read()
119
135
        del temp_file
120
136
        self.assertEqual(
121
 
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=0\n"
122
 
            "row_lengths=\n",
 
137
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=0\n"
 
138
            b"row_lengths=\n",
123
139
            content)
124
140
 
125
141
    def test_empty_2_1(self):
129
145
        content = temp_file.read()
130
146
        del temp_file
131
147
        self.assertEqual(
132
 
            "B+Tree Graph Index 2\nnode_ref_lists=1\nkey_elements=2\nlen=0\n"
133
 
            "row_lengths=\n",
 
148
            b"B+Tree Graph Index 2\nnode_ref_lists=1\nkey_elements=2\nlen=0\n"
 
149
            b"row_lengths=\n",
134
150
            content)
135
151
 
136
152
    def test_root_leaf_1_0(self):
144
160
        del temp_file
145
161
        self.assertEqual(131, len(content))
146
162
        self.assertEqual(
147
 
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"
148
 
            "row_lengths=1\n",
 
163
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"
 
164
            b"row_lengths=1\n",
149
165
            content[:73])
150
166
        node_content = content[73:]
151
167
        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")
 
168
        expected_node = (b"type=leaf\n"
 
169
            b"0000000000000000000000000000000000000000\x00\x00value:0\n"
 
170
            b"1111111111111111111111111111111111111111\x00\x00value:1\n"
 
171
            b"2222222222222222222222222222222222222222\x00\x00value:2\n"
 
172
            b"3333333333333333333333333333333333333333\x00\x00value:3\n"
 
173
            b"4444444444444444444444444444444444444444\x00\x00value:4\n")
158
174
        self.assertEqual(expected_node, node_bytes)
159
175
 
160
176
    def test_root_leaf_2_2(self):
168
184
        del temp_file
169
185
        self.assertEqual(238, len(content))
170
186
        self.assertEqual(
171
 
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"
172
 
            "row_lengths=1\n",
 
187
            b"B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"
 
188
            b"row_lengths=1\n",
173
189
            content[:74])
174
190
        node_content = content[74:]
175
191
        node_bytes = zlib.decompress(node_content)
176
192
        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
 
            ""
 
193
            b"type=leaf\n"
 
194
            b"0000000000000000000000000000000000000000\x000000000000000000000000000000000000000000\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:0\n"
 
195
            b"0000000000000000000000000000000000000000\x001111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\r0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:1\n"
 
196
            b"0000000000000000000000000000000000000000\x002222222222222222222222222222222222222222\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:2\n"
 
197
            b"0000000000000000000000000000000000000000\x003333333333333333333333333333333333333333\x000000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\t0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\r0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\x00value:3\n"
 
198
            b"0000000000000000000000000000000000000000\x004444444444444444444444444444444444444444\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:4\n"
 
199
            b"1111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:0\n"
 
200
            b"1111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\r1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:1\n"
 
201
            b"1111111111111111111111111111111111111111\x002222222222222222222222222222222222222222\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:2\n"
 
202
            b"1111111111111111111111111111111111111111\x003333333333333333333333333333333333333333\x001111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\t1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\r1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\x00value:3\n"
 
203
            b"1111111111111111111111111111111111111111\x004444444444444444444444444444444444444444\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:4\n"
 
204
            b""
189
205
            )
190
206
        self.assertEqual(expected_node, node_bytes)
191
207
 
198
214
        temp_file = builder.finish()
199
215
        content = temp_file.read()
200
216
        del temp_file
201
 
        self.assertEqual(9283, len(content))
 
217
        self.assertEqualApproxCompressed(9283, len(content))
202
218
        self.assertEqual(
203
 
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
204
 
            "row_lengths=1,2\n",
 
219
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
 
220
            b"row_lengths=1,2\n",
205
221
            content[:77])
206
222
        root = content[77:4096]
207
223
        leaf1 = content[4096:8192]
208
224
        leaf2 = content[8192:]
209
225
        root_bytes = zlib.decompress(root)
210
226
        expected_root = (
211
 
            "type=internal\n"
212
 
            "offset=0\n"
213
 
            ) + ("307" * 40) + "\n"
 
227
            b"type=internal\n"
 
228
            b"offset=0\n"
 
229
            ) + (b"307" * 40) + b"\n"
214
230
        self.assertEqual(expected_root, root_bytes)
215
231
        # We already know serialisation works for leaves, check key selection:
216
232
        leaf1_bytes = zlib.decompress(leaf1)
217
233
        sorted_node_keys = sorted(node[0] for node in nodes)
218
234
        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))
 
235
        self.assertEqual(231, len(node))
 
236
        self.assertEqual(sorted_node_keys[:231], node.all_keys())
221
237
        leaf2_bytes = zlib.decompress(leaf2)
222
238
        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))
 
239
        self.assertEqual(400 - 231, len(node))
 
240
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
225
241
 
226
242
    def test_last_page_rounded_1_layer(self):
227
243
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
232
248
        temp_file = builder.finish()
233
249
        content = temp_file.read()
234
250
        del temp_file
235
 
        self.assertEqual(155, len(content))
 
251
        self.assertEqualApproxCompressed(155, len(content))
236
252
        self.assertEqual(
237
 
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
238
 
            "row_lengths=1\n",
 
253
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
 
254
            b"row_lengths=1\n",
239
255
            content[:74])
240
256
        # Check thelast page is well formed
241
257
        leaf2 = content[74:]
242
258
        leaf2_bytes = zlib.decompress(leaf2)
243
259
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
244
 
        self.assertEqual(10, len(node.keys))
 
260
        self.assertEqual(10, len(node))
245
261
        sorted_node_keys = sorted(node[0] for node in nodes)
246
 
        self.assertEqual(sorted_node_keys, sorted(node.keys))
 
262
        self.assertEqual(sorted_node_keys, node.all_keys())
247
263
 
248
264
    def test_last_page_not_rounded_2_layer(self):
249
265
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
254
270
        temp_file = builder.finish()
255
271
        content = temp_file.read()
256
272
        del temp_file
257
 
        self.assertEqual(9283, len(content))
 
273
        self.assertEqualApproxCompressed(9283, len(content))
258
274
        self.assertEqual(
259
 
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
260
 
            "row_lengths=1,2\n",
 
275
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
 
276
            b"row_lengths=1,2\n",
261
277
            content[:77])
262
278
        # Check the last page is well formed
263
279
        leaf2 = content[8192:]
264
280
        leaf2_bytes = zlib.decompress(leaf2)
265
281
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
266
 
        self.assertEqual(400 - 231, len(node.keys))
 
282
        self.assertEqual(400 - 231, len(node))
267
283
        sorted_node_keys = sorted(node[0] for node in nodes)
268
 
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
 
284
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
269
285
 
270
286
    def test_three_level_tree_details(self):
271
287
        # The left most pointer in the second internal node in a row should
280
296
 
281
297
        for node in nodes:
282
298
            builder.add_node(*node)
283
 
        transport = get_transport('trace+' + self.get_url(''))
284
 
        size = transport.put_file('index', self.time(builder.finish))
 
299
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
300
        size = t.put_file('index', self.time(builder.finish))
285
301
        del builder
286
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
302
        index = btree_index.BTreeGraphIndex(t, 'index', size)
287
303
        # Seed the metadata, we're using internal calls now.
288
304
        index.key_count()
289
305
        self.assertEqual(3, len(index._row_lengths),
302
318
        # in the second node it points at
303
319
        pos = index._row_offsets[2] + internal_node2.offset + 1
304
320
        leaf = index._get_leaf_nodes([pos])[pos]
305
 
        self.assertTrue(internal_node2.keys[0] in leaf.keys)
 
321
        self.assertTrue(internal_node2.keys[0] in leaf)
306
322
 
307
323
    def test_2_leaves_2_2(self):
308
324
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
313
329
        temp_file = builder.finish()
314
330
        content = temp_file.read()
315
331
        del temp_file
316
 
        self.assertEqual(12643, len(content))
 
332
        self.assertEqualApproxCompressed(12643, len(content))
317
333
        self.assertEqual(
318
 
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
319
 
            "row_lengths=1,3\n",
 
334
            b"B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
 
335
            b"row_lengths=1,3\n",
320
336
            content[:77])
321
337
        root = content[77:4096]
322
338
        leaf1 = content[4096:8192]
324
340
        leaf3 = content[12288:]
325
341
        root_bytes = zlib.decompress(root)
326
342
        expected_root = (
327
 
            "type=internal\n"
328
 
            "offset=0\n"
329
 
            + ("0" * 40) + "\x00" + ("91" * 40) + "\n"
330
 
            + ("1" * 40) + "\x00" + ("81" * 40) + "\n"
 
343
            b"type=internal\n"
 
344
            b"offset=0\n"
 
345
            + (b"0" * 40) + b"\x00" + (b"91" * 40) + b"\n"
 
346
            + (b"1" * 40) + b"\x00" + (b"81" * 40) + b"\n"
331
347
            )
332
348
        self.assertEqual(expected_root, root_bytes)
333
349
        # We assume the other leaf nodes have been written correctly - layering
391
407
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
392
408
            list(builder.iter_all_entries()))
393
409
        # Two nodes - one memory one disk
394
 
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
410
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
395
411
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
396
412
        self.assertEqual(13, builder.key_count())
397
 
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
413
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
398
414
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
399
415
        builder.add_node(*nodes[13])
400
416
        self.assertEqual(3, len(builder._backing_indices))
409
425
        self.assertEqual(None, builder._backing_indices[2])
410
426
        self.assertEqual(16, builder._backing_indices[3].key_count())
411
427
        # 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)
 
428
        t = self.get_transport('')
 
429
        size = t.put_file('index', builder.finish())
 
430
        index = btree_index.BTreeGraphIndex(t, 'index', size)
415
431
        nodes = list(index.iter_all_entries())
416
432
        self.assertEqual(sorted(nodes), nodes)
417
433
        self.assertEqual(16, len(nodes))
465
481
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
466
482
            list(builder.iter_all_entries()))
467
483
        # Two nodes - one memory one disk
468
 
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
484
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
469
485
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
470
486
        self.assertEqual(13, builder.key_count())
471
 
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
487
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
472
488
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
473
489
        builder.add_node(*nodes[13])
474
490
        builder.add_node(*nodes[14])
565
581
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
566
582
            list(builder.iter_all_entries()))
567
583
        # Two nodes - one memory one disk
568
 
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
584
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
569
585
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
570
586
        self.assertEqual(13, builder.key_count())
571
 
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
587
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
572
588
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
573
589
        builder.add_node(*nodes[13])
574
590
        self.assertEqual(3, len(builder._backing_indices))
596
612
        builder.add_node(*nodes[0])
597
613
        builder.add_node(*nodes[1])
598
614
        builder.add_node(*nodes[0])
599
 
        self.assertRaises(errors.BadIndexDuplicateKey, builder.finish)
 
615
        self.assertRaises(_mod_index.BadIndexDuplicateKey, builder.finish)
600
616
 
601
617
 
602
618
class TestBTreeIndex(BTreeTestCase):
607
623
        for key, value, references in nodes:
608
624
            builder.add_node(key, value, references)
609
625
        stream = builder.finish()
610
 
        trans = get_transport('trace+' + self.get_url())
 
626
        trans = transport.get_transport_from_url('trace+' + self.get_url())
611
627
        size = trans.put_file('index', stream)
612
628
        return btree_index.BTreeGraphIndex(trans, 'index', size)
613
629
 
622
638
        content = temp_file.read()
623
639
        del temp_file
624
640
        size = len(content)
625
 
        transport.put_bytes('index', (' '*offset)+content)
 
641
        transport.put_bytes('index', (b' '*offset)+content)
626
642
        return btree_index.BTreeGraphIndex(transport, 'index', size=size,
627
643
                                           offset=offset)
628
644
 
632
648
        self.assertEqual(1, len(list(index.iter_entries([nodes[30][0]]))))
633
649
        self.assertEqual([1, 4], index._row_lengths)
634
650
        self.assertIsNot(None, index._root_node)
635
 
        internal_node_pre_clear = index._internal_node_cache.keys()
 
651
        internal_node_pre_clear = set(index._internal_node_cache)
636
652
        self.assertTrue(len(index._leaf_node_cache) > 0)
637
653
        index.clear_cache()
638
654
        # We don't touch _root_node or _internal_node_cache, both should be
644
660
        #       becuase without a 3-level index, we don't have any internal
645
661
        #       nodes cached.
646
662
        self.assertEqual(internal_node_pre_clear,
647
 
                         index._internal_node_cache.keys())
 
663
                         set(index._internal_node_cache))
648
664
        self.assertEqual(0, len(index._leaf_node_cache))
649
665
 
650
666
    def test_trivial_constructor(self):
651
 
        transport = get_transport('trace+' + self.get_url(''))
652
 
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
 
667
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
668
        index = btree_index.BTreeGraphIndex(t, 'index', None)
653
669
        # Checks the page size at load, but that isn't logged yet.
654
 
        self.assertEqual([], transport._activity)
 
670
        self.assertEqual([], t._activity)
655
671
 
656
672
    def test_with_size_constructor(self):
657
 
        transport = get_transport('trace+' + self.get_url(''))
658
 
        index = btree_index.BTreeGraphIndex(transport, 'index', 1)
 
673
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
674
        index = btree_index.BTreeGraphIndex(t, 'index', 1)
659
675
        # Checks the page size at load, but that isn't logged yet.
660
 
        self.assertEqual([], transport._activity)
 
676
        self.assertEqual([], t._activity)
661
677
 
662
678
    def test_empty_key_count_no_size(self):
663
679
        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)
 
680
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
681
        t.put_file('index', builder.finish())
 
682
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
683
        del t._activity[:]
 
684
        self.assertEqual([], t._activity)
669
685
        self.assertEqual(0, index.key_count())
670
686
        # The entire index should have been requested (as we generally have the
671
687
        # size available, and doing many small readvs is inappropriate).
672
688
        # We can't tell how much was actually read here, but - check the code.
673
 
        self.assertEqual([('get', 'index')], transport._activity)
 
689
        self.assertEqual([('get', 'index')], t._activity)
674
690
 
675
691
    def test_empty_key_count(self):
676
692
        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())
 
693
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
694
        size = t.put_file('index', builder.finish())
679
695
        self.assertEqual(72, size)
680
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
681
 
        del transport._activity[:]
682
 
        self.assertEqual([], transport._activity)
 
696
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
697
        del t._activity[:]
 
698
        self.assertEqual([], t._activity)
683
699
        self.assertEqual(0, index.key_count())
684
700
        # The entire index should have been read, as 4K > size
685
701
        self.assertEqual([('readv', 'index', [(0, 72)], False, None)],
686
 
            transport._activity)
 
702
                         t._activity)
687
703
 
688
704
    def test_non_empty_key_count_2_2(self):
689
705
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
690
706
        nodes = self.make_nodes(35, 2, 2)
691
707
        for node in nodes:
692
708
            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)
 
709
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
710
        size = t.put_file('index', builder.finish())
 
711
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
712
        del t._activity[:]
 
713
        self.assertEqual([], t._activity)
698
714
        self.assertEqual(70, index.key_count())
699
715
        # The entire index should have been read, as it is one page long.
700
716
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
701
 
            transport._activity)
702
 
        self.assertEqual(1173, size)
 
717
            t._activity)
 
718
        self.assertEqualApproxCompressed(1173, size)
703
719
 
704
720
    def test_with_offset_no_size(self):
705
721
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
721
737
        self.assertEqual(200, index.key_count())
722
738
 
723
739
    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())
 
740
        self.make_index(nodes=[((b'key',), b'value', ())])
 
741
        trans = transport.get_transport_from_url('trace+' + self.get_url())
726
742
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
727
743
        del trans._activity[:]
728
744
        nodes = dict(index._read_nodes([0]))
729
 
        self.assertEqual([0], nodes.keys())
 
745
        self.assertEqual({0}, set(nodes))
730
746
        node = nodes[0]
731
 
        self.assertEqual([('key',)], node.keys.keys())
 
747
        self.assertEqual([(b'key',)], node.all_keys())
732
748
        self.assertEqual([('get', 'index')], trans._activity)
733
749
 
734
750
    def test__read_nodes_no_size_multiple_pages(self):
736
752
        index.key_count()
737
753
        num_pages = index._row_offsets[-1]
738
754
        # Reopen with a traced transport and no size
739
 
        trans = get_transport('trace+' + self.get_url())
 
755
        trans = transport.get_transport_from_url('trace+' + self.get_url())
740
756
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
741
757
        del trans._activity[:]
742
758
        nodes = dict(index._read_nodes([0]))
743
 
        self.assertEqual(range(num_pages), nodes.keys())
 
759
        self.assertEqual(list(range(num_pages)), sorted(nodes))
744
760
 
745
761
    def test_2_levels_key_count_2_2(self):
746
762
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
747
763
        nodes = self.make_nodes(160, 2, 2)
748
764
        for node in nodes:
749
765
            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)
 
766
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
767
        size = t.put_file('index', builder.finish())
 
768
        self.assertEqualApproxCompressed(17692, size)
 
769
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
770
        del t._activity[:]
 
771
        self.assertEqual([], t._activity)
756
772
        self.assertEqual(320, index.key_count())
757
773
        # The entire index should not have been read.
758
774
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None)],
759
 
            transport._activity)
 
775
                         t._activity)
760
776
 
761
777
    def test_validate_one_page(self):
762
778
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
763
779
        nodes = self.make_nodes(45, 2, 2)
764
780
        for node in nodes:
765
781
            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)
 
782
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
783
        size = t.put_file('index', builder.finish())
 
784
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
785
        del t._activity[:]
 
786
        self.assertEqual([], t._activity)
771
787
        index.validate()
772
788
        # The entire index should have been read linearly.
773
789
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
774
 
            transport._activity)
775
 
        self.assertEqual(1488, size)
 
790
                         t._activity)
 
791
        self.assertEqualApproxCompressed(1488, size)
776
792
 
777
793
    def test_validate_two_pages(self):
778
794
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
779
795
        nodes = self.make_nodes(80, 2, 2)
780
796
        for node in nodes:
781
797
            builder.add_node(*node)
782
 
        transport = get_transport('trace+' + self.get_url(''))
783
 
        size = transport.put_file('index', builder.finish())
 
798
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
799
        size = t.put_file('index', builder.finish())
784
800
        # 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)
 
801
        self.assertEqualApproxCompressed(9339, size)
 
802
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
803
        del t._activity[:]
 
804
        self.assertEqual([], t._activity)
789
805
        index.validate()
 
806
        rem = size - 8192 # Number of remaining bytes after second block
790
807
        # 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)
 
808
        self.assertEqual(
 
809
            [('readv', 'index', [(0, 4096)], False, None),
 
810
             ('readv', 'index', [(4096, 4096), (8192, rem)], False, None)],
 
811
            t._activity)
794
812
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
795
813
        # node and make validate find them.
796
814
 
797
815
    def test_eq_ne(self):
798
816
        # 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))
 
817
        t1 = transport.get_transport_from_url('trace+' + self.get_url(''))
 
818
        t2 = self.get_transport()
 
819
        self.assertTrue(
 
820
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
 
821
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
822
        self.assertTrue(
 
823
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
824
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
825
        self.assertFalse(
 
826
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
827
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
828
        self.assertFalse(
 
829
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) ==
 
830
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
831
        self.assertFalse(
 
832
            btree_index.BTreeGraphIndex(t1, 'index', 10) ==
 
833
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
834
        self.assertFalse(
 
835
            btree_index.BTreeGraphIndex(t1, 'index', None) !=
 
836
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
837
        self.assertFalse(
 
838
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
839
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
840
        self.assertTrue(
 
841
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
842
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
843
        self.assertTrue(
 
844
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) !=
 
845
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
846
        self.assertTrue(
 
847
            btree_index.BTreeGraphIndex(t1, 'index', 10) !=
 
848
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
849
 
 
850
    def test_key_too_big(self):
 
851
        # the size that matters here is the _compressed_ size of the key, so we can't
 
852
        # do a simple character repeat.
 
853
        bigKey = b''.join(b'%d' % n for n in range(btree_index._PAGE_SIZE))
 
854
        self.assertRaises(_mod_index.BadIndexKey,
 
855
                          self.make_index,
 
856
                          nodes=[((bigKey,), b'value', ())])
831
857
 
832
858
    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')],
 
859
        self.make_index(nodes=[((b'key',), b'value', ())])
 
860
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
861
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
862
        del t._activity[:]
 
863
        self.assertEqual([((b'key',), b'value')],
838
864
                         [x[1:] for x in index.iter_all_entries()])
839
 
        self.assertEqual([('get', 'index')], trans._activity)
 
865
        self.assertEqual([('get', 'index')], t._activity)
840
866
 
841
867
    def test_iter_all_entries_reads(self):
842
868
        # iterating all entries reads the header, then does a linear
848
874
        nodes = self.make_nodes(10000, 2, 2)
849
875
        for node in nodes:
850
876
            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')
 
877
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
878
        size = t.put_file('index', builder.finish())
855
879
        page_size = btree_index._PAGE_SIZE
856
880
        del builder
857
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
858
 
        del transport._activity[:]
859
 
        self.assertEqual([], transport._activity)
 
881
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
882
        del t._activity[:]
 
883
        self.assertEqual([], t._activity)
860
884
        found_nodes = self.time(list, index.iter_all_entries())
861
885
        bare_nodes = []
862
886
        for node in found_nodes:
873
897
        # The entire index should have been read
874
898
        total_pages = sum(index._row_lengths)
875
899
        self.assertEqual(total_pages, index._row_offsets[-1])
876
 
        self.assertEqual(1303220, size)
 
900
        self.assertEqualApproxCompressed(1303220, size)
877
901
        # The start of the leaves
878
902
        first_byte = index._row_offsets[-2] * page_size
879
903
        readv_request = []
880
904
        for offset in range(first_byte, size, page_size):
881
905
            readv_request.append((offset, page_size))
882
906
        # The last page is truncated
883
 
        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
 
907
        readv_request[-1] = (readv_request[-1][0], size % page_size)
884
908
        expected = [('readv', 'index', [(0, page_size)], False, None),
885
909
             ('readv',  'index', readv_request, False, None)]
886
 
        if expected != transport._activity:
 
910
        if expected != t._activity:
887
911
            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',)])))
 
912
                                 pprint.pformat(t._activity))
897
913
 
898
914
    def test_iter_entries_references_2_refs_resolved(self):
899
915
        # iterating some entries reads just the pages needed. For now, to
903
919
        nodes = self.make_nodes(160, 2, 2)
904
920
        for node in nodes:
905
921
            builder.add_node(*node)
906
 
        transport = get_transport('trace+' + self.get_url(''))
907
 
        size = transport.put_file('index', builder.finish())
 
922
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
923
        size = t.put_file('index', builder.finish())
908
924
        del builder
909
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
910
 
        del transport._activity[:]
911
 
        self.assertEqual([], transport._activity)
 
925
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
926
        del t._activity[:]
 
927
        self.assertEqual([], t._activity)
912
928
        # search for one key
913
929
        found_nodes = list(index.iter_entries([nodes[30][0]]))
914
930
        bare_nodes = []
922
938
        # Should have read the root node, then one leaf page:
923
939
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
924
940
             ('readv',  'index', [(8192, 4096), ], False, None)],
925
 
            transport._activity)
 
941
            t._activity)
926
942
 
927
943
    def test_iter_key_prefix_1_element_key_None(self):
928
944
        index = self.make_index()
929
 
        self.assertRaises(errors.BadIndexKey, list,
 
945
        self.assertRaises(_mod_index.BadIndexKey, list,
930
946
            index.iter_entries_prefix([(None, )]))
931
947
 
932
948
    def test_iter_key_prefix_wrong_length(self):
933
949
        index = self.make_index()
934
 
        self.assertRaises(errors.BadIndexKey, list,
935
 
            index.iter_entries_prefix([('foo', None)]))
 
950
        self.assertRaises(_mod_index.BadIndexKey, list,
 
951
            index.iter_entries_prefix([(b'foo', None)]))
936
952
        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)]))
 
953
        self.assertRaises(_mod_index.BadIndexKey, list,
 
954
            index.iter_entries_prefix([(b'foo', )]))
 
955
        self.assertRaises(_mod_index.BadIndexKey, list,
 
956
            index.iter_entries_prefix([(b'foo', None, None)]))
941
957
 
942
958
    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', )])))
 
959
        index = self.make_index(nodes=[
 
960
            ((b'name', ), b'data', ()),
 
961
            ((b'ref', ), b'refdata', ())])
 
962
        self.assertEqual({(index, (b'name', ), b'data'),
 
963
            (index, (b'ref', ), b'refdata')},
 
964
            set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
949
965
 
950
966
    def test_iter_key_prefix_1_key_element_refs(self):
951
967
        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', )])))
 
968
            ((b'name', ), b'data', ([(b'ref', )], )),
 
969
            ((b'ref', ), b'refdata', ([], ))])
 
970
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),)),
 
971
            (index, (b'ref', ), b'refdata', ((), ))},
 
972
            set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
957
973
 
958
974
    def test_iter_key_prefix_2_key_element_no_refs(self):
959
975
        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)])))
 
976
            ((b'name', b'fin1'), b'data', ()),
 
977
            ((b'name', b'fin2'), b'beta', ()),
 
978
            ((b'ref', b'erence'), b'refdata', ())])
 
979
        self.assertEqual({(index, (b'name', b'fin1'), b'data'),
 
980
            (index, (b'ref', b'erence'), b'refdata')},
 
981
            set(index.iter_entries_prefix(
 
982
                [(b'name', b'fin1'), (b'ref', b'erence')])))
 
983
        self.assertEqual({(index, (b'name', b'fin1'), b'data'),
 
984
            (index, (b'name', b'fin2'), b'beta')},
 
985
            set(index.iter_entries_prefix([(b'name', None)])))
969
986
 
970
987
    def test_iter_key_prefix_2_key_element_refs(self):
971
988
        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)])))
 
989
            ((b'name', b'fin1'), b'data', ([(b'ref', b'erence')], )),
 
990
            ((b'name', b'fin2'), b'beta', ([], )),
 
991
            ((b'ref', b'erence'), b'refdata', ([], ))])
 
992
        self.assertEqual(
 
993
            {(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
 
994
                (index, (b'ref', b'erence'), b'refdata', ((), ))},
 
995
            set(index.iter_entries_prefix(
 
996
                [(b'name', b'fin1'), (b'ref', b'erence')])))
 
997
        self.assertEqual(
 
998
            {(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
 
999
                (index, (b'name', b'fin2'), b'beta', ((), ))},
 
1000
            set(index.iter_entries_prefix([(b'name', None)])))
981
1001
 
982
1002
    # XXX: external_references tests are duplicated in test_index.  We
983
1003
    # probably should have per_graph_index tests...
987
1007
 
988
1008
    def test_external_references_no_results(self):
989
1009
        index = self.make_index(ref_lists=1, nodes=[
990
 
            (('key',), 'value', ([],))])
 
1010
            ((b'key',), b'value', ([],))])
991
1011
        self.assertEqual(set(), index.external_references(0))
992
1012
 
993
1013
    def test_external_references_missing_ref(self):
994
 
        missing_key = ('missing',)
 
1014
        missing_key = (b'missing',)
995
1015
        index = self.make_index(ref_lists=1, nodes=[
996
 
            (('key',), 'value', ([missing_key],))])
997
 
        self.assertEqual(set([missing_key]), index.external_references(0))
 
1016
            ((b'key',), b'value', ([missing_key],))])
 
1017
        self.assertEqual({missing_key}, index.external_references(0))
998
1018
 
999
1019
    def test_external_references_multiple_ref_lists(self):
1000
 
        missing_key = ('missing',)
 
1020
        missing_key = (b'missing',)
1001
1021
        index = self.make_index(ref_lists=2, nodes=[
1002
 
            (('key',), 'value', ([], [missing_key]))])
 
1022
            ((b'key',), b'value', ([], [missing_key]))])
1003
1023
        self.assertEqual(set([]), index.external_references(0))
1004
 
        self.assertEqual(set([missing_key]), index.external_references(1))
 
1024
        self.assertEqual({missing_key}, index.external_references(1))
1005
1025
 
1006
1026
    def test_external_references_two_records(self):
1007
1027
        index = self.make_index(ref_lists=1, nodes=[
1008
 
            (('key-1',), 'value', ([('key-2',)],)),
1009
 
            (('key-2',), 'value', ([],)),
 
1028
            ((b'key-1',), b'value', ([(b'key-2',)],)),
 
1029
            ((b'key-2',), b'value', ([],)),
1010
1030
            ])
1011
1031
        self.assertEqual(set([]), index.external_references(0))
1012
1032
 
1013
1033
    def test__find_ancestors_one_page(self):
1014
 
        key1 = ('key-1',)
1015
 
        key2 = ('key-2',)
 
1034
        key1 = (b'key-1',)
 
1035
        key2 = (b'key-2',)
1016
1036
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1017
 
            (key1, 'value', ([key2],)),
1018
 
            (key2, 'value', ([],)),
 
1037
            (key1, b'value', ([key2],)),
 
1038
            (key2, b'value', ([],)),
1019
1039
            ])
1020
1040
        parent_map = {}
1021
1041
        missing_keys = set()
1025
1045
        self.assertEqual(set(), search_keys)
1026
1046
 
1027
1047
    def test__find_ancestors_one_page_w_missing(self):
1028
 
        key1 = ('key-1',)
1029
 
        key2 = ('key-2',)
1030
 
        key3 = ('key-3',)
 
1048
        key1 = (b'key-1',)
 
1049
        key2 = (b'key-2',)
 
1050
        key3 = (b'key-3',)
1031
1051
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1032
 
            (key1, 'value', ([key2],)),
1033
 
            (key2, 'value', ([],)),
 
1052
            (key1, b'value', ([key2],)),
 
1053
            (key2, b'value', ([],)),
1034
1054
            ])
1035
1055
        parent_map = {}
1036
1056
        missing_keys = set()
1039
1059
        self.assertEqual({key2: ()}, parent_map)
1040
1060
        # we know that key3 is missing because we read the page that it would
1041
1061
        # otherwise be on
1042
 
        self.assertEqual(set([key3]), missing_keys)
 
1062
        self.assertEqual({key3}, missing_keys)
1043
1063
        self.assertEqual(set(), search_keys)
1044
1064
 
1045
1065
    def test__find_ancestors_one_parent_missing(self):
1046
 
        key1 = ('key-1',)
1047
 
        key2 = ('key-2',)
1048
 
        key3 = ('key-3',)
 
1066
        key1 = (b'key-1',)
 
1067
        key2 = (b'key-2',)
 
1068
        key3 = (b'key-3',)
1049
1069
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1050
 
            (key1, 'value', ([key2],)),
1051
 
            (key2, 'value', ([key3],)),
 
1070
            (key1, b'value', ([key2],)),
 
1071
            (key2, b'value', ([key3],)),
1052
1072
            ])
1053
1073
        parent_map = {}
1054
1074
        missing_keys = set()
1059
1079
        # all we know is that key3 wasn't present on the page we were reading
1060
1080
        # but if you look, the last key is key2 which comes before key3, so we
1061
1081
        # don't know whether key3 would land on this page or not.
1062
 
        self.assertEqual(set([key3]), search_keys)
 
1082
        self.assertEqual({key3}, search_keys)
1063
1083
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
1064
1084
                                            missing_keys)
1065
1085
        # passing it back in, we are sure it is 'missing'
1066
1086
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1067
 
        self.assertEqual(set([key3]), missing_keys)
 
1087
        self.assertEqual({key3}, missing_keys)
1068
1088
        self.assertEqual(set([]), search_keys)
1069
1089
 
1070
1090
    def test__find_ancestors_dont_search_known(self):
1071
 
        key1 = ('key-1',)
1072
 
        key2 = ('key-2',)
1073
 
        key3 = ('key-3',)
 
1091
        key1 = (b'key-1',)
 
1092
        key2 = (b'key-2',)
 
1093
        key3 = (b'key-3',)
1074
1094
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1075
 
            (key1, 'value', ([key2],)),
1076
 
            (key2, 'value', ([key3],)),
1077
 
            (key3, 'value', ([],)),
 
1095
            (key1, b'value', ([key2],)),
 
1096
            (key2, b'value', ([key3],)),
 
1097
            (key3, b'value', ([],)),
1078
1098
            ])
1079
1099
        # We already know about key2, so we won't try to search for key3
1080
1100
        parent_map = {key2: (key3,)}
1092
1112
        nodes = []
1093
1113
        ref_lists = ((),)
1094
1114
        rev_keys = []
1095
 
        for i in xrange(400):
1096
 
            rev_id = '%s-%s-%s' % (email,
 
1115
        for i in range(400):
 
1116
            rev_id = ('%s-%s-%s' % (email,
1097
1117
                                   osutils.compact_date(start_time + i),
1098
 
                                   osutils.rand_chars(16))
 
1118
                                   osutils.rand_chars(16))).encode('ascii')
1099
1119
            rev_key = (rev_id,)
1100
 
            nodes.append((rev_key, 'value', ref_lists))
 
1120
            nodes.append((rev_key, b'value', ref_lists))
1101
1121
            # We have a ref 'list' of length 1, with a list of parents, with 1
1102
1122
            # parent which is a key
1103
1123
            ref_lists = ((rev_key,),)
1111
1131
        min_l2_key = l2.min_key
1112
1132
        max_l1_key = l1.max_key
1113
1133
        self.assertTrue(max_l1_key < min_l2_key)
1114
 
        parents_min_l2_key = l2.keys[min_l2_key][1][0]
 
1134
        parents_min_l2_key = l2[min_l2_key][1][0]
1115
1135
        self.assertEqual((l1.max_key,), parents_min_l2_key)
1116
1136
        # Now, whatever key we select that would fall on the second page,
1117
1137
        # should give us all the parents until the page break
1126
1146
                                            missing_keys)
1127
1147
        self.assertEqual([min_l2_key, next_key], sorted(parent_map))
1128
1148
        self.assertEqual(set(), missing_keys)
1129
 
        self.assertEqual(set([max_l1_key]), search_keys)
 
1149
        self.assertEqual({max_l1_key}, search_keys)
1130
1150
        parent_map = {}
1131
1151
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
1132
1152
                                            missing_keys)
1133
 
        self.assertEqual(sorted(l1.keys), sorted(parent_map))
 
1153
        self.assertEqual(l1.all_keys(), sorted(parent_map))
1134
1154
        self.assertEqual(set(), missing_keys)
1135
1155
        self.assertEqual(set(), search_keys)
1136
1156
 
1142
1162
                                            missing_keys)
1143
1163
        self.assertEqual(set(), search_keys)
1144
1164
        self.assertEqual({}, parent_map)
1145
 
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
 
1165
        self.assertEqual({('one',), ('two',)}, missing_keys)
1146
1166
 
1147
1167
    def test_supports_unlimited_cache(self):
1148
1168
        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)
1152
1172
        for node in nodes:
1153
1173
            builder.add_node(*node)
1154
1174
        stream = builder.finish()
1155
 
        trans = get_transport(self.get_url())
 
1175
        trans = self.get_transport()
1156
1176
        size = trans.put_file('index', stream)
1157
1177
        index = btree_index.BTreeGraphIndex(trans, 'index', size)
1158
1178
        self.assertEqual(500, index.key_count())
1184
1204
 
1185
1205
class TestBTreeNodes(BTreeTestCase):
1186
1206
 
 
1207
    scenarios = btreeparser_scenarios()
 
1208
 
1187
1209
    def setUp(self):
1188
 
        BTreeTestCase.setUp(self)
 
1210
        super(TestBTreeNodes, self).setUp()
1189
1211
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
1190
1212
 
1191
1213
    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")
 
1214
        node_bytes = (b"type=leaf\n"
 
1215
            b"0000000000000000000000000000000000000000\x00\x00value:0\n"
 
1216
            b"1111111111111111111111111111111111111111\x00\x00value:1\n"
 
1217
            b"2222222222222222222222222222222222222222\x00\x00value:2\n"
 
1218
            b"3333333333333333333333333333333333333333\x00\x00value:3\n"
 
1219
            b"4444444444444444444444444444444444444444\x00\x00value:4\n")
1198
1220
        node = btree_index._LeafNode(node_bytes, 1, 0)
1199
1221
        # We do direct access, or don't care about order, to leaf nodes most of
1200
1222
        # the time, so a dict is useful:
1201
1223
        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)
 
1224
            (b"0000000000000000000000000000000000000000",): (b"value:0", ()),
 
1225
            (b"1111111111111111111111111111111111111111",): (b"value:1", ()),
 
1226
            (b"2222222222222222222222222222222222222222",): (b"value:2", ()),
 
1227
            (b"3333333333333333333333333333333333333333",): (b"value:3", ()),
 
1228
            (b"4444444444444444444444444444444444444444",): (b"value:4", ()),
 
1229
            }, dict(node.all_items()))
1208
1230
 
1209
1231
    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
 
            ""
 
1232
        node_bytes = (b"type=leaf\n"
 
1233
            b"00\x0000\x00\t00\x00ref00\x00value:0\n"
 
1234
            b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
 
1235
            b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
 
1236
            b"11\x0044\x00\t11\x00ref00\x00value:4\n"
 
1237
            b""
1216
1238
            )
1217
1239
        node = btree_index._LeafNode(node_bytes, 2, 2)
1218
1240
        # We do direct access, or don't care about order, to leaf nodes most of
1219
1241
        # the time, so a dict is useful:
1220
1242
        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)
 
1243
            (b'00', b'00'): (b'value:0', ((), ((b'00', b'ref00'),))),
 
1244
            (b'00', b'11'): (b'value:1', (((b'00', b'ref00'),),
 
1245
                ((b'00', b'ref00'), (b'01', b'ref01')))),
 
1246
            (b'11', b'33'): (b'value:3', (((b'11', b'ref22'),),
 
1247
                ((b'11', b'ref22'), (b'11', b'ref22')))),
 
1248
            (b'11', b'44'): (b'value:4', ((), ((b'11', b'ref00'),)))
 
1249
            }, dict(node.all_items()))
1228
1250
 
1229
1251
    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"
 
1252
        node_bytes = (b"type=internal\n"
 
1253
            b"offset=1\n"
 
1254
            b"0000000000000000000000000000000000000000\n"
 
1255
            b"1111111111111111111111111111111111111111\n"
 
1256
            b"2222222222222222222222222222222222222222\n"
 
1257
            b"3333333333333333333333333333333333333333\n"
 
1258
            b"4444444444444444444444444444444444444444\n"
1237
1259
            )
1238
1260
        node = btree_index._InternalNode(node_bytes)
1239
1261
        # We want to bisect to find the right children from this node, so a
1240
1262
        # vector is most useful.
1241
1263
        self.assertEqual([
1242
 
            ("0000000000000000000000000000000000000000",),
1243
 
            ("1111111111111111111111111111111111111111",),
1244
 
            ("2222222222222222222222222222222222222222",),
1245
 
            ("3333333333333333333333333333333333333333",),
1246
 
            ("4444444444444444444444444444444444444444",),
 
1264
            (b"0000000000000000000000000000000000000000",),
 
1265
            (b"1111111111111111111111111111111111111111",),
 
1266
            (b"2222222222222222222222222222222222222222",),
 
1267
            (b"3333333333333333333333333333333333333333",),
 
1268
            (b"4444444444444444444444444444444444444444",),
1247
1269
            ], node.keys)
1248
1270
        self.assertEqual(1, node.offset)
1249
1271
 
1250
1272
    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
 
            ""
 
1273
        node_bytes = (b"type=leaf\n"
 
1274
            b"00\x0000\x00\t00\x00ref00\x00value:0\n"
 
1275
            b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
 
1276
            b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
 
1277
            b"11\x0044\x00\t11\x00ref00\x00value:4\n"
 
1278
            b""
1257
1279
            )
1258
1280
        node = btree_index._LeafNode(node_bytes, 2, 2)
1259
1281
        # We do direct access, or don't care about order, to leaf nodes most of
1260
1282
        # the time, so a dict is useful:
1261
1283
        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)
 
1284
            (b'00', b'00'): (b'value:0', ((), ((b'00', b'ref00'),))),
 
1285
            (b'00', b'11'): (b'value:1', (((b'00', b'ref00'),),
 
1286
                ((b'00', b'ref00'), (b'01', b'ref01')))),
 
1287
            (b'11', b'33'): (b'value:3', (((b'11', b'ref22'),),
 
1288
                ((b'11', b'ref22'), (b'11', b'ref22')))),
 
1289
            (b'11', b'44'): (b'value:4', ((), ((b'11', b'ref00'),)))
 
1290
            }, dict(node.all_items()))
1269
1291
 
1270
1292
    def assertFlattened(self, expected, key, value, refs):
1271
1293
        flat_key, flat_line = self.parse_btree._flatten_node(
1272
1294
            (None, key, value, refs), bool(refs))
1273
 
        self.assertEqual('\x00'.join(key), flat_key)
 
1295
        self.assertEqual(b'\x00'.join(key), flat_key)
1274
1296
        self.assertEqual(expected, flat_line)
1275
1297
 
1276
1298
    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'),)))
 
1299
        self.assertFlattened(b'key\0\0value\n', (b'key',), b'value', [])
 
1300
        self.assertFlattened(b'key\0tuple\0\0value str\n',
 
1301
            (b'key', b'tuple'), b'value str', [])
 
1302
        self.assertFlattened(b'key\0tuple\0triple\0\0value str\n',
 
1303
            (b'key', b'tuple', b'triple'), b'value str', [])
 
1304
        self.assertFlattened(b'k\0t\0s\0ref\0value str\n',
 
1305
            (b'k', b't', b's'), b'value str', [[(b'ref',)]])
 
1306
        self.assertFlattened(b'key\0tuple\0ref\0key\0value str\n',
 
1307
            (b'key', b'tuple'), b'value str', [[(b'ref', b'key')]])
 
1308
        self.assertFlattened(b"00\x0000\x00\t00\x00ref00\x00value:0\n",
 
1309
            (b'00', b'00'), b'value:0', ((), ((b'00', b'ref00'),)))
 
1310
        self.assertFlattened(
 
1311
            b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n",
 
1312
            (b'00', b'11'), b'value:1',
 
1313
                (((b'00', b'ref00'),), ((b'00', b'ref00'), (b'01', b'ref01'))))
 
1314
        self.assertFlattened(
 
1315
            b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n",
 
1316
            (b'11', b'33'), b'value:3',
 
1317
                (((b'11', b'ref22'),), ((b'11', b'ref22'), (b'11', b'ref22'))))
 
1318
        self.assertFlattened(
 
1319
            b"11\x0044\x00\t11\x00ref00\x00value:4\n",
 
1320
            (b'11', b'44'), b'value:4', ((), ((b'11', b'ref00'),)))
1299
1321
 
1300
1322
 
1301
1323
class TestCompiledBtree(tests.TestCase):
1349
1371
        This doesn't actually create anything on disk, it just primes a
1350
1372
        BTreeGraphIndex with the recommended information.
1351
1373
        """
1352
 
        index = btree_index.BTreeGraphIndex(get_transport('memory:///'),
1353
 
                                            'test-index', size=size)
 
1374
        index = btree_index.BTreeGraphIndex(
 
1375
            transport.get_transport_from_url('memory:///'),
 
1376
            'test-index', size=size)
1354
1377
        if recommended_pages is not None:
1355
1378
            index._recommended_pages = recommended_pages
1356
1379
        return index
1370
1393
        index._key_count = key_count
1371
1394
        index._row_lengths = row_lengths
1372
1395
        index._compute_row_offsets()
1373
 
        index._root_node = btree_index._InternalNode('internal\noffset=0\n')
 
1396
        index._root_node = btree_index._InternalNode(b'internal\noffset=0\n')
1374
1397
        self.set_cached_offsets(index, cached_offsets)
1375
1398
 
1376
1399
    def make_100_node_index(self):
1434
1457
 
1435
1458
    def test_read_all_from_root(self):
1436
1459
        index = self.make_index(4096*10, 20)
1437
 
        self.assertExpandOffsets(range(10), index, [0])
 
1460
        self.assertExpandOffsets(list(range(10)), index, [0])
1438
1461
 
1439
1462
    def test_read_all_when_cached(self):
1440
1463
        # We've read enough that we can grab all the rest in a single request