/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: 2018-09-12 18:20:02 UTC
  • mto: This revision was merged to the branch mainline in revision 7107.
  • Revision ID: jelmer@jelmer.uk-20180912182002-5z6dvag2frdvr9y2
Fix remaining deprecation warning test.

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,
 
31
    bencode,
34
32
    errors,
35
33
    graph as _mod_graph,
36
 
    groupcompress,
37
 
    index,
38
 
    knit,
39
34
    osutils,
40
35
    multiparent,
41
36
    tsort,
42
37
    revision,
43
 
    ui,
44
 
    )
45
 
from bzrlib.graph import DictParentsProvider, Graph, StackedParentsProvider
46
 
from bzrlib.transport.memory import MemoryTransport
 
38
    urlutils,
 
39
    )
 
40
from breezy.bzr import (
 
41
    groupcompress,
 
42
    index,
 
43
    knit,
 
44
    )
47
45
""")
48
 
from bzrlib.registry import Registry
49
 
from bzrlib.symbol_versioning import *
50
 
from bzrlib.textmerge import TextMerge
51
 
from bzrlib import bencode
 
46
from ..registry import Registry
 
47
from ..sixish import (
 
48
    BytesIO,
 
49
    viewitems,
 
50
    viewvalues,
 
51
    zip,
 
52
    )
 
53
from ..textmerge import TextMerge
52
54
 
53
55
 
54
56
adapter_registry = Registry()
55
 
adapter_registry.register_lazy(('knit-delta-gz', 'fulltext'), 'bzrlib.knit',
 
57
adapter_registry.register_lazy(('knit-delta-gz', 'fulltext'), 'breezy.bzr.knit',
56
58
    'DeltaPlainToFullText')
57
 
adapter_registry.register_lazy(('knit-ft-gz', 'fulltext'), 'bzrlib.knit',
 
59
adapter_registry.register_lazy(('knit-ft-gz', 'fulltext'), 'breezy.bzr.knit',
58
60
    'FTPlainToFullText')
59
61
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'knit-delta-gz'),
60
 
    'bzrlib.knit', 'DeltaAnnotatedToUnannotated')
 
62
    'breezy.bzr.knit', 'DeltaAnnotatedToUnannotated')
61
63
adapter_registry.register_lazy(('knit-annotated-delta-gz', 'fulltext'),
62
 
    'bzrlib.knit', 'DeltaAnnotatedToFullText')
 
64
    'breezy.bzr.knit', 'DeltaAnnotatedToFullText')
63
65
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'knit-ft-gz'),
64
 
    'bzrlib.knit', 'FTAnnotatedToUnannotated')
 
66
    'breezy.bzr.knit', 'FTAnnotatedToUnannotated')
65
67
adapter_registry.register_lazy(('knit-annotated-ft-gz', 'fulltext'),
66
 
    'bzrlib.knit', 'FTAnnotatedToFullText')
 
68
    'breezy.bzr.knit', 'FTAnnotatedToFullText')
67
69
# adapter_registry.register_lazy(('knit-annotated-ft-gz', 'chunked'),
68
 
#     'bzrlib.knit', 'FTAnnotatedToChunked')
 
70
#     'breezy.bzr.knit', 'FTAnnotatedToChunked')
69
71
 
70
72
 
71
73
class ContentFactory(object):
120
122
        if storage_kind == 'chunked':
121
123
            return self._chunks
122
124
        elif storage_kind == 'fulltext':
123
 
            return ''.join(self._chunks)
 
125
            return b''.join(self._chunks)
124
126
        raise errors.UnavailableRepresentation(self.key, storage_kind,
125
127
            self.storage_kind)
126
128
 
147
149
        self.storage_kind = 'fulltext'
148
150
        self.key = key
149
151
        self.parents = parents
 
152
        if not isinstance(text, bytes):
 
153
            raise TypeError(text)
150
154
        self._text = text
151
155
 
152
156
    def get_bytes_as(self, storage_kind):
206
210
            yield record
207
211
 
208
212
 
 
213
class _MPDiffGenerator(object):
 
214
    """Pull out the functionality for generating mp_diffs."""
 
215
 
 
216
    def __init__(self, vf, keys):
 
217
        self.vf = vf
 
218
        # This is the order the keys were requested in
 
219
        self.ordered_keys = tuple(keys)
 
220
        # keys + their parents, what we need to compute the diffs
 
221
        self.needed_keys = ()
 
222
        # Map from key: mp_diff
 
223
        self.diffs = {}
 
224
        # Map from key: parents_needed (may have ghosts)
 
225
        self.parent_map = {}
 
226
        # Parents that aren't present
 
227
        self.ghost_parents = ()
 
228
        # Map from parent_key => number of children for this text
 
229
        self.refcounts = {}
 
230
        # Content chunks that are cached while we still need them
 
231
        self.chunks = {}
 
232
 
 
233
    def _find_needed_keys(self):
 
234
        """Find the set of keys we need to request.
 
235
 
 
236
        This includes all the original keys passed in, and the non-ghost
 
237
        parents of those keys.
 
238
 
 
239
        :return: (needed_keys, refcounts)
 
240
            needed_keys is the set of all texts we need to extract
 
241
            refcounts is a dict of {key: num_children} letting us know when we
 
242
                no longer need to cache a given parent text
 
243
        """
 
244
        # All the keys and their parents
 
245
        needed_keys = set(self.ordered_keys)
 
246
        parent_map = self.vf.get_parent_map(needed_keys)
 
247
        self.parent_map = parent_map
 
248
        # TODO: Should we be using a different construct here? I think this
 
249
        #       uses difference_update internally, and we expect the result to
 
250
        #       be tiny
 
251
        missing_keys = needed_keys.difference(parent_map)
 
252
        if missing_keys:
 
253
            raise errors.RevisionNotPresent(list(missing_keys)[0], self.vf)
 
254
        # Parents that might be missing. They are allowed to be ghosts, but we
 
255
        # should check for them
 
256
        refcounts = {}
 
257
        setdefault = refcounts.setdefault
 
258
        just_parents = set()
 
259
        for child_key, parent_keys in viewitems(parent_map):
 
260
            if not parent_keys:
 
261
                # parent_keys may be None if a given VersionedFile claims to
 
262
                # not support graph operations.
 
263
                continue
 
264
            just_parents.update(parent_keys)
 
265
            needed_keys.update(parent_keys)
 
266
            for p in parent_keys:
 
267
                refcounts[p] = setdefault(p, 0) + 1
 
268
        just_parents.difference_update(parent_map)
 
269
        # Remove any parents that are actually ghosts from the needed set
 
270
        self.present_parents = set(self.vf.get_parent_map(just_parents))
 
271
        self.ghost_parents = just_parents.difference(self.present_parents)
 
272
        needed_keys.difference_update(self.ghost_parents)
 
273
        self.needed_keys = needed_keys
 
274
        self.refcounts = refcounts
 
275
        return needed_keys, refcounts
 
276
 
 
277
    def _compute_diff(self, key, parent_lines, lines):
 
278
        """Compute a single mp_diff, and store it in self._diffs"""
 
279
        if len(parent_lines) > 0:
 
280
            # XXX: _extract_blocks is not usefully defined anywhere...
 
281
            #      It was meant to extract the left-parent diff without
 
282
            #      having to recompute it for Knit content (pack-0.92,
 
283
            #      etc). That seems to have regressed somewhere
 
284
            left_parent_blocks = self.vf._extract_blocks(key,
 
285
                parent_lines[0], lines)
 
286
        else:
 
287
            left_parent_blocks = None
 
288
        diff = multiparent.MultiParent.from_lines(lines,
 
289
                    parent_lines, left_parent_blocks)
 
290
        self.diffs[key] = diff
 
291
 
 
292
    def _process_one_record(self, key, this_chunks):
 
293
        parent_keys = None
 
294
        if key in self.parent_map:
 
295
            # This record should be ready to diff, since we requested
 
296
            # content in 'topological' order
 
297
            parent_keys = self.parent_map.pop(key)
 
298
            # If a VersionedFile claims 'no-graph' support, then it may return
 
299
            # None for any parent request, so we replace it with an empty tuple
 
300
            if parent_keys is None:
 
301
                parent_keys = ()
 
302
            parent_lines = []
 
303
            for p in parent_keys:
 
304
                # Alternatively we could check p not in self.needed_keys, but
 
305
                # ghost_parents should be tiny versus huge
 
306
                if p in self.ghost_parents:
 
307
                    continue
 
308
                refcount = self.refcounts[p]
 
309
                if refcount == 1: # Last child reference
 
310
                    self.refcounts.pop(p)
 
311
                    parent_chunks = self.chunks.pop(p)
 
312
                else:
 
313
                    self.refcounts[p] = refcount - 1
 
314
                    parent_chunks = self.chunks[p]
 
315
                p_lines = osutils.chunks_to_lines(parent_chunks)
 
316
                # TODO: Should we cache the line form? We did the
 
317
                #       computation to get it, but storing it this way will
 
318
                #       be less memory efficient...
 
319
                parent_lines.append(p_lines)
 
320
                del p_lines
 
321
            lines = osutils.chunks_to_lines(this_chunks)
 
322
            # Since we needed the lines, we'll go ahead and cache them this way
 
323
            this_chunks = lines
 
324
            self._compute_diff(key, parent_lines, lines)
 
325
            del lines
 
326
        # Is this content required for any more children?
 
327
        if key in self.refcounts:
 
328
            self.chunks[key] = this_chunks
 
329
 
 
330
    def _extract_diffs(self):
 
331
        needed_keys, refcounts = self._find_needed_keys()
 
332
        for record in self.vf.get_record_stream(needed_keys,
 
333
                                                'topological', True):
 
334
            if record.storage_kind == 'absent':
 
335
                raise errors.RevisionNotPresent(record.key, self.vf)
 
336
            self._process_one_record(record.key,
 
337
                                     record.get_bytes_as('chunked'))
 
338
        
 
339
    def compute_diffs(self):
 
340
        self._extract_diffs()
 
341
        dpop = self.diffs.pop
 
342
        return [dpop(k) for k in self.ordered_keys]
 
343
 
 
344
 
209
345
class VersionedFile(object):
210
346
    """Versioned text file storage.
211
347
 
330
466
    def _check_lines_not_unicode(self, lines):
331
467
        """Check that lines being added to a versioned file are not unicode."""
332
468
        for line in lines:
333
 
            if line.__class__ is not str:
 
469
            if not isinstance(line, bytes):
334
470
                raise errors.BzrBadParameterUnicode("lines")
335
471
 
336
472
    def _check_lines_are_lines(self, lines):
337
473
        """Check that the lines really are full lines without inline EOL."""
338
474
        for line in lines:
339
 
            if '\n' in line[:-1]:
 
475
            if b'\n' in line[:-1]:
340
476
                raise errors.BzrBadParameterContainsNewline("lines")
341
477
 
342
478
    def get_format_signature(self):
348
484
 
349
485
    def make_mpdiffs(self, version_ids):
350
486
        """Create multiparent diffs for specified versions."""
 
487
        # XXX: Can't use _MPDiffGenerator just yet. This is because version_ids
 
488
        #      is a list of strings, not keys. And while self.get_record_stream
 
489
        #      is supported, it takes *keys*, while self.get_parent_map() takes
 
490
        #      strings... *sigh*
351
491
        knit_versions = set()
352
492
        knit_versions.update(version_ids)
353
493
        parent_map = self.get_parent_map(version_ids)
357
497
            except KeyError:
358
498
                raise errors.RevisionNotPresent(version_id, self)
359
499
        # We need to filter out ghosts, because we can't diff against them.
360
 
        knit_versions = set(self.get_parent_map(knit_versions).keys())
 
500
        knit_versions = set(self.get_parent_map(knit_versions))
361
501
        lines = dict(zip(knit_versions,
362
502
            self._get_lf_split_line_list(knit_versions)))
363
503
        diffs = []
401
541
        for version, parent_ids, expected_sha1, mpdiff in records:
402
542
            needed_parents.update(p for p in parent_ids
403
543
                                  if not mpvf.has_version(p))
404
 
        present_parents = set(self.get_parent_map(needed_parents).keys())
 
544
        present_parents = set(self.get_parent_map(needed_parents))
405
545
        for parent_id, lines in zip(present_parents,
406
 
                                 self._get_lf_split_line_list(present_parents)):
 
546
                self._get_lf_split_line_list(present_parents)):
407
547
            mpvf.add_version(lines, parent_id, [])
408
 
        for (version, parent_ids, expected_sha1, mpdiff), lines in\
409
 
            zip(records, mpvf.get_line_list(versions)):
 
548
        for (version, parent_ids, expected_sha1, mpdiff), lines in zip(
 
549
                records, mpvf.get_line_list(versions)):
410
550
            if len(parent_ids) == 1:
411
551
                left_matching_blocks = list(mpdiff.get_matching_blocks(0,
412
552
                    mpvf.get_diff(parent_ids[0]).num_lines()))
434
574
        Raises RevisionNotPresent if version is not present in
435
575
        file history.
436
576
        """
437
 
        return ''.join(self.get_lines(version_id))
 
577
        return b''.join(self.get_lines(version_id))
438
578
    get_string = get_text
439
579
 
440
580
    def get_texts(self, version_ids):
443
583
        Raises RevisionNotPresent if version is not present in
444
584
        file history.
445
585
        """
446
 
        return [''.join(self.get_lines(v)) for v in version_ids]
 
586
        return [b''.join(self.get_lines(v)) for v in version_ids]
447
587
 
448
588
    def get_lines(self, version_id):
449
589
        """Return version contents as a sequence of lines.
454
594
        raise NotImplementedError(self.get_lines)
455
595
 
456
596
    def _get_lf_split_line_list(self, version_ids):
457
 
        return [StringIO(t).readlines() for t in self.get_texts(version_ids)]
 
597
        return [BytesIO(t).readlines() for t in self.get_texts(version_ids)]
458
598
 
459
599
    def get_ancestry(self, version_ids, topo_sorted=True):
460
600
        """Return a list of all ancestors of given version(s). This
465
605
 
466
606
        Must raise RevisionNotPresent if any of the given versions are
467
607
        not present in file history."""
468
 
        if isinstance(version_ids, basestring):
469
 
            version_ids = [version_ids]
470
608
        raise NotImplementedError(self.get_ancestry)
471
609
 
472
610
    def get_ancestry_with_ghosts(self, version_ids):
533
671
        """
534
672
        raise NotImplementedError(self.iter_lines_added_or_present_in_versions)
535
673
 
536
 
    def plan_merge(self, ver_a, ver_b):
 
674
    def plan_merge(self, ver_a, ver_b, base=None):
537
675
        """Return pseudo-annotation indicating how the two versions merge.
538
676
 
539
677
        This is computed between versions a and b and their common
655
793
    def map(self, key):
656
794
        """Map key to an underlying storage identifier.
657
795
 
658
 
        :param key: A key tuple e.g. ('file-id', 'revision-id').
 
796
        :param key: A key tuple e.g. (b'file-id', b'revision-id').
659
797
        :return: An underlying storage identifier, specific to the partitioning
660
798
            mechanism.
661
799
        """
692
830
 
693
831
    def map(self, key):
694
832
        """See KeyMapper.map()."""
695
 
        return urllib.quote(self._map(key))
 
833
        return urlutils.quote(self._map(key))
696
834
 
697
835
    def unmap(self, partition_id):
698
836
        """See KeyMapper.unmap()."""
699
 
        return self._unmap(urllib.unquote(partition_id))
 
837
        return self._unmap(urlutils.unquote(partition_id))
700
838
 
701
839
 
702
840
class PrefixMapper(URLEscapeMapper):
707
845
 
708
846
    def _map(self, key):
709
847
        """See KeyMapper.map()."""
710
 
        return key[0]
 
848
        return key[0].decode('utf-8')
711
849
 
712
850
    def _unmap(self, partition_id):
713
851
        """See KeyMapper.unmap()."""
714
 
        return (partition_id,)
 
852
        return (partition_id.encode('utf-8'),)
715
853
 
716
854
 
717
855
class HashPrefixMapper(URLEscapeMapper):
723
861
    def _map(self, key):
724
862
        """See KeyMapper.map()."""
725
863
        prefix = self._escape(key[0])
726
 
        return "%02x/%s" % (adler32(prefix) & 0xff, prefix)
 
864
        return "%02x/%s" % (adler32(prefix) & 0xff, prefix.decode('utf-8'))
727
865
 
728
866
    def _escape(self, prefix):
729
867
        """No escaping needed here."""
731
869
 
732
870
    def _unmap(self, partition_id):
733
871
        """See KeyMapper.unmap()."""
734
 
        return (self._unescape(osutils.basename(partition_id)),)
 
872
        return (self._unescape(osutils.basename(partition_id)).encode('utf-8'),)
735
873
 
736
874
    def _unescape(self, basename):
737
875
        """No unescaping needed for HashPrefixMapper."""
744
882
    This mapper is for use with a transport based backend.
745
883
    """
746
884
 
747
 
    _safe = "abcdefghijklmnopqrstuvwxyz0123456789-_@,."
 
885
    _safe = bytearray(b"abcdefghijklmnopqrstuvwxyz0123456789-_@,.")
748
886
 
749
887
    def _escape(self, prefix):
750
888
        """Turn a key element into a filesystem safe string.
751
889
 
752
 
        This is similar to a plain urllib.quote, except
 
890
        This is similar to a plain urlutils.quote, except
753
891
        it uses specific safe characters, so that it doesn't
754
892
        have to translate a lot of valid file ids.
755
893
        """
756
894
        # @ does not get escaped. This is because it is a valid
757
895
        # filesystem character we use all the time, and it looks
758
896
        # 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)
 
897
        r = [(c in self._safe) and chr(c) or ('%%%02x' % c)
 
898
                for c in bytearray(prefix)]
 
899
        return ''.join(r).encode('ascii')
762
900
 
763
901
    def _unescape(self, basename):
764
902
        """Escaped names are easily unescaped by urlutils."""
765
 
        return urllib.unquote(basename)
 
903
        return urlutils.unquote(basename)
766
904
 
767
905
 
768
906
def make_versioned_files_factory(versioned_file_factory, mapper):
774
912
    """
775
913
    def factory(transport):
776
914
        return ThunkedVersionedFiles(transport, versioned_file_factory, mapper,
777
 
            lambda:True)
 
915
            lambda: True)
778
916
    return factory
779
917
 
780
918
 
789
927
 
790
928
    The keyspace is expressed via simple tuples. Any instance of VersionedFiles
791
929
    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
 
930
    all texts added to or retrieved from it. For instance, breezy uses
793
931
    instances with a key-size of 2 for storing user files in a repository, with
794
932
    the first element the fileid, and the second the version of that file.
795
933
 
796
934
    The use of tuples allows a single code base to support several different
797
935
    uses with only the mapping logic changing from instance to instance.
 
936
 
 
937
    :ivar _immediate_fallback_vfs: For subclasses that support stacking,
 
938
        this is a list of other VersionedFiles immediately underneath this
 
939
        one.  They may in turn each have further fallbacks.
798
940
    """
799
941
 
800
942
    def add_lines(self, key, parents, lines, parent_texts=None,
836
978
        """
837
979
        raise NotImplementedError(self.add_lines)
838
980
 
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.
843
 
 
844
 
        :param key: The key tuple of the text to add. If the last element is
845
 
            None, a CHK string will be generated during the addition.
846
 
        :param parents: The parents key tuples of the text to add.
847
 
        :param text: A string containing the text to be committed.
848
 
        :param nostore_sha: Raise ExistingContent and do not add the lines to
849
 
            the versioned file if the digest of the lines matches this.
850
 
        :param random_id: If True a random id has been selected rather than
851
 
            an id determined by some deterministic process such as a converter
852
 
            from a foreign VCS. When True the backend may choose not to check
853
 
            for uniqueness of the resulting key within the versioned file, so
854
 
            this should only be done when the result is expected to be unique
855
 
            anyway.
856
 
        :param check_content: If True, the lines supplied are verified to be
857
 
            bytestrings that are correctly formed lines.
858
 
        :return: The text sha1, the number of bytes in the text, and an opaque
859
 
                 representation of the inserted version which can be provided
860
 
                 back to future _add_text calls in the parent_texts dictionary.
861
 
        """
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)
868
 
 
869
981
    def add_mpdiffs(self, records):
870
982
        """Add mpdiffs to this VersionedFile.
871
983
 
891
1003
                continue
892
1004
            mpvf.add_version(chunks_to_lines(record.get_bytes_as('chunked')),
893
1005
                record.key, [])
894
 
        for (key, parent_keys, expected_sha1, mpdiff), lines in\
895
 
            zip(records, mpvf.get_line_list(versions)):
 
1006
        for (key, parent_keys, expected_sha1, mpdiff), lines in zip(
 
1007
                records, mpvf.get_line_list(versions)):
896
1008
            if len(parent_keys) == 1:
897
1009
                left_matching_blocks = list(mpdiff.get_matching_blocks(0,
898
1010
                    mpvf.get_diff(parent_keys[0]).num_lines()))
939
1051
    def _check_lines_not_unicode(self, lines):
940
1052
        """Check that lines being added to a versioned file are not unicode."""
941
1053
        for line in lines:
942
 
            if line.__class__ is not str:
 
1054
            if line.__class__ is not bytes:
943
1055
                raise errors.BzrBadParameterUnicode("lines")
944
1056
 
945
1057
    def _check_lines_are_lines(self, lines):
946
1058
        """Check that the lines really are full lines without inline EOL."""
947
1059
        for line in lines:
948
 
            if '\n' in line[:-1]:
 
1060
            if b'\n' in line[:-1]:
949
1061
                raise errors.BzrBadParameterContainsNewline("lines")
950
1062
 
951
1063
    def get_known_graph_ancestry(self, keys):
956
1068
        while pending:
957
1069
            this_parent_map = self.get_parent_map(pending)
958
1070
            parent_map.update(this_parent_map)
959
 
            pending = set()
960
 
            map(pending.update, this_parent_map.itervalues())
961
 
            pending = pending.difference(parent_map)
 
1071
            pending = set(itertools.chain.from_iterable(
 
1072
                viewvalues(this_parent_map)))
 
1073
            pending.difference_update(parent_map)
962
1074
        kg = _mod_graph.KnownGraph(parent_map)
963
1075
        return kg
964
1076
 
995
1107
        """
996
1108
        raise NotImplementedError(self.get_sha1s)
997
1109
 
998
 
    has_key = index._has_key_from_parent_map
 
1110
    __contains__ = index._has_key_from_parent_map
999
1111
 
1000
1112
    def get_missing_compression_parent_keys(self):
1001
1113
        """Return an iterable of keys of missing compression parents.
1047
1159
 
1048
1160
    def make_mpdiffs(self, keys):
1049
1161
        """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
 
1162
        generator = _MPDiffGenerator(self, keys)
 
1163
        return generator.compute_diffs()
 
1164
 
 
1165
    def get_annotator(self):
 
1166
        return annotate.Annotator(self)
1087
1167
 
1088
1168
    missing_keys = index._missing_keys_from_parent_map
1089
1169
 
1090
1170
    def _extract_blocks(self, version_id, source, target):
1091
1171
        return None
1092
1172
 
 
1173
    def _transitive_fallbacks(self):
 
1174
        """Return the whole stack of fallback versionedfiles.
 
1175
 
 
1176
        This VersionedFiles may have a list of fallbacks, but it doesn't
 
1177
        necessarily know about the whole stack going down, and it can't know
 
1178
        at open time because they may change after the objects are opened.
 
1179
        """
 
1180
        all_fallbacks = []
 
1181
        for a_vfs in self._immediate_fallback_vfs:
 
1182
            all_fallbacks.append(a_vfs)
 
1183
            all_fallbacks.extend(a_vfs._transitive_fallbacks())
 
1184
        return all_fallbacks
 
1185
 
1093
1186
 
1094
1187
class ThunkedVersionedFiles(VersionedFiles):
1095
1188
    """Storage for many versioned files thunked onto a 'VersionedFile' class.
1159
1252
            result.append((prefix + (origin,), line))
1160
1253
        return result
1161
1254
 
1162
 
    def get_annotator(self):
1163
 
        return annotate.Annotator(self)
1164
 
 
1165
1255
    def check(self, progress_bar=None, keys=None):
1166
1256
        """See VersionedFiles.check()."""
1167
1257
        # XXX: This is over-enthusiastic but as we only thunk for Weaves today
1181
1271
        """
1182
1272
        prefixes = self._partition_keys(keys)
1183
1273
        result = {}
1184
 
        for prefix, suffixes in prefixes.items():
 
1274
        for prefix, suffixes in viewitems(prefixes):
1185
1275
            path = self._mapper.map(prefix)
1186
1276
            vf = self._get_vf(path)
1187
1277
            parent_map = vf.get_parent_map(suffixes)
1188
 
            for key, parents in parent_map.items():
 
1278
            for key, parents in viewitems(parent_map):
1189
1279
                result[prefix + (key,)] = tuple(
1190
1280
                    prefix + (parent,) for parent in parents)
1191
1281
        return result
1204
1294
            prefix_keys.append(key[-1])
1205
1295
        return result
1206
1296
 
1207
 
    def _get_all_prefixes(self):
 
1297
    def _iter_all_prefixes(self):
1208
1298
        # Identify all key prefixes.
1209
1299
        # XXX: A bit hacky, needs polish.
1210
 
        if type(self._mapper) == ConstantMapper:
 
1300
        if isinstance(self._mapper, ConstantMapper):
1211
1301
            paths = [self._mapper.map(())]
1212
1302
            prefixes = [()]
1213
1303
        else:
1237
1327
    def _iter_keys_vf(self, keys):
1238
1328
        prefixes = self._partition_keys(keys)
1239
1329
        sha1s = {}
1240
 
        for prefix, suffixes in prefixes.items():
 
1330
        for prefix, suffixes in viewitems(prefixes):
1241
1331
            path = self._mapper.map(prefix)
1242
1332
            vf = self._get_vf(path)
1243
1333
            yield prefix, suffixes, vf
1245
1335
    def get_sha1s(self, keys):
1246
1336
        """See VersionedFiles.get_sha1s()."""
1247
1337
        sha1s = {}
1248
 
        for prefix,suffixes, vf in self._iter_keys_vf(keys):
 
1338
        for prefix, suffixes, vf in self._iter_keys_vf(keys):
1249
1339
            vf_sha1s = vf.get_sha1s(suffixes)
1250
 
            for suffix, sha1 in vf_sha1s.iteritems():
 
1340
            for suffix, sha1 in viewitems(vf_sha1s):
1251
1341
                sha1s[prefix + (suffix,)] = sha1
1252
1342
        return sha1s
1253
1343
 
1299
1389
                yield line, prefix + (version,)
1300
1390
 
1301
1391
    def _iter_all_components(self):
1302
 
        for path, prefix in self._get_all_prefixes():
 
1392
        for path, prefix in self._iter_all_prefixes():
1303
1393
            yield prefix, self._get_vf(path)
1304
1394
 
1305
1395
    def keys(self):
1311
1401
        return result
1312
1402
 
1313
1403
 
 
1404
class VersionedFilesWithFallbacks(VersionedFiles):
 
1405
 
 
1406
    def without_fallbacks(self):
 
1407
        """Return a clone of this object without any fallbacks configured."""
 
1408
        raise NotImplementedError(self.without_fallbacks)
 
1409
 
 
1410
    def add_fallback_versioned_files(self, a_versioned_files):
 
1411
        """Add a source of texts for texts not present in this knit.
 
1412
 
 
1413
        :param a_versioned_files: A VersionedFiles object.
 
1414
        """
 
1415
        raise NotImplementedError(self.add_fallback_versioned_files)
 
1416
 
 
1417
    def get_known_graph_ancestry(self, keys):
 
1418
        """Get a KnownGraph instance with the ancestry of keys."""
 
1419
        parent_map, missing_keys = self._index.find_ancestry(keys)
 
1420
        for fallback in self._transitive_fallbacks():
 
1421
            if not missing_keys:
 
1422
                break
 
1423
            (f_parent_map, f_missing_keys) = fallback._index.find_ancestry(
 
1424
                                                missing_keys)
 
1425
            parent_map.update(f_parent_map)
 
1426
            missing_keys = f_missing_keys
 
1427
        kg = _mod_graph.KnownGraph(parent_map)
 
1428
        return kg
 
1429
 
 
1430
 
1314
1431
class _PlanMergeVersionedFile(VersionedFiles):
1315
1432
    """A VersionedFile for uncommitted and committed texts.
1316
1433
 
1337
1454
        # line data for locally held keys.
1338
1455
        self._lines = {}
1339
1456
        # key lookup providers
1340
 
        self._providers = [DictParentsProvider(self._parents)]
 
1457
        self._providers = [_mod_graph.DictParentsProvider(self._parents)]
1341
1458
 
1342
1459
    def plan_merge(self, ver_a, ver_b, base=None):
1343
1460
        """See VersionedFile.plan_merge"""
1344
 
        from bzrlib.merge import _PlanMerge
 
1461
        from ..merge import _PlanMerge
1345
1462
        if base is None:
1346
1463
            return _PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge()
1347
1464
        old_plan = list(_PlanMerge(ver_a, base, self, (self._file_id,)).plan_merge())
1349
1466
        return _PlanMerge._subtract_plans(old_plan, new_plan)
1350
1467
 
1351
1468
    def plan_lca_merge(self, ver_a, ver_b, base=None):
1352
 
        from bzrlib.merge import _PlanLCAMerge
1353
 
        graph = Graph(self)
 
1469
        from ..merge import _PlanLCAMerge
 
1470
        graph = _mod_graph.Graph(self)
1354
1471
        new_plan = _PlanLCAMerge(ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
1355
1472
        if base is None:
1356
1473
            return new_plan
1363
1480
        Lines are added locally, not to fallback versionedfiles.  Also, ghosts
1364
1481
        are permitted.  Only reserved ids are permitted.
1365
1482
        """
1366
 
        if type(key) is not tuple:
 
1483
        if not isinstance(key, tuple):
1367
1484
            raise TypeError(key)
1368
1485
        if not revision.is_reserved_id(key[-1]):
1369
1486
            raise ValueError('Only reserved ids may be used')
1408
1525
            result[revision.NULL_REVISION] = ()
1409
1526
        self._providers = self._providers[:1] + self.fallback_versionedfiles
1410
1527
        result.update(
1411
 
            StackedParentsProvider(self._providers).get_parent_map(keys))
1412
 
        for key, parents in result.iteritems():
 
1528
            _mod_graph.StackedParentsProvider(
 
1529
                self._providers).get_parent_map(keys))
 
1530
        for key, parents in viewitems(result):
1413
1531
            if parents == ():
1414
1532
                result[key] = (revision.NULL_REVISION,)
1415
1533
        return result
1588
1706
 
1589
1707
    def get_parent_map(self, keys):
1590
1708
        """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()])
 
1709
        parent_view = viewitems(self._get_parent_map(k for (k,) in keys))
 
1710
        return dict(((k,), tuple((p,) for p in v)) for k, v in parent_view)
1593
1711
 
1594
1712
    def get_sha1s(self, keys):
1595
1713
        """See VersionedFiles.get_sha1s."""
1624
1742
                yield (l, key)
1625
1743
 
1626
1744
 
 
1745
class NoDupeAddLinesDecorator(object):
 
1746
    """Decorator for a VersionedFiles that skips doing an add_lines if the key
 
1747
    is already present.
 
1748
    """
 
1749
 
 
1750
    def __init__(self, store):
 
1751
        self._store = store
 
1752
 
 
1753
    def add_lines(self, key, parents, lines, parent_texts=None,
 
1754
            left_matching_blocks=None, nostore_sha=None, random_id=False,
 
1755
            check_content=True):
 
1756
        """See VersionedFiles.add_lines.
 
1757
        
 
1758
        This implementation may return None as the third element of the return
 
1759
        value when the original store wouldn't.
 
1760
        """
 
1761
        if nostore_sha:
 
1762
            raise NotImplementedError(
 
1763
                "NoDupeAddLinesDecorator.add_lines does not implement the "
 
1764
                "nostore_sha behaviour.")
 
1765
        if key[-1] is None:
 
1766
            sha1 = osutils.sha_strings(lines)
 
1767
            key = (b"sha1:" + sha1,)
 
1768
        else:
 
1769
            sha1 = None
 
1770
        if key in self._store.get_parent_map([key]):
 
1771
            # This key has already been inserted, so don't do it again.
 
1772
            if sha1 is None:
 
1773
                sha1 = osutils.sha_strings(lines)
 
1774
            return sha1, sum(map(len, lines)), None
 
1775
        return self._store.add_lines(key, parents, lines,
 
1776
                parent_texts=parent_texts,
 
1777
                left_matching_blocks=left_matching_blocks,
 
1778
                nostore_sha=nostore_sha, random_id=random_id,
 
1779
                check_content=check_content)
 
1780
 
 
1781
    def __getattr__(self, name):
 
1782
        return getattr(self._store, name)
 
1783
 
 
1784
 
1627
1785
def network_bytes_to_kind_and_offset(network_bytes):
1628
1786
    """Strip of a record kind from the front of network_bytes.
1629
1787
 
1630
1788
    :param network_bytes: The bytes of a record.
1631
1789
    :return: A tuple (storage_kind, offset_of_remaining_bytes)
1632
1790
    """
1633
 
    line_end = network_bytes.find('\n')
1634
 
    storage_kind = network_bytes[:line_end]
 
1791
    line_end = network_bytes.find(b'\n')
 
1792
    storage_kind = network_bytes[:line_end].decode('ascii')
1635
1793
    return storage_kind, line_end + 1
1636
1794
 
1637
1795
 
1673
1831
    meta_len, = struct.unpack('!L', bytes[line_end:line_end+4])
1674
1832
    record_meta = bytes[line_end+4:line_end+4+meta_len]
1675
1833
    key, parents = bencode.bdecode_as_tuple(record_meta)
1676
 
    if parents == 'nil':
 
1834
    if parents == b'nil':
1677
1835
        parents = None
1678
1836
    fulltext = bytes[line_end+4+meta_len:]
1679
1837
    return [FulltextContentFactory(key, parents, None, fulltext)]
1685
1843
 
1686
1844
def record_to_fulltext_bytes(record):
1687
1845
    if record.parents is None:
1688
 
        parents = 'nil'
 
1846
        parents = b'nil'
1689
1847
    else:
1690
1848
        parents = record.parents
1691
1849
    record_meta = bencode.bencode((record.key, parents))
1692
1850
    record_content = record.get_bytes_as('fulltext')
1693
 
    return "fulltext\n%s%s%s" % (
 
1851
    return b"fulltext\n%s%s%s" % (
1694
1852
        _length_prefix(record_meta), record_meta, record_content)
1695
1853
 
1696
1854
 
1705
1863
    # gc-optimal ordering is approximately reverse topological,
1706
1864
    # properly grouped by file-id.
1707
1865
    per_prefix_map = {}
1708
 
    for item in parent_map.iteritems():
 
1866
    for item in viewitems(parent_map):
1709
1867
        key = item[0]
1710
 
        if isinstance(key, str) or len(key) == 1:
1711
 
            prefix = ''
 
1868
        if isinstance(key, bytes) or len(key) == 1:
 
1869
            prefix = b''
1712
1870
        else:
1713
1871
            prefix = key[0]
1714
1872
        try:
1720
1878
    for prefix in sorted(per_prefix_map):
1721
1879
        present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
1722
1880
    return present_keys
 
1881
 
 
1882
 
 
1883
class _KeyRefs(object):
 
1884
 
 
1885
    def __init__(self, track_new_keys=False):
 
1886
        # dict mapping 'key' to 'set of keys referring to that key'
 
1887
        self.refs = {}
 
1888
        if track_new_keys:
 
1889
            # set remembering all new keys
 
1890
            self.new_keys = set()
 
1891
        else:
 
1892
            self.new_keys = None
 
1893
 
 
1894
    def clear(self):
 
1895
        if self.refs:
 
1896
            self.refs.clear()
 
1897
        if self.new_keys:
 
1898
            self.new_keys.clear()
 
1899
 
 
1900
    def add_references(self, key, refs):
 
1901
        # Record the new references
 
1902
        for referenced in refs:
 
1903
            try:
 
1904
                needed_by = self.refs[referenced]
 
1905
            except KeyError:
 
1906
                needed_by = self.refs[referenced] = set()
 
1907
            needed_by.add(key)
 
1908
        # Discard references satisfied by the new key
 
1909
        self.add_key(key)
 
1910
 
 
1911
    def get_new_keys(self):
 
1912
        return self.new_keys
 
1913
 
 
1914
    def get_unsatisfied_refs(self):
 
1915
        return self.refs.keys()
 
1916
 
 
1917
    def _satisfy_refs_for_key(self, key):
 
1918
        try:
 
1919
            del self.refs[key]
 
1920
        except KeyError:
 
1921
            # No keys depended on this key.  That's ok.
 
1922
            pass
 
1923
 
 
1924
    def add_key(self, key):
 
1925
        # satisfy refs for key, and remember that we've seen this key.
 
1926
        self._satisfy_refs_for_key(key)
 
1927
        if self.new_keys is not None:
 
1928
            self.new_keys.add(key)
 
1929
 
 
1930
    def satisfy_refs_for_keys(self, keys):
 
1931
        for key in keys:
 
1932
            self._satisfy_refs_for_key(key)
 
1933
 
 
1934
    def get_referrers(self):
 
1935
        return set(itertools.chain.from_iterable(viewvalues(self.refs)))
 
1936
 
 
1937
 
 
1938