/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: 2017-10-27 00:18:42 UTC
  • mto: This revision was merged to the branch mainline in revision 6799.
  • Revision ID: jelmer@jelmer.uk-20171027001842-o77sekj0g2t2zwbn
Properly escape backslashes.

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
 
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):
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,
839
979
    def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
840
980
        """Add a text to the store.
841
981
 
842
 
        This is a private function for use by CommitBuilder.
 
982
        This is a private function for use by VersionedFileCommitBuilder.
843
983
 
844
984
        :param key: The key tuple of the text to add. If the last element is
845
985
            None, a CHK string will be generated during the addition.
891
1031
                continue
892
1032
            mpvf.add_version(chunks_to_lines(record.get_bytes_as('chunked')),
893
1033
                record.key, [])
894
 
        for (key, parent_keys, expected_sha1, mpdiff), lines in\
895
 
            zip(records, mpvf.get_line_list(versions)):
 
1034
        for (key, parent_keys, expected_sha1, mpdiff), lines in zip(
 
1035
                records, mpvf.get_line_list(versions)):
896
1036
            if len(parent_keys) == 1:
897
1037
                left_matching_blocks = list(mpdiff.get_matching_blocks(0,
898
1038
                    mpvf.get_diff(parent_keys[0]).num_lines()))
939
1079
    def _check_lines_not_unicode(self, lines):
940
1080
        """Check that lines being added to a versioned file are not unicode."""
941
1081
        for line in lines:
942
 
            if line.__class__ is not str:
 
1082
            if line.__class__ is not bytes:
943
1083
                raise errors.BzrBadParameterUnicode("lines")
944
1084
 
945
1085
    def _check_lines_are_lines(self, lines):
946
1086
        """Check that the lines really are full lines without inline EOL."""
947
1087
        for line in lines:
948
 
            if '\n' in line[:-1]:
 
1088
            if b'\n' in line[:-1]:
949
1089
                raise errors.BzrBadParameterContainsNewline("lines")
950
1090
 
951
1091
    def get_known_graph_ancestry(self, keys):
956
1096
        while pending:
957
1097
            this_parent_map = self.get_parent_map(pending)
958
1098
            parent_map.update(this_parent_map)
959
 
            pending = set()
960
 
            map(pending.update, this_parent_map.itervalues())
961
 
            pending = pending.difference(parent_map)
 
1099
            pending = set(itertools.chain.from_iterable(
 
1100
                viewvalues(this_parent_map)))
 
1101
            pending.difference_update(parent_map)
962
1102
        kg = _mod_graph.KnownGraph(parent_map)
963
1103
        return kg
964
1104
 
995
1135
        """
996
1136
        raise NotImplementedError(self.get_sha1s)
997
1137
 
998
 
    has_key = index._has_key_from_parent_map
 
1138
    __contains__ = index._has_key_from_parent_map
999
1139
 
1000
1140
    def get_missing_compression_parent_keys(self):
1001
1141
        """Return an iterable of keys of missing compression parents.
1047
1187
 
1048
1188
    def make_mpdiffs(self, keys):
1049
1189
        """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
 
1190
        generator = _MPDiffGenerator(self, keys)
 
1191
        return generator.compute_diffs()
 
1192
 
 
1193
    def get_annotator(self):
 
1194
        return annotate.Annotator(self)
1087
1195
 
1088
1196
    missing_keys = index._missing_keys_from_parent_map
1089
1197
 
1090
1198
    def _extract_blocks(self, version_id, source, target):
1091
1199
        return None
1092
1200
 
 
1201
    def _transitive_fallbacks(self):
 
1202
        """Return the whole stack of fallback versionedfiles.
 
1203
 
 
1204
        This VersionedFiles may have a list of fallbacks, but it doesn't
 
1205
        necessarily know about the whole stack going down, and it can't know
 
1206
        at open time because they may change after the objects are opened.
 
1207
        """
 
1208
        all_fallbacks = []
 
1209
        for a_vfs in self._immediate_fallback_vfs:
 
1210
            all_fallbacks.append(a_vfs)
 
1211
            all_fallbacks.extend(a_vfs._transitive_fallbacks())
 
1212
        return all_fallbacks
 
1213
 
1093
1214
 
1094
1215
class ThunkedVersionedFiles(VersionedFiles):
1095
1216
    """Storage for many versioned files thunked onto a 'VersionedFile' class.
1159
1280
            result.append((prefix + (origin,), line))
1160
1281
        return result
1161
1282
 
1162
 
    def get_annotator(self):
1163
 
        return annotate.Annotator(self)
1164
 
 
1165
1283
    def check(self, progress_bar=None, keys=None):
1166
1284
        """See VersionedFiles.check()."""
1167
1285
        # XXX: This is over-enthusiastic but as we only thunk for Weaves today
1181
1299
        """
1182
1300
        prefixes = self._partition_keys(keys)
1183
1301
        result = {}
1184
 
        for prefix, suffixes in prefixes.items():
 
1302
        for prefix, suffixes in viewitems(prefixes):
1185
1303
            path = self._mapper.map(prefix)
1186
1304
            vf = self._get_vf(path)
1187
1305
            parent_map = vf.get_parent_map(suffixes)
1188
 
            for key, parents in parent_map.items():
 
1306
            for key, parents in viewitems(parent_map):
1189
1307
                result[prefix + (key,)] = tuple(
1190
1308
                    prefix + (parent,) for parent in parents)
1191
1309
        return result
1204
1322
            prefix_keys.append(key[-1])
1205
1323
        return result
1206
1324
 
1207
 
    def _get_all_prefixes(self):
 
1325
    def _iter_all_prefixes(self):
1208
1326
        # Identify all key prefixes.
1209
1327
        # XXX: A bit hacky, needs polish.
1210
 
        if type(self._mapper) == ConstantMapper:
 
1328
        if isinstance(self._mapper, ConstantMapper):
1211
1329
            paths = [self._mapper.map(())]
1212
1330
            prefixes = [()]
1213
1331
        else:
1237
1355
    def _iter_keys_vf(self, keys):
1238
1356
        prefixes = self._partition_keys(keys)
1239
1357
        sha1s = {}
1240
 
        for prefix, suffixes in prefixes.items():
 
1358
        for prefix, suffixes in viewitems(prefixes):
1241
1359
            path = self._mapper.map(prefix)
1242
1360
            vf = self._get_vf(path)
1243
1361
            yield prefix, suffixes, vf
1247
1365
        sha1s = {}
1248
1366
        for prefix,suffixes, vf in self._iter_keys_vf(keys):
1249
1367
            vf_sha1s = vf.get_sha1s(suffixes)
1250
 
            for suffix, sha1 in vf_sha1s.iteritems():
 
1368
            for suffix, sha1 in viewitems(vf_sha1s):
1251
1369
                sha1s[prefix + (suffix,)] = sha1
1252
1370
        return sha1s
1253
1371
 
1299
1417
                yield line, prefix + (version,)
1300
1418
 
1301
1419
    def _iter_all_components(self):
1302
 
        for path, prefix in self._get_all_prefixes():
 
1420
        for path, prefix in self._iter_all_prefixes():
1303
1421
            yield prefix, self._get_vf(path)
1304
1422
 
1305
1423
    def keys(self):
1311
1429
        return result
1312
1430
 
1313
1431
 
 
1432
class VersionedFilesWithFallbacks(VersionedFiles):
 
1433
 
 
1434
    def without_fallbacks(self):
 
1435
        """Return a clone of this object without any fallbacks configured."""
 
1436
        raise NotImplementedError(self.without_fallbacks)
 
1437
 
 
1438
    def add_fallback_versioned_files(self, a_versioned_files):
 
1439
        """Add a source of texts for texts not present in this knit.
 
1440
 
 
1441
        :param a_versioned_files: A VersionedFiles object.
 
1442
        """
 
1443
        raise NotImplementedError(self.add_fallback_versioned_files)
 
1444
 
 
1445
    def get_known_graph_ancestry(self, keys):
 
1446
        """Get a KnownGraph instance with the ancestry of keys."""
 
1447
        parent_map, missing_keys = self._index.find_ancestry(keys)
 
1448
        for fallback in self._transitive_fallbacks():
 
1449
            if not missing_keys:
 
1450
                break
 
1451
            (f_parent_map, f_missing_keys) = fallback._index.find_ancestry(
 
1452
                                                missing_keys)
 
1453
            parent_map.update(f_parent_map)
 
1454
            missing_keys = f_missing_keys
 
1455
        kg = _mod_graph.KnownGraph(parent_map)
 
1456
        return kg
 
1457
 
 
1458
 
1314
1459
class _PlanMergeVersionedFile(VersionedFiles):
1315
1460
    """A VersionedFile for uncommitted and committed texts.
1316
1461
 
1337
1482
        # line data for locally held keys.
1338
1483
        self._lines = {}
1339
1484
        # key lookup providers
1340
 
        self._providers = [DictParentsProvider(self._parents)]
 
1485
        self._providers = [_mod_graph.DictParentsProvider(self._parents)]
1341
1486
 
1342
1487
    def plan_merge(self, ver_a, ver_b, base=None):
1343
1488
        """See VersionedFile.plan_merge"""
1344
 
        from bzrlib.merge import _PlanMerge
 
1489
        from ..merge import _PlanMerge
1345
1490
        if base is None:
1346
1491
            return _PlanMerge(ver_a, ver_b, self, (self._file_id,)).plan_merge()
1347
1492
        old_plan = list(_PlanMerge(ver_a, base, self, (self._file_id,)).plan_merge())
1349
1494
        return _PlanMerge._subtract_plans(old_plan, new_plan)
1350
1495
 
1351
1496
    def plan_lca_merge(self, ver_a, ver_b, base=None):
1352
 
        from bzrlib.merge import _PlanLCAMerge
1353
 
        graph = Graph(self)
 
1497
        from ..merge import _PlanLCAMerge
 
1498
        graph = _mod_graph.Graph(self)
1354
1499
        new_plan = _PlanLCAMerge(ver_a, ver_b, self, (self._file_id,), graph).plan_merge()
1355
1500
        if base is None:
1356
1501
            return new_plan
1363
1508
        Lines are added locally, not to fallback versionedfiles.  Also, ghosts
1364
1509
        are permitted.  Only reserved ids are permitted.
1365
1510
        """
1366
 
        if type(key) is not tuple:
 
1511
        if not isinstance(key, tuple):
1367
1512
            raise TypeError(key)
1368
1513
        if not revision.is_reserved_id(key[-1]):
1369
1514
            raise ValueError('Only reserved ids may be used')
1408
1553
            result[revision.NULL_REVISION] = ()
1409
1554
        self._providers = self._providers[:1] + self.fallback_versionedfiles
1410
1555
        result.update(
1411
 
            StackedParentsProvider(self._providers).get_parent_map(keys))
1412
 
        for key, parents in result.iteritems():
 
1556
            _mod_graph.StackedParentsProvider(
 
1557
                self._providers).get_parent_map(keys))
 
1558
        for key, parents in viewitems(result):
1413
1559
            if parents == ():
1414
1560
                result[key] = (revision.NULL_REVISION,)
1415
1561
        return result
1588
1734
 
1589
1735
    def get_parent_map(self, keys):
1590
1736
        """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()])
 
1737
        parent_view = viewitems(self._get_parent_map(k for (k,) in keys))
 
1738
        return dict(((k,), tuple((p,) for p in v)) for k, v in parent_view)
1593
1739
 
1594
1740
    def get_sha1s(self, keys):
1595
1741
        """See VersionedFiles.get_sha1s."""
1624
1770
                yield (l, key)
1625
1771
 
1626
1772
 
 
1773
class NoDupeAddLinesDecorator(object):
 
1774
    """Decorator for a VersionedFiles that skips doing an add_lines if the key
 
1775
    is already present.
 
1776
    """
 
1777
 
 
1778
    def __init__(self, store):
 
1779
        self._store = store
 
1780
 
 
1781
    def add_lines(self, key, parents, lines, parent_texts=None,
 
1782
            left_matching_blocks=None, nostore_sha=None, random_id=False,
 
1783
            check_content=True):
 
1784
        """See VersionedFiles.add_lines.
 
1785
        
 
1786
        This implementation may return None as the third element of the return
 
1787
        value when the original store wouldn't.
 
1788
        """
 
1789
        if nostore_sha:
 
1790
            raise NotImplementedError(
 
1791
                "NoDupeAddLinesDecorator.add_lines does not implement the "
 
1792
                "nostore_sha behaviour.")
 
1793
        if key[-1] is None:
 
1794
            sha1 = osutils.sha_strings(lines)
 
1795
            key = (b"sha1:" + sha1,)
 
1796
        else:
 
1797
            sha1 = None
 
1798
        if key in self._store.get_parent_map([key]):
 
1799
            # This key has already been inserted, so don't do it again.
 
1800
            if sha1 is None:
 
1801
                sha1 = osutils.sha_strings(lines)
 
1802
            return sha1, sum(map(len, lines)), None
 
1803
        return self._store.add_lines(key, parents, lines,
 
1804
                parent_texts=parent_texts,
 
1805
                left_matching_blocks=left_matching_blocks,
 
1806
                nostore_sha=nostore_sha, random_id=random_id,
 
1807
                check_content=check_content)
 
1808
 
 
1809
    def __getattr__(self, name):
 
1810
        return getattr(self._store, name)
 
1811
 
 
1812
 
1627
1813
def network_bytes_to_kind_and_offset(network_bytes):
1628
1814
    """Strip of a record kind from the front of network_bytes.
1629
1815
 
1630
1816
    :param network_bytes: The bytes of a record.
1631
1817
    :return: A tuple (storage_kind, offset_of_remaining_bytes)
1632
1818
    """
1633
 
    line_end = network_bytes.find('\n')
 
1819
    line_end = network_bytes.find(b'\n')
1634
1820
    storage_kind = network_bytes[:line_end]
1635
1821
    return storage_kind, line_end + 1
1636
1822
 
1673
1859
    meta_len, = struct.unpack('!L', bytes[line_end:line_end+4])
1674
1860
    record_meta = bytes[line_end+4:line_end+4+meta_len]
1675
1861
    key, parents = bencode.bdecode_as_tuple(record_meta)
1676
 
    if parents == 'nil':
 
1862
    if parents == b'nil':
1677
1863
        parents = None
1678
1864
    fulltext = bytes[line_end+4+meta_len:]
1679
1865
    return [FulltextContentFactory(key, parents, None, fulltext)]
1685
1871
 
1686
1872
def record_to_fulltext_bytes(record):
1687
1873
    if record.parents is None:
1688
 
        parents = 'nil'
 
1874
        parents = b'nil'
1689
1875
    else:
1690
1876
        parents = record.parents
1691
1877
    record_meta = bencode.bencode((record.key, parents))
1692
1878
    record_content = record.get_bytes_as('fulltext')
1693
 
    return "fulltext\n%s%s%s" % (
 
1879
    return b"fulltext\n%s%s%s" % (
1694
1880
        _length_prefix(record_meta), record_meta, record_content)
1695
1881
 
1696
1882
 
1705
1891
    # gc-optimal ordering is approximately reverse topological,
1706
1892
    # properly grouped by file-id.
1707
1893
    per_prefix_map = {}
1708
 
    for item in parent_map.iteritems():
 
1894
    for item in viewitems(parent_map):
1709
1895
        key = item[0]
1710
 
        if isinstance(key, str) or len(key) == 1:
1711
 
            prefix = ''
 
1896
        if isinstance(key, bytes) or len(key) == 1:
 
1897
            prefix = b''
1712
1898
        else:
1713
1899
            prefix = key[0]
1714
1900
        try:
1720
1906
    for prefix in sorted(per_prefix_map):
1721
1907
        present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
1722
1908
    return present_keys
 
1909
 
 
1910
 
 
1911
class _KeyRefs(object):
 
1912
 
 
1913
    def __init__(self, track_new_keys=False):
 
1914
        # dict mapping 'key' to 'set of keys referring to that key'
 
1915
        self.refs = {}
 
1916
        if track_new_keys:
 
1917
            # set remembering all new keys
 
1918
            self.new_keys = set()
 
1919
        else:
 
1920
            self.new_keys = None
 
1921
 
 
1922
    def clear(self):
 
1923
        if self.refs:
 
1924
            self.refs.clear()
 
1925
        if self.new_keys:
 
1926
            self.new_keys.clear()
 
1927
 
 
1928
    def add_references(self, key, refs):
 
1929
        # Record the new references
 
1930
        for referenced in refs:
 
1931
            try:
 
1932
                needed_by = self.refs[referenced]
 
1933
            except KeyError:
 
1934
                needed_by = self.refs[referenced] = set()
 
1935
            needed_by.add(key)
 
1936
        # Discard references satisfied by the new key
 
1937
        self.add_key(key)
 
1938
 
 
1939
    def get_new_keys(self):
 
1940
        return self.new_keys
 
1941
 
 
1942
    def get_unsatisfied_refs(self):
 
1943
        return self.refs.keys()
 
1944
 
 
1945
    def _satisfy_refs_for_key(self, key):
 
1946
        try:
 
1947
            del self.refs[key]
 
1948
        except KeyError:
 
1949
            # No keys depended on this key.  That's ok.
 
1950
            pass
 
1951
 
 
1952
    def add_key(self, key):
 
1953
        # satisfy refs for key, and remember that we've seen this key.
 
1954
        self._satisfy_refs_for_key(key)
 
1955
        if self.new_keys is not None:
 
1956
            self.new_keys.add(key)
 
1957
 
 
1958
    def satisfy_refs_for_keys(self, keys):
 
1959
        for key in keys:
 
1960
            self._satisfy_refs_for_key(key)
 
1961
 
 
1962
    def get_referrers(self):
 
1963
        return set(itertools.chain.from_iterable(viewvalues(self.refs)))
 
1964
 
 
1965
 
 
1966