22
22
"""Weave - storage of related text file versions"""
24
# before intset (r923) 2000 versions in 41.5s
25
# with intset (r926) 2000 versions in 93s !!!
26
# better to just use plain sets.
28
# making _extract build and return a list, rather than being a generator
31
# with python -O, r923 does 2000 versions in 36.87s
33
# with optimizations to avoid mutating lists - 35.75! I guess copying
34
# all the elements every time costs more than the small manipulations.
35
# a surprisingly small change.
37
# r931, which avoids using a generator for extract, does 36.98s
39
# with memoized inclusions, takes 41.49s; not very good
41
# with slots, takes 37.35s; without takes 39.16, a bit surprising
43
# with the delta calculation mixed in with the add method, rather than
44
# separated, takes 36.78s
46
# with delta folded in and mutation of the list, 36.13s
48
# with all this and simplification of add code, 33s
51
24
# TODO: Perhaps have copy method for Weave instances?
53
26
# XXX: If we do weaves this way, will a merge still behave the same
54
27
# way if it's done in a different order? That's a pretty desirable
30
# TODO: How to write these to disk? One option is cPickle, which
31
# would be fast but less friendly to C, and perhaps not portable. Another is
57
33
# TODO: Nothing here so far assumes the lines are really \n newlines,
58
34
# rather than being split up in some other way. We could accomodate
59
35
# binaries, perhaps by naively splitting on \n or perhaps using
60
36
# something like a rolling checksum.
38
# TODO: Perhaps track SHA-1 in the header for protection? This would
39
# be redundant with it being stored in the inventory, but perhaps
62
42
# TODO: Track version names as well as indexes.
44
# TODO: Probably do transitive expansion when specifying parents?
46
# TODO: Separate out some code to read and write weaves.
64
48
# TODO: End marker for each version so we can stop reading?
66
50
# TODO: Check that no insertion occurs inside a deletion that was
67
51
# active in the version of the insertion.
69
# TODO: In addition to the SHA-1 check, perhaps have some code that
70
# checks structural constraints of the weave: ie that insertions are
71
# properly nested, that there is no text outside of an insertion, that
72
# insertions or deletions are not repeated, etc.
74
# TODO: Parallel-extract that passes back each line along with a
75
# description of which revisions include it. Nice for checking all
53
# TODO: Perhaps a special slower check() method that verifies more
54
# nesting constraints and the MD5 of each version?
62
from sets import Set, ImmutableSet
64
frozenset = ImmutableSet
81
68
class WeaveError(Exception):
151
138
should be no way to get an earlier version deleting a later
155
Text of the weave; list of control instruction tuples and strings.
158
List of parents, indexed by version number.
159
It is only necessary to store the minimal set of parents for
160
each version; the parent's parents are implied.
145
List of versions, indexed by index number.
147
For each version we store the set (included_versions), which
148
lists the previous versions also considered active; the
149
versions included in those versions are included transitively.
150
So new versions created from nothing list []; most versions
151
have a single entry; some have more.
163
154
List of hex SHA-1 of each version, or None if not recorded.
166
__slots__ = ['_weave', '_parents', '_sha1s']
168
156
def __init__(self):
174
162
def __eq__(self, other):
175
163
if not isinstance(other, Weave):
177
return self._parents == other._parents \
178
and self._weave == other._weave
165
return self._v == other._v \
166
and self._l == other._l
181
169
def __ne__(self, other):
188
176
Returns the index number of the newly added version.
191
List or set of direct parent version numbers.
179
List or set of parent version numbers. This must normally include
180
the parents and the parent's parents, or wierd things might happen.
194
183
Sequence of lines to be added in the new version."""
196
self._check_versions(parents)
184
## self._check_versions(parents)
197
185
## self._check_lines(text)
198
new_version = len(self._parents)
203
192
sha1 = s.hexdigest()
206
# if we abort after here the weave will be corrupt
207
self._parents.append(frozenset(parents))
196
delta = self._delta(self.inclusions(parents), text)
198
# offset gives the number of lines that have been inserted
199
# into the weave up to the current point; if the original edit instruction
200
# says to change line A then we actually change (A+offset)
203
for i1, i2, newlines in delta:
206
assert i2 <= len(self._l)
208
# the deletion and insertion are handled separately.
209
# first delete the region.
211
self._l.insert(i1+offset, ('[', idx))
212
self._l.insert(i2+offset+1, (']', idx))
217
# there may have been a deletion spanning up to
218
# i2; we want to insert after this region to make sure
219
# we don't destroy ourselves
221
self._l[i:i] = [('{', idx)] \
224
offset += 2 + len(newlines)
226
self._addversion(parents)
228
# special case; adding with no parents revision; can do this
229
# more quickly by just appending unconditionally
230
self._l.append(('{', idx))
232
self._l.append(('}', idx))
234
self._addversion(None)
208
236
self._sha1s.append(sha1)
212
# special case; adding with no parents revision; can do
213
# this more quickly by just appending unconditionally.
214
# even more specially, if we're adding an empty text we
215
# need do nothing at all.
217
self._weave.append(('{', new_version))
218
self._weave.extend(text)
219
self._weave.append(('}', new_version))
223
if len(parents) == 1:
224
pv = list(parents)[0]
225
if sha1 == self._sha1s[pv]:
226
# special case: same as the single parent
230
ancestors = self.inclusions(parents)
234
# basis a list of (origin, lineno, line)
237
for origin, lineno, line in self._extract(ancestors):
238
basis_lineno.append(lineno)
239
basis_lines.append(line)
241
# another small special case: a merge, producing the same text as auto-merge
242
if text == basis_lines:
245
# add a sentinal, because we can also match against the final line
246
basis_lineno.append(len(self._weave))
248
# XXX: which line of the weave should we really consider
249
# matches the end of the file? the current code says it's the
250
# last line of the weave?
252
#print 'basis_lines:', basis_lines
253
#print 'new_lines: ', lines
255
from difflib import SequenceMatcher
256
s = SequenceMatcher(None, basis_lines, text)
258
# offset gives the number of lines that have been inserted
259
# into the weave up to the current point; if the original edit instruction
260
# says to change line A then we actually change (A+offset)
263
for tag, i1, i2, j1, j2 in s.get_opcodes():
264
# i1,i2 are given in offsets within basis_lines; we need to map them
265
# back to offsets within the entire weave
266
#print 'raw match', tag, i1, i2, j1, j2
270
i1 = basis_lineno[i1]
271
i2 = basis_lineno[i2]
273
assert 0 <= j1 <= j2 <= len(text)
275
#print tag, i1, i2, j1, j2
277
# the deletion and insertion are handled separately.
278
# first delete the region.
280
self._weave.insert(i1+offset, ('[', new_version))
281
self._weave.insert(i2+offset+1, (']', new_version))
285
# there may have been a deletion spanning up to
286
# i2; we want to insert after this region to make sure
287
# we don't destroy ourselves
289
self._weave[i:i] = ([('{', new_version)]
291
+ [('}', new_version)])
292
offset += 2 + (j2 - j1)
297
241
def inclusions(self, versions):
298
"""Return set of all ancestors of given version(s)."""
242
"""Expand out everything included by versions."""
299
243
i = set(versions)
304
# include all its parents
305
i.update(self._parents[v])
309
raise ValueError("version %d not present in weave" % v)
312
def minimal_parents(self, version):
313
"""Find the minimal set of parents for the version."""
314
included = self._parents[version]
319
li.sort(reverse=True)
327
gotit.update(self.inclusions(pv))
329
assert mininc[0] >= 0
330
assert mininc[-1] < version
248
raise ValueError("version %d not present in weave" % v)
252
def _addversion(self, parents):
254
self._v.append(frozenset(parents))
256
self._v.append(frozenset())
335
259
def _check_lines(self, text):
360
284
"""Yield list of (index-id, line) pairs for the specified version.
362
286
The index indicates when the line originated in the weave."""
363
for origin, lineno, text in self._extract([version]):
287
included = self.inclusions([version])
288
for origin, lineno, text in self._extract(included):
364
289
yield origin, text
371
(lineno, insert, deletes, text)
372
for each literal line.
378
lineno = 0 # line of weave, 0-based
380
for l in self._weave:
381
if isinstance(l, tuple):
394
raise WeaveFormatError('unexpected instruction %r'
397
assert isinstance(l, basestring)
399
yield lineno, istack[-1], dset, l
404
def _extract(self, versions):
292
def _extract(self, included):
405
293
"""Yield annotation of lines in included set.
407
295
Yields a sequence of tuples (origin, lineno, text), where
411
299
The set typically but not necessarily corresponds to a version.
413
included = self.inclusions(versions)
418
lineno = 0 # line of weave, 0-based
301
istack = [] # versions for which an insertion block is current
303
dset = set() # versions for which a deletion block is current
307
lineno = 0 # line of weave, 0-based
309
# TODO: Probably only need to put included revisions in the istack
311
# TODO: Could split this into two functions, one that updates
312
# the stack and the other that processes the results -- but
313
# I'm not sure it's really needed.
315
# TODO: In fact, I think we only need to store the *count* of
316
# active insertions and deletions, and we can maintain that by
317
# just by just counting as we go along.
424
319
WFE = WeaveFormatError
426
for l in self._weave:
427
322
if isinstance(l, tuple):
323
isactive = None # recalculate
431
assert v not in istack
326
if istack and (istack[-1] >= v):
327
raise WFE("improperly nested insertions %d>=%d on line %d"
328
% (istack[-1], v, lineno))
334
raise WFE("unmatched close of insertion %d on line %d"
337
raise WFE("mismatched close of insertion %d!=%d on line %d"
342
raise WFE("repeated deletion marker for version %d on line %d"
346
raise WFE("version %d deletes own text on line %d"
354
raise WFE("unmatched close of deletion %d on line %d"
357
raise WFE("invalid processing instruction %r on line %d"
446
360
assert isinstance(l, basestring)
448
isactive = (not dset) and istack and (istack[-1] in included)
362
raise WFE("literal at top level on line %d"
365
isactive = (istack[-1] in included) \
366
and not included.intersection(dset)
450
result.append((istack[-1], lineno, l))
369
yield origin, lineno, l
474
390
def mash_iter(self, included):
475
391
"""Return composed version of multiple included versions."""
392
included = frozenset(included)
476
393
for origin, lineno, text in self._extract(included):
480
397
def dump(self, to_file):
481
398
from pprint import pprint
482
print >>to_file, "Weave._weave = ",
483
pprint(self._weave, to_file)
484
print >>to_file, "Weave._parents = ",
485
pprint(self._parents, to_file)
399
print >>to_file, "Weave._l = ",
400
pprint(self._l, to_file)
401
print >>to_file, "Weave._v = ",
402
pprint(self._v, to_file)
489
406
def numversions(self):
490
l = len(self._parents)
491
408
assert l == len(self._sha1s)
496
return self.numversions()
499
def check(self, progress_bar=None):
500
413
# check no circular inclusions
501
414
for version in range(self.numversions()):
502
inclusions = list(self._parents[version])
415
inclusions = list(self._v[version])
504
417
inclusions.sort()
505
418
if inclusions[-1] >= version:
565
471
If line1=line2, this is a pure insert; if newlines=[] this is a
566
472
pure delete. (Similar to difflib.)
571
def plan_merge(self, ver_a, ver_b):
572
"""Return pseudo-annotation indicating how the two versions merge.
574
This is computed between versions a and b and their common
577
Weave lines present in none of them are skipped entirely.
579
inc_a = self.inclusions([ver_a])
580
inc_b = self.inclusions([ver_b])
581
inc_c = inc_a & inc_b
583
for lineno, insert, deleteset, line in self._walk():
584
if deleteset & inc_c:
585
# killed in parent; can't be in either a or b
586
# not relevant to our work
587
yield 'killed-base', line
588
elif insert in inc_c:
589
# was inserted in base
590
killed_a = bool(deleteset & inc_a)
591
killed_b = bool(deleteset & inc_b)
592
if killed_a and killed_b:
593
yield 'killed-both', line
595
yield 'killed-a', line
597
yield 'killed-b', line
599
yield 'unchanged', line
600
elif insert in inc_a:
601
if deleteset & inc_a:
602
yield 'ghost-a', line
606
elif insert in inc_b:
607
if deleteset & inc_b:
608
yield 'ghost-b', line
612
# not in either revision
613
yield 'irrelevant', line
615
yield 'unchanged', '' # terminator
619
def weave_merge(self, plan):
624
for state, line in plan:
625
if state == 'unchanged' or state == 'killed-both':
626
# resync and flush queued conflicts changes if any
627
if not lines_a and not lines_b:
629
elif ch_a and not ch_b:
631
for l in lines_a: yield l
632
elif ch_b and not ch_a:
633
for l in lines_b: yield l
634
elif lines_a == lines_b:
635
for l in lines_a: yield l
638
for l in lines_a: yield l
640
for l in lines_b: yield l
647
if state == 'unchanged':
650
elif state == 'killed-a':
653
elif state == 'killed-b':
656
elif state == 'new-a':
659
elif state == 'new-b':
663
assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
474
# basis a list of (origin, lineno, line)
477
for origin, lineno, line in self._extract(included):
478
basis_lineno.append(lineno)
479
basis_lines.append(line)
481
# add a sentinal, because we can also match against the final line
482
basis_lineno.append(len(self._l))
484
# XXX: which line of the weave should we really consider
485
# matches the end of the file? the current code says it's the
486
# last line of the weave?
488
from difflib import SequenceMatcher
489
s = SequenceMatcher(None, basis_lines, lines)
491
# TODO: Perhaps return line numbers from composed weave as well?
493
for tag, i1, i2, j1, j2 in s.get_opcodes():
494
##print tag, i1, i2, j1, j2
499
# i1,i2 are given in offsets within basis_lines; we need to map them
500
# back to offsets within the entire weave
501
real_i1 = basis_lineno[i1]
502
real_i2 = basis_lineno[i2]
506
assert j2 <= len(lines)
508
yield real_i1, real_i2, lines[j1:j2]
512
def weave_info(filename, out):
674
513
"""Show some text information about the weave."""
675
print '%6s %40s %20s' % ('ver', 'sha1', 'parents')
676
for i in (6, 40, 20):
679
for i in range(w.numversions()):
681
print '%6d %40s %s' % (i, sha1, ' '.join(map(str, w._parents[i])))
685
def weave_stats(weave_file):
686
from bzrlib.progress import ProgressBar
687
from bzrlib.weavefile import read_weave
691
wf = file(weave_file, 'rb')
514
from weavefile import read_weave
515
wf = file(filename, 'rb')
692
516
w = read_weave(wf)
693
517
# FIXME: doesn't work on pipes
694
518
weave_size = wf.tell()
519
print >>out, "weave file size %d bytes" % weave_size
520
print >>out, "weave contains %d versions" % len(w._v)
698
for i in range(vers):
699
pb.update('checking sizes', i, vers)
700
for line in w.get_iter(i):
705
print 'versions %9d' % vers
706
print 'weave file %9d bytes' % weave_size
707
print 'total contents %9d bytes' % total
708
print 'compression ratio %9.2fx' % (float(total) / float(weave_size))
523
print '%6s %6s %8s %40s %20s' % ('ver', 'lines', 'bytes', 'sha1', 'parents')
524
for i in (6, 6, 8, 40, 20):
527
for i in range(len(w._v)):
530
bytes = sum((len(a) for a in text))
532
print '%6d %6d %8d %40s' % (i, lines, bytes, sha1),
533
print ', '.join(map(str, w._v[i]))
536
print >>out, "versions total %d bytes" % total
537
print >>out, "compression ratio %.3f" % (float(total)/float(weave_size))