← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

  • Committer: Matt Nordhoff
  • Date: 2009-04-04 02:50:01 UTC
  • mfrom: (4253 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4256.
  • Revision ID: mnordhoff@mattnordhoff.com-20090404025001-z1403k0tatmc8l91
Merge bzr.dev, fixing conflicts.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/weave.py
14
14
#
15
15
# You should have received a copy of the GNU General Public License
16
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
 
17
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
18
18
 
19
19
# Author: Martin Pool <mbp@canonical.com>
20
20
 
61
61
# where the basis and destination are unchanged.
62
62
 
63
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 
 
64
# that includes some redundant parents (i.e. already a parent of
 
65
# something in the list.)  We should eliminate them.  This can
66
66
# be done fairly efficiently because the sequence numbers constrain
67
67
# the possible relationships.
68
68
 
99
99
    AbsentContentFactory,
100
100
    adapter_registry,
101
101
    ContentFactory,
 
102
    sort_groupcompress,
102
103
    VersionedFile,
103
104
    )
104
105
from bzrlib.weavefile import _read_weave_v5, write_weave_v5
131
132
 
132
133
class Weave(VersionedFile):
133
134
    """weave - versioned text file storage.
134
 
    
 
135
 
135
136
    A Weave manages versions of line-based text files, keeping track
136
137
    of the originating version for each line.
137
138
 
183
184
 
184
185
    * It doesn't seem very useful to have an active insertion
185
186
      inside an inactive insertion, but it might happen.
186
 
      
 
187
 
187
188
    * Therefore, all instructions are always"considered"; that
188
189
      is passed onto and off the stack.  An outer inactive block
189
190
      doesn't disable an inner block.
259
260
 
260
261
    def copy(self):
261
262
        """Return a deep copy of self.
262
 
        
 
263
 
263
264
        The copy can be modified without affecting the original weave."""
264
265
        other = Weave()
265
266
        other._weave = self._weave[:]
275
276
            return False
276
277
        return self._parents == other._parents \
277
278
               and self._weave == other._weave \
278
 
               and self._sha1s == other._sha1s 
279
 
    
 
279
               and self._sha1s == other._sha1s
 
280
 
280
281
    def __ne__(self, other):
281
282
        return not self.__eq__(other)
282
283
 
321
322
            new_versions = tsort.topo_sort(parents)
322
323
            new_versions.extend(set(versions).difference(set(parents)))
323
324
            versions = new_versions
 
325
        elif ordering == 'groupcompress':
 
326
            parents = self.get_parent_map(versions)
 
327
            new_versions = sort_groupcompress(parents)
 
328
            new_versions.extend(set(versions).difference(set(parents)))
 
329
            versions = new_versions
324
330
        for version in versions:
325
331
            if version in self:
326
332
                yield WeaveContentFactory(version, self)
349
355
    def insert_record_stream(self, stream):
350
356
        """Insert a record stream into this versioned file.
351
357
 
352
 
        :param stream: A stream of records to insert. 
 
358
        :param stream: A stream of records to insert.
353
359
        :return: None
354
360
        :seealso VersionedFile.get_record_stream:
355
361
        """
398
404
 
399
405
    def _add(self, version_id, lines, parents, sha1=None, nostore_sha=None):
400
406
        """Add a single text on top of the weave.
401
 
  
 
407
 
402
408
        Returns the index number of the newly added version.
403
409
 
404
410
        version_id
405
411
            Symbolic name for this version.
406
412
            (Typically the revision-id of the revision that added it.)
 
413
            If None, a name will be allocated based on the hash. (sha1:SHAHASH)
407
414
 
408
415
        parents
409
416
            List or set of direct parent version numbers.
410
 
            
 
417
 
411
418
        lines
412
419
            Sequence of lines to be added in the new version.
413
420
 
419
426
            sha1 = sha_strings(lines)
420
427
        if sha1 == nostore_sha:
421
428
            raise errors.ExistingContent
 
429
        if version_id is None:
 
430
            version_id = "sha1:" + sha1
422
431
        if version_id in self._name_map:
423
432
            return self._check_repeated_add(version_id, parents, lines, sha1)
424
433
 
435
444
        self._names.append(version_id)
436
445
        self._name_map[version_id] = new_version
437
446
 
438
 
            
 
447
 
439
448
        if not parents:
440
449
            # special case; adding with no parents revision; can do
441
450
            # this more quickly by just appending unconditionally.
452
461
            if sha1 == self._sha1s[pv]:
453
462
                # special case: same as the single parent
454
463
                return new_version
455
 
            
 
464
 
456
465
 
457
466
        ancestors = self._inclusions(parents)
458
467
 
507
516
                # i2; we want to insert after this region to make sure
508
517
                # we don't destroy ourselves
509
518
                i = i2 + offset
510
 
                self._weave[i:i] = ([('{', new_version)] 
511
 
                                    + lines[j1:j2] 
 
519
                self._weave[i:i] = ([('{', new_version)]
 
520
                                    + lines[j1:j2]
512
521
                                    + [('}', None)])
513
522
                offset += 2 + (j2 - j1)
514
523
        return new_version
541
550
            if not isinstance(l, basestring):
542
551
                raise ValueError("text line should be a string or unicode, not %s"
543
552
                                 % type(l))
544
 
        
 
553
 
545
554
 
546
555
 
547
556
    def _check_versions(self, indexes):
555
564
    def _compatible_parents(self, my_parents, other_parents):
556
565
        """During join check that other_parents are joinable with my_parents.
557
566
 
558
 
        Joinable is defined as 'is a subset of' - supersets may require 
 
567
        Joinable is defined as 'is a subset of' - supersets may require
559
568
        regeneration of diffs, but subsets do not.
560
569
        """
561
570
        return len(other_parents.difference(my_parents)) == 0
575
584
            version_ids = self.versions()
576
585
        version_ids = set(version_ids)
577
586
        for lineno, inserted, deletes, line in self._walk_internal(version_ids):
578
 
            # if inserted not in version_ids then it was inserted before the
579
 
            # versions we care about, but because weaves cannot represent ghosts
580
 
            # properly, we do not filter down to that
581
 
            # if inserted not in version_ids: continue
 
587
            if inserted not in version_ids: continue
582
588
            if line[-1] != '\n':
583
589
                yield line + '\n', inserted
584
590
            else:
586
592
 
587
593
    def _walk_internal(self, version_ids=None):
588
594
        """Helper method for weave actions."""
589
 
        
 
595
 
590
596
        istack = []
591
597
        dset = set()
592
598
 
673
679
        for i in versions:
674
680
            if not isinstance(i, int):
675
681
                raise ValueError(i)
676
 
            
 
682
 
677
683
        included = self._inclusions(versions)
678
684
 
679
685
        istack = []
688
694
 
689
695
        WFE = WeaveFormatError
690
696
 
691
 
        # wow. 
 
697
        # wow.
692
698
        #  449       0   4474.6820   2356.5590   bzrlib.weave:556(_extract)
693
699
        #  +285282   0   1676.8040   1676.8040   +<isinstance>
694
700
        # 1.6 seconds in 'isinstance'.
700
706
        # we're still spending ~1/4 of the method in isinstance though.
701
707
        # so lets hard code the acceptable string classes we expect:
702
708
        #  449       0   1202.9420    786.2930   bzrlib.weave:556(_extract)
703
 
        # +71352     0    377.5560    377.5560   +<method 'append' of 'list' 
 
709
        # +71352     0    377.5560    377.5560   +<method 'append' of 'list'
704
710
        #                                          objects>
705
711
        # yay, down to ~1/4 the initial extract time, and our inline time
706
712
        # has shrunk again, with isinstance no longer dominating.
707
713
        # tweaking the stack inclusion test to use a set gives:
708
714
        #  449       0   1122.8030    713.0080   bzrlib.weave:556(_extract)
709
 
        # +71352     0    354.9980    354.9980   +<method 'append' of 'list' 
 
715
        # +71352     0    354.9980    354.9980   +<method 'append' of 'list'
710
716
        #                                          objects>
711
717
        # - a 5% win, or possibly just noise. However with large istacks that
712
718
        # 'in' test could dominate, so I'm leaving this change in place -
713
719
        # when its fast enough to consider profiling big datasets we can review.
714
720
 
715
 
              
716
 
             
 
721
 
 
722
 
717
723
 
718
724
        for l in self._weave:
719
725
            if l.__class__ == tuple:
748
754
 
749
755
    def _maybe_lookup(self, name_or_index):
750
756
        """Convert possible symbolic name to index, or pass through indexes.
751
 
        
 
757
 
752
758
        NOT FOR PUBLIC USE.
753
759
        """
754
760
        if isinstance(name_or_index, (int, long)):
764
770
        measured_sha1 = sha_strings(result)
765
771
        if measured_sha1 != expected_sha1:
766
772
            raise errors.WeaveInvalidChecksum(
767
 
                    'file %s, revision %s, expected: %s, measured %s' 
 
773
                    'file %s, revision %s, expected: %s, measured %s'
768
774
                    % (self._weave_name, version_id,
769
775
                       expected_sha1, measured_sha1))
770
776
        return result
812
818
 
813
819
            if set(new_inc) != set(self.get_ancestry(name)):
814
820
                raise AssertionError(
815
 
                    'failed %s != %s' 
 
821
                    'failed %s != %s'
816
822
                    % (set(new_inc), set(self.get_ancestry(name))))
817
823
            inclusions[name] = new_inc
818
824
 
856
862
            parent_name = other._names[parent_idx]
857
863
            if parent_name not in self._name_map:
858
864
                # should not be possible
859
 
                raise WeaveError("missing parent {%s} of {%s} in %r" 
 
865
                raise WeaveError("missing parent {%s} of {%s} in %r"
860
866
                                 % (parent_name, other._name_map[other_idx], self))
861
867
            new_parents.append(self._name_map[parent_name])
862
868
        return new_parents
869
875
         * the same text
870
876
         * the same direct parents (by name, not index, and disregarding
871
877
           order)
872
 
        
 
878
 
873
879
        If present & correct return True;
874
 
        if not present in self return False; 
 
880
        if not present in self return False;
875
881
        if inconsistent raise error."""
876
882
        this_idx = self._name_map.get(name, -1)
877
883
        if this_idx != -1:
910
916
    """A WeaveFile represents a Weave on disk and writes on change."""
911
917
 
912
918
    WEAVE_SUFFIX = '.weave'
913
 
    
 
919
 
914
920
    def __init__(self, name, transport, filemode=None, create=False, access_mode='w', get_scope=None):
915
921
        """Create a WeaveFile.
916
 
        
 
922
 
917
923
        :param create: If not True, only open an existing knit.
918
924
        """
919
925
        super(WeaveFile, self).__init__(name, access_mode, get_scope=get_scope,
969
975
        super(WeaveFile, self).insert_record_stream(stream)
970
976
        self._save()
971
977
 
972
 
    @deprecated_method(one_five)
973
 
    def join(self, other, pb=None, msg=None, version_ids=None,
974
 
             ignore_missing=False):
975
 
        """Join other into self and save."""
976
 
        super(WeaveFile, self).join(other, pb, msg, version_ids, ignore_missing)
977
 
        self._save()
978
 
 
979
978
 
980
979
def _reweave(wa, wb, pb=None, msg=None):
981
980
    """Combine two weaves and return the result.
982
981
 
983
 
    This works even if a revision R has different parents in 
 
982
    This works even if a revision R has different parents in
984
983
    wa and wb.  In the resulting weave all the parents are given.
985
984
 
986
 
    This is done by just building up a new weave, maintaining ordering 
 
985
    This is done by just building up a new weave, maintaining ordering
987
986
    of the versions in the two inputs.  More efficient approaches
988
 
    might be possible but it should only be necessary to do 
989
 
    this operation rarely, when a new previously ghost version is 
 
987
    might be possible but it should only be necessary to do
 
988
    this operation rarely, when a new previously ghost version is
990
989
    inserted.
991
990
 
992
991
    :param pb: An optional progress bar, indicating how far done we are
1028
1027
 
1029
1028
def _reweave_parent_graphs(wa, wb):
1030
1029
    """Return combined parent ancestry for two weaves.
1031
 
    
 
1030
 
1032
1031
    Returned as a list of (version_name, set(parent_names))"""
1033
1032
    combined = {}
1034
1033
    for weave in [wa, wb]:
1099
1098
        Display origin of each line.
1100
1099
    weave merge WEAVEFILE VERSION1 VERSION2 > OUT
1101
1100
        Auto-merge two versions and display conflicts.
1102
 
    weave diff WEAVEFILE VERSION1 VERSION2 
 
1101
    weave diff WEAVEFILE VERSION1 VERSION2
1103
1102
        Show differences between two versions.
1104
1103
 
1105
1104
example:
1122
1121
 
1123
1122
    % weave merge foo.weave 1 2 > foo.txt   (merge them)
1124
1123
    % vi foo.txt                            (resolve conflicts)
1125
 
    % weave add foo.weave merged 1 2 < foo.txt     (commit merged version)     
1126
 
    
 
1124
    % weave add foo.weave merged 1 2 < foo.txt     (commit merged version)
 
1125
 
1127
1126
"""
1128
 
    
 
1127
 
1129
1128
 
1130
1129
 
1131
1130
def main(argv):
1154
1153
 
1155
1154
    def readit():
1156
1155
        return read_weave(file(argv[2], 'rb'))
1157
 
    
 
1156
 
1158
1157
    if cmd == 'help':
1159
1158
        usage()
1160
1159
    elif cmd == 'add':
1175
1174
    elif cmd == 'get': # get one version
1176
1175
        w = readit()
1177
1176
        sys.stdout.writelines(w.get_iter(int(argv[3])))
1178
 
        
 
1177
 
1179
1178
    elif cmd == 'diff':
1180
1179
        w = readit()
1181
1180
        fn = argv[2]
1186
1185
                                '%s version %d' % (fn, v1),
1187
1186
                                '%s version %d' % (fn, v2))
1188
1187
        sys.stdout.writelines(diff_gen)
1189
 
            
 
1188
 
1190
1189
    elif cmd == 'annotate':
1191
1190
        w = readit()
1192
1191
        # newline is added to all lines regardless; too hard to get
1199
1198
            else:
1200
1199
                print '%5d | %s' % (origin, text)
1201
1200
                lasto = origin
1202
 
                
 
1201
 
1203
1202
    elif cmd == 'toc':
1204
1203
        weave_toc(readit())
1205
1204
 
1206
1205
    elif cmd == 'stats':
1207
1206
        weave_stats(argv[2], ProgressBar())
1208
 
        
 
1207
 
1209
1208
    elif cmd == 'check':
1210
1209
        w = readit()
1211
1210
        pb = ProgressBar()
1234
1233
        sys.stdout.writelines(w.weave_merge(p))
1235
1234
    else:
1236
1235
        raise ValueError('unknown command %r' % cmd)
1237
 
    
 
1236
 
1238
1237
 
1239
1238
if __name__ == '__main__':
1240
1239
    import sys