/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: 2017-07-23 22:06:41 UTC
  • mfrom: (6738 trunk)
  • mto: This revision was merged to the branch mainline in revision 6739.
  • Revision ID: jelmer@jelmer.uk-20170723220641-69eczax9bmv8d6kk
Merge trunk, address review comments.

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