110
94
if not element or _whitespace_re.search(element) is not None:
111
95
raise errors.BadIndexKey(element)
113
def _external_references(self):
114
"""Return references that are not present in this index.
118
# TODO: JAM 2008-11-21 This makes an assumption about how the reference
119
# lists are used. It is currently correct for pack-0.92 through
120
# 1.9, which use the node references (3rd column) second
121
# reference list as the compression parent. Perhaps this should
122
# be moved into something higher up the stack, since it
123
# makes assumptions about how the index is used.
124
if self.reference_lists > 1:
125
for node in self.iter_all_entries():
127
refs.update(node[3][1])
130
# If reference_lists == 0 there can be no external references, and
131
# if reference_lists == 1, then there isn't a place to store the
135
def _get_nodes_by_key(self):
136
if self._nodes_by_key is None:
138
if self.reference_lists:
139
for key, (absent, references, value) in self._nodes.iteritems():
142
key_dict = nodes_by_key
143
for subkey in key[:-1]:
144
key_dict = key_dict.setdefault(subkey, {})
145
key_dict[key[-1]] = key, value, references
147
for key, (absent, references, value) in self._nodes.iteritems():
150
key_dict = nodes_by_key
151
for subkey in key[:-1]:
152
key_dict = key_dict.setdefault(subkey, {})
153
key_dict[key[-1]] = key, value
154
self._nodes_by_key = nodes_by_key
155
return self._nodes_by_key
157
def _update_nodes_by_key(self, key, value, node_refs):
158
"""Update the _nodes_by_key dict with a new key.
160
For a key of (foo, bar, baz) create
161
_nodes_by_key[foo][bar][baz] = key_value
163
if self._nodes_by_key is None:
165
key_dict = self._nodes_by_key
166
if self.reference_lists:
167
key_value = key, value, node_refs
169
key_value = key, value
170
for subkey in key[:-1]:
171
key_dict = key_dict.setdefault(subkey, {})
172
key_dict[key[-1]] = key_value
174
def _check_key_ref_value(self, key, references, value):
175
"""Check that 'key' and 'references' are all valid.
177
:param key: A key tuple. Must conform to the key interface (be a tuple,
178
be of the right length, not have any whitespace or nulls in any key
180
:param references: An iterable of reference lists. Something like
181
[[(ref, key)], [(ref, key), (other, key)]]
182
:param value: The value associate with this key. Must not contain
183
newlines or null characters.
184
:return: (node_refs, absent_references)
185
node_refs basically a packed form of 'references' where all
187
absent_references reference keys that are not in self._nodes.
188
This may contain duplicates if the same key is
189
referenced in multiple lists.
97
def add_node(self, key, value, references=()):
98
"""Add a node to the index.
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.
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.
191
108
self._check_key(key)
192
109
if _newline_null_re.search(value) is not None:
194
111
if len(references) != self.reference_lists:
195
112
raise errors.BadIndexValue(references)
197
absent_references = []
198
114
for reference_list in references:
199
115
for reference in reference_list:
200
# If reference *is* in self._nodes, then we know it has already
116
self._check_key(reference)
202
117
if reference not in self._nodes:
203
self._check_key(reference)
204
absent_references.append(reference)
118
self._nodes[reference] = ('a', (), '')
205
119
node_refs.append(tuple(reference_list))
206
return tuple(node_refs), absent_references
208
def add_node(self, key, value, references=()):
209
"""Add a node to the index.
211
:param key: The key. keys are non-empty tuples containing
212
as many whitespace-free utf8 bytestrings as the key length
213
defined for this index.
214
:param references: An iterable of iterables of keys. Each is a
215
reference to another key.
216
:param value: The value to associate with the key. It may be any
217
bytes as long as it does not contain \0 or \n.
220
absent_references) = self._check_key_ref_value(key, references, value)
221
if key in self._nodes and self._nodes[key][0] != 'a':
120
if key in self._nodes and self._nodes[key][0] == '':
222
121
raise errors.BadIndexDuplicateKey(key, self)
223
for reference in absent_references:
224
# There may be duplicates, but I don't think it is worth worrying
226
self._nodes[reference] = ('a', (), '')
227
self._nodes[key] = ('', node_refs, value)
122
self._nodes[key] = ('', tuple(node_refs), value)
228
123
self._keys.add(key)
229
if self._nodes_by_key is not None and self._key_length > 1:
230
self._update_nodes_by_key(key, value, node_refs)
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)
129
key_value = key, value
130
# possibly should do this on-demand, but it seems likely it is
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, {})
136
key_dict[key[-1]] = key_value
232
138
def finish(self):
233
139
lines = [_SIGNATURE]
391
284
def __ne__(self, other):
392
285
return not self.__eq__(other)
395
return "%s(%r)" % (self.__class__.__name__,
396
self._transport.abspath(self._name))
398
def _buffer_all(self, stream=None):
287
def _buffer_all(self):
399
288
"""Buffer all the index data.
401
290
Mutates self._nodes and self.keys_by_offset.
403
if self._nodes is not None:
404
# We already did this
406
292
if 'index' in debug.debug_flags:
407
293
mutter('Reading entire index %s', self._transport.abspath(self._name))
409
stream = self._transport.get(self._name)
294
stream = self._transport.get(self._name)
410
295
self._read_prefix(stream)
411
296
self._expected_elements = 3 + self._key_length
430
315
node_value = value
431
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]
323
key_value = key, node_value
324
# possibly should do this on-demand, but it seems likely it is
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, {})
330
key_dict[key[-1]] = key_value
432
331
# cache the keys for quick set intersections
433
332
self._keys = set(self._nodes)
434
333
if trailers != 1:
435
334
# there must be one line - the empty trailer line.
436
335
raise errors.BadIndexData(self)
438
def _get_nodes_by_key(self):
439
if self._nodes_by_key is None:
441
if self.node_ref_lists:
442
for key, (value, references) in self._nodes.iteritems():
443
key_dict = nodes_by_key
444
for subkey in key[:-1]:
445
key_dict = key_dict.setdefault(subkey, {})
446
key_dict[key[-1]] = key, value, references
448
for key, value in self._nodes.iteritems():
449
key_dict = nodes_by_key
450
for subkey in key[:-1]:
451
key_dict = key_dict.setdefault(subkey, {})
452
key_dict[key[-1]] = key, value
453
self._nodes_by_key = nodes_by_key
454
return self._nodes_by_key
456
337
def iter_all_entries(self):
457
338
"""Iterate over all keys within the index.
583
464
keys supplied. No additional keys will be returned, and every
584
465
key supplied that is in the index will be returned.
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.
589
473
if self._size is None and self._nodes is None:
590
474
self._buffer_all()
592
# We fit about 20 keys per minimum-read (4K), so if we are looking for
593
# more than 1/20th of the index its likely (assuming homogenous key
594
# spread) that we'll read the entire index. If we're going to do that,
595
# buffer the whole thing. A better analysis might take key spread into
596
# account - but B+Tree indices are better anyway.
597
# We could look at all data read, and use a threshold there, which will
598
# trigger on ancestry walks, but that is not yet fully mapped out.
599
if self._nodes is None and len(keys) * 20 > self.key_count():
601
475
if self._nodes is not None:
602
476
return self._iter_entries_from_total_buffer(keys)
746
619
if self._bisect_nodes is None:
747
620
readv_ranges.append(_HEADER_READV)
748
621
self._read_and_parse(readv_ranges)
750
if self._nodes is not None:
751
# _read_and_parse triggered a _buffer_all because we requested the
753
for location, key in location_keys:
754
if key not in self._nodes: # not present
755
result.append(((location, key), False))
756
elif self.node_ref_lists:
757
value, refs = self._nodes[key]
758
result.append(((location, key),
759
(self, key, value, refs)))
761
result.append(((location, key),
762
(self, key, self._nodes[key])))
764
622
# generate results:
765
623
# - figure out <, >, missing, present
766
624
# - result present references so we can return them.
767
626
# keys that we cannot answer until we resolve references
768
627
pending_references = []
769
628
pending_locations = set()
820
679
readv_ranges.append((location, length))
821
680
self._read_and_parse(readv_ranges)
822
if self._nodes is not None:
823
# The _read_and_parse triggered a _buffer_all, grab the data and
825
for location, key in pending_references:
826
value, refs = self._nodes[key]
827
result.append(((location, key), (self, key, value, refs)))
829
681
for location, key in pending_references:
830
682
# answer key references we had to look-up-late.
683
index = self._parsed_key_index(key)
831
684
value, refs = self._bisect_nodes[key]
832
685
result.append(((location, key), (self, key,
833
686
value, self._resolve_references(refs))))
1104
956
:param readv_ranges: A prepared readv range list.
1106
if not readv_ranges:
1108
if self._nodes is None and self._bytes_read * 2 >= self._size:
1109
# We've already read more than 50% of the file and we are about to
1110
# request more data, just _buffer_all() and be done
1114
readv_data = self._transport.readv(self._name, readv_ranges, True,
1117
for offset, data in readv_data:
1118
self._bytes_read += len(data)
1119
if offset == 0 and len(data) == self._size:
1120
# We read the whole range, most likely because the
1121
# Transport upcast our readv ranges into one long request
1122
# for enough total data to grab the whole index.
1123
self._buffer_all(StringIO(data))
1125
if self._bisect_nodes is None:
1126
# this must be the start
1127
if not (offset == 0):
1128
raise AssertionError()
1129
offset, data = self._parse_header_from_bytes(data)
1130
# print readv_ranges, "[%d:%d]" % (offset, offset + len(data))
1131
self._parse_region(offset, data)
959
readv_data = self._transport.readv(self._name, readv_ranges, True,
962
for offset, data in readv_data:
963
if self._bisect_nodes is None:
964
# this must be the start
965
if not (offset == 0):
966
raise AssertionError()
967
offset, data = self._parse_header_from_bytes(data)
968
# print readv_ranges, "[%d:%d]" % (offset, offset + len(data))
969
self._parse_region(offset, data)
1133
971
def _signature(self):
1134
972
"""The file signature for this index type."""
1284
1106
seen_keys = set()
1287
for index in self._indices:
1288
for node in index.iter_entries_prefix(keys):
1289
if node[1] in seen_keys:
1291
seen_keys.add(node[1])
1294
except errors.NoSuchFile:
1295
self._reload_or_raise()
1107
for index in self._indices:
1108
for node in index.iter_entries_prefix(keys):
1109
if node[1] in seen_keys:
1111
seen_keys.add(node[1])
1297
1114
def key_count(self):
1298
1115
"""Return an estimate of the number of keys in this index.
1300
1117
For CombinedGraphIndex this is approximated by the sum of the keys of
1301
1118
the child indices. As child indices may have duplicate keys this can
1302
1119
have a maximum error of the number of child indices * largest number of
1303
1120
keys in any index.
1307
return sum((index.key_count() for index in self._indices), 0)
1308
except errors.NoSuchFile:
1309
self._reload_or_raise()
1311
missing_keys = _missing_keys_from_parent_map
1313
def _reload_or_raise(self):
1314
"""We just got a NoSuchFile exception.
1316
Try to reload the indices, if it fails, just raise the current
1319
if self._reload_func is None:
1321
exc_type, exc_value, exc_traceback = sys.exc_info()
1322
trace.mutter('Trying to reload after getting exception: %s',
1324
if not self._reload_func():
1325
# We tried to reload, but nothing changed, so we fail anyway
1326
trace.mutter('_reload_func indicated nothing has changed.'
1327
' Raising original exception.')
1328
raise exc_type, exc_value, exc_traceback
1122
return sum((index.key_count() for index in self._indices), 0)
1330
1124
def validate(self):
1331
1125
"""Validate that everything in the index can be accessed."""
1334
for index in self._indices:
1337
except errors.NoSuchFile:
1338
self._reload_or_raise()
1126
for index in self._indices:
1341
1130
class InMemoryGraphIndex(GraphIndexBuilder):
added
removed
bzrlib/index.py
