/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 breezy/bzr/index.py

  • Committer: Breezy landing bot
  • Author(s): Jelmer Vernooij
  • Date: 2018-11-16 11:31:40 UTC
  • mfrom: (7143.12.3 annotated-tags)
  • Revision ID: breezy.the.bot@gmail.com-20181116113140-618u04763u0dyxnh
Fix fetching of revisions that are referenced by annotated tags.

Merged from https://code.launchpad.net/~jelmer/brz/annotated-tags/+merge/358536

Show diffs side-by-side

added added

removed removed

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