/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

add ghost aware apis to knits.

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
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.
 
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
 
 
55
"""
 
56
 
 
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.
 
62
# move sha1 out of the content so that join is faster at verifying parents
 
63
# record content length ?
 
64
                  
 
65
 
 
66
from cStringIO import StringIO
 
67
import difflib
 
68
from difflib import SequenceMatcher
 
69
from gzip import GzipFile
 
70
import os
 
71
 
 
72
import bzrlib.errors as errors
 
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
 
79
from bzrlib.versionedfile import VersionedFile, InterVersionedFile
 
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."""
 
215
    k = KnitVersionedFile(transport, relpath, 'w', KnitPlainFactory)
 
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
 
 
234
    def __init__(self, relpath, transport, file_mode=None, access_mode=None, factory=None,
 
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
        """
 
240
        if access_mode is None:
 
241
            access_mode = 'w'
 
242
        assert access_mode in ('r', 'w'), "invalid mode specified %r" % access_mode
 
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
 
249
        self.factory = factory or KnitAnnotateFactory()
 
250
        self.writable = (access_mode == 'w')
 
251
        self.delta = delta
 
252
 
 
253
        self._index = _KnitIndex(transport, relpath + INDEX_SUFFIX,
 
254
            access_mode, create=create)
 
255
        self._data = _KnitData(transport, relpath + DATA_SUFFIX,
 
256
            access_mode, create=not len(self.versions()))
 
257
 
 
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
 
 
268
    def create_empty(self, name, transport, mode=None):
 
269
        return KnitVersionedFile(name, transport, factory=self.factory, delta=self.delta, create=True)
 
270
    
 
271
    def fix_parents(self, version, new_parents):
 
272
        """Fix the parents list for version.
 
273
        
 
274
        This is done by appending a new version to the index
 
275
        with identical data except for the parents list.
 
276
        the parents list must be a superset of the current
 
277
        list.
 
278
        """
 
279
        current_values = self._index._cache[version]
 
280
        assert set(current_values[4]).difference(set(new_parents)) == set()
 
281
        self._index.add_version(version,
 
282
                                current_values[1], 
 
283
                                current_values[2],
 
284
                                current_values[3],
 
285
                                new_parents)
 
286
 
 
287
    def get_graph_with_ghosts(self):
 
288
        """See VersionedFile.get_graph_with_ghosts()."""
 
289
        graph_items = self._index.get_graph()
 
290
        return dict(graph_items)
 
291
 
 
292
    @staticmethod
 
293
    def get_suffixes():
 
294
        """See VersionedFile.get_suffixes()."""
 
295
        return [DATA_SUFFIX, INDEX_SUFFIX]
 
296
 
 
297
    def has_ghost(self, version_id):
 
298
        """True if there is a ghost reference in the file to version_id."""
 
299
        # maybe we have it
 
300
        if self.has_version(version_id):
 
301
            return False
 
302
        # optimisable if needed by memoising the _ghosts set.
 
303
        items = self._index.get_graph()
 
304
        for node, parents in items:
 
305
            for parent in parents:
 
306
                if parent not in self._index._cache:
 
307
                    if parent == version_id:
 
308
                        return True
 
309
        return False
 
310
 
 
311
    def versions(self):
 
312
        """See VersionedFile.versions."""
 
313
        return self._index.get_versions()
 
314
 
 
315
    def has_version(self, version_id):
 
316
        """See VersionedFile.has_version."""
 
317
        return self._index.has_version(version_id)
 
318
 
 
319
    __contains__ = has_version
 
320
 
 
321
    def _merge_annotations(self, content, parents):
 
322
        """Merge annotations for content.  This is done by comparing
 
323
        the annotations based on changed to the text."""
 
324
        for parent_id in parents:
 
325
            merge_content = self._get_content(parent_id)
 
326
            seq = SequenceMatcher(None, merge_content.text(), content.text())
 
327
            for i, j, n in seq.get_matching_blocks():
 
328
                if n == 0:
 
329
                    continue
 
330
                content._lines[j:j+n] = merge_content._lines[i:i+n]
 
331
 
 
332
    def _get_components(self, version_id):
 
333
        """Return a list of (version_id, method, data) tuples that
 
334
        makes up version specified by version_id of the knit.
 
335
 
 
336
        The components should be applied in the order of the returned
 
337
        list.
 
338
 
 
339
        The basis knit will be used to the largest extent possible
 
340
        since it is assumed that accesses to it is faster.
 
341
        """
 
342
        # needed_revisions holds a list of (method, version_id) of
 
343
        # versions that is needed to be fetched to construct the final
 
344
        # version of the file.
 
345
        #
 
346
        # basis_revisions is a list of versions that needs to be
 
347
        # fetched but exists in the basis knit.
 
348
 
 
349
        basis = self.basis_knit
 
350
        needed_versions = []
 
351
        basis_versions = []
 
352
        cursor = version_id
 
353
 
 
354
        while 1:
 
355
            picked_knit = self
 
356
            if basis and basis._index.has_version(cursor):
 
357
                picked_knit = basis
 
358
                basis_versions.append(cursor)
 
359
            method = picked_knit._index.get_method(cursor)
 
360
            needed_versions.append((method, cursor))
 
361
            if method == 'fulltext':
 
362
                break
 
363
            cursor = picked_knit.get_parents(cursor)[0]
 
364
 
 
365
        components = {}
 
366
        if basis_versions:
 
367
            records = []
 
368
            for comp_id in basis_versions:
 
369
                data_pos, data_size = basis._index.get_data_position(comp_id)
 
370
                records.append((piece_id, data_pos, data_size))
 
371
            components.update(basis._data.read_records(records))
 
372
 
 
373
        records = []
 
374
        for comp_id in [vid for method, vid in needed_versions
 
375
                        if vid not in basis_versions]:
 
376
            data_pos, data_size = self._index.get_position(comp_id)
 
377
            records.append((comp_id, data_pos, data_size))
 
378
        components.update(self._data.read_records(records))
 
379
 
 
380
        # get_data_records returns a mapping with the version id as
 
381
        # index and the value as data.  The order the components need
 
382
        # to be applied is held by needed_versions (reversed).
 
383
        out = []
 
384
        for method, comp_id in reversed(needed_versions):
 
385
            out.append((comp_id, method, components[comp_id]))
 
386
 
 
387
        return out
 
388
 
 
389
    def _get_content(self, version_id):
 
390
        """Returns a content object that makes up the specified
 
391
        version."""
 
392
        if not self.has_version(version_id):
 
393
            raise RevisionNotPresent(version_id, self.filename)
 
394
 
 
395
        if self.basis_knit and version_id in self.basis_knit:
 
396
            return self.basis_knit._get_content(version_id)
 
397
 
 
398
        content = None
 
399
        components = self._get_components(version_id)
 
400
        for component_id, method, (data, digest) in components:
 
401
            version_idx = self._index.lookup(component_id)
 
402
            if method == 'fulltext':
 
403
                assert content is None
 
404
                content = self.factory.parse_fulltext(data, version_idx)
 
405
            elif method == 'line-delta':
 
406
                delta = self.factory.parse_line_delta(data, version_idx)
 
407
                content.apply_delta(delta)
 
408
 
 
409
        if 'no-eol' in self._index.get_options(version_id):
 
410
            line = content._lines[-1][1].rstrip('\n')
 
411
            content._lines[-1] = (content._lines[-1][0], line)
 
412
 
 
413
        if sha_strings(content.text()) != digest:
 
414
            raise KnitCorrupt(self.filename, 'sha-1 does not match')
 
415
 
 
416
        return content
 
417
 
 
418
    def _check_versions_present(self, version_ids):
 
419
        """Check that all specified versions are present."""
 
420
        version_ids = set(version_ids)
 
421
        for r in list(version_ids):
 
422
            if self._index.has_version(r):
 
423
                version_ids.remove(r)
 
424
        if version_ids:
 
425
            raise RevisionNotPresent(list(version_ids)[0], self.filename)
 
426
 
 
427
    def add_lines_with_ghosts(self, version_id, parents, lines):
 
428
        """See VersionedFile.add_lines_with_ghosts()."""
 
429
        self._check_add(version_id, lines)
 
430
        return self._add(version_id, lines[:], parents, self.delta)
 
431
 
 
432
    def add_lines(self, version_id, parents, lines):
 
433
        """See VersionedFile.add_lines."""
 
434
        self._check_add(version_id, lines)
 
435
        self._check_versions_present(parents)
 
436
        return self._add(version_id, lines[:], parents, self.delta)
 
437
 
 
438
    def _check_add(self, version_id, lines):
 
439
        """check that version_id and lines are safe to add."""
 
440
        assert self.writable, "knit is not opened for write"
 
441
        ### FIXME escape. RBC 20060228
 
442
        if contains_whitespace(version_id):
 
443
            raise InvalidRevisionId(version_id)
 
444
        if self.has_version(version_id):
 
445
            raise RevisionAlreadyPresent(version_id, self.filename)
 
446
 
 
447
        if False or __debug__:
 
448
            for l in lines:
 
449
                assert '\n' not in l[:-1]
 
450
 
 
451
    def _add(self, version_id, lines, parents, delta):
 
452
        """Add a set of lines on top of version specified by parents.
 
453
 
 
454
        If delta is true, compress the text as a line-delta against
 
455
        the first parent.
 
456
 
 
457
        Any versions not present will be converted into ghosts.
 
458
        """
 
459
        ghosts = []
 
460
        for parent in parents:
 
461
            if not self.has_version(parent):
 
462
                ghosts.append(parent)
 
463
 
 
464
        if delta and not len(parents)-len(ghosts):
 
465
            delta = False
 
466
 
 
467
        digest = sha_strings(lines)
 
468
        options = []
 
469
        if lines:
 
470
            if lines[-1][-1] != '\n':
 
471
                options.append('no-eol')
 
472
                lines[-1] = lines[-1] + '\n'
 
473
 
 
474
        lines = self.factory.make(lines, len(self._index))
 
475
        if self.factory.annotated and len(parents)-len(ghosts) > 0:
 
476
            # Merge annotations from parent texts if so is needed.
 
477
            self._merge_annotations(lines, parents)
 
478
 
 
479
        if len(parents)-len(ghosts) and delta:
 
480
            # To speed the extract of texts the delta chain is limited
 
481
            # to a fixed number of deltas.  This should minimize both
 
482
            # I/O and the time spend applying deltas.
 
483
            count = 0
 
484
            delta_parents = [parent for parent in parents if not parent in ghosts]
 
485
            first_parent = delta_parents[0]
 
486
            while count < 25:
 
487
                parent = delta_parents[0]
 
488
                method = self._index.get_method(parent)
 
489
                if method == 'fulltext':
 
490
                    break
 
491
                delta_parents = self._index.get_parents(parent)
 
492
                count = count + 1
 
493
            if method == 'line-delta':
 
494
                delta = False
 
495
 
 
496
        if delta:
 
497
            options.append('line-delta')
 
498
            content = self._get_content(first_parent)
 
499
            delta_hunks = content.line_delta(lines)
 
500
            store_lines = self.factory.lower_line_delta(delta_hunks)
 
501
        else:
 
502
            options.append('fulltext')
 
503
            store_lines = self.factory.lower_fulltext(lines)
 
504
 
 
505
        where, size = self._data.add_record(version_id, digest, store_lines)
 
506
        self._index.add_version(version_id, options, where, size, parents)
 
507
 
 
508
    def check(self, progress_bar=None):
 
509
        """See VersionedFile.check()."""
 
510
 
 
511
    def clone_text(self, new_version_id, old_version_id, parents):
 
512
        """See VersionedFile.clone_text()."""
 
513
        # FIXME RBC 20060228 make fast by only inserting an index with null delta.
 
514
        self.add_lines(new_version_id, parents, self.get_lines(old_version_id))
 
515
 
 
516
    def get_lines(self, version_id):
 
517
        """See VersionedFile.get_lines()."""
 
518
        return self._get_content(version_id).text()
 
519
 
 
520
    def iter_lines_added_or_present_in_versions(self, version_ids=None):
 
521
        """See VersionedFile.iter_lines_added_or_present_in_versions()."""
 
522
        if version_ids is None:
 
523
            version_ids = self.versions()
 
524
        # we dont care about inclusions, the caller cares.
 
525
        # but we need to setup a list of records to visit.
 
526
        # we need version_id, position, length
 
527
        version_id_records = []
 
528
        for version_id in version_ids:
 
529
            if not self.has_version(version_id):
 
530
                raise RevisionNotPresent(version_id, self.filename)
 
531
            data_pos, length = self._index.get_position(version_id)
 
532
            version_id_records.append((version_id, data_pos, length))
 
533
        for version_id, data, sha_value in \
 
534
            self._data.read_records_iter(version_id_records):
 
535
            method = self._index.get_method(version_id)
 
536
            version_idx = self._index.lookup(version_id)
 
537
            assert method in ('fulltext', 'line-delta')
 
538
            if method == 'fulltext':
 
539
                content = self.factory.parse_fulltext(data, version_idx)
 
540
                for line in content.text():
 
541
                    yield line
 
542
            else:
 
543
                delta = self.factory.parse_line_delta(data, version_idx)
 
544
                for start, end, count, lines in delta:
 
545
                    for origin, line in lines:
 
546
                        yield line
 
547
        
 
548
    def num_versions(self):
 
549
        """See VersionedFile.num_versions()."""
 
550
        return self._index.num_versions()
 
551
 
 
552
    __len__ = num_versions
 
553
 
 
554
    def annotate_iter(self, version_id):
 
555
        """See VersionedFile.annotate_iter."""
 
556
        content = self._get_content(version_id)
 
557
        for origin, text in content.annotate_iter():
 
558
            yield self._index.idx_to_name(origin), text
 
559
 
 
560
    def get_parents(self, version_id):
 
561
        """See VersionedFile.get_parents."""
 
562
        self._check_versions_present([version_id])
 
563
        return list(self._index.get_parents(version_id))
 
564
 
 
565
    def get_parents_with_ghosts(self, version_id):
 
566
        """See VersionedFile.get_parents."""
 
567
        self._check_versions_present([version_id])
 
568
        return list(self._index.get_parents_with_ghosts(version_id))
 
569
 
 
570
    def get_ancestry(self, versions):
 
571
        """See VersionedFile.get_ancestry."""
 
572
        if isinstance(versions, basestring):
 
573
            versions = [versions]
 
574
        if not versions:
 
575
            return []
 
576
        self._check_versions_present(versions)
 
577
        return self._index.get_ancestry(versions)
 
578
 
 
579
    def get_ancestry_with_ghosts(self, versions):
 
580
        """See VersionedFile.get_ancestry_with_ghosts."""
 
581
        if isinstance(versions, basestring):
 
582
            versions = [versions]
 
583
        if not versions:
 
584
            return []
 
585
        self._check_versions_present(versions)
 
586
        return self._index.get_ancestry_with_ghosts(versions)
 
587
 
 
588
    def _reannotate_line_delta(self, other, lines, new_version_id,
 
589
                               new_version_idx):
 
590
        """Re-annotate line-delta and return new delta."""
 
591
        new_delta = []
 
592
        for start, end, count, contents \
 
593
                in self.factory.parse_line_delta_iter(lines):
 
594
            new_lines = []
 
595
            for origin, line in contents:
 
596
                old_version_id = other._index.idx_to_name(origin)
 
597
                if old_version_id == new_version_id:
 
598
                    idx = new_version_idx
 
599
                else:
 
600
                    idx = self._index.lookup(old_version_id)
 
601
                new_lines.append((idx, line))
 
602
            new_delta.append((start, end, count, new_lines))
 
603
 
 
604
        return self.factory.lower_line_delta(new_delta)
 
605
 
 
606
    def _reannotate_fulltext(self, other, lines, new_version_id,
 
607
                             new_version_idx):
 
608
        """Re-annotate fulltext and return new version."""
 
609
        content = self.factory.parse_fulltext(lines, new_version_idx)
 
610
        new_lines = []
 
611
        for origin, line in content.annotate_iter():
 
612
            old_version_id = other._index.idx_to_name(origin)
 
613
            if old_version_id == new_version_id:
 
614
                idx = new_version_idx
 
615
            else:
 
616
                idx = self._index.lookup(old_version_id)
 
617
            new_lines.append((idx, line))
 
618
 
 
619
        return self.factory.lower_fulltext(KnitContent(new_lines))
 
620
 
 
621
    #@deprecated_method(zero_eight)
 
622
    def walk(self, version_ids):
 
623
        """See VersionedFile.walk."""
 
624
        # We take the short path here, and extract all relevant texts
 
625
        # and put them in a weave and let that do all the work.  Far
 
626
        # from optimal, but is much simpler.
 
627
        # FIXME RB 20060228 this really is inefficient!
 
628
        from bzrlib.weave import Weave
 
629
 
 
630
        w = Weave(self.filename)
 
631
        ancestry = self.get_ancestry(version_ids)
 
632
        sorted_graph = topo_sort(self._index.get_graph())
 
633
        version_list = [vid for vid in sorted_graph if vid in ancestry]
 
634
        
 
635
        for version_id in version_list:
 
636
            lines = self.get_lines(version_id)
 
637
            w.add_lines(version_id, self.get_parents(version_id), lines)
 
638
 
 
639
        for lineno, insert_id, dset, line in w.walk(version_ids):
 
640
            yield lineno, insert_id, dset, line
 
641
 
 
642
 
 
643
class _KnitComponentFile(object):
 
644
    """One of the files used to implement a knit database"""
 
645
 
 
646
    def __init__(self, transport, filename, mode):
 
647
        self._transport = transport
 
648
        self._filename = filename
 
649
        self._mode = mode
 
650
 
 
651
    def write_header(self):
 
652
        old_len = self._transport.append(self._filename, StringIO(self.HEADER))
 
653
        if old_len != 0:
 
654
            raise KnitCorrupt(self._filename, 'misaligned after writing header')
 
655
 
 
656
    def check_header(self, fp):
 
657
        line = fp.read(len(self.HEADER))
 
658
        if line != self.HEADER:
 
659
            raise KnitHeaderError(badline=line)
 
660
 
 
661
    def commit(self):
 
662
        """Commit is a nop."""
 
663
 
 
664
    def __repr__(self):
 
665
        return '%s(%s)' % (self.__class__.__name__, self._filename)
 
666
 
 
667
 
 
668
class _KnitIndex(_KnitComponentFile):
 
669
    """Manages knit index file.
 
670
 
 
671
    The index is already kept in memory and read on startup, to enable
 
672
    fast lookups of revision information.  The cursor of the index
 
673
    file is always pointing to the end, making it easy to append
 
674
    entries.
 
675
 
 
676
    _cache is a cache for fast mapping from version id to a Index
 
677
    object.
 
678
 
 
679
    _history is a cache for fast mapping from indexes to version ids.
 
680
 
 
681
    The index data format is dictionary compressed when it comes to
 
682
    parent references; a index entry may only have parents that with a
 
683
    lover index number.  As a result, the index is topological sorted.
 
684
 
 
685
    Duplicate entries may be written to the index for a single version id
 
686
    if this is done then the latter one completely replaces the former:
 
687
    this allows updates to correct version and parent information. 
 
688
    Note that the two entries may share the delta, and that successive
 
689
    annotations and references MUST point to the first entry.
 
690
    """
 
691
 
 
692
    HEADER = "# bzr knit index 7\n"
 
693
 
 
694
    def _cache_version(self, version_id, options, pos, size, parents):
 
695
        val = (version_id, options, pos, size, parents)
 
696
        self._cache[version_id] = val
 
697
        if not version_id in self._history:
 
698
            self._history.append(version_id)
 
699
 
 
700
    def _iter_index(self, fp):
 
701
        lines = fp.read()
 
702
        for l in lines.splitlines(False):
 
703
            yield l.split()
 
704
 
 
705
    def __init__(self, transport, filename, mode, create=False):
 
706
        _KnitComponentFile.__init__(self, transport, filename, mode)
 
707
        self._cache = {}
 
708
        # position in _history is the 'official' index for a revision
 
709
        # but the values may have come from a newer entry.
 
710
        # so - wc -l of a knit index is != the number of uniqe names
 
711
        # in the weave.
 
712
        self._history = []
 
713
        try:
 
714
            fp = self._transport.get(self._filename)
 
715
            self.check_header(fp)
 
716
            for rec in self._iter_index(fp):
 
717
                parents = self._parse_parents(rec[4:])
 
718
                self._cache_version(rec[0], rec[1].split(','), int(rec[2]), int(rec[3]),
 
719
                    parents)
 
720
        except NoSuchFile, e:
 
721
            if mode != 'w' or not create:
 
722
                raise
 
723
            self.write_header()
 
724
 
 
725
    def _parse_parents(self, compressed_parents):
 
726
        """convert a list of string parent values into version ids.
 
727
 
 
728
        ints are looked up in the index.
 
729
        .FOO values are ghosts and converted in to FOO.
 
730
        """
 
731
        result = []
 
732
        for value in compressed_parents:
 
733
            if value.startswith('.'):
 
734
                result.append(value[1:])
 
735
            else:
 
736
                result.append(self._history[int(value)])
 
737
        return result
 
738
 
 
739
    def get_graph(self):
 
740
        graph = []
 
741
        for version_id, index in self._cache.iteritems():
 
742
            graph.append((version_id, index[4]))
 
743
        return graph
 
744
 
 
745
    def get_ancestry(self, versions):
 
746
        """See VersionedFile.get_ancestry."""
 
747
        # get a graph of all the mentioned versions:
 
748
        graph = {}
 
749
        pending = set(versions)
 
750
        while len(pending):
 
751
            version = pending.pop()
 
752
#            try:
 
753
            parents = self._cache[version][4]
 
754
#            except KeyError:
 
755
#                # ghost, elide it.
 
756
#                pass
 
757
#            else:
 
758
            # got the parents ok
 
759
            # trim ghosts
 
760
            parents = [parent for parent in parents if parent in self._cache]
 
761
            for parent in parents:
 
762
                # if not completed and not a ghost
 
763
                if parent not in graph:
 
764
                    pending.add(parent)
 
765
            graph[version] = parents
 
766
        return topo_sort(graph.items())
 
767
 
 
768
    def get_ancestry_with_ghosts(self, versions):
 
769
        """See VersionedFile.get_ancestry_with_ghosts."""
 
770
        # get a graph of all the mentioned versions:
 
771
        graph = {}
 
772
        pending = set(versions)
 
773
        while len(pending):
 
774
            version = pending.pop()
 
775
            try:
 
776
                parents = self._cache[version][4]
 
777
            except KeyError:
 
778
                # ghost, fake it
 
779
                graph[version] = []
 
780
                pass
 
781
            else:
 
782
                # got the parents ok
 
783
                for parent in parents:
 
784
                    if parent not in graph:
 
785
                        pending.add(parent)
 
786
                graph[version] = parents
 
787
        return topo_sort(graph.items())
 
788
 
 
789
    def num_versions(self):
 
790
        return len(self._history)
 
791
 
 
792
    __len__ = num_versions
 
793
 
 
794
    def get_versions(self):
 
795
        return self._history
 
796
 
 
797
    def idx_to_name(self, idx):
 
798
        return self._history[idx]
 
799
 
 
800
    def lookup(self, version_id):
 
801
        assert version_id in self._cache
 
802
        return self._history.index(version_id)
 
803
 
 
804
    def _version_list_to_index(self, versions):
 
805
        result_list = []
 
806
        for version in versions:
 
807
            if version in self._cache:
 
808
                result_list.append(str(self._history.index(version)))
 
809
            else:
 
810
                result_list.append('.' + version)
 
811
        return ' '.join(result_list)
 
812
 
 
813
    def add_version(self, version_id, options, pos, size, parents):
 
814
        """Add a version record to the index."""
 
815
        self._cache_version(version_id, options, pos, size, parents)
 
816
 
 
817
        content = "%s %s %s %s %s\n" % (version_id,
 
818
                                        ','.join(options),
 
819
                                        pos,
 
820
                                        size,
 
821
                                        self._version_list_to_index(parents))
 
822
        self._transport.append(self._filename, StringIO(content))
 
823
 
 
824
    def has_version(self, version_id):
 
825
        """True if the version is in the index."""
 
826
        return self._cache.has_key(version_id)
 
827
 
 
828
    def get_position(self, version_id):
 
829
        """Return data position and size of specified version."""
 
830
        return (self._cache[version_id][2], \
 
831
                self._cache[version_id][3])
 
832
 
 
833
    def get_method(self, version_id):
 
834
        """Return compression method of specified version."""
 
835
        options = self._cache[version_id][1]
 
836
        if 'fulltext' in options:
 
837
            return 'fulltext'
 
838
        else:
 
839
            assert 'line-delta' in options
 
840
            return 'line-delta'
 
841
 
 
842
    def get_options(self, version_id):
 
843
        return self._cache[version_id][1]
 
844
 
 
845
    def get_parents(self, version_id):
 
846
        """Return parents of specified version ignoring ghosts."""
 
847
        return [parent for parent in self._cache[version_id][4] 
 
848
                if parent in self._cache]
 
849
 
 
850
    def get_parents_with_ghosts(self, version_id):
 
851
        """Return parents of specified version wth ghosts."""
 
852
        return self._cache[version_id][4] 
 
853
 
 
854
    def check_versions_present(self, version_ids):
 
855
        """Check that all specified versions are present."""
 
856
        version_ids = set(version_ids)
 
857
        for version_id in list(version_ids):
 
858
            if version_id in self._cache:
 
859
                version_ids.remove(version_id)
 
860
        if version_ids:
 
861
            raise RevisionNotPresent(list(version_ids)[0], self.filename)
 
862
 
 
863
 
 
864
class _KnitData(_KnitComponentFile):
 
865
    """Contents of the knit data file"""
 
866
 
 
867
    HEADER = "# bzr knit data 7\n"
 
868
 
 
869
    def __init__(self, transport, filename, mode, create=False):
 
870
        _KnitComponentFile.__init__(self, transport, filename, mode)
 
871
        self._file = None
 
872
        self._checked = False
 
873
        if create:
 
874
            self._transport.put(self._filename, StringIO(''))
 
875
 
 
876
    def _open_file(self):
 
877
        if self._file is None:
 
878
            try:
 
879
                self._file = self._transport.get(self._filename)
 
880
            except NoSuchFile:
 
881
                pass
 
882
        return self._file
 
883
 
 
884
    def add_record(self, version_id, digest, lines):
 
885
        """Write new text record to disk.  Returns the position in the
 
886
        file where it was written."""
 
887
        sio = StringIO()
 
888
        data_file = GzipFile(None, mode='wb', fileobj=sio)
 
889
        print >>data_file, "version %s %d %s" % (version_id, len(lines), digest)
 
890
        data_file.writelines(lines)
 
891
        print >>data_file, "end %s\n" % version_id
 
892
        data_file.close()
 
893
 
 
894
        content = sio.getvalue()
 
895
        start_pos = self._transport.append(self._filename, StringIO(content))
 
896
        return start_pos, len(content)
 
897
 
 
898
    def _parse_record(self, version_id, data):
 
899
        df = GzipFile(mode='rb', fileobj=StringIO(data))
 
900
        rec = df.readline().split()
 
901
        if len(rec) != 4:
 
902
            raise KnitCorrupt(self._filename, 'unexpected number of records')
 
903
        if rec[1] != version_id:
 
904
            raise KnitCorrupt(self.file.name, 
 
905
                              'unexpected version, wanted %r' % version_id)
 
906
        lines = int(rec[2])
 
907
        record_contents = self._read_record_contents(df, lines)
 
908
        l = df.readline()
 
909
        if l != 'end %s\n' % version_id:
 
910
            raise KnitCorrupt(self._filename, 'unexpected version end line %r, wanted %r' 
 
911
                        % (l, version_id))
 
912
        return record_contents, rec[3]
 
913
 
 
914
    def _read_record_contents(self, df, record_lines):
 
915
        """Read and return n lines from datafile."""
 
916
        r = []
 
917
        for i in range(record_lines):
 
918
            r.append(df.readline())
 
919
        return r
 
920
 
 
921
    def read_records_iter(self, records):
 
922
        """Read text records from data file and yield result.
 
923
 
 
924
        Each passed record is a tuple of (version_id, pos, len) and
 
925
        will be read in the given order.  Yields (version_id,
 
926
        contents, digest).
 
927
        """
 
928
 
 
929
        class ContinuousRange:
 
930
            def __init__(self, rec_id, pos, size):
 
931
                self.start_pos = pos
 
932
                self.end_pos = pos + size
 
933
                self.versions = [(rec_id, pos, size)]
 
934
 
 
935
            def add(self, rec_id, pos, size):
 
936
                if self.end_pos != pos:
 
937
                    return False
 
938
                self.end_pos = pos + size
 
939
                self.versions.append((rec_id, pos, size))
 
940
                return True
 
941
 
 
942
            def split(self, fp):
 
943
                for rec_id, pos, size in self.versions:
 
944
                    yield rec_id, fp.read(size)
 
945
 
 
946
        # We take it that the transport optimizes the fetching as good
 
947
        # as possible (ie, reads continous ranges.)
 
948
        response = self._transport.readv(self._filename,
 
949
            [(pos, size) for version_id, pos, size in records])
 
950
 
 
951
        for (record_id, pos, size), (pos, data) in zip(records, response):
 
952
            content, digest = self._parse_record(record_id, data)
 
953
            yield record_id, content, digest
 
954
 
 
955
    def read_records(self, records):
 
956
        """Read records into a dictionary."""
 
957
        components = {}
 
958
        for record_id, content, digest in self.read_records_iter(records):
 
959
            components[record_id] = (content, digest)
 
960
        return components
 
961
 
 
962
 
 
963
class InterKnit(InterVersionedFile):
 
964
    """Optimised code paths for knit to knit operations."""
 
965
    
 
966
    _matching_file_factory = KnitVersionedFile
 
967
    
 
968
    @staticmethod
 
969
    def is_compatible(source, target):
 
970
        """Be compatible with knits.  """
 
971
        try:
 
972
            return (isinstance(source, KnitVersionedFile) and
 
973
                    isinstance(target, KnitVersionedFile))
 
974
        except AttributeError:
 
975
            return False
 
976
 
 
977
    def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
 
978
        """See InterVersionedFile.join."""
 
979
        assert isinstance(self.source, KnitVersionedFile)
 
980
        assert isinstance(self.target, KnitVersionedFile)
 
981
 
 
982
        if version_ids is None:
 
983
            version_ids = self.source.versions()
 
984
        else:
 
985
            if not ignore_missing:
 
986
                self.source._check_versions_present(version_ids)
 
987
            else:
 
988
                version_ids = set(self.source.versions()).intersection(
 
989
                    set(version_ids))
 
990
 
 
991
        if not version_ids:
 
992
            return 0
 
993
 
 
994
        if pb is None:
 
995
            from bzrlib.progress import DummyProgress
 
996
            pb = DummyProgress()
 
997
 
 
998
        version_ids = list(version_ids)
 
999
        if None in version_ids:
 
1000
            version_ids.remove(None)
 
1001
 
 
1002
        self.source_ancestry = set(self.source.get_ancestry(version_ids))
 
1003
        this_versions = set(self.target._index.get_versions())
 
1004
        needed_versions = self.source_ancestry - this_versions
 
1005
        cross_check_versions = self.source_ancestry.intersection(this_versions)
 
1006
        mismatched_versions = set()
 
1007
        for version in cross_check_versions:
 
1008
            # scan to include needed parents.
 
1009
            n1 = set(self.target.get_parents_with_ghosts(version))
 
1010
            n2 = set(self.source.get_parents_with_ghosts(version))
 
1011
            if n1 != n2:
 
1012
                # FIXME TEST this check for cycles being introduced works
 
1013
                # the logic is we have a cycle if in our graph we are an
 
1014
                # ancestor of any of the n2 revisions.
 
1015
                for parent in n2:
 
1016
                    if parent in n1:
 
1017
                        # safe
 
1018
                        continue
 
1019
                    else:
 
1020
                        parent_ancestors = self.source.get_ancestry(parent)
 
1021
                        if version in parent_ancestors:
 
1022
                            raise errors.GraphCycleError([parent, version])
 
1023
                # ensure this parent will be available later.
 
1024
                new_parents = n2.difference(n1)
 
1025
                needed_versions.update(new_parents.difference(this_versions))
 
1026
                mismatched_versions.add(version)
 
1027
 
 
1028
        if not needed_versions and not cross_check_versions:
 
1029
            return 0
 
1030
        full_list = topo_sort(self.source.get_graph())
 
1031
 
 
1032
        version_list = [i for i in full_list if (not self.target.has_version(i)
 
1033
                        and i in needed_versions)]
 
1034
 
 
1035
        records = []
 
1036
        for version_id in version_list:
 
1037
            data_pos, data_size = self.source._index.get_position(version_id)
 
1038
            records.append((version_id, data_pos, data_size))
 
1039
 
 
1040
        count = 0
 
1041
        for version_id, lines, digest \
 
1042
                in self.source._data.read_records_iter(records):
 
1043
            options = self.source._index.get_options(version_id)
 
1044
            parents = self.source._index.get_parents_with_ghosts(version_id)
 
1045
            
 
1046
            for parent in parents:
 
1047
                # if source has the parent, we must hav grabbed it first.
 
1048
                assert (self.target.has_version(parent) or not
 
1049
                        self.source.has_version(parent))
 
1050
 
 
1051
            if self.target.factory.annotated:
 
1052
                # FIXME jrydberg: it should be possible to skip
 
1053
                # re-annotating components if we know that we are
 
1054
                # going to pull all revisions in the same order.
 
1055
                new_version_id = version_id
 
1056
                new_version_idx = self.target._index.num_versions()
 
1057
                if 'fulltext' in options:
 
1058
                    lines = self.target._reannotate_fulltext(self.source, lines,
 
1059
                        new_version_id, new_version_idx)
 
1060
                elif 'line-delta' in options:
 
1061
                    lines = self.target._reannotate_line_delta(self.source, lines,
 
1062
                        new_version_id, new_version_idx)
 
1063
 
 
1064
            count = count + 1
 
1065
            pb.update("Joining knit", count, len(version_list))
 
1066
 
 
1067
            pos, size = self.target._data.add_record(version_id, digest, lines)
 
1068
            self.target._index.add_version(version_id, options, pos, size, parents)
 
1069
 
 
1070
        for version in mismatched_versions:
 
1071
            n1 = set(self.target.get_parents_with_ghosts(version))
 
1072
            n2 = set(self.source.get_parents_with_ghosts(version))
 
1073
            # write a combined record to our history preserving the current 
 
1074
            # parents as first in the list
 
1075
            new_parents = self.target.get_parents_with_ghosts(version) + list(n2.difference(n1))
 
1076
            self.target.fix_parents(version, new_parents)
 
1077
        pb.clear()
 
1078
        return count
 
1079
 
 
1080
 
 
1081
InterVersionedFile.register_optimiser(InterKnit)