70
69
class GraphIndexBuilder(object):
71
70
"""A builder that can build a GraphIndex.
73
The resulting graph has the structure::
72
The resulting graph has the structure:
75
_SIGNATURE OPTIONS NODES NEWLINE
76
_SIGNATURE := 'Bazaar Graph Index 1' NEWLINE
77
OPTIONS := 'node_ref_lists=' DIGITS NEWLINE
79
NODE := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
80
KEY := Not-whitespace-utf8
82
REFERENCES := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
83
REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
84
REFERENCE := DIGITS ; digits is the byte offset in the index of the
86
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
89
88
def __init__(self, reference_lists=0, key_elements=1):
185
184
:param value: The value associate with this key. Must not contain
186
185
newlines or null characters.
187
186
:return: (node_refs, absent_references)
189
* node_refs: basically a packed form of 'references' where all
191
* absent_references: reference keys that are not in self._nodes.
192
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.
195
193
as_st = StaticTuple.from_sequence
196
194
self._check_key(key)
389
382
suitable for production use. :XXX
392
def __init__(self, transport, name, size, unlimited_cache=False, offset=0):
385
def __init__(self, transport, name, size, unlimited_cache=False):
393
386
"""Open an index called name on transport.
395
388
:param transport: A bzrlib.transport.Transport.
451
441
# We already did this
453
443
if 'index' in debug.debug_flags:
454
trace.mutter('Reading entire index %s',
455
self._transport.abspath(self._name))
444
mutter('Reading entire index %s', self._transport.abspath(self._name))
456
445
if stream is None:
457
446
stream = self._transport.get(self._name)
458
if self._base_offset != 0:
459
# This is wasteful, but it is better than dealing with
460
# adjusting all the offsets, etc.
461
stream = StringIO(stream.read()[self._base_offset:])
462
447
self._read_prefix(stream)
463
448
self._expected_elements = 3 + self._key_length
1206
1190
self._buffer_all()
1209
base_offset = self._base_offset
1210
if base_offset != 0:
1211
# Rewrite the ranges for the offset
1212
readv_ranges = [(start+base_offset, size)
1213
for start, size in readv_ranges]
1214
1193
readv_data = self._transport.readv(self._name, readv_ranges, True,
1215
self._size + self._base_offset)
1217
1196
for offset, data in readv_data:
1218
offset -= base_offset
1219
1197
self._bytes_read += len(data)
1221
# transport.readv() expanded to extra data which isn't part of
1223
data = data[-offset:]
1225
1198
if offset == 0 and len(data) == self._size:
1226
1199
# We read the whole range, most likely because the
1227
1200
# Transport upcast our readv ranges into one long request
1256
1229
Queries against the combined index will be made against the first index,
1257
and then the second and so on. The order of indices can thus influence
1230
and then the second and so on. The order of index's can thus influence
1258
1231
performance significantly. For example, if one index is on local disk and a
1259
1232
second on a remote server, the local disk index should be before the other
1260
1233
in the index list.
1262
Also, queries tend to need results from the same indices as previous
1263
queries. So the indices will be reordered after every query to put the
1264
indices that had the result(s) of that query first (while otherwise
1265
preserving the relative ordering).
1268
1236
def __init__(self, indices, reload_func=None):
1276
1244
self._indices = indices
1277
1245
self._reload_func = reload_func
1278
# Sibling indices are other CombinedGraphIndex that we should call
1279
# _move_to_front_by_name on when we auto-reorder ourself.
1280
self._sibling_indices = []
1281
# A list of names that corresponds to the instances in self._indices,
1282
# so _index_names[0] is always the name for _indices[0], etc. Sibling
1283
# indices must all use the same set of names as each other.
1284
self._index_names = [None] * len(self._indices)
1286
1247
def __repr__(self):
1287
1248
return "%s(%s)" % (
1296
1257
def get_parent_map(self, keys):
1297
1258
"""See graph.StackedParentsProvider.get_parent_map"""
1298
1259
search_keys = set(keys)
1299
if _mod_revision.NULL_REVISION in search_keys:
1300
search_keys.discard(_mod_revision.NULL_REVISION)
1301
found_parents = {_mod_revision.NULL_REVISION:[]}
1260
if NULL_REVISION in search_keys:
1261
search_keys.discard(NULL_REVISION)
1262
found_parents = {NULL_REVISION:[]}
1303
1264
found_parents = {}
1304
1265
for index, key, value, refs in self.iter_entries(search_keys):
1305
1266
parents = refs[0]
1306
1267
if not parents:
1307
parents = (_mod_revision.NULL_REVISION,)
1268
parents = (NULL_REVISION,)
1308
1269
found_parents[key] = parents
1309
1270
return found_parents
1311
1272
has_key = _has_key_from_parent_map
1313
def insert_index(self, pos, index, name=None):
1274
def insert_index(self, pos, index):
1314
1275
"""Insert a new index in the list of indices to query.
1316
1277
:param pos: The position to insert the index.
1317
1278
:param index: The index to insert.
1318
:param name: a name for this index, e.g. a pack name. These names can
1319
be used to reflect index reorderings to related CombinedGraphIndex
1320
instances that use the same names. (see set_sibling_indices)
1322
1280
self._indices.insert(pos, index)
1323
self._index_names.insert(pos, name)
1325
1282
def iter_all_entries(self):
1326
1283
"""Iterate over all keys within the index
1351
1308
value and are only reported once.
1353
1310
:param keys: An iterable providing the keys to be retrieved.
1354
:return: An iterable of (index, key, reference_lists, value). There is
1355
no defined order for the result iteration - it will be in the most
1311
:return: An iterable of (index, key, reference_lists, value). There is no
1312
defined order for the result iteration - it will be in the most
1356
1313
efficient order for the index.
1358
1315
keys = set(keys)
1362
1318
for index in self._indices:
1366
1321
for node in index.iter_entries(keys):
1367
1322
keys.remove(node[1])
1371
hit_indices.append(index)
1373
1325
except errors.NoSuchFile:
1374
1326
self._reload_or_raise()
1375
self._move_to_front(hit_indices)
1377
1328
def iter_entries_prefix(self, keys):
1378
1329
"""Iterate over keys within the index using prefix matching.
1400
1351
seen_keys = set()
1404
1354
for index in self._indices:
1406
1355
for node in index.iter_entries_prefix(keys):
1407
1356
if node[1] in seen_keys:
1409
1358
seen_keys.add(node[1])
1413
hit_indices.append(index)
1415
1361
except errors.NoSuchFile:
1416
1362
self._reload_or_raise()
1417
self._move_to_front(hit_indices)
1419
def _move_to_front(self, hit_indices):
1420
"""Rearrange self._indices so that hit_indices are first.
1422
Order is maintained as much as possible, e.g. the first unhit index
1423
will be the first index in _indices after the hit_indices, and the
1424
hit_indices will be present in exactly the order they are passed to
1427
_move_to_front propagates to all objects in self._sibling_indices by
1428
calling _move_to_front_by_name.
1430
if self._indices[:len(hit_indices)] == hit_indices:
1431
# The 'hit_indices' are already at the front (and in the same
1432
# order), no need to re-order
1434
hit_names = self._move_to_front_by_index(hit_indices)
1435
for sibling_idx in self._sibling_indices:
1436
sibling_idx._move_to_front_by_name(hit_names)
1438
def _move_to_front_by_index(self, hit_indices):
1439
"""Core logic for _move_to_front.
1441
Returns a list of names corresponding to the hit_indices param.
1443
indices_info = zip(self._index_names, self._indices)
1444
if 'index' in debug.debug_flags:
1445
trace.mutter('CombinedGraphIndex reordering: currently %r, '
1446
'promoting %r', indices_info, hit_indices)
1449
new_hit_indices = []
1452
for offset, (name, idx) in enumerate(indices_info):
1453
if idx in hit_indices:
1454
hit_names.append(name)
1455
new_hit_indices.append(idx)
1456
if len(new_hit_indices) == len(hit_indices):
1457
# We've found all of the hit entries, everything else is
1459
unhit_names.extend(self._index_names[offset+1:])
1460
unhit_indices.extend(self._indices[offset+1:])
1463
unhit_names.append(name)
1464
unhit_indices.append(idx)
1466
self._indices = new_hit_indices + unhit_indices
1467
self._index_names = hit_names + unhit_names
1468
if 'index' in debug.debug_flags:
1469
trace.mutter('CombinedGraphIndex reordered: %r', self._indices)
1472
def _move_to_front_by_name(self, hit_names):
1473
"""Moves indices named by 'hit_names' to front of the search order, as
1474
described in _move_to_front.
1476
# Translate names to index instances, and then call
1477
# _move_to_front_by_index.
1478
indices_info = zip(self._index_names, self._indices)
1480
for name, idx in indices_info:
1481
if name in hit_names:
1482
hit_indices.append(idx)
1483
self._move_to_front_by_index(hit_indices)
1485
1364
def find_ancestry(self, keys, ref_list_num):
1486
1365
"""Find the complete ancestry for the given set of keys.