~bzr-pqm/bzr/bzr.dev

2592.1.4 by Robert Collins
Create a GraphIndexBuilder.
1
# Copyright (C) 2007 Canonical Ltd
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
2592.1.4 by Robert Collins
Create a GraphIndexBuilder.
30
2624.2.15 by Robert Collins
Add useful -Dindex flag.
31
from bzrlib.lazy_import import lazy_import
32
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.
33
from bzrlib import trace
2890.2.7 by Robert Collins
* Pack indices are now partially parsed for specific key lookup using a
34
from bzrlib.bisect_multi import bisect_multi_bytes
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.
35
from bzrlib.trace import mutter
2624.2.15 by Robert Collins
Add useful -Dindex flag.
36
""")
37
from bzrlib import debug, errors
2592.1.4 by Robert Collins
Create a GraphIndexBuilder.
38
2624.2.8 by Robert Collins
Explicitly mark the number of keys elements in use in GraphIndex files.
39
_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.
40
_OPTION_LEN = "len="
2592.1.6 by Robert Collins
Record the number of node reference lists a particular index has.
41
_OPTION_NODE_REFS = "node_ref_lists="
2592.1.4 by Robert Collins
Create a GraphIndexBuilder.
42
_SIGNATURE = "Bazaar Graph Index 1\n"
43
44
2592.1.14 by Robert Collins
Detect bad reference key values.
45
_whitespace_re = re.compile('[\t\n\x0b\x0c\r\x00 ]')
2592.1.12 by Robert Collins
Handle basic node adds.
46
_newline_null_re = re.compile('[\n\0]')
47
48
2592.1.4 by Robert Collins
Create a GraphIndexBuilder.
49
class GraphIndexBuilder(object):
2592.1.18 by Robert Collins
Add space to mark absent nodes.
50
    """A builder that can build a GraphIndex.
51
    
52
    The resulting graph has the structure:
53
    
54
    _SIGNATURE OPTIONS NODES NEWLINE
55
    _SIGNATURE     := 'Bazaar Graph Index 1' NEWLINE
56
    OPTIONS        := 'node_ref_lists=' DIGITS NEWLINE
57
    NODES          := NODE*
58
    NODE           := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
59
    KEY            := Not-whitespace-utf8
60
    ABSENT         := 'a'
2592.1.19 by Robert Collins
Node references are tab separated.
61
    REFERENCES     := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
62
    REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
63
    REFERENCE      := DIGITS  ; digits is the byte offset in the index of the
64
                              ; referenced key.
2592.1.18 by Robert Collins
Add space to mark absent nodes.
65
    VALUE          := no-newline-no-null-bytes
66
    """
2592.1.4 by Robert Collins
Create a GraphIndexBuilder.
67
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
68
    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.
69
        """Create a GraphIndex builder.
70
71
        :param reference_lists: The number of node references lists for each
72
            entry.
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
73
        :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.
74
        """
75
        self.reference_lists = reference_lists
2592.3.62 by Robert Collins
Performance tweak - use a set for InMemoryGraph key iteration.
76
        self._keys = set()
2592.1.15 by Robert Collins
Detect duplicate key insertion.
77
        self._nodes = {}
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
78
        self._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.
79
        self._key_length = key_elements
2624.2.5 by Robert Collins
Change bzrlib.index.Index keys to be 1-tuples, not strings.
80
81
    def _check_key(self, key):
82
        """Raise BadIndexKey if key is not a valid key for this index."""
83
        if type(key) != tuple:
84
            raise errors.BadIndexKey(key)
85
        if self._key_length != len(key):
86
            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.
87
        for element in key:
88
            if not element or _whitespace_re.search(element) is not None:
89
                raise errors.BadIndexKey(element)
2592.1.12 by Robert Collins
Handle basic node adds.
90
2592.1.46 by Robert Collins
Make GraphIndex accept nodes as key, value, references, so that the method
91
    def add_node(self, key, value, references=()):
2592.1.12 by Robert Collins
Handle basic node adds.
92
        """Add a node to the index.
93
2624.2.5 by Robert Collins
Change bzrlib.index.Index keys to be 1-tuples, not strings.
94
        :param key: The key. keys are non-empty tuples containing
95
            as many whitespace-free utf8 bytestrings as the key length
96
            defined for this index.
2592.1.12 by Robert Collins
Handle basic node adds.
97
        :param references: An iterable of iterables of keys. Each is a
98
            reference to another key.
99
        :param value: The value to associate with the key. It may be any
100
            bytes as long as it does not contain \0 or \n.
101
        """
2624.2.5 by Robert Collins
Change bzrlib.index.Index keys to be 1-tuples, not strings.
102
        self._check_key(key)
2592.1.12 by Robert Collins
Handle basic node adds.
103
        if _newline_null_re.search(value) is not None:
104
            raise errors.BadIndexValue(value)
2592.1.13 by Robert Collins
Handle mismatched numbers of reference lists.
105
        if len(references) != self.reference_lists:
106
            raise errors.BadIndexValue(references)
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
107
        node_refs = []
2592.1.14 by Robert Collins
Detect bad reference key values.
108
        for reference_list in references:
109
            for reference in reference_list:
2624.2.5 by Robert Collins
Change bzrlib.index.Index keys to be 1-tuples, not strings.
110
                self._check_key(reference)
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
111
                if reference not in self._nodes:
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
112
                    self._nodes[reference] = ('a', (), '')
113
            node_refs.append(tuple(reference_list))
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
114
        if key in self._nodes and self._nodes[key][0] == '':
2592.1.15 by Robert Collins
Detect duplicate key insertion.
115
            raise errors.BadIndexDuplicateKey(key, self)
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
116
        self._nodes[key] = ('', tuple(node_refs), value)
2592.3.62 by Robert Collins
Performance tweak - use a set for InMemoryGraph key iteration.
117
        self._keys.add(key)
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
118
        if self._key_length > 1:
119
            key_dict = self._nodes_by_key
120
            if self.reference_lists:
121
                key_value = key, value, tuple(node_refs)
122
            else:
123
                key_value = key, value
124
            # possibly should do this on-demand, but it seems likely it is 
125
            # always wanted
2624.2.11 by Robert Collins
Review comments.
126
            # For a key of (foo, bar, baz) create
127
            # _nodes_by_key[foo][bar][baz] = key_value
128
            for subkey in key[:-1]:
129
                key_dict = key_dict.setdefault(subkey, {})
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
130
            key_dict[key[-1]] = key_value
2592.1.6 by Robert Collins
Record the number of node reference lists a particular index has.
131
2592.1.4 by Robert Collins
Create a GraphIndexBuilder.
132
    def finish(self):
2592.1.6 by Robert Collins
Record the number of node reference lists a particular index has.
133
        lines = [_SIGNATURE]
134
        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.
135
        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.
136
        lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
2624.2.11 by Robert Collins
Review comments.
137
        prefix_length = sum(len(x) for x in lines)
2592.1.22 by Robert Collins
Node references are byte offsets.
138
        # references are byte offsets. To avoid having to do nasty
139
        # polynomial work to resolve offsets (references to later in the 
140
        # file cannot be determined until all the inbetween references have
141
        # been calculated too) we pad the offsets with 0's to make them be
142
        # of consistent length. Using binary offsets would break the trivial
143
        # file parsing.
144
        # to calculate the width of zero's needed we do three passes:
145
        # one to gather all the non-reference data and the number of references.
146
        # one to pad all the data with reference-length and determine entry
147
        # addresses.
148
        # One to serialise.
2592.1.40 by Robert Collins
Reverse index ordering - we do not have date prefixed revids.
149
        
150
        # forward sorted by key. In future we may consider topological sorting,
151
        # at the cost of table scans for direct lookup, or a second index for
152
        # direct lookup
153
        nodes = sorted(self._nodes.items())
2592.1.42 by Robert Collins
Check the index length is as expected, when we have done preprocessing.
154
        # if we do not prepass, we don't know how long it will be up front.
155
        expected_bytes = None
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
156
        # we only need to pre-pass if we have reference lists at all.
157
        if self.reference_lists:
2592.1.41 by Robert Collins
Remove duplication in the index serialisation logic with John's suggestion.
158
            key_offset_info = []
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
159
            non_ref_bytes = prefix_length
160
            total_references = 0
161
            # TODO use simple multiplication for the constants in this loop.
162
            for key, (absent, references, value) in nodes:
2592.1.41 by Robert Collins
Remove duplication in the index serialisation logic with John's suggestion.
163
                # record the offset known *so far* for this key:
164
                # the non reference bytes to date, and the total references to
165
                # date - saves reaccumulating on the second pass
166
                key_offset_info.append((key, non_ref_bytes, total_references))
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
167
                # 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.
168
                # 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.
169
                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.
170
                if self._key_length > 1:
171
                    non_ref_bytes += self._key_length - 1
2624.2.5 by Robert Collins
Change bzrlib.index.Index keys to be 1-tuples, not strings.
172
                # value is literal bytes, there are 3 null's, 1 NL.
173
                non_ref_bytes += len(value) + 3 + 1
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
174
                # one byte for absent if set.
175
                if absent:
176
                    non_ref_bytes += 1
2592.1.36 by Robert Collins
Bugfix incorrect offset generation when an absent record is before a referenced record.
177
                elif self.reference_lists:
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
178
                    # (ref_lists -1) tabs
179
                    non_ref_bytes += self.reference_lists - 1
180
                    # (ref-1 cr's per ref_list)
181
                    for ref_list in references:
182
                        # how many references across the whole file?
183
                        total_references += len(ref_list)
184
                        # accrue reference separators
185
                        if ref_list:
186
                            non_ref_bytes += len(ref_list) - 1
187
            # how many digits are needed to represent the total byte count?
188
            digits = 1
2592.1.22 by Robert Collins
Node references are byte offsets.
189
            possible_total_bytes = non_ref_bytes + total_references*digits
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
190
            while 10 ** digits < possible_total_bytes:
191
                digits += 1
192
                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.
193
            expected_bytes = possible_total_bytes + 1 # terminating newline
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
194
            # resolve key addresses.
195
            key_addresses = {}
2592.1.41 by Robert Collins
Remove duplication in the index serialisation logic with John's suggestion.
196
            for key, non_ref_bytes, total_references in key_offset_info:
197
                key_addresses[key] = non_ref_bytes + total_references*digits
2592.1.25 by Robert Collins
Fix and tune node offset calculation.
198
            # serialise
199
            format_string = '%%0%sd' % digits
200
        for key, (absent, references, value) in nodes:
2592.1.19 by Robert Collins
Node references are tab separated.
201
            flattened_references = []
202
            for ref_list in references:
2592.1.22 by Robert Collins
Node references are byte offsets.
203
                ref_addresses = []
204
                for reference in ref_list:
205
                    ref_addresses.append(format_string % key_addresses[reference])
206
                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.
207
            string_key = '\x00'.join(key)
2624.2.11 by Robert Collins
Review comments.
208
            lines.append("%s\x00%s\x00%s\x00%s\n" % (string_key, absent,
2592.1.19 by Robert Collins
Node references are tab separated.
209
                '\t'.join(flattened_references), value))
2592.1.6 by Robert Collins
Record the number of node reference lists a particular index has.
210
        lines.append('\n')
2592.1.42 by Robert Collins
Check the index length is as expected, when we have done preprocessing.
211
        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.
212
        if expected_bytes and len(result.getvalue()) != expected_bytes:
213
            raise errors.BzrError('Failed index creation. Internal error:'
214
                ' mismatched output length and expected length: %d %d' %
215
                (len(result.getvalue()), expected_bytes))
2592.1.6 by Robert Collins
Record the number of node reference lists a particular index has.
216
        return StringIO(''.join(lines))
2592.1.5 by Robert Collins
Trivial index reading.
217
218
219
class GraphIndex(object):
220
    """An index for data with embedded graphs.
2592.1.10 by Robert Collins
Make validate detect node reference parsing errors.
221
 
222
    The index maps keys to a list of key reference lists, and a value.
223
    Each node has the same number of key reference lists. Each key reference
224
    list can be empty or an arbitrary length. The value is an opaque NULL
2592.1.45 by Robert Collins
Tweak documentation as per Aaron's review.
225
    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.
226
    hidden in the interface: keys and key references are always tuples of
227
    bytestrings, never the internal representation (e.g. dictionary offsets).
2592.1.30 by Robert Collins
Absent entries are not yeilded.
228
229
    It is presumed that the index will not be mutated - it is static data.
2592.1.34 by Robert Collins
Cleanup docs.
230
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.
231
    Successive iter_all_entries calls will read the entire index each time.
232
    Additionally, iter_entries calls will read the index linearly until the
233
    desired keys are found. XXX: This must be fixed before the index is
2592.1.34 by Robert Collins
Cleanup docs.
234
    suitable for production use. :XXX
2592.1.5 by Robert Collins
Trivial index reading.
235
    """
236
2890.2.1 by Robert Collins
* ``bzrlib.index.GraphIndex`` now requires a size parameter to the
237
    def __init__(self, transport, name, size):
2592.1.5 by Robert Collins
Trivial index reading.
238
        """Open an index called name on transport.
239
240
        :param transport: A bzrlib.transport.Transport.
241
        :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
242
        :param size: The size of the index in bytes. This is used for bisection
243
            logic to perform partial index reads. While the size could be
244
            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.
245
            trip as well as requiring stat'able transports, both of which are
246
            avoided by having it supplied. If size is None, then bisection
247
            support will be disabled and accessing the index will just stream
248
            all the data.
2592.1.5 by Robert Collins
Trivial index reading.
249
        """
250
        self._transport = transport
251
        self._name = name
2890.2.16 by Robert Collins
Review feedback.
252
        # Becomes a dict of key:(value, reference-list-byte-locations) used by
253
        # 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.
254
        self._bisect_nodes = None
2890.2.16 by Robert Collins
Review feedback.
255
        # Becomes a dict of key:(value, reference-list-keys) which are ready to
256
        # 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.
257
        self._nodes = None
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
258
        # a sorted list of slice-addresses for the parsed bytes of the file.
259
        # 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.
260
        self._parsed_byte_map = []
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
261
        # a sorted list of keys matching each slice address for parsed bytes
262
        # e.g. (None, 'foo@bar') would mean that the first byte contained no
263
        # key, and the end byte of the slice is the of the data for 'foo@bar'
264
        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.
265
        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.
266
        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.
267
        self._nodes_by_key = None
2890.2.1 by Robert Collins
* ``bzrlib.index.GraphIndex`` now requires a size parameter to the
268
        self._size = size
2624.2.2 by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram.
269
2592.3.176 by Robert Collins
Various pack refactorings.
270
    def __eq__(self, other):
2592.3.215 by Robert Collins
Review feedback.
271
        """Equal when self and other were created with the same parameters."""
2592.3.176 by Robert Collins
Various pack refactorings.
272
        return (
273
            type(self) == type(other) and
274
            self._transport == other._transport and
275
            self._name == other._name and
276
            self._size == other._size)
277
278
    def __ne__(self, other):
279
        return not self.__eq__(other)
280
2624.2.2 by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram.
281
    def _buffer_all(self):
282
        """Buffer all the index data.
283
284
        Mutates self._nodes and self.keys_by_offset.
2592.1.5 by Robert Collins
Trivial index reading.
285
        """
2624.2.15 by Robert Collins
Add useful -Dindex flag.
286
        if 'index' in debug.debug_flags:
287
            mutter('Reading entire index %s', self._transport.abspath(self._name))
2592.1.27 by Robert Collins
Test missing end lines with non-empty indices.
288
        stream = self._transport.get(self._name)
289
        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.
290
        self._expected_elements = 3 + self._key_length
2592.1.27 by Robert Collins
Test missing end lines with non-empty indices.
291
        line_count = 0
2624.2.2 by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram.
292
        # raw data keyed by offset
293
        self._keys_by_offset = {}
294
        # ready-to-return key:value or key:value, node_ref_lists
295
        self._nodes = {}
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
296
        self._nodes_by_key = {}
2592.1.27 by Robert Collins
Test missing end lines with non-empty indices.
297
        trailers = 0
298
        pos = stream.tell()
2890.2.17 by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing.
299
        lines = stream.read().split('\n')
300
        del lines[-1]
301
        _, _, _, 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.
302
        for key, absent, references, value in self._keys_by_offset.itervalues():
2592.1.30 by Robert Collins
Absent entries are not yeilded.
303
            if absent:
304
                continue
2592.1.28 by Robert Collins
Basic two pass iter_all_entries.
305
            # resolve references:
306
            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.
307
                node_value = (value, self._resolve_references(references))
2592.1.28 by Robert Collins
Basic two pass iter_all_entries.
308
            else:
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
309
                node_value = value
310
            self._nodes[key] = node_value
311
            if self._key_length > 1:
312
                subkey = list(reversed(key[:-1]))
313
                key_dict = self._nodes_by_key
314
                if self.node_ref_lists:
315
                    key_value = key, node_value[0], node_value[1]
316
                else:
317
                    key_value = key, node_value
318
                # possibly should do this on-demand, but it seems likely it is 
319
                # always wanted
2624.2.11 by Robert Collins
Review comments.
320
                # For a key of (foo, bar, baz) create
321
                # _nodes_by_key[foo][bar][baz] = key_value
322
                for subkey in key[:-1]:
323
                    key_dict = key_dict.setdefault(subkey, {})
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
324
                key_dict[key[-1]] = key_value
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
325
        # cache the keys for quick set intersections
2592.3.54 by Robert Collins
Fix remaining performance discrepancy with regular repositories.
326
        self._keys = set(self._nodes)
2592.1.27 by Robert Collins
Test missing end lines with non-empty indices.
327
        if trailers != 1:
328
            # there must be one line - the empty trailer line.
329
            raise errors.BadIndexData(self)
330
2624.2.2 by Robert Collins
Temporary performance hack for GraphIndex : load the entire index once and only once into ram.
331
    def iter_all_entries(self):
332
        """Iterate over all keys within the index.
333
2592.5.1 by Martin Pool
Fix docstrings for Index.iter_entries etc
334
        :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.
335
            The former tuple is used when there are no reference lists in the
336
            index, making the API compatible with simple key:value index types.
337
            There is no defined order for the result iteration - it will be in
338
            the most efficient order for the index.
339
        """
2745.1.1 by Robert Collins
Add a number of -Devil checkpoints.
340
        if 'evil' in debug.debug_flags:
2592.3.112 by Robert Collins
Various fixups found dogfooding.
341
            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.
342
                "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.
343
        if self._nodes is None:
344
            self._buffer_all()
345
        if self.node_ref_lists:
346
            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.
347
                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.
348
        else:
349
            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.
350
                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.
351
2592.1.27 by Robert Collins
Test missing end lines with non-empty indices.
352
    def _read_prefix(self, stream):
353
        signature = stream.read(len(self._signature()))
354
        if not signature == self._signature():
355
            raise errors.BadIndexFormatSignature(self._name, GraphIndex)
356
        options_line = stream.readline()
357
        if not options_line.startswith(_OPTION_NODE_REFS):
358
            raise errors.BadIndexOptions(self)
359
        try:
360
            self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):-1])
361
        except ValueError:
362
            raise errors.BadIndexOptions(self)
2624.2.8 by Robert Collins
Explicitly mark the number of keys elements in use in GraphIndex files.
363
        options_line = stream.readline()
364
        if not options_line.startswith(_OPTION_KEY_ELEMENTS):
365
            raise errors.BadIndexOptions(self)
366
        try:
367
            self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):-1])
368
        except ValueError:
369
            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.
370
        options_line = stream.readline()
371
        if not options_line.startswith(_OPTION_LEN):
372
            raise errors.BadIndexOptions(self)
373
        try:
374
            self._key_count = int(options_line[len(_OPTION_LEN):-1])
375
        except ValueError:
376
            raise errors.BadIndexOptions(self)
2592.1.5 by Robert Collins
Trivial index reading.
377
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
378
    def _resolve_references(self, references):
2890.2.16 by Robert Collins
Review feedback.
379
        """Return the resolved key references for references.
380
        
381
        References are resolved by looking up the location of the key in the
382
        _keys_by_offset map and substituting the key name, preserving ordering.
383
384
        :param references: An iterable of iterables of key locations. e.g. 
385
            [[123, 456], [123]]
386
        :return: A tuple of tuples of keys.
387
        """
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
388
        node_refs = []
389
        for ref_list in references:
390
            node_refs.append(tuple([self._keys_by_offset[ref][0] for ref in ref_list]))
391
        return tuple(node_refs)
392
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
393
    def _find_index(self, range_map, key):
394
        """Helper for the _parsed_*_index calls.
395
396
        Given a range map - [(start, end), ...], finds the index of the range
397
        in the map for key if it is in the map, and if it is not there, the
398
        immediately preceeding range in the map.
399
        """
400
        result = bisect_right(range_map, key) - 1
401
        if result + 1 < len(range_map):
402
            # check the border condition, it may be in result + 1
403
            if range_map[result + 1][0] == key[0]:
404
                return result + 1
405
        return result
406
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
407
    def _parsed_byte_index(self, offset):
408
        """Return the index of the entry immediately before offset.
409
410
        e.g. if the parsed map has regions 0,10 and 11,12 parsed, meaning that
411
        there is one unparsed byte (the 11th, addressed as[10]). then:
412
        asking for 0 will return 0
413
        asking for 10 will return 0
414
        asking for 11 will return 1
415
        asking for 12 will return 1
416
        """
417
        key = (offset, 0)
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
418
        return self._find_index(self._parsed_byte_map, key)
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
419
420
    def _parsed_key_index(self, key):
421
        """Return the index of the entry immediately before key.
422
423
        e.g. if the parsed map has regions (None, 'a') and ('b','c') parsed,
424
        meaning that keys from None to 'a' inclusive, and 'b' to 'c' inclusive
425
        have been parsed, then:
426
        asking for '' will return 0
427
        asking for 'a' will return 0
428
        asking for 'b' will return 1
429
        asking for 'e' will return 1
430
        """
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
431
        search_key = (key, None)
432
        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.
433
434
    def _is_parsed(self, offset):
435
        """Returns True if offset has been parsed."""
436
        index = self._parsed_byte_index(offset)
437
        if index == len(self._parsed_byte_map):
438
            return offset < self._parsed_byte_map[index - 1][1]
439
        start, end = self._parsed_byte_map[index]
440
        return offset >= start and offset < end
441
2890.2.7 by Robert Collins
* Pack indices are now partially parsed for specific key lookup using a
442
    def _iter_entries_from_total_buffer(self, keys):
443
        """Iterate over keys when the entire index is parsed."""
2592.3.54 by Robert Collins
Fix remaining performance discrepancy with regular repositories.
444
        keys = keys.intersection(self._keys)
2624.2.3 by Robert Collins
Make GraphIndex.iter_entries do hash lookups rather than table scans.
445
        if self.node_ref_lists:
446
            for key in keys:
447
                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.
448
                yield self, key, value, node_refs
2624.2.3 by Robert Collins
Make GraphIndex.iter_entries do hash lookups rather than table scans.
449
        else:
450
            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.
451
                yield self, key, self._nodes[key]
2592.1.7 by Robert Collins
A validate that goes boom.
452
2890.2.7 by Robert Collins
* Pack indices are now partially parsed for specific key lookup using a
453
    def iter_entries(self, keys):
454
        """Iterate over keys within the index.
455
456
        :param keys: An iterable providing the keys to be retrieved.
457
        :return: An iterable as per iter_all_entries, but restricted to the
458
            keys supplied. No additional keys will be returned, and every
459
            key supplied that is in the index will be returned.
460
        """
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.
461
        # PERFORMANCE TODO: parse and bisect all remaining data at some
462
        # threshold of total-index processing/get calling layers that expect to
463
        # read the entire index to use the iter_all_entries  method instead.
2890.2.7 by Robert Collins
* Pack indices are now partially parsed for specific key lookup using a
464
        keys = set(keys)
465
        if not keys:
466
            return []
2890.2.8 by Robert Collins
Make the size of the index optionally None for the pack-names index.
467
        if self._size is None and self._nodes is None:
468
            self._buffer_all()
2890.2.7 by Robert Collins
* Pack indices are now partially parsed for specific key lookup using a
469
        if self._nodes is not None:
470
            return self._iter_entries_from_total_buffer(keys)
471
        else:
472
            return (result[1] for result in bisect_multi_bytes(
2890.2.18 by Robert Collins
Review feedback.
473
                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
474
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
475
    def iter_entries_prefix(self, keys):
476
        """Iterate over keys within the index using prefix matching.
477
478
        Prefix matching is applied within the tuple of a key, not to within
479
        the bytestring of each key element. e.g. if you have the keys ('foo',
480
        'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
481
        only the former key is returned.
482
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
483
        WARNING: Note that this method currently causes a full index parse
484
        unconditionally (which is reasonably appropriate as it is a means for
485
        thunking many small indices into one larger one and still supplies
486
        iter_all_entries at the thunk layer).
487
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
488
        :param keys: An iterable providing the key prefixes to be retrieved.
489
            Each key prefix takes the form of a tuple the length of a key, but
490
            with the last N elements 'None' rather than a regular bytestring.
491
            The first element cannot be 'None'.
492
        :return: An iterable as per iter_all_entries, but restricted to the
493
            keys with a matching prefix to those supplied. No additional keys
494
            will be returned, and every match that is in the index will be
495
            returned.
496
        """
497
        keys = set(keys)
498
        if not keys:
499
            return
500
        # load data - also finds key lengths
501
        if self._nodes is None:
502
            self._buffer_all()
503
        if self._key_length == 1:
504
            for key in keys:
505
                # sanity check
506
                if key[0] is None:
507
                    raise errors.BadIndexKey(key)
508
                if len(key) != self._key_length:
509
                    raise errors.BadIndexKey(key)
510
                if self.node_ref_lists:
511
                    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.
512
                    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.
513
                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.
514
                    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.
515
            return
516
        for key in keys:
517
            # sanity check
518
            if key[0] is None:
519
                raise errors.BadIndexKey(key)
520
            if len(key) != self._key_length:
521
                raise errors.BadIndexKey(key)
522
            # find what it refers to:
523
            key_dict = self._nodes_by_key
524
            elements = list(key)
2624.2.11 by Robert Collins
Review comments.
525
            # 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.
526
            try:
527
                while len(elements) and elements[0] is not None:
528
                    key_dict = key_dict[elements[0]]
529
                    elements.pop(0)
530
            except KeyError:
531
                # a non-existant lookup.
532
                continue
533
            if len(elements):
534
                dicts = [key_dict]
535
                while dicts:
536
                    key_dict = dicts.pop(-1)
537
                    # can't be empty or would not exist
538
                    item, value = key_dict.iteritems().next()
539
                    if type(value) == dict:
540
                        # push keys 
541
                        dicts.extend(key_dict.itervalues())
542
                    else:
543
                        # yield keys
544
                        for value in key_dict.itervalues():
2624.2.11 by Robert Collins
Review comments.
545
                            # each value is the key:value:node refs tuple
546
                            # 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.
547
                            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.
548
            else:
2624.2.11 by Robert Collins
Review comments.
549
                # 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.
550
                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.
551
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
552
    def key_count(self):
553
        """Return an estimate of the number of keys in this index.
554
        
555
        For GraphIndex the estimate is exact.
556
        """
557
        if self._key_count is None:
558
            # really this should just read the prefix
559
            self._buffer_all()
560
        return self._key_count
561
2890.2.18 by Robert Collins
Review feedback.
562
    def _lookup_keys_via_location(self, location_keys):
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
563
        """Public interface for implementing bisection.
564
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
565
        If _buffer_all has been called, then all the data for the index is in
566
        memory, and this method should not be called, as it uses a separate
567
        cache because it cannot pre-resolve all indices, which buffer_all does
568
        for performance.
569
2890.2.16 by Robert Collins
Review feedback.
570
        :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.
571
        :return: A list of (location_key, result) tuples as expected by
572
            bzrlib.bisect_multi.bisect_multi_bytes.
573
        """
574
        # Possible improvements:
575
        #  - only bisect lookup each key once
576
        #  - sort the keys first, and use that to reduce the bisection window
577
        # ----- 
578
        # this progresses in three parts:
579
        # read data
580
        # parse it
581
        # attempt to answer the question from the now in memory data.
582
        # build the readv request
583
        # for each location, ask for 800 bytes - much more than rows we've seen
584
        # anywhere.
585
        readv_ranges = []
586
        for location, key in location_keys:
587
            # 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).
588
            if self._bisect_nodes and key in self._bisect_nodes:
589
                # We have the key parsed.
590
                continue
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
591
            index = self._parsed_key_index(key)
592
            if (len(self._parsed_key_map) and 
593
                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).
594
                (self._parsed_key_map[index][1] >= key or
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
595
                 # end of the file has been parsed
596
                 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).
597
                # the key has been parsed, so no lookup is needed even if its
598
                # not present.
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
599
                continue
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
600
            # - if we have examined this part of the file already - yes
601
            index = self._parsed_byte_index(location)
602
            if (len(self._parsed_byte_map) and 
603
                self._parsed_byte_map[index][0] <= location and
604
                self._parsed_byte_map[index][1] > location):
605
                # the byte region has been parsed, so no read is needed.
606
                continue
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
607
            length = 800
608
            if location + length > self._size:
609
                length = self._size - location
610
            # todo, trim out parsed locations.
611
            if length > 0:
612
                readv_ranges.append((location, length))
613
        # 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.
614
        if self._bisect_nodes is None:
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
615
            readv_ranges.append((0, 200))
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
616
        self._read_and_parse(readv_ranges)
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
617
        # generate results:
618
        #  - figure out <, >, missing, present
619
        #  - result present references so we can return them.
620
        result = []
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
621
        # keys that we cannot answer until we resolve references
622
        pending_references = []
623
        pending_locations = set()
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
624
        for location, key in location_keys:
625
            # 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).
626
            if key in self._bisect_nodes:
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
627
                # 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).
628
                if self.node_ref_lists:
629
                    # the references may not have been all parsed.
630
                    value, refs = self._bisect_nodes[key]
631
                    wanted_locations = []
632
                    for ref_list in refs:
633
                        for ref in ref_list:
634
                            if ref not in self._keys_by_offset:
635
                                wanted_locations.append(ref)
636
                    if wanted_locations:
637
                        pending_locations.update(wanted_locations)
638
                        pending_references.append((location, key))
639
                        continue
640
                    result.append(((location, key), (self, key,
641
                        value, self._resolve_references(refs))))
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
642
                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).
643
                    result.append(((location, key),
644
                        (self, key, self._bisect_nodes[key])))
645
                continue
646
            else:
647
                # has the region the key should be in, been parsed?
648
                index = self._parsed_key_index(key)
649
                if (self._parsed_key_map[index][0] <= key and
650
                    (self._parsed_key_map[index][1] >= key or
651
                     # end of the file has been parsed
652
                     self._parsed_byte_map[index][1] == self._size)):
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
653
                    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).
654
                    continue
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
655
            # no, is the key above or below the probed location:
656
            # get the range of the probed & parsed location
657
            index = self._parsed_byte_index(location)
658
            # if the key is below the start of the range, its below
659
            if key < self._parsed_key_map[index][0]:
660
                direction = -1
661
            else:
662
                direction = +1
663
            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.
664
        readv_ranges = []
665
        # lookup data to resolve references
666
        for location in pending_locations:
667
            length = 800
668
            if location + length > self._size:
669
                length = self._size - location
670
            # TODO: trim out parsed locations (e.g. if the 800 is into the
2890.2.16 by Robert Collins
Review feedback.
671
            # 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.
672
            # facility)
673
            if length > 0:
674
                readv_ranges.append((location, length))
675
        self._read_and_parse(readv_ranges)
676
        for location, key in pending_references:
677
            # answer key references we had to look-up-late.
678
            index = self._parsed_key_index(key)
679
            value, refs = self._bisect_nodes[key]
680
            result.append(((location, key), (self, key,
681
                value, self._resolve_references(refs))))
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
682
        return result
683
684
    def _parse_header_from_bytes(self, bytes):
685
        """Parse the header from a region of bytes.
686
687
        :param bytes: The data to parse.
688
        :return: An offset, data tuple such as readv yields, for the unparsed
689
            data. (which may length 0).
690
        """
691
        signature = bytes[0:len(self._signature())]
692
        if not signature == self._signature():
693
            raise errors.BadIndexFormatSignature(self._name, GraphIndex)
694
        lines = bytes[len(self._signature()):].splitlines()
695
        options_line = lines[0]
696
        if not options_line.startswith(_OPTION_NODE_REFS):
697
            raise errors.BadIndexOptions(self)
698
        try:
699
            self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):])
700
        except ValueError:
701
            raise errors.BadIndexOptions(self)
702
        options_line = lines[1]
703
        if not options_line.startswith(_OPTION_KEY_ELEMENTS):
704
            raise errors.BadIndexOptions(self)
705
        try:
706
            self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):])
707
        except ValueError:
708
            raise errors.BadIndexOptions(self)
709
        options_line = lines[2]
710
        if not options_line.startswith(_OPTION_LEN):
711
            raise errors.BadIndexOptions(self)
712
        try:
713
            self._key_count = int(options_line[len(_OPTION_LEN):])
714
        except ValueError:
715
            raise errors.BadIndexOptions(self)
716
        # calculate the bytes we have processed
717
        header_end = (len(signature) + len(lines[0]) + len(lines[1]) +
718
            len(lines[2]) + 3)
719
        self._parsed_bytes(0, None, header_end, None)
720
        # setup parsing state
721
        self._expected_elements = 3 + self._key_length
722
        # raw data keyed by offset
723
        self._keys_by_offset = {}
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
724
        # keys with the value and node references
725
        self._bisect_nodes = {}
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
726
        return header_end, bytes[header_end:]
727
728
    def _parse_region(self, offset, data):
729
        """Parse node data returned from a readv operation.
730
731
        :param offset: The byte offset the data starts at.
732
        :param data: The data to parse.
733
        """
734
        # trim the data.
735
        # end first:
736
        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.
737
        high_parsed = offset
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
738
        while True:
739
            # Trivial test - if the current index's end is within the
740
            # 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.
741
            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.
742
            if end < self._parsed_byte_map[index][1]:
743
                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.
744
            # print "[%d:%d]" % (offset, end), \
745
            #     self._parsed_byte_map[index:index + 2]
746
            high_parsed, last_segment = self._parse_segment(
747
                offset, data, end, index)
748
            if last_segment:
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
749
                return
750
751
    def _parse_segment(self, offset, data, end, index):
752
        """Parse one segment of data.
753
754
        :param offset: Where 'data' begins in the file.
755
        :param data: Some data to parse a segment of.
756
        :param end: Where data ends
757
        :param index: The current index into the parsed bytes map.
758
        :return: True if the parsed segment is the last possible one in the
759
            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.
760
        :return: high_parsed_byte, last_segment.
761
            high_parsed_byte is the location of the highest parsed byte in this
762
            segment, last_segment is True if the parsed segment is the last
763
            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.
764
        """
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
765
        # default is to use all data
766
        trim_end = None
767
        # accomodate overlap with data before this.
768
        if offset < self._parsed_byte_map[index][1]:
769
            # overlaps the lower parsed region
770
            # skip the parsed data
771
            trim_start = self._parsed_byte_map[index][1] - offset
772
            # don't trim the start for \n
773
            start_adjacent = True
774
        elif offset == self._parsed_byte_map[index][1]:
775
            # abuts the lower parsed region
776
            # use all data
777
            trim_start = None
778
            # do not trim anything
779
            start_adjacent = True
780
        else:
781
            # does not overlap the lower parsed region
782
            # use all data
783
            trim_start = None
784
            # but trim the leading \n
785
            start_adjacent = False
786
        if end == self._size:
787
            # lines up to the end of all data:
788
            # use it all
789
            trim_end = None
790
            # do not strip to the last \n
791
            end_adjacent = True
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
792
            last_segment = True
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
793
        elif index + 1 == len(self._parsed_byte_map):
794
            # at the end of the parsed data
795
            # use it all
796
            trim_end = None
797
            # but strip to the last \n
798
            end_adjacent = False
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
799
            last_segment = True
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
800
        elif end == self._parsed_byte_map[index + 1][0]:
801
            # buts up against the next parsed region
802
            # use it all
803
            trim_end = None
804
            # do not strip to the last \n
805
            end_adjacent = True
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
806
            last_segment = True
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
807
        elif end > self._parsed_byte_map[index + 1][0]:
808
            # overlaps into the next parsed region
809
            # only consider the unparsed data
810
            trim_end = self._parsed_byte_map[index + 1][0] - offset
811
            # do not strip to the last \n as we know its an entire record
812
            end_adjacent = True
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
813
            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.
814
        else:
815
            # does not overlap into the next region
816
            # use it all
817
            trim_end = None
818
            # but strip to the last \n
819
            end_adjacent = False
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
820
            last_segment = True
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
821
        # now find bytes to discard if needed
822
        if not start_adjacent:
823
            # work around python bug in rfind
824
            if trim_start is None:
825
                trim_start = data.find('\n') + 1
826
            else:
827
                trim_start = data.find('\n', trim_start) + 1
828
            assert trim_start != 0, 'no \n was present'
829
            # print 'removing start', offset, trim_start, repr(data[:trim_start])
830
        if not end_adjacent:
831
            # work around python bug in rfind
832
            if trim_end is None:
833
                trim_end = data.rfind('\n') + 1
834
            else:
835
                trim_end = data.rfind('\n', None, trim_end) + 1
836
            assert trim_end != 0, 'no \n was present'
837
            # print 'removing end', offset, trim_end, repr(data[trim_end:])
838
        # adjust offset and data to the parseable data.
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
839
        trimmed_data = data[trim_start:trim_end]
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.
840
        assert trimmed_data, 'read unneeded data [%d:%d] from [%d:%d]' % (
841
            trim_start, trim_end, offset, offset + len(data))
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
842
        if trim_start:
843
            offset += trim_start
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
844
        # print "parsing", repr(trimmed_data)
2890.2.10 by Robert Collins
Add test coverage to ensure \r's are not mangled by bisection parsing.
845
        # splitlines mangles the \r delimiters.. don't use it.
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
846
        lines = trimmed_data.split('\n')
2890.2.9 by Robert Collins
Don't use splitlines for index data parsing, we embed \r.
847
        del lines[-1]
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
848
        pos = offset
2890.2.17 by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing.
849
        first_key, last_key, nodes, _ = self._parse_lines(lines, pos)
850
        for key, value in nodes:
851
            self._bisect_nodes[key] = value
852
        self._parsed_bytes(offset, first_key,
853
            offset + len(trimmed_data), last_key)
854
        return offset + len(trimmed_data), last_segment
855
856
    def _parse_lines(self, lines, pos):
857
        key = None
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
858
        first_key = None
2890.2.17 by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing.
859
        trailers = 0
860
        nodes = []
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
861
        for line in lines:
862
            if line == '':
863
                # 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.
864
                if self._size:
865
                    assert self._size == pos + 1, "%s %s" % (self._size, pos)
866
                trailers += 1
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
867
                continue
868
            elements = line.split('\0')
869
            if len(elements) != self._expected_elements:
870
                raise errors.BadIndexData(self)
871
            # keys are tuples
872
            key = tuple(elements[:self._key_length])
873
            if first_key is None:
874
                first_key = key
875
            absent, references, value = elements[-3:]
876
            ref_lists = []
877
            for ref_string in references.split('\t'):
878
                ref_lists.append(tuple([
879
                    int(ref) for ref in ref_string.split('\r') if ref
880
                    ]))
881
            ref_lists = tuple(ref_lists)
882
            self._keys_by_offset[pos] = (key, absent, ref_lists, value)
883
            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.
884
            if absent:
885
                continue
886
            if self.node_ref_lists:
887
                node_value = (value, ref_lists)
888
            else:
889
                node_value = value
2890.2.17 by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing.
890
            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.
891
            # print "parsed ", key
2890.2.17 by Robert Collins
Split _parse_segment out into a _parse_lines helper, reducing duplication with full index parsing.
892
        return first_key, key, nodes, trailers
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
893
894
    def _parsed_bytes(self, start, start_key, end, end_key):
895
        """Mark the bytes from start to end as parsed.
896
897
        Calling self._parsed_bytes(1,2) will mark one byte (the one at offset
898
        1) as parsed.
899
900
        :param start: The start of the parsed region.
901
        :param end: The end of the parsed region.
902
        """
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
903
        index = self._parsed_byte_index(start)
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
904
        new_value = (start, end)
905
        new_key = (start_key, end_key)
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
906
        if index == -1:
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
907
            # first range parsed is always the beginning.
908
            self._parsed_byte_map.insert(index, new_value)
909
            self._parsed_key_map.insert(index, new_key)
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
910
            return
911
        # four cases:
912
        # new region
913
        # extend lower region
914
        # extend higher region
915
        # combine two regions
916
        if (index + 1 < len(self._parsed_byte_map) and
917
            self._parsed_byte_map[index][1] == start and
918
            self._parsed_byte_map[index + 1][0] == end):
919
            # combine two regions
920
            self._parsed_byte_map[index] = (self._parsed_byte_map[index][0],
921
                self._parsed_byte_map[index + 1][1])
922
            self._parsed_key_map[index] = (self._parsed_key_map[index][0],
923
                self._parsed_key_map[index + 1][1])
2890.2.12 by Robert Collins
More index tweaks.
924
            del self._parsed_byte_map[index + 1]
925
            del self._parsed_key_map[index + 1]
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
926
        elif self._parsed_byte_map[index][1] == start:
927
            # extend the lower entry
928
            self._parsed_byte_map[index] = (
929
                self._parsed_byte_map[index][0], end)
930
            self._parsed_key_map[index] = (
931
                self._parsed_key_map[index][0], end_key)
932
        elif (index + 1 < len(self._parsed_byte_map) and
933
            self._parsed_byte_map[index + 1][0] == end):
934
            # extend the higher entry
935
            self._parsed_byte_map[index + 1] = (
936
                start, self._parsed_byte_map[index + 1][1])
937
            self._parsed_key_map[index + 1] = (
938
                start_key, self._parsed_key_map[index + 1][1])
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
939
        else:
2890.2.11 by Robert Collins
Bisection improvements after integrating with packs.
940
            # new entry
941
            self._parsed_byte_map.insert(index + 1, new_value)
942
            self._parsed_key_map.insert(index + 1, new_key)
2890.2.5 by Robert Collins
Create a content lookup function for bisection in GraphIndex.
943
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
944
    def _read_and_parse(self, readv_ranges):
945
        """Read the the ranges and parse the resulting data.
946
947
        :param readv_ranges: A prepared readv range list.
948
        """
949
        if readv_ranges:
950
            readv_data = self._transport.readv(self._name, readv_ranges, True,
951
                self._size)
952
            # parse
953
            for offset, data in readv_data:
954
                if self._bisect_nodes is None:
955
                    # this must be the start
956
                    assert offset == 0
957
                    offset, data = self._parse_header_from_bytes(data)
2890.2.14 by Robert Collins
Parse more than one segment of data from a single readv response if needed.
958
                # print readv_ranges, "[%d:%d]" % (offset, offset + len(data))
2890.2.6 by Robert Collins
Add support for key references to the index lookup_keys_via_location bisection interface.
959
                self._parse_region(offset, data)
960
2592.1.8 by Robert Collins
Empty files should validate ok.
961
    def _signature(self):
962
        """The file signature for this index type."""
963
        return _SIGNATURE
964
2592.1.7 by Robert Collins
A validate that goes boom.
965
    def validate(self):
966
        """Validate that everything in the index can be accessed."""
2592.1.27 by Robert Collins
Test missing end lines with non-empty indices.
967
        # iter_all validates completely at the moment, so just do that.
968
        for node in self.iter_all_entries():
969
            pass
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
970
971
972
class CombinedGraphIndex(object):
973
    """A GraphIndex made up from smaller GraphIndices.
974
    
975
    The backing indices must implement GraphIndex, and are presumed to be
976
    static data.
2592.1.45 by Robert Collins
Tweak documentation as per Aaron's review.
977
978
    Queries against the combined index will be made against the first index,
979
    and then the second and so on. The order of index's can thus influence
980
    performance significantly. For example, if one index is on local disk and a
981
    second on a remote server, the local disk index should be before the other
982
    in the index list.
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
983
    """
984
985
    def __init__(self, indices):
986
        """Create a CombinedGraphIndex backed by indices.
987
2592.1.45 by Robert Collins
Tweak documentation as per Aaron's review.
988
        :param indices: An ordered list of indices to query for data.
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
989
        """
990
        self._indices = indices
2592.1.37 by Robert Collins
Add CombinedGraphIndex.insert_index.
991
2592.5.4 by Martin Pool
Add CombinedGraphIndex repr
992
    def __repr__(self):
993
        return "%s(%s)" % (
994
                self.__class__.__name__,
995
                ', '.join(map(repr, self._indices)))
996
2592.1.37 by Robert Collins
Add CombinedGraphIndex.insert_index.
997
    def insert_index(self, pos, index):
998
        """Insert a new index in the list of indices to query.
999
1000
        :param pos: The position to insert the index.
1001
        :param index: The index to insert.
1002
        """
1003
        self._indices.insert(pos, index)
1004
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1005
    def iter_all_entries(self):
1006
        """Iterate over all keys within the index
1007
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.
1008
        Duplicate keys across child indices are presumed to have the same
1009
        value and are only reported once.
1010
2592.5.1 by Martin Pool
Fix docstrings for Index.iter_entries etc
1011
        :return: An iterable of (index, key, reference_lists, value).
1012
            There is no defined order for the result iteration - it will be in
1013
            the most efficient order for the index.
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1014
        """
1015
        seen_keys = set()
1016
        for index in self._indices:
1017
            for node in index.iter_all_entries():
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
1018
                if node[1] not in seen_keys:
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1019
                    yield node
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
1020
                    seen_keys.add(node[1])
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1021
1022
    def iter_entries(self, keys):
1023
        """Iterate over keys within the index.
1024
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.
1025
        Duplicate keys across child indices are presumed to have the same
1026
        value and are only reported once.
1027
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1028
        :param keys: An iterable providing the keys to be retrieved.
2592.5.1 by Martin Pool
Fix docstrings for Index.iter_entries etc
1029
        :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.
1030
            defined order for the result iteration - it will be in the most
1031
            efficient order for the index.
1032
        """
1033
        keys = set(keys)
2592.1.39 by Robert Collins
CombinedGraphIndex.iter_entries does not need to see all entries.
1034
        for index in self._indices:
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.
1035
            if not keys:
1036
                return
2592.1.39 by Robert Collins
CombinedGraphIndex.iter_entries does not need to see all entries.
1037
            for node in index.iter_entries(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.
1038
                keys.remove(node[1])
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1039
                yield node
1040
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
1041
    def iter_entries_prefix(self, keys):
1042
        """Iterate over keys within the index using prefix matching.
1043
1044
        Duplicate keys across child indices are presumed to have the same
1045
        value and are only reported once.
1046
1047
        Prefix matching is applied within the tuple of a key, not to within
1048
        the bytestring of each key element. e.g. if you have the keys ('foo',
1049
        'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
1050
        only the former key is returned.
1051
1052
        :param keys: An iterable providing the key prefixes to be retrieved.
1053
            Each key prefix takes the form of a tuple the length of a key, but
1054
            with the last N elements 'None' rather than a regular bytestring.
1055
            The first element cannot be 'None'.
1056
        :return: An iterable as per iter_all_entries, but restricted to the
1057
            keys with a matching prefix to those supplied. No additional keys
1058
            will be returned, and every match that is in the index will be
1059
            returned.
1060
        """
1061
        keys = set(keys)
1062
        if not keys:
1063
            return
1064
        seen_keys = set()
1065
        for index in self._indices:
1066
            for node in index.iter_entries_prefix(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.
1067
                if node[1] in seen_keys:
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
1068
                    continue
2624.2.14 by Robert Collins
Add source index to the index iteration API to allow mapping back to the origin of retrieved data.
1069
                seen_keys.add(node[1])
2624.2.9 by Robert Collins
Introduce multiple component keys, which is what is needed to combine multiple knit indices into one.
1070
                yield node
1071
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
1072
    def key_count(self):
1073
        """Return an estimate of the number of keys in this index.
1074
        
1075
        For CombinedGraphIndex this is approximated by the sum of the keys of
1076
        the child indices. As child indices may have duplicate keys this can
1077
        have a maximum error of the number of child indices * largest number of
1078
        keys in any index.
1079
        """
1080
        return sum((index.key_count() for index in self._indices), 0)
1081
2592.1.31 by Robert Collins
Build a combined graph index to use multiple indices at once.
1082
    def validate(self):
1083
        """Validate that everything in the index can be accessed."""
1084
        for index in self._indices:
1085
            index.validate()
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
1086
1087
1088
class InMemoryGraphIndex(GraphIndexBuilder):
1089
    """A GraphIndex which operates entirely out of memory and is mutable.
1090
1091
    This is designed to allow the accumulation of GraphIndex entries during a
1092
    single write operation, where the accumulated entries need to be immediately
1093
    available - for example via a CombinedGraphIndex.
1094
    """
1095
1096
    def add_nodes(self, nodes):
1097
        """Add nodes to the index.
1098
1099
        :param nodes: An iterable of (key, node_refs, value) entries to add.
1100
        """
2592.3.39 by Robert Collins
Fugly version to remove signatures.kndx
1101
        if self.reference_lists:
1102
            for (key, value, node_refs) in nodes:
1103
                self.add_node(key, value, node_refs)
1104
        else:
1105
            for (key, value) in nodes:
1106
                self.add_node(key, value)
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
1107
1108
    def iter_all_entries(self):
1109
        """Iterate over all keys within the index
1110
2592.5.1 by Martin Pool
Fix docstrings for Index.iter_entries etc
1111
        :return: An iterable of (index, key, reference_lists, value). There is no
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
1112
            defined order for the result iteration - it will be in the most
1113
            efficient order for the index (in this case dictionary hash order).
1114
        """
2745.1.1 by Robert Collins
Add a number of -Devil checkpoints.
1115
        if 'evil' in debug.debug_flags:
2592.3.112 by Robert Collins
Various fixups found dogfooding.
1116
            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.
1117
                "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
1118
        if self.reference_lists:
1119
            for key, (absent, references, value) in self._nodes.iteritems():
1120
                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.
1121
                    yield self, key, value, references
2592.1.46 by Robert Collins
Make GraphIndex accept nodes as key, value, references, so that the method
1122
        else:
1123
            for key, (absent, references, value) in self._nodes.iteritems():
1124
                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.
1125
                    yield self, key, value
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
1126
1127
    def iter_entries(self, keys):
1128
        """Iterate over keys within the index.
1129
1130
        :param keys: An iterable providing the keys to be retrieved.
2592.5.1 by Martin Pool
Fix docstrings for Index.iter_entries etc
1131
        :return: An iterable of (index, key, reference_lists, value). There is no
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
1132
            defined order for the result iteration - it will be in the most
1133
            efficient order for the index (keys iteration order in this case).
1134
        """
1135
        keys = set(keys)
2592.1.46 by Robert Collins
Make GraphIndex accept nodes as key, value, references, so that the method
1136
        if self.reference_lists:
2592.3.62 by Robert Collins
Performance tweak - use a set for InMemoryGraph key iteration.
1137
            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
1138
                node = self._nodes[key]
1139
                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.
1140
                    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
1141
        else:
2592.3.62 by Robert Collins
Performance tweak - use a set for InMemoryGraph key iteration.
1142
            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
1143
                node = self._nodes[key]
1144
                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.
1145
                    yield self, key, node[2]
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
1146
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
1147
    def iter_entries_prefix(self, keys):
1148
        """Iterate over keys within the index using prefix matching.
1149
1150
        Prefix matching is applied within the tuple of a key, not to within
1151
        the bytestring of each key element. e.g. if you have the keys ('foo',
1152
        'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
1153
        only the former key is returned.
1154
1155
        :param keys: An iterable providing the key prefixes to be retrieved.
1156
            Each key prefix takes the form of a tuple the length of a key, but
1157
            with the last N elements 'None' rather than a regular bytestring.
1158
            The first element cannot be 'None'.
1159
        :return: An iterable as per iter_all_entries, but restricted to the
1160
            keys with a matching prefix to those supplied. No additional keys
1161
            will be returned, and every match that is in the index will be
1162
            returned.
1163
        """
1164
        # XXX: To much duplication with the GraphIndex class; consider finding
1165
        # a good place to pull out the actual common logic.
1166
        keys = set(keys)
1167
        if not keys:
1168
            return
1169
        if self._key_length == 1:
1170
            for key in keys:
1171
                # sanity check
1172
                if key[0] is None:
1173
                    raise errors.BadIndexKey(key)
1174
                if len(key) != self._key_length:
1175
                    raise errors.BadIndexKey(key)
1176
                node = self._nodes[key]
1177
                if node[0]:
1178
                    continue 
1179
                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.
1180
                    yield self, key, node[2], node[1]
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
1181
                else:
2624.2.17 by Robert Collins
Review feedback.
1182
                    yield self, key, node[2]
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
1183
            return
1184
        for key in keys:
1185
            # sanity check
1186
            if key[0] is None:
1187
                raise errors.BadIndexKey(key)
1188
            if len(key) != self._key_length:
1189
                raise errors.BadIndexKey(key)
1190
            # find what it refers to:
1191
            key_dict = self._nodes_by_key
1192
            elements = list(key)
1193
            # find the subdict to return
1194
            try:
1195
                while len(elements) and elements[0] is not None:
1196
                    key_dict = key_dict[elements[0]]
1197
                    elements.pop(0)
1198
            except KeyError:
1199
                # a non-existant lookup.
1200
                continue
1201
            if len(elements):
1202
                dicts = [key_dict]
1203
                while dicts:
1204
                    key_dict = dicts.pop(-1)
1205
                    # can't be empty or would not exist
1206
                    item, value = key_dict.iteritems().next()
1207
                    if type(value) == dict:
1208
                        # push keys 
1209
                        dicts.extend(key_dict.itervalues())
1210
                    else:
1211
                        # yield keys
1212
                        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.
1213
                            yield (self, ) + value
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
1214
            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.
1215
                yield (self, ) + key_dict
2624.2.10 by Robert Collins
Also add iter_key_prefix support to InMemoryGraphIndex.
1216
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
1217
    def key_count(self):
1218
        """Return an estimate of the number of keys in this index.
1219
        
1220
        For InMemoryGraphIndex the estimate is exact.
1221
        """
1222
        return len(self._keys)
1223
2592.1.38 by Robert Collins
Create an InMemoryGraphIndex for temporary indexing.
1224
    def validate(self):
1225
        """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.
1226
1227
1228
class GraphIndexPrefixAdapter(object):
1229
    """An adapter between GraphIndex with different key lengths.
1230
1231
    Queries against this will emit queries against the adapted Graph with the
1232
    prefix added, queries for all items use iter_entries_prefix. The returned
1233
    nodes will have their keys and node references adjusted to remove the 
1234
    prefix. Finally, an add_nodes_callback can be supplied - when called the
1235
    nodes and references being added will have prefix prepended.
1236
    """
1237
2624.2.17 by Robert Collins
Review feedback.
1238
    def __init__(self, adapted, prefix, missing_key_length,
1239
        add_nodes_callback=None):
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1240
        """Construct an adapter against adapted with prefix."""
1241
        self.adapted = adapted
2624.2.19 by Robert Collins
Why we should always test before committing.
1242
        self.prefix_key = prefix + (None,)*missing_key_length
2624.2.17 by Robert Collins
Review feedback.
1243
        self.prefix = prefix
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1244
        self.prefix_len = len(prefix)
1245
        self.add_nodes_callback = add_nodes_callback
1246
2624.2.13 by Robert Collins
Implement add_node/add_nodes to the GraphIndexPrefixAdapter.
1247
    def add_nodes(self, nodes):
1248
        """Add nodes to the index.
1249
1250
        :param nodes: An iterable of (key, node_refs, value) entries to add.
1251
        """
1252
        # save nodes in case its an iterator
1253
        nodes = tuple(nodes)
1254
        translated_nodes = []
1255
        try:
2624.2.17 by Robert Collins
Review feedback.
1256
            # Add prefix_key to each reference node_refs is a tuple of tuples,
1257
            # 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.
1258
            for (key, value, node_refs) in nodes:
1259
                adjusted_references = (
2624.2.17 by Robert Collins
Review feedback.
1260
                    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.
1261
                        for ref_list in node_refs))
2624.2.17 by Robert Collins
Review feedback.
1262
                translated_nodes.append((self.prefix + key, value,
2624.2.13 by Robert Collins
Implement add_node/add_nodes to the GraphIndexPrefixAdapter.
1263
                    adjusted_references))
1264
        except ValueError:
1265
            # XXX: TODO add an explicit interface for getting the reference list
1266
            # status, to handle this bit of user-friendliness in the API more 
1267
            # explicitly.
1268
            for (key, value) in nodes:
2624.2.17 by Robert Collins
Review feedback.
1269
                translated_nodes.append((self.prefix + key, value))
2624.2.13 by Robert Collins
Implement add_node/add_nodes to the GraphIndexPrefixAdapter.
1270
        self.add_nodes_callback(translated_nodes)
1271
1272
    def add_node(self, key, value, references=()):
1273
        """Add a node to the index.
1274
1275
        :param key: The key. keys are non-empty tuples containing
1276
            as many whitespace-free utf8 bytestrings as the key length
1277
            defined for this index.
1278
        :param references: An iterable of iterables of keys. Each is a
1279
            reference to another key.
1280
        :param value: The value to associate with the key. It may be any
1281
            bytes as long as it does not contain \0 or \n.
1282
        """
1283
        self.add_nodes(((key, value, references), ))
1284
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1285
    def _strip_prefix(self, an_iter):
1286
        """Strip prefix data from nodes and return it."""
1287
        for node in an_iter:
1288
            # cross checks
2624.2.17 by Robert Collins
Review feedback.
1289
            if node[1][:self.prefix_len] != self.prefix:
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1290
                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.
1291
            for ref_list in node[3]:
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1292
                for ref_node in ref_list:
2624.2.17 by Robert Collins
Review feedback.
1293
                    if ref_node[:self.prefix_len] != self.prefix:
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1294
                        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.
1295
            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.
1296
                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.
1297
                for ref_list in node[3]))
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1298
1299
    def iter_all_entries(self):
1300
        """Iterate over all keys within the index
1301
1302
        iter_all_entries is implemented against the adapted index using
1303
        iter_entries_prefix.
1304
2592.5.1 by Martin Pool
Fix docstrings for Index.iter_entries etc
1305
        :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.
1306
            defined order for the result iteration - it will be in the most
1307
            efficient order for the index (in this case dictionary hash order).
1308
        """
2624.2.19 by Robert Collins
Why we should always test before committing.
1309
        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.
1310
1311
    def iter_entries(self, keys):
1312
        """Iterate over keys within the index.
1313
1314
        :param keys: An iterable providing the keys to be retrieved.
1315
        :return: An iterable of (key, reference_lists, value). There is no
1316
            defined order for the result iteration - it will be in the most
1317
            efficient order for the index (keys iteration order in this case).
1318
        """
1319
        return self._strip_prefix(self.adapted.iter_entries(
2624.2.17 by Robert Collins
Review feedback.
1320
            self.prefix + key for key in keys))
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1321
1322
    def iter_entries_prefix(self, keys):
1323
        """Iterate over keys within the index using prefix matching.
1324
1325
        Prefix matching is applied within the tuple of a key, not to within
1326
        the bytestring of each key element. e.g. if you have the keys ('foo',
1327
        'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
1328
        only the former key is returned.
1329
1330
        :param keys: An iterable providing the key prefixes to be retrieved.
1331
            Each key prefix takes the form of a tuple the length of a key, but
1332
            with the last N elements 'None' rather than a regular bytestring.
1333
            The first element cannot be 'None'.
1334
        :return: An iterable as per iter_all_entries, but restricted to the
1335
            keys with a matching prefix to those supplied. No additional keys
1336
            will be returned, and every match that is in the index will be
1337
            returned.
1338
        """
1339
        return self._strip_prefix(self.adapted.iter_entries_prefix(
2624.2.17 by Robert Collins
Review feedback.
1340
            self.prefix + key for key in keys))
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1341
2624.2.16 by Robert Collins
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.
1342
    def key_count(self):
1343
        """Return an estimate of the number of keys in this index.
1344
        
1345
        For GraphIndexPrefixAdapter this is relatively expensive - key
1346
        iteration with the prefix is done.
1347
        """
1348
        return len(list(self.iter_all_entries()))
1349
2624.2.12 by Robert Collins
Create an adapter between indices with differing key lengths.
1350
    def validate(self):
1351
        """Call the adapted's validate."""
1352
        self.adapted.validate()