53
52
_newline_null_re = re.compile('[\n\0]')
56
def _has_key_from_parent_map(self, key):
57
"""Check if this index has one key.
59
If it's possible to check for multiple keys at once through
60
calling get_parent_map that should be faster.
62
return (key in self.get_parent_map([key]))
65
def _missing_keys_from_parent_map(self, keys):
66
return set(keys) - set(self.get_parent_map(keys))
69
55
class GraphIndexBuilder(object):
70
56
"""A builder that can build a GraphIndex.
72
58
The resulting graph has the structure:
74
60
_SIGNATURE OPTIONS NODES NEWLINE
75
61
_SIGNATURE := 'Bazaar Graph Index 1' NEWLINE
76
62
OPTIONS := 'node_ref_lists=' DIGITS NEWLINE
93
79
:param key_elements: The number of bytestrings in each key.
95
81
self.reference_lists = reference_lists
96
83
# A dict of {key: (absent, ref_lists, value)}
98
# Keys that are referenced but not actually present in this index
99
self._absent_keys = set()
100
85
self._nodes_by_key = None
101
86
self._key_length = key_elements
102
self._optimize_for_size = False
103
self._combine_backing_indices = True
105
88
def _check_key(self, key):
106
89
"""Raise BadIndexKey if key is not a valid key for this index."""
107
if type(key) not in (tuple, StaticTuple):
90
if type(key) != tuple:
108
91
raise errors.BadIndexKey(key)
109
92
if self._key_length != len(key):
110
93
raise errors.BadIndexKey(key)
112
95
if not element or _whitespace_re.search(element) is not None:
113
96
raise errors.BadIndexKey(element)
115
def _external_references(self):
116
"""Return references that are not present in this index.
120
# TODO: JAM 2008-11-21 This makes an assumption about how the reference
121
# lists are used. It is currently correct for pack-0.92 through
122
# 1.9, which use the node references (3rd column) second
123
# reference list as the compression parent. Perhaps this should
124
# be moved into something higher up the stack, since it
125
# makes assumptions about how the index is used.
126
if self.reference_lists > 1:
127
for node in self.iter_all_entries():
129
refs.update(node[3][1])
132
# If reference_lists == 0 there can be no external references, and
133
# if reference_lists == 1, then there isn't a place to store the
137
98
def _get_nodes_by_key(self):
138
99
if self._nodes_by_key is None:
139
100
nodes_by_key = {}
229
187
# There may be duplicates, but I don't think it is worth worrying
231
189
self._nodes[reference] = ('a', (), '')
232
self._absent_keys.update(absent_references)
233
self._absent_keys.discard(key)
234
190
self._nodes[key] = ('', node_refs, value)
235
192
if self._nodes_by_key is not None and self._key_length > 1:
236
193
self._update_nodes_by_key(key, value, node_refs)
238
def clear_cache(self):
239
"""See GraphIndex.clear_cache()
241
This is a no-op, but we need the api to conform to a generic 'Index'
245
195
def finish(self):
246
196
lines = [_SIGNATURE]
247
197
lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
248
198
lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
249
key_count = len(self._nodes) - len(self._absent_keys)
250
lines.append(_OPTION_LEN + str(key_count) + '\n')
199
lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
251
200
prefix_length = sum(len(x) for x in lines)
252
201
# references are byte offsets. To avoid having to do nasty
253
202
# polynomial work to resolve offsets (references to later in the
329
278
(len(result.getvalue()), expected_bytes))
332
def set_optimize(self, for_size=None, combine_backing_indices=None):
333
"""Change how the builder tries to optimize the result.
335
:param for_size: Tell the builder to try and make the index as small as
337
:param combine_backing_indices: If the builder spills to disk to save
338
memory, should the on-disk indices be combined. Set to True if you
339
are going to be probing the index, but to False if you are not. (If
340
you are not querying, then the time spent combining is wasted.)
343
# GraphIndexBuilder itself doesn't pay attention to the flag yet, but
345
if for_size is not None:
346
self._optimize_for_size = for_size
347
if combine_backing_indices is not None:
348
self._combine_backing_indices = combine_backing_indices
350
def find_ancestry(self, keys, ref_list_num):
351
"""See CombinedGraphIndex.find_ancestry()"""
357
for _, key, value, ref_lists in self.iter_entries(pending):
358
parent_keys = ref_lists[ref_list_num]
359
parent_map[key] = parent_keys
360
next_pending.update([p for p in parent_keys if p not in
362
missing_keys.update(pending.difference(parent_map))
363
pending = next_pending
364
return parent_map, missing_keys
367
282
class GraphIndex(object):
368
283
"""An index for data with embedded graphs.
370
285
The index maps keys to a list of key reference lists, and a value.
371
286
Each node has the same number of key reference lists. Each key reference
372
287
list can be empty or an arbitrary length. The value is an opaque NULL
373
terminated string without any newlines. The storage of the index is
288
terminated string without any newlines. The storage of the index is
374
289
hidden in the interface: keys and key references are always tuples of
375
290
bytestrings, never the internal representation (e.g. dictionary offsets).
468
382
node_value = value
469
383
self._nodes[key] = node_value
470
384
# cache the keys for quick set intersections
385
self._keys = set(self._nodes)
471
386
if trailers != 1:
472
387
# there must be one line - the empty trailer line.
473
388
raise errors.BadIndexData(self)
475
def clear_cache(self):
476
"""Clear out any cached/memoized values.
478
This can be called at any time, but generally it is used when we have
479
extracted some information, but don't expect to be requesting any more
483
def external_references(self, ref_list_num):
484
"""Return references that are not present in this index.
487
if ref_list_num + 1 > self.node_ref_lists:
488
raise ValueError('No ref list %d, index has %d ref lists'
489
% (ref_list_num, self.node_ref_lists))
492
for key, (value, ref_lists) in nodes.iteritems():
493
ref_list = ref_lists[ref_list_num]
494
refs.update([ref for ref in ref_list if ref not in nodes])
497
390
def _get_nodes_by_key(self):
498
391
if self._nodes_by_key is None:
499
392
nodes_by_key = {}
626
519
def _iter_entries_from_total_buffer(self, keys):
627
520
"""Iterate over keys when the entire index is parsed."""
628
# Note: See the note in BTreeBuilder.iter_entries for why we don't use
629
# .intersection() here
631
keys = [key for key in keys if key in nodes]
521
keys = keys.intersection(self._keys)
632
522
if self.node_ref_lists:
634
value, node_refs = nodes[key]
524
value, node_refs = self._nodes[key]
635
525
yield self, key, value, node_refs
638
yield self, key, nodes[key]
528
yield self, key, self._nodes[key]
640
530
def iter_entries(self, keys):
641
531
"""Iterate over keys within the index.
744
634
# the last thing looked up was a terminal element
745
635
yield (self, ) + key_dict
747
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
748
"""See BTreeIndex._find_ancestors."""
749
# The api can be implemented as a trivial overlay on top of
750
# iter_entries, it is not an efficient implementation, but it at least
754
for index, key, value, refs in self.iter_entries(keys):
755
parent_keys = refs[ref_list_num]
757
parent_map[key] = parent_keys
758
search_keys.update(parent_keys)
759
# Figure out what, if anything, was missing
760
missing_keys.update(set(keys).difference(found_keys))
761
search_keys = search_keys.difference(parent_map)
764
637
def key_count(self):
765
638
"""Return an estimate of the number of keys in this index.
767
640
For GraphIndex the estimate is exact.
769
642
if self._key_count is None:
1233
1106
in the index list.
1236
def __init__(self, indices, reload_func=None):
1109
def __init__(self, indices):
1237
1110
"""Create a CombinedGraphIndex backed by indices.
1239
1112
:param indices: An ordered list of indices to query for data.
1240
:param reload_func: A function to call if we find we are missing an
1241
index. Should have the form reload_func() => True/False to indicate
1242
if reloading actually changed anything.
1244
1114
self._indices = indices
1245
self._reload_func = reload_func
1247
1116
def __repr__(self):
1248
1117
return "%s(%s)" % (
1249
1118
self.__class__.__name__,
1250
1119
', '.join(map(repr, self._indices)))
1252
def clear_cache(self):
1253
"""See GraphIndex.clear_cache()"""
1254
for index in self._indices:
1121
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
1122
def get_parents(self, revision_ids):
1123
"""See graph._StackedParentsProvider.get_parents.
1125
This implementation thunks the graph.Graph.get_parents api across to
1128
:param revision_ids: An iterable of graph keys for this graph.
1129
:return: A list of parent details for each key in revision_ids.
1130
Each parent details will be one of:
1131
* None when the key was missing
1132
* (NULL_REVISION,) when the key has no parents.
1133
* (parent_key, parent_key...) otherwise.
1135
parent_map = self.get_parent_map(revision_ids)
1136
return [parent_map.get(r, None) for r in revision_ids]
1257
1138
def get_parent_map(self, keys):
1258
"""See graph.StackedParentsProvider.get_parent_map"""
1139
"""See graph._StackedParentsProvider.get_parent_map"""
1259
1140
search_keys = set(keys)
1260
1141
if NULL_REVISION in search_keys:
1261
1142
search_keys.discard(NULL_REVISION)
1351
1220
seen_keys = set()
1354
for index in self._indices:
1355
for node in index.iter_entries_prefix(keys):
1356
if node[1] in seen_keys:
1358
seen_keys.add(node[1])
1361
except errors.NoSuchFile:
1362
self._reload_or_raise()
1364
def find_ancestry(self, keys, ref_list_num):
1365
"""Find the complete ancestry for the given set of keys.
1367
Note that this is a whole-ancestry request, so it should be used
1370
:param keys: An iterable of keys to look for
1371
:param ref_list_num: The reference list which references the parents
1373
:return: (parent_map, missing_keys)
1375
missing_keys = set()
1377
keys_to_lookup = set(keys)
1379
while keys_to_lookup:
1380
# keys that *all* indexes claim are missing, stop searching them
1382
all_index_missing = None
1383
# print 'gen\tidx\tsub\tn_keys\tn_pmap\tn_miss'
1384
# print '%4d\t\t\t%4d\t%5d\t%5d' % (generation, len(keys_to_lookup),
1386
# len(missing_keys))
1387
for index_idx, index in enumerate(self._indices):
1388
# TODO: we should probably be doing something with
1389
# 'missing_keys' since we've already determined that
1390
# those revisions have not been found anywhere
1391
index_missing_keys = set()
1392
# Find all of the ancestry we can from this index
1393
# keep looking until the search_keys set is empty, which means
1394
# things we didn't find should be in index_missing_keys
1395
search_keys = keys_to_lookup
1397
# print ' \t%2d\t\t%4d\t%5d\t%5d' % (
1398
# index_idx, len(search_keys),
1399
# len(parent_map), len(index_missing_keys))
1402
# TODO: ref_list_num should really be a parameter, since
1403
# CombinedGraphIndex does not know what the ref lists
1405
search_keys = index._find_ancestors(search_keys,
1406
ref_list_num, parent_map, index_missing_keys)
1407
# print ' \t \t%2d\t%4d\t%5d\t%5d' % (
1408
# sub_generation, len(search_keys),
1409
# len(parent_map), len(index_missing_keys))
1410
# Now set whatever was missing to be searched in the next index
1411
keys_to_lookup = index_missing_keys
1412
if all_index_missing is None:
1413
all_index_missing = set(index_missing_keys)
1415
all_index_missing.intersection_update(index_missing_keys)
1416
if not keys_to_lookup:
1418
if all_index_missing is None:
1419
# There were no indexes, so all search keys are 'missing'
1420
missing_keys.update(keys_to_lookup)
1421
keys_to_lookup = None
1423
missing_keys.update(all_index_missing)
1424
keys_to_lookup.difference_update(all_index_missing)
1425
return parent_map, missing_keys
1221
for index in self._indices:
1222
for node in index.iter_entries_prefix(keys):
1223
if node[1] in seen_keys:
1225
seen_keys.add(node[1])
1427
1228
def key_count(self):
1428
1229
"""Return an estimate of the number of keys in this index.
1430
1231
For CombinedGraphIndex this is approximated by the sum of the keys of
1431
1232
the child indices. As child indices may have duplicate keys this can
1432
1233
have a maximum error of the number of child indices * largest number of
1433
1234
keys in any index.
1437
return sum((index.key_count() for index in self._indices), 0)
1438
except errors.NoSuchFile:
1439
self._reload_or_raise()
1441
missing_keys = _missing_keys_from_parent_map
1443
def _reload_or_raise(self):
1444
"""We just got a NoSuchFile exception.
1446
Try to reload the indices, if it fails, just raise the current
1449
if self._reload_func is None:
1451
exc_type, exc_value, exc_traceback = sys.exc_info()
1452
trace.mutter('Trying to reload after getting exception: %s',
1454
if not self._reload_func():
1455
# We tried to reload, but nothing changed, so we fail anyway
1456
trace.mutter('_reload_func indicated nothing has changed.'
1457
' Raising original exception.')
1458
raise exc_type, exc_value, exc_traceback
1236
return sum((index.key_count() for index in self._indices), 0)
1460
1238
def validate(self):
1461
1239
"""Validate that everything in the index can be accessed."""
1464
for index in self._indices:
1467
except errors.NoSuchFile:
1468
self._reload_or_raise()
1240
for index in self._indices:
1471
1244
class InMemoryGraphIndex(GraphIndexBuilder):
added
removed
bzrlib/index.py
