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."""
19
from __future__ import absolute_import
22
from cStringIO import StringIO
25
from zlib import adler32
27
from bzrlib.lazy_import import lazy_import
28
lazy_import(globals(), """
44
from bzrlib.registry import Registry
45
from bzrlib.textmerge import TextMerge
48
adapter_registry = Registry()
49
adapter_registry.register_lazy(('knit-delta-gz', 'fulltext'), 'bzrlib.knit',
50
'DeltaPlainToFullText')
51
adapter_registry.register_lazy(('knit-ft-gz', 'fulltext'), 'bzrlib.knit',
53
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'knit-delta-gz'),
54
'bzrlib.knit', 'DeltaAnnotatedToUnannotated')
55
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'fulltext'),
56
'bzrlib.knit', 'DeltaAnnotatedToFullText')
57
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'knit-ft-gz'),
58
'bzrlib.knit', 'FTAnnotatedToUnannotated')
59
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'fulltext'),
60
'bzrlib.knit', 'FTAnnotatedToFullText')
61
# adapter_registry.register_lazy(('knit-annotated-ft-gz', 'chunked'),
62
# 'bzrlib.knit', 'FTAnnotatedToChunked')
65
class ContentFactory(object):
66
"""Abstract interface for insertion and retrieval from a VersionedFile.
68
:ivar sha1: None, or the sha1 of the content fulltext.
69
:ivar storage_kind: The native storage kind of this factory. One of
70
'mpdiff', 'knit-annotated-ft', 'knit-annotated-delta', 'knit-ft',
71
'knit-delta', 'fulltext', 'knit-annotated-ft-gz',
72
'knit-annotated-delta-gz', 'knit-ft-gz', 'knit-delta-gz'.
73
:ivar key: The key of this content. Each key is a tuple with a single
75
:ivar parents: A tuple of parent keys for self.key. If the object has
76
no parent information, None (as opposed to () for an empty list of
81
"""Create a ContentFactory."""
83
self.storage_kind = None
88
class ChunkedContentFactory(ContentFactory):
89
"""Static data content factory.
91
This takes a 'chunked' list of strings. The only requirement on 'chunked' is
92
that ''.join(lines) becomes a valid fulltext. A tuple of a single string
93
satisfies this, as does a list of lines.
95
:ivar sha1: None, or the sha1 of the content fulltext.
96
:ivar storage_kind: The native storage kind of this factory. Always
98
:ivar key: The key of this content. Each key is a tuple with a single
100
:ivar parents: A tuple of parent keys for self.key. If the object has
101
no parent information, None (as opposed to () for an empty list of
105
def __init__(self, key, parents, sha1, chunks):
106
"""Create a ContentFactory."""
108
self.storage_kind = 'chunked'
110
self.parents = parents
111
self._chunks = chunks
113
def get_bytes_as(self, storage_kind):
114
if storage_kind == 'chunked':
116
elif storage_kind == 'fulltext':
117
return ''.join(self._chunks)
118
raise errors.UnavailableRepresentation(self.key, storage_kind,
122
class FulltextContentFactory(ContentFactory):
123
"""Static data content factory.
125
This takes a fulltext when created and just returns that during
126
get_bytes_as('fulltext').
128
:ivar sha1: None, or the sha1 of the content fulltext.
129
:ivar storage_kind: The native storage kind of this factory. Always
131
:ivar key: The key of this content. Each key is a tuple with a single
133
:ivar parents: A tuple of parent keys for self.key. If the object has
134
no parent information, None (as opposed to () for an empty list of
138
def __init__(self, key, parents, sha1, text):
139
"""Create a ContentFactory."""
141
self.storage_kind = 'fulltext'
143
self.parents = parents
146
def get_bytes_as(self, storage_kind):
147
if storage_kind == self.storage_kind:
149
elif storage_kind == 'chunked':
151
raise errors.UnavailableRepresentation(self.key, storage_kind,
155
class AbsentContentFactory(ContentFactory):
156
"""A placeholder content factory for unavailable texts.
159
:ivar storage_kind: 'absent'.
160
:ivar key: The key of this content. Each key is a tuple with a single
165
def __init__(self, key):
166
"""Create a ContentFactory."""
168
self.storage_kind = 'absent'
172
def get_bytes_as(self, storage_kind):
173
raise ValueError('A request was made for key: %s, but that'
174
' content is not available, and the calling'
175
' code does not handle if it is missing.'
179
class AdapterFactory(ContentFactory):
180
"""A content factory to adapt between key prefix's."""
182
def __init__(self, key, parents, adapted):
183
"""Create an adapter factory instance."""
185
self.parents = parents
186
self._adapted = adapted
188
def __getattr__(self, attr):
189
"""Return a member from the adapted object."""
190
if attr in ('key', 'parents'):
191
return self.__dict__[attr]
193
return getattr(self._adapted, attr)
196
def filter_absent(record_stream):
197
"""Adapt a record stream to remove absent records."""
198
for record in record_stream:
199
if record.storage_kind != 'absent':
203
class _MPDiffGenerator(object):
204
"""Pull out the functionality for generating mp_diffs."""
206
def __init__(self, vf, keys):
208
# This is the order the keys were requested in
209
self.ordered_keys = tuple(keys)
210
# keys + their parents, what we need to compute the diffs
211
self.needed_keys = ()
212
# Map from key: mp_diff
214
# Map from key: parents_needed (may have ghosts)
216
# Parents that aren't present
217
self.ghost_parents = ()
218
# Map from parent_key => number of children for this text
220
# Content chunks that are cached while we still need them
223
def _find_needed_keys(self):
224
"""Find the set of keys we need to request.
226
This includes all the original keys passed in, and the non-ghost
227
parents of those keys.
229
:return: (needed_keys, refcounts)
230
needed_keys is the set of all texts we need to extract
231
refcounts is a dict of {key: num_children} letting us know when we
232
no longer need to cache a given parent text
234
# All the keys and their parents
235
needed_keys = set(self.ordered_keys)
236
parent_map = self.vf.get_parent_map(needed_keys)
237
self.parent_map = parent_map
238
# TODO: Should we be using a different construct here? I think this
239
# uses difference_update internally, and we expect the result to
241
missing_keys = needed_keys.difference(parent_map)
243
raise errors.RevisionNotPresent(list(missing_keys)[0], self.vf)
244
# Parents that might be missing. They are allowed to be ghosts, but we
245
# should check for them
247
setdefault = refcounts.setdefault
249
for child_key, parent_keys in parent_map.iteritems():
251
# parent_keys may be None if a given VersionedFile claims to
252
# not support graph operations.
254
just_parents.update(parent_keys)
255
needed_keys.update(parent_keys)
256
for p in parent_keys:
257
refcounts[p] = setdefault(p, 0) + 1
258
just_parents.difference_update(parent_map)
259
# Remove any parents that are actually ghosts from the needed set
260
self.present_parents = set(self.vf.get_parent_map(just_parents))
261
self.ghost_parents = just_parents.difference(self.present_parents)
262
needed_keys.difference_update(self.ghost_parents)
263
self.needed_keys = needed_keys
264
self.refcounts = refcounts
265
return needed_keys, refcounts
267
def _compute_diff(self, key, parent_lines, lines):
268
"""Compute a single mp_diff, and store it in self._diffs"""
269
if len(parent_lines) > 0:
270
# XXX: _extract_blocks is not usefully defined anywhere...
271
# It was meant to extract the left-parent diff without
272
# having to recompute it for Knit content (pack-0.92,
273
# etc). That seems to have regressed somewhere
274
left_parent_blocks = self.vf._extract_blocks(key,
275
parent_lines[0], lines)
277
left_parent_blocks = None
278
diff = multiparent.MultiParent.from_lines(lines,
279
parent_lines, left_parent_blocks)
280
self.diffs[key] = diff
282
def _process_one_record(self, key, this_chunks):
284
if key in self.parent_map:
285
# This record should be ready to diff, since we requested
286
# content in 'topological' order
287
parent_keys = self.parent_map.pop(key)
288
# If a VersionedFile claims 'no-graph' support, then it may return
289
# None for any parent request, so we replace it with an empty tuple
290
if parent_keys is None:
293
for p in parent_keys:
294
# Alternatively we could check p not in self.needed_keys, but
295
# ghost_parents should be tiny versus huge
296
if p in self.ghost_parents:
298
refcount = self.refcounts[p]
299
if refcount == 1: # Last child reference
300
self.refcounts.pop(p)
301
parent_chunks = self.chunks.pop(p)
303
self.refcounts[p] = refcount - 1
304
parent_chunks = self.chunks[p]
305
p_lines = osutils.chunks_to_lines(parent_chunks)
306
# TODO: Should we cache the line form? We did the
307
# computation to get it, but storing it this way will
308
# be less memory efficient...
309
parent_lines.append(p_lines)
311
lines = osutils.chunks_to_lines(this_chunks)
312
# Since we needed the lines, we'll go ahead and cache them this way
314
self._compute_diff(key, parent_lines, lines)
316
# Is this content required for any more children?
317
if key in self.refcounts:
318
self.chunks[key] = this_chunks
320
def _extract_diffs(self):
321
needed_keys, refcounts = self._find_needed_keys()
322
for record in self.vf.get_record_stream(needed_keys,
323
'topological', True):
324
if record.storage_kind == 'absent':
325
raise errors.RevisionNotPresent(record.key, self.vf)
326
self._process_one_record(record.key,
327
record.get_bytes_as('chunked'))
329
def compute_diffs(self):
330
self._extract_diffs()
331
dpop = self.diffs.pop
332
return [dpop(k) for k in self.ordered_keys]
335
class VersionedFile(object):
336
"""Versioned text file storage.
338
A versioned file manages versions of line-based text files,
339
keeping track of the originating version for each line.
341
To clients the "lines" of the file are represented as a list of
342
strings. These strings will typically have terminal newline
343
characters, but this is not required. In particular files commonly
344
do not have a newline at the end of the file.
346
Texts are identified by a version-id string.
350
def check_not_reserved_id(version_id):
351
revision.check_not_reserved_id(version_id)
353
def copy_to(self, name, transport):
354
"""Copy this versioned file to name on transport."""
355
raise NotImplementedError(self.copy_to)
357
def get_record_stream(self, versions, ordering, include_delta_closure):
358
"""Get a stream of records for versions.
360
:param versions: The versions to include. Each version is a tuple
362
:param ordering: Either 'unordered' or 'topological'. A topologically
363
sorted stream has compression parents strictly before their
365
:param include_delta_closure: If True then the closure across any
366
compression parents will be included (in the data content of the
367
stream, not in the emitted records). This guarantees that
368
'fulltext' can be used successfully on every record.
369
:return: An iterator of ContentFactory objects, each of which is only
370
valid until the iterator is advanced.
372
raise NotImplementedError(self.get_record_stream)
374
def has_version(self, version_id):
375
"""Returns whether version is present."""
376
raise NotImplementedError(self.has_version)
378
def insert_record_stream(self, stream):
379
"""Insert a record stream into this versioned file.
381
:param stream: A stream of records to insert.
383
:seealso VersionedFile.get_record_stream:
385
raise NotImplementedError
387
def add_lines(self, version_id, parents, lines, parent_texts=None,
388
left_matching_blocks=None, nostore_sha=None, random_id=False,
390
"""Add a single text on top of the versioned file.
392
Must raise RevisionAlreadyPresent if the new version is
393
already present in file history.
395
Must raise RevisionNotPresent if any of the given parents are
396
not present in file history.
398
:param lines: A list of lines. Each line must be a bytestring. And all
399
of them except the last must be terminated with \n and contain no
400
other \n's. The last line may either contain no \n's or a single
401
terminated \n. If the lines list does meet this constraint the add
402
routine may error or may succeed - but you will be unable to read
403
the data back accurately. (Checking the lines have been split
404
correctly is expensive and extremely unlikely to catch bugs so it
405
is not done at runtime unless check_content is True.)
406
:param parent_texts: An optional dictionary containing the opaque
407
representations of some or all of the parents of version_id to
408
allow delta optimisations. VERY IMPORTANT: the texts must be those
409
returned by add_lines or data corruption can be caused.
410
:param left_matching_blocks: a hint about which areas are common
411
between the text and its left-hand-parent. The format is
412
the SequenceMatcher.get_matching_blocks format.
413
:param nostore_sha: Raise ExistingContent and do not add the lines to
414
the versioned file if the digest of the lines matches this.
415
:param random_id: If True a random id has been selected rather than
416
an id determined by some deterministic process such as a converter
417
from a foreign VCS. When True the backend may choose not to check
418
for uniqueness of the resulting key within the versioned file, so
419
this should only be done when the result is expected to be unique
421
:param check_content: If True, the lines supplied are verified to be
422
bytestrings that are correctly formed lines.
423
:return: The text sha1, the number of bytes in the text, and an opaque
424
representation of the inserted version which can be provided
425
back to future add_lines calls in the parent_texts dictionary.
427
self._check_write_ok()
428
return self._add_lines(version_id, parents, lines, parent_texts,
429
left_matching_blocks, nostore_sha, random_id, check_content)
431
def _add_lines(self, version_id, parents, lines, parent_texts,
432
left_matching_blocks, nostore_sha, random_id, check_content):
433
"""Helper to do the class specific add_lines."""
434
raise NotImplementedError(self.add_lines)
436
def add_lines_with_ghosts(self, version_id, parents, lines,
437
parent_texts=None, nostore_sha=None, random_id=False,
438
check_content=True, left_matching_blocks=None):
439
"""Add lines to the versioned file, allowing ghosts to be present.
441
This takes the same parameters as add_lines and returns the same.
443
self._check_write_ok()
444
return self._add_lines_with_ghosts(version_id, parents, lines,
445
parent_texts, nostore_sha, random_id, check_content, left_matching_blocks)
447
def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts,
448
nostore_sha, random_id, check_content, left_matching_blocks):
449
"""Helper to do class specific add_lines_with_ghosts."""
450
raise NotImplementedError(self.add_lines_with_ghosts)
452
def check(self, progress_bar=None):
453
"""Check the versioned file for integrity."""
454
raise NotImplementedError(self.check)
456
def _check_lines_not_unicode(self, lines):
457
"""Check that lines being added to a versioned file are not unicode."""
459
if line.__class__ is not str:
460
raise errors.BzrBadParameterUnicode("lines")
462
def _check_lines_are_lines(self, lines):
463
"""Check that the lines really are full lines without inline EOL."""
465
if '\n' in line[:-1]:
466
raise errors.BzrBadParameterContainsNewline("lines")
468
def get_format_signature(self):
469
"""Get a text description of the data encoding in this file.
473
raise NotImplementedError(self.get_format_signature)
475
def make_mpdiffs(self, version_ids):
476
"""Create multiparent diffs for specified versions."""
477
# XXX: Can't use _MPDiffGenerator just yet. This is because version_ids
478
# is a list of strings, not keys. And while self.get_record_stream
479
# is supported, it takes *keys*, while self.get_parent_map() takes
481
knit_versions = set()
482
knit_versions.update(version_ids)
483
parent_map = self.get_parent_map(version_ids)
484
for version_id in version_ids:
486
knit_versions.update(parent_map[version_id])
488
raise errors.RevisionNotPresent(version_id, self)
489
# We need to filter out ghosts, because we can't diff against them.
490
knit_versions = set(self.get_parent_map(knit_versions).keys())
491
lines = dict(zip(knit_versions,
492
self._get_lf_split_line_list(knit_versions)))
494
for version_id in version_ids:
495
target = lines[version_id]
497
parents = [lines[p] for p in parent_map[version_id] if p in
500
# I don't know how this could ever trigger.
501
# parent_map[version_id] was already triggered in the previous
502
# for loop, and lines[p] has the 'if p in knit_versions' check,
503
# so we again won't have a KeyError.
504
raise errors.RevisionNotPresent(version_id, self)
506
left_parent_blocks = self._extract_blocks(version_id,
509
left_parent_blocks = None
510
diffs.append(multiparent.MultiParent.from_lines(target, parents,
514
def _extract_blocks(self, version_id, source, target):
517
def add_mpdiffs(self, records):
518
"""Add mpdiffs to this VersionedFile.
520
Records should be iterables of version, parents, expected_sha1,
521
mpdiff. mpdiff should be a MultiParent instance.
523
# Does this need to call self._check_write_ok()? (IanC 20070919)
525
mpvf = multiparent.MultiMemoryVersionedFile()
527
for version, parent_ids, expected_sha1, mpdiff in records:
528
versions.append(version)
529
mpvf.add_diff(mpdiff, version, parent_ids)
530
needed_parents = set()
531
for version, parent_ids, expected_sha1, mpdiff in records:
532
needed_parents.update(p for p in parent_ids
533
if not mpvf.has_version(p))
534
present_parents = set(self.get_parent_map(needed_parents).keys())
535
for parent_id, lines in zip(present_parents,
536
self._get_lf_split_line_list(present_parents)):
537
mpvf.add_version(lines, parent_id, [])
538
for (version, parent_ids, expected_sha1, mpdiff), lines in\
539
zip(records, mpvf.get_line_list(versions)):
540
if len(parent_ids) == 1:
541
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
542
mpvf.get_diff(parent_ids[0]).num_lines()))
544
left_matching_blocks = None
546
_, _, version_text = self.add_lines_with_ghosts(version,
547
parent_ids, lines, vf_parents,
548
left_matching_blocks=left_matching_blocks)
549
except NotImplementedError:
550
# The vf can't handle ghosts, so add lines normally, which will
551
# (reasonably) fail if there are ghosts in the data.
552
_, _, version_text = self.add_lines(version,
553
parent_ids, lines, vf_parents,
554
left_matching_blocks=left_matching_blocks)
555
vf_parents[version] = version_text
556
sha1s = self.get_sha1s(versions)
557
for version, parent_ids, expected_sha1, mpdiff in records:
558
if expected_sha1 != sha1s[version]:
559
raise errors.VersionedFileInvalidChecksum(version)
561
def get_text(self, version_id):
562
"""Return version contents as a text string.
564
Raises RevisionNotPresent if version is not present in
567
return ''.join(self.get_lines(version_id))
568
get_string = get_text
570
def get_texts(self, version_ids):
571
"""Return the texts of listed versions as a list of strings.
573
Raises RevisionNotPresent if version is not present in
576
return [''.join(self.get_lines(v)) for v in version_ids]
578
def get_lines(self, version_id):
579
"""Return version contents as a sequence of lines.
581
Raises RevisionNotPresent if version is not present in
584
raise NotImplementedError(self.get_lines)
586
def _get_lf_split_line_list(self, version_ids):
587
return [StringIO(t).readlines() for t in self.get_texts(version_ids)]
589
def get_ancestry(self, version_ids, topo_sorted=True):
590
"""Return a list of all ancestors of given version(s). This
591
will not include the null revision.
593
This list will not be topologically sorted if topo_sorted=False is
596
Must raise RevisionNotPresent if any of the given versions are
597
not present in file history."""
598
if isinstance(version_ids, basestring):
599
version_ids = [version_ids]
600
raise NotImplementedError(self.get_ancestry)
602
def get_ancestry_with_ghosts(self, version_ids):
603
"""Return a list of all ancestors of given version(s). This
604
will not include the null revision.
606
Must raise RevisionNotPresent if any of the given versions are
607
not present in file history.
609
Ghosts that are known about will be included in ancestry list,
610
but are not explicitly marked.
612
raise NotImplementedError(self.get_ancestry_with_ghosts)
614
def get_parent_map(self, version_ids):
615
"""Get a map of the parents of version_ids.
617
:param version_ids: The version ids to look up parents for.
618
:return: A mapping from version id to parents.
620
raise NotImplementedError(self.get_parent_map)
622
def get_parents_with_ghosts(self, version_id):
623
"""Return version names for parents of version_id.
625
Will raise RevisionNotPresent if version_id is not present
628
Ghosts that are known about will be included in the parent list,
629
but are not explicitly marked.
632
return list(self.get_parent_map([version_id])[version_id])
634
raise errors.RevisionNotPresent(version_id, self)
636
def annotate(self, version_id):
637
"""Return a list of (version-id, line) tuples for version_id.
639
:raise RevisionNotPresent: If the given version is
640
not present in file history.
642
raise NotImplementedError(self.annotate)
644
def iter_lines_added_or_present_in_versions(self, version_ids=None,
646
"""Iterate over the lines in the versioned file from version_ids.
648
This may return lines from other versions. Each item the returned
649
iterator yields is a tuple of a line and a text version that that line
650
is present in (not introduced in).
652
Ordering of results is in whatever order is most suitable for the
653
underlying storage format.
655
If a progress bar is supplied, it may be used to indicate progress.
656
The caller is responsible for cleaning up progress bars (because this
659
NOTES: Lines are normalised: they will all have \n terminators.
660
Lines are returned in arbitrary order.
662
:return: An iterator over (line, version_id).
664
raise NotImplementedError(self.iter_lines_added_or_present_in_versions)
666
def plan_merge(self, ver_a, ver_b):
667
"""Return pseudo-annotation indicating how the two versions merge.
669
This is computed between versions a and b and their common
672
Weave lines present in none of them are skipped entirely.
675
killed-base Dead in base revision
676
killed-both Killed in each revision
679
unchanged Alive in both a and b (possibly created in both)
682
ghost-a Killed in a, unborn in b
683
ghost-b Killed in b, unborn in a
684
irrelevant Not in either revision
686
raise NotImplementedError(VersionedFile.plan_merge)
688
def weave_merge(self, plan, a_marker=TextMerge.A_MARKER,
689
b_marker=TextMerge.B_MARKER):
690
return PlanWeaveMerge(plan, a_marker, b_marker).merge_lines()[0]
693
class RecordingVersionedFilesDecorator(object):
694
"""A minimal versioned files that records calls made on it.
696
Only enough methods have been added to support tests using it to date.
698
:ivar calls: A list of the calls made; can be reset at any time by
702
def __init__(self, backing_vf):
703
"""Create a RecordingVersionedFilesDecorator decorating backing_vf.
705
:param backing_vf: The versioned file to answer all methods.
707
self._backing_vf = backing_vf
710
def add_lines(self, key, parents, lines, parent_texts=None,
711
left_matching_blocks=None, nostore_sha=None, random_id=False,
713
self.calls.append(("add_lines", key, parents, lines, parent_texts,
714
left_matching_blocks, nostore_sha, random_id, check_content))
715
return self._backing_vf.add_lines(key, parents, lines, parent_texts,
716
left_matching_blocks, nostore_sha, random_id, check_content)
719
self._backing_vf.check()
721
def get_parent_map(self, keys):
722
self.calls.append(("get_parent_map", copy(keys)))
723
return self._backing_vf.get_parent_map(keys)
725
def get_record_stream(self, keys, sort_order, include_delta_closure):
726
self.calls.append(("get_record_stream", list(keys), sort_order,
727
include_delta_closure))
728
return self._backing_vf.get_record_stream(keys, sort_order,
729
include_delta_closure)
731
def get_sha1s(self, keys):
732
self.calls.append(("get_sha1s", copy(keys)))
733
return self._backing_vf.get_sha1s(keys)
735
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
736
self.calls.append(("iter_lines_added_or_present_in_keys", copy(keys)))
737
return self._backing_vf.iter_lines_added_or_present_in_keys(keys, pb=pb)
740
self.calls.append(("keys",))
741
return self._backing_vf.keys()
744
class OrderingVersionedFilesDecorator(RecordingVersionedFilesDecorator):
745
"""A VF that records calls, and returns keys in specific order.
747
:ivar calls: A list of the calls made; can be reset at any time by
751
def __init__(self, backing_vf, key_priority):
752
"""Create a RecordingVersionedFilesDecorator decorating backing_vf.
754
:param backing_vf: The versioned file to answer all methods.
755
:param key_priority: A dictionary defining what order keys should be
756
returned from an 'unordered' get_record_stream request.
757
Keys with lower priority are returned first, keys not present in
758
the map get an implicit priority of 0, and are returned in
759
lexicographical order.
761
RecordingVersionedFilesDecorator.__init__(self, backing_vf)
762
self._key_priority = key_priority
764
def get_record_stream(self, keys, sort_order, include_delta_closure):
765
self.calls.append(("get_record_stream", list(keys), sort_order,
766
include_delta_closure))
767
if sort_order == 'unordered':
769
return (self._key_priority.get(key, 0), key)
770
# Use a defined order by asking for the keys one-by-one from the
772
for key in sorted(keys, key=sort_key):
773
for record in self._backing_vf.get_record_stream([key],
774
'unordered', include_delta_closure):
777
for record in self._backing_vf.get_record_stream(keys, sort_order,
778
include_delta_closure):
782
class KeyMapper(object):
783
"""KeyMappers map between keys and underlying partitioned storage."""
786
"""Map key to an underlying storage identifier.
788
:param key: A key tuple e.g. ('file-id', 'revision-id').
789
:return: An underlying storage identifier, specific to the partitioning
792
raise NotImplementedError(self.map)
794
def unmap(self, partition_id):
795
"""Map a partitioned storage id back to a key prefix.
797
:param partition_id: The underlying partition id.
798
:return: As much of a key (or prefix) as is derivable from the partition
801
raise NotImplementedError(self.unmap)
804
class ConstantMapper(KeyMapper):
805
"""A key mapper that maps to a constant result."""
807
def __init__(self, result):
808
"""Create a ConstantMapper which will return result for all maps."""
809
self._result = result
812
"""See KeyMapper.map()."""
816
class URLEscapeMapper(KeyMapper):
817
"""Base class for use with transport backed storage.
819
This provides a map and unmap wrapper that respectively url escape and
820
unescape their outputs and inputs.
824
"""See KeyMapper.map()."""
825
return urlutils.quote(self._map(key))
827
def unmap(self, partition_id):
828
"""See KeyMapper.unmap()."""
829
return self._unmap(urlutils.unquote(partition_id))
832
class PrefixMapper(URLEscapeMapper):
833
"""A key mapper that extracts the first component of a key.
835
This mapper is for use with a transport based backend.
839
"""See KeyMapper.map()."""
842
def _unmap(self, partition_id):
843
"""See KeyMapper.unmap()."""
844
return (partition_id,)
847
class HashPrefixMapper(URLEscapeMapper):
848
"""A key mapper that combines the first component of a key with a hash.
850
This mapper is for use with a transport based backend.
854
"""See KeyMapper.map()."""
855
prefix = self._escape(key[0])
856
return "%02x/%s" % (adler32(prefix) & 0xff, prefix)
858
def _escape(self, prefix):
859
"""No escaping needed here."""
862
def _unmap(self, partition_id):
863
"""See KeyMapper.unmap()."""
864
return (self._unescape(osutils.basename(partition_id)),)
866
def _unescape(self, basename):
867
"""No unescaping needed for HashPrefixMapper."""
871
class HashEscapedPrefixMapper(HashPrefixMapper):
872
"""Combines the escaped first component of a key with a hash.
874
This mapper is for use with a transport based backend.
877
_safe = "abcdefghijklmnopqrstuvwxyz0123456789-_@,."
879
def _escape(self, prefix):
880
"""Turn a key element into a filesystem safe string.
882
This is similar to a plain urlutils.quote, except
883
it uses specific safe characters, so that it doesn't
884
have to translate a lot of valid file ids.
886
# @ does not get escaped. This is because it is a valid
887
# filesystem character we use all the time, and it looks
888
# a lot better than seeing %40 all the time.
889
r = [((c in self._safe) and c or ('%%%02x' % ord(c)))
893
def _unescape(self, basename):
894
"""Escaped names are easily unescaped by urlutils."""
895
return urlutils.unquote(basename)
898
def make_versioned_files_factory(versioned_file_factory, mapper):
899
"""Create a ThunkedVersionedFiles factory.
901
This will create a callable which when called creates a
902
ThunkedVersionedFiles on a transport, using mapper to access individual
903
versioned files, and versioned_file_factory to create each individual file.
905
def factory(transport):
906
return ThunkedVersionedFiles(transport, versioned_file_factory, mapper,
911
class VersionedFiles(object):
912
"""Storage for many versioned files.
914
This object allows a single keyspace for accessing the history graph and
915
contents of named bytestrings.
917
Currently no implementation allows the graph of different key prefixes to
918
intersect, but the API does allow such implementations in the future.
920
The keyspace is expressed via simple tuples. Any instance of VersionedFiles
921
may have a different length key-size, but that size will be constant for
922
all texts added to or retrieved from it. For instance, bzrlib uses
923
instances with a key-size of 2 for storing user files in a repository, with
924
the first element the fileid, and the second the version of that file.
926
The use of tuples allows a single code base to support several different
927
uses with only the mapping logic changing from instance to instance.
929
:ivar _immediate_fallback_vfs: For subclasses that support stacking,
930
this is a list of other VersionedFiles immediately underneath this
931
one. They may in turn each have further fallbacks.
934
def add_lines(self, key, parents, lines, parent_texts=None,
935
left_matching_blocks=None, nostore_sha=None, random_id=False,
937
"""Add a text to the store.
939
:param key: The key tuple of the text to add. If the last element is
940
None, a CHK string will be generated during the addition.
941
:param parents: The parents key tuples of the text to add.
942
:param lines: A list of lines. Each line must be a bytestring. And all
943
of them except the last must be terminated with \n and contain no
944
other \n's. The last line may either contain no \n's or a single
945
terminating \n. If the lines list does meet this constraint the add
946
routine may error or may succeed - but you will be unable to read
947
the data back accurately. (Checking the lines have been split
948
correctly is expensive and extremely unlikely to catch bugs so it
949
is not done at runtime unless check_content is True.)
950
:param parent_texts: An optional dictionary containing the opaque
951
representations of some or all of the parents of version_id to
952
allow delta optimisations. VERY IMPORTANT: the texts must be those
953
returned by add_lines or data corruption can be caused.
954
:param left_matching_blocks: a hint about which areas are common
955
between the text and its left-hand-parent. The format is
956
the SequenceMatcher.get_matching_blocks format.
957
:param nostore_sha: Raise ExistingContent and do not add the lines to
958
the versioned file if the digest of the lines matches this.
959
:param random_id: If True a random id has been selected rather than
960
an id determined by some deterministic process such as a converter
961
from a foreign VCS. When True the backend may choose not to check
962
for uniqueness of the resulting key within the versioned file, so
963
this should only be done when the result is expected to be unique
965
:param check_content: If True, the lines supplied are verified to be
966
bytestrings that are correctly formed lines.
967
:return: The text sha1, the number of bytes in the text, and an opaque
968
representation of the inserted version which can be provided
969
back to future add_lines calls in the parent_texts dictionary.
971
raise NotImplementedError(self.add_lines)
973
def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
974
"""Add a text to the store.
976
This is a private function for use by VersionedFileCommitBuilder.
978
:param key: The key tuple of the text to add. If the last element is
979
None, a CHK string will be generated during the addition.
980
:param parents: The parents key tuples of the text to add.
981
:param text: A string containing the text to be committed.
982
:param nostore_sha: Raise ExistingContent and do not add the lines to
983
the versioned file if the digest of the lines matches this.
984
:param random_id: If True a random id has been selected rather than
985
an id determined by some deterministic process such as a converter
986
from a foreign VCS. When True the backend may choose not to check
987
for uniqueness of the resulting key within the versioned file, so
988
this should only be done when the result is expected to be unique
990
:param check_content: If True, the lines supplied are verified to be
991
bytestrings that are correctly formed lines.
992
:return: The text sha1, the number of bytes in the text, and an opaque
993
representation of the inserted version which can be provided
994
back to future _add_text calls in the parent_texts dictionary.
996
# The default implementation just thunks over to .add_lines(),
997
# inefficient, but it works.
998
return self.add_lines(key, parents, osutils.split_lines(text),
999
nostore_sha=nostore_sha,
1000
random_id=random_id,
1003
def add_mpdiffs(self, records):
1004
"""Add mpdiffs to this VersionedFile.
1006
Records should be iterables of version, parents, expected_sha1,
1007
mpdiff. mpdiff should be a MultiParent instance.
1010
mpvf = multiparent.MultiMemoryVersionedFile()
1012
for version, parent_ids, expected_sha1, mpdiff in records:
1013
versions.append(version)
1014
mpvf.add_diff(mpdiff, version, parent_ids)
1015
needed_parents = set()
1016
for version, parent_ids, expected_sha1, mpdiff in records:
1017
needed_parents.update(p for p in parent_ids
1018
if not mpvf.has_version(p))
1019
# It seems likely that adding all the present parents as fulltexts can
1020
# easily exhaust memory.
1021
chunks_to_lines = osutils.chunks_to_lines
1022
for record in self.get_record_stream(needed_parents, 'unordered',
1024
if record.storage_kind == 'absent':
1026
mpvf.add_version(chunks_to_lines(record.get_bytes_as('chunked')),
1028
for (key, parent_keys, expected_sha1, mpdiff), lines in\
1029
zip(records, mpvf.get_line_list(versions)):
1030
if len(parent_keys) == 1:
1031
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
1032
mpvf.get_diff(parent_keys[0]).num_lines()))
1034
left_matching_blocks = None
1035
version_sha1, _, version_text = self.add_lines(key,
1036
parent_keys, lines, vf_parents,
1037
left_matching_blocks=left_matching_blocks)
1038
if version_sha1 != expected_sha1:
1039
raise errors.VersionedFileInvalidChecksum(version)
1040
vf_parents[key] = version_text
1042
def annotate(self, key):
1043
"""Return a list of (version-key, line) tuples for the text of key.
1045
:raise RevisionNotPresent: If the key is not present.
1047
raise NotImplementedError(self.annotate)
1049
def check(self, progress_bar=None):
1050
"""Check this object for integrity.
1052
:param progress_bar: A progress bar to output as the check progresses.
1053
:param keys: Specific keys within the VersionedFiles to check. When
1054
this parameter is not None, check() becomes a generator as per
1055
get_record_stream. The difference to get_record_stream is that
1056
more or deeper checks will be performed.
1057
:return: None, or if keys was supplied a generator as per
1060
raise NotImplementedError(self.check)
1063
def check_not_reserved_id(version_id):
1064
revision.check_not_reserved_id(version_id)
1066
def clear_cache(self):
1067
"""Clear whatever caches this VersionedFile holds.
1069
This is generally called after an operation has been performed, when we
1070
don't expect to be using this versioned file again soon.
1073
def _check_lines_not_unicode(self, lines):
1074
"""Check that lines being added to a versioned file are not unicode."""
1076
if line.__class__ is not str:
1077
raise errors.BzrBadParameterUnicode("lines")
1079
def _check_lines_are_lines(self, lines):
1080
"""Check that the lines really are full lines without inline EOL."""
1082
if '\n' in line[:-1]:
1083
raise errors.BzrBadParameterContainsNewline("lines")
1085
def get_known_graph_ancestry(self, keys):
1086
"""Get a KnownGraph instance with the ancestry of keys."""
1087
# most basic implementation is a loop around get_parent_map
1091
this_parent_map = self.get_parent_map(pending)
1092
parent_map.update(this_parent_map)
1094
map(pending.update, this_parent_map.itervalues())
1095
pending = pending.difference(parent_map)
1096
kg = _mod_graph.KnownGraph(parent_map)
1099
def get_parent_map(self, keys):
1100
"""Get a map of the parents of keys.
1102
:param keys: The keys to look up parents for.
1103
:return: A mapping from keys to parents. Absent keys are absent from
1106
raise NotImplementedError(self.get_parent_map)
1108
def get_record_stream(self, keys, ordering, include_delta_closure):
1109
"""Get a stream of records for keys.
1111
:param keys: The keys to include.
1112
:param ordering: Either 'unordered' or 'topological'. A topologically
1113
sorted stream has compression parents strictly before their
1115
:param include_delta_closure: If True then the closure across any
1116
compression parents will be included (in the opaque data).
1117
:return: An iterator of ContentFactory objects, each of which is only
1118
valid until the iterator is advanced.
1120
raise NotImplementedError(self.get_record_stream)
1122
def get_sha1s(self, keys):
1123
"""Get the sha1's of the texts for the given keys.
1125
:param keys: The names of the keys to lookup
1126
:return: a dict from key to sha1 digest. Keys of texts which are not
1127
present in the store are not present in the returned
1130
raise NotImplementedError(self.get_sha1s)
1132
has_key = index._has_key_from_parent_map
1134
def get_missing_compression_parent_keys(self):
1135
"""Return an iterable of keys of missing compression parents.
1137
Check this after calling insert_record_stream to find out if there are
1138
any missing compression parents. If there are, the records that
1139
depend on them are not able to be inserted safely. The precise
1140
behaviour depends on the concrete VersionedFiles class in use.
1142
Classes that do not support this will raise NotImplementedError.
1144
raise NotImplementedError(self.get_missing_compression_parent_keys)
1146
def insert_record_stream(self, stream):
1147
"""Insert a record stream into this container.
1149
:param stream: A stream of records to insert.
1151
:seealso VersionedFile.get_record_stream:
1153
raise NotImplementedError
1155
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1156
"""Iterate over the lines in the versioned files from keys.
1158
This may return lines from other keys. Each item the returned
1159
iterator yields is a tuple of a line and a text version that that line
1160
is present in (not introduced in).
1162
Ordering of results is in whatever order is most suitable for the
1163
underlying storage format.
1165
If a progress bar is supplied, it may be used to indicate progress.
1166
The caller is responsible for cleaning up progress bars (because this
1170
* Lines are normalised by the underlying store: they will all have \n
1172
* Lines are returned in arbitrary order.
1174
:return: An iterator over (line, key).
1176
raise NotImplementedError(self.iter_lines_added_or_present_in_keys)
1179
"""Return a iterable of the keys for all the contained texts."""
1180
raise NotImplementedError(self.keys)
1182
def make_mpdiffs(self, keys):
1183
"""Create multiparent diffs for specified keys."""
1184
generator = _MPDiffGenerator(self, keys)
1185
return generator.compute_diffs()
1187
def get_annotator(self):
1188
return annotate.Annotator(self)
1190
missing_keys = index._missing_keys_from_parent_map
1192
def _extract_blocks(self, version_id, source, target):
1195
def _transitive_fallbacks(self):
1196
"""Return the whole stack of fallback versionedfiles.
1198
This VersionedFiles may have a list of fallbacks, but it doesn't
1199
necessarily know about the whole stack going down, and it can't know
1200
at open time because they may change after the objects are opened.
1203
for a_vfs in self._immediate_fallback_vfs:
1204
all_fallbacks.append(a_vfs)
1205
all_fallbacks.extend(a_vfs._transitive_fallbacks())
1206
return all_fallbacks
1209
class ThunkedVersionedFiles(VersionedFiles):
1210
"""Storage for many versioned files thunked onto a 'VersionedFile' class.
1212
This object allows a single keyspace for accessing the history graph and
1213
contents of named bytestrings.
1215
Currently no implementation allows the graph of different key prefixes to
1216
intersect, but the API does allow such implementations in the future.
1219
def __init__(self, transport, file_factory, mapper, is_locked):
1220
"""Create a ThunkedVersionedFiles."""
1221
self._transport = transport
1222
self._file_factory = file_factory
1223
self._mapper = mapper
1224
self._is_locked = is_locked
1226
def add_lines(self, key, parents, lines, parent_texts=None,
1227
left_matching_blocks=None, nostore_sha=None, random_id=False,
1228
check_content=True):
1229
"""See VersionedFiles.add_lines()."""
1230
path = self._mapper.map(key)
1231
version_id = key[-1]
1232
parents = [parent[-1] for parent in parents]
1233
vf = self._get_vf(path)
1236
return vf.add_lines_with_ghosts(version_id, parents, lines,
1237
parent_texts=parent_texts,
1238
left_matching_blocks=left_matching_blocks,
1239
nostore_sha=nostore_sha, random_id=random_id,
1240
check_content=check_content)
1241
except NotImplementedError:
1242
return vf.add_lines(version_id, parents, lines,
1243
parent_texts=parent_texts,
1244
left_matching_blocks=left_matching_blocks,
1245
nostore_sha=nostore_sha, random_id=random_id,
1246
check_content=check_content)
1247
except errors.NoSuchFile:
1248
# parent directory may be missing, try again.
1249
self._transport.mkdir(osutils.dirname(path))
1251
return vf.add_lines_with_ghosts(version_id, parents, lines,
1252
parent_texts=parent_texts,
1253
left_matching_blocks=left_matching_blocks,
1254
nostore_sha=nostore_sha, random_id=random_id,
1255
check_content=check_content)
1256
except NotImplementedError:
1257
return vf.add_lines(version_id, parents, lines,
1258
parent_texts=parent_texts,
1259
left_matching_blocks=left_matching_blocks,
1260
nostore_sha=nostore_sha, random_id=random_id,
1261
check_content=check_content)
1263
def annotate(self, key):
1264
"""Return a list of (version-key, line) tuples for the text of key.
1266
:raise RevisionNotPresent: If the key is not present.
1269
path = self._mapper.map(prefix)
1270
vf = self._get_vf(path)
1271
origins = vf.annotate(key[-1])
1273
for origin, line in origins:
1274
result.append((prefix + (origin,), line))
1277
def check(self, progress_bar=None, keys=None):
1278
"""See VersionedFiles.check()."""
1279
# XXX: This is over-enthusiastic but as we only thunk for Weaves today
1280
# this is tolerable. Ideally we'd pass keys down to check() and
1281
# have the older VersiondFile interface updated too.
1282
for prefix, vf in self._iter_all_components():
1284
if keys is not None:
1285
return self.get_record_stream(keys, 'unordered', True)
1287
def get_parent_map(self, keys):
1288
"""Get a map of the parents of keys.
1290
:param keys: The keys to look up parents for.
1291
:return: A mapping from keys to parents. Absent keys are absent from
1294
prefixes = self._partition_keys(keys)
1296
for prefix, suffixes in prefixes.items():
1297
path = self._mapper.map(prefix)
1298
vf = self._get_vf(path)
1299
parent_map = vf.get_parent_map(suffixes)
1300
for key, parents in parent_map.items():
1301
result[prefix + (key,)] = tuple(
1302
prefix + (parent,) for parent in parents)
1305
def _get_vf(self, path):
1306
if not self._is_locked():
1307
raise errors.ObjectNotLocked(self)
1308
return self._file_factory(path, self._transport, create=True,
1309
get_scope=lambda:None)
1311
def _partition_keys(self, keys):
1312
"""Turn keys into a dict of prefix:suffix_list."""
1315
prefix_keys = result.setdefault(key[:-1], [])
1316
prefix_keys.append(key[-1])
1319
def _get_all_prefixes(self):
1320
# Identify all key prefixes.
1321
# XXX: A bit hacky, needs polish.
1322
if type(self._mapper) == ConstantMapper:
1323
paths = [self._mapper.map(())]
1327
for quoted_relpath in self._transport.iter_files_recursive():
1328
path, ext = os.path.splitext(quoted_relpath)
1330
paths = list(relpaths)
1331
prefixes = [self._mapper.unmap(path) for path in paths]
1332
return zip(paths, prefixes)
1334
def get_record_stream(self, keys, ordering, include_delta_closure):
1335
"""See VersionedFiles.get_record_stream()."""
1336
# Ordering will be taken care of by each partitioned store; group keys
1339
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1340
suffixes = [(suffix,) for suffix in suffixes]
1341
for record in vf.get_record_stream(suffixes, ordering,
1342
include_delta_closure):
1343
if record.parents is not None:
1344
record.parents = tuple(
1345
prefix + parent for parent in record.parents)
1346
record.key = prefix + record.key
1349
def _iter_keys_vf(self, keys):
1350
prefixes = self._partition_keys(keys)
1352
for prefix, suffixes in prefixes.items():
1353
path = self._mapper.map(prefix)
1354
vf = self._get_vf(path)
1355
yield prefix, suffixes, vf
1357
def get_sha1s(self, keys):
1358
"""See VersionedFiles.get_sha1s()."""
1360
for prefix,suffixes, vf in self._iter_keys_vf(keys):
1361
vf_sha1s = vf.get_sha1s(suffixes)
1362
for suffix, sha1 in vf_sha1s.iteritems():
1363
sha1s[prefix + (suffix,)] = sha1
1366
def insert_record_stream(self, stream):
1367
"""Insert a record stream into this container.
1369
:param stream: A stream of records to insert.
1371
:seealso VersionedFile.get_record_stream:
1373
for record in stream:
1374
prefix = record.key[:-1]
1375
key = record.key[-1:]
1376
if record.parents is not None:
1377
parents = [parent[-1:] for parent in record.parents]
1380
thunk_record = AdapterFactory(key, parents, record)
1381
path = self._mapper.map(prefix)
1382
# Note that this parses the file many times; we can do better but
1383
# as this only impacts weaves in terms of performance, it is
1385
vf = self._get_vf(path)
1386
vf.insert_record_stream([thunk_record])
1388
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1389
"""Iterate over the lines in the versioned files from keys.
1391
This may return lines from other keys. Each item the returned
1392
iterator yields is a tuple of a line and a text version that that line
1393
is present in (not introduced in).
1395
Ordering of results is in whatever order is most suitable for the
1396
underlying storage format.
1398
If a progress bar is supplied, it may be used to indicate progress.
1399
The caller is responsible for cleaning up progress bars (because this
1403
* Lines are normalised by the underlying store: they will all have \n
1405
* Lines are returned in arbitrary order.
1407
:return: An iterator over (line, key).
1409
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1410
for line, version in vf.iter_lines_added_or_present_in_versions(suffixes):
1411
yield line, prefix + (version,)
1413
def _iter_all_components(self):
1414
for path, prefix in self._get_all_prefixes():
1415
yield prefix, self._get_vf(path)
1418
"""See VersionedFiles.keys()."""
1420
for prefix, vf in self._iter_all_components():
1421
for suffix in vf.versions():
1422
result.add(prefix + (suffix,))
1426
class VersionedFilesWithFallbacks(VersionedFiles):
1428
def without_fallbacks(self):
1429
"""Return a clone of this object without any fallbacks configured."""
1430
raise NotImplementedError(self.without_fallbacks)
1432
def add_fallback_versioned_files(self, a_versioned_files):
1433
"""Add a source of texts for texts not present in this knit.
1435
:param a_versioned_files: A VersionedFiles object.
1437
raise NotImplementedError(self.add_fallback_versioned_files)
1439
def get_known_graph_ancestry(self, keys):
1440
"""Get a KnownGraph instance with the ancestry of keys."""
1441
parent_map, missing_keys = self._index.find_ancestry(keys)
1442
for fallback in self._transitive_fallbacks():
1443
if not missing_keys:
1445
(f_parent_map, f_missing_keys) = fallback._index.find_ancestry(
1447
parent_map.update(f_parent_map)
1448
missing_keys = f_missing_keys
1449
kg = _mod_graph.KnownGraph(parent_map)
1453
class _PlanMergeVersionedFile(VersionedFiles):
1454
"""A VersionedFile for uncommitted and committed texts.
1456
It is intended to allow merges to be planned with working tree texts.
1457
It implements only the small part of the VersionedFiles interface used by
1458
PlanMerge. It falls back to multiple versionedfiles for data not stored in
1459
_PlanMergeVersionedFile itself.
1461
:ivar: fallback_versionedfiles a list of VersionedFiles objects that can be
1462
queried for missing texts.
1465
def __init__(self, file_id):
1466
"""Create a _PlanMergeVersionedFile.
1468
:param file_id: Used with _PlanMerge code which is not yet fully
1469
tuple-keyspace aware.
1471
self._file_id = file_id
1472
# fallback locations
1473
self.fallback_versionedfiles = []
1474
# Parents for locally held keys.
1476
# line data for locally held keys.
1478
# key lookup providers
1479
self._providers = [_mod_graph.DictParentsProvider(self._parents)]
1481
def plan_merge(self, ver_a, ver_b, base=None):
1482
"""See VersionedFile.plan_merge"""
1483
from bzrlib.merge import _PlanMerge
1485
return _PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge()
1486
old_plan = list(_PlanMerge(ver_a, base, self, (self._file_id,)).plan_merge())
1487
new_plan = list(_PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge())
1488
return _PlanMerge._subtract_plans(old_plan, new_plan)
1490
def plan_lca_merge(self, ver_a, ver_b, base=None):
1491
from bzrlib.merge import _PlanLCAMerge
1492
graph = _mod_graph.Graph(self)
1493
new_plan = _PlanLCAMerge(ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
1496
old_plan = _PlanLCAMerge(ver_a, base, self, (self._file_id,), graph).plan_merge()
1497
return _PlanLCAMerge._subtract_plans(list(old_plan), list(new_plan))
1499
def add_lines(self, key, parents, lines):
1500
"""See VersionedFiles.add_lines
1502
Lines are added locally, not to fallback versionedfiles. Also, ghosts
1503
are permitted. Only reserved ids are permitted.
1505
if type(key) is not tuple:
1506
raise TypeError(key)
1507
if not revision.is_reserved_id(key[-1]):
1508
raise ValueError('Only reserved ids may be used')
1510
raise ValueError('Parents may not be None')
1512
raise ValueError('Lines may not be None')
1513
self._parents[key] = tuple(parents)
1514
self._lines[key] = lines
1516
def get_record_stream(self, keys, ordering, include_delta_closure):
1519
if key in self._lines:
1520
lines = self._lines[key]
1521
parents = self._parents[key]
1523
yield ChunkedContentFactory(key, parents, None, lines)
1524
for versionedfile in self.fallback_versionedfiles:
1525
for record in versionedfile.get_record_stream(
1526
pending, 'unordered', True):
1527
if record.storage_kind == 'absent':
1530
pending.remove(record.key)
1534
# report absent entries
1536
yield AbsentContentFactory(key)
1538
def get_parent_map(self, keys):
1539
"""See VersionedFiles.get_parent_map"""
1540
# We create a new provider because a fallback may have been added.
1541
# If we make fallbacks private we can update a stack list and avoid
1542
# object creation thrashing.
1545
if revision.NULL_REVISION in keys:
1546
keys.remove(revision.NULL_REVISION)
1547
result[revision.NULL_REVISION] = ()
1548
self._providers = self._providers[:1] + self.fallback_versionedfiles
1550
_mod_graph.StackedParentsProvider(
1551
self._providers).get_parent_map(keys))
1552
for key, parents in result.iteritems():
1554
result[key] = (revision.NULL_REVISION,)
1558
class PlanWeaveMerge(TextMerge):
1559
"""Weave merge that takes a plan as its input.
1561
This exists so that VersionedFile.plan_merge is implementable.
1562
Most callers will want to use WeaveMerge instead.
1565
def __init__(self, plan, a_marker=TextMerge.A_MARKER,
1566
b_marker=TextMerge.B_MARKER):
1567
TextMerge.__init__(self, a_marker, b_marker)
1568
self.plan = list(plan)
1570
def _merge_struct(self):
1575
def outstanding_struct():
1576
if not lines_a and not lines_b:
1578
elif ch_a and not ch_b:
1581
elif ch_b and not ch_a:
1583
elif lines_a == lines_b:
1586
yield (lines_a, lines_b)
1588
# We previously considered either 'unchanged' or 'killed-both' lines
1589
# to be possible places to resynchronize. However, assuming agreement
1590
# on killed-both lines may be too aggressive. -- mbp 20060324
1591
for state, line in self.plan:
1592
if state == 'unchanged':
1593
# resync and flush queued conflicts changes if any
1594
for struct in outstanding_struct():
1600
if state == 'unchanged':
1603
elif state == 'killed-a':
1605
lines_b.append(line)
1606
elif state == 'killed-b':
1608
lines_a.append(line)
1609
elif state == 'new-a':
1611
lines_a.append(line)
1612
elif state == 'new-b':
1614
lines_b.append(line)
1615
elif state == 'conflicted-a':
1617
lines_a.append(line)
1618
elif state == 'conflicted-b':
1620
lines_b.append(line)
1621
elif state == 'killed-both':
1622
# This counts as a change, even though there is no associated
1626
if state not in ('irrelevant', 'ghost-a', 'ghost-b',
1628
raise AssertionError(state)
1629
for struct in outstanding_struct():
1632
def base_from_plan(self):
1633
"""Construct a BASE file from the plan text."""
1635
for state, line in self.plan:
1636
if state in ('killed-a', 'killed-b', 'killed-both', 'unchanged'):
1637
# If unchanged, then this line is straight from base. If a or b
1638
# or both killed the line, then it *used* to be in base.
1639
base_lines.append(line)
1641
if state not in ('killed-base', 'irrelevant',
1642
'ghost-a', 'ghost-b',
1644
'conflicted-a', 'conflicted-b'):
1645
# killed-base, irrelevant means it doesn't apply
1646
# ghost-a/ghost-b are harder to say for sure, but they
1647
# aren't in the 'inc_c' which means they aren't in the
1648
# shared base of a & b. So we don't include them. And
1649
# obviously if the line is newly inserted, it isn't in base
1651
# If 'conflicted-a' or b, then it is new vs one base, but
1652
# old versus another base. However, if we make it present
1653
# in the base, it will be deleted from the target, and it
1654
# seems better to get a line doubled in the merge result,
1655
# rather than have it deleted entirely.
1656
# Example, each node is the 'text' at that point:
1664
# There was a criss-cross conflict merge. Both sides
1665
# include the other, but put themselves first.
1666
# Weave marks this as a 'clean' merge, picking OTHER over
1667
# THIS. (Though the details depend on order inserted into
1669
# LCA generates a plan:
1670
# [('unchanged', M),
1671
# ('conflicted-b', b),
1673
# ('conflicted-a', b),
1675
# If you mark 'conflicted-*' as part of BASE, then a 3-way
1676
# merge tool will cleanly generate "MaN" (as BASE vs THIS
1677
# removes one 'b', and BASE vs OTHER removes the other)
1678
# If you include neither, 3-way creates a clean "MbabN" as
1679
# THIS adds one 'b', and OTHER does too.
1680
# It seems that having the line 2 times is better than
1681
# having it omitted. (Easier to manually delete than notice
1682
# it needs to be added.)
1683
raise AssertionError('Unknown state: %s' % (state,))
1687
class WeaveMerge(PlanWeaveMerge):
1688
"""Weave merge that takes a VersionedFile and two versions as its input."""
1690
def __init__(self, versionedfile, ver_a, ver_b,
1691
a_marker=PlanWeaveMerge.A_MARKER, b_marker=PlanWeaveMerge.B_MARKER):
1692
plan = versionedfile.plan_merge(ver_a, ver_b)
1693
PlanWeaveMerge.__init__(self, plan, a_marker, b_marker)
1696
class VirtualVersionedFiles(VersionedFiles):
1697
"""Dummy implementation for VersionedFiles that uses other functions for
1698
obtaining fulltexts and parent maps.
1700
This is always on the bottom of the stack and uses string keys
1701
(rather than tuples) internally.
1704
def __init__(self, get_parent_map, get_lines):
1705
"""Create a VirtualVersionedFiles.
1707
:param get_parent_map: Same signature as Repository.get_parent_map.
1708
:param get_lines: Should return lines for specified key or None if
1711
super(VirtualVersionedFiles, self).__init__()
1712
self._get_parent_map = get_parent_map
1713
self._get_lines = get_lines
1715
def check(self, progressbar=None):
1716
"""See VersionedFiles.check.
1718
:note: Always returns True for VirtualVersionedFiles.
1722
def add_mpdiffs(self, records):
1723
"""See VersionedFiles.mpdiffs.
1725
:note: Not implemented for VirtualVersionedFiles.
1727
raise NotImplementedError(self.add_mpdiffs)
1729
def get_parent_map(self, keys):
1730
"""See VersionedFiles.get_parent_map."""
1731
return dict([((k,), tuple([(p,) for p in v]))
1732
for k,v in self._get_parent_map([k for (k,) in keys]).iteritems()])
1734
def get_sha1s(self, keys):
1735
"""See VersionedFiles.get_sha1s."""
1738
lines = self._get_lines(k)
1739
if lines is not None:
1740
if not isinstance(lines, list):
1741
raise AssertionError
1742
ret[(k,)] = osutils.sha_strings(lines)
1745
def get_record_stream(self, keys, ordering, include_delta_closure):
1746
"""See VersionedFiles.get_record_stream."""
1747
for (k,) in list(keys):
1748
lines = self._get_lines(k)
1749
if lines is not None:
1750
if not isinstance(lines, list):
1751
raise AssertionError
1752
yield ChunkedContentFactory((k,), None,
1753
sha1=osutils.sha_strings(lines),
1756
yield AbsentContentFactory((k,))
1758
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1759
"""See VersionedFile.iter_lines_added_or_present_in_versions()."""
1760
for i, (key,) in enumerate(keys):
1762
pb.update("Finding changed lines", i, len(keys))
1763
for l in self._get_lines(key):
1767
class NoDupeAddLinesDecorator(object):
1768
"""Decorator for a VersionedFiles that skips doing an add_lines if the key
1772
def __init__(self, store):
1775
def add_lines(self, key, parents, lines, parent_texts=None,
1776
left_matching_blocks=None, nostore_sha=None, random_id=False,
1777
check_content=True):
1778
"""See VersionedFiles.add_lines.
1780
This implementation may return None as the third element of the return
1781
value when the original store wouldn't.
1784
raise NotImplementedError(
1785
"NoDupeAddLinesDecorator.add_lines does not implement the "
1786
"nostore_sha behaviour.")
1788
sha1 = osutils.sha_strings(lines)
1789
key = ("sha1:" + sha1,)
1792
if key in self._store.get_parent_map([key]):
1793
# This key has already been inserted, so don't do it again.
1795
sha1 = osutils.sha_strings(lines)
1796
return sha1, sum(map(len, lines)), None
1797
return self._store.add_lines(key, parents, lines,
1798
parent_texts=parent_texts,
1799
left_matching_blocks=left_matching_blocks,
1800
nostore_sha=nostore_sha, random_id=random_id,
1801
check_content=check_content)
1803
def __getattr__(self, name):
1804
return getattr(self._store, name)
1807
def network_bytes_to_kind_and_offset(network_bytes):
1808
"""Strip of a record kind from the front of network_bytes.
1810
:param network_bytes: The bytes of a record.
1811
:return: A tuple (storage_kind, offset_of_remaining_bytes)
1813
line_end = network_bytes.find('\n')
1814
storage_kind = network_bytes[:line_end]
1815
return storage_kind, line_end + 1
1818
class NetworkRecordStream(object):
1819
"""A record_stream which reconstitures a serialised stream."""
1821
def __init__(self, bytes_iterator):
1822
"""Create a NetworkRecordStream.
1824
:param bytes_iterator: An iterator of bytes. Each item in this
1825
iterator should have been obtained from a record_streams'
1826
record.get_bytes_as(record.storage_kind) call.
1828
self._bytes_iterator = bytes_iterator
1829
self._kind_factory = {
1830
'fulltext': fulltext_network_to_record,
1831
'groupcompress-block': groupcompress.network_block_to_records,
1832
'knit-ft-gz': knit.knit_network_to_record,
1833
'knit-delta-gz': knit.knit_network_to_record,
1834
'knit-annotated-ft-gz': knit.knit_network_to_record,
1835
'knit-annotated-delta-gz': knit.knit_network_to_record,
1836
'knit-delta-closure': knit.knit_delta_closure_to_records,
1842
:return: An iterator as per VersionedFiles.get_record_stream().
1844
for bytes in self._bytes_iterator:
1845
storage_kind, line_end = network_bytes_to_kind_and_offset(bytes)
1846
for record in self._kind_factory[storage_kind](
1847
storage_kind, bytes, line_end):
1851
def fulltext_network_to_record(kind, bytes, line_end):
1852
"""Convert a network fulltext record to record."""
1853
meta_len, = struct.unpack('!L', bytes[line_end:line_end+4])
1854
record_meta = bytes[line_end+4:line_end+4+meta_len]
1855
key, parents = bencode.bdecode_as_tuple(record_meta)
1856
if parents == 'nil':
1858
fulltext = bytes[line_end+4+meta_len:]
1859
return [FulltextContentFactory(key, parents, None, fulltext)]
1862
def _length_prefix(bytes):
1863
return struct.pack('!L', len(bytes))
1866
def record_to_fulltext_bytes(record):
1867
if record.parents is None:
1870
parents = record.parents
1871
record_meta = bencode.bencode((record.key, parents))
1872
record_content = record.get_bytes_as('fulltext')
1873
return "fulltext\n%s%s%s" % (
1874
_length_prefix(record_meta), record_meta, record_content)
1877
def sort_groupcompress(parent_map):
1878
"""Sort and group the keys in parent_map into groupcompress order.
1880
groupcompress is defined (currently) as reverse-topological order, grouped
1883
:return: A sorted-list of keys
1885
# gc-optimal ordering is approximately reverse topological,
1886
# properly grouped by file-id.
1888
for item in parent_map.iteritems():
1890
if isinstance(key, str) or len(key) == 1:
1895
per_prefix_map[prefix].append(item)
1897
per_prefix_map[prefix] = [item]
1900
for prefix in sorted(per_prefix_map):
1901
present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
1905
class _KeyRefs(object):
1907
def __init__(self, track_new_keys=False):
1908
# dict mapping 'key' to 'set of keys referring to that key'
1911
# set remembering all new keys
1912
self.new_keys = set()
1914
self.new_keys = None
1920
self.new_keys.clear()
1922
def add_references(self, key, refs):
1923
# Record the new references
1924
for referenced in refs:
1926
needed_by = self.refs[referenced]
1928
needed_by = self.refs[referenced] = set()
1930
# Discard references satisfied by the new key
1933
def get_new_keys(self):
1934
return self.new_keys
1936
def get_unsatisfied_refs(self):
1937
return self.refs.iterkeys()
1939
def _satisfy_refs_for_key(self, key):
1943
# No keys depended on this key. That's ok.
1946
def add_key(self, key):
1947
# satisfy refs for key, and remember that we've seen this key.
1948
self._satisfy_refs_for_key(key)
1949
if self.new_keys is not None:
1950
self.new_keys.add(key)
1952
def satisfy_refs_for_keys(self, keys):
1954
self._satisfy_refs_for_key(key)
1956
def get_referrers(self):
1958
for referrers in self.refs.itervalues():
1959
result.update(referrers)
added
removed
bzrlib/versionedfile.py
