« back to all changes in this revision
Viewing changes to bzrlib/weave.py
- browse files at revision 1429
- compare with another revision
- download diff
- download tarball
- view history from revision 1429
- Committer: Robert Collins
- Date: 2005-10-09 23:42:12 UTC
- Revision ID: robertc@robertcollins.net-20051009234212-7973344d900afb0b
merge in niemeyers prefixed-store patch
- files added:
- NEWS.developers
- bzrlib/store
- bzrlib/transport
- files removed:
- bzrlib/meta_store.py
- files renamed:
- tools/testweave.py => bzrlib/selftest/test_weave.py
- bzrlib/store.py => bzrlib/store/__init__.py
- bzrlib/weavestore.py => bzrlib/store/weave.py
- tools/history2weaves.py => bzrlib/upgrade.py
- files modified:
- .bzrignore
- setup.py *
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?
55
24
56
25
# XXX: If we do weaves this way, will a merge still behave the same
57
26
# way if it's done in a different order? That's a pretty desirable
74
43
75
44
# TODO: Parallel-extract that passes back each line along with a
76
45
# description of which revisions include it. Nice for checking all
77
# shas in parallel.
46
# shas or calculating stats in parallel.
78
47
79
48
# TODO: Using a single _extract routine and then processing the output
80
49
# is probably inefficient. It's simple enough that we can afford to
84
53
# TODO: Perhaps the API should work only in names to hide the integer
85
54
# indexes from the user?
86
55
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
87
72
88
73
89
74
import sha
90
from cStringIO import StringIO
75
from difflib import SequenceMatcher
76
77
from bzrlib.trace import mutter
91
78
92
79
93
80
class WeaveError(Exception):
96
83
97
84
class WeaveFormatError(WeaveError):
98
85
"""Weave invariant violated"""
86
87
88
class WeaveParentMismatch(WeaveError):
89
"""Parents are mismatched between two revisions."""
99
90
100
91
101
92
class Weave(object):
113
104
114
105
* a nonnegative index number.
115
106
116
* a version-id string. (not implemented yet)
107
* a version-id string.
117
108
118
109
Typically the index number will be valid only inside this weave and
119
110
the version-id is used to reference it in the larger world.
199
190
self._weave_name = weave_name
200
191
201
192
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
202
206
def __eq__(self, other):
203
207
if not isinstance(other, Weave):
204
208
return False
211
215
return not self.__eq__(other)
212
216
213
217
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
214
226
def lookup(self, name):
227
"""Convert symbolic version name to index."""
215
228
try:
216
229
return self._name_map[name]
217
230
except KeyError:
218
raise WeaveError("name %s not present in weave %s" %
231
raise WeaveError("name %r not present in weave %r" %
219
232
(name, self._weave_name))
220
233
221
222
def add(self, name, parents, text):
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):
223
260
"""Add a single text on top of the weave.
224
261
225
262
Returns the index number of the newly added version.
232
269
List or set of direct parent version numbers.
233
270
234
271
text
235
Sequence of lines to be added in the new version."""
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
236
278
237
279
assert isinstance(name, basestring)
280
if sha1 is None:
281
sha1 = sha_strings(text)
238
282
if name in self._name_map:
239
raise WeaveError("name %r already present in weave" % name)
240
283
return self._check_repeated_add(name, parents, text, sha1)
284
285
parents = map(self.maybe_lookup, parents)
241
286
self._check_versions(parents)
242
287
## self._check_lines(text)
243
288
new_version = len(self._parents)
244
289
245
s = sha.new()
246
map(s.update, text)
247
sha1 = s.hexdigest()
248
del s
249
290
250
291
# if we abort after here the (in-memory) weave will be corrupt because only
251
292
# some fields are updated
300
341
#print 'basis_lines:', basis_lines
301
342
#print 'new_lines: ', lines
302
343
303
from difflib import SequenceMatcher
304
344
s = SequenceMatcher(None, basis_lines, text)
305
345
306
346
# offset gives the number of lines that have been inserted
341
381
342
382
return new_version
343
383
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)
344
388
345
389
def inclusions(self, versions):
346
390
"""Return set of all ancestors of given version(s)."""
347
391
i = set(versions)
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)
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)])
358
408
359
409
360
410
def minimal_parents(self, version):
400
450
raise IndexError("invalid version number %r" % i)
401
451
402
452
403
def annotate(self, index):
404
return list(self.annotate_iter(index))
405
406
407
def annotate_iter(self, version):
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):
408
458
"""Yield list of (index-id, line) pairs for the specified version.
409
459
410
460
The index indicates when the line originated in the weave."""
411
for origin, lineno, text in self._extract([version]):
461
incls = [self.maybe_lookup(name_or_index)]
462
for origin, lineno, text in self._extract(incls):
412
463
yield origin, text
413
464
414
465
512
563
513
564
514
565
515
def get_iter(self, version):
566
def get_iter(self, name_or_index):
516
567
"""Yield lines for the specified version."""
517
for origin, lineno, line in self._extract([version]):
568
incls = [self.maybe_lookup(name_or_index)]
569
for origin, lineno, line in self._extract(incls):
518
570
yield line
519
571
520
572
521
def get_text(self, version):
573
def get_text(self, name_or_index):
574
return ''.join(self.get_iter(name_or_index))
522
575
assert isinstance(version, int)
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))
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
530
583
531
584
532
585
def mash_iter(self, included):
533
586
"""Return composed version of multiple included versions."""
587
included = map(self.maybe_lookup, included)
534
588
for origin, lineno, text in self._extract(included):
535
589
yield text
536
590
596
650
If there is a chunk of the file where there's no diagreement,
597
651
only one alternative is given.
598
652
"""
599
600
653
# approach: find the included versions common to all the
601
654
# merged versions
602
655
raise NotImplementedError()
622
675
If line1=line2, this is a pure insert; if newlines=[] this is a
623
676
pure delete. (Similar to difflib.)
624
677
"""
625
678
raise NotImplementedError()
626
679
627
680
628
681
def plan_merge(self, ver_a, ver_b):
722
775
state
723
776
724
777
725
726
727
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
728
934
729
935
730
936
def weave_toc(w):
741
947
742
948
743
949
744
def weave_stats(weave_file):
745
from bzrlib.progress import ProgressBar
950
def weave_stats(weave_file, pb):
746
951
from bzrlib.weavefile import read_weave
747
952
748
pb = ProgressBar()
749
750
953
wf = file(weave_file, 'rb')
751
954
w = read_weave(wf)
752
955
# FIXME: doesn't work on pipes
756
959
vers = len(w)
757
960
for i in range(vers):
758
961
pb.update('checking sizes', i, vers)
759
for line in w.get_iter(i):
962
for origin, lineno, line in w._extract([i]):
760
963
total += len(line)
761
964
762
965
pb.clear()
793
996
Display composite of all selected versions.
794
997
weave merge WEAVEFILE VERSION1 VERSION2 > OUT
795
998
Auto-merge two versions and display conflicts.
999
weave diff WEAVEFILE VERSION1 VERSION2
1000
Show differences between two versions.
796
1001
797
1002
example:
798
1003
823
1028
def main(argv):
824
1029
import sys
825
1030
import os
826
from weavefile import write_weave, read_weave
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
827
1038
from bzrlib.progress import ProgressBar
828
1039
829
1040
try:
866
1077
w = readit()
867
1078
sys.stdout.writelines(w.mash_iter(map(int, argv[3:])))
868
1079
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
869
1092
elif cmd == 'annotate':
870
1093
w = readit()
871
1094
# newline is added to all lines regardless; too hard to get
883
1106
weave_toc(readit())
884
1107
885
1108
elif cmd == 'stats':
886
weave_stats(argv[2])
1109
weave_stats(argv[2], ProgressBar())
887
1110
888
1111
elif cmd == 'check':
889
1112
w = readit()
Loggerhead is a web-based interface for Breezy
Version: 2.0.1