512
549
unchanged Alive in both a and b (possibly created in both)
513
550
new-a Created in a
514
551
new-b Created in b
515
ghost-a Killed in a, unborn in b
552
ghost-a Killed in a, unborn in b
516
553
ghost-b Killed in b, unborn in a
517
554
irrelevant Not in either revision
519
556
raise NotImplementedError(VersionedFile.plan_merge)
521
558
def weave_merge(self, plan, a_marker=TextMerge.A_MARKER,
522
559
b_marker=TextMerge.B_MARKER):
523
560
return PlanWeaveMerge(plan, a_marker, b_marker).merge_lines()[0]
526
class _PlanMergeVersionedFile(object):
563
class RecordingVersionedFilesDecorator(object):
564
"""A minimal versioned files that records calls made on it.
566
Only enough methods have been added to support tests using it to date.
568
:ivar calls: A list of the calls made; can be reset at any time by
572
def __init__(self, backing_vf):
573
"""Create a RecordingVersionedFilesDecorator decorating backing_vf.
575
:param backing_vf: The versioned file to answer all methods.
577
self._backing_vf = backing_vf
580
def add_lines(self, key, parents, lines, parent_texts=None,
581
left_matching_blocks=None, nostore_sha=None, random_id=False,
583
self.calls.append(("add_lines", key, parents, lines, parent_texts,
584
left_matching_blocks, nostore_sha, random_id, check_content))
585
return self._backing_vf.add_lines(key, parents, lines, parent_texts,
586
left_matching_blocks, nostore_sha, random_id, check_content)
589
self._backing_vf.check()
591
def get_parent_map(self, keys):
592
self.calls.append(("get_parent_map", copy(keys)))
593
return self._backing_vf.get_parent_map(keys)
595
def get_record_stream(self, keys, sort_order, include_delta_closure):
596
self.calls.append(("get_record_stream", list(keys), sort_order,
597
include_delta_closure))
598
return self._backing_vf.get_record_stream(keys, sort_order,
599
include_delta_closure)
601
def get_sha1s(self, keys):
602
self.calls.append(("get_sha1s", copy(keys)))
603
return self._backing_vf.get_sha1s(keys)
605
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
606
self.calls.append(("iter_lines_added_or_present_in_keys", copy(keys)))
607
return self._backing_vf.iter_lines_added_or_present_in_keys(keys, pb=pb)
610
self.calls.append(("keys",))
611
return self._backing_vf.keys()
614
class OrderingVersionedFilesDecorator(RecordingVersionedFilesDecorator):
615
"""A VF that records calls, and returns keys in specific order.
617
:ivar calls: A list of the calls made; can be reset at any time by
621
def __init__(self, backing_vf, key_priority):
622
"""Create a RecordingVersionedFilesDecorator decorating backing_vf.
624
:param backing_vf: The versioned file to answer all methods.
625
:param key_priority: A dictionary defining what order keys should be
626
returned from an 'unordered' get_record_stream request.
627
Keys with lower priority are returned first, keys not present in
628
the map get an implicit priority of 0, and are returned in
629
lexicographical order.
631
RecordingVersionedFilesDecorator.__init__(self, backing_vf)
632
self._key_priority = key_priority
634
def get_record_stream(self, keys, sort_order, include_delta_closure):
635
self.calls.append(("get_record_stream", list(keys), sort_order,
636
include_delta_closure))
637
if sort_order == 'unordered':
639
return (self._key_priority.get(key, 0), key)
640
# Use a defined order by asking for the keys one-by-one from the
642
for key in sorted(keys, key=sort_key):
643
for record in self._backing_vf.get_record_stream([key],
644
'unordered', include_delta_closure):
647
for record in self._backing_vf.get_record_stream(keys, sort_order,
648
include_delta_closure):
652
class KeyMapper(object):
653
"""KeyMappers map between keys and underlying partitioned storage."""
656
"""Map key to an underlying storage identifier.
658
:param key: A key tuple e.g. ('file-id', 'revision-id').
659
:return: An underlying storage identifier, specific to the partitioning
662
raise NotImplementedError(self.map)
664
def unmap(self, partition_id):
665
"""Map a partitioned storage id back to a key prefix.
667
:param partition_id: The underlying partition id.
668
:return: As much of a key (or prefix) as is derivable from the partition
671
raise NotImplementedError(self.unmap)
674
class ConstantMapper(KeyMapper):
675
"""A key mapper that maps to a constant result."""
677
def __init__(self, result):
678
"""Create a ConstantMapper which will return result for all maps."""
679
self._result = result
682
"""See KeyMapper.map()."""
686
class URLEscapeMapper(KeyMapper):
687
"""Base class for use with transport backed storage.
689
This provides a map and unmap wrapper that respectively url escape and
690
unescape their outputs and inputs.
694
"""See KeyMapper.map()."""
695
return urllib.quote(self._map(key))
697
def unmap(self, partition_id):
698
"""See KeyMapper.unmap()."""
699
return self._unmap(urllib.unquote(partition_id))
702
class PrefixMapper(URLEscapeMapper):
703
"""A key mapper that extracts the first component of a key.
705
This mapper is for use with a transport based backend.
709
"""See KeyMapper.map()."""
712
def _unmap(self, partition_id):
713
"""See KeyMapper.unmap()."""
714
return (partition_id,)
717
class HashPrefixMapper(URLEscapeMapper):
718
"""A key mapper that combines the first component of a key with a hash.
720
This mapper is for use with a transport based backend.
724
"""See KeyMapper.map()."""
725
prefix = self._escape(key[0])
726
return "%02x/%s" % (adler32(prefix) & 0xff, prefix)
728
def _escape(self, prefix):
729
"""No escaping needed here."""
732
def _unmap(self, partition_id):
733
"""See KeyMapper.unmap()."""
734
return (self._unescape(osutils.basename(partition_id)),)
736
def _unescape(self, basename):
737
"""No unescaping needed for HashPrefixMapper."""
741
class HashEscapedPrefixMapper(HashPrefixMapper):
742
"""Combines the escaped first component of a key with a hash.
744
This mapper is for use with a transport based backend.
747
_safe = "abcdefghijklmnopqrstuvwxyz0123456789-_@,."
749
def _escape(self, prefix):
750
"""Turn a key element into a filesystem safe string.
752
This is similar to a plain urllib.quote, except
753
it uses specific safe characters, so that it doesn't
754
have to translate a lot of valid file ids.
756
# @ does not get escaped. This is because it is a valid
757
# filesystem character we use all the time, and it looks
758
# a lot better than seeing %40 all the time.
759
r = [((c in self._safe) and c or ('%%%02x' % ord(c)))
763
def _unescape(self, basename):
764
"""Escaped names are easily unescaped by urlutils."""
765
return urllib.unquote(basename)
768
def make_versioned_files_factory(versioned_file_factory, mapper):
769
"""Create a ThunkedVersionedFiles factory.
771
This will create a callable which when called creates a
772
ThunkedVersionedFiles on a transport, using mapper to access individual
773
versioned files, and versioned_file_factory to create each individual file.
775
def factory(transport):
776
return ThunkedVersionedFiles(transport, versioned_file_factory, mapper,
781
class VersionedFiles(object):
782
"""Storage for many versioned files.
784
This object allows a single keyspace for accessing the history graph and
785
contents of named bytestrings.
787
Currently no implementation allows the graph of different key prefixes to
788
intersect, but the API does allow such implementations in the future.
790
The keyspace is expressed via simple tuples. Any instance of VersionedFiles
791
may have a different length key-size, but that size will be constant for
792
all texts added to or retrieved from it. For instance, bzrlib uses
793
instances with a key-size of 2 for storing user files in a repository, with
794
the first element the fileid, and the second the version of that file.
796
The use of tuples allows a single code base to support several different
797
uses with only the mapping logic changing from instance to instance.
800
def add_lines(self, key, parents, lines, parent_texts=None,
801
left_matching_blocks=None, nostore_sha=None, random_id=False,
803
"""Add a text to the store.
805
:param key: The key tuple of the text to add. If the last element is
806
None, a CHK string will be generated during the addition.
807
:param parents: The parents key tuples of the text to add.
808
:param lines: A list of lines. Each line must be a bytestring. And all
809
of them except the last must be terminated with \n and contain no
810
other \n's. The last line may either contain no \n's or a single
811
terminating \n. If the lines list does meet this constraint the add
812
routine may error or may succeed - but you will be unable to read
813
the data back accurately. (Checking the lines have been split
814
correctly is expensive and extremely unlikely to catch bugs so it
815
is not done at runtime unless check_content is True.)
816
:param parent_texts: An optional dictionary containing the opaque
817
representations of some or all of the parents of version_id to
818
allow delta optimisations. VERY IMPORTANT: the texts must be those
819
returned by add_lines or data corruption can be caused.
820
:param left_matching_blocks: a hint about which areas are common
821
between the text and its left-hand-parent. The format is
822
the SequenceMatcher.get_matching_blocks format.
823
:param nostore_sha: Raise ExistingContent and do not add the lines to
824
the versioned file if the digest of the lines matches this.
825
:param random_id: If True a random id has been selected rather than
826
an id determined by some deterministic process such as a converter
827
from a foreign VCS. When True the backend may choose not to check
828
for uniqueness of the resulting key within the versioned file, so
829
this should only be done when the result is expected to be unique
831
:param check_content: If True, the lines supplied are verified to be
832
bytestrings that are correctly formed lines.
833
:return: The text sha1, the number of bytes in the text, and an opaque
834
representation of the inserted version which can be provided
835
back to future add_lines calls in the parent_texts dictionary.
837
raise NotImplementedError(self.add_lines)
839
def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
840
"""Add a text to the store.
842
This is a private function for use by CommitBuilder.
844
:param key: The key tuple of the text to add. If the last element is
845
None, a CHK string will be generated during the addition.
846
:param parents: The parents key tuples of the text to add.
847
:param text: A string containing the text to be committed.
848
:param nostore_sha: Raise ExistingContent and do not add the lines to
849
the versioned file if the digest of the lines matches this.
850
:param random_id: If True a random id has been selected rather than
851
an id determined by some deterministic process such as a converter
852
from a foreign VCS. When True the backend may choose not to check
853
for uniqueness of the resulting key within the versioned file, so
854
this should only be done when the result is expected to be unique
856
:param check_content: If True, the lines supplied are verified to be
857
bytestrings that are correctly formed lines.
858
:return: The text sha1, the number of bytes in the text, and an opaque
859
representation of the inserted version which can be provided
860
back to future _add_text calls in the parent_texts dictionary.
862
# The default implementation just thunks over to .add_lines(),
863
# inefficient, but it works.
864
return self.add_lines(key, parents, osutils.split_lines(text),
865
nostore_sha=nostore_sha,
869
def add_mpdiffs(self, records):
870
"""Add mpdiffs to this VersionedFile.
872
Records should be iterables of version, parents, expected_sha1,
873
mpdiff. mpdiff should be a MultiParent instance.
876
mpvf = multiparent.MultiMemoryVersionedFile()
878
for version, parent_ids, expected_sha1, mpdiff in records:
879
versions.append(version)
880
mpvf.add_diff(mpdiff, version, parent_ids)
881
needed_parents = set()
882
for version, parent_ids, expected_sha1, mpdiff in records:
883
needed_parents.update(p for p in parent_ids
884
if not mpvf.has_version(p))
885
# It seems likely that adding all the present parents as fulltexts can
886
# easily exhaust memory.
887
chunks_to_lines = osutils.chunks_to_lines
888
for record in self.get_record_stream(needed_parents, 'unordered',
890
if record.storage_kind == 'absent':
892
mpvf.add_version(chunks_to_lines(record.get_bytes_as('chunked')),
894
for (key, parent_keys, expected_sha1, mpdiff), lines in\
895
zip(records, mpvf.get_line_list(versions)):
896
if len(parent_keys) == 1:
897
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
898
mpvf.get_diff(parent_keys[0]).num_lines()))
900
left_matching_blocks = None
901
version_sha1, _, version_text = self.add_lines(key,
902
parent_keys, lines, vf_parents,
903
left_matching_blocks=left_matching_blocks)
904
if version_sha1 != expected_sha1:
905
raise errors.VersionedFileInvalidChecksum(version)
906
vf_parents[key] = version_text
908
def annotate(self, key):
909
"""Return a list of (version-key, line) tuples for the text of key.
911
:raise RevisionNotPresent: If the key is not present.
913
raise NotImplementedError(self.annotate)
915
def check(self, progress_bar=None):
916
"""Check this object for integrity.
918
:param progress_bar: A progress bar to output as the check progresses.
919
:param keys: Specific keys within the VersionedFiles to check. When
920
this parameter is not None, check() becomes a generator as per
921
get_record_stream. The difference to get_record_stream is that
922
more or deeper checks will be performed.
923
:return: None, or if keys was supplied a generator as per
926
raise NotImplementedError(self.check)
929
def check_not_reserved_id(version_id):
930
revision.check_not_reserved_id(version_id)
932
def clear_cache(self):
933
"""Clear whatever caches this VersionedFile holds.
935
This is generally called after an operation has been performed, when we
936
don't expect to be using this versioned file again soon.
939
def _check_lines_not_unicode(self, lines):
940
"""Check that lines being added to a versioned file are not unicode."""
942
if line.__class__ is not str:
943
raise errors.BzrBadParameterUnicode("lines")
945
def _check_lines_are_lines(self, lines):
946
"""Check that the lines really are full lines without inline EOL."""
948
if '\n' in line[:-1]:
949
raise errors.BzrBadParameterContainsNewline("lines")
951
def get_known_graph_ancestry(self, keys):
952
"""Get a KnownGraph instance with the ancestry of keys."""
953
# most basic implementation is a loop around get_parent_map
957
this_parent_map = self.get_parent_map(pending)
958
parent_map.update(this_parent_map)
960
map(pending.update, this_parent_map.itervalues())
961
pending = pending.difference(parent_map)
962
kg = _mod_graph.KnownGraph(parent_map)
965
def get_parent_map(self, keys):
966
"""Get a map of the parents of keys.
968
:param keys: The keys to look up parents for.
969
:return: A mapping from keys to parents. Absent keys are absent from
972
raise NotImplementedError(self.get_parent_map)
974
def get_record_stream(self, keys, ordering, include_delta_closure):
975
"""Get a stream of records for keys.
977
:param keys: The keys to include.
978
:param ordering: Either 'unordered' or 'topological'. A topologically
979
sorted stream has compression parents strictly before their
981
:param include_delta_closure: If True then the closure across any
982
compression parents will be included (in the opaque data).
983
:return: An iterator of ContentFactory objects, each of which is only
984
valid until the iterator is advanced.
986
raise NotImplementedError(self.get_record_stream)
988
def get_sha1s(self, keys):
989
"""Get the sha1's of the texts for the given keys.
991
:param keys: The names of the keys to lookup
992
:return: a dict from key to sha1 digest. Keys of texts which are not
993
present in the store are not present in the returned
996
raise NotImplementedError(self.get_sha1s)
998
has_key = index._has_key_from_parent_map
1000
def get_missing_compression_parent_keys(self):
1001
"""Return an iterable of keys of missing compression parents.
1003
Check this after calling insert_record_stream to find out if there are
1004
any missing compression parents. If there are, the records that
1005
depend on them are not able to be inserted safely. The precise
1006
behaviour depends on the concrete VersionedFiles class in use.
1008
Classes that do not support this will raise NotImplementedError.
1010
raise NotImplementedError(self.get_missing_compression_parent_keys)
1012
def insert_record_stream(self, stream):
1013
"""Insert a record stream into this container.
1015
:param stream: A stream of records to insert.
1017
:seealso VersionedFile.get_record_stream:
1019
raise NotImplementedError
1021
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1022
"""Iterate over the lines in the versioned files from keys.
1024
This may return lines from other keys. Each item the returned
1025
iterator yields is a tuple of a line and a text version that that line
1026
is present in (not introduced in).
1028
Ordering of results is in whatever order is most suitable for the
1029
underlying storage format.
1031
If a progress bar is supplied, it may be used to indicate progress.
1032
The caller is responsible for cleaning up progress bars (because this
1036
* Lines are normalised by the underlying store: they will all have \n
1038
* Lines are returned in arbitrary order.
1040
:return: An iterator over (line, key).
1042
raise NotImplementedError(self.iter_lines_added_or_present_in_keys)
1045
"""Return a iterable of the keys for all the contained texts."""
1046
raise NotImplementedError(self.keys)
1048
def make_mpdiffs(self, keys):
1049
"""Create multiparent diffs for specified keys."""
1050
keys_order = tuple(keys)
1051
keys = frozenset(keys)
1052
knit_keys = set(keys)
1053
parent_map = self.get_parent_map(keys)
1054
for parent_keys in parent_map.itervalues():
1056
knit_keys.update(parent_keys)
1057
missing_keys = keys - set(parent_map)
1059
raise errors.RevisionNotPresent(list(missing_keys)[0], self)
1060
# We need to filter out ghosts, because we can't diff against them.
1061
maybe_ghosts = knit_keys - keys
1062
ghosts = maybe_ghosts - set(self.get_parent_map(maybe_ghosts))
1063
knit_keys.difference_update(ghosts)
1065
chunks_to_lines = osutils.chunks_to_lines
1066
for record in self.get_record_stream(knit_keys, 'topological', True):
1067
lines[record.key] = chunks_to_lines(record.get_bytes_as('chunked'))
1068
# line_block_dict = {}
1069
# for parent, blocks in record.extract_line_blocks():
1070
# line_blocks[parent] = blocks
1071
# line_blocks[record.key] = line_block_dict
1073
for key in keys_order:
1075
parents = parent_map[key] or []
1076
# Note that filtering knit_keys can lead to a parent difference
1077
# between the creation and the application of the mpdiff.
1078
parent_lines = [lines[p] for p in parents if p in knit_keys]
1079
if len(parent_lines) > 0:
1080
left_parent_blocks = self._extract_blocks(key, parent_lines[0],
1083
left_parent_blocks = None
1084
diffs.append(multiparent.MultiParent.from_lines(target,
1085
parent_lines, left_parent_blocks))
1088
missing_keys = index._missing_keys_from_parent_map
1090
def _extract_blocks(self, version_id, source, target):
1094
class ThunkedVersionedFiles(VersionedFiles):
1095
"""Storage for many versioned files thunked onto a 'VersionedFile' class.
1097
This object allows a single keyspace for accessing the history graph and
1098
contents of named bytestrings.
1100
Currently no implementation allows the graph of different key prefixes to
1101
intersect, but the API does allow such implementations in the future.
1104
def __init__(self, transport, file_factory, mapper, is_locked):
1105
"""Create a ThunkedVersionedFiles."""
1106
self._transport = transport
1107
self._file_factory = file_factory
1108
self._mapper = mapper
1109
self._is_locked = is_locked
1111
def add_lines(self, key, parents, lines, parent_texts=None,
1112
left_matching_blocks=None, nostore_sha=None, random_id=False,
1113
check_content=True):
1114
"""See VersionedFiles.add_lines()."""
1115
path = self._mapper.map(key)
1116
version_id = key[-1]
1117
parents = [parent[-1] for parent in parents]
1118
vf = self._get_vf(path)
1121
return vf.add_lines_with_ghosts(version_id, parents, lines,
1122
parent_texts=parent_texts,
1123
left_matching_blocks=left_matching_blocks,
1124
nostore_sha=nostore_sha, random_id=random_id,
1125
check_content=check_content)
1126
except NotImplementedError:
1127
return vf.add_lines(version_id, parents, lines,
1128
parent_texts=parent_texts,
1129
left_matching_blocks=left_matching_blocks,
1130
nostore_sha=nostore_sha, random_id=random_id,
1131
check_content=check_content)
1132
except errors.NoSuchFile:
1133
# parent directory may be missing, try again.
1134
self._transport.mkdir(osutils.dirname(path))
1136
return vf.add_lines_with_ghosts(version_id, parents, lines,
1137
parent_texts=parent_texts,
1138
left_matching_blocks=left_matching_blocks,
1139
nostore_sha=nostore_sha, random_id=random_id,
1140
check_content=check_content)
1141
except NotImplementedError:
1142
return vf.add_lines(version_id, parents, lines,
1143
parent_texts=parent_texts,
1144
left_matching_blocks=left_matching_blocks,
1145
nostore_sha=nostore_sha, random_id=random_id,
1146
check_content=check_content)
1148
def annotate(self, key):
1149
"""Return a list of (version-key, line) tuples for the text of key.
1151
:raise RevisionNotPresent: If the key is not present.
1154
path = self._mapper.map(prefix)
1155
vf = self._get_vf(path)
1156
origins = vf.annotate(key[-1])
1158
for origin, line in origins:
1159
result.append((prefix + (origin,), line))
1162
def get_annotator(self):
1163
return annotate.Annotator(self)
1165
def check(self, progress_bar=None, keys=None):
1166
"""See VersionedFiles.check()."""
1167
# XXX: This is over-enthusiastic but as we only thunk for Weaves today
1168
# this is tolerable. Ideally we'd pass keys down to check() and
1169
# have the older VersiondFile interface updated too.
1170
for prefix, vf in self._iter_all_components():
1172
if keys is not None:
1173
return self.get_record_stream(keys, 'unordered', True)
1175
def get_parent_map(self, keys):
1176
"""Get a map of the parents of keys.
1178
:param keys: The keys to look up parents for.
1179
:return: A mapping from keys to parents. Absent keys are absent from
1182
prefixes = self._partition_keys(keys)
1184
for prefix, suffixes in prefixes.items():
1185
path = self._mapper.map(prefix)
1186
vf = self._get_vf(path)
1187
parent_map = vf.get_parent_map(suffixes)
1188
for key, parents in parent_map.items():
1189
result[prefix + (key,)] = tuple(
1190
prefix + (parent,) for parent in parents)
1193
def _get_vf(self, path):
1194
if not self._is_locked():
1195
raise errors.ObjectNotLocked(self)
1196
return self._file_factory(path, self._transport, create=True,
1197
get_scope=lambda:None)
1199
def _partition_keys(self, keys):
1200
"""Turn keys into a dict of prefix:suffix_list."""
1203
prefix_keys = result.setdefault(key[:-1], [])
1204
prefix_keys.append(key[-1])
1207
def _get_all_prefixes(self):
1208
# Identify all key prefixes.
1209
# XXX: A bit hacky, needs polish.
1210
if type(self._mapper) == ConstantMapper:
1211
paths = [self._mapper.map(())]
1215
for quoted_relpath in self._transport.iter_files_recursive():
1216
path, ext = os.path.splitext(quoted_relpath)
1218
paths = list(relpaths)
1219
prefixes = [self._mapper.unmap(path) for path in paths]
1220
return zip(paths, prefixes)
1222
def get_record_stream(self, keys, ordering, include_delta_closure):
1223
"""See VersionedFiles.get_record_stream()."""
1224
# Ordering will be taken care of by each partitioned store; group keys
1227
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1228
suffixes = [(suffix,) for suffix in suffixes]
1229
for record in vf.get_record_stream(suffixes, ordering,
1230
include_delta_closure):
1231
if record.parents is not None:
1232
record.parents = tuple(
1233
prefix + parent for parent in record.parents)
1234
record.key = prefix + record.key
1237
def _iter_keys_vf(self, keys):
1238
prefixes = self._partition_keys(keys)
1240
for prefix, suffixes in prefixes.items():
1241
path = self._mapper.map(prefix)
1242
vf = self._get_vf(path)
1243
yield prefix, suffixes, vf
1245
def get_sha1s(self, keys):
1246
"""See VersionedFiles.get_sha1s()."""
1248
for prefix,suffixes, vf in self._iter_keys_vf(keys):
1249
vf_sha1s = vf.get_sha1s(suffixes)
1250
for suffix, sha1 in vf_sha1s.iteritems():
1251
sha1s[prefix + (suffix,)] = sha1
1254
def insert_record_stream(self, stream):
1255
"""Insert a record stream into this container.
1257
:param stream: A stream of records to insert.
1259
:seealso VersionedFile.get_record_stream:
1261
for record in stream:
1262
prefix = record.key[:-1]
1263
key = record.key[-1:]
1264
if record.parents is not None:
1265
parents = [parent[-1:] for parent in record.parents]
1268
thunk_record = AdapterFactory(key, parents, record)
1269
path = self._mapper.map(prefix)
1270
# Note that this parses the file many times; we can do better but
1271
# as this only impacts weaves in terms of performance, it is
1273
vf = self._get_vf(path)
1274
vf.insert_record_stream([thunk_record])
1276
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1277
"""Iterate over the lines in the versioned files from keys.
1279
This may return lines from other keys. Each item the returned
1280
iterator yields is a tuple of a line and a text version that that line
1281
is present in (not introduced in).
1283
Ordering of results is in whatever order is most suitable for the
1284
underlying storage format.
1286
If a progress bar is supplied, it may be used to indicate progress.
1287
The caller is responsible for cleaning up progress bars (because this
1291
* Lines are normalised by the underlying store: they will all have \n
1293
* Lines are returned in arbitrary order.
1295
:return: An iterator over (line, key).
1297
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1298
for line, version in vf.iter_lines_added_or_present_in_versions(suffixes):
1299
yield line, prefix + (version,)
1301
def _iter_all_components(self):
1302
for path, prefix in self._get_all_prefixes():
1303
yield prefix, self._get_vf(path)
1306
"""See VersionedFiles.keys()."""
1308
for prefix, vf in self._iter_all_components():
1309
for suffix in vf.versions():
1310
result.add(prefix + (suffix,))
1314
class _PlanMergeVersionedFile(VersionedFiles):
527
1315
"""A VersionedFile for uncommitted and committed texts.
529
1317
It is intended to allow merges to be planned with working tree texts.
530
It implements only the small part of the VersionedFile interface used by
1318
It implements only the small part of the VersionedFiles interface used by
531
1319
PlanMerge. It falls back to multiple versionedfiles for data not stored in
532
1320
_PlanMergeVersionedFile itself.
1322
:ivar: fallback_versionedfiles a list of VersionedFiles objects that can be
1323
queried for missing texts.
535
def __init__(self, file_id, fallback_versionedfiles=None):
1326
def __init__(self, file_id):
1327
"""Create a _PlanMergeVersionedFile.
538
:param file_id: Used when raising exceptions.
539
:param fallback_versionedfiles: If supplied, the set of fallbacks to
540
use. Otherwise, _PlanMergeVersionedFile.fallback_versionedfiles
541
can be appended to later.
1329
:param file_id: Used with _PlanMerge code which is not yet fully
1330
tuple-keyspace aware.
543
1332
self._file_id = file_id
544
if fallback_versionedfiles is None:
545
self.fallback_versionedfiles = []
547
self.fallback_versionedfiles = fallback_versionedfiles
1333
# fallback locations
1334
self.fallback_versionedfiles = []
1335
# Parents for locally held keys.
548
1336
self._parents = {}
1337
# line data for locally held keys.
549
1338
self._lines = {}
1339
# key lookup providers
1340
self._providers = [DictParentsProvider(self._parents)]
551
1342
def plan_merge(self, ver_a, ver_b, base=None):
552
1343
"""See VersionedFile.plan_merge"""
553
1344
from bzrlib.merge import _PlanMerge
554
1345
if base is None:
555
return _PlanMerge(ver_a, ver_b, self).plan_merge()
556
old_plan = list(_PlanMerge(ver_a, base, self).plan_merge())
557
new_plan = list(_PlanMerge(ver_a, ver_b, self).plan_merge())
1346
return _PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge()
1347
old_plan = list(_PlanMerge(ver_a, base, self, (self._file_id,)).plan_merge())
1348
new_plan = list(_PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge())
558
1349
return _PlanMerge._subtract_plans(old_plan, new_plan)
560
1351
def plan_lca_merge(self, ver_a, ver_b, base=None):
561
1352
from bzrlib.merge import _PlanLCAMerge
562
graph = self._get_graph()
563
new_plan = _PlanLCAMerge(ver_a, ver_b, self, graph).plan_merge()
1354
new_plan = _PlanLCAMerge(ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
564
1355
if base is None:
566
old_plan = _PlanLCAMerge(ver_a, base, self, graph).plan_merge()
1357
old_plan = _PlanLCAMerge(ver_a, base, self, (self._file_id,), graph).plan_merge()
567
1358
return _PlanLCAMerge._subtract_plans(list(old_plan), list(new_plan))
569
def add_lines(self, version_id, parents, lines):
570
"""See VersionedFile.add_lines
1360
def add_lines(self, key, parents, lines):
1361
"""See VersionedFiles.add_lines
572
Lines are added locally, not fallback versionedfiles. Also, ghosts are
573
permitted. Only reserved ids are permitted.
1363
Lines are added locally, not to fallback versionedfiles. Also, ghosts
1364
are permitted. Only reserved ids are permitted.
575
if not revision.is_reserved_id(version_id):
1366
if type(key) is not tuple:
1367
raise TypeError(key)
1368
if not revision.is_reserved_id(key[-1]):
576
1369
raise ValueError('Only reserved ids may be used')
577
1370
if parents is None:
578
1371
raise ValueError('Parents may not be None')
579
1372
if lines is None:
580
1373
raise ValueError('Lines may not be None')
581
self._parents[version_id] = tuple(parents)
582
self._lines[version_id] = lines
1374
self._parents[key] = tuple(parents)
1375
self._lines[key] = lines
584
def get_lines(self, version_id):
585
"""See VersionedFile.get_ancestry"""
586
lines = self._lines.get(version_id)
587
if lines is not None:
1377
def get_record_stream(self, keys, ordering, include_delta_closure):
1380
if key in self._lines:
1381
lines = self._lines[key]
1382
parents = self._parents[key]
1384
yield ChunkedContentFactory(key, parents, None, lines)
589
1385
for versionedfile in self.fallback_versionedfiles:
591
return versionedfile.get_lines(version_id)
592
except errors.RevisionNotPresent:
595
raise errors.RevisionNotPresent(version_id, self._file_id)
597
def get_ancestry(self, version_id, topo_sorted=False):
598
"""See VersionedFile.get_ancestry.
600
Note that this implementation assumes that if a VersionedFile can
601
answer get_ancestry at all, it can give an authoritative answer. In
602
fact, ghosts can invalidate this assumption. But it's good enough
603
99% of the time, and far cheaper/simpler.
605
Also note that the results of this version are never topologically
606
sorted, and are a set.
609
raise ValueError('This implementation does not provide sorting')
610
parents = self._parents.get(version_id)
612
for vf in self.fallback_versionedfiles:
614
return vf.get_ancestry(version_id, topo_sorted=False)
615
except errors.RevisionNotPresent:
1386
for record in versionedfile.get_record_stream(
1387
pending, 'unordered', True):
1388
if record.storage_kind == 'absent':
618
raise errors.RevisionNotPresent(version_id, self._file_id)
619
ancestry = set([version_id])
620
for parent in parents:
621
ancestry.update(self.get_ancestry(parent, topo_sorted=False))
624
def get_parent_map(self, version_ids):
625
"""See VersionedFile.get_parent_map"""
627
pending = set(version_ids)
628
for key in version_ids:
630
result[key] = self._parents[key]
633
pending = pending - set(result.keys())
634
for versionedfile in self.fallback_versionedfiles:
635
parents = versionedfile.get_parent_map(pending)
636
result.update(parents)
637
pending = pending - set(parents.keys())
1391
pending.remove(record.key)
1395
# report absent entries
1397
yield AbsentContentFactory(key)
1399
def get_parent_map(self, keys):
1400
"""See VersionedFiles.get_parent_map"""
1401
# We create a new provider because a fallback may have been added.
1402
# If we make fallbacks private we can update a stack list and avoid
1403
# object creation thrashing.
1406
if revision.NULL_REVISION in keys:
1407
keys.remove(revision.NULL_REVISION)
1408
result[revision.NULL_REVISION] = ()
1409
self._providers = self._providers[:1] + self.fallback_versionedfiles
1411
StackedParentsProvider(self._providers).get_parent_map(keys))
1412
for key, parents in result.iteritems():
1414
result[key] = (revision.NULL_REVISION,)
642
def _get_graph(self):
643
from bzrlib.graph import (
646
_StackedParentsProvider,
648
from bzrlib.repofmt.knitrepo import _KnitParentsProvider
649
parent_providers = [DictParentsProvider(self._parents)]
650
for vf in self.fallback_versionedfiles:
651
parent_providers.append(_KnitParentsProvider(vf))
652
return Graph(_StackedParentsProvider(parent_providers))
655
1418
class PlanWeaveMerge(TextMerge):
656
1419
"""Weave merge that takes a plan as its input.
658
1421
This exists so that VersionedFile.plan_merge is implementable.
659
1422
Most callers will want to use WeaveMerge instead.
715
1478
elif state == 'conflicted-b':
716
1479
ch_b = ch_a = True
717
1480
lines_b.append(line)
1481
elif state == 'killed-both':
1482
# This counts as a change, even though there is no associated
719
assert state in ('irrelevant', 'ghost-a', 'ghost-b',
720
'killed-base', 'killed-both'), state
1486
if state not in ('irrelevant', 'ghost-a', 'ghost-b',
1488
raise AssertionError(state)
721
1489
for struct in outstanding_struct():
1492
def base_from_plan(self):
1493
"""Construct a BASE file from the plan text."""
1495
for state, line in self.plan:
1496
if state in ('killed-a', 'killed-b', 'killed-both', 'unchanged'):
1497
# If unchanged, then this line is straight from base. If a or b
1498
# or both killed the line, then it *used* to be in base.
1499
base_lines.append(line)
1501
if state not in ('killed-base', 'irrelevant',
1502
'ghost-a', 'ghost-b',
1504
'conflicted-a', 'conflicted-b'):
1505
# killed-base, irrelevant means it doesn't apply
1506
# ghost-a/ghost-b are harder to say for sure, but they
1507
# aren't in the 'inc_c' which means they aren't in the
1508
# shared base of a & b. So we don't include them. And
1509
# obviously if the line is newly inserted, it isn't in base
1511
# If 'conflicted-a' or b, then it is new vs one base, but
1512
# old versus another base. However, if we make it present
1513
# in the base, it will be deleted from the target, and it
1514
# seems better to get a line doubled in the merge result,
1515
# rather than have it deleted entirely.
1516
# Example, each node is the 'text' at that point:
1524
# There was a criss-cross conflict merge. Both sides
1525
# include the other, but put themselves first.
1526
# Weave marks this as a 'clean' merge, picking OTHER over
1527
# THIS. (Though the details depend on order inserted into
1529
# LCA generates a plan:
1530
# [('unchanged', M),
1531
# ('conflicted-b', b),
1533
# ('conflicted-a', b),
1535
# If you mark 'conflicted-*' as part of BASE, then a 3-way
1536
# merge tool will cleanly generate "MaN" (as BASE vs THIS
1537
# removes one 'b', and BASE vs OTHER removes the other)
1538
# If you include neither, 3-way creates a clean "MbabN" as
1539
# THIS adds one 'b', and OTHER does too.
1540
# It seems that having the line 2 times is better than
1541
# having it omitted. (Easier to manually delete than notice
1542
# it needs to be added.)
1543
raise AssertionError('Unknown state: %s' % (state,))
725
1547
class WeaveMerge(PlanWeaveMerge):
726
1548
"""Weave merge that takes a VersionedFile and two versions as its input."""
728
def __init__(self, versionedfile, ver_a, ver_b,
1550
def __init__(self, versionedfile, ver_a, ver_b,
729
1551
a_marker=PlanWeaveMerge.A_MARKER, b_marker=PlanWeaveMerge.B_MARKER):
730
1552
plan = versionedfile.plan_merge(ver_a, ver_b)
731
1553
PlanWeaveMerge.__init__(self, plan, a_marker, b_marker)
734
class InterVersionedFile(InterObject):
735
"""This class represents operations taking place between two VersionedFiles.
737
Its instances have methods like join, and contain
738
references to the source and target versionedfiles these operations can be
741
Often we will provide convenience methods on 'versionedfile' which carry out
742
operations with another versionedfile - they will always forward to
743
InterVersionedFile.get(other).method_name(parameters).
747
"""The available optimised InterVersionedFile types."""
749
def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
750
"""Integrate versions from self.source into self.target.
752
If version_ids is None all versions from source should be
753
incorporated into this versioned file.
755
Must raise RevisionNotPresent if any of the specified versions
756
are not present in the other file's history unless ignore_missing is
757
supplied in which case they are silently skipped.
760
version_ids = self._get_source_version_ids(version_ids, ignore_missing)
761
graph = Graph(self.source)
762
search = graph._make_breadth_first_searcher(version_ids)
763
transitive_ids = set()
764
map(transitive_ids.update, list(search))
765
parent_map = self.source.get_parent_map(transitive_ids)
766
order = tsort.topo_sort(parent_map.items())
767
pb = ui.ui_factory.nested_progress_bar()
1556
class VirtualVersionedFiles(VersionedFiles):
1557
"""Dummy implementation for VersionedFiles that uses other functions for
1558
obtaining fulltexts and parent maps.
1560
This is always on the bottom of the stack and uses string keys
1561
(rather than tuples) internally.
1564
def __init__(self, get_parent_map, get_lines):
1565
"""Create a VirtualVersionedFiles.
1567
:param get_parent_map: Same signature as Repository.get_parent_map.
1568
:param get_lines: Should return lines for specified key or None if
1571
super(VirtualVersionedFiles, self).__init__()
1572
self._get_parent_map = get_parent_map
1573
self._get_lines = get_lines
1575
def check(self, progressbar=None):
1576
"""See VersionedFiles.check.
1578
:note: Always returns True for VirtualVersionedFiles.
1582
def add_mpdiffs(self, records):
1583
"""See VersionedFiles.mpdiffs.
1585
:note: Not implemented for VirtualVersionedFiles.
1587
raise NotImplementedError(self.add_mpdiffs)
1589
def get_parent_map(self, keys):
1590
"""See VersionedFiles.get_parent_map."""
1591
return dict([((k,), tuple([(p,) for p in v]))
1592
for k,v in self._get_parent_map([k for (k,) in keys]).iteritems()])
1594
def get_sha1s(self, keys):
1595
"""See VersionedFiles.get_sha1s."""
1598
lines = self._get_lines(k)
1599
if lines is not None:
1600
if not isinstance(lines, list):
1601
raise AssertionError
1602
ret[(k,)] = osutils.sha_strings(lines)
1605
def get_record_stream(self, keys, ordering, include_delta_closure):
1606
"""See VersionedFiles.get_record_stream."""
1607
for (k,) in list(keys):
1608
lines = self._get_lines(k)
1609
if lines is not None:
1610
if not isinstance(lines, list):
1611
raise AssertionError
1612
yield ChunkedContentFactory((k,), None,
1613
sha1=osutils.sha_strings(lines),
1616
yield AbsentContentFactory((k,))
1618
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1619
"""See VersionedFile.iter_lines_added_or_present_in_versions()."""
1620
for i, (key,) in enumerate(keys):
1622
pb.update("Finding changed lines", i, len(keys))
1623
for l in self._get_lines(key):
1627
def network_bytes_to_kind_and_offset(network_bytes):
1628
"""Strip of a record kind from the front of network_bytes.
1630
:param network_bytes: The bytes of a record.
1631
:return: A tuple (storage_kind, offset_of_remaining_bytes)
1633
line_end = network_bytes.find('\n')
1634
storage_kind = network_bytes[:line_end]
1635
return storage_kind, line_end + 1
1638
class NetworkRecordStream(object):
1639
"""A record_stream which reconstitures a serialised stream."""
1641
def __init__(self, bytes_iterator):
1642
"""Create a NetworkRecordStream.
1644
:param bytes_iterator: An iterator of bytes. Each item in this
1645
iterator should have been obtained from a record_streams'
1646
record.get_bytes_as(record.storage_kind) call.
1648
self._bytes_iterator = bytes_iterator
1649
self._kind_factory = {
1650
'fulltext': fulltext_network_to_record,
1651
'groupcompress-block': groupcompress.network_block_to_records,
1652
'knit-ft-gz': knit.knit_network_to_record,
1653
'knit-delta-gz': knit.knit_network_to_record,
1654
'knit-annotated-ft-gz': knit.knit_network_to_record,
1655
'knit-annotated-delta-gz': knit.knit_network_to_record,
1656
'knit-delta-closure': knit.knit_delta_closure_to_records,
1662
:return: An iterator as per VersionedFiles.get_record_stream().
1664
for bytes in self._bytes_iterator:
1665
storage_kind, line_end = network_bytes_to_kind_and_offset(bytes)
1666
for record in self._kind_factory[storage_kind](
1667
storage_kind, bytes, line_end):
1671
def fulltext_network_to_record(kind, bytes, line_end):
1672
"""Convert a network fulltext record to record."""
1673
meta_len, = struct.unpack('!L', bytes[line_end:line_end+4])
1674
record_meta = bytes[line_end+4:line_end+4+meta_len]
1675
key, parents = bencode.bdecode_as_tuple(record_meta)
1676
if parents == 'nil':
1678
fulltext = bytes[line_end+4+meta_len:]
1679
return [FulltextContentFactory(key, parents, None, fulltext)]
1682
def _length_prefix(bytes):
1683
return struct.pack('!L', len(bytes))
1686
def record_to_fulltext_bytes(record):
1687
if record.parents is None:
1690
parents = record.parents
1691
record_meta = bencode.bencode((record.key, parents))
1692
record_content = record.get_bytes_as('fulltext')
1693
return "fulltext\n%s%s%s" % (
1694
_length_prefix(record_meta), record_meta, record_content)
1697
def sort_groupcompress(parent_map):
1698
"""Sort and group the keys in parent_map into groupcompress order.
1700
groupcompress is defined (currently) as reverse-topological order, grouped
1703
:return: A sorted-list of keys
1705
# gc-optimal ordering is approximately reverse topological,
1706
# properly grouped by file-id.
1708
for item in parent_map.iteritems():
1710
if isinstance(key, str) or len(key) == 1:
770
# TODO for incremental cross-format work:
771
# make a versioned file with the following content:
772
# all revisions we have been asked to join
773
# all their ancestors that are *not* in target already.
774
# the immediate parents of the above two sets, with
775
# empty parent lists - these versions are in target already
776
# and the incorrect version data will be ignored.
777
# TODO: for all ancestors that are present in target already,
778
# check them for consistent data, this requires moving sha1 from
780
# TODO: remove parent texts when they are not relevant any more for
781
# memory pressure reduction. RBC 20060313
782
# pb.update('Converting versioned data', 0, len(order))
784
for index, version in enumerate(order):
785
pb.update('Converting versioned data', index, total)
786
if version in target:
788
_, _, parent_text = target.add_lines(version,
790
self.source.get_lines(version),
791
parent_texts=parent_texts)
792
parent_texts[version] = parent_text
797
def _get_source_version_ids(self, version_ids, ignore_missing):
798
"""Determine the version ids to be used from self.source.
800
:param version_ids: The caller-supplied version ids to check. (None
801
for all). If None is in version_ids, it is stripped.
802
:param ignore_missing: if True, remove missing ids from the version
803
list. If False, raise RevisionNotPresent on
804
a missing version id.
805
:return: A set of version ids.
807
if version_ids is None:
808
# None cannot be in source.versions
809
return set(self.source.versions())
812
return set(self.source.versions()).intersection(set(version_ids))
814
new_version_ids = set()
815
for version in version_ids:
818
if not self.source.has_version(version):
819
raise errors.RevisionNotPresent(version, str(self.source))
821
new_version_ids.add(version)
822
return new_version_ids
1715
per_prefix_map[prefix].append(item)
1717
per_prefix_map[prefix] = [item]
1720
for prefix in sorted(per_prefix_map):
1721
present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
added
removed
bzrlib/versionedfile.py
