1
# Copyright (C) 2005, 2006 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
"""Knit versionedfile implementation.
19
A knit is a versioned file implementation that supports efficient append only
23
lifeless: the data file is made up of "delta records". each delta record has a delta header
24
that contains; (1) a version id, (2) the size of the delta (in lines), and (3) the digest of
25
the -expanded data- (ie, the delta applied to the parent). the delta also ends with a
26
end-marker; simply "end VERSION"
28
delta can be line or full contents.a
29
... the 8's there are the index number of the annotation.
30
version robertc@robertcollins.net-20051003014215-ee2990904cc4c7ad 7 c7d23b2a5bd6ca00e8e266cec0ec228158ee9f9e
34
8 e.set('executable', 'yes')
36
8 if elt.get('executable') == 'yes':
37
8 ie.executable = True
38
end robertc@robertcollins.net-20051003014215-ee2990904cc4c7ad
42
09:33 < jrydberg> lifeless: each index is made up of a tuple of; version id, options, position, size, parents
43
09:33 < jrydberg> lifeless: the parents are currently dictionary compressed
44
09:33 < jrydberg> lifeless: (meaning it currently does not support ghosts)
45
09:33 < lifeless> right
46
09:33 < jrydberg> lifeless: the position and size is the range in the data file
49
so the index sequence is the dictionary compressed sequence number used
50
in the deltas to provide line annotation
55
# 10:16 < lifeless> make partial index writes safe
56
# 10:16 < lifeless> implement 'knit.check()' like weave.check()
57
# 10:17 < lifeless> record known ghosts so we can detect when they are filled in rather than the current 'reweave
59
# move sha1 out of the content so that join is faster at verifying parents
60
# record content length ?
64
from cStringIO import StringIO
66
from itertools import izip, chain
81
from bzrlib.errors import (
89
RevisionAlreadyPresent,
91
from bzrlib.tuned_gzip import GzipFile
92
from bzrlib.trace import mutter
93
from bzrlib.osutils import (
98
from bzrlib.symbol_versioning import DEPRECATED_PARAMETER, deprecated_passed
99
from bzrlib.tsort import topo_sort
102
from bzrlib.versionedfile import VersionedFile, InterVersionedFile
105
# TODO: Split out code specific to this format into an associated object.
107
# TODO: Can we put in some kind of value to check that the index and data
108
# files belong together?
110
# TODO: accommodate binaries, perhaps by storing a byte count
112
# TODO: function to check whole file
114
# TODO: atomically append data, then measure backwards from the cursor
115
# position after writing to work out where it was located. we may need to
116
# bypass python file buffering.
118
DATA_SUFFIX = '.knit'
119
INDEX_SUFFIX = '.kndx'
122
class KnitContent(object):
123
"""Content of a knit version to which deltas can be applied."""
125
def __init__(self, lines):
128
def annotate_iter(self):
129
"""Yield tuples of (origin, text) for each content line."""
130
return iter(self._lines)
133
"""Return a list of (origin, text) tuples."""
134
return list(self.annotate_iter())
136
def line_delta_iter(self, new_lines):
137
"""Generate line-based delta from this content to new_lines."""
138
new_texts = new_lines.text()
139
old_texts = self.text()
140
s = KnitSequenceMatcher(None, old_texts, new_texts)
141
for tag, i1, i2, j1, j2 in s.get_opcodes():
144
# ofrom, oto, length, data
145
yield i1, i2, j2 - j1, new_lines._lines[j1:j2]
147
def line_delta(self, new_lines):
148
return list(self.line_delta_iter(new_lines))
151
return [text for origin, text in self._lines]
154
return KnitContent(self._lines[:])
157
class _KnitFactory(object):
158
"""Base factory for creating content objects."""
160
def make(self, lines, version_id):
161
num_lines = len(lines)
162
return KnitContent(zip([version_id] * num_lines, lines))
165
class KnitAnnotateFactory(_KnitFactory):
166
"""Factory for creating annotated Content objects."""
170
def parse_fulltext(self, content, version_id):
171
"""Convert fulltext to internal representation
173
fulltext content is of the format
174
revid(utf8) plaintext\n
175
internal representation is of the format:
178
# TODO: jam 20070209 The tests expect this to be returned as tuples,
179
# but the code itself doesn't really depend on that.
180
# Figure out a way to not require the overhead of turning the
181
# list back into tuples.
182
lines = [tuple(line.split(' ', 1)) for line in content]
183
return KnitContent(lines)
185
def parse_line_delta_iter(self, lines):
186
return iter(self.parse_line_delta(lines))
188
def parse_line_delta(self, lines, version_id):
189
"""Convert a line based delta into internal representation.
191
line delta is in the form of:
192
intstart intend intcount
194
revid(utf8) newline\n
195
internal representation is
196
(start, end, count, [1..count tuples (revid, newline)])
202
# walk through the lines parsing.
204
start, end, count = [int(n) for n in header.split(',')]
205
contents = [tuple(next().split(' ', 1)) for i in xrange(count)]
206
result.append((start, end, count, contents))
209
def get_fulltext_content(self, lines):
210
"""Extract just the content lines from a fulltext."""
211
return (line.split(' ', 1)[1] for line in lines)
213
def get_linedelta_content(self, lines):
214
"""Extract just the content from a line delta.
216
This doesn't return all of the extra information stored in a delta.
217
Only the actual content lines.
222
header = header.split(',')
223
count = int(header[2])
224
for i in xrange(count):
225
origin, text = next().split(' ', 1)
228
def lower_fulltext(self, content):
229
"""convert a fulltext content record into a serializable form.
231
see parse_fulltext which this inverts.
233
# TODO: jam 20070209 We only do the caching thing to make sure that
234
# the origin is a valid utf-8 line, eventually we could remove it
235
get_cached_utf8 = cache_utf8.get_cached_utf8
236
return ['%s %s' % (get_cached_utf8(o), t) for o, t in content._lines]
238
def lower_line_delta(self, delta):
239
"""convert a delta into a serializable form.
241
See parse_line_delta which this inverts.
243
# TODO: jam 20070209 We only do the caching thing to make sure that
244
# the origin is a valid utf-8 line, eventually we could remove it
245
get_cached_utf8 = cache_utf8.get_cached_utf8
247
for start, end, c, lines in delta:
248
out.append('%d,%d,%d\n' % (start, end, c))
249
out.extend(get_cached_utf8(origin) + ' ' + text
250
for origin, text in lines)
254
class KnitPlainFactory(_KnitFactory):
255
"""Factory for creating plain Content objects."""
259
def parse_fulltext(self, content, version_id):
260
"""This parses an unannotated fulltext.
262
Note that this is not a noop - the internal representation
263
has (versionid, line) - its just a constant versionid.
265
return self.make(content, version_id)
267
def parse_line_delta_iter(self, lines, version_id):
269
num_lines = len(lines)
270
while cur < num_lines:
273
start, end, c = [int(n) for n in header.split(',')]
274
yield start, end, c, zip([version_id] * c, lines[cur:cur+c])
277
def parse_line_delta(self, lines, version_id):
278
return list(self.parse_line_delta_iter(lines, version_id))
280
def get_fulltext_content(self, lines):
281
"""Extract just the content lines from a fulltext."""
284
def get_linedelta_content(self, lines):
285
"""Extract just the content from a line delta.
287
This doesn't return all of the extra information stored in a delta.
288
Only the actual content lines.
293
header = header.split(',')
294
count = int(header[2])
295
for i in xrange(count):
298
def lower_fulltext(self, content):
299
return content.text()
301
def lower_line_delta(self, delta):
303
for start, end, c, lines in delta:
304
out.append('%d,%d,%d\n' % (start, end, c))
305
out.extend([text for origin, text in lines])
309
def make_empty_knit(transport, relpath):
310
"""Construct a empty knit at the specified location."""
311
k = KnitVersionedFile(transport, relpath, 'w', KnitPlainFactory)
315
class KnitVersionedFile(VersionedFile):
316
"""Weave-like structure with faster random access.
318
A knit stores a number of texts and a summary of the relationships
319
between them. Texts are identified by a string version-id. Texts
320
are normally stored and retrieved as a series of lines, but can
321
also be passed as single strings.
323
Lines are stored with the trailing newline (if any) included, to
324
avoid special cases for files with no final newline. Lines are
325
composed of 8-bit characters, not unicode. The combination of
326
these approaches should mean any 'binary' file can be safely
327
stored and retrieved.
330
def __init__(self, relpath, transport, file_mode=None, access_mode=None,
331
factory=None, basis_knit=DEPRECATED_PARAMETER, delta=True,
332
create=False, create_parent_dir=False, delay_create=False,
334
"""Construct a knit at location specified by relpath.
336
:param create: If not True, only open an existing knit.
337
:param create_parent_dir: If True, create the parent directory if
338
creating the file fails. (This is used for stores with
339
hash-prefixes that may not exist yet)
340
:param delay_create: The calling code is aware that the knit won't
341
actually be created until the first data is stored.
343
if deprecated_passed(basis_knit):
344
warnings.warn("KnitVersionedFile.__(): The basis_knit parameter is"
345
" deprecated as of bzr 0.9.",
346
DeprecationWarning, stacklevel=2)
347
if access_mode is None:
349
super(KnitVersionedFile, self).__init__(access_mode)
350
assert access_mode in ('r', 'w'), "invalid mode specified %r" % access_mode
351
self.transport = transport
352
self.filename = relpath
353
self.factory = factory or KnitAnnotateFactory()
354
self.writable = (access_mode == 'w')
357
self._max_delta_chain = 200
359
self._index = _KnitIndex(transport, relpath + INDEX_SUFFIX,
360
access_mode, create=create, file_mode=file_mode,
361
create_parent_dir=create_parent_dir, delay_create=delay_create,
363
self._data = _KnitData(transport, relpath + DATA_SUFFIX,
364
access_mode, create=create and not len(self), file_mode=file_mode,
365
create_parent_dir=create_parent_dir, delay_create=delay_create,
369
return '%s(%s)' % (self.__class__.__name__,
370
self.transport.abspath(self.filename))
372
def _check_should_delta(self, first_parents):
373
"""Iterate back through the parent listing, looking for a fulltext.
375
This is used when we want to decide whether to add a delta or a new
376
fulltext. It searches for _max_delta_chain parents. When it finds a
377
fulltext parent, it sees if the total size of the deltas leading up to
378
it is large enough to indicate that we want a new full text anyway.
380
Return True if we should create a new delta, False if we should use a
385
delta_parents = first_parents
386
for count in xrange(self._max_delta_chain):
387
parent = delta_parents[0]
388
method = self._index.get_method(parent)
389
pos, size = self._index.get_position(parent)
390
if method == 'fulltext':
394
delta_parents = self._index.get_parents(parent)
396
# We couldn't find a fulltext, so we must create a new one
399
return fulltext_size > delta_size
401
def _add_delta(self, version_id, parents, delta_parent, sha1, noeol, delta):
402
"""See VersionedFile._add_delta()."""
403
self._check_add(version_id, []) # should we check the lines ?
404
self._check_versions_present(parents)
408
for parent in parents:
409
if not self.has_version(parent):
410
ghosts.append(parent)
412
present_parents.append(parent)
414
if delta_parent is None:
415
# reconstitute as full text.
416
assert len(delta) == 1 or len(delta) == 0
418
assert delta[0][0] == 0
419
assert delta[0][1] == 0, delta[0][1]
420
return super(KnitVersionedFile, self)._add_delta(version_id,
431
options.append('no-eol')
433
if delta_parent is not None:
434
# determine the current delta chain length.
435
# To speed the extract of texts the delta chain is limited
436
# to a fixed number of deltas. This should minimize both
437
# I/O and the time spend applying deltas.
438
# The window was changed to a maximum of 200 deltas, but also added
439
# was a check that the total compressed size of the deltas is
440
# smaller than the compressed size of the fulltext.
441
if not self._check_should_delta([delta_parent]):
442
# We don't want a delta here, just do a normal insertion.
443
return super(KnitVersionedFile, self)._add_delta(version_id,
450
options.append('line-delta')
451
store_lines = self.factory.lower_line_delta(delta)
453
where, size = self._data.add_record(version_id, digest, store_lines)
454
self._index.add_version(version_id, options, where, size, parents)
456
def _add_raw_records(self, records, data):
457
"""Add all the records 'records' with data pre-joined in 'data'.
459
:param records: A list of tuples(version_id, options, parents, size).
460
:param data: The data for the records. When it is written, the records
461
are adjusted to have pos pointing into data by the sum of
462
the preceding records sizes.
465
pos = self._data.add_raw_record(data)
468
for (version_id, options, parents, size) in records:
469
index_entries.append((version_id, options, pos+offset,
471
if self._data._do_cache:
472
self._data._cache[version_id] = data[offset:offset+size]
474
self._index.add_versions(index_entries)
476
def enable_cache(self):
477
"""Start caching data for this knit"""
478
self._data.enable_cache()
480
def clear_cache(self):
481
"""Clear the data cache only."""
482
self._data.clear_cache()
484
def copy_to(self, name, transport):
485
"""See VersionedFile.copy_to()."""
486
# copy the current index to a temp index to avoid racing with local
488
transport.put_file_non_atomic(name + INDEX_SUFFIX + '.tmp',
489
self.transport.get(self._index._filename))
491
f = self._data._open_file()
493
transport.put_file(name + DATA_SUFFIX, f)
496
# move the copied index into place
497
transport.move(name + INDEX_SUFFIX + '.tmp', name + INDEX_SUFFIX)
499
def create_empty(self, name, transport, mode=None):
500
return KnitVersionedFile(name, transport, factory=self.factory,
501
delta=self.delta, create=True)
503
def _fix_parents(self, version_id, new_parents):
504
"""Fix the parents list for version.
506
This is done by appending a new version to the index
507
with identical data except for the parents list.
508
the parents list must be a superset of the current
511
current_values = self._index._cache[version_id]
512
assert set(current_values[4]).difference(set(new_parents)) == set()
513
self._index.add_version(version_id,
519
def get_delta(self, version_id):
520
"""Get a delta for constructing version from some other version."""
521
version_id = osutils.safe_revision_id(version_id)
522
self.check_not_reserved_id(version_id)
523
if not self.has_version(version_id):
524
raise RevisionNotPresent(version_id, self.filename)
526
parents = self.get_parents(version_id)
531
data_pos, data_size = self._index.get_position(version_id)
532
data, sha1 = self._data.read_records(((version_id, data_pos, data_size),))[version_id]
533
noeol = 'no-eol' in self._index.get_options(version_id)
534
if 'fulltext' == self._index.get_method(version_id):
535
new_content = self.factory.parse_fulltext(data, version_id)
536
if parent is not None:
537
reference_content = self._get_content(parent)
538
old_texts = reference_content.text()
541
new_texts = new_content.text()
542
delta_seq = KnitSequenceMatcher(None, old_texts, new_texts)
543
return parent, sha1, noeol, self._make_line_delta(delta_seq, new_content)
545
delta = self.factory.parse_line_delta(data, version_id)
546
return parent, sha1, noeol, delta
548
def get_graph_with_ghosts(self):
549
"""See VersionedFile.get_graph_with_ghosts()."""
550
graph_items = self._index.get_graph()
551
return dict(graph_items)
553
def get_sha1(self, version_id):
554
"""See VersionedFile.get_sha1()."""
555
version_id = osutils.safe_revision_id(version_id)
556
record_map = self._get_record_map([version_id])
557
method, content, digest, next = record_map[version_id]
562
"""See VersionedFile.get_suffixes()."""
563
return [DATA_SUFFIX, INDEX_SUFFIX]
565
def has_ghost(self, version_id):
566
"""True if there is a ghost reference in the file to version_id."""
567
version_id = osutils.safe_revision_id(version_id)
569
if self.has_version(version_id):
571
# optimisable if needed by memoising the _ghosts set.
572
items = self._index.get_graph()
573
for node, parents in items:
574
for parent in parents:
575
if parent not in self._index._cache:
576
if parent == version_id:
581
"""See VersionedFile.versions."""
582
return self._index.get_versions()
584
def has_version(self, version_id):
585
"""See VersionedFile.has_version."""
586
version_id = osutils.safe_revision_id(version_id)
587
return self._index.has_version(version_id)
589
__contains__ = has_version
591
def _merge_annotations(self, content, parents, parent_texts={},
592
delta=None, annotated=None):
593
"""Merge annotations for content. This is done by comparing
594
the annotations based on changed to the text.
598
for parent_id in parents:
599
merge_content = self._get_content(parent_id, parent_texts)
600
seq = patiencediff.PatienceSequenceMatcher(
601
None, merge_content.text(), content.text())
602
if delta_seq is None:
603
# setup a delta seq to reuse.
605
for i, j, n in seq.get_matching_blocks():
608
# this appears to copy (origin, text) pairs across to the new
609
# content for any line that matches the last-checked parent.
610
# FIXME: save the sequence control data for delta compression
611
# against the most relevant parent rather than rediffing.
612
content._lines[j:j+n] = merge_content._lines[i:i+n]
615
reference_content = self._get_content(parents[0], parent_texts)
616
new_texts = content.text()
617
old_texts = reference_content.text()
618
delta_seq = patiencediff.PatienceSequenceMatcher(
619
None, old_texts, new_texts)
620
return self._make_line_delta(delta_seq, content)
622
def _make_line_delta(self, delta_seq, new_content):
623
"""Generate a line delta from delta_seq and new_content."""
625
for op in delta_seq.get_opcodes():
628
diff_hunks.append((op[1], op[2], op[4]-op[3], new_content._lines[op[3]:op[4]]))
631
def _get_components_positions(self, version_ids):
632
"""Produce a map of position data for the components of versions.
634
This data is intended to be used for retrieving the knit records.
636
A dict of version_id to (method, data_pos, data_size, next) is
638
method is the way referenced data should be applied.
639
data_pos is the position of the data in the knit.
640
data_size is the size of the data in the knit.
641
next is the build-parent of the version, or None for fulltexts.
644
for version_id in version_ids:
647
while cursor is not None and cursor not in component_data:
648
method = self._index.get_method(cursor)
649
if method == 'fulltext':
652
next = self.get_parents(cursor)[0]
653
data_pos, data_size = self._index.get_position(cursor)
654
component_data[cursor] = (method, data_pos, data_size, next)
656
return component_data
658
def _get_content(self, version_id, parent_texts={}):
659
"""Returns a content object that makes up the specified
661
if not self.has_version(version_id):
662
raise RevisionNotPresent(version_id, self.filename)
664
cached_version = parent_texts.get(version_id, None)
665
if cached_version is not None:
666
return cached_version
668
text_map, contents_map = self._get_content_maps([version_id])
669
return contents_map[version_id]
671
def _check_versions_present(self, version_ids):
672
"""Check that all specified versions are present."""
673
self._index.check_versions_present(version_ids)
675
def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts):
676
"""See VersionedFile.add_lines_with_ghosts()."""
677
self._check_add(version_id, lines)
678
return self._add(version_id, lines[:], parents, self.delta, parent_texts)
680
def _add_lines(self, version_id, parents, lines, parent_texts):
681
"""See VersionedFile.add_lines."""
682
self._check_add(version_id, lines)
683
self._check_versions_present(parents)
684
return self._add(version_id, lines[:], parents, self.delta, parent_texts)
686
def _check_add(self, version_id, lines):
687
"""check that version_id and lines are safe to add."""
688
assert self.writable, "knit is not opened for write"
689
### FIXME escape. RBC 20060228
690
if contains_whitespace(version_id):
691
raise InvalidRevisionId(version_id, self.filename)
692
self.check_not_reserved_id(version_id)
693
if self.has_version(version_id):
694
raise RevisionAlreadyPresent(version_id, self.filename)
695
self._check_lines_not_unicode(lines)
696
self._check_lines_are_lines(lines)
698
def _add(self, version_id, lines, parents, delta, parent_texts):
699
"""Add a set of lines on top of version specified by parents.
701
If delta is true, compress the text as a line-delta against
704
Any versions not present will be converted into ghosts.
706
# 461 0 6546.0390 43.9100 bzrlib.knit:489(_add)
707
# +400 0 889.4890 418.9790 +bzrlib.knit:192(lower_fulltext)
708
# +461 0 1364.8070 108.8030 +bzrlib.knit:996(add_record)
709
# +461 0 193.3940 41.5720 +bzrlib.knit:898(add_version)
710
# +461 0 134.0590 18.3810 +bzrlib.osutils:361(sha_strings)
711
# +461 0 36.3420 15.4540 +bzrlib.knit:146(make)
712
# +1383 0 8.0370 8.0370 +<len>
713
# +61 0 13.5770 7.9190 +bzrlib.knit:199(lower_line_delta)
714
# +61 0 963.3470 7.8740 +bzrlib.knit:427(_get_content)
715
# +61 0 973.9950 5.2950 +bzrlib.knit:136(line_delta)
716
# +61 0 1918.1800 5.2640 +bzrlib.knit:359(_merge_annotations)
720
if parent_texts is None:
722
for parent in parents:
723
if not self.has_version(parent):
724
ghosts.append(parent)
726
present_parents.append(parent)
728
if delta and not len(present_parents):
731
digest = sha_strings(lines)
734
if lines[-1][-1] != '\n':
735
options.append('no-eol')
736
lines[-1] = lines[-1] + '\n'
738
if len(present_parents) and delta:
739
# To speed the extract of texts the delta chain is limited
740
# to a fixed number of deltas. This should minimize both
741
# I/O and the time spend applying deltas.
742
delta = self._check_should_delta(present_parents)
744
lines = self.factory.make(lines, version_id)
745
if delta or (self.factory.annotated and len(present_parents) > 0):
746
# Merge annotations from parent texts if so is needed.
747
delta_hunks = self._merge_annotations(lines, present_parents, parent_texts,
748
delta, self.factory.annotated)
751
options.append('line-delta')
752
store_lines = self.factory.lower_line_delta(delta_hunks)
754
options.append('fulltext')
755
store_lines = self.factory.lower_fulltext(lines)
757
where, size = self._data.add_record(version_id, digest, store_lines)
758
self._index.add_version(version_id, options, where, size, parents)
761
def check(self, progress_bar=None):
762
"""See VersionedFile.check()."""
764
def _clone_text(self, new_version_id, old_version_id, parents):
765
"""See VersionedFile.clone_text()."""
766
# FIXME RBC 20060228 make fast by only inserting an index with null
768
self.add_lines(new_version_id, parents, self.get_lines(old_version_id))
770
def get_lines(self, version_id):
771
"""See VersionedFile.get_lines()."""
772
return self.get_line_list([version_id])[0]
774
def _get_record_map(self, version_ids):
775
"""Produce a dictionary of knit records.
777
The keys are version_ids, the values are tuples of (method, content,
779
method is the way the content should be applied.
780
content is a KnitContent object.
781
digest is the SHA1 digest of this version id after all steps are done
782
next is the build-parent of the version, i.e. the leftmost ancestor.
783
If the method is fulltext, next will be None.
785
position_map = self._get_components_positions(version_ids)
786
# c = component_id, m = method, p = position, s = size, n = next
787
records = [(c, p, s) for c, (m, p, s, n) in position_map.iteritems()]
789
for component_id, content, digest in \
790
self._data.read_records_iter(records):
791
method, position, size, next = position_map[component_id]
792
record_map[component_id] = method, content, digest, next
796
def get_text(self, version_id):
797
"""See VersionedFile.get_text"""
798
return self.get_texts([version_id])[0]
800
def get_texts(self, version_ids):
801
return [''.join(l) for l in self.get_line_list(version_ids)]
803
def get_line_list(self, version_ids):
804
"""Return the texts of listed versions as a list of strings."""
805
version_ids = [osutils.safe_revision_id(v) for v in version_ids]
806
for version_id in version_ids:
807
self.check_not_reserved_id(version_id)
808
text_map, content_map = self._get_content_maps(version_ids)
809
return [text_map[v] for v in version_ids]
811
def _get_content_maps(self, version_ids):
812
"""Produce maps of text and KnitContents
814
:return: (text_map, content_map) where text_map contains the texts for
815
the requested versions and content_map contains the KnitContents.
816
Both dicts take version_ids as their keys.
818
for version_id in version_ids:
819
if not self.has_version(version_id):
820
raise RevisionNotPresent(version_id, self.filename)
821
record_map = self._get_record_map(version_ids)
826
for version_id in version_ids:
829
while cursor is not None:
830
method, data, digest, next = record_map[cursor]
831
components.append((cursor, method, data, digest))
832
if cursor in content_map:
837
for component_id, method, data, digest in reversed(components):
838
if component_id in content_map:
839
content = content_map[component_id]
841
if method == 'fulltext':
842
assert content is None
843
content = self.factory.parse_fulltext(data, version_id)
844
elif method == 'line-delta':
845
delta = self.factory.parse_line_delta(data, version_id)
846
content = content.copy()
847
content._lines = self._apply_delta(content._lines,
849
content_map[component_id] = content
851
if 'no-eol' in self._index.get_options(version_id):
852
content = content.copy()
853
line = content._lines[-1][1].rstrip('\n')
854
content._lines[-1] = (content._lines[-1][0], line)
855
final_content[version_id] = content
857
# digest here is the digest from the last applied component.
858
text = content.text()
859
if sha_strings(text) != digest:
860
raise KnitCorrupt(self.filename,
861
'sha-1 does not match %s' % version_id)
863
text_map[version_id] = text
864
return text_map, final_content
866
def iter_lines_added_or_present_in_versions(self, version_ids=None,
868
"""See VersionedFile.iter_lines_added_or_present_in_versions()."""
869
if version_ids is None:
870
version_ids = self.versions()
872
version_ids = [osutils.safe_revision_id(v) for v in version_ids]
874
pb = progress.DummyProgress()
875
# we don't care about inclusions, the caller cares.
876
# but we need to setup a list of records to visit.
877
# we need version_id, position, length
878
version_id_records = []
879
requested_versions = set(version_ids)
880
# filter for available versions
881
for version_id in requested_versions:
882
if not self.has_version(version_id):
883
raise RevisionNotPresent(version_id, self.filename)
884
# get a in-component-order queue:
885
for version_id in self.versions():
886
if version_id in requested_versions:
887
data_pos, length = self._index.get_position(version_id)
888
version_id_records.append((version_id, data_pos, length))
890
total = len(version_id_records)
891
for version_idx, (version_id, data, sha_value) in \
892
enumerate(self._data.read_records_iter(version_id_records)):
893
pb.update('Walking content.', version_idx, total)
894
method = self._index.get_method(version_id)
896
assert method in ('fulltext', 'line-delta')
897
if method == 'fulltext':
898
line_iterator = self.factory.get_fulltext_content(data)
900
line_iterator = self.factory.get_linedelta_content(data)
901
for line in line_iterator:
904
pb.update('Walking content.', total, total)
906
def num_versions(self):
907
"""See VersionedFile.num_versions()."""
908
return self._index.num_versions()
910
__len__ = num_versions
912
def annotate_iter(self, version_id):
913
"""See VersionedFile.annotate_iter."""
914
version_id = osutils.safe_revision_id(version_id)
915
content = self._get_content(version_id)
916
for origin, text in content.annotate_iter():
919
def get_parents(self, version_id):
920
"""See VersionedFile.get_parents."""
923
# 52554 calls in 1264 872 internal down from 3674
924
version_id = osutils.safe_revision_id(version_id)
926
return self._index.get_parents(version_id)
928
raise RevisionNotPresent(version_id, self.filename)
930
def get_parents_with_ghosts(self, version_id):
931
"""See VersionedFile.get_parents."""
932
version_id = osutils.safe_revision_id(version_id)
934
return self._index.get_parents_with_ghosts(version_id)
936
raise RevisionNotPresent(version_id, self.filename)
938
def get_ancestry(self, versions):
939
"""See VersionedFile.get_ancestry."""
940
if isinstance(versions, basestring):
941
versions = [versions]
944
versions = [osutils.safe_revision_id(v) for v in versions]
945
return self._index.get_ancestry(versions)
947
def get_ancestry_with_ghosts(self, versions):
948
"""See VersionedFile.get_ancestry_with_ghosts."""
949
if isinstance(versions, basestring):
950
versions = [versions]
953
versions = [osutils.safe_revision_id(v) for v in versions]
954
return self._index.get_ancestry_with_ghosts(versions)
956
#@deprecated_method(zero_eight)
957
def walk(self, version_ids):
958
"""See VersionedFile.walk."""
959
# We take the short path here, and extract all relevant texts
960
# and put them in a weave and let that do all the work. Far
961
# from optimal, but is much simpler.
962
# FIXME RB 20060228 this really is inefficient!
963
from bzrlib.weave import Weave
965
w = Weave(self.filename)
966
ancestry = self.get_ancestry(version_ids)
967
sorted_graph = topo_sort(self._index.get_graph())
968
version_list = [vid for vid in sorted_graph if vid in ancestry]
970
for version_id in version_list:
971
lines = self.get_lines(version_id)
972
w.add_lines(version_id, self.get_parents(version_id), lines)
974
for lineno, insert_id, dset, line in w.walk(version_ids):
975
yield lineno, insert_id, dset, line
977
def plan_merge(self, ver_a, ver_b):
978
"""See VersionedFile.plan_merge."""
979
ver_a = osutils.safe_revision_id(ver_a)
980
ver_b = osutils.safe_revision_id(ver_b)
981
ancestors_b = set(self.get_ancestry(ver_b))
982
def status_a(revision, text):
983
if revision in ancestors_b:
984
return 'killed-b', text
988
ancestors_a = set(self.get_ancestry(ver_a))
989
def status_b(revision, text):
990
if revision in ancestors_a:
991
return 'killed-a', text
995
annotated_a = self.annotate(ver_a)
996
annotated_b = self.annotate(ver_b)
997
plain_a = [t for (a, t) in annotated_a]
998
plain_b = [t for (a, t) in annotated_b]
999
blocks = KnitSequenceMatcher(None, plain_a, plain_b).get_matching_blocks()
1002
for ai, bi, l in blocks:
1003
# process all mismatched sections
1004
# (last mismatched section is handled because blocks always
1005
# includes a 0-length last block)
1006
for revision, text in annotated_a[a_cur:ai]:
1007
yield status_a(revision, text)
1008
for revision, text in annotated_b[b_cur:bi]:
1009
yield status_b(revision, text)
1011
# and now the matched section
1014
for text_a, text_b in zip(plain_a[ai:a_cur], plain_b[bi:b_cur]):
1015
assert text_a == text_b
1016
yield "unchanged", text_a
1019
class _KnitComponentFile(object):
1020
"""One of the files used to implement a knit database"""
1022
def __init__(self, transport, filename, mode, file_mode=None,
1023
create_parent_dir=False, dir_mode=None):
1024
self._transport = transport
1025
self._filename = filename
1027
self._file_mode = file_mode
1028
self._dir_mode = dir_mode
1029
self._create_parent_dir = create_parent_dir
1030
self._need_to_create = False
1032
def _full_path(self):
1033
"""Return the full path to this file."""
1034
return self._transport.base + self._filename
1036
def check_header(self, fp):
1037
line = fp.readline()
1039
# An empty file can actually be treated as though the file doesn't
1041
raise errors.NoSuchFile(self._full_path())
1042
if line != self.HEADER:
1043
raise KnitHeaderError(badline=line,
1044
filename=self._transport.abspath(self._filename))
1047
"""Commit is a nop."""
1050
return '%s(%s)' % (self.__class__.__name__, self._filename)
1053
class _KnitIndex(_KnitComponentFile):
1054
"""Manages knit index file.
1056
The index is already kept in memory and read on startup, to enable
1057
fast lookups of revision information. The cursor of the index
1058
file is always pointing to the end, making it easy to append
1061
_cache is a cache for fast mapping from version id to a Index
1064
_history is a cache for fast mapping from indexes to version ids.
1066
The index data format is dictionary compressed when it comes to
1067
parent references; a index entry may only have parents that with a
1068
lover index number. As a result, the index is topological sorted.
1070
Duplicate entries may be written to the index for a single version id
1071
if this is done then the latter one completely replaces the former:
1072
this allows updates to correct version and parent information.
1073
Note that the two entries may share the delta, and that successive
1074
annotations and references MUST point to the first entry.
1076
The index file on disc contains a header, followed by one line per knit
1077
record. The same revision can be present in an index file more than once.
1078
The first occurrence gets assigned a sequence number starting from 0.
1080
The format of a single line is
1081
REVISION_ID FLAGS BYTE_OFFSET LENGTH( PARENT_ID|PARENT_SEQUENCE_ID)* :\n
1082
REVISION_ID is a utf8-encoded revision id
1083
FLAGS is a comma separated list of flags about the record. Values include
1084
no-eol, line-delta, fulltext.
1085
BYTE_OFFSET is the ascii representation of the byte offset in the data file
1086
that the the compressed data starts at.
1087
LENGTH is the ascii representation of the length of the data file.
1088
PARENT_ID a utf-8 revision id prefixed by a '.' that is a parent of
1090
PARENT_SEQUENCE_ID the ascii representation of the sequence number of a
1091
revision id already in the knit that is a parent of REVISION_ID.
1092
The ' :' marker is the end of record marker.
1095
when a write is interrupted to the index file, it will result in a line
1096
that does not end in ' :'. If the ' :' is not present at the end of a line,
1097
or at the end of the file, then the record that is missing it will be
1098
ignored by the parser.
1100
When writing new records to the index file, the data is preceded by '\n'
1101
to ensure that records always start on new lines even if the last write was
1102
interrupted. As a result its normal for the last line in the index to be
1103
missing a trailing newline. One can be added with no harmful effects.
1106
HEADER = "# bzr knit index 8\n"
1108
# speed of knit parsing went from 280 ms to 280 ms with slots addition.
1109
# __slots__ = ['_cache', '_history', '_transport', '_filename']
1111
def _cache_version(self, version_id, options, pos, size, parents):
1112
"""Cache a version record in the history array and index cache.
1114
This is inlined into _load_data for performance. KEEP IN SYNC.
1115
(It saves 60ms, 25% of the __init__ overhead on local 4000 record
1118
# only want the _history index to reference the 1st index entry
1120
if version_id not in self._cache:
1121
index = len(self._history)
1122
self._history.append(version_id)
1124
index = self._cache[version_id][5]
1125
self._cache[version_id] = (version_id,
1132
def __init__(self, transport, filename, mode, create=False, file_mode=None,
1133
create_parent_dir=False, delay_create=False, dir_mode=None):
1134
_KnitComponentFile.__init__(self, transport, filename, mode,
1135
file_mode=file_mode,
1136
create_parent_dir=create_parent_dir,
1139
# position in _history is the 'official' index for a revision
1140
# but the values may have come from a newer entry.
1141
# so - wc -l of a knit index is != the number of unique names
1144
pb = ui.ui_factory.nested_progress_bar()
1146
pb.update('read knit index', 0, 1)
1148
fp = self._transport.get(self._filename)
1150
# _load_data may raise NoSuchFile if the target knit is
1156
if mode != 'w' or not create:
1159
self._need_to_create = True
1161
self._transport.put_bytes_non_atomic(
1162
self._filename, self.HEADER, mode=self._file_mode)
1164
pb.update('read knit index', 1, 1)
1167
def _load_data(self, fp):
1169
history = self._history
1170
get_cached_utf8 = cache_utf8.get_cached_utf8
1172
self.check_header(fp)
1173
# readlines reads the whole file at once:
1174
# bad for transports like http, good for local disk
1175
# we save 60 ms doing this one change (
1176
# from calling readline each time to calling
1178
# probably what we want for nice behaviour on
1179
# http is a incremental readlines that yields, or
1180
# a check for local vs non local indexes,
1181
history_top = len(history) - 1
1182
for line in fp.readlines():
1184
if len(rec) < 5 or rec[-1] != ':':
1186
# FIXME: in the future we should determine if its a
1187
# short write - and ignore it
1188
# or a different failure, and raise. RBC 20060407
1192
for value in rec[4:-1]:
1194
# uncompressed reference
1195
parent_id = get_cached_utf8(value[1:])
1197
parent_id = history[int(value)]
1198
parents.append(parent_id)
1200
version_id, options, pos, size = rec[:4]
1201
version_id = get_cached_utf8(version_id)
1203
# See self._cache_version
1204
# only want the _history index to reference the 1st
1205
# index entry for version_id
1206
if version_id not in cache:
1209
history.append(version_id)
1211
index = cache[version_id][5]
1212
cache[version_id] = (version_id,
1218
# end self._cache_version
1220
def get_graph(self):
1221
return [(vid, idx[4]) for vid, idx in self._cache.iteritems()]
1223
def get_ancestry(self, versions):
1224
"""See VersionedFile.get_ancestry."""
1225
# get a graph of all the mentioned versions:
1227
pending = set(versions)
1230
version = pending.pop()
1233
parents = [p for p in cache[version][4] if p in cache]
1235
raise RevisionNotPresent(version, self._filename)
1236
# if not completed and not a ghost
1237
pending.update([p for p in parents if p not in graph])
1238
graph[version] = parents
1239
return topo_sort(graph.items())
1241
def get_ancestry_with_ghosts(self, versions):
1242
"""See VersionedFile.get_ancestry_with_ghosts."""
1243
# get a graph of all the mentioned versions:
1244
self.check_versions_present(versions)
1247
pending = set(versions)
1249
version = pending.pop()
1251
parents = cache[version][4]
1257
pending.update([p for p in parents if p not in graph])
1258
graph[version] = parents
1259
return topo_sort(graph.items())
1261
def num_versions(self):
1262
return len(self._history)
1264
__len__ = num_versions
1266
def get_versions(self):
1267
return self._history
1269
def idx_to_name(self, idx):
1270
return self._history[idx]
1272
def lookup(self, version_id):
1273
assert version_id in self._cache
1274
return self._cache[version_id][5]
1276
def _version_list_to_index(self, versions):
1277
# TODO: jam 20070209 We only do the caching thing to make sure that
1278
# what we have in memory is already a proper utf-8 string
1279
# Eventually we should be able to write out the index without
1280
# doing any sort of encode step
1281
get_cached_utf8 = cache_utf8.get_cached_utf8
1284
for version in versions:
1285
if version in cache:
1286
# -- inlined lookup() --
1287
result_list.append(str(cache[version][5]))
1288
# -- end lookup () --
1290
result_list.append('.' + get_cached_utf8(version))
1291
return ' '.join(result_list)
1293
def add_version(self, version_id, options, pos, size, parents):
1294
"""Add a version record to the index."""
1295
self.add_versions(((version_id, options, pos, size, parents),))
1297
def add_versions(self, versions):
1298
"""Add multiple versions to the index.
1300
:param versions: a list of tuples:
1301
(version_id, options, pos, size, parents).
1304
# TODO: jam 20070209 get_cached_utf8 is just used to verify the
1305
# version_ids are indeed utf-8 eventually these calls can be
1307
get_cached_utf8 = cache_utf8.get_cached_utf8
1308
orig_history = self._history[:]
1309
orig_cache = self._cache.copy()
1312
for version_id, options, pos, size, parents in versions:
1313
line = "\n%s %s %s %s %s :" % (get_cached_utf8(version_id),
1317
self._version_list_to_index(parents))
1318
assert isinstance(line, str), \
1319
'content must be utf-8 encoded: %r' % (line,)
1321
self._cache_version(version_id, options, pos, size, parents)
1322
if not self._need_to_create:
1323
self._transport.append_bytes(self._filename, ''.join(lines))
1326
sio.write(self.HEADER)
1327
sio.writelines(lines)
1329
self._transport.put_file_non_atomic(self._filename, sio,
1330
create_parent_dir=self._create_parent_dir,
1331
mode=self._file_mode,
1332
dir_mode=self._dir_mode)
1333
self._need_to_create = False
1335
# If any problems happen, restore the original values and re-raise
1336
self._history = orig_history
1337
self._cache = orig_cache
1340
def has_version(self, version_id):
1341
"""True if the version is in the index."""
1342
return version_id in self._cache
1344
def get_position(self, version_id):
1345
"""Return data position and size of specified version."""
1346
entry = self._cache[version_id]
1347
return entry[2], entry[3]
1349
def get_method(self, version_id):
1350
"""Return compression method of specified version."""
1351
options = self._cache[version_id][1]
1352
if 'fulltext' in options:
1355
if 'line-delta' not in options:
1356
raise errors.KnitIndexUnknownMethod(self._full_path(), options)
1359
def get_options(self, version_id):
1360
return self._cache[version_id][1]
1362
def get_parents(self, version_id):
1363
"""Return parents of specified version ignoring ghosts."""
1364
return [parent for parent in self._cache[version_id][4]
1365
if parent in self._cache]
1367
def get_parents_with_ghosts(self, version_id):
1368
"""Return parents of specified version with ghosts."""
1369
return self._cache[version_id][4]
1371
def check_versions_present(self, version_ids):
1372
"""Check that all specified versions are present."""
1374
for version_id in version_ids:
1375
if version_id not in cache:
1376
raise RevisionNotPresent(version_id, self._filename)
1379
class _KnitData(_KnitComponentFile):
1380
"""Contents of the knit data file"""
1382
def __init__(self, transport, filename, mode, create=False, file_mode=None,
1383
create_parent_dir=False, delay_create=False,
1385
_KnitComponentFile.__init__(self, transport, filename, mode,
1386
file_mode=file_mode,
1387
create_parent_dir=create_parent_dir,
1389
self._checked = False
1390
# TODO: jam 20060713 conceptually, this could spill to disk
1391
# if the cached size gets larger than a certain amount
1392
# but it complicates the model a bit, so for now just use
1393
# a simple dictionary
1395
self._do_cache = False
1398
self._need_to_create = create
1400
self._transport.put_bytes_non_atomic(self._filename, '',
1401
mode=self._file_mode)
1403
def enable_cache(self):
1404
"""Enable caching of reads."""
1405
self._do_cache = True
1407
def clear_cache(self):
1408
"""Clear the record cache."""
1409
self._do_cache = False
1412
def _open_file(self):
1414
return self._transport.get(self._filename)
1419
def _record_to_data(self, version_id, digest, lines):
1420
"""Convert version_id, digest, lines into a raw data block.
1422
:return: (len, a StringIO instance with the raw data ready to read.)
1425
data_file = GzipFile(None, mode='wb', fileobj=sio)
1427
version_id_utf8 = cache_utf8.get_cached_utf8(version_id)
1428
data_file.writelines(chain(
1429
["version %s %d %s\n" % (version_id_utf8,
1433
["end %s\n" % version_id_utf8]))
1440
def add_raw_record(self, raw_data):
1441
"""Append a prepared record to the data file.
1443
:return: the offset in the data file raw_data was written.
1445
assert isinstance(raw_data, str), 'data must be plain bytes'
1446
if not self._need_to_create:
1447
return self._transport.append_bytes(self._filename, raw_data)
1449
self._transport.put_bytes_non_atomic(self._filename, raw_data,
1450
create_parent_dir=self._create_parent_dir,
1451
mode=self._file_mode,
1452
dir_mode=self._dir_mode)
1453
self._need_to_create = False
1456
def add_record(self, version_id, digest, lines):
1457
"""Write new text record to disk. Returns the position in the
1458
file where it was written."""
1459
size, sio = self._record_to_data(version_id, digest, lines)
1461
if not self._need_to_create:
1462
start_pos = self._transport.append_file(self._filename, sio)
1464
self._transport.put_file_non_atomic(self._filename, sio,
1465
create_parent_dir=self._create_parent_dir,
1466
mode=self._file_mode,
1467
dir_mode=self._dir_mode)
1468
self._need_to_create = False
1471
self._cache[version_id] = sio.getvalue()
1472
return start_pos, size
1474
def _parse_record_header(self, version_id, raw_data):
1475
"""Parse a record header for consistency.
1477
:return: the header and the decompressor stream.
1478
as (stream, header_record)
1480
df = GzipFile(mode='rb', fileobj=StringIO(raw_data))
1481
rec = self._check_header(version_id, df.readline())
1484
def _check_header(self, version_id, line):
1487
raise KnitCorrupt(self._filename,
1488
'unexpected number of elements in record header')
1489
if rec[1] != version_id:
1490
raise KnitCorrupt(self._filename,
1491
'unexpected version, wanted %r, got %r'
1492
% (version_id, rec[1]))
1495
def _parse_record(self, version_id, data):
1497
# 4168 calls in 2880 217 internal
1498
# 4168 calls to _parse_record_header in 2121
1499
# 4168 calls to readlines in 330
1500
df = GzipFile(mode='rb', fileobj=StringIO(data))
1502
record_contents = df.readlines()
1503
header = record_contents.pop(0)
1504
rec = self._check_header(version_id, header)
1506
last_line = record_contents.pop()
1507
assert len(record_contents) == int(rec[2])
1508
if last_line != 'end %s\n' % rec[1]:
1509
raise KnitCorrupt(self._filename,
1510
'unexpected version end line %r, wanted %r'
1511
% (last_line, version_id))
1513
return record_contents, rec[3]
1515
def read_records_iter_raw(self, records):
1516
"""Read text records from data file and yield raw data.
1518
This unpacks enough of the text record to validate the id is
1519
as expected but thats all.
1521
# setup an iterator of the external records:
1522
# uses readv so nice and fast we hope.
1524
# grab the disk data needed.
1526
# Don't check _cache if it is empty
1527
needed_offsets = [(pos, size) for version_id, pos, size
1529
if version_id not in self._cache]
1531
needed_offsets = [(pos, size) for version_id, pos, size
1534
raw_records = self._transport.readv(self._filename, needed_offsets)
1536
for version_id, pos, size in records:
1537
if version_id in self._cache:
1538
# This data has already been validated
1539
data = self._cache[version_id]
1541
pos, data = raw_records.next()
1543
self._cache[version_id] = data
1545
# validate the header
1546
df, rec = self._parse_record_header(version_id, data)
1548
yield version_id, data
1550
def read_records_iter(self, records):
1551
"""Read text records from data file and yield result.
1553
The result will be returned in whatever is the fastest to read.
1554
Not by the order requested. Also, multiple requests for the same
1555
record will only yield 1 response.
1556
:param records: A list of (version_id, pos, len) entries
1557
:return: Yields (version_id, contents, digest) in the order
1558
read, not the order requested
1564
# Skip records we have alread seen
1565
yielded_records = set()
1566
needed_records = set()
1567
for record in records:
1568
if record[0] in self._cache:
1569
if record[0] in yielded_records:
1571
yielded_records.add(record[0])
1572
data = self._cache[record[0]]
1573
content, digest = self._parse_record(record[0], data)
1574
yield (record[0], content, digest)
1576
needed_records.add(record)
1577
needed_records = sorted(needed_records, key=operator.itemgetter(1))
1579
needed_records = sorted(set(records), key=operator.itemgetter(1))
1581
if not needed_records:
1584
# The transport optimizes the fetching as well
1585
# (ie, reads continuous ranges.)
1586
readv_response = self._transport.readv(self._filename,
1587
[(pos, size) for version_id, pos, size in needed_records])
1589
for (version_id, pos, size), (pos, data) in \
1590
izip(iter(needed_records), readv_response):
1591
content, digest = self._parse_record(version_id, data)
1593
self._cache[version_id] = data
1594
yield version_id, content, digest
1596
def read_records(self, records):
1597
"""Read records into a dictionary."""
1599
for record_id, content, digest in \
1600
self.read_records_iter(records):
1601
components[record_id] = (content, digest)
1605
class InterKnit(InterVersionedFile):
1606
"""Optimised code paths for knit to knit operations."""
1608
_matching_file_from_factory = KnitVersionedFile
1609
_matching_file_to_factory = KnitVersionedFile
1612
def is_compatible(source, target):
1613
"""Be compatible with knits. """
1615
return (isinstance(source, KnitVersionedFile) and
1616
isinstance(target, KnitVersionedFile))
1617
except AttributeError:
1620
def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
1621
"""See InterVersionedFile.join."""
1622
assert isinstance(self.source, KnitVersionedFile)
1623
assert isinstance(self.target, KnitVersionedFile)
1625
version_ids = self._get_source_version_ids(version_ids, ignore_missing)
1630
pb = ui.ui_factory.nested_progress_bar()
1632
version_ids = list(version_ids)
1633
if None in version_ids:
1634
version_ids.remove(None)
1636
self.source_ancestry = set(self.source.get_ancestry(version_ids))
1637
this_versions = set(self.target._index.get_versions())
1638
needed_versions = self.source_ancestry - this_versions
1639
cross_check_versions = self.source_ancestry.intersection(this_versions)
1640
mismatched_versions = set()
1641
for version in cross_check_versions:
1642
# scan to include needed parents.
1643
n1 = set(self.target.get_parents_with_ghosts(version))
1644
n2 = set(self.source.get_parents_with_ghosts(version))
1646
# FIXME TEST this check for cycles being introduced works
1647
# the logic is we have a cycle if in our graph we are an
1648
# ancestor of any of the n2 revisions.
1654
parent_ancestors = self.source.get_ancestry(parent)
1655
if version in parent_ancestors:
1656
raise errors.GraphCycleError([parent, version])
1657
# ensure this parent will be available later.
1658
new_parents = n2.difference(n1)
1659
needed_versions.update(new_parents.difference(this_versions))
1660
mismatched_versions.add(version)
1662
if not needed_versions and not mismatched_versions:
1664
full_list = topo_sort(self.source.get_graph())
1666
version_list = [i for i in full_list if (not self.target.has_version(i)
1667
and i in needed_versions)]
1671
copy_queue_records = []
1673
for version_id in version_list:
1674
options = self.source._index.get_options(version_id)
1675
parents = self.source._index.get_parents_with_ghosts(version_id)
1676
# check that its will be a consistent copy:
1677
for parent in parents:
1678
# if source has the parent, we must :
1679
# * already have it or
1680
# * have it scheduled already
1681
# otherwise we don't care
1682
assert (self.target.has_version(parent) or
1683
parent in copy_set or
1684
not self.source.has_version(parent))
1685
data_pos, data_size = self.source._index.get_position(version_id)
1686
copy_queue_records.append((version_id, data_pos, data_size))
1687
copy_queue.append((version_id, options, parents))
1688
copy_set.add(version_id)
1690
# data suck the join:
1692
total = len(version_list)
1695
for (version_id, raw_data), \
1696
(version_id2, options, parents) in \
1697
izip(self.source._data.read_records_iter_raw(copy_queue_records),
1699
assert version_id == version_id2, 'logic error, inconsistent results'
1701
pb.update("Joining knit", count, total)
1702
raw_records.append((version_id, options, parents, len(raw_data)))
1703
raw_datum.append(raw_data)
1704
self.target._add_raw_records(raw_records, ''.join(raw_datum))
1706
for version in mismatched_versions:
1707
# FIXME RBC 20060309 is this needed?
1708
n1 = set(self.target.get_parents_with_ghosts(version))
1709
n2 = set(self.source.get_parents_with_ghosts(version))
1710
# write a combined record to our history preserving the current
1711
# parents as first in the list
1712
new_parents = self.target.get_parents_with_ghosts(version) + list(n2.difference(n1))
1713
self.target.fix_parents(version, new_parents)
1719
InterVersionedFile.register_optimiser(InterKnit)
1722
class WeaveToKnit(InterVersionedFile):
1723
"""Optimised code paths for weave to knit operations."""
1725
_matching_file_from_factory = bzrlib.weave.WeaveFile
1726
_matching_file_to_factory = KnitVersionedFile
1729
def is_compatible(source, target):
1730
"""Be compatible with weaves to knits."""
1732
return (isinstance(source, bzrlib.weave.Weave) and
1733
isinstance(target, KnitVersionedFile))
1734
except AttributeError:
1737
def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
1738
"""See InterVersionedFile.join."""
1739
assert isinstance(self.source, bzrlib.weave.Weave)
1740
assert isinstance(self.target, KnitVersionedFile)
1742
version_ids = self._get_source_version_ids(version_ids, ignore_missing)
1747
pb = ui.ui_factory.nested_progress_bar()
1749
version_ids = list(version_ids)
1751
self.source_ancestry = set(self.source.get_ancestry(version_ids))
1752
this_versions = set(self.target._index.get_versions())
1753
needed_versions = self.source_ancestry - this_versions
1754
cross_check_versions = self.source_ancestry.intersection(this_versions)
1755
mismatched_versions = set()
1756
for version in cross_check_versions:
1757
# scan to include needed parents.
1758
n1 = set(self.target.get_parents_with_ghosts(version))
1759
n2 = set(self.source.get_parents(version))
1760
# if all of n2's parents are in n1, then its fine.
1761
if n2.difference(n1):
1762
# FIXME TEST this check for cycles being introduced works
1763
# the logic is we have a cycle if in our graph we are an
1764
# ancestor of any of the n2 revisions.
1770
parent_ancestors = self.source.get_ancestry(parent)
1771
if version in parent_ancestors:
1772
raise errors.GraphCycleError([parent, version])
1773
# ensure this parent will be available later.
1774
new_parents = n2.difference(n1)
1775
needed_versions.update(new_parents.difference(this_versions))
1776
mismatched_versions.add(version)
1778
if not needed_versions and not mismatched_versions:
1780
full_list = topo_sort(self.source.get_graph())
1782
version_list = [i for i in full_list if (not self.target.has_version(i)
1783
and i in needed_versions)]
1787
total = len(version_list)
1788
for version_id in version_list:
1789
pb.update("Converting to knit", count, total)
1790
parents = self.source.get_parents(version_id)
1791
# check that its will be a consistent copy:
1792
for parent in parents:
1793
# if source has the parent, we must already have it
1794
assert (self.target.has_version(parent))
1795
self.target.add_lines(
1796
version_id, parents, self.source.get_lines(version_id))
1799
for version in mismatched_versions:
1800
# FIXME RBC 20060309 is this needed?
1801
n1 = set(self.target.get_parents_with_ghosts(version))
1802
n2 = set(self.source.get_parents(version))
1803
# write a combined record to our history preserving the current
1804
# parents as first in the list
1805
new_parents = self.target.get_parents_with_ghosts(version) + list(n2.difference(n1))
1806
self.target.fix_parents(version, new_parents)
1812
InterVersionedFile.register_optimiser(WeaveToKnit)
1815
class KnitSequenceMatcher(difflib.SequenceMatcher):
1816
"""Knit tuned sequence matcher.
1818
This is based on profiling of difflib which indicated some improvements
1819
for our usage pattern.
1822
def find_longest_match(self, alo, ahi, blo, bhi):
1823
"""Find longest matching block in a[alo:ahi] and b[blo:bhi].
1825
If isjunk is not defined:
1827
Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
1828
alo <= i <= i+k <= ahi
1829
blo <= j <= j+k <= bhi
1830
and for all (i',j',k') meeting those conditions,
1833
and if i == i', j <= j'
1835
In other words, of all maximal matching blocks, return one that
1836
starts earliest in a, and of all those maximal matching blocks that
1837
start earliest in a, return the one that starts earliest in b.
1839
>>> s = SequenceMatcher(None, " abcd", "abcd abcd")
1840
>>> s.find_longest_match(0, 5, 0, 9)
1843
If isjunk is defined, first the longest matching block is
1844
determined as above, but with the additional restriction that no
1845
junk element appears in the block. Then that block is extended as
1846
far as possible by matching (only) junk elements on both sides. So
1847
the resulting block never matches on junk except as identical junk
1848
happens to be adjacent to an "interesting" match.
1850
Here's the same example as before, but considering blanks to be
1851
junk. That prevents " abcd" from matching the " abcd" at the tail
1852
end of the second sequence directly. Instead only the "abcd" can
1853
match, and matches the leftmost "abcd" in the second sequence:
1855
>>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
1856
>>> s.find_longest_match(0, 5, 0, 9)
1859
If no blocks match, return (alo, blo, 0).
1861
>>> s = SequenceMatcher(None, "ab", "c")
1862
>>> s.find_longest_match(0, 2, 0, 1)
1866
# CAUTION: stripping common prefix or suffix would be incorrect.
1870
# Longest matching block is "ab", but if common prefix is
1871
# stripped, it's "a" (tied with "b"). UNIX(tm) diff does so
1872
# strip, so ends up claiming that ab is changed to acab by
1873
# inserting "ca" in the middle. That's minimal but unintuitive:
1874
# "it's obvious" that someone inserted "ac" at the front.
1875
# Windiff ends up at the same place as diff, but by pairing up
1876
# the unique 'b's and then matching the first two 'a's.
1878
a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.isbjunk
1879
besti, bestj, bestsize = alo, blo, 0
1880
# find longest junk-free match
1881
# during an iteration of the loop, j2len[j] = length of longest
1882
# junk-free match ending with a[i-1] and b[j]
1886
for i in xrange(alo, ahi):
1887
# look at all instances of a[i] in b; note that because
1888
# b2j has no junk keys, the loop is skipped if a[i] is junk
1889
j2lenget = j2len.get
1892
# changing b2j.get(a[i], nothing) to a try:KeyError pair produced the
1893
# following improvement
1894
# 704 0 4650.5320 2620.7410 bzrlib.knit:1336(find_longest_match)
1895
# +326674 0 1655.1210 1655.1210 +<method 'get' of 'dict' objects>
1896
# +76519 0 374.6700 374.6700 +<method 'has_key' of 'dict' objects>
1898
# 704 0 3733.2820 2209.6520 bzrlib.knit:1336(find_longest_match)
1899
# +211400 0 1147.3520 1147.3520 +<method 'get' of 'dict' objects>
1900
# +76519 0 376.2780 376.2780 +<method 'has_key' of 'dict' objects>
1912
k = newj2len[j] = 1 + j2lenget(-1 + j, 0)
1914
besti, bestj, bestsize = 1 + i-k, 1 + j-k, k
1917
# Extend the best by non-junk elements on each end. In particular,
1918
# "popular" non-junk elements aren't in b2j, which greatly speeds
1919
# the inner loop above, but also means "the best" match so far
1920
# doesn't contain any junk *or* popular non-junk elements.
1921
while besti > alo and bestj > blo and \
1922
not isbjunk(b[bestj-1]) and \
1923
a[besti-1] == b[bestj-1]:
1924
besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
1925
while besti+bestsize < ahi and bestj+bestsize < bhi and \
1926
not isbjunk(b[bestj+bestsize]) and \
1927
a[besti+bestsize] == b[bestj+bestsize]:
1930
# Now that we have a wholly interesting match (albeit possibly
1931
# empty!), we may as well suck up the matching junk on each
1932
# side of it too. Can't think of a good reason not to, and it
1933
# saves post-processing the (possibly considerable) expense of
1934
# figuring out what to do with it. In the case of an empty
1935
# interesting match, this is clearly the right thing to do,
1936
# because no other kind of match is possible in the regions.
1937
while besti > alo and bestj > blo and \
1938
isbjunk(b[bestj-1]) and \
1939
a[besti-1] == b[bestj-1]:
1940
besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
1941
while besti+bestsize < ahi and bestj+bestsize < bhi and \
1942
isbjunk(b[bestj+bestsize]) and \
1943
a[besti+bestsize] == b[bestj+bestsize]:
1944
bestsize = bestsize + 1
1946
return besti, bestj, bestsize
added
removed
bzrlib/knit.py
