13
13
# You should have received a copy of the GNU General Public License
14
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
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
17
"""Indexing facilities."""
93
93
:param key_elements: The number of bytestrings in each key.
95
95
self.reference_lists = reference_lists
97
96
# 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()
99
100
self._nodes_by_key = None
100
101
self._key_length = key_elements
101
102
self._optimize_for_size = False
103
self._combine_backing_indices = True
103
105
def _check_key(self, key):
104
106
"""Raise BadIndexKey if key is not a valid key for this index."""
105
if type(key) != tuple:
107
if type(key) not in (tuple, StaticTuple):
106
108
raise errors.BadIndexKey(key)
107
109
if self._key_length != len(key):
108
110
raise errors.BadIndexKey(key)
165
167
key_dict = self._nodes_by_key
166
168
if self.reference_lists:
167
key_value = key, value, node_refs
169
key_value = StaticTuple(key, value, node_refs)
169
key_value = key, value
171
key_value = StaticTuple(key, value)
170
172
for subkey in key[:-1]:
171
173
key_dict = key_dict.setdefault(subkey, {})
172
174
key_dict[key[-1]] = key_value
202
205
if reference not in self._nodes:
203
206
self._check_key(reference)
204
207
absent_references.append(reference)
205
node_refs.append(tuple(reference_list))
206
return tuple(node_refs), absent_references
208
reference_list = as_st([as_st(ref).intern()
209
for ref in reference_list])
210
node_refs.append(reference_list)
211
return as_st(node_refs), absent_references
208
213
def add_node(self, key, value, references=()):
209
214
"""Add a node to the index.
224
229
# There may be duplicates, but I don't think it is worth worrying
226
231
self._nodes[reference] = ('a', (), '')
232
self._absent_keys.update(absent_references)
233
self._absent_keys.discard(key)
227
234
self._nodes[key] = ('', node_refs, value)
229
235
if self._nodes_by_key is not None and self._key_length > 1:
230
236
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'
232
245
def finish(self):
233
246
lines = [_SIGNATURE]
234
247
lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
235
248
lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
236
lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
249
key_count = len(self._nodes) - len(self._absent_keys)
250
lines.append(_OPTION_LEN + str(key_count) + '\n')
237
251
prefix_length = sum(len(x) for x in lines)
238
252
# references are byte offsets. To avoid having to do nasty
239
253
# polynomial work to resolve offsets (references to later in the
315
329
(len(result.getvalue()), expected_bytes))
318
def set_optimize(self, for_size=True):
332
def set_optimize(self, for_size=None, combine_backing_indices=None):
319
333
"""Change how the builder tries to optimize the result.
321
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.)
325
343
# GraphIndexBuilder itself doesn't pay attention to the flag yet, but
326
344
# other builders do.
327
self._optimize_for_size = for_size
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
330
367
class GraphIndex(object):
331
368
"""An index for data with embedded graphs.
333
370
The index maps keys to a list of key reference lists, and a value.
334
371
Each node has the same number of key reference lists. Each key reference
335
372
list can be empty or an arbitrary length. The value is an opaque NULL
336
terminated string without any newlines. The storage of the index is
373
terminated string without any newlines. The storage of the index is
337
374
hidden in the interface: keys and key references are always tuples of
338
375
bytestrings, never the internal representation (e.g. dictionary offsets).
345
382
suitable for production use. :XXX
348
def __init__(self, transport, name, size):
385
def __init__(self, transport, name, size, unlimited_cache=False):
349
386
"""Open an index called name on transport.
351
388
:param transport: A bzrlib.transport.Transport.
430
468
node_value = value
431
469
self._nodes[key] = node_value
432
470
# cache the keys for quick set intersections
433
self._keys = set(self._nodes)
434
471
if trailers != 1:
435
472
# there must be one line - the empty trailer line.
436
473
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])
438
497
def _get_nodes_by_key(self):
439
498
if self._nodes_by_key is None:
440
499
nodes_by_key = {}
503
562
def _resolve_references(self, references):
504
563
"""Return the resolved key references for references.
506
565
References are resolved by looking up the location of the key in the
507
566
_keys_by_offset map and substituting the key name, preserving ordering.
509
:param references: An iterable of iterables of key locations. e.g.
568
:param references: An iterable of iterables of key locations. e.g.
510
569
[[123, 456], [123]]
511
570
:return: A tuple of tuples of keys.
567
626
def _iter_entries_from_total_buffer(self, keys):
568
627
"""Iterate over keys when the entire index is parsed."""
569
keys = keys.intersection(self._keys)
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]
570
632
if self.node_ref_lists:
572
value, node_refs = self._nodes[key]
634
value, node_refs = nodes[key]
573
635
yield self, key, value, node_refs
576
yield self, key, self._nodes[key]
638
yield self, key, nodes[key]
578
640
def iter_entries(self, keys):
579
641
"""Iterate over keys within the index.
682
744
# the last thing looked up was a terminal element
683
745
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)
685
764
def key_count(self):
686
765
"""Return an estimate of the number of keys in this index.
688
767
For GraphIndex the estimate is exact.
690
769
if self._key_count is None:
732
811
# - if we have examined this part of the file already - yes
733
812
index = self._parsed_byte_index(location)
734
if (len(self._parsed_byte_map) and
813
if (len(self._parsed_byte_map) and
735
814
self._parsed_byte_map[index][0] <= location and
736
815
self._parsed_byte_map[index][1] > location):
737
816
# the byte region has been parsed, so no read is needed.
1170
1249
self.__class__.__name__,
1171
1250
', '.join(map(repr, self._indices)))
1173
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
1174
def get_parents(self, revision_ids):
1175
"""See graph._StackedParentsProvider.get_parents.
1177
This implementation thunks the graph.Graph.get_parents api across to
1180
:param revision_ids: An iterable of graph keys for this graph.
1181
:return: A list of parent details for each key in revision_ids.
1182
Each parent details will be one of:
1183
* None when the key was missing
1184
* (NULL_REVISION,) when the key has no parents.
1185
* (parent_key, parent_key...) otherwise.
1187
parent_map = self.get_parent_map(revision_ids)
1188
return [parent_map.get(r, None) for r in revision_ids]
1252
def clear_cache(self):
1253
"""See GraphIndex.clear_cache()"""
1254
for index in self._indices:
1190
1257
def get_parent_map(self, keys):
1191
"""See graph._StackedParentsProvider.get_parent_map"""
1258
"""See graph.StackedParentsProvider.get_parent_map"""
1192
1259
search_keys = set(keys)
1193
1260
if NULL_REVISION in search_keys:
1194
1261
search_keys.discard(NULL_REVISION)
1294
1361
except errors.NoSuchFile:
1295
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
1297
1427
def key_count(self):
1298
1428
"""Return an estimate of the number of keys in this index.
1385
1515
defined order for the result iteration - it will be in the most
1386
1516
efficient order for the index (keys iteration order in this case).
1518
# Note: See BTreeBuilder.iter_entries for an explanation of why we
1519
# aren't using set().intersection() here
1521
keys = [key for key in keys if key in nodes]
1389
1522
if self.reference_lists:
1390
for key in keys.intersection(self._keys):
1391
node = self._nodes[key]
1392
1525
if not node[0]:
1393
1526
yield self, key, node[2], node[1]
1395
for key in keys.intersection(self._keys):
1396
node = self._nodes[key]
1397
1530
if not node[0]:
1398
1531
yield self, key, node[2]
1485
1618
Queries against this will emit queries against the adapted Graph with the
1486
1619
prefix added, queries for all items use iter_entries_prefix. The returned
1487
nodes will have their keys and node references adjusted to remove the
1620
nodes will have their keys and node references adjusted to remove the
1488
1621
prefix. Finally, an add_nodes_callback can be supplied - when called the
1489
1622
nodes and references being added will have prefix prepended.
added
removed
bzrlib/index.py
