67
67
# the possible relationships.
71
72
from difflib import SequenceMatcher
73
74
from bzrlib.trace import mutter
76
class WeaveError(Exception):
77
"""Exception in processing weave"""
80
class WeaveFormatError(WeaveError):
81
"""Weave invariant violated"""
84
class WeaveParentMismatch(WeaveError):
85
"""Parents are mismatched between two revisions."""
75
from bzrlib.errors import (WeaveError, WeaveFormatError, WeaveParentMismatch,
76
WeaveRevisionNotPresent, WeaveRevisionAlreadyPresent)
77
import bzrlib.errors as errors
78
from bzrlib.tsort import topo_sort
88
81
class Weave(object):
89
82
"""weave - versioned text file storage.
235
234
def idx_to_name(self, version):
236
235
return self._names[version]
239
237
def _check_repeated_add(self, name, parents, text, sha1):
240
238
"""Check that a duplicated add is OK.
242
240
If it is, return the (old) index; otherwise raise an exception.
244
242
idx = self.lookup(name)
245
if sorted(self._parents[idx]) != sorted(parents):
246
raise WeaveError("name \"%s\" already present in weave "
247
"with different parents" % name)
248
if sha1 != self._sha1s[idx]:
249
raise WeaveError("name \"%s\" already present in weave "
250
"with different text" % name)
243
if sorted(self._parents[idx]) != sorted(parents) \
244
or sha1 != self._sha1s[idx]:
245
raise WeaveRevisionAlreadyPresent(name, self)
255
248
def add(self, name, parents, text, sha1=None):
256
249
"""Add a single text on top of the weave.
489
raise WeaveFormatError('unexpected instruction %r'
481
raise WeaveFormatError('unexpected instruction %r' % v)
492
483
assert isinstance(l, basestring)
494
485
yield lineno, istack[-1], dset, l
489
raise WeaveFormatError("unclosed insertion blocks "
490
"at end of weave: %s" % istack)
492
raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
499
495
def _extract(self, versions):
500
496
"""Yield annotation of lines in included set.
548
544
result.append((istack[-1], lineno, l))
552
raise WFE("unclosed insertion blocks at end of weave",
547
raise WeaveFormatError("unclosed insertion blocks "
548
"at end of weave: %s" % istack)
555
raise WFE("unclosed deletion blocks at end of weave",
550
raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
562
555
def get_iter(self, name_or_index):
563
556
"""Yield lines for the specified version."""
564
557
incls = [self.maybe_lookup(name_or_index)]
562
# We don't have sha1 sums for multiple entries
565
564
for origin, lineno, line in self._extract(incls):
569
expected_sha1 = self._sha1s[index]
570
measured_sha1 = cur_sha.hexdigest()
571
if measured_sha1 != expected_sha1:
572
raise errors.WeaveInvalidChecksum(
573
'file %s, revision %s, expected: %s, measured %s'
574
% (self._weave_name, self._names[index],
575
expected_sha1, measured_sha1))
569
578
def get_text(self, name_or_index):
614
629
raise WeaveFormatError("invalid included version %d for index %d"
615
630
% (inclusions[-1], version))
617
# try extracting all versions; this is a bit slow and parallel
618
# extraction could be used
632
# try extracting all versions; parallel extraction is used
619
633
nv = self.numversions()
634
sha1s = [sha.new() for i in range(nv)]
635
texts = [[] for i in range(nv)]
638
# For creating the ancestry, IntSet is much faster (3.7s vs 0.17s)
639
# The problem is that set membership is much more expensive
641
for p in self._parents[i]:
642
new_inc.update(inclusions[p])
644
#assert set(new_inc) == self.inclusions([i]), 'failed %s != %s' % (new_inc, self.inclusions([i]))
645
inclusions.append(new_inc)
647
nlines = len(self._weave)
649
update_text = 'checking weave'
651
short_name = os.path.basename(self._weave_name)
652
update_text = 'checking %s' % (short_name,)
653
update_text = update_text[:25]
655
for lineno, insert, deleteset, line in self._walk():
657
progress_bar.update(update_text, lineno, nlines)
659
for j, j_inc in enumerate(inclusions):
660
# The active inclusion must be an ancestor,
661
# and no ancestors must have deleted this line,
662
# because we don't support resurrection.
663
if (insert in j_inc) and not (deleteset & j_inc):
664
sha1s[j].update(line)
620
666
for version in range(nv):
622
progress_bar.update('checking text', version, nv)
624
for l in self.get_iter(version):
667
hd = sha1s[version].hexdigest()
627
668
expected = self._sha1s[version]
628
669
if hd != expected:
629
raise WeaveError("mismatched sha1 for version %d; "
630
"got %s, expected %s"
631
% (version, hd, expected))
670
raise errors.WeaveInvalidChecksum(
671
"mismatched sha1 for version %s: "
672
"got %s, expected %s"
673
% (self._names[version], hd, expected))
633
675
# TODO: check insertions are properly nested, that there are
634
676
# no lines outside of insertion blocks, that deletions are
635
677
# properly paired, etc.
639
def merge(self, merge_versions):
640
"""Automerge and mark conflicts between versions.
642
This returns a sequence, each entry describing alternatives
643
for a chunk of the file. Each of the alternatives is given as
646
If there is a chunk of the file where there's no diagreement,
647
only one alternative is given.
649
# approach: find the included versions common to all the
651
raise NotImplementedError()
655
679
def _delta(self, included, lines):
656
680
"""Return changes from basis to new revision.
781
810
It is illegal for the two weaves to contain different values
782
811
or different parents for any version. See also reweave().
813
:param other: The other weave to pull into this one
814
:param pb: An optional progress bar
815
:param msg: An optional message to display for progress
784
817
if other.numversions() == 0:
785
818
return # nothing to update, easy
786
819
# two loops so that we do not change ourselves before verifying it
788
821
# work through in index order to make sure we get all dependencies
789
for other_idx, name in enumerate(other._names):
790
if self._check_version_consistent(other, other_idx, name):
792
for other_idx, name in enumerate(other._names):
793
# TODO: If all the parents of the other version are already
824
for other_idx, name in enumerate(other._names):
825
self._check_version_consistent(other, other_idx, name)
826
sha1 = other._sha1s[other_idx]
830
if name in self._name_map:
831
idx = self.lookup(name)
832
n1 = set(map(other.idx_to_name, other._parents[other_idx]))
833
n2 = set(map(self.idx_to_name, self._parents[idx]))
834
if sha1 == self._sha1s[idx] and n1 == n2:
837
names_to_join.append((other_idx, name))
844
for other_idx, name in names_to_join:
845
# TODO: If all the parents of the other version are already
794
846
# present then we can avoid some work by just taking the delta
795
847
# and adjusting the offsets.
796
848
new_parents = self._imported_parents(other, other_idx)
849
sha1 = other._sha1s[other_idx]
854
pb.update(msg, merged, len(names_to_join))
797
856
lines = other.get_lines(other_idx)
798
sha1 = other._sha1s[other_idx]
799
857
self.add(name, new_parents, lines, sha1)
859
mutter("merged = %d, processed = %d, file_id=%s; deltat=%d"%(
860
merged, processed, self._weave_name, time.time( )-time0))
802
862
def _imported_parents(self, other, other_idx):
803
863
"""Return list of parents in self corresponding to indexes in other."""
832
892
self_parents = self._parents[this_idx]
833
893
other_parents = other._parents[other_idx]
834
n1 = [self._names[i] for i in self_parents]
835
n2 = [other._names[i] for i in other_parents]
894
n1 = set([self._names[i] for i in self_parents])
895
n2 = set([other._names[i] for i in other_parents])
839
897
raise WeaveParentMismatch("inconsistent parents "
840
898
"for version {%s}: %s vs %s" % (name, n1, n2))
846
def reweave(self, other):
847
"""Reweave self with other."""
848
new_weave = reweave(self, other)
904
def reweave(self, other, pb=None, msg=None):
905
"""Reweave self with other.
907
:param other: The other weave to merge
908
:param pb: An optional progress bar, indicating how far done we are
909
:param msg: An optional message for the progress
911
new_weave = reweave(self, other, pb=pb, msg=msg)
849
912
for attr in self.__slots__:
850
913
setattr(self, attr, getattr(new_weave, attr))
916
def reweave(wa, wb, pb=None, msg=None):
854
917
"""Combine two weaves and return the result.
856
919
This works even if a revision R has different parents in
870
936
# map from version name -> all parent names
871
937
combined_parents = _reweave_parent_graphs(wa, wb)
872
938
mutter("combined parents: %r", combined_parents)
873
order = _make_reweave_order(wa._names, wb._names, combined_parents)
939
order = topo_sort(combined_parents.iteritems())
874
940
mutter("order to reweave: %r", order)
945
for idx, name in enumerate(order):
947
pb.update(msg, idx, len(order))
876
948
if name in wa._name_map:
877
949
lines = wa.get_lines(name)
878
950
if name in wb._name_map:
879
assert lines == wb.get_lines(name)
951
lines_b = wb.get_lines(name)
953
mutter('Weaves differ on content. rev_id {%s}', name)
954
mutter('weaves: %s, %s', wa._weave_name, wb._weave_name)
956
lines = list(difflib.unified_diff(lines, lines_b,
957
wa._weave_name, wb._weave_name))
958
mutter('lines:\n%s', ''.join(lines))
959
raise errors.WeaveTextDiffers(name, wa, wb)
881
961
lines = wb.get_lines(name)
882
962
wr.add(name, combined_parents[name], lines)
898
def _make_reweave_order(wa_order, wb_order, combined_parents):
899
"""Return an order to reweave versions respecting parents."""
903
next_a = next_b = None
904
len_a = len(wa_order)
905
len_b = len(wb_order)
906
while ia < len(wa_order) or ib < len(wb_order):
908
next_a = wa_order[ia]
912
if combined_parents[next_a].issubset(done):
914
result.append(next_a)
918
next_b = wb_order[ib]
922
elif combined_parents[next_b].issubset(done):
924
result.append(next_b)
927
raise WeaveError("don't know how to reweave at {%s} and {%s}"
932
978
def weave_toc(w):
933
979
"""Show the weave's table-of-contents"""
934
980
print '%6s %50s %10s %10s' % ('ver', 'name', 'sha1', 'parents')
1224
def lsprofile_main(argv):
1225
from bzrlib.lsprof import profile
1226
ret,stats = profile(main, argv)
1178
1232
if __name__ == '__main__':
1180
1234
if '--profile' in sys.argv:
1181
1235
args = sys.argv[:]
1182
1236
args.remove('--profile')
1183
1237
sys.exit(profile_main(args))
1238
elif '--lsprof' in sys.argv:
1240
args.remove('--lsprof')
1241
sys.exit(lsprofile_main(args))
1185
1243
sys.exit(main(sys.argv))
added
removed
bzrlib/weave.py
