201
class _MPDiffGenerator(object):
202
"""Pull out the functionality for generating mp_diffs."""
204
def __init__(self, vf, keys):
206
# This is the order the keys were requested in
207
self.ordered_keys = tuple(keys)
208
# keys + their parents, what we need to compute the diffs
209
self.needed_keys = ()
210
# Map from key: mp_diff
212
# Map from key: parents_needed (may have ghosts)
214
# Parents that aren't present
215
self.ghost_parents = ()
216
# Map from parent_key => number of children for this text
218
# Content chunks that are cached while we still need them
221
def _find_needed_keys(self):
222
"""Find the set of keys we need to request.
224
This includes all the original keys passed in, and the non-ghost
225
parents of those keys.
227
:return: (needed_keys, refcounts)
228
needed_keys is the set of all texts we need to extract
229
refcounts is a dict of {key: num_children} letting us know when we
230
no longer need to cache a given parent text
232
# All the keys and their parents
233
needed_keys = set(self.ordered_keys)
234
parent_map = self.vf.get_parent_map(needed_keys)
235
self.parent_map = parent_map
236
# TODO: Should we be using a different construct here? I think this
237
# uses difference_update internally, and we expect the result to
239
missing_keys = needed_keys.difference(parent_map)
241
raise errors.RevisionNotPresent(list(missing_keys)[0], self.vf)
242
# Parents that might be missing. They are allowed to be ghosts, but we
243
# should check for them
245
setdefault = refcounts.setdefault
247
for child_key, parent_keys in parent_map.iteritems():
249
# parent_keys may be None if a given VersionedFile claims to
250
# not support graph operations.
252
just_parents.update(parent_keys)
253
needed_keys.update(parent_keys)
254
for p in parent_keys:
255
refcounts[p] = setdefault(p, 0) + 1
256
just_parents.difference_update(parent_map)
257
# Remove any parents that are actually ghosts from the needed set
258
self.present_parents = set(self.vf.get_parent_map(just_parents))
259
self.ghost_parents = just_parents.difference(self.present_parents)
260
needed_keys.difference_update(self.ghost_parents)
261
self.needed_keys = needed_keys
262
self.refcounts = refcounts
263
return needed_keys, refcounts
265
def _compute_diff(self, key, parent_lines, lines):
266
"""Compute a single mp_diff, and store it in self._diffs"""
267
if len(parent_lines) > 0:
268
# XXX: _extract_blocks is not usefully defined anywhere...
269
# It was meant to extract the left-parent diff without
270
# having to recompute it for Knit content (pack-0.92,
271
# etc). That seems to have regressed somewhere
272
left_parent_blocks = self.vf._extract_blocks(key,
273
parent_lines[0], lines)
275
left_parent_blocks = None
276
diff = multiparent.MultiParent.from_lines(lines,
277
parent_lines, left_parent_blocks)
278
self.diffs[key] = diff
280
def _process_one_record(self, key, this_chunks):
282
if key in self.parent_map:
283
# This record should be ready to diff, since we requested
284
# content in 'topological' order
285
parent_keys = self.parent_map.pop(key)
286
# If a VersionedFile claims 'no-graph' support, then it may return
287
# None for any parent request, so we replace it with an empty tuple
288
if parent_keys is None:
291
for p in parent_keys:
292
# Alternatively we could check p not in self.needed_keys, but
293
# ghost_parents should be tiny versus huge
294
if p in self.ghost_parents:
296
refcount = self.refcounts[p]
297
if refcount == 1: # Last child reference
298
self.refcounts.pop(p)
299
parent_chunks = self.chunks.pop(p)
301
self.refcounts[p] = refcount - 1
302
parent_chunks = self.chunks[p]
303
p_lines = osutils.chunks_to_lines(parent_chunks)
304
# TODO: Should we cache the line form? We did the
305
# computation to get it, but storing it this way will
306
# be less memory efficient...
307
parent_lines.append(p_lines)
309
lines = osutils.chunks_to_lines(this_chunks)
310
# Since we needed the lines, we'll go ahead and cache them this way
312
self._compute_diff(key, parent_lines, lines)
314
# Is this content required for any more children?
315
if key in self.refcounts:
316
self.chunks[key] = this_chunks
318
def _extract_diffs(self):
319
needed_keys, refcounts = self._find_needed_keys()
320
for record in self.vf.get_record_stream(needed_keys,
321
'topological', True):
322
if record.storage_kind == 'absent':
323
raise errors.RevisionNotPresent(record.key, self.vf)
324
self._process_one_record(record.key,
325
record.get_bytes_as('chunked'))
327
def compute_diffs(self):
328
self._extract_diffs()
329
dpop = self.diffs.pop
330
return [dpop(k) for k in self.ordered_keys]
209
333
class VersionedFile(object):
210
334
"""Versioned text file storage.
1048
1180
def make_mpdiffs(self, keys):
1049
1181
"""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))
1182
generator = _MPDiffGenerator(self, keys)
1183
return generator.compute_diffs()
1185
def get_annotator(self):
1186
return annotate.Annotator(self)
1088
1188
missing_keys = index._missing_keys_from_parent_map
1090
1190
def _extract_blocks(self, version_id, source, target):
1193
def _transitive_fallbacks(self):
1194
"""Return the whole stack of fallback versionedfiles.
1196
This VersionedFiles may have a list of fallbacks, but it doesn't
1197
necessarily know about the whole stack going down, and it can't know
1198
at open time because they may change after the objects are opened.
1201
for a_vfs in self._immediate_fallback_vfs:
1202
all_fallbacks.append(a_vfs)
1203
all_fallbacks.extend(a_vfs._transitive_fallbacks())
1204
return all_fallbacks
1094
1207
class ThunkedVersionedFiles(VersionedFiles):
1095
1208
"""Storage for many versioned files thunked onto a 'VersionedFile' class.
1424
class VersionedFilesWithFallbacks(VersionedFiles):
1426
def without_fallbacks(self):
1427
"""Return a clone of this object without any fallbacks configured."""
1428
raise NotImplementedError(self.without_fallbacks)
1430
def add_fallback_versioned_files(self, a_versioned_files):
1431
"""Add a source of texts for texts not present in this knit.
1433
:param a_versioned_files: A VersionedFiles object.
1435
raise NotImplementedError(self.add_fallback_versioned_files)
1437
def get_known_graph_ancestry(self, keys):
1438
"""Get a KnownGraph instance with the ancestry of keys."""
1439
parent_map, missing_keys = self._index.find_ancestry(keys)
1440
for fallback in self._transitive_fallbacks():
1441
if not missing_keys:
1443
(f_parent_map, f_missing_keys) = fallback._index.find_ancestry(
1445
parent_map.update(f_parent_map)
1446
missing_keys = f_missing_keys
1447
kg = _mod_graph.KnownGraph(parent_map)
1314
1451
class _PlanMergeVersionedFile(VersionedFiles):
1315
1452
"""A VersionedFile for uncommitted and committed texts.
1765
class NoDupeAddLinesDecorator(object):
1766
"""Decorator for a VersionedFiles that skips doing an add_lines if the key
1770
def __init__(self, store):
1773
def add_lines(self, key, parents, lines, parent_texts=None,
1774
left_matching_blocks=None, nostore_sha=None, random_id=False,
1775
check_content=True):
1776
"""See VersionedFiles.add_lines.
1778
This implementation may return None as the third element of the return
1779
value when the original store wouldn't.
1782
raise NotImplementedError(
1783
"NoDupeAddLinesDecorator.add_lines does not implement the "
1784
"nostore_sha behaviour.")
1786
sha1 = osutils.sha_strings(lines)
1787
key = ("sha1:" + sha1,)
1790
if key in self._store.get_parent_map([key]):
1791
# This key has already been inserted, so don't do it again.
1793
sha1 = osutils.sha_strings(lines)
1794
return sha1, sum(map(len, lines)), None
1795
return self._store.add_lines(key, parents, lines,
1796
parent_texts=parent_texts,
1797
left_matching_blocks=left_matching_blocks,
1798
nostore_sha=nostore_sha, random_id=random_id,
1799
check_content=check_content)
1801
def __getattr__(self, name):
1802
return getattr(self._store, name)
1627
1805
def network_bytes_to_kind_and_offset(network_bytes):
1628
1806
"""Strip of a record kind from the front of network_bytes.
1720
1898
for prefix in sorted(per_prefix_map):
1721
1899
present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
1722
1900
return present_keys
1903
class _KeyRefs(object):
1905
def __init__(self, track_new_keys=False):
1906
# dict mapping 'key' to 'set of keys referring to that key'
1909
# set remembering all new keys
1910
self.new_keys = set()
1912
self.new_keys = None
1918
self.new_keys.clear()
1920
def add_references(self, key, refs):
1921
# Record the new references
1922
for referenced in refs:
1924
needed_by = self.refs[referenced]
1926
needed_by = self.refs[referenced] = set()
1928
# Discard references satisfied by the new key
1931
def get_new_keys(self):
1932
return self.new_keys
1934
def get_unsatisfied_refs(self):
1935
return self.refs.iterkeys()
1937
def _satisfy_refs_for_key(self, key):
1941
# No keys depended on this key. That's ok.
1944
def add_key(self, key):
1945
# satisfy refs for key, and remember that we've seen this key.
1946
self._satisfy_refs_for_key(key)
1947
if self.new_keys is not None:
1948
self.new_keys.add(key)
1950
def satisfy_refs_for_keys(self, keys):
1952
self._satisfy_refs_for_key(key)
1954
def get_referrers(self):
1956
for referrers in self.refs.itervalues():
1957
result.update(referrers)
added
removed
bzrlib/versionedfile.py
