/breezy/unstable

To get this branch, use:
bzr branch https://code.breezy-vcs.org/breezy/unstable

« back to all changes in this revision

Viewing changes to breezy/tests/test_btree_index.py

Merge trunk, address review comments.

Show diffs side-by-side

added added

removed removed

Lines of Context:
66
66
 
67
67
    def make_nodes(self, count, key_elements, reference_lists):
68
68
        """Generate count*key_elements sample nodes."""
 
69
        def _pos_to_key(pos, lead=b""):
 
70
            return (lead + (b"%d" % pos) * 40,)
69
71
        keys = []
70
72
        for prefix_pos in range(key_elements):
71
73
            if key_elements - 1:
72
 
                prefix = (str(prefix_pos) * 40,)
 
74
                prefix = _pos_to_key(prefix_pos)
73
75
            else:
74
76
                prefix = ()
75
77
            for pos in range(count):
76
78
                # TODO: This creates odd keys. When count == 100,000, it
77
79
                #       creates a 240 byte key
78
 
                key = prefix + (str(pos) * 40,)
79
 
                value = "value:%s" % pos
 
80
                key = prefix + _pos_to_key(pos)
 
81
                value = b"value:%d" % pos
80
82
                if reference_lists:
81
83
                    # generate some references
82
84
                    refs = []
89
91
                        for ref_pos in range(list_pos + pos % 2):
90
92
                            if pos % 2:
91
93
                                # refer to a nearby key
92
 
                                refs[-1].append(prefix + ("ref" + str(pos - 1) * 40,))
 
94
                                refs[-1].append(prefix + _pos_to_key(pos - 1, b"ref"))
93
95
                            else:
94
96
                                # serial of this ref in the ref list
95
 
                                refs[-1].append(prefix + ("ref" + str(ref_pos) * 40,))
 
97
                                refs[-1].append(prefix + _pos_to_key(ref_pos, b"ref"))
96
98
                        refs[-1] = tuple(refs[-1])
97
99
                    refs = tuple(refs)
98
100
                else:
131
133
        content = temp_file.read()
132
134
        del temp_file
133
135
        self.assertEqual(
134
 
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=0\n"
135
 
            "row_lengths=\n",
 
136
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=0\n"
 
137
            b"row_lengths=\n",
136
138
            content)
137
139
 
138
140
    def test_empty_2_1(self):
142
144
        content = temp_file.read()
143
145
        del temp_file
144
146
        self.assertEqual(
145
 
            "B+Tree Graph Index 2\nnode_ref_lists=1\nkey_elements=2\nlen=0\n"
146
 
            "row_lengths=\n",
 
147
            b"B+Tree Graph Index 2\nnode_ref_lists=1\nkey_elements=2\nlen=0\n"
 
148
            b"row_lengths=\n",
147
149
            content)
148
150
 
149
151
    def test_root_leaf_1_0(self):
157
159
        del temp_file
158
160
        self.assertEqual(131, len(content))
159
161
        self.assertEqual(
160
 
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"
161
 
            "row_lengths=1\n",
 
162
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"
 
163
            b"row_lengths=1\n",
162
164
            content[:73])
163
165
        node_content = content[73:]
164
166
        node_bytes = zlib.decompress(node_content)
165
 
        expected_node = ("type=leaf\n"
166
 
            "0000000000000000000000000000000000000000\x00\x00value:0\n"
167
 
            "1111111111111111111111111111111111111111\x00\x00value:1\n"
168
 
            "2222222222222222222222222222222222222222\x00\x00value:2\n"
169
 
            "3333333333333333333333333333333333333333\x00\x00value:3\n"
170
 
            "4444444444444444444444444444444444444444\x00\x00value:4\n")
 
167
        expected_node = (b"type=leaf\n"
 
168
            b"0000000000000000000000000000000000000000\x00\x00value:0\n"
 
169
            b"1111111111111111111111111111111111111111\x00\x00value:1\n"
 
170
            b"2222222222222222222222222222222222222222\x00\x00value:2\n"
 
171
            b"3333333333333333333333333333333333333333\x00\x00value:3\n"
 
172
            b"4444444444444444444444444444444444444444\x00\x00value:4\n")
171
173
        self.assertEqual(expected_node, node_bytes)
172
174
 
173
175
    def test_root_leaf_2_2(self):
181
183
        del temp_file
182
184
        self.assertEqual(238, len(content))
183
185
        self.assertEqual(
184
 
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"
185
 
            "row_lengths=1\n",
 
186
            b"B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"
 
187
            b"row_lengths=1\n",
186
188
            content[:74])
187
189
        node_content = content[74:]
188
190
        node_bytes = zlib.decompress(node_content)
189
191
        expected_node = (
190
 
            "type=leaf\n"
191
 
            "0000000000000000000000000000000000000000\x000000000000000000000000000000000000000000\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:0\n"
192
 
            "0000000000000000000000000000000000000000\x001111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\r0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:1\n"
193
 
            "0000000000000000000000000000000000000000\x002222222222222222222222222222222222222222\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:2\n"
194
 
            "0000000000000000000000000000000000000000\x003333333333333333333333333333333333333333\x000000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\t0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\r0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\x00value:3\n"
195
 
            "0000000000000000000000000000000000000000\x004444444444444444444444444444444444444444\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:4\n"
196
 
            "1111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:0\n"
197
 
            "1111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\r1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:1\n"
198
 
            "1111111111111111111111111111111111111111\x002222222222222222222222222222222222222222\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:2\n"
199
 
            "1111111111111111111111111111111111111111\x003333333333333333333333333333333333333333\x001111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\t1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\r1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\x00value:3\n"
200
 
            "1111111111111111111111111111111111111111\x004444444444444444444444444444444444444444\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:4\n"
201
 
            ""
 
192
            b"type=leaf\n"
 
193
            b"0000000000000000000000000000000000000000\x000000000000000000000000000000000000000000\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:0\n"
 
194
            b"0000000000000000000000000000000000000000\x001111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\r0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:1\n"
 
195
            b"0000000000000000000000000000000000000000\x002222222222222222222222222222222222222222\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:2\n"
 
196
            b"0000000000000000000000000000000000000000\x003333333333333333333333333333333333333333\x000000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\t0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\r0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\x00value:3\n"
 
197
            b"0000000000000000000000000000000000000000\x004444444444444444444444444444444444444444\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:4\n"
 
198
            b"1111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:0\n"
 
199
            b"1111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\r1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:1\n"
 
200
            b"1111111111111111111111111111111111111111\x002222222222222222222222222222222222222222\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:2\n"
 
201
            b"1111111111111111111111111111111111111111\x003333333333333333333333333333333333333333\x001111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\t1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\r1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\x00value:3\n"
 
202
            b"1111111111111111111111111111111111111111\x004444444444444444444444444444444444444444\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:4\n"
 
203
            b""
202
204
            )
203
205
        self.assertEqual(expected_node, node_bytes)
204
206
 
213
215
        del temp_file
214
216
        self.assertEqualApproxCompressed(9283, len(content))
215
217
        self.assertEqual(
216
 
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
217
 
            "row_lengths=1,2\n",
 
218
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
 
219
            b"row_lengths=1,2\n",
218
220
            content[:77])
219
221
        root = content[77:4096]
220
222
        leaf1 = content[4096:8192]
221
223
        leaf2 = content[8192:]
222
224
        root_bytes = zlib.decompress(root)
223
225
        expected_root = (
224
 
            "type=internal\n"
225
 
            "offset=0\n"
226
 
            ) + ("307" * 40) + "\n"
 
226
            b"type=internal\n"
 
227
            b"offset=0\n"
 
228
            ) + (b"307" * 40) + b"\n"
227
229
        self.assertEqual(expected_root, root_bytes)
228
230
        # We already know serialisation works for leaves, check key selection:
229
231
        leaf1_bytes = zlib.decompress(leaf1)
247
249
        del temp_file
248
250
        self.assertEqualApproxCompressed(155, len(content))
249
251
        self.assertEqual(
250
 
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
251
 
            "row_lengths=1\n",
 
252
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
 
253
            b"row_lengths=1\n",
252
254
            content[:74])
253
255
        # Check thelast page is well formed
254
256
        leaf2 = content[74:]
269
271
        del temp_file
270
272
        self.assertEqualApproxCompressed(9283, len(content))
271
273
        self.assertEqual(
272
 
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
273
 
            "row_lengths=1,2\n",
 
274
            b"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
 
275
            b"row_lengths=1,2\n",
274
276
            content[:77])
275
277
        # Check the last page is well formed
276
278
        leaf2 = content[8192:]
328
330
        del temp_file
329
331
        self.assertEqualApproxCompressed(12643, len(content))
330
332
        self.assertEqual(
331
 
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
332
 
            "row_lengths=1,3\n",
 
333
            b"B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
 
334
            b"row_lengths=1,3\n",
333
335
            content[:77])
334
336
        root = content[77:4096]
335
337
        leaf1 = content[4096:8192]
337
339
        leaf3 = content[12288:]
338
340
        root_bytes = zlib.decompress(root)
339
341
        expected_root = (
340
 
            "type=internal\n"
341
 
            "offset=0\n"
342
 
            + ("0" * 40) + "\x00" + ("91" * 40) + "\n"
343
 
            + ("1" * 40) + "\x00" + ("81" * 40) + "\n"
 
342
            b"type=internal\n"
 
343
            b"offset=0\n"
 
344
            + (b"0" * 40) + b"\x00" + (b"91" * 40) + b"\n"
 
345
            + (b"1" * 40) + b"\x00" + (b"81" * 40) + b"\n"
344
346
            )
345
347
        self.assertEqual(expected_root, root_bytes)
346
348
        # We assume the other leaf nodes have been written correctly - layering
635
637
        content = temp_file.read()
636
638
        del temp_file
637
639
        size = len(content)
638
 
        transport.put_bytes('index', (' '*offset)+content)
 
640
        transport.put_bytes('index', (b' '*offset)+content)
639
641
        return btree_index.BTreeGraphIndex(transport, 'index', size=size,
640
642
                                           offset=offset)
641
643
 
734
736
        self.assertEqual(200, index.key_count())
735
737
 
736
738
    def test__read_nodes_no_size_one_page_reads_once(self):
737
 
        self.make_index(nodes=[(('key',), 'value', ())])
 
739
        self.make_index(nodes=[((b'key',), b'value', ())])
738
740
        trans = transport.get_transport_from_url('trace+' + self.get_url())
739
741
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
740
742
        del trans._activity[:]
741
743
        nodes = dict(index._read_nodes([0]))
742
744
        self.assertEqual({0}, set(nodes))
743
745
        node = nodes[0]
744
 
        self.assertEqual([('key',)], node.all_keys())
 
746
        self.assertEqual([(b'key',)], node.all_keys())
745
747
        self.assertEqual([('get', 'index')], trans._activity)
746
748
 
747
749
    def test__read_nodes_no_size_multiple_pages(self):
847
849
    def test_key_too_big(self):
848
850
        # the size that matters here is the _compressed_ size of the key, so we can't
849
851
        # do a simple character repeat.
850
 
        bigKey = ''.join(map(repr, range(btree_index._PAGE_SIZE)))
 
852
        bigKey = b''.join(b'%d' % n for n in range(btree_index._PAGE_SIZE))
851
853
        self.assertRaises(errors.BadIndexKey,
852
854
                          self.make_index,
853
 
                          nodes=[((bigKey,), 'value', ())])
854
 
        
 
855
                          nodes=[((bigKey,), b'value', ())])
 
856
 
855
857
    def test_iter_all_only_root_no_size(self):
856
 
        self.make_index(nodes=[(('key',), 'value', ())])
 
858
        self.make_index(nodes=[((b'key',), b'value', ())])
857
859
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
858
860
        index = btree_index.BTreeGraphIndex(t, 'index', None)
859
861
        del t._activity[:]
860
 
        self.assertEqual([(('key',), 'value')],
 
862
        self.assertEqual([((b'key',), b'value')],
861
863
                         [x[1:] for x in index.iter_all_entries()])
862
864
        self.assertEqual([('get', 'index')], t._activity)
863
865
 
908
910
            self.assertEqualDiff(pprint.pformat(expected),
909
911
                                 pprint.pformat(t._activity))
910
912
 
911
 
    def _test_iter_entries_references_resolved(self):
912
 
        index = self.make_index(1, nodes=[
913
 
            (('name', ), 'data', ([('ref', ), ('ref', )], )),
914
 
            (('ref', ), 'refdata', ([], ))])
915
 
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),('ref',)),)),
916
 
            (index, ('ref', ), 'refdata', ((), ))},
917
 
            set(index.iter_entries([('name',), ('ref',)])))
918
 
 
919
913
    def test_iter_entries_references_2_refs_resolved(self):
920
914
        # iterating some entries reads just the pages needed. For now, to
921
915
        # get it working and start measuring, only 4K pages are read.
953
947
    def test_iter_key_prefix_wrong_length(self):
954
948
        index = self.make_index()
955
949
        self.assertRaises(errors.BadIndexKey, list,
956
 
            index.iter_entries_prefix([('foo', None)]))
 
950
            index.iter_entries_prefix([(b'foo', None)]))
957
951
        index = self.make_index(key_elements=2)
958
952
        self.assertRaises(errors.BadIndexKey, list,
959
 
            index.iter_entries_prefix([('foo', )]))
 
953
            index.iter_entries_prefix([(b'foo', )]))
960
954
        self.assertRaises(errors.BadIndexKey, list,
961
 
            index.iter_entries_prefix([('foo', None, None)]))
 
955
            index.iter_entries_prefix([(b'foo', None, None)]))
962
956
 
963
957
    def test_iter_key_prefix_1_key_element_no_refs(self):
964
 
        index = self.make_index( nodes=[
965
 
            (('name', ), 'data', ()),
966
 
            (('ref', ), 'refdata', ())])
967
 
        self.assertEqual({(index, ('name', ), 'data'),
968
 
            (index, ('ref', ), 'refdata')},
969
 
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
 
958
        index = self.make_index(nodes=[
 
959
            ((b'name', ), b'data', ()),
 
960
            ((b'ref', ), b'refdata', ())])
 
961
        self.assertEqual({(index, (b'name', ), b'data'),
 
962
            (index, (b'ref', ), b'refdata')},
 
963
            set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
970
964
 
971
965
    def test_iter_key_prefix_1_key_element_refs(self):
972
966
        index = self.make_index(1, nodes=[
973
 
            (('name', ), 'data', ([('ref', )], )),
974
 
            (('ref', ), 'refdata', ([], ))])
975
 
        self.assertEqual({(index, ('name', ), 'data', ((('ref',),),)),
976
 
            (index, ('ref', ), 'refdata', ((), ))},
977
 
            set(index.iter_entries_prefix([('name', ), ('ref', )])))
 
967
            ((b'name', ), b'data', ([(b'ref', )], )),
 
968
            ((b'ref', ), b'refdata', ([], ))])
 
969
        self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),)),
 
970
            (index, (b'ref', ), b'refdata', ((), ))},
 
971
            set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
978
972
 
979
973
    def test_iter_key_prefix_2_key_element_no_refs(self):
980
974
        index = self.make_index(key_elements=2, nodes=[
981
 
            (('name', 'fin1'), 'data', ()),
982
 
            (('name', 'fin2'), 'beta', ()),
983
 
            (('ref', 'erence'), 'refdata', ())])
984
 
        self.assertEqual({(index, ('name', 'fin1'), 'data'),
985
 
            (index, ('ref', 'erence'), 'refdata')},
986
 
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
987
 
        self.assertEqual({(index, ('name', 'fin1'), 'data'),
988
 
            (index, ('name', 'fin2'), 'beta')},
989
 
            set(index.iter_entries_prefix([('name', None)])))
 
975
            ((b'name', b'fin1'), b'data', ()),
 
976
            ((b'name', b'fin2'), b'beta', ()),
 
977
            ((b'ref', b'erence'), b'refdata', ())])
 
978
        self.assertEqual({(index, (b'name', b'fin1'), b'data'),
 
979
            (index, (b'ref', b'erence'), b'refdata')},
 
980
            set(index.iter_entries_prefix(
 
981
                [(b'name', b'fin1'), (b'ref', b'erence')])))
 
982
        self.assertEqual({(index, (b'name', b'fin1'), b'data'),
 
983
            (index, (b'name', b'fin2'), b'beta')},
 
984
            set(index.iter_entries_prefix([(b'name', None)])))
990
985
 
991
986
    def test_iter_key_prefix_2_key_element_refs(self):
992
987
        index = self.make_index(1, key_elements=2, nodes=[
993
 
            (('name', 'fin1'), 'data', ([('ref', 'erence')], )),
994
 
            (('name', 'fin2'), 'beta', ([], )),
995
 
            (('ref', 'erence'), 'refdata', ([], ))])
996
 
        self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
997
 
            (index, ('ref', 'erence'), 'refdata', ((), ))},
998
 
            set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
999
 
        self.assertEqual({(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
1000
 
            (index, ('name', 'fin2'), 'beta', ((), ))},
1001
 
            set(index.iter_entries_prefix([('name', None)])))
 
988
            ((b'name', b'fin1'), b'data', ([(b'ref', b'erence')], )),
 
989
            ((b'name', b'fin2'), b'beta', ([], )),
 
990
            ((b'ref', b'erence'), b'refdata', ([], ))])
 
991
        self.assertEqual(
 
992
            {(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
 
993
                (index, (b'ref', b'erence'), b'refdata', ((), ))},
 
994
            set(index.iter_entries_prefix(
 
995
                [(b'name', b'fin1'), (b'ref', b'erence')])))
 
996
        self.assertEqual(
 
997
            {(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
 
998
                (index, (b'name', b'fin2'), b'beta', ((), ))},
 
999
            set(index.iter_entries_prefix([(b'name', None)])))
1002
1000
 
1003
1001
    # XXX: external_references tests are duplicated in test_index.  We
1004
1002
    # probably should have per_graph_index tests...
1008
1006
 
1009
1007
    def test_external_references_no_results(self):
1010
1008
        index = self.make_index(ref_lists=1, nodes=[
1011
 
            (('key',), 'value', ([],))])
 
1009
            ((b'key',), b'value', ([],))])
1012
1010
        self.assertEqual(set(), index.external_references(0))
1013
1011
 
1014
1012
    def test_external_references_missing_ref(self):
1015
 
        missing_key = ('missing',)
 
1013
        missing_key = (b'missing',)
1016
1014
        index = self.make_index(ref_lists=1, nodes=[
1017
 
            (('key',), 'value', ([missing_key],))])
 
1015
            ((b'key',), b'value', ([missing_key],))])
1018
1016
        self.assertEqual({missing_key}, index.external_references(0))
1019
1017
 
1020
1018
    def test_external_references_multiple_ref_lists(self):
1021
 
        missing_key = ('missing',)
 
1019
        missing_key = (b'missing',)
1022
1020
        index = self.make_index(ref_lists=2, nodes=[
1023
 
            (('key',), 'value', ([], [missing_key]))])
 
1021
            ((b'key',), b'value', ([], [missing_key]))])
1024
1022
        self.assertEqual(set([]), index.external_references(0))
1025
1023
        self.assertEqual({missing_key}, index.external_references(1))
1026
1024
 
1027
1025
    def test_external_references_two_records(self):
1028
1026
        index = self.make_index(ref_lists=1, nodes=[
1029
 
            (('key-1',), 'value', ([('key-2',)],)),
1030
 
            (('key-2',), 'value', ([],)),
 
1027
            ((b'key-1',), b'value', ([(b'key-2',)],)),
 
1028
            ((b'key-2',), b'value', ([],)),
1031
1029
            ])
1032
1030
        self.assertEqual(set([]), index.external_references(0))
1033
1031
 
1034
1032
    def test__find_ancestors_one_page(self):
1035
 
        key1 = ('key-1',)
1036
 
        key2 = ('key-2',)
 
1033
        key1 = (b'key-1',)
 
1034
        key2 = (b'key-2',)
1037
1035
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1038
 
            (key1, 'value', ([key2],)),
1039
 
            (key2, 'value', ([],)),
 
1036
            (key1, b'value', ([key2],)),
 
1037
            (key2, b'value', ([],)),
1040
1038
            ])
1041
1039
        parent_map = {}
1042
1040
        missing_keys = set()
1046
1044
        self.assertEqual(set(), search_keys)
1047
1045
 
1048
1046
    def test__find_ancestors_one_page_w_missing(self):
1049
 
        key1 = ('key-1',)
1050
 
        key2 = ('key-2',)
1051
 
        key3 = ('key-3',)
 
1047
        key1 = (b'key-1',)
 
1048
        key2 = (b'key-2',)
 
1049
        key3 = (b'key-3',)
1052
1050
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1053
 
            (key1, 'value', ([key2],)),
1054
 
            (key2, 'value', ([],)),
 
1051
            (key1, b'value', ([key2],)),
 
1052
            (key2, b'value', ([],)),
1055
1053
            ])
1056
1054
        parent_map = {}
1057
1055
        missing_keys = set()
1064
1062
        self.assertEqual(set(), search_keys)
1065
1063
 
1066
1064
    def test__find_ancestors_one_parent_missing(self):
1067
 
        key1 = ('key-1',)
1068
 
        key2 = ('key-2',)
1069
 
        key3 = ('key-3',)
 
1065
        key1 = (b'key-1',)
 
1066
        key2 = (b'key-2',)
 
1067
        key3 = (b'key-3',)
1070
1068
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1071
 
            (key1, 'value', ([key2],)),
1072
 
            (key2, 'value', ([key3],)),
 
1069
            (key1, b'value', ([key2],)),
 
1070
            (key2, b'value', ([key3],)),
1073
1071
            ])
1074
1072
        parent_map = {}
1075
1073
        missing_keys = set()
1089
1087
        self.assertEqual(set([]), search_keys)
1090
1088
 
1091
1089
    def test__find_ancestors_dont_search_known(self):
1092
 
        key1 = ('key-1',)
1093
 
        key2 = ('key-2',)
1094
 
        key3 = ('key-3',)
 
1090
        key1 = (b'key-1',)
 
1091
        key2 = (b'key-2',)
 
1092
        key3 = (b'key-3',)
1095
1093
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1096
 
            (key1, 'value', ([key2],)),
1097
 
            (key2, 'value', ([key3],)),
1098
 
            (key3, 'value', ([],)),
 
1094
            (key1, b'value', ([key2],)),
 
1095
            (key2, b'value', ([key3],)),
 
1096
            (key3, b'value', ([],)),
1099
1097
            ])
1100
1098
        # We already know about key2, so we won't try to search for key3
1101
1099
        parent_map = {key2: (key3,)}
1114
1112
        ref_lists = ((),)
1115
1113
        rev_keys = []
1116
1114
        for i in range(400):
1117
 
            rev_id = '%s-%s-%s' % (email,
 
1115
            rev_id = ('%s-%s-%s' % (email,
1118
1116
                                   osutils.compact_date(start_time + i),
1119
 
                                   osutils.rand_chars(16))
 
1117
                                   osutils.rand_chars(16))).encode('ascii')
1120
1118
            rev_key = (rev_id,)
1121
 
            nodes.append((rev_key, 'value', ref_lists))
 
1119
            nodes.append((rev_key, b'value', ref_lists))
1122
1120
            # We have a ref 'list' of length 1, with a list of parents, with 1
1123
1121
            # parent which is a key
1124
1122
            ref_lists = ((rev_key,),)
1212
1210
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
1213
1211
 
1214
1212
    def test_LeafNode_1_0(self):
1215
 
        node_bytes = ("type=leaf\n"
1216
 
            "0000000000000000000000000000000000000000\x00\x00value:0\n"
1217
 
            "1111111111111111111111111111111111111111\x00\x00value:1\n"
1218
 
            "2222222222222222222222222222222222222222\x00\x00value:2\n"
1219
 
            "3333333333333333333333333333333333333333\x00\x00value:3\n"
1220
 
            "4444444444444444444444444444444444444444\x00\x00value:4\n")
 
1213
        node_bytes = (b"type=leaf\n"
 
1214
            b"0000000000000000000000000000000000000000\x00\x00value:0\n"
 
1215
            b"1111111111111111111111111111111111111111\x00\x00value:1\n"
 
1216
            b"2222222222222222222222222222222222222222\x00\x00value:2\n"
 
1217
            b"3333333333333333333333333333333333333333\x00\x00value:3\n"
 
1218
            b"4444444444444444444444444444444444444444\x00\x00value:4\n")
1221
1219
        node = btree_index._LeafNode(node_bytes, 1, 0)
1222
1220
        # We do direct access, or don't care about order, to leaf nodes most of
1223
1221
        # the time, so a dict is useful:
1224
1222
        self.assertEqual({
1225
 
            ("0000000000000000000000000000000000000000",): ("value:0", ()),
1226
 
            ("1111111111111111111111111111111111111111",): ("value:1", ()),
1227
 
            ("2222222222222222222222222222222222222222",): ("value:2", ()),
1228
 
            ("3333333333333333333333333333333333333333",): ("value:3", ()),
1229
 
            ("4444444444444444444444444444444444444444",): ("value:4", ()),
 
1223
            (b"0000000000000000000000000000000000000000",): (b"value:0", ()),
 
1224
            (b"1111111111111111111111111111111111111111",): (b"value:1", ()),
 
1225
            (b"2222222222222222222222222222222222222222",): (b"value:2", ()),
 
1226
            (b"3333333333333333333333333333333333333333",): (b"value:3", ()),
 
1227
            (b"4444444444444444444444444444444444444444",): (b"value:4", ()),
1230
1228
            }, dict(node.all_items()))
1231
1229
 
1232
1230
    def test_LeafNode_2_2(self):
1233
 
        node_bytes = ("type=leaf\n"
1234
 
            "00\x0000\x00\t00\x00ref00\x00value:0\n"
1235
 
            "00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
1236
 
            "11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
1237
 
            "11\x0044\x00\t11\x00ref00\x00value:4\n"
1238
 
            ""
 
1231
        node_bytes = (b"type=leaf\n"
 
1232
            b"00\x0000\x00\t00\x00ref00\x00value:0\n"
 
1233
            b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
 
1234
            b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
 
1235
            b"11\x0044\x00\t11\x00ref00\x00value:4\n"
 
1236
            b""
1239
1237
            )
1240
1238
        node = btree_index._LeafNode(node_bytes, 2, 2)
1241
1239
        # We do direct access, or don't care about order, to leaf nodes most of
1242
1240
        # the time, so a dict is useful:
1243
1241
        self.assertEqual({
1244
 
            ('00', '00'): ('value:0', ((), (('00', 'ref00'),))),
1245
 
            ('00', '11'): ('value:1',
1246
 
                ((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01')))),
1247
 
            ('11', '33'): ('value:3',
1248
 
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1249
 
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
 
1242
            (b'00', b'00'): (b'value:0', ((), ((b'00', b'ref00'),))),
 
1243
            (b'00', b'11'): (b'value:1', (((b'00', b'ref00'),),
 
1244
                ((b'00', b'ref00'), (b'01', b'ref01')))),
 
1245
            (b'11', b'33'): (b'value:3', (((b'11', b'ref22'),),
 
1246
                ((b'11', b'ref22'), (b'11', b'ref22')))),
 
1247
            (b'11', b'44'): (b'value:4', ((), ((b'11', b'ref00'),)))
1250
1248
            }, dict(node.all_items()))
1251
1249
 
1252
1250
    def test_InternalNode_1(self):
1253
 
        node_bytes = ("type=internal\n"
1254
 
            "offset=1\n"
1255
 
            "0000000000000000000000000000000000000000\n"
1256
 
            "1111111111111111111111111111111111111111\n"
1257
 
            "2222222222222222222222222222222222222222\n"
1258
 
            "3333333333333333333333333333333333333333\n"
1259
 
            "4444444444444444444444444444444444444444\n"
 
1251
        node_bytes = (b"type=internal\n"
 
1252
            b"offset=1\n"
 
1253
            b"0000000000000000000000000000000000000000\n"
 
1254
            b"1111111111111111111111111111111111111111\n"
 
1255
            b"2222222222222222222222222222222222222222\n"
 
1256
            b"3333333333333333333333333333333333333333\n"
 
1257
            b"4444444444444444444444444444444444444444\n"
1260
1258
            )
1261
1259
        node = btree_index._InternalNode(node_bytes)
1262
1260
        # We want to bisect to find the right children from this node, so a
1263
1261
        # vector is most useful.
1264
1262
        self.assertEqual([
1265
 
            ("0000000000000000000000000000000000000000",),
1266
 
            ("1111111111111111111111111111111111111111",),
1267
 
            ("2222222222222222222222222222222222222222",),
1268
 
            ("3333333333333333333333333333333333333333",),
1269
 
            ("4444444444444444444444444444444444444444",),
 
1263
            (b"0000000000000000000000000000000000000000",),
 
1264
            (b"1111111111111111111111111111111111111111",),
 
1265
            (b"2222222222222222222222222222222222222222",),
 
1266
            (b"3333333333333333333333333333333333333333",),
 
1267
            (b"4444444444444444444444444444444444444444",),
1270
1268
            ], node.keys)
1271
1269
        self.assertEqual(1, node.offset)
1272
1270
 
1273
1271
    def test_LeafNode_2_2(self):
1274
 
        node_bytes = ("type=leaf\n"
1275
 
            "00\x0000\x00\t00\x00ref00\x00value:0\n"
1276
 
            "00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
1277
 
            "11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
1278
 
            "11\x0044\x00\t11\x00ref00\x00value:4\n"
1279
 
            ""
 
1272
        node_bytes = (b"type=leaf\n"
 
1273
            b"00\x0000\x00\t00\x00ref00\x00value:0\n"
 
1274
            b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
 
1275
            b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
 
1276
            b"11\x0044\x00\t11\x00ref00\x00value:4\n"
 
1277
            b""
1280
1278
            )
1281
1279
        node = btree_index._LeafNode(node_bytes, 2, 2)
1282
1280
        # We do direct access, or don't care about order, to leaf nodes most of
1283
1281
        # the time, so a dict is useful:
1284
1282
        self.assertEqual({
1285
 
            ('00', '00'): ('value:0', ((), (('00', 'ref00'),))),
1286
 
            ('00', '11'): ('value:1',
1287
 
                ((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01')))),
1288
 
            ('11', '33'): ('value:3',
1289
 
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1290
 
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
 
1283
            (b'00', b'00'): (b'value:0', ((), ((b'00', b'ref00'),))),
 
1284
            (b'00', b'11'): (b'value:1', (((b'00', b'ref00'),),
 
1285
                ((b'00', b'ref00'), (b'01', b'ref01')))),
 
1286
            (b'11', b'33'): (b'value:3', (((b'11', b'ref22'),),
 
1287
                ((b'11', b'ref22'), (b'11', b'ref22')))),
 
1288
            (b'11', b'44'): (b'value:4', ((), ((b'11', b'ref00'),)))
1291
1289
            }, dict(node.all_items()))
1292
1290
 
1293
1291
    def assertFlattened(self, expected, key, value, refs):
1294
1292
        flat_key, flat_line = self.parse_btree._flatten_node(
1295
1293
            (None, key, value, refs), bool(refs))
1296
 
        self.assertEqual('\x00'.join(key), flat_key)
 
1294
        self.assertEqual(b'\x00'.join(key), flat_key)
1297
1295
        self.assertEqual(expected, flat_line)
1298
1296
 
1299
1297
    def test__flatten_node(self):
1300
 
        self.assertFlattened('key\0\0value\n', ('key',), 'value', [])
1301
 
        self.assertFlattened('key\0tuple\0\0value str\n',
1302
 
                             ('key', 'tuple'), 'value str', [])
1303
 
        self.assertFlattened('key\0tuple\0triple\0\0value str\n',
1304
 
                             ('key', 'tuple', 'triple'), 'value str', [])
1305
 
        self.assertFlattened('k\0t\0s\0ref\0value str\n',
1306
 
                             ('k', 't', 's'), 'value str', [[('ref',)]])
1307
 
        self.assertFlattened('key\0tuple\0ref\0key\0value str\n',
1308
 
                             ('key', 'tuple'), 'value str', [[('ref', 'key')]])
1309
 
        self.assertFlattened("00\x0000\x00\t00\x00ref00\x00value:0\n",
1310
 
            ('00', '00'), 'value:0', ((), (('00', 'ref00'),)))
1311
 
        self.assertFlattened(
1312
 
            "00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n",
1313
 
            ('00', '11'), 'value:1',
1314
 
                ((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01'))))
1315
 
        self.assertFlattened(
1316
 
            "11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n",
1317
 
            ('11', '33'), 'value:3',
1318
 
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22'))))
1319
 
        self.assertFlattened(
1320
 
            "11\x0044\x00\t11\x00ref00\x00value:4\n",
1321
 
            ('11', '44'), 'value:4', ((), (('11', 'ref00'),)))
 
1298
        self.assertFlattened(b'key\0\0value\n', (b'key',), b'value', [])
 
1299
        self.assertFlattened(b'key\0tuple\0\0value str\n',
 
1300
            (b'key', b'tuple'), b'value str', [])
 
1301
        self.assertFlattened(b'key\0tuple\0triple\0\0value str\n',
 
1302
            (b'key', b'tuple', b'triple'), b'value str', [])
 
1303
        self.assertFlattened(b'k\0t\0s\0ref\0value str\n',
 
1304
            (b'k', b't', b's'), b'value str', [[(b'ref',)]])
 
1305
        self.assertFlattened(b'key\0tuple\0ref\0key\0value str\n',
 
1306
            (b'key', b'tuple'), b'value str', [[(b'ref', b'key')]])
 
1307
        self.assertFlattened(b"00\x0000\x00\t00\x00ref00\x00value:0\n",
 
1308
            (b'00', b'00'), b'value:0', ((), ((b'00', b'ref00'),)))
 
1309
        self.assertFlattened(
 
1310
            b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n",
 
1311
            (b'00', b'11'), b'value:1',
 
1312
                (((b'00', b'ref00'),), ((b'00', b'ref00'), (b'01', b'ref01'))))
 
1313
        self.assertFlattened(
 
1314
            b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n",
 
1315
            (b'11', b'33'), b'value:3',
 
1316
                (((b'11', b'ref22'),), ((b'11', b'ref22'), (b'11', b'ref22'))))
 
1317
        self.assertFlattened(
 
1318
            b"11\x0044\x00\t11\x00ref00\x00value:4\n",
 
1319
            (b'11', b'44'), b'value:4', ((), ((b'11', b'ref00'),)))
1322
1320
 
1323
1321
 
1324
1322
class TestCompiledBtree(tests.TestCase):
1394
1392
        index._key_count = key_count
1395
1393
        index._row_lengths = row_lengths
1396
1394
        index._compute_row_offsets()
1397
 
        index._root_node = btree_index._InternalNode('internal\noffset=0\n')
 
1395
        index._root_node = btree_index._InternalNode(b'internal\noffset=0\n')
1398
1396
        self.set_cached_offsets(index, cached_offsets)
1399
1397
 
1400
1398
    def make_100_node_index(self):