« back to all changes in this revision
Viewing changes to weave.py
- browse files at revision 0.1.48
- compare with another revision
- download diff
- download tarball
- view history from revision 0.1.48
- Committer: Martin Pool
- Date: 2005-06-28 09:21:30 UTC
- mto: This revision was merged to the branch mainline in revision 852.
- Revision ID: mbp@sourcefrog.net-20050628092130-b3b669cc920a7cdd
Basic parsing of delete instructions.
Check that they don't interfere with extracting revisions composed only of
insertions.
Check that they don't interfere with extracting revisions composed only of
insertions.
- files added:
- .bzrignore
- files removed:
- .bzrignore
- bzrlib
- bzrlib/plugins
- bzrlib/selftest
- bzrlib/store
- bzrlib/transport
- bzrlib/util
- bzrlib/util/effbot
- bzrlib/util/effbot/org
- bzrlib/util/elementtree
- bzrlib/util/urlgrabber
- contrib
- contrib/bash
- contrib/emacs
- contrib/zsh
- doc
- notes
- patches
- tools
- files renamed:
- bzrlib/selftest/test_weave.py => testweave.py
- bzrlib/weave.py => weave.py
added
removed
weave.py
21
21
22
22
"""Weave - storage of related text file versions"""
23
23
24
25
# XXX: If we do weaves this way, will a merge still behave the same
26
# way if it's done in a different order? That's a pretty desirable
27
# property.
28
29
# TODO: Nothing here so far assumes the lines are really \n newlines,
30
# rather than being split up in some other way. We could accomodate
31
# binaries, perhaps by naively splitting on \n or perhaps using
32
# something like a rolling checksum.
33
34
# TODO: End marker for each version so we can stop reading?
35
36
# TODO: Check that no insertion occurs inside a deletion that was
37
# active in the version of the insertion.
38
39
# TODO: In addition to the SHA-1 check, perhaps have some code that
40
# checks structural constraints of the weave: ie that insertions are
41
# properly nested, that there is no text outside of an insertion, that
42
# insertions or deletions are not repeated, etc.
43
44
# TODO: Parallel-extract that passes back each line along with a
45
# description of which revisions include it. Nice for checking all
46
# shas or calculating stats in parallel.
47
48
# TODO: Using a single _extract routine and then processing the output
49
# is probably inefficient. It's simple enough that we can afford to
50
# have slight specializations for different ways its used: annotate,
51
# basis for add, get, etc.
52
53
# TODO: Probably the API should work only in names to hide the integer
54
# indexes from the user.
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: Reweave can possibly be made faster by remembering diffs
61
# where the basis and destination are unchanged.
62
63
# FIXME: Sometimes we will be given a parents list for a revision
64
# that includes some redundant parents (i.e. already a parent of
65
# something in the list.) We should eliminate them. This can
66
# be done fairly efficiently because the sequence numbers constrain
67
# the possible relationships.
68
69
70
import sha
71
from difflib import SequenceMatcher
72
73
from bzrlib.trace import mutter
24
# TODO: Perhaps have copy and comparison methods of Weave instances?
25
26
27
class VerInfo(object):
28
"""Information about a version in a Weave."""
29
included = frozenset()
30
def __init__(self, included=None):
31
if included:
32
self.included = frozenset(included)
33
34
def __repr__(self):
35
s = self.__class__.__name__ + '('
36
if self.included:
37
s += 'included=%r' % (list(self.included))
38
s += ')'
39
return s
74
40
75
41
76
42
class WeaveError(Exception):
79
45
80
46
class WeaveFormatError(WeaveError):
81
47
"""Weave invariant violated"""
82
83
84
class WeaveParentMismatch(WeaveError):
85
"""Parents are mismatched between two revisions."""
86
48
87
49
88
50
class Weave(object):
89
51
"""weave - versioned text file storage.
90
52
91
A Weave manages versions of line-based text files, keeping track
92
of the originating version for each line.
93
94
To clients the "lines" of the file are represented as a list of strings.
95
These strings will typically have terminal newline characters, but
96
this is not required. In particular files commonly do not have a newline
97
at the end of the file.
53
A Weave manages versions of line-based text files, keeping track of the
54
originating version for each line.
98
55
99
56
Texts can be identified in either of two ways:
100
57
106
63
the version-id is used to reference it in the larger world.
107
64
108
65
The weave is represented as a list mixing edit instructions and
109
literal text. Each entry in _weave can be either a string (or
66
literal text. Each entry in _l can be either a string (or
110
67
unicode), or a tuple. If a string, it means that the given line
111
68
should be output in the currently active revisions.
112
69
117
74
The instruction can be '{' or '}' for an insertion block, and '['
118
75
and ']' for a deletion block respectively. The version is the
119
76
integer version index. There is no replace operator, only deletes
120
and inserts. For '}', the end of an insertion, there is no
121
version parameter because it always closes the most recently
122
opened insertion.
77
and inserts.
123
78
124
79
Constraints/notes:
125
80
147
102
* Lines are enabled if the most recent enclosing insertion is
148
103
active and none of the enclosing deletions are active.
149
104
150
* There is no point having a deletion directly inside its own
151
insertion; you might as well just not write it. And there
152
should be no way to get an earlier version deleting a later
153
version.
154
155
_weave
156
Text of the weave; list of control instruction tuples and strings.
157
158
_parents
159
List of parents, indexed by version number.
160
It is only necessary to store the minimal set of parents for
161
each version; the parent's parents are implied.
162
163
_sha1s
164
List of hex SHA-1 of each version.
165
166
_names
167
List of symbolic names for each version. Each should be unique.
168
169
_name_map
170
For each name, the version number.
171
172
_weave_name
173
Descriptive name of this weave; typically the filename if known.
174
Set by read_weave.
105
106
_l
107
Text of the weave.
108
109
_v
110
List of versions, indexed by index number.
111
112
For each version we store the tuple (included_versions), which
113
lists the previous versions also considered active.
175
114
"""
176
177
__slots__ = ['_weave', '_parents', '_sha1s', '_names', '_name_map',
178
'_weave_name']
179
180
def __init__(self, weave_name=None):
181
self._weave = []
182
self._parents = []
183
self._sha1s = []
184
self._names = []
185
self._name_map = {}
186
self._weave_name = weave_name
187
188
189
def copy(self):
190
"""Return a deep copy of self.
191
192
The copy can be modified without affecting the original weave."""
193
other = Weave()
194
other._weave = self._weave[:]
195
other._parents = self._parents[:]
196
other._sha1s = self._sha1s[:]
197
other._names = self._names[:]
198
other._name_map = self._name_map.copy()
199
other._weave_name = self._weave_name
200
return other
201
202
def __eq__(self, other):
203
if not isinstance(other, Weave):
204
return False
205
return self._parents == other._parents \
206
and self._weave == other._weave \
207
and self._sha1s == other._sha1s
208
209
210
def __ne__(self, other):
211
return not self.__eq__(other)
212
213
214
def maybe_lookup(self, name_or_index):
215
"""Convert possible symbolic name to index, or pass through indexes."""
216
if isinstance(name_or_index, (int, long)):
217
return name_or_index
218
else:
219
return self.lookup(name_or_index)
220
221
222
def lookup(self, name):
223
"""Convert symbolic version name to index."""
224
try:
225
return self._name_map[name]
226
except KeyError:
227
raise WeaveError("name %r not present in weave %r" %
228
(name, self._weave_name))
229
230
231
def iter_names(self):
232
"""Yield a list of all names in this weave."""
233
return iter(self._names)
234
235
def idx_to_name(self, version):
236
return self._names[version]
237
238
239
def _check_repeated_add(self, name, parents, text, sha1):
240
"""Check that a duplicated add is OK.
241
242
If it is, return the (old) index; otherwise raise an exception.
243
"""
244
idx = self.lookup(name)
245
if sorted(self._parents[idx]) != sorted(parents):
246
raise WeaveError("name \"%s\" already present in weave "
247
"with different parents" % name)
248
if sha1 != self._sha1s[idx]:
249
raise WeaveError("name \"%s\" already present in weave "
250
"with different text" % name)
251
return idx
252
253
254
255
def add(self, name, parents, text, sha1=None):
115
def __init__(self):
116
self._l = []
117
self._v = []
118
119
120
def add(self, parents, text):
256
121
"""Add a single text on top of the weave.
257
122
258
123
Returns the index number of the newly added version.
259
124
260
name
261
Symbolic name for this version.
262
(Typically the revision-id of the revision that added it.)
263
264
125
parents
265
List or set of direct parent version numbers.
266
126
List or set of parent version numbers.
127
267
128
text
268
Sequence of lines to be added in the new version.
269
270
sha -- SHA-1 of the file, if known. This is trusted to be
271
correct if supplied.
272
"""
273
from bzrlib.osutils import sha_strings
274
275
assert isinstance(name, basestring)
276
if sha1 is None:
277
sha1 = sha_strings(text)
278
if name in self._name_map:
279
return self._check_repeated_add(name, parents, text, sha1)
280
281
parents = map(self.maybe_lookup, parents)
129
Sequence of lines to be added in the new version."""
282
130
self._check_versions(parents)
283
## self._check_lines(text)
284
new_version = len(self._parents)
285
286
287
# if we abort after here the (in-memory) weave will be corrupt because only
288
# some fields are updated
289
self._parents.append(parents[:])
290
self._sha1s.append(sha1)
291
self._names.append(name)
292
self._name_map[name] = new_version
293
294
295
if not parents:
296
# special case; adding with no parents revision; can do
297
# this more quickly by just appending unconditionally.
298
# even more specially, if we're adding an empty text we
299
# need do nothing at all.
300
if text:
301
self._weave.append(('{', new_version))
302
self._weave.extend(text)
303
self._weave.append(('}', None))
304
305
return new_version
306
307
if len(parents) == 1:
308
pv = list(parents)[0]
309
if sha1 == self._sha1s[pv]:
310
# special case: same as the single parent
311
return new_version
312
313
314
ancestors = self.inclusions(parents)
315
316
l = self._weave
317
318
# basis a list of (origin, lineno, line)
319
basis_lineno = []
320
basis_lines = []
321
for origin, lineno, line in self._extract(ancestors):
322
basis_lineno.append(lineno)
323
basis_lines.append(line)
324
325
# another small special case: a merge, producing the same text
326
# as auto-merge
327
if text == basis_lines:
328
return new_version
329
330
# add a sentinal, because we can also match against the final line
331
basis_lineno.append(len(self._weave))
332
333
# XXX: which line of the weave should we really consider
334
# matches the end of the file? the current code says it's the
335
# last line of the weave?
336
337
#print 'basis_lines:', basis_lines
338
#print 'new_lines: ', lines
339
340
s = SequenceMatcher(None, basis_lines, text)
341
342
# offset gives the number of lines that have been inserted
343
# into the weave up to the current point; if the original edit instruction
344
# says to change line A then we actually change (A+offset)
345
offset = 0
346
347
for tag, i1, i2, j1, j2 in s.get_opcodes():
348
# i1,i2 are given in offsets within basis_lines; we need to map them
349
# back to offsets within the entire weave
350
#print 'raw match', tag, i1, i2, j1, j2
351
if tag == 'equal':
352
continue
353
354
i1 = basis_lineno[i1]
355
i2 = basis_lineno[i2]
356
357
assert 0 <= j1 <= j2 <= len(text)
358
359
#print tag, i1, i2, j1, j2
360
361
# the deletion and insertion are handled separately.
362
# first delete the region.
363
if i1 != i2:
364
self._weave.insert(i1+offset, ('[', new_version))
365
self._weave.insert(i2+offset+1, (']', new_version))
366
offset += 2
367
368
if j1 != j2:
369
# there may have been a deletion spanning up to
370
# i2; we want to insert after this region to make sure
371
# we don't destroy ourselves
372
i = i2 + offset
373
self._weave[i:i] = ([('{', new_version)]
374
+ text[j1:j2]
375
+ [('}', None)])
376
offset += 2 + (j2 - j1)
377
378
return new_version
379
380
def add_identical(self, old_rev_id, new_rev_id, parents):
381
"""Add an identical text to old_rev_id as new_rev_id."""
382
old_lines = self.get(self.lookup(old_rev_id))
383
self.add(new_rev_id, parents, old_lines)
384
385
def inclusions(self, versions):
386
"""Return set of all ancestors of given version(s)."""
387
i = set(versions)
388
for v in xrange(max(versions), 0, -1):
389
if v in i:
390
# include all its parents
391
i.update(self._parents[v])
392
return i
393
## except IndexError:
394
## raise ValueError("version %d not present in weave" % v)
395
396
397
def parents(self, version):
398
return self._parents[version]
399
400
401
def parent_names(self, version):
402
"""Return version names for parents of a version."""
403
return map(self.idx_to_name, self._parents[self.lookup(version)])
404
405
406
def minimal_parents(self, version):
407
"""Find the minimal set of parents for the version."""
408
included = self._parents[version]
409
if not included:
410
return []
411
412
li = list(included)
413
li.sort(reverse=True)
414
415
mininc = []
416
gotit = set()
417
418
for pv in li:
419
if pv not in gotit:
420
mininc.append(pv)
421
gotit.update(self.inclusions(pv))
422
423
assert mininc[0] >= 0
424
assert mininc[-1] < version
425
return mininc
426
131
self._check_lines(text)
132
133
idx = len(self._v)
134
135
if parents:
136
parents = frozenset(parents)
137
delta = self._delta(parents, text)
138
139
# offset gives the number of lines that have been inserted
140
# into the weave up to the current point; if the original edit instruction
141
# says to change line A then we actually change (A+offset)
142
offset = 0
143
144
for i1, i2, newlines in delta:
145
assert 0 <= i1
146
assert i1 <= i2
147
assert i2 <= len(self._l)
148
149
if i1 != i2:
150
raise NotImplementedError("can't handle replacing weave [%d:%d] yet"
151
% (i1, i2))
152
153
self._l.insert(i1 + offset, ('{', idx))
154
i = i1 + offset + 1
155
self._l[i:i] = newlines
156
self._l.insert(i + 1, ('}', idx))
157
offset += 2 + len(newlines)
158
159
self._v.append(VerInfo(parents))
160
else:
161
# special case; adding with no parents revision; can do this
162
# more quickly by just appending unconditionally
163
self._l.append(('{', idx))
164
self._l += text
165
self._l.append(('}', idx))
166
167
self._v.append(VerInfo())
168
169
return idx
427
170
428
171
429
172
def _check_lines(self, text):
432
175
433
176
for l in text:
434
177
if not isinstance(l, basestring):
435
raise ValueError("text line should be a string or unicode, not %s"
436
% type(l))
178
raise ValueError("text line should be a string or unicode, not %s" % type(l))
437
179
438
180
439
181
441
183
"""Check everything in the sequence of indexes is valid"""
442
184
for i in indexes:
443
185
try:
444
self._parents[i]
186
self._v[i]
445
187
except IndexError:
446
188
raise IndexError("invalid version number %r" % i)
447
189
448
190
449
def annotate(self, name_or_index):
450
return list(self.annotate_iter(name_or_index))
451
452
453
def annotate_iter(self, name_or_index):
191
def annotate(self, index):
192
return list(self.annotate_iter(index))
193
194
195
def annotate_iter(self, index):
454
196
"""Yield list of (index-id, line) pairs for the specified version.
455
197
456
198
The index indicates when the line originated in the weave."""
457
incls = [self.maybe_lookup(name_or_index)]
458
for origin, lineno, text in self._extract(incls):
199
try:
200
vi = self._v[index]
201
except IndexError:
202
raise IndexError('version index %d out of range' % index)
203
included = set(vi.included)
204
included.add(index)
205
for origin, lineno, text in self._extract(included):
459
206
yield origin, text
460
207
461
208
462
def _walk(self):
463
"""Walk the weave.
464
465
Yields sequence of
466
(lineno, insert, deletes, text)
467
for each literal line.
468
"""
469
470
istack = []
471
dset = set()
472
473
lineno = 0 # line of weave, 0-based
474
475
for l in self._weave:
476
if isinstance(l, tuple):
477
c, v = l
478
isactive = None
479
if c == '{':
480
istack.append(v)
481
elif c == '}':
482
istack.pop()
483
elif c == '[':
484
assert v not in dset
485
dset.add(v)
486
elif c == ']':
487
dset.remove(v)
488
else:
489
raise WeaveFormatError('unexpected instruction %r'
490
% v)
491
else:
492
assert isinstance(l, basestring)
493
assert istack
494
yield lineno, istack[-1], dset, l
495
lineno += 1
496
497
498
499
def _extract(self, versions):
209
def _extract(self, included):
500
210
"""Yield annotation of lines in included set.
501
211
502
212
Yields a sequence of tuples (origin, lineno, text), where
505
215
506
216
The set typically but not necessarily corresponds to a version.
507
217
"""
508
for i in versions:
509
if not isinstance(i, int):
510
raise ValueError(i)
511
512
included = self.inclusions(versions)
513
514
istack = []
515
dset = set()
218
istack = [] # versions for which an insertion block is current
219
220
dset = set() # versions for which a deletion block is current
221
222
isactive = False
516
223
517
224
lineno = 0 # line of weave, 0-based
518
519
isactive = None
520
521
result = []
522
523
WFE = WeaveFormatError
524
525
for l in self._weave:
225
226
for l in self._l:
526
227
if isinstance(l, tuple):
527
228
c, v = l
528
isactive = None
529
229
if c == '{':
530
assert v not in istack
230
if istack and (istack[-1] >= v):
231
raise WeaveFormatError("improperly nested insertions %d>=%d on line %d"
232
% (istack[-1], v, lineno))
531
233
istack.append(v)
532
234
elif c == '}':
533
istack.pop()
235
try:
236
oldv = istack.pop()
237
except IndexError:
238
raise WeaveFormatError("unmatched close of insertion %d on line %d"
239
% (v, lineno))
240
if oldv != v:
241
raise WeaveFormatError("mismatched close of insertion %d!=%d on line %d"
242
% (oldv, v, lineno))
534
243
elif c == '[':
535
if v in included:
536
assert v not in dset
244
# block deleted in v
245
if v in dset:
246
raise WeaveFormatError("repeated deletion marker for version %d on line %d"
247
% (v, lineno))
248
else:
537
249
dset.add(v)
538
else:
539
assert c == ']'
540
if v in included:
541
assert v in dset
250
elif c == ']':
251
if v in dset:
542
252
dset.remove(v)
253
else:
254
raise WeaveFormatError("unmatched close of deletion %d on line %d"
255
% (v, lineno))
256
else:
257
raise WeaveFormatError("invalid processing instruction %r on line %d"
258
% (l, lineno))
543
259
else:
544
260
assert isinstance(l, basestring)
545
if isactive is None:
546
isactive = (not dset) and istack and (istack[-1] in included)
261
if not istack:
262
raise WeaveFormatError("literal at top level on line %d"
263
% lineno)
264
isactive = istack[-1] in included
547
265
if isactive:
548
result.append((istack[-1], lineno, l))
266
origin = istack[-1]
267
yield origin, lineno, l
549
268
lineno += 1
550
269
551
270
if istack:
552
raise WFE("unclosed insertion blocks at end of weave",
271
raise WeaveFormatError("unclosed insertion blocks at end of weave",
553
272
istack)
554
273
if dset:
555
raise WFE("unclosed deletion blocks at end of weave",
274
raise WeaveFormatError("unclosed deletion blocks at end of weave",
556
275
dset)
557
276
558
return result
559
560
561
562
def get_iter(self, name_or_index):
277
278
def getiter(self, index):
563
279
"""Yield lines for the specified version."""
564
incls = [self.maybe_lookup(name_or_index)]
565
for origin, lineno, line in self._extract(incls):
280
for origin, line in self.annotate_iter(index):
566
281
yield line
567
282
568
283
569
def get_text(self, name_or_index):
570
return ''.join(self.get_iter(name_or_index))
571
assert isinstance(version, int)
572
573
574
def get_lines(self, name_or_index):
575
return list(self.get_iter(name_or_index))
576
577
578
get = get_lines
579
580
581
def mash_iter(self, included):
582
"""Return composed version of multiple included versions."""
583
included = map(self.maybe_lookup, included)
584
for origin, lineno, text in self._extract(included):
585
yield text
284
def get(self, index):
285
return list(self.getiter(index))
586
286
587
287
588
288
def dump(self, to_file):
589
289
from pprint import pprint
590
print >>to_file, "Weave._weave = ",
591
pprint(self._weave, to_file)
592
print >>to_file, "Weave._parents = ",
593
pprint(self._parents, to_file)
594
595
596
597
def numversions(self):
598
l = len(self._parents)
599
assert l == len(self._sha1s)
600
return l
601
602
603
def __len__(self):
604
return self.numversions()
605
606
607
def check(self, progress_bar=None):
608
# check no circular inclusions
609
for version in range(self.numversions()):
610
inclusions = list(self._parents[version])
611
if inclusions:
612
inclusions.sort()
613
if inclusions[-1] >= version:
290
print >>to_file, "Weave._l = ",
291
pprint(self._l, to_file)
292
print >>to_file, "Weave._v = ",
293
pprint(self._v, to_file)
294
295
296
def check(self):
297
for vers_info in self._v:
298
included = set()
299
for vi in vers_info[0]:
300
if vi < 0 or vi >= index:
614
301
raise WeaveFormatError("invalid included version %d for index %d"
615
% (inclusions[-1], version))
616
617
# try extracting all versions; this is a bit slow and parallel
618
# extraction could be used
619
nv = self.numversions()
620
for version in range(nv):
621
if progress_bar:
622
progress_bar.update('checking text', version, nv)
623
s = sha.new()
624
for l in self.get_iter(version):
625
s.update(l)
626
hd = s.hexdigest()
627
expected = self._sha1s[version]
628
if hd != expected:
629
raise WeaveError("mismatched sha1 for version %d; "
630
"got %s, expected %s"
631
% (version, hd, expected))
632
633
# TODO: check insertions are properly nested, that there are
634
# no lines outside of insertion blocks, that deletions are
635
# properly paired, etc.
636
637
638
639
def merge(self, merge_versions):
640
"""Automerge and mark conflicts between versions.
641
642
This returns a sequence, each entry describing alternatives
643
for a chunk of the file. Each of the alternatives is given as
644
a list of lines.
645
646
If there is a chunk of the file where there's no diagreement,
647
only one alternative is given.
648
"""
649
# approach: find the included versions common to all the
650
# merged versions
651
raise NotImplementedError()
302
% (vi, index))
303
if vi in included:
304
raise WeaveFormatError("repeated included version %d for index %d"
305
% (vi, index))
306
included.add(vi)
652
307
653
308
654
309
659
314
660
315
This is used in inserting a new text.
661
316
662
Delta is returned as a sequence of
663
(weave1, weave2, newlines).
664
665
This indicates that weave1:weave2 of the old weave should be
317
Delta is returned as a sequence of (line1, line2, newlines),
318
indicating that line1 through line2 of the old weave should be
666
319
replaced by the sequence of lines in newlines. Note that
667
320
these line numbers are positions in the total weave and don't
668
321
correspond to the lines in any extracted version, or even the
671
324
If line1=line2, this is a pure insert; if newlines=[] this is a
672
325
pure delete. (Similar to difflib.)
673
326
"""
674
raise NotImplementedError()
675
676
677
def plan_merge(self, ver_a, ver_b):
678
"""Return pseudo-annotation indicating how the two versions merge.
679
680
This is computed between versions a and b and their common
681
base.
682
683
Weave lines present in none of them are skipped entirely.
684
"""
685
inc_a = self.inclusions([ver_a])
686
inc_b = self.inclusions([ver_b])
687
inc_c = inc_a & inc_b
688
689
for lineno, insert, deleteset, line in self._walk():
690
if deleteset & inc_c:
691
# killed in parent; can't be in either a or b
692
# not relevant to our work
693
yield 'killed-base', line
694
elif insert in inc_c:
695
# was inserted in base
696
killed_a = bool(deleteset & inc_a)
697
killed_b = bool(deleteset & inc_b)
698
if killed_a and killed_b:
699
yield 'killed-both', line
700
elif killed_a:
701
yield 'killed-a', line
702
elif killed_b:
703
yield 'killed-b', line
704
else:
705
yield 'unchanged', line
706
elif insert in inc_a:
707
if deleteset & inc_a:
708
yield 'ghost-a', line
709
else:
710
# new in A; not in B
711
yield 'new-a', line
712
elif insert in inc_b:
713
if deleteset & inc_b:
714
yield 'ghost-b', line
715
else:
716
yield 'new-b', line
717
else:
718
# not in either revision
719
yield 'irrelevant', line
720
721
yield 'unchanged', '' # terminator
722
723
724
725
def weave_merge(self, plan):
726
lines_a = []
727
lines_b = []
728
ch_a = ch_b = False
729
730
for state, line in plan:
731
if state == 'unchanged' or state == 'killed-both':
732
# resync and flush queued conflicts changes if any
733
if not lines_a and not lines_b:
734
pass
735
elif ch_a and not ch_b:
736
# one-sided change:
737
for l in lines_a: yield l
738
elif ch_b and not ch_a:
739
for l in lines_b: yield l
740
elif lines_a == lines_b:
741
for l in lines_a: yield l
742
else:
743
yield '<<<<\n'
744
for l in lines_a: yield l
745
yield '====\n'
746
for l in lines_b: yield l
747
yield '>>>>\n'
748
749
del lines_a[:]
750
del lines_b[:]
751
ch_a = ch_b = False
752
753
if state == 'unchanged':
754
if line:
755
yield line
756
elif state == 'killed-a':
757
ch_a = True
758
lines_b.append(line)
759
elif state == 'killed-b':
760
ch_b = True
761
lines_a.append(line)
762
elif state == 'new-a':
763
ch_a = True
764
lines_a.append(line)
765
elif state == 'new-b':
766
ch_b = True
767
lines_b.append(line)
768
else:
769
assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
770
'killed-both'), \
771
state
772
773
774
def join(self, other):
775
"""Integrate versions from other into this weave.
776
777
The resulting weave contains all the history of both weaves;
778
any version you could retrieve from either self or other can be
779
retrieved from self after this call.
780
781
It is illegal for the two weaves to contain different values
782
or different parents for any version. See also reweave().
783
"""
784
if other.numversions() == 0:
785
return # nothing to update, easy
786
# two loops so that we do not change ourselves before verifying it
787
# will be ok
788
# work through in index order to make sure we get all dependencies
789
for other_idx, name in enumerate(other._names):
790
if self._check_version_consistent(other, other_idx, name):
791
continue
792
for other_idx, name in enumerate(other._names):
793
# TODO: If all the parents of the other version are already
794
# present then we can avoid some work by just taking the delta
795
# and adjusting the offsets.
796
new_parents = self._imported_parents(other, other_idx)
797
lines = other.get_lines(other_idx)
798
sha1 = other._sha1s[other_idx]
799
self.add(name, new_parents, lines, sha1)
800
801
802
def _imported_parents(self, other, other_idx):
803
"""Return list of parents in self corresponding to indexes in other."""
804
new_parents = []
805
for parent_idx in other._parents[other_idx]:
806
parent_name = other._names[parent_idx]
807
if parent_name not in self._names:
808
# should not be possible
809
raise WeaveError("missing parent {%s} of {%s} in %r"
810
% (parent_name, other._name_map[other_idx], self))
811
new_parents.append(self._name_map[parent_name])
812
return new_parents
813
814
def _check_version_consistent(self, other, other_idx, name):
815
"""Check if a version in consistent in this and other.
816
817
To be consistent it must have:
818
819
* the same text
820
* the same direct parents (by name, not index, and disregarding
821
order)
822
823
If present & correct return True;
824
if not present in self return False;
825
if inconsistent raise error."""
826
this_idx = self._name_map.get(name, -1)
827
if this_idx != -1:
828
if self._sha1s[this_idx] != other._sha1s[other_idx]:
829
raise WeaveError("inconsistent texts for version {%s} "
830
"when joining weaves"
831
% (name))
832
self_parents = self._parents[this_idx]
833
other_parents = other._parents[other_idx]
834
n1 = [self._names[i] for i in self_parents]
835
n2 = [other._names[i] for i in other_parents]
836
n1.sort()
837
n2.sort()
838
if n1 != n2:
839
raise WeaveParentMismatch("inconsistent parents "
840
"for version {%s}: %s vs %s" % (name, n1, n2))
841
else:
842
return True # ok!
843
else:
844
return False
845
846
def reweave(self, other):
847
"""Reweave self with other."""
848
new_weave = reweave(self, other)
849
for attr in self.__slots__:
850
setattr(self, attr, getattr(new_weave, attr))
851
852
853
def reweave(wa, wb):
854
"""Combine two weaves and return the result.
855
856
This works even if a revision R has different parents in
857
wa and wb. In the resulting weave all the parents are given.
858
859
This is done by just building up a new weave, maintaining ordering
860
of the versions in the two inputs. More efficient approaches
861
might be possible but it should only be necessary to do
862
this operation rarely, when a new previously ghost version is
863
inserted.
864
"""
865
wr = Weave()
866
ia = ib = 0
867
queue_a = range(wa.numversions())
868
queue_b = range(wb.numversions())
869
# first determine combined parents of all versions
870
# map from version name -> all parent names
871
combined_parents = _reweave_parent_graphs(wa, wb)
872
mutter("combined parents: %r", combined_parents)
873
order = _make_reweave_order(wa._names, wb._names, combined_parents)
874
mutter("order to reweave: %r", order)
875
for name in order:
876
if name in wa._name_map:
877
lines = wa.get_lines(name)
878
if name in wb._name_map:
879
assert lines == wb.get_lines(name)
880
else:
881
lines = wb.get_lines(name)
882
wr.add(name, combined_parents[name], lines)
883
return wr
884
885
886
def _reweave_parent_graphs(wa, wb):
887
"""Return combined parent ancestry for two weaves.
888
889
Returned as a list of (version_name, set(parent_names))"""
890
combined = {}
891
for weave in [wa, wb]:
892
for idx, name in enumerate(weave._names):
893
p = combined.setdefault(name, set())
894
p.update(map(weave.idx_to_name, weave._parents[idx]))
895
return combined
896
897
898
def _make_reweave_order(wa_order, wb_order, combined_parents):
899
"""Return an order to reweave versions respecting parents."""
900
done = set()
901
result = []
902
ia = ib = 0
903
next_a = next_b = None
904
len_a = len(wa_order)
905
len_b = len(wb_order)
906
while ia < len(wa_order) or ib < len(wb_order):
907
if ia < len_a:
908
next_a = wa_order[ia]
909
if next_a in done:
910
ia += 1
911
continue
912
if combined_parents[next_a].issubset(done):
913
ia += 1
914
result.append(next_a)
915
done.add(next_a)
916
continue
917
if ib < len_b:
918
next_b = wb_order[ib]
919
if next_b in done:
920
ib += 1
921
continue
922
elif combined_parents[next_b].issubset(done):
923
ib += 1
924
result.append(next_b)
925
done.add(next_b)
926
continue
927
raise WeaveError("don't know how to reweave at {%s} and {%s}"
928
% (next_a, next_b))
929
return result
930
931
932
def weave_toc(w):
933
"""Show the weave's table-of-contents"""
934
print '%6s %50s %10s %10s' % ('ver', 'name', 'sha1', 'parents')
935
for i in (6, 50, 10, 10):
936
print '-' * i,
937
print
938
for i in range(w.numversions()):
939
sha1 = w._sha1s[i]
940
name = w._names[i]
941
parent_str = ' '.join(map(str, w._parents[i]))
942
print '%6d %-50.50s %10.10s %s' % (i, name, sha1, parent_str)
943
944
945
946
def weave_stats(weave_file, pb):
947
from bzrlib.weavefile import read_weave
948
949
wf = file(weave_file, 'rb')
950
w = read_weave(wf)
951
# FIXME: doesn't work on pipes
952
weave_size = wf.tell()
953
954
total = 0
955
vers = len(w)
956
for i in range(vers):
957
pb.update('checking sizes', i, vers)
958
for origin, lineno, line in w._extract([i]):
959
total += len(line)
960
961
pb.clear()
962
963
print 'versions %9d' % vers
964
print 'weave file %9d bytes' % weave_size
965
print 'total contents %9d bytes' % total
966
print 'compression ratio %9.2fx' % (float(total) / float(weave_size))
967
if vers:
968
avg = total/vers
969
print 'average size %9d bytes' % avg
970
print 'relative size %9.2fx' % (float(weave_size) / float(avg))
971
972
973
def usage():
974
print """bzr weave tool
975
976
Experimental tool for weave algorithm.
977
978
usage:
979
weave init WEAVEFILE
980
Create an empty weave file
981
weave get WEAVEFILE VERSION
982
Write out specified version.
983
weave check WEAVEFILE
984
Check consistency of all versions.
985
weave toc WEAVEFILE
986
Display table of contents.
987
weave add WEAVEFILE NAME [BASE...] < NEWTEXT
988
Add NEWTEXT, with specified parent versions.
989
weave annotate WEAVEFILE VERSION
990
Display origin of each line.
991
weave mash WEAVEFILE VERSION...
992
Display composite of all selected versions.
993
weave merge WEAVEFILE VERSION1 VERSION2 > OUT
994
Auto-merge two versions and display conflicts.
995
weave diff WEAVEFILE VERSION1 VERSION2
996
Show differences between two versions.
997
998
example:
999
1000
% weave init foo.weave
1001
% vi foo.txt
1002
% weave add foo.weave ver0 < foo.txt
1003
added version 0
1004
1005
(create updated version)
1006
% vi foo.txt
1007
% weave get foo.weave 0 | diff -u - foo.txt
1008
% weave add foo.weave ver1 0 < foo.txt
1009
added version 1
1010
1011
% weave get foo.weave 0 > foo.txt (create forked version)
1012
% vi foo.txt
1013
% weave add foo.weave ver2 0 < foo.txt
1014
added version 2
1015
1016
% weave merge foo.weave 1 2 > foo.txt (merge them)
1017
% vi foo.txt (resolve conflicts)
1018
% weave add foo.weave merged 1 2 < foo.txt (commit merged version)
1019
1020
"""
1021
1022
1023
1024
def main(argv):
1025
import sys
1026
import os
1027
try:
1028
import bzrlib
1029
except ImportError:
1030
# in case we're run directly from the subdirectory
1031
sys.path.append('..')
1032
import bzrlib
1033
from bzrlib.weavefile import write_weave, read_weave
1034
from bzrlib.progress import ProgressBar
1035
1036
try:
1037
import psyco
1038
psyco.full()
1039
except ImportError:
1040
pass
1041
1042
if len(argv) < 2:
1043
usage()
1044
return 0
1045
1046
cmd = argv[1]
1047
1048
def readit():
1049
return read_weave(file(argv[2], 'rb'))
1050
1051
if cmd == 'help':
1052
usage()
1053
elif cmd == 'add':
1054
w = readit()
1055
# at the moment, based on everything in the file
1056
name = argv[3]
1057
parents = map(int, argv[4:])
1058
lines = sys.stdin.readlines()
1059
ver = w.add(name, parents, lines)
1060
write_weave(w, file(argv[2], 'wb'))
1061
print 'added version %r %d' % (name, ver)
1062
elif cmd == 'init':
1063
fn = argv[2]
1064
if os.path.exists(fn):
1065
raise IOError("file exists")
1066
w = Weave()
1067
write_weave(w, file(fn, 'wb'))
1068
elif cmd == 'get': # get one version
1069
w = readit()
1070
sys.stdout.writelines(w.get_iter(int(argv[3])))
1071
1072
elif cmd == 'mash': # get composite
1073
w = readit()
1074
sys.stdout.writelines(w.mash_iter(map(int, argv[3:])))
1075
1076
elif cmd == 'diff':
1077
from difflib import unified_diff
1078
w = readit()
1079
fn = argv[2]
1080
v1, v2 = map(int, argv[3:5])
1081
lines1 = w.get(v1)
1082
lines2 = w.get(v2)
1083
diff_gen = unified_diff(lines1, lines2,
1084
'%s version %d' % (fn, v1),
1085
'%s version %d' % (fn, v2))
1086
sys.stdout.writelines(diff_gen)
1087
1088
elif cmd == 'annotate':
1089
w = readit()
1090
# newline is added to all lines regardless; too hard to get
1091
# reasonable formatting otherwise
1092
lasto = None
1093
for origin, text in w.annotate(int(argv[3])):
1094
text = text.rstrip('\r\n')
1095
if origin == lasto:
1096
print ' | %s' % (text)
1097
else:
1098
print '%5d | %s' % (origin, text)
1099
lasto = origin
1100
1101
elif cmd == 'toc':
1102
weave_toc(readit())
1103
1104
elif cmd == 'stats':
1105
weave_stats(argv[2], ProgressBar())
1106
1107
elif cmd == 'check':
1108
w = readit()
1109
pb = ProgressBar()
1110
w.check(pb)
1111
pb.clear()
1112
print '%d versions ok' % w.numversions()
1113
1114
elif cmd == 'inclusions':
1115
w = readit()
1116
print ' '.join(map(str, w.inclusions([int(argv[3])])))
1117
1118
elif cmd == 'parents':
1119
w = readit()
1120
print ' '.join(map(str, w._parents[int(argv[3])]))
1121
1122
elif cmd == 'plan-merge':
1123
w = readit()
1124
for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
1125
if line:
1126
print '%14s | %s' % (state, line),
1127
1128
elif cmd == 'merge':
1129
w = readit()
1130
p = w.plan_merge(int(argv[3]), int(argv[4]))
1131
sys.stdout.writelines(w.weave_merge(p))
1132
1133
elif cmd == 'mash-merge':
1134
if len(argv) != 5:
1135
usage()
1136
return 1
1137
1138
w = readit()
1139
v1, v2 = map(int, argv[3:5])
1140
1141
basis = w.inclusions([v1]).intersection(w.inclusions([v2]))
1142
1143
base_lines = list(w.mash_iter(basis))
1144
a_lines = list(w.get(v1))
1145
b_lines = list(w.get(v2))
1146
1147
from bzrlib.merge3 import Merge3
1148
m3 = Merge3(base_lines, a_lines, b_lines)
1149
1150
name_a = 'version %d' % v1
1151
name_b = 'version %d' % v2
1152
sys.stdout.writelines(m3.merge_lines(name_a=name_a, name_b=name_b))
1153
else:
1154
raise ValueError('unknown command %r' % cmd)
1155
1156
1157
1158
def profile_main(argv):
1159
import tempfile, hotshot, hotshot.stats
1160
1161
prof_f = tempfile.NamedTemporaryFile()
1162
1163
prof = hotshot.Profile(prof_f.name)
1164
1165
ret = prof.runcall(main, argv)
1166
prof.close()
1167
1168
stats = hotshot.stats.load(prof_f.name)
1169
#stats.strip_dirs()
1170
stats.sort_stats('cumulative')
1171
## XXX: Might like to write to stderr or the trace file instead but
1172
## print_stats seems hardcoded to stdout
1173
stats.print_stats(20)
1174
1175
return ret
1176
1177
1178
if __name__ == '__main__':
1179
import sys
1180
if '--profile' in sys.argv:
1181
args = sys.argv[:]
1182
args.remove('--profile')
1183
sys.exit(profile_main(args))
1184
else:
1185
sys.exit(main(sys.argv))
327
328
self._check_versions(included)
329
330
##from pprint import pprint
331
332
# first get basis for comparison
333
# basis holds (lineno, origin, line)
334
basis = []
335
336
##print 'my lines:'
337
##pprint(self._l)
338
339
basis = list(self._extract(included))
340
341
# now make a parallel list with only the text, to pass to the differ
342
basis_lines = [line for (origin, lineno, line) in basis]
343
344
# add a sentinal, because we can also match against the final line
345
basis.append((len(self._l), None))
346
347
# XXX: which line of the weave should we really consider matches the end of the file?
348
# the current code says it's the last line of the weave?
349
350
from difflib import SequenceMatcher
351
s = SequenceMatcher(None, basis_lines, lines)
352
353
##print 'basis sequence:'
354
##pprint(basis)
355
356
for tag, i1, i2, j1, j2 in s.get_opcodes():
357
##print tag, i1, i2, j1, j2
358
359
if tag == 'equal':
360
continue
361
362
# i1,i2 are given in offsets within basis_lines; we need to map them
363
# back to offsets within the entire weave
364
real_i1 = basis[i1][0]
365
real_i2 = basis[i2][0]
366
367
assert 0 <= j1
368
assert j1 <= j2
369
assert j2 <= len(lines)
370
371
yield real_i1, real_i2, lines[j1:j2]
372
1186
373
Loggerhead is a web-based interface for Breezy
Version: 2.0.1