← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

[merge] jam-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
 
176
178
        self._name_map = {}
177
179
        self._weave_name = weave_name
178
180
 
 
181
    def __repr__(self):
 
182
        return "Weave(%r)" % self._weave_name
 
183
 
179
184
 
180
185
    def copy(self):
181
186
        """Return a deep copy of self.
480
485
                yield lineno, istack[-1], dset, l
481
486
            lineno += 1
482
487
 
483
 
 
 
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)
484
494
 
485
495
    def _extract(self, versions):
486
496
        """Yield annotation of lines in included set.
545
555
    def get_iter(self, name_or_index):
546
556
        """Yield lines for the specified version."""
547
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
548
564
        for origin, lineno, line in self._extract(incls):
 
565
            if cur_sha:
 
566
                cur_sha.update(line)
549
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))
550
576
 
551
577
 
552
578
    def get_text(self, name_or_index):
561
587
    get = get_lines
562
588
 
563
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
 
564
597
    def mash_iter(self, included):
565
598
        """Return composed version of multiple included versions."""
566
599
        included = map(self.maybe_lookup, included)
586
619
    def __len__(self):
587
620
        return self.numversions()
588
621
 
589
 
 
590
622
    def check(self, progress_bar=None):
591
623
        # check no circular inclusions
592
624
        for version in range(self.numversions()):
597
629
                    raise WeaveFormatError("invalid included version %d for index %d"
598
630
                                           % (inclusions[-1], version))
599
631
 
600
 
        # try extracting all versions; this is a bit slow and parallel
601
 
        # extraction could be used
 
632
        # try extracting all versions; parallel extraction is used
602
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
 
603
666
        for version in range(nv):
604
 
            if progress_bar:
605
 
                progress_bar.update('checking text', version, nv)
606
 
            s = sha.new()
607
 
            for l in self.get_iter(version):
608
 
                s.update(l)
609
 
            hd = s.hexdigest()
 
667
            hd = sha1s[version].hexdigest()
610
668
            expected = self._sha1s[version]
611
669
            if hd != expected:
612
 
                raise WeaveError("mismatched sha1 for version %d; "
613
 
                                 "got %s, expected %s"
614
 
                                 % (version, hd, expected))
 
670
                raise errors.WeaveInvalidChecksum(
 
671
                        "mismatched sha1 for version %s: "
 
672
                        "got %s, expected %s"
 
673
                        % (self._names[version], hd, expected))
615
674
 
616
675
        # TODO: check insertions are properly nested, that there are
617
676
        # no lines outside of insertion blocks, that deletions are
618
677
        # properly paired, etc.
619
678
 
620
 
 
621
 
 
622
 
    def merge(self, merge_versions):
623
 
        """Automerge and mark conflicts between versions.
624
 
 
625
 
        This returns a sequence, each entry describing alternatives
626
 
        for a chunk of the file.  Each of the alternatives is given as
627
 
        a list of lines.
628
 
 
629
 
        If there is a chunk of the file where there's no diagreement,
630
 
        only one alternative is given.
631
 
        """
632
 
        # approach: find the included versions common to all the
633
 
        # merged versions
634
 
        raise NotImplementedError()
635
 
 
636
 
 
637
 
 
638
679
    def _delta(self, included, lines):
639
680
        """Return changes from basis to new revision.
640
681
 
709
750
        lines_a = []
710
751
        lines_b = []
711
752
        ch_a = ch_b = False
712
 
 
 
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.
713
758
        for state, line in plan:
714
759
            if state == 'unchanged' or state == 'killed-both':
715
760
                # resync and flush queued conflicts changes if any
753
798
                                 'killed-both'), \
754
799
                       state
755
800
 
756
 
                
757
 
    def join(self, other):
 
801
 
 
802
    def join(self, other, pb=None, msg=None):
 
803
        import sys, time
758
804
        """Integrate versions from other into this weave.
759
805
 
760
806
        The resulting weave contains all the history of both weaves; 
763
809
 
764
810
        It is illegal for the two weaves to contain different values 
765
811
        or different parents for any version.  See also reweave().
 
812
 
 
813
        :param other: The other weave to pull into this one
 
814
        :param pb: An optional progress bar
 
815
        :param msg: An optional message to display for progress
766
816
        """
767
817
        if other.numversions() == 0:
768
818
            return          # nothing to update, easy
770
820
        # will be ok
771
821
        # work through in index order to make sure we get all dependencies
772
822
        for other_idx, name in enumerate(other._names):
773
 
            if self._check_version_consistent(other, other_idx, name):
774
 
                continue
 
823
            self._check_version_consistent(other, other_idx, name)
 
824
 
 
825
        if pb and not msg:
 
826
            msg = 'weave join'
 
827
 
 
828
        merged = 0
 
829
        processed = 0
 
830
        time0 = time.time( )
775
831
        for other_idx, name in enumerate(other._names):
776
 
            # TODO: If all the parents of the other version are already 
 
832
            # TODO: If all the parents of the other version are already
777
833
            # present then we can avoid some work by just taking the delta
778
834
            # and adjusting the offsets.
779
835
            new_parents = self._imported_parents(other, other_idx)
 
836
            sha1 = other._sha1s[other_idx]
 
837
 
 
838
            processed += 1
 
839
 
 
840
            if name in self._name_map:
 
841
                idx = self.lookup(name)
 
842
                n1 = set(map(other.idx_to_name, other._parents[other_idx]))
 
843
                n2 = set(map(self.idx_to_name, self._parents[idx]))
 
844
                if sha1 ==  self._sha1s[idx] and n1 == n2:
 
845
                        continue
 
846
 
 
847
            if pb:
 
848
                pb.update(msg, other_idx, len(other._names))
 
849
           
 
850
            merged += 1
780
851
            lines = other.get_lines(other_idx)
781
 
            sha1 = other._sha1s[other_idx]
782
852
            self.add(name, new_parents, lines, sha1)
783
853
 
784
 
 
 
854
        mutter("merged = %d, processed = %d, file_id=%s; deltat=%d"%(
 
855
                merged,processed,self._weave_name, time.time( )-time0))
 
856
 
 
857
 
 
858
 
 
859
 
785
860
    def _imported_parents(self, other, other_idx):
786
861
        """Return list of parents in self corresponding to indexes in other."""
787
862
        new_parents = []
814
889
                                 % (name))
815
890
            self_parents = self._parents[this_idx]
816
891
            other_parents = other._parents[other_idx]
817
 
            n1 = [self._names[i] for i in self_parents]
818
 
            n2 = [other._names[i] for i in other_parents]
819
 
            n1.sort()
820
 
            n2.sort()
 
892
            n1 = set([self._names[i] for i in self_parents])
 
893
            n2 = set([other._names[i] for i in other_parents])
821
894
            if n1 != n2:
822
895
                raise WeaveParentMismatch("inconsistent parents "
823
896
                    "for version {%s}: %s vs %s" % (name, n1, n2))
826
899
        else:
827
900
            return False
828
901
 
829
 
    def reweave(self, other):
830
 
        """Reweave self with other."""
831
 
        new_weave = reweave(self, other)
 
902
    def reweave(self, other, pb=None, msg=None):
 
903
        """Reweave self with other.
 
904
 
 
905
        :param other: The other weave to merge
 
906
        :param pb: An optional progress bar, indicating how far done we are
 
907
        :param msg: An optional message for the progress
 
908
        """
 
909
        new_weave = reweave(self, other, pb=pb, msg=msg)
832
910
        for attr in self.__slots__:
833
911
            setattr(self, attr, getattr(new_weave, attr))
834
912
 
835
913
 
836
 
def reweave(wa, wb):
 
914
def reweave(wa, wb, pb=None, msg=None):
837
915
    """Combine two weaves and return the result.
838
916
 
839
917
    This works even if a revision R has different parents in 
844
922
    might be possible but it should only be necessary to do 
845
923
    this operation rarely, when a new previously ghost version is 
846
924
    inserted.
 
925
 
 
926
    :param pb: An optional progress bar, indicating how far done we are
 
927
    :param msg: An optional message for the progress
847
928
    """
848
929
    wr = Weave()
849
930
    ia = ib = 0
855
936
    mutter("combined parents: %r", combined_parents)
856
937
    order = topo_sort(combined_parents.iteritems())
857
938
    mutter("order to reweave: %r", order)
858
 
    for name in order:
 
939
 
 
940
    if pb and not msg:
 
941
        msg = 'reweave'
 
942
 
 
943
    for idx, name in enumerate(order):
 
944
        if pb:
 
945
            pb.update(msg, idx, len(order))
859
946
        if name in wa._name_map:
860
947
            lines = wa.get_lines(name)
861
948
            if name in wb._name_map:
862
 
                assert lines == wb.get_lines(name)
 
949
                lines_b = wb.get_lines(name)
 
950
                if lines != lines_b:
 
951
                    mutter('Weaves differ on content. rev_id {%s}', name)
 
952
                    mutter('weaves: %s, %s', wa._weave_name, wb._weave_name)
 
953
                    import difflib
 
954
                    lines = list(difflib.unified_diff(lines, lines_b,
 
955
                            wa._weave_name, wb._weave_name))
 
956
                    mutter('lines:\n%s', ''.join(lines))
 
957
                    raise errors.WeaveTextDiffers(name, wa, wb)
863
958
        else:
864
959
            lines = wb.get_lines(name)
865
960
        wr.add(name, combined_parents[name], lines)
1124
1219
    return ret
1125
1220
 
1126
1221
 
 
1222
def lsprofile_main(argv): 
 
1223
    from bzrlib.lsprof import profile
 
1224
    ret,stats = profile(main, argv)
 
1225
    stats.sort()
 
1226
    stats.pprint()
 
1227
    return ret
 
1228
 
 
1229
 
1127
1230
if __name__ == '__main__':
1128
1231
    import sys
1129
1232
    if '--profile' in sys.argv:
1130
1233
        args = sys.argv[:]
1131
1234
        args.remove('--profile')
1132
1235
        sys.exit(profile_main(args))
 
1236
    elif '--lsprof' in sys.argv:
 
1237
        args = sys.argv[:]
 
1238
        args.remove('--lsprof')
 
1239
        sys.exit(lsprofile_main(args))
1133
1240
    else:
1134
1241
        sys.exit(main(sys.argv))
1135
1242