« back to all changes in this revision
Viewing changes to bzrlib/weave.py
- browse files at revision 1422
- compare with another revision
- compare with revision 334
- download diff
- download tarball
- view history from revision 1422
- Committer: Robert Collins
- Date: 2005-10-08 00:39:04 UTC
- mfrom: (1185.1.52)
- Revision ID: robertc@robertcollins.net-20051008003904-aaffaea2778efe3e
merge in martins reweave, integrated to fetch, and a bugfix for commit and upgrade with executable files
added
removed
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):
83
83
84
84
class WeaveFormatError(WeaveError):
85
85
"""Weave invariant violated"""
86
87
88
class WeaveParentMismatch(WeaveError):
89
"""Parents are mismatched between two revisions."""
86
90
87
91
88
92
class Weave(object):
398
402
return self._parents[version]
399
403
400
404
405
def parent_names(self, version):
406
"""Return version names for parents of a version."""
407
return map(self.idx_to_name, self._parents[self.lookup(version)])
408
409
401
410
def minimal_parents(self, version):
402
411
"""Find the minimal set of parents for the version."""
403
412
included = self._parents[version]
774
783
retrieved from self after this call.
775
784
776
785
It is illegal for the two weaves to contain different values
777
for any version.
786
or different parents for any version. See also reweave().
778
787
"""
779
788
if other.numversions() == 0:
780
789
return # nothing to update, easy
790
# two loops so that we do not change ourselves before verifying it
791
# will be ok
781
792
# work through in index order to make sure we get all dependencies
782
793
for other_idx, name in enumerate(other._names):
794
if self._check_version_consistent(other, other_idx, name):
795
continue
796
for other_idx, name in enumerate(other._names):
783
797
# TODO: If all the parents of the other version are already
784
798
# present then we can avoid some work by just taking the delta
785
799
# and adjusting the offsets.
786
if self._check_version_consistent(other, other_idx, name):
787
continue
788
800
new_parents = self._imported_parents(other, other_idx)
789
801
lines = other.get_lines(other_idx)
790
802
sha1 = other._sha1s[other_idx]
828
840
n1.sort()
829
841
n2.sort()
830
842
if n1 != n2:
831
raise WeaveError("inconsistent parents for version {%s}: "
832
"%s vs %s"
833
% (name, n1, n2))
843
raise WeaveParentMismatch("inconsistent parents "
844
"for version {%s}: %s vs %s" % (name, n1, n2))
834
845
else:
835
846
return True # ok!
836
847
else:
837
848
return False
838
849
850
def reweave(self, other):
851
"""Reweave self with other."""
852
new_weave = reweave(self, other)
853
for attr in self.__slots__:
854
setattr(self, attr, getattr(new_weave, attr))
855
856
857
def reweave(wa, wb):
858
"""Combine two weaves and return the result.
859
860
This works even if a revision R has different parents in
861
wa and wb. In the resulting weave all the parents are given.
862
863
This is done by just building up a new weave, maintaining ordering
864
of the versions in the two inputs. More efficient approaches
865
might be possible but it should only be necessary to do
866
this operation rarely, when a new previously ghost version is
867
inserted.
868
"""
869
wr = Weave()
870
ia = ib = 0
871
queue_a = range(wa.numversions())
872
queue_b = range(wb.numversions())
873
# first determine combined parents of all versions
874
# map from version name -> all parent names
875
combined_parents = _reweave_parent_graphs(wa, wb)
876
mutter("combined parents: %r", combined_parents)
877
order = _make_reweave_order(wa._names, wb._names, combined_parents)
878
mutter("order to reweave: %r", order)
879
for name in order:
880
if name in wa._name_map:
881
lines = wa.get_lines(name)
882
if name in wb._name_map:
883
assert lines == wb.get_lines(name)
884
else:
885
lines = wb.get_lines(name)
886
wr.add(name, combined_parents[name], lines)
887
return wr
888
889
890
def _reweave_parent_graphs(wa, wb):
891
"""Return combined parent ancestry for two weaves.
892
893
Returned as a list of (version_name, set(parent_names))"""
894
combined = {}
895
for weave in [wa, wb]:
896
for idx, name in enumerate(weave._names):
897
p = combined.setdefault(name, set())
898
p.update(map(weave.idx_to_name, weave._parents[idx]))
899
return combined
900
901
902
def _make_reweave_order(wa_order, wb_order, combined_parents):
903
"""Return an order to reweave versions respecting parents."""
904
done = set()
905
result = []
906
ia = ib = 0
907
next_a = next_b = None
908
len_a = len(wa_order)
909
len_b = len(wb_order)
910
while ia < len(wa_order) or ib < len(wb_order):
911
if ia < len_a:
912
next_a = wa_order[ia]
913
if next_a in done:
914
ia += 1
915
continue
916
if combined_parents[next_a].issubset(done):
917
ia += 1
918
result.append(next_a)
919
done.add(next_a)
920
continue
921
if ib < len_b:
922
next_b = wb_order[ib]
923
if next_b in done:
924
ib += 1
925
continue
926
elif combined_parents[next_b].issubset(done):
927
ib += 1
928
result.append(next_b)
929
done.add(next_b)
930
continue
931
raise WeaveError("don't know how to reweave at {%s} and {%s}"
932
% (next_a, next_b))
933
return result
934
839
935
840
936
def weave_toc(w):
841
937
"""Show the weave's table-of-contents"""
Loggerhead is a web-based interface for Breezy
Version: 2.0.1