← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Sabin Iacob
  • Date: 2009-03-23 14:59:43 UTC
  • mto: (4189.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 4193.
  • Revision ID: iacobs@m0n5t3r.info-20090323145943-3s3p1px5q1rkh2e5
update FSF mailing address

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, 2008 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(), """
52
53
_newline_null_re = re.compile('[\n\0]')
53
54
 
54
55
 
 
56
def _has_key_from_parent_map(self, key):
 
57
    """Check if this index has one key.
 
58
 
 
59
    If it's possible to check for multiple keys at once through
 
60
    calling get_parent_map that should be faster.
 
61
    """
 
62
    return (key in self.get_parent_map([key]))
 
63
 
 
64
 
 
65
def _missing_keys_from_parent_map(self, keys):
 
66
    return set(keys) - set(self.get_parent_map(keys))
 
67
 
 
68
 
55
69
class GraphIndexBuilder(object):
56
70
    """A builder that can build a GraphIndex.
57
 
    
 
71
 
58
72
    The resulting graph has the structure:
59
 
    
 
73
 
60
74
    _SIGNATURE OPTIONS NODES NEWLINE
61
75
    _SIGNATURE     := 'Bazaar Graph Index 1' NEWLINE
62
76
    OPTIONS        := 'node_ref_lists=' DIGITS NEWLINE
80
94
        """
81
95
        self.reference_lists = reference_lists
82
96
        self._keys = set()
 
97
        # A dict of {key: (absent, ref_lists, value)}
83
98
        self._nodes = {}
84
 
        self._nodes_by_key = {}
 
99
        self._nodes_by_key = None
85
100
        self._key_length = key_elements
 
101
        self._optimize_for_size = False
86
102
 
87
103
    def _check_key(self, key):
88
104
        """Raise BadIndexKey if key is not a valid key for this index."""
94
110
            if not element or _whitespace_re.search(element) is not None:
95
111
                raise errors.BadIndexKey(element)
96
112
 
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.
 
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.
107
190
        """
108
191
        self._check_key(key)
109
192
        if _newline_null_re.search(value) is not None:
111
194
        if len(references) != self.reference_lists:
112
195
            raise errors.BadIndexValue(references)
113
196
        node_refs = []
 
197
        absent_references = []
114
198
        for reference_list in references:
115
199
            for reference in reference_list:
116
 
                self._check_key(reference)
 
200
                # If reference *is* in self._nodes, then we know it has already
 
201
                # been checked.
117
202
                if reference not in self._nodes:
118
 
                    self._nodes[reference] = ('a', (), '')
 
203
                    self._check_key(reference)
 
204
                    absent_references.append(reference)
119
205
            node_refs.append(tuple(reference_list))
120
 
        if key in self._nodes and self._nodes[key][0] == '':
 
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':
121
222
            raise errors.BadIndexDuplicateKey(key, self)
122
 
        self._nodes[key] = ('', tuple(node_refs), value)
 
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)
123
228
        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
 
229
        if self._nodes_by_key is not None and self._key_length > 1:
 
230
            self._update_nodes_by_key(key, value, node_refs)
137
231
 
138
232
    def finish(self):
139
233
        lines = [_SIGNATURE]
142
236
        lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
143
237
        prefix_length = sum(len(x) for x in lines)
144
238
        # references are byte offsets. To avoid having to do nasty
145
 
        # polynomial work to resolve offsets (references to later in the 
 
239
        # polynomial work to resolve offsets (references to later in the
146
240
        # file cannot be determined until all the inbetween references have
147
241
        # been calculated too) we pad the offsets with 0's to make them be
148
242
        # of consistent length. Using binary offsets would break the trivial
152
246
        # one to pad all the data with reference-length and determine entry
153
247
        # addresses.
154
248
        # One to serialise.
155
 
        
 
249
 
156
250
        # forward sorted by key. In future we may consider topological sorting,
157
251
        # at the cost of table scans for direct lookup, or a second index for
158
252
        # direct lookup
219
313
            raise errors.BzrError('Failed index creation. Internal error:'
220
314
                ' mismatched output length and expected length: %d %d' %
221
315
                (len(result.getvalue()), expected_bytes))
222
 
        return StringIO(''.join(lines))
 
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
223
328
 
224
329
 
225
330
class GraphIndex(object):
226
331
    """An index for data with embedded graphs.
227
 
 
 
332
 
228
333
    The index maps keys to a list of key reference lists, and a value.
229
334
    Each node has the same number of key reference lists. Each key reference
230
335
    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 
 
336
    terminated string without any newlines. The storage of the index is
232
337
    hidden in the interface: keys and key references are always tuples of
233
338
    bytestrings, never the internal representation (e.g. dictionary offsets).
234
339
 
272
377
        self._keys_by_offset = None
273
378
        self._nodes_by_key = None
274
379
        self._size = size
 
380
        # The number of bytes we've read so far in trying to process this file
 
381
        self._bytes_read = 0
275
382
 
276
383
    def __eq__(self, other):
277
384
        """Equal when self and other were created with the same parameters."""
284
391
    def __ne__(self, other):
285
392
        return not self.__eq__(other)
286
393
 
287
 
    def _buffer_all(self):
 
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):
288
399
        """Buffer all the index data.
289
400
 
290
401
        Mutates self._nodes and self.keys_by_offset.
291
402
        """
 
403
        if self._nodes is not None:
 
404
            # We already did this
 
405
            return
292
406
        if 'index' in debug.debug_flags:
293
407
            mutter('Reading entire index %s', self._transport.abspath(self._name))
294
 
        stream = self._transport.get(self._name)
 
408
        if stream is None:
 
409
            stream = self._transport.get(self._name)
295
410
        self._read_prefix(stream)
296
411
        self._expected_elements = 3 + self._key_length
297
412
        line_count = 0
299
414
        self._keys_by_offset = {}
300
415
        # ready-to-return key:value or key:value, node_ref_lists
301
416
        self._nodes = {}
302
 
        self._nodes_by_key = {}
 
417
        self._nodes_by_key = None
303
418
        trailers = 0
304
419
        pos = stream.tell()
305
420
        lines = stream.read().split('\n')
314
429
            else:
315
430
                node_value = value
316
431
            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
432
        # cache the keys for quick set intersections
332
433
        self._keys = set(self._nodes)
333
434
        if trailers != 1:
334
435
            # there must be one line - the empty trailer line.
335
436
            raise errors.BadIndexData(self)
336
437
 
 
438
    def external_references(self, ref_list_num):
 
439
        """Return references that are not present in this index.
 
440
        """
 
441
        self._buffer_all()
 
442
        if ref_list_num + 1 > self.node_ref_lists:
 
443
            raise ValueError('No ref list %d, index has %d ref lists'
 
444
                % (ref_list_num, self.node_ref_lists))
 
445
        refs = set()
 
446
        for key, (value, ref_lists) in self._nodes.iteritems():
 
447
            ref_list = ref_lists[ref_list_num]
 
448
            refs.update(ref_list)
 
449
        return refs - self._keys
 
450
 
 
451
    def _get_nodes_by_key(self):
 
452
        if self._nodes_by_key is None:
 
453
            nodes_by_key = {}
 
454
            if self.node_ref_lists:
 
455
                for key, (value, references) in self._nodes.iteritems():
 
456
                    key_dict = nodes_by_key
 
457
                    for subkey in key[:-1]:
 
458
                        key_dict = key_dict.setdefault(subkey, {})
 
459
                    key_dict[key[-1]] = key, value, references
 
460
            else:
 
461
                for key, value in self._nodes.iteritems():
 
462
                    key_dict = nodes_by_key
 
463
                    for subkey in key[:-1]:
 
464
                        key_dict = key_dict.setdefault(subkey, {})
 
465
                    key_dict[key[-1]] = key, value
 
466
            self._nodes_by_key = nodes_by_key
 
467
        return self._nodes_by_key
 
468
 
337
469
    def iter_all_entries(self):
338
470
        """Iterate over all keys within the index.
339
471
 
383
515
 
384
516
    def _resolve_references(self, references):
385
517
        """Return the resolved key references for references.
386
 
        
 
518
 
387
519
        References are resolved by looking up the location of the key in the
388
520
        _keys_by_offset map and substituting the key name, preserving ordering.
389
521
 
390
 
        :param references: An iterable of iterables of key locations. e.g. 
 
522
        :param references: An iterable of iterables of key locations. e.g.
391
523
            [[123, 456], [123]]
392
524
        :return: A tuple of tuples of keys.
393
525
        """
464
596
            keys supplied. No additional keys will be returned, and every
465
597
            key supplied that is in the index will be returned.
466
598
        """
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
599
        keys = set(keys)
471
600
        if not keys:
472
601
            return []
473
602
        if self._size is None and self._nodes is None:
474
603
            self._buffer_all()
 
604
 
 
605
        # We fit about 20 keys per minimum-read (4K), so if we are looking for
 
606
        # more than 1/20th of the index its likely (assuming homogenous key
 
607
        # spread) that we'll read the entire index. If we're going to do that,
 
608
        # buffer the whole thing. A better analysis might take key spread into
 
609
        # account - but B+Tree indices are better anyway.
 
610
        # We could look at all data read, and use a threshold there, which will
 
611
        # trigger on ancestry walks, but that is not yet fully mapped out.
 
612
        if self._nodes is None and len(keys) * 20 > self.key_count():
 
613
            self._buffer_all()
475
614
        if self._nodes is not None:
476
615
            return self._iter_entries_from_total_buffer(keys)
477
616
        else:
519
658
                else:
520
659
                    yield self, key, self._nodes[key]
521
660
            return
 
661
        nodes_by_key = self._get_nodes_by_key()
522
662
        for key in keys:
523
663
            # sanity check
524
664
            if key[0] is None:
526
666
            if len(key) != self._key_length:
527
667
                raise errors.BadIndexKey(key)
528
668
            # find what it refers to:
529
 
            key_dict = self._nodes_by_key
 
669
            key_dict = nodes_by_key
530
670
            elements = list(key)
531
671
            # find the subdict whose contents should be returned.
532
672
            try:
543
683
                    # can't be empty or would not exist
544
684
                    item, value = key_dict.iteritems().next()
545
685
                    if type(value) == dict:
546
 
                        # push keys 
 
686
                        # push keys
547
687
                        dicts.extend(key_dict.itervalues())
548
688
                    else:
549
689
                        # yield keys
557
697
 
558
698
    def key_count(self):
559
699
        """Return an estimate of the number of keys in this index.
560
 
        
 
700
 
561
701
        For GraphIndex the estimate is exact.
562
702
        """
563
703
        if self._key_count is None:
579
719
        # Possible improvements:
580
720
        #  - only bisect lookup each key once
581
721
        #  - sort the keys first, and use that to reduce the bisection window
582
 
        # ----- 
 
722
        # -----
583
723
        # this progresses in three parts:
584
724
        # read data
585
725
        # parse it
594
734
                # We have the key parsed.
595
735
                continue
596
736
            index = self._parsed_key_index(key)
597
 
            if (len(self._parsed_key_map) and 
 
737
            if (len(self._parsed_key_map) and
598
738
                self._parsed_key_map[index][0] <= key and
599
739
                (self._parsed_key_map[index][1] >= key or
600
740
                 # end of the file has been parsed
604
744
                continue
605
745
            # - if we have examined this part of the file already - yes
606
746
            index = self._parsed_byte_index(location)
607
 
            if (len(self._parsed_byte_map) and 
 
747
            if (len(self._parsed_byte_map) and
608
748
                self._parsed_byte_map[index][0] <= location and
609
749
                self._parsed_byte_map[index][1] > location):
610
750
                # the byte region has been parsed, so no read is needed.
619
759
        if self._bisect_nodes is None:
620
760
            readv_ranges.append(_HEADER_READV)
621
761
        self._read_and_parse(readv_ranges)
 
762
        result = []
 
763
        if self._nodes is not None:
 
764
            # _read_and_parse triggered a _buffer_all because we requested the
 
765
            # whole data range
 
766
            for location, key in location_keys:
 
767
                if key not in self._nodes: # not present
 
768
                    result.append(((location, key), False))
 
769
                elif self.node_ref_lists:
 
770
                    value, refs = self._nodes[key]
 
771
                    result.append(((location, key),
 
772
                        (self, key, value, refs)))
 
773
                else:
 
774
                    result.append(((location, key),
 
775
                        (self, key, self._nodes[key])))
 
776
            return result
622
777
        # generate results:
623
778
        #  - figure out <, >, missing, present
624
779
        #  - result present references so we can return them.
625
 
        result = []
626
780
        # keys that we cannot answer until we resolve references
627
781
        pending_references = []
628
782
        pending_locations = set()
678
832
            if length > 0:
679
833
                readv_ranges.append((location, length))
680
834
        self._read_and_parse(readv_ranges)
 
835
        if self._nodes is not None:
 
836
            # The _read_and_parse triggered a _buffer_all, grab the data and
 
837
            # return it
 
838
            for location, key in pending_references:
 
839
                value, refs = self._nodes[key]
 
840
                result.append(((location, key), (self, key, value, refs)))
 
841
            return result
681
842
        for location, key in pending_references:
682
843
            # answer key references we had to look-up-late.
683
 
            index = self._parsed_key_index(key)
684
844
            value, refs = self._bisect_nodes[key]
685
845
            result.append(((location, key), (self, key,
686
846
                value, self._resolve_references(refs))))
830
990
                trim_start = data.find('\n') + 1
831
991
            else:
832
992
                trim_start = data.find('\n', trim_start) + 1
833
 
            assert trim_start != 0, 'no \n was present'
 
993
            if not (trim_start != 0):
 
994
                raise AssertionError('no \n was present')
834
995
            # print 'removing start', offset, trim_start, repr(data[:trim_start])
835
996
        if not end_adjacent:
836
997
            # work around python bug in rfind
838
999
                trim_end = data.rfind('\n') + 1
839
1000
            else:
840
1001
                trim_end = data.rfind('\n', None, trim_end) + 1
841
 
            assert trim_end != 0, 'no \n was present'
 
1002
            if not (trim_end != 0):
 
1003
                raise AssertionError('no \n was present')
842
1004
            # print 'removing end', offset, trim_end, repr(data[trim_end:])
843
1005
        # adjust offset and data to the parseable data.
844
1006
        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))
 
1007
        if not (trimmed_data):
 
1008
            raise AssertionError('read unneeded data [%d:%d] from [%d:%d]'
 
1009
                % (trim_start, trim_end, offset, offset + len(data)))
847
1010
        if trim_start:
848
1011
            offset += trim_start
849
1012
        # print "parsing", repr(trimmed_data)
867
1030
            if line == '':
868
1031
                # must be at the end
869
1032
                if self._size:
870
 
                    assert self._size == pos + 1, "%s %s" % (self._size, pos)
 
1033
                    if not (self._size == pos + 1):
 
1034
                        raise AssertionError("%s %s" % (self._size, pos))
871
1035
                trailers += 1
872
1036
                continue
873
1037
            elements = line.split('\0')
874
1038
            if len(elements) != self._expected_elements:
875
1039
                raise errors.BadIndexData(self)
876
 
            # keys are tuples
877
 
            key = tuple(elements[:self._key_length])
 
1040
            # keys are tuples. Each element is a string that may occur many
 
1041
            # times, so we intern them to save space. AB, RC, 200807
 
1042
            key = tuple([intern(element) for element in elements[:self._key_length]])
878
1043
            if first_key is None:
879
1044
                first_key = key
880
1045
            absent, references, value = elements[-3:]
951
1116
 
952
1117
        :param readv_ranges: A prepared readv range list.
953
1118
        """
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)
 
1119
        if not readv_ranges:
 
1120
            return
 
1121
        if self._nodes is None and self._bytes_read * 2 >= self._size:
 
1122
            # We've already read more than 50% of the file and we are about to
 
1123
            # request more data, just _buffer_all() and be done
 
1124
            self._buffer_all()
 
1125
            return
 
1126
 
 
1127
        readv_data = self._transport.readv(self._name, readv_ranges, True,
 
1128
            self._size)
 
1129
        # parse
 
1130
        for offset, data in readv_data:
 
1131
            self._bytes_read += len(data)
 
1132
            if offset == 0 and len(data) == self._size:
 
1133
                # We read the whole range, most likely because the
 
1134
                # Transport upcast our readv ranges into one long request
 
1135
                # for enough total data to grab the whole index.
 
1136
                self._buffer_all(StringIO(data))
 
1137
                return
 
1138
            if self._bisect_nodes is None:
 
1139
                # this must be the start
 
1140
                if not (offset == 0):
 
1141
                    raise AssertionError()
 
1142
                offset, data = self._parse_header_from_bytes(data)
 
1143
            # print readv_ranges, "[%d:%d]" % (offset, offset + len(data))
 
1144
            self._parse_region(offset, data)
965
1145
 
966
1146
    def _signature(self):
967
1147
        """The file signature for this index type."""
976
1156
 
977
1157
class CombinedGraphIndex(object):
978
1158
    """A GraphIndex made up from smaller GraphIndices.
979
 
    
 
1159
 
980
1160
    The backing indices must implement GraphIndex, and are presumed to be
981
1161
    static data.
982
1162
 
987
1167
    in the index list.
988
1168
    """
989
1169
 
990
 
    def __init__(self, indices):
 
1170
    def __init__(self, indices, reload_func=None):
991
1171
        """Create a CombinedGraphIndex backed by indices.
992
1172
 
993
1173
        :param indices: An ordered list of indices to query for data.
 
1174
        :param reload_func: A function to call if we find we are missing an
 
1175
            index. Should have the form reload_func() => True/False to indicate
 
1176
            if reloading actually changed anything.
994
1177
        """
995
1178
        self._indices = indices
 
1179
        self._reload_func = reload_func
996
1180
 
997
1181
    def __repr__(self):
998
1182
        return "%s(%s)" % (
1002
1186
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
1003
1187
    def get_parents(self, revision_ids):
1004
1188
        """See graph._StackedParentsProvider.get_parents.
1005
 
        
 
1189
 
1006
1190
        This implementation thunks the graph.Graph.get_parents api across to
1007
1191
        GraphIndex.
1008
1192
 
1031
1215
            found_parents[key] = parents
1032
1216
        return found_parents
1033
1217
 
 
1218
    has_key = _has_key_from_parent_map
 
1219
 
1034
1220
    def insert_index(self, pos, index):
1035
1221
        """Insert a new index in the list of indices to query.
1036
1222
 
1050
1236
            the most efficient order for the index.
1051
1237
        """
1052
1238
        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])
 
1239
        while True:
 
1240
            try:
 
1241
                for index in self._indices:
 
1242
                    for node in index.iter_all_entries():
 
1243
                        if node[1] not in seen_keys:
 
1244
                            yield node
 
1245
                            seen_keys.add(node[1])
 
1246
                return
 
1247
            except errors.NoSuchFile:
 
1248
                self._reload_or_raise()
1058
1249
 
1059
1250
    def iter_entries(self, keys):
1060
1251
        """Iterate over keys within the index.
1068
1259
            efficient order for the index.
1069
1260
        """
1070
1261
        keys = set(keys)
1071
 
        for index in self._indices:
1072
 
            if not keys:
 
1262
        while True:
 
1263
            try:
 
1264
                for index in self._indices:
 
1265
                    if not keys:
 
1266
                        return
 
1267
                    for node in index.iter_entries(keys):
 
1268
                        keys.remove(node[1])
 
1269
                        yield node
1073
1270
                return
1074
 
            for node in index.iter_entries(keys):
1075
 
                keys.remove(node[1])
1076
 
                yield node
 
1271
            except errors.NoSuchFile:
 
1272
                self._reload_or_raise()
1077
1273
 
1078
1274
    def iter_entries_prefix(self, keys):
1079
1275
        """Iterate over keys within the index using prefix matching.
1099
1295
        if not keys:
1100
1296
            return
1101
1297
        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
 
1298
        while True:
 
1299
            try:
 
1300
                for index in self._indices:
 
1301
                    for node in index.iter_entries_prefix(keys):
 
1302
                        if node[1] in seen_keys:
 
1303
                            continue
 
1304
                        seen_keys.add(node[1])
 
1305
                        yield node
 
1306
                return
 
1307
            except errors.NoSuchFile:
 
1308
                self._reload_or_raise()
1108
1309
 
1109
1310
    def key_count(self):
1110
1311
        """Return an estimate of the number of keys in this index.
1111
 
        
 
1312
 
1112
1313
        For CombinedGraphIndex this is approximated by the sum of the keys of
1113
1314
        the child indices. As child indices may have duplicate keys this can
1114
1315
        have a maximum error of the number of child indices * largest number of
1115
1316
        keys in any index.
1116
1317
        """
1117
 
        return sum((index.key_count() for index in self._indices), 0)
 
1318
        while True:
 
1319
            try:
 
1320
                return sum((index.key_count() for index in self._indices), 0)
 
1321
            except errors.NoSuchFile:
 
1322
                self._reload_or_raise()
 
1323
 
 
1324
    missing_keys = _missing_keys_from_parent_map
 
1325
 
 
1326
    def _reload_or_raise(self):
 
1327
        """We just got a NoSuchFile exception.
 
1328
 
 
1329
        Try to reload the indices, if it fails, just raise the current
 
1330
        exception.
 
1331
        """
 
1332
        if self._reload_func is None:
 
1333
            raise
 
1334
        exc_type, exc_value, exc_traceback = sys.exc_info()
 
1335
        trace.mutter('Trying to reload after getting exception: %s',
 
1336
                     exc_value)
 
1337
        if not self._reload_func():
 
1338
            # We tried to reload, but nothing changed, so we fail anyway
 
1339
            trace.mutter('_reload_func indicated nothing has changed.'
 
1340
                         ' Raising original exception.')
 
1341
            raise exc_type, exc_value, exc_traceback
1118
1342
 
1119
1343
    def validate(self):
1120
1344
        """Validate that everything in the index can be accessed."""
1121
 
        for index in self._indices:
1122
 
            index.validate()
 
1345
        while True:
 
1346
            try:
 
1347
                for index in self._indices:
 
1348
                    index.validate()
 
1349
                return
 
1350
            except errors.NoSuchFile:
 
1351
                self._reload_or_raise()
1123
1352
 
1124
1353
 
1125
1354
class InMemoryGraphIndex(GraphIndexBuilder):
1212
1441
                    raise errors.BadIndexKey(key)
1213
1442
                node = self._nodes[key]
1214
1443
                if node[0]:
1215
 
                    continue 
 
1444
                    continue
1216
1445
                if self.reference_lists:
1217
1446
                    yield self, key, node[2], node[1]
1218
1447
                else:
1219
1448
                    yield self, key, node[2]
1220
1449
            return
 
1450
        nodes_by_key = self._get_nodes_by_key()
1221
1451
        for key in keys:
1222
1452
            # sanity check
1223
1453
            if key[0] is None:
1225
1455
            if len(key) != self._key_length:
1226
1456
                raise errors.BadIndexKey(key)
1227
1457
            # find what it refers to:
1228
 
            key_dict = self._nodes_by_key
 
1458
            key_dict = nodes_by_key
1229
1459
            elements = list(key)
1230
1460
            # find the subdict to return
1231
1461
            try:
1242
1472
                    # can't be empty or would not exist
1243
1473
                    item, value = key_dict.iteritems().next()
1244
1474
                    if type(value) == dict:
1245
 
                        # push keys 
 
1475
                        # push keys
1246
1476
                        dicts.extend(key_dict.itervalues())
1247
1477
                    else:
1248
1478
                        # yield keys
1253
1483
 
1254
1484
    def key_count(self):
1255
1485
        """Return an estimate of the number of keys in this index.
1256
 
        
 
1486
 
1257
1487
        For InMemoryGraphIndex the estimate is exact.
1258
1488
        """
1259
1489
        return len(self._keys)
1267
1497
 
1268
1498
    Queries against this will emit queries against the adapted Graph with the
1269
1499
    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 
 
1500
    nodes will have their keys and node references adjusted to remove the
1271
1501
    prefix. Finally, an add_nodes_callback can be supplied - when called the
1272
1502
    nodes and references being added will have prefix prepended.
1273
1503
    """
1300
1530
                    adjusted_references))
1301
1531
        except ValueError:
1302
1532
            # XXX: TODO add an explicit interface for getting the reference list
1303
 
            # status, to handle this bit of user-friendliness in the API more 
 
1533
            # status, to handle this bit of user-friendliness in the API more
1304
1534
            # explicitly.
1305
1535
            for (key, value) in nodes:
1306
1536
                translated_nodes.append((self.prefix + key, value))
1378
1608
 
1379
1609
    def key_count(self):
1380
1610
        """Return an estimate of the number of keys in this index.
1381
 
        
 
1611
 
1382
1612
        For GraphIndexPrefixAdapter this is relatively expensive - key
1383
1613
        iteration with the prefix is done.
1384
1614
        """