/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to bzrlib/index.py

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

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2007-2011 Canonical Ltd
 
1
# Copyright (C) 2007-2010 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
16
16
 
17
17
"""Indexing facilities."""
18
18
 
19
 
from __future__ import absolute_import
20
 
 
21
19
__all__ = [
22
20
    'CombinedGraphIndex',
23
21
    'GraphIndex',
27
25
    ]
28
26
 
29
27
from bisect import bisect_right
 
28
from cStringIO import StringIO
30
29
import re
 
30
import sys
31
31
 
32
 
from ..lazy_import import lazy_import
 
32
from bzrlib.lazy_import import lazy_import
33
33
lazy_import(globals(), """
34
 
from breezy import (
35
 
    bisect_multi,
36
 
    revision as _mod_revision,
37
 
    trace,
38
 
    )
 
34
from bzrlib import trace
 
35
from bzrlib.bisect_multi import bisect_multi_bytes
 
36
from bzrlib.revision import NULL_REVISION
 
37
from bzrlib.trace import mutter
39
38
""")
40
 
from .. import (
 
39
from bzrlib import (
41
40
    debug,
42
41
    errors,
43
42
    )
44
 
from ..sixish import (
45
 
    BytesIO,
46
 
    bytesintern,
47
 
    viewvalues,
48
 
    viewitems,
49
 
    zip,
50
 
    )
51
 
from ..static_tuple import StaticTuple
 
43
from bzrlib.static_tuple import StaticTuple
52
44
 
53
45
_HEADER_READV = (0, 200)
54
 
_OPTION_KEY_ELEMENTS = b"key_elements="
55
 
_OPTION_LEN = b"len="
56
 
_OPTION_NODE_REFS = b"node_ref_lists="
57
 
_SIGNATURE = b"Bazaar Graph Index 1\n"
58
 
 
59
 
 
60
 
class BadIndexFormatSignature(errors.BzrError):
61
 
 
62
 
    _fmt = "%(value)s is not an index of type %(_type)s."
63
 
 
64
 
    def __init__(self, value, _type):
65
 
        errors.BzrError.__init__(self)
66
 
        self.value = value
67
 
        self._type = _type
68
 
 
69
 
 
70
 
class BadIndexData(errors.BzrError):
71
 
 
72
 
    _fmt = "Error in data for index %(value)s."
73
 
 
74
 
    def __init__(self, value):
75
 
        errors.BzrError.__init__(self)
76
 
        self.value = value
77
 
 
78
 
 
79
 
class BadIndexDuplicateKey(errors.BzrError):
80
 
 
81
 
    _fmt = "The key '%(key)s' is already in index '%(index)s'."
82
 
 
83
 
    def __init__(self, key, index):
84
 
        errors.BzrError.__init__(self)
85
 
        self.key = key
86
 
        self.index = index
87
 
 
88
 
 
89
 
class BadIndexKey(errors.BzrError):
90
 
 
91
 
    _fmt = "The key '%(key)s' is not a valid key."
92
 
 
93
 
    def __init__(self, key):
94
 
        errors.BzrError.__init__(self)
95
 
        self.key = key
96
 
 
97
 
 
98
 
class BadIndexOptions(errors.BzrError):
99
 
 
100
 
    _fmt = "Could not parse options for index %(value)s."
101
 
 
102
 
    def __init__(self, value):
103
 
        errors.BzrError.__init__(self)
104
 
        self.value = value
105
 
 
106
 
 
107
 
class BadIndexValue(errors.BzrError):
108
 
 
109
 
    _fmt = "The value '%(value)s' is not a valid value."
110
 
 
111
 
    def __init__(self, value):
112
 
        errors.BzrError.__init__(self)
113
 
        self.value = value
114
 
 
115
 
 
116
 
_whitespace_re = re.compile(b'[\t\n\x0b\x0c\r\x00 ]')
117
 
_newline_null_re = re.compile(b'[\n\0]')
 
46
_OPTION_KEY_ELEMENTS = "key_elements="
 
47
_OPTION_LEN = "len="
 
48
_OPTION_NODE_REFS = "node_ref_lists="
 
49
_SIGNATURE = "Bazaar Graph Index 1\n"
 
50
 
 
51
 
 
52
_whitespace_re = re.compile('[\t\n\x0b\x0c\r\x00 ]')
 
53
_newline_null_re = re.compile('[\n\0]')
118
54
 
119
55
 
120
56
def _has_key_from_parent_map(self, key):
133
69
class GraphIndexBuilder(object):
134
70
    """A builder that can build a GraphIndex.
135
71
 
136
 
    The resulting graph has the structure::
 
72
    The resulting graph has the structure:
137
73
 
138
 
      _SIGNATURE OPTIONS NODES NEWLINE
139
 
      _SIGNATURE     := 'Bazaar Graph Index 1' NEWLINE
140
 
      OPTIONS        := 'node_ref_lists=' DIGITS NEWLINE
141
 
      NODES          := NODE*
142
 
      NODE           := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
143
 
      KEY            := Not-whitespace-utf8
144
 
      ABSENT         := 'a'
145
 
      REFERENCES     := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
146
 
      REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
147
 
      REFERENCE      := DIGITS  ; digits is the byte offset in the index of the
148
 
                                ; referenced key.
149
 
      VALUE          := no-newline-no-null-bytes
 
74
    _SIGNATURE OPTIONS NODES NEWLINE
 
75
    _SIGNATURE     := 'Bazaar Graph Index 1' NEWLINE
 
76
    OPTIONS        := 'node_ref_lists=' DIGITS NEWLINE
 
77
    NODES          := NODE*
 
78
    NODE           := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
 
79
    KEY            := Not-whitespace-utf8
 
80
    ABSENT         := 'a'
 
81
    REFERENCES     := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
 
82
    REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
 
83
    REFERENCE      := DIGITS  ; digits is the byte offset in the index of the
 
84
                              ; referenced key.
 
85
    VALUE          := no-newline-no-null-bytes
150
86
    """
151
87
 
152
88
    def __init__(self, reference_lists=0, key_elements=1):
169
105
    def _check_key(self, key):
170
106
        """Raise BadIndexKey if key is not a valid key for this index."""
171
107
        if type(key) not in (tuple, StaticTuple):
172
 
            raise BadIndexKey(key)
 
108
            raise errors.BadIndexKey(key)
173
109
        if self._key_length != len(key):
174
 
            raise BadIndexKey(key)
 
110
            raise errors.BadIndexKey(key)
175
111
        for element in key:
176
 
            if not element or type(element) != bytes or _whitespace_re.search(element) is not None:
177
 
                raise BadIndexKey(key)
 
112
            if not element or _whitespace_re.search(element) is not None:
 
113
                raise errors.BadIndexKey(element)
178
114
 
179
115
    def _external_references(self):
180
116
        """Return references that are not present in this index.
202
138
        if self._nodes_by_key is None:
203
139
            nodes_by_key = {}
204
140
            if self.reference_lists:
205
 
                for key, (absent, references, value) in viewitems(self._nodes):
 
141
                for key, (absent, references, value) in self._nodes.iteritems():
206
142
                    if absent:
207
143
                        continue
208
144
                    key_dict = nodes_by_key
210
146
                        key_dict = key_dict.setdefault(subkey, {})
211
147
                    key_dict[key[-1]] = key, value, references
212
148
            else:
213
 
                for key, (absent, references, value) in viewitems(self._nodes):
 
149
                for key, (absent, references, value) in self._nodes.iteritems():
214
150
                    if absent:
215
151
                        continue
216
152
                    key_dict = nodes_by_key
248
184
        :param value: The value associate with this key. Must not contain
249
185
            newlines or null characters.
250
186
        :return: (node_refs, absent_references)
251
 
        
252
 
            * node_refs: basically a packed form of 'references' where all
253
 
              iterables are tuples
254
 
            * absent_references: reference keys that are not in self._nodes.
255
 
              This may contain duplicates if the same key is referenced in
256
 
              multiple lists.
 
187
            node_refs   basically a packed form of 'references' where all
 
188
                        iterables are tuples
 
189
            absent_references   reference keys that are not in self._nodes.
 
190
                                This may contain duplicates if the same key is
 
191
                                referenced in multiple lists.
257
192
        """
258
193
        as_st = StaticTuple.from_sequence
259
194
        self._check_key(key)
260
195
        if _newline_null_re.search(value) is not None:
261
 
            raise BadIndexValue(value)
 
196
            raise errors.BadIndexValue(value)
262
197
        if len(references) != self.reference_lists:
263
 
            raise BadIndexValue(references)
 
198
            raise errors.BadIndexValue(references)
264
199
        node_refs = []
265
200
        absent_references = []
266
201
        for reference_list in references:
284
219
        :param references: An iterable of iterables of keys. Each is a
285
220
            reference to another key.
286
221
        :param value: The value to associate with the key. It may be any
287
 
            bytes as long as it does not contain \\0 or \\n.
 
222
            bytes as long as it does not contain \0 or \n.
288
223
        """
289
224
        (node_refs,
290
225
         absent_references) = self._check_key_ref_value(key, references, value)
291
 
        if key in self._nodes and self._nodes[key][0] != b'a':
292
 
            raise BadIndexDuplicateKey(key, self)
 
226
        if key in self._nodes and self._nodes[key][0] != 'a':
 
227
            raise errors.BadIndexDuplicateKey(key, self)
293
228
        for reference in absent_references:
294
229
            # There may be duplicates, but I don't think it is worth worrying
295
230
            # about
296
 
            self._nodes[reference] = (b'a', (), b'')
 
231
            self._nodes[reference] = ('a', (), '')
297
232
        self._absent_keys.update(absent_references)
298
233
        self._absent_keys.discard(key)
299
 
        self._nodes[key] = (b'', node_refs, value)
 
234
        self._nodes[key] = ('', node_refs, value)
300
235
        if self._nodes_by_key is not None and self._key_length > 1:
301
236
            self._update_nodes_by_key(key, value, node_refs)
302
237
 
308
243
        """
309
244
        
310
245
    def finish(self):
311
 
        """Finish the index.
312
 
 
313
 
        :returns: cBytesIO holding the full context of the index as it 
314
 
        should be written to disk.
315
 
        """
316
246
        lines = [_SIGNATURE]
317
 
        lines.append(b'%s%d\n' % (_OPTION_NODE_REFS, self.reference_lists))
318
 
        lines.append(b'%s%d\n' % (_OPTION_KEY_ELEMENTS, self._key_length))
 
247
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
 
248
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
319
249
        key_count = len(self._nodes) - len(self._absent_keys)
320
 
        lines.append(b'%s%d\n' % (_OPTION_LEN, key_count))
 
250
        lines.append(_OPTION_LEN + str(key_count) + '\n')
321
251
        prefix_length = sum(len(x) for x in lines)
322
252
        # references are byte offsets. To avoid having to do nasty
323
253
        # polynomial work to resolve offsets (references to later in the
334
264
        # forward sorted by key. In future we may consider topological sorting,
335
265
        # at the cost of table scans for direct lookup, or a second index for
336
266
        # direct lookup
337
 
        nodes = sorted(viewitems(self._nodes))
 
267
        nodes = sorted(self._nodes.items())
338
268
        # if we do not prepass, we don't know how long it will be up front.
339
269
        expected_bytes = None
340
270
        # we only need to pre-pass if we have reference lists at all.
380
310
            for key, non_ref_bytes, total_references in key_offset_info:
381
311
                key_addresses[key] = non_ref_bytes + total_references*digits
382
312
            # serialise
383
 
            format_string = b'%%0%dd' % digits
 
313
            format_string = '%%0%sd' % digits
384
314
        for key, (absent, references, value) in nodes:
385
315
            flattened_references = []
386
316
            for ref_list in references:
387
317
                ref_addresses = []
388
318
                for reference in ref_list:
389
319
                    ref_addresses.append(format_string % key_addresses[reference])
390
 
                flattened_references.append(b'\r'.join(ref_addresses))
391
 
            string_key = b'\x00'.join(key)
392
 
            lines.append(b"%s\x00%s\x00%s\x00%s\n" % (string_key, absent,
393
 
                b'\t'.join(flattened_references), value))
394
 
        lines.append(b'\n')
395
 
        result = BytesIO(b''.join(lines))
 
320
                flattened_references.append('\r'.join(ref_addresses))
 
321
            string_key = '\x00'.join(key)
 
322
            lines.append("%s\x00%s\x00%s\x00%s\n" % (string_key, absent,
 
323
                '\t'.join(flattened_references), value))
 
324
        lines.append('\n')
 
325
        result = StringIO(''.join(lines))
396
326
        if expected_bytes and len(result.getvalue()) != expected_bytes:
397
327
            raise errors.BzrError('Failed index creation. Internal error:'
398
328
                ' mismatched output length and expected length: %d %d' %
455
385
    def __init__(self, transport, name, size, unlimited_cache=False, offset=0):
456
386
        """Open an index called name on transport.
457
387
 
458
 
        :param transport: A breezy.transport.Transport.
 
388
        :param transport: A bzrlib.transport.Transport.
459
389
        :param name: A path to provide to transport API calls.
460
390
        :param size: The size of the index in bytes. This is used for bisection
461
391
            logic to perform partial index reads. While the size could be
493
423
    def __eq__(self, other):
494
424
        """Equal when self and other were created with the same parameters."""
495
425
        return (
496
 
            isinstance(self, type(other)) and
 
426
            type(self) == type(other) and
497
427
            self._transport == other._transport and
498
428
            self._name == other._name and
499
429
            self._size == other._size)
501
431
    def __ne__(self, other):
502
432
        return not self.__eq__(other)
503
433
 
504
 
    def __lt__(self, other):
505
 
        # We don't really care about the order, just that there is an order.
506
 
        if (not isinstance(other, GraphIndex) and
507
 
            not isinstance(other, InMemoryGraphIndex)):
508
 
            raise TypeError(other)
509
 
        return hash(self) < hash(other)
510
 
 
511
 
    def __hash__(self):
512
 
        return hash((type(self), self._transport, self._name, self._size))
513
 
 
514
434
    def __repr__(self):
515
435
        return "%s(%r)" % (self.__class__.__name__,
516
436
            self._transport.abspath(self._name))
524
444
            # We already did this
525
445
            return
526
446
        if 'index' in debug.debug_flags:
527
 
            trace.mutter('Reading entire index %s',
528
 
                          self._transport.abspath(self._name))
 
447
            mutter('Reading entire index %s', self._transport.abspath(self._name))
529
448
        if stream is None:
530
449
            stream = self._transport.get(self._name)
531
450
            if self._base_offset != 0:
532
451
                # This is wasteful, but it is better than dealing with
533
452
                # adjusting all the offsets, etc.
534
 
                stream = BytesIO(stream.read()[self._base_offset:])
535
 
        try:
536
 
            self._read_prefix(stream)
537
 
            self._expected_elements = 3 + self._key_length
538
 
            line_count = 0
539
 
            # raw data keyed by offset
540
 
            self._keys_by_offset = {}
541
 
            # ready-to-return key:value or key:value, node_ref_lists
542
 
            self._nodes = {}
543
 
            self._nodes_by_key = None
544
 
            trailers = 0
545
 
            pos = stream.tell()
546
 
            lines = stream.read().split(b'\n')
547
 
        finally:
548
 
            stream.close()
 
453
                stream = StringIO(stream.read()[self._base_offset:])
 
454
        self._read_prefix(stream)
 
455
        self._expected_elements = 3 + self._key_length
 
456
        line_count = 0
 
457
        # raw data keyed by offset
 
458
        self._keys_by_offset = {}
 
459
        # ready-to-return key:value or key:value, node_ref_lists
 
460
        self._nodes = {}
 
461
        self._nodes_by_key = None
 
462
        trailers = 0
 
463
        pos = stream.tell()
 
464
        lines = stream.read().split('\n')
 
465
        stream.close()
549
466
        del lines[-1]
550
467
        _, _, _, trailers = self._parse_lines(lines, pos)
551
 
        for key, absent, references, value in viewvalues(self._keys_by_offset):
 
468
        for key, absent, references, value in self._keys_by_offset.itervalues():
552
469
            if absent:
553
470
                continue
554
471
            # resolve references:
560
477
        # cache the keys for quick set intersections
561
478
        if trailers != 1:
562
479
            # there must be one line - the empty trailer line.
563
 
            raise BadIndexData(self)
 
480
            raise errors.BadIndexData(self)
564
481
 
565
482
    def clear_cache(self):
566
483
        """Clear out any cached/memoized values.
579
496
                % (ref_list_num, self.node_ref_lists))
580
497
        refs = set()
581
498
        nodes = self._nodes
582
 
        for key, (value, ref_lists) in viewitems(nodes):
 
499
        for key, (value, ref_lists) in nodes.iteritems():
583
500
            ref_list = ref_lists[ref_list_num]
584
501
            refs.update([ref for ref in ref_list if ref not in nodes])
585
502
        return refs
588
505
        if self._nodes_by_key is None:
589
506
            nodes_by_key = {}
590
507
            if self.node_ref_lists:
591
 
                for key, (value, references) in viewitems(self._nodes):
 
508
                for key, (value, references) in self._nodes.iteritems():
592
509
                    key_dict = nodes_by_key
593
510
                    for subkey in key[:-1]:
594
511
                        key_dict = key_dict.setdefault(subkey, {})
595
512
                    key_dict[key[-1]] = key, value, references
596
513
            else:
597
 
                for key, value in viewitems(self._nodes):
 
514
                for key, value in self._nodes.iteritems():
598
515
                    key_dict = nodes_by_key
599
516
                    for subkey in key[:-1]:
600
517
                        key_dict = key_dict.setdefault(subkey, {})
617
534
        if self._nodes is None:
618
535
            self._buffer_all()
619
536
        if self.node_ref_lists:
620
 
            for key, (value, node_ref_lists) in viewitems(self._nodes):
 
537
            for key, (value, node_ref_lists) in self._nodes.iteritems():
621
538
                yield self, key, value, node_ref_lists
622
539
        else:
623
 
            for key, value in viewitems(self._nodes):
 
540
            for key, value in self._nodes.iteritems():
624
541
                yield self, key, value
625
542
 
626
543
    def _read_prefix(self, stream):
627
544
        signature = stream.read(len(self._signature()))
628
545
        if not signature == self._signature():
629
 
            raise BadIndexFormatSignature(self._name, GraphIndex)
 
546
            raise errors.BadIndexFormatSignature(self._name, GraphIndex)
630
547
        options_line = stream.readline()
631
548
        if not options_line.startswith(_OPTION_NODE_REFS):
632
 
            raise BadIndexOptions(self)
 
549
            raise errors.BadIndexOptions(self)
633
550
        try:
634
551
            self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):-1])
635
552
        except ValueError:
636
 
            raise BadIndexOptions(self)
 
553
            raise errors.BadIndexOptions(self)
637
554
        options_line = stream.readline()
638
555
        if not options_line.startswith(_OPTION_KEY_ELEMENTS):
639
 
            raise BadIndexOptions(self)
 
556
            raise errors.BadIndexOptions(self)
640
557
        try:
641
558
            self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):-1])
642
559
        except ValueError:
643
 
            raise BadIndexOptions(self)
 
560
            raise errors.BadIndexOptions(self)
644
561
        options_line = stream.readline()
645
562
        if not options_line.startswith(_OPTION_LEN):
646
 
            raise BadIndexOptions(self)
 
563
            raise errors.BadIndexOptions(self)
647
564
        try:
648
565
            self._key_count = int(options_line[len(_OPTION_LEN):-1])
649
566
        except ValueError:
650
 
            raise BadIndexOptions(self)
 
567
            raise errors.BadIndexOptions(self)
651
568
 
652
569
    def _resolve_references(self, references):
653
570
        """Return the resolved key references for references.
753
670
        if self._nodes is not None:
754
671
            return self._iter_entries_from_total_buffer(keys)
755
672
        else:
756
 
            return (result[1] for result in bisect_multi.bisect_multi_bytes(
 
673
            return (result[1] for result in bisect_multi_bytes(
757
674
                self._lookup_keys_via_location, self._size, keys))
758
675
 
759
676
    def iter_entries_prefix(self, keys):
786
703
            self._buffer_all()
787
704
        if self._key_length == 1:
788
705
            for key in keys:
789
 
                _sanity_check_key(self, key)
 
706
                # sanity check
 
707
                if key[0] is None:
 
708
                    raise errors.BadIndexKey(key)
 
709
                if len(key) != self._key_length:
 
710
                    raise errors.BadIndexKey(key)
790
711
                if self.node_ref_lists:
791
712
                    value, node_refs = self._nodes[key]
792
713
                    yield self, key, value, node_refs
794
715
                    yield self, key, self._nodes[key]
795
716
            return
796
717
        nodes_by_key = self._get_nodes_by_key()
797
 
        for entry in _iter_entries_prefix(self, nodes_by_key, keys):
798
 
            yield entry
 
718
        for key in keys:
 
719
            # sanity check
 
720
            if key[0] is None:
 
721
                raise errors.BadIndexKey(key)
 
722
            if len(key) != self._key_length:
 
723
                raise errors.BadIndexKey(key)
 
724
            # find what it refers to:
 
725
            key_dict = nodes_by_key
 
726
            elements = list(key)
 
727
            # find the subdict whose contents should be returned.
 
728
            try:
 
729
                while len(elements) and elements[0] is not None:
 
730
                    key_dict = key_dict[elements[0]]
 
731
                    elements.pop(0)
 
732
            except KeyError:
 
733
                # a non-existant lookup.
 
734
                continue
 
735
            if len(elements):
 
736
                dicts = [key_dict]
 
737
                while dicts:
 
738
                    key_dict = dicts.pop(-1)
 
739
                    # can't be empty or would not exist
 
740
                    item, value = key_dict.iteritems().next()
 
741
                    if type(value) == dict:
 
742
                        # push keys
 
743
                        dicts.extend(key_dict.itervalues())
 
744
                    else:
 
745
                        # yield keys
 
746
                        for value in key_dict.itervalues():
 
747
                            # each value is the key:value:node refs tuple
 
748
                            # ready to yield.
 
749
                            yield (self, ) + value
 
750
            else:
 
751
                # the last thing looked up was a terminal element
 
752
                yield (self, ) + key_dict
799
753
 
800
754
    def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
801
755
        """See BTreeIndex._find_ancestors."""
833
787
 
834
788
        :param location_keys: A list of location(byte offset), key tuples.
835
789
        :return: A list of (location_key, result) tuples as expected by
836
 
            breezy.bisect_multi.bisect_multi_bytes.
 
790
            bzrlib.bisect_multi.bisect_multi_bytes.
837
791
        """
838
792
        # Possible improvements:
839
793
        #  - only bisect lookup each key once
974
928
        """
975
929
        signature = bytes[0:len(self._signature())]
976
930
        if not signature == self._signature():
977
 
            raise BadIndexFormatSignature(self._name, GraphIndex)
 
931
            raise errors.BadIndexFormatSignature(self._name, GraphIndex)
978
932
        lines = bytes[len(self._signature()):].splitlines()
979
933
        options_line = lines[0]
980
934
        if not options_line.startswith(_OPTION_NODE_REFS):
981
 
            raise BadIndexOptions(self)
 
935
            raise errors.BadIndexOptions(self)
982
936
        try:
983
937
            self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):])
984
938
        except ValueError:
985
 
            raise BadIndexOptions(self)
 
939
            raise errors.BadIndexOptions(self)
986
940
        options_line = lines[1]
987
941
        if not options_line.startswith(_OPTION_KEY_ELEMENTS):
988
 
            raise BadIndexOptions(self)
 
942
            raise errors.BadIndexOptions(self)
989
943
        try:
990
944
            self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):])
991
945
        except ValueError:
992
 
            raise BadIndexOptions(self)
 
946
            raise errors.BadIndexOptions(self)
993
947
        options_line = lines[2]
994
948
        if not options_line.startswith(_OPTION_LEN):
995
 
            raise BadIndexOptions(self)
 
949
            raise errors.BadIndexOptions(self)
996
950
        try:
997
951
            self._key_count = int(options_line[len(_OPTION_LEN):])
998
952
        except ValueError:
999
 
            raise BadIndexOptions(self)
 
953
            raise errors.BadIndexOptions(self)
1000
954
        # calculate the bytes we have processed
1001
955
        header_end = (len(signature) + len(lines[0]) + len(lines[1]) +
1002
956
            len(lines[2]) + 3)
1106
1060
        if not start_adjacent:
1107
1061
            # work around python bug in rfind
1108
1062
            if trim_start is None:
1109
 
                trim_start = data.find(b'\n') + 1
 
1063
                trim_start = data.find('\n') + 1
1110
1064
            else:
1111
 
                trim_start = data.find(b'\n', trim_start) + 1
 
1065
                trim_start = data.find('\n', trim_start) + 1
1112
1066
            if not (trim_start != 0):
1113
1067
                raise AssertionError('no \n was present')
1114
1068
            # print 'removing start', offset, trim_start, repr(data[:trim_start])
1115
1069
        if not end_adjacent:
1116
1070
            # work around python bug in rfind
1117
1071
            if trim_end is None:
1118
 
                trim_end = data.rfind(b'\n') + 1
 
1072
                trim_end = data.rfind('\n') + 1
1119
1073
            else:
1120
 
                trim_end = data.rfind(b'\n', None, trim_end) + 1
 
1074
                trim_end = data.rfind('\n', None, trim_end) + 1
1121
1075
            if not (trim_end != 0):
1122
1076
                raise AssertionError('no \n was present')
1123
1077
            # print 'removing end', offset, trim_end, repr(data[trim_end:])
1130
1084
            offset += trim_start
1131
1085
        # print "parsing", repr(trimmed_data)
1132
1086
        # splitlines mangles the \r delimiters.. don't use it.
1133
 
        lines = trimmed_data.split(b'\n')
 
1087
        lines = trimmed_data.split('\n')
1134
1088
        del lines[-1]
1135
1089
        pos = offset
1136
1090
        first_key, last_key, nodes, _ = self._parse_lines(lines, pos)
1146
1100
        trailers = 0
1147
1101
        nodes = []
1148
1102
        for line in lines:
1149
 
            if line == b'':
 
1103
            if line == '':
1150
1104
                # must be at the end
1151
1105
                if self._size:
1152
1106
                    if not (self._size == pos + 1):
1153
1107
                        raise AssertionError("%s %s" % (self._size, pos))
1154
1108
                trailers += 1
1155
1109
                continue
1156
 
            elements = line.split(b'\0')
 
1110
            elements = line.split('\0')
1157
1111
            if len(elements) != self._expected_elements:
1158
 
                raise BadIndexData(self)
 
1112
                raise errors.BadIndexData(self)
1159
1113
            # keys are tuples. Each element is a string that may occur many
1160
1114
            # times, so we intern them to save space. AB, RC, 200807
1161
 
            key = tuple([bytesintern(element) for element in elements[:self._key_length]])
 
1115
            key = tuple([intern(element) for element in elements[:self._key_length]])
1162
1116
            if first_key is None:
1163
1117
                first_key = key
1164
1118
            absent, references, value = elements[-3:]
1165
1119
            ref_lists = []
1166
 
            for ref_string in references.split(b'\t'):
 
1120
            for ref_string in references.split('\t'):
1167
1121
                ref_lists.append(tuple([
1168
 
                    int(ref) for ref in ref_string.split(b'\r') if ref
 
1122
                    int(ref) for ref in ref_string.split('\r') if ref
1169
1123
                    ]))
1170
1124
            ref_lists = tuple(ref_lists)
1171
1125
            self._keys_by_offset[pos] = (key, absent, ref_lists, value)
1263
1217
                # We read the whole range, most likely because the
1264
1218
                # Transport upcast our readv ranges into one long request
1265
1219
                # for enough total data to grab the whole index.
1266
 
                self._buffer_all(BytesIO(data))
 
1220
                self._buffer_all(StringIO(data))
1267
1221
                return
1268
1222
            if self._bisect_nodes is None:
1269
1223
                # this must be the start
1333
1287
    def get_parent_map(self, keys):
1334
1288
        """See graph.StackedParentsProvider.get_parent_map"""
1335
1289
        search_keys = set(keys)
1336
 
        if _mod_revision.NULL_REVISION in search_keys:
1337
 
            search_keys.discard(_mod_revision.NULL_REVISION)
1338
 
            found_parents = {_mod_revision.NULL_REVISION:[]}
 
1290
        if NULL_REVISION in search_keys:
 
1291
            search_keys.discard(NULL_REVISION)
 
1292
            found_parents = {NULL_REVISION:[]}
1339
1293
        else:
1340
1294
            found_parents = {}
1341
1295
        for index, key, value, refs in self.iter_entries(search_keys):
1342
1296
            parents = refs[0]
1343
1297
            if not parents:
1344
 
                parents = (_mod_revision.NULL_REVISION,)
 
1298
                parents = (NULL_REVISION,)
1345
1299
            found_parents[key] = parents
1346
1300
        return found_parents
1347
1301
 
1348
 
    __contains__ = _has_key_from_parent_map
 
1302
    has_key = _has_key_from_parent_map
1349
1303
 
1350
1304
    def insert_index(self, pos, index, name=None):
1351
1305
        """Insert a new index in the list of indices to query.
1378
1332
                            yield node
1379
1333
                            seen_keys.add(node[1])
1380
1334
                return
1381
 
            except errors.NoSuchFile as e:
1382
 
                if not self._try_reload(e):
1383
 
                    raise
 
1335
            except errors.NoSuchFile:
 
1336
                self._reload_or_raise()
1384
1337
 
1385
1338
    def iter_entries(self, keys):
1386
1339
        """Iterate over keys within the index.
1408
1361
                    if index_hit:
1409
1362
                        hit_indices.append(index)
1410
1363
                break
1411
 
            except errors.NoSuchFile as e:
1412
 
                if not self._try_reload(e):
1413
 
                    raise
 
1364
            except errors.NoSuchFile:
 
1365
                self._reload_or_raise()
1414
1366
        self._move_to_front(hit_indices)
1415
1367
 
1416
1368
    def iter_entries_prefix(self, keys):
1451
1403
                    if index_hit:
1452
1404
                        hit_indices.append(index)
1453
1405
                break
1454
 
            except errors.NoSuchFile as e:
1455
 
                if not self._try_reload(e):
1456
 
                    raise
 
1406
            except errors.NoSuchFile:
 
1407
                self._reload_or_raise()
1457
1408
        self._move_to_front(hit_indices)
1458
1409
 
1459
1410
    def _move_to_front(self, hit_indices):
1482
1433
        """
1483
1434
        indices_info = zip(self._index_names, self._indices)
1484
1435
        if 'index' in debug.debug_flags:
1485
 
            indices_info = list(indices_info)
1486
 
            trace.mutter('CombinedGraphIndex reordering: currently %r, '
1487
 
                         'promoting %r', indices_info, hit_indices)
 
1436
            mutter('CombinedGraphIndex reordering: currently %r, promoting %r',
 
1437
                   indices_info, hit_indices)
1488
1438
        hit_names = []
1489
1439
        unhit_names = []
1490
1440
        new_hit_indices = []
1507
1457
        self._indices = new_hit_indices + unhit_indices
1508
1458
        self._index_names = hit_names + unhit_names
1509
1459
        if 'index' in debug.debug_flags:
1510
 
            trace.mutter('CombinedGraphIndex reordered: %r', self._indices)
 
1460
            mutter('CombinedGraphIndex reordered: %r', self._indices)
1511
1461
        return hit_names
1512
1462
 
1513
1463
    def _move_to_front_by_name(self, hit_names):
1598
1548
        while True:
1599
1549
            try:
1600
1550
                return sum((index.key_count() for index in self._indices), 0)
1601
 
            except errors.NoSuchFile as e:
1602
 
                if not self._try_reload(e):
1603
 
                    raise
 
1551
            except errors.NoSuchFile:
 
1552
                self._reload_or_raise()
1604
1553
 
1605
1554
    missing_keys = _missing_keys_from_parent_map
1606
1555
 
1607
 
    def _try_reload(self, error):
 
1556
    def _reload_or_raise(self):
1608
1557
        """We just got a NoSuchFile exception.
1609
1558
 
1610
1559
        Try to reload the indices, if it fails, just raise the current
1611
1560
        exception.
1612
1561
        """
1613
1562
        if self._reload_func is None:
1614
 
            return False
1615
 
        trace.mutter('Trying to reload after getting exception: %s', str(error))
 
1563
            raise
 
1564
        exc_type, exc_value, exc_traceback = sys.exc_info()
 
1565
        trace.mutter('Trying to reload after getting exception: %s',
 
1566
                     exc_value)
1616
1567
        if not self._reload_func():
1617
1568
            # We tried to reload, but nothing changed, so we fail anyway
1618
1569
            trace.mutter('_reload_func indicated nothing has changed.'
1619
1570
                         ' Raising original exception.')
1620
 
            return False
1621
 
        return True
 
1571
            raise exc_type, exc_value, exc_traceback
1622
1572
 
1623
1573
    def set_sibling_indices(self, sibling_combined_graph_indices):
1624
1574
        """Set the CombinedGraphIndex objects to reorder after reordering self.
1632
1582
                for index in self._indices:
1633
1583
                    index.validate()
1634
1584
                return
1635
 
            except errors.NoSuchFile as e:
1636
 
                if not self._try_reload(e):
1637
 
                    raise
 
1585
            except errors.NoSuchFile:
 
1586
                self._reload_or_raise()
1638
1587
 
1639
1588
 
1640
1589
class InMemoryGraphIndex(GraphIndexBuilder):
1668
1617
            trace.mutter_callsite(3,
1669
1618
                "iter_all_entries scales with size of history.")
1670
1619
        if self.reference_lists:
1671
 
            for key, (absent, references, value) in viewitems(self._nodes):
 
1620
            for key, (absent, references, value) in self._nodes.iteritems():
1672
1621
                if not absent:
1673
1622
                    yield self, key, value, references
1674
1623
        else:
1675
 
            for key, (absent, references, value) in viewitems(self._nodes):
 
1624
            for key, (absent, references, value) in self._nodes.iteritems():
1676
1625
                if not absent:
1677
1626
                    yield self, key, value
1678
1627
 
1716
1665
            will be returned, and every match that is in the index will be
1717
1666
            returned.
1718
1667
        """
 
1668
        # XXX: To much duplication with the GraphIndex class; consider finding
 
1669
        # a good place to pull out the actual common logic.
1719
1670
        keys = set(keys)
1720
1671
        if not keys:
1721
1672
            return
1722
1673
        if self._key_length == 1:
1723
1674
            for key in keys:
1724
 
                _sanity_check_key(self, key)
 
1675
                # sanity check
 
1676
                if key[0] is None:
 
1677
                    raise errors.BadIndexKey(key)
 
1678
                if len(key) != self._key_length:
 
1679
                    raise errors.BadIndexKey(key)
1725
1680
                node = self._nodes[key]
1726
1681
                if node[0]:
1727
1682
                    continue
1731
1686
                    yield self, key, node[2]
1732
1687
            return
1733
1688
        nodes_by_key = self._get_nodes_by_key()
1734
 
        for entry in _iter_entries_prefix(self, nodes_by_key, keys):
1735
 
            yield entry
 
1689
        for key in keys:
 
1690
            # sanity check
 
1691
            if key[0] is None:
 
1692
                raise errors.BadIndexKey(key)
 
1693
            if len(key) != self._key_length:
 
1694
                raise errors.BadIndexKey(key)
 
1695
            # find what it refers to:
 
1696
            key_dict = nodes_by_key
 
1697
            elements = list(key)
 
1698
            # find the subdict to return
 
1699
            try:
 
1700
                while len(elements) and elements[0] is not None:
 
1701
                    key_dict = key_dict[elements[0]]
 
1702
                    elements.pop(0)
 
1703
            except KeyError:
 
1704
                # a non-existant lookup.
 
1705
                continue
 
1706
            if len(elements):
 
1707
                dicts = [key_dict]
 
1708
                while dicts:
 
1709
                    key_dict = dicts.pop(-1)
 
1710
                    # can't be empty or would not exist
 
1711
                    item, value = key_dict.iteritems().next()
 
1712
                    if type(value) == dict:
 
1713
                        # push keys
 
1714
                        dicts.extend(key_dict.itervalues())
 
1715
                    else:
 
1716
                        # yield keys
 
1717
                        for value in key_dict.itervalues():
 
1718
                            yield (self, ) + value
 
1719
            else:
 
1720
                yield (self, ) + key_dict
1736
1721
 
1737
1722
    def key_count(self):
1738
1723
        """Return an estimate of the number of keys in this index.
1744
1729
    def validate(self):
1745
1730
        """In memory index's have no known corruption at the moment."""
1746
1731
 
1747
 
    def __lt__(self, other):
1748
 
        # We don't really care about the order, just that there is an order.
1749
 
        if (not isinstance(other, GraphIndex) and
1750
 
            not isinstance(other, InMemoryGraphIndex)):
1751
 
            raise TypeError(other)
1752
 
        return hash(self) < hash(other)
1753
 
 
1754
1732
 
1755
1733
class GraphIndexPrefixAdapter(object):
1756
1734
    """An adapter between GraphIndex with different key lengths.
1814
1792
        for node in an_iter:
1815
1793
            # cross checks
1816
1794
            if node[1][:self.prefix_len] != self.prefix:
1817
 
                raise BadIndexData(self)
 
1795
                raise errors.BadIndexData(self)
1818
1796
            for ref_list in node[3]:
1819
1797
                for ref_node in ref_list:
1820
1798
                    if ref_node[:self.prefix_len] != self.prefix:
1821
 
                        raise BadIndexData(self)
 
1799
                        raise errors.BadIndexData(self)
1822
1800
            yield node[0], node[1][self.prefix_len:], node[2], (
1823
1801
                tuple(tuple(ref_node[self.prefix_len:] for ref_node in ref_list)
1824
1802
                for ref_list in node[3]))
1877
1855
    def validate(self):
1878
1856
        """Call the adapted's validate."""
1879
1857
        self.adapted.validate()
1880
 
 
1881
 
 
1882
 
def _sanity_check_key(index_or_builder, key):
1883
 
    """Raise BadIndexKey if key cannot be used for prefix matching."""
1884
 
    if key[0] is None:
1885
 
        raise BadIndexKey(key)
1886
 
    if len(key) != index_or_builder._key_length:
1887
 
        raise BadIndexKey(key)
1888
 
 
1889
 
 
1890
 
def _iter_entries_prefix(index_or_builder, nodes_by_key, keys):
1891
 
    """Helper for implementing prefix matching iterators."""
1892
 
    for key in keys:
1893
 
        _sanity_check_key(index_or_builder, key)
1894
 
        # find what it refers to:
1895
 
        key_dict = nodes_by_key
1896
 
        elements = list(key)
1897
 
        # find the subdict whose contents should be returned.
1898
 
        try:
1899
 
            while len(elements) and elements[0] is not None:
1900
 
                key_dict = key_dict[elements[0]]
1901
 
                elements.pop(0)
1902
 
        except KeyError:
1903
 
            # a non-existant lookup.
1904
 
            continue
1905
 
        if len(elements):
1906
 
            dicts = [key_dict]
1907
 
            while dicts:
1908
 
                values_view = viewvalues(dicts.pop())
1909
 
                # can't be empty or would not exist
1910
 
                value = next(iter(values_view))
1911
 
                if isinstance(value, dict):
1912
 
                    # still descending, push values
1913
 
                    dicts.extend(values_view)
1914
 
                else:
1915
 
                    # at leaf tuples, yield values
1916
 
                    for value in values_view:
1917
 
                        # each value is the key:value:node refs tuple
1918
 
                        # ready to yield.
1919
 
                        yield (index_or_builder, ) + value
1920
 
        else:
1921
 
            # the last thing looked up was a terminal element
1922
 
            yield (index_or_builder, ) + key_dict