← 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: 2005-10-07 23:35:42 UTC
  • mfrom: (1393.1.70)
  • mto: (1185.1.51)
  • mto: This revision was merged to the branch mainline in revision 1422.
  • Revision ID: robertc@robertcollins.net-20051007233541-eb80a1c86fa1405f
merge from martins newformat

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/weave.py
74
74
import sha
75
75
from difflib import SequenceMatcher
76
76
 
77
 
 
 
77
from bzrlib.trace import mutter
78
78
 
79
79
 
80
80
class WeaveError(Exception):
398
398
        return self._parents[version]
399
399
 
400
400
 
 
401
    def parent_names(self, version):
 
402
        """Return version names for parents of a version."""
 
403
        return map(self.idx_to_name, self._parents[self.lookup(version)])
 
404
 
 
405
 
401
406
    def minimal_parents(self, version):
402
407
        """Find the minimal set of parents for the version."""
403
408
        included = self._parents[version]
774
779
        retrieved from self after this call.
775
780
 
776
781
        It is illegal for the two weaves to contain different values 
777
 
        for any version.
 
782
        or different parents for any version.  See also reweave().
778
783
        """
779
784
        if other.numversions() == 0:
780
785
            return          # nothing to update, easy
828
833
            n1.sort()
829
834
            n2.sort()
830
835
            if n1 != n2:
 
836
                # XXX: Perhaps return a specific exception for this so
 
837
                # we can retry through reweave().
831
838
                raise WeaveError("inconsistent parents for version {%s}: "
832
839
                                 "%s vs %s"
833
840
                                 % (name, n1, n2))
837
844
            return False
838
845
 
839
846
 
 
847
def reweave(wa, wb):
 
848
    """Combine two weaves and return the result.
 
849
 
 
850
    This works even if a revision R has different parents in 
 
851
    wa and wb.  In the resulting weave all the parents are given.
 
852
 
 
853
    This is done by just building up a new weave, maintaining ordering 
 
854
    of the versions in the two inputs.  More efficient approaches
 
855
    might be possible but it should only be necessary to do 
 
856
    this operation rarely, when a new previously ghost version is 
 
857
    inserted.
 
858
    """
 
859
    wr = Weave()
 
860
    ia = ib = 0
 
861
    queue_a = range(wa.numversions())
 
862
    queue_b = range(wb.numversions())
 
863
    # first determine combined parents of all versions
 
864
    # map from version name -> all parent names
 
865
    combined_parents = _reweave_parent_graphs(wa, wb)
 
866
    mutter("combined parents: %r", combined_parents)
 
867
    order = _make_reweave_order(wa._names, wb._names, combined_parents)
 
868
    mutter("order to reweave: %r", order)
 
869
    for name in order:
 
870
        if name in wa._name_map:
 
871
            lines = wa.get_lines(name)
 
872
            if name in wb._name_map:
 
873
                assert lines == wb.get_lines(name)
 
874
        else:
 
875
            lines = wb.get_lines(name)
 
876
        wr.add(name, combined_parents[name], lines)
 
877
    return wr
 
878
 
 
879
 
 
880
def _reweave_parent_graphs(wa, wb):
 
881
    """Return combined parent ancestry for two weaves.
 
882
    
 
883
    Returned as a list of (version_name, set(parent_names))"""
 
884
    combined = {}
 
885
    for weave in [wa, wb]:
 
886
        for idx, name in enumerate(weave._names):
 
887
            p = combined.setdefault(name, set())
 
888
            p.update(map(weave.idx_to_name, weave._parents[idx]))
 
889
    return combined
 
890
 
 
891
 
 
892
def _make_reweave_order(wa_order, wb_order, combined_parents):
 
893
    """Return an order to reweave versions respecting parents."""
 
894
    done = set()
 
895
    result = []
 
896
    ia = ib = 0
 
897
    next_a = next_b = None
 
898
    len_a = len(wa_order)
 
899
    len_b = len(wb_order)
 
900
    while ia < len(wa_order) or ib < len(wb_order):
 
901
        if ia < len_a:
 
902
            next_a = wa_order[ia]
 
903
            if next_a in done:
 
904
                ia += 1
 
905
                continue
 
906
            if combined_parents[next_a].issubset(done):
 
907
                ia += 1
 
908
                result.append(next_a)
 
909
                done.add(next_a)
 
910
                continue
 
911
        if ib < len_b:
 
912
            next_b = wb_order[ib]
 
913
            if next_b in done:
 
914
                ib += 1
 
915
                continue
 
916
            elif combined_parents[next_b].issubset(done):
 
917
                ib += 1
 
918
                result.append(next_b)
 
919
                done.add(next_b)
 
920
                continue
 
921
        raise WeaveError("don't know how to reweave at {%s} and {%s}"
 
922
                         % (next_a, next_b))
 
923
    return result
 
924
 
 
925
 
840
926
def weave_toc(w):
841
927
    """Show the weave's table-of-contents"""
842
928
    print '%6s %50s %10s %10s' % ('ver', 'name', 'sha1', 'parents')