/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 brzlib/tests/test_btree_index.py

  • Committer: Jelmer Vernooij
  • Date: 2017-05-21 12:41:27 UTC
  • mto: This revision was merged to the branch mainline in revision 6623.
  • Revision ID: jelmer@jelmer.uk-20170521124127-iv8etg0vwymyai6y
s/bzr/brz/ in apport config.

Show diffs side-by-side

added added

removed removed

Lines of Context:
brzlib/tests/test_btree_index.py
20
20
import pprint
21
21
import zlib
22
22
 
23
 
from .. import (
 
23
from brzlib 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 brzlib.tests import (
36
33
    TestCaseWithTransport,
37
34
    scenarios,
38
35
    )
39
 
from ..tests import (
 
36
from brzlib.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 brzlib._btree_serializer_py as py_module
49
46
    scenarios = [('python', {'parse_btree': py_module})]
50
47
    if compiled_btreeparser_feature.available():
51
 
        scenarios.append(('C',
52
 
                          {'parse_btree': compiled_btreeparser_feature.module}))
 
48
        scenarios.append(('C', 
 
49
            {'parse_btree': compiled_btreeparser_feature.module}))
53
50
    return scenarios
54
51
 
55
52
 
56
53
compiled_btreeparser_feature = features.ModuleAvailableFeature(
57
 
    'breezy.bzr._btree_serializer_pyx')
 
54
    'brzlib._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
96
 
                                                + _pos_to_key(pos - 1, b"ref"))
 
90
                                refs[-1].append(prefix + ("ref" + str(pos - 1) * 40,))
97
91
                            else:
98
92
                                # serial of this ref in the ref list
99
 
                                refs[-1].append(prefix
100
 
                                                + _pos_to_key(ref_pos, b"ref"))
 
93
                                refs[-1].append(prefix + ("ref" + str(ref_pos) * 40,))
101
94
                        refs[-1] = tuple(refs[-1])
102
95
                    refs = tuple(refs)
103
96
                else:
118
111
        """
119
112
        if not expected - slop < actual < expected + slop:
120
113
            self.fail("Expected around %d bytes compressed but got %d" %
121
 
                      (expected, actual))
 
114
                (expected, actual))
122
115
 
123
116
 
124
117
class TestBTreeBuilder(BTreeTestCase):
136
129
        content = temp_file.read()
137
130
        del temp_file
138
131
        self.assertEqual(
139
 
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=0\n"
140
 
            b"row_lengths=\n",
 
132
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=0\n"
 
133
            "row_lengths=\n",
141
134
            content)
142
135
 
143
136
    def test_empty_2_1(self):
147
140
        content = temp_file.read()
148
141
        del temp_file
149
142
        self.assertEqual(
150
 
            b"B+Tree Graph Index 2\nnode_ref_lists=1\nkey_elements=2\nlen=0\n"
151
 
            b"row_lengths=\n",
 
143
            "B+Tree Graph Index 2\nnode_ref_lists=1\nkey_elements=2\nlen=0\n"
 
144
            "row_lengths=\n",
152
145
            content)
153
146
 
154
147
    def test_root_leaf_1_0(self):
162
155
        del temp_file
163
156
        self.assertEqual(131, len(content))
164
157
        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",
 
158
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"
 
159
            "row_lengths=1\n",
167
160
            content[:73])
168
161
        node_content = content[73:]
169
162
        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")
 
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")
176
169
        self.assertEqual(expected_node, node_bytes)
177
170
 
178
171
    def test_root_leaf_2_2(self):
186
179
        del temp_file
187
180
        self.assertEqual(238, len(content))
188
181
        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",
 
182
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"
 
183
            "row_lengths=1\n",
191
184
            content[:74])
192
185
        node_content = content[74:]
193
186
        node_bytes = zlib.decompress(node_content)
194
187
        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""
 
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
            ""
207
200
            )
208
201
        self.assertEqual(expected_node, node_bytes)
209
202
 
218
211
        del temp_file
219
212
        self.assertEqualApproxCompressed(9283, len(content))
220
213
        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",
 
214
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
 
215
            "row_lengths=1,2\n",
223
216
            content[:77])
224
217
        root = content[77:4096]
225
218
        leaf1 = content[4096:8192]
226
219
        leaf2 = content[8192:]
227
220
        root_bytes = zlib.decompress(root)
228
221
        expected_root = (
229
 
            b"type=internal\n"
230
 
            b"offset=0\n"
231
 
            ) + (b"307" * 40) + b"\n"
 
222
            "type=internal\n"
 
223
            "offset=0\n"
 
224
            ) + ("307" * 40) + "\n"
232
225
        self.assertEqual(expected_root, root_bytes)
233
226
        # We already know serialisation works for leaves, check key selection:
234
227
        leaf1_bytes = zlib.decompress(leaf1)
252
245
        del temp_file
253
246
        self.assertEqualApproxCompressed(155, len(content))
254
247
        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",
 
248
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
 
249
            "row_lengths=1\n",
257
250
            content[:74])
258
251
        # Check thelast page is well formed
259
252
        leaf2 = content[74:]
274
267
        del temp_file
275
268
        self.assertEqualApproxCompressed(9283, len(content))
276
269
        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",
 
270
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
 
271
            "row_lengths=1,2\n",
279
272
            content[:77])
280
273
        # Check the last page is well formed
281
274
        leaf2 = content[8192:]
305
298
        # Seed the metadata, we're using internal calls now.
306
299
        index.key_count()
307
300
        self.assertEqual(3, len(index._row_lengths),
308
 
                         "Not enough rows: %r" % index._row_lengths)
 
301
            "Not enough rows: %r" % index._row_lengths)
309
302
        self.assertEqual(4, len(index._row_offsets))
310
303
        self.assertEqual(sum(index._row_lengths), index._row_offsets[-1])
311
304
        internal_nodes = index._get_internal_nodes([0, 1, 2])
333
326
        del temp_file
334
327
        self.assertEqualApproxCompressed(12643, len(content))
335
328
        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",
 
329
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
 
330
            "row_lengths=1,3\n",
338
331
            content[:77])
339
332
        root = content[77:4096]
340
333
        leaf1 = content[4096:8192]
342
335
        leaf3 = content[12288:]
343
336
        root_bytes = zlib.decompress(root)
344
337
        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"
 
338
            "type=internal\n"
 
339
            "offset=0\n"
 
340
            + ("0" * 40) + "\x00" + ("91" * 40) + "\n"
 
341
            + ("1" * 40) + "\x00" + ("81" * 40) + "\n"
349
342
            )
350
343
        self.assertEqual(expected_root, root_bytes)
351
344
        # We assume the other leaf nodes have been written correctly - layering
407
400
        # Test that memory and disk are both used for query methods; and that
408
401
        # None is skipped over happily.
409
402
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
410
 
                         list(builder.iter_all_entries()))
 
403
            list(builder.iter_all_entries()))
411
404
        # Two nodes - one memory one disk
412
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
413
 
                         set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
405
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
406
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
414
407
        self.assertEqual(13, builder.key_count())
415
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
416
 
                         set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
408
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
409
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
417
410
        builder.add_node(*nodes[13])
418
411
        self.assertEqual(3, len(builder._backing_indices))
419
412
        self.assertEqual(2, builder._backing_indices[0].key_count())
481
474
        # Test that memory and disk are both used for query methods; and that
482
475
        # None is skipped over happily.
483
476
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
484
 
                         list(builder.iter_all_entries()))
 
477
            list(builder.iter_all_entries()))
485
478
        # Two nodes - one memory one disk
486
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
487
 
                         set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
479
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
480
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
488
481
        self.assertEqual(13, builder.key_count())
489
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
490
 
                         set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
482
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
483
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
491
484
        builder.add_node(*nodes[13])
492
485
        builder.add_node(*nodes[14])
493
486
        builder.add_node(*nodes[15])
522
515
    def test_spill_index_stress_2_2(self):
523
516
        # test that references and longer keys don't confuse things.
524
517
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2,
525
 
                                           spill_at=2)
 
518
            spill_at=2)
526
519
        nodes = self.make_nodes(16, 2, 2)
527
520
        builder.add_node(*nodes[0])
528
521
        # Test the parts of the index that take up memory are doing so
535
528
        self.assertEqual(1, len(builder._backing_indices))
536
529
        self.assertEqual(2, builder._backing_indices[0].key_count())
537
530
        # now back to memory
538
 
        # Build up the nodes by key dict
539
 
        old = dict(builder._get_nodes_by_key())
 
531
        old = dict(builder._get_nodes_by_key()) #Build up the nodes by key dict
540
532
        builder.add_node(*nodes[2])
541
533
        self.assertEqual(1, len(builder._nodes))
542
534
        self.assertIsNot(None, builder._nodes_by_key)
582
574
        # Test that memory and disk are both used for query methods; and that
583
575
        # None is skipped over happily.
584
576
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
585
 
                         list(builder.iter_all_entries()))
 
577
            list(builder.iter_all_entries()))
586
578
        # Two nodes - one memory one disk
587
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
588
 
                         set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
579
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
580
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
589
581
        self.assertEqual(13, builder.key_count())
590
 
        self.assertEqual({(builder,) + node for node in nodes[11:13]},
591
 
                         set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
582
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
583
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
592
584
        builder.add_node(*nodes[13])
593
585
        self.assertEqual(3, len(builder._backing_indices))
594
586
        self.assertEqual(2, builder._backing_indices[0].key_count())
615
607
        builder.add_node(*nodes[0])
616
608
        builder.add_node(*nodes[1])
617
609
        builder.add_node(*nodes[0])
618
 
        self.assertRaises(_mod_index.BadIndexDuplicateKey, builder.finish)
 
610
        self.assertRaises(errors.BadIndexDuplicateKey, builder.finish)
619
611
 
620
612
 
621
613
class TestBTreeIndex(BTreeTestCase):
622
614
 
623
615
    def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
624
616
        builder = btree_index.BTreeBuilder(reference_lists=ref_lists,
625
 
                                           key_elements=key_elements)
 
617
            key_elements=key_elements)
626
618
        for key, value, references in nodes:
627
619
            builder.add_node(key, value, references)
628
620
        stream = builder.finish()
641
633
        content = temp_file.read()
642
634
        del temp_file
643
635
        size = len(content)
644
 
        transport.put_bytes('index', (b' ' * offset) + content)
 
636
        transport.put_bytes('index', (' '*offset)+content)
645
637
        return btree_index.BTreeGraphIndex(transport, 'index', size=size,
646
638
                                           offset=offset)
647
639
 
651
643
        self.assertEqual(1, len(list(index.iter_entries([nodes[30][0]]))))
652
644
        self.assertEqual([1, 4], index._row_lengths)
653
645
        self.assertIsNot(None, index._root_node)
654
 
        internal_node_pre_clear = set(index._internal_node_cache)
 
646
        internal_node_pre_clear = index._internal_node_cache.keys()
655
647
        self.assertTrue(len(index._leaf_node_cache) > 0)
656
648
        index.clear_cache()
657
649
        # We don't touch _root_node or _internal_node_cache, both should be
663
655
        #       becuase without a 3-level index, we don't have any internal
664
656
        #       nodes cached.
665
657
        self.assertEqual(internal_node_pre_clear,
666
 
                         set(index._internal_node_cache))
 
658
                         index._internal_node_cache.keys())
667
659
        self.assertEqual(0, len(index._leaf_node_cache))
668
660
 
669
661
    def test_trivial_constructor(self):
717
709
        self.assertEqual(70, index.key_count())
718
710
        # The entire index should have been read, as it is one page long.
719
711
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
720
 
                         t._activity)
 
712
            t._activity)
721
713
        self.assertEqualApproxCompressed(1173, size)
722
714
 
723
715
    def test_with_offset_no_size(self):
724
716
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
725
717
                                            offset=1234,
726
718
                                            nodes=self.make_nodes(200, 1, 1))
727
 
        index._size = None  # throw away the size info
 
719
        index._size = None # throw away the size info
728
720
        self.assertEqual(200, index.key_count())
729
721
 
730
722
    def test_with_small_offset(self):
740
732
        self.assertEqual(200, index.key_count())
741
733
 
742
734
    def test__read_nodes_no_size_one_page_reads_once(self):
743
 
        self.make_index(nodes=[((b'key',), b'value', ())])
 
735
        self.make_index(nodes=[(('key',), 'value', ())])
744
736
        trans = transport.get_transport_from_url('trace+' + self.get_url())
745
737
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
746
738
        del trans._activity[:]
747
739
        nodes = dict(index._read_nodes([0]))
748
 
        self.assertEqual({0}, set(nodes))
 
740
        self.assertEqual([0], nodes.keys())
749
741
        node = nodes[0]
750
 
        self.assertEqual([(b'key',)], node.all_keys())
 
742
        self.assertEqual([('key',)], node.all_keys())
751
743
        self.assertEqual([('get', 'index')], trans._activity)
752
744
 
753
745
    def test__read_nodes_no_size_multiple_pages(self):
759
751
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
760
752
        del trans._activity[:]
761
753
        nodes = dict(index._read_nodes([0]))
762
 
        self.assertEqual(list(range(num_pages)), sorted(nodes))
 
754
        self.assertEqual(range(num_pages), nodes.keys())
763
755
 
764
756
    def test_2_levels_key_count_2_2(self):
765
757
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
806
798
        del t._activity[:]
807
799
        self.assertEqual([], t._activity)
808
800
        index.validate()
809
 
        rem = size - 8192  # Number of remaining bytes after second block
 
801
        rem = size - 8192 # Number of remaining bytes after second block
810
802
        # The entire index should have been read linearly.
811
803
        self.assertEqual(
812
804
            [('readv', 'index', [(0, 4096)], False, None),
820
812
        t1 = transport.get_transport_from_url('trace+' + self.get_url(''))
821
813
        t2 = self.get_transport()
822
814
        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))
 
815
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
 
816
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
817
        self.assertTrue(
 
818
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
819
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
820
        self.assertFalse(
 
821
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
822
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
823
        self.assertFalse(
 
824
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) ==
 
825
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
826
        self.assertFalse(
 
827
            btree_index.BTreeGraphIndex(t1, 'index', 10) ==
 
828
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
829
        self.assertFalse(
 
830
            btree_index.BTreeGraphIndex(t1, 'index', None) !=
 
831
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
832
        self.assertFalse(
 
833
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
834
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
835
        self.assertTrue(
 
836
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
837
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
838
        self.assertTrue(
 
839
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) !=
 
840
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
841
        self.assertTrue(
 
842
            btree_index.BTreeGraphIndex(t1, 'index', 10) !=
 
843
            btree_index.BTreeGraphIndex(t1, 'index', 20))
852
844
 
853
845
    def test_key_too_big(self):
854
846
        # the size that matters here is the _compressed_ size of the key, so we can't
855
847
        # 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,
 
848
        bigKey = ''.join(map(repr, xrange(btree_index._PAGE_SIZE)))
 
849
        self.assertRaises(errors.BadIndexKey,
858
850
                          self.make_index,
859
 
                          nodes=[((bigKey,), b'value', ())])
860
 
 
 
851
                          nodes=[((bigKey,), 'value', ())])
 
852
        
861
853
    def test_iter_all_only_root_no_size(self):
862
 
        self.make_index(nodes=[((b'key',), b'value', ())])
 
854
        self.make_index(nodes=[(('key',), 'value', ())])
863
855
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
864
856
        index = btree_index.BTreeGraphIndex(t, 'index', None)
865
857
        del t._activity[:]
866
 
        self.assertEqual([((b'key',), b'value')],
 
858
        self.assertEqual([(('key',), 'value')],
867
859
                         [x[1:] for x in index.iter_all_entries()])
868
860
        self.assertEqual([('get', 'index')], t._activity)
869
861
 
890
882
            self.assertTrue(node[0] is index)
891
883
            bare_nodes.append(node[1:])
892
884
        self.assertEqual(3, len(index._row_lengths),
893
 
                         "Not enough rows: %r" % index._row_lengths)
 
885
            "Not enough rows: %r" % index._row_lengths)
894
886
        # Should be as long as the nodes we supplied
895
887
        self.assertEqual(20000, len(found_nodes))
896
888
        # Should have the same content
909
901
        # The last page is truncated
910
902
        readv_request[-1] = (readv_request[-1][0], size % page_size)
911
903
        expected = [('readv', 'index', [(0, page_size)], False, None),
912
 
                    ('readv', 'index', readv_request, False, None)]
 
904
             ('readv',  'index', readv_request, False, None)]
913
905
        if expected != t._activity:
914
906
            self.assertEqualDiff(pprint.pformat(expected),
915
907
                                 pprint.pformat(t._activity))
916
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
 
917
917
    def test_iter_entries_references_2_refs_resolved(self):
918
918
        # iterating some entries reads just the pages needed. For now, to
919
919
        # get it working and start measuring, only 4K pages are read.
940
940
        self.assertEqual(nodes[30], bare_nodes[0])
941
941
        # Should have read the root node, then one leaf page:
942
942
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
943
 
                          ('readv', 'index', [(8192, 4096), ], False, None)],
944
 
                         t._activity)
 
943
             ('readv',  'index', [(8192, 4096), ], False, None)],
 
944
            t._activity)
945
945
 
946
946
    def test_iter_key_prefix_1_element_key_None(self):
947
947
        index = self.make_index()
948
 
        self.assertRaises(_mod_index.BadIndexKey, list,
949
 
                          index.iter_entries_prefix([(None, )]))
 
948
        self.assertRaises(errors.BadIndexKey, list,
 
949
            index.iter_entries_prefix([(None, )]))
950
950
 
951
951
    def test_iter_key_prefix_wrong_length(self):
952
952
        index = self.make_index()
953
 
        self.assertRaises(_mod_index.BadIndexKey, list,
954
 
                          index.iter_entries_prefix([(b'foo', None)]))
 
953
        self.assertRaises(errors.BadIndexKey, list,
 
954
            index.iter_entries_prefix([('foo', None)]))
955
955
        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)]))
 
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)]))
960
960
 
961
961
    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', )])))
 
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', )])))
968
968
 
969
969
    def test_iter_key_prefix_1_key_element_refs(self):
970
970
        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', )])))
 
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', )])))
976
976
 
977
977
    def test_iter_key_prefix_2_key_element_no_refs(self):
978
978
        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)])))
 
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)])))
989
988
 
990
989
    def test_iter_key_prefix_2_key_element_refs(self):
991
990
        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)])))
 
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)])))
1004
1000
 
1005
1001
    # XXX: external_references tests are duplicated in test_index.  We
1006
1002
    # probably should have per_graph_index tests...
1010
1006
 
1011
1007
    def test_external_references_no_results(self):
1012
1008
        index = self.make_index(ref_lists=1, nodes=[
1013
 
            ((b'key',), b'value', ([],))])
 
1009
            (('key',), 'value', ([],))])
1014
1010
        self.assertEqual(set(), index.external_references(0))
1015
1011
 
1016
1012
    def test_external_references_missing_ref(self):
1017
 
        missing_key = (b'missing',)
 
1013
        missing_key = ('missing',)
1018
1014
        index = self.make_index(ref_lists=1, nodes=[
1019
 
            ((b'key',), b'value', ([missing_key],))])
1020
 
        self.assertEqual({missing_key}, index.external_references(0))
 
1015
            (('key',), 'value', ([missing_key],))])
 
1016
        self.assertEqual(set([missing_key]), index.external_references(0))
1021
1017
 
1022
1018
    def test_external_references_multiple_ref_lists(self):
1023
 
        missing_key = (b'missing',)
 
1019
        missing_key = ('missing',)
1024
1020
        index = self.make_index(ref_lists=2, nodes=[
1025
 
            ((b'key',), b'value', ([], [missing_key]))])
 
1021
            (('key',), 'value', ([], [missing_key]))])
1026
1022
        self.assertEqual(set([]), index.external_references(0))
1027
 
        self.assertEqual({missing_key}, index.external_references(1))
 
1023
        self.assertEqual(set([missing_key]), index.external_references(1))
1028
1024
 
1029
1025
    def test_external_references_two_records(self):
1030
1026
        index = self.make_index(ref_lists=1, nodes=[
1031
 
            ((b'key-1',), b'value', ([(b'key-2',)],)),
1032
 
            ((b'key-2',), b'value', ([],)),
 
1027
            (('key-1',), 'value', ([('key-2',)],)),
 
1028
            (('key-2',), 'value', ([],)),
1033
1029
            ])
1034
1030
        self.assertEqual(set([]), index.external_references(0))
1035
1031
 
1036
1032
    def test__find_ancestors_one_page(self):
1037
 
        key1 = (b'key-1',)
1038
 
        key2 = (b'key-2',)
 
1033
        key1 = ('key-1',)
 
1034
        key2 = ('key-2',)
1039
1035
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1040
 
            (key1, b'value', ([key2],)),
1041
 
            (key2, b'value', ([],)),
 
1036
            (key1, 'value', ([key2],)),
 
1037
            (key2, 'value', ([],)),
1042
1038
            ])
1043
1039
        parent_map = {}
1044
1040
        missing_keys = set()
1045
 
        search_keys = index._find_ancestors(
1046
 
            [key1], 0, parent_map, missing_keys)
 
1041
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
1047
1042
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
1048
1043
        self.assertEqual(set(), missing_keys)
1049
1044
        self.assertEqual(set(), search_keys)
1050
1045
 
1051
1046
    def test__find_ancestors_one_page_w_missing(self):
1052
 
        key1 = (b'key-1',)
1053
 
        key2 = (b'key-2',)
1054
 
        key3 = (b'key-3',)
 
1047
        key1 = ('key-1',)
 
1048
        key2 = ('key-2',)
 
1049
        key3 = ('key-3',)
1055
1050
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1056
 
            (key1, b'value', ([key2],)),
1057
 
            (key2, b'value', ([],)),
 
1051
            (key1, 'value', ([key2],)),
 
1052
            (key2, 'value', ([],)),
1058
1053
            ])
1059
1054
        parent_map = {}
1060
1055
        missing_keys = set()
1063
1058
        self.assertEqual({key2: ()}, parent_map)
1064
1059
        # we know that key3 is missing because we read the page that it would
1065
1060
        # otherwise be on
1066
 
        self.assertEqual({key3}, missing_keys)
 
1061
        self.assertEqual(set([key3]), missing_keys)
1067
1062
        self.assertEqual(set(), search_keys)
1068
1063
 
1069
1064
    def test__find_ancestors_one_parent_missing(self):
1070
 
        key1 = (b'key-1',)
1071
 
        key2 = (b'key-2',)
1072
 
        key3 = (b'key-3',)
 
1065
        key1 = ('key-1',)
 
1066
        key2 = ('key-2',)
 
1067
        key3 = ('key-3',)
1073
1068
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1074
 
            (key1, b'value', ([key2],)),
1075
 
            (key2, b'value', ([key3],)),
 
1069
            (key1, 'value', ([key2],)),
 
1070
            (key2, 'value', ([key3],)),
1076
1071
            ])
1077
1072
        parent_map = {}
1078
1073
        missing_keys = set()
1083
1078
        # all we know is that key3 wasn't present on the page we were reading
1084
1079
        # but if you look, the last key is key2 which comes before key3, so we
1085
1080
        # don't know whether key3 would land on this page or not.
1086
 
        self.assertEqual({key3}, search_keys)
 
1081
        self.assertEqual(set([key3]), search_keys)
1087
1082
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
1088
1083
                                            missing_keys)
1089
1084
        # passing it back in, we are sure it is 'missing'
1090
1085
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
1091
 
        self.assertEqual({key3}, missing_keys)
 
1086
        self.assertEqual(set([key3]), missing_keys)
1092
1087
        self.assertEqual(set([]), search_keys)
1093
1088
 
1094
1089
    def test__find_ancestors_dont_search_known(self):
1095
 
        key1 = (b'key-1',)
1096
 
        key2 = (b'key-2',)
1097
 
        key3 = (b'key-3',)
 
1090
        key1 = ('key-1',)
 
1091
        key2 = ('key-2',)
 
1092
        key3 = ('key-3',)
1098
1093
        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', ([],)),
 
1094
            (key1, 'value', ([key2],)),
 
1095
            (key2, 'value', ([key3],)),
 
1096
            (key3, 'value', ([],)),
1102
1097
            ])
1103
1098
        # We already know about key2, so we won't try to search for key3
1104
1099
        parent_map = {key2: (key3,)}
1116
1111
        nodes = []
1117
1112
        ref_lists = ((),)
1118
1113
        rev_keys = []
1119
 
        for i in range(400):
1120
 
            rev_id = ('%s-%s-%s' % (email,
1121
 
                                    osutils.compact_date(start_time + i),
1122
 
                                    osutils.rand_chars(16))).encode('ascii')
 
1114
        for i in xrange(400):
 
1115
            rev_id = '%s-%s-%s' % (email,
 
1116
                                   osutils.compact_date(start_time + i),
 
1117
                                   osutils.rand_chars(16))
1123
1118
            rev_key = (rev_id,)
1124
 
            nodes.append((rev_key, b'value', ref_lists))
 
1119
            nodes.append((rev_key, 'value', ref_lists))
1125
1120
            # We have a ref 'list' of length 1, with a list of parents, with 1
1126
1121
            # parent which is a key
1127
1122
            ref_lists = ((rev_key,),)
1140
1135
        # Now, whatever key we select that would fall on the second page,
1141
1136
        # should give us all the parents until the page break
1142
1137
        key_idx = rev_keys.index(min_l2_key)
1143
 
        next_key = rev_keys[key_idx + 1]
 
1138
        next_key = rev_keys[key_idx+1]
1144
1139
        # So now when we get the parent map, we should get the key we are
1145
1140
        # looking for, min_l2_key, and then a reference to go look for the
1146
1141
        # parent of that key
1150
1145
                                            missing_keys)
1151
1146
        self.assertEqual([min_l2_key, next_key], sorted(parent_map))
1152
1147
        self.assertEqual(set(), missing_keys)
1153
 
        self.assertEqual({max_l1_key}, search_keys)
 
1148
        self.assertEqual(set([max_l1_key]), search_keys)
1154
1149
        parent_map = {}
1155
1150
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
1156
1151
                                            missing_keys)
1166
1161
                                            missing_keys)
1167
1162
        self.assertEqual(set(), search_keys)
1168
1163
        self.assertEqual({}, parent_map)
1169
 
        self.assertEqual({('one',), ('two',)}, missing_keys)
 
1164
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
1170
1165
 
1171
1166
    def test_supports_unlimited_cache(self):
1172
1167
        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)
1215
1210
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
1216
1211
 
1217
1212
    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")
 
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")
1224
1219
        node = btree_index._LeafNode(node_bytes, 1, 0)
1225
1220
        # We do direct access, or don't care about order, to leaf nodes most of
1226
1221
        # the time, so a dict is useful:
1227
1222
        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", ()),
 
1223
            ("0000000000000000000000000000000000000000",): ("value:0", ()),
 
1224
            ("1111111111111111111111111111111111111111",): ("value:1", ()),
 
1225
            ("2222222222222222222222222222222222222222",): ("value:2", ()),
 
1226
            ("3333333333333333333333333333333333333333",): ("value:3", ()),
 
1227
            ("4444444444444444444444444444444444444444",): ("value:4", ()),
1233
1228
            }, dict(node.all_items()))
1234
1229
 
1235
1230
    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
 
                      )
 
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
            ""
 
1237
            )
1243
1238
        node = btree_index._LeafNode(node_bytes, 2, 2)
1244
1239
        # We do direct access, or don't care about order, to leaf nodes most of
1245
1240
        # the time, so a dict is useful:
1246
1241
        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'),)))
 
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'),)))
1253
1248
            }, dict(node.all_items()))
1254
1249
 
1255
1250
    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
 
                      )
 
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"
 
1258
            )
1264
1259
        node = btree_index._InternalNode(node_bytes)
1265
1260
        # We want to bisect to find the right children from this node, so a
1266
1261
        # vector is most useful.
1267
1262
        self.assertEqual([
1268
 
            (b"0000000000000000000000000000000000000000",),
1269
 
            (b"1111111111111111111111111111111111111111",),
1270
 
            (b"2222222222222222222222222222222222222222",),
1271
 
            (b"3333333333333333333333333333333333333333",),
1272
 
            (b"4444444444444444444444444444444444444444",),
 
1263
            ("0000000000000000000000000000000000000000",),
 
1264
            ("1111111111111111111111111111111111111111",),
 
1265
            ("2222222222222222222222222222222222222222",),
 
1266
            ("3333333333333333333333333333333333333333",),
 
1267
            ("4444444444444444444444444444444444444444",),
1273
1268
            ], node.keys)
1274
1269
        self.assertEqual(1, node.offset)
1275
1270
 
1276
1271
    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
 
                      )
 
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
            ""
 
1278
            )
1284
1279
        node = btree_index._LeafNode(node_bytes, 2, 2)
1285
1280
        # We do direct access, or don't care about order, to leaf nodes most of
1286
1281
        # the time, so a dict is useful:
1287
1282
        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'),)))
 
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'),)))
1294
1289
            }, dict(node.all_items()))
1295
1290
 
1296
1291
    def assertFlattened(self, expected, key, value, refs):
1297
1292
        flat_key, flat_line = self.parse_btree._flatten_node(
1298
1293
            (None, key, value, refs), bool(refs))
1299
 
        self.assertEqual(b'\x00'.join(key), flat_key)
 
1294
        self.assertEqual('\x00'.join(key), flat_key)
1300
1295
        self.assertEqual(expected, flat_line)
1301
1296
 
1302
1297
    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'),)))
 
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'),)))
1325
1320
 
1326
1321
 
1327
1322
class TestCompiledBtree(tests.TestCase):
1337
1332
    def assertMultiBisectRight(self, offsets, search_keys, fixed_keys):
1338
1333
        self.assertEqual(offsets,
1339
1334
                         btree_index.BTreeGraphIndex._multi_bisect_right(
1340
 
                             search_keys, fixed_keys))
 
1335
                            search_keys, fixed_keys))
1341
1336
 
1342
1337
    def test_after(self):
1343
1338
        self.assertMultiBisectRight([(1, ['b'])], ['b'], ['a'])
1351
1346
 
1352
1347
    def test_exact(self):
1353
1348
        self.assertMultiBisectRight([(1, ['a'])], ['a'], ['a'])
1354
 
        self.assertMultiBisectRight(
1355
 
            [(1, ['a']), (2, ['b'])], ['a', 'b'], ['a', 'b'])
 
1349
        self.assertMultiBisectRight([(1, ['a']), (2, ['b'])], ['a', 'b'], ['a', 'b'])
1356
1350
        self.assertMultiBisectRight([(1, ['a']), (3, ['c'])],
1357
1351
                                    ['a', 'c'], ['a', 'b', 'c'])
1358
1352
 
1398
1392
        index._key_count = key_count
1399
1393
        index._row_lengths = row_lengths
1400
1394
        index._compute_row_offsets()
1401
 
        index._root_node = btree_index._InternalNode(b'internal\noffset=0\n')
 
1395
        index._root_node = btree_index._InternalNode('internal\noffset=0\n')
1402
1396
        self.set_cached_offsets(index, cached_offsets)
1403
1397
 
1404
1398
    def make_100_node_index(self):
1405
 
        index = self.make_index(4096 * 100, 6)
 
1399
        index = self.make_index(4096*100, 6)
1406
1400
        # Consider we've already made a single request at the middle
1407
1401
        self.prepare_index(index, node_ref_lists=0, key_length=1,
1408
1402
                           key_count=1000, row_lengths=[1, 99],
1410
1404
        return index
1411
1405
 
1412
1406
    def make_1000_node_index(self):
1413
 
        index = self.make_index(4096 * 1000, 6)
 
1407
        index = self.make_index(4096*1000, 6)
1414
1408
        # Pretend we've already made a single request in the middle
1415
1409
        self.prepare_index(index, node_ref_lists=0, key_length=1,
1416
1410
                           key_count=90000, row_lengths=[1, 9, 990],
1438
1432
        self.assertNumPages(1, index, 4096)
1439
1433
        self.assertNumPages(2, index, 4097)
1440
1434
        self.assertNumPages(2, index, 8192)
1441
 
        self.assertNumPages(76, index, 4096 * 75 + 10)
 
1435
        self.assertNumPages(76, index, 4096*75 + 10)
1442
1436
 
1443
1437
    def test__find_layer_start_and_stop(self):
1444
1438
        index = self.make_1000_node_index()
1456
1450
        self.assertExpandOffsets([1, 4, 9], index, [1, 4, 9])
1457
1451
 
1458
1452
    def test_more_than_recommended(self):
1459
 
        index = self.make_index(4096 * 100, 2)
 
1453
        index = self.make_index(4096*100, 2)
1460
1454
        self.assertExpandOffsets([1, 10], index, [1, 10])
1461
1455
        self.assertExpandOffsets([1, 10, 20], index, [1, 10, 20])
1462
1456
 
1463
1457
    def test_read_all_from_root(self):
1464
 
        index = self.make_index(4096 * 10, 20)
1465
 
        self.assertExpandOffsets(list(range(10)), index, [0])
 
1458
        index = self.make_index(4096*10, 20)
 
1459
        self.assertExpandOffsets(range(10), index, [0])
1466
1460
 
1467
1461
    def test_read_all_when_cached(self):
1468
1462
        # We've read enough that we can grab all the rest in a single request
1469
 
        index = self.make_index(4096 * 10, 5)
 
1463
        index = self.make_index(4096*10, 5)
1470
1464
        self.prepare_index(index, node_ref_lists=0, key_length=1,
1471
1465
                           key_count=1000, row_lengths=[1, 9],
1472
1466
                           cached_offsets=[0, 1, 2, 5, 6])
1476
1470
        self.assertExpandOffsets([3, 4, 7, 8, 9], index, [9])
1477
1471
 
1478
1472
    def test_no_root_node(self):
1479
 
        index = self.make_index(4096 * 10, 5)
 
1473
        index = self.make_index(4096*10, 5)
1480
1474
        self.assertExpandOffsets([0], index, [0])
1481
1475
 
1482
1476
    def test_include_neighbors(self):
1492
1486
        # Requesting many nodes will expand all locations equally
1493
1487
        self.assertExpandOffsets([1, 2, 3, 80, 81, 82], index, [2, 81])
1494
1488
        self.assertExpandOffsets([1, 2, 3, 9, 10, 11, 80, 81, 82], index,
1495
 
                                 [2, 10, 81])
 
1489
                               [2, 10, 81])
1496
1490
 
1497
1491
    def test_stop_at_cached(self):
1498
1492
        index = self.make_100_node_index()