220
208
return self._parents == other._parents \
221
209
and self._weave == other._weave \
222
210
and self._sha1s == other._sha1s
224
213
def __ne__(self, other):
225
214
return not self.__eq__(other)
227
def _idx_to_name(self, version):
228
return self._names[version]
230
def _lookup(self, name):
231
"""Convert symbolic version name to index."""
232
self.check_not_reserved_id(name)
217
def lookup(self, name):
234
219
return self._name_map[name]
236
raise RevisionNotPresent(name, self._weave_name)
239
"""See VersionedFile.versions."""
240
return self._names[:]
242
def has_version(self, version_id):
243
"""See VersionedFile.has_version."""
244
return (version_id in self._name_map)
246
__contains__ = has_version
248
def get_parents(self, version_id):
249
"""See VersionedFile.get_parent."""
250
return map(self._idx_to_name, self._parents[self._lookup(version_id)])
252
def _check_repeated_add(self, name, parents, text, sha1):
221
raise WeaveError("name %s not present in weave %s" %
222
(name, self._weave_name))
225
def idx_to_name(self, version):
226
return self._names[version]
229
def _check_repeated_add(self, name, parents, text):
253
230
"""Check that a duplicated add is OK.
255
232
If it is, return the (old) index; otherwise raise an exception.
257
idx = self._lookup(name)
258
if sorted(self._parents[idx]) != sorted(parents) \
259
or sha1 != self._sha1s[idx]:
260
raise RevisionAlreadyPresent(name, self._weave_name)
234
idx = self.lookup(name)
235
if sorted(self._parents[idx]) != sorted(parents):
236
raise WeaveError("name \"%s\" already present in weave "
237
"with different parents" % name)
238
new_sha1 = sha_strings(text)
239
if new_sha1 != self._sha1s[idx]:
240
raise WeaveError("name \"%s\" already present in weave "
241
"with different text" % name)
263
def _add_lines(self, version_id, parents, lines, parent_texts,
264
left_matching_blocks, nostore_sha, random_id, check_content):
265
"""See VersionedFile.add_lines."""
266
idx = self._add(version_id, lines, map(self._lookup, parents),
267
nostore_sha=nostore_sha)
268
return sha_strings(lines), sum(map(len, lines)), idx
270
def _add(self, version_id, lines, parents, sha1=None, nostore_sha=None):
246
def add(self, name, parents, text):
271
247
"""Add a single text on top of the weave.
273
249
Returns the index number of the newly added version.
276
252
Symbolic name for this version.
277
253
(Typically the revision-id of the revision that added it.)
280
256
List or set of direct parent version numbers.
283
Sequence of lines to be added in the new version.
285
:param nostore_sha: See VersionedFile.add_lines.
287
assert isinstance(version_id, basestring)
288
self._check_lines_not_unicode(lines)
289
self._check_lines_are_lines(lines)
291
sha1 = sha_strings(lines)
292
if sha1 == nostore_sha:
293
raise errors.ExistingContent
294
if version_id in self._name_map:
295
return self._check_repeated_add(version_id, parents, lines, sha1)
259
Sequence of lines to be added in the new version."""
261
assert isinstance(name, basestring)
262
if name in self._name_map:
263
return self._check_repeated_add(name, parents, text)
297
265
self._check_versions(parents)
298
## self._check_lines(lines)
266
## self._check_lines(text)
299
267
new_version = len(self._parents)
269
sha1 = sha_strings(text)
301
271
# if we abort after here the (in-memory) weave will be corrupt because only
302
272
# some fields are updated
303
# XXX: FIXME implement a succeed-or-fail of the rest of this routine.
304
# - Robert Collins 20060226
305
273
self._parents.append(parents[:])
306
274
self._sha1s.append(sha1)
307
self._names.append(version_id)
308
self._name_map[version_id] = new_version
275
self._names.append(name)
276
self._name_map[name] = new_version
626
assert l.__class__ in (str, unicode)
522
assert isinstance(l, basestring)
627
523
if isactive is None:
628
524
isactive = (not dset) and istack and (istack[-1] in included)
630
526
result.append((istack[-1], lineno, l))
633
raise WeaveFormatError("unclosed insertion blocks "
634
"at end of weave: %s" % istack)
530
raise WFE("unclosed insertion blocks at end of weave",
636
raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
640
def _maybe_lookup(self, name_or_index):
641
"""Convert possible symbolic name to index, or pass through indexes.
645
if isinstance(name_or_index, (int, long)):
648
return self._lookup(name_or_index)
650
def get_lines(self, version_id):
651
"""See VersionedFile.get_lines()."""
652
int_index = self._maybe_lookup(version_id)
653
result = [line for (origin, lineno, line) in self._extract([int_index])]
654
expected_sha1 = self._sha1s[int_index]
655
measured_sha1 = sha_strings(result)
656
if measured_sha1 != expected_sha1:
657
raise errors.WeaveInvalidChecksum(
658
'file %s, revision %s, expected: %s, measured %s'
659
% (self._weave_name, version_id,
660
expected_sha1, measured_sha1))
663
def get_sha1(self, version_id):
664
"""See VersionedFile.get_sha1()."""
665
return self._sha1s[self._lookup(version_id)]
667
def get_sha1s(self, version_ids):
668
"""See VersionedFile.get_sha1s()."""
669
return [self._sha1s[self._lookup(v)] for v in version_ids]
671
def num_versions(self):
672
"""How many versions are in this weave?"""
533
raise WFE("unclosed deletion blocks at end of weave",
540
def get_iter(self, version):
541
"""Yield lines for the specified version."""
542
for origin, lineno, line in self._extract([version]):
546
def get_text(self, version):
547
assert isinstance(version, int)
549
s.writelines(self.get_iter(version))
553
def get(self, index):
554
return list(self.get_iter(index))
557
def mash_iter(self, included):
558
"""Return composed version of multiple included versions."""
559
for origin, lineno, text in self._extract(included):
563
def dump(self, to_file):
564
from pprint import pprint
565
print >>to_file, "Weave._weave = ",
566
pprint(self._weave, to_file)
567
print >>to_file, "Weave._parents = ",
568
pprint(self._parents, to_file)
572
def numversions(self):
673
573
l = len(self._parents)
674
574
assert l == len(self._sha1s)
677
__len__ = num_versions
579
return self.numversions()
679
582
def check(self, progress_bar=None):
680
# TODO evaluate performance hit of using string sets in this routine.
681
# TODO: check no circular inclusions
682
# TODO: create a nested progress bar
683
for version in range(self.num_versions()):
583
# check no circular inclusions
584
for version in range(self.numversions()):
684
585
inclusions = list(self._parents[version])
686
587
inclusions.sort()
688
589
raise WeaveFormatError("invalid included version %d for index %d"
689
590
% (inclusions[-1], version))
691
# try extracting all versions; parallel extraction is used
692
nv = self.num_versions()
697
# For creating the ancestry, IntSet is much faster (3.7s vs 0.17s)
698
# The problem is that set membership is much more expensive
699
name = self._idx_to_name(i)
700
sha1s[name] = sha.new()
702
new_inc = set([name])
703
for p in self._parents[i]:
704
new_inc.update(inclusions[self._idx_to_name(p)])
706
assert set(new_inc) == set(self.get_ancestry(name)), \
707
'failed %s != %s' % (set(new_inc), set(self.get_ancestry(name)))
708
inclusions[name] = new_inc
710
nlines = len(self._weave)
712
update_text = 'checking weave'
714
short_name = os.path.basename(self._weave_name)
715
update_text = 'checking %s' % (short_name,)
716
update_text = update_text[:25]
718
for lineno, insert, deleteset, line in self._walk_internal():
592
# try extracting all versions; this is a bit slow and parallel
593
# extraction could be used
594
nv = self.numversions()
595
for version in range(nv):
720
progress_bar.update(update_text, lineno, nlines)
722
for name, name_inclusions in inclusions.items():
723
# The active inclusion must be an ancestor,
724
# and no ancestors must have deleted this line,
725
# because we don't support resurrection.
726
if (insert in name_inclusions) and not (deleteset & name_inclusions):
727
sha1s[name].update(line)
730
version = self._idx_to_name(i)
731
hd = sha1s[version].hexdigest()
732
expected = self._sha1s[i]
597
progress_bar.update('checking text', version, nv)
599
for l in self.get_iter(version):
602
expected = self._sha1s[version]
733
603
if hd != expected:
734
raise errors.WeaveInvalidChecksum(
735
"mismatched sha1 for version %s: "
736
"got %s, expected %s"
737
% (version, hd, expected))
604
raise WeaveError("mismatched sha1 for version %d; "
605
"got %s, expected %s"
606
% (version, hd, expected))
739
608
# TODO: check insertions are properly nested, that there are
740
609
# no lines outside of insertion blocks, that deletions are
741
610
# properly paired, etc.
743
def _join(self, other, pb, msg, version_ids, ignore_missing):
744
"""Worker routine for join()."""
745
if not other.versions():
746
return # nothing to update, easy
749
# versions is never none, InterWeave checks this.
752
# two loops so that we do not change ourselves before verifying it
754
# work through in index order to make sure we get all dependencies
757
# get the selected versions only that are in other.versions.
758
version_ids = set(other.versions()).intersection(set(version_ids))
759
# pull in the referenced graph.
760
version_ids = other.get_ancestry(version_ids)
761
pending_graph = [(version, other.get_parents(version)) for
762
version in version_ids]
763
for name in topo_sort(pending_graph):
764
other_idx = other._name_map[name]
765
# returns True if we have it, False if we need it.
766
if not self._check_version_consistent(other, other_idx, name):
767
names_to_join.append((other_idx, name))
776
for other_idx, name in names_to_join:
777
# TODO: If all the parents of the other version are already
778
# present then we can avoid some work by just taking the delta
779
# and adjusting the offsets.
780
new_parents = self._imported_parents(other, other_idx)
781
sha1 = other._sha1s[other_idx]
786
pb.update(msg, merged, len(names_to_join))
788
lines = other.get_lines(other_idx)
789
self._add(name, lines, new_parents, sha1)
791
mutter("merged = %d, processed = %d, file_id=%s; deltat=%d"%(
792
merged, processed, self._weave_name, time.time()-time0))
794
def _imported_parents(self, other, other_idx):
795
"""Return list of parents in self corresponding to indexes in other."""
797
for parent_idx in other._parents[other_idx]:
798
parent_name = other._names[parent_idx]
799
if parent_name not in self._name_map:
800
# should not be possible
801
raise WeaveError("missing parent {%s} of {%s} in %r"
802
% (parent_name, other._name_map[other_idx], self))
803
new_parents.append(self._name_map[parent_name])
806
def _check_version_consistent(self, other, other_idx, name):
807
"""Check if a version in consistent in this and other.
809
To be consistent it must have:
812
* the same direct parents (by name, not index, and disregarding
815
If present & correct return True;
816
if not present in self return False;
817
if inconsistent raise error."""
818
this_idx = self._name_map.get(name, -1)
820
if self._sha1s[this_idx] != other._sha1s[other_idx]:
821
raise errors.WeaveTextDiffers(name, self, other)
822
self_parents = self._parents[this_idx]
823
other_parents = other._parents[other_idx]
824
n1 = set([self._names[i] for i in self_parents])
825
n2 = set([other._names[i] for i in other_parents])
826
if not self._compatible_parents(n1, n2):
827
raise WeaveParentMismatch("inconsistent parents "
828
"for version {%s}: %s vs %s" % (name, n1, n2))
834
def _reweave(self, other, pb, msg):
835
"""Reweave self with other - internal helper for join().
837
:param other: The other weave to merge
838
:param pb: An optional progress bar, indicating how far done we are
839
:param msg: An optional message for the progress
841
new_weave = _reweave(self, other, pb=pb, msg=msg)
842
self._copy_weave_content(new_weave)
844
def _copy_weave_content(self, otherweave):
845
"""adsorb the content from otherweave."""
846
for attr in self.__slots__:
847
if attr != '_weave_name':
848
setattr(self, attr, copy(getattr(otherweave, attr)))
851
class WeaveFile(Weave):
852
"""A WeaveFile represents a Weave on disk and writes on change."""
854
WEAVE_SUFFIX = '.weave'
856
def __init__(self, name, transport, filemode=None, create=False, access_mode='w'):
857
"""Create a WeaveFile.
859
:param create: If not True, only open an existing knit.
861
super(WeaveFile, self).__init__(name, access_mode)
862
self._transport = transport
863
self._filemode = filemode
865
_read_weave_v5(self._transport.get(name + WeaveFile.WEAVE_SUFFIX), self)
866
except errors.NoSuchFile:
872
def _add_lines(self, version_id, parents, lines, parent_texts,
873
left_matching_blocks, nostore_sha, random_id, check_content):
874
"""Add a version and save the weave."""
875
self.check_not_reserved_id(version_id)
876
result = super(WeaveFile, self)._add_lines(version_id, parents, lines,
877
parent_texts, left_matching_blocks, nostore_sha, random_id,
882
def _clone_text(self, new_version_id, old_version_id, parents):
883
"""See VersionedFile.clone_text."""
884
super(WeaveFile, self)._clone_text(new_version_id, old_version_id, parents)
887
def copy_to(self, name, transport):
888
"""See VersionedFile.copy_to()."""
889
# as we are all in memory always, just serialise to the new place.
891
write_weave_v5(self, sio)
893
transport.put_file(name + WeaveFile.WEAVE_SUFFIX, sio, self._filemode)
895
def create_empty(self, name, transport, filemode=None):
896
return WeaveFile(name, transport, filemode, create=True)
899
"""Save the weave."""
900
self._check_write_ok()
902
write_weave_v5(self, sio)
904
self._transport.put_file(self._weave_name + WeaveFile.WEAVE_SUFFIX,
910
"""See VersionedFile.get_suffixes()."""
911
return [WeaveFile.WEAVE_SUFFIX]
913
def join(self, other, pb=None, msg=None, version_ids=None,
914
ignore_missing=False):
915
"""Join other into self and save."""
916
super(WeaveFile, self).join(other, pb, msg, version_ids, ignore_missing)
920
def _reweave(wa, wb, pb=None, msg=None):
921
"""Combine two weaves and return the result.
923
This works even if a revision R has different parents in
924
wa and wb. In the resulting weave all the parents are given.
926
This is done by just building up a new weave, maintaining ordering
927
of the versions in the two inputs. More efficient approaches
928
might be possible but it should only be necessary to do
929
this operation rarely, when a new previously ghost version is
932
:param pb: An optional progress bar, indicating how far done we are
933
:param msg: An optional message for the progress
937
queue_a = range(wa.num_versions())
938
queue_b = range(wb.num_versions())
939
# first determine combined parents of all versions
940
# map from version name -> all parent names
941
combined_parents = _reweave_parent_graphs(wa, wb)
942
mutter("combined parents: %r", combined_parents)
943
order = topo_sort(combined_parents.iteritems())
944
mutter("order to reweave: %r", order)
949
for idx, name in enumerate(order):
951
pb.update(msg, idx, len(order))
952
if name in wa._name_map:
953
lines = wa.get_lines(name)
954
if name in wb._name_map:
955
lines_b = wb.get_lines(name)
957
mutter('Weaves differ on content. rev_id {%s}', name)
958
mutter('weaves: %s, %s', wa._weave_name, wb._weave_name)
960
lines = list(difflib.unified_diff(lines, lines_b,
961
wa._weave_name, wb._weave_name))
962
mutter('lines:\n%s', ''.join(lines))
963
raise errors.WeaveTextDiffers(name, wa, wb)
965
lines = wb.get_lines(name)
966
wr._add(name, lines, [wr._lookup(i) for i in combined_parents[name]])
969
def _reweave_parent_graphs(wa, wb):
970
"""Return combined parent ancestry for two weaves.
972
Returned as a list of (version_name, set(parent_names))"""
974
for weave in [wa, wb]:
975
for idx, name in enumerate(weave._names):
976
p = combined.setdefault(name, set())
977
p.update(map(weave._idx_to_name, weave._parents[idx]))
614
def merge(self, merge_versions):
615
"""Automerge and mark conflicts between versions.
617
This returns a sequence, each entry describing alternatives
618
for a chunk of the file. Each of the alternatives is given as
621
If there is a chunk of the file where there's no diagreement,
622
only one alternative is given.
625
# approach: find the included versions common to all the
627
raise NotImplementedError()
631
def _delta(self, included, lines):
632
"""Return changes from basis to new revision.
634
The old text for comparison is the union of included revisions.
636
This is used in inserting a new text.
638
Delta is returned as a sequence of
639
(weave1, weave2, newlines).
641
This indicates that weave1:weave2 of the old weave should be
642
replaced by the sequence of lines in newlines. Note that
643
these line numbers are positions in the total weave and don't
644
correspond to the lines in any extracted version, or even the
645
extracted union of included versions.
647
If line1=line2, this is a pure insert; if newlines=[] this is a
648
pure delete. (Similar to difflib.)
653
def plan_merge(self, ver_a, ver_b):
654
"""Return pseudo-annotation indicating how the two versions merge.
656
This is computed between versions a and b and their common
659
Weave lines present in none of them are skipped entirely.
661
inc_a = self.inclusions([ver_a])
662
inc_b = self.inclusions([ver_b])
663
inc_c = inc_a & inc_b
665
for lineno, insert, deleteset, line in self._walk():
666
if deleteset & inc_c:
667
# killed in parent; can't be in either a or b
668
# not relevant to our work
669
yield 'killed-base', line
670
elif insert in inc_c:
671
# was inserted in base
672
killed_a = bool(deleteset & inc_a)
673
killed_b = bool(deleteset & inc_b)
674
if killed_a and killed_b:
675
yield 'killed-both', line
677
yield 'killed-a', line
679
yield 'killed-b', line
681
yield 'unchanged', line
682
elif insert in inc_a:
683
if deleteset & inc_a:
684
yield 'ghost-a', line
688
elif insert in inc_b:
689
if deleteset & inc_b:
690
yield 'ghost-b', line
694
# not in either revision
695
yield 'irrelevant', line
697
yield 'unchanged', '' # terminator
701
def weave_merge(self, plan):
706
for state, line in plan:
707
if state == 'unchanged' or state == 'killed-both':
708
# resync and flush queued conflicts changes if any
709
if not lines_a and not lines_b:
711
elif ch_a and not ch_b:
713
for l in lines_a: yield l
714
elif ch_b and not ch_a:
715
for l in lines_b: yield l
716
elif lines_a == lines_b:
717
for l in lines_a: yield l
720
for l in lines_a: yield l
722
for l in lines_b: yield l
729
if state == 'unchanged':
732
elif state == 'killed-a':
735
elif state == 'killed-b':
738
elif state == 'new-a':
741
elif state == 'new-b':
745
assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
981
755
def weave_toc(w):
1162
926
print ' '.join(map(str, w._parents[int(argv[3])]))
1164
928
elif cmd == 'plan-merge':
1165
# replaced by 'bzr weave-plan-merge'
1167
930
for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
1169
932
print '%14s | %s' % (state, line),
1170
934
elif cmd == 'merge':
1171
# replaced by 'bzr weave-merge-text'
1173
936
p = w.plan_merge(int(argv[3]), int(argv[4]))
1174
937
sys.stdout.writelines(w.weave_merge(p))
939
elif cmd == 'mash-merge':
945
v1, v2 = map(int, argv[3:5])
947
basis = w.inclusions([v1]).intersection(w.inclusions([v2]))
949
base_lines = list(w.mash_iter(basis))
950
a_lines = list(w.get(v1))
951
b_lines = list(w.get(v2))
953
from bzrlib.merge3 import Merge3
954
m3 = Merge3(base_lines, a_lines, b_lines)
956
name_a = 'version %d' % v1
957
name_b = 'version %d' % v2
958
sys.stdout.writelines(m3.merge_lines(name_a=name_a, name_b=name_b))
1176
960
raise ValueError('unknown command %r' % cmd)
964
def profile_main(argv):
965
import tempfile, hotshot, hotshot.stats
967
prof_f = tempfile.NamedTemporaryFile()
969
prof = hotshot.Profile(prof_f.name)
971
ret = prof.runcall(main, argv)
974
stats = hotshot.stats.load(prof_f.name)
976
stats.sort_stats('cumulative')
977
## XXX: Might like to write to stderr or the trace file instead but
978
## print_stats seems hardcoded to stdout
979
stats.print_stats(20)
1179
984
if __name__ == '__main__':
1181
sys.exit(main(sys.argv))
1184
class InterWeave(InterVersionedFile):
1185
"""Optimised code paths for weave to weave operations."""
1187
_matching_file_from_factory = staticmethod(WeaveFile)
1188
_matching_file_to_factory = staticmethod(WeaveFile)
1191
def is_compatible(source, target):
1192
"""Be compatible with weaves."""
1194
return (isinstance(source, Weave) and
1195
isinstance(target, Weave))
1196
except AttributeError:
1199
def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
1200
"""See InterVersionedFile.join."""
1201
version_ids = self._get_source_version_ids(version_ids, ignore_missing)
1202
if self.target.versions() == [] and version_ids is None:
1203
self.target._copy_weave_content(self.source)
1205
self.target._join(self.source, pb, msg, version_ids, ignore_missing)
1208
InterVersionedFile.register_optimiser(InterWeave)
986
if '--profile' in sys.argv:
988
args.remove('--profile')
989
sys.exit(profile_main(args))
991
sys.exit(main(sys.argv))
added
removed
bzrlib/weave.py
