/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to breezy/tests/test_btree_index.py

  • Committer: Jelmer Vernooij
  • Date: 2017-06-08 23:30:31 UTC
  • mto: This revision was merged to the branch mainline in revision 6690.
  • Revision ID: jelmer@jelmer.uk-20170608233031-3qavls2o7a1pqllj
Update imports.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/tests/test_btree_index.py
20
20
import pprint
21
21
import zlib
22
22
 
23
 
from ... import (
 
23
from .. import (
24
24
    errors,
25
25
    fifo_cache,
26
26
    lru_cache,
28
28
    tests,
29
29
    transport,
30
30
    )
31
 
from .. import (
 
31
from ..bzr import (
32
32
    btree_index,
33
 
    index as _mod_index,
34
33
    )
35
 
from ...tests import (
 
34
from ..tests import (
36
35
    TestCaseWithTransport,
37
36
    scenarios,
38
37
    )
39
 
from ...tests import (
 
38
from ..tests import (
40
39
    features,
41
40
    )
42
41
 
48
47
    import breezy.bzr._btree_serializer_py as py_module
49
48
    scenarios = [('python', {'parse_btree': py_module})]
50
49
    if compiled_btreeparser_feature.available():
51
 
        scenarios.append(('C',
52
 
                          {'parse_btree': compiled_btreeparser_feature.module}))
 
50
        scenarios.append(('C', 
 
51
            {'parse_btree': compiled_btreeparser_feature.module}))
53
52
    return scenarios
54
53
 
55
54
 
56
55
compiled_btreeparser_feature = features.ModuleAvailableFeature(
57
 
    'breezy.bzr._btree_serializer_pyx')
 
56
    'breezy._btree_serializer_pyx')
58
57
 
59
58
 
60
59
class BTreeTestCase(TestCaseWithTransport):
67
66
 
68
67
    def make_nodes(self, count, key_elements, reference_lists):
69
68
        """Generate count*key_elements sample nodes."""
70
 
        def _pos_to_key(pos, lead=b""):
71
 
            return (lead + (b"%d" % pos) * 40,)
72
69
        keys = []
73
70
        for prefix_pos in range(key_elements):
74
71
            if key_elements - 1:
75
 
                prefix = _pos_to_key(prefix_pos)
 
72
                prefix = (str(prefix_pos) * 40,)
76
73
            else:
77
74
                prefix = ()
78
75
            for pos in range(count):
79
76
                # TODO: This creates odd keys. When count == 100,000, it
80
77
                #       creates a 240 byte key
81
 
                key = prefix + _pos_to_key(pos)
82
 
                value = b"value:%d" % pos
 
78
                key = prefix + (str(pos) * 40,)
 
79
                value = "value:%s" % pos
83
80
                if reference_lists:
84
81
                    # generate some references
85
82
                    refs = []
92
89
                        for ref_pos in range(list_pos + pos % 2):
93
90
                            if pos % 2:
94
91
                                # refer to a nearby key
95
 
                                refs[-1].append(prefix
96
 
                                                + _pos_to_key(pos - 1, b"ref"))
 
92
                                refs[-1].append(prefix + ("ref" + str(pos - 1) * 40,))
97
93
                            else:
98
94
                                # serial of this ref in the ref list
99
 
                                refs[-1].append(prefix
100
 
                                                + _pos_to_key(ref_pos, b"ref"))
 
95
                                refs[-1].append(prefix + ("ref" + str(ref_pos) * 40,))
101
96
                        refs[-1] = tuple(refs[-1])
102
97
                    refs = tuple(refs)
103
98
                else:
118
113
        """
119
114
        if not expected - slop < actual < expected + slop:
120
115
            self.fail("Expected around %d bytes compressed but got %d" %
121
 
                      (expected, actual))
 
116
                (expected, actual))
122
117
 
123
118
 
124
119
class TestBTreeBuilder(BTreeTestCase):
136
131
        content = temp_file.read()
137
132
        del temp_file
138
133
        self.assertEqual(
139
 
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=0\n"
140
 
            b"row_lengths=\n",
 
134
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=0\n"
 
135
            "row_lengths=\n",
141
136
            content)
142
137
 
143
138
    def test_empty_2_1(self):
147
142
        content = temp_file.read()
148
143
        del temp_file
149
144
        self.assertEqual(
150
 
            b"B+Tree Graph Index 2\nnode_ref_lists=1\nkey_elements=2\nlen=0\n"
151
 
            b"row_lengths=\n",
 
145
            "B+Tree Graph Index 2\nnode_ref_lists=1\nkey_elements=2\nlen=0\n"
 
146
            "row_lengths=\n",
152
147
            content)
153
148
 
154
149
    def test_root_leaf_1_0(self):
162
157
        del temp_file
163
158
        self.assertEqual(131, len(content))
164
159
        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",
 
160
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"
 
161
            "row_lengths=1\n",
167
162
            content[:73])
168
163
        node_content = content[73:]
169
164
        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")
 
165
        expected_node = ("type=leaf\n"
 
166
            "0000000000000000000000000000000000000000\x00\x00value:0\n"
 
167
            "1111111111111111111111111111111111111111\x00\x00value:1\n"
 
168
            "2222222222222222222222222222222222222222\x00\x00value:2\n"
 
169
            "3333333333333333333333333333333333333333\x00\x00value:3\n"
 
170
            "4444444444444444444444444444444444444444\x00\x00value:4\n")
176
171
        self.assertEqual(expected_node, node_bytes)
177
172
 
178
173
    def test_root_leaf_2_2(self):
186
181
        del temp_file
187
182
        self.assertEqual(238, len(content))
188
183
        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",
 
184
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"
 
185
            "row_lengths=1\n",
191
186
            content[:74])
192
187
        node_content = content[74:]
193
188
        node_bytes = zlib.decompress(node_content)
194
189
        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""
 
190
            "type=leaf\n"
 
191
            "0000000000000000000000000000000000000000\x000000000000000000000000000000000000000000\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:0\n"
 
192
            "0000000000000000000000000000000000000000\x001111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\r0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:1\n"
 
193
            "0000000000000000000000000000000000000000\x002222222222222222222222222222222222222222\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:2\n"
 
194
            "0000000000000000000000000000000000000000\x003333333333333333333333333333333333333333\x000000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\t0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\r0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\x00value:3\n"
 
195
            "0000000000000000000000000000000000000000\x004444444444444444444444444444444444444444\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:4\n"
 
196
            "1111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:0\n"
 
197
            "1111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\r1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:1\n"
 
198
            "1111111111111111111111111111111111111111\x002222222222222222222222222222222222222222\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:2\n"
 
199
            "1111111111111111111111111111111111111111\x003333333333333333333333333333333333333333\x001111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\t1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\r1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\x00value:3\n"
 
200
            "1111111111111111111111111111111111111111\x004444444444444444444444444444444444444444\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:4\n"
 
201
            ""
207
202
            )
208
203
        self.assertEqual(expected_node, node_bytes)
209
204
 
218
213
        del temp_file
219
214
        self.assertEqualApproxCompressed(9283, len(content))
220
215
        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",
 
216
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
 
217
            "row_lengths=1,2\n",
223
218
            content[:77])
224
219
        root = content[77:4096]
225
220
        leaf1 = content[4096:8192]
226
221
        leaf2 = content[8192:]
227
222
        root_bytes = zlib.decompress(root)
228
223
        expected_root = (
229
 
            b"type=internal\n"
230
 
            b"offset=0\n"
231
 
            ) + (b"307" * 40) + b"\n"
 
224
            "type=internal\n"
 
225
            "offset=0\n"
 
226
            ) + ("307" * 40) + "\n"
232
227
        self.assertEqual(expected_root, root_bytes)
233
228
        # We already know serialisation works for leaves, check key selection:
234
229
        leaf1_bytes = zlib.decompress(leaf1)
252
247
        del temp_file
253
248
        self.assertEqualApproxCompressed(155, len(content))
254
249
        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",
 
250
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
 
251
            "row_lengths=1\n",
257
252
            content[:74])
258
253
        # Check thelast page is well formed
259
254
        leaf2 = content[74:]
274
269
        del temp_file
275
270
        self.assertEqualApproxCompressed(9283, len(content))
276
271
        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",
 
272
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
 
273
            "row_lengths=1,2\n",
279
274
            content[:77])
280
275
        # Check the last page is well formed
281
276
        leaf2 = content[8192:]
305
300
        # Seed the metadata, we're using internal calls now.
306
301
        index.key_count()
307
302
        self.assertEqual(3, len(index._row_lengths),
308
 
                         "Not enough rows: %r" % index._row_lengths)
 
303
            "Not enough rows: %r" % index._row_lengths)
309
304
        self.assertEqual(4, len(index._row_offsets))
310
305
        self.assertEqual(sum(index._row_lengths), index._row_offsets[-1])
311
306
        internal_nodes = index._get_internal_nodes([0, 1, 2])
333
328
        del temp_file
334
329
        self.assertEqualApproxCompressed(12643, len(content))
335
330
        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",
 
331
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
 
332
            "row_lengths=1,3\n",
338
333
            content[:77])
339
334
        root = content[77:4096]
340
335
        leaf1 = content[4096:8192]
342
337
        leaf3 = content[12288:]
343
338
        root_bytes = zlib.decompress(root)
344
339
        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"
 
340
            "type=internal\n"
 
341
            "offset=0\n"
 
342
            + ("0" * 40) + "\x00" + ("91" * 40) + "\n"
 
343
            + ("1" * 40) + "\x00" + ("81" * 40) + "\n"
349
344
            )
350
345
        self.assertEqual(expected_root, root_bytes)
351
346
        # We assume the other leaf nodes have been written correctly - layering
407
402
        # Test that memory and disk are both used for query methods; and that
408
403
        # None is skipped over happily.
409
404
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
410
 
                         list(builder.iter_all_entries()))
 
405
            list(builder.iter_all_entries()))
411
406
        # Two nodes - one memory one disk
412
407
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
413
 
                         set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
408
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
414
409
        self.assertEqual(13, builder.key_count())
415
410
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
416
 
                         set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
411
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
417
412
        builder.add_node(*nodes[13])
418
413
        self.assertEqual(3, len(builder._backing_indices))
419
414
        self.assertEqual(2, builder._backing_indices[0].key_count())
481
476
        # Test that memory and disk are both used for query methods; and that
482
477
        # None is skipped over happily.
483
478
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
484
 
                         list(builder.iter_all_entries()))
 
479
            list(builder.iter_all_entries()))
485
480
        # Two nodes - one memory one disk
486
481
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
487
 
                         set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
482
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
488
483
        self.assertEqual(13, builder.key_count())
489
484
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
490
 
                         set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
485
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
491
486
        builder.add_node(*nodes[13])
492
487
        builder.add_node(*nodes[14])
493
488
        builder.add_node(*nodes[15])
522
517
    def test_spill_index_stress_2_2(self):
523
518
        # test that references and longer keys don't confuse things.
524
519
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2,
525
 
                                           spill_at=2)
 
520
            spill_at=2)
526
521
        nodes = self.make_nodes(16, 2, 2)
527
522
        builder.add_node(*nodes[0])
528
523
        # Test the parts of the index that take up memory are doing so
535
530
        self.assertEqual(1, len(builder._backing_indices))
536
531
        self.assertEqual(2, builder._backing_indices[0].key_count())
537
532
        # now back to memory
538
 
        # Build up the nodes by key dict
539
 
        old = dict(builder._get_nodes_by_key())
 
533
        old = dict(builder._get_nodes_by_key()) #Build up the nodes by key dict
540
534
        builder.add_node(*nodes[2])
541
535
        self.assertEqual(1, len(builder._nodes))
542
536
        self.assertIsNot(None, builder._nodes_by_key)
582
576
        # Test that memory and disk are both used for query methods; and that
583
577
        # None is skipped over happily.
584
578
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
585
 
                         list(builder.iter_all_entries()))
 
579
            list(builder.iter_all_entries()))
586
580
        # Two nodes - one memory one disk
587
581
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
588
 
                         set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
582
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
589
583
        self.assertEqual(13, builder.key_count())
590
584
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
591
 
                         set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
585
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
592
586
        builder.add_node(*nodes[13])
593
587
        self.assertEqual(3, len(builder._backing_indices))
594
588
        self.assertEqual(2, builder._backing_indices[0].key_count())
615
609
        builder.add_node(*nodes[0])
616
610
        builder.add_node(*nodes[1])
617
611
        builder.add_node(*nodes[0])
618
 
        self.assertRaises(_mod_index.BadIndexDuplicateKey, builder.finish)
 
612
        self.assertRaises(errors.BadIndexDuplicateKey, builder.finish)
619
613
 
620
614
 
621
615
class TestBTreeIndex(BTreeTestCase):
622
616
 
623
617
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
624
618
        builder = btree_index.BTreeBuilder(reference_lists=ref_lists,
625
 
                                           key_elements=key_elements)
 
619
            key_elements=key_elements)
626
620
        for key, value, references in nodes:
627
621
            builder.add_node(key, value, references)
628
622
        stream = builder.finish()
641
635
        content = temp_file.read()
642
636
        del temp_file
643
637
        size = len(content)
644
 
        transport.put_bytes('index', (b' ' * offset) + content)
 
638
        transport.put_bytes('index', (' '*offset)+content)
645
639
        return btree_index.BTreeGraphIndex(transport, 'index', size=size,
646
640
                                           offset=offset)
647
641
 
717
711
        self.assertEqual(70, index.key_count())
718
712
        # The entire index should have been read, as it is one page long.
719
713
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
720
 
                         t._activity)
 
714
            t._activity)
721
715
        self.assertEqualApproxCompressed(1173, size)
722
716
 
723
717
    def test_with_offset_no_size(self):
724
718
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
725
719
                                            offset=1234,
726
720
                                            nodes=self.make_nodes(200, 1, 1))
727
 
        index._size = None  # throw away the size info
 
721
        index._size = None # throw away the size info
728
722
        self.assertEqual(200, index.key_count())
729
723
 
730
724
    def test_with_small_offset(self):
740
734
        self.assertEqual(200, index.key_count())
741
735
 
742
736
    def test__read_nodes_no_size_one_page_reads_once(self):
743
 
        self.make_index(nodes=[((b'key',), b'value', ())])
 
737
        self.make_index(nodes=[(('key',), 'value', ())])
744
738
        trans = transport.get_transport_from_url('trace+' + self.get_url())
745
739
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
746
740
        del trans._activity[:]
747
741
        nodes = dict(index._read_nodes([0]))
748
742
        self.assertEqual({0}, set(nodes))
749
743
        node = nodes[0]
750
 
        self.assertEqual([(b'key',)], node.all_keys())
 
744
        self.assertEqual([('key',)], node.all_keys())
751
745
        self.assertEqual([('get', 'index')], trans._activity)
752
746
 
753
747
    def test__read_nodes_no_size_multiple_pages(self):
806
800
        del t._activity[:]
807
801
        self.assertEqual([], t._activity)
808
802
        index.validate()
809
 
        rem = size - 8192  # Number of remaining bytes after second block
 
803
        rem = size - 8192 # Number of remaining bytes after second block
810
804
        # The entire index should have been read linearly.
811
805
        self.assertEqual(
812
806
            [('readv', 'index', [(0, 4096)], False, None),
820
814
        t1 = transport.get_transport_from_url('trace+' + self.get_url(''))
821
815
        t2 = self.get_transport()
822
816
        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))
 
817
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
 
818
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
819
        self.assertTrue(
 
820
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
821
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
822
        self.assertFalse(
 
823
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
824
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
825
        self.assertFalse(
 
826
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) ==
 
827
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
828
        self.assertFalse(
 
829
            btree_index.BTreeGraphIndex(t1, 'index', 10) ==
 
830
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
831
        self.assertFalse(
 
832
            btree_index.BTreeGraphIndex(t1, 'index', None) !=
 
833
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
834
        self.assertFalse(
 
835
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
836
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
837
        self.assertTrue(
 
838
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
839
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
840
        self.assertTrue(
 
841
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) !=
 
842
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
843
        self.assertTrue(
 
844
            btree_index.BTreeGraphIndex(t1, 'index', 10) !=
 
845
            btree_index.BTreeGraphIndex(t1, 'index', 20))
852
846
 
853
847
    def test_key_too_big(self):
854
848
        # the size that matters here is the _compressed_ size of the key, so we can't
855
849
        # 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,
 
850
        bigKey = ''.join(map(repr, range(btree_index._PAGE_SIZE)))
 
851
        self.assertRaises(errors.BadIndexKey,
858
852
                          self.make_index,
859
 
                          nodes=[((bigKey,), b'value', ())])
860
 
 
 
853
                          nodes=[((bigKey,), 'value', ())])
 
854
        
861
855
    def test_iter_all_only_root_no_size(self):
862
 
        self.make_index(nodes=[((b'key',), b'value', ())])
 
856
        self.make_index(nodes=[(('key',), 'value', ())])
863
857
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
864
858
        index = btree_index.BTreeGraphIndex(t, 'index', None)
865
859
        del t._activity[:]
866
 
        self.assertEqual([((b'key',), b'value')],
 
860
        self.assertEqual([(('key',), 'value')],
867
861
                         [x[1:] for x in index.iter_all_entries()])
868
862
        self.assertEqual([('get', 'index')], t._activity)
869
863
 
890
884
            self.assertTrue(node[0] is index)
891
885
            bare_nodes.append(node[1:])
892
886
        self.assertEqual(3, len(index._row_lengths),
893
 
                         "Not enough rows: %r" % index._row_lengths)
 
887
            "Not enough rows: %r" % index._row_lengths)
894
888
        # Should be as long as the nodes we supplied
895
889
        self.assertEqual(20000, len(found_nodes))
896
890
        # Should have the same content
909
903
        # The last page is truncated
910
904
        readv_request[-1] = (readv_request[-1][0], size % page_size)
911
905
        expected = [('readv', 'index', [(0, page_size)], False, None),
912
 
                    ('readv', 'index', readv_request, False, None)]
 
906
             ('readv',  'index', readv_request, False, None)]
913
907
        if expected != t._activity:
914
908
            self.assertEqualDiff(pprint.pformat(expected),
915
909
                                 pprint.pformat(t._activity))
916
910
 
 
911
    def _test_iter_entries_references_resolved(self):
 
912
        index = self.make_index(1, nodes=[
 
913
            (('name', ), 'data', ([('ref', ), ('ref', )], )),
 
914
            (('ref', ), 'refdata', ([], ))])
 
915
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),('ref',)),)),
 
916
            (index, ('ref', ), 'refdata', ((), ))},
 
917
            set(index.iter_entries([('name',), ('ref',)])))
 
918
 
917
919
    def test_iter_entries_references_2_refs_resolved(self):
918
920
        # iterating some entries reads just the pages needed. For now, to
919
921
        # get it working and start measuring, only 4K pages are read.
940
942
        self.assertEqual(nodes[30], bare_nodes[0])
941
943
        # Should have read the root node, then one leaf page:
942
944
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
943
 
                          ('readv', 'index', [(8192, 4096), ], False, None)],
944
 
                         t._activity)
 
945
             ('readv',  'index', [(8192, 4096), ], False, None)],
 
946
            t._activity)
945
947
 
946
948
    def test_iter_key_prefix_1_element_key_None(self):
947
949
        index = self.make_index()
948
 
        self.assertRaises(_mod_index.BadIndexKey, list,
949
 
                          index.iter_entries_prefix([(None, )]))
 
950
        self.assertRaises(errors.BadIndexKey, list,
 
951
            index.iter_entries_prefix([(None, )]))
950
952
 
951
953
    def test_iter_key_prefix_wrong_length(self):
952
954
        index = self.make_index()
953
 
        self.assertRaises(_mod_index.BadIndexKey, list,
954
 
                          index.iter_entries_prefix([(b'foo', None)]))
 
955
        self.assertRaises(errors.BadIndexKey, list,
 
956
            index.iter_entries_prefix([('foo', None)]))
955
957
        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)]))
 
958
        self.assertRaises(errors.BadIndexKey, list,
 
959
            index.iter_entries_prefix([('foo', )]))
 
960
        self.assertRaises(errors.BadIndexKey, list,
 
961
            index.iter_entries_prefix([('foo', None, None)]))
960
962
 
961
963
    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', )])))
 
964
        index = self.make_index( nodes=[
 
965
            (('name', ), 'data', ()),
 
966
            (('ref', ), 'refdata', ())])
 
967
        self.assertEqual({(index, ('name', ), 'data'),
 
968
            (index, ('ref', ), 'refdata')},
 
969
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
968
970
 
969
971
    def test_iter_key_prefix_1_key_element_refs(self):
970
972
        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', )])))
 
973
            (('name', ), 'data', ([('ref', )], )),
 
974
            (('ref', ), 'refdata', ([], ))])
 
975
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
 
976
            (index, ('ref', ), 'refdata', ((), ))},
 
977
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
976
978
 
977
979
    def test_iter_key_prefix_2_key_element_no_refs(self):
978
980
        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)])))
 
981
            (('name', 'fin1'), 'data', ()),
 
982
            (('name', 'fin2'), 'beta', ()),
 
983
            (('ref', 'erence'), 'refdata', ())])
 
984
        self.assertEqual({(index, ('name', 'fin1'), 'data'),
 
985
            (index, ('ref', 'erence'), 'refdata')},
 
986
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
 
987
        self.assertEqual({(index, ('name', 'fin1'), 'data'),
 
988
            (index, ('name', 'fin2'), 'beta')},
 
989
            set(index.iter_entries_prefix([('name', None)])))
989
990
 
990
991
    def test_iter_key_prefix_2_key_element_refs(self):
991
992
        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)])))
 
993
            (('name', 'fin1'), 'data', ([('ref', 'erence')], )),
 
994
            (('name', 'fin2'), 'beta', ([], )),
 
995
            (('ref', 'erence'), 'refdata', ([], ))])
 
996
        self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
997
            (index, ('ref', 'erence'), 'refdata', ((), ))},
 
998
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
 
999
        self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
 
1000
            (index, ('name', 'fin2'), 'beta', ((), ))},
 
1001
            set(index.iter_entries_prefix([('name', None)])))
1004
1002
 
1005
1003
    # XXX: external_references tests are duplicated in test_index.  We
1006
1004
    # probably should have per_graph_index tests...
1010
1008
 
1011
1009
    def test_external_references_no_results(self):
1012
1010
        index = self.make_index(ref_lists=1, nodes=[
1013
 
            ((b'key',), b'value', ([],))])
 
1011
            (('key',), 'value', ([],))])
1014
1012
        self.assertEqual(set(), index.external_references(0))
1015
1013
 
1016
1014
    def test_external_references_missing_ref(self):
1017
 
        missing_key = (b'missing',)
 
1015
        missing_key = ('missing',)
1018
1016
        index = self.make_index(ref_lists=1, nodes=[
1019
 
            ((b'key',), b'value', ([missing_key],))])
 
1017
            (('key',), 'value', ([missing_key],))])
1020
1018
        self.assertEqual({missing_key}, index.external_references(0))
1021
1019
 
1022
1020
    def test_external_references_multiple_ref_lists(self):
1023
 
        missing_key = (b'missing',)
 
1021
        missing_key = ('missing',)
1024
1022
        index = self.make_index(ref_lists=2, nodes=[
1025
 
            ((b'key',), b'value', ([], [missing_key]))])
 
1023
            (('key',), 'value', ([], [missing_key]))])
1026
1024
        self.assertEqual(set([]), index.external_references(0))
1027
1025
        self.assertEqual({missing_key}, index.external_references(1))
1028
1026
 
1029
1027
    def test_external_references_two_records(self):
1030
1028
        index = self.make_index(ref_lists=1, nodes=[
1031
 
            ((b'key-1',), b'value', ([(b'key-2',)],)),
1032
 
            ((b'key-2',), b'value', ([],)),
 
1029
            (('key-1',), 'value', ([('key-2',)],)),
 
1030
            (('key-2',), 'value', ([],)),
1033
1031
            ])
1034
1032
        self.assertEqual(set([]), index.external_references(0))
1035
1033
 
1036
1034
    def test__find_ancestors_one_page(self):
1037
 
        key1 = (b'key-1',)
1038
 
        key2 = (b'key-2',)
 
1035
        key1 = ('key-1',)
 
1036
        key2 = ('key-2',)
1039
1037
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1040
 
            (key1, b'value', ([key2],)),
1041
 
            (key2, b'value', ([],)),
 
1038
            (key1, 'value', ([key2],)),
 
1039
            (key2, 'value', ([],)),
1042
1040
            ])
1043
1041
        parent_map = {}
1044
1042
        missing_keys = set()
1045
 
        search_keys = index._find_ancestors(
1046
 
            [key1], 0, parent_map, missing_keys)
 
1043
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
1047
1044
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
1048
1045
        self.assertEqual(set(), missing_keys)
1049
1046
        self.assertEqual(set(), search_keys)
1050
1047
 
1051
1048
    def test__find_ancestors_one_page_w_missing(self):
1052
 
        key1 = (b'key-1',)
1053
 
        key2 = (b'key-2',)
1054
 
        key3 = (b'key-3',)
 
1049
        key1 = ('key-1',)
 
1050
        key2 = ('key-2',)
 
1051
        key3 = ('key-3',)
1055
1052
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1056
 
            (key1, b'value', ([key2],)),
1057
 
            (key2, b'value', ([],)),
 
1053
            (key1, 'value', ([key2],)),
 
1054
            (key2, 'value', ([],)),
1058
1055
            ])
1059
1056
        parent_map = {}
1060
1057
        missing_keys = set()
1067
1064
        self.assertEqual(set(), search_keys)
1068
1065
 
1069
1066
    def test__find_ancestors_one_parent_missing(self):
1070
 
        key1 = (b'key-1',)
1071
 
        key2 = (b'key-2',)
1072
 
        key3 = (b'key-3',)
 
1067
        key1 = ('key-1',)
 
1068
        key2 = ('key-2',)
 
1069
        key3 = ('key-3',)
1073
1070
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1074
 
            (key1, b'value', ([key2],)),
1075
 
            (key2, b'value', ([key3],)),
 
1071
            (key1, 'value', ([key2],)),
 
1072
            (key2, 'value', ([key3],)),
1076
1073
            ])
1077
1074
        parent_map = {}
1078
1075
        missing_keys = set()
1092
1089
        self.assertEqual(set([]), search_keys)
1093
1090
 
1094
1091
    def test__find_ancestors_dont_search_known(self):
1095
 
        key1 = (b'key-1',)
1096
 
        key2 = (b'key-2',)
1097
 
        key3 = (b'key-3',)
 
1092
        key1 = ('key-1',)
 
1093
        key2 = ('key-2',)
 
1094
        key3 = ('key-3',)
1098
1095
        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', ([],)),
 
1096
            (key1, 'value', ([key2],)),
 
1097
            (key2, 'value', ([key3],)),
 
1098
            (key3, 'value', ([],)),
1102
1099
            ])
1103
1100
        # We already know about key2, so we won't try to search for key3
1104
1101
        parent_map = {key2: (key3,)}
1117
1114
        ref_lists = ((),)
1118
1115
        rev_keys = []
1119
1116
        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')
 
1117
            rev_id = '%s-%s-%s' % (email,
 
1118
                                   osutils.compact_date(start_time + i),
 
1119
                                   osutils.rand_chars(16))
1123
1120
            rev_key = (rev_id,)
1124
 
            nodes.append((rev_key, b'value', ref_lists))
 
1121
            nodes.append((rev_key, 'value', ref_lists))
1125
1122
            # We have a ref 'list' of length 1, with a list of parents, with 1
1126
1123
            # parent which is a key
1127
1124
            ref_lists = ((rev_key,),)
1140
1137
        # Now, whatever key we select that would fall on the second page,
1141
1138
        # should give us all the parents until the page break
1142
1139
        key_idx = rev_keys.index(min_l2_key)
1143
 
        next_key = rev_keys[key_idx + 1]
 
1140
        next_key = rev_keys[key_idx+1]
1144
1141
        # So now when we get the parent map, we should get the key we are
1145
1142
        # looking for, min_l2_key, and then a reference to go look for the
1146
1143
        # parent of that key
1215
1212
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
1216
1213
 
1217
1214
    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")
 
1215
        node_bytes = ("type=leaf\n"
 
1216
            "0000000000000000000000000000000000000000\x00\x00value:0\n"
 
1217
            "1111111111111111111111111111111111111111\x00\x00value:1\n"
 
1218
            "2222222222222222222222222222222222222222\x00\x00value:2\n"
 
1219
            "3333333333333333333333333333333333333333\x00\x00value:3\n"
 
1220
            "4444444444444444444444444444444444444444\x00\x00value:4\n")
1224
1221
        node = btree_index._LeafNode(node_bytes, 1, 0)
1225
1222
        # We do direct access, or don't care about order, to leaf nodes most of
1226
1223
        # the time, so a dict is useful:
1227
1224
        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", ()),
 
1225
            ("0000000000000000000000000000000000000000",): ("value:0", ()),
 
1226
            ("1111111111111111111111111111111111111111",): ("value:1", ()),
 
1227
            ("2222222222222222222222222222222222222222",): ("value:2", ()),
 
1228
            ("3333333333333333333333333333333333333333",): ("value:3", ()),
 
1229
            ("4444444444444444444444444444444444444444",): ("value:4", ()),
1233
1230
            }, dict(node.all_items()))
1234
1231
 
1235
1232
    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
 
                      )
 
1233
        node_bytes = ("type=leaf\n"
 
1234
            "00\x0000\x00\t00\x00ref00\x00value:0\n"
 
1235
            "00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
 
1236
            "11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
 
1237
            "11\x0044\x00\t11\x00ref00\x00value:4\n"
 
1238
            ""
 
1239
            )
1243
1240
        node = btree_index._LeafNode(node_bytes, 2, 2)
1244
1241
        # We do direct access, or don't care about order, to leaf nodes most of
1245
1242
        # the time, so a dict is useful:
1246
1243
        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'),)))
 
1244
            ('00', '00'): ('value:0', ((), (('00', 'ref00'),))),
 
1245
            ('00', '11'): ('value:1',
 
1246
                ((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01')))),
 
1247
            ('11', '33'): ('value:3',
 
1248
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
 
1249
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1253
1250
            }, dict(node.all_items()))
1254
1251
 
1255
1252
    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
 
                      )
 
1253
        node_bytes = ("type=internal\n"
 
1254
            "offset=1\n"
 
1255
            "0000000000000000000000000000000000000000\n"
 
1256
            "1111111111111111111111111111111111111111\n"
 
1257
            "2222222222222222222222222222222222222222\n"
 
1258
            "3333333333333333333333333333333333333333\n"
 
1259
            "4444444444444444444444444444444444444444\n"
 
1260
            )
1264
1261
        node = btree_index._InternalNode(node_bytes)
1265
1262
        # We want to bisect to find the right children from this node, so a
1266
1263
        # vector is most useful.
1267
1264
        self.assertEqual([
1268
 
            (b"0000000000000000000000000000000000000000",),
1269
 
            (b"1111111111111111111111111111111111111111",),
1270
 
            (b"2222222222222222222222222222222222222222",),
1271
 
            (b"3333333333333333333333333333333333333333",),
1272
 
            (b"4444444444444444444444444444444444444444",),
 
1265
            ("0000000000000000000000000000000000000000",),
 
1266
            ("1111111111111111111111111111111111111111",),
 
1267
            ("2222222222222222222222222222222222222222",),
 
1268
            ("3333333333333333333333333333333333333333",),
 
1269
            ("4444444444444444444444444444444444444444",),
1273
1270
            ], node.keys)
1274
1271
        self.assertEqual(1, node.offset)
1275
1272
 
1276
1273
    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
 
                      )
 
1274
        node_bytes = ("type=leaf\n"
 
1275
            "00\x0000\x00\t00\x00ref00\x00value:0\n"
 
1276
            "00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
 
1277
            "11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
 
1278
            "11\x0044\x00\t11\x00ref00\x00value:4\n"
 
1279
            ""
 
1280
            )
1284
1281
        node = btree_index._LeafNode(node_bytes, 2, 2)
1285
1282
        # We do direct access, or don't care about order, to leaf nodes most of
1286
1283
        # the time, so a dict is useful:
1287
1284
        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'),)))
 
1285
            ('00', '00'): ('value:0', ((), (('00', 'ref00'),))),
 
1286
            ('00', '11'): ('value:1',
 
1287
                ((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01')))),
 
1288
            ('11', '33'): ('value:3',
 
1289
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
 
1290
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1294
1291
            }, dict(node.all_items()))
1295
1292
 
1296
1293
    def assertFlattened(self, expected, key, value, refs):
1297
1294
        flat_key, flat_line = self.parse_btree._flatten_node(
1298
1295
            (None, key, value, refs), bool(refs))
1299
 
        self.assertEqual(b'\x00'.join(key), flat_key)
 
1296
        self.assertEqual('\x00'.join(key), flat_key)
1300
1297
        self.assertEqual(expected, flat_line)
1301
1298
 
1302
1299
    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'),)))
 
1300
        self.assertFlattened('key\0\0value\n', ('key',), 'value', [])
 
1301
        self.assertFlattened('key\0tuple\0\0value str\n',
 
1302
                             ('key', 'tuple'), 'value str', [])
 
1303
        self.assertFlattened('key\0tuple\0triple\0\0value str\n',
 
1304
                             ('key', 'tuple', 'triple'), 'value str', [])
 
1305
        self.assertFlattened('k\0t\0s\0ref\0value str\n',
 
1306
                             ('k', 't', 's'), 'value str', [[('ref',)]])
 
1307
        self.assertFlattened('key\0tuple\0ref\0key\0value str\n',
 
1308
                             ('key', 'tuple'), 'value str', [[('ref', 'key')]])
 
1309
        self.assertFlattened("00\x0000\x00\t00\x00ref00\x00value:0\n",
 
1310
            ('00', '00'), 'value:0', ((), (('00', 'ref00'),)))
 
1311
        self.assertFlattened(
 
1312
            "00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n",
 
1313
            ('00', '11'), 'value:1',
 
1314
                ((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01'))))
 
1315
        self.assertFlattened(
 
1316
            "11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n",
 
1317
            ('11', '33'), 'value:3',
 
1318
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22'))))
 
1319
        self.assertFlattened(
 
1320
            "11\x0044\x00\t11\x00ref00\x00value:4\n",
 
1321
            ('11', '44'), 'value:4', ((), (('11', 'ref00'),)))
1325
1322
 
1326
1323
 
1327
1324
class TestCompiledBtree(tests.TestCase):
1337
1334
    def assertMultiBisectRight(self, offsets, search_keys, fixed_keys):
1338
1335
        self.assertEqual(offsets,
1339
1336
                         btree_index.BTreeGraphIndex._multi_bisect_right(
1340
 
                             search_keys, fixed_keys))
 
1337
                            search_keys, fixed_keys))
1341
1338
 
1342
1339
    def test_after(self):
1343
1340
        self.assertMultiBisectRight([(1, ['b'])], ['b'], ['a'])
1351
1348
 
1352
1349
    def test_exact(self):
1353
1350
        self.assertMultiBisectRight([(1, ['a'])], ['a'], ['a'])
1354
 
        self.assertMultiBisectRight(
1355
 
            [(1, ['a']), (2, ['b'])], ['a', 'b'], ['a', 'b'])
 
1351
        self.assertMultiBisectRight([(1, ['a']), (2, ['b'])], ['a', 'b'], ['a', 'b'])
1356
1352
        self.assertMultiBisectRight([(1, ['a']), (3, ['c'])],
1357
1353
                                    ['a', 'c'], ['a', 'b', 'c'])
1358
1354
 
1398
1394
        index._key_count = key_count
1399
1395
        index._row_lengths = row_lengths
1400
1396
        index._compute_row_offsets()
1401
 
        index._root_node = btree_index._InternalNode(b'internal\noffset=0\n')
 
1397
        index._root_node = btree_index._InternalNode('internal\noffset=0\n')
1402
1398
        self.set_cached_offsets(index, cached_offsets)
1403
1399
 
1404
1400
    def make_100_node_index(self):
1405
 
        index = self.make_index(4096 * 100, 6)
 
1401
        index = self.make_index(4096*100, 6)
1406
1402
        # Consider we've already made a single request at the middle
1407
1403
        self.prepare_index(index, node_ref_lists=0, key_length=1,
1408
1404
                           key_count=1000, row_lengths=[1, 99],
1410
1406
        return index
1411
1407
 
1412
1408
    def make_1000_node_index(self):
1413
 
        index = self.make_index(4096 * 1000, 6)
 
1409
        index = self.make_index(4096*1000, 6)
1414
1410
        # Pretend we've already made a single request in the middle
1415
1411
        self.prepare_index(index, node_ref_lists=0, key_length=1,
1416
1412
                           key_count=90000, row_lengths=[1, 9, 990],
1438
1434
        self.assertNumPages(1, index, 4096)
1439
1435
        self.assertNumPages(2, index, 4097)
1440
1436
        self.assertNumPages(2, index, 8192)
1441
 
        self.assertNumPages(76, index, 4096 * 75 + 10)
 
1437
        self.assertNumPages(76, index, 4096*75 + 10)
1442
1438
 
1443
1439
    def test__find_layer_start_and_stop(self):
1444
1440
        index = self.make_1000_node_index()
1456
1452
        self.assertExpandOffsets([1, 4, 9], index, [1, 4, 9])
1457
1453
 
1458
1454
    def test_more_than_recommended(self):
1459
 
        index = self.make_index(4096 * 100, 2)
 
1455
        index = self.make_index(4096*100, 2)
1460
1456
        self.assertExpandOffsets([1, 10], index, [1, 10])
1461
1457
        self.assertExpandOffsets([1, 10, 20], index, [1, 10, 20])
1462
1458
 
1463
1459
    def test_read_all_from_root(self):
1464
 
        index = self.make_index(4096 * 10, 20)
 
1460
        index = self.make_index(4096*10, 20)
1465
1461
        self.assertExpandOffsets(list(range(10)), index, [0])
1466
1462
 
1467
1463
    def test_read_all_when_cached(self):
1468
1464
        # We've read enough that we can grab all the rest in a single request
1469
 
        index = self.make_index(4096 * 10, 5)
 
1465
        index = self.make_index(4096*10, 5)
1470
1466
        self.prepare_index(index, node_ref_lists=0, key_length=1,
1471
1467
                           key_count=1000, row_lengths=[1, 9],
1472
1468
                           cached_offsets=[0, 1, 2, 5, 6])
1476
1472
        self.assertExpandOffsets([3, 4, 7, 8, 9], index, [9])
1477
1473
 
1478
1474
    def test_no_root_node(self):
1479
 
        index = self.make_index(4096 * 10, 5)
 
1475
        index = self.make_index(4096*10, 5)
1480
1476
        self.assertExpandOffsets([0], index, [0])
1481
1477
 
1482
1478
    def test_include_neighbors(self):
1492
1488
        # Requesting many nodes will expand all locations equally
1493
1489
        self.assertExpandOffsets([1, 2, 3, 80, 81, 82], index, [2, 81])
1494
1490
        self.assertExpandOffsets([1, 2, 3, 9, 10, 11, 80, 81, 82], index,
1495
 
                                 [2, 10, 81])
 
1491
                               [2, 10, 81])
1496
1492
 
1497
1493
    def test_stop_at_cached(self):
1498
1494
        index = self.make_100_node_index()