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):
115
94
if not element or _whitespace_re.search(element) is not None:
116
95
raise errors.BadIndexKey(element)
118
def _external_references(self):
119
"""Return references that are not present in this index.
123
# TODO: JAM 2008-11-21 This makes an assumption about how the reference
124
# lists are used. It is currently correct for pack-0.92 through
125
# 1.9, which use the node references (3rd column) second
126
# reference list as the compression parent. Perhaps this should
127
# be moved into something higher up the stack, since it
128
# makes assumptions about how the index is used.
129
if self.reference_lists > 1:
130
for node in self.iter_all_entries():
132
refs.update(node[3][1])
135
# If reference_lists == 0 there can be no external references, and
136
# if reference_lists == 1, then there isn't a place to store the
140
def _get_nodes_by_key(self):
141
if self._nodes_by_key is None:
143
if self.reference_lists:
144
for key, (absent, references, value) in self._nodes.iteritems():
147
key_dict = nodes_by_key
148
for subkey in key[:-1]:
149
key_dict = key_dict.setdefault(subkey, {})
150
key_dict[key[-1]] = key, value, references
152
for key, (absent, references, value) in self._nodes.iteritems():
155
key_dict = nodes_by_key
156
for subkey in key[:-1]:
157
key_dict = key_dict.setdefault(subkey, {})
158
key_dict[key[-1]] = key, value
159
self._nodes_by_key = nodes_by_key
160
return self._nodes_by_key
162
def _update_nodes_by_key(self, key, value, node_refs):
163
"""Update the _nodes_by_key dict with a new key.
165
For a key of (foo, bar, baz) create
166
_nodes_by_key[foo][bar][baz] = key_value
168
if self._nodes_by_key is None:
170
key_dict = self._nodes_by_key
171
if self.reference_lists:
172
key_value = StaticTuple(key, value, node_refs)
174
key_value = StaticTuple(key, value)
175
for subkey in key[:-1]:
176
key_dict = key_dict.setdefault(subkey, {})
177
key_dict[key[-1]] = key_value
179
def _check_key_ref_value(self, key, references, value):
180
"""Check that 'key' and 'references' are all valid.
182
:param key: A key tuple. Must conform to the key interface (be a tuple,
183
be of the right length, not have any whitespace or nulls in any key
185
:param references: An iterable of reference lists. Something like
186
[[(ref, key)], [(ref, key), (other, key)]]
187
:param value: The value associate with this key. Must not contain
188
newlines or null characters.
189
:return: (node_refs, absent_references)
191
* node_refs: basically a packed form of 'references' where all
193
* absent_references: reference keys that are not in self._nodes.
194
This may contain duplicates if the same key is referenced in
197
as_st = StaticTuple.from_sequence
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.
198
108
self._check_key(key)
199
109
if _newline_null_re.search(value) is not None:
200
110
raise errors.BadIndexValue(value)
201
111
if len(references) != self.reference_lists:
202
112
raise errors.BadIndexValue(references)
204
absent_references = []
205
114
for reference_list in references:
206
115
for reference in reference_list:
207
# If reference *is* in self._nodes, then we know it has already
116
self._check_key(reference)
209
117
if reference not in self._nodes:
210
self._check_key(reference)
211
absent_references.append(reference)
212
reference_list = as_st([as_st(ref).intern()
213
for ref in reference_list])
214
node_refs.append(reference_list)
215
return as_st(node_refs), absent_references
217
def add_node(self, key, value, references=()):
218
"""Add a node to the index.
220
:param key: The key. keys are non-empty tuples containing
221
as many whitespace-free utf8 bytestrings as the key length
222
defined for this index.
223
:param references: An iterable of iterables of keys. Each is a
224
reference to another key.
225
:param value: The value to associate with the key. It may be any
226
bytes as long as it does not contain \\0 or \\n.
229
absent_references) = self._check_key_ref_value(key, references, value)
230
if key in self._nodes and self._nodes[key][0] != 'a':
118
self._nodes[reference] = ('a', (), '')
119
node_refs.append(tuple(reference_list))
120
if key in self._nodes and self._nodes[key][0] == '':
231
121
raise errors.BadIndexDuplicateKey(key, self)
232
for reference in absent_references:
233
# There may be duplicates, but I don't think it is worth worrying
235
self._nodes[reference] = ('a', (), '')
236
self._absent_keys.update(absent_references)
237
self._absent_keys.discard(key)
238
self._nodes[key] = ('', node_refs, value)
239
if self._nodes_by_key is not None and self._key_length > 1:
240
self._update_nodes_by_key(key, value, node_refs)
242
def clear_cache(self):
243
"""See GraphIndex.clear_cache()
245
This is a no-op, but we need the api to conform to a generic 'Index'
122
self._nodes[key] = ('', tuple(node_refs), value)
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
249
138
def finish(self):
252
:returns: cStringIO holding the full context of the index as it
253
should be written to disk.
255
139
lines = [_SIGNATURE]
256
140
lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
257
141
lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
258
key_count = len(self._nodes) - len(self._absent_keys)
259
lines.append(_OPTION_LEN + str(key_count) + '\n')
142
lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
260
143
prefix_length = sum(len(x) for x in lines)
261
144
# references are byte offsets. To avoid having to do nasty
262
# polynomial work to resolve offsets (references to later in the
145
# polynomial work to resolve offsets (references to later in the
263
146
# file cannot be determined until all the inbetween references have
264
147
# been calculated too) we pad the offsets with 0's to make them be
265
148
# of consistent length. Using binary offsets would break the trivial
338
221
(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
225
class GraphIndex(object):
377
226
"""An index for data with embedded graphs.
379
228
The index maps keys to a list of key reference lists, and a value.
380
229
Each node has the same number of key reference lists. Each key reference
381
230
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
231
terminated string without any newlines. The storage of the index is
383
232
hidden in the interface: keys and key references are always tuples of
384
233
bytestrings, never the internal representation (e.g. dictionary offsets).
486
325
node_value = value
487
326
self._nodes[key] = node_value
327
if self._key_length > 1:
328
subkey = list(reversed(key[:-1]))
329
key_dict = self._nodes_by_key
330
if self.node_ref_lists:
331
key_value = key, node_value[0], node_value[1]
333
key_value = key, node_value
334
# possibly should do this on-demand, but it seems likely it is
336
# For a key of (foo, bar, baz) create
337
# _nodes_by_key[foo][bar][baz] = key_value
338
for subkey in key[:-1]:
339
key_dict = key_dict.setdefault(subkey, {})
340
key_dict[key[-1]] = key_value
488
341
# cache the keys for quick set intersections
342
self._keys = set(self._nodes)
489
343
if trailers != 1:
490
344
# there must be one line - the empty trailer line.
491
345
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
347
def iter_all_entries(self):
534
348
"""Iterate over all keys within the index.
1252
1034
class CombinedGraphIndex(object):
1253
1035
"""A GraphIndex made up from smaller GraphIndices.
1255
1037
The backing indices must implement GraphIndex, and are presumed to be
1258
1040
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
1041
and then the second and so on. The order of index's can thus influence
1260
1042
performance significantly. For example, if one index is on local disk and a
1261
1043
second on a remote server, the local disk index should be before the other
1262
1044
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):
1047
def __init__(self, indices):
1271
1048
"""Create a CombinedGraphIndex backed by indices.
1273
1050
: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
1052
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
1054
def __repr__(self):
1289
1055
return "%s(%s)" % (
1290
1056
self.__class__.__name__,
1291
1057
', '.join(map(repr, self._indices)))
1293
def clear_cache(self):
1294
"""See GraphIndex.clear_cache()"""
1295
for index in self._indices:
1059
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
1060
def get_parents(self, revision_ids):
1061
"""See graph._StackedParentsProvider.get_parents.
1063
This implementation thunks the graph.Graph.get_parents api across to
1066
:param revision_ids: An iterable of graph keys for this graph.
1067
:return: A list of parent details for each key in revision_ids.
1068
Each parent details will be one of:
1069
* None when the key was missing
1070
* (NULL_REVISION,) when the key has no parents.
1071
* (parent_key, parent_key...) otherwise.
1073
parent_map = self.get_parent_map(revision_ids)
1074
return [parent_map.get(r, None) for r in revision_ids]
1298
1076
def get_parent_map(self, keys):
1299
"""See graph.StackedParentsProvider.get_parent_map"""
1077
"""See graph._StackedParentsProvider.get_parent_map"""
1300
1078
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:[]}
1079
if NULL_REVISION in search_keys:
1080
search_keys.discard(NULL_REVISION)
1081
found_parents = {NULL_REVISION:[]}
1305
1083
found_parents = {}
1306
1084
for index, key, value, refs in self.iter_entries(search_keys):
1307
1085
parents = refs[0]
1308
1086
if not parents:
1309
parents = (_mod_revision.NULL_REVISION,)
1087
parents = (NULL_REVISION,)
1310
1088
found_parents[key] = parents
1311
1089
return found_parents
1313
has_key = _has_key_from_parent_map
1315
def insert_index(self, pos, index, name=None):
1091
def insert_index(self, pos, index):
1316
1092
"""Insert a new index in the list of indices to query.
1318
1094
:param pos: The position to insert the index.
1319
1095
: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
1097
self._indices.insert(pos, index)
1325
self._index_names.insert(pos, name)
1327
1099
def iter_all_entries(self):
1328
1100
"""Iterate over all keys within the index
1402
1158
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
1159
for index in self._indices:
1160
for node in index.iter_entries_prefix(keys):
1161
if node[1] in seen_keys:
1163
seen_keys.add(node[1])
1551
1166
def key_count(self):
1552
1167
"""Return an estimate of the number of keys in this index.
1554
1169
For CombinedGraphIndex this is approximated by the sum of the keys of
1555
1170
the child indices. As child indices may have duplicate keys this can
1556
1171
have a maximum error of the number of child indices * largest number of
1557
1172
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
1174
return sum((index.key_count() for index in self._indices), 0)
1589
1176
def validate(self):
1590
1177
"""Validate that everything in the index can be accessed."""
1593
for index in self._indices:
1596
except errors.NoSuchFile:
1597
self._reload_or_raise()
1178
for index in self._indices:
1600
1182
class InMemoryGraphIndex(GraphIndexBuilder):
added
removed
bzrlib/index.py
