542
481
unchanged Alive in both a and b (possibly created in both)
543
482
new-a Created in a
544
483
new-b Created in b
545
ghost-a Killed in a, unborn in b
484
ghost-a Killed in a, unborn in b
546
485
ghost-b Killed in b, unborn in a
547
486
irrelevant Not in either revision
549
488
raise NotImplementedError(VersionedFile.plan_merge)
551
490
def weave_merge(self, plan, a_marker=TextMerge.A_MARKER,
552
491
b_marker=TextMerge.B_MARKER):
553
492
return PlanWeaveMerge(plan, a_marker, b_marker).merge_lines()[0]
556
class RecordingVersionedFilesDecorator(object):
557
"""A minimal versioned files that records calls made on it.
559
Only enough methods have been added to support tests using it to date.
561
:ivar calls: A list of the calls made; can be reset at any time by
565
def __init__(self, backing_vf):
566
"""Create a RecordingVersionedFilesDecorator decorating backing_vf.
568
:param backing_vf: The versioned file to answer all methods.
570
self._backing_vf = backing_vf
573
def add_lines(self, key, parents, lines, parent_texts=None,
574
left_matching_blocks=None, nostore_sha=None, random_id=False,
576
self.calls.append(("add_lines", key, parents, lines, parent_texts,
577
left_matching_blocks, nostore_sha, random_id, check_content))
578
return self._backing_vf.add_lines(key, parents, lines, parent_texts,
579
left_matching_blocks, nostore_sha, random_id, check_content)
582
self._backing_vf.check()
584
def get_parent_map(self, keys):
585
self.calls.append(("get_parent_map", copy(keys)))
586
return self._backing_vf.get_parent_map(keys)
588
def get_record_stream(self, keys, sort_order, include_delta_closure):
589
self.calls.append(("get_record_stream", list(keys), sort_order,
590
include_delta_closure))
591
return self._backing_vf.get_record_stream(keys, sort_order,
592
include_delta_closure)
594
def get_sha1s(self, keys):
595
self.calls.append(("get_sha1s", copy(keys)))
596
return self._backing_vf.get_sha1s(keys)
598
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
599
self.calls.append(("iter_lines_added_or_present_in_keys", copy(keys)))
600
return self._backing_vf.iter_lines_added_or_present_in_keys(keys, pb=pb)
603
self.calls.append(("keys",))
604
return self._backing_vf.keys()
607
class OrderingVersionedFilesDecorator(RecordingVersionedFilesDecorator):
608
"""A VF that records calls, and returns keys in specific order.
610
:ivar calls: A list of the calls made; can be reset at any time by
614
def __init__(self, backing_vf, key_priority):
615
"""Create a RecordingVersionedFilesDecorator decorating backing_vf.
617
:param backing_vf: The versioned file to answer all methods.
618
:param key_priority: A dictionary defining what order keys should be
619
returned from an 'unordered' get_record_stream request.
620
Keys with lower priority are returned first, keys not present in
621
the map get an implicit priority of 0, and are returned in
622
lexicographical order.
624
RecordingVersionedFilesDecorator.__init__(self, backing_vf)
625
self._key_priority = key_priority
627
def get_record_stream(self, keys, sort_order, include_delta_closure):
628
self.calls.append(("get_record_stream", list(keys), sort_order,
629
include_delta_closure))
630
if sort_order == 'unordered':
632
return (self._key_priority.get(key, 0), key)
633
# Use a defined order by asking for the keys one-by-one from the
635
for key in sorted(keys, key=sort_key):
636
for record in self._backing_vf.get_record_stream([key],
637
'unordered', include_delta_closure):
640
for record in self._backing_vf.get_record_stream(keys, sort_order,
641
include_delta_closure):
645
class KeyMapper(object):
646
"""KeyMappers map between keys and underlying partitioned storage."""
649
"""Map key to an underlying storage identifier.
651
:param key: A key tuple e.g. ('file-id', 'revision-id').
652
:return: An underlying storage identifier, specific to the partitioning
655
raise NotImplementedError(self.map)
657
def unmap(self, partition_id):
658
"""Map a partitioned storage id back to a key prefix.
660
:param partition_id: The underlying partition id.
661
:return: As much of a key (or prefix) as is derivable from the partition
664
raise NotImplementedError(self.unmap)
667
class ConstantMapper(KeyMapper):
668
"""A key mapper that maps to a constant result."""
670
def __init__(self, result):
671
"""Create a ConstantMapper which will return result for all maps."""
672
self._result = result
675
"""See KeyMapper.map()."""
679
class URLEscapeMapper(KeyMapper):
680
"""Base class for use with transport backed storage.
682
This provides a map and unmap wrapper that respectively url escape and
683
unescape their outputs and inputs.
687
"""See KeyMapper.map()."""
688
return urllib.quote(self._map(key))
690
def unmap(self, partition_id):
691
"""See KeyMapper.unmap()."""
692
return self._unmap(urllib.unquote(partition_id))
695
class PrefixMapper(URLEscapeMapper):
696
"""A key mapper that extracts the first component of a key.
698
This mapper is for use with a transport based backend.
702
"""See KeyMapper.map()."""
705
def _unmap(self, partition_id):
706
"""See KeyMapper.unmap()."""
707
return (partition_id,)
710
class HashPrefixMapper(URLEscapeMapper):
711
"""A key mapper that combines the first component of a key with a hash.
713
This mapper is for use with a transport based backend.
717
"""See KeyMapper.map()."""
718
prefix = self._escape(key[0])
719
return "%02x/%s" % (adler32(prefix) & 0xff, prefix)
721
def _escape(self, prefix):
722
"""No escaping needed here."""
725
def _unmap(self, partition_id):
726
"""See KeyMapper.unmap()."""
727
return (self._unescape(osutils.basename(partition_id)),)
729
def _unescape(self, basename):
730
"""No unescaping needed for HashPrefixMapper."""
734
class HashEscapedPrefixMapper(HashPrefixMapper):
735
"""Combines the escaped first component of a key with a hash.
737
This mapper is for use with a transport based backend.
740
_safe = "abcdefghijklmnopqrstuvwxyz0123456789-_@,."
742
def _escape(self, prefix):
743
"""Turn a key element into a filesystem safe string.
745
This is similar to a plain urllib.quote, except
746
it uses specific safe characters, so that it doesn't
747
have to translate a lot of valid file ids.
749
# @ does not get escaped. This is because it is a valid
750
# filesystem character we use all the time, and it looks
751
# a lot better than seeing %40 all the time.
752
r = [((c in self._safe) and c or ('%%%02x' % ord(c)))
756
def _unescape(self, basename):
757
"""Escaped names are easily unescaped by urlutils."""
758
return urllib.unquote(basename)
761
def make_versioned_files_factory(versioned_file_factory, mapper):
762
"""Create a ThunkedVersionedFiles factory.
764
This will create a callable which when called creates a
765
ThunkedVersionedFiles on a transport, using mapper to access individual
766
versioned files, and versioned_file_factory to create each individual file.
768
def factory(transport):
769
return ThunkedVersionedFiles(transport, versioned_file_factory, mapper,
774
class VersionedFiles(object):
775
"""Storage for many versioned files.
777
This object allows a single keyspace for accessing the history graph and
778
contents of named bytestrings.
780
Currently no implementation allows the graph of different key prefixes to
781
intersect, but the API does allow such implementations in the future.
783
The keyspace is expressed via simple tuples. Any instance of VersionedFiles
784
may have a different length key-size, but that size will be constant for
785
all texts added to or retrieved from it. For instance, bzrlib uses
786
instances with a key-size of 2 for storing user files in a repository, with
787
the first element the fileid, and the second the version of that file.
789
The use of tuples allows a single code base to support several different
790
uses with only the mapping logic changing from instance to instance.
793
def add_lines(self, key, parents, lines, parent_texts=None,
794
left_matching_blocks=None, nostore_sha=None, random_id=False,
796
"""Add a text to the store.
798
:param key: The key tuple of the text to add. If the last element is
799
None, a CHK string will be generated during the addition.
800
:param parents: The parents key tuples of the text to add.
801
:param lines: A list of lines. Each line must be a bytestring. And all
802
of them except the last must be terminated with \n and contain no
803
other \n's. The last line may either contain no \n's or a single
804
terminating \n. If the lines list does meet this constraint the add
805
routine may error or may succeed - but you will be unable to read
806
the data back accurately. (Checking the lines have been split
807
correctly is expensive and extremely unlikely to catch bugs so it
808
is not done at runtime unless check_content is True.)
809
:param parent_texts: An optional dictionary containing the opaque
810
representations of some or all of the parents of version_id to
811
allow delta optimisations. VERY IMPORTANT: the texts must be those
812
returned by add_lines or data corruption can be caused.
813
:param left_matching_blocks: a hint about which areas are common
814
between the text and its left-hand-parent. The format is
815
the SequenceMatcher.get_matching_blocks format.
816
:param nostore_sha: Raise ExistingContent and do not add the lines to
817
the versioned file if the digest of the lines matches this.
818
:param random_id: If True a random id has been selected rather than
819
an id determined by some deterministic process such as a converter
820
from a foreign VCS. When True the backend may choose not to check
821
for uniqueness of the resulting key within the versioned file, so
822
this should only be done when the result is expected to be unique
824
:param check_content: If True, the lines supplied are verified to be
825
bytestrings that are correctly formed lines.
826
:return: The text sha1, the number of bytes in the text, and an opaque
827
representation of the inserted version which can be provided
828
back to future add_lines calls in the parent_texts dictionary.
830
raise NotImplementedError(self.add_lines)
832
def add_mpdiffs(self, records):
833
"""Add mpdiffs to this VersionedFile.
835
Records should be iterables of version, parents, expected_sha1,
836
mpdiff. mpdiff should be a MultiParent instance.
839
mpvf = multiparent.MultiMemoryVersionedFile()
841
for version, parent_ids, expected_sha1, mpdiff in records:
842
versions.append(version)
843
mpvf.add_diff(mpdiff, version, parent_ids)
844
needed_parents = set()
845
for version, parent_ids, expected_sha1, mpdiff in records:
846
needed_parents.update(p for p in parent_ids
847
if not mpvf.has_version(p))
848
# It seems likely that adding all the present parents as fulltexts can
849
# easily exhaust memory.
850
chunks_to_lines = osutils.chunks_to_lines
851
for record in self.get_record_stream(needed_parents, 'unordered',
853
if record.storage_kind == 'absent':
855
mpvf.add_version(chunks_to_lines(record.get_bytes_as('chunked')),
857
for (key, parent_keys, expected_sha1, mpdiff), lines in\
858
zip(records, mpvf.get_line_list(versions)):
859
if len(parent_keys) == 1:
860
left_matching_blocks = list(mpdiff.get_matching_blocks(0,
861
mpvf.get_diff(parent_keys[0]).num_lines()))
863
left_matching_blocks = None
864
version_sha1, _, version_text = self.add_lines(key,
865
parent_keys, lines, vf_parents,
866
left_matching_blocks=left_matching_blocks)
867
if version_sha1 != expected_sha1:
868
raise errors.VersionedFileInvalidChecksum(version)
869
vf_parents[key] = version_text
871
def annotate(self, key):
872
"""Return a list of (version-key, line) tuples for the text of key.
874
:raise RevisionNotPresent: If the key is not present.
876
raise NotImplementedError(self.annotate)
878
def check(self, progress_bar=None):
879
"""Check this object for integrity."""
880
raise NotImplementedError(self.check)
883
def check_not_reserved_id(version_id):
884
revision.check_not_reserved_id(version_id)
886
def _check_lines_not_unicode(self, lines):
887
"""Check that lines being added to a versioned file are not unicode."""
889
if line.__class__ is not str:
890
raise errors.BzrBadParameterUnicode("lines")
892
def _check_lines_are_lines(self, lines):
893
"""Check that the lines really are full lines without inline EOL."""
895
if '\n' in line[:-1]:
896
raise errors.BzrBadParameterContainsNewline("lines")
898
def get_parent_map(self, keys):
899
"""Get a map of the parents of keys.
901
:param keys: The keys to look up parents for.
902
:return: A mapping from keys to parents. Absent keys are absent from
905
raise NotImplementedError(self.get_parent_map)
907
def get_record_stream(self, keys, ordering, include_delta_closure):
908
"""Get a stream of records for keys.
910
:param keys: The keys to include.
911
:param ordering: Either 'unordered' or 'topological'. A topologically
912
sorted stream has compression parents strictly before their
914
:param include_delta_closure: If True then the closure across any
915
compression parents will be included (in the opaque data).
916
:return: An iterator of ContentFactory objects, each of which is only
917
valid until the iterator is advanced.
919
raise NotImplementedError(self.get_record_stream)
921
def get_sha1s(self, keys):
922
"""Get the sha1's of the texts for the given keys.
924
:param keys: The names of the keys to lookup
925
:return: a dict from key to sha1 digest. Keys of texts which are not
926
present in the store are not present in the returned
929
raise NotImplementedError(self.get_sha1s)
931
has_key = index._has_key_from_parent_map
933
def get_missing_compression_parent_keys(self):
934
"""Return an iterable of keys of missing compression parents.
936
Check this after calling insert_record_stream to find out if there are
937
any missing compression parents. If there are, the records that
938
depend on them are not able to be inserted safely. The precise
939
behaviour depends on the concrete VersionedFiles class in use.
941
Classes that do not support this will raise NotImplementedError.
943
raise NotImplementedError(self.get_missing_compression_parent_keys)
945
def insert_record_stream(self, stream):
946
"""Insert a record stream into this container.
948
:param stream: A stream of records to insert.
950
:seealso VersionedFile.get_record_stream:
952
raise NotImplementedError
954
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
955
"""Iterate over the lines in the versioned files from keys.
957
This may return lines from other keys. Each item the returned
958
iterator yields is a tuple of a line and a text version that that line
959
is present in (not introduced in).
961
Ordering of results is in whatever order is most suitable for the
962
underlying storage format.
964
If a progress bar is supplied, it may be used to indicate progress.
965
The caller is responsible for cleaning up progress bars (because this
969
* Lines are normalised by the underlying store: they will all have \n
971
* Lines are returned in arbitrary order.
973
:return: An iterator over (line, key).
975
raise NotImplementedError(self.iter_lines_added_or_present_in_keys)
978
"""Return a iterable of the keys for all the contained texts."""
979
raise NotImplementedError(self.keys)
981
def make_mpdiffs(self, keys):
982
"""Create multiparent diffs for specified keys."""
983
keys_order = tuple(keys)
984
keys = frozenset(keys)
985
knit_keys = set(keys)
986
parent_map = self.get_parent_map(keys)
987
for parent_keys in parent_map.itervalues():
989
knit_keys.update(parent_keys)
990
missing_keys = keys - set(parent_map)
992
raise errors.RevisionNotPresent(list(missing_keys)[0], self)
993
# We need to filter out ghosts, because we can't diff against them.
994
maybe_ghosts = knit_keys - keys
995
ghosts = maybe_ghosts - set(self.get_parent_map(maybe_ghosts))
996
knit_keys.difference_update(ghosts)
998
chunks_to_lines = osutils.chunks_to_lines
999
for record in self.get_record_stream(knit_keys, 'topological', True):
1000
lines[record.key] = chunks_to_lines(record.get_bytes_as('chunked'))
1001
# line_block_dict = {}
1002
# for parent, blocks in record.extract_line_blocks():
1003
# line_blocks[parent] = blocks
1004
# line_blocks[record.key] = line_block_dict
1006
for key in keys_order:
1008
parents = parent_map[key] or []
1009
# Note that filtering knit_keys can lead to a parent difference
1010
# between the creation and the application of the mpdiff.
1011
parent_lines = [lines[p] for p in parents if p in knit_keys]
1012
if len(parent_lines) > 0:
1013
left_parent_blocks = self._extract_blocks(key, parent_lines[0],
1016
left_parent_blocks = None
1017
diffs.append(multiparent.MultiParent.from_lines(target,
1018
parent_lines, left_parent_blocks))
1021
missing_keys = index._missing_keys_from_parent_map
1023
def _extract_blocks(self, version_id, source, target):
1027
class ThunkedVersionedFiles(VersionedFiles):
1028
"""Storage for many versioned files thunked onto a 'VersionedFile' class.
1030
This object allows a single keyspace for accessing the history graph and
1031
contents of named bytestrings.
1033
Currently no implementation allows the graph of different key prefixes to
1034
intersect, but the API does allow such implementations in the future.
1037
def __init__(self, transport, file_factory, mapper, is_locked):
1038
"""Create a ThunkedVersionedFiles."""
1039
self._transport = transport
1040
self._file_factory = file_factory
1041
self._mapper = mapper
1042
self._is_locked = is_locked
1044
def add_lines(self, key, parents, lines, parent_texts=None,
1045
left_matching_blocks=None, nostore_sha=None, random_id=False,
1046
check_content=True):
1047
"""See VersionedFiles.add_lines()."""
1048
path = self._mapper.map(key)
1049
version_id = key[-1]
1050
parents = [parent[-1] for parent in parents]
1051
vf = self._get_vf(path)
1054
return vf.add_lines_with_ghosts(version_id, parents, lines,
1055
parent_texts=parent_texts,
1056
left_matching_blocks=left_matching_blocks,
1057
nostore_sha=nostore_sha, random_id=random_id,
1058
check_content=check_content)
1059
except NotImplementedError:
1060
return vf.add_lines(version_id, parents, lines,
1061
parent_texts=parent_texts,
1062
left_matching_blocks=left_matching_blocks,
1063
nostore_sha=nostore_sha, random_id=random_id,
1064
check_content=check_content)
1065
except errors.NoSuchFile:
1066
# parent directory may be missing, try again.
1067
self._transport.mkdir(osutils.dirname(path))
1069
return vf.add_lines_with_ghosts(version_id, parents, lines,
1070
parent_texts=parent_texts,
1071
left_matching_blocks=left_matching_blocks,
1072
nostore_sha=nostore_sha, random_id=random_id,
1073
check_content=check_content)
1074
except NotImplementedError:
1075
return vf.add_lines(version_id, parents, lines,
1076
parent_texts=parent_texts,
1077
left_matching_blocks=left_matching_blocks,
1078
nostore_sha=nostore_sha, random_id=random_id,
1079
check_content=check_content)
1081
def annotate(self, key):
1082
"""Return a list of (version-key, line) tuples for the text of key.
1084
:raise RevisionNotPresent: If the key is not present.
1087
path = self._mapper.map(prefix)
1088
vf = self._get_vf(path)
1089
origins = vf.annotate(key[-1])
1091
for origin, line in origins:
1092
result.append((prefix + (origin,), line))
1095
def check(self, progress_bar=None):
1096
"""See VersionedFiles.check()."""
1097
for prefix, vf in self._iter_all_components():
1100
def get_parent_map(self, keys):
1101
"""Get a map of the parents of keys.
1103
:param keys: The keys to look up parents for.
1104
:return: A mapping from keys to parents. Absent keys are absent from
1107
prefixes = self._partition_keys(keys)
1109
for prefix, suffixes in prefixes.items():
1110
path = self._mapper.map(prefix)
1111
vf = self._get_vf(path)
1112
parent_map = vf.get_parent_map(suffixes)
1113
for key, parents in parent_map.items():
1114
result[prefix + (key,)] = tuple(
1115
prefix + (parent,) for parent in parents)
1118
def _get_vf(self, path):
1119
if not self._is_locked():
1120
raise errors.ObjectNotLocked(self)
1121
return self._file_factory(path, self._transport, create=True,
1122
get_scope=lambda:None)
1124
def _partition_keys(self, keys):
1125
"""Turn keys into a dict of prefix:suffix_list."""
1128
prefix_keys = result.setdefault(key[:-1], [])
1129
prefix_keys.append(key[-1])
1132
def _get_all_prefixes(self):
1133
# Identify all key prefixes.
1134
# XXX: A bit hacky, needs polish.
1135
if type(self._mapper) == ConstantMapper:
1136
paths = [self._mapper.map(())]
1140
for quoted_relpath in self._transport.iter_files_recursive():
1141
path, ext = os.path.splitext(quoted_relpath)
1143
paths = list(relpaths)
1144
prefixes = [self._mapper.unmap(path) for path in paths]
1145
return zip(paths, prefixes)
1147
def get_record_stream(self, keys, ordering, include_delta_closure):
1148
"""See VersionedFiles.get_record_stream()."""
1149
# Ordering will be taken care of by each partitioned store; group keys
1152
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1153
suffixes = [(suffix,) for suffix in suffixes]
1154
for record in vf.get_record_stream(suffixes, ordering,
1155
include_delta_closure):
1156
if record.parents is not None:
1157
record.parents = tuple(
1158
prefix + parent for parent in record.parents)
1159
record.key = prefix + record.key
1162
def _iter_keys_vf(self, keys):
1163
prefixes = self._partition_keys(keys)
1165
for prefix, suffixes in prefixes.items():
1166
path = self._mapper.map(prefix)
1167
vf = self._get_vf(path)
1168
yield prefix, suffixes, vf
1170
def get_sha1s(self, keys):
1171
"""See VersionedFiles.get_sha1s()."""
1173
for prefix,suffixes, vf in self._iter_keys_vf(keys):
1174
vf_sha1s = vf.get_sha1s(suffixes)
1175
for suffix, sha1 in vf_sha1s.iteritems():
1176
sha1s[prefix + (suffix,)] = sha1
1179
def insert_record_stream(self, stream):
1180
"""Insert a record stream into this container.
1182
:param stream: A stream of records to insert.
1184
:seealso VersionedFile.get_record_stream:
1186
for record in stream:
1187
prefix = record.key[:-1]
1188
key = record.key[-1:]
1189
if record.parents is not None:
1190
parents = [parent[-1:] for parent in record.parents]
1193
thunk_record = AdapterFactory(key, parents, record)
1194
path = self._mapper.map(prefix)
1195
# Note that this parses the file many times; we can do better but
1196
# as this only impacts weaves in terms of performance, it is
1198
vf = self._get_vf(path)
1199
vf.insert_record_stream([thunk_record])
1201
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1202
"""Iterate over the lines in the versioned files from keys.
1204
This may return lines from other keys. Each item the returned
1205
iterator yields is a tuple of a line and a text version that that line
1206
is present in (not introduced in).
1208
Ordering of results is in whatever order is most suitable for the
1209
underlying storage format.
1211
If a progress bar is supplied, it may be used to indicate progress.
1212
The caller is responsible for cleaning up progress bars (because this
1216
* Lines are normalised by the underlying store: they will all have \n
1218
* Lines are returned in arbitrary order.
1220
:return: An iterator over (line, key).
1222
for prefix, suffixes, vf in self._iter_keys_vf(keys):
1223
for line, version in vf.iter_lines_added_or_present_in_versions(suffixes):
1224
yield line, prefix + (version,)
1226
def _iter_all_components(self):
1227
for path, prefix in self._get_all_prefixes():
1228
yield prefix, self._get_vf(path)
1231
"""See VersionedFiles.keys()."""
1233
for prefix, vf in self._iter_all_components():
1234
for suffix in vf.versions():
1235
result.add(prefix + (suffix,))
1239
class _PlanMergeVersionedFile(VersionedFiles):
495
class _PlanMergeVersionedFile(object):
1240
496
"""A VersionedFile for uncommitted and committed texts.
1242
498
It is intended to allow merges to be planned with working tree texts.
1243
It implements only the small part of the VersionedFiles interface used by
499
It implements only the small part of the VersionedFile interface used by
1244
500
PlanMerge. It falls back to multiple versionedfiles for data not stored in
1245
501
_PlanMergeVersionedFile itself.
1247
:ivar: fallback_versionedfiles a list of VersionedFiles objects that can be
1248
queried for missing texts.
1251
def __init__(self, file_id):
1252
"""Create a _PlanMergeVersionedFile.
504
def __init__(self, file_id, fallback_versionedfiles=None):
1254
:param file_id: Used with _PlanMerge code which is not yet fully
1255
tuple-keyspace aware.
507
:param file_id: Used when raising exceptions.
508
:param fallback_versionedfiles: If supplied, the set of fallbacks to
509
use. Otherwise, _PlanMergeVersionedFile.fallback_versionedfiles
510
can be appended to later.
1257
512
self._file_id = file_id
1258
# fallback locations
1259
self.fallback_versionedfiles = []
1260
# Parents for locally held keys.
513
if fallback_versionedfiles is None:
514
self.fallback_versionedfiles = []
516
self.fallback_versionedfiles = fallback_versionedfiles
1261
517
self._parents = {}
1262
# line data for locally held keys.
1263
518
self._lines = {}
1264
# key lookup providers
1265
self._providers = [DictParentsProvider(self._parents)]
1267
520
def plan_merge(self, ver_a, ver_b, base=None):
1268
521
"""See VersionedFile.plan_merge"""
1269
522
from bzrlib.merge import _PlanMerge
1270
523
if base is None:
1271
return _PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge()
1272
old_plan = list(_PlanMerge(ver_a, base, self, (self._file_id,)).plan_merge())
1273
new_plan = list(_PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge())
524
return _PlanMerge(ver_a, ver_b, self).plan_merge()
525
old_plan = list(_PlanMerge(ver_a, base, self).plan_merge())
526
new_plan = list(_PlanMerge(ver_a, ver_b, self).plan_merge())
1274
527
return _PlanMerge._subtract_plans(old_plan, new_plan)
1276
529
def plan_lca_merge(self, ver_a, ver_b, base=None):
1277
530
from bzrlib.merge import _PlanLCAMerge
1279
new_plan = _PlanLCAMerge(ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
531
graph = self._get_graph()
532
new_plan = _PlanLCAMerge(ver_a, ver_b, self, graph).plan_merge()
1280
533
if base is None:
1282
old_plan = _PlanLCAMerge(ver_a, base, self, (self._file_id,), graph).plan_merge()
535
old_plan = _PlanLCAMerge(ver_a, base, self, graph).plan_merge()
1283
536
return _PlanLCAMerge._subtract_plans(list(old_plan), list(new_plan))
1285
def add_lines(self, key, parents, lines):
1286
"""See VersionedFiles.add_lines
538
def add_lines(self, version_id, parents, lines):
539
"""See VersionedFile.add_lines
1288
Lines are added locally, not to fallback versionedfiles. Also, ghosts
1289
are permitted. Only reserved ids are permitted.
541
Lines are added locally, not fallback versionedfiles. Also, ghosts are
542
permitted. Only reserved ids are permitted.
1291
if type(key) is not tuple:
1292
raise TypeError(key)
1293
if not revision.is_reserved_id(key[-1]):
544
if not revision.is_reserved_id(version_id):
1294
545
raise ValueError('Only reserved ids may be used')
1295
546
if parents is None:
1296
547
raise ValueError('Parents may not be None')
1297
548
if lines is None:
1298
549
raise ValueError('Lines may not be None')
1299
self._parents[key] = tuple(parents)
1300
self._lines[key] = lines
550
self._parents[version_id] = parents
551
self._lines[version_id] = lines
1302
def get_record_stream(self, keys, ordering, include_delta_closure):
1305
if key in self._lines:
1306
lines = self._lines[key]
1307
parents = self._parents[key]
1309
yield ChunkedContentFactory(key, parents, None, lines)
553
def get_lines(self, version_id):
554
"""See VersionedFile.get_ancestry"""
555
lines = self._lines.get(version_id)
556
if lines is not None:
1310
558
for versionedfile in self.fallback_versionedfiles:
1311
for record in versionedfile.get_record_stream(
1312
pending, 'unordered', True):
1313
if record.storage_kind == 'absent':
560
return versionedfile.get_lines(version_id)
561
except errors.RevisionNotPresent:
564
raise errors.RevisionNotPresent(version_id, self._file_id)
566
def get_ancestry(self, version_id, topo_sorted=False):
567
"""See VersionedFile.get_ancestry.
569
Note that this implementation assumes that if a VersionedFile can
570
answer get_ancestry at all, it can give an authoritative answer. In
571
fact, ghosts can invalidate this assumption. But it's good enough
572
99% of the time, and far cheaper/simpler.
574
Also note that the results of this version are never topologically
575
sorted, and are a set.
578
raise ValueError('This implementation does not provide sorting')
579
parents = self._parents.get(version_id)
581
for vf in self.fallback_versionedfiles:
583
return vf.get_ancestry(version_id, topo_sorted=False)
584
except errors.RevisionNotPresent:
1316
pending.remove(record.key)
1320
# report absent entries
1322
yield AbsentContentFactory(key)
1324
def get_parent_map(self, keys):
1325
"""See VersionedFiles.get_parent_map"""
1326
# We create a new provider because a fallback may have been added.
1327
# If we make fallbacks private we can update a stack list and avoid
1328
# object creation thrashing.
1331
if revision.NULL_REVISION in keys:
1332
keys.remove(revision.NULL_REVISION)
1333
result[revision.NULL_REVISION] = ()
1334
self._providers = self._providers[:1] + self.fallback_versionedfiles
1336
_StackedParentsProvider(self._providers).get_parent_map(keys))
1337
for key, parents in result.iteritems():
1339
result[key] = (revision.NULL_REVISION,)
587
raise errors.RevisionNotPresent(version_id, self._file_id)
588
ancestry = set([version_id])
589
for parent in parents:
590
ancestry.update(self.get_ancestry(parent, topo_sorted=False))
593
def get_parents(self, version_id):
594
"""See VersionedFile.get_parents"""
595
parents = self._parents.get(version_id)
596
if parents is not None:
598
for versionedfile in self.fallback_versionedfiles:
600
return versionedfile.get_parents(version_id)
601
except errors.RevisionNotPresent:
604
raise errors.RevisionNotPresent(version_id, self._file_id)
606
def _get_graph(self):
607
from bzrlib.graph import (
610
_StackedParentsProvider,
612
from bzrlib.repofmt.knitrepo import _KnitParentsProvider
613
parent_providers = [DictParentsProvider(self._parents)]
614
for vf in self.fallback_versionedfiles:
615
parent_providers.append(_KnitParentsProvider(vf))
616
return Graph(_StackedParentsProvider(parent_providers))
1343
619
class PlanWeaveMerge(TextMerge):
1344
620
"""Weave merge that takes a plan as its input.
1346
622
This exists so that VersionedFile.plan_merge is implementable.
1347
623
Most callers will want to use WeaveMerge instead.
1418
689
class WeaveMerge(PlanWeaveMerge):
1419
690
"""Weave merge that takes a VersionedFile and two versions as its input."""
1421
def __init__(self, versionedfile, ver_a, ver_b,
692
def __init__(self, versionedfile, ver_a, ver_b,
1422
693
a_marker=PlanWeaveMerge.A_MARKER, b_marker=PlanWeaveMerge.B_MARKER):
1423
694
plan = versionedfile.plan_merge(ver_a, ver_b)
1424
695
PlanWeaveMerge.__init__(self, plan, a_marker, b_marker)
1427
class VirtualVersionedFiles(VersionedFiles):
1428
"""Dummy implementation for VersionedFiles that uses other functions for
1429
obtaining fulltexts and parent maps.
1431
This is always on the bottom of the stack and uses string keys
1432
(rather than tuples) internally.
1435
def __init__(self, get_parent_map, get_lines):
1436
"""Create a VirtualVersionedFiles.
1438
:param get_parent_map: Same signature as Repository.get_parent_map.
1439
:param get_lines: Should return lines for specified key or None if
1442
super(VirtualVersionedFiles, self).__init__()
1443
self._get_parent_map = get_parent_map
1444
self._get_lines = get_lines
1446
def check(self, progressbar=None):
1447
"""See VersionedFiles.check.
1449
:note: Always returns True for VirtualVersionedFiles.
1453
def add_mpdiffs(self, records):
1454
"""See VersionedFiles.mpdiffs.
1456
:note: Not implemented for VirtualVersionedFiles.
1458
raise NotImplementedError(self.add_mpdiffs)
1460
def get_parent_map(self, keys):
1461
"""See VersionedFiles.get_parent_map."""
1462
return dict([((k,), tuple([(p,) for p in v]))
1463
for k,v in self._get_parent_map([k for (k,) in keys]).iteritems()])
1465
def get_sha1s(self, keys):
1466
"""See VersionedFiles.get_sha1s."""
1469
lines = self._get_lines(k)
1470
if lines is not None:
1471
if not isinstance(lines, list):
1472
raise AssertionError
1473
ret[(k,)] = osutils.sha_strings(lines)
1476
def get_record_stream(self, keys, ordering, include_delta_closure):
1477
"""See VersionedFiles.get_record_stream."""
1478
for (k,) in list(keys):
1479
lines = self._get_lines(k)
1480
if lines is not None:
1481
if not isinstance(lines, list):
1482
raise AssertionError
1483
yield ChunkedContentFactory((k,), None,
1484
sha1=osutils.sha_strings(lines),
1487
yield AbsentContentFactory((k,))
1489
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1490
"""See VersionedFile.iter_lines_added_or_present_in_versions()."""
1491
for i, (key,) in enumerate(keys):
1493
pb.update("Finding changed lines", i, len(keys))
1494
for l in self._get_lines(key):
1498
def network_bytes_to_kind_and_offset(network_bytes):
1499
"""Strip of a record kind from the front of network_bytes.
1501
:param network_bytes: The bytes of a record.
1502
:return: A tuple (storage_kind, offset_of_remaining_bytes)
1504
line_end = network_bytes.find('\n')
1505
storage_kind = network_bytes[:line_end]
1506
return storage_kind, line_end + 1
1509
class NetworkRecordStream(object):
1510
"""A record_stream which reconstitures a serialised stream."""
1512
def __init__(self, bytes_iterator):
1513
"""Create a NetworkRecordStream.
1515
:param bytes_iterator: An iterator of bytes. Each item in this
1516
iterator should have been obtained from a record_streams'
1517
record.get_bytes_as(record.storage_kind) call.
1519
self._bytes_iterator = bytes_iterator
1520
self._kind_factory = {'knit-ft-gz':knit.knit_network_to_record,
1521
'knit-delta-gz':knit.knit_network_to_record,
1522
'knit-annotated-ft-gz':knit.knit_network_to_record,
1523
'knit-annotated-delta-gz':knit.knit_network_to_record,
1524
'knit-delta-closure':knit.knit_delta_closure_to_records,
1525
'fulltext':fulltext_network_to_record,
1526
'groupcompress-block':groupcompress.network_block_to_records,
1532
:return: An iterator as per VersionedFiles.get_record_stream().
1534
for bytes in self._bytes_iterator:
1535
storage_kind, line_end = network_bytes_to_kind_and_offset(bytes)
1536
for record in self._kind_factory[storage_kind](
1537
storage_kind, bytes, line_end):
1541
def fulltext_network_to_record(kind, bytes, line_end):
1542
"""Convert a network fulltext record to record."""
1543
meta_len, = struct.unpack('!L', bytes[line_end:line_end+4])
1544
record_meta = bytes[line_end+4:line_end+4+meta_len]
1545
key, parents = bencode.bdecode_as_tuple(record_meta)
1546
if parents == 'nil':
1548
fulltext = bytes[line_end+4+meta_len:]
1549
return [FulltextContentFactory(key, parents, None, fulltext)]
1552
def _length_prefix(bytes):
1553
return struct.pack('!L', len(bytes))
1556
def record_to_fulltext_bytes(record):
1557
if record.parents is None:
1560
parents = record.parents
1561
record_meta = bencode.bencode((record.key, parents))
1562
record_content = record.get_bytes_as('fulltext')
1563
return "fulltext\n%s%s%s" % (
1564
_length_prefix(record_meta), record_meta, record_content)
1567
def sort_groupcompress(parent_map):
1568
"""Sort and group the keys in parent_map into groupcompress order.
1570
groupcompress is defined (currently) as reverse-topological order, grouped
1573
:return: A sorted-list of keys
1575
# gc-optimal ordering is approximately reverse topological,
1576
# properly grouped by file-id.
1578
for item in parent_map.iteritems():
1580
if isinstance(key, str) or len(key) == 1:
698
class InterVersionedFile(InterObject):
699
"""This class represents operations taking place between two VersionedFiles.
701
Its instances have methods like join, and contain
702
references to the source and target versionedfiles these operations can be
705
Often we will provide convenience methods on 'versionedfile' which carry out
706
operations with another versionedfile - they will always forward to
707
InterVersionedFile.get(other).method_name(parameters).
711
"""The available optimised InterVersionedFile types."""
713
def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
714
"""Integrate versions from self.source into self.target.
716
If version_ids is None all versions from source should be
717
incorporated into this versioned file.
719
Must raise RevisionNotPresent if any of the specified versions
720
are not present in the other file's history unless ignore_missing is
721
supplied in which case they are silently skipped.
724
# - if the target is empty, just add all the versions from
725
# source to target, otherwise:
726
# - make a temporary versioned file of type target
727
# - insert the source content into it one at a time
729
if not self.target.versions():
732
# Make a new target-format versioned file.
733
temp_source = self.target.create_empty("temp", MemoryTransport())
735
version_ids = self._get_source_version_ids(version_ids, ignore_missing)
736
graph = self.source.get_graph(version_ids)
737
order = tsort.topo_sort(graph.items())
738
pb = ui.ui_factory.nested_progress_bar()
1585
per_prefix_map[prefix].append(item)
1587
per_prefix_map[prefix] = [item]
1590
for prefix in sorted(per_prefix_map):
1591
present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
741
# TODO for incremental cross-format work:
742
# make a versioned file with the following content:
743
# all revisions we have been asked to join
744
# all their ancestors that are *not* in target already.
745
# the immediate parents of the above two sets, with
746
# empty parent lists - these versions are in target already
747
# and the incorrect version data will be ignored.
748
# TODO: for all ancestors that are present in target already,
749
# check them for consistent data, this requires moving sha1 from
751
# TODO: remove parent texts when they are not relevant any more for
752
# memory pressure reduction. RBC 20060313
753
# pb.update('Converting versioned data', 0, len(order))
755
for index, version in enumerate(order):
756
pb.update('Converting versioned data', index, total)
757
_, _, parent_text = target.add_lines(version,
758
self.source.get_parents(version),
759
self.source.get_lines(version),
760
parent_texts=parent_texts)
761
parent_texts[version] = parent_text
763
# this should hit the native code path for target
764
if target is not self.target:
765
return self.target.join(temp_source,
775
def _get_source_version_ids(self, version_ids, ignore_missing):
776
"""Determine the version ids to be used from self.source.
778
:param version_ids: The caller-supplied version ids to check. (None
779
for all). If None is in version_ids, it is stripped.
780
:param ignore_missing: if True, remove missing ids from the version
781
list. If False, raise RevisionNotPresent on
782
a missing version id.
783
:return: A set of version ids.
785
if version_ids is None:
786
# None cannot be in source.versions
787
return set(self.source.versions())
790
return set(self.source.versions()).intersection(set(version_ids))
792
new_version_ids = set()
793
for version in version_ids:
796
if not self.source.has_version(version):
797
raise errors.RevisionNotPresent(version, str(self.source))
799
new_version_ids.add(version)
800
return new_version_ids
added
removed
bzrlib/versionedfile.py
