/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_btree_index.py

Merge bzr.dev

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
434
434
        self.assertEqual(sorted(nodes), nodes)
435
435
        self.assertEqual(16, len(nodes))
436
436
 
 
437
    def test_set_optimize(self):
 
438
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
 
439
        builder.set_optimize(for_size=True)
 
440
        self.assertTrue(builder._optimize_for_size)
 
441
        builder.set_optimize(for_size=False)
 
442
        self.assertFalse(builder._optimize_for_size)
 
443
 
437
444
    def test_spill_index_stress_2_2(self):
438
445
        # test that references and longer keys don't confuse things.
439
446
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2,
572
579
        # The entire index should have been requested (as we generally have the
573
580
        # size available, and doing many small readvs is inappropriate).
574
581
        # 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)
 
582
        self.assertEqual([('get', 'index')], transport._activity)
578
583
 
579
584
    def test_empty_key_count(self):
580
585
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
605
610
            transport._activity)
606
611
        self.assertEqual(1199, size)
607
612
 
 
613
    def test__read_nodes_no_size_one_page_reads_once(self):
 
614
        self.make_index(nodes=[(('key',), 'value', ())])
 
615
        trans = get_transport('trace+' + self.get_url())
 
616
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
 
617
        del trans._activity[:]
 
618
        nodes = dict(index._read_nodes([0]))
 
619
        self.assertEqual([0], nodes.keys())
 
620
        node = nodes[0]
 
621
        self.assertEqual([('key',)], node.keys.keys())
 
622
        self.assertEqual([('get', 'index')], trans._activity)
 
623
 
 
624
    def test__read_nodes_no_size_multiple_pages(self):
 
625
        index = self.make_index(2, 2, nodes=self.make_nodes(160, 2, 2))
 
626
        index.key_count()
 
627
        num_pages = index._row_offsets[-1]
 
628
        # Reopen with a traced transport and no size
 
629
        trans = get_transport('trace+' + self.get_url())
 
630
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
 
631
        del trans._activity[:]
 
632
        nodes = dict(index._read_nodes([0]))
 
633
        self.assertEqual(range(num_pages), nodes.keys())
 
634
 
608
635
    def test_2_levels_key_count_2_2(self):
609
636
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
610
637
        nodes = self.make_nodes(160, 2, 2)
692
719
            btree_index.BTreeGraphIndex(transport1, 'index', 10) !=
693
720
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
694
721
 
 
722
    def test_iter_all_only_root_no_size(self):
 
723
        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[:]
 
727
        self.assertEqual([(('key',), 'value')],
 
728
                         [x[1:] for x in index.iter_all_entries()])
 
729
        self.assertEqual([('get', 'index')], trans._activity)
 
730
 
695
731
    def test_iter_all_entries_reads(self):
696
732
        # iterating all entries reads the header, then does a linear
697
733
        # read.
996
1032
                                     (4, ['g', 'h'])],
997
1033
                                    ['a', 'b', 'd', 'e', 'g', 'h'],
998
1034
                                    ['c', 'd', 'f', 'g'])
 
1035
 
 
1036
 
 
1037
class TestExpandOffsets(tests.TestCase):
 
1038
 
 
1039
    def make_index(self, size, recommended_pages=None):
 
1040
        """Make an index with a generic size.
 
1041
 
 
1042
        This doesn't actually create anything on disk, it just primes a
 
1043
        BTreeGraphIndex with the recommended information.
 
1044
        """
 
1045
        index = btree_index.BTreeGraphIndex(get_transport('memory:///'),
 
1046
                                            'test-index', size=size)
 
1047
        if recommended_pages is not None:
 
1048
            index._recommended_pages = recommended_pages
 
1049
        return index
 
1050
 
 
1051
    def set_cached_offsets(self, index, cached_offsets):
 
1052
        """Monkeypatch to give a canned answer for _get_offsets_for...()."""
 
1053
        def _get_offsets_to_cached_pages():
 
1054
            cached = set(cached_offsets)
 
1055
            return cached
 
1056
        index._get_offsets_to_cached_pages = _get_offsets_to_cached_pages
 
1057
 
 
1058
    def prepare_index(self, index, node_ref_lists, key_length, key_count,
 
1059
                      row_lengths, cached_offsets):
 
1060
        """Setup the BTreeGraphIndex with some pre-canned information."""
 
1061
        index.node_ref_lists = node_ref_lists
 
1062
        index._key_length = key_length
 
1063
        index._key_count = key_count
 
1064
        index._row_lengths = row_lengths
 
1065
        index._compute_row_offsets()
 
1066
        index._root_node = btree_index._InternalNode('internal\noffset=0\n')
 
1067
        self.set_cached_offsets(index, cached_offsets)
 
1068
 
 
1069
    def make_100_node_index(self):
 
1070
        index = self.make_index(4096*100, 6)
 
1071
        # Consider we've already made a single request at the middle
 
1072
        self.prepare_index(index, node_ref_lists=0, key_length=1,
 
1073
                           key_count=1000, row_lengths=[1, 99],
 
1074
                           cached_offsets=[0, 50])
 
1075
        return index
 
1076
 
 
1077
    def make_1000_node_index(self):
 
1078
        index = self.make_index(4096*1000, 6)
 
1079
        # Pretend we've already made a single request in the middle
 
1080
        self.prepare_index(index, node_ref_lists=0, key_length=1,
 
1081
                           key_count=90000, row_lengths=[1, 9, 990],
 
1082
                           cached_offsets=[0, 5, 500])
 
1083
        return index
 
1084
 
 
1085
    def assertNumPages(self, expected_pages, index, size):
 
1086
        index._size = size
 
1087
        self.assertEqual(expected_pages, index._compute_total_pages_in_index())
 
1088
 
 
1089
    def assertExpandOffsets(self, expected, index, offsets):
 
1090
        self.assertEqual(expected, index._expand_offsets(offsets),
 
1091
                         'We did not get the expected value after expanding'
 
1092
                         ' %s' % (offsets,))
 
1093
 
 
1094
    def test_default_recommended_pages(self):
 
1095
        index = self.make_index(None)
 
1096
        # local transport recommends 4096 byte reads, which is 1 page
 
1097
        self.assertEqual(1, index._recommended_pages)
 
1098
 
 
1099
    def test__compute_total_pages_in_index(self):
 
1100
        index = self.make_index(None)
 
1101
        self.assertNumPages(1, index, 1024)
 
1102
        self.assertNumPages(1, index, 4095)
 
1103
        self.assertNumPages(1, index, 4096)
 
1104
        self.assertNumPages(2, index, 4097)
 
1105
        self.assertNumPages(2, index, 8192)
 
1106
        self.assertNumPages(76, index, 4096*75 + 10)
 
1107
 
 
1108
    def test__find_layer_start_and_stop(self):
 
1109
        index = self.make_1000_node_index()
 
1110
        self.assertEqual((0, 1), index._find_layer_first_and_end(0))
 
1111
        self.assertEqual((1, 10), index._find_layer_first_and_end(1))
 
1112
        self.assertEqual((1, 10), index._find_layer_first_and_end(9))
 
1113
        self.assertEqual((10, 1000), index._find_layer_first_and_end(10))
 
1114
        self.assertEqual((10, 1000), index._find_layer_first_and_end(99))
 
1115
        self.assertEqual((10, 1000), index._find_layer_first_and_end(999))
 
1116
 
 
1117
    def test_unknown_size(self):
 
1118
        # We should not expand if we don't know the file size
 
1119
        index = self.make_index(None, 10)
 
1120
        self.assertExpandOffsets([0], index, [0])
 
1121
        self.assertExpandOffsets([1, 4, 9], index, [1, 4, 9])
 
1122
 
 
1123
    def test_more_than_recommended(self):
 
1124
        index = self.make_index(4096*100, 2)
 
1125
        self.assertExpandOffsets([1, 10], index, [1, 10])
 
1126
        self.assertExpandOffsets([1, 10, 20], index, [1, 10, 20])
 
1127
 
 
1128
    def test_read_all_from_root(self):
 
1129
        index = self.make_index(4096*10, 20)
 
1130
        self.assertExpandOffsets(range(10), index, [0])
 
1131
 
 
1132
    def test_read_all_when_cached(self):
 
1133
        # We've read enough that we can grab all the rest in a single request
 
1134
        index = self.make_index(4096*10, 5)
 
1135
        self.prepare_index(index, node_ref_lists=0, key_length=1,
 
1136
                           key_count=1000, row_lengths=[1, 9],
 
1137
                           cached_offsets=[0, 1, 2, 5, 6])
 
1138
        # It should fill the remaining nodes, regardless of the one requested
 
1139
        self.assertExpandOffsets([3, 4, 7, 8, 9], index, [3])
 
1140
        self.assertExpandOffsets([3, 4, 7, 8, 9], index, [8])
 
1141
        self.assertExpandOffsets([3, 4, 7, 8, 9], index, [9])
 
1142
 
 
1143
    def test_no_root_node(self):
 
1144
        index = self.make_index(4096*10, 5)
 
1145
        self.assertExpandOffsets([0], index, [0])
 
1146
 
 
1147
    def test_include_neighbors(self):
 
1148
        index = self.make_100_node_index()
 
1149
        # We expand in both directions, until we have at least 'recommended'
 
1150
        # pages
 
1151
        self.assertExpandOffsets([9, 10, 11, 12, 13, 14, 15], index, [12])
 
1152
        self.assertExpandOffsets([88, 89, 90, 91, 92, 93, 94], index, [91])
 
1153
        # If we hit an 'edge' we continue in the other direction
 
1154
        self.assertExpandOffsets([1, 2, 3, 4, 5, 6], index, [2])
 
1155
        self.assertExpandOffsets([94, 95, 96, 97, 98, 99], index, [98])
 
1156
 
 
1157
        # Requesting many nodes will expand all locations equally
 
1158
        self.assertExpandOffsets([1, 2, 3, 80, 81, 82], index, [2, 81])
 
1159
        self.assertExpandOffsets([1, 2, 3, 9, 10, 11, 80, 81, 82], index,
 
1160
                               [2, 10, 81])
 
1161
 
 
1162
    def test_stop_at_cached(self):
 
1163
        index = self.make_100_node_index()
 
1164
        self.set_cached_offsets(index, [0, 10, 19])
 
1165
        self.assertExpandOffsets([11, 12, 13, 14, 15, 16], index, [11])
 
1166
        self.assertExpandOffsets([11, 12, 13, 14, 15, 16], index, [12])
 
1167
        self.assertExpandOffsets([12, 13, 14, 15, 16, 17, 18], index, [15])
 
1168
        self.assertExpandOffsets([13, 14, 15, 16, 17, 18], index, [16])
 
1169
        self.assertExpandOffsets([13, 14, 15, 16, 17, 18], index, [17])
 
1170
        self.assertExpandOffsets([13, 14, 15, 16, 17, 18], index, [18])
 
1171
 
 
1172
    def test_cannot_fully_expand(self):
 
1173
        index = self.make_100_node_index()
 
1174
        self.set_cached_offsets(index, [0, 10, 12])
 
1175
        # We don't go into an endless loop if we are bound by cached nodes
 
1176
        self.assertExpandOffsets([11], index, [11])
 
1177
 
 
1178
    def test_overlap(self):
 
1179
        index = self.make_100_node_index()
 
1180
        self.assertExpandOffsets([10, 11, 12, 13, 14, 15], index, [12, 13])
 
1181
        self.assertExpandOffsets([10, 11, 12, 13, 14, 15], index, [11, 14])
 
1182
 
 
1183
    def test_stay_within_layer(self):
 
1184
        index = self.make_1000_node_index()
 
1185
        # When expanding a request, we won't read nodes from the next layer
 
1186
        self.assertExpandOffsets([1, 2, 3, 4], index, [2])
 
1187
        self.assertExpandOffsets([6, 7, 8, 9], index, [6])
 
1188
        self.assertExpandOffsets([6, 7, 8, 9], index, [9])
 
1189
        self.assertExpandOffsets([10, 11, 12, 13, 14, 15], index, [10])
 
1190
        self.assertExpandOffsets([10, 11, 12, 13, 14, 15, 16], index, [13])
 
1191
 
 
1192
        self.set_cached_offsets(index, [0, 4, 12])
 
1193
        self.assertExpandOffsets([5, 6, 7, 8, 9], index, [7])
 
1194
        self.assertExpandOffsets([10, 11], index, [11])
 
1195
 
 
1196
    def test_small_requests_unexpanded(self):
 
1197
        index = self.make_100_node_index()
 
1198
        self.set_cached_offsets(index, [0])
 
1199
        self.assertExpandOffsets([1], index, [1])
 
1200
        self.assertExpandOffsets([50], index, [50])
 
1201
        # If we request more than one node, then we'll expand
 
1202
        self.assertExpandOffsets([49, 50, 51, 59, 60, 61], index, [50, 60])
 
1203
 
 
1204
        # The first pass does not expand
 
1205
        index = self.make_1000_node_index()
 
1206
        self.set_cached_offsets(index, [0])
 
1207
        self.assertExpandOffsets([1], index, [1])
 
1208
        self.set_cached_offsets(index, [0, 1])
 
1209
        self.assertExpandOffsets([100], index, [100])
 
1210
        self.set_cached_offsets(index, [0, 1, 100])
 
1211
        # But after the first depth, we will expand
 
1212
        self.assertExpandOffsets([2, 3, 4, 5, 6, 7], index, [2])
 
1213
        self.assertExpandOffsets([2, 3, 4, 5, 6, 7], index, [4])
 
1214
        self.set_cached_offsets(index, [0, 1, 2, 3, 4, 5, 6, 7, 100])
 
1215
        self.assertExpandOffsets([102, 103, 104, 105, 106, 107, 108], index,
 
1216
                                 [105])