~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

merge with bzr.dev revno.1860

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2005, 2006, 2007 Canonical Ltd
 
1
# Copyright (C) 2005, 2006 by Canonical Ltd
 
2
# Written by Martin Pool.
 
3
# Modified by Johan Rydberg <jrydberg@gnu.org>
 
4
# Modified by Robert Collins <robert.collins@canonical.com>
 
5
# Modified by Aaron Bentley <aaron.bentley@utoronto.ca>
2
6
#
3
7
# This program is free software; you can redistribute it and/or modify
4
8
# it under the terms of the GNU General Public License as published by
70
74
import warnings
71
75
 
72
76
import bzrlib
73
 
from bzrlib.lazy_import import lazy_import
74
 
lazy_import(globals(), """
75
 
from bzrlib import (
76
 
    pack,
77
 
    )
78
 
""")
79
 
from bzrlib import (
80
 
    cache_utf8,
81
 
    errors,
82
 
    osutils,
83
 
    patiencediff,
84
 
    progress,
85
 
    merge,
86
 
    ui,
87
 
    )
88
 
from bzrlib.errors import (
89
 
    FileExists,
90
 
    NoSuchFile,
91
 
    KnitError,
92
 
    InvalidRevisionId,
93
 
    KnitCorrupt,
94
 
    KnitHeaderError,
95
 
    RevisionNotPresent,
96
 
    RevisionAlreadyPresent,
97
 
    )
 
77
import bzrlib.errors as errors
 
78
from bzrlib.errors import FileExists, NoSuchFile, KnitError, \
 
79
        InvalidRevisionId, KnitCorrupt, KnitHeaderError, \
 
80
        RevisionNotPresent, RevisionAlreadyPresent
98
81
from bzrlib.tuned_gzip import GzipFile
99
82
from bzrlib.trace import mutter
100
 
from bzrlib.osutils import (
101
 
    contains_whitespace,
102
 
    contains_linebreaks,
103
 
    sha_strings,
104
 
    )
 
83
from bzrlib.osutils import contains_whitespace, contains_linebreaks, \
 
84
     sha_strings
 
85
from bzrlib.versionedfile import VersionedFile, InterVersionedFile
105
86
from bzrlib.symbol_versioning import DEPRECATED_PARAMETER, deprecated_passed
106
87
from bzrlib.tsort import topo_sort
107
 
import bzrlib.ui
108
88
import bzrlib.weave
109
 
from bzrlib.versionedfile import VersionedFile, InterVersionedFile
110
89
 
111
90
 
112
91
# TODO: Split out code specific to this format into an associated object.
134
113
 
135
114
    def annotate_iter(self):
136
115
        """Yield tuples of (origin, text) for each content line."""
137
 
        return iter(self._lines)
 
116
        for origin, text in self._lines:
 
117
            yield origin, text
138
118
 
139
119
    def annotate(self):
140
120
        """Return a list of (origin, text) tuples."""
142
122
 
143
123
    def line_delta_iter(self, new_lines):
144
124
        """Generate line-based delta from this content to new_lines."""
145
 
        new_texts = new_lines.text()
146
 
        old_texts = self.text()
 
125
        new_texts = [text for origin, text in new_lines._lines]
 
126
        old_texts = [text for origin, text in self._lines]
147
127
        s = KnitSequenceMatcher(None, old_texts, new_texts)
148
 
        for tag, i1, i2, j1, j2 in s.get_opcodes():
149
 
            if tag == 'equal':
 
128
        for op in s.get_opcodes():
 
129
            if op[0] == 'equal':
150
130
                continue
151
 
            # ofrom, oto, length, data
152
 
            yield i1, i2, j2 - j1, new_lines._lines[j1:j2]
 
131
            #     ofrom   oto   length        data
 
132
            yield (op[1], op[2], op[4]-op[3], new_lines._lines[op[3]:op[4]])
153
133
 
154
134
    def line_delta(self, new_lines):
155
135
        return list(self.line_delta_iter(new_lines))
160
140
    def copy(self):
161
141
        return KnitContent(self._lines[:])
162
142
 
163
 
    @staticmethod
164
 
    def get_line_delta_blocks(knit_delta, source, target):
165
 
        """Extract SequenceMatcher.get_matching_blocks() from a knit delta"""
166
 
        target_len = len(target)
167
 
        s_pos = 0
168
 
        t_pos = 0
169
 
        for s_begin, s_end, t_len, new_text in knit_delta:
170
 
            true_n = s_begin - s_pos
171
 
            n = true_n
172
 
            if n > 0:
173
 
                # knit deltas do not provide reliable info about whether the
174
 
                # last line of a file matches, due to eol handling.
175
 
                if source[s_pos + n -1] != target[t_pos + n -1]:
176
 
                    n-=1
177
 
                if n > 0:
178
 
                    yield s_pos, t_pos, n
179
 
            t_pos += t_len + true_n
180
 
            s_pos = s_end
181
 
        n = target_len - t_pos
182
 
        if n > 0:
183
 
            if source[s_pos + n -1] != target[t_pos + n -1]:
184
 
                n-=1
185
 
            if n > 0:
186
 
                yield s_pos, t_pos, n
187
 
        yield s_pos + (target_len - t_pos), target_len, 0
188
 
 
189
143
 
190
144
class _KnitFactory(object):
191
145
    """Base factory for creating content objects."""
192
146
 
193
 
    def make(self, lines, version_id):
 
147
    def make(self, lines, version):
194
148
        num_lines = len(lines)
195
 
        return KnitContent(zip([version_id] * num_lines, lines))
 
149
        return KnitContent(zip([version] * num_lines, lines))
196
150
 
197
151
 
198
152
class KnitAnnotateFactory(_KnitFactory):
200
154
 
201
155
    annotated = True
202
156
 
203
 
    def parse_fulltext(self, content, version_id):
 
157
    def parse_fulltext(self, content, version):
204
158
        """Convert fulltext to internal representation
205
159
 
206
160
        fulltext content is of the format
208
162
        internal representation is of the format:
209
163
        (revid, plaintext)
210
164
        """
211
 
        # TODO: jam 20070209 The tests expect this to be returned as tuples,
212
 
        #       but the code itself doesn't really depend on that.
213
 
        #       Figure out a way to not require the overhead of turning the
214
 
        #       list back into tuples.
215
 
        lines = [tuple(line.split(' ', 1)) for line in content]
 
165
        lines = []
 
166
        for line in content:
 
167
            origin, text = line.split(' ', 1)
 
168
            lines.append((origin.decode('utf-8'), text))
216
169
        return KnitContent(lines)
217
170
 
218
171
    def parse_line_delta_iter(self, lines):
219
 
        return iter(self.parse_line_delta(lines))
 
172
        for result_item in self.parse_line_delta[lines]:
 
173
            yield result_item
220
174
 
221
 
    def parse_line_delta(self, lines, version_id):
 
175
    def parse_line_delta(self, lines, version):
222
176
        """Convert a line based delta into internal representation.
223
177
 
224
178
        line delta is in the form of:
231
185
        result = []
232
186
        lines = iter(lines)
233
187
        next = lines.next
234
 
 
235
 
        cache = {}
236
 
        def cache_and_return(line):
237
 
            origin, text = line.split(' ', 1)
238
 
            return cache.setdefault(origin, origin), text
239
 
 
240
188
        # walk through the lines parsing.
241
189
        for header in lines:
242
190
            start, end, count = [int(n) for n in header.split(',')]
243
 
            contents = [tuple(next().split(' ', 1)) for i in xrange(count)]
 
191
            contents = []
 
192
            remaining = count
 
193
            while remaining:
 
194
                origin, text = next().split(' ', 1)
 
195
                remaining -= 1
 
196
                contents.append((origin.decode('utf-8'), text))
244
197
            result.append((start, end, count, contents))
245
198
        return result
246
199
 
247
 
    def get_fulltext_content(self, lines):
248
 
        """Extract just the content lines from a fulltext."""
249
 
        return (line.split(' ', 1)[1] for line in lines)
250
 
 
251
 
    def get_linedelta_content(self, lines):
252
 
        """Extract just the content from a line delta.
253
 
 
254
 
        This doesn't return all of the extra information stored in a delta.
255
 
        Only the actual content lines.
256
 
        """
257
 
        lines = iter(lines)
258
 
        next = lines.next
259
 
        for header in lines:
260
 
            header = header.split(',')
261
 
            count = int(header[2])
262
 
            for i in xrange(count):
263
 
                origin, text = next().split(' ', 1)
264
 
                yield text
265
 
 
266
200
    def lower_fulltext(self, content):
267
201
        """convert a fulltext content record into a serializable form.
268
202
 
269
203
        see parse_fulltext which this inverts.
270
204
        """
271
 
        # TODO: jam 20070209 We only do the caching thing to make sure that
272
 
        #       the origin is a valid utf-8 line, eventually we could remove it
273
 
        return ['%s %s' % (o, t) for o, t in content._lines]
 
205
        return ['%s %s' % (o.encode('utf-8'), t) for o, t in content._lines]
274
206
 
275
207
    def lower_line_delta(self, delta):
276
208
        """convert a delta into a serializable form.
277
209
 
278
210
        See parse_line_delta which this inverts.
279
211
        """
280
 
        # TODO: jam 20070209 We only do the caching thing to make sure that
281
 
        #       the origin is a valid utf-8 line, eventually we could remove it
282
212
        out = []
283
213
        for start, end, c, lines in delta:
284
214
            out.append('%d,%d,%d\n' % (start, end, c))
285
 
            out.extend(origin + ' ' + text
286
 
                       for origin, text in lines)
 
215
            for origin, text in lines:
 
216
                out.append('%s %s' % (origin.encode('utf-8'), text))
287
217
        return out
288
218
 
289
219
 
292
222
 
293
223
    annotated = False
294
224
 
295
 
    def parse_fulltext(self, content, version_id):
 
225
    def parse_fulltext(self, content, version):
296
226
        """This parses an unannotated fulltext.
297
227
 
298
228
        Note that this is not a noop - the internal representation
299
229
        has (versionid, line) - its just a constant versionid.
300
230
        """
301
 
        return self.make(content, version_id)
 
231
        return self.make(content, version)
302
232
 
303
 
    def parse_line_delta_iter(self, lines, version_id):
304
 
        cur = 0
305
 
        num_lines = len(lines)
306
 
        while cur < num_lines:
307
 
            header = lines[cur]
308
 
            cur += 1
 
233
    def parse_line_delta_iter(self, lines, version):
 
234
        while lines:
 
235
            header = lines.pop(0)
309
236
            start, end, c = [int(n) for n in header.split(',')]
310
 
            yield start, end, c, zip([version_id] * c, lines[cur:cur+c])
311
 
            cur += c
312
 
 
313
 
    def parse_line_delta(self, lines, version_id):
314
 
        return list(self.parse_line_delta_iter(lines, version_id))
315
 
 
316
 
    def get_fulltext_content(self, lines):
317
 
        """Extract just the content lines from a fulltext."""
318
 
        return iter(lines)
319
 
 
320
 
    def get_linedelta_content(self, lines):
321
 
        """Extract just the content from a line delta.
322
 
 
323
 
        This doesn't return all of the extra information stored in a delta.
324
 
        Only the actual content lines.
325
 
        """
326
 
        lines = iter(lines)
327
 
        next = lines.next
328
 
        for header in lines:
329
 
            header = header.split(',')
330
 
            count = int(header[2])
331
 
            for i in xrange(count):
332
 
                yield next()
333
 
 
 
237
            yield start, end, c, zip([version] * c, lines[:c])
 
238
            del lines[:c]
 
239
 
 
240
    def parse_line_delta(self, lines, version):
 
241
        return list(self.parse_line_delta_iter(lines, version))
 
242
    
334
243
    def lower_fulltext(self, content):
335
244
        return content.text()
336
245
 
345
254
def make_empty_knit(transport, relpath):
346
255
    """Construct a empty knit at the specified location."""
347
256
    k = KnitVersionedFile(transport, relpath, 'w', KnitPlainFactory)
 
257
    k._data._open_file()
348
258
 
349
259
 
350
260
class KnitVersionedFile(VersionedFile):
362
272
    stored and retrieved.
363
273
    """
364
274
 
365
 
    def __init__(self, relpath, transport, file_mode=None, access_mode=None,
 
275
    def __init__(self, relpath, transport, file_mode=None, access_mode=None, 
366
276
                 factory=None, basis_knit=DEPRECATED_PARAMETER, delta=True,
367
 
                 create=False, create_parent_dir=False, delay_create=False,
368
 
                 dir_mode=None, index=None, access_method=None):
 
277
                 create=False):
369
278
        """Construct a knit at location specified by relpath.
370
279
        
371
280
        :param create: If not True, only open an existing knit.
372
 
        :param create_parent_dir: If True, create the parent directory if 
373
 
            creating the file fails. (This is used for stores with 
374
 
            hash-prefixes that may not exist yet)
375
 
        :param delay_create: The calling code is aware that the knit won't 
376
 
            actually be created until the first data is stored.
377
 
        :param index: An index to use for the knit.
378
281
        """
379
282
        if deprecated_passed(basis_knit):
380
283
            warnings.warn("KnitVersionedFile.__(): The basis_knit parameter is"
390
293
        self.writable = (access_mode == 'w')
391
294
        self.delta = delta
392
295
 
393
 
        self._max_delta_chain = 200
394
 
 
395
 
        if index is None:
396
 
            self._index = _KnitIndex(transport, relpath + INDEX_SUFFIX,
397
 
                access_mode, create=create, file_mode=file_mode,
398
 
                create_parent_dir=create_parent_dir, delay_create=delay_create,
399
 
                dir_mode=dir_mode)
400
 
        else:
401
 
            self._index = index
402
 
        if access_method is None:
403
 
            _access = _KnitAccess(transport, relpath + DATA_SUFFIX, file_mode, dir_mode,
404
 
                ((create and not len(self)) and delay_create), create_parent_dir)
405
 
        else:
406
 
            _access = access_method
407
 
        if create and not len(self) and not delay_create:
408
 
            _access.create()
409
 
        self._data = _KnitData(_access)
 
296
        self._index = _KnitIndex(transport, relpath + INDEX_SUFFIX,
 
297
            access_mode, create=create, file_mode=file_mode)
 
298
        self._data = _KnitData(transport, relpath + DATA_SUFFIX,
 
299
            access_mode, create=create and not len(self), file_mode=file_mode)
410
300
 
411
301
    def __repr__(self):
412
302
        return '%s(%s)' % (self.__class__.__name__, 
413
303
                           self.transport.abspath(self.filename))
414
304
    
415
 
    def _check_should_delta(self, first_parents):
416
 
        """Iterate back through the parent listing, looking for a fulltext.
417
 
 
418
 
        This is used when we want to decide whether to add a delta or a new
419
 
        fulltext. It searches for _max_delta_chain parents. When it finds a
420
 
        fulltext parent, it sees if the total size of the deltas leading up to
421
 
        it is large enough to indicate that we want a new full text anyway.
422
 
 
423
 
        Return True if we should create a new delta, False if we should use a
424
 
        full text.
425
 
        """
426
 
        delta_size = 0
427
 
        fulltext_size = None
428
 
        delta_parents = first_parents
429
 
        for count in xrange(self._max_delta_chain):
430
 
            parent = delta_parents[0]
431
 
            method = self._index.get_method(parent)
432
 
            index, pos, size = self._index.get_position(parent)
433
 
            if method == 'fulltext':
434
 
                fulltext_size = size
435
 
                break
436
 
            delta_size += size
437
 
            delta_parents = self._index.get_parents(parent)
438
 
        else:
439
 
            # We couldn't find a fulltext, so we must create a new one
440
 
            return False
441
 
 
442
 
        return fulltext_size > delta_size
443
 
 
444
305
    def _add_delta(self, version_id, parents, delta_parent, sha1, noeol, delta):
445
306
        """See VersionedFile._add_delta()."""
446
307
        self._check_add(version_id, []) # should we check the lines ?
478
339
            # To speed the extract of texts the delta chain is limited
479
340
            # to a fixed number of deltas.  This should minimize both
480
341
            # I/O and the time spend applying deltas.
481
 
            # The window was changed to a maximum of 200 deltas, but also added
482
 
            # was a check that the total compressed size of the deltas is
483
 
            # smaller than the compressed size of the fulltext.
484
 
            if not self._check_should_delta([delta_parent]):
485
 
                # We don't want a delta here, just do a normal insertion.
 
342
            count = 0
 
343
            delta_parents = [delta_parent]
 
344
            while count < 25:
 
345
                parent = delta_parents[0]
 
346
                method = self._index.get_method(parent)
 
347
                if method == 'fulltext':
 
348
                    break
 
349
                delta_parents = self._index.get_parents(parent)
 
350
                count = count + 1
 
351
            if method == 'line-delta':
 
352
                # did not find a fulltext in the delta limit.
 
353
                # just do a normal insertion.
486
354
                return super(KnitVersionedFile, self)._add_delta(version_id,
487
355
                                                                 parents,
488
356
                                                                 delta_parent,
493
361
        options.append('line-delta')
494
362
        store_lines = self.factory.lower_line_delta(delta)
495
363
 
496
 
        access_memo = self._data.add_record(version_id, digest, store_lines)
497
 
        self._index.add_version(version_id, options, access_memo, parents)
 
364
        where, size = self._data.add_record(version_id, digest, store_lines)
 
365
        self._index.add_version(version_id, options, where, size, parents)
498
366
 
499
367
    def _add_raw_records(self, records, data):
500
368
        """Add all the records 'records' with data pre-joined in 'data'.
505
373
                     the preceding records sizes.
506
374
        """
507
375
        # write all the data
508
 
        raw_record_sizes = [record[3] for record in records]
509
 
        positions = self._data.add_raw_records(raw_record_sizes, data)
510
 
        offset = 0
 
376
        pos = self._data.add_raw_record(data)
511
377
        index_entries = []
512
 
        for (version_id, options, parents, size), access_memo in zip(
513
 
            records, positions):
514
 
            index_entries.append((version_id, options, access_memo, parents))
515
 
            if self._data._do_cache:
516
 
                self._data._cache[version_id] = data[offset:offset+size]
517
 
            offset += size
 
378
        for (version_id, options, parents, size) in records:
 
379
            index_entries.append((version_id, options, pos, size, parents))
 
380
            pos += size
518
381
        self._index.add_versions(index_entries)
519
382
 
520
 
    def enable_cache(self):
521
 
        """Start caching data for this knit"""
522
 
        self._data.enable_cache()
523
 
 
524
383
    def clear_cache(self):
525
384
        """Clear the data cache only."""
526
385
        self._data.clear_cache()
529
388
        """See VersionedFile.copy_to()."""
530
389
        # copy the current index to a temp index to avoid racing with local
531
390
        # writes
532
 
        transport.put_file_non_atomic(name + INDEX_SUFFIX + '.tmp',
533
 
                self.transport.get(self._index._filename))
 
391
        transport.put(name + INDEX_SUFFIX + '.tmp', self.transport.get(self._index._filename),)
534
392
        # copy the data file
535
393
        f = self._data._open_file()
536
394
        try:
537
 
            transport.put_file(name + DATA_SUFFIX, f)
 
395
            transport.put(name + DATA_SUFFIX, f)
538
396
        finally:
539
397
            f.close()
540
398
        # move the copied index into place
541
399
        transport.move(name + INDEX_SUFFIX + '.tmp', name + INDEX_SUFFIX)
542
400
 
543
401
    def create_empty(self, name, transport, mode=None):
544
 
        return KnitVersionedFile(name, transport, factory=self.factory,
545
 
                                 delta=self.delta, create=True)
 
402
        return KnitVersionedFile(name, transport, factory=self.factory, delta=self.delta, create=True)
546
403
    
547
 
    def _fix_parents(self, version_id, new_parents):
 
404
    def _fix_parents(self, version, new_parents):
548
405
        """Fix the parents list for version.
549
406
        
550
407
        This is done by appending a new version to the index
552
409
        the parents list must be a superset of the current
553
410
        list.
554
411
        """
555
 
        current_values = self._index._cache[version_id]
 
412
        current_values = self._index._cache[version]
556
413
        assert set(current_values[4]).difference(set(new_parents)) == set()
557
 
        self._index.add_version(version_id,
558
 
                                current_values[1],
559
 
                                (None, current_values[2], current_values[3]),
 
414
        self._index.add_version(version,
 
415
                                current_values[1], 
 
416
                                current_values[2],
 
417
                                current_values[3],
560
418
                                new_parents)
561
419
 
562
 
    def _extract_blocks(self, version_id, source, target):
563
 
        if self._index.get_method(version_id) != 'line-delta':
564
 
            return None
565
 
        parent, sha1, noeol, delta = self.get_delta(version_id)
566
 
        return KnitContent.get_line_delta_blocks(delta, source, target)
567
 
 
568
420
    def get_delta(self, version_id):
569
421
        """Get a delta for constructing version from some other version."""
570
 
        version_id = osutils.safe_revision_id(version_id)
571
 
        self.check_not_reserved_id(version_id)
572
422
        if not self.has_version(version_id):
573
423
            raise RevisionNotPresent(version_id, self.filename)
574
424
        
577
427
            parent = parents[0]
578
428
        else:
579
429
            parent = None
580
 
        index_memo = self._index.get_position(version_id)
581
 
        data, sha1 = self._data.read_records(((version_id, index_memo),))[version_id]
 
430
        data_pos, data_size = self._index.get_position(version_id)
 
431
        data, sha1 = self._data.read_records(((version_id, data_pos, data_size),))[version_id]
 
432
        version_idx = self._index.lookup(version_id)
582
433
        noeol = 'no-eol' in self._index.get_options(version_id)
583
434
        if 'fulltext' == self._index.get_method(version_id):
584
 
            new_content = self.factory.parse_fulltext(data, version_id)
 
435
            new_content = self.factory.parse_fulltext(data, version_idx)
585
436
            if parent is not None:
586
437
                reference_content = self._get_content(parent)
587
438
                old_texts = reference_content.text()
591
442
            delta_seq = KnitSequenceMatcher(None, old_texts, new_texts)
592
443
            return parent, sha1, noeol, self._make_line_delta(delta_seq, new_content)
593
444
        else:
594
 
            delta = self.factory.parse_line_delta(data, version_id)
 
445
            delta = self.factory.parse_line_delta(data, version_idx)
595
446
            return parent, sha1, noeol, delta
596
447
        
597
448
    def get_graph_with_ghosts(self):
600
451
        return dict(graph_items)
601
452
 
602
453
    def get_sha1(self, version_id):
603
 
        return self.get_sha1s([version_id])[0]
604
 
 
605
 
    def get_sha1s(self, version_ids):
606
454
        """See VersionedFile.get_sha1()."""
607
 
        version_ids = [osutils.safe_revision_id(v) for v in version_ids]
608
 
        record_map = self._get_record_map(version_ids)
609
 
        # record entry 2 is the 'digest'.
610
 
        return [record_map[v][2] for v in version_ids]
 
455
        record_map = self._get_record_map([version_id])
 
456
        method, content, digest, next = record_map[version_id]
 
457
        return digest 
611
458
 
612
459
    @staticmethod
613
460
    def get_suffixes():
616
463
 
617
464
    def has_ghost(self, version_id):
618
465
        """True if there is a ghost reference in the file to version_id."""
619
 
        version_id = osutils.safe_revision_id(version_id)
620
466
        # maybe we have it
621
467
        if self.has_version(version_id):
622
468
            return False
635
481
 
636
482
    def has_version(self, version_id):
637
483
        """See VersionedFile.has_version."""
638
 
        version_id = osutils.safe_revision_id(version_id)
639
484
        return self._index.has_version(version_id)
640
485
 
641
486
    __contains__ = has_version
649
494
            delta_seq = None
650
495
            for parent_id in parents:
651
496
                merge_content = self._get_content(parent_id, parent_texts)
652
 
                seq = patiencediff.PatienceSequenceMatcher(
653
 
                                   None, merge_content.text(), content.text())
 
497
                seq = KnitSequenceMatcher(None, merge_content.text(), content.text())
654
498
                if delta_seq is None:
655
499
                    # setup a delta seq to reuse.
656
500
                    delta_seq = seq
667
511
                reference_content = self._get_content(parents[0], parent_texts)
668
512
                new_texts = content.text()
669
513
                old_texts = reference_content.text()
670
 
                delta_seq = patiencediff.PatienceSequenceMatcher(
671
 
                                                 None, old_texts, new_texts)
 
514
                delta_seq = KnitSequenceMatcher(None, old_texts, new_texts)
672
515
            return self._make_line_delta(delta_seq, content)
673
516
 
674
517
    def _make_line_delta(self, delta_seq, new_content):
702
545
                    next = None
703
546
                else:
704
547
                    next = self.get_parents(cursor)[0]
705
 
                index_memo = self._index.get_position(cursor)
706
 
                component_data[cursor] = (method, index_memo, next)
 
548
                data_pos, data_size = self._index.get_position(cursor)
 
549
                component_data[cursor] = (method, data_pos, data_size, next)
707
550
                cursor = next
708
551
        return component_data
709
552
       
722
565
 
723
566
    def _check_versions_present(self, version_ids):
724
567
        """Check that all specified versions are present."""
725
 
        self._index.check_versions_present(version_ids)
 
568
        version_ids = set(version_ids)
 
569
        for r in list(version_ids):
 
570
            if self._index.has_version(r):
 
571
                version_ids.remove(r)
 
572
        if version_ids:
 
573
            raise RevisionNotPresent(list(version_ids)[0], self.filename)
726
574
 
727
575
    def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts):
728
576
        """See VersionedFile.add_lines_with_ghosts()."""
741
589
        ### FIXME escape. RBC 20060228
742
590
        if contains_whitespace(version_id):
743
591
            raise InvalidRevisionId(version_id, self.filename)
744
 
        self.check_not_reserved_id(version_id)
745
592
        if self.has_version(version_id):
746
593
            raise RevisionAlreadyPresent(version_id, self.filename)
747
594
        self._check_lines_not_unicode(lines)
791
638
            # To speed the extract of texts the delta chain is limited
792
639
            # to a fixed number of deltas.  This should minimize both
793
640
            # I/O and the time spend applying deltas.
794
 
            delta = self._check_should_delta(present_parents)
 
641
            count = 0
 
642
            delta_parents = present_parents
 
643
            while count < 25:
 
644
                parent = delta_parents[0]
 
645
                method = self._index.get_method(parent)
 
646
                if method == 'fulltext':
 
647
                    break
 
648
                delta_parents = self._index.get_parents(parent)
 
649
                count = count + 1
 
650
            if method == 'line-delta':
 
651
                delta = False
795
652
 
796
 
        assert isinstance(version_id, str)
797
653
        lines = self.factory.make(lines, version_id)
798
654
        if delta or (self.factory.annotated and len(present_parents) > 0):
799
655
            # Merge annotations from parent texts if so is needed.
807
663
            options.append('fulltext')
808
664
            store_lines = self.factory.lower_fulltext(lines)
809
665
 
810
 
        access_memo = self._data.add_record(version_id, digest, store_lines)
811
 
        self._index.add_version(version_id, options, access_memo, parents)
 
666
        where, size = self._data.add_record(version_id, digest, store_lines)
 
667
        self._index.add_version(version_id, options, where, size, parents)
812
668
        return lines
813
669
 
814
670
    def check(self, progress_bar=None):
836
692
        If the method is fulltext, next will be None.
837
693
        """
838
694
        position_map = self._get_components_positions(version_ids)
839
 
        # c = component_id, m = method, i_m = index_memo, n = next
840
 
        records = [(c, i_m) for c, (m, i_m, n) in position_map.iteritems()]
 
695
        # c = component_id, m = method, p = position, s = size, n = next
 
696
        records = [(c, p, s) for c, (m, p, s, n) in position_map.iteritems()]
841
697
        record_map = {}
842
 
        for component_id, content, digest in \
843
 
                self._data.read_records_iter(records):
844
 
            method, index_memo, next = position_map[component_id]
 
698
        for component_id, content, digest in\
 
699
            self._data.read_records_iter(records): 
 
700
            method, position, size, next = position_map[component_id]
845
701
            record_map[component_id] = method, content, digest, next
846
702
                          
847
703
        return record_map
855
711
 
856
712
    def get_line_list(self, version_ids):
857
713
        """Return the texts of listed versions as a list of strings."""
858
 
        version_ids = [osutils.safe_revision_id(v) for v in version_ids]
859
 
        for version_id in version_ids:
860
 
            self.check_not_reserved_id(version_id)
861
714
        text_map, content_map = self._get_content_maps(version_ids)
862
715
        return [text_map[v] for v in version_ids]
863
716
 
864
 
    _get_lf_split_line_list = get_line_list
865
 
 
866
717
    def _get_content_maps(self, version_ids):
867
718
        """Produce maps of text and KnitContents
868
719
        
893
744
                if component_id in content_map:
894
745
                    content = content_map[component_id]
895
746
                else:
 
747
                    version_idx = self._index.lookup(component_id)
896
748
                    if method == 'fulltext':
897
749
                        assert content is None
898
 
                        content = self.factory.parse_fulltext(data, version_id)
 
750
                        content = self.factory.parse_fulltext(data, version_idx)
899
751
                    elif method == 'line-delta':
900
 
                        delta = self.factory.parse_line_delta(data, version_id)
 
752
                        delta = self.factory.parse_line_delta(data[:], 
 
753
                                                              version_idx)
901
754
                        content = content.copy()
902
755
                        content._lines = self._apply_delta(content._lines, 
903
756
                                                           delta)
918
771
            text_map[version_id] = text 
919
772
        return text_map, final_content 
920
773
 
921
 
    def iter_lines_added_or_present_in_versions(self, version_ids=None, 
922
 
                                                pb=None):
 
774
    def iter_lines_added_or_present_in_versions(self, version_ids=None):
923
775
        """See VersionedFile.iter_lines_added_or_present_in_versions()."""
924
776
        if version_ids is None:
925
777
            version_ids = self.versions()
926
 
        else:
927
 
            version_ids = [osutils.safe_revision_id(v) for v in version_ids]
928
 
        if pb is None:
929
 
            pb = progress.DummyProgress()
930
778
        # we don't care about inclusions, the caller cares.
931
779
        # but we need to setup a list of records to visit.
932
780
        # we need version_id, position, length
933
781
        version_id_records = []
934
 
        requested_versions = set(version_ids)
 
782
        requested_versions = list(version_ids)
935
783
        # filter for available versions
936
784
        for version_id in requested_versions:
937
785
            if not self.has_version(version_id):
938
786
                raise RevisionNotPresent(version_id, self.filename)
939
787
        # get a in-component-order queue:
 
788
        version_ids = []
940
789
        for version_id in self.versions():
941
790
            if version_id in requested_versions:
942
 
                index_memo = self._index.get_position(version_id)
943
 
                version_id_records.append((version_id, index_memo))
 
791
                version_ids.append(version_id)
 
792
                data_pos, length = self._index.get_position(version_id)
 
793
                version_id_records.append((version_id, data_pos, length))
944
794
 
 
795
        pb = bzrlib.ui.ui_factory.nested_progress_bar()
 
796
        count = 0
945
797
        total = len(version_id_records)
946
 
        for version_idx, (version_id, data, sha_value) in \
947
 
            enumerate(self._data.read_records_iter(version_id_records)):
948
 
            pb.update('Walking content.', version_idx, total)
949
 
            method = self._index.get_method(version_id)
950
 
 
951
 
            assert method in ('fulltext', 'line-delta')
952
 
            if method == 'fulltext':
953
 
                line_iterator = self.factory.get_fulltext_content(data)
954
 
            else:
955
 
                line_iterator = self.factory.get_linedelta_content(data)
956
 
            for line in line_iterator:
957
 
                yield line
958
 
 
959
 
        pb.update('Walking content.', total, total)
 
798
        try:
 
799
            pb.update('Walking content.', count, total)
 
800
            for version_id, data, sha_value in \
 
801
                self._data.read_records_iter(version_id_records):
 
802
                pb.update('Walking content.', count, total)
 
803
                method = self._index.get_method(version_id)
 
804
                version_idx = self._index.lookup(version_id)
 
805
                assert method in ('fulltext', 'line-delta')
 
806
                if method == 'fulltext':
 
807
                    content = self.factory.parse_fulltext(data, version_idx)
 
808
                    for line in content.text():
 
809
                        yield line
 
810
                else:
 
811
                    delta = self.factory.parse_line_delta(data, version_idx)
 
812
                    for start, end, count, lines in delta:
 
813
                        for origin, line in lines:
 
814
                            yield line
 
815
                count +=1
 
816
            pb.update('Walking content.', total, total)
 
817
            pb.finished()
 
818
        except:
 
819
            pb.update('Walking content.', total, total)
 
820
            pb.finished()
 
821
            raise
960
822
        
961
 
    def iter_parents(self, version_ids):
962
 
        """Iterate through the parents for many version ids.
963
 
 
964
 
        :param version_ids: An iterable yielding version_ids.
965
 
        :return: An iterator that yields (version_id, parents). Requested 
966
 
            version_ids not present in the versioned file are simply skipped.
967
 
            The order is undefined, allowing for different optimisations in
968
 
            the underlying implementation.
969
 
        """
970
 
        version_ids = [osutils.safe_revision_id(version_id) for
971
 
            version_id in version_ids]
972
 
        return self._index.iter_parents(version_ids)
973
 
 
974
823
    def num_versions(self):
975
824
        """See VersionedFile.num_versions()."""
976
825
        return self._index.num_versions()
979
828
 
980
829
    def annotate_iter(self, version_id):
981
830
        """See VersionedFile.annotate_iter."""
982
 
        version_id = osutils.safe_revision_id(version_id)
983
831
        content = self._get_content(version_id)
984
832
        for origin, text in content.annotate_iter():
985
833
            yield origin, text
989
837
        # perf notes:
990
838
        # optimism counts!
991
839
        # 52554 calls in 1264 872 internal down from 3674
992
 
        version_id = osutils.safe_revision_id(version_id)
993
840
        try:
994
841
            return self._index.get_parents(version_id)
995
842
        except KeyError:
997
844
 
998
845
    def get_parents_with_ghosts(self, version_id):
999
846
        """See VersionedFile.get_parents."""
1000
 
        version_id = osutils.safe_revision_id(version_id)
1001
847
        try:
1002
848
            return self._index.get_parents_with_ghosts(version_id)
1003
849
        except KeyError:
1004
850
            raise RevisionNotPresent(version_id, self.filename)
1005
851
 
1006
 
    def get_ancestry(self, versions, topo_sorted=True):
 
852
    def get_ancestry(self, versions):
1007
853
        """See VersionedFile.get_ancestry."""
1008
854
        if isinstance(versions, basestring):
1009
855
            versions = [versions]
1010
856
        if not versions:
1011
857
            return []
1012
 
        versions = [osutils.safe_revision_id(v) for v in versions]
1013
 
        return self._index.get_ancestry(versions, topo_sorted)
 
858
        self._check_versions_present(versions)
 
859
        return self._index.get_ancestry(versions)
1014
860
 
1015
861
    def get_ancestry_with_ghosts(self, versions):
1016
862
        """See VersionedFile.get_ancestry_with_ghosts."""
1018
864
            versions = [versions]
1019
865
        if not versions:
1020
866
            return []
1021
 
        versions = [osutils.safe_revision_id(v) for v in versions]
 
867
        self._check_versions_present(versions)
1022
868
        return self._index.get_ancestry_with_ghosts(versions)
1023
869
 
1024
870
    #@deprecated_method(zero_eight)
1031
877
        from bzrlib.weave import Weave
1032
878
 
1033
879
        w = Weave(self.filename)
1034
 
        ancestry = set(self.get_ancestry(version_ids, topo_sorted=False))
 
880
        ancestry = self.get_ancestry(version_ids)
1035
881
        sorted_graph = topo_sort(self._index.get_graph())
1036
882
        version_list = [vid for vid in sorted_graph if vid in ancestry]
1037
883
        
1044
890
 
1045
891
    def plan_merge(self, ver_a, ver_b):
1046
892
        """See VersionedFile.plan_merge."""
1047
 
        ver_a = osutils.safe_revision_id(ver_a)
1048
 
        ver_b = osutils.safe_revision_id(ver_b)
1049
 
        ancestors_b = set(self.get_ancestry(ver_b, topo_sorted=False))
 
893
        ancestors_b = set(self.get_ancestry(ver_b))
 
894
        def status_a(revision, text):
 
895
            if revision in ancestors_b:
 
896
                return 'killed-b', text
 
897
            else:
 
898
                return 'new-a', text
1050
899
        
1051
 
        ancestors_a = set(self.get_ancestry(ver_a, topo_sorted=False))
 
900
        ancestors_a = set(self.get_ancestry(ver_a))
 
901
        def status_b(revision, text):
 
902
            if revision in ancestors_a:
 
903
                return 'killed-a', text
 
904
            else:
 
905
                return 'new-b', text
 
906
 
1052
907
        annotated_a = self.annotate(ver_a)
1053
908
        annotated_b = self.annotate(ver_b)
1054
 
        return merge._plan_annotate_merge(annotated_a, annotated_b,
1055
 
                                          ancestors_a, ancestors_b)
 
909
        plain_a = [t for (a, t) in annotated_a]
 
910
        plain_b = [t for (a, t) in annotated_b]
 
911
        blocks = KnitSequenceMatcher(None, plain_a, plain_b).get_matching_blocks()
 
912
        a_cur = 0
 
913
        b_cur = 0
 
914
        for ai, bi, l in blocks:
 
915
            # process all mismatched sections
 
916
            # (last mismatched section is handled because blocks always
 
917
            # includes a 0-length last block)
 
918
            for revision, text in annotated_a[a_cur:ai]:
 
919
                yield status_a(revision, text)
 
920
            for revision, text in annotated_b[b_cur:bi]:
 
921
                yield status_b(revision, text)
 
922
 
 
923
            # and now the matched section
 
924
            a_cur = ai + l
 
925
            b_cur = bi + l
 
926
            for text_a, text_b in zip(plain_a[ai:a_cur], plain_b[bi:b_cur]):
 
927
                assert text_a == text_b
 
928
                yield "unchanged", text_a
1056
929
 
1057
930
 
1058
931
class _KnitComponentFile(object):
1059
932
    """One of the files used to implement a knit database"""
1060
933
 
1061
 
    def __init__(self, transport, filename, mode, file_mode=None,
1062
 
                 create_parent_dir=False, dir_mode=None):
 
934
    def __init__(self, transport, filename, mode, file_mode=None):
1063
935
        self._transport = transport
1064
936
        self._filename = filename
1065
937
        self._mode = mode
1066
 
        self._file_mode = file_mode
1067
 
        self._dir_mode = dir_mode
1068
 
        self._create_parent_dir = create_parent_dir
1069
 
        self._need_to_create = False
 
938
        self._file_mode=file_mode
1070
939
 
1071
 
    def _full_path(self):
1072
 
        """Return the full path to this file."""
1073
 
        return self._transport.base + self._filename
 
940
    def write_header(self):
 
941
        if self._transport.append(self._filename, StringIO(self.HEADER),
 
942
            mode=self._file_mode):
 
943
            raise KnitCorrupt(self._filename, 'misaligned after writing header')
1074
944
 
1075
945
    def check_header(self, fp):
1076
946
        line = fp.readline()
1077
 
        if line == '':
1078
 
            # An empty file can actually be treated as though the file doesn't
1079
 
            # exist yet.
1080
 
            raise errors.NoSuchFile(self._full_path())
1081
947
        if line != self.HEADER:
1082
 
            raise KnitHeaderError(badline=line,
1083
 
                              filename=self._transport.abspath(self._filename))
 
948
            raise KnitHeaderError(badline=line)
 
949
 
 
950
    def commit(self):
 
951
        """Commit is a nop."""
1084
952
 
1085
953
    def __repr__(self):
1086
954
        return '%s(%s)' % (self.__class__.__name__, self._filename)
1128
996
    The ' :' marker is the end of record marker.
1129
997
    
1130
998
    partial writes:
1131
 
    when a write is interrupted to the index file, it will result in a line
1132
 
    that does not end in ' :'. If the ' :' is not present at the end of a line,
1133
 
    or at the end of the file, then the record that is missing it will be
1134
 
    ignored by the parser.
 
999
    when a write is interrupted to the index file, it will result in a line that
 
1000
    does not end in ' :'. If the ' :' is not present at the end of a line, or at
 
1001
    the end of the file, then the record that is missing it will be ignored by
 
1002
    the parser.
1135
1003
 
1136
1004
    When writing new records to the index file, the data is preceded by '\n'
1137
1005
    to ensure that records always start on new lines even if the last write was
1146
1014
 
1147
1015
    def _cache_version(self, version_id, options, pos, size, parents):
1148
1016
        """Cache a version record in the history array and index cache.
1149
 
 
1150
 
        This is inlined into _load_data for performance. KEEP IN SYNC.
 
1017
        
 
1018
        This is inlined into __init__ for performance. KEEP IN SYNC.
1151
1019
        (It saves 60ms, 25% of the __init__ overhead on local 4000 record
1152
1020
         indexes).
1153
1021
        """
1158
1026
            self._history.append(version_id)
1159
1027
        else:
1160
1028
            index = self._cache[version_id][5]
1161
 
        self._cache[version_id] = (version_id,
 
1029
        self._cache[version_id] = (version_id, 
1162
1030
                                   options,
1163
1031
                                   pos,
1164
1032
                                   size,
1165
1033
                                   parents,
1166
1034
                                   index)
1167
1035
 
1168
 
    def __init__(self, transport, filename, mode, create=False, file_mode=None,
1169
 
                 create_parent_dir=False, delay_create=False, dir_mode=None):
1170
 
        _KnitComponentFile.__init__(self, transport, filename, mode,
1171
 
                                    file_mode=file_mode,
1172
 
                                    create_parent_dir=create_parent_dir,
1173
 
                                    dir_mode=dir_mode)
 
1036
    def __init__(self, transport, filename, mode, create=False, file_mode=None):
 
1037
        _KnitComponentFile.__init__(self, transport, filename, mode, file_mode)
1174
1038
        self._cache = {}
1175
1039
        # position in _history is the 'official' index for a revision
1176
1040
        # but the values may have come from a newer entry.
1177
1041
        # so - wc -l of a knit index is != the number of unique names
1178
1042
        # in the knit.
1179
1043
        self._history = []
 
1044
        pb = bzrlib.ui.ui_factory.nested_progress_bar()
1180
1045
        try:
1181
 
            fp = self._transport.get(self._filename)
 
1046
            count = 0
 
1047
            total = 1
1182
1048
            try:
1183
 
                # _load_data may raise NoSuchFile if the target knit is
1184
 
                # completely empty.
1185
 
                _load_data(self, fp)
1186
 
            finally:
1187
 
                fp.close()
1188
 
        except NoSuchFile:
1189
 
            if mode != 'w' or not create:
1190
 
                raise
1191
 
            elif delay_create:
1192
 
                self._need_to_create = True
 
1049
                pb.update('read knit index', count, total)
 
1050
                fp = self._transport.get(self._filename)
 
1051
                try:
 
1052
                    self.check_header(fp)
 
1053
                    # readlines reads the whole file at once:
 
1054
                    # bad for transports like http, good for local disk
 
1055
                    # we save 60 ms doing this one change (
 
1056
                    # from calling readline each time to calling
 
1057
                    # readlines once.
 
1058
                    # probably what we want for nice behaviour on
 
1059
                    # http is a incremental readlines that yields, or
 
1060
                    # a check for local vs non local indexes,
 
1061
                    for l in fp.readlines():
 
1062
                        rec = l.split()
 
1063
                        if len(rec) < 5 or rec[-1] != ':':
 
1064
                            # corrupt line.
 
1065
                            # FIXME: in the future we should determine if its a
 
1066
                            # short write - and ignore it 
 
1067
                            # or a different failure, and raise. RBC 20060407
 
1068
                            continue
 
1069
                        count += 1
 
1070
                        total += 1
 
1071
                        #pb.update('read knit index', count, total)
 
1072
                        # See self._parse_parents
 
1073
                        parents = []
 
1074
                        for value in rec[4:-1]:
 
1075
                            if '.' == value[0]:
 
1076
                                # uncompressed reference
 
1077
                                parents.append(value[1:])
 
1078
                            else:
 
1079
                                # this is 15/4000ms faster than isinstance,
 
1080
                                # (in lsprof)
 
1081
                                # this function is called thousands of times a 
 
1082
                                # second so small variations add up.
 
1083
                                assert value.__class__ is str
 
1084
                                parents.append(self._history[int(value)])
 
1085
                        # end self._parse_parents
 
1086
                        # self._cache_version(rec[0], 
 
1087
                        #                     rec[1].split(','),
 
1088
                        #                     int(rec[2]),
 
1089
                        #                     int(rec[3]),
 
1090
                        #                     parents)
 
1091
                        # --- self._cache_version
 
1092
                        # only want the _history index to reference the 1st 
 
1093
                        # index entry for version_id
 
1094
                        version_id = rec[0]
 
1095
                        if version_id not in self._cache:
 
1096
                            index = len(self._history)
 
1097
                            self._history.append(version_id)
 
1098
                        else:
 
1099
                            index = self._cache[version_id][5]
 
1100
                        self._cache[version_id] = (version_id,
 
1101
                                                   rec[1].split(','),
 
1102
                                                   int(rec[2]),
 
1103
                                                   int(rec[3]),
 
1104
                                                   parents,
 
1105
                                                   index)
 
1106
                        # --- self._cache_version 
 
1107
                finally:
 
1108
                    fp.close()
 
1109
            except NoSuchFile, e:
 
1110
                if mode != 'w' or not create:
 
1111
                    raise
 
1112
                self.write_header()
 
1113
        finally:
 
1114
            pb.update('read knit index', total, total)
 
1115
            pb.finished()
 
1116
 
 
1117
    def _parse_parents(self, compressed_parents):
 
1118
        """convert a list of string parent values into version ids.
 
1119
 
 
1120
        ints are looked up in the index.
 
1121
        .FOO values are ghosts and converted in to FOO.
 
1122
 
 
1123
        NOTE: the function is retained here for clarity, and for possible
 
1124
              use in partial index reads. However bulk processing now has
 
1125
              it inlined in __init__ for inner-loop optimisation.
 
1126
        """
 
1127
        result = []
 
1128
        for value in compressed_parents:
 
1129
            if value[-1] == '.':
 
1130
                # uncompressed reference
 
1131
                result.append(value[1:])
1193
1132
            else:
1194
 
                self._transport.put_bytes_non_atomic(
1195
 
                    self._filename, self.HEADER, mode=self._file_mode)
 
1133
                # this is 15/4000ms faster than isinstance,
 
1134
                # this function is called thousands of times a 
 
1135
                # second so small variations add up.
 
1136
                assert value.__class__ is str
 
1137
                result.append(self._history[int(value)])
 
1138
        return result
1196
1139
 
1197
1140
    def get_graph(self):
1198
 
        """Return a list of the node:parents lists from this knit index."""
1199
 
        return [(vid, idx[4]) for vid, idx in self._cache.iteritems()]
 
1141
        graph = []
 
1142
        for version_id, index in self._cache.iteritems():
 
1143
            graph.append((version_id, index[4]))
 
1144
        return graph
1200
1145
 
1201
 
    def get_ancestry(self, versions, topo_sorted=True):
 
1146
    def get_ancestry(self, versions):
1202
1147
        """See VersionedFile.get_ancestry."""
1203
1148
        # get a graph of all the mentioned versions:
1204
1149
        graph = {}
1205
1150
        pending = set(versions)
1206
 
        cache = self._cache
1207
 
        while pending:
 
1151
        while len(pending):
1208
1152
            version = pending.pop()
 
1153
            parents = self._cache[version][4]
 
1154
            # got the parents ok
1209
1155
            # trim ghosts
1210
 
            try:
1211
 
                parents = [p for p in cache[version][4] if p in cache]
1212
 
            except KeyError:
1213
 
                raise RevisionNotPresent(version, self._filename)
1214
 
            # if not completed and not a ghost
1215
 
            pending.update([p for p in parents if p not in graph])
 
1156
            parents = [parent for parent in parents if parent in self._cache]
 
1157
            for parent in parents:
 
1158
                # if not completed and not a ghost
 
1159
                if parent not in graph:
 
1160
                    pending.add(parent)
1216
1161
            graph[version] = parents
1217
 
        if not topo_sorted:
1218
 
            return graph.keys()
1219
1162
        return topo_sort(graph.items())
1220
1163
 
1221
1164
    def get_ancestry_with_ghosts(self, versions):
1222
1165
        """See VersionedFile.get_ancestry_with_ghosts."""
1223
1166
        # get a graph of all the mentioned versions:
1224
 
        self.check_versions_present(versions)
1225
 
        cache = self._cache
1226
1167
        graph = {}
1227
1168
        pending = set(versions)
1228
 
        while pending:
 
1169
        while len(pending):
1229
1170
            version = pending.pop()
1230
1171
            try:
1231
 
                parents = cache[version][4]
 
1172
                parents = self._cache[version][4]
1232
1173
            except KeyError:
1233
1174
                # ghost, fake it
1234
1175
                graph[version] = []
 
1176
                pass
1235
1177
            else:
1236
 
                # if not completed
1237
 
                pending.update([p for p in parents if p not in graph])
 
1178
                # got the parents ok
 
1179
                for parent in parents:
 
1180
                    if parent not in graph:
 
1181
                        pending.add(parent)
1238
1182
                graph[version] = parents
1239
1183
        return topo_sort(graph.items())
1240
1184
 
1241
 
    def iter_parents(self, version_ids):
1242
 
        """Iterate through the parents for many version ids.
1243
 
 
1244
 
        :param version_ids: An iterable yielding version_ids.
1245
 
        :return: An iterator that yields (version_id, parents). Requested 
1246
 
            version_ids not present in the versioned file are simply skipped.
1247
 
            The order is undefined, allowing for different optimisations in
1248
 
            the underlying implementation.
1249
 
        """
1250
 
        for version_id in version_ids:
1251
 
            try:
1252
 
                yield version_id, tuple(self.get_parents(version_id))
1253
 
            except KeyError:
1254
 
                pass
1255
 
 
1256
1185
    def num_versions(self):
1257
1186
        return len(self._history)
1258
1187
 
1259
1188
    __len__ = num_versions
1260
1189
 
1261
1190
    def get_versions(self):
1262
 
        """Get all the versions in the file. not topologically sorted."""
1263
1191
        return self._history
1264
1192
 
 
1193
    def idx_to_name(self, idx):
 
1194
        return self._history[idx]
 
1195
 
 
1196
    def lookup(self, version_id):
 
1197
        assert version_id in self._cache
 
1198
        return self._cache[version_id][5]
 
1199
 
1265
1200
    def _version_list_to_index(self, versions):
1266
1201
        result_list = []
1267
 
        cache = self._cache
1268
1202
        for version in versions:
1269
 
            if version in cache:
 
1203
            if version in self._cache:
1270
1204
                # -- inlined lookup() --
1271
 
                result_list.append(str(cache[version][5]))
 
1205
                result_list.append(str(self._cache[version][5]))
1272
1206
                # -- end lookup () --
1273
1207
            else:
1274
 
                result_list.append('.' + version)
 
1208
                result_list.append('.' + version.encode('utf-8'))
1275
1209
        return ' '.join(result_list)
1276
1210
 
1277
 
    def add_version(self, version_id, options, index_memo, parents):
 
1211
    def add_version(self, version_id, options, pos, size, parents):
1278
1212
        """Add a version record to the index."""
1279
 
        self.add_versions(((version_id, options, index_memo, parents),))
 
1213
        self.add_versions(((version_id, options, pos, size, parents),))
1280
1214
 
1281
1215
    def add_versions(self, versions):
1282
1216
        """Add multiple versions to the index.
1285
1219
                         (version_id, options, pos, size, parents).
1286
1220
        """
1287
1221
        lines = []
1288
 
        orig_history = self._history[:]
1289
 
        orig_cache = self._cache.copy()
1290
 
 
1291
 
        try:
1292
 
            for version_id, options, (index, pos, size), parents in versions:
1293
 
                line = "\n%s %s %s %s %s :" % (version_id,
1294
 
                                               ','.join(options),
1295
 
                                               pos,
1296
 
                                               size,
1297
 
                                               self._version_list_to_index(parents))
1298
 
                assert isinstance(line, str), \
1299
 
                    'content must be utf-8 encoded: %r' % (line,)
1300
 
                lines.append(line)
1301
 
                self._cache_version(version_id, options, pos, size, parents)
1302
 
            if not self._need_to_create:
1303
 
                self._transport.append_bytes(self._filename, ''.join(lines))
1304
 
            else:
1305
 
                sio = StringIO()
1306
 
                sio.write(self.HEADER)
1307
 
                sio.writelines(lines)
1308
 
                sio.seek(0)
1309
 
                self._transport.put_file_non_atomic(self._filename, sio,
1310
 
                                    create_parent_dir=self._create_parent_dir,
1311
 
                                    mode=self._file_mode,
1312
 
                                    dir_mode=self._dir_mode)
1313
 
                self._need_to_create = False
1314
 
        except:
1315
 
            # If any problems happen, restore the original values and re-raise
1316
 
            self._history = orig_history
1317
 
            self._cache = orig_cache
1318
 
            raise
1319
 
 
 
1222
        for version_id, options, pos, size, parents in versions:
 
1223
            line = "\n%s %s %s %s %s :" % (version_id.encode('utf-8'),
 
1224
                                           ','.join(options),
 
1225
                                           pos,
 
1226
                                           size,
 
1227
                                           self._version_list_to_index(parents))
 
1228
            assert isinstance(line, str), \
 
1229
                'content must be utf-8 encoded: %r' % (line,)
 
1230
            lines.append(line)
 
1231
        self._transport.append(self._filename, StringIO(''.join(lines)))
 
1232
        # cache after writing, so that a failed write leads to missing cache
 
1233
        # entries not extra ones. XXX TODO: RBC 20060502 in the event of a 
 
1234
        # failure, reload the index or flush it or some such, to prevent
 
1235
        # writing records that did complete twice.
 
1236
        for version_id, options, pos, size, parents in versions:
 
1237
            self._cache_version(version_id, options, pos, size, parents)
 
1238
        
1320
1239
    def has_version(self, version_id):
1321
1240
        """True if the version is in the index."""
1322
 
        return version_id in self._cache
 
1241
        return self._cache.has_key(version_id)
1323
1242
 
1324
1243
    def get_position(self, version_id):
1325
 
        """Return details needed to access the version.
1326
 
        
1327
 
        .kndx indices do not support split-out data, so return None for the 
1328
 
        index field.
1329
 
 
1330
 
        :return: a tuple (None, data position, size) to hand to the access
1331
 
            logic to get the record.
1332
 
        """
1333
 
        entry = self._cache[version_id]
1334
 
        return None, entry[2], entry[3]
 
1244
        """Return data position and size of specified version."""
 
1245
        return (self._cache[version_id][2], \
 
1246
                self._cache[version_id][3])
1335
1247
 
1336
1248
    def get_method(self, version_id):
1337
1249
        """Return compression method of specified version."""
1339
1251
        if 'fulltext' in options:
1340
1252
            return 'fulltext'
1341
1253
        else:
1342
 
            if 'line-delta' not in options:
1343
 
                raise errors.KnitIndexUnknownMethod(self._full_path(), options)
 
1254
            assert 'line-delta' in options
1344
1255
            return 'line-delta'
1345
1256
 
1346
1257
    def get_options(self, version_id):
1347
 
        """Return a string represention options.
1348
 
 
1349
 
        e.g. foo,bar
1350
 
        """
1351
1258
        return self._cache[version_id][1]
1352
1259
 
1353
1260
    def get_parents(self, version_id):
1361
1268
 
1362
1269
    def check_versions_present(self, version_ids):
1363
1270
        """Check that all specified versions are present."""
1364
 
        cache = self._cache
1365
 
        for version_id in version_ids:
1366
 
            if version_id not in cache:
1367
 
                raise RevisionNotPresent(version_id, self._filename)
1368
 
 
1369
 
 
1370
 
class KnitGraphIndex(object):
1371
 
    """A knit index that builds on GraphIndex."""
1372
 
 
1373
 
    def __init__(self, graph_index, deltas=False, parents=True, add_callback=None):
1374
 
        """Construct a KnitGraphIndex on a graph_index.
1375
 
 
1376
 
        :param graph_index: An implementation of bzrlib.index.GraphIndex.
1377
 
        :param deltas: Allow delta-compressed records.
1378
 
        :param add_callback: If not None, allow additions to the index and call
1379
 
            this callback with a list of added GraphIndex nodes:
1380
 
            [(node, value, node_refs), ...]
1381
 
        :param parents: If True, record knits parents, if not do not record 
1382
 
            parents.
1383
 
        """
1384
 
        self._graph_index = graph_index
1385
 
        self._deltas = deltas
1386
 
        self._add_callback = add_callback
1387
 
        self._parents = parents
1388
 
        if deltas and not parents:
1389
 
            raise KnitCorrupt(self, "Cannot do delta compression without "
1390
 
                "parent tracking.")
1391
 
 
1392
 
    def _get_entries(self, keys, check_present=False):
1393
 
        """Get the entries for keys.
1394
 
        
1395
 
        :param keys: An iterable of index keys, - 1-tuples.
1396
 
        """
1397
 
        keys = set(keys)
1398
 
        found_keys = set()
1399
 
        if self._parents:
1400
 
            for node in self._graph_index.iter_entries(keys):
1401
 
                yield node
1402
 
                found_keys.add(node[1])
1403
 
        else:
1404
 
            # adapt parentless index to the rest of the code.
1405
 
            for node in self._graph_index.iter_entries(keys):
1406
 
                yield node[0], node[1], node[2], ()
1407
 
                found_keys.add(node[1])
1408
 
        if check_present:
1409
 
            missing_keys = keys.difference(found_keys)
1410
 
            if missing_keys:
1411
 
                raise RevisionNotPresent(missing_keys.pop(), self)
1412
 
 
1413
 
    def _present_keys(self, version_ids):
1414
 
        return set([
1415
 
            node[1] for node in self._get_entries(version_ids)])
1416
 
 
1417
 
    def _parentless_ancestry(self, versions):
1418
 
        """Honour the get_ancestry API for parentless knit indices."""
1419
 
        wanted_keys = self._version_ids_to_keys(versions)
1420
 
        present_keys = self._present_keys(wanted_keys)
1421
 
        missing = set(wanted_keys).difference(present_keys)
1422
 
        if missing:
1423
 
            raise RevisionNotPresent(missing.pop(), self)
1424
 
        return list(self._keys_to_version_ids(present_keys))
1425
 
 
1426
 
    def get_ancestry(self, versions, topo_sorted=True):
1427
 
        """See VersionedFile.get_ancestry."""
1428
 
        if not self._parents:
1429
 
            return self._parentless_ancestry(versions)
1430
 
        # XXX: This will do len(history) index calls - perhaps
1431
 
        # it should be altered to be a index core feature?
1432
 
        # get a graph of all the mentioned versions:
1433
 
        graph = {}
1434
 
        ghosts = set()
1435
 
        versions = self._version_ids_to_keys(versions)
1436
 
        pending = set(versions)
1437
 
        while pending:
1438
 
            # get all pending nodes
1439
 
            this_iteration = pending
1440
 
            new_nodes = self._get_entries(this_iteration)
1441
 
            found = set()
1442
 
            pending = set()
1443
 
            for (index, key, value, node_refs) in new_nodes:
1444
 
                # dont ask for ghosties - otherwise
1445
 
                # we we can end up looping with pending
1446
 
                # being entirely ghosted.
1447
 
                graph[key] = [parent for parent in node_refs[0]
1448
 
                    if parent not in ghosts]
1449
 
                # queue parents
1450
 
                for parent in graph[key]:
1451
 
                    # dont examine known nodes again
1452
 
                    if parent in graph:
1453
 
                        continue
1454
 
                    pending.add(parent)
1455
 
                found.add(key)
1456
 
            ghosts.update(this_iteration.difference(found))
1457
 
        if versions.difference(graph):
1458
 
            raise RevisionNotPresent(versions.difference(graph).pop(), self)
1459
 
        if topo_sorted:
1460
 
            result_keys = topo_sort(graph.items())
1461
 
        else:
1462
 
            result_keys = graph.iterkeys()
1463
 
        return [key[0] for key in result_keys]
1464
 
 
1465
 
    def get_ancestry_with_ghosts(self, versions):
1466
 
        """See VersionedFile.get_ancestry."""
1467
 
        if not self._parents:
1468
 
            return self._parentless_ancestry(versions)
1469
 
        # XXX: This will do len(history) index calls - perhaps
1470
 
        # it should be altered to be a index core feature?
1471
 
        # get a graph of all the mentioned versions:
1472
 
        graph = {}
1473
 
        versions = self._version_ids_to_keys(versions)
1474
 
        pending = set(versions)
1475
 
        while pending:
1476
 
            # get all pending nodes
1477
 
            this_iteration = pending
1478
 
            new_nodes = self._get_entries(this_iteration)
1479
 
            pending = set()
1480
 
            for (index, key, value, node_refs) in new_nodes:
1481
 
                graph[key] = node_refs[0]
1482
 
                # queue parents 
1483
 
                for parent in graph[key]:
1484
 
                    # dont examine known nodes again
1485
 
                    if parent in graph:
1486
 
                        continue
1487
 
                    pending.add(parent)
1488
 
            missing_versions = this_iteration.difference(graph)
1489
 
            missing_needed = versions.intersection(missing_versions)
1490
 
            if missing_needed:
1491
 
                raise RevisionNotPresent(missing_needed.pop(), self)
1492
 
            for missing_version in missing_versions:
1493
 
                # add a key, no parents
1494
 
                graph[missing_version] = []
1495
 
                pending.discard(missing_version) # don't look for it
1496
 
        result_keys = topo_sort(graph.items())
1497
 
        return [key[0] for key in result_keys]
1498
 
 
1499
 
    def get_graph(self):
1500
 
        """Return a list of the node:parents lists from this knit index."""
1501
 
        if not self._parents:
1502
 
            return [(key, ()) for key in self.get_versions()]
1503
 
        result = []
1504
 
        for index, key, value, refs in self._graph_index.iter_all_entries():
1505
 
            result.append((key[0], tuple([ref[0] for ref in refs[0]])))
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
 
        if self._parents:
1518
 
            all_nodes = set(self._get_entries(self._version_ids_to_keys(version_ids)))
1519
 
            all_parents = set()
1520
 
            present_parents = set()
1521
 
            for node in all_nodes:
1522
 
                all_parents.update(node[3][0])
1523
 
                # any node we are querying must be present
1524
 
                present_parents.add(node[1])
1525
 
            unknown_parents = all_parents.difference(present_parents)
1526
 
            present_parents.update(self._present_keys(unknown_parents))
1527
 
            for node in all_nodes:
1528
 
                parents = []
1529
 
                for parent in node[3][0]:
1530
 
                    if parent in present_parents:
1531
 
                        parents.append(parent[0])
1532
 
                yield node[1][0], tuple(parents)
1533
 
        else:
1534
 
            for node in self._get_entries(self._version_ids_to_keys(version_ids)):
1535
 
                yield node[1][0], ()
1536
 
 
1537
 
    def num_versions(self):
1538
 
        return len(list(self._graph_index.iter_all_entries()))
1539
 
 
1540
 
    __len__ = num_versions
1541
 
 
1542
 
    def get_versions(self):
1543
 
        """Get all the versions in the file. not topologically sorted."""
1544
 
        return [node[1][0] for node in self._graph_index.iter_all_entries()]
1545
 
    
1546
 
    def has_version(self, version_id):
1547
 
        """True if the version is in the index."""
1548
 
        return len(self._present_keys(self._version_ids_to_keys([version_id]))) == 1
1549
 
 
1550
 
    def _keys_to_version_ids(self, keys):
1551
 
        return tuple(key[0] for key in keys)
1552
 
 
1553
 
    def get_position(self, version_id):
1554
 
        """Return details needed to access the version.
1555
 
        
1556
 
        :return: a tuple (index, data position, size) to hand to the access
1557
 
            logic to get the record.
1558
 
        """
1559
 
        node = self._get_node(version_id)
1560
 
        bits = node[2][1:].split(' ')
1561
 
        return node[0], int(bits[0]), int(bits[1])
1562
 
 
1563
 
    def get_method(self, version_id):
1564
 
        """Return compression method of specified version."""
1565
 
        if not self._deltas:
1566
 
            return 'fulltext'
1567
 
        return self._parent_compression(self._get_node(version_id)[3][1])
1568
 
 
1569
 
    def _parent_compression(self, reference_list):
1570
 
        # use the second reference list to decide if this is delta'd or not.
1571
 
        if len(reference_list):
1572
 
            return 'line-delta'
1573
 
        else:
1574
 
            return 'fulltext'
1575
 
 
1576
 
    def _get_node(self, version_id):
1577
 
        return list(self._get_entries(self._version_ids_to_keys([version_id])))[0]
1578
 
 
1579
 
    def get_options(self, version_id):
1580
 
        """Return a string represention options.
1581
 
 
1582
 
        e.g. foo,bar
1583
 
        """
1584
 
        node = self._get_node(version_id)
1585
 
        if not self._deltas:
1586
 
            options = ['fulltext']
1587
 
        else:
1588
 
            options = [self._parent_compression(node[3][1])]
1589
 
        if node[2][0] == 'N':
1590
 
            options.append('no-eol')
1591
 
        return options
1592
 
 
1593
 
    def get_parents(self, version_id):
1594
 
        """Return parents of specified version ignoring ghosts."""
1595
 
        parents = list(self.iter_parents([version_id]))
1596
 
        if not parents:
1597
 
            # missing key
1598
 
            raise errors.RevisionNotPresent(version_id, self)
1599
 
        return parents[0][1]
1600
 
 
1601
 
    def get_parents_with_ghosts(self, version_id):
1602
 
        """Return parents of specified version with ghosts."""
1603
 
        nodes = list(self._get_entries(self._version_ids_to_keys([version_id]),
1604
 
            check_present=True))
1605
 
        if not self._parents:
1606
 
            return ()
1607
 
        return self._keys_to_version_ids(nodes[0][3][0])
1608
 
 
1609
 
    def check_versions_present(self, version_ids):
1610
 
        """Check that all specified versions are present."""
1611
 
        keys = self._version_ids_to_keys(version_ids)
1612
 
        present = self._present_keys(keys)
1613
 
        missing = keys.difference(present)
1614
 
        if missing:
1615
 
            raise RevisionNotPresent(missing.pop(), self)
1616
 
 
1617
 
    def add_version(self, version_id, options, access_memo, parents):
1618
 
        """Add a version record to the index."""
1619
 
        return self.add_versions(((version_id, options, access_memo, parents),))
1620
 
 
1621
 
    def add_versions(self, versions):
1622
 
        """Add multiple versions to the index.
1623
 
        
1624
 
        This function does not insert data into the Immutable GraphIndex
1625
 
        backing the KnitGraphIndex, instead it prepares data for insertion by
1626
 
        the caller and checks that it is safe to insert then calls
1627
 
        self._add_callback with the prepared GraphIndex nodes.
1628
 
 
1629
 
        :param versions: a list of tuples:
1630
 
                         (version_id, options, pos, size, parents).
1631
 
        """
1632
 
        if not self._add_callback:
1633
 
            raise errors.ReadOnlyError(self)
1634
 
        # we hope there are no repositories with inconsistent parentage
1635
 
        # anymore.
1636
 
        # check for dups
1637
 
 
1638
 
        keys = {}
1639
 
        for (version_id, options, access_memo, parents) in versions:
1640
 
            index, pos, size = access_memo
1641
 
            key = (version_id, )
1642
 
            parents = tuple((parent, ) for parent in parents)
1643
 
            if 'no-eol' in options:
1644
 
                value = 'N'
1645
 
            else:
1646
 
                value = ' '
1647
 
            value += "%d %d" % (pos, size)
1648
 
            if not self._deltas:
1649
 
                if 'line-delta' in options:
1650
 
                    raise KnitCorrupt(self, "attempt to add line-delta in non-delta knit")
1651
 
            if self._parents:
1652
 
                if self._deltas:
1653
 
                    if 'line-delta' in options:
1654
 
                        node_refs = (parents, (parents[0],))
1655
 
                    else:
1656
 
                        node_refs = (parents, ())
1657
 
                else:
1658
 
                    node_refs = (parents, )
1659
 
            else:
1660
 
                if parents:
1661
 
                    raise KnitCorrupt(self, "attempt to add node with parents "
1662
 
                        "in parentless index.")
1663
 
                node_refs = ()
1664
 
            keys[key] = (value, node_refs)
1665
 
        present_nodes = self._get_entries(keys)
1666
 
        for (index, key, value, node_refs) in present_nodes:
1667
 
            if (value, node_refs) != keys[key]:
1668
 
                raise KnitCorrupt(self, "inconsistent details in add_versions"
1669
 
                    ": %s %s" % ((value, node_refs), keys[key]))
1670
 
            del keys[key]
1671
 
        result = []
1672
 
        if self._parents:
1673
 
            for key, (value, node_refs) in keys.iteritems():
1674
 
                result.append((key, value, node_refs))
1675
 
        else:
1676
 
            for key, (value, node_refs) in keys.iteritems():
1677
 
                result.append((key, value))
1678
 
        self._add_callback(result)
1679
 
        
1680
 
    def _version_ids_to_keys(self, version_ids):
1681
 
        return set((version_id, ) for version_id in version_ids)
1682
 
 
1683
 
 
1684
 
class _KnitAccess(object):
1685
 
    """Access to knit records in a .knit file."""
1686
 
 
1687
 
    def __init__(self, transport, filename, _file_mode, _dir_mode,
1688
 
        _need_to_create, _create_parent_dir):
1689
 
        """Create a _KnitAccess for accessing and inserting data.
1690
 
 
1691
 
        :param transport: The transport the .knit is located on.
1692
 
        :param filename: The filename of the .knit.
1693
 
        """
1694
 
        self._transport = transport
1695
 
        self._filename = filename
1696
 
        self._file_mode = _file_mode
1697
 
        self._dir_mode = _dir_mode
1698
 
        self._need_to_create = _need_to_create
1699
 
        self._create_parent_dir = _create_parent_dir
1700
 
 
1701
 
    def add_raw_records(self, sizes, raw_data):
1702
 
        """Add raw knit bytes to a storage area.
1703
 
 
1704
 
        The data is spooled to whereever the access method is storing data.
1705
 
 
1706
 
        :param sizes: An iterable containing the size of each raw data segment.
1707
 
        :param raw_data: A bytestring containing the data.
1708
 
        :return: A list of memos to retrieve the record later. Each memo is a
1709
 
            tuple - (index, pos, length), where the index field is always None
1710
 
            for the .knit access method.
1711
 
        """
1712
 
        assert type(raw_data) == str, \
1713
 
            'data must be plain bytes was %s' % type(raw_data)
1714
 
        if not self._need_to_create:
1715
 
            base = self._transport.append_bytes(self._filename, raw_data)
1716
 
        else:
1717
 
            self._transport.put_bytes_non_atomic(self._filename, raw_data,
1718
 
                                   create_parent_dir=self._create_parent_dir,
1719
 
                                   mode=self._file_mode,
1720
 
                                   dir_mode=self._dir_mode)
1721
 
            self._need_to_create = False
1722
 
            base = 0
1723
 
        result = []
1724
 
        for size in sizes:
1725
 
            result.append((None, base, size))
1726
 
            base += size
1727
 
        return result
1728
 
 
1729
 
    def create(self):
1730
 
        """IFF this data access has its own storage area, initialise it.
1731
 
 
1732
 
        :return: None.
1733
 
        """
1734
 
        self._transport.put_bytes_non_atomic(self._filename, '',
1735
 
                                             mode=self._file_mode)
1736
 
 
1737
 
    def open_file(self):
1738
 
        """IFF this data access can be represented as a single file, open it.
1739
 
 
1740
 
        For knits that are not mapped to a single file on disk this will
1741
 
        always return None.
1742
 
 
1743
 
        :return: None or a file handle.
1744
 
        """
1745
 
        try:
1746
 
            return self._transport.get(self._filename)
1747
 
        except NoSuchFile:
1748
 
            pass
1749
 
        return None
1750
 
 
1751
 
    def get_raw_records(self, memos_for_retrieval):
1752
 
        """Get the raw bytes for a records.
1753
 
 
1754
 
        :param memos_for_retrieval: An iterable containing the (index, pos, 
1755
 
            length) memo for retrieving the bytes. The .knit method ignores
1756
 
            the index as there is always only a single file.
1757
 
        :return: An iterator over the bytes of the records.
1758
 
        """
1759
 
        read_vector = [(pos, size) for (index, pos, size) in memos_for_retrieval]
1760
 
        for pos, data in self._transport.readv(self._filename, read_vector):
1761
 
            yield data
1762
 
 
1763
 
 
1764
 
class _PackAccess(object):
1765
 
    """Access to knit records via a collection of packs."""
1766
 
 
1767
 
    def __init__(self, index_to_packs, writer=None):
1768
 
        """Create a _PackAccess object.
1769
 
 
1770
 
        :param index_to_packs: A dict mapping index objects to the transport
1771
 
            and file names for obtaining data.
1772
 
        :param writer: A tuple (pack.ContainerWriter, write_index) which
1773
 
            is contains the pack to write, and the index that reads from
1774
 
            it will be associated with.
1775
 
        """
1776
 
        if writer:
1777
 
            self.container_writer = writer[0]
1778
 
            self.write_index = writer[1]
1779
 
        else:
1780
 
            self.container_writer = None
1781
 
            self.write_index = None
1782
 
        self.indices = index_to_packs
1783
 
 
1784
 
    def add_raw_records(self, sizes, raw_data):
1785
 
        """Add raw knit bytes to a storage area.
1786
 
 
1787
 
        The data is spooled to the container writer in one bytes record per
1788
 
        raw data item.
1789
 
 
1790
 
        :param sizes: An iterable containing the size of each raw data segment.
1791
 
        :param raw_data: A bytestring containing the data.
1792
 
        :return: A list of memos to retrieve the record later. Each memo is a
1793
 
            tuple - (index, pos, length), where the index field is the 
1794
 
            write_index object supplied to the PackAccess object.
1795
 
        """
1796
 
        assert type(raw_data) == str, \
1797
 
            'data must be plain bytes was %s' % type(raw_data)
1798
 
        result = []
1799
 
        offset = 0
1800
 
        for size in sizes:
1801
 
            p_offset, p_length = self.container_writer.add_bytes_record(
1802
 
                raw_data[offset:offset+size], [])
1803
 
            offset += size
1804
 
            result.append((self.write_index, p_offset, p_length))
1805
 
        return result
1806
 
 
1807
 
    def create(self):
1808
 
        """Pack based knits do not get individually created."""
1809
 
 
1810
 
    def get_raw_records(self, memos_for_retrieval):
1811
 
        """Get the raw bytes for a records.
1812
 
 
1813
 
        :param memos_for_retrieval: An iterable containing the (index, pos, 
1814
 
            length) memo for retrieving the bytes. The Pack access method
1815
 
            looks up the pack to use for a given record in its index_to_pack
1816
 
            map.
1817
 
        :return: An iterator over the bytes of the records.
1818
 
        """
1819
 
        # first pass, group into same-index requests
1820
 
        request_lists = []
1821
 
        current_index = None
1822
 
        for (index, offset, length) in memos_for_retrieval:
1823
 
            if current_index == index:
1824
 
                current_list.append((offset, length))
1825
 
            else:
1826
 
                if current_index is not None:
1827
 
                    request_lists.append((current_index, current_list))
1828
 
                current_index = index
1829
 
                current_list = [(offset, length)]
1830
 
        # handle the last entry
1831
 
        if current_index is not None:
1832
 
            request_lists.append((current_index, current_list))
1833
 
        for index, offsets in request_lists:
1834
 
            transport, path = self.indices[index]
1835
 
            reader = pack.make_readv_reader(transport, path, offsets)
1836
 
            for names, read_func in reader.iter_records():
1837
 
                yield read_func(None)
1838
 
 
1839
 
    def open_file(self):
1840
 
        """Pack based knits have no single file."""
1841
 
        return None
1842
 
 
1843
 
    def set_writer(self, writer, index, (transport, packname)):
1844
 
        """Set a writer to use for adding data."""
1845
 
        self.indices[index] = (transport, packname)
1846
 
        self.container_writer = writer
1847
 
        self.write_index = index
1848
 
 
1849
 
 
1850
 
class _KnitData(object):
1851
 
    """Manage extraction of data from a KnitAccess, caching and decompressing.
1852
 
    
1853
 
    The KnitData class provides the logic for parsing and using knit records,
1854
 
    making use of an access method for the low level read and write operations.
1855
 
    """
1856
 
 
1857
 
    def __init__(self, access):
1858
 
        """Create a KnitData object.
1859
 
 
1860
 
        :param access: The access method to use. Access methods such as
1861
 
            _KnitAccess manage the insertion of raw records and the subsequent
1862
 
            retrieval of the same.
1863
 
        """
1864
 
        self._access = access
 
1271
        version_ids = set(version_ids)
 
1272
        for version_id in list(version_ids):
 
1273
            if version_id in self._cache:
 
1274
                version_ids.remove(version_id)
 
1275
        if version_ids:
 
1276
            raise RevisionNotPresent(list(version_ids)[0], self.filename)
 
1277
 
 
1278
 
 
1279
class _KnitData(_KnitComponentFile):
 
1280
    """Contents of the knit data file"""
 
1281
 
 
1282
    HEADER = "# bzr knit data 8\n"
 
1283
 
 
1284
    def __init__(self, transport, filename, mode, create=False, file_mode=None):
 
1285
        _KnitComponentFile.__init__(self, transport, filename, mode)
1865
1286
        self._checked = False
1866
 
        # TODO: jam 20060713 conceptually, this could spill to disk
1867
 
        #       if the cached size gets larger than a certain amount
1868
 
        #       but it complicates the model a bit, so for now just use
1869
 
        #       a simple dictionary
1870
 
        self._cache = {}
1871
 
        self._do_cache = False
1872
 
 
1873
 
    def enable_cache(self):
1874
 
        """Enable caching of reads."""
1875
 
        self._do_cache = True
 
1287
        if create:
 
1288
            self._transport.put(self._filename, StringIO(''), mode=file_mode)
1876
1289
 
1877
1290
    def clear_cache(self):
1878
1291
        """Clear the record cache."""
1879
 
        self._do_cache = False
1880
 
        self._cache = {}
 
1292
        pass
1881
1293
 
1882
1294
    def _open_file(self):
1883
 
        return self._access.open_file()
 
1295
        try:
 
1296
            return self._transport.get(self._filename)
 
1297
        except NoSuchFile:
 
1298
            pass
 
1299
        return None
1884
1300
 
1885
1301
    def _record_to_data(self, version_id, digest, lines):
1886
1302
        """Convert version_id, digest, lines into a raw data block.
1889
1305
        """
1890
1306
        sio = StringIO()
1891
1307
        data_file = GzipFile(None, mode='wb', fileobj=sio)
1892
 
 
1893
 
        assert isinstance(version_id, str)
1894
1308
        data_file.writelines(chain(
1895
 
            ["version %s %d %s\n" % (version_id,
 
1309
            ["version %s %d %s\n" % (version_id.encode('utf-8'), 
1896
1310
                                     len(lines),
1897
1311
                                     digest)],
1898
1312
            lines,
1899
 
            ["end %s\n" % version_id]))
 
1313
            ["end %s\n" % version_id.encode('utf-8')]))
1900
1314
        data_file.close()
1901
1315
        length= sio.tell()
1902
1316
 
1903
1317
        sio.seek(0)
1904
1318
        return length, sio
1905
1319
 
1906
 
    def add_raw_records(self, sizes, raw_data):
 
1320
    def add_raw_record(self, raw_data):
1907
1321
        """Append a prepared record to the data file.
1908
1322
        
1909
 
        :param sizes: An iterable containing the size of each raw data segment.
1910
 
        :param raw_data: A bytestring containing the data.
1911
 
        :return: a list of index data for the way the data was stored.
1912
 
            See the access method add_raw_records documentation for more
1913
 
            details.
 
1323
        :return: the offset in the data file raw_data was written.
1914
1324
        """
1915
 
        return self._access.add_raw_records(sizes, raw_data)
 
1325
        assert isinstance(raw_data, str), 'data must be plain bytes'
 
1326
        return self._transport.append(self._filename, StringIO(raw_data))
1916
1327
        
1917
1328
    def add_record(self, version_id, digest, lines):
1918
 
        """Write new text record to disk. 
1919
 
        
1920
 
        Returns index data for retrieving it later, as per add_raw_records.
1921
 
        """
 
1329
        """Write new text record to disk.  Returns the position in the
 
1330
        file where it was written."""
1922
1331
        size, sio = self._record_to_data(version_id, digest, lines)
1923
 
        result = self.add_raw_records([size], sio.getvalue())
1924
 
        if self._do_cache:
1925
 
            self._cache[version_id] = sio.getvalue()
1926
 
        return result[0]
 
1332
        # write to disk
 
1333
        start_pos = self._transport.append(self._filename, sio)
 
1334
        return start_pos, size
1927
1335
 
1928
1336
    def _parse_record_header(self, version_id, raw_data):
1929
1337
        """Parse a record header for consistency.
1932
1340
                 as (stream, header_record)
1933
1341
        """
1934
1342
        df = GzipFile(mode='rb', fileobj=StringIO(raw_data))
1935
 
        try:
1936
 
            rec = self._check_header(version_id, df.readline())
1937
 
        except Exception, e:
1938
 
            raise KnitCorrupt(self._access,
1939
 
                              "While reading {%s} got %s(%s)"
1940
 
                              % (version_id, e.__class__.__name__, str(e)))
 
1343
        rec = df.readline().split()
 
1344
        if len(rec) != 4:
 
1345
            raise KnitCorrupt(self._filename, 'unexpected number of elements in record header')
 
1346
        if rec[1].decode('utf-8')!= version_id:
 
1347
            raise KnitCorrupt(self._filename, 
 
1348
                              'unexpected version, wanted %r, got %r' % (
 
1349
                                version_id, rec[1]))
1941
1350
        return df, rec
1942
1351
 
1943
 
    def _check_header(self, version_id, line):
1944
 
        rec = line.split()
1945
 
        if len(rec) != 4:
1946
 
            raise KnitCorrupt(self._access,
1947
 
                              'unexpected number of elements in record header')
1948
 
        if rec[1] != version_id:
1949
 
            raise KnitCorrupt(self._access,
1950
 
                              'unexpected version, wanted %r, got %r'
1951
 
                              % (version_id, rec[1]))
1952
 
        return rec
1953
 
 
1954
1352
    def _parse_record(self, version_id, data):
1955
1353
        # profiling notes:
1956
1354
        # 4168 calls in 2880 217 internal
1957
1355
        # 4168 calls to _parse_record_header in 2121
1958
1356
        # 4168 calls to readlines in 330
1959
 
        df = GzipFile(mode='rb', fileobj=StringIO(data))
1960
 
 
1961
 
        try:
1962
 
            record_contents = df.readlines()
1963
 
        except Exception, e:
1964
 
            raise KnitCorrupt(self._access,
1965
 
                              "While reading {%s} got %s(%s)"
1966
 
                              % (version_id, e.__class__.__name__, str(e)))
1967
 
        header = record_contents.pop(0)
1968
 
        rec = self._check_header(version_id, header)
1969
 
 
1970
 
        last_line = record_contents.pop()
1971
 
        if len(record_contents) != int(rec[2]):
1972
 
            raise KnitCorrupt(self._access,
1973
 
                              'incorrect number of lines %s != %s'
1974
 
                              ' for version {%s}'
1975
 
                              % (len(record_contents), int(rec[2]),
1976
 
                                 version_id))
1977
 
        if last_line != 'end %s\n' % rec[1]:
1978
 
            raise KnitCorrupt(self._access,
1979
 
                              'unexpected version end line %r, wanted %r' 
1980
 
                              % (last_line, version_id))
 
1357
        df, rec = self._parse_record_header(version_id, data)
 
1358
        record_contents = df.readlines()
 
1359
        l = record_contents.pop()
 
1360
        assert len(record_contents) == int(rec[2])
 
1361
        if l.decode('utf-8') != 'end %s\n' % version_id:
 
1362
            raise KnitCorrupt(self._filename, 'unexpected version end line %r, wanted %r' 
 
1363
                        % (l, version_id))
1981
1364
        df.close()
1982
1365
        return record_contents, rec[3]
1983
1366
 
1986
1369
 
1987
1370
        This unpacks enough of the text record to validate the id is
1988
1371
        as expected but thats all.
 
1372
 
 
1373
        It will actively recompress currently cached records on the
 
1374
        basis that that is cheaper than I/O activity.
1989
1375
        """
1990
1376
        # setup an iterator of the external records:
1991
1377
        # uses readv so nice and fast we hope.
1992
1378
        if len(records):
1993
1379
            # grab the disk data needed.
1994
 
            if self._cache:
1995
 
                # Don't check _cache if it is empty
1996
 
                needed_offsets = [index_memo for version_id, index_memo
1997
 
                                              in records
1998
 
                                              if version_id not in self._cache]
1999
 
            else:
2000
 
                needed_offsets = [index_memo for version_id, index_memo
2001
 
                                               in records]
2002
 
 
2003
 
            raw_records = self._access.get_raw_records(needed_offsets)
2004
 
 
2005
 
        for version_id, index_memo in records:
2006
 
            if version_id in self._cache:
2007
 
                # This data has already been validated
2008
 
                data = self._cache[version_id]
2009
 
            else:
2010
 
                data = raw_records.next()
2011
 
                if self._do_cache:
2012
 
                    self._cache[version_id] = data
2013
 
 
2014
 
                # validate the header
2015
 
                df, rec = self._parse_record_header(version_id, data)
2016
 
                df.close()
 
1380
            raw_records = self._transport.readv(self._filename,
 
1381
                [(pos, size) for version_id, pos, size in records])
 
1382
 
 
1383
        for version_id, pos, size in records:
 
1384
            pos, data = raw_records.next()
 
1385
            # validate the header
 
1386
            df, rec = self._parse_record_header(version_id, data)
 
1387
            df.close()
2017
1388
            yield version_id, data
2018
1389
 
2019
1390
    def read_records_iter(self, records):
2020
1391
        """Read text records from data file and yield result.
2021
1392
 
2022
 
        The result will be returned in whatever is the fastest to read.
2023
 
        Not by the order requested. Also, multiple requests for the same
2024
 
        record will only yield 1 response.
2025
 
        :param records: A list of (version_id, pos, len) entries
2026
 
        :return: Yields (version_id, contents, digest) in the order
2027
 
                 read, not the order requested
 
1393
        Each passed record is a tuple of (version_id, pos, len) and
 
1394
        will be read in the given order.  Yields (version_id,
 
1395
        contents, digest).
2028
1396
        """
2029
 
        if not records:
2030
 
            return
2031
 
 
2032
 
        if self._cache:
2033
 
            # Skip records we have alread seen
2034
 
            yielded_records = set()
2035
 
            needed_records = set()
2036
 
            for record in records:
2037
 
                if record[0] in self._cache:
2038
 
                    if record[0] in yielded_records:
2039
 
                        continue
2040
 
                    yielded_records.add(record[0])
2041
 
                    data = self._cache[record[0]]
2042
 
                    content, digest = self._parse_record(record[0], data)
2043
 
                    yield (record[0], content, digest)
2044
 
                else:
2045
 
                    needed_records.add(record)
2046
 
            needed_records = sorted(needed_records, key=operator.itemgetter(1))
2047
 
        else:
2048
 
            needed_records = sorted(set(records), key=operator.itemgetter(1))
2049
 
 
2050
 
        if not needed_records:
2051
 
            return
2052
 
 
2053
 
        # The transport optimizes the fetching as well 
2054
 
        # (ie, reads continuous ranges.)
2055
 
        raw_data = self._access.get_raw_records(
2056
 
            [index_memo for version_id, index_memo in needed_records])
2057
 
 
2058
 
        for (version_id, index_memo), data in \
2059
 
                izip(iter(needed_records), raw_data):
2060
 
            content, digest = self._parse_record(version_id, data)
2061
 
            if self._do_cache:
2062
 
                self._cache[version_id] = data
 
1397
        if len(records) == 0:
 
1398
            return
 
1399
        # profiling notes:
 
1400
        # 60890  calls for 4168 extractions in 5045, 683 internal.
 
1401
        # 4168   calls to readv              in 1411
 
1402
        # 4168   calls to parse_record       in 2880
 
1403
 
 
1404
        # Get unique records, sorted by position
 
1405
        needed_records = sorted(set(records), key=operator.itemgetter(1))
 
1406
 
 
1407
        # We take it that the transport optimizes the fetching as good
 
1408
        # as possible (ie, reads continuous ranges.)
 
1409
        response = self._transport.readv(self._filename,
 
1410
            [(pos, size) for version_id, pos, size in needed_records])
 
1411
 
 
1412
        record_map = {}
 
1413
        for (record_id, pos, size), (pos, data) in \
 
1414
            izip(iter(needed_records), response):
 
1415
            content, digest = self._parse_record(record_id, data)
 
1416
            record_map[record_id] = (digest, content)
 
1417
 
 
1418
        for version_id, pos, size in records:
 
1419
            digest, content = record_map[version_id]
2063
1420
            yield version_id, content, digest
2064
1421
 
2065
1422
    def read_records(self, records):
2066
1423
        """Read records into a dictionary."""
2067
1424
        components = {}
2068
 
        for record_id, content, digest in \
2069
 
                self.read_records_iter(records):
 
1425
        for record_id, content, digest in self.read_records_iter(records):
2070
1426
            components[record_id] = (content, digest)
2071
1427
        return components
2072
1428
 
2096
1452
        if not version_ids:
2097
1453
            return 0
2098
1454
 
2099
 
        pb = ui.ui_factory.nested_progress_bar()
 
1455
        pb = bzrlib.ui.ui_factory.nested_progress_bar()
2100
1456
        try:
2101
1457
            version_ids = list(version_ids)
2102
1458
            if None in version_ids:
2151
1507
                    assert (self.target.has_version(parent) or
2152
1508
                            parent in copy_set or
2153
1509
                            not self.source.has_version(parent))
2154
 
                index_memo = self.source._index.get_position(version_id)
2155
 
                copy_queue_records.append((version_id, index_memo))
 
1510
                data_pos, data_size = self.source._index.get_position(version_id)
 
1511
                copy_queue_records.append((version_id, data_pos, data_size))
2156
1512
                copy_queue.append((version_id, options, parents))
2157
1513
                copy_set.add(version_id)
2158
1514
 
2213
1569
        if not version_ids:
2214
1570
            return 0
2215
1571
 
2216
 
        pb = ui.ui_factory.nested_progress_bar()
 
1572
        pb = bzrlib.ui.ui_factory.nested_progress_bar()
2217
1573
        try:
2218
1574
            version_ids = list(version_ids)
2219
1575
    
2414
1770
 
2415
1771
        return besti, bestj, bestsize
2416
1772
 
2417
 
 
2418
 
try:
2419
 
    from bzrlib._knit_load_data_c import _load_data_c as _load_data
2420
 
except ImportError:
2421
 
    from bzrlib._knit_load_data_py import _load_data_py as _load_data