← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

merge merge tweaks from aaron, which includes latest .dev

Show diffs side-by-side

added added

removed removed

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