~bzr-pqm/bzr/bzr.dev

1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
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
#
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.
10
#
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.
15
#
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
19
20
"""Knit versionedfile implementation.
21
22
A knit is a versioned file implementation that supports efficient append only
23
updates.
1563.2.6 by Robert Collins
Start check tests for knits (pending), and remove dead code.
24
25
Knit file layout:
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"
30
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
34
59,59,3
35
8
36
8         if ie.executable:
37
8             e.set('executable', 'yes')
38
130,130,2
39
8         if elt.get('executable') == 'yes':
40
8             ie.executable = True
41
end robertc@robertcollins.net-20051003014215-ee2990904cc4c7ad 
42
43
44
whats in an index:
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
50
51
52
so the index sequence is the dictionary compressed sequence number used
53
in the deltas to provide line annotation
54
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
55
"""
56
1563.2.6 by Robert Collins
Start check tests for knits (pending), and remove dead code.
57
# TODOS:
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 
61
#                    always' approach.
1563.2.11 by Robert Collins
Consolidate reweave and join as we have no separate usage, make reweave tests apply to all versionedfile implementations and deprecate the old reweave apis.
62
# move sha1 out of the content so that join is faster at verifying parents
63
# record content length ?
1563.2.6 by Robert Collins
Start check tests for knits (pending), and remove dead code.
64
                  
65
1563.2.11 by Robert Collins
Consolidate reweave and join as we have no separate usage, make reweave tests apply to all versionedfile implementations and deprecate the old reweave apis.
66
from cStringIO import StringIO
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
67
import difflib
68
from difflib import SequenceMatcher
1563.2.6 by Robert Collins
Start check tests for knits (pending), and remove dead code.
69
from gzip import GzipFile
70
import os
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
71
1563.2.11 by Robert Collins
Consolidate reweave and join as we have no separate usage, make reweave tests apply to all versionedfile implementations and deprecate the old reweave apis.
72
import bzrlib.errors as errors
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
73
from bzrlib.errors import FileExists, NoSuchFile, KnitError, \
74
        InvalidRevisionId, KnitCorrupt, KnitHeaderError, \
75
        RevisionNotPresent, RevisionAlreadyPresent
76
from bzrlib.trace import mutter
77
from bzrlib.osutils import contains_whitespace, contains_linebreaks, \
78
     sha_strings
1563.2.13 by Robert Collins
InterVersionedFile implemented.
79
from bzrlib.versionedfile import VersionedFile, InterVersionedFile
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
80
from bzrlib.tsort import topo_sort
81
82
83
# TODO: Split out code specific to this format into an associated object.
84
85
# TODO: Can we put in some kind of value to check that the index and data
86
# files belong together?
87
88
# TODO: accomodate binaries, perhaps by storing a byte count
89
90
# TODO: function to check whole file
91
92
# TODO: atomically append data, then measure backwards from the cursor
93
# position after writing to work out where it was located.  we may need to
94
# bypass python file buffering.
95
96
DATA_SUFFIX = '.knit'
97
INDEX_SUFFIX = '.kndx'
98
99
100
class KnitContent(object):
101
    """Content of a knit version to which deltas can be applied."""
102
103
    def __init__(self, lines):
104
        self._lines = lines
105
106
    def annotate_iter(self):
107
        """Yield tuples of (origin, text) for each content line."""
108
        for origin, text in self._lines:
109
            yield origin, text
110
111
    def annotate(self):
112
        """Return a list of (origin, text) tuples."""
113
        return list(self.annotate_iter())
114
115
    def apply_delta(self, delta):
116
        """Apply delta to this content."""
117
        offset = 0
118
        for start, end, count, lines in delta:
119
            self._lines[offset+start:offset+end] = lines
120
            offset = offset + (start - end) + count
121
122
    def line_delta_iter(self, new_lines):
123
        """Generate line-based delta from new_lines to this content."""
124
        new_texts = [text for origin, text in new_lines._lines]
125
        old_texts = [text for origin, text in self._lines]
126
        s = difflib.SequenceMatcher(None, old_texts, new_texts)
127
        for op in s.get_opcodes():
128
            if op[0] == 'equal':
129
                continue
130
            yield (op[1], op[2], op[4]-op[3], new_lines._lines[op[3]:op[4]])
131
132
    def line_delta(self, new_lines):
133
        return list(self.line_delta_iter(new_lines))
134
135
    def text(self):
136
        return [text for origin, text in self._lines]
137
138
139
class _KnitFactory(object):
140
    """Base factory for creating content objects."""
141
142
    def make(self, lines, version):
143
        num_lines = len(lines)
144
        return KnitContent(zip([version] * num_lines, lines))
145
146
147
class KnitAnnotateFactory(_KnitFactory):
148
    """Factory for creating annotated Content objects."""
149
150
    annotated = True
151
152
    def parse_fulltext(self, content, version):
153
        lines = []
154
        for line in content:
155
            origin, text = line.split(' ', 1)
156
            lines.append((int(origin), text))
157
        return KnitContent(lines)
158
159
    def parse_line_delta_iter(self, lines):
160
        while lines:
161
            header = lines.pop(0)
162
            start, end, c = [int(n) for n in header.split(',')]
163
            contents = []
164
            for i in range(c):
165
                origin, text = lines.pop(0).split(' ', 1)
166
                contents.append((int(origin), text))
167
            yield start, end, c, contents
168
169
    def parse_line_delta(self, lines, version):
170
        return list(self.parse_line_delta_iter(lines))
171
172
    def lower_fulltext(self, content):
173
        return ['%d %s' % (o, t) for o, t in content._lines]
174
175
    def lower_line_delta(self, delta):
176
        out = []
177
        for start, end, c, lines in delta:
178
            out.append('%d,%d,%d\n' % (start, end, c))
179
            for origin, text in lines:
180
                out.append('%d %s' % (origin, text))
181
        return out
182
183
184
class KnitPlainFactory(_KnitFactory):
185
    """Factory for creating plain Content objects."""
186
187
    annotated = False
188
189
    def parse_fulltext(self, content, version):
190
        return self.make(content, version)
191
192
    def parse_line_delta_iter(self, lines, version):
193
        while lines:
194
            header = lines.pop(0)
195
            start, end, c = [int(n) for n in header.split(',')]
196
            yield start, end, c, zip([version] * c, lines[:c])
197
            del lines[:c]
198
199
    def parse_line_delta(self, lines, version):
200
        return list(self.parse_line_delta_iter(lines, version))
201
    
202
    def lower_fulltext(self, content):
203
        return content.text()
204
205
    def lower_line_delta(self, delta):
206
        out = []
207
        for start, end, c, lines in delta:
208
            out.append('%d,%d,%d\n' % (start, end, c))
209
            out.extend([text for origin, text in lines])
210
        return out
211
212
213
def make_empty_knit(transport, relpath):
214
    """Construct a empty knit at the specified location."""
1563.2.5 by Robert Collins
Remove unused transaction references from knit.py and the versionedfile interface.
215
    k = KnitVersionedFile(transport, relpath, 'w', KnitPlainFactory)
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
216
    k._data._open_file()
217
218
219
class KnitVersionedFile(VersionedFile):
220
    """Weave-like structure with faster random access.
221
222
    A knit stores a number of texts and a summary of the relationships
223
    between them.  Texts are identified by a string version-id.  Texts
224
    are normally stored and retrieved as a series of lines, but can
225
    also be passed as single strings.
226
227
    Lines are stored with the trailing newline (if any) included, to
228
    avoid special cases for files with no final newline.  Lines are
229
    composed of 8-bit characters, not unicode.  The combination of
230
    these approaches should mean any 'binary' file can be safely
231
    stored and retrieved.
232
    """
233
1563.2.16 by Robert Collins
Change WeaveStore into VersionedFileStore and make its versoined file class parameterisable.
234
    def __init__(self, relpath, transport, file_mode=None, access_mode=None, factory=None,
1563.2.25 by Robert Collins
Merge in upstream.
235
                 basis_knit=None, delta=True, create=False):
236
        """Construct a knit at location specified by relpath.
237
        
238
        :param create: If not True, only open an existing knit.
239
        """
1563.2.16 by Robert Collins
Change WeaveStore into VersionedFileStore and make its versoined file class parameterisable.
240
        if access_mode is None:
241
            access_mode = 'w'
242
        assert access_mode in ('r', 'w'), "invalid mode specified %r" % access_mode
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
243
        assert not basis_knit or isinstance(basis_knit, KnitVersionedFile), \
244
            type(basis_knit)
245
246
        self.transport = transport
247
        self.filename = relpath
248
        self.basis_knit = basis_knit
1563.2.16 by Robert Collins
Change WeaveStore into VersionedFileStore and make its versoined file class parameterisable.
249
        self.factory = factory or KnitAnnotateFactory()
250
        self.writable = (access_mode == 'w')
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
251
        self.delta = delta
252
253
        self._index = _KnitIndex(transport, relpath + INDEX_SUFFIX,
1563.2.25 by Robert Collins
Merge in upstream.
254
            access_mode, create=create)
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
255
        self._data = _KnitData(transport, relpath + DATA_SUFFIX,
1563.2.16 by Robert Collins
Change WeaveStore into VersionedFileStore and make its versoined file class parameterisable.
256
            access_mode)
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
257
1563.2.15 by Robert Collins
remove the weavestore assumptions about the number and nature of files it manages.
258
    def copy_to(self, name, transport):
259
        """See VersionedFile.copy_to()."""
260
        # copy the current index to a temp index to avoid racing with local
261
        # writes
262
        transport.put(name + INDEX_SUFFIX + '.tmp', self.transport.get(self._index._filename))
263
        # copy the data file
264
        transport.put(name + DATA_SUFFIX, self._data._open_file())
265
        # rename the copied index into place
266
        transport.rename(name + INDEX_SUFFIX + '.tmp', name + INDEX_SUFFIX)
267
1563.2.13 by Robert Collins
InterVersionedFile implemented.
268
    def create_empty(self, name, transport, mode=None):
1563.2.25 by Robert Collins
Merge in upstream.
269
        return KnitVersionedFile(name, transport, factory=self.factory, delta=self.delta, create=True)
1563.2.15 by Robert Collins
remove the weavestore assumptions about the number and nature of files it manages.
270
    
271
    @staticmethod
272
    def get_suffixes():
273
        """See VersionedFile.get_suffixes()."""
274
        return [DATA_SUFFIX, INDEX_SUFFIX]
1563.2.13 by Robert Collins
InterVersionedFile implemented.
275
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
276
    def versions(self):
277
        """See VersionedFile.versions."""
278
        return self._index.get_versions()
279
280
    def has_version(self, version_id):
281
        """See VersionedFile.has_version."""
282
        return self._index.has_version(version_id)
283
284
    __contains__ = has_version
285
286
    def _merge_annotations(self, content, parents):
287
        """Merge annotations for content.  This is done by comparing
288
        the annotations based on changed to the text."""
289
        for parent_id in parents:
290
            merge_content = self._get_content(parent_id)
291
            seq = SequenceMatcher(None, merge_content.text(), content.text())
292
            for i, j, n in seq.get_matching_blocks():
293
                if n == 0:
294
                    continue
295
                content._lines[j:j+n] = merge_content._lines[i:i+n]
296
297
    def _get_components(self, version_id):
298
        """Return a list of (version_id, method, data) tuples that
299
        makes up version specified by version_id of the knit.
300
301
        The components should be applied in the order of the returned
302
        list.
303
304
        The basis knit will be used to the largest extent possible
305
        since it is assumed that accesses to it is faster.
306
        """
307
        # needed_revisions holds a list of (method, version_id) of
308
        # versions that is needed to be fetched to construct the final
309
        # version of the file.
310
        #
311
        # basis_revisions is a list of versions that needs to be
312
        # fetched but exists in the basis knit.
313
314
        basis = self.basis_knit
315
        needed_versions = []
316
        basis_versions = []
317
        cursor = version_id
318
319
        while 1:
320
            picked_knit = self
321
            if basis and basis._index.has_version(cursor):
322
                picked_knit = basis
323
                basis_versions.append(cursor)
324
            method = picked_knit._index.get_method(cursor)
325
            needed_versions.append((method, cursor))
326
            if method == 'fulltext':
327
                break
328
            cursor = picked_knit.get_parents(cursor)[0]
329
330
        components = {}
331
        if basis_versions:
332
            records = []
333
            for comp_id in basis_versions:
334
                data_pos, data_size = basis._index.get_data_position(comp_id)
335
                records.append((piece_id, data_pos, data_size))
336
            components.update(basis._data.read_records(records))
337
338
        records = []
339
        for comp_id in [vid for method, vid in needed_versions
340
                        if vid not in basis_versions]:
341
            data_pos, data_size = self._index.get_position(comp_id)
342
            records.append((comp_id, data_pos, data_size))
343
        components.update(self._data.read_records(records))
344
345
        # get_data_records returns a mapping with the version id as
346
        # index and the value as data.  The order the components need
347
        # to be applied is held by needed_versions (reversed).
348
        out = []
349
        for method, comp_id in reversed(needed_versions):
350
            out.append((comp_id, method, components[comp_id]))
351
352
        return out
353
354
    def _get_content(self, version_id):
355
        """Returns a content object that makes up the specified
356
        version."""
357
        if not self.has_version(version_id):
358
            raise RevisionNotPresent(version_id, self.filename)
359
360
        if self.basis_knit and version_id in self.basis_knit:
361
            return self.basis_knit._get_content(version_id)
362
363
        content = None
364
        components = self._get_components(version_id)
365
        for component_id, method, (data, digest) in components:
366
            version_idx = self._index.lookup(component_id)
367
            if method == 'fulltext':
368
                assert content is None
369
                content = self.factory.parse_fulltext(data, version_idx)
370
            elif method == 'line-delta':
371
                delta = self.factory.parse_line_delta(data, version_idx)
372
                content.apply_delta(delta)
373
374
        if 'no-eol' in self._index.get_options(version_id):
375
            line = content._lines[-1][1].rstrip('\n')
376
            content._lines[-1] = (content._lines[-1][0], line)
377
378
        if sha_strings(content.text()) != digest:
379
            raise KnitCorrupt(self.filename, 'sha-1 does not match')
380
381
        return content
382
383
    def _check_versions_present(self, version_ids):
384
        """Check that all specified versions are present."""
385
        version_ids = set(version_ids)
386
        for r in list(version_ids):
387
            if self._index.has_version(r):
388
                version_ids.remove(r)
389
        if version_ids:
390
            raise RevisionNotPresent(list(version_ids)[0], self.filename)
391
392
    def add_lines(self, version_id, parents, lines):
393
        """See VersionedFile.add_lines."""
394
        assert self.writable, "knit is not opened for write"
395
        ### FIXME escape. RBC 20060228
396
        if contains_whitespace(version_id):
397
            raise InvalidRevisionId(version_id)
398
        if self.has_version(version_id):
399
            raise RevisionAlreadyPresent(version_id, self.filename)
400
401
        if True or __debug__:
402
            for l in lines:
403
                assert '\n' not in l[:-1]
404
405
        self._check_versions_present(parents)
406
        return self._add(version_id, lines[:], parents, self.delta)
407
408
    def _add(self, version_id, lines, parents, delta):
409
        """Add a set of lines on top of version specified by parents.
410
411
        If delta is true, compress the text as a line-delta against
412
        the first parent.
413
        """
414
        if delta and not parents:
415
            delta = False
416
417
        digest = sha_strings(lines)
418
        options = []
419
        if lines:
420
            if lines[-1][-1] != '\n':
421
                options.append('no-eol')
422
                lines[-1] = lines[-1] + '\n'
423
424
        lines = self.factory.make(lines, len(self._index))
425
        if self.factory.annotated and len(parents) > 0:
426
            # Merge annotations from parent texts if so is needed.
427
            self._merge_annotations(lines, parents)
428
429
        if parents and delta:
430
            # To speed the extract of texts the delta chain is limited
431
            # to a fixed number of deltas.  This should minimize both
432
            # I/O and the time spend applying deltas.
433
            count = 0
434
            delta_parents = parents
435
            while count < 25:
436
                parent = delta_parents[0]
437
                method = self._index.get_method(parent)
438
                if method == 'fulltext':
439
                    break
440
                delta_parents = self._index.get_parents(parent)
441
                count = count + 1
442
            if method == 'line-delta':
443
                delta = False
444
445
        if delta:
446
            options.append('line-delta')
447
            content = self._get_content(parents[0])
448
            delta_hunks = content.line_delta(lines)
449
            store_lines = self.factory.lower_line_delta(delta_hunks)
450
        else:
451
            options.append('fulltext')
452
            store_lines = self.factory.lower_fulltext(lines)
453
454
        where, size = self._data.add_record(version_id, digest, store_lines)
455
        self._index.add_version(version_id, options, where, size, parents)
456
1563.2.19 by Robert Collins
stub out a check for knits.
457
    def check(self, progress_bar=None):
458
        """See VersionedFile.check()."""
459
1563.2.5 by Robert Collins
Remove unused transaction references from knit.py and the versionedfile interface.
460
    def clone_text(self, new_version_id, old_version_id, parents):
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
461
        """See VersionedFile.clone_text()."""
462
        # FIXME RBC 20060228 make fast by only inserting an index with null delta.
463
        self.add_lines(new_version_id, parents, self.get_lines(old_version_id))
464
465
    def get_lines(self, version_id):
466
        """See VersionedFile.get_lines()."""
467
        return self._get_content(version_id).text()
468
1563.2.18 by Robert Collins
get knit repositories really using knits for text storage.
469
    def num_versions(self):
470
        """See VersionedFile.num_versions()."""
471
        return self._index.num_versions()
472
473
    __len__ = num_versions
474
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
475
    def annotate_iter(self, version_id):
476
        """See VersionedFile.annotate_iter."""
477
        content = self._get_content(version_id)
478
        for origin, text in content.annotate_iter():
479
            yield self._index.idx_to_name(origin), text
480
481
    def get_parents(self, version_id):
482
        """See VersionedFile.get_parents."""
483
        self._check_versions_present([version_id])
484
        return list(self._index.get_parents(version_id))
485
486
    def get_ancestry(self, versions):
487
        """See VersionedFile.get_ancestry."""
488
        if isinstance(versions, basestring):
489
            versions = [versions]
490
        if not versions:
491
            return []
492
        self._check_versions_present(versions)
493
        return self._index.get_ancestry(versions)
494
495
    def _reannotate_line_delta(self, other, lines, new_version_id,
496
                               new_version_idx):
497
        """Re-annotate line-delta and return new delta."""
498
        new_delta = []
499
        for start, end, count, contents \
500
                in self.factory.parse_line_delta_iter(lines):
501
            new_lines = []
502
            for origin, line in contents:
503
                old_version_id = other._index.idx_to_name(origin)
504
                if old_version_id == new_version_id:
505
                    idx = new_version_idx
506
                else:
507
                    idx = self._index.lookup(old_version_id)
508
                new_lines.append((idx, line))
509
            new_delta.append((start, end, count, new_lines))
510
511
        return self.factory.lower_line_delta(new_delta)
512
513
    def _reannotate_fulltext(self, other, lines, new_version_id,
514
                             new_version_idx):
515
        """Re-annotate fulltext and return new version."""
516
        content = self.factory.parse_fulltext(lines, new_version_idx)
517
        new_lines = []
518
        for origin, line in content.annotate_iter():
519
            old_version_id = other._index.idx_to_name(origin)
520
            if old_version_id == new_version_id:
521
                idx = new_version_idx
522
            else:
523
                idx = self._index.lookup(old_version_id)
524
            new_lines.append((idx, line))
525
526
        return self.factory.lower_fulltext(KnitContent(new_lines))
527
528
    def walk(self, version_ids):
529
        """See VersionedFile.walk."""
530
        # We take the short path here, and extract all relevant texts
531
        # and put them in a weave and let that do all the work.  Far
532
        # from optimal, but is much simpler.
1563.2.6 by Robert Collins
Start check tests for knits (pending), and remove dead code.
533
        # FIXME RB 20060228 this really is inefficient!
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
534
        from bzrlib.weave import Weave
535
536
        w = Weave(self.filename)
537
        ancestry = self.get_ancestry(version_ids)
538
        sorted_graph = topo_sort(self._index.get_graph())
539
        version_list = [vid for vid in sorted_graph if vid in ancestry]
540
        
541
        for version_id in version_list:
542
            lines = self.get_lines(version_id)
543
            w.add_lines(version_id, self.get_parents(version_id), lines)
544
545
        for lineno, insert_id, dset, line in w.walk(version_ids):
546
            yield lineno, insert_id, dset, line
547
548
549
class _KnitComponentFile(object):
550
    """One of the files used to implement a knit database"""
551
1563.2.5 by Robert Collins
Remove unused transaction references from knit.py and the versionedfile interface.
552
    def __init__(self, transport, filename, mode):
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
553
        self._transport = transport
554
        self._filename = filename
555
        self._mode = mode
556
557
    def write_header(self):
1563.2.13 by Robert Collins
InterVersionedFile implemented.
558
        old_len = self._transport.append(self._filename, StringIO(self.HEADER))
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
559
        if old_len != 0:
560
            raise KnitCorrupt(self._filename, 'misaligned after writing header')
561
562
    def check_header(self, fp):
563
        line = fp.read(len(self.HEADER))
564
        if line != self.HEADER:
565
            raise KnitHeaderError(badline=line)
566
567
    def commit(self):
568
        """Commit is a nop."""
569
570
    def __repr__(self):
571
        return '%s(%s)' % (self.__class__.__name__, self._filename)
572
573
574
class _KnitIndex(_KnitComponentFile):
575
    """Manages knit index file.
576
577
    The index is already kept in memory and read on startup, to enable
578
    fast lookups of revision information.  The cursor of the index
579
    file is always pointing to the end, making it easy to append
580
    entries.
581
582
    _cache is a cache for fast mapping from version id to a Index
583
    object.
584
585
    _history is a cache for fast mapping from indexes to version ids.
586
587
    The index data format is dictionary compressed when it comes to
588
    parent references; a index entry may only have parents that with a
589
    lover index number.  As a result, the index is topological sorted.
1563.2.11 by Robert Collins
Consolidate reweave and join as we have no separate usage, make reweave tests apply to all versionedfile implementations and deprecate the old reweave apis.
590
591
    Duplicate entries may be written to the index for a single version id
592
    if this is done then the latter one completely replaces the former:
593
    this allows updates to correct version and parent information. 
594
    Note that the two entries may share the delta, and that successive
595
    annotations and references MUST point to the first entry.
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
596
    """
597
598
    HEADER = "# bzr knit index 7\n"
599
600
    def _cache_version(self, version_id, options, pos, size, parents):
601
        val = (version_id, options, pos, size, parents)
602
        self._cache[version_id] = val
1563.2.11 by Robert Collins
Consolidate reweave and join as we have no separate usage, make reweave tests apply to all versionedfile implementations and deprecate the old reweave apis.
603
        if not version_id in self._history:
604
            self._history.append(version_id)
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
605
606
    def _iter_index(self, fp):
607
        lines = fp.read()
608
        for l in lines.splitlines(False):
609
            yield l.split()
610
1563.2.25 by Robert Collins
Merge in upstream.
611
    def __init__(self, transport, filename, mode, create=False):
1563.2.5 by Robert Collins
Remove unused transaction references from knit.py and the versionedfile interface.
612
        _KnitComponentFile.__init__(self, transport, filename, mode)
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
613
        self._cache = {}
1563.2.11 by Robert Collins
Consolidate reweave and join as we have no separate usage, make reweave tests apply to all versionedfile implementations and deprecate the old reweave apis.
614
        # position in _history is the 'official' index for a revision
615
        # but the values may have come from a newer entry.
616
        # so - wc -l of a knit index is != the number of uniqe names
617
        # in the weave.
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
618
        self._history = []
619
        try:
620
            fp = self._transport.get(self._filename)
621
            self.check_header(fp)
622
            for rec in self._iter_index(fp):
623
                self._cache_version(rec[0], rec[1].split(','), int(rec[2]), int(rec[3]),
624
                    [self._history[int(i)] for i in rec[4:]])
625
        except NoSuchFile, e:
1563.2.25 by Robert Collins
Merge in upstream.
626
            if mode != 'w' or not create:
627
                raise
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
628
            self.write_header()
629
630
    def get_graph(self):
631
        graph = []
632
        for version_id, index in self._cache.iteritems():
633
            graph.append((version_id, index[4]))
634
        return graph
635
636
    def get_ancestry(self, versions):
637
        """See VersionedFile.get_ancestry."""
638
        version_idxs = []
639
        for version_id in versions:
640
            version_idxs.append(self._history.index(version_id))
641
        i = set(versions)
642
        for v in xrange(max(version_idxs), 0, -1):
643
            if self._history[v] in i:
644
                # include all its parents
645
                i.update(self._cache[self._history[v]][4])
646
        return list(i)
647
648
    def num_versions(self):
649
        return len(self._history)
650
651
    __len__ = num_versions
652
653
    def get_versions(self):
654
        return self._history
655
656
    def idx_to_name(self, idx):
657
        return self._history[idx]
658
659
    def lookup(self, version_id):
660
        assert version_id in self._cache
661
        return self._history.index(version_id)
662
663
    def add_version(self, version_id, options, pos, size, parents):
664
        """Add a version record to the index."""
665
        self._cache_version(version_id, options, pos, size, parents)
666
667
        content = "%s %s %s %s %s\n" % (version_id,
668
                                        ','.join(options),
669
                                        pos,
670
                                        size,
671
                                        ' '.join([str(self.lookup(vid)) for 
672
                                                  vid in parents]))
1563.2.13 by Robert Collins
InterVersionedFile implemented.
673
        self._transport.append(self._filename, StringIO(content))
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
674
675
    def has_version(self, version_id):
676
        """True if the version is in the index."""
677
        return self._cache.has_key(version_id)
678
679
    def get_position(self, version_id):
680
        """Return data position and size of specified version."""
681
        return (self._cache[version_id][2], \
682
                self._cache[version_id][3])
683
684
    def get_method(self, version_id):
685
        """Return compression method of specified version."""
686
        options = self._cache[version_id][1]
687
        if 'fulltext' in options:
688
            return 'fulltext'
689
        else:
690
            assert 'line-delta' in options
691
            return 'line-delta'
692
693
    def get_options(self, version_id):
694
        return self._cache[version_id][1]
695
696
    def get_parents(self, version_id):
697
        """Return parents of specified version."""
698
        return self._cache[version_id][4]
699
700
    def check_versions_present(self, version_ids):
701
        """Check that all specified versions are present."""
702
        version_ids = set(version_ids)
703
        for version_id in list(version_ids):
704
            if version_id in self._cache:
705
                version_ids.remove(version_id)
706
        if version_ids:
707
            raise RevisionNotPresent(list(version_ids)[0], self.filename)
708
709
710
class _KnitData(_KnitComponentFile):
711
    """Contents of the knit data file"""
712
713
    HEADER = "# bzr knit data 7\n"
714
1563.2.5 by Robert Collins
Remove unused transaction references from knit.py and the versionedfile interface.
715
    def __init__(self, transport, filename, mode):
716
        _KnitComponentFile.__init__(self, transport, filename, mode)
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
717
        self._file = None
718
        self._checked = False
719
720
    def _open_file(self):
721
        if self._file is None:
722
            try:
723
                self._file = self._transport.get(self._filename)
724
            except NoSuchFile:
725
                pass
726
        return self._file
727
728
    def add_record(self, version_id, digest, lines):
729
        """Write new text record to disk.  Returns the position in the
730
        file where it was written."""
731
        sio = StringIO()
732
        data_file = GzipFile(None, mode='wb', fileobj=sio)
733
        print >>data_file, "version %s %d %s" % (version_id, len(lines), digest)
734
        data_file.writelines(lines)
735
        print >>data_file, "end %s\n" % version_id
736
        data_file.close()
737
738
        content = sio.getvalue()
1563.2.13 by Robert Collins
InterVersionedFile implemented.
739
        start_pos = self._transport.append(self._filename, StringIO(content))
1563.2.4 by Robert Collins
First cut at including the knit implementation of versioned_file.
740
        return start_pos, len(content)
741
742
    def _parse_record(self, version_id, data):
743
        df = GzipFile(mode='rb', fileobj=StringIO(data))
744
        rec = df.readline().split()
745
        if len(rec) != 4:
746
            raise KnitCorrupt(self._filename, 'unexpected number of records')
747
        if rec[1] != version_id:
748
            raise KnitCorrupt(self.file.name, 
749
                              'unexpected version, wanted %r' % version_id)
750
        lines = int(rec[2])
751
        record_contents = self._read_record_contents(df, lines)
752
        l = df.readline()
753
        if l != 'end %s\n' % version_id:
754
            raise KnitCorrupt(self._filename, 'unexpected version end line %r, wanted %r' 
755
                        % (l, version_id))
756
        return record_contents, rec[3]
757
758
    def _read_record_contents(self, df, record_lines):
759
        """Read and return n lines from datafile."""
760
        r = []
761
        for i in range(record_lines):
762
            r.append(df.readline())
763
        return r
764
765
    def read_records_iter(self, records):
766
        """Read text records from data file and yield result.
767
768
        Each passed record is a tuple of (version_id, pos, len) and
769
        will be read in the given order.  Yields (version_id,
770
        contents, digest).
771
        """
772
773
        class ContinuousRange:
774
            def __init__(self, rec_id, pos, size):
775
                self.start_pos = pos
776
                self.end_pos = pos + size
777
                self.versions = [(rec_id, pos, size)]
778
779
            def add(self, rec_id, pos, size):
780
                if self.end_pos != pos:
781
                    return False
782
                self.end_pos = pos + size
783
                self.versions.append((rec_id, pos, size))
784
                return True
785
786
            def split(self, fp):
787
                for rec_id, pos, size in self.versions:
788
                    yield rec_id, fp.read(size)
789
790
        fp = self._open_file()
791
792
        # Loop through all records and try to collect as large
793
        # continuous region as possible to read.
794
        while records:
795
            record_id, pos, size = records.pop(0)
796
            continuous_range = ContinuousRange(record_id, pos, size)
797
            while records:
798
                record_id, pos, size = records[0]
799
                if continuous_range.add(record_id, pos, size):
800
                    del records[0]
801
                else:
802
                    break
803
            fp.seek(continuous_range.start_pos, 0)
804
            for record_id, data in continuous_range.split(fp):
805
                content, digest = self._parse_record(record_id, data)
806
                yield record_id, content, digest
807
808
        self._file = None
809
810
    def read_records(self, records):
811
        """Read records into a dictionary."""
812
        components = {}
813
        for record_id, content, digest in self.read_records_iter(records):
814
            components[record_id] = (content, digest)
815
        return components
816
1563.2.13 by Robert Collins
InterVersionedFile implemented.
817
818
class InterKnit(InterVersionedFile):
819
    """Optimised code paths for knit to knit operations."""
820
    
1563.2.16 by Robert Collins
Change WeaveStore into VersionedFileStore and make its versoined file class parameterisable.
821
    _matching_file_factory = KnitVersionedFile
1563.2.13 by Robert Collins
InterVersionedFile implemented.
822
    
823
    @staticmethod
824
    def is_compatible(source, target):
825
        """Be compatible with knits.  """
826
        try:
827
            return (isinstance(source, KnitVersionedFile) and
828
                    isinstance(target, KnitVersionedFile))
829
        except AttributeError:
830
            return False
831
1563.2.31 by Robert Collins
Convert Knit repositories to use knits.
832
    def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
1563.2.13 by Robert Collins
InterVersionedFile implemented.
833
        """See InterVersionedFile.join."""
834
        assert isinstance(self.source, KnitVersionedFile)
835
        assert isinstance(self.target, KnitVersionedFile)
836
837
        if version_ids is None:
838
            version_ids = self.source.versions()
1563.2.31 by Robert Collins
Convert Knit repositories to use knits.
839
        else:
840
            if not ignore_missing:
841
                self.source._check_versions_present(version_ids)
842
            else:
843
                version_ids = set(self.source.versions()).intersection(
844
                    set(version_ids))
845
1563.2.13 by Robert Collins
InterVersionedFile implemented.
846
        if not version_ids:
847
            return 0
848
849
        if pb is None:
850
            from bzrlib.progress import DummyProgress
851
            pb = DummyProgress()
852
853
        version_ids = list(version_ids)
854
        if None in version_ids:
855
            version_ids.remove(None)
856
857
        self.source_ancestry = set(self.source.get_ancestry(version_ids))
858
        this_versions = set(self.target._index.get_versions())
859
        needed_versions = self.source_ancestry - this_versions
860
        cross_check_versions = self.source_ancestry.intersection(this_versions)
861
        mismatched_versions = set()
862
        for version in cross_check_versions:
863
            # scan to include needed parents.
864
            n1 = set(self.target.get_parents(version))
865
            n2 = set(self.source.get_parents(version))
866
            if n1 != n2:
867
                # FIXME TEST this check for cycles being introduced works
868
                # the logic is we have a cycle if in our graph we are an
869
                # ancestor of any of the n2 revisions.
870
                for parent in n2:
871
                    if parent in n1:
872
                        # safe
873
                        continue
874
                    else:
875
                        parent_ancestors = self.source.get_ancestry(parent)
876
                        if version in parent_ancestors:
877
                            raise errors.GraphCycleError([parent, version])
878
                # ensure this parent will be available later.
879
                new_parents = n2.difference(n1)
880
                needed_versions.update(new_parents.difference(this_versions))
881
                mismatched_versions.add(version)
882
883
        if not needed_versions and not cross_check_versions:
884
            return 0
885
        full_list = topo_sort(self.source._index.get_graph())
886
887
        version_list = [i for i in full_list if (not self.target.has_version(i)
888
                        and i in needed_versions)]
889
890
        records = []
891
        for version_id in version_list:
892
            data_pos, data_size = self.source._index.get_position(version_id)
893
            records.append((version_id, data_pos, data_size))
894
895
        count = 0
896
        for version_id, lines, digest \
897
                in self.source._data.read_records_iter(records):
898
            options = self.source._index.get_options(version_id)
899
            parents = self.source._index.get_parents(version_id)
900
            
901
            for parent in parents:
902
                assert self.target.has_version(parent)
903
904
            if self.target.factory.annotated:
905
                # FIXME jrydberg: it should be possible to skip
906
                # re-annotating components if we know that we are
907
                # going to pull all revisions in the same order.
908
                new_version_id = version_id
909
                new_version_idx = self.target._index.num_versions()
910
                if 'fulltext' in options:
911
                    lines = self.target._reannotate_fulltext(self.source, lines,
912
                        new_version_id, new_version_idx)
913
                elif 'line-delta' in options:
914
                    lines = self.target._reannotate_line_delta(self.source, lines,
915
                        new_version_id, new_version_idx)
916
917
            count = count + 1
1563.2.33 by Robert Collins
Nicer progress updates during conversion to knits.
918
            pb.update("Joining knit", count, len(version_list))
1563.2.13 by Robert Collins
InterVersionedFile implemented.
919
920
            pos, size = self.target._data.add_record(version_id, digest, lines)
921
            self.target._index.add_version(version_id, options, pos, size, parents)
922
923
        for version in mismatched_versions:
924
            n1 = set(self.target.get_parents(version))
925
            n2 = set(self.source.get_parents(version))
926
            # write a combined record to our history.
927
            new_parents = self.target.get_parents(version) + list(n2.difference(n1))
928
            current_values = self.target._index._cache[version]
929
            self.target._index.add_version(version,
930
                                    current_values[1], 
931
                                    current_values[2],
932
                                    current_values[3],
933
                                    new_parents)
934
        pb.clear()
935
        return count
936
937
938
InterVersionedFile.register_optimiser(InterKnit)