« back to all changes in this revision
Viewing changes to bzrlib/weave.py
- browse files at revision 918
- compare with another revision
- download diff
- download tarball
- view history from revision 918
- Committer: Martin Pool
- Date: 2005-07-14 08:03:52 UTC
- Revision ID: mbp@sourcefrog.net-20050714080352-d8631baf3620057d
- start doing new weave-merge algorithm
- files added:
- bzrlib/hashcache.py
- bzrlib/selftest
- effbot
- effbot/org
- plugins
- plugins/changeset
- tools
- files removed:
- bzrlib/statcache.py
- files renamed:
- bzrlib/selftest.py => bzrlib/selftest/__init__.py
- bzrlib/whitebox.py => bzrlib/selftest/whitebox.py
- files modified:
- .bzrignore
added
removed
bzrlib/weave.py
1
#! /usr/bin/python
2
3
# Copyright (C) 2005 Canonical Ltd
4
5
# This program is free software; you can redistribute it and/or modify
6
# it under the terms of the GNU General Public License as published by
7
# the Free Software Foundation; either version 2 of the License, or
8
# (at your option) any later version.
9
10
# This program is distributed in the hope that it will be useful,
11
# but WITHOUT ANY WARRANTY; without even the implied warranty of
12
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13
# GNU General Public License for more details.
14
15
# You should have received a copy of the GNU General Public License
16
# along with this program; if not, write to the Free Software
17
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18
19
# Author: Martin Pool <mbp@canonical.com>
20
21
22
"""Weave - storage of related text file versions"""
23
24
# TODO: Perhaps have copy method for Weave instances?
25
26
# XXX: If we do weaves this way, will a merge still behave the same
27
# way if it's done in a different order? That's a pretty desirable
28
# property.
29
30
# TODO: Nothing here so far assumes the lines are really \n newlines,
31
# rather than being split up in some other way. We could accomodate
32
# binaries, perhaps by naively splitting on \n or perhaps using
33
# something like a rolling checksum.
34
35
# TODO: Track version names as well as indexes.
36
37
# TODO: End marker for each version so we can stop reading?
38
39
# TODO: Check that no insertion occurs inside a deletion that was
40
# active in the version of the insertion.
41
42
# TODO: In addition to the SHA-1 check, perhaps have some code that
43
# checks structural constraints of the weave: ie that insertions are
44
# properly nested, that there is no text outside of an insertion, that
45
# insertions or deletions are not repeated, etc.
46
47
# TODO: Make the info command just show info, not extract everything:
48
# it can be much faster.
49
50
# TODO: Perhaps use long integers as sets instead of set objects; may
51
# be faster.
52
53
# TODO: Parallel-extract that passes back each line along with a
54
# description of which revisions include it. Nice for checking all
55
# shas in parallel.
56
57
58
59
60
try:
61
set
62
frozenset
63
except NameError:
64
from sets import Set, ImmutableSet
65
set = Set
66
frozenset = ImmutableSet
67
del Set, ImmutableSet
68
69
70
class WeaveError(Exception):
71
"""Exception in processing weave"""
72
73
74
class WeaveFormatError(WeaveError):
75
"""Weave invariant violated"""
76
77
78
class Weave(object):
79
"""weave - versioned text file storage.
80
81
A Weave manages versions of line-based text files, keeping track
82
of the originating version for each line.
83
84
To clients the "lines" of the file are represented as a list of strings.
85
These strings will typically have terminal newline characters, but
86
this is not required. In particular files commonly do not have a newline
87
at the end of the file.
88
89
Texts can be identified in either of two ways:
90
91
* a nonnegative index number.
92
93
* a version-id string.
94
95
Typically the index number will be valid only inside this weave and
96
the version-id is used to reference it in the larger world.
97
98
The weave is represented as a list mixing edit instructions and
99
literal text. Each entry in _l can be either a string (or
100
unicode), or a tuple. If a string, it means that the given line
101
should be output in the currently active revisions.
102
103
If a tuple, it gives a processing instruction saying in which
104
revisions the enclosed lines are active. The tuple has the form
105
(instruction, version).
106
107
The instruction can be '{' or '}' for an insertion block, and '['
108
and ']' for a deletion block respectively. The version is the
109
integer version index. There is no replace operator, only deletes
110
and inserts.
111
112
Constraints/notes:
113
114
* A later version can delete lines that were introduced by any
115
number of ancestor versions; this implies that deletion
116
instructions can span insertion blocks without regard to the
117
insertion block's nesting.
118
119
* Similarly, deletions need not be properly nested with regard to
120
each other, because they might have been generated by
121
independent revisions.
122
123
* Insertions are always made by inserting a new bracketed block
124
into a single point in the previous weave. This implies they
125
can nest but not overlap, and the nesting must always have later
126
insertions on the inside.
127
128
* It doesn't seem very useful to have an active insertion
129
inside an inactive insertion, but it might happen.
130
131
* Therefore, all instructions are always"considered"; that
132
is passed onto and off the stack. An outer inactive block
133
doesn't disable an inner block.
134
135
* Lines are enabled if the most recent enclosing insertion is
136
active and none of the enclosing deletions are active.
137
138
* There is no point having a deletion directly inside its own
139
insertion; you might as well just not write it. And there
140
should be no way to get an earlier version deleting a later
141
version.
142
143
_l
144
Text of the weave.
145
146
_v
147
List of parents, indexed by version number.
148
It is only necessary to store the minimal set of parents for
149
each version; the parent's parents are implied.
150
151
_sha1s
152
List of hex SHA-1 of each version, or None if not recorded.
153
"""
154
def __init__(self):
155
self._l = []
156
self._v = []
157
self._sha1s = []
158
159
160
def __eq__(self, other):
161
if not isinstance(other, Weave):
162
return False
163
return self._v == other._v \
164
and self._l == other._l
165
166
167
def __ne__(self, other):
168
return not self.__eq__(other)
169
170
171
def add(self, parents, text):
172
"""Add a single text on top of the weave.
173
174
Returns the index number of the newly added version.
175
176
parents
177
List or set of direct parent version numbers.
178
179
text
180
Sequence of lines to be added in the new version."""
181
## self._check_versions(parents)
182
## self._check_lines(text)
183
idx = len(self._v)
184
185
import sha
186
s = sha.new()
187
for l in text:
188
s.update(l)
189
sha1 = s.hexdigest()
190
del s
191
192
# TODO: It'd probably be faster to append things on to a new
193
# list rather than modifying the existing one, which is likely
194
# to cause a lot of copying.
195
196
if parents:
197
ancestors = self.inclusions(parents)
198
delta = self._delta(ancestors, text)
199
200
# offset gives the number of lines that have been inserted
201
# into the weave up to the current point; if the original edit instruction
202
# says to change line A then we actually change (A+offset)
203
offset = 0
204
205
for i1, i2, newlines in delta:
206
assert 0 <= i1
207
assert i1 <= i2
208
assert i2 <= len(self._l)
209
210
# the deletion and insertion are handled separately.
211
# first delete the region.
212
if i1 != i2:
213
self._l.insert(i1+offset, ('[', idx))
214
self._l.insert(i2+offset+1, (']', idx))
215
offset += 2
216
# is this OK???
217
218
if newlines:
219
# there may have been a deletion spanning up to
220
# i2; we want to insert after this region to make sure
221
# we don't destroy ourselves
222
i = i2 + offset
223
self._l[i:i] = [('{', idx)] \
224
+ newlines \
225
+ [('}', idx)]
226
offset += 2 + len(newlines)
227
228
self._addversion(parents)
229
else:
230
# special case; adding with no parents revision; can do this
231
# more quickly by just appending unconditionally
232
self._l.append(('{', idx))
233
self._l += text
234
self._l.append(('}', idx))
235
236
self._addversion(None)
237
238
self._sha1s.append(sha1)
239
240
return idx
241
242
243
def inclusions_bitset(self, versions):
244
i = 0
245
for v in versions:
246
i |= (1L << v)
247
v = max(versions)
248
while v >= 0:
249
if i & (1L << v):
250
# if v is included, include all its parents
251
for pv in self._v[v]:
252
i |= (1L << pv)
253
v -= 1
254
return i
255
256
257
def inclusions(self, versions):
258
"""Return set of all ancestors of given version(s)."""
259
i = set(versions)
260
v = max(versions)
261
try:
262
while v >= 0:
263
if v in i:
264
# include all its parents
265
i.update(self._v[v])
266
v -= 1
267
return i
268
except IndexError:
269
raise ValueError("version %d not present in weave" % v)
270
271
272
def minimal_parents(self, version):
273
"""Find the minimal set of parents for the version."""
274
included = self._v[version]
275
if not included:
276
return []
277
278
li = list(included)
279
li.sort(reverse=True)
280
281
mininc = []
282
gotit = set()
283
284
for pv in li:
285
if pv not in gotit:
286
mininc.append(pv)
287
gotit.update(self.inclusions(pv))
288
289
assert mininc[0] >= 0
290
assert mininc[-1] < version
291
return mininc
292
293
294
def _addversion(self, parents):
295
if parents:
296
self._v.append(parents)
297
else:
298
self._v.append(frozenset())
299
300
301
def _check_lines(self, text):
302
if not isinstance(text, list):
303
raise ValueError("text should be a list, not %s" % type(text))
304
305
for l in text:
306
if not isinstance(l, basestring):
307
raise ValueError("text line should be a string or unicode, not %s"
308
% type(l))
309
310
311
312
def _check_versions(self, indexes):
313
"""Check everything in the sequence of indexes is valid"""
314
for i in indexes:
315
try:
316
self._v[i]
317
except IndexError:
318
raise IndexError("invalid version number %r" % i)
319
320
321
def annotate(self, index):
322
return list(self.annotate_iter(index))
323
324
325
def annotate_iter(self, version):
326
"""Yield list of (index-id, line) pairs for the specified version.
327
328
The index indicates when the line originated in the weave."""
329
for origin, lineno, text in self._extract([version]):
330
yield origin, text
331
332
333
def _walk(self):
334
"""Walk the weave.
335
336
Yields sequence of
337
(lineno, insert, deletes, text)
338
for each literal line.
339
"""
340
341
istack = []
342
dset = 0L
343
344
lineno = 0 # line of weave, 0-based
345
346
for l in self._l:
347
if isinstance(l, tuple):
348
c, v = l
349
isactive = None
350
if c == '{':
351
istack.append(v)
352
elif c == '}':
353
oldv = istack.pop()
354
elif c == '[':
355
vs = (1L << v)
356
assert not (dset & vs)
357
dset |= vs
358
elif c == ']':
359
vs = (1L << v)
360
assert dset & vs
361
dset ^= vs
362
else:
363
raise WeaveFormatError('unexpected instruction %r'
364
% v)
365
else:
366
assert isinstance(l, basestring)
367
assert istack
368
yield lineno, istack[-1], dset, l
369
lineno += 1
370
371
372
373
def _extract(self, versions):
374
"""Yield annotation of lines in included set.
375
376
Yields a sequence of tuples (origin, lineno, text), where
377
origin is the origin version, lineno the index in the weave,
378
and text the text of the line.
379
380
The set typically but not necessarily corresponds to a version.
381
"""
382
included = self.inclusions(versions)
383
384
istack = []
385
dset = set()
386
387
lineno = 0 # line of weave, 0-based
388
389
isactive = None
390
391
WFE = WeaveFormatError
392
393
for l in self._l:
394
if isinstance(l, tuple):
395
c, v = l
396
isactive = None
397
if c == '{':
398
assert v not in istack
399
istack.append(v)
400
elif c == '}':
401
oldv = istack.pop()
402
assert oldv == v
403
elif c == '[':
404
if v in included:
405
assert v not in dset
406
dset.add(v)
407
else:
408
assert c == ']'
409
if v in included:
410
assert v in dset
411
dset.remove(v)
412
else:
413
assert isinstance(l, basestring)
414
if isactive is None:
415
isactive = (not dset) and istack and (istack[-1] in included)
416
if isactive:
417
yield istack[-1], lineno, l
418
lineno += 1
419
420
if istack:
421
raise WFE("unclosed insertion blocks at end of weave",
422
istack)
423
if dset:
424
raise WFE("unclosed deletion blocks at end of weave",
425
dset)
426
427
428
def get_iter(self, version):
429
"""Yield lines for the specified version."""
430
for origin, lineno, line in self._extract([version]):
431
yield line
432
433
434
def get(self, index):
435
return list(self.get_iter(index))
436
437
438
def mash_iter(self, included):
439
"""Return composed version of multiple included versions."""
440
included = frozenset(included)
441
for origin, lineno, text in self._extract(included):
442
yield text
443
444
445
def dump(self, to_file):
446
from pprint import pprint
447
print >>to_file, "Weave._l = ",
448
pprint(self._l, to_file)
449
print >>to_file, "Weave._v = ",
450
pprint(self._v, to_file)
451
452
453
454
def numversions(self):
455
l = len(self._v)
456
assert l == len(self._sha1s)
457
return l
458
459
460
def check(self, progress_bar=None):
461
# check no circular inclusions
462
for version in range(self.numversions()):
463
inclusions = list(self._v[version])
464
if inclusions:
465
inclusions.sort()
466
if inclusions[-1] >= version:
467
raise WeaveFormatError("invalid included version %d for index %d"
468
% (inclusions[-1], version))
469
470
# try extracting all versions; this is a bit slow and parallel
471
# extraction could be used
472
import sha
473
nv = self.numversions()
474
for version in range(nv):
475
if progress_bar:
476
progress_bar.update('checking text', version, nv)
477
s = sha.new()
478
for l in self.get_iter(version):
479
s.update(l)
480
hd = s.hexdigest()
481
expected = self._sha1s[version]
482
if hd != expected:
483
raise WeaveError("mismatched sha1 for version %d; "
484
"got %s, expected %s"
485
% (version, hd, expected))
486
487
# TODO: check insertions are properly nested, that there are
488
# no lines outside of insertion blocks, that deletions are
489
# properly paired, etc.
490
491
492
493
def merge(self, merge_versions):
494
"""Automerge and mark conflicts between versions.
495
496
This returns a sequence, each entry describing alternatives
497
for a chunk of the file. Each of the alternatives is given as
498
a list of lines.
499
500
If there is a chunk of the file where there's no diagreement,
501
only one alternative is given.
502
"""
503
504
# approach: find the included versions common to all the
505
# merged versions
506
raise NotImplementedError()
507
508
509
510
def _delta(self, included, lines):
511
"""Return changes from basis to new revision.
512
513
The old text for comparison is the union of included revisions.
514
515
This is used in inserting a new text.
516
517
Delta is returned as a sequence of
518
(weave1, weave2, newlines).
519
520
This indicates that weave1:weave2 of the old weave should be
521
replaced by the sequence of lines in newlines. Note that
522
these line numbers are positions in the total weave and don't
523
correspond to the lines in any extracted version, or even the
524
extracted union of included versions.
525
526
If line1=line2, this is a pure insert; if newlines=[] this is a
527
pure delete. (Similar to difflib.)
528
"""
529
# basis a list of (origin, lineno, line)
530
basis_lineno = []
531
basis_lines = []
532
for origin, lineno, line in self._extract(included):
533
basis_lineno.append(lineno)
534
basis_lines.append(line)
535
536
# add a sentinal, because we can also match against the final line
537
basis_lineno.append(len(self._l))
538
539
# XXX: which line of the weave should we really consider
540
# matches the end of the file? the current code says it's the
541
# last line of the weave?
542
543
from difflib import SequenceMatcher
544
s = SequenceMatcher(None, basis_lines, lines)
545
546
# TODO: Perhaps return line numbers from composed weave as well?
547
548
for tag, i1, i2, j1, j2 in s.get_opcodes():
549
##print tag, i1, i2, j1, j2
550
551
if tag == 'equal':
552
continue
553
554
# i1,i2 are given in offsets within basis_lines; we need to map them
555
# back to offsets within the entire weave
556
real_i1 = basis_lineno[i1]
557
real_i2 = basis_lineno[i2]
558
559
assert 0 <= j1
560
assert j1 <= j2
561
assert j2 <= len(lines)
562
563
yield real_i1, real_i2, lines[j1:j2]
564
565
566
567
def plan_merge(self, ver_a, ver_b):
568
"""Return pseudo-annotation indicating how the two versions merge.
569
570
This is computed between versions a and b and their common
571
base.
572
573
Weave lines present in none of them are skipped entirely.
574
"""
575
inc_a = self.inclusions_bitset([ver_a])
576
inc_b = self.inclusions_bitset([ver_b])
577
inc_c = inc_a & inc_b
578
579
for lineno, insert, deleteset, line in self._walk():
580
insertset = (1L << insert)
581
if deleteset & inc_c:
582
# killed in parent; can't be in either a or b
583
# not relevant to our work
584
yield 'killed-base', line
585
elif insertset & inc_c:
586
# was inserted in base
587
killed_a = bool(deleteset & inc_a)
588
killed_b = bool(deleteset & inc_b)
589
if killed_a and killed_b:
590
# killed in both
591
yield 'killed-both', line
592
elif killed_a:
593
yield 'killed-a', line
594
elif killed_b:
595
yield 'killed-b', line
596
else:
597
yield 'unchanged', line
598
elif insertset & inc_a:
599
if deleteset & inc_a:
600
yield 'ghost-a', line
601
else:
602
# new in A; not in B
603
yield 'new-a', line
604
elif insertset & inc_b:
605
if deleteset & inc_b:
606
yield 'ghost-b', line
607
else:
608
yield 'new-b', line
609
else:
610
# not in either revision
611
yield 'irrelevant', line
612
613
614
615
616
def weave_info(filename, out):
617
"""Show some text information about the weave."""
618
from weavefile import read_weave
619
wf = file(filename, 'rb')
620
w = read_weave(wf)
621
# FIXME: doesn't work on pipes
622
weave_size = wf.tell()
623
print >>out, "weave file size %d bytes" % weave_size
624
print >>out, "weave contains %d versions" % len(w._v)
625
626
total = 0
627
print '%6s %6s %8s %40s %20s' % ('ver', 'lines', 'bytes', 'sha1', 'parents')
628
for i in (6, 6, 8, 40, 20):
629
print '-' * i,
630
print
631
for i in range(len(w._v)):
632
text = w.get(i)
633
lines = len(text)
634
bytes = sum((len(a) for a in text))
635
sha1 = w._sha1s[i]
636
print '%6d %6d %8d %40s' % (i, lines, bytes, sha1),
637
for pv in w._v[i]:
638
print pv,
639
print
640
total += bytes
641
642
print >>out, "versions total %d bytes" % total
643
print >>out, "compression ratio %.3f" % (float(total)/float(weave_size))
644
645
646
def usage():
647
print """bzr weave tool
648
649
Experimental tool for weave algorithm.
650
651
usage:
652
weave init WEAVEFILE
653
Create an empty weave file
654
weave get WEAVEFILE VERSION
655
Write out specified version.
656
weave check WEAVEFILE
657
Check consistency of all versions.
658
weave info WEAVEFILE
659
Display table of contents.
660
weave add WEAVEFILE [BASE...] < NEWTEXT
661
Add NEWTEXT, with specified parent versions.
662
weave annotate WEAVEFILE VERSION
663
Display origin of each line.
664
weave mash WEAVEFILE VERSION...
665
Display composite of all selected versions.
666
weave merge WEAVEFILE VERSION1 VERSION2 > OUT
667
Auto-merge two versions and display conflicts.
668
669
example:
670
671
% weave init foo.weave
672
% vi foo.txt
673
% weave add foo.weave < foo.txt
674
added version 0
675
676
(create updated version)
677
% vi foo.txt
678
% weave get foo.weave 0 | diff -u - foo.txt
679
% weave add foo.weave 0 < foo.txt
680
added version 1
681
682
% weave get foo.weave 0 > foo.txt (create forked version)
683
% vi foo.txt
684
% weave add foo.weave 0 < foo.txt
685
added version 2
686
687
% weave merge foo.weave 1 2 > foo.txt (merge them)
688
% vi foo.txt (resolve conflicts)
689
% weave add foo.weave 1 2 < foo.txt (commit merged version)
690
691
"""
692
693
694
695
def main(argv):
696
import sys
697
import os
698
from weavefile import write_weave, read_weave
699
from bzrlib.progress import ProgressBar
700
701
#import psyco
702
#psyco.full()
703
704
cmd = argv[1]
705
706
def readit():
707
return read_weave(file(argv[2], 'rb'))
708
709
if cmd == 'help':
710
usage()
711
elif cmd == 'add':
712
w = readit()
713
# at the moment, based on everything in the file
714
parents = map(int, argv[3:])
715
lines = sys.stdin.readlines()
716
ver = w.add(parents, lines)
717
write_weave(w, file(argv[2], 'wb'))
718
print 'added version %d' % ver
719
elif cmd == 'init':
720
fn = argv[2]
721
if os.path.exists(fn):
722
raise IOError("file exists")
723
w = Weave()
724
write_weave(w, file(fn, 'wb'))
725
elif cmd == 'get': # get one version
726
w = readit()
727
sys.stdout.writelines(w.get_iter(int(argv[3])))
728
729
elif cmd == 'mash': # get composite
730
w = readit()
731
sys.stdout.writelines(w.mash_iter(map(int, argv[3:])))
732
733
elif cmd == 'annotate':
734
w = readit()
735
# newline is added to all lines regardless; too hard to get
736
# reasonable formatting otherwise
737
lasto = None
738
for origin, text in w.annotate(int(argv[3])):
739
text = text.rstrip('\r\n')
740
if origin == lasto:
741
print ' | %s' % (text)
742
else:
743
print '%5d | %s' % (origin, text)
744
lasto = origin
745
746
elif cmd == 'info':
747
weave_info(argv[2], sys.stdout)
748
749
elif cmd == 'check':
750
w = readit()
751
pb = ProgressBar()
752
w.check(pb)
753
pb.clear()
754
755
elif cmd == 'inclusions':
756
w = readit()
757
print ' '.join(map(str, w.inclusions([int(argv[3])])))
758
759
elif cmd == 'parents':
760
w = readit()
761
print ' '.join(map(str, w._v[int(argv[3])]))
762
763
elif cmd == 'plan-merge':
764
w = readit()
765
for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
766
print '%14s | %s' % (state, line),
767
768
elif cmd == 'merge':
769
if len(argv) != 5:
770
usage()
771
return 1
772
773
w = readit()
774
v1, v2 = map(int, argv[3:5])
775
776
basis = w.inclusions([v1]).intersection(w.inclusions([v2]))
777
778
base_lines = list(w.mash_iter(basis))
779
a_lines = list(w.get(v1))
780
b_lines = list(w.get(v2))
781
782
from bzrlib.merge3 import Merge3
783
m3 = Merge3(base_lines, a_lines, b_lines)
784
785
name_a = 'version %d' % v1
786
name_b = 'version %d' % v2
787
sys.stdout.writelines(m3.merge_lines(name_a=name_a, name_b=name_b))
788
else:
789
raise ValueError('unknown command %r' % cmd)
790
791
792
if __name__ == '__main__':
793
import sys
794
sys.exit(main(sys.argv))
Loggerhead is a web-based interface for Breezy
Version: 2.0.1