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>
6
# This program is free software; you can redistribute it and/or modify
7
# it under the terms of the GNU General Public License as published by
8
# the Free Software Foundation; either version 2 of the License, or
9
# (at your option) any later version.
11
# This program is distributed in the hope that it will be useful,
12
# but WITHOUT ANY WARRANTY; without even the implied warranty of
13
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14
# GNU General Public License for more details.
16
# You should have received a copy of the GNU General Public License
17
# along with this program; if not, write to the Free Software
18
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20
"""Knit versionedfile implementation.
22
A knit is a versioned file implementation that supports efficient append only
26
lifeless: the data file is made up of "delta records". each delta record has a delta header
27
that contains; (1) a version id, (2) the size of the delta (in lines), and (3) the digest of
28
the -expanded data- (ie, the delta applied to the parent). the delta also ends with a
29
end-marker; simply "end VERSION"
31
delta can be line or full contents.a
32
... the 8's there are the index number of the annotation.
33
version robertc@robertcollins.net-20051003014215-ee2990904cc4c7ad 7 c7d23b2a5bd6ca00e8e266cec0ec228158ee9f9e
37
8 e.set('executable', 'yes')
39
8 if elt.get('executable') == 'yes':
40
8 ie.executable = True
41
end robertc@robertcollins.net-20051003014215-ee2990904cc4c7ad
45
09:33 < jrydberg> lifeless: each index is made up of a tuple of; version id, options, position, size, parents
46
09:33 < jrydberg> lifeless: the parents are currently dictionary compressed
47
09:33 < jrydberg> lifeless: (meaning it currently does not support ghosts)
48
09:33 < lifeless> right
49
09:33 < jrydberg> lifeless: the position and size is the range in the data file
52
so the index sequence is the dictionary compressed sequence number used
53
in the deltas to provide line annotation
58
# 10:16 < lifeless> make partial index writes safe
59
# 10:16 < lifeless> implement 'knit.check()' like weave.check()
60
# 10:17 < lifeless> record known ghosts so we can detect when they are filled in rather than the current 'reweave
62
# move sha1 out of the content so that join is faster at verifying parents
63
# record content length ?
66
from cStringIO import StringIO
68
from difflib import SequenceMatcher
69
from gzip import GzipFile
73
import bzrlib.errors as errors
74
from bzrlib.errors import FileExists, NoSuchFile, KnitError, \
75
InvalidRevisionId, KnitCorrupt, KnitHeaderError, \
76
RevisionNotPresent, RevisionAlreadyPresent
77
from bzrlib.trace import mutter
78
from bzrlib.osutils import contains_whitespace, contains_linebreaks, \
80
from bzrlib.versionedfile import VersionedFile, InterVersionedFile
81
from bzrlib.tsort import topo_sort
84
# TODO: Split out code specific to this format into an associated object.
86
# TODO: Can we put in some kind of value to check that the index and data
87
# files belong together?
89
# TODO: accomodate binaries, perhaps by storing a byte count
91
# TODO: function to check whole file
93
# TODO: atomically append data, then measure backwards from the cursor
94
# position after writing to work out where it was located. we may need to
95
# bypass python file buffering.
98
INDEX_SUFFIX = '.kndx'
101
class KnitContent(object):
102
"""Content of a knit version to which deltas can be applied."""
104
def __init__(self, lines):
107
def annotate_iter(self):
108
"""Yield tuples of (origin, text) for each content line."""
109
for origin, text in self._lines:
113
"""Return a list of (origin, text) tuples."""
114
return list(self.annotate_iter())
116
def apply_delta(self, delta):
117
"""Apply delta to this content."""
119
for start, end, count, lines in delta:
120
self._lines[offset+start:offset+end] = lines
121
offset = offset + (start - end) + count
123
def line_delta_iter(self, new_lines):
124
"""Generate line-based delta from new_lines to this content."""
125
new_texts = [text for origin, text in new_lines._lines]
126
old_texts = [text for origin, text in self._lines]
127
s = difflib.SequenceMatcher(None, old_texts, new_texts)
128
for op in s.get_opcodes():
131
yield (op[1], op[2], op[4]-op[3], new_lines._lines[op[3]:op[4]])
133
def line_delta(self, new_lines):
134
return list(self.line_delta_iter(new_lines))
137
return [text for origin, text in self._lines]
140
class _KnitFactory(object):
141
"""Base factory for creating content objects."""
143
def make(self, lines, version):
144
num_lines = len(lines)
145
return KnitContent(zip([version] * num_lines, lines))
148
class KnitAnnotateFactory(_KnitFactory):
149
"""Factory for creating annotated Content objects."""
153
def parse_fulltext(self, content, version):
156
origin, text = line.split(' ', 1)
157
lines.append((int(origin), text))
158
return KnitContent(lines)
160
def parse_line_delta_iter(self, lines):
162
header = lines.pop(0)
163
start, end, c = [int(n) for n in header.split(',')]
166
origin, text = lines.pop(0).split(' ', 1)
167
contents.append((int(origin), text))
168
yield start, end, c, contents
170
def parse_line_delta(self, lines, version):
171
return list(self.parse_line_delta_iter(lines))
173
def lower_fulltext(self, content):
174
return ['%d %s' % (o, t) for o, t in content._lines]
176
def lower_line_delta(self, delta):
178
for start, end, c, lines in delta:
179
out.append('%d,%d,%d\n' % (start, end, c))
180
for origin, text in lines:
181
out.append('%d %s' % (origin, text))
185
class KnitPlainFactory(_KnitFactory):
186
"""Factory for creating plain Content objects."""
190
def parse_fulltext(self, content, version):
191
return self.make(content, version)
193
def parse_line_delta_iter(self, lines, version):
195
header = lines.pop(0)
196
start, end, c = [int(n) for n in header.split(',')]
197
yield start, end, c, zip([version] * c, lines[:c])
200
def parse_line_delta(self, lines, version):
201
return list(self.parse_line_delta_iter(lines, version))
203
def lower_fulltext(self, content):
204
return content.text()
206
def lower_line_delta(self, delta):
208
for start, end, c, lines in delta:
209
out.append('%d,%d,%d\n' % (start, end, c))
210
out.extend([text for origin, text in lines])
214
def make_empty_knit(transport, relpath):
215
"""Construct a empty knit at the specified location."""
216
k = KnitVersionedFile(transport, relpath, 'w', KnitPlainFactory)
220
class KnitVersionedFile(VersionedFile):
221
"""Weave-like structure with faster random access.
223
A knit stores a number of texts and a summary of the relationships
224
between them. Texts are identified by a string version-id. Texts
225
are normally stored and retrieved as a series of lines, but can
226
also be passed as single strings.
228
Lines are stored with the trailing newline (if any) included, to
229
avoid special cases for files with no final newline. Lines are
230
composed of 8-bit characters, not unicode. The combination of
231
these approaches should mean any 'binary' file can be safely
232
stored and retrieved.
235
def __init__(self, relpath, transport, file_mode=None, access_mode=None, factory=None,
236
basis_knit=None, delta=True, create=False):
237
"""Construct a knit at location specified by relpath.
239
:param create: If not True, only open an existing knit.
241
if access_mode is None:
243
assert access_mode in ('r', 'w'), "invalid mode specified %r" % access_mode
244
assert not basis_knit or isinstance(basis_knit, KnitVersionedFile), \
247
self.transport = transport
248
self.filename = relpath
249
self.basis_knit = basis_knit
250
self.factory = factory or KnitAnnotateFactory()
251
self.writable = (access_mode == 'w')
254
self._index = _KnitIndex(transport, relpath + INDEX_SUFFIX,
255
access_mode, create=create)
256
self._data = _KnitData(transport, relpath + DATA_SUFFIX,
257
access_mode, create=not len(self.versions()))
259
def copy_to(self, name, transport):
260
"""See VersionedFile.copy_to()."""
261
# copy the current index to a temp index to avoid racing with local
263
transport.put(name + INDEX_SUFFIX + '.tmp', self.transport.get(self._index._filename))
265
transport.put(name + DATA_SUFFIX, self._data._open_file())
266
# rename the copied index into place
267
transport.rename(name + INDEX_SUFFIX + '.tmp', name + INDEX_SUFFIX)
269
def create_empty(self, name, transport, mode=None):
270
return KnitVersionedFile(name, transport, factory=self.factory, delta=self.delta, create=True)
272
def fix_parents(self, version, new_parents):
273
"""Fix the parents list for version.
275
This is done by appending a new version to the index
276
with identical data except for the parents list.
277
the parents list must be a superset of the current
280
current_values = self._index._cache[version]
281
assert set(current_values[4]).difference(set(new_parents)) == set()
282
self._index.add_version(version,
288
def get_graph_with_ghosts(self):
289
"""See VersionedFile.get_graph_with_ghosts()."""
290
graph_items = self._index.get_graph()
291
return dict(graph_items)
295
"""See VersionedFile.get_suffixes()."""
296
return [DATA_SUFFIX, INDEX_SUFFIX]
298
def has_ghost(self, version_id):
299
"""True if there is a ghost reference in the file to version_id."""
301
if self.has_version(version_id):
303
# optimisable if needed by memoising the _ghosts set.
304
items = self._index.get_graph()
305
for node, parents in items:
306
for parent in parents:
307
if parent not in self._index._cache:
308
if parent == version_id:
313
"""See VersionedFile.versions."""
314
return self._index.get_versions()
316
def has_version(self, version_id):
317
"""See VersionedFile.has_version."""
318
return self._index.has_version(version_id)
320
__contains__ = has_version
322
def _merge_annotations(self, content, parents):
323
"""Merge annotations for content. This is done by comparing
324
the annotations based on changed to the text."""
325
for parent_id in parents:
326
merge_content = self._get_content(parent_id)
327
seq = SequenceMatcher(None, merge_content.text(), content.text())
328
for i, j, n in seq.get_matching_blocks():
331
content._lines[j:j+n] = merge_content._lines[i:i+n]
333
def _get_components(self, version_id):
334
"""Return a list of (version_id, method, data) tuples that
335
makes up version specified by version_id of the knit.
337
The components should be applied in the order of the returned
340
The basis knit will be used to the largest extent possible
341
since it is assumed that accesses to it is faster.
343
# needed_revisions holds a list of (method, version_id) of
344
# versions that is needed to be fetched to construct the final
345
# version of the file.
347
# basis_revisions is a list of versions that needs to be
348
# fetched but exists in the basis knit.
350
basis = self.basis_knit
357
if basis and basis._index.has_version(cursor):
359
basis_versions.append(cursor)
360
method = picked_knit._index.get_method(cursor)
361
needed_versions.append((method, cursor))
362
if method == 'fulltext':
364
cursor = picked_knit.get_parents(cursor)[0]
369
for comp_id in basis_versions:
370
data_pos, data_size = basis._index.get_data_position(comp_id)
371
records.append((piece_id, data_pos, data_size))
372
components.update(basis._data.read_records(records))
375
for comp_id in [vid for method, vid in needed_versions
376
if vid not in basis_versions]:
377
data_pos, data_size = self._index.get_position(comp_id)
378
records.append((comp_id, data_pos, data_size))
379
components.update(self._data.read_records(records))
381
# get_data_records returns a mapping with the version id as
382
# index and the value as data. The order the components need
383
# to be applied is held by needed_versions (reversed).
385
for method, comp_id in reversed(needed_versions):
386
out.append((comp_id, method, components[comp_id]))
390
def _get_content(self, version_id):
391
"""Returns a content object that makes up the specified
393
if not self.has_version(version_id):
394
raise RevisionNotPresent(version_id, self.filename)
396
if self.basis_knit and version_id in self.basis_knit:
397
return self.basis_knit._get_content(version_id)
400
components = self._get_components(version_id)
401
for component_id, method, (data, digest) in components:
402
version_idx = self._index.lookup(component_id)
403
if method == 'fulltext':
404
assert content is None
405
content = self.factory.parse_fulltext(data, version_idx)
406
elif method == 'line-delta':
407
delta = self.factory.parse_line_delta(data, version_idx)
408
content.apply_delta(delta)
410
if 'no-eol' in self._index.get_options(version_id):
411
line = content._lines[-1][1].rstrip('\n')
412
content._lines[-1] = (content._lines[-1][0], line)
414
if sha_strings(content.text()) != digest:
415
raise KnitCorrupt(self.filename, 'sha-1 does not match')
419
def _check_versions_present(self, version_ids):
420
"""Check that all specified versions are present."""
421
version_ids = set(version_ids)
422
for r in list(version_ids):
423
if self._index.has_version(r):
424
version_ids.remove(r)
426
raise RevisionNotPresent(list(version_ids)[0], self.filename)
428
def add_lines_with_ghosts(self, version_id, parents, lines):
429
"""See VersionedFile.add_lines_with_ghosts()."""
430
self._check_add(version_id, lines)
431
return self._add(version_id, lines[:], parents, self.delta)
433
def add_lines(self, version_id, parents, lines):
434
"""See VersionedFile.add_lines."""
435
self._check_add(version_id, lines)
436
self._check_versions_present(parents)
437
return self._add(version_id, lines[:], parents, self.delta)
439
def _check_add(self, version_id, lines):
440
"""check that version_id and lines are safe to add."""
441
assert self.writable, "knit is not opened for write"
442
### FIXME escape. RBC 20060228
443
if contains_whitespace(version_id):
444
raise InvalidRevisionId(version_id)
445
if self.has_version(version_id):
446
raise RevisionAlreadyPresent(version_id, self.filename)
448
if False or __debug__:
450
assert '\n' not in l[:-1]
452
def _add(self, version_id, lines, parents, delta):
453
"""Add a set of lines on top of version specified by parents.
455
If delta is true, compress the text as a line-delta against
458
Any versions not present will be converted into ghosts.
460
ghostless_parents = []
462
for parent in parents:
463
if not self.has_version(parent):
464
ghosts.append(parent)
466
ghostless_parents.append(parent)
468
if delta and not len(ghostless_parents):
471
digest = sha_strings(lines)
474
if lines[-1][-1] != '\n':
475
options.append('no-eol')
476
lines[-1] = lines[-1] + '\n'
478
lines = self.factory.make(lines, len(self._index))
479
if self.factory.annotated and len(ghostless_parents) > 0:
480
# Merge annotations from parent texts if so is needed.
481
self._merge_annotations(lines, ghostless_parents)
483
if len(ghostless_parents) and delta:
484
# To speed the extract of texts the delta chain is limited
485
# to a fixed number of deltas. This should minimize both
486
# I/O and the time spend applying deltas.
488
delta_parents = ghostless_parents
490
parent = delta_parents[0]
491
method = self._index.get_method(parent)
492
if method == 'fulltext':
494
delta_parents = self._index.get_parents(parent)
496
if method == 'line-delta':
500
options.append('line-delta')
501
content = self._get_content(ghostless_parents[0])
502
delta_hunks = content.line_delta(lines)
503
store_lines = self.factory.lower_line_delta(delta_hunks)
505
options.append('fulltext')
506
store_lines = self.factory.lower_fulltext(lines)
508
where, size = self._data.add_record(version_id, digest, store_lines)
509
self._index.add_version(version_id, options, where, size, parents)
511
def check(self, progress_bar=None):
512
"""See VersionedFile.check()."""
514
def clone_text(self, new_version_id, old_version_id, parents):
515
"""See VersionedFile.clone_text()."""
516
# FIXME RBC 20060228 make fast by only inserting an index with null delta.
517
self.add_lines(new_version_id, parents, self.get_lines(old_version_id))
519
def get_lines(self, version_id):
520
"""See VersionedFile.get_lines()."""
521
return self._get_content(version_id).text()
523
def iter_lines_added_or_present_in_versions(self, version_ids=None):
524
"""See VersionedFile.iter_lines_added_or_present_in_versions()."""
525
if version_ids is None:
526
version_ids = self.versions()
527
# we dont care about inclusions, the caller cares.
528
# but we need to setup a list of records to visit.
529
# we need version_id, position, length
530
version_id_records = []
531
for version_id in version_ids:
532
if not self.has_version(version_id):
533
raise RevisionNotPresent(version_id, self.filename)
534
data_pos, length = self._index.get_position(version_id)
535
version_id_records.append((version_id, data_pos, length))
536
pb = bzrlib.ui.ui_factory.nested_progress_bar()
538
total = len(version_id_records)
540
for version_id, data, sha_value in \
541
self._data.read_records_iter(version_id_records):
542
pb.update('Walking content.', count, total)
543
method = self._index.get_method(version_id)
544
version_idx = self._index.lookup(version_id)
545
assert method in ('fulltext', 'line-delta')
546
if method == 'fulltext':
547
content = self.factory.parse_fulltext(data, version_idx)
548
for line in content.text():
551
delta = self.factory.parse_line_delta(data, version_idx)
552
for start, end, count, lines in delta:
553
for origin, line in lines:
557
pb.update('Walking content.', total, total)
561
def num_versions(self):
562
"""See VersionedFile.num_versions()."""
563
return self._index.num_versions()
565
__len__ = num_versions
567
def annotate_iter(self, version_id):
568
"""See VersionedFile.annotate_iter."""
569
content = self._get_content(version_id)
570
for origin, text in content.annotate_iter():
571
yield self._index.idx_to_name(origin), text
573
def get_parents(self, version_id):
574
"""See VersionedFile.get_parents."""
575
self._check_versions_present([version_id])
576
return list(self._index.get_parents(version_id))
578
def get_parents_with_ghosts(self, version_id):
579
"""See VersionedFile.get_parents."""
580
self._check_versions_present([version_id])
581
return list(self._index.get_parents_with_ghosts(version_id))
583
def get_ancestry(self, versions):
584
"""See VersionedFile.get_ancestry."""
585
if isinstance(versions, basestring):
586
versions = [versions]
589
self._check_versions_present(versions)
590
return self._index.get_ancestry(versions)
592
def get_ancestry_with_ghosts(self, versions):
593
"""See VersionedFile.get_ancestry_with_ghosts."""
594
if isinstance(versions, basestring):
595
versions = [versions]
598
self._check_versions_present(versions)
599
return self._index.get_ancestry_with_ghosts(versions)
601
def _reannotate_line_delta(self, other, lines, new_version_id,
603
"""Re-annotate line-delta and return new delta."""
605
for start, end, count, contents \
606
in self.factory.parse_line_delta_iter(lines):
608
for origin, line in contents:
609
old_version_id = other._index.idx_to_name(origin)
610
if old_version_id == new_version_id:
611
idx = new_version_idx
613
idx = self._index.lookup(old_version_id)
614
new_lines.append((idx, line))
615
new_delta.append((start, end, count, new_lines))
617
return self.factory.lower_line_delta(new_delta)
619
def _reannotate_fulltext(self, other, lines, new_version_id,
621
"""Re-annotate fulltext and return new version."""
622
content = self.factory.parse_fulltext(lines, new_version_idx)
624
for origin, line in content.annotate_iter():
625
old_version_id = other._index.idx_to_name(origin)
626
if old_version_id == new_version_id:
627
idx = new_version_idx
629
idx = self._index.lookup(old_version_id)
630
new_lines.append((idx, line))
632
return self.factory.lower_fulltext(KnitContent(new_lines))
634
#@deprecated_method(zero_eight)
635
def walk(self, version_ids):
636
"""See VersionedFile.walk."""
637
# We take the short path here, and extract all relevant texts
638
# and put them in a weave and let that do all the work. Far
639
# from optimal, but is much simpler.
640
# FIXME RB 20060228 this really is inefficient!
641
from bzrlib.weave import Weave
643
w = Weave(self.filename)
644
ancestry = self.get_ancestry(version_ids)
645
sorted_graph = topo_sort(self._index.get_graph())
646
version_list = [vid for vid in sorted_graph if vid in ancestry]
648
for version_id in version_list:
649
lines = self.get_lines(version_id)
650
w.add_lines(version_id, self.get_parents(version_id), lines)
652
for lineno, insert_id, dset, line in w.walk(version_ids):
653
yield lineno, insert_id, dset, line
656
class _KnitComponentFile(object):
657
"""One of the files used to implement a knit database"""
659
def __init__(self, transport, filename, mode):
660
self._transport = transport
661
self._filename = filename
664
def write_header(self):
665
old_len = self._transport.append(self._filename, StringIO(self.HEADER))
667
raise KnitCorrupt(self._filename, 'misaligned after writing header')
669
def check_header(self, fp):
670
line = fp.read(len(self.HEADER))
671
if line != self.HEADER:
672
raise KnitHeaderError(badline=line)
675
"""Commit is a nop."""
678
return '%s(%s)' % (self.__class__.__name__, self._filename)
681
class _KnitIndex(_KnitComponentFile):
682
"""Manages knit index file.
684
The index is already kept in memory and read on startup, to enable
685
fast lookups of revision information. The cursor of the index
686
file is always pointing to the end, making it easy to append
689
_cache is a cache for fast mapping from version id to a Index
692
_history is a cache for fast mapping from indexes to version ids.
694
The index data format is dictionary compressed when it comes to
695
parent references; a index entry may only have parents that with a
696
lover index number. As a result, the index is topological sorted.
698
Duplicate entries may be written to the index for a single version id
699
if this is done then the latter one completely replaces the former:
700
this allows updates to correct version and parent information.
701
Note that the two entries may share the delta, and that successive
702
annotations and references MUST point to the first entry.
705
HEADER = "# bzr knit index 7\n"
707
def _cache_version(self, version_id, options, pos, size, parents):
708
val = (version_id, options, pos, size, parents)
709
self._cache[version_id] = val
710
if not version_id in self._history:
711
self._history.append(version_id)
713
def _iter_index(self, fp):
714
for l in fp.readlines():
717
#for l in lines.splitlines(False):
720
def __init__(self, transport, filename, mode, create=False):
721
_KnitComponentFile.__init__(self, transport, filename, mode)
723
# position in _history is the 'official' index for a revision
724
# but the values may have come from a newer entry.
725
# so - wc -l of a knit index is != the number of uniqe names
728
pb = bzrlib.ui.ui_factory.nested_progress_bar()
733
pb.update('read knit index', count, total)
734
fp = self._transport.get(self._filename)
735
self.check_header(fp)
736
for rec in self._iter_index(fp):
739
pb.update('read knit index', count, total)
740
parents = self._parse_parents(rec[4:])
741
self._cache_version(rec[0], rec[1].split(','), int(rec[2]), int(rec[3]),
743
except NoSuchFile, e:
744
if mode != 'w' or not create:
748
pb.update('read knit index', total, total)
751
def _parse_parents(self, compressed_parents):
752
"""convert a list of string parent values into version ids.
754
ints are looked up in the index.
755
.FOO values are ghosts and converted in to FOO.
758
for value in compressed_parents:
759
if value.startswith('.'):
760
result.append(value[1:])
762
assert isinstance(value, str)
763
result.append(self._history[int(value)])
768
for version_id, index in self._cache.iteritems():
769
graph.append((version_id, index[4]))
772
def get_ancestry(self, versions):
773
"""See VersionedFile.get_ancestry."""
774
# get a graph of all the mentioned versions:
776
pending = set(versions)
778
version = pending.pop()
779
parents = self._cache[version][4]
782
parents = [parent for parent in parents if parent in self._cache]
783
for parent in parents:
784
# if not completed and not a ghost
785
if parent not in graph:
787
graph[version] = parents
788
return topo_sort(graph.items())
790
def get_ancestry_with_ghosts(self, versions):
791
"""See VersionedFile.get_ancestry_with_ghosts."""
792
# get a graph of all the mentioned versions:
794
pending = set(versions)
796
version = pending.pop()
798
parents = self._cache[version][4]
805
for parent in parents:
806
if parent not in graph:
808
graph[version] = parents
809
return topo_sort(graph.items())
811
def num_versions(self):
812
return len(self._history)
814
__len__ = num_versions
816
def get_versions(self):
819
def idx_to_name(self, idx):
820
return self._history[idx]
822
def lookup(self, version_id):
823
assert version_id in self._cache
824
return self._history.index(version_id)
826
def _version_list_to_index(self, versions):
828
for version in versions:
829
if version in self._cache:
830
result_list.append(str(self._history.index(version)))
832
result_list.append('.' + version.encode('utf-8'))
833
return ' '.join(result_list)
835
def add_version(self, version_id, options, pos, size, parents):
836
"""Add a version record to the index."""
837
self._cache_version(version_id, options, pos, size, parents)
839
content = "%s %s %s %s %s\n" % (version_id,
843
self._version_list_to_index(parents))
844
self._transport.append(self._filename, StringIO(content))
846
def has_version(self, version_id):
847
"""True if the version is in the index."""
848
return self._cache.has_key(version_id)
850
def get_position(self, version_id):
851
"""Return data position and size of specified version."""
852
return (self._cache[version_id][2], \
853
self._cache[version_id][3])
855
def get_method(self, version_id):
856
"""Return compression method of specified version."""
857
options = self._cache[version_id][1]
858
if 'fulltext' in options:
861
assert 'line-delta' in options
864
def get_options(self, version_id):
865
return self._cache[version_id][1]
867
def get_parents(self, version_id):
868
"""Return parents of specified version ignoring ghosts."""
869
return [parent for parent in self._cache[version_id][4]
870
if parent in self._cache]
872
def get_parents_with_ghosts(self, version_id):
873
"""Return parents of specified version wth ghosts."""
874
return self._cache[version_id][4]
876
def check_versions_present(self, version_ids):
877
"""Check that all specified versions are present."""
878
version_ids = set(version_ids)
879
for version_id in list(version_ids):
880
if version_id in self._cache:
881
version_ids.remove(version_id)
883
raise RevisionNotPresent(list(version_ids)[0], self.filename)
886
class _KnitData(_KnitComponentFile):
887
"""Contents of the knit data file"""
889
HEADER = "# bzr knit data 7\n"
891
def __init__(self, transport, filename, mode, create=False):
892
_KnitComponentFile.__init__(self, transport, filename, mode)
894
self._checked = False
896
self._transport.put(self._filename, StringIO(''))
898
def _open_file(self):
899
if self._file is None:
901
self._file = self._transport.get(self._filename)
906
def add_record(self, version_id, digest, lines):
907
"""Write new text record to disk. Returns the position in the
908
file where it was written."""
910
data_file = GzipFile(None, mode='wb', fileobj=sio)
911
print >>data_file, "version %s %d %s" % (version_id, len(lines), digest)
912
data_file.writelines(lines)
913
print >>data_file, "end %s\n" % version_id
916
content = sio.getvalue()
917
start_pos = self._transport.append(self._filename, StringIO(content))
918
return start_pos, len(content)
920
def _parse_record(self, version_id, data):
921
df = GzipFile(mode='rb', fileobj=StringIO(data))
922
rec = df.readline().split()
924
raise KnitCorrupt(self._filename, 'unexpected number of records')
925
if rec[1] != version_id:
926
raise KnitCorrupt(self.file.name,
927
'unexpected version, wanted %r' % version_id)
929
record_contents = self._read_record_contents(df, lines)
931
if l != 'end %s\n' % version_id:
932
raise KnitCorrupt(self._filename, 'unexpected version end line %r, wanted %r'
934
return record_contents, rec[3]
936
def _read_record_contents(self, df, record_lines):
937
"""Read and return n lines from datafile."""
939
for i in range(record_lines):
940
r.append(df.readline())
943
def read_records_iter(self, records):
944
"""Read text records from data file and yield result.
946
Each passed record is a tuple of (version_id, pos, len) and
947
will be read in the given order. Yields (version_id,
951
class ContinuousRange:
952
def __init__(self, rec_id, pos, size):
954
self.end_pos = pos + size
955
self.versions = [(rec_id, pos, size)]
957
def add(self, rec_id, pos, size):
958
if self.end_pos != pos:
960
self.end_pos = pos + size
961
self.versions.append((rec_id, pos, size))
965
for rec_id, pos, size in self.versions:
966
yield rec_id, fp.read(size)
968
# We take it that the transport optimizes the fetching as good
969
# as possible (ie, reads continous ranges.)
970
response = self._transport.readv(self._filename,
971
[(pos, size) for version_id, pos, size in records])
973
for (record_id, pos, size), (pos, data) in zip(records, response):
974
content, digest = self._parse_record(record_id, data)
975
yield record_id, content, digest
977
def read_records(self, records):
978
"""Read records into a dictionary."""
980
for record_id, content, digest in self.read_records_iter(records):
981
components[record_id] = (content, digest)
985
class InterKnit(InterVersionedFile):
986
"""Optimised code paths for knit to knit operations."""
988
_matching_file_factory = KnitVersionedFile
991
def is_compatible(source, target):
992
"""Be compatible with knits. """
994
return (isinstance(source, KnitVersionedFile) and
995
isinstance(target, KnitVersionedFile))
996
except AttributeError:
999
def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
1000
"""See InterVersionedFile.join."""
1001
assert isinstance(self.source, KnitVersionedFile)
1002
assert isinstance(self.target, KnitVersionedFile)
1004
if version_ids is None:
1005
version_ids = self.source.versions()
1007
if not ignore_missing:
1008
self.source._check_versions_present(version_ids)
1010
version_ids = set(self.source.versions()).intersection(
1017
from bzrlib.progress import DummyProgress
1018
pb = DummyProgress()
1020
version_ids = list(version_ids)
1021
if None in version_ids:
1022
version_ids.remove(None)
1024
self.source_ancestry = set(self.source.get_ancestry(version_ids))
1025
this_versions = set(self.target._index.get_versions())
1026
needed_versions = self.source_ancestry - this_versions
1027
cross_check_versions = self.source_ancestry.intersection(this_versions)
1028
mismatched_versions = set()
1029
for version in cross_check_versions:
1030
# scan to include needed parents.
1031
n1 = set(self.target.get_parents_with_ghosts(version))
1032
n2 = set(self.source.get_parents_with_ghosts(version))
1034
# FIXME TEST this check for cycles being introduced works
1035
# the logic is we have a cycle if in our graph we are an
1036
# ancestor of any of the n2 revisions.
1042
parent_ancestors = self.source.get_ancestry(parent)
1043
if version in parent_ancestors:
1044
raise errors.GraphCycleError([parent, version])
1045
# ensure this parent will be available later.
1046
new_parents = n2.difference(n1)
1047
needed_versions.update(new_parents.difference(this_versions))
1048
mismatched_versions.add(version)
1050
if not needed_versions and not cross_check_versions:
1052
full_list = topo_sort(self.source.get_graph())
1054
version_list = [i for i in full_list if (not self.target.has_version(i)
1055
and i in needed_versions)]
1058
for version_id in version_list:
1059
data_pos, data_size = self.source._index.get_position(version_id)
1060
records.append((version_id, data_pos, data_size))
1063
for version_id, lines, digest \
1064
in self.source._data.read_records_iter(records):
1065
options = self.source._index.get_options(version_id)
1066
parents = self.source._index.get_parents_with_ghosts(version_id)
1068
for parent in parents:
1069
# if source has the parent, we must hav grabbed it first.
1070
assert (self.target.has_version(parent) or not
1071
self.source.has_version(parent))
1073
if self.target.factory.annotated:
1074
# FIXME jrydberg: it should be possible to skip
1075
# re-annotating components if we know that we are
1076
# going to pull all revisions in the same order.
1077
new_version_id = version_id
1078
new_version_idx = self.target._index.num_versions()
1079
if 'fulltext' in options:
1080
lines = self.target._reannotate_fulltext(self.source, lines,
1081
new_version_id, new_version_idx)
1082
elif 'line-delta' in options:
1083
lines = self.target._reannotate_line_delta(self.source, lines,
1084
new_version_id, new_version_idx)
1087
pb.update("Joining knit", count, len(version_list))
1089
pos, size = self.target._data.add_record(version_id, digest, lines)
1090
self.target._index.add_version(version_id, options, pos, size, parents)
1092
for version in mismatched_versions:
1093
n1 = set(self.target.get_parents_with_ghosts(version))
1094
n2 = set(self.source.get_parents_with_ghosts(version))
1095
# write a combined record to our history preserving the current
1096
# parents as first in the list
1097
new_parents = self.target.get_parents_with_ghosts(version) + list(n2.difference(n1))
1098
self.target.fix_parents(version, new_parents)
1103
InterVersionedFile.register_optimiser(InterKnit)
added
removed
bzrlib/knit.py
