← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

(jelmer) Support upgrading between the 2a and development-colo formats.
 (Jelmer Vernooij)

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-2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
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(), """
33
 
from bzrlib import trace
34
 
from bzrlib.bisect_multi import bisect_multi_bytes
35
 
from bzrlib.revision import NULL_REVISION
36
 
from bzrlib.trace import mutter
 
34
from bzrlib import (
 
35
    bisect_multi,
 
36
    revision as _mod_revision,
 
37
    trace,
 
38
    )
37
39
""")
38
40
from bzrlib import (
39
41
    debug,
40
42
    errors,
41
 
    symbol_versioning,
42
43
    )
 
44
from bzrlib.static_tuple import StaticTuple
43
45
 
44
46
_HEADER_READV = (0, 200)
45
47
_OPTION_KEY_ELEMENTS = "key_elements="
52
54
_newline_null_re = re.compile('[\n\0]')
53
55
 
54
56
 
 
57
def _has_key_from_parent_map(self, key):
 
58
    """Check if this index has one key.
 
59
 
 
60
    If it's possible to check for multiple keys at once through
 
61
    calling get_parent_map that should be faster.
 
62
    """
 
63
    return (key in self.get_parent_map([key]))
 
64
 
 
65
 
 
66
def _missing_keys_from_parent_map(self, keys):
 
67
    return set(keys) - set(self.get_parent_map(keys))
 
68
 
 
69
 
55
70
class GraphIndexBuilder(object):
56
71
    """A builder that can build a GraphIndex.
57
 
    
58
 
    The resulting graph has the structure:
59
 
    
60
 
    _SIGNATURE OPTIONS NODES NEWLINE
61
 
    _SIGNATURE     := 'Bazaar Graph Index 1' NEWLINE
62
 
    OPTIONS        := 'node_ref_lists=' DIGITS NEWLINE
63
 
    NODES          := NODE*
64
 
    NODE           := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
65
 
    KEY            := Not-whitespace-utf8
66
 
    ABSENT         := 'a'
67
 
    REFERENCES     := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
68
 
    REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
69
 
    REFERENCE      := DIGITS  ; digits is the byte offset in the index of the
70
 
                              ; referenced key.
71
 
    VALUE          := no-newline-no-null-bytes
 
72
 
 
73
    The resulting graph has the structure::
 
74
 
 
75
      _SIGNATURE OPTIONS NODES NEWLINE
 
76
      _SIGNATURE     := 'Bazaar Graph Index 1' NEWLINE
 
77
      OPTIONS        := 'node_ref_lists=' DIGITS NEWLINE
 
78
      NODES          := NODE*
 
79
      NODE           := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
 
80
      KEY            := Not-whitespace-utf8
 
81
      ABSENT         := 'a'
 
82
      REFERENCES     := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
 
83
      REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
 
84
      REFERENCE      := DIGITS  ; digits is the byte offset in the index of the
 
85
                                ; referenced key.
 
86
      VALUE          := no-newline-no-null-bytes
72
87
    """
73
88
 
74
89
    def __init__(self, reference_lists=0, key_elements=1):
79
94
        :param key_elements: The number of bytestrings in each key.
80
95
        """
81
96
        self.reference_lists = reference_lists
82
 
        self._keys = set()
 
97
        # A dict of {key: (absent, ref_lists, value)}
83
98
        self._nodes = {}
84
 
        self._nodes_by_key = {}
 
99
        # Keys that are referenced but not actually present in this index
 
100
        self._absent_keys = set()
 
101
        self._nodes_by_key = None
85
102
        self._key_length = key_elements
 
103
        self._optimize_for_size = False
 
104
        self._combine_backing_indices = True
86
105
 
87
106
    def _check_key(self, key):
88
107
        """Raise BadIndexKey if key is not a valid key for this index."""
89
 
        if type(key) != tuple:
 
108
        if type(key) not in (tuple, StaticTuple):
90
109
            raise errors.BadIndexKey(key)
91
110
        if self._key_length != len(key):
92
111
            raise errors.BadIndexKey(key)
94
113
            if not element or _whitespace_re.search(element) is not None:
95
114
                raise errors.BadIndexKey(element)
96
115
 
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
 
        """
 
116
    def _external_references(self):
 
117
        """Return references that are not present in this index.
 
118
        """
 
119
        keys = set()
 
120
        refs = set()
 
121
        # TODO: JAM 2008-11-21 This makes an assumption about how the reference
 
122
        #       lists are used. It is currently correct for pack-0.92 through
 
123
        #       1.9, which use the node references (3rd column) second
 
124
        #       reference list as the compression parent. Perhaps this should
 
125
        #       be moved into something higher up the stack, since it
 
126
        #       makes assumptions about how the index is used.
 
127
        if self.reference_lists > 1:
 
128
            for node in self.iter_all_entries():
 
129
                keys.add(node[1])
 
130
                refs.update(node[3][1])
 
131
            return refs - keys
 
132
        else:
 
133
            # If reference_lists == 0 there can be no external references, and
 
134
            # if reference_lists == 1, then there isn't a place to store the
 
135
            # compression parent
 
136
            return set()
 
137
 
 
138
    def _get_nodes_by_key(self):
 
139
        if self._nodes_by_key is None:
 
140
            nodes_by_key = {}
 
141
            if self.reference_lists:
 
142
                for key, (absent, references, value) in self._nodes.iteritems():
 
143
                    if absent:
 
144
                        continue
 
145
                    key_dict = nodes_by_key
 
146
                    for subkey in key[:-1]:
 
147
                        key_dict = key_dict.setdefault(subkey, {})
 
148
                    key_dict[key[-1]] = key, value, references
 
149
            else:
 
150
                for key, (absent, references, value) in self._nodes.iteritems():
 
151
                    if absent:
 
152
                        continue
 
153
                    key_dict = nodes_by_key
 
154
                    for subkey in key[:-1]:
 
155
                        key_dict = key_dict.setdefault(subkey, {})
 
156
                    key_dict[key[-1]] = key, value
 
157
            self._nodes_by_key = nodes_by_key
 
158
        return self._nodes_by_key
 
159
 
 
160
    def _update_nodes_by_key(self, key, value, node_refs):
 
161
        """Update the _nodes_by_key dict with a new key.
 
162
 
 
163
        For a key of (foo, bar, baz) create
 
164
        _nodes_by_key[foo][bar][baz] = key_value
 
165
        """
 
166
        if self._nodes_by_key is None:
 
167
            return
 
168
        key_dict = self._nodes_by_key
 
169
        if self.reference_lists:
 
170
            key_value = StaticTuple(key, value, node_refs)
 
171
        else:
 
172
            key_value = StaticTuple(key, value)
 
173
        for subkey in key[:-1]:
 
174
            key_dict = key_dict.setdefault(subkey, {})
 
175
        key_dict[key[-1]] = key_value
 
176
 
 
177
    def _check_key_ref_value(self, key, references, value):
 
178
        """Check that 'key' and 'references' are all valid.
 
179
 
 
180
        :param key: A key tuple. Must conform to the key interface (be a tuple,
 
181
            be of the right length, not have any whitespace or nulls in any key
 
182
            element.)
 
183
        :param references: An iterable of reference lists. Something like
 
184
            [[(ref, key)], [(ref, key), (other, key)]]
 
185
        :param value: The value associate with this key. Must not contain
 
186
            newlines or null characters.
 
187
        :return: (node_refs, absent_references)
 
188
        
 
189
            * node_refs: basically a packed form of 'references' where all
 
190
              iterables are tuples
 
191
            * absent_references: reference keys that are not in self._nodes.
 
192
              This may contain duplicates if the same key is referenced in
 
193
              multiple lists.
 
194
        """
 
195
        as_st = StaticTuple.from_sequence
108
196
        self._check_key(key)
109
197
        if _newline_null_re.search(value) is not None:
110
198
            raise errors.BadIndexValue(value)
111
199
        if len(references) != self.reference_lists:
112
200
            raise errors.BadIndexValue(references)
113
201
        node_refs = []
 
202
        absent_references = []
114
203
        for reference_list in references:
115
204
            for reference in reference_list:
116
 
                self._check_key(reference)
 
205
                # If reference *is* in self._nodes, then we know it has already
 
206
                # been checked.
117
207
                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] == '':
 
208
                    self._check_key(reference)
 
209
                    absent_references.append(reference)
 
210
            reference_list = as_st([as_st(ref).intern()
 
211
                                    for ref in reference_list])
 
212
            node_refs.append(reference_list)
 
213
        return as_st(node_refs), absent_references
 
214
 
 
215
    def add_node(self, key, value, references=()):
 
216
        """Add a node to the index.
 
217
 
 
218
        :param key: The key. keys are non-empty tuples containing
 
219
            as many whitespace-free utf8 bytestrings as the key length
 
220
            defined for this index.
 
221
        :param references: An iterable of iterables of keys. Each is a
 
222
            reference to another key.
 
223
        :param value: The value to associate with the key. It may be any
 
224
            bytes as long as it does not contain \\0 or \\n.
 
225
        """
 
226
        (node_refs,
 
227
         absent_references) = self._check_key_ref_value(key, references, value)
 
228
        if key in self._nodes and self._nodes[key][0] != 'a':
121
229
            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
 
 
 
230
        for reference in absent_references:
 
231
            # There may be duplicates, but I don't think it is worth worrying
 
232
            # about
 
233
            self._nodes[reference] = ('a', (), '')
 
234
        self._absent_keys.update(absent_references)
 
235
        self._absent_keys.discard(key)
 
236
        self._nodes[key] = ('', node_refs, value)
 
237
        if self._nodes_by_key is not None and self._key_length > 1:
 
238
            self._update_nodes_by_key(key, value, node_refs)
 
239
 
 
240
    def clear_cache(self):
 
241
        """See GraphIndex.clear_cache()
 
242
 
 
243
        This is a no-op, but we need the api to conform to a generic 'Index'
 
244
        abstraction.
 
245
        """
 
246
        
138
247
    def finish(self):
 
248
        """Finish the index.
 
249
 
 
250
        :returns: cStringIO holding the full context of the index as it 
 
251
        should be written to disk.
 
252
        """
139
253
        lines = [_SIGNATURE]
140
254
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
141
255
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
142
 
        lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
 
256
        key_count = len(self._nodes) - len(self._absent_keys)
 
257
        lines.append(_OPTION_LEN + str(key_count) + '\n')
143
258
        prefix_length = sum(len(x) for x in lines)
144
259
        # references are byte offsets. To avoid having to do nasty
145
 
        # polynomial work to resolve offsets (references to later in the 
 
260
        # polynomial work to resolve offsets (references to later in the
146
261
        # file cannot be determined until all the inbetween references have
147
262
        # been calculated too) we pad the offsets with 0's to make them be
148
263
        # of consistent length. Using binary offsets would break the trivial
152
267
        # one to pad all the data with reference-length and determine entry
153
268
        # addresses.
154
269
        # One to serialise.
155
 
        
 
270
 
156
271
        # forward sorted by key. In future we may consider topological sorting,
157
272
        # at the cost of table scans for direct lookup, or a second index for
158
273
        # direct lookup
219
334
            raise errors.BzrError('Failed index creation. Internal error:'
220
335
                ' mismatched output length and expected length: %d %d' %
221
336
                (len(result.getvalue()), expected_bytes))
222
 
        return StringIO(''.join(lines))
 
337
        return result
 
338
 
 
339
    def set_optimize(self, for_size=None, combine_backing_indices=None):
 
340
        """Change how the builder tries to optimize the result.
 
341
 
 
342
        :param for_size: Tell the builder to try and make the index as small as
 
343
            possible.
 
344
        :param combine_backing_indices: If the builder spills to disk to save
 
345
            memory, should the on-disk indices be combined. Set to True if you
 
346
            are going to be probing the index, but to False if you are not. (If
 
347
            you are not querying, then the time spent combining is wasted.)
 
348
        :return: None
 
349
        """
 
350
        # GraphIndexBuilder itself doesn't pay attention to the flag yet, but
 
351
        # other builders do.
 
352
        if for_size is not None:
 
353
            self._optimize_for_size = for_size
 
354
        if combine_backing_indices is not None:
 
355
            self._combine_backing_indices = combine_backing_indices
 
356
 
 
357
    def find_ancestry(self, keys, ref_list_num):
 
358
        """See CombinedGraphIndex.find_ancestry()"""
 
359
        pending = set(keys)
 
360
        parent_map = {}
 
361
        missing_keys = set()
 
362
        while pending:
 
363
            next_pending = set()
 
364
            for _, key, value, ref_lists in self.iter_entries(pending):
 
365
                parent_keys = ref_lists[ref_list_num]
 
366
                parent_map[key] = parent_keys
 
367
                next_pending.update([p for p in parent_keys if p not in
 
368
                                     parent_map])
 
369
                missing_keys.update(pending.difference(parent_map))
 
370
            pending = next_pending
 
371
        return parent_map, missing_keys
223
372
 
224
373
 
225
374
class GraphIndex(object):
226
375
    """An index for data with embedded graphs.
227
 
 
 
376
 
228
377
    The index maps keys to a list of key reference lists, and a value.
229
378
    Each node has the same number of key reference lists. Each key reference
230
379
    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 
 
380
    terminated string without any newlines. The storage of the index is
232
381
    hidden in the interface: keys and key references are always tuples of
233
382
    bytestrings, never the internal representation (e.g. dictionary offsets).
234
383
 
240
389
    suitable for production use. :XXX
241
390
    """
242
391
 
243
 
    def __init__(self, transport, name, size):
 
392
    def __init__(self, transport, name, size, unlimited_cache=False, offset=0):
244
393
        """Open an index called name on transport.
245
394
 
246
395
        :param transport: A bzrlib.transport.Transport.
252
401
            avoided by having it supplied. If size is None, then bisection
253
402
            support will be disabled and accessing the index will just stream
254
403
            all the data.
 
404
        :param offset: Instead of starting the index data at offset 0, start it
 
405
            at an arbitrary offset.
255
406
        """
256
407
        self._transport = transport
257
408
        self._name = name
272
423
        self._keys_by_offset = None
273
424
        self._nodes_by_key = None
274
425
        self._size = size
 
426
        # The number of bytes we've read so far in trying to process this file
 
427
        self._bytes_read = 0
 
428
        self._base_offset = offset
275
429
 
276
430
    def __eq__(self, other):
277
431
        """Equal when self and other were created with the same parameters."""
284
438
    def __ne__(self, other):
285
439
        return not self.__eq__(other)
286
440
 
287
 
    def _buffer_all(self):
 
441
    def __repr__(self):
 
442
        return "%s(%r)" % (self.__class__.__name__,
 
443
            self._transport.abspath(self._name))
 
444
 
 
445
    def _buffer_all(self, stream=None):
288
446
        """Buffer all the index data.
289
447
 
290
448
        Mutates self._nodes and self.keys_by_offset.
291
449
        """
 
450
        if self._nodes is not None:
 
451
            # We already did this
 
452
            return
292
453
        if 'index' in debug.debug_flags:
293
 
            mutter('Reading entire index %s', self._transport.abspath(self._name))
294
 
        stream = self._transport.get(self._name)
 
454
            trace.mutter('Reading entire index %s',
 
455
                          self._transport.abspath(self._name))
 
456
        if stream is None:
 
457
            stream = self._transport.get(self._name)
 
458
            if self._base_offset != 0:
 
459
                # This is wasteful, but it is better than dealing with
 
460
                # adjusting all the offsets, etc.
 
461
                stream = StringIO(stream.read()[self._base_offset:])
295
462
        self._read_prefix(stream)
296
463
        self._expected_elements = 3 + self._key_length
297
464
        line_count = 0
299
466
        self._keys_by_offset = {}
300
467
        # ready-to-return key:value or key:value, node_ref_lists
301
468
        self._nodes = {}
302
 
        self._nodes_by_key = {}
 
469
        self._nodes_by_key = None
303
470
        trailers = 0
304
471
        pos = stream.tell()
305
472
        lines = stream.read().split('\n')
 
473
        # GZ 2009-09-20: Should really use a try/finally block to ensure close
 
474
        stream.close()
306
475
        del lines[-1]
307
476
        _, _, _, trailers = self._parse_lines(lines, pos)
308
477
        for key, absent, references, value in self._keys_by_offset.itervalues():
314
483
            else:
315
484
                node_value = value
316
485
            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
486
        # cache the keys for quick set intersections
332
 
        self._keys = set(self._nodes)
333
487
        if trailers != 1:
334
488
            # there must be one line - the empty trailer line.
335
489
            raise errors.BadIndexData(self)
336
490
 
 
491
    def clear_cache(self):
 
492
        """Clear out any cached/memoized values.
 
493
 
 
494
        This can be called at any time, but generally it is used when we have
 
495
        extracted some information, but don't expect to be requesting any more
 
496
        from this index.
 
497
        """
 
498
 
 
499
    def external_references(self, ref_list_num):
 
500
        """Return references that are not present in this index.
 
501
        """
 
502
        self._buffer_all()
 
503
        if ref_list_num + 1 > self.node_ref_lists:
 
504
            raise ValueError('No ref list %d, index has %d ref lists'
 
505
                % (ref_list_num, self.node_ref_lists))
 
506
        refs = set()
 
507
        nodes = self._nodes
 
508
        for key, (value, ref_lists) in nodes.iteritems():
 
509
            ref_list = ref_lists[ref_list_num]
 
510
            refs.update([ref for ref in ref_list if ref not in nodes])
 
511
        return refs
 
512
 
 
513
    def _get_nodes_by_key(self):
 
514
        if self._nodes_by_key is None:
 
515
            nodes_by_key = {}
 
516
            if self.node_ref_lists:
 
517
                for key, (value, references) in self._nodes.iteritems():
 
518
                    key_dict = nodes_by_key
 
519
                    for subkey in key[:-1]:
 
520
                        key_dict = key_dict.setdefault(subkey, {})
 
521
                    key_dict[key[-1]] = key, value, references
 
522
            else:
 
523
                for key, value in self._nodes.iteritems():
 
524
                    key_dict = nodes_by_key
 
525
                    for subkey in key[:-1]:
 
526
                        key_dict = key_dict.setdefault(subkey, {})
 
527
                    key_dict[key[-1]] = key, value
 
528
            self._nodes_by_key = nodes_by_key
 
529
        return self._nodes_by_key
 
530
 
337
531
    def iter_all_entries(self):
338
532
        """Iterate over all keys within the index.
339
533
 
383
577
 
384
578
    def _resolve_references(self, references):
385
579
        """Return the resolved key references for references.
386
 
        
 
580
 
387
581
        References are resolved by looking up the location of the key in the
388
582
        _keys_by_offset map and substituting the key name, preserving ordering.
389
583
 
390
 
        :param references: An iterable of iterables of key locations. e.g. 
 
584
        :param references: An iterable of iterables of key locations. e.g.
391
585
            [[123, 456], [123]]
392
586
        :return: A tuple of tuples of keys.
393
587
        """
447
641
 
448
642
    def _iter_entries_from_total_buffer(self, keys):
449
643
        """Iterate over keys when the entire index is parsed."""
450
 
        keys = keys.intersection(self._keys)
 
644
        # Note: See the note in BTreeBuilder.iter_entries for why we don't use
 
645
        #       .intersection() here
 
646
        nodes = self._nodes
 
647
        keys = [key for key in keys if key in nodes]
451
648
        if self.node_ref_lists:
452
649
            for key in keys:
453
 
                value, node_refs = self._nodes[key]
 
650
                value, node_refs = nodes[key]
454
651
                yield self, key, value, node_refs
455
652
        else:
456
653
            for key in keys:
457
 
                yield self, key, self._nodes[key]
 
654
                yield self, key, nodes[key]
458
655
 
459
656
    def iter_entries(self, keys):
460
657
        """Iterate over keys within the index.
464
661
            keys supplied. No additional keys will be returned, and every
465
662
            key supplied that is in the index will be returned.
466
663
        """
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
664
        keys = set(keys)
471
665
        if not keys:
472
666
            return []
473
667
        if self._size is None and self._nodes is None:
474
668
            self._buffer_all()
 
669
 
 
670
        # We fit about 20 keys per minimum-read (4K), so if we are looking for
 
671
        # more than 1/20th of the index its likely (assuming homogenous key
 
672
        # spread) that we'll read the entire index. If we're going to do that,
 
673
        # buffer the whole thing. A better analysis might take key spread into
 
674
        # account - but B+Tree indices are better anyway.
 
675
        # We could look at all data read, and use a threshold there, which will
 
676
        # trigger on ancestry walks, but that is not yet fully mapped out.
 
677
        if self._nodes is None and len(keys) * 20 > self.key_count():
 
678
            self._buffer_all()
475
679
        if self._nodes is not None:
476
680
            return self._iter_entries_from_total_buffer(keys)
477
681
        else:
478
 
            return (result[1] for result in bisect_multi_bytes(
 
682
            return (result[1] for result in bisect_multi.bisect_multi_bytes(
479
683
                self._lookup_keys_via_location, self._size, keys))
480
684
 
481
685
    def iter_entries_prefix(self, keys):
519
723
                else:
520
724
                    yield self, key, self._nodes[key]
521
725
            return
 
726
        nodes_by_key = self._get_nodes_by_key()
522
727
        for key in keys:
523
728
            # sanity check
524
729
            if key[0] is None:
526
731
            if len(key) != self._key_length:
527
732
                raise errors.BadIndexKey(key)
528
733
            # find what it refers to:
529
 
            key_dict = self._nodes_by_key
 
734
            key_dict = nodes_by_key
530
735
            elements = list(key)
531
736
            # find the subdict whose contents should be returned.
532
737
            try:
543
748
                    # can't be empty or would not exist
544
749
                    item, value = key_dict.iteritems().next()
545
750
                    if type(value) == dict:
546
 
                        # push keys 
 
751
                        # push keys
547
752
                        dicts.extend(key_dict.itervalues())
548
753
                    else:
549
754
                        # yield keys
555
760
                # the last thing looked up was a terminal element
556
761
                yield (self, ) + key_dict
557
762
 
 
763
    def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
 
764
        """See BTreeIndex._find_ancestors."""
 
765
        # The api can be implemented as a trivial overlay on top of
 
766
        # iter_entries, it is not an efficient implementation, but it at least
 
767
        # gets the job done.
 
768
        found_keys = set()
 
769
        search_keys = set()
 
770
        for index, key, value, refs in self.iter_entries(keys):
 
771
            parent_keys = refs[ref_list_num]
 
772
            found_keys.add(key)
 
773
            parent_map[key] = parent_keys
 
774
            search_keys.update(parent_keys)
 
775
        # Figure out what, if anything, was missing
 
776
        missing_keys.update(set(keys).difference(found_keys))
 
777
        search_keys = search_keys.difference(parent_map)
 
778
        return search_keys
 
779
 
558
780
    def key_count(self):
559
781
        """Return an estimate of the number of keys in this index.
560
 
        
 
782
 
561
783
        For GraphIndex the estimate is exact.
562
784
        """
563
785
        if self._key_count is None:
579
801
        # Possible improvements:
580
802
        #  - only bisect lookup each key once
581
803
        #  - sort the keys first, and use that to reduce the bisection window
582
 
        # ----- 
 
804
        # -----
583
805
        # this progresses in three parts:
584
806
        # read data
585
807
        # parse it
594
816
                # We have the key parsed.
595
817
                continue
596
818
            index = self._parsed_key_index(key)
597
 
            if (len(self._parsed_key_map) and 
 
819
            if (len(self._parsed_key_map) and
598
820
                self._parsed_key_map[index][0] <= key and
599
821
                (self._parsed_key_map[index][1] >= key or
600
822
                 # end of the file has been parsed
604
826
                continue
605
827
            # - if we have examined this part of the file already - yes
606
828
            index = self._parsed_byte_index(location)
607
 
            if (len(self._parsed_byte_map) and 
 
829
            if (len(self._parsed_byte_map) and
608
830
                self._parsed_byte_map[index][0] <= location and
609
831
                self._parsed_byte_map[index][1] > location):
610
832
                # the byte region has been parsed, so no read is needed.
619
841
        if self._bisect_nodes is None:
620
842
            readv_ranges.append(_HEADER_READV)
621
843
        self._read_and_parse(readv_ranges)
 
844
        result = []
 
845
        if self._nodes is not None:
 
846
            # _read_and_parse triggered a _buffer_all because we requested the
 
847
            # whole data range
 
848
            for location, key in location_keys:
 
849
                if key not in self._nodes: # not present
 
850
                    result.append(((location, key), False))
 
851
                elif self.node_ref_lists:
 
852
                    value, refs = self._nodes[key]
 
853
                    result.append(((location, key),
 
854
                        (self, key, value, refs)))
 
855
                else:
 
856
                    result.append(((location, key),
 
857
                        (self, key, self._nodes[key])))
 
858
            return result
622
859
        # generate results:
623
860
        #  - figure out <, >, missing, present
624
861
        #  - result present references so we can return them.
625
 
        result = []
626
862
        # keys that we cannot answer until we resolve references
627
863
        pending_references = []
628
864
        pending_locations = set()
678
914
            if length > 0:
679
915
                readv_ranges.append((location, length))
680
916
        self._read_and_parse(readv_ranges)
 
917
        if self._nodes is not None:
 
918
            # The _read_and_parse triggered a _buffer_all, grab the data and
 
919
            # return it
 
920
            for location, key in pending_references:
 
921
                value, refs = self._nodes[key]
 
922
                result.append(((location, key), (self, key, value, refs)))
 
923
            return result
681
924
        for location, key in pending_references:
682
925
            # answer key references we had to look-up-late.
683
 
            index = self._parsed_key_index(key)
684
926
            value, refs = self._bisect_nodes[key]
685
927
            result.append(((location, key), (self, key,
686
928
                value, self._resolve_references(refs))))
830
1072
                trim_start = data.find('\n') + 1
831
1073
            else:
832
1074
                trim_start = data.find('\n', trim_start) + 1
833
 
            assert trim_start != 0, 'no \n was present'
 
1075
            if not (trim_start != 0):
 
1076
                raise AssertionError('no \n was present')
834
1077
            # print 'removing start', offset, trim_start, repr(data[:trim_start])
835
1078
        if not end_adjacent:
836
1079
            # work around python bug in rfind
838
1081
                trim_end = data.rfind('\n') + 1
839
1082
            else:
840
1083
                trim_end = data.rfind('\n', None, trim_end) + 1
841
 
            assert trim_end != 0, 'no \n was present'
 
1084
            if not (trim_end != 0):
 
1085
                raise AssertionError('no \n was present')
842
1086
            # print 'removing end', offset, trim_end, repr(data[trim_end:])
843
1087
        # adjust offset and data to the parseable data.
844
1088
        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))
 
1089
        if not (trimmed_data):
 
1090
            raise AssertionError('read unneeded data [%d:%d] from [%d:%d]'
 
1091
                % (trim_start, trim_end, offset, offset + len(data)))
847
1092
        if trim_start:
848
1093
            offset += trim_start
849
1094
        # print "parsing", repr(trimmed_data)
867
1112
            if line == '':
868
1113
                # must be at the end
869
1114
                if self._size:
870
 
                    assert self._size == pos + 1, "%s %s" % (self._size, pos)
 
1115
                    if not (self._size == pos + 1):
 
1116
                        raise AssertionError("%s %s" % (self._size, pos))
871
1117
                trailers += 1
872
1118
                continue
873
1119
            elements = line.split('\0')
874
1120
            if len(elements) != self._expected_elements:
875
1121
                raise errors.BadIndexData(self)
876
 
            # keys are tuples
877
 
            key = tuple(elements[:self._key_length])
 
1122
            # keys are tuples. Each element is a string that may occur many
 
1123
            # times, so we intern them to save space. AB, RC, 200807
 
1124
            key = tuple([intern(element) for element in elements[:self._key_length]])
878
1125
            if first_key is None:
879
1126
                first_key = key
880
1127
            absent, references, value = elements[-3:]
947
1194
            self._parsed_key_map.insert(index + 1, new_key)
948
1195
 
949
1196
    def _read_and_parse(self, readv_ranges):
950
 
        """Read the the ranges and parse the resulting data.
 
1197
        """Read the ranges and parse the resulting data.
951
1198
 
952
1199
        :param readv_ranges: A prepared readv range list.
953
1200
        """
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)
 
1201
        if not readv_ranges:
 
1202
            return
 
1203
        if self._nodes is None and self._bytes_read * 2 >= self._size:
 
1204
            # We've already read more than 50% of the file and we are about to
 
1205
            # request more data, just _buffer_all() and be done
 
1206
            self._buffer_all()
 
1207
            return
 
1208
 
 
1209
        base_offset = self._base_offset
 
1210
        if base_offset != 0:
 
1211
            # Rewrite the ranges for the offset
 
1212
            readv_ranges = [(start+base_offset, size)
 
1213
                            for start, size in readv_ranges]
 
1214
        readv_data = self._transport.readv(self._name, readv_ranges, True,
 
1215
            self._size + self._base_offset)
 
1216
        # parse
 
1217
        for offset, data in readv_data:
 
1218
            offset -= base_offset
 
1219
            self._bytes_read += len(data)
 
1220
            if offset < 0:
 
1221
                # transport.readv() expanded to extra data which isn't part of
 
1222
                # this index
 
1223
                data = data[-offset:]
 
1224
                offset = 0
 
1225
            if offset == 0 and len(data) == self._size:
 
1226
                # We read the whole range, most likely because the
 
1227
                # Transport upcast our readv ranges into one long request
 
1228
                # for enough total data to grab the whole index.
 
1229
                self._buffer_all(StringIO(data))
 
1230
                return
 
1231
            if self._bisect_nodes is None:
 
1232
                # this must be the start
 
1233
                if not (offset == 0):
 
1234
                    raise AssertionError()
 
1235
                offset, data = self._parse_header_from_bytes(data)
 
1236
            # print readv_ranges, "[%d:%d]" % (offset, offset + len(data))
 
1237
            self._parse_region(offset, data)
965
1238
 
966
1239
    def _signature(self):
967
1240
        """The file signature for this index type."""
976
1249
 
977
1250
class CombinedGraphIndex(object):
978
1251
    """A GraphIndex made up from smaller GraphIndices.
979
 
    
 
1252
 
980
1253
    The backing indices must implement GraphIndex, and are presumed to be
981
1254
    static data.
982
1255
 
983
1256
    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
 
1257
    and then the second and so on. The order of indices can thus influence
985
1258
    performance significantly. For example, if one index is on local disk and a
986
1259
    second on a remote server, the local disk index should be before the other
987
1260
    in the index list.
 
1261
    
 
1262
    Also, queries tend to need results from the same indices as previous
 
1263
    queries.  So the indices will be reordered after every query to put the
 
1264
    indices that had the result(s) of that query first (while otherwise
 
1265
    preserving the relative ordering).
988
1266
    """
989
1267
 
990
 
    def __init__(self, indices):
 
1268
    def __init__(self, indices, reload_func=None):
991
1269
        """Create a CombinedGraphIndex backed by indices.
992
1270
 
993
1271
        :param indices: An ordered list of indices to query for data.
 
1272
        :param reload_func: A function to call if we find we are missing an
 
1273
            index. Should have the form reload_func() => True/False to indicate
 
1274
            if reloading actually changed anything.
994
1275
        """
995
1276
        self._indices = indices
 
1277
        self._reload_func = reload_func
 
1278
        # Sibling indices are other CombinedGraphIndex that we should call
 
1279
        # _move_to_front_by_name on when we auto-reorder ourself.
 
1280
        self._sibling_indices = []
 
1281
        # A list of names that corresponds to the instances in self._indices,
 
1282
        # so _index_names[0] is always the name for _indices[0], etc.  Sibling
 
1283
        # indices must all use the same set of names as each other.
 
1284
        self._index_names = [None] * len(self._indices)
996
1285
 
997
1286
    def __repr__(self):
998
1287
        return "%s(%s)" % (
999
1288
                self.__class__.__name__,
1000
1289
                ', '.join(map(repr, self._indices)))
1001
1290
 
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]
 
1291
    def clear_cache(self):
 
1292
        """See GraphIndex.clear_cache()"""
 
1293
        for index in self._indices:
 
1294
            index.clear_cache()
1018
1295
 
1019
1296
    def get_parent_map(self, keys):
1020
 
        """See graph._StackedParentsProvider.get_parent_map"""
 
1297
        """See graph.StackedParentsProvider.get_parent_map"""
1021
1298
        search_keys = set(keys)
1022
 
        if NULL_REVISION in search_keys:
1023
 
            search_keys.discard(NULL_REVISION)
1024
 
            found_parents = {NULL_REVISION:[]}
 
1299
        if _mod_revision.NULL_REVISION in search_keys:
 
1300
            search_keys.discard(_mod_revision.NULL_REVISION)
 
1301
            found_parents = {_mod_revision.NULL_REVISION:[]}
1025
1302
        else:
1026
1303
            found_parents = {}
1027
1304
        for index, key, value, refs in self.iter_entries(search_keys):
1028
1305
            parents = refs[0]
1029
1306
            if not parents:
1030
 
                parents = (NULL_REVISION,)
 
1307
                parents = (_mod_revision.NULL_REVISION,)
1031
1308
            found_parents[key] = parents
1032
1309
        return found_parents
1033
1310
 
1034
 
    def insert_index(self, pos, index):
 
1311
    has_key = _has_key_from_parent_map
 
1312
 
 
1313
    def insert_index(self, pos, index, name=None):
1035
1314
        """Insert a new index in the list of indices to query.
1036
1315
 
1037
1316
        :param pos: The position to insert the index.
1038
1317
        :param index: The index to insert.
 
1318
        :param name: a name for this index, e.g. a pack name.  These names can
 
1319
            be used to reflect index reorderings to related CombinedGraphIndex
 
1320
            instances that use the same names.  (see set_sibling_indices)
1039
1321
        """
1040
1322
        self._indices.insert(pos, index)
 
1323
        self._index_names.insert(pos, name)
1041
1324
 
1042
1325
    def iter_all_entries(self):
1043
1326
        """Iterate over all keys within the index
1050
1333
            the most efficient order for the index.
1051
1334
        """
1052
1335
        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])
 
1336
        while True:
 
1337
            try:
 
1338
                for index in self._indices:
 
1339
                    for node in index.iter_all_entries():
 
1340
                        if node[1] not in seen_keys:
 
1341
                            yield node
 
1342
                            seen_keys.add(node[1])
 
1343
                return
 
1344
            except errors.NoSuchFile:
 
1345
                self._reload_or_raise()
1058
1346
 
1059
1347
    def iter_entries(self, keys):
1060
1348
        """Iterate over keys within the index.
1063
1351
        value and are only reported once.
1064
1352
 
1065
1353
        :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
 
1354
        :return: An iterable of (index, key, reference_lists, value). There is
 
1355
            no defined order for the result iteration - it will be in the most
1068
1356
            efficient order for the index.
1069
1357
        """
1070
1358
        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
 
1359
        hit_indices = []
 
1360
        while True:
 
1361
            try:
 
1362
                for index in self._indices:
 
1363
                    if not keys:
 
1364
                        break
 
1365
                    index_hit = False
 
1366
                    for node in index.iter_entries(keys):
 
1367
                        keys.remove(node[1])
 
1368
                        yield node
 
1369
                        index_hit = True
 
1370
                    if index_hit:
 
1371
                        hit_indices.append(index)
 
1372
                break
 
1373
            except errors.NoSuchFile:
 
1374
                self._reload_or_raise()
 
1375
        self._move_to_front(hit_indices)
1077
1376
 
1078
1377
    def iter_entries_prefix(self, keys):
1079
1378
        """Iterate over keys within the index using prefix matching.
1099
1398
        if not keys:
1100
1399
            return
1101
1400
        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
 
1401
        hit_indices = []
 
1402
        while True:
 
1403
            try:
 
1404
                for index in self._indices:
 
1405
                    index_hit = False
 
1406
                    for node in index.iter_entries_prefix(keys):
 
1407
                        if node[1] in seen_keys:
 
1408
                            continue
 
1409
                        seen_keys.add(node[1])
 
1410
                        yield node
 
1411
                        index_hit = True
 
1412
                    if index_hit:
 
1413
                        hit_indices.append(index)
 
1414
                break
 
1415
            except errors.NoSuchFile:
 
1416
                self._reload_or_raise()
 
1417
        self._move_to_front(hit_indices)
 
1418
 
 
1419
    def _move_to_front(self, hit_indices):
 
1420
        """Rearrange self._indices so that hit_indices are first.
 
1421
 
 
1422
        Order is maintained as much as possible, e.g. the first unhit index
 
1423
        will be the first index in _indices after the hit_indices, and the
 
1424
        hit_indices will be present in exactly the order they are passed to
 
1425
        _move_to_front.
 
1426
 
 
1427
        _move_to_front propagates to all objects in self._sibling_indices by
 
1428
        calling _move_to_front_by_name.
 
1429
        """
 
1430
        if self._indices[:len(hit_indices)] == hit_indices:
 
1431
            # The 'hit_indices' are already at the front (and in the same
 
1432
            # order), no need to re-order
 
1433
            return
 
1434
        hit_names = self._move_to_front_by_index(hit_indices)
 
1435
        for sibling_idx in self._sibling_indices:
 
1436
            sibling_idx._move_to_front_by_name(hit_names)
 
1437
 
 
1438
    def _move_to_front_by_index(self, hit_indices):
 
1439
        """Core logic for _move_to_front.
 
1440
        
 
1441
        Returns a list of names corresponding to the hit_indices param.
 
1442
        """
 
1443
        indices_info = zip(self._index_names, self._indices)
 
1444
        if 'index' in debug.debug_flags:
 
1445
            trace.mutter('CombinedGraphIndex reordering: currently %r, '
 
1446
                         'promoting %r', indices_info, hit_indices)
 
1447
        hit_names = []
 
1448
        unhit_names = []
 
1449
        new_hit_indices = []
 
1450
        unhit_indices = []
 
1451
 
 
1452
        for offset, (name, idx) in enumerate(indices_info):
 
1453
            if idx in hit_indices:
 
1454
                hit_names.append(name)
 
1455
                new_hit_indices.append(idx)
 
1456
                if len(new_hit_indices) == len(hit_indices):
 
1457
                    # We've found all of the hit entries, everything else is
 
1458
                    # unhit
 
1459
                    unhit_names.extend(self._index_names[offset+1:])
 
1460
                    unhit_indices.extend(self._indices[offset+1:])
 
1461
                    break
 
1462
            else:
 
1463
                unhit_names.append(name)
 
1464
                unhit_indices.append(idx)
 
1465
 
 
1466
        self._indices = new_hit_indices + unhit_indices
 
1467
        self._index_names = hit_names + unhit_names
 
1468
        if 'index' in debug.debug_flags:
 
1469
            trace.mutter('CombinedGraphIndex reordered: %r', self._indices)
 
1470
        return hit_names
 
1471
 
 
1472
    def _move_to_front_by_name(self, hit_names):
 
1473
        """Moves indices named by 'hit_names' to front of the search order, as
 
1474
        described in _move_to_front.
 
1475
        """
 
1476
        # Translate names to index instances, and then call
 
1477
        # _move_to_front_by_index.
 
1478
        indices_info = zip(self._index_names, self._indices)
 
1479
        hit_indices = []
 
1480
        for name, idx in indices_info:
 
1481
            if name in hit_names:
 
1482
                hit_indices.append(idx)
 
1483
        self._move_to_front_by_index(hit_indices)
 
1484
 
 
1485
    def find_ancestry(self, keys, ref_list_num):
 
1486
        """Find the complete ancestry for the given set of keys.
 
1487
 
 
1488
        Note that this is a whole-ancestry request, so it should be used
 
1489
        sparingly.
 
1490
 
 
1491
        :param keys: An iterable of keys to look for
 
1492
        :param ref_list_num: The reference list which references the parents
 
1493
            we care about.
 
1494
        :return: (parent_map, missing_keys)
 
1495
        """
 
1496
        # XXX: make this call _move_to_front?
 
1497
        missing_keys = set()
 
1498
        parent_map = {}
 
1499
        keys_to_lookup = set(keys)
 
1500
        generation = 0
 
1501
        while keys_to_lookup:
 
1502
            # keys that *all* indexes claim are missing, stop searching them
 
1503
            generation += 1
 
1504
            all_index_missing = None
 
1505
            # print 'gen\tidx\tsub\tn_keys\tn_pmap\tn_miss'
 
1506
            # print '%4d\t\t\t%4d\t%5d\t%5d' % (generation, len(keys_to_lookup),
 
1507
            #                                   len(parent_map),
 
1508
            #                                   len(missing_keys))
 
1509
            for index_idx, index in enumerate(self._indices):
 
1510
                # TODO: we should probably be doing something with
 
1511
                #       'missing_keys' since we've already determined that
 
1512
                #       those revisions have not been found anywhere
 
1513
                index_missing_keys = set()
 
1514
                # Find all of the ancestry we can from this index
 
1515
                # keep looking until the search_keys set is empty, which means
 
1516
                # things we didn't find should be in index_missing_keys
 
1517
                search_keys = keys_to_lookup
 
1518
                sub_generation = 0
 
1519
                # print '    \t%2d\t\t%4d\t%5d\t%5d' % (
 
1520
                #     index_idx, len(search_keys),
 
1521
                #     len(parent_map), len(index_missing_keys))
 
1522
                while search_keys:
 
1523
                    sub_generation += 1
 
1524
                    # TODO: ref_list_num should really be a parameter, since
 
1525
                    #       CombinedGraphIndex does not know what the ref lists
 
1526
                    #       mean.
 
1527
                    search_keys = index._find_ancestors(search_keys,
 
1528
                        ref_list_num, parent_map, index_missing_keys)
 
1529
                    # print '    \t  \t%2d\t%4d\t%5d\t%5d' % (
 
1530
                    #     sub_generation, len(search_keys),
 
1531
                    #     len(parent_map), len(index_missing_keys))
 
1532
                # Now set whatever was missing to be searched in the next index
 
1533
                keys_to_lookup = index_missing_keys
 
1534
                if all_index_missing is None:
 
1535
                    all_index_missing = set(index_missing_keys)
 
1536
                else:
 
1537
                    all_index_missing.intersection_update(index_missing_keys)
 
1538
                if not keys_to_lookup:
 
1539
                    break
 
1540
            if all_index_missing is None:
 
1541
                # There were no indexes, so all search keys are 'missing'
 
1542
                missing_keys.update(keys_to_lookup)
 
1543
                keys_to_lookup = None
 
1544
            else:
 
1545
                missing_keys.update(all_index_missing)
 
1546
                keys_to_lookup.difference_update(all_index_missing)
 
1547
        return parent_map, missing_keys
1108
1548
 
1109
1549
    def key_count(self):
1110
1550
        """Return an estimate of the number of keys in this index.
1111
 
        
 
1551
 
1112
1552
        For CombinedGraphIndex this is approximated by the sum of the keys of
1113
1553
        the child indices. As child indices may have duplicate keys this can
1114
1554
        have a maximum error of the number of child indices * largest number of
1115
1555
        keys in any index.
1116
1556
        """
1117
 
        return sum((index.key_count() for index in self._indices), 0)
 
1557
        while True:
 
1558
            try:
 
1559
                return sum((index.key_count() for index in self._indices), 0)
 
1560
            except errors.NoSuchFile:
 
1561
                self._reload_or_raise()
 
1562
 
 
1563
    missing_keys = _missing_keys_from_parent_map
 
1564
 
 
1565
    def _reload_or_raise(self):
 
1566
        """We just got a NoSuchFile exception.
 
1567
 
 
1568
        Try to reload the indices, if it fails, just raise the current
 
1569
        exception.
 
1570
        """
 
1571
        if self._reload_func is None:
 
1572
            raise
 
1573
        exc_type, exc_value, exc_traceback = sys.exc_info()
 
1574
        trace.mutter('Trying to reload after getting exception: %s',
 
1575
                     exc_value)
 
1576
        if not self._reload_func():
 
1577
            # We tried to reload, but nothing changed, so we fail anyway
 
1578
            trace.mutter('_reload_func indicated nothing has changed.'
 
1579
                         ' Raising original exception.')
 
1580
            raise exc_type, exc_value, exc_traceback
 
1581
 
 
1582
    def set_sibling_indices(self, sibling_combined_graph_indices):
 
1583
        """Set the CombinedGraphIndex objects to reorder after reordering self.
 
1584
        """
 
1585
        self._sibling_indices = sibling_combined_graph_indices
1118
1586
 
1119
1587
    def validate(self):
1120
1588
        """Validate that everything in the index can be accessed."""
1121
 
        for index in self._indices:
1122
 
            index.validate()
 
1589
        while True:
 
1590
            try:
 
1591
                for index in self._indices:
 
1592
                    index.validate()
 
1593
                return
 
1594
            except errors.NoSuchFile:
 
1595
                self._reload_or_raise()
1123
1596
 
1124
1597
 
1125
1598
class InMemoryGraphIndex(GraphIndexBuilder):
1169
1642
            defined order for the result iteration - it will be in the most
1170
1643
            efficient order for the index (keys iteration order in this case).
1171
1644
        """
1172
 
        keys = set(keys)
 
1645
        # Note: See BTreeBuilder.iter_entries for an explanation of why we
 
1646
        #       aren't using set().intersection() here
 
1647
        nodes = self._nodes
 
1648
        keys = [key for key in keys if key in nodes]
1173
1649
        if self.reference_lists:
1174
 
            for key in keys.intersection(self._keys):
1175
 
                node = self._nodes[key]
 
1650
            for key in keys:
 
1651
                node = nodes[key]
1176
1652
                if not node[0]:
1177
1653
                    yield self, key, node[2], node[1]
1178
1654
        else:
1179
 
            for key in keys.intersection(self._keys):
1180
 
                node = self._nodes[key]
 
1655
            for key in keys:
 
1656
                node = nodes[key]
1181
1657
                if not node[0]:
1182
1658
                    yield self, key, node[2]
1183
1659
 
1212
1688
                    raise errors.BadIndexKey(key)
1213
1689
                node = self._nodes[key]
1214
1690
                if node[0]:
1215
 
                    continue 
 
1691
                    continue
1216
1692
                if self.reference_lists:
1217
1693
                    yield self, key, node[2], node[1]
1218
1694
                else:
1219
1695
                    yield self, key, node[2]
1220
1696
            return
 
1697
        nodes_by_key = self._get_nodes_by_key()
1221
1698
        for key in keys:
1222
1699
            # sanity check
1223
1700
            if key[0] is None:
1225
1702
            if len(key) != self._key_length:
1226
1703
                raise errors.BadIndexKey(key)
1227
1704
            # find what it refers to:
1228
 
            key_dict = self._nodes_by_key
 
1705
            key_dict = nodes_by_key
1229
1706
            elements = list(key)
1230
1707
            # find the subdict to return
1231
1708
            try:
1242
1719
                    # can't be empty or would not exist
1243
1720
                    item, value = key_dict.iteritems().next()
1244
1721
                    if type(value) == dict:
1245
 
                        # push keys 
 
1722
                        # push keys
1246
1723
                        dicts.extend(key_dict.itervalues())
1247
1724
                    else:
1248
1725
                        # yield keys
1253
1730
 
1254
1731
    def key_count(self):
1255
1732
        """Return an estimate of the number of keys in this index.
1256
 
        
 
1733
 
1257
1734
        For InMemoryGraphIndex the estimate is exact.
1258
1735
        """
1259
 
        return len(self._keys)
 
1736
        return len(self._nodes) - len(self._absent_keys)
1260
1737
 
1261
1738
    def validate(self):
1262
1739
        """In memory index's have no known corruption at the moment."""
1267
1744
 
1268
1745
    Queries against this will emit queries against the adapted Graph with the
1269
1746
    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 
 
1747
    nodes will have their keys and node references adjusted to remove the
1271
1748
    prefix. Finally, an add_nodes_callback can be supplied - when called the
1272
1749
    nodes and references being added will have prefix prepended.
1273
1750
    """
1300
1777
                    adjusted_references))
1301
1778
        except ValueError:
1302
1779
            # XXX: TODO add an explicit interface for getting the reference list
1303
 
            # status, to handle this bit of user-friendliness in the API more 
 
1780
            # status, to handle this bit of user-friendliness in the API more
1304
1781
            # explicitly.
1305
1782
            for (key, value) in nodes:
1306
1783
                translated_nodes.append((self.prefix + key, value))
1378
1855
 
1379
1856
    def key_count(self):
1380
1857
        """Return an estimate of the number of keys in this index.
1381
 
        
 
1858
 
1382
1859
        For GraphIndexPrefixAdapter this is relatively expensive - key
1383
1860
        iteration with the prefix is done.
1384
1861
        """