« back to all changes in this revision
Viewing changes to bzrlib/weave.py
- browse files at revision 915
- compare with another revision
- download diff
- download tarball
- view history from revision 915
- Committer: Martin Pool
- Date: 2005-07-12 01:44:23 UTC
- Revision ID: mbp@sourcefrog.net-20050712014423-1d95eb47ce7ab510
- add simple test case for bzr status
- show_status takes to_file argument
- show_status takes to_file argument
- files added:
- plugins/changeset
- files removed:
- HACKING
- bzrlib/util
- contrib/emacs
- files renamed:
- bzrlib/util/effbot/ => effbot/
- bzrlib/util/elementtree/ => elementtree/
- bzrlib/plugins/ => plugins/
- bzrlib/util/urlgrabber/ => urlgrabber/
- files modified:
- .bzrignore
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
51
24
# TODO: Perhaps have copy method for Weave instances?
52
25
53
26
# XXX: If we do weaves this way, will a merge still behave the same
71
44
# properly nested, that there is no text outside of an insertion, that
72
45
# insertions or deletions are not repeated, etc.
73
46
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
47
48
49
try:
50
set
51
frozenset
52
except NameError:
53
from sets import Set, ImmutableSet
54
set = Set
55
frozenset = ImmutableSet
56
del Set, ImmutableSet
79
57
80
58
81
59
class WeaveError(Exception):
107
85
the version-id is used to reference it in the larger world.
108
86
109
87
The weave is represented as a list mixing edit instructions and
110
literal text. Each entry in _weave can be either a string (or
88
literal text. Each entry in _l can be either a string (or
111
89
unicode), or a tuple. If a string, it means that the given line
112
90
should be output in the currently active revisions.
113
91
151
129
should be no way to get an earlier version deleting a later
152
130
version.
153
131
154
_weave
155
Text of the weave; list of control instruction tuples and strings.
132
_l
133
Text of the weave.
156
134
157
_parents
135
_v
158
136
List of parents, indexed by version number.
159
137
It is only necessary to store the minimal set of parents for
160
138
each version; the parent's parents are implied.
162
140
_sha1s
163
141
List of hex SHA-1 of each version, or None if not recorded.
164
142
"""
165
166
__slots__ = ['_weave', '_parents', '_sha1s']
167
168
143
def __init__(self):
169
self._weave = []
170
self._parents = []
144
self._l = []
145
self._v = []
171
146
self._sha1s = []
172
147
173
148
174
149
def __eq__(self, other):
175
150
if not isinstance(other, Weave):
176
151
return False
177
return self._parents == other._parents \
178
and self._weave == other._weave
152
return self._v == other._v \
153
and self._l == other._l
179
154
180
155
181
156
def __ne__(self, other):
192
167
193
168
text
194
169
Sequence of lines to be added in the new version."""
195
196
self._check_versions(parents)
170
## self._check_versions(parents)
197
171
## self._check_lines(text)
198
new_version = len(self._parents)
172
idx = len(self._v)
199
173
200
174
import sha
201
175
s = sha.new()
202
map(s.update, text)
176
for l in text:
177
s.update(l)
203
178
sha1 = s.hexdigest()
204
179
del s
205
180
206
# if we abort after here the weave will be corrupt
207
self._parents.append(frozenset(parents))
181
if parents:
182
ancestors = self.inclusions(parents)
183
delta = self._delta(ancestors, text)
184
185
# offset gives the number of lines that have been inserted
186
# into the weave up to the current point; if the original edit instruction
187
# says to change line A then we actually change (A+offset)
188
offset = 0
189
190
for i1, i2, newlines in delta:
191
assert 0 <= i1
192
assert i1 <= i2
193
assert i2 <= len(self._l)
194
195
# the deletion and insertion are handled separately.
196
# first delete the region.
197
if i1 != i2:
198
self._l.insert(i1+offset, ('[', idx))
199
self._l.insert(i2+offset+1, (']', idx))
200
offset += 2
201
# is this OK???
202
203
if newlines:
204
# there may have been a deletion spanning up to
205
# i2; we want to insert after this region to make sure
206
# we don't destroy ourselves
207
i = i2 + offset
208
self._l[i:i] = [('{', idx)] \
209
+ newlines \
210
+ [('}', idx)]
211
offset += 2 + len(newlines)
212
213
self._addversion(parents)
214
else:
215
# special case; adding with no parents revision; can do this
216
# more quickly by just appending unconditionally
217
self._l.append(('{', idx))
218
self._l += text
219
self._l.append(('}', idx))
220
221
self._addversion(None)
222
208
223
self._sha1s.append(sha1)
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
242
# as auto-merge
243
if text == basis_lines:
244
return new_version
245
246
# add a sentinal, because we can also match against the final line
247
basis_lineno.append(len(self._weave))
248
249
# XXX: which line of the weave should we really consider
250
# matches the end of the file? the current code says it's the
251
# last line of the weave?
252
253
#print 'basis_lines:', basis_lines
254
#print 'new_lines: ', lines
255
256
from difflib import SequenceMatcher
257
s = SequenceMatcher(None, basis_lines, text)
258
259
# offset gives the number of lines that have been inserted
260
# into the weave up to the current point; if the original edit instruction
261
# says to change line A then we actually change (A+offset)
262
offset = 0
263
264
for tag, i1, i2, j1, j2 in s.get_opcodes():
265
# i1,i2 are given in offsets within basis_lines; we need to map them
266
# back to offsets within the entire weave
267
#print 'raw match', tag, i1, i2, j1, j2
268
if tag == 'equal':
269
continue
270
271
i1 = basis_lineno[i1]
272
i2 = basis_lineno[i2]
273
274
assert 0 <= j1 <= j2 <= len(text)
275
276
#print tag, i1, i2, j1, j2
277
278
# the deletion and insertion are handled separately.
279
# first delete the region.
280
if i1 != i2:
281
self._weave.insert(i1+offset, ('[', new_version))
282
self._weave.insert(i2+offset+1, (']', new_version))
283
offset += 2
284
285
if j1 != j2:
286
# there may have been a deletion spanning up to
287
# i2; we want to insert after this region to make sure
288
# we don't destroy ourselves
289
i = i2 + offset
290
self._weave[i:i] = ([('{', new_version)]
291
+ text[j1:j2]
292
+ [('}', new_version)])
293
offset += 2 + (j2 - j1)
294
295
return new_version
224
225
return idx
296
226
297
227
298
228
def inclusions(self, versions):
303
233
while v >= 0:
304
234
if v in i:
305
235
# include all its parents
306
i.update(self._parents[v])
236
i.update(self._v[v])
307
237
v -= 1
308
238
return i
309
239
except IndexError:
312
242
313
243
def minimal_parents(self, version):
314
244
"""Find the minimal set of parents for the version."""
315
included = self._parents[version]
245
included = self._v[version]
316
246
if not included:
317
247
return []
318
248
332
262
return mininc
333
263
334
264
265
def _addversion(self, parents):
266
if parents:
267
self._v.append(parents)
268
else:
269
self._v.append(frozenset())
270
335
271
336
272
def _check_lines(self, text):
337
273
if not isinstance(text, list):
348
284
"""Check everything in the sequence of indexes is valid"""
349
285
for i in indexes:
350
286
try:
351
self._parents[i]
287
self._v[i]
352
288
except IndexError:
353
289
raise IndexError("invalid version number %r" % i)
354
290
365
301
yield origin, text
366
302
367
303
368
def _walk(self):
369
"""Walk the weave.
370
371
Yields sequence of
372
(lineno, insert, deletes, text)
373
for each literal line.
374
"""
375
376
istack = []
377
dset = set()
378
379
lineno = 0 # line of weave, 0-based
380
381
for l in self._weave:
382
if isinstance(l, tuple):
383
c, v = l
384
isactive = None
385
if c == '{':
386
istack.append(v)
387
elif c == '}':
388
oldv = istack.pop()
389
elif c == '[':
390
assert v not in dset
391
dset.add(v)
392
elif c == ']':
393
dset.remove(v)
394
else:
395
raise WeaveFormatError('unexpected instruction %r'
396
% v)
397
else:
398
assert isinstance(l, basestring)
399
assert istack
400
yield lineno, istack[-1], dset, l
401
lineno += 1
402
403
404
405
304
def _extract(self, versions):
406
305
"""Yield annotation of lines in included set.
407
306
420
319
421
320
isactive = None
422
321
423
result = []
424
425
322
WFE = WeaveFormatError
426
323
427
for l in self._weave:
324
for l in self._l:
428
325
if isinstance(l, tuple):
429
326
c, v = l
430
327
isactive = None
448
345
if isactive is None:
449
346
isactive = (not dset) and istack and (istack[-1] in included)
450
347
if isactive:
451
result.append((istack[-1], lineno, l))
348
yield istack[-1], lineno, l
452
349
lineno += 1
453
350
454
351
if istack:
458
355
raise WFE("unclosed deletion blocks at end of weave",
459
356
dset)
460
357
461
return result
462
463
464
358
465
359
def get_iter(self, version):
466
360
"""Yield lines for the specified version."""
474
368
475
369
def mash_iter(self, included):
476
370
"""Return composed version of multiple included versions."""
371
included = frozenset(included)
477
372
for origin, lineno, text in self._extract(included):
478
373
yield text
479
374
480
375
481
376
def dump(self, to_file):
482
377
from pprint import pprint
483
print >>to_file, "Weave._weave = ",
484
pprint(self._weave, to_file)
485
print >>to_file, "Weave._parents = ",
486
pprint(self._parents, to_file)
378
print >>to_file, "Weave._l = ",
379
pprint(self._l, to_file)
380
print >>to_file, "Weave._v = ",
381
pprint(self._v, to_file)
487
382
488
383
489
384
490
385
def numversions(self):
491
l = len(self._parents)
386
l = len(self._v)
492
387
assert l == len(self._sha1s)
493
388
return l
494
389
495
390
496
def __len__(self):
497
return self.numversions()
498
499
500
391
def check(self, progress_bar=None):
501
392
# check no circular inclusions
502
393
for version in range(self.numversions()):
503
inclusions = list(self._parents[version])
394
inclusions = list(self._v[version])
504
395
if inclusions:
505
396
inclusions.sort()
506
397
if inclusions[-1] >= version:
566
457
If line1=line2, this is a pure insert; if newlines=[] this is a
567
458
pure delete. (Similar to difflib.)
568
459
"""
569
570
571
572
def plan_merge(self, ver_a, ver_b):
573
"""Return pseudo-annotation indicating how the two versions merge.
574
575
This is computed between versions a and b and their common
576
base.
577
578
Weave lines present in none of them are skipped entirely.
579
"""
580
inc_a = self.inclusions([ver_a])
581
inc_b = self.inclusions([ver_b])
582
inc_c = inc_a & inc_b
583
584
for lineno, insert, deleteset, line in self._walk():
585
if deleteset & inc_c:
586
# killed in parent; can't be in either a or b
587
# not relevant to our work
588
yield 'killed-base', line
589
elif insert in inc_c:
590
# was inserted in base
591
killed_a = bool(deleteset & inc_a)
592
killed_b = bool(deleteset & inc_b)
593
if killed_a and killed_b:
594
yield 'killed-both', line
595
elif killed_a:
596
yield 'killed-a', line
597
elif killed_b:
598
yield 'killed-b', line
599
else:
600
yield 'unchanged', line
601
elif insert in inc_a:
602
if deleteset & inc_a:
603
yield 'ghost-a', line
604
else:
605
# new in A; not in B
606
yield 'new-a', line
607
elif insert in inc_b:
608
if deleteset & inc_b:
609
yield 'ghost-b', line
610
else:
611
yield 'new-b', line
612
else:
613
# not in either revision
614
yield 'irrelevant', line
615
616
yield 'unchanged', '' # terminator
617
618
619
620
def weave_merge(self, plan):
621
lines_a = []
622
lines_b = []
623
ch_a = ch_b = False
624
625
for state, line in plan:
626
if state == 'unchanged' or state == 'killed-both':
627
# resync and flush queued conflicts changes if any
628
if not lines_a and not lines_b:
629
pass
630
elif ch_a and not ch_b:
631
# one-sided change:
632
for l in lines_a: yield l
633
elif ch_b and not ch_a:
634
for l in lines_b: yield l
635
elif lines_a == lines_b:
636
for l in lines_a: yield l
637
else:
638
yield '<<<<\n'
639
for l in lines_a: yield l
640
yield '====\n'
641
for l in lines_b: yield l
642
yield '>>>>\n'
643
644
del lines_a[:]
645
del lines_b[:]
646
ch_a = ch_b = False
647
648
if state == 'unchanged':
649
if line:
650
yield line
651
elif state == 'killed-a':
652
ch_a = True
653
lines_b.append(line)
654
elif state == 'killed-b':
655
ch_b = True
656
lines_a.append(line)
657
elif state == 'new-a':
658
ch_a = True
659
lines_a.append(line)
660
elif state == 'new-b':
661
ch_b = True
662
lines_b.append(line)
663
else:
664
assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
665
'killed-both'), \
666
state
667
668
669
670
671
672
673
674
def weave_info(w):
460
# basis a list of (origin, lineno, line)
461
basis_lineno = []
462
basis_lines = []
463
for origin, lineno, line in self._extract(included):
464
basis_lineno.append(lineno)
465
basis_lines.append(line)
466
467
# add a sentinal, because we can also match against the final line
468
basis_lineno.append(len(self._l))
469
470
# XXX: which line of the weave should we really consider
471
# matches the end of the file? the current code says it's the
472
# last line of the weave?
473
474
from difflib import SequenceMatcher
475
s = SequenceMatcher(None, basis_lines, lines)
476
477
# TODO: Perhaps return line numbers from composed weave as well?
478
479
for tag, i1, i2, j1, j2 in s.get_opcodes():
480
##print tag, i1, i2, j1, j2
481
482
if tag == 'equal':
483
continue
484
485
# i1,i2 are given in offsets within basis_lines; we need to map them
486
# back to offsets within the entire weave
487
real_i1 = basis_lineno[i1]
488
real_i2 = basis_lineno[i2]
489
490
assert 0 <= j1
491
assert j1 <= j2
492
assert j2 <= len(lines)
493
494
yield real_i1, real_i2, lines[j1:j2]
495
496
497
498
def weave_info(filename, out):
675
499
"""Show some text information about the weave."""
676
print '%6s %40s %20s' % ('ver', 'sha1', 'parents')
677
for i in (6, 40, 20):
678
print '-' * i,
679
print
680
for i in range(w.numversions()):
681
sha1 = w._sha1s[i]
682
print '%6d %40s %s' % (i, sha1, ' '.join(map(str, w._parents[i])))
683
684
685
686
def weave_stats(weave_file):
687
from bzrlib.progress import ProgressBar
688
from bzrlib.weavefile import read_weave
689
690
pb = ProgressBar()
691
692
wf = file(weave_file, 'rb')
500
from weavefile import read_weave
501
wf = file(filename, 'rb')
693
502
w = read_weave(wf)
694
503
# FIXME: doesn't work on pipes
695
504
weave_size = wf.tell()
505
print >>out, "weave file size %d bytes" % weave_size
506
print >>out, "weave contains %d versions" % len(w._v)
696
507
697
508
total = 0
698
vers = len(w)
699
for i in range(vers):
700
pb.update('checking sizes', i, vers)
701
for line in w.get_iter(i):
702
total += len(line)
703
704
pb.clear()
705
706
print 'versions %9d' % vers
707
print 'weave file %9d bytes' % weave_size
708
print 'total contents %9d bytes' % total
709
print 'compression ratio %9.2fx' % (float(total) / float(weave_size))
710
if vers:
711
avg = total/vers
712
print 'average size %9d bytes' % avg
713
print 'relative size %9.2fx' % (float(weave_size) / float(avg))
509
print '%6s %6s %8s %40s %20s' % ('ver', 'lines', 'bytes', 'sha1', 'parents')
510
for i in (6, 6, 8, 40, 20):
511
print '-' * i,
512
print
513
for i in range(len(w._v)):
514
text = w.get(i)
515
lines = len(text)
516
bytes = sum((len(a) for a in text))
517
sha1 = w._sha1s[i]
518
print '%6d %6d %8d %40s' % (i, lines, bytes, sha1),
519
for pv in w._v[i]:
520
print pv,
521
print
522
total += bytes
523
524
print >>out, "versions total %d bytes" % total
525
print >>out, "compression ratio %.3f" % (float(total)/float(weave_size))
714
526
715
527
716
528
def usage():
814
626
lasto = origin
815
627
816
628
elif cmd == 'info':
817
weave_info(readit())
818
819
elif cmd == 'stats':
820
weave_stats(argv[2])
629
weave_info(argv[2], sys.stdout)
821
630
822
631
elif cmd == 'check':
823
632
w = readit()
824
633
pb = ProgressBar()
825
634
w.check(pb)
826
635
pb.clear()
827
print '%d versions ok' % w.numversions()
828
636
829
637
elif cmd == 'inclusions':
830
638
w = readit()
832
640
833
641
elif cmd == 'parents':
834
642
w = readit()
835
print ' '.join(map(str, w._parents[int(argv[3])]))
836
837
elif cmd == 'plan-merge':
838
w = readit()
839
for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
840
if line:
841
print '%14s | %s' % (state, line),
643
print ' '.join(map(str, w._v[int(argv[3])]))
842
644
843
645
elif cmd == 'merge':
844
w = readit()
845
p = w.plan_merge(int(argv[3]), int(argv[4]))
846
sys.stdout.writelines(w.weave_merge(p))
847
848
elif cmd == 'mash-merge':
849
646
if len(argv) != 5:
850
647
usage()
851
648
return 1
Loggerhead is a web-based interface for Breezy
Version: 2.0.1