← 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: 2009-08-27 02:27:19 UTC
  • mfrom: (4634.3.19 gc-batching)
  • Revision ID: pqm@pqm.ubuntu.com-20090827022719-bl2yoqhpj3fcfczu
(andrew) Fix #402657: 2a fetch over dumb transport reads one group at
        a time.

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 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
    osutils,
26
27
    tests,
27
28
    )
28
29
from bzrlib.tests import (
29
30
    TestCaseWithTransport,
30
 
    TestScenarioApplier,
31
 
    adapt_tests,
32
31
    condition_isinstance,
 
32
    multiply_tests,
33
33
    split_suite_by_condition,
34
34
    )
35
35
from bzrlib.transport import get_transport
39
39
    # parameterise the TestBTreeNodes tests
40
40
    node_tests, others = split_suite_by_condition(standard_tests,
41
41
        condition_isinstance(TestBTreeNodes))
42
 
    applier = TestScenarioApplier()
43
42
    import bzrlib._btree_serializer_py as py_module
44
 
    applier.scenarios = [('python', {'parse_btree': py_module})]
 
43
    scenarios = [('python', {'parse_btree': py_module})]
45
44
    if CompiledBtreeParserFeature.available():
46
45
        # Is there a way to do this that gets missing feature failures rather
47
46
        # 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
 
47
        import bzrlib._btree_serializer_pyx as c_module
 
48
        scenarios.append(('C', {'parse_btree': c_module}))
 
49
    return multiply_tests(node_tests, scenarios, others)
52
50
 
53
51
 
54
52
class _CompiledBtreeParserFeature(tests.Feature):
55
53
    def _probe(self):
56
54
        try:
57
 
            import bzrlib._btree_serializer_c
 
55
            import bzrlib._btree_serializer_pyx
58
56
        except ImportError:
59
57
            return False
60
58
        return True
61
59
 
62
60
    def feature_name(self):
63
 
        return 'bzrlib._btree_serializer_c'
 
61
        return 'bzrlib._btree_serializer_pyx'
64
62
 
65
63
CompiledBtreeParserFeature = _CompiledBtreeParserFeature()
66
64
 
434
432
        self.assertEqual(sorted(nodes), nodes)
435
433
        self.assertEqual(16, len(nodes))
436
434
 
 
435
    def test_spill_index_stress_1_1_no_combine(self):
 
436
        builder = btree_index.BTreeBuilder(key_elements=1, spill_at=2)
 
437
        builder.set_optimize(for_size=False, combine_backing_indices=False)
 
438
        nodes = [node[0:2] for node in self.make_nodes(16, 1, 0)]
 
439
        builder.add_node(*nodes[0])
 
440
        # Test the parts of the index that take up memory are doing so
 
441
        # predictably.
 
442
        self.assertEqual(1, len(builder._nodes))
 
443
        self.assertEqual(1, len(builder._keys))
 
444
        self.assertIs(None, builder._nodes_by_key)
 
445
        builder.add_node(*nodes[1])
 
446
        self.assertEqual(0, len(builder._nodes))
 
447
        self.assertEqual(0, len(builder._keys))
 
448
        self.assertIs(None, builder._nodes_by_key)
 
449
        self.assertEqual(1, len(builder._backing_indices))
 
450
        self.assertEqual(2, builder._backing_indices[0].key_count())
 
451
        # now back to memory
 
452
        builder.add_node(*nodes[2])
 
453
        self.assertEqual(1, len(builder._nodes))
 
454
        self.assertEqual(1, len(builder._keys))
 
455
        self.assertIs(None, builder._nodes_by_key)
 
456
        # And spills to a second backing index but doesn't combine
 
457
        builder.add_node(*nodes[3])
 
458
        self.assertEqual(0, len(builder._nodes))
 
459
        self.assertEqual(0, len(builder._keys))
 
460
        self.assertIs(None, builder._nodes_by_key)
 
461
        self.assertEqual(2, len(builder._backing_indices))
 
462
        for backing_index in builder._backing_indices:
 
463
            self.assertEqual(2, backing_index.key_count())
 
464
        # The next spills to the 3rd slot
 
465
        builder.add_node(*nodes[4])
 
466
        builder.add_node(*nodes[5])
 
467
        self.assertEqual(0, len(builder._nodes))
 
468
        self.assertEqual(0, len(builder._keys))
 
469
        self.assertIs(None, builder._nodes_by_key)
 
470
        self.assertEqual(3, len(builder._backing_indices))
 
471
        for backing_index in builder._backing_indices:
 
472
            self.assertEqual(2, backing_index.key_count())
 
473
        # Now spill a few more, and check that we don't combine
 
474
        builder.add_node(*nodes[6])
 
475
        builder.add_node(*nodes[7])
 
476
        builder.add_node(*nodes[8])
 
477
        builder.add_node(*nodes[9])
 
478
        builder.add_node(*nodes[10])
 
479
        builder.add_node(*nodes[11])
 
480
        builder.add_node(*nodes[12])
 
481
        self.assertEqual(6, len(builder._backing_indices))
 
482
        for backing_index in builder._backing_indices:
 
483
            self.assertEqual(2, backing_index.key_count())
 
484
        # Test that memory and disk are both used for query methods; and that
 
485
        # None is skipped over happily.
 
486
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
 
487
            list(builder.iter_all_entries()))
 
488
        # Two nodes - one memory one disk
 
489
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
490
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
491
        self.assertEqual(13, builder.key_count())
 
492
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
493
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
494
        builder.add_node(*nodes[13])
 
495
        builder.add_node(*nodes[14])
 
496
        builder.add_node(*nodes[15])
 
497
        self.assertEqual(8, len(builder._backing_indices))
 
498
        for backing_index in builder._backing_indices:
 
499
            self.assertEqual(2, backing_index.key_count())
 
500
        # Now finish, and check we got a correctly ordered tree
 
501
        transport = self.get_transport('')
 
502
        size = transport.put_file('index', builder.finish())
 
503
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
504
        nodes = list(index.iter_all_entries())
 
505
        self.assertEqual(sorted(nodes), nodes)
 
506
        self.assertEqual(16, len(nodes))
 
507
 
 
508
    def test_set_optimize(self):
 
509
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
 
510
        builder.set_optimize(for_size=True)
 
511
        self.assertTrue(builder._optimize_for_size)
 
512
        builder.set_optimize(for_size=False)
 
513
        self.assertFalse(builder._optimize_for_size)
 
514
        # test that we can set combine_backing_indices without effecting
 
515
        # _optimize_for_size
 
516
        obj = object()
 
517
        builder._optimize_for_size = obj
 
518
        builder.set_optimize(combine_backing_indices=False)
 
519
        self.assertFalse(builder._combine_backing_indices)
 
520
        self.assertIs(obj, builder._optimize_for_size)
 
521
        builder.set_optimize(combine_backing_indices=True)
 
522
        self.assertTrue(builder._combine_backing_indices)
 
523
        self.assertIs(obj, builder._optimize_for_size)
 
524
 
437
525
    def test_spill_index_stress_2_2(self):
438
526
        # test that references and longer keys don't confuse things.
439
527
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2,
572
660
        # The entire index should have been requested (as we generally have the
573
661
        # size available, and doing many small readvs is inappropriate).
574
662
        # 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)
 
663
        self.assertEqual([('get', 'index')], transport._activity)
578
664
 
579
665
    def test_empty_key_count(self):
580
666
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
605
691
            transport._activity)
606
692
        self.assertEqual(1199, size)
607
693
 
 
694
    def test__read_nodes_no_size_one_page_reads_once(self):
 
695
        self.make_index(nodes=[(('key',), 'value', ())])
 
696
        trans = get_transport('trace+' + self.get_url())
 
697
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
 
698
        del trans._activity[:]
 
699
        nodes = dict(index._read_nodes([0]))
 
700
        self.assertEqual([0], nodes.keys())
 
701
        node = nodes[0]
 
702
        self.assertEqual([('key',)], node.keys.keys())
 
703
        self.assertEqual([('get', 'index')], trans._activity)
 
704
 
 
705
    def test__read_nodes_no_size_multiple_pages(self):
 
706
        index = self.make_index(2, 2, nodes=self.make_nodes(160, 2, 2))
 
707
        index.key_count()
 
708
        num_pages = index._row_offsets[-1]
 
709
        # Reopen with a traced transport and no size
 
710
        trans = get_transport('trace+' + self.get_url())
 
711
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
 
712
        del trans._activity[:]
 
713
        nodes = dict(index._read_nodes([0]))
 
714
        self.assertEqual(range(num_pages), nodes.keys())
 
715
 
608
716
    def test_2_levels_key_count_2_2(self):
609
717
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
610
718
        nodes = self.make_nodes(160, 2, 2)
692
800
            btree_index.BTreeGraphIndex(transport1, 'index', 10) !=
693
801
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
694
802
 
 
803
    def test_iter_all_only_root_no_size(self):
 
804
        self.make_index(nodes=[(('key',), 'value', ())])
 
805
        trans = get_transport('trace+' + self.get_url(''))
 
806
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
 
807
        del trans._activity[:]
 
808
        self.assertEqual([(('key',), 'value')],
 
809
                         [x[1:] for x in index.iter_all_entries()])
 
810
        self.assertEqual([('get', 'index')], trans._activity)
 
811
 
695
812
    def test_iter_all_entries_reads(self):
696
813
        # iterating all entries reads the header, then does a linear
697
814
        # read.
833
950
            (index, ('name', 'fin2'), 'beta', ((), ))]),
834
951
            set(index.iter_entries_prefix([('name', None)])))
835
952
 
 
953
    # XXX: external_references tests are duplicated in test_index.  We
 
954
    # probably should have per_graph_index tests...
 
955
    def test_external_references_no_refs(self):
 
956
        index = self.make_index(ref_lists=0, nodes=[])
 
957
        self.assertRaises(ValueError, index.external_references, 0)
 
958
 
 
959
    def test_external_references_no_results(self):
 
960
        index = self.make_index(ref_lists=1, nodes=[
 
961
            (('key',), 'value', ([],))])
 
962
        self.assertEqual(set(), index.external_references(0))
 
963
 
 
964
    def test_external_references_missing_ref(self):
 
965
        missing_key = ('missing',)
 
966
        index = self.make_index(ref_lists=1, nodes=[
 
967
            (('key',), 'value', ([missing_key],))])
 
968
        self.assertEqual(set([missing_key]), index.external_references(0))
 
969
 
 
970
    def test_external_references_multiple_ref_lists(self):
 
971
        missing_key = ('missing',)
 
972
        index = self.make_index(ref_lists=2, nodes=[
 
973
            (('key',), 'value', ([], [missing_key]))])
 
974
        self.assertEqual(set([]), index.external_references(0))
 
975
        self.assertEqual(set([missing_key]), index.external_references(1))
 
976
 
 
977
    def test_external_references_two_records(self):
 
978
        index = self.make_index(ref_lists=1, nodes=[
 
979
            (('key-1',), 'value', ([('key-2',)],)),
 
980
            (('key-2',), 'value', ([],)),
 
981
            ])
 
982
        self.assertEqual(set([]), index.external_references(0))
 
983
 
 
984
    def test__find_ancestors_one_page(self):
 
985
        key1 = ('key-1',)
 
986
        key2 = ('key-2',)
 
987
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
988
            (key1, 'value', ([key2],)),
 
989
            (key2, 'value', ([],)),
 
990
            ])
 
991
        parent_map = {}
 
992
        missing_keys = set()
 
993
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
 
994
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
 
995
        self.assertEqual(set(), missing_keys)
 
996
        self.assertEqual(set(), search_keys)
 
997
 
 
998
    def test__find_ancestors_one_page_w_missing(self):
 
999
        key1 = ('key-1',)
 
1000
        key2 = ('key-2',)
 
1001
        key3 = ('key-3',)
 
1002
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1003
            (key1, 'value', ([key2],)),
 
1004
            (key2, 'value', ([],)),
 
1005
            ])
 
1006
        parent_map = {}
 
1007
        missing_keys = set()
 
1008
        search_keys = index._find_ancestors([key2, key3], 0, parent_map,
 
1009
                                            missing_keys)
 
1010
        self.assertEqual({key2: ()}, parent_map)
 
1011
        # we know that key3 is missing because we read the page that it would
 
1012
        # otherwise be on
 
1013
        self.assertEqual(set([key3]), missing_keys)
 
1014
        self.assertEqual(set(), search_keys)
 
1015
 
 
1016
    def test__find_ancestors_one_parent_missing(self):
 
1017
        key1 = ('key-1',)
 
1018
        key2 = ('key-2',)
 
1019
        key3 = ('key-3',)
 
1020
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1021
            (key1, 'value', ([key2],)),
 
1022
            (key2, 'value', ([key3],)),
 
1023
            ])
 
1024
        parent_map = {}
 
1025
        missing_keys = set()
 
1026
        search_keys = index._find_ancestors([key1], 0, parent_map,
 
1027
                                            missing_keys)
 
1028
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1029
        self.assertEqual(set(), missing_keys)
 
1030
        # all we know is that key3 wasn't present on the page we were reading
 
1031
        # but if you look, the last key is key2 which comes before key3, so we
 
1032
        # don't know whether key3 would land on this page or not.
 
1033
        self.assertEqual(set([key3]), search_keys)
 
1034
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
 
1035
                                            missing_keys)
 
1036
        # passing it back in, we are sure it is 'missing'
 
1037
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1038
        self.assertEqual(set([key3]), missing_keys)
 
1039
        self.assertEqual(set([]), search_keys)
 
1040
 
 
1041
    def test__find_ancestors_dont_search_known(self):
 
1042
        key1 = ('key-1',)
 
1043
        key2 = ('key-2',)
 
1044
        key3 = ('key-3',)
 
1045
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1046
            (key1, 'value', ([key2],)),
 
1047
            (key2, 'value', ([key3],)),
 
1048
            (key3, 'value', ([],)),
 
1049
            ])
 
1050
        # We already know about key2, so we won't try to search for key3
 
1051
        parent_map = {key2: (key3,)}
 
1052
        missing_keys = set()
 
1053
        search_keys = index._find_ancestors([key1], 0, parent_map,
 
1054
                                            missing_keys)
 
1055
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1056
        self.assertEqual(set(), missing_keys)
 
1057
        self.assertEqual(set(), search_keys)
 
1058
 
 
1059
    def test__find_ancestors_multiple_pages(self):
 
1060
        # We need to use enough keys that we actually cause a split
 
1061
        start_time = 1249671539
 
1062
        email = "joebob@example.com"
 
1063
        nodes = []
 
1064
        ref_lists = ((),)
 
1065
        rev_keys = []
 
1066
        for i in xrange(400):
 
1067
            rev_id = '%s-%s-%s' % (email,
 
1068
                                   osutils.compact_date(start_time + i),
 
1069
                                   osutils.rand_chars(16))
 
1070
            rev_key = (rev_id,)
 
1071
            nodes.append((rev_key, 'value', ref_lists))
 
1072
            # We have a ref 'list' of length 1, with a list of parents, with 1
 
1073
            # parent which is a key
 
1074
            ref_lists = ((rev_key,),)
 
1075
            rev_keys.append(rev_key)
 
1076
        index = self.make_index(ref_lists=1, key_elements=1, nodes=nodes)
 
1077
        self.assertEqual(400, index.key_count())
 
1078
        self.assertEqual(3, len(index._row_offsets))
 
1079
        nodes = dict(index._read_nodes([1, 2]))
 
1080
        l1 = nodes[1]
 
1081
        l2 = nodes[2]
 
1082
        min_l2_key = l2.min_key
 
1083
        max_l1_key = l1.max_key
 
1084
        self.assertTrue(max_l1_key < min_l2_key)
 
1085
        parents_min_l2_key = l2.keys[min_l2_key][1][0]
 
1086
        self.assertEqual((l1.max_key,), parents_min_l2_key)
 
1087
        # Now, whatever key we select that would fall on the second page,
 
1088
        # should give us all the parents until the page break
 
1089
        key_idx = rev_keys.index(min_l2_key)
 
1090
        next_key = rev_keys[key_idx+1]
 
1091
        # So now when we get the parent map, we should get the key we are
 
1092
        # looking for, min_l2_key, and then a reference to go look for the
 
1093
        # parent of that key
 
1094
        parent_map = {}
 
1095
        missing_keys = set()
 
1096
        search_keys = index._find_ancestors([next_key], 0, parent_map,
 
1097
                                            missing_keys)
 
1098
        self.assertEqual([min_l2_key, next_key], sorted(parent_map))
 
1099
        self.assertEqual(set(), missing_keys)
 
1100
        self.assertEqual(set([max_l1_key]), search_keys)
 
1101
        parent_map = {}
 
1102
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
 
1103
                                            missing_keys)
 
1104
        self.assertEqual(sorted(l1.keys), sorted(parent_map))
 
1105
        self.assertEqual(set(), missing_keys)
 
1106
        self.assertEqual(set(), search_keys)
 
1107
 
 
1108
    def test__find_ancestors_empty_index(self):
 
1109
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[])
 
1110
        parent_map = {}
 
1111
        missing_keys = set()
 
1112
        search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
 
1113
                                            missing_keys)
 
1114
        self.assertEqual(set(), search_keys)
 
1115
        self.assertEqual({}, parent_map)
 
1116
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
 
1117
 
836
1118
 
837
1119
class TestBTreeNodes(BTreeTestCase):
838
1120
 
996
1278
                                     (4, ['g', 'h'])],
997
1279
                                    ['a', 'b', 'd', 'e', 'g', 'h'],
998
1280
                                    ['c', 'd', 'f', 'g'])
 
1281
 
 
1282
 
 
1283
class TestExpandOffsets(tests.TestCase):
 
1284
 
 
1285
    def make_index(self, size, recommended_pages=None):
 
1286
        """Make an index with a generic size.
 
1287
 
 
1288
        This doesn't actually create anything on disk, it just primes a
 
1289
        BTreeGraphIndex with the recommended information.
 
1290
        """
 
1291
        index = btree_index.BTreeGraphIndex(get_transport('memory:///'),
 
1292
                                            'test-index', size=size)
 
1293
        if recommended_pages is not None:
 
1294
            index._recommended_pages = recommended_pages
 
1295
        return index
 
1296
 
 
1297
    def set_cached_offsets(self, index, cached_offsets):
 
1298
        """Monkeypatch to give a canned answer for _get_offsets_for...()."""
 
1299
        def _get_offsets_to_cached_pages():
 
1300
            cached = set(cached_offsets)
 
1301
            return cached
 
1302
        index._get_offsets_to_cached_pages = _get_offsets_to_cached_pages
 
1303
 
 
1304
    def prepare_index(self, index, node_ref_lists, key_length, key_count,
 
1305
                      row_lengths, cached_offsets):
 
1306
        """Setup the BTreeGraphIndex with some pre-canned information."""
 
1307
        index.node_ref_lists = node_ref_lists
 
1308
        index._key_length = key_length
 
1309
        index._key_count = key_count
 
1310
        index._row_lengths = row_lengths
 
1311
        index._compute_row_offsets()
 
1312
        index._root_node = btree_index._InternalNode('internal\noffset=0\n')
 
1313
        self.set_cached_offsets(index, cached_offsets)
 
1314
 
 
1315
    def make_100_node_index(self):
 
1316
        index = self.make_index(4096*100, 6)
 
1317
        # Consider we've already made a single request at the middle
 
1318
        self.prepare_index(index, node_ref_lists=0, key_length=1,
 
1319
                           key_count=1000, row_lengths=[1, 99],
 
1320
                           cached_offsets=[0, 50])
 
1321
        return index
 
1322
 
 
1323
    def make_1000_node_index(self):
 
1324
        index = self.make_index(4096*1000, 6)
 
1325
        # Pretend we've already made a single request in the middle
 
1326
        self.prepare_index(index, node_ref_lists=0, key_length=1,
 
1327
                           key_count=90000, row_lengths=[1, 9, 990],
 
1328
                           cached_offsets=[0, 5, 500])
 
1329
        return index
 
1330
 
 
1331
    def assertNumPages(self, expected_pages, index, size):
 
1332
        index._size = size
 
1333
        self.assertEqual(expected_pages, index._compute_total_pages_in_index())
 
1334
 
 
1335
    def assertExpandOffsets(self, expected, index, offsets):
 
1336
        self.assertEqual(expected, index._expand_offsets(offsets),
 
1337
                         'We did not get the expected value after expanding'
 
1338
                         ' %s' % (offsets,))
 
1339
 
 
1340
    def test_default_recommended_pages(self):
 
1341
        index = self.make_index(None)
 
1342
        # local transport recommends 4096 byte reads, which is 1 page
 
1343
        self.assertEqual(1, index._recommended_pages)
 
1344
 
 
1345
    def test__compute_total_pages_in_index(self):
 
1346
        index = self.make_index(None)
 
1347
        self.assertNumPages(1, index, 1024)
 
1348
        self.assertNumPages(1, index, 4095)
 
1349
        self.assertNumPages(1, index, 4096)
 
1350
        self.assertNumPages(2, index, 4097)
 
1351
        self.assertNumPages(2, index, 8192)
 
1352
        self.assertNumPages(76, index, 4096*75 + 10)
 
1353
 
 
1354
    def test__find_layer_start_and_stop(self):
 
1355
        index = self.make_1000_node_index()
 
1356
        self.assertEqual((0, 1), index._find_layer_first_and_end(0))
 
1357
        self.assertEqual((1, 10), index._find_layer_first_and_end(1))
 
1358
        self.assertEqual((1, 10), index._find_layer_first_and_end(9))
 
1359
        self.assertEqual((10, 1000), index._find_layer_first_and_end(10))
 
1360
        self.assertEqual((10, 1000), index._find_layer_first_and_end(99))
 
1361
        self.assertEqual((10, 1000), index._find_layer_first_and_end(999))
 
1362
 
 
1363
    def test_unknown_size(self):
 
1364
        # We should not expand if we don't know the file size
 
1365
        index = self.make_index(None, 10)
 
1366
        self.assertExpandOffsets([0], index, [0])
 
1367
        self.assertExpandOffsets([1, 4, 9], index, [1, 4, 9])
 
1368
 
 
1369
    def test_more_than_recommended(self):
 
1370
        index = self.make_index(4096*100, 2)
 
1371
        self.assertExpandOffsets([1, 10], index, [1, 10])
 
1372
        self.assertExpandOffsets([1, 10, 20], index, [1, 10, 20])
 
1373
 
 
1374
    def test_read_all_from_root(self):
 
1375
        index = self.make_index(4096*10, 20)
 
1376
        self.assertExpandOffsets(range(10), index, [0])
 
1377
 
 
1378
    def test_read_all_when_cached(self):
 
1379
        # We've read enough that we can grab all the rest in a single request
 
1380
        index = self.make_index(4096*10, 5)
 
1381
        self.prepare_index(index, node_ref_lists=0, key_length=1,
 
1382
                           key_count=1000, row_lengths=[1, 9],
 
1383
                           cached_offsets=[0, 1, 2, 5, 6])
 
1384
        # It should fill the remaining nodes, regardless of the one requested
 
1385
        self.assertExpandOffsets([3, 4, 7, 8, 9], index, [3])
 
1386
        self.assertExpandOffsets([3, 4, 7, 8, 9], index, [8])
 
1387
        self.assertExpandOffsets([3, 4, 7, 8, 9], index, [9])
 
1388
 
 
1389
    def test_no_root_node(self):
 
1390
        index = self.make_index(4096*10, 5)
 
1391
        self.assertExpandOffsets([0], index, [0])
 
1392
 
 
1393
    def test_include_neighbors(self):
 
1394
        index = self.make_100_node_index()
 
1395
        # We expand in both directions, until we have at least 'recommended'
 
1396
        # pages
 
1397
        self.assertExpandOffsets([9, 10, 11, 12, 13, 14, 15], index, [12])
 
1398
        self.assertExpandOffsets([88, 89, 90, 91, 92, 93, 94], index, [91])
 
1399
        # If we hit an 'edge' we continue in the other direction
 
1400
        self.assertExpandOffsets([1, 2, 3, 4, 5, 6], index, [2])
 
1401
        self.assertExpandOffsets([94, 95, 96, 97, 98, 99], index, [98])
 
1402
 
 
1403
        # Requesting many nodes will expand all locations equally
 
1404
        self.assertExpandOffsets([1, 2, 3, 80, 81, 82], index, [2, 81])
 
1405
        self.assertExpandOffsets([1, 2, 3, 9, 10, 11, 80, 81, 82], index,
 
1406
                               [2, 10, 81])
 
1407
 
 
1408
    def test_stop_at_cached(self):
 
1409
        index = self.make_100_node_index()
 
1410
        self.set_cached_offsets(index, [0, 10, 19])
 
1411
        self.assertExpandOffsets([11, 12, 13, 14, 15, 16], index, [11])
 
1412
        self.assertExpandOffsets([11, 12, 13, 14, 15, 16], index, [12])
 
1413
        self.assertExpandOffsets([12, 13, 14, 15, 16, 17, 18], index, [15])
 
1414
        self.assertExpandOffsets([13, 14, 15, 16, 17, 18], index, [16])
 
1415
        self.assertExpandOffsets([13, 14, 15, 16, 17, 18], index, [17])
 
1416
        self.assertExpandOffsets([13, 14, 15, 16, 17, 18], index, [18])
 
1417
 
 
1418
    def test_cannot_fully_expand(self):
 
1419
        index = self.make_100_node_index()
 
1420
        self.set_cached_offsets(index, [0, 10, 12])
 
1421
        # We don't go into an endless loop if we are bound by cached nodes
 
1422
        self.assertExpandOffsets([11], index, [11])
 
1423
 
 
1424
    def test_overlap(self):
 
1425
        index = self.make_100_node_index()
 
1426
        self.assertExpandOffsets([10, 11, 12, 13, 14, 15], index, [12, 13])
 
1427
        self.assertExpandOffsets([10, 11, 12, 13, 14, 15], index, [11, 14])
 
1428
 
 
1429
    def test_stay_within_layer(self):
 
1430
        index = self.make_1000_node_index()
 
1431
        # When expanding a request, we won't read nodes from the next layer
 
1432
        self.assertExpandOffsets([1, 2, 3, 4], index, [2])
 
1433
        self.assertExpandOffsets([6, 7, 8, 9], index, [6])
 
1434
        self.assertExpandOffsets([6, 7, 8, 9], index, [9])
 
1435
        self.assertExpandOffsets([10, 11, 12, 13, 14, 15], index, [10])
 
1436
        self.assertExpandOffsets([10, 11, 12, 13, 14, 15, 16], index, [13])
 
1437
 
 
1438
        self.set_cached_offsets(index, [0, 4, 12])
 
1439
        self.assertExpandOffsets([5, 6, 7, 8, 9], index, [7])
 
1440
        self.assertExpandOffsets([10, 11], index, [11])
 
1441
 
 
1442
    def test_small_requests_unexpanded(self):
 
1443
        index = self.make_100_node_index()
 
1444
        self.set_cached_offsets(index, [0])
 
1445
        self.assertExpandOffsets([1], index, [1])
 
1446
        self.assertExpandOffsets([50], index, [50])
 
1447
        # If we request more than one node, then we'll expand
 
1448
        self.assertExpandOffsets([49, 50, 51, 59, 60, 61], index, [50, 60])
 
1449
 
 
1450
        # The first pass does not expand
 
1451
        index = self.make_1000_node_index()
 
1452
        self.set_cached_offsets(index, [0])
 
1453
        self.assertExpandOffsets([1], index, [1])
 
1454
        self.set_cached_offsets(index, [0, 1])
 
1455
        self.assertExpandOffsets([100], index, [100])
 
1456
        self.set_cached_offsets(index, [0, 1, 100])
 
1457
        # But after the first depth, we will expand
 
1458
        self.assertExpandOffsets([2, 3, 4, 5, 6, 7], index, [2])
 
1459
        self.assertExpandOffsets([2, 3, 4, 5, 6, 7], index, [4])
 
1460
        self.set_cached_offsets(index, [0, 1, 2, 3, 4, 5, 6, 7, 100])
 
1461
        self.assertExpandOffsets([102, 103, 104, 105, 106, 107, 108], index,
 
1462
                                 [105])