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