~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

  • Committer: Martin Pool
  • Date: 2005-07-18 13:12:43 UTC
  • Revision ID: mbp@sourcefrog.net-20050718131243-44532527fd065b31
- update convertinv to work with current weave code

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