160
162
each version; the parent's parents are implied.
163
List of hex SHA-1 of each version, or None if not recorded.
165
List of hex SHA-1 of each version.
168
List of symbolic names for each version. Each should be unique.
171
For each name, the version number.
174
Descriptive name of this weave; typically the filename if known.
166
__slots__ = ['_weave', '_parents', '_sha1s']
178
__slots__ = ['_weave', '_parents', '_sha1s', '_names', '_name_map',
181
def __init__(self, weave_name=None):
170
183
self._parents = []
187
self._weave_name = weave_name
190
return "Weave(%r)" % self._weave_name
194
"""Return a deep copy of self.
196
The copy can be modified without affecting the original weave."""
198
other._weave = self._weave[:]
199
other._parents = self._parents[:]
200
other._sha1s = self._sha1s[:]
201
other._names = self._names[:]
202
other._name_map = self._name_map.copy()
203
other._weave_name = self._weave_name
174
206
def __eq__(self, other):
175
207
if not isinstance(other, Weave):
177
209
return self._parents == other._parents \
178
and self._weave == other._weave
210
and self._weave == other._weave \
211
and self._sha1s == other._sha1s
181
214
def __ne__(self, other):
182
215
return not self.__eq__(other)
217
@deprecated_method(zero_eight)
218
def idx_to_name(self, index):
219
"""Old public interface, the public interface is all names now."""
222
def _idx_to_name(self, version):
223
return self._names[version]
225
@deprecated_method(zero_eight)
226
def lookup(self, name):
227
"""Backwards compatability thunk:
229
Return name, as name is valid in the api now, and spew deprecation
234
def _lookup(self, name):
235
"""Convert symbolic version name to index."""
237
return self._name_map[name]
239
raise RevisionNotPresent(name, self._weave_name)
241
@deprecated_method(zero_eight)
242
def iter_names(self):
243
"""Deprecated convenience function, please see VersionedFile.names()."""
244
return iter(self.names())
246
@deprecated_method(zero_eight)
248
"""See Weave.versions for the current api."""
249
return self.versions()
252
"""See VersionedFile.versions."""
253
return self._names[:]
255
def has_version(self, version_id):
256
"""See VersionedFile.has_version."""
257
return self._name_map.has_key(version_id)
259
__contains__ = has_version
261
@deprecated_method(zero_eight)
262
def parent_names(self, version):
263
"""Return version names for parents of a version.
185
def add(self, parents, text):
265
See get_parents for the current api.
267
return self.get_parents(version)
269
def get_parents(self, version_id):
270
"""See VersionedFile.get_parent."""
271
return map(self._idx_to_name, self._parents[self._lookup(version_id)])
273
def _check_repeated_add(self, name, parents, text, sha1):
274
"""Check that a duplicated add is OK.
276
If it is, return the (old) index; otherwise raise an exception.
278
idx = self._lookup(name)
279
if sorted(self._parents[idx]) != sorted(parents) \
280
or sha1 != self._sha1s[idx]:
281
raise RevisionAlreadyPresent(name, self._weave_name)
284
@deprecated_method(zero_eight)
285
def add_identical(self, old_rev_id, new_rev_id, parents):
286
"""Please use Weave.clone_text now."""
287
return self.clone_text(new_rev_id, old_rev_id, parents)
289
def add_lines(self, version_id, parents, lines):
290
"""See VersionedFile.add_lines."""
291
return self._add(version_id, lines, map(self._lookup, parents))
293
@deprecated_method(zero_eight)
294
def add(self, name, parents, text, sha1=None):
295
"""See VersionedFile.add_lines for the non deprecated api."""
296
return self._add(name, text, map(self._maybe_lookup, parents), sha1)
298
def _add(self, version_id, lines, parents, sha1=None):
186
299
"""Add a single text on top of the weave.
188
301
Returns the index number of the newly added version.
304
Symbolic name for this version.
305
(Typically the revision-id of the revision that added it.)
191
308
List or set of direct parent version numbers.
194
Sequence of lines to be added in the new version."""
311
Sequence of lines to be added in the new version.
314
assert isinstance(version_id, basestring)
316
sha1 = sha_strings(lines)
317
if version_id in self._name_map:
318
return self._check_repeated_add(version_id, parents, lines, sha1)
196
320
self._check_versions(parents)
197
## self._check_lines(text)
321
## self._check_lines(lines)
198
322
new_version = len(self._parents)
206
# if we abort after here the weave will be corrupt
207
self._parents.append(frozenset(parents))
324
# if we abort after here the (in-memory) weave will be corrupt because only
325
# some fields are updated
326
self._parents.append(parents[:])
208
327
self._sha1s.append(sha1)
328
self._names.append(version_id)
329
self._name_map[version_id] = new_version
450
579
result.append((istack[-1], lineno, l))
454
raise WFE("unclosed insertion blocks at end of weave",
582
raise WeaveFormatError("unclosed insertion blocks "
583
"at end of weave: %s" % istack)
457
raise WFE("unclosed deletion blocks at end of weave",
585
raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
464
def get_iter(self, version):
589
@deprecated_method(zero_eight)
590
def get_iter(self, name_or_index):
591
"""Deprecated, please do not use. Lookups are not not needed."""
592
return self._get_iter(self._maybe_lookup(name_or_index))
594
@deprecated_method(zero_eight)
595
def maybe_lookup(self, name_or_index):
596
"""Deprecated, please do not use. Lookups are not not needed."""
597
return self._maybe_lookup(name_or_index)
599
def _maybe_lookup(self, name_or_index):
600
"""Convert possible symbolic name to index, or pass through indexes.
604
if isinstance(name_or_index, (int, long)):
607
return self._lookup(name_or_index)
609
def _get_iter(self, version_id):
465
610
"""Yield lines for the specified version."""
466
for origin, lineno, line in self._extract([version]):
611
incls = [self._maybe_lookup(version_id)]
616
# We don't have sha1 sums for multiple entries
618
for origin, lineno, line in self._extract(incls):
470
def get(self, index):
471
return list(self.get_iter(index))
474
def mash_iter(self, included):
475
"""Return composed version of multiple included versions."""
476
for origin, lineno, text in self._extract(included):
480
def dump(self, to_file):
481
from pprint import pprint
482
print >>to_file, "Weave._weave = ",
483
pprint(self._weave, to_file)
484
print >>to_file, "Weave._parents = ",
485
pprint(self._parents, to_file)
623
expected_sha1 = self._sha1s[index]
624
measured_sha1 = cur_sha.hexdigest()
625
if measured_sha1 != expected_sha1:
626
raise errors.WeaveInvalidChecksum(
627
'file %s, revision %s, expected: %s, measured %s'
628
% (self._weave_name, self._names[index],
629
expected_sha1, measured_sha1))
631
@deprecated_method(zero_eight)
632
def get(self, version_id):
633
"""Please use either Weave.get_text or Weave.get_lines as desired."""
634
return self.get_lines(version_id)
636
def get_lines(self, version_id):
637
"""See VersionedFile.get_lines()."""
638
return list(self._get_iter(version_id))
640
def get_sha1(self, name):
641
"""Get the stored sha1 sum for the given revision.
643
:param name: The name of the version to lookup
645
return self._sha1s[self._lookup(name)]
489
647
def numversions(self):
490
648
l = len(self._parents)
491
649
assert l == len(self._sha1s)
496
return self.numversions()
652
__len__ = numversions
499
654
def check(self, progress_bar=None):
655
# TODO evaluate performance hit of using string sets in this routine.
500
656
# check no circular inclusions
501
657
for version in range(self.numversions()):
502
658
inclusions = list(self._parents[version])
506
662
raise WeaveFormatError("invalid included version %d for index %d"
507
663
% (inclusions[-1], version))
509
# try extracting all versions; this is a bit slow and parallel
510
# extraction could be used
665
# try extracting all versions; parallel extraction is used
512
666
nv = self.numversions()
513
for version in range(nv):
671
# For creating the ancestry, IntSet is much faster (3.7s vs 0.17s)
672
# The problem is that set membership is much more expensive
673
name = self._idx_to_name(i)
674
sha1s[name] = sha.new()
676
new_inc = set([name])
677
for p in self._parents[i]:
678
new_inc.update(inclusions[self._idx_to_name(p)])
680
assert set(new_inc) == set(self.get_ancestry(name)), \
681
'failed %s != %s' % (set(new_inc), set(self.get_ancestry(name)))
682
inclusions[name] = new_inc
684
nlines = len(self._weave)
686
update_text = 'checking weave'
688
short_name = os.path.basename(self._weave_name)
689
update_text = 'checking %s' % (short_name,)
690
update_text = update_text[:25]
692
for lineno, insert, deleteset, line in self.walk():
515
progress_bar.update('checking text', version, nv)
517
for l in self.get_iter(version):
520
expected = self._sha1s[version]
694
progress_bar.update(update_text, lineno, nlines)
696
for name, name_inclusions in inclusions.items():
697
# The active inclusion must be an ancestor,
698
# and no ancestors must have deleted this line,
699
# because we don't support resurrection.
700
if (insert in name_inclusions) and not (deleteset & name_inclusions):
701
sha1s[name].update(line)
704
version = self._idx_to_name(i)
705
hd = sha1s[version].hexdigest()
706
expected = self._sha1s[i]
521
707
if hd != expected:
522
raise WeaveError("mismatched sha1 for version %d; "
523
"got %s, expected %s"
524
% (version, hd, expected))
708
raise errors.WeaveInvalidChecksum(
709
"mismatched sha1 for version %s: "
710
"got %s, expected %s"
711
% (version, hd, expected))
526
713
# TODO: check insertions are properly nested, that there are
527
714
# no lines outside of insertion blocks, that deletions are
528
715
# properly paired, etc.
532
def merge(self, merge_versions):
533
"""Automerge and mark conflicts between versions.
535
This returns a sequence, each entry describing alternatives
536
for a chunk of the file. Each of the alternatives is given as
539
If there is a chunk of the file where there's no diagreement,
540
only one alternative is given.
543
# approach: find the included versions common to all the
545
raise NotImplementedError()
549
def _delta(self, included, lines):
550
"""Return changes from basis to new revision.
552
The old text for comparison is the union of included revisions.
554
This is used in inserting a new text.
556
Delta is returned as a sequence of
557
(weave1, weave2, newlines).
559
This indicates that weave1:weave2 of the old weave should be
560
replaced by the sequence of lines in newlines. Note that
561
these line numbers are positions in the total weave and don't
562
correspond to the lines in any extracted version, or even the
563
extracted union of included versions.
565
If line1=line2, this is a pure insert; if newlines=[] this is a
566
pure delete. (Similar to difflib.)
571
def plan_merge(self, ver_a, ver_b):
572
"""Return pseudo-annotation indicating how the two versions merge.
574
This is computed between versions a and b and their common
577
Weave lines present in none of them are skipped entirely.
579
inc_a = self.inclusions([ver_a])
580
inc_b = self.inclusions([ver_b])
581
inc_c = inc_a & inc_b
583
for lineno, insert, deleteset, line in self._walk():
584
if deleteset & inc_c:
585
# killed in parent; can't be in either a or b
586
# not relevant to our work
587
yield 'killed-base', line
588
elif insert in inc_c:
589
# was inserted in base
590
killed_a = bool(deleteset & inc_a)
591
killed_b = bool(deleteset & inc_b)
592
if killed_a and killed_b:
593
yield 'killed-both', line
595
yield 'killed-a', line
597
yield 'killed-b', line
599
yield 'unchanged', line
600
elif insert in inc_a:
601
if deleteset & inc_a:
602
yield 'ghost-a', line
606
elif insert in inc_b:
607
if deleteset & inc_b:
608
yield 'ghost-b', line
612
# not in either revision
613
yield 'irrelevant', line
615
yield 'unchanged', '' # terminator
619
def weave_merge(self, plan):
624
for state, line in plan:
625
if state == 'unchanged' or state == 'killed-both':
626
# resync and flush queued conflicts changes if any
627
if not lines_a and not lines_b:
629
elif ch_a and not ch_b:
631
for l in lines_a: yield l
632
elif ch_b and not ch_a:
633
for l in lines_b: yield l
634
elif lines_a == lines_b:
635
for l in lines_a: yield l
638
for l in lines_a: yield l
640
for l in lines_b: yield l
647
if state == 'unchanged':
650
elif state == 'killed-a':
653
elif state == 'killed-b':
656
elif state == 'new-a':
659
elif state == 'new-b':
663
assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
674
"""Show some text information about the weave."""
675
print '%6s %40s %20s' % ('ver', 'sha1', 'parents')
676
for i in (6, 40, 20):
718
def join(self, other, pb=None, msg=None, version_ids=None):
720
"""Integrate versions from other into this weave.
722
The resulting weave contains all the history of both weaves;
723
any version you could retrieve from either self or other can be
724
retrieved from self after this call.
726
It is illegal for the two weaves to contain different values
727
or different parents for any version. See also reweave().
729
:param other: The other weave to pull into this one
730
:param pb: An optional progress bar
731
:param msg: An optional message to display for progress
733
if not other.versions():
734
return # nothing to update, easy
737
for version_id in version_ids:
738
if not self.has_version(version_id):
739
raise RevisionNotPresent(version_id, self._weave_name)
740
assert version_ids == None
742
# two loops so that we do not change ourselves before verifying it
744
# work through in index order to make sure we get all dependencies
747
for other_idx, name in enumerate(other._names):
748
self._check_version_consistent(other, other_idx, name)
749
sha1 = other._sha1s[other_idx]
753
if name in self._name_map:
754
idx = self._lookup(name)
755
n1 = set(map(other._idx_to_name, other._parents[other_idx]))
756
n2 = set(map(self._idx_to_name, self._parents[idx]))
757
if sha1 == self._sha1s[idx] and n1 == n2:
760
names_to_join.append((other_idx, name))
767
for other_idx, name in names_to_join:
768
# TODO: If all the parents of the other version are already
769
# present then we can avoid some work by just taking the delta
770
# and adjusting the offsets.
771
new_parents = self._imported_parents(other, other_idx)
772
sha1 = other._sha1s[other_idx]
777
pb.update(msg, merged, len(names_to_join))
779
lines = other.get_lines(other_idx)
780
self._add(name, lines, new_parents, sha1)
782
mutter("merged = %d, processed = %d, file_id=%s; deltat=%d"%(
783
merged, processed, self._weave_name, time.time()-time0))
785
def _imported_parents(self, other, other_idx):
786
"""Return list of parents in self corresponding to indexes in other."""
788
for parent_idx in other._parents[other_idx]:
789
parent_name = other._names[parent_idx]
790
if parent_name not in self._names:
791
# should not be possible
792
raise WeaveError("missing parent {%s} of {%s} in %r"
793
% (parent_name, other._name_map[other_idx], self))
794
new_parents.append(self._name_map[parent_name])
797
def _check_version_consistent(self, other, other_idx, name):
798
"""Check if a version in consistent in this and other.
800
To be consistent it must have:
803
* the same direct parents (by name, not index, and disregarding
806
If present & correct return True;
807
if not present in self return False;
808
if inconsistent raise error."""
809
this_idx = self._name_map.get(name, -1)
811
if self._sha1s[this_idx] != other._sha1s[other_idx]:
812
raise WeaveError("inconsistent texts for version {%s} "
813
"when joining weaves"
815
self_parents = self._parents[this_idx]
816
other_parents = other._parents[other_idx]
817
n1 = set([self._names[i] for i in self_parents])
818
n2 = set([other._names[i] for i in other_parents])
820
raise WeaveParentMismatch("inconsistent parents "
821
"for version {%s}: %s vs %s" % (name, n1, n2))
827
def reweave(self, other, pb=None, msg=None):
828
"""Reweave self with other.
830
:param other: The other weave to merge
831
:param pb: An optional progress bar, indicating how far done we are
832
:param msg: An optional message for the progress
834
new_weave = reweave(self, other, pb=pb, msg=msg)
835
for attr in self.__slots__:
836
setattr(self, attr, getattr(new_weave, attr))
839
def reweave(wa, wb, pb=None, msg=None):
840
"""Combine two weaves and return the result.
842
This works even if a revision R has different parents in
843
wa and wb. In the resulting weave all the parents are given.
845
This is done by just building up a new weave, maintaining ordering
846
of the versions in the two inputs. More efficient approaches
847
might be possible but it should only be necessary to do
848
this operation rarely, when a new previously ghost version is
851
:param pb: An optional progress bar, indicating how far done we are
852
:param msg: An optional message for the progress
856
queue_a = range(wa.numversions())
857
queue_b = range(wb.numversions())
858
# first determine combined parents of all versions
859
# map from version name -> all parent names
860
combined_parents = _reweave_parent_graphs(wa, wb)
861
mutter("combined parents: %r", combined_parents)
862
order = topo_sort(combined_parents.iteritems())
863
mutter("order to reweave: %r", order)
868
for idx, name in enumerate(order):
870
pb.update(msg, idx, len(order))
871
if name in wa._name_map:
872
lines = wa.get_lines(name)
873
if name in wb._name_map:
874
lines_b = wb.get_lines(name)
876
mutter('Weaves differ on content. rev_id {%s}', name)
877
mutter('weaves: %s, %s', wa._weave_name, wb._weave_name)
879
lines = list(difflib.unified_diff(lines, lines_b,
880
wa._weave_name, wb._weave_name))
881
mutter('lines:\n%s', ''.join(lines))
882
raise errors.WeaveTextDiffers(name, wa, wb)
884
lines = wb.get_lines(name)
885
wr._add(name, lines, [wr._lookup(i) for i in combined_parents[name]])
888
def _reweave_parent_graphs(wa, wb):
889
"""Return combined parent ancestry for two weaves.
891
Returned as a list of (version_name, set(parent_names))"""
893
for weave in [wa, wb]:
894
for idx, name in enumerate(weave._names):
895
p = combined.setdefault(name, set())
896
p.update(map(weave._idx_to_name, weave._parents[idx]))
901
"""Show the weave's table-of-contents"""
902
print '%6s %50s %10s %10s' % ('ver', 'name', 'sha1', 'parents')
903
for i in (6, 50, 10, 10):
679
906
for i in range(w.numversions()):
680
907
sha1 = w._sha1s[i]
681
print '%6d %40s %s' % (i, sha1, ' '.join(map(str, w._parents[i])))
685
def weave_stats(weave_file):
686
from bzrlib.progress import ProgressBar
909
parent_str = ' '.join(map(str, w._parents[i]))
910
print '%6d %-50.50s %10.10s %s' % (i, name, sha1, parent_str)
914
def weave_stats(weave_file, pb):
687
915
from bzrlib.weavefile import read_weave
691
917
wf = file(weave_file, 'rb')
918
w = read_weave(wf, WeaveVersionedFile)
693
919
# FIXME: doesn't work on pipes
694
920
weave_size = wf.tell()
added
removed
bzrlib/weave.py
