← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/weave.py

  • Committer: Robert Collins
  • Date: 2006-02-15 08:11:37 UTC
  • mto: (1534.1.24 integration)
  • mto: This revision was merged to the branch mainline in revision 1554.
  • Revision ID: robertc@robertcollins.net-20060215081137-4c27377517e96dd1
Make format 4/5/6 branches share a single LockableFiles instance across wt/branch/repository.

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
 
                
760
 
    def join(self, other):
 
801
 
 
802
    def join(self, other, pb=None, msg=None):
 
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; 
766
809
 
767
810
        It is illegal for the two weaves to contain different values 
768
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
769
816
        """
770
817
        if other.numversions() == 0:
771
818
            return          # nothing to update, easy
772
819
        # two loops so that we do not change ourselves before verifying it
773
820
        # will be ok
774
821
        # work through in index order to make sure we get all dependencies
775
 
        for other_idx, name in enumerate(other._names):
776
 
            if self._check_version_consistent(other, other_idx, name):
777
 
                continue
778
 
        for other_idx, name in enumerate(other._names):
779
 
            # TODO: If all the parents of the other version are already 
 
822
        names_to_join = []
 
823
        processed = 0
 
824
        for other_idx, name in enumerate(other._names):
 
825
            self._check_version_consistent(other, other_idx, name)
 
826
            sha1 = other._sha1s[other_idx]
 
827
 
 
828
            processed += 1
 
829
 
 
830
            if name in self._name_map:
 
831
                idx = self.lookup(name)
 
832
                n1 = set(map(other.idx_to_name, other._parents[other_idx]))
 
833
                n2 = set(map(self.idx_to_name, self._parents[idx]))
 
834
                if sha1 ==  self._sha1s[idx] and n1 == n2:
 
835
                        continue
 
836
 
 
837
            names_to_join.append((other_idx, name))
 
838
 
 
839
        if pb and not msg:
 
840
            msg = 'weave join'
 
841
 
 
842
        merged = 0
 
843
        time0 = time.time( )
 
844
        for other_idx, name in names_to_join:
 
845
            # TODO: If all the parents of the other version are already
780
846
            # present then we can avoid some work by just taking the delta
781
847
            # and adjusting the offsets.
782
848
            new_parents = self._imported_parents(other, other_idx)
 
849
            sha1 = other._sha1s[other_idx]
 
850
 
 
851
            merged += 1
 
852
 
 
853
            if pb:
 
854
                pb.update(msg, merged, len(names_to_join))
 
855
           
783
856
            lines = other.get_lines(other_idx)
784
 
            sha1 = other._sha1s[other_idx]
785
857
            self.add(name, new_parents, lines, sha1)
786
858
 
787
 
 
 
859
        mutter("merged = %d, processed = %d, file_id=%s; deltat=%d"%(
 
860
                merged, processed, self._weave_name, time.time( )-time0))
 
861
 
788
862
    def _imported_parents(self, other, other_idx):
789
863
        """Return list of parents in self corresponding to indexes in other."""
790
864
        new_parents = []
817
891
                                 % (name))
818
892
            self_parents = self._parents[this_idx]
819
893
            other_parents = other._parents[other_idx]
820
 
            n1 = [self._names[i] for i in self_parents]
821
 
            n2 = [other._names[i] for i in other_parents]
822
 
            n1.sort()
823
 
            n2.sort()
 
894
            n1 = set([self._names[i] for i in self_parents])
 
895
            n2 = set([other._names[i] for i in other_parents])
824
896
            if n1 != n2:
825
897
                raise WeaveParentMismatch("inconsistent parents "
826
898
                    "for version {%s}: %s vs %s" % (name, n1, n2))
829
901
        else:
830
902
            return False
831
903
 
832
 
    def reweave(self, other):
833
 
        """Reweave self with other."""
834
 
        new_weave = reweave(self, other)
 
904
    def reweave(self, other, pb=None, msg=None):
 
905
        """Reweave self with other.
 
906
 
 
907
        :param other: The other weave to merge
 
908
        :param pb: An optional progress bar, indicating how far done we are
 
909
        :param msg: An optional message for the progress
 
910
        """
 
911
        new_weave = reweave(self, other, pb=pb, msg=msg)
835
912
        for attr in self.__slots__:
836
913
            setattr(self, attr, getattr(new_weave, attr))
837
914
 
838
915
 
839
 
def reweave(wa, wb):
 
916
def reweave(wa, wb, pb=None, msg=None):
840
917
    """Combine two weaves and return the result.
841
918
 
842
919
    This works even if a revision R has different parents in 
847
924
    might be possible but it should only be necessary to do 
848
925
    this operation rarely, when a new previously ghost version is 
849
926
    inserted.
 
927
 
 
928
    :param pb: An optional progress bar, indicating how far done we are
 
929
    :param msg: An optional message for the progress
850
930
    """
851
931
    wr = Weave()
852
932
    ia = ib = 0
858
938
    mutter("combined parents: %r", combined_parents)
859
939
    order = topo_sort(combined_parents.iteritems())
860
940
    mutter("order to reweave: %r", order)
861
 
    for name in order:
 
941
 
 
942
    if pb and not msg:
 
943
        msg = 'reweave'
 
944
 
 
945
    for idx, name in enumerate(order):
 
946
        if pb:
 
947
            pb.update(msg, idx, len(order))
862
948
        if name in wa._name_map:
863
949
            lines = wa.get_lines(name)
864
950
            if name in wb._name_map:
865
 
                assert lines == wb.get_lines(name)
 
951
                lines_b = wb.get_lines(name)
 
952
                if lines != lines_b:
 
953
                    mutter('Weaves differ on content. rev_id {%s}', name)
 
954
                    mutter('weaves: %s, %s', wa._weave_name, wb._weave_name)
 
955
                    import difflib
 
956
                    lines = list(difflib.unified_diff(lines, lines_b,
 
957
                            wa._weave_name, wb._weave_name))
 
958
                    mutter('lines:\n%s', ''.join(lines))
 
959
                    raise errors.WeaveTextDiffers(name, wa, wb)
866
960
        else:
867
961
            lines = wb.get_lines(name)
868
962
        wr.add(name, combined_parents[name], lines)
1127
1221
    return ret
1128
1222
 
1129
1223
 
 
1224
def lsprofile_main(argv): 
 
1225
    from bzrlib.lsprof import profile
 
1226
    ret,stats = profile(main, argv)
 
1227
    stats.sort()
 
1228
    stats.pprint()
 
1229
    return ret
 
1230
 
 
1231
 
1130
1232
if __name__ == '__main__':
1131
1233
    import sys
1132
1234
    if '--profile' in sys.argv:
1133
1235
        args = sys.argv[:]
1134
1236
        args.remove('--profile')
1135
1237
        sys.exit(profile_main(args))
 
1238
    elif '--lsprof' in sys.argv:
 
1239
        args = sys.argv[:]
 
1240
        args.remove('--lsprof')
 
1241
        sys.exit(lsprofile_main(args))
1136
1242
    else:
1137
1243
        sys.exit(main(sys.argv))
1138
1244