« back to all changes in this revision
Viewing changes to bzrlib/weave.py
- browse files at revision 1216
- compare with another revision
- download diff
- download tarball
- view history from revision 1216
- Committer: Martin Pool
- Date: 2005-09-12 09:50:44 UTC
- Revision ID: mbp@sourcefrog.net-20050912095044-6acfdb5611729987
- no tests in bzrlib.fetch anymore
- files added:
- bzrlib/meta_store.py
- files removed:
- NEWS.developers
- bzrlib/store
- bzrlib/transport
- files renamed:
- bzrlib/store/__init__.py => bzrlib/store.py
- bzrlib/store/weave.py => bzrlib/weavestore.py
- bzrlib/upgrade.py => tools/history2weaves.py
- bzrlib/selftest/test_weave.py => tools/testweave.py
- files modified:
- .bzrignore
- bzr *
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
52
53
54
# TODO: Perhaps have copy method for Weave instances?
24
55
25
56
# XXX: If we do weaves this way, will a merge still behave the same
26
57
# way if it's done in a different order? That's a pretty desirable
43
74
44
75
# TODO: Parallel-extract that passes back each line along with a
45
76
# description of which revisions include it. Nice for checking all
46
# shas or calculating stats in parallel.
77
# shas in parallel.
47
78
48
79
# TODO: Using a single _extract routine and then processing the output
49
80
# is probably inefficient. It's simple enough that we can afford to
53
84
# TODO: Perhaps the API should work only in names to hide the integer
54
85
# indexes from the user?
55
86
56
# TODO: Is there any potential performance win by having an add()
57
# variant that is passed a pre-cooked version of the single basis
58
# version?
59
60
# TODO: Have a way to go back and insert a revision V1 that is a parent
61
# of an already-stored revision V2. This means some lines previously
62
# counted as new in V2 will be discovered to have actually come from V1.
63
# It is probably necessary to insert V1, then compute a whole new diff
64
# from the mashed ancestors to V2. This must be repeated for every
65
# direct child of V1. The deltas from V2 to its descendents won't change,
66
# although their location within the weave may change. It may be possible
67
# to just adjust the location of those instructions rather than
68
# re-weaving the whole thing. This is expected to be a fairly rare
69
# operation, only used when inserting data that was previously a ghost.
70
71
72
87
73
88
74
89
import sha
75
from difflib import SequenceMatcher
76
77
from bzrlib.trace import mutter
90
from cStringIO import StringIO
78
91
79
92
80
93
class WeaveError(Exception):
83
96
84
97
class WeaveFormatError(WeaveError):
85
98
"""Weave invariant violated"""
86
87
88
class WeaveParentMismatch(WeaveError):
89
"""Parents are mismatched between two revisions."""
90
99
91
100
92
101
class Weave(object):
104
113
105
114
* a nonnegative index number.
106
115
107
* a version-id string.
116
* a version-id string. (not implemented yet)
108
117
109
118
Typically the index number will be valid only inside this weave and
110
119
the version-id is used to reference it in the larger world.
190
199
self._weave_name = weave_name
191
200
192
201
193
def copy(self):
194
"""Return a deep copy of self.
195
196
The copy can be modified without affecting the original weave."""
197
other = Weave()
198
other._weave = self._weave[:]
199
other._parents = self._parents[:]
200
other._sha1s = self._sha1s[:]
201
other._names = self._names[:]
202
other._name_map = self._name_map.copy()
203
other._weave_name = self._weave_name
204
return other
205
206
202
def __eq__(self, other):
207
203
if not isinstance(other, Weave):
208
204
return False
215
211
return not self.__eq__(other)
216
212
217
213
218
def maybe_lookup(self, name_or_index):
219
"""Convert possible symbolic name to index, or pass through indexes."""
220
if isinstance(name_or_index, (int, long)):
221
return name_or_index
222
else:
223
return self.lookup(name_or_index)
224
225
226
214
def lookup(self, name):
227
"""Convert symbolic version name to index."""
228
215
try:
229
216
return self._name_map[name]
230
217
except KeyError:
231
raise WeaveError("name %r not present in weave %r" %
218
raise WeaveError("name %s not present in weave %s" %
232
219
(name, self._weave_name))
233
220
234
235
def iter_names(self):
236
"""Yield a list of all names in this weave."""
237
return iter(self._names)
238
239
def idx_to_name(self, version):
240
return self._names[version]
241
242
243
def _check_repeated_add(self, name, parents, text, sha1):
244
"""Check that a duplicated add is OK.
245
246
If it is, return the (old) index; otherwise raise an exception.
247
"""
248
idx = self.lookup(name)
249
if sorted(self._parents[idx]) != sorted(parents):
250
raise WeaveError("name \"%s\" already present in weave "
251
"with different parents" % name)
252
if sha1 != self._sha1s[idx]:
253
raise WeaveError("name \"%s\" already present in weave "
254
"with different text" % name)
255
return idx
256
257
258
259
def add(self, name, parents, text, sha1=None):
221
222
def add(self, name, parents, text):
260
223
"""Add a single text on top of the weave.
261
224
262
225
Returns the index number of the newly added version.
269
232
List or set of direct parent version numbers.
270
233
271
234
text
272
Sequence of lines to be added in the new version.
273
274
sha -- SHA-1 of the file, if known. This is trusted to be
275
correct if supplied.
276
"""
277
from bzrlib.osutils import sha_strings
235
Sequence of lines to be added in the new version."""
278
236
279
237
assert isinstance(name, basestring)
280
if sha1 is None:
281
sha1 = sha_strings(text)
282
238
if name in self._name_map:
283
return self._check_repeated_add(name, parents, text, sha1)
284
285
parents = map(self.maybe_lookup, parents)
239
raise WeaveError("name %r already present in weave" % name)
240
286
241
self._check_versions(parents)
287
242
## self._check_lines(text)
288
243
new_version = len(self._parents)
289
244
245
s = sha.new()
246
map(s.update, text)
247
sha1 = s.hexdigest()
248
del s
290
249
291
250
# if we abort after here the (in-memory) weave will be corrupt because only
292
251
# some fields are updated
341
300
#print 'basis_lines:', basis_lines
342
301
#print 'new_lines: ', lines
343
302
303
from difflib import SequenceMatcher
344
304
s = SequenceMatcher(None, basis_lines, text)
345
305
346
306
# offset gives the number of lines that have been inserted
381
341
382
342
return new_version
383
343
384
def add_identical(self, old_rev_id, new_rev_id, parents):
385
"""Add an identical text to old_rev_id as new_rev_id."""
386
old_lines = self.get(self.lookup(old_rev_id))
387
self.add(new_rev_id, parents, old_lines)
388
344
389
345
def inclusions(self, versions):
390
346
"""Return set of all ancestors of given version(s)."""
391
347
i = set(versions)
392
for v in xrange(max(versions), 0, -1):
393
if v in i:
394
# include all its parents
395
i.update(self._parents[v])
396
return i
397
## except IndexError:
398
## raise ValueError("version %d not present in weave" % v)
399
400
401
def parents(self, version):
402
return self._parents[version]
403
404
405
def parent_names(self, version):
406
"""Return version names for parents of a version."""
407
return map(self.idx_to_name, self._parents[self.lookup(version)])
348
v = max(versions)
349
try:
350
while v >= 0:
351
if v in i:
352
# include all its parents
353
i.update(self._parents[v])
354
v -= 1
355
return i
356
except IndexError:
357
raise ValueError("version %d not present in weave" % v)
408
358
409
359
410
360
def minimal_parents(self, version):
450
400
raise IndexError("invalid version number %r" % i)
451
401
452
402
453
def annotate(self, name_or_index):
454
return list(self.annotate_iter(name_or_index))
455
456
457
def annotate_iter(self, name_or_index):
403
def annotate(self, index):
404
return list(self.annotate_iter(index))
405
406
407
def annotate_iter(self, version):
458
408
"""Yield list of (index-id, line) pairs for the specified version.
459
409
460
410
The index indicates when the line originated in the weave."""
461
incls = [self.maybe_lookup(name_or_index)]
462
for origin, lineno, text in self._extract(incls):
411
for origin, lineno, text in self._extract([version]):
463
412
yield origin, text
464
413
465
414
563
512
564
513
565
514
566
def get_iter(self, name_or_index):
515
def get_iter(self, version):
567
516
"""Yield lines for the specified version."""
568
incls = [self.maybe_lookup(name_or_index)]
569
for origin, lineno, line in self._extract(incls):
517
for origin, lineno, line in self._extract([version]):
570
518
yield line
571
519
572
520
573
def get_text(self, name_or_index):
574
return ''.join(self.get_iter(name_or_index))
521
def get_text(self, version):
575
522
assert isinstance(version, int)
576
577
578
def get_lines(self, name_or_index):
579
return list(self.get_iter(name_or_index))
580
581
582
get = get_lines
523
s = StringIO()
524
s.writelines(self.get_iter(version))
525
return s.getvalue()
526
527
528
def get(self, index):
529
return list(self.get_iter(index))
583
530
584
531
585
532
def mash_iter(self, included):
586
533
"""Return composed version of multiple included versions."""
587
included = map(self.maybe_lookup, included)
588
534
for origin, lineno, text in self._extract(included):
589
535
yield text
590
536
650
596
If there is a chunk of the file where there's no diagreement,
651
597
only one alternative is given.
652
598
"""
599
653
600
# approach: find the included versions common to all the
654
601
# merged versions
655
602
raise NotImplementedError()
675
622
If line1=line2, this is a pure insert; if newlines=[] this is a
676
623
pure delete. (Similar to difflib.)
677
624
"""
678
raise NotImplementedError()
625
679
626
680
627
681
628
def plan_merge(self, ver_a, ver_b):
775
722
state
776
723
777
724
778
def join(self, other):
779
"""Integrate versions from other into this weave.
780
781
The resulting weave contains all the history of both weaves;
782
any version you could retrieve from either self or other can be
783
retrieved from self after this call.
784
785
It is illegal for the two weaves to contain different values
786
or different parents for any version. See also reweave().
787
"""
788
if other.numversions() == 0:
789
return # nothing to update, easy
790
# two loops so that we do not change ourselves before verifying it
791
# will be ok
792
# work through in index order to make sure we get all dependencies
793
for other_idx, name in enumerate(other._names):
794
if self._check_version_consistent(other, other_idx, name):
795
continue
796
for other_idx, name in enumerate(other._names):
797
# TODO: If all the parents of the other version are already
798
# present then we can avoid some work by just taking the delta
799
# and adjusting the offsets.
800
new_parents = self._imported_parents(other, other_idx)
801
lines = other.get_lines(other_idx)
802
sha1 = other._sha1s[other_idx]
803
self.add(name, new_parents, lines, sha1)
804
805
806
def _imported_parents(self, other, other_idx):
807
"""Return list of parents in self corresponding to indexes in other."""
808
new_parents = []
809
for parent_idx in other._parents[other_idx]:
810
parent_name = other._names[parent_idx]
811
if parent_name not in self._names:
812
# should not be possible
813
raise WeaveError("missing parent {%s} of {%s} in %r"
814
% (parent_name, other._name_map[other_idx], self))
815
new_parents.append(self._name_map[parent_name])
816
return new_parents
817
818
def _check_version_consistent(self, other, other_idx, name):
819
"""Check if a version in consistent in this and other.
820
821
To be consistent it must have:
822
823
* the same text
824
* the same direct parents (by name, not index, and disregarding
825
order)
826
827
If present & correct return True;
828
if not present in self return False;
829
if inconsistent raise error."""
830
this_idx = self._name_map.get(name, -1)
831
if this_idx != -1:
832
if self._sha1s[this_idx] != other._sha1s[other_idx]:
833
raise WeaveError("inconsistent texts for version {%s} "
834
"when joining weaves"
835
% (name))
836
self_parents = self._parents[this_idx]
837
other_parents = other._parents[other_idx]
838
n1 = [self._names[i] for i in self_parents]
839
n2 = [other._names[i] for i in other_parents]
840
n1.sort()
841
n2.sort()
842
if n1 != n2:
843
raise WeaveParentMismatch("inconsistent parents "
844
"for version {%s}: %s vs %s" % (name, n1, n2))
845
else:
846
return True # ok!
847
else:
848
return False
849
850
def reweave(self, other):
851
"""Reweave self with other."""
852
new_weave = reweave(self, other)
853
for attr in self.__slots__:
854
setattr(self, attr, getattr(new_weave, attr))
855
856
857
def reweave(wa, wb):
858
"""Combine two weaves and return the result.
859
860
This works even if a revision R has different parents in
861
wa and wb. In the resulting weave all the parents are given.
862
863
This is done by just building up a new weave, maintaining ordering
864
of the versions in the two inputs. More efficient approaches
865
might be possible but it should only be necessary to do
866
this operation rarely, when a new previously ghost version is
867
inserted.
868
"""
869
wr = Weave()
870
ia = ib = 0
871
queue_a = range(wa.numversions())
872
queue_b = range(wb.numversions())
873
# first determine combined parents of all versions
874
# map from version name -> all parent names
875
combined_parents = _reweave_parent_graphs(wa, wb)
876
mutter("combined parents: %r", combined_parents)
877
order = _make_reweave_order(wa._names, wb._names, combined_parents)
878
mutter("order to reweave: %r", order)
879
for name in order:
880
if name in wa._name_map:
881
lines = wa.get_lines(name)
882
if name in wb._name_map:
883
assert lines == wb.get_lines(name)
884
else:
885
lines = wb.get_lines(name)
886
wr.add(name, combined_parents[name], lines)
887
return wr
888
889
890
def _reweave_parent_graphs(wa, wb):
891
"""Return combined parent ancestry for two weaves.
892
893
Returned as a list of (version_name, set(parent_names))"""
894
combined = {}
895
for weave in [wa, wb]:
896
for idx, name in enumerate(weave._names):
897
p = combined.setdefault(name, set())
898
p.update(map(weave.idx_to_name, weave._parents[idx]))
899
return combined
900
901
902
def _make_reweave_order(wa_order, wb_order, combined_parents):
903
"""Return an order to reweave versions respecting parents."""
904
done = set()
905
result = []
906
ia = ib = 0
907
next_a = next_b = None
908
len_a = len(wa_order)
909
len_b = len(wb_order)
910
while ia < len(wa_order) or ib < len(wb_order):
911
if ia < len_a:
912
next_a = wa_order[ia]
913
if next_a in done:
914
ia += 1
915
continue
916
if combined_parents[next_a].issubset(done):
917
ia += 1
918
result.append(next_a)
919
done.add(next_a)
920
continue
921
if ib < len_b:
922
next_b = wb_order[ib]
923
if next_b in done:
924
ib += 1
925
continue
926
elif combined_parents[next_b].issubset(done):
927
ib += 1
928
result.append(next_b)
929
done.add(next_b)
930
continue
931
raise WeaveError("don't know how to reweave at {%s} and {%s}"
932
% (next_a, next_b))
933
return result
725
726
727
934
728
935
729
936
730
def weave_toc(w):
947
741
948
742
949
743
950
def weave_stats(weave_file, pb):
744
def weave_stats(weave_file):
745
from bzrlib.progress import ProgressBar
951
746
from bzrlib.weavefile import read_weave
952
747
748
pb = ProgressBar()
749
953
750
wf = file(weave_file, 'rb')
954
751
w = read_weave(wf)
955
752
# FIXME: doesn't work on pipes
959
756
vers = len(w)
960
757
for i in range(vers):
961
758
pb.update('checking sizes', i, vers)
962
for origin, lineno, line in w._extract([i]):
759
for line in w.get_iter(i):
963
760
total += len(line)
964
761
965
762
pb.clear()
996
793
Display composite of all selected versions.
997
794
weave merge WEAVEFILE VERSION1 VERSION2 > OUT
998
795
Auto-merge two versions and display conflicts.
999
weave diff WEAVEFILE VERSION1 VERSION2
1000
Show differences between two versions.
1001
796
1002
797
example:
1003
798
1028
823
def main(argv):
1029
824
import sys
1030
825
import os
1031
try:
1032
import bzrlib
1033
except ImportError:
1034
# in case we're run directly from the subdirectory
1035
sys.path.append('..')
1036
import bzrlib
1037
from bzrlib.weavefile import write_weave, read_weave
826
from weavefile import write_weave, read_weave
1038
827
from bzrlib.progress import ProgressBar
1039
828
1040
829
try:
1077
866
w = readit()
1078
867
sys.stdout.writelines(w.mash_iter(map(int, argv[3:])))
1079
868
1080
elif cmd == 'diff':
1081
from difflib import unified_diff
1082
w = readit()
1083
fn = argv[2]
1084
v1, v2 = map(int, argv[3:5])
1085
lines1 = w.get(v1)
1086
lines2 = w.get(v2)
1087
diff_gen = unified_diff(lines1, lines2,
1088
'%s version %d' % (fn, v1),
1089
'%s version %d' % (fn, v2))
1090
sys.stdout.writelines(diff_gen)
1091
1092
869
elif cmd == 'annotate':
1093
870
w = readit()
1094
871
# newline is added to all lines regardless; too hard to get
1106
883
weave_toc(readit())
1107
884
1108
885
elif cmd == 'stats':
1109
weave_stats(argv[2], ProgressBar())
886
weave_stats(argv[2])
1110
887
1111
888
elif cmd == 'check':
1112
889
w = readit()
Loggerhead is a web-based interface for Breezy
Version: 2.0.1