« back to all changes in this revision
Viewing changes to bzrlib/tests/test_chk_map.py
- browse files at revision 4194.1.1
- compare with another revision
- compare with revision 5020.1.1
- download diff
- download tarball
- view history from revision 4194.1.1
- Committer: Vincent Ladeuil
- Date: 2009-03-24 09:38:47 UTC
- mfrom: (3735.2.165 brisbane-core)
- mto: (3735.40.1 for-jam) (4194.1.3 groupcompress-python-only)
- mto: This revision was merged to the branch mainline in revision 4280.
- Revision ID: v.ladeuil+lp@free.fr-20090324093847-zwbjrv8awx73feiz
create thread for bbc
- files added:
- bzrlib/_chk_map_py.py
- bzrlib/tests/per_repository_chk
- files modified:
- .bzrignore
added
removed
bzrlib/tests/test_chk_map.py
1
# Copyright (C) 2008 Canonical Ltd
2
#
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
7
#
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
12
#
13
# You should have received a copy of the GNU General Public License
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
16
17
"""Tests for maps built on a CHK versionedfiles facility."""
18
19
from itertools import izip
20
21
from bzrlib import (
22
chk_map,
23
osutils,
24
tests,
25
)
26
from bzrlib.chk_map import (
27
CHKMap,
28
InternalNode,
29
LeafNode,
30
Node,
31
)
32
33
34
class TestNode(tests.TestCase):
35
36
def assertCommonPrefix(self, expected_common, prefix, key):
37
common = Node.common_prefix(prefix, key)
38
self.assertTrue(len(common) <= len(prefix))
39
self.assertTrue(len(common) <= len(key))
40
self.assertStartsWith(prefix, common)
41
self.assertStartsWith(key, common)
42
self.assertEquals(expected_common, common)
43
44
def test_common_prefix(self):
45
self.assertCommonPrefix('beg', 'beg', 'begin')
46
47
def test_no_common_prefix(self):
48
self.assertCommonPrefix('', 'begin', 'end')
49
50
def test_equal(self):
51
self.assertCommonPrefix('begin', 'begin', 'begin')
52
53
def test_not_a_prefix(self):
54
self.assertCommonPrefix('b', 'begin', 'b')
55
56
57
class TestCaseWithStore(tests.TestCaseWithTransport):
58
59
def get_chk_bytes(self):
60
# The easiest way to get a CHK store is a development5 repository and
61
# then work with the chk_bytes attribute directly.
62
repo = self.make_repository(".", format="development5")
63
repo.lock_write()
64
self.addCleanup(repo.unlock)
65
repo.start_write_group()
66
self.addCleanup(repo.abort_write_group)
67
return repo.chk_bytes
68
69
def _get_map(self, a_dict, maximum_size=0, chk_bytes=None, key_width=1,
70
search_key_func=None):
71
if chk_bytes is None:
72
chk_bytes = self.get_chk_bytes()
73
root_key = CHKMap.from_dict(chk_bytes, a_dict,
74
maximum_size=maximum_size, key_width=key_width,
75
search_key_func=search_key_func)
76
chkmap = CHKMap(chk_bytes, root_key, search_key_func=search_key_func)
77
return chkmap
78
79
def read_bytes(self, chk_bytes, key):
80
stream = chk_bytes.get_record_stream([key], 'unordered', True)
81
record = stream.next()
82
if record.storage_kind == 'absent':
83
self.fail('Store does not contain the key %s' % (key,))
84
return record.get_bytes_as("fulltext")
85
86
def to_dict(self, node, *args):
87
return dict(node.iteritems(*args))
88
89
90
class TestMap(TestCaseWithStore):
91
92
def assertHasABMap(self, chk_bytes):
93
ab_leaf_bytes = 'chkleaf:\n0\n1\n1\na\n\x001\nb\n'
94
ab_sha1 = osutils.sha_string(ab_leaf_bytes)
95
self.assertEqual('90986195696b177c8895d48fdb4b7f2366f798a0', ab_sha1)
96
root_key = ('sha1:' + ab_sha1,)
97
self.assertEqual(ab_leaf_bytes, self.read_bytes(chk_bytes, root_key))
98
return root_key
99
100
def assertHasEmptyMap(self, chk_bytes):
101
empty_leaf_bytes = 'chkleaf:\n0\n1\n0\n\n'
102
empty_sha1 = osutils.sha_string(empty_leaf_bytes)
103
self.assertEqual('8571e09bf1bcc5b9621ce31b3d4c93d6e9a1ed26', empty_sha1)
104
root_key = ('sha1:' + empty_sha1,)
105
self.assertEqual(empty_leaf_bytes, self.read_bytes(chk_bytes, root_key))
106
return root_key
107
108
def assertMapLayoutEqual(self, map_one, map_two):
109
"""Assert that the internal structure is identical between the maps."""
110
map_one._ensure_root()
111
node_one_stack = [map_one._root_node]
112
map_two._ensure_root()
113
node_two_stack = [map_two._root_node]
114
while node_one_stack:
115
node_one = node_one_stack.pop()
116
node_two = node_two_stack.pop()
117
if node_one.__class__ != node_two.__class__:
118
self.assertEqualDiff(map_one._dump_tree(include_keys=True),
119
map_two._dump_tree(include_keys=True))
120
self.assertEqual(node_one._search_prefix,
121
node_two._search_prefix)
122
if isinstance(node_one, InternalNode):
123
# Internal nodes must have identical references
124
self.assertEqual(sorted(node_one._items.keys()),
125
sorted(node_two._items.keys()))
126
node_one_stack.extend(node_one._iter_nodes(map_one._store))
127
node_two_stack.extend(node_two._iter_nodes(map_two._store))
128
else:
129
# Leaf nodes must have identical contents
130
self.assertEqual(node_one._items, node_two._items)
131
self.assertEquals([], node_two_stack)
132
133
def assertCanonicalForm(self, chkmap):
134
"""Assert that the chkmap is in 'canonical' form.
135
136
We do this by adding all of the key value pairs from scratch, both in
137
forward order and reverse order, and assert that the final tree layout
138
is identical.
139
"""
140
items = list(chkmap.iteritems())
141
map_forward = chk_map.CHKMap(None, None)
142
map_forward._root_node.set_maximum_size(chkmap._root_node.maximum_size)
143
for key, value in items:
144
map_forward.map(key, value)
145
self.assertMapLayoutEqual(map_forward, chkmap)
146
map_reverse = chk_map.CHKMap(None, None)
147
map_reverse._root_node.set_maximum_size(chkmap._root_node.maximum_size)
148
for key, value in reversed(items):
149
map_reverse.map(key, value)
150
self.assertMapLayoutEqual(map_reverse, chkmap)
151
152
def test_assert_map_layout_equal(self):
153
store = self.get_chk_bytes()
154
map_one = CHKMap(store, None)
155
map_one._root_node.set_maximum_size(20)
156
map_two = CHKMap(store, None)
157
map_two._root_node.set_maximum_size(20)
158
self.assertMapLayoutEqual(map_one, map_two)
159
map_one.map('aaa', 'value')
160
self.assertRaises(AssertionError,
161
self.assertMapLayoutEqual, map_one, map_two)
162
map_two.map('aaa', 'value')
163
self.assertMapLayoutEqual(map_one, map_two)
164
# Split the tree, so we ensure that internal nodes and leaf nodes are
165
# properly checked
166
map_one.map('aab', 'value')
167
self.assertIsInstance(map_one._root_node, InternalNode)
168
self.assertRaises(AssertionError,
169
self.assertMapLayoutEqual, map_one, map_two)
170
map_two.map('aab', 'value')
171
self.assertMapLayoutEqual(map_one, map_two)
172
map_one.map('aac', 'value')
173
self.assertRaises(AssertionError,
174
self.assertMapLayoutEqual, map_one, map_two)
175
self.assertCanonicalForm(map_one)
176
177
def test_from_dict_empty(self):
178
chk_bytes = self.get_chk_bytes()
179
root_key = CHKMap.from_dict(chk_bytes, {})
180
# Check the data was saved and inserted correctly.
181
expected_root_key = self.assertHasEmptyMap(chk_bytes)
182
self.assertEqual(expected_root_key, root_key)
183
184
def test_from_dict_ab(self):
185
chk_bytes = self.get_chk_bytes()
186
root_key = CHKMap.from_dict(chk_bytes, {"a": "b"})
187
# Check the data was saved and inserted correctly.
188
expected_root_key = self.assertHasABMap(chk_bytes)
189
self.assertEqual(expected_root_key, root_key)
190
191
def test_apply_empty_ab(self):
192
# applying a delta (None, "a", "b") to an empty chkmap generates the
193
# same map as from_dict_ab.
194
chk_bytes = self.get_chk_bytes()
195
root_key = CHKMap.from_dict(chk_bytes, {})
196
chkmap = CHKMap(chk_bytes, root_key)
197
new_root = chkmap.apply_delta([(None, "a", "b")])
198
# Check the data was saved and inserted correctly.
199
expected_root_key = self.assertHasABMap(chk_bytes)
200
self.assertEqual(expected_root_key, new_root)
201
# The update should have left us with an in memory root node, with an
202
# updated key.
203
self.assertEqual(new_root, chkmap._root_node._key)
204
205
def test_apply_ab_empty(self):
206
# applying a delta ("a", None, None) to a map with 'a' in it generates
207
# an empty map.
208
chk_bytes = self.get_chk_bytes()
209
root_key = CHKMap.from_dict(chk_bytes, {("a",):"b"})
210
chkmap = CHKMap(chk_bytes, root_key)
211
new_root = chkmap.apply_delta([(("a",), None, None)])
212
# Check the data was saved and inserted correctly.
213
expected_root_key = self.assertHasEmptyMap(chk_bytes)
214
self.assertEqual(expected_root_key, new_root)
215
# The update should have left us with an in memory root node, with an
216
# updated key.
217
self.assertEqual(new_root, chkmap._root_node._key)
218
219
def test_apply_delta_is_deterministic(self):
220
chk_bytes = self.get_chk_bytes()
221
chkmap1 = CHKMap(chk_bytes, None)
222
chkmap1._root_node.set_maximum_size(10)
223
chkmap1.apply_delta([(None, ('aaa',), 'common'),
224
(None, ('bba',), 'target2'),
225
(None, ('bbb',), 'common')])
226
root_key1 = chkmap1._save()
227
self.assertCanonicalForm(chkmap1)
228
229
chkmap2 = CHKMap(chk_bytes, None)
230
chkmap2._root_node.set_maximum_size(10)
231
chkmap2.apply_delta([(None, ('bbb',), 'common'),
232
(None, ('bba',), 'target2'),
233
(None, ('aaa',), 'common')])
234
root_key2 = chkmap2._save()
235
self.assertEqualDiff(chkmap1._dump_tree(include_keys=True),
236
chkmap2._dump_tree(include_keys=True))
237
self.assertEqual(root_key1, root_key2)
238
self.assertCanonicalForm(chkmap2)
239
240
def test_stable_splitting(self):
241
store = self.get_chk_bytes()
242
chkmap = CHKMap(store, None)
243
# Should fit 2 keys per LeafNode
244
chkmap._root_node.set_maximum_size(35)
245
chkmap.map(('aaa',), 'v')
246
self.assertEqualDiff("'' LeafNode\n"
247
" ('aaa',) 'v'\n",
248
chkmap._dump_tree())
249
chkmap.map(('aab',), 'v')
250
self.assertEqualDiff("'' LeafNode\n"
251
" ('aaa',) 'v'\n"
252
" ('aab',) 'v'\n",
253
chkmap._dump_tree())
254
self.assertCanonicalForm(chkmap)
255
256
# Creates a new internal node, and splits the others into leaves
257
chkmap.map(('aac',), 'v')
258
self.assertEqualDiff("'' InternalNode\n"
259
" 'aaa' LeafNode\n"
260
" ('aaa',) 'v'\n"
261
" 'aab' LeafNode\n"
262
" ('aab',) 'v'\n"
263
" 'aac' LeafNode\n"
264
" ('aac',) 'v'\n",
265
chkmap._dump_tree())
266
self.assertCanonicalForm(chkmap)
267
268
# Splits again, because it can't fit in the current structure
269
chkmap.map(('bbb',), 'v')
270
self.assertEqualDiff("'' InternalNode\n"
271
" 'a' InternalNode\n"
272
" 'aaa' LeafNode\n"
273
" ('aaa',) 'v'\n"
274
" 'aab' LeafNode\n"
275
" ('aab',) 'v'\n"
276
" 'aac' LeafNode\n"
277
" ('aac',) 'v'\n"
278
" 'b' LeafNode\n"
279
" ('bbb',) 'v'\n",
280
chkmap._dump_tree())
281
self.assertCanonicalForm(chkmap)
282
283
def test_map_splits_with_longer_key(self):
284
store = self.get_chk_bytes()
285
chkmap = CHKMap(store, None)
286
# Should fit 1 key per LeafNode
287
chkmap._root_node.set_maximum_size(10)
288
chkmap.map(('aaa',), 'v')
289
chkmap.map(('aaaa',), 'v')
290
self.assertCanonicalForm(chkmap)
291
self.assertIsInstance(chkmap._root_node, InternalNode)
292
293
def test_with_linefeed_in_key(self):
294
store = self.get_chk_bytes()
295
chkmap = CHKMap(store, None)
296
# Should fit 1 key per LeafNode
297
chkmap._root_node.set_maximum_size(10)
298
chkmap.map(('a\ra',), 'val1')
299
chkmap.map(('a\rb',), 'val2')
300
chkmap.map(('ac',), 'val3')
301
self.assertCanonicalForm(chkmap)
302
self.assertEqualDiff("'' InternalNode\n"
303
" 'a\\r' InternalNode\n"
304
" 'a\\ra' LeafNode\n"
305
" ('a\\ra',) 'val1'\n"
306
" 'a\\rb' LeafNode\n"
307
" ('a\\rb',) 'val2'\n"
308
" 'ac' LeafNode\n"
309
" ('ac',) 'val3'\n",
310
chkmap._dump_tree())
311
# We should also successfully serialise and deserialise these items
312
root_key = chkmap._save()
313
chkmap = CHKMap(store, root_key)
314
self.assertEqualDiff("'' InternalNode\n"
315
" 'a\\r' InternalNode\n"
316
" 'a\\ra' LeafNode\n"
317
" ('a\\ra',) 'val1'\n"
318
" 'a\\rb' LeafNode\n"
319
" ('a\\rb',) 'val2'\n"
320
" 'ac' LeafNode\n"
321
" ('ac',) 'val3'\n",
322
chkmap._dump_tree())
323
324
def test_deep_splitting(self):
325
store = self.get_chk_bytes()
326
chkmap = CHKMap(store, None)
327
# Should fit 2 keys per LeafNode
328
chkmap._root_node.set_maximum_size(40)
329
chkmap.map(('aaaaaaaa',), 'v')
330
chkmap.map(('aaaaabaa',), 'v')
331
self.assertEqualDiff("'' LeafNode\n"
332
" ('aaaaaaaa',) 'v'\n"
333
" ('aaaaabaa',) 'v'\n",
334
chkmap._dump_tree())
335
chkmap.map(('aaabaaaa',), 'v')
336
chkmap.map(('aaababaa',), 'v')
337
self.assertEqualDiff("'' InternalNode\n"
338
" 'aaaa' LeafNode\n"
339
" ('aaaaaaaa',) 'v'\n"
340
" ('aaaaabaa',) 'v'\n"
341
" 'aaab' LeafNode\n"
342
" ('aaabaaaa',) 'v'\n"
343
" ('aaababaa',) 'v'\n",
344
chkmap._dump_tree())
345
chkmap.map(('aaabacaa',), 'v')
346
chkmap.map(('aaabadaa',), 'v')
347
self.assertEqualDiff("'' InternalNode\n"
348
" 'aaaa' LeafNode\n"
349
" ('aaaaaaaa',) 'v'\n"
350
" ('aaaaabaa',) 'v'\n"
351
" 'aaab' InternalNode\n"
352
" 'aaabaa' LeafNode\n"
353
" ('aaabaaaa',) 'v'\n"
354
" 'aaabab' LeafNode\n"
355
" ('aaababaa',) 'v'\n"
356
" 'aaabac' LeafNode\n"
357
" ('aaabacaa',) 'v'\n"
358
" 'aaabad' LeafNode\n"
359
" ('aaabadaa',) 'v'\n",
360
chkmap._dump_tree())
361
chkmap.map(('aaababba',), 'val')
362
chkmap.map(('aaababca',), 'val')
363
self.assertEqualDiff("'' InternalNode\n"
364
" 'aaaa' LeafNode\n"
365
" ('aaaaaaaa',) 'v'\n"
366
" ('aaaaabaa',) 'v'\n"
367
" 'aaab' InternalNode\n"
368
" 'aaabaa' LeafNode\n"
369
" ('aaabaaaa',) 'v'\n"
370
" 'aaabab' InternalNode\n"
371
" 'aaababa' LeafNode\n"
372
" ('aaababaa',) 'v'\n"
373
" 'aaababb' LeafNode\n"
374
" ('aaababba',) 'val'\n"
375
" 'aaababc' LeafNode\n"
376
" ('aaababca',) 'val'\n"
377
" 'aaabac' LeafNode\n"
378
" ('aaabacaa',) 'v'\n"
379
" 'aaabad' LeafNode\n"
380
" ('aaabadaa',) 'v'\n",
381
chkmap._dump_tree())
382
# Now we add a node that should fit around an existing InternalNode,
383
# but has a slightly different key prefix, which causes a new
384
# InternalNode split
385
chkmap.map(('aaabDaaa',), 'v')
386
self.assertEqualDiff("'' InternalNode\n"
387
" 'aaaa' LeafNode\n"
388
" ('aaaaaaaa',) 'v'\n"
389
" ('aaaaabaa',) 'v'\n"
390
" 'aaab' InternalNode\n"
391
" 'aaabD' LeafNode\n"
392
" ('aaabDaaa',) 'v'\n"
393
" 'aaaba' InternalNode\n"
394
" 'aaabaa' LeafNode\n"
395
" ('aaabaaaa',) 'v'\n"
396
" 'aaabab' InternalNode\n"
397
" 'aaababa' LeafNode\n"
398
" ('aaababaa',) 'v'\n"
399
" 'aaababb' LeafNode\n"
400
" ('aaababba',) 'val'\n"
401
" 'aaababc' LeafNode\n"
402
" ('aaababca',) 'val'\n"
403
" 'aaabac' LeafNode\n"
404
" ('aaabacaa',) 'v'\n"
405
" 'aaabad' LeafNode\n"
406
" ('aaabadaa',) 'v'\n",
407
chkmap._dump_tree())
408
409
def test_map_collapses_if_size_changes(self):
410
store = self.get_chk_bytes()
411
chkmap = CHKMap(store, None)
412
# Should fit 2 keys per LeafNode
413
chkmap._root_node.set_maximum_size(35)
414
chkmap.map(('aaa',), 'v')
415
chkmap.map(('aab',), 'very long value that splits')
416
self.assertEqualDiff("'' InternalNode\n"
417
" 'aaa' LeafNode\n"
418
" ('aaa',) 'v'\n"
419
" 'aab' LeafNode\n"
420
" ('aab',) 'very long value that splits'\n",
421
chkmap._dump_tree())
422
self.assertCanonicalForm(chkmap)
423
# Now changing the value to something small should cause a rebuild
424
chkmap.map(('aab',), 'v')
425
self.assertEqualDiff("'' LeafNode\n"
426
" ('aaa',) 'v'\n"
427
" ('aab',) 'v'\n",
428
chkmap._dump_tree())
429
self.assertCanonicalForm(chkmap)
430
431
def test_map_double_deep_collapses(self):
432
store = self.get_chk_bytes()
433
chkmap = CHKMap(store, None)
434
# Should fit 3 small keys per LeafNode
435
chkmap._root_node.set_maximum_size(40)
436
chkmap.map(('aaa',), 'v')
437
chkmap.map(('aab',), 'very long value that splits')
438
chkmap.map(('abc',), 'v')
439
self.assertEqualDiff("'' InternalNode\n"
440
" 'aa' InternalNode\n"
441
" 'aaa' LeafNode\n"
442
" ('aaa',) 'v'\n"
443
" 'aab' LeafNode\n"
444
" ('aab',) 'very long value that splits'\n"
445
" 'ab' LeafNode\n"
446
" ('abc',) 'v'\n",
447
chkmap._dump_tree())
448
chkmap.map(('aab',), 'v')
449
self.assertCanonicalForm(chkmap)
450
self.assertEqualDiff("'' LeafNode\n"
451
" ('aaa',) 'v'\n"
452
" ('aab',) 'v'\n"
453
" ('abc',) 'v'\n",
454
chkmap._dump_tree())
455
456
def test_stable_unmap(self):
457
store = self.get_chk_bytes()
458
chkmap = CHKMap(store, None)
459
# Should fit 2 keys per LeafNode
460
chkmap._root_node.set_maximum_size(35)
461
chkmap.map(('aaa',), 'v')
462
chkmap.map(('aab',), 'v')
463
self.assertEqualDiff("'' LeafNode\n"
464
" ('aaa',) 'v'\n"
465
" ('aab',) 'v'\n",
466
chkmap._dump_tree())
467
# Creates a new internal node, and splits the others into leaves
468
chkmap.map(('aac',), 'v')
469
self.assertEqualDiff("'' InternalNode\n"
470
" 'aaa' LeafNode\n"
471
" ('aaa',) 'v'\n"
472
" 'aab' LeafNode\n"
473
" ('aab',) 'v'\n"
474
" 'aac' LeafNode\n"
475
" ('aac',) 'v'\n",
476
chkmap._dump_tree())
477
self.assertCanonicalForm(chkmap)
478
# Now lets unmap one of the keys, and assert that we collapse the
479
# structures.
480
chkmap.unmap(('aac',))
481
self.assertEqualDiff("'' LeafNode\n"
482
" ('aaa',) 'v'\n"
483
" ('aab',) 'v'\n",
484
chkmap._dump_tree())
485
self.assertCanonicalForm(chkmap)
486
487
def test_unmap_double_deep(self):
488
store = self.get_chk_bytes()
489
chkmap = CHKMap(store, None)
490
# Should fit 3 keys per LeafNode
491
chkmap._root_node.set_maximum_size(40)
492
chkmap.map(('aaa',), 'v')
493
chkmap.map(('aaab',), 'v')
494
chkmap.map(('aab',), 'very long value')
495
chkmap.map(('abc',), 'v')
496
self.assertEqualDiff("'' InternalNode\n"
497
" 'aa' InternalNode\n"
498
" 'aaa' LeafNode\n"
499
" ('aaa',) 'v'\n"
500
" ('aaab',) 'v'\n"
501
" 'aab' LeafNode\n"
502
" ('aab',) 'very long value'\n"
503
" 'ab' LeafNode\n"
504
" ('abc',) 'v'\n",
505
chkmap._dump_tree())
506
# Removing the 'aab' key should cause everything to collapse back to a
507
# single node
508
chkmap.unmap(('aab',))
509
self.assertEqualDiff("'' LeafNode\n"
510
" ('aaa',) 'v'\n"
511
" ('aaab',) 'v'\n"
512
" ('abc',) 'v'\n",
513
chkmap._dump_tree())
514
515
def test_unmap_double_deep_non_empty_leaf(self):
516
store = self.get_chk_bytes()
517
chkmap = CHKMap(store, None)
518
# Should fit 3 keys per LeafNode
519
chkmap._root_node.set_maximum_size(40)
520
chkmap.map(('aaa',), 'v')
521
chkmap.map(('aab',), 'long value')
522
chkmap.map(('aabb',), 'v')
523
chkmap.map(('abc',), 'v')
524
self.assertEqualDiff("'' InternalNode\n"
525
" 'aa' InternalNode\n"
526
" 'aaa' LeafNode\n"
527
" ('aaa',) 'v'\n"
528
" 'aab' LeafNode\n"
529
" ('aab',) 'long value'\n"
530
" ('aabb',) 'v'\n"
531
" 'ab' LeafNode\n"
532
" ('abc',) 'v'\n",
533
chkmap._dump_tree())
534
# Removing the 'aab' key should cause everything to collapse back to a
535
# single node
536
chkmap.unmap(('aab',))
537
self.assertEqualDiff("'' LeafNode\n"
538
" ('aaa',) 'v'\n"
539
" ('aabb',) 'v'\n"
540
" ('abc',) 'v'\n",
541
chkmap._dump_tree())
542
543
def test_unmap_with_known_internal_node_doesnt_page(self):
544
store = self.get_chk_bytes()
545
chkmap = CHKMap(store, None)
546
# Should fit 3 keys per LeafNode
547
chkmap._root_node.set_maximum_size(30)
548
chkmap.map(('aaa',), 'v')
549
chkmap.map(('aab',), 'v')
550
chkmap.map(('aac',), 'v')
551
chkmap.map(('abc',), 'v')
552
chkmap.map(('acd',), 'v')
553
self.assertEqualDiff("'' InternalNode\n"
554
" 'aa' InternalNode\n"
555
" 'aaa' LeafNode\n"
556
" ('aaa',) 'v'\n"
557
" 'aab' LeafNode\n"
558
" ('aab',) 'v'\n"
559
" 'aac' LeafNode\n"
560
" ('aac',) 'v'\n"
561
" 'ab' LeafNode\n"
562
" ('abc',) 'v'\n"
563
" 'ac' LeafNode\n"
564
" ('acd',) 'v'\n",
565
chkmap._dump_tree())
566
# Save everything to the map, and start over
567
chkmap = CHKMap(store, chkmap._save())
568
# Mapping an 'aa' key loads the internal node, but should not map the
569
# 'ab' and 'ac' nodes
570
chkmap.map(('aad',), 'v')
571
self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
572
self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
573
self.assertIsInstance(chkmap._root_node._items['ac'], tuple)
574
# Unmapping 'acd' can notice that 'aa' is an InternalNode and not have
575
# to map in 'ab'
576
chkmap.unmap(('acd',))
577
self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
578
self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
579
580
def test_unmap_without_fitting_doesnt_page_in(self):
581
store = self.get_chk_bytes()
582
chkmap = CHKMap(store, None)
583
# Should fit 2 keys per LeafNode
584
chkmap._root_node.set_maximum_size(20)
585
chkmap.map(('aaa',), 'v')
586
chkmap.map(('aab',), 'v')
587
self.assertEqualDiff("'' InternalNode\n"
588
" 'aaa' LeafNode\n"
589
" ('aaa',) 'v'\n"
590
" 'aab' LeafNode\n"
591
" ('aab',) 'v'\n",
592
chkmap._dump_tree())
593
# Save everything to the map, and start over
594
chkmap = CHKMap(store, chkmap._save())
595
chkmap.map(('aac',), 'v')
596
chkmap.map(('aad',), 'v')
597
chkmap.map(('aae',), 'v')
598
chkmap.map(('aaf',), 'v')
599
# At this point, the previous nodes should not be paged in, but the
600
# newly added nodes would be
601
self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
602
self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
603
self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
604
self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
605
self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
606
self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
607
# Now unmapping one of the new nodes will use only the already-paged-in
608
# nodes to determine that we don't need to do more.
609
chkmap.unmap(('aaf',))
610
self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
611
self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
612
self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
613
self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
614
self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
615
616
def test_unmap_pages_in_if_necessary(self):
617
store = self.get_chk_bytes()
618
chkmap = CHKMap(store, None)
619
# Should fit 2 keys per LeafNode
620
chkmap._root_node.set_maximum_size(30)
621
chkmap.map(('aaa',), 'val')
622
chkmap.map(('aab',), 'val')
623
chkmap.map(('aac',), 'val')
624
self.assertEqualDiff("'' InternalNode\n"
625
" 'aaa' LeafNode\n"
626
" ('aaa',) 'val'\n"
627
" 'aab' LeafNode\n"
628
" ('aab',) 'val'\n"
629
" 'aac' LeafNode\n"
630
" ('aac',) 'val'\n",
631
chkmap._dump_tree())
632
root_key = chkmap._save()
633
# Save everything to the map, and start over
634
chkmap = CHKMap(store, root_key)
635
chkmap.map(('aad',), 'v')
636
# At this point, the previous nodes should not be paged in, but the
637
# newly added node would be
638
self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
639
self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
640
self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
641
self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
642
# Unmapping the new node will check the existing nodes to see if they
643
# would fit.
644
# Clear the page cache so we ensure we have to read all the children
645
chk_map._page_cache.clear()
646
chkmap.unmap(('aad',))
647
self.assertIsInstance(chkmap._root_node._items['aaa'], LeafNode)
648
self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
649
self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
650
651
def test_unmap_pages_in_from_page_cache(self):
652
store = self.get_chk_bytes()
653
chkmap = CHKMap(store, None)
654
# Should fit 2 keys per LeafNode
655
chkmap._root_node.set_maximum_size(30)
656
chkmap.map(('aaa',), 'val')
657
chkmap.map(('aab',), 'val')
658
chkmap.map(('aac',), 'val')
659
root_key = chkmap._save()
660
# Save everything to the map, and start over
661
chkmap = CHKMap(store, root_key)
662
chkmap.map(('aad',), 'val')
663
self.assertEqualDiff("'' InternalNode\n"
664
" 'aaa' LeafNode\n"
665
" ('aaa',) 'val'\n"
666
" 'aab' LeafNode\n"
667
" ('aab',) 'val'\n"
668
" 'aac' LeafNode\n"
669
" ('aac',) 'val'\n"
670
" 'aad' LeafNode\n"
671
" ('aad',) 'val'\n",
672
chkmap._dump_tree())
673
# Save everything to the map, start over after _dump_tree
674
chkmap = CHKMap(store, root_key)
675
chkmap.map(('aad',), 'v')
676
# At this point, the previous nodes should not be paged in, but the
677
# newly added node would be
678
self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
679
self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
680
self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
681
self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
682
# Now clear the page cache, and only include 2 of the children in the
683
# cache
684
aab_key = chkmap._root_node._items['aab']
685
aab_bytes = chk_map._page_cache[aab_key]
686
aac_key = chkmap._root_node._items['aac']
687
aac_bytes = chk_map._page_cache[aac_key]
688
chk_map._page_cache.clear()
689
chk_map._page_cache[aab_key] = aab_bytes
690
chk_map._page_cache[aac_key] = aac_bytes
691
692
# Unmapping the new node will check the nodes from the page cache
693
# first, and not have to read in 'aaa'
694
chkmap.unmap(('aad',))
695
self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
696
self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
697
self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
698
699
def test_unmap_uses_existing_items(self):
700
store = self.get_chk_bytes()
701
chkmap = CHKMap(store, None)
702
# Should fit 2 keys per LeafNode
703
chkmap._root_node.set_maximum_size(30)
704
chkmap.map(('aaa',), 'val')
705
chkmap.map(('aab',), 'val')
706
chkmap.map(('aac',), 'val')
707
root_key = chkmap._save()
708
# Save everything to the map, and start over
709
chkmap = CHKMap(store, root_key)
710
chkmap.map(('aad',), 'val')
711
chkmap.map(('aae',), 'val')
712
chkmap.map(('aaf',), 'val')
713
# At this point, the previous nodes should not be paged in, but the
714
# newly added node would be
715
self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
716
self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
717
self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
718
self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
719
self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
720
self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
721
722
# Unmapping a new node will see the other nodes that are already in
723
# memory, and not need to page in anything else
724
chkmap.unmap(('aad',))
725
self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
726
self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
727
self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
728
self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
729
self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
730
731
def test_iter_changes_empty_ab(self):
732
# Asking for changes between an empty dict to a dict with keys returns
733
# all the keys.
734
basis = self._get_map({}, maximum_size=10)
735
target = self._get_map(
736
{('a',): 'content here', ('b',): 'more content'},
737
chk_bytes=basis._store, maximum_size=10)
738
self.assertEqual([(('a',), None, 'content here'),
739
(('b',), None, 'more content')],
740
sorted(list(target.iter_changes(basis))))
741
742
def test_iter_changes_ab_empty(self):
743
# Asking for changes between a dict with keys to an empty dict returns
744
# all the keys.
745
basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
746
maximum_size=10)
747
target = self._get_map({}, chk_bytes=basis._store, maximum_size=10)
748
self.assertEqual([(('a',), 'content here', None),
749
(('b',), 'more content', None)],
750
sorted(list(target.iter_changes(basis))))
751
752
def test_iter_changes_empty_empty_is_empty(self):
753
basis = self._get_map({}, maximum_size=10)
754
target = self._get_map({}, chk_bytes=basis._store, maximum_size=10)
755
self.assertEqual([], sorted(list(target.iter_changes(basis))))
756
757
def test_iter_changes_ab_ab_is_empty(self):
758
basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
759
maximum_size=10)
760
target = self._get_map(
761
{('a',): 'content here', ('b',): 'more content'},
762
chk_bytes=basis._store, maximum_size=10)
763
self.assertEqual([], sorted(list(target.iter_changes(basis))))
764
765
def test_iter_changes_ab_ab_nodes_not_loaded(self):
766
basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
767
maximum_size=10)
768
target = self._get_map(
769
{('a',): 'content here', ('b',): 'more content'},
770
chk_bytes=basis._store, maximum_size=10)
771
list(target.iter_changes(basis))
772
self.assertIsInstance(target._root_node, tuple)
773
self.assertIsInstance(basis._root_node, tuple)
774
775
def test_iter_changes_ab_ab_changed_values_shown(self):
776
basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
777
maximum_size=10)
778
target = self._get_map(
779
{('a',): 'content here', ('b',): 'different content'},
780
chk_bytes=basis._store, maximum_size=10)
781
result = sorted(list(target.iter_changes(basis)))
782
self.assertEqual([(('b',), 'more content', 'different content')],
783
result)
784
785
def test_iter_changes_mixed_node_length(self):
786
# When one side has different node lengths than the other, common
787
# but different keys still need to be show, and new-and-old included
788
# appropriately.
789
# aaa - common unaltered
790
# aab - common altered
791
# b - basis only
792
# at - target only
793
# we expect:
794
# aaa to be not loaded (later test)
795
# aab, b, at to be returned.
796
# basis splits at byte 0,1,2, aaa is commonb is basis only
797
basis_dict = {('aaa',): 'foo bar',
798
('aab',): 'common altered a', ('b',): 'foo bar b'}
799
# target splits at byte 1,2, at is target only
800
target_dict = {('aaa',): 'foo bar',
801
('aab',): 'common altered b', ('at',): 'foo bar t'}
802
changes = [
803
(('aab',), 'common altered a', 'common altered b'),
804
(('at',), None, 'foo bar t'),
805
(('b',), 'foo bar b', None),
806
]
807
basis = self._get_map(basis_dict, maximum_size=10)
808
target = self._get_map(target_dict, maximum_size=10,
809
chk_bytes=basis._store)
810
self.assertEqual(changes, sorted(list(target.iter_changes(basis))))
811
812
def test_iter_changes_common_pages_not_loaded(self):
813
# aaa - common unaltered
814
# aab - common altered
815
# b - basis only
816
# at - target only
817
# we expect:
818
# aaa to be not loaded
819
# aaa not to be in result.
820
basis_dict = {('aaa',): 'foo bar',
821
('aab',): 'common altered a', ('b',): 'foo bar b'}
822
# target splits at byte 1, at is target only
823
target_dict = {('aaa',): 'foo bar',
824
('aab',): 'common altered b', ('at',): 'foo bar t'}
825
basis = self._get_map(basis_dict, maximum_size=10)
826
target = self._get_map(target_dict, maximum_size=10,
827
chk_bytes=basis._store)
828
basis_get = basis._store.get_record_stream
829
def get_record_stream(keys, order, fulltext):
830
if ('sha1:1adf7c0d1b9140ab5f33bb64c6275fa78b1580b7',) in keys:
831
self.fail("'aaa' pointer was followed %r" % keys)
832
return basis_get(keys, order, fulltext)
833
basis._store.get_record_stream = get_record_stream
834
result = sorted(list(target.iter_changes(basis)))
835
for change in result:
836
if change[0] == ('aaa',):
837
self.fail("Found unexpected change: %s" % change)
838
839
def test_iter_changes_unchanged_keys_in_multi_key_leafs_ignored(self):
840
# Within a leaf there are no hash's to exclude keys, make sure multi
841
# value leaf nodes are handled well.
842
basis_dict = {('aaa',): 'foo bar',
843
('aab',): 'common altered a', ('b',): 'foo bar b'}
844
target_dict = {('aaa',): 'foo bar',
845
('aab',): 'common altered b', ('at',): 'foo bar t'}
846
changes = [
847
(('aab',), 'common altered a', 'common altered b'),
848
(('at',), None, 'foo bar t'),
849
(('b',), 'foo bar b', None),
850
]
851
basis = self._get_map(basis_dict)
852
target = self._get_map(target_dict, chk_bytes=basis._store)
853
self.assertEqual(changes, sorted(list(target.iter_changes(basis))))
854
855
def test_iteritems_empty(self):
856
chk_bytes = self.get_chk_bytes()
857
root_key = CHKMap.from_dict(chk_bytes, {})
858
chkmap = CHKMap(chk_bytes, root_key)
859
self.assertEqual([], list(chkmap.iteritems()))
860
861
def test_iteritems_two_items(self):
862
chk_bytes = self.get_chk_bytes()
863
root_key = CHKMap.from_dict(chk_bytes,
864
{"a":"content here", "b":"more content"})
865
chkmap = CHKMap(chk_bytes, root_key)
866
self.assertEqual([(("a",), "content here"), (("b",), "more content")],
867
sorted(list(chkmap.iteritems())))
868
869
def test_iteritems_selected_one_of_two_items(self):
870
chkmap = self._get_map( {("a",):"content here", ("b",):"more content"})
871
self.assertEqual({("a",): "content here"},
872
self.to_dict(chkmap, [("a",)]))
873
874
def test_iteritems_keys_prefixed_by_2_width_nodes(self):
875
chkmap = self._get_map(
876
{("a","a"):"content here", ("a", "b",):"more content",
877
("b", ""): 'boring content'},
878
maximum_size=10, key_width=2)
879
self.assertEqual(
880
{("a", "a"): "content here", ("a", "b"): 'more content'},
881
self.to_dict(chkmap, [("a",)]))
882
883
def test_iteritems_keys_prefixed_by_2_width_nodes_hashed(self):
884
search_key_func = chk_map.search_key_registry.get('hash-16-way')
885
self.assertEqual('E8B7BE43\x00E8B7BE43', search_key_func(('a', 'a')))
886
self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
887
self.assertEqual('71BEEFF9\x0000000000', search_key_func(('b', '')))
888
chkmap = self._get_map(
889
{("a","a"):"content here", ("a", "b",):"more content",
890
("b", ""): 'boring content'},
891
maximum_size=10, key_width=2, search_key_func=search_key_func)
892
self.assertEqual(
893
{("a", "a"): "content here", ("a", "b"): 'more content'},
894
self.to_dict(chkmap, [("a",)]))
895
896
def test_iteritems_keys_prefixed_by_2_width_one_leaf(self):
897
chkmap = self._get_map(
898
{("a","a"):"content here", ("a", "b",):"more content",
899
("b", ""): 'boring content'}, key_width=2)
900
self.assertEqual(
901
{("a", "a"): "content here", ("a", "b"): 'more content'},
902
self.to_dict(chkmap, [("a",)]))
903
904
def test___len__empty(self):
905
chkmap = self._get_map({})
906
self.assertEqual(0, len(chkmap))
907
908
def test___len__2(self):
909
chkmap = self._get_map({("foo",):"bar", ("gam",):"quux"})
910
self.assertEqual(2, len(chkmap))
911
912
def test_max_size_100_bytes_new(self):
913
# When there is a 100 byte upper node limit, a tree is formed.
914
chkmap = self._get_map({("k1"*50,):"v1", ("k2"*50,):"v2"}, maximum_size=100)
915
# We expect three nodes:
916
# A root, with two children, and with two key prefixes - k1 to one, and
917
# k2 to the other as our node splitting is only just being developed.
918
# The maximum size should be embedded
919
chkmap._ensure_root()
920
self.assertEqual(100, chkmap._root_node.maximum_size)
921
self.assertEqual(1, chkmap._root_node._key_width)
922
# There should be two child nodes, and prefix of 2(bytes):
923
self.assertEqual(2, len(chkmap._root_node._items))
924
self.assertEqual("k", chkmap._root_node._compute_search_prefix())
925
# The actual nodes pointed at will change as serialisers change; so
926
# here we test that the key prefix is correct; then load the nodes and
927
# check they have the right pointed at key; whether they have the
928
# pointed at value inline or not is also unrelated to this test so we
929
# don't check that in detail - rather we just check the aggregate
930
# value.
931
nodes = sorted(chkmap._root_node._items.items())
932
ptr1 = nodes[0]
933
ptr2 = nodes[1]
934
self.assertEqual('k1', ptr1[0])
935
self.assertEqual('k2', ptr2[0])
936
node1 = chk_map._deserialise(chkmap._read_bytes(ptr1[1]), ptr1[1], None)
937
self.assertIsInstance(node1, LeafNode)
938
self.assertEqual(1, len(node1))
939
self.assertEqual({('k1'*50,): 'v1'}, self.to_dict(node1, chkmap._store))
940
node2 = chk_map._deserialise(chkmap._read_bytes(ptr2[1]), ptr2[1], None)
941
self.assertIsInstance(node2, LeafNode)
942
self.assertEqual(1, len(node2))
943
self.assertEqual({('k2'*50,): 'v2'}, self.to_dict(node2, chkmap._store))
944
# Having checked we have a good structure, check that the content is
945
# still accessible.
946
self.assertEqual(2, len(chkmap))
947
self.assertEqual({("k1"*50,): "v1", ("k2"*50,): "v2"},
948
self.to_dict(chkmap))
949
950
def test_init_root_is_LeafNode_new(self):
951
chk_bytes = self.get_chk_bytes()
952
chkmap = CHKMap(chk_bytes, None)
953
self.assertIsInstance(chkmap._root_node, LeafNode)
954
self.assertEqual({}, self.to_dict(chkmap))
955
self.assertEqual(0, len(chkmap))
956
957
def test_init_and_save_new(self):
958
chk_bytes = self.get_chk_bytes()
959
chkmap = CHKMap(chk_bytes, None)
960
key = chkmap._save()
961
leaf_node = LeafNode()
962
self.assertEqual([key], leaf_node.serialise(chk_bytes))
963
964
def test_map_first_item_new(self):
965
chk_bytes = self.get_chk_bytes()
966
chkmap = CHKMap(chk_bytes, None)
967
chkmap.map(("foo,",), "bar")
968
self.assertEqual({('foo,',): 'bar'}, self.to_dict(chkmap))
969
self.assertEqual(1, len(chkmap))
970
key = chkmap._save()
971
leaf_node = LeafNode()
972
leaf_node.map(chk_bytes, ("foo,",), "bar")
973
self.assertEqual([key], leaf_node.serialise(chk_bytes))
974
975
def test_unmap_last_item_root_is_leaf_new(self):
976
chkmap = self._get_map({("k1"*50,): "v1", ("k2"*50,): "v2"})
977
chkmap.unmap(("k1"*50,))
978
chkmap.unmap(("k2"*50,))
979
self.assertEqual(0, len(chkmap))
980
self.assertEqual({}, self.to_dict(chkmap))
981
key = chkmap._save()
982
leaf_node = LeafNode()
983
self.assertEqual([key], leaf_node.serialise(chkmap._store))
984
985
def test__dump_tree(self):
986
chkmap = self._get_map({("aaa",): "value1", ("aab",): "value2",
987
("bbb",): "value3",},
988
maximum_size=15)
989
self.assertEqualDiff("'' InternalNode\n"
990
" 'a' InternalNode\n"
991
" 'aaa' LeafNode\n"
992
" ('aaa',) 'value1'\n"
993
" 'aab' LeafNode\n"
994
" ('aab',) 'value2'\n"
995
" 'b' LeafNode\n"
996
" ('bbb',) 'value3'\n",
997
chkmap._dump_tree())
998
self.assertEqualDiff("'' InternalNode\n"
999
" 'a' InternalNode\n"
1000
" 'aaa' LeafNode\n"
1001
" ('aaa',) 'value1'\n"
1002
" 'aab' LeafNode\n"
1003
" ('aab',) 'value2'\n"
1004
" 'b' LeafNode\n"
1005
" ('bbb',) 'value3'\n",
1006
chkmap._dump_tree())
1007
self.assertEqualDiff(
1008
"'' InternalNode sha1:0690d471eb0a624f359797d0ee4672bd68f4e236\n"
1009
" 'a' InternalNode sha1:1514c35503da9418d8fd90c1bed553077cb53673\n"
1010
" 'aaa' LeafNode sha1:4cc5970454d40b4ce297a7f13ddb76f63b88fefb\n"
1011
" ('aaa',) 'value1'\n"
1012
" 'aab' LeafNode sha1:1d68bc90914ef8a3edbcc8bb28b00cb4fea4b5e2\n"
1013
" ('aab',) 'value2'\n"
1014
" 'b' LeafNode sha1:3686831435b5596515353364eab0399dc45d49e7\n"
1015
" ('bbb',) 'value3'\n",
1016
chkmap._dump_tree(include_keys=True))
1017
1018
def test__dump_tree_in_progress(self):
1019
chkmap = self._get_map({("aaa",): "value1", ("aab",): "value2"},
1020
maximum_size=10)
1021
chkmap.map(('bbb',), 'value3')
1022
self.assertEqualDiff("'' InternalNode\n"
1023
" 'a' InternalNode\n"
1024
" 'aaa' LeafNode\n"
1025
" ('aaa',) 'value1'\n"
1026
" 'aab' LeafNode\n"
1027
" ('aab',) 'value2'\n"
1028
" 'b' LeafNode\n"
1029
" ('bbb',) 'value3'\n",
1030
chkmap._dump_tree())
1031
# For things that are updated by adding 'bbb', we don't have a sha key
1032
# for them yet, so they are listed as None
1033
self.assertEqualDiff(
1034
"'' InternalNode None\n"
1035
" 'a' InternalNode sha1:6b0d881dd739a66f733c178b24da64395edfaafd\n"
1036
" 'aaa' LeafNode sha1:40b39a08d895babce17b20ae5f62d187eaa4f63a\n"
1037
" ('aaa',) 'value1'\n"
1038
" 'aab' LeafNode sha1:ad1dc7c4e801302c95bf1ba7b20bc45e548cd51a\n"
1039
" ('aab',) 'value2'\n"
1040
" 'b' LeafNode None\n"
1041
" ('bbb',) 'value3'\n",
1042
chkmap._dump_tree(include_keys=True))
1043
1044
1045
def _search_key_single(key):
1046
"""A search key function that maps all nodes to the same value"""
1047
return 'value'
1048
1049
def _test_search_key(key):
1050
return 'test:' + '\x00'.join(key)
1051
1052
1053
class TestMapSearchKeys(TestCaseWithStore):
1054
1055
def test_default_chk_map_uses_flat_search_key(self):
1056
chkmap = chk_map.CHKMap(self.get_chk_bytes(), None)
1057
self.assertEqual('1',
1058
chkmap._search_key_func(('1',)))
1059
self.assertEqual('1\x002',
1060
chkmap._search_key_func(('1', '2')))
1061
self.assertEqual('1\x002\x003',
1062
chkmap._search_key_func(('1', '2', '3')))
1063
1064
def test_search_key_is_passed_to_root_node(self):
1065
chkmap = chk_map.CHKMap(self.get_chk_bytes(), None,
1066
search_key_func=_test_search_key)
1067
self.assertIs(_test_search_key, chkmap._search_key_func)
1068
self.assertEqual('test:1\x002\x003',
1069
chkmap._search_key_func(('1', '2', '3')))
1070
self.assertEqual('test:1\x002\x003',
1071
chkmap._root_node._search_key(('1', '2', '3')))
1072
1073
def test_search_key_passed_via__ensure_root(self):
1074
chk_bytes = self.get_chk_bytes()
1075
chkmap = chk_map.CHKMap(chk_bytes, None,
1076
search_key_func=_test_search_key)
1077
root_key = chkmap._save()
1078
chkmap = chk_map.CHKMap(chk_bytes, root_key,
1079
search_key_func=_test_search_key)
1080
chkmap._ensure_root()
1081
self.assertEqual('test:1\x002\x003',
1082
chkmap._root_node._search_key(('1', '2', '3')))
1083
1084
def test_search_key_with_internal_node(self):
1085
chk_bytes = self.get_chk_bytes()
1086
chkmap = chk_map.CHKMap(chk_bytes, None,
1087
search_key_func=_test_search_key)
1088
chkmap._root_node.set_maximum_size(10)
1089
chkmap.map(('1',), 'foo')
1090
chkmap.map(('2',), 'bar')
1091
chkmap.map(('3',), 'baz')
1092
self.assertEqualDiff("'' InternalNode\n"
1093
" 'test:1' LeafNode\n"
1094
" ('1',) 'foo'\n"
1095
" 'test:2' LeafNode\n"
1096
" ('2',) 'bar'\n"
1097
" 'test:3' LeafNode\n"
1098
" ('3',) 'baz'\n"
1099
, chkmap._dump_tree())
1100
root_key = chkmap._save()
1101
chkmap = chk_map.CHKMap(chk_bytes, root_key,
1102
search_key_func=_test_search_key)
1103
self.assertEqualDiff("'' InternalNode\n"
1104
" 'test:1' LeafNode\n"
1105
" ('1',) 'foo'\n"
1106
" 'test:2' LeafNode\n"
1107
" ('2',) 'bar'\n"
1108
" 'test:3' LeafNode\n"
1109
" ('3',) 'baz'\n"
1110
, chkmap._dump_tree())
1111
1112
def test_search_key_16(self):
1113
chk_bytes = self.get_chk_bytes()
1114
chkmap = chk_map.CHKMap(chk_bytes, None,
1115
search_key_func=chk_map._search_key_16)
1116
chkmap._root_node.set_maximum_size(10)
1117
chkmap.map(('1',), 'foo')
1118
chkmap.map(('2',), 'bar')
1119
chkmap.map(('3',), 'baz')
1120
self.assertEqualDiff("'' InternalNode\n"
1121
" '1' LeafNode\n"
1122
" ('2',) 'bar'\n"
1123
" '6' LeafNode\n"
1124
" ('3',) 'baz'\n"
1125
" '8' LeafNode\n"
1126
" ('1',) 'foo'\n"
1127
, chkmap._dump_tree())
1128
root_key = chkmap._save()
1129
chkmap = chk_map.CHKMap(chk_bytes, root_key,
1130
search_key_func=chk_map._search_key_16)
1131
# We can get the values back correctly
1132
self.assertEqual([(('1',), 'foo')],
1133
list(chkmap.iteritems([('1',)])))
1134
self.assertEqualDiff("'' InternalNode\n"
1135
" '1' LeafNode\n"
1136
" ('2',) 'bar'\n"
1137
" '6' LeafNode\n"
1138
" ('3',) 'baz'\n"
1139
" '8' LeafNode\n"
1140
" ('1',) 'foo'\n"
1141
, chkmap._dump_tree())
1142
1143
def test_search_key_255(self):
1144
chk_bytes = self.get_chk_bytes()
1145
chkmap = chk_map.CHKMap(chk_bytes, None,
1146
search_key_func=chk_map._search_key_255)
1147
chkmap._root_node.set_maximum_size(10)
1148
chkmap.map(('1',), 'foo')
1149
chkmap.map(('2',), 'bar')
1150
chkmap.map(('3',), 'baz')
1151
self.assertEqualDiff("'' InternalNode\n"
1152
" '\\x1a' LeafNode\n"
1153
" ('2',) 'bar'\n"
1154
" 'm' LeafNode\n"
1155
" ('3',) 'baz'\n"
1156
" '\\x83' LeafNode\n"
1157
" ('1',) 'foo'\n"
1158
, chkmap._dump_tree())
1159
root_key = chkmap._save()
1160
chkmap = chk_map.CHKMap(chk_bytes, root_key,
1161
search_key_func=chk_map._search_key_255)
1162
# We can get the values back correctly
1163
self.assertEqual([(('1',), 'foo')],
1164
list(chkmap.iteritems([('1',)])))
1165
self.assertEqualDiff("'' InternalNode\n"
1166
" '\\x1a' LeafNode\n"
1167
" ('2',) 'bar'\n"
1168
" 'm' LeafNode\n"
1169
" ('3',) 'baz'\n"
1170
" '\\x83' LeafNode\n"
1171
" ('1',) 'foo'\n"
1172
, chkmap._dump_tree())
1173
1174
def test_search_key_collisions(self):
1175
chkmap = chk_map.CHKMap(self.get_chk_bytes(), None,
1176
search_key_func=_search_key_single)
1177
# The node will want to expand, but it cannot, because it knows that
1178
# all the keys must map to this node
1179
chkmap._root_node.set_maximum_size(20)
1180
chkmap.map(('1',), 'foo')
1181
chkmap.map(('2',), 'bar')
1182
chkmap.map(('3',), 'baz')
1183
self.assertEqualDiff("'' LeafNode\n"
1184
" ('1',) 'foo'\n"
1185
" ('2',) 'bar'\n"
1186
" ('3',) 'baz'\n"
1187
, chkmap._dump_tree())
1188
1189
1190
class TestSearchKeyFuncs(tests.TestCase):
1191
1192
def assertSearchKey16(self, expected, key):
1193
self.assertEqual(expected, chk_map._search_key_16(key))
1194
1195
def assertSearchKey255(self, expected, key):
1196
actual = chk_map._search_key_255(key)
1197
self.assertEqual(expected, actual, 'actual: %r' % (actual,))
1198
1199
def test_simple_16(self):
1200
self.assertSearchKey16('8C736521', ('foo',))
1201
self.assertSearchKey16('8C736521\x008C736521', ('foo', 'foo'))
1202
self.assertSearchKey16('8C736521\x0076FF8CAA', ('foo', 'bar'))
1203
self.assertSearchKey16('ED82CD11', ('abcd',))
1204
1205
def test_simple_255(self):
1206
self.assertSearchKey255('\x8cse!', ('foo',))
1207
self.assertSearchKey255('\x8cse!\x00\x8cse!', ('foo', 'foo'))
1208
self.assertSearchKey255('\x8cse!\x00v\xff\x8c\xaa', ('foo', 'bar'))
1209
# The standard mapping for these would include '\n', so it should be
1210
# mapped to '_'
1211
self.assertSearchKey255('\xfdm\x93_\x00P_\x1bL', ('<', 'V'))
1212
1213
def test_255_does_not_include_newline(self):
1214
# When mapping via _search_key_255, we should never have the '\n'
1215
# character, but all other 255 values should be present
1216
chars_used = set()
1217
for char_in in range(256):
1218
search_key = chk_map._search_key_255((chr(char_in),))
1219
chars_used.update(search_key)
1220
all_chars = set([chr(x) for x in range(256)])
1221
unused_chars = all_chars.symmetric_difference(chars_used)
1222
self.assertEqual(set('\n'), unused_chars)
1223
1224
1225
class TestLeafNode(TestCaseWithStore):
1226
1227
def test_current_size_empty(self):
1228
node = LeafNode()
1229
self.assertEqual(16, node._current_size())
1230
1231
def test_current_size_size_changed(self):
1232
node = LeafNode()
1233
node.set_maximum_size(10)
1234
self.assertEqual(17, node._current_size())
1235
1236
def test_current_size_width_changed(self):
1237
node = LeafNode()
1238
node._key_width = 10
1239
self.assertEqual(17, node._current_size())
1240
1241
def test_current_size_items(self):
1242
node = LeafNode()
1243
base_size = node._current_size()
1244
node.map(None, ("foo bar",), "baz")
1245
self.assertEqual(base_size + 14, node._current_size())
1246
1247
def test_deserialise_empty(self):
1248
node = LeafNode.deserialise("chkleaf:\n10\n1\n0\n\n", ("sha1:1234",))
1249
self.assertEqual(0, len(node))
1250
self.assertEqual(10, node.maximum_size)
1251
self.assertEqual(("sha1:1234",), node.key())
1252
self.assertIs(None, node._search_prefix)
1253
self.assertIs(None, node._common_serialised_prefix)
1254
1255
def test_deserialise_items(self):
1256
node = LeafNode.deserialise(
1257
"chkleaf:\n0\n1\n2\n\nfoo bar\x001\nbaz\nquux\x001\nblarh\n",
1258
("sha1:1234",))
1259
self.assertEqual(2, len(node))
1260
self.assertEqual([(("foo bar",), "baz"), (("quux",), "blarh")],
1261
sorted(node.iteritems(None)))
1262
1263
def test_deserialise_item_with_null_width_1(self):
1264
node = LeafNode.deserialise(
1265
"chkleaf:\n0\n1\n2\n\nfoo\x001\nbar\x00baz\nquux\x001\nblarh\n",
1266
("sha1:1234",))
1267
self.assertEqual(2, len(node))
1268
self.assertEqual([(("foo",), "bar\x00baz"), (("quux",), "blarh")],
1269
sorted(node.iteritems(None)))
1270
1271
def test_deserialise_item_with_null_width_2(self):
1272
node = LeafNode.deserialise(
1273
"chkleaf:\n0\n2\n2\n\nfoo\x001\x001\nbar\x00baz\n"
1274
"quux\x00\x001\nblarh\n",
1275
("sha1:1234",))
1276
self.assertEqual(2, len(node))
1277
self.assertEqual([(("foo", "1"), "bar\x00baz"), (("quux", ""), "blarh")],
1278
sorted(node.iteritems(None)))
1279
1280
def test_iteritems_selected_one_of_two_items(self):
1281
node = LeafNode.deserialise(
1282
"chkleaf:\n0\n1\n2\n\nfoo bar\x001\nbaz\nquux\x001\nblarh\n",
1283
("sha1:1234",))
1284
self.assertEqual(2, len(node))
1285
self.assertEqual([(("quux",), "blarh")],
1286
sorted(node.iteritems(None, [("quux",), ("qaz",)])))
1287
1288
def test_deserialise_item_with_common_prefix(self):
1289
node = LeafNode.deserialise(
1290
"chkleaf:\n0\n2\n2\nfoo\x00\n1\x001\nbar\x00baz\n2\x001\nblarh\n",
1291
("sha1:1234",))
1292
self.assertEqual(2, len(node))
1293
self.assertEqual([(("foo", "1"), "bar\x00baz"), (("foo", "2"), "blarh")],
1294
sorted(node.iteritems(None)))
1295
self.assertIs(chk_map._unknown, node._search_prefix)
1296
self.assertEqual('foo\x00', node._common_serialised_prefix)
1297
1298
def test_deserialise_multi_line(self):
1299
node = LeafNode.deserialise(
1300
"chkleaf:\n0\n2\n2\nfoo\x00\n1\x002\nbar\nbaz\n2\x002\nblarh\n\n",
1301
("sha1:1234",))
1302
self.assertEqual(2, len(node))
1303
self.assertEqual([(("foo", "1"), "bar\nbaz"),
1304
(("foo", "2"), "blarh\n"),
1305
], sorted(node.iteritems(None)))
1306
self.assertIs(chk_map._unknown, node._search_prefix)
1307
self.assertEqual('foo\x00', node._common_serialised_prefix)
1308
1309
def test_key_new(self):
1310
node = LeafNode()
1311
self.assertEqual(None, node.key())
1312
1313
def test_key_after_map(self):
1314
node = LeafNode.deserialise("chkleaf:\n10\n1\n0\n\n", ("sha1:1234",))
1315
node.map(None, ("foo bar",), "baz quux")
1316
self.assertEqual(None, node.key())
1317
1318
def test_key_after_unmap(self):
1319
node = LeafNode.deserialise(
1320
"chkleaf:\n0\n1\n2\n\nfoo bar\x001\nbaz\nquux\x001\nblarh\n",
1321
("sha1:1234",))
1322
node.unmap(None, ("foo bar",))
1323
self.assertEqual(None, node.key())
1324
1325
def test_map_exceeding_max_size_only_entry_new(self):
1326
node = LeafNode()
1327
node.set_maximum_size(10)
1328
result = node.map(None, ("foo bar",), "baz quux")
1329
self.assertEqual(("foo bar", [("", node)]), result)
1330
self.assertTrue(10 < node._current_size())
1331
1332
def test_map_exceeding_max_size_second_entry_early_difference_new(self):
1333
node = LeafNode()
1334
node.set_maximum_size(10)
1335
node.map(None, ("foo bar",), "baz quux")
1336
prefix, result = list(node.map(None, ("blue",), "red"))
1337
self.assertEqual("", prefix)
1338
self.assertEqual(2, len(result))
1339
split_chars = set([result[0][0], result[1][0]])
1340
self.assertEqual(set(["f", "b"]), split_chars)
1341
nodes = dict(result)
1342
node = nodes["f"]
1343
self.assertEqual({("foo bar",): "baz quux"}, self.to_dict(node, None))
1344
self.assertEqual(10, node.maximum_size)
1345
self.assertEqual(1, node._key_width)
1346
node = nodes["b"]
1347
self.assertEqual({("blue",): "red"}, self.to_dict(node, None))
1348
self.assertEqual(10, node.maximum_size)
1349
self.assertEqual(1, node._key_width)
1350
1351
def test_map_first(self):
1352
node = LeafNode()
1353
result = node.map(None, ("foo bar",), "baz quux")
1354
self.assertEqual(("foo bar", [("", node)]), result)
1355
self.assertEqual({("foo bar",):"baz quux"}, self.to_dict(node, None))
1356
self.assertEqual(1, len(node))
1357
1358
def test_map_second(self):
1359
node = LeafNode()
1360
node.map(None, ("foo bar",), "baz quux")
1361
result = node.map(None, ("bingo",), "bango")
1362
self.assertEqual(("", [("", node)]), result)
1363
self.assertEqual({("foo bar",):"baz quux", ("bingo",):"bango"},
1364
self.to_dict(node, None))
1365
self.assertEqual(2, len(node))
1366
1367
def test_map_replacement(self):
1368
node = LeafNode()
1369
node.map(None, ("foo bar",), "baz quux")
1370
result = node.map(None, ("foo bar",), "bango")
1371
self.assertEqual(("foo bar", [("", node)]), result)
1372
self.assertEqual({("foo bar",): "bango"},
1373
self.to_dict(node, None))
1374
self.assertEqual(1, len(node))
1375
1376
def test_serialise_empty(self):
1377
store = self.get_chk_bytes()
1378
node = LeafNode()
1379
node.set_maximum_size(10)
1380
expected_key = ("sha1:f34c3f0634ea3f85953dffa887620c0a5b1f4a51",)
1381
self.assertEqual([expected_key],
1382
list(node.serialise(store)))
1383
self.assertEqual("chkleaf:\n10\n1\n0\n\n", self.read_bytes(store, expected_key))
1384
self.assertEqual(expected_key, node.key())
1385
1386
def test_serialise_items(self):
1387
store = self.get_chk_bytes()
1388
node = LeafNode()
1389
node.set_maximum_size(10)
1390
node.map(None, ("foo bar",), "baz quux")
1391
expected_key = ("sha1:f89fac7edfc6bdb1b1b54a556012ff0c646ef5e0",)
1392
self.assertEqual('foo bar', node._common_serialised_prefix)
1393
self.assertEqual([expected_key],
1394
list(node.serialise(store)))
1395
self.assertEqual("chkleaf:\n10\n1\n1\nfoo bar\n\x001\nbaz quux\n",
1396
self.read_bytes(store, expected_key))
1397
self.assertEqual(expected_key, node.key())
1398
1399
def test_unique_serialised_prefix_empty_new(self):
1400
node = LeafNode()
1401
self.assertIs(None, node._compute_search_prefix())
1402
1403
def test_unique_serialised_prefix_one_item_new(self):
1404
node = LeafNode()
1405
node.map(None, ("foo bar", "baz"), "baz quux")
1406
self.assertEqual("foo bar\x00baz", node._compute_search_prefix())
1407
1408
def test_unmap_missing(self):
1409
node = LeafNode()
1410
self.assertRaises(KeyError, node.unmap, None, ("foo bar",))
1411
1412
def test_unmap_present(self):
1413
node = LeafNode()
1414
node.map(None, ("foo bar",), "baz quux")
1415
result = node.unmap(None, ("foo bar",))
1416
self.assertEqual(node, result)
1417
self.assertEqual({}, self.to_dict(node, None))
1418
self.assertEqual(0, len(node))
1419
1420
def test_map_maintains_common_prefixes(self):
1421
node = LeafNode()
1422
node._key_width = 2
1423
node.map(None, ("foo bar", "baz"), "baz quux")
1424
self.assertEqual('foo bar\x00baz', node._search_prefix)
1425
self.assertEqual('foo bar\x00baz', node._common_serialised_prefix)
1426
node.map(None, ("foo bar", "bing"), "baz quux")
1427
self.assertEqual('foo bar\x00b', node._search_prefix)
1428
self.assertEqual('foo bar\x00b', node._common_serialised_prefix)
1429
node.map(None, ("fool", "baby"), "baz quux")
1430
self.assertEqual('foo', node._search_prefix)
1431
self.assertEqual('foo', node._common_serialised_prefix)
1432
node.map(None, ("foo bar", "baz"), "replaced")
1433
self.assertEqual('foo', node._search_prefix)
1434
self.assertEqual('foo', node._common_serialised_prefix)
1435
node.map(None, ("very", "different"), "value")
1436
self.assertEqual('', node._search_prefix)
1437
self.assertEqual('', node._common_serialised_prefix)
1438
1439
def test_unmap_maintains_common_prefixes(self):
1440
node = LeafNode()
1441
node._key_width = 2
1442
node.map(None, ("foo bar", "baz"), "baz quux")
1443
node.map(None, ("foo bar", "bing"), "baz quux")
1444
node.map(None, ("fool", "baby"), "baz quux")
1445
node.map(None, ("very", "different"), "value")
1446
self.assertEqual('', node._search_prefix)
1447
self.assertEqual('', node._common_serialised_prefix)
1448
node.unmap(None, ("very", "different"))
1449
self.assertEqual("foo", node._search_prefix)
1450
self.assertEqual("foo", node._common_serialised_prefix)
1451
node.unmap(None, ("fool", "baby"))
1452
self.assertEqual('foo bar\x00b', node._search_prefix)
1453
self.assertEqual('foo bar\x00b', node._common_serialised_prefix)
1454
node.unmap(None, ("foo bar", "baz"))
1455
self.assertEqual('foo bar\x00bing', node._search_prefix)
1456
self.assertEqual('foo bar\x00bing', node._common_serialised_prefix)
1457
node.unmap(None, ("foo bar", "bing"))
1458
self.assertEqual(None, node._search_prefix)
1459
self.assertEqual(None, node._common_serialised_prefix)
1460
1461
1462
class TestInternalNode(TestCaseWithStore):
1463
1464
def test_add_node_empty_new(self):
1465
node = InternalNode('fo')
1466
child = LeafNode()
1467
child.set_maximum_size(100)
1468
child.map(None, ("foo",), "bar")
1469
node.add_node("foo", child)
1470
# Note that node isn't strictly valid now as a tree (only one child),
1471
# but thats ok for this test.
1472
# The first child defines the node's width:
1473
self.assertEqual(3, node._node_width)
1474
# We should be able to iterate over the contents without doing IO.
1475
self.assertEqual({('foo',): 'bar'}, self.to_dict(node, None))
1476
# The length should be known:
1477
self.assertEqual(1, len(node))
1478
# serialising the node should serialise the child and the node.
1479
chk_bytes = self.get_chk_bytes()
1480
keys = list(node.serialise(chk_bytes))
1481
child_key = child.serialise(chk_bytes)[0]
1482
self.assertEqual(
1483
[child_key, ('sha1:cf67e9997d8228a907c1f5bfb25a8bd9cd916fac',)],
1484
keys)
1485
# We should be able to access deserialised content.
1486
bytes = self.read_bytes(chk_bytes, keys[1])
1487
node = chk_map._deserialise(bytes, keys[1], None)
1488
self.assertEqual(1, len(node))
1489
self.assertEqual({('foo',): 'bar'}, self.to_dict(node, chk_bytes))
1490
self.assertEqual(3, node._node_width)
1491
1492
def test_add_node_resets_key_new(self):
1493
node = InternalNode('fo')
1494
child = LeafNode()
1495
child.set_maximum_size(100)
1496
child.map(None, ("foo",), "bar")
1497
node.add_node("foo", child)
1498
chk_bytes = self.get_chk_bytes()
1499
keys = list(node.serialise(chk_bytes))
1500
self.assertEqual(keys[1], node._key)
1501
node.add_node("fos", child)
1502
self.assertEqual(None, node._key)
1503
1504
# def test_add_node_empty_oversized_one_ok_new(self):
1505
# def test_add_node_one_oversized_second_kept_minimum_fan(self):
1506
# def test_add_node_two_oversized_third_kept_minimum_fan(self):
1507
# def test_add_node_one_oversized_second_splits_errors(self):
1508
1509
def test_iteritems_empty_new(self):
1510
node = InternalNode()
1511
self.assertEqual([], sorted(node.iteritems(None)))
1512
1513
def test_iteritems_two_children(self):
1514
node = InternalNode()
1515
leaf1 = LeafNode()
1516
leaf1.map(None, ('foo bar',), 'quux')
1517
leaf2 = LeafNode()
1518
leaf2.map(None, ('strange',), 'beast')
1519
node.add_node("f", leaf1)
1520
node.add_node("s", leaf2)
1521
self.assertEqual([(('foo bar',), 'quux'), (('strange',), 'beast')],
1522
sorted(node.iteritems(None)))
1523
1524
def test_iteritems_two_children_partial(self):
1525
node = InternalNode()
1526
leaf1 = LeafNode()
1527
leaf1.map(None, ('foo bar',), 'quux')
1528
leaf2 = LeafNode()
1529
leaf2.map(None, ('strange',), 'beast')
1530
node.add_node("f", leaf1)
1531
# This sets up a path that should not be followed - it will error if
1532
# the code tries to.
1533
node._items['f'] = None
1534
node.add_node("s", leaf2)
1535
self.assertEqual([(('strange',), 'beast')],
1536
sorted(node.iteritems(None, [('strange',), ('weird',)])))
1537
1538
def test_iteritems_two_children_with_hash(self):
1539
search_key_func = chk_map.search_key_registry.get('hash-255-way')
1540
node = InternalNode(search_key_func=search_key_func)
1541
leaf1 = LeafNode(search_key_func=search_key_func)
1542
leaf1.map(None, ('foo bar',), 'quux')
1543
leaf2 = LeafNode(search_key_func=search_key_func)
1544
leaf2.map(None, ('strange',), 'beast')
1545
self.assertEqual('\xbeF\x014', search_key_func(('foo bar',)))
1546
self.assertEqual('\x85\xfa\xf7K', search_key_func(('strange',)))
1547
node.add_node("\xbe", leaf1)
1548
# This sets up a path that should not be followed - it will error if
1549
# the code tries to.
1550
node._items['\xbe'] = None
1551
node.add_node("\x85", leaf2)
1552
self.assertEqual([(('strange',), 'beast')],
1553
sorted(node.iteritems(None, [('strange',), ('weird',)])))
1554
1555
def test_iteritems_partial_empty(self):
1556
node = InternalNode()
1557
self.assertEqual([], sorted(node.iteritems([('missing',)])))
1558
1559
def test_map_to_new_child_new(self):
1560
chkmap = self._get_map({('k1',):'foo', ('k2',):'bar'}, maximum_size=10)
1561
chkmap._ensure_root()
1562
node = chkmap._root_node
1563
# Ensure test validity: nothing paged in below the root.
1564
self.assertEqual(2,
1565
len([value for value in node._items.values()
1566
if type(value) == tuple]))
1567
# now, mapping to k3 should add a k3 leaf
1568
prefix, nodes = node.map(None, ('k3',), 'quux')
1569
self.assertEqual("k", prefix)
1570
self.assertEqual([("", node)], nodes)
1571
# check new child details
1572
child = node._items['k3']
1573
self.assertIsInstance(child, LeafNode)
1574
self.assertEqual(1, len(child))
1575
self.assertEqual({('k3',): 'quux'}, self.to_dict(child, None))
1576
self.assertEqual(None, child._key)
1577
self.assertEqual(10, child.maximum_size)
1578
self.assertEqual(1, child._key_width)
1579
# Check overall structure:
1580
self.assertEqual(3, len(chkmap))
1581
self.assertEqual({('k1',): 'foo', ('k2',): 'bar', ('k3',): 'quux'},
1582
self.to_dict(chkmap))
1583
# serialising should only serialise the new data - k3 and the internal
1584
# node.
1585
keys = list(node.serialise(chkmap._store))
1586
child_key = child.serialise(chkmap._store)[0]
1587
self.assertEqual([child_key, keys[1]], keys)
1588
1589
def test_map_to_child_child_splits_new(self):
1590
chkmap = self._get_map({('k1',):'foo', ('k22',):'bar'}, maximum_size=10)
1591
# Check for the canonical root value for this tree:
1592
self.assertEqualDiff("'' InternalNode\n"
1593
" 'k1' LeafNode\n"
1594
" ('k1',) 'foo'\n"
1595
" 'k2' LeafNode\n"
1596
" ('k22',) 'bar'\n"
1597
, chkmap._dump_tree())
1598
# _dump_tree pages everything in, so reload using just the root
1599
chkmap = CHKMap(chkmap._store, chkmap._root_node)
1600
chkmap._ensure_root()
1601
node = chkmap._root_node
1602
# Ensure test validity: nothing paged in below the root.
1603
self.assertEqual(2,
1604
len([value for value in node._items.values()
1605
if type(value) == tuple]))
1606
# now, mapping to k23 causes k22 ('k2' in node) to split into k22 and
1607
# k23, which for simplicity in the current implementation generates
1608
# a new internal node between node, and k22/k23.
1609
prefix, nodes = node.map(chkmap._store, ('k23',), 'quux')
1610
self.assertEqual("k", prefix)
1611
self.assertEqual([("", node)], nodes)
1612
# check new child details
1613
child = node._items['k2']
1614
self.assertIsInstance(child, InternalNode)
1615
self.assertEqual(2, len(child))
1616
self.assertEqual({('k22',): 'bar', ('k23',): 'quux'},
1617
self.to_dict(child, None))
1618
self.assertEqual(None, child._key)
1619
self.assertEqual(10, child.maximum_size)
1620
self.assertEqual(1, child._key_width)
1621
self.assertEqual(3, child._node_width)
1622
# Check overall structure:
1623
self.assertEqual(3, len(chkmap))
1624
self.assertEqual({('k1',): 'foo', ('k22',): 'bar', ('k23',): 'quux'},
1625
self.to_dict(chkmap))
1626
# serialising should only serialise the new data - although k22 hasn't
1627
# changed because its a special corner case (splitting on with only one
1628
# key leaves one node unaltered), in general k22 is serialised, so we
1629
# expect k22, k23, the new internal node, and node, to be serialised.
1630
keys = list(node.serialise(chkmap._store))
1631
child_key = child._key
1632
k22_key = child._items['k22']._key
1633
k23_key = child._items['k23']._key
1634
self.assertEqual([k22_key, k23_key, child_key, node.key()], keys)
1635
self.assertEqualDiff("'' InternalNode\n"
1636
" 'k1' LeafNode\n"
1637
" ('k1',) 'foo'\n"
1638
" 'k2' InternalNode\n"
1639
" 'k22' LeafNode\n"
1640
" ('k22',) 'bar'\n"
1641
" 'k23' LeafNode\n"
1642
" ('k23',) 'quux'\n"
1643
, chkmap._dump_tree())
1644
1645
def test__search_prefix_filter_with_hash(self):
1646
search_key_func = chk_map.search_key_registry.get('hash-16-way')
1647
node = InternalNode(search_key_func=search_key_func)
1648
node._key_width = 2
1649
node._node_width = 4
1650
self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
1651
self.assertEqual('E8B7', node._search_prefix_filter(('a', 'b')))
1652
self.assertEqual('E8B7', node._search_prefix_filter(('a',)))
1653
1654
def test_unmap_k23_from_k1_k22_k23_gives_k1_k22_tree_new(self):
1655
chkmap = self._get_map(
1656
{('k1',):'foo', ('k22',):'bar', ('k23',): 'quux'}, maximum_size=10)
1657
# Check we have the expected tree.
1658
self.assertEqualDiff("'' InternalNode\n"
1659
" 'k1' LeafNode\n"
1660
" ('k1',) 'foo'\n"
1661
" 'k2' InternalNode\n"
1662
" 'k22' LeafNode\n"
1663
" ('k22',) 'bar'\n"
1664
" 'k23' LeafNode\n"
1665
" ('k23',) 'quux'\n"
1666
, chkmap._dump_tree())
1667
chkmap = CHKMap(chkmap._store, chkmap._root_node)
1668
chkmap._ensure_root()
1669
node = chkmap._root_node
1670
# unmapping k23 should give us a root, with k1 and k22 as direct
1671
# children.
1672
result = node.unmap(chkmap._store, ('k23',))
1673
# check the pointed-at object within node - k2 should now point at the
1674
# k22 leaf (which has been paged in to see if we can collapse the tree)
1675
child = node._items['k2']
1676
self.assertIsInstance(child, LeafNode)
1677
self.assertEqual(1, len(child))
1678
self.assertEqual({('k22',): 'bar'},
1679
self.to_dict(child, None))
1680
# Check overall structure is instact:
1681
self.assertEqual(2, len(chkmap))
1682
self.assertEqual({('k1',): 'foo', ('k22',): 'bar'},
1683
self.to_dict(chkmap))
1684
# serialising should only serialise the new data - the root node.
1685
keys = list(node.serialise(chkmap._store))
1686
self.assertEqual([keys[-1]], keys)
1687
chkmap = CHKMap(chkmap._store, keys[-1])
1688
self.assertEqualDiff("'' InternalNode\n"
1689
" 'k1' LeafNode\n"
1690
" ('k1',) 'foo'\n"
1691
" 'k2' LeafNode\n"
1692
" ('k22',) 'bar'\n"
1693
, chkmap._dump_tree())
1694
1695
def test_unmap_k1_from_k1_k22_k23_gives_k22_k23_tree_new(self):
1696
chkmap = self._get_map(
1697
{('k1',):'foo', ('k22',):'bar', ('k23',): 'quux'}, maximum_size=10)
1698
self.assertEqualDiff("'' InternalNode\n"
1699
" 'k1' LeafNode\n"
1700
" ('k1',) 'foo'\n"
1701
" 'k2' InternalNode\n"
1702
" 'k22' LeafNode\n"
1703
" ('k22',) 'bar'\n"
1704
" 'k23' LeafNode\n"
1705
" ('k23',) 'quux'\n"
1706
, chkmap._dump_tree())
1707
orig_root = chkmap._root_node
1708
chkmap = CHKMap(chkmap._store, orig_root)
1709
chkmap._ensure_root()
1710
node = chkmap._root_node
1711
k2_ptr = node._items['k2']
1712
# unmapping k1 should give us a root, with k22 and k23 as direct
1713
# children, and should not have needed to page in the subtree.
1714
result = node.unmap(chkmap._store, ('k1',))
1715
self.assertEqual(k2_ptr, result)
1716
chkmap = CHKMap(chkmap._store, orig_root)
1717
# Unmapping at the CHKMap level should switch to the new root
1718
chkmap.unmap(('k1',))
1719
self.assertEqual(k2_ptr, chkmap._root_node)
1720
self.assertEqualDiff("'' InternalNode\n"
1721
" 'k22' LeafNode\n"
1722
" ('k22',) 'bar'\n"
1723
" 'k23' LeafNode\n"
1724
" ('k23',) 'quux'\n"
1725
, chkmap._dump_tree())
1726
1727
1728
# leaf:
1729
# map -> fits - done
1730
# map -> doesn't fit - shrink from left till fits
1731
# key data to return: the common prefix, new nodes.
1732
1733
# unmap -> how to tell if siblings can be combined.
1734
# combing leaf nodes means expanding the prefix to the left; so gather the size of
1735
# all the leaf nodes addressed by expanding the prefix by 1; if any adjacent node
1736
# is an internal node, we know that that is a dense subtree - can't combine.
1737
# otherwise as soon as the sum of serialised values exceeds the split threshold
1738
# we know we can't combine - stop.
1739
# unmap -> key return data - space in node, common prefix length? and key count
1740
# internal:
1741
# variable length prefixes? -> later start with fixed width to get something going
1742
# map -> fits - update pointer to leaf
1743
# return [prefix and node] - seems sound.
1744
# map -> doesn't fit - find unique prefix and shift right
1745
# create internal nodes for all the partitions, return list of unique
1746
# prefixes and nodes.
1747
# map -> new prefix - create a leaf
1748
# unmap -> if child key count 0, remove
1749
# unmap -> return space in node, common prefix length? (why?), key count
1750
# map:
1751
# map, if 1 node returned, use it, otherwise make an internal and populate.
1752
# map - unmap - if empty, use empty leafnode (avoids special cases in driver
1753
# code)
1754
# map inits as empty leafnode.
1755
# tools:
1756
# visualiser
1757
1758
1759
# how to handle:
1760
# AA, AB, AC, AD, BA
1761
# packed internal node - ideal:
1762
# AA, AB, AC, AD, BA
1763
# single byte fanout - A,B, AA,AB,AC,AD, BA
1764
# build order's:
1765
# BA
1766
# AB - split, but we want to end up with AB, BA, in one node, with
1767
# 1-4K get0
1768
1769
1770
class TestIterInterestingNodes(TestCaseWithStore):
1771
1772
def get_chk_bytes(self):
1773
if getattr(self, '_chk_bytes', None) is None:
1774
self._chk_bytes = super(TestIterInterestingNodes,
1775
self).get_chk_bytes()
1776
return self._chk_bytes
1777
1778
def get_map_key(self, a_dict):
1779
c_map = self._get_map(a_dict, maximum_size=10,
1780
chk_bytes=self.get_chk_bytes())
1781
return c_map.key()
1782
1783
def assertIterInteresting(self, expected, interesting_keys,
1784
uninteresting_keys):
1785
"""Check the result of iter_interesting_nodes.
1786
1787
:param expected: A list of (record_keys, interesting_chk_pages,
1788
interesting key value pairs)
1789
"""
1790
store = self.get_chk_bytes()
1791
iter_nodes = chk_map.iter_interesting_nodes(store, interesting_keys,
1792
uninteresting_keys)
1793
for count, (exp, act) in enumerate(izip(expected, iter_nodes)):
1794
exp_record_keys, exp_items = exp
1795
records, items = act
1796
exp_tuple = (sorted(exp_record_keys), sorted(exp_items))
1797
act_tuple = (sorted(records.keys()), sorted(items))
1798
self.assertEqual(exp_tuple, act_tuple)
1799
self.assertEqual(len(expected), count + 1)
1800
1801
def test_empty_to_one_keys(self):
1802
target = self.get_map_key({('a',): 'content'})
1803
self.assertIterInteresting(
1804
[([target], [(('a',), 'content')])],
1805
[target], [])
1806
1807
def test_none_to_one_key(self):
1808
basis = self.get_map_key({})
1809
target = self.get_map_key({('a',): 'content'})
1810
self.assertIterInteresting(
1811
[([target], [(('a',), 'content')])],
1812
[target], [basis])
1813
1814
def test_one_to_none_key(self):
1815
basis = self.get_map_key({('a',): 'content'})
1816
target = self.get_map_key({})
1817
self.assertIterInteresting(
1818
[([target], [])],
1819
[target], [basis])
1820
1821
def test_common_pages(self):
1822
basis = self.get_map_key({('a',): 'content',
1823
('b',): 'content',
1824
('c',): 'content',
1825
})
1826
target = self.get_map_key({('a',): 'content',
1827
('b',): 'other content',
1828
('c',): 'content',
1829
})
1830
target_map = CHKMap(self.get_chk_bytes(), target)
1831
self.assertEqualDiff(
1832
"'' InternalNode\n"
1833
" 'a' LeafNode\n"
1834
" ('a',) 'content'\n"
1835
" 'b' LeafNode\n"
1836
" ('b',) 'other content'\n"
1837
" 'c' LeafNode\n"
1838
" ('c',) 'content'\n",
1839
target_map._dump_tree())
1840
b_key = target_map._root_node._items['b'].key()
1841
# This should return the root node, and the node for the 'b' key
1842
self.assertIterInteresting(
1843
[([target], []),
1844
([b_key], [(('b',), 'other content')])],
1845
[target], [basis])
1846
1847
def test_common_sub_page(self):
1848
basis = self.get_map_key({('aaa',): 'common',
1849
('c',): 'common',
1850
})
1851
target = self.get_map_key({('aaa',): 'common',
1852
('aab',): 'new',
1853
('c',): 'common',
1854
})
1855
target_map = CHKMap(self.get_chk_bytes(), target)
1856
self.assertEqualDiff(
1857
"'' InternalNode\n"
1858
" 'a' InternalNode\n"
1859
" 'aaa' LeafNode\n"
1860
" ('aaa',) 'common'\n"
1861
" 'aab' LeafNode\n"
1862
" ('aab',) 'new'\n"
1863
" 'c' LeafNode\n"
1864
" ('c',) 'common'\n",
1865
target_map._dump_tree())
1866
# The key for the internal aa node
1867
a_key = target_map._root_node._items['a'].key()
1868
# The key for the leaf aab node
1869
aab_key = target_map._root_node._items['a']._items['aab'].key()
1870
self.assertIterInteresting(
1871
[([target], []),
1872
([a_key], []),
1873
([aab_key], [(('aab',), 'new')])],
1874
[target], [basis])
1875
1876
def test_multiple_maps(self):
1877
basis1 = self.get_map_key({('aaa',): 'common',
1878
('aab',): 'basis1',
1879
})
1880
basis2 = self.get_map_key({('bbb',): 'common',
1881
('bbc',): 'basis2',
1882
})
1883
target1 = self.get_map_key({('aaa',): 'common',
1884
('aac',): 'target1',
1885
('bbb',): 'common',
1886
})
1887
target2 = self.get_map_key({('aaa',): 'common',
1888
('bba',): 'target2',
1889
('bbb',): 'common',
1890
})
1891
target1_map = CHKMap(self.get_chk_bytes(), target1)
1892
self.assertEqualDiff(
1893
"'' InternalNode\n"
1894
" 'a' InternalNode\n"
1895
" 'aaa' LeafNode\n"
1896
" ('aaa',) 'common'\n"
1897
" 'aac' LeafNode\n"
1898
" ('aac',) 'target1'\n"
1899
" 'b' LeafNode\n"
1900
" ('bbb',) 'common'\n",
1901
target1_map._dump_tree())
1902
# The key for the target1 internal a node
1903
a_key = target1_map._root_node._items['a'].key()
1904
# The key for the leaf aac node
1905
aac_key = target1_map._root_node._items['a']._items['aac'].key()
1906
1907
target2_map = CHKMap(self.get_chk_bytes(), target2)
1908
self.assertEqualDiff(
1909
"'' InternalNode\n"
1910
" 'a' LeafNode\n"
1911
" ('aaa',) 'common'\n"
1912
" 'b' InternalNode\n"
1913
" 'bba' LeafNode\n"
1914
" ('bba',) 'target2'\n"
1915
" 'bbb' LeafNode\n"
1916
" ('bbb',) 'common'\n",
1917
target2_map._dump_tree())
1918
# The key for the target2 internal bb node
1919
b_key = target2_map._root_node._items['b'].key()
1920
# The key for the leaf bba node
1921
bba_key = target2_map._root_node._items['b']._items['bba'].key()
1922
self.assertIterInteresting(
1923
[([target1, target2], []),
1924
([a_key], []),
1925
([b_key], []),
1926
([aac_key], [(('aac',), 'target1')]),
1927
([bba_key], [(('bba',), 'target2')]),
1928
], [target1, target2], [basis1, basis2])
Loggerhead is a web-based interface for Breezy
Version: 2.0.1