/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Robert Collins
  • Date: 2010-05-06 11:08:10 UTC
  • mto: This revision was merged to the branch mainline in revision 5223.
  • Revision ID: robertc@robertcollins.net-20100506110810-h3j07fh5gmw54s25
Cleaner matcher matching revised unlocking protocol.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
1
 
# Copyright (C) 2007 Canonical Ltd
 
1
# Copyright (C) 2007-2010 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
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
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
"""Indexing facilities."""
18
18
 
27
27
from bisect import bisect_right
28
28
from cStringIO import StringIO
29
29
import re
 
30
import sys
30
31
 
31
32
from bzrlib.lazy_import import lazy_import
32
33
lazy_import(globals(), """
38
39
from bzrlib import (
39
40
    debug,
40
41
    errors,
41
 
    symbol_versioning,
42
42
    )
 
43
from bzrlib.static_tuple import StaticTuple
43
44
 
44
45
_HEADER_READV = (0, 200)
45
46
_OPTION_KEY_ELEMENTS = "key_elements="
52
53
_newline_null_re = re.compile('[\n\0]')
53
54
 
54
55
 
 
56
def _has_key_from_parent_map(self, key):
 
57
    """Check if this index has one key.
 
58
 
 
59
    If it's possible to check for multiple keys at once through
 
60
    calling get_parent_map that should be faster.
 
61
    """
 
62
    return (key in self.get_parent_map([key]))
 
63
 
 
64
 
 
65
def _missing_keys_from_parent_map(self, keys):
 
66
    return set(keys) - set(self.get_parent_map(keys))
 
67
 
 
68
 
55
69
class GraphIndexBuilder(object):
56
70
    """A builder that can build a GraphIndex.
57
 
    
 
71
 
58
72
    The resulting graph has the structure:
59
 
    
 
73
 
60
74
    _SIGNATURE OPTIONS NODES NEWLINE
61
75
    _SIGNATURE     := 'Bazaar Graph Index 1' NEWLINE
62
76
    OPTIONS        := 'node_ref_lists=' DIGITS NEWLINE
79
93
        :param key_elements: The number of bytestrings in each key.
80
94
        """
81
95
        self.reference_lists = reference_lists
82
 
        self._keys = set()
 
96
        # A dict of {key: (absent, ref_lists, value)}
83
97
        self._nodes = {}
84
 
        self._nodes_by_key = {}
 
98
        # Keys that are referenced but not actually present in this index
 
99
        self._absent_keys = set()
 
100
        self._nodes_by_key = None
85
101
        self._key_length = key_elements
 
102
        self._optimize_for_size = False
 
103
        self._combine_backing_indices = True
86
104
 
87
105
    def _check_key(self, key):
88
106
        """Raise BadIndexKey if key is not a valid key for this index."""
89
 
        if type(key) != tuple:
 
107
        if type(key) not in (tuple, StaticTuple):
90
108
            raise errors.BadIndexKey(key)
91
109
        if self._key_length != len(key):
92
110
            raise errors.BadIndexKey(key)
94
112
            if not element or _whitespace_re.search(element) is not None:
95
113
                raise errors.BadIndexKey(element)
96
114
 
97
 
    def add_node(self, key, value, references=()):
98
 
        """Add a node to the index.
99
 
 
100
 
        :param key: The key. keys are non-empty tuples containing
101
 
            as many whitespace-free utf8 bytestrings as the key length
102
 
            defined for this index.
103
 
        :param references: An iterable of iterables of keys. Each is a
104
 
            reference to another key.
105
 
        :param value: The value to associate with the key. It may be any
106
 
            bytes as long as it does not contain \0 or \n.
107
 
        """
 
115
    def _external_references(self):
 
116
        """Return references that are not present in this index.
 
117
        """
 
118
        keys = set()
 
119
        refs = set()
 
120
        # TODO: JAM 2008-11-21 This makes an assumption about how the reference
 
121
        #       lists are used. It is currently correct for pack-0.92 through
 
122
        #       1.9, which use the node references (3rd column) second
 
123
        #       reference list as the compression parent. Perhaps this should
 
124
        #       be moved into something higher up the stack, since it
 
125
        #       makes assumptions about how the index is used.
 
126
        if self.reference_lists > 1:
 
127
            for node in self.iter_all_entries():
 
128
                keys.add(node[1])
 
129
                refs.update(node[3][1])
 
130
            return refs - keys
 
131
        else:
 
132
            # If reference_lists == 0 there can be no external references, and
 
133
            # if reference_lists == 1, then there isn't a place to store the
 
134
            # compression parent
 
135
            return set()
 
136
 
 
137
    def _get_nodes_by_key(self):
 
138
        if self._nodes_by_key is None:
 
139
            nodes_by_key = {}
 
140
            if self.reference_lists:
 
141
                for key, (absent, references, value) in self._nodes.iteritems():
 
142
                    if absent:
 
143
                        continue
 
144
                    key_dict = nodes_by_key
 
145
                    for subkey in key[:-1]:
 
146
                        key_dict = key_dict.setdefault(subkey, {})
 
147
                    key_dict[key[-1]] = key, value, references
 
148
            else:
 
149
                for key, (absent, references, value) in self._nodes.iteritems():
 
150
                    if absent:
 
151
                        continue
 
152
                    key_dict = nodes_by_key
 
153
                    for subkey in key[:-1]:
 
154
                        key_dict = key_dict.setdefault(subkey, {})
 
155
                    key_dict[key[-1]] = key, value
 
156
            self._nodes_by_key = nodes_by_key
 
157
        return self._nodes_by_key
 
158
 
 
159
    def _update_nodes_by_key(self, key, value, node_refs):
 
160
        """Update the _nodes_by_key dict with a new key.
 
161
 
 
162
        For a key of (foo, bar, baz) create
 
163
        _nodes_by_key[foo][bar][baz] = key_value
 
164
        """
 
165
        if self._nodes_by_key is None:
 
166
            return
 
167
        key_dict = self._nodes_by_key
 
168
        if self.reference_lists:
 
169
            key_value = StaticTuple(key, value, node_refs)
 
170
        else:
 
171
            key_value = StaticTuple(key, value)
 
172
        for subkey in key[:-1]:
 
173
            key_dict = key_dict.setdefault(subkey, {})
 
174
        key_dict[key[-1]] = key_value
 
175
 
 
176
    def _check_key_ref_value(self, key, references, value):
 
177
        """Check that 'key' and 'references' are all valid.
 
178
 
 
179
        :param key: A key tuple. Must conform to the key interface (be a tuple,
 
180
            be of the right length, not have any whitespace or nulls in any key
 
181
            element.)
 
182
        :param references: An iterable of reference lists. Something like
 
183
            [[(ref, key)], [(ref, key), (other, key)]]
 
184
        :param value: The value associate with this key. Must not contain
 
185
            newlines or null characters.
 
186
        :return: (node_refs, absent_references)
 
187
            node_refs   basically a packed form of 'references' where all
 
188
                        iterables are tuples
 
189
            absent_references   reference keys that are not in self._nodes.
 
190
                                This may contain duplicates if the same key is
 
191
                                referenced in multiple lists.
 
192
        """
 
193
        as_st = StaticTuple.from_sequence
108
194
        self._check_key(key)
109
195
        if _newline_null_re.search(value) is not None:
110
196
            raise errors.BadIndexValue(value)
111
197
        if len(references) != self.reference_lists:
112
198
            raise errors.BadIndexValue(references)
113
199
        node_refs = []
 
200
        absent_references = []
114
201
        for reference_list in references:
115
202
            for reference in reference_list:
116
 
                self._check_key(reference)
 
203
                # If reference *is* in self._nodes, then we know it has already
 
204
                # been checked.
117
205
                if reference not in self._nodes:
118
 
                    self._nodes[reference] = ('a', (), '')
119
 
            node_refs.append(tuple(reference_list))
120
 
        if key in self._nodes and self._nodes[key][0] == '':
 
206
                    self._check_key(reference)
 
207
                    absent_references.append(reference)
 
208
            reference_list = as_st([as_st(ref).intern()
 
209
                                    for ref in reference_list])
 
210
            node_refs.append(reference_list)
 
211
        return as_st(node_refs), absent_references
 
212
 
 
213
    def add_node(self, key, value, references=()):
 
214
        """Add a node to the index.
 
215
 
 
216
        :param key: The key. keys are non-empty tuples containing
 
217
            as many whitespace-free utf8 bytestrings as the key length
 
218
            defined for this index.
 
219
        :param references: An iterable of iterables of keys. Each is a
 
220
            reference to another key.
 
221
        :param value: The value to associate with the key. It may be any
 
222
            bytes as long as it does not contain \0 or \n.
 
223
        """
 
224
        (node_refs,
 
225
         absent_references) = self._check_key_ref_value(key, references, value)
 
226
        if key in self._nodes and self._nodes[key][0] != 'a':
121
227
            raise errors.BadIndexDuplicateKey(key, self)
122
 
        self._nodes[key] = ('', tuple(node_refs), value)
123
 
        self._keys.add(key)
124
 
        if self._key_length > 1:
125
 
            key_dict = self._nodes_by_key
126
 
            if self.reference_lists:
127
 
                key_value = key, value, tuple(node_refs)
128
 
            else:
129
 
                key_value = key, value
130
 
            # possibly should do this on-demand, but it seems likely it is 
131
 
            # always wanted
132
 
            # For a key of (foo, bar, baz) create
133
 
            # _nodes_by_key[foo][bar][baz] = key_value
134
 
            for subkey in key[:-1]:
135
 
                key_dict = key_dict.setdefault(subkey, {})
136
 
            key_dict[key[-1]] = key_value
137
 
 
 
228
        for reference in absent_references:
 
229
            # There may be duplicates, but I don't think it is worth worrying
 
230
            # about
 
231
            self._nodes[reference] = ('a', (), '')
 
232
        self._absent_keys.update(absent_references)
 
233
        self._absent_keys.discard(key)
 
234
        self._nodes[key] = ('', node_refs, value)
 
235
        if self._nodes_by_key is not None and self._key_length > 1:
 
236
            self._update_nodes_by_key(key, value, node_refs)
 
237
 
 
238
    def clear_cache(self):
 
239
        """See GraphIndex.clear_cache()
 
240
 
 
241
        This is a no-op, but we need the api to conform to a generic 'Index'
 
242
        abstraction.
 
243
        """
 
244
        
138
245
    def finish(self):
139
246
        lines = [_SIGNATURE]
140
247
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
141
248
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
142
 
        lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
 
249
        key_count = len(self._nodes) - len(self._absent_keys)
 
250
        lines.append(_OPTION_LEN + str(key_count) + '\n')
143
251
        prefix_length = sum(len(x) for x in lines)
144
252
        # references are byte offsets. To avoid having to do nasty
145
 
        # polynomial work to resolve offsets (references to later in the 
 
253
        # polynomial work to resolve offsets (references to later in the
146
254
        # file cannot be determined until all the inbetween references have
147
255
        # been calculated too) we pad the offsets with 0's to make them be
148
256
        # of consistent length. Using binary offsets would break the trivial
152
260
        # one to pad all the data with reference-length and determine entry
153
261
        # addresses.
154
262
        # One to serialise.
155
 
        
 
263
 
156
264
        # forward sorted by key. In future we may consider topological sorting,
157
265
        # at the cost of table scans for direct lookup, or a second index for
158
266
        # direct lookup
219
327
            raise errors.BzrError('Failed index creation. Internal error:'
220
328
                ' mismatched output length and expected length: %d %d' %
221
329
                (len(result.getvalue()), expected_bytes))
222
 
        return StringIO(''.join(lines))
 
330
        return result
 
331
 
 
332
    def set_optimize(self, for_size=None, combine_backing_indices=None):
 
333
        """Change how the builder tries to optimize the result.
 
334
 
 
335
        :param for_size: Tell the builder to try and make the index as small as
 
336
            possible.
 
337
        :param combine_backing_indices: If the builder spills to disk to save
 
338
            memory, should the on-disk indices be combined. Set to True if you
 
339
            are going to be probing the index, but to False if you are not. (If
 
340
            you are not querying, then the time spent combining is wasted.)
 
341
        :return: None
 
342
        """
 
343
        # GraphIndexBuilder itself doesn't pay attention to the flag yet, but
 
344
        # other builders do.
 
345
        if for_size is not None:
 
346
            self._optimize_for_size = for_size
 
347
        if combine_backing_indices is not None:
 
348
            self._combine_backing_indices = combine_backing_indices
 
349
 
 
350
    def find_ancestry(self, keys, ref_list_num):
 
351
        """See CombinedGraphIndex.find_ancestry()"""
 
352
        pending = set(keys)
 
353
        parent_map = {}
 
354
        missing_keys = set()
 
355
        while pending:
 
356
            next_pending = set()
 
357
            for _, key, value, ref_lists in self.iter_entries(pending):
 
358
                parent_keys = ref_lists[ref_list_num]
 
359
                parent_map[key] = parent_keys
 
360
                next_pending.update([p for p in parent_keys if p not in
 
361
                                     parent_map])
 
362
                missing_keys.update(pending.difference(parent_map))
 
363
            pending = next_pending
 
364
        return parent_map, missing_keys
223
365
 
224
366
 
225
367
class GraphIndex(object):
226
368
    """An index for data with embedded graphs.
227
 
 
 
369
 
228
370
    The index maps keys to a list of key reference lists, and a value.
229
371
    Each node has the same number of key reference lists. Each key reference
230
372
    list can be empty or an arbitrary length. The value is an opaque NULL
231
 
    terminated string without any newlines. The storage of the index is 
 
373
    terminated string without any newlines. The storage of the index is
232
374
    hidden in the interface: keys and key references are always tuples of
233
375
    bytestrings, never the internal representation (e.g. dictionary offsets).
234
376
 
240
382
    suitable for production use. :XXX
241
383
    """
242
384
 
243
 
    def __init__(self, transport, name, size):
 
385
    def __init__(self, transport, name, size, unlimited_cache=False, offset=0):
244
386
        """Open an index called name on transport.
245
387
 
246
388
        :param transport: A bzrlib.transport.Transport.
252
394
            avoided by having it supplied. If size is None, then bisection
253
395
            support will be disabled and accessing the index will just stream
254
396
            all the data.
 
397
        :param offset: Instead of starting the index data at offset 0, start it
 
398
            at an arbitrary offset.
255
399
        """
256
400
        self._transport = transport
257
401
        self._name = name
272
416
        self._keys_by_offset = None
273
417
        self._nodes_by_key = None
274
418
        self._size = size
 
419
        # The number of bytes we've read so far in trying to process this file
 
420
        self._bytes_read = 0
 
421
        self._base_offset = offset
275
422
 
276
423
    def __eq__(self, other):
277
424
        """Equal when self and other were created with the same parameters."""
284
431
    def __ne__(self, other):
285
432
        return not self.__eq__(other)
286
433
 
287
 
    def _buffer_all(self):
 
434
    def __repr__(self):
 
435
        return "%s(%r)" % (self.__class__.__name__,
 
436
            self._transport.abspath(self._name))
 
437
 
 
438
    def _buffer_all(self, stream=None):
288
439
        """Buffer all the index data.
289
440
 
290
441
        Mutates self._nodes and self.keys_by_offset.
291
442
        """
 
443
        if self._nodes is not None:
 
444
            # We already did this
 
445
            return
292
446
        if 'index' in debug.debug_flags:
293
447
            mutter('Reading entire index %s', self._transport.abspath(self._name))
294
 
        stream = self._transport.get(self._name)
 
448
        if stream is None:
 
449
            stream = self._transport.get(self._name)
 
450
            if self._base_offset != 0:
 
451
                # This is wasteful, but it is better than dealing with
 
452
                # adjusting all the offsets, etc.
 
453
                stream = StringIO(stream.read()[self._base_offset:])
295
454
        self._read_prefix(stream)
296
455
        self._expected_elements = 3 + self._key_length
297
456
        line_count = 0
299
458
        self._keys_by_offset = {}
300
459
        # ready-to-return key:value or key:value, node_ref_lists
301
460
        self._nodes = {}
302
 
        self._nodes_by_key = {}
 
461
        self._nodes_by_key = None
303
462
        trailers = 0
304
463
        pos = stream.tell()
305
464
        lines = stream.read().split('\n')
 
465
        stream.close()
306
466
        del lines[-1]
307
467
        _, _, _, trailers = self._parse_lines(lines, pos)
308
468
        for key, absent, references, value in self._keys_by_offset.itervalues():
314
474
            else:
315
475
                node_value = value
316
476
            self._nodes[key] = node_value
317
 
            if self._key_length > 1:
318
 
                subkey = list(reversed(key[:-1]))
319
 
                key_dict = self._nodes_by_key
320
 
                if self.node_ref_lists:
321
 
                    key_value = key, node_value[0], node_value[1]
322
 
                else:
323
 
                    key_value = key, node_value
324
 
                # possibly should do this on-demand, but it seems likely it is 
325
 
                # always wanted
326
 
                # For a key of (foo, bar, baz) create
327
 
                # _nodes_by_key[foo][bar][baz] = key_value
328
 
                for subkey in key[:-1]:
329
 
                    key_dict = key_dict.setdefault(subkey, {})
330
 
                key_dict[key[-1]] = key_value
331
477
        # cache the keys for quick set intersections
332
 
        self._keys = set(self._nodes)
333
478
        if trailers != 1:
334
479
            # there must be one line - the empty trailer line.
335
480
            raise errors.BadIndexData(self)
336
481
 
 
482
    def clear_cache(self):
 
483
        """Clear out any cached/memoized values.
 
484
 
 
485
        This can be called at any time, but generally it is used when we have
 
486
        extracted some information, but don't expect to be requesting any more
 
487
        from this index.
 
488
        """
 
489
 
 
490
    def external_references(self, ref_list_num):
 
491
        """Return references that are not present in this index.
 
492
        """
 
493
        self._buffer_all()
 
494
        if ref_list_num + 1 > self.node_ref_lists:
 
495
            raise ValueError('No ref list %d, index has %d ref lists'
 
496
                % (ref_list_num, self.node_ref_lists))
 
497
        refs = set()
 
498
        nodes = self._nodes
 
499
        for key, (value, ref_lists) in nodes.iteritems():
 
500
            ref_list = ref_lists[ref_list_num]
 
501
            refs.update([ref for ref in ref_list if ref not in nodes])
 
502
        return refs
 
503
 
 
504
    def _get_nodes_by_key(self):
 
505
        if self._nodes_by_key is None:
 
506
            nodes_by_key = {}
 
507
            if self.node_ref_lists:
 
508
                for key, (value, references) in self._nodes.iteritems():
 
509
                    key_dict = nodes_by_key
 
510
                    for subkey in key[:-1]:
 
511
                        key_dict = key_dict.setdefault(subkey, {})
 
512
                    key_dict[key[-1]] = key, value, references
 
513
            else:
 
514
                for key, value in self._nodes.iteritems():
 
515
                    key_dict = nodes_by_key
 
516
                    for subkey in key[:-1]:
 
517
                        key_dict = key_dict.setdefault(subkey, {})
 
518
                    key_dict[key[-1]] = key, value
 
519
            self._nodes_by_key = nodes_by_key
 
520
        return self._nodes_by_key
 
521
 
337
522
    def iter_all_entries(self):
338
523
        """Iterate over all keys within the index.
339
524
 
383
568
 
384
569
    def _resolve_references(self, references):
385
570
        """Return the resolved key references for references.
386
 
        
 
571
 
387
572
        References are resolved by looking up the location of the key in the
388
573
        _keys_by_offset map and substituting the key name, preserving ordering.
389
574
 
390
 
        :param references: An iterable of iterables of key locations. e.g. 
 
575
        :param references: An iterable of iterables of key locations. e.g.
391
576
            [[123, 456], [123]]
392
577
        :return: A tuple of tuples of keys.
393
578
        """
447
632
 
448
633
    def _iter_entries_from_total_buffer(self, keys):
449
634
        """Iterate over keys when the entire index is parsed."""
450
 
        keys = keys.intersection(self._keys)
 
635
        # Note: See the note in BTreeBuilder.iter_entries for why we don't use
 
636
        #       .intersection() here
 
637
        nodes = self._nodes
 
638
        keys = [key for key in keys if key in nodes]
451
639
        if self.node_ref_lists:
452
640
            for key in keys:
453
 
                value, node_refs = self._nodes[key]
 
641
                value, node_refs = nodes[key]
454
642
                yield self, key, value, node_refs
455
643
        else:
456
644
            for key in keys:
457
 
                yield self, key, self._nodes[key]
 
645
                yield self, key, nodes[key]
458
646
 
459
647
    def iter_entries(self, keys):
460
648
        """Iterate over keys within the index.
464
652
            keys supplied. No additional keys will be returned, and every
465
653
            key supplied that is in the index will be returned.
466
654
        """
467
 
        # PERFORMANCE TODO: parse and bisect all remaining data at some
468
 
        # threshold of total-index processing/get calling layers that expect to
469
 
        # read the entire index to use the iter_all_entries  method instead.
470
655
        keys = set(keys)
471
656
        if not keys:
472
657
            return []
473
658
        if self._size is None and self._nodes is None:
474
659
            self._buffer_all()
 
660
 
 
661
        # We fit about 20 keys per minimum-read (4K), so if we are looking for
 
662
        # more than 1/20th of the index its likely (assuming homogenous key
 
663
        # spread) that we'll read the entire index. If we're going to do that,
 
664
        # buffer the whole thing. A better analysis might take key spread into
 
665
        # account - but B+Tree indices are better anyway.
 
666
        # We could look at all data read, and use a threshold there, which will
 
667
        # trigger on ancestry walks, but that is not yet fully mapped out.
 
668
        if self._nodes is None and len(keys) * 20 > self.key_count():
 
669
            self._buffer_all()
475
670
        if self._nodes is not None:
476
671
            return self._iter_entries_from_total_buffer(keys)
477
672
        else:
519
714
                else:
520
715
                    yield self, key, self._nodes[key]
521
716
            return
 
717
        nodes_by_key = self._get_nodes_by_key()
522
718
        for key in keys:
523
719
            # sanity check
524
720
            if key[0] is None:
526
722
            if len(key) != self._key_length:
527
723
                raise errors.BadIndexKey(key)
528
724
            # find what it refers to:
529
 
            key_dict = self._nodes_by_key
 
725
            key_dict = nodes_by_key
530
726
            elements = list(key)
531
727
            # find the subdict whose contents should be returned.
532
728
            try:
543
739
                    # can't be empty or would not exist
544
740
                    item, value = key_dict.iteritems().next()
545
741
                    if type(value) == dict:
546
 
                        # push keys 
 
742
                        # push keys
547
743
                        dicts.extend(key_dict.itervalues())
548
744
                    else:
549
745
                        # yield keys
555
751
                # the last thing looked up was a terminal element
556
752
                yield (self, ) + key_dict
557
753
 
 
754
    def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
 
755
        """See BTreeIndex._find_ancestors."""
 
756
        # The api can be implemented as a trivial overlay on top of
 
757
        # iter_entries, it is not an efficient implementation, but it at least
 
758
        # gets the job done.
 
759
        found_keys = set()
 
760
        search_keys = set()
 
761
        for index, key, value, refs in self.iter_entries(keys):
 
762
            parent_keys = refs[ref_list_num]
 
763
            found_keys.add(key)
 
764
            parent_map[key] = parent_keys
 
765
            search_keys.update(parent_keys)
 
766
        # Figure out what, if anything, was missing
 
767
        missing_keys.update(set(keys).difference(found_keys))
 
768
        search_keys = search_keys.difference(parent_map)
 
769
        return search_keys
 
770
 
558
771
    def key_count(self):
559
772
        """Return an estimate of the number of keys in this index.
560
 
        
 
773
 
561
774
        For GraphIndex the estimate is exact.
562
775
        """
563
776
        if self._key_count is None:
579
792
        # Possible improvements:
580
793
        #  - only bisect lookup each key once
581
794
        #  - sort the keys first, and use that to reduce the bisection window
582
 
        # ----- 
 
795
        # -----
583
796
        # this progresses in three parts:
584
797
        # read data
585
798
        # parse it
594
807
                # We have the key parsed.
595
808
                continue
596
809
            index = self._parsed_key_index(key)
597
 
            if (len(self._parsed_key_map) and 
 
810
            if (len(self._parsed_key_map) and
598
811
                self._parsed_key_map[index][0] <= key and
599
812
                (self._parsed_key_map[index][1] >= key or
600
813
                 # end of the file has been parsed
604
817
                continue
605
818
            # - if we have examined this part of the file already - yes
606
819
            index = self._parsed_byte_index(location)
607
 
            if (len(self._parsed_byte_map) and 
 
820
            if (len(self._parsed_byte_map) and
608
821
                self._parsed_byte_map[index][0] <= location and
609
822
                self._parsed_byte_map[index][1] > location):
610
823
                # the byte region has been parsed, so no read is needed.
619
832
        if self._bisect_nodes is None:
620
833
            readv_ranges.append(_HEADER_READV)
621
834
        self._read_and_parse(readv_ranges)
 
835
        result = []
 
836
        if self._nodes is not None:
 
837
            # _read_and_parse triggered a _buffer_all because we requested the
 
838
            # whole data range
 
839
            for location, key in location_keys:
 
840
                if key not in self._nodes: # not present
 
841
                    result.append(((location, key), False))
 
842
                elif self.node_ref_lists:
 
843
                    value, refs = self._nodes[key]
 
844
                    result.append(((location, key),
 
845
                        (self, key, value, refs)))
 
846
                else:
 
847
                    result.append(((location, key),
 
848
                        (self, key, self._nodes[key])))
 
849
            return result
622
850
        # generate results:
623
851
        #  - figure out <, >, missing, present
624
852
        #  - result present references so we can return them.
625
 
        result = []
626
853
        # keys that we cannot answer until we resolve references
627
854
        pending_references = []
628
855
        pending_locations = set()
678
905
            if length > 0:
679
906
                readv_ranges.append((location, length))
680
907
        self._read_and_parse(readv_ranges)
 
908
        if self._nodes is not None:
 
909
            # The _read_and_parse triggered a _buffer_all, grab the data and
 
910
            # return it
 
911
            for location, key in pending_references:
 
912
                value, refs = self._nodes[key]
 
913
                result.append(((location, key), (self, key, value, refs)))
 
914
            return result
681
915
        for location, key in pending_references:
682
916
            # answer key references we had to look-up-late.
683
 
            index = self._parsed_key_index(key)
684
917
            value, refs = self._bisect_nodes[key]
685
918
            result.append(((location, key), (self, key,
686
919
                value, self._resolve_references(refs))))
830
1063
                trim_start = data.find('\n') + 1
831
1064
            else:
832
1065
                trim_start = data.find('\n', trim_start) + 1
833
 
            assert trim_start != 0, 'no \n was present'
 
1066
            if not (trim_start != 0):
 
1067
                raise AssertionError('no \n was present')
834
1068
            # print 'removing start', offset, trim_start, repr(data[:trim_start])
835
1069
        if not end_adjacent:
836
1070
            # work around python bug in rfind
838
1072
                trim_end = data.rfind('\n') + 1
839
1073
            else:
840
1074
                trim_end = data.rfind('\n', None, trim_end) + 1
841
 
            assert trim_end != 0, 'no \n was present'
 
1075
            if not (trim_end != 0):
 
1076
                raise AssertionError('no \n was present')
842
1077
            # print 'removing end', offset, trim_end, repr(data[trim_end:])
843
1078
        # adjust offset and data to the parseable data.
844
1079
        trimmed_data = data[trim_start:trim_end]
845
 
        assert trimmed_data, 'read unneeded data [%d:%d] from [%d:%d]' % (
846
 
            trim_start, trim_end, offset, offset + len(data))
 
1080
        if not (trimmed_data):
 
1081
            raise AssertionError('read unneeded data [%d:%d] from [%d:%d]'
 
1082
                % (trim_start, trim_end, offset, offset + len(data)))
847
1083
        if trim_start:
848
1084
            offset += trim_start
849
1085
        # print "parsing", repr(trimmed_data)
867
1103
            if line == '':
868
1104
                # must be at the end
869
1105
                if self._size:
870
 
                    assert self._size == pos + 1, "%s %s" % (self._size, pos)
 
1106
                    if not (self._size == pos + 1):
 
1107
                        raise AssertionError("%s %s" % (self._size, pos))
871
1108
                trailers += 1
872
1109
                continue
873
1110
            elements = line.split('\0')
874
1111
            if len(elements) != self._expected_elements:
875
1112
                raise errors.BadIndexData(self)
876
 
            # keys are tuples
877
 
            key = tuple(elements[:self._key_length])
 
1113
            # keys are tuples. Each element is a string that may occur many
 
1114
            # times, so we intern them to save space. AB, RC, 200807
 
1115
            key = tuple([intern(element) for element in elements[:self._key_length]])
878
1116
            if first_key is None:
879
1117
                first_key = key
880
1118
            absent, references, value = elements[-3:]
947
1185
            self._parsed_key_map.insert(index + 1, new_key)
948
1186
 
949
1187
    def _read_and_parse(self, readv_ranges):
950
 
        """Read the the ranges and parse the resulting data.
 
1188
        """Read the ranges and parse the resulting data.
951
1189
 
952
1190
        :param readv_ranges: A prepared readv range list.
953
1191
        """
954
 
        if readv_ranges:
955
 
            readv_data = self._transport.readv(self._name, readv_ranges, True,
956
 
                self._size)
957
 
            # parse
958
 
            for offset, data in readv_data:
959
 
                if self._bisect_nodes is None:
960
 
                    # this must be the start
961
 
                    assert offset == 0
962
 
                    offset, data = self._parse_header_from_bytes(data)
963
 
                # print readv_ranges, "[%d:%d]" % (offset, offset + len(data))
964
 
                self._parse_region(offset, data)
 
1192
        if not readv_ranges:
 
1193
            return
 
1194
        if self._nodes is None and self._bytes_read * 2 >= self._size:
 
1195
            # We've already read more than 50% of the file and we are about to
 
1196
            # request more data, just _buffer_all() and be done
 
1197
            self._buffer_all()
 
1198
            return
 
1199
 
 
1200
        base_offset = self._base_offset
 
1201
        if base_offset != 0:
 
1202
            # Rewrite the ranges for the offset
 
1203
            readv_ranges = [(start+base_offset, size)
 
1204
                            for start, size in readv_ranges]
 
1205
        readv_data = self._transport.readv(self._name, readv_ranges, True,
 
1206
            self._size + self._base_offset)
 
1207
        # parse
 
1208
        for offset, data in readv_data:
 
1209
            offset -= base_offset
 
1210
            self._bytes_read += len(data)
 
1211
            if offset < 0:
 
1212
                # transport.readv() expanded to extra data which isn't part of
 
1213
                # this index
 
1214
                data = data[-offset:]
 
1215
                offset = 0
 
1216
            if offset == 0 and len(data) == self._size:
 
1217
                # We read the whole range, most likely because the
 
1218
                # Transport upcast our readv ranges into one long request
 
1219
                # for enough total data to grab the whole index.
 
1220
                self._buffer_all(StringIO(data))
 
1221
                return
 
1222
            if self._bisect_nodes is None:
 
1223
                # this must be the start
 
1224
                if not (offset == 0):
 
1225
                    raise AssertionError()
 
1226
                offset, data = self._parse_header_from_bytes(data)
 
1227
            # print readv_ranges, "[%d:%d]" % (offset, offset + len(data))
 
1228
            self._parse_region(offset, data)
965
1229
 
966
1230
    def _signature(self):
967
1231
        """The file signature for this index type."""
976
1240
 
977
1241
class CombinedGraphIndex(object):
978
1242
    """A GraphIndex made up from smaller GraphIndices.
979
 
    
 
1243
 
980
1244
    The backing indices must implement GraphIndex, and are presumed to be
981
1245
    static data.
982
1246
 
983
1247
    Queries against the combined index will be made against the first index,
984
 
    and then the second and so on. The order of index's can thus influence
 
1248
    and then the second and so on. The order of indices can thus influence
985
1249
    performance significantly. For example, if one index is on local disk and a
986
1250
    second on a remote server, the local disk index should be before the other
987
1251
    in the index list.
 
1252
    
 
1253
    Also, queries tend to need results from the same indices as previous
 
1254
    queries.  So the indices will be reordered after every query to put the
 
1255
    indices that had the result(s) of that query first (while otherwise
 
1256
    preserving the relative ordering).
988
1257
    """
989
1258
 
990
 
    def __init__(self, indices):
 
1259
    def __init__(self, indices, reload_func=None):
991
1260
        """Create a CombinedGraphIndex backed by indices.
992
1261
 
993
1262
        :param indices: An ordered list of indices to query for data.
 
1263
        :param reload_func: A function to call if we find we are missing an
 
1264
            index. Should have the form reload_func() => True/False to indicate
 
1265
            if reloading actually changed anything.
994
1266
        """
995
1267
        self._indices = indices
 
1268
        self._reload_func = reload_func
 
1269
        # Sibling indices are other CombinedGraphIndex that we should call
 
1270
        # _move_to_front_by_name on when we auto-reorder ourself.
 
1271
        self._sibling_indices = []
 
1272
        # A list of names that corresponds to the instances in self._indices,
 
1273
        # so _index_names[0] is always the name for _indices[0], etc.  Sibling
 
1274
        # indices must all use the same set of names as each other.
 
1275
        self._index_names = [None] * len(self._indices)
996
1276
 
997
1277
    def __repr__(self):
998
1278
        return "%s(%s)" % (
999
1279
                self.__class__.__name__,
1000
1280
                ', '.join(map(repr, self._indices)))
1001
1281
 
1002
 
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
1003
 
    def get_parents(self, revision_ids):
1004
 
        """See graph._StackedParentsProvider.get_parents.
1005
 
        
1006
 
        This implementation thunks the graph.Graph.get_parents api across to
1007
 
        GraphIndex.
1008
 
 
1009
 
        :param revision_ids: An iterable of graph keys for this graph.
1010
 
        :return: A list of parent details for each key in revision_ids.
1011
 
            Each parent details will be one of:
1012
 
             * None when the key was missing
1013
 
             * (NULL_REVISION,) when the key has no parents.
1014
 
             * (parent_key, parent_key...) otherwise.
1015
 
        """
1016
 
        parent_map = self.get_parent_map(revision_ids)
1017
 
        return [parent_map.get(r, None) for r in revision_ids]
 
1282
    def clear_cache(self):
 
1283
        """See GraphIndex.clear_cache()"""
 
1284
        for index in self._indices:
 
1285
            index.clear_cache()
1018
1286
 
1019
1287
    def get_parent_map(self, keys):
1020
 
        """See graph._StackedParentsProvider.get_parent_map"""
 
1288
        """See graph.StackedParentsProvider.get_parent_map"""
1021
1289
        search_keys = set(keys)
1022
1290
        if NULL_REVISION in search_keys:
1023
1291
            search_keys.discard(NULL_REVISION)
1031
1299
            found_parents[key] = parents
1032
1300
        return found_parents
1033
1301
 
1034
 
    def insert_index(self, pos, index):
 
1302
    has_key = _has_key_from_parent_map
 
1303
 
 
1304
    def insert_index(self, pos, index, name=None):
1035
1305
        """Insert a new index in the list of indices to query.
1036
1306
 
1037
1307
        :param pos: The position to insert the index.
1038
1308
        :param index: The index to insert.
 
1309
        :param name: a name for this index, e.g. a pack name.  These names can
 
1310
            be used to reflect index reorderings to related CombinedGraphIndex
 
1311
            instances that use the same names.  (see set_sibling_indices)
1039
1312
        """
1040
1313
        self._indices.insert(pos, index)
 
1314
        self._index_names.insert(pos, name)
1041
1315
 
1042
1316
    def iter_all_entries(self):
1043
1317
        """Iterate over all keys within the index
1050
1324
            the most efficient order for the index.
1051
1325
        """
1052
1326
        seen_keys = set()
1053
 
        for index in self._indices:
1054
 
            for node in index.iter_all_entries():
1055
 
                if node[1] not in seen_keys:
1056
 
                    yield node
1057
 
                    seen_keys.add(node[1])
 
1327
        while True:
 
1328
            try:
 
1329
                for index in self._indices:
 
1330
                    for node in index.iter_all_entries():
 
1331
                        if node[1] not in seen_keys:
 
1332
                            yield node
 
1333
                            seen_keys.add(node[1])
 
1334
                return
 
1335
            except errors.NoSuchFile:
 
1336
                self._reload_or_raise()
1058
1337
 
1059
1338
    def iter_entries(self, keys):
1060
1339
        """Iterate over keys within the index.
1063
1342
        value and are only reported once.
1064
1343
 
1065
1344
        :param keys: An iterable providing the keys to be retrieved.
1066
 
        :return: An iterable of (index, key, reference_lists, value). There is no
1067
 
            defined order for the result iteration - it will be in the most
 
1345
        :return: An iterable of (index, key, reference_lists, value). There is
 
1346
            no defined order for the result iteration - it will be in the most
1068
1347
            efficient order for the index.
1069
1348
        """
1070
1349
        keys = set(keys)
1071
 
        for index in self._indices:
1072
 
            if not keys:
1073
 
                return
1074
 
            for node in index.iter_entries(keys):
1075
 
                keys.remove(node[1])
1076
 
                yield node
 
1350
        hit_indices = []
 
1351
        while True:
 
1352
            try:
 
1353
                for index in self._indices:
 
1354
                    if not keys:
 
1355
                        break
 
1356
                    index_hit = False
 
1357
                    for node in index.iter_entries(keys):
 
1358
                        keys.remove(node[1])
 
1359
                        yield node
 
1360
                        index_hit = True
 
1361
                    if index_hit:
 
1362
                        hit_indices.append(index)
 
1363
                break
 
1364
            except errors.NoSuchFile:
 
1365
                self._reload_or_raise()
 
1366
        self._move_to_front(hit_indices)
1077
1367
 
1078
1368
    def iter_entries_prefix(self, keys):
1079
1369
        """Iterate over keys within the index using prefix matching.
1099
1389
        if not keys:
1100
1390
            return
1101
1391
        seen_keys = set()
1102
 
        for index in self._indices:
1103
 
            for node in index.iter_entries_prefix(keys):
1104
 
                if node[1] in seen_keys:
1105
 
                    continue
1106
 
                seen_keys.add(node[1])
1107
 
                yield node
 
1392
        hit_indices = []
 
1393
        while True:
 
1394
            try:
 
1395
                for index in self._indices:
 
1396
                    index_hit = False
 
1397
                    for node in index.iter_entries_prefix(keys):
 
1398
                        if node[1] in seen_keys:
 
1399
                            continue
 
1400
                        seen_keys.add(node[1])
 
1401
                        yield node
 
1402
                        index_hit = True
 
1403
                    if index_hit:
 
1404
                        hit_indices.append(index)
 
1405
                break
 
1406
            except errors.NoSuchFile:
 
1407
                self._reload_or_raise()
 
1408
        self._move_to_front(hit_indices)
 
1409
 
 
1410
    def _move_to_front(self, hit_indices):
 
1411
        """Rearrange self._indices so that hit_indices are first.
 
1412
 
 
1413
        Order is maintained as much as possible, e.g. the first unhit index
 
1414
        will be the first index in _indices after the hit_indices, and the
 
1415
        hit_indices will be present in exactly the order they are passed to
 
1416
        _move_to_front.
 
1417
 
 
1418
        _move_to_front propagates to all objects in self._sibling_indices by
 
1419
        calling _move_to_front_by_name.
 
1420
        """
 
1421
        if self._indices[:len(hit_indices)] == hit_indices:
 
1422
            # The 'hit_indices' are already at the front (and in the same
 
1423
            # order), no need to re-order
 
1424
            return
 
1425
        hit_names = self._move_to_front_by_index(hit_indices)
 
1426
        for sibling_idx in self._sibling_indices:
 
1427
            sibling_idx._move_to_front_by_name(hit_names)
 
1428
 
 
1429
    def _move_to_front_by_index(self, hit_indices):
 
1430
        """Core logic for _move_to_front.
 
1431
        
 
1432
        Returns a list of names corresponding to the hit_indices param.
 
1433
        """
 
1434
        indices_info = zip(self._index_names, self._indices)
 
1435
        if 'index' in debug.debug_flags:
 
1436
            mutter('CombinedGraphIndex reordering: currently %r, promoting %r',
 
1437
                   indices_info, hit_indices)
 
1438
        hit_names = []
 
1439
        unhit_names = []
 
1440
        new_hit_indices = []
 
1441
        unhit_indices = []
 
1442
 
 
1443
        for offset, (name, idx) in enumerate(indices_info):
 
1444
            if idx in hit_indices:
 
1445
                hit_names.append(name)
 
1446
                new_hit_indices.append(idx)
 
1447
                if len(new_hit_indices) == len(hit_indices):
 
1448
                    # We've found all of the hit entries, everything else is
 
1449
                    # unhit
 
1450
                    unhit_names.extend(self._index_names[offset+1:])
 
1451
                    unhit_indices.extend(self._indices[offset+1:])
 
1452
                    break
 
1453
            else:
 
1454
                unhit_names.append(name)
 
1455
                unhit_indices.append(idx)
 
1456
 
 
1457
        self._indices = new_hit_indices + unhit_indices
 
1458
        self._index_names = hit_names + unhit_names
 
1459
        if 'index' in debug.debug_flags:
 
1460
            mutter('CombinedGraphIndex reordered: %r', self._indices)
 
1461
        return hit_names
 
1462
 
 
1463
    def _move_to_front_by_name(self, hit_names):
 
1464
        """Moves indices named by 'hit_names' to front of the search order, as
 
1465
        described in _move_to_front.
 
1466
        """
 
1467
        # Translate names to index instances, and then call
 
1468
        # _move_to_front_by_index.
 
1469
        indices_info = zip(self._index_names, self._indices)
 
1470
        hit_indices = []
 
1471
        for name, idx in indices_info:
 
1472
            if name in hit_names:
 
1473
                hit_indices.append(idx)
 
1474
        self._move_to_front_by_index(hit_indices)
 
1475
 
 
1476
    def find_ancestry(self, keys, ref_list_num):
 
1477
        """Find the complete ancestry for the given set of keys.
 
1478
 
 
1479
        Note that this is a whole-ancestry request, so it should be used
 
1480
        sparingly.
 
1481
 
 
1482
        :param keys: An iterable of keys to look for
 
1483
        :param ref_list_num: The reference list which references the parents
 
1484
            we care about.
 
1485
        :return: (parent_map, missing_keys)
 
1486
        """
 
1487
        # XXX: make this call _move_to_front?
 
1488
        missing_keys = set()
 
1489
        parent_map = {}
 
1490
        keys_to_lookup = set(keys)
 
1491
        generation = 0
 
1492
        while keys_to_lookup:
 
1493
            # keys that *all* indexes claim are missing, stop searching them
 
1494
            generation += 1
 
1495
            all_index_missing = None
 
1496
            # print 'gen\tidx\tsub\tn_keys\tn_pmap\tn_miss'
 
1497
            # print '%4d\t\t\t%4d\t%5d\t%5d' % (generation, len(keys_to_lookup),
 
1498
            #                                   len(parent_map),
 
1499
            #                                   len(missing_keys))
 
1500
            for index_idx, index in enumerate(self._indices):
 
1501
                # TODO: we should probably be doing something with
 
1502
                #       'missing_keys' since we've already determined that
 
1503
                #       those revisions have not been found anywhere
 
1504
                index_missing_keys = set()
 
1505
                # Find all of the ancestry we can from this index
 
1506
                # keep looking until the search_keys set is empty, which means
 
1507
                # things we didn't find should be in index_missing_keys
 
1508
                search_keys = keys_to_lookup
 
1509
                sub_generation = 0
 
1510
                # print '    \t%2d\t\t%4d\t%5d\t%5d' % (
 
1511
                #     index_idx, len(search_keys),
 
1512
                #     len(parent_map), len(index_missing_keys))
 
1513
                while search_keys:
 
1514
                    sub_generation += 1
 
1515
                    # TODO: ref_list_num should really be a parameter, since
 
1516
                    #       CombinedGraphIndex does not know what the ref lists
 
1517
                    #       mean.
 
1518
                    search_keys = index._find_ancestors(search_keys,
 
1519
                        ref_list_num, parent_map, index_missing_keys)
 
1520
                    # print '    \t  \t%2d\t%4d\t%5d\t%5d' % (
 
1521
                    #     sub_generation, len(search_keys),
 
1522
                    #     len(parent_map), len(index_missing_keys))
 
1523
                # Now set whatever was missing to be searched in the next index
 
1524
                keys_to_lookup = index_missing_keys
 
1525
                if all_index_missing is None:
 
1526
                    all_index_missing = set(index_missing_keys)
 
1527
                else:
 
1528
                    all_index_missing.intersection_update(index_missing_keys)
 
1529
                if not keys_to_lookup:
 
1530
                    break
 
1531
            if all_index_missing is None:
 
1532
                # There were no indexes, so all search keys are 'missing'
 
1533
                missing_keys.update(keys_to_lookup)
 
1534
                keys_to_lookup = None
 
1535
            else:
 
1536
                missing_keys.update(all_index_missing)
 
1537
                keys_to_lookup.difference_update(all_index_missing)
 
1538
        return parent_map, missing_keys
1108
1539
 
1109
1540
    def key_count(self):
1110
1541
        """Return an estimate of the number of keys in this index.
1111
 
        
 
1542
 
1112
1543
        For CombinedGraphIndex this is approximated by the sum of the keys of
1113
1544
        the child indices. As child indices may have duplicate keys this can
1114
1545
        have a maximum error of the number of child indices * largest number of
1115
1546
        keys in any index.
1116
1547
        """
1117
 
        return sum((index.key_count() for index in self._indices), 0)
 
1548
        while True:
 
1549
            try:
 
1550
                return sum((index.key_count() for index in self._indices), 0)
 
1551
            except errors.NoSuchFile:
 
1552
                self._reload_or_raise()
 
1553
 
 
1554
    missing_keys = _missing_keys_from_parent_map
 
1555
 
 
1556
    def _reload_or_raise(self):
 
1557
        """We just got a NoSuchFile exception.
 
1558
 
 
1559
        Try to reload the indices, if it fails, just raise the current
 
1560
        exception.
 
1561
        """
 
1562
        if self._reload_func is None:
 
1563
            raise
 
1564
        exc_type, exc_value, exc_traceback = sys.exc_info()
 
1565
        trace.mutter('Trying to reload after getting exception: %s',
 
1566
                     exc_value)
 
1567
        if not self._reload_func():
 
1568
            # We tried to reload, but nothing changed, so we fail anyway
 
1569
            trace.mutter('_reload_func indicated nothing has changed.'
 
1570
                         ' Raising original exception.')
 
1571
            raise exc_type, exc_value, exc_traceback
 
1572
 
 
1573
    def set_sibling_indices(self, sibling_combined_graph_indices):
 
1574
        """Set the CombinedGraphIndex objects to reorder after reordering self.
 
1575
        """
 
1576
        self._sibling_indices = sibling_combined_graph_indices
1118
1577
 
1119
1578
    def validate(self):
1120
1579
        """Validate that everything in the index can be accessed."""
1121
 
        for index in self._indices:
1122
 
            index.validate()
 
1580
        while True:
 
1581
            try:
 
1582
                for index in self._indices:
 
1583
                    index.validate()
 
1584
                return
 
1585
            except errors.NoSuchFile:
 
1586
                self._reload_or_raise()
1123
1587
 
1124
1588
 
1125
1589
class InMemoryGraphIndex(GraphIndexBuilder):
1169
1633
            defined order for the result iteration - it will be in the most
1170
1634
            efficient order for the index (keys iteration order in this case).
1171
1635
        """
1172
 
        keys = set(keys)
 
1636
        # Note: See BTreeBuilder.iter_entries for an explanation of why we
 
1637
        #       aren't using set().intersection() here
 
1638
        nodes = self._nodes
 
1639
        keys = [key for key in keys if key in nodes]
1173
1640
        if self.reference_lists:
1174
 
            for key in keys.intersection(self._keys):
1175
 
                node = self._nodes[key]
 
1641
            for key in keys:
 
1642
                node = nodes[key]
1176
1643
                if not node[0]:
1177
1644
                    yield self, key, node[2], node[1]
1178
1645
        else:
1179
 
            for key in keys.intersection(self._keys):
1180
 
                node = self._nodes[key]
 
1646
            for key in keys:
 
1647
                node = nodes[key]
1181
1648
                if not node[0]:
1182
1649
                    yield self, key, node[2]
1183
1650
 
1212
1679
                    raise errors.BadIndexKey(key)
1213
1680
                node = self._nodes[key]
1214
1681
                if node[0]:
1215
 
                    continue 
 
1682
                    continue
1216
1683
                if self.reference_lists:
1217
1684
                    yield self, key, node[2], node[1]
1218
1685
                else:
1219
1686
                    yield self, key, node[2]
1220
1687
            return
 
1688
        nodes_by_key = self._get_nodes_by_key()
1221
1689
        for key in keys:
1222
1690
            # sanity check
1223
1691
            if key[0] is None:
1225
1693
            if len(key) != self._key_length:
1226
1694
                raise errors.BadIndexKey(key)
1227
1695
            # find what it refers to:
1228
 
            key_dict = self._nodes_by_key
 
1696
            key_dict = nodes_by_key
1229
1697
            elements = list(key)
1230
1698
            # find the subdict to return
1231
1699
            try:
1242
1710
                    # can't be empty or would not exist
1243
1711
                    item, value = key_dict.iteritems().next()
1244
1712
                    if type(value) == dict:
1245
 
                        # push keys 
 
1713
                        # push keys
1246
1714
                        dicts.extend(key_dict.itervalues())
1247
1715
                    else:
1248
1716
                        # yield keys
1253
1721
 
1254
1722
    def key_count(self):
1255
1723
        """Return an estimate of the number of keys in this index.
1256
 
        
 
1724
 
1257
1725
        For InMemoryGraphIndex the estimate is exact.
1258
1726
        """
1259
 
        return len(self._keys)
 
1727
        return len(self._nodes) - len(self._absent_keys)
1260
1728
 
1261
1729
    def validate(self):
1262
1730
        """In memory index's have no known corruption at the moment."""
1267
1735
 
1268
1736
    Queries against this will emit queries against the adapted Graph with the
1269
1737
    prefix added, queries for all items use iter_entries_prefix. The returned
1270
 
    nodes will have their keys and node references adjusted to remove the 
 
1738
    nodes will have their keys and node references adjusted to remove the
1271
1739
    prefix. Finally, an add_nodes_callback can be supplied - when called the
1272
1740
    nodes and references being added will have prefix prepended.
1273
1741
    """
1300
1768
                    adjusted_references))
1301
1769
        except ValueError:
1302
1770
            # XXX: TODO add an explicit interface for getting the reference list
1303
 
            # status, to handle this bit of user-friendliness in the API more 
 
1771
            # status, to handle this bit of user-friendliness in the API more
1304
1772
            # explicitly.
1305
1773
            for (key, value) in nodes:
1306
1774
                translated_nodes.append((self.prefix + key, value))
1378
1846
 
1379
1847
    def key_count(self):
1380
1848
        """Return an estimate of the number of keys in this index.
1381
 
        
 
1849
 
1382
1850
        For GraphIndexPrefixAdapter this is relatively expensive - key
1383
1851
        iteration with the prefix is done.
1384
1852
        """