~bzr-pqm/bzr/bzr.dev : contents of bzrlib/tests/test_btree

~bzr-pqm/bzr/bzr.dev : (revision 4149)

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