2592.1.4
by Robert Collins
Create a GraphIndexBuilder. |
1 |
# Copyright (C) 2007 Canonical Ltd
|
2 |
#
|
|
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.
|
|
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
|
|
15 |
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
|
|
16 |
||
17 |
"""Indexing facilities."""
|
|
18 |
||
2592.1.38
by Robert Collins
Create an InMemoryGraphIndex for temporary indexing. |
19 |
__all__ = [ |
20 |
'CombinedGraphIndex', |
|
21 |
'GraphIndex', |
|
22 |
'GraphIndexBuilder', |
|
2624.2.12
by Robert Collins
Create an adapter between indices with differing key lengths. |
23 |
'GraphIndexPrefixAdapter', |
2592.1.38
by Robert Collins
Create an InMemoryGraphIndex for temporary indexing. |
24 |
'InMemoryGraphIndex', |
25 |
]
|
|
2592.1.32
by Robert Collins
Add __all__ to index. |
26 |
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
27 |
from bisect import bisect_right |
2592.1.4
by Robert Collins
Create a GraphIndexBuilder. |
28 |
from cStringIO import StringIO |
2592.1.12
by Robert Collins
Handle basic node adds. |
29 |
import re |
2592.1.4
by Robert Collins
Create a GraphIndexBuilder. |
30 |
|
2624.2.15
by Robert Collins
Add useful -Dindex flag. |
31 |
from bzrlib.lazy_import import lazy_import |
32 |
lazy_import(globals(), """ |
|
2745.1.2
by Robert Collins
Ensure mutter_callsite is not directly called on a lazy_load object, to make the stacklevel parameter work correctly. |
33 |
from bzrlib import trace
|
2890.2.7
by Robert Collins
* Pack indices are now partially parsed for specific key lookup using a |
34 |
from bzrlib.bisect_multi import bisect_multi_bytes
|
2979.2.2
by Robert Collins
Per-file graph heads detection during commit for pack repositories. |
35 |
from bzrlib.revision import NULL_REVISION
|
2745.1.2
by Robert Collins
Ensure mutter_callsite is not directly called on a lazy_load object, to make the stacklevel parameter work correctly. |
36 |
from bzrlib.trace import mutter
|
2624.2.15
by Robert Collins
Add useful -Dindex flag. |
37 |
""") |
3099.3.3
by John Arbash Meinel
Deprecate get_parents() in favor of get_parent_map() |
38 |
from bzrlib import ( |
39 |
debug, |
|
40 |
errors, |
|
41 |
symbol_versioning, |
|
42 |
)
|
|
2592.1.4
by Robert Collins
Create a GraphIndexBuilder. |
43 |
|
2979.1.1
by Robert Collins
Use the GraphIndex header to answer key_count queries rather than parsing the entire index unnecessarily. |
44 |
_HEADER_READV = (0, 200) |
2624.2.8
by Robert Collins
Explicitly mark the number of keys elements in use in GraphIndex files. |
45 |
_OPTION_KEY_ELEMENTS = "key_elements=" |
2624.2.16
by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index. |
46 |
_OPTION_LEN = "len=" |
2592.1.6
by Robert Collins
Record the number of node reference lists a particular index has. |
47 |
_OPTION_NODE_REFS = "node_ref_lists=" |
2592.1.4
by Robert Collins
Create a GraphIndexBuilder. |
48 |
_SIGNATURE = "Bazaar Graph Index 1\n" |
49 |
||
50 |
||
2592.1.14
by Robert Collins
Detect bad reference key values. |
51 |
_whitespace_re = re.compile('[\t\n\x0b\x0c\r\x00 ]') |
2592.1.12
by Robert Collins
Handle basic node adds. |
52 |
_newline_null_re = re.compile('[\n\0]') |
53 |
||
54 |
||
2592.1.4
by Robert Collins
Create a GraphIndexBuilder. |
55 |
class GraphIndexBuilder(object): |
2592.1.18
by Robert Collins
Add space to mark absent nodes. |
56 |
"""A builder that can build a GraphIndex.
|
57 |
|
|
58 |
The resulting graph has the structure:
|
|
59 |
|
|
60 |
_SIGNATURE OPTIONS NODES NEWLINE
|
|
61 |
_SIGNATURE := 'Bazaar Graph Index 1' NEWLINE
|
|
62 |
OPTIONS := 'node_ref_lists=' DIGITS NEWLINE
|
|
63 |
NODES := NODE*
|
|
64 |
NODE := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
|
|
65 |
KEY := Not-whitespace-utf8
|
|
66 |
ABSENT := 'a'
|
|
2592.1.19
by Robert Collins
Node references are tab separated. |
67 |
REFERENCES := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
|
68 |
REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
|
|
69 |
REFERENCE := DIGITS ; digits is the byte offset in the index of the
|
|
70 |
; referenced key.
|
|
2592.1.18
by Robert Collins
Add space to mark absent nodes. |
71 |
VALUE := no-newline-no-null-bytes
|
72 |
"""
|
|
2592.1.4
by Robert Collins
Create a GraphIndexBuilder. |
73 |
|
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
74 |
def __init__(self, reference_lists=0, key_elements=1): |
2592.1.6
by Robert Collins
Record the number of node reference lists a particular index has. |
75 |
"""Create a GraphIndex builder.
|
76 |
||
77 |
:param reference_lists: The number of node references lists for each
|
|
78 |
entry.
|
|
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
79 |
:param key_elements: The number of bytestrings in each key.
|
2592.1.6
by Robert Collins
Record the number of node reference lists a particular index has. |
80 |
"""
|
81 |
self.reference_lists = reference_lists |
|
2592.3.62
by Robert Collins
Performance tweak - use a set for InMemoryGraph key iteration. |
82 |
self._keys = set() |
2592.1.15
by Robert Collins
Detect duplicate key insertion. |
83 |
self._nodes = {} |
2624.2.10
by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex. |
84 |
self._nodes_by_key = {} |
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
85 |
self._key_length = key_elements |
2624.2.5
by Robert Collins
Change bzrlib.index.Index keys to be 1-tuples, not strings. |
86 |
|
87 |
def _check_key(self, key): |
|
88 |
"""Raise BadIndexKey if key is not a valid key for this index."""
|
|
89 |
if type(key) != tuple: |
|
90 |
raise errors.BadIndexKey(key) |
|
91 |
if self._key_length != len(key): |
|
92 |
raise errors.BadIndexKey(key) |
|
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
93 |
for element in key: |
94 |
if not element or _whitespace_re.search(element) is not None: |
|
95 |
raise errors.BadIndexKey(element) |
|
2592.1.12
by Robert Collins
Handle basic node adds. |
96 |
|
2592.1.46
by Robert Collins
Make GraphIndex accept nodes as key, value, references, so that the method |
97 |
def add_node(self, key, value, references=()): |
2592.1.12
by Robert Collins
Handle basic node adds. |
98 |
"""Add a node to the index.
|
99 |
||
2624.2.5
by Robert Collins
Change bzrlib.index.Index keys to be 1-tuples, not strings. |
100 |
:param key: The key. keys are non-empty tuples containing
|
101 |
as many whitespace-free utf8 bytestrings as the key length
|
|
102 |
defined for this index.
|
|
2592.1.12
by Robert Collins
Handle basic node adds. |
103 |
:param references: An iterable of iterables of keys. Each is a
|
104 |
reference to another key.
|
|
105 |
:param value: The value to associate with the key. It may be any
|
|
106 |
bytes as long as it does not contain \0 or \n.
|
|
107 |
"""
|
|
2624.2.5
by Robert Collins
Change bzrlib.index.Index keys to be 1-tuples, not strings. |
108 |
self._check_key(key) |
2592.1.12
by Robert Collins
Handle basic node adds. |
109 |
if _newline_null_re.search(value) is not None: |
110 |
raise errors.BadIndexValue(value) |
|
2592.1.13
by Robert Collins
Handle mismatched numbers of reference lists. |
111 |
if len(references) != self.reference_lists: |
112 |
raise errors.BadIndexValue(references) |
|
2592.1.38
by Robert Collins
Create an InMemoryGraphIndex for temporary indexing. |
113 |
node_refs = [] |
2592.1.14
by Robert Collins
Detect bad reference key values. |
114 |
for reference_list in references: |
115 |
for reference in reference_list: |
|
2624.2.5
by Robert Collins
Change bzrlib.index.Index keys to be 1-tuples, not strings. |
116 |
self._check_key(reference) |
2592.1.25
by Robert Collins
Fix and tune node offset calculation. |
117 |
if reference not in self._nodes: |
2592.1.38
by Robert Collins
Create an InMemoryGraphIndex for temporary indexing. |
118 |
self._nodes[reference] = ('a', (), '') |
119 |
node_refs.append(tuple(reference_list)) |
|
2592.1.25
by Robert Collins
Fix and tune node offset calculation. |
120 |
if key in self._nodes and self._nodes[key][0] == '': |
2592.1.15
by Robert Collins
Detect duplicate key insertion. |
121 |
raise errors.BadIndexDuplicateKey(key, self) |
2592.1.38
by Robert Collins
Create an InMemoryGraphIndex for temporary indexing. |
122 |
self._nodes[key] = ('', tuple(node_refs), value) |
2592.3.62
by Robert Collins
Performance tweak - use a set for InMemoryGraph key iteration. |
123 |
self._keys.add(key) |
2624.2.10
by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex. |
124 |
if self._key_length > 1: |
125 |
key_dict = self._nodes_by_key |
|
126 |
if self.reference_lists: |
|
127 |
key_value = key, value, tuple(node_refs) |
|
128 |
else: |
|
129 |
key_value = key, value |
|
130 |
# possibly should do this on-demand, but it seems likely it is
|
|
131 |
# always wanted
|
|
2624.2.11
by Robert Collins
Review comments. |
132 |
# For a key of (foo, bar, baz) create
|
133 |
# _nodes_by_key[foo][bar][baz] = key_value
|
|
134 |
for subkey in key[:-1]: |
|
135 |
key_dict = key_dict.setdefault(subkey, {}) |
|
2624.2.10
by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex. |
136 |
key_dict[key[-1]] = key_value |
2592.1.6
by Robert Collins
Record the number of node reference lists a particular index has. |
137 |
|
2592.1.4
by Robert Collins
Create a GraphIndexBuilder. |
138 |
def finish(self): |
2592.1.6
by Robert Collins
Record the number of node reference lists a particular index has. |
139 |
lines = [_SIGNATURE] |
140 |
lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n') |
|
2624.2.8
by Robert Collins
Explicitly mark the number of keys elements in use in GraphIndex files. |
141 |
lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n') |
2624.2.16
by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index. |
142 |
lines.append(_OPTION_LEN + str(len(self._keys)) + '\n') |
2624.2.11
by Robert Collins
Review comments. |
143 |
prefix_length = sum(len(x) for x in lines) |
2592.1.22
by Robert Collins
Node references are byte offsets. |
144 |
# references are byte offsets. To avoid having to do nasty
|
145 |
# polynomial work to resolve offsets (references to later in the
|
|
146 |
# file cannot be determined until all the inbetween references have
|
|
147 |
# been calculated too) we pad the offsets with 0's to make them be
|
|
148 |
# of consistent length. Using binary offsets would break the trivial
|
|
149 |
# file parsing.
|
|
150 |
# to calculate the width of zero's needed we do three passes:
|
|
151 |
# one to gather all the non-reference data and the number of references.
|
|
152 |
# one to pad all the data with reference-length and determine entry
|
|
153 |
# addresses.
|
|
154 |
# One to serialise.
|
|
2592.1.40
by Robert Collins
Reverse index ordering - we do not have date prefixed revids. |
155 |
|
156 |
# forward sorted by key. In future we may consider topological sorting,
|
|
157 |
# at the cost of table scans for direct lookup, or a second index for
|
|
158 |
# direct lookup
|
|
159 |
nodes = sorted(self._nodes.items()) |
|
2592.1.42
by Robert Collins
Check the index length is as expected, when we have done preprocessing. |
160 |
# if we do not prepass, we don't know how long it will be up front.
|
161 |
expected_bytes = None |
|
2592.1.25
by Robert Collins
Fix and tune node offset calculation. |
162 |
# we only need to pre-pass if we have reference lists at all.
|
163 |
if self.reference_lists: |
|
2592.1.41
by Robert Collins
Remove duplication in the index serialisation logic with John's suggestion. |
164 |
key_offset_info = [] |
2592.1.25
by Robert Collins
Fix and tune node offset calculation. |
165 |
non_ref_bytes = prefix_length |
166 |
total_references = 0 |
|
167 |
# TODO use simple multiplication for the constants in this loop.
|
|
168 |
for key, (absent, references, value) in nodes: |
|
2592.1.41
by Robert Collins
Remove duplication in the index serialisation logic with John's suggestion. |
169 |
# record the offset known *so far* for this key:
|
170 |
# the non reference bytes to date, and the total references to
|
|
171 |
# date - saves reaccumulating on the second pass
|
|
172 |
key_offset_info.append((key, non_ref_bytes, total_references)) |
|
2592.1.25
by Robert Collins
Fix and tune node offset calculation. |
173 |
# key is literal, value is literal, there are 3 null's, 1 NL
|
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
174 |
# key is variable length tuple, \x00 between elements
|
2624.2.5
by Robert Collins
Change bzrlib.index.Index keys to be 1-tuples, not strings. |
175 |
non_ref_bytes += sum(len(element) for element in key) |
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
176 |
if self._key_length > 1: |
177 |
non_ref_bytes += self._key_length - 1 |
|
2624.2.5
by Robert Collins
Change bzrlib.index.Index keys to be 1-tuples, not strings. |
178 |
# value is literal bytes, there are 3 null's, 1 NL.
|
179 |
non_ref_bytes += len(value) + 3 + 1 |
|
2592.1.25
by Robert Collins
Fix and tune node offset calculation. |
180 |
# one byte for absent if set.
|
181 |
if absent: |
|
182 |
non_ref_bytes += 1 |
|
2592.1.36
by Robert Collins
Bugfix incorrect offset generation when an absent record is before a referenced record. |
183 |
elif self.reference_lists: |
2592.1.25
by Robert Collins
Fix and tune node offset calculation. |
184 |
# (ref_lists -1) tabs
|
185 |
non_ref_bytes += self.reference_lists - 1 |
|
186 |
# (ref-1 cr's per ref_list)
|
|
187 |
for ref_list in references: |
|
188 |
# how many references across the whole file?
|
|
189 |
total_references += len(ref_list) |
|
190 |
# accrue reference separators
|
|
191 |
if ref_list: |
|
192 |
non_ref_bytes += len(ref_list) - 1 |
|
193 |
# how many digits are needed to represent the total byte count?
|
|
194 |
digits = 1 |
|
2592.1.22
by Robert Collins
Node references are byte offsets. |
195 |
possible_total_bytes = non_ref_bytes + total_references*digits |
2592.1.25
by Robert Collins
Fix and tune node offset calculation. |
196 |
while 10 ** digits < possible_total_bytes: |
197 |
digits += 1 |
|
198 |
possible_total_bytes = non_ref_bytes + total_references*digits |
|
2592.1.42
by Robert Collins
Check the index length is as expected, when we have done preprocessing. |
199 |
expected_bytes = possible_total_bytes + 1 # terminating newline |
2592.1.25
by Robert Collins
Fix and tune node offset calculation. |
200 |
# resolve key addresses.
|
201 |
key_addresses = {} |
|
2592.1.41
by Robert Collins
Remove duplication in the index serialisation logic with John's suggestion. |
202 |
for key, non_ref_bytes, total_references in key_offset_info: |
203 |
key_addresses[key] = non_ref_bytes + total_references*digits |
|
2592.1.25
by Robert Collins
Fix and tune node offset calculation. |
204 |
# serialise
|
205 |
format_string = '%%0%sd' % digits |
|
206 |
for key, (absent, references, value) in nodes: |
|
2592.1.19
by Robert Collins
Node references are tab separated. |
207 |
flattened_references = [] |
208 |
for ref_list in references: |
|
2592.1.22
by Robert Collins
Node references are byte offsets. |
209 |
ref_addresses = [] |
210 |
for reference in ref_list: |
|
211 |
ref_addresses.append(format_string % key_addresses[reference]) |
|
212 |
flattened_references.append('\r'.join(ref_addresses)) |
|
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
213 |
string_key = '\x00'.join(key) |
2624.2.11
by Robert Collins
Review comments. |
214 |
lines.append("%s\x00%s\x00%s\x00%s\n" % (string_key, absent, |
2592.1.19
by Robert Collins
Node references are tab separated. |
215 |
'\t'.join(flattened_references), value)) |
2592.1.6
by Robert Collins
Record the number of node reference lists a particular index has. |
216 |
lines.append('\n') |
2592.1.42
by Robert Collins
Check the index length is as expected, when we have done preprocessing. |
217 |
result = StringIO(''.join(lines)) |
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
218 |
if expected_bytes and len(result.getvalue()) != expected_bytes: |
219 |
raise errors.BzrError('Failed index creation. Internal error:' |
|
220 |
' mismatched output length and expected length: %d %d' % |
|
221 |
(len(result.getvalue()), expected_bytes)) |
|
2592.1.6
by Robert Collins
Record the number of node reference lists a particular index has. |
222 |
return StringIO(''.join(lines)) |
2592.1.5
by Robert Collins
Trivial index reading. |
223 |
|
224 |
||
225 |
class GraphIndex(object): |
|
226 |
"""An index for data with embedded graphs.
|
|
2592.1.10
by Robert Collins
Make validate detect node reference parsing errors. |
227 |
|
228 |
The index maps keys to a list of key reference lists, and a value.
|
|
229 |
Each node has the same number of key reference lists. Each key reference
|
|
230 |
list can be empty or an arbitrary length. The value is an opaque NULL
|
|
2592.1.45
by Robert Collins
Tweak documentation as per Aaron's review. |
231 |
terminated string without any newlines. The storage of the index is
|
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
232 |
hidden in the interface: keys and key references are always tuples of
|
233 |
bytestrings, never the internal representation (e.g. dictionary offsets).
|
|
2592.1.30
by Robert Collins
Absent entries are not yeilded. |
234 |
|
235 |
It is presumed that the index will not be mutated - it is static data.
|
|
2592.1.34
by Robert Collins
Cleanup docs. |
236 |
|
2592.1.44
by Robert Collins
Remove some unneeded index iteration by checking if we have found all keys, and grammar improvements from Aaron's review. |
237 |
Successive iter_all_entries calls will read the entire index each time.
|
238 |
Additionally, iter_entries calls will read the index linearly until the
|
|
239 |
desired keys are found. XXX: This must be fixed before the index is
|
|
2592.1.34
by Robert Collins
Cleanup docs. |
240 |
suitable for production use. :XXX
|
2592.1.5
by Robert Collins
Trivial index reading. |
241 |
"""
|
242 |
||
2890.2.1
by Robert Collins
* ``bzrlib.index.GraphIndex`` now requires a size parameter to the |
243 |
def __init__(self, transport, name, size): |
2592.1.5
by Robert Collins
Trivial index reading. |
244 |
"""Open an index called name on transport.
|
245 |
||
246 |
:param transport: A bzrlib.transport.Transport.
|
|
247 |
:param name: A path to provide to transport API calls.
|
|
2890.2.1
by Robert Collins
* ``bzrlib.index.GraphIndex`` now requires a size parameter to the |
248 |
:param size: The size of the index in bytes. This is used for bisection
|
249 |
logic to perform partial index reads. While the size could be
|
|
250 |
obtained by statting the file this introduced an additional round
|
|
2890.2.8
by Robert Collins
Make the size of the index optionally None for the pack-names index. |
251 |
trip as well as requiring stat'able transports, both of which are
|
252 |
avoided by having it supplied. If size is None, then bisection
|
|
253 |
support will be disabled and accessing the index will just stream
|
|
254 |
all the data.
|
|
2592.1.5
by Robert Collins
Trivial index reading. |
255 |
"""
|
256 |
self._transport = transport |
|
257 |
self._name = name |
|
2890.2.16
by Robert Collins
Review feedback. |
258 |
# Becomes a dict of key:(value, reference-list-byte-locations) used by
|
259 |
# the bisection interface to store parsed but not resolved keys.
|
|
2890.2.6
by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface. |
260 |
self._bisect_nodes = None |
2890.2.16
by Robert Collins
Review feedback. |
261 |
# Becomes a dict of key:(value, reference-list-keys) which are ready to
|
262 |
# be returned directly to callers.
|
|
2624.2.2
by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram. |
263 |
self._nodes = None |
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
264 |
# a sorted list of slice-addresses for the parsed bytes of the file.
|
265 |
# e.g. (0,1) would mean that byte 0 is parsed.
|
|
2890.2.2
by Robert Collins
Opening an index creates a map for the parsed bytes. |
266 |
self._parsed_byte_map = [] |
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
267 |
# a sorted list of keys matching each slice address for parsed bytes
|
268 |
# e.g. (None, 'foo@bar') would mean that the first byte contained no
|
|
269 |
# key, and the end byte of the slice is the of the data for 'foo@bar'
|
|
270 |
self._parsed_key_map = [] |
|
2624.2.16
by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index. |
271 |
self._key_count = None |
2624.2.2
by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram. |
272 |
self._keys_by_offset = None |
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
273 |
self._nodes_by_key = None |
2890.2.1
by Robert Collins
* ``bzrlib.index.GraphIndex`` now requires a size parameter to the |
274 |
self._size = size |
2624.2.2
by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram. |
275 |
|
2592.3.176
by Robert Collins
Various pack refactorings. |
276 |
def __eq__(self, other): |
2592.3.215
by Robert Collins
Review feedback. |
277 |
"""Equal when self and other were created with the same parameters."""
|
2592.3.176
by Robert Collins
Various pack refactorings. |
278 |
return ( |
279 |
type(self) == type(other) and |
|
280 |
self._transport == other._transport and |
|
281 |
self._name == other._name and |
|
282 |
self._size == other._size) |
|
283 |
||
284 |
def __ne__(self, other): |
|
285 |
return not self.__eq__(other) |
|
286 |
||
2624.2.2
by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram. |
287 |
def _buffer_all(self): |
288 |
"""Buffer all the index data.
|
|
289 |
||
290 |
Mutates self._nodes and self.keys_by_offset.
|
|
2592.1.5
by Robert Collins
Trivial index reading. |
291 |
"""
|
2624.2.15
by Robert Collins
Add useful -Dindex flag. |
292 |
if 'index' in debug.debug_flags: |
293 |
mutter('Reading entire index %s', self._transport.abspath(self._name)) |
|
2592.1.27
by Robert Collins
Test missing end lines with non-empty indices. |
294 |
stream = self._transport.get(self._name) |
295 |
self._read_prefix(stream) |
|
2890.2.17
by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing. |
296 |
self._expected_elements = 3 + self._key_length |
2592.1.27
by Robert Collins
Test missing end lines with non-empty indices. |
297 |
line_count = 0 |
2624.2.2
by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram. |
298 |
# raw data keyed by offset
|
299 |
self._keys_by_offset = {} |
|
300 |
# ready-to-return key:value or key:value, node_ref_lists
|
|
301 |
self._nodes = {} |
|
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
302 |
self._nodes_by_key = {} |
2592.1.27
by Robert Collins
Test missing end lines with non-empty indices. |
303 |
trailers = 0 |
304 |
pos = stream.tell() |
|
2890.2.17
by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing. |
305 |
lines = stream.read().split('\n') |
306 |
del lines[-1] |
|
307 |
_, _, _, trailers = self._parse_lines(lines, pos) |
|
2624.2.2
by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram. |
308 |
for key, absent, references, value in self._keys_by_offset.itervalues(): |
2592.1.30
by Robert Collins
Absent entries are not yeilded. |
309 |
if absent: |
310 |
continue
|
|
2592.1.28
by Robert Collins
Basic two pass iter_all_entries. |
311 |
# resolve references:
|
312 |
if self.node_ref_lists: |
|
2890.2.17
by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing. |
313 |
node_value = (value, self._resolve_references(references)) |
2592.1.28
by Robert Collins
Basic two pass iter_all_entries. |
314 |
else: |
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
315 |
node_value = value |
316 |
self._nodes[key] = node_value |
|
317 |
if self._key_length > 1: |
|
318 |
subkey = list(reversed(key[:-1])) |
|
319 |
key_dict = self._nodes_by_key |
|
320 |
if self.node_ref_lists: |
|
321 |
key_value = key, node_value[0], node_value[1] |
|
322 |
else: |
|
323 |
key_value = key, node_value |
|
324 |
# possibly should do this on-demand, but it seems likely it is
|
|
325 |
# always wanted
|
|
2624.2.11
by Robert Collins
Review comments. |
326 |
# For a key of (foo, bar, baz) create
|
327 |
# _nodes_by_key[foo][bar][baz] = key_value
|
|
328 |
for subkey in key[:-1]: |
|
329 |
key_dict = key_dict.setdefault(subkey, {}) |
|
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
330 |
key_dict[key[-1]] = key_value |
2624.2.16
by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index. |
331 |
# cache the keys for quick set intersections
|
2592.3.54
by Robert Collins
Fix remaining performance discrepancy with regular repositories. |
332 |
self._keys = set(self._nodes) |
2592.1.27
by Robert Collins
Test missing end lines with non-empty indices. |
333 |
if trailers != 1: |
334 |
# there must be one line - the empty trailer line.
|
|
335 |
raise errors.BadIndexData(self) |
|
336 |
||
2624.2.2
by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram. |
337 |
def iter_all_entries(self): |
338 |
"""Iterate over all keys within the index.
|
|
339 |
||
2592.5.1
by Martin Pool
Fix docstrings for Index.iter_entries etc |
340 |
:return: An iterable of (index, key, value) or (index, key, value, reference_lists).
|
2624.2.2
by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram. |
341 |
The former tuple is used when there are no reference lists in the
|
342 |
index, making the API compatible with simple key:value index types.
|
|
343 |
There is no defined order for the result iteration - it will be in
|
|
344 |
the most efficient order for the index.
|
|
345 |
"""
|
|
2745.1.1
by Robert Collins
Add a number of -Devil checkpoints. |
346 |
if 'evil' in debug.debug_flags: |
2592.3.112
by Robert Collins
Various fixups found dogfooding. |
347 |
trace.mutter_callsite(3, |
2745.1.2
by Robert Collins
Ensure mutter_callsite is not directly called on a lazy_load object, to make the stacklevel parameter work correctly. |
348 |
"iter_all_entries scales with size of history.") |
2624.2.2
by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram. |
349 |
if self._nodes is None: |
350 |
self._buffer_all() |
|
351 |
if self.node_ref_lists: |
|
352 |
for key, (value, node_ref_lists) in self._nodes.iteritems(): |
|
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
353 |
yield self, key, value, node_ref_lists |
2624.2.2
by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram. |
354 |
else: |
355 |
for key, value in self._nodes.iteritems(): |
|
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
356 |
yield self, key, value |
2624.2.2
by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram. |
357 |
|
2592.1.27
by Robert Collins
Test missing end lines with non-empty indices. |
358 |
def _read_prefix(self, stream): |
359 |
signature = stream.read(len(self._signature())) |
|
360 |
if not signature == self._signature(): |
|
361 |
raise errors.BadIndexFormatSignature(self._name, GraphIndex) |
|
362 |
options_line = stream.readline() |
|
363 |
if not options_line.startswith(_OPTION_NODE_REFS): |
|
364 |
raise errors.BadIndexOptions(self) |
|
365 |
try: |
|
366 |
self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):-1]) |
|
367 |
except ValueError: |
|
368 |
raise errors.BadIndexOptions(self) |
|
2624.2.8
by Robert Collins
Explicitly mark the number of keys elements in use in GraphIndex files. |
369 |
options_line = stream.readline() |
370 |
if not options_line.startswith(_OPTION_KEY_ELEMENTS): |
|
371 |
raise errors.BadIndexOptions(self) |
|
372 |
try: |
|
373 |
self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):-1]) |
|
374 |
except ValueError: |
|
375 |
raise errors.BadIndexOptions(self) |
|
2624.2.16
by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index. |
376 |
options_line = stream.readline() |
377 |
if not options_line.startswith(_OPTION_LEN): |
|
378 |
raise errors.BadIndexOptions(self) |
|
379 |
try: |
|
380 |
self._key_count = int(options_line[len(_OPTION_LEN):-1]) |
|
381 |
except ValueError: |
|
382 |
raise errors.BadIndexOptions(self) |
|
2592.1.5
by Robert Collins
Trivial index reading. |
383 |
|
2890.2.6
by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface. |
384 |
def _resolve_references(self, references): |
2890.2.16
by Robert Collins
Review feedback. |
385 |
"""Return the resolved key references for references.
|
386 |
|
|
387 |
References are resolved by looking up the location of the key in the
|
|
388 |
_keys_by_offset map and substituting the key name, preserving ordering.
|
|
389 |
||
390 |
:param references: An iterable of iterables of key locations. e.g.
|
|
391 |
[[123, 456], [123]]
|
|
392 |
:return: A tuple of tuples of keys.
|
|
393 |
"""
|
|
2890.2.6
by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface. |
394 |
node_refs = [] |
395 |
for ref_list in references: |
|
396 |
node_refs.append(tuple([self._keys_by_offset[ref][0] for ref in ref_list])) |
|
397 |
return tuple(node_refs) |
|
398 |
||
2890.2.11
by Robert Collins
Bisection improvements after integrating with packs. |
399 |
def _find_index(self, range_map, key): |
400 |
"""Helper for the _parsed_*_index calls.
|
|
401 |
||
402 |
Given a range map - [(start, end), ...], finds the index of the range
|
|
403 |
in the map for key if it is in the map, and if it is not there, the
|
|
404 |
immediately preceeding range in the map.
|
|
405 |
"""
|
|
406 |
result = bisect_right(range_map, key) - 1 |
|
407 |
if result + 1 < len(range_map): |
|
408 |
# check the border condition, it may be in result + 1
|
|
409 |
if range_map[result + 1][0] == key[0]: |
|
410 |
return result + 1 |
|
411 |
return result |
|
412 |
||
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
413 |
def _parsed_byte_index(self, offset): |
414 |
"""Return the index of the entry immediately before offset.
|
|
415 |
||
416 |
e.g. if the parsed map has regions 0,10 and 11,12 parsed, meaning that
|
|
417 |
there is one unparsed byte (the 11th, addressed as[10]). then:
|
|
418 |
asking for 0 will return 0
|
|
419 |
asking for 10 will return 0
|
|
420 |
asking for 11 will return 1
|
|
421 |
asking for 12 will return 1
|
|
422 |
"""
|
|
423 |
key = (offset, 0) |
|
2890.2.11
by Robert Collins
Bisection improvements after integrating with packs. |
424 |
return self._find_index(self._parsed_byte_map, key) |
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
425 |
|
426 |
def _parsed_key_index(self, key): |
|
427 |
"""Return the index of the entry immediately before key.
|
|
428 |
||
429 |
e.g. if the parsed map has regions (None, 'a') and ('b','c') parsed,
|
|
430 |
meaning that keys from None to 'a' inclusive, and 'b' to 'c' inclusive
|
|
431 |
have been parsed, then:
|
|
432 |
asking for '' will return 0
|
|
433 |
asking for 'a' will return 0
|
|
434 |
asking for 'b' will return 1
|
|
435 |
asking for 'e' will return 1
|
|
436 |
"""
|
|
2890.2.11
by Robert Collins
Bisection improvements after integrating with packs. |
437 |
search_key = (key, None) |
438 |
return self._find_index(self._parsed_key_map, search_key) |
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
439 |
|
440 |
def _is_parsed(self, offset): |
|
441 |
"""Returns True if offset has been parsed."""
|
|
442 |
index = self._parsed_byte_index(offset) |
|
443 |
if index == len(self._parsed_byte_map): |
|
444 |
return offset < self._parsed_byte_map[index - 1][1] |
|
445 |
start, end = self._parsed_byte_map[index] |
|
446 |
return offset >= start and offset < end |
|
447 |
||
2890.2.7
by Robert Collins
* Pack indices are now partially parsed for specific key lookup using a |
448 |
def _iter_entries_from_total_buffer(self, keys): |
449 |
"""Iterate over keys when the entire index is parsed."""
|
|
2592.3.54
by Robert Collins
Fix remaining performance discrepancy with regular repositories. |
450 |
keys = keys.intersection(self._keys) |
2624.2.3
by Robert Collins
Make GraphIndex.iter_entries do hash lookups rather than table scans. |
451 |
if self.node_ref_lists: |
452 |
for key in keys: |
|
453 |
value, node_refs = self._nodes[key] |
|
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
454 |
yield self, key, value, node_refs |
2624.2.3
by Robert Collins
Make GraphIndex.iter_entries do hash lookups rather than table scans. |
455 |
else: |
456 |
for key in keys: |
|
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
457 |
yield self, key, self._nodes[key] |
2592.1.7
by Robert Collins
A validate that goes boom. |
458 |
|
2890.2.7
by Robert Collins
* Pack indices are now partially parsed for specific key lookup using a |
459 |
def iter_entries(self, keys): |
460 |
"""Iterate over keys within the index.
|
|
461 |
||
462 |
:param keys: An iterable providing the keys to be retrieved.
|
|
463 |
:return: An iterable as per iter_all_entries, but restricted to the
|
|
464 |
keys supplied. No additional keys will be returned, and every
|
|
465 |
key supplied that is in the index will be returned.
|
|
466 |
"""
|
|
2890.2.15
by Robert Collins
Corner case when parsing repeated sections - the bottom section of a region may not be parsed, so we need to manually advance past that. |
467 |
# PERFORMANCE TODO: parse and bisect all remaining data at some
|
468 |
# threshold of total-index processing/get calling layers that expect to
|
|
469 |
# read the entire index to use the iter_all_entries method instead.
|
|
2890.2.7
by Robert Collins
* Pack indices are now partially parsed for specific key lookup using a |
470 |
keys = set(keys) |
471 |
if not keys: |
|
472 |
return [] |
|
2890.2.8
by Robert Collins
Make the size of the index optionally None for the pack-names index. |
473 |
if self._size is None and self._nodes is None: |
474 |
self._buffer_all() |
|
2890.2.7
by Robert Collins
* Pack indices are now partially parsed for specific key lookup using a |
475 |
if self._nodes is not None: |
476 |
return self._iter_entries_from_total_buffer(keys) |
|
477 |
else: |
|
478 |
return (result[1] for result in bisect_multi_bytes( |
|
2890.2.18
by Robert Collins
Review feedback. |
479 |
self._lookup_keys_via_location, self._size, keys)) |
2890.2.7
by Robert Collins
* Pack indices are now partially parsed for specific key lookup using a |
480 |
|
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
481 |
def iter_entries_prefix(self, keys): |
482 |
"""Iterate over keys within the index using prefix matching.
|
|
483 |
||
484 |
Prefix matching is applied within the tuple of a key, not to within
|
|
485 |
the bytestring of each key element. e.g. if you have the keys ('foo',
|
|
486 |
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
|
|
487 |
only the former key is returned.
|
|
488 |
||
2890.2.6
by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface. |
489 |
WARNING: Note that this method currently causes a full index parse
|
490 |
unconditionally (which is reasonably appropriate as it is a means for
|
|
491 |
thunking many small indices into one larger one and still supplies
|
|
492 |
iter_all_entries at the thunk layer).
|
|
493 |
||
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
494 |
:param keys: An iterable providing the key prefixes to be retrieved.
|
495 |
Each key prefix takes the form of a tuple the length of a key, but
|
|
496 |
with the last N elements 'None' rather than a regular bytestring.
|
|
497 |
The first element cannot be 'None'.
|
|
498 |
:return: An iterable as per iter_all_entries, but restricted to the
|
|
499 |
keys with a matching prefix to those supplied. No additional keys
|
|
500 |
will be returned, and every match that is in the index will be
|
|
501 |
returned.
|
|
502 |
"""
|
|
503 |
keys = set(keys) |
|
504 |
if not keys: |
|
505 |
return
|
|
506 |
# load data - also finds key lengths
|
|
507 |
if self._nodes is None: |
|
508 |
self._buffer_all() |
|
509 |
if self._key_length == 1: |
|
510 |
for key in keys: |
|
511 |
# sanity check
|
|
512 |
if key[0] is None: |
|
513 |
raise errors.BadIndexKey(key) |
|
514 |
if len(key) != self._key_length: |
|
515 |
raise errors.BadIndexKey(key) |
|
516 |
if self.node_ref_lists: |
|
517 |
value, node_refs = self._nodes[key] |
|
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
518 |
yield self, key, value, node_refs |
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
519 |
else: |
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
520 |
yield self, key, self._nodes[key] |
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
521 |
return
|
522 |
for key in keys: |
|
523 |
# sanity check
|
|
524 |
if key[0] is None: |
|
525 |
raise errors.BadIndexKey(key) |
|
526 |
if len(key) != self._key_length: |
|
527 |
raise errors.BadIndexKey(key) |
|
528 |
# find what it refers to:
|
|
529 |
key_dict = self._nodes_by_key |
|
530 |
elements = list(key) |
|
2624.2.11
by Robert Collins
Review comments. |
531 |
# find the subdict whose contents should be returned.
|
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
532 |
try: |
533 |
while len(elements) and elements[0] is not None: |
|
534 |
key_dict = key_dict[elements[0]] |
|
535 |
elements.pop(0) |
|
536 |
except KeyError: |
|
537 |
# a non-existant lookup.
|
|
538 |
continue
|
|
539 |
if len(elements): |
|
540 |
dicts = [key_dict] |
|
541 |
while dicts: |
|
542 |
key_dict = dicts.pop(-1) |
|
543 |
# can't be empty or would not exist
|
|
544 |
item, value = key_dict.iteritems().next() |
|
545 |
if type(value) == dict: |
|
546 |
# push keys
|
|
547 |
dicts.extend(key_dict.itervalues()) |
|
548 |
else: |
|
549 |
# yield keys
|
|
550 |
for value in key_dict.itervalues(): |
|
2624.2.11
by Robert Collins
Review comments. |
551 |
# each value is the key:value:node refs tuple
|
552 |
# ready to yield.
|
|
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
553 |
yield (self, ) + value |
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
554 |
else: |
2624.2.11
by Robert Collins
Review comments. |
555 |
# the last thing looked up was a terminal element
|
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
556 |
yield (self, ) + key_dict |
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
557 |
|
2624.2.16
by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index. |
558 |
def key_count(self): |
559 |
"""Return an estimate of the number of keys in this index.
|
|
560 |
|
|
561 |
For GraphIndex the estimate is exact.
|
|
562 |
"""
|
|
563 |
if self._key_count is None: |
|
2979.1.1
by Robert Collins
Use the GraphIndex header to answer key_count queries rather than parsing the entire index unnecessarily. |
564 |
self._read_and_parse([_HEADER_READV]) |
2624.2.16
by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index. |
565 |
return self._key_count |
566 |
||
2890.2.18
by Robert Collins
Review feedback. |
567 |
def _lookup_keys_via_location(self, location_keys): |
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
568 |
"""Public interface for implementing bisection.
|
569 |
||
2890.2.6
by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface. |
570 |
If _buffer_all has been called, then all the data for the index is in
|
571 |
memory, and this method should not be called, as it uses a separate
|
|
572 |
cache because it cannot pre-resolve all indices, which buffer_all does
|
|
573 |
for performance.
|
|
574 |
||
2890.2.16
by Robert Collins
Review feedback. |
575 |
:param location_keys: A list of location(byte offset), key tuples.
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
576 |
:return: A list of (location_key, result) tuples as expected by
|
577 |
bzrlib.bisect_multi.bisect_multi_bytes.
|
|
578 |
"""
|
|
579 |
# Possible improvements:
|
|
580 |
# - only bisect lookup each key once
|
|
581 |
# - sort the keys first, and use that to reduce the bisection window
|
|
582 |
# -----
|
|
583 |
# this progresses in three parts:
|
|
584 |
# read data
|
|
585 |
# parse it
|
|
586 |
# attempt to answer the question from the now in memory data.
|
|
587 |
# build the readv request
|
|
588 |
# for each location, ask for 800 bytes - much more than rows we've seen
|
|
589 |
# anywhere.
|
|
590 |
readv_ranges = [] |
|
591 |
for location, key in location_keys: |
|
592 |
# can we answer from cache?
|
|
2911.3.1
by Robert Collins
(robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins). |
593 |
if self._bisect_nodes and key in self._bisect_nodes: |
594 |
# We have the key parsed.
|
|
595 |
continue
|
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
596 |
index = self._parsed_key_index(key) |
597 |
if (len(self._parsed_key_map) and |
|
598 |
self._parsed_key_map[index][0] <= key and |
|
2911.3.1
by Robert Collins
(robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins). |
599 |
(self._parsed_key_map[index][1] >= key or |
2890.2.11
by Robert Collins
Bisection improvements after integrating with packs. |
600 |
# end of the file has been parsed
|
601 |
self._parsed_byte_map[index][1] == self._size)): |
|
2911.3.1
by Robert Collins
(robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins). |
602 |
# the key has been parsed, so no lookup is needed even if its
|
603 |
# not present.
|
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
604 |
continue
|
2890.2.11
by Robert Collins
Bisection improvements after integrating with packs. |
605 |
# - if we have examined this part of the file already - yes
|
606 |
index = self._parsed_byte_index(location) |
|
607 |
if (len(self._parsed_byte_map) and |
|
608 |
self._parsed_byte_map[index][0] <= location and |
|
609 |
self._parsed_byte_map[index][1] > location): |
|
610 |
# the byte region has been parsed, so no read is needed.
|
|
611 |
continue
|
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
612 |
length = 800 |
613 |
if location + length > self._size: |
|
614 |
length = self._size - location |
|
615 |
# todo, trim out parsed locations.
|
|
616 |
if length > 0: |
|
617 |
readv_ranges.append((location, length)) |
|
618 |
# read the header if needed
|
|
2890.2.6
by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface. |
619 |
if self._bisect_nodes is None: |
2979.1.1
by Robert Collins
Use the GraphIndex header to answer key_count queries rather than parsing the entire index unnecessarily. |
620 |
readv_ranges.append(_HEADER_READV) |
2890.2.6
by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface. |
621 |
self._read_and_parse(readv_ranges) |
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
622 |
# generate results:
|
623 |
# - figure out <, >, missing, present
|
|
624 |
# - result present references so we can return them.
|
|
625 |
result = [] |
|
2890.2.6
by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface. |
626 |
# keys that we cannot answer until we resolve references
|
627 |
pending_references = [] |
|
628 |
pending_locations = set() |
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
629 |
for location, key in location_keys: |
630 |
# can we answer from cache?
|
|
2911.3.1
by Robert Collins
(robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins). |
631 |
if key in self._bisect_nodes: |
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
632 |
# the key has been parsed, so no lookup is needed
|
2911.3.1
by Robert Collins
(robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins). |
633 |
if self.node_ref_lists: |
634 |
# the references may not have been all parsed.
|
|
635 |
value, refs = self._bisect_nodes[key] |
|
636 |
wanted_locations = [] |
|
637 |
for ref_list in refs: |
|
638 |
for ref in ref_list: |
|
639 |
if ref not in self._keys_by_offset: |
|
640 |
wanted_locations.append(ref) |
|
641 |
if wanted_locations: |
|
642 |
pending_locations.update(wanted_locations) |
|
643 |
pending_references.append((location, key)) |
|
644 |
continue
|
|
645 |
result.append(((location, key), (self, key, |
|
646 |
value, self._resolve_references(refs)))) |
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
647 |
else: |
2911.3.1
by Robert Collins
(robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins). |
648 |
result.append(((location, key), |
649 |
(self, key, self._bisect_nodes[key]))) |
|
650 |
continue
|
|
651 |
else: |
|
652 |
# has the region the key should be in, been parsed?
|
|
653 |
index = self._parsed_key_index(key) |
|
654 |
if (self._parsed_key_map[index][0] <= key and |
|
655 |
(self._parsed_key_map[index][1] >= key or |
|
656 |
# end of the file has been parsed
|
|
657 |
self._parsed_byte_map[index][1] == self._size)): |
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
658 |
result.append(((location, key), False)) |
2911.3.1
by Robert Collins
(robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins). |
659 |
continue
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
660 |
# no, is the key above or below the probed location:
|
661 |
# get the range of the probed & parsed location
|
|
662 |
index = self._parsed_byte_index(location) |
|
663 |
# if the key is below the start of the range, its below
|
|
664 |
if key < self._parsed_key_map[index][0]: |
|
665 |
direction = -1 |
|
666 |
else: |
|
667 |
direction = +1 |
|
668 |
result.append(((location, key), direction)) |
|
2890.2.6
by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface. |
669 |
readv_ranges = [] |
670 |
# lookup data to resolve references
|
|
671 |
for location in pending_locations: |
|
672 |
length = 800 |
|
673 |
if location + length > self._size: |
|
674 |
length = self._size - location |
|
675 |
# TODO: trim out parsed locations (e.g. if the 800 is into the
|
|
2890.2.16
by Robert Collins
Review feedback. |
676 |
# parsed region trim it, and dont use the adjust_for_latency
|
2890.2.6
by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface. |
677 |
# facility)
|
678 |
if length > 0: |
|
679 |
readv_ranges.append((location, length)) |
|
680 |
self._read_and_parse(readv_ranges) |
|
681 |
for location, key in pending_references: |
|
682 |
# answer key references we had to look-up-late.
|
|
683 |
index = self._parsed_key_index(key) |
|
684 |
value, refs = self._bisect_nodes[key] |
|
685 |
result.append(((location, key), (self, key, |
|
686 |
value, self._resolve_references(refs)))) |
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
687 |
return result |
688 |
||
689 |
def _parse_header_from_bytes(self, bytes): |
|
690 |
"""Parse the header from a region of bytes.
|
|
691 |
||
692 |
:param bytes: The data to parse.
|
|
693 |
:return: An offset, data tuple such as readv yields, for the unparsed
|
|
694 |
data. (which may length 0).
|
|
695 |
"""
|
|
696 |
signature = bytes[0:len(self._signature())] |
|
697 |
if not signature == self._signature(): |
|
698 |
raise errors.BadIndexFormatSignature(self._name, GraphIndex) |
|
699 |
lines = bytes[len(self._signature()):].splitlines() |
|
700 |
options_line = lines[0] |
|
701 |
if not options_line.startswith(_OPTION_NODE_REFS): |
|
702 |
raise errors.BadIndexOptions(self) |
|
703 |
try: |
|
704 |
self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):]) |
|
705 |
except ValueError: |
|
706 |
raise errors.BadIndexOptions(self) |
|
707 |
options_line = lines[1] |
|
708 |
if not options_line.startswith(_OPTION_KEY_ELEMENTS): |
|
709 |
raise errors.BadIndexOptions(self) |
|
710 |
try: |
|
711 |
self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):]) |
|
712 |
except ValueError: |
|
713 |
raise errors.BadIndexOptions(self) |
|
714 |
options_line = lines[2] |
|
715 |
if not options_line.startswith(_OPTION_LEN): |
|
716 |
raise errors.BadIndexOptions(self) |
|
717 |
try: |
|
718 |
self._key_count = int(options_line[len(_OPTION_LEN):]) |
|
719 |
except ValueError: |
|
720 |
raise errors.BadIndexOptions(self) |
|
721 |
# calculate the bytes we have processed
|
|
722 |
header_end = (len(signature) + len(lines[0]) + len(lines[1]) + |
|
723 |
len(lines[2]) + 3) |
|
724 |
self._parsed_bytes(0, None, header_end, None) |
|
725 |
# setup parsing state
|
|
726 |
self._expected_elements = 3 + self._key_length |
|
727 |
# raw data keyed by offset
|
|
728 |
self._keys_by_offset = {} |
|
2890.2.6
by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface. |
729 |
# keys with the value and node references
|
730 |
self._bisect_nodes = {} |
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
731 |
return header_end, bytes[header_end:] |
732 |
||
733 |
def _parse_region(self, offset, data): |
|
734 |
"""Parse node data returned from a readv operation.
|
|
735 |
||
736 |
:param offset: The byte offset the data starts at.
|
|
737 |
:param data: The data to parse.
|
|
738 |
"""
|
|
739 |
# trim the data.
|
|
740 |
# end first:
|
|
741 |
end = offset + len(data) |
|
2890.2.15
by Robert Collins
Corner case when parsing repeated sections - the bottom section of a region may not be parsed, so we need to manually advance past that. |
742 |
high_parsed = offset |
2890.2.14
by Robert Collins
Parse more than one segment of data from a single readv response if needed. |
743 |
while True: |
744 |
# Trivial test - if the current index's end is within the
|
|
745 |
# low-matching parsed range, we're done.
|
|
2890.2.15
by Robert Collins
Corner case when parsing repeated sections - the bottom section of a region may not be parsed, so we need to manually advance past that. |
746 |
index = self._parsed_byte_index(high_parsed) |
2890.2.14
by Robert Collins
Parse more than one segment of data from a single readv response if needed. |
747 |
if end < self._parsed_byte_map[index][1]: |
748 |
return
|
|
2890.2.15
by Robert Collins
Corner case when parsing repeated sections - the bottom section of a region may not be parsed, so we need to manually advance past that. |
749 |
# print "[%d:%d]" % (offset, end), \
|
750 |
# self._parsed_byte_map[index:index + 2]
|
|
751 |
high_parsed, last_segment = self._parse_segment( |
|
752 |
offset, data, end, index) |
|
753 |
if last_segment: |
|
2890.2.14
by Robert Collins
Parse more than one segment of data from a single readv response if needed. |
754 |
return
|
755 |
||
756 |
def _parse_segment(self, offset, data, end, index): |
|
757 |
"""Parse one segment of data.
|
|
758 |
||
759 |
:param offset: Where 'data' begins in the file.
|
|
760 |
:param data: Some data to parse a segment of.
|
|
761 |
:param end: Where data ends
|
|
762 |
:param index: The current index into the parsed bytes map.
|
|
763 |
:return: True if the parsed segment is the last possible one in the
|
|
764 |
range of data.
|
|
2890.2.15
by Robert Collins
Corner case when parsing repeated sections - the bottom section of a region may not be parsed, so we need to manually advance past that. |
765 |
:return: high_parsed_byte, last_segment.
|
766 |
high_parsed_byte is the location of the highest parsed byte in this
|
|
767 |
segment, last_segment is True if the parsed segment is the last
|
|
768 |
possible one in the data block.
|
|
2890.2.14
by Robert Collins
Parse more than one segment of data from a single readv response if needed. |
769 |
"""
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
770 |
# default is to use all data
|
771 |
trim_end = None |
|
772 |
# accomodate overlap with data before this.
|
|
773 |
if offset < self._parsed_byte_map[index][1]: |
|
774 |
# overlaps the lower parsed region
|
|
775 |
# skip the parsed data
|
|
776 |
trim_start = self._parsed_byte_map[index][1] - offset |
|
777 |
# don't trim the start for \n
|
|
778 |
start_adjacent = True |
|
779 |
elif offset == self._parsed_byte_map[index][1]: |
|
780 |
# abuts the lower parsed region
|
|
781 |
# use all data
|
|
782 |
trim_start = None |
|
783 |
# do not trim anything
|
|
784 |
start_adjacent = True |
|
785 |
else: |
|
786 |
# does not overlap the lower parsed region
|
|
787 |
# use all data
|
|
788 |
trim_start = None |
|
789 |
# but trim the leading \n
|
|
790 |
start_adjacent = False |
|
791 |
if end == self._size: |
|
792 |
# lines up to the end of all data:
|
|
793 |
# use it all
|
|
794 |
trim_end = None |
|
795 |
# do not strip to the last \n
|
|
796 |
end_adjacent = True |
|
2890.2.14
by Robert Collins
Parse more than one segment of data from a single readv response if needed. |
797 |
last_segment = True |
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
798 |
elif index + 1 == len(self._parsed_byte_map): |
799 |
# at the end of the parsed data
|
|
800 |
# use it all
|
|
801 |
trim_end = None |
|
802 |
# but strip to the last \n
|
|
803 |
end_adjacent = False |
|
2890.2.14
by Robert Collins
Parse more than one segment of data from a single readv response if needed. |
804 |
last_segment = True |
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
805 |
elif end == self._parsed_byte_map[index + 1][0]: |
806 |
# buts up against the next parsed region
|
|
807 |
# use it all
|
|
808 |
trim_end = None |
|
809 |
# do not strip to the last \n
|
|
810 |
end_adjacent = True |
|
2890.2.14
by Robert Collins
Parse more than one segment of data from a single readv response if needed. |
811 |
last_segment = True |
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
812 |
elif end > self._parsed_byte_map[index + 1][0]: |
813 |
# overlaps into the next parsed region
|
|
814 |
# only consider the unparsed data
|
|
815 |
trim_end = self._parsed_byte_map[index + 1][0] - offset |
|
816 |
# do not strip to the last \n as we know its an entire record
|
|
817 |
end_adjacent = True |
|
2890.2.14
by Robert Collins
Parse more than one segment of data from a single readv response if needed. |
818 |
last_segment = end < self._parsed_byte_map[index + 1][1] |
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
819 |
else: |
820 |
# does not overlap into the next region
|
|
821 |
# use it all
|
|
822 |
trim_end = None |
|
823 |
# but strip to the last \n
|
|
824 |
end_adjacent = False |
|
2890.2.14
by Robert Collins
Parse more than one segment of data from a single readv response if needed. |
825 |
last_segment = True |
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
826 |
# now find bytes to discard if needed
|
827 |
if not start_adjacent: |
|
828 |
# work around python bug in rfind
|
|
829 |
if trim_start is None: |
|
830 |
trim_start = data.find('\n') + 1 |
|
831 |
else: |
|
832 |
trim_start = data.find('\n', trim_start) + 1 |
|
833 |
assert trim_start != 0, 'no \n was present' |
|
834 |
# print 'removing start', offset, trim_start, repr(data[:trim_start])
|
|
835 |
if not end_adjacent: |
|
836 |
# work around python bug in rfind
|
|
837 |
if trim_end is None: |
|
838 |
trim_end = data.rfind('\n') + 1 |
|
839 |
else: |
|
840 |
trim_end = data.rfind('\n', None, trim_end) + 1 |
|
841 |
assert trim_end != 0, 'no \n was present' |
|
842 |
# print 'removing end', offset, trim_end, repr(data[trim_end:])
|
|
843 |
# adjust offset and data to the parseable data.
|
|
2890.2.11
by Robert Collins
Bisection improvements after integrating with packs. |
844 |
trimmed_data = data[trim_start:trim_end] |
2890.2.15
by Robert Collins
Corner case when parsing repeated sections - the bottom section of a region may not be parsed, so we need to manually advance past that. |
845 |
assert trimmed_data, 'read unneeded data [%d:%d] from [%d:%d]' % ( |
846 |
trim_start, trim_end, offset, offset + len(data)) |
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
847 |
if trim_start: |
848 |
offset += trim_start |
|
2890.2.11
by Robert Collins
Bisection improvements after integrating with packs. |
849 |
# print "parsing", repr(trimmed_data)
|
2890.2.10
by Robert Collins
Add test coverage to ensure \r's are not mangled by bisection parsing. |
850 |
# splitlines mangles the \r delimiters.. don't use it.
|
2890.2.11
by Robert Collins
Bisection improvements after integrating with packs. |
851 |
lines = trimmed_data.split('\n') |
2890.2.9
by Robert Collins
Don't use splitlines for index data parsing, we embed \r. |
852 |
del lines[-1] |
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
853 |
pos = offset |
2890.2.17
by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing. |
854 |
first_key, last_key, nodes, _ = self._parse_lines(lines, pos) |
855 |
for key, value in nodes: |
|
856 |
self._bisect_nodes[key] = value |
|
857 |
self._parsed_bytes(offset, first_key, |
|
858 |
offset + len(trimmed_data), last_key) |
|
859 |
return offset + len(trimmed_data), last_segment |
|
860 |
||
861 |
def _parse_lines(self, lines, pos): |
|
862 |
key = None |
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
863 |
first_key = None |
2890.2.17
by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing. |
864 |
trailers = 0 |
865 |
nodes = [] |
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
866 |
for line in lines: |
867 |
if line == '': |
|
868 |
# must be at the end
|
|
2890.2.17
by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing. |
869 |
if self._size: |
870 |
assert self._size == pos + 1, "%s %s" % (self._size, pos) |
|
871 |
trailers += 1 |
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
872 |
continue
|
873 |
elements = line.split('\0') |
|
874 |
if len(elements) != self._expected_elements: |
|
875 |
raise errors.BadIndexData(self) |
|
876 |
# keys are tuples
|
|
877 |
key = tuple(elements[:self._key_length]) |
|
878 |
if first_key is None: |
|
879 |
first_key = key |
|
880 |
absent, references, value = elements[-3:] |
|
881 |
ref_lists = [] |
|
882 |
for ref_string in references.split('\t'): |
|
883 |
ref_lists.append(tuple([ |
|
884 |
int(ref) for ref in ref_string.split('\r') if ref |
|
885 |
]))
|
|
886 |
ref_lists = tuple(ref_lists) |
|
887 |
self._keys_by_offset[pos] = (key, absent, ref_lists, value) |
|
888 |
pos += len(line) + 1 # +1 for the \n |
|
2890.2.6
by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface. |
889 |
if absent: |
890 |
continue
|
|
891 |
if self.node_ref_lists: |
|
892 |
node_value = (value, ref_lists) |
|
893 |
else: |
|
894 |
node_value = value |
|
2890.2.17
by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing. |
895 |
nodes.append((key, node_value)) |
2890.2.6
by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface. |
896 |
# print "parsed ", key
|
2890.2.17
by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing. |
897 |
return first_key, key, nodes, trailers |
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
898 |
|
899 |
def _parsed_bytes(self, start, start_key, end, end_key): |
|
900 |
"""Mark the bytes from start to end as parsed.
|
|
901 |
||
902 |
Calling self._parsed_bytes(1,2) will mark one byte (the one at offset
|
|
903 |
1) as parsed.
|
|
904 |
||
905 |
:param start: The start of the parsed region.
|
|
906 |
:param end: The end of the parsed region.
|
|
907 |
"""
|
|
2890.2.11
by Robert Collins
Bisection improvements after integrating with packs. |
908 |
index = self._parsed_byte_index(start) |
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
909 |
new_value = (start, end) |
910 |
new_key = (start_key, end_key) |
|
2890.2.11
by Robert Collins
Bisection improvements after integrating with packs. |
911 |
if index == -1: |
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
912 |
# first range parsed is always the beginning.
|
913 |
self._parsed_byte_map.insert(index, new_value) |
|
914 |
self._parsed_key_map.insert(index, new_key) |
|
2890.2.11
by Robert Collins
Bisection improvements after integrating with packs. |
915 |
return
|
916 |
# four cases:
|
|
917 |
# new region
|
|
918 |
# extend lower region
|
|
919 |
# extend higher region
|
|
920 |
# combine two regions
|
|
921 |
if (index + 1 < len(self._parsed_byte_map) and |
|
922 |
self._parsed_byte_map[index][1] == start and |
|
923 |
self._parsed_byte_map[index + 1][0] == end): |
|
924 |
# combine two regions
|
|
925 |
self._parsed_byte_map[index] = (self._parsed_byte_map[index][0], |
|
926 |
self._parsed_byte_map[index + 1][1]) |
|
927 |
self._parsed_key_map[index] = (self._parsed_key_map[index][0], |
|
928 |
self._parsed_key_map[index + 1][1]) |
|
2890.2.12
by Robert Collins
More index tweaks. |
929 |
del self._parsed_byte_map[index + 1] |
930 |
del self._parsed_key_map[index + 1] |
|
2890.2.11
by Robert Collins
Bisection improvements after integrating with packs. |
931 |
elif self._parsed_byte_map[index][1] == start: |
932 |
# extend the lower entry
|
|
933 |
self._parsed_byte_map[index] = ( |
|
934 |
self._parsed_byte_map[index][0], end) |
|
935 |
self._parsed_key_map[index] = ( |
|
936 |
self._parsed_key_map[index][0], end_key) |
|
937 |
elif (index + 1 < len(self._parsed_byte_map) and |
|
938 |
self._parsed_byte_map[index + 1][0] == end): |
|
939 |
# extend the higher entry
|
|
940 |
self._parsed_byte_map[index + 1] = ( |
|
941 |
start, self._parsed_byte_map[index + 1][1]) |
|
942 |
self._parsed_key_map[index + 1] = ( |
|
943 |
start_key, self._parsed_key_map[index + 1][1]) |
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
944 |
else: |
2890.2.11
by Robert Collins
Bisection improvements after integrating with packs. |
945 |
# new entry
|
946 |
self._parsed_byte_map.insert(index + 1, new_value) |
|
947 |
self._parsed_key_map.insert(index + 1, new_key) |
|
2890.2.5
by Robert Collins
Create a content lookup function for bisection in GraphIndex. |
948 |
|
2890.2.6
by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface. |
949 |
def _read_and_parse(self, readv_ranges): |
950 |
"""Read the the ranges and parse the resulting data.
|
|
951 |
||
952 |
:param readv_ranges: A prepared readv range list.
|
|
953 |
"""
|
|
954 |
if readv_ranges: |
|
955 |
readv_data = self._transport.readv(self._name, readv_ranges, True, |
|
956 |
self._size) |
|
957 |
# parse
|
|
958 |
for offset, data in readv_data: |
|
959 |
if self._bisect_nodes is None: |
|
960 |
# this must be the start
|
|
961 |
assert offset == 0 |
|
962 |
offset, data = self._parse_header_from_bytes(data) |
|
2890.2.14
by Robert Collins
Parse more than one segment of data from a single readv response if needed. |
963 |
# print readv_ranges, "[%d:%d]" % (offset, offset + len(data))
|
2890.2.6
by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface. |
964 |
self._parse_region(offset, data) |
965 |
||
2592.1.8
by Robert Collins
Empty files should validate ok. |
966 |
def _signature(self): |
967 |
"""The file signature for this index type."""
|
|
968 |
return _SIGNATURE |
|
969 |
||
2592.1.7
by Robert Collins
A validate that goes boom. |
970 |
def validate(self): |
971 |
"""Validate that everything in the index can be accessed."""
|
|
2592.1.27
by Robert Collins
Test missing end lines with non-empty indices. |
972 |
# iter_all validates completely at the moment, so just do that.
|
973 |
for node in self.iter_all_entries(): |
|
974 |
pass
|
|
2592.1.31
by Robert Collins
Build a combined graph index to use multiple indices at once. |
975 |
|
976 |
||
977 |
class CombinedGraphIndex(object): |
|
978 |
"""A GraphIndex made up from smaller GraphIndices.
|
|
979 |
|
|
980 |
The backing indices must implement GraphIndex, and are presumed to be
|
|
981 |
static data.
|
|
2592.1.45
by Robert Collins
Tweak documentation as per Aaron's review. |
982 |
|
983 |
Queries against the combined index will be made against the first index,
|
|
984 |
and then the second and so on. The order of index's can thus influence
|
|
985 |
performance significantly. For example, if one index is on local disk and a
|
|
986 |
second on a remote server, the local disk index should be before the other
|
|
987 |
in the index list.
|
|
2592.1.31
by Robert Collins
Build a combined graph index to use multiple indices at once. |
988 |
"""
|
989 |
||
990 |
def __init__(self, indices): |
|
991 |
"""Create a CombinedGraphIndex backed by indices.
|
|
992 |
||
2592.1.45
by Robert Collins
Tweak documentation as per Aaron's review. |
993 |
:param indices: An ordered list of indices to query for data.
|
2592.1.31
by Robert Collins
Build a combined graph index to use multiple indices at once. |
994 |
"""
|
995 |
self._indices = indices |
|
2592.1.37
by Robert Collins
Add CombinedGraphIndex.insert_index. |
996 |
|
2592.5.4
by Martin Pool
Add CombinedGraphIndex repr |
997 |
def __repr__(self): |
998 |
return "%s(%s)" % ( |
|
999 |
self.__class__.__name__, |
|
1000 |
', '.join(map(repr, self._indices))) |
|
1001 |
||
3099.3.3
by John Arbash Meinel
Deprecate get_parents() in favor of get_parent_map() |
1002 |
@symbol_versioning.deprecated_method(symbol_versioning.one_one) |
2979.2.2
by Robert Collins
Per-file graph heads detection during commit for pack repositories. |
1003 |
def get_parents(self, revision_ids): |
3099.3.1
by John Arbash Meinel
Implement get_parent_map for ParentProviders |
1004 |
"""See graph._StackedParentsProvider.get_parents.
|
2979.2.2
by Robert Collins
Per-file graph heads detection during commit for pack repositories. |
1005 |
|
1006 |
This implementation thunks the graph.Graph.get_parents api across to
|
|
1007 |
GraphIndex.
|
|
1008 |
||
1009 |
:param revision_ids: An iterable of graph keys for this graph.
|
|
1010 |
:return: A list of parent details for each key in revision_ids.
|
|
1011 |
Each parent details will be one of:
|
|
1012 |
* None when the key was missing
|
|
1013 |
* (NULL_REVISION,) when the key has no parents.
|
|
1014 |
* (parent_key, parent_key...) otherwise.
|
|
1015 |
"""
|
|
3099.3.1
by John Arbash Meinel
Implement get_parent_map for ParentProviders |
1016 |
parent_map = self.get_parent_map(revision_ids) |
1017 |
return [parent_map.get(r, None) for r in revision_ids] |
|
1018 |
||
1019 |
def get_parent_map(self, keys): |
|
1020 |
"""See graph._StackedParentsProvider.get_parent_map"""
|
|
1021 |
search_keys = set(keys) |
|
1022 |
if NULL_REVISION in search_keys: |
|
1023 |
search_keys.discard(NULL_REVISION) |
|
1024 |
found_parents = {NULL_REVISION:[]} |
|
1025 |
else: |
|
1026 |
found_parents = {} |
|
2979.2.2
by Robert Collins
Per-file graph heads detection during commit for pack repositories. |
1027 |
for index, key, value, refs in self.iter_entries(search_keys): |
1028 |
parents = refs[0] |
|
1029 |
if not parents: |
|
1030 |
parents = (NULL_REVISION,) |
|
1031 |
found_parents[key] = parents |
|
3099.3.1
by John Arbash Meinel
Implement get_parent_map for ParentProviders |
1032 |
return found_parents |
2979.2.2
by Robert Collins
Per-file graph heads detection during commit for pack repositories. |
1033 |
|
2592.1.37
by Robert Collins
Add CombinedGraphIndex.insert_index. |
1034 |
def insert_index(self, pos, index): |
1035 |
"""Insert a new index in the list of indices to query.
|
|
1036 |
||
1037 |
:param pos: The position to insert the index.
|
|
1038 |
:param index: The index to insert.
|
|
1039 |
"""
|
|
1040 |
self._indices.insert(pos, index) |
|
1041 |
||
2592.1.31
by Robert Collins
Build a combined graph index to use multiple indices at once. |
1042 |
def iter_all_entries(self): |
1043 |
"""Iterate over all keys within the index
|
|
1044 |
||
2592.1.44
by Robert Collins
Remove some unneeded index iteration by checking if we have found all keys, and grammar improvements from Aaron's review. |
1045 |
Duplicate keys across child indices are presumed to have the same
|
1046 |
value and are only reported once.
|
|
1047 |
||
2592.5.1
by Martin Pool
Fix docstrings for Index.iter_entries etc |
1048 |
:return: An iterable of (index, key, reference_lists, value).
|
1049 |
There is no defined order for the result iteration - it will be in
|
|
1050 |
the most efficient order for the index.
|
|
2592.1.31
by Robert Collins
Build a combined graph index to use multiple indices at once. |
1051 |
"""
|
1052 |
seen_keys = set() |
|
1053 |
for index in self._indices: |
|
1054 |
for node in index.iter_all_entries(): |
|
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
1055 |
if node[1] not in seen_keys: |
2592.1.31
by Robert Collins
Build a combined graph index to use multiple indices at once. |
1056 |
yield node |
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
1057 |
seen_keys.add(node[1]) |
2592.1.31
by Robert Collins
Build a combined graph index to use multiple indices at once. |
1058 |
|
1059 |
def iter_entries(self, keys): |
|
1060 |
"""Iterate over keys within the index.
|
|
1061 |
||
2592.1.44
by Robert Collins
Remove some unneeded index iteration by checking if we have found all keys, and grammar improvements from Aaron's review. |
1062 |
Duplicate keys across child indices are presumed to have the same
|
1063 |
value and are only reported once.
|
|
1064 |
||
2592.1.31
by Robert Collins
Build a combined graph index to use multiple indices at once. |
1065 |
:param keys: An iterable providing the keys to be retrieved.
|
2592.5.1
by Martin Pool
Fix docstrings for Index.iter_entries etc |
1066 |
:return: An iterable of (index, key, reference_lists, value). There is no
|
2592.1.31
by Robert Collins
Build a combined graph index to use multiple indices at once. |
1067 |
defined order for the result iteration - it will be in the most
|
1068 |
efficient order for the index.
|
|
1069 |
"""
|
|
1070 |
keys = set(keys) |
|
2592.1.39
by Robert Collins
CombinedGraphIndex.iter_entries does not need to see all entries. |
1071 |
for index in self._indices: |
2592.1.44
by Robert Collins
Remove some unneeded index iteration by checking if we have found all keys, and grammar improvements from Aaron's review. |
1072 |
if not keys: |
1073 |
return
|
|
2592.1.39
by Robert Collins
CombinedGraphIndex.iter_entries does not need to see all entries. |
1074 |
for node in index.iter_entries(keys): |
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
1075 |
keys.remove(node[1]) |
2592.1.31
by Robert Collins
Build a combined graph index to use multiple indices at once. |
1076 |
yield node |
1077 |
||
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
1078 |
def iter_entries_prefix(self, keys): |
1079 |
"""Iterate over keys within the index using prefix matching.
|
|
1080 |
||
1081 |
Duplicate keys across child indices are presumed to have the same
|
|
1082 |
value and are only reported once.
|
|
1083 |
||
1084 |
Prefix matching is applied within the tuple of a key, not to within
|
|
1085 |
the bytestring of each key element. e.g. if you have the keys ('foo',
|
|
1086 |
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
|
|
1087 |
only the former key is returned.
|
|
1088 |
||
1089 |
:param keys: An iterable providing the key prefixes to be retrieved.
|
|
1090 |
Each key prefix takes the form of a tuple the length of a key, but
|
|
1091 |
with the last N elements 'None' rather than a regular bytestring.
|
|
1092 |
The first element cannot be 'None'.
|
|
1093 |
:return: An iterable as per iter_all_entries, but restricted to the
|
|
1094 |
keys with a matching prefix to those supplied. No additional keys
|
|
1095 |
will be returned, and every match that is in the index will be
|
|
1096 |
returned.
|
|
1097 |
"""
|
|
1098 |
keys = set(keys) |
|
1099 |
if not keys: |
|
1100 |
return
|
|
1101 |
seen_keys = set() |
|
1102 |
for index in self._indices: |
|
1103 |
for node in index.iter_entries_prefix(keys): |
|
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
1104 |
if node[1] in seen_keys: |
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
1105 |
continue
|
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
1106 |
seen_keys.add(node[1]) |
2624.2.9
by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one. |
1107 |
yield node |
1108 |
||
2624.2.16
by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index. |
1109 |
def key_count(self): |
1110 |
"""Return an estimate of the number of keys in this index.
|
|
1111 |
|
|
1112 |
For CombinedGraphIndex this is approximated by the sum of the keys of
|
|
1113 |
the child indices. As child indices may have duplicate keys this can
|
|
1114 |
have a maximum error of the number of child indices * largest number of
|
|
1115 |
keys in any index.
|
|
1116 |
"""
|
|
1117 |
return sum((index.key_count() for index in self._indices), 0) |
|
1118 |
||
2592.1.31
by Robert Collins
Build a combined graph index to use multiple indices at once. |
1119 |
def validate(self): |
1120 |
"""Validate that everything in the index can be accessed."""
|
|
1121 |
for index in self._indices: |
|
1122 |
index.validate() |
|
2592.1.38
by Robert Collins
Create an InMemoryGraphIndex for temporary indexing. |
1123 |
|
1124 |
||
1125 |
class InMemoryGraphIndex(GraphIndexBuilder): |
|
1126 |
"""A GraphIndex which operates entirely out of memory and is mutable.
|
|
1127 |
||
1128 |
This is designed to allow the accumulation of GraphIndex entries during a
|
|
1129 |
single write operation, where the accumulated entries need to be immediately
|
|
1130 |
available - for example via a CombinedGraphIndex.
|
|
1131 |
"""
|
|
1132 |
||
1133 |
def add_nodes(self, nodes): |
|
1134 |
"""Add nodes to the index.
|
|
1135 |
||
1136 |
:param nodes: An iterable of (key, node_refs, value) entries to add.
|
|
1137 |
"""
|
|
2592.3.39
by Robert Collins
Fugly version to remove signatures.kndx |
1138 |
if self.reference_lists: |
1139 |
for (key, value, node_refs) in nodes: |
|
1140 |
self.add_node(key, value, node_refs) |
|
1141 |
else: |
|
1142 |
for (key, value) in nodes: |
|
1143 |
self.add_node(key, value) |
|
2592.1.38
by Robert Collins
Create an InMemoryGraphIndex for temporary indexing. |
1144 |
|
1145 |
def iter_all_entries(self): |
|
1146 |
"""Iterate over all keys within the index
|
|
1147 |
||
2592.5.1
by Martin Pool
Fix docstrings for Index.iter_entries etc |
1148 |
:return: An iterable of (index, key, reference_lists, value). There is no
|
2592.1.38
by Robert Collins
Create an InMemoryGraphIndex for temporary indexing. |
1149 |
defined order for the result iteration - it will be in the most
|
1150 |
efficient order for the index (in this case dictionary hash order).
|
|
1151 |
"""
|
|
2745.1.1
by Robert Collins
Add a number of -Devil checkpoints. |
1152 |
if 'evil' in debug.debug_flags: |
2592.3.112
by Robert Collins
Various fixups found dogfooding. |
1153 |
trace.mutter_callsite(3, |
2745.1.2
by Robert Collins
Ensure mutter_callsite is not directly called on a lazy_load object, to make the stacklevel parameter work correctly. |
1154 |
"iter_all_entries scales with size of history.") |
2592.1.46
by Robert Collins
Make GraphIndex accept nodes as key, value, references, so that the method |
1155 |
if self.reference_lists: |
1156 |
for key, (absent, references, value) in self._nodes.iteritems(): |
|
1157 |
if not absent: |
|
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
1158 |
yield self, key, value, references |
2592.1.46
by Robert Collins
Make GraphIndex accept nodes as key, value, references, so that the method |
1159 |
else: |
1160 |
for key, (absent, references, value) in self._nodes.iteritems(): |
|
1161 |
if not absent: |
|
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
1162 |
yield self, key, value |
2592.1.38
by Robert Collins
Create an InMemoryGraphIndex for temporary indexing. |
1163 |
|
1164 |
def iter_entries(self, keys): |
|
1165 |
"""Iterate over keys within the index.
|
|
1166 |
||
1167 |
:param keys: An iterable providing the keys to be retrieved.
|
|
2979.2.4
by Robert Collins
Docstring fixes from review. |
1168 |
:return: An iterable of (index, key, value, reference_lists). There is no
|
2592.1.38
by Robert Collins
Create an InMemoryGraphIndex for temporary indexing. |
1169 |
defined order for the result iteration - it will be in the most
|
1170 |
efficient order for the index (keys iteration order in this case).
|
|
1171 |
"""
|
|
1172 |
keys = set(keys) |
|
2592.1.46
by Robert Collins
Make GraphIndex accept nodes as key, value, references, so that the method |
1173 |
if self.reference_lists: |
2592.3.62
by Robert Collins
Performance tweak - use a set for InMemoryGraph key iteration. |
1174 |
for key in keys.intersection(self._keys): |
2592.1.46
by Robert Collins
Make GraphIndex accept nodes as key, value, references, so that the method |
1175 |
node = self._nodes[key] |
1176 |
if not node[0]: |
|
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
1177 |
yield self, key, node[2], node[1] |
2592.1.46
by Robert Collins
Make GraphIndex accept nodes as key, value, references, so that the method |
1178 |
else: |
2592.3.62
by Robert Collins
Performance tweak - use a set for InMemoryGraph key iteration. |
1179 |
for key in keys.intersection(self._keys): |
2592.1.46
by Robert Collins
Make GraphIndex accept nodes as key, value, references, so that the method |
1180 |
node = self._nodes[key] |
1181 |
if not node[0]: |
|
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
1182 |
yield self, key, node[2] |
2592.1.38
by Robert Collins
Create an InMemoryGraphIndex for temporary indexing. |
1183 |
|
2624.2.10
by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex. |
1184 |
def iter_entries_prefix(self, keys): |
1185 |
"""Iterate over keys within the index using prefix matching.
|
|
1186 |
||
1187 |
Prefix matching is applied within the tuple of a key, not to within
|
|
1188 |
the bytestring of each key element. e.g. if you have the keys ('foo',
|
|
1189 |
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
|
|
1190 |
only the former key is returned.
|
|
1191 |
||
1192 |
:param keys: An iterable providing the key prefixes to be retrieved.
|
|
1193 |
Each key prefix takes the form of a tuple the length of a key, but
|
|
1194 |
with the last N elements 'None' rather than a regular bytestring.
|
|
1195 |
The first element cannot be 'None'.
|
|
1196 |
:return: An iterable as per iter_all_entries, but restricted to the
|
|
1197 |
keys with a matching prefix to those supplied. No additional keys
|
|
1198 |
will be returned, and every match that is in the index will be
|
|
1199 |
returned.
|
|
1200 |
"""
|
|
1201 |
# XXX: To much duplication with the GraphIndex class; consider finding
|
|
1202 |
# a good place to pull out the actual common logic.
|
|
1203 |
keys = set(keys) |
|
1204 |
if not keys: |
|
1205 |
return
|
|
1206 |
if self._key_length == 1: |
|
1207 |
for key in keys: |
|
1208 |
# sanity check
|
|
1209 |
if key[0] is None: |
|
1210 |
raise errors.BadIndexKey(key) |
|
1211 |
if len(key) != self._key_length: |
|
1212 |
raise errors.BadIndexKey(key) |
|
1213 |
node = self._nodes[key] |
|
1214 |
if node[0]: |
|
1215 |
continue
|
|
1216 |
if self.reference_lists: |
|
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
1217 |
yield self, key, node[2], node[1] |
2624.2.10
by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex. |
1218 |
else: |
2624.2.17
by Robert Collins
Review feedback. |
1219 |
yield self, key, node[2] |
2624.2.10
by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex. |
1220 |
return
|
1221 |
for key in keys: |
|
1222 |
# sanity check
|
|
1223 |
if key[0] is None: |
|
1224 |
raise errors.BadIndexKey(key) |
|
1225 |
if len(key) != self._key_length: |
|
1226 |
raise errors.BadIndexKey(key) |
|
1227 |
# find what it refers to:
|
|
1228 |
key_dict = self._nodes_by_key |
|
1229 |
elements = list(key) |
|
1230 |
# find the subdict to return
|
|
1231 |
try: |
|
1232 |
while len(elements) and elements[0] is not None: |
|
1233 |
key_dict = key_dict[elements[0]] |
|
1234 |
elements.pop(0) |
|
1235 |
except KeyError: |
|
1236 |
# a non-existant lookup.
|
|
1237 |
continue
|
|
1238 |
if len(elements): |
|
1239 |
dicts = [key_dict] |
|
1240 |
while dicts: |
|
1241 |
key_dict = dicts.pop(-1) |
|
1242 |
# can't be empty or would not exist
|
|
1243 |
item, value = key_dict.iteritems().next() |
|
1244 |
if type(value) == dict: |
|
1245 |
# push keys
|
|
1246 |
dicts.extend(key_dict.itervalues()) |
|
1247 |
else: |
|
1248 |
# yield keys
|
|
1249 |
for value in key_dict.itervalues(): |
|
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
1250 |
yield (self, ) + value |
2624.2.10
by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex. |
1251 |
else: |
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
1252 |
yield (self, ) + key_dict |
2624.2.10
by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex. |
1253 |
|
2624.2.16
by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index. |
1254 |
def key_count(self): |
1255 |
"""Return an estimate of the number of keys in this index.
|
|
1256 |
|
|
1257 |
For InMemoryGraphIndex the estimate is exact.
|
|
1258 |
"""
|
|
1259 |
return len(self._keys) |
|
1260 |
||
2592.1.38
by Robert Collins
Create an InMemoryGraphIndex for temporary indexing. |
1261 |
def validate(self): |
1262 |
"""In memory index's have no known corruption at the moment."""
|
|
2624.2.12
by Robert Collins
Create an adapter between indices with differing key lengths. |
1263 |
|
1264 |
||
1265 |
class GraphIndexPrefixAdapter(object): |
|
1266 |
"""An adapter between GraphIndex with different key lengths.
|
|
1267 |
||
1268 |
Queries against this will emit queries against the adapted Graph with the
|
|
1269 |
prefix added, queries for all items use iter_entries_prefix. The returned
|
|
1270 |
nodes will have their keys and node references adjusted to remove the
|
|
1271 |
prefix. Finally, an add_nodes_callback can be supplied - when called the
|
|
1272 |
nodes and references being added will have prefix prepended.
|
|
1273 |
"""
|
|
1274 |
||
2624.2.17
by Robert Collins
Review feedback. |
1275 |
def __init__(self, adapted, prefix, missing_key_length, |
1276 |
add_nodes_callback=None): |
|
2624.2.12
by Robert Collins
Create an adapter between indices with differing key lengths. |
1277 |
"""Construct an adapter against adapted with prefix."""
|
1278 |
self.adapted = adapted |
|
2624.2.19
by Robert Collins
Why we should always test before committing. |
1279 |
self.prefix_key = prefix + (None,)*missing_key_length |
2624.2.17
by Robert Collins
Review feedback. |
1280 |
self.prefix = prefix |
2624.2.12
by Robert Collins
Create an adapter between indices with differing key lengths. |
1281 |
self.prefix_len = len(prefix) |
1282 |
self.add_nodes_callback = add_nodes_callback |
|
1283 |
||
2624.2.13
by Robert Collins
Implement add_node/add_nodes to the GraphIndexPrefixAdapter. |
1284 |
def add_nodes(self, nodes): |
1285 |
"""Add nodes to the index.
|
|
1286 |
||
1287 |
:param nodes: An iterable of (key, node_refs, value) entries to add.
|
|
1288 |
"""
|
|
1289 |
# save nodes in case its an iterator
|
|
1290 |
nodes = tuple(nodes) |
|
1291 |
translated_nodes = [] |
|
1292 |
try: |
|
2624.2.17
by Robert Collins
Review feedback. |
1293 |
# Add prefix_key to each reference node_refs is a tuple of tuples,
|
1294 |
# so split it apart, and add prefix_key to the internal reference
|
|
2624.2.13
by Robert Collins
Implement add_node/add_nodes to the GraphIndexPrefixAdapter. |
1295 |
for (key, value, node_refs) in nodes: |
1296 |
adjusted_references = ( |
|
2624.2.17
by Robert Collins
Review feedback. |
1297 |
tuple(tuple(self.prefix + ref_node for ref_node in ref_list) |
2624.2.13
by Robert Collins
Implement add_node/add_nodes to the GraphIndexPrefixAdapter. |
1298 |
for ref_list in node_refs)) |
2624.2.17
by Robert Collins
Review feedback. |
1299 |
translated_nodes.append((self.prefix + key, value, |
2624.2.13
by Robert Collins
Implement add_node/add_nodes to the GraphIndexPrefixAdapter. |
1300 |
adjusted_references)) |
1301 |
except ValueError: |
|
1302 |
# XXX: TODO add an explicit interface for getting the reference list
|
|
1303 |
# status, to handle this bit of user-friendliness in the API more
|
|
1304 |
# explicitly.
|
|
1305 |
for (key, value) in nodes: |
|
2624.2.17
by Robert Collins
Review feedback. |
1306 |
translated_nodes.append((self.prefix + key, value)) |
2624.2.13
by Robert Collins
Implement add_node/add_nodes to the GraphIndexPrefixAdapter. |
1307 |
self.add_nodes_callback(translated_nodes) |
1308 |
||
1309 |
def add_node(self, key, value, references=()): |
|
1310 |
"""Add a node to the index.
|
|
1311 |
||
1312 |
:param key: The key. keys are non-empty tuples containing
|
|
1313 |
as many whitespace-free utf8 bytestrings as the key length
|
|
1314 |
defined for this index.
|
|
1315 |
:param references: An iterable of iterables of keys. Each is a
|
|
1316 |
reference to another key.
|
|
1317 |
:param value: The value to associate with the key. It may be any
|
|
1318 |
bytes as long as it does not contain \0 or \n.
|
|
1319 |
"""
|
|
1320 |
self.add_nodes(((key, value, references), )) |
|
1321 |
||
2624.2.12
by Robert Collins
Create an adapter between indices with differing key lengths. |
1322 |
def _strip_prefix(self, an_iter): |
1323 |
"""Strip prefix data from nodes and return it."""
|
|
1324 |
for node in an_iter: |
|
1325 |
# cross checks
|
|
2624.2.17
by Robert Collins
Review feedback. |
1326 |
if node[1][:self.prefix_len] != self.prefix: |
2624.2.12
by Robert Collins
Create an adapter between indices with differing key lengths. |
1327 |
raise errors.BadIndexData(self) |
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
1328 |
for ref_list in node[3]: |
2624.2.12
by Robert Collins
Create an adapter between indices with differing key lengths. |
1329 |
for ref_node in ref_list: |
2624.2.17
by Robert Collins
Review feedback. |
1330 |
if ref_node[:self.prefix_len] != self.prefix: |
2624.2.12
by Robert Collins
Create an adapter between indices with differing key lengths. |
1331 |
raise errors.BadIndexData(self) |
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
1332 |
yield node[0], node[1][self.prefix_len:], node[2], ( |
2624.2.12
by Robert Collins
Create an adapter between indices with differing key lengths. |
1333 |
tuple(tuple(ref_node[self.prefix_len:] for ref_node in ref_list) |
2624.2.14
by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data. |
1334 |
for ref_list in node[3])) |
2624.2.12
by Robert Collins
Create an adapter between indices with differing key lengths. |
1335 |
|
1336 |
def iter_all_entries(self): |
|
1337 |
"""Iterate over all keys within the index
|
|
1338 |
||
1339 |
iter_all_entries is implemented against the adapted index using
|
|
1340 |
iter_entries_prefix.
|
|
1341 |
||
2592.5.1
by Martin Pool
Fix docstrings for Index.iter_entries etc |
1342 |
:return: An iterable of (index, key, reference_lists, value). There is no
|
2624.2.12
by Robert Collins
Create an adapter between indices with differing key lengths. |
1343 |
defined order for the result iteration - it will be in the most
|
1344 |
efficient order for the index (in this case dictionary hash order).
|
|
1345 |
"""
|
|
2624.2.19
by Robert Collins
Why we should always test before committing. |
1346 |
return self._strip_prefix(self.adapted.iter_entries_prefix([self.prefix_key])) |
2624.2.12
by Robert Collins
Create an adapter between indices with differing key lengths. |
1347 |
|
1348 |
def iter_entries(self, keys): |
|
1349 |
"""Iterate over keys within the index.
|
|
1350 |
||
1351 |
:param keys: An iterable providing the keys to be retrieved.
|
|
2979.2.4
by Robert Collins
Docstring fixes from review. |
1352 |
:return: An iterable of (index, key, value, reference_lists). There is no
|
2624.2.12
by Robert Collins
Create an adapter between indices with differing key lengths. |
1353 |
defined order for the result iteration - it will be in the most
|
1354 |
efficient order for the index (keys iteration order in this case).
|
|
1355 |
"""
|
|
1356 |
return self._strip_prefix(self.adapted.iter_entries( |
|
2624.2.17
by Robert Collins
Review feedback. |
1357 |
self.prefix + key for key in keys)) |
2624.2.12
by Robert Collins
Create an adapter between indices with differing key lengths. |
1358 |
|
1359 |
def iter_entries_prefix(self, keys): |
|
1360 |
"""Iterate over keys within the index using prefix matching.
|
|
1361 |
||
1362 |
Prefix matching is applied within the tuple of a key, not to within
|
|
1363 |
the bytestring of each key element. e.g. if you have the keys ('foo',
|
|
1364 |
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
|
|
1365 |
only the former key is returned.
|
|
1366 |
||
1367 |
:param keys: An iterable providing the key prefixes to be retrieved.
|
|
1368 |
Each key prefix takes the form of a tuple the length of a key, but
|
|
1369 |
with the last N elements 'None' rather than a regular bytestring.
|
|
1370 |
The first element cannot be 'None'.
|
|
1371 |
:return: An iterable as per iter_all_entries, but restricted to the
|
|
1372 |
keys with a matching prefix to those supplied. No additional keys
|
|
1373 |
will be returned, and every match that is in the index will be
|
|
1374 |
returned.
|
|
1375 |
"""
|
|
1376 |
return self._strip_prefix(self.adapted.iter_entries_prefix( |
|
2624.2.17
by Robert Collins
Review feedback. |
1377 |
self.prefix + key for key in keys)) |
2624.2.12
by Robert Collins
Create an adapter between indices with differing key lengths. |
1378 |
|
2624.2.16
by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index. |
1379 |
def key_count(self): |
1380 |
"""Return an estimate of the number of keys in this index.
|
|
1381 |
|
|
1382 |
For GraphIndexPrefixAdapter this is relatively expensive - key
|
|
1383 |
iteration with the prefix is done.
|
|
1384 |
"""
|
|
1385 |
return len(list(self.iter_all_entries())) |
|
1386 |
||
2624.2.12
by Robert Collins
Create an adapter between indices with differing key lengths. |
1387 |
def validate(self): |
1388 |
"""Call the adapted's validate."""
|
|
1389 |
self.adapted.validate() |