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 bisect import bisect_right
28
from cStringIO import StringIO
31
from bzrlib.lazy_import import lazy_import
32
lazy_import(globals(), """
33
from bzrlib import trace
34
from bzrlib.bisect_multi import bisect_multi_bytes
35
from bzrlib.revision import NULL_REVISION
36
from bzrlib.trace import mutter
38
from bzrlib import debug, errors
40
_HEADER_READV = (0, 200)
41
_OPTION_KEY_ELEMENTS = "key_elements="
43
_OPTION_NODE_REFS = "node_ref_lists="
44
_SIGNATURE = "Bazaar Graph Index 1\n"
47
_whitespace_re = re.compile('[\t\n\x0b\x0c\r\x00 ]')
48
_newline_null_re = re.compile('[\n\0]')
51
class GraphIndexBuilder(object):
52
"""A builder that can build a GraphIndex.
54
The resulting graph has the structure:
56
_SIGNATURE OPTIONS NODES NEWLINE
57
_SIGNATURE := 'Bazaar Graph Index 1' NEWLINE
58
OPTIONS := 'node_ref_lists=' DIGITS NEWLINE
60
NODE := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
61
KEY := Not-whitespace-utf8
63
REFERENCES := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
64
REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
65
REFERENCE := DIGITS ; digits is the byte offset in the index of the
67
VALUE := no-newline-no-null-bytes
70
def __init__(self, reference_lists=0, key_elements=1):
71
"""Create a GraphIndex builder.
73
:param reference_lists: The number of node references lists for each
75
:param key_elements: The number of bytestrings in each key.
77
self.reference_lists = reference_lists
80
self._nodes_by_key = {}
81
self._key_length = key_elements
83
def _check_key(self, key):
84
"""Raise BadIndexKey if key is not a valid key for this index."""
85
if type(key) != tuple:
86
raise errors.BadIndexKey(key)
87
if self._key_length != len(key):
88
raise errors.BadIndexKey(key)
90
if not element or _whitespace_re.search(element) is not None:
91
raise errors.BadIndexKey(element)
93
def add_node(self, key, value, references=()):
94
"""Add a node to the index.
96
:param key: The key. keys are non-empty tuples containing
97
as many whitespace-free utf8 bytestrings as the key length
98
defined for this index.
99
:param references: An iterable of iterables of keys. Each is a
100
reference to another key.
101
:param value: The value to associate with the key. It may be any
102
bytes as long as it does not contain \0 or \n.
105
if _newline_null_re.search(value) is not None:
106
raise errors.BadIndexValue(value)
107
if len(references) != self.reference_lists:
108
raise errors.BadIndexValue(references)
110
for reference_list in references:
111
for reference in reference_list:
112
self._check_key(reference)
113
if reference not in self._nodes:
114
self._nodes[reference] = ('a', (), '')
115
node_refs.append(tuple(reference_list))
116
if key in self._nodes and self._nodes[key][0] == '':
117
raise errors.BadIndexDuplicateKey(key, self)
118
self._nodes[key] = ('', tuple(node_refs), value)
120
if self._key_length > 1:
121
key_dict = self._nodes_by_key
122
if self.reference_lists:
123
key_value = key, value, tuple(node_refs)
125
key_value = key, value
126
# possibly should do this on-demand, but it seems likely it is
128
# For a key of (foo, bar, baz) create
129
# _nodes_by_key[foo][bar][baz] = key_value
130
for subkey in key[:-1]:
131
key_dict = key_dict.setdefault(subkey, {})
132
key_dict[key[-1]] = key_value
136
lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
137
lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
138
lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
139
prefix_length = sum(len(x) for x in lines)
140
# references are byte offsets. To avoid having to do nasty
141
# polynomial work to resolve offsets (references to later in the
142
# file cannot be determined until all the inbetween references have
143
# been calculated too) we pad the offsets with 0's to make them be
144
# of consistent length. Using binary offsets would break the trivial
146
# to calculate the width of zero's needed we do three passes:
147
# one to gather all the non-reference data and the number of references.
148
# one to pad all the data with reference-length and determine entry
152
# forward sorted by key. In future we may consider topological sorting,
153
# at the cost of table scans for direct lookup, or a second index for
155
nodes = sorted(self._nodes.items())
156
# if we do not prepass, we don't know how long it will be up front.
157
expected_bytes = None
158
# we only need to pre-pass if we have reference lists at all.
159
if self.reference_lists:
161
non_ref_bytes = prefix_length
163
# TODO use simple multiplication for the constants in this loop.
164
for key, (absent, references, value) in nodes:
165
# record the offset known *so far* for this key:
166
# the non reference bytes to date, and the total references to
167
# date - saves reaccumulating on the second pass
168
key_offset_info.append((key, non_ref_bytes, total_references))
169
# key is literal, value is literal, there are 3 null's, 1 NL
170
# key is variable length tuple, \x00 between elements
171
non_ref_bytes += sum(len(element) for element in key)
172
if self._key_length > 1:
173
non_ref_bytes += self._key_length - 1
174
# value is literal bytes, there are 3 null's, 1 NL.
175
non_ref_bytes += len(value) + 3 + 1
176
# one byte for absent if set.
179
elif self.reference_lists:
180
# (ref_lists -1) tabs
181
non_ref_bytes += self.reference_lists - 1
182
# (ref-1 cr's per ref_list)
183
for ref_list in references:
184
# how many references across the whole file?
185
total_references += len(ref_list)
186
# accrue reference separators
188
non_ref_bytes += len(ref_list) - 1
189
# how many digits are needed to represent the total byte count?
191
possible_total_bytes = non_ref_bytes + total_references*digits
192
while 10 ** digits < possible_total_bytes:
194
possible_total_bytes = non_ref_bytes + total_references*digits
195
expected_bytes = possible_total_bytes + 1 # terminating newline
196
# resolve key addresses.
198
for key, non_ref_bytes, total_references in key_offset_info:
199
key_addresses[key] = non_ref_bytes + total_references*digits
201
format_string = '%%0%sd' % digits
202
for key, (absent, references, value) in nodes:
203
flattened_references = []
204
for ref_list in references:
206
for reference in ref_list:
207
ref_addresses.append(format_string % key_addresses[reference])
208
flattened_references.append('\r'.join(ref_addresses))
209
string_key = '\x00'.join(key)
210
lines.append("%s\x00%s\x00%s\x00%s\n" % (string_key, absent,
211
'\t'.join(flattened_references), value))
213
result = StringIO(''.join(lines))
214
if expected_bytes and len(result.getvalue()) != expected_bytes:
215
raise errors.BzrError('Failed index creation. Internal error:'
216
' mismatched output length and expected length: %d %d' %
217
(len(result.getvalue()), expected_bytes))
218
return StringIO(''.join(lines))
221
class GraphIndex(object):
222
"""An index for data with embedded graphs.
224
The index maps keys to a list of key reference lists, and a value.
225
Each node has the same number of key reference lists. Each key reference
226
list can be empty or an arbitrary length. The value is an opaque NULL
227
terminated string without any newlines. The storage of the index is
228
hidden in the interface: keys and key references are always tuples of
229
bytestrings, never the internal representation (e.g. dictionary offsets).
231
It is presumed that the index will not be mutated - it is static data.
233
Successive iter_all_entries calls will read the entire index each time.
234
Additionally, iter_entries calls will read the index linearly until the
235
desired keys are found. XXX: This must be fixed before the index is
236
suitable for production use. :XXX
239
def __init__(self, transport, name, size):
240
"""Open an index called name on transport.
242
:param transport: A bzrlib.transport.Transport.
243
:param name: A path to provide to transport API calls.
244
:param size: The size of the index in bytes. This is used for bisection
245
logic to perform partial index reads. While the size could be
246
obtained by statting the file this introduced an additional round
247
trip as well as requiring stat'able transports, both of which are
248
avoided by having it supplied. If size is None, then bisection
249
support will be disabled and accessing the index will just stream
252
self._transport = transport
254
# Becomes a dict of key:(value, reference-list-byte-locations) used by
255
# the bisection interface to store parsed but not resolved keys.
256
self._bisect_nodes = None
257
# Becomes a dict of key:(value, reference-list-keys) which are ready to
258
# be returned directly to callers.
260
# a sorted list of slice-addresses for the parsed bytes of the file.
261
# e.g. (0,1) would mean that byte 0 is parsed.
262
self._parsed_byte_map = []
263
# a sorted list of keys matching each slice address for parsed bytes
264
# e.g. (None, 'foo@bar') would mean that the first byte contained no
265
# key, and the end byte of the slice is the of the data for 'foo@bar'
266
self._parsed_key_map = []
267
self._key_count = None
268
self._keys_by_offset = None
269
self._nodes_by_key = None
272
def __eq__(self, other):
273
"""Equal when self and other were created with the same parameters."""
275
type(self) == type(other) and
276
self._transport == other._transport and
277
self._name == other._name and
278
self._size == other._size)
280
def __ne__(self, other):
281
return not self.__eq__(other)
283
def _buffer_all(self):
284
"""Buffer all the index data.
286
Mutates self._nodes and self.keys_by_offset.
288
if 'index' in debug.debug_flags:
289
mutter('Reading entire index %s', self._transport.abspath(self._name))
290
stream = self._transport.get(self._name)
291
self._read_prefix(stream)
292
self._expected_elements = 3 + self._key_length
294
# raw data keyed by offset
295
self._keys_by_offset = {}
296
# ready-to-return key:value or key:value, node_ref_lists
298
self._nodes_by_key = {}
301
lines = stream.read().split('\n')
303
_, _, _, trailers = self._parse_lines(lines, pos)
304
for key, absent, references, value in self._keys_by_offset.itervalues():
307
# resolve references:
308
if self.node_ref_lists:
309
node_value = (value, self._resolve_references(references))
312
self._nodes[key] = node_value
313
if self._key_length > 1:
314
subkey = list(reversed(key[:-1]))
315
key_dict = self._nodes_by_key
316
if self.node_ref_lists:
317
key_value = key, node_value[0], node_value[1]
319
key_value = key, node_value
320
# possibly should do this on-demand, but it seems likely it is
322
# For a key of (foo, bar, baz) create
323
# _nodes_by_key[foo][bar][baz] = key_value
324
for subkey in key[:-1]:
325
key_dict = key_dict.setdefault(subkey, {})
326
key_dict[key[-1]] = key_value
327
# cache the keys for quick set intersections
328
self._keys = set(self._nodes)
330
# there must be one line - the empty trailer line.
331
raise errors.BadIndexData(self)
333
def iter_all_entries(self):
334
"""Iterate over all keys within the index.
336
:return: An iterable of (index, key, value) or (index, key, value, reference_lists).
337
The former tuple is used when there are no reference lists in the
338
index, making the API compatible with simple key:value index types.
339
There is no defined order for the result iteration - it will be in
340
the most efficient order for the index.
342
if 'evil' in debug.debug_flags:
343
trace.mutter_callsite(3,
344
"iter_all_entries scales with size of history.")
345
if self._nodes is None:
347
if self.node_ref_lists:
348
for key, (value, node_ref_lists) in self._nodes.iteritems():
349
yield self, key, value, node_ref_lists
351
for key, value in self._nodes.iteritems():
352
yield self, key, value
354
def _read_prefix(self, stream):
355
signature = stream.read(len(self._signature()))
356
if not signature == self._signature():
357
raise errors.BadIndexFormatSignature(self._name, GraphIndex)
358
options_line = stream.readline()
359
if not options_line.startswith(_OPTION_NODE_REFS):
360
raise errors.BadIndexOptions(self)
362
self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):-1])
364
raise errors.BadIndexOptions(self)
365
options_line = stream.readline()
366
if not options_line.startswith(_OPTION_KEY_ELEMENTS):
367
raise errors.BadIndexOptions(self)
369
self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):-1])
371
raise errors.BadIndexOptions(self)
372
options_line = stream.readline()
373
if not options_line.startswith(_OPTION_LEN):
374
raise errors.BadIndexOptions(self)
376
self._key_count = int(options_line[len(_OPTION_LEN):-1])
378
raise errors.BadIndexOptions(self)
380
def _resolve_references(self, references):
381
"""Return the resolved key references for references.
383
References are resolved by looking up the location of the key in the
384
_keys_by_offset map and substituting the key name, preserving ordering.
386
:param references: An iterable of iterables of key locations. e.g.
388
:return: A tuple of tuples of keys.
391
for ref_list in references:
392
node_refs.append(tuple([self._keys_by_offset[ref][0] for ref in ref_list]))
393
return tuple(node_refs)
395
def _find_index(self, range_map, key):
396
"""Helper for the _parsed_*_index calls.
398
Given a range map - [(start, end), ...], finds the index of the range
399
in the map for key if it is in the map, and if it is not there, the
400
immediately preceeding range in the map.
402
result = bisect_right(range_map, key) - 1
403
if result + 1 < len(range_map):
404
# check the border condition, it may be in result + 1
405
if range_map[result + 1][0] == key[0]:
409
def _parsed_byte_index(self, offset):
410
"""Return the index of the entry immediately before offset.
412
e.g. if the parsed map has regions 0,10 and 11,12 parsed, meaning that
413
there is one unparsed byte (the 11th, addressed as[10]). then:
414
asking for 0 will return 0
415
asking for 10 will return 0
416
asking for 11 will return 1
417
asking for 12 will return 1
420
return self._find_index(self._parsed_byte_map, key)
422
def _parsed_key_index(self, key):
423
"""Return the index of the entry immediately before key.
425
e.g. if the parsed map has regions (None, 'a') and ('b','c') parsed,
426
meaning that keys from None to 'a' inclusive, and 'b' to 'c' inclusive
427
have been parsed, then:
428
asking for '' will return 0
429
asking for 'a' will return 0
430
asking for 'b' will return 1
431
asking for 'e' will return 1
433
search_key = (key, None)
434
return self._find_index(self._parsed_key_map, search_key)
436
def _is_parsed(self, offset):
437
"""Returns True if offset has been parsed."""
438
index = self._parsed_byte_index(offset)
439
if index == len(self._parsed_byte_map):
440
return offset < self._parsed_byte_map[index - 1][1]
441
start, end = self._parsed_byte_map[index]
442
return offset >= start and offset < end
444
def _iter_entries_from_total_buffer(self, keys):
445
"""Iterate over keys when the entire index is parsed."""
446
keys = keys.intersection(self._keys)
447
if self.node_ref_lists:
449
value, node_refs = self._nodes[key]
450
yield self, key, value, node_refs
453
yield self, key, self._nodes[key]
455
def iter_entries(self, keys):
456
"""Iterate over keys within the index.
458
:param keys: An iterable providing the keys to be retrieved.
459
:return: An iterable as per iter_all_entries, but restricted to the
460
keys supplied. No additional keys will be returned, and every
461
key supplied that is in the index will be returned.
463
# PERFORMANCE TODO: parse and bisect all remaining data at some
464
# threshold of total-index processing/get calling layers that expect to
465
# read the entire index to use the iter_all_entries method instead.
469
if self._size is None and self._nodes is None:
471
if self._nodes is not None:
472
return self._iter_entries_from_total_buffer(keys)
474
return (result[1] for result in bisect_multi_bytes(
475
self._lookup_keys_via_location, self._size, keys))
477
def iter_entries_prefix(self, keys):
478
"""Iterate over keys within the index using prefix matching.
480
Prefix matching is applied within the tuple of a key, not to within
481
the bytestring of each key element. e.g. if you have the keys ('foo',
482
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
483
only the former key is returned.
485
WARNING: Note that this method currently causes a full index parse
486
unconditionally (which is reasonably appropriate as it is a means for
487
thunking many small indices into one larger one and still supplies
488
iter_all_entries at the thunk layer).
490
:param keys: An iterable providing the key prefixes to be retrieved.
491
Each key prefix takes the form of a tuple the length of a key, but
492
with the last N elements 'None' rather than a regular bytestring.
493
The first element cannot be 'None'.
494
:return: An iterable as per iter_all_entries, but restricted to the
495
keys with a matching prefix to those supplied. No additional keys
496
will be returned, and every match that is in the index will be
502
# load data - also finds key lengths
503
if self._nodes is None:
505
if self._key_length == 1:
509
raise errors.BadIndexKey(key)
510
if len(key) != self._key_length:
511
raise errors.BadIndexKey(key)
512
if self.node_ref_lists:
513
value, node_refs = self._nodes[key]
514
yield self, key, value, node_refs
516
yield self, key, self._nodes[key]
521
raise errors.BadIndexKey(key)
522
if len(key) != self._key_length:
523
raise errors.BadIndexKey(key)
524
# find what it refers to:
525
key_dict = self._nodes_by_key
527
# find the subdict whose contents should be returned.
529
while len(elements) and elements[0] is not None:
530
key_dict = key_dict[elements[0]]
533
# a non-existant lookup.
538
key_dict = dicts.pop(-1)
539
# can't be empty or would not exist
540
item, value = key_dict.iteritems().next()
541
if type(value) == dict:
543
dicts.extend(key_dict.itervalues())
546
for value in key_dict.itervalues():
547
# each value is the key:value:node refs tuple
549
yield (self, ) + value
551
# the last thing looked up was a terminal element
552
yield (self, ) + key_dict
555
"""Return an estimate of the number of keys in this index.
557
For GraphIndex the estimate is exact.
559
if self._key_count is None:
560
self._read_and_parse([_HEADER_READV])
561
return self._key_count
563
def _lookup_keys_via_location(self, location_keys):
564
"""Public interface for implementing bisection.
566
If _buffer_all has been called, then all the data for the index is in
567
memory, and this method should not be called, as it uses a separate
568
cache because it cannot pre-resolve all indices, which buffer_all does
571
:param location_keys: A list of location(byte offset), key tuples.
572
:return: A list of (location_key, result) tuples as expected by
573
bzrlib.bisect_multi.bisect_multi_bytes.
575
# Possible improvements:
576
# - only bisect lookup each key once
577
# - sort the keys first, and use that to reduce the bisection window
579
# this progresses in three parts:
582
# attempt to answer the question from the now in memory data.
583
# build the readv request
584
# for each location, ask for 800 bytes - much more than rows we've seen
587
for location, key in location_keys:
588
# can we answer from cache?
589
if self._bisect_nodes and key in self._bisect_nodes:
590
# We have the key parsed.
592
index = self._parsed_key_index(key)
593
if (len(self._parsed_key_map) and
594
self._parsed_key_map[index][0] <= key and
595
(self._parsed_key_map[index][1] >= key or
596
# end of the file has been parsed
597
self._parsed_byte_map[index][1] == self._size)):
598
# the key has been parsed, so no lookup is needed even if its
601
# - if we have examined this part of the file already - yes
602
index = self._parsed_byte_index(location)
603
if (len(self._parsed_byte_map) and
604
self._parsed_byte_map[index][0] <= location and
605
self._parsed_byte_map[index][1] > location):
606
# the byte region has been parsed, so no read is needed.
609
if location + length > self._size:
610
length = self._size - location
611
# todo, trim out parsed locations.
613
readv_ranges.append((location, length))
614
# read the header if needed
615
if self._bisect_nodes is None:
616
readv_ranges.append(_HEADER_READV)
617
self._read_and_parse(readv_ranges)
619
# - figure out <, >, missing, present
620
# - result present references so we can return them.
622
# keys that we cannot answer until we resolve references
623
pending_references = []
624
pending_locations = set()
625
for location, key in location_keys:
626
# can we answer from cache?
627
if key in self._bisect_nodes:
628
# the key has been parsed, so no lookup is needed
629
if self.node_ref_lists:
630
# the references may not have been all parsed.
631
value, refs = self._bisect_nodes[key]
632
wanted_locations = []
633
for ref_list in refs:
635
if ref not in self._keys_by_offset:
636
wanted_locations.append(ref)
638
pending_locations.update(wanted_locations)
639
pending_references.append((location, key))
641
result.append(((location, key), (self, key,
642
value, self._resolve_references(refs))))
644
result.append(((location, key),
645
(self, key, self._bisect_nodes[key])))
648
# has the region the key should be in, been parsed?
649
index = self._parsed_key_index(key)
650
if (self._parsed_key_map[index][0] <= key and
651
(self._parsed_key_map[index][1] >= key or
652
# end of the file has been parsed
653
self._parsed_byte_map[index][1] == self._size)):
654
result.append(((location, key), False))
656
# no, is the key above or below the probed location:
657
# get the range of the probed & parsed location
658
index = self._parsed_byte_index(location)
659
# if the key is below the start of the range, its below
660
if key < self._parsed_key_map[index][0]:
664
result.append(((location, key), direction))
666
# lookup data to resolve references
667
for location in pending_locations:
669
if location + length > self._size:
670
length = self._size - location
671
# TODO: trim out parsed locations (e.g. if the 800 is into the
672
# parsed region trim it, and dont use the adjust_for_latency
675
readv_ranges.append((location, length))
676
self._read_and_parse(readv_ranges)
677
for location, key in pending_references:
678
# answer key references we had to look-up-late.
679
index = self._parsed_key_index(key)
680
value, refs = self._bisect_nodes[key]
681
result.append(((location, key), (self, key,
682
value, self._resolve_references(refs))))
685
def _parse_header_from_bytes(self, bytes):
686
"""Parse the header from a region of bytes.
688
:param bytes: The data to parse.
689
:return: An offset, data tuple such as readv yields, for the unparsed
690
data. (which may length 0).
692
signature = bytes[0:len(self._signature())]
693
if not signature == self._signature():
694
raise errors.BadIndexFormatSignature(self._name, GraphIndex)
695
lines = bytes[len(self._signature()):].splitlines()
696
options_line = lines[0]
697
if not options_line.startswith(_OPTION_NODE_REFS):
698
raise errors.BadIndexOptions(self)
700
self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):])
702
raise errors.BadIndexOptions(self)
703
options_line = lines[1]
704
if not options_line.startswith(_OPTION_KEY_ELEMENTS):
705
raise errors.BadIndexOptions(self)
707
self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):])
709
raise errors.BadIndexOptions(self)
710
options_line = lines[2]
711
if not options_line.startswith(_OPTION_LEN):
712
raise errors.BadIndexOptions(self)
714
self._key_count = int(options_line[len(_OPTION_LEN):])
716
raise errors.BadIndexOptions(self)
717
# calculate the bytes we have processed
718
header_end = (len(signature) + len(lines[0]) + len(lines[1]) +
720
self._parsed_bytes(0, None, header_end, None)
721
# setup parsing state
722
self._expected_elements = 3 + self._key_length
723
# raw data keyed by offset
724
self._keys_by_offset = {}
725
# keys with the value and node references
726
self._bisect_nodes = {}
727
return header_end, bytes[header_end:]
729
def _parse_region(self, offset, data):
730
"""Parse node data returned from a readv operation.
732
:param offset: The byte offset the data starts at.
733
:param data: The data to parse.
737
end = offset + len(data)
740
# Trivial test - if the current index's end is within the
741
# low-matching parsed range, we're done.
742
index = self._parsed_byte_index(high_parsed)
743
if end < self._parsed_byte_map[index][1]:
745
# print "[%d:%d]" % (offset, end), \
746
# self._parsed_byte_map[index:index + 2]
747
high_parsed, last_segment = self._parse_segment(
748
offset, data, end, index)
752
def _parse_segment(self, offset, data, end, index):
753
"""Parse one segment of data.
755
:param offset: Where 'data' begins in the file.
756
:param data: Some data to parse a segment of.
757
:param end: Where data ends
758
:param index: The current index into the parsed bytes map.
759
:return: True if the parsed segment is the last possible one in the
761
:return: high_parsed_byte, last_segment.
762
high_parsed_byte is the location of the highest parsed byte in this
763
segment, last_segment is True if the parsed segment is the last
764
possible one in the data block.
766
# default is to use all data
768
# accomodate overlap with data before this.
769
if offset < self._parsed_byte_map[index][1]:
770
# overlaps the lower parsed region
771
# skip the parsed data
772
trim_start = self._parsed_byte_map[index][1] - offset
773
# don't trim the start for \n
774
start_adjacent = True
775
elif offset == self._parsed_byte_map[index][1]:
776
# abuts the lower parsed region
779
# do not trim anything
780
start_adjacent = True
782
# does not overlap the lower parsed region
785
# but trim the leading \n
786
start_adjacent = False
787
if end == self._size:
788
# lines up to the end of all data:
791
# do not strip to the last \n
794
elif index + 1 == len(self._parsed_byte_map):
795
# at the end of the parsed data
798
# but strip to the last \n
801
elif end == self._parsed_byte_map[index + 1][0]:
802
# buts up against the next parsed region
805
# do not strip to the last \n
808
elif end > self._parsed_byte_map[index + 1][0]:
809
# overlaps into the next parsed region
810
# only consider the unparsed data
811
trim_end = self._parsed_byte_map[index + 1][0] - offset
812
# do not strip to the last \n as we know its an entire record
814
last_segment = end < self._parsed_byte_map[index + 1][1]
816
# does not overlap into the next region
819
# but strip to the last \n
822
# now find bytes to discard if needed
823
if not start_adjacent:
824
# work around python bug in rfind
825
if trim_start is None:
826
trim_start = data.find('\n') + 1
828
trim_start = data.find('\n', trim_start) + 1
829
assert trim_start != 0, 'no \n was present'
830
# print 'removing start', offset, trim_start, repr(data[:trim_start])
832
# work around python bug in rfind
834
trim_end = data.rfind('\n') + 1
836
trim_end = data.rfind('\n', None, trim_end) + 1
837
assert trim_end != 0, 'no \n was present'
838
# print 'removing end', offset, trim_end, repr(data[trim_end:])
839
# adjust offset and data to the parseable data.
840
trimmed_data = data[trim_start:trim_end]
841
assert trimmed_data, 'read unneeded data [%d:%d] from [%d:%d]' % (
842
trim_start, trim_end, offset, offset + len(data))
845
# print "parsing", repr(trimmed_data)
846
# splitlines mangles the \r delimiters.. don't use it.
847
lines = trimmed_data.split('\n')
850
first_key, last_key, nodes, _ = self._parse_lines(lines, pos)
851
for key, value in nodes:
852
self._bisect_nodes[key] = value
853
self._parsed_bytes(offset, first_key,
854
offset + len(trimmed_data), last_key)
855
return offset + len(trimmed_data), last_segment
857
def _parse_lines(self, lines, pos):
866
assert self._size == pos + 1, "%s %s" % (self._size, pos)
869
elements = line.split('\0')
870
if len(elements) != self._expected_elements:
871
raise errors.BadIndexData(self)
873
key = tuple(elements[:self._key_length])
874
if first_key is None:
876
absent, references, value = elements[-3:]
878
for ref_string in references.split('\t'):
879
ref_lists.append(tuple([
880
int(ref) for ref in ref_string.split('\r') if ref
882
ref_lists = tuple(ref_lists)
883
self._keys_by_offset[pos] = (key, absent, ref_lists, value)
884
pos += len(line) + 1 # +1 for the \n
887
if self.node_ref_lists:
888
node_value = (value, ref_lists)
891
nodes.append((key, node_value))
892
# print "parsed ", key
893
return first_key, key, nodes, trailers
895
def _parsed_bytes(self, start, start_key, end, end_key):
896
"""Mark the bytes from start to end as parsed.
898
Calling self._parsed_bytes(1,2) will mark one byte (the one at offset
901
:param start: The start of the parsed region.
902
:param end: The end of the parsed region.
904
index = self._parsed_byte_index(start)
905
new_value = (start, end)
906
new_key = (start_key, end_key)
908
# first range parsed is always the beginning.
909
self._parsed_byte_map.insert(index, new_value)
910
self._parsed_key_map.insert(index, new_key)
914
# extend lower region
915
# extend higher region
916
# combine two regions
917
if (index + 1 < len(self._parsed_byte_map) and
918
self._parsed_byte_map[index][1] == start and
919
self._parsed_byte_map[index + 1][0] == end):
920
# combine two regions
921
self._parsed_byte_map[index] = (self._parsed_byte_map[index][0],
922
self._parsed_byte_map[index + 1][1])
923
self._parsed_key_map[index] = (self._parsed_key_map[index][0],
924
self._parsed_key_map[index + 1][1])
925
del self._parsed_byte_map[index + 1]
926
del self._parsed_key_map[index + 1]
927
elif self._parsed_byte_map[index][1] == start:
928
# extend the lower entry
929
self._parsed_byte_map[index] = (
930
self._parsed_byte_map[index][0], end)
931
self._parsed_key_map[index] = (
932
self._parsed_key_map[index][0], end_key)
933
elif (index + 1 < len(self._parsed_byte_map) and
934
self._parsed_byte_map[index + 1][0] == end):
935
# extend the higher entry
936
self._parsed_byte_map[index + 1] = (
937
start, self._parsed_byte_map[index + 1][1])
938
self._parsed_key_map[index + 1] = (
939
start_key, self._parsed_key_map[index + 1][1])
942
self._parsed_byte_map.insert(index + 1, new_value)
943
self._parsed_key_map.insert(index + 1, new_key)
945
def _read_and_parse(self, readv_ranges):
946
"""Read the the ranges and parse the resulting data.
948
:param readv_ranges: A prepared readv range list.
951
readv_data = self._transport.readv(self._name, readv_ranges, True,
954
for offset, data in readv_data:
955
if self._bisect_nodes is None:
956
# this must be the start
958
offset, data = self._parse_header_from_bytes(data)
959
# print readv_ranges, "[%d:%d]" % (offset, offset + len(data))
960
self._parse_region(offset, data)
962
def _signature(self):
963
"""The file signature for this index type."""
967
"""Validate that everything in the index can be accessed."""
968
# iter_all validates completely at the moment, so just do that.
969
for node in self.iter_all_entries():
973
class CombinedGraphIndex(object):
974
"""A GraphIndex made up from smaller GraphIndices.
976
The backing indices must implement GraphIndex, and are presumed to be
979
Queries against the combined index will be made against the first index,
980
and then the second and so on. The order of index's can thus influence
981
performance significantly. For example, if one index is on local disk and a
982
second on a remote server, the local disk index should be before the other
986
def __init__(self, indices):
987
"""Create a CombinedGraphIndex backed by indices.
989
:param indices: An ordered list of indices to query for data.
991
self._indices = indices
995
self.__class__.__name__,
996
', '.join(map(repr, self._indices)))
998
def get_parents(self, revision_ids):
999
"""See StackedParentsProvider.get_parents.
1001
This implementation thunks the graph.Graph.get_parents api across to
1004
:param revision_ids: An iterable of graph keys for this graph.
1005
:return: A list of parent details for each key in revision_ids.
1006
Each parent details will be one of:
1007
* None when the key was missing
1008
* (NULL_REVISION,) when the key has no parents.
1009
* (parent_key, parent_key...) otherwise.
1011
search_keys = set(revision_ids)
1012
search_keys.discard(NULL_REVISION)
1013
found_parents = {NULL_REVISION:[]}
1014
for index, key, value, refs in self.iter_entries(search_keys):
1017
parents = (NULL_REVISION,)
1018
found_parents[key] = parents
1020
for key in revision_ids:
1022
result.append(found_parents[key])
1027
def insert_index(self, pos, index):
1028
"""Insert a new index in the list of indices to query.
1030
:param pos: The position to insert the index.
1031
:param index: The index to insert.
1033
self._indices.insert(pos, index)
1035
def iter_all_entries(self):
1036
"""Iterate over all keys within the index
1038
Duplicate keys across child indices are presumed to have the same
1039
value and are only reported once.
1041
:return: An iterable of (index, key, reference_lists, value).
1042
There is no defined order for the result iteration - it will be in
1043
the most efficient order for the index.
1046
for index in self._indices:
1047
for node in index.iter_all_entries():
1048
if node[1] not in seen_keys:
1050
seen_keys.add(node[1])
1052
def iter_entries(self, keys):
1053
"""Iterate over keys within the index.
1055
Duplicate keys across child indices are presumed to have the same
1056
value and are only reported once.
1058
:param keys: An iterable providing the keys to be retrieved.
1059
:return: An iterable of (index, key, reference_lists, value). There is no
1060
defined order for the result iteration - it will be in the most
1061
efficient order for the index.
1064
for index in self._indices:
1067
for node in index.iter_entries(keys):
1068
keys.remove(node[1])
1071
def iter_entries_prefix(self, keys):
1072
"""Iterate over keys within the index using prefix matching.
1074
Duplicate keys across child indices are presumed to have the same
1075
value and are only reported once.
1077
Prefix matching is applied within the tuple of a key, not to within
1078
the bytestring of each key element. e.g. if you have the keys ('foo',
1079
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
1080
only the former key is returned.
1082
:param keys: An iterable providing the key prefixes to be retrieved.
1083
Each key prefix takes the form of a tuple the length of a key, but
1084
with the last N elements 'None' rather than a regular bytestring.
1085
The first element cannot be 'None'.
1086
:return: An iterable as per iter_all_entries, but restricted to the
1087
keys with a matching prefix to those supplied. No additional keys
1088
will be returned, and every match that is in the index will be
1095
for index in self._indices:
1096
for node in index.iter_entries_prefix(keys):
1097
if node[1] in seen_keys:
1099
seen_keys.add(node[1])
1102
def key_count(self):
1103
"""Return an estimate of the number of keys in this index.
1105
For CombinedGraphIndex this is approximated by the sum of the keys of
1106
the child indices. As child indices may have duplicate keys this can
1107
have a maximum error of the number of child indices * largest number of
1110
return sum((index.key_count() for index in self._indices), 0)
1113
"""Validate that everything in the index can be accessed."""
1114
for index in self._indices:
1118
class InMemoryGraphIndex(GraphIndexBuilder):
1119
"""A GraphIndex which operates entirely out of memory and is mutable.
1121
This is designed to allow the accumulation of GraphIndex entries during a
1122
single write operation, where the accumulated entries need to be immediately
1123
available - for example via a CombinedGraphIndex.
1126
def add_nodes(self, nodes):
1127
"""Add nodes to the index.
1129
:param nodes: An iterable of (key, node_refs, value) entries to add.
1131
if self.reference_lists:
1132
for (key, value, node_refs) in nodes:
1133
self.add_node(key, value, node_refs)
1135
for (key, value) in nodes:
1136
self.add_node(key, value)
1138
def iter_all_entries(self):
1139
"""Iterate over all keys within the index
1141
:return: An iterable of (index, key, reference_lists, value). There is no
1142
defined order for the result iteration - it will be in the most
1143
efficient order for the index (in this case dictionary hash order).
1145
if 'evil' in debug.debug_flags:
1146
trace.mutter_callsite(3,
1147
"iter_all_entries scales with size of history.")
1148
if self.reference_lists:
1149
for key, (absent, references, value) in self._nodes.iteritems():
1151
yield self, key, value, references
1153
for key, (absent, references, value) in self._nodes.iteritems():
1155
yield self, key, value
1157
def iter_entries(self, keys):
1158
"""Iterate over keys within the index.
1160
:param keys: An iterable providing the keys to be retrieved.
1161
:return: An iterable of (index, key, value, reference_lists). There is no
1162
defined order for the result iteration - it will be in the most
1163
efficient order for the index (keys iteration order in this case).
1166
if self.reference_lists:
1167
for key in keys.intersection(self._keys):
1168
node = self._nodes[key]
1170
yield self, key, node[2], node[1]
1172
for key in keys.intersection(self._keys):
1173
node = self._nodes[key]
1175
yield self, key, node[2]
1177
def iter_entries_prefix(self, keys):
1178
"""Iterate over keys within the index using prefix matching.
1180
Prefix matching is applied within the tuple of a key, not to within
1181
the bytestring of each key element. e.g. if you have the keys ('foo',
1182
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
1183
only the former key is returned.
1185
:param keys: An iterable providing the key prefixes to be retrieved.
1186
Each key prefix takes the form of a tuple the length of a key, but
1187
with the last N elements 'None' rather than a regular bytestring.
1188
The first element cannot be 'None'.
1189
:return: An iterable as per iter_all_entries, but restricted to the
1190
keys with a matching prefix to those supplied. No additional keys
1191
will be returned, and every match that is in the index will be
1194
# XXX: To much duplication with the GraphIndex class; consider finding
1195
# a good place to pull out the actual common logic.
1199
if self._key_length == 1:
1203
raise errors.BadIndexKey(key)
1204
if len(key) != self._key_length:
1205
raise errors.BadIndexKey(key)
1206
node = self._nodes[key]
1209
if self.reference_lists:
1210
yield self, key, node[2], node[1]
1212
yield self, key, node[2]
1217
raise errors.BadIndexKey(key)
1218
if len(key) != self._key_length:
1219
raise errors.BadIndexKey(key)
1220
# find what it refers to:
1221
key_dict = self._nodes_by_key
1222
elements = list(key)
1223
# find the subdict to return
1225
while len(elements) and elements[0] is not None:
1226
key_dict = key_dict[elements[0]]
1229
# a non-existant lookup.
1234
key_dict = dicts.pop(-1)
1235
# can't be empty or would not exist
1236
item, value = key_dict.iteritems().next()
1237
if type(value) == dict:
1239
dicts.extend(key_dict.itervalues())
1242
for value in key_dict.itervalues():
1243
yield (self, ) + value
1245
yield (self, ) + key_dict
1247
def key_count(self):
1248
"""Return an estimate of the number of keys in this index.
1250
For InMemoryGraphIndex the estimate is exact.
1252
return len(self._keys)
1255
"""In memory index's have no known corruption at the moment."""
1258
class GraphIndexPrefixAdapter(object):
1259
"""An adapter between GraphIndex with different key lengths.
1261
Queries against this will emit queries against the adapted Graph with the
1262
prefix added, queries for all items use iter_entries_prefix. The returned
1263
nodes will have their keys and node references adjusted to remove the
1264
prefix. Finally, an add_nodes_callback can be supplied - when called the
1265
nodes and references being added will have prefix prepended.
1268
def __init__(self, adapted, prefix, missing_key_length,
1269
add_nodes_callback=None):
1270
"""Construct an adapter against adapted with prefix."""
1271
self.adapted = adapted
1272
self.prefix_key = prefix + (None,)*missing_key_length
1273
self.prefix = prefix
1274
self.prefix_len = len(prefix)
1275
self.add_nodes_callback = add_nodes_callback
1277
def add_nodes(self, nodes):
1278
"""Add nodes to the index.
1280
:param nodes: An iterable of (key, node_refs, value) entries to add.
1282
# save nodes in case its an iterator
1283
nodes = tuple(nodes)
1284
translated_nodes = []
1286
# Add prefix_key to each reference node_refs is a tuple of tuples,
1287
# so split it apart, and add prefix_key to the internal reference
1288
for (key, value, node_refs) in nodes:
1289
adjusted_references = (
1290
tuple(tuple(self.prefix + ref_node for ref_node in ref_list)
1291
for ref_list in node_refs))
1292
translated_nodes.append((self.prefix + key, value,
1293
adjusted_references))
1295
# XXX: TODO add an explicit interface for getting the reference list
1296
# status, to handle this bit of user-friendliness in the API more
1298
for (key, value) in nodes:
1299
translated_nodes.append((self.prefix + key, value))
1300
self.add_nodes_callback(translated_nodes)
1302
def add_node(self, key, value, references=()):
1303
"""Add a node to the index.
1305
:param key: The key. keys are non-empty tuples containing
1306
as many whitespace-free utf8 bytestrings as the key length
1307
defined for this index.
1308
:param references: An iterable of iterables of keys. Each is a
1309
reference to another key.
1310
:param value: The value to associate with the key. It may be any
1311
bytes as long as it does not contain \0 or \n.
1313
self.add_nodes(((key, value, references), ))
1315
def _strip_prefix(self, an_iter):
1316
"""Strip prefix data from nodes and return it."""
1317
for node in an_iter:
1319
if node[1][:self.prefix_len] != self.prefix:
1320
raise errors.BadIndexData(self)
1321
for ref_list in node[3]:
1322
for ref_node in ref_list:
1323
if ref_node[:self.prefix_len] != self.prefix:
1324
raise errors.BadIndexData(self)
1325
yield node[0], node[1][self.prefix_len:], node[2], (
1326
tuple(tuple(ref_node[self.prefix_len:] for ref_node in ref_list)
1327
for ref_list in node[3]))
1329
def iter_all_entries(self):
1330
"""Iterate over all keys within the index
1332
iter_all_entries is implemented against the adapted index using
1333
iter_entries_prefix.
1335
:return: An iterable of (index, key, reference_lists, value). There is no
1336
defined order for the result iteration - it will be in the most
1337
efficient order for the index (in this case dictionary hash order).
1339
return self._strip_prefix(self.adapted.iter_entries_prefix([self.prefix_key]))
1341
def iter_entries(self, keys):
1342
"""Iterate over keys within the index.
1344
:param keys: An iterable providing the keys to be retrieved.
1345
:return: An iterable of (index, key, value, reference_lists). There is no
1346
defined order for the result iteration - it will be in the most
1347
efficient order for the index (keys iteration order in this case).
1349
return self._strip_prefix(self.adapted.iter_entries(
1350
self.prefix + key for key in keys))
1352
def iter_entries_prefix(self, keys):
1353
"""Iterate over keys within the index using prefix matching.
1355
Prefix matching is applied within the tuple of a key, not to within
1356
the bytestring of each key element. e.g. if you have the keys ('foo',
1357
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
1358
only the former key is returned.
1360
:param keys: An iterable providing the key prefixes to be retrieved.
1361
Each key prefix takes the form of a tuple the length of a key, but
1362
with the last N elements 'None' rather than a regular bytestring.
1363
The first element cannot be 'None'.
1364
:return: An iterable as per iter_all_entries, but restricted to the
1365
keys with a matching prefix to those supplied. No additional keys
1366
will be returned, and every match that is in the index will be
1369
return self._strip_prefix(self.adapted.iter_entries_prefix(
1370
self.prefix + key for key in keys))
1372
def key_count(self):
1373
"""Return an estimate of the number of keys in this index.
1375
For GraphIndexPrefixAdapter this is relatively expensive - key
1376
iteration with the prefix is done.
1378
return len(list(self.iter_all_entries()))
1381
"""Call the adapted's validate."""
1382
self.adapted.validate()
added
removed
bzrlib/index.py
