← 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: 2010-09-01 08:02:42 UTC
  • mfrom: (5390.3.3 faster-revert-593560)
  • Revision ID: pqm@pqm.ubuntu.com-20100901080242-esg62ody4frwmy66
(spiv) Avoid repeatedly calling self.target.all_file_ids() in
 InterTree.iter_changes. (Andrew Bennetts)

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, 2009, 2010 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
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
34
    condition_isinstance,
 
35
    multiply_tests,
33
36
    split_suite_by_condition,
34
37
    )
35
 
from bzrlib.transport import get_transport
36
38
 
37
39
 
38
40
def load_tests(standard_tests, module, loader):
39
41
    # parameterise the TestBTreeNodes tests
40
42
    node_tests, others = split_suite_by_condition(standard_tests,
41
43
        condition_isinstance(TestBTreeNodes))
42
 
    applier = TestScenarioApplier()
43
44
    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()
 
45
    scenarios = [('python', {'parse_btree': py_module})]
 
46
    if compiled_btreeparser_feature.available():
 
47
        scenarios.append(('C', {'parse_btree':
 
48
                                compiled_btreeparser_feature.module}))
 
49
    return multiply_tests(node_tests, scenarios, others)
 
50
 
 
51
 
 
52
compiled_btreeparser_feature = tests.ModuleAvailableFeature(
 
53
                                'bzrlib._btree_serializer_pyx')
66
54
 
67
55
 
68
56
class BTreeTestCase(TestCaseWithTransport):
71
59
 
72
60
    def setUp(self):
73
61
        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
 
62
        self.overrideAttr(btree_index, '_RESERVED_HEADER_BYTES', 100)
79
63
 
80
64
    def make_nodes(self, count, key_elements, reference_lists):
81
65
        """Generate count*key_elements sample nodes."""
115
99
 
116
100
    def shrink_page_size(self):
117
101
        """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)
 
102
        self.overrideAttr(btree_index, '_PAGE_SIZE')
122
103
        btree_index._PAGE_SIZE = 2048
123
104
 
124
105
 
125
106
class TestBTreeBuilder(BTreeTestCase):
126
107
 
 
108
    def test_clear_cache(self):
 
109
        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)
 
110
        # This is a no-op, but we need the api to be consistent with other
 
111
        # BTreeGraphIndex apis.
 
112
        builder.clear_cache()
 
113
 
127
114
    def test_empty_1_0(self):
128
115
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
129
116
        # NamedTemporaryFile dies on builder.finish().read(). weird.
155
142
        temp_file = builder.finish()
156
143
        content = temp_file.read()
157
144
        del temp_file
158
 
        self.assertEqual(158, len(content))
 
145
        self.assertEqual(131, len(content))
159
146
        self.assertEqual(
160
147
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"
161
148
            "row_lengths=1\n",
179
166
        temp_file = builder.finish()
180
167
        content = temp_file.read()
181
168
        del temp_file
182
 
        self.assertEqual(264, len(content))
 
169
        self.assertEqual(238, len(content))
183
170
        self.assertEqual(
184
171
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"
185
172
            "row_lengths=1\n",
229
216
        leaf1_bytes = zlib.decompress(leaf1)
230
217
        sorted_node_keys = sorted(node[0] for node in nodes)
231
218
        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))
 
219
        self.assertEqual(231, len(node))
 
220
        self.assertEqual(sorted_node_keys[:231], node.all_keys())
234
221
        leaf2_bytes = zlib.decompress(leaf2)
235
222
        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))
 
223
        self.assertEqual(400 - 231, len(node))
 
224
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
238
225
 
239
226
    def test_last_page_rounded_1_layer(self):
240
227
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
245
232
        temp_file = builder.finish()
246
233
        content = temp_file.read()
247
234
        del temp_file
248
 
        self.assertEqual(181, len(content))
 
235
        self.assertEqual(155, len(content))
249
236
        self.assertEqual(
250
237
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
251
238
            "row_lengths=1\n",
254
241
        leaf2 = content[74:]
255
242
        leaf2_bytes = zlib.decompress(leaf2)
256
243
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
257
 
        self.assertEqual(10, len(node.keys))
 
244
        self.assertEqual(10, len(node))
258
245
        sorted_node_keys = sorted(node[0] for node in nodes)
259
 
        self.assertEqual(sorted_node_keys, sorted(node.keys))
 
246
        self.assertEqual(sorted_node_keys, node.all_keys())
260
247
 
261
248
    def test_last_page_not_rounded_2_layer(self):
262
249
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
276
263
        leaf2 = content[8192:]
277
264
        leaf2_bytes = zlib.decompress(leaf2)
278
265
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
279
 
        self.assertEqual(400 - 231, len(node.keys))
 
266
        self.assertEqual(400 - 231, len(node))
280
267
        sorted_node_keys = sorted(node[0] for node in nodes)
281
 
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
 
268
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
282
269
 
283
270
    def test_three_level_tree_details(self):
284
271
        # The left most pointer in the second internal node in a row should
293
280
 
294
281
        for node in nodes:
295
282
            builder.add_node(*node)
296
 
        transport = get_transport('trace+' + self.get_url(''))
297
 
        size = transport.put_file('index', self.time(builder.finish))
 
283
        t = transport.get_transport('trace+' + self.get_url(''))
 
284
        size = t.put_file('index', self.time(builder.finish))
298
285
        del builder
299
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
286
        index = btree_index.BTreeGraphIndex(t, 'index', size)
300
287
        # Seed the metadata, we're using internal calls now.
301
288
        index.key_count()
302
289
        self.assertEqual(3, len(index._row_lengths),
315
302
        # in the second node it points at
316
303
        pos = index._row_offsets[2] + internal_node2.offset + 1
317
304
        leaf = index._get_leaf_nodes([pos])[pos]
318
 
        self.assertTrue(internal_node2.keys[0] in leaf.keys)
 
305
        self.assertTrue(internal_node2.keys[0] in leaf)
319
306
 
320
307
    def test_2_leaves_2_2(self):
321
308
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
353
340
        # Test the parts of the index that take up memory are doing so
354
341
        # predictably.
355
342
        self.assertEqual(1, len(builder._nodes))
356
 
        self.assertEqual(1, len(builder._keys))
357
343
        self.assertIs(None, builder._nodes_by_key)
358
344
        builder.add_node(*nodes[1])
359
345
        self.assertEqual(0, len(builder._nodes))
360
 
        self.assertEqual(0, len(builder._keys))
361
346
        self.assertIs(None, builder._nodes_by_key)
362
347
        self.assertEqual(1, len(builder._backing_indices))
363
348
        self.assertEqual(2, builder._backing_indices[0].key_count())
364
349
        # now back to memory
365
350
        builder.add_node(*nodes[2])
366
351
        self.assertEqual(1, len(builder._nodes))
367
 
        self.assertEqual(1, len(builder._keys))
368
352
        self.assertIs(None, builder._nodes_by_key)
369
353
        # And spills to a second backing index combing all
370
354
        builder.add_node(*nodes[3])
371
355
        self.assertEqual(0, len(builder._nodes))
372
 
        self.assertEqual(0, len(builder._keys))
373
356
        self.assertIs(None, builder._nodes_by_key)
374
357
        self.assertEqual(2, len(builder._backing_indices))
375
358
        self.assertEqual(None, builder._backing_indices[0])
378
361
        builder.add_node(*nodes[4])
379
362
        builder.add_node(*nodes[5])
380
363
        self.assertEqual(0, len(builder._nodes))
381
 
        self.assertEqual(0, len(builder._keys))
382
364
        self.assertIs(None, builder._nodes_by_key)
383
365
        self.assertEqual(2, len(builder._backing_indices))
384
366
        self.assertEqual(2, builder._backing_indices[0].key_count())
427
409
        self.assertEqual(None, builder._backing_indices[2])
428
410
        self.assertEqual(16, builder._backing_indices[3].key_count())
429
411
        # Now finish, and check we got a correctly ordered tree
 
412
        t = self.get_transport('')
 
413
        size = t.put_file('index', builder.finish())
 
414
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
415
        nodes = list(index.iter_all_entries())
 
416
        self.assertEqual(sorted(nodes), nodes)
 
417
        self.assertEqual(16, len(nodes))
 
418
 
 
419
    def test_spill_index_stress_1_1_no_combine(self):
 
420
        builder = btree_index.BTreeBuilder(key_elements=1, spill_at=2)
 
421
        builder.set_optimize(for_size=False, combine_backing_indices=False)
 
422
        nodes = [node[0:2] for node in self.make_nodes(16, 1, 0)]
 
423
        builder.add_node(*nodes[0])
 
424
        # Test the parts of the index that take up memory are doing so
 
425
        # predictably.
 
426
        self.assertEqual(1, len(builder._nodes))
 
427
        self.assertIs(None, builder._nodes_by_key)
 
428
        builder.add_node(*nodes[1])
 
429
        self.assertEqual(0, len(builder._nodes))
 
430
        self.assertIs(None, builder._nodes_by_key)
 
431
        self.assertEqual(1, len(builder._backing_indices))
 
432
        self.assertEqual(2, builder._backing_indices[0].key_count())
 
433
        # now back to memory
 
434
        builder.add_node(*nodes[2])
 
435
        self.assertEqual(1, len(builder._nodes))
 
436
        self.assertIs(None, builder._nodes_by_key)
 
437
        # And spills to a second backing index but doesn't combine
 
438
        builder.add_node(*nodes[3])
 
439
        self.assertEqual(0, len(builder._nodes))
 
440
        self.assertIs(None, builder._nodes_by_key)
 
441
        self.assertEqual(2, len(builder._backing_indices))
 
442
        for backing_index in builder._backing_indices:
 
443
            self.assertEqual(2, backing_index.key_count())
 
444
        # The next spills to the 3rd slot
 
445
        builder.add_node(*nodes[4])
 
446
        builder.add_node(*nodes[5])
 
447
        self.assertEqual(0, len(builder._nodes))
 
448
        self.assertIs(None, builder._nodes_by_key)
 
449
        self.assertEqual(3, len(builder._backing_indices))
 
450
        for backing_index in builder._backing_indices:
 
451
            self.assertEqual(2, backing_index.key_count())
 
452
        # Now spill a few more, and check that we don't combine
 
453
        builder.add_node(*nodes[6])
 
454
        builder.add_node(*nodes[7])
 
455
        builder.add_node(*nodes[8])
 
456
        builder.add_node(*nodes[9])
 
457
        builder.add_node(*nodes[10])
 
458
        builder.add_node(*nodes[11])
 
459
        builder.add_node(*nodes[12])
 
460
        self.assertEqual(6, len(builder._backing_indices))
 
461
        for backing_index in builder._backing_indices:
 
462
            self.assertEqual(2, backing_index.key_count())
 
463
        # Test that memory and disk are both used for query methods; and that
 
464
        # None is skipped over happily.
 
465
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
 
466
            list(builder.iter_all_entries()))
 
467
        # Two nodes - one memory one disk
 
468
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
469
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
470
        self.assertEqual(13, builder.key_count())
 
471
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
472
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
473
        builder.add_node(*nodes[13])
 
474
        builder.add_node(*nodes[14])
 
475
        builder.add_node(*nodes[15])
 
476
        self.assertEqual(8, len(builder._backing_indices))
 
477
        for backing_index in builder._backing_indices:
 
478
            self.assertEqual(2, backing_index.key_count())
 
479
        # Now finish, and check we got a correctly ordered tree
430
480
        transport = self.get_transport('')
431
481
        size = transport.put_file('index', builder.finish())
432
482
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
440
490
        self.assertTrue(builder._optimize_for_size)
441
491
        builder.set_optimize(for_size=False)
442
492
        self.assertFalse(builder._optimize_for_size)
 
493
        # test that we can set combine_backing_indices without effecting
 
494
        # _optimize_for_size
 
495
        obj = object()
 
496
        builder._optimize_for_size = obj
 
497
        builder.set_optimize(combine_backing_indices=False)
 
498
        self.assertFalse(builder._combine_backing_indices)
 
499
        self.assertIs(obj, builder._optimize_for_size)
 
500
        builder.set_optimize(combine_backing_indices=True)
 
501
        self.assertTrue(builder._combine_backing_indices)
 
502
        self.assertIs(obj, builder._optimize_for_size)
443
503
 
444
504
    def test_spill_index_stress_2_2(self):
445
505
        # test that references and longer keys don't confuse things.
449
509
        builder.add_node(*nodes[0])
450
510
        # Test the parts of the index that take up memory are doing so
451
511
        # predictably.
452
 
        self.assertEqual(1, len(builder._keys))
453
512
        self.assertEqual(1, len(builder._nodes))
454
513
        self.assertIs(None, builder._nodes_by_key)
455
514
        builder.add_node(*nodes[1])
456
 
        self.assertEqual(0, len(builder._keys))
457
515
        self.assertEqual(0, len(builder._nodes))
458
516
        self.assertIs(None, builder._nodes_by_key)
459
517
        self.assertEqual(1, len(builder._backing_indices))
462
520
        old = dict(builder._get_nodes_by_key()) #Build up the nodes by key dict
463
521
        builder.add_node(*nodes[2])
464
522
        self.assertEqual(1, len(builder._nodes))
465
 
        self.assertEqual(1, len(builder._keys))
466
523
        self.assertIsNot(None, builder._nodes_by_key)
467
524
        self.assertNotEqual({}, builder._nodes_by_key)
468
525
        # We should have a new entry
470
527
        # And spills to a second backing index combing all
471
528
        builder.add_node(*nodes[3])
472
529
        self.assertEqual(0, len(builder._nodes))
473
 
        self.assertEqual(0, len(builder._keys))
474
530
        self.assertIs(None, builder._nodes_by_key)
475
531
        self.assertEqual(2, len(builder._backing_indices))
476
532
        self.assertEqual(None, builder._backing_indices[0])
479
535
        builder.add_node(*nodes[4])
480
536
        builder.add_node(*nodes[5])
481
537
        self.assertEqual(0, len(builder._nodes))
482
 
        self.assertEqual(0, len(builder._keys))
483
538
        self.assertIs(None, builder._nodes_by_key)
484
539
        self.assertEqual(2, len(builder._backing_indices))
485
540
        self.assertEqual(2, builder._backing_indices[0].key_count())
552
607
        for key, value, references in nodes:
553
608
            builder.add_node(key, value, references)
554
609
        stream = builder.finish()
555
 
        trans = get_transport('trace+' + self.get_url())
 
610
        trans = transport.get_transport('trace+' + self.get_url())
556
611
        size = trans.put_file('index', stream)
557
612
        return btree_index.BTreeGraphIndex(trans, 'index', size)
558
613
 
 
614
    def make_index_with_offset(self, ref_lists=1, key_elements=1, nodes=[],
 
615
                               offset=0):
 
616
        builder = btree_index.BTreeBuilder(key_elements=key_elements,
 
617
                                           reference_lists=ref_lists)
 
618
        builder.add_nodes(nodes)
 
619
        transport = self.get_transport('')
 
620
        # NamedTemporaryFile dies on builder.finish().read(). weird.
 
621
        temp_file = builder.finish()
 
622
        content = temp_file.read()
 
623
        del temp_file
 
624
        size = len(content)
 
625
        transport.put_bytes('index', (' '*offset)+content)
 
626
        return btree_index.BTreeGraphIndex(transport, 'index', size=size,
 
627
                                           offset=offset)
 
628
 
 
629
    def test_clear_cache(self):
 
630
        nodes = self.make_nodes(160, 2, 2)
 
631
        index = self.make_index(ref_lists=2, key_elements=2, nodes=nodes)
 
632
        self.assertEqual(1, len(list(index.iter_entries([nodes[30][0]]))))
 
633
        self.assertEqual([1, 4], index._row_lengths)
 
634
        self.assertIsNot(None, index._root_node)
 
635
        internal_node_pre_clear = index._internal_node_cache.keys()
 
636
        self.assertTrue(len(index._leaf_node_cache) > 0)
 
637
        index.clear_cache()
 
638
        # We don't touch _root_node or _internal_node_cache, both should be
 
639
        # small, and can save a round trip or two
 
640
        self.assertIsNot(None, index._root_node)
 
641
        # NOTE: We don't want to affect the _internal_node_cache, as we expect
 
642
        #       it will be small, and if we ever do touch this index again, it
 
643
        #       will save round-trips.  This assertion isn't very strong,
 
644
        #       becuase without a 3-level index, we don't have any internal
 
645
        #       nodes cached.
 
646
        self.assertEqual(internal_node_pre_clear,
 
647
                         index._internal_node_cache.keys())
 
648
        self.assertEqual(0, len(index._leaf_node_cache))
 
649
 
559
650
    def test_trivial_constructor(self):
560
 
        transport = get_transport('trace+' + self.get_url(''))
561
 
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
 
651
        t = transport.get_transport('trace+' + self.get_url(''))
 
652
        index = btree_index.BTreeGraphIndex(t, 'index', None)
562
653
        # Checks the page size at load, but that isn't logged yet.
563
 
        self.assertEqual([], transport._activity)
 
654
        self.assertEqual([], t._activity)
564
655
 
565
656
    def test_with_size_constructor(self):
566
 
        transport = get_transport('trace+' + self.get_url(''))
567
 
        index = btree_index.BTreeGraphIndex(transport, 'index', 1)
 
657
        t = transport.get_transport('trace+' + self.get_url(''))
 
658
        index = btree_index.BTreeGraphIndex(t, 'index', 1)
568
659
        # Checks the page size at load, but that isn't logged yet.
569
 
        self.assertEqual([], transport._activity)
 
660
        self.assertEqual([], t._activity)
570
661
 
571
662
    def test_empty_key_count_no_size(self):
572
663
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
573
 
        transport = get_transport('trace+' + self.get_url(''))
574
 
        transport.put_file('index', builder.finish())
575
 
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
576
 
        del transport._activity[:]
577
 
        self.assertEqual([], transport._activity)
 
664
        t = transport.get_transport('trace+' + self.get_url(''))
 
665
        t.put_file('index', builder.finish())
 
666
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
667
        del t._activity[:]
 
668
        self.assertEqual([], t._activity)
578
669
        self.assertEqual(0, index.key_count())
579
670
        # The entire index should have been requested (as we generally have the
580
671
        # size available, and doing many small readvs is inappropriate).
581
672
        # We can't tell how much was actually read here, but - check the code.
582
 
        self.assertEqual([('get', 'index')], transport._activity)
 
673
        self.assertEqual([('get', 'index')], t._activity)
583
674
 
584
675
    def test_empty_key_count(self):
585
676
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
586
 
        transport = get_transport('trace+' + self.get_url(''))
587
 
        size = transport.put_file('index', builder.finish())
 
677
        t = transport.get_transport('trace+' + self.get_url(''))
 
678
        size = t.put_file('index', builder.finish())
588
679
        self.assertEqual(72, size)
589
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
590
 
        del transport._activity[:]
591
 
        self.assertEqual([], transport._activity)
 
680
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
681
        del t._activity[:]
 
682
        self.assertEqual([], t._activity)
592
683
        self.assertEqual(0, index.key_count())
593
684
        # The entire index should have been read, as 4K > size
594
685
        self.assertEqual([('readv', 'index', [(0, 72)], False, None)],
595
 
            transport._activity)
 
686
                         t._activity)
596
687
 
597
688
    def test_non_empty_key_count_2_2(self):
598
689
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
599
690
        nodes = self.make_nodes(35, 2, 2)
600
691
        for node in nodes:
601
692
            builder.add_node(*node)
602
 
        transport = get_transport('trace+' + self.get_url(''))
603
 
        size = transport.put_file('index', builder.finish())
604
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
605
 
        del transport._activity[:]
606
 
        self.assertEqual([], transport._activity)
 
693
        t = transport.get_transport('trace+' + self.get_url(''))
 
694
        size = t.put_file('index', builder.finish())
 
695
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
696
        del t._activity[:]
 
697
        self.assertEqual([], t._activity)
607
698
        self.assertEqual(70, index.key_count())
608
699
        # The entire index should have been read, as it is one page long.
609
700
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
610
 
            transport._activity)
611
 
        self.assertEqual(1199, size)
 
701
            t._activity)
 
702
        self.assertEqual(1173, size)
 
703
 
 
704
    def test_with_offset_no_size(self):
 
705
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
 
706
                                            offset=1234,
 
707
                                            nodes=self.make_nodes(200, 1, 1))
 
708
        index._size = None # throw away the size info
 
709
        self.assertEqual(200, index.key_count())
 
710
 
 
711
    def test_with_small_offset(self):
 
712
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
 
713
                                            offset=1234,
 
714
                                            nodes=self.make_nodes(200, 1, 1))
 
715
        self.assertEqual(200, index.key_count())
 
716
 
 
717
    def test_with_large_offset(self):
 
718
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
 
719
                                            offset=123456,
 
720
                                            nodes=self.make_nodes(200, 1, 1))
 
721
        self.assertEqual(200, index.key_count())
612
722
 
613
723
    def test__read_nodes_no_size_one_page_reads_once(self):
614
724
        self.make_index(nodes=[(('key',), 'value', ())])
615
 
        trans = get_transport('trace+' + self.get_url())
 
725
        trans = transport.get_transport('trace+' + self.get_url())
616
726
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
617
727
        del trans._activity[:]
618
728
        nodes = dict(index._read_nodes([0]))
619
729
        self.assertEqual([0], nodes.keys())
620
730
        node = nodes[0]
621
 
        self.assertEqual([('key',)], node.keys.keys())
 
731
        self.assertEqual([('key',)], node.all_keys())
622
732
        self.assertEqual([('get', 'index')], trans._activity)
623
733
 
624
734
    def test__read_nodes_no_size_multiple_pages(self):
626
736
        index.key_count()
627
737
        num_pages = index._row_offsets[-1]
628
738
        # Reopen with a traced transport and no size
629
 
        trans = get_transport('trace+' + self.get_url())
 
739
        trans = transport.get_transport('trace+' + self.get_url())
630
740
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
631
741
        del trans._activity[:]
632
742
        nodes = dict(index._read_nodes([0]))
637
747
        nodes = self.make_nodes(160, 2, 2)
638
748
        for node in nodes:
639
749
            builder.add_node(*node)
640
 
        transport = get_transport('trace+' + self.get_url(''))
641
 
        size = transport.put_file('index', builder.finish())
 
750
        t = transport.get_transport('trace+' + self.get_url(''))
 
751
        size = t.put_file('index', builder.finish())
642
752
        self.assertEqual(17692, size)
643
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
644
 
        del transport._activity[:]
645
 
        self.assertEqual([], transport._activity)
 
753
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
754
        del t._activity[:]
 
755
        self.assertEqual([], t._activity)
646
756
        self.assertEqual(320, index.key_count())
647
757
        # The entire index should not have been read.
648
758
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None)],
649
 
            transport._activity)
 
759
                         t._activity)
650
760
 
651
761
    def test_validate_one_page(self):
652
762
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
653
763
        nodes = self.make_nodes(45, 2, 2)
654
764
        for node in nodes:
655
765
            builder.add_node(*node)
656
 
        transport = get_transport('trace+' + self.get_url(''))
657
 
        size = transport.put_file('index', builder.finish())
658
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
659
 
        del transport._activity[:]
660
 
        self.assertEqual([], transport._activity)
 
766
        t = transport.get_transport('trace+' + self.get_url(''))
 
767
        size = t.put_file('index', builder.finish())
 
768
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
769
        del t._activity[:]
 
770
        self.assertEqual([], t._activity)
661
771
        index.validate()
662
772
        # The entire index should have been read linearly.
663
773
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
664
 
            transport._activity)
665
 
        self.assertEqual(1514, size)
 
774
                         t._activity)
 
775
        self.assertEqual(1488, size)
666
776
 
667
777
    def test_validate_two_pages(self):
668
778
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
669
779
        nodes = self.make_nodes(80, 2, 2)
670
780
        for node in nodes:
671
781
            builder.add_node(*node)
672
 
        transport = get_transport('trace+' + self.get_url(''))
673
 
        size = transport.put_file('index', builder.finish())
 
782
        t = transport.get_transport('trace+' + self.get_url(''))
 
783
        size = t.put_file('index', builder.finish())
674
784
        # Root page, 2 leaf pages
675
785
        self.assertEqual(9339, size)
676
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
677
 
        del transport._activity[:]
678
 
        self.assertEqual([], transport._activity)
 
786
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
787
        del t._activity[:]
 
788
        self.assertEqual([], t._activity)
679
789
        index.validate()
680
790
        # The entire index should have been read linearly.
681
 
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
682
 
            ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
683
 
            transport._activity)
 
791
        self.assertEqual(
 
792
            [('readv', 'index', [(0, 4096)], False, None),
 
793
             ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
 
794
            t._activity)
684
795
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
685
796
        # node and make validate find them.
686
797
 
687
798
    def test_eq_ne(self):
688
799
        # two indices are equal when constructed with the same parameters:
689
 
        transport1 = get_transport('trace+' + self.get_url(''))
690
 
        transport2 = get_transport(self.get_url(''))
691
 
        self.assertTrue(
692
 
            btree_index.BTreeGraphIndex(transport1, 'index', None) ==
693
 
            btree_index.BTreeGraphIndex(transport1, 'index', None))
694
 
        self.assertTrue(
695
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
696
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
697
 
        self.assertFalse(
698
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
699
 
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
700
 
        self.assertFalse(
701
 
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) ==
702
 
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
703
 
        self.assertFalse(
704
 
            btree_index.BTreeGraphIndex(transport1, 'index', 10) ==
705
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
706
 
        self.assertFalse(
707
 
            btree_index.BTreeGraphIndex(transport1, 'index', None) !=
708
 
            btree_index.BTreeGraphIndex(transport1, 'index', None))
709
 
        self.assertFalse(
710
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
711
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
712
 
        self.assertTrue(
713
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
714
 
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
715
 
        self.assertTrue(
716
 
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) !=
717
 
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
718
 
        self.assertTrue(
719
 
            btree_index.BTreeGraphIndex(transport1, 'index', 10) !=
720
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
 
800
        t1 = transport.get_transport('trace+' + self.get_url(''))
 
801
        t2 = transport.get_transport(self.get_url(''))
 
802
        self.assertTrue(
 
803
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
 
804
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
805
        self.assertTrue(
 
806
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
807
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
808
        self.assertFalse(
 
809
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
810
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
811
        self.assertFalse(
 
812
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) ==
 
813
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
814
        self.assertFalse(
 
815
            btree_index.BTreeGraphIndex(t1, 'index', 10) ==
 
816
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
817
        self.assertFalse(
 
818
            btree_index.BTreeGraphIndex(t1, 'index', None) !=
 
819
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
820
        self.assertFalse(
 
821
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
822
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
823
        self.assertTrue(
 
824
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
825
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
826
        self.assertTrue(
 
827
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) !=
 
828
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
829
        self.assertTrue(
 
830
            btree_index.BTreeGraphIndex(t1, 'index', 10) !=
 
831
            btree_index.BTreeGraphIndex(t1, 'index', 20))
721
832
 
722
833
    def test_iter_all_only_root_no_size(self):
723
834
        self.make_index(nodes=[(('key',), 'value', ())])
724
 
        trans = get_transport('trace+' + self.get_url(''))
725
 
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
726
 
        del trans._activity[:]
 
835
        t = transport.get_transport('trace+' + self.get_url(''))
 
836
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
837
        del t._activity[:]
727
838
        self.assertEqual([(('key',), 'value')],
728
839
                         [x[1:] for x in index.iter_all_entries()])
729
 
        self.assertEqual([('get', 'index')], trans._activity)
 
840
        self.assertEqual([('get', 'index')], t._activity)
730
841
 
731
842
    def test_iter_all_entries_reads(self):
732
843
        # iterating all entries reads the header, then does a linear
738
849
        nodes = self.make_nodes(10000, 2, 2)
739
850
        for node in nodes:
740
851
            builder.add_node(*node)
741
 
        transport = get_transport('trace+' + self.get_url(''))
742
 
        size = transport.put_file('index', builder.finish())
 
852
        t = transport.get_transport('trace+' + self.get_url(''))
 
853
        size = t.put_file('index', builder.finish())
743
854
        self.assertEqual(1303220, size, 'number of expected bytes in the'
744
855
                                        ' output changed')
745
856
        page_size = btree_index._PAGE_SIZE
746
857
        del builder
747
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
748
 
        del transport._activity[:]
749
 
        self.assertEqual([], transport._activity)
 
858
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
859
        del t._activity[:]
 
860
        self.assertEqual([], t._activity)
750
861
        found_nodes = self.time(list, index.iter_all_entries())
751
862
        bare_nodes = []
752
863
        for node in found_nodes:
773
884
        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
774
885
        expected = [('readv', 'index', [(0, page_size)], False, None),
775
886
             ('readv',  'index', readv_request, False, None)]
776
 
        if expected != transport._activity:
 
887
        if expected != t._activity:
777
888
            self.assertEqualDiff(pprint.pformat(expected),
778
889
                                 pprint.pformat(transport._activity))
779
890
 
793
904
        nodes = self.make_nodes(160, 2, 2)
794
905
        for node in nodes:
795
906
            builder.add_node(*node)
796
 
        transport = get_transport('trace+' + self.get_url(''))
797
 
        size = transport.put_file('index', builder.finish())
 
907
        t = transport.get_transport('trace+' + self.get_url(''))
 
908
        size = t.put_file('index', builder.finish())
798
909
        del builder
799
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
800
 
        del transport._activity[:]
801
 
        self.assertEqual([], transport._activity)
 
910
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
911
        del t._activity[:]
 
912
        self.assertEqual([], t._activity)
802
913
        # search for one key
803
914
        found_nodes = list(index.iter_entries([nodes[30][0]]))
804
915
        bare_nodes = []
812
923
        # Should have read the root node, then one leaf page:
813
924
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
814
925
             ('readv',  'index', [(8192, 4096), ], False, None)],
815
 
            transport._activity)
 
926
            t._activity)
816
927
 
817
928
    def test_iter_key_prefix_1_element_key_None(self):
818
929
        index = self.make_index()
869
980
            (index, ('name', 'fin2'), 'beta', ((), ))]),
870
981
            set(index.iter_entries_prefix([('name', None)])))
871
982
 
 
983
    # XXX: external_references tests are duplicated in test_index.  We
 
984
    # probably should have per_graph_index tests...
 
985
    def test_external_references_no_refs(self):
 
986
        index = self.make_index(ref_lists=0, nodes=[])
 
987
        self.assertRaises(ValueError, index.external_references, 0)
 
988
 
 
989
    def test_external_references_no_results(self):
 
990
        index = self.make_index(ref_lists=1, nodes=[
 
991
            (('key',), 'value', ([],))])
 
992
        self.assertEqual(set(), index.external_references(0))
 
993
 
 
994
    def test_external_references_missing_ref(self):
 
995
        missing_key = ('missing',)
 
996
        index = self.make_index(ref_lists=1, nodes=[
 
997
            (('key',), 'value', ([missing_key],))])
 
998
        self.assertEqual(set([missing_key]), index.external_references(0))
 
999
 
 
1000
    def test_external_references_multiple_ref_lists(self):
 
1001
        missing_key = ('missing',)
 
1002
        index = self.make_index(ref_lists=2, nodes=[
 
1003
            (('key',), 'value', ([], [missing_key]))])
 
1004
        self.assertEqual(set([]), index.external_references(0))
 
1005
        self.assertEqual(set([missing_key]), index.external_references(1))
 
1006
 
 
1007
    def test_external_references_two_records(self):
 
1008
        index = self.make_index(ref_lists=1, nodes=[
 
1009
            (('key-1',), 'value', ([('key-2',)],)),
 
1010
            (('key-2',), 'value', ([],)),
 
1011
            ])
 
1012
        self.assertEqual(set([]), index.external_references(0))
 
1013
 
 
1014
    def test__find_ancestors_one_page(self):
 
1015
        key1 = ('key-1',)
 
1016
        key2 = ('key-2',)
 
1017
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1018
            (key1, 'value', ([key2],)),
 
1019
            (key2, 'value', ([],)),
 
1020
            ])
 
1021
        parent_map = {}
 
1022
        missing_keys = set()
 
1023
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
 
1024
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
 
1025
        self.assertEqual(set(), missing_keys)
 
1026
        self.assertEqual(set(), search_keys)
 
1027
 
 
1028
    def test__find_ancestors_one_page_w_missing(self):
 
1029
        key1 = ('key-1',)
 
1030
        key2 = ('key-2',)
 
1031
        key3 = ('key-3',)
 
1032
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1033
            (key1, 'value', ([key2],)),
 
1034
            (key2, 'value', ([],)),
 
1035
            ])
 
1036
        parent_map = {}
 
1037
        missing_keys = set()
 
1038
        search_keys = index._find_ancestors([key2, key3], 0, parent_map,
 
1039
                                            missing_keys)
 
1040
        self.assertEqual({key2: ()}, parent_map)
 
1041
        # we know that key3 is missing because we read the page that it would
 
1042
        # otherwise be on
 
1043
        self.assertEqual(set([key3]), missing_keys)
 
1044
        self.assertEqual(set(), search_keys)
 
1045
 
 
1046
    def test__find_ancestors_one_parent_missing(self):
 
1047
        key1 = ('key-1',)
 
1048
        key2 = ('key-2',)
 
1049
        key3 = ('key-3',)
 
1050
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1051
            (key1, 'value', ([key2],)),
 
1052
            (key2, 'value', ([key3],)),
 
1053
            ])
 
1054
        parent_map = {}
 
1055
        missing_keys = set()
 
1056
        search_keys = index._find_ancestors([key1], 0, parent_map,
 
1057
                                            missing_keys)
 
1058
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1059
        self.assertEqual(set(), missing_keys)
 
1060
        # all we know is that key3 wasn't present on the page we were reading
 
1061
        # but if you look, the last key is key2 which comes before key3, so we
 
1062
        # don't know whether key3 would land on this page or not.
 
1063
        self.assertEqual(set([key3]), search_keys)
 
1064
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
 
1065
                                            missing_keys)
 
1066
        # passing it back in, we are sure it is 'missing'
 
1067
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1068
        self.assertEqual(set([key3]), missing_keys)
 
1069
        self.assertEqual(set([]), search_keys)
 
1070
 
 
1071
    def test__find_ancestors_dont_search_known(self):
 
1072
        key1 = ('key-1',)
 
1073
        key2 = ('key-2',)
 
1074
        key3 = ('key-3',)
 
1075
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1076
            (key1, 'value', ([key2],)),
 
1077
            (key2, 'value', ([key3],)),
 
1078
            (key3, 'value', ([],)),
 
1079
            ])
 
1080
        # We already know about key2, so we won't try to search for key3
 
1081
        parent_map = {key2: (key3,)}
 
1082
        missing_keys = set()
 
1083
        search_keys = index._find_ancestors([key1], 0, parent_map,
 
1084
                                            missing_keys)
 
1085
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1086
        self.assertEqual(set(), missing_keys)
 
1087
        self.assertEqual(set(), search_keys)
 
1088
 
 
1089
    def test__find_ancestors_multiple_pages(self):
 
1090
        # We need to use enough keys that we actually cause a split
 
1091
        start_time = 1249671539
 
1092
        email = "joebob@example.com"
 
1093
        nodes = []
 
1094
        ref_lists = ((),)
 
1095
        rev_keys = []
 
1096
        for i in xrange(400):
 
1097
            rev_id = '%s-%s-%s' % (email,
 
1098
                                   osutils.compact_date(start_time + i),
 
1099
                                   osutils.rand_chars(16))
 
1100
            rev_key = (rev_id,)
 
1101
            nodes.append((rev_key, 'value', ref_lists))
 
1102
            # We have a ref 'list' of length 1, with a list of parents, with 1
 
1103
            # parent which is a key
 
1104
            ref_lists = ((rev_key,),)
 
1105
            rev_keys.append(rev_key)
 
1106
        index = self.make_index(ref_lists=1, key_elements=1, nodes=nodes)
 
1107
        self.assertEqual(400, index.key_count())
 
1108
        self.assertEqual(3, len(index._row_offsets))
 
1109
        nodes = dict(index._read_nodes([1, 2]))
 
1110
        l1 = nodes[1]
 
1111
        l2 = nodes[2]
 
1112
        min_l2_key = l2.min_key
 
1113
        max_l1_key = l1.max_key
 
1114
        self.assertTrue(max_l1_key < min_l2_key)
 
1115
        parents_min_l2_key = l2[min_l2_key][1][0]
 
1116
        self.assertEqual((l1.max_key,), parents_min_l2_key)
 
1117
        # Now, whatever key we select that would fall on the second page,
 
1118
        # should give us all the parents until the page break
 
1119
        key_idx = rev_keys.index(min_l2_key)
 
1120
        next_key = rev_keys[key_idx+1]
 
1121
        # So now when we get the parent map, we should get the key we are
 
1122
        # looking for, min_l2_key, and then a reference to go look for the
 
1123
        # parent of that key
 
1124
        parent_map = {}
 
1125
        missing_keys = set()
 
1126
        search_keys = index._find_ancestors([next_key], 0, parent_map,
 
1127
                                            missing_keys)
 
1128
        self.assertEqual([min_l2_key, next_key], sorted(parent_map))
 
1129
        self.assertEqual(set(), missing_keys)
 
1130
        self.assertEqual(set([max_l1_key]), search_keys)
 
1131
        parent_map = {}
 
1132
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
 
1133
                                            missing_keys)
 
1134
        self.assertEqual(l1.all_keys(), sorted(parent_map))
 
1135
        self.assertEqual(set(), missing_keys)
 
1136
        self.assertEqual(set(), search_keys)
 
1137
 
 
1138
    def test__find_ancestors_empty_index(self):
 
1139
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[])
 
1140
        parent_map = {}
 
1141
        missing_keys = set()
 
1142
        search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
 
1143
                                            missing_keys)
 
1144
        self.assertEqual(set(), search_keys)
 
1145
        self.assertEqual({}, parent_map)
 
1146
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
 
1147
 
 
1148
    def test_supports_unlimited_cache(self):
 
1149
        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)
 
1150
        # We need enough nodes to cause a page split (so we have both an
 
1151
        # internal node and a couple leaf nodes. 500 seems to be enough.)
 
1152
        nodes = self.make_nodes(500, 1, 0)
 
1153
        for node in nodes:
 
1154
            builder.add_node(*node)
 
1155
        stream = builder.finish()
 
1156
        trans = transport.get_transport(self.get_url())
 
1157
        size = trans.put_file('index', stream)
 
1158
        index = btree_index.BTreeGraphIndex(trans, 'index', size)
 
1159
        self.assertEqual(500, index.key_count())
 
1160
        # We have an internal node
 
1161
        self.assertEqual(2, len(index._row_lengths))
 
1162
        # We have at least 2 leaf nodes
 
1163
        self.assertTrue(index._row_lengths[-1] >= 2)
 
1164
        self.assertIsInstance(index._leaf_node_cache, lru_cache.LRUCache)
 
1165
        self.assertEqual(btree_index._NODE_CACHE_SIZE,
 
1166
                         index._leaf_node_cache._max_cache)
 
1167
        self.assertIsInstance(index._internal_node_cache, fifo_cache.FIFOCache)
 
1168
        self.assertEqual(100, index._internal_node_cache._max_cache)
 
1169
        # No change if unlimited_cache=False is passed
 
1170
        index = btree_index.BTreeGraphIndex(trans, 'index', size,
 
1171
                                            unlimited_cache=False)
 
1172
        self.assertIsInstance(index._leaf_node_cache, lru_cache.LRUCache)
 
1173
        self.assertEqual(btree_index._NODE_CACHE_SIZE,
 
1174
                         index._leaf_node_cache._max_cache)
 
1175
        self.assertIsInstance(index._internal_node_cache, fifo_cache.FIFOCache)
 
1176
        self.assertEqual(100, index._internal_node_cache._max_cache)
 
1177
        index = btree_index.BTreeGraphIndex(trans, 'index', size,
 
1178
                                            unlimited_cache=True)
 
1179
        self.assertIsInstance(index._leaf_node_cache, dict)
 
1180
        self.assertIs(type(index._internal_node_cache), dict)
 
1181
        # Exercise the lookup code
 
1182
        entries = set(index.iter_entries([n[0] for n in nodes]))
 
1183
        self.assertEqual(500, len(entries))
 
1184
 
872
1185
 
873
1186
class TestBTreeNodes(BTreeTestCase):
874
1187
 
875
 
    def restore_parser(self):
876
 
        btree_index._btree_serializer = self.saved_parser
877
 
 
878
1188
    def setUp(self):
879
1189
        BTreeTestCase.setUp(self)
880
 
        self.saved_parser = btree_index._btree_serializer
881
 
        self.addCleanup(self.restore_parser)
882
 
        btree_index._btree_serializer = self.parse_btree
 
1190
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
883
1191
 
884
1192
    def test_LeafNode_1_0(self):
885
1193
        node_bytes = ("type=leaf\n"
897
1205
            ("2222222222222222222222222222222222222222",): ("value:2", ()),
898
1206
            ("3333333333333333333333333333333333333333",): ("value:3", ()),
899
1207
            ("4444444444444444444444444444444444444444",): ("value:4", ()),
900
 
            }, node.keys)
 
1208
            }, dict(node.all_items()))
901
1209
 
902
1210
    def test_LeafNode_2_2(self):
903
1211
        node_bytes = ("type=leaf\n"
917
1225
            ('11', '33'): ('value:3',
918
1226
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
919
1227
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
920
 
            }, node.keys)
 
1228
            }, dict(node.all_items()))
921
1229
 
922
1230
    def test_InternalNode_1(self):
923
1231
        node_bytes = ("type=internal\n"
958
1266
            ('11', '33'): ('value:3',
959
1267
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
960
1268
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
961
 
            }, node.keys)
 
1269
            }, dict(node.all_items()))
962
1270
 
963
1271
    def assertFlattened(self, expected, key, value, refs):
964
1272
        flat_key, flat_line = self.parse_btree._flatten_node(
996
1304
    def test_exists(self):
997
1305
        # This is just to let the user know if they don't have the feature
998
1306
        # available
999
 
        self.requireFeature(CompiledBtreeParserFeature)
 
1307
        self.requireFeature(compiled_btreeparser_feature)
1000
1308
 
1001
1309
 
1002
1310
class TestMultiBisectRight(tests.TestCase):
1042
1350
        This doesn't actually create anything on disk, it just primes a
1043
1351
        BTreeGraphIndex with the recommended information.
1044
1352
        """
1045
 
        index = btree_index.BTreeGraphIndex(get_transport('memory:///'),
1046
 
                                            'test-index', size=size)
 
1353
        index = btree_index.BTreeGraphIndex(
 
1354
            transport.get_transport('memory:///'), 'test-index', size=size)
1047
1355
        if recommended_pages is not None:
1048
1356
            index._recommended_pages = recommended_pages
1049
1357
        return index