← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_btree_index.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2011-08-17 18:13:57 UTC
  • mfrom: (5268.7.29 transport-segments)
  • Revision ID: pqm@pqm.ubuntu.com-20110817181357-y5q5eth1hk8bl3om
(jelmer) Allow specifying the colocated branch to use in the branch URL,
 and retrieving the branch name using ControlDir._get_selected_branch.
 (Jelmer Vernooij)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
1
 
# Copyright (C) 2008 Canonical Ltd
 
1
# Copyright (C) 2008-2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
#
17
17
 
18
18
"""Tests for btree indices."""
23
23
from bzrlib import (
24
24
    btree_index,
25
25
    errors,
 
26
    fifo_cache,
 
27
    lru_cache,
 
28
    osutils,
26
29
    tests,
 
30
    transport,
27
31
    )
28
32
from bzrlib.tests import (
29
33
    TestCaseWithTransport,
30
 
    TestScenarioApplier,
31
 
    adapt_tests,
32
 
    condition_isinstance,
33
 
    split_suite_by_condition,
34
 
    )
35
 
from bzrlib.transport import get_transport
36
 
 
37
 
 
38
 
def load_tests(standard_tests, module, loader):
39
 
    # parameterise the TestBTreeNodes tests
40
 
    node_tests, others = split_suite_by_condition(standard_tests,
41
 
        condition_isinstance(TestBTreeNodes))
42
 
    applier = TestScenarioApplier()
 
34
    scenarios,
 
35
    )
 
36
from bzrlib.tests import (
 
37
    features,
 
38
    )
 
39
 
 
40
 
 
41
load_tests = scenarios.load_tests_apply_scenarios
 
42
 
 
43
 
 
44
def btreeparser_scenarios():
43
45
    import bzrlib._btree_serializer_py as py_module
44
 
    applier.scenarios = [('python', {'parse_btree': py_module})]
45
 
    if CompiledBtreeParserFeature.available():
46
 
        # Is there a way to do this that gets missing feature failures rather
47
 
        # than no indication to the user?
48
 
        import bzrlib._btree_serializer_c as c_module
49
 
        applier.scenarios.append(('C', {'parse_btree': c_module}))
50
 
    adapt_tests(node_tests, applier, others)
51
 
    return others
52
 
 
53
 
 
54
 
class _CompiledBtreeParserFeature(tests.Feature):
55
 
    def _probe(self):
56
 
        try:
57
 
            import bzrlib._btree_serializer_c
58
 
        except ImportError:
59
 
            return False
60
 
        return True
61
 
 
62
 
    def feature_name(self):
63
 
        return 'bzrlib._btree_serializer_c'
64
 
 
65
 
CompiledBtreeParserFeature = _CompiledBtreeParserFeature()
 
46
    scenarios = [('python', {'parse_btree': py_module})]
 
47
    if compiled_btreeparser_feature.available():
 
48
        scenarios.append(('C', 
 
49
            {'parse_btree': compiled_btreeparser_feature.module}))
 
50
    return scenarios
 
51
 
 
52
 
 
53
compiled_btreeparser_feature = features.ModuleAvailableFeature(
 
54
    'bzrlib._btree_serializer_pyx')
66
55
 
67
56
 
68
57
class BTreeTestCase(TestCaseWithTransport):
71
60
 
72
61
    def setUp(self):
73
62
        TestCaseWithTransport.setUp(self)
74
 
        self._original_header = btree_index._RESERVED_HEADER_BYTES
75
 
        def restore():
76
 
            btree_index._RESERVED_HEADER_BYTES = self._original_header
77
 
        self.addCleanup(restore)
78
 
        btree_index._RESERVED_HEADER_BYTES = 100
 
63
        self.overrideAttr(btree_index, '_RESERVED_HEADER_BYTES', 100)
79
64
 
80
65
    def make_nodes(self, count, key_elements, reference_lists):
81
66
        """Generate count*key_elements sample nodes."""
115
100
 
116
101
    def shrink_page_size(self):
117
102
        """Shrink the default page size so that less fits in a page."""
118
 
        old_page_size = btree_index._PAGE_SIZE
119
 
        def cleanup():
120
 
            btree_index._PAGE_SIZE = old_page_size
121
 
        self.addCleanup(cleanup)
 
103
        self.overrideAttr(btree_index, '_PAGE_SIZE')
122
104
        btree_index._PAGE_SIZE = 2048
123
105
 
124
106
 
125
107
class TestBTreeBuilder(BTreeTestCase):
126
108
 
 
109
    def test_clear_cache(self):
 
110
        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)
 
111
        # This is a no-op, but we need the api to be consistent with other
 
112
        # BTreeGraphIndex apis.
 
113
        builder.clear_cache()
 
114
 
127
115
    def test_empty_1_0(self):
128
116
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
129
117
        # NamedTemporaryFile dies on builder.finish().read(). weird.
155
143
        temp_file = builder.finish()
156
144
        content = temp_file.read()
157
145
        del temp_file
158
 
        self.assertEqual(158, len(content))
 
146
        self.assertEqual(131, len(content))
159
147
        self.assertEqual(
160
148
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"
161
149
            "row_lengths=1\n",
179
167
        temp_file = builder.finish()
180
168
        content = temp_file.read()
181
169
        del temp_file
182
 
        self.assertEqual(264, len(content))
 
170
        self.assertEqual(238, len(content))
183
171
        self.assertEqual(
184
172
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"
185
173
            "row_lengths=1\n",
229
217
        leaf1_bytes = zlib.decompress(leaf1)
230
218
        sorted_node_keys = sorted(node[0] for node in nodes)
231
219
        node = btree_index._LeafNode(leaf1_bytes, 1, 0)
232
 
        self.assertEqual(231, len(node.keys))
233
 
        self.assertEqual(sorted_node_keys[:231], sorted(node.keys))
 
220
        self.assertEqual(231, len(node))
 
221
        self.assertEqual(sorted_node_keys[:231], node.all_keys())
234
222
        leaf2_bytes = zlib.decompress(leaf2)
235
223
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
236
 
        self.assertEqual(400 - 231, len(node.keys))
237
 
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
 
224
        self.assertEqual(400 - 231, len(node))
 
225
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
238
226
 
239
227
    def test_last_page_rounded_1_layer(self):
240
228
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
245
233
        temp_file = builder.finish()
246
234
        content = temp_file.read()
247
235
        del temp_file
248
 
        self.assertEqual(181, len(content))
 
236
        self.assertEqual(155, len(content))
249
237
        self.assertEqual(
250
238
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
251
239
            "row_lengths=1\n",
254
242
        leaf2 = content[74:]
255
243
        leaf2_bytes = zlib.decompress(leaf2)
256
244
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
257
 
        self.assertEqual(10, len(node.keys))
 
245
        self.assertEqual(10, len(node))
258
246
        sorted_node_keys = sorted(node[0] for node in nodes)
259
 
        self.assertEqual(sorted_node_keys, sorted(node.keys))
 
247
        self.assertEqual(sorted_node_keys, node.all_keys())
260
248
 
261
249
    def test_last_page_not_rounded_2_layer(self):
262
250
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
276
264
        leaf2 = content[8192:]
277
265
        leaf2_bytes = zlib.decompress(leaf2)
278
266
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
279
 
        self.assertEqual(400 - 231, len(node.keys))
 
267
        self.assertEqual(400 - 231, len(node))
280
268
        sorted_node_keys = sorted(node[0] for node in nodes)
281
 
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
 
269
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
282
270
 
283
271
    def test_three_level_tree_details(self):
284
272
        # The left most pointer in the second internal node in a row should
293
281
 
294
282
        for node in nodes:
295
283
            builder.add_node(*node)
296
 
        transport = get_transport('trace+' + self.get_url(''))
297
 
        size = transport.put_file('index', self.time(builder.finish))
 
284
        t = transport.get_transport('trace+' + self.get_url(''))
 
285
        size = t.put_file('index', self.time(builder.finish))
298
286
        del builder
299
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
287
        index = btree_index.BTreeGraphIndex(t, 'index', size)
300
288
        # Seed the metadata, we're using internal calls now.
301
289
        index.key_count()
302
290
        self.assertEqual(3, len(index._row_lengths),
315
303
        # in the second node it points at
316
304
        pos = index._row_offsets[2] + internal_node2.offset + 1
317
305
        leaf = index._get_leaf_nodes([pos])[pos]
318
 
        self.assertTrue(internal_node2.keys[0] in leaf.keys)
 
306
        self.assertTrue(internal_node2.keys[0] in leaf)
319
307
 
320
308
    def test_2_leaves_2_2(self):
321
309
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
353
341
        # Test the parts of the index that take up memory are doing so
354
342
        # predictably.
355
343
        self.assertEqual(1, len(builder._nodes))
356
 
        self.assertEqual(1, len(builder._keys))
357
344
        self.assertIs(None, builder._nodes_by_key)
358
345
        builder.add_node(*nodes[1])
359
346
        self.assertEqual(0, len(builder._nodes))
360
 
        self.assertEqual(0, len(builder._keys))
361
347
        self.assertIs(None, builder._nodes_by_key)
362
348
        self.assertEqual(1, len(builder._backing_indices))
363
349
        self.assertEqual(2, builder._backing_indices[0].key_count())
364
350
        # now back to memory
365
351
        builder.add_node(*nodes[2])
366
352
        self.assertEqual(1, len(builder._nodes))
367
 
        self.assertEqual(1, len(builder._keys))
368
353
        self.assertIs(None, builder._nodes_by_key)
369
354
        # And spills to a second backing index combing all
370
355
        builder.add_node(*nodes[3])
371
356
        self.assertEqual(0, len(builder._nodes))
372
 
        self.assertEqual(0, len(builder._keys))
373
357
        self.assertIs(None, builder._nodes_by_key)
374
358
        self.assertEqual(2, len(builder._backing_indices))
375
359
        self.assertEqual(None, builder._backing_indices[0])
378
362
        builder.add_node(*nodes[4])
379
363
        builder.add_node(*nodes[5])
380
364
        self.assertEqual(0, len(builder._nodes))
381
 
        self.assertEqual(0, len(builder._keys))
382
365
        self.assertIs(None, builder._nodes_by_key)
383
366
        self.assertEqual(2, len(builder._backing_indices))
384
367
        self.assertEqual(2, builder._backing_indices[0].key_count())
427
410
        self.assertEqual(None, builder._backing_indices[2])
428
411
        self.assertEqual(16, builder._backing_indices[3].key_count())
429
412
        # Now finish, and check we got a correctly ordered tree
 
413
        t = self.get_transport('')
 
414
        size = t.put_file('index', builder.finish())
 
415
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
416
        nodes = list(index.iter_all_entries())
 
417
        self.assertEqual(sorted(nodes), nodes)
 
418
        self.assertEqual(16, len(nodes))
 
419
 
 
420
    def test_spill_index_stress_1_1_no_combine(self):
 
421
        builder = btree_index.BTreeBuilder(key_elements=1, spill_at=2)
 
422
        builder.set_optimize(for_size=False, combine_backing_indices=False)
 
423
        nodes = [node[0:2] for node in self.make_nodes(16, 1, 0)]
 
424
        builder.add_node(*nodes[0])
 
425
        # Test the parts of the index that take up memory are doing so
 
426
        # predictably.
 
427
        self.assertEqual(1, len(builder._nodes))
 
428
        self.assertIs(None, builder._nodes_by_key)
 
429
        builder.add_node(*nodes[1])
 
430
        self.assertEqual(0, len(builder._nodes))
 
431
        self.assertIs(None, builder._nodes_by_key)
 
432
        self.assertEqual(1, len(builder._backing_indices))
 
433
        self.assertEqual(2, builder._backing_indices[0].key_count())
 
434
        # now back to memory
 
435
        builder.add_node(*nodes[2])
 
436
        self.assertEqual(1, len(builder._nodes))
 
437
        self.assertIs(None, builder._nodes_by_key)
 
438
        # And spills to a second backing index but doesn't combine
 
439
        builder.add_node(*nodes[3])
 
440
        self.assertEqual(0, len(builder._nodes))
 
441
        self.assertIs(None, builder._nodes_by_key)
 
442
        self.assertEqual(2, len(builder._backing_indices))
 
443
        for backing_index in builder._backing_indices:
 
444
            self.assertEqual(2, backing_index.key_count())
 
445
        # The next spills to the 3rd slot
 
446
        builder.add_node(*nodes[4])
 
447
        builder.add_node(*nodes[5])
 
448
        self.assertEqual(0, len(builder._nodes))
 
449
        self.assertIs(None, builder._nodes_by_key)
 
450
        self.assertEqual(3, len(builder._backing_indices))
 
451
        for backing_index in builder._backing_indices:
 
452
            self.assertEqual(2, backing_index.key_count())
 
453
        # Now spill a few more, and check that we don't combine
 
454
        builder.add_node(*nodes[6])
 
455
        builder.add_node(*nodes[7])
 
456
        builder.add_node(*nodes[8])
 
457
        builder.add_node(*nodes[9])
 
458
        builder.add_node(*nodes[10])
 
459
        builder.add_node(*nodes[11])
 
460
        builder.add_node(*nodes[12])
 
461
        self.assertEqual(6, len(builder._backing_indices))
 
462
        for backing_index in builder._backing_indices:
 
463
            self.assertEqual(2, backing_index.key_count())
 
464
        # Test that memory and disk are both used for query methods; and that
 
465
        # None is skipped over happily.
 
466
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
 
467
            list(builder.iter_all_entries()))
 
468
        # Two nodes - one memory one disk
 
469
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
470
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
471
        self.assertEqual(13, builder.key_count())
 
472
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
473
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
474
        builder.add_node(*nodes[13])
 
475
        builder.add_node(*nodes[14])
 
476
        builder.add_node(*nodes[15])
 
477
        self.assertEqual(8, len(builder._backing_indices))
 
478
        for backing_index in builder._backing_indices:
 
479
            self.assertEqual(2, backing_index.key_count())
 
480
        # Now finish, and check we got a correctly ordered tree
430
481
        transport = self.get_transport('')
431
482
        size = transport.put_file('index', builder.finish())
432
483
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
434
485
        self.assertEqual(sorted(nodes), nodes)
435
486
        self.assertEqual(16, len(nodes))
436
487
 
 
488
    def test_set_optimize(self):
 
489
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
 
490
        builder.set_optimize(for_size=True)
 
491
        self.assertTrue(builder._optimize_for_size)
 
492
        builder.set_optimize(for_size=False)
 
493
        self.assertFalse(builder._optimize_for_size)
 
494
        # test that we can set combine_backing_indices without effecting
 
495
        # _optimize_for_size
 
496
        obj = object()
 
497
        builder._optimize_for_size = obj
 
498
        builder.set_optimize(combine_backing_indices=False)
 
499
        self.assertFalse(builder._combine_backing_indices)
 
500
        self.assertIs(obj, builder._optimize_for_size)
 
501
        builder.set_optimize(combine_backing_indices=True)
 
502
        self.assertTrue(builder._combine_backing_indices)
 
503
        self.assertIs(obj, builder._optimize_for_size)
 
504
 
437
505
    def test_spill_index_stress_2_2(self):
438
506
        # test that references and longer keys don't confuse things.
439
507
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2,
442
510
        builder.add_node(*nodes[0])
443
511
        # Test the parts of the index that take up memory are doing so
444
512
        # predictably.
445
 
        self.assertEqual(1, len(builder._keys))
446
513
        self.assertEqual(1, len(builder._nodes))
447
514
        self.assertIs(None, builder._nodes_by_key)
448
515
        builder.add_node(*nodes[1])
449
 
        self.assertEqual(0, len(builder._keys))
450
516
        self.assertEqual(0, len(builder._nodes))
451
517
        self.assertIs(None, builder._nodes_by_key)
452
518
        self.assertEqual(1, len(builder._backing_indices))
455
521
        old = dict(builder._get_nodes_by_key()) #Build up the nodes by key dict
456
522
        builder.add_node(*nodes[2])
457
523
        self.assertEqual(1, len(builder._nodes))
458
 
        self.assertEqual(1, len(builder._keys))
459
524
        self.assertIsNot(None, builder._nodes_by_key)
460
525
        self.assertNotEqual({}, builder._nodes_by_key)
461
526
        # We should have a new entry
463
528
        # And spills to a second backing index combing all
464
529
        builder.add_node(*nodes[3])
465
530
        self.assertEqual(0, len(builder._nodes))
466
 
        self.assertEqual(0, len(builder._keys))
467
531
        self.assertIs(None, builder._nodes_by_key)
468
532
        self.assertEqual(2, len(builder._backing_indices))
469
533
        self.assertEqual(None, builder._backing_indices[0])
472
536
        builder.add_node(*nodes[4])
473
537
        builder.add_node(*nodes[5])
474
538
        self.assertEqual(0, len(builder._nodes))
475
 
        self.assertEqual(0, len(builder._keys))
476
539
        self.assertIs(None, builder._nodes_by_key)
477
540
        self.assertEqual(2, len(builder._backing_indices))
478
541
        self.assertEqual(2, builder._backing_indices[0].key_count())
545
608
        for key, value, references in nodes:
546
609
            builder.add_node(key, value, references)
547
610
        stream = builder.finish()
548
 
        trans = get_transport('trace+' + self.get_url())
 
611
        trans = transport.get_transport('trace+' + self.get_url())
549
612
        size = trans.put_file('index', stream)
550
613
        return btree_index.BTreeGraphIndex(trans, 'index', size)
551
614
 
 
615
    def make_index_with_offset(self, ref_lists=1, key_elements=1, nodes=[],
 
616
                               offset=0):
 
617
        builder = btree_index.BTreeBuilder(key_elements=key_elements,
 
618
                                           reference_lists=ref_lists)
 
619
        builder.add_nodes(nodes)
 
620
        transport = self.get_transport('')
 
621
        # NamedTemporaryFile dies on builder.finish().read(). weird.
 
622
        temp_file = builder.finish()
 
623
        content = temp_file.read()
 
624
        del temp_file
 
625
        size = len(content)
 
626
        transport.put_bytes('index', (' '*offset)+content)
 
627
        return btree_index.BTreeGraphIndex(transport, 'index', size=size,
 
628
                                           offset=offset)
 
629
 
 
630
    def test_clear_cache(self):
 
631
        nodes = self.make_nodes(160, 2, 2)
 
632
        index = self.make_index(ref_lists=2, key_elements=2, nodes=nodes)
 
633
        self.assertEqual(1, len(list(index.iter_entries([nodes[30][0]]))))
 
634
        self.assertEqual([1, 4], index._row_lengths)
 
635
        self.assertIsNot(None, index._root_node)
 
636
        internal_node_pre_clear = index._internal_node_cache.keys()
 
637
        self.assertTrue(len(index._leaf_node_cache) > 0)
 
638
        index.clear_cache()
 
639
        # We don't touch _root_node or _internal_node_cache, both should be
 
640
        # small, and can save a round trip or two
 
641
        self.assertIsNot(None, index._root_node)
 
642
        # NOTE: We don't want to affect the _internal_node_cache, as we expect
 
643
        #       it will be small, and if we ever do touch this index again, it
 
644
        #       will save round-trips.  This assertion isn't very strong,
 
645
        #       becuase without a 3-level index, we don't have any internal
 
646
        #       nodes cached.
 
647
        self.assertEqual(internal_node_pre_clear,
 
648
                         index._internal_node_cache.keys())
 
649
        self.assertEqual(0, len(index._leaf_node_cache))
 
650
 
552
651
    def test_trivial_constructor(self):
553
 
        transport = get_transport('trace+' + self.get_url(''))
554
 
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
 
652
        t = transport.get_transport('trace+' + self.get_url(''))
 
653
        index = btree_index.BTreeGraphIndex(t, 'index', None)
555
654
        # Checks the page size at load, but that isn't logged yet.
556
 
        self.assertEqual([], transport._activity)
 
655
        self.assertEqual([], t._activity)
557
656
 
558
657
    def test_with_size_constructor(self):
559
 
        transport = get_transport('trace+' + self.get_url(''))
560
 
        index = btree_index.BTreeGraphIndex(transport, 'index', 1)
 
658
        t = transport.get_transport('trace+' + self.get_url(''))
 
659
        index = btree_index.BTreeGraphIndex(t, 'index', 1)
561
660
        # Checks the page size at load, but that isn't logged yet.
562
 
        self.assertEqual([], transport._activity)
 
661
        self.assertEqual([], t._activity)
563
662
 
564
663
    def test_empty_key_count_no_size(self):
565
664
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
566
 
        transport = get_transport('trace+' + self.get_url(''))
567
 
        transport.put_file('index', builder.finish())
568
 
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
569
 
        del transport._activity[:]
570
 
        self.assertEqual([], transport._activity)
 
665
        t = transport.get_transport('trace+' + self.get_url(''))
 
666
        t.put_file('index', builder.finish())
 
667
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
668
        del t._activity[:]
 
669
        self.assertEqual([], t._activity)
571
670
        self.assertEqual(0, index.key_count())
572
671
        # The entire index should have been requested (as we generally have the
573
672
        # size available, and doing many small readvs is inappropriate).
574
673
        # We can't tell how much was actually read here, but - check the code.
575
 
        self.assertEqual([('get', 'index'),
576
 
            ('readv', 'index', [(0, 72)], False, None)],
577
 
            transport._activity)
 
674
        self.assertEqual([('get', 'index')], t._activity)
578
675
 
579
676
    def test_empty_key_count(self):
580
677
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
581
 
        transport = get_transport('trace+' + self.get_url(''))
582
 
        size = transport.put_file('index', builder.finish())
 
678
        t = transport.get_transport('trace+' + self.get_url(''))
 
679
        size = t.put_file('index', builder.finish())
583
680
        self.assertEqual(72, size)
584
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
585
 
        del transport._activity[:]
586
 
        self.assertEqual([], transport._activity)
 
681
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
682
        del t._activity[:]
 
683
        self.assertEqual([], t._activity)
587
684
        self.assertEqual(0, index.key_count())
588
685
        # The entire index should have been read, as 4K > size
589
686
        self.assertEqual([('readv', 'index', [(0, 72)], False, None)],
590
 
            transport._activity)
 
687
                         t._activity)
591
688
 
592
689
    def test_non_empty_key_count_2_2(self):
593
690
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
594
691
        nodes = self.make_nodes(35, 2, 2)
595
692
        for node in nodes:
596
693
            builder.add_node(*node)
597
 
        transport = get_transport('trace+' + self.get_url(''))
598
 
        size = transport.put_file('index', builder.finish())
599
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
600
 
        del transport._activity[:]
601
 
        self.assertEqual([], transport._activity)
 
694
        t = transport.get_transport('trace+' + self.get_url(''))
 
695
        size = t.put_file('index', builder.finish())
 
696
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
697
        del t._activity[:]
 
698
        self.assertEqual([], t._activity)
602
699
        self.assertEqual(70, index.key_count())
603
700
        # The entire index should have been read, as it is one page long.
604
701
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
605
 
            transport._activity)
606
 
        self.assertEqual(1199, size)
 
702
            t._activity)
 
703
        self.assertEqual(1173, size)
 
704
 
 
705
    def test_with_offset_no_size(self):
 
706
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
 
707
                                            offset=1234,
 
708
                                            nodes=self.make_nodes(200, 1, 1))
 
709
        index._size = None # throw away the size info
 
710
        self.assertEqual(200, index.key_count())
 
711
 
 
712
    def test_with_small_offset(self):
 
713
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
 
714
                                            offset=1234,
 
715
                                            nodes=self.make_nodes(200, 1, 1))
 
716
        self.assertEqual(200, index.key_count())
 
717
 
 
718
    def test_with_large_offset(self):
 
719
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
 
720
                                            offset=123456,
 
721
                                            nodes=self.make_nodes(200, 1, 1))
 
722
        self.assertEqual(200, index.key_count())
 
723
 
 
724
    def test__read_nodes_no_size_one_page_reads_once(self):
 
725
        self.make_index(nodes=[(('key',), 'value', ())])
 
726
        trans = transport.get_transport('trace+' + self.get_url())
 
727
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
 
728
        del trans._activity[:]
 
729
        nodes = dict(index._read_nodes([0]))
 
730
        self.assertEqual([0], nodes.keys())
 
731
        node = nodes[0]
 
732
        self.assertEqual([('key',)], node.all_keys())
 
733
        self.assertEqual([('get', 'index')], trans._activity)
 
734
 
 
735
    def test__read_nodes_no_size_multiple_pages(self):
 
736
        index = self.make_index(2, 2, nodes=self.make_nodes(160, 2, 2))
 
737
        index.key_count()
 
738
        num_pages = index._row_offsets[-1]
 
739
        # Reopen with a traced transport and no size
 
740
        trans = transport.get_transport('trace+' + self.get_url())
 
741
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
 
742
        del trans._activity[:]
 
743
        nodes = dict(index._read_nodes([0]))
 
744
        self.assertEqual(range(num_pages), nodes.keys())
607
745
 
608
746
    def test_2_levels_key_count_2_2(self):
609
747
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
610
748
        nodes = self.make_nodes(160, 2, 2)
611
749
        for node in nodes:
612
750
            builder.add_node(*node)
613
 
        transport = get_transport('trace+' + self.get_url(''))
614
 
        size = transport.put_file('index', builder.finish())
 
751
        t = transport.get_transport('trace+' + self.get_url(''))
 
752
        size = t.put_file('index', builder.finish())
615
753
        self.assertEqual(17692, size)
616
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
617
 
        del transport._activity[:]
618
 
        self.assertEqual([], transport._activity)
 
754
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
755
        del t._activity[:]
 
756
        self.assertEqual([], t._activity)
619
757
        self.assertEqual(320, index.key_count())
620
758
        # The entire index should not have been read.
621
759
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None)],
622
 
            transport._activity)
 
760
                         t._activity)
623
761
 
624
762
    def test_validate_one_page(self):
625
763
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
626
764
        nodes = self.make_nodes(45, 2, 2)
627
765
        for node in nodes:
628
766
            builder.add_node(*node)
629
 
        transport = get_transport('trace+' + self.get_url(''))
630
 
        size = transport.put_file('index', builder.finish())
631
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
632
 
        del transport._activity[:]
633
 
        self.assertEqual([], transport._activity)
 
767
        t = transport.get_transport('trace+' + self.get_url(''))
 
768
        size = t.put_file('index', builder.finish())
 
769
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
770
        del t._activity[:]
 
771
        self.assertEqual([], t._activity)
634
772
        index.validate()
635
773
        # The entire index should have been read linearly.
636
774
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
637
 
            transport._activity)
638
 
        self.assertEqual(1514, size)
 
775
                         t._activity)
 
776
        self.assertEqual(1488, size)
639
777
 
640
778
    def test_validate_two_pages(self):
641
779
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
642
780
        nodes = self.make_nodes(80, 2, 2)
643
781
        for node in nodes:
644
782
            builder.add_node(*node)
645
 
        transport = get_transport('trace+' + self.get_url(''))
646
 
        size = transport.put_file('index', builder.finish())
 
783
        t = transport.get_transport('trace+' + self.get_url(''))
 
784
        size = t.put_file('index', builder.finish())
647
785
        # Root page, 2 leaf pages
648
786
        self.assertEqual(9339, size)
649
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
650
 
        del transport._activity[:]
651
 
        self.assertEqual([], transport._activity)
 
787
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
788
        del t._activity[:]
 
789
        self.assertEqual([], t._activity)
652
790
        index.validate()
653
791
        # The entire index should have been read linearly.
654
 
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
655
 
            ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
656
 
            transport._activity)
 
792
        self.assertEqual(
 
793
            [('readv', 'index', [(0, 4096)], False, None),
 
794
             ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
 
795
            t._activity)
657
796
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
658
797
        # node and make validate find them.
659
798
 
660
799
    def test_eq_ne(self):
661
800
        # two indices are equal when constructed with the same parameters:
662
 
        transport1 = get_transport('trace+' + self.get_url(''))
663
 
        transport2 = get_transport(self.get_url(''))
664
 
        self.assertTrue(
665
 
            btree_index.BTreeGraphIndex(transport1, 'index', None) ==
666
 
            btree_index.BTreeGraphIndex(transport1, 'index', None))
667
 
        self.assertTrue(
668
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
669
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
670
 
        self.assertFalse(
671
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
672
 
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
673
 
        self.assertFalse(
674
 
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) ==
675
 
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
676
 
        self.assertFalse(
677
 
            btree_index.BTreeGraphIndex(transport1, 'index', 10) ==
678
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
679
 
        self.assertFalse(
680
 
            btree_index.BTreeGraphIndex(transport1, 'index', None) !=
681
 
            btree_index.BTreeGraphIndex(transport1, 'index', None))
682
 
        self.assertFalse(
683
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
684
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
685
 
        self.assertTrue(
686
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
687
 
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
688
 
        self.assertTrue(
689
 
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) !=
690
 
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
691
 
        self.assertTrue(
692
 
            btree_index.BTreeGraphIndex(transport1, 'index', 10) !=
693
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
 
801
        t1 = transport.get_transport('trace+' + self.get_url(''))
 
802
        t2 = self.get_transport()
 
803
        self.assertTrue(
 
804
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
 
805
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
806
        self.assertTrue(
 
807
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
808
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
809
        self.assertFalse(
 
810
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
811
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
812
        self.assertFalse(
 
813
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) ==
 
814
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
815
        self.assertFalse(
 
816
            btree_index.BTreeGraphIndex(t1, 'index', 10) ==
 
817
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
818
        self.assertFalse(
 
819
            btree_index.BTreeGraphIndex(t1, 'index', None) !=
 
820
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
821
        self.assertFalse(
 
822
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
823
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
824
        self.assertTrue(
 
825
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
826
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
827
        self.assertTrue(
 
828
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) !=
 
829
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
830
        self.assertTrue(
 
831
            btree_index.BTreeGraphIndex(t1, 'index', 10) !=
 
832
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
833
 
 
834
    def test_iter_all_only_root_no_size(self):
 
835
        self.make_index(nodes=[(('key',), 'value', ())])
 
836
        t = transport.get_transport('trace+' + self.get_url(''))
 
837
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
838
        del t._activity[:]
 
839
        self.assertEqual([(('key',), 'value')],
 
840
                         [x[1:] for x in index.iter_all_entries()])
 
841
        self.assertEqual([('get', 'index')], t._activity)
694
842
 
695
843
    def test_iter_all_entries_reads(self):
696
844
        # iterating all entries reads the header, then does a linear
702
850
        nodes = self.make_nodes(10000, 2, 2)
703
851
        for node in nodes:
704
852
            builder.add_node(*node)
705
 
        transport = get_transport('trace+' + self.get_url(''))
706
 
        size = transport.put_file('index', builder.finish())
 
853
        t = transport.get_transport('trace+' + self.get_url(''))
 
854
        size = t.put_file('index', builder.finish())
707
855
        self.assertEqual(1303220, size, 'number of expected bytes in the'
708
856
                                        ' output changed')
709
857
        page_size = btree_index._PAGE_SIZE
710
858
        del builder
711
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
712
 
        del transport._activity[:]
713
 
        self.assertEqual([], transport._activity)
 
859
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
860
        del t._activity[:]
 
861
        self.assertEqual([], t._activity)
714
862
        found_nodes = self.time(list, index.iter_all_entries())
715
863
        bare_nodes = []
716
864
        for node in found_nodes:
737
885
        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
738
886
        expected = [('readv', 'index', [(0, page_size)], False, None),
739
887
             ('readv',  'index', readv_request, False, None)]
740
 
        if expected != transport._activity:
 
888
        if expected != t._activity:
741
889
            self.assertEqualDiff(pprint.pformat(expected),
742
890
                                 pprint.pformat(transport._activity))
743
891
 
757
905
        nodes = self.make_nodes(160, 2, 2)
758
906
        for node in nodes:
759
907
            builder.add_node(*node)
760
 
        transport = get_transport('trace+' + self.get_url(''))
761
 
        size = transport.put_file('index', builder.finish())
 
908
        t = transport.get_transport('trace+' + self.get_url(''))
 
909
        size = t.put_file('index', builder.finish())
762
910
        del builder
763
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
764
 
        del transport._activity[:]
765
 
        self.assertEqual([], transport._activity)
 
911
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
912
        del t._activity[:]
 
913
        self.assertEqual([], t._activity)
766
914
        # search for one key
767
915
        found_nodes = list(index.iter_entries([nodes[30][0]]))
768
916
        bare_nodes = []
776
924
        # Should have read the root node, then one leaf page:
777
925
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
778
926
             ('readv',  'index', [(8192, 4096), ], False, None)],
779
 
            transport._activity)
 
927
            t._activity)
780
928
 
781
929
    def test_iter_key_prefix_1_element_key_None(self):
782
930
        index = self.make_index()
833
981
            (index, ('name', 'fin2'), 'beta', ((), ))]),
834
982
            set(index.iter_entries_prefix([('name', None)])))
835
983
 
 
984
    # XXX: external_references tests are duplicated in test_index.  We
 
985
    # probably should have per_graph_index tests...
 
986
    def test_external_references_no_refs(self):
 
987
        index = self.make_index(ref_lists=0, nodes=[])
 
988
        self.assertRaises(ValueError, index.external_references, 0)
 
989
 
 
990
    def test_external_references_no_results(self):
 
991
        index = self.make_index(ref_lists=1, nodes=[
 
992
            (('key',), 'value', ([],))])
 
993
        self.assertEqual(set(), index.external_references(0))
 
994
 
 
995
    def test_external_references_missing_ref(self):
 
996
        missing_key = ('missing',)
 
997
        index = self.make_index(ref_lists=1, nodes=[
 
998
            (('key',), 'value', ([missing_key],))])
 
999
        self.assertEqual(set([missing_key]), index.external_references(0))
 
1000
 
 
1001
    def test_external_references_multiple_ref_lists(self):
 
1002
        missing_key = ('missing',)
 
1003
        index = self.make_index(ref_lists=2, nodes=[
 
1004
            (('key',), 'value', ([], [missing_key]))])
 
1005
        self.assertEqual(set([]), index.external_references(0))
 
1006
        self.assertEqual(set([missing_key]), index.external_references(1))
 
1007
 
 
1008
    def test_external_references_two_records(self):
 
1009
        index = self.make_index(ref_lists=1, nodes=[
 
1010
            (('key-1',), 'value', ([('key-2',)],)),
 
1011
            (('key-2',), 'value', ([],)),
 
1012
            ])
 
1013
        self.assertEqual(set([]), index.external_references(0))
 
1014
 
 
1015
    def test__find_ancestors_one_page(self):
 
1016
        key1 = ('key-1',)
 
1017
        key2 = ('key-2',)
 
1018
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1019
            (key1, 'value', ([key2],)),
 
1020
            (key2, 'value', ([],)),
 
1021
            ])
 
1022
        parent_map = {}
 
1023
        missing_keys = set()
 
1024
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
 
1025
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
 
1026
        self.assertEqual(set(), missing_keys)
 
1027
        self.assertEqual(set(), search_keys)
 
1028
 
 
1029
    def test__find_ancestors_one_page_w_missing(self):
 
1030
        key1 = ('key-1',)
 
1031
        key2 = ('key-2',)
 
1032
        key3 = ('key-3',)
 
1033
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1034
            (key1, 'value', ([key2],)),
 
1035
            (key2, 'value', ([],)),
 
1036
            ])
 
1037
        parent_map = {}
 
1038
        missing_keys = set()
 
1039
        search_keys = index._find_ancestors([key2, key3], 0, parent_map,
 
1040
                                            missing_keys)
 
1041
        self.assertEqual({key2: ()}, parent_map)
 
1042
        # we know that key3 is missing because we read the page that it would
 
1043
        # otherwise be on
 
1044
        self.assertEqual(set([key3]), missing_keys)
 
1045
        self.assertEqual(set(), search_keys)
 
1046
 
 
1047
    def test__find_ancestors_one_parent_missing(self):
 
1048
        key1 = ('key-1',)
 
1049
        key2 = ('key-2',)
 
1050
        key3 = ('key-3',)
 
1051
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1052
            (key1, 'value', ([key2],)),
 
1053
            (key2, 'value', ([key3],)),
 
1054
            ])
 
1055
        parent_map = {}
 
1056
        missing_keys = set()
 
1057
        search_keys = index._find_ancestors([key1], 0, parent_map,
 
1058
                                            missing_keys)
 
1059
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1060
        self.assertEqual(set(), missing_keys)
 
1061
        # all we know is that key3 wasn't present on the page we were reading
 
1062
        # but if you look, the last key is key2 which comes before key3, so we
 
1063
        # don't know whether key3 would land on this page or not.
 
1064
        self.assertEqual(set([key3]), search_keys)
 
1065
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
 
1066
                                            missing_keys)
 
1067
        # passing it back in, we are sure it is 'missing'
 
1068
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1069
        self.assertEqual(set([key3]), missing_keys)
 
1070
        self.assertEqual(set([]), search_keys)
 
1071
 
 
1072
    def test__find_ancestors_dont_search_known(self):
 
1073
        key1 = ('key-1',)
 
1074
        key2 = ('key-2',)
 
1075
        key3 = ('key-3',)
 
1076
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1077
            (key1, 'value', ([key2],)),
 
1078
            (key2, 'value', ([key3],)),
 
1079
            (key3, 'value', ([],)),
 
1080
            ])
 
1081
        # We already know about key2, so we won't try to search for key3
 
1082
        parent_map = {key2: (key3,)}
 
1083
        missing_keys = set()
 
1084
        search_keys = index._find_ancestors([key1], 0, parent_map,
 
1085
                                            missing_keys)
 
1086
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1087
        self.assertEqual(set(), missing_keys)
 
1088
        self.assertEqual(set(), search_keys)
 
1089
 
 
1090
    def test__find_ancestors_multiple_pages(self):
 
1091
        # We need to use enough keys that we actually cause a split
 
1092
        start_time = 1249671539
 
1093
        email = "joebob@example.com"
 
1094
        nodes = []
 
1095
        ref_lists = ((),)
 
1096
        rev_keys = []
 
1097
        for i in xrange(400):
 
1098
            rev_id = '%s-%s-%s' % (email,
 
1099
                                   osutils.compact_date(start_time + i),
 
1100
                                   osutils.rand_chars(16))
 
1101
            rev_key = (rev_id,)
 
1102
            nodes.append((rev_key, 'value', ref_lists))
 
1103
            # We have a ref 'list' of length 1, with a list of parents, with 1
 
1104
            # parent which is a key
 
1105
            ref_lists = ((rev_key,),)
 
1106
            rev_keys.append(rev_key)
 
1107
        index = self.make_index(ref_lists=1, key_elements=1, nodes=nodes)
 
1108
        self.assertEqual(400, index.key_count())
 
1109
        self.assertEqual(3, len(index._row_offsets))
 
1110
        nodes = dict(index._read_nodes([1, 2]))
 
1111
        l1 = nodes[1]
 
1112
        l2 = nodes[2]
 
1113
        min_l2_key = l2.min_key
 
1114
        max_l1_key = l1.max_key
 
1115
        self.assertTrue(max_l1_key < min_l2_key)
 
1116
        parents_min_l2_key = l2[min_l2_key][1][0]
 
1117
        self.assertEqual((l1.max_key,), parents_min_l2_key)
 
1118
        # Now, whatever key we select that would fall on the second page,
 
1119
        # should give us all the parents until the page break
 
1120
        key_idx = rev_keys.index(min_l2_key)
 
1121
        next_key = rev_keys[key_idx+1]
 
1122
        # So now when we get the parent map, we should get the key we are
 
1123
        # looking for, min_l2_key, and then a reference to go look for the
 
1124
        # parent of that key
 
1125
        parent_map = {}
 
1126
        missing_keys = set()
 
1127
        search_keys = index._find_ancestors([next_key], 0, parent_map,
 
1128
                                            missing_keys)
 
1129
        self.assertEqual([min_l2_key, next_key], sorted(parent_map))
 
1130
        self.assertEqual(set(), missing_keys)
 
1131
        self.assertEqual(set([max_l1_key]), search_keys)
 
1132
        parent_map = {}
 
1133
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
 
1134
                                            missing_keys)
 
1135
        self.assertEqual(l1.all_keys(), sorted(parent_map))
 
1136
        self.assertEqual(set(), missing_keys)
 
1137
        self.assertEqual(set(), search_keys)
 
1138
 
 
1139
    def test__find_ancestors_empty_index(self):
 
1140
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[])
 
1141
        parent_map = {}
 
1142
        missing_keys = set()
 
1143
        search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
 
1144
                                            missing_keys)
 
1145
        self.assertEqual(set(), search_keys)
 
1146
        self.assertEqual({}, parent_map)
 
1147
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
 
1148
 
 
1149
    def test_supports_unlimited_cache(self):
 
1150
        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)
 
1151
        # We need enough nodes to cause a page split (so we have both an
 
1152
        # internal node and a couple leaf nodes. 500 seems to be enough.)
 
1153
        nodes = self.make_nodes(500, 1, 0)
 
1154
        for node in nodes:
 
1155
            builder.add_node(*node)
 
1156
        stream = builder.finish()
 
1157
        trans = self.get_transport()
 
1158
        size = trans.put_file('index', stream)
 
1159
        index = btree_index.BTreeGraphIndex(trans, 'index', size)
 
1160
        self.assertEqual(500, index.key_count())
 
1161
        # We have an internal node
 
1162
        self.assertEqual(2, len(index._row_lengths))
 
1163
        # We have at least 2 leaf nodes
 
1164
        self.assertTrue(index._row_lengths[-1] >= 2)
 
1165
        self.assertIsInstance(index._leaf_node_cache, lru_cache.LRUCache)
 
1166
        self.assertEqual(btree_index._NODE_CACHE_SIZE,
 
1167
                         index._leaf_node_cache._max_cache)
 
1168
        self.assertIsInstance(index._internal_node_cache, fifo_cache.FIFOCache)
 
1169
        self.assertEqual(100, index._internal_node_cache._max_cache)
 
1170
        # No change if unlimited_cache=False is passed
 
1171
        index = btree_index.BTreeGraphIndex(trans, 'index', size,
 
1172
                                            unlimited_cache=False)
 
1173
        self.assertIsInstance(index._leaf_node_cache, lru_cache.LRUCache)
 
1174
        self.assertEqual(btree_index._NODE_CACHE_SIZE,
 
1175
                         index._leaf_node_cache._max_cache)
 
1176
        self.assertIsInstance(index._internal_node_cache, fifo_cache.FIFOCache)
 
1177
        self.assertEqual(100, index._internal_node_cache._max_cache)
 
1178
        index = btree_index.BTreeGraphIndex(trans, 'index', size,
 
1179
                                            unlimited_cache=True)
 
1180
        self.assertIsInstance(index._leaf_node_cache, dict)
 
1181
        self.assertIs(type(index._internal_node_cache), dict)
 
1182
        # Exercise the lookup code
 
1183
        entries = set(index.iter_entries([n[0] for n in nodes]))
 
1184
        self.assertEqual(500, len(entries))
 
1185
 
836
1186
 
837
1187
class TestBTreeNodes(BTreeTestCase):
838
1188
 
839
 
    def restore_parser(self):
840
 
        btree_index._btree_serializer = self.saved_parser
 
1189
    scenarios = btreeparser_scenarios()
841
1190
 
842
1191
    def setUp(self):
843
1192
        BTreeTestCase.setUp(self)
844
 
        self.saved_parser = btree_index._btree_serializer
845
 
        self.addCleanup(self.restore_parser)
846
 
        btree_index._btree_serializer = self.parse_btree
 
1193
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
847
1194
 
848
1195
    def test_LeafNode_1_0(self):
849
1196
        node_bytes = ("type=leaf\n"
861
1208
            ("2222222222222222222222222222222222222222",): ("value:2", ()),
862
1209
            ("3333333333333333333333333333333333333333",): ("value:3", ()),
863
1210
            ("4444444444444444444444444444444444444444",): ("value:4", ()),
864
 
            }, node.keys)
 
1211
            }, dict(node.all_items()))
865
1212
 
866
1213
    def test_LeafNode_2_2(self):
867
1214
        node_bytes = ("type=leaf\n"
881
1228
            ('11', '33'): ('value:3',
882
1229
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
883
1230
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
884
 
            }, node.keys)
 
1231
            }, dict(node.all_items()))
885
1232
 
886
1233
    def test_InternalNode_1(self):
887
1234
        node_bytes = ("type=internal\n"
922
1269
            ('11', '33'): ('value:3',
923
1270
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
924
1271
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
925
 
            }, node.keys)
 
1272
            }, dict(node.all_items()))
926
1273
 
927
1274
    def assertFlattened(self, expected, key, value, refs):
928
1275
        flat_key, flat_line = self.parse_btree._flatten_node(
960
1307
    def test_exists(self):
961
1308
        # This is just to let the user know if they don't have the feature
962
1309
        # available
963
 
        self.requireFeature(CompiledBtreeParserFeature)
 
1310
        self.requireFeature(compiled_btreeparser_feature)
964
1311
 
965
1312
 
966
1313
class TestMultiBisectRight(tests.TestCase):
996
1343
                                     (4, ['g', 'h'])],
997
1344
                                    ['a', 'b', 'd', 'e', 'g', 'h'],
998
1345
                                    ['c', 'd', 'f', 'g'])
 
1346
 
 
1347
 
 
1348
class TestExpandOffsets(tests.TestCase):
 
1349
 
 
1350
    def make_index(self, size, recommended_pages=None):
 
1351
        """Make an index with a generic size.
 
1352
 
 
1353
        This doesn't actually create anything on disk, it just primes a
 
1354
        BTreeGraphIndex with the recommended information.
 
1355
        """
 
1356
        index = btree_index.BTreeGraphIndex(
 
1357
            transport.get_transport('memory:///'), 'test-index', size=size)
 
1358
        if recommended_pages is not None:
 
1359
            index._recommended_pages = recommended_pages
 
1360
        return index
 
1361
 
 
1362
    def set_cached_offsets(self, index, cached_offsets):
 
1363
        """Monkeypatch to give a canned answer for _get_offsets_for...()."""
 
1364
        def _get_offsets_to_cached_pages():
 
1365
            cached = set(cached_offsets)
 
1366
            return cached
 
1367
        index._get_offsets_to_cached_pages = _get_offsets_to_cached_pages
 
1368
 
 
1369
    def prepare_index(self, index, node_ref_lists, key_length, key_count,
 
1370
                      row_lengths, cached_offsets):
 
1371
        """Setup the BTreeGraphIndex with some pre-canned information."""
 
1372
        index.node_ref_lists = node_ref_lists
 
1373
        index._key_length = key_length
 
1374
        index._key_count = key_count
 
1375
        index._row_lengths = row_lengths
 
1376
        index._compute_row_offsets()
 
1377
        index._root_node = btree_index._InternalNode('internal\noffset=0\n')
 
1378
        self.set_cached_offsets(index, cached_offsets)
 
1379
 
 
1380
    def make_100_node_index(self):
 
1381
        index = self.make_index(4096*100, 6)
 
1382
        # Consider we've already made a single request at the middle
 
1383
        self.prepare_index(index, node_ref_lists=0, key_length=1,
 
1384
                           key_count=1000, row_lengths=[1, 99],
 
1385
                           cached_offsets=[0, 50])
 
1386
        return index
 
1387
 
 
1388
    def make_1000_node_index(self):
 
1389
        index = self.make_index(4096*1000, 6)
 
1390
        # Pretend we've already made a single request in the middle
 
1391
        self.prepare_index(index, node_ref_lists=0, key_length=1,
 
1392
                           key_count=90000, row_lengths=[1, 9, 990],
 
1393
                           cached_offsets=[0, 5, 500])
 
1394
        return index
 
1395
 
 
1396
    def assertNumPages(self, expected_pages, index, size):
 
1397
        index._size = size
 
1398
        self.assertEqual(expected_pages, index._compute_total_pages_in_index())
 
1399
 
 
1400
    def assertExpandOffsets(self, expected, index, offsets):
 
1401
        self.assertEqual(expected, index._expand_offsets(offsets),
 
1402
                         'We did not get the expected value after expanding'
 
1403
                         ' %s' % (offsets,))
 
1404
 
 
1405
    def test_default_recommended_pages(self):
 
1406
        index = self.make_index(None)
 
1407
        # local transport recommends 4096 byte reads, which is 1 page
 
1408
        self.assertEqual(1, index._recommended_pages)
 
1409
 
 
1410
    def test__compute_total_pages_in_index(self):
 
1411
        index = self.make_index(None)
 
1412
        self.assertNumPages(1, index, 1024)
 
1413
        self.assertNumPages(1, index, 4095)
 
1414
        self.assertNumPages(1, index, 4096)
 
1415
        self.assertNumPages(2, index, 4097)
 
1416
        self.assertNumPages(2, index, 8192)
 
1417
        self.assertNumPages(76, index, 4096*75 + 10)
 
1418
 
 
1419
    def test__find_layer_start_and_stop(self):
 
1420
        index = self.make_1000_node_index()
 
1421
        self.assertEqual((0, 1), index._find_layer_first_and_end(0))
 
1422
        self.assertEqual((1, 10), index._find_layer_first_and_end(1))
 
1423
        self.assertEqual((1, 10), index._find_layer_first_and_end(9))
 
1424
        self.assertEqual((10, 1000), index._find_layer_first_and_end(10))
 
1425
        self.assertEqual((10, 1000), index._find_layer_first_and_end(99))
 
1426
        self.assertEqual((10, 1000), index._find_layer_first_and_end(999))
 
1427
 
 
1428
    def test_unknown_size(self):
 
1429
        # We should not expand if we don't know the file size
 
1430
        index = self.make_index(None, 10)
 
1431
        self.assertExpandOffsets([0], index, [0])
 
1432
        self.assertExpandOffsets([1, 4, 9], index, [1, 4, 9])
 
1433
 
 
1434
    def test_more_than_recommended(self):
 
1435
        index = self.make_index(4096*100, 2)
 
1436
        self.assertExpandOffsets([1, 10], index, [1, 10])
 
1437
        self.assertExpandOffsets([1, 10, 20], index, [1, 10, 20])
 
1438
 
 
1439
    def test_read_all_from_root(self):
 
1440
        index = self.make_index(4096*10, 20)
 
1441
        self.assertExpandOffsets(range(10), index, [0])
 
1442
 
 
1443
    def test_read_all_when_cached(self):
 
1444
        # We've read enough that we can grab all the rest in a single request
 
1445
        index = self.make_index(4096*10, 5)
 
1446
        self.prepare_index(index, node_ref_lists=0, key_length=1,
 
1447
                           key_count=1000, row_lengths=[1, 9],
 
1448
                           cached_offsets=[0, 1, 2, 5, 6])
 
1449
        # It should fill the remaining nodes, regardless of the one requested
 
1450
        self.assertExpandOffsets([3, 4, 7, 8, 9], index, [3])
 
1451
        self.assertExpandOffsets([3, 4, 7, 8, 9], index, [8])
 
1452
        self.assertExpandOffsets([3, 4, 7, 8, 9], index, [9])
 
1453
 
 
1454
    def test_no_root_node(self):
 
1455
        index = self.make_index(4096*10, 5)
 
1456
        self.assertExpandOffsets([0], index, [0])
 
1457
 
 
1458
    def test_include_neighbors(self):
 
1459
        index = self.make_100_node_index()
 
1460
        # We expand in both directions, until we have at least 'recommended'
 
1461
        # pages
 
1462
        self.assertExpandOffsets([9, 10, 11, 12, 13, 14, 15], index, [12])
 
1463
        self.assertExpandOffsets([88, 89, 90, 91, 92, 93, 94], index, [91])
 
1464
        # If we hit an 'edge' we continue in the other direction
 
1465
        self.assertExpandOffsets([1, 2, 3, 4, 5, 6], index, [2])
 
1466
        self.assertExpandOffsets([94, 95, 96, 97, 98, 99], index, [98])
 
1467
 
 
1468
        # Requesting many nodes will expand all locations equally
 
1469
        self.assertExpandOffsets([1, 2, 3, 80, 81, 82], index, [2, 81])
 
1470
        self.assertExpandOffsets([1, 2, 3, 9, 10, 11, 80, 81, 82], index,
 
1471
                               [2, 10, 81])
 
1472
 
 
1473
    def test_stop_at_cached(self):
 
1474
        index = self.make_100_node_index()
 
1475
        self.set_cached_offsets(index, [0, 10, 19])
 
1476
        self.assertExpandOffsets([11, 12, 13, 14, 15, 16], index, [11])
 
1477
        self.assertExpandOffsets([11, 12, 13, 14, 15, 16], index, [12])
 
1478
        self.assertExpandOffsets([12, 13, 14, 15, 16, 17, 18], index, [15])
 
1479
        self.assertExpandOffsets([13, 14, 15, 16, 17, 18], index, [16])
 
1480
        self.assertExpandOffsets([13, 14, 15, 16, 17, 18], index, [17])
 
1481
        self.assertExpandOffsets([13, 14, 15, 16, 17, 18], index, [18])
 
1482
 
 
1483
    def test_cannot_fully_expand(self):
 
1484
        index = self.make_100_node_index()
 
1485
        self.set_cached_offsets(index, [0, 10, 12])
 
1486
        # We don't go into an endless loop if we are bound by cached nodes
 
1487
        self.assertExpandOffsets([11], index, [11])
 
1488
 
 
1489
    def test_overlap(self):
 
1490
        index = self.make_100_node_index()
 
1491
        self.assertExpandOffsets([10, 11, 12, 13, 14, 15], index, [12, 13])
 
1492
        self.assertExpandOffsets([10, 11, 12, 13, 14, 15], index, [11, 14])
 
1493
 
 
1494
    def test_stay_within_layer(self):
 
1495
        index = self.make_1000_node_index()
 
1496
        # When expanding a request, we won't read nodes from the next layer
 
1497
        self.assertExpandOffsets([1, 2, 3, 4], index, [2])
 
1498
        self.assertExpandOffsets([6, 7, 8, 9], index, [6])
 
1499
        self.assertExpandOffsets([6, 7, 8, 9], index, [9])
 
1500
        self.assertExpandOffsets([10, 11, 12, 13, 14, 15], index, [10])
 
1501
        self.assertExpandOffsets([10, 11, 12, 13, 14, 15, 16], index, [13])
 
1502
 
 
1503
        self.set_cached_offsets(index, [0, 4, 12])
 
1504
        self.assertExpandOffsets([5, 6, 7, 8, 9], index, [7])
 
1505
        self.assertExpandOffsets([10, 11], index, [11])
 
1506
 
 
1507
    def test_small_requests_unexpanded(self):
 
1508
        index = self.make_100_node_index()
 
1509
        self.set_cached_offsets(index, [0])
 
1510
        self.assertExpandOffsets([1], index, [1])
 
1511
        self.assertExpandOffsets([50], index, [50])
 
1512
        # If we request more than one node, then we'll expand
 
1513
        self.assertExpandOffsets([49, 50, 51, 59, 60, 61], index, [50, 60])
 
1514
 
 
1515
        # The first pass does not expand
 
1516
        index = self.make_1000_node_index()
 
1517
        self.set_cached_offsets(index, [0])
 
1518
        self.assertExpandOffsets([1], index, [1])
 
1519
        self.set_cached_offsets(index, [0, 1])
 
1520
        self.assertExpandOffsets([100], index, [100])
 
1521
        self.set_cached_offsets(index, [0, 1, 100])
 
1522
        # But after the first depth, we will expand
 
1523
        self.assertExpandOffsets([2, 3, 4, 5, 6, 7], index, [2])
 
1524
        self.assertExpandOffsets([2, 3, 4, 5, 6, 7], index, [4])
 
1525
        self.set_cached_offsets(index, [0, 1, 2, 3, 4, 5, 6, 7, 100])
 
1526
        self.assertExpandOffsets([102, 103, 104, 105, 106, 107, 108], index,
 
1527
                                 [105])