1
# Copyright (C) 2006-2010 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 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(), """
45
from bzrlib.graph import DictParentsProvider, Graph, StackedParentsProvider
46
from bzrlib.transport.memory import MemoryTransport
48
from bzrlib.registry import Registry
49
from bzrlib.symbol_versioning import *
50
from bzrlib.textmerge import TextMerge
51
from bzrlib import bencode
54
adapter_registry = Registry()
55
adapter_registry.register_lazy(('knit-delta-gz', 'fulltext'), 'bzrlib.knit',
56
'DeltaPlainToFullText')
57
adapter_registry.register_lazy(('knit-ft-gz', 'fulltext'), 'bzrlib.knit',
59
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'knit-delta-gz'),
60
'bzrlib.knit', 'DeltaAnnotatedToUnannotated')
61
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'fulltext'),
62
'bzrlib.knit', 'DeltaAnnotatedToFullText')
63
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'knit-ft-gz'),
64
'bzrlib.knit', 'FTAnnotatedToUnannotated')
65
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'fulltext'),
66
'bzrlib.knit', 'FTAnnotatedToFullText')
67
# adapter_registry.register_lazy(('knit-annotated-ft-gz', 'chunked'),
68
# 'bzrlib.knit', 'FTAnnotatedToChunked')
71
class ContentFactory(object):
72
"""Abstract interface for insertion and retrieval from a VersionedFile.
74
:ivar sha1: None, or the sha1 of the content fulltext.
75
:ivar storage_kind: The native storage kind of this factory. One of
76
'mpdiff', 'knit-annotated-ft', 'knit-annotated-delta', 'knit-ft',
77
'knit-delta', 'fulltext', 'knit-annotated-ft-gz',
78
'knit-annotated-delta-gz', 'knit-ft-gz', 'knit-delta-gz'.
79
:ivar key: The key of this content. Each key is a tuple with a single
81
:ivar parents: A tuple of parent keys for self.key. If the object has
82
no parent information, None (as opposed to () for an empty list of
87
"""Create a ContentFactory."""
89
self.storage_kind = None
94
class ChunkedContentFactory(ContentFactory):
95
"""Static data content factory.
97
This takes a 'chunked' list of strings. The only requirement on 'chunked' is
98
that ''.join(lines) becomes a valid fulltext. A tuple of a single string
99
satisfies this, as does a list of lines.
101
:ivar sha1: None, or the sha1 of the content fulltext.
102
:ivar storage_kind: The native storage kind of this factory. Always
104
:ivar key: The key of this content. Each key is a tuple with a single
106
:ivar parents: A tuple of parent keys for self.key. If the object has
107
no parent information, None (as opposed to () for an empty list of
111
def __init__(self, key, parents, sha1, chunks):
112
"""Create a ContentFactory."""
114
self.storage_kind = 'chunked'
116
self.parents = parents
117
self._chunks = chunks
119
def get_bytes_as(self, storage_kind):
120
if storage_kind == 'chunked':
122
elif storage_kind == 'fulltext':
123
return ''.join(self._chunks)
124
raise errors.UnavailableRepresentation(self.key, storage_kind,
128
class FulltextContentFactory(ContentFactory):
129
"""Static data content factory.
131
This takes a fulltext when created and just returns that during
132
get_bytes_as('fulltext').
134
:ivar sha1: None, or the sha1 of the content fulltext.
135
:ivar storage_kind: The native storage kind of this factory. Always
137
:ivar key: The key of this content. Each key is a tuple with a single
139
:ivar parents: A tuple of parent keys for self.key. If the object has
140
no parent information, None (as opposed to () for an empty list of
144
def __init__(self, key, parents, sha1, text):
145
"""Create a ContentFactory."""
147
self.storage_kind = 'fulltext'
149
self.parents = parents
152
def get_bytes_as(self, storage_kind):
153
if storage_kind == self.storage_kind:
155
elif storage_kind == 'chunked':
157
raise errors.UnavailableRepresentation(self.key, storage_kind,
161
class AbsentContentFactory(ContentFactory):
162
"""A placeholder content factory for unavailable texts.
165
:ivar storage_kind: 'absent'.
166
:ivar key: The key of this content. Each key is a tuple with a single
171
def __init__(self, key):
172
"""Create a ContentFactory."""
174
self.storage_kind = 'absent'
178
def get_bytes_as(self, storage_kind):
179
raise ValueError('A request was made for key: %s, but that'
180
' content is not available, and the calling'
181
' code does not handle if it is missing.'
185
class AdapterFactory(ContentFactory):
186
"""A content factory to adapt between key prefix's."""
188
def __init__(self, key, parents, adapted):
189
"""Create an adapter factory instance."""
191
self.parents = parents
192
self._adapted = adapted
194
def __getattr__(self, attr):
195
"""Return a member from the adapted object."""
196
if attr in ('key', 'parents'):
197
return self.__dict__[attr]
199
return getattr(self._adapted, attr)
202
def filter_absent(record_stream):
203
"""Adapt a record stream to remove absent records."""
204
for record in record_stream:
205
if record.storage_kind != 'absent':
209
class VersionedFile(object):
210
"""Versioned text file storage.
212
A versioned file manages versions of line-based text files,
213
keeping track of the originating version for each line.
215
To clients the "lines" of the file are represented as a list of
216
strings. These strings will typically have terminal newline
217
characters, but this is not required. In particular files commonly
218
do not have a newline at the end of the file.
220
Texts are identified by a version-id string.
224
def check_not_reserved_id(version_id):
225
revision.check_not_reserved_id(version_id)
227
def copy_to(self, name, transport):
228
"""Copy this versioned file to name on transport."""
229
raise NotImplementedError(self.copy_to)
231
def get_record_stream(self, versions, ordering, include_delta_closure):
232
"""Get a stream of records for versions.
234
:param versions: The versions to include. Each version is a tuple
236
:param ordering: Either 'unordered' or 'topological'. A topologically
237
sorted stream has compression parents strictly before their
239
:param include_delta_closure: If True then the closure across any
240
compression parents will be included (in the data content of the
241
stream, not in the emitted records). This guarantees that
242
'fulltext' can be used successfully on every record.
243
:return: An iterator of ContentFactory objects, each of which is only
244
valid until the iterator is advanced.
246
raise NotImplementedError(self.get_record_stream)
248
def has_version(self, version_id):
249
"""Returns whether version is present."""
250
raise NotImplementedError(self.has_version)
252
def insert_record_stream(self, stream):
253
"""Insert a record stream into this versioned file.
255
:param stream: A stream of records to insert.
257
:seealso VersionedFile.get_record_stream:
259
raise NotImplementedError
261
def add_lines(self, version_id, parents, lines, parent_texts=None,
262
left_matching_blocks=None, nostore_sha=None, random_id=False,
264
"""Add a single text on top of the versioned file.
266
Must raise RevisionAlreadyPresent if the new version is
267
already present in file history.
269
Must raise RevisionNotPresent if any of the given parents are
270
not present in file history.
272
:param lines: A list of lines. Each line must be a bytestring. And all
273
of them except the last must be terminated with \n and contain no
274
other \n's. The last line may either contain no \n's or a single
275
terminated \n. If the lines list does meet this constraint the add
276
routine may error or may succeed - but you will be unable to read
277
the data back accurately. (Checking the lines have been split
278
correctly is expensive and extremely unlikely to catch bugs so it
279
is not done at runtime unless check_content is True.)
280
:param parent_texts: An optional dictionary containing the opaque
281
representations of some or all of the parents of version_id to
282
allow delta optimisations. VERY IMPORTANT: the texts must be those
283
returned by add_lines or data corruption can be caused.
284
:param left_matching_blocks: a hint about which areas are common
285
between the text and its left-hand-parent. The format is
286
the SequenceMatcher.get_matching_blocks format.
287
:param nostore_sha: Raise ExistingContent and do not add the lines to
288
the versioned file if the digest of the lines matches this.
289
:param random_id: If True a random id has been selected rather than
290
an id determined by some deterministic process such as a converter
291
from a foreign VCS. When True the backend may choose not to check
292
for uniqueness of the resulting key within the versioned file, so
293
this should only be done when the result is expected to be unique
295
:param check_content: If True, the lines supplied are verified to be
296
bytestrings that are correctly formed lines.
297
:return: The text sha1, the number of bytes in the text, and an opaque
298
representation of the inserted version which can be provided
299
back to future add_lines calls in the parent_texts dictionary.
301
self._check_write_ok()
302
return self._add_lines(version_id, parents, lines, parent_texts,
303
left_matching_blocks, nostore_sha, random_id, check_content)
305
def _add_lines(self, version_id, parents, lines, parent_texts,
306
left_matching_blocks, nostore_sha, random_id, check_content):
307
"""Helper to do the class specific add_lines."""
308
raise NotImplementedError(self.add_lines)
310
def add_lines_with_ghosts(self, version_id, parents, lines,
311
parent_texts=None, nostore_sha=None, random_id=False,
312
check_content=True, left_matching_blocks=None):
313
"""Add lines to the versioned file, allowing ghosts to be present.
315
This takes the same parameters as add_lines and returns the same.
317
self._check_write_ok()
318
return self._add_lines_with_ghosts(version_id, parents, lines,
319
parent_texts, nostore_sha, random_id, check_content, left_matching_blocks)
321
def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts,
322
nostore_sha, random_id, check_content, left_matching_blocks):
323
"""Helper to do class specific add_lines_with_ghosts."""
324
raise NotImplementedError(self.add_lines_with_ghosts)
326
def check(self, progress_bar=None):
327
"""Check the versioned file for integrity."""
328
raise NotImplementedError(self.check)
330
def _check_lines_not_unicode(self, lines):
331
"""Check that lines being added to a versioned file are not unicode."""
333
if line.__class__ is not str:
334
raise errors.BzrBadParameterUnicode("lines")
336
def _check_lines_are_lines(self, lines):
337
"""Check that the lines really are full lines without inline EOL."""
339
if '\n' in line[:-1]:
340
raise errors.BzrBadParameterContainsNewline("lines")
342
def get_format_signature(self):
343
"""Get a text description of the data encoding in this file.
347
raise NotImplementedError(self.get_format_signature)
349
def make_mpdiffs(self, version_ids):
350
"""Create multiparent diffs for specified versions."""
351
knit_versions = set()
352
knit_versions.update(version_ids)
353
parent_map = self.get_parent_map(version_ids)
354
for version_id in version_ids:
356
knit_versions.update(parent_map[version_id])
358
raise errors.RevisionNotPresent(version_id, self)
359
# We need to filter out ghosts, because we can't diff against them.
360
knit_versions = set(self.get_parent_map(knit_versions).keys())
361
lines = dict(zip(knit_versions,
362
self._get_lf_split_line_list(knit_versions)))
364
for version_id in version_ids:
365
target = lines[version_id]
367
parents = [lines[p] for p in parent_map[version_id] if p in
370
# I don't know how this could ever trigger.
371
# parent_map[version_id] was already triggered in the previous
372
# for loop, and lines[p] has the 'if p in knit_versions' check,
373
# so we again won't have a KeyError.
374
raise errors.RevisionNotPresent(version_id, self)
376
left_parent_blocks = self._extract_blocks(version_id,
379
left_parent_blocks = None
380
diffs.append(multiparent.MultiParent.from_lines(target, parents,
384
def _extract_blocks(self, version_id, source, target):
387
def add_mpdiffs(self, records):
388
"""Add mpdiffs to this VersionedFile.
390
Records should be iterables of version, parents, expected_sha1,
391
mpdiff. mpdiff should be a MultiParent instance.
393
# Does this need to call self._check_write_ok()? (IanC 20070919)
395
mpvf = multiparent.MultiMemoryVersionedFile()
397
for version, parent_ids, expected_sha1, mpdiff in records:
398
versions.append(version)
399
mpvf.add_diff(mpdiff, version, parent_ids)
400
needed_parents = set()
401
for version, parent_ids, expected_sha1, mpdiff in records:
402
needed_parents.update(p for p in parent_ids
403
if not mpvf.has_version(p))
404
present_parents = set(self.get_parent_map(needed_parents).keys())
405
for parent_id, lines in zip(present_parents,
406
self._get_lf_split_line_list(present_parents)):
407
mpvf.add_version(lines, parent_id, [])
408
for (version, parent_ids, expected_sha1, mpdiff), lines in\
409
zip(records, mpvf.get_line_list(versions)):
410
if len(parent_ids) == 1:
411
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
412
mpvf.get_diff(parent_ids[0]).num_lines()))
414
left_matching_blocks = None
416
_, _, version_text = self.add_lines_with_ghosts(version,
417
parent_ids, lines, vf_parents,
418
left_matching_blocks=left_matching_blocks)
419
except NotImplementedError:
420
# The vf can't handle ghosts, so add lines normally, which will
421
# (reasonably) fail if there are ghosts in the data.
422
_, _, version_text = self.add_lines(version,
423
parent_ids, lines, vf_parents,
424
left_matching_blocks=left_matching_blocks)
425
vf_parents[version] = version_text
426
sha1s = self.get_sha1s(versions)
427
for version, parent_ids, expected_sha1, mpdiff in records:
428
if expected_sha1 != sha1s[version]:
429
raise errors.VersionedFileInvalidChecksum(version)
431
def get_text(self, version_id):
432
"""Return version contents as a text string.
434
Raises RevisionNotPresent if version is not present in
437
return ''.join(self.get_lines(version_id))
438
get_string = get_text
440
def get_texts(self, version_ids):
441
"""Return the texts of listed versions as a list of strings.
443
Raises RevisionNotPresent if version is not present in
446
return [''.join(self.get_lines(v)) for v in version_ids]
448
def get_lines(self, version_id):
449
"""Return version contents as a sequence of lines.
451
Raises RevisionNotPresent if version is not present in
454
raise NotImplementedError(self.get_lines)
456
def _get_lf_split_line_list(self, version_ids):
457
return [StringIO(t).readlines() for t in self.get_texts(version_ids)]
459
def get_ancestry(self, version_ids, topo_sorted=True):
460
"""Return a list of all ancestors of given version(s). This
461
will not include the null revision.
463
This list will not be topologically sorted if topo_sorted=False is
466
Must raise RevisionNotPresent if any of the given versions are
467
not present in file history."""
468
if isinstance(version_ids, basestring):
469
version_ids = [version_ids]
470
raise NotImplementedError(self.get_ancestry)
472
def get_ancestry_with_ghosts(self, version_ids):
473
"""Return a list of all ancestors of given version(s). This
474
will not include the null revision.
476
Must raise RevisionNotPresent if any of the given versions are
477
not present in file history.
479
Ghosts that are known about will be included in ancestry list,
480
but are not explicitly marked.
482
raise NotImplementedError(self.get_ancestry_with_ghosts)
484
def get_parent_map(self, version_ids):
485
"""Get a map of the parents of version_ids.
487
:param version_ids: The version ids to look up parents for.
488
:return: A mapping from version id to parents.
490
raise NotImplementedError(self.get_parent_map)
492
def get_parents_with_ghosts(self, version_id):
493
"""Return version names for parents of version_id.
495
Will raise RevisionNotPresent if version_id is not present
498
Ghosts that are known about will be included in the parent list,
499
but are not explicitly marked.
502
return list(self.get_parent_map([version_id])[version_id])
504
raise errors.RevisionNotPresent(version_id, self)
506
def annotate(self, version_id):
507
"""Return a list of (version-id, line) tuples for version_id.
509
:raise RevisionNotPresent: If the given version is
510
not present in file history.
512
raise NotImplementedError(self.annotate)
514
def iter_lines_added_or_present_in_versions(self, version_ids=None,
516
"""Iterate over the lines in the versioned file from version_ids.
518
This may return lines from other versions. Each item the returned
519
iterator yields is a tuple of a line and a text version that that line
520
is present in (not introduced in).
522
Ordering of results is in whatever order is most suitable for the
523
underlying storage format.
525
If a progress bar is supplied, it may be used to indicate progress.
526
The caller is responsible for cleaning up progress bars (because this
529
NOTES: Lines are normalised: they will all have \n terminators.
530
Lines are returned in arbitrary order.
532
:return: An iterator over (line, version_id).
534
raise NotImplementedError(self.iter_lines_added_or_present_in_versions)
536
def plan_merge(self, ver_a, ver_b):
537
"""Return pseudo-annotation indicating how the two versions merge.
539
This is computed between versions a and b and their common
542
Weave lines present in none of them are skipped entirely.
545
killed-base Dead in base revision
546
killed-both Killed in each revision
549
unchanged Alive in both a and b (possibly created in both)
552
ghost-a Killed in a, unborn in b
553
ghost-b Killed in b, unborn in a
554
irrelevant Not in either revision
556
raise NotImplementedError(VersionedFile.plan_merge)
558
def weave_merge(self, plan, a_marker=TextMerge.A_MARKER,
559
b_marker=TextMerge.B_MARKER):
560
return PlanWeaveMerge(plan, a_marker, b_marker).merge_lines()[0]
563
class RecordingVersionedFilesDecorator(object):
564
"""A minimal versioned files that records calls made on it.
566
Only enough methods have been added to support tests using it to date.
568
:ivar calls: A list of the calls made; can be reset at any time by
572
def __init__(self, backing_vf):
573
"""Create a RecordingVersionedFilesDecorator decorating backing_vf.
575
:param backing_vf: The versioned file to answer all methods.
577
self._backing_vf = backing_vf
580
def add_lines(self, key, parents, lines, parent_texts=None,
581
left_matching_blocks=None, nostore_sha=None, random_id=False,
583
self.calls.append(("add_lines", key, parents, lines, parent_texts,
584
left_matching_blocks, nostore_sha, random_id, check_content))
585
return self._backing_vf.add_lines(key, parents, lines, parent_texts,
586
left_matching_blocks, nostore_sha, random_id, check_content)
589
self._backing_vf.check()
591
def get_parent_map(self, keys):
592
self.calls.append(("get_parent_map", copy(keys)))
593
return self._backing_vf.get_parent_map(keys)
595
def get_record_stream(self, keys, sort_order, include_delta_closure):
596
self.calls.append(("get_record_stream", list(keys), sort_order,
597
include_delta_closure))
598
return self._backing_vf.get_record_stream(keys, sort_order,
599
include_delta_closure)
601
def get_sha1s(self, keys):
602
self.calls.append(("get_sha1s", copy(keys)))
603
return self._backing_vf.get_sha1s(keys)
605
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
606
self.calls.append(("iter_lines_added_or_present_in_keys", copy(keys)))
607
return self._backing_vf.iter_lines_added_or_present_in_keys(keys, pb=pb)
610
self.calls.append(("keys",))
611
return self._backing_vf.keys()
614
class OrderingVersionedFilesDecorator(RecordingVersionedFilesDecorator):
615
"""A VF that records calls, and returns keys in specific order.
617
:ivar calls: A list of the calls made; can be reset at any time by
621
def __init__(self, backing_vf, key_priority):
622
"""Create a RecordingVersionedFilesDecorator decorating backing_vf.
624
:param backing_vf: The versioned file to answer all methods.
625
:param key_priority: A dictionary defining what order keys should be
626
returned from an 'unordered' get_record_stream request.
627
Keys with lower priority are returned first, keys not present in
628
the map get an implicit priority of 0, and are returned in
629
lexicographical order.
631
RecordingVersionedFilesDecorator.__init__(self, backing_vf)
632
self._key_priority = key_priority
634
def get_record_stream(self, keys, sort_order, include_delta_closure):
635
self.calls.append(("get_record_stream", list(keys), sort_order,
636
include_delta_closure))
637
if sort_order == 'unordered':
639
return (self._key_priority.get(key, 0), key)
640
# Use a defined order by asking for the keys one-by-one from the
642
for key in sorted(keys, key=sort_key):
643
for record in self._backing_vf.get_record_stream([key],
644
'unordered', include_delta_closure):
647
for record in self._backing_vf.get_record_stream(keys, sort_order,
648
include_delta_closure):
652
class KeyMapper(object):
653
"""KeyMappers map between keys and underlying partitioned storage."""
656
"""Map key to an underlying storage identifier.
658
:param key: A key tuple e.g. ('file-id', 'revision-id').
659
:return: An underlying storage identifier, specific to the partitioning
662
raise NotImplementedError(self.map)
664
def unmap(self, partition_id):
665
"""Map a partitioned storage id back to a key prefix.
667
:param partition_id: The underlying partition id.
668
:return: As much of a key (or prefix) as is derivable from the partition
671
raise NotImplementedError(self.unmap)
674
class ConstantMapper(KeyMapper):
675
"""A key mapper that maps to a constant result."""
677
def __init__(self, result):
678
"""Create a ConstantMapper which will return result for all maps."""
679
self._result = result
682
"""See KeyMapper.map()."""
686
class URLEscapeMapper(KeyMapper):
687
"""Base class for use with transport backed storage.
689
This provides a map and unmap wrapper that respectively url escape and
690
unescape their outputs and inputs.
694
"""See KeyMapper.map()."""
695
return urllib.quote(self._map(key))
697
def unmap(self, partition_id):
698
"""See KeyMapper.unmap()."""
699
return self._unmap(urllib.unquote(partition_id))
702
class PrefixMapper(URLEscapeMapper):
703
"""A key mapper that extracts the first component of a key.
705
This mapper is for use with a transport based backend.
709
"""See KeyMapper.map()."""
712
def _unmap(self, partition_id):
713
"""See KeyMapper.unmap()."""
714
return (partition_id,)
717
class HashPrefixMapper(URLEscapeMapper):
718
"""A key mapper that combines the first component of a key with a hash.
720
This mapper is for use with a transport based backend.
724
"""See KeyMapper.map()."""
725
prefix = self._escape(key[0])
726
return "%02x/%s" % (adler32(prefix) & 0xff, prefix)
728
def _escape(self, prefix):
729
"""No escaping needed here."""
732
def _unmap(self, partition_id):
733
"""See KeyMapper.unmap()."""
734
return (self._unescape(osutils.basename(partition_id)),)
736
def _unescape(self, basename):
737
"""No unescaping needed for HashPrefixMapper."""
741
class HashEscapedPrefixMapper(HashPrefixMapper):
742
"""Combines the escaped first component of a key with a hash.
744
This mapper is for use with a transport based backend.
747
_safe = "abcdefghijklmnopqrstuvwxyz0123456789-_@,."
749
def _escape(self, prefix):
750
"""Turn a key element into a filesystem safe string.
752
This is similar to a plain urllib.quote, except
753
it uses specific safe characters, so that it doesn't
754
have to translate a lot of valid file ids.
756
# @ does not get escaped. This is because it is a valid
757
# filesystem character we use all the time, and it looks
758
# a lot better than seeing %40 all the time.
759
r = [((c in self._safe) and c or ('%%%02x' % ord(c)))
763
def _unescape(self, basename):
764
"""Escaped names are easily unescaped by urlutils."""
765
return urllib.unquote(basename)
768
def make_versioned_files_factory(versioned_file_factory, mapper):
769
"""Create a ThunkedVersionedFiles factory.
771
This will create a callable which when called creates a
772
ThunkedVersionedFiles on a transport, using mapper to access individual
773
versioned files, and versioned_file_factory to create each individual file.
775
def factory(transport):
776
return ThunkedVersionedFiles(transport, versioned_file_factory, mapper,
781
class VersionedFiles(object):
782
"""Storage for many versioned files.
784
This object allows a single keyspace for accessing the history graph and
785
contents of named bytestrings.
787
Currently no implementation allows the graph of different key prefixes to
788
intersect, but the API does allow such implementations in the future.
790
The keyspace is expressed via simple tuples. Any instance of VersionedFiles
791
may have a different length key-size, but that size will be constant for
792
all texts added to or retrieved from it. For instance, bzrlib uses
793
instances with a key-size of 2 for storing user files in a repository, with
794
the first element the fileid, and the second the version of that file.
796
The use of tuples allows a single code base to support several different
797
uses with only the mapping logic changing from instance to instance.
800
def add_lines(self, key, parents, lines, parent_texts=None,
801
left_matching_blocks=None, nostore_sha=None, random_id=False,
803
"""Add a text to the store.
805
:param key: The key tuple of the text to add. If the last element is
806
None, a CHK string will be generated during the addition.
807
:param parents: The parents key tuples of the text to add.
808
:param lines: A list of lines. Each line must be a bytestring. And all
809
of them except the last must be terminated with \n and contain no
810
other \n's. The last line may either contain no \n's or a single
811
terminating \n. If the lines list does meet this constraint the add
812
routine may error or may succeed - but you will be unable to read
813
the data back accurately. (Checking the lines have been split
814
correctly is expensive and extremely unlikely to catch bugs so it
815
is not done at runtime unless check_content is True.)
816
:param parent_texts: An optional dictionary containing the opaque
817
representations of some or all of the parents of version_id to
818
allow delta optimisations. VERY IMPORTANT: the texts must be those
819
returned by add_lines or data corruption can be caused.
820
:param left_matching_blocks: a hint about which areas are common
821
between the text and its left-hand-parent. The format is
822
the SequenceMatcher.get_matching_blocks format.
823
:param nostore_sha: Raise ExistingContent and do not add the lines to
824
the versioned file if the digest of the lines matches this.
825
:param random_id: If True a random id has been selected rather than
826
an id determined by some deterministic process such as a converter
827
from a foreign VCS. When True the backend may choose not to check
828
for uniqueness of the resulting key within the versioned file, so
829
this should only be done when the result is expected to be unique
831
:param check_content: If True, the lines supplied are verified to be
832
bytestrings that are correctly formed lines.
833
:return: The text sha1, the number of bytes in the text, and an opaque
834
representation of the inserted version which can be provided
835
back to future add_lines calls in the parent_texts dictionary.
837
raise NotImplementedError(self.add_lines)
839
def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
840
"""Add a text to the store.
842
This is a private function for use by CommitBuilder.
844
:param key: The key tuple of the text to add. If the last element is
845
None, a CHK string will be generated during the addition.
846
:param parents: The parents key tuples of the text to add.
847
:param text: A string containing the text to be committed.
848
:param nostore_sha: Raise ExistingContent and do not add the lines to
849
the versioned file if the digest of the lines matches this.
850
:param random_id: If True a random id has been selected rather than
851
an id determined by some deterministic process such as a converter
852
from a foreign VCS. When True the backend may choose not to check
853
for uniqueness of the resulting key within the versioned file, so
854
this should only be done when the result is expected to be unique
856
:param check_content: If True, the lines supplied are verified to be
857
bytestrings that are correctly formed lines.
858
:return: The text sha1, the number of bytes in the text, and an opaque
859
representation of the inserted version which can be provided
860
back to future _add_text calls in the parent_texts dictionary.
862
# The default implementation just thunks over to .add_lines(),
863
# inefficient, but it works.
864
return self.add_lines(key, parents, osutils.split_lines(text),
865
nostore_sha=nostore_sha,
869
def add_mpdiffs(self, records):
870
"""Add mpdiffs to this VersionedFile.
872
Records should be iterables of version, parents, expected_sha1,
873
mpdiff. mpdiff should be a MultiParent instance.
876
mpvf = multiparent.MultiMemoryVersionedFile()
878
for version, parent_ids, expected_sha1, mpdiff in records:
879
versions.append(version)
880
mpvf.add_diff(mpdiff, version, parent_ids)
881
needed_parents = set()
882
for version, parent_ids, expected_sha1, mpdiff in records:
883
needed_parents.update(p for p in parent_ids
884
if not mpvf.has_version(p))
885
# It seems likely that adding all the present parents as fulltexts can
886
# easily exhaust memory.
887
chunks_to_lines = osutils.chunks_to_lines
888
for record in self.get_record_stream(needed_parents, 'unordered',
890
if record.storage_kind == 'absent':
892
mpvf.add_version(chunks_to_lines(record.get_bytes_as('chunked')),
894
for (key, parent_keys, expected_sha1, mpdiff), lines in\
895
zip(records, mpvf.get_line_list(versions)):
896
if len(parent_keys) == 1:
897
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
898
mpvf.get_diff(parent_keys[0]).num_lines()))
900
left_matching_blocks = None
901
version_sha1, _, version_text = self.add_lines(key,
902
parent_keys, lines, vf_parents,
903
left_matching_blocks=left_matching_blocks)
904
if version_sha1 != expected_sha1:
905
raise errors.VersionedFileInvalidChecksum(version)
906
vf_parents[key] = version_text
908
def annotate(self, key):
909
"""Return a list of (version-key, line) tuples for the text of key.
911
:raise RevisionNotPresent: If the key is not present.
913
raise NotImplementedError(self.annotate)
915
def check(self, progress_bar=None):
916
"""Check this object for integrity.
918
:param progress_bar: A progress bar to output as the check progresses.
919
:param keys: Specific keys within the VersionedFiles to check. When
920
this parameter is not None, check() becomes a generator as per
921
get_record_stream. The difference to get_record_stream is that
922
more or deeper checks will be performed.
923
:return: None, or if keys was supplied a generator as per
926
raise NotImplementedError(self.check)
929
def check_not_reserved_id(version_id):
930
revision.check_not_reserved_id(version_id)
932
def clear_cache(self):
933
"""Clear whatever caches this VersionedFile holds.
935
This is generally called after an operation has been performed, when we
936
don't expect to be using this versioned file again soon.
939
def _check_lines_not_unicode(self, lines):
940
"""Check that lines being added to a versioned file are not unicode."""
942
if line.__class__ is not str:
943
raise errors.BzrBadParameterUnicode("lines")
945
def _check_lines_are_lines(self, lines):
946
"""Check that the lines really are full lines without inline EOL."""
948
if '\n' in line[:-1]:
949
raise errors.BzrBadParameterContainsNewline("lines")
951
def get_known_graph_ancestry(self, keys):
952
"""Get a KnownGraph instance with the ancestry of keys."""
953
# most basic implementation is a loop around get_parent_map
957
this_parent_map = self.get_parent_map(pending)
958
parent_map.update(this_parent_map)
960
map(pending.update, this_parent_map.itervalues())
961
pending = pending.difference(parent_map)
962
kg = _mod_graph.KnownGraph(parent_map)
965
def get_parent_map(self, keys):
966
"""Get a map of the parents of keys.
968
:param keys: The keys to look up parents for.
969
:return: A mapping from keys to parents. Absent keys are absent from
972
raise NotImplementedError(self.get_parent_map)
974
def get_record_stream(self, keys, ordering, include_delta_closure):
975
"""Get a stream of records for keys.
977
:param keys: The keys to include.
978
:param ordering: Either 'unordered' or 'topological'. A topologically
979
sorted stream has compression parents strictly before their
981
:param include_delta_closure: If True then the closure across any
982
compression parents will be included (in the opaque data).
983
:return: An iterator of ContentFactory objects, each of which is only
984
valid until the iterator is advanced.
986
raise NotImplementedError(self.get_record_stream)
988
def get_sha1s(self, keys):
989
"""Get the sha1's of the texts for the given keys.
991
:param keys: The names of the keys to lookup
992
:return: a dict from key to sha1 digest. Keys of texts which are not
993
present in the store are not present in the returned
996
raise NotImplementedError(self.get_sha1s)
998
has_key = index._has_key_from_parent_map
1000
def get_missing_compression_parent_keys(self):
1001
"""Return an iterable of keys of missing compression parents.
1003
Check this after calling insert_record_stream to find out if there are
1004
any missing compression parents. If there are, the records that
1005
depend on them are not able to be inserted safely. The precise
1006
behaviour depends on the concrete VersionedFiles class in use.
1008
Classes that do not support this will raise NotImplementedError.
1010
raise NotImplementedError(self.get_missing_compression_parent_keys)
1012
def insert_record_stream(self, stream):
1013
"""Insert a record stream into this container.
1015
:param stream: A stream of records to insert.
1017
:seealso VersionedFile.get_record_stream:
1019
raise NotImplementedError
1021
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1022
"""Iterate over the lines in the versioned files from keys.
1024
This may return lines from other keys. Each item the returned
1025
iterator yields is a tuple of a line and a text version that that line
1026
is present in (not introduced in).
1028
Ordering of results is in whatever order is most suitable for the
1029
underlying storage format.
1031
If a progress bar is supplied, it may be used to indicate progress.
1032
The caller is responsible for cleaning up progress bars (because this
1036
* Lines are normalised by the underlying store: they will all have \n
1038
* Lines are returned in arbitrary order.
1040
:return: An iterator over (line, key).
1042
raise NotImplementedError(self.iter_lines_added_or_present_in_keys)
1045
"""Return a iterable of the keys for all the contained texts."""
1046
raise NotImplementedError(self.keys)
1048
def make_mpdiffs(self, keys):
1049
"""Create multiparent diffs for specified keys."""
1050
keys_order = tuple(keys)
1051
keys = frozenset(keys)
1052
knit_keys = set(keys)
1053
parent_map = self.get_parent_map(keys)
1054
for parent_keys in parent_map.itervalues():
1056
knit_keys.update(parent_keys)
1057
missing_keys = keys - set(parent_map)
1059
raise errors.RevisionNotPresent(list(missing_keys)[0], self)
1060
# We need to filter out ghosts, because we can't diff against them.
1061
maybe_ghosts = knit_keys - keys
1062
ghosts = maybe_ghosts - set(self.get_parent_map(maybe_ghosts))
1063
knit_keys.difference_update(ghosts)
1065
chunks_to_lines = osutils.chunks_to_lines
1066
for record in self.get_record_stream(knit_keys, 'topological', True):
1067
lines[record.key] = chunks_to_lines(record.get_bytes_as('chunked'))
1068
# line_block_dict = {}
1069
# for parent, blocks in record.extract_line_blocks():
1070
# line_blocks[parent] = blocks
1071
# line_blocks[record.key] = line_block_dict
1073
for key in keys_order:
1075
parents = parent_map[key] or []
1076
# Note that filtering knit_keys can lead to a parent difference
1077
# between the creation and the application of the mpdiff.
1078
parent_lines = [lines[p] for p in parents if p in knit_keys]
1079
if len(parent_lines) > 0:
1080
left_parent_blocks = self._extract_blocks(key, parent_lines[0],
1083
left_parent_blocks = None
1084
diffs.append(multiparent.MultiParent.from_lines(target,
1085
parent_lines, left_parent_blocks))
1088
missing_keys = index._missing_keys_from_parent_map
1090
def _extract_blocks(self, version_id, source, target):
1094
class ThunkedVersionedFiles(VersionedFiles):
1095
"""Storage for many versioned files thunked onto a 'VersionedFile' class.
1097
This object allows a single keyspace for accessing the history graph and
1098
contents of named bytestrings.
1100
Currently no implementation allows the graph of different key prefixes to
1101
intersect, but the API does allow such implementations in the future.
1104
def __init__(self, transport, file_factory, mapper, is_locked):
1105
"""Create a ThunkedVersionedFiles."""
1106
self._transport = transport
1107
self._file_factory = file_factory
1108
self._mapper = mapper
1109
self._is_locked = is_locked
1111
def add_lines(self, key, parents, lines, parent_texts=None,
1112
left_matching_blocks=None, nostore_sha=None, random_id=False,
1113
check_content=True):
1114
"""See VersionedFiles.add_lines()."""
1115
path = self._mapper.map(key)
1116
version_id = key[-1]
1117
parents = [parent[-1] for parent in parents]
1118
vf = self._get_vf(path)
1121
return vf.add_lines_with_ghosts(version_id, parents, lines,
1122
parent_texts=parent_texts,
1123
left_matching_blocks=left_matching_blocks,
1124
nostore_sha=nostore_sha, random_id=random_id,
1125
check_content=check_content)
1126
except NotImplementedError:
1127
return vf.add_lines(version_id, parents, lines,
1128
parent_texts=parent_texts,
1129
left_matching_blocks=left_matching_blocks,
1130
nostore_sha=nostore_sha, random_id=random_id,
1131
check_content=check_content)
1132
except errors.NoSuchFile:
1133
# parent directory may be missing, try again.
1134
self._transport.mkdir(osutils.dirname(path))
1136
return vf.add_lines_with_ghosts(version_id, parents, lines,
1137
parent_texts=parent_texts,
1138
left_matching_blocks=left_matching_blocks,
1139
nostore_sha=nostore_sha, random_id=random_id,
1140
check_content=check_content)
1141
except NotImplementedError:
1142
return vf.add_lines(version_id, parents, lines,
1143
parent_texts=parent_texts,
1144
left_matching_blocks=left_matching_blocks,
1145
nostore_sha=nostore_sha, random_id=random_id,
1146
check_content=check_content)
1148
def annotate(self, key):
1149
"""Return a list of (version-key, line) tuples for the text of key.
1151
:raise RevisionNotPresent: If the key is not present.
1154
path = self._mapper.map(prefix)
1155
vf = self._get_vf(path)
1156
origins = vf.annotate(key[-1])
1158
for origin, line in origins:
1159
result.append((prefix + (origin,), line))
1162
def get_annotator(self):
1163
return annotate.Annotator(self)
1165
def check(self, progress_bar=None, keys=None):
1166
"""See VersionedFiles.check()."""
1167
# XXX: This is over-enthusiastic but as we only thunk for Weaves today
1168
# this is tolerable. Ideally we'd pass keys down to check() and
1169
# have the older VersiondFile interface updated too.
1170
for prefix, vf in self._iter_all_components():
1172
if keys is not None:
1173
return self.get_record_stream(keys, 'unordered', True)
1175
def get_parent_map(self, keys):
1176
"""Get a map of the parents of keys.
1178
:param keys: The keys to look up parents for.
1179
:return: A mapping from keys to parents. Absent keys are absent from
1182
prefixes = self._partition_keys(keys)
1184
for prefix, suffixes in prefixes.items():
1185
path = self._mapper.map(prefix)
1186
vf = self._get_vf(path)
1187
parent_map = vf.get_parent_map(suffixes)
1188
for key, parents in parent_map.items():
1189
result[prefix + (key,)] = tuple(
1190
prefix + (parent,) for parent in parents)
1193
def _get_vf(self, path):
1194
if not self._is_locked():
1195
raise errors.ObjectNotLocked(self)
1196
return self._file_factory(path, self._transport, create=True,
1197
get_scope=lambda:None)
1199
def _partition_keys(self, keys):
1200
"""Turn keys into a dict of prefix:suffix_list."""
1203
prefix_keys = result.setdefault(key[:-1], [])
1204
prefix_keys.append(key[-1])
1207
def _get_all_prefixes(self):
1208
# Identify all key prefixes.
1209
# XXX: A bit hacky, needs polish.
1210
if type(self._mapper) == ConstantMapper:
1211
paths = [self._mapper.map(())]
1215
for quoted_relpath in self._transport.iter_files_recursive():
1216
path, ext = os.path.splitext(quoted_relpath)
1218
paths = list(relpaths)
1219
prefixes = [self._mapper.unmap(path) for path in paths]
1220
return zip(paths, prefixes)
1222
def get_record_stream(self, keys, ordering, include_delta_closure):
1223
"""See VersionedFiles.get_record_stream()."""
1224
# Ordering will be taken care of by each partitioned store; group keys
1227
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1228
suffixes = [(suffix,) for suffix in suffixes]
1229
for record in vf.get_record_stream(suffixes, ordering,
1230
include_delta_closure):
1231
if record.parents is not None:
1232
record.parents = tuple(
1233
prefix + parent for parent in record.parents)
1234
record.key = prefix + record.key
1237
def _iter_keys_vf(self, keys):
1238
prefixes = self._partition_keys(keys)
1240
for prefix, suffixes in prefixes.items():
1241
path = self._mapper.map(prefix)
1242
vf = self._get_vf(path)
1243
yield prefix, suffixes, vf
1245
def get_sha1s(self, keys):
1246
"""See VersionedFiles.get_sha1s()."""
1248
for prefix,suffixes, vf in self._iter_keys_vf(keys):
1249
vf_sha1s = vf.get_sha1s(suffixes)
1250
for suffix, sha1 in vf_sha1s.iteritems():
1251
sha1s[prefix + (suffix,)] = sha1
1254
def insert_record_stream(self, stream):
1255
"""Insert a record stream into this container.
1257
:param stream: A stream of records to insert.
1259
:seealso VersionedFile.get_record_stream:
1261
for record in stream:
1262
prefix = record.key[:-1]
1263
key = record.key[-1:]
1264
if record.parents is not None:
1265
parents = [parent[-1:] for parent in record.parents]
1268
thunk_record = AdapterFactory(key, parents, record)
1269
path = self._mapper.map(prefix)
1270
# Note that this parses the file many times; we can do better but
1271
# as this only impacts weaves in terms of performance, it is
1273
vf = self._get_vf(path)
1274
vf.insert_record_stream([thunk_record])
1276
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1277
"""Iterate over the lines in the versioned files from keys.
1279
This may return lines from other keys. Each item the returned
1280
iterator yields is a tuple of a line and a text version that that line
1281
is present in (not introduced in).
1283
Ordering of results is in whatever order is most suitable for the
1284
underlying storage format.
1286
If a progress bar is supplied, it may be used to indicate progress.
1287
The caller is responsible for cleaning up progress bars (because this
1291
* Lines are normalised by the underlying store: they will all have \n
1293
* Lines are returned in arbitrary order.
1295
:return: An iterator over (line, key).
1297
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1298
for line, version in vf.iter_lines_added_or_present_in_versions(suffixes):
1299
yield line, prefix + (version,)
1301
def _iter_all_components(self):
1302
for path, prefix in self._get_all_prefixes():
1303
yield prefix, self._get_vf(path)
1306
"""See VersionedFiles.keys()."""
1308
for prefix, vf in self._iter_all_components():
1309
for suffix in vf.versions():
1310
result.add(prefix + (suffix,))
1314
class _PlanMergeVersionedFile(VersionedFiles):
1315
"""A VersionedFile for uncommitted and committed texts.
1317
It is intended to allow merges to be planned with working tree texts.
1318
It implements only the small part of the VersionedFiles interface used by
1319
PlanMerge. It falls back to multiple versionedfiles for data not stored in
1320
_PlanMergeVersionedFile itself.
1322
:ivar: fallback_versionedfiles a list of VersionedFiles objects that can be
1323
queried for missing texts.
1326
def __init__(self, file_id):
1327
"""Create a _PlanMergeVersionedFile.
1329
:param file_id: Used with _PlanMerge code which is not yet fully
1330
tuple-keyspace aware.
1332
self._file_id = file_id
1333
# fallback locations
1334
self.fallback_versionedfiles = []
1335
# Parents for locally held keys.
1337
# line data for locally held keys.
1339
# key lookup providers
1340
self._providers = [DictParentsProvider(self._parents)]
1342
def plan_merge(self, ver_a, ver_b, base=None):
1343
"""See VersionedFile.plan_merge"""
1344
from bzrlib.merge import _PlanMerge
1346
return _PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge()
1347
old_plan = list(_PlanMerge(ver_a, base, self, (self._file_id,)).plan_merge())
1348
new_plan = list(_PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge())
1349
return _PlanMerge._subtract_plans(old_plan, new_plan)
1351
def plan_lca_merge(self, ver_a, ver_b, base=None):
1352
from bzrlib.merge import _PlanLCAMerge
1354
new_plan = _PlanLCAMerge(ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
1357
old_plan = _PlanLCAMerge(ver_a, base, self, (self._file_id,), graph).plan_merge()
1358
return _PlanLCAMerge._subtract_plans(list(old_plan), list(new_plan))
1360
def add_lines(self, key, parents, lines):
1361
"""See VersionedFiles.add_lines
1363
Lines are added locally, not to fallback versionedfiles. Also, ghosts
1364
are permitted. Only reserved ids are permitted.
1366
if type(key) is not tuple:
1367
raise TypeError(key)
1368
if not revision.is_reserved_id(key[-1]):
1369
raise ValueError('Only reserved ids may be used')
1371
raise ValueError('Parents may not be None')
1373
raise ValueError('Lines may not be None')
1374
self._parents[key] = tuple(parents)
1375
self._lines[key] = lines
1377
def get_record_stream(self, keys, ordering, include_delta_closure):
1380
if key in self._lines:
1381
lines = self._lines[key]
1382
parents = self._parents[key]
1384
yield ChunkedContentFactory(key, parents, None, lines)
1385
for versionedfile in self.fallback_versionedfiles:
1386
for record in versionedfile.get_record_stream(
1387
pending, 'unordered', True):
1388
if record.storage_kind == 'absent':
1391
pending.remove(record.key)
1395
# report absent entries
1397
yield AbsentContentFactory(key)
1399
def get_parent_map(self, keys):
1400
"""See VersionedFiles.get_parent_map"""
1401
# We create a new provider because a fallback may have been added.
1402
# If we make fallbacks private we can update a stack list and avoid
1403
# object creation thrashing.
1406
if revision.NULL_REVISION in keys:
1407
keys.remove(revision.NULL_REVISION)
1408
result[revision.NULL_REVISION] = ()
1409
self._providers = self._providers[:1] + self.fallback_versionedfiles
1411
StackedParentsProvider(self._providers).get_parent_map(keys))
1412
for key, parents in result.iteritems():
1414
result[key] = (revision.NULL_REVISION,)
1418
class PlanWeaveMerge(TextMerge):
1419
"""Weave merge that takes a plan as its input.
1421
This exists so that VersionedFile.plan_merge is implementable.
1422
Most callers will want to use WeaveMerge instead.
1425
def __init__(self, plan, a_marker=TextMerge.A_MARKER,
1426
b_marker=TextMerge.B_MARKER):
1427
TextMerge.__init__(self, a_marker, b_marker)
1428
self.plan = list(plan)
1430
def _merge_struct(self):
1435
def outstanding_struct():
1436
if not lines_a and not lines_b:
1438
elif ch_a and not ch_b:
1441
elif ch_b and not ch_a:
1443
elif lines_a == lines_b:
1446
yield (lines_a, lines_b)
1448
# We previously considered either 'unchanged' or 'killed-both' lines
1449
# to be possible places to resynchronize. However, assuming agreement
1450
# on killed-both lines may be too aggressive. -- mbp 20060324
1451
for state, line in self.plan:
1452
if state == 'unchanged':
1453
# resync and flush queued conflicts changes if any
1454
for struct in outstanding_struct():
1460
if state == 'unchanged':
1463
elif state == 'killed-a':
1465
lines_b.append(line)
1466
elif state == 'killed-b':
1468
lines_a.append(line)
1469
elif state == 'new-a':
1471
lines_a.append(line)
1472
elif state == 'new-b':
1474
lines_b.append(line)
1475
elif state == 'conflicted-a':
1477
lines_a.append(line)
1478
elif state == 'conflicted-b':
1480
lines_b.append(line)
1481
elif state == 'killed-both':
1482
# This counts as a change, even though there is no associated
1486
if state not in ('irrelevant', 'ghost-a', 'ghost-b',
1488
raise AssertionError(state)
1489
for struct in outstanding_struct():
1492
def base_from_plan(self):
1493
"""Construct a BASE file from the plan text."""
1495
for state, line in self.plan:
1496
if state in ('killed-a', 'killed-b', 'killed-both', 'unchanged'):
1497
# If unchanged, then this line is straight from base. If a or b
1498
# or both killed the line, then it *used* to be in base.
1499
base_lines.append(line)
1501
if state not in ('killed-base', 'irrelevant',
1502
'ghost-a', 'ghost-b',
1504
'conflicted-a', 'conflicted-b'):
1505
# killed-base, irrelevant means it doesn't apply
1506
# ghost-a/ghost-b are harder to say for sure, but they
1507
# aren't in the 'inc_c' which means they aren't in the
1508
# shared base of a & b. So we don't include them. And
1509
# obviously if the line is newly inserted, it isn't in base
1511
# If 'conflicted-a' or b, then it is new vs one base, but
1512
# old versus another base. However, if we make it present
1513
# in the base, it will be deleted from the target, and it
1514
# seems better to get a line doubled in the merge result,
1515
# rather than have it deleted entirely.
1516
# Example, each node is the 'text' at that point:
1524
# There was a criss-cross conflict merge. Both sides
1525
# include the other, but put themselves first.
1526
# Weave marks this as a 'clean' merge, picking OTHER over
1527
# THIS. (Though the details depend on order inserted into
1529
# LCA generates a plan:
1530
# [('unchanged', M),
1531
# ('conflicted-b', b),
1533
# ('conflicted-a', b),
1535
# If you mark 'conflicted-*' as part of BASE, then a 3-way
1536
# merge tool will cleanly generate "MaN" (as BASE vs THIS
1537
# removes one 'b', and BASE vs OTHER removes the other)
1538
# If you include neither, 3-way creates a clean "MbabN" as
1539
# THIS adds one 'b', and OTHER does too.
1540
# It seems that having the line 2 times is better than
1541
# having it omitted. (Easier to manually delete than notice
1542
# it needs to be added.)
1543
raise AssertionError('Unknown state: %s' % (state,))
1547
class WeaveMerge(PlanWeaveMerge):
1548
"""Weave merge that takes a VersionedFile and two versions as its input."""
1550
def __init__(self, versionedfile, ver_a, ver_b,
1551
a_marker=PlanWeaveMerge.A_MARKER, b_marker=PlanWeaveMerge.B_MARKER):
1552
plan = versionedfile.plan_merge(ver_a, ver_b)
1553
PlanWeaveMerge.__init__(self, plan, a_marker, b_marker)
1556
class VirtualVersionedFiles(VersionedFiles):
1557
"""Dummy implementation for VersionedFiles that uses other functions for
1558
obtaining fulltexts and parent maps.
1560
This is always on the bottom of the stack and uses string keys
1561
(rather than tuples) internally.
1564
def __init__(self, get_parent_map, get_lines):
1565
"""Create a VirtualVersionedFiles.
1567
:param get_parent_map: Same signature as Repository.get_parent_map.
1568
:param get_lines: Should return lines for specified key or None if
1571
super(VirtualVersionedFiles, self).__init__()
1572
self._get_parent_map = get_parent_map
1573
self._get_lines = get_lines
1575
def check(self, progressbar=None):
1576
"""See VersionedFiles.check.
1578
:note: Always returns True for VirtualVersionedFiles.
1582
def add_mpdiffs(self, records):
1583
"""See VersionedFiles.mpdiffs.
1585
:note: Not implemented for VirtualVersionedFiles.
1587
raise NotImplementedError(self.add_mpdiffs)
1589
def get_parent_map(self, keys):
1590
"""See VersionedFiles.get_parent_map."""
1591
return dict([((k,), tuple([(p,) for p in v]))
1592
for k,v in self._get_parent_map([k for (k,) in keys]).iteritems()])
1594
def get_sha1s(self, keys):
1595
"""See VersionedFiles.get_sha1s."""
1598
lines = self._get_lines(k)
1599
if lines is not None:
1600
if not isinstance(lines, list):
1601
raise AssertionError
1602
ret[(k,)] = osutils.sha_strings(lines)
1605
def get_record_stream(self, keys, ordering, include_delta_closure):
1606
"""See VersionedFiles.get_record_stream."""
1607
for (k,) in list(keys):
1608
lines = self._get_lines(k)
1609
if lines is not None:
1610
if not isinstance(lines, list):
1611
raise AssertionError
1612
yield ChunkedContentFactory((k,), None,
1613
sha1=osutils.sha_strings(lines),
1616
yield AbsentContentFactory((k,))
1618
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1619
"""See VersionedFile.iter_lines_added_or_present_in_versions()."""
1620
for i, (key,) in enumerate(keys):
1622
pb.update("Finding changed lines", i, len(keys))
1623
for l in self._get_lines(key):
1627
def network_bytes_to_kind_and_offset(network_bytes):
1628
"""Strip of a record kind from the front of network_bytes.
1630
:param network_bytes: The bytes of a record.
1631
:return: A tuple (storage_kind, offset_of_remaining_bytes)
1633
line_end = network_bytes.find('\n')
1634
storage_kind = network_bytes[:line_end]
1635
return storage_kind, line_end + 1
1638
class NetworkRecordStream(object):
1639
"""A record_stream which reconstitures a serialised stream."""
1641
def __init__(self, bytes_iterator):
1642
"""Create a NetworkRecordStream.
1644
:param bytes_iterator: An iterator of bytes. Each item in this
1645
iterator should have been obtained from a record_streams'
1646
record.get_bytes_as(record.storage_kind) call.
1648
self._bytes_iterator = bytes_iterator
1649
self._kind_factory = {
1650
'fulltext': fulltext_network_to_record,
1651
'groupcompress-block': groupcompress.network_block_to_records,
1652
'knit-ft-gz': knit.knit_network_to_record,
1653
'knit-delta-gz': knit.knit_network_to_record,
1654
'knit-annotated-ft-gz': knit.knit_network_to_record,
1655
'knit-annotated-delta-gz': knit.knit_network_to_record,
1656
'knit-delta-closure': knit.knit_delta_closure_to_records,
1662
:return: An iterator as per VersionedFiles.get_record_stream().
1664
for bytes in self._bytes_iterator:
1665
storage_kind, line_end = network_bytes_to_kind_and_offset(bytes)
1666
for record in self._kind_factory[storage_kind](
1667
storage_kind, bytes, line_end):
1671
def fulltext_network_to_record(kind, bytes, line_end):
1672
"""Convert a network fulltext record to record."""
1673
meta_len, = struct.unpack('!L', bytes[line_end:line_end+4])
1674
record_meta = bytes[line_end+4:line_end+4+meta_len]
1675
key, parents = bencode.bdecode_as_tuple(record_meta)
1676
if parents == 'nil':
1678
fulltext = bytes[line_end+4+meta_len:]
1679
return [FulltextContentFactory(key, parents, None, fulltext)]
1682
def _length_prefix(bytes):
1683
return struct.pack('!L', len(bytes))
1686
def record_to_fulltext_bytes(record):
1687
if record.parents is None:
1690
parents = record.parents
1691
record_meta = bencode.bencode((record.key, parents))
1692
record_content = record.get_bytes_as('fulltext')
1693
return "fulltext\n%s%s%s" % (
1694
_length_prefix(record_meta), record_meta, record_content)
1697
def sort_groupcompress(parent_map):
1698
"""Sort and group the keys in parent_map into groupcompress order.
1700
groupcompress is defined (currently) as reverse-topological order, grouped
1703
:return: A sorted-list of keys
1705
# gc-optimal ordering is approximately reverse topological,
1706
# properly grouped by file-id.
1708
for item in parent_map.iteritems():
1710
if isinstance(key, str) or len(key) == 1:
1715
per_prefix_map[prefix].append(item)
1717
per_prefix_map[prefix] = [item]
1720
for prefix in sorted(per_prefix_map):
1721
present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
added
removed
bzrlib/versionedfile.py
