1
# Copyright (C) 2005, 2006 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
26
from zlib import adler32
28
from bzrlib.lazy_import import lazy_import
29
lazy_import(globals(), """
39
from bzrlib.graph import DictParentsProvider, Graph, _StackedParentsProvider
40
from bzrlib.transport.memory import MemoryTransport
42
from bzrlib.inter import InterObject
43
from bzrlib.registry import Registry
44
from bzrlib.symbol_versioning import *
45
from bzrlib.textmerge import TextMerge
48
adapter_registry = Registry()
49
adapter_registry.register_lazy(('knit-delta-gz', 'fulltext'), 'bzrlib.knit',
50
'DeltaPlainToFullText')
51
adapter_registry.register_lazy(('knit-ft-gz', 'fulltext'), 'bzrlib.knit',
53
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'knit-delta-gz'),
54
'bzrlib.knit', 'DeltaAnnotatedToUnannotated')
55
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'fulltext'),
56
'bzrlib.knit', 'DeltaAnnotatedToFullText')
57
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'knit-ft-gz'),
58
'bzrlib.knit', 'FTAnnotatedToUnannotated')
59
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'fulltext'),
60
'bzrlib.knit', 'FTAnnotatedToFullText')
63
class ContentFactory(object):
64
"""Abstract interface for insertion and retrieval from a VersionedFile.
66
:ivar sha1: None, or the sha1 of the content fulltext.
67
:ivar storage_kind: The native storage kind of this factory. One of
68
'mpdiff', 'knit-annotated-ft', 'knit-annotated-delta', 'knit-ft',
69
'knit-delta', 'fulltext', 'knit-annotated-ft-gz',
70
'knit-annotated-delta-gz', 'knit-ft-gz', 'knit-delta-gz'.
71
:ivar key: The key of this content. Each key is a tuple with a single
73
:ivar parents: A tuple of parent keys for self.key. If the object has
74
no parent information, None (as opposed to () for an empty list of
79
"""Create a ContentFactory."""
81
self.storage_kind = None
86
class FulltextContentFactory(ContentFactory):
87
"""Static data content factory.
89
This takes a fulltext when created and just returns that during
90
get_bytes_as('fulltext').
92
:ivar sha1: None, or the sha1 of the content fulltext.
93
:ivar storage_kind: The native storage kind of this factory. Always
95
:ivar key: The key of this content. Each key is a tuple with a single
97
:ivar parents: A tuple of parent keys for self.key. If the object has
98
no parent information, None (as opposed to () for an empty list of
102
def __init__(self, key, parents, sha1, text):
103
"""Create a ContentFactory."""
105
self.storage_kind = 'fulltext'
107
self.parents = parents
110
def get_bytes_as(self, storage_kind):
111
if storage_kind == self.storage_kind:
113
raise errors.UnavailableRepresentation(self.key, storage_kind,
117
class AbsentContentFactory(ContentFactory):
118
"""A placeholder content factory for unavailable texts.
121
:ivar storage_kind: 'absent'.
122
:ivar key: The key of this content. Each key is a tuple with a single
127
def __init__(self, key):
128
"""Create a ContentFactory."""
130
self.storage_kind = 'absent'
135
class AdapterFactory(ContentFactory):
136
"""A content factory to adapt between key prefix's."""
138
def __init__(self, key, parents, adapted):
139
"""Create an adapter factory instance."""
141
self.parents = parents
142
self._adapted = adapted
144
def __getattr__(self, attr):
145
"""Return a member from the adapted object."""
146
if attr in ('key', 'parents'):
147
return self.__dict__[attr]
149
return getattr(self._adapted, attr)
152
def filter_absent(record_stream):
153
"""Adapt a record stream to remove absent records."""
154
for record in record_stream:
155
if record.storage_kind != 'absent':
159
class VersionedFile(object):
160
"""Versioned text file storage.
162
A versioned file manages versions of line-based text files,
163
keeping track of the originating version for each line.
165
To clients the "lines" of the file are represented as a list of
166
strings. These strings will typically have terminal newline
167
characters, but this is not required. In particular files commonly
168
do not have a newline at the end of the file.
170
Texts are identified by a version-id string.
174
def check_not_reserved_id(version_id):
175
revision.check_not_reserved_id(version_id)
177
def copy_to(self, name, transport):
178
"""Copy this versioned file to name on transport."""
179
raise NotImplementedError(self.copy_to)
181
def get_record_stream(self, versions, ordering, include_delta_closure):
182
"""Get a stream of records for versions.
184
:param versions: The versions to include. Each version is a tuple
186
:param ordering: Either 'unordered' or 'topological'. A topologically
187
sorted stream has compression parents strictly before their
189
:param include_delta_closure: If True then the closure across any
190
compression parents will be included (in the data content of the
191
stream, not in the emitted records). This guarantees that
192
'fulltext' can be used successfully on every record.
193
:return: An iterator of ContentFactory objects, each of which is only
194
valid until the iterator is advanced.
196
raise NotImplementedError(self.get_record_stream)
198
def has_version(self, version_id):
199
"""Returns whether version is present."""
200
raise NotImplementedError(self.has_version)
202
def insert_record_stream(self, stream):
203
"""Insert a record stream into this versioned file.
205
:param stream: A stream of records to insert.
207
:seealso VersionedFile.get_record_stream:
209
raise NotImplementedError
211
def add_lines(self, version_id, parents, lines, parent_texts=None,
212
left_matching_blocks=None, nostore_sha=None, random_id=False,
214
"""Add a single text on top of the versioned file.
216
Must raise RevisionAlreadyPresent if the new version is
217
already present in file history.
219
Must raise RevisionNotPresent if any of the given parents are
220
not present in file history.
222
:param lines: A list of lines. Each line must be a bytestring. And all
223
of them except the last must be terminated with \n and contain no
224
other \n's. The last line may either contain no \n's or a single
225
terminated \n. If the lines list does meet this constraint the add
226
routine may error or may succeed - but you will be unable to read
227
the data back accurately. (Checking the lines have been split
228
correctly is expensive and extremely unlikely to catch bugs so it
229
is not done at runtime unless check_content is True.)
230
:param parent_texts: An optional dictionary containing the opaque
231
representations of some or all of the parents of version_id to
232
allow delta optimisations. VERY IMPORTANT: the texts must be those
233
returned by add_lines or data corruption can be caused.
234
:param left_matching_blocks: a hint about which areas are common
235
between the text and its left-hand-parent. The format is
236
the SequenceMatcher.get_matching_blocks format.
237
:param nostore_sha: Raise ExistingContent and do not add the lines to
238
the versioned file if the digest of the lines matches this.
239
:param random_id: If True a random id has been selected rather than
240
an id determined by some deterministic process such as a converter
241
from a foreign VCS. When True the backend may choose not to check
242
for uniqueness of the resulting key within the versioned file, so
243
this should only be done when the result is expected to be unique
245
:param check_content: If True, the lines supplied are verified to be
246
bytestrings that are correctly formed lines.
247
:return: The text sha1, the number of bytes in the text, and an opaque
248
representation of the inserted version which can be provided
249
back to future add_lines calls in the parent_texts dictionary.
251
self._check_write_ok()
252
return self._add_lines(version_id, parents, lines, parent_texts,
253
left_matching_blocks, nostore_sha, random_id, check_content)
255
def _add_lines(self, version_id, parents, lines, parent_texts,
256
left_matching_blocks, nostore_sha, random_id, check_content):
257
"""Helper to do the class specific add_lines."""
258
raise NotImplementedError(self.add_lines)
260
def add_lines_with_ghosts(self, version_id, parents, lines,
261
parent_texts=None, nostore_sha=None, random_id=False,
262
check_content=True, left_matching_blocks=None):
263
"""Add lines to the versioned file, allowing ghosts to be present.
265
This takes the same parameters as add_lines and returns the same.
267
self._check_write_ok()
268
return self._add_lines_with_ghosts(version_id, parents, lines,
269
parent_texts, nostore_sha, random_id, check_content, left_matching_blocks)
271
def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts,
272
nostore_sha, random_id, check_content, left_matching_blocks):
273
"""Helper to do class specific add_lines_with_ghosts."""
274
raise NotImplementedError(self.add_lines_with_ghosts)
276
def check(self, progress_bar=None):
277
"""Check the versioned file for integrity."""
278
raise NotImplementedError(self.check)
280
def _check_lines_not_unicode(self, lines):
281
"""Check that lines being added to a versioned file are not unicode."""
283
if line.__class__ is not str:
284
raise errors.BzrBadParameterUnicode("lines")
286
def _check_lines_are_lines(self, lines):
287
"""Check that the lines really are full lines without inline EOL."""
289
if '\n' in line[:-1]:
290
raise errors.BzrBadParameterContainsNewline("lines")
292
def get_format_signature(self):
293
"""Get a text description of the data encoding in this file.
297
raise NotImplementedError(self.get_format_signature)
299
def make_mpdiffs(self, version_ids):
300
"""Create multiparent diffs for specified versions."""
301
knit_versions = set()
302
knit_versions.update(version_ids)
303
parent_map = self.get_parent_map(version_ids)
304
for version_id in version_ids:
306
knit_versions.update(parent_map[version_id])
308
raise errors.RevisionNotPresent(version_id, self)
309
# We need to filter out ghosts, because we can't diff against them.
310
knit_versions = set(self.get_parent_map(knit_versions).keys())
311
lines = dict(zip(knit_versions,
312
self._get_lf_split_line_list(knit_versions)))
314
for version_id in version_ids:
315
target = lines[version_id]
317
parents = [lines[p] for p in parent_map[version_id] if p in
320
# I don't know how this could ever trigger.
321
# parent_map[version_id] was already triggered in the previous
322
# for loop, and lines[p] has the 'if p in knit_versions' check,
323
# so we again won't have a KeyError.
324
raise errors.RevisionNotPresent(version_id, self)
326
left_parent_blocks = self._extract_blocks(version_id,
329
left_parent_blocks = None
330
diffs.append(multiparent.MultiParent.from_lines(target, parents,
334
def _extract_blocks(self, version_id, source, target):
337
def add_mpdiffs(self, records):
338
"""Add mpdiffs to this VersionedFile.
340
Records should be iterables of version, parents, expected_sha1,
341
mpdiff. mpdiff should be a MultiParent instance.
343
# Does this need to call self._check_write_ok()? (IanC 20070919)
345
mpvf = multiparent.MultiMemoryVersionedFile()
347
for version, parent_ids, expected_sha1, mpdiff in records:
348
versions.append(version)
349
mpvf.add_diff(mpdiff, version, parent_ids)
350
needed_parents = set()
351
for version, parent_ids, expected_sha1, mpdiff in records:
352
needed_parents.update(p for p in parent_ids
353
if not mpvf.has_version(p))
354
present_parents = set(self.get_parent_map(needed_parents).keys())
355
for parent_id, lines in zip(present_parents,
356
self._get_lf_split_line_list(present_parents)):
357
mpvf.add_version(lines, parent_id, [])
358
for (version, parent_ids, expected_sha1, mpdiff), lines in\
359
zip(records, mpvf.get_line_list(versions)):
360
if len(parent_ids) == 1:
361
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
362
mpvf.get_diff(parent_ids[0]).num_lines()))
364
left_matching_blocks = None
366
_, _, version_text = self.add_lines_with_ghosts(version,
367
parent_ids, lines, vf_parents,
368
left_matching_blocks=left_matching_blocks)
369
except NotImplementedError:
370
# The vf can't handle ghosts, so add lines normally, which will
371
# (reasonably) fail if there are ghosts in the data.
372
_, _, version_text = self.add_lines(version,
373
parent_ids, lines, vf_parents,
374
left_matching_blocks=left_matching_blocks)
375
vf_parents[version] = version_text
376
sha1s = self.get_sha1s(versions)
377
for version, parent_ids, expected_sha1, mpdiff in records:
378
if expected_sha1 != sha1s[version]:
379
raise errors.VersionedFileInvalidChecksum(version)
381
def get_text(self, version_id):
382
"""Return version contents as a text string.
384
Raises RevisionNotPresent if version is not present in
387
return ''.join(self.get_lines(version_id))
388
get_string = get_text
390
def get_texts(self, version_ids):
391
"""Return the texts of listed versions as a list of strings.
393
Raises RevisionNotPresent if version is not present in
396
return [''.join(self.get_lines(v)) for v in version_ids]
398
def get_lines(self, version_id):
399
"""Return version contents as a sequence of lines.
401
Raises RevisionNotPresent if version is not present in
404
raise NotImplementedError(self.get_lines)
406
def _get_lf_split_line_list(self, version_ids):
407
return [StringIO(t).readlines() for t in self.get_texts(version_ids)]
409
def get_ancestry(self, version_ids, topo_sorted=True):
410
"""Return a list of all ancestors of given version(s). This
411
will not include the null revision.
413
This list will not be topologically sorted if topo_sorted=False is
416
Must raise RevisionNotPresent if any of the given versions are
417
not present in file history."""
418
if isinstance(version_ids, basestring):
419
version_ids = [version_ids]
420
raise NotImplementedError(self.get_ancestry)
422
def get_ancestry_with_ghosts(self, version_ids):
423
"""Return a list of all ancestors of given version(s). This
424
will not include the null revision.
426
Must raise RevisionNotPresent if any of the given versions are
427
not present in file history.
429
Ghosts that are known about will be included in ancestry list,
430
but are not explicitly marked.
432
raise NotImplementedError(self.get_ancestry_with_ghosts)
434
def get_parent_map(self, version_ids):
435
"""Get a map of the parents of version_ids.
437
:param version_ids: The version ids to look up parents for.
438
:return: A mapping from version id to parents.
440
raise NotImplementedError(self.get_parent_map)
442
def get_parents_with_ghosts(self, version_id):
443
"""Return version names for parents of version_id.
445
Will raise RevisionNotPresent if version_id is not present
448
Ghosts that are known about will be included in the parent list,
449
but are not explicitly marked.
452
return list(self.get_parent_map([version_id])[version_id])
454
raise errors.RevisionNotPresent(version_id, self)
456
def annotate(self, version_id):
457
"""Return a list of (version-id, line) tuples for version_id.
459
:raise RevisionNotPresent: If the given version is
460
not present in file history.
462
raise NotImplementedError(self.annotate)
464
def iter_lines_added_or_present_in_versions(self, version_ids=None,
466
"""Iterate over the lines in the versioned file from version_ids.
468
This may return lines from other versions. Each item the returned
469
iterator yields is a tuple of a line and a text version that that line
470
is present in (not introduced in).
472
Ordering of results is in whatever order is most suitable for the
473
underlying storage format.
475
If a progress bar is supplied, it may be used to indicate progress.
476
The caller is responsible for cleaning up progress bars (because this
479
NOTES: Lines are normalised: they will all have \n terminators.
480
Lines are returned in arbitrary order.
482
:return: An iterator over (line, version_id).
484
raise NotImplementedError(self.iter_lines_added_or_present_in_versions)
486
def plan_merge(self, ver_a, ver_b):
487
"""Return pseudo-annotation indicating how the two versions merge.
489
This is computed between versions a and b and their common
492
Weave lines present in none of them are skipped entirely.
495
killed-base Dead in base revision
496
killed-both Killed in each revision
499
unchanged Alive in both a and b (possibly created in both)
502
ghost-a Killed in a, unborn in b
503
ghost-b Killed in b, unborn in a
504
irrelevant Not in either revision
506
raise NotImplementedError(VersionedFile.plan_merge)
508
def weave_merge(self, plan, a_marker=TextMerge.A_MARKER,
509
b_marker=TextMerge.B_MARKER):
510
return PlanWeaveMerge(plan, a_marker, b_marker).merge_lines()[0]
513
class RecordingVersionedFilesDecorator(object):
514
"""A minimal versioned files that records calls made on it.
516
Only enough methods have been added to support tests using it to date.
518
:ivar calls: A list of the calls made; can be reset at any time by
522
def __init__(self, backing_vf):
523
"""Create a RecordingVersionedFileDsecorator decorating backing_vf.
525
:param backing_vf: The versioned file to answer all methods.
527
self._backing_vf = backing_vf
530
def add_lines(self, key, parents, lines, parent_texts=None,
531
left_matching_blocks=None, nostore_sha=None, random_id=False,
533
self.calls.append(("add_lines", key, parents, lines, parent_texts,
534
left_matching_blocks, nostore_sha, random_id, check_content))
535
return self._backing_vf.add_lines(key, parents, lines, parent_texts,
536
left_matching_blocks, nostore_sha, random_id, check_content)
538
def get_parent_map(self, keys):
539
self.calls.append(("get_parent_map", copy(keys)))
540
return self._backing_vf.get_parent_map(keys)
542
def get_record_stream(self, keys, sort_order, include_delta_closure):
543
self.calls.append(("get_record_stream", list(keys), sort_order,
544
include_delta_closure))
545
return self._backing_vf.get_record_stream(keys, sort_order,
546
include_delta_closure)
548
def get_sha1s(self, keys):
549
self.calls.append(("get_sha1s", copy(keys)))
550
return self._backing_vf.get_sha1s(keys)
552
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
553
self.calls.append(("iter_lines_added_or_present_in_keys", copy(keys)))
554
return self._backing_vf.iter_lines_added_or_present_in_keys(keys, pb=pb)
557
self.calls.append(("keys",))
558
return self._backing_vf.keys()
561
class KeyMapper(object):
562
"""KeyMappers map between keys and underlying partitioned storage."""
565
"""Map key to an underlying storage identifier.
567
:param key: A key tuple e.g. ('file-id', 'revision-id').
568
:return: An underlying storage identifier, specific to the partitioning
571
raise NotImplementedError(self.map)
573
def unmap(self, partition_id):
574
"""Map a partitioned storage id back to a key prefix.
576
:param partition_id: The underlying partition id.
577
:return: As much of a key (or prefix) as is derivable from the partition
580
raise NotImplementedError(self.unmap)
583
class ConstantMapper(KeyMapper):
584
"""A key mapper that maps to a constant result."""
586
def __init__(self, result):
587
"""Create a ConstantMapper which will return result for all maps."""
588
self._result = result
591
"""See KeyMapper.map()."""
595
class URLEscapeMapper(KeyMapper):
596
"""Base class for use with transport backed storage.
598
This provides a map and unmap wrapper that respectively url escape and
599
unescape their outputs and inputs.
603
"""See KeyMapper.map()."""
604
return urllib.quote(self._map(key))
606
def unmap(self, partition_id):
607
"""See KeyMapper.unmap()."""
608
return self._unmap(urllib.unquote(partition_id))
611
class PrefixMapper(URLEscapeMapper):
612
"""A key mapper that extracts the first component of a key.
614
This mapper is for use with a transport based backend.
618
"""See KeyMapper.map()."""
621
def _unmap(self, partition_id):
622
"""See KeyMapper.unmap()."""
623
return (partition_id,)
626
class HashPrefixMapper(URLEscapeMapper):
627
"""A key mapper that combines the first component of a key with a hash.
629
This mapper is for use with a transport based backend.
633
"""See KeyMapper.map()."""
634
prefix = self._escape(key[0])
635
return "%02x/%s" % (adler32(prefix) & 0xff, prefix)
637
def _escape(self, prefix):
638
"""No escaping needed here."""
641
def _unmap(self, partition_id):
642
"""See KeyMapper.unmap()."""
643
return (self._unescape(osutils.basename(partition_id)),)
645
def _unescape(self, basename):
646
"""No unescaping needed for HashPrefixMapper."""
650
class HashEscapedPrefixMapper(HashPrefixMapper):
651
"""Combines the escaped first component of a key with a hash.
653
This mapper is for use with a transport based backend.
656
_safe = "abcdefghijklmnopqrstuvwxyz0123456789-_@,."
658
def _escape(self, prefix):
659
"""Turn a key element into a filesystem safe string.
661
This is similar to a plain urllib.quote, except
662
it uses specific safe characters, so that it doesn't
663
have to translate a lot of valid file ids.
665
# @ does not get escaped. This is because it is a valid
666
# filesystem character we use all the time, and it looks
667
# a lot better than seeing %40 all the time.
668
r = [((c in self._safe) and c or ('%%%02x' % ord(c)))
672
def _unescape(self, basename):
673
"""Escaped names are easily unescaped by urlutils."""
674
return urllib.unquote(basename)
677
def make_versioned_files_factory(versioned_file_factory, mapper):
678
"""Create a ThunkedVersionedFiles factory.
680
This will create a callable which when called creates a
681
ThunkedVersionedFiles on a transport, using mapper to access individual
682
versioned files, and versioned_file_factory to create each individual file.
684
def factory(transport):
685
return ThunkedVersionedFiles(transport, versioned_file_factory, mapper,
690
class VersionedFiles(object):
691
"""Storage for many versioned files.
693
This object allows a single keyspace for accessing the history graph and
694
contents of named bytestrings.
696
Currently no implementation allows the graph of different key prefixes to
697
intersect, but the API does allow such implementations in the future.
699
The keyspace is expressed via simple tuples. Any instance of VersionedFiles
700
may have a different length key-size, but that size will be constant for
701
all texts added to or retrieved from it. For instance, bzrlib uses
702
instances with a key-size of 2 for storing user files in a repository, with
703
the first element the fileid, and the second the version of that file.
705
The use of tuples allows a single code base to support several different
706
uses with only the mapping logic changing from instance to instance.
709
def add_lines(self, key, parents, lines, parent_texts=None,
710
left_matching_blocks=None, nostore_sha=None, random_id=False,
712
"""Add a text to the store.
714
:param key: The key tuple of the text to add.
715
:param parents: The parents key tuples of the text to add.
716
:param lines: A list of lines. Each line must be a bytestring. And all
717
of them except the last must be terminated with \n and contain no
718
other \n's. The last line may either contain no \n's or a single
719
terminating \n. If the lines list does meet this constraint the add
720
routine may error or may succeed - but you will be unable to read
721
the data back accurately. (Checking the lines have been split
722
correctly is expensive and extremely unlikely to catch bugs so it
723
is not done at runtime unless check_content is True.)
724
:param parent_texts: An optional dictionary containing the opaque
725
representations of some or all of the parents of version_id to
726
allow delta optimisations. VERY IMPORTANT: the texts must be those
727
returned by add_lines or data corruption can be caused.
728
:param left_matching_blocks: a hint about which areas are common
729
between the text and its left-hand-parent. The format is
730
the SequenceMatcher.get_matching_blocks format.
731
:param nostore_sha: Raise ExistingContent and do not add the lines to
732
the versioned file if the digest of the lines matches this.
733
:param random_id: If True a random id has been selected rather than
734
an id determined by some deterministic process such as a converter
735
from a foreign VCS. When True the backend may choose not to check
736
for uniqueness of the resulting key within the versioned file, so
737
this should only be done when the result is expected to be unique
739
:param check_content: If True, the lines supplied are verified to be
740
bytestrings that are correctly formed lines.
741
:return: The text sha1, the number of bytes in the text, and an opaque
742
representation of the inserted version which can be provided
743
back to future add_lines calls in the parent_texts dictionary.
745
raise NotImplementedError(self.add_lines)
747
def add_mpdiffs(self, records):
748
"""Add mpdiffs to this VersionedFile.
750
Records should be iterables of version, parents, expected_sha1,
751
mpdiff. mpdiff should be a MultiParent instance.
754
mpvf = multiparent.MultiMemoryVersionedFile()
756
for version, parent_ids, expected_sha1, mpdiff in records:
757
versions.append(version)
758
mpvf.add_diff(mpdiff, version, parent_ids)
759
needed_parents = set()
760
for version, parent_ids, expected_sha1, mpdiff in records:
761
needed_parents.update(p for p in parent_ids
762
if not mpvf.has_version(p))
763
# It seems likely that adding all the present parents as fulltexts can
764
# easily exhaust memory.
765
split_lines = osutils.split_lines
766
for record in self.get_record_stream(needed_parents, 'unordered',
768
if record.storage_kind == 'absent':
770
mpvf.add_version(split_lines(record.get_bytes_as('fulltext')),
772
for (key, parent_keys, expected_sha1, mpdiff), lines in\
773
zip(records, mpvf.get_line_list(versions)):
774
if len(parent_keys) == 1:
775
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
776
mpvf.get_diff(parent_keys[0]).num_lines()))
778
left_matching_blocks = None
779
version_sha1, _, version_text = self.add_lines(key,
780
parent_keys, lines, vf_parents,
781
left_matching_blocks=left_matching_blocks)
782
if version_sha1 != expected_sha1:
783
raise errors.VersionedFileInvalidChecksum(version)
784
vf_parents[key] = version_text
786
def annotate(self, key):
787
"""Return a list of (version-key, line) tuples for the text of key.
789
:raise RevisionNotPresent: If the key is not present.
791
raise NotImplementedError(self.annotate)
793
def check(self, progress_bar=None):
794
"""Check this object for integrity."""
795
raise NotImplementedError(self.check)
798
def check_not_reserved_id(version_id):
799
revision.check_not_reserved_id(version_id)
801
def _check_lines_not_unicode(self, lines):
802
"""Check that lines being added to a versioned file are not unicode."""
804
if line.__class__ is not str:
805
raise errors.BzrBadParameterUnicode("lines")
807
def _check_lines_are_lines(self, lines):
808
"""Check that the lines really are full lines without inline EOL."""
810
if '\n' in line[:-1]:
811
raise errors.BzrBadParameterContainsNewline("lines")
813
def get_parent_map(self, keys):
814
"""Get a map of the parents of keys.
816
:param keys: The keys to look up parents for.
817
:return: A mapping from keys to parents. Absent keys are absent from
820
raise NotImplementedError(self.get_parent_map)
822
def get_record_stream(self, keys, ordering, include_delta_closure):
823
"""Get a stream of records for keys.
825
:param keys: The keys to include.
826
:param ordering: Either 'unordered' or 'topological'. A topologically
827
sorted stream has compression parents strictly before their
829
:param include_delta_closure: If True then the closure across any
830
compression parents will be included (in the opaque data).
831
:return: An iterator of ContentFactory objects, each of which is only
832
valid until the iterator is advanced.
834
raise NotImplementedError(self.get_record_stream)
836
def get_sha1s(self, keys):
837
"""Get the sha1's of the texts for the given keys.
839
:param keys: The names of the keys to lookup
840
:return: a dict from key to sha1 digest. Keys of texts which are not
841
present in the store are not present in the returned
844
raise NotImplementedError(self.get_sha1s)
846
def insert_record_stream(self, stream):
847
"""Insert a record stream into this container.
849
:param stream: A stream of records to insert.
851
:seealso VersionedFile.get_record_stream:
853
raise NotImplementedError
855
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
856
"""Iterate over the lines in the versioned files from keys.
858
This may return lines from other keys. Each item the returned
859
iterator yields is a tuple of a line and a text version that that line
860
is present in (not introduced in).
862
Ordering of results is in whatever order is most suitable for the
863
underlying storage format.
865
If a progress bar is supplied, it may be used to indicate progress.
866
The caller is responsible for cleaning up progress bars (because this
870
* Lines are normalised by the underlying store: they will all have \n
872
* Lines are returned in arbitrary order.
874
:return: An iterator over (line, key).
876
raise NotImplementedError(self.iter_lines_added_or_present_in_keys)
879
"""Return a iterable of the keys for all the contained texts."""
880
raise NotImplementedError(self.keys)
882
def make_mpdiffs(self, keys):
883
"""Create multiparent diffs for specified keys."""
884
keys_order = tuple(keys)
885
keys = frozenset(keys)
886
knit_keys = set(keys)
887
parent_map = self.get_parent_map(keys)
888
for parent_keys in parent_map.itervalues():
890
knit_keys.update(parent_keys)
891
missing_keys = keys - set(parent_map)
893
raise errors.RevisionNotPresent(missing_keys.pop(), self)
894
# We need to filter out ghosts, because we can't diff against them.
895
maybe_ghosts = knit_keys - keys
896
ghosts = maybe_ghosts - set(self.get_parent_map(maybe_ghosts))
897
knit_keys.difference_update(ghosts)
899
split_lines = osutils.split_lines
900
for record in self.get_record_stream(knit_keys, 'topological', True):
901
lines[record.key] = split_lines(record.get_bytes_as('fulltext'))
902
# line_block_dict = {}
903
# for parent, blocks in record.extract_line_blocks():
904
# line_blocks[parent] = blocks
905
# line_blocks[record.key] = line_block_dict
907
for key in keys_order:
909
parents = parent_map[key] or []
910
# Note that filtering knit_keys can lead to a parent difference
911
# between the creation and the application of the mpdiff.
912
parent_lines = [lines[p] for p in parents if p in knit_keys]
913
if len(parent_lines) > 0:
914
left_parent_blocks = self._extract_blocks(key, parent_lines[0],
917
left_parent_blocks = None
918
diffs.append(multiparent.MultiParent.from_lines(target,
919
parent_lines, left_parent_blocks))
922
def _extract_blocks(self, version_id, source, target):
926
class ThunkedVersionedFiles(VersionedFiles):
927
"""Storage for many versioned files thunked onto a 'VersionedFile' class.
929
This object allows a single keyspace for accessing the history graph and
930
contents of named bytestrings.
932
Currently no implementation allows the graph of different key prefixes to
933
intersect, but the API does allow such implementations in the future.
936
def __init__(self, transport, file_factory, mapper, is_locked):
937
"""Create a ThunkedVersionedFiles."""
938
self._transport = transport
939
self._file_factory = file_factory
940
self._mapper = mapper
941
self._is_locked = is_locked
943
def add_lines(self, key, parents, lines, parent_texts=None,
944
left_matching_blocks=None, nostore_sha=None, random_id=False,
946
"""See VersionedFiles.add_lines()."""
947
path = self._mapper.map(key)
949
parents = [parent[-1] for parent in parents]
950
vf = self._get_vf(path)
953
return vf.add_lines_with_ghosts(version_id, parents, lines,
954
parent_texts=parent_texts,
955
left_matching_blocks=left_matching_blocks,
956
nostore_sha=nostore_sha, random_id=random_id,
957
check_content=check_content)
958
except NotImplementedError:
959
return vf.add_lines(version_id, parents, lines,
960
parent_texts=parent_texts,
961
left_matching_blocks=left_matching_blocks,
962
nostore_sha=nostore_sha, random_id=random_id,
963
check_content=check_content)
964
except errors.NoSuchFile:
965
# parent directory may be missing, try again.
966
self._transport.mkdir(osutils.dirname(path))
968
return vf.add_lines_with_ghosts(version_id, parents, lines,
969
parent_texts=parent_texts,
970
left_matching_blocks=left_matching_blocks,
971
nostore_sha=nostore_sha, random_id=random_id,
972
check_content=check_content)
973
except NotImplementedError:
974
return vf.add_lines(version_id, parents, lines,
975
parent_texts=parent_texts,
976
left_matching_blocks=left_matching_blocks,
977
nostore_sha=nostore_sha, random_id=random_id,
978
check_content=check_content)
980
def annotate(self, key):
981
"""Return a list of (version-key, line) tuples for the text of key.
983
:raise RevisionNotPresent: If the key is not present.
986
path = self._mapper.map(prefix)
987
vf = self._get_vf(path)
988
origins = vf.annotate(key[-1])
990
for origin, line in origins:
991
result.append((prefix + (origin,), line))
994
def check(self, progress_bar=None):
995
"""See VersionedFiles.check()."""
996
for prefix, vf in self._iter_all_components():
999
def get_parent_map(self, keys):
1000
"""Get a map of the parents of keys.
1002
:param keys: The keys to look up parents for.
1003
:return: A mapping from keys to parents. Absent keys are absent from
1006
prefixes = self._partition_keys(keys)
1008
for prefix, suffixes in prefixes.items():
1009
path = self._mapper.map(prefix)
1010
vf = self._get_vf(path)
1011
parent_map = vf.get_parent_map(suffixes)
1012
for key, parents in parent_map.items():
1013
result[prefix + (key,)] = tuple(
1014
prefix + (parent,) for parent in parents)
1017
def _get_vf(self, path):
1018
if not self._is_locked():
1019
raise errors.ObjectNotLocked(self)
1020
return self._file_factory(path, self._transport, create=True,
1021
get_scope=lambda:None)
1023
def _partition_keys(self, keys):
1024
"""Turn keys into a dict of prefix:suffix_list."""
1027
prefix_keys = result.setdefault(key[:-1], [])
1028
prefix_keys.append(key[-1])
1031
def _get_all_prefixes(self):
1032
# Identify all key prefixes.
1033
# XXX: A bit hacky, needs polish.
1034
if type(self._mapper) == ConstantMapper:
1035
paths = [self._mapper.map(())]
1039
for quoted_relpath in self._transport.iter_files_recursive():
1040
path, ext = os.path.splitext(quoted_relpath)
1042
paths = list(relpaths)
1043
prefixes = [self._mapper.unmap(path) for path in paths]
1044
return zip(paths, prefixes)
1046
def get_record_stream(self, keys, ordering, include_delta_closure):
1047
"""See VersionedFiles.get_record_stream()."""
1048
# Ordering will be taken care of by each partitioned store; group keys
1051
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1052
suffixes = [(suffix,) for suffix in suffixes]
1053
for record in vf.get_record_stream(suffixes, ordering,
1054
include_delta_closure):
1055
if record.parents is not None:
1056
record.parents = tuple(
1057
prefix + parent for parent in record.parents)
1058
record.key = prefix + record.key
1061
def _iter_keys_vf(self, keys):
1062
prefixes = self._partition_keys(keys)
1064
for prefix, suffixes in prefixes.items():
1065
path = self._mapper.map(prefix)
1066
vf = self._get_vf(path)
1067
yield prefix, suffixes, vf
1069
def get_sha1s(self, keys):
1070
"""See VersionedFiles.get_sha1s()."""
1072
for prefix,suffixes, vf in self._iter_keys_vf(keys):
1073
vf_sha1s = vf.get_sha1s(suffixes)
1074
for suffix, sha1 in vf_sha1s.iteritems():
1075
sha1s[prefix + (suffix,)] = sha1
1078
def insert_record_stream(self, stream):
1079
"""Insert a record stream into this container.
1081
:param stream: A stream of records to insert.
1083
:seealso VersionedFile.get_record_stream:
1085
for record in stream:
1086
prefix = record.key[:-1]
1087
key = record.key[-1:]
1088
if record.parents is not None:
1089
parents = [parent[-1:] for parent in record.parents]
1092
thunk_record = AdapterFactory(key, parents, record)
1093
path = self._mapper.map(prefix)
1094
# Note that this parses the file many times; we can do better but
1095
# as this only impacts weaves in terms of performance, it is
1097
vf = self._get_vf(path)
1098
vf.insert_record_stream([thunk_record])
1100
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1101
"""Iterate over the lines in the versioned files from keys.
1103
This may return lines from other keys. Each item the returned
1104
iterator yields is a tuple of a line and a text version that that line
1105
is present in (not introduced in).
1107
Ordering of results is in whatever order is most suitable for the
1108
underlying storage format.
1110
If a progress bar is supplied, it may be used to indicate progress.
1111
The caller is responsible for cleaning up progress bars (because this
1115
* Lines are normalised by the underlying store: they will all have \n
1117
* Lines are returned in arbitrary order.
1119
:return: An iterator over (line, key).
1121
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1122
for line, version in vf.iter_lines_added_or_present_in_versions(suffixes):
1123
yield line, prefix + (version,)
1125
def _iter_all_components(self):
1126
for path, prefix in self._get_all_prefixes():
1127
yield prefix, self._get_vf(path)
1130
"""See VersionedFiles.keys()."""
1132
for prefix, vf in self._iter_all_components():
1133
for suffix in vf.versions():
1134
result.add(prefix + (suffix,))
1138
class _PlanMergeVersionedFile(VersionedFiles):
1139
"""A VersionedFile for uncommitted and committed texts.
1141
It is intended to allow merges to be planned with working tree texts.
1142
It implements only the small part of the VersionedFiles interface used by
1143
PlanMerge. It falls back to multiple versionedfiles for data not stored in
1144
_PlanMergeVersionedFile itself.
1146
:ivar: fallback_versionedfiles a list of VersionedFiles objects that can be
1147
queried for missing texts.
1150
def __init__(self, file_id):
1151
"""Create a _PlanMergeVersionedFile.
1153
:param file_id: Used with _PlanMerge code which is not yet fully
1154
tuple-keyspace aware.
1156
self._file_id = file_id
1157
# fallback locations
1158
self.fallback_versionedfiles = []
1159
# Parents for locally held keys.
1161
# line data for locally held keys.
1163
# key lookup providers
1164
self._providers = [DictParentsProvider(self._parents)]
1166
def plan_merge(self, ver_a, ver_b, base=None):
1167
"""See VersionedFile.plan_merge"""
1168
from bzrlib.merge import _PlanMerge
1170
return _PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge()
1171
old_plan = list(_PlanMerge(ver_a, base, self, (self._file_id,)).plan_merge())
1172
new_plan = list(_PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge())
1173
return _PlanMerge._subtract_plans(old_plan, new_plan)
1175
def plan_lca_merge(self, ver_a, ver_b, base=None):
1176
from bzrlib.merge import _PlanLCAMerge
1178
new_plan = _PlanLCAMerge(ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
1181
old_plan = _PlanLCAMerge(ver_a, base, self, (self._file_id,), graph).plan_merge()
1182
return _PlanLCAMerge._subtract_plans(list(old_plan), list(new_plan))
1184
def add_lines(self, key, parents, lines):
1185
"""See VersionedFiles.add_lines
1187
Lines are added locally, not to fallback versionedfiles. Also, ghosts
1188
are permitted. Only reserved ids are permitted.
1190
if type(key) is not tuple:
1191
raise TypeError(key)
1192
if not revision.is_reserved_id(key[-1]):
1193
raise ValueError('Only reserved ids may be used')
1195
raise ValueError('Parents may not be None')
1197
raise ValueError('Lines may not be None')
1198
self._parents[key] = tuple(parents)
1199
self._lines[key] = lines
1201
def get_record_stream(self, keys, ordering, include_delta_closure):
1204
if key in self._lines:
1205
lines = self._lines[key]
1206
parents = self._parents[key]
1208
yield FulltextContentFactory(key, parents, None,
1210
for versionedfile in self.fallback_versionedfiles:
1211
for record in versionedfile.get_record_stream(
1212
pending, 'unordered', True):
1213
if record.storage_kind == 'absent':
1216
pending.remove(record.key)
1220
# report absent entries
1222
yield AbsentContentFactory(key)
1224
def get_parent_map(self, keys):
1225
"""See VersionedFiles.get_parent_map"""
1226
# We create a new provider because a fallback may have been added.
1227
# If we make fallbacks private we can update a stack list and avoid
1228
# object creation thrashing.
1231
if revision.NULL_REVISION in keys:
1232
keys.remove(revision.NULL_REVISION)
1233
result[revision.NULL_REVISION] = ()
1234
self._providers = self._providers[:1] + self.fallback_versionedfiles
1236
_StackedParentsProvider(self._providers).get_parent_map(keys))
1237
for key, parents in result.iteritems():
1239
result[key] = (revision.NULL_REVISION,)
1243
class PlanWeaveMerge(TextMerge):
1244
"""Weave merge that takes a plan as its input.
1246
This exists so that VersionedFile.plan_merge is implementable.
1247
Most callers will want to use WeaveMerge instead.
1250
def __init__(self, plan, a_marker=TextMerge.A_MARKER,
1251
b_marker=TextMerge.B_MARKER):
1252
TextMerge.__init__(self, a_marker, b_marker)
1255
def _merge_struct(self):
1260
def outstanding_struct():
1261
if not lines_a and not lines_b:
1263
elif ch_a and not ch_b:
1266
elif ch_b and not ch_a:
1268
elif lines_a == lines_b:
1271
yield (lines_a, lines_b)
1273
# We previously considered either 'unchanged' or 'killed-both' lines
1274
# to be possible places to resynchronize. However, assuming agreement
1275
# on killed-both lines may be too aggressive. -- mbp 20060324
1276
for state, line in self.plan:
1277
if state == 'unchanged':
1278
# resync and flush queued conflicts changes if any
1279
for struct in outstanding_struct():
1285
if state == 'unchanged':
1288
elif state == 'killed-a':
1290
lines_b.append(line)
1291
elif state == 'killed-b':
1293
lines_a.append(line)
1294
elif state == 'new-a':
1296
lines_a.append(line)
1297
elif state == 'new-b':
1299
lines_b.append(line)
1300
elif state == 'conflicted-a':
1302
lines_a.append(line)
1303
elif state == 'conflicted-b':
1305
lines_b.append(line)
1307
if state not in ('irrelevant', 'ghost-a', 'ghost-b',
1308
'killed-base', 'killed-both'):
1309
raise AssertionError(state)
1310
for struct in outstanding_struct():
1314
class WeaveMerge(PlanWeaveMerge):
1315
"""Weave merge that takes a VersionedFile and two versions as its input."""
1317
def __init__(self, versionedfile, ver_a, ver_b,
1318
a_marker=PlanWeaveMerge.A_MARKER, b_marker=PlanWeaveMerge.B_MARKER):
1319
plan = versionedfile.plan_merge(ver_a, ver_b)
1320
PlanWeaveMerge.__init__(self, plan, a_marker, b_marker)
added
removed
bzrlib/versionedfile.py
