← 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: 2006-01-23 02:09:39 UTC
  • mfrom: (1534.1.11 integration)
  • Revision ID: mbp@sourcefrog.net-20060123020939-567fb193328ed7a6
[merge] robert's integration

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/weave.py
67
67
# the possible relationships.
68
68
 
69
69
 
 
70
import os
70
71
import sha
71
72
from difflib import SequenceMatcher
72
73
 
73
74
from bzrlib.trace import mutter
74
 
from bzrlib.errors import WeaveError, WeaveFormatError, WeaveParentMismatch, \
75
 
        WeaveRevisionNotPresent, WeaveRevisionAlreadyPresent
 
75
from bzrlib.errors import (WeaveError, WeaveFormatError, WeaveParentMismatch,
 
76
        WeaveRevisionNotPresent, WeaveRevisionAlreadyPresent)
 
77
import bzrlib.errors as errors
76
78
from bzrlib.tsort import topo_sort
77
79
 
78
80
 
483
485
                yield lineno, istack[-1], dset, l
484
486
            lineno += 1
485
487
 
486
 
 
 
488
        if istack:
 
489
            raise WeaveFormatError("unclosed insertion blocks "
 
490
                    "at end of weave: %s" % istack)
 
491
        if dset:
 
492
            raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
 
493
                                   % dset)
487
494
 
488
495
    def _extract(self, versions):
489
496
        """Yield annotation of lines in included set.
548
555
    def get_iter(self, name_or_index):
549
556
        """Yield lines for the specified version."""
550
557
        incls = [self.maybe_lookup(name_or_index)]
 
558
        if len(incls) == 1:
 
559
            index = incls[0]
 
560
            cur_sha = sha.new()
 
561
        else:
 
562
            # We don't have sha1 sums for multiple entries
 
563
            cur_sha = None
551
564
        for origin, lineno, line in self._extract(incls):
 
565
            if cur_sha:
 
566
                cur_sha.update(line)
552
567
            yield line
 
568
        if cur_sha:
 
569
            expected_sha1 = self._sha1s[index]
 
570
            measured_sha1 = cur_sha.hexdigest() 
 
571
            if measured_sha1 != expected_sha1:
 
572
                raise errors.WeaveInvalidChecksum(
 
573
                        'file %s, revision %s, expected: %s, measured %s' 
 
574
                        % (self._weave_name, self._names[index],
 
575
                           expected_sha1, measured_sha1))
553
576
 
554
577
 
555
578
    def get_text(self, name_or_index):
564
587
    get = get_lines
565
588
 
566
589
 
 
590
    def get_sha1(self, name):
 
591
        """Get the stored sha1 sum for the given revision.
 
592
        
 
593
        :param name: The name of the version to lookup
 
594
        """
 
595
        return self._sha1s[self.lookup(name)]
 
596
 
567
597
    def mash_iter(self, included):
568
598
        """Return composed version of multiple included versions."""
569
599
        included = map(self.maybe_lookup, included)
589
619
    def __len__(self):
590
620
        return self.numversions()
591
621
 
592
 
 
593
622
    def check(self, progress_bar=None):
594
623
        # check no circular inclusions
595
624
        for version in range(self.numversions()):
600
629
                    raise WeaveFormatError("invalid included version %d for index %d"
601
630
                                           % (inclusions[-1], version))
602
631
 
603
 
        # try extracting all versions; this is a bit slow and parallel
604
 
        # extraction could be used
 
632
        # try extracting all versions; parallel extraction is used
605
633
        nv = self.numversions()
 
634
        sha1s = [sha.new() for i in range(nv)]
 
635
        texts = [[] for i in range(nv)]
 
636
        inclusions = []
 
637
        for i in range(nv):
 
638
            # For creating the ancestry, IntSet is much faster (3.7s vs 0.17s)
 
639
            # The problem is that set membership is much more expensive
 
640
            new_inc = set([i])
 
641
            for p in self._parents[i]:
 
642
                new_inc.update(inclusions[p])
 
643
 
 
644
            #assert set(new_inc) == self.inclusions([i]), 'failed %s != %s' % (new_inc, self.inclusions([i]))
 
645
            inclusions.append(new_inc)
 
646
 
 
647
        nlines = len(self._weave)
 
648
 
 
649
        update_text = 'checking weave'
 
650
        if self._weave_name:
 
651
            short_name = os.path.basename(self._weave_name)
 
652
            update_text = 'checking %s' % (short_name,)
 
653
            update_text = update_text[:25]
 
654
 
 
655
        for lineno, insert, deleteset, line in self._walk():
 
656
            if progress_bar:
 
657
                progress_bar.update(update_text, lineno, nlines)
 
658
 
 
659
            for j, j_inc in enumerate(inclusions):
 
660
                # The active inclusion must be an ancestor,
 
661
                # and no ancestors must have deleted this line,
 
662
                # because we don't support resurrection.
 
663
                if (insert in j_inc) and not (deleteset & j_inc):
 
664
                    sha1s[j].update(line)
 
665
 
606
666
        for version in range(nv):
607
 
            if progress_bar:
608
 
                progress_bar.update('checking text', version, nv)
609
 
            s = sha.new()
610
 
            for l in self.get_iter(version):
611
 
                s.update(l)
612
 
            hd = s.hexdigest()
 
667
            hd = sha1s[version].hexdigest()
613
668
            expected = self._sha1s[version]
614
669
            if hd != expected:
615
 
                raise WeaveError("mismatched sha1 for version %d; "
616
 
                                 "got %s, expected %s"
617
 
                                 % (version, hd, expected))
 
670
                raise errors.WeaveInvalidChecksum(
 
671
                        "mismatched sha1 for version %s: "
 
672
                        "got %s, expected %s"
 
673
                        % (self._names[version], hd, expected))
618
674
 
619
675
        # TODO: check insertions are properly nested, that there are
620
676
        # no lines outside of insertion blocks, that deletions are
621
677
        # properly paired, etc.
622
678
 
623
 
 
624
 
 
625
 
    def merge(self, merge_versions):
626
 
        """Automerge and mark conflicts between versions.
627
 
 
628
 
        This returns a sequence, each entry describing alternatives
629
 
        for a chunk of the file.  Each of the alternatives is given as
630
 
        a list of lines.
631
 
 
632
 
        If there is a chunk of the file where there's no diagreement,
633
 
        only one alternative is given.
634
 
        """
635
 
        # approach: find the included versions common to all the
636
 
        # merged versions
637
 
        raise NotImplementedError()
638
 
 
639
 
 
640
 
 
641
679
    def _delta(self, included, lines):
642
680
        """Return changes from basis to new revision.
643
681
 
712
750
        lines_a = []
713
751
        lines_b = []
714
752
        ch_a = ch_b = False
715
 
 
 
753
        # TODO: Return a structured form of the conflicts (e.g. 2-tuples for
 
754
        # conflicted regions), rather than just inserting the markers.
 
755
        # 
 
756
        # TODO: Show some version information (e.g. author, date) on 
 
757
        # conflicted regions.
716
758
        for state, line in plan:
717
759
            if state == 'unchanged' or state == 'killed-both':
718
760
                # resync and flush queued conflicts changes if any
756
798
                                 'killed-both'), \
757
799
                       state
758
800
 
759
 
                
 
801
 
760
802
    def join(self, other):
 
803
        import sys, time
761
804
        """Integrate versions from other into this weave.
762
805
 
763
806
        The resulting weave contains all the history of both weaves; 
773
816
        # will be ok
774
817
        # work through in index order to make sure we get all dependencies
775
818
        for other_idx, name in enumerate(other._names):
776
 
            if self._check_version_consistent(other, other_idx, name):
777
 
                continue
 
819
            self._check_version_consistent(other, other_idx, name)
 
820
 
 
821
        merged = 0
 
822
        processed = 0
 
823
        time0 = time.time( )
778
824
        for other_idx, name in enumerate(other._names):
779
 
            # TODO: If all the parents of the other version are already 
 
825
            # TODO: If all the parents of the other version are already
780
826
            # present then we can avoid some work by just taking the delta
781
827
            # and adjusting the offsets.
782
828
            new_parents = self._imported_parents(other, other_idx)
 
829
            sha1 = other._sha1s[other_idx]
 
830
 
 
831
            processed += 1
 
832
           
 
833
            if name in self._names:
 
834
                idx = self.lookup(name)
 
835
                n1 = map(other.idx_to_name, other._parents[other_idx] )
 
836
                n2 = map(self.idx_to_name, self._parents[other_idx] )
 
837
                if sha1 ==  self._sha1s[idx] and n1 == n2:
 
838
                        continue
 
839
 
 
840
            merged += 1
783
841
            lines = other.get_lines(other_idx)
784
 
            sha1 = other._sha1s[other_idx]
785
842
            self.add(name, new_parents, lines, sha1)
786
843
 
787
 
 
 
844
        mutter("merged = %d, processed = %d, file_id=%s; deltat=%d"%(
 
845
                merged,processed,self._weave_name, time.time( )-time0))
 
846
 
 
847
 
 
848
 
 
849
 
788
850
    def _imported_parents(self, other, other_idx):
789
851
        """Return list of parents in self corresponding to indexes in other."""
790
852
        new_parents = []
1127
1189
    return ret
1128
1190
 
1129
1191
 
 
1192
def lsprofile_main(argv): 
 
1193
    from bzrlib.lsprof import profile
 
1194
    ret,stats = profile(main, argv)
 
1195
    stats.sort()
 
1196
    stats.pprint()
 
1197
    return ret
 
1198
 
 
1199
 
1130
1200
if __name__ == '__main__':
1131
1201
    import sys
1132
1202
    if '--profile' in sys.argv:
1133
1203
        args = sys.argv[:]
1134
1204
        args.remove('--profile')
1135
1205
        sys.exit(profile_main(args))
 
1206
    elif '--lsprof' in sys.argv:
 
1207
        args = sys.argv[:]
 
1208
        args.remove('--lsprof')
 
1209
        sys.exit(lsprofile_main(args))
1136
1210
    else:
1137
1211
        sys.exit(main(sys.argv))
1138
1212