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')
64
class ContentFactory(object):
65
"""Abstract interface for insertion and retrieval from a VersionedFile.
67
:ivar sha1: None, or the sha1 of the content fulltext.
68
:ivar storage_kind: The native storage kind of this factory. One of
69
'mpdiff', 'knit-annotated-ft', 'knit-annotated-delta', 'knit-ft',
70
'knit-delta', 'fulltext', 'knit-annotated-ft-gz',
71
'knit-annotated-delta-gz', 'knit-ft-gz', 'knit-delta-gz'.
72
:ivar key: The key of this content. Each key is a tuple with a single
74
:ivar parents: A tuple of parent keys for self.key. If the object has
75
no parent information, None (as opposed to () for an empty list of
80
"""Create a ContentFactory."""
82
self.storage_kind = None
87
class FulltextContentFactory(ContentFactory):
88
"""Static data content factory.
90
This takes a fulltext when created and just returns that during
91
get_bytes_as('fulltext').
93
:ivar sha1: None, or the sha1 of the content fulltext.
94
:ivar storage_kind: The native storage kind of this factory. Always
96
:ivar key: The key of this content. Each key is a tuple with a single
98
:ivar parents: A tuple of parent keys for self.key. If the object has
99
no parent information, None (as opposed to () for an empty list of
103
def __init__(self, key, parents, sha1, text):
104
"""Create a ContentFactory."""
106
self.storage_kind = 'fulltext'
108
self.parents = parents
111
def get_bytes_as(self, storage_kind):
112
if storage_kind == self.storage_kind:
114
raise errors.UnavailableRepresentation(self.key, storage_kind,
118
class AbsentContentFactory(ContentFactory):
119
"""A placeholder content factory for unavailable texts.
122
:ivar storage_kind: 'absent'.
123
:ivar key: The key of this content. Each key is a tuple with a single
128
def __init__(self, key):
129
"""Create a ContentFactory."""
131
self.storage_kind = 'absent'
136
class AdapterFactory(ContentFactory):
137
"""A content factory to adapt between key prefix's."""
139
def __init__(self, key, parents, adapted):
140
"""Create an adapter factory instance."""
142
self.parents = parents
143
self._adapted = adapted
145
def __getattr__(self, attr):
146
"""Return a member from the adapted object."""
147
if attr in ('key', 'parents'):
148
return self.__dict__[attr]
150
return getattr(self._adapted, attr)
153
def filter_absent(record_stream):
154
"""Adapt a record stream to remove absent records."""
155
for record in record_stream:
156
if record.storage_kind != 'absent':
160
class VersionedFile(object):
161
"""Versioned text file storage.
163
A versioned file manages versions of line-based text files,
164
keeping track of the originating version for each line.
166
To clients the "lines" of the file are represented as a list of
167
strings. These strings will typically have terminal newline
168
characters, but this is not required. In particular files commonly
169
do not have a newline at the end of the file.
171
Texts are identified by a version-id string.
175
def check_not_reserved_id(version_id):
176
revision.check_not_reserved_id(version_id)
178
def copy_to(self, name, transport):
179
"""Copy this versioned file to name on transport."""
180
raise NotImplementedError(self.copy_to)
182
def get_record_stream(self, versions, ordering, include_delta_closure):
183
"""Get a stream of records for versions.
185
:param versions: The versions to include. Each version is a tuple
187
:param ordering: Either 'unordered' or 'topological'. A topologically
188
sorted stream has compression parents strictly before their
190
:param include_delta_closure: If True then the closure across any
191
compression parents will be included (in the data content of the
192
stream, not in the emitted records). This guarantees that
193
'fulltext' can be used successfully on every record.
194
:return: An iterator of ContentFactory objects, each of which is only
195
valid until the iterator is advanced.
197
raise NotImplementedError(self.get_record_stream)
199
def has_version(self, version_id):
200
"""Returns whether version is present."""
201
raise NotImplementedError(self.has_version)
203
def insert_record_stream(self, stream):
204
"""Insert a record stream into this versioned file.
206
:param stream: A stream of records to insert.
208
:seealso VersionedFile.get_record_stream:
210
raise NotImplementedError
212
def add_lines(self, version_id, parents, lines, parent_texts=None,
213
left_matching_blocks=None, nostore_sha=None, random_id=False,
215
"""Add a single text on top of the versioned file.
217
Must raise RevisionAlreadyPresent if the new version is
218
already present in file history.
220
Must raise RevisionNotPresent if any of the given parents are
221
not present in file history.
223
:param lines: A list of lines. Each line must be a bytestring. And all
224
of them except the last must be terminated with \n and contain no
225
other \n's. The last line may either contain no \n's or a single
226
terminated \n. If the lines list does meet this constraint the add
227
routine may error or may succeed - but you will be unable to read
228
the data back accurately. (Checking the lines have been split
229
correctly is expensive and extremely unlikely to catch bugs so it
230
is not done at runtime unless check_content is True.)
231
:param parent_texts: An optional dictionary containing the opaque
232
representations of some or all of the parents of version_id to
233
allow delta optimisations. VERY IMPORTANT: the texts must be those
234
returned by add_lines or data corruption can be caused.
235
:param left_matching_blocks: a hint about which areas are common
236
between the text and its left-hand-parent. The format is
237
the SequenceMatcher.get_matching_blocks format.
238
:param nostore_sha: Raise ExistingContent and do not add the lines to
239
the versioned file if the digest of the lines matches this.
240
:param random_id: If True a random id has been selected rather than
241
an id determined by some deterministic process such as a converter
242
from a foreign VCS. When True the backend may choose not to check
243
for uniqueness of the resulting key within the versioned file, so
244
this should only be done when the result is expected to be unique
246
:param check_content: If True, the lines supplied are verified to be
247
bytestrings that are correctly formed lines.
248
:return: The text sha1, the number of bytes in the text, and an opaque
249
representation of the inserted version which can be provided
250
back to future add_lines calls in the parent_texts dictionary.
252
self._check_write_ok()
253
return self._add_lines(version_id, parents, lines, parent_texts,
254
left_matching_blocks, nostore_sha, random_id, check_content)
256
def _add_lines(self, version_id, parents, lines, parent_texts,
257
left_matching_blocks, nostore_sha, random_id, check_content):
258
"""Helper to do the class specific add_lines."""
259
raise NotImplementedError(self.add_lines)
261
def add_lines_with_ghosts(self, version_id, parents, lines,
262
parent_texts=None, nostore_sha=None, random_id=False,
263
check_content=True, left_matching_blocks=None):
264
"""Add lines to the versioned file, allowing ghosts to be present.
266
This takes the same parameters as add_lines and returns the same.
268
self._check_write_ok()
269
return self._add_lines_with_ghosts(version_id, parents, lines,
270
parent_texts, nostore_sha, random_id, check_content, left_matching_blocks)
272
def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts,
273
nostore_sha, random_id, check_content, left_matching_blocks):
274
"""Helper to do class specific add_lines_with_ghosts."""
275
raise NotImplementedError(self.add_lines_with_ghosts)
277
def check(self, progress_bar=None):
278
"""Check the versioned file for integrity."""
279
raise NotImplementedError(self.check)
281
def _check_lines_not_unicode(self, lines):
282
"""Check that lines being added to a versioned file are not unicode."""
284
if line.__class__ is not str:
285
raise errors.BzrBadParameterUnicode("lines")
287
def _check_lines_are_lines(self, lines):
288
"""Check that the lines really are full lines without inline EOL."""
290
if '\n' in line[:-1]:
291
raise errors.BzrBadParameterContainsNewline("lines")
293
def get_format_signature(self):
294
"""Get a text description of the data encoding in this file.
298
raise NotImplementedError(self.get_format_signature)
300
def make_mpdiffs(self, version_ids):
301
"""Create multiparent diffs for specified versions."""
302
knit_versions = set()
303
knit_versions.update(version_ids)
304
parent_map = self.get_parent_map(version_ids)
305
for version_id in version_ids:
307
knit_versions.update(parent_map[version_id])
309
raise errors.RevisionNotPresent(version_id, self)
310
# We need to filter out ghosts, because we can't diff against them.
311
knit_versions = set(self.get_parent_map(knit_versions).keys())
312
lines = dict(zip(knit_versions,
313
self._get_lf_split_line_list(knit_versions)))
315
for version_id in version_ids:
316
target = lines[version_id]
318
parents = [lines[p] for p in parent_map[version_id] if p in
321
# I don't know how this could ever trigger.
322
# parent_map[version_id] was already triggered in the previous
323
# for loop, and lines[p] has the 'if p in knit_versions' check,
324
# so we again won't have a KeyError.
325
raise errors.RevisionNotPresent(version_id, self)
327
left_parent_blocks = self._extract_blocks(version_id,
330
left_parent_blocks = None
331
diffs.append(multiparent.MultiParent.from_lines(target, parents,
335
def _extract_blocks(self, version_id, source, target):
338
def add_mpdiffs(self, records):
339
"""Add mpdiffs to this VersionedFile.
341
Records should be iterables of version, parents, expected_sha1,
342
mpdiff. mpdiff should be a MultiParent instance.
344
# Does this need to call self._check_write_ok()? (IanC 20070919)
346
mpvf = multiparent.MultiMemoryVersionedFile()
348
for version, parent_ids, expected_sha1, mpdiff in records:
349
versions.append(version)
350
mpvf.add_diff(mpdiff, version, parent_ids)
351
needed_parents = set()
352
for version, parent_ids, expected_sha1, mpdiff in records:
353
needed_parents.update(p for p in parent_ids
354
if not mpvf.has_version(p))
355
present_parents = set(self.get_parent_map(needed_parents).keys())
356
for parent_id, lines in zip(present_parents,
357
self._get_lf_split_line_list(present_parents)):
358
mpvf.add_version(lines, parent_id, [])
359
for (version, parent_ids, expected_sha1, mpdiff), lines in\
360
zip(records, mpvf.get_line_list(versions)):
361
if len(parent_ids) == 1:
362
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
363
mpvf.get_diff(parent_ids[0]).num_lines()))
365
left_matching_blocks = None
367
_, _, version_text = self.add_lines_with_ghosts(version,
368
parent_ids, lines, vf_parents,
369
left_matching_blocks=left_matching_blocks)
370
except NotImplementedError:
371
# The vf can't handle ghosts, so add lines normally, which will
372
# (reasonably) fail if there are ghosts in the data.
373
_, _, version_text = self.add_lines(version,
374
parent_ids, lines, vf_parents,
375
left_matching_blocks=left_matching_blocks)
376
vf_parents[version] = version_text
377
sha1s = self.get_sha1s(versions)
378
for version, parent_ids, expected_sha1, mpdiff in records:
379
if expected_sha1 != sha1s[version]:
380
raise errors.VersionedFileInvalidChecksum(version)
382
def get_text(self, version_id):
383
"""Return version contents as a text string.
385
Raises RevisionNotPresent if version is not present in
388
return ''.join(self.get_lines(version_id))
389
get_string = get_text
391
def get_texts(self, version_ids):
392
"""Return the texts of listed versions as a list of strings.
394
Raises RevisionNotPresent if version is not present in
397
return [''.join(self.get_lines(v)) for v in version_ids]
399
def get_lines(self, version_id):
400
"""Return version contents as a sequence of lines.
402
Raises RevisionNotPresent if version is not present in
405
raise NotImplementedError(self.get_lines)
407
def _get_lf_split_line_list(self, version_ids):
408
return [StringIO(t).readlines() for t in self.get_texts(version_ids)]
410
def get_ancestry(self, version_ids, topo_sorted=True):
411
"""Return a list of all ancestors of given version(s). This
412
will not include the null revision.
414
This list will not be topologically sorted if topo_sorted=False is
417
Must raise RevisionNotPresent if any of the given versions are
418
not present in file history."""
419
if isinstance(version_ids, basestring):
420
version_ids = [version_ids]
421
raise NotImplementedError(self.get_ancestry)
423
def get_ancestry_with_ghosts(self, version_ids):
424
"""Return a list of all ancestors of given version(s). This
425
will not include the null revision.
427
Must raise RevisionNotPresent if any of the given versions are
428
not present in file history.
430
Ghosts that are known about will be included in ancestry list,
431
but are not explicitly marked.
433
raise NotImplementedError(self.get_ancestry_with_ghosts)
435
def get_parent_map(self, version_ids):
436
"""Get a map of the parents of version_ids.
438
:param version_ids: The version ids to look up parents for.
439
:return: A mapping from version id to parents.
441
raise NotImplementedError(self.get_parent_map)
443
def get_parents_with_ghosts(self, version_id):
444
"""Return version names for parents of version_id.
446
Will raise RevisionNotPresent if version_id is not present
449
Ghosts that are known about will be included in the parent list,
450
but are not explicitly marked.
453
return list(self.get_parent_map([version_id])[version_id])
455
raise errors.RevisionNotPresent(version_id, self)
457
def annotate(self, version_id):
458
"""Return a list of (version-id, line) tuples for version_id.
460
:raise RevisionNotPresent: If the given version is
461
not present in file history.
463
raise NotImplementedError(self.annotate)
465
def iter_lines_added_or_present_in_versions(self, version_ids=None,
467
"""Iterate over the lines in the versioned file from version_ids.
469
This may return lines from other versions. Each item the returned
470
iterator yields is a tuple of a line and a text version that that line
471
is present in (not introduced in).
473
Ordering of results is in whatever order is most suitable for the
474
underlying storage format.
476
If a progress bar is supplied, it may be used to indicate progress.
477
The caller is responsible for cleaning up progress bars (because this
480
NOTES: Lines are normalised: they will all have \n terminators.
481
Lines are returned in arbitrary order.
483
:return: An iterator over (line, version_id).
485
raise NotImplementedError(self.iter_lines_added_or_present_in_versions)
487
def plan_merge(self, ver_a, ver_b):
488
"""Return pseudo-annotation indicating how the two versions merge.
490
This is computed between versions a and b and their common
493
Weave lines present in none of them are skipped entirely.
496
killed-base Dead in base revision
497
killed-both Killed in each revision
500
unchanged Alive in both a and b (possibly created in both)
503
ghost-a Killed in a, unborn in b
504
ghost-b Killed in b, unborn in a
505
irrelevant Not in either revision
507
raise NotImplementedError(VersionedFile.plan_merge)
509
def weave_merge(self, plan, a_marker=TextMerge.A_MARKER,
510
b_marker=TextMerge.B_MARKER):
511
return PlanWeaveMerge(plan, a_marker, b_marker).merge_lines()[0]
514
class RecordingVersionedFilesDecorator(object):
515
"""A minimal versioned files that records calls made on it.
517
Only enough methods have been added to support tests using it to date.
519
:ivar calls: A list of the calls made; can be reset at any time by
523
def __init__(self, backing_vf):
524
"""Create a RecordingVersionedFilesDecorator decorating backing_vf.
526
:param backing_vf: The versioned file to answer all methods.
528
self._backing_vf = backing_vf
531
def add_lines(self, key, parents, lines, parent_texts=None,
532
left_matching_blocks=None, nostore_sha=None, random_id=False,
534
self.calls.append(("add_lines", key, parents, lines, parent_texts,
535
left_matching_blocks, nostore_sha, random_id, check_content))
536
return self._backing_vf.add_lines(key, parents, lines, parent_texts,
537
left_matching_blocks, nostore_sha, random_id, check_content)
540
self._backing_vf.check()
542
def get_parent_map(self, keys):
543
self.calls.append(("get_parent_map", copy(keys)))
544
return self._backing_vf.get_parent_map(keys)
546
def get_record_stream(self, keys, sort_order, include_delta_closure):
547
self.calls.append(("get_record_stream", list(keys), sort_order,
548
include_delta_closure))
549
return self._backing_vf.get_record_stream(keys, sort_order,
550
include_delta_closure)
552
def get_sha1s(self, keys):
553
self.calls.append(("get_sha1s", copy(keys)))
554
return self._backing_vf.get_sha1s(keys)
556
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
557
self.calls.append(("iter_lines_added_or_present_in_keys", copy(keys)))
558
return self._backing_vf.iter_lines_added_or_present_in_keys(keys, pb=pb)
561
self.calls.append(("keys",))
562
return self._backing_vf.keys()
565
class OrderingVersionedFilesDecorator(RecordingVersionedFilesDecorator):
566
"""A VF that records calls, and returns keys in specific order.
568
:ivar calls: A list of the calls made; can be reset at any time by
572
def __init__(self, backing_vf, key_priority):
573
"""Create a RecordingVersionedFilesDecorator decorating backing_vf.
575
:param backing_vf: The versioned file to answer all methods.
576
:param key_priority: A dictionary defining what order keys should be
577
returned from an 'unordered' get_record_stream request.
578
Keys with lower priority are returned first, keys not present in
579
the map get an implicit priority of 0, and are returned in
580
lexicographical order.
582
RecordingVersionedFilesDecorator.__init__(self, backing_vf)
583
self._key_priority = key_priority
585
def get_record_stream(self, keys, sort_order, include_delta_closure):
586
self.calls.append(("get_record_stream", list(keys), sort_order,
587
include_delta_closure))
588
if sort_order == 'unordered':
590
return (self._key_priority.get(key, 0), key)
591
# Use a defined order by asking for the keys one-by-one from the
593
for key in sorted(keys, key=sort_key):
594
for record in self._backing_vf.get_record_stream([key],
595
'unordered', include_delta_closure):
598
for record in self._backing_vf.get_record_stream(keys, sort_order,
599
include_delta_closure):
603
class KeyMapper(object):
604
"""KeyMappers map between keys and underlying partitioned storage."""
607
"""Map key to an underlying storage identifier.
609
:param key: A key tuple e.g. ('file-id', 'revision-id').
610
:return: An underlying storage identifier, specific to the partitioning
613
raise NotImplementedError(self.map)
615
def unmap(self, partition_id):
616
"""Map a partitioned storage id back to a key prefix.
618
:param partition_id: The underlying partition id.
619
:return: As much of a key (or prefix) as is derivable from the partition
622
raise NotImplementedError(self.unmap)
625
class ConstantMapper(KeyMapper):
626
"""A key mapper that maps to a constant result."""
628
def __init__(self, result):
629
"""Create a ConstantMapper which will return result for all maps."""
630
self._result = result
633
"""See KeyMapper.map()."""
637
class URLEscapeMapper(KeyMapper):
638
"""Base class for use with transport backed storage.
640
This provides a map and unmap wrapper that respectively url escape and
641
unescape their outputs and inputs.
645
"""See KeyMapper.map()."""
646
return urllib.quote(self._map(key))
648
def unmap(self, partition_id):
649
"""See KeyMapper.unmap()."""
650
return self._unmap(urllib.unquote(partition_id))
653
class PrefixMapper(URLEscapeMapper):
654
"""A key mapper that extracts the first component of a key.
656
This mapper is for use with a transport based backend.
660
"""See KeyMapper.map()."""
663
def _unmap(self, partition_id):
664
"""See KeyMapper.unmap()."""
665
return (partition_id,)
668
class HashPrefixMapper(URLEscapeMapper):
669
"""A key mapper that combines the first component of a key with a hash.
671
This mapper is for use with a transport based backend.
675
"""See KeyMapper.map()."""
676
prefix = self._escape(key[0])
677
return "%02x/%s" % (adler32(prefix) & 0xff, prefix)
679
def _escape(self, prefix):
680
"""No escaping needed here."""
683
def _unmap(self, partition_id):
684
"""See KeyMapper.unmap()."""
685
return (self._unescape(osutils.basename(partition_id)),)
687
def _unescape(self, basename):
688
"""No unescaping needed for HashPrefixMapper."""
692
class HashEscapedPrefixMapper(HashPrefixMapper):
693
"""Combines the escaped first component of a key with a hash.
695
This mapper is for use with a transport based backend.
698
_safe = "abcdefghijklmnopqrstuvwxyz0123456789-_@,."
700
def _escape(self, prefix):
701
"""Turn a key element into a filesystem safe string.
703
This is similar to a plain urllib.quote, except
704
it uses specific safe characters, so that it doesn't
705
have to translate a lot of valid file ids.
707
# @ does not get escaped. This is because it is a valid
708
# filesystem character we use all the time, and it looks
709
# a lot better than seeing %40 all the time.
710
r = [((c in self._safe) and c or ('%%%02x' % ord(c)))
714
def _unescape(self, basename):
715
"""Escaped names are easily unescaped by urlutils."""
716
return urllib.unquote(basename)
719
def make_versioned_files_factory(versioned_file_factory, mapper):
720
"""Create a ThunkedVersionedFiles factory.
722
This will create a callable which when called creates a
723
ThunkedVersionedFiles on a transport, using mapper to access individual
724
versioned files, and versioned_file_factory to create each individual file.
726
def factory(transport):
727
return ThunkedVersionedFiles(transport, versioned_file_factory, mapper,
732
class VersionedFiles(object):
733
"""Storage for many versioned files.
735
This object allows a single keyspace for accessing the history graph and
736
contents of named bytestrings.
738
Currently no implementation allows the graph of different key prefixes to
739
intersect, but the API does allow such implementations in the future.
741
The keyspace is expressed via simple tuples. Any instance of VersionedFiles
742
may have a different length key-size, but that size will be constant for
743
all texts added to or retrieved from it. For instance, bzrlib uses
744
instances with a key-size of 2 for storing user files in a repository, with
745
the first element the fileid, and the second the version of that file.
747
The use of tuples allows a single code base to support several different
748
uses with only the mapping logic changing from instance to instance.
751
def add_lines(self, key, parents, lines, parent_texts=None,
752
left_matching_blocks=None, nostore_sha=None, random_id=False,
754
"""Add a text to the store.
756
:param key: The key tuple of the text to add.
757
:param parents: The parents key tuples of the text to add.
758
:param lines: A list of lines. Each line must be a bytestring. And all
759
of them except the last must be terminated with \n and contain no
760
other \n's. The last line may either contain no \n's or a single
761
terminating \n. If the lines list does meet this constraint the add
762
routine may error or may succeed - but you will be unable to read
763
the data back accurately. (Checking the lines have been split
764
correctly is expensive and extremely unlikely to catch bugs so it
765
is not done at runtime unless check_content is True.)
766
:param parent_texts: An optional dictionary containing the opaque
767
representations of some or all of the parents of version_id to
768
allow delta optimisations. VERY IMPORTANT: the texts must be those
769
returned by add_lines or data corruption can be caused.
770
:param left_matching_blocks: a hint about which areas are common
771
between the text and its left-hand-parent. The format is
772
the SequenceMatcher.get_matching_blocks format.
773
:param nostore_sha: Raise ExistingContent and do not add the lines to
774
the versioned file if the digest of the lines matches this.
775
:param random_id: If True a random id has been selected rather than
776
an id determined by some deterministic process such as a converter
777
from a foreign VCS. When True the backend may choose not to check
778
for uniqueness of the resulting key within the versioned file, so
779
this should only be done when the result is expected to be unique
781
:param check_content: If True, the lines supplied are verified to be
782
bytestrings that are correctly formed lines.
783
:return: The text sha1, the number of bytes in the text, and an opaque
784
representation of the inserted version which can be provided
785
back to future add_lines calls in the parent_texts dictionary.
787
raise NotImplementedError(self.add_lines)
789
def add_mpdiffs(self, records):
790
"""Add mpdiffs to this VersionedFile.
792
Records should be iterables of version, parents, expected_sha1,
793
mpdiff. mpdiff should be a MultiParent instance.
796
mpvf = multiparent.MultiMemoryVersionedFile()
798
for version, parent_ids, expected_sha1, mpdiff in records:
799
versions.append(version)
800
mpvf.add_diff(mpdiff, version, parent_ids)
801
needed_parents = set()
802
for version, parent_ids, expected_sha1, mpdiff in records:
803
needed_parents.update(p for p in parent_ids
804
if not mpvf.has_version(p))
805
# It seems likely that adding all the present parents as fulltexts can
806
# easily exhaust memory.
807
split_lines = osutils.split_lines
808
for record in self.get_record_stream(needed_parents, 'unordered',
810
if record.storage_kind == 'absent':
812
mpvf.add_version(split_lines(record.get_bytes_as('fulltext')),
814
for (key, parent_keys, expected_sha1, mpdiff), lines in\
815
zip(records, mpvf.get_line_list(versions)):
816
if len(parent_keys) == 1:
817
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
818
mpvf.get_diff(parent_keys[0]).num_lines()))
820
left_matching_blocks = None
821
version_sha1, _, version_text = self.add_lines(key,
822
parent_keys, lines, vf_parents,
823
left_matching_blocks=left_matching_blocks)
824
if version_sha1 != expected_sha1:
825
raise errors.VersionedFileInvalidChecksum(version)
826
vf_parents[key] = version_text
828
def annotate(self, key):
829
"""Return a list of (version-key, line) tuples for the text of key.
831
:raise RevisionNotPresent: If the key is not present.
833
raise NotImplementedError(self.annotate)
835
def check(self, progress_bar=None):
836
"""Check this object for integrity."""
837
raise NotImplementedError(self.check)
840
def check_not_reserved_id(version_id):
841
revision.check_not_reserved_id(version_id)
843
def _check_lines_not_unicode(self, lines):
844
"""Check that lines being added to a versioned file are not unicode."""
846
if line.__class__ is not str:
847
raise errors.BzrBadParameterUnicode("lines")
849
def _check_lines_are_lines(self, lines):
850
"""Check that the lines really are full lines without inline EOL."""
852
if '\n' in line[:-1]:
853
raise errors.BzrBadParameterContainsNewline("lines")
855
def get_parent_map(self, keys):
856
"""Get a map of the parents of keys.
858
:param keys: The keys to look up parents for.
859
:return: A mapping from keys to parents. Absent keys are absent from
862
raise NotImplementedError(self.get_parent_map)
864
def get_record_stream(self, keys, ordering, include_delta_closure):
865
"""Get a stream of records for keys.
867
:param keys: The keys to include.
868
:param ordering: Either 'unordered' or 'topological'. A topologically
869
sorted stream has compression parents strictly before their
871
:param include_delta_closure: If True then the closure across any
872
compression parents will be included (in the opaque data).
873
:return: An iterator of ContentFactory objects, each of which is only
874
valid until the iterator is advanced.
876
raise NotImplementedError(self.get_record_stream)
878
def get_sha1s(self, keys):
879
"""Get the sha1's of the texts for the given keys.
881
:param keys: The names of the keys to lookup
882
:return: a dict from key to sha1 digest. Keys of texts which are not
883
present in the store are not present in the returned
886
raise NotImplementedError(self.get_sha1s)
888
has_key = index._has_key_from_parent_map
890
def insert_record_stream(self, stream):
891
"""Insert a record stream into this container.
893
:param stream: A stream of records to insert.
895
:seealso VersionedFile.get_record_stream:
897
raise NotImplementedError
899
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
900
"""Iterate over the lines in the versioned files from keys.
902
This may return lines from other keys. Each item the returned
903
iterator yields is a tuple of a line and a text version that that line
904
is present in (not introduced in).
906
Ordering of results is in whatever order is most suitable for the
907
underlying storage format.
909
If a progress bar is supplied, it may be used to indicate progress.
910
The caller is responsible for cleaning up progress bars (because this
914
* Lines are normalised by the underlying store: they will all have \n
916
* Lines are returned in arbitrary order.
918
:return: An iterator over (line, key).
920
raise NotImplementedError(self.iter_lines_added_or_present_in_keys)
923
"""Return a iterable of the keys for all the contained texts."""
924
raise NotImplementedError(self.keys)
926
def make_mpdiffs(self, keys):
927
"""Create multiparent diffs for specified keys."""
928
keys_order = tuple(keys)
929
keys = frozenset(keys)
930
knit_keys = set(keys)
931
parent_map = self.get_parent_map(keys)
932
for parent_keys in parent_map.itervalues():
934
knit_keys.update(parent_keys)
935
missing_keys = keys - set(parent_map)
937
raise errors.RevisionNotPresent(list(missing_keys)[0], self)
938
# We need to filter out ghosts, because we can't diff against them.
939
maybe_ghosts = knit_keys - keys
940
ghosts = maybe_ghosts - set(self.get_parent_map(maybe_ghosts))
941
knit_keys.difference_update(ghosts)
943
split_lines = osutils.split_lines
944
for record in self.get_record_stream(knit_keys, 'topological', True):
945
lines[record.key] = split_lines(record.get_bytes_as('fulltext'))
946
# line_block_dict = {}
947
# for parent, blocks in record.extract_line_blocks():
948
# line_blocks[parent] = blocks
949
# line_blocks[record.key] = line_block_dict
951
for key in keys_order:
953
parents = parent_map[key] or []
954
# Note that filtering knit_keys can lead to a parent difference
955
# between the creation and the application of the mpdiff.
956
parent_lines = [lines[p] for p in parents if p in knit_keys]
957
if len(parent_lines) > 0:
958
left_parent_blocks = self._extract_blocks(key, parent_lines[0],
961
left_parent_blocks = None
962
diffs.append(multiparent.MultiParent.from_lines(target,
963
parent_lines, left_parent_blocks))
966
missing_keys = index._missing_keys_from_parent_map
968
def _extract_blocks(self, version_id, source, target):
972
class ThunkedVersionedFiles(VersionedFiles):
973
"""Storage for many versioned files thunked onto a 'VersionedFile' class.
975
This object allows a single keyspace for accessing the history graph and
976
contents of named bytestrings.
978
Currently no implementation allows the graph of different key prefixes to
979
intersect, but the API does allow such implementations in the future.
982
def __init__(self, transport, file_factory, mapper, is_locked):
983
"""Create a ThunkedVersionedFiles."""
984
self._transport = transport
985
self._file_factory = file_factory
986
self._mapper = mapper
987
self._is_locked = is_locked
989
def add_lines(self, key, parents, lines, parent_texts=None,
990
left_matching_blocks=None, nostore_sha=None, random_id=False,
992
"""See VersionedFiles.add_lines()."""
993
path = self._mapper.map(key)
995
parents = [parent[-1] for parent in parents]
996
vf = self._get_vf(path)
999
return vf.add_lines_with_ghosts(version_id, parents, lines,
1000
parent_texts=parent_texts,
1001
left_matching_blocks=left_matching_blocks,
1002
nostore_sha=nostore_sha, random_id=random_id,
1003
check_content=check_content)
1004
except NotImplementedError:
1005
return vf.add_lines(version_id, parents, lines,
1006
parent_texts=parent_texts,
1007
left_matching_blocks=left_matching_blocks,
1008
nostore_sha=nostore_sha, random_id=random_id,
1009
check_content=check_content)
1010
except errors.NoSuchFile:
1011
# parent directory may be missing, try again.
1012
self._transport.mkdir(osutils.dirname(path))
1014
return vf.add_lines_with_ghosts(version_id, parents, lines,
1015
parent_texts=parent_texts,
1016
left_matching_blocks=left_matching_blocks,
1017
nostore_sha=nostore_sha, random_id=random_id,
1018
check_content=check_content)
1019
except NotImplementedError:
1020
return vf.add_lines(version_id, parents, lines,
1021
parent_texts=parent_texts,
1022
left_matching_blocks=left_matching_blocks,
1023
nostore_sha=nostore_sha, random_id=random_id,
1024
check_content=check_content)
1026
def annotate(self, key):
1027
"""Return a list of (version-key, line) tuples for the text of key.
1029
:raise RevisionNotPresent: If the key is not present.
1032
path = self._mapper.map(prefix)
1033
vf = self._get_vf(path)
1034
origins = vf.annotate(key[-1])
1036
for origin, line in origins:
1037
result.append((prefix + (origin,), line))
1040
def check(self, progress_bar=None):
1041
"""See VersionedFiles.check()."""
1042
for prefix, vf in self._iter_all_components():
1045
def get_parent_map(self, keys):
1046
"""Get a map of the parents of keys.
1048
:param keys: The keys to look up parents for.
1049
:return: A mapping from keys to parents. Absent keys are absent from
1052
prefixes = self._partition_keys(keys)
1054
for prefix, suffixes in prefixes.items():
1055
path = self._mapper.map(prefix)
1056
vf = self._get_vf(path)
1057
parent_map = vf.get_parent_map(suffixes)
1058
for key, parents in parent_map.items():
1059
result[prefix + (key,)] = tuple(
1060
prefix + (parent,) for parent in parents)
1063
def _get_vf(self, path):
1064
if not self._is_locked():
1065
raise errors.ObjectNotLocked(self)
1066
return self._file_factory(path, self._transport, create=True,
1067
get_scope=lambda:None)
1069
def _partition_keys(self, keys):
1070
"""Turn keys into a dict of prefix:suffix_list."""
1073
prefix_keys = result.setdefault(key[:-1], [])
1074
prefix_keys.append(key[-1])
1077
def _get_all_prefixes(self):
1078
# Identify all key prefixes.
1079
# XXX: A bit hacky, needs polish.
1080
if type(self._mapper) == ConstantMapper:
1081
paths = [self._mapper.map(())]
1085
for quoted_relpath in self._transport.iter_files_recursive():
1086
path, ext = os.path.splitext(quoted_relpath)
1088
paths = list(relpaths)
1089
prefixes = [self._mapper.unmap(path) for path in paths]
1090
return zip(paths, prefixes)
1092
def get_record_stream(self, keys, ordering, include_delta_closure):
1093
"""See VersionedFiles.get_record_stream()."""
1094
# Ordering will be taken care of by each partitioned store; group keys
1097
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1098
suffixes = [(suffix,) for suffix in suffixes]
1099
for record in vf.get_record_stream(suffixes, ordering,
1100
include_delta_closure):
1101
if record.parents is not None:
1102
record.parents = tuple(
1103
prefix + parent for parent in record.parents)
1104
record.key = prefix + record.key
1107
def _iter_keys_vf(self, keys):
1108
prefixes = self._partition_keys(keys)
1110
for prefix, suffixes in prefixes.items():
1111
path = self._mapper.map(prefix)
1112
vf = self._get_vf(path)
1113
yield prefix, suffixes, vf
1115
def get_sha1s(self, keys):
1116
"""See VersionedFiles.get_sha1s()."""
1118
for prefix,suffixes, vf in self._iter_keys_vf(keys):
1119
vf_sha1s = vf.get_sha1s(suffixes)
1120
for suffix, sha1 in vf_sha1s.iteritems():
1121
sha1s[prefix + (suffix,)] = sha1
1124
def insert_record_stream(self, stream):
1125
"""Insert a record stream into this container.
1127
:param stream: A stream of records to insert.
1129
:seealso VersionedFile.get_record_stream:
1131
for record in stream:
1132
prefix = record.key[:-1]
1133
key = record.key[-1:]
1134
if record.parents is not None:
1135
parents = [parent[-1:] for parent in record.parents]
1138
thunk_record = AdapterFactory(key, parents, record)
1139
path = self._mapper.map(prefix)
1140
# Note that this parses the file many times; we can do better but
1141
# as this only impacts weaves in terms of performance, it is
1143
vf = self._get_vf(path)
1144
vf.insert_record_stream([thunk_record])
1146
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1147
"""Iterate over the lines in the versioned files from keys.
1149
This may return lines from other keys. Each item the returned
1150
iterator yields is a tuple of a line and a text version that that line
1151
is present in (not introduced in).
1153
Ordering of results is in whatever order is most suitable for the
1154
underlying storage format.
1156
If a progress bar is supplied, it may be used to indicate progress.
1157
The caller is responsible for cleaning up progress bars (because this
1161
* Lines are normalised by the underlying store: they will all have \n
1163
* Lines are returned in arbitrary order.
1165
:return: An iterator over (line, key).
1167
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1168
for line, version in vf.iter_lines_added_or_present_in_versions(suffixes):
1169
yield line, prefix + (version,)
1171
def _iter_all_components(self):
1172
for path, prefix in self._get_all_prefixes():
1173
yield prefix, self._get_vf(path)
1176
"""See VersionedFiles.keys()."""
1178
for prefix, vf in self._iter_all_components():
1179
for suffix in vf.versions():
1180
result.add(prefix + (suffix,))
1184
class _PlanMergeVersionedFile(VersionedFiles):
1185
"""A VersionedFile for uncommitted and committed texts.
1187
It is intended to allow merges to be planned with working tree texts.
1188
It implements only the small part of the VersionedFiles interface used by
1189
PlanMerge. It falls back to multiple versionedfiles for data not stored in
1190
_PlanMergeVersionedFile itself.
1192
:ivar: fallback_versionedfiles a list of VersionedFiles objects that can be
1193
queried for missing texts.
1196
def __init__(self, file_id):
1197
"""Create a _PlanMergeVersionedFile.
1199
:param file_id: Used with _PlanMerge code which is not yet fully
1200
tuple-keyspace aware.
1202
self._file_id = file_id
1203
# fallback locations
1204
self.fallback_versionedfiles = []
1205
# Parents for locally held keys.
1207
# line data for locally held keys.
1209
# key lookup providers
1210
self._providers = [DictParentsProvider(self._parents)]
1212
def plan_merge(self, ver_a, ver_b, base=None):
1213
"""See VersionedFile.plan_merge"""
1214
from bzrlib.merge import _PlanMerge
1216
return _PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge()
1217
old_plan = list(_PlanMerge(ver_a, base, self, (self._file_id,)).plan_merge())
1218
new_plan = list(_PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge())
1219
return _PlanMerge._subtract_plans(old_plan, new_plan)
1221
def plan_lca_merge(self, ver_a, ver_b, base=None):
1222
from bzrlib.merge import _PlanLCAMerge
1224
new_plan = _PlanLCAMerge(ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
1227
old_plan = _PlanLCAMerge(ver_a, base, self, (self._file_id,), graph).plan_merge()
1228
return _PlanLCAMerge._subtract_plans(list(old_plan), list(new_plan))
1230
def add_lines(self, key, parents, lines):
1231
"""See VersionedFiles.add_lines
1233
Lines are added locally, not to fallback versionedfiles. Also, ghosts
1234
are permitted. Only reserved ids are permitted.
1236
if type(key) is not tuple:
1237
raise TypeError(key)
1238
if not revision.is_reserved_id(key[-1]):
1239
raise ValueError('Only reserved ids may be used')
1241
raise ValueError('Parents may not be None')
1243
raise ValueError('Lines may not be None')
1244
self._parents[key] = tuple(parents)
1245
self._lines[key] = lines
1247
def get_record_stream(self, keys, ordering, include_delta_closure):
1250
if key in self._lines:
1251
lines = self._lines[key]
1252
parents = self._parents[key]
1254
yield FulltextContentFactory(key, parents, None,
1256
for versionedfile in self.fallback_versionedfiles:
1257
for record in versionedfile.get_record_stream(
1258
pending, 'unordered', True):
1259
if record.storage_kind == 'absent':
1262
pending.remove(record.key)
1266
# report absent entries
1268
yield AbsentContentFactory(key)
1270
def get_parent_map(self, keys):
1271
"""See VersionedFiles.get_parent_map"""
1272
# We create a new provider because a fallback may have been added.
1273
# If we make fallbacks private we can update a stack list and avoid
1274
# object creation thrashing.
1277
if revision.NULL_REVISION in keys:
1278
keys.remove(revision.NULL_REVISION)
1279
result[revision.NULL_REVISION] = ()
1280
self._providers = self._providers[:1] + self.fallback_versionedfiles
1282
_StackedParentsProvider(self._providers).get_parent_map(keys))
1283
for key, parents in result.iteritems():
1285
result[key] = (revision.NULL_REVISION,)
1289
class PlanWeaveMerge(TextMerge):
1290
"""Weave merge that takes a plan as its input.
1292
This exists so that VersionedFile.plan_merge is implementable.
1293
Most callers will want to use WeaveMerge instead.
1296
def __init__(self, plan, a_marker=TextMerge.A_MARKER,
1297
b_marker=TextMerge.B_MARKER):
1298
TextMerge.__init__(self, a_marker, b_marker)
1301
def _merge_struct(self):
1306
def outstanding_struct():
1307
if not lines_a and not lines_b:
1309
elif ch_a and not ch_b:
1312
elif ch_b and not ch_a:
1314
elif lines_a == lines_b:
1317
yield (lines_a, lines_b)
1319
# We previously considered either 'unchanged' or 'killed-both' lines
1320
# to be possible places to resynchronize. However, assuming agreement
1321
# on killed-both lines may be too aggressive. -- mbp 20060324
1322
for state, line in self.plan:
1323
if state == 'unchanged':
1324
# resync and flush queued conflicts changes if any
1325
for struct in outstanding_struct():
1331
if state == 'unchanged':
1334
elif state == 'killed-a':
1336
lines_b.append(line)
1337
elif state == 'killed-b':
1339
lines_a.append(line)
1340
elif state == 'new-a':
1342
lines_a.append(line)
1343
elif state == 'new-b':
1345
lines_b.append(line)
1346
elif state == 'conflicted-a':
1348
lines_a.append(line)
1349
elif state == 'conflicted-b':
1351
lines_b.append(line)
1353
if state not in ('irrelevant', 'ghost-a', 'ghost-b',
1354
'killed-base', 'killed-both'):
1355
raise AssertionError(state)
1356
for struct in outstanding_struct():
1360
class WeaveMerge(PlanWeaveMerge):
1361
"""Weave merge that takes a VersionedFile and two versions as its input."""
1363
def __init__(self, versionedfile, ver_a, ver_b,
1364
a_marker=PlanWeaveMerge.A_MARKER, b_marker=PlanWeaveMerge.B_MARKER):
1365
plan = versionedfile.plan_merge(ver_a, ver_b)
1366
PlanWeaveMerge.__init__(self, plan, a_marker, b_marker)
1369
class VirtualVersionedFiles(VersionedFiles):
1370
"""Dummy implementation for VersionedFiles that uses other functions for
1371
obtaining fulltexts and parent maps.
1373
This is always on the bottom of the stack and uses string keys
1374
(rather than tuples) internally.
1377
def __init__(self, get_parent_map, get_lines):
1378
"""Create a VirtualVersionedFiles.
1380
:param get_parent_map: Same signature as Repository.get_parent_map.
1381
:param get_lines: Should return lines for specified key or None if
1384
super(VirtualVersionedFiles, self).__init__()
1385
self._get_parent_map = get_parent_map
1386
self._get_lines = get_lines
1388
def check(self, progressbar=None):
1389
"""See VersionedFiles.check.
1391
:note: Always returns True for VirtualVersionedFiles.
1395
def add_mpdiffs(self, records):
1396
"""See VersionedFiles.mpdiffs.
1398
:note: Not implemented for VirtualVersionedFiles.
1400
raise NotImplementedError(self.add_mpdiffs)
1402
def get_parent_map(self, keys):
1403
"""See VersionedFiles.get_parent_map."""
1404
return dict([((k,), tuple([(p,) for p in v]))
1405
for k,v in self._get_parent_map([k for (k,) in keys]).iteritems()])
1407
def get_sha1s(self, keys):
1408
"""See VersionedFiles.get_sha1s."""
1411
lines = self._get_lines(k)
1412
if lines is not None:
1413
if not isinstance(lines, list):
1414
raise AssertionError
1415
ret[(k,)] = osutils.sha_strings(lines)
1418
def get_record_stream(self, keys, ordering, include_delta_closure):
1419
"""See VersionedFiles.get_record_stream."""
1420
for (k,) in list(keys):
1421
lines = self._get_lines(k)
1422
if lines is not None:
1423
if not isinstance(lines, list):
1424
raise AssertionError
1425
yield FulltextContentFactory((k,), None,
1426
sha1=osutils.sha_strings(lines),
1427
text=''.join(lines))
1429
yield AbsentContentFactory((k,))
added
removed
bzrlib/versionedfile.py
