1
# Copyright (C) 2005, 2006 by Canonical Ltd
2
# Written by Martin Pool.
3
# Modified by Johan Rydberg <jrydberg@gnu.org>
4
# Modified by Robert Collins <robert.collins@canonical.com>
5
# Modified by Aaron Bentley <aaron.bentley@utoronto.ca>
7
# This program is free software; you can redistribute it and/or modify
8
# it under the terms of the GNU General Public License as published by
9
# the Free Software Foundation; either version 2 of the License, or
10
# (at your option) any later version.
12
# This program is distributed in the hope that it will be useful,
13
# but WITHOUT ANY WARRANTY; without even the implied warranty of
14
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15
# GNU General Public License for more details.
17
# You should have received a copy of the GNU General Public License
18
# along with this program; if not, write to the Free Software
19
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21
"""Knit versionedfile implementation.
23
A knit is a versioned file implementation that supports efficient append only
27
lifeless: the data file is made up of "delta records". each delta record has a delta header
28
that contains; (1) a version id, (2) the size of the delta (in lines), and (3) the digest of
29
the -expanded data- (ie, the delta applied to the parent). the delta also ends with a
30
end-marker; simply "end VERSION"
32
delta can be line or full contents.a
33
... the 8's there are the index number of the annotation.
34
version robertc@robertcollins.net-20051003014215-ee2990904cc4c7ad 7 c7d23b2a5bd6ca00e8e266cec0ec228158ee9f9e
38
8 e.set('executable', 'yes')
40
8 if elt.get('executable') == 'yes':
41
8 ie.executable = True
42
end robertc@robertcollins.net-20051003014215-ee2990904cc4c7ad
46
09:33 < jrydberg> lifeless: each index is made up of a tuple of; version id, options, position, size, parents
47
09:33 < jrydberg> lifeless: the parents are currently dictionary compressed
48
09:33 < jrydberg> lifeless: (meaning it currently does not support ghosts)
49
09:33 < lifeless> right
50
09:33 < jrydberg> lifeless: the position and size is the range in the data file
53
so the index sequence is the dictionary compressed sequence number used
54
in the deltas to provide line annotation
59
# 10:16 < lifeless> make partial index writes safe
60
# 10:16 < lifeless> implement 'knit.check()' like weave.check()
61
# 10:17 < lifeless> record known ghosts so we can detect when they are filled in rather than the current 'reweave
63
# move sha1 out of the content so that join is faster at verifying parents
64
# record content length ?
68
from cStringIO import StringIO
70
from itertools import izip, chain
77
import bzrlib.errors as errors
78
from bzrlib.errors import FileExists, NoSuchFile, KnitError, \
79
InvalidRevisionId, KnitCorrupt, KnitHeaderError, \
80
RevisionNotPresent, RevisionAlreadyPresent
81
from bzrlib.tuned_gzip import GzipFile
82
from bzrlib.trace import mutter
83
from bzrlib.osutils import contains_whitespace, contains_linebreaks, \
85
from bzrlib.versionedfile import VersionedFile, InterVersionedFile
86
from bzrlib.symbol_versioning import DEPRECATED_PARAMETER, deprecated_passed
87
from bzrlib.tsort import topo_sort
91
# TODO: Split out code specific to this format into an associated object.
93
# TODO: Can we put in some kind of value to check that the index and data
94
# files belong together?
96
# TODO: accommodate binaries, perhaps by storing a byte count
98
# TODO: function to check whole file
100
# TODO: atomically append data, then measure backwards from the cursor
101
# position after writing to work out where it was located. we may need to
102
# bypass python file buffering.
104
DATA_SUFFIX = '.knit'
105
INDEX_SUFFIX = '.kndx'
108
class KnitContent(object):
109
"""Content of a knit version to which deltas can be applied."""
111
def __init__(self, lines):
114
def annotate_iter(self):
115
"""Yield tuples of (origin, text) for each content line."""
116
for origin, text in self._lines:
120
"""Return a list of (origin, text) tuples."""
121
return list(self.annotate_iter())
123
def line_delta_iter(self, new_lines):
124
"""Generate line-based delta from this content to new_lines."""
125
new_texts = [text for origin, text in new_lines._lines]
126
old_texts = [text for origin, text in self._lines]
127
s = KnitSequenceMatcher(None, old_texts, new_texts)
128
for op in s.get_opcodes():
131
# ofrom oto length data
132
yield (op[1], op[2], op[4]-op[3], new_lines._lines[op[3]:op[4]])
134
def line_delta(self, new_lines):
135
return list(self.line_delta_iter(new_lines))
138
return [text for origin, text in self._lines]
141
return KnitContent(self._lines[:])
144
class _KnitFactory(object):
145
"""Base factory for creating content objects."""
147
def make(self, lines, version):
148
num_lines = len(lines)
149
return KnitContent(zip([version] * num_lines, lines))
152
class KnitAnnotateFactory(_KnitFactory):
153
"""Factory for creating annotated Content objects."""
157
def parse_fulltext(self, content, version):
158
"""Convert fulltext to internal representation
160
fulltext content is of the format
161
revid(utf8) plaintext\n
162
internal representation is of the format:
167
origin, text = line.split(' ', 1)
168
lines.append((origin.decode('utf-8'), text))
169
return KnitContent(lines)
171
def parse_line_delta_iter(self, lines):
172
for result_item in self.parse_line_delta[lines]:
175
def parse_line_delta(self, lines, version):
176
"""Convert a line based delta into internal representation.
178
line delta is in the form of:
179
intstart intend intcount
181
revid(utf8) newline\n
182
internal representation is
183
(start, end, count, [1..count tuples (revid, newline)])
188
# walk through the lines parsing.
190
start, end, count = [int(n) for n in header.split(',')]
194
origin, text = next().split(' ', 1)
196
contents.append((origin.decode('utf-8'), text))
197
result.append((start, end, count, contents))
200
def lower_fulltext(self, content):
201
"""convert a fulltext content record into a serializable form.
203
see parse_fulltext which this inverts.
205
return ['%s %s' % (o.encode('utf-8'), t) for o, t in content._lines]
207
def lower_line_delta(self, delta):
208
"""convert a delta into a serializable form.
210
See parse_line_delta which this inverts.
213
for start, end, c, lines in delta:
214
out.append('%d,%d,%d\n' % (start, end, c))
215
for origin, text in lines:
216
out.append('%s %s' % (origin.encode('utf-8'), text))
220
class KnitPlainFactory(_KnitFactory):
221
"""Factory for creating plain Content objects."""
225
def parse_fulltext(self, content, version):
226
"""This parses an unannotated fulltext.
228
Note that this is not a noop - the internal representation
229
has (versionid, line) - its just a constant versionid.
231
return self.make(content, version)
233
def parse_line_delta_iter(self, lines, version):
235
header = lines.pop(0)
236
start, end, c = [int(n) for n in header.split(',')]
237
yield start, end, c, zip([version] * c, lines[:c])
240
def parse_line_delta(self, lines, version):
241
return list(self.parse_line_delta_iter(lines, version))
243
def lower_fulltext(self, content):
244
return content.text()
246
def lower_line_delta(self, delta):
248
for start, end, c, lines in delta:
249
out.append('%d,%d,%d\n' % (start, end, c))
250
out.extend([text for origin, text in lines])
254
def make_empty_knit(transport, relpath):
255
"""Construct a empty knit at the specified location."""
256
k = KnitVersionedFile(transport, relpath, 'w', KnitPlainFactory)
260
class KnitVersionedFile(VersionedFile):
261
"""Weave-like structure with faster random access.
263
A knit stores a number of texts and a summary of the relationships
264
between them. Texts are identified by a string version-id. Texts
265
are normally stored and retrieved as a series of lines, but can
266
also be passed as single strings.
268
Lines are stored with the trailing newline (if any) included, to
269
avoid special cases for files with no final newline. Lines are
270
composed of 8-bit characters, not unicode. The combination of
271
these approaches should mean any 'binary' file can be safely
272
stored and retrieved.
275
def __init__(self, relpath, transport, file_mode=None, access_mode=None,
276
factory=None, basis_knit=DEPRECATED_PARAMETER, delta=True,
278
"""Construct a knit at location specified by relpath.
280
:param create: If not True, only open an existing knit.
282
if deprecated_passed(basis_knit):
283
warnings.warn("KnitVersionedFile.__(): The basis_knit parameter is"
284
" deprecated as of bzr 0.9.",
285
DeprecationWarning, stacklevel=2)
286
if access_mode is None:
288
super(KnitVersionedFile, self).__init__(access_mode)
289
assert access_mode in ('r', 'w'), "invalid mode specified %r" % access_mode
290
self.transport = transport
291
self.filename = relpath
292
self.factory = factory or KnitAnnotateFactory()
293
self.writable = (access_mode == 'w')
296
self._index = _KnitIndex(transport, relpath + INDEX_SUFFIX,
297
access_mode, create=create, file_mode=file_mode)
298
self._data = _KnitData(transport, relpath + DATA_SUFFIX,
299
access_mode, create=create and not len(self), file_mode=file_mode)
302
return '%s(%s)' % (self.__class__.__name__,
303
self.transport.abspath(self.filename))
305
def _add_delta(self, version_id, parents, delta_parent, sha1, noeol, delta):
306
"""See VersionedFile._add_delta()."""
307
self._check_add(version_id, []) # should we check the lines ?
308
self._check_versions_present(parents)
312
for parent in parents:
313
if not self.has_version(parent):
314
ghosts.append(parent)
316
present_parents.append(parent)
318
if delta_parent is None:
319
# reconstitute as full text.
320
assert len(delta) == 1 or len(delta) == 0
322
assert delta[0][0] == 0
323
assert delta[0][1] == 0, delta[0][1]
324
return super(KnitVersionedFile, self)._add_delta(version_id,
335
options.append('no-eol')
337
if delta_parent is not None:
338
# determine the current delta chain length.
339
# To speed the extract of texts the delta chain is limited
340
# to a fixed number of deltas. This should minimize both
341
# I/O and the time spend applying deltas.
343
delta_parents = [delta_parent]
345
parent = delta_parents[0]
346
method = self._index.get_method(parent)
347
if method == 'fulltext':
349
delta_parents = self._index.get_parents(parent)
351
if method == 'line-delta':
352
# did not find a fulltext in the delta limit.
353
# just do a normal insertion.
354
return super(KnitVersionedFile, self)._add_delta(version_id,
361
options.append('line-delta')
362
store_lines = self.factory.lower_line_delta(delta)
364
where, size = self._data.add_record(version_id, digest, store_lines)
365
self._index.add_version(version_id, options, where, size, parents)
367
def _add_raw_records(self, records, data):
368
"""Add all the records 'records' with data pre-joined in 'data'.
370
:param records: A list of tuples(version_id, options, parents, size).
371
:param data: The data for the records. When it is written, the records
372
are adjusted to have pos pointing into data by the sum of
373
the preceding records sizes.
376
pos = self._data.add_raw_record(data)
378
for (version_id, options, parents, size) in records:
379
index_entries.append((version_id, options, pos, size, parents))
381
self._index.add_versions(index_entries)
383
def clear_cache(self):
384
"""Clear the data cache only."""
385
self._data.clear_cache()
387
def copy_to(self, name, transport):
388
"""See VersionedFile.copy_to()."""
389
# copy the current index to a temp index to avoid racing with local
391
transport.put(name + INDEX_SUFFIX + '.tmp', self.transport.get(self._index._filename),)
393
transport.put(name + DATA_SUFFIX, self._data._open_file())
394
# rename the copied index into place
395
transport.rename(name + INDEX_SUFFIX + '.tmp', name + INDEX_SUFFIX)
397
def create_empty(self, name, transport, mode=None):
398
return KnitVersionedFile(name, transport, factory=self.factory, delta=self.delta, create=True)
400
def _fix_parents(self, version, new_parents):
401
"""Fix the parents list for version.
403
This is done by appending a new version to the index
404
with identical data except for the parents list.
405
the parents list must be a superset of the current
408
current_values = self._index._cache[version]
409
assert set(current_values[4]).difference(set(new_parents)) == set()
410
self._index.add_version(version,
416
def get_delta(self, version_id):
417
"""Get a delta for constructing version from some other version."""
418
if not self.has_version(version_id):
419
raise RevisionNotPresent(version_id, self.filename)
421
parents = self.get_parents(version_id)
426
data_pos, data_size = self._index.get_position(version_id)
427
data, sha1 = self._data.read_records(((version_id, data_pos, data_size),))[version_id]
428
version_idx = self._index.lookup(version_id)
429
noeol = 'no-eol' in self._index.get_options(version_id)
430
if 'fulltext' == self._index.get_method(version_id):
431
new_content = self.factory.parse_fulltext(data, version_idx)
432
if parent is not None:
433
reference_content = self._get_content(parent)
434
old_texts = reference_content.text()
437
new_texts = new_content.text()
438
delta_seq = KnitSequenceMatcher(None, old_texts, new_texts)
439
return parent, sha1, noeol, self._make_line_delta(delta_seq, new_content)
441
delta = self.factory.parse_line_delta(data, version_idx)
442
return parent, sha1, noeol, delta
444
def get_graph_with_ghosts(self):
445
"""See VersionedFile.get_graph_with_ghosts()."""
446
graph_items = self._index.get_graph()
447
return dict(graph_items)
449
def get_sha1(self, version_id):
450
"""See VersionedFile.get_sha1()."""
451
record_map = self._get_record_map([version_id])
452
method, content, digest, next = record_map[version_id]
457
"""See VersionedFile.get_suffixes()."""
458
return [DATA_SUFFIX, INDEX_SUFFIX]
460
def has_ghost(self, version_id):
461
"""True if there is a ghost reference in the file to version_id."""
463
if self.has_version(version_id):
465
# optimisable if needed by memoising the _ghosts set.
466
items = self._index.get_graph()
467
for node, parents in items:
468
for parent in parents:
469
if parent not in self._index._cache:
470
if parent == version_id:
475
"""See VersionedFile.versions."""
476
return self._index.get_versions()
478
def has_version(self, version_id):
479
"""See VersionedFile.has_version."""
480
return self._index.has_version(version_id)
482
__contains__ = has_version
484
def _merge_annotations(self, content, parents, parent_texts={},
485
delta=None, annotated=None):
486
"""Merge annotations for content. This is done by comparing
487
the annotations based on changed to the text.
491
for parent_id in parents:
492
merge_content = self._get_content(parent_id, parent_texts)
493
seq = KnitSequenceMatcher(None, merge_content.text(), content.text())
494
if delta_seq is None:
495
# setup a delta seq to reuse.
497
for i, j, n in seq.get_matching_blocks():
500
# this appears to copy (origin, text) pairs across to the new
501
# content for any line that matches the last-checked parent.
502
# FIXME: save the sequence control data for delta compression
503
# against the most relevant parent rather than rediffing.
504
content._lines[j:j+n] = merge_content._lines[i:i+n]
507
reference_content = self._get_content(parents[0], parent_texts)
508
new_texts = content.text()
509
old_texts = reference_content.text()
510
delta_seq = KnitSequenceMatcher(None, old_texts, new_texts)
511
return self._make_line_delta(delta_seq, content)
513
def _make_line_delta(self, delta_seq, new_content):
514
"""Generate a line delta from delta_seq and new_content."""
516
for op in delta_seq.get_opcodes():
519
diff_hunks.append((op[1], op[2], op[4]-op[3], new_content._lines[op[3]:op[4]]))
522
def _get_components_positions(self, version_ids):
523
"""Produce a map of position data for the components of versions.
525
This data is intended to be used for retrieving the knit records.
527
A dict of version_id to (method, data_pos, data_size, next) is
529
method is the way referenced data should be applied.
530
data_pos is the position of the data in the knit.
531
data_size is the size of the data in the knit.
532
next is the build-parent of the version, or None for fulltexts.
535
for version_id in version_ids:
538
while cursor is not None and cursor not in component_data:
539
method = self._index.get_method(cursor)
540
if method == 'fulltext':
543
next = self.get_parents(cursor)[0]
544
data_pos, data_size = self._index.get_position(cursor)
545
component_data[cursor] = (method, data_pos, data_size, next)
547
return component_data
549
def _get_content(self, version_id, parent_texts={}):
550
"""Returns a content object that makes up the specified
552
if not self.has_version(version_id):
553
raise RevisionNotPresent(version_id, self.filename)
555
cached_version = parent_texts.get(version_id, None)
556
if cached_version is not None:
557
return cached_version
559
text_map, contents_map = self._get_content_maps([version_id])
560
return contents_map[version_id]
562
def _check_versions_present(self, version_ids):
563
"""Check that all specified versions are present."""
564
version_ids = set(version_ids)
565
for r in list(version_ids):
566
if self._index.has_version(r):
567
version_ids.remove(r)
569
raise RevisionNotPresent(list(version_ids)[0], self.filename)
571
def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts):
572
"""See VersionedFile.add_lines_with_ghosts()."""
573
self._check_add(version_id, lines)
574
return self._add(version_id, lines[:], parents, self.delta, parent_texts)
576
def _add_lines(self, version_id, parents, lines, parent_texts):
577
"""See VersionedFile.add_lines."""
578
self._check_add(version_id, lines)
579
self._check_versions_present(parents)
580
return self._add(version_id, lines[:], parents, self.delta, parent_texts)
582
def _check_add(self, version_id, lines):
583
"""check that version_id and lines are safe to add."""
584
assert self.writable, "knit is not opened for write"
585
### FIXME escape. RBC 20060228
586
if contains_whitespace(version_id):
587
raise InvalidRevisionId(version_id, self.filename)
588
if self.has_version(version_id):
589
raise RevisionAlreadyPresent(version_id, self.filename)
590
self._check_lines_not_unicode(lines)
591
self._check_lines_are_lines(lines)
593
def _add(self, version_id, lines, parents, delta, parent_texts):
594
"""Add a set of lines on top of version specified by parents.
596
If delta is true, compress the text as a line-delta against
599
Any versions not present will be converted into ghosts.
601
# 461 0 6546.0390 43.9100 bzrlib.knit:489(_add)
602
# +400 0 889.4890 418.9790 +bzrlib.knit:192(lower_fulltext)
603
# +461 0 1364.8070 108.8030 +bzrlib.knit:996(add_record)
604
# +461 0 193.3940 41.5720 +bzrlib.knit:898(add_version)
605
# +461 0 134.0590 18.3810 +bzrlib.osutils:361(sha_strings)
606
# +461 0 36.3420 15.4540 +bzrlib.knit:146(make)
607
# +1383 0 8.0370 8.0370 +<len>
608
# +61 0 13.5770 7.9190 +bzrlib.knit:199(lower_line_delta)
609
# +61 0 963.3470 7.8740 +bzrlib.knit:427(_get_content)
610
# +61 0 973.9950 5.2950 +bzrlib.knit:136(line_delta)
611
# +61 0 1918.1800 5.2640 +bzrlib.knit:359(_merge_annotations)
615
if parent_texts is None:
617
for parent in parents:
618
if not self.has_version(parent):
619
ghosts.append(parent)
621
present_parents.append(parent)
623
if delta and not len(present_parents):
626
digest = sha_strings(lines)
629
if lines[-1][-1] != '\n':
630
options.append('no-eol')
631
lines[-1] = lines[-1] + '\n'
633
if len(present_parents) and delta:
634
# To speed the extract of texts the delta chain is limited
635
# to a fixed number of deltas. This should minimize both
636
# I/O and the time spend applying deltas.
638
delta_parents = present_parents
640
parent = delta_parents[0]
641
method = self._index.get_method(parent)
642
if method == 'fulltext':
644
delta_parents = self._index.get_parents(parent)
646
if method == 'line-delta':
649
lines = self.factory.make(lines, version_id)
650
if delta or (self.factory.annotated and len(present_parents) > 0):
651
# Merge annotations from parent texts if so is needed.
652
delta_hunks = self._merge_annotations(lines, present_parents, parent_texts,
653
delta, self.factory.annotated)
656
options.append('line-delta')
657
store_lines = self.factory.lower_line_delta(delta_hunks)
659
options.append('fulltext')
660
store_lines = self.factory.lower_fulltext(lines)
662
where, size = self._data.add_record(version_id, digest, store_lines)
663
self._index.add_version(version_id, options, where, size, parents)
666
def check(self, progress_bar=None):
667
"""See VersionedFile.check()."""
669
def _clone_text(self, new_version_id, old_version_id, parents):
670
"""See VersionedFile.clone_text()."""
671
# FIXME RBC 20060228 make fast by only inserting an index with null
673
self.add_lines(new_version_id, parents, self.get_lines(old_version_id))
675
def get_lines(self, version_id):
676
"""See VersionedFile.get_lines()."""
677
return self.get_line_list([version_id])[0]
679
def _get_record_map(self, version_ids):
680
"""Produce a dictionary of knit records.
682
The keys are version_ids, the values are tuples of (method, content,
684
method is the way the content should be applied.
685
content is a KnitContent object.
686
digest is the SHA1 digest of this version id after all steps are done
687
next is the build-parent of the version, i.e. the leftmost ancestor.
688
If the method is fulltext, next will be None.
690
position_map = self._get_components_positions(version_ids)
691
# c = component_id, m = method, p = position, s = size, n = next
692
records = [(c, p, s) for c, (m, p, s, n) in position_map.iteritems()]
694
for component_id, content, digest in\
695
self._data.read_records_iter(records):
696
method, position, size, next = position_map[component_id]
697
record_map[component_id] = method, content, digest, next
701
def get_text(self, version_id):
702
"""See VersionedFile.get_text"""
703
return self.get_texts([version_id])[0]
705
def get_texts(self, version_ids):
706
return [''.join(l) for l in self.get_line_list(version_ids)]
708
def get_line_list(self, version_ids):
709
"""Return the texts of listed versions as a list of strings."""
710
text_map, content_map = self._get_content_maps(version_ids)
711
return [text_map[v] for v in version_ids]
713
def _get_content_maps(self, version_ids):
714
"""Produce maps of text and KnitContents
716
:return: (text_map, content_map) where text_map contains the texts for
717
the requested versions and content_map contains the KnitContents.
718
Both dicts take version_ids as their keys.
720
for version_id in version_ids:
721
if not self.has_version(version_id):
722
raise RevisionNotPresent(version_id, self.filename)
723
record_map = self._get_record_map(version_ids)
728
for version_id in version_ids:
731
while cursor is not None:
732
method, data, digest, next = record_map[cursor]
733
components.append((cursor, method, data, digest))
734
if cursor in content_map:
739
for component_id, method, data, digest in reversed(components):
740
if component_id in content_map:
741
content = content_map[component_id]
743
version_idx = self._index.lookup(component_id)
744
if method == 'fulltext':
745
assert content is None
746
content = self.factory.parse_fulltext(data, version_idx)
747
elif method == 'line-delta':
748
delta = self.factory.parse_line_delta(data[:],
750
content = content.copy()
751
content._lines = self._apply_delta(content._lines,
753
content_map[component_id] = content
755
if 'no-eol' in self._index.get_options(version_id):
756
content = content.copy()
757
line = content._lines[-1][1].rstrip('\n')
758
content._lines[-1] = (content._lines[-1][0], line)
759
final_content[version_id] = content
761
# digest here is the digest from the last applied component.
762
text = content.text()
763
if sha_strings(text) != digest:
764
raise KnitCorrupt(self.filename,
765
'sha-1 does not match %s' % version_id)
767
text_map[version_id] = text
768
return text_map, final_content
770
def iter_lines_added_or_present_in_versions(self, version_ids=None):
771
"""See VersionedFile.iter_lines_added_or_present_in_versions()."""
772
if version_ids is None:
773
version_ids = self.versions()
774
# we don't care about inclusions, the caller cares.
775
# but we need to setup a list of records to visit.
776
# we need version_id, position, length
777
version_id_records = []
778
requested_versions = list(version_ids)
779
# filter for available versions
780
for version_id in requested_versions:
781
if not self.has_version(version_id):
782
raise RevisionNotPresent(version_id, self.filename)
783
# get a in-component-order queue:
785
for version_id in self.versions():
786
if version_id in requested_versions:
787
version_ids.append(version_id)
788
data_pos, length = self._index.get_position(version_id)
789
version_id_records.append((version_id, data_pos, length))
791
pb = bzrlib.ui.ui_factory.nested_progress_bar()
793
total = len(version_id_records)
795
pb.update('Walking content.', count, total)
796
for version_id, data, sha_value in \
797
self._data.read_records_iter(version_id_records):
798
pb.update('Walking content.', count, total)
799
method = self._index.get_method(version_id)
800
version_idx = self._index.lookup(version_id)
801
assert method in ('fulltext', 'line-delta')
802
if method == 'fulltext':
803
content = self.factory.parse_fulltext(data, version_idx)
804
for line in content.text():
807
delta = self.factory.parse_line_delta(data, version_idx)
808
for start, end, count, lines in delta:
809
for origin, line in lines:
812
pb.update('Walking content.', total, total)
815
pb.update('Walking content.', total, total)
819
def num_versions(self):
820
"""See VersionedFile.num_versions()."""
821
return self._index.num_versions()
823
__len__ = num_versions
825
def annotate_iter(self, version_id):
826
"""See VersionedFile.annotate_iter."""
827
content = self._get_content(version_id)
828
for origin, text in content.annotate_iter():
831
def get_parents(self, version_id):
832
"""See VersionedFile.get_parents."""
835
# 52554 calls in 1264 872 internal down from 3674
837
return self._index.get_parents(version_id)
839
raise RevisionNotPresent(version_id, self.filename)
841
def get_parents_with_ghosts(self, version_id):
842
"""See VersionedFile.get_parents."""
844
return self._index.get_parents_with_ghosts(version_id)
846
raise RevisionNotPresent(version_id, self.filename)
848
def get_ancestry(self, versions):
849
"""See VersionedFile.get_ancestry."""
850
if isinstance(versions, basestring):
851
versions = [versions]
854
self._check_versions_present(versions)
855
return self._index.get_ancestry(versions)
857
def get_ancestry_with_ghosts(self, versions):
858
"""See VersionedFile.get_ancestry_with_ghosts."""
859
if isinstance(versions, basestring):
860
versions = [versions]
863
self._check_versions_present(versions)
864
return self._index.get_ancestry_with_ghosts(versions)
866
#@deprecated_method(zero_eight)
867
def walk(self, version_ids):
868
"""See VersionedFile.walk."""
869
# We take the short path here, and extract all relevant texts
870
# and put them in a weave and let that do all the work. Far
871
# from optimal, but is much simpler.
872
# FIXME RB 20060228 this really is inefficient!
873
from bzrlib.weave import Weave
875
w = Weave(self.filename)
876
ancestry = self.get_ancestry(version_ids)
877
sorted_graph = topo_sort(self._index.get_graph())
878
version_list = [vid for vid in sorted_graph if vid in ancestry]
880
for version_id in version_list:
881
lines = self.get_lines(version_id)
882
w.add_lines(version_id, self.get_parents(version_id), lines)
884
for lineno, insert_id, dset, line in w.walk(version_ids):
885
yield lineno, insert_id, dset, line
887
def plan_merge(self, ver_a, ver_b):
888
"""See VersionedFile.plan_merge."""
889
ancestors_b = set(self.get_ancestry(ver_b))
890
def status_a(revision, text):
891
if revision in ancestors_b:
892
return 'killed-b', text
896
ancestors_a = set(self.get_ancestry(ver_a))
897
def status_b(revision, text):
898
if revision in ancestors_a:
899
return 'killed-a', text
903
annotated_a = self.annotate(ver_a)
904
annotated_b = self.annotate(ver_b)
905
plain_a = [t for (a, t) in annotated_a]
906
plain_b = [t for (a, t) in annotated_b]
907
blocks = KnitSequenceMatcher(None, plain_a, plain_b).get_matching_blocks()
910
for ai, bi, l in blocks:
911
# process all mismatched sections
912
# (last mismatched section is handled because blocks always
913
# includes a 0-length last block)
914
for revision, text in annotated_a[a_cur:ai]:
915
yield status_a(revision, text)
916
for revision, text in annotated_b[b_cur:bi]:
917
yield status_b(revision, text)
919
# and now the matched section
922
for text_a, text_b in zip(plain_a[ai:a_cur], plain_b[bi:b_cur]):
923
assert text_a == text_b
924
yield "unchanged", text_a
927
class _KnitComponentFile(object):
928
"""One of the files used to implement a knit database"""
930
def __init__(self, transport, filename, mode, file_mode=None):
931
self._transport = transport
932
self._filename = filename
934
self._file_mode=file_mode
936
def write_header(self):
937
if self._transport.append(self._filename, StringIO(self.HEADER),
938
mode=self._file_mode):
939
raise KnitCorrupt(self._filename, 'misaligned after writing header')
941
def check_header(self, fp):
943
if line != self.HEADER:
944
raise KnitHeaderError(badline=line)
947
"""Commit is a nop."""
950
return '%s(%s)' % (self.__class__.__name__, self._filename)
953
class _KnitIndex(_KnitComponentFile):
954
"""Manages knit index file.
956
The index is already kept in memory and read on startup, to enable
957
fast lookups of revision information. The cursor of the index
958
file is always pointing to the end, making it easy to append
961
_cache is a cache for fast mapping from version id to a Index
964
_history is a cache for fast mapping from indexes to version ids.
966
The index data format is dictionary compressed when it comes to
967
parent references; a index entry may only have parents that with a
968
lover index number. As a result, the index is topological sorted.
970
Duplicate entries may be written to the index for a single version id
971
if this is done then the latter one completely replaces the former:
972
this allows updates to correct version and parent information.
973
Note that the two entries may share the delta, and that successive
974
annotations and references MUST point to the first entry.
976
The index file on disc contains a header, followed by one line per knit
977
record. The same revision can be present in an index file more than once.
978
The first occurrence gets assigned a sequence number starting from 0.
980
The format of a single line is
981
REVISION_ID FLAGS BYTE_OFFSET LENGTH( PARENT_ID|PARENT_SEQUENCE_ID)* :\n
982
REVISION_ID is a utf8-encoded revision id
983
FLAGS is a comma separated list of flags about the record. Values include
984
no-eol, line-delta, fulltext.
985
BYTE_OFFSET is the ascii representation of the byte offset in the data file
986
that the the compressed data starts at.
987
LENGTH is the ascii representation of the length of the data file.
988
PARENT_ID a utf-8 revision id prefixed by a '.' that is a parent of
990
PARENT_SEQUENCE_ID the ascii representation of the sequence number of a
991
revision id already in the knit that is a parent of REVISION_ID.
992
The ' :' marker is the end of record marker.
995
when a write is interrupted to the index file, it will result in a line that
996
does not end in ' :'. If the ' :' is not present at the end of a line, or at
997
the end of the file, then the record that is missing it will be ignored by
1000
When writing new records to the index file, the data is preceded by '\n'
1001
to ensure that records always start on new lines even if the last write was
1002
interrupted. As a result its normal for the last line in the index to be
1003
missing a trailing newline. One can be added with no harmful effects.
1006
HEADER = "# bzr knit index 8\n"
1008
# speed of knit parsing went from 280 ms to 280 ms with slots addition.
1009
# __slots__ = ['_cache', '_history', '_transport', '_filename']
1011
def _cache_version(self, version_id, options, pos, size, parents):
1012
"""Cache a version record in the history array and index cache.
1014
This is inlined into __init__ for performance. KEEP IN SYNC.
1015
(It saves 60ms, 25% of the __init__ overhead on local 4000 record
1018
# only want the _history index to reference the 1st index entry
1020
if version_id not in self._cache:
1021
index = len(self._history)
1022
self._history.append(version_id)
1024
index = self._cache[version_id][5]
1025
self._cache[version_id] = (version_id,
1032
def __init__(self, transport, filename, mode, create=False, file_mode=None):
1033
_KnitComponentFile.__init__(self, transport, filename, mode, file_mode)
1035
# position in _history is the 'official' index for a revision
1036
# but the values may have come from a newer entry.
1037
# so - wc -l of a knit index is != the number of unique names
1040
pb = bzrlib.ui.ui_factory.nested_progress_bar()
1045
pb.update('read knit index', count, total)
1046
fp = self._transport.get(self._filename)
1047
self.check_header(fp)
1048
# readlines reads the whole file at once:
1049
# bad for transports like http, good for local disk
1050
# we save 60 ms doing this one change (
1051
# from calling readline each time to calling
1053
# probably what we want for nice behaviour on
1054
# http is a incremental readlines that yields, or
1055
# a check for local vs non local indexes,
1056
for l in fp.readlines():
1058
if len(rec) < 5 or rec[-1] != ':':
1060
# FIXME: in the future we should determine if its a
1061
# short write - and ignore it
1062
# or a different failure, and raise. RBC 20060407
1066
#pb.update('read knit index', count, total)
1067
# See self._parse_parents
1069
for value in rec[4:-1]:
1071
# uncompressed reference
1072
parents.append(value[1:])
1074
# this is 15/4000ms faster than isinstance,
1076
# this function is called thousands of times a
1077
# second so small variations add up.
1078
assert value.__class__ is str
1079
parents.append(self._history[int(value)])
1080
# end self._parse_parents
1081
# self._cache_version(rec[0],
1082
# rec[1].split(','),
1086
# --- self._cache_version
1087
# only want the _history index to reference the 1st
1088
# index entry for version_id
1090
if version_id not in self._cache:
1091
index = len(self._history)
1092
self._history.append(version_id)
1094
index = self._cache[version_id][5]
1095
self._cache[version_id] = (version_id,
1101
# --- self._cache_version
1102
except NoSuchFile, e:
1103
if mode != 'w' or not create:
1107
pb.update('read knit index', total, total)
1110
def _parse_parents(self, compressed_parents):
1111
"""convert a list of string parent values into version ids.
1113
ints are looked up in the index.
1114
.FOO values are ghosts and converted in to FOO.
1116
NOTE: the function is retained here for clarity, and for possible
1117
use in partial index reads. However bulk processing now has
1118
it inlined in __init__ for inner-loop optimisation.
1121
for value in compressed_parents:
1122
if value[-1] == '.':
1123
# uncompressed reference
1124
result.append(value[1:])
1126
# this is 15/4000ms faster than isinstance,
1127
# this function is called thousands of times a
1128
# second so small variations add up.
1129
assert value.__class__ is str
1130
result.append(self._history[int(value)])
1133
def get_graph(self):
1135
for version_id, index in self._cache.iteritems():
1136
graph.append((version_id, index[4]))
1139
def get_ancestry(self, versions):
1140
"""See VersionedFile.get_ancestry."""
1141
# get a graph of all the mentioned versions:
1143
pending = set(versions)
1145
version = pending.pop()
1146
parents = self._cache[version][4]
1147
# got the parents ok
1149
parents = [parent for parent in parents if parent in self._cache]
1150
for parent in parents:
1151
# if not completed and not a ghost
1152
if parent not in graph:
1154
graph[version] = parents
1155
return topo_sort(graph.items())
1157
def get_ancestry_with_ghosts(self, versions):
1158
"""See VersionedFile.get_ancestry_with_ghosts."""
1159
# get a graph of all the mentioned versions:
1161
pending = set(versions)
1163
version = pending.pop()
1165
parents = self._cache[version][4]
1171
# got the parents ok
1172
for parent in parents:
1173
if parent not in graph:
1175
graph[version] = parents
1176
return topo_sort(graph.items())
1178
def num_versions(self):
1179
return len(self._history)
1181
__len__ = num_versions
1183
def get_versions(self):
1184
return self._history
1186
def idx_to_name(self, idx):
1187
return self._history[idx]
1189
def lookup(self, version_id):
1190
assert version_id in self._cache
1191
return self._cache[version_id][5]
1193
def _version_list_to_index(self, versions):
1195
for version in versions:
1196
if version in self._cache:
1197
# -- inlined lookup() --
1198
result_list.append(str(self._cache[version][5]))
1199
# -- end lookup () --
1201
result_list.append('.' + version.encode('utf-8'))
1202
return ' '.join(result_list)
1204
def add_version(self, version_id, options, pos, size, parents):
1205
"""Add a version record to the index."""
1206
self.add_versions(((version_id, options, pos, size, parents),))
1208
def add_versions(self, versions):
1209
"""Add multiple versions to the index.
1211
:param versions: a list of tuples:
1212
(version_id, options, pos, size, parents).
1215
for version_id, options, pos, size, parents in versions:
1216
line = "\n%s %s %s %s %s :" % (version_id.encode('utf-8'),
1220
self._version_list_to_index(parents))
1221
assert isinstance(line, str), \
1222
'content must be utf-8 encoded: %r' % (line,)
1224
self._transport.append(self._filename, StringIO(''.join(lines)))
1225
# cache after writing, so that a failed write leads to missing cache
1226
# entries not extra ones. XXX TODO: RBC 20060502 in the event of a
1227
# failure, reload the index or flush it or some such, to prevent
1228
# writing records that did complete twice.
1229
for version_id, options, pos, size, parents in versions:
1230
self._cache_version(version_id, options, pos, size, parents)
1232
def has_version(self, version_id):
1233
"""True if the version is in the index."""
1234
return self._cache.has_key(version_id)
1236
def get_position(self, version_id):
1237
"""Return data position and size of specified version."""
1238
return (self._cache[version_id][2], \
1239
self._cache[version_id][3])
1241
def get_method(self, version_id):
1242
"""Return compression method of specified version."""
1243
options = self._cache[version_id][1]
1244
if 'fulltext' in options:
1247
assert 'line-delta' in options
1250
def get_options(self, version_id):
1251
return self._cache[version_id][1]
1253
def get_parents(self, version_id):
1254
"""Return parents of specified version ignoring ghosts."""
1255
return [parent for parent in self._cache[version_id][4]
1256
if parent in self._cache]
1258
def get_parents_with_ghosts(self, version_id):
1259
"""Return parents of specified version with ghosts."""
1260
return self._cache[version_id][4]
1262
def check_versions_present(self, version_ids):
1263
"""Check that all specified versions are present."""
1264
version_ids = set(version_ids)
1265
for version_id in list(version_ids):
1266
if version_id in self._cache:
1267
version_ids.remove(version_id)
1269
raise RevisionNotPresent(list(version_ids)[0], self.filename)
1272
class _KnitData(_KnitComponentFile):
1273
"""Contents of the knit data file"""
1275
HEADER = "# bzr knit data 8\n"
1277
def __init__(self, transport, filename, mode, create=False, file_mode=None):
1278
_KnitComponentFile.__init__(self, transport, filename, mode)
1280
self._checked = False
1282
self._transport.put(self._filename, StringIO(''), mode=file_mode)
1284
def clear_cache(self):
1285
"""Clear the record cache."""
1288
def _open_file(self):
1289
if self._file is None:
1291
self._file = self._transport.get(self._filename)
1296
def _record_to_data(self, version_id, digest, lines):
1297
"""Convert version_id, digest, lines into a raw data block.
1299
:return: (len, a StringIO instance with the raw data ready to read.)
1302
data_file = GzipFile(None, mode='wb', fileobj=sio)
1303
data_file.writelines(chain(
1304
["version %s %d %s\n" % (version_id.encode('utf-8'),
1308
["end %s\n" % version_id.encode('utf-8')]))
1315
def add_raw_record(self, raw_data):
1316
"""Append a prepared record to the data file.
1318
:return: the offset in the data file raw_data was written.
1320
assert isinstance(raw_data, str), 'data must be plain bytes'
1321
return self._transport.append(self._filename, StringIO(raw_data))
1323
def add_record(self, version_id, digest, lines):
1324
"""Write new text record to disk. Returns the position in the
1325
file where it was written."""
1326
size, sio = self._record_to_data(version_id, digest, lines)
1328
start_pos = self._transport.append(self._filename, sio)
1329
return start_pos, size
1331
def _parse_record_header(self, version_id, raw_data):
1332
"""Parse a record header for consistency.
1334
:return: the header and the decompressor stream.
1335
as (stream, header_record)
1337
df = GzipFile(mode='rb', fileobj=StringIO(raw_data))
1338
rec = df.readline().split()
1340
raise KnitCorrupt(self._filename, 'unexpected number of elements in record header')
1341
if rec[1].decode('utf-8')!= version_id:
1342
raise KnitCorrupt(self._filename,
1343
'unexpected version, wanted %r, got %r' % (
1344
version_id, rec[1]))
1347
def _parse_record(self, version_id, data):
1349
# 4168 calls in 2880 217 internal
1350
# 4168 calls to _parse_record_header in 2121
1351
# 4168 calls to readlines in 330
1352
df, rec = self._parse_record_header(version_id, data)
1353
record_contents = df.readlines()
1354
l = record_contents.pop()
1355
assert len(record_contents) == int(rec[2])
1356
if l.decode('utf-8') != 'end %s\n' % version_id:
1357
raise KnitCorrupt(self._filename, 'unexpected version end line %r, wanted %r'
1360
return record_contents, rec[3]
1362
def read_records_iter_raw(self, records):
1363
"""Read text records from data file and yield raw data.
1365
This unpacks enough of the text record to validate the id is
1366
as expected but thats all.
1368
It will actively recompress currently cached records on the
1369
basis that that is cheaper than I/O activity.
1371
# setup an iterator of the external records:
1372
# uses readv so nice and fast we hope.
1374
# grab the disk data needed.
1375
raw_records = self._transport.readv(self._filename,
1376
[(pos, size) for version_id, pos, size in records])
1378
for version_id, pos, size in records:
1379
pos, data = raw_records.next()
1380
# validate the header
1381
df, rec = self._parse_record_header(version_id, data)
1383
yield version_id, data
1385
def read_records_iter(self, records):
1386
"""Read text records from data file and yield result.
1388
Each passed record is a tuple of (version_id, pos, len) and
1389
will be read in the given order. Yields (version_id,
1392
if len(records) == 0:
1395
# 60890 calls for 4168 extractions in 5045, 683 internal.
1396
# 4168 calls to readv in 1411
1397
# 4168 calls to parse_record in 2880
1399
# Get unique records, sorted by position
1400
needed_records = sorted(set(records), key=operator.itemgetter(1))
1402
# We take it that the transport optimizes the fetching as good
1403
# as possible (ie, reads continuous ranges.)
1404
response = self._transport.readv(self._filename,
1405
[(pos, size) for version_id, pos, size in needed_records])
1408
for (record_id, pos, size), (pos, data) in \
1409
izip(iter(needed_records), response):
1410
content, digest = self._parse_record(record_id, data)
1411
record_map[record_id] = (digest, content)
1413
for version_id, pos, size in records:
1414
digest, content = record_map[version_id]
1415
yield version_id, content, digest
1417
def read_records(self, records):
1418
"""Read records into a dictionary."""
1420
for record_id, content, digest in self.read_records_iter(records):
1421
components[record_id] = (content, digest)
1425
class InterKnit(InterVersionedFile):
1426
"""Optimised code paths for knit to knit operations."""
1428
_matching_file_from_factory = KnitVersionedFile
1429
_matching_file_to_factory = KnitVersionedFile
1432
def is_compatible(source, target):
1433
"""Be compatible with knits. """
1435
return (isinstance(source, KnitVersionedFile) and
1436
isinstance(target, KnitVersionedFile))
1437
except AttributeError:
1440
def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
1441
"""See InterVersionedFile.join."""
1442
assert isinstance(self.source, KnitVersionedFile)
1443
assert isinstance(self.target, KnitVersionedFile)
1445
version_ids = self._get_source_version_ids(version_ids, ignore_missing)
1450
pb = bzrlib.ui.ui_factory.nested_progress_bar()
1452
version_ids = list(version_ids)
1453
if None in version_ids:
1454
version_ids.remove(None)
1456
self.source_ancestry = set(self.source.get_ancestry(version_ids))
1457
this_versions = set(self.target._index.get_versions())
1458
needed_versions = self.source_ancestry - this_versions
1459
cross_check_versions = self.source_ancestry.intersection(this_versions)
1460
mismatched_versions = set()
1461
for version in cross_check_versions:
1462
# scan to include needed parents.
1463
n1 = set(self.target.get_parents_with_ghosts(version))
1464
n2 = set(self.source.get_parents_with_ghosts(version))
1466
# FIXME TEST this check for cycles being introduced works
1467
# the logic is we have a cycle if in our graph we are an
1468
# ancestor of any of the n2 revisions.
1474
parent_ancestors = self.source.get_ancestry(parent)
1475
if version in parent_ancestors:
1476
raise errors.GraphCycleError([parent, version])
1477
# ensure this parent will be available later.
1478
new_parents = n2.difference(n1)
1479
needed_versions.update(new_parents.difference(this_versions))
1480
mismatched_versions.add(version)
1482
if not needed_versions and not mismatched_versions:
1484
full_list = topo_sort(self.source.get_graph())
1486
version_list = [i for i in full_list if (not self.target.has_version(i)
1487
and i in needed_versions)]
1491
copy_queue_records = []
1493
for version_id in version_list:
1494
options = self.source._index.get_options(version_id)
1495
parents = self.source._index.get_parents_with_ghosts(version_id)
1496
# check that its will be a consistent copy:
1497
for parent in parents:
1498
# if source has the parent, we must :
1499
# * already have it or
1500
# * have it scheduled already
1501
# otherwise we don't care
1502
assert (self.target.has_version(parent) or
1503
parent in copy_set or
1504
not self.source.has_version(parent))
1505
data_pos, data_size = self.source._index.get_position(version_id)
1506
copy_queue_records.append((version_id, data_pos, data_size))
1507
copy_queue.append((version_id, options, parents))
1508
copy_set.add(version_id)
1510
# data suck the join:
1512
total = len(version_list)
1515
for (version_id, raw_data), \
1516
(version_id2, options, parents) in \
1517
izip(self.source._data.read_records_iter_raw(copy_queue_records),
1519
assert version_id == version_id2, 'logic error, inconsistent results'
1521
pb.update("Joining knit", count, total)
1522
raw_records.append((version_id, options, parents, len(raw_data)))
1523
raw_datum.append(raw_data)
1524
self.target._add_raw_records(raw_records, ''.join(raw_datum))
1526
for version in mismatched_versions:
1527
# FIXME RBC 20060309 is this needed?
1528
n1 = set(self.target.get_parents_with_ghosts(version))
1529
n2 = set(self.source.get_parents_with_ghosts(version))
1530
# write a combined record to our history preserving the current
1531
# parents as first in the list
1532
new_parents = self.target.get_parents_with_ghosts(version) + list(n2.difference(n1))
1533
self.target.fix_parents(version, new_parents)
1539
InterVersionedFile.register_optimiser(InterKnit)
1542
class WeaveToKnit(InterVersionedFile):
1543
"""Optimised code paths for weave to knit operations."""
1545
_matching_file_from_factory = bzrlib.weave.WeaveFile
1546
_matching_file_to_factory = KnitVersionedFile
1549
def is_compatible(source, target):
1550
"""Be compatible with weaves to knits."""
1552
return (isinstance(source, bzrlib.weave.Weave) and
1553
isinstance(target, KnitVersionedFile))
1554
except AttributeError:
1557
def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
1558
"""See InterVersionedFile.join."""
1559
assert isinstance(self.source, bzrlib.weave.Weave)
1560
assert isinstance(self.target, KnitVersionedFile)
1562
version_ids = self._get_source_version_ids(version_ids, ignore_missing)
1567
pb = bzrlib.ui.ui_factory.nested_progress_bar()
1569
version_ids = list(version_ids)
1571
self.source_ancestry = set(self.source.get_ancestry(version_ids))
1572
this_versions = set(self.target._index.get_versions())
1573
needed_versions = self.source_ancestry - this_versions
1574
cross_check_versions = self.source_ancestry.intersection(this_versions)
1575
mismatched_versions = set()
1576
for version in cross_check_versions:
1577
# scan to include needed parents.
1578
n1 = set(self.target.get_parents_with_ghosts(version))
1579
n2 = set(self.source.get_parents(version))
1580
# if all of n2's parents are in n1, then its fine.
1581
if n2.difference(n1):
1582
# FIXME TEST this check for cycles being introduced works
1583
# the logic is we have a cycle if in our graph we are an
1584
# ancestor of any of the n2 revisions.
1590
parent_ancestors = self.source.get_ancestry(parent)
1591
if version in parent_ancestors:
1592
raise errors.GraphCycleError([parent, version])
1593
# ensure this parent will be available later.
1594
new_parents = n2.difference(n1)
1595
needed_versions.update(new_parents.difference(this_versions))
1596
mismatched_versions.add(version)
1598
if not needed_versions and not mismatched_versions:
1600
full_list = topo_sort(self.source.get_graph())
1602
version_list = [i for i in full_list if (not self.target.has_version(i)
1603
and i in needed_versions)]
1607
total = len(version_list)
1608
for version_id in version_list:
1609
pb.update("Converting to knit", count, total)
1610
parents = self.source.get_parents(version_id)
1611
# check that its will be a consistent copy:
1612
for parent in parents:
1613
# if source has the parent, we must already have it
1614
assert (self.target.has_version(parent))
1615
self.target.add_lines(
1616
version_id, parents, self.source.get_lines(version_id))
1619
for version in mismatched_versions:
1620
# FIXME RBC 20060309 is this needed?
1621
n1 = set(self.target.get_parents_with_ghosts(version))
1622
n2 = set(self.source.get_parents(version))
1623
# write a combined record to our history preserving the current
1624
# parents as first in the list
1625
new_parents = self.target.get_parents_with_ghosts(version) + list(n2.difference(n1))
1626
self.target.fix_parents(version, new_parents)
1632
InterVersionedFile.register_optimiser(WeaveToKnit)
1635
class KnitSequenceMatcher(difflib.SequenceMatcher):
1636
"""Knit tuned sequence matcher.
1638
This is based on profiling of difflib which indicated some improvements
1639
for our usage pattern.
1642
def find_longest_match(self, alo, ahi, blo, bhi):
1643
"""Find longest matching block in a[alo:ahi] and b[blo:bhi].
1645
If isjunk is not defined:
1647
Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
1648
alo <= i <= i+k <= ahi
1649
blo <= j <= j+k <= bhi
1650
and for all (i',j',k') meeting those conditions,
1653
and if i == i', j <= j'
1655
In other words, of all maximal matching blocks, return one that
1656
starts earliest in a, and of all those maximal matching blocks that
1657
start earliest in a, return the one that starts earliest in b.
1659
>>> s = SequenceMatcher(None, " abcd", "abcd abcd")
1660
>>> s.find_longest_match(0, 5, 0, 9)
1663
If isjunk is defined, first the longest matching block is
1664
determined as above, but with the additional restriction that no
1665
junk element appears in the block. Then that block is extended as
1666
far as possible by matching (only) junk elements on both sides. So
1667
the resulting block never matches on junk except as identical junk
1668
happens to be adjacent to an "interesting" match.
1670
Here's the same example as before, but considering blanks to be
1671
junk. That prevents " abcd" from matching the " abcd" at the tail
1672
end of the second sequence directly. Instead only the "abcd" can
1673
match, and matches the leftmost "abcd" in the second sequence:
1675
>>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
1676
>>> s.find_longest_match(0, 5, 0, 9)
1679
If no blocks match, return (alo, blo, 0).
1681
>>> s = SequenceMatcher(None, "ab", "c")
1682
>>> s.find_longest_match(0, 2, 0, 1)
1686
# CAUTION: stripping common prefix or suffix would be incorrect.
1690
# Longest matching block is "ab", but if common prefix is
1691
# stripped, it's "a" (tied with "b"). UNIX(tm) diff does so
1692
# strip, so ends up claiming that ab is changed to acab by
1693
# inserting "ca" in the middle. That's minimal but unintuitive:
1694
# "it's obvious" that someone inserted "ac" at the front.
1695
# Windiff ends up at the same place as diff, but by pairing up
1696
# the unique 'b's and then matching the first two 'a's.
1698
a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.isbjunk
1699
besti, bestj, bestsize = alo, blo, 0
1700
# find longest junk-free match
1701
# during an iteration of the loop, j2len[j] = length of longest
1702
# junk-free match ending with a[i-1] and b[j]
1706
for i in xrange(alo, ahi):
1707
# look at all instances of a[i] in b; note that because
1708
# b2j has no junk keys, the loop is skipped if a[i] is junk
1709
j2lenget = j2len.get
1712
# changing b2j.get(a[i], nothing) to a try:KeyError pair produced the
1713
# following improvement
1714
# 704 0 4650.5320 2620.7410 bzrlib.knit:1336(find_longest_match)
1715
# +326674 0 1655.1210 1655.1210 +<method 'get' of 'dict' objects>
1716
# +76519 0 374.6700 374.6700 +<method 'has_key' of 'dict' objects>
1718
# 704 0 3733.2820 2209.6520 bzrlib.knit:1336(find_longest_match)
1719
# +211400 0 1147.3520 1147.3520 +<method 'get' of 'dict' objects>
1720
# +76519 0 376.2780 376.2780 +<method 'has_key' of 'dict' objects>
1732
k = newj2len[j] = 1 + j2lenget(-1 + j, 0)
1734
besti, bestj, bestsize = 1 + i-k, 1 + j-k, k
1737
# Extend the best by non-junk elements on each end. In particular,
1738
# "popular" non-junk elements aren't in b2j, which greatly speeds
1739
# the inner loop above, but also means "the best" match so far
1740
# doesn't contain any junk *or* popular non-junk elements.
1741
while besti > alo and bestj > blo and \
1742
not isbjunk(b[bestj-1]) and \
1743
a[besti-1] == b[bestj-1]:
1744
besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
1745
while besti+bestsize < ahi and bestj+bestsize < bhi and \
1746
not isbjunk(b[bestj+bestsize]) and \
1747
a[besti+bestsize] == b[bestj+bestsize]:
1750
# Now that we have a wholly interesting match (albeit possibly
1751
# empty!), we may as well suck up the matching junk on each
1752
# side of it too. Can't think of a good reason not to, and it
1753
# saves post-processing the (possibly considerable) expense of
1754
# figuring out what to do with it. In the case of an empty
1755
# interesting match, this is clearly the right thing to do,
1756
# because no other kind of match is possible in the regions.
1757
while besti > alo and bestj > blo and \
1758
isbjunk(b[bestj-1]) and \
1759
a[besti-1] == b[bestj-1]:
1760
besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
1761
while besti+bestsize < ahi and bestj+bestsize < bhi and \
1762
isbjunk(b[bestj+bestsize]) and \
1763
a[besti+bestsize] == b[bestj+bestsize]:
1764
bestsize = bestsize + 1
1766
return besti, bestj, bestsize
added
removed
bzrlib/knit.py
