57
61
# where the basis and destination are unchanged.
59
63
# FIXME: Sometimes we will be given a parents list for a revision
60
# that includes some redundant parents (i.e. already a parent of
61
# something in the list.) We should eliminate them. This can
64
# that includes some redundant parents (i.e. already a parent of
65
# something in the list.) We should eliminate them. This can
62
66
# be done fairly efficiently because the sequence numbers constrain
63
67
# the possible relationships.
65
# FIXME: the conflict markers should be *7* characters
68
from io import BytesIO
72
from ..lazy_import import lazy_import
73
lazy_import(globals(), """
74
from breezy import tsort
80
from ..errors import (
81
RevisionAlreadyPresent,
84
from ..osutils import dirname, sha, sha_strings, split_lines
85
from ..revision import NULL_REVISION
86
from ..trace import mutter
87
from .versionedfile import (
93
UnavailableRepresentation,
96
from .weavefile import _read_weave_v5, write_weave_v5
99
class WeaveError(errors.BzrError):
101
_fmt = "Error in processing weave: %(msg)s"
103
def __init__(self, msg=None):
104
errors.BzrError.__init__(self)
108
class WeaveRevisionAlreadyPresent(WeaveError):
110
_fmt = "Revision {%(revision_id)s} already present in %(weave)s"
112
def __init__(self, revision_id, weave):
114
WeaveError.__init__(self)
115
self.revision_id = revision_id
119
class WeaveRevisionNotPresent(WeaveError):
121
_fmt = "Revision {%(revision_id)s} not present in %(weave)s"
123
def __init__(self, revision_id, weave):
124
WeaveError.__init__(self)
125
self.revision_id = revision_id
129
class WeaveFormatError(WeaveError):
131
_fmt = "Weave invariant violated: %(what)s"
133
def __init__(self, what):
134
WeaveError.__init__(self)
138
class WeaveParentMismatch(WeaveError):
140
_fmt = "Parents are mismatched between two revisions. %(msg)s"
143
class WeaveInvalidChecksum(WeaveError):
145
_fmt = "Text did not match its checksum: %(msg)s"
148
class WeaveTextDiffers(WeaveError):
150
_fmt = ("Weaves differ on text content. Revision:"
151
" {%(revision_id)s}, %(weave_a)s, %(weave_b)s")
153
def __init__(self, revision_id, weave_a, weave_b):
154
WeaveError.__init__(self)
155
self.revision_id = revision_id
156
self.weave_a = weave_a
157
self.weave_b = weave_b
160
class WeaveContentFactory(ContentFactory):
161
"""Content factory for streaming from weaves.
163
:seealso ContentFactory:
166
def __init__(self, version, weave):
167
"""Create a WeaveContentFactory for version from weave."""
168
ContentFactory.__init__(self)
169
self.sha1 = weave.get_sha1s([version])[version]
170
self.key = (version,)
171
parents = weave.get_parent_map([version])[version]
172
self.parents = tuple((parent,) for parent in parents)
173
self.storage_kind = 'fulltext'
176
def get_bytes_as(self, storage_kind):
177
if storage_kind == 'fulltext':
178
return self._weave.get_text(self.key[-1])
179
elif storage_kind in ('chunked', 'lines'):
180
return self._weave.get_lines(self.key[-1])
182
raise UnavailableRepresentation(self.key, storage_kind, 'fulltext')
184
def iter_bytes_as(self, storage_kind):
185
if storage_kind in ('chunked', 'lines'):
186
return iter(self._weave.get_lines(self.key[-1]))
188
raise UnavailableRepresentation(self.key, storage_kind, 'fulltext')
191
class Weave(VersionedFile):
71
from difflib import SequenceMatcher
73
from bzrlib.trace import mutter
74
from bzrlib.errors import WeaveError, WeaveFormatError, WeaveParentMismatch, \
75
WeaveRevisionNotPresent, WeaveRevisionAlreadyPresent
76
from bzrlib.tsort import topo_sort
192
80
"""weave - versioned text file storage.
194
82
A Weave manages versions of line-based text files, keeping track
195
83
of the originating version for each line.
334
197
if not isinstance(other, Weave):
336
199
return self._parents == other._parents \
337
and self._weave == other._weave \
338
and self._sha1s == other._sha1s
200
and self._weave == other._weave \
201
and self._sha1s == other._sha1s
340
204
def __ne__(self, other):
341
205
return not self.__eq__(other)
343
def _idx_to_name(self, version):
344
return self._names[version]
346
def _lookup(self, name):
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):
347
219
"""Convert symbolic version name to index."""
348
if not self._allow_reserved:
349
self.check_not_reserved_id(name)
351
221
return self._name_map[name]
353
raise RevisionNotPresent(name, self._weave_name)
223
raise WeaveRevisionNotPresent(name, self)
356
"""See VersionedFile.versions."""
357
226
return self._names[:]
359
def has_version(self, version_id):
360
"""See VersionedFile.has_version."""
361
return (version_id in self._name_map)
363
__contains__ = has_version
365
def get_record_stream(self, versions, ordering, include_delta_closure):
366
"""Get a stream of records for versions.
368
:param versions: The versions to include. Each version is a tuple
370
:param ordering: Either 'unordered' or 'topological'. A topologically
371
sorted stream has compression parents strictly before their
373
:param include_delta_closure: If True then the closure across any
374
compression parents will be included (in the opaque data).
375
:return: An iterator of ContentFactory objects, each of which is only
376
valid until the iterator is advanced.
378
versions = [version[-1] for version in versions]
379
if ordering == 'topological':
380
parents = self.get_parent_map(versions)
381
new_versions = tsort.topo_sort(parents)
382
new_versions.extend(set(versions).difference(set(parents)))
383
versions = new_versions
384
elif ordering == 'groupcompress':
385
parents = self.get_parent_map(versions)
386
new_versions = sort_groupcompress(parents)
387
new_versions.extend(set(versions).difference(set(parents)))
388
versions = new_versions
389
for version in versions:
391
yield WeaveContentFactory(version, self)
393
yield AbsentContentFactory((version,))
395
def get_parent_map(self, version_ids):
396
"""See VersionedFile.get_parent_map."""
398
for version_id in version_ids:
399
if version_id == NULL_REVISION:
404
map(self._idx_to_name,
405
self._parents[self._lookup(version_id)]))
406
except RevisionNotPresent:
408
result[version_id] = parents
411
def get_parents_with_ghosts(self, version_id):
412
raise NotImplementedError(self.get_parents_with_ghosts)
414
def insert_record_stream(self, stream):
415
"""Insert a record stream into this versioned file.
417
:param stream: A stream of records to insert.
419
:seealso VersionedFile.get_record_stream:
422
for record in stream:
423
# Raise an error when a record is missing.
424
if record.storage_kind == 'absent':
425
raise RevisionNotPresent([record.key[0]], self)
426
# adapt to non-tuple interface
427
parents = [parent[0] for parent in record.parents]
428
if record.storage_kind in ('fulltext', 'chunked', 'lines'):
430
record.key[0], parents,
431
record.get_bytes_as('lines'))
433
adapter_key = record.storage_kind, 'lines'
435
adapter = adapters[adapter_key]
437
adapter_factory = adapter_registry.get(adapter_key)
438
adapter = adapter_factory(self)
439
adapters[adapter_key] = adapter
440
lines = adapter.get_bytes(record, 'lines')
442
self.add_lines(record.key[0], parents, lines)
443
except RevisionAlreadyPresent:
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]
446
235
def _check_repeated_add(self, name, parents, text, sha1):
447
236
"""Check that a duplicated add is OK.
449
238
If it is, return the (old) index; otherwise raise an exception.
451
idx = self._lookup(name)
240
idx = self.lookup(name)
452
241
if sorted(self._parents[idx]) != sorted(parents) \
453
or sha1 != self._sha1s[idx]:
454
raise RevisionAlreadyPresent(name, self._weave_name)
242
or sha1 != self._sha1s[idx]:
243
raise WeaveRevisionAlreadyPresent(name, self)
457
def _add_lines(self, version_id, parents, lines, parent_texts,
458
left_matching_blocks, nostore_sha, random_id,
460
"""See VersionedFile.add_lines."""
461
idx = self._add(version_id, lines, list(map(self._lookup, parents)),
462
nostore_sha=nostore_sha)
463
return sha_strings(lines), sum(map(len, lines)), idx
465
def _add(self, version_id, lines, parents, sha1=None, nostore_sha=None):
246
def add(self, name, parents, text, sha1=None):
466
247
"""Add a single text on top of the weave.
468
249
Returns the index number of the newly added version.
471
252
Symbolic name for this version.
472
253
(Typically the revision-id of the revision that added it.)
473
If None, a name will be allocated based on the hash. (sha1:SHAHASH)
476
256
List or set of direct parent version numbers.
479
259
Sequence of lines to be added in the new version.
481
:param nostore_sha: See VersionedFile.add_lines.
261
sha -- SHA-1 of the file, if known. This is trusted to be
483
self._check_lines_not_unicode(lines)
484
self._check_lines_are_lines(lines)
486
sha1 = sha_strings(lines)
487
if sha1 == nostore_sha:
488
raise ExistingContent
489
if version_id is None:
490
version_id = b"sha1:" + sha1
491
if version_id in self._name_map:
492
return self._check_repeated_add(version_id, parents, lines, sha1)
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)
494
273
self._check_versions(parents)
274
## self._check_lines(text)
495
275
new_version = len(self._parents)
497
# if we abort after here the (in-memory) weave will be corrupt because
498
# only some fields are updated
499
# XXX: FIXME implement a succeed-or-fail of the rest of this routine.
500
# - Robert Collins 20060226
278
# if we abort after here the (in-memory) weave will be corrupt because only
279
# some fields are updated
501
280
self._parents.append(parents[:])
502
281
self._sha1s.append(sha1)
503
self._names.append(version_id)
504
self._name_map[version_id] = new_version
282
self._names.append(name)
283
self._name_map[name] = new_version
507
287
# special case; adding with no parents revision; can do
508
288
# this more quickly by just appending unconditionally.
509
289
# even more specially, if we're adding an empty text we
510
290
# need do nothing at all.
512
self._weave.append((b'{', new_version))
513
self._weave.extend(lines)
514
self._weave.append((b'}', None))
292
self._weave.append(('{', new_version))
293
self._weave.extend(text)
294
self._weave.append(('}', None))
515
296
return new_version
517
298
if len(parents) == 1:
605
436
except IndexError:
606
437
raise IndexError("invalid version number %r" % i)
608
def _compatible_parents(self, my_parents, other_parents):
609
"""During join check that other_parents are joinable with my_parents.
611
Joinable is defined as 'is a subset of' - supersets may require
612
regeneration of diffs, but subsets do not.
614
return len(other_parents.difference(my_parents)) == 0
616
def annotate(self, version_id):
617
"""Return a list of (version-id, line) tuples for version_id.
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.
619
447
The index indicates when the line originated in the weave."""
620
incls = [self._lookup(version_id)]
621
return [(self._idx_to_name(origin), text) for origin, lineno, text in
622
self._extract(incls)]
624
def iter_lines_added_or_present_in_versions(self, version_ids=None,
626
"""See VersionedFile.iter_lines_added_or_present_in_versions()."""
627
if version_ids is None:
628
version_ids = self.versions()
629
version_ids = set(version_ids)
630
for lineno, inserted, deletes, line in self._walk_internal(
632
if inserted not in version_ids:
634
if not line.endswith(b'\n'):
635
yield line + b'\n', inserted
639
def _walk_internal(self, version_ids=None):
640
"""Helper method for weave actions."""
448
incls = [self.maybe_lookup(name_or_index)]
449
for origin, lineno, text in self._extract(incls):
456
(lineno, insert, deletes, text)
457
for each literal line.
645
463
lineno = 0 # line of weave, 0-based
647
465
for l in self._weave:
648
if l.__class__ == tuple:
466
if isinstance(l, tuple):
651
istack.append(self._names[v])
655
dset.add(self._names[v])
657
dset.remove(self._names[v])
659
479
raise WeaveFormatError('unexpected instruction %r' % v)
661
yield lineno, istack[-1], frozenset(dset), l
481
assert isinstance(l, basestring)
483
yield lineno, istack[-1], dset, l
488
def _extract(self, versions):
489
"""Yield annotation of lines in included set.
491
Yields a sequence of tuples (origin, lineno, text), where
492
origin is the origin version, lineno the index in the weave,
493
and text the text of the line.
495
The set typically but not necessarily corresponds to a version.
498
if not isinstance(i, int):
501
included = self.inclusions(versions)
506
lineno = 0 # line of weave, 0-based
512
WFE = WeaveFormatError
514
for l in self._weave:
515
if isinstance(l, tuple):
519
assert v not in istack
533
assert isinstance(l, basestring)
535
isactive = (not dset) and istack and (istack[-1] in included)
537
result.append((istack[-1], lineno, l))
665
540
raise WeaveFormatError("unclosed insertion blocks "
666
"at end of weave: %s" % istack)
541
"at end of weave: %s" % istack)
668
raise WeaveFormatError(
669
"unclosed deletion blocks at end of weave: %s" % dset)
543
raise WeaveFormatError("unclosed deletion blocks at end of weave: %s"
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):
584
l = len(self._parents)
585
assert l == len(self._sha1s)
590
return self.numversions()
593
def check(self, progress_bar=None):
594
# check no circular inclusions
595
for version in range(self.numversions()):
596
inclusions = list(self._parents[version])
599
if inclusions[-1] >= version:
600
raise WeaveFormatError("invalid included version %d for index %d"
601
% (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):
608
progress_bar.update('checking text', version, nv)
610
for l in self.get_iter(version):
613
expected = self._sha1s[version]
615
raise WeaveError("mismatched sha1 for version %d; "
616
"got %s, expected %s"
617
% (version, hd, expected))
619
# TODO: check insertions are properly nested, that there are
620
# no lines outside of insertion blocks, that deletions are
621
# 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()
671
646
def plan_merge(self, ver_a, ver_b):
672
647
"""Return pseudo-annotation indicating how the two versions merge.
713
687
# not in either revision
714
688
yield 'irrelevant', line
716
def _extract(self, versions):
717
"""Yield annotation of lines in included set.
719
Yields a sequence of tuples (origin, lineno, text), where
720
origin is the origin version, lineno the index in the weave,
721
and text the text of the line.
723
The set typically but not necessarily corresponds to a version.
726
if not isinstance(i, int):
729
included = self._inclusions(versions)
735
lineno = 0 # line of weave, 0-based
742
# 449 0 4474.6820 2356.5590 breezy.weave:556(_extract)
743
# +285282 0 1676.8040 1676.8040 +<isinstance>
744
# 1.6 seconds in 'isinstance'.
745
# changing the first isinstance:
746
# 449 0 2814.2660 1577.1760 breezy.weave:556(_extract)
747
# +140414 0 762.8050 762.8050 +<isinstance>
748
# note that the inline time actually dropped (less function calls)
749
# and total processing time was halved.
750
# we're still spending ~1/4 of the method in isinstance though.
751
# so lets hard code the acceptable string classes we expect:
752
# 449 0 1202.9420 786.2930 breezy.weave:556(_extract)
753
# +71352 0 377.5560 377.5560 +<method 'append' of 'list'
755
# yay, down to ~1/4 the initial extract time, and our inline time
756
# has shrunk again, with isinstance no longer dominating.
757
# tweaking the stack inclusion test to use a set gives:
758
# 449 0 1122.8030 713.0080 breezy.weave:556(_extract)
759
# +71352 0 354.9980 354.9980 +<method 'append' of 'list'
761
# - a 5% win, or possibly just noise. However with large istacks that
762
# 'in' test could dominate, so I'm leaving this change in place - when
763
# its fast enough to consider profiling big datasets we can review.
765
for l in self._weave:
766
if l.__class__ == tuple:
773
iset.remove(istack.pop())
690
yield 'unchanged', '' # terminator
694
def weave_merge(self, plan):
698
# TODO: Return a structured form of the conflicts (e.g. 2-tuples for
699
# conflicted regions), rather than just inserting the markers.
701
# TODO: Show some version information (e.g. author, date) on
702
# conflicted regions.
703
for state, line in plan:
704
if state == 'unchanged' or state == 'killed-both':
705
# resync and flush queued conflicts changes if any
706
if not lines_a and not lines_b:
708
elif ch_a and not ch_b:
710
for l in lines_a: yield l
711
elif ch_b and not ch_a:
712
for l in lines_b: yield l
713
elif lines_a == lines_b:
714
for l in lines_a: yield l
781
raise AssertionError()
717
for l in lines_a: yield l
719
for l in lines_b: yield l
726
if state == 'unchanged':
729
elif state == 'killed-a':
732
elif state == 'killed-b':
735
elif state == 'new-a':
738
elif state == 'new-b':
784
isactive = (not dset) and istack and (
785
istack[-1] in included)
787
result.append((istack[-1], lineno, l))
790
raise WeaveFormatError("unclosed insertion blocks "
791
"at end of weave: %s" % istack)
793
raise WeaveFormatError(
794
"unclosed deletion blocks at end of weave: %s" % dset)
797
def _maybe_lookup(self, name_or_index):
798
"""Convert possible symbolic name to index, or pass through indexes.
742
assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
747
def join(self, other):
749
"""Integrate versions from other into this weave.
751
The resulting weave contains all the history of both weaves;
752
any version you could retrieve from either self or other can be
753
retrieved from self after this call.
755
It is illegal for the two weaves to contain different values
756
or different parents for any version. See also reweave().
802
# GZ 2017-04-01: This used to check for long as well, but I don't think
803
# there are python implementations with sys.maxsize > sys.maxint
804
if isinstance(name_or_index, int):
807
return self._lookup(name_or_index)
809
def get_lines(self, version_id):
810
"""See VersionedFile.get_lines()."""
811
int_index = self._maybe_lookup(version_id)
812
result = [line for (origin, lineno, line)
813
in self._extract([int_index])]
814
expected_sha1 = self._sha1s[int_index]
815
measured_sha1 = sha_strings(result)
816
if measured_sha1 != expected_sha1:
817
raise WeaveInvalidChecksum(
818
'file %s, revision %s, expected: %s, measured %s'
819
% (self._weave_name, version_id,
820
expected_sha1, measured_sha1))
823
def get_sha1s(self, version_ids):
824
"""See VersionedFile.get_sha1s()."""
826
for v in version_ids:
827
result[v] = self._sha1s[self._lookup(v)]
830
def num_versions(self):
831
"""How many versions are in this weave?"""
832
return len(self._parents)
834
__len__ = num_versions
836
def check(self, progress_bar=None):
837
# TODO evaluate performance hit of using string sets in this routine.
838
# TODO: check no circular inclusions
839
# TODO: create a nested progress bar
840
for version in range(self.num_versions()):
841
inclusions = list(self._parents[version])
844
if inclusions[-1] >= version:
845
raise WeaveFormatError(
846
"invalid included version %d for index %d"
847
% (inclusions[-1], version))
849
# try extracting all versions; parallel extraction is used
850
nv = self.num_versions()
855
# For creating the ancestry, IntSet is much faster (3.7s vs 0.17s)
856
# The problem is that set membership is much more expensive
857
name = self._idx_to_name(i)
861
for p in self._parents[i]:
862
new_inc.update(inclusions[self._idx_to_name(p)])
864
if new_inc != self.get_ancestry(name):
865
raise AssertionError(
867
% (new_inc, self.get_ancestry(name)))
868
inclusions[name] = new_inc
870
nlines = len(self._weave)
872
update_text = 'checking weave'
874
short_name = os.path.basename(self._weave_name)
875
update_text = 'checking %s' % (short_name,)
876
update_text = update_text[:25]
878
for lineno, insert, deleteset, line in self._walk_internal():
880
progress_bar.update(update_text, lineno, nlines)
882
for name, name_inclusions in inclusions.items():
883
# The active inclusion must be an ancestor,
884
# and no ancestors must have deleted this line,
885
# because we don't support resurrection.
886
if ((insert in name_inclusions) and
887
not (deleteset & name_inclusions)):
888
sha1s[name].update(line)
891
version = self._idx_to_name(i)
892
hd = sha1s[version].hexdigest().encode()
893
expected = self._sha1s[i]
895
raise WeaveInvalidChecksum(
896
"mismatched sha1 for version %s: "
897
"got %s, expected %s"
898
% (version, hd, expected))
900
# TODO: check insertions are properly nested, that there are
901
# no lines outside of insertion blocks, that deletions are
902
# properly paired, etc.
758
if other.numversions() == 0:
759
return # nothing to update, easy
760
# two loops so that we do not change ourselves before verifying it
762
# work through in index order to make sure we get all dependencies
763
for other_idx, name in enumerate(other._names):
764
self._check_version_consistent(other, other_idx, name)
769
for other_idx, name in enumerate(other._names):
770
# TODO: If all the parents of the other version are already
771
# present then we can avoid some work by just taking the delta
772
# and adjusting the offsets.
773
new_parents = self._imported_parents(other, other_idx)
774
sha1 = other._sha1s[other_idx]
778
if name in self._names:
779
idx = self.lookup(name)
780
n1 = map(other.idx_to_name, other._parents[other_idx] )
781
n2 = map(self.idx_to_name, self._parents[other_idx] )
782
if sha1 == self._sha1s[idx] and n1 == n2:
786
lines = other.get_lines(other_idx)
787
self.add(name, new_parents, lines, sha1)
789
mutter("merged = %d, processed = %d, file_id=%s; deltat=%d"%(
790
merged,processed,self._weave_name, time.time( )-time0))
904
795
def _imported_parents(self, other, other_idx):
905
796
"""Return list of parents in self corresponding to indexes in other."""
907
798
for parent_idx in other._parents[other_idx]:
908
799
parent_name = other._names[parent_idx]
909
if parent_name not in self._name_map:
800
if parent_name not in self._names:
910
801
# should not be possible
911
raise WeaveError("missing parent {%s} of {%s} in %r"
802
raise WeaveError("missing parent {%s} of {%s} in %r"
912
803
% (parent_name, other._name_map[other_idx], self))
913
804
new_parents.append(self._name_map[parent_name])
914
805
return new_parents
922
813
* the same direct parents (by name, not index, and disregarding
925
816
If present & correct return True;
926
if not present in self return False;
817
if not present in self return False;
927
818
if inconsistent raise error."""
928
819
this_idx = self._name_map.get(name, -1)
929
820
if this_idx != -1:
930
821
if self._sha1s[this_idx] != other._sha1s[other_idx]:
931
raise WeaveTextDiffers(name, self, other)
822
raise WeaveError("inconsistent texts for version {%s} "
823
"when joining weaves"
932
825
self_parents = self._parents[this_idx]
933
826
other_parents = other._parents[other_idx]
934
n1 = {self._names[i] for i in self_parents}
935
n2 = {other._names[i] for i in other_parents}
936
if not self._compatible_parents(n1, n2):
937
raise WeaveParentMismatch(
938
"inconsistent parents "
827
n1 = [self._names[i] for i in self_parents]
828
n2 = [other._names[i] for i in other_parents]
832
raise WeaveParentMismatch("inconsistent parents "
939
833
"for version {%s}: %s vs %s" % (name, n1, n2))
941
835
return True # ok!
945
def _reweave(self, other, pb, msg):
946
"""Reweave self with other - internal helper for join().
948
:param other: The other weave to merge
949
:param pb: An optional progress bar, indicating how far done we are
950
:param msg: An optional message for the progress
952
new_weave = _reweave(self, other, pb=pb, msg=msg)
953
self._copy_weave_content(new_weave)
955
def _copy_weave_content(self, otherweave):
956
"""adsorb the content from otherweave."""
839
def reweave(self, other):
840
"""Reweave self with other."""
841
new_weave = reweave(self, other)
957
842
for attr in self.__slots__:
958
if attr != '_weave_name':
959
setattr(self, attr, copy(getattr(otherweave, attr)))
962
class WeaveFile(Weave):
963
"""A WeaveFile represents a Weave on disk and writes on change."""
965
WEAVE_SUFFIX = '.weave'
967
def __init__(self, name, transport, filemode=None, create=False,
968
access_mode='w', get_scope=None):
969
"""Create a WeaveFile.
971
:param create: If not True, only open an existing knit.
973
super(WeaveFile, self).__init__(name, access_mode, get_scope=get_scope,
974
allow_reserved=False)
975
self._transport = transport
976
self._filemode = filemode
978
f = self._transport.get(name + WeaveFile.WEAVE_SUFFIX)
979
_read_weave_v5(BytesIO(f.read()), self)
980
except errors.NoSuchFile:
986
def _add_lines(self, version_id, parents, lines, parent_texts,
987
left_matching_blocks, nostore_sha, random_id,
989
"""Add a version and save the weave."""
990
self.check_not_reserved_id(version_id)
991
result = super(WeaveFile, self)._add_lines(
992
version_id, parents, lines, parent_texts, left_matching_blocks,
993
nostore_sha, random_id, check_content)
997
def copy_to(self, name, transport):
998
"""See VersionedFile.copy_to()."""
999
# as we are all in memory always, just serialise to the new place.
1001
write_weave_v5(self, sio)
1003
transport.put_file(name + WeaveFile.WEAVE_SUFFIX, sio, self._filemode)
1006
"""Save the weave."""
1007
self._check_write_ok()
1009
write_weave_v5(self, sio)
1011
bytes = sio.getvalue()
1012
path = self._weave_name + WeaveFile.WEAVE_SUFFIX
1014
self._transport.put_bytes(path, bytes, self._filemode)
1015
except errors.NoSuchFile:
1016
self._transport.mkdir(dirname(path))
1017
self._transport.put_bytes(path, bytes, self._filemode)
1021
"""See VersionedFile.get_suffixes()."""
1022
return [WeaveFile.WEAVE_SUFFIX]
1024
def insert_record_stream(self, stream):
1025
super(WeaveFile, self).insert_record_stream(stream)
1029
def _reweave(wa, wb, pb=None, msg=None):
843
setattr(self, attr, getattr(new_weave, attr))
1030
847
"""Combine two weaves and return the result.
1032
This works even if a revision R has different parents in
849
This works even if a revision R has different parents in
1033
850
wa and wb. In the resulting weave all the parents are given.
1035
This is done by just building up a new weave, maintaining ordering
852
This is done by just building up a new weave, maintaining ordering
1036
853
of the versions in the two inputs. More efficient approaches
1037
might be possible but it should only be necessary to do
1038
this operation rarely, when a new previously ghost version is
854
might be possible but it should only be necessary to do
855
this operation rarely, when a new previously ghost version is
1041
:param pb: An optional progress bar, indicating how far done we are
1042
:param msg: An optional message for the progress
860
queue_a = range(wa.numversions())
861
queue_b = range(wb.numversions())
1045
862
# first determine combined parents of all versions
1046
863
# map from version name -> all parent names
1047
864
combined_parents = _reweave_parent_graphs(wa, wb)
1048
865
mutter("combined parents: %r", combined_parents)
1049
order = tsort.topo_sort(combined_parents.items())
866
order = topo_sort(combined_parents.iteritems())
1050
867
mutter("order to reweave: %r", order)
1055
for idx, name in enumerate(order):
1057
pb.update(msg, idx, len(order))
1058
869
if name in wa._name_map:
1059
870
lines = wa.get_lines(name)
1060
871
if name in wb._name_map:
1061
lines_b = wb.get_lines(name)
1062
if lines != lines_b:
1063
mutter('Weaves differ on content. rev_id {%s}', name)
1064
mutter('weaves: %s, %s', wa._weave_name, wb._weave_name)
1066
lines = list(difflib.unified_diff(lines, lines_b,
1067
wa._weave_name, wb._weave_name))
1068
mutter('lines:\n%s', ''.join(lines))
1069
raise WeaveTextDiffers(name, wa, wb)
872
assert lines == wb.get_lines(name)
1071
874
lines = wb.get_lines(name)
1072
wr._add(name, lines, [wr._lookup(i) for i in combined_parents[name]])
875
wr.add(name, combined_parents[name], lines)
1076
879
def _reweave_parent_graphs(wa, wb):
1077
880
"""Return combined parent ancestry for two weaves.
1079
882
Returned as a list of (version_name, set(parent_names))"""
1081
884
for weave in [wa, wb]:
1082
885
for idx, name in enumerate(weave._names):
1083
886
p = combined.setdefault(name, set())
1084
p.update(map(weave._idx_to_name, weave._parents[idx]))
887
p.update(map(weave.idx_to_name, weave._parents[idx]))
892
"""Show the weave's table-of-contents"""
893
print '%6s %50s %10s %10s' % ('ver', 'name', 'sha1', 'parents')
894
for i in (6, 50, 10, 10):
897
for i in range(w.numversions()):
900
parent_str = ' '.join(map(str, w._parents[i]))
901
print '%6d %-50.50s %10.10s %s' % (i, name, sha1, parent_str)
905
def weave_stats(weave_file, pb):
906
from bzrlib.weavefile import read_weave
908
wf = file(weave_file, 'rb')
910
# FIXME: doesn't work on pipes
911
weave_size = wf.tell()
915
for i in range(vers):
916
pb.update('checking sizes', i, vers)
917
for origin, lineno, line in w._extract([i]):
922
print 'versions %9d' % vers
923
print 'weave file %9d bytes' % weave_size
924
print 'total contents %9d bytes' % total
925
print 'compression ratio %9.2fx' % (float(total) / float(weave_size))
928
print 'average size %9d bytes' % avg
929
print 'relative size %9.2fx' % (float(weave_size) / float(avg))
933
print """bzr weave tool
935
Experimental tool for weave algorithm.
939
Create an empty weave file
940
weave get WEAVEFILE VERSION
941
Write out specified version.
942
weave check WEAVEFILE
943
Check consistency of all versions.
945
Display table of contents.
946
weave add WEAVEFILE NAME [BASE...] < NEWTEXT
947
Add NEWTEXT, with specified parent versions.
948
weave annotate WEAVEFILE VERSION
949
Display origin of each line.
950
weave mash WEAVEFILE VERSION...
951
Display composite of all selected versions.
952
weave merge WEAVEFILE VERSION1 VERSION2 > OUT
953
Auto-merge two versions and display conflicts.
954
weave diff WEAVEFILE VERSION1 VERSION2
955
Show differences between two versions.
959
% weave init foo.weave
961
% weave add foo.weave ver0 < foo.txt
964
(create updated version)
966
% weave get foo.weave 0 | diff -u - foo.txt
967
% weave add foo.weave ver1 0 < foo.txt
970
% weave get foo.weave 0 > foo.txt (create forked version)
972
% weave add foo.weave ver2 0 < foo.txt
975
% weave merge foo.weave 1 2 > foo.txt (merge them)
976
% vi foo.txt (resolve conflicts)
977
% weave add foo.weave merged 1 2 < foo.txt (commit merged version)
989
# in case we're run directly from the subdirectory
990
sys.path.append('..')
992
from bzrlib.weavefile import write_weave, read_weave
993
from bzrlib.progress import ProgressBar
1008
return read_weave(file(argv[2], 'rb'))
1014
# at the moment, based on everything in the file
1016
parents = map(int, argv[4:])
1017
lines = sys.stdin.readlines()
1018
ver = w.add(name, parents, lines)
1019
write_weave(w, file(argv[2], 'wb'))
1020
print 'added version %r %d' % (name, ver)
1023
if os.path.exists(fn):
1024
raise IOError("file exists")
1026
write_weave(w, file(fn, 'wb'))
1027
elif cmd == 'get': # get one version
1029
sys.stdout.writelines(w.get_iter(int(argv[3])))
1031
elif cmd == 'mash': # get composite
1033
sys.stdout.writelines(w.mash_iter(map(int, argv[3:])))
1036
from difflib import unified_diff
1039
v1, v2 = map(int, argv[3:5])
1042
diff_gen = unified_diff(lines1, lines2,
1043
'%s version %d' % (fn, v1),
1044
'%s version %d' % (fn, v2))
1045
sys.stdout.writelines(diff_gen)
1047
elif cmd == 'annotate':
1049
# newline is added to all lines regardless; too hard to get
1050
# reasonable formatting otherwise
1052
for origin, text in w.annotate(int(argv[3])):
1053
text = text.rstrip('\r\n')
1055
print ' | %s' % (text)
1057
print '%5d | %s' % (origin, text)
1063
elif cmd == 'stats':
1064
weave_stats(argv[2], ProgressBar())
1066
elif cmd == 'check':
1071
print '%d versions ok' % w.numversions()
1073
elif cmd == 'inclusions':
1075
print ' '.join(map(str, w.inclusions([int(argv[3])])))
1077
elif cmd == 'parents':
1079
print ' '.join(map(str, w._parents[int(argv[3])]))
1081
elif cmd == 'plan-merge':
1083
for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
1085
print '%14s | %s' % (state, line),
1087
elif cmd == 'merge':
1089
p = w.plan_merge(int(argv[3]), int(argv[4]))
1090
sys.stdout.writelines(w.weave_merge(p))
1092
elif cmd == 'mash-merge':
1098
v1, v2 = map(int, argv[3:5])
1100
basis = w.inclusions([v1]).intersection(w.inclusions([v2]))
1102
base_lines = list(w.mash_iter(basis))
1103
a_lines = list(w.get(v1))
1104
b_lines = list(w.get(v2))
1106
from bzrlib.merge3 import Merge3
1107
m3 = Merge3(base_lines, a_lines, b_lines)
1109
name_a = 'version %d' % v1
1110
name_b = 'version %d' % v2
1111
sys.stdout.writelines(m3.merge_lines(name_a=name_a, name_b=name_b))
1113
raise ValueError('unknown command %r' % cmd)
1117
def profile_main(argv):
1118
import tempfile, hotshot, hotshot.stats
1120
prof_f = tempfile.NamedTemporaryFile()
1122
prof = hotshot.Profile(prof_f.name)
1124
ret = prof.runcall(main, argv)
1127
stats = hotshot.stats.load(prof_f.name)
1129
stats.sort_stats('cumulative')
1130
## XXX: Might like to write to stderr or the trace file instead but
1131
## print_stats seems hardcoded to stdout
1132
stats.print_stats(20)
1137
def lsprofile_main(argv):
1138
from bzrlib.lsprof import profile
1139
ret,stats = profile(main, argv)
1145
if __name__ == '__main__':
1147
if '--profile' in sys.argv:
1149
args.remove('--profile')
1150
sys.exit(profile_main(args))
1151
elif '--lsprof' in sys.argv:
1153
args.remove('--lsprof')
1154
sys.exit(lsprofile_main(args))
1156
sys.exit(main(sys.argv))
added
removed
bzrlib/weave.py
