« back to all changes in this revision
Viewing changes to bzrlib/weave.py
- browse files at revision 149
- compare with another revision
- download diff
- download tarball
- view history from revision 149
- Committer: mbp at sourcefrog
- Date: 2005-03-30 22:27:17 UTC
- Revision ID: mbp@sourcefrog.net-20050330222717-027b5837127b938d
experiment with new nested inventory file format
not used by default yet
not used by default yet
- files added:
- bzrlib/tests.py
- files removed:
- .rsyncexclude
- bzrlib/plugins
- bzrlib/selftest
- bzrlib/store
- bzrlib/transport
- bzrlib/util
- bzrlib/util/effbot
- bzrlib/util/effbot/org
- bzrlib/util/urlgrabber
- contrib
- contrib/bash
- contrib/emacs
- contrib/zsh
- patches
- tools
- files renamed:
- contrib/newinventory.py => bzrlib/newinventory.py
- bzrlib/store/__init__.py => bzrlib/store.py
- bzrlib/util/elementtree/ => elementtree/
- files modified:
- .bzrignore
added
removed
bzrlib/weave.py
1
#! /usr/bin/python
2
3
# Copyright (C) 2005 Canonical Ltd
4
5
# This program is free software; you can redistribute it and/or modify
6
# it under the terms of the GNU General Public License as published by
7
# the Free Software Foundation; either version 2 of the License, or
8
# (at your option) any later version.
9
10
# This program is distributed in the hope that it will be useful,
11
# but WITHOUT ANY WARRANTY; without even the implied warranty of
12
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13
# GNU General Public License for more details.
14
15
# You should have received a copy of the GNU General Public License
16
# along with this program; if not, write to the Free Software
17
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18
19
# Author: Martin Pool <mbp@canonical.com>
20
21
22
"""Weave - storage of related text file versions"""
23
24
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: Perhaps 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: Have a way to go back and insert a revision V1 that is a parent
61
# of an already-stored revision V2. This means some lines previously
62
# counted as new in V2 will be discovered to have actually come from V1.
63
# It is probably necessary to insert V1, then compute a whole new diff
64
# from the mashed ancestors to V2. This must be repeated for every
65
# direct child of V1. The deltas from V2 to its descendents won't change,
66
# although their location within the weave may change. It may be possible
67
# to just adjust the location of those instructions rather than
68
# re-weaving the whole thing. This is expected to be a fairly rare
69
# operation, only used when inserting data that was previously a ghost.
70
71
72
73
74
import sha
75
from difflib import SequenceMatcher
76
77
from bzrlib.trace import mutter
78
79
80
class WeaveError(Exception):
81
"""Exception in processing weave"""
82
83
84
class WeaveFormatError(WeaveError):
85
"""Weave invariant violated"""
86
87
88
class Weave(object):
89
"""weave - versioned text file storage.
90
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.
98
99
Texts can be identified in either of two ways:
100
101
* a nonnegative index number.
102
103
* a version-id string.
104
105
Typically the index number will be valid only inside this weave and
106
the version-id is used to reference it in the larger world.
107
108
The weave is represented as a list mixing edit instructions and
109
literal text. Each entry in _weave can be either a string (or
110
unicode), or a tuple. If a string, it means that the given line
111
should be output in the currently active revisions.
112
113
If a tuple, it gives a processing instruction saying in which
114
revisions the enclosed lines are active. The tuple has the form
115
(instruction, version).
116
117
The instruction can be '{' or '}' for an insertion block, and '['
118
and ']' for a deletion block respectively. The version is the
119
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.
123
124
Constraints/notes:
125
126
* A later version can delete lines that were introduced by any
127
number of ancestor versions; this implies that deletion
128
instructions can span insertion blocks without regard to the
129
insertion block's nesting.
130
131
* Similarly, deletions need not be properly nested with regard to
132
each other, because they might have been generated by
133
independent revisions.
134
135
* Insertions are always made by inserting a new bracketed block
136
into a single point in the previous weave. This implies they
137
can nest but not overlap, and the nesting must always have later
138
insertions on the inside.
139
140
* It doesn't seem very useful to have an active insertion
141
inside an inactive insertion, but it might happen.
142
143
* Therefore, all instructions are always"considered"; that
144
is passed onto and off the stack. An outer inactive block
145
doesn't disable an inner block.
146
147
* Lines are enabled if the most recent enclosing insertion is
148
active and none of the enclosing deletions are active.
149
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.
175
"""
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):
256
"""Add a single text on top of the weave.
257
258
Returns the index number of the newly added version.
259
260
name
261
Symbolic name for this version.
262
(Typically the revision-id of the revision that added it.)
263
264
parents
265
List or set of direct parent version numbers.
266
267
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)
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
427
428
429
def _check_lines(self, text):
430
if not isinstance(text, list):
431
raise ValueError("text should be a list, not %s" % type(text))
432
433
for l in text:
434
if not isinstance(l, basestring):
435
raise ValueError("text line should be a string or unicode, not %s"
436
% type(l))
437
438
439
440
def _check_versions(self, indexes):
441
"""Check everything in the sequence of indexes is valid"""
442
for i in indexes:
443
try:
444
self._parents[i]
445
except IndexError:
446
raise IndexError("invalid version number %r" % i)
447
448
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):
454
"""Yield list of (index-id, line) pairs for the specified version.
455
456
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):
459
yield origin, text
460
461
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):
500
"""Yield annotation of lines in included set.
501
502
Yields a sequence of tuples (origin, lineno, text), where
503
origin is the origin version, lineno the index in the weave,
504
and text the text of the line.
505
506
The set typically but not necessarily corresponds to a version.
507
"""
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
518
519
isactive = None
520
521
result = []
522
523
WFE = WeaveFormatError
524
525
for l in self._weave:
526
if isinstance(l, tuple):
527
c, v = l
528
isactive = None
529
if c == '{':
530
assert v not in istack
531
istack.append(v)
532
elif c == '}':
533
istack.pop()
534
elif c == '[':
535
if v in included:
536
assert v not in dset
537
dset.add(v)
538
else:
539
assert c == ']'
540
if v in included:
541
assert v in dset
542
dset.remove(v)
543
else:
544
assert isinstance(l, basestring)
545
if isactive is None:
546
isactive = (not dset) and istack and (istack[-1] in included)
547
if isactive:
548
result.append((istack[-1], lineno, l))
549
lineno += 1
550
551
if istack:
552
raise WFE("unclosed insertion blocks at end of weave",
553
istack)
554
if dset:
555
raise WFE("unclosed deletion blocks at end of weave",
556
dset)
557
558
return result
559
560
561
562
def get_iter(self, name_or_index):
563
"""Yield lines for the specified version."""
564
incls = [self.maybe_lookup(name_or_index)]
565
for origin, lineno, line in self._extract(incls):
566
yield line
567
568
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
586
587
588
def dump(self, to_file):
589
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:
614
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()
652
653
654
655
def _delta(self, included, lines):
656
"""Return changes from basis to new revision.
657
658
The old text for comparison is the union of included revisions.
659
660
This is used in inserting a new text.
661
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
666
replaced by the sequence of lines in newlines. Note that
667
these line numbers are positions in the total weave and don't
668
correspond to the lines in any extracted version, or even the
669
extracted union of included versions.
670
671
If line1=line2, this is a pure insert; if newlines=[] this is a
672
pure delete. (Similar to difflib.)
673
"""
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
# work through in index order to make sure we get all dependencies
787
for other_idx, name in enumerate(other._names):
788
# TODO: If all the parents of the other version are already
789
# present then we can avoid some work by just taking the delta
790
# and adjusting the offsets.
791
if self._check_version_consistent(other, other_idx, name):
792
continue
793
new_parents = self._imported_parents(other, other_idx)
794
lines = other.get_lines(other_idx)
795
sha1 = other._sha1s[other_idx]
796
self.add(name, new_parents, lines, sha1)
797
798
799
def _imported_parents(self, other, other_idx):
800
"""Return list of parents in self corresponding to indexes in other."""
801
new_parents = []
802
for parent_idx in other._parents[other_idx]:
803
parent_name = other._names[parent_idx]
804
if parent_name not in self._names:
805
# should not be possible
806
raise WeaveError("missing parent {%s} of {%s} in %r"
807
% (parent_name, other._name_map[other_idx], self))
808
new_parents.append(self._name_map[parent_name])
809
return new_parents
810
811
def _check_version_consistent(self, other, other_idx, name):
812
"""Check if a version in consistent in this and other.
813
814
To be consistent it must have:
815
816
* the same text
817
* the same direct parents (by name, not index, and disregarding
818
order)
819
820
If present & correct return True;
821
if not present in self return False;
822
if inconsistent raise error."""
823
this_idx = self._name_map.get(name, -1)
824
if this_idx != -1:
825
if self._sha1s[this_idx] != other._sha1s[other_idx]:
826
raise WeaveError("inconsistent texts for version {%s} "
827
"when joining weaves"
828
% (name))
829
self_parents = self._parents[this_idx]
830
other_parents = other._parents[other_idx]
831
n1 = [self._names[i] for i in self_parents]
832
n2 = [other._names[i] for i in other_parents]
833
n1.sort()
834
n2.sort()
835
if n1 != n2:
836
# XXX: Perhaps return a specific exception for this so
837
# we can retry through reweave().
838
raise WeaveError("inconsistent parents for version {%s}: "
839
"%s vs %s"
840
% (name, n1, n2))
841
else:
842
return True # ok!
843
else:
844
return False
845
846
847
def reweave(wa, wb):
848
"""Combine two weaves and return the result.
849
850
This works even if a revision R has different parents in
851
wa and wb. In the resulting weave all the parents are given.
852
853
This is done by just building up a new weave, maintaining ordering
854
of the versions in the two inputs. More efficient approaches
855
might be possible but it should only be necessary to do
856
this operation rarely, when a new previously ghost version is
857
inserted.
858
"""
859
wr = Weave()
860
ia = ib = 0
861
queue_a = range(wa.numversions())
862
queue_b = range(wb.numversions())
863
# first determine combined parents of all versions
864
# map from version name -> all parent names
865
combined_parents = _reweave_parent_graphs(wa, wb)
866
mutter("combined parents: %r", combined_parents)
867
order = _make_reweave_order(wa._names, wb._names, combined_parents)
868
mutter("order to reweave: %r", order)
869
for name in order:
870
if name in wa._name_map:
871
lines = wa.get_lines(name)
872
if name in wb._name_map:
873
assert lines == wb.get_lines(name)
874
else:
875
lines = wb.get_lines(name)
876
wr.add(name, combined_parents[name], lines)
877
return wr
878
879
880
def _reweave_parent_graphs(wa, wb):
881
"""Return combined parent ancestry for two weaves.
882
883
Returned as a list of (version_name, set(parent_names))"""
884
combined = {}
885
for weave in [wa, wb]:
886
for idx, name in enumerate(weave._names):
887
p = combined.setdefault(name, set())
888
p.update(map(weave.idx_to_name, weave._parents[idx]))
889
return combined
890
891
892
def _make_reweave_order(wa_order, wb_order, combined_parents):
893
"""Return an order to reweave versions respecting parents."""
894
done = set()
895
result = []
896
ia = ib = 0
897
next_a = next_b = None
898
len_a = len(wa_order)
899
len_b = len(wb_order)
900
while ia < len(wa_order) or ib < len(wb_order):
901
if ia < len_a:
902
next_a = wa_order[ia]
903
if next_a in done:
904
ia += 1
905
continue
906
if combined_parents[next_a].issubset(done):
907
ia += 1
908
result.append(next_a)
909
done.add(next_a)
910
continue
911
if ib < len_b:
912
next_b = wb_order[ib]
913
if next_b in done:
914
ib += 1
915
continue
916
elif combined_parents[next_b].issubset(done):
917
ib += 1
918
result.append(next_b)
919
done.add(next_b)
920
continue
921
raise WeaveError("don't know how to reweave at {%s} and {%s}"
922
% (next_a, next_b))
923
return result
924
925
926
def weave_toc(w):
927
"""Show the weave's table-of-contents"""
928
print '%6s %50s %10s %10s' % ('ver', 'name', 'sha1', 'parents')
929
for i in (6, 50, 10, 10):
930
print '-' * i,
931
print
932
for i in range(w.numversions()):
933
sha1 = w._sha1s[i]
934
name = w._names[i]
935
parent_str = ' '.join(map(str, w._parents[i]))
936
print '%6d %-50.50s %10.10s %s' % (i, name, sha1, parent_str)
937
938
939
940
def weave_stats(weave_file, pb):
941
from bzrlib.weavefile import read_weave
942
943
wf = file(weave_file, 'rb')
944
w = read_weave(wf)
945
# FIXME: doesn't work on pipes
946
weave_size = wf.tell()
947
948
total = 0
949
vers = len(w)
950
for i in range(vers):
951
pb.update('checking sizes', i, vers)
952
for origin, lineno, line in w._extract([i]):
953
total += len(line)
954
955
pb.clear()
956
957
print 'versions %9d' % vers
958
print 'weave file %9d bytes' % weave_size
959
print 'total contents %9d bytes' % total
960
print 'compression ratio %9.2fx' % (float(total) / float(weave_size))
961
if vers:
962
avg = total/vers
963
print 'average size %9d bytes' % avg
964
print 'relative size %9.2fx' % (float(weave_size) / float(avg))
965
966
967
def usage():
968
print """bzr weave tool
969
970
Experimental tool for weave algorithm.
971
972
usage:
973
weave init WEAVEFILE
974
Create an empty weave file
975
weave get WEAVEFILE VERSION
976
Write out specified version.
977
weave check WEAVEFILE
978
Check consistency of all versions.
979
weave toc WEAVEFILE
980
Display table of contents.
981
weave add WEAVEFILE NAME [BASE...] < NEWTEXT
982
Add NEWTEXT, with specified parent versions.
983
weave annotate WEAVEFILE VERSION
984
Display origin of each line.
985
weave mash WEAVEFILE VERSION...
986
Display composite of all selected versions.
987
weave merge WEAVEFILE VERSION1 VERSION2 > OUT
988
Auto-merge two versions and display conflicts.
989
weave diff WEAVEFILE VERSION1 VERSION2
990
Show differences between two versions.
991
992
example:
993
994
% weave init foo.weave
995
% vi foo.txt
996
% weave add foo.weave ver0 < foo.txt
997
added version 0
998
999
(create updated version)
1000
% vi foo.txt
1001
% weave get foo.weave 0 | diff -u - foo.txt
1002
% weave add foo.weave ver1 0 < foo.txt
1003
added version 1
1004
1005
% weave get foo.weave 0 > foo.txt (create forked version)
1006
% vi foo.txt
1007
% weave add foo.weave ver2 0 < foo.txt
1008
added version 2
1009
1010
% weave merge foo.weave 1 2 > foo.txt (merge them)
1011
% vi foo.txt (resolve conflicts)
1012
% weave add foo.weave merged 1 2 < foo.txt (commit merged version)
1013
1014
"""
1015
1016
1017
1018
def main(argv):
1019
import sys
1020
import os
1021
try:
1022
import bzrlib
1023
except ImportError:
1024
# in case we're run directly from the subdirectory
1025
sys.path.append('..')
1026
import bzrlib
1027
from bzrlib.weavefile import write_weave, read_weave
1028
from bzrlib.progress import ProgressBar
1029
1030
try:
1031
import psyco
1032
psyco.full()
1033
except ImportError:
1034
pass
1035
1036
if len(argv) < 2:
1037
usage()
1038
return 0
1039
1040
cmd = argv[1]
1041
1042
def readit():
1043
return read_weave(file(argv[2], 'rb'))
1044
1045
if cmd == 'help':
1046
usage()
1047
elif cmd == 'add':
1048
w = readit()
1049
# at the moment, based on everything in the file
1050
name = argv[3]
1051
parents = map(int, argv[4:])
1052
lines = sys.stdin.readlines()
1053
ver = w.add(name, parents, lines)
1054
write_weave(w, file(argv[2], 'wb'))
1055
print 'added version %r %d' % (name, ver)
1056
elif cmd == 'init':
1057
fn = argv[2]
1058
if os.path.exists(fn):
1059
raise IOError("file exists")
1060
w = Weave()
1061
write_weave(w, file(fn, 'wb'))
1062
elif cmd == 'get': # get one version
1063
w = readit()
1064
sys.stdout.writelines(w.get_iter(int(argv[3])))
1065
1066
elif cmd == 'mash': # get composite
1067
w = readit()
1068
sys.stdout.writelines(w.mash_iter(map(int, argv[3:])))
1069
1070
elif cmd == 'diff':
1071
from difflib import unified_diff
1072
w = readit()
1073
fn = argv[2]
1074
v1, v2 = map(int, argv[3:5])
1075
lines1 = w.get(v1)
1076
lines2 = w.get(v2)
1077
diff_gen = unified_diff(lines1, lines2,
1078
'%s version %d' % (fn, v1),
1079
'%s version %d' % (fn, v2))
1080
sys.stdout.writelines(diff_gen)
1081
1082
elif cmd == 'annotate':
1083
w = readit()
1084
# newline is added to all lines regardless; too hard to get
1085
# reasonable formatting otherwise
1086
lasto = None
1087
for origin, text in w.annotate(int(argv[3])):
1088
text = text.rstrip('\r\n')
1089
if origin == lasto:
1090
print ' | %s' % (text)
1091
else:
1092
print '%5d | %s' % (origin, text)
1093
lasto = origin
1094
1095
elif cmd == 'toc':
1096
weave_toc(readit())
1097
1098
elif cmd == 'stats':
1099
weave_stats(argv[2], ProgressBar())
1100
1101
elif cmd == 'check':
1102
w = readit()
1103
pb = ProgressBar()
1104
w.check(pb)
1105
pb.clear()
1106
print '%d versions ok' % w.numversions()
1107
1108
elif cmd == 'inclusions':
1109
w = readit()
1110
print ' '.join(map(str, w.inclusions([int(argv[3])])))
1111
1112
elif cmd == 'parents':
1113
w = readit()
1114
print ' '.join(map(str, w._parents[int(argv[3])]))
1115
1116
elif cmd == 'plan-merge':
1117
w = readit()
1118
for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
1119
if line:
1120
print '%14s | %s' % (state, line),
1121
1122
elif cmd == 'merge':
1123
w = readit()
1124
p = w.plan_merge(int(argv[3]), int(argv[4]))
1125
sys.stdout.writelines(w.weave_merge(p))
1126
1127
elif cmd == 'mash-merge':
1128
if len(argv) != 5:
1129
usage()
1130
return 1
1131
1132
w = readit()
1133
v1, v2 = map(int, argv[3:5])
1134
1135
basis = w.inclusions([v1]).intersection(w.inclusions([v2]))
1136
1137
base_lines = list(w.mash_iter(basis))
1138
a_lines = list(w.get(v1))
1139
b_lines = list(w.get(v2))
1140
1141
from bzrlib.merge3 import Merge3
1142
m3 = Merge3(base_lines, a_lines, b_lines)
1143
1144
name_a = 'version %d' % v1
1145
name_b = 'version %d' % v2
1146
sys.stdout.writelines(m3.merge_lines(name_a=name_a, name_b=name_b))
1147
else:
1148
raise ValueError('unknown command %r' % cmd)
1149
1150
1151
1152
def profile_main(argv):
1153
import tempfile, hotshot, hotshot.stats
1154
1155
prof_f = tempfile.NamedTemporaryFile()
1156
1157
prof = hotshot.Profile(prof_f.name)
1158
1159
ret = prof.runcall(main, argv)
1160
prof.close()
1161
1162
stats = hotshot.stats.load(prof_f.name)
1163
#stats.strip_dirs()
1164
stats.sort_stats('cumulative')
1165
## XXX: Might like to write to stderr or the trace file instead but
1166
## print_stats seems hardcoded to stdout
1167
stats.print_stats(20)
1168
1169
return ret
1170
1171
1172
if __name__ == '__main__':
1173
import sys
1174
if '--profile' in sys.argv:
1175
args = sys.argv[:]
1176
args.remove('--profile')
1177
sys.exit(profile_main(args))
1178
else:
1179
sys.exit(main(sys.argv))
1180
Loggerhead is a web-based interface for Breezy
Version: 2.0.1