← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

  • Committer: Martin Pool
  • Date: 2009-01-13 03:06:36 UTC
  • mfrom: (3932.2.3 1.11)
  • mto: This revision was merged to the branch mainline in revision 3937.
  • Revision ID: mbp@sourcefrog.net-20090113030636-dqx4t8yaaqgdvam5
Merge 1.11rc1

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/weave.py
1
 
# Copyright (C) 2005, 2009 Canonical Ltd
 
1
#! /usr/bin/python
 
2
 
 
3
# Copyright (C) 2005 Canonical Ltd
2
4
#
3
5
# This program is free software; you can redistribute it and/or modify
4
6
# it under the terms of the GNU General Public License as published by
12
14
#
13
15
# You should have received a copy of the GNU General Public License
14
16
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
17
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
18
 
17
19
# Author: Martin Pool <mbp@canonical.com>
18
20
 
 
21
 
19
22
"""Weave - storage of related text file versions"""
20
23
 
21
 
from __future__ import absolute_import
22
24
 
23
25
# XXX: If we do weaves this way, will a merge still behave the same
24
26
# way if it's done in a different order?  That's a pretty desirable
59
61
# where the basis and destination are unchanged.
60
62
 
61
63
# FIXME: Sometimes we will be given a parents list for a revision
62
 
# that includes some redundant parents (i.e. already a parent of
63
 
# something in the list.)  We should eliminate them.  This can
 
64
# that includes some redundant parents (i.e. already a parent of 
 
65
# something in the list.)  We should eliminate them.  This can 
64
66
# be done fairly efficiently because the sequence numbers constrain
65
67
# the possible relationships.
66
68
 
69
71
from copy import copy
70
72
from cStringIO import StringIO
71
73
import os
 
74
import time
 
75
import warnings
72
76
 
73
77
from bzrlib.lazy_import import lazy_import
74
78
lazy_import(globals(), """
77
81
from bzrlib import (
78
82
    errors,
79
83
    osutils,
 
84
    progress,
80
85
    )
81
86
from bzrlib.errors import (WeaveError, WeaveFormatError, WeaveParentMismatch,
82
87
        RevisionAlreadyPresent,
83
88
        RevisionNotPresent,
84
89
        UnavailableRepresentation,
 
90
        WeaveRevisionAlreadyPresent,
 
91
        WeaveRevisionNotPresent,
85
92
        )
86
93
from bzrlib.osutils import dirname, sha, sha_strings, split_lines
87
94
import bzrlib.patiencediff
92
99
    AbsentContentFactory,
93
100
    adapter_registry,
94
101
    ContentFactory,
95
 
    sort_groupcompress,
96
102
    VersionedFile,
97
103
    )
98
104
from bzrlib.weavefile import _read_weave_v5, write_weave_v5
125
131
 
126
132
class Weave(VersionedFile):
127
133
    """weave - versioned text file storage.
128
 
 
 
134
    
129
135
    A Weave manages versions of line-based text files, keeping track
130
136
    of the originating version for each line.
131
137
 
177
183
 
178
184
    * It doesn't seem very useful to have an active insertion
179
185
      inside an inactive insertion, but it might happen.
180
 
 
 
186
      
181
187
    * Therefore, all instructions are always"considered"; that
182
188
      is passed onto and off the stack.  An outer inactive block
183
189
      doesn't disable an inner block.
253
259
 
254
260
    def copy(self):
255
261
        """Return a deep copy of self.
256
 
 
 
262
        
257
263
        The copy can be modified without affecting the original weave."""
258
264
        other = Weave()
259
265
        other._weave = self._weave[:]
269
275
            return False
270
276
        return self._parents == other._parents \
271
277
               and self._weave == other._weave \
272
 
               and self._sha1s == other._sha1s
273
 
 
 
278
               and self._sha1s == other._sha1s 
 
279
    
274
280
    def __ne__(self, other):
275
281
        return not self.__eq__(other)
276
282
 
315
321
            new_versions = tsort.topo_sort(parents)
316
322
            new_versions.extend(set(versions).difference(set(parents)))
317
323
            versions = new_versions
318
 
        elif ordering == 'groupcompress':
319
 
            parents = self.get_parent_map(versions)
320
 
            new_versions = sort_groupcompress(parents)
321
 
            new_versions.extend(set(versions).difference(set(parents)))
322
 
            versions = new_versions
323
324
        for version in versions:
324
325
            if version in self:
325
326
                yield WeaveContentFactory(version, self)
348
349
    def insert_record_stream(self, stream):
349
350
        """Insert a record stream into this versioned file.
350
351
 
351
 
        :param stream: A stream of records to insert.
 
352
        :param stream: A stream of records to insert. 
352
353
        :return: None
353
354
        :seealso VersionedFile.get_record_stream:
354
355
        """
371
372
                    adapter_factory = adapter_registry.get(adapter_key)
372
373
                    adapter = adapter_factory(self)
373
374
                    adapters[adapter_key] = adapter
374
 
                lines = split_lines(adapter.get_bytes(record))
 
375
                lines = split_lines(adapter.get_bytes(
 
376
                    record, record.get_bytes_as(record.storage_kind)))
375
377
                try:
376
378
                    self.add_lines(record.key[0], parents, lines)
377
379
                except RevisionAlreadyPresent:
397
399
 
398
400
    def _add(self, version_id, lines, parents, sha1=None, nostore_sha=None):
399
401
        """Add a single text on top of the weave.
400
 
 
 
402
  
401
403
        Returns the index number of the newly added version.
402
404
 
403
405
        version_id
404
406
            Symbolic name for this version.
405
407
            (Typically the revision-id of the revision that added it.)
406
 
            If None, a name will be allocated based on the hash. (sha1:SHAHASH)
407
408
 
408
409
        parents
409
410
            List or set of direct parent version numbers.
410
 
 
 
411
            
411
412
        lines
412
413
            Sequence of lines to be added in the new version.
413
414
 
419
420
            sha1 = sha_strings(lines)
420
421
        if sha1 == nostore_sha:
421
422
            raise errors.ExistingContent
422
 
        if version_id is None:
423
 
            version_id = "sha1:" + sha1
424
423
        if version_id in self._name_map:
425
424
            return self._check_repeated_add(version_id, parents, lines, sha1)
426
425
 
437
436
        self._names.append(version_id)
438
437
        self._name_map[version_id] = new_version
439
438
 
440
 
 
 
439
            
441
440
        if not parents:
442
441
            # special case; adding with no parents revision; can do
443
442
            # this more quickly by just appending unconditionally.
454
453
            if sha1 == self._sha1s[pv]:
455
454
                # special case: same as the single parent
456
455
                return new_version
457
 
 
 
456
            
458
457
 
459
458
        ancestors = self._inclusions(parents)
460
459
 
509
508
                # i2; we want to insert after this region to make sure
510
509
                # we don't destroy ourselves
511
510
                i = i2 + offset
512
 
                self._weave[i:i] = ([('{', new_version)]
513
 
                                    + lines[j1:j2]
 
511
                self._weave[i:i] = ([('{', new_version)] 
 
512
                                    + lines[j1:j2] 
514
513
                                    + [('}', None)])
515
514
                offset += 2 + (j2 - j1)
516
515
        return new_version
543
542
            if not isinstance(l, basestring):
544
543
                raise ValueError("text line should be a string or unicode, not %s"
545
544
                                 % type(l))
546
 
 
 
545
        
547
546
 
548
547
 
549
548
    def _check_versions(self, indexes):
557
556
    def _compatible_parents(self, my_parents, other_parents):
558
557
        """During join check that other_parents are joinable with my_parents.
559
558
 
560
 
        Joinable is defined as 'is a subset of' - supersets may require
 
559
        Joinable is defined as 'is a subset of' - supersets may require 
561
560
        regeneration of diffs, but subsets do not.
562
561
        """
563
562
        return len(other_parents.difference(my_parents)) == 0
577
576
            version_ids = self.versions()
578
577
        version_ids = set(version_ids)
579
578
        for lineno, inserted, deletes, line in self._walk_internal(version_ids):
580
 
            if inserted not in version_ids: continue
 
579
            # if inserted not in version_ids then it was inserted before the
 
580
            # versions we care about, but because weaves cannot represent ghosts
 
581
            # properly, we do not filter down to that
 
582
            # if inserted not in version_ids: continue
581
583
            if line[-1] != '\n':
582
584
                yield line + '\n', inserted
583
585
            else:
585
587
 
586
588
    def _walk_internal(self, version_ids=None):
587
589
        """Helper method for weave actions."""
588
 
 
 
590
        
589
591
        istack = []
590
592
        dset = set()
591
593
 
672
674
        for i in versions:
673
675
            if not isinstance(i, int):
674
676
                raise ValueError(i)
675
 
 
 
677
            
676
678
        included = self._inclusions(versions)
677
679
 
678
680
        istack = []
687
689
 
688
690
        WFE = WeaveFormatError
689
691
 
690
 
        # wow.
 
692
        # wow. 
691
693
        #  449       0   4474.6820   2356.5590   bzrlib.weave:556(_extract)
692
694
        #  +285282   0   1676.8040   1676.8040   +<isinstance>
693
695
        # 1.6 seconds in 'isinstance'.
699
701
        # we're still spending ~1/4 of the method in isinstance though.
700
702
        # so lets hard code the acceptable string classes we expect:
701
703
        #  449       0   1202.9420    786.2930   bzrlib.weave:556(_extract)
702
 
        # +71352     0    377.5560    377.5560   +<method 'append' of 'list'
 
704
        # +71352     0    377.5560    377.5560   +<method 'append' of 'list' 
703
705
        #                                          objects>
704
706
        # yay, down to ~1/4 the initial extract time, and our inline time
705
707
        # has shrunk again, with isinstance no longer dominating.
706
708
        # tweaking the stack inclusion test to use a set gives:
707
709
        #  449       0   1122.8030    713.0080   bzrlib.weave:556(_extract)
708
 
        # +71352     0    354.9980    354.9980   +<method 'append' of 'list'
 
710
        # +71352     0    354.9980    354.9980   +<method 'append' of 'list' 
709
711
        #                                          objects>
710
712
        # - a 5% win, or possibly just noise. However with large istacks that
711
713
        # 'in' test could dominate, so I'm leaving this change in place -
712
714
        # when its fast enough to consider profiling big datasets we can review.
713
715
 
714
 
 
715
 
 
 
716
              
 
717
             
716
718
 
717
719
        for l in self._weave:
718
720
            if l.__class__ == tuple:
747
749
 
748
750
    def _maybe_lookup(self, name_or_index):
749
751
        """Convert possible symbolic name to index, or pass through indexes.
750
 
 
 
752
        
751
753
        NOT FOR PUBLIC USE.
752
754
        """
753
755
        if isinstance(name_or_index, (int, long)):
763
765
        measured_sha1 = sha_strings(result)
764
766
        if measured_sha1 != expected_sha1:
765
767
            raise errors.WeaveInvalidChecksum(
766
 
                    'file %s, revision %s, expected: %s, measured %s'
 
768
                    'file %s, revision %s, expected: %s, measured %s' 
767
769
                    % (self._weave_name, version_id,
768
770
                       expected_sha1, measured_sha1))
769
771
        return result
811
813
 
812
814
            if set(new_inc) != set(self.get_ancestry(name)):
813
815
                raise AssertionError(
814
 
                    'failed %s != %s'
 
816
                    'failed %s != %s' 
815
817
                    % (set(new_inc), set(self.get_ancestry(name))))
816
818
            inclusions[name] = new_inc
817
819
 
855
857
            parent_name = other._names[parent_idx]
856
858
            if parent_name not in self._name_map:
857
859
                # should not be possible
858
 
                raise WeaveError("missing parent {%s} of {%s} in %r"
 
860
                raise WeaveError("missing parent {%s} of {%s} in %r" 
859
861
                                 % (parent_name, other._name_map[other_idx], self))
860
862
            new_parents.append(self._name_map[parent_name])
861
863
        return new_parents
868
870
         * the same text
869
871
         * the same direct parents (by name, not index, and disregarding
870
872
           order)
871
 
 
 
873
        
872
874
        If present & correct return True;
873
 
        if not present in self return False;
 
875
        if not present in self return False; 
874
876
        if inconsistent raise error."""
875
877
        this_idx = self._name_map.get(name, -1)
876
878
        if this_idx != -1:
909
911
    """A WeaveFile represents a Weave on disk and writes on change."""
910
912
 
911
913
    WEAVE_SUFFIX = '.weave'
912
 
 
 
914
    
913
915
    def __init__(self, name, transport, filemode=None, create=False, access_mode='w', get_scope=None):
914
916
        """Create a WeaveFile.
915
 
 
 
917
        
916
918
        :param create: If not True, only open an existing knit.
917
919
        """
918
920
        super(WeaveFile, self).__init__(name, access_mode, get_scope=get_scope,
920
922
        self._transport = transport
921
923
        self._filemode = filemode
922
924
        try:
923
 
            f = self._transport.get(name + WeaveFile.WEAVE_SUFFIX)
924
 
            _read_weave_v5(StringIO(f.read()), self)
 
925
            _read_weave_v5(self._transport.get(name + WeaveFile.WEAVE_SUFFIX), self)
925
926
        except errors.NoSuchFile:
926
927
            if not create:
927
928
                raise
969
970
        super(WeaveFile, self).insert_record_stream(stream)
970
971
        self._save()
971
972
 
 
973
    @deprecated_method(one_five)
 
974
    def join(self, other, pb=None, msg=None, version_ids=None,
 
975
             ignore_missing=False):
 
976
        """Join other into self and save."""
 
977
        super(WeaveFile, self).join(other, pb, msg, version_ids, ignore_missing)
 
978
        self._save()
 
979
 
972
980
 
973
981
def _reweave(wa, wb, pb=None, msg=None):
974
982
    """Combine two weaves and return the result.
975
983
 
976
 
    This works even if a revision R has different parents in
 
984
    This works even if a revision R has different parents in 
977
985
    wa and wb.  In the resulting weave all the parents are given.
978
986
 
979
 
    This is done by just building up a new weave, maintaining ordering
 
987
    This is done by just building up a new weave, maintaining ordering 
980
988
    of the versions in the two inputs.  More efficient approaches
981
 
    might be possible but it should only be necessary to do
982
 
    this operation rarely, when a new previously ghost version is
 
989
    might be possible but it should only be necessary to do 
 
990
    this operation rarely, when a new previously ghost version is 
983
991
    inserted.
984
992
 
985
993
    :param pb: An optional progress bar, indicating how far done we are
1019
1027
        wr._add(name, lines, [wr._lookup(i) for i in combined_parents[name]])
1020
1028
    return wr
1021
1029
 
1022
 
 
1023
1030
def _reweave_parent_graphs(wa, wb):
1024
1031
    """Return combined parent ancestry for two weaves.
1025
 
 
 
1032
    
1026
1033
    Returned as a list of (version_name, set(parent_names))"""
1027
1034
    combined = {}
1028
1035
    for weave in [wa, wb]:
1030
1037
            p = combined.setdefault(name, set())
1031
1038
            p.update(map(weave._idx_to_name, weave._parents[idx]))
1032
1039
    return combined
 
1040
 
 
1041
 
 
1042
def weave_toc(w):
 
1043
    """Show the weave's table-of-contents"""
 
1044
    print '%6s %50s %10s %10s' % ('ver', 'name', 'sha1', 'parents')
 
1045
    for i in (6, 50, 10, 10):
 
1046
        print '-' * i,
 
1047
    print
 
1048
    for i in range(w.num_versions()):
 
1049
        sha1 = w._sha1s[i]
 
1050
        name = w._names[i]
 
1051
        parent_str = ' '.join(map(str, w._parents[i]))
 
1052
        print '%6d %-50.50s %10.10s %s' % (i, name, sha1, parent_str)
 
1053
 
 
1054
 
 
1055
 
 
1056
def weave_stats(weave_file, pb):
 
1057
    from bzrlib.weavefile import read_weave
 
1058
 
 
1059
    wf = file(weave_file, 'rb')
 
1060
    w = read_weave(wf)
 
1061
    # FIXME: doesn't work on pipes
 
1062
    weave_size = wf.tell()
 
1063
 
 
1064
    total = 0
 
1065
    vers = len(w)
 
1066
    for i in range(vers):
 
1067
        pb.update('checking sizes', i, vers)
 
1068
        for origin, lineno, line in w._extract([i]):
 
1069
            total += len(line)
 
1070
 
 
1071
    pb.clear()
 
1072
 
 
1073
    print 'versions          %9d' % vers
 
1074
    print 'weave file        %9d bytes' % weave_size
 
1075
    print 'total contents    %9d bytes' % total
 
1076
    print 'compression ratio %9.2fx' % (float(total) / float(weave_size))
 
1077
    if vers:
 
1078
        avg = total/vers
 
1079
        print 'average size      %9d bytes' % avg
 
1080
        print 'relative size     %9.2fx' % (float(weave_size) / float(avg))
 
1081
 
 
1082
 
 
1083
def usage():
 
1084
    print """bzr weave tool
 
1085
 
 
1086
Experimental tool for weave algorithm.
 
1087
 
 
1088
usage:
 
1089
    weave init WEAVEFILE
 
1090
        Create an empty weave file
 
1091
    weave get WEAVEFILE VERSION
 
1092
        Write out specified version.
 
1093
    weave check WEAVEFILE
 
1094
        Check consistency of all versions.
 
1095
    weave toc WEAVEFILE
 
1096
        Display table of contents.
 
1097
    weave add WEAVEFILE NAME [BASE...] < NEWTEXT
 
1098
        Add NEWTEXT, with specified parent versions.
 
1099
    weave annotate WEAVEFILE VERSION
 
1100
        Display origin of each line.
 
1101
    weave merge WEAVEFILE VERSION1 VERSION2 > OUT
 
1102
        Auto-merge two versions and display conflicts.
 
1103
    weave diff WEAVEFILE VERSION1 VERSION2 
 
1104
        Show differences between two versions.
 
1105
 
 
1106
example:
 
1107
 
 
1108
    % weave init foo.weave
 
1109
    % vi foo.txt
 
1110
    % weave add foo.weave ver0 < foo.txt
 
1111
    added version 0
 
1112
 
 
1113
    (create updated version)
 
1114
    % vi foo.txt
 
1115
    % weave get foo.weave 0 | diff -u - foo.txt
 
1116
    % weave add foo.weave ver1 0 < foo.txt
 
1117
    added version 1
 
1118
 
 
1119
    % weave get foo.weave 0 > foo.txt       (create forked version)
 
1120
    % vi foo.txt
 
1121
    % weave add foo.weave ver2 0 < foo.txt
 
1122
    added version 2
 
1123
 
 
1124
    % weave merge foo.weave 1 2 > foo.txt   (merge them)
 
1125
    % vi foo.txt                            (resolve conflicts)
 
1126
    % weave add foo.weave merged 1 2 < foo.txt     (commit merged version)     
 
1127
    
 
1128
"""
 
1129
    
 
1130
 
 
1131
 
 
1132
def main(argv):
 
1133
    import sys
 
1134
    import os
 
1135
    try:
 
1136
        import bzrlib
 
1137
    except ImportError:
 
1138
        # in case we're run directly from the subdirectory
 
1139
        sys.path.append('..')
 
1140
        import bzrlib
 
1141
    from bzrlib.weavefile import write_weave, read_weave
 
1142
    from bzrlib.progress import ProgressBar
 
1143
 
 
1144
    try:
 
1145
        import psyco
 
1146
        psyco.full()
 
1147
    except ImportError:
 
1148
        pass
 
1149
 
 
1150
    if len(argv) < 2:
 
1151
        usage()
 
1152
        return 0
 
1153
 
 
1154
    cmd = argv[1]
 
1155
 
 
1156
    def readit():
 
1157
        return read_weave(file(argv[2], 'rb'))
 
1158
    
 
1159
    if cmd == 'help':
 
1160
        usage()
 
1161
    elif cmd == 'add':
 
1162
        w = readit()
 
1163
        # at the moment, based on everything in the file
 
1164
        name = argv[3]
 
1165
        parents = map(int, argv[4:])
 
1166
        lines = sys.stdin.readlines()
 
1167
        ver = w.add(name, parents, lines)
 
1168
        write_weave(w, file(argv[2], 'wb'))
 
1169
        print 'added version %r %d' % (name, ver)
 
1170
    elif cmd == 'init':
 
1171
        fn = argv[2]
 
1172
        if os.path.exists(fn):
 
1173
            raise IOError("file exists")
 
1174
        w = Weave()
 
1175
        write_weave(w, file(fn, 'wb'))
 
1176
    elif cmd == 'get': # get one version
 
1177
        w = readit()
 
1178
        sys.stdout.writelines(w.get_iter(int(argv[3])))
 
1179
        
 
1180
    elif cmd == 'diff':
 
1181
        w = readit()
 
1182
        fn = argv[2]
 
1183
        v1, v2 = map(int, argv[3:5])
 
1184
        lines1 = w.get(v1)
 
1185
        lines2 = w.get(v2)
 
1186
        diff_gen = bzrlib.patiencediff.unified_diff(lines1, lines2,
 
1187
                                '%s version %d' % (fn, v1),
 
1188
                                '%s version %d' % (fn, v2))
 
1189
        sys.stdout.writelines(diff_gen)
 
1190
            
 
1191
    elif cmd == 'annotate':
 
1192
        w = readit()
 
1193
        # newline is added to all lines regardless; too hard to get
 
1194
        # reasonable formatting otherwise
 
1195
        lasto = None
 
1196
        for origin, text in w.annotate(int(argv[3])):
 
1197
            text = text.rstrip('\r\n')
 
1198
            if origin == lasto:
 
1199
                print '      | %s' % (text)
 
1200
            else:
 
1201
                print '%5d | %s' % (origin, text)
 
1202
                lasto = origin
 
1203
                
 
1204
    elif cmd == 'toc':
 
1205
        weave_toc(readit())
 
1206
 
 
1207
    elif cmd == 'stats':
 
1208
        weave_stats(argv[2], ProgressBar())
 
1209
        
 
1210
    elif cmd == 'check':
 
1211
        w = readit()
 
1212
        pb = ProgressBar()
 
1213
        w.check(pb)
 
1214
        pb.clear()
 
1215
        print '%d versions ok' % w.num_versions()
 
1216
 
 
1217
    elif cmd == 'inclusions':
 
1218
        w = readit()
 
1219
        print ' '.join(map(str, w.inclusions([int(argv[3])])))
 
1220
 
 
1221
    elif cmd == 'parents':
 
1222
        w = readit()
 
1223
        print ' '.join(map(str, w._parents[int(argv[3])]))
 
1224
 
 
1225
    elif cmd == 'plan-merge':
 
1226
        # replaced by 'bzr weave-plan-merge'
 
1227
        w = readit()
 
1228
        for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
 
1229
            if line:
 
1230
                print '%14s | %s' % (state, line),
 
1231
    elif cmd == 'merge':
 
1232
        # replaced by 'bzr weave-merge-text'
 
1233
        w = readit()
 
1234
        p = w.plan_merge(int(argv[3]), int(argv[4]))
 
1235
        sys.stdout.writelines(w.weave_merge(p))
 
1236
    else:
 
1237
        raise ValueError('unknown command %r' % cmd)
 
1238
    
 
1239
 
 
1240
if __name__ == '__main__':
 
1241
    import sys
 
1242
    sys.exit(main(sys.argv))