~bzr-pqm/bzr/bzr.dev

3830.3.12 by Martin Pool
Review cleanups: unify has_key impls, add missing_keys(), clean up exception blocks
1
# Copyright (C) 2007, 2008 Canonical Ltd
2592.1.4 by Robert Collins
Create a GraphIndexBuilder.
2
#
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
7
#
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
# GNU General Public License for more details.
12
#
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
17
"""Indexing facilities."""
18
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
19
__all__ = [
20
    'CombinedGraphIndex',
21
    'GraphIndex',
22
    'GraphIndexBuilder',
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
23
    'GraphIndexPrefixAdapter',
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
24
    'InMemoryGraphIndex',
25
    ]
2592.1.32 by Robert Collins
Add __all__ to index.
26
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
27
from bisect import bisect_right
2592.1.4 by Robert Collins
Create a GraphIndexBuilder.
28
from cStringIO import StringIO
2592.1.12 by Robert Collins
Handle basic node adds.
29
import re
3789.1.3 by John Arbash Meinel
CombinedGraphIndex can now reload when calling key_count().
30
import sys
2592.1.4 by Robert Collins
Create a GraphIndexBuilder.
31
2624.2.15 by Robert Collins
Add useful -Dindex flag.
32
from bzrlib.lazy_import import lazy_import
33
lazy_import(globals(), """
2745.1.2 by Robert Collins
Ensure mutter_callsite is not directly called on a lazy_load object, to make the stacklevel parameter work correctly.
34
from bzrlib import trace
2890.2.7 by Robert Collins
* Pack indices are now partially parsed for specific key lookup using a
35
from bzrlib.bisect_multi import bisect_multi_bytes
2979.2.2 by Robert Collins
Per-file graph heads detection during commit for pack repositories.
36
from bzrlib.revision import NULL_REVISION
2745.1.2 by Robert Collins
Ensure mutter_callsite is not directly called on a lazy_load object, to make the stacklevel parameter work correctly.
37
from bzrlib.trace import mutter
2624.2.15 by Robert Collins
Add useful -Dindex flag.
38
""")
3099.3.3 by John Arbash Meinel
Deprecate get_parents() in favor of get_parent_map()
39
from bzrlib import (
40
    debug,
41
    errors,
42
    symbol_versioning,
43
    )
2592.1.4 by Robert Collins
Create a GraphIndexBuilder.
44
2979.1.1 by Robert Collins
Use the GraphIndex header to answer key_count queries rather than parsing the entire index unnecessarily.
45
_HEADER_READV = (0, 200)
2624.2.8 by Robert Collins
Explicitly mark the number of keys elements in use in GraphIndex files.
46
_OPTION_KEY_ELEMENTS = "key_elements="
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
47
_OPTION_LEN = "len="
2592.1.6 by Robert Collins
Record the number of node reference lists a particular index has.
48
_OPTION_NODE_REFS = "node_ref_lists="
2592.1.4 by Robert Collins
Create a GraphIndexBuilder.
49
_SIGNATURE = "Bazaar Graph Index 1\n"
50
51
2592.1.14 by Robert Collins
Detect bad reference key values.
52
_whitespace_re = re.compile('[\t\n\x0b\x0c\r\x00 ]')
2592.1.12 by Robert Collins
Handle basic node adds.
53
_newline_null_re = re.compile('[\n\0]')
54
55
3830.3.12 by Martin Pool
Review cleanups: unify has_key impls, add missing_keys(), clean up exception blocks
56
def _has_key_from_parent_map(self, key):
57
    """Check if this index has one key.
58
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
59
    If it's possible to check for multiple keys at once through
3830.3.12 by Martin Pool
Review cleanups: unify has_key impls, add missing_keys(), clean up exception blocks
60
    calling get_parent_map that should be faster.
61
    """
62
    return (key in self.get_parent_map([key]))
63
3830.3.20 by John Arbash Meinel
Minor PEP8 and copyright updates.
64
3830.3.12 by Martin Pool
Review cleanups: unify has_key impls, add missing_keys(), clean up exception blocks
65
def _missing_keys_from_parent_map(self, keys):
66
    return set(keys) - set(self.get_parent_map(keys))
67
68
2592.1.4 by Robert Collins
Create a GraphIndexBuilder.
69
class GraphIndexBuilder(object):
2592.1.18 by Robert Collins
Add space to mark absent nodes.
70
    """A builder that can build a GraphIndex.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
71
2592.1.18 by Robert Collins
Add space to mark absent nodes.
72
    The resulting graph has the structure:
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
73
2592.1.18 by Robert Collins
Add space to mark absent nodes.
74
    _SIGNATURE OPTIONS NODES NEWLINE
75
    _SIGNATURE     := 'Bazaar Graph Index 1' NEWLINE
76
    OPTIONS        := 'node_ref_lists=' DIGITS NEWLINE
77
    NODES          := NODE*
78
    NODE           := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
79
    KEY            := Not-whitespace-utf8
80
    ABSENT         := 'a'
2592.1.19 by Robert Collins
Node references are tab separated.
81
    REFERENCES     := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
82
    REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
83
    REFERENCE      := DIGITS  ; digits is the byte offset in the index of the
84
                              ; referenced key.
2592.1.18 by Robert Collins
Add space to mark absent nodes.
85
    VALUE          := no-newline-no-null-bytes
86
    """
2592.1.4 by Robert Collins
Create a GraphIndexBuilder.
87
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
88
    def __init__(self, reference_lists=0, key_elements=1):
2592.1.6 by Robert Collins
Record the number of node reference lists a particular index has.
89
        """Create a GraphIndex builder.
90
91
        :param reference_lists: The number of node references lists for each
92
            entry.
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
93
        :param key_elements: The number of bytestrings in each key.
2592.1.6 by Robert Collins
Record the number of node reference lists a particular index has.
94
        """
95
        self.reference_lists = reference_lists
2592.3.62 by Robert Collins
Performance tweak - use a set for InMemoryGraph key iteration.
96
        self._keys = set()
3644.2.1 by John Arbash Meinel
Change the IndexBuilders to not generate the nodes_by_key unless needed.
97
        # A dict of {key: (absent, ref_lists, value)}
2592.1.15 by Robert Collins
Detect duplicate key insertion.
98
        self._nodes = {}
3644.2.1 by John Arbash Meinel
Change the IndexBuilders to not generate the nodes_by_key unless needed.
99
        self._nodes_by_key = None
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
100
        self._key_length = key_elements
3777.5.3 by John Arbash Meinel
Add Builder.set_optimize(for_size=True) for GraphIndexBuilder and BTreeBuilder.
101
        self._optimize_for_size = False
2624.2.5 by Robert Collins
Change bzrlib.index.Index keys to be 1-tuples, not strings.
102
103
    def _check_key(self, key):
104
        """Raise BadIndexKey if key is not a valid key for this index."""
105
        if type(key) != tuple:
106
            raise errors.BadIndexKey(key)
107
        if self._key_length != len(key):
108
            raise errors.BadIndexKey(key)
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
109
        for element in key:
110
            if not element or _whitespace_re.search(element) is not None:
111
                raise errors.BadIndexKey(element)
2592.1.12 by Robert Collins
Handle basic node adds.
112
3830.3.5 by Martin Pool
GraphIndexBuilder shouldn't know references are for compression so rename
113
    def _external_references(self):
114
        """Return references that are not present in this index.
3830.3.4 by Martin Pool
Move _external_compression_references onto the GraphIndexBuilder, and check them for inventories too
115
        """
116
        keys = set()
117
        refs = set()
3830.3.19 by John Arbash Meinel
Small update to GraphIndexBuilder._external_references
118
        # TODO: JAM 2008-11-21 This makes an assumption about how the reference
119
        #       lists are used. It is currently correct for pack-0.92 through
120
        #       1.9, which use the node references (3rd column) second
121
        #       reference list as the compression parent. Perhaps this should
122
        #       be moved into something higher up the stack, since it
123
        #       makes assumptions about how the index is used.
124
        if self.reference_lists > 1:
125
            for node in self.iter_all_entries():
126
                keys.add(node[1])
127
                refs.update(node[3][1])
128
            return refs - keys
129
        else:
130
            # If reference_lists == 0 there can be no external references, and
131
            # if reference_lists == 1, then there isn't a place to store the
132
            # compression parent
133
            return set()
3830.3.4 by Martin Pool
Move _external_compression_references onto the GraphIndexBuilder, and check them for inventories too
134
3644.2.4 by John Arbash Meinel
Change GraphIndex to also have a _get_nodes_by_key
135
    def _get_nodes_by_key(self):
136
        if self._nodes_by_key is None:
137
            nodes_by_key = {}
138
            if self.reference_lists:
139
                for key, (absent, references, value) in self._nodes.iteritems():
140
                    if absent:
141
                        continue
142
                    key_dict = nodes_by_key
143
                    for subkey in key[:-1]:
144
                        key_dict = key_dict.setdefault(subkey, {})
145
                    key_dict[key[-1]] = key, value, references
146
            else:
147
                for key, (absent, references, value) in self._nodes.iteritems():
148
                    if absent:
149
                        continue
150
                    key_dict = nodes_by_key
151
                    for subkey in key[:-1]:
152
                        key_dict = key_dict.setdefault(subkey, {})
153
                    key_dict[key[-1]] = key, value
154
            self._nodes_by_key = nodes_by_key
155
        return self._nodes_by_key
156
3644.2.3 by John Arbash Meinel
Do a bit more work to get all the tests to pass.
157
    def _update_nodes_by_key(self, key, value, node_refs):
158
        """Update the _nodes_by_key dict with a new key.
159
160
        For a key of (foo, bar, baz) create
161
        _nodes_by_key[foo][bar][baz] = key_value
162
        """
163
        if self._nodes_by_key is None:
164
            return
165
        key_dict = self._nodes_by_key
166
        if self.reference_lists:
167
            key_value = key, value, node_refs
168
        else:
169
            key_value = key, value
170
        for subkey in key[:-1]:
171
            key_dict = key_dict.setdefault(subkey, {})
172
        key_dict[key[-1]] = key_value
173
3644.2.9 by John Arbash Meinel
Refactor some code.
174
    def _check_key_ref_value(self, key, references, value):
175
        """Check that 'key' and 'references' are all valid.
2592.1.12 by Robert Collins
Handle basic node adds.
176
3644.2.9 by John Arbash Meinel
Refactor some code.
177
        :param key: A key tuple. Must conform to the key interface (be a tuple,
178
            be of the right length, not have any whitespace or nulls in any key
179
            element.)
180
        :param references: An iterable of reference lists. Something like
181
            [[(ref, key)], [(ref, key), (other, key)]]
182
        :param value: The value associate with this key. Must not contain
183
            newlines or null characters.
184
        :return: (node_refs, absent_references)
185
            node_refs   basically a packed form of 'references' where all
186
                        iterables are tuples
187
            absent_references   reference keys that are not in self._nodes.
188
                                This may contain duplicates if the same key is
189
                                referenced in multiple lists.
2592.1.12 by Robert Collins
Handle basic node adds.
190
        """
2624.2.5 by Robert Collins
Change bzrlib.index.Index keys to be 1-tuples, not strings.
191
        self._check_key(key)
2592.1.12 by Robert Collins
Handle basic node adds.
192
        if _newline_null_re.search(value) is not None:
193
            raise errors.BadIndexValue(value)
2592.1.13 by Robert Collins
Handle mismatched numbers of reference lists.
194
        if len(references) != self.reference_lists:
195
            raise errors.BadIndexValue(references)
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
196
        node_refs = []
3644.2.9 by John Arbash Meinel
Refactor some code.
197
        absent_references = []
2592.1.14 by Robert Collins
Detect bad reference key values.
198
        for reference_list in references:
199
            for reference in reference_list:
3644.2.9 by John Arbash Meinel
Refactor some code.
200
                # If reference *is* in self._nodes, then we know it has already
201
                # been checked.
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
202
                if reference not in self._nodes:
3644.2.9 by John Arbash Meinel
Refactor some code.
203
                    self._check_key(reference)
204
                    absent_references.append(reference)
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
205
            node_refs.append(tuple(reference_list))
3644.2.9 by John Arbash Meinel
Refactor some code.
206
        return tuple(node_refs), absent_references
207
208
    def add_node(self, key, value, references=()):
209
        """Add a node to the index.
210
211
        :param key: The key. keys are non-empty tuples containing
212
            as many whitespace-free utf8 bytestrings as the key length
213
            defined for this index.
214
        :param references: An iterable of iterables of keys. Each is a
215
            reference to another key.
216
        :param value: The value to associate with the key. It may be any
217
            bytes as long as it does not contain \0 or \n.
218
        """
219
        (node_refs,
220
         absent_references) = self._check_key_ref_value(key, references, value)
221
        if key in self._nodes and self._nodes[key][0] != 'a':
2592.1.15 by Robert Collins
Detect duplicate key insertion.
222
            raise errors.BadIndexDuplicateKey(key, self)
3644.2.9 by John Arbash Meinel
Refactor some code.
223
        for reference in absent_references:
224
            # There may be duplicates, but I don't think it is worth worrying
225
            # about
226
            self._nodes[reference] = ('a', (), '')
3644.2.3 by John Arbash Meinel
Do a bit more work to get all the tests to pass.
227
        self._nodes[key] = ('', node_refs, value)
2592.3.62 by Robert Collins
Performance tweak - use a set for InMemoryGraph key iteration.
228
        self._keys.add(key)
3644.2.9 by John Arbash Meinel
Refactor some code.
229
        if self._nodes_by_key is not None and self._key_length > 1:
3644.2.3 by John Arbash Meinel
Do a bit more work to get all the tests to pass.
230
            self._update_nodes_by_key(key, value, node_refs)
2592.1.6 by Robert Collins
Record the number of node reference lists a particular index has.
231
2592.1.4 by Robert Collins
Create a GraphIndexBuilder.
232
    def finish(self):
2592.1.6 by Robert Collins
Record the number of node reference lists a particular index has.
233
        lines = [_SIGNATURE]
234
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
2624.2.8 by Robert Collins
Explicitly mark the number of keys elements in use in GraphIndex files.
235
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
236
        lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
2624.2.11 by Robert Collins
Review comments.
237
        prefix_length = sum(len(x) for x in lines)
2592.1.22 by Robert Collins
Node references are byte offsets.
238
        # references are byte offsets. To avoid having to do nasty
3644.2.9 by John Arbash Meinel
Refactor some code.
239
        # polynomial work to resolve offsets (references to later in the
2592.1.22 by Robert Collins
Node references are byte offsets.
240
        # file cannot be determined until all the inbetween references have
241
        # been calculated too) we pad the offsets with 0's to make them be
242
        # of consistent length. Using binary offsets would break the trivial
243
        # file parsing.
244
        # to calculate the width of zero's needed we do three passes:
245
        # one to gather all the non-reference data and the number of references.
246
        # one to pad all the data with reference-length and determine entry
247
        # addresses.
248
        # One to serialise.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
249
2592.1.40 by Robert Collins
Reverse index ordering - we do not have date prefixed revids.
250
        # forward sorted by key. In future we may consider topological sorting,
251
        # at the cost of table scans for direct lookup, or a second index for
252
        # direct lookup
253
        nodes = sorted(self._nodes.items())
2592.1.42 by Robert Collins
Check the index length is as expected, when we have done preprocessing.
254
        # if we do not prepass, we don't know how long it will be up front.
255
        expected_bytes = None
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
256
        # we only need to pre-pass if we have reference lists at all.
257
        if self.reference_lists:
2592.1.41 by Robert Collins
Remove duplication in the index serialisation logic with John's suggestion.
258
            key_offset_info = []
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
259
            non_ref_bytes = prefix_length
260
            total_references = 0
261
            # TODO use simple multiplication for the constants in this loop.
262
            for key, (absent, references, value) in nodes:
2592.1.41 by Robert Collins
Remove duplication in the index serialisation logic with John's suggestion.
263
                # record the offset known *so far* for this key:
264
                # the non reference bytes to date, and the total references to
265
                # date - saves reaccumulating on the second pass
266
                key_offset_info.append((key, non_ref_bytes, total_references))
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
267
                # key is literal, value is literal, there are 3 null's, 1 NL
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
268
                # key is variable length tuple, \x00 between elements
2624.2.5 by Robert Collins
Change bzrlib.index.Index keys to be 1-tuples, not strings.
269
                non_ref_bytes += sum(len(element) for element in key)
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
270
                if self._key_length > 1:
271
                    non_ref_bytes += self._key_length - 1
2624.2.5 by Robert Collins
Change bzrlib.index.Index keys to be 1-tuples, not strings.
272
                # value is literal bytes, there are 3 null's, 1 NL.
273
                non_ref_bytes += len(value) + 3 + 1
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
274
                # one byte for absent if set.
275
                if absent:
276
                    non_ref_bytes += 1
2592.1.36 by Robert Collins
Bugfix incorrect offset generation when an absent record is before a referenced record.
277
                elif self.reference_lists:
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
278
                    # (ref_lists -1) tabs
279
                    non_ref_bytes += self.reference_lists - 1
280
                    # (ref-1 cr's per ref_list)
281
                    for ref_list in references:
282
                        # how many references across the whole file?
283
                        total_references += len(ref_list)
284
                        # accrue reference separators
285
                        if ref_list:
286
                            non_ref_bytes += len(ref_list) - 1
287
            # how many digits are needed to represent the total byte count?
288
            digits = 1
2592.1.22 by Robert Collins
Node references are byte offsets.
289
            possible_total_bytes = non_ref_bytes + total_references*digits
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
290
            while 10 ** digits < possible_total_bytes:
291
                digits += 1
292
                possible_total_bytes = non_ref_bytes + total_references*digits
2592.1.42 by Robert Collins
Check the index length is as expected, when we have done preprocessing.
293
            expected_bytes = possible_total_bytes + 1 # terminating newline
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
294
            # resolve key addresses.
295
            key_addresses = {}
2592.1.41 by Robert Collins
Remove duplication in the index serialisation logic with John's suggestion.
296
            for key, non_ref_bytes, total_references in key_offset_info:
297
                key_addresses[key] = non_ref_bytes + total_references*digits
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
298
            # serialise
299
            format_string = '%%0%sd' % digits
300
        for key, (absent, references, value) in nodes:
2592.1.19 by Robert Collins
Node references are tab separated.
301
            flattened_references = []
302
            for ref_list in references:
2592.1.22 by Robert Collins
Node references are byte offsets.
303
                ref_addresses = []
304
                for reference in ref_list:
305
                    ref_addresses.append(format_string % key_addresses[reference])
306
                flattened_references.append('\r'.join(ref_addresses))
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
307
            string_key = '\x00'.join(key)
2624.2.11 by Robert Collins
Review comments.
308
            lines.append("%s\x00%s\x00%s\x00%s\n" % (string_key, absent,
2592.1.19 by Robert Collins
Node references are tab separated.
309
                '\t'.join(flattened_references), value))
2592.1.6 by Robert Collins
Record the number of node reference lists a particular index has.
310
        lines.append('\n')
2592.1.42 by Robert Collins
Check the index length is as expected, when we have done preprocessing.
311
        result = StringIO(''.join(lines))
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
312
        if expected_bytes and len(result.getvalue()) != expected_bytes:
313
            raise errors.BzrError('Failed index creation. Internal error:'
314
                ' mismatched output length and expected length: %d %d' %
315
                (len(result.getvalue()), expected_bytes))
3498.1.1 by James Westby
Don't join the lines of the index twice.
316
        return result
2592.1.5 by Robert Collins
Trivial index reading.
317
3777.5.3 by John Arbash Meinel
Add Builder.set_optimize(for_size=True) for GraphIndexBuilder and BTreeBuilder.
318
    def set_optimize(self, for_size=True):
319
        """Change how the builder tries to optimize the result.
320
321
        :param for_size: Tell the builder to try and make the index as small as
322
            possible.
323
        :return: None
324
        """
325
        # GraphIndexBuilder itself doesn't pay attention to the flag yet, but
326
        # other builders do.
327
        self._optimize_for_size = for_size
328
2592.1.5 by Robert Collins
Trivial index reading.
329
330
class GraphIndex(object):
331
    """An index for data with embedded graphs.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
332
2592.1.10 by Robert Collins
Make validate detect node reference parsing errors.
333
    The index maps keys to a list of key reference lists, and a value.
334
    Each node has the same number of key reference lists. Each key reference
335
    list can be empty or an arbitrary length. The value is an opaque NULL
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
336
    terminated string without any newlines. The storage of the index is
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
337
    hidden in the interface: keys and key references are always tuples of
338
    bytestrings, never the internal representation (e.g. dictionary offsets).
2592.1.30 by Robert Collins
Absent entries are not yeilded.
339
340
    It is presumed that the index will not be mutated - it is static data.
2592.1.34 by Robert Collins
Cleanup docs.
341
2592.1.44 by Robert Collins
Remove some unneeded index iteration by checking if we have found all keys, and grammar improvements from Aaron's review.
342
    Successive iter_all_entries calls will read the entire index each time.
343
    Additionally, iter_entries calls will read the index linearly until the
344
    desired keys are found. XXX: This must be fixed before the index is
2592.1.34 by Robert Collins
Cleanup docs.
345
    suitable for production use. :XXX
2592.1.5 by Robert Collins
Trivial index reading.
346
    """
347
2890.2.1 by Robert Collins
* ``bzrlib.index.GraphIndex`` now requires a size parameter to the
348
    def __init__(self, transport, name, size):
2592.1.5 by Robert Collins
Trivial index reading.
349
        """Open an index called name on transport.
350
351
        :param transport: A bzrlib.transport.Transport.
352
        :param name: A path to provide to transport API calls.
2890.2.1 by Robert Collins
* ``bzrlib.index.GraphIndex`` now requires a size parameter to the
353
        :param size: The size of the index in bytes. This is used for bisection
354
            logic to perform partial index reads. While the size could be
355
            obtained by statting the file this introduced an additional round
2890.2.8 by Robert Collins
Make the size of the index optionally None for the pack-names index.
356
            trip as well as requiring stat'able transports, both of which are
357
            avoided by having it supplied. If size is None, then bisection
358
            support will be disabled and accessing the index will just stream
359
            all the data.
2592.1.5 by Robert Collins
Trivial index reading.
360
        """
361
        self._transport = transport
362
        self._name = name
2890.2.16 by Robert Collins
Review feedback.
363
        # Becomes a dict of key:(value, reference-list-byte-locations) used by
364
        # the bisection interface to store parsed but not resolved keys.
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
365
        self._bisect_nodes = None
2890.2.16 by Robert Collins
Review feedback.
366
        # Becomes a dict of key:(value, reference-list-keys) which are ready to
367
        # be returned directly to callers.
2624.2.2 by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram.
368
        self._nodes = None
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
369
        # a sorted list of slice-addresses for the parsed bytes of the file.
370
        # e.g. (0,1) would mean that byte 0 is parsed.
2890.2.2 by Robert Collins
Opening an index creates a map for the parsed bytes.
371
        self._parsed_byte_map = []
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
372
        # a sorted list of keys matching each slice address for parsed bytes
373
        # e.g. (None, 'foo@bar') would mean that the first byte contained no
374
        # key, and the end byte of the slice is the of the data for 'foo@bar'
375
        self._parsed_key_map = []
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
376
        self._key_count = None
2624.2.2 by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram.
377
        self._keys_by_offset = None
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
378
        self._nodes_by_key = None
2890.2.1 by Robert Collins
* ``bzrlib.index.GraphIndex`` now requires a size parameter to the
379
        self._size = size
3665.3.3 by John Arbash Meinel
If we read more than 50% of the whole index,
380
        # The number of bytes we've read so far in trying to process this file
381
        self._bytes_read = 0
2624.2.2 by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram.
382
2592.3.176 by Robert Collins
Various pack refactorings.
383
    def __eq__(self, other):
2592.3.215 by Robert Collins
Review feedback.
384
        """Equal when self and other were created with the same parameters."""
2592.3.176 by Robert Collins
Various pack refactorings.
385
        return (
386
            type(self) == type(other) and
387
            self._transport == other._transport and
388
            self._name == other._name and
389
            self._size == other._size)
390
391
    def __ne__(self, other):
392
        return not self.__eq__(other)
393
3517.4.13 by Martin Pool
Add repr methods
394
    def __repr__(self):
395
        return "%s(%r)" % (self.__class__.__name__,
396
            self._transport.abspath(self._name))
397
3665.3.1 by John Arbash Meinel
Updates to GraphIndex processing.
398
    def _buffer_all(self, stream=None):
2624.2.2 by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram.
399
        """Buffer all the index data.
400
401
        Mutates self._nodes and self.keys_by_offset.
2592.1.5 by Robert Collins
Trivial index reading.
402
        """
3665.3.1 by John Arbash Meinel
Updates to GraphIndex processing.
403
        if self._nodes is not None:
404
            # We already did this
405
            return
2624.2.15 by Robert Collins
Add useful -Dindex flag.
406
        if 'index' in debug.debug_flags:
407
            mutter('Reading entire index %s', self._transport.abspath(self._name))
3665.3.1 by John Arbash Meinel
Updates to GraphIndex processing.
408
        if stream is None:
409
            stream = self._transport.get(self._name)
2592.1.27 by Robert Collins
Test missing end lines with non-empty indices.
410
        self._read_prefix(stream)
2890.2.17 by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing.
411
        self._expected_elements = 3 + self._key_length
2592.1.27 by Robert Collins
Test missing end lines with non-empty indices.
412
        line_count = 0
2624.2.2 by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram.
413
        # raw data keyed by offset
414
        self._keys_by_offset = {}
415
        # ready-to-return key:value or key:value, node_ref_lists
416
        self._nodes = {}
3711.3.13 by John Arbash Meinel
Shave off another 5s by not building 'node_by_key'
417
        self._nodes_by_key = None
2592.1.27 by Robert Collins
Test missing end lines with non-empty indices.
418
        trailers = 0
419
        pos = stream.tell()
2890.2.17 by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing.
420
        lines = stream.read().split('\n')
421
        del lines[-1]
422
        _, _, _, trailers = self._parse_lines(lines, pos)
2624.2.2 by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram.
423
        for key, absent, references, value in self._keys_by_offset.itervalues():
2592.1.30 by Robert Collins
Absent entries are not yeilded.
424
            if absent:
425
                continue
2592.1.28 by Robert Collins
Basic two pass iter_all_entries.
426
            # resolve references:
427
            if self.node_ref_lists:
2890.2.17 by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing.
428
                node_value = (value, self._resolve_references(references))
2592.1.28 by Robert Collins
Basic two pass iter_all_entries.
429
            else:
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
430
                node_value = value
431
            self._nodes[key] = node_value
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
432
        # cache the keys for quick set intersections
2592.3.54 by Robert Collins
Fix remaining performance discrepancy with regular repositories.
433
        self._keys = set(self._nodes)
2592.1.27 by Robert Collins
Test missing end lines with non-empty indices.
434
        if trailers != 1:
435
            # there must be one line - the empty trailer line.
436
            raise errors.BadIndexData(self)
437
4011.5.11 by Robert Collins
Polish the KnitVersionedFiles.scan_unvalidated_index api.
438
    def external_references(self, ref_list_num):
4011.5.2 by Andrew Bennetts
Add more tests, improve existing tests, add GraphIndex._external_references()
439
        """Return references that are not present in this index.
440
        """
441
        self._buffer_all()
4011.5.3 by Andrew Bennetts
Implement and test external_references on GraphIndex and BTreeGraphIndex.
442
        if ref_list_num + 1 > self.node_ref_lists:
443
            raise ValueError('No ref list %d, index has %d ref lists'
444
                % (ref_list_num, self.node_ref_lists))
4011.5.2 by Andrew Bennetts
Add more tests, improve existing tests, add GraphIndex._external_references()
445
        refs = set()
446
        for key, (value, ref_lists) in self._nodes.iteritems():
447
            ref_list = ref_lists[ref_list_num]
448
            refs.update(ref_list)
449
        return refs - self._keys
450
3711.3.21 by John Arbash Meinel
Fix GraphIndex to properly generate _nodes_by_keys on demand.
451
    def _get_nodes_by_key(self):
452
        if self._nodes_by_key is None:
453
            nodes_by_key = {}
454
            if self.node_ref_lists:
455
                for key, (value, references) in self._nodes.iteritems():
456
                    key_dict = nodes_by_key
457
                    for subkey in key[:-1]:
458
                        key_dict = key_dict.setdefault(subkey, {})
459
                    key_dict[key[-1]] = key, value, references
460
            else:
461
                for key, value in self._nodes.iteritems():
462
                    key_dict = nodes_by_key
463
                    for subkey in key[:-1]:
464
                        key_dict = key_dict.setdefault(subkey, {})
465
                    key_dict[key[-1]] = key, value
466
            self._nodes_by_key = nodes_by_key
467
        return self._nodes_by_key
468
2624.2.2 by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram.
469
    def iter_all_entries(self):
470
        """Iterate over all keys within the index.
471
2592.5.1 by Martin Pool
Fix docstrings for Index.iter_entries etc
472
        :return: An iterable of (index, key, value) or (index, key, value, reference_lists).
2624.2.2 by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram.
473
            The former tuple is used when there are no reference lists in the
474
            index, making the API compatible with simple key:value index types.
475
            There is no defined order for the result iteration - it will be in
476
            the most efficient order for the index.
477
        """
2745.1.1 by Robert Collins
Add a number of -Devil checkpoints.
478
        if 'evil' in debug.debug_flags:
2592.3.112 by Robert Collins
Various fixups found dogfooding.
479
            trace.mutter_callsite(3,
2745.1.2 by Robert Collins
Ensure mutter_callsite is not directly called on a lazy_load object, to make the stacklevel parameter work correctly.
480
                "iter_all_entries scales with size of history.")
2624.2.2 by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram.
481
        if self._nodes is None:
482
            self._buffer_all()
483
        if self.node_ref_lists:
484
            for key, (value, node_ref_lists) in self._nodes.iteritems():
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
485
                yield self, key, value, node_ref_lists
2624.2.2 by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram.
486
        else:
487
            for key, value in self._nodes.iteritems():
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
488
                yield self, key, value
2624.2.2 by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram.
489
2592.1.27 by Robert Collins
Test missing end lines with non-empty indices.
490
    def _read_prefix(self, stream):
491
        signature = stream.read(len(self._signature()))
492
        if not signature == self._signature():
493
            raise errors.BadIndexFormatSignature(self._name, GraphIndex)
494
        options_line = stream.readline()
495
        if not options_line.startswith(_OPTION_NODE_REFS):
496
            raise errors.BadIndexOptions(self)
497
        try:
498
            self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):-1])
499
        except ValueError:
500
            raise errors.BadIndexOptions(self)
2624.2.8 by Robert Collins
Explicitly mark the number of keys elements in use in GraphIndex files.
501
        options_line = stream.readline()
502
        if not options_line.startswith(_OPTION_KEY_ELEMENTS):
503
            raise errors.BadIndexOptions(self)
504
        try:
505
            self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):-1])
506
        except ValueError:
507
            raise errors.BadIndexOptions(self)
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
508
        options_line = stream.readline()
509
        if not options_line.startswith(_OPTION_LEN):
510
            raise errors.BadIndexOptions(self)
511
        try:
512
            self._key_count = int(options_line[len(_OPTION_LEN):-1])
513
        except ValueError:
514
            raise errors.BadIndexOptions(self)
2592.1.5 by Robert Collins
Trivial index reading.
515
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
516
    def _resolve_references(self, references):
2890.2.16 by Robert Collins
Review feedback.
517
        """Return the resolved key references for references.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
518
2890.2.16 by Robert Collins
Review feedback.
519
        References are resolved by looking up the location of the key in the
520
        _keys_by_offset map and substituting the key name, preserving ordering.
521
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
522
        :param references: An iterable of iterables of key locations. e.g.
2890.2.16 by Robert Collins
Review feedback.
523
            [[123, 456], [123]]
524
        :return: A tuple of tuples of keys.
525
        """
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
526
        node_refs = []
527
        for ref_list in references:
528
            node_refs.append(tuple([self._keys_by_offset[ref][0] for ref in ref_list]))
529
        return tuple(node_refs)
530
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
531
    def _find_index(self, range_map, key):
532
        """Helper for the _parsed_*_index calls.
533
534
        Given a range map - [(start, end), ...], finds the index of the range
535
        in the map for key if it is in the map, and if it is not there, the
536
        immediately preceeding range in the map.
537
        """
538
        result = bisect_right(range_map, key) - 1
539
        if result + 1 < len(range_map):
540
            # check the border condition, it may be in result + 1
541
            if range_map[result + 1][0] == key[0]:
542
                return result + 1
543
        return result
544
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
545
    def _parsed_byte_index(self, offset):
546
        """Return the index of the entry immediately before offset.
547
548
        e.g. if the parsed map has regions 0,10 and 11,12 parsed, meaning that
549
        there is one unparsed byte (the 11th, addressed as[10]). then:
550
        asking for 0 will return 0
551
        asking for 10 will return 0
552
        asking for 11 will return 1
553
        asking for 12 will return 1
554
        """
555
        key = (offset, 0)
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
556
        return self._find_index(self._parsed_byte_map, key)
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
557
558
    def _parsed_key_index(self, key):
559
        """Return the index of the entry immediately before key.
560
561
        e.g. if the parsed map has regions (None, 'a') and ('b','c') parsed,
562
        meaning that keys from None to 'a' inclusive, and 'b' to 'c' inclusive
563
        have been parsed, then:
564
        asking for '' will return 0
565
        asking for 'a' will return 0
566
        asking for 'b' will return 1
567
        asking for 'e' will return 1
568
        """
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
569
        search_key = (key, None)
570
        return self._find_index(self._parsed_key_map, search_key)
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
571
572
    def _is_parsed(self, offset):
573
        """Returns True if offset has been parsed."""
574
        index = self._parsed_byte_index(offset)
575
        if index == len(self._parsed_byte_map):
576
            return offset < self._parsed_byte_map[index - 1][1]
577
        start, end = self._parsed_byte_map[index]
578
        return offset >= start and offset < end
579
2890.2.7 by Robert Collins
* Pack indices are now partially parsed for specific key lookup using a
580
    def _iter_entries_from_total_buffer(self, keys):
581
        """Iterate over keys when the entire index is parsed."""
2592.3.54 by Robert Collins
Fix remaining performance discrepancy with regular repositories.
582
        keys = keys.intersection(self._keys)
2624.2.3 by Robert Collins
Make GraphIndex.iter_entries do hash lookups rather than table scans.
583
        if self.node_ref_lists:
584
            for key in keys:
585
                value, node_refs = self._nodes[key]
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
586
                yield self, key, value, node_refs
2624.2.3 by Robert Collins
Make GraphIndex.iter_entries do hash lookups rather than table scans.
587
        else:
588
            for key in keys:
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
589
                yield self, key, self._nodes[key]
2592.1.7 by Robert Collins
A validate that goes boom.
590
2890.2.7 by Robert Collins
* Pack indices are now partially parsed for specific key lookup using a
591
    def iter_entries(self, keys):
592
        """Iterate over keys within the index.
593
594
        :param keys: An iterable providing the keys to be retrieved.
595
        :return: An iterable as per iter_all_entries, but restricted to the
596
            keys supplied. No additional keys will be returned, and every
597
            key supplied that is in the index will be returned.
598
        """
599
        keys = set(keys)
600
        if not keys:
601
            return []
2890.2.8 by Robert Collins
Make the size of the index optionally None for the pack-names index.
602
        if self._size is None and self._nodes is None:
603
            self._buffer_all()
3665.3.3 by John Arbash Meinel
If we read more than 50% of the whole index,
604
3606.6.1 by Robert Collins
Cherry-pick Robert's index buffering.
605
        # We fit about 20 keys per minimum-read (4K), so if we are looking for
606
        # more than 1/20th of the index its likely (assuming homogenous key
607
        # spread) that we'll read the entire index. If we're going to do that,
608
        # buffer the whole thing. A better analysis might take key spread into
609
        # account - but B+Tree indices are better anyway.
610
        # We could look at all data read, and use a threshold there, which will
611
        # trigger on ancestry walks, but that is not yet fully mapped out.
612
        if self._nodes is None and len(keys) * 20 > self.key_count():
613
            self._buffer_all()
2890.2.7 by Robert Collins
* Pack indices are now partially parsed for specific key lookup using a
614
        if self._nodes is not None:
615
            return self._iter_entries_from_total_buffer(keys)
616
        else:
617
            return (result[1] for result in bisect_multi_bytes(
2890.2.18 by Robert Collins
Review feedback.
618
                self._lookup_keys_via_location, self._size, keys))
2890.2.7 by Robert Collins
* Pack indices are now partially parsed for specific key lookup using a
619
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
620
    def iter_entries_prefix(self, keys):
621
        """Iterate over keys within the index using prefix matching.
622
623
        Prefix matching is applied within the tuple of a key, not to within
624
        the bytestring of each key element. e.g. if you have the keys ('foo',
625
        'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
626
        only the former key is returned.
627
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
628
        WARNING: Note that this method currently causes a full index parse
629
        unconditionally (which is reasonably appropriate as it is a means for
630
        thunking many small indices into one larger one and still supplies
631
        iter_all_entries at the thunk layer).
632
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
633
        :param keys: An iterable providing the key prefixes to be retrieved.
634
            Each key prefix takes the form of a tuple the length of a key, but
635
            with the last N elements 'None' rather than a regular bytestring.
636
            The first element cannot be 'None'.
637
        :return: An iterable as per iter_all_entries, but restricted to the
638
            keys with a matching prefix to those supplied. No additional keys
639
            will be returned, and every match that is in the index will be
640
            returned.
641
        """
642
        keys = set(keys)
643
        if not keys:
644
            return
645
        # load data - also finds key lengths
646
        if self._nodes is None:
647
            self._buffer_all()
648
        if self._key_length == 1:
649
            for key in keys:
650
                # sanity check
651
                if key[0] is None:
652
                    raise errors.BadIndexKey(key)
653
                if len(key) != self._key_length:
654
                    raise errors.BadIndexKey(key)
655
                if self.node_ref_lists:
656
                    value, node_refs = self._nodes[key]
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
657
                    yield self, key, value, node_refs
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
658
                else:
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
659
                    yield self, key, self._nodes[key]
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
660
            return
3711.3.21 by John Arbash Meinel
Fix GraphIndex to properly generate _nodes_by_keys on demand.
661
        nodes_by_key = self._get_nodes_by_key()
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
662
        for key in keys:
663
            # sanity check
664
            if key[0] is None:
665
                raise errors.BadIndexKey(key)
666
            if len(key) != self._key_length:
667
                raise errors.BadIndexKey(key)
668
            # find what it refers to:
3711.3.21 by John Arbash Meinel
Fix GraphIndex to properly generate _nodes_by_keys on demand.
669
            key_dict = nodes_by_key
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
670
            elements = list(key)
2624.2.11 by Robert Collins
Review comments.
671
            # find the subdict whose contents should be returned.
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
672
            try:
673
                while len(elements) and elements[0] is not None:
674
                    key_dict = key_dict[elements[0]]
675
                    elements.pop(0)
676
            except KeyError:
677
                # a non-existant lookup.
678
                continue
679
            if len(elements):
680
                dicts = [key_dict]
681
                while dicts:
682
                    key_dict = dicts.pop(-1)
683
                    # can't be empty or would not exist
684
                    item, value = key_dict.iteritems().next()
685
                    if type(value) == dict:
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
686
                        # push keys
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
687
                        dicts.extend(key_dict.itervalues())
688
                    else:
689
                        # yield keys
690
                        for value in key_dict.itervalues():
2624.2.11 by Robert Collins
Review comments.
691
                            # each value is the key:value:node refs tuple
692
                            # ready to yield.
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
693
                            yield (self, ) + value
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
694
            else:
2624.2.11 by Robert Collins
Review comments.
695
                # the last thing looked up was a terminal element
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
696
                yield (self, ) + key_dict
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
697
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
698
    def key_count(self):
699
        """Return an estimate of the number of keys in this index.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
700
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
701
        For GraphIndex the estimate is exact.
702
        """
703
        if self._key_count is None:
2979.1.1 by Robert Collins
Use the GraphIndex header to answer key_count queries rather than parsing the entire index unnecessarily.
704
            self._read_and_parse([_HEADER_READV])
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
705
        return self._key_count
706
2890.2.18 by Robert Collins
Review feedback.
707
    def _lookup_keys_via_location(self, location_keys):
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
708
        """Public interface for implementing bisection.
709
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
710
        If _buffer_all has been called, then all the data for the index is in
711
        memory, and this method should not be called, as it uses a separate
712
        cache because it cannot pre-resolve all indices, which buffer_all does
713
        for performance.
714
2890.2.16 by Robert Collins
Review feedback.
715
        :param location_keys: A list of location(byte offset), key tuples.
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
716
        :return: A list of (location_key, result) tuples as expected by
717
            bzrlib.bisect_multi.bisect_multi_bytes.
718
        """
719
        # Possible improvements:
720
        #  - only bisect lookup each key once
721
        #  - sort the keys first, and use that to reduce the bisection window
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
722
        # -----
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
723
        # this progresses in three parts:
724
        # read data
725
        # parse it
726
        # attempt to answer the question from the now in memory data.
727
        # build the readv request
728
        # for each location, ask for 800 bytes - much more than rows we've seen
729
        # anywhere.
730
        readv_ranges = []
731
        for location, key in location_keys:
732
            # can we answer from cache?
2911.3.1 by Robert Collins
(robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins).
733
            if self._bisect_nodes and key in self._bisect_nodes:
734
                # We have the key parsed.
735
                continue
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
736
            index = self._parsed_key_index(key)
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
737
            if (len(self._parsed_key_map) and
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
738
                self._parsed_key_map[index][0] <= key and
2911.3.1 by Robert Collins
(robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins).
739
                (self._parsed_key_map[index][1] >= key or
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
740
                 # end of the file has been parsed
741
                 self._parsed_byte_map[index][1] == self._size)):
2911.3.1 by Robert Collins
(robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins).
742
                # the key has been parsed, so no lookup is needed even if its
743
                # not present.
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
744
                continue
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
745
            # - if we have examined this part of the file already - yes
746
            index = self._parsed_byte_index(location)
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
747
            if (len(self._parsed_byte_map) and
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
748
                self._parsed_byte_map[index][0] <= location and
749
                self._parsed_byte_map[index][1] > location):
750
                # the byte region has been parsed, so no read is needed.
751
                continue
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
752
            length = 800
753
            if location + length > self._size:
754
                length = self._size - location
755
            # todo, trim out parsed locations.
756
            if length > 0:
757
                readv_ranges.append((location, length))
758
        # read the header if needed
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
759
        if self._bisect_nodes is None:
2979.1.1 by Robert Collins
Use the GraphIndex header to answer key_count queries rather than parsing the entire index unnecessarily.
760
            readv_ranges.append(_HEADER_READV)
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
761
        self._read_and_parse(readv_ranges)
3665.3.1 by John Arbash Meinel
Updates to GraphIndex processing.
762
        result = []
763
        if self._nodes is not None:
764
            # _read_and_parse triggered a _buffer_all because we requested the
765
            # whole data range
766
            for location, key in location_keys:
767
                if key not in self._nodes: # not present
768
                    result.append(((location, key), False))
769
                elif self.node_ref_lists:
770
                    value, refs = self._nodes[key]
771
                    result.append(((location, key),
772
                        (self, key, value, refs)))
773
                else:
774
                    result.append(((location, key),
775
                        (self, key, self._nodes[key])))
776
            return result
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
777
        # generate results:
778
        #  - figure out <, >, missing, present
779
        #  - result present references so we can return them.
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
780
        # keys that we cannot answer until we resolve references
781
        pending_references = []
782
        pending_locations = set()
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
783
        for location, key in location_keys:
784
            # can we answer from cache?
2911.3.1 by Robert Collins
(robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins).
785
            if key in self._bisect_nodes:
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
786
                # the key has been parsed, so no lookup is needed
2911.3.1 by Robert Collins
(robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins).
787
                if self.node_ref_lists:
788
                    # the references may not have been all parsed.
789
                    value, refs = self._bisect_nodes[key]
790
                    wanted_locations = []
791
                    for ref_list in refs:
792
                        for ref in ref_list:
793
                            if ref not in self._keys_by_offset:
794
                                wanted_locations.append(ref)
795
                    if wanted_locations:
796
                        pending_locations.update(wanted_locations)
797
                        pending_references.append((location, key))
798
                        continue
799
                    result.append(((location, key), (self, key,
800
                        value, self._resolve_references(refs))))
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
801
                else:
2911.3.1 by Robert Collins
(robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins).
802
                    result.append(((location, key),
803
                        (self, key, self._bisect_nodes[key])))
804
                continue
805
            else:
806
                # has the region the key should be in, been parsed?
807
                index = self._parsed_key_index(key)
808
                if (self._parsed_key_map[index][0] <= key and
809
                    (self._parsed_key_map[index][1] >= key or
810
                     # end of the file has been parsed
811
                     self._parsed_byte_map[index][1] == self._size)):
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
812
                    result.append(((location, key), False))
2911.3.1 by Robert Collins
(robertc) Improve index bisection lookup performance looking for keys in the parsed dict before doing bisection searches in the parsed ranges. (Robert Collins).
813
                    continue
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
814
            # no, is the key above or below the probed location:
815
            # get the range of the probed & parsed location
816
            index = self._parsed_byte_index(location)
817
            # if the key is below the start of the range, its below
818
            if key < self._parsed_key_map[index][0]:
819
                direction = -1
820
            else:
821
                direction = +1
822
            result.append(((location, key), direction))
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
823
        readv_ranges = []
824
        # lookup data to resolve references
825
        for location in pending_locations:
826
            length = 800
827
            if location + length > self._size:
828
                length = self._size - location
829
            # TODO: trim out parsed locations (e.g. if the 800 is into the
2890.2.16 by Robert Collins
Review feedback.
830
            # parsed region trim it, and dont use the adjust_for_latency
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
831
            # facility)
832
            if length > 0:
833
                readv_ranges.append((location, length))
834
        self._read_and_parse(readv_ranges)
3665.3.5 by John Arbash Meinel
Move the point at which we 'buffer_all' if we've read >50% of the index.
835
        if self._nodes is not None:
836
            # The _read_and_parse triggered a _buffer_all, grab the data and
837
            # return it
838
            for location, key in pending_references:
839
                value, refs = self._nodes[key]
840
                result.append(((location, key), (self, key, value, refs)))
841
            return result
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
842
        for location, key in pending_references:
843
            # answer key references we had to look-up-late.
844
            value, refs = self._bisect_nodes[key]
845
            result.append(((location, key), (self, key,
846
                value, self._resolve_references(refs))))
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
847
        return result
848
849
    def _parse_header_from_bytes(self, bytes):
850
        """Parse the header from a region of bytes.
851
852
        :param bytes: The data to parse.
853
        :return: An offset, data tuple such as readv yields, for the unparsed
854
            data. (which may length 0).
855
        """
856
        signature = bytes[0:len(self._signature())]
857
        if not signature == self._signature():
858
            raise errors.BadIndexFormatSignature(self._name, GraphIndex)
859
        lines = bytes[len(self._signature()):].splitlines()
860
        options_line = lines[0]
861
        if not options_line.startswith(_OPTION_NODE_REFS):
862
            raise errors.BadIndexOptions(self)
863
        try:
864
            self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):])
865
        except ValueError:
866
            raise errors.BadIndexOptions(self)
867
        options_line = lines[1]
868
        if not options_line.startswith(_OPTION_KEY_ELEMENTS):
869
            raise errors.BadIndexOptions(self)
870
        try:
871
            self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):])
872
        except ValueError:
873
            raise errors.BadIndexOptions(self)
874
        options_line = lines[2]
875
        if not options_line.startswith(_OPTION_LEN):
876
            raise errors.BadIndexOptions(self)
877
        try:
878
            self._key_count = int(options_line[len(_OPTION_LEN):])
879
        except ValueError:
880
            raise errors.BadIndexOptions(self)
881
        # calculate the bytes we have processed
882
        header_end = (len(signature) + len(lines[0]) + len(lines[1]) +
883
            len(lines[2]) + 3)
884
        self._parsed_bytes(0, None, header_end, None)
885
        # setup parsing state
886
        self._expected_elements = 3 + self._key_length
887
        # raw data keyed by offset
888
        self._keys_by_offset = {}
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
889
        # keys with the value and node references
890
        self._bisect_nodes = {}
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
891
        return header_end, bytes[header_end:]
892
893
    def _parse_region(self, offset, data):
894
        """Parse node data returned from a readv operation.
895
896
        :param offset: The byte offset the data starts at.
897
        :param data: The data to parse.
898
        """
899
        # trim the data.
900
        # end first:
901
        end = offset + len(data)
2890.2.15 by Robert Collins
Corner case when parsing repeated sections - the bottom section of a region may not be parsed, so we need to manually advance past that.
902
        high_parsed = offset
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
903
        while True:
904
            # Trivial test - if the current index's end is within the
905
            # low-matching parsed range, we're done.
2890.2.15 by Robert Collins
Corner case when parsing repeated sections - the bottom section of a region may not be parsed, so we need to manually advance past that.
906
            index = self._parsed_byte_index(high_parsed)
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
907
            if end < self._parsed_byte_map[index][1]:
908
                return
2890.2.15 by Robert Collins
Corner case when parsing repeated sections - the bottom section of a region may not be parsed, so we need to manually advance past that.
909
            # print "[%d:%d]" % (offset, end), \
910
            #     self._parsed_byte_map[index:index + 2]
911
            high_parsed, last_segment = self._parse_segment(
912
                offset, data, end, index)
913
            if last_segment:
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
914
                return
915
916
    def _parse_segment(self, offset, data, end, index):
917
        """Parse one segment of data.
918
919
        :param offset: Where 'data' begins in the file.
920
        :param data: Some data to parse a segment of.
921
        :param end: Where data ends
922
        :param index: The current index into the parsed bytes map.
923
        :return: True if the parsed segment is the last possible one in the
924
            range of data.
2890.2.15 by Robert Collins
Corner case when parsing repeated sections - the bottom section of a region may not be parsed, so we need to manually advance past that.
925
        :return: high_parsed_byte, last_segment.
926
            high_parsed_byte is the location of the highest parsed byte in this
927
            segment, last_segment is True if the parsed segment is the last
928
            possible one in the data block.
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
929
        """
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
930
        # default is to use all data
931
        trim_end = None
932
        # accomodate overlap with data before this.
933
        if offset < self._parsed_byte_map[index][1]:
934
            # overlaps the lower parsed region
935
            # skip the parsed data
936
            trim_start = self._parsed_byte_map[index][1] - offset
937
            # don't trim the start for \n
938
            start_adjacent = True
939
        elif offset == self._parsed_byte_map[index][1]:
940
            # abuts the lower parsed region
941
            # use all data
942
            trim_start = None
943
            # do not trim anything
944
            start_adjacent = True
945
        else:
946
            # does not overlap the lower parsed region
947
            # use all data
948
            trim_start = None
949
            # but trim the leading \n
950
            start_adjacent = False
951
        if end == self._size:
952
            # lines up to the end of all data:
953
            # use it all
954
            trim_end = None
955
            # do not strip to the last \n
956
            end_adjacent = True
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
957
            last_segment = True
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
958
        elif index + 1 == len(self._parsed_byte_map):
959
            # at the end of the parsed data
960
            # use it all
961
            trim_end = None
962
            # but strip to the last \n
963
            end_adjacent = False
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
964
            last_segment = True
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
965
        elif end == self._parsed_byte_map[index + 1][0]:
966
            # buts up against the next parsed region
967
            # use it all
968
            trim_end = None
969
            # do not strip to the last \n
970
            end_adjacent = True
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
971
            last_segment = True
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
972
        elif end > self._parsed_byte_map[index + 1][0]:
973
            # overlaps into the next parsed region
974
            # only consider the unparsed data
975
            trim_end = self._parsed_byte_map[index + 1][0] - offset
976
            # do not strip to the last \n as we know its an entire record
977
            end_adjacent = True
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
978
            last_segment = end < self._parsed_byte_map[index + 1][1]
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
979
        else:
980
            # does not overlap into the next region
981
            # use it all
982
            trim_end = None
983
            # but strip to the last \n
984
            end_adjacent = False
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
985
            last_segment = True
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
986
        # now find bytes to discard if needed
987
        if not start_adjacent:
988
            # work around python bug in rfind
989
            if trim_start is None:
990
                trim_start = data.find('\n') + 1
991
            else:
992
                trim_start = data.find('\n', trim_start) + 1
3376.2.4 by Martin Pool
Remove every assert statement from bzrlib!
993
            if not (trim_start != 0):
994
                raise AssertionError('no \n was present')
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
995
            # print 'removing start', offset, trim_start, repr(data[:trim_start])
996
        if not end_adjacent:
997
            # work around python bug in rfind
998
            if trim_end is None:
999
                trim_end = data.rfind('\n') + 1
1000
            else:
1001
                trim_end = data.rfind('\n', None, trim_end) + 1
3376.2.4 by Martin Pool
Remove every assert statement from bzrlib!
1002
            if not (trim_end != 0):
1003
                raise AssertionError('no \n was present')
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
1004
            # print 'removing end', offset, trim_end, repr(data[trim_end:])
1005
        # adjust offset and data to the parseable data.
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
1006
        trimmed_data = data[trim_start:trim_end]
3376.2.4 by Martin Pool
Remove every assert statement from bzrlib!
1007
        if not (trimmed_data):
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1008
            raise AssertionError('read unneeded data [%d:%d] from [%d:%d]'
3376.2.4 by Martin Pool
Remove every assert statement from bzrlib!
1009
                % (trim_start, trim_end, offset, offset + len(data)))
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
1010
        if trim_start:
1011
            offset += trim_start
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
1012
        # print "parsing", repr(trimmed_data)
2890.2.10 by Robert Collins
Add test coverage to ensure \r's are not mangled by bisection parsing.
1013
        # splitlines mangles the \r delimiters.. don't use it.
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
1014
        lines = trimmed_data.split('\n')
2890.2.9 by Robert Collins
Don't use splitlines for index data parsing, we embed \r.
1015
        del lines[-1]
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
1016
        pos = offset
2890.2.17 by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing.
1017
        first_key, last_key, nodes, _ = self._parse_lines(lines, pos)
1018
        for key, value in nodes:
1019
            self._bisect_nodes[key] = value
1020
        self._parsed_bytes(offset, first_key,
1021
            offset + len(trimmed_data), last_key)
1022
        return offset + len(trimmed_data), last_segment
1023
1024
    def _parse_lines(self, lines, pos):
1025
        key = None
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
1026
        first_key = None
2890.2.17 by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing.
1027
        trailers = 0
1028
        nodes = []
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
1029
        for line in lines:
1030
            if line == '':
1031
                # must be at the end
2890.2.17 by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing.
1032
                if self._size:
3376.2.4 by Martin Pool
Remove every assert statement from bzrlib!
1033
                    if not (self._size == pos + 1):
1034
                        raise AssertionError("%s %s" % (self._size, pos))
2890.2.17 by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing.
1035
                trailers += 1
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
1036
                continue
1037
            elements = line.split('\0')
1038
            if len(elements) != self._expected_elements:
1039
                raise errors.BadIndexData(self)
3530.3.3 by Robert Collins
Credit and explanation for interning.
1040
            # keys are tuples. Each element is a string that may occur many
1041
            # times, so we intern them to save space. AB, RC, 200807
3711.3.13 by John Arbash Meinel
Shave off another 5s by not building 'node_by_key'
1042
            key = tuple([intern(element) for element in elements[:self._key_length]])
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
1043
            if first_key is None:
1044
                first_key = key
1045
            absent, references, value = elements[-3:]
1046
            ref_lists = []
1047
            for ref_string in references.split('\t'):
1048
                ref_lists.append(tuple([
1049
                    int(ref) for ref in ref_string.split('\r') if ref
1050
                    ]))
1051
            ref_lists = tuple(ref_lists)
1052
            self._keys_by_offset[pos] = (key, absent, ref_lists, value)
1053
            pos += len(line) + 1 # +1 for the \n
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
1054
            if absent:
1055
                continue
1056
            if self.node_ref_lists:
1057
                node_value = (value, ref_lists)
1058
            else:
1059
                node_value = value
2890.2.17 by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing.
1060
            nodes.append((key, node_value))
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
1061
            # print "parsed ", key
2890.2.17 by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing.
1062
        return first_key, key, nodes, trailers
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
1063
1064
    def _parsed_bytes(self, start, start_key, end, end_key):
1065
        """Mark the bytes from start to end as parsed.
1066
1067
        Calling self._parsed_bytes(1,2) will mark one byte (the one at offset
1068
        1) as parsed.
1069
1070
        :param start: The start of the parsed region.
1071
        :param end: The end of the parsed region.
1072
        """
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
1073
        index = self._parsed_byte_index(start)
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
1074
        new_value = (start, end)
1075
        new_key = (start_key, end_key)
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
1076
        if index == -1:
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
1077
            # first range parsed is always the beginning.
1078
            self._parsed_byte_map.insert(index, new_value)
1079
            self._parsed_key_map.insert(index, new_key)
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
1080
            return
1081
        # four cases:
1082
        # new region
1083
        # extend lower region
1084
        # extend higher region
1085
        # combine two regions
1086
        if (index + 1 < len(self._parsed_byte_map) and
1087
            self._parsed_byte_map[index][1] == start and
1088
            self._parsed_byte_map[index + 1][0] == end):
1089
            # combine two regions
1090
            self._parsed_byte_map[index] = (self._parsed_byte_map[index][0],
1091
                self._parsed_byte_map[index + 1][1])
1092
            self._parsed_key_map[index] = (self._parsed_key_map[index][0],
1093
                self._parsed_key_map[index + 1][1])
2890.2.12 by Robert Collins
More index tweaks.
1094
            del self._parsed_byte_map[index + 1]
1095
            del self._parsed_key_map[index + 1]
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
1096
        elif self._parsed_byte_map[index][1] == start:
1097
            # extend the lower entry
1098
            self._parsed_byte_map[index] = (
1099
                self._parsed_byte_map[index][0], end)
1100
            self._parsed_key_map[index] = (
1101
                self._parsed_key_map[index][0], end_key)
1102
        elif (index + 1 < len(self._parsed_byte_map) and
1103
            self._parsed_byte_map[index + 1][0] == end):
1104
            # extend the higher entry
1105
            self._parsed_byte_map[index + 1] = (
1106
                start, self._parsed_byte_map[index + 1][1])
1107
            self._parsed_key_map[index + 1] = (
1108
                start_key, self._parsed_key_map[index + 1][1])
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
1109
        else:
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
1110
            # new entry
1111
            self._parsed_byte_map.insert(index + 1, new_value)
1112
            self._parsed_key_map.insert(index + 1, new_key)
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
1113
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
1114
    def _read_and_parse(self, readv_ranges):
1115
        """Read the the ranges and parse the resulting data.
1116
1117
        :param readv_ranges: A prepared readv range list.
1118
        """
3665.3.5 by John Arbash Meinel
Move the point at which we 'buffer_all' if we've read >50% of the index.
1119
        if not readv_ranges:
1120
            return
1121
        if self._nodes is None and self._bytes_read * 2 >= self._size:
1122
            # We've already read more than 50% of the file and we are about to
1123
            # request more data, just _buffer_all() and be done
1124
            self._buffer_all()
1125
            return
1126
1127
        readv_data = self._transport.readv(self._name, readv_ranges, True,
1128
            self._size)
1129
        # parse
1130
        for offset, data in readv_data:
1131
            self._bytes_read += len(data)
1132
            if offset == 0 and len(data) == self._size:
1133
                # We read the whole range, most likely because the
1134
                # Transport upcast our readv ranges into one long request
1135
                # for enough total data to grab the whole index.
1136
                self._buffer_all(StringIO(data))
1137
                return
1138
            if self._bisect_nodes is None:
1139
                # this must be the start
1140
                if not (offset == 0):
1141
                    raise AssertionError()
1142
                offset, data = self._parse_header_from_bytes(data)
1143
            # print readv_ranges, "[%d:%d]" % (offset, offset + len(data))
1144
            self._parse_region(offset, data)
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
1145
2592.1.8 by Robert Collins
Empty files should validate ok.
1146
    def _signature(self):
1147
        """The file signature for this index type."""
1148
        return _SIGNATURE
1149
2592.1.7 by Robert Collins
A validate that goes boom.
1150
    def validate(self):
1151
        """Validate that everything in the index can be accessed."""
2592.1.27 by Robert Collins
Test missing end lines with non-empty indices.
1152
        # iter_all validates completely at the moment, so just do that.
1153
        for node in self.iter_all_entries():
1154
            pass
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1155
1156
1157
class CombinedGraphIndex(object):
1158
    """A GraphIndex made up from smaller GraphIndices.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1159
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1160
    The backing indices must implement GraphIndex, and are presumed to be
1161
    static data.
2592.1.45 by Robert Collins
Tweak documentation as per Aaron's review.
1162
1163
    Queries against the combined index will be made against the first index,
1164
    and then the second and so on. The order of index's can thus influence
1165
    performance significantly. For example, if one index is on local disk and a
1166
    second on a remote server, the local disk index should be before the other
1167
    in the index list.
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1168
    """
1169
3789.1.3 by John Arbash Meinel
CombinedGraphIndex can now reload when calling key_count().
1170
    def __init__(self, indices, reload_func=None):
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1171
        """Create a CombinedGraphIndex backed by indices.
1172
2592.1.45 by Robert Collins
Tweak documentation as per Aaron's review.
1173
        :param indices: An ordered list of indices to query for data.
3789.1.3 by John Arbash Meinel
CombinedGraphIndex can now reload when calling key_count().
1174
        :param reload_func: A function to call if we find we are missing an
1175
            index. Should have the form reload_func() => True/False to indicate
1176
            if reloading actually changed anything.
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1177
        """
1178
        self._indices = indices
3789.1.3 by John Arbash Meinel
CombinedGraphIndex can now reload when calling key_count().
1179
        self._reload_func = reload_func
2592.1.37 by Robert Collins
Add CombinedGraphIndex.insert_index.
1180
2592.5.4 by Martin Pool
Add CombinedGraphIndex repr
1181
    def __repr__(self):
1182
        return "%s(%s)" % (
1183
                self.__class__.__name__,
1184
                ', '.join(map(repr, self._indices)))
1185
3099.3.3 by John Arbash Meinel
Deprecate get_parents() in favor of get_parent_map()
1186
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
2979.2.2 by Robert Collins
Per-file graph heads detection during commit for pack repositories.
1187
    def get_parents(self, revision_ids):
3099.3.1 by John Arbash Meinel
Implement get_parent_map for ParentProviders
1188
        """See graph._StackedParentsProvider.get_parents.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1189
2979.2.2 by Robert Collins
Per-file graph heads detection during commit for pack repositories.
1190
        This implementation thunks the graph.Graph.get_parents api across to
1191
        GraphIndex.
1192
1193
        :param revision_ids: An iterable of graph keys for this graph.
1194
        :return: A list of parent details for each key in revision_ids.
1195
            Each parent details will be one of:
1196
             * None when the key was missing
1197
             * (NULL_REVISION,) when the key has no parents.
1198
             * (parent_key, parent_key...) otherwise.
1199
        """
3099.3.1 by John Arbash Meinel
Implement get_parent_map for ParentProviders
1200
        parent_map = self.get_parent_map(revision_ids)
1201
        return [parent_map.get(r, None) for r in revision_ids]
1202
1203
    def get_parent_map(self, keys):
1204
        """See graph._StackedParentsProvider.get_parent_map"""
1205
        search_keys = set(keys)
1206
        if NULL_REVISION in search_keys:
1207
            search_keys.discard(NULL_REVISION)
1208
            found_parents = {NULL_REVISION:[]}
1209
        else:
1210
            found_parents = {}
2979.2.2 by Robert Collins
Per-file graph heads detection during commit for pack repositories.
1211
        for index, key, value, refs in self.iter_entries(search_keys):
1212
            parents = refs[0]
1213
            if not parents:
1214
                parents = (NULL_REVISION,)
1215
            found_parents[key] = parents
3099.3.1 by John Arbash Meinel
Implement get_parent_map for ParentProviders
1216
        return found_parents
2979.2.2 by Robert Collins
Per-file graph heads detection during commit for pack repositories.
1217
3830.3.12 by Martin Pool
Review cleanups: unify has_key impls, add missing_keys(), clean up exception blocks
1218
    has_key = _has_key_from_parent_map
3830.3.9 by Martin Pool
Simplify kvf insert_record_stream; add has_key shorthand methods; update stacking effort tests
1219
2592.1.37 by Robert Collins
Add CombinedGraphIndex.insert_index.
1220
    def insert_index(self, pos, index):
1221
        """Insert a new index in the list of indices to query.
1222
1223
        :param pos: The position to insert the index.
1224
        :param index: The index to insert.
1225
        """
1226
        self._indices.insert(pos, index)
1227
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1228
    def iter_all_entries(self):
1229
        """Iterate over all keys within the index
1230
2592.1.44 by Robert Collins
Remove some unneeded index iteration by checking if we have found all keys, and grammar improvements from Aaron's review.
1231
        Duplicate keys across child indices are presumed to have the same
1232
        value and are only reported once.
1233
2592.5.1 by Martin Pool
Fix docstrings for Index.iter_entries etc
1234
        :return: An iterable of (index, key, reference_lists, value).
1235
            There is no defined order for the result iteration - it will be in
1236
            the most efficient order for the index.
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1237
        """
1238
        seen_keys = set()
3789.1.5 by John Arbash Meinel
CombinedGraphIndex.iter_all_entries() can now reload when needed.
1239
        while True:
1240
            try:
1241
                for index in self._indices:
1242
                    for node in index.iter_all_entries():
1243
                        if node[1] not in seen_keys:
1244
                            yield node
1245
                            seen_keys.add(node[1])
1246
                return
1247
            except errors.NoSuchFile:
1248
                self._reload_or_raise()
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1249
1250
    def iter_entries(self, keys):
1251
        """Iterate over keys within the index.
1252
2592.1.44 by Robert Collins
Remove some unneeded index iteration by checking if we have found all keys, and grammar improvements from Aaron's review.
1253
        Duplicate keys across child indices are presumed to have the same
1254
        value and are only reported once.
1255
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1256
        :param keys: An iterable providing the keys to be retrieved.
2592.5.1 by Martin Pool
Fix docstrings for Index.iter_entries etc
1257
        :return: An iterable of (index, key, reference_lists, value). There is no
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1258
            defined order for the result iteration - it will be in the most
1259
            efficient order for the index.
1260
        """
1261
        keys = set(keys)
3789.1.4 by John Arbash Meinel
CombinedGraphIndex.iter_entries() is now able to reload on request.
1262
        while True:
1263
            try:
1264
                for index in self._indices:
1265
                    if not keys:
1266
                        return
1267
                    for node in index.iter_entries(keys):
1268
                        keys.remove(node[1])
1269
                        yield node
2592.1.44 by Robert Collins
Remove some unneeded index iteration by checking if we have found all keys, and grammar improvements from Aaron's review.
1270
                return
3789.1.4 by John Arbash Meinel
CombinedGraphIndex.iter_entries() is now able to reload on request.
1271
            except errors.NoSuchFile:
1272
                self._reload_or_raise()
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1273
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
1274
    def iter_entries_prefix(self, keys):
1275
        """Iterate over keys within the index using prefix matching.
1276
1277
        Duplicate keys across child indices are presumed to have the same
1278
        value and are only reported once.
1279
1280
        Prefix matching is applied within the tuple of a key, not to within
1281
        the bytestring of each key element. e.g. if you have the keys ('foo',
1282
        'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
1283
        only the former key is returned.
1284
1285
        :param keys: An iterable providing the key prefixes to be retrieved.
1286
            Each key prefix takes the form of a tuple the length of a key, but
1287
            with the last N elements 'None' rather than a regular bytestring.
1288
            The first element cannot be 'None'.
1289
        :return: An iterable as per iter_all_entries, but restricted to the
1290
            keys with a matching prefix to those supplied. No additional keys
1291
            will be returned, and every match that is in the index will be
1292
            returned.
1293
        """
1294
        keys = set(keys)
1295
        if not keys:
1296
            return
1297
        seen_keys = set()
3789.1.6 by John Arbash Meinel
CombinedGraphIndex.iter_entries_prefix can now reload when needed.
1298
        while True:
1299
            try:
1300
                for index in self._indices:
1301
                    for node in index.iter_entries_prefix(keys):
1302
                        if node[1] in seen_keys:
1303
                            continue
1304
                        seen_keys.add(node[1])
1305
                        yield node
1306
                return
1307
            except errors.NoSuchFile:
1308
                self._reload_or_raise()
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
1309
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
1310
    def key_count(self):
1311
        """Return an estimate of the number of keys in this index.
3789.1.3 by John Arbash Meinel
CombinedGraphIndex can now reload when calling key_count().
1312
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
1313
        For CombinedGraphIndex this is approximated by the sum of the keys of
1314
        the child indices. As child indices may have duplicate keys this can
1315
        have a maximum error of the number of child indices * largest number of
1316
        keys in any index.
1317
        """
3789.1.4 by John Arbash Meinel
CombinedGraphIndex.iter_entries() is now able to reload on request.
1318
        while True:
3789.1.3 by John Arbash Meinel
CombinedGraphIndex can now reload when calling key_count().
1319
            try:
1320
                return sum((index.key_count() for index in self._indices), 0)
1321
            except errors.NoSuchFile:
3789.1.4 by John Arbash Meinel
CombinedGraphIndex.iter_entries() is now able to reload on request.
1322
                self._reload_or_raise()
1323
3830.3.12 by Martin Pool
Review cleanups: unify has_key impls, add missing_keys(), clean up exception blocks
1324
    missing_keys = _missing_keys_from_parent_map
1325
3789.1.4 by John Arbash Meinel
CombinedGraphIndex.iter_entries() is now able to reload on request.
1326
    def _reload_or_raise(self):
1327
        """We just got a NoSuchFile exception.
1328
1329
        Try to reload the indices, if it fails, just raise the current
1330
        exception.
1331
        """
1332
        if self._reload_func is None:
1333
            raise
1334
        exc_type, exc_value, exc_traceback = sys.exc_info()
3789.1.10 by John Arbash Meinel
Review comments from Martin.
1335
        trace.mutter('Trying to reload after getting exception: %s',
1336
                     exc_value)
3789.1.4 by John Arbash Meinel
CombinedGraphIndex.iter_entries() is now able to reload on request.
1337
        if not self._reload_func():
1338
            # We tried to reload, but nothing changed, so we fail anyway
3789.1.10 by John Arbash Meinel
Review comments from Martin.
1339
            trace.mutter('_reload_func indicated nothing has changed.'
1340
                         ' Raising original exception.')
3789.1.4 by John Arbash Meinel
CombinedGraphIndex.iter_entries() is now able to reload on request.
1341
            raise exc_type, exc_value, exc_traceback
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
1342
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1343
    def validate(self):
1344
        """Validate that everything in the index can be accessed."""
3789.1.7 by John Arbash Meinel
CombinedGraphIndex.validate() will now reload.
1345
        while True:
1346
            try:
1347
                for index in self._indices:
1348
                    index.validate()
1349
                return
1350
            except errors.NoSuchFile:
1351
                self._reload_or_raise()
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
1352
1353
1354
class InMemoryGraphIndex(GraphIndexBuilder):
1355
    """A GraphIndex which operates entirely out of memory and is mutable.
1356
1357
    This is designed to allow the accumulation of GraphIndex entries during a
1358
    single write operation, where the accumulated entries need to be immediately
1359
    available - for example via a CombinedGraphIndex.
1360
    """
1361
1362
    def add_nodes(self, nodes):
1363
        """Add nodes to the index.
1364
1365
        :param nodes: An iterable of (key, node_refs, value) entries to add.
1366
        """
2592.3.39 by Robert Collins
Fugly version to remove signatures.kndx
1367
        if self.reference_lists:
1368
            for (key, value, node_refs) in nodes:
1369
                self.add_node(key, value, node_refs)
1370
        else:
1371
            for (key, value) in nodes:
1372
                self.add_node(key, value)
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
1373
1374
    def iter_all_entries(self):
1375
        """Iterate over all keys within the index
1376
2592.5.1 by Martin Pool
Fix docstrings for Index.iter_entries etc
1377
        :return: An iterable of (index, key, reference_lists, value). There is no
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
1378
            defined order for the result iteration - it will be in the most
1379
            efficient order for the index (in this case dictionary hash order).
1380
        """
2745.1.1 by Robert Collins
Add a number of -Devil checkpoints.
1381
        if 'evil' in debug.debug_flags:
2592.3.112 by Robert Collins
Various fixups found dogfooding.
1382
            trace.mutter_callsite(3,
2745.1.2 by Robert Collins
Ensure mutter_callsite is not directly called on a lazy_load object, to make the stacklevel parameter work correctly.
1383
                "iter_all_entries scales with size of history.")
2592.1.46 by Robert Collins
Make GraphIndex accept nodes as key, value, references, so that the method
1384
        if self.reference_lists:
1385
            for key, (absent, references, value) in self._nodes.iteritems():
1386
                if not absent:
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
1387
                    yield self, key, value, references
2592.1.46 by Robert Collins
Make GraphIndex accept nodes as key, value, references, so that the method
1388
        else:
1389
            for key, (absent, references, value) in self._nodes.iteritems():
1390
                if not absent:
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
1391
                    yield self, key, value
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
1392
1393
    def iter_entries(self, keys):
1394
        """Iterate over keys within the index.
1395
1396
        :param keys: An iterable providing the keys to be retrieved.
2979.2.4 by Robert Collins
Docstring fixes from review.
1397
        :return: An iterable of (index, key, value, reference_lists). There is no
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
1398
            defined order for the result iteration - it will be in the most
1399
            efficient order for the index (keys iteration order in this case).
1400
        """
1401
        keys = set(keys)
2592.1.46 by Robert Collins
Make GraphIndex accept nodes as key, value, references, so that the method
1402
        if self.reference_lists:
2592.3.62 by Robert Collins
Performance tweak - use a set for InMemoryGraph key iteration.
1403
            for key in keys.intersection(self._keys):
2592.1.46 by Robert Collins
Make GraphIndex accept nodes as key, value, references, so that the method
1404
                node = self._nodes[key]
1405
                if not node[0]:
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
1406
                    yield self, key, node[2], node[1]
2592.1.46 by Robert Collins
Make GraphIndex accept nodes as key, value, references, so that the method
1407
        else:
2592.3.62 by Robert Collins
Performance tweak - use a set for InMemoryGraph key iteration.
1408
            for key in keys.intersection(self._keys):
2592.1.46 by Robert Collins
Make GraphIndex accept nodes as key, value, references, so that the method
1409
                node = self._nodes[key]
1410
                if not node[0]:
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
1411
                    yield self, key, node[2]
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
1412
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
1413
    def iter_entries_prefix(self, keys):
1414
        """Iterate over keys within the index using prefix matching.
1415
1416
        Prefix matching is applied within the tuple of a key, not to within
1417
        the bytestring of each key element. e.g. if you have the keys ('foo',
1418
        'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
1419
        only the former key is returned.
1420
1421
        :param keys: An iterable providing the key prefixes to be retrieved.
1422
            Each key prefix takes the form of a tuple the length of a key, but
1423
            with the last N elements 'None' rather than a regular bytestring.
1424
            The first element cannot be 'None'.
1425
        :return: An iterable as per iter_all_entries, but restricted to the
1426
            keys with a matching prefix to those supplied. No additional keys
1427
            will be returned, and every match that is in the index will be
1428
            returned.
1429
        """
1430
        # XXX: To much duplication with the GraphIndex class; consider finding
1431
        # a good place to pull out the actual common logic.
1432
        keys = set(keys)
1433
        if not keys:
1434
            return
1435
        if self._key_length == 1:
1436
            for key in keys:
1437
                # sanity check
1438
                if key[0] is None:
1439
                    raise errors.BadIndexKey(key)
1440
                if len(key) != self._key_length:
1441
                    raise errors.BadIndexKey(key)
1442
                node = self._nodes[key]
1443
                if node[0]:
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1444
                    continue
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
1445
                if self.reference_lists:
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
1446
                    yield self, key, node[2], node[1]
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
1447
                else:
2624.2.17 by Robert Collins
Review feedback.
1448
                    yield self, key, node[2]
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
1449
            return
3644.2.4 by John Arbash Meinel
Change GraphIndex to also have a _get_nodes_by_key
1450
        nodes_by_key = self._get_nodes_by_key()
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
1451
        for key in keys:
1452
            # sanity check
1453
            if key[0] is None:
1454
                raise errors.BadIndexKey(key)
1455
            if len(key) != self._key_length:
1456
                raise errors.BadIndexKey(key)
1457
            # find what it refers to:
3644.2.4 by John Arbash Meinel
Change GraphIndex to also have a _get_nodes_by_key
1458
            key_dict = nodes_by_key
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
1459
            elements = list(key)
1460
            # find the subdict to return
1461
            try:
1462
                while len(elements) and elements[0] is not None:
1463
                    key_dict = key_dict[elements[0]]
1464
                    elements.pop(0)
1465
            except KeyError:
1466
                # a non-existant lookup.
1467
                continue
1468
            if len(elements):
1469
                dicts = [key_dict]
1470
                while dicts:
1471
                    key_dict = dicts.pop(-1)
1472
                    # can't be empty or would not exist
1473
                    item, value = key_dict.iteritems().next()
1474
                    if type(value) == dict:
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1475
                        # push keys
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
1476
                        dicts.extend(key_dict.itervalues())
1477
                    else:
1478
                        # yield keys
1479
                        for value in key_dict.itervalues():
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
1480
                            yield (self, ) + value
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
1481
            else:
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
1482
                yield (self, ) + key_dict
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
1483
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
1484
    def key_count(self):
1485
        """Return an estimate of the number of keys in this index.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1486
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
1487
        For InMemoryGraphIndex the estimate is exact.
1488
        """
1489
        return len(self._keys)
1490
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
1491
    def validate(self):
1492
        """In memory index's have no known corruption at the moment."""
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1493
1494
1495
class GraphIndexPrefixAdapter(object):
1496
    """An adapter between GraphIndex with different key lengths.
1497
1498
    Queries against this will emit queries against the adapted Graph with the
1499
    prefix added, queries for all items use iter_entries_prefix. The returned
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1500
    nodes will have their keys and node references adjusted to remove the
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1501
    prefix. Finally, an add_nodes_callback can be supplied - when called the
1502
    nodes and references being added will have prefix prepended.
1503
    """
1504
2624.2.17 by Robert Collins
Review feedback.
1505
    def __init__(self, adapted, prefix, missing_key_length,
1506
        add_nodes_callback=None):
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1507
        """Construct an adapter against adapted with prefix."""
1508
        self.adapted = adapted
2624.2.19 by Robert Collins
Why we should always test before committing.
1509
        self.prefix_key = prefix + (None,)*missing_key_length
2624.2.17 by Robert Collins
Review feedback.
1510
        self.prefix = prefix
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1511
        self.prefix_len = len(prefix)
1512
        self.add_nodes_callback = add_nodes_callback
1513
2624.2.13 by Robert Collins
Implement add_node/add_nodes to the GraphIndexPrefixAdapter.
1514
    def add_nodes(self, nodes):
1515
        """Add nodes to the index.
1516
1517
        :param nodes: An iterable of (key, node_refs, value) entries to add.
1518
        """
1519
        # save nodes in case its an iterator
1520
        nodes = tuple(nodes)
1521
        translated_nodes = []
1522
        try:
2624.2.17 by Robert Collins
Review feedback.
1523
            # Add prefix_key to each reference node_refs is a tuple of tuples,
1524
            # so split it apart, and add prefix_key to the internal reference
2624.2.13 by Robert Collins
Implement add_node/add_nodes to the GraphIndexPrefixAdapter.
1525
            for (key, value, node_refs) in nodes:
1526
                adjusted_references = (
2624.2.17 by Robert Collins
Review feedback.
1527
                    tuple(tuple(self.prefix + ref_node for ref_node in ref_list)
2624.2.13 by Robert Collins
Implement add_node/add_nodes to the GraphIndexPrefixAdapter.
1528
                        for ref_list in node_refs))
2624.2.17 by Robert Collins
Review feedback.
1529
                translated_nodes.append((self.prefix + key, value,
2624.2.13 by Robert Collins
Implement add_node/add_nodes to the GraphIndexPrefixAdapter.
1530
                    adjusted_references))
1531
        except ValueError:
1532
            # XXX: TODO add an explicit interface for getting the reference list
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1533
            # status, to handle this bit of user-friendliness in the API more
2624.2.13 by Robert Collins
Implement add_node/add_nodes to the GraphIndexPrefixAdapter.
1534
            # explicitly.
1535
            for (key, value) in nodes:
2624.2.17 by Robert Collins
Review feedback.
1536
                translated_nodes.append((self.prefix + key, value))
2624.2.13 by Robert Collins
Implement add_node/add_nodes to the GraphIndexPrefixAdapter.
1537
        self.add_nodes_callback(translated_nodes)
1538
1539
    def add_node(self, key, value, references=()):
1540
        """Add a node to the index.
1541
1542
        :param key: The key. keys are non-empty tuples containing
1543
            as many whitespace-free utf8 bytestrings as the key length
1544
            defined for this index.
1545
        :param references: An iterable of iterables of keys. Each is a
1546
            reference to another key.
1547
        :param value: The value to associate with the key. It may be any
1548
            bytes as long as it does not contain \0 or \n.
1549
        """
1550
        self.add_nodes(((key, value, references), ))
1551
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1552
    def _strip_prefix(self, an_iter):
1553
        """Strip prefix data from nodes and return it."""
1554
        for node in an_iter:
1555
            # cross checks
2624.2.17 by Robert Collins
Review feedback.
1556
            if node[1][:self.prefix_len] != self.prefix:
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1557
                raise errors.BadIndexData(self)
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
1558
            for ref_list in node[3]:
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1559
                for ref_node in ref_list:
2624.2.17 by Robert Collins
Review feedback.
1560
                    if ref_node[:self.prefix_len] != self.prefix:
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1561
                        raise errors.BadIndexData(self)
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
1562
            yield node[0], node[1][self.prefix_len:], node[2], (
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1563
                tuple(tuple(ref_node[self.prefix_len:] for ref_node in ref_list)
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
1564
                for ref_list in node[3]))
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1565
1566
    def iter_all_entries(self):
1567
        """Iterate over all keys within the index
1568
1569
        iter_all_entries is implemented against the adapted index using
1570
        iter_entries_prefix.
1571
2592.5.1 by Martin Pool
Fix docstrings for Index.iter_entries etc
1572
        :return: An iterable of (index, key, reference_lists, value). There is no
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1573
            defined order for the result iteration - it will be in the most
1574
            efficient order for the index (in this case dictionary hash order).
1575
        """
2624.2.19 by Robert Collins
Why we should always test before committing.
1576
        return self._strip_prefix(self.adapted.iter_entries_prefix([self.prefix_key]))
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1577
1578
    def iter_entries(self, keys):
1579
        """Iterate over keys within the index.
1580
1581
        :param keys: An iterable providing the keys to be retrieved.
2979.2.4 by Robert Collins
Docstring fixes from review.
1582
        :return: An iterable of (index, key, value, reference_lists). There is no
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1583
            defined order for the result iteration - it will be in the most
1584
            efficient order for the index (keys iteration order in this case).
1585
        """
1586
        return self._strip_prefix(self.adapted.iter_entries(
2624.2.17 by Robert Collins
Review feedback.
1587
            self.prefix + key for key in keys))
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1588
1589
    def iter_entries_prefix(self, keys):
1590
        """Iterate over keys within the index using prefix matching.
1591
1592
        Prefix matching is applied within the tuple of a key, not to within
1593
        the bytestring of each key element. e.g. if you have the keys ('foo',
1594
        'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
1595
        only the former key is returned.
1596
1597
        :param keys: An iterable providing the key prefixes to be retrieved.
1598
            Each key prefix takes the form of a tuple the length of a key, but
1599
            with the last N elements 'None' rather than a regular bytestring.
1600
            The first element cannot be 'None'.
1601
        :return: An iterable as per iter_all_entries, but restricted to the
1602
            keys with a matching prefix to those supplied. No additional keys
1603
            will be returned, and every match that is in the index will be
1604
            returned.
1605
        """
1606
        return self._strip_prefix(self.adapted.iter_entries_prefix(
2624.2.17 by Robert Collins
Review feedback.
1607
            self.prefix + key for key in keys))
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1608
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
1609
    def key_count(self):
1610
        """Return an estimate of the number of keys in this index.
3943.8.1 by Marius Kruger
remove all trailing whitespace from bzr source
1611
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
1612
        For GraphIndexPrefixAdapter this is relatively expensive - key
1613
        iteration with the prefix is done.
1614
        """
1615
        return len(list(self.iter_all_entries()))
1616
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1617
    def validate(self):
1618
        """Call the adapted's validate."""
1619
        self.adapted.validate()