~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2008-04-07 07:52:50 UTC
  • mfrom: (3340.1.1 208418-1.4)
  • Revision ID: pqm@pqm.ubuntu.com-20080407075250-phs53xnslo8boaeo
Return the correct knit serialisation method in _StreamAccess.
        (Andrew Bennetts, Martin Pool, Robert Collins)

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
1
# Copyright (C) 2005, 2006, 2007 Canonical Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
16
 
 
17
"""Knit versionedfile implementation.
 
18
 
 
19
A knit is a versioned file implementation that supports efficient append only
 
20
updates.
 
21
 
 
22
Knit file layout:
 
23
lifeless: the data file is made up of "delta records".  each delta record has a delta header 
 
24
that contains; (1) a version id, (2) the size of the delta (in lines), and (3)  the digest of 
 
25
the -expanded data- (ie, the delta applied to the parent).  the delta also ends with a 
 
26
end-marker; simply "end VERSION"
 
27
 
 
28
delta can be line or full contents.a
 
29
... the 8's there are the index number of the annotation.
 
30
version robertc@robertcollins.net-20051003014215-ee2990904cc4c7ad 7 c7d23b2a5bd6ca00e8e266cec0ec228158ee9f9e
 
31
59,59,3
 
32
8
 
33
8         if ie.executable:
 
34
8             e.set('executable', 'yes')
 
35
130,130,2
 
36
8         if elt.get('executable') == 'yes':
 
37
8             ie.executable = True
 
38
end robertc@robertcollins.net-20051003014215-ee2990904cc4c7ad 
 
39
 
 
40
 
 
41
whats in an index:
 
42
09:33 < jrydberg> lifeless: each index is made up of a tuple of; version id, options, position, size, parents
 
43
09:33 < jrydberg> lifeless: the parents are currently dictionary compressed
 
44
09:33 < jrydberg> lifeless: (meaning it currently does not support ghosts)
 
45
09:33 < lifeless> right
 
46
09:33 < jrydberg> lifeless: the position and size is the range in the data file
 
47
 
 
48
 
 
49
so the index sequence is the dictionary compressed sequence number used
 
50
in the deltas to provide line annotation
 
51
 
 
52
"""
 
53
 
 
54
# TODOS:
 
55
# 10:16 < lifeless> make partial index writes safe
 
56
# 10:16 < lifeless> implement 'knit.check()' like weave.check()
 
57
# 10:17 < lifeless> record known ghosts so we can detect when they are filled in rather than the current 'reweave 
 
58
#                    always' approach.
 
59
# move sha1 out of the content so that join is faster at verifying parents
 
60
# record content length ?
 
61
                  
 
62
 
 
63
from copy import copy
 
64
from cStringIO import StringIO
 
65
from itertools import izip, chain
 
66
import operator
 
67
import os
 
68
import sys
 
69
import warnings
 
70
from zlib import Z_DEFAULT_COMPRESSION
 
71
 
 
72
import bzrlib
 
73
from bzrlib.lazy_import import lazy_import
 
74
lazy_import(globals(), """
 
75
from bzrlib import (
 
76
    annotate,
 
77
    graph as _mod_graph,
 
78
    lru_cache,
 
79
    pack,
 
80
    trace,
 
81
    )
 
82
""")
 
83
from bzrlib import (
 
84
    cache_utf8,
 
85
    debug,
 
86
    diff,
 
87
    errors,
 
88
    osutils,
 
89
    patiencediff,
 
90
    progress,
 
91
    merge,
 
92
    ui,
 
93
    )
 
94
from bzrlib.errors import (
 
95
    FileExists,
 
96
    NoSuchFile,
 
97
    KnitError,
 
98
    InvalidRevisionId,
 
99
    KnitCorrupt,
 
100
    KnitHeaderError,
 
101
    RevisionNotPresent,
 
102
    RevisionAlreadyPresent,
 
103
    )
 
104
from bzrlib.graph import Graph
 
105
from bzrlib.osutils import (
 
106
    contains_whitespace,
 
107
    contains_linebreaks,
 
108
    sha_string,
 
109
    sha_strings,
 
110
    )
 
111
from bzrlib.symbol_versioning import (
 
112
    DEPRECATED_PARAMETER,
 
113
    deprecated_method,
 
114
    deprecated_passed,
 
115
    one_four,
 
116
    )
 
117
from bzrlib.tsort import topo_sort
 
118
from bzrlib.tuned_gzip import GzipFile, bytes_to_gzip
 
119
import bzrlib.ui
 
120
from bzrlib.versionedfile import VersionedFile, InterVersionedFile
 
121
import bzrlib.weave
 
122
 
 
123
 
 
124
# TODO: Split out code specific to this format into an associated object.
 
125
 
 
126
# TODO: Can we put in some kind of value to check that the index and data
 
127
# files belong together?
 
128
 
 
129
# TODO: accommodate binaries, perhaps by storing a byte count
 
130
 
 
131
# TODO: function to check whole file
 
132
 
 
133
# TODO: atomically append data, then measure backwards from the cursor
 
134
# position after writing to work out where it was located.  we may need to
 
135
# bypass python file buffering.
 
136
 
 
137
DATA_SUFFIX = '.knit'
 
138
INDEX_SUFFIX = '.kndx'
 
139
 
 
140
 
 
141
class KnitContent(object):
 
142
    """Content of a knit version to which deltas can be applied."""
 
143
 
 
144
    def __init__(self):
 
145
        self._should_strip_eol = False
 
146
 
 
147
    def annotate(self):
 
148
        """Return a list of (origin, text) tuples."""
 
149
        return list(self.annotate_iter())
 
150
 
 
151
    def apply_delta(self, delta, new_version_id):
 
152
        """Apply delta to this object to become new_version_id."""
 
153
        raise NotImplementedError(self.apply_delta)
 
154
 
 
155
    def cleanup_eol(self, copy_on_mutate=True):
 
156
        if self._should_strip_eol:
 
157
            if copy_on_mutate:
 
158
                self._lines = self._lines[:]
 
159
            self.strip_last_line_newline()
 
160
 
 
161
    def line_delta_iter(self, new_lines):
 
162
        """Generate line-based delta from this content to new_lines."""
 
163
        new_texts = new_lines.text()
 
164
        old_texts = self.text()
 
165
        s = patiencediff.PatienceSequenceMatcher(None, old_texts, new_texts)
 
166
        for tag, i1, i2, j1, j2 in s.get_opcodes():
 
167
            if tag == 'equal':
 
168
                continue
 
169
            # ofrom, oto, length, data
 
170
            yield i1, i2, j2 - j1, new_lines._lines[j1:j2]
 
171
 
 
172
    def line_delta(self, new_lines):
 
173
        return list(self.line_delta_iter(new_lines))
 
174
 
 
175
    @staticmethod
 
176
    def get_line_delta_blocks(knit_delta, source, target):
 
177
        """Extract SequenceMatcher.get_matching_blocks() from a knit delta"""
 
178
        target_len = len(target)
 
179
        s_pos = 0
 
180
        t_pos = 0
 
181
        for s_begin, s_end, t_len, new_text in knit_delta:
 
182
            true_n = s_begin - s_pos
 
183
            n = true_n
 
184
            if n > 0:
 
185
                # knit deltas do not provide reliable info about whether the
 
186
                # last line of a file matches, due to eol handling.
 
187
                if source[s_pos + n -1] != target[t_pos + n -1]:
 
188
                    n-=1
 
189
                if n > 0:
 
190
                    yield s_pos, t_pos, n
 
191
            t_pos += t_len + true_n
 
192
            s_pos = s_end
 
193
        n = target_len - t_pos
 
194
        if n > 0:
 
195
            if source[s_pos + n -1] != target[t_pos + n -1]:
 
196
                n-=1
 
197
            if n > 0:
 
198
                yield s_pos, t_pos, n
 
199
        yield s_pos + (target_len - t_pos), target_len, 0
 
200
 
 
201
 
 
202
class AnnotatedKnitContent(KnitContent):
 
203
    """Annotated content."""
 
204
 
 
205
    def __init__(self, lines):
 
206
        KnitContent.__init__(self)
 
207
        self._lines = lines
 
208
 
 
209
    def annotate_iter(self):
 
210
        """Yield tuples of (origin, text) for each content line."""
 
211
        return iter(self._lines)
 
212
 
 
213
    def apply_delta(self, delta, new_version_id):
 
214
        """Apply delta to this object to become new_version_id."""
 
215
        offset = 0
 
216
        lines = self._lines
 
217
        for start, end, count, delta_lines in delta:
 
218
            lines[offset+start:offset+end] = delta_lines
 
219
            offset = offset + (start - end) + count
 
220
 
 
221
    def strip_last_line_newline(self):
 
222
        line = self._lines[-1][1].rstrip('\n')
 
223
        self._lines[-1] = (self._lines[-1][0], line)
 
224
        self._should_strip_eol = False
 
225
 
 
226
    def text(self):
 
227
        try:
 
228
            lines = [text for origin, text in self._lines]
 
229
        except ValueError, e:
 
230
            # most commonly (only?) caused by the internal form of the knit
 
231
            # missing annotation information because of a bug - see thread
 
232
            # around 20071015
 
233
            raise KnitCorrupt(self,
 
234
                "line in annotated knit missing annotation information: %s"
 
235
                % (e,))
 
236
 
 
237
        if self._should_strip_eol:
 
238
            anno, line = lines[-1]
 
239
            lines[-1] = (anno, line.rstrip('\n'))
 
240
        return lines
 
241
 
 
242
    def copy(self):
 
243
        return AnnotatedKnitContent(self._lines[:])
 
244
 
 
245
 
 
246
class PlainKnitContent(KnitContent):
 
247
    """Unannotated content.
 
248
    
 
249
    When annotate[_iter] is called on this content, the same version is reported
 
250
    for all lines. Generally, annotate[_iter] is not useful on PlainKnitContent
 
251
    objects.
 
252
    """
 
253
 
 
254
    def __init__(self, lines, version_id):
 
255
        KnitContent.__init__(self)
 
256
        self._lines = lines
 
257
        self._version_id = version_id
 
258
 
 
259
    def annotate_iter(self):
 
260
        """Yield tuples of (origin, text) for each content line."""
 
261
        for line in self._lines:
 
262
            yield self._version_id, line
 
263
 
 
264
    def apply_delta(self, delta, new_version_id):
 
265
        """Apply delta to this object to become new_version_id."""
 
266
        offset = 0
 
267
        lines = self._lines
 
268
        for start, end, count, delta_lines in delta:
 
269
            lines[offset+start:offset+end] = delta_lines
 
270
            offset = offset + (start - end) + count
 
271
        self._version_id = new_version_id
 
272
 
 
273
    def copy(self):
 
274
        return PlainKnitContent(self._lines[:], self._version_id)
 
275
 
 
276
    def strip_last_line_newline(self):
 
277
        self._lines[-1] = self._lines[-1].rstrip('\n')
 
278
        self._should_strip_eol = False
 
279
 
 
280
    def text(self):
 
281
        lines = self._lines
 
282
        if self._should_strip_eol:
 
283
            lines = lines[:]
 
284
            lines[-1] = lines[-1].rstrip('\n')
 
285
        return lines
 
286
 
 
287
 
 
288
class _KnitFactory(object):
 
289
    """Base class for common Factory functions."""
 
290
 
 
291
    def parse_record(self, version_id, record, record_details,
 
292
                     base_content, copy_base_content=True):
 
293
        """Parse a record into a full content object.
 
294
 
 
295
        :param version_id: The official version id for this content
 
296
        :param record: The data returned by read_records_iter()
 
297
        :param record_details: Details about the record returned by
 
298
            get_build_details
 
299
        :param base_content: If get_build_details returns a compression_parent,
 
300
            you must return a base_content here, else use None
 
301
        :param copy_base_content: When building from the base_content, decide
 
302
            you can either copy it and return a new object, or modify it in
 
303
            place.
 
304
        :return: (content, delta) A Content object and possibly a line-delta,
 
305
            delta may be None
 
306
        """
 
307
        method, noeol = record_details
 
308
        if method == 'line-delta':
 
309
            assert base_content is not None
 
310
            if copy_base_content:
 
311
                content = base_content.copy()
 
312
            else:
 
313
                content = base_content
 
314
            delta = self.parse_line_delta(record, version_id)
 
315
            content.apply_delta(delta, version_id)
 
316
        else:
 
317
            content = self.parse_fulltext(record, version_id)
 
318
            delta = None
 
319
        content._should_strip_eol = noeol
 
320
        return (content, delta)
 
321
 
 
322
 
 
323
class KnitAnnotateFactory(_KnitFactory):
 
324
    """Factory for creating annotated Content objects."""
 
325
 
 
326
    annotated = True
 
327
 
 
328
    def make(self, lines, version_id):
 
329
        num_lines = len(lines)
 
330
        return AnnotatedKnitContent(zip([version_id] * num_lines, lines))
 
331
 
 
332
    def parse_fulltext(self, content, version_id):
 
333
        """Convert fulltext to internal representation
 
334
 
 
335
        fulltext content is of the format
 
336
        revid(utf8) plaintext\n
 
337
        internal representation is of the format:
 
338
        (revid, plaintext)
 
339
        """
 
340
        # TODO: jam 20070209 The tests expect this to be returned as tuples,
 
341
        #       but the code itself doesn't really depend on that.
 
342
        #       Figure out a way to not require the overhead of turning the
 
343
        #       list back into tuples.
 
344
        lines = [tuple(line.split(' ', 1)) for line in content]
 
345
        return AnnotatedKnitContent(lines)
 
346
 
 
347
    def parse_line_delta_iter(self, lines):
 
348
        return iter(self.parse_line_delta(lines))
 
349
 
 
350
    def parse_line_delta(self, lines, version_id, plain=False):
 
351
        """Convert a line based delta into internal representation.
 
352
 
 
353
        line delta is in the form of:
 
354
        intstart intend intcount
 
355
        1..count lines:
 
356
        revid(utf8) newline\n
 
357
        internal representation is
 
358
        (start, end, count, [1..count tuples (revid, newline)])
 
359
 
 
360
        :param plain: If True, the lines are returned as a plain
 
361
            list without annotations, not as a list of (origin, content) tuples, i.e.
 
362
            (start, end, count, [1..count newline])
 
363
        """
 
364
        result = []
 
365
        lines = iter(lines)
 
366
        next = lines.next
 
367
 
 
368
        cache = {}
 
369
        def cache_and_return(line):
 
370
            origin, text = line.split(' ', 1)
 
371
            return cache.setdefault(origin, origin), text
 
372
 
 
373
        # walk through the lines parsing.
 
374
        # Note that the plain test is explicitly pulled out of the
 
375
        # loop to minimise any performance impact
 
376
        if plain:
 
377
            for header in lines:
 
378
                start, end, count = [int(n) for n in header.split(',')]
 
379
                contents = [next().split(' ', 1)[1] for i in xrange(count)]
 
380
                result.append((start, end, count, contents))
 
381
        else:
 
382
            for header in lines:
 
383
                start, end, count = [int(n) for n in header.split(',')]
 
384
                contents = [tuple(next().split(' ', 1)) for i in xrange(count)]
 
385
                result.append((start, end, count, contents))
 
386
        return result
 
387
 
 
388
    def get_fulltext_content(self, lines):
 
389
        """Extract just the content lines from a fulltext."""
 
390
        return (line.split(' ', 1)[1] for line in lines)
 
391
 
 
392
    def get_linedelta_content(self, lines):
 
393
        """Extract just the content from a line delta.
 
394
 
 
395
        This doesn't return all of the extra information stored in a delta.
 
396
        Only the actual content lines.
 
397
        """
 
398
        lines = iter(lines)
 
399
        next = lines.next
 
400
        for header in lines:
 
401
            header = header.split(',')
 
402
            count = int(header[2])
 
403
            for i in xrange(count):
 
404
                origin, text = next().split(' ', 1)
 
405
                yield text
 
406
 
 
407
    def lower_fulltext(self, content):
 
408
        """convert a fulltext content record into a serializable form.
 
409
 
 
410
        see parse_fulltext which this inverts.
 
411
        """
 
412
        # TODO: jam 20070209 We only do the caching thing to make sure that
 
413
        #       the origin is a valid utf-8 line, eventually we could remove it
 
414
        return ['%s %s' % (o, t) for o, t in content._lines]
 
415
 
 
416
    def lower_line_delta(self, delta):
 
417
        """convert a delta into a serializable form.
 
418
 
 
419
        See parse_line_delta which this inverts.
 
420
        """
 
421
        # TODO: jam 20070209 We only do the caching thing to make sure that
 
422
        #       the origin is a valid utf-8 line, eventually we could remove it
 
423
        out = []
 
424
        for start, end, c, lines in delta:
 
425
            out.append('%d,%d,%d\n' % (start, end, c))
 
426
            out.extend(origin + ' ' + text
 
427
                       for origin, text in lines)
 
428
        return out
 
429
 
 
430
    def annotate_iter(self, knit, version_id):
 
431
        content = knit._get_content(version_id)
 
432
        return content.annotate_iter()
 
433
 
 
434
 
 
435
class KnitPlainFactory(_KnitFactory):
 
436
    """Factory for creating plain Content objects."""
 
437
 
 
438
    annotated = False
 
439
 
 
440
    def make(self, lines, version_id):
 
441
        return PlainKnitContent(lines, version_id)
 
442
 
 
443
    def parse_fulltext(self, content, version_id):
 
444
        """This parses an unannotated fulltext.
 
445
 
 
446
        Note that this is not a noop - the internal representation
 
447
        has (versionid, line) - its just a constant versionid.
 
448
        """
 
449
        return self.make(content, version_id)
 
450
 
 
451
    def parse_line_delta_iter(self, lines, version_id):
 
452
        cur = 0
 
453
        num_lines = len(lines)
 
454
        while cur < num_lines:
 
455
            header = lines[cur]
 
456
            cur += 1
 
457
            start, end, c = [int(n) for n in header.split(',')]
 
458
            yield start, end, c, lines[cur:cur+c]
 
459
            cur += c
 
460
 
 
461
    def parse_line_delta(self, lines, version_id):
 
462
        return list(self.parse_line_delta_iter(lines, version_id))
 
463
 
 
464
    def get_fulltext_content(self, lines):
 
465
        """Extract just the content lines from a fulltext."""
 
466
        return iter(lines)
 
467
 
 
468
    def get_linedelta_content(self, lines):
 
469
        """Extract just the content from a line delta.
 
470
 
 
471
        This doesn't return all of the extra information stored in a delta.
 
472
        Only the actual content lines.
 
473
        """
 
474
        lines = iter(lines)
 
475
        next = lines.next
 
476
        for header in lines:
 
477
            header = header.split(',')
 
478
            count = int(header[2])
 
479
            for i in xrange(count):
 
480
                yield next()
 
481
 
 
482
    def lower_fulltext(self, content):
 
483
        return content.text()
 
484
 
 
485
    def lower_line_delta(self, delta):
 
486
        out = []
 
487
        for start, end, c, lines in delta:
 
488
            out.append('%d,%d,%d\n' % (start, end, c))
 
489
            out.extend(lines)
 
490
        return out
 
491
 
 
492
    def annotate_iter(self, knit, version_id):
 
493
        annotator = _KnitAnnotator(knit)
 
494
        return iter(annotator.annotate(version_id))
 
495
 
 
496
 
 
497
def make_empty_knit(transport, relpath):
 
498
    """Construct a empty knit at the specified location."""
 
499
    k = KnitVersionedFile(transport, relpath, 'w', KnitPlainFactory)
 
500
 
 
501
 
 
502
class KnitVersionedFile(VersionedFile):
 
503
    """Weave-like structure with faster random access.
 
504
 
 
505
    A knit stores a number of texts and a summary of the relationships
 
506
    between them.  Texts are identified by a string version-id.  Texts
 
507
    are normally stored and retrieved as a series of lines, but can
 
508
    also be passed as single strings.
 
509
 
 
510
    Lines are stored with the trailing newline (if any) included, to
 
511
    avoid special cases for files with no final newline.  Lines are
 
512
    composed of 8-bit characters, not unicode.  The combination of
 
513
    these approaches should mean any 'binary' file can be safely
 
514
    stored and retrieved.
 
515
    """
 
516
 
 
517
    def __init__(self, relpath, transport, file_mode=None, access_mode=None,
 
518
        factory=None, delta=True, create=False, create_parent_dir=False,
 
519
        delay_create=False, dir_mode=None, index=None, access_method=None):
 
520
        """Construct a knit at location specified by relpath.
 
521
        
 
522
        :param create: If not True, only open an existing knit.
 
523
        :param create_parent_dir: If True, create the parent directory if 
 
524
            creating the file fails. (This is used for stores with 
 
525
            hash-prefixes that may not exist yet)
 
526
        :param delay_create: The calling code is aware that the knit won't 
 
527
            actually be created until the first data is stored.
 
528
        :param index: An index to use for the knit.
 
529
        """
 
530
        if access_mode is None:
 
531
            access_mode = 'w'
 
532
        super(KnitVersionedFile, self).__init__(access_mode)
 
533
        assert access_mode in ('r', 'w'), "invalid mode specified %r" % access_mode
 
534
        self.transport = transport
 
535
        self.filename = relpath
 
536
        self.factory = factory or KnitAnnotateFactory()
 
537
        self.writable = (access_mode == 'w')
 
538
        self.delta = delta
 
539
 
 
540
        self._max_delta_chain = 200
 
541
 
 
542
        if index is None:
 
543
            self._index = _KnitIndex(transport, relpath + INDEX_SUFFIX,
 
544
                access_mode, create=create, file_mode=file_mode,
 
545
                create_parent_dir=create_parent_dir, delay_create=delay_create,
 
546
                dir_mode=dir_mode)
 
547
        else:
 
548
            self._index = index
 
549
        if access_method is None:
 
550
            _access = _KnitAccess(transport, relpath + DATA_SUFFIX, file_mode, dir_mode,
 
551
                ((create and not len(self)) and delay_create), create_parent_dir)
 
552
        else:
 
553
            _access = access_method
 
554
        if create and not len(self) and not delay_create:
 
555
            _access.create()
 
556
        self._data = _KnitData(_access)
 
557
 
 
558
    def __repr__(self):
 
559
        return '%s(%s)' % (self.__class__.__name__,
 
560
                           self.transport.abspath(self.filename))
 
561
    
 
562
    def _check_should_delta(self, first_parents):
 
563
        """Iterate back through the parent listing, looking for a fulltext.
 
564
 
 
565
        This is used when we want to decide whether to add a delta or a new
 
566
        fulltext. It searches for _max_delta_chain parents. When it finds a
 
567
        fulltext parent, it sees if the total size of the deltas leading up to
 
568
        it is large enough to indicate that we want a new full text anyway.
 
569
 
 
570
        Return True if we should create a new delta, False if we should use a
 
571
        full text.
 
572
        """
 
573
        delta_size = 0
 
574
        fulltext_size = None
 
575
        delta_parents = first_parents
 
576
        for count in xrange(self._max_delta_chain):
 
577
            parent = delta_parents[0]
 
578
            method = self._index.get_method(parent)
 
579
            index, pos, size = self._index.get_position(parent)
 
580
            if method == 'fulltext':
 
581
                fulltext_size = size
 
582
                break
 
583
            delta_size += size
 
584
            delta_parents = self._index.get_parent_map([parent])[parent]
 
585
        else:
 
586
            # We couldn't find a fulltext, so we must create a new one
 
587
            return False
 
588
 
 
589
        return fulltext_size > delta_size
 
590
 
 
591
    def _add_raw_records(self, records, data):
 
592
        """Add all the records 'records' with data pre-joined in 'data'.
 
593
 
 
594
        :param records: A list of tuples(version_id, options, parents, size).
 
595
        :param data: The data for the records. When it is written, the records
 
596
                     are adjusted to have pos pointing into data by the sum of
 
597
                     the preceding records sizes.
 
598
        """
 
599
        # write all the data
 
600
        raw_record_sizes = [record[3] for record in records]
 
601
        positions = self._data.add_raw_records(raw_record_sizes, data)
 
602
        offset = 0
 
603
        index_entries = []
 
604
        for (version_id, options, parents, size), access_memo in zip(
 
605
            records, positions):
 
606
            index_entries.append((version_id, options, access_memo, parents))
 
607
            if self._data._do_cache:
 
608
                self._data._cache[version_id] = data[offset:offset+size]
 
609
            offset += size
 
610
        self._index.add_versions(index_entries)
 
611
 
 
612
    def enable_cache(self):
 
613
        """Start caching data for this knit"""
 
614
        self._data.enable_cache()
 
615
 
 
616
    def clear_cache(self):
 
617
        """Clear the data cache only."""
 
618
        self._data.clear_cache()
 
619
 
 
620
    def copy_to(self, name, transport):
 
621
        """See VersionedFile.copy_to()."""
 
622
        # copy the current index to a temp index to avoid racing with local
 
623
        # writes
 
624
        transport.put_file_non_atomic(name + INDEX_SUFFIX + '.tmp',
 
625
                self.transport.get(self._index._filename))
 
626
        # copy the data file
 
627
        f = self._data._open_file()
 
628
        try:
 
629
            transport.put_file(name + DATA_SUFFIX, f)
 
630
        finally:
 
631
            f.close()
 
632
        # move the copied index into place
 
633
        transport.move(name + INDEX_SUFFIX + '.tmp', name + INDEX_SUFFIX)
 
634
 
 
635
    def get_data_stream(self, required_versions):
 
636
        """Get a data stream for the specified versions.
 
637
 
 
638
        Versions may be returned in any order, not necessarily the order
 
639
        specified.  They are returned in a partial order by compression
 
640
        parent, so that the deltas can be applied as the data stream is
 
641
        inserted; however note that compression parents will not be sent
 
642
        unless they were specifically requested, as the client may already
 
643
        have them.
 
644
 
 
645
        :param required_versions: The exact set of versions to be extracted.
 
646
            Unlike some other knit methods, this is not used to generate a
 
647
            transitive closure, rather it is used precisely as given.
 
648
        
 
649
        :returns: format_signature, list of (version, options, length, parents),
 
650
            reader_callable.
 
651
        """
 
652
        required_version_set = frozenset(required_versions)
 
653
        version_index = {}
 
654
        # list of revisions that can just be sent without waiting for their
 
655
        # compression parent
 
656
        ready_to_send = []
 
657
        # map from revision to the children based on it
 
658
        deferred = {}
 
659
        # first, read all relevant index data, enough to sort into the right
 
660
        # order to return
 
661
        for version_id in required_versions:
 
662
            options = self._index.get_options(version_id)
 
663
            parents = self._index.get_parents_with_ghosts(version_id)
 
664
            index_memo = self._index.get_position(version_id)
 
665
            version_index[version_id] = (index_memo, options, parents)
 
666
            if ('line-delta' in options
 
667
                and parents[0] in required_version_set):
 
668
                # must wait until the parent has been sent
 
669
                deferred.setdefault(parents[0], []). \
 
670
                    append(version_id)
 
671
            else:
 
672
                # either a fulltext, or a delta whose parent the client did
 
673
                # not ask for and presumably already has
 
674
                ready_to_send.append(version_id)
 
675
        # build a list of results to return, plus instructions for data to
 
676
        # read from the file
 
677
        copy_queue_records = []
 
678
        temp_version_list = []
 
679
        while ready_to_send:
 
680
            # XXX: pushing and popping lists may be a bit inefficient
 
681
            version_id = ready_to_send.pop(0)
 
682
            (index_memo, options, parents) = version_index[version_id]
 
683
            copy_queue_records.append((version_id, index_memo))
 
684
            none, data_pos, data_size = index_memo
 
685
            temp_version_list.append((version_id, options, data_size,
 
686
                parents))
 
687
            if version_id in deferred:
 
688
                # now we can send all the children of this revision - we could
 
689
                # put them in anywhere, but we hope that sending them soon
 
690
                # after the fulltext will give good locality in the receiver
 
691
                ready_to_send[:0] = deferred.pop(version_id)
 
692
        assert len(deferred) == 0, \
 
693
            "Still have compressed child versions waiting to be sent"
 
694
        # XXX: The stream format is such that we cannot stream it - we have to
 
695
        # know the length of all the data a-priori.
 
696
        raw_datum = []
 
697
        result_version_list = []
 
698
        for (version_id, raw_data), \
 
699
            (version_id2, options, _, parents) in \
 
700
            izip(self._data.read_records_iter_raw(copy_queue_records),
 
701
                 temp_version_list):
 
702
            assert version_id == version_id2, \
 
703
                'logic error, inconsistent results'
 
704
            raw_datum.append(raw_data)
 
705
            result_version_list.append(
 
706
                (version_id, options, len(raw_data), parents))
 
707
        # provide a callback to get data incrementally.
 
708
        pseudo_file = StringIO(''.join(raw_datum))
 
709
        def read(length):
 
710
            if length is None:
 
711
                return pseudo_file.read()
 
712
            else:
 
713
                return pseudo_file.read(length)
 
714
        return (self.get_format_signature(), result_version_list, read)
 
715
 
 
716
    def _extract_blocks(self, version_id, source, target):
 
717
        if self._index.get_method(version_id) != 'line-delta':
 
718
            return None
 
719
        parent, sha1, noeol, delta = self.get_delta(version_id)
 
720
        return KnitContent.get_line_delta_blocks(delta, source, target)
 
721
 
 
722
    def get_delta(self, version_id):
 
723
        """Get a delta for constructing version from some other version."""
 
724
        self.check_not_reserved_id(version_id)
 
725
        parents = self.get_parent_map([version_id])[version_id]
 
726
        if len(parents):
 
727
            parent = parents[0]
 
728
        else:
 
729
            parent = None
 
730
        index_memo = self._index.get_position(version_id)
 
731
        data, sha1 = self._data.read_records(((version_id, index_memo),))[version_id]
 
732
        noeol = 'no-eol' in self._index.get_options(version_id)
 
733
        if 'fulltext' == self._index.get_method(version_id):
 
734
            new_content = self.factory.parse_fulltext(data, version_id)
 
735
            if parent is not None:
 
736
                reference_content = self._get_content(parent)
 
737
                old_texts = reference_content.text()
 
738
            else:
 
739
                old_texts = []
 
740
            new_texts = new_content.text()
 
741
            delta_seq = patiencediff.PatienceSequenceMatcher(None, old_texts,
 
742
                                                             new_texts)
 
743
            return parent, sha1, noeol, self._make_line_delta(delta_seq, new_content)
 
744
        else:
 
745
            delta = self.factory.parse_line_delta(data, version_id)
 
746
            return parent, sha1, noeol, delta
 
747
 
 
748
    def get_format_signature(self):
 
749
        """See VersionedFile.get_format_signature()."""
 
750
        if self.factory.annotated:
 
751
            annotated_part = "annotated"
 
752
        else:
 
753
            annotated_part = "plain"
 
754
        return "knit-%s" % (annotated_part,)
 
755
        
 
756
    @deprecated_method(one_four)
 
757
    def get_graph_with_ghosts(self):
 
758
        """See VersionedFile.get_graph_with_ghosts()."""
 
759
        return self.get_parent_map(self.versions())
 
760
 
 
761
    def get_sha1(self, version_id):
 
762
        return self.get_sha1s([version_id])[0]
 
763
 
 
764
    def get_sha1s(self, version_ids):
 
765
        """See VersionedFile.get_sha1()."""
 
766
        record_map = self._get_record_map(version_ids)
 
767
        # record entry 2 is the 'digest'.
 
768
        return [record_map[v][2] for v in version_ids]
 
769
 
 
770
    @staticmethod
 
771
    def get_suffixes():
 
772
        """See VersionedFile.get_suffixes()."""
 
773
        return [DATA_SUFFIX, INDEX_SUFFIX]
 
774
 
 
775
    @deprecated_method(one_four)
 
776
    def has_ghost(self, version_id):
 
777
        """True if there is a ghost reference in the file to version_id."""
 
778
        # maybe we have it
 
779
        if self.has_version(version_id):
 
780
            return False
 
781
        # optimisable if needed by memoising the _ghosts set.
 
782
        items = self.get_parent_map(self.versions())
 
783
        for parents in items.itervalues():
 
784
            for parent in parents:
 
785
                if parent == version_id and parent not in items:
 
786
                    return True
 
787
        return False
 
788
 
 
789
    def insert_data_stream(self, (format, data_list, reader_callable)):
 
790
        """Insert knit records from a data stream into this knit.
 
791
 
 
792
        If a version in the stream is already present in this knit, it will not
 
793
        be inserted a second time.  It will be checked for consistency with the
 
794
        stored version however, and may cause a KnitCorrupt error to be raised
 
795
        if the data in the stream disagrees with the already stored data.
 
796
        
 
797
        :seealso: get_data_stream
 
798
        """
 
799
        if format != self.get_format_signature():
 
800
            if 'knit' in debug.debug_flags:
 
801
                trace.mutter(
 
802
                    'incompatible format signature inserting to %r', self)
 
803
            source = self._knit_from_datastream(
 
804
                (format, data_list, reader_callable))
 
805
            self.join(source)
 
806
            return
 
807
 
 
808
        for version_id, options, length, parents in data_list:
 
809
            if self.has_version(version_id):
 
810
                # First check: the list of parents.
 
811
                my_parents = self.get_parents_with_ghosts(version_id)
 
812
                if tuple(my_parents) != tuple(parents):
 
813
                    # XXX: KnitCorrupt is not quite the right exception here.
 
814
                    raise KnitCorrupt(
 
815
                        self.filename,
 
816
                        'parents list %r from data stream does not match '
 
817
                        'already recorded parents %r for %s'
 
818
                        % (parents, my_parents, version_id))
 
819
 
 
820
                # Also check the SHA-1 of the fulltext this content will
 
821
                # produce.
 
822
                raw_data = reader_callable(length)
 
823
                my_fulltext_sha1 = self.get_sha1(version_id)
 
824
                df, rec = self._data._parse_record_header(version_id, raw_data)
 
825
                stream_fulltext_sha1 = rec[3]
 
826
                if my_fulltext_sha1 != stream_fulltext_sha1:
 
827
                    # Actually, we don't know if it's this knit that's corrupt,
 
828
                    # or the data stream we're trying to insert.
 
829
                    raise KnitCorrupt(
 
830
                        self.filename, 'sha-1 does not match %s' % version_id)
 
831
            else:
 
832
                if 'line-delta' in options:
 
833
                    # Make sure that this knit record is actually useful: a
 
834
                    # line-delta is no use unless we have its parent.
 
835
                    # Fetching from a broken repository with this problem
 
836
                    # shouldn't break the target repository.
 
837
                    #
 
838
                    # See https://bugs.launchpad.net/bzr/+bug/164443
 
839
                    if not self._index.has_version(parents[0]):
 
840
                        raise KnitCorrupt(
 
841
                            self.filename,
 
842
                            'line-delta from stream '
 
843
                            'for version %s '
 
844
                            'references '
 
845
                            'missing parent %s\n'
 
846
                            'Try running "bzr check" '
 
847
                            'on the source repository, and "bzr reconcile" '
 
848
                            'if necessary.' %
 
849
                            (version_id, parents[0]))
 
850
                self._add_raw_records(
 
851
                    [(version_id, options, parents, length)],
 
852
                    reader_callable(length))
 
853
 
 
854
    def _knit_from_datastream(self, (format, data_list, reader_callable)):
 
855
        """Create a knit object from a data stream.
 
856
 
 
857
        This method exists to allow conversion of data streams that do not
 
858
        match the signature of this knit. Generally it will be slower and use
 
859
        more memory to use this method to insert data, but it will work.
 
860
 
 
861
        :seealso: get_data_stream for details on datastreams.
 
862
        :return: A knit versioned file which can be used to join the datastream
 
863
            into self.
 
864
        """
 
865
        if format == "knit-plain":
 
866
            factory = KnitPlainFactory()
 
867
        elif format == "knit-annotated":
 
868
            factory = KnitAnnotateFactory()
 
869
        else:
 
870
            raise errors.KnitDataStreamUnknown(format)
 
871
        index = _StreamIndex(data_list, self._index)
 
872
        access = _StreamAccess(reader_callable, index, self, factory)
 
873
        return KnitVersionedFile(self.filename, self.transport,
 
874
            factory=factory, index=index, access_method=access)
 
875
 
 
876
    def versions(self):
 
877
        """See VersionedFile.versions."""
 
878
        if 'evil' in debug.debug_flags:
 
879
            trace.mutter_callsite(2, "versions scales with size of history")
 
880
        return self._index.get_versions()
 
881
 
 
882
    def has_version(self, version_id):
 
883
        """See VersionedFile.has_version."""
 
884
        if 'evil' in debug.debug_flags:
 
885
            trace.mutter_callsite(2, "has_version is a LBYL scenario")
 
886
        return self._index.has_version(version_id)
 
887
 
 
888
    __contains__ = has_version
 
889
 
 
890
    def _merge_annotations(self, content, parents, parent_texts={},
 
891
                           delta=None, annotated=None,
 
892
                           left_matching_blocks=None):
 
893
        """Merge annotations for content.  This is done by comparing
 
894
        the annotations based on changed to the text.
 
895
        """
 
896
        if left_matching_blocks is not None:
 
897
            delta_seq = diff._PrematchedMatcher(left_matching_blocks)
 
898
        else:
 
899
            delta_seq = None
 
900
        if annotated:
 
901
            for parent_id in parents:
 
902
                merge_content = self._get_content(parent_id, parent_texts)
 
903
                if (parent_id == parents[0] and delta_seq is not None):
 
904
                    seq = delta_seq
 
905
                else:
 
906
                    seq = patiencediff.PatienceSequenceMatcher(
 
907
                        None, merge_content.text(), content.text())
 
908
                for i, j, n in seq.get_matching_blocks():
 
909
                    if n == 0:
 
910
                        continue
 
911
                    # this appears to copy (origin, text) pairs across to the
 
912
                    # new content for any line that matches the last-checked
 
913
                    # parent.
 
914
                    content._lines[j:j+n] = merge_content._lines[i:i+n]
 
915
        if delta:
 
916
            if delta_seq is None:
 
917
                reference_content = self._get_content(parents[0], parent_texts)
 
918
                new_texts = content.text()
 
919
                old_texts = reference_content.text()
 
920
                delta_seq = patiencediff.PatienceSequenceMatcher(
 
921
                                                 None, old_texts, new_texts)
 
922
            return self._make_line_delta(delta_seq, content)
 
923
 
 
924
    def _make_line_delta(self, delta_seq, new_content):
 
925
        """Generate a line delta from delta_seq and new_content."""
 
926
        diff_hunks = []
 
927
        for op in delta_seq.get_opcodes():
 
928
            if op[0] == 'equal':
 
929
                continue
 
930
            diff_hunks.append((op[1], op[2], op[4]-op[3], new_content._lines[op[3]:op[4]]))
 
931
        return diff_hunks
 
932
 
 
933
    def _get_components_positions(self, version_ids):
 
934
        """Produce a map of position data for the components of versions.
 
935
 
 
936
        This data is intended to be used for retrieving the knit records.
 
937
 
 
938
        A dict of version_id to (record_details, index_memo, next, parents) is
 
939
        returned.
 
940
        method is the way referenced data should be applied.
 
941
        index_memo is the handle to pass to the data access to actually get the
 
942
            data
 
943
        next is the build-parent of the version, or None for fulltexts.
 
944
        parents is the version_ids of the parents of this version
 
945
        """
 
946
        component_data = {}
 
947
        pending_components = version_ids
 
948
        while pending_components:
 
949
            build_details = self._index.get_build_details(pending_components)
 
950
            current_components = set(pending_components)
 
951
            pending_components = set()
 
952
            for version_id, details in build_details.iteritems():
 
953
                (index_memo, compression_parent, parents,
 
954
                 record_details) = details
 
955
                method = record_details[0]
 
956
                if compression_parent is not None:
 
957
                    pending_components.add(compression_parent)
 
958
                component_data[version_id] = (record_details, index_memo,
 
959
                                              compression_parent)
 
960
            missing = current_components.difference(build_details)
 
961
            if missing:
 
962
                raise errors.RevisionNotPresent(missing.pop(), self.filename)
 
963
        return component_data
 
964
       
 
965
    def _get_content(self, version_id, parent_texts={}):
 
966
        """Returns a content object that makes up the specified
 
967
        version."""
 
968
        cached_version = parent_texts.get(version_id, None)
 
969
        if cached_version is not None:
 
970
            if not self.has_version(version_id):
 
971
                raise RevisionNotPresent(version_id, self.filename)
 
972
            return cached_version
 
973
 
 
974
        text_map, contents_map = self._get_content_maps([version_id])
 
975
        return contents_map[version_id]
 
976
 
 
977
    def _check_versions_present(self, version_ids):
 
978
        """Check that all specified versions are present."""
 
979
        self._index.check_versions_present(version_ids)
 
980
 
 
981
    def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts,
 
982
        nostore_sha, random_id, check_content, left_matching_blocks):
 
983
        """See VersionedFile.add_lines_with_ghosts()."""
 
984
        self._check_add(version_id, lines, random_id, check_content)
 
985
        return self._add(version_id, lines, parents, self.delta,
 
986
            parent_texts, left_matching_blocks, nostore_sha, random_id)
 
987
 
 
988
    def _add_lines(self, version_id, parents, lines, parent_texts,
 
989
        left_matching_blocks, nostore_sha, random_id, check_content):
 
990
        """See VersionedFile.add_lines."""
 
991
        self._check_add(version_id, lines, random_id, check_content)
 
992
        self._check_versions_present(parents)
 
993
        return self._add(version_id, lines[:], parents, self.delta,
 
994
            parent_texts, left_matching_blocks, nostore_sha, random_id)
 
995
 
 
996
    def _check_add(self, version_id, lines, random_id, check_content):
 
997
        """check that version_id and lines are safe to add."""
 
998
        if contains_whitespace(version_id):
 
999
            raise InvalidRevisionId(version_id, self.filename)
 
1000
        self.check_not_reserved_id(version_id)
 
1001
        # Technically this could be avoided if we are happy to allow duplicate
 
1002
        # id insertion when other things than bzr core insert texts, but it
 
1003
        # seems useful for folk using the knit api directly to have some safety
 
1004
        # blanket that we can disable.
 
1005
        if not random_id and self.has_version(version_id):
 
1006
            raise RevisionAlreadyPresent(version_id, self.filename)
 
1007
        if check_content:
 
1008
            self._check_lines_not_unicode(lines)
 
1009
            self._check_lines_are_lines(lines)
 
1010
 
 
1011
    def _add(self, version_id, lines, parents, delta, parent_texts,
 
1012
        left_matching_blocks, nostore_sha, random_id):
 
1013
        """Add a set of lines on top of version specified by parents.
 
1014
 
 
1015
        If delta is true, compress the text as a line-delta against
 
1016
        the first parent.
 
1017
 
 
1018
        Any versions not present will be converted into ghosts.
 
1019
        """
 
1020
        # first thing, if the content is something we don't need to store, find
 
1021
        # that out.
 
1022
        line_bytes = ''.join(lines)
 
1023
        digest = sha_string(line_bytes)
 
1024
        if nostore_sha == digest:
 
1025
            raise errors.ExistingContent
 
1026
 
 
1027
        present_parents = []
 
1028
        if parent_texts is None:
 
1029
            parent_texts = {}
 
1030
        for parent in parents:
 
1031
            if self.has_version(parent):
 
1032
                present_parents.append(parent)
 
1033
 
 
1034
        # can only compress against the left most present parent.
 
1035
        if (delta and
 
1036
            (len(present_parents) == 0 or
 
1037
             present_parents[0] != parents[0])):
 
1038
            delta = False
 
1039
 
 
1040
        text_length = len(line_bytes)
 
1041
        options = []
 
1042
        if lines:
 
1043
            if lines[-1][-1] != '\n':
 
1044
                # copy the contents of lines.
 
1045
                lines = lines[:]
 
1046
                options.append('no-eol')
 
1047
                lines[-1] = lines[-1] + '\n'
 
1048
                line_bytes += '\n'
 
1049
 
 
1050
        if delta:
 
1051
            # To speed the extract of texts the delta chain is limited
 
1052
            # to a fixed number of deltas.  This should minimize both
 
1053
            # I/O and the time spend applying deltas.
 
1054
            delta = self._check_should_delta(present_parents)
 
1055
 
 
1056
        assert isinstance(version_id, str)
 
1057
        content = self.factory.make(lines, version_id)
 
1058
        if delta or (self.factory.annotated and len(present_parents) > 0):
 
1059
            # Merge annotations from parent texts if needed.
 
1060
            delta_hunks = self._merge_annotations(content, present_parents,
 
1061
                parent_texts, delta, self.factory.annotated,
 
1062
                left_matching_blocks)
 
1063
 
 
1064
        if delta:
 
1065
            options.append('line-delta')
 
1066
            store_lines = self.factory.lower_line_delta(delta_hunks)
 
1067
            size, bytes = self._data._record_to_data(version_id, digest,
 
1068
                store_lines)
 
1069
        else:
 
1070
            options.append('fulltext')
 
1071
            # isinstance is slower and we have no hierarchy.
 
1072
            if self.factory.__class__ == KnitPlainFactory:
 
1073
                # Use the already joined bytes saving iteration time in
 
1074
                # _record_to_data.
 
1075
                size, bytes = self._data._record_to_data(version_id, digest,
 
1076
                    lines, [line_bytes])
 
1077
            else:
 
1078
                # get mixed annotation + content and feed it into the
 
1079
                # serialiser.
 
1080
                store_lines = self.factory.lower_fulltext(content)
 
1081
                size, bytes = self._data._record_to_data(version_id, digest,
 
1082
                    store_lines)
 
1083
 
 
1084
        access_memo = self._data.add_raw_records([size], bytes)[0]
 
1085
        self._index.add_versions(
 
1086
            ((version_id, options, access_memo, parents),),
 
1087
            random_id=random_id)
 
1088
        return digest, text_length, content
 
1089
 
 
1090
    def check(self, progress_bar=None):
 
1091
        """See VersionedFile.check()."""
 
1092
 
 
1093
    def _clone_text(self, new_version_id, old_version_id, parents):
 
1094
        """See VersionedFile.clone_text()."""
 
1095
        # FIXME RBC 20060228 make fast by only inserting an index with null 
 
1096
        # delta.
 
1097
        self.add_lines(new_version_id, parents, self.get_lines(old_version_id))
 
1098
 
 
1099
    def get_lines(self, version_id):
 
1100
        """See VersionedFile.get_lines()."""
 
1101
        return self.get_line_list([version_id])[0]
 
1102
 
 
1103
    def _get_record_map(self, version_ids):
 
1104
        """Produce a dictionary of knit records.
 
1105
        
 
1106
        :return: {version_id:(record, record_details, digest, next)}
 
1107
            record
 
1108
                data returned from read_records
 
1109
            record_details
 
1110
                opaque information to pass to parse_record
 
1111
            digest
 
1112
                SHA1 digest of the full text after all steps are done
 
1113
            next
 
1114
                build-parent of the version, i.e. the leftmost ancestor.
 
1115
                Will be None if the record is not a delta.
 
1116
        """
 
1117
        position_map = self._get_components_positions(version_ids)
 
1118
        # c = component_id, r = record_details, i_m = index_memo, n = next
 
1119
        records = [(c, i_m) for c, (r, i_m, n)
 
1120
                             in position_map.iteritems()]
 
1121
        record_map = {}
 
1122
        for component_id, record, digest in \
 
1123
                self._data.read_records_iter(records):
 
1124
            (record_details, index_memo, next) = position_map[component_id]
 
1125
            record_map[component_id] = record, record_details, digest, next
 
1126
 
 
1127
        return record_map
 
1128
 
 
1129
    def get_text(self, version_id):
 
1130
        """See VersionedFile.get_text"""
 
1131
        return self.get_texts([version_id])[0]
 
1132
 
 
1133
    def get_texts(self, version_ids):
 
1134
        return [''.join(l) for l in self.get_line_list(version_ids)]
 
1135
 
 
1136
    def get_line_list(self, version_ids):
 
1137
        """Return the texts of listed versions as a list of strings."""
 
1138
        for version_id in version_ids:
 
1139
            self.check_not_reserved_id(version_id)
 
1140
        text_map, content_map = self._get_content_maps(version_ids)
 
1141
        return [text_map[v] for v in version_ids]
 
1142
 
 
1143
    _get_lf_split_line_list = get_line_list
 
1144
 
 
1145
    def _get_content_maps(self, version_ids):
 
1146
        """Produce maps of text and KnitContents
 
1147
        
 
1148
        :return: (text_map, content_map) where text_map contains the texts for
 
1149
        the requested versions and content_map contains the KnitContents.
 
1150
        Both dicts take version_ids as their keys.
 
1151
        """
 
1152
        # FUTURE: This function could be improved for the 'extract many' case
 
1153
        # by tracking each component and only doing the copy when the number of
 
1154
        # children than need to apply delta's to it is > 1 or it is part of the
 
1155
        # final output.
 
1156
        version_ids = list(version_ids)
 
1157
        multiple_versions = len(version_ids) != 1
 
1158
        record_map = self._get_record_map(version_ids)
 
1159
 
 
1160
        text_map = {}
 
1161
        content_map = {}
 
1162
        final_content = {}
 
1163
        for version_id in version_ids:
 
1164
            components = []
 
1165
            cursor = version_id
 
1166
            while cursor is not None:
 
1167
                record, record_details, digest, next = record_map[cursor]
 
1168
                components.append((cursor, record, record_details, digest))
 
1169
                if cursor in content_map:
 
1170
                    break
 
1171
                cursor = next
 
1172
 
 
1173
            content = None
 
1174
            for (component_id, record, record_details,
 
1175
                 digest) in reversed(components):
 
1176
                if component_id in content_map:
 
1177
                    content = content_map[component_id]
 
1178
                else:
 
1179
                    content, delta = self.factory.parse_record(version_id,
 
1180
                        record, record_details, content,
 
1181
                        copy_base_content=multiple_versions)
 
1182
                    if multiple_versions:
 
1183
                        content_map[component_id] = content
 
1184
 
 
1185
            content.cleanup_eol(copy_on_mutate=multiple_versions)
 
1186
            final_content[version_id] = content
 
1187
 
 
1188
            # digest here is the digest from the last applied component.
 
1189
            text = content.text()
 
1190
            actual_sha = sha_strings(text)
 
1191
            if actual_sha != digest:
 
1192
                raise KnitCorrupt(self.filename,
 
1193
                    '\n  sha-1 %s'
 
1194
                    '\n  of reconstructed text does not match'
 
1195
                    '\n  expected %s'
 
1196
                    '\n  for version %s' %
 
1197
                    (actual_sha, digest, version_id))
 
1198
            text_map[version_id] = text
 
1199
        return text_map, final_content
 
1200
 
 
1201
    def iter_lines_added_or_present_in_versions(self, version_ids=None, 
 
1202
                                                pb=None):
 
1203
        """See VersionedFile.iter_lines_added_or_present_in_versions()."""
 
1204
        if version_ids is None:
 
1205
            version_ids = self.versions()
 
1206
        if pb is None:
 
1207
            pb = progress.DummyProgress()
 
1208
        # we don't care about inclusions, the caller cares.
 
1209
        # but we need to setup a list of records to visit.
 
1210
        # we need version_id, position, length
 
1211
        version_id_records = []
 
1212
        requested_versions = set(version_ids)
 
1213
        # filter for available versions
 
1214
        for version_id in requested_versions:
 
1215
            if not self.has_version(version_id):
 
1216
                raise RevisionNotPresent(version_id, self.filename)
 
1217
        # get a in-component-order queue:
 
1218
        for version_id in self.versions():
 
1219
            if version_id in requested_versions:
 
1220
                index_memo = self._index.get_position(version_id)
 
1221
                version_id_records.append((version_id, index_memo))
 
1222
 
 
1223
        total = len(version_id_records)
 
1224
        for version_idx, (version_id, data, sha_value) in \
 
1225
            enumerate(self._data.read_records_iter(version_id_records)):
 
1226
            pb.update('Walking content.', version_idx, total)
 
1227
            method = self._index.get_method(version_id)
 
1228
 
 
1229
            assert method in ('fulltext', 'line-delta')
 
1230
            if method == 'fulltext':
 
1231
                line_iterator = self.factory.get_fulltext_content(data)
 
1232
            else:
 
1233
                line_iterator = self.factory.get_linedelta_content(data)
 
1234
            # XXX: It might be more efficient to yield (version_id,
 
1235
            # line_iterator) in the future. However for now, this is a simpler
 
1236
            # change to integrate into the rest of the codebase. RBC 20071110
 
1237
            for line in line_iterator:
 
1238
                yield line, version_id
 
1239
 
 
1240
        pb.update('Walking content.', total, total)
 
1241
        
 
1242
    def iter_parents(self, version_ids):
 
1243
        """Iterate through the parents for many version ids.
 
1244
 
 
1245
        :param version_ids: An iterable yielding version_ids.
 
1246
        :return: An iterator that yields (version_id, parents). Requested 
 
1247
            version_ids not present in the versioned file are simply skipped.
 
1248
            The order is undefined, allowing for different optimisations in
 
1249
            the underlying implementation.
 
1250
        """
 
1251
        return self._index.iter_parents(version_ids)
 
1252
 
 
1253
    def num_versions(self):
 
1254
        """See VersionedFile.num_versions()."""
 
1255
        return self._index.num_versions()
 
1256
 
 
1257
    __len__ = num_versions
 
1258
 
 
1259
    def annotate_iter(self, version_id):
 
1260
        """See VersionedFile.annotate_iter."""
 
1261
        return self.factory.annotate_iter(self, version_id)
 
1262
 
 
1263
    def get_parent_map(self, version_ids):
 
1264
        """See VersionedFile.get_parent_map."""
 
1265
        return self._index.get_parent_map(version_ids)
 
1266
 
 
1267
    def get_ancestry(self, versions, topo_sorted=True):
 
1268
        """See VersionedFile.get_ancestry."""
 
1269
        if isinstance(versions, basestring):
 
1270
            versions = [versions]
 
1271
        if not versions:
 
1272
            return []
 
1273
        return self._index.get_ancestry(versions, topo_sorted)
 
1274
 
 
1275
    def get_ancestry_with_ghosts(self, versions):
 
1276
        """See VersionedFile.get_ancestry_with_ghosts."""
 
1277
        if isinstance(versions, basestring):
 
1278
            versions = [versions]
 
1279
        if not versions:
 
1280
            return []
 
1281
        return self._index.get_ancestry_with_ghosts(versions)
 
1282
 
 
1283
    def plan_merge(self, ver_a, ver_b):
 
1284
        """See VersionedFile.plan_merge."""
 
1285
        ancestors_b = set(self.get_ancestry(ver_b, topo_sorted=False))
 
1286
        ancestors_a = set(self.get_ancestry(ver_a, topo_sorted=False))
 
1287
        annotated_a = self.annotate(ver_a)
 
1288
        annotated_b = self.annotate(ver_b)
 
1289
        return merge._plan_annotate_merge(annotated_a, annotated_b,
 
1290
                                          ancestors_a, ancestors_b)
 
1291
 
 
1292
 
 
1293
class _KnitComponentFile(object):
 
1294
    """One of the files used to implement a knit database"""
 
1295
 
 
1296
    def __init__(self, transport, filename, mode, file_mode=None,
 
1297
                 create_parent_dir=False, dir_mode=None):
 
1298
        self._transport = transport
 
1299
        self._filename = filename
 
1300
        self._mode = mode
 
1301
        self._file_mode = file_mode
 
1302
        self._dir_mode = dir_mode
 
1303
        self._create_parent_dir = create_parent_dir
 
1304
        self._need_to_create = False
 
1305
 
 
1306
    def _full_path(self):
 
1307
        """Return the full path to this file."""
 
1308
        return self._transport.base + self._filename
 
1309
 
 
1310
    def check_header(self, fp):
 
1311
        line = fp.readline()
 
1312
        if line == '':
 
1313
            # An empty file can actually be treated as though the file doesn't
 
1314
            # exist yet.
 
1315
            raise errors.NoSuchFile(self._full_path())
 
1316
        if line != self.HEADER:
 
1317
            raise KnitHeaderError(badline=line,
 
1318
                              filename=self._transport.abspath(self._filename))
 
1319
 
 
1320
    def __repr__(self):
 
1321
        return '%s(%s)' % (self.__class__.__name__, self._filename)
 
1322
 
 
1323
 
 
1324
class _KnitIndex(_KnitComponentFile):
 
1325
    """Manages knit index file.
 
1326
 
 
1327
    The index is already kept in memory and read on startup, to enable
 
1328
    fast lookups of revision information.  The cursor of the index
 
1329
    file is always pointing to the end, making it easy to append
 
1330
    entries.
 
1331
 
 
1332
    _cache is a cache for fast mapping from version id to a Index
 
1333
    object.
 
1334
 
 
1335
    _history is a cache for fast mapping from indexes to version ids.
 
1336
 
 
1337
    The index data format is dictionary compressed when it comes to
 
1338
    parent references; a index entry may only have parents that with a
 
1339
    lover index number.  As a result, the index is topological sorted.
 
1340
 
 
1341
    Duplicate entries may be written to the index for a single version id
 
1342
    if this is done then the latter one completely replaces the former:
 
1343
    this allows updates to correct version and parent information. 
 
1344
    Note that the two entries may share the delta, and that successive
 
1345
    annotations and references MUST point to the first entry.
 
1346
 
 
1347
    The index file on disc contains a header, followed by one line per knit
 
1348
    record. The same revision can be present in an index file more than once.
 
1349
    The first occurrence gets assigned a sequence number starting from 0. 
 
1350
    
 
1351
    The format of a single line is
 
1352
    REVISION_ID FLAGS BYTE_OFFSET LENGTH( PARENT_ID|PARENT_SEQUENCE_ID)* :\n
 
1353
    REVISION_ID is a utf8-encoded revision id
 
1354
    FLAGS is a comma separated list of flags about the record. Values include 
 
1355
        no-eol, line-delta, fulltext.
 
1356
    BYTE_OFFSET is the ascii representation of the byte offset in the data file
 
1357
        that the the compressed data starts at.
 
1358
    LENGTH is the ascii representation of the length of the data file.
 
1359
    PARENT_ID a utf-8 revision id prefixed by a '.' that is a parent of
 
1360
        REVISION_ID.
 
1361
    PARENT_SEQUENCE_ID the ascii representation of the sequence number of a
 
1362
        revision id already in the knit that is a parent of REVISION_ID.
 
1363
    The ' :' marker is the end of record marker.
 
1364
    
 
1365
    partial writes:
 
1366
    when a write is interrupted to the index file, it will result in a line
 
1367
    that does not end in ' :'. If the ' :' is not present at the end of a line,
 
1368
    or at the end of the file, then the record that is missing it will be
 
1369
    ignored by the parser.
 
1370
 
 
1371
    When writing new records to the index file, the data is preceded by '\n'
 
1372
    to ensure that records always start on new lines even if the last write was
 
1373
    interrupted. As a result its normal for the last line in the index to be
 
1374
    missing a trailing newline. One can be added with no harmful effects.
 
1375
    """
 
1376
 
 
1377
    HEADER = "# bzr knit index 8\n"
 
1378
 
 
1379
    # speed of knit parsing went from 280 ms to 280 ms with slots addition.
 
1380
    # __slots__ = ['_cache', '_history', '_transport', '_filename']
 
1381
 
 
1382
    def _cache_version(self, version_id, options, pos, size, parents):
 
1383
        """Cache a version record in the history array and index cache.
 
1384
 
 
1385
        This is inlined into _load_data for performance. KEEP IN SYNC.
 
1386
        (It saves 60ms, 25% of the __init__ overhead on local 4000 record
 
1387
         indexes).
 
1388
        """
 
1389
        # only want the _history index to reference the 1st index entry
 
1390
        # for version_id
 
1391
        if version_id not in self._cache:
 
1392
            index = len(self._history)
 
1393
            self._history.append(version_id)
 
1394
        else:
 
1395
            index = self._cache[version_id][5]
 
1396
        self._cache[version_id] = (version_id,
 
1397
                                   options,
 
1398
                                   pos,
 
1399
                                   size,
 
1400
                                   parents,
 
1401
                                   index)
 
1402
 
 
1403
    def __init__(self, transport, filename, mode, create=False, file_mode=None,
 
1404
                 create_parent_dir=False, delay_create=False, dir_mode=None):
 
1405
        _KnitComponentFile.__init__(self, transport, filename, mode,
 
1406
                                    file_mode=file_mode,
 
1407
                                    create_parent_dir=create_parent_dir,
 
1408
                                    dir_mode=dir_mode)
 
1409
        self._cache = {}
 
1410
        # position in _history is the 'official' index for a revision
 
1411
        # but the values may have come from a newer entry.
 
1412
        # so - wc -l of a knit index is != the number of unique names
 
1413
        # in the knit.
 
1414
        self._history = []
 
1415
        try:
 
1416
            fp = self._transport.get(self._filename)
 
1417
            try:
 
1418
                # _load_data may raise NoSuchFile if the target knit is
 
1419
                # completely empty.
 
1420
                _load_data(self, fp)
 
1421
            finally:
 
1422
                fp.close()
 
1423
        except NoSuchFile:
 
1424
            if mode != 'w' or not create:
 
1425
                raise
 
1426
            elif delay_create:
 
1427
                self._need_to_create = True
 
1428
            else:
 
1429
                self._transport.put_bytes_non_atomic(
 
1430
                    self._filename, self.HEADER, mode=self._file_mode)
 
1431
 
 
1432
    def get_ancestry(self, versions, topo_sorted=True):
 
1433
        """See VersionedFile.get_ancestry."""
 
1434
        # get a graph of all the mentioned versions:
 
1435
        graph = {}
 
1436
        pending = set(versions)
 
1437
        cache = self._cache
 
1438
        while pending:
 
1439
            version = pending.pop()
 
1440
            # trim ghosts
 
1441
            try:
 
1442
                parents = [p for p in cache[version][4] if p in cache]
 
1443
            except KeyError:
 
1444
                raise RevisionNotPresent(version, self._filename)
 
1445
            # if not completed and not a ghost
 
1446
            pending.update([p for p in parents if p not in graph])
 
1447
            graph[version] = parents
 
1448
        if not topo_sorted:
 
1449
            return graph.keys()
 
1450
        return topo_sort(graph.items())
 
1451
 
 
1452
    def get_ancestry_with_ghosts(self, versions):
 
1453
        """See VersionedFile.get_ancestry_with_ghosts."""
 
1454
        # get a graph of all the mentioned versions:
 
1455
        self.check_versions_present(versions)
 
1456
        cache = self._cache
 
1457
        graph = {}
 
1458
        pending = set(versions)
 
1459
        while pending:
 
1460
            version = pending.pop()
 
1461
            try:
 
1462
                parents = cache[version][4]
 
1463
            except KeyError:
 
1464
                # ghost, fake it
 
1465
                graph[version] = []
 
1466
            else:
 
1467
                # if not completed
 
1468
                pending.update([p for p in parents if p not in graph])
 
1469
                graph[version] = parents
 
1470
        return topo_sort(graph.items())
 
1471
 
 
1472
    def get_build_details(self, version_ids):
 
1473
        """Get the method, index_memo and compression parent for version_ids.
 
1474
 
 
1475
        Ghosts are omitted from the result.
 
1476
 
 
1477
        :param version_ids: An iterable of version_ids.
 
1478
        :return: A dict of version_id:(index_memo, compression_parent,
 
1479
                                       parents, record_details).
 
1480
            index_memo
 
1481
                opaque structure to pass to read_records to extract the raw
 
1482
                data
 
1483
            compression_parent
 
1484
                Content that this record is built upon, may be None
 
1485
            parents
 
1486
                Logical parents of this node
 
1487
            record_details
 
1488
                extra information about the content which needs to be passed to
 
1489
                Factory.parse_record
 
1490
        """
 
1491
        result = {}
 
1492
        for version_id in version_ids:
 
1493
            if version_id not in self._cache:
 
1494
                # ghosts are omitted
 
1495
                continue
 
1496
            method = self.get_method(version_id)
 
1497
            parents = self.get_parents_with_ghosts(version_id)
 
1498
            if method == 'fulltext':
 
1499
                compression_parent = None
 
1500
            else:
 
1501
                compression_parent = parents[0]
 
1502
            noeol = 'no-eol' in self.get_options(version_id)
 
1503
            index_memo = self.get_position(version_id)
 
1504
            result[version_id] = (index_memo, compression_parent,
 
1505
                                  parents, (method, noeol))
 
1506
        return result
 
1507
 
 
1508
    def iter_parents(self, version_ids):
 
1509
        """Iterate through the parents for many version ids.
 
1510
 
 
1511
        :param version_ids: An iterable yielding version_ids.
 
1512
        :return: An iterator that yields (version_id, parents). Requested 
 
1513
            version_ids not present in the versioned file are simply skipped.
 
1514
            The order is undefined, allowing for different optimisations in
 
1515
            the underlying implementation.
 
1516
        """
 
1517
        parent_map = self.get_parent_map(version_ids)
 
1518
        parent_map_set = set(parent_map)
 
1519
        unknown_existence = set()
 
1520
        for parents in parent_map.itervalues():
 
1521
            unknown_existence.update(parents)
 
1522
        unknown_existence.difference_update(parent_map_set)
 
1523
        present_parents = set(self.get_parent_map(unknown_existence))
 
1524
        present_parents.update(parent_map_set)
 
1525
        for version_id, parents in parent_map.iteritems():
 
1526
            parents = tuple(parent for parent in parents
 
1527
                if parent in present_parents)
 
1528
            yield version_id, parents
 
1529
 
 
1530
    def num_versions(self):
 
1531
        return len(self._history)
 
1532
 
 
1533
    __len__ = num_versions
 
1534
 
 
1535
    def get_versions(self):
 
1536
        """Get all the versions in the file. not topologically sorted."""
 
1537
        return self._history
 
1538
 
 
1539
    def _version_list_to_index(self, versions):
 
1540
        result_list = []
 
1541
        cache = self._cache
 
1542
        for version in versions:
 
1543
            if version in cache:
 
1544
                # -- inlined lookup() --
 
1545
                result_list.append(str(cache[version][5]))
 
1546
                # -- end lookup () --
 
1547
            else:
 
1548
                result_list.append('.' + version)
 
1549
        return ' '.join(result_list)
 
1550
 
 
1551
    def add_version(self, version_id, options, index_memo, parents):
 
1552
        """Add a version record to the index."""
 
1553
        self.add_versions(((version_id, options, index_memo, parents),))
 
1554
 
 
1555
    def add_versions(self, versions, random_id=False):
 
1556
        """Add multiple versions to the index.
 
1557
        
 
1558
        :param versions: a list of tuples:
 
1559
                         (version_id, options, pos, size, parents).
 
1560
        :param random_id: If True the ids being added were randomly generated
 
1561
            and no check for existence will be performed.
 
1562
        """
 
1563
        lines = []
 
1564
        orig_history = self._history[:]
 
1565
        orig_cache = self._cache.copy()
 
1566
 
 
1567
        try:
 
1568
            for version_id, options, (index, pos, size), parents in versions:
 
1569
                line = "\n%s %s %s %s %s :" % (version_id,
 
1570
                                               ','.join(options),
 
1571
                                               pos,
 
1572
                                               size,
 
1573
                                               self._version_list_to_index(parents))
 
1574
                assert isinstance(line, str), \
 
1575
                    'content must be utf-8 encoded: %r' % (line,)
 
1576
                lines.append(line)
 
1577
                self._cache_version(version_id, options, pos, size, tuple(parents))
 
1578
            if not self._need_to_create:
 
1579
                self._transport.append_bytes(self._filename, ''.join(lines))
 
1580
            else:
 
1581
                sio = StringIO()
 
1582
                sio.write(self.HEADER)
 
1583
                sio.writelines(lines)
 
1584
                sio.seek(0)
 
1585
                self._transport.put_file_non_atomic(self._filename, sio,
 
1586
                                    create_parent_dir=self._create_parent_dir,
 
1587
                                    mode=self._file_mode,
 
1588
                                    dir_mode=self._dir_mode)
 
1589
                self._need_to_create = False
 
1590
        except:
 
1591
            # If any problems happen, restore the original values and re-raise
 
1592
            self._history = orig_history
 
1593
            self._cache = orig_cache
 
1594
            raise
 
1595
 
 
1596
    def has_version(self, version_id):
 
1597
        """True if the version is in the index."""
 
1598
        return version_id in self._cache
 
1599
 
 
1600
    def get_position(self, version_id):
 
1601
        """Return details needed to access the version.
 
1602
        
 
1603
        .kndx indices do not support split-out data, so return None for the 
 
1604
        index field.
 
1605
 
 
1606
        :return: a tuple (None, data position, size) to hand to the access
 
1607
            logic to get the record.
 
1608
        """
 
1609
        entry = self._cache[version_id]
 
1610
        return None, entry[2], entry[3]
 
1611
 
 
1612
    def get_method(self, version_id):
 
1613
        """Return compression method of specified version."""
 
1614
        try:
 
1615
            options = self._cache[version_id][1]
 
1616
        except KeyError:
 
1617
            raise RevisionNotPresent(version_id, self._filename)
 
1618
        if 'fulltext' in options:
 
1619
            return 'fulltext'
 
1620
        else:
 
1621
            if 'line-delta' not in options:
 
1622
                raise errors.KnitIndexUnknownMethod(self._full_path(), options)
 
1623
            return 'line-delta'
 
1624
 
 
1625
    def get_options(self, version_id):
 
1626
        """Return a list representing options.
 
1627
 
 
1628
        e.g. ['foo', 'bar']
 
1629
        """
 
1630
        return self._cache[version_id][1]
 
1631
 
 
1632
    def get_parent_map(self, version_ids):
 
1633
        """Passed through to by KnitVersionedFile.get_parent_map."""
 
1634
        result = {}
 
1635
        for version_id in version_ids:
 
1636
            try:
 
1637
                result[version_id] = tuple(self._cache[version_id][4])
 
1638
            except KeyError:
 
1639
                pass
 
1640
        return result
 
1641
 
 
1642
    def get_parents_with_ghosts(self, version_id):
 
1643
        """Return parents of specified version with ghosts."""
 
1644
        try:
 
1645
            return self.get_parent_map([version_id])[version_id]
 
1646
        except KeyError:
 
1647
            raise RevisionNotPresent(version_id, self)
 
1648
 
 
1649
    def check_versions_present(self, version_ids):
 
1650
        """Check that all specified versions are present."""
 
1651
        cache = self._cache
 
1652
        for version_id in version_ids:
 
1653
            if version_id not in cache:
 
1654
                raise RevisionNotPresent(version_id, self._filename)
 
1655
 
 
1656
 
 
1657
class KnitGraphIndex(object):
 
1658
    """A knit index that builds on GraphIndex."""
 
1659
 
 
1660
    def __init__(self, graph_index, deltas=False, parents=True, add_callback=None):
 
1661
        """Construct a KnitGraphIndex on a graph_index.
 
1662
 
 
1663
        :param graph_index: An implementation of bzrlib.index.GraphIndex.
 
1664
        :param deltas: Allow delta-compressed records.
 
1665
        :param add_callback: If not None, allow additions to the index and call
 
1666
            this callback with a list of added GraphIndex nodes:
 
1667
            [(node, value, node_refs), ...]
 
1668
        :param parents: If True, record knits parents, if not do not record 
 
1669
            parents.
 
1670
        """
 
1671
        self._graph_index = graph_index
 
1672
        self._deltas = deltas
 
1673
        self._add_callback = add_callback
 
1674
        self._parents = parents
 
1675
        if deltas and not parents:
 
1676
            raise KnitCorrupt(self, "Cannot do delta compression without "
 
1677
                "parent tracking.")
 
1678
 
 
1679
    def _get_entries(self, keys, check_present=False):
 
1680
        """Get the entries for keys.
 
1681
        
 
1682
        :param keys: An iterable of index keys, - 1-tuples.
 
1683
        """
 
1684
        keys = set(keys)
 
1685
        found_keys = set()
 
1686
        if self._parents:
 
1687
            for node in self._graph_index.iter_entries(keys):
 
1688
                yield node
 
1689
                found_keys.add(node[1])
 
1690
        else:
 
1691
            # adapt parentless index to the rest of the code.
 
1692
            for node in self._graph_index.iter_entries(keys):
 
1693
                yield node[0], node[1], node[2], ()
 
1694
                found_keys.add(node[1])
 
1695
        if check_present:
 
1696
            missing_keys = keys.difference(found_keys)
 
1697
            if missing_keys:
 
1698
                raise RevisionNotPresent(missing_keys.pop(), self)
 
1699
 
 
1700
    def _present_keys(self, version_ids):
 
1701
        return set([
 
1702
            node[1] for node in self._get_entries(version_ids)])
 
1703
 
 
1704
    def _parentless_ancestry(self, versions):
 
1705
        """Honour the get_ancestry API for parentless knit indices."""
 
1706
        wanted_keys = self._version_ids_to_keys(versions)
 
1707
        present_keys = self._present_keys(wanted_keys)
 
1708
        missing = set(wanted_keys).difference(present_keys)
 
1709
        if missing:
 
1710
            raise RevisionNotPresent(missing.pop(), self)
 
1711
        return list(self._keys_to_version_ids(present_keys))
 
1712
 
 
1713
    def get_ancestry(self, versions, topo_sorted=True):
 
1714
        """See VersionedFile.get_ancestry."""
 
1715
        if not self._parents:
 
1716
            return self._parentless_ancestry(versions)
 
1717
        # XXX: This will do len(history) index calls - perhaps
 
1718
        # it should be altered to be a index core feature?
 
1719
        # get a graph of all the mentioned versions:
 
1720
        graph = {}
 
1721
        ghosts = set()
 
1722
        versions = self._version_ids_to_keys(versions)
 
1723
        pending = set(versions)
 
1724
        while pending:
 
1725
            # get all pending nodes
 
1726
            this_iteration = pending
 
1727
            new_nodes = self._get_entries(this_iteration)
 
1728
            found = set()
 
1729
            pending = set()
 
1730
            for (index, key, value, node_refs) in new_nodes:
 
1731
                # dont ask for ghosties - otherwise
 
1732
                # we we can end up looping with pending
 
1733
                # being entirely ghosted.
 
1734
                graph[key] = [parent for parent in node_refs[0]
 
1735
                    if parent not in ghosts]
 
1736
                # queue parents
 
1737
                for parent in graph[key]:
 
1738
                    # dont examine known nodes again
 
1739
                    if parent in graph:
 
1740
                        continue
 
1741
                    pending.add(parent)
 
1742
                found.add(key)
 
1743
            ghosts.update(this_iteration.difference(found))
 
1744
        if versions.difference(graph):
 
1745
            raise RevisionNotPresent(versions.difference(graph).pop(), self)
 
1746
        if topo_sorted:
 
1747
            result_keys = topo_sort(graph.items())
 
1748
        else:
 
1749
            result_keys = graph.iterkeys()
 
1750
        return [key[0] for key in result_keys]
 
1751
 
 
1752
    def get_ancestry_with_ghosts(self, versions):
 
1753
        """See VersionedFile.get_ancestry."""
 
1754
        if not self._parents:
 
1755
            return self._parentless_ancestry(versions)
 
1756
        # XXX: This will do len(history) index calls - perhaps
 
1757
        # it should be altered to be a index core feature?
 
1758
        # get a graph of all the mentioned versions:
 
1759
        graph = {}
 
1760
        versions = self._version_ids_to_keys(versions)
 
1761
        pending = set(versions)
 
1762
        while pending:
 
1763
            # get all pending nodes
 
1764
            this_iteration = pending
 
1765
            new_nodes = self._get_entries(this_iteration)
 
1766
            pending = set()
 
1767
            for (index, key, value, node_refs) in new_nodes:
 
1768
                graph[key] = node_refs[0]
 
1769
                # queue parents 
 
1770
                for parent in graph[key]:
 
1771
                    # dont examine known nodes again
 
1772
                    if parent in graph:
 
1773
                        continue
 
1774
                    pending.add(parent)
 
1775
            missing_versions = this_iteration.difference(graph)
 
1776
            missing_needed = versions.intersection(missing_versions)
 
1777
            if missing_needed:
 
1778
                raise RevisionNotPresent(missing_needed.pop(), self)
 
1779
            for missing_version in missing_versions:
 
1780
                # add a key, no parents
 
1781
                graph[missing_version] = []
 
1782
                pending.discard(missing_version) # don't look for it
 
1783
        result_keys = topo_sort(graph.items())
 
1784
        return [key[0] for key in result_keys]
 
1785
 
 
1786
    def get_build_details(self, version_ids):
 
1787
        """Get the method, index_memo and compression parent for version_ids.
 
1788
 
 
1789
        Ghosts are omitted from the result.
 
1790
 
 
1791
        :param version_ids: An iterable of version_ids.
 
1792
        :return: A dict of version_id:(index_memo, compression_parent,
 
1793
                                       parents, record_details).
 
1794
            index_memo
 
1795
                opaque structure to pass to read_records to extract the raw
 
1796
                data
 
1797
            compression_parent
 
1798
                Content that this record is built upon, may be None
 
1799
            parents
 
1800
                Logical parents of this node
 
1801
            record_details
 
1802
                extra information about the content which needs to be passed to
 
1803
                Factory.parse_record
 
1804
        """
 
1805
        result = {}
 
1806
        entries = self._get_entries(self._version_ids_to_keys(version_ids), True)
 
1807
        for entry in entries:
 
1808
            version_id = self._keys_to_version_ids((entry[1],))[0]
 
1809
            if not self._parents:
 
1810
                parents = ()
 
1811
            else:
 
1812
                parents = self._keys_to_version_ids(entry[3][0])
 
1813
            if not self._deltas:
 
1814
                compression_parent = None
 
1815
            else:
 
1816
                compression_parent_key = self._compression_parent(entry)
 
1817
                if compression_parent_key:
 
1818
                    compression_parent = self._keys_to_version_ids(
 
1819
                    (compression_parent_key,))[0]
 
1820
                else:
 
1821
                    compression_parent = None
 
1822
            noeol = (entry[2][0] == 'N')
 
1823
            if compression_parent:
 
1824
                method = 'line-delta'
 
1825
            else:
 
1826
                method = 'fulltext'
 
1827
            result[version_id] = (self._node_to_position(entry),
 
1828
                                  compression_parent, parents,
 
1829
                                  (method, noeol))
 
1830
        return result
 
1831
 
 
1832
    def _compression_parent(self, an_entry):
 
1833
        # return the key that an_entry is compressed against, or None
 
1834
        # Grab the second parent list (as deltas implies parents currently)
 
1835
        compression_parents = an_entry[3][1]
 
1836
        if not compression_parents:
 
1837
            return None
 
1838
        assert len(compression_parents) == 1
 
1839
        return compression_parents[0]
 
1840
 
 
1841
    def _get_method(self, node):
 
1842
        if not self._deltas:
 
1843
            return 'fulltext'
 
1844
        if self._compression_parent(node):
 
1845
            return 'line-delta'
 
1846
        else:
 
1847
            return 'fulltext'
 
1848
 
 
1849
    def iter_parents(self, version_ids):
 
1850
        """Iterate through the parents for many version ids.
 
1851
 
 
1852
        :param version_ids: An iterable yielding version_ids.
 
1853
        :return: An iterator that yields (version_id, parents). Requested 
 
1854
            version_ids not present in the versioned file are simply skipped.
 
1855
            The order is undefined, allowing for different optimisations in
 
1856
            the underlying implementation.
 
1857
        """
 
1858
        if self._parents:
 
1859
            all_nodes = set(self._get_entries(self._version_ids_to_keys(version_ids)))
 
1860
            all_parents = set()
 
1861
            present_parents = set()
 
1862
            for node in all_nodes:
 
1863
                all_parents.update(node[3][0])
 
1864
                # any node we are querying must be present
 
1865
                present_parents.add(node[1])
 
1866
            unknown_parents = all_parents.difference(present_parents)
 
1867
            present_parents.update(self._present_keys(unknown_parents))
 
1868
            for node in all_nodes:
 
1869
                parents = []
 
1870
                for parent in node[3][0]:
 
1871
                    if parent in present_parents:
 
1872
                        parents.append(parent[0])
 
1873
                yield node[1][0], tuple(parents)
 
1874
        else:
 
1875
            for node in self._get_entries(self._version_ids_to_keys(version_ids)):
 
1876
                yield node[1][0], ()
 
1877
 
 
1878
    def num_versions(self):
 
1879
        return len(list(self._graph_index.iter_all_entries()))
 
1880
 
 
1881
    __len__ = num_versions
 
1882
 
 
1883
    def get_versions(self):
 
1884
        """Get all the versions in the file. not topologically sorted."""
 
1885
        return [node[1][0] for node in self._graph_index.iter_all_entries()]
 
1886
    
 
1887
    def has_version(self, version_id):
 
1888
        """True if the version is in the index."""
 
1889
        return len(self._present_keys(self._version_ids_to_keys([version_id]))) == 1
 
1890
 
 
1891
    def _keys_to_version_ids(self, keys):
 
1892
        return tuple(key[0] for key in keys)
 
1893
 
 
1894
    def get_position(self, version_id):
 
1895
        """Return details needed to access the version.
 
1896
        
 
1897
        :return: a tuple (index, data position, size) to hand to the access
 
1898
            logic to get the record.
 
1899
        """
 
1900
        node = self._get_node(version_id)
 
1901
        return self._node_to_position(node)
 
1902
 
 
1903
    def _node_to_position(self, node):
 
1904
        """Convert an index value to position details."""
 
1905
        bits = node[2][1:].split(' ')
 
1906
        return node[0], int(bits[0]), int(bits[1])
 
1907
 
 
1908
    def get_method(self, version_id):
 
1909
        """Return compression method of specified version."""
 
1910
        return self._get_method(self._get_node(version_id))
 
1911
 
 
1912
    def _get_node(self, version_id):
 
1913
        try:
 
1914
            return list(self._get_entries(self._version_ids_to_keys([version_id])))[0]
 
1915
        except IndexError:
 
1916
            raise RevisionNotPresent(version_id, self)
 
1917
 
 
1918
    def get_options(self, version_id):
 
1919
        """Return a list representing options.
 
1920
 
 
1921
        e.g. ['foo', 'bar']
 
1922
        """
 
1923
        node = self._get_node(version_id)
 
1924
        options = [self._get_method(node)]
 
1925
        if node[2][0] == 'N':
 
1926
            options.append('no-eol')
 
1927
        return options
 
1928
 
 
1929
    def get_parent_map(self, version_ids):
 
1930
        """Passed through to by KnitVersionedFile.get_parent_map."""
 
1931
        nodes = self._get_entries(self._version_ids_to_keys(version_ids))
 
1932
        result = {}
 
1933
        if self._parents:
 
1934
            for node in nodes:
 
1935
                result[node[1][0]] = self._keys_to_version_ids(node[3][0])
 
1936
        else:
 
1937
            for node in nodes:
 
1938
                result[node[1][0]] = ()
 
1939
        return result
 
1940
 
 
1941
    def get_parents_with_ghosts(self, version_id):
 
1942
        """Return parents of specified version with ghosts."""
 
1943
        try:
 
1944
            return self.get_parent_map([version_id])[version_id]
 
1945
        except KeyError:
 
1946
            raise RevisionNotPresent(version_id, self)
 
1947
 
 
1948
    def check_versions_present(self, version_ids):
 
1949
        """Check that all specified versions are present."""
 
1950
        keys = self._version_ids_to_keys(version_ids)
 
1951
        present = self._present_keys(keys)
 
1952
        missing = keys.difference(present)
 
1953
        if missing:
 
1954
            raise RevisionNotPresent(missing.pop(), self)
 
1955
 
 
1956
    def add_version(self, version_id, options, access_memo, parents):
 
1957
        """Add a version record to the index."""
 
1958
        return self.add_versions(((version_id, options, access_memo, parents),))
 
1959
 
 
1960
    def add_versions(self, versions, random_id=False):
 
1961
        """Add multiple versions to the index.
 
1962
        
 
1963
        This function does not insert data into the Immutable GraphIndex
 
1964
        backing the KnitGraphIndex, instead it prepares data for insertion by
 
1965
        the caller and checks that it is safe to insert then calls
 
1966
        self._add_callback with the prepared GraphIndex nodes.
 
1967
 
 
1968
        :param versions: a list of tuples:
 
1969
                         (version_id, options, pos, size, parents).
 
1970
        :param random_id: If True the ids being added were randomly generated
 
1971
            and no check for existence will be performed.
 
1972
        """
 
1973
        if not self._add_callback:
 
1974
            raise errors.ReadOnlyError(self)
 
1975
        # we hope there are no repositories with inconsistent parentage
 
1976
        # anymore.
 
1977
        # check for dups
 
1978
 
 
1979
        keys = {}
 
1980
        for (version_id, options, access_memo, parents) in versions:
 
1981
            index, pos, size = access_memo
 
1982
            key = (version_id, )
 
1983
            parents = tuple((parent, ) for parent in parents)
 
1984
            if 'no-eol' in options:
 
1985
                value = 'N'
 
1986
            else:
 
1987
                value = ' '
 
1988
            value += "%d %d" % (pos, size)
 
1989
            if not self._deltas:
 
1990
                if 'line-delta' in options:
 
1991
                    raise KnitCorrupt(self, "attempt to add line-delta in non-delta knit")
 
1992
            if self._parents:
 
1993
                if self._deltas:
 
1994
                    if 'line-delta' in options:
 
1995
                        node_refs = (parents, (parents[0],))
 
1996
                    else:
 
1997
                        node_refs = (parents, ())
 
1998
                else:
 
1999
                    node_refs = (parents, )
 
2000
            else:
 
2001
                if parents:
 
2002
                    raise KnitCorrupt(self, "attempt to add node with parents "
 
2003
                        "in parentless index.")
 
2004
                node_refs = ()
 
2005
            keys[key] = (value, node_refs)
 
2006
        if not random_id:
 
2007
            present_nodes = self._get_entries(keys)
 
2008
            for (index, key, value, node_refs) in present_nodes:
 
2009
                if (value, node_refs) != keys[key]:
 
2010
                    raise KnitCorrupt(self, "inconsistent details in add_versions"
 
2011
                        ": %s %s" % ((value, node_refs), keys[key]))
 
2012
                del keys[key]
 
2013
        result = []
 
2014
        if self._parents:
 
2015
            for key, (value, node_refs) in keys.iteritems():
 
2016
                result.append((key, value, node_refs))
 
2017
        else:
 
2018
            for key, (value, node_refs) in keys.iteritems():
 
2019
                result.append((key, value))
 
2020
        self._add_callback(result)
 
2021
        
 
2022
    def _version_ids_to_keys(self, version_ids):
 
2023
        return set((version_id, ) for version_id in version_ids)
 
2024
 
 
2025
 
 
2026
class _KnitAccess(object):
 
2027
    """Access to knit records in a .knit file."""
 
2028
 
 
2029
    def __init__(self, transport, filename, _file_mode, _dir_mode,
 
2030
        _need_to_create, _create_parent_dir):
 
2031
        """Create a _KnitAccess for accessing and inserting data.
 
2032
 
 
2033
        :param transport: The transport the .knit is located on.
 
2034
        :param filename: The filename of the .knit.
 
2035
        """
 
2036
        self._transport = transport
 
2037
        self._filename = filename
 
2038
        self._file_mode = _file_mode
 
2039
        self._dir_mode = _dir_mode
 
2040
        self._need_to_create = _need_to_create
 
2041
        self._create_parent_dir = _create_parent_dir
 
2042
 
 
2043
    def add_raw_records(self, sizes, raw_data):
 
2044
        """Add raw knit bytes to a storage area.
 
2045
 
 
2046
        The data is spooled to whereever the access method is storing data.
 
2047
 
 
2048
        :param sizes: An iterable containing the size of each raw data segment.
 
2049
        :param raw_data: A bytestring containing the data.
 
2050
        :return: A list of memos to retrieve the record later. Each memo is a
 
2051
            tuple - (index, pos, length), where the index field is always None
 
2052
            for the .knit access method.
 
2053
        """
 
2054
        assert type(raw_data) == str, \
 
2055
            'data must be plain bytes was %s' % type(raw_data)
 
2056
        if not self._need_to_create:
 
2057
            base = self._transport.append_bytes(self._filename, raw_data)
 
2058
        else:
 
2059
            self._transport.put_bytes_non_atomic(self._filename, raw_data,
 
2060
                                   create_parent_dir=self._create_parent_dir,
 
2061
                                   mode=self._file_mode,
 
2062
                                   dir_mode=self._dir_mode)
 
2063
            self._need_to_create = False
 
2064
            base = 0
 
2065
        result = []
 
2066
        for size in sizes:
 
2067
            result.append((None, base, size))
 
2068
            base += size
 
2069
        return result
 
2070
 
 
2071
    def create(self):
 
2072
        """IFF this data access has its own storage area, initialise it.
 
2073
 
 
2074
        :return: None.
 
2075
        """
 
2076
        self._transport.put_bytes_non_atomic(self._filename, '',
 
2077
                                             mode=self._file_mode)
 
2078
 
 
2079
    def open_file(self):
 
2080
        """IFF this data access can be represented as a single file, open it.
 
2081
 
 
2082
        For knits that are not mapped to a single file on disk this will
 
2083
        always return None.
 
2084
 
 
2085
        :return: None or a file handle.
 
2086
        """
 
2087
        try:
 
2088
            return self._transport.get(self._filename)
 
2089
        except NoSuchFile:
 
2090
            pass
 
2091
        return None
 
2092
 
 
2093
    def get_raw_records(self, memos_for_retrieval):
 
2094
        """Get the raw bytes for a records.
 
2095
 
 
2096
        :param memos_for_retrieval: An iterable containing the (index, pos, 
 
2097
            length) memo for retrieving the bytes. The .knit method ignores
 
2098
            the index as there is always only a single file.
 
2099
        :return: An iterator over the bytes of the records.
 
2100
        """
 
2101
        read_vector = [(pos, size) for (index, pos, size) in memos_for_retrieval]
 
2102
        for pos, data in self._transport.readv(self._filename, read_vector):
 
2103
            yield data
 
2104
 
 
2105
 
 
2106
class _PackAccess(object):
 
2107
    """Access to knit records via a collection of packs."""
 
2108
 
 
2109
    def __init__(self, index_to_packs, writer=None):
 
2110
        """Create a _PackAccess object.
 
2111
 
 
2112
        :param index_to_packs: A dict mapping index objects to the transport
 
2113
            and file names for obtaining data.
 
2114
        :param writer: A tuple (pack.ContainerWriter, write_index) which
 
2115
            contains the pack to write, and the index that reads from it will
 
2116
            be associated with.
 
2117
        """
 
2118
        if writer:
 
2119
            self.container_writer = writer[0]
 
2120
            self.write_index = writer[1]
 
2121
        else:
 
2122
            self.container_writer = None
 
2123
            self.write_index = None
 
2124
        self.indices = index_to_packs
 
2125
 
 
2126
    def add_raw_records(self, sizes, raw_data):
 
2127
        """Add raw knit bytes to a storage area.
 
2128
 
 
2129
        The data is spooled to the container writer in one bytes-record per
 
2130
        raw data item.
 
2131
 
 
2132
        :param sizes: An iterable containing the size of each raw data segment.
 
2133
        :param raw_data: A bytestring containing the data.
 
2134
        :return: A list of memos to retrieve the record later. Each memo is a
 
2135
            tuple - (index, pos, length), where the index field is the 
 
2136
            write_index object supplied to the PackAccess object.
 
2137
        """
 
2138
        assert type(raw_data) == str, \
 
2139
            'data must be plain bytes was %s' % type(raw_data)
 
2140
        result = []
 
2141
        offset = 0
 
2142
        for size in sizes:
 
2143
            p_offset, p_length = self.container_writer.add_bytes_record(
 
2144
                raw_data[offset:offset+size], [])
 
2145
            offset += size
 
2146
            result.append((self.write_index, p_offset, p_length))
 
2147
        return result
 
2148
 
 
2149
    def create(self):
 
2150
        """Pack based knits do not get individually created."""
 
2151
 
 
2152
    def get_raw_records(self, memos_for_retrieval):
 
2153
        """Get the raw bytes for a records.
 
2154
 
 
2155
        :param memos_for_retrieval: An iterable containing the (index, pos, 
 
2156
            length) memo for retrieving the bytes. The Pack access method
 
2157
            looks up the pack to use for a given record in its index_to_pack
 
2158
            map.
 
2159
        :return: An iterator over the bytes of the records.
 
2160
        """
 
2161
        # first pass, group into same-index requests
 
2162
        request_lists = []
 
2163
        current_index = None
 
2164
        for (index, offset, length) in memos_for_retrieval:
 
2165
            if current_index == index:
 
2166
                current_list.append((offset, length))
 
2167
            else:
 
2168
                if current_index is not None:
 
2169
                    request_lists.append((current_index, current_list))
 
2170
                current_index = index
 
2171
                current_list = [(offset, length)]
 
2172
        # handle the last entry
 
2173
        if current_index is not None:
 
2174
            request_lists.append((current_index, current_list))
 
2175
        for index, offsets in request_lists:
 
2176
            transport, path = self.indices[index]
 
2177
            reader = pack.make_readv_reader(transport, path, offsets)
 
2178
            for names, read_func in reader.iter_records():
 
2179
                yield read_func(None)
 
2180
 
 
2181
    def open_file(self):
 
2182
        """Pack based knits have no single file."""
 
2183
        return None
 
2184
 
 
2185
    def set_writer(self, writer, index, (transport, packname)):
 
2186
        """Set a writer to use for adding data."""
 
2187
        if index is not None:
 
2188
            self.indices[index] = (transport, packname)
 
2189
        self.container_writer = writer
 
2190
        self.write_index = index
 
2191
 
 
2192
 
 
2193
class _StreamAccess(object):
 
2194
    """A Knit Access object that provides data from a datastream.
 
2195
    
 
2196
    It also provides a fallback to present as unannotated data, annotated data
 
2197
    from a *backing* access object.
 
2198
 
 
2199
    This is triggered by a index_memo which is pointing to a different index
 
2200
    than this was constructed with, and is used to allow extracting full
 
2201
    unannotated texts for insertion into annotated knits.
 
2202
    """
 
2203
 
 
2204
    def __init__(self, reader_callable, stream_index, backing_knit,
 
2205
        orig_factory):
 
2206
        """Create a _StreamAccess object.
 
2207
 
 
2208
        :param reader_callable: The reader_callable from the datastream.
 
2209
            This is called to buffer all the data immediately, for 
 
2210
            random access.
 
2211
        :param stream_index: The index the data stream this provides access to
 
2212
            which will be present in native index_memo's.
 
2213
        :param backing_knit: The knit object that will provide access to 
 
2214
            annotated texts which are not available in the stream, so as to
 
2215
            create unannotated texts.
 
2216
        :param orig_factory: The original content factory used to generate the
 
2217
            stream. This is used for checking whether the thunk code for
 
2218
            supporting _copy_texts will generate the correct form of data.
 
2219
        """
 
2220
        self.data = reader_callable(None)
 
2221
        self.stream_index = stream_index
 
2222
        self.backing_knit = backing_knit
 
2223
        self.orig_factory = orig_factory
 
2224
 
 
2225
    def get_raw_records(self, memos_for_retrieval):
 
2226
        """Get the raw bytes for a records.
 
2227
 
 
2228
        :param memos_for_retrieval: An iterable of memos from the
 
2229
            _StreamIndex object identifying bytes to read; for these classes
 
2230
            they are (from_backing_knit, index, start, end) and can point to
 
2231
            either the backing knit or streamed data.
 
2232
        :return: An iterator yielding a byte string for each record in 
 
2233
            memos_for_retrieval.
 
2234
        """
 
2235
        # use a generator for memory friendliness
 
2236
        for from_backing_knit, version_id, start, end in memos_for_retrieval:
 
2237
            if not from_backing_knit:
 
2238
                assert version_id is self.stream_index
 
2239
                yield self.data[start:end]
 
2240
                continue
 
2241
            # we have been asked to thunk. This thunking only occurs when
 
2242
            # we are obtaining plain texts from an annotated backing knit
 
2243
            # so that _copy_texts will work.
 
2244
            # We could improve performance here by scanning for where we need
 
2245
            # to do this and using get_line_list, then interleaving the output
 
2246
            # as desired. However, for now, this is sufficient.
 
2247
            if self.orig_factory.__class__ != KnitPlainFactory:
 
2248
                raise errors.KnitCorrupt(
 
2249
                    self, 'Bad thunk request %r cannot be backed by %r' %
 
2250
                        (version_id, self.orig_factory))
 
2251
            lines = self.backing_knit.get_lines(version_id)
 
2252
            line_bytes = ''.join(lines)
 
2253
            digest = sha_string(line_bytes)
 
2254
            # the packed form of the fulltext always has a trailing newline,
 
2255
            # even if the actual text does not, unless the file is empty.  the
 
2256
            # record options including the noeol flag are passed through by
 
2257
            # _StreamIndex, so this is safe.
 
2258
            if lines:
 
2259
                if lines[-1][-1] != '\n':
 
2260
                    lines[-1] = lines[-1] + '\n'
 
2261
                    line_bytes += '\n'
 
2262
            # We want plain data, because we expect to thunk only to allow text
 
2263
            # extraction.
 
2264
            size, bytes = self.backing_knit._data._record_to_data(version_id,
 
2265
                digest, lines, line_bytes)
 
2266
            yield bytes
 
2267
 
 
2268
 
 
2269
class _StreamIndex(object):
 
2270
    """A Knit Index object that uses the data map from a datastream."""
 
2271
 
 
2272
    def __init__(self, data_list, backing_index):
 
2273
        """Create a _StreamIndex object.
 
2274
 
 
2275
        :param data_list: The data_list from the datastream.
 
2276
        :param backing_index: The index which will supply values for nodes
 
2277
            referenced outside of this stream.
 
2278
        """
 
2279
        self.data_list = data_list
 
2280
        self.backing_index = backing_index
 
2281
        self._by_version = {}
 
2282
        pos = 0
 
2283
        for key, options, length, parents in data_list:
 
2284
            self._by_version[key] = options, (pos, pos + length), parents
 
2285
            pos += length
 
2286
 
 
2287
    def get_ancestry(self, versions, topo_sorted):
 
2288
        """Get an ancestry list for versions."""
 
2289
        if topo_sorted:
 
2290
            # Not needed for basic joins
 
2291
            raise NotImplementedError(self.get_ancestry)
 
2292
        # get a graph of all the mentioned versions:
 
2293
        # Little ugly - basically copied from KnitIndex, but don't want to
 
2294
        # accidentally incorporate too much of that index's code.
 
2295
        ancestry = set()
 
2296
        pending = set(versions)
 
2297
        cache = self._by_version
 
2298
        while pending:
 
2299
            version = pending.pop()
 
2300
            # trim ghosts
 
2301
            try:
 
2302
                parents = [p for p in cache[version][2] if p in cache]
 
2303
            except KeyError:
 
2304
                raise RevisionNotPresent(version, self)
 
2305
            # if not completed and not a ghost
 
2306
            pending.update([p for p in parents if p not in ancestry])
 
2307
            ancestry.add(version)
 
2308
        return list(ancestry)
 
2309
 
 
2310
    def get_build_details(self, version_ids):
 
2311
        """Get the method, index_memo and compression parent for version_ids.
 
2312
 
 
2313
        Ghosts are omitted from the result.
 
2314
 
 
2315
        :param version_ids: An iterable of version_ids.
 
2316
        :return: A dict of version_id:(index_memo, compression_parent,
 
2317
                                       parents, record_details).
 
2318
            index_memo
 
2319
                opaque memo that can be passed to _StreamAccess.read_records
 
2320
                to extract the raw data; for these classes it is
 
2321
                (from_backing_knit, index, start, end) 
 
2322
            compression_parent
 
2323
                Content that this record is built upon, may be None
 
2324
            parents
 
2325
                Logical parents of this node
 
2326
            record_details
 
2327
                extra information about the content which needs to be passed to
 
2328
                Factory.parse_record
 
2329
        """
 
2330
        result = {}
 
2331
        for version_id in version_ids:
 
2332
            try:
 
2333
                method = self.get_method(version_id)
 
2334
            except errors.RevisionNotPresent:
 
2335
                # ghosts are omitted
 
2336
                continue
 
2337
            parent_ids = self.get_parents_with_ghosts(version_id)
 
2338
            noeol = ('no-eol' in self.get_options(version_id))
 
2339
            index_memo = self.get_position(version_id)
 
2340
            from_backing_knit = index_memo[0]
 
2341
            if from_backing_knit:
 
2342
                # texts retrieved from the backing knit are always full texts
 
2343
                method = 'fulltext'
 
2344
            if method == 'fulltext':
 
2345
                compression_parent = None
 
2346
            else:
 
2347
                compression_parent = parent_ids[0]
 
2348
            result[version_id] = (index_memo, compression_parent,
 
2349
                                  parent_ids, (method, noeol))
 
2350
        return result
 
2351
 
 
2352
    def get_method(self, version_id):
 
2353
        """Return compression method of specified version."""
 
2354
        options = self.get_options(version_id)
 
2355
        if 'fulltext' in options:
 
2356
            return 'fulltext'
 
2357
        elif 'line-delta' in options:
 
2358
            return 'line-delta'
 
2359
        else:
 
2360
            raise errors.KnitIndexUnknownMethod(self, options)
 
2361
 
 
2362
    def get_options(self, version_id):
 
2363
        """Return a list representing options.
 
2364
 
 
2365
        e.g. ['foo', 'bar']
 
2366
        """
 
2367
        try:
 
2368
            return self._by_version[version_id][0]
 
2369
        except KeyError:
 
2370
            options = list(self.backing_index.get_options(version_id))
 
2371
            if 'fulltext' in options:
 
2372
                pass
 
2373
            elif 'line-delta' in options:
 
2374
                # Texts from the backing knit are always returned from the stream
 
2375
                # as full texts
 
2376
                options.remove('line-delta')
 
2377
                options.append('fulltext')
 
2378
            else:
 
2379
                raise errors.KnitIndexUnknownMethod(self, options)
 
2380
            return tuple(options)
 
2381
 
 
2382
    def get_parent_map(self, version_ids):
 
2383
        """Passed through to by KnitVersionedFile.get_parent_map."""
 
2384
        result = {}
 
2385
        pending_ids = set()
 
2386
        for version_id in version_ids:
 
2387
            try:
 
2388
                result[version_id] = self._by_version[version_id][2]
 
2389
            except KeyError:
 
2390
                pending_ids.add(version_id)
 
2391
        result.update(self.backing_index.get_parent_map(pending_ids))
 
2392
        return result
 
2393
 
 
2394
    def get_parents_with_ghosts(self, version_id):
 
2395
        """Return parents of specified version with ghosts."""
 
2396
        try:
 
2397
            return self.get_parent_map([version_id])[version_id]
 
2398
        except KeyError:
 
2399
            raise RevisionNotPresent(version_id, self)
 
2400
 
 
2401
    def get_position(self, version_id):
 
2402
        """Return details needed to access the version.
 
2403
        
 
2404
        _StreamAccess has the data as a big array, so we return slice
 
2405
        coordinates into that (as index_memo's are opaque outside the
 
2406
        index and matching access class).
 
2407
 
 
2408
        :return: a tuple (from_backing_knit, index, start, end) that can 
 
2409
            be passed e.g. to get_raw_records.  
 
2410
            If from_backing_knit is False, index will be self, otherwise it
 
2411
            will be a version id.
 
2412
        """
 
2413
        try:
 
2414
            start, end = self._by_version[version_id][1]
 
2415
            return False, self, start, end
 
2416
        except KeyError:
 
2417
            # Signal to the access object to handle this from the backing knit.
 
2418
            return (True, version_id, None, None)
 
2419
 
 
2420
    def get_versions(self):
 
2421
        """Get all the versions in the stream."""
 
2422
        return self._by_version.keys()
 
2423
 
 
2424
    def iter_parents(self, version_ids):
 
2425
        """Iterate through the parents for many version ids.
 
2426
 
 
2427
        :param version_ids: An iterable yielding version_ids.
 
2428
        :return: An iterator that yields (version_id, parents). Requested 
 
2429
            version_ids not present in the versioned file are simply skipped.
 
2430
            The order is undefined, allowing for different optimisations in
 
2431
            the underlying implementation.
 
2432
        """
 
2433
        result = []
 
2434
        for version in version_ids:
 
2435
            try:
 
2436
                result.append((version, self._by_version[version][2]))
 
2437
            except KeyError:
 
2438
                pass
 
2439
        return result
 
2440
 
 
2441
 
 
2442
class _KnitData(object):
 
2443
    """Manage extraction of data from a KnitAccess, caching and decompressing.
 
2444
    
 
2445
    The KnitData class provides the logic for parsing and using knit records,
 
2446
    making use of an access method for the low level read and write operations.
 
2447
    """
 
2448
 
 
2449
    def __init__(self, access):
 
2450
        """Create a KnitData object.
 
2451
 
 
2452
        :param access: The access method to use. Access methods such as
 
2453
            _KnitAccess manage the insertion of raw records and the subsequent
 
2454
            retrieval of the same.
 
2455
        """
 
2456
        self._access = access
 
2457
        self._checked = False
 
2458
        # TODO: jam 20060713 conceptually, this could spill to disk
 
2459
        #       if the cached size gets larger than a certain amount
 
2460
        #       but it complicates the model a bit, so for now just use
 
2461
        #       a simple dictionary
 
2462
        self._cache = {}
 
2463
        self._do_cache = False
 
2464
 
 
2465
    def enable_cache(self):
 
2466
        """Enable caching of reads."""
 
2467
        self._do_cache = True
 
2468
 
 
2469
    def clear_cache(self):
 
2470
        """Clear the record cache."""
 
2471
        self._do_cache = False
 
2472
        self._cache = {}
 
2473
 
 
2474
    def _open_file(self):
 
2475
        return self._access.open_file()
 
2476
 
 
2477
    def _record_to_data(self, version_id, digest, lines, dense_lines=None):
 
2478
        """Convert version_id, digest, lines into a raw data block.
 
2479
        
 
2480
        :param dense_lines: The bytes of lines but in a denser form. For
 
2481
            instance, if lines is a list of 1000 bytestrings each ending in \n,
 
2482
            dense_lines may be a list with one line in it, containing all the
 
2483
            1000's lines and their \n's. Using dense_lines if it is already
 
2484
            known is a win because the string join to create bytes in this
 
2485
            function spends less time resizing the final string.
 
2486
        :return: (len, a StringIO instance with the raw data ready to read.)
 
2487
        """
 
2488
        # Note: using a string copy here increases memory pressure with e.g.
 
2489
        # ISO's, but it is about 3 seconds faster on a 1.2Ghz intel machine
 
2490
        # when doing the initial commit of a mozilla tree. RBC 20070921
 
2491
        bytes = ''.join(chain(
 
2492
            ["version %s %d %s\n" % (version_id,
 
2493
                                     len(lines),
 
2494
                                     digest)],
 
2495
            dense_lines or lines,
 
2496
            ["end %s\n" % version_id]))
 
2497
        assert bytes.__class__ == str
 
2498
        compressed_bytes = bytes_to_gzip(bytes)
 
2499
        return len(compressed_bytes), compressed_bytes
 
2500
 
 
2501
    def add_raw_records(self, sizes, raw_data):
 
2502
        """Append a prepared record to the data file.
 
2503
        
 
2504
        :param sizes: An iterable containing the size of each raw data segment.
 
2505
        :param raw_data: A bytestring containing the data.
 
2506
        :return: a list of index data for the way the data was stored.
 
2507
            See the access method add_raw_records documentation for more
 
2508
            details.
 
2509
        """
 
2510
        return self._access.add_raw_records(sizes, raw_data)
 
2511
        
 
2512
    def _parse_record_header(self, version_id, raw_data):
 
2513
        """Parse a record header for consistency.
 
2514
 
 
2515
        :return: the header and the decompressor stream.
 
2516
                 as (stream, header_record)
 
2517
        """
 
2518
        df = GzipFile(mode='rb', fileobj=StringIO(raw_data))
 
2519
        try:
 
2520
            rec = self._check_header(version_id, df.readline())
 
2521
        except Exception, e:
 
2522
            raise KnitCorrupt(self._access,
 
2523
                              "While reading {%s} got %s(%s)"
 
2524
                              % (version_id, e.__class__.__name__, str(e)))
 
2525
        return df, rec
 
2526
 
 
2527
    def _check_header(self, version_id, line):
 
2528
        rec = line.split()
 
2529
        if len(rec) != 4:
 
2530
            raise KnitCorrupt(self._access,
 
2531
                              'unexpected number of elements in record header')
 
2532
        if rec[1] != version_id:
 
2533
            raise KnitCorrupt(self._access,
 
2534
                              'unexpected version, wanted %r, got %r'
 
2535
                              % (version_id, rec[1]))
 
2536
        return rec
 
2537
 
 
2538
    def _parse_record(self, version_id, data):
 
2539
        # profiling notes:
 
2540
        # 4168 calls in 2880 217 internal
 
2541
        # 4168 calls to _parse_record_header in 2121
 
2542
        # 4168 calls to readlines in 330
 
2543
        df = GzipFile(mode='rb', fileobj=StringIO(data))
 
2544
 
 
2545
        try:
 
2546
            record_contents = df.readlines()
 
2547
        except Exception, e:
 
2548
            raise KnitCorrupt(self._access,
 
2549
                              "While reading {%s} got %s(%s)"
 
2550
                              % (version_id, e.__class__.__name__, str(e)))
 
2551
        header = record_contents.pop(0)
 
2552
        rec = self._check_header(version_id, header)
 
2553
 
 
2554
        last_line = record_contents.pop()
 
2555
        if len(record_contents) != int(rec[2]):
 
2556
            raise KnitCorrupt(self._access,
 
2557
                              'incorrect number of lines %s != %s'
 
2558
                              ' for version {%s}'
 
2559
                              % (len(record_contents), int(rec[2]),
 
2560
                                 version_id))
 
2561
        if last_line != 'end %s\n' % rec[1]:
 
2562
            raise KnitCorrupt(self._access,
 
2563
                              'unexpected version end line %r, wanted %r' 
 
2564
                              % (last_line, version_id))
 
2565
        df.close()
 
2566
        return record_contents, rec[3]
 
2567
 
 
2568
    def read_records_iter_raw(self, records):
 
2569
        """Read text records from data file and yield raw data.
 
2570
 
 
2571
        This unpacks enough of the text record to validate the id is
 
2572
        as expected but thats all.
 
2573
        """
 
2574
        # setup an iterator of the external records:
 
2575
        # uses readv so nice and fast we hope.
 
2576
        if len(records):
 
2577
            # grab the disk data needed.
 
2578
            if self._cache:
 
2579
                # Don't check _cache if it is empty
 
2580
                needed_offsets = [index_memo for version_id, index_memo
 
2581
                                              in records
 
2582
                                              if version_id not in self._cache]
 
2583
            else:
 
2584
                needed_offsets = [index_memo for version_id, index_memo
 
2585
                                               in records]
 
2586
 
 
2587
            raw_records = self._access.get_raw_records(needed_offsets)
 
2588
 
 
2589
        for version_id, index_memo in records:
 
2590
            if version_id in self._cache:
 
2591
                # This data has already been validated
 
2592
                data = self._cache[version_id]
 
2593
            else:
 
2594
                data = raw_records.next()
 
2595
                if self._do_cache:
 
2596
                    self._cache[version_id] = data
 
2597
 
 
2598
                # validate the header
 
2599
                df, rec = self._parse_record_header(version_id, data)
 
2600
                df.close()
 
2601
            yield version_id, data
 
2602
 
 
2603
    def read_records_iter(self, records):
 
2604
        """Read text records from data file and yield result.
 
2605
 
 
2606
        The result will be returned in whatever is the fastest to read.
 
2607
        Not by the order requested. Also, multiple requests for the same
 
2608
        record will only yield 1 response.
 
2609
        :param records: A list of (version_id, pos, len) entries
 
2610
        :return: Yields (version_id, contents, digest) in the order
 
2611
                 read, not the order requested
 
2612
        """
 
2613
        if not records:
 
2614
            return
 
2615
 
 
2616
        if self._cache:
 
2617
            # Skip records we have alread seen
 
2618
            yielded_records = set()
 
2619
            needed_records = set()
 
2620
            for record in records:
 
2621
                if record[0] in self._cache:
 
2622
                    if record[0] in yielded_records:
 
2623
                        continue
 
2624
                    yielded_records.add(record[0])
 
2625
                    data = self._cache[record[0]]
 
2626
                    content, digest = self._parse_record(record[0], data)
 
2627
                    yield (record[0], content, digest)
 
2628
                else:
 
2629
                    needed_records.add(record)
 
2630
            needed_records = sorted(needed_records, key=operator.itemgetter(1))
 
2631
        else:
 
2632
            needed_records = sorted(set(records), key=operator.itemgetter(1))
 
2633
 
 
2634
        if not needed_records:
 
2635
            return
 
2636
 
 
2637
        # The transport optimizes the fetching as well 
 
2638
        # (ie, reads continuous ranges.)
 
2639
        raw_data = self._access.get_raw_records(
 
2640
            [index_memo for version_id, index_memo in needed_records])
 
2641
 
 
2642
        for (version_id, index_memo), data in \
 
2643
                izip(iter(needed_records), raw_data):
 
2644
            content, digest = self._parse_record(version_id, data)
 
2645
            if self._do_cache:
 
2646
                self._cache[version_id] = data
 
2647
            yield version_id, content, digest
 
2648
 
 
2649
    def read_records(self, records):
 
2650
        """Read records into a dictionary."""
 
2651
        components = {}
 
2652
        for record_id, content, digest in \
 
2653
                self.read_records_iter(records):
 
2654
            components[record_id] = (content, digest)
 
2655
        return components
 
2656
 
 
2657
 
 
2658
class InterKnit(InterVersionedFile):
 
2659
    """Optimised code paths for knit to knit operations."""
 
2660
    
 
2661
    _matching_file_from_factory = KnitVersionedFile
 
2662
    _matching_file_to_factory = KnitVersionedFile
 
2663
    
 
2664
    @staticmethod
 
2665
    def is_compatible(source, target):
 
2666
        """Be compatible with knits.  """
 
2667
        try:
 
2668
            return (isinstance(source, KnitVersionedFile) and
 
2669
                    isinstance(target, KnitVersionedFile))
 
2670
        except AttributeError:
 
2671
            return False
 
2672
 
 
2673
    def _copy_texts(self, pb, msg, version_ids, ignore_missing=False):
 
2674
        """Copy texts to the target by extracting and adding them one by one.
 
2675
 
 
2676
        see join() for the parameter definitions.
 
2677
        """
 
2678
        version_ids = self._get_source_version_ids(version_ids, ignore_missing)
 
2679
        # --- the below is factorable out with VersionedFile.join, but wait for
 
2680
        # VersionedFiles, it may all be simpler then.
 
2681
        graph = Graph(self.source)
 
2682
        search = graph._make_breadth_first_searcher(version_ids)
 
2683
        transitive_ids = set()
 
2684
        map(transitive_ids.update, list(search))
 
2685
        parent_map = self.source.get_parent_map(transitive_ids)
 
2686
        order = topo_sort(parent_map.items())
 
2687
 
 
2688
        def size_of_content(content):
 
2689
            return sum(len(line) for line in content.text())
 
2690
        # Cache at most 10MB of parent texts
 
2691
        parent_cache = lru_cache.LRUSizeCache(max_size=10*1024*1024,
 
2692
                                              compute_size=size_of_content)
 
2693
        # TODO: jam 20071116 It would be nice to have a streaming interface to
 
2694
        #       get multiple texts from a source. The source could be smarter
 
2695
        #       about how it handled intermediate stages.
 
2696
        #       get_line_list() or make_mpdiffs() seem like a possibility, but
 
2697
        #       at the moment they extract all full texts into memory, which
 
2698
        #       causes us to store more than our 3x fulltext goal.
 
2699
        #       Repository.iter_files_bytes() may be another possibility
 
2700
        to_process = [version for version in order
 
2701
                               if version not in self.target]
 
2702
        total = len(to_process)
 
2703
        pb = ui.ui_factory.nested_progress_bar()
 
2704
        try:
 
2705
            for index, version in enumerate(to_process):
 
2706
                pb.update('Converting versioned data', index, total)
 
2707
                sha1, num_bytes, parent_text = self.target.add_lines(version,
 
2708
                    self.source.get_parents_with_ghosts(version),
 
2709
                    self.source.get_lines(version),
 
2710
                    parent_texts=parent_cache)
 
2711
                parent_cache[version] = parent_text
 
2712
        finally:
 
2713
            pb.finished()
 
2714
        return total
 
2715
 
 
2716
    def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
 
2717
        """See InterVersionedFile.join."""
 
2718
        assert isinstance(self.source, KnitVersionedFile)
 
2719
        assert isinstance(self.target, KnitVersionedFile)
 
2720
 
 
2721
        # If the source and target are mismatched w.r.t. annotations vs
 
2722
        # plain, the data needs to be converted accordingly
 
2723
        if self.source.factory.annotated == self.target.factory.annotated:
 
2724
            converter = None
 
2725
        elif self.source.factory.annotated:
 
2726
            converter = self._anno_to_plain_converter
 
2727
        else:
 
2728
            # We're converting from a plain to an annotated knit. Copy them
 
2729
            # across by full texts.
 
2730
            return self._copy_texts(pb, msg, version_ids, ignore_missing)
 
2731
 
 
2732
        version_ids = self._get_source_version_ids(version_ids, ignore_missing)
 
2733
        if not version_ids:
 
2734
            return 0
 
2735
 
 
2736
        pb = ui.ui_factory.nested_progress_bar()
 
2737
        try:
 
2738
            version_ids = list(version_ids)
 
2739
            if None in version_ids:
 
2740
                version_ids.remove(None)
 
2741
    
 
2742
            self.source_ancestry = set(self.source.get_ancestry(version_ids,
 
2743
                topo_sorted=False))
 
2744
            this_versions = set(self.target._index.get_versions())
 
2745
            # XXX: For efficiency we should not look at the whole index,
 
2746
            #      we only need to consider the referenced revisions - they
 
2747
            #      must all be present, or the method must be full-text.
 
2748
            #      TODO, RBC 20070919
 
2749
            needed_versions = self.source_ancestry - this_versions
 
2750
    
 
2751
            if not needed_versions:
 
2752
                return 0
 
2753
            full_list = topo_sort(
 
2754
                self.source.get_parent_map(self.source.versions()))
 
2755
    
 
2756
            version_list = [i for i in full_list if (not self.target.has_version(i)
 
2757
                            and i in needed_versions)]
 
2758
    
 
2759
            # plan the join:
 
2760
            copy_queue = []
 
2761
            copy_queue_records = []
 
2762
            copy_set = set()
 
2763
            for version_id in version_list:
 
2764
                options = self.source._index.get_options(version_id)
 
2765
                parents = self.source._index.get_parents_with_ghosts(version_id)
 
2766
                # check that its will be a consistent copy:
 
2767
                for parent in parents:
 
2768
                    # if source has the parent, we must :
 
2769
                    # * already have it or
 
2770
                    # * have it scheduled already
 
2771
                    # otherwise we don't care
 
2772
                    assert (self.target.has_version(parent) or
 
2773
                            parent in copy_set or
 
2774
                            not self.source.has_version(parent))
 
2775
                index_memo = self.source._index.get_position(version_id)
 
2776
                copy_queue_records.append((version_id, index_memo))
 
2777
                copy_queue.append((version_id, options, parents))
 
2778
                copy_set.add(version_id)
 
2779
 
 
2780
            # data suck the join:
 
2781
            count = 0
 
2782
            total = len(version_list)
 
2783
            raw_datum = []
 
2784
            raw_records = []
 
2785
            for (version_id, raw_data), \
 
2786
                (version_id2, options, parents) in \
 
2787
                izip(self.source._data.read_records_iter_raw(copy_queue_records),
 
2788
                     copy_queue):
 
2789
                assert version_id == version_id2, 'logic error, inconsistent results'
 
2790
                count = count + 1
 
2791
                pb.update("Joining knit", count, total)
 
2792
                if converter:
 
2793
                    size, raw_data = converter(raw_data, version_id, options,
 
2794
                        parents)
 
2795
                else:
 
2796
                    size = len(raw_data)
 
2797
                raw_records.append((version_id, options, parents, size))
 
2798
                raw_datum.append(raw_data)
 
2799
            self.target._add_raw_records(raw_records, ''.join(raw_datum))
 
2800
            return count
 
2801
        finally:
 
2802
            pb.finished()
 
2803
 
 
2804
    def _anno_to_plain_converter(self, raw_data, version_id, options,
 
2805
                                 parents):
 
2806
        """Convert annotated content to plain content."""
 
2807
        data, digest = self.source._data._parse_record(version_id, raw_data)
 
2808
        if 'fulltext' in options:
 
2809
            content = self.source.factory.parse_fulltext(data, version_id)
 
2810
            lines = self.target.factory.lower_fulltext(content)
 
2811
        else:
 
2812
            delta = self.source.factory.parse_line_delta(data, version_id,
 
2813
                plain=True)
 
2814
            lines = self.target.factory.lower_line_delta(delta)
 
2815
        return self.target._data._record_to_data(version_id, digest, lines)
 
2816
 
 
2817
 
 
2818
InterVersionedFile.register_optimiser(InterKnit)
 
2819
 
 
2820
 
 
2821
class WeaveToKnit(InterVersionedFile):
 
2822
    """Optimised code paths for weave to knit operations."""
 
2823
    
 
2824
    _matching_file_from_factory = bzrlib.weave.WeaveFile
 
2825
    _matching_file_to_factory = KnitVersionedFile
 
2826
    
 
2827
    @staticmethod
 
2828
    def is_compatible(source, target):
 
2829
        """Be compatible with weaves to knits."""
 
2830
        try:
 
2831
            return (isinstance(source, bzrlib.weave.Weave) and
 
2832
                    isinstance(target, KnitVersionedFile))
 
2833
        except AttributeError:
 
2834
            return False
 
2835
 
 
2836
    def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
 
2837
        """See InterVersionedFile.join."""
 
2838
        assert isinstance(self.source, bzrlib.weave.Weave)
 
2839
        assert isinstance(self.target, KnitVersionedFile)
 
2840
 
 
2841
        version_ids = self._get_source_version_ids(version_ids, ignore_missing)
 
2842
 
 
2843
        if not version_ids:
 
2844
            return 0
 
2845
 
 
2846
        pb = ui.ui_factory.nested_progress_bar()
 
2847
        try:
 
2848
            version_ids = list(version_ids)
 
2849
    
 
2850
            self.source_ancestry = set(self.source.get_ancestry(version_ids))
 
2851
            this_versions = set(self.target._index.get_versions())
 
2852
            needed_versions = self.source_ancestry - this_versions
 
2853
    
 
2854
            if not needed_versions:
 
2855
                return 0
 
2856
            full_list = topo_sort(
 
2857
                self.source.get_parent_map(self.source.versions()))
 
2858
    
 
2859
            version_list = [i for i in full_list if (not self.target.has_version(i)
 
2860
                            and i in needed_versions)]
 
2861
    
 
2862
            # do the join:
 
2863
            count = 0
 
2864
            total = len(version_list)
 
2865
            parent_map = self.source.get_parent_map(version_list)
 
2866
            for version_id in version_list:
 
2867
                pb.update("Converting to knit", count, total)
 
2868
                parents = parent_map[version_id]
 
2869
                # check that its will be a consistent copy:
 
2870
                for parent in parents:
 
2871
                    # if source has the parent, we must already have it
 
2872
                    assert (self.target.has_version(parent))
 
2873
                self.target.add_lines(
 
2874
                    version_id, parents, self.source.get_lines(version_id))
 
2875
                count = count + 1
 
2876
            return count
 
2877
        finally:
 
2878
            pb.finished()
 
2879
 
 
2880
 
 
2881
InterVersionedFile.register_optimiser(WeaveToKnit)
 
2882
 
 
2883
 
 
2884
# Deprecated, use PatienceSequenceMatcher instead
 
2885
KnitSequenceMatcher = patiencediff.PatienceSequenceMatcher
 
2886
 
 
2887
 
 
2888
def annotate_knit(knit, revision_id):
 
2889
    """Annotate a knit with no cached annotations.
 
2890
 
 
2891
    This implementation is for knits with no cached annotations.
 
2892
    It will work for knits with cached annotations, but this is not
 
2893
    recommended.
 
2894
    """
 
2895
    annotator = _KnitAnnotator(knit)
 
2896
    return iter(annotator.annotate(revision_id))
 
2897
 
 
2898
 
 
2899
class _KnitAnnotator(object):
 
2900
    """Build up the annotations for a text."""
 
2901
 
 
2902
    def __init__(self, knit):
 
2903
        self._knit = knit
 
2904
 
 
2905
        # Content objects, differs from fulltexts because of how final newlines
 
2906
        # are treated by knits. the content objects here will always have a
 
2907
        # final newline
 
2908
        self._fulltext_contents = {}
 
2909
 
 
2910
        # Annotated lines of specific revisions
 
2911
        self._annotated_lines = {}
 
2912
 
 
2913
        # Track the raw data for nodes that we could not process yet.
 
2914
        # This maps the revision_id of the base to a list of children that will
 
2915
        # annotated from it.
 
2916
        self._pending_children = {}
 
2917
 
 
2918
        # Nodes which cannot be extracted
 
2919
        self._ghosts = set()
 
2920
 
 
2921
        # Track how many children this node has, so we know if we need to keep
 
2922
        # it
 
2923
        self._annotate_children = {}
 
2924
        self._compression_children = {}
 
2925
 
 
2926
        self._all_build_details = {}
 
2927
        # The children => parent revision_id graph
 
2928
        self._revision_id_graph = {}
 
2929
 
 
2930
        self._heads_provider = None
 
2931
 
 
2932
        self._nodes_to_keep_annotations = set()
 
2933
        self._generations_until_keep = 100
 
2934
 
 
2935
    def set_generations_until_keep(self, value):
 
2936
        """Set the number of generations before caching a node.
 
2937
 
 
2938
        Setting this to -1 will cache every merge node, setting this higher
 
2939
        will cache fewer nodes.
 
2940
        """
 
2941
        self._generations_until_keep = value
 
2942
 
 
2943
    def _add_fulltext_content(self, revision_id, content_obj):
 
2944
        self._fulltext_contents[revision_id] = content_obj
 
2945
        # TODO: jam 20080305 It might be good to check the sha1digest here
 
2946
        return content_obj.text()
 
2947
 
 
2948
    def _check_parents(self, child, nodes_to_annotate):
 
2949
        """Check if all parents have been processed.
 
2950
 
 
2951
        :param child: A tuple of (rev_id, parents, raw_content)
 
2952
        :param nodes_to_annotate: If child is ready, add it to
 
2953
            nodes_to_annotate, otherwise put it back in self._pending_children
 
2954
        """
 
2955
        for parent_id in child[1]:
 
2956
            if (parent_id not in self._annotated_lines):
 
2957
                # This parent is present, but another parent is missing
 
2958
                self._pending_children.setdefault(parent_id,
 
2959
                                                  []).append(child)
 
2960
                break
 
2961
        else:
 
2962
            # This one is ready to be processed
 
2963
            nodes_to_annotate.append(child)
 
2964
 
 
2965
    def _add_annotation(self, revision_id, fulltext, parent_ids,
 
2966
                        left_matching_blocks=None):
 
2967
        """Add an annotation entry.
 
2968
 
 
2969
        All parents should already have been annotated.
 
2970
        :return: A list of children that now have their parents satisfied.
 
2971
        """
 
2972
        a = self._annotated_lines
 
2973
        annotated_parent_lines = [a[p] for p in parent_ids]
 
2974
        annotated_lines = list(annotate.reannotate(annotated_parent_lines,
 
2975
            fulltext, revision_id, left_matching_blocks,
 
2976
            heads_provider=self._get_heads_provider()))
 
2977
        self._annotated_lines[revision_id] = annotated_lines
 
2978
        for p in parent_ids:
 
2979
            ann_children = self._annotate_children[p]
 
2980
            ann_children.remove(revision_id)
 
2981
            if (not ann_children
 
2982
                and p not in self._nodes_to_keep_annotations):
 
2983
                del self._annotated_lines[p]
 
2984
                del self._all_build_details[p]
 
2985
                if p in self._fulltext_contents:
 
2986
                    del self._fulltext_contents[p]
 
2987
        # Now that we've added this one, see if there are any pending
 
2988
        # deltas to be done, certainly this parent is finished
 
2989
        nodes_to_annotate = []
 
2990
        for child in self._pending_children.pop(revision_id, []):
 
2991
            self._check_parents(child, nodes_to_annotate)
 
2992
        return nodes_to_annotate
 
2993
 
 
2994
    def _get_build_graph(self, revision_id):
 
2995
        """Get the graphs for building texts and annotations.
 
2996
 
 
2997
        The data you need for creating a full text may be different than the
 
2998
        data you need to annotate that text. (At a minimum, you need both
 
2999
        parents to create an annotation, but only need 1 parent to generate the
 
3000
        fulltext.)
 
3001
 
 
3002
        :return: A list of (revision_id, index_memo) records, suitable for
 
3003
            passing to read_records_iter to start reading in the raw data fro/
 
3004
            the pack file.
 
3005
        """
 
3006
        if revision_id in self._annotated_lines:
 
3007
            # Nothing to do
 
3008
            return []
 
3009
        pending = set([revision_id])
 
3010
        records = []
 
3011
        generation = 0
 
3012
        kept_generation = 0
 
3013
        while pending:
 
3014
            # get all pending nodes
 
3015
            generation += 1
 
3016
            this_iteration = pending
 
3017
            build_details = self._knit._index.get_build_details(this_iteration)
 
3018
            self._all_build_details.update(build_details)
 
3019
            # new_nodes = self._knit._index._get_entries(this_iteration)
 
3020
            pending = set()
 
3021
            for rev_id, details in build_details.iteritems():
 
3022
                (index_memo, compression_parent, parents,
 
3023
                 record_details) = details
 
3024
                self._revision_id_graph[rev_id] = parents
 
3025
                records.append((rev_id, index_memo))
 
3026
                # Do we actually need to check _annotated_lines?
 
3027
                pending.update(p for p in parents
 
3028
                                 if p not in self._all_build_details)
 
3029
                if compression_parent:
 
3030
                    self._compression_children.setdefault(compression_parent,
 
3031
                        []).append(rev_id)
 
3032
                if parents:
 
3033
                    for parent in parents:
 
3034
                        self._annotate_children.setdefault(parent,
 
3035
                            []).append(rev_id)
 
3036
                    num_gens = generation - kept_generation
 
3037
                    if ((num_gens >= self._generations_until_keep)
 
3038
                        and len(parents) > 1):
 
3039
                        kept_generation = generation
 
3040
                        self._nodes_to_keep_annotations.add(rev_id)
 
3041
 
 
3042
            missing_versions = this_iteration.difference(build_details.keys())
 
3043
            self._ghosts.update(missing_versions)
 
3044
            for missing_version in missing_versions:
 
3045
                # add a key, no parents
 
3046
                self._revision_id_graph[missing_version] = ()
 
3047
                pending.discard(missing_version) # don't look for it
 
3048
        # XXX: This should probably be a real exception, as it is a data
 
3049
        #      inconsistency
 
3050
        assert not self._ghosts.intersection(self._compression_children), \
 
3051
            "We cannot have nodes which have a compression parent of a ghost."
 
3052
        # Cleanout anything that depends on a ghost so that we don't wait for
 
3053
        # the ghost to show up
 
3054
        for node in self._ghosts:
 
3055
            if node in self._annotate_children:
 
3056
                # We won't be building this node
 
3057
                del self._annotate_children[node]
 
3058
        # Generally we will want to read the records in reverse order, because
 
3059
        # we find the parent nodes after the children
 
3060
        records.reverse()
 
3061
        return records
 
3062
 
 
3063
    def _annotate_records(self, records):
 
3064
        """Build the annotations for the listed records."""
 
3065
        # We iterate in the order read, rather than a strict order requested
 
3066
        # However, process what we can, and put off to the side things that
 
3067
        # still need parents, cleaning them up when those parents are
 
3068
        # processed.
 
3069
        for (rev_id, record,
 
3070
             digest) in self._knit._data.read_records_iter(records):
 
3071
            if rev_id in self._annotated_lines:
 
3072
                continue
 
3073
            parent_ids = self._revision_id_graph[rev_id]
 
3074
            parent_ids = [p for p in parent_ids if p not in self._ghosts]
 
3075
            details = self._all_build_details[rev_id]
 
3076
            (index_memo, compression_parent, parents,
 
3077
             record_details) = details
 
3078
            nodes_to_annotate = []
 
3079
            # TODO: Remove the punning between compression parents, and
 
3080
            #       parent_ids, we should be able to do this without assuming
 
3081
            #       the build order
 
3082
            if len(parent_ids) == 0:
 
3083
                # There are no parents for this node, so just add it
 
3084
                # TODO: This probably needs to be decoupled
 
3085
                assert compression_parent is None
 
3086
                fulltext_content, delta = self._knit.factory.parse_record(
 
3087
                    rev_id, record, record_details, None)
 
3088
                fulltext = self._add_fulltext_content(rev_id, fulltext_content)
 
3089
                nodes_to_annotate.extend(self._add_annotation(rev_id, fulltext,
 
3090
                    parent_ids, left_matching_blocks=None))
 
3091
            else:
 
3092
                child = (rev_id, parent_ids, record)
 
3093
                # Check if all the parents are present
 
3094
                self._check_parents(child, nodes_to_annotate)
 
3095
            while nodes_to_annotate:
 
3096
                # Should we use a queue here instead of a stack?
 
3097
                (rev_id, parent_ids, record) = nodes_to_annotate.pop()
 
3098
                (index_memo, compression_parent, parents,
 
3099
                 record_details) = self._all_build_details[rev_id]
 
3100
                if compression_parent is not None:
 
3101
                    comp_children = self._compression_children[compression_parent]
 
3102
                    assert rev_id in comp_children
 
3103
                    # If there is only 1 child, it is safe to reuse this
 
3104
                    # content
 
3105
                    reuse_content = (len(comp_children) == 1
 
3106
                        and compression_parent not in
 
3107
                            self._nodes_to_keep_annotations)
 
3108
                    if reuse_content:
 
3109
                        # Remove it from the cache since it will be changing
 
3110
                        parent_fulltext_content = self._fulltext_contents.pop(compression_parent)
 
3111
                        # Make sure to copy the fulltext since it might be
 
3112
                        # modified
 
3113
                        parent_fulltext = list(parent_fulltext_content.text())
 
3114
                    else:
 
3115
                        parent_fulltext_content = self._fulltext_contents[compression_parent]
 
3116
                        parent_fulltext = parent_fulltext_content.text()
 
3117
                    comp_children.remove(rev_id)
 
3118
                    fulltext_content, delta = self._knit.factory.parse_record(
 
3119
                        rev_id, record, record_details,
 
3120
                        parent_fulltext_content,
 
3121
                        copy_base_content=(not reuse_content))
 
3122
                    fulltext = self._add_fulltext_content(rev_id,
 
3123
                                                          fulltext_content)
 
3124
                    blocks = KnitContent.get_line_delta_blocks(delta,
 
3125
                            parent_fulltext, fulltext)
 
3126
                else:
 
3127
                    fulltext_content = self._knit.factory.parse_fulltext(
 
3128
                        record, rev_id)
 
3129
                    fulltext = self._add_fulltext_content(rev_id,
 
3130
                        fulltext_content)
 
3131
                    blocks = None
 
3132
                nodes_to_annotate.extend(
 
3133
                    self._add_annotation(rev_id, fulltext, parent_ids,
 
3134
                                     left_matching_blocks=blocks))
 
3135
 
 
3136
    def _get_heads_provider(self):
 
3137
        """Create a heads provider for resolving ancestry issues."""
 
3138
        if self._heads_provider is not None:
 
3139
            return self._heads_provider
 
3140
        parent_provider = _mod_graph.DictParentsProvider(
 
3141
            self._revision_id_graph)
 
3142
        graph_obj = _mod_graph.Graph(parent_provider)
 
3143
        head_cache = _mod_graph.FrozenHeadsCache(graph_obj)
 
3144
        self._heads_provider = head_cache
 
3145
        return head_cache
 
3146
 
 
3147
    def annotate(self, revision_id):
 
3148
        """Return the annotated fulltext at the given revision.
 
3149
 
 
3150
        :param revision_id: The revision id for this file
 
3151
        """
 
3152
        records = self._get_build_graph(revision_id)
 
3153
        if revision_id in self._ghosts:
 
3154
            raise errors.RevisionNotPresent(revision_id, self._knit)
 
3155
        self._annotate_records(records)
 
3156
        return self._annotated_lines[revision_id]
 
3157
 
 
3158
 
 
3159
try:
 
3160
    from bzrlib._knit_load_data_c import _load_data_c as _load_data
 
3161
except ImportError:
 
3162
    from bzrlib._knit_load_data_py import _load_data_py as _load_data