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