← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Alexander Belchenko
  • Date: 2007-08-10 09:04:38 UTC
  • mto: This revision was merged to the branch mainline in revision 2694.
  • Revision ID: bialix@ukr.net-20070810090438-0835xdz0rl8825qv
fixes after Ian's review

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
24
24
    'InMemoryGraphIndex',
25
25
    ]
26
26
 
27
 
from bisect import bisect_right
28
27
from cStringIO import StringIO
29
28
import re
30
29
 
31
 
from bzrlib.lazy_import import lazy_import
32
 
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
37
 
""")
38
 
from bzrlib import (
39
 
    debug,
40
 
    errors,
41
 
    symbol_versioning,
42
 
    )
 
30
from bzrlib import errors
43
31
 
44
 
_HEADER_READV = (0, 200)
45
32
_OPTION_KEY_ELEMENTS = "key_elements="
46
 
_OPTION_LEN = "len="
47
33
_OPTION_NODE_REFS = "node_ref_lists="
48
34
_SIGNATURE = "Bazaar Graph Index 1\n"
49
35
 
79
65
        :param key_elements: The number of bytestrings in each key.
80
66
        """
81
67
        self.reference_lists = reference_lists
82
 
        self._keys = set()
83
68
        self._nodes = {}
84
69
        self._nodes_by_key = {}
85
70
        self._key_length = key_elements
120
105
        if key in self._nodes and self._nodes[key][0] == '':
121
106
            raise errors.BadIndexDuplicateKey(key, self)
122
107
        self._nodes[key] = ('', tuple(node_refs), value)
123
 
        self._keys.add(key)
124
108
        if self._key_length > 1:
125
109
            key_dict = self._nodes_by_key
126
110
            if self.reference_lists:
139
123
        lines = [_SIGNATURE]
140
124
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
141
125
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
142
 
        lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
143
126
        prefix_length = sum(len(x) for x in lines)
144
127
        # references are byte offsets. To avoid having to do nasty
145
128
        # polynomial work to resolve offsets (references to later in the 
240
223
    suitable for production use. :XXX
241
224
    """
242
225
 
243
 
    def __init__(self, transport, name, size):
 
226
    def __init__(self, transport, name):
244
227
        """Open an index called name on transport.
245
228
 
246
229
        :param transport: A bzrlib.transport.Transport.
247
230
        :param name: A path to provide to transport API calls.
248
 
        :param size: The size of the index in bytes. This is used for bisection
249
 
            logic to perform partial index reads. While the size could be
250
 
            obtained by statting the file this introduced an additional round
251
 
            trip as well as requiring stat'able transports, both of which are
252
 
            avoided by having it supplied. If size is None, then bisection
253
 
            support will be disabled and accessing the index will just stream
254
 
            all the data.
255
231
        """
256
232
        self._transport = transport
257
233
        self._name = name
258
 
        # Becomes a dict of key:(value, reference-list-byte-locations) used by
259
 
        # the bisection interface to store parsed but not resolved keys.
260
 
        self._bisect_nodes = None
261
 
        # Becomes a dict of key:(value, reference-list-keys) which are ready to
262
 
        # be returned directly to callers.
263
234
        self._nodes = None
264
 
        # a sorted list of slice-addresses for the parsed bytes of the file.
265
 
        # e.g. (0,1) would mean that byte 0 is parsed.
266
 
        self._parsed_byte_map = []
267
 
        # a sorted list of keys matching each slice address for parsed bytes
268
 
        # e.g. (None, 'foo@bar') would mean that the first byte contained no
269
 
        # key, and the end byte of the slice is the of the data for 'foo@bar'
270
 
        self._parsed_key_map = []
271
 
        self._key_count = None
272
235
        self._keys_by_offset = None
273
236
        self._nodes_by_key = None
274
 
        self._size = size
275
 
 
276
 
    def __eq__(self, other):
277
 
        """Equal when self and other were created with the same parameters."""
278
 
        return (
279
 
            type(self) == type(other) and
280
 
            self._transport == other._transport and
281
 
            self._name == other._name and
282
 
            self._size == other._size)
283
 
 
284
 
    def __ne__(self, other):
285
 
        return not self.__eq__(other)
286
237
 
287
238
    def _buffer_all(self):
288
239
        """Buffer all the index data.
289
240
 
290
241
        Mutates self._nodes and self.keys_by_offset.
291
242
        """
292
 
        if 'index' in debug.debug_flags:
293
 
            mutter('Reading entire index %s', self._transport.abspath(self._name))
294
243
        stream = self._transport.get(self._name)
295
244
        self._read_prefix(stream)
296
 
        self._expected_elements = 3 + self._key_length
 
245
        expected_elements = 3 + self._key_length
297
246
        line_count = 0
298
247
        # raw data keyed by offset
299
248
        self._keys_by_offset = {}
302
251
        self._nodes_by_key = {}
303
252
        trailers = 0
304
253
        pos = stream.tell()
305
 
        lines = stream.read().split('\n')
306
 
        del lines[-1]
307
 
        _, _, _, trailers = self._parse_lines(lines, pos)
 
254
        for line in stream.readlines():
 
255
            if line == '\n':
 
256
                trailers += 1
 
257
                continue
 
258
            elements = line.split('\0')
 
259
            if len(elements) != expected_elements:
 
260
                raise errors.BadIndexData(self)
 
261
            # keys are tuples
 
262
            key = tuple(elements[:self._key_length])
 
263
            absent, references, value = elements[-3:]
 
264
            value = value[:-1] # remove the newline
 
265
            ref_lists = []
 
266
            for ref_string in references.split('\t'):
 
267
                ref_lists.append(tuple([
 
268
                    int(ref) for ref in ref_string.split('\r') if ref
 
269
                    ]))
 
270
            ref_lists = tuple(ref_lists)
 
271
            self._keys_by_offset[pos] = (key, absent, ref_lists, value)
 
272
            pos += len(line)
308
273
        for key, absent, references, value in self._keys_by_offset.itervalues():
309
274
            if absent:
310
275
                continue
311
276
            # resolve references:
312
277
            if self.node_ref_lists:
313
 
                node_value = (value, self._resolve_references(references))
 
278
                node_refs = []
 
279
                for ref_list in references:
 
280
                    node_refs.append(tuple([self._keys_by_offset[ref][0] for ref in ref_list]))
 
281
                node_value = (value, tuple(node_refs))
314
282
            else:
315
283
                node_value = value
316
284
            self._nodes[key] = node_value
328
296
                for subkey in key[:-1]:
329
297
                    key_dict = key_dict.setdefault(subkey, {})
330
298
                key_dict[key[-1]] = key_value
331
 
        # cache the keys for quick set intersections
332
299
        self._keys = set(self._nodes)
333
300
        if trailers != 1:
334
301
            # there must be one line - the empty trailer line.
337
304
    def iter_all_entries(self):
338
305
        """Iterate over all keys within the index.
339
306
 
340
 
        :return: An iterable of (index, key, value) or (index, key, value, reference_lists).
 
307
        :return: An iterable of (key, value) or (key, value, reference_lists).
341
308
            The former tuple is used when there are no reference lists in the
342
309
            index, making the API compatible with simple key:value index types.
343
310
            There is no defined order for the result iteration - it will be in
344
311
            the most efficient order for the index.
345
312
        """
346
 
        if 'evil' in debug.debug_flags:
347
 
            trace.mutter_callsite(3,
348
 
                "iter_all_entries scales with size of history.")
349
313
        if self._nodes is None:
350
314
            self._buffer_all()
351
315
        if self.node_ref_lists:
373
337
            self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):-1])
374
338
        except ValueError:
375
339
            raise errors.BadIndexOptions(self)
376
 
        options_line = stream.readline()
377
 
        if not options_line.startswith(_OPTION_LEN):
378
 
            raise errors.BadIndexOptions(self)
379
 
        try:
380
 
            self._key_count = int(options_line[len(_OPTION_LEN):-1])
381
 
        except ValueError:
382
 
            raise errors.BadIndexOptions(self)
383
 
 
384
 
    def _resolve_references(self, references):
385
 
        """Return the resolved key references for references.
386
 
        
387
 
        References are resolved by looking up the location of the key in the
388
 
        _keys_by_offset map and substituting the key name, preserving ordering.
389
 
 
390
 
        :param references: An iterable of iterables of key locations. e.g. 
391
 
            [[123, 456], [123]]
392
 
        :return: A tuple of tuples of keys.
393
 
        """
394
 
        node_refs = []
395
 
        for ref_list in references:
396
 
            node_refs.append(tuple([self._keys_by_offset[ref][0] for ref in ref_list]))
397
 
        return tuple(node_refs)
398
 
 
399
 
    def _find_index(self, range_map, key):
400
 
        """Helper for the _parsed_*_index calls.
401
 
 
402
 
        Given a range map - [(start, end), ...], finds the index of the range
403
 
        in the map for key if it is in the map, and if it is not there, the
404
 
        immediately preceeding range in the map.
405
 
        """
406
 
        result = bisect_right(range_map, key) - 1
407
 
        if result + 1 < len(range_map):
408
 
            # check the border condition, it may be in result + 1
409
 
            if range_map[result + 1][0] == key[0]:
410
 
                return result + 1
411
 
        return result
412
 
 
413
 
    def _parsed_byte_index(self, offset):
414
 
        """Return the index of the entry immediately before offset.
415
 
 
416
 
        e.g. if the parsed map has regions 0,10 and 11,12 parsed, meaning that
417
 
        there is one unparsed byte (the 11th, addressed as[10]). then:
418
 
        asking for 0 will return 0
419
 
        asking for 10 will return 0
420
 
        asking for 11 will return 1
421
 
        asking for 12 will return 1
422
 
        """
423
 
        key = (offset, 0)
424
 
        return self._find_index(self._parsed_byte_map, key)
425
 
 
426
 
    def _parsed_key_index(self, key):
427
 
        """Return the index of the entry immediately before key.
428
 
 
429
 
        e.g. if the parsed map has regions (None, 'a') and ('b','c') parsed,
430
 
        meaning that keys from None to 'a' inclusive, and 'b' to 'c' inclusive
431
 
        have been parsed, then:
432
 
        asking for '' will return 0
433
 
        asking for 'a' will return 0
434
 
        asking for 'b' will return 1
435
 
        asking for 'e' will return 1
436
 
        """
437
 
        search_key = (key, None)
438
 
        return self._find_index(self._parsed_key_map, search_key)
439
 
 
440
 
    def _is_parsed(self, offset):
441
 
        """Returns True if offset has been parsed."""
442
 
        index = self._parsed_byte_index(offset)
443
 
        if index == len(self._parsed_byte_map):
444
 
            return offset < self._parsed_byte_map[index - 1][1]
445
 
        start, end = self._parsed_byte_map[index]
446
 
        return offset >= start and offset < end
447
 
 
448
 
    def _iter_entries_from_total_buffer(self, keys):
449
 
        """Iterate over keys when the entire index is parsed."""
 
340
 
 
341
    def iter_entries(self, keys):
 
342
        """Iterate over keys within the index.
 
343
 
 
344
        :param keys: An iterable providing the keys to be retrieved.
 
345
        :return: An iterable as per iter_all_entries, but restricted to the
 
346
            keys supplied. No additional keys will be returned, and every
 
347
            key supplied that is in the index will be returned.
 
348
        """
 
349
        keys = set(keys)
 
350
        if not keys:
 
351
            return
 
352
        if self._nodes is None:
 
353
            self._buffer_all()
450
354
        keys = keys.intersection(self._keys)
451
355
        if self.node_ref_lists:
452
356
            for key in keys:
456
360
            for key in keys:
457
361
                yield self, key, self._nodes[key]
458
362
 
459
 
    def iter_entries(self, keys):
460
 
        """Iterate over keys within the index.
461
 
 
462
 
        :param keys: An iterable providing the keys to be retrieved.
463
 
        :return: An iterable as per iter_all_entries, but restricted to the
464
 
            keys supplied. No additional keys will be returned, and every
465
 
            key supplied that is in the index will be returned.
466
 
        """
467
 
        # PERFORMANCE TODO: parse and bisect all remaining data at some
468
 
        # threshold of total-index processing/get calling layers that expect to
469
 
        # read the entire index to use the iter_all_entries  method instead.
470
 
        keys = set(keys)
471
 
        if not keys:
472
 
            return []
473
 
        if self._size is None and self._nodes is None:
474
 
            self._buffer_all()
475
 
        if self._nodes is not None:
476
 
            return self._iter_entries_from_total_buffer(keys)
477
 
        else:
478
 
            return (result[1] for result in bisect_multi_bytes(
479
 
                self._lookup_keys_via_location, self._size, keys))
480
 
 
481
363
    def iter_entries_prefix(self, keys):
482
364
        """Iterate over keys within the index using prefix matching.
483
365
 
486
368
        'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
487
369
        only the former key is returned.
488
370
 
489
 
        WARNING: Note that this method currently causes a full index parse
490
 
        unconditionally (which is reasonably appropriate as it is a means for
491
 
        thunking many small indices into one larger one and still supplies
492
 
        iter_all_entries at the thunk layer).
493
 
 
494
371
        :param keys: An iterable providing the key prefixes to be retrieved.
495
372
            Each key prefix takes the form of a tuple the length of a key, but
496
373
            with the last N elements 'None' rather than a regular bytestring.
555
432
                # the last thing looked up was a terminal element
556
433
                yield (self, ) + key_dict
557
434
 
558
 
    def key_count(self):
559
 
        """Return an estimate of the number of keys in this index.
560
 
        
561
 
        For GraphIndex the estimate is exact.
562
 
        """
563
 
        if self._key_count is None:
564
 
            self._read_and_parse([_HEADER_READV])
565
 
        return self._key_count
566
 
 
567
 
    def _lookup_keys_via_location(self, location_keys):
568
 
        """Public interface for implementing bisection.
569
 
 
570
 
        If _buffer_all has been called, then all the data for the index is in
571
 
        memory, and this method should not be called, as it uses a separate
572
 
        cache because it cannot pre-resolve all indices, which buffer_all does
573
 
        for performance.
574
 
 
575
 
        :param location_keys: A list of location(byte offset), key tuples.
576
 
        :return: A list of (location_key, result) tuples as expected by
577
 
            bzrlib.bisect_multi.bisect_multi_bytes.
578
 
        """
579
 
        # Possible improvements:
580
 
        #  - only bisect lookup each key once
581
 
        #  - sort the keys first, and use that to reduce the bisection window
582
 
        # ----- 
583
 
        # this progresses in three parts:
584
 
        # read data
585
 
        # parse it
586
 
        # attempt to answer the question from the now in memory data.
587
 
        # build the readv request
588
 
        # for each location, ask for 800 bytes - much more than rows we've seen
589
 
        # anywhere.
590
 
        readv_ranges = []
591
 
        for location, key in location_keys:
592
 
            # can we answer from cache?
593
 
            if self._bisect_nodes and key in self._bisect_nodes:
594
 
                # We have the key parsed.
595
 
                continue
596
 
            index = self._parsed_key_index(key)
597
 
            if (len(self._parsed_key_map) and 
598
 
                self._parsed_key_map[index][0] <= key and
599
 
                (self._parsed_key_map[index][1] >= key or
600
 
                 # end of the file has been parsed
601
 
                 self._parsed_byte_map[index][1] == self._size)):
602
 
                # the key has been parsed, so no lookup is needed even if its
603
 
                # not present.
604
 
                continue
605
 
            # - if we have examined this part of the file already - yes
606
 
            index = self._parsed_byte_index(location)
607
 
            if (len(self._parsed_byte_map) and 
608
 
                self._parsed_byte_map[index][0] <= location and
609
 
                self._parsed_byte_map[index][1] > location):
610
 
                # the byte region has been parsed, so no read is needed.
611
 
                continue
612
 
            length = 800
613
 
            if location + length > self._size:
614
 
                length = self._size - location
615
 
            # todo, trim out parsed locations.
616
 
            if length > 0:
617
 
                readv_ranges.append((location, length))
618
 
        # read the header if needed
619
 
        if self._bisect_nodes is None:
620
 
            readv_ranges.append(_HEADER_READV)
621
 
        self._read_and_parse(readv_ranges)
622
 
        # generate results:
623
 
        #  - figure out <, >, missing, present
624
 
        #  - result present references so we can return them.
625
 
        result = []
626
 
        # keys that we cannot answer until we resolve references
627
 
        pending_references = []
628
 
        pending_locations = set()
629
 
        for location, key in location_keys:
630
 
            # can we answer from cache?
631
 
            if key in self._bisect_nodes:
632
 
                # the key has been parsed, so no lookup is needed
633
 
                if self.node_ref_lists:
634
 
                    # the references may not have been all parsed.
635
 
                    value, refs = self._bisect_nodes[key]
636
 
                    wanted_locations = []
637
 
                    for ref_list in refs:
638
 
                        for ref in ref_list:
639
 
                            if ref not in self._keys_by_offset:
640
 
                                wanted_locations.append(ref)
641
 
                    if wanted_locations:
642
 
                        pending_locations.update(wanted_locations)
643
 
                        pending_references.append((location, key))
644
 
                        continue
645
 
                    result.append(((location, key), (self, key,
646
 
                        value, self._resolve_references(refs))))
647
 
                else:
648
 
                    result.append(((location, key),
649
 
                        (self, key, self._bisect_nodes[key])))
650
 
                continue
651
 
            else:
652
 
                # has the region the key should be in, been parsed?
653
 
                index = self._parsed_key_index(key)
654
 
                if (self._parsed_key_map[index][0] <= key and
655
 
                    (self._parsed_key_map[index][1] >= key or
656
 
                     # end of the file has been parsed
657
 
                     self._parsed_byte_map[index][1] == self._size)):
658
 
                    result.append(((location, key), False))
659
 
                    continue
660
 
            # no, is the key above or below the probed location:
661
 
            # get the range of the probed & parsed location
662
 
            index = self._parsed_byte_index(location)
663
 
            # if the key is below the start of the range, its below
664
 
            if key < self._parsed_key_map[index][0]:
665
 
                direction = -1
666
 
            else:
667
 
                direction = +1
668
 
            result.append(((location, key), direction))
669
 
        readv_ranges = []
670
 
        # lookup data to resolve references
671
 
        for location in pending_locations:
672
 
            length = 800
673
 
            if location + length > self._size:
674
 
                length = self._size - location
675
 
            # TODO: trim out parsed locations (e.g. if the 800 is into the
676
 
            # parsed region trim it, and dont use the adjust_for_latency
677
 
            # facility)
678
 
            if length > 0:
679
 
                readv_ranges.append((location, length))
680
 
        self._read_and_parse(readv_ranges)
681
 
        for location, key in pending_references:
682
 
            # answer key references we had to look-up-late.
683
 
            index = self._parsed_key_index(key)
684
 
            value, refs = self._bisect_nodes[key]
685
 
            result.append(((location, key), (self, key,
686
 
                value, self._resolve_references(refs))))
687
 
        return result
688
 
 
689
 
    def _parse_header_from_bytes(self, bytes):
690
 
        """Parse the header from a region of bytes.
691
 
 
692
 
        :param bytes: The data to parse.
693
 
        :return: An offset, data tuple such as readv yields, for the unparsed
694
 
            data. (which may length 0).
695
 
        """
696
 
        signature = bytes[0:len(self._signature())]
697
 
        if not signature == self._signature():
698
 
            raise errors.BadIndexFormatSignature(self._name, GraphIndex)
699
 
        lines = bytes[len(self._signature()):].splitlines()
700
 
        options_line = lines[0]
701
 
        if not options_line.startswith(_OPTION_NODE_REFS):
702
 
            raise errors.BadIndexOptions(self)
703
 
        try:
704
 
            self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):])
705
 
        except ValueError:
706
 
            raise errors.BadIndexOptions(self)
707
 
        options_line = lines[1]
708
 
        if not options_line.startswith(_OPTION_KEY_ELEMENTS):
709
 
            raise errors.BadIndexOptions(self)
710
 
        try:
711
 
            self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):])
712
 
        except ValueError:
713
 
            raise errors.BadIndexOptions(self)
714
 
        options_line = lines[2]
715
 
        if not options_line.startswith(_OPTION_LEN):
716
 
            raise errors.BadIndexOptions(self)
717
 
        try:
718
 
            self._key_count = int(options_line[len(_OPTION_LEN):])
719
 
        except ValueError:
720
 
            raise errors.BadIndexOptions(self)
721
 
        # calculate the bytes we have processed
722
 
        header_end = (len(signature) + len(lines[0]) + len(lines[1]) +
723
 
            len(lines[2]) + 3)
724
 
        self._parsed_bytes(0, None, header_end, None)
725
 
        # setup parsing state
726
 
        self._expected_elements = 3 + self._key_length
727
 
        # raw data keyed by offset
728
 
        self._keys_by_offset = {}
729
 
        # keys with the value and node references
730
 
        self._bisect_nodes = {}
731
 
        return header_end, bytes[header_end:]
732
 
 
733
 
    def _parse_region(self, offset, data):
734
 
        """Parse node data returned from a readv operation.
735
 
 
736
 
        :param offset: The byte offset the data starts at.
737
 
        :param data: The data to parse.
738
 
        """
739
 
        # trim the data.
740
 
        # end first:
741
 
        end = offset + len(data)
742
 
        high_parsed = offset
743
 
        while True:
744
 
            # Trivial test - if the current index's end is within the
745
 
            # low-matching parsed range, we're done.
746
 
            index = self._parsed_byte_index(high_parsed)
747
 
            if end < self._parsed_byte_map[index][1]:
748
 
                return
749
 
            # print "[%d:%d]" % (offset, end), \
750
 
            #     self._parsed_byte_map[index:index + 2]
751
 
            high_parsed, last_segment = self._parse_segment(
752
 
                offset, data, end, index)
753
 
            if last_segment:
754
 
                return
755
 
 
756
 
    def _parse_segment(self, offset, data, end, index):
757
 
        """Parse one segment of data.
758
 
 
759
 
        :param offset: Where 'data' begins in the file.
760
 
        :param data: Some data to parse a segment of.
761
 
        :param end: Where data ends
762
 
        :param index: The current index into the parsed bytes map.
763
 
        :return: True if the parsed segment is the last possible one in the
764
 
            range of data.
765
 
        :return: high_parsed_byte, last_segment.
766
 
            high_parsed_byte is the location of the highest parsed byte in this
767
 
            segment, last_segment is True if the parsed segment is the last
768
 
            possible one in the data block.
769
 
        """
770
 
        # default is to use all data
771
 
        trim_end = None
772
 
        # accomodate overlap with data before this.
773
 
        if offset < self._parsed_byte_map[index][1]:
774
 
            # overlaps the lower parsed region
775
 
            # skip the parsed data
776
 
            trim_start = self._parsed_byte_map[index][1] - offset
777
 
            # don't trim the start for \n
778
 
            start_adjacent = True
779
 
        elif offset == self._parsed_byte_map[index][1]:
780
 
            # abuts the lower parsed region
781
 
            # use all data
782
 
            trim_start = None
783
 
            # do not trim anything
784
 
            start_adjacent = True
785
 
        else:
786
 
            # does not overlap the lower parsed region
787
 
            # use all data
788
 
            trim_start = None
789
 
            # but trim the leading \n
790
 
            start_adjacent = False
791
 
        if end == self._size:
792
 
            # lines up to the end of all data:
793
 
            # use it all
794
 
            trim_end = None
795
 
            # do not strip to the last \n
796
 
            end_adjacent = True
797
 
            last_segment = True
798
 
        elif index + 1 == len(self._parsed_byte_map):
799
 
            # at the end of the parsed data
800
 
            # use it all
801
 
            trim_end = None
802
 
            # but strip to the last \n
803
 
            end_adjacent = False
804
 
            last_segment = True
805
 
        elif end == self._parsed_byte_map[index + 1][0]:
806
 
            # buts up against the next parsed region
807
 
            # use it all
808
 
            trim_end = None
809
 
            # do not strip to the last \n
810
 
            end_adjacent = True
811
 
            last_segment = True
812
 
        elif end > self._parsed_byte_map[index + 1][0]:
813
 
            # overlaps into the next parsed region
814
 
            # only consider the unparsed data
815
 
            trim_end = self._parsed_byte_map[index + 1][0] - offset
816
 
            # do not strip to the last \n as we know its an entire record
817
 
            end_adjacent = True
818
 
            last_segment = end < self._parsed_byte_map[index + 1][1]
819
 
        else:
820
 
            # does not overlap into the next region
821
 
            # use it all
822
 
            trim_end = None
823
 
            # but strip to the last \n
824
 
            end_adjacent = False
825
 
            last_segment = True
826
 
        # now find bytes to discard if needed
827
 
        if not start_adjacent:
828
 
            # work around python bug in rfind
829
 
            if trim_start is None:
830
 
                trim_start = data.find('\n') + 1
831
 
            else:
832
 
                trim_start = data.find('\n', trim_start) + 1
833
 
            assert trim_start != 0, 'no \n was present'
834
 
            # print 'removing start', offset, trim_start, repr(data[:trim_start])
835
 
        if not end_adjacent:
836
 
            # work around python bug in rfind
837
 
            if trim_end is None:
838
 
                trim_end = data.rfind('\n') + 1
839
 
            else:
840
 
                trim_end = data.rfind('\n', None, trim_end) + 1
841
 
            assert trim_end != 0, 'no \n was present'
842
 
            # print 'removing end', offset, trim_end, repr(data[trim_end:])
843
 
        # adjust offset and data to the parseable data.
844
 
        trimmed_data = data[trim_start:trim_end]
845
 
        assert trimmed_data, 'read unneeded data [%d:%d] from [%d:%d]' % (
846
 
            trim_start, trim_end, offset, offset + len(data))
847
 
        if trim_start:
848
 
            offset += trim_start
849
 
        # print "parsing", repr(trimmed_data)
850
 
        # splitlines mangles the \r delimiters.. don't use it.
851
 
        lines = trimmed_data.split('\n')
852
 
        del lines[-1]
853
 
        pos = offset
854
 
        first_key, last_key, nodes, _ = self._parse_lines(lines, pos)
855
 
        for key, value in nodes:
856
 
            self._bisect_nodes[key] = value
857
 
        self._parsed_bytes(offset, first_key,
858
 
            offset + len(trimmed_data), last_key)
859
 
        return offset + len(trimmed_data), last_segment
860
 
 
861
 
    def _parse_lines(self, lines, pos):
862
 
        key = None
863
 
        first_key = None
864
 
        trailers = 0
865
 
        nodes = []
866
 
        for line in lines:
867
 
            if line == '':
868
 
                # must be at the end
869
 
                if self._size:
870
 
                    assert self._size == pos + 1, "%s %s" % (self._size, pos)
871
 
                trailers += 1
872
 
                continue
873
 
            elements = line.split('\0')
874
 
            if len(elements) != self._expected_elements:
875
 
                raise errors.BadIndexData(self)
876
 
            # keys are tuples
877
 
            key = tuple(elements[:self._key_length])
878
 
            if first_key is None:
879
 
                first_key = key
880
 
            absent, references, value = elements[-3:]
881
 
            ref_lists = []
882
 
            for ref_string in references.split('\t'):
883
 
                ref_lists.append(tuple([
884
 
                    int(ref) for ref in ref_string.split('\r') if ref
885
 
                    ]))
886
 
            ref_lists = tuple(ref_lists)
887
 
            self._keys_by_offset[pos] = (key, absent, ref_lists, value)
888
 
            pos += len(line) + 1 # +1 for the \n
889
 
            if absent:
890
 
                continue
891
 
            if self.node_ref_lists:
892
 
                node_value = (value, ref_lists)
893
 
            else:
894
 
                node_value = value
895
 
            nodes.append((key, node_value))
896
 
            # print "parsed ", key
897
 
        return first_key, key, nodes, trailers
898
 
 
899
 
    def _parsed_bytes(self, start, start_key, end, end_key):
900
 
        """Mark the bytes from start to end as parsed.
901
 
 
902
 
        Calling self._parsed_bytes(1,2) will mark one byte (the one at offset
903
 
        1) as parsed.
904
 
 
905
 
        :param start: The start of the parsed region.
906
 
        :param end: The end of the parsed region.
907
 
        """
908
 
        index = self._parsed_byte_index(start)
909
 
        new_value = (start, end)
910
 
        new_key = (start_key, end_key)
911
 
        if index == -1:
912
 
            # first range parsed is always the beginning.
913
 
            self._parsed_byte_map.insert(index, new_value)
914
 
            self._parsed_key_map.insert(index, new_key)
915
 
            return
916
 
        # four cases:
917
 
        # new region
918
 
        # extend lower region
919
 
        # extend higher region
920
 
        # combine two regions
921
 
        if (index + 1 < len(self._parsed_byte_map) and
922
 
            self._parsed_byte_map[index][1] == start and
923
 
            self._parsed_byte_map[index + 1][0] == end):
924
 
            # combine two regions
925
 
            self._parsed_byte_map[index] = (self._parsed_byte_map[index][0],
926
 
                self._parsed_byte_map[index + 1][1])
927
 
            self._parsed_key_map[index] = (self._parsed_key_map[index][0],
928
 
                self._parsed_key_map[index + 1][1])
929
 
            del self._parsed_byte_map[index + 1]
930
 
            del self._parsed_key_map[index + 1]
931
 
        elif self._parsed_byte_map[index][1] == start:
932
 
            # extend the lower entry
933
 
            self._parsed_byte_map[index] = (
934
 
                self._parsed_byte_map[index][0], end)
935
 
            self._parsed_key_map[index] = (
936
 
                self._parsed_key_map[index][0], end_key)
937
 
        elif (index + 1 < len(self._parsed_byte_map) and
938
 
            self._parsed_byte_map[index + 1][0] == end):
939
 
            # extend the higher entry
940
 
            self._parsed_byte_map[index + 1] = (
941
 
                start, self._parsed_byte_map[index + 1][1])
942
 
            self._parsed_key_map[index + 1] = (
943
 
                start_key, self._parsed_key_map[index + 1][1])
944
 
        else:
945
 
            # new entry
946
 
            self._parsed_byte_map.insert(index + 1, new_value)
947
 
            self._parsed_key_map.insert(index + 1, new_key)
948
 
 
949
 
    def _read_and_parse(self, readv_ranges):
950
 
        """Read the the ranges and parse the resulting data.
951
 
 
952
 
        :param readv_ranges: A prepared readv range list.
953
 
        """
954
 
        if readv_ranges:
955
 
            readv_data = self._transport.readv(self._name, readv_ranges, True,
956
 
                self._size)
957
 
            # parse
958
 
            for offset, data in readv_data:
959
 
                if self._bisect_nodes is None:
960
 
                    # this must be the start
961
 
                    assert offset == 0
962
 
                    offset, data = self._parse_header_from_bytes(data)
963
 
                # print readv_ranges, "[%d:%d]" % (offset, offset + len(data))
964
 
                self._parse_region(offset, data)
965
 
 
966
435
    def _signature(self):
967
436
        """The file signature for this index type."""
968
437
        return _SIGNATURE
994
463
        """
995
464
        self._indices = indices
996
465
 
997
 
    def __repr__(self):
998
 
        return "%s(%s)" % (
999
 
                self.__class__.__name__,
1000
 
                ', '.join(map(repr, self._indices)))
1001
 
 
1002
 
    @symbol_versioning.deprecated_method(symbol_versioning.one_one)
1003
 
    def get_parents(self, revision_ids):
1004
 
        """See graph._StackedParentsProvider.get_parents.
1005
 
        
1006
 
        This implementation thunks the graph.Graph.get_parents api across to
1007
 
        GraphIndex.
1008
 
 
1009
 
        :param revision_ids: An iterable of graph keys for this graph.
1010
 
        :return: A list of parent details for each key in revision_ids.
1011
 
            Each parent details will be one of:
1012
 
             * None when the key was missing
1013
 
             * (NULL_REVISION,) when the key has no parents.
1014
 
             * (parent_key, parent_key...) otherwise.
1015
 
        """
1016
 
        parent_map = self.get_parent_map(revision_ids)
1017
 
        return [parent_map.get(r, None) for r in revision_ids]
1018
 
 
1019
 
    def get_parent_map(self, keys):
1020
 
        """See graph._StackedParentsProvider.get_parent_map"""
1021
 
        search_keys = set(keys)
1022
 
        if NULL_REVISION in search_keys:
1023
 
            search_keys.discard(NULL_REVISION)
1024
 
            found_parents = {NULL_REVISION:[]}
1025
 
        else:
1026
 
            found_parents = {}
1027
 
        for index, key, value, refs in self.iter_entries(search_keys):
1028
 
            parents = refs[0]
1029
 
            if not parents:
1030
 
                parents = (NULL_REVISION,)
1031
 
            found_parents[key] = parents
1032
 
        return found_parents
1033
 
 
1034
466
    def insert_index(self, pos, index):
1035
467
        """Insert a new index in the list of indices to query.
1036
468
 
1045
477
        Duplicate keys across child indices are presumed to have the same
1046
478
        value and are only reported once.
1047
479
 
1048
 
        :return: An iterable of (index, key, reference_lists, value).
1049
 
            There is no defined order for the result iteration - it will be in
1050
 
            the most efficient order for the index.
 
480
        :return: An iterable of (key, reference_lists, value). There is no
 
481
            defined order for the result iteration - it will be in the most
 
482
            efficient order for the index.
1051
483
        """
1052
484
        seen_keys = set()
1053
485
        for index in self._indices:
1063
495
        value and are only reported once.
1064
496
 
1065
497
        :param keys: An iterable providing the keys to be retrieved.
1066
 
        :return: An iterable of (index, key, reference_lists, value). There is no
 
498
        :return: An iterable of (key, reference_lists, value). There is no
1067
499
            defined order for the result iteration - it will be in the most
1068
500
            efficient order for the index.
1069
501
        """
1106
538
                seen_keys.add(node[1])
1107
539
                yield node
1108
540
 
1109
 
    def key_count(self):
1110
 
        """Return an estimate of the number of keys in this index.
1111
 
        
1112
 
        For CombinedGraphIndex this is approximated by the sum of the keys of
1113
 
        the child indices. As child indices may have duplicate keys this can
1114
 
        have a maximum error of the number of child indices * largest number of
1115
 
        keys in any index.
1116
 
        """
1117
 
        return sum((index.key_count() for index in self._indices), 0)
1118
 
 
1119
541
    def validate(self):
1120
542
        """Validate that everything in the index can be accessed."""
1121
543
        for index in self._indices:
1145
567
    def iter_all_entries(self):
1146
568
        """Iterate over all keys within the index
1147
569
 
1148
 
        :return: An iterable of (index, key, reference_lists, value). There is no
 
570
        :return: An iterable of (key, reference_lists, value). There is no
1149
571
            defined order for the result iteration - it will be in the most
1150
572
            efficient order for the index (in this case dictionary hash order).
1151
573
        """
1152
 
        if 'evil' in debug.debug_flags:
1153
 
            trace.mutter_callsite(3,
1154
 
                "iter_all_entries scales with size of history.")
1155
574
        if self.reference_lists:
1156
575
            for key, (absent, references, value) in self._nodes.iteritems():
1157
576
                if not absent:
1165
584
        """Iterate over keys within the index.
1166
585
 
1167
586
        :param keys: An iterable providing the keys to be retrieved.
1168
 
        :return: An iterable of (index, key, value, reference_lists). There is no
 
587
        :return: An iterable of (key, reference_lists, value). There is no
1169
588
            defined order for the result iteration - it will be in the most
1170
589
            efficient order for the index (keys iteration order in this case).
1171
590
        """
1172
591
        keys = set(keys)
1173
592
        if self.reference_lists:
1174
 
            for key in keys.intersection(self._keys):
 
593
            for key in keys.intersection(self._nodes):
1175
594
                node = self._nodes[key]
1176
595
                if not node[0]:
1177
596
                    yield self, key, node[2], node[1]
1178
597
        else:
1179
 
            for key in keys.intersection(self._keys):
 
598
            for key in keys.intersection(self._nodes):
1180
599
                node = self._nodes[key]
1181
600
                if not node[0]:
1182
601
                    yield self, key, node[2]
1216
635
                if self.reference_lists:
1217
636
                    yield self, key, node[2], node[1]
1218
637
                else:
1219
 
                    yield self, key, node[2]
 
638
                    yield self ,key, node[2]
1220
639
            return
1221
640
        for key in keys:
1222
641
            # sanity check
1251
670
            else:
1252
671
                yield (self, ) + key_dict
1253
672
 
1254
 
    def key_count(self):
1255
 
        """Return an estimate of the number of keys in this index.
1256
 
        
1257
 
        For InMemoryGraphIndex the estimate is exact.
1258
 
        """
1259
 
        return len(self._keys)
1260
 
 
1261
673
    def validate(self):
1262
674
        """In memory index's have no known corruption at the moment."""
1263
675
 
1272
684
    nodes and references being added will have prefix prepended.
1273
685
    """
1274
686
 
1275
 
    def __init__(self, adapted, prefix, missing_key_length,
1276
 
        add_nodes_callback=None):
 
687
    def __init__(self, adapted, prefix, missing_key_length, add_nodes_callback=None):
1277
688
        """Construct an adapter against adapted with prefix."""
1278
689
        self.adapted = adapted
1279
 
        self.prefix_key = prefix + (None,)*missing_key_length
1280
 
        self.prefix = prefix
 
690
        self.prefix = prefix + (None,)*missing_key_length
 
691
        self.prefix_key = prefix
1281
692
        self.prefix_len = len(prefix)
1282
693
        self.add_nodes_callback = add_nodes_callback
1283
694
 
1290
701
        nodes = tuple(nodes)
1291
702
        translated_nodes = []
1292
703
        try:
1293
 
            # Add prefix_key to each reference node_refs is a tuple of tuples,
1294
 
            # so split it apart, and add prefix_key to the internal reference
1295
704
            for (key, value, node_refs) in nodes:
1296
705
                adjusted_references = (
1297
 
                    tuple(tuple(self.prefix + ref_node for ref_node in ref_list)
 
706
                    tuple(tuple(self.prefix_key + ref_node for ref_node in ref_list)
1298
707
                        for ref_list in node_refs))
1299
 
                translated_nodes.append((self.prefix + key, value,
 
708
                translated_nodes.append((self.prefix_key + key, value,
1300
709
                    adjusted_references))
1301
710
        except ValueError:
1302
711
            # XXX: TODO add an explicit interface for getting the reference list
1303
712
            # status, to handle this bit of user-friendliness in the API more 
1304
713
            # explicitly.
1305
714
            for (key, value) in nodes:
1306
 
                translated_nodes.append((self.prefix + key, value))
 
715
                translated_nodes.append((self.prefix_key + key, value))
1307
716
        self.add_nodes_callback(translated_nodes)
1308
717
 
1309
718
    def add_node(self, key, value, references=()):
1323
732
        """Strip prefix data from nodes and return it."""
1324
733
        for node in an_iter:
1325
734
            # cross checks
1326
 
            if node[1][:self.prefix_len] != self.prefix:
 
735
            if node[1][:self.prefix_len] != self.prefix_key:
1327
736
                raise errors.BadIndexData(self)
1328
737
            for ref_list in node[3]:
1329
738
                for ref_node in ref_list:
1330
 
                    if ref_node[:self.prefix_len] != self.prefix:
 
739
                    if ref_node[:self.prefix_len] != self.prefix_key:
1331
740
                        raise errors.BadIndexData(self)
1332
741
            yield node[0], node[1][self.prefix_len:], node[2], (
1333
742
                tuple(tuple(ref_node[self.prefix_len:] for ref_node in ref_list)
1339
748
        iter_all_entries is implemented against the adapted index using
1340
749
        iter_entries_prefix.
1341
750
 
1342
 
        :return: An iterable of (index, key, reference_lists, value). There is no
 
751
        :return: An iterable of (key, reference_lists, value). There is no
1343
752
            defined order for the result iteration - it will be in the most
1344
753
            efficient order for the index (in this case dictionary hash order).
1345
754
        """
1346
 
        return self._strip_prefix(self.adapted.iter_entries_prefix([self.prefix_key]))
 
755
        return self._strip_prefix(self.adapted.iter_entries_prefix([self.prefix]))
1347
756
 
1348
757
    def iter_entries(self, keys):
1349
758
        """Iterate over keys within the index.
1350
759
 
1351
760
        :param keys: An iterable providing the keys to be retrieved.
1352
 
        :return: An iterable of (index, key, value, reference_lists). There is no
 
761
        :return: An iterable of (key, reference_lists, value). There is no
1353
762
            defined order for the result iteration - it will be in the most
1354
763
            efficient order for the index (keys iteration order in this case).
1355
764
        """
1356
765
        return self._strip_prefix(self.adapted.iter_entries(
1357
 
            self.prefix + key for key in keys))
 
766
            self.prefix_key + key for key in keys))
1358
767
 
1359
768
    def iter_entries_prefix(self, keys):
1360
769
        """Iterate over keys within the index using prefix matching.
1374
783
            returned.
1375
784
        """
1376
785
        return self._strip_prefix(self.adapted.iter_entries_prefix(
1377
 
            self.prefix + key for key in keys))
1378
 
 
1379
 
    def key_count(self):
1380
 
        """Return an estimate of the number of keys in this index.
1381
 
        
1382
 
        For GraphIndexPrefixAdapter this is relatively expensive - key
1383
 
        iteration with the prefix is done.
1384
 
        """
1385
 
        return len(list(self.iter_all_entries()))
 
786
            self.prefix_key + key for key in keys))
1386
787
 
1387
788
    def validate(self):
1388
789
        """Call the adapted's validate."""