/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/knit.py

  • Committer: Jelmer Vernooij
  • Date: 2017-11-13 22:52:33 UTC
  • mfrom: (6816 trunk)
  • mto: This revision was merged to the branch mainline in revision 6819.
  • Revision ID: jelmer@jelmer.uk-20171113225233-gma778z1cy8nqiig
merge trunk

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2006-2010 Canonical Ltd
 
1
# Copyright (C) 2006-2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
51
51
 
52
52
"""
53
53
 
 
54
from __future__ import absolute_import
54
55
 
55
 
from cStringIO import StringIO
56
 
from itertools import izip
57
56
import operator
58
57
import os
59
 
import sys
60
58
 
61
 
from bzrlib.lazy_import import lazy_import
 
59
from ..lazy_import import lazy_import
62
60
lazy_import(globals(), """
63
 
from bzrlib import (
64
 
    annotate,
 
61
import gzip
 
62
 
 
63
from breezy import (
65
64
    debug,
66
65
    diff,
67
66
    graph as _mod_graph,
68
 
    index as _mod_index,
69
 
    lru_cache,
70
 
    pack,
71
 
    progress,
 
67
    patiencediff,
72
68
    static_tuple,
73
69
    trace,
74
70
    tsort,
75
71
    tuned_gzip,
76
72
    ui,
77
73
    )
 
74
from breezy.bzr import (
 
75
    index as _mod_index,
 
76
    pack,
 
77
    )
 
78
 
 
79
from breezy.bzr import pack_repo
 
80
from breezy.i18n import gettext
78
81
""")
79
 
from bzrlib import (
 
82
from .. import (
 
83
    annotate,
80
84
    errors,
81
85
    osutils,
82
 
    patiencediff,
83
86
    )
84
 
from bzrlib.errors import (
85
 
    FileExists,
 
87
from ..errors import (
 
88
    InternalBzrError,
 
89
    InvalidRevisionId,
86
90
    NoSuchFile,
87
 
    KnitError,
88
 
    InvalidRevisionId,
89
 
    KnitCorrupt,
90
 
    KnitHeaderError,
91
91
    RevisionNotPresent,
92
 
    RevisionAlreadyPresent,
93
 
    SHA1KnitCorrupt,
94
92
    )
95
 
from bzrlib.osutils import (
 
93
from ..osutils import (
96
94
    contains_whitespace,
97
 
    contains_linebreaks,
98
95
    sha_string,
99
96
    sha_strings,
100
97
    split_lines,
101
98
    )
102
 
from bzrlib.versionedfile import (
 
99
from ..sixish import (
 
100
    BytesIO,
 
101
    range,
 
102
    viewitems,
 
103
    viewvalues,
 
104
    )
 
105
from ..bzr.versionedfile import (
 
106
    _KeyRefs,
103
107
    AbsentContentFactory,
104
108
    adapter_registry,
105
109
    ConstantMapper,
106
110
    ContentFactory,
107
 
    ChunkedContentFactory,
108
111
    sort_groupcompress,
109
 
    VersionedFile,
110
 
    VersionedFiles,
 
112
    VersionedFilesWithFallbacks,
111
113
    )
112
114
 
113
115
 
129
131
_STREAM_MIN_BUFFER_SIZE = 5*1024*1024
130
132
 
131
133
 
 
134
class KnitError(InternalBzrError):
 
135
 
 
136
    _fmt = "Knit error"
 
137
 
 
138
 
 
139
class KnitCorrupt(KnitError):
 
140
 
 
141
    _fmt = "Knit %(filename)s corrupt: %(how)s"
 
142
 
 
143
    def __init__(self, filename, how):
 
144
        KnitError.__init__(self)
 
145
        self.filename = filename
 
146
        self.how = how
 
147
 
 
148
 
 
149
class SHA1KnitCorrupt(KnitCorrupt):
 
150
 
 
151
    _fmt = ("Knit %(filename)s corrupt: sha-1 of reconstructed text does not "
 
152
        "match expected sha-1. key %(key)s expected sha %(expected)s actual "
 
153
        "sha %(actual)s")
 
154
 
 
155
    def __init__(self, filename, actual, expected, key, content):
 
156
        KnitError.__init__(self)
 
157
        self.filename = filename
 
158
        self.actual = actual
 
159
        self.expected = expected
 
160
        self.key = key
 
161
        self.content = content
 
162
 
 
163
 
 
164
class KnitDataStreamIncompatible(KnitError):
 
165
    # Not raised anymore, as we can convert data streams.  In future we may
 
166
    # need it again for more exotic cases, so we're keeping it around for now.
 
167
 
 
168
    _fmt = "Cannot insert knit data stream of format \"%(stream_format)s\" into knit of format \"%(target_format)s\"."
 
169
 
 
170
    def __init__(self, stream_format, target_format):
 
171
        self.stream_format = stream_format
 
172
        self.target_format = target_format
 
173
 
 
174
 
 
175
class KnitDataStreamUnknown(KnitError):
 
176
    # Indicates a data stream we don't know how to handle.
 
177
 
 
178
    _fmt = "Cannot parse knit data stream of format \"%(stream_format)s\"."
 
179
 
 
180
    def __init__(self, stream_format):
 
181
        self.stream_format = stream_format
 
182
 
 
183
 
 
184
class KnitHeaderError(KnitError):
 
185
 
 
186
    _fmt = 'Knit header error: %(badline)r unexpected for file "%(filename)s".'
 
187
 
 
188
    def __init__(self, badline, filename):
 
189
        KnitError.__init__(self)
 
190
        self.badline = badline
 
191
        self.filename = filename
 
192
 
 
193
 
 
194
class KnitIndexUnknownMethod(KnitError):
 
195
    """Raised when we don't understand the storage method.
 
196
 
 
197
    Currently only 'fulltext' and 'line-delta' are supported.
 
198
    """
 
199
 
 
200
    _fmt = ("Knit index %(filename)s does not have a known method"
 
201
            " in options: %(options)r")
 
202
 
 
203
    def __init__(self, filename, options):
 
204
        KnitError.__init__(self)
 
205
        self.filename = filename
 
206
        self.options = options
 
207
 
 
208
 
132
209
class KnitAdapter(object):
133
210
    """Base class for knit record adaption."""
134
211
 
192
269
        delta = self._annotate_factory.parse_line_delta(contents, rec[1],
193
270
            plain=True)
194
271
        compression_parent = factory.parents[0]
195
 
        basis_entry = self._basis_vf.get_record_stream(
196
 
            [compression_parent], 'unordered', True).next()
 
272
        basis_entry = next(self._basis_vf.get_record_stream(
 
273
            [compression_parent], 'unordered', True))
197
274
        if basis_entry.storage_kind == 'absent':
198
275
            raise errors.RevisionNotPresent(compression_parent, self._basis_vf)
199
276
        basis_chunks = basis_entry.get_bytes_as('chunked')
228
305
        delta = self._plain_factory.parse_line_delta(contents, rec[1])
229
306
        compression_parent = factory.parents[0]
230
307
        # XXX: string splitting overhead.
231
 
        basis_entry = self._basis_vf.get_record_stream(
232
 
            [compression_parent], 'unordered', True).next()
 
308
        basis_entry = next(self._basis_vf.get_record_stream(
 
309
            [compression_parent], 'unordered', True))
233
310
        if basis_entry.storage_kind == 'absent':
234
311
            raise errors.RevisionNotPresent(compression_parent, self._basis_vf)
235
312
        basis_chunks = basis_entry.get_bytes_as('chunked')
412
489
class KnitContent(object):
413
490
    """Content of a knit version to which deltas can be applied.
414
491
 
415
 
    This is always stored in memory as a list of lines with \n at the end,
 
492
    This is always stored in memory as a list of lines with \\n at the end,
416
493
    plus a flag saying if the final ending is really there or not, because that
417
494
    corresponds to the on-disk knit representation.
418
495
    """
470
547
 
471
548
    def __init__(self, lines):
472
549
        KnitContent.__init__(self)
473
 
        self._lines = lines
 
550
        self._lines = list(lines)
474
551
 
475
552
    def annotate(self):
476
553
        """Return a list of (origin, text) for each content line."""
491
568
    def text(self):
492
569
        try:
493
570
            lines = [text for origin, text in self._lines]
494
 
        except ValueError, e:
 
571
        except ValueError as e:
495
572
            # most commonly (only?) caused by the internal form of the knit
496
573
            # missing annotation information because of a bug - see thread
497
574
            # around 20071015
503
580
        return lines
504
581
 
505
582
    def copy(self):
506
 
        return AnnotatedKnitContent(self._lines[:])
 
583
        return AnnotatedKnitContent(self._lines)
507
584
 
508
585
 
509
586
class PlainKnitContent(KnitContent):
598
675
        #       but the code itself doesn't really depend on that.
599
676
        #       Figure out a way to not require the overhead of turning the
600
677
        #       list back into tuples.
601
 
        lines = [tuple(line.split(' ', 1)) for line in content]
 
678
        lines = (tuple(line.split(' ', 1)) for line in content)
602
679
        return AnnotatedKnitContent(lines)
603
680
 
604
681
    def parse_line_delta_iter(self, lines):
620
697
        """
621
698
        result = []
622
699
        lines = iter(lines)
623
 
        next = lines.next
624
700
 
625
701
        cache = {}
626
702
        def cache_and_return(line):
633
709
        if plain:
634
710
            for header in lines:
635
711
                start, end, count = [int(n) for n in header.split(',')]
636
 
                contents = [next().split(' ', 1)[1] for i in xrange(count)]
 
712
                contents = [next(lines).split(' ', 1)[1] for _ in range(count)]
637
713
                result.append((start, end, count, contents))
638
714
        else:
639
715
            for header in lines:
640
716
                start, end, count = [int(n) for n in header.split(',')]
641
 
                contents = [tuple(next().split(' ', 1)) for i in xrange(count)]
 
717
                contents = [tuple(next(lines).split(' ', 1))
 
718
                    for _ in range(count)]
642
719
                result.append((start, end, count, contents))
643
720
        return result
644
721
 
653
730
        Only the actual content lines.
654
731
        """
655
732
        lines = iter(lines)
656
 
        next = lines.next
657
733
        for header in lines:
658
734
            header = header.split(',')
659
735
            count = int(header[2])
660
 
            for i in xrange(count):
661
 
                origin, text = next().split(' ', 1)
 
736
            for _ in range(count):
 
737
                origin, text = next(lines).split(' ', 1)
662
738
                yield text
663
739
 
664
740
    def lower_fulltext(self, content):
686
762
        content = knit._get_content(key)
687
763
        # adjust for the fact that serialised annotations are only key suffixes
688
764
        # for this factory.
689
 
        if type(key) is tuple:
 
765
        if isinstance(key, tuple):
690
766
            prefix = key[:-1]
691
767
            origins = content.annotate()
692
768
            result = []
739
815
        Only the actual content lines.
740
816
        """
741
817
        lines = iter(lines)
742
 
        next = lines.next
743
818
        for header in lines:
744
819
            header = header.split(',')
745
820
            count = int(header[2])
746
 
            for i in xrange(count):
747
 
                yield next()
 
821
            for _ in range(count):
 
822
                yield next(lines)
748
823
 
749
824
    def lower_fulltext(self, content):
750
825
        return content.text()
805
880
        writer.begin()
806
881
        index = _KnitGraphIndex(graph_index, lambda:True, parents=parents,
807
882
            deltas=delta, add_callback=graph_index.add_nodes)
808
 
        access = _DirectPackAccess({})
 
883
        access = pack_repo._DirectPackAccess({})
809
884
        access.set_writer(writer, graph_index, (transport, 'newpack'))
810
885
        result = KnitVersionedFiles(index, access,
811
886
            max_delta_chain=max_delta_chain)
845
920
            if compression_parent not in all_build_index_memos:
846
921
                next_keys.add(compression_parent)
847
922
        build_keys = next_keys
848
 
    return sum([index_memo[2] for index_memo
849
 
                in all_build_index_memos.itervalues()])
850
 
 
851
 
 
852
 
class KnitVersionedFiles(VersionedFiles):
 
923
    return sum(index_memo[2]
 
924
               for index_memo in viewvalues(all_build_index_memos))
 
925
 
 
926
 
 
927
class KnitVersionedFiles(VersionedFilesWithFallbacks):
853
928
    """Storage for many versioned files using knit compression.
854
929
 
855
930
    Backend storage is managed by indices and data objects.
873
948
            stored during insertion.
874
949
        :param reload_func: An function that can be called if we think we need
875
950
            to reload the pack listing and try again. See
876
 
            'bzrlib.repofmt.pack_repo.AggregateIndex' for the signature.
 
951
            'breezy.bzr.pack_repo.AggregateIndex' for the signature.
877
952
        """
878
953
        self._index = index
879
954
        self._access = data_access
882
957
            self._factory = KnitAnnotateFactory()
883
958
        else:
884
959
            self._factory = KnitPlainFactory()
885
 
        self._fallback_vfs = []
 
960
        self._immediate_fallback_vfs = []
886
961
        self._reload_func = reload_func
887
962
 
888
963
    def __repr__(self):
891
966
            self._index,
892
967
            self._access)
893
968
 
 
969
    def without_fallbacks(self):
 
970
        """Return a clone of this object without any fallbacks configured."""
 
971
        return KnitVersionedFiles(self._index, self._access,
 
972
            self._max_delta_chain, self._factory.annotated,
 
973
            self._reload_func)
 
974
 
894
975
    def add_fallback_versioned_files(self, a_versioned_files):
895
976
        """Add a source of texts for texts not present in this knit.
896
977
 
897
978
        :param a_versioned_files: A VersionedFiles object.
898
979
        """
899
 
        self._fallback_vfs.append(a_versioned_files)
 
980
        self._immediate_fallback_vfs.append(a_versioned_files)
900
981
 
901
982
    def add_lines(self, key, parents, lines, parent_texts=None,
902
983
        left_matching_blocks=None, nostore_sha=None, random_id=False,
918
999
        """See VersionedFiles._add_text()."""
919
1000
        self._index._check_write_ok()
920
1001
        self._check_add(key, None, random_id, check_content=False)
921
 
        if text.__class__ is not str:
 
1002
        if not isinstance(text, bytes):
922
1003
            raise errors.BzrBadParameterUnicode("text")
923
1004
        if parents is None:
924
1005
            # The caller might pass None if there is no graph data, but kndx
992
1073
            lines = osutils.split_lines(line_bytes)
993
1074
 
994
1075
        for element in key[:-1]:
995
 
            if type(element) is not str:
 
1076
            if not isinstance(element, str):
996
1077
                raise TypeError("key contains non-strings: %r" % (key,))
997
1078
        if key[-1] is None:
998
1079
            key = key[:-1] + ('sha1:' + digest,)
999
 
        elif type(key[-1]) is not str:
 
1080
        elif not isinstance(key[-1], str):
1000
1081
                raise TypeError("key contains non-strings: %r" % (key,))
1001
1082
        # Knit hunks are still last-element only
1002
1083
        version_id = key[-1]
1066
1147
            if self._index.get_method(key) != 'fulltext':
1067
1148
                compression_parent = parent_map[key][0]
1068
1149
                if compression_parent not in parent_map:
1069
 
                    raise errors.KnitCorrupt(self,
 
1150
                    raise KnitCorrupt(self,
1070
1151
                        "Missing basis parent %s for %s" % (
1071
1152
                        compression_parent, key))
1072
 
        for fallback_vfs in self._fallback_vfs:
 
1153
        for fallback_vfs in self._immediate_fallback_vfs:
1073
1154
            fallback_vfs.check()
1074
1155
 
1075
1156
    def _check_add(self, key, lines, random_id, check_content):
1114
1195
        """
1115
1196
        delta_size = 0
1116
1197
        fulltext_size = None
1117
 
        for count in xrange(self._max_delta_chain):
 
1198
        for count in range(self._max_delta_chain):
1118
1199
            try:
1119
1200
                # Note that this only looks in the index of this particular
1120
1201
                # KnitVersionedFiles, not in the fallbacks.  This ensures that
1122
1203
                # boundaries.
1123
1204
                build_details = self._index.get_build_details([parent])
1124
1205
                parent_details = build_details[parent]
1125
 
            except (RevisionNotPresent, KeyError), e:
 
1206
            except (RevisionNotPresent, KeyError) as e:
1126
1207
                # Some basis is not locally present: always fulltext
1127
1208
                return False
1128
1209
            index_memo, compression_parent, _, _ = parent_details
1153
1234
 
1154
1235
        A dict of key to (record_details, index_memo, next, parents) is
1155
1236
        returned.
1156
 
        method is the way referenced data should be applied.
1157
 
        index_memo is the handle to pass to the data access to actually get the
1158
 
            data
1159
 
        next is the build-parent of the version, or None for fulltexts.
1160
 
        parents is the version_ids of the parents of this version
1161
 
 
1162
 
        :param allow_missing: If True do not raise an error on a missing component,
1163
 
            just ignore it.
 
1237
 
 
1238
        * method is the way referenced data should be applied.
 
1239
        * index_memo is the handle to pass to the data access to actually get
 
1240
          the data
 
1241
        * next is the build-parent of the version, or None for fulltexts.
 
1242
        * parents is the version_ids of the parents of this version
 
1243
 
 
1244
        :param allow_missing: If True do not raise an error on a missing
 
1245
            component, just ignore it.
1164
1246
        """
1165
1247
        component_data = {}
1166
1248
        pending_components = keys
1168
1250
            build_details = self._index.get_build_details(pending_components)
1169
1251
            current_components = set(pending_components)
1170
1252
            pending_components = set()
1171
 
            for key, details in build_details.iteritems():
 
1253
            for key, details in viewitems(build_details):
1172
1254
                (index_memo, compression_parent, parents,
1173
1255
                 record_details) = details
1174
1256
                method = record_details[0]
1192
1274
        generator = _VFContentMapGenerator(self, [key])
1193
1275
        return generator._get_content(key)
1194
1276
 
1195
 
    def get_known_graph_ancestry(self, keys):
1196
 
        """Get a KnownGraph instance with the ancestry of keys."""
1197
 
        parent_map, missing_keys = self._index.find_ancestry(keys)
1198
 
        for fallback in self._fallback_vfs:
1199
 
            if not missing_keys:
1200
 
                break
1201
 
            (f_parent_map, f_missing_keys) = fallback._index.find_ancestry(
1202
 
                                                missing_keys)
1203
 
            parent_map.update(f_parent_map)
1204
 
            missing_keys = f_missing_keys
1205
 
        kg = _mod_graph.KnownGraph(parent_map)
1206
 
        return kg
1207
 
 
1208
1277
    def get_parent_map(self, keys):
1209
1278
        """Get a map of the graph parents of keys.
1210
1279
 
1225
1294
            and so on.
1226
1295
        """
1227
1296
        result = {}
1228
 
        sources = [self._index] + self._fallback_vfs
 
1297
        sources = [self._index] + self._immediate_fallback_vfs
1229
1298
        source_results = []
1230
1299
        missing = set(keys)
1231
1300
        for source in sources:
1241
1310
        """Produce a dictionary of knit records.
1242
1311
 
1243
1312
        :return: {key:(record, record_details, digest, next)}
1244
 
            record
1245
 
                data returned from read_records (a KnitContentobject)
1246
 
            record_details
1247
 
                opaque information to pass to parse_record
1248
 
            digest
1249
 
                SHA1 digest of the full text after all steps are done
1250
 
            next
1251
 
                build-parent of the version, i.e. the leftmost ancestor.
 
1313
 
 
1314
            * record: data returned from read_records (a KnitContentobject)
 
1315
            * record_details: opaque information to pass to parse_record
 
1316
            * digest: SHA1 digest of the full text after all steps are done
 
1317
            * next: build-parent of the version, i.e. the leftmost ancestor.
1252
1318
                Will be None if the record is not a delta.
 
1319
 
1253
1320
        :param keys: The keys to build a map for
1254
1321
        :param allow_missing: If some records are missing, rather than
1255
1322
            error, just return the data that could be generated.
1290
1357
                # key = component_id, r = record_details, i_m = index_memo,
1291
1358
                # n = next
1292
1359
                records = [(key, i_m) for key, (r, i_m, n)
1293
 
                                       in position_map.iteritems()]
 
1360
                                       in viewitems(position_map)]
1294
1361
                # Sort by the index memo, so that we request records from the
1295
1362
                # same pack file together, and in forward-sorted order
1296
1363
                records.sort(key=operator.itemgetter(1))
1299
1366
                    (record_details, index_memo, next) = position_map[key]
1300
1367
                    raw_record_map[key] = data, record_details, next
1301
1368
                return raw_record_map
1302
 
            except errors.RetryWithNewPacks, e:
 
1369
            except errors.RetryWithNewPacks as e:
1303
1370
                self._access.reload_or_raise(e)
1304
1371
 
1305
1372
    @classmethod
1408
1475
                    remaining_keys.discard(content_factory.key)
1409
1476
                    yield content_factory
1410
1477
                return
1411
 
            except errors.RetryWithNewPacks, e:
 
1478
            except errors.RetryWithNewPacks as e:
1412
1479
                self._access.reload_or_raise(e)
1413
1480
 
1414
1481
    def _get_remaining_record_stream(self, keys, ordering,
1421
1488
            # map from key to
1422
1489
            # (record_details, access_memo, compression_parent_key)
1423
1490
            positions = dict((key, self._build_details_to_components(details))
1424
 
                for key, details in build_details.iteritems())
 
1491
                for key, details in viewitems(build_details))
1425
1492
        absent_keys = keys.difference(set(positions))
1426
1493
        # There may be more absent keys : if we're missing the basis component
1427
1494
        # and are trying to include the delta closure.
1525
1592
                        yield KnitContentFactory(key, global_map[key],
1526
1593
                            record_details, None, raw_data, self._factory.annotated, None)
1527
1594
                else:
1528
 
                    vf = self._fallback_vfs[parent_maps.index(source) - 1]
 
1595
                    vf = self._immediate_fallback_vfs[parent_maps.index(source) - 1]
1529
1596
                    for record in vf.get_record_stream(keys, ordering,
1530
1597
                        include_delta_closure):
1531
1598
                        yield record
1535
1602
        missing = set(keys)
1536
1603
        record_map = self._get_record_map(missing, allow_missing=True)
1537
1604
        result = {}
1538
 
        for key, details in record_map.iteritems():
 
1605
        for key, details in viewitems(record_map):
1539
1606
            if key not in missing:
1540
1607
                continue
1541
1608
            # record entry 2 is the 'digest'.
1542
1609
            result[key] = details[2]
1543
1610
        missing.difference_update(set(result))
1544
 
        for source in self._fallback_vfs:
 
1611
        for source in self._immediate_fallback_vfs:
1545
1612
            if not missing:
1546
1613
                break
1547
1614
            new_result = source.get_sha1s(missing)
1572
1639
        else:
1573
1640
            # self is not annotated, but we can strip annotations cheaply.
1574
1641
            annotated = ""
1575
 
            convertibles = set(["knit-annotated-ft-gz"])
 
1642
            convertibles = {"knit-annotated-ft-gz"}
1576
1643
            if self._max_delta_chain:
1577
1644
                delta_types.add("knit-annotated-delta-gz")
1578
1645
                convertibles.add("knit-annotated-delta-gz")
1618
1685
                raise RevisionNotPresent([record.key], self)
1619
1686
            elif ((record.storage_kind in knit_types)
1620
1687
                  and (compression_parent is None
1621
 
                       or not self._fallback_vfs
1622
 
                       or self._index.has_key(compression_parent)
1623
 
                       or not self.has_key(compression_parent))):
 
1688
                       or not self._immediate_fallback_vfs
 
1689
                       or compression_parent in self._index
 
1690
                       or compression_parent not in self)):
1624
1691
                # we can insert the knit record literally if either it has no
1625
1692
                # compression parent OR we already have its basis in this kvf
1626
1693
                # OR the basis is not present even in the fallbacks.  In the
1628
1695
                # will be well, or it won't turn up at all and we'll raise an
1629
1696
                # error at the end.
1630
1697
                #
1631
 
                # TODO: self.has_key is somewhat redundant with
1632
 
                # self._index.has_key; we really want something that directly
 
1698
                # TODO: self.__contains__ is somewhat redundant with
 
1699
                # self._index.__contains__; we really want something that directly
1633
1700
                # asks if it's only present in the fallbacks. -- mbp 20081119
1634
1701
                if record.storage_kind not in native_types:
1635
1702
                    try:
1668
1735
                    #
1669
1736
                    # They're required to be physically in this
1670
1737
                    # KnitVersionedFiles, not in a fallback.
1671
 
                    if not self._index.has_key(compression_parent):
 
1738
                    if compression_parent not in self._index:
1672
1739
                        pending = buffered_index_entries.setdefault(
1673
1740
                            compression_parent, [])
1674
1741
                        pending.append(index_entry)
1767
1834
                # we need key, position, length
1768
1835
                key_records = []
1769
1836
                build_details = self._index.get_build_details(keys)
1770
 
                for key, details in build_details.iteritems():
 
1837
                for key, details in viewitems(build_details):
1771
1838
                    if key in keys:
1772
1839
                        key_records.append((key, details[0]))
1773
1840
                records_iter = enumerate(self._read_records_iter(key_records))
1774
1841
                for (key_idx, (key, data, sha_value)) in records_iter:
1775
 
                    pb.update('Walking content', key_idx, total)
 
1842
                    pb.update(gettext('Walking content'), key_idx, total)
1776
1843
                    compression_parent = build_details[key][1]
1777
1844
                    if compression_parent is None:
1778
1845
                        # fulltext
1790
1857
                    for line in line_iterator:
1791
1858
                        yield line, key
1792
1859
                done = True
1793
 
            except errors.RetryWithNewPacks, e:
 
1860
            except errors.RetryWithNewPacks as e:
1794
1861
                self._access.reload_or_raise(e)
1795
1862
        # If there are still keys we've not yet found, we look in the fallback
1796
1863
        # vfs, and hope to find them there.  Note that if the keys are found
1797
1864
        # but had no changes or no content, the fallback may not return
1798
1865
        # anything.
1799
 
        if keys and not self._fallback_vfs:
 
1866
        if keys and not self._immediate_fallback_vfs:
1800
1867
            # XXX: strictly the second parameter is meant to be the file id
1801
1868
            # but it's not easily accessible here.
1802
1869
            raise RevisionNotPresent(keys, repr(self))
1803
 
        for source in self._fallback_vfs:
 
1870
        for source in self._immediate_fallback_vfs:
1804
1871
            if not keys:
1805
1872
                break
1806
1873
            source_keys = set()
1808
1875
                source_keys.add(key)
1809
1876
                yield line, key
1810
1877
            keys.difference_update(source_keys)
1811
 
        pb.update('Walking content', total, total)
 
1878
        pb.update(gettext('Walking content'), total, total)
1812
1879
 
1813
1880
    def _make_line_delta(self, delta_seq, new_content):
1814
1881
        """Generate a line delta from delta_seq and new_content."""
1879
1946
        :return: the header and the decompressor stream.
1880
1947
                 as (stream, header_record)
1881
1948
        """
1882
 
        df = tuned_gzip.GzipFile(mode='rb', fileobj=StringIO(raw_data))
 
1949
        df = gzip.GzipFile(mode='rb', fileobj=BytesIO(raw_data))
1883
1950
        try:
1884
1951
            # Current serialise
1885
1952
            rec = self._check_header(key, df.readline())
1886
 
        except Exception, e:
 
1953
        except Exception as e:
1887
1954
            raise KnitCorrupt(self,
1888
1955
                              "While reading {%s} got %s(%s)"
1889
1956
                              % (key, e.__class__.__name__, str(e)))
1894
1961
        # 4168 calls in 2880 217 internal
1895
1962
        # 4168 calls to _parse_record_header in 2121
1896
1963
        # 4168 calls to readlines in 330
1897
 
        df = tuned_gzip.GzipFile(mode='rb', fileobj=StringIO(data))
 
1964
        df = gzip.GzipFile(mode='rb', fileobj=BytesIO(data))
1898
1965
        try:
1899
1966
            record_contents = df.readlines()
1900
 
        except Exception, e:
 
1967
        except Exception as e:
1901
1968
            raise KnitCorrupt(self, "Corrupt compressed record %r, got %s(%s)" %
1902
1969
                (data, e.__class__.__name__, str(e)))
1903
1970
        header = record_contents.pop(0)
1922
1989
        The result will be returned in whatever is the fastest to read.
1923
1990
        Not by the order requested. Also, multiple requests for the same
1924
1991
        record will only yield 1 response.
 
1992
 
1925
1993
        :param records: A list of (key, access_memo) entries
1926
1994
        :return: Yields (key, contents, digest) in the order
1927
1995
                 read, not the order requested
1939
2007
        raw_data = self._access.get_raw_records(
1940
2008
            [index_memo for key, index_memo in needed_records])
1941
2009
 
1942
 
        for (key, index_memo), data in \
1943
 
                izip(iter(needed_records), raw_data):
 
2010
        for (key, index_memo), data in zip(needed_records, raw_data):
1944
2011
            content, digest = self._parse_record(key[-1], data)
1945
2012
            yield key, content, digest
1946
2013
 
1976
2043
            raw_records = self._access.get_raw_records(needed_offsets)
1977
2044
 
1978
2045
        for key, index_memo in records:
1979
 
            data = raw_records.next()
 
2046
            data = next(raw_records)
1980
2047
            yield key, data
1981
2048
 
1982
2049
    def _record_to_data(self, key, digest, lines, dense_lines=None):
1985
2052
        :param key: The key of the record. Currently keys are always serialised
1986
2053
            using just the trailing component.
1987
2054
        :param dense_lines: The bytes of lines but in a denser form. For
1988
 
            instance, if lines is a list of 1000 bytestrings each ending in \n,
1989
 
            dense_lines may be a list with one line in it, containing all the
1990
 
            1000's lines and their \n's. Using dense_lines if it is already
1991
 
            known is a win because the string join to create bytes in this
1992
 
            function spends less time resizing the final string.
1993
 
        :return: (len, a StringIO instance with the raw data ready to read.)
 
2055
            instance, if lines is a list of 1000 bytestrings each ending in
 
2056
            \\n, dense_lines may be a list with one line in it, containing all
 
2057
            the 1000's lines and their \\n's. Using dense_lines if it is
 
2058
            already known is a win because the string join to create bytes in
 
2059
            this function spends less time resizing the final string.
 
2060
        :return: (len, a BytesIO instance with the raw data ready to read.)
1994
2061
        """
1995
2062
        chunks = ["version %s %d %s\n" % (key[-1], len(lines), digest)]
1996
2063
        chunks.extend(dense_lines or lines)
1997
2064
        chunks.append("end %s\n" % key[-1])
1998
2065
        for chunk in chunks:
1999
 
            if type(chunk) is not str:
 
2066
            if not isinstance(chunk, str):
2000
2067
                raise AssertionError(
2001
2068
                    'data must be plain bytes was %s' % type(chunk))
2002
2069
        if lines and lines[-1][-1] != '\n':
2015
2082
        """See VersionedFiles.keys."""
2016
2083
        if 'evil' in debug.debug_flags:
2017
2084
            trace.mutter_callsite(2, "keys scales with size of history")
2018
 
        sources = [self._index] + self._fallback_vfs
 
2085
        sources = [self._index] + self._immediate_fallback_vfs
2019
2086
        result = set()
2020
2087
        for source in sources:
2021
2088
            result.update(source.keys())
2033
2100
        # Note that _get_content is only called when the _ContentMapGenerator
2034
2101
        # has been constructed with just one key requested for reconstruction.
2035
2102
        if key in self.nonlocal_keys:
2036
 
            record = self.get_record_stream().next()
 
2103
            record = next(self.get_record_stream())
2037
2104
            # Create a content object on the fly
2038
2105
            lines = osutils.chunks_to_lines(record.get_bytes_as('chunked'))
2039
2106
            return PlainKnitContent(lines, record.key)
2061
2128
 
2062
2129
        missing_keys = set(nonlocal_keys)
2063
2130
        # Read from remote versioned file instances and provide to our caller.
2064
 
        for source in self.vf._fallback_vfs:
 
2131
        for source in self.vf._immediate_fallback_vfs:
2065
2132
            if not missing_keys:
2066
2133
                break
2067
2134
            # Loop over fallback repositories asking them for texts - ignore
2175
2242
        # one line with next ('' for None)
2176
2243
        # one line with byte count of the record bytes
2177
2244
        # the record bytes
2178
 
        for key, (record_bytes, (method, noeol), next) in \
2179
 
            self._raw_record_map.iteritems():
 
2245
        for key, (record_bytes, (method, noeol), next) in viewitems(
 
2246
                self._raw_record_map):
2180
2247
            key_bytes = '\x00'.join(key)
2181
2248
            parents = self.global_map.get(key, None)
2182
2249
            if parents is None:
2446
2513
                    line = "\n%s %s %s %s %s :" % (
2447
2514
                        key[-1], ','.join(options), pos, size,
2448
2515
                        self._dictionary_compress(parents))
2449
 
                    if type(line) is not str:
 
2516
                    if not isinstance(line, str):
2450
2517
                        raise AssertionError(
2451
2518
                            'data must be utf8 was %s' % type(line))
2452
2519
                    lines.append(line)
2570
2637
        elif 'line-delta' in options:
2571
2638
            return 'line-delta'
2572
2639
        else:
2573
 
            raise errors.KnitIndexUnknownMethod(self, options)
 
2640
            raise KnitIndexUnknownMethod(self, options)
2574
2641
 
2575
2642
    def get_options(self, key):
2576
2643
        """Return a list representing options.
2646
2713
        entry = self._kndx_cache[prefix][0][suffix]
2647
2714
        return key, entry[2], entry[3]
2648
2715
 
2649
 
    has_key = _mod_index._has_key_from_parent_map
 
2716
    __contains__ = _mod_index._has_key_from_parent_map
2650
2717
 
2651
2718
    def _init_index(self, path, extra_lines=[]):
2652
2719
        """Initialize an index."""
2653
 
        sio = StringIO()
 
2720
        sio = BytesIO()
2654
2721
        sio.write(self.HEADER)
2655
2722
        sio.writelines(extra_lines)
2656
2723
        sio.seek(0)
2668
2735
        result = set()
2669
2736
        # Identify all key prefixes.
2670
2737
        # XXX: A bit hacky, needs polish.
2671
 
        if type(self._mapper) is ConstantMapper:
 
2738
        if isinstance(self._mapper, ConstantMapper):
2672
2739
            prefixes = [()]
2673
2740
        else:
2674
2741
            relpaths = set()
2706
2773
                    del self._history
2707
2774
                except NoSuchFile:
2708
2775
                    self._kndx_cache[prefix] = ({}, [])
2709
 
                    if type(self._mapper) is ConstantMapper:
 
2776
                    if isinstance(self._mapper, ConstantMapper):
2710
2777
                        # preserve behaviour for revisions.kndx etc.
2711
2778
                        self._init_index(path)
2712
2779
                    del self._cache
2786
2853
        return key[:-1], key[-1]
2787
2854
 
2788
2855
 
2789
 
class _KeyRefs(object):
2790
 
 
2791
 
    def __init__(self, track_new_keys=False):
2792
 
        # dict mapping 'key' to 'set of keys referring to that key'
2793
 
        self.refs = {}
2794
 
        if track_new_keys:
2795
 
            # set remembering all new keys
2796
 
            self.new_keys = set()
2797
 
        else:
2798
 
            self.new_keys = None
2799
 
 
2800
 
    def clear(self):
2801
 
        if self.refs:
2802
 
            self.refs.clear()
2803
 
        if self.new_keys:
2804
 
            self.new_keys.clear()
2805
 
 
2806
 
    def add_references(self, key, refs):
2807
 
        # Record the new references
2808
 
        for referenced in refs:
2809
 
            try:
2810
 
                needed_by = self.refs[referenced]
2811
 
            except KeyError:
2812
 
                needed_by = self.refs[referenced] = set()
2813
 
            needed_by.add(key)
2814
 
        # Discard references satisfied by the new key
2815
 
        self.add_key(key)
2816
 
 
2817
 
    def get_new_keys(self):
2818
 
        return self.new_keys
2819
 
    
2820
 
    def get_unsatisfied_refs(self):
2821
 
        return self.refs.iterkeys()
2822
 
 
2823
 
    def _satisfy_refs_for_key(self, key):
2824
 
        try:
2825
 
            del self.refs[key]
2826
 
        except KeyError:
2827
 
            # No keys depended on this key.  That's ok.
2828
 
            pass
2829
 
 
2830
 
    def add_key(self, key):
2831
 
        # satisfy refs for key, and remember that we've seen this key.
2832
 
        self._satisfy_refs_for_key(key)
2833
 
        if self.new_keys is not None:
2834
 
            self.new_keys.add(key)
2835
 
 
2836
 
    def satisfy_refs_for_keys(self, keys):
2837
 
        for key in keys:
2838
 
            self._satisfy_refs_for_key(key)
2839
 
 
2840
 
    def get_referrers(self):
2841
 
        result = set()
2842
 
        for referrers in self.refs.itervalues():
2843
 
            result.update(referrers)
2844
 
        return result
2845
 
 
2846
 
 
2847
2856
class _KnitGraphIndex(object):
2848
2857
    """A KnitVersionedFiles index layered on GraphIndex."""
2849
2858
 
2851
2860
        add_callback=None, track_external_parent_refs=False):
2852
2861
        """Construct a KnitGraphIndex on a graph_index.
2853
2862
 
2854
 
        :param graph_index: An implementation of bzrlib.index.GraphIndex.
 
2863
        :param graph_index: An implementation of breezy.index.GraphIndex.
2855
2864
        :param is_locked: A callback to check whether the object should answer
2856
2865
            queries.
2857
2866
        :param deltas: Allow delta-compressed records.
2958
2967
                del keys[key]
2959
2968
        result = []
2960
2969
        if self._parents:
2961
 
            for key, (value, node_refs) in keys.iteritems():
 
2970
            for key, (value, node_refs) in viewitems(keys):
2962
2971
                result.append((key, value, node_refs))
2963
2972
        else:
2964
 
            for key, (value, node_refs) in keys.iteritems():
 
2973
            for key, (value, node_refs) in viewitems(keys):
2965
2974
                result.append((key, value))
2966
2975
        self._add_callback(result)
2967
2976
        if missing_compression_parents:
3156
3165
        node = self._get_node(key)
3157
3166
        return self._node_to_position(node)
3158
3167
 
3159
 
    has_key = _mod_index._has_key_from_parent_map
 
3168
    __contains__ = _mod_index._has_key_from_parent_map
3160
3169
 
3161
3170
    def keys(self):
3162
3171
        """Get all the keys in the collection.
3221
3230
            opaque index memo. For _KnitKeyAccess the memo is (key, pos,
3222
3231
            length), where the key is the record key.
3223
3232
        """
3224
 
        if type(raw_data) is not str:
 
3233
        if not isinstance(raw_data, str):
3225
3234
            raise AssertionError(
3226
3235
                'data must be plain bytes was %s' % type(raw_data))
3227
3236
        result = []
3278
3287
                yield data
3279
3288
 
3280
3289
 
3281
 
class _DirectPackAccess(object):
3282
 
    """Access to data in one or more packs with less translation."""
3283
 
 
3284
 
    def __init__(self, index_to_packs, reload_func=None, flush_func=None):
3285
 
        """Create a _DirectPackAccess object.
3286
 
 
3287
 
        :param index_to_packs: A dict mapping index objects to the transport
3288
 
            and file names for obtaining data.
3289
 
        :param reload_func: A function to call if we determine that the pack
3290
 
            files have moved and we need to reload our caches. See
3291
 
            bzrlib.repo_fmt.pack_repo.AggregateIndex for more details.
3292
 
        """
3293
 
        self._container_writer = None
3294
 
        self._write_index = None
3295
 
        self._indices = index_to_packs
3296
 
        self._reload_func = reload_func
3297
 
        self._flush_func = flush_func
3298
 
 
3299
 
    def add_raw_records(self, key_sizes, raw_data):
3300
 
        """Add raw knit bytes to a storage area.
3301
 
 
3302
 
        The data is spooled to the container writer in one bytes-record per
3303
 
        raw data item.
3304
 
 
3305
 
        :param sizes: An iterable of tuples containing the key and size of each
3306
 
            raw data segment.
3307
 
        :param raw_data: A bytestring containing the data.
3308
 
        :return: A list of memos to retrieve the record later. Each memo is an
3309
 
            opaque index memo. For _DirectPackAccess the memo is (index, pos,
3310
 
            length), where the index field is the write_index object supplied
3311
 
            to the PackAccess object.
3312
 
        """
3313
 
        if type(raw_data) is not str:
3314
 
            raise AssertionError(
3315
 
                'data must be plain bytes was %s' % type(raw_data))
3316
 
        result = []
3317
 
        offset = 0
3318
 
        for key, size in key_sizes:
3319
 
            p_offset, p_length = self._container_writer.add_bytes_record(
3320
 
                raw_data[offset:offset+size], [])
3321
 
            offset += size
3322
 
            result.append((self._write_index, p_offset, p_length))
3323
 
        return result
3324
 
 
3325
 
    def flush(self):
3326
 
        """Flush pending writes on this access object.
3327
 
 
3328
 
        This will flush any buffered writes to a NewPack.
3329
 
        """
3330
 
        if self._flush_func is not None:
3331
 
            self._flush_func()
3332
 
            
3333
 
    def get_raw_records(self, memos_for_retrieval):
3334
 
        """Get the raw bytes for a records.
3335
 
 
3336
 
        :param memos_for_retrieval: An iterable containing the (index, pos,
3337
 
            length) memo for retrieving the bytes. The Pack access method
3338
 
            looks up the pack to use for a given record in its index_to_pack
3339
 
            map.
3340
 
        :return: An iterator over the bytes of the records.
3341
 
        """
3342
 
        # first pass, group into same-index requests
3343
 
        request_lists = []
3344
 
        current_index = None
3345
 
        for (index, offset, length) in memos_for_retrieval:
3346
 
            if current_index == index:
3347
 
                current_list.append((offset, length))
3348
 
            else:
3349
 
                if current_index is not None:
3350
 
                    request_lists.append((current_index, current_list))
3351
 
                current_index = index
3352
 
                current_list = [(offset, length)]
3353
 
        # handle the last entry
3354
 
        if current_index is not None:
3355
 
            request_lists.append((current_index, current_list))
3356
 
        for index, offsets in request_lists:
3357
 
            try:
3358
 
                transport, path = self._indices[index]
3359
 
            except KeyError:
3360
 
                # A KeyError here indicates that someone has triggered an index
3361
 
                # reload, and this index has gone missing, we need to start
3362
 
                # over.
3363
 
                if self._reload_func is None:
3364
 
                    # If we don't have a _reload_func there is nothing that can
3365
 
                    # be done
3366
 
                    raise
3367
 
                raise errors.RetryWithNewPacks(index,
3368
 
                                               reload_occurred=True,
3369
 
                                               exc_info=sys.exc_info())
3370
 
            try:
3371
 
                reader = pack.make_readv_reader(transport, path, offsets)
3372
 
                for names, read_func in reader.iter_records():
3373
 
                    yield read_func(None)
3374
 
            except errors.NoSuchFile:
3375
 
                # A NoSuchFile error indicates that a pack file has gone
3376
 
                # missing on disk, we need to trigger a reload, and start over.
3377
 
                if self._reload_func is None:
3378
 
                    raise
3379
 
                raise errors.RetryWithNewPacks(transport.abspath(path),
3380
 
                                               reload_occurred=False,
3381
 
                                               exc_info=sys.exc_info())
3382
 
 
3383
 
    def set_writer(self, writer, index, transport_packname):
3384
 
        """Set a writer to use for adding data."""
3385
 
        if index is not None:
3386
 
            self._indices[index] = transport_packname
3387
 
        self._container_writer = writer
3388
 
        self._write_index = index
3389
 
 
3390
 
    def reload_or_raise(self, retry_exc):
3391
 
        """Try calling the reload function, or re-raise the original exception.
3392
 
 
3393
 
        This should be called after _DirectPackAccess raises a
3394
 
        RetryWithNewPacks exception. This function will handle the common logic
3395
 
        of determining when the error is fatal versus being temporary.
3396
 
        It will also make sure that the original exception is raised, rather
3397
 
        than the RetryWithNewPacks exception.
3398
 
 
3399
 
        If this function returns, then the calling function should retry
3400
 
        whatever operation was being performed. Otherwise an exception will
3401
 
        be raised.
3402
 
 
3403
 
        :param retry_exc: A RetryWithNewPacks exception.
3404
 
        """
3405
 
        is_error = False
3406
 
        if self._reload_func is None:
3407
 
            is_error = True
3408
 
        elif not self._reload_func():
3409
 
            # The reload claimed that nothing changed
3410
 
            if not retry_exc.reload_occurred:
3411
 
                # If there wasn't an earlier reload, then we really were
3412
 
                # expecting to find changes. We didn't find them, so this is a
3413
 
                # hard error
3414
 
                is_error = True
3415
 
        if is_error:
3416
 
            exc_class, exc_value, exc_traceback = retry_exc.exc_info
3417
 
            raise exc_class, exc_value, exc_traceback
3418
 
 
3419
 
 
3420
 
# Deprecated, use PatienceSequenceMatcher instead
3421
 
KnitSequenceMatcher = patiencediff.PatienceSequenceMatcher
3422
 
 
3423
 
 
3424
3290
def annotate_knit(knit, revision_id):
3425
3291
    """Annotate a knit with no cached annotations.
3426
3292
 
3469
3335
            passing to read_records_iter to start reading in the raw data from
3470
3336
            the pack file.
3471
3337
        """
3472
 
        pending = set([key])
 
3338
        pending = {key}
3473
3339
        records = []
3474
3340
        ann_keys = set()
3475
3341
        self._num_needed_children[key] = 1
3480
3346
            self._all_build_details.update(build_details)
3481
3347
            # new_nodes = self._vf._index._get_entries(this_iteration)
3482
3348
            pending = set()
3483
 
            for key, details in build_details.iteritems():
 
3349
            for key, details in viewitems(build_details):
3484
3350
                (index_memo, compression_parent, parent_keys,
3485
3351
                 record_details) = details
3486
3352
                self._parent_map[key] = parent_keys
3501
3367
                    else:
3502
3368
                        self._num_compression_children[compression_parent] = 1
3503
3369
 
3504
 
            missing_versions = this_iteration.difference(build_details.keys())
 
3370
            missing_versions = this_iteration.difference(build_details)
3505
3371
            if missing_versions:
3506
3372
                for key in missing_versions:
3507
3373
                    if key in self._parent_map and key in self._text_cache:
3524
3390
        return records, ann_keys
3525
3391
 
3526
3392
    def _get_needed_texts(self, key, pb=None):
3527
 
        # if True or len(self._vf._fallback_vfs) > 0:
3528
 
        if len(self._vf._fallback_vfs) > 0:
 
3393
        # if True or len(self._vf._immediate_fallback_vfs) > 0:
 
3394
        if len(self._vf._immediate_fallback_vfs) > 0:
3529
3395
            # If we have fallbacks, go to the generic path
3530
3396
            for v in annotate.Annotator._get_needed_texts(self, key, pb=pb):
3531
3397
                yield v
3536
3402
                for idx, (sub_key, text, num_lines) in enumerate(
3537
3403
                                                self._extract_texts(records)):
3538
3404
                    if pb is not None:
3539
 
                        pb.update('annotating', idx, len(records))
 
3405
                        pb.update(gettext('annotating'), idx, len(records))
3540
3406
                    yield sub_key, text, num_lines
3541
3407
                for sub_key in ann_keys:
3542
3408
                    text = self._text_cache[sub_key]
3543
3409
                    num_lines = len(text) # bad assumption
3544
3410
                    yield sub_key, text, num_lines
3545
3411
                return
3546
 
            except errors.RetryWithNewPacks, e:
 
3412
            except errors.RetryWithNewPacks as e:
3547
3413
                self._vf._access.reload_or_raise(e)
3548
3414
                # The cached build_details are no longer valid
3549
3415
                self._all_build_details.clear()
3708
3574
                    to_process.extend(self._process_pending(key))
3709
3575
 
3710
3576
try:
3711
 
    from bzrlib._knit_load_data_pyx import _load_data_c as _load_data
3712
 
except ImportError, e:
 
3577
    from ._knit_load_data_pyx import _load_data_c as _load_data
 
3578
except ImportError as e:
3713
3579
    osutils.failed_to_load_extension(e)
3714
 
    from bzrlib._knit_load_data_py import _load_data_py as _load_data
 
3580
    from ._knit_load_data_py import _load_data_py as _load_data