1
# Copyright (C) 2005, 2006, 2007, 2008 Canonical Ltd
4
# Johan Rydberg <jrydberg@gnu.org>
6
# This program is free software; you can redistribute it and/or modify
7
# it under the terms of the GNU General Public License as published by
8
# the Free Software Foundation; either version 2 of the License, or
9
# (at your option) any later version.
11
# This program is distributed in the hope that it will be useful,
12
# but WITHOUT ANY WARRANTY; without even the implied warranty of
13
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14
# GNU General Public License for more details.
16
# You should have received a copy of the GNU General Public License
17
# along with this program; if not, write to the Free Software
18
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20
"""Versioned text file storage api."""
23
from cStringIO import StringIO
25
from zlib import adler32
27
from bzrlib.lazy_import import lazy_import
28
lazy_import(globals(), """
40
from bzrlib.graph import DictParentsProvider, Graph, _StackedParentsProvider
41
from bzrlib.transport.memory import MemoryTransport
43
from bzrlib.inter import InterObject
44
from bzrlib.registry import Registry
45
from bzrlib.symbol_versioning import *
46
from bzrlib.textmerge import TextMerge
49
adapter_registry = Registry()
50
adapter_registry.register_lazy(('knit-delta-gz', 'fulltext'), 'bzrlib.knit',
51
'DeltaPlainToFullText')
52
adapter_registry.register_lazy(('knit-ft-gz', 'fulltext'), 'bzrlib.knit',
54
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'knit-delta-gz'),
55
'bzrlib.knit', 'DeltaAnnotatedToUnannotated')
56
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'fulltext'),
57
'bzrlib.knit', 'DeltaAnnotatedToFullText')
58
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'knit-ft-gz'),
59
'bzrlib.knit', 'FTAnnotatedToUnannotated')
60
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'fulltext'),
61
'bzrlib.knit', 'FTAnnotatedToFullText')
62
# adapter_registry.register_lazy(('knit-annotated-ft-gz', 'chunked'),
63
# 'bzrlib.knit', 'FTAnnotatedToChunked')
66
class ContentFactory(object):
67
"""Abstract interface for insertion and retrieval from a VersionedFile.
69
:ivar sha1: None, or the sha1 of the content fulltext.
70
:ivar storage_kind: The native storage kind of this factory. One of
71
'mpdiff', 'knit-annotated-ft', 'knit-annotated-delta', 'knit-ft',
72
'knit-delta', 'fulltext', 'knit-annotated-ft-gz',
73
'knit-annotated-delta-gz', 'knit-ft-gz', 'knit-delta-gz'.
74
:ivar key: The key of this content. Each key is a tuple with a single
76
:ivar parents: A tuple of parent keys for self.key. If the object has
77
no parent information, None (as opposed to () for an empty list of
82
"""Create a ContentFactory."""
84
self.storage_kind = None
89
class ChunkedContentFactory(ContentFactory):
90
"""Static data content factory.
92
This takes a 'chunked' list of strings. The only requirement on 'chunked' is
93
that ''.join(lines) becomes a valid fulltext. A tuple of a single string
94
satisfies this, as does a list of lines.
96
:ivar sha1: None, or the sha1 of the content fulltext.
97
:ivar storage_kind: The native storage kind of this factory. Always
99
:ivar key: The key of this content. Each key is a tuple with a single
101
:ivar parents: A tuple of parent keys for self.key. If the object has
102
no parent information, None (as opposed to () for an empty list of
106
def __init__(self, key, parents, sha1, chunks):
107
"""Create a ContentFactory."""
109
self.storage_kind = 'chunked'
111
self.parents = parents
112
self._chunks = chunks
114
def get_bytes_as(self, storage_kind):
115
if storage_kind == 'chunked':
117
elif storage_kind == 'fulltext':
118
return ''.join(self._chunks)
119
raise errors.UnavailableRepresentation(self.key, storage_kind,
123
class FulltextContentFactory(ContentFactory):
124
"""Static data content factory.
126
This takes a fulltext when created and just returns that during
127
get_bytes_as('fulltext').
129
:ivar sha1: None, or the sha1 of the content fulltext.
130
:ivar storage_kind: The native storage kind of this factory. Always
132
:ivar key: The key of this content. Each key is a tuple with a single
134
:ivar parents: A tuple of parent keys for self.key. If the object has
135
no parent information, None (as opposed to () for an empty list of
139
def __init__(self, key, parents, sha1, text):
140
"""Create a ContentFactory."""
142
self.storage_kind = 'fulltext'
144
self.parents = parents
147
def get_bytes_as(self, storage_kind):
148
if storage_kind == self.storage_kind:
150
elif storage_kind == 'chunked':
152
raise errors.UnavailableRepresentation(self.key, storage_kind,
156
class AbsentContentFactory(ContentFactory):
157
"""A placeholder content factory for unavailable texts.
160
:ivar storage_kind: 'absent'.
161
:ivar key: The key of this content. Each key is a tuple with a single
166
def __init__(self, key):
167
"""Create a ContentFactory."""
169
self.storage_kind = 'absent'
174
class AdapterFactory(ContentFactory):
175
"""A content factory to adapt between key prefix's."""
177
def __init__(self, key, parents, adapted):
178
"""Create an adapter factory instance."""
180
self.parents = parents
181
self._adapted = adapted
183
def __getattr__(self, attr):
184
"""Return a member from the adapted object."""
185
if attr in ('key', 'parents'):
186
return self.__dict__[attr]
188
return getattr(self._adapted, attr)
191
def filter_absent(record_stream):
192
"""Adapt a record stream to remove absent records."""
193
for record in record_stream:
194
if record.storage_kind != 'absent':
198
class VersionedFile(object):
199
"""Versioned text file storage.
201
A versioned file manages versions of line-based text files,
202
keeping track of the originating version for each line.
204
To clients the "lines" of the file are represented as a list of
205
strings. These strings will typically have terminal newline
206
characters, but this is not required. In particular files commonly
207
do not have a newline at the end of the file.
209
Texts are identified by a version-id string.
213
def check_not_reserved_id(version_id):
214
revision.check_not_reserved_id(version_id)
216
def copy_to(self, name, transport):
217
"""Copy this versioned file to name on transport."""
218
raise NotImplementedError(self.copy_to)
220
def get_record_stream(self, versions, ordering, include_delta_closure):
221
"""Get a stream of records for versions.
223
:param versions: The versions to include. Each version is a tuple
225
:param ordering: Either 'unordered' or 'topological'. A topologically
226
sorted stream has compression parents strictly before their
228
:param include_delta_closure: If True then the closure across any
229
compression parents will be included (in the data content of the
230
stream, not in the emitted records). This guarantees that
231
'fulltext' can be used successfully on every record.
232
:return: An iterator of ContentFactory objects, each of which is only
233
valid until the iterator is advanced.
235
raise NotImplementedError(self.get_record_stream)
237
def has_version(self, version_id):
238
"""Returns whether version is present."""
239
raise NotImplementedError(self.has_version)
241
def insert_record_stream(self, stream):
242
"""Insert a record stream into this versioned file.
244
:param stream: A stream of records to insert.
246
:seealso VersionedFile.get_record_stream:
248
raise NotImplementedError
250
def add_lines(self, version_id, parents, lines, parent_texts=None,
251
left_matching_blocks=None, nostore_sha=None, random_id=False,
253
"""Add a single text on top of the versioned file.
255
Must raise RevisionAlreadyPresent if the new version is
256
already present in file history.
258
Must raise RevisionNotPresent if any of the given parents are
259
not present in file history.
261
:param lines: A list of lines. Each line must be a bytestring. And all
262
of them except the last must be terminated with \n and contain no
263
other \n's. The last line may either contain no \n's or a single
264
terminated \n. If the lines list does meet this constraint the add
265
routine may error or may succeed - but you will be unable to read
266
the data back accurately. (Checking the lines have been split
267
correctly is expensive and extremely unlikely to catch bugs so it
268
is not done at runtime unless check_content is True.)
269
:param parent_texts: An optional dictionary containing the opaque
270
representations of some or all of the parents of version_id to
271
allow delta optimisations. VERY IMPORTANT: the texts must be those
272
returned by add_lines or data corruption can be caused.
273
:param left_matching_blocks: a hint about which areas are common
274
between the text and its left-hand-parent. The format is
275
the SequenceMatcher.get_matching_blocks format.
276
:param nostore_sha: Raise ExistingContent and do not add the lines to
277
the versioned file if the digest of the lines matches this.
278
:param random_id: If True a random id has been selected rather than
279
an id determined by some deterministic process such as a converter
280
from a foreign VCS. When True the backend may choose not to check
281
for uniqueness of the resulting key within the versioned file, so
282
this should only be done when the result is expected to be unique
284
:param check_content: If True, the lines supplied are verified to be
285
bytestrings that are correctly formed lines.
286
:return: The text sha1, the number of bytes in the text, and an opaque
287
representation of the inserted version which can be provided
288
back to future add_lines calls in the parent_texts dictionary.
290
self._check_write_ok()
291
return self._add_lines(version_id, parents, lines, parent_texts,
292
left_matching_blocks, nostore_sha, random_id, check_content)
294
def _add_lines(self, version_id, parents, lines, parent_texts,
295
left_matching_blocks, nostore_sha, random_id, check_content):
296
"""Helper to do the class specific add_lines."""
297
raise NotImplementedError(self.add_lines)
299
def add_lines_with_ghosts(self, version_id, parents, lines,
300
parent_texts=None, nostore_sha=None, random_id=False,
301
check_content=True, left_matching_blocks=None):
302
"""Add lines to the versioned file, allowing ghosts to be present.
304
This takes the same parameters as add_lines and returns the same.
306
self._check_write_ok()
307
return self._add_lines_with_ghosts(version_id, parents, lines,
308
parent_texts, nostore_sha, random_id, check_content, left_matching_blocks)
310
def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts,
311
nostore_sha, random_id, check_content, left_matching_blocks):
312
"""Helper to do class specific add_lines_with_ghosts."""
313
raise NotImplementedError(self.add_lines_with_ghosts)
315
def check(self, progress_bar=None):
316
"""Check the versioned file for integrity."""
317
raise NotImplementedError(self.check)
319
def _check_lines_not_unicode(self, lines):
320
"""Check that lines being added to a versioned file are not unicode."""
322
if line.__class__ is not str:
323
raise errors.BzrBadParameterUnicode("lines")
325
def _check_lines_are_lines(self, lines):
326
"""Check that the lines really are full lines without inline EOL."""
328
if '\n' in line[:-1]:
329
raise errors.BzrBadParameterContainsNewline("lines")
331
def get_format_signature(self):
332
"""Get a text description of the data encoding in this file.
336
raise NotImplementedError(self.get_format_signature)
338
def make_mpdiffs(self, version_ids):
339
"""Create multiparent diffs for specified versions."""
340
knit_versions = set()
341
knit_versions.update(version_ids)
342
parent_map = self.get_parent_map(version_ids)
343
for version_id in version_ids:
345
knit_versions.update(parent_map[version_id])
347
raise errors.RevisionNotPresent(version_id, self)
348
# We need to filter out ghosts, because we can't diff against them.
349
knit_versions = set(self.get_parent_map(knit_versions).keys())
350
lines = dict(zip(knit_versions,
351
self._get_lf_split_line_list(knit_versions)))
353
for version_id in version_ids:
354
target = lines[version_id]
356
parents = [lines[p] for p in parent_map[version_id] if p in
359
# I don't know how this could ever trigger.
360
# parent_map[version_id] was already triggered in the previous
361
# for loop, and lines[p] has the 'if p in knit_versions' check,
362
# so we again won't have a KeyError.
363
raise errors.RevisionNotPresent(version_id, self)
365
left_parent_blocks = self._extract_blocks(version_id,
368
left_parent_blocks = None
369
diffs.append(multiparent.MultiParent.from_lines(target, parents,
373
def _extract_blocks(self, version_id, source, target):
376
def add_mpdiffs(self, records):
377
"""Add mpdiffs to this VersionedFile.
379
Records should be iterables of version, parents, expected_sha1,
380
mpdiff. mpdiff should be a MultiParent instance.
382
# Does this need to call self._check_write_ok()? (IanC 20070919)
384
mpvf = multiparent.MultiMemoryVersionedFile()
386
for version, parent_ids, expected_sha1, mpdiff in records:
387
versions.append(version)
388
mpvf.add_diff(mpdiff, version, parent_ids)
389
needed_parents = set()
390
for version, parent_ids, expected_sha1, mpdiff in records:
391
needed_parents.update(p for p in parent_ids
392
if not mpvf.has_version(p))
393
present_parents = set(self.get_parent_map(needed_parents).keys())
394
for parent_id, lines in zip(present_parents,
395
self._get_lf_split_line_list(present_parents)):
396
mpvf.add_version(lines, parent_id, [])
397
for (version, parent_ids, expected_sha1, mpdiff), lines in\
398
zip(records, mpvf.get_line_list(versions)):
399
if len(parent_ids) == 1:
400
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
401
mpvf.get_diff(parent_ids[0]).num_lines()))
403
left_matching_blocks = None
405
_, _, version_text = self.add_lines_with_ghosts(version,
406
parent_ids, lines, vf_parents,
407
left_matching_blocks=left_matching_blocks)
408
except NotImplementedError:
409
# The vf can't handle ghosts, so add lines normally, which will
410
# (reasonably) fail if there are ghosts in the data.
411
_, _, version_text = self.add_lines(version,
412
parent_ids, lines, vf_parents,
413
left_matching_blocks=left_matching_blocks)
414
vf_parents[version] = version_text
415
sha1s = self.get_sha1s(versions)
416
for version, parent_ids, expected_sha1, mpdiff in records:
417
if expected_sha1 != sha1s[version]:
418
raise errors.VersionedFileInvalidChecksum(version)
420
def get_text(self, version_id):
421
"""Return version contents as a text string.
423
Raises RevisionNotPresent if version is not present in
426
return ''.join(self.get_lines(version_id))
427
get_string = get_text
429
def get_texts(self, version_ids):
430
"""Return the texts of listed versions as a list of strings.
432
Raises RevisionNotPresent if version is not present in
435
return [''.join(self.get_lines(v)) for v in version_ids]
437
def get_lines(self, version_id):
438
"""Return version contents as a sequence of lines.
440
Raises RevisionNotPresent if version is not present in
443
raise NotImplementedError(self.get_lines)
445
def _get_lf_split_line_list(self, version_ids):
446
return [StringIO(t).readlines() for t in self.get_texts(version_ids)]
448
def get_ancestry(self, version_ids, topo_sorted=True):
449
"""Return a list of all ancestors of given version(s). This
450
will not include the null revision.
452
This list will not be topologically sorted if topo_sorted=False is
455
Must raise RevisionNotPresent if any of the given versions are
456
not present in file history."""
457
if isinstance(version_ids, basestring):
458
version_ids = [version_ids]
459
raise NotImplementedError(self.get_ancestry)
461
def get_ancestry_with_ghosts(self, version_ids):
462
"""Return a list of all ancestors of given version(s). This
463
will not include the null revision.
465
Must raise RevisionNotPresent if any of the given versions are
466
not present in file history.
468
Ghosts that are known about will be included in ancestry list,
469
but are not explicitly marked.
471
raise NotImplementedError(self.get_ancestry_with_ghosts)
473
def get_parent_map(self, version_ids):
474
"""Get a map of the parents of version_ids.
476
:param version_ids: The version ids to look up parents for.
477
:return: A mapping from version id to parents.
479
raise NotImplementedError(self.get_parent_map)
481
def get_parents_with_ghosts(self, version_id):
482
"""Return version names for parents of version_id.
484
Will raise RevisionNotPresent if version_id is not present
487
Ghosts that are known about will be included in the parent list,
488
but are not explicitly marked.
491
return list(self.get_parent_map([version_id])[version_id])
493
raise errors.RevisionNotPresent(version_id, self)
495
def annotate(self, version_id):
496
"""Return a list of (version-id, line) tuples for version_id.
498
:raise RevisionNotPresent: If the given version is
499
not present in file history.
501
raise NotImplementedError(self.annotate)
503
def iter_lines_added_or_present_in_versions(self, version_ids=None,
505
"""Iterate over the lines in the versioned file from version_ids.
507
This may return lines from other versions. Each item the returned
508
iterator yields is a tuple of a line and a text version that that line
509
is present in (not introduced in).
511
Ordering of results is in whatever order is most suitable for the
512
underlying storage format.
514
If a progress bar is supplied, it may be used to indicate progress.
515
The caller is responsible for cleaning up progress bars (because this
518
NOTES: Lines are normalised: they will all have \n terminators.
519
Lines are returned in arbitrary order.
521
:return: An iterator over (line, version_id).
523
raise NotImplementedError(self.iter_lines_added_or_present_in_versions)
525
def plan_merge(self, ver_a, ver_b):
526
"""Return pseudo-annotation indicating how the two versions merge.
528
This is computed between versions a and b and their common
531
Weave lines present in none of them are skipped entirely.
534
killed-base Dead in base revision
535
killed-both Killed in each revision
538
unchanged Alive in both a and b (possibly created in both)
541
ghost-a Killed in a, unborn in b
542
ghost-b Killed in b, unborn in a
543
irrelevant Not in either revision
545
raise NotImplementedError(VersionedFile.plan_merge)
547
def weave_merge(self, plan, a_marker=TextMerge.A_MARKER,
548
b_marker=TextMerge.B_MARKER):
549
return PlanWeaveMerge(plan, a_marker, b_marker).merge_lines()[0]
552
class RecordingVersionedFilesDecorator(object):
553
"""A minimal versioned files that records calls made on it.
555
Only enough methods have been added to support tests using it to date.
557
:ivar calls: A list of the calls made; can be reset at any time by
561
def __init__(self, backing_vf):
562
"""Create a RecordingVersionedFilesDecorator decorating backing_vf.
564
:param backing_vf: The versioned file to answer all methods.
566
self._backing_vf = backing_vf
569
def add_lines(self, key, parents, lines, parent_texts=None,
570
left_matching_blocks=None, nostore_sha=None, random_id=False,
572
self.calls.append(("add_lines", key, parents, lines, parent_texts,
573
left_matching_blocks, nostore_sha, random_id, check_content))
574
return self._backing_vf.add_lines(key, parents, lines, parent_texts,
575
left_matching_blocks, nostore_sha, random_id, check_content)
578
self._backing_vf.check()
580
def get_parent_map(self, keys):
581
self.calls.append(("get_parent_map", copy(keys)))
582
return self._backing_vf.get_parent_map(keys)
584
def get_record_stream(self, keys, sort_order, include_delta_closure):
585
self.calls.append(("get_record_stream", list(keys), sort_order,
586
include_delta_closure))
587
return self._backing_vf.get_record_stream(keys, sort_order,
588
include_delta_closure)
590
def get_sha1s(self, keys):
591
self.calls.append(("get_sha1s", copy(keys)))
592
return self._backing_vf.get_sha1s(keys)
594
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
595
self.calls.append(("iter_lines_added_or_present_in_keys", copy(keys)))
596
return self._backing_vf.iter_lines_added_or_present_in_keys(keys, pb=pb)
599
self.calls.append(("keys",))
600
return self._backing_vf.keys()
603
class OrderingVersionedFilesDecorator(RecordingVersionedFilesDecorator):
604
"""A VF that records calls, and returns keys in specific order.
606
:ivar calls: A list of the calls made; can be reset at any time by
610
def __init__(self, backing_vf, key_priority):
611
"""Create a RecordingVersionedFilesDecorator decorating backing_vf.
613
:param backing_vf: The versioned file to answer all methods.
614
:param key_priority: A dictionary defining what order keys should be
615
returned from an 'unordered' get_record_stream request.
616
Keys with lower priority are returned first, keys not present in
617
the map get an implicit priority of 0, and are returned in
618
lexicographical order.
620
RecordingVersionedFilesDecorator.__init__(self, backing_vf)
621
self._key_priority = key_priority
623
def get_record_stream(self, keys, sort_order, include_delta_closure):
624
self.calls.append(("get_record_stream", list(keys), sort_order,
625
include_delta_closure))
626
if sort_order == 'unordered':
628
return (self._key_priority.get(key, 0), key)
629
# Use a defined order by asking for the keys one-by-one from the
631
for key in sorted(keys, key=sort_key):
632
for record in self._backing_vf.get_record_stream([key],
633
'unordered', include_delta_closure):
636
for record in self._backing_vf.get_record_stream(keys, sort_order,
637
include_delta_closure):
641
class KeyMapper(object):
642
"""KeyMappers map between keys and underlying partitioned storage."""
645
"""Map key to an underlying storage identifier.
647
:param key: A key tuple e.g. ('file-id', 'revision-id').
648
:return: An underlying storage identifier, specific to the partitioning
651
raise NotImplementedError(self.map)
653
def unmap(self, partition_id):
654
"""Map a partitioned storage id back to a key prefix.
656
:param partition_id: The underlying partition id.
657
:return: As much of a key (or prefix) as is derivable from the partition
660
raise NotImplementedError(self.unmap)
663
class ConstantMapper(KeyMapper):
664
"""A key mapper that maps to a constant result."""
666
def __init__(self, result):
667
"""Create a ConstantMapper which will return result for all maps."""
668
self._result = result
671
"""See KeyMapper.map()."""
675
class URLEscapeMapper(KeyMapper):
676
"""Base class for use with transport backed storage.
678
This provides a map and unmap wrapper that respectively url escape and
679
unescape their outputs and inputs.
683
"""See KeyMapper.map()."""
684
return urllib.quote(self._map(key))
686
def unmap(self, partition_id):
687
"""See KeyMapper.unmap()."""
688
return self._unmap(urllib.unquote(partition_id))
691
class PrefixMapper(URLEscapeMapper):
692
"""A key mapper that extracts the first component of a key.
694
This mapper is for use with a transport based backend.
698
"""See KeyMapper.map()."""
701
def _unmap(self, partition_id):
702
"""See KeyMapper.unmap()."""
703
return (partition_id,)
706
class HashPrefixMapper(URLEscapeMapper):
707
"""A key mapper that combines the first component of a key with a hash.
709
This mapper is for use with a transport based backend.
713
"""See KeyMapper.map()."""
714
prefix = self._escape(key[0])
715
return "%02x/%s" % (adler32(prefix) & 0xff, prefix)
717
def _escape(self, prefix):
718
"""No escaping needed here."""
721
def _unmap(self, partition_id):
722
"""See KeyMapper.unmap()."""
723
return (self._unescape(osutils.basename(partition_id)),)
725
def _unescape(self, basename):
726
"""No unescaping needed for HashPrefixMapper."""
730
class HashEscapedPrefixMapper(HashPrefixMapper):
731
"""Combines the escaped first component of a key with a hash.
733
This mapper is for use with a transport based backend.
736
_safe = "abcdefghijklmnopqrstuvwxyz0123456789-_@,."
738
def _escape(self, prefix):
739
"""Turn a key element into a filesystem safe string.
741
This is similar to a plain urllib.quote, except
742
it uses specific safe characters, so that it doesn't
743
have to translate a lot of valid file ids.
745
# @ does not get escaped. This is because it is a valid
746
# filesystem character we use all the time, and it looks
747
# a lot better than seeing %40 all the time.
748
r = [((c in self._safe) and c or ('%%%02x' % ord(c)))
752
def _unescape(self, basename):
753
"""Escaped names are easily unescaped by urlutils."""
754
return urllib.unquote(basename)
757
def make_versioned_files_factory(versioned_file_factory, mapper):
758
"""Create a ThunkedVersionedFiles factory.
760
This will create a callable which when called creates a
761
ThunkedVersionedFiles on a transport, using mapper to access individual
762
versioned files, and versioned_file_factory to create each individual file.
764
def factory(transport):
765
return ThunkedVersionedFiles(transport, versioned_file_factory, mapper,
770
class VersionedFiles(object):
771
"""Storage for many versioned files.
773
This object allows a single keyspace for accessing the history graph and
774
contents of named bytestrings.
776
Currently no implementation allows the graph of different key prefixes to
777
intersect, but the API does allow such implementations in the future.
779
The keyspace is expressed via simple tuples. Any instance of VersionedFiles
780
may have a different length key-size, but that size will be constant for
781
all texts added to or retrieved from it. For instance, bzrlib uses
782
instances with a key-size of 2 for storing user files in a repository, with
783
the first element the fileid, and the second the version of that file.
785
The use of tuples allows a single code base to support several different
786
uses with only the mapping logic changing from instance to instance.
789
def add_lines(self, key, parents, lines, parent_texts=None,
790
left_matching_blocks=None, nostore_sha=None, random_id=False,
792
"""Add a text to the store.
794
:param key: The key tuple of the text to add.
795
:param parents: The parents key tuples of the text to add.
796
:param lines: A list of lines. Each line must be a bytestring. And all
797
of them except the last must be terminated with \n and contain no
798
other \n's. The last line may either contain no \n's or a single
799
terminating \n. If the lines list does meet this constraint the add
800
routine may error or may succeed - but you will be unable to read
801
the data back accurately. (Checking the lines have been split
802
correctly is expensive and extremely unlikely to catch bugs so it
803
is not done at runtime unless check_content is True.)
804
:param parent_texts: An optional dictionary containing the opaque
805
representations of some or all of the parents of version_id to
806
allow delta optimisations. VERY IMPORTANT: the texts must be those
807
returned by add_lines or data corruption can be caused.
808
:param left_matching_blocks: a hint about which areas are common
809
between the text and its left-hand-parent. The format is
810
the SequenceMatcher.get_matching_blocks format.
811
:param nostore_sha: Raise ExistingContent and do not add the lines to
812
the versioned file if the digest of the lines matches this.
813
:param random_id: If True a random id has been selected rather than
814
an id determined by some deterministic process such as a converter
815
from a foreign VCS. When True the backend may choose not to check
816
for uniqueness of the resulting key within the versioned file, so
817
this should only be done when the result is expected to be unique
819
:param check_content: If True, the lines supplied are verified to be
820
bytestrings that are correctly formed lines.
821
:return: The text sha1, the number of bytes in the text, and an opaque
822
representation of the inserted version which can be provided
823
back to future add_lines calls in the parent_texts dictionary.
825
raise NotImplementedError(self.add_lines)
827
def add_mpdiffs(self, records):
828
"""Add mpdiffs to this VersionedFile.
830
Records should be iterables of version, parents, expected_sha1,
831
mpdiff. mpdiff should be a MultiParent instance.
834
mpvf = multiparent.MultiMemoryVersionedFile()
836
for version, parent_ids, expected_sha1, mpdiff in records:
837
versions.append(version)
838
mpvf.add_diff(mpdiff, version, parent_ids)
839
needed_parents = set()
840
for version, parent_ids, expected_sha1, mpdiff in records:
841
needed_parents.update(p for p in parent_ids
842
if not mpvf.has_version(p))
843
# It seems likely that adding all the present parents as fulltexts can
844
# easily exhaust memory.
845
chunks_to_lines = osutils.chunks_to_lines
846
for record in self.get_record_stream(needed_parents, 'unordered',
848
if record.storage_kind == 'absent':
850
mpvf.add_version(chunks_to_lines(record.get_bytes_as('chunked')),
852
for (key, parent_keys, expected_sha1, mpdiff), lines in\
853
zip(records, mpvf.get_line_list(versions)):
854
if len(parent_keys) == 1:
855
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
856
mpvf.get_diff(parent_keys[0]).num_lines()))
858
left_matching_blocks = None
859
version_sha1, _, version_text = self.add_lines(key,
860
parent_keys, lines, vf_parents,
861
left_matching_blocks=left_matching_blocks)
862
if version_sha1 != expected_sha1:
863
raise errors.VersionedFileInvalidChecksum(version)
864
vf_parents[key] = version_text
866
def annotate(self, key):
867
"""Return a list of (version-key, line) tuples for the text of key.
869
:raise RevisionNotPresent: If the key is not present.
871
raise NotImplementedError(self.annotate)
873
def check(self, progress_bar=None):
874
"""Check this object for integrity."""
875
raise NotImplementedError(self.check)
878
def check_not_reserved_id(version_id):
879
revision.check_not_reserved_id(version_id)
881
def _check_lines_not_unicode(self, lines):
882
"""Check that lines being added to a versioned file are not unicode."""
884
if line.__class__ is not str:
885
raise errors.BzrBadParameterUnicode("lines")
887
def _check_lines_are_lines(self, lines):
888
"""Check that the lines really are full lines without inline EOL."""
890
if '\n' in line[:-1]:
891
raise errors.BzrBadParameterContainsNewline("lines")
893
def get_parent_map(self, keys):
894
"""Get a map of the parents of keys.
896
:param keys: The keys to look up parents for.
897
:return: A mapping from keys to parents. Absent keys are absent from
900
raise NotImplementedError(self.get_parent_map)
902
def get_record_stream(self, keys, ordering, include_delta_closure):
903
"""Get a stream of records for keys.
905
:param keys: The keys to include.
906
:param ordering: Either 'unordered' or 'topological'. A topologically
907
sorted stream has compression parents strictly before their
909
:param include_delta_closure: If True then the closure across any
910
compression parents will be included (in the opaque data).
911
:return: An iterator of ContentFactory objects, each of which is only
912
valid until the iterator is advanced.
914
raise NotImplementedError(self.get_record_stream)
916
def get_sha1s(self, keys):
917
"""Get the sha1's of the texts for the given keys.
919
:param keys: The names of the keys to lookup
920
:return: a dict from key to sha1 digest. Keys of texts which are not
921
present in the store are not present in the returned
924
raise NotImplementedError(self.get_sha1s)
926
has_key = index._has_key_from_parent_map
928
def insert_record_stream(self, stream):
929
"""Insert a record stream into this container.
931
:param stream: A stream of records to insert.
933
:seealso VersionedFile.get_record_stream:
935
raise NotImplementedError
937
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
938
"""Iterate over the lines in the versioned files from keys.
940
This may return lines from other keys. Each item the returned
941
iterator yields is a tuple of a line and a text version that that line
942
is present in (not introduced in).
944
Ordering of results is in whatever order is most suitable for the
945
underlying storage format.
947
If a progress bar is supplied, it may be used to indicate progress.
948
The caller is responsible for cleaning up progress bars (because this
952
* Lines are normalised by the underlying store: they will all have \n
954
* Lines are returned in arbitrary order.
956
:return: An iterator over (line, key).
958
raise NotImplementedError(self.iter_lines_added_or_present_in_keys)
961
"""Return a iterable of the keys for all the contained texts."""
962
raise NotImplementedError(self.keys)
964
def make_mpdiffs(self, keys):
965
"""Create multiparent diffs for specified keys."""
966
keys_order = tuple(keys)
967
keys = frozenset(keys)
968
knit_keys = set(keys)
969
parent_map = self.get_parent_map(keys)
970
for parent_keys in parent_map.itervalues():
972
knit_keys.update(parent_keys)
973
missing_keys = keys - set(parent_map)
975
raise errors.RevisionNotPresent(list(missing_keys)[0], self)
976
# We need to filter out ghosts, because we can't diff against them.
977
maybe_ghosts = knit_keys - keys
978
ghosts = maybe_ghosts - set(self.get_parent_map(maybe_ghosts))
979
knit_keys.difference_update(ghosts)
981
chunks_to_lines = osutils.chunks_to_lines
982
for record in self.get_record_stream(knit_keys, 'topological', True):
983
lines[record.key] = chunks_to_lines(record.get_bytes_as('chunked'))
984
# line_block_dict = {}
985
# for parent, blocks in record.extract_line_blocks():
986
# line_blocks[parent] = blocks
987
# line_blocks[record.key] = line_block_dict
989
for key in keys_order:
991
parents = parent_map[key] or []
992
# Note that filtering knit_keys can lead to a parent difference
993
# between the creation and the application of the mpdiff.
994
parent_lines = [lines[p] for p in parents if p in knit_keys]
995
if len(parent_lines) > 0:
996
left_parent_blocks = self._extract_blocks(key, parent_lines[0],
999
left_parent_blocks = None
1000
diffs.append(multiparent.MultiParent.from_lines(target,
1001
parent_lines, left_parent_blocks))
1004
missing_keys = index._missing_keys_from_parent_map
1006
def _extract_blocks(self, version_id, source, target):
1010
class ThunkedVersionedFiles(VersionedFiles):
1011
"""Storage for many versioned files thunked onto a 'VersionedFile' class.
1013
This object allows a single keyspace for accessing the history graph and
1014
contents of named bytestrings.
1016
Currently no implementation allows the graph of different key prefixes to
1017
intersect, but the API does allow such implementations in the future.
1020
def __init__(self, transport, file_factory, mapper, is_locked):
1021
"""Create a ThunkedVersionedFiles."""
1022
self._transport = transport
1023
self._file_factory = file_factory
1024
self._mapper = mapper
1025
self._is_locked = is_locked
1027
def add_lines(self, key, parents, lines, parent_texts=None,
1028
left_matching_blocks=None, nostore_sha=None, random_id=False,
1029
check_content=True):
1030
"""See VersionedFiles.add_lines()."""
1031
path = self._mapper.map(key)
1032
version_id = key[-1]
1033
parents = [parent[-1] for parent in parents]
1034
vf = self._get_vf(path)
1037
return vf.add_lines_with_ghosts(version_id, parents, lines,
1038
parent_texts=parent_texts,
1039
left_matching_blocks=left_matching_blocks,
1040
nostore_sha=nostore_sha, random_id=random_id,
1041
check_content=check_content)
1042
except NotImplementedError:
1043
return vf.add_lines(version_id, parents, lines,
1044
parent_texts=parent_texts,
1045
left_matching_blocks=left_matching_blocks,
1046
nostore_sha=nostore_sha, random_id=random_id,
1047
check_content=check_content)
1048
except errors.NoSuchFile:
1049
# parent directory may be missing, try again.
1050
self._transport.mkdir(osutils.dirname(path))
1052
return vf.add_lines_with_ghosts(version_id, parents, lines,
1053
parent_texts=parent_texts,
1054
left_matching_blocks=left_matching_blocks,
1055
nostore_sha=nostore_sha, random_id=random_id,
1056
check_content=check_content)
1057
except NotImplementedError:
1058
return vf.add_lines(version_id, parents, lines,
1059
parent_texts=parent_texts,
1060
left_matching_blocks=left_matching_blocks,
1061
nostore_sha=nostore_sha, random_id=random_id,
1062
check_content=check_content)
1064
def annotate(self, key):
1065
"""Return a list of (version-key, line) tuples for the text of key.
1067
:raise RevisionNotPresent: If the key is not present.
1070
path = self._mapper.map(prefix)
1071
vf = self._get_vf(path)
1072
origins = vf.annotate(key[-1])
1074
for origin, line in origins:
1075
result.append((prefix + (origin,), line))
1078
def check(self, progress_bar=None):
1079
"""See VersionedFiles.check()."""
1080
for prefix, vf in self._iter_all_components():
1083
def get_parent_map(self, keys):
1084
"""Get a map of the parents of keys.
1086
:param keys: The keys to look up parents for.
1087
:return: A mapping from keys to parents. Absent keys are absent from
1090
prefixes = self._partition_keys(keys)
1092
for prefix, suffixes in prefixes.items():
1093
path = self._mapper.map(prefix)
1094
vf = self._get_vf(path)
1095
parent_map = vf.get_parent_map(suffixes)
1096
for key, parents in parent_map.items():
1097
result[prefix + (key,)] = tuple(
1098
prefix + (parent,) for parent in parents)
1101
def _get_vf(self, path):
1102
if not self._is_locked():
1103
raise errors.ObjectNotLocked(self)
1104
return self._file_factory(path, self._transport, create=True,
1105
get_scope=lambda:None)
1107
def _partition_keys(self, keys):
1108
"""Turn keys into a dict of prefix:suffix_list."""
1111
prefix_keys = result.setdefault(key[:-1], [])
1112
prefix_keys.append(key[-1])
1115
def _get_all_prefixes(self):
1116
# Identify all key prefixes.
1117
# XXX: A bit hacky, needs polish.
1118
if type(self._mapper) == ConstantMapper:
1119
paths = [self._mapper.map(())]
1123
for quoted_relpath in self._transport.iter_files_recursive():
1124
path, ext = os.path.splitext(quoted_relpath)
1126
paths = list(relpaths)
1127
prefixes = [self._mapper.unmap(path) for path in paths]
1128
return zip(paths, prefixes)
1130
def get_record_stream(self, keys, ordering, include_delta_closure):
1131
"""See VersionedFiles.get_record_stream()."""
1132
# Ordering will be taken care of by each partitioned store; group keys
1135
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1136
suffixes = [(suffix,) for suffix in suffixes]
1137
for record in vf.get_record_stream(suffixes, ordering,
1138
include_delta_closure):
1139
if record.parents is not None:
1140
record.parents = tuple(
1141
prefix + parent for parent in record.parents)
1142
record.key = prefix + record.key
1145
def _iter_keys_vf(self, keys):
1146
prefixes = self._partition_keys(keys)
1148
for prefix, suffixes in prefixes.items():
1149
path = self._mapper.map(prefix)
1150
vf = self._get_vf(path)
1151
yield prefix, suffixes, vf
1153
def get_sha1s(self, keys):
1154
"""See VersionedFiles.get_sha1s()."""
1156
for prefix,suffixes, vf in self._iter_keys_vf(keys):
1157
vf_sha1s = vf.get_sha1s(suffixes)
1158
for suffix, sha1 in vf_sha1s.iteritems():
1159
sha1s[prefix + (suffix,)] = sha1
1162
def insert_record_stream(self, stream):
1163
"""Insert a record stream into this container.
1165
:param stream: A stream of records to insert.
1167
:seealso VersionedFile.get_record_stream:
1169
for record in stream:
1170
prefix = record.key[:-1]
1171
key = record.key[-1:]
1172
if record.parents is not None:
1173
parents = [parent[-1:] for parent in record.parents]
1176
thunk_record = AdapterFactory(key, parents, record)
1177
path = self._mapper.map(prefix)
1178
# Note that this parses the file many times; we can do better but
1179
# as this only impacts weaves in terms of performance, it is
1181
vf = self._get_vf(path)
1182
vf.insert_record_stream([thunk_record])
1184
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1185
"""Iterate over the lines in the versioned files from keys.
1187
This may return lines from other keys. Each item the returned
1188
iterator yields is a tuple of a line and a text version that that line
1189
is present in (not introduced in).
1191
Ordering of results is in whatever order is most suitable for the
1192
underlying storage format.
1194
If a progress bar is supplied, it may be used to indicate progress.
1195
The caller is responsible for cleaning up progress bars (because this
1199
* Lines are normalised by the underlying store: they will all have \n
1201
* Lines are returned in arbitrary order.
1203
:return: An iterator over (line, key).
1205
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1206
for line, version in vf.iter_lines_added_or_present_in_versions(suffixes):
1207
yield line, prefix + (version,)
1209
def _iter_all_components(self):
1210
for path, prefix in self._get_all_prefixes():
1211
yield prefix, self._get_vf(path)
1214
"""See VersionedFiles.keys()."""
1216
for prefix, vf in self._iter_all_components():
1217
for suffix in vf.versions():
1218
result.add(prefix + (suffix,))
1222
class _PlanMergeVersionedFile(VersionedFiles):
1223
"""A VersionedFile for uncommitted and committed texts.
1225
It is intended to allow merges to be planned with working tree texts.
1226
It implements only the small part of the VersionedFiles interface used by
1227
PlanMerge. It falls back to multiple versionedfiles for data not stored in
1228
_PlanMergeVersionedFile itself.
1230
:ivar: fallback_versionedfiles a list of VersionedFiles objects that can be
1231
queried for missing texts.
1234
def __init__(self, file_id):
1235
"""Create a _PlanMergeVersionedFile.
1237
:param file_id: Used with _PlanMerge code which is not yet fully
1238
tuple-keyspace aware.
1240
self._file_id = file_id
1241
# fallback locations
1242
self.fallback_versionedfiles = []
1243
# Parents for locally held keys.
1245
# line data for locally held keys.
1247
# key lookup providers
1248
self._providers = [DictParentsProvider(self._parents)]
1250
def plan_merge(self, ver_a, ver_b, base=None):
1251
"""See VersionedFile.plan_merge"""
1252
from bzrlib.merge import _PlanMerge
1254
return _PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge()
1255
old_plan = list(_PlanMerge(ver_a, base, self, (self._file_id,)).plan_merge())
1256
new_plan = list(_PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge())
1257
return _PlanMerge._subtract_plans(old_plan, new_plan)
1259
def plan_lca_merge(self, ver_a, ver_b, base=None):
1260
from bzrlib.merge import _PlanLCAMerge
1262
new_plan = _PlanLCAMerge(ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
1265
old_plan = _PlanLCAMerge(ver_a, base, self, (self._file_id,), graph).plan_merge()
1266
return _PlanLCAMerge._subtract_plans(list(old_plan), list(new_plan))
1268
def add_lines(self, key, parents, lines):
1269
"""See VersionedFiles.add_lines
1271
Lines are added locally, not to fallback versionedfiles. Also, ghosts
1272
are permitted. Only reserved ids are permitted.
1274
if type(key) is not tuple:
1275
raise TypeError(key)
1276
if not revision.is_reserved_id(key[-1]):
1277
raise ValueError('Only reserved ids may be used')
1279
raise ValueError('Parents may not be None')
1281
raise ValueError('Lines may not be None')
1282
self._parents[key] = tuple(parents)
1283
self._lines[key] = lines
1285
def get_record_stream(self, keys, ordering, include_delta_closure):
1288
if key in self._lines:
1289
lines = self._lines[key]
1290
parents = self._parents[key]
1292
yield ChunkedContentFactory(key, parents, None, lines)
1293
for versionedfile in self.fallback_versionedfiles:
1294
for record in versionedfile.get_record_stream(
1295
pending, 'unordered', True):
1296
if record.storage_kind == 'absent':
1299
pending.remove(record.key)
1303
# report absent entries
1305
yield AbsentContentFactory(key)
1307
def get_parent_map(self, keys):
1308
"""See VersionedFiles.get_parent_map"""
1309
# We create a new provider because a fallback may have been added.
1310
# If we make fallbacks private we can update a stack list and avoid
1311
# object creation thrashing.
1314
if revision.NULL_REVISION in keys:
1315
keys.remove(revision.NULL_REVISION)
1316
result[revision.NULL_REVISION] = ()
1317
self._providers = self._providers[:1] + self.fallback_versionedfiles
1319
_StackedParentsProvider(self._providers).get_parent_map(keys))
1320
for key, parents in result.iteritems():
1322
result[key] = (revision.NULL_REVISION,)
1326
class PlanWeaveMerge(TextMerge):
1327
"""Weave merge that takes a plan as its input.
1329
This exists so that VersionedFile.plan_merge is implementable.
1330
Most callers will want to use WeaveMerge instead.
1333
def __init__(self, plan, a_marker=TextMerge.A_MARKER,
1334
b_marker=TextMerge.B_MARKER):
1335
TextMerge.__init__(self, a_marker, b_marker)
1338
def _merge_struct(self):
1343
def outstanding_struct():
1344
if not lines_a and not lines_b:
1346
elif ch_a and not ch_b:
1349
elif ch_b and not ch_a:
1351
elif lines_a == lines_b:
1354
yield (lines_a, lines_b)
1356
# We previously considered either 'unchanged' or 'killed-both' lines
1357
# to be possible places to resynchronize. However, assuming agreement
1358
# on killed-both lines may be too aggressive. -- mbp 20060324
1359
for state, line in self.plan:
1360
if state == 'unchanged':
1361
# resync and flush queued conflicts changes if any
1362
for struct in outstanding_struct():
1368
if state == 'unchanged':
1371
elif state == 'killed-a':
1373
lines_b.append(line)
1374
elif state == 'killed-b':
1376
lines_a.append(line)
1377
elif state == 'new-a':
1379
lines_a.append(line)
1380
elif state == 'new-b':
1382
lines_b.append(line)
1383
elif state == 'conflicted-a':
1385
lines_a.append(line)
1386
elif state == 'conflicted-b':
1388
lines_b.append(line)
1390
if state not in ('irrelevant', 'ghost-a', 'ghost-b',
1391
'killed-base', 'killed-both'):
1392
raise AssertionError(state)
1393
for struct in outstanding_struct():
1397
class WeaveMerge(PlanWeaveMerge):
1398
"""Weave merge that takes a VersionedFile and two versions as its input."""
1400
def __init__(self, versionedfile, ver_a, ver_b,
1401
a_marker=PlanWeaveMerge.A_MARKER, b_marker=PlanWeaveMerge.B_MARKER):
1402
plan = versionedfile.plan_merge(ver_a, ver_b)
1403
PlanWeaveMerge.__init__(self, plan, a_marker, b_marker)
1406
class VirtualVersionedFiles(VersionedFiles):
1407
"""Dummy implementation for VersionedFiles that uses other functions for
1408
obtaining fulltexts and parent maps.
1410
This is always on the bottom of the stack and uses string keys
1411
(rather than tuples) internally.
1414
def __init__(self, get_parent_map, get_lines):
1415
"""Create a VirtualVersionedFiles.
1417
:param get_parent_map: Same signature as Repository.get_parent_map.
1418
:param get_lines: Should return lines for specified key or None if
1421
super(VirtualVersionedFiles, self).__init__()
1422
self._get_parent_map = get_parent_map
1423
self._get_lines = get_lines
1425
def check(self, progressbar=None):
1426
"""See VersionedFiles.check.
1428
:note: Always returns True for VirtualVersionedFiles.
1432
def add_mpdiffs(self, records):
1433
"""See VersionedFiles.mpdiffs.
1435
:note: Not implemented for VirtualVersionedFiles.
1437
raise NotImplementedError(self.add_mpdiffs)
1439
def get_parent_map(self, keys):
1440
"""See VersionedFiles.get_parent_map."""
1441
return dict([((k,), tuple([(p,) for p in v]))
1442
for k,v in self._get_parent_map([k for (k,) in keys]).iteritems()])
1444
def get_sha1s(self, keys):
1445
"""See VersionedFiles.get_sha1s."""
1448
lines = self._get_lines(k)
1449
if lines is not None:
1450
if not isinstance(lines, list):
1451
raise AssertionError
1452
ret[(k,)] = osutils.sha_strings(lines)
1455
def get_record_stream(self, keys, ordering, include_delta_closure):
1456
"""See VersionedFiles.get_record_stream."""
1457
for (k,) in list(keys):
1458
lines = self._get_lines(k)
1459
if lines is not None:
1460
if not isinstance(lines, list):
1461
raise AssertionError
1462
yield ChunkedContentFactory((k,), None,
1463
sha1=osutils.sha_strings(lines),
1466
yield AbsentContentFactory((k,))
1468
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1469
"""See VersionedFile.iter_lines_added_or_present_in_versions()."""
1470
for i, (key,) in enumerate(keys):
1472
pb.update("iterating texts", i, len(keys))
1473
for l in self._get_lines(key):
added
removed
bzrlib/versionedfile.py
