1
# Copyright (C) 2008 Canonical Ltd
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.
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.
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
17
"""Tests for maps built on a CHK versionedfiles facility."""
19
from itertools import izip
26
from bzrlib.chk_map import (
34
class TestNode(tests.TestCase):
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)
44
def test_common_prefix(self):
45
self.assertCommonPrefix('beg', 'beg', 'begin')
47
def test_no_common_prefix(self):
48
self.assertCommonPrefix('', 'begin', 'end')
51
self.assertCommonPrefix('begin', 'begin', 'begin')
53
def test_not_a_prefix(self):
54
self.assertCommonPrefix('b', 'begin', 'b')
57
class TestCaseWithStore(tests.TestCaseWithTransport):
59
def get_chk_bytes(self):
60
# The easiest way to get a CHK store is a development6 repository and
61
# then work with the chk_bytes attribute directly.
62
repo = self.make_repository(".", format="development6-rich-root")
64
self.addCleanup(repo.unlock)
65
repo.start_write_group()
66
self.addCleanup(repo.abort_write_group)
69
def _get_map(self, a_dict, maximum_size=0, chk_bytes=None, key_width=1,
70
search_key_func=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)
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")
86
def to_dict(self, node, *args):
87
return dict(node.iteritems(*args))
90
class TestMap(TestCaseWithStore):
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))
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))
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)])
131
# Leaf nodes must have identical contents
132
self.assertEqual(node_one._items, node_two._items)
133
self.assertEquals([], node_two_stack)
135
def assertCanonicalForm(self, chkmap):
136
"""Assert that the chkmap is in 'canonical' form.
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
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)
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
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)
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)
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)
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
205
self.assertEqual(new_root, chkmap._root_node._key)
207
def test_apply_ab_empty(self):
208
# applying a delta ("a", None, None) to a map with 'a' in it generates
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
219
self.assertEqual(new_root, chkmap._root_node._key)
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)
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)
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"
251
chkmap.map(('aab',), 'v')
252
self.assertEqualDiff("'' LeafNode\n"
256
self.assertCanonicalForm(chkmap)
258
# Creates a new internal node, and splits the others into leaves
259
chkmap.map(('aac',), 'v')
260
self.assertEqualDiff("'' InternalNode\n"
268
self.assertCanonicalForm(chkmap)
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"
283
self.assertCanonicalForm(chkmap)
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)
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"
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"
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",
337
chkmap.map(('aaabaaaa',), 'v')
338
chkmap.map(('aaababaa',), 'v')
339
self.assertEqualDiff("'' InternalNode\n"
341
" ('aaaaaaaa',) 'v'\n"
342
" ('aaaaabaa',) 'v'\n"
344
" ('aaabaaaa',) 'v'\n"
345
" ('aaababaa',) 'v'\n",
347
chkmap.map(('aaabacaa',), 'v')
348
chkmap.map(('aaabadaa',), 'v')
349
self.assertEqualDiff("'' InternalNode\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",
363
chkmap.map(('aaababba',), 'val')
364
chkmap.map(('aaababca',), 'val')
365
self.assertEqualDiff("'' InternalNode\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",
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
387
chkmap.map(('aaabDaaa',), 'v')
388
self.assertEqualDiff("'' InternalNode\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",
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"
422
" ('aab',) 'very long value that splits'\n",
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"
431
self.assertCanonicalForm(chkmap)
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"
446
" ('aab',) 'very long value that splits'\n"
450
chkmap.map(('aab',), 'v')
451
self.assertCanonicalForm(chkmap)
452
self.assertEqualDiff("'' LeafNode\n"
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"
469
# Creates a new internal node, and splits the others into leaves
470
chkmap.map(('aac',), 'v')
471
self.assertEqualDiff("'' InternalNode\n"
479
self.assertCanonicalForm(chkmap)
480
# Now lets unmap one of the keys, and assert that we collapse the
482
chkmap.unmap(('aac',))
483
self.assertEqualDiff("'' LeafNode\n"
487
self.assertCanonicalForm(chkmap)
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"
504
" ('aab',) 'very long value'\n"
508
# Removing the 'aab' key should cause everything to collapse back to a
510
chkmap.unmap(('aab',))
511
self.assertEqualDiff("'' LeafNode\n"
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"
531
" ('aab',) 'long value'\n"
536
# Removing the 'aab' key should cause everything to collapse back to a
538
chkmap.unmap(('aab',))
539
self.assertEqualDiff("'' LeafNode\n"
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"
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
578
chkmap.unmap(('acd',))
579
self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
580
self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
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"
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)
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"
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
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)
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"
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
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
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)
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)
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)
733
def test_iter_changes_empty_ab(self):
734
# Asking for changes between an empty dict to a dict with keys returns
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))))
744
def test_iter_changes_ab_empty(self):
745
# Asking for changes between a dict with keys to an empty dict returns
747
basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
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))))
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))))
759
def test_iter_changes_ab_ab_is_empty(self):
760
basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
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))))
767
def test_iter_changes_ab_ab_nodes_not_loaded(self):
768
basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
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)
777
def test_iter_changes_ab_ab_changed_values_shown(self):
778
basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
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')],
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
791
# aaa - common unaltered
792
# aab - common altered
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'}
805
(('aab',), 'common altered a', 'common altered b'),
806
(('at',), None, 'foo bar t'),
807
(('b',), 'foo bar b', None),
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))))
814
def test_iter_changes_common_pages_not_loaded(self):
815
# aaa - common unaltered
816
# aab - common altered
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)
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'}
849
(('aab',), 'common altered a', 'common altered b'),
850
(('at',), None, 'foo bar t'),
851
(('b',), 'foo bar b', None),
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))))
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()))
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())))
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",)]))
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)
882
{("a", "a"): "content here", ("a", "b"): 'more content'},
883
self.to_dict(chkmap, [("a",)]))
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)
895
{("a", "a"): "content here", ("a", "b"): 'more content'},
896
self.to_dict(chkmap, [("a",)]))
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)
903
{("a", "a"): "content here", ("a", "b"): 'more content'},
904
self.to_dict(chkmap, [("a",)]))
906
def test___len__empty(self):
907
chkmap = self._get_map({})
908
self.assertEqual(0, len(chkmap))
910
def test___len__2(self):
911
chkmap = self._get_map({("foo",):"bar", ("gam",):"quux"})
912
self.assertEqual(2, len(chkmap))
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
933
nodes = sorted(chkmap._root_node._items.items())
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
948
self.assertEqual(2, len(chkmap))
949
self.assertEqual({("k1"*50,): "v1", ("k2"*50,): "v2"},
950
self.to_dict(chkmap))
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))
959
def test_init_and_save_new(self):
960
chk_bytes = self.get_chk_bytes()
961
chkmap = CHKMap(chk_bytes, None)
963
leaf_node = LeafNode()
964
self.assertEqual([key], leaf_node.serialise(chk_bytes))
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))
973
leaf_node = LeafNode()
974
leaf_node.map(chk_bytes, ("foo,",), "bar")
975
self.assertEqual([key], leaf_node.serialise(chk_bytes))
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))
984
leaf_node = LeafNode()
985
self.assertEqual([key], leaf_node.serialise(chkmap._store))
987
def test__dump_tree(self):
988
chkmap = self._get_map({("aaa",): "value1", ("aab",): "value2",
989
("bbb",): "value3",},
991
self.assertEqualDiff("'' InternalNode\n"
992
" 'a' InternalNode\n"
994
" ('aaa',) 'value1'\n"
996
" ('aab',) 'value2'\n"
998
" ('bbb',) 'value3'\n",
1000
self.assertEqualDiff("'' InternalNode\n"
1001
" 'a' InternalNode\n"
1003
" ('aaa',) 'value1'\n"
1005
" ('aab',) 'value2'\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))
1020
def test__dump_tree_in_progress(self):
1021
chkmap = self._get_map({("aaa",): "value1", ("aab",): "value2"},
1023
chkmap.map(('bbb',), 'value3')
1024
self.assertEqualDiff("'' InternalNode\n"
1025
" 'a' InternalNode\n"
1027
" ('aaa',) 'value1'\n"
1029
" ('aab',) 'value2'\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))
1047
def _search_key_single(key):
1048
"""A search key function that maps all nodes to the same value"""
1051
def _test_search_key(key):
1052
return 'test:' + '\x00'.join(key)
1055
class TestMapSearchKeys(TestCaseWithStore):
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')))
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')))
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')))
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"
1097
" 'test:2' LeafNode\n"
1099
" 'test:3' LeafNode\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"
1108
" 'test:2' LeafNode\n"
1110
" 'test:3' LeafNode\n"
1112
, chkmap._dump_tree())
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"
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"
1143
, chkmap._dump_tree())
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"
1158
" '\\x83' LeafNode\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"
1172
" '\\x83' LeafNode\n"
1174
, chkmap._dump_tree())
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"
1189
, chkmap._dump_tree())
1192
class TestSearchKeyFuncs(tests.TestCase):
1194
def assertSearchKey16(self, expected, key):
1195
self.assertEqual(expected, chk_map._search_key_16(key))
1197
def assertSearchKey255(self, expected, key):
1198
actual = chk_map._search_key_255(key)
1199
self.assertEqual(expected, actual, 'actual: %r' % (actual,))
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',))
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
1213
self.assertSearchKey255('\xfdm\x93_\x00P_\x1bL', ('<', 'V'))
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
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)
1227
class TestLeafNode(TestCaseWithStore):
1229
def test_current_size_empty(self):
1231
self.assertEqual(16, node._current_size())
1233
def test_current_size_size_changed(self):
1235
node.set_maximum_size(10)
1236
self.assertEqual(17, node._current_size())
1238
def test_current_size_width_changed(self):
1240
node._key_width = 10
1241
self.assertEqual(17, node._current_size())
1243
def test_current_size_items(self):
1245
base_size = node._current_size()
1246
node.map(None, ("foo bar",), "baz")
1247
self.assertEqual(base_size + 14, node._current_size())
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)
1257
def test_deserialise_items(self):
1258
node = LeafNode.deserialise(
1259
"chkleaf:\n0\n1\n2\n\nfoo bar\x001\nbaz\nquux\x001\nblarh\n",
1261
self.assertEqual(2, len(node))
1262
self.assertEqual([(("foo bar",), "baz"), (("quux",), "blarh")],
1263
sorted(node.iteritems(None)))
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",
1269
self.assertEqual(2, len(node))
1270
self.assertEqual([(("foo",), "bar\x00baz"), (("quux",), "blarh")],
1271
sorted(node.iteritems(None)))
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",
1278
self.assertEqual(2, len(node))
1279
self.assertEqual([(("foo", "1"), "bar\x00baz"), (("quux", ""), "blarh")],
1280
sorted(node.iteritems(None)))
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",
1286
self.assertEqual(2, len(node))
1287
self.assertEqual([(("quux",), "blarh")],
1288
sorted(node.iteritems(None, [("quux",), ("qaz",)])))
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",
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)
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",
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)
1311
def test_key_new(self):
1313
self.assertEqual(None, node.key())
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())
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",
1324
node.unmap(None, ("foo bar",))
1325
self.assertEqual(None, node.key())
1327
def test_map_exceeding_max_size_only_entry_new(self):
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())
1334
def test_map_exceeding_max_size_second_entry_early_difference_new(self):
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)
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)
1349
self.assertEqual({("blue",): "red"}, self.to_dict(node, None))
1350
self.assertEqual(10, node.maximum_size)
1351
self.assertEqual(1, node._key_width)
1353
def test_map_first(self):
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))
1360
def test_map_second(self):
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))
1369
def test_map_replacement(self):
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))
1378
def test_serialise_empty(self):
1379
store = self.get_chk_bytes()
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())
1388
def test_serialise_items(self):
1389
store = self.get_chk_bytes()
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())
1401
def test_unique_serialised_prefix_empty_new(self):
1403
self.assertIs(None, node._compute_search_prefix())
1405
def test_unique_serialised_prefix_one_item_new(self):
1407
node.map(None, ("foo bar", "baz"), "baz quux")
1408
self.assertEqual("foo bar\x00baz", node._compute_search_prefix())
1410
def test_unmap_missing(self):
1412
self.assertRaises(KeyError, node.unmap, None, ("foo bar",))
1414
def test_unmap_present(self):
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))
1422
def test_map_maintains_common_prefixes(self):
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)
1441
def test_unmap_maintains_common_prefixes(self):
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)
1464
class TestInternalNode(TestCaseWithStore):
1466
def test_add_node_empty_new(self):
1467
node = InternalNode('fo')
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]
1485
[child_key, ('sha1:cf67e9997d8228a907c1f5bfb25a8bd9cd916fac',)],
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)
1494
def test_add_node_resets_key_new(self):
1495
node = InternalNode('fo')
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)
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):
1511
def test__iter_nodes_no_key_filter(self):
1512
node = InternalNode('')
1514
child.set_maximum_size(100)
1515
child.map(None, ("foo",), "bar")
1516
node.add_node("f", child)
1518
child.set_maximum_size(100)
1519
child.map(None, ("bar",), "baz")
1520
node.add_node("b", child)
1522
for child, node_key_filter in node._iter_nodes(None, key_filter=None):
1523
self.assertEqual(None, node_key_filter)
1525
def test__iter_nodes_splits_key_filter(self):
1526
node = InternalNode('')
1528
child.set_maximum_size(100)
1529
child.map(None, ("foo",), "bar")
1530
node.add_node("f", child)
1532
child.set_maximum_size(100)
1533
child.map(None, ("bar",), "baz")
1534
node.add_node("b", child)
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
1543
self.assertEqual(1, len(node_key_filter))
1545
def test__iter_nodes_with_multiple_matches(self):
1546
node = InternalNode('')
1548
child.set_maximum_size(100)
1549
child.map(None, ("foo",), "val")
1550
child.map(None, ("fob",), "val")
1551
node.add_node("f", child)
1553
child.set_maximum_size(100)
1554
child.map(None, ("bar",), "val")
1555
child.map(None, ("baz",), "val")
1556
node.add_node("b", child)
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
1563
self.assertEqual(2, len(node_key_filter))
1565
def test_iteritems_empty_new(self):
1566
node = InternalNode()
1567
self.assertEqual([], sorted(node.iteritems(None)))
1569
def test_iteritems_two_children(self):
1570
node = InternalNode()
1572
leaf1.map(None, ('foo bar',), 'quux')
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)))
1580
def test_iteritems_two_children_partial(self):
1581
node = InternalNode()
1583
leaf1.map(None, ('foo bar',), 'quux')
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',)])))
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',)])))
1611
def test_iteritems_partial_empty(self):
1612
node = InternalNode()
1613
self.assertEqual([], sorted(node.iteritems([('missing',)])))
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.
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
1641
keys = list(node.serialise(chkmap._store))
1642
child_key = child.serialise(chkmap._store)[0]
1643
self.assertEqual([child_key, keys[1]], keys)
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"
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.
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"
1694
" 'k2' InternalNode\n"
1698
" ('k23',) 'quux'\n"
1699
, chkmap._dump_tree())
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)
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',)))
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"
1717
" 'k2' InternalNode\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
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"
1749
, chkmap._dump_tree())
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"
1757
" 'k2' InternalNode\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"
1780
" ('k23',) 'quux'\n"
1781
, chkmap._dump_tree())
1785
# map -> fits - done
1786
# map -> doesn't fit - shrink from left till fits
1787
# key data to return: the common prefix, new nodes.
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
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
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
1810
# map inits as empty leafnode.
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
1822
# AB - split, but we want to end up with AB, BA, in one node, with
1826
class TestIterInterestingNodes(TestCaseWithStore):
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
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())
1839
def assertIterInteresting(self, expected, interesting_keys,
1840
uninteresting_keys):
1841
"""Check the result of iter_interesting_nodes.
1843
:param expected: A list of (record_keys, interesting_chk_pages,
1844
interesting key value pairs)
1846
store = self.get_chk_bytes()
1847
iter_nodes = chk_map.iter_interesting_nodes(store, interesting_keys,
1849
nodes = list(iter_nodes)
1850
for count, (exp, act) in enumerate(izip(expected, nodes)):
1851
exp_record, exp_items = exp
1853
exp_tuple = (exp_record, sorted(exp_items))
1855
act_tuple = (None, sorted(items))
1857
act_tuple = (record.key, sorted(items))
1858
self.assertEqual(exp_tuple, act_tuple,
1859
'entry %d did not match expected' % count)
1860
self.assertEqual(len(expected), len(nodes))
1862
def test_empty_to_one_keys(self):
1863
target = self.get_map_key({('a',): 'content'})
1864
self.assertIterInteresting(
1865
[(target, [(('a',), 'content')]),
1868
def test_none_to_one_key(self):
1869
basis = self.get_map_key({})
1870
target = self.get_map_key({('a',): 'content'})
1871
self.assertIterInteresting(
1872
[(None, [(('a',), 'content')]),
1874
], [target], [basis])
1876
def test_one_to_none_key(self):
1877
basis = self.get_map_key({('a',): 'content'})
1878
target = self.get_map_key({})
1879
self.assertIterInteresting(
1883
def test_common_pages(self):
1884
basis = self.get_map_key({('a',): 'content',
1888
target = self.get_map_key({('a',): 'content',
1889
('b',): 'other content',
1892
target_map = CHKMap(self.get_chk_bytes(), target)
1893
self.assertEqualDiff(
1896
" ('a',) 'content'\n"
1898
" ('b',) 'other content'\n"
1900
" ('c',) 'content'\n",
1901
target_map._dump_tree())
1902
b_key = target_map._root_node._items['b'].key()
1903
# This should return the root node, and the node for the 'b' key
1904
self.assertIterInteresting(
1906
(b_key, [(('b',), 'other content')])],
1909
def test_common_sub_page(self):
1910
basis = self.get_map_key({('aaa',): 'common',
1913
target = self.get_map_key({('aaa',): 'common',
1917
target_map = CHKMap(self.get_chk_bytes(), target)
1918
self.assertEqualDiff(
1920
" 'a' InternalNode\n"
1922
" ('aaa',) 'common'\n"
1926
" ('c',) 'common'\n",
1927
target_map._dump_tree())
1928
# The key for the internal aa node
1929
a_key = target_map._root_node._items['a'].key()
1930
# The key for the leaf aab node
1931
aab_key = target_map._root_node._items['a']._items['aab'].key()
1932
self.assertIterInteresting(
1935
(aab_key, [(('aab',), 'new')])],
1938
def test_common_leaf(self):
1939
basis = self.get_map_key({})
1940
target1 = self.get_map_key({('aaa',): 'common'})
1941
target2 = self.get_map_key({('aaa',): 'common',
1944
target3 = self.get_map_key({('aaa',): 'common',
1948
# The LeafNode containing 'aaa': 'common' occurs at 3 different levels.
1949
# Once as a root node, once as a second layer, and once as a third
1950
# layer. It should only be returned one time regardless
1951
target1_map = CHKMap(self.get_chk_bytes(), target1)
1952
self.assertEqualDiff(
1954
" ('aaa',) 'common'\n",
1955
target1_map._dump_tree())
1956
target2_map = CHKMap(self.get_chk_bytes(), target2)
1957
self.assertEqualDiff(
1960
" ('aaa',) 'common'\n"
1962
" ('bbb',) 'new'\n",
1963
target2_map._dump_tree())
1964
target3_map = CHKMap(self.get_chk_bytes(), target3)
1965
self.assertEqualDiff(
1967
" 'a' InternalNode\n"
1969
" ('aaa',) 'common'\n"
1971
" ('aac',) 'other'\n"
1973
" ('bbb',) 'new'\n",
1974
target3_map._dump_tree())
1975
aaa_key = target1_map._root_node.key()
1976
b_key = target2_map._root_node._items['b'].key()
1977
a_key = target3_map._root_node._items['a'].key()
1978
aac_key = target3_map._root_node._items['a']._items['aac'].key()
1979
self.assertIterInteresting(
1980
[(None, [(('aaa',), 'common')]),
1984
(b_key, [(('bbb',), 'new')]),
1986
(aac_key, [(('aac',), 'other')]),
1987
], [target1, target2, target3], [basis])
1989
self.assertIterInteresting(
1992
(b_key, [(('bbb',), 'new')]),
1994
(aac_key, [(('aac',), 'other')]),
1995
], [target2, target3], [target1])
1997
# This may be a case that we relax. A root node is a deep child of the
1998
# excluded set. The cost is buffering root nodes until we have
1999
# determined all possible exclusions. (Because a prefix of '', cannot
2001
self.assertIterInteresting(
2002
[], [target1], [target3])
2004
def test_multiple_maps(self):
2005
basis1 = self.get_map_key({('aaa',): 'common',
2008
basis2 = self.get_map_key({('bbb',): 'common',
2011
target1 = self.get_map_key({('aaa',): 'common',
2012
('aac',): 'target1',
2015
target2 = self.get_map_key({('aaa',): 'common',
2016
('bba',): 'target2',
2019
target1_map = CHKMap(self.get_chk_bytes(), target1)
2020
self.assertEqualDiff(
2022
" 'a' InternalNode\n"
2024
" ('aaa',) 'common'\n"
2026
" ('aac',) 'target1'\n"
2028
" ('bbb',) 'common'\n",
2029
target1_map._dump_tree())
2030
# The key for the target1 internal a node
2031
a_key = target1_map._root_node._items['a'].key()
2032
# The key for the leaf aac node
2033
aac_key = target1_map._root_node._items['a']._items['aac'].key()
2035
target2_map = CHKMap(self.get_chk_bytes(), target2)
2036
self.assertEqualDiff(
2039
" ('aaa',) 'common'\n"
2040
" 'b' InternalNode\n"
2042
" ('bba',) 'target2'\n"
2044
" ('bbb',) 'common'\n",
2045
target2_map._dump_tree())
2046
# The key for the target2 internal bb node
2047
b_key = target2_map._root_node._items['b'].key()
2048
# The key for the leaf bba node
2049
bba_key = target2_map._root_node._items['b']._items['bba'].key()
2050
self.assertIterInteresting(
2055
(aac_key, [(('aac',), 'target1')]),
2056
(bba_key, [(('bba',), 'target2')]),
2057
], [target1, target2], [basis1, basis2])
added
removed
bzrlib/tests/test_chk_map.py
