← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2011-08-17 18:13:57 UTC
  • mfrom: (5268.7.29 transport-segments)
  • Revision ID: pqm@pqm.ubuntu.com-20110817181357-y5q5eth1hk8bl3om
(jelmer) Allow specifying the colocated branch to use in the branch URL,
 and retrieving the branch name using ControlDir._get_selected_branch.
 (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()
83
97
        # A dict of {key: (absent, ref_lists, value)}
84
98
        self._nodes = {}
 
99
        # Keys that are referenced but not actually present in this index
 
100
        self._absent_keys = set()
85
101
        self._nodes_by_key = None
86
102
        self._key_length = key_elements
 
103
        self._optimize_for_size = False
 
104
        self._combine_backing_indices = True
87
105
 
88
106
    def _check_key(self, key):
89
107
        """Raise BadIndexKey if key is not a valid key for this index."""
90
 
        if type(key) != tuple:
 
108
        if type(key) not in (tuple, StaticTuple):
91
109
            raise errors.BadIndexKey(key)
92
110
        if self._key_length != len(key):
93
111
            raise errors.BadIndexKey(key)
95
113
            if not element or _whitespace_re.search(element) is not None:
96
114
                raise errors.BadIndexKey(element)
97
115
 
 
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
 
98
138
    def _get_nodes_by_key(self):
99
139
        if self._nodes_by_key is None:
100
140
            nodes_by_key = {}
127
167
            return
128
168
        key_dict = self._nodes_by_key
129
169
        if self.reference_lists:
130
 
            key_value = key, value, node_refs
 
170
            key_value = StaticTuple(key, value, node_refs)
131
171
        else:
132
 
            key_value = key, value
 
172
            key_value = StaticTuple(key, value)
133
173
        for subkey in key[:-1]:
134
174
            key_dict = key_dict.setdefault(subkey, {})
135
175
        key_dict[key[-1]] = key_value
145
185
        :param value: The value associate with this key. Must not contain
146
186
            newlines or null characters.
147
187
        :return: (node_refs, absent_references)
148
 
            node_refs   basically a packed form of 'references' where all
149
 
                        iterables are tuples
150
 
            absent_references   reference keys that are not in self._nodes.
151
 
                                This may contain duplicates if the same key is
152
 
                                referenced in multiple lists.
 
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.
153
194
        """
 
195
        as_st = StaticTuple.from_sequence
154
196
        self._check_key(key)
155
197
        if _newline_null_re.search(value) is not None:
156
198
            raise errors.BadIndexValue(value)
165
207
                if reference not in self._nodes:
166
208
                    self._check_key(reference)
167
209
                    absent_references.append(reference)
168
 
            node_refs.append(tuple(reference_list))
169
 
        return tuple(node_refs), absent_references
 
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
170
214
 
171
215
    def add_node(self, key, value, references=()):
172
216
        """Add a node to the index.
177
221
        :param references: An iterable of iterables of keys. Each is a
178
222
            reference to another key.
179
223
        :param value: The value to associate with the key. It may be any
180
 
            bytes as long as it does not contain \0 or \n.
 
224
            bytes as long as it does not contain \\0 or \\n.
181
225
        """
182
226
        (node_refs,
183
227
         absent_references) = self._check_key_ref_value(key, references, value)
187
231
            # There may be duplicates, but I don't think it is worth worrying
188
232
            # about
189
233
            self._nodes[reference] = ('a', (), '')
 
234
        self._absent_keys.update(absent_references)
 
235
        self._absent_keys.discard(key)
190
236
        self._nodes[key] = ('', node_refs, value)
191
 
        self._keys.add(key)
192
237
        if self._nodes_by_key is not None and self._key_length > 1:
193
238
            self._update_nodes_by_key(key, value, node_refs)
194
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
        
195
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
        """
196
253
        lines = [_SIGNATURE]
197
254
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
198
255
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
199
 
        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')
200
258
        prefix_length = sum(len(x) for x in lines)
201
259
        # references are byte offsets. To avoid having to do nasty
202
260
        # polynomial work to resolve offsets (references to later in the
209
267
        # one to pad all the data with reference-length and determine entry
210
268
        # addresses.
211
269
        # One to serialise.
212
 
        
 
270
 
213
271
        # forward sorted by key. In future we may consider topological sorting,
214
272
        # at the cost of table scans for direct lookup, or a second index for
215
273
        # direct lookup
278
336
                (len(result.getvalue()), expected_bytes))
279
337
        return result
280
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
 
372
 
281
373
 
282
374
class GraphIndex(object):
283
375
    """An index for data with embedded graphs.
284
 
 
 
376
 
285
377
    The index maps keys to a list of key reference lists, and a value.
286
378
    Each node has the same number of key reference lists. Each key reference
287
379
    list can be empty or an arbitrary length. The value is an opaque NULL
288
 
    terminated string without any newlines. The storage of the index is 
 
380
    terminated string without any newlines. The storage of the index is
289
381
    hidden in the interface: keys and key references are always tuples of
290
382
    bytestrings, never the internal representation (e.g. dictionary offsets).
291
383
 
297
389
    suitable for production use. :XXX
298
390
    """
299
391
 
300
 
    def __init__(self, transport, name, size):
 
392
    def __init__(self, transport, name, size, unlimited_cache=False, offset=0):
301
393
        """Open an index called name on transport.
302
394
 
303
395
        :param transport: A bzrlib.transport.Transport.
309
401
            avoided by having it supplied. If size is None, then bisection
310
402
            support will be disabled and accessing the index will just stream
311
403
            all the data.
 
404
        :param offset: Instead of starting the index data at offset 0, start it
 
405
            at an arbitrary offset.
312
406
        """
313
407
        self._transport = transport
314
408
        self._name = name
331
425
        self._size = size
332
426
        # The number of bytes we've read so far in trying to process this file
333
427
        self._bytes_read = 0
 
428
        self._base_offset = offset
334
429
 
335
430
    def __eq__(self, other):
336
431
        """Equal when self and other were created with the same parameters."""
356
451
            # We already did this
357
452
            return
358
453
        if 'index' in debug.debug_flags:
359
 
            mutter('Reading entire index %s', self._transport.abspath(self._name))
 
454
            trace.mutter('Reading entire index %s',
 
455
                          self._transport.abspath(self._name))
360
456
        if stream is None:
361
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:])
362
462
        self._read_prefix(stream)
363
463
        self._expected_elements = 3 + self._key_length
364
464
        line_count = 0
370
470
        trailers = 0
371
471
        pos = stream.tell()
372
472
        lines = stream.read().split('\n')
 
473
        # GZ 2009-09-20: Should really use a try/finally block to ensure close
 
474
        stream.close()
373
475
        del lines[-1]
374
476
        _, _, _, trailers = self._parse_lines(lines, pos)
375
477
        for key, absent, references, value in self._keys_by_offset.itervalues():
382
484
                node_value = value
383
485
            self._nodes[key] = node_value
384
486
        # cache the keys for quick set intersections
385
 
        self._keys = set(self._nodes)
386
487
        if trailers != 1:
387
488
            # there must be one line - the empty trailer line.
388
489
            raise errors.BadIndexData(self)
389
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
 
390
513
    def _get_nodes_by_key(self):
391
514
        if self._nodes_by_key is None:
392
515
            nodes_by_key = {}
454
577
 
455
578
    def _resolve_references(self, references):
456
579
        """Return the resolved key references for references.
457
 
        
 
580
 
458
581
        References are resolved by looking up the location of the key in the
459
582
        _keys_by_offset map and substituting the key name, preserving ordering.
460
583
 
461
 
        :param references: An iterable of iterables of key locations. e.g. 
 
584
        :param references: An iterable of iterables of key locations. e.g.
462
585
            [[123, 456], [123]]
463
586
        :return: A tuple of tuples of keys.
464
587
        """
518
641
 
519
642
    def _iter_entries_from_total_buffer(self, keys):
520
643
        """Iterate over keys when the entire index is parsed."""
521
 
        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]
522
648
        if self.node_ref_lists:
523
649
            for key in keys:
524
 
                value, node_refs = self._nodes[key]
 
650
                value, node_refs = nodes[key]
525
651
                yield self, key, value, node_refs
526
652
        else:
527
653
            for key in keys:
528
 
                yield self, key, self._nodes[key]
 
654
                yield self, key, nodes[key]
529
655
 
530
656
    def iter_entries(self, keys):
531
657
        """Iterate over keys within the index.
553
679
        if self._nodes is not None:
554
680
            return self._iter_entries_from_total_buffer(keys)
555
681
        else:
556
 
            return (result[1] for result in bisect_multi_bytes(
 
682
            return (result[1] for result in bisect_multi.bisect_multi_bytes(
557
683
                self._lookup_keys_via_location, self._size, keys))
558
684
 
559
685
    def iter_entries_prefix(self, keys):
622
748
                    # can't be empty or would not exist
623
749
                    item, value = key_dict.iteritems().next()
624
750
                    if type(value) == dict:
625
 
                        # push keys 
 
751
                        # push keys
626
752
                        dicts.extend(key_dict.itervalues())
627
753
                    else:
628
754
                        # yield keys
634
760
                # the last thing looked up was a terminal element
635
761
                yield (self, ) + key_dict
636
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
 
637
780
    def key_count(self):
638
781
        """Return an estimate of the number of keys in this index.
639
 
        
 
782
 
640
783
        For GraphIndex the estimate is exact.
641
784
        """
642
785
        if self._key_count is None:
658
801
        # Possible improvements:
659
802
        #  - only bisect lookup each key once
660
803
        #  - sort the keys first, and use that to reduce the bisection window
661
 
        # ----- 
 
804
        # -----
662
805
        # this progresses in three parts:
663
806
        # read data
664
807
        # parse it
673
816
                # We have the key parsed.
674
817
                continue
675
818
            index = self._parsed_key_index(key)
676
 
            if (len(self._parsed_key_map) and 
 
819
            if (len(self._parsed_key_map) and
677
820
                self._parsed_key_map[index][0] <= key and
678
821
                (self._parsed_key_map[index][1] >= key or
679
822
                 # end of the file has been parsed
683
826
                continue
684
827
            # - if we have examined this part of the file already - yes
685
828
            index = self._parsed_byte_index(location)
686
 
            if (len(self._parsed_byte_map) and 
 
829
            if (len(self._parsed_byte_map) and
687
830
                self._parsed_byte_map[index][0] <= location and
688
831
                self._parsed_byte_map[index][1] > location):
689
832
                # the byte region has been parsed, so no read is needed.
944
1087
        # adjust offset and data to the parseable data.
945
1088
        trimmed_data = data[trim_start:trim_end]
946
1089
        if not (trimmed_data):
947
 
            raise AssertionError('read unneeded data [%d:%d] from [%d:%d]' 
 
1090
            raise AssertionError('read unneeded data [%d:%d] from [%d:%d]'
948
1091
                % (trim_start, trim_end, offset, offset + len(data)))
949
1092
        if trim_start:
950
1093
            offset += trim_start
1051
1194
            self._parsed_key_map.insert(index + 1, new_key)
1052
1195
 
1053
1196
    def _read_and_parse(self, readv_ranges):
1054
 
        """Read the the ranges and parse the resulting data.
 
1197
        """Read the ranges and parse the resulting data.
1055
1198
 
1056
1199
        :param readv_ranges: A prepared readv range list.
1057
1200
        """
1063
1206
            self._buffer_all()
1064
1207
            return
1065
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]
1066
1214
        readv_data = self._transport.readv(self._name, readv_ranges, True,
1067
 
            self._size)
 
1215
            self._size + self._base_offset)
1068
1216
        # parse
1069
1217
        for offset, data in readv_data:
 
1218
            offset -= base_offset
1070
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
1071
1225
            if offset == 0 and len(data) == self._size:
1072
1226
                # We read the whole range, most likely because the
1073
1227
                # Transport upcast our readv ranges into one long request
1095
1249
 
1096
1250
class CombinedGraphIndex(object):
1097
1251
    """A GraphIndex made up from smaller GraphIndices.
1098
 
    
 
1252
 
1099
1253
    The backing indices must implement GraphIndex, and are presumed to be
1100
1254
    static data.
1101
1255
 
1102
1256
    Queries against the combined index will be made against the first index,
1103
 
    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
1104
1258
    performance significantly. For example, if one index is on local disk and a
1105
1259
    second on a remote server, the local disk index should be before the other
1106
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).
1107
1266
    """
1108
1267
 
1109
 
    def __init__(self, indices):
 
1268
    def __init__(self, indices, reload_func=None):
1110
1269
        """Create a CombinedGraphIndex backed by indices.
1111
1270
 
1112
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.
1113
1275
        """
1114
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)
1115
1285
 
1116
1286
    def __repr__(self):
1117
1287
        return "%s(%s)" % (
1118
1288
                self.__class__.__name__,
1119
1289
                ', '.join(map(repr, self._indices)))
1120
1290
 
1121
 
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
1122
 
    def get_parents(self, revision_ids):
1123
 
        """See graph._StackedParentsProvider.get_parents.
1124
 
        
1125
 
        This implementation thunks the graph.Graph.get_parents api across to
1126
 
        GraphIndex.
1127
 
 
1128
 
        :param revision_ids: An iterable of graph keys for this graph.
1129
 
        :return: A list of parent details for each key in revision_ids.
1130
 
            Each parent details will be one of:
1131
 
             * None when the key was missing
1132
 
             * (NULL_REVISION,) when the key has no parents.
1133
 
             * (parent_key, parent_key...) otherwise.
1134
 
        """
1135
 
        parent_map = self.get_parent_map(revision_ids)
1136
 
        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()
1137
1295
 
1138
1296
    def get_parent_map(self, keys):
1139
 
        """See graph._StackedParentsProvider.get_parent_map"""
 
1297
        """See graph.StackedParentsProvider.get_parent_map"""
1140
1298
        search_keys = set(keys)
1141
 
        if NULL_REVISION in search_keys:
1142
 
            search_keys.discard(NULL_REVISION)
1143
 
            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:[]}
1144
1302
        else:
1145
1303
            found_parents = {}
1146
1304
        for index, key, value, refs in self.iter_entries(search_keys):
1147
1305
            parents = refs[0]
1148
1306
            if not parents:
1149
 
                parents = (NULL_REVISION,)
 
1307
                parents = (_mod_revision.NULL_REVISION,)
1150
1308
            found_parents[key] = parents
1151
1309
        return found_parents
1152
1310
 
1153
 
    def insert_index(self, pos, index):
 
1311
    has_key = _has_key_from_parent_map
 
1312
 
 
1313
    def insert_index(self, pos, index, name=None):
1154
1314
        """Insert a new index in the list of indices to query.
1155
1315
 
1156
1316
        :param pos: The position to insert the index.
1157
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)
1158
1321
        """
1159
1322
        self._indices.insert(pos, index)
 
1323
        self._index_names.insert(pos, name)
1160
1324
 
1161
1325
    def iter_all_entries(self):
1162
1326
        """Iterate over all keys within the index
1169
1333
            the most efficient order for the index.
1170
1334
        """
1171
1335
        seen_keys = set()
1172
 
        for index in self._indices:
1173
 
            for node in index.iter_all_entries():
1174
 
                if node[1] not in seen_keys:
1175
 
                    yield node
1176
 
                    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()
1177
1346
 
1178
1347
    def iter_entries(self, keys):
1179
1348
        """Iterate over keys within the index.
1182
1351
        value and are only reported once.
1183
1352
 
1184
1353
        :param keys: An iterable providing the keys to be retrieved.
1185
 
        :return: An iterable of (index, key, reference_lists, value). There is no
1186
 
            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
1187
1356
            efficient order for the index.
1188
1357
        """
1189
1358
        keys = set(keys)
1190
 
        for index in self._indices:
1191
 
            if not keys:
1192
 
                return
1193
 
            for node in index.iter_entries(keys):
1194
 
                keys.remove(node[1])
1195
 
                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)
1196
1376
 
1197
1377
    def iter_entries_prefix(self, keys):
1198
1378
        """Iterate over keys within the index using prefix matching.
1218
1398
        if not keys:
1219
1399
            return
1220
1400
        seen_keys = set()
1221
 
        for index in self._indices:
1222
 
            for node in index.iter_entries_prefix(keys):
1223
 
                if node[1] in seen_keys:
1224
 
                    continue
1225
 
                seen_keys.add(node[1])
1226
 
                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
1227
1548
 
1228
1549
    def key_count(self):
1229
1550
        """Return an estimate of the number of keys in this index.
1230
 
        
 
1551
 
1231
1552
        For CombinedGraphIndex this is approximated by the sum of the keys of
1232
1553
        the child indices. As child indices may have duplicate keys this can
1233
1554
        have a maximum error of the number of child indices * largest number of
1234
1555
        keys in any index.
1235
1556
        """
1236
 
        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
1237
1586
 
1238
1587
    def validate(self):
1239
1588
        """Validate that everything in the index can be accessed."""
1240
 
        for index in self._indices:
1241
 
            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()
1242
1596
 
1243
1597
 
1244
1598
class InMemoryGraphIndex(GraphIndexBuilder):
1288
1642
            defined order for the result iteration - it will be in the most
1289
1643
            efficient order for the index (keys iteration order in this case).
1290
1644
        """
1291
 
        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]
1292
1649
        if self.reference_lists:
1293
 
            for key in keys.intersection(self._keys):
1294
 
                node = self._nodes[key]
 
1650
            for key in keys:
 
1651
                node = nodes[key]
1295
1652
                if not node[0]:
1296
1653
                    yield self, key, node[2], node[1]
1297
1654
        else:
1298
 
            for key in keys.intersection(self._keys):
1299
 
                node = self._nodes[key]
 
1655
            for key in keys:
 
1656
                node = nodes[key]
1300
1657
                if not node[0]:
1301
1658
                    yield self, key, node[2]
1302
1659
 
1331
1688
                    raise errors.BadIndexKey(key)
1332
1689
                node = self._nodes[key]
1333
1690
                if node[0]:
1334
 
                    continue 
 
1691
                    continue
1335
1692
                if self.reference_lists:
1336
1693
                    yield self, key, node[2], node[1]
1337
1694
                else:
1362
1719
                    # can't be empty or would not exist
1363
1720
                    item, value = key_dict.iteritems().next()
1364
1721
                    if type(value) == dict:
1365
 
                        # push keys 
 
1722
                        # push keys
1366
1723
                        dicts.extend(key_dict.itervalues())
1367
1724
                    else:
1368
1725
                        # yield keys
1373
1730
 
1374
1731
    def key_count(self):
1375
1732
        """Return an estimate of the number of keys in this index.
1376
 
        
 
1733
 
1377
1734
        For InMemoryGraphIndex the estimate is exact.
1378
1735
        """
1379
 
        return len(self._keys)
 
1736
        return len(self._nodes) - len(self._absent_keys)
1380
1737
 
1381
1738
    def validate(self):
1382
1739
        """In memory index's have no known corruption at the moment."""
1387
1744
 
1388
1745
    Queries against this will emit queries against the adapted Graph with the
1389
1746
    prefix added, queries for all items use iter_entries_prefix. The returned
1390
 
    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
1391
1748
    prefix. Finally, an add_nodes_callback can be supplied - when called the
1392
1749
    nodes and references being added will have prefix prepended.
1393
1750
    """
1420
1777
                    adjusted_references))
1421
1778
        except ValueError:
1422
1779
            # XXX: TODO add an explicit interface for getting the reference list
1423
 
            # 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
1424
1781
            # explicitly.
1425
1782
            for (key, value) in nodes:
1426
1783
                translated_nodes.append((self.prefix + key, value))
1498
1855
 
1499
1856
    def key_count(self):
1500
1857
        """Return an estimate of the number of keys in this index.
1501
 
        
 
1858
 
1502
1859
        For GraphIndexPrefixAdapter this is relatively expensive - key
1503
1860
        iteration with the prefix is done.
1504
1861
        """