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 RecordingVersionedFileDsecorator 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 KeyMapper(object):
566
"""KeyMappers map between keys and underlying partitioned storage."""
569
"""Map key to an underlying storage identifier.
571
:param key: A key tuple e.g. ('file-id', 'revision-id').
572
:return: An underlying storage identifier, specific to the partitioning
575
raise NotImplementedError(self.map)
577
def unmap(self, partition_id):
578
"""Map a partitioned storage id back to a key prefix.
580
:param partition_id: The underlying partition id.
581
:return: As much of a key (or prefix) as is derivable from the partition
584
raise NotImplementedError(self.unmap)
587
class ConstantMapper(KeyMapper):
588
"""A key mapper that maps to a constant result."""
590
def __init__(self, result):
591
"""Create a ConstantMapper which will return result for all maps."""
592
self._result = result
595
"""See KeyMapper.map()."""
599
class URLEscapeMapper(KeyMapper):
600
"""Base class for use with transport backed storage.
602
This provides a map and unmap wrapper that respectively url escape and
603
unescape their outputs and inputs.
607
"""See KeyMapper.map()."""
608
return urllib.quote(self._map(key))
610
def unmap(self, partition_id):
611
"""See KeyMapper.unmap()."""
612
return self._unmap(urllib.unquote(partition_id))
615
class PrefixMapper(URLEscapeMapper):
616
"""A key mapper that extracts the first component of a key.
618
This mapper is for use with a transport based backend.
622
"""See KeyMapper.map()."""
625
def _unmap(self, partition_id):
626
"""See KeyMapper.unmap()."""
627
return (partition_id,)
630
class HashPrefixMapper(URLEscapeMapper):
631
"""A key mapper that combines the first component of a key with a hash.
633
This mapper is for use with a transport based backend.
637
"""See KeyMapper.map()."""
638
prefix = self._escape(key[0])
639
return "%02x/%s" % (adler32(prefix) & 0xff, prefix)
641
def _escape(self, prefix):
642
"""No escaping needed here."""
645
def _unmap(self, partition_id):
646
"""See KeyMapper.unmap()."""
647
return (self._unescape(osutils.basename(partition_id)),)
649
def _unescape(self, basename):
650
"""No unescaping needed for HashPrefixMapper."""
654
class HashEscapedPrefixMapper(HashPrefixMapper):
655
"""Combines the escaped first component of a key with a hash.
657
This mapper is for use with a transport based backend.
660
_safe = "abcdefghijklmnopqrstuvwxyz0123456789-_@,."
662
def _escape(self, prefix):
663
"""Turn a key element into a filesystem safe string.
665
This is similar to a plain urllib.quote, except
666
it uses specific safe characters, so that it doesn't
667
have to translate a lot of valid file ids.
669
# @ does not get escaped. This is because it is a valid
670
# filesystem character we use all the time, and it looks
671
# a lot better than seeing %40 all the time.
672
r = [((c in self._safe) and c or ('%%%02x' % ord(c)))
676
def _unescape(self, basename):
677
"""Escaped names are easily unescaped by urlutils."""
678
return urllib.unquote(basename)
681
def make_versioned_files_factory(versioned_file_factory, mapper):
682
"""Create a ThunkedVersionedFiles factory.
684
This will create a callable which when called creates a
685
ThunkedVersionedFiles on a transport, using mapper to access individual
686
versioned files, and versioned_file_factory to create each individual file.
688
def factory(transport):
689
return ThunkedVersionedFiles(transport, versioned_file_factory, mapper,
694
class VersionedFiles(object):
695
"""Storage for many versioned files.
697
This object allows a single keyspace for accessing the history graph and
698
contents of named bytestrings.
700
Currently no implementation allows the graph of different key prefixes to
701
intersect, but the API does allow such implementations in the future.
703
The keyspace is expressed via simple tuples. Any instance of VersionedFiles
704
may have a different length key-size, but that size will be constant for
705
all texts added to or retrieved from it. For instance, bzrlib uses
706
instances with a key-size of 2 for storing user files in a repository, with
707
the first element the fileid, and the second the version of that file.
709
The use of tuples allows a single code base to support several different
710
uses with only the mapping logic changing from instance to instance.
713
def add_lines(self, key, parents, lines, parent_texts=None,
714
left_matching_blocks=None, nostore_sha=None, random_id=False,
716
"""Add a text to the store.
718
:param key: The key tuple of the text to add.
719
:param parents: The parents key tuples of the text to add.
720
:param lines: A list of lines. Each line must be a bytestring. And all
721
of them except the last must be terminated with \n and contain no
722
other \n's. The last line may either contain no \n's or a single
723
terminating \n. If the lines list does meet this constraint the add
724
routine may error or may succeed - but you will be unable to read
725
the data back accurately. (Checking the lines have been split
726
correctly is expensive and extremely unlikely to catch bugs so it
727
is not done at runtime unless check_content is True.)
728
:param parent_texts: An optional dictionary containing the opaque
729
representations of some or all of the parents of version_id to
730
allow delta optimisations. VERY IMPORTANT: the texts must be those
731
returned by add_lines or data corruption can be caused.
732
:param left_matching_blocks: a hint about which areas are common
733
between the text and its left-hand-parent. The format is
734
the SequenceMatcher.get_matching_blocks format.
735
:param nostore_sha: Raise ExistingContent and do not add the lines to
736
the versioned file if the digest of the lines matches this.
737
:param random_id: If True a random id has been selected rather than
738
an id determined by some deterministic process such as a converter
739
from a foreign VCS. When True the backend may choose not to check
740
for uniqueness of the resulting key within the versioned file, so
741
this should only be done when the result is expected to be unique
743
:param check_content: If True, the lines supplied are verified to be
744
bytestrings that are correctly formed lines.
745
:return: The text sha1, the number of bytes in the text, and an opaque
746
representation of the inserted version which can be provided
747
back to future add_lines calls in the parent_texts dictionary.
749
raise NotImplementedError(self.add_lines)
751
def add_mpdiffs(self, records):
752
"""Add mpdiffs to this VersionedFile.
754
Records should be iterables of version, parents, expected_sha1,
755
mpdiff. mpdiff should be a MultiParent instance.
758
mpvf = multiparent.MultiMemoryVersionedFile()
760
for version, parent_ids, expected_sha1, mpdiff in records:
761
versions.append(version)
762
mpvf.add_diff(mpdiff, version, parent_ids)
763
needed_parents = set()
764
for version, parent_ids, expected_sha1, mpdiff in records:
765
needed_parents.update(p for p in parent_ids
766
if not mpvf.has_version(p))
767
# It seems likely that adding all the present parents as fulltexts can
768
# easily exhaust memory.
769
split_lines = osutils.split_lines
770
for record in self.get_record_stream(needed_parents, 'unordered',
772
if record.storage_kind == 'absent':
774
mpvf.add_version(split_lines(record.get_bytes_as('fulltext')),
776
for (key, parent_keys, expected_sha1, mpdiff), lines in\
777
zip(records, mpvf.get_line_list(versions)):
778
if len(parent_keys) == 1:
779
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
780
mpvf.get_diff(parent_keys[0]).num_lines()))
782
left_matching_blocks = None
783
version_sha1, _, version_text = self.add_lines(key,
784
parent_keys, lines, vf_parents,
785
left_matching_blocks=left_matching_blocks)
786
if version_sha1 != expected_sha1:
787
raise errors.VersionedFileInvalidChecksum(version)
788
vf_parents[key] = version_text
790
def annotate(self, key):
791
"""Return a list of (version-key, line) tuples for the text of key.
793
:raise RevisionNotPresent: If the key is not present.
795
raise NotImplementedError(self.annotate)
797
def check(self, progress_bar=None):
798
"""Check this object for integrity."""
799
raise NotImplementedError(self.check)
802
def check_not_reserved_id(version_id):
803
revision.check_not_reserved_id(version_id)
805
def _check_lines_not_unicode(self, lines):
806
"""Check that lines being added to a versioned file are not unicode."""
808
if line.__class__ is not str:
809
raise errors.BzrBadParameterUnicode("lines")
811
def _check_lines_are_lines(self, lines):
812
"""Check that the lines really are full lines without inline EOL."""
814
if '\n' in line[:-1]:
815
raise errors.BzrBadParameterContainsNewline("lines")
817
def get_parent_map(self, keys):
818
"""Get a map of the parents of keys.
820
:param keys: The keys to look up parents for.
821
:return: A mapping from keys to parents. Absent keys are absent from
824
raise NotImplementedError(self.get_parent_map)
826
def get_record_stream(self, keys, ordering, include_delta_closure):
827
"""Get a stream of records for keys.
829
:param keys: The keys to include.
830
:param ordering: Either 'unordered' or 'topological'. A topologically
831
sorted stream has compression parents strictly before their
833
:param include_delta_closure: If True then the closure across any
834
compression parents will be included (in the opaque data).
835
:return: An iterator of ContentFactory objects, each of which is only
836
valid until the iterator is advanced.
838
raise NotImplementedError(self.get_record_stream)
840
def get_sha1s(self, keys):
841
"""Get the sha1's of the texts for the given keys.
843
:param keys: The names of the keys to lookup
844
:return: a dict from key to sha1 digest. Keys of texts which are not
845
present in the store are not present in the returned
848
raise NotImplementedError(self.get_sha1s)
850
has_key = index._has_key_from_parent_map
852
def insert_record_stream(self, stream):
853
"""Insert a record stream into this container.
855
:param stream: A stream of records to insert.
857
:seealso VersionedFile.get_record_stream:
859
raise NotImplementedError
861
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
862
"""Iterate over the lines in the versioned files from keys.
864
This may return lines from other keys. Each item the returned
865
iterator yields is a tuple of a line and a text version that that line
866
is present in (not introduced in).
868
Ordering of results is in whatever order is most suitable for the
869
underlying storage format.
871
If a progress bar is supplied, it may be used to indicate progress.
872
The caller is responsible for cleaning up progress bars (because this
876
* Lines are normalised by the underlying store: they will all have \n
878
* Lines are returned in arbitrary order.
880
:return: An iterator over (line, key).
882
raise NotImplementedError(self.iter_lines_added_or_present_in_keys)
885
"""Return a iterable of the keys for all the contained texts."""
886
raise NotImplementedError(self.keys)
888
def make_mpdiffs(self, keys):
889
"""Create multiparent diffs for specified keys."""
890
keys_order = tuple(keys)
891
keys = frozenset(keys)
892
knit_keys = set(keys)
893
parent_map = self.get_parent_map(keys)
894
for parent_keys in parent_map.itervalues():
896
knit_keys.update(parent_keys)
897
missing_keys = keys - set(parent_map)
899
raise errors.RevisionNotPresent(list(missing_keys)[0], self)
900
# We need to filter out ghosts, because we can't diff against them.
901
maybe_ghosts = knit_keys - keys
902
ghosts = maybe_ghosts - set(self.get_parent_map(maybe_ghosts))
903
knit_keys.difference_update(ghosts)
905
split_lines = osutils.split_lines
906
for record in self.get_record_stream(knit_keys, 'topological', True):
907
lines[record.key] = split_lines(record.get_bytes_as('fulltext'))
908
# line_block_dict = {}
909
# for parent, blocks in record.extract_line_blocks():
910
# line_blocks[parent] = blocks
911
# line_blocks[record.key] = line_block_dict
913
for key in keys_order:
915
parents = parent_map[key] or []
916
# Note that filtering knit_keys can lead to a parent difference
917
# between the creation and the application of the mpdiff.
918
parent_lines = [lines[p] for p in parents if p in knit_keys]
919
if len(parent_lines) > 0:
920
left_parent_blocks = self._extract_blocks(key, parent_lines[0],
923
left_parent_blocks = None
924
diffs.append(multiparent.MultiParent.from_lines(target,
925
parent_lines, left_parent_blocks))
928
missing_keys = index._missing_keys_from_parent_map
930
def _extract_blocks(self, version_id, source, target):
934
class ThunkedVersionedFiles(VersionedFiles):
935
"""Storage for many versioned files thunked onto a 'VersionedFile' class.
937
This object allows a single keyspace for accessing the history graph and
938
contents of named bytestrings.
940
Currently no implementation allows the graph of different key prefixes to
941
intersect, but the API does allow such implementations in the future.
944
def __init__(self, transport, file_factory, mapper, is_locked):
945
"""Create a ThunkedVersionedFiles."""
946
self._transport = transport
947
self._file_factory = file_factory
948
self._mapper = mapper
949
self._is_locked = is_locked
951
def add_lines(self, key, parents, lines, parent_texts=None,
952
left_matching_blocks=None, nostore_sha=None, random_id=False,
954
"""See VersionedFiles.add_lines()."""
955
path = self._mapper.map(key)
957
parents = [parent[-1] for parent in parents]
958
vf = self._get_vf(path)
961
return vf.add_lines_with_ghosts(version_id, parents, lines,
962
parent_texts=parent_texts,
963
left_matching_blocks=left_matching_blocks,
964
nostore_sha=nostore_sha, random_id=random_id,
965
check_content=check_content)
966
except NotImplementedError:
967
return vf.add_lines(version_id, parents, lines,
968
parent_texts=parent_texts,
969
left_matching_blocks=left_matching_blocks,
970
nostore_sha=nostore_sha, random_id=random_id,
971
check_content=check_content)
972
except errors.NoSuchFile:
973
# parent directory may be missing, try again.
974
self._transport.mkdir(osutils.dirname(path))
976
return vf.add_lines_with_ghosts(version_id, parents, lines,
977
parent_texts=parent_texts,
978
left_matching_blocks=left_matching_blocks,
979
nostore_sha=nostore_sha, random_id=random_id,
980
check_content=check_content)
981
except NotImplementedError:
982
return vf.add_lines(version_id, parents, lines,
983
parent_texts=parent_texts,
984
left_matching_blocks=left_matching_blocks,
985
nostore_sha=nostore_sha, random_id=random_id,
986
check_content=check_content)
988
def annotate(self, key):
989
"""Return a list of (version-key, line) tuples for the text of key.
991
:raise RevisionNotPresent: If the key is not present.
994
path = self._mapper.map(prefix)
995
vf = self._get_vf(path)
996
origins = vf.annotate(key[-1])
998
for origin, line in origins:
999
result.append((prefix + (origin,), line))
1002
def check(self, progress_bar=None):
1003
"""See VersionedFiles.check()."""
1004
for prefix, vf in self._iter_all_components():
1007
def get_parent_map(self, keys):
1008
"""Get a map of the parents of keys.
1010
:param keys: The keys to look up parents for.
1011
:return: A mapping from keys to parents. Absent keys are absent from
1014
prefixes = self._partition_keys(keys)
1016
for prefix, suffixes in prefixes.items():
1017
path = self._mapper.map(prefix)
1018
vf = self._get_vf(path)
1019
parent_map = vf.get_parent_map(suffixes)
1020
for key, parents in parent_map.items():
1021
result[prefix + (key,)] = tuple(
1022
prefix + (parent,) for parent in parents)
1025
def _get_vf(self, path):
1026
if not self._is_locked():
1027
raise errors.ObjectNotLocked(self)
1028
return self._file_factory(path, self._transport, create=True,
1029
get_scope=lambda:None)
1031
def _partition_keys(self, keys):
1032
"""Turn keys into a dict of prefix:suffix_list."""
1035
prefix_keys = result.setdefault(key[:-1], [])
1036
prefix_keys.append(key[-1])
1039
def _get_all_prefixes(self):
1040
# Identify all key prefixes.
1041
# XXX: A bit hacky, needs polish.
1042
if type(self._mapper) == ConstantMapper:
1043
paths = [self._mapper.map(())]
1047
for quoted_relpath in self._transport.iter_files_recursive():
1048
path, ext = os.path.splitext(quoted_relpath)
1050
paths = list(relpaths)
1051
prefixes = [self._mapper.unmap(path) for path in paths]
1052
return zip(paths, prefixes)
1054
def get_record_stream(self, keys, ordering, include_delta_closure):
1055
"""See VersionedFiles.get_record_stream()."""
1056
# Ordering will be taken care of by each partitioned store; group keys
1059
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1060
suffixes = [(suffix,) for suffix in suffixes]
1061
for record in vf.get_record_stream(suffixes, ordering,
1062
include_delta_closure):
1063
if record.parents is not None:
1064
record.parents = tuple(
1065
prefix + parent for parent in record.parents)
1066
record.key = prefix + record.key
1069
def _iter_keys_vf(self, keys):
1070
prefixes = self._partition_keys(keys)
1072
for prefix, suffixes in prefixes.items():
1073
path = self._mapper.map(prefix)
1074
vf = self._get_vf(path)
1075
yield prefix, suffixes, vf
1077
def get_sha1s(self, keys):
1078
"""See VersionedFiles.get_sha1s()."""
1080
for prefix,suffixes, vf in self._iter_keys_vf(keys):
1081
vf_sha1s = vf.get_sha1s(suffixes)
1082
for suffix, sha1 in vf_sha1s.iteritems():
1083
sha1s[prefix + (suffix,)] = sha1
1086
def insert_record_stream(self, stream):
1087
"""Insert a record stream into this container.
1089
:param stream: A stream of records to insert.
1091
:seealso VersionedFile.get_record_stream:
1093
for record in stream:
1094
prefix = record.key[:-1]
1095
key = record.key[-1:]
1096
if record.parents is not None:
1097
parents = [parent[-1:] for parent in record.parents]
1100
thunk_record = AdapterFactory(key, parents, record)
1101
path = self._mapper.map(prefix)
1102
# Note that this parses the file many times; we can do better but
1103
# as this only impacts weaves in terms of performance, it is
1105
vf = self._get_vf(path)
1106
vf.insert_record_stream([thunk_record])
1108
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1109
"""Iterate over the lines in the versioned files from keys.
1111
This may return lines from other keys. Each item the returned
1112
iterator yields is a tuple of a line and a text version that that line
1113
is present in (not introduced in).
1115
Ordering of results is in whatever order is most suitable for the
1116
underlying storage format.
1118
If a progress bar is supplied, it may be used to indicate progress.
1119
The caller is responsible for cleaning up progress bars (because this
1123
* Lines are normalised by the underlying store: they will all have \n
1125
* Lines are returned in arbitrary order.
1127
:return: An iterator over (line, key).
1129
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1130
for line, version in vf.iter_lines_added_or_present_in_versions(suffixes):
1131
yield line, prefix + (version,)
1133
def _iter_all_components(self):
1134
for path, prefix in self._get_all_prefixes():
1135
yield prefix, self._get_vf(path)
1138
"""See VersionedFiles.keys()."""
1140
for prefix, vf in self._iter_all_components():
1141
for suffix in vf.versions():
1142
result.add(prefix + (suffix,))
1146
class _PlanMergeVersionedFile(VersionedFiles):
1147
"""A VersionedFile for uncommitted and committed texts.
1149
It is intended to allow merges to be planned with working tree texts.
1150
It implements only the small part of the VersionedFiles interface used by
1151
PlanMerge. It falls back to multiple versionedfiles for data not stored in
1152
_PlanMergeVersionedFile itself.
1154
:ivar: fallback_versionedfiles a list of VersionedFiles objects that can be
1155
queried for missing texts.
1158
def __init__(self, file_id):
1159
"""Create a _PlanMergeVersionedFile.
1161
:param file_id: Used with _PlanMerge code which is not yet fully
1162
tuple-keyspace aware.
1164
self._file_id = file_id
1165
# fallback locations
1166
self.fallback_versionedfiles = []
1167
# Parents for locally held keys.
1169
# line data for locally held keys.
1171
# key lookup providers
1172
self._providers = [DictParentsProvider(self._parents)]
1174
def plan_merge(self, ver_a, ver_b, base=None):
1175
"""See VersionedFile.plan_merge"""
1176
from bzrlib.merge import _PlanMerge
1178
return _PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge()
1179
old_plan = list(_PlanMerge(ver_a, base, self, (self._file_id,)).plan_merge())
1180
new_plan = list(_PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge())
1181
return _PlanMerge._subtract_plans(old_plan, new_plan)
1183
def plan_lca_merge(self, ver_a, ver_b, base=None):
1184
from bzrlib.merge import _PlanLCAMerge
1186
new_plan = _PlanLCAMerge(ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
1189
old_plan = _PlanLCAMerge(ver_a, base, self, (self._file_id,), graph).plan_merge()
1190
return _PlanLCAMerge._subtract_plans(list(old_plan), list(new_plan))
1192
def add_lines(self, key, parents, lines):
1193
"""See VersionedFiles.add_lines
1195
Lines are added locally, not to fallback versionedfiles. Also, ghosts
1196
are permitted. Only reserved ids are permitted.
1198
if type(key) is not tuple:
1199
raise TypeError(key)
1200
if not revision.is_reserved_id(key[-1]):
1201
raise ValueError('Only reserved ids may be used')
1203
raise ValueError('Parents may not be None')
1205
raise ValueError('Lines may not be None')
1206
self._parents[key] = tuple(parents)
1207
self._lines[key] = lines
1209
def get_record_stream(self, keys, ordering, include_delta_closure):
1212
if key in self._lines:
1213
lines = self._lines[key]
1214
parents = self._parents[key]
1216
yield FulltextContentFactory(key, parents, None,
1218
for versionedfile in self.fallback_versionedfiles:
1219
for record in versionedfile.get_record_stream(
1220
pending, 'unordered', True):
1221
if record.storage_kind == 'absent':
1224
pending.remove(record.key)
1228
# report absent entries
1230
yield AbsentContentFactory(key)
1232
def get_parent_map(self, keys):
1233
"""See VersionedFiles.get_parent_map"""
1234
# We create a new provider because a fallback may have been added.
1235
# If we make fallbacks private we can update a stack list and avoid
1236
# object creation thrashing.
1239
if revision.NULL_REVISION in keys:
1240
keys.remove(revision.NULL_REVISION)
1241
result[revision.NULL_REVISION] = ()
1242
self._providers = self._providers[:1] + self.fallback_versionedfiles
1244
_StackedParentsProvider(self._providers).get_parent_map(keys))
1245
for key, parents in result.iteritems():
1247
result[key] = (revision.NULL_REVISION,)
1251
class PlanWeaveMerge(TextMerge):
1252
"""Weave merge that takes a plan as its input.
1254
This exists so that VersionedFile.plan_merge is implementable.
1255
Most callers will want to use WeaveMerge instead.
1258
def __init__(self, plan, a_marker=TextMerge.A_MARKER,
1259
b_marker=TextMerge.B_MARKER):
1260
TextMerge.__init__(self, a_marker, b_marker)
1263
def _merge_struct(self):
1268
def outstanding_struct():
1269
if not lines_a and not lines_b:
1271
elif ch_a and not ch_b:
1274
elif ch_b and not ch_a:
1276
elif lines_a == lines_b:
1279
yield (lines_a, lines_b)
1281
# We previously considered either 'unchanged' or 'killed-both' lines
1282
# to be possible places to resynchronize. However, assuming agreement
1283
# on killed-both lines may be too aggressive. -- mbp 20060324
1284
for state, line in self.plan:
1285
if state == 'unchanged':
1286
# resync and flush queued conflicts changes if any
1287
for struct in outstanding_struct():
1293
if state == 'unchanged':
1296
elif state == 'killed-a':
1298
lines_b.append(line)
1299
elif state == 'killed-b':
1301
lines_a.append(line)
1302
elif state == 'new-a':
1304
lines_a.append(line)
1305
elif state == 'new-b':
1307
lines_b.append(line)
1308
elif state == 'conflicted-a':
1310
lines_a.append(line)
1311
elif state == 'conflicted-b':
1313
lines_b.append(line)
1315
if state not in ('irrelevant', 'ghost-a', 'ghost-b',
1316
'killed-base', 'killed-both'):
1317
raise AssertionError(state)
1318
for struct in outstanding_struct():
1322
class WeaveMerge(PlanWeaveMerge):
1323
"""Weave merge that takes a VersionedFile and two versions as its input."""
1325
def __init__(self, versionedfile, ver_a, ver_b,
1326
a_marker=PlanWeaveMerge.A_MARKER, b_marker=PlanWeaveMerge.B_MARKER):
1327
plan = versionedfile.plan_merge(ver_a, ver_b)
1328
PlanWeaveMerge.__init__(self, plan, a_marker, b_marker)
1331
class VirtualVersionedFiles(VersionedFiles):
1332
"""Dummy implementation for VersionedFiles that uses other functions for
1333
obtaining fulltexts and parent maps.
1335
This is always on the bottom of the stack and uses string keys
1336
(rather than tuples) internally.
1339
def __init__(self, get_parent_map, get_lines):
1340
"""Create a VirtualVersionedFiles.
1342
:param get_parent_map: Same signature as Repository.get_parent_map.
1343
:param get_lines: Should return lines for specified key or None if
1346
super(VirtualVersionedFiles, self).__init__()
1347
self._get_parent_map = get_parent_map
1348
self._get_lines = get_lines
1350
def check(self, progressbar=None):
1351
"""See VersionedFiles.check.
1353
:note: Always returns True for VirtualVersionedFiles.
1357
def add_mpdiffs(self, records):
1358
"""See VersionedFiles.mpdiffs.
1360
:note: Not implemented for VirtualVersionedFiles.
1362
raise NotImplementedError(self.add_mpdiffs)
1364
def get_parent_map(self, keys):
1365
"""See VersionedFiles.get_parent_map."""
1366
return dict([((k,), tuple([(p,) for p in v]))
1367
for k,v in self._get_parent_map([k for (k,) in keys]).iteritems()])
1369
def get_sha1s(self, keys):
1370
"""See VersionedFiles.get_sha1s."""
1373
lines = self._get_lines(k)
1374
if lines is not None:
1375
if not isinstance(lines, list):
1376
raise AssertionError
1377
ret[(k,)] = osutils.sha_strings(lines)
1380
def get_record_stream(self, keys, ordering, include_delta_closure):
1381
"""See VersionedFiles.get_record_stream."""
1382
for (k,) in list(keys):
1383
lines = self._get_lines(k)
1384
if lines is not None:
1385
if not isinstance(lines, list):
1386
raise AssertionError
1387
yield FulltextContentFactory((k,), None,
1388
sha1=osutils.sha_strings(lines),
1389
text=''.join(lines))
1391
yield AbsentContentFactory((k,))
added
removed
bzrlib/versionedfile.py
