~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

  • Committer: John Arbash Meinel
  • Date: 2006-10-10 06:26:39 UTC
  • mto: This revision was merged to the branch mainline in revision 2070.
  • Revision ID: john@arbash-meinel.com-20061010062639-6d527d0f9a3401d8
Catch an exception while opening /dev/urandom rather than using os.path.exists()

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
# Modified by Aaron Bentley <aaron.bentley@utoronto.ca>
 
6
#
 
7
# This program is free software; you can redistribute it and/or modify
 
8
# it under the terms of the GNU General Public License as published by
 
9
# the Free Software Foundation; either version 2 of the License, or
 
10
# (at your option) any later version.
 
11
#
 
12
# This program is distributed in the hope that it will be useful,
 
13
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
14
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
15
# GNU General Public License for more details.
 
16
#
 
17
# You should have received a copy of the GNU General Public License
 
18
# along with this program; if not, write to the Free Software
 
19
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
20
 
 
21
"""Knit versionedfile implementation.
 
22
 
 
23
A knit is a versioned file implementation that supports efficient append only
 
24
updates.
 
25
 
 
26
Knit file layout:
 
27
lifeless: the data file is made up of "delta records".  each delta record has a delta header 
 
28
that contains; (1) a version id, (2) the size of the delta (in lines), and (3)  the digest of 
 
29
the -expanded data- (ie, the delta applied to the parent).  the delta also ends with a 
 
30
end-marker; simply "end VERSION"
 
31
 
 
32
delta can be line or full contents.a
 
33
... the 8's there are the index number of the annotation.
 
34
version robertc@robertcollins.net-20051003014215-ee2990904cc4c7ad 7 c7d23b2a5bd6ca00e8e266cec0ec228158ee9f9e
 
35
59,59,3
 
36
8
 
37
8         if ie.executable:
 
38
8             e.set('executable', 'yes')
 
39
130,130,2
 
40
8         if elt.get('executable') == 'yes':
 
41
8             ie.executable = True
 
42
end robertc@robertcollins.net-20051003014215-ee2990904cc4c7ad 
 
43
 
 
44
 
 
45
whats in an index:
 
46
09:33 < jrydberg> lifeless: each index is made up of a tuple of; version id, options, position, size, parents
 
47
09:33 < jrydberg> lifeless: the parents are currently dictionary compressed
 
48
09:33 < jrydberg> lifeless: (meaning it currently does not support ghosts)
 
49
09:33 < lifeless> right
 
50
09:33 < jrydberg> lifeless: the position and size is the range in the data file
 
51
 
 
52
 
 
53
so the index sequence is the dictionary compressed sequence number used
 
54
in the deltas to provide line annotation
 
55
 
 
56
"""
 
57
 
 
58
# TODOS:
 
59
# 10:16 < lifeless> make partial index writes safe
 
60
# 10:16 < lifeless> implement 'knit.check()' like weave.check()
 
61
# 10:17 < lifeless> record known ghosts so we can detect when they are filled in rather than the current 'reweave 
 
62
#                    always' approach.
 
63
# move sha1 out of the content so that join is faster at verifying parents
 
64
# record content length ?
 
65
                  
 
66
 
 
67
from copy import copy
 
68
from cStringIO import StringIO
 
69
import difflib
 
70
from itertools import izip, chain
 
71
import operator
 
72
import os
 
73
import sys
 
74
import warnings
 
75
 
 
76
import bzrlib
 
77
from bzrlib import (
 
78
    cache_utf8,
 
79
    errors,
 
80
    progress,
 
81
    )
 
82
from bzrlib.errors import FileExists, NoSuchFile, KnitError, \
 
83
        InvalidRevisionId, KnitCorrupt, KnitHeaderError, \
 
84
        RevisionNotPresent, RevisionAlreadyPresent
 
85
from bzrlib.tuned_gzip import GzipFile
 
86
from bzrlib.trace import mutter
 
87
from bzrlib.osutils import contains_whitespace, contains_linebreaks, \
 
88
     sha_strings
 
89
from bzrlib.symbol_versioning import DEPRECATED_PARAMETER, deprecated_passed
 
90
from bzrlib.tsort import topo_sort
 
91
import bzrlib.weave
 
92
from bzrlib.versionedfile import VersionedFile, InterVersionedFile
 
93
 
 
94
 
 
95
# TODO: Split out code specific to this format into an associated object.
 
96
 
 
97
# TODO: Can we put in some kind of value to check that the index and data
 
98
# files belong together?
 
99
 
 
100
# TODO: accommodate binaries, perhaps by storing a byte count
 
101
 
 
102
# TODO: function to check whole file
 
103
 
 
104
# TODO: atomically append data, then measure backwards from the cursor
 
105
# position after writing to work out where it was located.  we may need to
 
106
# bypass python file buffering.
 
107
 
 
108
DATA_SUFFIX = '.knit'
 
109
INDEX_SUFFIX = '.kndx'
 
110
 
 
111
 
 
112
class KnitContent(object):
 
113
    """Content of a knit version to which deltas can be applied."""
 
114
 
 
115
    def __init__(self, lines):
 
116
        self._lines = lines
 
117
 
 
118
    def annotate_iter(self):
 
119
        """Yield tuples of (origin, text) for each content line."""
 
120
        for origin, text in self._lines:
 
121
            yield origin, text
 
122
 
 
123
    def annotate(self):
 
124
        """Return a list of (origin, text) tuples."""
 
125
        return list(self.annotate_iter())
 
126
 
 
127
    def line_delta_iter(self, new_lines):
 
128
        """Generate line-based delta from this content to new_lines."""
 
129
        new_texts = [text for origin, text in new_lines._lines]
 
130
        old_texts = [text for origin, text in self._lines]
 
131
        s = KnitSequenceMatcher(None, old_texts, new_texts)
 
132
        for op in s.get_opcodes():
 
133
            if op[0] == 'equal':
 
134
                continue
 
135
            #     ofrom   oto   length        data
 
136
            yield (op[1], op[2], op[4]-op[3], new_lines._lines[op[3]:op[4]])
 
137
 
 
138
    def line_delta(self, new_lines):
 
139
        return list(self.line_delta_iter(new_lines))
 
140
 
 
141
    def text(self):
 
142
        return [text for origin, text in self._lines]
 
143
 
 
144
    def copy(self):
 
145
        return KnitContent(self._lines[:])
 
146
 
 
147
 
 
148
class _KnitFactory(object):
 
149
    """Base factory for creating content objects."""
 
150
 
 
151
    def make(self, lines, version):
 
152
        num_lines = len(lines)
 
153
        return KnitContent(zip([version] * num_lines, lines))
 
154
 
 
155
 
 
156
class KnitAnnotateFactory(_KnitFactory):
 
157
    """Factory for creating annotated Content objects."""
 
158
 
 
159
    annotated = True
 
160
 
 
161
    def parse_fulltext(self, content, version):
 
162
        """Convert fulltext to internal representation
 
163
 
 
164
        fulltext content is of the format
 
165
        revid(utf8) plaintext\n
 
166
        internal representation is of the format:
 
167
        (revid, plaintext)
 
168
        """
 
169
        decode_utf8 = cache_utf8.decode
 
170
        lines = []
 
171
        for line in content:
 
172
            origin, text = line.split(' ', 1)
 
173
            lines.append((decode_utf8(origin), text))
 
174
        return KnitContent(lines)
 
175
 
 
176
    def parse_line_delta_iter(self, lines):
 
177
        for result_item in self.parse_line_delta[lines]:
 
178
            yield result_item
 
179
 
 
180
    def parse_line_delta(self, lines, version):
 
181
        """Convert a line based delta into internal representation.
 
182
 
 
183
        line delta is in the form of:
 
184
        intstart intend intcount
 
185
        1..count lines:
 
186
        revid(utf8) newline\n
 
187
        internal representation is
 
188
        (start, end, count, [1..count tuples (revid, newline)])
 
189
        """
 
190
        decode_utf8 = cache_utf8.decode
 
191
        result = []
 
192
        lines = iter(lines)
 
193
        next = lines.next
 
194
        # walk through the lines parsing.
 
195
        for header in lines:
 
196
            start, end, count = [int(n) for n in header.split(',')]
 
197
            contents = []
 
198
            remaining = count
 
199
            while remaining:
 
200
                origin, text = next().split(' ', 1)
 
201
                remaining -= 1
 
202
                contents.append((decode_utf8(origin), text))
 
203
            result.append((start, end, count, contents))
 
204
        return result
 
205
 
 
206
    def lower_fulltext(self, content):
 
207
        """convert a fulltext content record into a serializable form.
 
208
 
 
209
        see parse_fulltext which this inverts.
 
210
        """
 
211
        encode_utf8 = cache_utf8.encode
 
212
        return ['%s %s' % (encode_utf8(o), t) for o, t in content._lines]
 
213
 
 
214
    def lower_line_delta(self, delta):
 
215
        """convert a delta into a serializable form.
 
216
 
 
217
        See parse_line_delta which this inverts.
 
218
        """
 
219
        encode_utf8 = cache_utf8.encode
 
220
        out = []
 
221
        for start, end, c, lines in delta:
 
222
            out.append('%d,%d,%d\n' % (start, end, c))
 
223
            out.extend(encode_utf8(origin) + ' ' + text
 
224
                       for origin, text in lines)
 
225
        return out
 
226
 
 
227
 
 
228
class KnitPlainFactory(_KnitFactory):
 
229
    """Factory for creating plain Content objects."""
 
230
 
 
231
    annotated = False
 
232
 
 
233
    def parse_fulltext(self, content, version):
 
234
        """This parses an unannotated fulltext.
 
235
 
 
236
        Note that this is not a noop - the internal representation
 
237
        has (versionid, line) - its just a constant versionid.
 
238
        """
 
239
        return self.make(content, version)
 
240
 
 
241
    def parse_line_delta_iter(self, lines, version):
 
242
        while lines:
 
243
            header = lines.pop(0)
 
244
            start, end, c = [int(n) for n in header.split(',')]
 
245
            yield start, end, c, zip([version] * c, lines[:c])
 
246
            del lines[:c]
 
247
 
 
248
    def parse_line_delta(self, lines, version):
 
249
        return list(self.parse_line_delta_iter(lines, version))
 
250
    
 
251
    def lower_fulltext(self, content):
 
252
        return content.text()
 
253
 
 
254
    def lower_line_delta(self, delta):
 
255
        out = []
 
256
        for start, end, c, lines in delta:
 
257
            out.append('%d,%d,%d\n' % (start, end, c))
 
258
            out.extend([text for origin, text in lines])
 
259
        return out
 
260
 
 
261
 
 
262
def make_empty_knit(transport, relpath):
 
263
    """Construct a empty knit at the specified location."""
 
264
    k = KnitVersionedFile(transport, relpath, 'w', KnitPlainFactory)
 
265
    k._data._open_file()
 
266
 
 
267
 
 
268
class KnitVersionedFile(VersionedFile):
 
269
    """Weave-like structure with faster random access.
 
270
 
 
271
    A knit stores a number of texts and a summary of the relationships
 
272
    between them.  Texts are identified by a string version-id.  Texts
 
273
    are normally stored and retrieved as a series of lines, but can
 
274
    also be passed as single strings.
 
275
 
 
276
    Lines are stored with the trailing newline (if any) included, to
 
277
    avoid special cases for files with no final newline.  Lines are
 
278
    composed of 8-bit characters, not unicode.  The combination of
 
279
    these approaches should mean any 'binary' file can be safely
 
280
    stored and retrieved.
 
281
    """
 
282
 
 
283
    def __init__(self, relpath, transport, file_mode=None, access_mode=None,
 
284
                 factory=None, basis_knit=DEPRECATED_PARAMETER, delta=True,
 
285
                 create=False, create_parent_dir=False, delay_create=False,
 
286
                 dir_mode=None):
 
287
        """Construct a knit at location specified by relpath.
 
288
        
 
289
        :param create: If not True, only open an existing knit.
 
290
        :param create_parent_dir: If True, create the parent directory if 
 
291
            creating the file fails. (This is used for stores with 
 
292
            hash-prefixes that may not exist yet)
 
293
        :param delay_create: The calling code is aware that the knit won't 
 
294
            actually be created until the first data is stored.
 
295
        """
 
296
        if deprecated_passed(basis_knit):
 
297
            warnings.warn("KnitVersionedFile.__(): The basis_knit parameter is"
 
298
                 " deprecated as of bzr 0.9.",
 
299
                 DeprecationWarning, stacklevel=2)
 
300
        if access_mode is None:
 
301
            access_mode = 'w'
 
302
        super(KnitVersionedFile, self).__init__(access_mode)
 
303
        assert access_mode in ('r', 'w'), "invalid mode specified %r" % access_mode
 
304
        self.transport = transport
 
305
        self.filename = relpath
 
306
        self.factory = factory or KnitAnnotateFactory()
 
307
        self.writable = (access_mode == 'w')
 
308
        self.delta = delta
 
309
 
 
310
        self._index = _KnitIndex(transport, relpath + INDEX_SUFFIX,
 
311
            access_mode, create=create, file_mode=file_mode,
 
312
            create_parent_dir=create_parent_dir, delay_create=delay_create,
 
313
            dir_mode=dir_mode)
 
314
        self._data = _KnitData(transport, relpath + DATA_SUFFIX,
 
315
            access_mode, create=create and not len(self), file_mode=file_mode,
 
316
            create_parent_dir=create_parent_dir, delay_create=delay_create,
 
317
            dir_mode=dir_mode)
 
318
 
 
319
    def __repr__(self):
 
320
        return '%s(%s)' % (self.__class__.__name__, 
 
321
                           self.transport.abspath(self.filename))
 
322
    
 
323
    def _add_delta(self, version_id, parents, delta_parent, sha1, noeol, delta):
 
324
        """See VersionedFile._add_delta()."""
 
325
        self._check_add(version_id, []) # should we check the lines ?
 
326
        self._check_versions_present(parents)
 
327
        present_parents = []
 
328
        ghosts = []
 
329
        parent_texts = {}
 
330
        for parent in parents:
 
331
            if not self.has_version(parent):
 
332
                ghosts.append(parent)
 
333
            else:
 
334
                present_parents.append(parent)
 
335
 
 
336
        if delta_parent is None:
 
337
            # reconstitute as full text.
 
338
            assert len(delta) == 1 or len(delta) == 0
 
339
            if len(delta):
 
340
                assert delta[0][0] == 0
 
341
                assert delta[0][1] == 0, delta[0][1]
 
342
            return super(KnitVersionedFile, self)._add_delta(version_id,
 
343
                                                             parents,
 
344
                                                             delta_parent,
 
345
                                                             sha1,
 
346
                                                             noeol,
 
347
                                                             delta)
 
348
 
 
349
        digest = sha1
 
350
 
 
351
        options = []
 
352
        if noeol:
 
353
            options.append('no-eol')
 
354
 
 
355
        if delta_parent is not None:
 
356
            # determine the current delta chain length.
 
357
            # To speed the extract of texts the delta chain is limited
 
358
            # to a fixed number of deltas.  This should minimize both
 
359
            # I/O and the time spend applying deltas.
 
360
            count = 0
 
361
            delta_parents = [delta_parent]
 
362
            while count < 25:
 
363
                parent = delta_parents[0]
 
364
                method = self._index.get_method(parent)
 
365
                if method == 'fulltext':
 
366
                    break
 
367
                delta_parents = self._index.get_parents(parent)
 
368
                count = count + 1
 
369
            if method == 'line-delta':
 
370
                # did not find a fulltext in the delta limit.
 
371
                # just do a normal insertion.
 
372
                return super(KnitVersionedFile, self)._add_delta(version_id,
 
373
                                                                 parents,
 
374
                                                                 delta_parent,
 
375
                                                                 sha1,
 
376
                                                                 noeol,
 
377
                                                                 delta)
 
378
 
 
379
        options.append('line-delta')
 
380
        store_lines = self.factory.lower_line_delta(delta)
 
381
 
 
382
        where, size = self._data.add_record(version_id, digest, store_lines)
 
383
        self._index.add_version(version_id, options, where, size, parents)
 
384
 
 
385
    def _add_raw_records(self, records, data):
 
386
        """Add all the records 'records' with data pre-joined in 'data'.
 
387
 
 
388
        :param records: A list of tuples(version_id, options, parents, size).
 
389
        :param data: The data for the records. When it is written, the records
 
390
                     are adjusted to have pos pointing into data by the sum of
 
391
                     the preceding records sizes.
 
392
        """
 
393
        # write all the data
 
394
        pos = self._data.add_raw_record(data)
 
395
        offset = 0
 
396
        index_entries = []
 
397
        for (version_id, options, parents, size) in records:
 
398
            index_entries.append((version_id, options, pos+offset,
 
399
                                  size, parents))
 
400
            if self._data._do_cache:
 
401
                self._data._cache[version_id] = data[offset:offset+size]
 
402
            offset += size
 
403
        self._index.add_versions(index_entries)
 
404
 
 
405
    def enable_cache(self):
 
406
        """Start caching data for this knit"""
 
407
        self._data.enable_cache()
 
408
 
 
409
    def clear_cache(self):
 
410
        """Clear the data cache only."""
 
411
        self._data.clear_cache()
 
412
 
 
413
    def copy_to(self, name, transport):
 
414
        """See VersionedFile.copy_to()."""
 
415
        # copy the current index to a temp index to avoid racing with local
 
416
        # writes
 
417
        transport.put_file_non_atomic(name + INDEX_SUFFIX + '.tmp',
 
418
                self.transport.get(self._index._filename))
 
419
        # copy the data file
 
420
        f = self._data._open_file()
 
421
        try:
 
422
            transport.put_file(name + DATA_SUFFIX, f)
 
423
        finally:
 
424
            f.close()
 
425
        # move the copied index into place
 
426
        transport.move(name + INDEX_SUFFIX + '.tmp', name + INDEX_SUFFIX)
 
427
 
 
428
    def create_empty(self, name, transport, mode=None):
 
429
        return KnitVersionedFile(name, transport, factory=self.factory,
 
430
                                 delta=self.delta, create=True)
 
431
    
 
432
    def _fix_parents(self, version, new_parents):
 
433
        """Fix the parents list for version.
 
434
        
 
435
        This is done by appending a new version to the index
 
436
        with identical data except for the parents list.
 
437
        the parents list must be a superset of the current
 
438
        list.
 
439
        """
 
440
        current_values = self._index._cache[version]
 
441
        assert set(current_values[4]).difference(set(new_parents)) == set()
 
442
        self._index.add_version(version,
 
443
                                current_values[1], 
 
444
                                current_values[2],
 
445
                                current_values[3],
 
446
                                new_parents)
 
447
 
 
448
    def get_delta(self, version_id):
 
449
        """Get a delta for constructing version from some other version."""
 
450
        if not self.has_version(version_id):
 
451
            raise RevisionNotPresent(version_id, self.filename)
 
452
        
 
453
        parents = self.get_parents(version_id)
 
454
        if len(parents):
 
455
            parent = parents[0]
 
456
        else:
 
457
            parent = None
 
458
        data_pos, data_size = self._index.get_position(version_id)
 
459
        data, sha1 = self._data.read_records(((version_id, data_pos, data_size),))[version_id]
 
460
        version_idx = self._index.lookup(version_id)
 
461
        noeol = 'no-eol' in self._index.get_options(version_id)
 
462
        if 'fulltext' == self._index.get_method(version_id):
 
463
            new_content = self.factory.parse_fulltext(data, version_idx)
 
464
            if parent is not None:
 
465
                reference_content = self._get_content(parent)
 
466
                old_texts = reference_content.text()
 
467
            else:
 
468
                old_texts = []
 
469
            new_texts = new_content.text()
 
470
            delta_seq = KnitSequenceMatcher(None, old_texts, new_texts)
 
471
            return parent, sha1, noeol, self._make_line_delta(delta_seq, new_content)
 
472
        else:
 
473
            delta = self.factory.parse_line_delta(data, version_idx)
 
474
            return parent, sha1, noeol, delta
 
475
        
 
476
    def get_graph_with_ghosts(self):
 
477
        """See VersionedFile.get_graph_with_ghosts()."""
 
478
        graph_items = self._index.get_graph()
 
479
        return dict(graph_items)
 
480
 
 
481
    def get_sha1(self, version_id):
 
482
        """See VersionedFile.get_sha1()."""
 
483
        record_map = self._get_record_map([version_id])
 
484
        method, content, digest, next = record_map[version_id]
 
485
        return digest 
 
486
 
 
487
    @staticmethod
 
488
    def get_suffixes():
 
489
        """See VersionedFile.get_suffixes()."""
 
490
        return [DATA_SUFFIX, INDEX_SUFFIX]
 
491
 
 
492
    def has_ghost(self, version_id):
 
493
        """True if there is a ghost reference in the file to version_id."""
 
494
        # maybe we have it
 
495
        if self.has_version(version_id):
 
496
            return False
 
497
        # optimisable if needed by memoising the _ghosts set.
 
498
        items = self._index.get_graph()
 
499
        for node, parents in items:
 
500
            for parent in parents:
 
501
                if parent not in self._index._cache:
 
502
                    if parent == version_id:
 
503
                        return True
 
504
        return False
 
505
 
 
506
    def versions(self):
 
507
        """See VersionedFile.versions."""
 
508
        return self._index.get_versions()
 
509
 
 
510
    def has_version(self, version_id):
 
511
        """See VersionedFile.has_version."""
 
512
        return self._index.has_version(version_id)
 
513
 
 
514
    __contains__ = has_version
 
515
 
 
516
    def _merge_annotations(self, content, parents, parent_texts={},
 
517
                           delta=None, annotated=None):
 
518
        """Merge annotations for content.  This is done by comparing
 
519
        the annotations based on changed to the text.
 
520
        """
 
521
        if annotated:
 
522
            delta_seq = None
 
523
            for parent_id in parents:
 
524
                merge_content = self._get_content(parent_id, parent_texts)
 
525
                seq = KnitSequenceMatcher(None, merge_content.text(), content.text())
 
526
                if delta_seq is None:
 
527
                    # setup a delta seq to reuse.
 
528
                    delta_seq = seq
 
529
                for i, j, n in seq.get_matching_blocks():
 
530
                    if n == 0:
 
531
                        continue
 
532
                    # this appears to copy (origin, text) pairs across to the new
 
533
                    # content for any line that matches the last-checked parent.
 
534
                    # FIXME: save the sequence control data for delta compression
 
535
                    # against the most relevant parent rather than rediffing.
 
536
                    content._lines[j:j+n] = merge_content._lines[i:i+n]
 
537
        if delta:
 
538
            if not annotated:
 
539
                reference_content = self._get_content(parents[0], parent_texts)
 
540
                new_texts = content.text()
 
541
                old_texts = reference_content.text()
 
542
                delta_seq = KnitSequenceMatcher(None, old_texts, new_texts)
 
543
            return self._make_line_delta(delta_seq, content)
 
544
 
 
545
    def _make_line_delta(self, delta_seq, new_content):
 
546
        """Generate a line delta from delta_seq and new_content."""
 
547
        diff_hunks = []
 
548
        for op in delta_seq.get_opcodes():
 
549
            if op[0] == 'equal':
 
550
                continue
 
551
            diff_hunks.append((op[1], op[2], op[4]-op[3], new_content._lines[op[3]:op[4]]))
 
552
        return diff_hunks
 
553
 
 
554
    def _get_components_positions(self, version_ids):
 
555
        """Produce a map of position data for the components of versions.
 
556
 
 
557
        This data is intended to be used for retrieving the knit records.
 
558
 
 
559
        A dict of version_id to (method, data_pos, data_size, next) is
 
560
        returned.
 
561
        method is the way referenced data should be applied.
 
562
        data_pos is the position of the data in the knit.
 
563
        data_size is the size of the data in the knit.
 
564
        next is the build-parent of the version, or None for fulltexts.
 
565
        """
 
566
        component_data = {}
 
567
        for version_id in version_ids:
 
568
            cursor = version_id
 
569
 
 
570
            while cursor is not None and cursor not in component_data:
 
571
                method = self._index.get_method(cursor)
 
572
                if method == 'fulltext':
 
573
                    next = None
 
574
                else:
 
575
                    next = self.get_parents(cursor)[0]
 
576
                data_pos, data_size = self._index.get_position(cursor)
 
577
                component_data[cursor] = (method, data_pos, data_size, next)
 
578
                cursor = next
 
579
        return component_data
 
580
       
 
581
    def _get_content(self, version_id, parent_texts={}):
 
582
        """Returns a content object that makes up the specified
 
583
        version."""
 
584
        if not self.has_version(version_id):
 
585
            raise RevisionNotPresent(version_id, self.filename)
 
586
 
 
587
        cached_version = parent_texts.get(version_id, None)
 
588
        if cached_version is not None:
 
589
            return cached_version
 
590
 
 
591
        text_map, contents_map = self._get_content_maps([version_id])
 
592
        return contents_map[version_id]
 
593
 
 
594
    def _check_versions_present(self, version_ids):
 
595
        """Check that all specified versions are present."""
 
596
        version_ids = set(version_ids)
 
597
        for r in list(version_ids):
 
598
            if self._index.has_version(r):
 
599
                version_ids.remove(r)
 
600
        if version_ids:
 
601
            raise RevisionNotPresent(list(version_ids)[0], self.filename)
 
602
 
 
603
    def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts):
 
604
        """See VersionedFile.add_lines_with_ghosts()."""
 
605
        self._check_add(version_id, lines)
 
606
        return self._add(version_id, lines[:], parents, self.delta, parent_texts)
 
607
 
 
608
    def _add_lines(self, version_id, parents, lines, parent_texts):
 
609
        """See VersionedFile.add_lines."""
 
610
        self._check_add(version_id, lines)
 
611
        self._check_versions_present(parents)
 
612
        return self._add(version_id, lines[:], parents, self.delta, parent_texts)
 
613
 
 
614
    def _check_add(self, version_id, lines):
 
615
        """check that version_id and lines are safe to add."""
 
616
        assert self.writable, "knit is not opened for write"
 
617
        ### FIXME escape. RBC 20060228
 
618
        if contains_whitespace(version_id):
 
619
            raise InvalidRevisionId(version_id, self.filename)
 
620
        if self.has_version(version_id):
 
621
            raise RevisionAlreadyPresent(version_id, self.filename)
 
622
        self._check_lines_not_unicode(lines)
 
623
        self._check_lines_are_lines(lines)
 
624
 
 
625
    def _add(self, version_id, lines, parents, delta, parent_texts):
 
626
        """Add a set of lines on top of version specified by parents.
 
627
 
 
628
        If delta is true, compress the text as a line-delta against
 
629
        the first parent.
 
630
 
 
631
        Any versions not present will be converted into ghosts.
 
632
        """
 
633
        #  461    0   6546.0390     43.9100   bzrlib.knit:489(_add)
 
634
        # +400    0    889.4890    418.9790   +bzrlib.knit:192(lower_fulltext)
 
635
        # +461    0   1364.8070    108.8030   +bzrlib.knit:996(add_record)
 
636
        # +461    0    193.3940     41.5720   +bzrlib.knit:898(add_version)
 
637
        # +461    0    134.0590     18.3810   +bzrlib.osutils:361(sha_strings)
 
638
        # +461    0     36.3420     15.4540   +bzrlib.knit:146(make)
 
639
        # +1383   0      8.0370      8.0370   +<len>
 
640
        # +61     0     13.5770      7.9190   +bzrlib.knit:199(lower_line_delta)
 
641
        # +61     0    963.3470      7.8740   +bzrlib.knit:427(_get_content)
 
642
        # +61     0    973.9950      5.2950   +bzrlib.knit:136(line_delta)
 
643
        # +61     0   1918.1800      5.2640   +bzrlib.knit:359(_merge_annotations)
 
644
 
 
645
        present_parents = []
 
646
        ghosts = []
 
647
        if parent_texts is None:
 
648
            parent_texts = {}
 
649
        for parent in parents:
 
650
            if not self.has_version(parent):
 
651
                ghosts.append(parent)
 
652
            else:
 
653
                present_parents.append(parent)
 
654
 
 
655
        if delta and not len(present_parents):
 
656
            delta = False
 
657
 
 
658
        digest = sha_strings(lines)
 
659
        options = []
 
660
        if lines:
 
661
            if lines[-1][-1] != '\n':
 
662
                options.append('no-eol')
 
663
                lines[-1] = lines[-1] + '\n'
 
664
 
 
665
        if len(present_parents) and delta:
 
666
            # To speed the extract of texts the delta chain is limited
 
667
            # to a fixed number of deltas.  This should minimize both
 
668
            # I/O and the time spend applying deltas.
 
669
            count = 0
 
670
            delta_parents = present_parents
 
671
            while count < 25:
 
672
                parent = delta_parents[0]
 
673
                method = self._index.get_method(parent)
 
674
                if method == 'fulltext':
 
675
                    break
 
676
                delta_parents = self._index.get_parents(parent)
 
677
                count = count + 1
 
678
            if method == 'line-delta':
 
679
                delta = False
 
680
 
 
681
        lines = self.factory.make(lines, version_id)
 
682
        if delta or (self.factory.annotated and len(present_parents) > 0):
 
683
            # Merge annotations from parent texts if so is needed.
 
684
            delta_hunks = self._merge_annotations(lines, present_parents, parent_texts,
 
685
                                                  delta, self.factory.annotated)
 
686
 
 
687
        if delta:
 
688
            options.append('line-delta')
 
689
            store_lines = self.factory.lower_line_delta(delta_hunks)
 
690
        else:
 
691
            options.append('fulltext')
 
692
            store_lines = self.factory.lower_fulltext(lines)
 
693
 
 
694
        where, size = self._data.add_record(version_id, digest, store_lines)
 
695
        self._index.add_version(version_id, options, where, size, parents)
 
696
        return lines
 
697
 
 
698
    def check(self, progress_bar=None):
 
699
        """See VersionedFile.check()."""
 
700
 
 
701
    def _clone_text(self, new_version_id, old_version_id, parents):
 
702
        """See VersionedFile.clone_text()."""
 
703
        # FIXME RBC 20060228 make fast by only inserting an index with null 
 
704
        # delta.
 
705
        self.add_lines(new_version_id, parents, self.get_lines(old_version_id))
 
706
 
 
707
    def get_lines(self, version_id):
 
708
        """See VersionedFile.get_lines()."""
 
709
        return self.get_line_list([version_id])[0]
 
710
 
 
711
    def _get_record_map(self, version_ids):
 
712
        """Produce a dictionary of knit records.
 
713
        
 
714
        The keys are version_ids, the values are tuples of (method, content,
 
715
        digest, next).
 
716
        method is the way the content should be applied.  
 
717
        content is a KnitContent object.
 
718
        digest is the SHA1 digest of this version id after all steps are done
 
719
        next is the build-parent of the version, i.e. the leftmost ancestor.
 
720
        If the method is fulltext, next will be None.
 
721
        """
 
722
        position_map = self._get_components_positions(version_ids)
 
723
        # c = component_id, m = method, p = position, s = size, n = next
 
724
        records = [(c, p, s) for c, (m, p, s, n) in position_map.iteritems()]
 
725
        record_map = {}
 
726
        for component_id, content, digest in \
 
727
                self._data.read_records_iter(records):
 
728
            method, position, size, next = position_map[component_id]
 
729
            record_map[component_id] = method, content, digest, next
 
730
                          
 
731
        return record_map
 
732
 
 
733
    def get_text(self, version_id):
 
734
        """See VersionedFile.get_text"""
 
735
        return self.get_texts([version_id])[0]
 
736
 
 
737
    def get_texts(self, version_ids):
 
738
        return [''.join(l) for l in self.get_line_list(version_ids)]
 
739
 
 
740
    def get_line_list(self, version_ids):
 
741
        """Return the texts of listed versions as a list of strings."""
 
742
        text_map, content_map = self._get_content_maps(version_ids)
 
743
        return [text_map[v] for v in version_ids]
 
744
 
 
745
    def _get_content_maps(self, version_ids):
 
746
        """Produce maps of text and KnitContents
 
747
        
 
748
        :return: (text_map, content_map) where text_map contains the texts for
 
749
        the requested versions and content_map contains the KnitContents.
 
750
        Both dicts take version_ids as their keys.
 
751
        """
 
752
        for version_id in version_ids:
 
753
            if not self.has_version(version_id):
 
754
                raise RevisionNotPresent(version_id, self.filename)
 
755
        record_map = self._get_record_map(version_ids)
 
756
 
 
757
        text_map = {}
 
758
        content_map = {}
 
759
        final_content = {}
 
760
        for version_id in version_ids:
 
761
            components = []
 
762
            cursor = version_id
 
763
            while cursor is not None:
 
764
                method, data, digest, next = record_map[cursor]
 
765
                components.append((cursor, method, data, digest))
 
766
                if cursor in content_map:
 
767
                    break
 
768
                cursor = next
 
769
 
 
770
            content = None
 
771
            for component_id, method, data, digest in reversed(components):
 
772
                if component_id in content_map:
 
773
                    content = content_map[component_id]
 
774
                else:
 
775
                    version_idx = self._index.lookup(component_id)
 
776
                    if method == 'fulltext':
 
777
                        assert content is None
 
778
                        content = self.factory.parse_fulltext(data, version_idx)
 
779
                    elif method == 'line-delta':
 
780
                        delta = self.factory.parse_line_delta(data[:], 
 
781
                                                              version_idx)
 
782
                        content = content.copy()
 
783
                        content._lines = self._apply_delta(content._lines, 
 
784
                                                           delta)
 
785
                    content_map[component_id] = content
 
786
 
 
787
            if 'no-eol' in self._index.get_options(version_id):
 
788
                content = content.copy()
 
789
                line = content._lines[-1][1].rstrip('\n')
 
790
                content._lines[-1] = (content._lines[-1][0], line)
 
791
            final_content[version_id] = content
 
792
 
 
793
            # digest here is the digest from the last applied component.
 
794
            text = content.text()
 
795
            if sha_strings(text) != digest:
 
796
                raise KnitCorrupt(self.filename, 
 
797
                                  'sha-1 does not match %s' % version_id)
 
798
 
 
799
            text_map[version_id] = text 
 
800
        return text_map, final_content 
 
801
 
 
802
    def iter_lines_added_or_present_in_versions(self, version_ids=None, 
 
803
                                                pb=None):
 
804
        """See VersionedFile.iter_lines_added_or_present_in_versions()."""
 
805
        if version_ids is None:
 
806
            version_ids = self.versions()
 
807
        if pb is None:
 
808
            pb = progress.DummyProgress()
 
809
        # we don't care about inclusions, the caller cares.
 
810
        # but we need to setup a list of records to visit.
 
811
        # we need version_id, position, length
 
812
        version_id_records = []
 
813
        requested_versions = list(version_ids)
 
814
        # filter for available versions
 
815
        for version_id in requested_versions:
 
816
            if not self.has_version(version_id):
 
817
                raise RevisionNotPresent(version_id, self.filename)
 
818
        # get a in-component-order queue:
 
819
        version_ids = []
 
820
        for version_id in self.versions():
 
821
            if version_id in requested_versions:
 
822
                version_ids.append(version_id)
 
823
                data_pos, length = self._index.get_position(version_id)
 
824
                version_id_records.append((version_id, data_pos, length))
 
825
 
 
826
        count = 0
 
827
        total = len(version_id_records)
 
828
        pb.update('Walking content.', count, total)
 
829
        for version_id, data, sha_value in \
 
830
            self._data.read_records_iter(version_id_records):
 
831
            pb.update('Walking content.', count, total)
 
832
            method = self._index.get_method(version_id)
 
833
            version_idx = self._index.lookup(version_id)
 
834
            assert method in ('fulltext', 'line-delta')
 
835
            if method == 'fulltext':
 
836
                content = self.factory.parse_fulltext(data, version_idx)
 
837
                for line in content.text():
 
838
                    yield line
 
839
            else:
 
840
                delta = self.factory.parse_line_delta(data, version_idx)
 
841
                for start, end, count, lines in delta:
 
842
                    for origin, line in lines:
 
843
                        yield line
 
844
            count +=1
 
845
        pb.update('Walking content.', total, total)
 
846
        
 
847
    def num_versions(self):
 
848
        """See VersionedFile.num_versions()."""
 
849
        return self._index.num_versions()
 
850
 
 
851
    __len__ = num_versions
 
852
 
 
853
    def annotate_iter(self, version_id):
 
854
        """See VersionedFile.annotate_iter."""
 
855
        content = self._get_content(version_id)
 
856
        for origin, text in content.annotate_iter():
 
857
            yield origin, text
 
858
 
 
859
    def get_parents(self, version_id):
 
860
        """See VersionedFile.get_parents."""
 
861
        # perf notes:
 
862
        # optimism counts!
 
863
        # 52554 calls in 1264 872 internal down from 3674
 
864
        try:
 
865
            return self._index.get_parents(version_id)
 
866
        except KeyError:
 
867
            raise RevisionNotPresent(version_id, self.filename)
 
868
 
 
869
    def get_parents_with_ghosts(self, version_id):
 
870
        """See VersionedFile.get_parents."""
 
871
        try:
 
872
            return self._index.get_parents_with_ghosts(version_id)
 
873
        except KeyError:
 
874
            raise RevisionNotPresent(version_id, self.filename)
 
875
 
 
876
    def get_ancestry(self, versions):
 
877
        """See VersionedFile.get_ancestry."""
 
878
        if isinstance(versions, basestring):
 
879
            versions = [versions]
 
880
        if not versions:
 
881
            return []
 
882
        self._check_versions_present(versions)
 
883
        return self._index.get_ancestry(versions)
 
884
 
 
885
    def get_ancestry_with_ghosts(self, versions):
 
886
        """See VersionedFile.get_ancestry_with_ghosts."""
 
887
        if isinstance(versions, basestring):
 
888
            versions = [versions]
 
889
        if not versions:
 
890
            return []
 
891
        self._check_versions_present(versions)
 
892
        return self._index.get_ancestry_with_ghosts(versions)
 
893
 
 
894
    #@deprecated_method(zero_eight)
 
895
    def walk(self, version_ids):
 
896
        """See VersionedFile.walk."""
 
897
        # We take the short path here, and extract all relevant texts
 
898
        # and put them in a weave and let that do all the work.  Far
 
899
        # from optimal, but is much simpler.
 
900
        # FIXME RB 20060228 this really is inefficient!
 
901
        from bzrlib.weave import Weave
 
902
 
 
903
        w = Weave(self.filename)
 
904
        ancestry = self.get_ancestry(version_ids)
 
905
        sorted_graph = topo_sort(self._index.get_graph())
 
906
        version_list = [vid for vid in sorted_graph if vid in ancestry]
 
907
        
 
908
        for version_id in version_list:
 
909
            lines = self.get_lines(version_id)
 
910
            w.add_lines(version_id, self.get_parents(version_id), lines)
 
911
 
 
912
        for lineno, insert_id, dset, line in w.walk(version_ids):
 
913
            yield lineno, insert_id, dset, line
 
914
 
 
915
    def plan_merge(self, ver_a, ver_b):
 
916
        """See VersionedFile.plan_merge."""
 
917
        ancestors_b = set(self.get_ancestry(ver_b))
 
918
        def status_a(revision, text):
 
919
            if revision in ancestors_b:
 
920
                return 'killed-b', text
 
921
            else:
 
922
                return 'new-a', text
 
923
        
 
924
        ancestors_a = set(self.get_ancestry(ver_a))
 
925
        def status_b(revision, text):
 
926
            if revision in ancestors_a:
 
927
                return 'killed-a', text
 
928
            else:
 
929
                return 'new-b', text
 
930
 
 
931
        annotated_a = self.annotate(ver_a)
 
932
        annotated_b = self.annotate(ver_b)
 
933
        plain_a = [t for (a, t) in annotated_a]
 
934
        plain_b = [t for (a, t) in annotated_b]
 
935
        blocks = KnitSequenceMatcher(None, plain_a, plain_b).get_matching_blocks()
 
936
        a_cur = 0
 
937
        b_cur = 0
 
938
        for ai, bi, l in blocks:
 
939
            # process all mismatched sections
 
940
            # (last mismatched section is handled because blocks always
 
941
            # includes a 0-length last block)
 
942
            for revision, text in annotated_a[a_cur:ai]:
 
943
                yield status_a(revision, text)
 
944
            for revision, text in annotated_b[b_cur:bi]:
 
945
                yield status_b(revision, text)
 
946
 
 
947
            # and now the matched section
 
948
            a_cur = ai + l
 
949
            b_cur = bi + l
 
950
            for text_a, text_b in zip(plain_a[ai:a_cur], plain_b[bi:b_cur]):
 
951
                assert text_a == text_b
 
952
                yield "unchanged", text_a
 
953
 
 
954
 
 
955
class _KnitComponentFile(object):
 
956
    """One of the files used to implement a knit database"""
 
957
 
 
958
    def __init__(self, transport, filename, mode, file_mode=None,
 
959
                 create_parent_dir=False, dir_mode=None):
 
960
        self._transport = transport
 
961
        self._filename = filename
 
962
        self._mode = mode
 
963
        self._file_mode = file_mode
 
964
        self._dir_mode = dir_mode
 
965
        self._create_parent_dir = create_parent_dir
 
966
        self._need_to_create = False
 
967
 
 
968
    def check_header(self, fp):
 
969
        line = fp.readline()
 
970
        if line != self.HEADER:
 
971
            raise KnitHeaderError(badline=line)
 
972
 
 
973
    def commit(self):
 
974
        """Commit is a nop."""
 
975
 
 
976
    def __repr__(self):
 
977
        return '%s(%s)' % (self.__class__.__name__, self._filename)
 
978
 
 
979
 
 
980
class _KnitIndex(_KnitComponentFile):
 
981
    """Manages knit index file.
 
982
 
 
983
    The index is already kept in memory and read on startup, to enable
 
984
    fast lookups of revision information.  The cursor of the index
 
985
    file is always pointing to the end, making it easy to append
 
986
    entries.
 
987
 
 
988
    _cache is a cache for fast mapping from version id to a Index
 
989
    object.
 
990
 
 
991
    _history is a cache for fast mapping from indexes to version ids.
 
992
 
 
993
    The index data format is dictionary compressed when it comes to
 
994
    parent references; a index entry may only have parents that with a
 
995
    lover index number.  As a result, the index is topological sorted.
 
996
 
 
997
    Duplicate entries may be written to the index for a single version id
 
998
    if this is done then the latter one completely replaces the former:
 
999
    this allows updates to correct version and parent information. 
 
1000
    Note that the two entries may share the delta, and that successive
 
1001
    annotations and references MUST point to the first entry.
 
1002
 
 
1003
    The index file on disc contains a header, followed by one line per knit
 
1004
    record. The same revision can be present in an index file more than once.
 
1005
    The first occurrence gets assigned a sequence number starting from 0. 
 
1006
    
 
1007
    The format of a single line is
 
1008
    REVISION_ID FLAGS BYTE_OFFSET LENGTH( PARENT_ID|PARENT_SEQUENCE_ID)* :\n
 
1009
    REVISION_ID is a utf8-encoded revision id
 
1010
    FLAGS is a comma separated list of flags about the record. Values include 
 
1011
        no-eol, line-delta, fulltext.
 
1012
    BYTE_OFFSET is the ascii representation of the byte offset in the data file
 
1013
        that the the compressed data starts at.
 
1014
    LENGTH is the ascii representation of the length of the data file.
 
1015
    PARENT_ID a utf-8 revision id prefixed by a '.' that is a parent of
 
1016
        REVISION_ID.
 
1017
    PARENT_SEQUENCE_ID the ascii representation of the sequence number of a
 
1018
        revision id already in the knit that is a parent of REVISION_ID.
 
1019
    The ' :' marker is the end of record marker.
 
1020
    
 
1021
    partial writes:
 
1022
    when a write is interrupted to the index file, it will result in a line that
 
1023
    does not end in ' :'. If the ' :' is not present at the end of a line, or at
 
1024
    the end of the file, then the record that is missing it will be ignored by
 
1025
    the parser.
 
1026
 
 
1027
    When writing new records to the index file, the data is preceded by '\n'
 
1028
    to ensure that records always start on new lines even if the last write was
 
1029
    interrupted. As a result its normal for the last line in the index to be
 
1030
    missing a trailing newline. One can be added with no harmful effects.
 
1031
    """
 
1032
 
 
1033
    HEADER = "# bzr knit index 8\n"
 
1034
 
 
1035
    # speed of knit parsing went from 280 ms to 280 ms with slots addition.
 
1036
    # __slots__ = ['_cache', '_history', '_transport', '_filename']
 
1037
 
 
1038
    def _cache_version(self, version_id, options, pos, size, parents):
 
1039
        """Cache a version record in the history array and index cache.
 
1040
        
 
1041
        This is inlined into __init__ for performance. KEEP IN SYNC.
 
1042
        (It saves 60ms, 25% of the __init__ overhead on local 4000 record
 
1043
         indexes).
 
1044
        """
 
1045
        # only want the _history index to reference the 1st index entry
 
1046
        # for version_id
 
1047
        if version_id not in self._cache:
 
1048
            index = len(self._history)
 
1049
            self._history.append(version_id)
 
1050
        else:
 
1051
            index = self._cache[version_id][5]
 
1052
        self._cache[version_id] = (version_id, 
 
1053
                                   options,
 
1054
                                   pos,
 
1055
                                   size,
 
1056
                                   parents,
 
1057
                                   index)
 
1058
 
 
1059
    def __init__(self, transport, filename, mode, create=False, file_mode=None,
 
1060
                 create_parent_dir=False, delay_create=False, dir_mode=None):
 
1061
        _KnitComponentFile.__init__(self, transport, filename, mode,
 
1062
                                    file_mode=file_mode,
 
1063
                                    create_parent_dir=create_parent_dir,
 
1064
                                    dir_mode=dir_mode)
 
1065
        self._cache = {}
 
1066
        # position in _history is the 'official' index for a revision
 
1067
        # but the values may have come from a newer entry.
 
1068
        # so - wc -l of a knit index is != the number of unique names
 
1069
        # in the knit.
 
1070
        self._history = []
 
1071
        pb = bzrlib.ui.ui_factory.nested_progress_bar()
 
1072
        try:
 
1073
            count = 0
 
1074
            total = 1
 
1075
            try:
 
1076
                pb.update('read knit index', count, total)
 
1077
                fp = self._transport.get(self._filename)
 
1078
                try:
 
1079
                    self.check_header(fp)
 
1080
                    # readlines reads the whole file at once:
 
1081
                    # bad for transports like http, good for local disk
 
1082
                    # we save 60 ms doing this one change (
 
1083
                    # from calling readline each time to calling
 
1084
                    # readlines once.
 
1085
                    # probably what we want for nice behaviour on
 
1086
                    # http is a incremental readlines that yields, or
 
1087
                    # a check for local vs non local indexes,
 
1088
                    for l in fp.readlines():
 
1089
                        rec = l.split()
 
1090
                        if len(rec) < 5 or rec[-1] != ':':
 
1091
                            # corrupt line.
 
1092
                            # FIXME: in the future we should determine if its a
 
1093
                            # short write - and ignore it 
 
1094
                            # or a different failure, and raise. RBC 20060407
 
1095
                            continue
 
1096
                        count += 1
 
1097
                        total += 1
 
1098
                        #pb.update('read knit index', count, total)
 
1099
                        # See self._parse_parents
 
1100
                        parents = []
 
1101
                        for value in rec[4:-1]:
 
1102
                            if '.' == value[0]:
 
1103
                                # uncompressed reference
 
1104
                                parents.append(value[1:])
 
1105
                            else:
 
1106
                                # this is 15/4000ms faster than isinstance,
 
1107
                                # (in lsprof)
 
1108
                                # this function is called thousands of times a 
 
1109
                                # second so small variations add up.
 
1110
                                assert value.__class__ is str
 
1111
                                parents.append(self._history[int(value)])
 
1112
                        # end self._parse_parents
 
1113
                        # self._cache_version(rec[0], 
 
1114
                        #                     rec[1].split(','),
 
1115
                        #                     int(rec[2]),
 
1116
                        #                     int(rec[3]),
 
1117
                        #                     parents)
 
1118
                        # --- self._cache_version
 
1119
                        # only want the _history index to reference the 1st 
 
1120
                        # index entry for version_id
 
1121
                        version_id = rec[0]
 
1122
                        if version_id not in self._cache:
 
1123
                            index = len(self._history)
 
1124
                            self._history.append(version_id)
 
1125
                        else:
 
1126
                            index = self._cache[version_id][5]
 
1127
                        self._cache[version_id] = (version_id,
 
1128
                                                   rec[1].split(','),
 
1129
                                                   int(rec[2]),
 
1130
                                                   int(rec[3]),
 
1131
                                                   parents,
 
1132
                                                   index)
 
1133
                        # --- self._cache_version 
 
1134
                finally:
 
1135
                    fp.close()
 
1136
            except NoSuchFile, e:
 
1137
                if mode != 'w' or not create:
 
1138
                    raise
 
1139
                if delay_create:
 
1140
                    self._need_to_create = True
 
1141
                else:
 
1142
                    self._transport.put_bytes_non_atomic(self._filename,
 
1143
                        self.HEADER, mode=self._file_mode)
 
1144
 
 
1145
        finally:
 
1146
            pb.update('read knit index', total, total)
 
1147
            pb.finished()
 
1148
 
 
1149
    def _parse_parents(self, compressed_parents):
 
1150
        """convert a list of string parent values into version ids.
 
1151
 
 
1152
        ints are looked up in the index.
 
1153
        .FOO values are ghosts and converted in to FOO.
 
1154
 
 
1155
        NOTE: the function is retained here for clarity, and for possible
 
1156
              use in partial index reads. However bulk processing now has
 
1157
              it inlined in __init__ for inner-loop optimisation.
 
1158
        """
 
1159
        result = []
 
1160
        for value in compressed_parents:
 
1161
            if value[-1] == '.':
 
1162
                # uncompressed reference
 
1163
                result.append(value[1:])
 
1164
            else:
 
1165
                # this is 15/4000ms faster than isinstance,
 
1166
                # this function is called thousands of times a 
 
1167
                # second so small variations add up.
 
1168
                assert value.__class__ is str
 
1169
                result.append(self._history[int(value)])
 
1170
        return result
 
1171
 
 
1172
    def get_graph(self):
 
1173
        graph = []
 
1174
        for version_id, index in self._cache.iteritems():
 
1175
            graph.append((version_id, index[4]))
 
1176
        return graph
 
1177
 
 
1178
    def get_ancestry(self, versions):
 
1179
        """See VersionedFile.get_ancestry."""
 
1180
        # get a graph of all the mentioned versions:
 
1181
        graph = {}
 
1182
        pending = set(versions)
 
1183
        while len(pending):
 
1184
            version = pending.pop()
 
1185
            parents = self._cache[version][4]
 
1186
            # got the parents ok
 
1187
            # trim ghosts
 
1188
            parents = [parent for parent in parents if parent in self._cache]
 
1189
            for parent in parents:
 
1190
                # if not completed and not a ghost
 
1191
                if parent not in graph:
 
1192
                    pending.add(parent)
 
1193
            graph[version] = parents
 
1194
        return topo_sort(graph.items())
 
1195
 
 
1196
    def get_ancestry_with_ghosts(self, versions):
 
1197
        """See VersionedFile.get_ancestry_with_ghosts."""
 
1198
        # get a graph of all the mentioned versions:
 
1199
        graph = {}
 
1200
        pending = set(versions)
 
1201
        while len(pending):
 
1202
            version = pending.pop()
 
1203
            try:
 
1204
                parents = self._cache[version][4]
 
1205
            except KeyError:
 
1206
                # ghost, fake it
 
1207
                graph[version] = []
 
1208
                pass
 
1209
            else:
 
1210
                # got the parents ok
 
1211
                for parent in parents:
 
1212
                    if parent not in graph:
 
1213
                        pending.add(parent)
 
1214
                graph[version] = parents
 
1215
        return topo_sort(graph.items())
 
1216
 
 
1217
    def num_versions(self):
 
1218
        return len(self._history)
 
1219
 
 
1220
    __len__ = num_versions
 
1221
 
 
1222
    def get_versions(self):
 
1223
        return self._history
 
1224
 
 
1225
    def idx_to_name(self, idx):
 
1226
        return self._history[idx]
 
1227
 
 
1228
    def lookup(self, version_id):
 
1229
        assert version_id in self._cache
 
1230
        return self._cache[version_id][5]
 
1231
 
 
1232
    def _version_list_to_index(self, versions):
 
1233
        encode_utf8 = cache_utf8.encode
 
1234
        result_list = []
 
1235
        for version in versions:
 
1236
            if version in self._cache:
 
1237
                # -- inlined lookup() --
 
1238
                result_list.append(str(self._cache[version][5]))
 
1239
                # -- end lookup () --
 
1240
            else:
 
1241
                result_list.append('.' + encode_utf8(version))
 
1242
        return ' '.join(result_list)
 
1243
 
 
1244
    def add_version(self, version_id, options, pos, size, parents):
 
1245
        """Add a version record to the index."""
 
1246
        self.add_versions(((version_id, options, pos, size, parents),))
 
1247
 
 
1248
    def add_versions(self, versions):
 
1249
        """Add multiple versions to the index.
 
1250
        
 
1251
        :param versions: a list of tuples:
 
1252
                         (version_id, options, pos, size, parents).
 
1253
        """
 
1254
        lines = []
 
1255
        encode_utf8 = cache_utf8.encode
 
1256
        for version_id, options, pos, size, parents in versions:
 
1257
            line = "\n%s %s %s %s %s :" % (encode_utf8(version_id),
 
1258
                                           ','.join(options),
 
1259
                                           pos,
 
1260
                                           size,
 
1261
                                           self._version_list_to_index(parents))
 
1262
            assert isinstance(line, str), \
 
1263
                'content must be utf-8 encoded: %r' % (line,)
 
1264
            lines.append(line)
 
1265
        if not self._need_to_create:
 
1266
            self._transport.append_bytes(self._filename, ''.join(lines))
 
1267
        else:
 
1268
            sio = StringIO()
 
1269
            sio.write(self.HEADER)
 
1270
            sio.writelines(lines)
 
1271
            sio.seek(0)
 
1272
            self._transport.put_file_non_atomic(self._filename, sio,
 
1273
                                create_parent_dir=self._create_parent_dir,
 
1274
                                mode=self._file_mode,
 
1275
                                dir_mode=self._dir_mode)
 
1276
            self._need_to_create = False
 
1277
 
 
1278
        # cache after writing, so that a failed write leads to missing cache
 
1279
        # entries not extra ones. XXX TODO: RBC 20060502 in the event of a 
 
1280
        # failure, reload the index or flush it or some such, to prevent
 
1281
        # writing records that did complete twice.
 
1282
        for version_id, options, pos, size, parents in versions:
 
1283
            self._cache_version(version_id, options, pos, size, parents)
 
1284
        
 
1285
    def has_version(self, version_id):
 
1286
        """True if the version is in the index."""
 
1287
        return (version_id in self._cache)
 
1288
 
 
1289
    def get_position(self, version_id):
 
1290
        """Return data position and size of specified version."""
 
1291
        return (self._cache[version_id][2], \
 
1292
                self._cache[version_id][3])
 
1293
 
 
1294
    def get_method(self, version_id):
 
1295
        """Return compression method of specified version."""
 
1296
        options = self._cache[version_id][1]
 
1297
        if 'fulltext' in options:
 
1298
            return 'fulltext'
 
1299
        else:
 
1300
            assert 'line-delta' in options
 
1301
            return 'line-delta'
 
1302
 
 
1303
    def get_options(self, version_id):
 
1304
        return self._cache[version_id][1]
 
1305
 
 
1306
    def get_parents(self, version_id):
 
1307
        """Return parents of specified version ignoring ghosts."""
 
1308
        return [parent for parent in self._cache[version_id][4] 
 
1309
                if parent in self._cache]
 
1310
 
 
1311
    def get_parents_with_ghosts(self, version_id):
 
1312
        """Return parents of specified version with ghosts."""
 
1313
        return self._cache[version_id][4] 
 
1314
 
 
1315
    def check_versions_present(self, version_ids):
 
1316
        """Check that all specified versions are present."""
 
1317
        version_ids = set(version_ids)
 
1318
        for version_id in list(version_ids):
 
1319
            if version_id in self._cache:
 
1320
                version_ids.remove(version_id)
 
1321
        if version_ids:
 
1322
            raise RevisionNotPresent(list(version_ids)[0], self.filename)
 
1323
 
 
1324
 
 
1325
class _KnitData(_KnitComponentFile):
 
1326
    """Contents of the knit data file"""
 
1327
 
 
1328
    def __init__(self, transport, filename, mode, create=False, file_mode=None,
 
1329
                 create_parent_dir=False, delay_create=False,
 
1330
                 dir_mode=None):
 
1331
        _KnitComponentFile.__init__(self, transport, filename, mode,
 
1332
                                    file_mode=file_mode,
 
1333
                                    create_parent_dir=create_parent_dir,
 
1334
                                    dir_mode=dir_mode)
 
1335
        self._checked = False
 
1336
        # TODO: jam 20060713 conceptually, this could spill to disk
 
1337
        #       if the cached size gets larger than a certain amount
 
1338
        #       but it complicates the model a bit, so for now just use
 
1339
        #       a simple dictionary
 
1340
        self._cache = {}
 
1341
        self._do_cache = False
 
1342
        if create:
 
1343
            if delay_create:
 
1344
                self._need_to_create = create
 
1345
            else:
 
1346
                self._transport.put_bytes_non_atomic(self._filename, '',
 
1347
                                                     mode=self._file_mode)
 
1348
 
 
1349
    def enable_cache(self):
 
1350
        """Enable caching of reads."""
 
1351
        self._do_cache = True
 
1352
 
 
1353
    def clear_cache(self):
 
1354
        """Clear the record cache."""
 
1355
        self._do_cache = False
 
1356
        self._cache = {}
 
1357
 
 
1358
    def _open_file(self):
 
1359
        try:
 
1360
            return self._transport.get(self._filename)
 
1361
        except NoSuchFile:
 
1362
            pass
 
1363
        return None
 
1364
 
 
1365
    def _record_to_data(self, version_id, digest, lines):
 
1366
        """Convert version_id, digest, lines into a raw data block.
 
1367
        
 
1368
        :return: (len, a StringIO instance with the raw data ready to read.)
 
1369
        """
 
1370
        sio = StringIO()
 
1371
        data_file = GzipFile(None, mode='wb', fileobj=sio)
 
1372
 
 
1373
        version_id_utf8 = cache_utf8.encode(version_id)
 
1374
        data_file.writelines(chain(
 
1375
            ["version %s %d %s\n" % (version_id_utf8,
 
1376
                                     len(lines),
 
1377
                                     digest)],
 
1378
            lines,
 
1379
            ["end %s\n" % version_id_utf8]))
 
1380
        data_file.close()
 
1381
        length= sio.tell()
 
1382
 
 
1383
        sio.seek(0)
 
1384
        return length, sio
 
1385
 
 
1386
    def add_raw_record(self, raw_data):
 
1387
        """Append a prepared record to the data file.
 
1388
        
 
1389
        :return: the offset in the data file raw_data was written.
 
1390
        """
 
1391
        assert isinstance(raw_data, str), 'data must be plain bytes'
 
1392
        if not self._need_to_create:
 
1393
            return self._transport.append_bytes(self._filename, raw_data)
 
1394
        else:
 
1395
            self._transport.put_bytes_non_atomic(self._filename, raw_data,
 
1396
                                   create_parent_dir=self._create_parent_dir,
 
1397
                                   mode=self._file_mode,
 
1398
                                   dir_mode=self._dir_mode)
 
1399
            self._need_to_create = False
 
1400
            return 0
 
1401
        
 
1402
    def add_record(self, version_id, digest, lines):
 
1403
        """Write new text record to disk.  Returns the position in the
 
1404
        file where it was written."""
 
1405
        size, sio = self._record_to_data(version_id, digest, lines)
 
1406
        # write to disk
 
1407
        if not self._need_to_create:
 
1408
            start_pos = self._transport.append_file(self._filename, sio)
 
1409
        else:
 
1410
            self._transport.put_file_non_atomic(self._filename, sio,
 
1411
                               create_parent_dir=self._create_parent_dir,
 
1412
                               mode=self._file_mode,
 
1413
                               dir_mode=self._dir_mode)
 
1414
            self._need_to_create = False
 
1415
            start_pos = 0
 
1416
        if self._do_cache:
 
1417
            self._cache[version_id] = sio.getvalue()
 
1418
        return start_pos, size
 
1419
 
 
1420
    def _parse_record_header(self, version_id, raw_data):
 
1421
        """Parse a record header for consistency.
 
1422
 
 
1423
        :return: the header and the decompressor stream.
 
1424
                 as (stream, header_record)
 
1425
        """
 
1426
        df = GzipFile(mode='rb', fileobj=StringIO(raw_data))
 
1427
        rec = df.readline().split()
 
1428
        if len(rec) != 4:
 
1429
            raise KnitCorrupt(self._filename, 'unexpected number of elements in record header')
 
1430
        if cache_utf8.decode(rec[1]) != version_id:
 
1431
            raise KnitCorrupt(self._filename, 
 
1432
                              'unexpected version, wanted %r, got %r' % (
 
1433
                                version_id, rec[1]))
 
1434
        return df, rec
 
1435
 
 
1436
    def _parse_record(self, version_id, data):
 
1437
        # profiling notes:
 
1438
        # 4168 calls in 2880 217 internal
 
1439
        # 4168 calls to _parse_record_header in 2121
 
1440
        # 4168 calls to readlines in 330
 
1441
        df, rec = self._parse_record_header(version_id, data)
 
1442
        record_contents = df.readlines()
 
1443
        l = record_contents.pop()
 
1444
        assert len(record_contents) == int(rec[2])
 
1445
        if l != 'end %s\n' % cache_utf8.encode(version_id):
 
1446
            raise KnitCorrupt(self._filename, 'unexpected version end line %r, wanted %r' 
 
1447
                        % (l, version_id))
 
1448
        df.close()
 
1449
        return record_contents, rec[3]
 
1450
 
 
1451
    def read_records_iter_raw(self, records):
 
1452
        """Read text records from data file and yield raw data.
 
1453
 
 
1454
        This unpacks enough of the text record to validate the id is
 
1455
        as expected but thats all.
 
1456
        """
 
1457
        # setup an iterator of the external records:
 
1458
        # uses readv so nice and fast we hope.
 
1459
        if len(records):
 
1460
            # grab the disk data needed.
 
1461
            if self._cache:
 
1462
                # Don't check _cache if it is empty
 
1463
                needed_offsets = [(pos, size) for version_id, pos, size
 
1464
                                              in records
 
1465
                                              if version_id not in self._cache]
 
1466
            else:
 
1467
                needed_offsets = [(pos, size) for version_id, pos, size
 
1468
                                               in records]
 
1469
 
 
1470
            raw_records = self._transport.readv(self._filename, needed_offsets)
 
1471
                
 
1472
 
 
1473
        for version_id, pos, size in records:
 
1474
            if version_id in self._cache:
 
1475
                # This data has already been validated
 
1476
                data = self._cache[version_id]
 
1477
            else:
 
1478
                pos, data = raw_records.next()
 
1479
                if self._do_cache:
 
1480
                    self._cache[version_id] = data
 
1481
 
 
1482
                # validate the header
 
1483
                df, rec = self._parse_record_header(version_id, data)
 
1484
                df.close()
 
1485
            yield version_id, data
 
1486
 
 
1487
    def read_records_iter(self, records):
 
1488
        """Read text records from data file and yield result.
 
1489
 
 
1490
        The result will be returned in whatever is the fastest to read.
 
1491
        Not by the order requested. Also, multiple requests for the same
 
1492
        record will only yield 1 response.
 
1493
        :param records: A list of (version_id, pos, len) entries
 
1494
        :return: Yields (version_id, contents, digest) in the order
 
1495
                 read, not the order requested
 
1496
        """
 
1497
        if not records:
 
1498
            return
 
1499
 
 
1500
        if self._cache:
 
1501
            # Skip records we have alread seen
 
1502
            yielded_records = set()
 
1503
            needed_records = set()
 
1504
            for record in records:
 
1505
                if record[0] in self._cache:
 
1506
                    if record[0] in yielded_records:
 
1507
                        continue
 
1508
                    yielded_records.add(record[0])
 
1509
                    data = self._cache[record[0]]
 
1510
                    content, digest = self._parse_record(record[0], data)
 
1511
                    yield (record[0], content, digest)
 
1512
                else:
 
1513
                    needed_records.add(record)
 
1514
            needed_records = sorted(needed_records, key=operator.itemgetter(1))
 
1515
        else:
 
1516
            needed_records = sorted(set(records), key=operator.itemgetter(1))
 
1517
 
 
1518
        if not needed_records:
 
1519
            return
 
1520
 
 
1521
        # The transport optimizes the fetching as well 
 
1522
        # (ie, reads continuous ranges.)
 
1523
        readv_response = self._transport.readv(self._filename,
 
1524
            [(pos, size) for version_id, pos, size in needed_records])
 
1525
 
 
1526
        for (version_id, pos, size), (pos, data) in \
 
1527
                izip(iter(needed_records), readv_response):
 
1528
            content, digest = self._parse_record(version_id, data)
 
1529
            if self._do_cache:
 
1530
                self._cache[version_id] = data
 
1531
            yield version_id, content, digest
 
1532
 
 
1533
    def read_records(self, records):
 
1534
        """Read records into a dictionary."""
 
1535
        components = {}
 
1536
        for record_id, content, digest in \
 
1537
                self.read_records_iter(records):
 
1538
            components[record_id] = (content, digest)
 
1539
        return components
 
1540
 
 
1541
 
 
1542
class InterKnit(InterVersionedFile):
 
1543
    """Optimised code paths for knit to knit operations."""
 
1544
    
 
1545
    _matching_file_from_factory = KnitVersionedFile
 
1546
    _matching_file_to_factory = KnitVersionedFile
 
1547
    
 
1548
    @staticmethod
 
1549
    def is_compatible(source, target):
 
1550
        """Be compatible with knits.  """
 
1551
        try:
 
1552
            return (isinstance(source, KnitVersionedFile) and
 
1553
                    isinstance(target, KnitVersionedFile))
 
1554
        except AttributeError:
 
1555
            return False
 
1556
 
 
1557
    def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
 
1558
        """See InterVersionedFile.join."""
 
1559
        assert isinstance(self.source, KnitVersionedFile)
 
1560
        assert isinstance(self.target, KnitVersionedFile)
 
1561
 
 
1562
        version_ids = self._get_source_version_ids(version_ids, ignore_missing)
 
1563
 
 
1564
        if not version_ids:
 
1565
            return 0
 
1566
 
 
1567
        pb = bzrlib.ui.ui_factory.nested_progress_bar()
 
1568
        try:
 
1569
            version_ids = list(version_ids)
 
1570
            if None in version_ids:
 
1571
                version_ids.remove(None)
 
1572
    
 
1573
            self.source_ancestry = set(self.source.get_ancestry(version_ids))
 
1574
            this_versions = set(self.target._index.get_versions())
 
1575
            needed_versions = self.source_ancestry - this_versions
 
1576
            cross_check_versions = self.source_ancestry.intersection(this_versions)
 
1577
            mismatched_versions = set()
 
1578
            for version in cross_check_versions:
 
1579
                # scan to include needed parents.
 
1580
                n1 = set(self.target.get_parents_with_ghosts(version))
 
1581
                n2 = set(self.source.get_parents_with_ghosts(version))
 
1582
                if n1 != n2:
 
1583
                    # FIXME TEST this check for cycles being introduced works
 
1584
                    # the logic is we have a cycle if in our graph we are an
 
1585
                    # ancestor of any of the n2 revisions.
 
1586
                    for parent in n2:
 
1587
                        if parent in n1:
 
1588
                            # safe
 
1589
                            continue
 
1590
                        else:
 
1591
                            parent_ancestors = self.source.get_ancestry(parent)
 
1592
                            if version in parent_ancestors:
 
1593
                                raise errors.GraphCycleError([parent, version])
 
1594
                    # ensure this parent will be available later.
 
1595
                    new_parents = n2.difference(n1)
 
1596
                    needed_versions.update(new_parents.difference(this_versions))
 
1597
                    mismatched_versions.add(version)
 
1598
    
 
1599
            if not needed_versions and not mismatched_versions:
 
1600
                return 0
 
1601
            full_list = topo_sort(self.source.get_graph())
 
1602
    
 
1603
            version_list = [i for i in full_list if (not self.target.has_version(i)
 
1604
                            and i in needed_versions)]
 
1605
    
 
1606
            # plan the join:
 
1607
            copy_queue = []
 
1608
            copy_queue_records = []
 
1609
            copy_set = set()
 
1610
            for version_id in version_list:
 
1611
                options = self.source._index.get_options(version_id)
 
1612
                parents = self.source._index.get_parents_with_ghosts(version_id)
 
1613
                # check that its will be a consistent copy:
 
1614
                for parent in parents:
 
1615
                    # if source has the parent, we must :
 
1616
                    # * already have it or
 
1617
                    # * have it scheduled already
 
1618
                    # otherwise we don't care
 
1619
                    assert (self.target.has_version(parent) or
 
1620
                            parent in copy_set or
 
1621
                            not self.source.has_version(parent))
 
1622
                data_pos, data_size = self.source._index.get_position(version_id)
 
1623
                copy_queue_records.append((version_id, data_pos, data_size))
 
1624
                copy_queue.append((version_id, options, parents))
 
1625
                copy_set.add(version_id)
 
1626
 
 
1627
            # data suck the join:
 
1628
            count = 0
 
1629
            total = len(version_list)
 
1630
            raw_datum = []
 
1631
            raw_records = []
 
1632
            for (version_id, raw_data), \
 
1633
                (version_id2, options, parents) in \
 
1634
                izip(self.source._data.read_records_iter_raw(copy_queue_records),
 
1635
                     copy_queue):
 
1636
                assert version_id == version_id2, 'logic error, inconsistent results'
 
1637
                count = count + 1
 
1638
                pb.update("Joining knit", count, total)
 
1639
                raw_records.append((version_id, options, parents, len(raw_data)))
 
1640
                raw_datum.append(raw_data)
 
1641
            self.target._add_raw_records(raw_records, ''.join(raw_datum))
 
1642
 
 
1643
            for version in mismatched_versions:
 
1644
                # FIXME RBC 20060309 is this needed?
 
1645
                n1 = set(self.target.get_parents_with_ghosts(version))
 
1646
                n2 = set(self.source.get_parents_with_ghosts(version))
 
1647
                # write a combined record to our history preserving the current 
 
1648
                # parents as first in the list
 
1649
                new_parents = self.target.get_parents_with_ghosts(version) + list(n2.difference(n1))
 
1650
                self.target.fix_parents(version, new_parents)
 
1651
            return count
 
1652
        finally:
 
1653
            pb.finished()
 
1654
 
 
1655
 
 
1656
InterVersionedFile.register_optimiser(InterKnit)
 
1657
 
 
1658
 
 
1659
class WeaveToKnit(InterVersionedFile):
 
1660
    """Optimised code paths for weave to knit operations."""
 
1661
    
 
1662
    _matching_file_from_factory = bzrlib.weave.WeaveFile
 
1663
    _matching_file_to_factory = KnitVersionedFile
 
1664
    
 
1665
    @staticmethod
 
1666
    def is_compatible(source, target):
 
1667
        """Be compatible with weaves to knits."""
 
1668
        try:
 
1669
            return (isinstance(source, bzrlib.weave.Weave) and
 
1670
                    isinstance(target, KnitVersionedFile))
 
1671
        except AttributeError:
 
1672
            return False
 
1673
 
 
1674
    def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
 
1675
        """See InterVersionedFile.join."""
 
1676
        assert isinstance(self.source, bzrlib.weave.Weave)
 
1677
        assert isinstance(self.target, KnitVersionedFile)
 
1678
 
 
1679
        version_ids = self._get_source_version_ids(version_ids, ignore_missing)
 
1680
 
 
1681
        if not version_ids:
 
1682
            return 0
 
1683
 
 
1684
        pb = bzrlib.ui.ui_factory.nested_progress_bar()
 
1685
        try:
 
1686
            version_ids = list(version_ids)
 
1687
    
 
1688
            self.source_ancestry = set(self.source.get_ancestry(version_ids))
 
1689
            this_versions = set(self.target._index.get_versions())
 
1690
            needed_versions = self.source_ancestry - this_versions
 
1691
            cross_check_versions = self.source_ancestry.intersection(this_versions)
 
1692
            mismatched_versions = set()
 
1693
            for version in cross_check_versions:
 
1694
                # scan to include needed parents.
 
1695
                n1 = set(self.target.get_parents_with_ghosts(version))
 
1696
                n2 = set(self.source.get_parents(version))
 
1697
                # if all of n2's parents are in n1, then its fine.
 
1698
                if n2.difference(n1):
 
1699
                    # FIXME TEST this check for cycles being introduced works
 
1700
                    # the logic is we have a cycle if in our graph we are an
 
1701
                    # ancestor of any of the n2 revisions.
 
1702
                    for parent in n2:
 
1703
                        if parent in n1:
 
1704
                            # safe
 
1705
                            continue
 
1706
                        else:
 
1707
                            parent_ancestors = self.source.get_ancestry(parent)
 
1708
                            if version in parent_ancestors:
 
1709
                                raise errors.GraphCycleError([parent, version])
 
1710
                    # ensure this parent will be available later.
 
1711
                    new_parents = n2.difference(n1)
 
1712
                    needed_versions.update(new_parents.difference(this_versions))
 
1713
                    mismatched_versions.add(version)
 
1714
    
 
1715
            if not needed_versions and not mismatched_versions:
 
1716
                return 0
 
1717
            full_list = topo_sort(self.source.get_graph())
 
1718
    
 
1719
            version_list = [i for i in full_list if (not self.target.has_version(i)
 
1720
                            and i in needed_versions)]
 
1721
    
 
1722
            # do the join:
 
1723
            count = 0
 
1724
            total = len(version_list)
 
1725
            for version_id in version_list:
 
1726
                pb.update("Converting to knit", count, total)
 
1727
                parents = self.source.get_parents(version_id)
 
1728
                # check that its will be a consistent copy:
 
1729
                for parent in parents:
 
1730
                    # if source has the parent, we must already have it
 
1731
                    assert (self.target.has_version(parent))
 
1732
                self.target.add_lines(
 
1733
                    version_id, parents, self.source.get_lines(version_id))
 
1734
                count = count + 1
 
1735
 
 
1736
            for version in mismatched_versions:
 
1737
                # FIXME RBC 20060309 is this needed?
 
1738
                n1 = set(self.target.get_parents_with_ghosts(version))
 
1739
                n2 = set(self.source.get_parents(version))
 
1740
                # write a combined record to our history preserving the current 
 
1741
                # parents as first in the list
 
1742
                new_parents = self.target.get_parents_with_ghosts(version) + list(n2.difference(n1))
 
1743
                self.target.fix_parents(version, new_parents)
 
1744
            return count
 
1745
        finally:
 
1746
            pb.finished()
 
1747
 
 
1748
 
 
1749
InterVersionedFile.register_optimiser(WeaveToKnit)
 
1750
 
 
1751
 
 
1752
class KnitSequenceMatcher(difflib.SequenceMatcher):
 
1753
    """Knit tuned sequence matcher.
 
1754
 
 
1755
    This is based on profiling of difflib which indicated some improvements
 
1756
    for our usage pattern.
 
1757
    """
 
1758
 
 
1759
    def find_longest_match(self, alo, ahi, blo, bhi):
 
1760
        """Find longest matching block in a[alo:ahi] and b[blo:bhi].
 
1761
 
 
1762
        If isjunk is not defined:
 
1763
 
 
1764
        Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
 
1765
            alo <= i <= i+k <= ahi
 
1766
            blo <= j <= j+k <= bhi
 
1767
        and for all (i',j',k') meeting those conditions,
 
1768
            k >= k'
 
1769
            i <= i'
 
1770
            and if i == i', j <= j'
 
1771
 
 
1772
        In other words, of all maximal matching blocks, return one that
 
1773
        starts earliest in a, and of all those maximal matching blocks that
 
1774
        start earliest in a, return the one that starts earliest in b.
 
1775
 
 
1776
        >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
 
1777
        >>> s.find_longest_match(0, 5, 0, 9)
 
1778
        (0, 4, 5)
 
1779
 
 
1780
        If isjunk is defined, first the longest matching block is
 
1781
        determined as above, but with the additional restriction that no
 
1782
        junk element appears in the block.  Then that block is extended as
 
1783
        far as possible by matching (only) junk elements on both sides.  So
 
1784
        the resulting block never matches on junk except as identical junk
 
1785
        happens to be adjacent to an "interesting" match.
 
1786
 
 
1787
        Here's the same example as before, but considering blanks to be
 
1788
        junk.  That prevents " abcd" from matching the " abcd" at the tail
 
1789
        end of the second sequence directly.  Instead only the "abcd" can
 
1790
        match, and matches the leftmost "abcd" in the second sequence:
 
1791
 
 
1792
        >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
 
1793
        >>> s.find_longest_match(0, 5, 0, 9)
 
1794
        (1, 0, 4)
 
1795
 
 
1796
        If no blocks match, return (alo, blo, 0).
 
1797
 
 
1798
        >>> s = SequenceMatcher(None, "ab", "c")
 
1799
        >>> s.find_longest_match(0, 2, 0, 1)
 
1800
        (0, 0, 0)
 
1801
        """
 
1802
 
 
1803
        # CAUTION:  stripping common prefix or suffix would be incorrect.
 
1804
        # E.g.,
 
1805
        #    ab
 
1806
        #    acab
 
1807
        # Longest matching block is "ab", but if common prefix is
 
1808
        # stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
 
1809
        # strip, so ends up claiming that ab is changed to acab by
 
1810
        # inserting "ca" in the middle.  That's minimal but unintuitive:
 
1811
        # "it's obvious" that someone inserted "ac" at the front.
 
1812
        # Windiff ends up at the same place as diff, but by pairing up
 
1813
        # the unique 'b's and then matching the first two 'a's.
 
1814
 
 
1815
        a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.isbjunk
 
1816
        besti, bestj, bestsize = alo, blo, 0
 
1817
        # find longest junk-free match
 
1818
        # during an iteration of the loop, j2len[j] = length of longest
 
1819
        # junk-free match ending with a[i-1] and b[j]
 
1820
        j2len = {}
 
1821
        # nothing = []
 
1822
        b2jget = b2j.get
 
1823
        for i in xrange(alo, ahi):
 
1824
            # look at all instances of a[i] in b; note that because
 
1825
            # b2j has no junk keys, the loop is skipped if a[i] is junk
 
1826
            j2lenget = j2len.get
 
1827
            newj2len = {}
 
1828
            
 
1829
            # changing b2j.get(a[i], nothing) to a try:KeyError pair produced the
 
1830
            # following improvement
 
1831
            #     704  0   4650.5320   2620.7410   bzrlib.knit:1336(find_longest_match)
 
1832
            # +326674  0   1655.1210   1655.1210   +<method 'get' of 'dict' objects>
 
1833
            #  +76519  0    374.6700    374.6700   +<method 'has_key' of 'dict' objects>
 
1834
            # to 
 
1835
            #     704  0   3733.2820   2209.6520   bzrlib.knit:1336(find_longest_match)
 
1836
            #  +211400 0   1147.3520   1147.3520   +<method 'get' of 'dict' objects>
 
1837
            #  +76519  0    376.2780    376.2780   +<method 'has_key' of 'dict' objects>
 
1838
 
 
1839
            try:
 
1840
                js = b2j[a[i]]
 
1841
            except KeyError:
 
1842
                pass
 
1843
            else:
 
1844
                for j in js:
 
1845
                    # a[i] matches b[j]
 
1846
                    if j >= blo:
 
1847
                        if j >= bhi:
 
1848
                            break
 
1849
                        k = newj2len[j] = 1 + j2lenget(-1 + j, 0)
 
1850
                        if k > bestsize:
 
1851
                            besti, bestj, bestsize = 1 + i-k, 1 + j-k, k
 
1852
            j2len = newj2len
 
1853
 
 
1854
        # Extend the best by non-junk elements on each end.  In particular,
 
1855
        # "popular" non-junk elements aren't in b2j, which greatly speeds
 
1856
        # the inner loop above, but also means "the best" match so far
 
1857
        # doesn't contain any junk *or* popular non-junk elements.
 
1858
        while besti > alo and bestj > blo and \
 
1859
              not isbjunk(b[bestj-1]) and \
 
1860
              a[besti-1] == b[bestj-1]:
 
1861
            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
 
1862
        while besti+bestsize < ahi and bestj+bestsize < bhi and \
 
1863
              not isbjunk(b[bestj+bestsize]) and \
 
1864
              a[besti+bestsize] == b[bestj+bestsize]:
 
1865
            bestsize += 1
 
1866
 
 
1867
        # Now that we have a wholly interesting match (albeit possibly
 
1868
        # empty!), we may as well suck up the matching junk on each
 
1869
        # side of it too.  Can't think of a good reason not to, and it
 
1870
        # saves post-processing the (possibly considerable) expense of
 
1871
        # figuring out what to do with it.  In the case of an empty
 
1872
        # interesting match, this is clearly the right thing to do,
 
1873
        # because no other kind of match is possible in the regions.
 
1874
        while besti > alo and bestj > blo and \
 
1875
              isbjunk(b[bestj-1]) and \
 
1876
              a[besti-1] == b[bestj-1]:
 
1877
            besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
 
1878
        while besti+bestsize < ahi and bestj+bestsize < bhi and \
 
1879
              isbjunk(b[bestj+bestsize]) and \
 
1880
              a[besti+bestsize] == b[bestj+bestsize]:
 
1881
            bestsize = bestsize + 1
 
1882
 
 
1883
        return besti, bestj, bestsize
 
1884