← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Aaron Bentley
  • Date: 2007-12-09 23:53:50 UTC
  • mto: This revision was merged to the branch mainline in revision 3133.
  • Revision ID: aaron.bentley@utoronto.ca-20071209235350-qp39yk0xzx7a4f6p
Don't use the base if not cherrypicking

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
1
 
# Copyright (C) 2007, 2008 Canonical Ltd
 
1
# Copyright (C) 2007 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
27
27
from bisect import bisect_right
28
28
from cStringIO import StringIO
29
29
import re
30
 
import sys
31
30
 
32
31
from bzrlib.lazy_import import lazy_import
33
32
lazy_import(globals(), """
36
35
from bzrlib.revision import NULL_REVISION
37
36
from bzrlib.trace import mutter
38
37
""")
39
 
from bzrlib import (
40
 
    debug,
41
 
    errors,
42
 
    symbol_versioning,
43
 
    )
 
38
from bzrlib import debug, errors
44
39
 
45
40
_HEADER_READV = (0, 200)
46
41
_OPTION_KEY_ELEMENTS = "key_elements="
53
48
_newline_null_re = re.compile('[\n\0]')
54
49
 
55
50
 
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
 
 
69
51
class GraphIndexBuilder(object):
70
52
    """A builder that can build a GraphIndex.
71
53
    
94
76
        """
95
77
        self.reference_lists = reference_lists
96
78
        self._keys = set()
97
 
        # A dict of {key: (absent, ref_lists, value)}
98
79
        self._nodes = {}
99
 
        self._nodes_by_key = None
 
80
        self._nodes_by_key = {}
100
81
        self._key_length = key_elements
101
 
        self._optimize_for_size = False
102
82
 
103
83
    def _check_key(self, key):
104
84
        """Raise BadIndexKey if key is not a valid key for this index."""
110
90
            if not element or _whitespace_re.search(element) is not None:
111
91
                raise errors.BadIndexKey(element)
112
92
 
113
 
    def _external_references(self):
114
 
        """Return references that are not present in this index.
115
 
        """
116
 
        keys = set()
117
 
        refs = set()
118
 
        # TODO: JAM 2008-11-21 This makes an assumption about how the reference
119
 
        #       lists are used. It is currently correct for pack-0.92 through
120
 
        #       1.9, which use the node references (3rd column) second
121
 
        #       reference list as the compression parent. Perhaps this should
122
 
        #       be moved into something higher up the stack, since it
123
 
        #       makes assumptions about how the index is used.
124
 
        if self.reference_lists > 1:
125
 
            for node in self.iter_all_entries():
126
 
                keys.add(node[1])
127
 
                refs.update(node[3][1])
128
 
            return refs - keys
129
 
        else:
130
 
            # If reference_lists == 0 there can be no external references, and
131
 
            # if reference_lists == 1, then there isn't a place to store the
132
 
            # compression parent
133
 
            return set()
134
 
 
135
 
    def _get_nodes_by_key(self):
136
 
        if self._nodes_by_key is None:
137
 
            nodes_by_key = {}
138
 
            if self.reference_lists:
139
 
                for key, (absent, references, value) in self._nodes.iteritems():
140
 
                    if absent:
141
 
                        continue
142
 
                    key_dict = nodes_by_key
143
 
                    for subkey in key[:-1]:
144
 
                        key_dict = key_dict.setdefault(subkey, {})
145
 
                    key_dict[key[-1]] = key, value, references
146
 
            else:
147
 
                for key, (absent, references, value) in self._nodes.iteritems():
148
 
                    if absent:
149
 
                        continue
150
 
                    key_dict = nodes_by_key
151
 
                    for subkey in key[:-1]:
152
 
                        key_dict = key_dict.setdefault(subkey, {})
153
 
                    key_dict[key[-1]] = key, value
154
 
            self._nodes_by_key = nodes_by_key
155
 
        return self._nodes_by_key
156
 
 
157
 
    def _update_nodes_by_key(self, key, value, node_refs):
158
 
        """Update the _nodes_by_key dict with a new key.
159
 
 
160
 
        For a key of (foo, bar, baz) create
161
 
        _nodes_by_key[foo][bar][baz] = key_value
162
 
        """
163
 
        if self._nodes_by_key is None:
164
 
            return
165
 
        key_dict = self._nodes_by_key
166
 
        if self.reference_lists:
167
 
            key_value = key, value, node_refs
168
 
        else:
169
 
            key_value = key, value
170
 
        for subkey in key[:-1]:
171
 
            key_dict = key_dict.setdefault(subkey, {})
172
 
        key_dict[key[-1]] = key_value
173
 
 
174
 
    def _check_key_ref_value(self, key, references, value):
175
 
        """Check that 'key' and 'references' are all valid.
176
 
 
177
 
        :param key: A key tuple. Must conform to the key interface (be a tuple,
178
 
            be of the right length, not have any whitespace or nulls in any key
179
 
            element.)
180
 
        :param references: An iterable of reference lists. Something like
181
 
            [[(ref, key)], [(ref, key), (other, key)]]
182
 
        :param value: The value associate with this key. Must not contain
183
 
            newlines or null characters.
184
 
        :return: (node_refs, absent_references)
185
 
            node_refs   basically a packed form of 'references' where all
186
 
                        iterables are tuples
187
 
            absent_references   reference keys that are not in self._nodes.
188
 
                                This may contain duplicates if the same key is
189
 
                                referenced in multiple lists.
 
93
    def add_node(self, key, value, references=()):
 
94
        """Add a node to the index.
 
95
 
 
96
        :param key: The key. keys are non-empty tuples containing
 
97
            as many whitespace-free utf8 bytestrings as the key length
 
98
            defined for this index.
 
99
        :param references: An iterable of iterables of keys. Each is a
 
100
            reference to another key.
 
101
        :param value: The value to associate with the key. It may be any
 
102
            bytes as long as it does not contain \0 or \n.
190
103
        """
191
104
        self._check_key(key)
192
105
        if _newline_null_re.search(value) is not None:
194
107
        if len(references) != self.reference_lists:
195
108
            raise errors.BadIndexValue(references)
196
109
        node_refs = []
197
 
        absent_references = []
198
110
        for reference_list in references:
199
111
            for reference in reference_list:
200
 
                # If reference *is* in self._nodes, then we know it has already
201
 
                # been checked.
 
112
                self._check_key(reference)
202
113
                if reference not in self._nodes:
203
 
                    self._check_key(reference)
204
 
                    absent_references.append(reference)
 
114
                    self._nodes[reference] = ('a', (), '')
205
115
            node_refs.append(tuple(reference_list))
206
 
        return tuple(node_refs), absent_references
207
 
 
208
 
    def add_node(self, key, value, references=()):
209
 
        """Add a node to the index.
210
 
 
211
 
        :param key: The key. keys are non-empty tuples containing
212
 
            as many whitespace-free utf8 bytestrings as the key length
213
 
            defined for this index.
214
 
        :param references: An iterable of iterables of keys. Each is a
215
 
            reference to another key.
216
 
        :param value: The value to associate with the key. It may be any
217
 
            bytes as long as it does not contain \0 or \n.
218
 
        """
219
 
        (node_refs,
220
 
         absent_references) = self._check_key_ref_value(key, references, value)
221
 
        if key in self._nodes and self._nodes[key][0] != 'a':
 
116
        if key in self._nodes and self._nodes[key][0] == '':
222
117
            raise errors.BadIndexDuplicateKey(key, self)
223
 
        for reference in absent_references:
224
 
            # There may be duplicates, but I don't think it is worth worrying
225
 
            # about
226
 
            self._nodes[reference] = ('a', (), '')
227
 
        self._nodes[key] = ('', node_refs, value)
 
118
        self._nodes[key] = ('', tuple(node_refs), value)
228
119
        self._keys.add(key)
229
 
        if self._nodes_by_key is not None and self._key_length > 1:
230
 
            self._update_nodes_by_key(key, value, node_refs)
 
120
        if self._key_length > 1:
 
121
            key_dict = self._nodes_by_key
 
122
            if self.reference_lists:
 
123
                key_value = key, value, tuple(node_refs)
 
124
            else:
 
125
                key_value = key, value
 
126
            # possibly should do this on-demand, but it seems likely it is 
 
127
            # always wanted
 
128
            # For a key of (foo, bar, baz) create
 
129
            # _nodes_by_key[foo][bar][baz] = key_value
 
130
            for subkey in key[:-1]:
 
131
                key_dict = key_dict.setdefault(subkey, {})
 
132
            key_dict[key[-1]] = key_value
231
133
 
232
134
    def finish(self):
233
135
        lines = [_SIGNATURE]
236
138
        lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
237
139
        prefix_length = sum(len(x) for x in lines)
238
140
        # references are byte offsets. To avoid having to do nasty
239
 
        # polynomial work to resolve offsets (references to later in the
 
141
        # polynomial work to resolve offsets (references to later in the 
240
142
        # file cannot be determined until all the inbetween references have
241
143
        # been calculated too) we pad the offsets with 0's to make them be
242
144
        # of consistent length. Using binary offsets would break the trivial
313
215
            raise errors.BzrError('Failed index creation. Internal error:'
314
216
                ' mismatched output length and expected length: %d %d' %
315
217
                (len(result.getvalue()), expected_bytes))
316
 
        return result
317
 
 
318
 
    def set_optimize(self, for_size=True):
319
 
        """Change how the builder tries to optimize the result.
320
 
 
321
 
        :param for_size: Tell the builder to try and make the index as small as
322
 
            possible.
323
 
        :return: None
324
 
        """
325
 
        # GraphIndexBuilder itself doesn't pay attention to the flag yet, but
326
 
        # other builders do.
327
 
        self._optimize_for_size = for_size
 
218
        return StringIO(''.join(lines))
328
219
 
329
220
 
330
221
class GraphIndex(object):
377
268
        self._keys_by_offset = None
378
269
        self._nodes_by_key = None
379
270
        self._size = size
380
 
        # The number of bytes we've read so far in trying to process this file
381
 
        self._bytes_read = 0
382
271
 
383
272
    def __eq__(self, other):
384
273
        """Equal when self and other were created with the same parameters."""
391
280
    def __ne__(self, other):
392
281
        return not self.__eq__(other)
393
282
 
394
 
    def __repr__(self):
395
 
        return "%s(%r)" % (self.__class__.__name__,
396
 
            self._transport.abspath(self._name))
397
 
 
398
 
    def _buffer_all(self, stream=None):
 
283
    def _buffer_all(self):
399
284
        """Buffer all the index data.
400
285
 
401
286
        Mutates self._nodes and self.keys_by_offset.
402
287
        """
403
 
        if self._nodes is not None:
404
 
            # We already did this
405
 
            return
406
288
        if 'index' in debug.debug_flags:
407
289
            mutter('Reading entire index %s', self._transport.abspath(self._name))
408
 
        if stream is None:
409
 
            stream = self._transport.get(self._name)
 
290
        stream = self._transport.get(self._name)
410
291
        self._read_prefix(stream)
411
292
        self._expected_elements = 3 + self._key_length
412
293
        line_count = 0
414
295
        self._keys_by_offset = {}
415
296
        # ready-to-return key:value or key:value, node_ref_lists
416
297
        self._nodes = {}
417
 
        self._nodes_by_key = None
 
298
        self._nodes_by_key = {}
418
299
        trailers = 0
419
300
        pos = stream.tell()
420
301
        lines = stream.read().split('\n')
429
310
            else:
430
311
                node_value = value
431
312
            self._nodes[key] = node_value
 
313
            if self._key_length > 1:
 
314
                subkey = list(reversed(key[:-1]))
 
315
                key_dict = self._nodes_by_key
 
316
                if self.node_ref_lists:
 
317
                    key_value = key, node_value[0], node_value[1]
 
318
                else:
 
319
                    key_value = key, node_value
 
320
                # possibly should do this on-demand, but it seems likely it is 
 
321
                # always wanted
 
322
                # For a key of (foo, bar, baz) create
 
323
                # _nodes_by_key[foo][bar][baz] = key_value
 
324
                for subkey in key[:-1]:
 
325
                    key_dict = key_dict.setdefault(subkey, {})
 
326
                key_dict[key[-1]] = key_value
432
327
        # cache the keys for quick set intersections
433
328
        self._keys = set(self._nodes)
434
329
        if trailers != 1:
435
330
            # there must be one line - the empty trailer line.
436
331
            raise errors.BadIndexData(self)
437
332
 
438
 
    def _get_nodes_by_key(self):
439
 
        if self._nodes_by_key is None:
440
 
            nodes_by_key = {}
441
 
            if self.node_ref_lists:
442
 
                for key, (value, references) in self._nodes.iteritems():
443
 
                    key_dict = nodes_by_key
444
 
                    for subkey in key[:-1]:
445
 
                        key_dict = key_dict.setdefault(subkey, {})
446
 
                    key_dict[key[-1]] = key, value, references
447
 
            else:
448
 
                for key, value in self._nodes.iteritems():
449
 
                    key_dict = nodes_by_key
450
 
                    for subkey in key[:-1]:
451
 
                        key_dict = key_dict.setdefault(subkey, {})
452
 
                    key_dict[key[-1]] = key, value
453
 
            self._nodes_by_key = nodes_by_key
454
 
        return self._nodes_by_key
455
 
 
456
333
    def iter_all_entries(self):
457
334
        """Iterate over all keys within the index.
458
335
 
583
460
            keys supplied. No additional keys will be returned, and every
584
461
            key supplied that is in the index will be returned.
585
462
        """
 
463
        # PERFORMANCE TODO: parse and bisect all remaining data at some
 
464
        # threshold of total-index processing/get calling layers that expect to
 
465
        # read the entire index to use the iter_all_entries  method instead.
586
466
        keys = set(keys)
587
467
        if not keys:
588
468
            return []
589
469
        if self._size is None and self._nodes is None:
590
470
            self._buffer_all()
591
 
 
592
 
        # We fit about 20 keys per minimum-read (4K), so if we are looking for
593
 
        # more than 1/20th of the index its likely (assuming homogenous key
594
 
        # spread) that we'll read the entire index. If we're going to do that,
595
 
        # buffer the whole thing. A better analysis might take key spread into
596
 
        # account - but B+Tree indices are better anyway.
597
 
        # We could look at all data read, and use a threshold there, which will
598
 
        # trigger on ancestry walks, but that is not yet fully mapped out.
599
 
        if self._nodes is None and len(keys) * 20 > self.key_count():
600
 
            self._buffer_all()
601
471
        if self._nodes is not None:
602
472
            return self._iter_entries_from_total_buffer(keys)
603
473
        else:
645
515
                else:
646
516
                    yield self, key, self._nodes[key]
647
517
            return
648
 
        nodes_by_key = self._get_nodes_by_key()
649
518
        for key in keys:
650
519
            # sanity check
651
520
            if key[0] is None:
653
522
            if len(key) != self._key_length:
654
523
                raise errors.BadIndexKey(key)
655
524
            # find what it refers to:
656
 
            key_dict = nodes_by_key
 
525
            key_dict = self._nodes_by_key
657
526
            elements = list(key)
658
527
            # find the subdict whose contents should be returned.
659
528
            try:
746
615
        if self._bisect_nodes is None:
747
616
            readv_ranges.append(_HEADER_READV)
748
617
        self._read_and_parse(readv_ranges)
749
 
        result = []
750
 
        if self._nodes is not None:
751
 
            # _read_and_parse triggered a _buffer_all because we requested the
752
 
            # whole data range
753
 
            for location, key in location_keys:
754
 
                if key not in self._nodes: # not present
755
 
                    result.append(((location, key), False))
756
 
                elif self.node_ref_lists:
757
 
                    value, refs = self._nodes[key]
758
 
                    result.append(((location, key),
759
 
                        (self, key, value, refs)))
760
 
                else:
761
 
                    result.append(((location, key),
762
 
                        (self, key, self._nodes[key])))
763
 
            return result
764
618
        # generate results:
765
619
        #  - figure out <, >, missing, present
766
620
        #  - result present references so we can return them.
 
621
        result = []
767
622
        # keys that we cannot answer until we resolve references
768
623
        pending_references = []
769
624
        pending_locations = set()
819
674
            if length > 0:
820
675
                readv_ranges.append((location, length))
821
676
        self._read_and_parse(readv_ranges)
822
 
        if self._nodes is not None:
823
 
            # The _read_and_parse triggered a _buffer_all, grab the data and
824
 
            # return it
825
 
            for location, key in pending_references:
826
 
                value, refs = self._nodes[key]
827
 
                result.append(((location, key), (self, key, value, refs)))
828
 
            return result
829
677
        for location, key in pending_references:
830
678
            # answer key references we had to look-up-late.
 
679
            index = self._parsed_key_index(key)
831
680
            value, refs = self._bisect_nodes[key]
832
681
            result.append(((location, key), (self, key,
833
682
                value, self._resolve_references(refs))))
977
826
                trim_start = data.find('\n') + 1
978
827
            else:
979
828
                trim_start = data.find('\n', trim_start) + 1
980
 
            if not (trim_start != 0):
981
 
                raise AssertionError('no \n was present')
 
829
            assert trim_start != 0, 'no \n was present'
982
830
            # print 'removing start', offset, trim_start, repr(data[:trim_start])
983
831
        if not end_adjacent:
984
832
            # work around python bug in rfind
986
834
                trim_end = data.rfind('\n') + 1
987
835
            else:
988
836
                trim_end = data.rfind('\n', None, trim_end) + 1
989
 
            if not (trim_end != 0):
990
 
                raise AssertionError('no \n was present')
 
837
            assert trim_end != 0, 'no \n was present'
991
838
            # print 'removing end', offset, trim_end, repr(data[trim_end:])
992
839
        # adjust offset and data to the parseable data.
993
840
        trimmed_data = data[trim_start:trim_end]
994
 
        if not (trimmed_data):
995
 
            raise AssertionError('read unneeded data [%d:%d] from [%d:%d]' 
996
 
                % (trim_start, trim_end, offset, offset + len(data)))
 
841
        assert trimmed_data, 'read unneeded data [%d:%d] from [%d:%d]' % (
 
842
            trim_start, trim_end, offset, offset + len(data))
997
843
        if trim_start:
998
844
            offset += trim_start
999
845
        # print "parsing", repr(trimmed_data)
1017
863
            if line == '':
1018
864
                # must be at the end
1019
865
                if self._size:
1020
 
                    if not (self._size == pos + 1):
1021
 
                        raise AssertionError("%s %s" % (self._size, pos))
 
866
                    assert self._size == pos + 1, "%s %s" % (self._size, pos)
1022
867
                trailers += 1
1023
868
                continue
1024
869
            elements = line.split('\0')
1025
870
            if len(elements) != self._expected_elements:
1026
871
                raise errors.BadIndexData(self)
1027
 
            # keys are tuples. Each element is a string that may occur many
1028
 
            # times, so we intern them to save space. AB, RC, 200807
1029
 
            key = tuple([intern(element) for element in elements[:self._key_length]])
 
872
            # keys are tuples
 
873
            key = tuple(elements[:self._key_length])
1030
874
            if first_key is None:
1031
875
                first_key = key
1032
876
            absent, references, value = elements[-3:]
1103
947
 
1104
948
        :param readv_ranges: A prepared readv range list.
1105
949
        """
1106
 
        if not readv_ranges:
1107
 
            return
1108
 
        if self._nodes is None and self._bytes_read * 2 >= self._size:
1109
 
            # We've already read more than 50% of the file and we are about to
1110
 
            # request more data, just _buffer_all() and be done
1111
 
            self._buffer_all()
1112
 
            return
1113
 
 
1114
 
        readv_data = self._transport.readv(self._name, readv_ranges, True,
1115
 
            self._size)
1116
 
        # parse
1117
 
        for offset, data in readv_data:
1118
 
            self._bytes_read += len(data)
1119
 
            if offset == 0 and len(data) == self._size:
1120
 
                # We read the whole range, most likely because the
1121
 
                # Transport upcast our readv ranges into one long request
1122
 
                # for enough total data to grab the whole index.
1123
 
                self._buffer_all(StringIO(data))
1124
 
                return
1125
 
            if self._bisect_nodes is None:
1126
 
                # this must be the start
1127
 
                if not (offset == 0):
1128
 
                    raise AssertionError()
1129
 
                offset, data = self._parse_header_from_bytes(data)
1130
 
            # print readv_ranges, "[%d:%d]" % (offset, offset + len(data))
1131
 
            self._parse_region(offset, data)
 
950
        if readv_ranges:
 
951
            readv_data = self._transport.readv(self._name, readv_ranges, True,
 
952
                self._size)
 
953
            # parse
 
954
            for offset, data in readv_data:
 
955
                if self._bisect_nodes is None:
 
956
                    # this must be the start
 
957
                    assert offset == 0
 
958
                    offset, data = self._parse_header_from_bytes(data)
 
959
                # print readv_ranges, "[%d:%d]" % (offset, offset + len(data))
 
960
                self._parse_region(offset, data)
1132
961
 
1133
962
    def _signature(self):
1134
963
        """The file signature for this index type."""
1154
983
    in the index list.
1155
984
    """
1156
985
 
1157
 
    def __init__(self, indices, reload_func=None):
 
986
    def __init__(self, indices):
1158
987
        """Create a CombinedGraphIndex backed by indices.
1159
988
 
1160
989
        :param indices: An ordered list of indices to query for data.
1161
 
        :param reload_func: A function to call if we find we are missing an
1162
 
            index. Should have the form reload_func() => True/False to indicate
1163
 
            if reloading actually changed anything.
1164
990
        """
1165
991
        self._indices = indices
1166
 
        self._reload_func = reload_func
1167
992
 
1168
993
    def __repr__(self):
1169
994
        return "%s(%s)" % (
1170
995
                self.__class__.__name__,
1171
996
                ', '.join(map(repr, self._indices)))
1172
997
 
1173
 
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
1174
998
    def get_parents(self, revision_ids):
1175
 
        """See graph._StackedParentsProvider.get_parents.
 
999
        """See StackedParentsProvider.get_parents.
1176
1000
        
1177
1001
        This implementation thunks the graph.Graph.get_parents api across to
1178
1002
        GraphIndex.
1184
1008
             * (NULL_REVISION,) when the key has no parents.
1185
1009
             * (parent_key, parent_key...) otherwise.
1186
1010
        """
1187
 
        parent_map = self.get_parent_map(revision_ids)
1188
 
        return [parent_map.get(r, None) for r in revision_ids]
1189
 
 
1190
 
    def get_parent_map(self, keys):
1191
 
        """See graph._StackedParentsProvider.get_parent_map"""
1192
 
        search_keys = set(keys)
1193
 
        if NULL_REVISION in search_keys:
1194
 
            search_keys.discard(NULL_REVISION)
1195
 
            found_parents = {NULL_REVISION:[]}
1196
 
        else:
1197
 
            found_parents = {}
 
1011
        search_keys = set(revision_ids)
 
1012
        search_keys.discard(NULL_REVISION)
 
1013
        found_parents = {NULL_REVISION:[]}
1198
1014
        for index, key, value, refs in self.iter_entries(search_keys):
1199
1015
            parents = refs[0]
1200
1016
            if not parents:
1201
1017
                parents = (NULL_REVISION,)
1202
1018
            found_parents[key] = parents
1203
 
        return found_parents
1204
 
 
1205
 
    has_key = _has_key_from_parent_map
 
1019
        result = []
 
1020
        for key in revision_ids:
 
1021
            try:
 
1022
                result.append(found_parents[key])
 
1023
            except KeyError:
 
1024
                result.append(None)
 
1025
        return result
1206
1026
 
1207
1027
    def insert_index(self, pos, index):
1208
1028
        """Insert a new index in the list of indices to query.
1223
1043
            the most efficient order for the index.
1224
1044
        """
1225
1045
        seen_keys = set()
1226
 
        while True:
1227
 
            try:
1228
 
                for index in self._indices:
1229
 
                    for node in index.iter_all_entries():
1230
 
                        if node[1] not in seen_keys:
1231
 
                            yield node
1232
 
                            seen_keys.add(node[1])
1233
 
                return
1234
 
            except errors.NoSuchFile:
1235
 
                self._reload_or_raise()
 
1046
        for index in self._indices:
 
1047
            for node in index.iter_all_entries():
 
1048
                if node[1] not in seen_keys:
 
1049
                    yield node
 
1050
                    seen_keys.add(node[1])
1236
1051
 
1237
1052
    def iter_entries(self, keys):
1238
1053
        """Iterate over keys within the index.
1246
1061
            efficient order for the index.
1247
1062
        """
1248
1063
        keys = set(keys)
1249
 
        while True:
1250
 
            try:
1251
 
                for index in self._indices:
1252
 
                    if not keys:
1253
 
                        return
1254
 
                    for node in index.iter_entries(keys):
1255
 
                        keys.remove(node[1])
1256
 
                        yield node
 
1064
        for index in self._indices:
 
1065
            if not keys:
1257
1066
                return
1258
 
            except errors.NoSuchFile:
1259
 
                self._reload_or_raise()
 
1067
            for node in index.iter_entries(keys):
 
1068
                keys.remove(node[1])
 
1069
                yield node
1260
1070
 
1261
1071
    def iter_entries_prefix(self, keys):
1262
1072
        """Iterate over keys within the index using prefix matching.
1282
1092
        if not keys:
1283
1093
            return
1284
1094
        seen_keys = set()
1285
 
        while True:
1286
 
            try:
1287
 
                for index in self._indices:
1288
 
                    for node in index.iter_entries_prefix(keys):
1289
 
                        if node[1] in seen_keys:
1290
 
                            continue
1291
 
                        seen_keys.add(node[1])
1292
 
                        yield node
1293
 
                return
1294
 
            except errors.NoSuchFile:
1295
 
                self._reload_or_raise()
 
1095
        for index in self._indices:
 
1096
            for node in index.iter_entries_prefix(keys):
 
1097
                if node[1] in seen_keys:
 
1098
                    continue
 
1099
                seen_keys.add(node[1])
 
1100
                yield node
1296
1101
 
1297
1102
    def key_count(self):
1298
1103
        """Return an estimate of the number of keys in this index.
1299
 
 
 
1104
        
1300
1105
        For CombinedGraphIndex this is approximated by the sum of the keys of
1301
1106
        the child indices. As child indices may have duplicate keys this can
1302
1107
        have a maximum error of the number of child indices * largest number of
1303
1108
        keys in any index.
1304
1109
        """
1305
 
        while True:
1306
 
            try:
1307
 
                return sum((index.key_count() for index in self._indices), 0)
1308
 
            except errors.NoSuchFile:
1309
 
                self._reload_or_raise()
1310
 
 
1311
 
    missing_keys = _missing_keys_from_parent_map
1312
 
 
1313
 
    def _reload_or_raise(self):
1314
 
        """We just got a NoSuchFile exception.
1315
 
 
1316
 
        Try to reload the indices, if it fails, just raise the current
1317
 
        exception.
1318
 
        """
1319
 
        if self._reload_func is None:
1320
 
            raise
1321
 
        exc_type, exc_value, exc_traceback = sys.exc_info()
1322
 
        trace.mutter('Trying to reload after getting exception: %s',
1323
 
                     exc_value)
1324
 
        if not self._reload_func():
1325
 
            # We tried to reload, but nothing changed, so we fail anyway
1326
 
            trace.mutter('_reload_func indicated nothing has changed.'
1327
 
                         ' Raising original exception.')
1328
 
            raise exc_type, exc_value, exc_traceback
 
1110
        return sum((index.key_count() for index in self._indices), 0)
1329
1111
 
1330
1112
    def validate(self):
1331
1113
        """Validate that everything in the index can be accessed."""
1332
 
        while True:
1333
 
            try:
1334
 
                for index in self._indices:
1335
 
                    index.validate()
1336
 
                return
1337
 
            except errors.NoSuchFile:
1338
 
                self._reload_or_raise()
 
1114
        for index in self._indices:
 
1115
            index.validate()
1339
1116
 
1340
1117
 
1341
1118
class InMemoryGraphIndex(GraphIndexBuilder):
1434
1211
                else:
1435
1212
                    yield self, key, node[2]
1436
1213
            return
1437
 
        nodes_by_key = self._get_nodes_by_key()
1438
1214
        for key in keys:
1439
1215
            # sanity check
1440
1216
            if key[0] is None:
1442
1218
            if len(key) != self._key_length:
1443
1219
                raise errors.BadIndexKey(key)
1444
1220
            # find what it refers to:
1445
 
            key_dict = nodes_by_key
 
1221
            key_dict = self._nodes_by_key
1446
1222
            elements = list(key)
1447
1223
            # find the subdict to return
1448
1224
            try: