/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-03-30 13:59:35 UTC
  • mto: This revision was merged to the branch mainline in revision 6932.
  • Revision ID: jelmer@jelmer.uk-20180330135935-l7i1riyjeud34ra7
Add Tree.versionable_kind.

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
 
206
208
            yield record
207
209
 
208
210
 
 
211
class _MPDiffGenerator(object):
 
212
    """Pull out the functionality for generating mp_diffs."""
 
213
 
 
214
    def __init__(self, vf, keys):
 
215
        self.vf = vf
 
216
        # This is the order the keys were requested in
 
217
        self.ordered_keys = tuple(keys)
 
218
        # keys + their parents, what we need to compute the diffs
 
219
        self.needed_keys = ()
 
220
        # Map from key: mp_diff
 
221
        self.diffs = {}
 
222
        # Map from key: parents_needed (may have ghosts)
 
223
        self.parent_map = {}
 
224
        # Parents that aren't present
 
225
        self.ghost_parents = ()
 
226
        # Map from parent_key => number of children for this text
 
227
        self.refcounts = {}
 
228
        # Content chunks that are cached while we still need them
 
229
        self.chunks = {}
 
230
 
 
231
    def _find_needed_keys(self):
 
232
        """Find the set of keys we need to request.
 
233
 
 
234
        This includes all the original keys passed in, and the non-ghost
 
235
        parents of those keys.
 
236
 
 
237
        :return: (needed_keys, refcounts)
 
238
            needed_keys is the set of all texts we need to extract
 
239
            refcounts is a dict of {key: num_children} letting us know when we
 
240
                no longer need to cache a given parent text
 
241
        """
 
242
        # All the keys and their parents
 
243
        needed_keys = set(self.ordered_keys)
 
244
        parent_map = self.vf.get_parent_map(needed_keys)
 
245
        self.parent_map = parent_map
 
246
        # TODO: Should we be using a different construct here? I think this
 
247
        #       uses difference_update internally, and we expect the result to
 
248
        #       be tiny
 
249
        missing_keys = needed_keys.difference(parent_map)
 
250
        if missing_keys:
 
251
            raise errors.RevisionNotPresent(list(missing_keys)[0], self.vf)
 
252
        # Parents that might be missing. They are allowed to be ghosts, but we
 
253
        # should check for them
 
254
        refcounts = {}
 
255
        setdefault = refcounts.setdefault
 
256
        just_parents = set()
 
257
        for child_key, parent_keys in viewitems(parent_map):
 
258
            if not parent_keys:
 
259
                # parent_keys may be None if a given VersionedFile claims to
 
260
                # not support graph operations.
 
261
                continue
 
262
            just_parents.update(parent_keys)
 
263
            needed_keys.update(parent_keys)
 
264
            for p in parent_keys:
 
265
                refcounts[p] = setdefault(p, 0) + 1
 
266
        just_parents.difference_update(parent_map)
 
267
        # Remove any parents that are actually ghosts from the needed set
 
268
        self.present_parents = set(self.vf.get_parent_map(just_parents))
 
269
        self.ghost_parents = just_parents.difference(self.present_parents)
 
270
        needed_keys.difference_update(self.ghost_parents)
 
271
        self.needed_keys = needed_keys
 
272
        self.refcounts = refcounts
 
273
        return needed_keys, refcounts
 
274
 
 
275
    def _compute_diff(self, key, parent_lines, lines):
 
276
        """Compute a single mp_diff, and store it in self._diffs"""
 
277
        if len(parent_lines) > 0:
 
278
            # XXX: _extract_blocks is not usefully defined anywhere...
 
279
            #      It was meant to extract the left-parent diff without
 
280
            #      having to recompute it for Knit content (pack-0.92,
 
281
            #      etc). That seems to have regressed somewhere
 
282
            left_parent_blocks = self.vf._extract_blocks(key,
 
283
                parent_lines[0], lines)
 
284
        else:
 
285
            left_parent_blocks = None
 
286
        diff = multiparent.MultiParent.from_lines(lines,
 
287
                    parent_lines, left_parent_blocks)
 
288
        self.diffs[key] = diff
 
289
 
 
290
    def _process_one_record(self, key, this_chunks):
 
291
        parent_keys = None
 
292
        if key in self.parent_map:
 
293
            # This record should be ready to diff, since we requested
 
294
            # content in 'topological' order
 
295
            parent_keys = self.parent_map.pop(key)
 
296
            # If a VersionedFile claims 'no-graph' support, then it may return
 
297
            # None for any parent request, so we replace it with an empty tuple
 
298
            if parent_keys is None:
 
299
                parent_keys = ()
 
300
            parent_lines = []
 
301
            for p in parent_keys:
 
302
                # Alternatively we could check p not in self.needed_keys, but
 
303
                # ghost_parents should be tiny versus huge
 
304
                if p in self.ghost_parents:
 
305
                    continue
 
306
                refcount = self.refcounts[p]
 
307
                if refcount == 1: # Last child reference
 
308
                    self.refcounts.pop(p)
 
309
                    parent_chunks = self.chunks.pop(p)
 
310
                else:
 
311
                    self.refcounts[p] = refcount - 1
 
312
                    parent_chunks = self.chunks[p]
 
313
                p_lines = osutils.chunks_to_lines(parent_chunks)
 
314
                # TODO: Should we cache the line form? We did the
 
315
                #       computation to get it, but storing it this way will
 
316
                #       be less memory efficient...
 
317
                parent_lines.append(p_lines)
 
318
                del p_lines
 
319
            lines = osutils.chunks_to_lines(this_chunks)
 
320
            # Since we needed the lines, we'll go ahead and cache them this way
 
321
            this_chunks = lines
 
322
            self._compute_diff(key, parent_lines, lines)
 
323
            del lines
 
324
        # Is this content required for any more children?
 
325
        if key in self.refcounts:
 
326
            self.chunks[key] = this_chunks
 
327
 
 
328
    def _extract_diffs(self):
 
329
        needed_keys, refcounts = self._find_needed_keys()
 
330
        for record in self.vf.get_record_stream(needed_keys,
 
331
                                                'topological', True):
 
332
            if record.storage_kind == 'absent':
 
333
                raise errors.RevisionNotPresent(record.key, self.vf)
 
334
            self._process_one_record(record.key,
 
335
                                     record.get_bytes_as('chunked'))
 
336
        
 
337
    def compute_diffs(self):
 
338
        self._extract_diffs()
 
339
        dpop = self.diffs.pop
 
340
        return [dpop(k) for k in self.ordered_keys]
 
341
 
 
342
 
209
343
class VersionedFile(object):
210
344
    """Versioned text file storage.
211
345
 
330
464
    def _check_lines_not_unicode(self, lines):
331
465
        """Check that lines being added to a versioned file are not unicode."""
332
466
        for line in lines:
333
 
            if line.__class__ is not str:
 
467
            if not isinstance(line, bytes):
334
468
                raise errors.BzrBadParameterUnicode("lines")
335
469
 
336
470
    def _check_lines_are_lines(self, lines):
337
471
        """Check that the lines really are full lines without inline EOL."""
338
472
        for line in lines:
339
 
            if '\n' in line[:-1]:
 
473
            if b'\n' in line[:-1]:
340
474
                raise errors.BzrBadParameterContainsNewline("lines")
341
475
 
342
476
    def get_format_signature(self):
348
482
 
349
483
    def make_mpdiffs(self, version_ids):
350
484
        """Create multiparent diffs for specified versions."""
 
485
        # XXX: Can't use _MPDiffGenerator just yet. This is because version_ids
 
486
        #      is a list of strings, not keys. And while self.get_record_stream
 
487
        #      is supported, it takes *keys*, while self.get_parent_map() takes
 
488
        #      strings... *sigh*
351
489
        knit_versions = set()
352
490
        knit_versions.update(version_ids)
353
491
        parent_map = self.get_parent_map(version_ids)
357
495
            except KeyError:
358
496
                raise errors.RevisionNotPresent(version_id, self)
359
497
        # We need to filter out ghosts, because we can't diff against them.
360
 
        knit_versions = set(self.get_parent_map(knit_versions).keys())
 
498
        knit_versions = set(self.get_parent_map(knit_versions))
361
499
        lines = dict(zip(knit_versions,
362
500
            self._get_lf_split_line_list(knit_versions)))
363
501
        diffs = []
401
539
        for version, parent_ids, expected_sha1, mpdiff in records:
402
540
            needed_parents.update(p for p in parent_ids
403
541
                                  if not mpvf.has_version(p))
404
 
        present_parents = set(self.get_parent_map(needed_parents).keys())
 
542
        present_parents = set(self.get_parent_map(needed_parents))
405
543
        for parent_id, lines in zip(present_parents,
406
 
                                 self._get_lf_split_line_list(present_parents)):
 
544
                self._get_lf_split_line_list(present_parents)):
407
545
            mpvf.add_version(lines, parent_id, [])
408
 
        for (version, parent_ids, expected_sha1, mpdiff), lines in\
409
 
            zip(records, mpvf.get_line_list(versions)):
 
546
        for (version, parent_ids, expected_sha1, mpdiff), lines in zip(
 
547
                records, mpvf.get_line_list(versions)):
410
548
            if len(parent_ids) == 1:
411
549
                left_matching_blocks = list(mpdiff.get_matching_blocks(0,
412
550
                    mpvf.get_diff(parent_ids[0]).num_lines()))
454
592
        raise NotImplementedError(self.get_lines)
455
593
 
456
594
    def _get_lf_split_line_list(self, version_ids):
457
 
        return [StringIO(t).readlines() for t in self.get_texts(version_ids)]
 
595
        return [BytesIO(t).readlines() for t in self.get_texts(version_ids)]
458
596
 
459
597
    def get_ancestry(self, version_ids, topo_sorted=True):
460
598
        """Return a list of all ancestors of given version(s). This
465
603
 
466
604
        Must raise RevisionNotPresent if any of the given versions are
467
605
        not present in file history."""
468
 
        if isinstance(version_ids, basestring):
469
 
            version_ids = [version_ids]
470
606
        raise NotImplementedError(self.get_ancestry)
471
607
 
472
608
    def get_ancestry_with_ghosts(self, version_ids):
533
669
        """
534
670
        raise NotImplementedError(self.iter_lines_added_or_present_in_versions)
535
671
 
536
 
    def plan_merge(self, ver_a, ver_b):
 
672
    def plan_merge(self, ver_a, ver_b, base=None):
537
673
        """Return pseudo-annotation indicating how the two versions merge.
538
674
 
539
675
        This is computed between versions a and b and their common
692
828
 
693
829
    def map(self, key):
694
830
        """See KeyMapper.map()."""
695
 
        return urllib.quote(self._map(key))
 
831
        return urlutils.quote(self._map(key))
696
832
 
697
833
    def unmap(self, partition_id):
698
834
        """See KeyMapper.unmap()."""
699
 
        return self._unmap(urllib.unquote(partition_id))
 
835
        return self._unmap(urlutils.unquote(partition_id))
700
836
 
701
837
 
702
838
class PrefixMapper(URLEscapeMapper):
749
885
    def _escape(self, prefix):
750
886
        """Turn a key element into a filesystem safe string.
751
887
 
752
 
        This is similar to a plain urllib.quote, except
 
888
        This is similar to a plain urlutils.quote, except
753
889
        it uses specific safe characters, so that it doesn't
754
890
        have to translate a lot of valid file ids.
755
891
        """
762
898
 
763
899
    def _unescape(self, basename):
764
900
        """Escaped names are easily unescaped by urlutils."""
765
 
        return urllib.unquote(basename)
 
901
        return urlutils.unquote(basename)
766
902
 
767
903
 
768
904
def make_versioned_files_factory(versioned_file_factory, mapper):
789
925
 
790
926
    The keyspace is expressed via simple tuples. Any instance of VersionedFiles
791
927
    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
 
928
    all texts added to or retrieved from it. For instance, breezy uses
793
929
    instances with a key-size of 2 for storing user files in a repository, with
794
930
    the first element the fileid, and the second the version of that file.
795
931
 
796
932
    The use of tuples allows a single code base to support several different
797
933
    uses with only the mapping logic changing from instance to instance.
 
934
 
 
935
    :ivar _immediate_fallback_vfs: For subclasses that support stacking,
 
936
        this is a list of other VersionedFiles immediately underneath this
 
937
        one.  They may in turn each have further fallbacks.
798
938
    """
799
939
 
800
940
    def add_lines(self, key, parents, lines, parent_texts=None,
836
976
        """
837
977
        raise NotImplementedError(self.add_lines)
838
978
 
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
979
    def add_mpdiffs(self, records):
870
980
        """Add mpdiffs to this VersionedFile.
871
981
 
891
1001
                continue
892
1002
            mpvf.add_version(chunks_to_lines(record.get_bytes_as('chunked')),
893
1003
                record.key, [])
894
 
        for (key, parent_keys, expected_sha1, mpdiff), lines in\
895
 
            zip(records, mpvf.get_line_list(versions)):
 
1004
        for (key, parent_keys, expected_sha1, mpdiff), lines in zip(
 
1005
                records, mpvf.get_line_list(versions)):
896
1006
            if len(parent_keys) == 1:
897
1007
                left_matching_blocks = list(mpdiff.get_matching_blocks(0,
898
1008
                    mpvf.get_diff(parent_keys[0]).num_lines()))
939
1049
    def _check_lines_not_unicode(self, lines):
940
1050
        """Check that lines being added to a versioned file are not unicode."""
941
1051
        for line in lines:
942
 
            if line.__class__ is not str:
 
1052
            if line.__class__ is not bytes:
943
1053
                raise errors.BzrBadParameterUnicode("lines")
944
1054
 
945
1055
    def _check_lines_are_lines(self, lines):
946
1056
        """Check that the lines really are full lines without inline EOL."""
947
1057
        for line in lines:
948
 
            if '\n' in line[:-1]:
 
1058
            if b'\n' in line[:-1]:
949
1059
                raise errors.BzrBadParameterContainsNewline("lines")
950
1060
 
951
1061
    def get_known_graph_ancestry(self, keys):
956
1066
        while pending:
957
1067
            this_parent_map = self.get_parent_map(pending)
958
1068
            parent_map.update(this_parent_map)
959
 
            pending = set()
960
 
            map(pending.update, this_parent_map.itervalues())
961
 
            pending = pending.difference(parent_map)
 
1069
            pending = set(itertools.chain.from_iterable(
 
1070
                viewvalues(this_parent_map)))
 
1071
            pending.difference_update(parent_map)
962
1072
        kg = _mod_graph.KnownGraph(parent_map)
963
1073
        return kg
964
1074
 
995
1105
        """
996
1106
        raise NotImplementedError(self.get_sha1s)
997
1107
 
998
 
    has_key = index._has_key_from_parent_map
 
1108
    __contains__ = index._has_key_from_parent_map
999
1109
 
1000
1110
    def get_missing_compression_parent_keys(self):
1001
1111
        """Return an iterable of keys of missing compression parents.
1047
1157
 
1048
1158
    def make_mpdiffs(self, keys):
1049
1159
        """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
 
1160
        generator = _MPDiffGenerator(self, keys)
 
1161
        return generator.compute_diffs()
 
1162
 
 
1163
    def get_annotator(self):
 
1164
        return annotate.Annotator(self)
1087
1165
 
1088
1166
    missing_keys = index._missing_keys_from_parent_map
1089
1167
 
1090
1168
    def _extract_blocks(self, version_id, source, target):
1091
1169
        return None
1092
1170
 
 
1171
    def _transitive_fallbacks(self):
 
1172
        """Return the whole stack of fallback versionedfiles.
 
1173
 
 
1174
        This VersionedFiles may have a list of fallbacks, but it doesn't
 
1175
        necessarily know about the whole stack going down, and it can't know
 
1176
        at open time because they may change after the objects are opened.
 
1177
        """
 
1178
        all_fallbacks = []
 
1179
        for a_vfs in self._immediate_fallback_vfs:
 
1180
            all_fallbacks.append(a_vfs)
 
1181
            all_fallbacks.extend(a_vfs._transitive_fallbacks())
 
1182
        return all_fallbacks
 
1183
 
1093
1184
 
1094
1185
class ThunkedVersionedFiles(VersionedFiles):
1095
1186
    """Storage for many versioned files thunked onto a 'VersionedFile' class.
1159
1250
            result.append((prefix + (origin,), line))
1160
1251
        return result
1161
1252
 
1162
 
    def get_annotator(self):
1163
 
        return annotate.Annotator(self)
1164
 
 
1165
1253
    def check(self, progress_bar=None, keys=None):
1166
1254
        """See VersionedFiles.check()."""
1167
1255
        # XXX: This is over-enthusiastic but as we only thunk for Weaves today
1181
1269
        """
1182
1270
        prefixes = self._partition_keys(keys)
1183
1271
        result = {}
1184
 
        for prefix, suffixes in prefixes.items():
 
1272
        for prefix, suffixes in viewitems(prefixes):
1185
1273
            path = self._mapper.map(prefix)
1186
1274
            vf = self._get_vf(path)
1187
1275
            parent_map = vf.get_parent_map(suffixes)
1188
 
            for key, parents in parent_map.items():
 
1276
            for key, parents in viewitems(parent_map):
1189
1277
                result[prefix + (key,)] = tuple(
1190
1278
                    prefix + (parent,) for parent in parents)
1191
1279
        return result
1204
1292
            prefix_keys.append(key[-1])
1205
1293
        return result
1206
1294
 
1207
 
    def _get_all_prefixes(self):
 
1295
    def _iter_all_prefixes(self):
1208
1296
        # Identify all key prefixes.
1209
1297
        # XXX: A bit hacky, needs polish.
1210
 
        if type(self._mapper) == ConstantMapper:
 
1298
        if isinstance(self._mapper, ConstantMapper):
1211
1299
            paths = [self._mapper.map(())]
1212
1300
            prefixes = [()]
1213
1301
        else:
1237
1325
    def _iter_keys_vf(self, keys):
1238
1326
        prefixes = self._partition_keys(keys)
1239
1327
        sha1s = {}
1240
 
        for prefix, suffixes in prefixes.items():
 
1328
        for prefix, suffixes in viewitems(prefixes):
1241
1329
            path = self._mapper.map(prefix)
1242
1330
            vf = self._get_vf(path)
1243
1331
            yield prefix, suffixes, vf
1245
1333
    def get_sha1s(self, keys):
1246
1334
        """See VersionedFiles.get_sha1s()."""
1247
1335
        sha1s = {}
1248
 
        for prefix,suffixes, vf in self._iter_keys_vf(keys):
 
1336
        for prefix, suffixes, vf in self._iter_keys_vf(keys):
1249
1337
            vf_sha1s = vf.get_sha1s(suffixes)
1250
 
            for suffix, sha1 in vf_sha1s.iteritems():
 
1338
            for suffix, sha1 in viewitems(vf_sha1s):
1251
1339
                sha1s[prefix + (suffix,)] = sha1
1252
1340
        return sha1s
1253
1341
 
1299
1387
                yield line, prefix + (version,)
1300
1388
 
1301
1389
    def _iter_all_components(self):
1302
 
        for path, prefix in self._get_all_prefixes():
 
1390
        for path, prefix in self._iter_all_prefixes():
1303
1391
            yield prefix, self._get_vf(path)
1304
1392
 
1305
1393
    def keys(self):
1311
1399
        return result
1312
1400
 
1313
1401
 
 
1402
class VersionedFilesWithFallbacks(VersionedFiles):
 
1403
 
 
1404
    def without_fallbacks(self):
 
1405
        """Return a clone of this object without any fallbacks configured."""
 
1406
        raise NotImplementedError(self.without_fallbacks)
 
1407
 
 
1408
    def add_fallback_versioned_files(self, a_versioned_files):
 
1409
        """Add a source of texts for texts not present in this knit.
 
1410
 
 
1411
        :param a_versioned_files: A VersionedFiles object.
 
1412
        """
 
1413
        raise NotImplementedError(self.add_fallback_versioned_files)
 
1414
 
 
1415
    def get_known_graph_ancestry(self, keys):
 
1416
        """Get a KnownGraph instance with the ancestry of keys."""
 
1417
        parent_map, missing_keys = self._index.find_ancestry(keys)
 
1418
        for fallback in self._transitive_fallbacks():
 
1419
            if not missing_keys:
 
1420
                break
 
1421
            (f_parent_map, f_missing_keys) = fallback._index.find_ancestry(
 
1422
                                                missing_keys)
 
1423
            parent_map.update(f_parent_map)
 
1424
            missing_keys = f_missing_keys
 
1425
        kg = _mod_graph.KnownGraph(parent_map)
 
1426
        return kg
 
1427
 
 
1428
 
1314
1429
class _PlanMergeVersionedFile(VersionedFiles):
1315
1430
    """A VersionedFile for uncommitted and committed texts.
1316
1431
 
1337
1452
        # line data for locally held keys.
1338
1453
        self._lines = {}
1339
1454
        # key lookup providers
1340
 
        self._providers = [DictParentsProvider(self._parents)]
 
1455
        self._providers = [_mod_graph.DictParentsProvider(self._parents)]
1341
1456
 
1342
1457
    def plan_merge(self, ver_a, ver_b, base=None):
1343
1458
        """See VersionedFile.plan_merge"""
1344
 
        from bzrlib.merge import _PlanMerge
 
1459
        from ..merge import _PlanMerge
1345
1460
        if base is None:
1346
1461
            return _PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge()
1347
1462
        old_plan = list(_PlanMerge(ver_a, base, self, (self._file_id,)).plan_merge())
1349
1464
        return _PlanMerge._subtract_plans(old_plan, new_plan)
1350
1465
 
1351
1466
    def plan_lca_merge(self, ver_a, ver_b, base=None):
1352
 
        from bzrlib.merge import _PlanLCAMerge
1353
 
        graph = Graph(self)
 
1467
        from ..merge import _PlanLCAMerge
 
1468
        graph = _mod_graph.Graph(self)
1354
1469
        new_plan = _PlanLCAMerge(ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
1355
1470
        if base is None:
1356
1471
            return new_plan
1363
1478
        Lines are added locally, not to fallback versionedfiles.  Also, ghosts
1364
1479
        are permitted.  Only reserved ids are permitted.
1365
1480
        """
1366
 
        if type(key) is not tuple:
 
1481
        if not isinstance(key, tuple):
1367
1482
            raise TypeError(key)
1368
1483
        if not revision.is_reserved_id(key[-1]):
1369
1484
            raise ValueError('Only reserved ids may be used')
1408
1523
            result[revision.NULL_REVISION] = ()
1409
1524
        self._providers = self._providers[:1] + self.fallback_versionedfiles
1410
1525
        result.update(
1411
 
            StackedParentsProvider(self._providers).get_parent_map(keys))
1412
 
        for key, parents in result.iteritems():
 
1526
            _mod_graph.StackedParentsProvider(
 
1527
                self._providers).get_parent_map(keys))
 
1528
        for key, parents in viewitems(result):
1413
1529
            if parents == ():
1414
1530
                result[key] = (revision.NULL_REVISION,)
1415
1531
        return result
1588
1704
 
1589
1705
    def get_parent_map(self, keys):
1590
1706
        """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()])
 
1707
        parent_view = viewitems(self._get_parent_map(k for (k,) in keys))
 
1708
        return dict(((k,), tuple((p,) for p in v)) for k, v in parent_view)
1593
1709
 
1594
1710
    def get_sha1s(self, keys):
1595
1711
        """See VersionedFiles.get_sha1s."""
1624
1740
                yield (l, key)
1625
1741
 
1626
1742
 
 
1743
class NoDupeAddLinesDecorator(object):
 
1744
    """Decorator for a VersionedFiles that skips doing an add_lines if the key
 
1745
    is already present.
 
1746
    """
 
1747
 
 
1748
    def __init__(self, store):
 
1749
        self._store = store
 
1750
 
 
1751
    def add_lines(self, key, parents, lines, parent_texts=None,
 
1752
            left_matching_blocks=None, nostore_sha=None, random_id=False,
 
1753
            check_content=True):
 
1754
        """See VersionedFiles.add_lines.
 
1755
        
 
1756
        This implementation may return None as the third element of the return
 
1757
        value when the original store wouldn't.
 
1758
        """
 
1759
        if nostore_sha:
 
1760
            raise NotImplementedError(
 
1761
                "NoDupeAddLinesDecorator.add_lines does not implement the "
 
1762
                "nostore_sha behaviour.")
 
1763
        if key[-1] is None:
 
1764
            sha1 = osutils.sha_strings(lines)
 
1765
            key = (b"sha1:" + sha1,)
 
1766
        else:
 
1767
            sha1 = None
 
1768
        if key in self._store.get_parent_map([key]):
 
1769
            # This key has already been inserted, so don't do it again.
 
1770
            if sha1 is None:
 
1771
                sha1 = osutils.sha_strings(lines)
 
1772
            return sha1, sum(map(len, lines)), None
 
1773
        return self._store.add_lines(key, parents, lines,
 
1774
                parent_texts=parent_texts,
 
1775
                left_matching_blocks=left_matching_blocks,
 
1776
                nostore_sha=nostore_sha, random_id=random_id,
 
1777
                check_content=check_content)
 
1778
 
 
1779
    def __getattr__(self, name):
 
1780
        return getattr(self._store, name)
 
1781
 
 
1782
 
1627
1783
def network_bytes_to_kind_and_offset(network_bytes):
1628
1784
    """Strip of a record kind from the front of network_bytes.
1629
1785
 
1630
1786
    :param network_bytes: The bytes of a record.
1631
1787
    :return: A tuple (storage_kind, offset_of_remaining_bytes)
1632
1788
    """
1633
 
    line_end = network_bytes.find('\n')
 
1789
    line_end = network_bytes.find(b'\n')
1634
1790
    storage_kind = network_bytes[:line_end]
1635
1791
    return storage_kind, line_end + 1
1636
1792
 
1673
1829
    meta_len, = struct.unpack('!L', bytes[line_end:line_end+4])
1674
1830
    record_meta = bytes[line_end+4:line_end+4+meta_len]
1675
1831
    key, parents = bencode.bdecode_as_tuple(record_meta)
1676
 
    if parents == 'nil':
 
1832
    if parents == b'nil':
1677
1833
        parents = None
1678
1834
    fulltext = bytes[line_end+4+meta_len:]
1679
1835
    return [FulltextContentFactory(key, parents, None, fulltext)]
1685
1841
 
1686
1842
def record_to_fulltext_bytes(record):
1687
1843
    if record.parents is None:
1688
 
        parents = 'nil'
 
1844
        parents = b'nil'
1689
1845
    else:
1690
1846
        parents = record.parents
1691
1847
    record_meta = bencode.bencode((record.key, parents))
1692
1848
    record_content = record.get_bytes_as('fulltext')
1693
 
    return "fulltext\n%s%s%s" % (
 
1849
    return b"fulltext\n%s%s%s" % (
1694
1850
        _length_prefix(record_meta), record_meta, record_content)
1695
1851
 
1696
1852
 
1705
1861
    # gc-optimal ordering is approximately reverse topological,
1706
1862
    # properly grouped by file-id.
1707
1863
    per_prefix_map = {}
1708
 
    for item in parent_map.iteritems():
 
1864
    for item in viewitems(parent_map):
1709
1865
        key = item[0]
1710
 
        if isinstance(key, str) or len(key) == 1:
1711
 
            prefix = ''
 
1866
        if isinstance(key, bytes) or len(key) == 1:
 
1867
            prefix = b''
1712
1868
        else:
1713
1869
            prefix = key[0]
1714
1870
        try:
1720
1876
    for prefix in sorted(per_prefix_map):
1721
1877
        present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
1722
1878
    return present_keys
 
1879
 
 
1880
 
 
1881
class _KeyRefs(object):
 
1882
 
 
1883
    def __init__(self, track_new_keys=False):
 
1884
        # dict mapping 'key' to 'set of keys referring to that key'
 
1885
        self.refs = {}
 
1886
        if track_new_keys:
 
1887
            # set remembering all new keys
 
1888
            self.new_keys = set()
 
1889
        else:
 
1890
            self.new_keys = None
 
1891
 
 
1892
    def clear(self):
 
1893
        if self.refs:
 
1894
            self.refs.clear()
 
1895
        if self.new_keys:
 
1896
            self.new_keys.clear()
 
1897
 
 
1898
    def add_references(self, key, refs):
 
1899
        # Record the new references
 
1900
        for referenced in refs:
 
1901
            try:
 
1902
                needed_by = self.refs[referenced]
 
1903
            except KeyError:
 
1904
                needed_by = self.refs[referenced] = set()
 
1905
            needed_by.add(key)
 
1906
        # Discard references satisfied by the new key
 
1907
        self.add_key(key)
 
1908
 
 
1909
    def get_new_keys(self):
 
1910
        return self.new_keys
 
1911
 
 
1912
    def get_unsatisfied_refs(self):
 
1913
        return self.refs.keys()
 
1914
 
 
1915
    def _satisfy_refs_for_key(self, key):
 
1916
        try:
 
1917
            del self.refs[key]
 
1918
        except KeyError:
 
1919
            # No keys depended on this key.  That's ok.
 
1920
            pass
 
1921
 
 
1922
    def add_key(self, key):
 
1923
        # satisfy refs for key, and remember that we've seen this key.
 
1924
        self._satisfy_refs_for_key(key)
 
1925
        if self.new_keys is not None:
 
1926
            self.new_keys.add(key)
 
1927
 
 
1928
    def satisfy_refs_for_keys(self, keys):
 
1929
        for key in keys:
 
1930
            self._satisfy_refs_for_key(key)
 
1931
 
 
1932
    def get_referrers(self):
 
1933
        return set(itertools.chain.from_iterable(viewvalues(self.refs)))
 
1934
 
 
1935
 
 
1936