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.inter import InterObject
49
from bzrlib.registry import Registry
50
from bzrlib.symbol_versioning import *
51
from bzrlib.textmerge import TextMerge
52
from bzrlib import bencode
55
adapter_registry = Registry()
56
adapter_registry.register_lazy(('knit-delta-gz', 'fulltext'), 'bzrlib.knit',
57
'DeltaPlainToFullText')
58
adapter_registry.register_lazy(('knit-ft-gz', 'fulltext'), 'bzrlib.knit',
60
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'knit-delta-gz'),
61
'bzrlib.knit', 'DeltaAnnotatedToUnannotated')
62
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'fulltext'),
63
'bzrlib.knit', 'DeltaAnnotatedToFullText')
64
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'knit-ft-gz'),
65
'bzrlib.knit', 'FTAnnotatedToUnannotated')
66
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'fulltext'),
67
'bzrlib.knit', 'FTAnnotatedToFullText')
68
# adapter_registry.register_lazy(('knit-annotated-ft-gz', 'chunked'),
69
# 'bzrlib.knit', 'FTAnnotatedToChunked')
72
class ContentFactory(object):
73
"""Abstract interface for insertion and retrieval from a VersionedFile.
75
:ivar sha1: None, or the sha1 of the content fulltext.
76
:ivar storage_kind: The native storage kind of this factory. One of
77
'mpdiff', 'knit-annotated-ft', 'knit-annotated-delta', 'knit-ft',
78
'knit-delta', 'fulltext', 'knit-annotated-ft-gz',
79
'knit-annotated-delta-gz', 'knit-ft-gz', 'knit-delta-gz'.
80
:ivar key: The key of this content. Each key is a tuple with a single
82
:ivar parents: A tuple of parent keys for self.key. If the object has
83
no parent information, None (as opposed to () for an empty list of
88
"""Create a ContentFactory."""
90
self.storage_kind = None
95
class ChunkedContentFactory(ContentFactory):
96
"""Static data content factory.
98
This takes a 'chunked' list of strings. The only requirement on 'chunked' is
99
that ''.join(lines) becomes a valid fulltext. A tuple of a single string
100
satisfies this, as does a list of lines.
102
:ivar sha1: None, or the sha1 of the content fulltext.
103
:ivar storage_kind: The native storage kind of this factory. Always
105
:ivar key: The key of this content. Each key is a tuple with a single
107
:ivar parents: A tuple of parent keys for self.key. If the object has
108
no parent information, None (as opposed to () for an empty list of
112
def __init__(self, key, parents, sha1, chunks):
113
"""Create a ContentFactory."""
115
self.storage_kind = 'chunked'
117
self.parents = parents
118
self._chunks = chunks
120
def get_bytes_as(self, storage_kind):
121
if storage_kind == 'chunked':
123
elif storage_kind == 'fulltext':
124
return ''.join(self._chunks)
125
raise errors.UnavailableRepresentation(self.key, storage_kind,
129
class FulltextContentFactory(ContentFactory):
130
"""Static data content factory.
132
This takes a fulltext when created and just returns that during
133
get_bytes_as('fulltext').
135
:ivar sha1: None, or the sha1 of the content fulltext.
136
:ivar storage_kind: The native storage kind of this factory. Always
138
:ivar key: The key of this content. Each key is a tuple with a single
140
:ivar parents: A tuple of parent keys for self.key. If the object has
141
no parent information, None (as opposed to () for an empty list of
145
def __init__(self, key, parents, sha1, text):
146
"""Create a ContentFactory."""
148
self.storage_kind = 'fulltext'
150
self.parents = parents
153
def get_bytes_as(self, storage_kind):
154
if storage_kind == self.storage_kind:
156
elif storage_kind == 'chunked':
158
raise errors.UnavailableRepresentation(self.key, storage_kind,
162
class AbsentContentFactory(ContentFactory):
163
"""A placeholder content factory for unavailable texts.
166
:ivar storage_kind: 'absent'.
167
:ivar key: The key of this content. Each key is a tuple with a single
172
def __init__(self, key):
173
"""Create a ContentFactory."""
175
self.storage_kind = 'absent'
179
def get_bytes_as(self, storage_kind):
180
raise ValueError('A request was made for key: %s, but that'
181
' content is not available, and the calling'
182
' code does not handle if it is missing.'
186
class AdapterFactory(ContentFactory):
187
"""A content factory to adapt between key prefix's."""
189
def __init__(self, key, parents, adapted):
190
"""Create an adapter factory instance."""
192
self.parents = parents
193
self._adapted = adapted
195
def __getattr__(self, attr):
196
"""Return a member from the adapted object."""
197
if attr in ('key', 'parents'):
198
return self.__dict__[attr]
200
return getattr(self._adapted, attr)
203
def filter_absent(record_stream):
204
"""Adapt a record stream to remove absent records."""
205
for record in record_stream:
206
if record.storage_kind != 'absent':
210
class VersionedFile(object):
211
"""Versioned text file storage.
213
A versioned file manages versions of line-based text files,
214
keeping track of the originating version for each line.
216
To clients the "lines" of the file are represented as a list of
217
strings. These strings will typically have terminal newline
218
characters, but this is not required. In particular files commonly
219
do not have a newline at the end of the file.
221
Texts are identified by a version-id string.
225
def check_not_reserved_id(version_id):
226
revision.check_not_reserved_id(version_id)
228
def copy_to(self, name, transport):
229
"""Copy this versioned file to name on transport."""
230
raise NotImplementedError(self.copy_to)
232
def get_record_stream(self, versions, ordering, include_delta_closure):
233
"""Get a stream of records for versions.
235
:param versions: The versions to include. Each version is a tuple
237
:param ordering: Either 'unordered' or 'topological'. A topologically
238
sorted stream has compression parents strictly before their
240
:param include_delta_closure: If True then the closure across any
241
compression parents will be included (in the data content of the
242
stream, not in the emitted records). This guarantees that
243
'fulltext' can be used successfully on every record.
244
:return: An iterator of ContentFactory objects, each of which is only
245
valid until the iterator is advanced.
247
raise NotImplementedError(self.get_record_stream)
249
def has_version(self, version_id):
250
"""Returns whether version is present."""
251
raise NotImplementedError(self.has_version)
253
def insert_record_stream(self, stream):
254
"""Insert a record stream into this versioned file.
256
:param stream: A stream of records to insert.
258
:seealso VersionedFile.get_record_stream:
260
raise NotImplementedError
262
def add_lines(self, version_id, parents, lines, parent_texts=None,
263
left_matching_blocks=None, nostore_sha=None, random_id=False,
265
"""Add a single text on top of the versioned file.
267
Must raise RevisionAlreadyPresent if the new version is
268
already present in file history.
270
Must raise RevisionNotPresent if any of the given parents are
271
not present in file history.
273
:param lines: A list of lines. Each line must be a bytestring. And all
274
of them except the last must be terminated with \n and contain no
275
other \n's. The last line may either contain no \n's or a single
276
terminated \n. If the lines list does meet this constraint the add
277
routine may error or may succeed - but you will be unable to read
278
the data back accurately. (Checking the lines have been split
279
correctly is expensive and extremely unlikely to catch bugs so it
280
is not done at runtime unless check_content is True.)
281
:param parent_texts: An optional dictionary containing the opaque
282
representations of some or all of the parents of version_id to
283
allow delta optimisations. VERY IMPORTANT: the texts must be those
284
returned by add_lines or data corruption can be caused.
285
:param left_matching_blocks: a hint about which areas are common
286
between the text and its left-hand-parent. The format is
287
the SequenceMatcher.get_matching_blocks format.
288
:param nostore_sha: Raise ExistingContent and do not add the lines to
289
the versioned file if the digest of the lines matches this.
290
:param random_id: If True a random id has been selected rather than
291
an id determined by some deterministic process such as a converter
292
from a foreign VCS. When True the backend may choose not to check
293
for uniqueness of the resulting key within the versioned file, so
294
this should only be done when the result is expected to be unique
296
:param check_content: If True, the lines supplied are verified to be
297
bytestrings that are correctly formed lines.
298
:return: The text sha1, the number of bytes in the text, and an opaque
299
representation of the inserted version which can be provided
300
back to future add_lines calls in the parent_texts dictionary.
302
self._check_write_ok()
303
return self._add_lines(version_id, parents, lines, parent_texts,
304
left_matching_blocks, nostore_sha, random_id, check_content)
306
def _add_lines(self, version_id, parents, lines, parent_texts,
307
left_matching_blocks, nostore_sha, random_id, check_content):
308
"""Helper to do the class specific add_lines."""
309
raise NotImplementedError(self.add_lines)
311
def add_lines_with_ghosts(self, version_id, parents, lines,
312
parent_texts=None, nostore_sha=None, random_id=False,
313
check_content=True, left_matching_blocks=None):
314
"""Add lines to the versioned file, allowing ghosts to be present.
316
This takes the same parameters as add_lines and returns the same.
318
self._check_write_ok()
319
return self._add_lines_with_ghosts(version_id, parents, lines,
320
parent_texts, nostore_sha, random_id, check_content, left_matching_blocks)
322
def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts,
323
nostore_sha, random_id, check_content, left_matching_blocks):
324
"""Helper to do class specific add_lines_with_ghosts."""
325
raise NotImplementedError(self.add_lines_with_ghosts)
327
def check(self, progress_bar=None):
328
"""Check the versioned file for integrity."""
329
raise NotImplementedError(self.check)
331
def _check_lines_not_unicode(self, lines):
332
"""Check that lines being added to a versioned file are not unicode."""
334
if line.__class__ is not str:
335
raise errors.BzrBadParameterUnicode("lines")
337
def _check_lines_are_lines(self, lines):
338
"""Check that the lines really are full lines without inline EOL."""
340
if '\n' in line[:-1]:
341
raise errors.BzrBadParameterContainsNewline("lines")
343
def get_format_signature(self):
344
"""Get a text description of the data encoding in this file.
348
raise NotImplementedError(self.get_format_signature)
350
def make_mpdiffs(self, version_ids):
351
"""Create multiparent diffs for specified versions."""
352
knit_versions = set()
353
knit_versions.update(version_ids)
354
parent_map = self.get_parent_map(version_ids)
355
for version_id in version_ids:
357
knit_versions.update(parent_map[version_id])
359
raise errors.RevisionNotPresent(version_id, self)
360
# We need to filter out ghosts, because we can't diff against them.
361
knit_versions = set(self.get_parent_map(knit_versions).keys())
362
lines = dict(zip(knit_versions,
363
self._get_lf_split_line_list(knit_versions)))
365
for version_id in version_ids:
366
target = lines[version_id]
368
parents = [lines[p] for p in parent_map[version_id] if p in
371
# I don't know how this could ever trigger.
372
# parent_map[version_id] was already triggered in the previous
373
# for loop, and lines[p] has the 'if p in knit_versions' check,
374
# so we again won't have a KeyError.
375
raise errors.RevisionNotPresent(version_id, self)
377
left_parent_blocks = self._extract_blocks(version_id,
380
left_parent_blocks = None
381
diffs.append(multiparent.MultiParent.from_lines(target, parents,
385
def _extract_blocks(self, version_id, source, target):
388
def add_mpdiffs(self, records):
389
"""Add mpdiffs to this VersionedFile.
391
Records should be iterables of version, parents, expected_sha1,
392
mpdiff. mpdiff should be a MultiParent instance.
394
# Does this need to call self._check_write_ok()? (IanC 20070919)
396
mpvf = multiparent.MultiMemoryVersionedFile()
398
for version, parent_ids, expected_sha1, mpdiff in records:
399
versions.append(version)
400
mpvf.add_diff(mpdiff, version, parent_ids)
401
needed_parents = set()
402
for version, parent_ids, expected_sha1, mpdiff in records:
403
needed_parents.update(p for p in parent_ids
404
if not mpvf.has_version(p))
405
present_parents = set(self.get_parent_map(needed_parents).keys())
406
for parent_id, lines in zip(present_parents,
407
self._get_lf_split_line_list(present_parents)):
408
mpvf.add_version(lines, parent_id, [])
409
for (version, parent_ids, expected_sha1, mpdiff), lines in\
410
zip(records, mpvf.get_line_list(versions)):
411
if len(parent_ids) == 1:
412
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
413
mpvf.get_diff(parent_ids[0]).num_lines()))
415
left_matching_blocks = None
417
_, _, version_text = self.add_lines_with_ghosts(version,
418
parent_ids, lines, vf_parents,
419
left_matching_blocks=left_matching_blocks)
420
except NotImplementedError:
421
# The vf can't handle ghosts, so add lines normally, which will
422
# (reasonably) fail if there are ghosts in the data.
423
_, _, version_text = self.add_lines(version,
424
parent_ids, lines, vf_parents,
425
left_matching_blocks=left_matching_blocks)
426
vf_parents[version] = version_text
427
sha1s = self.get_sha1s(versions)
428
for version, parent_ids, expected_sha1, mpdiff in records:
429
if expected_sha1 != sha1s[version]:
430
raise errors.VersionedFileInvalidChecksum(version)
432
def get_text(self, version_id):
433
"""Return version contents as a text string.
435
Raises RevisionNotPresent if version is not present in
438
return ''.join(self.get_lines(version_id))
439
get_string = get_text
441
def get_texts(self, version_ids):
442
"""Return the texts of listed versions as a list of strings.
444
Raises RevisionNotPresent if version is not present in
447
return [''.join(self.get_lines(v)) for v in version_ids]
449
def get_lines(self, version_id):
450
"""Return version contents as a sequence of lines.
452
Raises RevisionNotPresent if version is not present in
455
raise NotImplementedError(self.get_lines)
457
def _get_lf_split_line_list(self, version_ids):
458
return [StringIO(t).readlines() for t in self.get_texts(version_ids)]
460
def get_ancestry(self, version_ids, topo_sorted=True):
461
"""Return a list of all ancestors of given version(s). This
462
will not include the null revision.
464
This list will not be topologically sorted if topo_sorted=False is
467
Must raise RevisionNotPresent if any of the given versions are
468
not present in file history."""
469
if isinstance(version_ids, basestring):
470
version_ids = [version_ids]
471
raise NotImplementedError(self.get_ancestry)
473
def get_ancestry_with_ghosts(self, version_ids):
474
"""Return a list of all ancestors of given version(s). This
475
will not include the null revision.
477
Must raise RevisionNotPresent if any of the given versions are
478
not present in file history.
480
Ghosts that are known about will be included in ancestry list,
481
but are not explicitly marked.
483
raise NotImplementedError(self.get_ancestry_with_ghosts)
485
def get_parent_map(self, version_ids):
486
"""Get a map of the parents of version_ids.
488
:param version_ids: The version ids to look up parents for.
489
:return: A mapping from version id to parents.
491
raise NotImplementedError(self.get_parent_map)
493
def get_parents_with_ghosts(self, version_id):
494
"""Return version names for parents of version_id.
496
Will raise RevisionNotPresent if version_id is not present
499
Ghosts that are known about will be included in the parent list,
500
but are not explicitly marked.
503
return list(self.get_parent_map([version_id])[version_id])
505
raise errors.RevisionNotPresent(version_id, self)
507
def annotate(self, version_id):
508
"""Return a list of (version-id, line) tuples for version_id.
510
:raise RevisionNotPresent: If the given version is
511
not present in file history.
513
raise NotImplementedError(self.annotate)
515
def iter_lines_added_or_present_in_versions(self, version_ids=None,
517
"""Iterate over the lines in the versioned file from version_ids.
519
This may return lines from other versions. Each item the returned
520
iterator yields is a tuple of a line and a text version that that line
521
is present in (not introduced in).
523
Ordering of results is in whatever order is most suitable for the
524
underlying storage format.
526
If a progress bar is supplied, it may be used to indicate progress.
527
The caller is responsible for cleaning up progress bars (because this
530
NOTES: Lines are normalised: they will all have \n terminators.
531
Lines are returned in arbitrary order.
533
:return: An iterator over (line, version_id).
535
raise NotImplementedError(self.iter_lines_added_or_present_in_versions)
537
def plan_merge(self, ver_a, ver_b):
538
"""Return pseudo-annotation indicating how the two versions merge.
540
This is computed between versions a and b and their common
543
Weave lines present in none of them are skipped entirely.
546
killed-base Dead in base revision
547
killed-both Killed in each revision
550
unchanged Alive in both a and b (possibly created in both)
553
ghost-a Killed in a, unborn in b
554
ghost-b Killed in b, unborn in a
555
irrelevant Not in either revision
557
raise NotImplementedError(VersionedFile.plan_merge)
559
def weave_merge(self, plan, a_marker=TextMerge.A_MARKER,
560
b_marker=TextMerge.B_MARKER):
561
return PlanWeaveMerge(plan, a_marker, b_marker).merge_lines()[0]
564
class RecordingVersionedFilesDecorator(object):
565
"""A minimal versioned files that records calls made on it.
567
Only enough methods have been added to support tests using it to date.
569
:ivar calls: A list of the calls made; can be reset at any time by
573
def __init__(self, backing_vf):
574
"""Create a RecordingVersionedFilesDecorator decorating backing_vf.
576
:param backing_vf: The versioned file to answer all methods.
578
self._backing_vf = backing_vf
581
def add_lines(self, key, parents, lines, parent_texts=None,
582
left_matching_blocks=None, nostore_sha=None, random_id=False,
584
self.calls.append(("add_lines", key, parents, lines, parent_texts,
585
left_matching_blocks, nostore_sha, random_id, check_content))
586
return self._backing_vf.add_lines(key, parents, lines, parent_texts,
587
left_matching_blocks, nostore_sha, random_id, check_content)
590
self._backing_vf.check()
592
def get_parent_map(self, keys):
593
self.calls.append(("get_parent_map", copy(keys)))
594
return self._backing_vf.get_parent_map(keys)
596
def get_record_stream(self, keys, sort_order, include_delta_closure):
597
self.calls.append(("get_record_stream", list(keys), sort_order,
598
include_delta_closure))
599
return self._backing_vf.get_record_stream(keys, sort_order,
600
include_delta_closure)
602
def get_sha1s(self, keys):
603
self.calls.append(("get_sha1s", copy(keys)))
604
return self._backing_vf.get_sha1s(keys)
606
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
607
self.calls.append(("iter_lines_added_or_present_in_keys", copy(keys)))
608
return self._backing_vf.iter_lines_added_or_present_in_keys(keys, pb=pb)
611
self.calls.append(("keys",))
612
return self._backing_vf.keys()
615
class OrderingVersionedFilesDecorator(RecordingVersionedFilesDecorator):
616
"""A VF that records calls, and returns keys in specific order.
618
:ivar calls: A list of the calls made; can be reset at any time by
622
def __init__(self, backing_vf, key_priority):
623
"""Create a RecordingVersionedFilesDecorator decorating backing_vf.
625
:param backing_vf: The versioned file to answer all methods.
626
:param key_priority: A dictionary defining what order keys should be
627
returned from an 'unordered' get_record_stream request.
628
Keys with lower priority are returned first, keys not present in
629
the map get an implicit priority of 0, and are returned in
630
lexicographical order.
632
RecordingVersionedFilesDecorator.__init__(self, backing_vf)
633
self._key_priority = key_priority
635
def get_record_stream(self, keys, sort_order, include_delta_closure):
636
self.calls.append(("get_record_stream", list(keys), sort_order,
637
include_delta_closure))
638
if sort_order == 'unordered':
640
return (self._key_priority.get(key, 0), key)
641
# Use a defined order by asking for the keys one-by-one from the
643
for key in sorted(keys, key=sort_key):
644
for record in self._backing_vf.get_record_stream([key],
645
'unordered', include_delta_closure):
648
for record in self._backing_vf.get_record_stream(keys, sort_order,
649
include_delta_closure):
653
class KeyMapper(object):
654
"""KeyMappers map between keys and underlying partitioned storage."""
657
"""Map key to an underlying storage identifier.
659
:param key: A key tuple e.g. ('file-id', 'revision-id').
660
:return: An underlying storage identifier, specific to the partitioning
663
raise NotImplementedError(self.map)
665
def unmap(self, partition_id):
666
"""Map a partitioned storage id back to a key prefix.
668
:param partition_id: The underlying partition id.
669
:return: As much of a key (or prefix) as is derivable from the partition
672
raise NotImplementedError(self.unmap)
675
class ConstantMapper(KeyMapper):
676
"""A key mapper that maps to a constant result."""
678
def __init__(self, result):
679
"""Create a ConstantMapper which will return result for all maps."""
680
self._result = result
683
"""See KeyMapper.map()."""
687
class URLEscapeMapper(KeyMapper):
688
"""Base class for use with transport backed storage.
690
This provides a map and unmap wrapper that respectively url escape and
691
unescape their outputs and inputs.
695
"""See KeyMapper.map()."""
696
return urllib.quote(self._map(key))
698
def unmap(self, partition_id):
699
"""See KeyMapper.unmap()."""
700
return self._unmap(urllib.unquote(partition_id))
703
class PrefixMapper(URLEscapeMapper):
704
"""A key mapper that extracts the first component of a key.
706
This mapper is for use with a transport based backend.
710
"""See KeyMapper.map()."""
713
def _unmap(self, partition_id):
714
"""See KeyMapper.unmap()."""
715
return (partition_id,)
718
class HashPrefixMapper(URLEscapeMapper):
719
"""A key mapper that combines the first component of a key with a hash.
721
This mapper is for use with a transport based backend.
725
"""See KeyMapper.map()."""
726
prefix = self._escape(key[0])
727
return "%02x/%s" % (adler32(prefix) & 0xff, prefix)
729
def _escape(self, prefix):
730
"""No escaping needed here."""
733
def _unmap(self, partition_id):
734
"""See KeyMapper.unmap()."""
735
return (self._unescape(osutils.basename(partition_id)),)
737
def _unescape(self, basename):
738
"""No unescaping needed for HashPrefixMapper."""
742
class HashEscapedPrefixMapper(HashPrefixMapper):
743
"""Combines the escaped first component of a key with a hash.
745
This mapper is for use with a transport based backend.
748
_safe = "abcdefghijklmnopqrstuvwxyz0123456789-_@,."
750
def _escape(self, prefix):
751
"""Turn a key element into a filesystem safe string.
753
This is similar to a plain urllib.quote, except
754
it uses specific safe characters, so that it doesn't
755
have to translate a lot of valid file ids.
757
# @ does not get escaped. This is because it is a valid
758
# filesystem character we use all the time, and it looks
759
# a lot better than seeing %40 all the time.
760
r = [((c in self._safe) and c or ('%%%02x' % ord(c)))
764
def _unescape(self, basename):
765
"""Escaped names are easily unescaped by urlutils."""
766
return urllib.unquote(basename)
769
def make_versioned_files_factory(versioned_file_factory, mapper):
770
"""Create a ThunkedVersionedFiles factory.
772
This will create a callable which when called creates a
773
ThunkedVersionedFiles on a transport, using mapper to access individual
774
versioned files, and versioned_file_factory to create each individual file.
776
def factory(transport):
777
return ThunkedVersionedFiles(transport, versioned_file_factory, mapper,
782
class VersionedFiles(object):
783
"""Storage for many versioned files.
785
This object allows a single keyspace for accessing the history graph and
786
contents of named bytestrings.
788
Currently no implementation allows the graph of different key prefixes to
789
intersect, but the API does allow such implementations in the future.
791
The keyspace is expressed via simple tuples. Any instance of VersionedFiles
792
may have a different length key-size, but that size will be constant for
793
all texts added to or retrieved from it. For instance, bzrlib uses
794
instances with a key-size of 2 for storing user files in a repository, with
795
the first element the fileid, and the second the version of that file.
797
The use of tuples allows a single code base to support several different
798
uses with only the mapping logic changing from instance to instance.
801
def add_lines(self, key, parents, lines, parent_texts=None,
802
left_matching_blocks=None, nostore_sha=None, random_id=False,
804
"""Add a text to the store.
806
:param key: The key tuple of the text to add. If the last element is
807
None, a CHK string will be generated during the addition.
808
:param parents: The parents key tuples of the text to add.
809
:param lines: A list of lines. Each line must be a bytestring. And all
810
of them except the last must be terminated with \n and contain no
811
other \n's. The last line may either contain no \n's or a single
812
terminating \n. If the lines list does meet this constraint the add
813
routine may error or may succeed - but you will be unable to read
814
the data back accurately. (Checking the lines have been split
815
correctly is expensive and extremely unlikely to catch bugs so it
816
is not done at runtime unless check_content is True.)
817
:param parent_texts: An optional dictionary containing the opaque
818
representations of some or all of the parents of version_id to
819
allow delta optimisations. VERY IMPORTANT: the texts must be those
820
returned by add_lines or data corruption can be caused.
821
:param left_matching_blocks: a hint about which areas are common
822
between the text and its left-hand-parent. The format is
823
the SequenceMatcher.get_matching_blocks format.
824
:param nostore_sha: Raise ExistingContent and do not add the lines to
825
the versioned file if the digest of the lines matches this.
826
:param random_id: If True a random id has been selected rather than
827
an id determined by some deterministic process such as a converter
828
from a foreign VCS. When True the backend may choose not to check
829
for uniqueness of the resulting key within the versioned file, so
830
this should only be done when the result is expected to be unique
832
:param check_content: If True, the lines supplied are verified to be
833
bytestrings that are correctly formed lines.
834
:return: The text sha1, the number of bytes in the text, and an opaque
835
representation of the inserted version which can be provided
836
back to future add_lines calls in the parent_texts dictionary.
838
raise NotImplementedError(self.add_lines)
840
def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
841
"""Add a text to the store.
843
This is a private function for use by CommitBuilder.
845
:param key: The key tuple of the text to add. If the last element is
846
None, a CHK string will be generated during the addition.
847
:param parents: The parents key tuples of the text to add.
848
:param text: A string containing the text to be committed.
849
:param nostore_sha: Raise ExistingContent and do not add the lines to
850
the versioned file if the digest of the lines matches this.
851
:param random_id: If True a random id has been selected rather than
852
an id determined by some deterministic process such as a converter
853
from a foreign VCS. When True the backend may choose not to check
854
for uniqueness of the resulting key within the versioned file, so
855
this should only be done when the result is expected to be unique
857
:param check_content: If True, the lines supplied are verified to be
858
bytestrings that are correctly formed lines.
859
:return: The text sha1, the number of bytes in the text, and an opaque
860
representation of the inserted version which can be provided
861
back to future _add_text calls in the parent_texts dictionary.
863
# The default implementation just thunks over to .add_lines(),
864
# inefficient, but it works.
865
return self.add_lines(key, parents, osutils.split_lines(text),
866
nostore_sha=nostore_sha,
870
def add_mpdiffs(self, records):
871
"""Add mpdiffs to this VersionedFile.
873
Records should be iterables of version, parents, expected_sha1,
874
mpdiff. mpdiff should be a MultiParent instance.
877
mpvf = multiparent.MultiMemoryVersionedFile()
879
for version, parent_ids, expected_sha1, mpdiff in records:
880
versions.append(version)
881
mpvf.add_diff(mpdiff, version, parent_ids)
882
needed_parents = set()
883
for version, parent_ids, expected_sha1, mpdiff in records:
884
needed_parents.update(p for p in parent_ids
885
if not mpvf.has_version(p))
886
# It seems likely that adding all the present parents as fulltexts can
887
# easily exhaust memory.
888
chunks_to_lines = osutils.chunks_to_lines
889
for record in self.get_record_stream(needed_parents, 'unordered',
891
if record.storage_kind == 'absent':
893
mpvf.add_version(chunks_to_lines(record.get_bytes_as('chunked')),
895
for (key, parent_keys, expected_sha1, mpdiff), lines in\
896
zip(records, mpvf.get_line_list(versions)):
897
if len(parent_keys) == 1:
898
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
899
mpvf.get_diff(parent_keys[0]).num_lines()))
901
left_matching_blocks = None
902
version_sha1, _, version_text = self.add_lines(key,
903
parent_keys, lines, vf_parents,
904
left_matching_blocks=left_matching_blocks)
905
if version_sha1 != expected_sha1:
906
raise errors.VersionedFileInvalidChecksum(version)
907
vf_parents[key] = version_text
909
def annotate(self, key):
910
"""Return a list of (version-key, line) tuples for the text of key.
912
:raise RevisionNotPresent: If the key is not present.
914
raise NotImplementedError(self.annotate)
916
def check(self, progress_bar=None):
917
"""Check this object for integrity.
919
:param progress_bar: A progress bar to output as the check progresses.
920
:param keys: Specific keys within the VersionedFiles to check. When
921
this parameter is not None, check() becomes a generator as per
922
get_record_stream. The difference to get_record_stream is that
923
more or deeper checks will be performed.
924
:return: None, or if keys was supplied a generator as per
927
raise NotImplementedError(self.check)
930
def check_not_reserved_id(version_id):
931
revision.check_not_reserved_id(version_id)
933
def clear_cache(self):
934
"""Clear whatever caches this VersionedFile holds.
936
This is generally called after an operation has been performed, when we
937
don't expect to be using this versioned file again soon.
940
def _check_lines_not_unicode(self, lines):
941
"""Check that lines being added to a versioned file are not unicode."""
943
if line.__class__ is not str:
944
raise errors.BzrBadParameterUnicode("lines")
946
def _check_lines_are_lines(self, lines):
947
"""Check that the lines really are full lines without inline EOL."""
949
if '\n' in line[:-1]:
950
raise errors.BzrBadParameterContainsNewline("lines")
952
def get_known_graph_ancestry(self, keys):
953
"""Get a KnownGraph instance with the ancestry of keys."""
954
# most basic implementation is a loop around get_parent_map
958
this_parent_map = self.get_parent_map(pending)
959
parent_map.update(this_parent_map)
961
map(pending.update, this_parent_map.itervalues())
962
pending = pending.difference(parent_map)
963
kg = _mod_graph.KnownGraph(parent_map)
966
def get_parent_map(self, keys):
967
"""Get a map of the parents of keys.
969
:param keys: The keys to look up parents for.
970
:return: A mapping from keys to parents. Absent keys are absent from
973
raise NotImplementedError(self.get_parent_map)
975
def get_record_stream(self, keys, ordering, include_delta_closure):
976
"""Get a stream of records for keys.
978
:param keys: The keys to include.
979
:param ordering: Either 'unordered' or 'topological'. A topologically
980
sorted stream has compression parents strictly before their
982
:param include_delta_closure: If True then the closure across any
983
compression parents will be included (in the opaque data).
984
:return: An iterator of ContentFactory objects, each of which is only
985
valid until the iterator is advanced.
987
raise NotImplementedError(self.get_record_stream)
989
def get_sha1s(self, keys):
990
"""Get the sha1's of the texts for the given keys.
992
:param keys: The names of the keys to lookup
993
:return: a dict from key to sha1 digest. Keys of texts which are not
994
present in the store are not present in the returned
997
raise NotImplementedError(self.get_sha1s)
999
has_key = index._has_key_from_parent_map
1001
def get_missing_compression_parent_keys(self):
1002
"""Return an iterable of keys of missing compression parents.
1004
Check this after calling insert_record_stream to find out if there are
1005
any missing compression parents. If there are, the records that
1006
depend on them are not able to be inserted safely. The precise
1007
behaviour depends on the concrete VersionedFiles class in use.
1009
Classes that do not support this will raise NotImplementedError.
1011
raise NotImplementedError(self.get_missing_compression_parent_keys)
1013
def insert_record_stream(self, stream):
1014
"""Insert a record stream into this container.
1016
:param stream: A stream of records to insert.
1018
:seealso VersionedFile.get_record_stream:
1020
raise NotImplementedError
1022
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1023
"""Iterate over the lines in the versioned files from keys.
1025
This may return lines from other keys. Each item the returned
1026
iterator yields is a tuple of a line and a text version that that line
1027
is present in (not introduced in).
1029
Ordering of results is in whatever order is most suitable for the
1030
underlying storage format.
1032
If a progress bar is supplied, it may be used to indicate progress.
1033
The caller is responsible for cleaning up progress bars (because this
1037
* Lines are normalised by the underlying store: they will all have \n
1039
* Lines are returned in arbitrary order.
1041
:return: An iterator over (line, key).
1043
raise NotImplementedError(self.iter_lines_added_or_present_in_keys)
1046
"""Return a iterable of the keys for all the contained texts."""
1047
raise NotImplementedError(self.keys)
1049
def make_mpdiffs(self, keys):
1050
"""Create multiparent diffs for specified keys."""
1051
keys_order = tuple(keys)
1052
keys = frozenset(keys)
1053
knit_keys = set(keys)
1054
parent_map = self.get_parent_map(keys)
1055
for parent_keys in parent_map.itervalues():
1057
knit_keys.update(parent_keys)
1058
missing_keys = keys - set(parent_map)
1060
raise errors.RevisionNotPresent(list(missing_keys)[0], self)
1061
# We need to filter out ghosts, because we can't diff against them.
1062
maybe_ghosts = knit_keys - keys
1063
ghosts = maybe_ghosts - set(self.get_parent_map(maybe_ghosts))
1064
knit_keys.difference_update(ghosts)
1066
chunks_to_lines = osutils.chunks_to_lines
1067
for record in self.get_record_stream(knit_keys, 'topological', True):
1068
lines[record.key] = chunks_to_lines(record.get_bytes_as('chunked'))
1069
# line_block_dict = {}
1070
# for parent, blocks in record.extract_line_blocks():
1071
# line_blocks[parent] = blocks
1072
# line_blocks[record.key] = line_block_dict
1074
for key in keys_order:
1076
parents = parent_map[key] or []
1077
# Note that filtering knit_keys can lead to a parent difference
1078
# between the creation and the application of the mpdiff.
1079
parent_lines = [lines[p] for p in parents if p in knit_keys]
1080
if len(parent_lines) > 0:
1081
left_parent_blocks = self._extract_blocks(key, parent_lines[0],
1084
left_parent_blocks = None
1085
diffs.append(multiparent.MultiParent.from_lines(target,
1086
parent_lines, left_parent_blocks))
1089
missing_keys = index._missing_keys_from_parent_map
1091
def _extract_blocks(self, version_id, source, target):
1095
class ThunkedVersionedFiles(VersionedFiles):
1096
"""Storage for many versioned files thunked onto a 'VersionedFile' class.
1098
This object allows a single keyspace for accessing the history graph and
1099
contents of named bytestrings.
1101
Currently no implementation allows the graph of different key prefixes to
1102
intersect, but the API does allow such implementations in the future.
1105
def __init__(self, transport, file_factory, mapper, is_locked):
1106
"""Create a ThunkedVersionedFiles."""
1107
self._transport = transport
1108
self._file_factory = file_factory
1109
self._mapper = mapper
1110
self._is_locked = is_locked
1112
def add_lines(self, key, parents, lines, parent_texts=None,
1113
left_matching_blocks=None, nostore_sha=None, random_id=False,
1114
check_content=True):
1115
"""See VersionedFiles.add_lines()."""
1116
path = self._mapper.map(key)
1117
version_id = key[-1]
1118
parents = [parent[-1] for parent in parents]
1119
vf = self._get_vf(path)
1122
return vf.add_lines_with_ghosts(version_id, parents, lines,
1123
parent_texts=parent_texts,
1124
left_matching_blocks=left_matching_blocks,
1125
nostore_sha=nostore_sha, random_id=random_id,
1126
check_content=check_content)
1127
except NotImplementedError:
1128
return vf.add_lines(version_id, parents, lines,
1129
parent_texts=parent_texts,
1130
left_matching_blocks=left_matching_blocks,
1131
nostore_sha=nostore_sha, random_id=random_id,
1132
check_content=check_content)
1133
except errors.NoSuchFile:
1134
# parent directory may be missing, try again.
1135
self._transport.mkdir(osutils.dirname(path))
1137
return vf.add_lines_with_ghosts(version_id, parents, lines,
1138
parent_texts=parent_texts,
1139
left_matching_blocks=left_matching_blocks,
1140
nostore_sha=nostore_sha, random_id=random_id,
1141
check_content=check_content)
1142
except NotImplementedError:
1143
return vf.add_lines(version_id, parents, lines,
1144
parent_texts=parent_texts,
1145
left_matching_blocks=left_matching_blocks,
1146
nostore_sha=nostore_sha, random_id=random_id,
1147
check_content=check_content)
1149
def annotate(self, key):
1150
"""Return a list of (version-key, line) tuples for the text of key.
1152
:raise RevisionNotPresent: If the key is not present.
1155
path = self._mapper.map(prefix)
1156
vf = self._get_vf(path)
1157
origins = vf.annotate(key[-1])
1159
for origin, line in origins:
1160
result.append((prefix + (origin,), line))
1163
def get_annotator(self):
1164
return annotate.Annotator(self)
1166
def check(self, progress_bar=None, keys=None):
1167
"""See VersionedFiles.check()."""
1168
# XXX: This is over-enthusiastic but as we only thunk for Weaves today
1169
# this is tolerable. Ideally we'd pass keys down to check() and
1170
# have the older VersiondFile interface updated too.
1171
for prefix, vf in self._iter_all_components():
1173
if keys is not None:
1174
return self.get_record_stream(keys, 'unordered', True)
1176
def get_parent_map(self, keys):
1177
"""Get a map of the parents of keys.
1179
:param keys: The keys to look up parents for.
1180
:return: A mapping from keys to parents. Absent keys are absent from
1183
prefixes = self._partition_keys(keys)
1185
for prefix, suffixes in prefixes.items():
1186
path = self._mapper.map(prefix)
1187
vf = self._get_vf(path)
1188
parent_map = vf.get_parent_map(suffixes)
1189
for key, parents in parent_map.items():
1190
result[prefix + (key,)] = tuple(
1191
prefix + (parent,) for parent in parents)
1194
def _get_vf(self, path):
1195
if not self._is_locked():
1196
raise errors.ObjectNotLocked(self)
1197
return self._file_factory(path, self._transport, create=True,
1198
get_scope=lambda:None)
1200
def _partition_keys(self, keys):
1201
"""Turn keys into a dict of prefix:suffix_list."""
1204
prefix_keys = result.setdefault(key[:-1], [])
1205
prefix_keys.append(key[-1])
1208
def _get_all_prefixes(self):
1209
# Identify all key prefixes.
1210
# XXX: A bit hacky, needs polish.
1211
if type(self._mapper) == ConstantMapper:
1212
paths = [self._mapper.map(())]
1216
for quoted_relpath in self._transport.iter_files_recursive():
1217
path, ext = os.path.splitext(quoted_relpath)
1219
paths = list(relpaths)
1220
prefixes = [self._mapper.unmap(path) for path in paths]
1221
return zip(paths, prefixes)
1223
def get_record_stream(self, keys, ordering, include_delta_closure):
1224
"""See VersionedFiles.get_record_stream()."""
1225
# Ordering will be taken care of by each partitioned store; group keys
1228
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1229
suffixes = [(suffix,) for suffix in suffixes]
1230
for record in vf.get_record_stream(suffixes, ordering,
1231
include_delta_closure):
1232
if record.parents is not None:
1233
record.parents = tuple(
1234
prefix + parent for parent in record.parents)
1235
record.key = prefix + record.key
1238
def _iter_keys_vf(self, keys):
1239
prefixes = self._partition_keys(keys)
1241
for prefix, suffixes in prefixes.items():
1242
path = self._mapper.map(prefix)
1243
vf = self._get_vf(path)
1244
yield prefix, suffixes, vf
1246
def get_sha1s(self, keys):
1247
"""See VersionedFiles.get_sha1s()."""
1249
for prefix,suffixes, vf in self._iter_keys_vf(keys):
1250
vf_sha1s = vf.get_sha1s(suffixes)
1251
for suffix, sha1 in vf_sha1s.iteritems():
1252
sha1s[prefix + (suffix,)] = sha1
1255
def insert_record_stream(self, stream):
1256
"""Insert a record stream into this container.
1258
:param stream: A stream of records to insert.
1260
:seealso VersionedFile.get_record_stream:
1262
for record in stream:
1263
prefix = record.key[:-1]
1264
key = record.key[-1:]
1265
if record.parents is not None:
1266
parents = [parent[-1:] for parent in record.parents]
1269
thunk_record = AdapterFactory(key, parents, record)
1270
path = self._mapper.map(prefix)
1271
# Note that this parses the file many times; we can do better but
1272
# as this only impacts weaves in terms of performance, it is
1274
vf = self._get_vf(path)
1275
vf.insert_record_stream([thunk_record])
1277
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1278
"""Iterate over the lines in the versioned files from keys.
1280
This may return lines from other keys. Each item the returned
1281
iterator yields is a tuple of a line and a text version that that line
1282
is present in (not introduced in).
1284
Ordering of results is in whatever order is most suitable for the
1285
underlying storage format.
1287
If a progress bar is supplied, it may be used to indicate progress.
1288
The caller is responsible for cleaning up progress bars (because this
1292
* Lines are normalised by the underlying store: they will all have \n
1294
* Lines are returned in arbitrary order.
1296
:return: An iterator over (line, key).
1298
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1299
for line, version in vf.iter_lines_added_or_present_in_versions(suffixes):
1300
yield line, prefix + (version,)
1302
def _iter_all_components(self):
1303
for path, prefix in self._get_all_prefixes():
1304
yield prefix, self._get_vf(path)
1307
"""See VersionedFiles.keys()."""
1309
for prefix, vf in self._iter_all_components():
1310
for suffix in vf.versions():
1311
result.add(prefix + (suffix,))
1315
class _PlanMergeVersionedFile(VersionedFiles):
1316
"""A VersionedFile for uncommitted and committed texts.
1318
It is intended to allow merges to be planned with working tree texts.
1319
It implements only the small part of the VersionedFiles interface used by
1320
PlanMerge. It falls back to multiple versionedfiles for data not stored in
1321
_PlanMergeVersionedFile itself.
1323
:ivar: fallback_versionedfiles a list of VersionedFiles objects that can be
1324
queried for missing texts.
1327
def __init__(self, file_id):
1328
"""Create a _PlanMergeVersionedFile.
1330
:param file_id: Used with _PlanMerge code which is not yet fully
1331
tuple-keyspace aware.
1333
self._file_id = file_id
1334
# fallback locations
1335
self.fallback_versionedfiles = []
1336
# Parents for locally held keys.
1338
# line data for locally held keys.
1340
# key lookup providers
1341
self._providers = [DictParentsProvider(self._parents)]
1343
def plan_merge(self, ver_a, ver_b, base=None):
1344
"""See VersionedFile.plan_merge"""
1345
from bzrlib.merge import _PlanMerge
1347
return _PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge()
1348
old_plan = list(_PlanMerge(ver_a, base, self, (self._file_id,)).plan_merge())
1349
new_plan = list(_PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge())
1350
return _PlanMerge._subtract_plans(old_plan, new_plan)
1352
def plan_lca_merge(self, ver_a, ver_b, base=None):
1353
from bzrlib.merge import _PlanLCAMerge
1355
new_plan = _PlanLCAMerge(ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
1358
old_plan = _PlanLCAMerge(ver_a, base, self, (self._file_id,), graph).plan_merge()
1359
return _PlanLCAMerge._subtract_plans(list(old_plan), list(new_plan))
1361
def add_lines(self, key, parents, lines):
1362
"""See VersionedFiles.add_lines
1364
Lines are added locally, not to fallback versionedfiles. Also, ghosts
1365
are permitted. Only reserved ids are permitted.
1367
if type(key) is not tuple:
1368
raise TypeError(key)
1369
if not revision.is_reserved_id(key[-1]):
1370
raise ValueError('Only reserved ids may be used')
1372
raise ValueError('Parents may not be None')
1374
raise ValueError('Lines may not be None')
1375
self._parents[key] = tuple(parents)
1376
self._lines[key] = lines
1378
def get_record_stream(self, keys, ordering, include_delta_closure):
1381
if key in self._lines:
1382
lines = self._lines[key]
1383
parents = self._parents[key]
1385
yield ChunkedContentFactory(key, parents, None, lines)
1386
for versionedfile in self.fallback_versionedfiles:
1387
for record in versionedfile.get_record_stream(
1388
pending, 'unordered', True):
1389
if record.storage_kind == 'absent':
1392
pending.remove(record.key)
1396
# report absent entries
1398
yield AbsentContentFactory(key)
1400
def get_parent_map(self, keys):
1401
"""See VersionedFiles.get_parent_map"""
1402
# We create a new provider because a fallback may have been added.
1403
# If we make fallbacks private we can update a stack list and avoid
1404
# object creation thrashing.
1407
if revision.NULL_REVISION in keys:
1408
keys.remove(revision.NULL_REVISION)
1409
result[revision.NULL_REVISION] = ()
1410
self._providers = self._providers[:1] + self.fallback_versionedfiles
1412
StackedParentsProvider(self._providers).get_parent_map(keys))
1413
for key, parents in result.iteritems():
1415
result[key] = (revision.NULL_REVISION,)
1419
class PlanWeaveMerge(TextMerge):
1420
"""Weave merge that takes a plan as its input.
1422
This exists so that VersionedFile.plan_merge is implementable.
1423
Most callers will want to use WeaveMerge instead.
1426
def __init__(self, plan, a_marker=TextMerge.A_MARKER,
1427
b_marker=TextMerge.B_MARKER):
1428
TextMerge.__init__(self, a_marker, b_marker)
1429
self.plan = list(plan)
1431
def _merge_struct(self):
1436
def outstanding_struct():
1437
if not lines_a and not lines_b:
1439
elif ch_a and not ch_b:
1442
elif ch_b and not ch_a:
1444
elif lines_a == lines_b:
1447
yield (lines_a, lines_b)
1449
# We previously considered either 'unchanged' or 'killed-both' lines
1450
# to be possible places to resynchronize. However, assuming agreement
1451
# on killed-both lines may be too aggressive. -- mbp 20060324
1452
for state, line in self.plan:
1453
if state == 'unchanged':
1454
# resync and flush queued conflicts changes if any
1455
for struct in outstanding_struct():
1461
if state == 'unchanged':
1464
elif state == 'killed-a':
1466
lines_b.append(line)
1467
elif state == 'killed-b':
1469
lines_a.append(line)
1470
elif state == 'new-a':
1472
lines_a.append(line)
1473
elif state == 'new-b':
1475
lines_b.append(line)
1476
elif state == 'conflicted-a':
1478
lines_a.append(line)
1479
elif state == 'conflicted-b':
1481
lines_b.append(line)
1482
elif state == 'killed-both':
1483
# This counts as a change, even though there is no associated
1487
if state not in ('irrelevant', 'ghost-a', 'ghost-b',
1489
raise AssertionError(state)
1490
for struct in outstanding_struct():
1493
def base_from_plan(self):
1494
"""Construct a BASE file from the plan text."""
1496
for state, line in self.plan:
1497
if state in ('killed-a', 'killed-b', 'killed-both', 'unchanged'):
1498
# If unchanged, then this line is straight from base. If a or b
1499
# or both killed the line, then it *used* to be in base.
1500
base_lines.append(line)
1502
if state not in ('killed-base', 'irrelevant',
1503
'ghost-a', 'ghost-b',
1505
'conflicted-a', 'conflicted-b'):
1506
# killed-base, irrelevant means it doesn't apply
1507
# ghost-a/ghost-b are harder to say for sure, but they
1508
# aren't in the 'inc_c' which means they aren't in the
1509
# shared base of a & b. So we don't include them. And
1510
# obviously if the line is newly inserted, it isn't in base
1512
# If 'conflicted-a' or b, then it is new vs one base, but
1513
# old versus another base. However, if we make it present
1514
# in the base, it will be deleted from the target, and it
1515
# seems better to get a line doubled in the merge result,
1516
# rather than have it deleted entirely.
1517
# Example, each node is the 'text' at that point:
1525
# There was a criss-cross conflict merge. Both sides
1526
# include the other, but put themselves first.
1527
# Weave marks this as a 'clean' merge, picking OTHER over
1528
# THIS. (Though the details depend on order inserted into
1530
# LCA generates a plan:
1531
# [('unchanged', M),
1532
# ('conflicted-b', b),
1534
# ('conflicted-a', b),
1536
# If you mark 'conflicted-*' as part of BASE, then a 3-way
1537
# merge tool will cleanly generate "MaN" (as BASE vs THIS
1538
# removes one 'b', and BASE vs OTHER removes the other)
1539
# If you include neither, 3-way creates a clean "MbabN" as
1540
# THIS adds one 'b', and OTHER does too.
1541
# It seems that having the line 2 times is better than
1542
# having it omitted. (Easier to manually delete than notice
1543
# it needs to be added.)
1544
raise AssertionError('Unknown state: %s' % (state,))
1548
class WeaveMerge(PlanWeaveMerge):
1549
"""Weave merge that takes a VersionedFile and two versions as its input."""
1551
def __init__(self, versionedfile, ver_a, ver_b,
1552
a_marker=PlanWeaveMerge.A_MARKER, b_marker=PlanWeaveMerge.B_MARKER):
1553
plan = versionedfile.plan_merge(ver_a, ver_b)
1554
PlanWeaveMerge.__init__(self, plan, a_marker, b_marker)
1557
class VirtualVersionedFiles(VersionedFiles):
1558
"""Dummy implementation for VersionedFiles that uses other functions for
1559
obtaining fulltexts and parent maps.
1561
This is always on the bottom of the stack and uses string keys
1562
(rather than tuples) internally.
1565
def __init__(self, get_parent_map, get_lines):
1566
"""Create a VirtualVersionedFiles.
1568
:param get_parent_map: Same signature as Repository.get_parent_map.
1569
:param get_lines: Should return lines for specified key or None if
1572
super(VirtualVersionedFiles, self).__init__()
1573
self._get_parent_map = get_parent_map
1574
self._get_lines = get_lines
1576
def check(self, progressbar=None):
1577
"""See VersionedFiles.check.
1579
:note: Always returns True for VirtualVersionedFiles.
1583
def add_mpdiffs(self, records):
1584
"""See VersionedFiles.mpdiffs.
1586
:note: Not implemented for VirtualVersionedFiles.
1588
raise NotImplementedError(self.add_mpdiffs)
1590
def get_parent_map(self, keys):
1591
"""See VersionedFiles.get_parent_map."""
1592
return dict([((k,), tuple([(p,) for p in v]))
1593
for k,v in self._get_parent_map([k for (k,) in keys]).iteritems()])
1595
def get_sha1s(self, keys):
1596
"""See VersionedFiles.get_sha1s."""
1599
lines = self._get_lines(k)
1600
if lines is not None:
1601
if not isinstance(lines, list):
1602
raise AssertionError
1603
ret[(k,)] = osutils.sha_strings(lines)
1606
def get_record_stream(self, keys, ordering, include_delta_closure):
1607
"""See VersionedFiles.get_record_stream."""
1608
for (k,) in list(keys):
1609
lines = self._get_lines(k)
1610
if lines is not None:
1611
if not isinstance(lines, list):
1612
raise AssertionError
1613
yield ChunkedContentFactory((k,), None,
1614
sha1=osutils.sha_strings(lines),
1617
yield AbsentContentFactory((k,))
1619
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1620
"""See VersionedFile.iter_lines_added_or_present_in_versions()."""
1621
for i, (key,) in enumerate(keys):
1623
pb.update("Finding changed lines", i, len(keys))
1624
for l in self._get_lines(key):
1628
def network_bytes_to_kind_and_offset(network_bytes):
1629
"""Strip of a record kind from the front of network_bytes.
1631
:param network_bytes: The bytes of a record.
1632
:return: A tuple (storage_kind, offset_of_remaining_bytes)
1634
line_end = network_bytes.find('\n')
1635
storage_kind = network_bytes[:line_end]
1636
return storage_kind, line_end + 1
1639
class NetworkRecordStream(object):
1640
"""A record_stream which reconstitures a serialised stream."""
1642
def __init__(self, bytes_iterator):
1643
"""Create a NetworkRecordStream.
1645
:param bytes_iterator: An iterator of bytes. Each item in this
1646
iterator should have been obtained from a record_streams'
1647
record.get_bytes_as(record.storage_kind) call.
1649
self._bytes_iterator = bytes_iterator
1650
self._kind_factory = {
1651
'fulltext': fulltext_network_to_record,
1652
'groupcompress-block': groupcompress.network_block_to_records,
1653
'knit-ft-gz': knit.knit_network_to_record,
1654
'knit-delta-gz': knit.knit_network_to_record,
1655
'knit-annotated-ft-gz': knit.knit_network_to_record,
1656
'knit-annotated-delta-gz': knit.knit_network_to_record,
1657
'knit-delta-closure': knit.knit_delta_closure_to_records,
1663
:return: An iterator as per VersionedFiles.get_record_stream().
1665
for bytes in self._bytes_iterator:
1666
storage_kind, line_end = network_bytes_to_kind_and_offset(bytes)
1667
for record in self._kind_factory[storage_kind](
1668
storage_kind, bytes, line_end):
1672
def fulltext_network_to_record(kind, bytes, line_end):
1673
"""Convert a network fulltext record to record."""
1674
meta_len, = struct.unpack('!L', bytes[line_end:line_end+4])
1675
record_meta = bytes[line_end+4:line_end+4+meta_len]
1676
key, parents = bencode.bdecode_as_tuple(record_meta)
1677
if parents == 'nil':
1679
fulltext = bytes[line_end+4+meta_len:]
1680
return [FulltextContentFactory(key, parents, None, fulltext)]
1683
def _length_prefix(bytes):
1684
return struct.pack('!L', len(bytes))
1687
def record_to_fulltext_bytes(record):
1688
if record.parents is None:
1691
parents = record.parents
1692
record_meta = bencode.bencode((record.key, parents))
1693
record_content = record.get_bytes_as('fulltext')
1694
return "fulltext\n%s%s%s" % (
1695
_length_prefix(record_meta), record_meta, record_content)
1698
def sort_groupcompress(parent_map):
1699
"""Sort and group the keys in parent_map into groupcompress order.
1701
groupcompress is defined (currently) as reverse-topological order, grouped
1704
:return: A sorted-list of keys
1706
# gc-optimal ordering is approximately reverse topological,
1707
# properly grouped by file-id.
1709
for item in parent_map.iteritems():
1711
if isinstance(key, str) or len(key) == 1:
1716
per_prefix_map[prefix].append(item)
1718
per_prefix_map[prefix] = [item]
1721
for prefix in sorted(per_prefix_map):
1722
present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
added
removed
bzrlib/versionedfile.py
