199
220
return self._parents == other._parents \
200
221
and self._weave == other._weave \
201
222
and self._sha1s == other._sha1s
204
224
def __ne__(self, other):
205
225
return not self.__eq__(other)
207
def __contains__(self, name):
208
return self._name_map.has_key(name)
210
def maybe_lookup(self, name_or_index):
211
"""Convert possible symbolic name to index, or pass through indexes."""
212
if isinstance(name_or_index, (int, long)):
215
return self.lookup(name_or_index)
218
def lookup(self, name):
227
def _idx_to_name(self, version):
228
return self._names[version]
230
def _lookup(self, name):
219
231
"""Convert symbolic version name to index."""
232
self.check_not_reserved_id(name)
221
234
return self._name_map[name]
223
raise WeaveRevisionNotPresent(name, self)
236
raise RevisionNotPresent(name, self._weave_name)
239
"""See VersionedFile.versions."""
226
240
return self._names[:]
228
def iter_names(self):
229
"""Yield a list of all names in this weave."""
230
return iter(self._names)
232
def idx_to_name(self, version):
233
return self._names[version]
242
def has_version(self, version_id):
243
"""See VersionedFile.has_version."""
244
return (version_id in self._name_map)
246
__contains__ = has_version
248
def get_parents(self, version_id):
249
"""See VersionedFile.get_parent."""
250
return map(self._idx_to_name, self._parents[self._lookup(version_id)])
235
252
def _check_repeated_add(self, name, parents, text, sha1):
236
253
"""Check that a duplicated add is OK.
238
255
If it is, return the (old) index; otherwise raise an exception.
240
idx = self.lookup(name)
257
idx = self._lookup(name)
241
258
if sorted(self._parents[idx]) != sorted(parents) \
242
259
or sha1 != self._sha1s[idx]:
243
raise WeaveRevisionAlreadyPresent(name, self)
260
raise RevisionAlreadyPresent(name, self._weave_name)
246
def add(self, name, parents, text, sha1=None):
263
def _add_lines(self, version_id, parents, lines, parent_texts,
264
left_matching_blocks, nostore_sha, random_id, check_content):
265
"""See VersionedFile.add_lines."""
266
idx = self._add(version_id, lines, map(self._lookup, parents),
267
nostore_sha=nostore_sha)
268
return sha_strings(lines), sum(map(len, lines)), idx
270
def _add(self, version_id, lines, parents, sha1=None, nostore_sha=None):
247
271
"""Add a single text on top of the weave.
249
273
Returns the index number of the newly added version.
252
276
Symbolic name for this version.
253
277
(Typically the revision-id of the revision that added it.)
256
280
List or set of direct parent version numbers.
259
283
Sequence of lines to be added in the new version.
261
sha -- SHA-1 of the file, if known. This is trusted to be
285
:param nostore_sha: See VersionedFile.add_lines.
264
from bzrlib.osutils import sha_strings
266
assert isinstance(name, basestring)
268
sha1 = sha_strings(text)
269
if name in self._name_map:
270
return self._check_repeated_add(name, parents, text, sha1)
272
parents = map(self.maybe_lookup, parents)
287
assert isinstance(version_id, basestring)
288
self._check_lines_not_unicode(lines)
289
self._check_lines_are_lines(lines)
291
sha1 = sha_strings(lines)
292
if sha1 == nostore_sha:
293
raise errors.ExistingContent
294
if version_id in self._name_map:
295
return self._check_repeated_add(version_id, parents, lines, sha1)
273
297
self._check_versions(parents)
274
## self._check_lines(text)
298
## self._check_lines(lines)
275
299
new_version = len(self._parents)
278
301
# if we abort after here the (in-memory) weave will be corrupt because only
279
302
# some fields are updated
303
# XXX: FIXME implement a succeed-or-fail of the rest of this routine.
304
# - Robert Collins 20060226
280
305
self._parents.append(parents[:])
281
306
self._sha1s.append(sha1)
282
self._names.append(name)
283
self._name_map[name] = new_version
307
self._names.append(version_id)
308
self._name_map[version_id] = new_version
436
435
except IndexError:
437
436
raise IndexError("invalid version number %r" % i)
440
def annotate(self, name_or_index):
441
return list(self.annotate_iter(name_or_index))
444
def annotate_iter(self, name_or_index):
445
"""Yield list of (index-id, line) pairs for the specified version.
438
def _compatible_parents(self, my_parents, other_parents):
439
"""During join check that other_parents are joinable with my_parents.
441
Joinable is defined as 'is a subset of' - supersets may require
442
regeneration of diffs, but subsets do not.
444
return len(other_parents.difference(my_parents)) == 0
446
def annotate_iter(self, version_id):
447
"""Yield list of (version-id, line) pairs for the specified version.
447
449
The index indicates when the line originated in the weave."""
448
incls = [self.maybe_lookup(name_or_index)]
450
incls = [self._lookup(version_id)]
449
451
for origin, lineno, text in self._extract(incls):
456
(lineno, insert, deletes, text)
457
for each literal line.
452
yield self._idx_to_name(origin), text
454
def iter_lines_added_or_present_in_versions(self, version_ids=None,
456
"""See VersionedFile.iter_lines_added_or_present_in_versions()."""
457
if version_ids is None:
458
version_ids = self.versions()
459
version_ids = set(version_ids)
460
for lineno, inserted, deletes, line in self._walk_internal(version_ids):
461
# if inserted not in version_ids then it was inserted before the
462
# versions we care about, but because weaves cannot represent ghosts
463
# properly, we do not filter down to that
464
# if inserted not in version_ids: continue
466
yield line + '\n', inserted
470
def _walk_internal(self, version_ids=None):
471
"""Helper method for weave actions."""
463
476
lineno = 0 # line of weave, 0-based
465
478
for l in self._weave:
466
if isinstance(l, tuple):
479
if l.__class__ == tuple:
483
istack.append(self._names[v])
487
assert self._names[v] not in dset
488
dset.add(self._names[v])
490
dset.remove(self._names[v])
479
492
raise WeaveFormatError('unexpected instruction %r' % v)
481
assert isinstance(l, basestring)
494
assert l.__class__ in (str, unicode)
483
yield lineno, istack[-1], dset, l
496
yield lineno, istack[-1], frozenset(dset), l
500
raise WeaveFormatError("unclosed insertion blocks "
501
"at end of weave: %s" % istack)
503
raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
506
def plan_merge(self, ver_a, ver_b):
507
"""Return pseudo-annotation indicating how the two versions merge.
509
This is computed between versions a and b and their common
512
Weave lines present in none of them are skipped entirely.
514
inc_a = set(self.get_ancestry([ver_a]))
515
inc_b = set(self.get_ancestry([ver_b]))
516
inc_c = inc_a & inc_b
518
for lineno, insert, deleteset, line in self._walk_internal([ver_a, ver_b]):
519
if deleteset & inc_c:
520
# killed in parent; can't be in either a or b
521
# not relevant to our work
522
yield 'killed-base', line
523
elif insert in inc_c:
524
# was inserted in base
525
killed_a = bool(deleteset & inc_a)
526
killed_b = bool(deleteset & inc_b)
527
if killed_a and killed_b:
528
yield 'killed-both', line
530
yield 'killed-a', line
532
yield 'killed-b', line
534
yield 'unchanged', line
535
elif insert in inc_a:
536
if deleteset & inc_a:
537
yield 'ghost-a', line
541
elif insert in inc_b:
542
if deleteset & inc_b:
543
yield 'ghost-b', line
547
# not in either revision
548
yield 'irrelevant', line
550
yield 'unchanged', '' # terminator
488
552
def _extract(self, versions):
489
553
"""Yield annotation of lines in included set.
548
def get_iter(self, name_or_index):
549
"""Yield lines for the specified version."""
550
incls = [self.maybe_lookup(name_or_index)]
551
for origin, lineno, line in self._extract(incls):
555
def get_text(self, name_or_index):
556
return ''.join(self.get_iter(name_or_index))
557
assert isinstance(version, int)
560
def get_lines(self, name_or_index):
561
return list(self.get_iter(name_or_index))
567
def mash_iter(self, included):
568
"""Return composed version of multiple included versions."""
569
included = map(self.maybe_lookup, included)
570
for origin, lineno, text in self._extract(included):
574
def dump(self, to_file):
575
from pprint import pprint
576
print >>to_file, "Weave._weave = ",
577
pprint(self._weave, to_file)
578
print >>to_file, "Weave._parents = ",
579
pprint(self._parents, to_file)
583
def numversions(self):
640
def _maybe_lookup(self, name_or_index):
641
"""Convert possible symbolic name to index, or pass through indexes.
645
if isinstance(name_or_index, (int, long)):
648
return self._lookup(name_or_index)
650
def get_lines(self, version_id):
651
"""See VersionedFile.get_lines()."""
652
int_index = self._maybe_lookup(version_id)
653
result = [line for (origin, lineno, line) in self._extract([int_index])]
654
expected_sha1 = self._sha1s[int_index]
655
measured_sha1 = sha_strings(result)
656
if measured_sha1 != expected_sha1:
657
raise errors.WeaveInvalidChecksum(
658
'file %s, revision %s, expected: %s, measured %s'
659
% (self._weave_name, version_id,
660
expected_sha1, measured_sha1))
663
def get_sha1(self, version_id):
664
"""See VersionedFile.get_sha1()."""
665
return self._sha1s[self._lookup(version_id)]
667
def get_sha1s(self, version_ids):
668
"""See VersionedFile.get_sha1s()."""
669
return [self._sha1s[self._lookup(v)] for v in version_ids]
671
def num_versions(self):
672
"""How many versions are in this weave?"""
584
673
l = len(self._parents)
585
674
assert l == len(self._sha1s)
590
return self.numversions()
677
__len__ = num_versions
593
679
def check(self, progress_bar=None):
594
# check no circular inclusions
595
for version in range(self.numversions()):
680
# TODO evaluate performance hit of using string sets in this routine.
681
# TODO: check no circular inclusions
682
# TODO: create a nested progress bar
683
for version in range(self.num_versions()):
596
684
inclusions = list(self._parents[version])
598
686
inclusions.sort()
600
688
raise WeaveFormatError("invalid included version %d for index %d"
601
689
% (inclusions[-1], version))
603
# try extracting all versions; this is a bit slow and parallel
604
# extraction could be used
605
nv = self.numversions()
606
for version in range(nv):
691
# try extracting all versions; parallel extraction is used
692
nv = self.num_versions()
697
# For creating the ancestry, IntSet is much faster (3.7s vs 0.17s)
698
# The problem is that set membership is much more expensive
699
name = self._idx_to_name(i)
700
sha1s[name] = sha.new()
702
new_inc = set([name])
703
for p in self._parents[i]:
704
new_inc.update(inclusions[self._idx_to_name(p)])
706
assert set(new_inc) == set(self.get_ancestry(name)), \
707
'failed %s != %s' % (set(new_inc), set(self.get_ancestry(name)))
708
inclusions[name] = new_inc
710
nlines = len(self._weave)
712
update_text = 'checking weave'
714
short_name = os.path.basename(self._weave_name)
715
update_text = 'checking %s' % (short_name,)
716
update_text = update_text[:25]
718
for lineno, insert, deleteset, line in self._walk_internal():
608
progress_bar.update('checking text', version, nv)
610
for l in self.get_iter(version):
613
expected = self._sha1s[version]
720
progress_bar.update(update_text, lineno, nlines)
722
for name, name_inclusions in inclusions.items():
723
# The active inclusion must be an ancestor,
724
# and no ancestors must have deleted this line,
725
# because we don't support resurrection.
726
if (insert in name_inclusions) and not (deleteset & name_inclusions):
727
sha1s[name].update(line)
730
version = self._idx_to_name(i)
731
hd = sha1s[version].hexdigest()
732
expected = self._sha1s[i]
614
733
if hd != expected:
615
raise WeaveError("mismatched sha1 for version %d; "
616
"got %s, expected %s"
617
% (version, hd, expected))
734
raise errors.WeaveInvalidChecksum(
735
"mismatched sha1 for version %s: "
736
"got %s, expected %s"
737
% (version, hd, expected))
619
739
# TODO: check insertions are properly nested, that there are
620
740
# no lines outside of insertion blocks, that deletions are
621
741
# properly paired, etc.
624
def _delta(self, included, lines):
625
"""Return changes from basis to new revision.
627
The old text for comparison is the union of included revisions.
629
This is used in inserting a new text.
631
Delta is returned as a sequence of
632
(weave1, weave2, newlines).
634
This indicates that weave1:weave2 of the old weave should be
635
replaced by the sequence of lines in newlines. Note that
636
these line numbers are positions in the total weave and don't
637
correspond to the lines in any extracted version, or even the
638
extracted union of included versions.
640
If line1=line2, this is a pure insert; if newlines=[] this is a
641
pure delete. (Similar to difflib.)
643
raise NotImplementedError()
646
def plan_merge(self, ver_a, ver_b):
647
"""Return pseudo-annotation indicating how the two versions merge.
649
This is computed between versions a and b and their common
652
Weave lines present in none of them are skipped entirely.
654
inc_a = self.inclusions([ver_a])
655
inc_b = self.inclusions([ver_b])
656
inc_c = inc_a & inc_b
658
for lineno, insert, deleteset, line in self._walk():
659
if deleteset & inc_c:
660
# killed in parent; can't be in either a or b
661
# not relevant to our work
662
yield 'killed-base', line
663
elif insert in inc_c:
664
# was inserted in base
665
killed_a = bool(deleteset & inc_a)
666
killed_b = bool(deleteset & inc_b)
667
if killed_a and killed_b:
668
yield 'killed-both', line
670
yield 'killed-a', line
672
yield 'killed-b', line
674
yield 'unchanged', line
675
elif insert in inc_a:
676
if deleteset & inc_a:
677
yield 'ghost-a', line
681
elif insert in inc_b:
682
if deleteset & inc_b:
683
yield 'ghost-b', line
687
# not in either revision
688
yield 'irrelevant', line
690
yield 'unchanged', '' # terminator
694
def weave_merge(self, plan):
699
for state, line in plan:
700
if state == 'unchanged' or state == 'killed-both':
701
# resync and flush queued conflicts changes if any
702
if not lines_a and not lines_b:
704
elif ch_a and not ch_b:
706
for l in lines_a: yield l
707
elif ch_b and not ch_a:
708
for l in lines_b: yield l
709
elif lines_a == lines_b:
710
for l in lines_a: yield l
713
for l in lines_a: yield l
715
for l in lines_b: yield l
722
if state == 'unchanged':
725
elif state == 'killed-a':
728
elif state == 'killed-b':
731
elif state == 'new-a':
734
elif state == 'new-b':
738
assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
743
def join(self, other):
744
"""Integrate versions from other into this weave.
746
The resulting weave contains all the history of both weaves;
747
any version you could retrieve from either self or other can be
748
retrieved from self after this call.
750
It is illegal for the two weaves to contain different values
751
or different parents for any version. See also reweave().
753
if other.numversions() == 0:
743
def _join(self, other, pb, msg, version_ids, ignore_missing):
744
"""Worker routine for join()."""
745
if not other.versions():
754
746
return # nothing to update, easy
749
# versions is never none, InterWeave checks this.
755
752
# two loops so that we do not change ourselves before verifying it
757
754
# work through in index order to make sure we get all dependencies
758
for other_idx, name in enumerate(other._names):
759
if self._check_version_consistent(other, other_idx, name):
761
for other_idx, name in enumerate(other._names):
762
# TODO: If all the parents of the other version are already
757
# get the selected versions only that are in other.versions.
758
version_ids = set(other.versions()).intersection(set(version_ids))
759
# pull in the referenced graph.
760
version_ids = other.get_ancestry(version_ids)
761
pending_graph = [(version, other.get_parents(version)) for
762
version in version_ids]
763
for name in topo_sort(pending_graph):
764
other_idx = other._name_map[name]
765
# returns True if we have it, False if we need it.
766
if not self._check_version_consistent(other, other_idx, name):
767
names_to_join.append((other_idx, name))
776
for other_idx, name in names_to_join:
777
# TODO: If all the parents of the other version are already
763
778
# present then we can avoid some work by just taking the delta
764
779
# and adjusting the offsets.
765
780
new_parents = self._imported_parents(other, other_idx)
781
sha1 = other._sha1s[other_idx]
786
pb.update(msg, merged, len(names_to_join))
766
788
lines = other.get_lines(other_idx)
767
sha1 = other._sha1s[other_idx]
768
self.add(name, new_parents, lines, sha1)
789
self._add(name, lines, new_parents, sha1)
791
mutter("merged = %d, processed = %d, file_id=%s; deltat=%d"%(
792
merged, processed, self._weave_name, time.time()-time0))
771
794
def _imported_parents(self, other, other_idx):
772
795
"""Return list of parents in self corresponding to indexes in other."""
774
797
for parent_idx in other._parents[other_idx]:
775
798
parent_name = other._names[parent_idx]
776
if parent_name not in self._names:
799
if parent_name not in self._name_map:
777
800
# should not be possible
778
801
raise WeaveError("missing parent {%s} of {%s} in %r"
779
802
% (parent_name, other._name_map[other_idx], self))
815
def reweave(self, other):
816
"""Reweave self with other."""
817
new_weave = reweave(self, other)
834
def _reweave(self, other, pb, msg):
835
"""Reweave self with other - internal helper for join().
837
:param other: The other weave to merge
838
:param pb: An optional progress bar, indicating how far done we are
839
:param msg: An optional message for the progress
841
new_weave = _reweave(self, other, pb=pb, msg=msg)
842
self._copy_weave_content(new_weave)
844
def _copy_weave_content(self, otherweave):
845
"""adsorb the content from otherweave."""
818
846
for attr in self.__slots__:
819
setattr(self, attr, getattr(new_weave, attr))
847
if attr != '_weave_name':
848
setattr(self, attr, copy(getattr(otherweave, attr)))
851
class WeaveFile(Weave):
852
"""A WeaveFile represents a Weave on disk and writes on change."""
854
WEAVE_SUFFIX = '.weave'
856
def __init__(self, name, transport, filemode=None, create=False, access_mode='w'):
857
"""Create a WeaveFile.
859
:param create: If not True, only open an existing knit.
861
super(WeaveFile, self).__init__(name, access_mode)
862
self._transport = transport
863
self._filemode = filemode
865
_read_weave_v5(self._transport.get(name + WeaveFile.WEAVE_SUFFIX), self)
866
except errors.NoSuchFile:
872
def _add_lines(self, version_id, parents, lines, parent_texts,
873
left_matching_blocks, nostore_sha, random_id, check_content):
874
"""Add a version and save the weave."""
875
self.check_not_reserved_id(version_id)
876
result = super(WeaveFile, self)._add_lines(version_id, parents, lines,
877
parent_texts, left_matching_blocks, nostore_sha, random_id,
882
def _clone_text(self, new_version_id, old_version_id, parents):
883
"""See VersionedFile.clone_text."""
884
super(WeaveFile, self)._clone_text(new_version_id, old_version_id, parents)
887
def copy_to(self, name, transport):
888
"""See VersionedFile.copy_to()."""
889
# as we are all in memory always, just serialise to the new place.
891
write_weave_v5(self, sio)
893
transport.put_file(name + WeaveFile.WEAVE_SUFFIX, sio, self._filemode)
895
def create_empty(self, name, transport, filemode=None):
896
return WeaveFile(name, transport, filemode, create=True)
899
"""Save the weave."""
900
self._check_write_ok()
902
write_weave_v5(self, sio)
904
self._transport.put_file(self._weave_name + WeaveFile.WEAVE_SUFFIX,
910
"""See VersionedFile.get_suffixes()."""
911
return [WeaveFile.WEAVE_SUFFIX]
913
def join(self, other, pb=None, msg=None, version_ids=None,
914
ignore_missing=False):
915
"""Join other into self and save."""
916
super(WeaveFile, self).join(other, pb, msg, version_ids, ignore_missing)
920
def _reweave(wa, wb, pb=None, msg=None):
823
921
"""Combine two weaves and return the result.
825
923
This works even if a revision R has different parents in
830
928
might be possible but it should only be necessary to do
831
929
this operation rarely, when a new previously ghost version is
932
:param pb: An optional progress bar, indicating how far done we are
933
:param msg: An optional message for the progress
836
queue_a = range(wa.numversions())
837
queue_b = range(wb.numversions())
937
queue_a = range(wa.num_versions())
938
queue_b = range(wb.num_versions())
838
939
# first determine combined parents of all versions
839
940
# map from version name -> all parent names
840
941
combined_parents = _reweave_parent_graphs(wa, wb)
841
942
mutter("combined parents: %r", combined_parents)
842
943
order = topo_sort(combined_parents.iteritems())
843
944
mutter("order to reweave: %r", order)
949
for idx, name in enumerate(order):
951
pb.update(msg, idx, len(order))
845
952
if name in wa._name_map:
846
953
lines = wa.get_lines(name)
847
954
if name in wb._name_map:
848
assert lines == wb.get_lines(name)
955
lines_b = wb.get_lines(name)
957
mutter('Weaves differ on content. rev_id {%s}', name)
958
mutter('weaves: %s, %s', wa._weave_name, wb._weave_name)
960
lines = list(difflib.unified_diff(lines, lines_b,
961
wa._weave_name, wb._weave_name))
962
mutter('lines:\n%s', ''.join(lines))
963
raise errors.WeaveTextDiffers(name, wa, wb)
850
965
lines = wb.get_lines(name)
851
wr.add(name, combined_parents[name], lines)
966
wr._add(name, lines, [wr._lookup(i) for i in combined_parents[name]])
855
969
def _reweave_parent_graphs(wa, wb):
856
970
"""Return combined parent ancestry for two weaves.
1055
1162
print ' '.join(map(str, w._parents[int(argv[3])]))
1057
1164
elif cmd == 'plan-merge':
1165
# replaced by 'bzr weave-plan-merge'
1059
1167
for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
1061
1169
print '%14s | %s' % (state, line),
1063
1170
elif cmd == 'merge':
1171
# replaced by 'bzr weave-merge-text'
1065
1173
p = w.plan_merge(int(argv[3]), int(argv[4]))
1066
1174
sys.stdout.writelines(w.weave_merge(p))
1068
elif cmd == 'mash-merge':
1074
v1, v2 = map(int, argv[3:5])
1076
basis = w.inclusions([v1]).intersection(w.inclusions([v2]))
1078
base_lines = list(w.mash_iter(basis))
1079
a_lines = list(w.get(v1))
1080
b_lines = list(w.get(v2))
1082
from bzrlib.merge3 import Merge3
1083
m3 = Merge3(base_lines, a_lines, b_lines)
1085
name_a = 'version %d' % v1
1086
name_b = 'version %d' % v2
1087
sys.stdout.writelines(m3.merge_lines(name_a=name_a, name_b=name_b))
1089
1176
raise ValueError('unknown command %r' % cmd)
1093
def profile_main(argv):
1094
import tempfile, hotshot, hotshot.stats
1096
prof_f = tempfile.NamedTemporaryFile()
1098
prof = hotshot.Profile(prof_f.name)
1100
ret = prof.runcall(main, argv)
1103
stats = hotshot.stats.load(prof_f.name)
1105
stats.sort_stats('cumulative')
1106
## XXX: Might like to write to stderr or the trace file instead but
1107
## print_stats seems hardcoded to stdout
1108
stats.print_stats(20)
1113
1179
if __name__ == '__main__':
1115
if '--profile' in sys.argv:
1117
args.remove('--profile')
1118
sys.exit(profile_main(args))
1120
sys.exit(main(sys.argv))
1181
sys.exit(main(sys.argv))
1184
class InterWeave(InterVersionedFile):
1185
"""Optimised code paths for weave to weave operations."""
1187
_matching_file_from_factory = staticmethod(WeaveFile)
1188
_matching_file_to_factory = staticmethod(WeaveFile)
1191
def is_compatible(source, target):
1192
"""Be compatible with weaves."""
1194
return (isinstance(source, Weave) and
1195
isinstance(target, Weave))
1196
except AttributeError:
1199
def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
1200
"""See InterVersionedFile.join."""
1201
version_ids = self._get_source_version_ids(version_ids, ignore_missing)
1202
if self.target.versions() == [] and version_ids is None:
1203
self.target._copy_weave_content(self.source)
1205
self.target._join(self.source, pb, msg, version_ids, ignore_missing)
1208
InterVersionedFile.register_optimiser(InterWeave)
added
removed
bzrlib/weave.py
