← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

  • Committer: Mark Hammond
  • Date: 2009-01-12 01:55:34 UTC
  • mto: (3995.8.2 prepare-1.12)
  • mto: This revision was merged to the branch mainline in revision 4007.
  • Revision ID: mhammond@skippinet.com.au-20090112015534-yfxg50p7mpds9j4v
Include all .html files from the tortoise doc directory.

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
 
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
 
97
99
    AbsentContentFactory,
98
100
    adapter_registry,
99
101
    ContentFactory,
100
 
    sort_groupcompress,
101
102
    VersionedFile,
102
103
    )
103
104
from bzrlib.weavefile import _read_weave_v5, write_weave_v5
130
131
 
131
132
class Weave(VersionedFile):
132
133
    """weave - versioned text file storage.
133
 
 
 
134
    
134
135
    A Weave manages versions of line-based text files, keeping track
135
136
    of the originating version for each line.
136
137
 
182
183
 
183
184
    * It doesn't seem very useful to have an active insertion
184
185
      inside an inactive insertion, but it might happen.
185
 
 
 
186
      
186
187
    * Therefore, all instructions are always"considered"; that
187
188
      is passed onto and off the stack.  An outer inactive block
188
189
      doesn't disable an inner block.
258
259
 
259
260
    def copy(self):
260
261
        """Return a deep copy of self.
261
 
 
 
262
        
262
263
        The copy can be modified without affecting the original weave."""
263
264
        other = Weave()
264
265
        other._weave = self._weave[:]
274
275
            return False
275
276
        return self._parents == other._parents \
276
277
               and self._weave == other._weave \
277
 
               and self._sha1s == other._sha1s
278
 
 
 
278
               and self._sha1s == other._sha1s 
 
279
    
279
280
    def __ne__(self, other):
280
281
        return not self.__eq__(other)
281
282
 
320
321
            new_versions = tsort.topo_sort(parents)
321
322
            new_versions.extend(set(versions).difference(set(parents)))
322
323
            versions = new_versions
323
 
        elif ordering == 'groupcompress':
324
 
            parents = self.get_parent_map(versions)
325
 
            new_versions = sort_groupcompress(parents)
326
 
            new_versions.extend(set(versions).difference(set(parents)))
327
 
            versions = new_versions
328
324
        for version in versions:
329
325
            if version in self:
330
326
                yield WeaveContentFactory(version, self)
353
349
    def insert_record_stream(self, stream):
354
350
        """Insert a record stream into this versioned file.
355
351
 
356
 
        :param stream: A stream of records to insert.
 
352
        :param stream: A stream of records to insert. 
357
353
        :return: None
358
354
        :seealso VersionedFile.get_record_stream:
359
355
        """
376
372
                    adapter_factory = adapter_registry.get(adapter_key)
377
373
                    adapter = adapter_factory(self)
378
374
                    adapters[adapter_key] = adapter
379
 
                lines = split_lines(adapter.get_bytes(record))
 
375
                lines = split_lines(adapter.get_bytes(
 
376
                    record, record.get_bytes_as(record.storage_kind)))
380
377
                try:
381
378
                    self.add_lines(record.key[0], parents, lines)
382
379
                except RevisionAlreadyPresent:
402
399
 
403
400
    def _add(self, version_id, lines, parents, sha1=None, nostore_sha=None):
404
401
        """Add a single text on top of the weave.
405
 
 
 
402
  
406
403
        Returns the index number of the newly added version.
407
404
 
408
405
        version_id
409
406
            Symbolic name for this version.
410
407
            (Typically the revision-id of the revision that added it.)
411
 
            If None, a name will be allocated based on the hash. (sha1:SHAHASH)
412
408
 
413
409
        parents
414
410
            List or set of direct parent version numbers.
415
 
 
 
411
            
416
412
        lines
417
413
            Sequence of lines to be added in the new version.
418
414
 
424
420
            sha1 = sha_strings(lines)
425
421
        if sha1 == nostore_sha:
426
422
            raise errors.ExistingContent
427
 
        if version_id is None:
428
 
            version_id = "sha1:" + sha1
429
423
        if version_id in self._name_map:
430
424
            return self._check_repeated_add(version_id, parents, lines, sha1)
431
425
 
442
436
        self._names.append(version_id)
443
437
        self._name_map[version_id] = new_version
444
438
 
445
 
 
 
439
            
446
440
        if not parents:
447
441
            # special case; adding with no parents revision; can do
448
442
            # this more quickly by just appending unconditionally.
459
453
            if sha1 == self._sha1s[pv]:
460
454
                # special case: same as the single parent
461
455
                return new_version
462
 
 
 
456
            
463
457
 
464
458
        ancestors = self._inclusions(parents)
465
459
 
514
508
                # i2; we want to insert after this region to make sure
515
509
                # we don't destroy ourselves
516
510
                i = i2 + offset
517
 
                self._weave[i:i] = ([('{', new_version)]
518
 
                                    + lines[j1:j2]
 
511
                self._weave[i:i] = ([('{', new_version)] 
 
512
                                    + lines[j1:j2] 
519
513
                                    + [('}', None)])
520
514
                offset += 2 + (j2 - j1)
521
515
        return new_version
548
542
            if not isinstance(l, basestring):
549
543
                raise ValueError("text line should be a string or unicode, not %s"
550
544
                                 % type(l))
551
 
 
 
545
        
552
546
 
553
547
 
554
548
    def _check_versions(self, indexes):
562
556
    def _compatible_parents(self, my_parents, other_parents):
563
557
        """During join check that other_parents are joinable with my_parents.
564
558
 
565
 
        Joinable is defined as 'is a subset of' - supersets may require
 
559
        Joinable is defined as 'is a subset of' - supersets may require 
566
560
        regeneration of diffs, but subsets do not.
567
561
        """
568
562
        return len(other_parents.difference(my_parents)) == 0
582
576
            version_ids = self.versions()
583
577
        version_ids = set(version_ids)
584
578
        for lineno, inserted, deletes, line in self._walk_internal(version_ids):
585
 
            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
586
583
            if line[-1] != '\n':
587
584
                yield line + '\n', inserted
588
585
            else:
590
587
 
591
588
    def _walk_internal(self, version_ids=None):
592
589
        """Helper method for weave actions."""
593
 
 
 
590
        
594
591
        istack = []
595
592
        dset = set()
596
593
 
677
674
        for i in versions:
678
675
            if not isinstance(i, int):
679
676
                raise ValueError(i)
680
 
 
 
677
            
681
678
        included = self._inclusions(versions)
682
679
 
683
680
        istack = []
692
689
 
693
690
        WFE = WeaveFormatError
694
691
 
695
 
        # wow.
 
692
        # wow. 
696
693
        #  449       0   4474.6820   2356.5590   bzrlib.weave:556(_extract)
697
694
        #  +285282   0   1676.8040   1676.8040   +<isinstance>
698
695
        # 1.6 seconds in 'isinstance'.
704
701
        # we're still spending ~1/4 of the method in isinstance though.
705
702
        # so lets hard code the acceptable string classes we expect:
706
703
        #  449       0   1202.9420    786.2930   bzrlib.weave:556(_extract)
707
 
        # +71352     0    377.5560    377.5560   +<method 'append' of 'list'
 
704
        # +71352     0    377.5560    377.5560   +<method 'append' of 'list' 
708
705
        #                                          objects>
709
706
        # yay, down to ~1/4 the initial extract time, and our inline time
710
707
        # has shrunk again, with isinstance no longer dominating.
711
708
        # tweaking the stack inclusion test to use a set gives:
712
709
        #  449       0   1122.8030    713.0080   bzrlib.weave:556(_extract)
713
 
        # +71352     0    354.9980    354.9980   +<method 'append' of 'list'
 
710
        # +71352     0    354.9980    354.9980   +<method 'append' of 'list' 
714
711
        #                                          objects>
715
712
        # - a 5% win, or possibly just noise. However with large istacks that
716
713
        # 'in' test could dominate, so I'm leaving this change in place -
717
714
        # when its fast enough to consider profiling big datasets we can review.
718
715
 
719
 
 
720
 
 
 
716
              
 
717
             
721
718
 
722
719
        for l in self._weave:
723
720
            if l.__class__ == tuple:
752
749
 
753
750
    def _maybe_lookup(self, name_or_index):
754
751
        """Convert possible symbolic name to index, or pass through indexes.
755
 
 
 
752
        
756
753
        NOT FOR PUBLIC USE.
757
754
        """
758
755
        if isinstance(name_or_index, (int, long)):
768
765
        measured_sha1 = sha_strings(result)
769
766
        if measured_sha1 != expected_sha1:
770
767
            raise errors.WeaveInvalidChecksum(
771
 
                    'file %s, revision %s, expected: %s, measured %s'
 
768
                    'file %s, revision %s, expected: %s, measured %s' 
772
769
                    % (self._weave_name, version_id,
773
770
                       expected_sha1, measured_sha1))
774
771
        return result
816
813
 
817
814
            if set(new_inc) != set(self.get_ancestry(name)):
818
815
                raise AssertionError(
819
 
                    'failed %s != %s'
 
816
                    'failed %s != %s' 
820
817
                    % (set(new_inc), set(self.get_ancestry(name))))
821
818
            inclusions[name] = new_inc
822
819
 
860
857
            parent_name = other._names[parent_idx]
861
858
            if parent_name not in self._name_map:
862
859
                # should not be possible
863
 
                raise WeaveError("missing parent {%s} of {%s} in %r"
 
860
                raise WeaveError("missing parent {%s} of {%s} in %r" 
864
861
                                 % (parent_name, other._name_map[other_idx], self))
865
862
            new_parents.append(self._name_map[parent_name])
866
863
        return new_parents
873
870
         * the same text
874
871
         * the same direct parents (by name, not index, and disregarding
875
872
           order)
876
 
 
 
873
        
877
874
        If present & correct return True;
878
 
        if not present in self return False;
 
875
        if not present in self return False; 
879
876
        if inconsistent raise error."""
880
877
        this_idx = self._name_map.get(name, -1)
881
878
        if this_idx != -1:
914
911
    """A WeaveFile represents a Weave on disk and writes on change."""
915
912
 
916
913
    WEAVE_SUFFIX = '.weave'
917
 
 
 
914
    
918
915
    def __init__(self, name, transport, filemode=None, create=False, access_mode='w', get_scope=None):
919
916
        """Create a WeaveFile.
920
 
 
 
917
        
921
918
        :param create: If not True, only open an existing knit.
922
919
        """
923
920
        super(WeaveFile, self).__init__(name, access_mode, get_scope=get_scope,
973
970
        super(WeaveFile, self).insert_record_stream(stream)
974
971
        self._save()
975
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
 
976
980
 
977
981
def _reweave(wa, wb, pb=None, msg=None):
978
982
    """Combine two weaves and return the result.
979
983
 
980
 
    This works even if a revision R has different parents in
 
984
    This works even if a revision R has different parents in 
981
985
    wa and wb.  In the resulting weave all the parents are given.
982
986
 
983
 
    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 
984
988
    of the versions in the two inputs.  More efficient approaches
985
 
    might be possible but it should only be necessary to do
986
 
    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 
987
991
    inserted.
988
992
 
989
993
    :param pb: An optional progress bar, indicating how far done we are
1023
1027
        wr._add(name, lines, [wr._lookup(i) for i in combined_parents[name]])
1024
1028
    return wr
1025
1029
 
1026
 
 
1027
1030
def _reweave_parent_graphs(wa, wb):
1028
1031
    """Return combined parent ancestry for two weaves.
1029
 
 
 
1032
    
1030
1033
    Returned as a list of (version_name, set(parent_names))"""
1031
1034
    combined = {}
1032
1035
    for weave in [wa, wb]:
1034
1037
            p = combined.setdefault(name, set())
1035
1038
            p.update(map(weave._idx_to_name, weave._parents[idx]))
1036
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))