« back to all changes in this revision
Viewing changes to bzrlib/weave.py
- browse files at revision 970
- compare with another revision
- download diff
- download tarball
- view history from revision 970
- Committer: Martin Pool
- Date: 2005-07-23 13:52:38 UTC
- Revision ID: mbp@sourcefrog.net-20050723135238-96b1580de8dff136
doc
- files added:
- bzrlib/intset.py
- files modified:
- NEWS
added
removed
bzrlib/weave.py
21
21
22
22
"""Weave - storage of related text file versions"""
23
23
24
# before intset (r923) 2000 versions in 41.5s
25
# with intset (r926) 2000 versions in 93s !!!
26
# better to just use plain sets.
27
28
# making _extract build and return a list, rather than being a generator
29
# takes 37.94s
30
31
# with python -O, r923 does 2000 versions in 36.87s
32
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.
36
37
# r931, which avoids using a generator for extract, does 36.98s
38
39
# with memoized inclusions, takes 41.49s; not very good
40
41
# with slots, takes 37.35s; without takes 39.16, a bit surprising
42
43
# with the delta calculation mixed in with the add method, rather than
44
# separated, takes 36.78s
45
46
# with delta folded in and mutation of the list, 36.13s
47
48
# with all this and simplification of add code, 33s
49
50
24
51
# TODO: Perhaps have copy method for Weave instances?
25
52
26
53
# XXX: If we do weaves this way, will a merge still behave the same
27
54
# way if it's done in a different order? That's a pretty desirable
28
55
# property.
29
56
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
32
33
57
# TODO: Nothing here so far assumes the lines are really \n newlines,
34
58
# rather than being split up in some other way. We could accomodate
35
59
# binaries, perhaps by naively splitting on \n or perhaps using
36
60
# something like a rolling checksum.
37
61
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
40
# usefully so?
41
42
62
# TODO: Track version names as well as indexes.
43
63
44
# TODO: Probably do transitive expansion when specifying parents?
45
46
# TODO: Separate out some code to read and write weaves.
47
48
64
# TODO: End marker for each version so we can stop reading?
49
65
50
66
# TODO: Check that no insertion occurs inside a deletion that was
51
67
# active in the version of the insertion.
52
68
53
# TODO: Perhaps a special slower check() method that verifies more
54
# nesting constraints and the MD5 of each version?
55
56
57
58
try:
59
set
60
frozenset
61
except NameError:
62
from sets import Set, ImmutableSet
63
set = Set
64
frozenset = ImmutableSet
65
del Set, ImmutableSet
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.
73
74
# TODO: Parallel-extract that passes back each line along with a
75
# description of which revisions include it. Nice for checking all
76
# shas in parallel.
77
78
66
79
67
80
68
81
class WeaveError(Exception):
94
107
the version-id is used to reference it in the larger world.
95
108
96
109
The weave is represented as a list mixing edit instructions and
97
literal text. Each entry in _l can be either a string (or
110
literal text. Each entry in _weave can be either a string (or
98
111
unicode), or a tuple. If a string, it means that the given line
99
112
should be output in the currently active revisions.
100
113
138
151
should be no way to get an earlier version deleting a later
139
152
version.
140
153
141
_l
142
Text of the weave.
154
_weave
155
Text of the weave; list of control instruction tuples and strings.
143
156
144
_v
157
_parents
145
158
List of parents, indexed by version number.
146
159
It is only necessary to store the minimal set of parents for
147
160
each version; the parent's parents are implied.
149
162
_sha1s
150
163
List of hex SHA-1 of each version, or None if not recorded.
151
164
"""
165
166
__slots__ = ['_weave', '_parents', '_sha1s']
167
152
168
def __init__(self):
153
self._l = []
154
self._v = []
169
self._weave = []
170
self._parents = []
155
171
self._sha1s = []
156
172
157
173
158
174
def __eq__(self, other):
159
175
if not isinstance(other, Weave):
160
176
return False
161
return self._v == other._v \
162
and self._l == other._l
177
return self._parents == other._parents \
178
and self._weave == other._weave
163
179
164
180
165
181
def __ne__(self, other):
176
192
177
193
text
178
194
Sequence of lines to be added in the new version."""
179
## self._check_versions(parents)
195
196
self._check_versions(parents)
180
197
## self._check_lines(text)
181
idx = len(self._v)
198
new_version = len(self._parents)
182
199
183
200
import sha
184
201
s = sha.new()
185
for l in text:
186
s.update(l)
202
map(s.update, text)
187
203
sha1 = s.hexdigest()
188
204
del s
189
205
190
if parents:
191
ancestors = self.inclusions(parents)
192
delta = self._delta(ancestors, text)
193
194
# offset gives the number of lines that have been inserted
195
# into the weave up to the current point; if the original edit instruction
196
# says to change line A then we actually change (A+offset)
197
offset = 0
198
199
for i1, i2, newlines in delta:
200
assert 0 <= i1
201
assert i1 <= i2
202
assert i2 <= len(self._l)
203
204
# the deletion and insertion are handled separately.
205
# first delete the region.
206
if i1 != i2:
207
self._l.insert(i1+offset, ('[', idx))
208
self._l.insert(i2+offset+1, (']', idx))
209
offset += 2
210
# is this OK???
211
212
if newlines:
213
# there may have been a deletion spanning up to
214
# i2; we want to insert after this region to make sure
215
# we don't destroy ourselves
216
i = i2 + offset
217
self._l[i:i] = [('{', idx)] \
218
+ newlines \
219
+ [('}', idx)]
220
offset += 2 + len(newlines)
221
222
self._addversion(parents)
223
else:
224
# special case; adding with no parents revision; can do this
225
# more quickly by just appending unconditionally
226
self._l.append(('{', idx))
227
self._l += text
228
self._l.append(('}', idx))
229
230
self._addversion(None)
231
206
# if we abort after here the weave will be corrupt
207
self._parents.append(frozenset(parents))
232
208
self._sha1s.append(sha1)
233
234
return idx
209
210
211
if not parents:
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.
216
if text:
217
self._weave.append(('{', new_version))
218
self._weave.extend(text)
219
self._weave.append(('}', new_version))
220
221
return new_version
222
223
if len(parents) == 1:
224
pv = list(parents)[0]
225
if sha1 == self._sha1s[pv]:
226
# special case: same as the single parent
227
return new_version
228
229
230
ancestors = self.inclusions(parents)
231
232
l = self._weave
233
234
# basis a list of (origin, lineno, line)
235
basis_lineno = []
236
basis_lines = []
237
for origin, lineno, line in self._extract(ancestors):
238
basis_lineno.append(lineno)
239
basis_lines.append(line)
240
241
# another small special case: a merge, producing the same text as auto-merge
242
if text == basis_lines:
243
return new_version
244
245
# add a sentinal, because we can also match against the final line
246
basis_lineno.append(len(self._weave))
247
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?
251
252
#print 'basis_lines:', basis_lines
253
#print 'new_lines: ', lines
254
255
from difflib import SequenceMatcher
256
s = SequenceMatcher(None, basis_lines, text)
257
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)
261
offset = 0
262
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
267
if tag == 'equal':
268
continue
269
270
i1 = basis_lineno[i1]
271
i2 = basis_lineno[i2]
272
273
assert 0 <= j1 <= j2 <= len(text)
274
275
#print tag, i1, i2, j1, j2
276
277
# the deletion and insertion are handled separately.
278
# first delete the region.
279
if i1 != i2:
280
self._weave.insert(i1+offset, ('[', new_version))
281
self._weave.insert(i2+offset+1, (']', new_version))
282
offset += 2
283
284
if j1 != j2:
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
288
i = i2 + offset
289
self._weave[i:i] = ([('{', new_version)]
290
+ text[j1:j2]
291
+ [('}', new_version)])
292
offset += 2 + (j2 - j1)
293
294
return new_version
235
295
236
296
237
297
def inclusions(self, versions):
242
302
while v >= 0:
243
303
if v in i:
244
304
# include all its parents
245
i.update(self._v[v])
305
i.update(self._parents[v])
246
306
v -= 1
247
307
return i
248
308
except IndexError:
251
311
252
312
def minimal_parents(self, version):
253
313
"""Find the minimal set of parents for the version."""
254
included = self._v[version]
314
included = self._parents[version]
255
315
if not included:
256
316
return []
257
317
271
331
return mininc
272
332
273
333
274
def _addversion(self, parents):
275
if parents:
276
self._v.append(parents)
277
else:
278
self._v.append(frozenset())
279
280
334
281
335
def _check_lines(self, text):
282
336
if not isinstance(text, list):
293
347
"""Check everything in the sequence of indexes is valid"""
294
348
for i in indexes:
295
349
try:
296
self._v[i]
350
self._parents[i]
297
351
except IndexError:
298
352
raise IndexError("invalid version number %r" % i)
299
353
310
364
yield origin, text
311
365
312
366
367
def _walk(self):
368
"""Walk the weave.
369
370
Yields sequence of
371
(lineno, insert, deletes, text)
372
for each literal line.
373
"""
374
375
istack = []
376
dset = set()
377
378
lineno = 0 # line of weave, 0-based
379
380
for l in self._weave:
381
if isinstance(l, tuple):
382
c, v = l
383
isactive = None
384
if c == '{':
385
istack.append(v)
386
elif c == '}':
387
oldv = istack.pop()
388
elif c == '[':
389
assert v not in dset
390
dset.add(v)
391
elif c == ']':
392
dset.remove(v)
393
else:
394
raise WeaveFormatError('unexpected instruction %r'
395
% v)
396
else:
397
assert isinstance(l, basestring)
398
assert istack
399
yield lineno, istack[-1], dset, l
400
lineno += 1
401
402
403
313
404
def _extract(self, versions):
314
405
"""Yield annotation of lines in included set.
315
406
328
419
329
420
isactive = None
330
421
422
result = []
423
331
424
WFE = WeaveFormatError
332
425
333
for l in self._l:
426
for l in self._weave:
334
427
if isinstance(l, tuple):
335
428
c, v = l
336
429
isactive = None
354
447
if isactive is None:
355
448
isactive = (not dset) and istack and (istack[-1] in included)
356
449
if isactive:
357
yield istack[-1], lineno, l
450
result.append((istack[-1], lineno, l))
358
451
lineno += 1
359
452
360
453
if istack:
364
457
raise WFE("unclosed deletion blocks at end of weave",
365
458
dset)
366
459
460
return result
461
462
367
463
368
464
def get_iter(self, version):
369
465
"""Yield lines for the specified version."""
377
473
378
474
def mash_iter(self, included):
379
475
"""Return composed version of multiple included versions."""
380
included = frozenset(included)
381
476
for origin, lineno, text in self._extract(included):
382
477
yield text
383
478
384
479
385
480
def dump(self, to_file):
386
481
from pprint import pprint
387
print >>to_file, "Weave._l = ",
388
pprint(self._l, to_file)
389
print >>to_file, "Weave._v = ",
390
pprint(self._v, to_file)
482
print >>to_file, "Weave._weave = ",
483
pprint(self._weave, to_file)
484
print >>to_file, "Weave._parents = ",
485
pprint(self._parents, to_file)
391
486
392
487
393
488
394
489
def numversions(self):
395
l = len(self._v)
490
l = len(self._parents)
396
491
assert l == len(self._sha1s)
397
492
return l
398
493
399
494
495
def __len__(self):
496
return self.numversions()
497
498
400
499
def check(self, progress_bar=None):
401
500
# check no circular inclusions
402
501
for version in range(self.numversions()):
403
inclusions = list(self._v[version])
502
inclusions = list(self._parents[version])
404
503
if inclusions:
405
504
inclusions.sort()
406
505
if inclusions[-1] >= version:
466
565
If line1=line2, this is a pure insert; if newlines=[] this is a
467
566
pure delete. (Similar to difflib.)
468
567
"""
469
# basis a list of (origin, lineno, line)
470
basis_lineno = []
471
basis_lines = []
472
for origin, lineno, line in self._extract(included):
473
basis_lineno.append(lineno)
474
basis_lines.append(line)
475
476
# add a sentinal, because we can also match against the final line
477
basis_lineno.append(len(self._l))
478
479
# XXX: which line of the weave should we really consider
480
# matches the end of the file? the current code says it's the
481
# last line of the weave?
482
483
from difflib import SequenceMatcher
484
s = SequenceMatcher(None, basis_lines, lines)
485
486
# TODO: Perhaps return line numbers from composed weave as well?
487
488
for tag, i1, i2, j1, j2 in s.get_opcodes():
489
##print tag, i1, i2, j1, j2
490
491
if tag == 'equal':
492
continue
493
494
# i1,i2 are given in offsets within basis_lines; we need to map them
495
# back to offsets within the entire weave
496
real_i1 = basis_lineno[i1]
497
real_i2 = basis_lineno[i2]
498
499
assert 0 <= j1
500
assert j1 <= j2
501
assert j2 <= len(lines)
502
503
yield real_i1, real_i2, lines[j1:j2]
504
505
506
507
def weave_info(filename, out):
568
569
570
571
def plan_merge(self, ver_a, ver_b):
572
"""Return pseudo-annotation indicating how the two versions merge.
573
574
This is computed between versions a and b and their common
575
base.
576
577
Weave lines present in none of them are skipped entirely.
578
"""
579
inc_a = self.inclusions([ver_a])
580
inc_b = self.inclusions([ver_b])
581
inc_c = inc_a & inc_b
582
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
594
elif killed_a:
595
yield 'killed-a', line
596
elif killed_b:
597
yield 'killed-b', line
598
else:
599
yield 'unchanged', line
600
elif insert in inc_a:
601
if deleteset & inc_a:
602
yield 'ghost-a', line
603
else:
604
# new in A; not in B
605
yield 'new-a', line
606
elif insert in inc_b:
607
if deleteset & inc_b:
608
yield 'ghost-b', line
609
else:
610
yield 'new-b', line
611
else:
612
# not in either revision
613
yield 'irrelevant', line
614
615
yield 'unchanged', '' # terminator
616
617
618
619
def weave_merge(self, plan):
620
lines_a = []
621
lines_b = []
622
ch_a = ch_b = False
623
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:
628
pass
629
elif ch_a and not ch_b:
630
# one-sided change:
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
636
else:
637
yield '<<<<\n'
638
for l in lines_a: yield l
639
yield '====\n'
640
for l in lines_b: yield l
641
yield '>>>>\n'
642
643
del lines_a[:]
644
del lines_b[:]
645
ch_a = ch_b = False
646
647
if state == 'unchanged':
648
if line:
649
yield line
650
elif state == 'killed-a':
651
ch_a = True
652
lines_b.append(line)
653
elif state == 'killed-b':
654
ch_b = True
655
lines_a.append(line)
656
elif state == 'new-a':
657
ch_a = True
658
lines_a.append(line)
659
elif state == 'new-b':
660
ch_b = True
661
lines_b.append(line)
662
else:
663
assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
664
'killed-both'), \
665
state
666
667
668
669
670
671
672
673
def weave_info(w):
508
674
"""Show some text information about the weave."""
509
from weavefile import read_weave
510
wf = file(filename, 'rb')
675
print '%6s %40s %20s' % ('ver', 'sha1', 'parents')
676
for i in (6, 40, 20):
677
print '-' * i,
678
print
679
for i in range(w.numversions()):
680
sha1 = w._sha1s[i]
681
print '%6d %40s %s' % (i, sha1, ' '.join(map(str, w._parents[i])))
682
683
684
685
def weave_stats(weave_file):
686
from bzrlib.progress import ProgressBar
687
from bzrlib.weavefile import read_weave
688
689
pb = ProgressBar()
690
691
wf = file(weave_file, 'rb')
511
692
w = read_weave(wf)
512
693
# FIXME: doesn't work on pipes
513
694
weave_size = wf.tell()
514
print >>out, "weave file size %d bytes" % weave_size
515
print >>out, "weave contains %d versions" % len(w._v)
516
695
517
696
total = 0
518
print '%6s %6s %8s %40s %20s' % ('ver', 'lines', 'bytes', 'sha1', 'parents')
519
for i in (6, 6, 8, 40, 20):
520
print '-' * i,
521
print
522
for i in range(len(w._v)):
523
text = w.get(i)
524
lines = len(text)
525
bytes = sum((len(a) for a in text))
526
sha1 = w._sha1s[i]
527
print '%6d %6d %8d %40s' % (i, lines, bytes, sha1),
528
for pv in w._v[i]:
529
print pv,
530
print
531
total += bytes
532
533
print >>out, "versions total %d bytes" % total
534
print >>out, "compression ratio %.3f" % (float(total)/float(weave_size))
697
vers = len(w)
698
for i in range(vers):
699
pb.update('checking sizes', i, vers)
700
for line in w.get_iter(i):
701
total += len(line)
702
703
pb.clear()
704
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))
709
535
710
536
711
537
712
def usage():
635
810
lasto = origin
636
811
637
812
elif cmd == 'info':
638
weave_info(argv[2], sys.stdout)
813
weave_info(readit())
814
815
elif cmd == 'stats':
816
weave_stats(argv[2])
639
817
640
818
elif cmd == 'check':
641
819
w = readit()
642
820
pb = ProgressBar()
643
821
w.check(pb)
644
822
pb.clear()
823
print '%d versions ok' % w.numversions()
645
824
646
825
elif cmd == 'inclusions':
647
826
w = readit()
649
828
650
829
elif cmd == 'parents':
651
830
w = readit()
652
print ' '.join(map(str, w._v[int(argv[3])]))
831
print ' '.join(map(str, w._parents[int(argv[3])]))
832
833
elif cmd == 'plan-merge':
834
w = readit()
835
for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
836
if line:
837
print '%14s | %s' % (state, line),
653
838
654
839
elif cmd == 'merge':
840
w = readit()
841
p = w.plan_merge(int(argv[3]), int(argv[4]))
842
sys.stdout.writelines(w.weave_merge(p))
843
844
elif cmd == 'mash-merge':
655
845
if len(argv) != 5:
656
846
usage()
657
847
return 1
Loggerhead is a web-based interface for Breezy
Version: 2.0.1