« back to all changes in this revision
Viewing changes to weave.py
- browse files at revision 0.1.85
- compare with another revision
- download diff
- download tarball
- view history from revision 0.1.85
- Committer: Martin Pool
- Date: 2005-06-30 10:00:57 UTC
- mto: This revision was merged to the branch mainline in revision 852.
- Revision ID: mbp@sourcefrog.net-20050630100057-32a93074b0f1faa8
doc
- 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:
- tools/convertfile.py => convertfile.py
- tools/convertinv.py => convertinv.py
- bzrlib/selftest/test_weave.py => testweave.py
- bzrlib/weave.py => weave.py
- bzrlib/weavefile.py => weavefile.py
added
removed
weave.py
21
21
22
22
"""Weave - storage of related text file versions"""
23
23
24
# TODO: Perhaps have copy method for Weave instances?
24
25
25
26
# XXX: If we do weaves this way, will a merge still behave the same
26
27
# way if it's done in a different order? That's a pretty desirable
27
28
# property.
28
29
30
# TODO: How to write these to disk? One option is cPickle, which
31
# would be fast but less friendly to C, and perhaps not portable. Another is
32
29
33
# TODO: Nothing here so far assumes the lines are really \n newlines,
30
34
# rather than being split up in some other way. We could accomodate
31
35
# binaries, perhaps by naively splitting on \n or perhaps using
32
36
# something like a rolling checksum.
33
37
38
# TODO: Perhaps track SHA-1 in the header for protection? This would
39
# be redundant with it being stored in the inventory, but perhaps
40
# usefully so?
41
42
# TODO: Track version names as well as indexes.
43
44
# TODO: Probably do transitive expansion when specifying parents?
45
46
# TODO: Separate out some code to read and write weaves.
47
34
48
# TODO: End marker for each version so we can stop reading?
35
49
36
50
# TODO: Check that no insertion occurs inside a deletion that was
37
51
# active in the version of the insertion.
38
52
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
53
# TODO: Perhaps a special slower check() method that verifies more
54
# nesting constraints and the MD5 of each version?
55
56
57
58
try:
59
set
60
frozenset
61
except NameError:
62
from sets import Set, ImmutableSet
63
set = Set
64
frozenset = ImmutableSet
65
del Set, ImmutableSet
74
66
75
67
76
68
class WeaveError(Exception):
79
71
80
72
class WeaveFormatError(WeaveError):
81
73
"""Weave invariant violated"""
82
83
84
class WeaveParentMismatch(WeaveError):
85
"""Parents are mismatched between two revisions."""
86
74
87
75
88
76
class Weave(object):
106
94
the version-id is used to reference it in the larger world.
107
95
108
96
The weave is represented as a list mixing edit instructions and
109
literal text. Each entry in _weave can be either a string (or
97
literal text. Each entry in _l can be either a string (or
110
98
unicode), or a tuple. If a string, it means that the given line
111
99
should be output in the currently active revisions.
112
100
117
105
The instruction can be '{' or '}' for an insertion block, and '['
118
106
and ']' for a deletion block respectively. The version is the
119
107
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.
108
and inserts.
123
109
124
110
Constraints/notes:
125
111
152
138
should be no way to get an earlier version deleting a later
153
139
version.
154
140
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.
141
_l
142
Text of the weave.
143
144
_v
145
List of versions, indexed by index number.
146
147
For each version we store the set (included_versions), which
148
lists the previous versions also considered active; the
149
versions included in those versions are included transitively.
150
So new versions created from nothing list []; most versions
151
have a single entry; some have more.
175
152
"""
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
153
def __init__(self):
154
self._l = []
155
self._v = []
156
157
201
158
202
159
def __eq__(self, other):
203
160
if not isinstance(other, Weave):
204
161
return False
205
return self._parents == other._parents \
206
and self._weave == other._weave \
207
and self._sha1s == other._sha1s
162
return self._v == other._v \
163
and self._l == other._l
164
208
165
209
210
166
def __ne__(self, other):
211
167
return not self.__eq__(other)
212
168
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):
169
170
def add(self, parents, text):
256
171
"""Add a single text on top of the weave.
257
172
258
173
Returns the index number of the newly added version.
259
174
260
name
261
Symbolic name for this version.
262
(Typically the revision-id of the revision that added it.)
263
264
175
parents
265
List or set of direct parent version numbers.
266
176
List or set of parent version numbers. This must normally include
177
the parents and the parent's parents, or wierd things might happen.
178
267
179
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)
282
self._check_versions(parents)
180
Sequence of lines to be added in the new version."""
181
## self._check_versions(parents)
283
182
## 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)
183
184
idx = len(self._v)
185
186
if parents:
187
delta = self._delta(self.inclusions(parents), text)
188
189
# offset gives the number of lines that have been inserted
190
# into the weave up to the current point; if the original edit instruction
191
# says to change line A then we actually change (A+offset)
192
offset = 0
193
194
for i1, i2, newlines in delta:
195
assert 0 <= i1
196
assert i1 <= i2
197
assert i2 <= len(self._l)
198
199
# the deletion and insertion are handled separately.
200
# first delete the region.
201
if i1 != i2:
202
self._l.insert(i1+offset, ('[', idx))
203
self._l.insert(i2+offset+1, (']', idx))
204
offset += 2
205
# is this OK???
206
207
if newlines:
208
# there may have been a deletion spanning up to
209
# i2; we want to insert after this region to make sure
210
# we don't destroy ourselves
211
i = i2 + offset
212
self._l[i:i] = [('{', idx)] \
213
+ newlines \
214
+ [('}', idx)]
215
offset += 2 + len(newlines)
216
217
self._addversion(parents)
218
else:
219
# special case; adding with no parents revision; can do this
220
# more quickly by just appending unconditionally
221
self._l.append(('{', idx))
222
self._l += text
223
self._l.append(('}', idx))
224
225
self._addversion(None)
226
227
return idx
228
384
229
385
230
def inclusions(self, versions):
386
"""Return set of all ancestors of given version(s)."""
231
"""Expand out everything included by versions."""
387
232
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])
233
for v in versions:
234
i.update(self._v[v])
392
235
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
236
237
238
def _addversion(self, parents):
239
if parents:
240
self._v.append(frozenset(parents))
241
else:
242
self._v.append(frozenset())
427
243
428
244
429
245
def _check_lines(self, text):
432
248
433
249
for l in text:
434
250
if not isinstance(l, basestring):
435
raise ValueError("text line should be a string or unicode, not %s"
436
% type(l))
251
raise ValueError("text line should be a string or unicode, not %s" % type(l))
437
252
438
253
439
254
441
256
"""Check everything in the sequence of indexes is valid"""
442
257
for i in indexes:
443
258
try:
444
self._parents[i]
259
self._v[i]
445
260
except IndexError:
446
261
raise IndexError("invalid version number %r" % i)
447
262
448
263
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):
264
def annotate(self, index):
265
return list(self.annotate_iter(index))
266
267
268
def annotate_iter(self, version):
454
269
"""Yield list of (index-id, line) pairs for the specified version.
455
270
456
271
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):
272
included = self.inclusions([version])
273
for origin, lineno, text in self._extract(included):
459
274
yield origin, text
460
275
461
276
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):
277
def _extract(self, included):
500
278
"""Yield annotation of lines in included set.
501
279
502
280
Yields a sequence of tuples (origin, lineno, text), where
505
283
506
284
The set typically but not necessarily corresponds to a version.
507
285
"""
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()
516
517
lineno = 0 # line of weave, 0-based
286
istack = [] # versions for which an insertion block is current
287
288
dset = set() # versions for which a deletion block is current
518
289
519
290
isactive = None
520
291
521
result = []
292
lineno = 0 # line of weave, 0-based
293
294
# TODO: Probably only need to put included revisions in the istack
295
296
# TODO: Could split this into two functions, one that updates
297
# the stack and the other that processes the results -- but
298
# I'm not sure it's really needed.
299
300
# TODO: In fact, I think we only need to store the *count* of
301
# active insertions and deletions, and we can maintain that by
302
# just by just counting as we go along.
522
303
523
304
WFE = WeaveFormatError
524
525
for l in self._weave:
305
306
for l in self._l:
526
307
if isinstance(l, tuple):
308
isactive = None # recalculate
527
309
c, v = l
528
isactive = None
529
310
if c == '{':
530
assert v not in istack
311
if istack and (istack[-1] >= v):
312
raise WFE("improperly nested insertions %d>=%d on line %d"
313
% (istack[-1], v, lineno))
531
314
istack.append(v)
532
315
elif c == '}':
533
istack.pop()
316
try:
317
oldv = istack.pop()
318
except IndexError:
319
raise WFE("unmatched close of insertion %d on line %d"
320
% (v, lineno))
321
if oldv != v:
322
raise WFE("mismatched close of insertion %d!=%d on line %d"
323
% (oldv, v, lineno))
534
324
elif c == '[':
535
if v in included:
536
assert v not in dset
325
# block deleted in v
326
if v in dset:
327
raise WFE("repeated deletion marker for version %d on line %d"
328
% (v, lineno))
329
if istack:
330
if istack[-1] == v:
331
raise WFE("version %d deletes own text on line %d"
332
% (v, lineno))
537
333
dset.add(v)
538
else:
539
assert c == ']'
540
if v in included:
541
assert v in dset
334
elif c == ']':
335
if v in dset:
542
336
dset.remove(v)
337
else:
338
raise WFE("unmatched close of deletion %d on line %d"
339
% (v, lineno))
340
else:
341
raise WFE("invalid processing instruction %r on line %d"
342
% (l, lineno))
543
343
else:
544
344
assert isinstance(l, basestring)
545
if isactive is None:
546
isactive = (not dset) and istack and (istack[-1] in included)
345
if not istack:
346
raise WFE("literal at top level on line %d"
347
% lineno)
348
if isactive == None:
349
isactive = (istack[-1] in included) \
350
and not included.intersection(dset)
547
351
if isactive:
548
result.append((istack[-1], lineno, l))
352
origin = istack[-1]
353
yield origin, lineno, l
549
354
lineno += 1
550
355
551
356
if istack:
555
360
raise WFE("unclosed deletion blocks at end of weave",
556
361
dset)
557
362
558
return result
559
560
561
562
def get_iter(self, name_or_index):
363
364
def get_iter(self, version):
563
365
"""Yield lines for the specified version."""
564
incls = [self.maybe_lookup(name_or_index)]
565
for origin, lineno, line in self._extract(incls):
366
for origin, lineno, line in self._extract(self.inclusions([version])):
566
367
yield line
567
368
568
369
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):
370
def get(self, index):
371
return list(self.get_iter(index))
372
373
374
def merge_iter(self, included):
582
375
"""Return composed version of multiple included versions."""
583
included = map(self.maybe_lookup, included)
376
included = frozenset(included)
584
377
for origin, lineno, text in self._extract(included):
585
378
yield text
586
379
587
380
588
381
def dump(self, to_file):
589
382
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:
383
print >>to_file, "Weave._l = ",
384
pprint(self._l, to_file)
385
print >>to_file, "Weave._v = ",
386
pprint(self._v, to_file)
387
388
389
def check(self):
390
for vers_info in self._v:
391
included = set()
392
for vi in vers_info[0]:
393
if vi < 0 or vi >= index:
614
394
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()
395
% (vi, index))
396
if vi in included:
397
raise WeaveFormatError("repeated included version %d for index %d"
398
% (vi, index))
399
included.add(vi)
652
400
653
401
654
402
671
419
If line1=line2, this is a pure insert; if newlines=[] this is a
672
420
pure delete. (Similar to difflib.)
673
421
"""
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
422
423
## self._check_versions(included)
424
425
##from pprint import pprint
426
427
# first get basis for comparison
428
# basis holds (lineno, origin, line)
429
basis = []
430
431
##print 'my lines:'
432
##pprint(self._l)
433
434
# basis a list of (origin, lineno, line)
435
basis_lineno = []
436
basis_lines = []
437
for origin, lineno, line in self._extract(included):
438
basis_lineno.append(lineno)
439
basis_lines.append(line)
440
441
# add a sentinal, because we can also match against the final line
442
basis_lineno.append(len(self._l))
443
444
# XXX: which line of the weave should we really consider
445
# matches the end of the file? the current code says it's the
446
# last line of the weave?
447
448
from difflib import SequenceMatcher
449
s = SequenceMatcher(None, basis_lines, lines)
450
451
# TODO: Perhaps return line numbers from composed weave as well?
452
453
for tag, i1, i2, j1, j2 in s.get_opcodes():
454
##print tag, i1, i2, j1, j2
455
456
if tag == 'equal':
457
continue
458
459
# i1,i2 are given in offsets within basis_lines; we need to map them
460
# back to offsets within the entire weave
461
real_i1 = basis_lineno[i1]
462
real_i2 = basis_lineno[i2]
463
464
assert 0 <= j1
465
assert j1 <= j2
466
assert j2 <= len(lines)
467
468
yield real_i1, real_i2, lines[j1:j2]
469
470
1022
471
1023
472
1024
473
def main(argv):
1025
474
import sys
1026
475
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
476
from weavefile import write_weave_v1, read_weave_v1
1046
477
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()
478
if cmd == 'add':
479
w = read_weave_v1(file(argv[2], 'rb'))
1055
480
# at the moment, based on everything in the file
1056
name = argv[3]
1057
parents = map(int, argv[4:])
481
parents = set(range(len(w._v)))
1058
482
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)
483
ver = w.add(parents, lines)
484
write_weave_v1(w, file(argv[2], 'wb'))
485
print 'added %d' % ver
1062
486
elif cmd == 'init':
1063
487
fn = argv[2]
1064
488
if os.path.exists(fn):
1065
489
raise IOError("file exists")
1066
490
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
491
write_weave_v1(w, file(fn, 'wb'))
492
elif cmd == 'get':
493
w = read_weave_v1(file(argv[2], 'rb'))
494
sys.stdout.writelines(w.getiter(int(argv[3])))
1088
495
elif cmd == 'annotate':
1089
w = readit()
496
w = read_weave_v1(file(argv[2], 'rb'))
1090
497
# newline is added to all lines regardless; too hard to get
1091
498
# reasonable formatting otherwise
1092
499
lasto = None
1097
504
else:
1098
505
print '%5d | %s' % (origin, text)
1099
506
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
507
else:
1154
508
raise ValueError('unknown command %r' % cmd)
1155
509
1156
510
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
511
if __name__ == '__main__':
1179
512
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))
1186
513
sys.exit(main(sys.argv))
Loggerhead is a web-based interface for Breezy
Version: 2.0.1