204
class _MPDiffGenerator(object):
205
"""Pull out the functionality for generating mp_diffs."""
207
def __init__(self, vf, keys):
209
# This is the order the keys were requested in
210
self.ordered_keys = tuple(keys)
211
# keys + their parents, what we need to compute the diffs
212
self.needed_keys = ()
213
# Map from key: mp_diff
215
# Map from key: parents_needed (may have ghosts)
217
# Parents that aren't present
218
self.ghost_parents = ()
219
# Map from parent_key => number of children for this text
221
# Content chunks that are cached while we still need them
224
def _find_needed_keys(self):
225
"""Find the set of keys we need to request.
227
This includes all the original keys passed in, and the non-ghost
228
parents of those keys.
230
:return: (needed_keys, refcounts)
231
needed_keys is the set of all texts we need to extract
232
refcounts is a dict of {key: num_children} letting us know when we
233
no longer need to cache a given parent text
235
# All the keys and their parents
236
needed_keys = set(self.ordered_keys)
237
parent_map = self.vf.get_parent_map(needed_keys)
238
self.parent_map = parent_map
239
# TODO: Should we be using a different construct here? I think this
240
# uses difference_update internally, and we expect the result to
242
missing_keys = needed_keys.difference(parent_map)
244
raise errors.RevisionNotPresent(list(missing_keys)[0], self.vf)
245
# Parents that might be missing. They are allowed to be ghosts, but we
246
# should check for them
248
setdefault = refcounts.setdefault
250
for child_key, parent_keys in parent_map.iteritems():
252
# parent_keys may be None if a given VersionedFile claims to
253
# not support graph operations.
255
just_parents.update(parent_keys)
256
needed_keys.update(parent_keys)
257
for p in parent_keys:
258
refcounts[p] = setdefault(p, 0) + 1
259
just_parents.difference_update(parent_map)
260
# Remove any parents that are actually ghosts from the needed set
261
self.present_parents = set(self.vf.get_parent_map(just_parents))
262
self.ghost_parents = just_parents.difference(self.present_parents)
263
needed_keys.difference_update(self.ghost_parents)
264
self.needed_keys = needed_keys
265
self.refcounts = refcounts
266
return needed_keys, refcounts
268
def _compute_diff(self, key, parent_lines, lines):
269
"""Compute a single mp_diff, and store it in self._diffs"""
270
if len(parent_lines) > 0:
271
# XXX: _extract_blocks is not usefully defined anywhere...
272
# It was meant to extract the left-parent diff without
273
# having to recompute it for Knit content (pack-0.92,
274
# etc). That seems to have regressed somewhere
275
left_parent_blocks = self.vf._extract_blocks(key,
276
parent_lines[0], lines)
278
left_parent_blocks = None
279
diff = multiparent.MultiParent.from_lines(lines,
280
parent_lines, left_parent_blocks)
281
self.diffs[key] = diff
283
def _process_one_record(self, key, this_chunks):
285
if key in self.parent_map:
286
# This record should be ready to diff, since we requested
287
# content in 'topological' order
288
parent_keys = self.parent_map.pop(key)
289
# If a VersionedFile claims 'no-graph' support, then it may return
290
# None for any parent request, so we replace it with an empty tuple
291
if parent_keys is None:
294
for p in parent_keys:
295
# Alternatively we could check p not in self.needed_keys, but
296
# ghost_parents should be tiny versus huge
297
if p in self.ghost_parents:
299
refcount = self.refcounts[p]
300
if refcount == 1: # Last child reference
301
self.refcounts.pop(p)
302
parent_chunks = self.chunks.pop(p)
304
self.refcounts[p] = refcount - 1
305
parent_chunks = self.chunks[p]
306
p_lines = osutils.chunks_to_lines(parent_chunks)
307
# TODO: Should we cache the line form? We did the
308
# computation to get it, but storing it this way will
309
# be less memory efficient...
310
parent_lines.append(p_lines)
312
lines = osutils.chunks_to_lines(this_chunks)
313
# Since we needed the lines, we'll go ahead and cache them this way
315
self._compute_diff(key, parent_lines, lines)
317
# Is this content required for any more children?
318
if key in self.refcounts:
319
self.chunks[key] = this_chunks
321
def _extract_diffs(self):
322
needed_keys, refcounts = self._find_needed_keys()
323
for record in self.vf.get_record_stream(needed_keys,
324
'topological', True):
325
if record.storage_kind == 'absent':
326
raise errors.RevisionNotPresent(record.key, self.vf)
327
self._process_one_record(record.key,
328
record.get_bytes_as('chunked'))
330
def compute_diffs(self):
331
self._extract_diffs()
332
dpop = self.diffs.pop
333
return [dpop(k) for k in self.ordered_keys]
209
336
class VersionedFile(object):
210
337
"""Versioned text file storage.
1048
1183
def make_mpdiffs(self, keys):
1049
1184
"""Create multiparent diffs for specified keys."""
1050
keys_order = tuple(keys)
1051
keys = frozenset(keys)
1052
knit_keys = set(keys)
1053
parent_map = self.get_parent_map(keys)
1054
for parent_keys in parent_map.itervalues():
1056
knit_keys.update(parent_keys)
1057
missing_keys = keys - set(parent_map)
1059
raise errors.RevisionNotPresent(list(missing_keys)[0], self)
1060
# We need to filter out ghosts, because we can't diff against them.
1061
maybe_ghosts = knit_keys - keys
1062
ghosts = maybe_ghosts - set(self.get_parent_map(maybe_ghosts))
1063
knit_keys.difference_update(ghosts)
1065
chunks_to_lines = osutils.chunks_to_lines
1066
for record in self.get_record_stream(knit_keys, 'topological', True):
1067
lines[record.key] = chunks_to_lines(record.get_bytes_as('chunked'))
1068
# line_block_dict = {}
1069
# for parent, blocks in record.extract_line_blocks():
1070
# line_blocks[parent] = blocks
1071
# line_blocks[record.key] = line_block_dict
1073
for key in keys_order:
1075
parents = parent_map[key] or []
1076
# Note that filtering knit_keys can lead to a parent difference
1077
# between the creation and the application of the mpdiff.
1078
parent_lines = [lines[p] for p in parents if p in knit_keys]
1079
if len(parent_lines) > 0:
1080
left_parent_blocks = self._extract_blocks(key, parent_lines[0],
1083
left_parent_blocks = None
1084
diffs.append(multiparent.MultiParent.from_lines(target,
1085
parent_lines, left_parent_blocks))
1185
generator = _MPDiffGenerator(self, keys)
1186
return generator.compute_diffs()
1188
def get_annotator(self):
1189
return annotate.Annotator(self)
1088
1191
missing_keys = index._missing_keys_from_parent_map
1090
1193
def _extract_blocks(self, version_id, source, target):
1196
def _transitive_fallbacks(self):
1197
"""Return the whole stack of fallback versionedfiles.
1199
This VersionedFiles may have a list of fallbacks, but it doesn't
1200
necessarily know about the whole stack going down, and it can't know
1201
at open time because they may change after the objects are opened.
1204
for a_vfs in self._immediate_fallback_vfs:
1205
all_fallbacks.append(a_vfs)
1206
all_fallbacks.extend(a_vfs._transitive_fallbacks())
1207
return all_fallbacks
1094
1210
class ThunkedVersionedFiles(VersionedFiles):
1095
1211
"""Storage for many versioned files thunked onto a 'VersionedFile' class.
1427
class VersionedFilesWithFallbacks(VersionedFiles):
1429
def without_fallbacks(self):
1430
"""Return a clone of this object without any fallbacks configured."""
1431
raise NotImplementedError(self.without_fallbacks)
1433
def add_fallback_versioned_files(self, a_versioned_files):
1434
"""Add a source of texts for texts not present in this knit.
1436
:param a_versioned_files: A VersionedFiles object.
1438
raise NotImplementedError(self.add_fallback_versioned_files)
1440
def get_known_graph_ancestry(self, keys):
1441
"""Get a KnownGraph instance with the ancestry of keys."""
1442
parent_map, missing_keys = self._index.find_ancestry(keys)
1443
for fallback in self._transitive_fallbacks():
1444
if not missing_keys:
1446
(f_parent_map, f_missing_keys) = fallback._index.find_ancestry(
1448
parent_map.update(f_parent_map)
1449
missing_keys = f_missing_keys
1450
kg = _mod_graph.KnownGraph(parent_map)
1314
1454
class _PlanMergeVersionedFile(VersionedFiles):
1315
1455
"""A VersionedFile for uncommitted and committed texts.
1768
class NoDupeAddLinesDecorator(object):
1769
"""Decorator for a VersionedFiles that skips doing an add_lines if the key
1773
def __init__(self, store):
1776
def add_lines(self, key, parents, lines, parent_texts=None,
1777
left_matching_blocks=None, nostore_sha=None, random_id=False,
1778
check_content=True):
1779
"""See VersionedFiles.add_lines.
1781
This implementation may return None as the third element of the return
1782
value when the original store wouldn't.
1785
raise NotImplementedError(
1786
"NoDupeAddLinesDecorator.add_lines does not implement the "
1787
"nostore_sha behaviour.")
1789
sha1 = osutils.sha_strings(lines)
1790
key = ("sha1:" + sha1,)
1793
if key in self._store.get_parent_map([key]):
1794
# This key has already been inserted, so don't do it again.
1796
sha1 = osutils.sha_strings(lines)
1797
return sha1, sum(map(len, lines)), None
1798
return self._store.add_lines(key, parents, lines,
1799
parent_texts=parent_texts,
1800
left_matching_blocks=left_matching_blocks,
1801
nostore_sha=nostore_sha, random_id=random_id,
1802
check_content=check_content)
1804
def __getattr__(self, name):
1805
return getattr(self._store, name)
1627
1808
def network_bytes_to_kind_and_offset(network_bytes):
1628
1809
"""Strip of a record kind from the front of network_bytes.
1720
1901
for prefix in sorted(per_prefix_map):
1721
1902
present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
1722
1903
return present_keys
1906
class _KeyRefs(object):
1908
def __init__(self, track_new_keys=False):
1909
# dict mapping 'key' to 'set of keys referring to that key'
1912
# set remembering all new keys
1913
self.new_keys = set()
1915
self.new_keys = None
1921
self.new_keys.clear()
1923
def add_references(self, key, refs):
1924
# Record the new references
1925
for referenced in refs:
1927
needed_by = self.refs[referenced]
1929
needed_by = self.refs[referenced] = set()
1931
# Discard references satisfied by the new key
1934
def get_new_keys(self):
1935
return self.new_keys
1937
def get_unsatisfied_refs(self):
1938
return self.refs.iterkeys()
1940
def _satisfy_refs_for_key(self, key):
1944
# No keys depended on this key. That's ok.
1947
def add_key(self, key):
1948
# satisfy refs for key, and remember that we've seen this key.
1949
self._satisfy_refs_for_key(key)
1950
if self.new_keys is not None:
1951
self.new_keys.add(key)
1953
def satisfy_refs_for_keys(self, keys):
1955
self._satisfy_refs_for_key(key)
1957
def get_referrers(self):
1959
for referrers in self.refs.itervalues():
1960
result.update(referrers)
added
removed
bzrlib/versionedfile.py
