/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_btree_index.py

  • Committer: Marius Kruger
  • Date: 2010-07-10 21:28:56 UTC
  • mto: (5384.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 5385.
  • Revision ID: marius.kruger@enerweb.co.za-20100710212856-uq4ji3go0u5se7hx
* Update documentation
* add NEWS

Show diffs side-by-side

added added

removed removed

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