~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

  • Committer: Martin Pool
  • Date: 2005-07-16 00:07:40 UTC
  • mfrom: (909.1.5)
  • Revision ID: mbp@sourcefrog.net-20050716000740-f2dcb8894a23fd2d
- merge aaron's bugfix branch
  up to abentley@panoramicfeedback.com-20050715134354-78f2bca607acb415

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
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
# TODO: Perhaps have copy method for Weave instances?
 
25
 
 
26
# XXX: If we do weaves this way, will a merge still behave the same
 
27
# way if it's done in a different order?  That's a pretty desirable
 
28
# property.
 
29
 
 
30
# TODO: Nothing here so far assumes the lines are really \n newlines,
 
31
# rather than being split up in some other way.  We could accomodate
 
32
# binaries, perhaps by naively splitting on \n or perhaps using
 
33
# something like a rolling checksum.
 
34
 
 
35
# TODO: Track version names as well as indexes. 
 
36
 
 
37
# TODO: End marker for each version so we can stop reading?
 
38
 
 
39
# TODO: Check that no insertion occurs inside a deletion that was
 
40
# active in the version of the insertion.
 
41
 
 
42
# TODO: In addition to the SHA-1 check, perhaps have some code that
 
43
# checks structural constraints of the weave: ie that insertions are
 
44
# properly nested, that there is no text outside of an insertion, that
 
45
# insertions or deletions are not repeated, etc.
 
46
 
 
47
# TODO: Make the info command just show info, not extract everything:
 
48
# it can be much faster.
 
49
 
 
50
# TODO: Perhaps use long integers as sets instead of set objects; may
 
51
# be faster.
 
52
 
 
53
# TODO: Parallel-extract that passes back each line along with a
 
54
# description of which revisions include it.  Nice for checking all
 
55
# shas in parallel.
 
56
 
 
57
 
 
58
 
 
59
 
 
60
try:
 
61
    set
 
62
    frozenset
 
63
except NameError:
 
64
    from sets import Set, ImmutableSet
 
65
    set = Set
 
66
    frozenset = ImmutableSet
 
67
    del Set, ImmutableSet
 
68
 
 
69
 
 
70
class WeaveError(Exception):
 
71
    """Exception in processing weave"""
 
72
 
 
73
 
 
74
class WeaveFormatError(WeaveError):
 
75
    """Weave invariant violated"""
 
76
    
 
77
 
 
78
class Weave(object):
 
79
    """weave - versioned text file storage.
 
80
    
 
81
    A Weave manages versions of line-based text files, keeping track
 
82
    of the originating version for each line.
 
83
 
 
84
    To clients the "lines" of the file are represented as a list of strings.
 
85
    These strings  will typically have terminal newline characters, but
 
86
    this is not required.  In particular files commonly do not have a newline
 
87
    at the end of the file.
 
88
 
 
89
    Texts can be identified in either of two ways:
 
90
 
 
91
    * a nonnegative index number.
 
92
 
 
93
    * a version-id string.
 
94
 
 
95
    Typically the index number will be valid only inside this weave and
 
96
    the version-id is used to reference it in the larger world.
 
97
 
 
98
    The weave is represented as a list mixing edit instructions and
 
99
    literal text.  Each entry in _l can be either a string (or
 
100
    unicode), or a tuple.  If a string, it means that the given line
 
101
    should be output in the currently active revisions.
 
102
 
 
103
    If a tuple, it gives a processing instruction saying in which
 
104
    revisions the enclosed lines are active.  The tuple has the form
 
105
    (instruction, version).
 
106
 
 
107
    The instruction can be '{' or '}' for an insertion block, and '['
 
108
    and ']' for a deletion block respectively.  The version is the
 
109
    integer version index.  There is no replace operator, only deletes
 
110
    and inserts.
 
111
 
 
112
    Constraints/notes:
 
113
 
 
114
    * A later version can delete lines that were introduced by any
 
115
      number of ancestor versions; this implies that deletion
 
116
      instructions can span insertion blocks without regard to the
 
117
      insertion block's nesting.
 
118
 
 
119
    * Similarly, deletions need not be properly nested with regard to
 
120
      each other, because they might have been generated by
 
121
      independent revisions.
 
122
 
 
123
    * Insertions are always made by inserting a new bracketed block
 
124
      into a single point in the previous weave.  This implies they
 
125
      can nest but not overlap, and the nesting must always have later
 
126
      insertions on the inside.
 
127
 
 
128
    * It doesn't seem very useful to have an active insertion
 
129
      inside an inactive insertion, but it might happen.
 
130
      
 
131
    * Therefore, all instructions are always"considered"; that
 
132
      is passed onto and off the stack.  An outer inactive block
 
133
      doesn't disable an inner block.
 
134
 
 
135
    * Lines are enabled if the most recent enclosing insertion is
 
136
      active and none of the enclosing deletions are active.
 
137
 
 
138
    * There is no point having a deletion directly inside its own
 
139
      insertion; you might as well just not write it.  And there
 
140
      should be no way to get an earlier version deleting a later
 
141
      version.
 
142
 
 
143
    _l
 
144
        Text of the weave.
 
145
 
 
146
    _v
 
147
        List of parents, indexed by version number.
 
148
        It is only necessary to store the minimal set of parents for
 
149
        each version; the parent's parents are implied.
 
150
 
 
151
    _sha1s
 
152
        List of hex SHA-1 of each version, or None if not recorded.
 
153
    """
 
154
    def __init__(self):
 
155
        self._l = []
 
156
        self._v = []
 
157
        self._sha1s = []
 
158
 
 
159
 
 
160
    def __eq__(self, other):
 
161
        if not isinstance(other, Weave):
 
162
            return False
 
163
        return self._v == other._v \
 
164
               and self._l == other._l
 
165
    
 
166
 
 
167
    def __ne__(self, other):
 
168
        return not self.__eq__(other)
 
169
 
 
170
        
 
171
    def add(self, parents, text):
 
172
        """Add a single text on top of the weave.
 
173
  
 
174
        Returns the index number of the newly added version.
 
175
 
 
176
        parents
 
177
            List or set of direct parent version numbers.
 
178
            
 
179
        text
 
180
            Sequence of lines to be added in the new version."""
 
181
        ## self._check_versions(parents)
 
182
        ## self._check_lines(text)
 
183
        idx = len(self._v)
 
184
 
 
185
        import sha
 
186
        s = sha.new()
 
187
        for l in text:
 
188
            s.update(l)
 
189
        sha1 = s.hexdigest()
 
190
        del s
 
191
 
 
192
        # TODO: It'd probably be faster to append things on to a new
 
193
        # list rather than modifying the existing one, which is likely
 
194
        # to cause a lot of copying.
 
195
 
 
196
        if parents:
 
197
            ancestors = self.inclusions(parents)
 
198
            delta = self._delta(ancestors, text)
 
199
 
 
200
            # offset gives the number of lines that have been inserted
 
201
            # into the weave up to the current point; if the original edit instruction
 
202
            # says to change line A then we actually change (A+offset)
 
203
            offset = 0
 
204
 
 
205
            for i1, i2, newlines in delta:
 
206
                assert 0 <= i1
 
207
                assert i1 <= i2
 
208
                assert i2 <= len(self._l)
 
209
 
 
210
                # the deletion and insertion are handled separately.
 
211
                # first delete the region.
 
212
                if i1 != i2:
 
213
                    self._l.insert(i1+offset, ('[', idx))
 
214
                    self._l.insert(i2+offset+1, (']', idx))
 
215
                    offset += 2
 
216
                    # is this OK???
 
217
 
 
218
                if newlines:
 
219
                    # there may have been a deletion spanning up to
 
220
                    # i2; we want to insert after this region to make sure
 
221
                    # we don't destroy ourselves
 
222
                    i = i2 + offset
 
223
                    self._l[i:i] = [('{', idx)] \
 
224
                                   + newlines \
 
225
                                   + [('}', idx)]
 
226
                    offset += 2 + len(newlines)
 
227
 
 
228
            self._addversion(parents)
 
229
        else:
 
230
            # special case; adding with no parents revision; can do this
 
231
            # more quickly by just appending unconditionally
 
232
            self._l.append(('{', idx))
 
233
            self._l += text
 
234
            self._l.append(('}', idx))
 
235
 
 
236
            self._addversion(None)
 
237
 
 
238
        self._sha1s.append(sha1)
 
239
            
 
240
        return idx
 
241
 
 
242
 
 
243
    def inclusions_bitset(self, versions):
 
244
        i = 0
 
245
        for v in versions:
 
246
            i |= (1L << v)
 
247
        v = max(versions)
 
248
        while v >= 0:
 
249
            if i & (1L << v):
 
250
                # if v is included, include all its parents
 
251
                for pv in self._v[v]:
 
252
                    i |= (1L << pv)
 
253
            v -= 1
 
254
        return i
 
255
 
 
256
 
 
257
    def inclusions(self, versions):
 
258
        """Return set of all ancestors of given version(s)."""
 
259
        i = set(versions)
 
260
        v = max(versions)
 
261
        try:
 
262
            while v >= 0:
 
263
                if v in i:
 
264
                    # include all its parents
 
265
                    i.update(self._v[v])
 
266
                v -= 1
 
267
            return i
 
268
        except IndexError:
 
269
            raise ValueError("version %d not present in weave" % v)
 
270
 
 
271
 
 
272
    def minimal_parents(self, version):
 
273
        """Find the minimal set of parents for the version."""
 
274
        included = self._v[version]
 
275
        if not included:
 
276
            return []
 
277
        
 
278
        li = list(included)
 
279
        li.sort(reverse=True)
 
280
 
 
281
        mininc = []
 
282
        gotit = set()
 
283
 
 
284
        for pv in li:
 
285
            if pv not in gotit:
 
286
                mininc.append(pv)
 
287
                gotit.update(self.inclusions(pv))
 
288
 
 
289
        assert mininc[0] >= 0
 
290
        assert mininc[-1] < version
 
291
        return mininc
 
292
 
 
293
 
 
294
    def _addversion(self, parents):
 
295
        if parents:
 
296
            self._v.append(parents)
 
297
        else:
 
298
            self._v.append(frozenset())
 
299
 
 
300
 
 
301
    def _check_lines(self, text):
 
302
        if not isinstance(text, list):
 
303
            raise ValueError("text should be a list, not %s" % type(text))
 
304
 
 
305
        for l in text:
 
306
            if not isinstance(l, basestring):
 
307
                raise ValueError("text line should be a string or unicode, not %s"
 
308
                                 % type(l))
 
309
        
 
310
 
 
311
 
 
312
    def _check_versions(self, indexes):
 
313
        """Check everything in the sequence of indexes is valid"""
 
314
        for i in indexes:
 
315
            try:
 
316
                self._v[i]
 
317
            except IndexError:
 
318
                raise IndexError("invalid version number %r" % i)
 
319
 
 
320
    
 
321
    def annotate(self, index):
 
322
        return list(self.annotate_iter(index))
 
323
 
 
324
 
 
325
    def annotate_iter(self, version):
 
326
        """Yield list of (index-id, line) pairs for the specified version.
 
327
 
 
328
        The index indicates when the line originated in the weave."""
 
329
        for origin, lineno, text in self._extract([version]):
 
330
            yield origin, text
 
331
 
 
332
 
 
333
    def _walk(self):
 
334
        """Walk the weave.
 
335
 
 
336
        Yields sequence of
 
337
        (lineno, insert, deletes, text)
 
338
        for each literal line.
 
339
        """
 
340
        
 
341
        istack = []
 
342
        dset = 0L
 
343
 
 
344
        lineno = 0         # line of weave, 0-based
 
345
 
 
346
        for l in self._l:
 
347
            if isinstance(l, tuple):
 
348
                c, v = l
 
349
                isactive = None
 
350
                if c == '{':
 
351
                    istack.append(v)
 
352
                elif c == '}':
 
353
                    oldv = istack.pop()
 
354
                elif c == '[':
 
355
                    vs = (1L << v)
 
356
                    assert not (dset & vs)
 
357
                    dset |= vs
 
358
                elif c == ']':
 
359
                    vs = (1L << v)
 
360
                    assert dset & vs
 
361
                    dset ^= vs
 
362
                else:
 
363
                    raise WeaveFormatError('unexpected instruction %r'
 
364
                                           % v)
 
365
            else:
 
366
                assert isinstance(l, basestring)
 
367
                assert istack
 
368
                yield lineno, istack[-1], dset, l
 
369
            lineno += 1
 
370
 
 
371
 
 
372
 
 
373
    def _extract(self, versions):
 
374
        """Yield annotation of lines in included set.
 
375
 
 
376
        Yields a sequence of tuples (origin, lineno, text), where
 
377
        origin is the origin version, lineno the index in the weave,
 
378
        and text the text of the line.
 
379
 
 
380
        The set typically but not necessarily corresponds to a version.
 
381
        """
 
382
        included = self.inclusions(versions)
 
383
 
 
384
        istack = []
 
385
        dset = set()
 
386
 
 
387
        lineno = 0         # line of weave, 0-based
 
388
 
 
389
        isactive = None
 
390
 
 
391
        WFE = WeaveFormatError
 
392
 
 
393
        for l in self._l:
 
394
            if isinstance(l, tuple):
 
395
                c, v = l
 
396
                isactive = None
 
397
                if c == '{':
 
398
                    assert v not in istack
 
399
                    istack.append(v)
 
400
                elif c == '}':
 
401
                    oldv = istack.pop()
 
402
                    assert oldv == v
 
403
                elif c == '[':
 
404
                    if v in included:
 
405
                        assert v not in dset
 
406
                        dset.add(v)
 
407
                else:
 
408
                    assert c == ']'
 
409
                    if v in included:
 
410
                        assert v in dset
 
411
                        dset.remove(v)
 
412
            else:
 
413
                assert isinstance(l, basestring)
 
414
                if isactive is None:
 
415
                    isactive = (not dset) and istack and (istack[-1] in included)
 
416
                if isactive:
 
417
                    yield istack[-1], lineno, l
 
418
            lineno += 1
 
419
 
 
420
        if istack:
 
421
            raise WFE("unclosed insertion blocks at end of weave",
 
422
                                   istack)
 
423
        if dset:
 
424
            raise WFE("unclosed deletion blocks at end of weave",
 
425
                                   dset)
 
426
 
 
427
 
 
428
    def get_iter(self, version):
 
429
        """Yield lines for the specified version."""
 
430
        for origin, lineno, line in self._extract([version]):
 
431
            yield line
 
432
 
 
433
 
 
434
    def get(self, index):
 
435
        return list(self.get_iter(index))
 
436
 
 
437
 
 
438
    def mash_iter(self, included):
 
439
        """Return composed version of multiple included versions."""
 
440
        included = frozenset(included)
 
441
        for origin, lineno, text in self._extract(included):
 
442
            yield text
 
443
 
 
444
 
 
445
    def dump(self, to_file):
 
446
        from pprint import pprint
 
447
        print >>to_file, "Weave._l = ",
 
448
        pprint(self._l, to_file)
 
449
        print >>to_file, "Weave._v = ",
 
450
        pprint(self._v, to_file)
 
451
 
 
452
 
 
453
 
 
454
    def numversions(self):
 
455
        l = len(self._v)
 
456
        assert l == len(self._sha1s)
 
457
        return l
 
458
 
 
459
 
 
460
    def check(self, progress_bar=None):
 
461
        # check no circular inclusions
 
462
        for version in range(self.numversions()):
 
463
            inclusions = list(self._v[version])
 
464
            if inclusions:
 
465
                inclusions.sort()
 
466
                if inclusions[-1] >= version:
 
467
                    raise WeaveFormatError("invalid included version %d for index %d"
 
468
                                           % (inclusions[-1], version))
 
469
 
 
470
        # try extracting all versions; this is a bit slow and parallel
 
471
        # extraction could be used
 
472
        import sha
 
473
        nv = self.numversions()
 
474
        for version in range(nv):
 
475
            if progress_bar:
 
476
                progress_bar.update('checking text', version, nv)
 
477
            s = sha.new()
 
478
            for l in self.get_iter(version):
 
479
                s.update(l)
 
480
            hd = s.hexdigest()
 
481
            expected = self._sha1s[version]
 
482
            if hd != expected:
 
483
                raise WeaveError("mismatched sha1 for version %d; "
 
484
                                 "got %s, expected %s"
 
485
                                 % (version, hd, expected))
 
486
 
 
487
        # TODO: check insertions are properly nested, that there are
 
488
        # no lines outside of insertion blocks, that deletions are
 
489
        # properly paired, etc.
 
490
 
 
491
 
 
492
 
 
493
    def merge(self, merge_versions):
 
494
        """Automerge and mark conflicts between versions.
 
495
 
 
496
        This returns a sequence, each entry describing alternatives
 
497
        for a chunk of the file.  Each of the alternatives is given as
 
498
        a list of lines.
 
499
 
 
500
        If there is a chunk of the file where there's no diagreement,
 
501
        only one alternative is given.
 
502
        """
 
503
 
 
504
        # approach: find the included versions common to all the
 
505
        # merged versions
 
506
        raise NotImplementedError()
 
507
 
 
508
 
 
509
 
 
510
    def _delta(self, included, lines):
 
511
        """Return changes from basis to new revision.
 
512
 
 
513
        The old text for comparison is the union of included revisions.
 
514
 
 
515
        This is used in inserting a new text.
 
516
 
 
517
        Delta is returned as a sequence of
 
518
        (weave1, weave2, newlines).
 
519
 
 
520
        This indicates that weave1:weave2 of the old weave should be
 
521
        replaced by the sequence of lines in newlines.  Note that
 
522
        these line numbers are positions in the total weave and don't
 
523
        correspond to the lines in any extracted version, or even the
 
524
        extracted union of included versions.
 
525
 
 
526
        If line1=line2, this is a pure insert; if newlines=[] this is a
 
527
        pure delete.  (Similar to difflib.)
 
528
        """
 
529
        # basis a list of (origin, lineno, line)
 
530
        basis_lineno = []
 
531
        basis_lines = []
 
532
        for origin, lineno, line in self._extract(included):
 
533
            basis_lineno.append(lineno)
 
534
            basis_lines.append(line)
 
535
 
 
536
        # add a sentinal, because we can also match against the final line
 
537
        basis_lineno.append(len(self._l))
 
538
 
 
539
        # XXX: which line of the weave should we really consider
 
540
        # matches the end of the file?  the current code says it's the
 
541
        # last line of the weave?
 
542
 
 
543
        from difflib import SequenceMatcher
 
544
        s = SequenceMatcher(None, basis_lines, lines)
 
545
 
 
546
        # TODO: Perhaps return line numbers from composed weave as well?
 
547
 
 
548
        for tag, i1, i2, j1, j2 in s.get_opcodes():
 
549
            ##print tag, i1, i2, j1, j2
 
550
 
 
551
            if tag == 'equal':
 
552
                continue
 
553
 
 
554
            # i1,i2 are given in offsets within basis_lines; we need to map them
 
555
            # back to offsets within the entire weave
 
556
            real_i1 = basis_lineno[i1]
 
557
            real_i2 = basis_lineno[i2]
 
558
 
 
559
            assert 0 <= j1
 
560
            assert j1 <= j2
 
561
            assert j2 <= len(lines)
 
562
 
 
563
            yield real_i1, real_i2, lines[j1:j2]
 
564
 
 
565
 
 
566
            
 
567
    def plan_merge(self, ver_a, ver_b):
 
568
        """Return pseudo-annotation indicating how the two versions merge.
 
569
 
 
570
        This is computed between versions a and b and their common
 
571
        base.
 
572
 
 
573
        Weave lines present in none of them are skipped entirely.
 
574
        """
 
575
        inc_a = self.inclusions_bitset([ver_a])
 
576
        inc_b = self.inclusions_bitset([ver_b])
 
577
        inc_c = inc_a & inc_b
 
578
 
 
579
        for lineno, insert, deleteset, line in self._walk():
 
580
            insertset = (1L << insert)
 
581
            if deleteset & inc_c:
 
582
                # killed in parent; can't be in either a or b
 
583
                # not relevant to our work
 
584
                yield 'killed-base', line
 
585
            elif insertset & inc_c:
 
586
                # was inserted in base
 
587
                killed_a = bool(deleteset & inc_a)
 
588
                killed_b = bool(deleteset & inc_b)
 
589
                if killed_a and killed_b:
 
590
                    yield 'killed-both', line
 
591
                elif killed_a:
 
592
                    yield 'killed-a', line
 
593
                elif killed_b:
 
594
                    yield 'killed-b', line
 
595
                else:
 
596
                    yield 'unchanged', line
 
597
            elif insertset & inc_a:
 
598
                if deleteset & inc_a:
 
599
                    yield 'ghost-a', line
 
600
                else:
 
601
                    # new in A; not in B
 
602
                    yield 'new-a', line
 
603
            elif insertset & inc_b:
 
604
                if deleteset & inc_b:
 
605
                    yield 'ghost-b', line
 
606
                else:
 
607
                    yield 'new-b', line
 
608
            else:
 
609
                # not in either revision
 
610
                yield 'irrelevant', line
 
611
 
 
612
        yield 'unchanged', ''           # terminator
 
613
 
 
614
 
 
615
 
 
616
    def weave_merge(self, plan):
 
617
        lines_a = []
 
618
        lines_b = []
 
619
        ch_a = ch_b = False
 
620
 
 
621
        for state, line in plan:
 
622
            if state == 'unchanged' or state == 'killed-both':
 
623
                # resync and flush queued conflicts changes if any
 
624
                if not lines_a and not lines_b:
 
625
                    pass
 
626
                elif ch_a and not ch_b:
 
627
                    # one-sided change:                    
 
628
                    for l in lines_a: yield l
 
629
                elif ch_b and not ch_a:
 
630
                    for l in lines_b: yield l
 
631
                elif lines_a == lines_b:
 
632
                    for l in lines_a: yield l
 
633
                else:
 
634
                    yield '<<<<\n'
 
635
                    for l in lines_a: yield l
 
636
                    yield '====\n'
 
637
                    for l in lines_b: yield l
 
638
                    yield '>>>>\n'
 
639
 
 
640
                del lines_a[:]
 
641
                del lines_b[:]
 
642
                ch_a = ch_b = False
 
643
                
 
644
            if state == 'unchanged':
 
645
                if line:
 
646
                    yield line
 
647
            elif state == 'killed-a':
 
648
                ch_a = True
 
649
                lines_b.append(line)
 
650
            elif state == 'killed-b':
 
651
                ch_b = True
 
652
                lines_a.append(line)
 
653
            elif state == 'new-a':
 
654
                ch_a = True
 
655
                lines_a.append(line)
 
656
            elif state == 'new-b':
 
657
                ch_b = True
 
658
                lines_b.append(line)
 
659
            else:
 
660
                assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
 
661
                                 'killed-both'), \
 
662
                       state
 
663
 
 
664
                
 
665
 
 
666
 
 
667
 
 
668
 
 
669
 
 
670
def weave_info(filename, out):
 
671
    """Show some text information about the weave."""
 
672
    from weavefile import read_weave
 
673
    wf = file(filename, 'rb')
 
674
    w = read_weave(wf)
 
675
    # FIXME: doesn't work on pipes
 
676
    weave_size = wf.tell()
 
677
    print >>out, "weave file size %d bytes" % weave_size
 
678
    print >>out, "weave contains %d versions" % len(w._v)
 
679
 
 
680
    total = 0
 
681
    print '%6s %6s %8s %40s %20s' % ('ver', 'lines', 'bytes', 'sha1', 'parents')
 
682
    for i in (6, 6, 8, 40, 20):
 
683
        print '-' * i,
 
684
    print
 
685
    for i in range(len(w._v)):
 
686
        text = w.get(i)
 
687
        lines = len(text)
 
688
        bytes = sum((len(a) for a in text))
 
689
        sha1 = w._sha1s[i]
 
690
        print '%6d %6d %8d %40s' % (i, lines, bytes, sha1),
 
691
        for pv in w._v[i]:
 
692
            print pv,
 
693
        print
 
694
        total += bytes
 
695
 
 
696
    print >>out, "versions total %d bytes" % total
 
697
    print >>out, "compression ratio %.3f" % (float(total)/float(weave_size))
 
698
 
 
699
 
 
700
def usage():
 
701
    print """bzr weave tool
 
702
 
 
703
Experimental tool for weave algorithm.
 
704
 
 
705
usage:
 
706
    weave init WEAVEFILE
 
707
        Create an empty weave file
 
708
    weave get WEAVEFILE VERSION
 
709
        Write out specified version.
 
710
    weave check WEAVEFILE
 
711
        Check consistency of all versions.
 
712
    weave info WEAVEFILE
 
713
        Display table of contents.
 
714
    weave add WEAVEFILE [BASE...] < NEWTEXT
 
715
        Add NEWTEXT, with specified parent versions.
 
716
    weave annotate WEAVEFILE VERSION
 
717
        Display origin of each line.
 
718
    weave mash WEAVEFILE VERSION...
 
719
        Display composite of all selected versions.
 
720
    weave merge WEAVEFILE VERSION1 VERSION2 > OUT
 
721
        Auto-merge two versions and display conflicts.
 
722
 
 
723
example:
 
724
 
 
725
    % weave init foo.weave
 
726
    % vi foo.txt
 
727
    % weave add foo.weave < foo.txt
 
728
    added version 0
 
729
 
 
730
    (create updated version)
 
731
    % vi foo.txt
 
732
    % weave get foo.weave 0 | diff -u - foo.txt
 
733
    % weave add foo.weave 0 < foo.txt
 
734
    added version 1
 
735
 
 
736
    % weave get foo.weave 0 > foo.txt       (create forked version)
 
737
    % vi foo.txt
 
738
    % weave add foo.weave 0 < foo.txt
 
739
    added version 2
 
740
 
 
741
    % weave merge foo.weave 1 2 > foo.txt   (merge them)
 
742
    % vi foo.txt                            (resolve conflicts)
 
743
    % weave add foo.weave 1 2 < foo.txt     (commit merged version)     
 
744
    
 
745
"""
 
746
    
 
747
 
 
748
 
 
749
def main(argv):
 
750
    import sys
 
751
    import os
 
752
    from weavefile import write_weave, read_weave
 
753
    from bzrlib.progress import ProgressBar
 
754
 
 
755
    #import psyco
 
756
    #psyco.full()
 
757
 
 
758
    cmd = argv[1]
 
759
 
 
760
    def readit():
 
761
        return read_weave(file(argv[2], 'rb'))
 
762
    
 
763
    if cmd == 'help':
 
764
        usage()
 
765
    elif cmd == 'add':
 
766
        w = readit()
 
767
        # at the moment, based on everything in the file
 
768
        parents = map(int, argv[3:])
 
769
        lines = sys.stdin.readlines()
 
770
        ver = w.add(parents, lines)
 
771
        write_weave(w, file(argv[2], 'wb'))
 
772
        print 'added version %d' % ver
 
773
    elif cmd == 'init':
 
774
        fn = argv[2]
 
775
        if os.path.exists(fn):
 
776
            raise IOError("file exists")
 
777
        w = Weave()
 
778
        write_weave(w, file(fn, 'wb'))
 
779
    elif cmd == 'get': # get one version
 
780
        w = readit()
 
781
        sys.stdout.writelines(w.get_iter(int(argv[3])))
 
782
        
 
783
    elif cmd == 'mash': # get composite
 
784
        w = readit()
 
785
        sys.stdout.writelines(w.mash_iter(map(int, argv[3:])))
 
786
 
 
787
    elif cmd == 'annotate':
 
788
        w = readit()
 
789
        # newline is added to all lines regardless; too hard to get
 
790
        # reasonable formatting otherwise
 
791
        lasto = None
 
792
        for origin, text in w.annotate(int(argv[3])):
 
793
            text = text.rstrip('\r\n')
 
794
            if origin == lasto:
 
795
                print '      | %s' % (text)
 
796
            else:
 
797
                print '%5d | %s' % (origin, text)
 
798
                lasto = origin
 
799
                
 
800
    elif cmd == 'info':
 
801
        weave_info(argv[2], sys.stdout)
 
802
        
 
803
    elif cmd == 'check':
 
804
        w = readit()
 
805
        pb = ProgressBar()
 
806
        w.check(pb)
 
807
        pb.clear()
 
808
 
 
809
    elif cmd == 'inclusions':
 
810
        w = readit()
 
811
        print ' '.join(map(str, w.inclusions([int(argv[3])])))
 
812
 
 
813
    elif cmd == 'parents':
 
814
        w = readit()
 
815
        print ' '.join(map(str, w._v[int(argv[3])]))
 
816
 
 
817
    elif cmd == 'plan-merge':
 
818
        w = readit()
 
819
        for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
 
820
            if line:
 
821
                print '%14s | %s' % (state, line),
 
822
 
 
823
    elif cmd == 'merge':
 
824
        w = readit()
 
825
        p = w.plan_merge(int(argv[3]), int(argv[4]))
 
826
        sys.stdout.writelines(w.weave_merge(p))
 
827
            
 
828
    elif cmd == 'mash-merge':
 
829
        if len(argv) != 5:
 
830
            usage()
 
831
            return 1
 
832
 
 
833
        w = readit()
 
834
        v1, v2 = map(int, argv[3:5])
 
835
 
 
836
        basis = w.inclusions([v1]).intersection(w.inclusions([v2]))
 
837
 
 
838
        base_lines = list(w.mash_iter(basis))
 
839
        a_lines = list(w.get(v1))
 
840
        b_lines = list(w.get(v2))
 
841
 
 
842
        from bzrlib.merge3 import Merge3
 
843
        m3 = Merge3(base_lines, a_lines, b_lines)
 
844
 
 
845
        name_a = 'version %d' % v1
 
846
        name_b = 'version %d' % v2
 
847
        sys.stdout.writelines(m3.merge_lines(name_a=name_a, name_b=name_b))
 
848
    else:
 
849
        raise ValueError('unknown command %r' % cmd)
 
850
    
 
851
 
 
852
if __name__ == '__main__':
 
853
    import sys
 
854
    sys.exit(main(sys.argv))