/brz/remove-bazaar : contents of bzrlib/tests/test_chk

: (revision 4194.2.2)

To get this branch, use:

bzr branch
http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

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