/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: Richard Wilbur
  • Date: 2016-02-04 19:07:28 UTC
  • mto: This revision was merged to the branch mainline in revision 6618.
  • Revision ID: richard.wilbur@gmail.com-20160204190728-p0zvfii6zase0fw7
Update COPYING.txt from the original http://www.gnu.org/licenses/gpl-2.0.txt  (Only differences were in whitespace.)  Thanks to Petr Stodulka for pointing out the discrepancy.

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-2011 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
34
    scenarios,
38
35
    )
39
 
from ..tests import (
 
36
from bzrlib.tests import (
40
37
    features,
41
38
    )
42
39
 
45
42
 
46
43
 
47
44
def btreeparser_scenarios():
48
 
    import breezy.bzr._btree_serializer_py as py_module
 
45
    import bzrlib._btree_serializer_py as py_module
49
46
    scenarios = [('python', {'parse_btree': py_module})]
50
47
    if compiled_btreeparser_feature.available():
51
48
        scenarios.append(('C', 
54
51
 
55
52
 
56
53
compiled_btreeparser_feature = features.ModuleAvailableFeature(
57
 
    'breezy.bzr._btree_serializer_pyx')
 
54
    'bzrlib._btree_serializer_pyx')
58
55
 
59
56
 
60
57
class BTreeTestCase(TestCaseWithTransport):
67
64
 
68
65
    def make_nodes(self, count, key_elements, reference_lists):
69
66
        """Generate count*key_elements sample nodes."""
70
 
        def _pos_to_key(pos, lead=b""):
71
 
            return (lead + (b"%d" % pos) * 40,)
72
67
        keys = []
73
68
        for prefix_pos in range(key_elements):
74
69
            if key_elements - 1:
75
 
                prefix = _pos_to_key(prefix_pos)
 
70
                prefix = (str(prefix_pos) * 40,)
76
71
            else:
77
72
                prefix = ()
78
 
            for pos in range(count):
 
73
            for pos in xrange(count):
79
74
                # TODO: This creates odd keys. When count == 100,000, it
80
75
                #       creates a 240 byte key
81
 
                key = prefix + _pos_to_key(pos)
82
 
                value = b"value:%d" % pos
 
76
                key = prefix + (str(pos) * 40,)
 
77
                value = "value:%s" % pos
83
78
                if reference_lists:
84
79
                    # generate some references
85
80
                    refs = []
92
87
                        for ref_pos in range(list_pos + pos % 2):
93
88
                            if pos % 2:
94
89
                                # refer to a nearby key
95
 
                                refs[-1].append(prefix + _pos_to_key(pos - 1, b"ref"))
 
90
                                refs[-1].append(prefix + ("ref" + str(pos - 1) * 40,))
96
91
                            else:
97
92
                                # serial of this ref in the ref list
98
 
                                refs[-1].append(prefix + _pos_to_key(ref_pos, b"ref"))
 
93
                                refs[-1].append(prefix + ("ref" + str(ref_pos) * 40,))
99
94
                        refs[-1] = tuple(refs[-1])
100
95
                    refs = tuple(refs)
101
96
                else:
108
103
        self.overrideAttr(btree_index, '_PAGE_SIZE')
109
104
        btree_index._PAGE_SIZE = 2048
110
105
 
111
 
    def assertEqualApproxCompressed(self, expected, actual, slop=6):
 
106
    def assertEqualsApproxCompressed(self, expected, actual, slop=6):
112
107
        """Check a count of compressed bytes is approximately as expected
113
108
 
114
109
        Relying on compressed length being stable even with fixed inputs is
134
129
        content = temp_file.read()
135
130
        del temp_file
136
131
        self.assertEqual(
137
 
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=0\n"
138
 
            b"row_lengths=\n",
 
132
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=0\n"
 
133
            "row_lengths=\n",
139
134
            content)
140
135
 
141
136
    def test_empty_2_1(self):
145
140
        content = temp_file.read()
146
141
        del temp_file
147
142
        self.assertEqual(
148
 
            b"B+Tree Graph Index 2\nnode_ref_lists=1\nkey_elements=2\nlen=0\n"
149
 
            b"row_lengths=\n",
 
143
            "B+Tree Graph Index 2\nnode_ref_lists=1\nkey_elements=2\nlen=0\n"
 
144
            "row_lengths=\n",
150
145
            content)
151
146
 
152
147
    def test_root_leaf_1_0(self):
160
155
        del temp_file
161
156
        self.assertEqual(131, len(content))
162
157
        self.assertEqual(
163
 
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"
164
 
            b"row_lengths=1\n",
 
158
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"
 
159
            "row_lengths=1\n",
165
160
            content[:73])
166
161
        node_content = content[73:]
167
162
        node_bytes = zlib.decompress(node_content)
168
 
        expected_node = (b"type=leaf\n"
169
 
            b"0000000000000000000000000000000000000000\x00\x00value:0\n"
170
 
            b"1111111111111111111111111111111111111111\x00\x00value:1\n"
171
 
            b"2222222222222222222222222222222222222222\x00\x00value:2\n"
172
 
            b"3333333333333333333333333333333333333333\x00\x00value:3\n"
173
 
            b"4444444444444444444444444444444444444444\x00\x00value:4\n")
 
163
        expected_node = ("type=leaf\n"
 
164
            "0000000000000000000000000000000000000000\x00\x00value:0\n"
 
165
            "1111111111111111111111111111111111111111\x00\x00value:1\n"
 
166
            "2222222222222222222222222222222222222222\x00\x00value:2\n"
 
167
            "3333333333333333333333333333333333333333\x00\x00value:3\n"
 
168
            "4444444444444444444444444444444444444444\x00\x00value:4\n")
174
169
        self.assertEqual(expected_node, node_bytes)
175
170
 
176
171
    def test_root_leaf_2_2(self):
184
179
        del temp_file
185
180
        self.assertEqual(238, len(content))
186
181
        self.assertEqual(
187
 
            b"B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"
188
 
            b"row_lengths=1\n",
 
182
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"
 
183
            "row_lengths=1\n",
189
184
            content[:74])
190
185
        node_content = content[74:]
191
186
        node_bytes = zlib.decompress(node_content)
192
187
        expected_node = (
193
 
            b"type=leaf\n"
194
 
            b"0000000000000000000000000000000000000000\x000000000000000000000000000000000000000000\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:0\n"
195
 
            b"0000000000000000000000000000000000000000\x001111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\r0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:1\n"
196
 
            b"0000000000000000000000000000000000000000\x002222222222222222222222222222222222222222\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:2\n"
197
 
            b"0000000000000000000000000000000000000000\x003333333333333333333333333333333333333333\x000000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\t0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\r0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\x00value:3\n"
198
 
            b"0000000000000000000000000000000000000000\x004444444444444444444444444444444444444444\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:4\n"
199
 
            b"1111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:0\n"
200
 
            b"1111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\r1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:1\n"
201
 
            b"1111111111111111111111111111111111111111\x002222222222222222222222222222222222222222\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:2\n"
202
 
            b"1111111111111111111111111111111111111111\x003333333333333333333333333333333333333333\x001111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\t1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\r1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\x00value:3\n"
203
 
            b"1111111111111111111111111111111111111111\x004444444444444444444444444444444444444444\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:4\n"
204
 
            b""
 
188
            "type=leaf\n"
 
189
            "0000000000000000000000000000000000000000\x000000000000000000000000000000000000000000\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:0\n"
 
190
            "0000000000000000000000000000000000000000\x001111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\r0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:1\n"
 
191
            "0000000000000000000000000000000000000000\x002222222222222222222222222222222222222222\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:2\n"
 
192
            "0000000000000000000000000000000000000000\x003333333333333333333333333333333333333333\x000000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\t0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\r0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\x00value:3\n"
 
193
            "0000000000000000000000000000000000000000\x004444444444444444444444444444444444444444\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:4\n"
 
194
            "1111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:0\n"
 
195
            "1111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\r1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:1\n"
 
196
            "1111111111111111111111111111111111111111\x002222222222222222222222222222222222222222\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:2\n"
 
197
            "1111111111111111111111111111111111111111\x003333333333333333333333333333333333333333\x001111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\t1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\r1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\x00value:3\n"
 
198
            "1111111111111111111111111111111111111111\x004444444444444444444444444444444444444444\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:4\n"
 
199
            ""
205
200
            )
206
201
        self.assertEqual(expected_node, node_bytes)
207
202
 
214
209
        temp_file = builder.finish()
215
210
        content = temp_file.read()
216
211
        del temp_file
217
 
        self.assertEqualApproxCompressed(9283, len(content))
 
212
        self.assertEqualsApproxCompressed(9283, len(content))
218
213
        self.assertEqual(
219
 
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
220
 
            b"row_lengths=1,2\n",
 
214
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
 
215
            "row_lengths=1,2\n",
221
216
            content[:77])
222
217
        root = content[77:4096]
223
218
        leaf1 = content[4096:8192]
224
219
        leaf2 = content[8192:]
225
220
        root_bytes = zlib.decompress(root)
226
221
        expected_root = (
227
 
            b"type=internal\n"
228
 
            b"offset=0\n"
229
 
            ) + (b"307" * 40) + b"\n"
 
222
            "type=internal\n"
 
223
            "offset=0\n"
 
224
            ) + ("307" * 40) + "\n"
230
225
        self.assertEqual(expected_root, root_bytes)
231
226
        # We already know serialisation works for leaves, check key selection:
232
227
        leaf1_bytes = zlib.decompress(leaf1)
248
243
        temp_file = builder.finish()
249
244
        content = temp_file.read()
250
245
        del temp_file
251
 
        self.assertEqualApproxCompressed(155, len(content))
 
246
        self.assertEqualsApproxCompressed(155, len(content))
252
247
        self.assertEqual(
253
 
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
254
 
            b"row_lengths=1\n",
 
248
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
 
249
            "row_lengths=1\n",
255
250
            content[:74])
256
251
        # Check thelast page is well formed
257
252
        leaf2 = content[74:]
270
265
        temp_file = builder.finish()
271
266
        content = temp_file.read()
272
267
        del temp_file
273
 
        self.assertEqualApproxCompressed(9283, len(content))
 
268
        self.assertEqualsApproxCompressed(9283, len(content))
274
269
        self.assertEqual(
275
 
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
276
 
            b"row_lengths=1,2\n",
 
270
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
 
271
            "row_lengths=1,2\n",
277
272
            content[:77])
278
273
        # Check the last page is well formed
279
274
        leaf2 = content[8192:]
329
324
        temp_file = builder.finish()
330
325
        content = temp_file.read()
331
326
        del temp_file
332
 
        self.assertEqualApproxCompressed(12643, len(content))
 
327
        self.assertEqualsApproxCompressed(12643, len(content))
333
328
        self.assertEqual(
334
 
            b"B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
335
 
            b"row_lengths=1,3\n",
 
329
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
 
330
            "row_lengths=1,3\n",
336
331
            content[:77])
337
332
        root = content[77:4096]
338
333
        leaf1 = content[4096:8192]
340
335
        leaf3 = content[12288:]
341
336
        root_bytes = zlib.decompress(root)
342
337
        expected_root = (
343
 
            b"type=internal\n"
344
 
            b"offset=0\n"
345
 
            + (b"0" * 40) + b"\x00" + (b"91" * 40) + b"\n"
346
 
            + (b"1" * 40) + b"\x00" + (b"81" * 40) + b"\n"
 
338
            "type=internal\n"
 
339
            "offset=0\n"
 
340
            + ("0" * 40) + "\x00" + ("91" * 40) + "\n"
 
341
            + ("1" * 40) + "\x00" + ("81" * 40) + "\n"
347
342
            )
348
343
        self.assertEqual(expected_root, root_bytes)
349
344
        # We assume the other leaf nodes have been written correctly - layering
407
402
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
408
403
            list(builder.iter_all_entries()))
409
404
        # Two nodes - one memory one disk
410
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
 
405
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
411
406
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
412
407
        self.assertEqual(13, builder.key_count())
413
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
 
408
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
414
409
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
415
410
        builder.add_node(*nodes[13])
416
411
        self.assertEqual(3, len(builder._backing_indices))
481
476
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
482
477
            list(builder.iter_all_entries()))
483
478
        # Two nodes - one memory one disk
484
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
 
479
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
485
480
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
486
481
        self.assertEqual(13, builder.key_count())
487
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
 
482
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
488
483
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
489
484
        builder.add_node(*nodes[13])
490
485
        builder.add_node(*nodes[14])
581
576
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
582
577
            list(builder.iter_all_entries()))
583
578
        # Two nodes - one memory one disk
584
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
 
579
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
585
580
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
586
581
        self.assertEqual(13, builder.key_count())
587
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
 
582
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
588
583
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
589
584
        builder.add_node(*nodes[13])
590
585
        self.assertEqual(3, len(builder._backing_indices))
612
607
        builder.add_node(*nodes[0])
613
608
        builder.add_node(*nodes[1])
614
609
        builder.add_node(*nodes[0])
615
 
        self.assertRaises(_mod_index.BadIndexDuplicateKey, builder.finish)
 
610
        self.assertRaises(errors.BadIndexDuplicateKey, builder.finish)
616
611
 
617
612
 
618
613
class TestBTreeIndex(BTreeTestCase):
638
633
        content = temp_file.read()
639
634
        del temp_file
640
635
        size = len(content)
641
 
        transport.put_bytes('index', (b' '*offset)+content)
 
636
        transport.put_bytes('index', (' '*offset)+content)
642
637
        return btree_index.BTreeGraphIndex(transport, 'index', size=size,
643
638
                                           offset=offset)
644
639
 
648
643
        self.assertEqual(1, len(list(index.iter_entries([nodes[30][0]]))))
649
644
        self.assertEqual([1, 4], index._row_lengths)
650
645
        self.assertIsNot(None, index._root_node)
651
 
        internal_node_pre_clear = set(index._internal_node_cache)
 
646
        internal_node_pre_clear = index._internal_node_cache.keys()
652
647
        self.assertTrue(len(index._leaf_node_cache) > 0)
653
648
        index.clear_cache()
654
649
        # We don't touch _root_node or _internal_node_cache, both should be
660
655
        #       becuase without a 3-level index, we don't have any internal
661
656
        #       nodes cached.
662
657
        self.assertEqual(internal_node_pre_clear,
663
 
                         set(index._internal_node_cache))
 
658
                         index._internal_node_cache.keys())
664
659
        self.assertEqual(0, len(index._leaf_node_cache))
665
660
 
666
661
    def test_trivial_constructor(self):
715
710
        # The entire index should have been read, as it is one page long.
716
711
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
717
712
            t._activity)
718
 
        self.assertEqualApproxCompressed(1173, size)
 
713
        self.assertEqualsApproxCompressed(1173, size)
719
714
 
720
715
    def test_with_offset_no_size(self):
721
716
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
737
732
        self.assertEqual(200, index.key_count())
738
733
 
739
734
    def test__read_nodes_no_size_one_page_reads_once(self):
740
 
        self.make_index(nodes=[((b'key',), b'value', ())])
 
735
        self.make_index(nodes=[(('key',), 'value', ())])
741
736
        trans = transport.get_transport_from_url('trace+' + self.get_url())
742
737
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
743
738
        del trans._activity[:]
744
739
        nodes = dict(index._read_nodes([0]))
745
 
        self.assertEqual({0}, set(nodes))
 
740
        self.assertEqual([0], nodes.keys())
746
741
        node = nodes[0]
747
 
        self.assertEqual([(b'key',)], node.all_keys())
 
742
        self.assertEqual([('key',)], node.all_keys())
748
743
        self.assertEqual([('get', 'index')], trans._activity)
749
744
 
750
745
    def test__read_nodes_no_size_multiple_pages(self):
756
751
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
757
752
        del trans._activity[:]
758
753
        nodes = dict(index._read_nodes([0]))
759
 
        self.assertEqual(list(range(num_pages)), sorted(nodes))
 
754
        self.assertEqual(range(num_pages), nodes.keys())
760
755
 
761
756
    def test_2_levels_key_count_2_2(self):
762
757
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
765
760
            builder.add_node(*node)
766
761
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
767
762
        size = t.put_file('index', builder.finish())
768
 
        self.assertEqualApproxCompressed(17692, size)
 
763
        self.assertEqualsApproxCompressed(17692, size)
769
764
        index = btree_index.BTreeGraphIndex(t, 'index', size)
770
765
        del t._activity[:]
771
766
        self.assertEqual([], t._activity)
788
783
        # The entire index should have been read linearly.
789
784
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
790
785
                         t._activity)
791
 
        self.assertEqualApproxCompressed(1488, size)
 
786
        self.assertEqualsApproxCompressed(1488, size)
792
787
 
793
788
    def test_validate_two_pages(self):
794
789
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
798
793
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
799
794
        size = t.put_file('index', builder.finish())
800
795
        # Root page, 2 leaf pages
801
 
        self.assertEqualApproxCompressed(9339, size)
 
796
        self.assertEqualsApproxCompressed(9339, size)
802
797
        index = btree_index.BTreeGraphIndex(t, 'index', size)
803
798
        del t._activity[:]
804
799
        self.assertEqual([], t._activity)
850
845
    def test_key_too_big(self):
851
846
        # the size that matters here is the _compressed_ size of the key, so we can't
852
847
        # do a simple character repeat.
853
 
        bigKey = b''.join(b'%d' % n for n in range(btree_index._PAGE_SIZE))
854
 
        self.assertRaises(_mod_index.BadIndexKey,
 
848
        bigKey = ''.join(map(repr, xrange(btree_index._PAGE_SIZE)))
 
849
        self.assertRaises(errors.BadIndexKey,
855
850
                          self.make_index,
856
 
                          nodes=[((bigKey,), b'value', ())])
857
 
 
 
851
                          nodes=[((bigKey,), 'value', ())])
 
852
        
858
853
    def test_iter_all_only_root_no_size(self):
859
 
        self.make_index(nodes=[((b'key',), b'value', ())])
 
854
        self.make_index(nodes=[(('key',), 'value', ())])
860
855
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
861
856
        index = btree_index.BTreeGraphIndex(t, 'index', None)
862
857
        del t._activity[:]
863
 
        self.assertEqual([((b'key',), b'value')],
 
858
        self.assertEqual([(('key',), 'value')],
864
859
                         [x[1:] for x in index.iter_all_entries()])
865
860
        self.assertEqual([('get', 'index')], t._activity)
866
861
 
897
892
        # The entire index should have been read
898
893
        total_pages = sum(index._row_lengths)
899
894
        self.assertEqual(total_pages, index._row_offsets[-1])
900
 
        self.assertEqualApproxCompressed(1303220, size)
 
895
        self.assertEqualsApproxCompressed(1303220, size)
901
896
        # The start of the leaves
902
897
        first_byte = index._row_offsets[-2] * page_size
903
898
        readv_request = []
911
906
            self.assertEqualDiff(pprint.pformat(expected),
912
907
                                 pprint.pformat(t._activity))
913
908
 
 
909
    def _test_iter_entries_references_resolved(self):
 
910
        index = self.make_index(1, nodes=[
 
911
            (('name', ), 'data', ([('ref', ), ('ref', )], )),
 
912
            (('ref', ), 'refdata', ([], ))])
 
913
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),('ref',)),)),
 
914
            (index, ('ref', ), 'refdata', ((), ))]),
 
915
            set(index.iter_entries([('name',), ('ref',)])))
 
916
 
914
917
    def test_iter_entries_references_2_refs_resolved(self):
915
918
        # iterating some entries reads just the pages needed. For now, to
916
919
        # get it working and start measuring, only 4K pages are read.
942
945
 
943
946
    def test_iter_key_prefix_1_element_key_None(self):
944
947
        index = self.make_index()
945
 
        self.assertRaises(_mod_index.BadIndexKey, list,
 
948
        self.assertRaises(errors.BadIndexKey, list,
946
949
            index.iter_entries_prefix([(None, )]))
947
950
 
948
951
    def test_iter_key_prefix_wrong_length(self):
949
952
        index = self.make_index()
950
 
        self.assertRaises(_mod_index.BadIndexKey, list,
951
 
            index.iter_entries_prefix([(b'foo', None)]))
 
953
        self.assertRaises(errors.BadIndexKey, list,
 
954
            index.iter_entries_prefix([('foo', None)]))
952
955
        index = self.make_index(key_elements=2)
953
 
        self.assertRaises(_mod_index.BadIndexKey, list,
954
 
            index.iter_entries_prefix([(b'foo', )]))
955
 
        self.assertRaises(_mod_index.BadIndexKey, list,
956
 
            index.iter_entries_prefix([(b'foo', None, None)]))
 
956
        self.assertRaises(errors.BadIndexKey, list,
 
957
            index.iter_entries_prefix([('foo', )]))
 
958
        self.assertRaises(errors.BadIndexKey, list,
 
959
            index.iter_entries_prefix([('foo', None, None)]))
957
960
 
958
961
    def test_iter_key_prefix_1_key_element_no_refs(self):
959
 
        index = self.make_index(nodes=[
960
 
            ((b'name', ), b'data', ()),
961
 
            ((b'ref', ), b'refdata', ())])
962
 
        self.assertEqual({(index, (b'name', ), b'data'),
963
 
            (index, (b'ref', ), b'refdata')},
964
 
            set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
 
962
        index = self.make_index( nodes=[
 
963
            (('name', ), 'data', ()),
 
964
            (('ref', ), 'refdata', ())])
 
965
        self.assertEqual(set([(index, ('name', ), 'data'),
 
966
            (index, ('ref', ), 'refdata')]),
 
967
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
965
968
 
966
969
    def test_iter_key_prefix_1_key_element_refs(self):
967
970
        index = self.make_index(1, nodes=[
968
 
            ((b'name', ), b'data', ([(b'ref', )], )),
969
 
            ((b'ref', ), b'refdata', ([], ))])
970
 
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),)),
971
 
            (index, (b'ref', ), b'refdata', ((), ))},
972
 
            set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
 
971
            (('name', ), 'data', ([('ref', )], )),
 
972
            (('ref', ), 'refdata', ([], ))])
 
973
        self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
 
974
            (index, ('ref', ), 'refdata', ((), ))]),
 
975
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
973
976
 
974
977
    def test_iter_key_prefix_2_key_element_no_refs(self):
975
978
        index = self.make_index(key_elements=2, nodes=[
976
 
            ((b'name', b'fin1'), b'data', ()),
977
 
            ((b'name', b'fin2'), b'beta', ()),
978
 
            ((b'ref', b'erence'), b'refdata', ())])
979
 
        self.assertEqual({(index, (b'name', b'fin1'), b'data'),
980
 
            (index, (b'ref', b'erence'), b'refdata')},
981
 
            set(index.iter_entries_prefix(
982
 
                [(b'name', b'fin1'), (b'ref', b'erence')])))
983
 
        self.assertEqual({(index, (b'name', b'fin1'), b'data'),
984
 
            (index, (b'name', b'fin2'), b'beta')},
985
 
            set(index.iter_entries_prefix([(b'name', None)])))
 
979
            (('name', 'fin1'), 'data', ()),
 
980
            (('name', 'fin2'), 'beta', ()),
 
981
            (('ref', 'erence'), 'refdata', ())])
 
982
        self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
 
983
            (index, ('ref', 'erence'), 'refdata')]),
 
984
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
 
985
        self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
 
986
            (index, ('name', 'fin2'), 'beta')]),
 
987
            set(index.iter_entries_prefix([('name', None)])))
986
988
 
987
989
    def test_iter_key_prefix_2_key_element_refs(self):
988
990
        index = self.make_index(1, key_elements=2, nodes=[
989
 
            ((b'name', b'fin1'), b'data', ([(b'ref', b'erence')], )),
990
 
            ((b'name', b'fin2'), b'beta', ([], )),
991
 
            ((b'ref', b'erence'), b'refdata', ([], ))])
992
 
        self.assertEqual(
993
 
            {(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
994
 
                (index, (b'ref', b'erence'), b'refdata', ((), ))},
995
 
            set(index.iter_entries_prefix(
996
 
                [(b'name', b'fin1'), (b'ref', b'erence')])))
997
 
        self.assertEqual(
998
 
            {(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
999
 
                (index, (b'name', b'fin2'), b'beta', ((), ))},
1000
 
            set(index.iter_entries_prefix([(b'name', None)])))
 
991
            (('name', 'fin1'), 'data', ([('ref', 'erence')], )),
 
992
            (('name', 'fin2'), 'beta', ([], )),
 
993
            (('ref', 'erence'), 'refdata', ([], ))])
 
994
        self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
995
            (index, ('ref', 'erence'), 'refdata', ((), ))]),
 
996
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
 
997
        self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
998
            (index, ('name', 'fin2'), 'beta', ((), ))]),
 
999
            set(index.iter_entries_prefix([('name', None)])))
1001
1000
 
1002
1001
    # XXX: external_references tests are duplicated in test_index.  We
1003
1002
    # probably should have per_graph_index tests...
1007
1006
 
1008
1007
    def test_external_references_no_results(self):
1009
1008
        index = self.make_index(ref_lists=1, nodes=[
1010
 
            ((b'key',), b'value', ([],))])
 
1009
            (('key',), 'value', ([],))])
1011
1010
        self.assertEqual(set(), index.external_references(0))
1012
1011
 
1013
1012
    def test_external_references_missing_ref(self):
1014
 
        missing_key = (b'missing',)
 
1013
        missing_key = ('missing',)
1015
1014
        index = self.make_index(ref_lists=1, nodes=[
1016
 
            ((b'key',), b'value', ([missing_key],))])
1017
 
        self.assertEqual({missing_key}, index.external_references(0))
 
1015
            (('key',), 'value', ([missing_key],))])
 
1016
        self.assertEqual(set([missing_key]), index.external_references(0))
1018
1017
 
1019
1018
    def test_external_references_multiple_ref_lists(self):
1020
 
        missing_key = (b'missing',)
 
1019
        missing_key = ('missing',)
1021
1020
        index = self.make_index(ref_lists=2, nodes=[
1022
 
            ((b'key',), b'value', ([], [missing_key]))])
 
1021
            (('key',), 'value', ([], [missing_key]))])
1023
1022
        self.assertEqual(set([]), index.external_references(0))
1024
 
        self.assertEqual({missing_key}, index.external_references(1))
 
1023
        self.assertEqual(set([missing_key]), index.external_references(1))
1025
1024
 
1026
1025
    def test_external_references_two_records(self):
1027
1026
        index = self.make_index(ref_lists=1, nodes=[
1028
 
            ((b'key-1',), b'value', ([(b'key-2',)],)),
1029
 
            ((b'key-2',), b'value', ([],)),
 
1027
            (('key-1',), 'value', ([('key-2',)],)),
 
1028
            (('key-2',), 'value', ([],)),
1030
1029
            ])
1031
1030
        self.assertEqual(set([]), index.external_references(0))
1032
1031
 
1033
1032
    def test__find_ancestors_one_page(self):
1034
 
        key1 = (b'key-1',)
1035
 
        key2 = (b'key-2',)
 
1033
        key1 = ('key-1',)
 
1034
        key2 = ('key-2',)
1036
1035
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1037
 
            (key1, b'value', ([key2],)),
1038
 
            (key2, b'value', ([],)),
 
1036
            (key1, 'value', ([key2],)),
 
1037
            (key2, 'value', ([],)),
1039
1038
            ])
1040
1039
        parent_map = {}
1041
1040
        missing_keys = set()
1045
1044
        self.assertEqual(set(), search_keys)
1046
1045
 
1047
1046
    def test__find_ancestors_one_page_w_missing(self):
1048
 
        key1 = (b'key-1',)
1049
 
        key2 = (b'key-2',)
1050
 
        key3 = (b'key-3',)
 
1047
        key1 = ('key-1',)
 
1048
        key2 = ('key-2',)
 
1049
        key3 = ('key-3',)
1051
1050
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1052
 
            (key1, b'value', ([key2],)),
1053
 
            (key2, b'value', ([],)),
 
1051
            (key1, 'value', ([key2],)),
 
1052
            (key2, 'value', ([],)),
1054
1053
            ])
1055
1054
        parent_map = {}
1056
1055
        missing_keys = set()
1059
1058
        self.assertEqual({key2: ()}, parent_map)
1060
1059
        # we know that key3 is missing because we read the page that it would
1061
1060
        # otherwise be on
1062
 
        self.assertEqual({key3}, missing_keys)
 
1061
        self.assertEqual(set([key3]), missing_keys)
1063
1062
        self.assertEqual(set(), search_keys)
1064
1063
 
1065
1064
    def test__find_ancestors_one_parent_missing(self):
1066
 
        key1 = (b'key-1',)
1067
 
        key2 = (b'key-2',)
1068
 
        key3 = (b'key-3',)
 
1065
        key1 = ('key-1',)
 
1066
        key2 = ('key-2',)
 
1067
        key3 = ('key-3',)
1069
1068
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1070
 
            (key1, b'value', ([key2],)),
1071
 
            (key2, b'value', ([key3],)),
 
1069
            (key1, 'value', ([key2],)),
 
1070
            (key2, 'value', ([key3],)),
1072
1071
            ])
1073
1072
        parent_map = {}
1074
1073
        missing_keys = set()
1079
1078
        # all we know is that key3 wasn't present on the page we were reading
1080
1079
        # but if you look, the last key is key2 which comes before key3, so we
1081
1080
        # don't know whether key3 would land on this page or not.
1082
 
        self.assertEqual({key3}, search_keys)
 
1081
        self.assertEqual(set([key3]), search_keys)
1083
1082
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
1084
1083
                                            missing_keys)
1085
1084
        # passing it back in, we are sure it is 'missing'
1086
1085
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1087
 
        self.assertEqual({key3}, missing_keys)
 
1086
        self.assertEqual(set([key3]), missing_keys)
1088
1087
        self.assertEqual(set([]), search_keys)
1089
1088
 
1090
1089
    def test__find_ancestors_dont_search_known(self):
1091
 
        key1 = (b'key-1',)
1092
 
        key2 = (b'key-2',)
1093
 
        key3 = (b'key-3',)
 
1090
        key1 = ('key-1',)
 
1091
        key2 = ('key-2',)
 
1092
        key3 = ('key-3',)
1094
1093
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1095
 
            (key1, b'value', ([key2],)),
1096
 
            (key2, b'value', ([key3],)),
1097
 
            (key3, b'value', ([],)),
 
1094
            (key1, 'value', ([key2],)),
 
1095
            (key2, 'value', ([key3],)),
 
1096
            (key3, 'value', ([],)),
1098
1097
            ])
1099
1098
        # We already know about key2, so we won't try to search for key3
1100
1099
        parent_map = {key2: (key3,)}
1112
1111
        nodes = []
1113
1112
        ref_lists = ((),)
1114
1113
        rev_keys = []
1115
 
        for i in range(400):
1116
 
            rev_id = ('%s-%s-%s' % (email,
 
1114
        for i in xrange(400):
 
1115
            rev_id = '%s-%s-%s' % (email,
1117
1116
                                   osutils.compact_date(start_time + i),
1118
 
                                   osutils.rand_chars(16))).encode('ascii')
 
1117
                                   osutils.rand_chars(16))
1119
1118
            rev_key = (rev_id,)
1120
 
            nodes.append((rev_key, b'value', ref_lists))
 
1119
            nodes.append((rev_key, 'value', ref_lists))
1121
1120
            # We have a ref 'list' of length 1, with a list of parents, with 1
1122
1121
            # parent which is a key
1123
1122
            ref_lists = ((rev_key,),)
1146
1145
                                            missing_keys)
1147
1146
        self.assertEqual([min_l2_key, next_key], sorted(parent_map))
1148
1147
        self.assertEqual(set(), missing_keys)
1149
 
        self.assertEqual({max_l1_key}, search_keys)
 
1148
        self.assertEqual(set([max_l1_key]), search_keys)
1150
1149
        parent_map = {}
1151
1150
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
1152
1151
                                            missing_keys)
1162
1161
                                            missing_keys)
1163
1162
        self.assertEqual(set(), search_keys)
1164
1163
        self.assertEqual({}, parent_map)
1165
 
        self.assertEqual({('one',), ('two',)}, missing_keys)
 
1164
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
1166
1165
 
1167
1166
    def test_supports_unlimited_cache(self):
1168
1167
        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)
1211
1210
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
1212
1211
 
1213
1212
    def test_LeafNode_1_0(self):
1214
 
        node_bytes = (b"type=leaf\n"
1215
 
            b"0000000000000000000000000000000000000000\x00\x00value:0\n"
1216
 
            b"1111111111111111111111111111111111111111\x00\x00value:1\n"
1217
 
            b"2222222222222222222222222222222222222222\x00\x00value:2\n"
1218
 
            b"3333333333333333333333333333333333333333\x00\x00value:3\n"
1219
 
            b"4444444444444444444444444444444444444444\x00\x00value:4\n")
 
1213
        node_bytes = ("type=leaf\n"
 
1214
            "0000000000000000000000000000000000000000\x00\x00value:0\n"
 
1215
            "1111111111111111111111111111111111111111\x00\x00value:1\n"
 
1216
            "2222222222222222222222222222222222222222\x00\x00value:2\n"
 
1217
            "3333333333333333333333333333333333333333\x00\x00value:3\n"
 
1218
            "4444444444444444444444444444444444444444\x00\x00value:4\n")
1220
1219
        node = btree_index._LeafNode(node_bytes, 1, 0)
1221
1220
        # We do direct access, or don't care about order, to leaf nodes most of
1222
1221
        # the time, so a dict is useful:
1223
1222
        self.assertEqual({
1224
 
            (b"0000000000000000000000000000000000000000",): (b"value:0", ()),
1225
 
            (b"1111111111111111111111111111111111111111",): (b"value:1", ()),
1226
 
            (b"2222222222222222222222222222222222222222",): (b"value:2", ()),
1227
 
            (b"3333333333333333333333333333333333333333",): (b"value:3", ()),
1228
 
            (b"4444444444444444444444444444444444444444",): (b"value:4", ()),
 
1223
            ("0000000000000000000000000000000000000000",): ("value:0", ()),
 
1224
            ("1111111111111111111111111111111111111111",): ("value:1", ()),
 
1225
            ("2222222222222222222222222222222222222222",): ("value:2", ()),
 
1226
            ("3333333333333333333333333333333333333333",): ("value:3", ()),
 
1227
            ("4444444444444444444444444444444444444444",): ("value:4", ()),
1229
1228
            }, dict(node.all_items()))
1230
1229
 
1231
1230
    def test_LeafNode_2_2(self):
1232
 
        node_bytes = (b"type=leaf\n"
1233
 
            b"00\x0000\x00\t00\x00ref00\x00value:0\n"
1234
 
            b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
1235
 
            b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
1236
 
            b"11\x0044\x00\t11\x00ref00\x00value:4\n"
1237
 
            b""
 
1231
        node_bytes = ("type=leaf\n"
 
1232
            "00\x0000\x00\t00\x00ref00\x00value:0\n"
 
1233
            "00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
 
1234
            "11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
 
1235
            "11\x0044\x00\t11\x00ref00\x00value:4\n"
 
1236
            ""
1238
1237
            )
1239
1238
        node = btree_index._LeafNode(node_bytes, 2, 2)
1240
1239
        # We do direct access, or don't care about order, to leaf nodes most of
1241
1240
        # the time, so a dict is useful:
1242
1241
        self.assertEqual({
1243
 
            (b'00', b'00'): (b'value:0', ((), ((b'00', b'ref00'),))),
1244
 
            (b'00', b'11'): (b'value:1', (((b'00', b'ref00'),),
1245
 
                ((b'00', b'ref00'), (b'01', b'ref01')))),
1246
 
            (b'11', b'33'): (b'value:3', (((b'11', b'ref22'),),
1247
 
                ((b'11', b'ref22'), (b'11', b'ref22')))),
1248
 
            (b'11', b'44'): (b'value:4', ((), ((b'11', b'ref00'),)))
 
1242
            ('00', '00'): ('value:0', ((), (('00', 'ref00'),))),
 
1243
            ('00', '11'): ('value:1',
 
1244
                ((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01')))),
 
1245
            ('11', '33'): ('value:3',
 
1246
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
 
1247
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1249
1248
            }, dict(node.all_items()))
1250
1249
 
1251
1250
    def test_InternalNode_1(self):
1252
 
        node_bytes = (b"type=internal\n"
1253
 
            b"offset=1\n"
1254
 
            b"0000000000000000000000000000000000000000\n"
1255
 
            b"1111111111111111111111111111111111111111\n"
1256
 
            b"2222222222222222222222222222222222222222\n"
1257
 
            b"3333333333333333333333333333333333333333\n"
1258
 
            b"4444444444444444444444444444444444444444\n"
 
1251
        node_bytes = ("type=internal\n"
 
1252
            "offset=1\n"
 
1253
            "0000000000000000000000000000000000000000\n"
 
1254
            "1111111111111111111111111111111111111111\n"
 
1255
            "2222222222222222222222222222222222222222\n"
 
1256
            "3333333333333333333333333333333333333333\n"
 
1257
            "4444444444444444444444444444444444444444\n"
1259
1258
            )
1260
1259
        node = btree_index._InternalNode(node_bytes)
1261
1260
        # We want to bisect to find the right children from this node, so a
1262
1261
        # vector is most useful.
1263
1262
        self.assertEqual([
1264
 
            (b"0000000000000000000000000000000000000000",),
1265
 
            (b"1111111111111111111111111111111111111111",),
1266
 
            (b"2222222222222222222222222222222222222222",),
1267
 
            (b"3333333333333333333333333333333333333333",),
1268
 
            (b"4444444444444444444444444444444444444444",),
 
1263
            ("0000000000000000000000000000000000000000",),
 
1264
            ("1111111111111111111111111111111111111111",),
 
1265
            ("2222222222222222222222222222222222222222",),
 
1266
            ("3333333333333333333333333333333333333333",),
 
1267
            ("4444444444444444444444444444444444444444",),
1269
1268
            ], node.keys)
1270
1269
        self.assertEqual(1, node.offset)
1271
1270
 
1272
1271
    def test_LeafNode_2_2(self):
1273
 
        node_bytes = (b"type=leaf\n"
1274
 
            b"00\x0000\x00\t00\x00ref00\x00value:0\n"
1275
 
            b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
1276
 
            b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
1277
 
            b"11\x0044\x00\t11\x00ref00\x00value:4\n"
1278
 
            b""
 
1272
        node_bytes = ("type=leaf\n"
 
1273
            "00\x0000\x00\t00\x00ref00\x00value:0\n"
 
1274
            "00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
 
1275
            "11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
 
1276
            "11\x0044\x00\t11\x00ref00\x00value:4\n"
 
1277
            ""
1279
1278
            )
1280
1279
        node = btree_index._LeafNode(node_bytes, 2, 2)
1281
1280
        # We do direct access, or don't care about order, to leaf nodes most of
1282
1281
        # the time, so a dict is useful:
1283
1282
        self.assertEqual({
1284
 
            (b'00', b'00'): (b'value:0', ((), ((b'00', b'ref00'),))),
1285
 
            (b'00', b'11'): (b'value:1', (((b'00', b'ref00'),),
1286
 
                ((b'00', b'ref00'), (b'01', b'ref01')))),
1287
 
            (b'11', b'33'): (b'value:3', (((b'11', b'ref22'),),
1288
 
                ((b'11', b'ref22'), (b'11', b'ref22')))),
1289
 
            (b'11', b'44'): (b'value:4', ((), ((b'11', b'ref00'),)))
 
1283
            ('00', '00'): ('value:0', ((), (('00', 'ref00'),))),
 
1284
            ('00', '11'): ('value:1',
 
1285
                ((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01')))),
 
1286
            ('11', '33'): ('value:3',
 
1287
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
 
1288
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1290
1289
            }, dict(node.all_items()))
1291
1290
 
1292
1291
    def assertFlattened(self, expected, key, value, refs):
1293
1292
        flat_key, flat_line = self.parse_btree._flatten_node(
1294
1293
            (None, key, value, refs), bool(refs))
1295
 
        self.assertEqual(b'\x00'.join(key), flat_key)
 
1294
        self.assertEqual('\x00'.join(key), flat_key)
1296
1295
        self.assertEqual(expected, flat_line)
1297
1296
 
1298
1297
    def test__flatten_node(self):
1299
 
        self.assertFlattened(b'key\0\0value\n', (b'key',), b'value', [])
1300
 
        self.assertFlattened(b'key\0tuple\0\0value str\n',
1301
 
            (b'key', b'tuple'), b'value str', [])
1302
 
        self.assertFlattened(b'key\0tuple\0triple\0\0value str\n',
1303
 
            (b'key', b'tuple', b'triple'), b'value str', [])
1304
 
        self.assertFlattened(b'k\0t\0s\0ref\0value str\n',
1305
 
            (b'k', b't', b's'), b'value str', [[(b'ref',)]])
1306
 
        self.assertFlattened(b'key\0tuple\0ref\0key\0value str\n',
1307
 
            (b'key', b'tuple'), b'value str', [[(b'ref', b'key')]])
1308
 
        self.assertFlattened(b"00\x0000\x00\t00\x00ref00\x00value:0\n",
1309
 
            (b'00', b'00'), b'value:0', ((), ((b'00', b'ref00'),)))
1310
 
        self.assertFlattened(
1311
 
            b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n",
1312
 
            (b'00', b'11'), b'value:1',
1313
 
                (((b'00', b'ref00'),), ((b'00', b'ref00'), (b'01', b'ref01'))))
1314
 
        self.assertFlattened(
1315
 
            b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n",
1316
 
            (b'11', b'33'), b'value:3',
1317
 
                (((b'11', b'ref22'),), ((b'11', b'ref22'), (b'11', b'ref22'))))
1318
 
        self.assertFlattened(
1319
 
            b"11\x0044\x00\t11\x00ref00\x00value:4\n",
1320
 
            (b'11', b'44'), b'value:4', ((), ((b'11', b'ref00'),)))
 
1298
        self.assertFlattened('key\0\0value\n', ('key',), 'value', [])
 
1299
        self.assertFlattened('key\0tuple\0\0value str\n',
 
1300
                             ('key', 'tuple'), 'value str', [])
 
1301
        self.assertFlattened('key\0tuple\0triple\0\0value str\n',
 
1302
                             ('key', 'tuple', 'triple'), 'value str', [])
 
1303
        self.assertFlattened('k\0t\0s\0ref\0value str\n',
 
1304
                             ('k', 't', 's'), 'value str', [[('ref',)]])
 
1305
        self.assertFlattened('key\0tuple\0ref\0key\0value str\n',
 
1306
                             ('key', 'tuple'), 'value str', [[('ref', 'key')]])
 
1307
        self.assertFlattened("00\x0000\x00\t00\x00ref00\x00value:0\n",
 
1308
            ('00', '00'), 'value:0', ((), (('00', 'ref00'),)))
 
1309
        self.assertFlattened(
 
1310
            "00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n",
 
1311
            ('00', '11'), 'value:1',
 
1312
                ((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01'))))
 
1313
        self.assertFlattened(
 
1314
            "11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n",
 
1315
            ('11', '33'), 'value:3',
 
1316
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22'))))
 
1317
        self.assertFlattened(
 
1318
            "11\x0044\x00\t11\x00ref00\x00value:4\n",
 
1319
            ('11', '44'), 'value:4', ((), (('11', 'ref00'),)))
1321
1320
 
1322
1321
 
1323
1322
class TestCompiledBtree(tests.TestCase):
1393
1392
        index._key_count = key_count
1394
1393
        index._row_lengths = row_lengths
1395
1394
        index._compute_row_offsets()
1396
 
        index._root_node = btree_index._InternalNode(b'internal\noffset=0\n')
 
1395
        index._root_node = btree_index._InternalNode('internal\noffset=0\n')
1397
1396
        self.set_cached_offsets(index, cached_offsets)
1398
1397
 
1399
1398
    def make_100_node_index(self):
1457
1456
 
1458
1457
    def test_read_all_from_root(self):
1459
1458
        index = self.make_index(4096*10, 20)
1460
 
        self.assertExpandOffsets(list(range(10)), index, [0])
 
1459
        self.assertExpandOffsets(range(10), index, [0])
1461
1460
 
1462
1461
    def test_read_all_when_cached(self):
1463
1462
        # We've read enough that we can grab all the rest in a single request