56
52
_newline_null_re = re.compile('[\n\0]')
59
def _has_key_from_parent_map(self, key):
60
"""Check if this index has one key.
62
If it's possible to check for multiple keys at once through
63
calling get_parent_map that should be faster.
65
return (key in self.get_parent_map([key]))
68
def _missing_keys_from_parent_map(self, keys):
69
return set(keys) - set(self.get_parent_map(keys))
72
55
class GraphIndexBuilder(object):
73
56
"""A builder that can build a GraphIndex.
75
The resulting graph has the structure::
77
_SIGNATURE OPTIONS NODES NEWLINE
78
_SIGNATURE := 'Bazaar Graph Index 1' NEWLINE
79
OPTIONS := 'node_ref_lists=' DIGITS NEWLINE
81
NODE := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
82
KEY := Not-whitespace-utf8
84
REFERENCES := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
85
REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
86
REFERENCE := DIGITS ; digits is the byte offset in the index of the
88
VALUE := no-newline-no-null-bytes
58
The resulting graph has the structure:
60
_SIGNATURE OPTIONS NODES NEWLINE
61
_SIGNATURE := 'Bazaar Graph Index 1' NEWLINE
62
OPTIONS := 'node_ref_lists=' DIGITS NEWLINE
64
NODE := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
65
KEY := Not-whitespace-utf8
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
71
VALUE := no-newline-no-null-bytes
91
74
def __init__(self, reference_lists=0, key_elements=1):
338
278
(len(result.getvalue()), expected_bytes))
341
def set_optimize(self, for_size=None, combine_backing_indices=None):
342
"""Change how the builder tries to optimize the result.
344
:param for_size: Tell the builder to try and make the index as small as
346
:param combine_backing_indices: If the builder spills to disk to save
347
memory, should the on-disk indices be combined. Set to True if you
348
are going to be probing the index, but to False if you are not. (If
349
you are not querying, then the time spent combining is wasted.)
352
# GraphIndexBuilder itself doesn't pay attention to the flag yet, but
354
if for_size is not None:
355
self._optimize_for_size = for_size
356
if combine_backing_indices is not None:
357
self._combine_backing_indices = combine_backing_indices
359
def find_ancestry(self, keys, ref_list_num):
360
"""See CombinedGraphIndex.find_ancestry()"""
366
for _, key, value, ref_lists in self.iter_entries(pending):
367
parent_keys = ref_lists[ref_list_num]
368
parent_map[key] = parent_keys
369
next_pending.update([p for p in parent_keys if p not in
371
missing_keys.update(pending.difference(parent_map))
372
pending = next_pending
373
return parent_map, missing_keys
376
282
class GraphIndex(object):
377
283
"""An index for data with embedded graphs.
379
285
The index maps keys to a list of key reference lists, and a value.
380
286
Each node has the same number of key reference lists. Each key reference
381
287
list can be empty or an arbitrary length. The value is an opaque NULL
382
terminated string without any newlines. The storage of the index is
288
terminated string without any newlines. The storage of the index is
383
289
hidden in the interface: keys and key references are always tuples of
384
290
bytestrings, never the internal representation (e.g. dictionary offsets).
486
382
node_value = value
487
383
self._nodes[key] = node_value
384
if self._key_length > 1:
385
# TODO: We may want to do this lazily, but if we are calling
386
# _buffer_all, we are likely to be doing
387
# iter_entries_prefix
388
key_dict = self._nodes_by_key
389
if self.node_ref_lists:
390
key_value = key, node_value[0], node_value[1]
392
key_value = key, node_value
393
# For a key of (foo, bar, baz) create
394
# _nodes_by_key[foo][bar][baz] = key_value
395
for subkey in key[:-1]:
396
key_dict = key_dict.setdefault(subkey, {})
397
key_dict[key[-1]] = key_value
488
398
# cache the keys for quick set intersections
399
self._keys = set(self._nodes)
489
400
if trailers != 1:
490
401
# there must be one line - the empty trailer line.
491
402
raise errors.BadIndexData(self)
493
def clear_cache(self):
494
"""Clear out any cached/memoized values.
496
This can be called at any time, but generally it is used when we have
497
extracted some information, but don't expect to be requesting any more
501
def external_references(self, ref_list_num):
502
"""Return references that are not present in this index.
505
if ref_list_num + 1 > self.node_ref_lists:
506
raise ValueError('No ref list %d, index has %d ref lists'
507
% (ref_list_num, self.node_ref_lists))
510
for key, (value, ref_lists) in nodes.iteritems():
511
ref_list = ref_lists[ref_list_num]
512
refs.update([ref for ref in ref_list if ref not in nodes])
515
def _get_nodes_by_key(self):
516
if self._nodes_by_key is None:
518
if self.node_ref_lists:
519
for key, (value, references) in self._nodes.iteritems():
520
key_dict = nodes_by_key
521
for subkey in key[:-1]:
522
key_dict = key_dict.setdefault(subkey, {})
523
key_dict[key[-1]] = key, value, references
525
for key, value in self._nodes.iteritems():
526
key_dict = nodes_by_key
527
for subkey in key[:-1]:
528
key_dict = key_dict.setdefault(subkey, {})
529
key_dict[key[-1]] = key, value
530
self._nodes_by_key = nodes_by_key
531
return self._nodes_by_key
533
404
def iter_all_entries(self):
534
405
"""Iterate over all keys within the index.
1252
1091
class CombinedGraphIndex(object):
1253
1092
"""A GraphIndex made up from smaller GraphIndices.
1255
1094
The backing indices must implement GraphIndex, and are presumed to be
1258
1097
Queries against the combined index will be made against the first index,
1259
and then the second and so on. The order of indices can thus influence
1098
and then the second and so on. The order of index's can thus influence
1260
1099
performance significantly. For example, if one index is on local disk and a
1261
1100
second on a remote server, the local disk index should be before the other
1262
1101
in the index list.
1264
Also, queries tend to need results from the same indices as previous
1265
queries. So the indices will be reordered after every query to put the
1266
indices that had the result(s) of that query first (while otherwise
1267
preserving the relative ordering).
1270
def __init__(self, indices, reload_func=None):
1104
def __init__(self, indices):
1271
1105
"""Create a CombinedGraphIndex backed by indices.
1273
1107
:param indices: An ordered list of indices to query for data.
1274
:param reload_func: A function to call if we find we are missing an
1275
index. Should have the form reload_func() => True/False to indicate
1276
if reloading actually changed anything.
1278
1109
self._indices = indices
1279
self._reload_func = reload_func
1280
# Sibling indices are other CombinedGraphIndex that we should call
1281
# _move_to_front_by_name on when we auto-reorder ourself.
1282
self._sibling_indices = []
1283
# A list of names that corresponds to the instances in self._indices,
1284
# so _index_names[0] is always the name for _indices[0], etc. Sibling
1285
# indices must all use the same set of names as each other.
1286
self._index_names = [None] * len(self._indices)
1288
1111
def __repr__(self):
1289
1112
return "%s(%s)" % (
1290
1113
self.__class__.__name__,
1291
1114
', '.join(map(repr, self._indices)))
1293
def clear_cache(self):
1294
"""See GraphIndex.clear_cache()"""
1295
for index in self._indices:
1116
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
1117
def get_parents(self, revision_ids):
1118
"""See graph._StackedParentsProvider.get_parents.
1120
This implementation thunks the graph.Graph.get_parents api across to
1123
:param revision_ids: An iterable of graph keys for this graph.
1124
:return: A list of parent details for each key in revision_ids.
1125
Each parent details will be one of:
1126
* None when the key was missing
1127
* (NULL_REVISION,) when the key has no parents.
1128
* (parent_key, parent_key...) otherwise.
1130
parent_map = self.get_parent_map(revision_ids)
1131
return [parent_map.get(r, None) for r in revision_ids]
1298
1133
def get_parent_map(self, keys):
1299
"""See graph.StackedParentsProvider.get_parent_map"""
1134
"""See graph._StackedParentsProvider.get_parent_map"""
1300
1135
search_keys = set(keys)
1301
if _mod_revision.NULL_REVISION in search_keys:
1302
search_keys.discard(_mod_revision.NULL_REVISION)
1303
found_parents = {_mod_revision.NULL_REVISION:[]}
1136
if NULL_REVISION in search_keys:
1137
search_keys.discard(NULL_REVISION)
1138
found_parents = {NULL_REVISION:[]}
1305
1140
found_parents = {}
1306
1141
for index, key, value, refs in self.iter_entries(search_keys):
1307
1142
parents = refs[0]
1308
1143
if not parents:
1309
parents = (_mod_revision.NULL_REVISION,)
1144
parents = (NULL_REVISION,)
1310
1145
found_parents[key] = parents
1311
1146
return found_parents
1313
has_key = _has_key_from_parent_map
1315
def insert_index(self, pos, index, name=None):
1148
def insert_index(self, pos, index):
1316
1149
"""Insert a new index in the list of indices to query.
1318
1151
:param pos: The position to insert the index.
1319
1152
:param index: The index to insert.
1320
:param name: a name for this index, e.g. a pack name. These names can
1321
be used to reflect index reorderings to related CombinedGraphIndex
1322
instances that use the same names. (see set_sibling_indices)
1324
1154
self._indices.insert(pos, index)
1325
self._index_names.insert(pos, name)
1327
1156
def iter_all_entries(self):
1328
1157
"""Iterate over all keys within the index
1402
1215
seen_keys = set()
1406
for index in self._indices:
1408
for node in index.iter_entries_prefix(keys):
1409
if node[1] in seen_keys:
1411
seen_keys.add(node[1])
1415
hit_indices.append(index)
1417
except errors.NoSuchFile:
1418
self._reload_or_raise()
1419
self._move_to_front(hit_indices)
1421
def _move_to_front(self, hit_indices):
1422
"""Rearrange self._indices so that hit_indices are first.
1424
Order is maintained as much as possible, e.g. the first unhit index
1425
will be the first index in _indices after the hit_indices, and the
1426
hit_indices will be present in exactly the order they are passed to
1429
_move_to_front propagates to all objects in self._sibling_indices by
1430
calling _move_to_front_by_name.
1432
if self._indices[:len(hit_indices)] == hit_indices:
1433
# The 'hit_indices' are already at the front (and in the same
1434
# order), no need to re-order
1436
hit_names = self._move_to_front_by_index(hit_indices)
1437
for sibling_idx in self._sibling_indices:
1438
sibling_idx._move_to_front_by_name(hit_names)
1440
def _move_to_front_by_index(self, hit_indices):
1441
"""Core logic for _move_to_front.
1443
Returns a list of names corresponding to the hit_indices param.
1445
indices_info = zip(self._index_names, self._indices)
1446
if 'index' in debug.debug_flags:
1447
trace.mutter('CombinedGraphIndex reordering: currently %r, '
1448
'promoting %r', indices_info, hit_indices)
1451
new_hit_indices = []
1454
for offset, (name, idx) in enumerate(indices_info):
1455
if idx in hit_indices:
1456
hit_names.append(name)
1457
new_hit_indices.append(idx)
1458
if len(new_hit_indices) == len(hit_indices):
1459
# We've found all of the hit entries, everything else is
1461
unhit_names.extend(self._index_names[offset+1:])
1462
unhit_indices.extend(self._indices[offset+1:])
1465
unhit_names.append(name)
1466
unhit_indices.append(idx)
1468
self._indices = new_hit_indices + unhit_indices
1469
self._index_names = hit_names + unhit_names
1470
if 'index' in debug.debug_flags:
1471
trace.mutter('CombinedGraphIndex reordered: %r', self._indices)
1474
def _move_to_front_by_name(self, hit_names):
1475
"""Moves indices named by 'hit_names' to front of the search order, as
1476
described in _move_to_front.
1478
# Translate names to index instances, and then call
1479
# _move_to_front_by_index.
1480
indices_info = zip(self._index_names, self._indices)
1482
for name, idx in indices_info:
1483
if name in hit_names:
1484
hit_indices.append(idx)
1485
self._move_to_front_by_index(hit_indices)
1487
def find_ancestry(self, keys, ref_list_num):
1488
"""Find the complete ancestry for the given set of keys.
1490
Note that this is a whole-ancestry request, so it should be used
1493
:param keys: An iterable of keys to look for
1494
:param ref_list_num: The reference list which references the parents
1496
:return: (parent_map, missing_keys)
1498
# XXX: make this call _move_to_front?
1499
missing_keys = set()
1501
keys_to_lookup = set(keys)
1503
while keys_to_lookup:
1504
# keys that *all* indexes claim are missing, stop searching them
1506
all_index_missing = None
1507
# print 'gen\tidx\tsub\tn_keys\tn_pmap\tn_miss'
1508
# print '%4d\t\t\t%4d\t%5d\t%5d' % (generation, len(keys_to_lookup),
1510
# len(missing_keys))
1511
for index_idx, index in enumerate(self._indices):
1512
# TODO: we should probably be doing something with
1513
# 'missing_keys' since we've already determined that
1514
# those revisions have not been found anywhere
1515
index_missing_keys = set()
1516
# Find all of the ancestry we can from this index
1517
# keep looking until the search_keys set is empty, which means
1518
# things we didn't find should be in index_missing_keys
1519
search_keys = keys_to_lookup
1521
# print ' \t%2d\t\t%4d\t%5d\t%5d' % (
1522
# index_idx, len(search_keys),
1523
# len(parent_map), len(index_missing_keys))
1526
# TODO: ref_list_num should really be a parameter, since
1527
# CombinedGraphIndex does not know what the ref lists
1529
search_keys = index._find_ancestors(search_keys,
1530
ref_list_num, parent_map, index_missing_keys)
1531
# print ' \t \t%2d\t%4d\t%5d\t%5d' % (
1532
# sub_generation, len(search_keys),
1533
# len(parent_map), len(index_missing_keys))
1534
# Now set whatever was missing to be searched in the next index
1535
keys_to_lookup = index_missing_keys
1536
if all_index_missing is None:
1537
all_index_missing = set(index_missing_keys)
1539
all_index_missing.intersection_update(index_missing_keys)
1540
if not keys_to_lookup:
1542
if all_index_missing is None:
1543
# There were no indexes, so all search keys are 'missing'
1544
missing_keys.update(keys_to_lookup)
1545
keys_to_lookup = None
1547
missing_keys.update(all_index_missing)
1548
keys_to_lookup.difference_update(all_index_missing)
1549
return parent_map, missing_keys
1216
for index in self._indices:
1217
for node in index.iter_entries_prefix(keys):
1218
if node[1] in seen_keys:
1220
seen_keys.add(node[1])
1551
1223
def key_count(self):
1552
1224
"""Return an estimate of the number of keys in this index.
1554
1226
For CombinedGraphIndex this is approximated by the sum of the keys of
1555
1227
the child indices. As child indices may have duplicate keys this can
1556
1228
have a maximum error of the number of child indices * largest number of
1557
1229
keys in any index.
1561
return sum((index.key_count() for index in self._indices), 0)
1562
except errors.NoSuchFile:
1563
self._reload_or_raise()
1565
missing_keys = _missing_keys_from_parent_map
1567
def _reload_or_raise(self):
1568
"""We just got a NoSuchFile exception.
1570
Try to reload the indices, if it fails, just raise the current
1573
if self._reload_func is None:
1575
exc_type, exc_value, exc_traceback = sys.exc_info()
1576
trace.mutter('Trying to reload after getting exception: %s',
1578
if not self._reload_func():
1579
# We tried to reload, but nothing changed, so we fail anyway
1580
trace.mutter('_reload_func indicated nothing has changed.'
1581
' Raising original exception.')
1582
raise exc_type, exc_value, exc_traceback
1584
def set_sibling_indices(self, sibling_combined_graph_indices):
1585
"""Set the CombinedGraphIndex objects to reorder after reordering self.
1587
self._sibling_indices = sibling_combined_graph_indices
1231
return sum((index.key_count() for index in self._indices), 0)
1589
1233
def validate(self):
1590
1234
"""Validate that everything in the index can be accessed."""
1593
for index in self._indices:
1596
except errors.NoSuchFile:
1597
self._reload_or_raise()
1235
for index in self._indices:
1600
1239
class InMemoryGraphIndex(GraphIndexBuilder):