~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

  • Committer: Robert Collins
  • Date: 2005-09-23 09:25:16 UTC
  • mto: (1092.3.4)
  • mto: This revision was merged to the branch mainline in revision 1390.
  • Revision ID: robertc@robertcollins.net-20050923092516-e2c3c0f31288669d
Merge what applied of Alexander Belchenko's win32 patch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
21
21
 
22
22
"""Weave - storage of related text file versions"""
23
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?
24
55
 
25
56
# XXX: If we do weaves this way, will a merge still behave the same
26
57
# way if it's done in a different order?  That's a pretty desirable
43
74
 
44
75
# TODO: Parallel-extract that passes back each line along with a
45
76
# description of which revisions include it.  Nice for checking all
46
 
# shas or calculating stats in parallel.
 
77
# shas in parallel.
47
78
 
48
79
# TODO: Using a single _extract routine and then processing the output
49
80
# is probably inefficient.  It's simple enough that we can afford to
50
81
# have slight specializations for different ways its used: annotate,
51
82
# basis for add, get, etc.
52
83
 
53
 
# TODO: Probably the API should work only in names to hide the integer
54
 
# indexes from the user.
55
 
 
56
 
# TODO: Is there any potential performance win by having an add()
57
 
# variant that is passed a pre-cooked version of the single basis
58
 
# version?
59
 
 
60
 
# TODO: Reweave can possibly be made faster by remembering diffs
61
 
# where the basis and destination are unchanged.
62
 
 
63
 
# FIXME: Sometimes we will be given a parents list for a revision
64
 
# that includes some redundant parents (i.e. already a parent of 
65
 
# something in the list.)  We should eliminate them.  This can 
66
 
# be done fairly efficiently because the sequence numbers constrain
67
 
# the possible relationships.
 
84
# TODO: Perhaps the API should work only in names to hide the integer
 
85
# indexes from the user?
 
86
 
68
87
 
69
88
 
70
89
import sha
71
 
from difflib import SequenceMatcher
72
 
 
73
 
from bzrlib.trace import mutter
74
 
from bzrlib.errors import WeaveError, WeaveFormatError, WeaveParentMismatch, \
75
 
        WeaveRevisionNotPresent, WeaveRevisionAlreadyPresent
76
 
from bzrlib.tsort import topo_sort
77
 
 
 
90
 
 
91
 
 
92
 
 
93
class WeaveError(Exception):
 
94
    """Exception in processing weave"""
 
95
 
 
96
 
 
97
class WeaveFormatError(WeaveError):
 
98
    """Weave invariant violated"""
 
99
    
78
100
 
79
101
class Weave(object):
80
102
    """weave - versioned text file storage.
91
113
 
92
114
    * a nonnegative index number.
93
115
 
94
 
    * a version-id string.
 
116
    * a version-id string. (not implemented yet)
95
117
 
96
118
    Typically the index number will be valid only inside this weave and
97
119
    the version-id is used to reference it in the larger world.
159
181
 
160
182
    _name_map
161
183
        For each name, the version number.
162
 
 
163
 
    _weave_name
164
 
        Descriptive name of this weave; typically the filename if known.
165
 
        Set by read_weave.
166
184
    """
167
185
 
168
 
    __slots__ = ['_weave', '_parents', '_sha1s', '_names', '_name_map',
169
 
                 '_weave_name']
 
186
    __slots__ = ['_weave', '_parents', '_sha1s', '_names', '_name_map']
170
187
    
171
 
    def __init__(self, weave_name=None):
 
188
    def __init__(self):
172
189
        self._weave = []
173
190
        self._parents = []
174
191
        self._sha1s = []
175
192
        self._names = []
176
193
        self._name_map = {}
177
 
        self._weave_name = weave_name
178
 
 
179
 
    def __repr__(self):
180
 
        return "Weave(%r)" % self._weave_name
181
 
 
182
 
 
183
 
    def copy(self):
184
 
        """Return a deep copy of self.
185
 
        
186
 
        The copy can be modified without affecting the original weave."""
187
 
        other = Weave()
188
 
        other._weave = self._weave[:]
189
 
        other._parents = self._parents[:]
190
 
        other._sha1s = self._sha1s[:]
191
 
        other._names = self._names[:]
192
 
        other._name_map = self._name_map.copy()
193
 
        other._weave_name = self._weave_name
194
 
        return other
 
194
 
195
195
 
196
196
    def __eq__(self, other):
197
197
        if not isinstance(other, Weave):
204
204
    def __ne__(self, other):
205
205
        return not self.__eq__(other)
206
206
 
207
 
    def __contains__(self, name):
208
 
        return self._name_map.has_key(name)
209
 
 
210
 
    def maybe_lookup(self, name_or_index):
211
 
        """Convert possible symbolic name to index, or pass through indexes."""
212
 
        if isinstance(name_or_index, (int, long)):
213
 
            return name_or_index
214
 
        else:
215
 
            return self.lookup(name_or_index)
216
 
 
217
 
        
 
207
 
218
208
    def lookup(self, name):
219
 
        """Convert symbolic version name to index."""
220
209
        try:
221
210
            return self._name_map[name]
222
211
        except KeyError:
223
 
            raise WeaveRevisionNotPresent(name, self)
224
 
 
225
 
    def names(self):
226
 
        return self._names[:]
227
 
 
228
 
    def iter_names(self):
229
 
        """Yield a list of all names in this weave."""
230
 
        return iter(self._names)
231
 
 
232
 
    def idx_to_name(self, version):
233
 
        return self._names[version]
234
 
 
235
 
    def _check_repeated_add(self, name, parents, text, sha1):
236
 
        """Check that a duplicated add is OK.
237
 
 
238
 
        If it is, return the (old) index; otherwise raise an exception.
239
 
        """
240
 
        idx = self.lookup(name)
241
 
        if sorted(self._parents[idx]) != sorted(parents) \
242
 
            or sha1 != self._sha1s[idx]:
243
 
            raise WeaveRevisionAlreadyPresent(name, self)
244
 
        return idx
 
212
            raise WeaveError("name %s not present in weave" % name)
 
213
 
245
214
        
246
 
    def add(self, name, parents, text, sha1=None):
 
215
    def add(self, name, parents, text):
247
216
        """Add a single text on top of the weave.
248
217
  
249
218
        Returns the index number of the newly added version.
256
225
            List or set of direct parent version numbers.
257
226
            
258
227
        text
259
 
            Sequence of lines to be added in the new version.
260
 
 
261
 
        sha -- SHA-1 of the file, if known.  This is trusted to be
262
 
            correct if supplied.
263
 
        """
264
 
        from bzrlib.osutils import sha_strings
 
228
            Sequence of lines to be added in the new version."""
265
229
 
266
230
        assert isinstance(name, basestring)
267
 
        if sha1 is None:
268
 
            sha1 = sha_strings(text)
269
231
        if name in self._name_map:
270
 
            return self._check_repeated_add(name, parents, text, sha1)
271
 
 
272
 
        parents = map(self.maybe_lookup, parents)
 
232
            raise WeaveError("name %r already present in weave" % name)
 
233
        
273
234
        self._check_versions(parents)
274
235
        ## self._check_lines(text)
275
236
        new_version = len(self._parents)
276
237
 
 
238
        s = sha.new()
 
239
        map(s.update, text)
 
240
        sha1 = s.hexdigest()
 
241
        del s
277
242
 
278
243
        # if we abort after here the (in-memory) weave will be corrupt because only
279
244
        # some fields are updated
328
293
        #print 'basis_lines:', basis_lines
329
294
        #print 'new_lines:  ', lines
330
295
 
 
296
        from difflib import SequenceMatcher
331
297
        s = SequenceMatcher(None, basis_lines, text)
332
298
 
333
299
        # offset gives the number of lines that have been inserted
368
334
 
369
335
        return new_version
370
336
 
371
 
    def add_identical(self, old_rev_id, new_rev_id, parents):
372
 
        """Add an identical text to old_rev_id as new_rev_id."""
373
 
        old_lines = self.get(self.lookup(old_rev_id))
374
 
        self.add(new_rev_id, parents, old_lines)
375
337
 
376
338
    def inclusions(self, versions):
377
339
        """Return set of all ancestors of given version(s)."""
378
340
        i = set(versions)
379
 
        for v in xrange(max(versions), 0, -1):
380
 
            if v in i:
381
 
                # include all its parents
382
 
                i.update(self._parents[v])
383
 
        return i
384
 
        ## except IndexError:
385
 
        ##     raise ValueError("version %d not present in weave" % v)
386
 
 
387
 
 
388
 
    def parents(self, version):
389
 
        return self._parents[version]
390
 
 
391
 
 
392
 
    def parent_names(self, version):
393
 
        """Return version names for parents of a version."""
394
 
        return map(self.idx_to_name, self._parents[self.lookup(version)])
 
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)
395
351
 
396
352
 
397
353
    def minimal_parents(self, version):
437
393
                raise IndexError("invalid version number %r" % i)
438
394
 
439
395
    
440
 
    def annotate(self, name_or_index):
441
 
        return list(self.annotate_iter(name_or_index))
442
 
 
443
 
 
444
 
    def annotate_iter(self, name_or_index):
 
396
    def annotate(self, index):
 
397
        return list(self.annotate_iter(index))
 
398
 
 
399
 
 
400
    def annotate_iter(self, version):
445
401
        """Yield list of (index-id, line) pairs for the specified version.
446
402
 
447
403
        The index indicates when the line originated in the weave."""
448
 
        incls = [self.maybe_lookup(name_or_index)]
449
 
        for origin, lineno, text in self._extract(incls):
 
404
        for origin, lineno, text in self._extract([version]):
450
405
            yield origin, text
451
406
 
 
407
 
452
408
    def _walk(self):
453
409
        """Walk the weave.
454
410
 
476
432
                elif c == ']':
477
433
                    dset.remove(v)
478
434
                else:
479
 
                    raise WeaveFormatError('unexpected instruction %r' % v)
 
435
                    raise WeaveFormatError('unexpected instruction %r'
 
436
                                           % v)
480
437
            else:
481
438
                assert isinstance(l, basestring)
482
439
                assert istack
494
451
 
495
452
        The set typically but not necessarily corresponds to a version.
496
453
        """
497
 
        for i in versions:
498
 
            if not isinstance(i, int):
499
 
                raise ValueError(i)
500
 
            
501
454
        included = self.inclusions(versions)
502
455
 
503
456
        istack = []
536
489
                if isactive:
537
490
                    result.append((istack[-1], lineno, l))
538
491
            lineno += 1
 
492
 
539
493
        if istack:
540
 
            raise WeaveFormatError("unclosed insertion blocks "
541
 
                    "at end of weave: %s" % istack)
 
494
            raise WFE("unclosed insertion blocks at end of weave",
 
495
                                   istack)
542
496
        if dset:
543
 
            raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
544
 
                                   % dset)
 
497
            raise WFE("unclosed deletion blocks at end of weave",
 
498
                                   dset)
 
499
 
545
500
        return result
546
 
 
547
 
 
548
 
    def get_iter(self, name_or_index):
 
501
    
 
502
 
 
503
 
 
504
    def get_iter(self, version):
549
505
        """Yield lines for the specified version."""
550
 
        incls = [self.maybe_lookup(name_or_index)]
551
 
        for origin, lineno, line in self._extract(incls):
 
506
        for origin, lineno, line in self._extract([version]):
552
507
            yield line
553
508
 
554
509
 
555
 
    def get_text(self, name_or_index):
556
 
        return ''.join(self.get_iter(name_or_index))
557
 
        assert isinstance(version, int)
558
 
 
559
 
 
560
 
    def get_lines(self, name_or_index):
561
 
        return list(self.get_iter(name_or_index))
562
 
 
563
 
 
564
 
    get = get_lines
 
510
    def get(self, index):
 
511
        return list(self.get_iter(index))
565
512
 
566
513
 
567
514
    def mash_iter(self, included):
568
515
        """Return composed version of multiple included versions."""
569
 
        included = map(self.maybe_lookup, included)
570
516
        for origin, lineno, text in self._extract(included):
571
517
            yield text
572
518
 
621
567
        # properly paired, etc.
622
568
 
623
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
 
624
588
    def _delta(self, included, lines):
625
589
        """Return changes from basis to new revision.
626
590
 
640
604
        If line1=line2, this is a pure insert; if newlines=[] this is a
641
605
        pure delete.  (Similar to difflib.)
642
606
        """
643
 
        raise NotImplementedError()
 
607
 
644
608
 
645
609
            
646
610
    def plan_merge(self, ver_a, ver_b):
709
673
                elif lines_a == lines_b:
710
674
                    for l in lines_a: yield l
711
675
                else:
712
 
                    yield '<<<<<<<\n'
 
676
                    yield '<<<<\n'
713
677
                    for l in lines_a: yield l
714
 
                    yield '=======\n'
 
678
                    yield '====\n'
715
679
                    for l in lines_b: yield l
716
 
                    yield '>>>>>>>\n'
 
680
                    yield '>>>>\n'
717
681
 
718
682
                del lines_a[:]
719
683
                del lines_b[:]
740
704
                       state
741
705
 
742
706
                
743
 
    def join(self, other):
744
 
        """Integrate versions from other into this weave.
745
 
 
746
 
        The resulting weave contains all the history of both weaves; 
747
 
        any version you could retrieve from either self or other can be 
748
 
        retrieved from self after this call.
749
 
 
750
 
        It is illegal for the two weaves to contain different values 
751
 
        or different parents for any version.  See also reweave().
752
 
        """
753
 
        if other.numversions() == 0:
754
 
            return          # nothing to update, easy
755
 
        # two loops so that we do not change ourselves before verifying it
756
 
        # will be ok
757
 
        # work through in index order to make sure we get all dependencies
758
 
        for other_idx, name in enumerate(other._names):
759
 
            if self._check_version_consistent(other, other_idx, name):
760
 
                continue
761
 
        for other_idx, name in enumerate(other._names):
762
 
            # TODO: If all the parents of the other version are already 
763
 
            # present then we can avoid some work by just taking the delta
764
 
            # and adjusting the offsets.
765
 
            new_parents = self._imported_parents(other, other_idx)
766
 
            lines = other.get_lines(other_idx)
767
 
            sha1 = other._sha1s[other_idx]
768
 
            self.add(name, new_parents, lines, sha1)
769
 
 
770
 
 
771
 
    def _imported_parents(self, other, other_idx):
772
 
        """Return list of parents in self corresponding to indexes in other."""
773
 
        new_parents = []
774
 
        for parent_idx in other._parents[other_idx]:
775
 
            parent_name = other._names[parent_idx]
776
 
            if parent_name not in self._names:
777
 
                # should not be possible
778
 
                raise WeaveError("missing parent {%s} of {%s} in %r" 
779
 
                                 % (parent_name, other._name_map[other_idx], self))
780
 
            new_parents.append(self._name_map[parent_name])
781
 
        return new_parents
782
 
 
783
 
    def _check_version_consistent(self, other, other_idx, name):
784
 
        """Check if a version in consistent in this and other.
785
 
 
786
 
        To be consistent it must have:
787
 
 
788
 
         * the same text
789
 
         * the same direct parents (by name, not index, and disregarding
790
 
           order)
791
 
        
792
 
        If present & correct return True;
793
 
        if not present in self return False; 
794
 
        if inconsistent raise error."""
795
 
        this_idx = self._name_map.get(name, -1)
796
 
        if this_idx != -1:
797
 
            if self._sha1s[this_idx] != other._sha1s[other_idx]:
798
 
                raise WeaveError("inconsistent texts for version {%s} "
799
 
                                 "when joining weaves"
800
 
                                 % (name))
801
 
            self_parents = self._parents[this_idx]
802
 
            other_parents = other._parents[other_idx]
803
 
            n1 = [self._names[i] for i in self_parents]
804
 
            n2 = [other._names[i] for i in other_parents]
805
 
            n1.sort()
806
 
            n2.sort()
807
 
            if n1 != n2:
808
 
                raise WeaveParentMismatch("inconsistent parents "
809
 
                    "for version {%s}: %s vs %s" % (name, n1, n2))
810
 
            else:
811
 
                return True         # ok!
812
 
        else:
813
 
            return False
814
 
 
815
 
    def reweave(self, other):
816
 
        """Reweave self with other."""
817
 
        new_weave = reweave(self, other)
818
 
        for attr in self.__slots__:
819
 
            setattr(self, attr, getattr(new_weave, attr))
820
 
 
821
 
 
822
 
def reweave(wa, wb):
823
 
    """Combine two weaves and return the result.
824
 
 
825
 
    This works even if a revision R has different parents in 
826
 
    wa and wb.  In the resulting weave all the parents are given.
827
 
 
828
 
    This is done by just building up a new weave, maintaining ordering 
829
 
    of the versions in the two inputs.  More efficient approaches
830
 
    might be possible but it should only be necessary to do 
831
 
    this operation rarely, when a new previously ghost version is 
832
 
    inserted.
833
 
    """
834
 
    wr = Weave()
835
 
    ia = ib = 0
836
 
    queue_a = range(wa.numversions())
837
 
    queue_b = range(wb.numversions())
838
 
    # first determine combined parents of all versions
839
 
    # map from version name -> all parent names
840
 
    combined_parents = _reweave_parent_graphs(wa, wb)
841
 
    mutter("combined parents: %r", combined_parents)
842
 
    order = topo_sort(combined_parents.iteritems())
843
 
    mutter("order to reweave: %r", order)
844
 
    for name in order:
845
 
        if name in wa._name_map:
846
 
            lines = wa.get_lines(name)
847
 
            if name in wb._name_map:
848
 
                assert lines == wb.get_lines(name)
849
 
        else:
850
 
            lines = wb.get_lines(name)
851
 
        wr.add(name, combined_parents[name], lines)
852
 
    return wr
853
 
 
854
 
 
855
 
def _reweave_parent_graphs(wa, wb):
856
 
    """Return combined parent ancestry for two weaves.
857
 
    
858
 
    Returned as a list of (version_name, set(parent_names))"""
859
 
    combined = {}
860
 
    for weave in [wa, wb]:
861
 
        for idx, name in enumerate(weave._names):
862
 
            p = combined.setdefault(name, set())
863
 
            p.update(map(weave.idx_to_name, weave._parents[idx]))
864
 
    return combined
 
707
 
 
708
 
 
709
 
865
710
 
866
711
 
867
712
def weave_toc(w):
878
723
 
879
724
 
880
725
 
881
 
def weave_stats(weave_file, pb):
 
726
def weave_stats(weave_file):
 
727
    from bzrlib.progress import ProgressBar
882
728
    from bzrlib.weavefile import read_weave
883
729
 
 
730
    pb = ProgressBar()
 
731
 
884
732
    wf = file(weave_file, 'rb')
885
733
    w = read_weave(wf)
886
734
    # FIXME: doesn't work on pipes
890
738
    vers = len(w)
891
739
    for i in range(vers):
892
740
        pb.update('checking sizes', i, vers)
893
 
        for origin, lineno, line in w._extract([i]):
 
741
        for line in w.get_iter(i):
894
742
            total += len(line)
895
743
 
896
744
    pb.clear()
927
775
        Display composite of all selected versions.
928
776
    weave merge WEAVEFILE VERSION1 VERSION2 > OUT
929
777
        Auto-merge two versions and display conflicts.
930
 
    weave diff WEAVEFILE VERSION1 VERSION2 
931
 
        Show differences between two versions.
932
778
 
933
779
example:
934
780
 
959
805
def main(argv):
960
806
    import sys
961
807
    import os
962
 
    try:
963
 
        import bzrlib
964
 
    except ImportError:
965
 
        # in case we're run directly from the subdirectory
966
 
        sys.path.append('..')
967
 
        import bzrlib
968
 
    from bzrlib.weavefile import write_weave, read_weave
 
808
    from weavefile import write_weave, read_weave
969
809
    from bzrlib.progress import ProgressBar
970
810
 
971
811
    try:
1008
848
        w = readit()
1009
849
        sys.stdout.writelines(w.mash_iter(map(int, argv[3:])))
1010
850
 
1011
 
    elif cmd == 'diff':
1012
 
        from difflib import unified_diff
1013
 
        w = readit()
1014
 
        fn = argv[2]
1015
 
        v1, v2 = map(int, argv[3:5])
1016
 
        lines1 = w.get(v1)
1017
 
        lines2 = w.get(v2)
1018
 
        diff_gen = unified_diff(lines1, lines2,
1019
 
                                '%s version %d' % (fn, v1),
1020
 
                                '%s version %d' % (fn, v2))
1021
 
        sys.stdout.writelines(diff_gen)
1022
 
            
1023
851
    elif cmd == 'annotate':
1024
852
        w = readit()
1025
853
        # newline is added to all lines regardless; too hard to get
1037
865
        weave_toc(readit())
1038
866
 
1039
867
    elif cmd == 'stats':
1040
 
        weave_stats(argv[2], ProgressBar())
 
868
        weave_stats(argv[2])
1041
869
        
1042
870
    elif cmd == 'check':
1043
871
        w = readit()