1
# Copyright (C) 2007 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
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.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
"""Indexing facilities."""
23
'GraphIndexPrefixAdapter',
27
from cStringIO import StringIO
30
from bzrlib import errors
32
_OPTION_KEY_ELEMENTS = "key_elements="
33
_OPTION_NODE_REFS = "node_ref_lists="
34
_SIGNATURE = "Bazaar Graph Index 1\n"
37
_whitespace_re = re.compile('[\t\n\x0b\x0c\r\x00 ]')
38
_newline_null_re = re.compile('[\n\0]')
41
class GraphIndexBuilder(object):
42
"""A builder that can build a GraphIndex.
44
The resulting graph has the structure:
46
_SIGNATURE OPTIONS NODES NEWLINE
47
_SIGNATURE := 'Bazaar Graph Index 1' NEWLINE
48
OPTIONS := 'node_ref_lists=' DIGITS NEWLINE
50
NODE := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
51
KEY := Not-whitespace-utf8
53
REFERENCES := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
54
REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
55
REFERENCE := DIGITS ; digits is the byte offset in the index of the
57
VALUE := no-newline-no-null-bytes
60
def __init__(self, reference_lists=0, key_elements=1):
61
"""Create a GraphIndex builder.
63
:param reference_lists: The number of node references lists for each
65
:param key_elements: The number of bytestrings in each key.
67
self.reference_lists = reference_lists
69
self._nodes_by_key = {}
70
self._key_length = key_elements
72
def _check_key(self, key):
73
"""Raise BadIndexKey if key is not a valid key for this index."""
74
if type(key) != tuple:
75
raise errors.BadIndexKey(key)
76
if self._key_length != len(key):
77
raise errors.BadIndexKey(key)
79
if not element or _whitespace_re.search(element) is not None:
80
raise errors.BadIndexKey(element)
82
def add_node(self, key, value, references=()):
83
"""Add a node to the index.
85
:param key: The key. keys are non-empty tuples containing
86
as many whitespace-free utf8 bytestrings as the key length
87
defined for this index.
88
:param references: An iterable of iterables of keys. Each is a
89
reference to another key.
90
:param value: The value to associate with the key. It may be any
91
bytes as long as it does not contain \0 or \n.
94
if _newline_null_re.search(value) is not None:
95
raise errors.BadIndexValue(value)
96
if len(references) != self.reference_lists:
97
raise errors.BadIndexValue(references)
99
for reference_list in references:
100
for reference in reference_list:
101
self._check_key(reference)
102
if reference not in self._nodes:
103
self._nodes[reference] = ('a', (), '')
104
node_refs.append(tuple(reference_list))
105
if key in self._nodes and self._nodes[key][0] == '':
106
raise errors.BadIndexDuplicateKey(key, self)
107
self._nodes[key] = ('', tuple(node_refs), value)
108
if self._key_length > 1:
109
key_dict = self._nodes_by_key
110
if self.reference_lists:
111
key_value = key, value, tuple(node_refs)
113
key_value = key, value
114
# possibly should do this on-demand, but it seems likely it is
116
# For a key of (foo, bar, baz) create
117
# _nodes_by_key[foo][bar][baz] = key_value
118
for subkey in key[:-1]:
119
key_dict = key_dict.setdefault(subkey, {})
120
key_dict[key[-1]] = key_value
124
lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
125
lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
126
prefix_length = sum(len(x) for x in lines)
127
# references are byte offsets. To avoid having to do nasty
128
# polynomial work to resolve offsets (references to later in the
129
# file cannot be determined until all the inbetween references have
130
# been calculated too) we pad the offsets with 0's to make them be
131
# of consistent length. Using binary offsets would break the trivial
133
# to calculate the width of zero's needed we do three passes:
134
# one to gather all the non-reference data and the number of references.
135
# one to pad all the data with reference-length and determine entry
139
# forward sorted by key. In future we may consider topological sorting,
140
# at the cost of table scans for direct lookup, or a second index for
142
nodes = sorted(self._nodes.items())
143
# if we do not prepass, we don't know how long it will be up front.
144
expected_bytes = None
145
# we only need to pre-pass if we have reference lists at all.
146
if self.reference_lists:
148
non_ref_bytes = prefix_length
150
# TODO use simple multiplication for the constants in this loop.
151
for key, (absent, references, value) in nodes:
152
# record the offset known *so far* for this key:
153
# the non reference bytes to date, and the total references to
154
# date - saves reaccumulating on the second pass
155
key_offset_info.append((key, non_ref_bytes, total_references))
156
# key is literal, value is literal, there are 3 null's, 1 NL
157
# key is variable length tuple, \x00 between elements
158
non_ref_bytes += sum(len(element) for element in key)
159
if self._key_length > 1:
160
non_ref_bytes += self._key_length - 1
161
# value is literal bytes, there are 3 null's, 1 NL.
162
non_ref_bytes += len(value) + 3 + 1
163
# one byte for absent if set.
166
elif self.reference_lists:
167
# (ref_lists -1) tabs
168
non_ref_bytes += self.reference_lists - 1
169
# (ref-1 cr's per ref_list)
170
for ref_list in references:
171
# how many references across the whole file?
172
total_references += len(ref_list)
173
# accrue reference separators
175
non_ref_bytes += len(ref_list) - 1
176
# how many digits are needed to represent the total byte count?
178
possible_total_bytes = non_ref_bytes + total_references*digits
179
while 10 ** digits < possible_total_bytes:
181
possible_total_bytes = non_ref_bytes + total_references*digits
182
expected_bytes = possible_total_bytes + 1 # terminating newline
183
# resolve key addresses.
185
for key, non_ref_bytes, total_references in key_offset_info:
186
key_addresses[key] = non_ref_bytes + total_references*digits
188
format_string = '%%0%sd' % digits
189
for key, (absent, references, value) in nodes:
190
flattened_references = []
191
for ref_list in references:
193
for reference in ref_list:
194
ref_addresses.append(format_string % key_addresses[reference])
195
flattened_references.append('\r'.join(ref_addresses))
196
string_key = '\x00'.join(key)
197
lines.append("%s\x00%s\x00%s\x00%s\n" % (string_key, absent,
198
'\t'.join(flattened_references), value))
200
result = StringIO(''.join(lines))
201
if expected_bytes and len(result.getvalue()) != expected_bytes:
202
raise errors.BzrError('Failed index creation. Internal error:'
203
' mismatched output length and expected length: %d %d' %
204
(len(result.getvalue()), expected_bytes))
205
return StringIO(''.join(lines))
208
class GraphIndex(object):
209
"""An index for data with embedded graphs.
211
The index maps keys to a list of key reference lists, and a value.
212
Each node has the same number of key reference lists. Each key reference
213
list can be empty or an arbitrary length. The value is an opaque NULL
214
terminated string without any newlines. The storage of the index is
215
hidden in the interface: keys and key references are always tuples of
216
bytestrings, never the internal representation (e.g. dictionary offsets).
218
It is presumed that the index will not be mutated - it is static data.
220
Successive iter_all_entries calls will read the entire index each time.
221
Additionally, iter_entries calls will read the index linearly until the
222
desired keys are found. XXX: This must be fixed before the index is
223
suitable for production use. :XXX
226
def __init__(self, transport, name):
227
"""Open an index called name on transport.
229
:param transport: A bzrlib.transport.Transport.
230
:param name: A path to provide to transport API calls.
232
self._transport = transport
235
self._keys_by_offset = None
236
self._nodes_by_key = None
238
def _buffer_all(self):
239
"""Buffer all the index data.
241
Mutates self._nodes and self.keys_by_offset.
243
stream = self._transport.get(self._name)
244
self._read_prefix(stream)
245
expected_elements = 3 + self._key_length
247
# raw data keyed by offset
248
self._keys_by_offset = {}
249
# ready-to-return key:value or key:value, node_ref_lists
251
self._nodes_by_key = {}
254
for line in stream.readlines():
258
elements = line.split('\0')
259
if len(elements) != expected_elements:
260
raise errors.BadIndexData(self)
262
key = tuple(elements[:self._key_length])
263
absent, references, value = elements[-3:]
264
value = value[:-1] # remove the newline
266
for ref_string in references.split('\t'):
267
ref_lists.append(tuple([
268
int(ref) for ref in ref_string.split('\r') if ref
270
ref_lists = tuple(ref_lists)
271
self._keys_by_offset[pos] = (key, absent, ref_lists, value)
273
for key, absent, references, value in self._keys_by_offset.itervalues():
276
# resolve references:
277
if self.node_ref_lists:
279
for ref_list in references:
280
node_refs.append(tuple([self._keys_by_offset[ref][0] for ref in ref_list]))
281
node_value = (value, tuple(node_refs))
284
self._nodes[key] = node_value
285
if self._key_length > 1:
286
subkey = list(reversed(key[:-1]))
287
key_dict = self._nodes_by_key
288
if self.node_ref_lists:
289
key_value = key, node_value[0], node_value[1]
291
key_value = key, node_value
292
# possibly should do this on-demand, but it seems likely it is
294
# For a key of (foo, bar, baz) create
295
# _nodes_by_key[foo][bar][baz] = key_value
296
for subkey in key[:-1]:
297
key_dict = key_dict.setdefault(subkey, {})
298
key_dict[key[-1]] = key_value
299
self._keys = set(self._nodes)
301
# there must be one line - the empty trailer line.
302
raise errors.BadIndexData(self)
304
def iter_all_entries(self):
305
"""Iterate over all keys within the index.
307
:return: An iterable of (key, value) or (key, value, reference_lists).
308
The former tuple is used when there are no reference lists in the
309
index, making the API compatible with simple key:value index types.
310
There is no defined order for the result iteration - it will be in
311
the most efficient order for the index.
313
if self._nodes is None:
315
if self.node_ref_lists:
316
for key, (value, node_ref_lists) in self._nodes.iteritems():
317
yield self, key, value, node_ref_lists
319
for key, value in self._nodes.iteritems():
320
yield self, key, value
322
def _read_prefix(self, stream):
323
signature = stream.read(len(self._signature()))
324
if not signature == self._signature():
325
raise errors.BadIndexFormatSignature(self._name, GraphIndex)
326
options_line = stream.readline()
327
if not options_line.startswith(_OPTION_NODE_REFS):
328
raise errors.BadIndexOptions(self)
330
self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):-1])
332
raise errors.BadIndexOptions(self)
333
options_line = stream.readline()
334
if not options_line.startswith(_OPTION_KEY_ELEMENTS):
335
raise errors.BadIndexOptions(self)
337
self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):-1])
339
raise errors.BadIndexOptions(self)
341
def iter_entries(self, keys):
342
"""Iterate over keys within the index.
344
:param keys: An iterable providing the keys to be retrieved.
345
:return: An iterable as per iter_all_entries, but restricted to the
346
keys supplied. No additional keys will be returned, and every
347
key supplied that is in the index will be returned.
352
if self._nodes is None:
354
keys = keys.intersection(self._keys)
355
if self.node_ref_lists:
357
value, node_refs = self._nodes[key]
358
yield self, key, value, node_refs
361
yield self, key, self._nodes[key]
363
def iter_entries_prefix(self, keys):
364
"""Iterate over keys within the index using prefix matching.
366
Prefix matching is applied within the tuple of a key, not to within
367
the bytestring of each key element. e.g. if you have the keys ('foo',
368
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
369
only the former key is returned.
371
:param keys: An iterable providing the key prefixes to be retrieved.
372
Each key prefix takes the form of a tuple the length of a key, but
373
with the last N elements 'None' rather than a regular bytestring.
374
The first element cannot be 'None'.
375
:return: An iterable as per iter_all_entries, but restricted to the
376
keys with a matching prefix to those supplied. No additional keys
377
will be returned, and every match that is in the index will be
383
# load data - also finds key lengths
384
if self._nodes is None:
386
if self._key_length == 1:
390
raise errors.BadIndexKey(key)
391
if len(key) != self._key_length:
392
raise errors.BadIndexKey(key)
393
if self.node_ref_lists:
394
value, node_refs = self._nodes[key]
395
yield self, key, value, node_refs
397
yield self, key, self._nodes[key]
402
raise errors.BadIndexKey(key)
403
if len(key) != self._key_length:
404
raise errors.BadIndexKey(key)
405
# find what it refers to:
406
key_dict = self._nodes_by_key
408
# find the subdict whose contents should be returned.
410
while len(elements) and elements[0] is not None:
411
key_dict = key_dict[elements[0]]
414
# a non-existant lookup.
419
key_dict = dicts.pop(-1)
420
# can't be empty or would not exist
421
item, value = key_dict.iteritems().next()
422
if type(value) == dict:
424
dicts.extend(key_dict.itervalues())
427
for value in key_dict.itervalues():
428
# each value is the key:value:node refs tuple
430
yield (self, ) + value
432
# the last thing looked up was a terminal element
433
yield (self, ) + key_dict
435
def _signature(self):
436
"""The file signature for this index type."""
440
"""Validate that everything in the index can be accessed."""
441
# iter_all validates completely at the moment, so just do that.
442
for node in self.iter_all_entries():
446
class CombinedGraphIndex(object):
447
"""A GraphIndex made up from smaller GraphIndices.
449
The backing indices must implement GraphIndex, and are presumed to be
452
Queries against the combined index will be made against the first index,
453
and then the second and so on. The order of index's can thus influence
454
performance significantly. For example, if one index is on local disk and a
455
second on a remote server, the local disk index should be before the other
459
def __init__(self, indices):
460
"""Create a CombinedGraphIndex backed by indices.
462
:param indices: An ordered list of indices to query for data.
464
self._indices = indices
466
def insert_index(self, pos, index):
467
"""Insert a new index in the list of indices to query.
469
:param pos: The position to insert the index.
470
:param index: The index to insert.
472
self._indices.insert(pos, index)
474
def iter_all_entries(self):
475
"""Iterate over all keys within the index
477
Duplicate keys across child indices are presumed to have the same
478
value and are only reported once.
480
:return: An iterable of (key, reference_lists, value). There is no
481
defined order for the result iteration - it will be in the most
482
efficient order for the index.
485
for index in self._indices:
486
for node in index.iter_all_entries():
487
if node[1] not in seen_keys:
489
seen_keys.add(node[1])
491
def iter_entries(self, keys):
492
"""Iterate over keys within the index.
494
Duplicate keys across child indices are presumed to have the same
495
value and are only reported once.
497
:param keys: An iterable providing the keys to be retrieved.
498
:return: An iterable of (key, reference_lists, value). There is no
499
defined order for the result iteration - it will be in the most
500
efficient order for the index.
503
for index in self._indices:
506
for node in index.iter_entries(keys):
510
def iter_entries_prefix(self, keys):
511
"""Iterate over keys within the index using prefix matching.
513
Duplicate keys across child indices are presumed to have the same
514
value and are only reported once.
516
Prefix matching is applied within the tuple of a key, not to within
517
the bytestring of each key element. e.g. if you have the keys ('foo',
518
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
519
only the former key is returned.
521
:param keys: An iterable providing the key prefixes to be retrieved.
522
Each key prefix takes the form of a tuple the length of a key, but
523
with the last N elements 'None' rather than a regular bytestring.
524
The first element cannot be 'None'.
525
:return: An iterable as per iter_all_entries, but restricted to the
526
keys with a matching prefix to those supplied. No additional keys
527
will be returned, and every match that is in the index will be
534
for index in self._indices:
535
for node in index.iter_entries_prefix(keys):
536
if node[1] in seen_keys:
538
seen_keys.add(node[1])
542
"""Validate that everything in the index can be accessed."""
543
for index in self._indices:
547
class InMemoryGraphIndex(GraphIndexBuilder):
548
"""A GraphIndex which operates entirely out of memory and is mutable.
550
This is designed to allow the accumulation of GraphIndex entries during a
551
single write operation, where the accumulated entries need to be immediately
552
available - for example via a CombinedGraphIndex.
555
def add_nodes(self, nodes):
556
"""Add nodes to the index.
558
:param nodes: An iterable of (key, node_refs, value) entries to add.
560
if self.reference_lists:
561
for (key, value, node_refs) in nodes:
562
self.add_node(key, value, node_refs)
564
for (key, value) in nodes:
565
self.add_node(key, value)
567
def iter_all_entries(self):
568
"""Iterate over all keys within the index
570
:return: An iterable of (key, reference_lists, value). There is no
571
defined order for the result iteration - it will be in the most
572
efficient order for the index (in this case dictionary hash order).
574
if self.reference_lists:
575
for key, (absent, references, value) in self._nodes.iteritems():
577
yield self, key, value, references
579
for key, (absent, references, value) in self._nodes.iteritems():
581
yield self, key, value
583
def iter_entries(self, keys):
584
"""Iterate over keys within the index.
586
:param keys: An iterable providing the keys to be retrieved.
587
:return: An iterable of (key, reference_lists, value). There is no
588
defined order for the result iteration - it will be in the most
589
efficient order for the index (keys iteration order in this case).
592
if self.reference_lists:
593
for key in keys.intersection(self._nodes):
594
node = self._nodes[key]
596
yield self, key, node[2], node[1]
598
for key in keys.intersection(self._nodes):
599
node = self._nodes[key]
601
yield self, key, node[2]
603
def iter_entries_prefix(self, keys):
604
"""Iterate over keys within the index using prefix matching.
606
Prefix matching is applied within the tuple of a key, not to within
607
the bytestring of each key element. e.g. if you have the keys ('foo',
608
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
609
only the former key is returned.
611
:param keys: An iterable providing the key prefixes to be retrieved.
612
Each key prefix takes the form of a tuple the length of a key, but
613
with the last N elements 'None' rather than a regular bytestring.
614
The first element cannot be 'None'.
615
:return: An iterable as per iter_all_entries, but restricted to the
616
keys with a matching prefix to those supplied. No additional keys
617
will be returned, and every match that is in the index will be
620
# XXX: To much duplication with the GraphIndex class; consider finding
621
# a good place to pull out the actual common logic.
625
if self._key_length == 1:
629
raise errors.BadIndexKey(key)
630
if len(key) != self._key_length:
631
raise errors.BadIndexKey(key)
632
node = self._nodes[key]
635
if self.reference_lists:
636
yield self, key, node[2], node[1]
638
yield self ,key, node[2]
643
raise errors.BadIndexKey(key)
644
if len(key) != self._key_length:
645
raise errors.BadIndexKey(key)
646
# find what it refers to:
647
key_dict = self._nodes_by_key
649
# find the subdict to return
651
while len(elements) and elements[0] is not None:
652
key_dict = key_dict[elements[0]]
655
# a non-existant lookup.
660
key_dict = dicts.pop(-1)
661
# can't be empty or would not exist
662
item, value = key_dict.iteritems().next()
663
if type(value) == dict:
665
dicts.extend(key_dict.itervalues())
668
for value in key_dict.itervalues():
669
yield (self, ) + value
671
yield (self, ) + key_dict
674
"""In memory index's have no known corruption at the moment."""
677
class GraphIndexPrefixAdapter(object):
678
"""An adapter between GraphIndex with different key lengths.
680
Queries against this will emit queries against the adapted Graph with the
681
prefix added, queries for all items use iter_entries_prefix. The returned
682
nodes will have their keys and node references adjusted to remove the
683
prefix. Finally, an add_nodes_callback can be supplied - when called the
684
nodes and references being added will have prefix prepended.
687
def __init__(self, adapted, prefix, missing_key_length, add_nodes_callback=None):
688
"""Construct an adapter against adapted with prefix."""
689
self.adapted = adapted
690
self.prefix = prefix + (None,)*missing_key_length
691
self.prefix_key = prefix
692
self.prefix_len = len(prefix)
693
self.add_nodes_callback = add_nodes_callback
695
def add_nodes(self, nodes):
696
"""Add nodes to the index.
698
:param nodes: An iterable of (key, node_refs, value) entries to add.
700
# save nodes in case its an iterator
702
translated_nodes = []
704
for (key, value, node_refs) in nodes:
705
adjusted_references = (
706
tuple(tuple(self.prefix_key + ref_node for ref_node in ref_list)
707
for ref_list in node_refs))
708
translated_nodes.append((self.prefix_key + key, value,
709
adjusted_references))
711
# XXX: TODO add an explicit interface for getting the reference list
712
# status, to handle this bit of user-friendliness in the API more
714
for (key, value) in nodes:
715
translated_nodes.append((self.prefix_key + key, value))
716
self.add_nodes_callback(translated_nodes)
718
def add_node(self, key, value, references=()):
719
"""Add a node to the index.
721
:param key: The key. keys are non-empty tuples containing
722
as many whitespace-free utf8 bytestrings as the key length
723
defined for this index.
724
:param references: An iterable of iterables of keys. Each is a
725
reference to another key.
726
:param value: The value to associate with the key. It may be any
727
bytes as long as it does not contain \0 or \n.
729
self.add_nodes(((key, value, references), ))
731
def _strip_prefix(self, an_iter):
732
"""Strip prefix data from nodes and return it."""
735
if node[1][:self.prefix_len] != self.prefix_key:
736
raise errors.BadIndexData(self)
737
for ref_list in node[3]:
738
for ref_node in ref_list:
739
if ref_node[:self.prefix_len] != self.prefix_key:
740
raise errors.BadIndexData(self)
741
yield node[0], node[1][self.prefix_len:], node[2], (
742
tuple(tuple(ref_node[self.prefix_len:] for ref_node in ref_list)
743
for ref_list in node[3]))
745
def iter_all_entries(self):
746
"""Iterate over all keys within the index
748
iter_all_entries is implemented against the adapted index using
751
:return: An iterable of (key, reference_lists, value). There is no
752
defined order for the result iteration - it will be in the most
753
efficient order for the index (in this case dictionary hash order).
755
return self._strip_prefix(self.adapted.iter_entries_prefix([self.prefix]))
757
def iter_entries(self, keys):
758
"""Iterate over keys within the index.
760
:param keys: An iterable providing the keys to be retrieved.
761
:return: An iterable of (key, reference_lists, value). There is no
762
defined order for the result iteration - it will be in the most
763
efficient order for the index (keys iteration order in this case).
765
return self._strip_prefix(self.adapted.iter_entries(
766
self.prefix_key + key for key in keys))
768
def iter_entries_prefix(self, keys):
769
"""Iterate over keys within the index using prefix matching.
771
Prefix matching is applied within the tuple of a key, not to within
772
the bytestring of each key element. e.g. if you have the keys ('foo',
773
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
774
only the former key is returned.
776
:param keys: An iterable providing the key prefixes to be retrieved.
777
Each key prefix takes the form of a tuple the length of a key, but
778
with the last N elements 'None' rather than a regular bytestring.
779
The first element cannot be 'None'.
780
:return: An iterable as per iter_all_entries, but restricted to the
781
keys with a matching prefix to those supplied. No additional keys
782
will be returned, and every match that is in the index will be
785
return self._strip_prefix(self.adapted.iter_entries_prefix(
786
self.prefix_key + key for key in keys))
789
"""Call the adapted's validate."""
790
self.adapted.validate()
added
removed
bzrlib/index.py
