/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to breezy/bzr/versionedfile.py

  • Committer: Jelmer Vernooij
  • Date: 2020-09-02 15:11:17 UTC
  • mto: (7490.40.109 work)
  • mto: This revision was merged to the branch mainline in revision 7526.
  • Revision ID: jelmer@jelmer.uk-20200902151117-jeu7tarbz3dkuju0
Move more transform code.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/bzr/versionedfile.py
1
 
# Copyright (C) 2006-2010 Canonical Ltd
2
 
#
3
 
# Authors:
4
 
#   Johan Rydberg <jrydberg@gnu.org>
 
1
# Copyright (C) 2006-2011 Canonical Ltd
5
2
#
6
3
# This program is free software; you can redistribute it and/or modify
7
4
# it under the terms of the GNU General Public License as published by
19
16
 
20
17
"""Versioned text file storage api."""
21
18
 
 
19
from __future__ import absolute_import
 
20
 
22
21
from copy import copy
23
 
from cStringIO import StringIO
 
22
import itertools
24
23
import os
25
24
import struct
26
25
from zlib import adler32
27
26
 
28
 
from bzrlib.lazy_import import lazy_import
 
27
from ..lazy_import import lazy_import
29
28
lazy_import(globals(), """
30
 
import urllib
31
 
 
32
 
from bzrlib import (
 
29
from breezy import (
33
30
    annotate,
34
 
    errors,
 
31
    bencode,
35
32
    graph as _mod_graph,
36
 
    groupcompress,
37
 
    index,
38
 
    knit,
39
33
    osutils,
40
34
    multiparent,
41
35
    tsort,
42
36
    revision,
43
 
    ui,
44
 
    )
45
 
from bzrlib.graph import DictParentsProvider, Graph, StackedParentsProvider
46
 
from bzrlib.transport.memory import MemoryTransport
 
37
    urlutils,
 
38
    )
 
39
from breezy.bzr import (
 
40
    groupcompress,
 
41
    index,
 
42
    knit,
 
43
    )
47
44
""")
48
 
from bzrlib.registry import Registry
49
 
from bzrlib.symbol_versioning import *
50
 
from bzrlib.textmerge import TextMerge
51
 
from bzrlib import bencode
 
45
from .. import (
 
46
    errors,
 
47
    )
 
48
from ..registry import Registry
 
49
from ..sixish import (
 
50
    BytesIO,
 
51
    viewitems,
 
52
    viewvalues,
 
53
    zip,
 
54
    )
 
55
from ..textmerge import TextMerge
52
56
 
53
57
 
54
58
adapter_registry = Registry()
55
 
adapter_registry.register_lazy(('knit-delta-gz', 'fulltext'), 'bzrlib.knit',
56
 
    'DeltaPlainToFullText')
57
 
adapter_registry.register_lazy(('knit-ft-gz', 'fulltext'), 'bzrlib.knit',
58
 
    'FTPlainToFullText')
59
59
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'knit-delta-gz'),
60
 
    'bzrlib.knit', 'DeltaAnnotatedToUnannotated')
61
 
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'fulltext'),
62
 
    'bzrlib.knit', 'DeltaAnnotatedToFullText')
 
60
                               'breezy.bzr.knit', 'DeltaAnnotatedToUnannotated')
63
61
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'knit-ft-gz'),
64
 
    'bzrlib.knit', 'FTAnnotatedToUnannotated')
65
 
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'fulltext'),
66
 
    'bzrlib.knit', 'FTAnnotatedToFullText')
67
 
# adapter_registry.register_lazy(('knit-annotated-ft-gz', 'chunked'),
68
 
#     'bzrlib.knit', 'FTAnnotatedToChunked')
 
62
                               'breezy.bzr.knit', 'FTAnnotatedToUnannotated')
 
63
for target_storage_kind in ('fulltext', 'chunked', 'lines'):
 
64
    adapter_registry.register_lazy(('knit-delta-gz', target_storage_kind), 'breezy.bzr.knit',
 
65
                                   'DeltaPlainToFullText')
 
66
    adapter_registry.register_lazy(('knit-ft-gz', target_storage_kind), 'breezy.bzr.knit',
 
67
                                   'FTPlainToFullText')
 
68
    adapter_registry.register_lazy(('knit-annotated-ft-gz', target_storage_kind),
 
69
                                   'breezy.bzr.knit', 'FTAnnotatedToFullText')
 
70
    adapter_registry.register_lazy(('knit-annotated-delta-gz', target_storage_kind),
 
71
                                   'breezy.bzr.knit', 'DeltaAnnotatedToFullText')
 
72
 
 
73
 
 
74
class UnavailableRepresentation(errors.InternalBzrError):
 
75
 
 
76
    _fmt = ("The encoding '%(wanted)s' is not available for key %(key)s which "
 
77
            "is encoded as '%(native)s'.")
 
78
 
 
79
    def __init__(self, key, wanted, native):
 
80
        errors.InternalBzrError.__init__(self)
 
81
        self.wanted = wanted
 
82
        self.native = native
 
83
        self.key = key
 
84
 
 
85
 
 
86
class ExistingContent(errors.BzrError):
 
87
 
 
88
    _fmt = "The content being inserted is already present."
69
89
 
70
90
 
71
91
class ContentFactory(object):
72
92
    """Abstract interface for insertion and retrieval from a VersionedFile.
73
93
 
74
94
    :ivar sha1: None, or the sha1 of the content fulltext.
 
95
    :ivar size: None, or the size of the content fulltext.
75
96
    :ivar storage_kind: The native storage kind of this factory. One of
76
97
        'mpdiff', 'knit-annotated-ft', 'knit-annotated-delta', 'knit-ft',
77
98
        'knit-delta', 'fulltext', 'knit-annotated-ft-gz',
86
107
    def __init__(self):
87
108
        """Create a ContentFactory."""
88
109
        self.sha1 = None
 
110
        self.size = None
89
111
        self.storage_kind = None
90
112
        self.key = None
91
113
        self.parents = None
99
121
    satisfies this, as does a list of lines.
100
122
 
101
123
    :ivar sha1: None, or the sha1 of the content fulltext.
 
124
    :ivar size: None, or the size of the content fulltext.
102
125
    :ivar storage_kind: The native storage kind of this factory. Always
103
126
        'chunked'
104
127
    :ivar key: The key of this content. Each key is a tuple with a single
106
129
    :ivar parents: A tuple of parent keys for self.key. If the object has
107
130
        no parent information, None (as opposed to () for an empty list of
108
131
        parents).
 
132
    :ivar chunks_are_lines: Whether chunks are lines.
109
133
     """
110
134
 
111
 
    def __init__(self, key, parents, sha1, chunks):
 
135
    def __init__(self, key, parents, sha1, chunks, chunks_are_lines=None):
112
136
        """Create a ContentFactory."""
113
137
        self.sha1 = sha1
 
138
        self.size = sum(map(len, chunks))
114
139
        self.storage_kind = 'chunked'
115
140
        self.key = key
116
141
        self.parents = parents
117
142
        self._chunks = chunks
 
143
        self._chunks_are_lines = chunks_are_lines
118
144
 
119
145
    def get_bytes_as(self, storage_kind):
120
146
        if storage_kind == 'chunked':
121
147
            return self._chunks
122
148
        elif storage_kind == 'fulltext':
123
 
            return ''.join(self._chunks)
124
 
        raise errors.UnavailableRepresentation(self.key, storage_kind,
125
 
            self.storage_kind)
 
149
            return b''.join(self._chunks)
 
150
        elif storage_kind == 'lines':
 
151
            if self._chunks_are_lines:
 
152
                return self._chunks
 
153
            return list(osutils.chunks_to_lines(self._chunks))
 
154
        raise UnavailableRepresentation(self.key, storage_kind,
 
155
                                        self.storage_kind)
126
156
 
 
157
    def iter_bytes_as(self, storage_kind):
 
158
        if storage_kind == 'chunked':
 
159
            return iter(self._chunks)
 
160
        elif storage_kind == 'lines':
 
161
            if self._chunks_are_lines:
 
162
                return iter(self._chunks)
 
163
            return iter(osutils.chunks_to_lines(self._chunks))
 
164
        raise UnavailableRepresentation(self.key, storage_kind,
 
165
                                        self.storage_kind)
127
166
 
128
167
class FulltextContentFactory(ContentFactory):
129
168
    """Static data content factory.
144
183
    def __init__(self, key, parents, sha1, text):
145
184
        """Create a ContentFactory."""
146
185
        self.sha1 = sha1
 
186
        self.size = len(text)
147
187
        self.storage_kind = 'fulltext'
148
188
        self.key = key
149
189
        self.parents = parents
 
190
        if not isinstance(text, bytes):
 
191
            raise TypeError(text)
150
192
        self._text = text
151
193
 
152
194
    def get_bytes_as(self, storage_kind):
154
196
            return self._text
155
197
        elif storage_kind == 'chunked':
156
198
            return [self._text]
157
 
        raise errors.UnavailableRepresentation(self.key, storage_kind,
158
 
            self.storage_kind)
 
199
        elif storage_kind == 'lines':
 
200
            return osutils.split_lines(self._text)
 
201
        raise UnavailableRepresentation(self.key, storage_kind,
 
202
                                        self.storage_kind)
 
203
 
 
204
    def iter_bytes_as(self, storage_kind):
 
205
        if storage_kind == 'chunked':
 
206
            return iter([self._text])
 
207
        elif storage_kind == 'lines':
 
208
            return iter(osutils.split_lines(self._text))
 
209
        raise UnavailableRepresentation(self.key, storage_kind,
 
210
                                        self.storage_kind)
 
211
 
 
212
 
 
213
class FileContentFactory(ContentFactory):
 
214
    """File-based content factory.
 
215
    """
 
216
 
 
217
    def __init__(self, key, parents, fileobj, sha1=None, size=None):
 
218
        self.key = key
 
219
        self.parents = parents
 
220
        self.file = fileobj
 
221
        self.storage_kind = 'file'
 
222
        self.sha1 = sha1
 
223
        self.size = size
 
224
 
 
225
    def get_bytes_as(self, storage_kind):
 
226
        self.file.seek(0)
 
227
        if storage_kind == 'fulltext':
 
228
            return self.file.read()
 
229
        elif storage_kind == 'chunked':
 
230
            return list(osutils.file_iterator(self.file))
 
231
        elif storage_kind == 'lines':
 
232
            return list(self.file.readlines())
 
233
        raise UnavailableRepresentation(self.key, storage_kind,
 
234
                                        self.storage_kind)
 
235
 
 
236
    def iter_bytes_as(self, storage_kind):
 
237
        self.file.seek(0)
 
238
        if storage_kind == 'chunked':
 
239
            return osutils.file_iterator(self.file)
 
240
        elif storage_kind == 'lines':
 
241
            return self.file
 
242
        raise UnavailableRepresentation(self.key, storage_kind,
 
243
                                        self.storage_kind)
159
244
 
160
245
 
161
246
class AbsentContentFactory(ContentFactory):
171
256
    def __init__(self, key):
172
257
        """Create a ContentFactory."""
173
258
        self.sha1 = None
 
259
        self.size = None
174
260
        self.storage_kind = 'absent'
175
261
        self.key = key
176
262
        self.parents = None
181
267
                         ' code does not handle if it is missing.'
182
268
                         % (self.key,))
183
269
 
 
270
    def iter_bytes_as(self, storage_kind):
 
271
        raise ValueError('A request was made for key: %s, but that'
 
272
                         ' content is not available, and the calling'
 
273
                         ' code does not handle if it is missing.'
 
274
                         % (self.key,))
 
275
 
184
276
 
185
277
class AdapterFactory(ContentFactory):
186
278
    """A content factory to adapt between key prefix's."""
206
298
            yield record
207
299
 
208
300
 
 
301
class _MPDiffGenerator(object):
 
302
    """Pull out the functionality for generating mp_diffs."""
 
303
 
 
304
    def __init__(self, vf, keys):
 
305
        self.vf = vf
 
306
        # This is the order the keys were requested in
 
307
        self.ordered_keys = tuple(keys)
 
308
        # keys + their parents, what we need to compute the diffs
 
309
        self.needed_keys = ()
 
310
        # Map from key: mp_diff
 
311
        self.diffs = {}
 
312
        # Map from key: parents_needed (may have ghosts)
 
313
        self.parent_map = {}
 
314
        # Parents that aren't present
 
315
        self.ghost_parents = ()
 
316
        # Map from parent_key => number of children for this text
 
317
        self.refcounts = {}
 
318
        # Content chunks that are cached while we still need them
 
319
        self.chunks = {}
 
320
 
 
321
    def _find_needed_keys(self):
 
322
        """Find the set of keys we need to request.
 
323
 
 
324
        This includes all the original keys passed in, and the non-ghost
 
325
        parents of those keys.
 
326
 
 
327
        :return: (needed_keys, refcounts)
 
328
            needed_keys is the set of all texts we need to extract
 
329
            refcounts is a dict of {key: num_children} letting us know when we
 
330
                no longer need to cache a given parent text
 
331
        """
 
332
        # All the keys and their parents
 
333
        needed_keys = set(self.ordered_keys)
 
334
        parent_map = self.vf.get_parent_map(needed_keys)
 
335
        self.parent_map = parent_map
 
336
        # TODO: Should we be using a different construct here? I think this
 
337
        #       uses difference_update internally, and we expect the result to
 
338
        #       be tiny
 
339
        missing_keys = needed_keys.difference(parent_map)
 
340
        if missing_keys:
 
341
            raise errors.RevisionNotPresent(list(missing_keys)[0], self.vf)
 
342
        # Parents that might be missing. They are allowed to be ghosts, but we
 
343
        # should check for them
 
344
        refcounts = {}
 
345
        setdefault = refcounts.setdefault
 
346
        just_parents = set()
 
347
        for child_key, parent_keys in viewitems(parent_map):
 
348
            if not parent_keys:
 
349
                # parent_keys may be None if a given VersionedFile claims to
 
350
                # not support graph operations.
 
351
                continue
 
352
            just_parents.update(parent_keys)
 
353
            needed_keys.update(parent_keys)
 
354
            for p in parent_keys:
 
355
                refcounts[p] = setdefault(p, 0) + 1
 
356
        just_parents.difference_update(parent_map)
 
357
        # Remove any parents that are actually ghosts from the needed set
 
358
        self.present_parents = set(self.vf.get_parent_map(just_parents))
 
359
        self.ghost_parents = just_parents.difference(self.present_parents)
 
360
        needed_keys.difference_update(self.ghost_parents)
 
361
        self.needed_keys = needed_keys
 
362
        self.refcounts = refcounts
 
363
        return needed_keys, refcounts
 
364
 
 
365
    def _compute_diff(self, key, parent_lines, lines):
 
366
        """Compute a single mp_diff, and store it in self._diffs"""
 
367
        if len(parent_lines) > 0:
 
368
            # XXX: _extract_blocks is not usefully defined anywhere...
 
369
            #      It was meant to extract the left-parent diff without
 
370
            #      having to recompute it for Knit content (pack-0.92,
 
371
            #      etc). That seems to have regressed somewhere
 
372
            left_parent_blocks = self.vf._extract_blocks(key,
 
373
                                                         parent_lines[0], lines)
 
374
        else:
 
375
            left_parent_blocks = None
 
376
        diff = multiparent.MultiParent.from_lines(lines,
 
377
                                                  parent_lines, left_parent_blocks)
 
378
        self.diffs[key] = diff
 
379
 
 
380
    def _process_one_record(self, key, this_chunks):
 
381
        parent_keys = None
 
382
        if key in self.parent_map:
 
383
            # This record should be ready to diff, since we requested
 
384
            # content in 'topological' order
 
385
            parent_keys = self.parent_map.pop(key)
 
386
            # If a VersionedFile claims 'no-graph' support, then it may return
 
387
            # None for any parent request, so we replace it with an empty tuple
 
388
            if parent_keys is None:
 
389
                parent_keys = ()
 
390
            parent_lines = []
 
391
            for p in parent_keys:
 
392
                # Alternatively we could check p not in self.needed_keys, but
 
393
                # ghost_parents should be tiny versus huge
 
394
                if p in self.ghost_parents:
 
395
                    continue
 
396
                refcount = self.refcounts[p]
 
397
                if refcount == 1:  # Last child reference
 
398
                    self.refcounts.pop(p)
 
399
                    parent_chunks = self.chunks.pop(p)
 
400
                else:
 
401
                    self.refcounts[p] = refcount - 1
 
402
                    parent_chunks = self.chunks[p]
 
403
                p_lines = osutils.chunks_to_lines(parent_chunks)
 
404
                # TODO: Should we cache the line form? We did the
 
405
                #       computation to get it, but storing it this way will
 
406
                #       be less memory efficient...
 
407
                parent_lines.append(p_lines)
 
408
                del p_lines
 
409
            lines = osutils.chunks_to_lines(this_chunks)
 
410
            # Since we needed the lines, we'll go ahead and cache them this way
 
411
            this_chunks = lines
 
412
            self._compute_diff(key, parent_lines, lines)
 
413
            del lines
 
414
        # Is this content required for any more children?
 
415
        if key in self.refcounts:
 
416
            self.chunks[key] = this_chunks
 
417
 
 
418
    def _extract_diffs(self):
 
419
        needed_keys, refcounts = self._find_needed_keys()
 
420
        for record in self.vf.get_record_stream(needed_keys,
 
421
                                                'topological', True):
 
422
            if record.storage_kind == 'absent':
 
423
                raise errors.RevisionNotPresent(record.key, self.vf)
 
424
            self._process_one_record(record.key,
 
425
                                     record.get_bytes_as('chunked'))
 
426
 
 
427
    def compute_diffs(self):
 
428
        self._extract_diffs()
 
429
        dpop = self.diffs.pop
 
430
        return [dpop(k) for k in self.ordered_keys]
 
431
 
 
432
 
209
433
class VersionedFile(object):
210
434
    """Versioned text file storage.
211
435
 
259
483
        raise NotImplementedError
260
484
 
261
485
    def add_lines(self, version_id, parents, lines, parent_texts=None,
262
 
        left_matching_blocks=None, nostore_sha=None, random_id=False,
263
 
        check_content=True):
 
486
                  left_matching_blocks=None, nostore_sha=None, random_id=False,
 
487
                  check_content=True):
264
488
        """Add a single text on top of the versioned file.
265
489
 
266
490
        Must raise RevisionAlreadyPresent if the new version is
300
524
        """
301
525
        self._check_write_ok()
302
526
        return self._add_lines(version_id, parents, lines, parent_texts,
303
 
            left_matching_blocks, nostore_sha, random_id, check_content)
 
527
                               left_matching_blocks, nostore_sha, random_id, check_content)
304
528
 
305
529
    def _add_lines(self, version_id, parents, lines, parent_texts,
306
 
        left_matching_blocks, nostore_sha, random_id, check_content):
 
530
                   left_matching_blocks, nostore_sha, random_id, check_content):
307
531
        """Helper to do the class specific add_lines."""
308
532
        raise NotImplementedError(self.add_lines)
309
533
 
310
534
    def add_lines_with_ghosts(self, version_id, parents, lines,
311
 
        parent_texts=None, nostore_sha=None, random_id=False,
312
 
        check_content=True, left_matching_blocks=None):
 
535
                              parent_texts=None, nostore_sha=None, random_id=False,
 
536
                              check_content=True, left_matching_blocks=None):
313
537
        """Add lines to the versioned file, allowing ghosts to be present.
314
538
 
315
539
        This takes the same parameters as add_lines and returns the same.
316
540
        """
317
541
        self._check_write_ok()
318
542
        return self._add_lines_with_ghosts(version_id, parents, lines,
319
 
            parent_texts, nostore_sha, random_id, check_content, left_matching_blocks)
 
543
                                           parent_texts, nostore_sha, random_id, check_content, left_matching_blocks)
320
544
 
321
545
    def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts,
322
 
        nostore_sha, random_id, check_content, left_matching_blocks):
 
546
                               nostore_sha, random_id, check_content, left_matching_blocks):
323
547
        """Helper to do class specific add_lines_with_ghosts."""
324
548
        raise NotImplementedError(self.add_lines_with_ghosts)
325
549
 
330
554
    def _check_lines_not_unicode(self, lines):
331
555
        """Check that lines being added to a versioned file are not unicode."""
332
556
        for line in lines:
333
 
            if line.__class__ is not str:
 
557
            if not isinstance(line, bytes):
334
558
                raise errors.BzrBadParameterUnicode("lines")
335
559
 
336
560
    def _check_lines_are_lines(self, lines):
337
561
        """Check that the lines really are full lines without inline EOL."""
338
562
        for line in lines:
339
 
            if '\n' in line[:-1]:
 
563
            if b'\n' in line[:-1]:
340
564
                raise errors.BzrBadParameterContainsNewline("lines")
341
565
 
342
566
    def get_format_signature(self):
348
572
 
349
573
    def make_mpdiffs(self, version_ids):
350
574
        """Create multiparent diffs for specified versions."""
 
575
        # XXX: Can't use _MPDiffGenerator just yet. This is because version_ids
 
576
        #      is a list of strings, not keys. And while self.get_record_stream
 
577
        #      is supported, it takes *keys*, while self.get_parent_map() takes
 
578
        #      strings... *sigh*
351
579
        knit_versions = set()
352
580
        knit_versions.update(version_ids)
353
581
        parent_map = self.get_parent_map(version_ids)
357
585
            except KeyError:
358
586
                raise errors.RevisionNotPresent(version_id, self)
359
587
        # We need to filter out ghosts, because we can't diff against them.
360
 
        knit_versions = set(self.get_parent_map(knit_versions).keys())
 
588
        knit_versions = set(self.get_parent_map(knit_versions))
361
589
        lines = dict(zip(knit_versions,
362
 
            self._get_lf_split_line_list(knit_versions)))
 
590
                         self._get_lf_split_line_list(knit_versions)))
363
591
        diffs = []
364
592
        for version_id in version_ids:
365
593
            target = lines[version_id]
366
594
            try:
367
595
                parents = [lines[p] for p in parent_map[version_id] if p in
368
 
                    knit_versions]
 
596
                           knit_versions]
369
597
            except KeyError:
370
598
                # I don't know how this could ever trigger.
371
599
                # parent_map[version_id] was already triggered in the previous
378
606
            else:
379
607
                left_parent_blocks = None
380
608
            diffs.append(multiparent.MultiParent.from_lines(target, parents,
381
 
                         left_parent_blocks))
 
609
                                                            left_parent_blocks))
382
610
        return diffs
383
611
 
384
612
    def _extract_blocks(self, version_id, source, target):
401
629
        for version, parent_ids, expected_sha1, mpdiff in records:
402
630
            needed_parents.update(p for p in parent_ids
403
631
                                  if not mpvf.has_version(p))
404
 
        present_parents = set(self.get_parent_map(needed_parents).keys())
 
632
        present_parents = set(self.get_parent_map(needed_parents))
405
633
        for parent_id, lines in zip(present_parents,
406
 
                                 self._get_lf_split_line_list(present_parents)):
 
634
                                    self._get_lf_split_line_list(present_parents)):
407
635
            mpvf.add_version(lines, parent_id, [])
408
 
        for (version, parent_ids, expected_sha1, mpdiff), lines in\
409
 
            zip(records, mpvf.get_line_list(versions)):
 
636
        for (version, parent_ids, expected_sha1, mpdiff), lines in zip(
 
637
                records, mpvf.get_line_list(versions)):
410
638
            if len(parent_ids) == 1:
411
639
                left_matching_blocks = list(mpdiff.get_matching_blocks(0,
412
 
                    mpvf.get_diff(parent_ids[0]).num_lines()))
 
640
                                                                       mpvf.get_diff(parent_ids[0]).num_lines()))
413
641
            else:
414
642
                left_matching_blocks = None
415
643
            try:
416
644
                _, _, version_text = self.add_lines_with_ghosts(version,
417
 
                    parent_ids, lines, vf_parents,
418
 
                    left_matching_blocks=left_matching_blocks)
 
645
                                                                parent_ids, lines, vf_parents,
 
646
                                                                left_matching_blocks=left_matching_blocks)
419
647
            except NotImplementedError:
420
648
                # The vf can't handle ghosts, so add lines normally, which will
421
649
                # (reasonably) fail if there are ghosts in the data.
422
650
                _, _, version_text = self.add_lines(version,
423
 
                    parent_ids, lines, vf_parents,
424
 
                    left_matching_blocks=left_matching_blocks)
 
651
                                                    parent_ids, lines, vf_parents,
 
652
                                                    left_matching_blocks=left_matching_blocks)
425
653
            vf_parents[version] = version_text
426
654
        sha1s = self.get_sha1s(versions)
427
655
        for version, parent_ids, expected_sha1, mpdiff in records:
434
662
        Raises RevisionNotPresent if version is not present in
435
663
        file history.
436
664
        """
437
 
        return ''.join(self.get_lines(version_id))
 
665
        return b''.join(self.get_lines(version_id))
438
666
    get_string = get_text
439
667
 
440
668
    def get_texts(self, version_ids):
443
671
        Raises RevisionNotPresent if version is not present in
444
672
        file history.
445
673
        """
446
 
        return [''.join(self.get_lines(v)) for v in version_ids]
 
674
        return [b''.join(self.get_lines(v)) for v in version_ids]
447
675
 
448
676
    def get_lines(self, version_id):
449
677
        """Return version contents as a sequence of lines.
454
682
        raise NotImplementedError(self.get_lines)
455
683
 
456
684
    def _get_lf_split_line_list(self, version_ids):
457
 
        return [StringIO(t).readlines() for t in self.get_texts(version_ids)]
 
685
        return [BytesIO(t).readlines() for t in self.get_texts(version_ids)]
458
686
 
459
 
    def get_ancestry(self, version_ids, topo_sorted=True):
 
687
    def get_ancestry(self, version_ids):
460
688
        """Return a list of all ancestors of given version(s). This
461
689
        will not include the null revision.
462
690
 
463
 
        This list will not be topologically sorted if topo_sorted=False is
464
 
        passed.
465
 
 
466
691
        Must raise RevisionNotPresent if any of the given versions are
467
692
        not present in file history."""
468
 
        if isinstance(version_ids, basestring):
469
 
            version_ids = [version_ids]
470
693
        raise NotImplementedError(self.get_ancestry)
471
694
 
472
695
    def get_ancestry_with_ghosts(self, version_ids):
533
756
        """
534
757
        raise NotImplementedError(self.iter_lines_added_or_present_in_versions)
535
758
 
536
 
    def plan_merge(self, ver_a, ver_b):
 
759
    def plan_merge(self, ver_a, ver_b, base=None):
537
760
        """Return pseudo-annotation indicating how the two versions merge.
538
761
 
539
762
        This is computed between versions a and b and their common
578
801
        self.calls = []
579
802
 
580
803
    def add_lines(self, key, parents, lines, parent_texts=None,
581
 
        left_matching_blocks=None, nostore_sha=None, random_id=False,
582
 
        check_content=True):
 
804
                  left_matching_blocks=None, nostore_sha=None, random_id=False,
 
805
                  check_content=True):
583
806
        self.calls.append(("add_lines", key, parents, lines, parent_texts,
584
 
            left_matching_blocks, nostore_sha, random_id, check_content))
 
807
                           left_matching_blocks, nostore_sha, random_id, check_content))
585
808
        return self._backing_vf.add_lines(key, parents, lines, parent_texts,
586
 
            left_matching_blocks, nostore_sha, random_id, check_content)
 
809
                                          left_matching_blocks, nostore_sha, random_id, check_content)
 
810
 
 
811
    def add_content(self, factory, parent_texts=None,
 
812
                    left_matching_blocks=None, nostore_sha=None, random_id=False,
 
813
                    check_content=True):
 
814
        self.calls.append(("add_content", factory, parent_texts,
 
815
                           left_matching_blocks, nostore_sha, random_id, check_content))
 
816
        return self._backing_vf.add_content(
 
817
            factory, parent_texts, left_matching_blocks, nostore_sha,
 
818
            random_id, check_content)
587
819
 
588
820
    def check(self):
589
821
        self._backing_vf.check()
594
826
 
595
827
    def get_record_stream(self, keys, sort_order, include_delta_closure):
596
828
        self.calls.append(("get_record_stream", list(keys), sort_order,
597
 
            include_delta_closure))
 
829
                           include_delta_closure))
598
830
        return self._backing_vf.get_record_stream(keys, sort_order,
599
 
            include_delta_closure)
 
831
                                                  include_delta_closure)
600
832
 
601
833
    def get_sha1s(self, keys):
602
834
        self.calls.append(("get_sha1s", copy(keys)))
633
865
 
634
866
    def get_record_stream(self, keys, sort_order, include_delta_closure):
635
867
        self.calls.append(("get_record_stream", list(keys), sort_order,
636
 
            include_delta_closure))
 
868
                           include_delta_closure))
637
869
        if sort_order == 'unordered':
638
870
            def sort_key(key):
639
871
                return (self._key_priority.get(key, 0), key)
641
873
            # backing_vf
642
874
            for key in sorted(keys, key=sort_key):
643
875
                for record in self._backing_vf.get_record_stream([key],
644
 
                                'unordered', include_delta_closure):
 
876
                                                                 'unordered', include_delta_closure):
645
877
                    yield record
646
878
        else:
647
879
            for record in self._backing_vf.get_record_stream(keys, sort_order,
648
 
                            include_delta_closure):
 
880
                                                             include_delta_closure):
649
881
                yield record
650
882
 
651
883
 
655
887
    def map(self, key):
656
888
        """Map key to an underlying storage identifier.
657
889
 
658
 
        :param key: A key tuple e.g. ('file-id', 'revision-id').
 
890
        :param key: A key tuple e.g. (b'file-id', b'revision-id').
659
891
        :return: An underlying storage identifier, specific to the partitioning
660
892
            mechanism.
661
893
        """
692
924
 
693
925
    def map(self, key):
694
926
        """See KeyMapper.map()."""
695
 
        return urllib.quote(self._map(key))
 
927
        return urlutils.quote(self._map(key))
696
928
 
697
929
    def unmap(self, partition_id):
698
930
        """See KeyMapper.unmap()."""
699
 
        return self._unmap(urllib.unquote(partition_id))
 
931
        return self._unmap(urlutils.unquote(partition_id))
700
932
 
701
933
 
702
934
class PrefixMapper(URLEscapeMapper):
707
939
 
708
940
    def _map(self, key):
709
941
        """See KeyMapper.map()."""
710
 
        return key[0]
 
942
        return key[0].decode('utf-8')
711
943
 
712
944
    def _unmap(self, partition_id):
713
945
        """See KeyMapper.unmap()."""
714
 
        return (partition_id,)
 
946
        return (partition_id.encode('utf-8'),)
715
947
 
716
948
 
717
949
class HashPrefixMapper(URLEscapeMapper):
723
955
    def _map(self, key):
724
956
        """See KeyMapper.map()."""
725
957
        prefix = self._escape(key[0])
726
 
        return "%02x/%s" % (adler32(prefix) & 0xff, prefix)
 
958
        return "%02x/%s" % (adler32(prefix) & 0xff, prefix.decode('utf-8'))
727
959
 
728
960
    def _escape(self, prefix):
729
961
        """No escaping needed here."""
731
963
 
732
964
    def _unmap(self, partition_id):
733
965
        """See KeyMapper.unmap()."""
734
 
        return (self._unescape(osutils.basename(partition_id)),)
 
966
        return (self._unescape(osutils.basename(partition_id)).encode('utf-8'),)
735
967
 
736
968
    def _unescape(self, basename):
737
969
        """No unescaping needed for HashPrefixMapper."""
744
976
    This mapper is for use with a transport based backend.
745
977
    """
746
978
 
747
 
    _safe = "abcdefghijklmnopqrstuvwxyz0123456789-_@,."
 
979
    _safe = bytearray(b"abcdefghijklmnopqrstuvwxyz0123456789-_@,.")
748
980
 
749
981
    def _escape(self, prefix):
750
982
        """Turn a key element into a filesystem safe string.
751
983
 
752
 
        This is similar to a plain urllib.quote, except
 
984
        This is similar to a plain urlutils.quote, except
753
985
        it uses specific safe characters, so that it doesn't
754
986
        have to translate a lot of valid file ids.
755
987
        """
756
988
        # @ does not get escaped. This is because it is a valid
757
989
        # filesystem character we use all the time, and it looks
758
990
        # a lot better than seeing %40 all the time.
759
 
        r = [((c in self._safe) and c or ('%%%02x' % ord(c)))
760
 
             for c in prefix]
761
 
        return ''.join(r)
 
991
        r = [(c in self._safe) and chr(c) or ('%%%02x' % c)
 
992
             for c in bytearray(prefix)]
 
993
        return ''.join(r).encode('ascii')
762
994
 
763
995
    def _unescape(self, basename):
764
996
        """Escaped names are easily unescaped by urlutils."""
765
 
        return urllib.unquote(basename)
 
997
        return urlutils.unquote(basename)
766
998
 
767
999
 
768
1000
def make_versioned_files_factory(versioned_file_factory, mapper):
774
1006
    """
775
1007
    def factory(transport):
776
1008
        return ThunkedVersionedFiles(transport, versioned_file_factory, mapper,
777
 
            lambda:True)
 
1009
                                     lambda: True)
778
1010
    return factory
779
1011
 
780
1012
 
789
1021
 
790
1022
    The keyspace is expressed via simple tuples. Any instance of VersionedFiles
791
1023
    may have a different length key-size, but that size will be constant for
792
 
    all texts added to or retrieved from it. For instance, bzrlib uses
 
1024
    all texts added to or retrieved from it. For instance, breezy uses
793
1025
    instances with a key-size of 2 for storing user files in a repository, with
794
1026
    the first element the fileid, and the second the version of that file.
795
1027
 
796
1028
    The use of tuples allows a single code base to support several different
797
1029
    uses with only the mapping logic changing from instance to instance.
 
1030
 
 
1031
    :ivar _immediate_fallback_vfs: For subclasses that support stacking,
 
1032
        this is a list of other VersionedFiles immediately underneath this
 
1033
        one.  They may in turn each have further fallbacks.
798
1034
    """
799
1035
 
800
1036
    def add_lines(self, key, parents, lines, parent_texts=None,
801
 
        left_matching_blocks=None, nostore_sha=None, random_id=False,
802
 
        check_content=True):
 
1037
                  left_matching_blocks=None, nostore_sha=None, random_id=False,
 
1038
                  check_content=True):
803
1039
        """Add a text to the store.
804
1040
 
805
1041
        :param key: The key tuple of the text to add. If the last element is
836
1072
        """
837
1073
        raise NotImplementedError(self.add_lines)
838
1074
 
839
 
    def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
840
 
        """Add a text to the store.
841
 
 
842
 
        This is a private function for use by CommitBuilder.
 
1075
    def add_content(self, factory, parent_texts=None,
 
1076
                    left_matching_blocks=None, nostore_sha=None, random_id=False,
 
1077
                    check_content=True):
 
1078
        """Add a text to the store from a chunk iterable.
843
1079
 
844
1080
        :param key: The key tuple of the text to add. If the last element is
845
1081
            None, a CHK string will be generated during the addition.
846
1082
        :param parents: The parents key tuples of the text to add.
847
 
        :param text: A string containing the text to be committed.
 
1083
        :param chunk_iter: An iterable over bytestrings.
 
1084
        :param parent_texts: An optional dictionary containing the opaque
 
1085
            representations of some or all of the parents of version_id to
 
1086
            allow delta optimisations.  VERY IMPORTANT: the texts must be those
 
1087
            returned by add_lines or data corruption can be caused.
 
1088
        :param left_matching_blocks: a hint about which areas are common
 
1089
            between the text and its left-hand-parent.  The format is
 
1090
            the SequenceMatcher.get_matching_blocks format.
848
1091
        :param nostore_sha: Raise ExistingContent and do not add the lines to
849
1092
            the versioned file if the digest of the lines matches this.
850
1093
        :param random_id: If True a random id has been selected rather than
857
1100
            bytestrings that are correctly formed lines.
858
1101
        :return: The text sha1, the number of bytes in the text, and an opaque
859
1102
                 representation of the inserted version which can be provided
860
 
                 back to future _add_text calls in the parent_texts dictionary.
 
1103
                 back to future add_lines calls in the parent_texts dictionary.
861
1104
        """
862
 
        # The default implementation just thunks over to .add_lines(),
863
 
        # inefficient, but it works.
864
 
        return self.add_lines(key, parents, osutils.split_lines(text),
865
 
                              nostore_sha=nostore_sha,
866
 
                              random_id=random_id,
867
 
                              check_content=True)
 
1105
        raise NotImplementedError(self.add_content)
868
1106
 
869
1107
    def add_mpdiffs(self, records):
870
1108
        """Add mpdiffs to this VersionedFile.
884
1122
                                  if not mpvf.has_version(p))
885
1123
        # It seems likely that adding all the present parents as fulltexts can
886
1124
        # easily exhaust memory.
887
 
        chunks_to_lines = osutils.chunks_to_lines
888
1125
        for record in self.get_record_stream(needed_parents, 'unordered',
889
 
            True):
 
1126
                                             True):
890
1127
            if record.storage_kind == 'absent':
891
1128
                continue
892
 
            mpvf.add_version(chunks_to_lines(record.get_bytes_as('chunked')),
893
 
                record.key, [])
894
 
        for (key, parent_keys, expected_sha1, mpdiff), lines in\
895
 
            zip(records, mpvf.get_line_list(versions)):
 
1129
            mpvf.add_version(record.get_bytes_as('lines'), record.key, [])
 
1130
        for (key, parent_keys, expected_sha1, mpdiff), lines in zip(
 
1131
                records, mpvf.get_line_list(versions)):
896
1132
            if len(parent_keys) == 1:
897
1133
                left_matching_blocks = list(mpdiff.get_matching_blocks(0,
898
 
                    mpvf.get_diff(parent_keys[0]).num_lines()))
 
1134
                                                                       mpvf.get_diff(parent_keys[0]).num_lines()))
899
1135
            else:
900
1136
                left_matching_blocks = None
901
1137
            version_sha1, _, version_text = self.add_lines(key,
902
 
                parent_keys, lines, vf_parents,
903
 
                left_matching_blocks=left_matching_blocks)
 
1138
                                                           parent_keys, lines, vf_parents,
 
1139
                                                           left_matching_blocks=left_matching_blocks)
904
1140
            if version_sha1 != expected_sha1:
905
1141
                raise errors.VersionedFileInvalidChecksum(version)
906
1142
            vf_parents[key] = version_text
914
1150
 
915
1151
    def check(self, progress_bar=None):
916
1152
        """Check this object for integrity.
917
 
        
 
1153
 
918
1154
        :param progress_bar: A progress bar to output as the check progresses.
919
1155
        :param keys: Specific keys within the VersionedFiles to check. When
920
1156
            this parameter is not None, check() becomes a generator as per
939
1175
    def _check_lines_not_unicode(self, lines):
940
1176
        """Check that lines being added to a versioned file are not unicode."""
941
1177
        for line in lines:
942
 
            if line.__class__ is not str:
 
1178
            if line.__class__ is not bytes:
943
1179
                raise errors.BzrBadParameterUnicode("lines")
944
1180
 
945
1181
    def _check_lines_are_lines(self, lines):
946
1182
        """Check that the lines really are full lines without inline EOL."""
947
1183
        for line in lines:
948
 
            if '\n' in line[:-1]:
 
1184
            if b'\n' in line[:-1]:
949
1185
                raise errors.BzrBadParameterContainsNewline("lines")
950
1186
 
951
1187
    def get_known_graph_ancestry(self, keys):
956
1192
        while pending:
957
1193
            this_parent_map = self.get_parent_map(pending)
958
1194
            parent_map.update(this_parent_map)
959
 
            pending = set()
960
 
            map(pending.update, this_parent_map.itervalues())
961
 
            pending = pending.difference(parent_map)
 
1195
            pending = set(itertools.chain.from_iterable(
 
1196
                viewvalues(this_parent_map)))
 
1197
            pending.difference_update(parent_map)
962
1198
        kg = _mod_graph.KnownGraph(parent_map)
963
1199
        return kg
964
1200
 
995
1231
        """
996
1232
        raise NotImplementedError(self.get_sha1s)
997
1233
 
998
 
    has_key = index._has_key_from_parent_map
 
1234
    __contains__ = index._has_key_from_parent_map
999
1235
 
1000
1236
    def get_missing_compression_parent_keys(self):
1001
1237
        """Return an iterable of keys of missing compression parents.
1047
1283
 
1048
1284
    def make_mpdiffs(self, keys):
1049
1285
        """Create multiparent diffs for specified keys."""
1050
 
        keys_order = tuple(keys)
1051
 
        keys = frozenset(keys)
1052
 
        knit_keys = set(keys)
1053
 
        parent_map = self.get_parent_map(keys)
1054
 
        for parent_keys in parent_map.itervalues():
1055
 
            if parent_keys:
1056
 
                knit_keys.update(parent_keys)
1057
 
        missing_keys = keys - set(parent_map)
1058
 
        if missing_keys:
1059
 
            raise errors.RevisionNotPresent(list(missing_keys)[0], self)
1060
 
        # We need to filter out ghosts, because we can't diff against them.
1061
 
        maybe_ghosts = knit_keys - keys
1062
 
        ghosts = maybe_ghosts - set(self.get_parent_map(maybe_ghosts))
1063
 
        knit_keys.difference_update(ghosts)
1064
 
        lines = {}
1065
 
        chunks_to_lines = osutils.chunks_to_lines
1066
 
        for record in self.get_record_stream(knit_keys, 'topological', True):
1067
 
            lines[record.key] = chunks_to_lines(record.get_bytes_as('chunked'))
1068
 
            # line_block_dict = {}
1069
 
            # for parent, blocks in record.extract_line_blocks():
1070
 
            #   line_blocks[parent] = blocks
1071
 
            # line_blocks[record.key] = line_block_dict
1072
 
        diffs = []
1073
 
        for key in keys_order:
1074
 
            target = lines[key]
1075
 
            parents = parent_map[key] or []
1076
 
            # Note that filtering knit_keys can lead to a parent difference
1077
 
            # between the creation and the application of the mpdiff.
1078
 
            parent_lines = [lines[p] for p in parents if p in knit_keys]
1079
 
            if len(parent_lines) > 0:
1080
 
                left_parent_blocks = self._extract_blocks(key, parent_lines[0],
1081
 
                    target)
1082
 
            else:
1083
 
                left_parent_blocks = None
1084
 
            diffs.append(multiparent.MultiParent.from_lines(target,
1085
 
                parent_lines, left_parent_blocks))
1086
 
        return diffs
 
1286
        generator = _MPDiffGenerator(self, keys)
 
1287
        return generator.compute_diffs()
 
1288
 
 
1289
    def get_annotator(self):
 
1290
        return annotate.Annotator(self)
1087
1291
 
1088
1292
    missing_keys = index._missing_keys_from_parent_map
1089
1293
 
1090
1294
    def _extract_blocks(self, version_id, source, target):
1091
1295
        return None
1092
1296
 
 
1297
    def _transitive_fallbacks(self):
 
1298
        """Return the whole stack of fallback versionedfiles.
 
1299
 
 
1300
        This VersionedFiles may have a list of fallbacks, but it doesn't
 
1301
        necessarily know about the whole stack going down, and it can't know
 
1302
        at open time because they may change after the objects are opened.
 
1303
        """
 
1304
        all_fallbacks = []
 
1305
        for a_vfs in self._immediate_fallback_vfs:
 
1306
            all_fallbacks.append(a_vfs)
 
1307
            all_fallbacks.extend(a_vfs._transitive_fallbacks())
 
1308
        return all_fallbacks
 
1309
 
1093
1310
 
1094
1311
class ThunkedVersionedFiles(VersionedFiles):
1095
1312
    """Storage for many versioned files thunked onto a 'VersionedFile' class.
1108
1325
        self._mapper = mapper
1109
1326
        self._is_locked = is_locked
1110
1327
 
 
1328
    def add_content(self, factory, parent_texts=None,
 
1329
                    left_matching_blocks=None, nostore_sha=None, random_id=False):
 
1330
        """See VersionedFiles.add_content()."""
 
1331
        lines = factory.get_bytes_as('lines')
 
1332
        return self.add_lines(
 
1333
            factory.key, factory.parents, lines,
 
1334
            parent_texts=parent_texts,
 
1335
            left_matching_blocks=left_matching_blocks,
 
1336
            nostore_sha=nostore_sha,
 
1337
            random_id=random_id,
 
1338
            check_content=True)
 
1339
 
1111
1340
    def add_lines(self, key, parents, lines, parent_texts=None,
1112
 
        left_matching_blocks=None, nostore_sha=None, random_id=False,
1113
 
        check_content=True):
 
1341
                  left_matching_blocks=None, nostore_sha=None, random_id=False,
 
1342
                  check_content=True):
1114
1343
        """See VersionedFiles.add_lines()."""
1115
1344
        path = self._mapper.map(key)
1116
1345
        version_id = key[-1]
1119
1348
        try:
1120
1349
            try:
1121
1350
                return vf.add_lines_with_ghosts(version_id, parents, lines,
1122
 
                    parent_texts=parent_texts,
1123
 
                    left_matching_blocks=left_matching_blocks,
1124
 
                    nostore_sha=nostore_sha, random_id=random_id,
1125
 
                    check_content=check_content)
 
1351
                                                parent_texts=parent_texts,
 
1352
                                                left_matching_blocks=left_matching_blocks,
 
1353
                                                nostore_sha=nostore_sha, random_id=random_id,
 
1354
                                                check_content=check_content)
1126
1355
            except NotImplementedError:
1127
1356
                return vf.add_lines(version_id, parents, lines,
1128
 
                    parent_texts=parent_texts,
1129
 
                    left_matching_blocks=left_matching_blocks,
1130
 
                    nostore_sha=nostore_sha, random_id=random_id,
1131
 
                    check_content=check_content)
 
1357
                                    parent_texts=parent_texts,
 
1358
                                    left_matching_blocks=left_matching_blocks,
 
1359
                                    nostore_sha=nostore_sha, random_id=random_id,
 
1360
                                    check_content=check_content)
1132
1361
        except errors.NoSuchFile:
1133
1362
            # parent directory may be missing, try again.
1134
1363
            self._transport.mkdir(osutils.dirname(path))
1135
1364
            try:
1136
1365
                return vf.add_lines_with_ghosts(version_id, parents, lines,
1137
 
                    parent_texts=parent_texts,
1138
 
                    left_matching_blocks=left_matching_blocks,
1139
 
                    nostore_sha=nostore_sha, random_id=random_id,
1140
 
                    check_content=check_content)
 
1366
                                                parent_texts=parent_texts,
 
1367
                                                left_matching_blocks=left_matching_blocks,
 
1368
                                                nostore_sha=nostore_sha, random_id=random_id,
 
1369
                                                check_content=check_content)
1141
1370
            except NotImplementedError:
1142
1371
                return vf.add_lines(version_id, parents, lines,
1143
 
                    parent_texts=parent_texts,
1144
 
                    left_matching_blocks=left_matching_blocks,
1145
 
                    nostore_sha=nostore_sha, random_id=random_id,
1146
 
                    check_content=check_content)
 
1372
                                    parent_texts=parent_texts,
 
1373
                                    left_matching_blocks=left_matching_blocks,
 
1374
                                    nostore_sha=nostore_sha, random_id=random_id,
 
1375
                                    check_content=check_content)
1147
1376
 
1148
1377
    def annotate(self, key):
1149
1378
        """Return a list of (version-key, line) tuples for the text of key.
1159
1388
            result.append((prefix + (origin,), line))
1160
1389
        return result
1161
1390
 
1162
 
    def get_annotator(self):
1163
 
        return annotate.Annotator(self)
1164
 
 
1165
1391
    def check(self, progress_bar=None, keys=None):
1166
1392
        """See VersionedFiles.check()."""
1167
1393
        # XXX: This is over-enthusiastic but as we only thunk for Weaves today
1168
 
        # this is tolerable. Ideally we'd pass keys down to check() and 
 
1394
        # this is tolerable. Ideally we'd pass keys down to check() and
1169
1395
        # have the older VersiondFile interface updated too.
1170
1396
        for prefix, vf in self._iter_all_components():
1171
1397
            vf.check()
1181
1407
        """
1182
1408
        prefixes = self._partition_keys(keys)
1183
1409
        result = {}
1184
 
        for prefix, suffixes in prefixes.items():
 
1410
        for prefix, suffixes in viewitems(prefixes):
1185
1411
            path = self._mapper.map(prefix)
1186
1412
            vf = self._get_vf(path)
1187
1413
            parent_map = vf.get_parent_map(suffixes)
1188
 
            for key, parents in parent_map.items():
 
1414
            for key, parents in viewitems(parent_map):
1189
1415
                result[prefix + (key,)] = tuple(
1190
1416
                    prefix + (parent,) for parent in parents)
1191
1417
        return result
1194
1420
        if not self._is_locked():
1195
1421
            raise errors.ObjectNotLocked(self)
1196
1422
        return self._file_factory(path, self._transport, create=True,
1197
 
            get_scope=lambda:None)
 
1423
                                  get_scope=lambda: None)
1198
1424
 
1199
1425
    def _partition_keys(self, keys):
1200
1426
        """Turn keys into a dict of prefix:suffix_list."""
1204
1430
            prefix_keys.append(key[-1])
1205
1431
        return result
1206
1432
 
1207
 
    def _get_all_prefixes(self):
 
1433
    def _iter_all_prefixes(self):
1208
1434
        # Identify all key prefixes.
1209
1435
        # XXX: A bit hacky, needs polish.
1210
 
        if type(self._mapper) == ConstantMapper:
 
1436
        if isinstance(self._mapper, ConstantMapper):
1211
1437
            paths = [self._mapper.map(())]
1212
1438
            prefixes = [()]
1213
1439
        else:
1227
1453
        for prefix, suffixes, vf in self._iter_keys_vf(keys):
1228
1454
            suffixes = [(suffix,) for suffix in suffixes]
1229
1455
            for record in vf.get_record_stream(suffixes, ordering,
1230
 
                include_delta_closure):
 
1456
                                               include_delta_closure):
1231
1457
                if record.parents is not None:
1232
1458
                    record.parents = tuple(
1233
1459
                        prefix + parent for parent in record.parents)
1237
1463
    def _iter_keys_vf(self, keys):
1238
1464
        prefixes = self._partition_keys(keys)
1239
1465
        sha1s = {}
1240
 
        for prefix, suffixes in prefixes.items():
 
1466
        for prefix, suffixes in viewitems(prefixes):
1241
1467
            path = self._mapper.map(prefix)
1242
1468
            vf = self._get_vf(path)
1243
1469
            yield prefix, suffixes, vf
1245
1471
    def get_sha1s(self, keys):
1246
1472
        """See VersionedFiles.get_sha1s()."""
1247
1473
        sha1s = {}
1248
 
        for prefix,suffixes, vf in self._iter_keys_vf(keys):
 
1474
        for prefix, suffixes, vf in self._iter_keys_vf(keys):
1249
1475
            vf_sha1s = vf.get_sha1s(suffixes)
1250
 
            for suffix, sha1 in vf_sha1s.iteritems():
 
1476
            for suffix, sha1 in viewitems(vf_sha1s):
1251
1477
                sha1s[prefix + (suffix,)] = sha1
1252
1478
        return sha1s
1253
1479
 
1299
1525
                yield line, prefix + (version,)
1300
1526
 
1301
1527
    def _iter_all_components(self):
1302
 
        for path, prefix in self._get_all_prefixes():
 
1528
        for path, prefix in self._iter_all_prefixes():
1303
1529
            yield prefix, self._get_vf(path)
1304
1530
 
1305
1531
    def keys(self):
1311
1537
        return result
1312
1538
 
1313
1539
 
 
1540
class VersionedFilesWithFallbacks(VersionedFiles):
 
1541
 
 
1542
    def without_fallbacks(self):
 
1543
        """Return a clone of this object without any fallbacks configured."""
 
1544
        raise NotImplementedError(self.without_fallbacks)
 
1545
 
 
1546
    def add_fallback_versioned_files(self, a_versioned_files):
 
1547
        """Add a source of texts for texts not present in this knit.
 
1548
 
 
1549
        :param a_versioned_files: A VersionedFiles object.
 
1550
        """
 
1551
        raise NotImplementedError(self.add_fallback_versioned_files)
 
1552
 
 
1553
    def get_known_graph_ancestry(self, keys):
 
1554
        """Get a KnownGraph instance with the ancestry of keys."""
 
1555
        parent_map, missing_keys = self._index.find_ancestry(keys)
 
1556
        for fallback in self._transitive_fallbacks():
 
1557
            if not missing_keys:
 
1558
                break
 
1559
            (f_parent_map, f_missing_keys) = fallback._index.find_ancestry(
 
1560
                missing_keys)
 
1561
            parent_map.update(f_parent_map)
 
1562
            missing_keys = f_missing_keys
 
1563
        kg = _mod_graph.KnownGraph(parent_map)
 
1564
        return kg
 
1565
 
 
1566
 
1314
1567
class _PlanMergeVersionedFile(VersionedFiles):
1315
1568
    """A VersionedFile for uncommitted and committed texts.
1316
1569
 
1337
1590
        # line data for locally held keys.
1338
1591
        self._lines = {}
1339
1592
        # key lookup providers
1340
 
        self._providers = [DictParentsProvider(self._parents)]
 
1593
        self._providers = [_mod_graph.DictParentsProvider(self._parents)]
1341
1594
 
1342
1595
    def plan_merge(self, ver_a, ver_b, base=None):
1343
1596
        """See VersionedFile.plan_merge"""
1344
 
        from bzrlib.merge import _PlanMerge
 
1597
        from ..merge import _PlanMerge
1345
1598
        if base is None:
1346
1599
            return _PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge()
1347
 
        old_plan = list(_PlanMerge(ver_a, base, self, (self._file_id,)).plan_merge())
1348
 
        new_plan = list(_PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge())
 
1600
        old_plan = list(_PlanMerge(ver_a, base, self,
 
1601
                                   (self._file_id,)).plan_merge())
 
1602
        new_plan = list(_PlanMerge(ver_a, ver_b, self,
 
1603
                                   (self._file_id,)).plan_merge())
1349
1604
        return _PlanMerge._subtract_plans(old_plan, new_plan)
1350
1605
 
1351
1606
    def plan_lca_merge(self, ver_a, ver_b, base=None):
1352
 
        from bzrlib.merge import _PlanLCAMerge
1353
 
        graph = Graph(self)
1354
 
        new_plan = _PlanLCAMerge(ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
 
1607
        from ..merge import _PlanLCAMerge
 
1608
        graph = _mod_graph.Graph(self)
 
1609
        new_plan = _PlanLCAMerge(
 
1610
            ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
1355
1611
        if base is None:
1356
1612
            return new_plan
1357
 
        old_plan = _PlanLCAMerge(ver_a, base, self, (self._file_id,), graph).plan_merge()
 
1613
        old_plan = _PlanLCAMerge(
 
1614
            ver_a, base, self, (self._file_id,), graph).plan_merge()
1358
1615
        return _PlanLCAMerge._subtract_plans(list(old_plan), list(new_plan))
1359
1616
 
 
1617
    def add_content(self, factory):
 
1618
        return self.add_lines(
 
1619
            factory.key, factory.parents, factory.get_bytes_as('lines'))
 
1620
 
1360
1621
    def add_lines(self, key, parents, lines):
1361
1622
        """See VersionedFiles.add_lines
1362
1623
 
1363
1624
        Lines are added locally, not to fallback versionedfiles.  Also, ghosts
1364
1625
        are permitted.  Only reserved ids are permitted.
1365
1626
        """
1366
 
        if type(key) is not tuple:
 
1627
        if not isinstance(key, tuple):
1367
1628
            raise TypeError(key)
1368
1629
        if not revision.is_reserved_id(key[-1]):
1369
1630
            raise ValueError('Only reserved ids may be used')
1381
1642
                lines = self._lines[key]
1382
1643
                parents = self._parents[key]
1383
1644
                pending.remove(key)
1384
 
                yield ChunkedContentFactory(key, parents, None, lines)
 
1645
                yield ChunkedContentFactory(
 
1646
                    key, parents, None, lines,
 
1647
                    chunks_are_lines=True)
1385
1648
        for versionedfile in self.fallback_versionedfiles:
1386
1649
            for record in versionedfile.get_record_stream(
1387
 
                pending, 'unordered', True):
 
1650
                    pending, 'unordered', True):
1388
1651
                if record.storage_kind == 'absent':
1389
1652
                    continue
1390
1653
                else:
1408
1671
            result[revision.NULL_REVISION] = ()
1409
1672
        self._providers = self._providers[:1] + self.fallback_versionedfiles
1410
1673
        result.update(
1411
 
            StackedParentsProvider(self._providers).get_parent_map(keys))
1412
 
        for key, parents in result.iteritems():
 
1674
            _mod_graph.StackedParentsProvider(
 
1675
                self._providers).get_parent_map(keys))
 
1676
        for key, parents in viewitems(result):
1413
1677
            if parents == ():
1414
1678
                result[key] = (revision.NULL_REVISION,)
1415
1679
        return result
1484
1748
                ch_b = ch_a = True
1485
1749
            else:
1486
1750
                if state not in ('irrelevant', 'ghost-a', 'ghost-b',
1487
 
                        'killed-base'):
 
1751
                                 'killed-base'):
1488
1752
                    raise AssertionError(state)
1489
1753
        for struct in outstanding_struct():
1490
1754
            yield struct
1548
1812
    """Weave merge that takes a VersionedFile and two versions as its input."""
1549
1813
 
1550
1814
    def __init__(self, versionedfile, ver_a, ver_b,
1551
 
        a_marker=PlanWeaveMerge.A_MARKER, b_marker=PlanWeaveMerge.B_MARKER):
 
1815
                 a_marker=PlanWeaveMerge.A_MARKER, b_marker=PlanWeaveMerge.B_MARKER):
1552
1816
        plan = versionedfile.plan_merge(ver_a, ver_b)
1553
1817
        PlanWeaveMerge.__init__(self, plan, a_marker, b_marker)
1554
1818
 
1588
1852
 
1589
1853
    def get_parent_map(self, keys):
1590
1854
        """See VersionedFiles.get_parent_map."""
1591
 
        return dict([((k,), tuple([(p,) for p in v]))
1592
 
            for k,v in self._get_parent_map([k for (k,) in keys]).iteritems()])
 
1855
        parent_view = viewitems(self._get_parent_map(k for (k,) in keys))
 
1856
        return dict(((k,), tuple((p,) for p in v)) for k, v in parent_view)
1593
1857
 
1594
1858
    def get_sha1s(self, keys):
1595
1859
        """See VersionedFiles.get_sha1s."""
1609
1873
            if lines is not None:
1610
1874
                if not isinstance(lines, list):
1611
1875
                    raise AssertionError
1612
 
                yield ChunkedContentFactory((k,), None,
1613
 
                        sha1=osutils.sha_strings(lines),
1614
 
                        chunks=lines)
 
1876
                yield ChunkedContentFactory(
 
1877
                    (k,), None, sha1=osutils.sha_strings(lines),
 
1878
                    chunks=lines, chunks_are_lines=True)
1615
1879
            else:
1616
1880
                yield AbsentContentFactory((k,))
1617
1881
 
1624
1888
                yield (l, key)
1625
1889
 
1626
1890
 
 
1891
class NoDupeAddLinesDecorator(object):
 
1892
    """Decorator for a VersionedFiles that skips doing an add_lines if the key
 
1893
    is already present.
 
1894
    """
 
1895
 
 
1896
    def __init__(self, store):
 
1897
        self._store = store
 
1898
 
 
1899
    def add_lines(self, key, parents, lines, parent_texts=None,
 
1900
                  left_matching_blocks=None, nostore_sha=None, random_id=False,
 
1901
                  check_content=True):
 
1902
        """See VersionedFiles.add_lines.
 
1903
 
 
1904
        This implementation may return None as the third element of the return
 
1905
        value when the original store wouldn't.
 
1906
        """
 
1907
        if nostore_sha:
 
1908
            raise NotImplementedError(
 
1909
                "NoDupeAddLinesDecorator.add_lines does not implement the "
 
1910
                "nostore_sha behaviour.")
 
1911
        if key[-1] is None:
 
1912
            sha1 = osutils.sha_strings(lines)
 
1913
            key = (b"sha1:" + sha1,)
 
1914
        else:
 
1915
            sha1 = None
 
1916
        if key in self._store.get_parent_map([key]):
 
1917
            # This key has already been inserted, so don't do it again.
 
1918
            if sha1 is None:
 
1919
                sha1 = osutils.sha_strings(lines)
 
1920
            return sha1, sum(map(len, lines)), None
 
1921
        return self._store.add_lines(key, parents, lines,
 
1922
                                     parent_texts=parent_texts,
 
1923
                                     left_matching_blocks=left_matching_blocks,
 
1924
                                     nostore_sha=nostore_sha, random_id=random_id,
 
1925
                                     check_content=check_content)
 
1926
 
 
1927
    def __getattr__(self, name):
 
1928
        return getattr(self._store, name)
 
1929
 
 
1930
 
1627
1931
def network_bytes_to_kind_and_offset(network_bytes):
1628
1932
    """Strip of a record kind from the front of network_bytes.
1629
1933
 
1630
1934
    :param network_bytes: The bytes of a record.
1631
1935
    :return: A tuple (storage_kind, offset_of_remaining_bytes)
1632
1936
    """
1633
 
    line_end = network_bytes.find('\n')
1634
 
    storage_kind = network_bytes[:line_end]
 
1937
    line_end = network_bytes.find(b'\n')
 
1938
    storage_kind = network_bytes[:line_end].decode('ascii')
1635
1939
    return storage_kind, line_end + 1
1636
1940
 
1637
1941
 
1664
1968
        for bytes in self._bytes_iterator:
1665
1969
            storage_kind, line_end = network_bytes_to_kind_and_offset(bytes)
1666
1970
            for record in self._kind_factory[storage_kind](
1667
 
                storage_kind, bytes, line_end):
 
1971
                    storage_kind, bytes, line_end):
1668
1972
                yield record
1669
1973
 
1670
1974
 
1671
1975
def fulltext_network_to_record(kind, bytes, line_end):
1672
1976
    """Convert a network fulltext record to record."""
1673
 
    meta_len, = struct.unpack('!L', bytes[line_end:line_end+4])
1674
 
    record_meta = bytes[line_end+4:line_end+4+meta_len]
 
1977
    meta_len, = struct.unpack('!L', bytes[line_end:line_end + 4])
 
1978
    record_meta = bytes[line_end + 4:line_end + 4 + meta_len]
1675
1979
    key, parents = bencode.bdecode_as_tuple(record_meta)
1676
 
    if parents == 'nil':
 
1980
    if parents == b'nil':
1677
1981
        parents = None
1678
 
    fulltext = bytes[line_end+4+meta_len:]
 
1982
    fulltext = bytes[line_end + 4 + meta_len:]
1679
1983
    return [FulltextContentFactory(key, parents, None, fulltext)]
1680
1984
 
1681
1985
 
1685
1989
 
1686
1990
def record_to_fulltext_bytes(record):
1687
1991
    if record.parents is None:
1688
 
        parents = 'nil'
 
1992
        parents = b'nil'
1689
1993
    else:
1690
1994
        parents = record.parents
1691
1995
    record_meta = bencode.bencode((record.key, parents))
1692
1996
    record_content = record.get_bytes_as('fulltext')
1693
 
    return "fulltext\n%s%s%s" % (
 
1997
    return b"fulltext\n%s%s%s" % (
1694
1998
        _length_prefix(record_meta), record_meta, record_content)
1695
1999
 
1696
2000
 
1705
2009
    # gc-optimal ordering is approximately reverse topological,
1706
2010
    # properly grouped by file-id.
1707
2011
    per_prefix_map = {}
1708
 
    for item in parent_map.iteritems():
 
2012
    for item in viewitems(parent_map):
1709
2013
        key = item[0]
1710
 
        if isinstance(key, str) or len(key) == 1:
1711
 
            prefix = ''
 
2014
        if isinstance(key, bytes) or len(key) == 1:
 
2015
            prefix = b''
1712
2016
        else:
1713
2017
            prefix = key[0]
1714
2018
        try:
1720
2024
    for prefix in sorted(per_prefix_map):
1721
2025
        present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
1722
2026
    return present_keys
 
2027
 
 
2028
 
 
2029
class _KeyRefs(object):
 
2030
 
 
2031
    def __init__(self, track_new_keys=False):
 
2032
        # dict mapping 'key' to 'set of keys referring to that key'
 
2033
        self.refs = {}
 
2034
        if track_new_keys:
 
2035
            # set remembering all new keys
 
2036
            self.new_keys = set()
 
2037
        else:
 
2038
            self.new_keys = None
 
2039
 
 
2040
    def clear(self):
 
2041
        if self.refs:
 
2042
            self.refs.clear()
 
2043
        if self.new_keys:
 
2044
            self.new_keys.clear()
 
2045
 
 
2046
    def add_references(self, key, refs):
 
2047
        # Record the new references
 
2048
        for referenced in refs:
 
2049
            try:
 
2050
                needed_by = self.refs[referenced]
 
2051
            except KeyError:
 
2052
                needed_by = self.refs[referenced] = set()
 
2053
            needed_by.add(key)
 
2054
        # Discard references satisfied by the new key
 
2055
        self.add_key(key)
 
2056
 
 
2057
    def get_new_keys(self):
 
2058
        return self.new_keys
 
2059
 
 
2060
    def get_unsatisfied_refs(self):
 
2061
        return self.refs.keys()
 
2062
 
 
2063
    def _satisfy_refs_for_key(self, key):
 
2064
        try:
 
2065
            del self.refs[key]
 
2066
        except KeyError:
 
2067
            # No keys depended on this key.  That's ok.
 
2068
            pass
 
2069
 
 
2070
    def add_key(self, key):
 
2071
        # satisfy refs for key, and remember that we've seen this key.
 
2072
        self._satisfy_refs_for_key(key)
 
2073
        if self.new_keys is not None:
 
2074
            self.new_keys.add(key)
 
2075
 
 
2076
    def satisfy_refs_for_keys(self, keys):
 
2077
        for key in keys:
 
2078
            self._satisfy_refs_for_key(key)
 
2079
 
 
2080
    def get_referrers(self):
 
2081
        return set(itertools.chain.from_iterable(viewvalues(self.refs)))