45
from bzrlib.graph import DictParentsProvider, Graph, StackedParentsProvider
46
from bzrlib.transport.memory import MemoryTransport
48
from bzrlib.registry import Registry
49
from bzrlib.symbol_versioning import *
50
from bzrlib.textmerge import TextMerge
51
from bzrlib import bencode
44
from .registry import Registry
49
from .textmerge import TextMerge
54
52
adapter_registry = Registry()
55
adapter_registry.register_lazy(('knit-delta-gz', 'fulltext'), 'bzrlib.knit',
53
adapter_registry.register_lazy(('knit-delta-gz', 'fulltext'), 'breezy.knit',
56
54
'DeltaPlainToFullText')
57
adapter_registry.register_lazy(('knit-ft-gz', 'fulltext'), 'bzrlib.knit',
55
adapter_registry.register_lazy(('knit-ft-gz', 'fulltext'), 'breezy.knit',
58
56
'FTPlainToFullText')
59
57
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'knit-delta-gz'),
60
'bzrlib.knit', 'DeltaAnnotatedToUnannotated')
58
'breezy.knit', 'DeltaAnnotatedToUnannotated')
61
59
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'fulltext'),
62
'bzrlib.knit', 'DeltaAnnotatedToFullText')
60
'breezy.knit', 'DeltaAnnotatedToFullText')
63
61
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'knit-ft-gz'),
64
'bzrlib.knit', 'FTAnnotatedToUnannotated')
62
'breezy.knit', 'FTAnnotatedToUnannotated')
65
63
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'fulltext'),
66
'bzrlib.knit', 'FTAnnotatedToFullText')
64
'breezy.knit', 'FTAnnotatedToFullText')
67
65
# adapter_registry.register_lazy(('knit-annotated-ft-gz', 'chunked'),
68
# 'bzrlib.knit', 'FTAnnotatedToChunked')
66
# 'breezy.knit', 'FTAnnotatedToChunked')
71
69
class ContentFactory(object):
207
class _MPDiffGenerator(object):
208
"""Pull out the functionality for generating mp_diffs."""
210
def __init__(self, vf, keys):
212
# This is the order the keys were requested in
213
self.ordered_keys = tuple(keys)
214
# keys + their parents, what we need to compute the diffs
215
self.needed_keys = ()
216
# Map from key: mp_diff
218
# Map from key: parents_needed (may have ghosts)
220
# Parents that aren't present
221
self.ghost_parents = ()
222
# Map from parent_key => number of children for this text
224
# Content chunks that are cached while we still need them
227
def _find_needed_keys(self):
228
"""Find the set of keys we need to request.
230
This includes all the original keys passed in, and the non-ghost
231
parents of those keys.
233
:return: (needed_keys, refcounts)
234
needed_keys is the set of all texts we need to extract
235
refcounts is a dict of {key: num_children} letting us know when we
236
no longer need to cache a given parent text
238
# All the keys and their parents
239
needed_keys = set(self.ordered_keys)
240
parent_map = self.vf.get_parent_map(needed_keys)
241
self.parent_map = parent_map
242
# TODO: Should we be using a different construct here? I think this
243
# uses difference_update internally, and we expect the result to
245
missing_keys = needed_keys.difference(parent_map)
247
raise errors.RevisionNotPresent(list(missing_keys)[0], self.vf)
248
# Parents that might be missing. They are allowed to be ghosts, but we
249
# should check for them
251
setdefault = refcounts.setdefault
253
for child_key, parent_keys in parent_map.iteritems():
255
# parent_keys may be None if a given VersionedFile claims to
256
# not support graph operations.
258
just_parents.update(parent_keys)
259
needed_keys.update(parent_keys)
260
for p in parent_keys:
261
refcounts[p] = setdefault(p, 0) + 1
262
just_parents.difference_update(parent_map)
263
# Remove any parents that are actually ghosts from the needed set
264
self.present_parents = set(self.vf.get_parent_map(just_parents))
265
self.ghost_parents = just_parents.difference(self.present_parents)
266
needed_keys.difference_update(self.ghost_parents)
267
self.needed_keys = needed_keys
268
self.refcounts = refcounts
269
return needed_keys, refcounts
271
def _compute_diff(self, key, parent_lines, lines):
272
"""Compute a single mp_diff, and store it in self._diffs"""
273
if len(parent_lines) > 0:
274
# XXX: _extract_blocks is not usefully defined anywhere...
275
# It was meant to extract the left-parent diff without
276
# having to recompute it for Knit content (pack-0.92,
277
# etc). That seems to have regressed somewhere
278
left_parent_blocks = self.vf._extract_blocks(key,
279
parent_lines[0], lines)
281
left_parent_blocks = None
282
diff = multiparent.MultiParent.from_lines(lines,
283
parent_lines, left_parent_blocks)
284
self.diffs[key] = diff
286
def _process_one_record(self, key, this_chunks):
288
if key in self.parent_map:
289
# This record should be ready to diff, since we requested
290
# content in 'topological' order
291
parent_keys = self.parent_map.pop(key)
292
# If a VersionedFile claims 'no-graph' support, then it may return
293
# None for any parent request, so we replace it with an empty tuple
294
if parent_keys is None:
297
for p in parent_keys:
298
# Alternatively we could check p not in self.needed_keys, but
299
# ghost_parents should be tiny versus huge
300
if p in self.ghost_parents:
302
refcount = self.refcounts[p]
303
if refcount == 1: # Last child reference
304
self.refcounts.pop(p)
305
parent_chunks = self.chunks.pop(p)
307
self.refcounts[p] = refcount - 1
308
parent_chunks = self.chunks[p]
309
p_lines = osutils.chunks_to_lines(parent_chunks)
310
# TODO: Should we cache the line form? We did the
311
# computation to get it, but storing it this way will
312
# be less memory efficient...
313
parent_lines.append(p_lines)
315
lines = osutils.chunks_to_lines(this_chunks)
316
# Since we needed the lines, we'll go ahead and cache them this way
318
self._compute_diff(key, parent_lines, lines)
320
# Is this content required for any more children?
321
if key in self.refcounts:
322
self.chunks[key] = this_chunks
324
def _extract_diffs(self):
325
needed_keys, refcounts = self._find_needed_keys()
326
for record in self.vf.get_record_stream(needed_keys,
327
'topological', True):
328
if record.storage_kind == 'absent':
329
raise errors.RevisionNotPresent(record.key, self.vf)
330
self._process_one_record(record.key,
331
record.get_bytes_as('chunked'))
333
def compute_diffs(self):
334
self._extract_diffs()
335
dpop = self.diffs.pop
336
return [dpop(k) for k in self.ordered_keys]
209
339
class VersionedFile(object):
210
340
"""Versioned text file storage.
403
537
if not mpvf.has_version(p))
404
538
present_parents = set(self.get_parent_map(needed_parents).keys())
405
539
for parent_id, lines in zip(present_parents,
406
self._get_lf_split_line_list(present_parents)):
540
self._get_lf_split_line_list(present_parents)):
407
541
mpvf.add_version(lines, parent_id, [])
408
for (version, parent_ids, expected_sha1, mpdiff), lines in\
409
zip(records, mpvf.get_line_list(versions)):
542
for (version, parent_ids, expected_sha1, mpdiff), lines in zip(
543
records, mpvf.get_line_list(versions)):
410
544
if len(parent_ids) == 1:
411
545
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
412
546
mpvf.get_diff(parent_ids[0]).num_lines()))
790
924
The keyspace is expressed via simple tuples. Any instance of VersionedFiles
791
925
may have a different length key-size, but that size will be constant for
792
all texts added to or retrieved from it. For instance, bzrlib uses
926
all texts added to or retrieved from it. For instance, breezy uses
793
927
instances with a key-size of 2 for storing user files in a repository, with
794
928
the first element the fileid, and the second the version of that file.
796
930
The use of tuples allows a single code base to support several different
797
931
uses with only the mapping logic changing from instance to instance.
933
:ivar _immediate_fallback_vfs: For subclasses that support stacking,
934
this is a list of other VersionedFiles immediately underneath this
935
one. They may in turn each have further fallbacks.
800
938
def add_lines(self, key, parents, lines, parent_texts=None,
1048
1186
def make_mpdiffs(self, keys):
1049
1187
"""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))
1188
generator = _MPDiffGenerator(self, keys)
1189
return generator.compute_diffs()
1191
def get_annotator(self):
1192
return annotate.Annotator(self)
1088
1194
missing_keys = index._missing_keys_from_parent_map
1090
1196
def _extract_blocks(self, version_id, source, target):
1199
def _transitive_fallbacks(self):
1200
"""Return the whole stack of fallback versionedfiles.
1202
This VersionedFiles may have a list of fallbacks, but it doesn't
1203
necessarily know about the whole stack going down, and it can't know
1204
at open time because they may change after the objects are opened.
1207
for a_vfs in self._immediate_fallback_vfs:
1208
all_fallbacks.append(a_vfs)
1209
all_fallbacks.extend(a_vfs._transitive_fallbacks())
1210
return all_fallbacks
1094
1213
class ThunkedVersionedFiles(VersionedFiles):
1095
1214
"""Storage for many versioned files thunked onto a 'VersionedFile' class.
1430
class VersionedFilesWithFallbacks(VersionedFiles):
1432
def without_fallbacks(self):
1433
"""Return a clone of this object without any fallbacks configured."""
1434
raise NotImplementedError(self.without_fallbacks)
1436
def add_fallback_versioned_files(self, a_versioned_files):
1437
"""Add a source of texts for texts not present in this knit.
1439
:param a_versioned_files: A VersionedFiles object.
1441
raise NotImplementedError(self.add_fallback_versioned_files)
1443
def get_known_graph_ancestry(self, keys):
1444
"""Get a KnownGraph instance with the ancestry of keys."""
1445
parent_map, missing_keys = self._index.find_ancestry(keys)
1446
for fallback in self._transitive_fallbacks():
1447
if not missing_keys:
1449
(f_parent_map, f_missing_keys) = fallback._index.find_ancestry(
1451
parent_map.update(f_parent_map)
1452
missing_keys = f_missing_keys
1453
kg = _mod_graph.KnownGraph(parent_map)
1314
1457
class _PlanMergeVersionedFile(VersionedFiles):
1315
1458
"""A VersionedFile for uncommitted and committed texts.
1771
class NoDupeAddLinesDecorator(object):
1772
"""Decorator for a VersionedFiles that skips doing an add_lines if the key
1776
def __init__(self, store):
1779
def add_lines(self, key, parents, lines, parent_texts=None,
1780
left_matching_blocks=None, nostore_sha=None, random_id=False,
1781
check_content=True):
1782
"""See VersionedFiles.add_lines.
1784
This implementation may return None as the third element of the return
1785
value when the original store wouldn't.
1788
raise NotImplementedError(
1789
"NoDupeAddLinesDecorator.add_lines does not implement the "
1790
"nostore_sha behaviour.")
1792
sha1 = osutils.sha_strings(lines)
1793
key = ("sha1:" + sha1,)
1796
if key in self._store.get_parent_map([key]):
1797
# This key has already been inserted, so don't do it again.
1799
sha1 = osutils.sha_strings(lines)
1800
return sha1, sum(map(len, lines)), None
1801
return self._store.add_lines(key, parents, lines,
1802
parent_texts=parent_texts,
1803
left_matching_blocks=left_matching_blocks,
1804
nostore_sha=nostore_sha, random_id=random_id,
1805
check_content=check_content)
1807
def __getattr__(self, name):
1808
return getattr(self._store, name)
1627
1811
def network_bytes_to_kind_and_offset(network_bytes):
1628
1812
"""Strip of a record kind from the front of network_bytes.
1720
1904
for prefix in sorted(per_prefix_map):
1721
1905
present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
1722
1906
return present_keys
1909
class _KeyRefs(object):
1911
def __init__(self, track_new_keys=False):
1912
# dict mapping 'key' to 'set of keys referring to that key'
1915
# set remembering all new keys
1916
self.new_keys = set()
1918
self.new_keys = None
1924
self.new_keys.clear()
1926
def add_references(self, key, refs):
1927
# Record the new references
1928
for referenced in refs:
1930
needed_by = self.refs[referenced]
1932
needed_by = self.refs[referenced] = set()
1934
# Discard references satisfied by the new key
1937
def get_new_keys(self):
1938
return self.new_keys
1940
def get_unsatisfied_refs(self):
1941
return self.refs.iterkeys()
1943
def _satisfy_refs_for_key(self, key):
1947
# No keys depended on this key. That's ok.
1950
def add_key(self, key):
1951
# satisfy refs for key, and remember that we've seen this key.
1952
self._satisfy_refs_for_key(key)
1953
if self.new_keys is not None:
1954
self.new_keys.add(key)
1956
def satisfy_refs_for_keys(self, keys):
1958
self._satisfy_refs_for_key(key)
1960
def get_referrers(self):
1962
for referrers in self.refs.itervalues():
1963
result.update(referrers)
added
removed
breezy/versionedfile.py
