1
# Copyright (C) 2006-2011 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
"""Versioned text file storage api."""
20
from cStringIO import StringIO
23
from zlib import adler32
25
from bzrlib.lazy_import import lazy_import
26
lazy_import(globals(), """
42
from bzrlib.graph import DictParentsProvider, Graph, StackedParentsProvider
43
from bzrlib.transport.memory import MemoryTransport
45
from bzrlib.registry import Registry
46
from bzrlib.textmerge import TextMerge
47
from bzrlib import bencode
50
adapter_registry = Registry()
51
adapter_registry.register_lazy(('knit-delta-gz', 'fulltext'), 'bzrlib.knit',
52
'DeltaPlainToFullText')
53
adapter_registry.register_lazy(('knit-ft-gz', 'fulltext'), 'bzrlib.knit',
55
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'knit-delta-gz'),
56
'bzrlib.knit', 'DeltaAnnotatedToUnannotated')
57
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'fulltext'),
58
'bzrlib.knit', 'DeltaAnnotatedToFullText')
59
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'knit-ft-gz'),
60
'bzrlib.knit', 'FTAnnotatedToUnannotated')
61
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'fulltext'),
62
'bzrlib.knit', 'FTAnnotatedToFullText')
63
# adapter_registry.register_lazy(('knit-annotated-ft-gz', 'chunked'),
64
# 'bzrlib.knit', 'FTAnnotatedToChunked')
67
class ContentFactory(object):
68
"""Abstract interface for insertion and retrieval from a VersionedFile.
70
:ivar sha1: None, or the sha1 of the content fulltext.
71
:ivar storage_kind: The native storage kind of this factory. One of
72
'mpdiff', 'knit-annotated-ft', 'knit-annotated-delta', 'knit-ft',
73
'knit-delta', 'fulltext', 'knit-annotated-ft-gz',
74
'knit-annotated-delta-gz', 'knit-ft-gz', 'knit-delta-gz'.
75
:ivar key: The key of this content. Each key is a tuple with a single
77
:ivar parents: A tuple of parent keys for self.key. If the object has
78
no parent information, None (as opposed to () for an empty list of
83
"""Create a ContentFactory."""
85
self.storage_kind = None
90
class ChunkedContentFactory(ContentFactory):
91
"""Static data content factory.
93
This takes a 'chunked' list of strings. The only requirement on 'chunked' is
94
that ''.join(lines) becomes a valid fulltext. A tuple of a single string
95
satisfies this, as does a list of lines.
97
:ivar sha1: None, or the sha1 of the content fulltext.
98
:ivar storage_kind: The native storage kind of this factory. Always
100
:ivar key: The key of this content. Each key is a tuple with a single
102
:ivar parents: A tuple of parent keys for self.key. If the object has
103
no parent information, None (as opposed to () for an empty list of
107
def __init__(self, key, parents, sha1, chunks):
108
"""Create a ContentFactory."""
110
self.storage_kind = 'chunked'
112
self.parents = parents
113
self._chunks = chunks
115
def get_bytes_as(self, storage_kind):
116
if storage_kind == 'chunked':
118
elif storage_kind == 'fulltext':
119
return ''.join(self._chunks)
120
raise errors.UnavailableRepresentation(self.key, storage_kind,
124
class FulltextContentFactory(ContentFactory):
125
"""Static data content factory.
127
This takes a fulltext when created and just returns that during
128
get_bytes_as('fulltext').
130
:ivar sha1: None, or the sha1 of the content fulltext.
131
:ivar storage_kind: The native storage kind of this factory. Always
133
:ivar key: The key of this content. Each key is a tuple with a single
135
:ivar parents: A tuple of parent keys for self.key. If the object has
136
no parent information, None (as opposed to () for an empty list of
140
def __init__(self, key, parents, sha1, text):
141
"""Create a ContentFactory."""
143
self.storage_kind = 'fulltext'
145
self.parents = parents
148
def get_bytes_as(self, storage_kind):
149
if storage_kind == self.storage_kind:
151
elif storage_kind == 'chunked':
153
raise errors.UnavailableRepresentation(self.key, storage_kind,
157
class AbsentContentFactory(ContentFactory):
158
"""A placeholder content factory for unavailable texts.
161
:ivar storage_kind: 'absent'.
162
:ivar key: The key of this content. Each key is a tuple with a single
167
def __init__(self, key):
168
"""Create a ContentFactory."""
170
self.storage_kind = 'absent'
174
def get_bytes_as(self, storage_kind):
175
raise ValueError('A request was made for key: %s, but that'
176
' content is not available, and the calling'
177
' code does not handle if it is missing.'
181
class AdapterFactory(ContentFactory):
182
"""A content factory to adapt between key prefix's."""
184
def __init__(self, key, parents, adapted):
185
"""Create an adapter factory instance."""
187
self.parents = parents
188
self._adapted = adapted
190
def __getattr__(self, attr):
191
"""Return a member from the adapted object."""
192
if attr in ('key', 'parents'):
193
return self.__dict__[attr]
195
return getattr(self._adapted, attr)
198
def filter_absent(record_stream):
199
"""Adapt a record stream to remove absent records."""
200
for record in record_stream:
201
if record.storage_kind != 'absent':
205
class _MPDiffGenerator(object):
206
"""Pull out the functionality for generating mp_diffs."""
208
def __init__(self, vf, keys):
210
# This is the order the keys were requested in
211
self.ordered_keys = tuple(keys)
212
# keys + their parents, what we need to compute the diffs
213
self.needed_keys = ()
214
# Map from key: mp_diff
216
# Map from key: parents_needed (may have ghosts)
218
# Parents that aren't present
219
self.ghost_parents = ()
220
# Map from parent_key => number of children for this text
222
# Content chunks that are cached while we still need them
225
def _find_needed_keys(self):
226
"""Find the set of keys we need to request.
228
This includes all the original keys passed in, and the non-ghost
229
parents of those keys.
231
:return: (needed_keys, refcounts)
232
needed_keys is the set of all texts we need to extract
233
refcounts is a dict of {key: num_children} letting us know when we
234
no longer need to cache a given parent text
236
# All the keys and their parents
237
needed_keys = set(self.ordered_keys)
238
parent_map = self.vf.get_parent_map(needed_keys)
239
self.parent_map = parent_map
240
# TODO: Should we be using a different construct here? I think this
241
# uses difference_update internally, and we expect the result to
243
missing_keys = needed_keys.difference(parent_map)
245
raise errors.RevisionNotPresent(list(missing_keys)[0], self.vf)
246
# Parents that might be missing. They are allowed to be ghosts, but we
247
# should check for them
249
setdefault = refcounts.setdefault
251
for child_key, parent_keys in parent_map.iteritems():
253
# parent_keys may be None if a given VersionedFile claims to
254
# not support graph operations.
256
just_parents.update(parent_keys)
257
needed_keys.update(parent_keys)
258
for p in parent_keys:
259
refcounts[p] = setdefault(p, 0) + 1
260
just_parents.difference_update(parent_map)
261
# Remove any parents that are actually ghosts from the needed set
262
self.present_parents = set(self.vf.get_parent_map(just_parents))
263
self.ghost_parents = just_parents.difference(self.present_parents)
264
needed_keys.difference_update(self.ghost_parents)
265
self.needed_keys = needed_keys
266
self.refcounts = refcounts
267
return needed_keys, refcounts
269
def _compute_diff(self, key, parent_lines, lines):
270
"""Compute a single mp_diff, and store it in self._diffs"""
271
if len(parent_lines) > 0:
272
# XXX: _extract_blocks is not usefully defined anywhere...
273
# It was meant to extract the left-parent diff without
274
# having to recompute it for Knit content (pack-0.92,
275
# etc). That seems to have regressed somewhere
276
left_parent_blocks = self.vf._extract_blocks(key,
277
parent_lines[0], lines)
279
left_parent_blocks = None
280
diff = multiparent.MultiParent.from_lines(lines,
281
parent_lines, left_parent_blocks)
282
self.diffs[key] = diff
284
def _process_one_record(self, key, this_chunks):
286
if key in self.parent_map:
287
# This record should be ready to diff, since we requested
288
# content in 'topological' order
289
parent_keys = self.parent_map.pop(key)
290
# If a VersionedFile claims 'no-graph' support, then it may return
291
# None for any parent request, so we replace it with an empty tuple
292
if parent_keys is None:
295
for p in parent_keys:
296
# Alternatively we could check p not in self.needed_keys, but
297
# ghost_parents should be tiny versus huge
298
if p in self.ghost_parents:
300
refcount = self.refcounts[p]
301
if refcount == 1: # Last child reference
302
self.refcounts.pop(p)
303
parent_chunks = self.chunks.pop(p)
305
self.refcounts[p] = refcount - 1
306
parent_chunks = self.chunks[p]
307
p_lines = osutils.chunks_to_lines(parent_chunks)
308
# TODO: Should we cache the line form? We did the
309
# computation to get it, but storing it this way will
310
# be less memory efficient...
311
parent_lines.append(p_lines)
313
lines = osutils.chunks_to_lines(this_chunks)
314
# Since we needed the lines, we'll go ahead and cache them this way
316
self._compute_diff(key, parent_lines, lines)
318
# Is this content required for any more children?
319
if key in self.refcounts:
320
self.chunks[key] = this_chunks
322
def _extract_diffs(self):
323
needed_keys, refcounts = self._find_needed_keys()
324
for record in self.vf.get_record_stream(needed_keys,
325
'topological', True):
326
if record.storage_kind == 'absent':
327
raise errors.RevisionNotPresent(record.key, self.vf)
328
self._process_one_record(record.key,
329
record.get_bytes_as('chunked'))
331
def compute_diffs(self):
332
self._extract_diffs()
333
dpop = self.diffs.pop
334
return [dpop(k) for k in self.ordered_keys]
337
class VersionedFile(object):
338
"""Versioned text file storage.
340
A versioned file manages versions of line-based text files,
341
keeping track of the originating version for each line.
343
To clients the "lines" of the file are represented as a list of
344
strings. These strings will typically have terminal newline
345
characters, but this is not required. In particular files commonly
346
do not have a newline at the end of the file.
348
Texts are identified by a version-id string.
352
def check_not_reserved_id(version_id):
353
revision.check_not_reserved_id(version_id)
355
def copy_to(self, name, transport):
356
"""Copy this versioned file to name on transport."""
357
raise NotImplementedError(self.copy_to)
359
def get_record_stream(self, versions, ordering, include_delta_closure):
360
"""Get a stream of records for versions.
362
:param versions: The versions to include. Each version is a tuple
364
:param ordering: Either 'unordered' or 'topological'. A topologically
365
sorted stream has compression parents strictly before their
367
:param include_delta_closure: If True then the closure across any
368
compression parents will be included (in the data content of the
369
stream, not in the emitted records). This guarantees that
370
'fulltext' can be used successfully on every record.
371
:return: An iterator of ContentFactory objects, each of which is only
372
valid until the iterator is advanced.
374
raise NotImplementedError(self.get_record_stream)
376
def has_version(self, version_id):
377
"""Returns whether version is present."""
378
raise NotImplementedError(self.has_version)
380
def insert_record_stream(self, stream):
381
"""Insert a record stream into this versioned file.
383
:param stream: A stream of records to insert.
385
:seealso VersionedFile.get_record_stream:
387
raise NotImplementedError
389
def add_lines(self, version_id, parents, lines, parent_texts=None,
390
left_matching_blocks=None, nostore_sha=None, random_id=False,
392
"""Add a single text on top of the versioned file.
394
Must raise RevisionAlreadyPresent if the new version is
395
already present in file history.
397
Must raise RevisionNotPresent if any of the given parents are
398
not present in file history.
400
:param lines: A list of lines. Each line must be a bytestring. And all
401
of them except the last must be terminated with \n and contain no
402
other \n's. The last line may either contain no \n's or a single
403
terminated \n. If the lines list does meet this constraint the add
404
routine may error or may succeed - but you will be unable to read
405
the data back accurately. (Checking the lines have been split
406
correctly is expensive and extremely unlikely to catch bugs so it
407
is not done at runtime unless check_content is True.)
408
:param parent_texts: An optional dictionary containing the opaque
409
representations of some or all of the parents of version_id to
410
allow delta optimisations. VERY IMPORTANT: the texts must be those
411
returned by add_lines or data corruption can be caused.
412
:param left_matching_blocks: a hint about which areas are common
413
between the text and its left-hand-parent. The format is
414
the SequenceMatcher.get_matching_blocks format.
415
:param nostore_sha: Raise ExistingContent and do not add the lines to
416
the versioned file if the digest of the lines matches this.
417
:param random_id: If True a random id has been selected rather than
418
an id determined by some deterministic process such as a converter
419
from a foreign VCS. When True the backend may choose not to check
420
for uniqueness of the resulting key within the versioned file, so
421
this should only be done when the result is expected to be unique
423
:param check_content: If True, the lines supplied are verified to be
424
bytestrings that are correctly formed lines.
425
:return: The text sha1, the number of bytes in the text, and an opaque
426
representation of the inserted version which can be provided
427
back to future add_lines calls in the parent_texts dictionary.
429
self._check_write_ok()
430
return self._add_lines(version_id, parents, lines, parent_texts,
431
left_matching_blocks, nostore_sha, random_id, check_content)
433
def _add_lines(self, version_id, parents, lines, parent_texts,
434
left_matching_blocks, nostore_sha, random_id, check_content):
435
"""Helper to do the class specific add_lines."""
436
raise NotImplementedError(self.add_lines)
438
def add_lines_with_ghosts(self, version_id, parents, lines,
439
parent_texts=None, nostore_sha=None, random_id=False,
440
check_content=True, left_matching_blocks=None):
441
"""Add lines to the versioned file, allowing ghosts to be present.
443
This takes the same parameters as add_lines and returns the same.
445
self._check_write_ok()
446
return self._add_lines_with_ghosts(version_id, parents, lines,
447
parent_texts, nostore_sha, random_id, check_content, left_matching_blocks)
449
def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts,
450
nostore_sha, random_id, check_content, left_matching_blocks):
451
"""Helper to do class specific add_lines_with_ghosts."""
452
raise NotImplementedError(self.add_lines_with_ghosts)
454
def check(self, progress_bar=None):
455
"""Check the versioned file for integrity."""
456
raise NotImplementedError(self.check)
458
def _check_lines_not_unicode(self, lines):
459
"""Check that lines being added to a versioned file are not unicode."""
461
if line.__class__ is not str:
462
raise errors.BzrBadParameterUnicode("lines")
464
def _check_lines_are_lines(self, lines):
465
"""Check that the lines really are full lines without inline EOL."""
467
if '\n' in line[:-1]:
468
raise errors.BzrBadParameterContainsNewline("lines")
470
def get_format_signature(self):
471
"""Get a text description of the data encoding in this file.
475
raise NotImplementedError(self.get_format_signature)
477
def make_mpdiffs(self, version_ids):
478
"""Create multiparent diffs for specified versions."""
479
# XXX: Can't use _MPDiffGenerator just yet. This is because version_ids
480
# is a list of strings, not keys. And while self.get_record_stream
481
# is supported, it takes *keys*, while self.get_parent_map() takes
483
knit_versions = set()
484
knit_versions.update(version_ids)
485
parent_map = self.get_parent_map(version_ids)
486
for version_id in version_ids:
488
knit_versions.update(parent_map[version_id])
490
raise errors.RevisionNotPresent(version_id, self)
491
# We need to filter out ghosts, because we can't diff against them.
492
knit_versions = set(self.get_parent_map(knit_versions).keys())
493
lines = dict(zip(knit_versions,
494
self._get_lf_split_line_list(knit_versions)))
496
for version_id in version_ids:
497
target = lines[version_id]
499
parents = [lines[p] for p in parent_map[version_id] if p in
502
# I don't know how this could ever trigger.
503
# parent_map[version_id] was already triggered in the previous
504
# for loop, and lines[p] has the 'if p in knit_versions' check,
505
# so we again won't have a KeyError.
506
raise errors.RevisionNotPresent(version_id, self)
508
left_parent_blocks = self._extract_blocks(version_id,
511
left_parent_blocks = None
512
diffs.append(multiparent.MultiParent.from_lines(target, parents,
516
def _extract_blocks(self, version_id, source, target):
519
def add_mpdiffs(self, records):
520
"""Add mpdiffs to this VersionedFile.
522
Records should be iterables of version, parents, expected_sha1,
523
mpdiff. mpdiff should be a MultiParent instance.
525
# Does this need to call self._check_write_ok()? (IanC 20070919)
527
mpvf = multiparent.MultiMemoryVersionedFile()
529
for version, parent_ids, expected_sha1, mpdiff in records:
530
versions.append(version)
531
mpvf.add_diff(mpdiff, version, parent_ids)
532
needed_parents = set()
533
for version, parent_ids, expected_sha1, mpdiff in records:
534
needed_parents.update(p for p in parent_ids
535
if not mpvf.has_version(p))
536
present_parents = set(self.get_parent_map(needed_parents).keys())
537
for parent_id, lines in zip(present_parents,
538
self._get_lf_split_line_list(present_parents)):
539
mpvf.add_version(lines, parent_id, [])
540
for (version, parent_ids, expected_sha1, mpdiff), lines in\
541
zip(records, mpvf.get_line_list(versions)):
542
if len(parent_ids) == 1:
543
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
544
mpvf.get_diff(parent_ids[0]).num_lines()))
546
left_matching_blocks = None
548
_, _, version_text = self.add_lines_with_ghosts(version,
549
parent_ids, lines, vf_parents,
550
left_matching_blocks=left_matching_blocks)
551
except NotImplementedError:
552
# The vf can't handle ghosts, so add lines normally, which will
553
# (reasonably) fail if there are ghosts in the data.
554
_, _, version_text = self.add_lines(version,
555
parent_ids, lines, vf_parents,
556
left_matching_blocks=left_matching_blocks)
557
vf_parents[version] = version_text
558
sha1s = self.get_sha1s(versions)
559
for version, parent_ids, expected_sha1, mpdiff in records:
560
if expected_sha1 != sha1s[version]:
561
raise errors.VersionedFileInvalidChecksum(version)
563
def get_text(self, version_id):
564
"""Return version contents as a text string.
566
Raises RevisionNotPresent if version is not present in
569
return ''.join(self.get_lines(version_id))
570
get_string = get_text
572
def get_texts(self, version_ids):
573
"""Return the texts of listed versions as a list of strings.
575
Raises RevisionNotPresent if version is not present in
578
return [''.join(self.get_lines(v)) for v in version_ids]
580
def get_lines(self, version_id):
581
"""Return version contents as a sequence of lines.
583
Raises RevisionNotPresent if version is not present in
586
raise NotImplementedError(self.get_lines)
588
def _get_lf_split_line_list(self, version_ids):
589
return [StringIO(t).readlines() for t in self.get_texts(version_ids)]
591
def get_ancestry(self, version_ids, topo_sorted=True):
592
"""Return a list of all ancestors of given version(s). This
593
will not include the null revision.
595
This list will not be topologically sorted if topo_sorted=False is
598
Must raise RevisionNotPresent if any of the given versions are
599
not present in file history."""
600
if isinstance(version_ids, basestring):
601
version_ids = [version_ids]
602
raise NotImplementedError(self.get_ancestry)
604
def get_ancestry_with_ghosts(self, version_ids):
605
"""Return a list of all ancestors of given version(s). This
606
will not include the null revision.
608
Must raise RevisionNotPresent if any of the given versions are
609
not present in file history.
611
Ghosts that are known about will be included in ancestry list,
612
but are not explicitly marked.
614
raise NotImplementedError(self.get_ancestry_with_ghosts)
616
def get_parent_map(self, version_ids):
617
"""Get a map of the parents of version_ids.
619
:param version_ids: The version ids to look up parents for.
620
:return: A mapping from version id to parents.
622
raise NotImplementedError(self.get_parent_map)
624
def get_parents_with_ghosts(self, version_id):
625
"""Return version names for parents of version_id.
627
Will raise RevisionNotPresent if version_id is not present
630
Ghosts that are known about will be included in the parent list,
631
but are not explicitly marked.
634
return list(self.get_parent_map([version_id])[version_id])
636
raise errors.RevisionNotPresent(version_id, self)
638
def annotate(self, version_id):
639
"""Return a list of (version-id, line) tuples for version_id.
641
:raise RevisionNotPresent: If the given version is
642
not present in file history.
644
raise NotImplementedError(self.annotate)
646
def iter_lines_added_or_present_in_versions(self, version_ids=None,
648
"""Iterate over the lines in the versioned file from version_ids.
650
This may return lines from other versions. Each item the returned
651
iterator yields is a tuple of a line and a text version that that line
652
is present in (not introduced in).
654
Ordering of results is in whatever order is most suitable for the
655
underlying storage format.
657
If a progress bar is supplied, it may be used to indicate progress.
658
The caller is responsible for cleaning up progress bars (because this
661
NOTES: Lines are normalised: they will all have \n terminators.
662
Lines are returned in arbitrary order.
664
:return: An iterator over (line, version_id).
666
raise NotImplementedError(self.iter_lines_added_or_present_in_versions)
668
def plan_merge(self, ver_a, ver_b):
669
"""Return pseudo-annotation indicating how the two versions merge.
671
This is computed between versions a and b and their common
674
Weave lines present in none of them are skipped entirely.
677
killed-base Dead in base revision
678
killed-both Killed in each revision
681
unchanged Alive in both a and b (possibly created in both)
684
ghost-a Killed in a, unborn in b
685
ghost-b Killed in b, unborn in a
686
irrelevant Not in either revision
688
raise NotImplementedError(VersionedFile.plan_merge)
690
def weave_merge(self, plan, a_marker=TextMerge.A_MARKER,
691
b_marker=TextMerge.B_MARKER):
692
return PlanWeaveMerge(plan, a_marker, b_marker).merge_lines()[0]
695
class RecordingVersionedFilesDecorator(object):
696
"""A minimal versioned files that records calls made on it.
698
Only enough methods have been added to support tests using it to date.
700
:ivar calls: A list of the calls made; can be reset at any time by
704
def __init__(self, backing_vf):
705
"""Create a RecordingVersionedFilesDecorator decorating backing_vf.
707
:param backing_vf: The versioned file to answer all methods.
709
self._backing_vf = backing_vf
712
def add_lines(self, key, parents, lines, parent_texts=None,
713
left_matching_blocks=None, nostore_sha=None, random_id=False,
715
self.calls.append(("add_lines", key, parents, lines, parent_texts,
716
left_matching_blocks, nostore_sha, random_id, check_content))
717
return self._backing_vf.add_lines(key, parents, lines, parent_texts,
718
left_matching_blocks, nostore_sha, random_id, check_content)
721
self._backing_vf.check()
723
def get_parent_map(self, keys):
724
self.calls.append(("get_parent_map", copy(keys)))
725
return self._backing_vf.get_parent_map(keys)
727
def get_record_stream(self, keys, sort_order, include_delta_closure):
728
self.calls.append(("get_record_stream", list(keys), sort_order,
729
include_delta_closure))
730
return self._backing_vf.get_record_stream(keys, sort_order,
731
include_delta_closure)
733
def get_sha1s(self, keys):
734
self.calls.append(("get_sha1s", copy(keys)))
735
return self._backing_vf.get_sha1s(keys)
737
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
738
self.calls.append(("iter_lines_added_or_present_in_keys", copy(keys)))
739
return self._backing_vf.iter_lines_added_or_present_in_keys(keys, pb=pb)
742
self.calls.append(("keys",))
743
return self._backing_vf.keys()
746
class OrderingVersionedFilesDecorator(RecordingVersionedFilesDecorator):
747
"""A VF that records calls, and returns keys in specific order.
749
:ivar calls: A list of the calls made; can be reset at any time by
753
def __init__(self, backing_vf, key_priority):
754
"""Create a RecordingVersionedFilesDecorator decorating backing_vf.
756
:param backing_vf: The versioned file to answer all methods.
757
:param key_priority: A dictionary defining what order keys should be
758
returned from an 'unordered' get_record_stream request.
759
Keys with lower priority are returned first, keys not present in
760
the map get an implicit priority of 0, and are returned in
761
lexicographical order.
763
RecordingVersionedFilesDecorator.__init__(self, backing_vf)
764
self._key_priority = key_priority
766
def get_record_stream(self, keys, sort_order, include_delta_closure):
767
self.calls.append(("get_record_stream", list(keys), sort_order,
768
include_delta_closure))
769
if sort_order == 'unordered':
771
return (self._key_priority.get(key, 0), key)
772
# Use a defined order by asking for the keys one-by-one from the
774
for key in sorted(keys, key=sort_key):
775
for record in self._backing_vf.get_record_stream([key],
776
'unordered', include_delta_closure):
779
for record in self._backing_vf.get_record_stream(keys, sort_order,
780
include_delta_closure):
784
class KeyMapper(object):
785
"""KeyMappers map between keys and underlying partitioned storage."""
788
"""Map key to an underlying storage identifier.
790
:param key: A key tuple e.g. ('file-id', 'revision-id').
791
:return: An underlying storage identifier, specific to the partitioning
794
raise NotImplementedError(self.map)
796
def unmap(self, partition_id):
797
"""Map a partitioned storage id back to a key prefix.
799
:param partition_id: The underlying partition id.
800
:return: As much of a key (or prefix) as is derivable from the partition
803
raise NotImplementedError(self.unmap)
806
class ConstantMapper(KeyMapper):
807
"""A key mapper that maps to a constant result."""
809
def __init__(self, result):
810
"""Create a ConstantMapper which will return result for all maps."""
811
self._result = result
814
"""See KeyMapper.map()."""
818
class URLEscapeMapper(KeyMapper):
819
"""Base class for use with transport backed storage.
821
This provides a map and unmap wrapper that respectively url escape and
822
unescape their outputs and inputs.
826
"""See KeyMapper.map()."""
827
return urllib.quote(self._map(key))
829
def unmap(self, partition_id):
830
"""See KeyMapper.unmap()."""
831
return self._unmap(urllib.unquote(partition_id))
834
class PrefixMapper(URLEscapeMapper):
835
"""A key mapper that extracts the first component of a key.
837
This mapper is for use with a transport based backend.
841
"""See KeyMapper.map()."""
844
def _unmap(self, partition_id):
845
"""See KeyMapper.unmap()."""
846
return (partition_id,)
849
class HashPrefixMapper(URLEscapeMapper):
850
"""A key mapper that combines the first component of a key with a hash.
852
This mapper is for use with a transport based backend.
856
"""See KeyMapper.map()."""
857
prefix = self._escape(key[0])
858
return "%02x/%s" % (adler32(prefix) & 0xff, prefix)
860
def _escape(self, prefix):
861
"""No escaping needed here."""
864
def _unmap(self, partition_id):
865
"""See KeyMapper.unmap()."""
866
return (self._unescape(osutils.basename(partition_id)),)
868
def _unescape(self, basename):
869
"""No unescaping needed for HashPrefixMapper."""
873
class HashEscapedPrefixMapper(HashPrefixMapper):
874
"""Combines the escaped first component of a key with a hash.
876
This mapper is for use with a transport based backend.
879
_safe = "abcdefghijklmnopqrstuvwxyz0123456789-_@,."
881
def _escape(self, prefix):
882
"""Turn a key element into a filesystem safe string.
884
This is similar to a plain urllib.quote, except
885
it uses specific safe characters, so that it doesn't
886
have to translate a lot of valid file ids.
888
# @ does not get escaped. This is because it is a valid
889
# filesystem character we use all the time, and it looks
890
# a lot better than seeing %40 all the time.
891
r = [((c in self._safe) and c or ('%%%02x' % ord(c)))
895
def _unescape(self, basename):
896
"""Escaped names are easily unescaped by urlutils."""
897
return urllib.unquote(basename)
900
def make_versioned_files_factory(versioned_file_factory, mapper):
901
"""Create a ThunkedVersionedFiles factory.
903
This will create a callable which when called creates a
904
ThunkedVersionedFiles on a transport, using mapper to access individual
905
versioned files, and versioned_file_factory to create each individual file.
907
def factory(transport):
908
return ThunkedVersionedFiles(transport, versioned_file_factory, mapper,
913
class VersionedFiles(object):
914
"""Storage for many versioned files.
916
This object allows a single keyspace for accessing the history graph and
917
contents of named bytestrings.
919
Currently no implementation allows the graph of different key prefixes to
920
intersect, but the API does allow such implementations in the future.
922
The keyspace is expressed via simple tuples. Any instance of VersionedFiles
923
may have a different length key-size, but that size will be constant for
924
all texts added to or retrieved from it. For instance, bzrlib uses
925
instances with a key-size of 2 for storing user files in a repository, with
926
the first element the fileid, and the second the version of that file.
928
The use of tuples allows a single code base to support several different
929
uses with only the mapping logic changing from instance to instance.
931
:ivar _immediate_fallback_vfs: For subclasses that support stacking,
932
this is a list of other VersionedFiles immediately underneath this
933
one. They may in turn each have further fallbacks.
936
def add_lines(self, key, parents, lines, parent_texts=None,
937
left_matching_blocks=None, nostore_sha=None, random_id=False,
939
"""Add a text to the store.
941
:param key: The key tuple of the text to add. If the last element is
942
None, a CHK string will be generated during the addition.
943
:param parents: The parents key tuples of the text to add.
944
:param lines: A list of lines. Each line must be a bytestring. And all
945
of them except the last must be terminated with \n and contain no
946
other \n's. The last line may either contain no \n's or a single
947
terminating \n. If the lines list does meet this constraint the add
948
routine may error or may succeed - but you will be unable to read
949
the data back accurately. (Checking the lines have been split
950
correctly is expensive and extremely unlikely to catch bugs so it
951
is not done at runtime unless check_content is True.)
952
:param parent_texts: An optional dictionary containing the opaque
953
representations of some or all of the parents of version_id to
954
allow delta optimisations. VERY IMPORTANT: the texts must be those
955
returned by add_lines or data corruption can be caused.
956
:param left_matching_blocks: a hint about which areas are common
957
between the text and its left-hand-parent. The format is
958
the SequenceMatcher.get_matching_blocks format.
959
:param nostore_sha: Raise ExistingContent and do not add the lines to
960
the versioned file if the digest of the lines matches this.
961
:param random_id: If True a random id has been selected rather than
962
an id determined by some deterministic process such as a converter
963
from a foreign VCS. When True the backend may choose not to check
964
for uniqueness of the resulting key within the versioned file, so
965
this should only be done when the result is expected to be unique
967
:param check_content: If True, the lines supplied are verified to be
968
bytestrings that are correctly formed lines.
969
:return: The text sha1, the number of bytes in the text, and an opaque
970
representation of the inserted version which can be provided
971
back to future add_lines calls in the parent_texts dictionary.
973
raise NotImplementedError(self.add_lines)
975
def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
976
"""Add a text to the store.
978
This is a private function for use by CommitBuilder.
980
:param key: The key tuple of the text to add. If the last element is
981
None, a CHK string will be generated during the addition.
982
:param parents: The parents key tuples of the text to add.
983
:param text: A string containing the text to be committed.
984
:param nostore_sha: Raise ExistingContent and do not add the lines to
985
the versioned file if the digest of the lines matches this.
986
:param random_id: If True a random id has been selected rather than
987
an id determined by some deterministic process such as a converter
988
from a foreign VCS. When True the backend may choose not to check
989
for uniqueness of the resulting key within the versioned file, so
990
this should only be done when the result is expected to be unique
992
:param check_content: If True, the lines supplied are verified to be
993
bytestrings that are correctly formed lines.
994
:return: The text sha1, the number of bytes in the text, and an opaque
995
representation of the inserted version which can be provided
996
back to future _add_text calls in the parent_texts dictionary.
998
# The default implementation just thunks over to .add_lines(),
999
# inefficient, but it works.
1000
return self.add_lines(key, parents, osutils.split_lines(text),
1001
nostore_sha=nostore_sha,
1002
random_id=random_id,
1005
def add_mpdiffs(self, records):
1006
"""Add mpdiffs to this VersionedFile.
1008
Records should be iterables of version, parents, expected_sha1,
1009
mpdiff. mpdiff should be a MultiParent instance.
1012
mpvf = multiparent.MultiMemoryVersionedFile()
1014
for version, parent_ids, expected_sha1, mpdiff in records:
1015
versions.append(version)
1016
mpvf.add_diff(mpdiff, version, parent_ids)
1017
needed_parents = set()
1018
for version, parent_ids, expected_sha1, mpdiff in records:
1019
needed_parents.update(p for p in parent_ids
1020
if not mpvf.has_version(p))
1021
# It seems likely that adding all the present parents as fulltexts can
1022
# easily exhaust memory.
1023
chunks_to_lines = osutils.chunks_to_lines
1024
for record in self.get_record_stream(needed_parents, 'unordered',
1026
if record.storage_kind == 'absent':
1028
mpvf.add_version(chunks_to_lines(record.get_bytes_as('chunked')),
1030
for (key, parent_keys, expected_sha1, mpdiff), lines in\
1031
zip(records, mpvf.get_line_list(versions)):
1032
if len(parent_keys) == 1:
1033
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
1034
mpvf.get_diff(parent_keys[0]).num_lines()))
1036
left_matching_blocks = None
1037
version_sha1, _, version_text = self.add_lines(key,
1038
parent_keys, lines, vf_parents,
1039
left_matching_blocks=left_matching_blocks)
1040
if version_sha1 != expected_sha1:
1041
raise errors.VersionedFileInvalidChecksum(version)
1042
vf_parents[key] = version_text
1044
def annotate(self, key):
1045
"""Return a list of (version-key, line) tuples for the text of key.
1047
:raise RevisionNotPresent: If the key is not present.
1049
raise NotImplementedError(self.annotate)
1051
def check(self, progress_bar=None):
1052
"""Check this object for integrity.
1054
:param progress_bar: A progress bar to output as the check progresses.
1055
:param keys: Specific keys within the VersionedFiles to check. When
1056
this parameter is not None, check() becomes a generator as per
1057
get_record_stream. The difference to get_record_stream is that
1058
more or deeper checks will be performed.
1059
:return: None, or if keys was supplied a generator as per
1062
raise NotImplementedError(self.check)
1065
def check_not_reserved_id(version_id):
1066
revision.check_not_reserved_id(version_id)
1068
def clear_cache(self):
1069
"""Clear whatever caches this VersionedFile holds.
1071
This is generally called after an operation has been performed, when we
1072
don't expect to be using this versioned file again soon.
1075
def _check_lines_not_unicode(self, lines):
1076
"""Check that lines being added to a versioned file are not unicode."""
1078
if line.__class__ is not str:
1079
raise errors.BzrBadParameterUnicode("lines")
1081
def _check_lines_are_lines(self, lines):
1082
"""Check that the lines really are full lines without inline EOL."""
1084
if '\n' in line[:-1]:
1085
raise errors.BzrBadParameterContainsNewline("lines")
1087
def get_known_graph_ancestry(self, keys):
1088
"""Get a KnownGraph instance with the ancestry of keys."""
1089
# most basic implementation is a loop around get_parent_map
1093
this_parent_map = self.get_parent_map(pending)
1094
parent_map.update(this_parent_map)
1096
map(pending.update, this_parent_map.itervalues())
1097
pending = pending.difference(parent_map)
1098
kg = _mod_graph.KnownGraph(parent_map)
1101
def get_parent_map(self, keys):
1102
"""Get a map of the parents of keys.
1104
:param keys: The keys to look up parents for.
1105
:return: A mapping from keys to parents. Absent keys are absent from
1108
raise NotImplementedError(self.get_parent_map)
1110
def get_record_stream(self, keys, ordering, include_delta_closure):
1111
"""Get a stream of records for keys.
1113
:param keys: The keys to include.
1114
:param ordering: Either 'unordered' or 'topological'. A topologically
1115
sorted stream has compression parents strictly before their
1117
:param include_delta_closure: If True then the closure across any
1118
compression parents will be included (in the opaque data).
1119
:return: An iterator of ContentFactory objects, each of which is only
1120
valid until the iterator is advanced.
1122
raise NotImplementedError(self.get_record_stream)
1124
def get_sha1s(self, keys):
1125
"""Get the sha1's of the texts for the given keys.
1127
:param keys: The names of the keys to lookup
1128
:return: a dict from key to sha1 digest. Keys of texts which are not
1129
present in the store are not present in the returned
1132
raise NotImplementedError(self.get_sha1s)
1134
has_key = index._has_key_from_parent_map
1136
def get_missing_compression_parent_keys(self):
1137
"""Return an iterable of keys of missing compression parents.
1139
Check this after calling insert_record_stream to find out if there are
1140
any missing compression parents. If there are, the records that
1141
depend on them are not able to be inserted safely. The precise
1142
behaviour depends on the concrete VersionedFiles class in use.
1144
Classes that do not support this will raise NotImplementedError.
1146
raise NotImplementedError(self.get_missing_compression_parent_keys)
1148
def insert_record_stream(self, stream):
1149
"""Insert a record stream into this container.
1151
:param stream: A stream of records to insert.
1153
:seealso VersionedFile.get_record_stream:
1155
raise NotImplementedError
1157
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1158
"""Iterate over the lines in the versioned files from keys.
1160
This may return lines from other keys. Each item the returned
1161
iterator yields is a tuple of a line and a text version that that line
1162
is present in (not introduced in).
1164
Ordering of results is in whatever order is most suitable for the
1165
underlying storage format.
1167
If a progress bar is supplied, it may be used to indicate progress.
1168
The caller is responsible for cleaning up progress bars (because this
1172
* Lines are normalised by the underlying store: they will all have \n
1174
* Lines are returned in arbitrary order.
1176
:return: An iterator over (line, key).
1178
raise NotImplementedError(self.iter_lines_added_or_present_in_keys)
1181
"""Return a iterable of the keys for all the contained texts."""
1182
raise NotImplementedError(self.keys)
1184
def make_mpdiffs(self, keys):
1185
"""Create multiparent diffs for specified keys."""
1186
generator = _MPDiffGenerator(self, keys)
1187
return generator.compute_diffs()
1189
def get_annotator(self):
1190
return annotate.Annotator(self)
1192
missing_keys = index._missing_keys_from_parent_map
1194
def _extract_blocks(self, version_id, source, target):
1197
def _transitive_fallbacks(self):
1198
"""Return the whole stack of fallback versionedfiles.
1200
This VersionedFiles may have a list of fallbacks, but it doesn't
1201
necessarily know about the whole stack going down, and it can't know
1202
at open time because they may change after the objects are opened.
1205
for a_vfs in self._immediate_fallback_vfs:
1206
all_fallbacks.append(a_vfs)
1207
all_fallbacks.extend(a_vfs._transitive_fallbacks())
1208
return all_fallbacks
1211
class ThunkedVersionedFiles(VersionedFiles):
1212
"""Storage for many versioned files thunked onto a 'VersionedFile' class.
1214
This object allows a single keyspace for accessing the history graph and
1215
contents of named bytestrings.
1217
Currently no implementation allows the graph of different key prefixes to
1218
intersect, but the API does allow such implementations in the future.
1221
def __init__(self, transport, file_factory, mapper, is_locked):
1222
"""Create a ThunkedVersionedFiles."""
1223
self._transport = transport
1224
self._file_factory = file_factory
1225
self._mapper = mapper
1226
self._is_locked = is_locked
1228
def add_lines(self, key, parents, lines, parent_texts=None,
1229
left_matching_blocks=None, nostore_sha=None, random_id=False,
1230
check_content=True):
1231
"""See VersionedFiles.add_lines()."""
1232
path = self._mapper.map(key)
1233
version_id = key[-1]
1234
parents = [parent[-1] for parent in parents]
1235
vf = self._get_vf(path)
1238
return vf.add_lines_with_ghosts(version_id, parents, lines,
1239
parent_texts=parent_texts,
1240
left_matching_blocks=left_matching_blocks,
1241
nostore_sha=nostore_sha, random_id=random_id,
1242
check_content=check_content)
1243
except NotImplementedError:
1244
return vf.add_lines(version_id, parents, lines,
1245
parent_texts=parent_texts,
1246
left_matching_blocks=left_matching_blocks,
1247
nostore_sha=nostore_sha, random_id=random_id,
1248
check_content=check_content)
1249
except errors.NoSuchFile:
1250
# parent directory may be missing, try again.
1251
self._transport.mkdir(osutils.dirname(path))
1253
return vf.add_lines_with_ghosts(version_id, parents, lines,
1254
parent_texts=parent_texts,
1255
left_matching_blocks=left_matching_blocks,
1256
nostore_sha=nostore_sha, random_id=random_id,
1257
check_content=check_content)
1258
except NotImplementedError:
1259
return vf.add_lines(version_id, parents, lines,
1260
parent_texts=parent_texts,
1261
left_matching_blocks=left_matching_blocks,
1262
nostore_sha=nostore_sha, random_id=random_id,
1263
check_content=check_content)
1265
def annotate(self, key):
1266
"""Return a list of (version-key, line) tuples for the text of key.
1268
:raise RevisionNotPresent: If the key is not present.
1271
path = self._mapper.map(prefix)
1272
vf = self._get_vf(path)
1273
origins = vf.annotate(key[-1])
1275
for origin, line in origins:
1276
result.append((prefix + (origin,), line))
1279
def check(self, progress_bar=None, keys=None):
1280
"""See VersionedFiles.check()."""
1281
# XXX: This is over-enthusiastic but as we only thunk for Weaves today
1282
# this is tolerable. Ideally we'd pass keys down to check() and
1283
# have the older VersiondFile interface updated too.
1284
for prefix, vf in self._iter_all_components():
1286
if keys is not None:
1287
return self.get_record_stream(keys, 'unordered', True)
1289
def get_parent_map(self, keys):
1290
"""Get a map of the parents of keys.
1292
:param keys: The keys to look up parents for.
1293
:return: A mapping from keys to parents. Absent keys are absent from
1296
prefixes = self._partition_keys(keys)
1298
for prefix, suffixes in prefixes.items():
1299
path = self._mapper.map(prefix)
1300
vf = self._get_vf(path)
1301
parent_map = vf.get_parent_map(suffixes)
1302
for key, parents in parent_map.items():
1303
result[prefix + (key,)] = tuple(
1304
prefix + (parent,) for parent in parents)
1307
def _get_vf(self, path):
1308
if not self._is_locked():
1309
raise errors.ObjectNotLocked(self)
1310
return self._file_factory(path, self._transport, create=True,
1311
get_scope=lambda:None)
1313
def _partition_keys(self, keys):
1314
"""Turn keys into a dict of prefix:suffix_list."""
1317
prefix_keys = result.setdefault(key[:-1], [])
1318
prefix_keys.append(key[-1])
1321
def _get_all_prefixes(self):
1322
# Identify all key prefixes.
1323
# XXX: A bit hacky, needs polish.
1324
if type(self._mapper) == ConstantMapper:
1325
paths = [self._mapper.map(())]
1329
for quoted_relpath in self._transport.iter_files_recursive():
1330
path, ext = os.path.splitext(quoted_relpath)
1332
paths = list(relpaths)
1333
prefixes = [self._mapper.unmap(path) for path in paths]
1334
return zip(paths, prefixes)
1336
def get_record_stream(self, keys, ordering, include_delta_closure):
1337
"""See VersionedFiles.get_record_stream()."""
1338
# Ordering will be taken care of by each partitioned store; group keys
1341
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1342
suffixes = [(suffix,) for suffix in suffixes]
1343
for record in vf.get_record_stream(suffixes, ordering,
1344
include_delta_closure):
1345
if record.parents is not None:
1346
record.parents = tuple(
1347
prefix + parent for parent in record.parents)
1348
record.key = prefix + record.key
1351
def _iter_keys_vf(self, keys):
1352
prefixes = self._partition_keys(keys)
1354
for prefix, suffixes in prefixes.items():
1355
path = self._mapper.map(prefix)
1356
vf = self._get_vf(path)
1357
yield prefix, suffixes, vf
1359
def get_sha1s(self, keys):
1360
"""See VersionedFiles.get_sha1s()."""
1362
for prefix,suffixes, vf in self._iter_keys_vf(keys):
1363
vf_sha1s = vf.get_sha1s(suffixes)
1364
for suffix, sha1 in vf_sha1s.iteritems():
1365
sha1s[prefix + (suffix,)] = sha1
1368
def insert_record_stream(self, stream):
1369
"""Insert a record stream into this container.
1371
:param stream: A stream of records to insert.
1373
:seealso VersionedFile.get_record_stream:
1375
for record in stream:
1376
prefix = record.key[:-1]
1377
key = record.key[-1:]
1378
if record.parents is not None:
1379
parents = [parent[-1:] for parent in record.parents]
1382
thunk_record = AdapterFactory(key, parents, record)
1383
path = self._mapper.map(prefix)
1384
# Note that this parses the file many times; we can do better but
1385
# as this only impacts weaves in terms of performance, it is
1387
vf = self._get_vf(path)
1388
vf.insert_record_stream([thunk_record])
1390
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1391
"""Iterate over the lines in the versioned files from keys.
1393
This may return lines from other keys. Each item the returned
1394
iterator yields is a tuple of a line and a text version that that line
1395
is present in (not introduced in).
1397
Ordering of results is in whatever order is most suitable for the
1398
underlying storage format.
1400
If a progress bar is supplied, it may be used to indicate progress.
1401
The caller is responsible for cleaning up progress bars (because this
1405
* Lines are normalised by the underlying store: they will all have \n
1407
* Lines are returned in arbitrary order.
1409
:return: An iterator over (line, key).
1411
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1412
for line, version in vf.iter_lines_added_or_present_in_versions(suffixes):
1413
yield line, prefix + (version,)
1415
def _iter_all_components(self):
1416
for path, prefix in self._get_all_prefixes():
1417
yield prefix, self._get_vf(path)
1420
"""See VersionedFiles.keys()."""
1422
for prefix, vf in self._iter_all_components():
1423
for suffix in vf.versions():
1424
result.add(prefix + (suffix,))
1428
class _PlanMergeVersionedFile(VersionedFiles):
1429
"""A VersionedFile for uncommitted and committed texts.
1431
It is intended to allow merges to be planned with working tree texts.
1432
It implements only the small part of the VersionedFiles interface used by
1433
PlanMerge. It falls back to multiple versionedfiles for data not stored in
1434
_PlanMergeVersionedFile itself.
1436
:ivar: fallback_versionedfiles a list of VersionedFiles objects that can be
1437
queried for missing texts.
1440
def __init__(self, file_id):
1441
"""Create a _PlanMergeVersionedFile.
1443
:param file_id: Used with _PlanMerge code which is not yet fully
1444
tuple-keyspace aware.
1446
self._file_id = file_id
1447
# fallback locations
1448
self.fallback_versionedfiles = []
1449
# Parents for locally held keys.
1451
# line data for locally held keys.
1453
# key lookup providers
1454
self._providers = [DictParentsProvider(self._parents)]
1456
def plan_merge(self, ver_a, ver_b, base=None):
1457
"""See VersionedFile.plan_merge"""
1458
from bzrlib.merge import _PlanMerge
1460
return _PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge()
1461
old_plan = list(_PlanMerge(ver_a, base, self, (self._file_id,)).plan_merge())
1462
new_plan = list(_PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge())
1463
return _PlanMerge._subtract_plans(old_plan, new_plan)
1465
def plan_lca_merge(self, ver_a, ver_b, base=None):
1466
from bzrlib.merge import _PlanLCAMerge
1468
new_plan = _PlanLCAMerge(ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
1471
old_plan = _PlanLCAMerge(ver_a, base, self, (self._file_id,), graph).plan_merge()
1472
return _PlanLCAMerge._subtract_plans(list(old_plan), list(new_plan))
1474
def add_lines(self, key, parents, lines):
1475
"""See VersionedFiles.add_lines
1477
Lines are added locally, not to fallback versionedfiles. Also, ghosts
1478
are permitted. Only reserved ids are permitted.
1480
if type(key) is not tuple:
1481
raise TypeError(key)
1482
if not revision.is_reserved_id(key[-1]):
1483
raise ValueError('Only reserved ids may be used')
1485
raise ValueError('Parents may not be None')
1487
raise ValueError('Lines may not be None')
1488
self._parents[key] = tuple(parents)
1489
self._lines[key] = lines
1491
def get_record_stream(self, keys, ordering, include_delta_closure):
1494
if key in self._lines:
1495
lines = self._lines[key]
1496
parents = self._parents[key]
1498
yield ChunkedContentFactory(key, parents, None, lines)
1499
for versionedfile in self.fallback_versionedfiles:
1500
for record in versionedfile.get_record_stream(
1501
pending, 'unordered', True):
1502
if record.storage_kind == 'absent':
1505
pending.remove(record.key)
1509
# report absent entries
1511
yield AbsentContentFactory(key)
1513
def get_parent_map(self, keys):
1514
"""See VersionedFiles.get_parent_map"""
1515
# We create a new provider because a fallback may have been added.
1516
# If we make fallbacks private we can update a stack list and avoid
1517
# object creation thrashing.
1520
if revision.NULL_REVISION in keys:
1521
keys.remove(revision.NULL_REVISION)
1522
result[revision.NULL_REVISION] = ()
1523
self._providers = self._providers[:1] + self.fallback_versionedfiles
1525
StackedParentsProvider(self._providers).get_parent_map(keys))
1526
for key, parents in result.iteritems():
1528
result[key] = (revision.NULL_REVISION,)
1532
class PlanWeaveMerge(TextMerge):
1533
"""Weave merge that takes a plan as its input.
1535
This exists so that VersionedFile.plan_merge is implementable.
1536
Most callers will want to use WeaveMerge instead.
1539
def __init__(self, plan, a_marker=TextMerge.A_MARKER,
1540
b_marker=TextMerge.B_MARKER):
1541
TextMerge.__init__(self, a_marker, b_marker)
1542
self.plan = list(plan)
1544
def _merge_struct(self):
1549
def outstanding_struct():
1550
if not lines_a and not lines_b:
1552
elif ch_a and not ch_b:
1555
elif ch_b and not ch_a:
1557
elif lines_a == lines_b:
1560
yield (lines_a, lines_b)
1562
# We previously considered either 'unchanged' or 'killed-both' lines
1563
# to be possible places to resynchronize. However, assuming agreement
1564
# on killed-both lines may be too aggressive. -- mbp 20060324
1565
for state, line in self.plan:
1566
if state == 'unchanged':
1567
# resync and flush queued conflicts changes if any
1568
for struct in outstanding_struct():
1574
if state == 'unchanged':
1577
elif state == 'killed-a':
1579
lines_b.append(line)
1580
elif state == 'killed-b':
1582
lines_a.append(line)
1583
elif state == 'new-a':
1585
lines_a.append(line)
1586
elif state == 'new-b':
1588
lines_b.append(line)
1589
elif state == 'conflicted-a':
1591
lines_a.append(line)
1592
elif state == 'conflicted-b':
1594
lines_b.append(line)
1595
elif state == 'killed-both':
1596
# This counts as a change, even though there is no associated
1600
if state not in ('irrelevant', 'ghost-a', 'ghost-b',
1602
raise AssertionError(state)
1603
for struct in outstanding_struct():
1606
def base_from_plan(self):
1607
"""Construct a BASE file from the plan text."""
1609
for state, line in self.plan:
1610
if state in ('killed-a', 'killed-b', 'killed-both', 'unchanged'):
1611
# If unchanged, then this line is straight from base. If a or b
1612
# or both killed the line, then it *used* to be in base.
1613
base_lines.append(line)
1615
if state not in ('killed-base', 'irrelevant',
1616
'ghost-a', 'ghost-b',
1618
'conflicted-a', 'conflicted-b'):
1619
# killed-base, irrelevant means it doesn't apply
1620
# ghost-a/ghost-b are harder to say for sure, but they
1621
# aren't in the 'inc_c' which means they aren't in the
1622
# shared base of a & b. So we don't include them. And
1623
# obviously if the line is newly inserted, it isn't in base
1625
# If 'conflicted-a' or b, then it is new vs one base, but
1626
# old versus another base. However, if we make it present
1627
# in the base, it will be deleted from the target, and it
1628
# seems better to get a line doubled in the merge result,
1629
# rather than have it deleted entirely.
1630
# Example, each node is the 'text' at that point:
1638
# There was a criss-cross conflict merge. Both sides
1639
# include the other, but put themselves first.
1640
# Weave marks this as a 'clean' merge, picking OTHER over
1641
# THIS. (Though the details depend on order inserted into
1643
# LCA generates a plan:
1644
# [('unchanged', M),
1645
# ('conflicted-b', b),
1647
# ('conflicted-a', b),
1649
# If you mark 'conflicted-*' as part of BASE, then a 3-way
1650
# merge tool will cleanly generate "MaN" (as BASE vs THIS
1651
# removes one 'b', and BASE vs OTHER removes the other)
1652
# If you include neither, 3-way creates a clean "MbabN" as
1653
# THIS adds one 'b', and OTHER does too.
1654
# It seems that having the line 2 times is better than
1655
# having it omitted. (Easier to manually delete than notice
1656
# it needs to be added.)
1657
raise AssertionError('Unknown state: %s' % (state,))
1661
class WeaveMerge(PlanWeaveMerge):
1662
"""Weave merge that takes a VersionedFile and two versions as its input."""
1664
def __init__(self, versionedfile, ver_a, ver_b,
1665
a_marker=PlanWeaveMerge.A_MARKER, b_marker=PlanWeaveMerge.B_MARKER):
1666
plan = versionedfile.plan_merge(ver_a, ver_b)
1667
PlanWeaveMerge.__init__(self, plan, a_marker, b_marker)
1670
class VirtualVersionedFiles(VersionedFiles):
1671
"""Dummy implementation for VersionedFiles that uses other functions for
1672
obtaining fulltexts and parent maps.
1674
This is always on the bottom of the stack and uses string keys
1675
(rather than tuples) internally.
1678
def __init__(self, get_parent_map, get_lines):
1679
"""Create a VirtualVersionedFiles.
1681
:param get_parent_map: Same signature as Repository.get_parent_map.
1682
:param get_lines: Should return lines for specified key or None if
1685
super(VirtualVersionedFiles, self).__init__()
1686
self._get_parent_map = get_parent_map
1687
self._get_lines = get_lines
1689
def check(self, progressbar=None):
1690
"""See VersionedFiles.check.
1692
:note: Always returns True for VirtualVersionedFiles.
1696
def add_mpdiffs(self, records):
1697
"""See VersionedFiles.mpdiffs.
1699
:note: Not implemented for VirtualVersionedFiles.
1701
raise NotImplementedError(self.add_mpdiffs)
1703
def get_parent_map(self, keys):
1704
"""See VersionedFiles.get_parent_map."""
1705
return dict([((k,), tuple([(p,) for p in v]))
1706
for k,v in self._get_parent_map([k for (k,) in keys]).iteritems()])
1708
def get_sha1s(self, keys):
1709
"""See VersionedFiles.get_sha1s."""
1712
lines = self._get_lines(k)
1713
if lines is not None:
1714
if not isinstance(lines, list):
1715
raise AssertionError
1716
ret[(k,)] = osutils.sha_strings(lines)
1719
def get_record_stream(self, keys, ordering, include_delta_closure):
1720
"""See VersionedFiles.get_record_stream."""
1721
for (k,) in list(keys):
1722
lines = self._get_lines(k)
1723
if lines is not None:
1724
if not isinstance(lines, list):
1725
raise AssertionError
1726
yield ChunkedContentFactory((k,), None,
1727
sha1=osutils.sha_strings(lines),
1730
yield AbsentContentFactory((k,))
1732
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1733
"""See VersionedFile.iter_lines_added_or_present_in_versions()."""
1734
for i, (key,) in enumerate(keys):
1736
pb.update("Finding changed lines", i, len(keys))
1737
for l in self._get_lines(key):
1741
class NoDupeAddLinesDecorator(object):
1742
"""Decorator for a VersionedFiles that skips doing an add_lines if the key
1746
def __init__(self, store):
1749
def add_lines(self, key, parents, lines, parent_texts=None,
1750
left_matching_blocks=None, nostore_sha=None, random_id=False,
1751
check_content=True):
1752
"""See VersionedFiles.add_lines.
1754
This implementation may return None as the third element of the return
1755
value when the original store wouldn't.
1758
raise NotImplementedError(
1759
"NoDupeAddLinesDecorator.add_lines does not implement the "
1760
"nostore_sha behaviour.")
1762
sha1 = osutils.sha_strings(lines)
1763
key = ("sha1:" + sha1,)
1766
if key in self._store.get_parent_map([key]):
1767
# This key has already been inserted, so don't do it again.
1769
sha1 = osutils.sha_strings(lines)
1770
return sha1, sum(map(len, lines)), None
1771
return self._store.add_lines(key, parents, lines,
1772
parent_texts=parent_texts,
1773
left_matching_blocks=left_matching_blocks,
1774
nostore_sha=nostore_sha, random_id=random_id,
1775
check_content=check_content)
1777
def __getattr__(self, name):
1778
return getattr(self._store, name)
1781
def network_bytes_to_kind_and_offset(network_bytes):
1782
"""Strip of a record kind from the front of network_bytes.
1784
:param network_bytes: The bytes of a record.
1785
:return: A tuple (storage_kind, offset_of_remaining_bytes)
1787
line_end = network_bytes.find('\n')
1788
storage_kind = network_bytes[:line_end]
1789
return storage_kind, line_end + 1
1792
class NetworkRecordStream(object):
1793
"""A record_stream which reconstitures a serialised stream."""
1795
def __init__(self, bytes_iterator):
1796
"""Create a NetworkRecordStream.
1798
:param bytes_iterator: An iterator of bytes. Each item in this
1799
iterator should have been obtained from a record_streams'
1800
record.get_bytes_as(record.storage_kind) call.
1802
self._bytes_iterator = bytes_iterator
1803
self._kind_factory = {
1804
'fulltext': fulltext_network_to_record,
1805
'groupcompress-block': groupcompress.network_block_to_records,
1806
'knit-ft-gz': knit.knit_network_to_record,
1807
'knit-delta-gz': knit.knit_network_to_record,
1808
'knit-annotated-ft-gz': knit.knit_network_to_record,
1809
'knit-annotated-delta-gz': knit.knit_network_to_record,
1810
'knit-delta-closure': knit.knit_delta_closure_to_records,
1816
:return: An iterator as per VersionedFiles.get_record_stream().
1818
for bytes in self._bytes_iterator:
1819
storage_kind, line_end = network_bytes_to_kind_and_offset(bytes)
1820
for record in self._kind_factory[storage_kind](
1821
storage_kind, bytes, line_end):
1825
def fulltext_network_to_record(kind, bytes, line_end):
1826
"""Convert a network fulltext record to record."""
1827
meta_len, = struct.unpack('!L', bytes[line_end:line_end+4])
1828
record_meta = bytes[line_end+4:line_end+4+meta_len]
1829
key, parents = bencode.bdecode_as_tuple(record_meta)
1830
if parents == 'nil':
1832
fulltext = bytes[line_end+4+meta_len:]
1833
return [FulltextContentFactory(key, parents, None, fulltext)]
1836
def _length_prefix(bytes):
1837
return struct.pack('!L', len(bytes))
1840
def record_to_fulltext_bytes(record):
1841
if record.parents is None:
1844
parents = record.parents
1845
record_meta = bencode.bencode((record.key, parents))
1846
record_content = record.get_bytes_as('fulltext')
1847
return "fulltext\n%s%s%s" % (
1848
_length_prefix(record_meta), record_meta, record_content)
1851
def sort_groupcompress(parent_map):
1852
"""Sort and group the keys in parent_map into groupcompress order.
1854
groupcompress is defined (currently) as reverse-topological order, grouped
1857
:return: A sorted-list of keys
1859
# gc-optimal ordering is approximately reverse topological,
1860
# properly grouped by file-id.
1862
for item in parent_map.iteritems():
1864
if isinstance(key, str) or len(key) == 1:
1869
per_prefix_map[prefix].append(item)
1871
per_prefix_map[prefix] = [item]
1874
for prefix in sorted(per_prefix_map):
1875
present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
added
removed
bzrlib/versionedfile.py
