29
27
from bisect import bisect_right
28
from cStringIO import StringIO
32
from ..lazy_import import lazy_import
32
from bzrlib.lazy_import import lazy_import
33
33
lazy_import(globals(), """
36
revision as _mod_revision,
34
from bzrlib import trace
35
from bzrlib.bisect_multi import bisect_multi_bytes
36
from bzrlib.revision import NULL_REVISION
37
from bzrlib.trace import mutter
44
from ..sixish import (
51
from ..static_tuple import StaticTuple
43
from bzrlib.static_tuple import StaticTuple
53
45
_HEADER_READV = (0, 200)
54
_OPTION_KEY_ELEMENTS = b"key_elements="
56
_OPTION_NODE_REFS = b"node_ref_lists="
57
_SIGNATURE = b"Bazaar Graph Index 1\n"
60
class BadIndexFormatSignature(errors.BzrError):
62
_fmt = "%(value)s is not an index of type %(_type)s."
64
def __init__(self, value, _type):
65
errors.BzrError.__init__(self)
70
class BadIndexData(errors.BzrError):
72
_fmt = "Error in data for index %(value)s."
74
def __init__(self, value):
75
errors.BzrError.__init__(self)
79
class BadIndexDuplicateKey(errors.BzrError):
81
_fmt = "The key '%(key)s' is already in index '%(index)s'."
83
def __init__(self, key, index):
84
errors.BzrError.__init__(self)
89
class BadIndexKey(errors.BzrError):
91
_fmt = "The key '%(key)s' is not a valid key."
93
def __init__(self, key):
94
errors.BzrError.__init__(self)
98
class BadIndexOptions(errors.BzrError):
100
_fmt = "Could not parse options for index %(value)s."
102
def __init__(self, value):
103
errors.BzrError.__init__(self)
107
class BadIndexValue(errors.BzrError):
109
_fmt = "The value '%(value)s' is not a valid value."
111
def __init__(self, value):
112
errors.BzrError.__init__(self)
116
_whitespace_re = re.compile(b'[\t\n\x0b\x0c\r\x00 ]')
117
_newline_null_re = re.compile(b'[\n\0]')
46
_OPTION_KEY_ELEMENTS = "key_elements="
48
_OPTION_NODE_REFS = "node_ref_lists="
49
_SIGNATURE = "Bazaar Graph Index 1\n"
52
_whitespace_re = re.compile('[\t\n\x0b\x0c\r\x00 ]')
53
_newline_null_re = re.compile('[\n\0]')
120
56
def _has_key_from_parent_map(self, key):
133
69
class GraphIndexBuilder(object):
134
70
"""A builder that can build a GraphIndex.
136
The resulting graph has the structure::
72
The resulting graph has the structure:
138
_SIGNATURE OPTIONS NODES NEWLINE
139
_SIGNATURE := 'Bazaar Graph Index 1' NEWLINE
140
OPTIONS := 'node_ref_lists=' DIGITS NEWLINE
142
NODE := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
143
KEY := Not-whitespace-utf8
145
REFERENCES := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
146
REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
147
REFERENCE := DIGITS ; digits is the byte offset in the index of the
149
VALUE := no-newline-no-null-bytes
74
_SIGNATURE OPTIONS NODES NEWLINE
75
_SIGNATURE := 'Bazaar Graph Index 1' NEWLINE
76
OPTIONS := 'node_ref_lists=' DIGITS NEWLINE
78
NODE := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
79
KEY := Not-whitespace-utf8
81
REFERENCES := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
82
REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
83
REFERENCE := DIGITS ; digits is the byte offset in the index of the
85
VALUE := no-newline-no-null-bytes
152
88
def __init__(self, reference_lists=0, key_elements=1):
169
105
def _check_key(self, key):
170
106
"""Raise BadIndexKey if key is not a valid key for this index."""
171
107
if type(key) not in (tuple, StaticTuple):
172
raise BadIndexKey(key)
108
raise errors.BadIndexKey(key)
173
109
if self._key_length != len(key):
174
raise BadIndexKey(key)
110
raise errors.BadIndexKey(key)
175
111
for element in key:
176
if not element or type(element) != bytes or _whitespace_re.search(element) is not None:
177
raise BadIndexKey(key)
112
if not element or _whitespace_re.search(element) is not None:
113
raise errors.BadIndexKey(element)
179
115
def _external_references(self):
180
116
"""Return references that are not present in this index.
210
146
key_dict = key_dict.setdefault(subkey, {})
211
147
key_dict[key[-1]] = key, value, references
213
for key, (absent, references, value) in viewitems(self._nodes):
149
for key, (absent, references, value) in self._nodes.iteritems():
216
152
key_dict = nodes_by_key
248
184
:param value: The value associate with this key. Must not contain
249
185
newlines or null characters.
250
186
:return: (node_refs, absent_references)
252
* node_refs: basically a packed form of 'references' where all
254
* absent_references: reference keys that are not in self._nodes.
255
This may contain duplicates if the same key is referenced in
187
node_refs basically a packed form of 'references' where all
189
absent_references reference keys that are not in self._nodes.
190
This may contain duplicates if the same key is
191
referenced in multiple lists.
258
193
as_st = StaticTuple.from_sequence
259
194
self._check_key(key)
260
195
if _newline_null_re.search(value) is not None:
261
raise BadIndexValue(value)
196
raise errors.BadIndexValue(value)
262
197
if len(references) != self.reference_lists:
263
raise BadIndexValue(references)
198
raise errors.BadIndexValue(references)
265
200
absent_references = []
266
201
for reference_list in references:
284
219
:param references: An iterable of iterables of keys. Each is a
285
220
reference to another key.
286
221
:param value: The value to associate with the key. It may be any
287
bytes as long as it does not contain \\0 or \\n.
222
bytes as long as it does not contain \0 or \n.
290
225
absent_references) = self._check_key_ref_value(key, references, value)
291
if key in self._nodes and self._nodes[key][0] != b'a':
292
raise BadIndexDuplicateKey(key, self)
226
if key in self._nodes and self._nodes[key][0] != 'a':
227
raise errors.BadIndexDuplicateKey(key, self)
293
228
for reference in absent_references:
294
229
# There may be duplicates, but I don't think it is worth worrying
296
self._nodes[reference] = (b'a', (), b'')
231
self._nodes[reference] = ('a', (), '')
297
232
self._absent_keys.update(absent_references)
298
233
self._absent_keys.discard(key)
299
self._nodes[key] = (b'', node_refs, value)
234
self._nodes[key] = ('', node_refs, value)
300
235
if self._nodes_by_key is not None and self._key_length > 1:
301
236
self._update_nodes_by_key(key, value, node_refs)
310
245
def finish(self):
313
:returns: cBytesIO holding the full context of the index as it
314
should be written to disk.
316
246
lines = [_SIGNATURE]
317
lines.append(b'%s%d\n' % (_OPTION_NODE_REFS, self.reference_lists))
318
lines.append(b'%s%d\n' % (_OPTION_KEY_ELEMENTS, self._key_length))
247
lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
248
lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
319
249
key_count = len(self._nodes) - len(self._absent_keys)
320
lines.append(b'%s%d\n' % (_OPTION_LEN, key_count))
250
lines.append(_OPTION_LEN + str(key_count) + '\n')
321
251
prefix_length = sum(len(x) for x in lines)
322
252
# references are byte offsets. To avoid having to do nasty
323
253
# polynomial work to resolve offsets (references to later in the
334
264
# forward sorted by key. In future we may consider topological sorting,
335
265
# at the cost of table scans for direct lookup, or a second index for
337
nodes = sorted(viewitems(self._nodes))
267
nodes = sorted(self._nodes.items())
338
268
# if we do not prepass, we don't know how long it will be up front.
339
269
expected_bytes = None
340
270
# we only need to pre-pass if we have reference lists at all.
380
310
for key, non_ref_bytes, total_references in key_offset_info:
381
311
key_addresses[key] = non_ref_bytes + total_references*digits
383
format_string = b'%%0%dd' % digits
313
format_string = '%%0%sd' % digits
384
314
for key, (absent, references, value) in nodes:
385
315
flattened_references = []
386
316
for ref_list in references:
387
317
ref_addresses = []
388
318
for reference in ref_list:
389
319
ref_addresses.append(format_string % key_addresses[reference])
390
flattened_references.append(b'\r'.join(ref_addresses))
391
string_key = b'\x00'.join(key)
392
lines.append(b"%s\x00%s\x00%s\x00%s\n" % (string_key, absent,
393
b'\t'.join(flattened_references), value))
395
result = BytesIO(b''.join(lines))
320
flattened_references.append('\r'.join(ref_addresses))
321
string_key = '\x00'.join(key)
322
lines.append("%s\x00%s\x00%s\x00%s\n" % (string_key, absent,
323
'\t'.join(flattened_references), value))
325
result = StringIO(''.join(lines))
396
326
if expected_bytes and len(result.getvalue()) != expected_bytes:
397
327
raise errors.BzrError('Failed index creation. Internal error:'
398
328
' mismatched output length and expected length: %d %d' %
455
385
def __init__(self, transport, name, size, unlimited_cache=False, offset=0):
456
386
"""Open an index called name on transport.
458
:param transport: A breezy.transport.Transport.
388
:param transport: A bzrlib.transport.Transport.
459
389
:param name: A path to provide to transport API calls.
460
390
:param size: The size of the index in bytes. This is used for bisection
461
391
logic to perform partial index reads. While the size could be
501
431
def __ne__(self, other):
502
432
return not self.__eq__(other)
504
def __lt__(self, other):
505
# We don't really care about the order, just that there is an order.
506
if (not isinstance(other, GraphIndex) and
507
not isinstance(other, InMemoryGraphIndex)):
508
raise TypeError(other)
509
return hash(self) < hash(other)
512
return hash((type(self), self._transport, self._name, self._size))
514
434
def __repr__(self):
515
435
return "%s(%r)" % (self.__class__.__name__,
516
436
self._transport.abspath(self._name))
524
444
# We already did this
526
446
if 'index' in debug.debug_flags:
527
trace.mutter('Reading entire index %s',
528
self._transport.abspath(self._name))
447
mutter('Reading entire index %s', self._transport.abspath(self._name))
529
448
if stream is None:
530
449
stream = self._transport.get(self._name)
531
450
if self._base_offset != 0:
532
451
# This is wasteful, but it is better than dealing with
533
452
# adjusting all the offsets, etc.
534
stream = BytesIO(stream.read()[self._base_offset:])
536
self._read_prefix(stream)
537
self._expected_elements = 3 + self._key_length
539
# raw data keyed by offset
540
self._keys_by_offset = {}
541
# ready-to-return key:value or key:value, node_ref_lists
543
self._nodes_by_key = None
546
lines = stream.read().split(b'\n')
453
stream = StringIO(stream.read()[self._base_offset:])
454
self._read_prefix(stream)
455
self._expected_elements = 3 + self._key_length
457
# raw data keyed by offset
458
self._keys_by_offset = {}
459
# ready-to-return key:value or key:value, node_ref_lists
461
self._nodes_by_key = None
464
lines = stream.read().split('\n')
550
467
_, _, _, trailers = self._parse_lines(lines, pos)
551
for key, absent, references, value in viewvalues(self._keys_by_offset):
468
for key, absent, references, value in self._keys_by_offset.itervalues():
554
471
# resolve references:
579
496
% (ref_list_num, self.node_ref_lists))
581
498
nodes = self._nodes
582
for key, (value, ref_lists) in viewitems(nodes):
499
for key, (value, ref_lists) in nodes.iteritems():
583
500
ref_list = ref_lists[ref_list_num]
584
501
refs.update([ref for ref in ref_list if ref not in nodes])
588
505
if self._nodes_by_key is None:
589
506
nodes_by_key = {}
590
507
if self.node_ref_lists:
591
for key, (value, references) in viewitems(self._nodes):
508
for key, (value, references) in self._nodes.iteritems():
592
509
key_dict = nodes_by_key
593
510
for subkey in key[:-1]:
594
511
key_dict = key_dict.setdefault(subkey, {})
595
512
key_dict[key[-1]] = key, value, references
597
for key, value in viewitems(self._nodes):
514
for key, value in self._nodes.iteritems():
598
515
key_dict = nodes_by_key
599
516
for subkey in key[:-1]:
600
517
key_dict = key_dict.setdefault(subkey, {})
617
534
if self._nodes is None:
618
535
self._buffer_all()
619
536
if self.node_ref_lists:
620
for key, (value, node_ref_lists) in viewitems(self._nodes):
537
for key, (value, node_ref_lists) in self._nodes.iteritems():
621
538
yield self, key, value, node_ref_lists
623
for key, value in viewitems(self._nodes):
540
for key, value in self._nodes.iteritems():
624
541
yield self, key, value
626
543
def _read_prefix(self, stream):
627
544
signature = stream.read(len(self._signature()))
628
545
if not signature == self._signature():
629
raise BadIndexFormatSignature(self._name, GraphIndex)
546
raise errors.BadIndexFormatSignature(self._name, GraphIndex)
630
547
options_line = stream.readline()
631
548
if not options_line.startswith(_OPTION_NODE_REFS):
632
raise BadIndexOptions(self)
549
raise errors.BadIndexOptions(self)
634
551
self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):-1])
635
552
except ValueError:
636
raise BadIndexOptions(self)
553
raise errors.BadIndexOptions(self)
637
554
options_line = stream.readline()
638
555
if not options_line.startswith(_OPTION_KEY_ELEMENTS):
639
raise BadIndexOptions(self)
556
raise errors.BadIndexOptions(self)
641
558
self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):-1])
642
559
except ValueError:
643
raise BadIndexOptions(self)
560
raise errors.BadIndexOptions(self)
644
561
options_line = stream.readline()
645
562
if not options_line.startswith(_OPTION_LEN):
646
raise BadIndexOptions(self)
563
raise errors.BadIndexOptions(self)
648
565
self._key_count = int(options_line[len(_OPTION_LEN):-1])
649
566
except ValueError:
650
raise BadIndexOptions(self)
567
raise errors.BadIndexOptions(self)
652
569
def _resolve_references(self, references):
653
570
"""Return the resolved key references for references.
664
581
node_refs.append(tuple([self._keys_by_offset[ref][0] for ref in ref_list]))
665
582
return tuple(node_refs)
668
def _find_index(range_map, key):
584
def _find_index(self, range_map, key):
669
585
"""Helper for the _parsed_*_index calls.
671
587
Given a range map - [(start, end), ...], finds the index of the range
754
670
if self._nodes is not None:
755
671
return self._iter_entries_from_total_buffer(keys)
757
return (result[1] for result in bisect_multi.bisect_multi_bytes(
673
return (result[1] for result in bisect_multi_bytes(
758
674
self._lookup_keys_via_location, self._size, keys))
760
676
def iter_entries_prefix(self, keys):
787
703
self._buffer_all()
788
704
if self._key_length == 1:
790
_sanity_check_key(self, key)
708
raise errors.BadIndexKey(key)
709
if len(key) != self._key_length:
710
raise errors.BadIndexKey(key)
791
711
if self.node_ref_lists:
792
712
value, node_refs = self._nodes[key]
793
713
yield self, key, value, node_refs
795
715
yield self, key, self._nodes[key]
797
717
nodes_by_key = self._get_nodes_by_key()
798
for entry in _iter_entries_prefix(self, nodes_by_key, keys):
721
raise errors.BadIndexKey(key)
722
if len(key) != self._key_length:
723
raise errors.BadIndexKey(key)
724
# find what it refers to:
725
key_dict = nodes_by_key
727
# find the subdict whose contents should be returned.
729
while len(elements) and elements[0] is not None:
730
key_dict = key_dict[elements[0]]
733
# a non-existant lookup.
738
key_dict = dicts.pop(-1)
739
# can't be empty or would not exist
740
item, value = key_dict.iteritems().next()
741
if type(value) == dict:
743
dicts.extend(key_dict.itervalues())
746
for value in key_dict.itervalues():
747
# each value is the key:value:node refs tuple
749
yield (self, ) + value
751
# the last thing looked up was a terminal element
752
yield (self, ) + key_dict
801
754
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
802
755
"""See BTreeIndex._find_ancestors."""
976
929
signature = bytes[0:len(self._signature())]
977
930
if not signature == self._signature():
978
raise BadIndexFormatSignature(self._name, GraphIndex)
931
raise errors.BadIndexFormatSignature(self._name, GraphIndex)
979
932
lines = bytes[len(self._signature()):].splitlines()
980
933
options_line = lines[0]
981
934
if not options_line.startswith(_OPTION_NODE_REFS):
982
raise BadIndexOptions(self)
935
raise errors.BadIndexOptions(self)
984
937
self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):])
985
938
except ValueError:
986
raise BadIndexOptions(self)
939
raise errors.BadIndexOptions(self)
987
940
options_line = lines[1]
988
941
if not options_line.startswith(_OPTION_KEY_ELEMENTS):
989
raise BadIndexOptions(self)
942
raise errors.BadIndexOptions(self)
991
944
self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):])
992
945
except ValueError:
993
raise BadIndexOptions(self)
946
raise errors.BadIndexOptions(self)
994
947
options_line = lines[2]
995
948
if not options_line.startswith(_OPTION_LEN):
996
raise BadIndexOptions(self)
949
raise errors.BadIndexOptions(self)
998
951
self._key_count = int(options_line[len(_OPTION_LEN):])
999
952
except ValueError:
1000
raise BadIndexOptions(self)
953
raise errors.BadIndexOptions(self)
1001
954
# calculate the bytes we have processed
1002
955
header_end = (len(signature) + len(lines[0]) + len(lines[1]) +
1003
956
len(lines[2]) + 3)
1004
self._parsed_bytes(0, (), header_end, ())
957
self._parsed_bytes(0, None, header_end, None)
1005
958
# setup parsing state
1006
959
self._expected_elements = 3 + self._key_length
1007
960
# raw data keyed by offset
1107
1060
if not start_adjacent:
1108
1061
# work around python bug in rfind
1109
1062
if trim_start is None:
1110
trim_start = data.find(b'\n') + 1
1063
trim_start = data.find('\n') + 1
1112
trim_start = data.find(b'\n', trim_start) + 1
1065
trim_start = data.find('\n', trim_start) + 1
1113
1066
if not (trim_start != 0):
1114
1067
raise AssertionError('no \n was present')
1115
1068
# print 'removing start', offset, trim_start, repr(data[:trim_start])
1116
1069
if not end_adjacent:
1117
1070
# work around python bug in rfind
1118
1071
if trim_end is None:
1119
trim_end = data.rfind(b'\n') + 1
1072
trim_end = data.rfind('\n') + 1
1121
trim_end = data.rfind(b'\n', None, trim_end) + 1
1074
trim_end = data.rfind('\n', None, trim_end) + 1
1122
1075
if not (trim_end != 0):
1123
1076
raise AssertionError('no \n was present')
1124
1077
# print 'removing end', offset, trim_end, repr(data[trim_end:])
1131
1084
offset += trim_start
1132
1085
# print "parsing", repr(trimmed_data)
1133
1086
# splitlines mangles the \r delimiters.. don't use it.
1134
lines = trimmed_data.split(b'\n')
1087
lines = trimmed_data.split('\n')
1137
1090
first_key, last_key, nodes, _ = self._parse_lines(lines, pos)
1149
1102
for line in lines:
1151
1104
# must be at the end
1153
1106
if not (self._size == pos + 1):
1154
1107
raise AssertionError("%s %s" % (self._size, pos))
1157
elements = line.split(b'\0')
1110
elements = line.split('\0')
1158
1111
if len(elements) != self._expected_elements:
1159
raise BadIndexData(self)
1112
raise errors.BadIndexData(self)
1160
1113
# keys are tuples. Each element is a string that may occur many
1161
1114
# times, so we intern them to save space. AB, RC, 200807
1162
key = tuple([bytesintern(element) for element in elements[:self._key_length]])
1115
key = tuple([intern(element) for element in elements[:self._key_length]])
1163
1116
if first_key is None:
1164
1117
first_key = key
1165
1118
absent, references, value = elements[-3:]
1167
for ref_string in references.split(b'\t'):
1120
for ref_string in references.split('\t'):
1168
1121
ref_lists.append(tuple([
1169
int(ref) for ref in ref_string.split(b'\r') if ref
1122
int(ref) for ref in ref_string.split('\r') if ref
1171
1124
ref_lists = tuple(ref_lists)
1172
1125
self._keys_by_offset[pos] = (key, absent, ref_lists, value)
1264
1217
# We read the whole range, most likely because the
1265
1218
# Transport upcast our readv ranges into one long request
1266
1219
# for enough total data to grab the whole index.
1267
self._buffer_all(BytesIO(data))
1220
self._buffer_all(StringIO(data))
1269
1222
if self._bisect_nodes is None:
1270
1223
# this must be the start
1334
1287
def get_parent_map(self, keys):
1335
1288
"""See graph.StackedParentsProvider.get_parent_map"""
1336
1289
search_keys = set(keys)
1337
if _mod_revision.NULL_REVISION in search_keys:
1338
search_keys.discard(_mod_revision.NULL_REVISION)
1339
found_parents = {_mod_revision.NULL_REVISION:[]}
1290
if NULL_REVISION in search_keys:
1291
search_keys.discard(NULL_REVISION)
1292
found_parents = {NULL_REVISION:[]}
1341
1294
found_parents = {}
1342
1295
for index, key, value, refs in self.iter_entries(search_keys):
1343
1296
parents = refs[0]
1344
1297
if not parents:
1345
parents = (_mod_revision.NULL_REVISION,)
1298
parents = (NULL_REVISION,)
1346
1299
found_parents[key] = parents
1347
1300
return found_parents
1349
__contains__ = _has_key_from_parent_map
1302
has_key = _has_key_from_parent_map
1351
1304
def insert_index(self, pos, index, name=None):
1352
1305
"""Insert a new index in the list of indices to query.
1484
1434
indices_info = zip(self._index_names, self._indices)
1485
1435
if 'index' in debug.debug_flags:
1486
indices_info = list(indices_info)
1487
trace.mutter('CombinedGraphIndex reordering: currently %r, '
1488
'promoting %r', indices_info, hit_indices)
1436
mutter('CombinedGraphIndex reordering: currently %r, promoting %r',
1437
indices_info, hit_indices)
1490
1439
unhit_names = []
1491
1440
new_hit_indices = []
1508
1457
self._indices = new_hit_indices + unhit_indices
1509
1458
self._index_names = hit_names + unhit_names
1510
1459
if 'index' in debug.debug_flags:
1511
trace.mutter('CombinedGraphIndex reordered: %r', self._indices)
1460
mutter('CombinedGraphIndex reordered: %r', self._indices)
1512
1461
return hit_names
1514
1463
def _move_to_front_by_name(self, hit_names):
1601
1550
return sum((index.key_count() for index in self._indices), 0)
1602
except errors.NoSuchFile as e:
1603
if not self._try_reload(e):
1551
except errors.NoSuchFile:
1552
self._reload_or_raise()
1606
1554
missing_keys = _missing_keys_from_parent_map
1608
def _try_reload(self, error):
1556
def _reload_or_raise(self):
1609
1557
"""We just got a NoSuchFile exception.
1611
1559
Try to reload the indices, if it fails, just raise the current
1614
1562
if self._reload_func is None:
1616
trace.mutter('Trying to reload after getting exception: %s', str(error))
1564
exc_type, exc_value, exc_traceback = sys.exc_info()
1565
trace.mutter('Trying to reload after getting exception: %s',
1617
1567
if not self._reload_func():
1618
1568
# We tried to reload, but nothing changed, so we fail anyway
1619
1569
trace.mutter('_reload_func indicated nothing has changed.'
1620
1570
' Raising original exception.')
1571
raise exc_type, exc_value, exc_traceback
1624
1573
def set_sibling_indices(self, sibling_combined_graph_indices):
1625
1574
"""Set the CombinedGraphIndex objects to reorder after reordering self.
1669
1617
trace.mutter_callsite(3,
1670
1618
"iter_all_entries scales with size of history.")
1671
1619
if self.reference_lists:
1672
for key, (absent, references, value) in viewitems(self._nodes):
1620
for key, (absent, references, value) in self._nodes.iteritems():
1674
1622
yield self, key, value, references
1676
for key, (absent, references, value) in viewitems(self._nodes):
1624
for key, (absent, references, value) in self._nodes.iteritems():
1678
1626
yield self, key, value
1717
1665
will be returned, and every match that is in the index will be
1668
# XXX: To much duplication with the GraphIndex class; consider finding
1669
# a good place to pull out the actual common logic.
1720
1670
keys = set(keys)
1723
1673
if self._key_length == 1:
1724
1674
for key in keys:
1725
_sanity_check_key(self, key)
1677
raise errors.BadIndexKey(key)
1678
if len(key) != self._key_length:
1679
raise errors.BadIndexKey(key)
1726
1680
node = self._nodes[key]
1732
1686
yield self, key, node[2]
1734
1688
nodes_by_key = self._get_nodes_by_key()
1735
for entry in _iter_entries_prefix(self, nodes_by_key, keys):
1692
raise errors.BadIndexKey(key)
1693
if len(key) != self._key_length:
1694
raise errors.BadIndexKey(key)
1695
# find what it refers to:
1696
key_dict = nodes_by_key
1697
elements = list(key)
1698
# find the subdict to return
1700
while len(elements) and elements[0] is not None:
1701
key_dict = key_dict[elements[0]]
1704
# a non-existant lookup.
1709
key_dict = dicts.pop(-1)
1710
# can't be empty or would not exist
1711
item, value = key_dict.iteritems().next()
1712
if type(value) == dict:
1714
dicts.extend(key_dict.itervalues())
1717
for value in key_dict.itervalues():
1718
yield (self, ) + value
1720
yield (self, ) + key_dict
1738
1722
def key_count(self):
1739
1723
"""Return an estimate of the number of keys in this index.
1745
1729
def validate(self):
1746
1730
"""In memory index's have no known corruption at the moment."""
1748
def __lt__(self, other):
1749
# We don't really care about the order, just that there is an order.
1750
if (not isinstance(other, GraphIndex) and
1751
not isinstance(other, InMemoryGraphIndex)):
1752
raise TypeError(other)
1753
return hash(self) < hash(other)
1756
1733
class GraphIndexPrefixAdapter(object):
1757
1734
"""An adapter between GraphIndex with different key lengths.
1815
1792
for node in an_iter:
1817
1794
if node[1][:self.prefix_len] != self.prefix:
1818
raise BadIndexData(self)
1795
raise errors.BadIndexData(self)
1819
1796
for ref_list in node[3]:
1820
1797
for ref_node in ref_list:
1821
1798
if ref_node[:self.prefix_len] != self.prefix:
1822
raise BadIndexData(self)
1799
raise errors.BadIndexData(self)
1823
1800
yield node[0], node[1][self.prefix_len:], node[2], (
1824
1801
tuple(tuple(ref_node[self.prefix_len:] for ref_node in ref_list)
1825
1802
for ref_list in node[3]))
1878
1855
def validate(self):
1879
1856
"""Call the adapted's validate."""
1880
1857
self.adapted.validate()
1883
def _sanity_check_key(index_or_builder, key):
1884
"""Raise BadIndexKey if key cannot be used for prefix matching."""
1886
raise BadIndexKey(key)
1887
if len(key) != index_or_builder._key_length:
1888
raise BadIndexKey(key)
1891
def _iter_entries_prefix(index_or_builder, nodes_by_key, keys):
1892
"""Helper for implementing prefix matching iterators."""
1894
_sanity_check_key(index_or_builder, key)
1895
# find what it refers to:
1896
key_dict = nodes_by_key
1897
elements = list(key)
1898
# find the subdict whose contents should be returned.
1900
while len(elements) and elements[0] is not None:
1901
key_dict = key_dict[elements[0]]
1904
# a non-existant lookup.
1909
values_view = viewvalues(dicts.pop())
1910
# can't be empty or would not exist
1911
value = next(iter(values_view))
1912
if isinstance(value, dict):
1913
# still descending, push values
1914
dicts.extend(values_view)
1916
# at leaf tuples, yield values
1917
for value in values_view:
1918
# each value is the key:value:node refs tuple
1920
yield (index_or_builder, ) + value
1922
# the last thing looked up was a terminal element
1923
yield (index_or_builder, ) + key_dict
added
removed
bzrlib/index.py
