~bzr-pqm/bzr/bzr.dev

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