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.
788
817
# work through in index order to make sure we get all dependencies
789
818
for other_idx, name in enumerate(other._names):
790
if self._check_version_consistent(other, other_idx, name):
819
self._check_version_consistent(other, other_idx, name)
792
824
for other_idx, name in enumerate(other._names):
793
# TODO: If all the parents of the other version are already
825
# TODO: If all the parents of the other version are already
794
826
# present then we can avoid some work by just taking the delta
795
827
# and adjusting the offsets.
796
828
new_parents = self._imported_parents(other, other_idx)
829
sha1 = other._sha1s[other_idx]
833
if name in self._names:
834
idx = self.lookup(name)
835
n1 = map(other.idx_to_name, other._parents[other_idx] )
836
n2 = map(self.idx_to_name, self._parents[other_idx] )
837
if sha1 == self._sha1s[idx] and n1 == n2:
797
841
lines = other.get_lines(other_idx)
798
sha1 = other._sha1s[other_idx]
799
842
self.add(name, new_parents, lines, sha1)
844
mutter("merged = %d, processed = %d, file_id=%s; deltat=%d"%(
845
merged,processed,self._weave_name, time.time( )-time0))
802
850
def _imported_parents(self, other, other_idx):
803
851
"""Return list of parents in self corresponding to indexes in other."""
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
946
def weave_toc(w):
933
947
"""Show the weave's table-of-contents"""
934
948
print '%6s %50s %10s %10s' % ('ver', 'name', 'sha1', 'parents')
1192
def lsprofile_main(argv):
1193
from bzrlib.lsprof import profile
1194
ret,stats = profile(main, argv)
1178
1200
if __name__ == '__main__':
1180
1202
if '--profile' in sys.argv:
1181
1203
args = sys.argv[:]
1182
1204
args.remove('--profile')
1183
1205
sys.exit(profile_main(args))
1206
elif '--lsprof' in sys.argv:
1208
args.remove('--lsprof')
1209
sys.exit(lsprofile_main(args))
1185
1211
sys.exit(main(sys.argv))
added
removed
bzrlib/weave.py
