« back to all changes in this revision
Viewing changes to breezy/tests/test_btree_index.py
- browse files at revision 6690.6.5
- compare with another revision
- download diff
- download tarball
- view history from revision 6690.6.5
- Committer: Jelmer Vernooij
- Date: 2017-07-23 22:06:41 UTC
- mfrom: (6738 trunk)
- mto: This revision was merged to the branch mainline in revision 6739.
- Revision ID: jelmer@jelmer.uk-20170723220641-69eczax9bmv8d6kk
Merge trunk, address review comments.
- files added:
- breezy/help_topics/en/missing-extensions.txt
- files modified:
- NEWS
added
removed
breezy/tests/test_btree_index.py
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):
Loggerhead is a web-based interface for Breezy
Version: 2.0.1