7
7
# it under the terms of the GNU General Public License as published by
8
8
# the Free Software Foundation; either version 2 of the License, or
9
9
# (at your option) any later version.
11
11
# This program is distributed in the hope that it will be useful,
12
12
# but WITHOUT ANY WARRANTY; without even the implied warranty of
13
13
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14
14
# GNU General Public License for more details.
16
16
# You should have received a copy of the GNU General Public License
17
17
# along with this program; if not, write to the Free Software
18
18
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20
20
"""Versioned text file storage api."""
23
from copy import deepcopy
24
from unittest import TestSuite
27
import bzrlib.errors as errors
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
28
43
from bzrlib.inter import InterObject
44
from bzrlib.registry import Registry
29
45
from bzrlib.symbol_versioning import *
30
46
from bzrlib.textmerge import TextMerge
31
from bzrlib.transport.memory import MemoryTransport
32
from bzrlib.tsort import topo_sort
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':
36
198
class VersionedFile(object):
163
328
if '\n' in line[:-1]:
164
329
raise errors.BzrBadParameterContainsNewline("lines")
166
def _check_write_ok(self):
167
"""Is the versioned file marked as 'finished' ? Raise if it is."""
169
raise errors.OutSideTransaction()
170
if self._access_mode != 'w':
171
raise errors.ReadOnlyObjectDirtiedError(self)
173
def clear_cache(self):
174
"""Remove any data cached in the versioned file object."""
176
def clone_text(self, new_version_id, old_version_id, parents):
177
"""Add an identical text to old_version_id as new_version_id.
179
Must raise RevisionNotPresent if the old version or any of the
180
parents are not present in file history.
182
Must raise RevisionAlreadyPresent if the new version is
183
already present in file history."""
184
self._check_write_ok()
185
return self._clone_text(new_version_id, old_version_id, parents)
187
def _clone_text(self, new_version_id, old_version_id, parents):
188
"""Helper function to do the _clone_text work."""
189
raise NotImplementedError(self.clone_text)
191
def create_empty(self, name, transport, mode=None):
192
"""Create a new versioned file of this exact type.
194
:param name: the file name
195
:param transport: the transport
196
:param mode: optional file mode.
198
raise NotImplementedError(self.create_empty)
200
def fix_parents(self, version, new_parents):
201
"""Fix the parents list for version.
203
This is done by appending a new version to the index
204
with identical data except for the parents list.
205
the parents list must be a superset of the current
208
self._check_write_ok()
209
return self._fix_parents(version, new_parents)
211
def _fix_parents(self, version, new_parents):
212
"""Helper for fix_parents."""
213
raise NotImplementedError(self.fix_parents)
215
def get_delta(self, version):
216
"""Get a delta for constructing version from some other version.
218
:return: (delta_parent, sha1, noeol, delta)
219
Where delta_parent is a version id or None to indicate no parent.
221
raise NotImplementedError(self.get_delta)
223
def get_deltas(self, versions):
224
"""Get multiple deltas at once for constructing versions.
226
:return: dict(version_id:(delta_parent, sha1, noeol, delta))
227
Where delta_parent is a version id or None to indicate no parent, and
228
version_id is the version_id created by that delta.
231
for version in versions:
232
result[version] = self.get_delta(version)
235
def get_sha1(self, version_id):
236
"""Get the stored sha1 sum for the given revision.
238
:param name: The name of the version to lookup
240
raise NotImplementedError(self.get_sha1)
242
def get_suffixes(self):
243
"""Return the file suffixes associated with this versioned file."""
244
raise NotImplementedError(self.get_suffixes)
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)
246
420
def get_text(self, version_id):
247
421
"""Return version contents as a text string.
447
545
raise NotImplementedError(VersionedFile.plan_merge)
449
def weave_merge(self, plan, a_marker=TextMerge.A_MARKER,
547
def weave_merge(self, plan, a_marker=TextMerge.A_MARKER,
450
548
b_marker=TextMerge.B_MARKER):
451
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,)
454
1326
class PlanWeaveMerge(TextMerge):
455
1327
"""Weave merge that takes a plan as its input.
524
1403
PlanWeaveMerge.__init__(self, plan, a_marker, b_marker)
527
class InterVersionedFile(InterObject):
528
"""This class represents operations taking place between two versionedfiles..
530
Its instances have methods like join, and contain
531
references to the source and target versionedfiles these operations can be
534
Often we will provide convenience methods on 'versionedfile' which carry out
535
operations with another versionedfile - they will always forward to
536
InterVersionedFile.get(other).method_name(parameters).
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.
540
"""The available optimised InterVersionedFile types."""
542
def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
543
"""Integrate versions from self.source into self.target.
545
If version_ids is None all versions from source should be
546
incorporated into this versioned file.
548
Must raise RevisionNotPresent if any of the specified versions
549
are not present in the other files history unless ignore_missing is
550
supplied when they are silently skipped.
553
# - if the target is empty, just add all the versions from
554
# source to target, otherwise:
555
# - make a temporary versioned file of type target
556
# - insert the source content into it one at a time
558
if not self.target.versions():
561
# Make a new target-format versioned file.
562
temp_source = self.target.create_empty("temp", MemoryTransport())
564
version_ids = self._get_source_version_ids(version_ids, ignore_missing)
565
graph = self.source.get_graph(version_ids)
566
order = topo_sort(graph.items())
567
pb = ui.ui_factory.nested_progress_bar()
570
# TODO for incremental cross-format work:
571
# make a versioned file with the following content:
572
# all revisions we have been asked to join
573
# all their ancestors that are *not* in target already.
574
# the immediate parents of the above two sets, with
575
# empty parent lists - these versions are in target already
576
# and the incorrect version data will be ignored.
577
# TODO: for all ancestors that are present in target already,
578
# check them for consistent data, this requires moving sha1 from
580
# TODO: remove parent texts when they are not relevant any more for
581
# memory pressure reduction. RBC 20060313
582
# pb.update('Converting versioned data', 0, len(order))
583
# deltas = self.source.get_deltas(order)
584
for index, version in enumerate(order):
585
pb.update('Converting versioned data', index, len(order))
586
parent_text = target.add_lines(version,
587
self.source.get_parents(version),
588
self.source.get_lines(version),
589
parent_texts=parent_texts)
590
parent_texts[version] = parent_text
591
#delta_parent, sha1, noeol, delta = deltas[version]
592
#target.add_delta(version,
593
# self.source.get_parents(version),
598
#target.get_lines(version)
600
# this should hit the native code path for target
601
if target is not self.target:
602
return self.target.join(temp_source,
610
def _get_source_version_ids(self, version_ids, ignore_missing):
611
"""Determine the version ids to be used from self.source.
613
:param version_ids: The caller-supplied version ids to check. (None
614
for all). If None is in version_ids, it is stripped.
615
:param ignore_missing: if True, remove missing ids from the version
616
list. If False, raise RevisionNotPresent on
617
a missing version id.
618
:return: A set of version ids.
620
if version_ids is None:
621
# None cannot be in source.versions
622
return set(self.source.versions())
625
return set(self.source.versions()).intersection(set(version_ids))
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),
627
new_version_ids = set()
628
for version in version_ids:
631
if not self.source.has_version(version):
632
raise errors.RevisionNotPresent(version, str(self.source))
634
new_version_ids.add(version)
635
return new_version_ids
638
class InterVersionedFileTestProviderAdapter(object):
639
"""A tool to generate a suite testing multiple inter versioned-file classes.
641
This is done by copying the test once for each InterVersionedFile provider
642
and injecting the transport_server, transport_readonly_server,
643
versionedfile_factory and versionedfile_factory_to classes into each copy.
644
Each copy is also given a new id() to make it easy to identify.
647
def __init__(self, transport_server, transport_readonly_server, formats):
648
self._transport_server = transport_server
649
self._transport_readonly_server = transport_readonly_server
650
self._formats = formats
652
def adapt(self, test):
654
for (interversionedfile_class,
655
versionedfile_factory,
656
versionedfile_factory_to) in self._formats:
657
new_test = deepcopy(test)
658
new_test.transport_server = self._transport_server
659
new_test.transport_readonly_server = self._transport_readonly_server
660
new_test.interversionedfile_class = interversionedfile_class
661
new_test.versionedfile_factory = versionedfile_factory
662
new_test.versionedfile_factory_to = versionedfile_factory_to
663
def make_new_test_id():
664
new_id = "%s(%s)" % (new_test.id(), interversionedfile_class.__name__)
665
return lambda: new_id
666
new_test.id = make_new_test_id()
667
result.addTest(new_test)
671
def default_test_list():
672
"""Generate the default list of interversionedfile permutations to test."""
673
from bzrlib.weave import WeaveFile
674
from bzrlib.knit import KnitVersionedFile
676
# test the fallback InterVersionedFile from annotated knits to weave
677
result.append((InterVersionedFile,
680
for optimiser in InterVersionedFile._optimisers:
681
result.append((optimiser,
682
optimiser._matching_file_from_factory,
683
optimiser._matching_file_to_factory
685
# if there are specific combinations we want to use, we can add them
1466
yield AbsentContentFactory((k,))