Rev 2633: Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. in http://people.ubuntu.com/~robertc/baz2.0/index
Robert Collins
robertc at robertcollins.net
Fri Jul 27 13:27:51 BST 2007
At http://people.ubuntu.com/~robertc/baz2.0/index
------------------------------------------------------------
revno: 2633
revision-id: robertc at robertcollins.net-20070727122746-99wyymjtkwcu51k6
parent: robertc at robertcollins.net-20070727074259-47dvq2n20vf0c79e
committer: Robert Collins <robertc at robertcollins.net>
branch nick: index
timestamp: Fri 2007-07-27 22:27:46 +1000
message:
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
modified:
bzrlib/index.py index.py-20070712131115-lolkarso50vjr64s-1
bzrlib/tests/test_index.py test_index.py-20070712131115-lolkarso50vjr64s-2
=== modified file 'bzrlib/index.py'
--- a/bzrlib/index.py 2007-07-27 07:42:59 +0000
+++ b/bzrlib/index.py 2007-07-27 12:27:46 +0000
@@ -56,15 +56,16 @@
VALUE := no-newline-no-null-bytes
"""
- def __init__(self, reference_lists=0):
+ def __init__(self, reference_lists=0, key_elements=1):
"""Create a GraphIndex builder.
:param reference_lists: The number of node references lists for each
entry.
+ :param key_elements: The number of bytestrings in each key.
"""
self.reference_lists = reference_lists
self._nodes = {}
- self._key_length = 1
+ self._key_length = key_elements
def _check_key(self, key):
"""Raise BadIndexKey if key is not a valid key for this index."""
@@ -72,9 +73,9 @@
raise errors.BadIndexKey(key)
if self._key_length != len(key):
raise errors.BadIndexKey(key)
- key = key[0]
- if not key or _whitespace_re.search(key) is not None:
- raise errors.BadIndexKey(key)
+ for element in key:
+ if not element or _whitespace_re.search(element) is not None:
+ raise errors.BadIndexKey(element)
def add_node(self, key, value, references=()):
"""Add a node to the index.
@@ -138,8 +139,10 @@
# date - saves reaccumulating on the second pass
key_offset_info.append((key, non_ref_bytes, total_references))
# key is literal, value is literal, there are 3 null's, 1 NL
- # key is variable length tuple,
+ # key is variable length tuple, \x00 between elements
non_ref_bytes += sum(len(element) for element in key)
+ if self._key_length > 1:
+ non_ref_bytes += self._key_length - 1
# value is literal bytes, there are 3 null's, 1 NL.
non_ref_bytes += len(value) + 3 + 1
# one byte for absent if set.
@@ -175,15 +178,15 @@
for reference in ref_list:
ref_addresses.append(format_string % key_addresses[reference])
flattened_references.append('\r'.join(ref_addresses))
- string_key = key[0]
+ string_key = '\x00'.join(key)
lines.append("%s\0%s\0%s\0%s\n" % (string_key, absent,
'\t'.join(flattened_references), value))
lines.append('\n')
result = StringIO(''.join(lines))
- #if expected_bytes and len(result.getvalue()) != expected_bytes:
- # raise errors.BzrError('Failed index creation. Internal error:'
- # ' mismatched output length and expected length: %d %d' %
- # (len(result.getvalue()), expected_bytes))
+ if expected_bytes and len(result.getvalue()) != expected_bytes:
+ raise errors.BzrError('Failed index creation. Internal error:'
+ ' mismatched output length and expected length: %d %d' %
+ (len(result.getvalue()), expected_bytes))
return StringIO(''.join(lines))
@@ -194,8 +197,8 @@
Each node has the same number of key reference lists. Each key reference
list can be empty or an arbitrary length. The value is an opaque NULL
terminated string without any newlines. The storage of the index is
- hidden in the interface: keys and key references are always bytestrings,
- never the internal representation (e.g. dictionary offsets).
+ hidden in the interface: keys and key references are always tuples of
+ bytestrings, never the internal representation (e.g. dictionary offsets).
It is presumed that the index will not be mutated - it is static data.
@@ -215,6 +218,7 @@
self._name = name
self._nodes = None
self._keys_by_offset = None
+ self._nodes_by_key = None
def _buffer_all(self):
"""Buffer all the index data.
@@ -228,15 +232,17 @@
self._keys_by_offset = {}
# ready-to-return key:value or key:value, node_ref_lists
self._nodes = {}
+ self._nodes_by_key = {}
trailers = 0
pos = stream.tell()
for line in stream.readlines():
if line == '\n':
trailers += 1
continue
- key, absent, references, value = line.split('\0')
+ elements = line.split('\0')
# keys are tuples
- key = (key, )
+ key = tuple(elements[:self._key_length])
+ absent, references, value = elements[-3:]
value = value[:-1] # remove the newline
ref_lists = []
for ref_string in references.split('\t'):
@@ -254,9 +260,25 @@
node_refs = []
for ref_list in references:
node_refs.append(tuple([self._keys_by_offset[ref][0] for ref in ref_list]))
- self._nodes[key] = (value, tuple(node_refs))
+ node_value = (value, tuple(node_refs))
else:
- self._nodes[key] = value
+ node_value = value
+ self._nodes[key] = node_value
+ if self._key_length > 1:
+ subkey = list(reversed(key[:-1]))
+ key_dict = self._nodes_by_key
+ if self.node_ref_lists:
+ key_value = key, node_value[0], node_value[1]
+ else:
+ key_value = key, node_value
+ # possibly should do this on-demand, but it seems likely it is
+ # always wanted
+ while len(subkey):
+ if subkey[-1] not in key_dict:
+ key_dict[subkey[-1]] = {}
+ key_dict = key_dict[subkey[-1]]
+ subkey.pop(-1)
+ key_dict[key[-1]] = key_value
self._keys = set(self._nodes)
if trailers != 1:
# there must be one line - the empty trailer line.
@@ -321,6 +343,75 @@
for key in keys:
yield key, self._nodes[key]
+ def iter_entries_prefix(self, keys):
+ """Iterate over keys within the index using prefix matching.
+
+ Prefix matching is applied within the tuple of a key, not to within
+ the bytestring of each key element. e.g. if you have the keys ('foo',
+ 'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
+ only the former key is returned.
+
+ :param keys: An iterable providing the key prefixes to be retrieved.
+ Each key prefix takes the form of a tuple the length of a key, but
+ with the last N elements 'None' rather than a regular bytestring.
+ The first element cannot be 'None'.
+ :return: An iterable as per iter_all_entries, but restricted to the
+ keys with a matching prefix to those supplied. No additional keys
+ will be returned, and every match that is in the index will be
+ returned.
+ """
+ keys = set(keys)
+ if not keys:
+ return
+ # load data - also finds key lengths
+ if self._nodes is None:
+ self._buffer_all()
+ if self._key_length == 1:
+ for key in keys:
+ # sanity check
+ if key[0] is None:
+ raise errors.BadIndexKey(key)
+ if len(key) != self._key_length:
+ raise errors.BadIndexKey(key)
+ if self.node_ref_lists:
+ value, node_refs = self._nodes[key]
+ yield key, value, node_refs
+ else:
+ yield key, self._nodes[key]
+ return
+ for key in keys:
+ # sanity check
+ if key[0] is None:
+ raise errors.BadIndexKey(key)
+ if len(key) != self._key_length:
+ raise errors.BadIndexKey(key)
+ # find what it refers to:
+ key_dict = self._nodes_by_key
+ elements = list(key)
+ # find the subdict to return
+ try:
+ while len(elements) and elements[0] is not None:
+ key_dict = key_dict[elements[0]]
+ elements.pop(0)
+ except KeyError:
+ # a non-existant lookup.
+ continue
+ if len(elements):
+ dicts = [key_dict]
+ while dicts:
+ key_dict = dicts.pop(-1)
+ # can't be empty or would not exist
+ item, value = key_dict.iteritems().next()
+ if type(value) == dict:
+ # push keys
+ dicts.extend(key_dict.itervalues())
+ else:
+ # yield keys
+ for value in key_dict.itervalues():
+ yield value
+ else:
+ yield key_dict
+
def _signature(self):
"""The file signature for this index type."""
return _SIGNATURE
@@ -396,6 +487,37 @@
keys.remove(node[0])
yield node
+ def iter_entries_prefix(self, keys):
+ """Iterate over keys within the index using prefix matching.
+
+ Duplicate keys across child indices are presumed to have the same
+ value and are only reported once.
+
+ Prefix matching is applied within the tuple of a key, not to within
+ the bytestring of each key element. e.g. if you have the keys ('foo',
+ 'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
+ only the former key is returned.
+
+ :param keys: An iterable providing the key prefixes to be retrieved.
+ Each key prefix takes the form of a tuple the length of a key, but
+ with the last N elements 'None' rather than a regular bytestring.
+ The first element cannot be 'None'.
+ :return: An iterable as per iter_all_entries, but restricted to the
+ keys with a matching prefix to those supplied. No additional keys
+ will be returned, and every match that is in the index will be
+ returned.
+ """
+ keys = set(keys)
+ if not keys:
+ return
+ seen_keys = set()
+ for index in self._indices:
+ for node in index.iter_entries_prefix(keys):
+ if node[0] in seen_keys:
+ continue
+ seen_keys.add(node[0])
+ yield node
+
def validate(self):
"""Validate that everything in the index can be accessed."""
for index in self._indices:
=== modified file 'bzrlib/tests/test_index.py'
--- a/bzrlib/tests/test_index.py 2007-07-27 07:42:59 +0000
+++ b/bzrlib/tests/test_index.py 2007-07-27 12:27:46 +0000
@@ -29,6 +29,12 @@
contents = stream.read()
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n\n", contents)
+ def test_build_index_empty_two_element_keys(self):
+ builder = GraphIndexBuilder(key_elements=2)
+ stream = builder.finish()
+ contents = stream.read()
+ self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\n\n", contents)
+
def test_build_index_one_reference_list_empty(self):
builder = GraphIndexBuilder(reference_lists=1)
stream = builder.finish()
@@ -57,6 +63,14 @@
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n"
"akey\x00\x00\x00data\n\n", contents)
+ def test_build_index_one_node_2_element_keys(self):
+ builder = GraphIndexBuilder(key_elements=2)
+ builder.add_node(('akey', 'secondpart'), 'data')
+ stream = builder.finish()
+ contents = stream.read()
+ self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\n"
+ "akey\x00secondpart\x00\x00\x00data\n\n", contents)
+
def test_add_node_empty_value(self):
builder = GraphIndexBuilder()
builder.add_node(('akey', ), '')
@@ -65,7 +79,7 @@
self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=1\n"
"akey\x00\x00\x00\n\n", contents)
- def test_build_index_two_nodes_sorted(self):
+ def test_build_index_nodes_sorted(self):
# the highest sorted node comes first.
builder = GraphIndexBuilder()
# use three to have a good chance of glitching dictionary hash
@@ -82,6 +96,35 @@
"2002\x00\x00\x00data\n"
"\n", contents)
+ def test_build_index_2_element_key_nodes_sorted(self):
+ # multiple element keys are sorted first-key, second-key.
+ builder = GraphIndexBuilder(key_elements=2)
+ # use three values of each key element, to have a good chance of
+ # glitching dictionary hash lookups etc. Insert in randomish order that
+ # is not correct and not the reverse of the correct order.
+ builder.add_node(('2002', '2002'), 'data')
+ builder.add_node(('2002', '2000'), 'data')
+ builder.add_node(('2002', '2001'), 'data')
+ builder.add_node(('2000', '2002'), 'data')
+ builder.add_node(('2000', '2000'), 'data')
+ builder.add_node(('2000', '2001'), 'data')
+ builder.add_node(('2001', '2002'), 'data')
+ builder.add_node(('2001', '2000'), 'data')
+ builder.add_node(('2001', '2001'), 'data')
+ stream = builder.finish()
+ contents = stream.read()
+ self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\nkey_elements=2\n"
+ "2000\x002000\x00\x00\x00data\n"
+ "2000\x002001\x00\x00\x00data\n"
+ "2000\x002002\x00\x00\x00data\n"
+ "2001\x002000\x00\x00\x00data\n"
+ "2001\x002001\x00\x00\x00data\n"
+ "2001\x002002\x00\x00\x00data\n"
+ "2002\x002000\x00\x00\x00data\n"
+ "2002\x002001\x00\x00\x00data\n"
+ "2002\x002002\x00\x00\x00data\n"
+ "\n", contents)
+
def test_build_index_reference_lists_are_included_one(self):
builder = GraphIndexBuilder(reference_lists=1)
builder.add_node(('key', ), 'data', ([], ))
@@ -91,6 +134,15 @@
"key\x00\x00\x00data\n"
"\n", contents)
+ def test_build_index_reference_lists_with_2_element_keys(self):
+ builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
+ builder.add_node(('key', 'key2'), 'data', ([], ))
+ stream = builder.finish()
+ contents = stream.read()
+ self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\nkey_elements=2\n"
+ "key\x00key2\x00\x00\x00data\n"
+ "\n", contents)
+
def test_build_index_reference_lists_are_included_two(self):
builder = GraphIndexBuilder(reference_lists=2)
builder.add_node(('key', ), 'data', ([], []))
@@ -194,6 +246,11 @@
# too long
self.assertRaises(errors.BadIndexKey, builder.add_node,
('primary', 'secondary'), 'data')
+ # secondary key elements get checked too:
+ builder = GraphIndexBuilder(key_elements=2)
+ for bad_char in '\t\n\x0b\x0c\r\x00 ':
+ self.assertRaises(errors.BadIndexKey, builder.add_node,
+ ('prefix', 'a%skey' % bad_char), 'data')
def test_add_node_bad_data(self):
builder = GraphIndexBuilder()
@@ -250,16 +307,27 @@
self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node, ('key', ),
'data')
+ def test_add_duplicate_key_2_elements(self):
+ builder = GraphIndexBuilder(key_elements=2)
+ builder.add_node(('key', 'key'), 'data')
+ self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node,
+ ('key', 'key'), 'data')
+
def test_add_key_after_referencing_key(self):
builder = GraphIndexBuilder(reference_lists=1)
builder.add_node(('key', ), 'data', ([('reference', )], ))
builder.add_node(('reference', ), 'data', ([],))
+ def test_add_key_after_referencing_key_2_elements(self):
+ builder = GraphIndexBuilder(reference_lists=1, key_elements=2)
+ builder.add_node(('k', 'ey'), 'data', ([('reference', 'tokey')], ))
+ builder.add_node(('reference', 'tokey'), 'data', ([],))
+
class TestGraphIndex(TestCaseWithMemoryTransport):
- def make_index(self, ref_lists=0, nodes=[]):
- builder = GraphIndexBuilder(ref_lists)
+ def make_index(self, ref_lists=0, key_elements=1, nodes=[]):
+ builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
for node, value, references in nodes:
builder.add_node(node, value, references)
stream = builder.finish()
@@ -281,6 +349,12 @@
self.assertEqual([(('name', ), 'data')],
list(index.iter_all_entries()))
+ def test_iter_all_entries_simple_2_elements(self):
+ index = self.make_index(key_elements=2,
+ nodes=[(('name', 'surname'), 'data', ())])
+ self.assertEqual([(('name', 'surname'), 'data')],
+ list(index.iter_all_entries()))
+
def test_iter_all_entries_references_resolved(self):
index = self.make_index(1, nodes=[
(('name', ), 'data', ([('ref', )], )),
@@ -298,6 +372,15 @@
set(index.iter_entries([('name', )])))
self.assertEqual([], list(index.iter_entries([('ref', )])))
+ def test_iteration_absent_skipped_2_element_keys(self):
+ index = self.make_index(1, key_elements=2, nodes=[
+ (('name', 'fin'), 'data', ([('ref', 'erence')], ))])
+ self.assertEqual(set([(('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
+ set(index.iter_all_entries()))
+ self.assertEqual(set([(('name', 'fin'), 'data', ((('ref', 'erence'),),))]),
+ set(index.iter_entries([('name', 'fin')])))
+ self.assertEqual([], list(index.iter_entries([('ref', 'erence')])))
+
def test_iter_all_keys(self):
index = self.make_index(1, nodes=[
(('name', ), 'data', ([('ref', )], )),
@@ -314,6 +397,61 @@
index = self.make_index()
self.assertEqual([], list(index.iter_entries([('a', )])))
+ def test_iter_key_prefix_1_element_key_None(self):
+ index = self.make_index()
+ self.assertRaises(errors.BadIndexKey, list,
+ index.iter_entries_prefix([(None, )]))
+
+ def test_iter_key_prefix_wrong_length(self):
+ index = self.make_index()
+ self.assertRaises(errors.BadIndexKey, list,
+ index.iter_entries_prefix([('foo', None)]))
+ index = self.make_index(key_elements=2)
+ self.assertRaises(errors.BadIndexKey, list,
+ index.iter_entries_prefix([('foo', )]))
+ self.assertRaises(errors.BadIndexKey, list,
+ index.iter_entries_prefix([('foo', None, None)]))
+
+ def test_iter_key_prefix_1_key_element_no_refs(self):
+ index = self.make_index( nodes=[
+ (('name', ), 'data', ()),
+ (('ref', ), 'refdata', ())])
+ self.assertEqual(set([(('name', ), 'data'),
+ (('ref', ), 'refdata')]),
+ set(index.iter_entries_prefix([('name', ), ('ref', )])))
+
+ def test_iter_key_prefix_1_key_element_refs(self):
+ index = self.make_index(1, nodes=[
+ (('name', ), 'data', ([('ref', )], )),
+ (('ref', ), 'refdata', ([], ))])
+ self.assertEqual(set([(('name', ), 'data', ((('ref',),),)),
+ (('ref', ), 'refdata', ((), ))]),
+ set(index.iter_entries_prefix([('name', ), ('ref', )])))
+
+ def test_iter_key_prefix_2_key_element_no_refs(self):
+ index = self.make_index(key_elements=2, nodes=[
+ (('name', 'fin1'), 'data', ()),
+ (('name', 'fin2'), 'beta', ()),
+ (('ref', 'erence'), 'refdata', ())])
+ self.assertEqual(set([(('name', 'fin1'), 'data'),
+ (('ref', 'erence'), 'refdata')]),
+ set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
+ self.assertEqual(set([(('name', 'fin1'), 'data'),
+ (('name', 'fin2'), 'beta')]),
+ set(index.iter_entries_prefix([('name', None)])))
+
+ def test_iter_key_prefix_2_key_element_refs(self):
+ index = self.make_index(1, key_elements=2, nodes=[
+ (('name', 'fin1'), 'data', ([('ref', 'erence')], )),
+ (('name', 'fin2'), 'beta', ([], )),
+ (('ref', 'erence'), 'refdata', ([], ))])
+ self.assertEqual(set([(('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
+ (('ref', 'erence'), 'refdata', ((), ))]),
+ set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
+ self.assertEqual(set([(('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
+ (('name', 'fin2'), 'beta', ((), ))]),
+ set(index.iter_entries_prefix([('name', None)])))
+
def test_validate_bad_index_errors(self):
trans = self.get_transport()
trans.put_bytes('name', "not an index\n")
@@ -338,7 +476,7 @@
self.assertRaises(errors.BadIndexData, index.validate)
def test_validate_missing_end_line_nonempty(self):
- index = self.make_index(2, [(('key', ), '', ([], []))])
+ index = self.make_index(2, nodes=[(('key', ), '', ([], []))])
trans = self.get_transport()
content = trans.get_bytes('index')
# truncate the last byte
@@ -356,8 +494,8 @@
class TestCombinedGraphIndex(TestCaseWithMemoryTransport):
- def make_index(self, name, ref_lists=0, nodes=[]):
- builder = GraphIndexBuilder(ref_lists)
+ def make_index(self, name, ref_lists=0, key_elements=1, nodes=[]):
+ builder = GraphIndexBuilder(ref_lists, key_elements=key_elements)
for node, value, references in nodes:
builder.add_node(node, value, references)
stream = builder.finish()
@@ -413,6 +551,20 @@
self.assertEqual([(('name', ), 'data')],
list(index.iter_all_entries()))
+ def test_iter_key_prefix_2_key_element_refs(self):
+ index1 = self.make_index('1', 1, key_elements=2, nodes=[
+ (('name', 'fin1'), 'data', ([('ref', 'erence')], ))])
+ index2 = self.make_index('2', 1, key_elements=2, nodes=[
+ (('name', 'fin2'), 'beta', ([], )),
+ (('ref', 'erence'), 'refdata', ([], ))])
+ index = CombinedGraphIndex([index1, index2])
+ self.assertEqual(set([(('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
+ (('ref', 'erence'), 'refdata', ((), ))]),
+ set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
+ self.assertEqual(set([(('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
+ (('name', 'fin2'), 'beta', ((), ))]),
+ set(index.iter_entries_prefix([('name', None)])))
+
def test_iter_nothing_empty(self):
index = CombinedGraphIndex([])
self.assertEqual([], list(index.iter_entries([])))
More information about the bazaar-commits
mailing list