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

: (revision 0.16.112)

To get this branch, use:

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

3641.3.29 by John Arbash Meinel Cleanup the copyright headers	1	# Copyright (C) 2008 Canonical Ltd
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	2	#
	3	# This program is free software; you can redistribute it and/or modify
3641.3.29 by John Arbash Meinel Cleanup the copyright headers	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.
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	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
3641.3.29 by John Arbash Meinel Cleanup the copyright headers	15	# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	16	#
	17
	18	"""Tests for btree indices."""
	19
3641.3.6 by John Arbash Meinel Dropping the number of nodes to 100k from 200k	20	import pprint
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	21	import zlib
	22
	23	from bzrlib import (
	24	btree_index,
	25	errors,
	26	tests,
	27	)
	28	from bzrlib.tests import (
	29	TestCaseWithTransport,
	30	TestScenarioApplier,
	31	adapt_tests,
	32	condition_isinstance,
	33	split_suite_by_condition,
	34	)
	35	from bzrlib.transport import get_transport
	36
	37
	38	def load_tests(standard_tests, module, loader):
	39	# parameterise the TestBTreeNodes tests
	40	node_tests, others = split_suite_by_condition(standard_tests,
	41	condition_isinstance(TestBTreeNodes))
	42	applier = TestScenarioApplier()
3641.3.30 by John Arbash Meinel Rename _parse_btree to _btree_serializer	43	import bzrlib._btree_serializer_py as py_module
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	44	applier.scenarios = [('python', {'parse_btree': py_module})]
	45	if CompiledBtreeParserFeature.available():
	46	# Is there a way to do this that gets missing feature failures rather
	47	# than no indication to the user?
3641.3.30 by John Arbash Meinel Rename _parse_btree to _btree_serializer	48	import bzrlib._btree_serializer_c as c_module
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	49	applier.scenarios.append(('C', {'parse_btree': c_module}))
	50	adapt_tests(node_tests, applier, others)
	51	return others
	52
	53
	54	class _CompiledBtreeParserFeature(tests.Feature):
	55	def _probe(self):
	56	try:
3641.3.30 by John Arbash Meinel Rename _parse_btree to _btree_serializer	57	import bzrlib._btree_serializer_c
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	58	except ImportError:
	59	return False
	60	return True
	61
	62	def feature_name(self):
3641.3.30 by John Arbash Meinel Rename _parse_btree to _btree_serializer	63	return 'bzrlib._btree_serializer_c'
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	64
	65	CompiledBtreeParserFeature = _CompiledBtreeParserFeature()
	66
	67
	68	class BTreeTestCase(TestCaseWithTransport):
	69	# test names here are suffixed by the key length and reference list count
	70	# that they test.
	71
	72	def setUp(self):
	73	TestCaseWithTransport.setUp(self)
	74	self._original_header = btree_index._RESERVED_HEADER_BYTES
	75	def restore():
	76	btree_index._RESERVED_HEADER_BYTES = self._original_header
	77	self.addCleanup(restore)
	78	btree_index._RESERVED_HEADER_BYTES = 100
	79
	80	def make_nodes(self, count, key_elements, reference_lists):
	81	"""Generate count*key_elements sample nodes."""
	82	keys = []
	83	for prefix_pos in range(key_elements):
	84	if key_elements - 1:
	85	prefix = (str(prefix_pos) * 40,)
	86	else:
	87	prefix = ()
3641.3.6 by John Arbash Meinel Dropping the number of nodes to 100k from 200k	88	for pos in xrange(count):
	89	# TODO: This creates odd keys. When count == 100,000, it
	90	# creates a 240 byte key
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	91	key = prefix + (str(pos) * 40,)
	92	value = "value:%s" % pos
	93	if reference_lists:
	94	# generate some references
	95	refs = []
	96	for list_pos in range(reference_lists):
	97	# as many keys in each list as its index + the key depth
	98	# mod 2 - this generates both 0 length lists and
	99	# ones slightly longer than the number of lists.
3641.3.6 by John Arbash Meinel Dropping the number of nodes to 100k from 200k	100	# It also ensures we have non homogeneous lists.
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	101	refs.append([])
	102	for ref_pos in range(list_pos + pos % 2):
	103	if pos % 2:
	104	# refer to a nearby key
	105	refs[-1].append(prefix + ("ref" + str(pos - 1) * 40,))
	106	else:
	107	# serial of this ref in the ref list
	108	refs[-1].append(prefix + ("ref" + str(ref_pos) * 40,))
	109	refs[-1] = tuple(refs[-1])
	110	refs = tuple(refs)
	111	else:
	112	refs = ()
	113	keys.append((key, value, refs))
	114	return keys
	115
3641.5.9 by John Arbash Meinel Shrink the page size so that the three_level and iter_all	116	def shrink_page_size(self):
	117	"""Shrink the default page size so that less fits in a page."""
	118	old_page_size = btree_index._PAGE_SIZE
	119	def cleanup():
	120	btree_index._PAGE_SIZE = old_page_size
	121	self.addCleanup(cleanup)
	122	btree_index._PAGE_SIZE = 2048
	123
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	124
	125	class TestBTreeBuilder(BTreeTestCase):
	126
	127	def test_empty_1_0(self):
	128	builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
	129	# NamedTemporaryFile dies on builder.finish().read(). weird.
	130	temp_file = builder.finish()
	131	content = temp_file.read()
	132	del temp_file
	133	self.assertEqual(
3641.3.3 by John Arbash Meinel Change the header to indicate these indexes are	134	"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=0\n"
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	135	"row_lengths=\n",
	136	content)
	137
	138	def test_empty_2_1(self):
	139	builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=1)
	140	# NamedTemporaryFile dies on builder.finish().read(). weird.
	141	temp_file = builder.finish()
	142	content = temp_file.read()
	143	del temp_file
	144	self.assertEqual(
3641.3.3 by John Arbash Meinel Change the header to indicate these indexes are	145	"B+Tree Graph Index 2\nnode_ref_lists=1\nkey_elements=2\nlen=0\n"
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	146	"row_lengths=\n",
	147	content)
	148
	149	def test_root_leaf_1_0(self):
	150	builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
	151	nodes = self.make_nodes(5, 1, 0)
	152	for node in nodes:
	153	builder.add_node(*node)
	154	# NamedTemporaryFile dies on builder.finish().read(). weird.
	155	temp_file = builder.finish()
	156	content = temp_file.read()
	157	del temp_file
	158	self.assertEqual(158, len(content))
	159	self.assertEqual(
3641.3.3 by John Arbash Meinel Change the header to indicate these indexes are	160	"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	161	"row_lengths=1\n",
	162	content[:73])
	163	node_content = content[73:]
	164	node_bytes = zlib.decompress(node_content)
	165	expected_node = ("type=leaf\n"
	166	"0000000000000000000000000000000000000000\x00\x00value:0\n"
	167	"1111111111111111111111111111111111111111\x00\x00value:1\n"
	168	"2222222222222222222222222222222222222222\x00\x00value:2\n"
	169	"3333333333333333333333333333333333333333\x00\x00value:3\n"
	170	"4444444444444444444444444444444444444444\x00\x00value:4\n")
	171	self.assertEqual(expected_node, node_bytes)
	172
	173	def test_root_leaf_2_2(self):
	174	builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
	175	nodes = self.make_nodes(5, 2, 2)
	176	for node in nodes:
	177	builder.add_node(*node)
	178	# NamedTemporaryFile dies on builder.finish().read(). weird.
	179	temp_file = builder.finish()
	180	content = temp_file.read()
	181	del temp_file
	182	self.assertEqual(264, len(content))
	183	self.assertEqual(
3641.3.3 by John Arbash Meinel Change the header to indicate these indexes are	184	"B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	185	"row_lengths=1\n",
	186	content[:74])
	187	node_content = content[74:]
	188	node_bytes = zlib.decompress(node_content)
	189	expected_node = (
	190	"type=leaf\n"
	191	"0000000000000000000000000000000000000000\x000000000000000000000000000000000000000000\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:0\n"
	192	"0000000000000000000000000000000000000000\x001111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\r0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:1\n"
	193	"0000000000000000000000000000000000000000\x002222222222222222222222222222222222222222\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:2\n"
	194	"0000000000000000000000000000000000000000\x003333333333333333333333333333333333333333\x000000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\t0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\r0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\x00value:3\n"
	195	"0000000000000000000000000000000000000000\x004444444444444444444444444444444444444444\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:4\n"
	196	"1111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:0\n"
	197	"1111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\r1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:1\n"
	198	"1111111111111111111111111111111111111111\x002222222222222222222222222222222222222222\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:2\n"
	199	"1111111111111111111111111111111111111111\x003333333333333333333333333333333333333333\x001111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\t1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\r1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\x00value:3\n"
	200	"1111111111111111111111111111111111111111\x004444444444444444444444444444444444444444\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:4\n"
	201	""
	202	)
	203	self.assertEqual(expected_node, node_bytes)
	204
	205	def test_2_leaves_1_0(self):
	206	builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	207	nodes = self.make_nodes(400, 1, 0)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	208	for node in nodes:
	209	builder.add_node(*node)
	210	# NamedTemporaryFile dies on builder.finish().read(). weird.
	211	temp_file = builder.finish()
	212	content = temp_file.read()
	213	del temp_file
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	214	self.assertEqual(9283, len(content))
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	215	self.assertEqual(
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	216	"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	217	"row_lengths=1,2\n",
	218	content[:77])
	219	root = content[77:4096]
	220	leaf1 = content[4096:8192]
	221	leaf2 = content[8192:]
	222	root_bytes = zlib.decompress(root)
	223	expected_root = (
	224	"type=internal\n"
	225	"offset=0\n"
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	226	) + ("307" * 40) + "\n"
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	227	self.assertEqual(expected_root, root_bytes)
	228	# We already know serialisation works for leaves, check key selection:
	229	leaf1_bytes = zlib.decompress(leaf1)
	230	sorted_node_keys = sorted(node[0] for node in nodes)
	231	node = btree_index._LeafNode(leaf1_bytes, 1, 0)
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	232	self.assertEqual(231, len(node.keys))
	233	self.assertEqual(sorted_node_keys[:231], sorted(node.keys))
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	234	leaf2_bytes = zlib.decompress(leaf2)
	235	node = btree_index._LeafNode(leaf2_bytes, 1, 0)
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	236	self.assertEqual(400 - 231, len(node.keys))
	237	self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	238
	239	def test_last_page_rounded_1_layer(self):
	240	builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
	241	nodes = self.make_nodes(10, 1, 0)
	242	for node in nodes:
	243	builder.add_node(*node)
	244	# NamedTemporaryFile dies on builder.finish().read(). weird.
	245	temp_file = builder.finish()
	246	content = temp_file.read()
	247	del temp_file
	248	self.assertEqual(181, len(content))
	249	self.assertEqual(
3641.3.3 by John Arbash Meinel Change the header to indicate these indexes are	250	"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	251	"row_lengths=1\n",
	252	content[:74])
	253	# Check thelast page is well formed
	254	leaf2 = content[74:]
	255	leaf2_bytes = zlib.decompress(leaf2)
	256	node = btree_index._LeafNode(leaf2_bytes, 1, 0)
	257	self.assertEqual(10, len(node.keys))
	258	sorted_node_keys = sorted(node[0] for node in nodes)
	259	self.assertEqual(sorted_node_keys, sorted(node.keys))
	260
	261	def test_last_page_not_rounded_2_layer(self):
	262	builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	263	nodes = self.make_nodes(400, 1, 0)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	264	for node in nodes:
	265	builder.add_node(*node)
	266	# NamedTemporaryFile dies on builder.finish().read(). weird.
	267	temp_file = builder.finish()
	268	content = temp_file.read()
	269	del temp_file
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	270	self.assertEqual(9283, len(content))
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	271	self.assertEqual(
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	272	"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	273	"row_lengths=1,2\n",
	274	content[:77])
3641.3.30 by John Arbash Meinel Rename _parse_btree to _btree_serializer	275	# Check the last page is well formed
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	276	leaf2 = content[8192:]
	277	leaf2_bytes = zlib.decompress(leaf2)
	278	node = btree_index._LeafNode(leaf2_bytes, 1, 0)
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	279	self.assertEqual(400 - 231, len(node.keys))
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	280	sorted_node_keys = sorted(node[0] for node in nodes)
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	281	self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	282
	283	def test_three_level_tree_details(self):
	284	# The left most pointer in the second internal node in a row should
	285	# pointer to the second node that the internal node is for, _not_
	286	# the first, otherwise the first node overlaps with the last node of
	287	# the prior internal node on that row.
3641.5.9 by John Arbash Meinel Shrink the page size so that the three_level and iter_all	288	self.shrink_page_size()
	289	builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
	290	# 40K nodes is enough to create a two internal nodes on the second
	291	# level, with a 2K page size
	292	nodes = self.make_nodes(20000, 2, 2)
3641.3.5 by John Arbash Meinel For iter_all and three_level tests adjust spill-at.	293
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	294	for node in nodes:
	295	builder.add_node(*node)
	296	transport = get_transport('trace+' + self.get_url(''))
3641.3.7 by John Arbash Meinel Make it easier to profile the btree writer time	297	size = transport.put_file('index', self.time(builder.finish))
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	298	del builder
	299	index = btree_index.BTreeGraphIndex(transport, 'index', size)
	300	# Seed the metadata, we're using internal calls now.
	301	index.key_count()
	302	self.assertEqual(3, len(index._row_lengths),
	303	"Not enough rows: %r" % index._row_lengths)
	304	self.assertEqual(4, len(index._row_offsets))
	305	self.assertEqual(sum(index._row_lengths), index._row_offsets[-1])
	306	internal_nodes = index._get_internal_nodes([0, 1, 2])
	307	root_node = internal_nodes[0]
	308	internal_node1 = internal_nodes[1]
	309	internal_node2 = internal_nodes[2]
	310	# The left most node node2 points at should be one after the right most
	311	# node pointed at by node1.
	312	self.assertEqual(internal_node2.offset, 1 + len(internal_node1.keys))
	313	# The left most key of the second node pointed at by internal_node2
	314	# should be its first key. We can check this by looking for its first key
	315	# in the second node it points at
	316	pos = index._row_offsets[2] + internal_node2.offset + 1
	317	leaf = index._get_leaf_nodes([pos])[pos]
	318	self.assertTrue(internal_node2.keys[0] in leaf.keys)
	319
	320	def test_2_leaves_2_2(self):
	321	builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	322	nodes = self.make_nodes(100, 2, 2)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	323	for node in nodes:
	324	builder.add_node(*node)
	325	# NamedTemporaryFile dies on builder.finish().read(). weird.
	326	temp_file = builder.finish()
	327	content = temp_file.read()
	328	del temp_file
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	329	self.assertEqual(12643, len(content))
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	330	self.assertEqual(
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	331	"B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
	332	"row_lengths=1,3\n",
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	333	content[:77])
	334	root = content[77:4096]
	335	leaf1 = content[4096:8192]
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	336	leaf2 = content[8192:12288]
	337	leaf3 = content[12288:]
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	338	root_bytes = zlib.decompress(root)
	339	expected_root = (
	340	"type=internal\n"
	341	"offset=0\n"
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	342	+ ("0" * 40) + "\x00" + ("91" * 40) + "\n"
	343	+ ("1" * 40) + "\x00" + ("81" * 40) + "\n"
	344	)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	345	self.assertEqual(expected_root, root_bytes)
	346	# We assume the other leaf nodes have been written correctly - layering
	347	# FTW.
	348
	349	def test_spill_index_stress_1_1(self):
	350	builder = btree_index.BTreeBuilder(key_elements=1, spill_at=2)
	351	nodes = [node[0:2] for node in self.make_nodes(16, 1, 0)]
	352	builder.add_node(*nodes[0])
	353	# Test the parts of the index that take up memory are doing so
	354	# predictably.
	355	self.assertEqual(1, len(builder._nodes))
	356	self.assertEqual(1, len(builder._keys))
3644.2.5 by John Arbash Meinel Restore the exact old tests, only assert that	357	self.assertIs(None, builder._nodes_by_key)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	358	builder.add_node(*nodes[1])
	359	self.assertEqual(0, len(builder._nodes))
	360	self.assertEqual(0, len(builder._keys))
3644.2.5 by John Arbash Meinel Restore the exact old tests, only assert that	361	self.assertIs(None, builder._nodes_by_key)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	362	self.assertEqual(1, len(builder._backing_indices))
	363	self.assertEqual(2, builder._backing_indices[0].key_count())
	364	# now back to memory
	365	builder.add_node(*nodes[2])
	366	self.assertEqual(1, len(builder._nodes))
	367	self.assertEqual(1, len(builder._keys))
3644.2.5 by John Arbash Meinel Restore the exact old tests, only assert that	368	self.assertIs(None, builder._nodes_by_key)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	369	# And spills to a second backing index combing all
	370	builder.add_node(*nodes[3])
	371	self.assertEqual(0, len(builder._nodes))
	372	self.assertEqual(0, len(builder._keys))
3644.2.5 by John Arbash Meinel Restore the exact old tests, only assert that	373	self.assertIs(None, builder._nodes_by_key)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	374	self.assertEqual(2, len(builder._backing_indices))
	375	self.assertEqual(None, builder._backing_indices[0])
	376	self.assertEqual(4, builder._backing_indices[1].key_count())
	377	# The next spills to the 2-len slot
	378	builder.add_node(*nodes[4])
	379	builder.add_node(*nodes[5])
	380	self.assertEqual(0, len(builder._nodes))
	381	self.assertEqual(0, len(builder._keys))
3644.2.5 by John Arbash Meinel Restore the exact old tests, only assert that	382	self.assertIs(None, builder._nodes_by_key)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	383	self.assertEqual(2, len(builder._backing_indices))
	384	self.assertEqual(2, builder._backing_indices[0].key_count())
	385	self.assertEqual(4, builder._backing_indices[1].key_count())
	386	# Next spill combines
	387	builder.add_node(*nodes[6])
	388	builder.add_node(*nodes[7])
	389	self.assertEqual(3, len(builder._backing_indices))
	390	self.assertEqual(None, builder._backing_indices[0])
	391	self.assertEqual(None, builder._backing_indices[1])
	392	self.assertEqual(8, builder._backing_indices[2].key_count())
	393	# And so forth - counting up in binary.
	394	builder.add_node(*nodes[8])
	395	builder.add_node(*nodes[9])
	396	self.assertEqual(3, len(builder._backing_indices))
	397	self.assertEqual(2, builder._backing_indices[0].key_count())
	398	self.assertEqual(None, builder._backing_indices[1])
	399	self.assertEqual(8, builder._backing_indices[2].key_count())
	400	builder.add_node(*nodes[10])
	401	builder.add_node(*nodes[11])
	402	self.assertEqual(3, len(builder._backing_indices))
	403	self.assertEqual(None, builder._backing_indices[0])
	404	self.assertEqual(4, builder._backing_indices[1].key_count())
	405	self.assertEqual(8, builder._backing_indices[2].key_count())
	406	builder.add_node(*nodes[12])
	407	# Test that memory and disk are both used for query methods; and that
	408	# None is skipped over happily.
	409	self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
	410	list(builder.iter_all_entries()))
	411	# Two nodes - one memory one disk
	412	self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
	413	set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
	414	self.assertEqual(13, builder.key_count())
	415	self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
	416	set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
	417	builder.add_node(*nodes[13])
	418	self.assertEqual(3, len(builder._backing_indices))
	419	self.assertEqual(2, builder._backing_indices[0].key_count())
	420	self.assertEqual(4, builder._backing_indices[1].key_count())
	421	self.assertEqual(8, builder._backing_indices[2].key_count())
	422	builder.add_node(*nodes[14])
	423	builder.add_node(*nodes[15])
	424	self.assertEqual(4, len(builder._backing_indices))
	425	self.assertEqual(None, builder._backing_indices[0])
	426	self.assertEqual(None, builder._backing_indices[1])
	427	self.assertEqual(None, builder._backing_indices[2])
	428	self.assertEqual(16, builder._backing_indices[3].key_count())
	429	# Now finish, and check we got a correctly ordered tree
	430	transport = self.get_transport('')
	431	size = transport.put_file('index', builder.finish())
	432	index = btree_index.BTreeGraphIndex(transport, 'index', size)
	433	nodes = list(index.iter_all_entries())
	434	self.assertEqual(sorted(nodes), nodes)
	435	self.assertEqual(16, len(nodes))
	436
3777.5.3 by John Arbash Meinel Add Builder.set_optimize(for_size=True) for GraphIndexBuilder and BTreeBuilder.	437	def test_set_optimize(self):
	438	builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
	439	builder.set_optimize(for_size=True)
	440	self.assertTrue(builder._optimize_for_size)
	441	builder.set_optimize(for_size=False)
	442	self.assertFalse(builder._optimize_for_size)
	443
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	444	def test_spill_index_stress_2_2(self):
	445	# test that references and longer keys don't confuse things.
	446	builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2,
	447	spill_at=2)
	448	nodes = self.make_nodes(16, 2, 2)
	449	builder.add_node(*nodes[0])
	450	# Test the parts of the index that take up memory are doing so
	451	# predictably.
	452	self.assertEqual(1, len(builder._keys))
3644.2.1 by John Arbash Meinel Change the IndexBuilders to not generate the nodes_by_key unless needed.	453	self.assertEqual(1, len(builder._nodes))
3644.2.5 by John Arbash Meinel Restore the exact old tests, only assert that	454	self.assertIs(None, builder._nodes_by_key)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	455	builder.add_node(*nodes[1])
	456	self.assertEqual(0, len(builder._keys))
	457	self.assertEqual(0, len(builder._nodes))
3644.2.5 by John Arbash Meinel Restore the exact old tests, only assert that	458	self.assertIs(None, builder._nodes_by_key)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	459	self.assertEqual(1, len(builder._backing_indices))
	460	self.assertEqual(2, builder._backing_indices[0].key_count())
	461	# now back to memory
3644.2.6 by John Arbash Meinel Restore the exact old tests, only assert that	462	old = dict(builder._get_nodes_by_key()) #Build up the nodes by key dict
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	463	builder.add_node(*nodes[2])
3644.2.1 by John Arbash Meinel Change the IndexBuilders to not generate the nodes_by_key unless needed.	464	self.assertEqual(1, len(builder._nodes))
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	465	self.assertEqual(1, len(builder._keys))
3644.2.6 by John Arbash Meinel Restore the exact old tests, only assert that	466	self.assertIsNot(None, builder._nodes_by_key)
	467	self.assertNotEqual({}, builder._nodes_by_key)
	468	# We should have a new entry
	469	self.assertNotEqual(old, builder._nodes_by_key)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	470	# And spills to a second backing index combing all
	471	builder.add_node(*nodes[3])
	472	self.assertEqual(0, len(builder._nodes))
	473	self.assertEqual(0, len(builder._keys))
3644.2.5 by John Arbash Meinel Restore the exact old tests, only assert that	474	self.assertIs(None, builder._nodes_by_key)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	475	self.assertEqual(2, len(builder._backing_indices))
	476	self.assertEqual(None, builder._backing_indices[0])
	477	self.assertEqual(4, builder._backing_indices[1].key_count())
	478	# The next spills to the 2-len slot
	479	builder.add_node(*nodes[4])
	480	builder.add_node(*nodes[5])
	481	self.assertEqual(0, len(builder._nodes))
	482	self.assertEqual(0, len(builder._keys))
3644.2.5 by John Arbash Meinel Restore the exact old tests, only assert that	483	self.assertIs(None, builder._nodes_by_key)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	484	self.assertEqual(2, len(builder._backing_indices))
	485	self.assertEqual(2, builder._backing_indices[0].key_count())
	486	self.assertEqual(4, builder._backing_indices[1].key_count())
	487	# Next spill combines
	488	builder.add_node(*nodes[6])
	489	builder.add_node(*nodes[7])
	490	self.assertEqual(3, len(builder._backing_indices))
	491	self.assertEqual(None, builder._backing_indices[0])
	492	self.assertEqual(None, builder._backing_indices[1])
	493	self.assertEqual(8, builder._backing_indices[2].key_count())
	494	# And so forth - counting up in binary.
	495	builder.add_node(*nodes[8])
	496	builder.add_node(*nodes[9])
	497	self.assertEqual(3, len(builder._backing_indices))
	498	self.assertEqual(2, builder._backing_indices[0].key_count())
	499	self.assertEqual(None, builder._backing_indices[1])
	500	self.assertEqual(8, builder._backing_indices[2].key_count())
	501	builder.add_node(*nodes[10])
	502	builder.add_node(*nodes[11])
	503	self.assertEqual(3, len(builder._backing_indices))
	504	self.assertEqual(None, builder._backing_indices[0])
	505	self.assertEqual(4, builder._backing_indices[1].key_count())
	506	self.assertEqual(8, builder._backing_indices[2].key_count())
	507	builder.add_node(*nodes[12])
	508	# Test that memory and disk are both used for query methods; and that
	509	# None is skipped over happily.
	510	self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
	511	list(builder.iter_all_entries()))
	512	# Two nodes - one memory one disk
3644.2.5 by John Arbash Meinel Restore the exact old tests, only assert that	513	self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
	514	set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	515	self.assertEqual(13, builder.key_count())
3644.2.5 by John Arbash Meinel Restore the exact old tests, only assert that	516	self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
	517	set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	518	builder.add_node(*nodes[13])
	519	self.assertEqual(3, len(builder._backing_indices))
	520	self.assertEqual(2, builder._backing_indices[0].key_count())
	521	self.assertEqual(4, builder._backing_indices[1].key_count())
	522	self.assertEqual(8, builder._backing_indices[2].key_count())
	523	builder.add_node(*nodes[14])
	524	builder.add_node(*nodes[15])
	525	self.assertEqual(4, len(builder._backing_indices))
	526	self.assertEqual(None, builder._backing_indices[0])
	527	self.assertEqual(None, builder._backing_indices[1])
	528	self.assertEqual(None, builder._backing_indices[2])
	529	self.assertEqual(16, builder._backing_indices[3].key_count())
	530	# Now finish, and check we got a correctly ordered tree
	531	transport = self.get_transport('')
	532	size = transport.put_file('index', builder.finish())
	533	index = btree_index.BTreeGraphIndex(transport, 'index', size)
	534	nodes = list(index.iter_all_entries())
	535	self.assertEqual(sorted(nodes), nodes)
	536	self.assertEqual(16, len(nodes))
	537
	538	def test_spill_index_duplicate_key_caught_on_finish(self):
	539	builder = btree_index.BTreeBuilder(key_elements=1, spill_at=2)
	540	nodes = [node[0:2] for node in self.make_nodes(16, 1, 0)]
	541	builder.add_node(*nodes[0])
	542	builder.add_node(*nodes[1])
	543	builder.add_node(*nodes[0])
	544	self.assertRaises(errors.BadIndexDuplicateKey, builder.finish)
	545
	546
	547	class TestBTreeIndex(BTreeTestCase):
	548
	549	def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
	550	builder = btree_index.BTreeBuilder(reference_lists=ref_lists,
	551	key_elements=key_elements)
	552	for key, value, references in nodes:
	553	builder.add_node(key, value, references)
	554	stream = builder.finish()
	555	trans = get_transport('trace+' + self.get_url())
	556	size = trans.put_file('index', stream)
	557	return btree_index.BTreeGraphIndex(trans, 'index', size)
	558
	559	def test_trivial_constructor(self):
	560	transport = get_transport('trace+' + self.get_url(''))
	561	index = btree_index.BTreeGraphIndex(transport, 'index', None)
	562	# Checks the page size at load, but that isn't logged yet.
	563	self.assertEqual([], transport._activity)
	564
	565	def test_with_size_constructor(self):
	566	transport = get_transport('trace+' + self.get_url(''))
	567	index = btree_index.BTreeGraphIndex(transport, 'index', 1)
	568	# Checks the page size at load, but that isn't logged yet.
	569	self.assertEqual([], transport._activity)
	570
	571	def test_empty_key_count_no_size(self):
	572	builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
	573	transport = get_transport('trace+' + self.get_url(''))
	574	transport.put_file('index', builder.finish())
	575	index = btree_index.BTreeGraphIndex(transport, 'index', None)
	576	del transport._activity[:]
	577	self.assertEqual([], transport._activity)
	578	self.assertEqual(0, index.key_count())
	579	# The entire index should have been requested (as we generally have the
	580	# size available, and doing many small readvs is inappropriate).
	581	# We can't tell how much was actually read here, but - check the code.
3824.1.2 by John Arbash Meinel iter_all_entries() shouldn't need to re-read the page.	582	self.assertEqual([('get', 'index')], transport._activity)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	583
	584	def test_empty_key_count(self):
	585	builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
	586	transport = get_transport('trace+' + self.get_url(''))
	587	size = transport.put_file('index', builder.finish())
	588	self.assertEqual(72, size)
	589	index = btree_index.BTreeGraphIndex(transport, 'index', size)
	590	del transport._activity[:]
	591	self.assertEqual([], transport._activity)
	592	self.assertEqual(0, index.key_count())
	593	# The entire index should have been read, as 4K > size
	594	self.assertEqual([('readv', 'index', [(0, 72)], False, None)],
	595	transport._activity)
	596
	597	def test_non_empty_key_count_2_2(self):
	598	builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
	599	nodes = self.make_nodes(35, 2, 2)
	600	for node in nodes:
	601	builder.add_node(*node)
	602	transport = get_transport('trace+' + self.get_url(''))
	603	size = transport.put_file('index', builder.finish())
	604	index = btree_index.BTreeGraphIndex(transport, 'index', size)
	605	del transport._activity[:]
	606	self.assertEqual([], transport._activity)
	607	self.assertEqual(70, index.key_count())
	608	# The entire index should have been read, as it is one page long.
	609	self.assertEqual([('readv', 'index', [(0, size)], False, None)],
	610	transport._activity)
3641.5.8 by John Arbash Meinel Fix up the test suite, now that we pack more efficiently.	611	self.assertEqual(1199, size)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	612
3824.1.1 by John Arbash Meinel Fix _read_nodes() to only issue a single read if there is no known size.	613	def test__read_nodes_no_size_one_page_reads_once(self):
	614	self.make_index(nodes=[(('key',), 'value', ())])
	615	trans = get_transport('trace+' + self.get_url())
	616	index = btree_index.BTreeGraphIndex(trans, 'index', None)
	617	del trans._activity[:]
	618	nodes = dict(index._read_nodes([0]))
	619	self.assertEqual([0], nodes.keys())
	620	node = nodes[0]
	621	self.assertEqual([('key',)], node.keys.keys())
	622	self.assertEqual([('get', 'index')], trans._activity)
	623
	624	def test__read_nodes_no_size_multiple_pages(self):
	625	index = self.make_index(2, 2, nodes=self.make_nodes(160, 2, 2))
	626	index.key_count()
	627	num_pages = index._row_offsets[-1]
	628	# Reopen with a traced transport and no size
	629	trans = get_transport('trace+' + self.get_url())
	630	index = btree_index.BTreeGraphIndex(trans, 'index', None)
	631	del trans._activity[:]
	632	nodes = dict(index._read_nodes([0]))
	633	self.assertEqual(range(num_pages), nodes.keys())
	634
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	635	def test_2_levels_key_count_2_2(self):
	636	builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
	637	nodes = self.make_nodes(160, 2, 2)
	638	for node in nodes:
	639	builder.add_node(*node)
	640	transport = get_transport('trace+' + self.get_url(''))
	641	size = transport.put_file('index', builder.finish())
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	642	self.assertEqual(17692, size)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	643	index = btree_index.BTreeGraphIndex(transport, 'index', size)
	644	del transport._activity[:]
	645	self.assertEqual([], transport._activity)
	646	self.assertEqual(320, index.key_count())
	647	# The entire index should not have been read.
	648	self.assertEqual([('readv', 'index', [(0, 4096)], False, None)],
	649	transport._activity)
	650
	651	def test_validate_one_page(self):
	652	builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	653	nodes = self.make_nodes(45, 2, 2)
	654	for node in nodes:
	655	builder.add_node(*node)
	656	transport = get_transport('trace+' + self.get_url(''))
	657	size = transport.put_file('index', builder.finish())
	658	index = btree_index.BTreeGraphIndex(transport, 'index', size)
	659	del transport._activity[:]
	660	self.assertEqual([], transport._activity)
	661	index.validate()
	662	# The entire index should have been read linearly.
	663	self.assertEqual([('readv', 'index', [(0, size)], False, None)],
	664	transport._activity)
	665	self.assertEqual(1514, size)
	666
	667	def test_validate_two_pages(self):
	668	builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	669	nodes = self.make_nodes(80, 2, 2)
	670	for node in nodes:
	671	builder.add_node(*node)
	672	transport = get_transport('trace+' + self.get_url(''))
	673	size = transport.put_file('index', builder.finish())
	674	# Root page, 2 leaf pages
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	675	self.assertEqual(9339, size)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	676	index = btree_index.BTreeGraphIndex(transport, 'index', size)
	677	del transport._activity[:]
	678	self.assertEqual([], transport._activity)
	679	index.validate()
	680	# The entire index should have been read linearly.
	681	self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	682	('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	683	transport._activity)
	684	# XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
	685	# node and make validate find them.
	686
	687	def test_eq_ne(self):
	688	# two indices are equal when constructed with the same parameters:
	689	transport1 = get_transport('trace+' + self.get_url(''))
	690	transport2 = get_transport(self.get_url(''))
	691	self.assertTrue(
	692	btree_index.BTreeGraphIndex(transport1, 'index', None) ==
	693	btree_index.BTreeGraphIndex(transport1, 'index', None))
	694	self.assertTrue(
	695	btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
	696	btree_index.BTreeGraphIndex(transport1, 'index', 20))
	697	self.assertFalse(
	698	btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
	699	btree_index.BTreeGraphIndex(transport2, 'index', 20))
	700	self.assertFalse(
	701	btree_index.BTreeGraphIndex(transport1, 'inde1', 20) ==
	702	btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
	703	self.assertFalse(
	704	btree_index.BTreeGraphIndex(transport1, 'index', 10) ==
	705	btree_index.BTreeGraphIndex(transport1, 'index', 20))
	706	self.assertFalse(
	707	btree_index.BTreeGraphIndex(transport1, 'index', None) !=
	708	btree_index.BTreeGraphIndex(transport1, 'index', None))
	709	self.assertFalse(
	710	btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
	711	btree_index.BTreeGraphIndex(transport1, 'index', 20))
	712	self.assertTrue(
	713	btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
	714	btree_index.BTreeGraphIndex(transport2, 'index', 20))
	715	self.assertTrue(
	716	btree_index.BTreeGraphIndex(transport1, 'inde1', 20) !=
	717	btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
	718	self.assertTrue(
	719	btree_index.BTreeGraphIndex(transport1, 'index', 10) !=
	720	btree_index.BTreeGraphIndex(transport1, 'index', 20))
	721
3824.1.2 by John Arbash Meinel iter_all_entries() shouldn't need to re-read the page.	722	def test_iter_all_only_root_no_size(self):
	723	self.make_index(nodes=[(('key',), 'value', ())])
	724	trans = get_transport('trace+' + self.get_url(''))
	725	index = btree_index.BTreeGraphIndex(trans, 'index', None)
	726	del trans._activity[:]
	727	self.assertEqual([(('key',), 'value')],
	728	[x[1:] for x in index.iter_all_entries()])
	729	self.assertEqual([('get', 'index')], trans._activity)
	730
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	731	def test_iter_all_entries_reads(self):
	732	# iterating all entries reads the header, then does a linear
	733	# read.
3641.5.9 by John Arbash Meinel Shrink the page size so that the three_level and iter_all	734	self.shrink_page_size()
3641.5.11 by John Arbash Meinel Some small test cleanup	735	builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	736	# 20k nodes is enough to create a two internal nodes on the second
3641.5.9 by John Arbash Meinel Shrink the page size so that the three_level and iter_all	737	# level, with a 2K page size
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	738	nodes = self.make_nodes(10000, 2, 2)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	739	for node in nodes:
	740	builder.add_node(*node)
	741	transport = get_transport('trace+' + self.get_url(''))
	742	size = transport.put_file('index', builder.finish())
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	743	self.assertEqual(1303220, size, 'number of expected bytes in the'
	744	' output changed')
3641.5.9 by John Arbash Meinel Shrink the page size so that the three_level and iter_all	745	page_size = btree_index._PAGE_SIZE
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	746	del builder
	747	index = btree_index.BTreeGraphIndex(transport, 'index', size)
	748	del transport._activity[:]
	749	self.assertEqual([], transport._activity)
3641.5.8 by John Arbash Meinel Fix up the test suite, now that we pack more efficiently.	750	found_nodes = self.time(list, index.iter_all_entries())
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	751	bare_nodes = []
	752	for node in found_nodes:
	753	self.assertTrue(node[0] is index)
	754	bare_nodes.append(node[1:])
	755	self.assertEqual(3, len(index._row_lengths),
	756	"Not enough rows: %r" % index._row_lengths)
	757	# Should be as long as the nodes we supplied
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	758	self.assertEqual(20000, len(found_nodes))
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	759	# Should have the same content
	760	self.assertEqual(set(nodes), set(bare_nodes))
	761	# Should have done linear scan IO up the index, ignoring
	762	# the internal nodes:
	763	# The entire index should have been read
	764	total_pages = sum(index._row_lengths)
	765	self.assertEqual(total_pages, index._row_offsets[-1])
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	766	self.assertEqual(1303220, size)
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	767	# The start of the leaves
3641.5.9 by John Arbash Meinel Shrink the page size so that the three_level and iter_all	768	first_byte = index._row_offsets[-2] * page_size
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	769	readv_request = []
3641.5.9 by John Arbash Meinel Shrink the page size so that the three_level and iter_all	770	for offset in range(first_byte, size, page_size):
	771	readv_request.append((offset, page_size))
3641.3.6 by John Arbash Meinel Dropping the number of nodes to 100k from 200k	772	# The last page is truncated
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	773	readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
3641.5.9 by John Arbash Meinel Shrink the page size so that the three_level and iter_all	774	expected = [('readv', 'index', [(0, page_size)], False, None),
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	775	('readv', 'index', readv_request, False, None)]
	776	if expected != transport._activity:
	777	self.assertEqualDiff(pprint.pformat(expected),
	778	pprint.pformat(transport._activity))
	779
	780	def _test_iter_entries_references_resolved(self):
	781	index = self.make_index(1, nodes=[
	782	(('name', ), 'data', ([('ref', ), ('ref', )], )),
	783	(('ref', ), 'refdata', ([], ))])
	784	self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),('ref',)),)),
	785	(index, ('ref', ), 'refdata', ((), ))]),
	786	set(index.iter_entries([('name',), ('ref',)])))
	787
	788	def test_iter_entries_references_2_refs_resolved(self):
	789	# iterating some entries reads just the pages needed. For now, to
	790	# get it working and start measuring, only 4K pages are read.
	791	builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
	792	# 80 nodes is enough to create a two-level index.
	793	nodes = self.make_nodes(160, 2, 2)
	794	for node in nodes:
	795	builder.add_node(*node)
	796	transport = get_transport('trace+' + self.get_url(''))
	797	size = transport.put_file('index', builder.finish())
	798	del builder
	799	index = btree_index.BTreeGraphIndex(transport, 'index', size)
	800	del transport._activity[:]
	801	self.assertEqual([], transport._activity)
	802	# search for one key
	803	found_nodes = list(index.iter_entries([nodes[30][0]]))
	804	bare_nodes = []
	805	for node in found_nodes:
	806	self.assertTrue(node[0] is index)
	807	bare_nodes.append(node[1:])
	808	# Should be as long as the nodes we supplied
	809	self.assertEqual(1, len(found_nodes))
	810	# Should have the same content
	811	self.assertEqual(nodes[30], bare_nodes[0])
	812	# Should have read the root node, then one leaf page:
	813	self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
3641.5.17 by John Arbash Meinel Fix up the test suite now that things don't pack as well.	814	('readv', 'index', [(8192, 4096), ], False, None)],
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	815	transport._activity)
	816
	817	def test_iter_key_prefix_1_element_key_None(self):
	818	index = self.make_index()
	819	self.assertRaises(errors.BadIndexKey, list,
	820	index.iter_entries_prefix([(None, )]))
	821
	822	def test_iter_key_prefix_wrong_length(self):
	823	index = self.make_index()
	824	self.assertRaises(errors.BadIndexKey, list,
	825	index.iter_entries_prefix([('foo', None)]))
	826	index = self.make_index(key_elements=2)
	827	self.assertRaises(errors.BadIndexKey, list,
	828	index.iter_entries_prefix([('foo', )]))
	829	self.assertRaises(errors.BadIndexKey, list,
	830	index.iter_entries_prefix([('foo', None, None)]))
	831
	832	def test_iter_key_prefix_1_key_element_no_refs(self):
	833	index = self.make_index( nodes=[
	834	(('name', ), 'data', ()),
	835	(('ref', ), 'refdata', ())])
	836	self.assertEqual(set([(index, ('name', ), 'data'),
	837	(index, ('ref', ), 'refdata')]),
	838	set(index.iter_entries_prefix([('name', ), ('ref', )])))
	839
	840	def test_iter_key_prefix_1_key_element_refs(self):
	841	index = self.make_index(1, nodes=[
	842	(('name', ), 'data', ([('ref', )], )),
	843	(('ref', ), 'refdata', ([], ))])
	844	self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
	845	(index, ('ref', ), 'refdata', ((), ))]),
	846	set(index.iter_entries_prefix([('name', ), ('ref', )])))
	847
	848	def test_iter_key_prefix_2_key_element_no_refs(self):
	849	index = self.make_index(key_elements=2, nodes=[
	850	(('name', 'fin1'), 'data', ()),
	851	(('name', 'fin2'), 'beta', ()),
	852	(('ref', 'erence'), 'refdata', ())])
	853	self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
	854	(index, ('ref', 'erence'), 'refdata')]),
	855	set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
	856	self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
	857	(index, ('name', 'fin2'), 'beta')]),
	858	set(index.iter_entries_prefix([('name', None)])))
	859
	860	def test_iter_key_prefix_2_key_element_refs(self):
	861	index = self.make_index(1, key_elements=2, nodes=[
	862	(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
	863	(('name', 'fin2'), 'beta', ([], )),
	864	(('ref', 'erence'), 'refdata', ([], ))])
	865	self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
	866	(index, ('ref', 'erence'), 'refdata', ((), ))]),
	867	set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
	868	self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
	869	(index, ('name', 'fin2'), 'beta', ((), ))]),
	870	set(index.iter_entries_prefix([('name', None)])))
	871
	872
	873	class TestBTreeNodes(BTreeTestCase):
	874
	875	def restore_parser(self):
3641.3.30 by John Arbash Meinel Rename _parse_btree to _btree_serializer	876	btree_index._btree_serializer = self.saved_parser
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	877
	878	def setUp(self):
	879	BTreeTestCase.setUp(self)
3641.3.30 by John Arbash Meinel Rename _parse_btree to _btree_serializer	880	self.saved_parser = btree_index._btree_serializer
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	881	self.addCleanup(self.restore_parser)
3641.3.30 by John Arbash Meinel Rename _parse_btree to _btree_serializer	882	btree_index._btree_serializer = self.parse_btree
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	883
	884	def test_LeafNode_1_0(self):
	885	node_bytes = ("type=leaf\n"
	886	"0000000000000000000000000000000000000000\x00\x00value:0\n"
	887	"1111111111111111111111111111111111111111\x00\x00value:1\n"
	888	"2222222222222222222222222222222222222222\x00\x00value:2\n"
	889	"3333333333333333333333333333333333333333\x00\x00value:3\n"
	890	"4444444444444444444444444444444444444444\x00\x00value:4\n")
	891	node = btree_index._LeafNode(node_bytes, 1, 0)
	892	# We do direct access, or don't care about order, to leaf nodes most of
	893	# the time, so a dict is useful:
	894	self.assertEqual({
	895	("0000000000000000000000000000000000000000",): ("value:0", ()),
	896	("1111111111111111111111111111111111111111",): ("value:1", ()),
	897	("2222222222222222222222222222222222222222",): ("value:2", ()),
	898	("3333333333333333333333333333333333333333",): ("value:3", ()),
	899	("4444444444444444444444444444444444444444",): ("value:4", ()),
	900	}, node.keys)
	901
	902	def test_LeafNode_2_2(self):
	903	node_bytes = ("type=leaf\n"
	904	"00\x0000\x00\t00\x00ref00\x00value:0\n"
	905	"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
	906	"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
	907	"11\x0044\x00\t11\x00ref00\x00value:4\n"
	908	""
	909	)
	910	node = btree_index._LeafNode(node_bytes, 2, 2)
	911	# We do direct access, or don't care about order, to leaf nodes most of
	912	# the time, so a dict is useful:
	913	self.assertEqual({
	914	('00', '00'): ('value:0', ((), (('00', 'ref00'),))),
	915	('00', '11'): ('value:1',
	916	((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01')))),
	917	('11', '33'): ('value:3',
	918	((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
	919	('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
	920	}, node.keys)
	921
	922	def test_InternalNode_1(self):
	923	node_bytes = ("type=internal\n"
	924	"offset=1\n"
	925	"0000000000000000000000000000000000000000\n"
	926	"1111111111111111111111111111111111111111\n"
	927	"2222222222222222222222222222222222222222\n"
	928	"3333333333333333333333333333333333333333\n"
	929	"4444444444444444444444444444444444444444\n"
	930	)
	931	node = btree_index._InternalNode(node_bytes)
	932	# We want to bisect to find the right children from this node, so a
	933	# vector is most useful.
	934	self.assertEqual([
	935	("0000000000000000000000000000000000000000",),
	936	("1111111111111111111111111111111111111111",),
	937	("2222222222222222222222222222222222222222",),
	938	("3333333333333333333333333333333333333333",),
	939	("4444444444444444444444444444444444444444",),
	940	], node.keys)
	941	self.assertEqual(1, node.offset)
	942
	943	def test_LeafNode_2_2(self):
	944	node_bytes = ("type=leaf\n"
	945	"00\x0000\x00\t00\x00ref00\x00value:0\n"
	946	"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
947	"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
948	"11\x0044\x00\t11\x00ref00\x00value:4\n"
949	""
950	)
951	node = btree_index._LeafNode(node_bytes, 2, 2)
952	# We do direct access, or don't care about order, to leaf nodes most of
953	# the time, so a dict is useful:
954	self.assertEqual({
955	('00', '00'): ('value:0', ((), (('00', 'ref00'),))),
956	('00', '11'): ('value:1',
957	((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01')))),
958	('11', '33'): ('value:3',
959	((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
960	('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
961	}, node.keys)
962
3641.3.19 by John Arbash Meinel The flatten code now handles the no-ref-list case.	963	def assertFlattened(self, expected, key, value, refs):
3641.3.18 by John Arbash Meinel Start working on a compiled function for transforming	964	flat_key, flat_line = self.parse_btree._flatten_node(
3641.3.19 by John Arbash Meinel The flatten code now handles the no-ref-list case.	965	(None, key, value, refs), bool(refs))
3641.3.18 by John Arbash Meinel Start working on a compiled function for transforming	966	self.assertEqual('\x00'.join(key), flat_key)
	967	self.assertEqual(expected, flat_line)
	968
3641.3.19 by John Arbash Meinel The flatten code now handles the no-ref-list case.	969	def test__flatten_node(self):
	970	self.assertFlattened('key\0\0value\n', ('key',), 'value', [])
	971	self.assertFlattened('key\0tuple\0\0value str\n',
	972	('key', 'tuple'), 'value str', [])
	973	self.assertFlattened('key\0tuple\0triple\0\0value str\n',
	974	('key', 'tuple', 'triple'), 'value str', [])
	975	self.assertFlattened('k\0t\0s\0ref\0value str\n',
	976	('k', 't', 's'), 'value str', [[('ref',)]])
	977	self.assertFlattened('key\0tuple\0ref\0key\0value str\n',
	978	('key', 'tuple'), 'value str', [[('ref', 'key')]])
	979	self.assertFlattened("00\x0000\x00\t00\x00ref00\x00value:0\n",
	980	('00', '00'), 'value:0', ((), (('00', 'ref00'),)))
	981	self.assertFlattened(
	982	"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n",
	983	('00', '11'), 'value:1',
	984	((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01'))))
	985	self.assertFlattened(
	986	"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n",
	987	('11', '33'), 'value:3',
	988	((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22'))))
	989	self.assertFlattened(
	990	"11\x0044\x00\t11\x00ref00\x00value:4\n",
	991	('11', '44'), 'value:4', ((), (('11', 'ref00'),)))
3641.3.18 by John Arbash Meinel Start working on a compiled function for transforming	992
3641.3.1 by John Arbash Meinel Bring in the btree_index and chunk_writer code and their tests.	993
	994	class TestCompiledBtree(tests.TestCase):
	995
	996	def test_exists(self):
	997	# This is just to let the user know if they don't have the feature
	998	# available
	999	self.requireFeature(CompiledBtreeParserFeature)
	1000
	1001
	1002	class TestMultiBisectRight(tests.TestCase):
	1003
	1004	def assertMultiBisectRight(self, offsets, search_keys, fixed_keys):
	1005	self.assertEqual(offsets,
	1006	btree_index.BTreeGraphIndex._multi_bisect_right(
	1007	search_keys, fixed_keys))
	1008
	1009	def test_after(self):
	1010	self.assertMultiBisectRight([(1, ['b'])], ['b'], ['a'])
	1011	self.assertMultiBisectRight([(3, ['e', 'f', 'g'])],
	1012	['e', 'f', 'g'], ['a', 'b', 'c'])
	1013
	1014	def test_before(self):
	1015	self.assertMultiBisectRight([(0, ['a'])], ['a'], ['b'])
	1016	self.assertMultiBisectRight([(0, ['a', 'b', 'c', 'd'])],
	1017	['a', 'b', 'c', 'd'], ['e', 'f', 'g'])
	1018
	1019	def test_exact(self):
	1020	self.assertMultiBisectRight([(1, ['a'])], ['a'], ['a'])
	1021	self.assertMultiBisectRight([(1, ['a']), (2, ['b'])], ['a', 'b'], ['a', 'b'])
	1022	self.assertMultiBisectRight([(1, ['a']), (3, ['c'])],
	1023	['a', 'c'], ['a', 'b', 'c'])
	1024
	1025	def test_inbetween(self):
	1026	self.assertMultiBisectRight([(1, ['b'])], ['b'], ['a', 'c'])
	1027	self.assertMultiBisectRight([(1, ['b', 'c', 'd']), (2, ['f', 'g'])],
	1028	['b', 'c', 'd', 'f', 'g'], ['a', 'e', 'h'])
	1029
	1030	def test_mixed(self):
	1031	self.assertMultiBisectRight([(0, ['a', 'b']), (2, ['d', 'e']),
	1032	(4, ['g', 'h'])],
	1033	['a', 'b', 'd', 'e', 'g', 'h'],
	1034	['c', 'd', 'f', 'g'])
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1035
	1036
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1037	class TestExpandOffsets(tests.TestCase):
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1038
	1039	def make_index(self, size, recommended_pages=None):
	1040	"""Make an index with a generic size.
	1041
	1042	This doesn't actually create anything on disk, it just primes a
	1043	BTreeGraphIndex with the recommended information.
	1044	"""
	1045	index = btree_index.BTreeGraphIndex(get_transport('memory:///'),
	1046	'test-index', size=size)
	1047	if recommended_pages is not None:
	1048	index._recommended_pages = recommended_pages
	1049	return index
	1050
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1051	def set_cached_offsets(self, index, cached_offsets):
	1052	"""Monkeypatch to give a canned answer for _get_offsets_for...()."""
	1053	def _get_offsets_to_cached_pages():
	1054	cached = set(cached_offsets)
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1055	return cached
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1056	index._get_offsets_to_cached_pages = _get_offsets_to_cached_pages
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1057
	1058	def prepare_index(self, index, node_ref_lists, key_length, key_count,
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1059	row_lengths, cached_offsets):
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1060	"""Setup the BTreeGraphIndex with some pre-canned information."""
	1061	index.node_ref_lists = node_ref_lists
	1062	index._key_length = key_length
	1063	index._key_count = key_count
	1064	index._row_lengths = row_lengths
	1065	index._compute_row_offsets()
	1066	index._root_node = btree_index._InternalNode('internal\noffset=0\n')
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1067	self.set_cached_offsets(index, cached_offsets)
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1068
	1069	def make_100_node_index(self):
	1070	index = self.make_index(4096*100, 6)
3763.8.14 by John Arbash Meinel Add in a shortcut when we haven't cached much yet.	1071	# Consider we've already made a single request at the middle
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1072	self.prepare_index(index, node_ref_lists=0, key_length=1,
	1073	key_count=1000, row_lengths=[1, 99],
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1074	cached_offsets=[0, 50])
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1075	return index
	1076
3763.8.9 by John Arbash Meinel Finish up the algorithm to stay within a given layer.	1077	def make_1000_node_index(self):
	1078	index = self.make_index(4096*1000, 6)
3763.8.14 by John Arbash Meinel Add in a shortcut when we haven't cached much yet.	1079	# Pretend we've already made a single request in the middle
3763.8.9 by John Arbash Meinel Finish up the algorithm to stay within a given layer.	1080	self.prepare_index(index, node_ref_lists=0, key_length=1,
	1081	key_count=90000, row_lengths=[1, 9, 990],
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1082	cached_offsets=[0, 5, 500])
3763.8.9 by John Arbash Meinel Finish up the algorithm to stay within a given layer.	1083	return index
	1084
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1085	def assertNumPages(self, expected_pages, index, size):
	1086	index._size = size
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1087	self.assertEqual(expected_pages, index._compute_total_pages_in_index())
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1088
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1089	def assertExpandOffsets(self, expected, index, offsets):
	1090	self.assertEqual(expected, index._expand_offsets(offsets),
	1091	'We did not get the expected value after expanding'
	1092	' %s' % (offsets,))
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1093
	1094	def test_default_recommended_pages(self):
	1095	index = self.make_index(None)
	1096	# local transport recommends 4096 byte reads, which is 1 page
	1097	self.assertEqual(1, index._recommended_pages)
	1098
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1099	def test__compute_total_pages_in_index(self):
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1100	index = self.make_index(None)
	1101	self.assertNumPages(1, index, 1024)
	1102	self.assertNumPages(1, index, 4095)
	1103	self.assertNumPages(1, index, 4096)
	1104	self.assertNumPages(2, index, 4097)
	1105	self.assertNumPages(2, index, 8192)
	1106	self.assertNumPages(76, index, 4096*75 + 10)
	1107
3763.8.9 by John Arbash Meinel Finish up the algorithm to stay within a given layer.	1108	def test__find_layer_start_and_stop(self):
	1109	index = self.make_1000_node_index()
	1110	self.assertEqual((0, 1), index._find_layer_first_and_end(0))
	1111	self.assertEqual((1, 10), index._find_layer_first_and_end(1))
	1112	self.assertEqual((1, 10), index._find_layer_first_and_end(9))
	1113	self.assertEqual((10, 1000), index._find_layer_first_and_end(10))
	1114	self.assertEqual((10, 1000), index._find_layer_first_and_end(99))
	1115	self.assertEqual((10, 1000), index._find_layer_first_and_end(999))
	1116
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1117	def test_unknown_size(self):
	1118	# We should not expand if we don't know the file size
	1119	index = self.make_index(None, 10)
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1120	self.assertExpandOffsets([0], index, [0])
	1121	self.assertExpandOffsets([1, 4, 9], index, [1, 4, 9])
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1122
	1123	def test_more_than_recommended(self):
	1124	index = self.make_index(4096*100, 2)
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1125	self.assertExpandOffsets([1, 10], index, [1, 10])
	1126	self.assertExpandOffsets([1, 10, 20], index, [1, 10, 20])
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1127
	1128	def test_read_all_from_root(self):
	1129	index = self.make_index(4096*10, 20)
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1130	self.assertExpandOffsets(range(10), index, [0])
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1131
	1132	def test_read_all_when_cached(self):
	1133	# We've read enough that we can grab all the rest in a single request
	1134	index = self.make_index(4096*10, 5)
	1135	self.prepare_index(index, node_ref_lists=0, key_length=1,
	1136	key_count=1000, row_lengths=[1, 9],
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1137	cached_offsets=[0, 1, 2, 5, 6])
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1138	# It should fill the remaining nodes, regardless of the one requested
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1139	self.assertExpandOffsets([3, 4, 7, 8, 9], index, [3])
	1140	self.assertExpandOffsets([3, 4, 7, 8, 9], index, [8])
	1141	self.assertExpandOffsets([3, 4, 7, 8, 9], index, [9])
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1142
	1143	def test_no_root_node(self):
	1144	index = self.make_index(4096*10, 5)
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1145	self.assertExpandOffsets([0], index, [0])
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1146
	1147	def test_include_neighbors(self):
	1148	index = self.make_100_node_index()
	1149	# We expand in both directions, until we have at least 'recommended'
	1150	# pages
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1151	self.assertExpandOffsets([9, 10, 11, 12, 13, 14, 15], index, [12])
	1152	self.assertExpandOffsets([88, 89, 90, 91, 92, 93, 94], index, [91])
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1153	# If we hit an 'edge' we continue in the other direction
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1154	self.assertExpandOffsets([1, 2, 3, 4, 5, 6], index, [2])
	1155	self.assertExpandOffsets([94, 95, 96, 97, 98, 99], index, [98])
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1156
	1157	# Requesting many nodes will expand all locations equally
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1158	self.assertExpandOffsets([1, 2, 3, 80, 81, 82], index, [2, 81])
	1159	self.assertExpandOffsets([1, 2, 3, 9, 10, 11, 80, 81, 82], index,
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1160	[2, 10, 81])
	1161
3763.8.8 by John Arbash Meinel simple test of overlapped behavior	1162	def test_stop_at_cached(self):
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1163	index = self.make_100_node_index()
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1164	self.set_cached_offsets(index, [0, 10, 19])
	1165	self.assertExpandOffsets([11, 12, 13, 14, 15, 16], index, [11])
	1166	self.assertExpandOffsets([11, 12, 13, 14, 15, 16], index, [12])
	1167	self.assertExpandOffsets([12, 13, 14, 15, 16, 17, 18], index, [15])
	1168	self.assertExpandOffsets([13, 14, 15, 16, 17, 18], index, [16])
	1169	self.assertExpandOffsets([13, 14, 15, 16, 17, 18], index, [17])
	1170	self.assertExpandOffsets([13, 14, 15, 16, 17, 18], index, [18])
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1171
3763.8.8 by John Arbash Meinel simple test of overlapped behavior	1172	def test_cannot_fully_expand(self):
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1173	index = self.make_100_node_index()
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1174	self.set_cached_offsets(index, [0, 10, 12])
3763.8.7 by John Arbash Meinel A bit of doc updates, start putting in tests for current behavior.	1175	# We don't go into an endless loop if we are bound by cached nodes
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1176	self.assertExpandOffsets([11], index, [11])
3763.8.8 by John Arbash Meinel simple test of overlapped behavior	1177
	1178	def test_overlap(self):
	1179	index = self.make_100_node_index()
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1180	self.assertExpandOffsets([10, 11, 12, 13, 14, 15], index, [12, 13])
	1181	self.assertExpandOffsets([10, 11, 12, 13, 14, 15], index, [11, 14])
3763.8.9 by John Arbash Meinel Finish up the algorithm to stay within a given layer.	1182
	1183	def test_stay_within_layer(self):
	1184	index = self.make_1000_node_index()
	1185	# When expanding a request, we won't read nodes from the next layer
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1186	self.assertExpandOffsets([1, 2, 3, 4], index, [2])
	1187	self.assertExpandOffsets([6, 7, 8, 9], index, [6])
	1188	self.assertExpandOffsets([6, 7, 8, 9], index, [9])
	1189	self.assertExpandOffsets([10, 11, 12, 13, 14, 15], index, [10])
	1190	self.assertExpandOffsets([10, 11, 12, 13, 14, 15, 16], index, [13])
3763.8.9 by John Arbash Meinel Finish up the algorithm to stay within a given layer.	1191
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1192	self.set_cached_offsets(index, [0, 4, 12])
	1193	self.assertExpandOffsets([5, 6, 7, 8, 9], index, [7])
	1194	self.assertExpandOffsets([10, 11], index, [11])
3763.8.14 by John Arbash Meinel Add in a shortcut when we haven't cached much yet.	1195
	1196	def test_small_requests_unexpanded(self):
	1197	index = self.make_100_node_index()
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1198	self.set_cached_offsets(index, [0])
	1199	self.assertExpandOffsets([1], index, [1])
	1200	self.assertExpandOffsets([50], index, [50])
3763.8.14 by John Arbash Meinel Add in a shortcut when we haven't cached much yet.	1201	# If we request more than one node, then we'll expand
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1202	self.assertExpandOffsets([49, 50, 51, 59, 60, 61], index, [50, 60])
3763.8.14 by John Arbash Meinel Add in a shortcut when we haven't cached much yet.	1203
	1204	# The first pass does not expand
	1205	index = self.make_1000_node_index()
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1206	self.set_cached_offsets(index, [0])
	1207	self.assertExpandOffsets([1], index, [1])
	1208	self.set_cached_offsets(index, [0, 1])
	1209	self.assertExpandOffsets([100], index, [100])
	1210	self.set_cached_offsets(index, [0, 1, 100])
3763.8.14 by John Arbash Meinel Add in a shortcut when we haven't cached much yet.	1211	# But after the first depth, we will expand
3763.8.15 by John Arbash Meinel Review comments from Martin. Code clarity/variable name/docstring updates.	1212	self.assertExpandOffsets([2, 3, 4, 5, 6, 7], index, [2])
	1213	self.assertExpandOffsets([2, 3, 4, 5, 6, 7], index, [4])
	1214	self.set_cached_offsets(index, [0, 1, 2, 3, 4, 5, 6, 7, 100])
	1215	self.assertExpandOffsets([102, 103, 104, 105, 106, 107, 108], index,
	1216	[105])