~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Aaron Bentley
  • Date: 2007-12-12 15:17:13 UTC
  • mto: This revision was merged to the branch mainline in revision 3113.
  • Revision ID: abentley@panoramicfeedback.com-20071212151713-ox5n8rlx8m3nsspy
Add support for reconfiguring repositories into branches or trees

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
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
 
 
19
__all__ = [
 
20
    'CombinedGraphIndex',
 
21
    'GraphIndex',
 
22
    'GraphIndexBuilder',
 
23
    'GraphIndexPrefixAdapter',
 
24
    'InMemoryGraphIndex',
 
25
    ]
 
26
 
 
27
from bisect import bisect_right
 
28
from cStringIO import StringIO
 
29
import re
 
30
 
 
31
from bzrlib.lazy_import import lazy_import
 
32
lazy_import(globals(), """
 
33
from bzrlib import trace
 
34
from bzrlib.bisect_multi import bisect_multi_bytes
 
35
from bzrlib.trace import mutter
 
36
""")
 
37
from bzrlib import debug, errors
 
38
 
 
39
_HEADER_READV = (0, 200)
 
40
_OPTION_KEY_ELEMENTS = "key_elements="
 
41
_OPTION_LEN = "len="
 
42
_OPTION_NODE_REFS = "node_ref_lists="
 
43
_SIGNATURE = "Bazaar Graph Index 1\n"
 
44
 
 
45
 
 
46
_whitespace_re = re.compile('[\t\n\x0b\x0c\r\x00 ]')
 
47
_newline_null_re = re.compile('[\n\0]')
 
48
 
 
49
 
 
50
class GraphIndexBuilder(object):
 
51
    """A builder that can build a GraphIndex.
 
52
    
 
53
    The resulting graph has the structure:
 
54
    
 
55
    _SIGNATURE OPTIONS NODES NEWLINE
 
56
    _SIGNATURE     := 'Bazaar Graph Index 1' NEWLINE
 
57
    OPTIONS        := 'node_ref_lists=' DIGITS NEWLINE
 
58
    NODES          := NODE*
 
59
    NODE           := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
 
60
    KEY            := Not-whitespace-utf8
 
61
    ABSENT         := 'a'
 
62
    REFERENCES     := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
 
63
    REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
 
64
    REFERENCE      := DIGITS  ; digits is the byte offset in the index of the
 
65
                              ; referenced key.
 
66
    VALUE          := no-newline-no-null-bytes
 
67
    """
 
68
 
 
69
    def __init__(self, reference_lists=0, key_elements=1):
 
70
        """Create a GraphIndex builder.
 
71
 
 
72
        :param reference_lists: The number of node references lists for each
 
73
            entry.
 
74
        :param key_elements: The number of bytestrings in each key.
 
75
        """
 
76
        self.reference_lists = reference_lists
 
77
        self._keys = set()
 
78
        self._nodes = {}
 
79
        self._nodes_by_key = {}
 
80
        self._key_length = key_elements
 
81
 
 
82
    def _check_key(self, key):
 
83
        """Raise BadIndexKey if key is not a valid key for this index."""
 
84
        if type(key) != tuple:
 
85
            raise errors.BadIndexKey(key)
 
86
        if self._key_length != len(key):
 
87
            raise errors.BadIndexKey(key)
 
88
        for element in key:
 
89
            if not element or _whitespace_re.search(element) is not None:
 
90
                raise errors.BadIndexKey(element)
 
91
 
 
92
    def add_node(self, key, value, references=()):
 
93
        """Add a node to the index.
 
94
 
 
95
        :param key: The key. keys are non-empty tuples containing
 
96
            as many whitespace-free utf8 bytestrings as the key length
 
97
            defined for this index.
 
98
        :param references: An iterable of iterables of keys. Each is a
 
99
            reference to another key.
 
100
        :param value: The value to associate with the key. It may be any
 
101
            bytes as long as it does not contain \0 or \n.
 
102
        """
 
103
        self._check_key(key)
 
104
        if _newline_null_re.search(value) is not None:
 
105
            raise errors.BadIndexValue(value)
 
106
        if len(references) != self.reference_lists:
 
107
            raise errors.BadIndexValue(references)
 
108
        node_refs = []
 
109
        for reference_list in references:
 
110
            for reference in reference_list:
 
111
                self._check_key(reference)
 
112
                if reference not in self._nodes:
 
113
                    self._nodes[reference] = ('a', (), '')
 
114
            node_refs.append(tuple(reference_list))
 
115
        if key in self._nodes and self._nodes[key][0] == '':
 
116
            raise errors.BadIndexDuplicateKey(key, self)
 
117
        self._nodes[key] = ('', tuple(node_refs), value)
 
118
        self._keys.add(key)
 
119
        if self._key_length > 1:
 
120
            key_dict = self._nodes_by_key
 
121
            if self.reference_lists:
 
122
                key_value = key, value, tuple(node_refs)
 
123
            else:
 
124
                key_value = key, value
 
125
            # possibly should do this on-demand, but it seems likely it is 
 
126
            # always wanted
 
127
            # For a key of (foo, bar, baz) create
 
128
            # _nodes_by_key[foo][bar][baz] = key_value
 
129
            for subkey in key[:-1]:
 
130
                key_dict = key_dict.setdefault(subkey, {})
 
131
            key_dict[key[-1]] = key_value
 
132
 
 
133
    def finish(self):
 
134
        lines = [_SIGNATURE]
 
135
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
 
136
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
 
137
        lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
 
138
        prefix_length = sum(len(x) for x in lines)
 
139
        # references are byte offsets. To avoid having to do nasty
 
140
        # polynomial work to resolve offsets (references to later in the 
 
141
        # file cannot be determined until all the inbetween references have
 
142
        # been calculated too) we pad the offsets with 0's to make them be
 
143
        # of consistent length. Using binary offsets would break the trivial
 
144
        # file parsing.
 
145
        # to calculate the width of zero's needed we do three passes:
 
146
        # one to gather all the non-reference data and the number of references.
 
147
        # one to pad all the data with reference-length and determine entry
 
148
        # addresses.
 
149
        # One to serialise.
 
150
        
 
151
        # forward sorted by key. In future we may consider topological sorting,
 
152
        # at the cost of table scans for direct lookup, or a second index for
 
153
        # direct lookup
 
154
        nodes = sorted(self._nodes.items())
 
155
        # if we do not prepass, we don't know how long it will be up front.
 
156
        expected_bytes = None
 
157
        # we only need to pre-pass if we have reference lists at all.
 
158
        if self.reference_lists:
 
159
            key_offset_info = []
 
160
            non_ref_bytes = prefix_length
 
161
            total_references = 0
 
162
            # TODO use simple multiplication for the constants in this loop.
 
163
            for key, (absent, references, value) in nodes:
 
164
                # record the offset known *so far* for this key:
 
165
                # the non reference bytes to date, and the total references to
 
166
                # date - saves reaccumulating on the second pass
 
167
                key_offset_info.append((key, non_ref_bytes, total_references))
 
168
                # key is literal, value is literal, there are 3 null's, 1 NL
 
169
                # key is variable length tuple, \x00 between elements
 
170
                non_ref_bytes += sum(len(element) for element in key)
 
171
                if self._key_length > 1:
 
172
                    non_ref_bytes += self._key_length - 1
 
173
                # value is literal bytes, there are 3 null's, 1 NL.
 
174
                non_ref_bytes += len(value) + 3 + 1
 
175
                # one byte for absent if set.
 
176
                if absent:
 
177
                    non_ref_bytes += 1
 
178
                elif self.reference_lists:
 
179
                    # (ref_lists -1) tabs
 
180
                    non_ref_bytes += self.reference_lists - 1
 
181
                    # (ref-1 cr's per ref_list)
 
182
                    for ref_list in references:
 
183
                        # how many references across the whole file?
 
184
                        total_references += len(ref_list)
 
185
                        # accrue reference separators
 
186
                        if ref_list:
 
187
                            non_ref_bytes += len(ref_list) - 1
 
188
            # how many digits are needed to represent the total byte count?
 
189
            digits = 1
 
190
            possible_total_bytes = non_ref_bytes + total_references*digits
 
191
            while 10 ** digits < possible_total_bytes:
 
192
                digits += 1
 
193
                possible_total_bytes = non_ref_bytes + total_references*digits
 
194
            expected_bytes = possible_total_bytes + 1 # terminating newline
 
195
            # resolve key addresses.
 
196
            key_addresses = {}
 
197
            for key, non_ref_bytes, total_references in key_offset_info:
 
198
                key_addresses[key] = non_ref_bytes + total_references*digits
 
199
            # serialise
 
200
            format_string = '%%0%sd' % digits
 
201
        for key, (absent, references, value) in nodes:
 
202
            flattened_references = []
 
203
            for ref_list in references:
 
204
                ref_addresses = []
 
205
                for reference in ref_list:
 
206
                    ref_addresses.append(format_string % key_addresses[reference])
 
207
                flattened_references.append('\r'.join(ref_addresses))
 
208
            string_key = '\x00'.join(key)
 
209
            lines.append("%s\x00%s\x00%s\x00%s\n" % (string_key, absent,
 
210
                '\t'.join(flattened_references), value))
 
211
        lines.append('\n')
 
212
        result = StringIO(''.join(lines))
 
213
        if expected_bytes and len(result.getvalue()) != expected_bytes:
 
214
            raise errors.BzrError('Failed index creation. Internal error:'
 
215
                ' mismatched output length and expected length: %d %d' %
 
216
                (len(result.getvalue()), expected_bytes))
 
217
        return StringIO(''.join(lines))
 
218
 
 
219
 
 
220
class GraphIndex(object):
 
221
    """An index for data with embedded graphs.
 
222
 
 
223
    The index maps keys to a list of key reference lists, and a value.
 
224
    Each node has the same number of key reference lists. Each key reference
 
225
    list can be empty or an arbitrary length. The value is an opaque NULL
 
226
    terminated string without any newlines. The storage of the index is 
 
227
    hidden in the interface: keys and key references are always tuples of
 
228
    bytestrings, never the internal representation (e.g. dictionary offsets).
 
229
 
 
230
    It is presumed that the index will not be mutated - it is static data.
 
231
 
 
232
    Successive iter_all_entries calls will read the entire index each time.
 
233
    Additionally, iter_entries calls will read the index linearly until the
 
234
    desired keys are found. XXX: This must be fixed before the index is
 
235
    suitable for production use. :XXX
 
236
    """
 
237
 
 
238
    def __init__(self, transport, name, size):
 
239
        """Open an index called name on transport.
 
240
 
 
241
        :param transport: A bzrlib.transport.Transport.
 
242
        :param name: A path to provide to transport API calls.
 
243
        :param size: The size of the index in bytes. This is used for bisection
 
244
            logic to perform partial index reads. While the size could be
 
245
            obtained by statting the file this introduced an additional round
 
246
            trip as well as requiring stat'able transports, both of which are
 
247
            avoided by having it supplied. If size is None, then bisection
 
248
            support will be disabled and accessing the index will just stream
 
249
            all the data.
 
250
        """
 
251
        self._transport = transport
 
252
        self._name = name
 
253
        # Becomes a dict of key:(value, reference-list-byte-locations) used by
 
254
        # the bisection interface to store parsed but not resolved keys.
 
255
        self._bisect_nodes = None
 
256
        # Becomes a dict of key:(value, reference-list-keys) which are ready to
 
257
        # be returned directly to callers.
 
258
        self._nodes = None
 
259
        # a sorted list of slice-addresses for the parsed bytes of the file.
 
260
        # e.g. (0,1) would mean that byte 0 is parsed.
 
261
        self._parsed_byte_map = []
 
262
        # a sorted list of keys matching each slice address for parsed bytes
 
263
        # e.g. (None, 'foo@bar') would mean that the first byte contained no
 
264
        # key, and the end byte of the slice is the of the data for 'foo@bar'
 
265
        self._parsed_key_map = []
 
266
        self._key_count = None
 
267
        self._keys_by_offset = None
 
268
        self._nodes_by_key = None
 
269
        self._size = size
 
270
 
 
271
    def __eq__(self, other):
 
272
        """Equal when self and other were created with the same parameters."""
 
273
        return (
 
274
            type(self) == type(other) and
 
275
            self._transport == other._transport and
 
276
            self._name == other._name and
 
277
            self._size == other._size)
 
278
 
 
279
    def __ne__(self, other):
 
280
        return not self.__eq__(other)
 
281
 
 
282
    def _buffer_all(self):
 
283
        """Buffer all the index data.
 
284
 
 
285
        Mutates self._nodes and self.keys_by_offset.
 
286
        """
 
287
        if 'index' in debug.debug_flags:
 
288
            mutter('Reading entire index %s', self._transport.abspath(self._name))
 
289
        stream = self._transport.get(self._name)
 
290
        self._read_prefix(stream)
 
291
        self._expected_elements = 3 + self._key_length
 
292
        line_count = 0
 
293
        # raw data keyed by offset
 
294
        self._keys_by_offset = {}
 
295
        # ready-to-return key:value or key:value, node_ref_lists
 
296
        self._nodes = {}
 
297
        self._nodes_by_key = {}
 
298
        trailers = 0
 
299
        pos = stream.tell()
 
300
        lines = stream.read().split('\n')
 
301
        del lines[-1]
 
302
        _, _, _, trailers = self._parse_lines(lines, pos)
 
303
        for key, absent, references, value in self._keys_by_offset.itervalues():
 
304
            if absent:
 
305
                continue
 
306
            # resolve references:
 
307
            if self.node_ref_lists:
 
308
                node_value = (value, self._resolve_references(references))
 
309
            else:
 
310
                node_value = value
 
311
            self._nodes[key] = node_value
 
312
            if self._key_length > 1:
 
313
                subkey = list(reversed(key[:-1]))
 
314
                key_dict = self._nodes_by_key
 
315
                if self.node_ref_lists:
 
316
                    key_value = key, node_value[0], node_value[1]
 
317
                else:
 
318
                    key_value = key, node_value
 
319
                # possibly should do this on-demand, but it seems likely it is 
 
320
                # always wanted
 
321
                # For a key of (foo, bar, baz) create
 
322
                # _nodes_by_key[foo][bar][baz] = key_value
 
323
                for subkey in key[:-1]:
 
324
                    key_dict = key_dict.setdefault(subkey, {})
 
325
                key_dict[key[-1]] = key_value
 
326
        # cache the keys for quick set intersections
 
327
        self._keys = set(self._nodes)
 
328
        if trailers != 1:
 
329
            # there must be one line - the empty trailer line.
 
330
            raise errors.BadIndexData(self)
 
331
 
 
332
    def iter_all_entries(self):
 
333
        """Iterate over all keys within the index.
 
334
 
 
335
        :return: An iterable of (index, key, value) or (index, key, value, reference_lists).
 
336
            The former tuple is used when there are no reference lists in the
 
337
            index, making the API compatible with simple key:value index types.
 
338
            There is no defined order for the result iteration - it will be in
 
339
            the most efficient order for the index.
 
340
        """
 
341
        if 'evil' in debug.debug_flags:
 
342
            trace.mutter_callsite(3,
 
343
                "iter_all_entries scales with size of history.")
 
344
        if self._nodes is None:
 
345
            self._buffer_all()
 
346
        if self.node_ref_lists:
 
347
            for key, (value, node_ref_lists) in self._nodes.iteritems():
 
348
                yield self, key, value, node_ref_lists
 
349
        else:
 
350
            for key, value in self._nodes.iteritems():
 
351
                yield self, key, value
 
352
 
 
353
    def _read_prefix(self, stream):
 
354
        signature = stream.read(len(self._signature()))
 
355
        if not signature == self._signature():
 
356
            raise errors.BadIndexFormatSignature(self._name, GraphIndex)
 
357
        options_line = stream.readline()
 
358
        if not options_line.startswith(_OPTION_NODE_REFS):
 
359
            raise errors.BadIndexOptions(self)
 
360
        try:
 
361
            self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):-1])
 
362
        except ValueError:
 
363
            raise errors.BadIndexOptions(self)
 
364
        options_line = stream.readline()
 
365
        if not options_line.startswith(_OPTION_KEY_ELEMENTS):
 
366
            raise errors.BadIndexOptions(self)
 
367
        try:
 
368
            self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):-1])
 
369
        except ValueError:
 
370
            raise errors.BadIndexOptions(self)
 
371
        options_line = stream.readline()
 
372
        if not options_line.startswith(_OPTION_LEN):
 
373
            raise errors.BadIndexOptions(self)
 
374
        try:
 
375
            self._key_count = int(options_line[len(_OPTION_LEN):-1])
 
376
        except ValueError:
 
377
            raise errors.BadIndexOptions(self)
 
378
 
 
379
    def _resolve_references(self, references):
 
380
        """Return the resolved key references for references.
 
381
        
 
382
        References are resolved by looking up the location of the key in the
 
383
        _keys_by_offset map and substituting the key name, preserving ordering.
 
384
 
 
385
        :param references: An iterable of iterables of key locations. e.g. 
 
386
            [[123, 456], [123]]
 
387
        :return: A tuple of tuples of keys.
 
388
        """
 
389
        node_refs = []
 
390
        for ref_list in references:
 
391
            node_refs.append(tuple([self._keys_by_offset[ref][0] for ref in ref_list]))
 
392
        return tuple(node_refs)
 
393
 
 
394
    def _find_index(self, range_map, key):
 
395
        """Helper for the _parsed_*_index calls.
 
396
 
 
397
        Given a range map - [(start, end), ...], finds the index of the range
 
398
        in the map for key if it is in the map, and if it is not there, the
 
399
        immediately preceeding range in the map.
 
400
        """
 
401
        result = bisect_right(range_map, key) - 1
 
402
        if result + 1 < len(range_map):
 
403
            # check the border condition, it may be in result + 1
 
404
            if range_map[result + 1][0] == key[0]:
 
405
                return result + 1
 
406
        return result
 
407
 
 
408
    def _parsed_byte_index(self, offset):
 
409
        """Return the index of the entry immediately before offset.
 
410
 
 
411
        e.g. if the parsed map has regions 0,10 and 11,12 parsed, meaning that
 
412
        there is one unparsed byte (the 11th, addressed as[10]). then:
 
413
        asking for 0 will return 0
 
414
        asking for 10 will return 0
 
415
        asking for 11 will return 1
 
416
        asking for 12 will return 1
 
417
        """
 
418
        key = (offset, 0)
 
419
        return self._find_index(self._parsed_byte_map, key)
 
420
 
 
421
    def _parsed_key_index(self, key):
 
422
        """Return the index of the entry immediately before key.
 
423
 
 
424
        e.g. if the parsed map has regions (None, 'a') and ('b','c') parsed,
 
425
        meaning that keys from None to 'a' inclusive, and 'b' to 'c' inclusive
 
426
        have been parsed, then:
 
427
        asking for '' will return 0
 
428
        asking for 'a' will return 0
 
429
        asking for 'b' will return 1
 
430
        asking for 'e' will return 1
 
431
        """
 
432
        search_key = (key, None)
 
433
        return self._find_index(self._parsed_key_map, search_key)
 
434
 
 
435
    def _is_parsed(self, offset):
 
436
        """Returns True if offset has been parsed."""
 
437
        index = self._parsed_byte_index(offset)
 
438
        if index == len(self._parsed_byte_map):
 
439
            return offset < self._parsed_byte_map[index - 1][1]
 
440
        start, end = self._parsed_byte_map[index]
 
441
        return offset >= start and offset < end
 
442
 
 
443
    def _iter_entries_from_total_buffer(self, keys):
 
444
        """Iterate over keys when the entire index is parsed."""
 
445
        keys = keys.intersection(self._keys)
 
446
        if self.node_ref_lists:
 
447
            for key in keys:
 
448
                value, node_refs = self._nodes[key]
 
449
                yield self, key, value, node_refs
 
450
        else:
 
451
            for key in keys:
 
452
                yield self, key, self._nodes[key]
 
453
 
 
454
    def iter_entries(self, keys):
 
455
        """Iterate over keys within the index.
 
456
 
 
457
        :param keys: An iterable providing the keys to be retrieved.
 
458
        :return: An iterable as per iter_all_entries, but restricted to the
 
459
            keys supplied. No additional keys will be returned, and every
 
460
            key supplied that is in the index will be returned.
 
461
        """
 
462
        # PERFORMANCE TODO: parse and bisect all remaining data at some
 
463
        # threshold of total-index processing/get calling layers that expect to
 
464
        # read the entire index to use the iter_all_entries  method instead.
 
465
        keys = set(keys)
 
466
        if not keys:
 
467
            return []
 
468
        if self._size is None and self._nodes is None:
 
469
            self._buffer_all()
 
470
        if self._nodes is not None:
 
471
            return self._iter_entries_from_total_buffer(keys)
 
472
        else:
 
473
            return (result[1] for result in bisect_multi_bytes(
 
474
                self._lookup_keys_via_location, self._size, keys))
 
475
 
 
476
    def iter_entries_prefix(self, keys):
 
477
        """Iterate over keys within the index using prefix matching.
 
478
 
 
479
        Prefix matching is applied within the tuple of a key, not to within
 
480
        the bytestring of each key element. e.g. if you have the keys ('foo',
 
481
        'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
 
482
        only the former key is returned.
 
483
 
 
484
        WARNING: Note that this method currently causes a full index parse
 
485
        unconditionally (which is reasonably appropriate as it is a means for
 
486
        thunking many small indices into one larger one and still supplies
 
487
        iter_all_entries at the thunk layer).
 
488
 
 
489
        :param keys: An iterable providing the key prefixes to be retrieved.
 
490
            Each key prefix takes the form of a tuple the length of a key, but
 
491
            with the last N elements 'None' rather than a regular bytestring.
 
492
            The first element cannot be 'None'.
 
493
        :return: An iterable as per iter_all_entries, but restricted to the
 
494
            keys with a matching prefix to those supplied. No additional keys
 
495
            will be returned, and every match that is in the index will be
 
496
            returned.
 
497
        """
 
498
        keys = set(keys)
 
499
        if not keys:
 
500
            return
 
501
        # load data - also finds key lengths
 
502
        if self._nodes is None:
 
503
            self._buffer_all()
 
504
        if self._key_length == 1:
 
505
            for key in keys:
 
506
                # sanity check
 
507
                if key[0] is None:
 
508
                    raise errors.BadIndexKey(key)
 
509
                if len(key) != self._key_length:
 
510
                    raise errors.BadIndexKey(key)
 
511
                if self.node_ref_lists:
 
512
                    value, node_refs = self._nodes[key]
 
513
                    yield self, key, value, node_refs
 
514
                else:
 
515
                    yield self, key, self._nodes[key]
 
516
            return
 
517
        for key in keys:
 
518
            # sanity check
 
519
            if key[0] is None:
 
520
                raise errors.BadIndexKey(key)
 
521
            if len(key) != self._key_length:
 
522
                raise errors.BadIndexKey(key)
 
523
            # find what it refers to:
 
524
            key_dict = self._nodes_by_key
 
525
            elements = list(key)
 
526
            # find the subdict whose contents should be returned.
 
527
            try:
 
528
                while len(elements) and elements[0] is not None:
 
529
                    key_dict = key_dict[elements[0]]
 
530
                    elements.pop(0)
 
531
            except KeyError:
 
532
                # a non-existant lookup.
 
533
                continue
 
534
            if len(elements):
 
535
                dicts = [key_dict]
 
536
                while dicts:
 
537
                    key_dict = dicts.pop(-1)
 
538
                    # can't be empty or would not exist
 
539
                    item, value = key_dict.iteritems().next()
 
540
                    if type(value) == dict:
 
541
                        # push keys 
 
542
                        dicts.extend(key_dict.itervalues())
 
543
                    else:
 
544
                        # yield keys
 
545
                        for value in key_dict.itervalues():
 
546
                            # each value is the key:value:node refs tuple
 
547
                            # ready to yield.
 
548
                            yield (self, ) + value
 
549
            else:
 
550
                # the last thing looked up was a terminal element
 
551
                yield (self, ) + key_dict
 
552
 
 
553
    def key_count(self):
 
554
        """Return an estimate of the number of keys in this index.
 
555
        
 
556
        For GraphIndex the estimate is exact.
 
557
        """
 
558
        if self._key_count is None:
 
559
            self._read_and_parse([_HEADER_READV])
 
560
        return self._key_count
 
561
 
 
562
    def _lookup_keys_via_location(self, location_keys):
 
563
        """Public interface for implementing bisection.
 
564
 
 
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
 
 
570
        :param location_keys: A list of location(byte offset), key tuples.
 
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?
 
588
            if self._bisect_nodes and key in self._bisect_nodes:
 
589
                # We have the key parsed.
 
590
                continue
 
591
            index = self._parsed_key_index(key)
 
592
            if (len(self._parsed_key_map) and 
 
593
                self._parsed_key_map[index][0] <= key and
 
594
                (self._parsed_key_map[index][1] >= key or
 
595
                 # end of the file has been parsed
 
596
                 self._parsed_byte_map[index][1] == self._size)):
 
597
                # the key has been parsed, so no lookup is needed even if its
 
598
                # not present.
 
599
                continue
 
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
 
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
 
614
        if self._bisect_nodes is None:
 
615
            readv_ranges.append(_HEADER_READV)
 
616
        self._read_and_parse(readv_ranges)
 
617
        # generate results:
 
618
        #  - figure out <, >, missing, present
 
619
        #  - result present references so we can return them.
 
620
        result = []
 
621
        # keys that we cannot answer until we resolve references
 
622
        pending_references = []
 
623
        pending_locations = set()
 
624
        for location, key in location_keys:
 
625
            # can we answer from cache?
 
626
            if key in self._bisect_nodes:
 
627
                # the key has been parsed, so no lookup is needed
 
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))))
 
642
                else:
 
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)):
 
653
                    result.append(((location, key), False))
 
654
                    continue
 
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))
 
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
 
671
            # parsed region trim it, and dont use the adjust_for_latency
 
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))))
 
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 = {}
 
724
        # keys with the value and node references
 
725
        self._bisect_nodes = {}
 
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)
 
737
        high_parsed = offset
 
738
        while True:
 
739
            # Trivial test - if the current index's end is within the
 
740
            # low-matching parsed range, we're done.
 
741
            index = self._parsed_byte_index(high_parsed)
 
742
            if end < self._parsed_byte_map[index][1]:
 
743
                return
 
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:
 
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.
 
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.
 
764
        """
 
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
 
792
            last_segment = True
 
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
 
799
            last_segment = True
 
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
 
806
            last_segment = True
 
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
 
813
            last_segment = end < self._parsed_byte_map[index + 1][1]
 
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
 
820
            last_segment = True
 
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.
 
839
        trimmed_data = data[trim_start:trim_end]
 
840
        assert trimmed_data, 'read unneeded data [%d:%d] from [%d:%d]' % (
 
841
            trim_start, trim_end, offset, offset + len(data))
 
842
        if trim_start:
 
843
            offset += trim_start
 
844
        # print "parsing", repr(trimmed_data)
 
845
        # splitlines mangles the \r delimiters.. don't use it.
 
846
        lines = trimmed_data.split('\n')
 
847
        del lines[-1]
 
848
        pos = offset
 
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
 
858
        first_key = None
 
859
        trailers = 0
 
860
        nodes = []
 
861
        for line in lines:
 
862
            if line == '':
 
863
                # must be at the end
 
864
                if self._size:
 
865
                    assert self._size == pos + 1, "%s %s" % (self._size, pos)
 
866
                trailers += 1
 
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
 
884
            if absent:
 
885
                continue
 
886
            if self.node_ref_lists:
 
887
                node_value = (value, ref_lists)
 
888
            else:
 
889
                node_value = value
 
890
            nodes.append((key, node_value))
 
891
            # print "parsed ", key
 
892
        return first_key, key, nodes, trailers
 
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
        """
 
903
        index = self._parsed_byte_index(start)
 
904
        new_value = (start, end)
 
905
        new_key = (start_key, end_key)
 
906
        if index == -1:
 
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)
 
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])
 
924
            del self._parsed_byte_map[index + 1]
 
925
            del self._parsed_key_map[index + 1]
 
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])
 
939
        else:
 
940
            # new entry
 
941
            self._parsed_byte_map.insert(index + 1, new_value)
 
942
            self._parsed_key_map.insert(index + 1, new_key)
 
943
 
 
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)
 
958
                # print readv_ranges, "[%d:%d]" % (offset, offset + len(data))
 
959
                self._parse_region(offset, data)
 
960
 
 
961
    def _signature(self):
 
962
        """The file signature for this index type."""
 
963
        return _SIGNATURE
 
964
 
 
965
    def validate(self):
 
966
        """Validate that everything in the index can be accessed."""
 
967
        # iter_all validates completely at the moment, so just do that.
 
968
        for node in self.iter_all_entries():
 
969
            pass
 
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.
 
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.
 
983
    """
 
984
 
 
985
    def __init__(self, indices):
 
986
        """Create a CombinedGraphIndex backed by indices.
 
987
 
 
988
        :param indices: An ordered list of indices to query for data.
 
989
        """
 
990
        self._indices = indices
 
991
 
 
992
    def __repr__(self):
 
993
        return "%s(%s)" % (
 
994
                self.__class__.__name__,
 
995
                ', '.join(map(repr, self._indices)))
 
996
 
 
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
 
 
1005
    def iter_all_entries(self):
 
1006
        """Iterate over all keys within the index
 
1007
 
 
1008
        Duplicate keys across child indices are presumed to have the same
 
1009
        value and are only reported once.
 
1010
 
 
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.
 
1014
        """
 
1015
        seen_keys = set()
 
1016
        for index in self._indices:
 
1017
            for node in index.iter_all_entries():
 
1018
                if node[1] not in seen_keys:
 
1019
                    yield node
 
1020
                    seen_keys.add(node[1])
 
1021
 
 
1022
    def iter_entries(self, keys):
 
1023
        """Iterate over keys within the index.
 
1024
 
 
1025
        Duplicate keys across child indices are presumed to have the same
 
1026
        value and are only reported once.
 
1027
 
 
1028
        :param keys: An iterable providing the keys to be retrieved.
 
1029
        :return: An iterable of (index, key, reference_lists, value). There is no
 
1030
            defined order for the result iteration - it will be in the most
 
1031
            efficient order for the index.
 
1032
        """
 
1033
        keys = set(keys)
 
1034
        for index in self._indices:
 
1035
            if not keys:
 
1036
                return
 
1037
            for node in index.iter_entries(keys):
 
1038
                keys.remove(node[1])
 
1039
                yield node
 
1040
 
 
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):
 
1067
                if node[1] in seen_keys:
 
1068
                    continue
 
1069
                seen_keys.add(node[1])
 
1070
                yield node
 
1071
 
 
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
 
 
1082
    def validate(self):
 
1083
        """Validate that everything in the index can be accessed."""
 
1084
        for index in self._indices:
 
1085
            index.validate()
 
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
        """
 
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)
 
1107
 
 
1108
    def iter_all_entries(self):
 
1109
        """Iterate over all keys within the index
 
1110
 
 
1111
        :return: An iterable of (index, key, reference_lists, value). There is no
 
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
        """
 
1115
        if 'evil' in debug.debug_flags:
 
1116
            trace.mutter_callsite(3,
 
1117
                "iter_all_entries scales with size of history.")
 
1118
        if self.reference_lists:
 
1119
            for key, (absent, references, value) in self._nodes.iteritems():
 
1120
                if not absent:
 
1121
                    yield self, key, value, references
 
1122
        else:
 
1123
            for key, (absent, references, value) in self._nodes.iteritems():
 
1124
                if not absent:
 
1125
                    yield self, key, value
 
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.
 
1131
        :return: An iterable of (index, key, reference_lists, value). There is no
 
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)
 
1136
        if self.reference_lists:
 
1137
            for key in keys.intersection(self._keys):
 
1138
                node = self._nodes[key]
 
1139
                if not node[0]:
 
1140
                    yield self, key, node[2], node[1]
 
1141
        else:
 
1142
            for key in keys.intersection(self._keys):
 
1143
                node = self._nodes[key]
 
1144
                if not node[0]:
 
1145
                    yield self, key, node[2]
 
1146
 
 
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:
 
1180
                    yield self, key, node[2], node[1]
 
1181
                else:
 
1182
                    yield self, key, node[2]
 
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():
 
1213
                            yield (self, ) + value
 
1214
            else:
 
1215
                yield (self, ) + key_dict
 
1216
 
 
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
 
 
1224
    def validate(self):
 
1225
        """In memory index's have no known corruption at the moment."""
 
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
 
 
1238
    def __init__(self, adapted, prefix, missing_key_length,
 
1239
        add_nodes_callback=None):
 
1240
        """Construct an adapter against adapted with prefix."""
 
1241
        self.adapted = adapted
 
1242
        self.prefix_key = prefix + (None,)*missing_key_length
 
1243
        self.prefix = prefix
 
1244
        self.prefix_len = len(prefix)
 
1245
        self.add_nodes_callback = add_nodes_callback
 
1246
 
 
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:
 
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
 
1258
            for (key, value, node_refs) in nodes:
 
1259
                adjusted_references = (
 
1260
                    tuple(tuple(self.prefix + ref_node for ref_node in ref_list)
 
1261
                        for ref_list in node_refs))
 
1262
                translated_nodes.append((self.prefix + key, value,
 
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:
 
1269
                translated_nodes.append((self.prefix + key, value))
 
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
 
 
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
 
1289
            if node[1][:self.prefix_len] != self.prefix:
 
1290
                raise errors.BadIndexData(self)
 
1291
            for ref_list in node[3]:
 
1292
                for ref_node in ref_list:
 
1293
                    if ref_node[:self.prefix_len] != self.prefix:
 
1294
                        raise errors.BadIndexData(self)
 
1295
            yield node[0], node[1][self.prefix_len:], node[2], (
 
1296
                tuple(tuple(ref_node[self.prefix_len:] for ref_node in ref_list)
 
1297
                for ref_list in node[3]))
 
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
 
 
1305
        :return: An iterable of (index, key, reference_lists, value). There is no
 
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
        """
 
1309
        return self._strip_prefix(self.adapted.iter_entries_prefix([self.prefix_key]))
 
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(
 
1320
            self.prefix + key for key in keys))
 
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(
 
1340
            self.prefix + key for key in keys))
 
1341
 
 
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
 
 
1350
    def validate(self):
 
1351
        """Call the adapted's validate."""
 
1352
        self.adapted.validate()