/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/btree_index.py

  • Committer: Jelmer Vernooij
  • Author(s): Richard Wilbur
  • Date: 2017-05-30 23:37:11 UTC
  • mto: This revision was merged to the branch mainline in revision 6645.
  • Revision ID: jelmer@jelmer.uk-20170530233711-r0m0qp8hpkqzpopw
https://launchpad.net/bugs/1537319
Fix order in which files are processed.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/btree_index.py
1
 
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 2008-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
17
17
 
18
18
"""B+Tree indices"""
19
19
 
20
 
import cStringIO
21
 
from bisect import bisect_right
 
20
from __future__ import absolute_import
 
21
 
 
22
from .lazy_import import lazy_import
 
23
lazy_import(globals(), """
 
24
import bisect
22
25
import math
23
26
import tempfile
24
27
import zlib
 
28
""")
25
29
 
26
 
from bzrlib import (
 
30
from . import (
27
31
    chunk_writer,
28
32
    debug,
29
33
    errors,
33
37
    osutils,
34
38
    static_tuple,
35
39
    trace,
36
 
    )
37
 
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
38
 
from bzrlib.transport import get_transport
 
40
    transport,
 
41
    )
 
42
from .index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
 
43
from .sixish import (
 
44
    BytesIO,
 
45
    map,
 
46
    )
39
47
 
40
48
 
41
49
_BTSIGNATURE = "B+Tree Graph Index 2\n"
68
76
    def finish_node(self, pad=True):
69
77
        byte_lines, _, padding = self.writer.finish()
70
78
        if self.nodes == 0:
71
 
            self.spool = cStringIO.StringIO()
 
79
            self.spool = BytesIO()
72
80
            # padded note:
73
81
            self.spool.write("\x00" * _RESERVED_HEADER_BYTES)
74
82
        elif self.nodes == 1:
158
166
        :param references: An iterable of iterables of keys. Each is a
159
167
            reference to another key.
160
168
        :param value: The value to associate with the key. It may be any
161
 
            bytes as long as it does not contain \0 or \n.
 
169
            bytes as long as it does not contain \\0 or \\n.
162
170
        """
163
171
        # Ensure that 'key' is a StaticTuple
164
172
        key = static_tuple.StaticTuple.from_sequence(key).intern()
193
201
            new_backing_file, size = self._spill_mem_keys_without_combining()
194
202
        # Note: The transport here isn't strictly needed, because we will use
195
203
        #       direct access to the new_backing._file object
196
 
        new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)
 
204
        new_backing = BTreeGraphIndex(transport.get_transport_from_path('.'),
 
205
                                      '<temp>', size)
197
206
        # GC will clean up the file
198
207
        new_backing._file = new_backing_file
199
208
        if self._combine_backing_indices:
256
265
        current_values = []
257
266
        for iterator in iterators_to_combine:
258
267
            try:
259
 
                current_values.append(iterator.next())
 
268
                current_values.append(next(iterator))
260
269
            except StopIteration:
261
270
                current_values.append(None)
262
271
        last = None
276
285
            yield (self,) + selected[1][1:]
277
286
            pos = selected[0]
278
287
            try:
279
 
                current_values[pos] = iterators_to_combine[pos].next()
 
288
                current_values[pos] = next(iterators_to_combine[pos])
280
289
            except StopIteration:
281
290
                current_values[pos] = None
282
291
 
289
298
            flag when writing out. This is used by the _spill_mem_keys_to_disk
290
299
            functionality.
291
300
        """
 
301
        new_leaf = False
292
302
        if rows[-1].writer is None:
293
303
            # opening a new leaf chunk;
 
304
            new_leaf = True
294
305
            for pos, internal_row in enumerate(rows[:-1]):
295
306
                # flesh out any internal nodes that are needed to
296
307
                # preserve the height of the tree
315
326
                optimize_for_size=self._optimize_for_size)
316
327
            rows[-1].writer.write(_LEAF_FLAG)
317
328
        if rows[-1].writer.write(line):
 
329
            # if we failed to write, despite having an empty page to write to,
 
330
            # then line is too big. raising the error avoids infinite recursion
 
331
            # searching for a suitably large page that will not be found.
 
332
            if new_leaf:
 
333
                raise errors.BadIndexKey(string_key)
318
334
            # this key did not fit in the node:
319
335
            rows[-1].finish_node()
320
336
            key_line = string_key + "\n"
383
399
                                    self.reference_lists)
384
400
            self._add_key(string_key, line, rows, allow_optimize=allow_optimize)
385
401
        for row in reversed(rows):
386
 
            pad = (type(row) != _LeafBuilderRow)
 
402
            pad = (not isinstance(row, _LeafBuilderRow))
387
403
            row.finish_node(pad=pad)
388
404
        lines = [_BTSIGNATURE]
389
405
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
394
410
        if row_lengths and row_lengths[-1] > 1:
395
411
            result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
396
412
        else:
397
 
            result = cStringIO.StringIO()
 
413
            result = BytesIO()
398
414
        result.writelines(lines)
399
415
        position = sum(map(len, lines))
400
416
        root_row = True
416
432
            position = 0 # Only the root row actually has an offset
417
433
            copied_len = osutils.pumpfile(row.spool, result)
418
434
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
419
 
                if type(row) != _LeafBuilderRow:
 
435
                if not isinstance(row, _LeafBuilderRow):
420
436
                    raise AssertionError("Incorrect amount of data copied"
421
437
                        " expected: %d, got: %d"
422
438
                        % ((row.nodes - 1) * _PAGE_SIZE,
560
576
                while dicts:
561
577
                    key_dict = dicts.pop(-1)
562
578
                    # can't be empty or would not exist
563
 
                    item, value = key_dict.iteritems().next()
564
 
                    if type(value) == dict:
 
579
                    item, value = next(key_dict.iteritems())
 
580
                    if isinstance(value, dict):
565
581
                        # push keys
566
582
                        dicts.extend(key_dict.itervalues())
567
583
                    else:
601
617
        """In memory index's have no known corruption at the moment."""
602
618
 
603
619
 
604
 
class _LeafNode(object):
 
620
class _LeafNode(dict):
605
621
    """A leaf node for a serialised B+Tree index."""
606
622
 
607
 
    __slots__ = ('keys', 'min_key', 'max_key')
 
623
    __slots__ = ('min_key', 'max_key', '_keys')
608
624
 
609
625
    def __init__(self, bytes, key_length, ref_list_length):
610
626
        """Parse bytes to create a leaf node object."""
616
632
            self.max_key = key_list[-1][0]
617
633
        else:
618
634
            self.min_key = self.max_key = None
619
 
        self.keys = dict(key_list)
 
635
        super(_LeafNode, self).__init__(key_list)
 
636
        self._keys = dict(self)
 
637
 
 
638
    def all_items(self):
 
639
        """Return a sorted list of (key, (value, refs)) items"""
 
640
        items = sorted(self.items())
 
641
        return items
 
642
 
 
643
    def all_keys(self):
 
644
        """Return a sorted list of all keys."""
 
645
        keys = sorted(self.keys())
 
646
        return keys
620
647
 
621
648
 
622
649
class _InternalNode(object):
636
663
        for line in lines[2:]:
637
664
            if line == '':
638
665
                break
639
 
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
 
666
            # GZ 2017-05-24: Used to intern() each chunk of line as well, need
 
667
            # to recheck performance and perhaps adapt StaticTuple to adjust.
 
668
            nodes.append(as_st(line.split(b'\0')).intern())
640
669
        return nodes
641
670
 
642
671
 
671
700
        self._recommended_pages = self._compute_recommended_pages()
672
701
        self._root_node = None
673
702
        self._base_offset = offset
 
703
        self._leaf_factory = _LeafNode
674
704
        # Default max size is 100,000 leave values
675
705
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
676
706
        if unlimited_cache:
689
719
    def __eq__(self, other):
690
720
        """Equal when self and other were created with the same parameters."""
691
721
        return (
692
 
            type(self) == type(other) and
 
722
            isinstance(self, type(other)) and
693
723
            self._transport == other._transport and
694
724
            self._name == other._name and
695
725
            self._size == other._size)
949
979
        """Cache directly from key => value, skipping the btree."""
950
980
        if self._leaf_value_cache is not None:
951
981
            for node in nodes.itervalues():
952
 
                for key, value in node.keys.iteritems():
 
982
                for key, value in node.all_items():
953
983
                    if key in self._leaf_value_cache:
954
984
                        # Don't add the rest of the keys, we've seen this node
955
985
                        # before.
979
1009
        if self._row_offsets[-1] == 1:
980
1010
            # There is only the root node, and we read that via key_count()
981
1011
            if self.node_ref_lists:
982
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1012
                for key, (value, refs) in self._root_node.all_items():
983
1013
                    yield (self, key, value, refs)
984
1014
            else:
985
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1015
                for key, (value, refs) in self._root_node.all_items():
986
1016
                    yield (self, key, value)
987
1017
            return
988
1018
        start_of_leaves = self._row_offsets[-2]
998
1028
        # for spilling index builds to disk.
999
1029
        if self.node_ref_lists:
1000
1030
            for _, node in nodes:
1001
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1031
                for key, (value, refs) in node.all_items():
1002
1032
                    yield (self, key, value, refs)
1003
1033
        else:
1004
1034
            for _, node in nodes:
1005
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1035
                for key, (value, refs) in node.all_items():
1006
1036
                    yield (self, key, value)
1007
1037
 
1008
1038
    @staticmethod
1032
1062
        # iter_steps = len(in_keys) + len(fixed_keys)
1033
1063
        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1034
1064
        if len(in_keys) == 1: # Bisect will always be faster for M = 1
1035
 
            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
 
1065
            return [(bisect.bisect_right(fixed_keys, in_keys[0]), in_keys)]
1036
1066
        # elif bisect_steps < iter_steps:
1037
1067
        #     offsets = {}
1038
1068
        #     for key in in_keys:
1041
1071
        #     return [(o, offsets[o]) for o in sorted(offsets)]
1042
1072
        in_keys_iter = iter(in_keys)
1043
1073
        fixed_keys_iter = enumerate(fixed_keys)
1044
 
        cur_in_key = in_keys_iter.next()
1045
 
        cur_fixed_offset, cur_fixed_key = fixed_keys_iter.next()
 
1074
        cur_in_key = next(in_keys_iter)
 
1075
        cur_fixed_offset, cur_fixed_key = next(fixed_keys_iter)
1046
1076
 
1047
1077
        class InputDone(Exception): pass
1048
1078
        class FixedDone(Exception): pass
1064
1094
                    while cur_in_key < cur_fixed_key:
1065
1095
                        cur_keys.append(cur_in_key)
1066
1096
                        try:
1067
 
                            cur_in_key = in_keys_iter.next()
 
1097
                            cur_in_key = next(in_keys_iter)
1068
1098
                        except StopIteration:
1069
1099
                            raise InputDone
1070
1100
                    # At this point cur_in_key must be >= cur_fixed_key
1072
1102
                # the end
1073
1103
                while cur_in_key >= cur_fixed_key:
1074
1104
                    try:
1075
 
                        cur_fixed_offset, cur_fixed_key = fixed_keys_iter.next()
 
1105
                        cur_fixed_offset, cur_fixed_key = next(fixed_keys_iter)
1076
1106
                    except StopIteration:
1077
1107
                        raise FixedDone
1078
1108
        except InputDone:
1169
1199
                continue
1170
1200
            node = nodes[node_index]
1171
1201
            for next_sub_key in sub_keys:
1172
 
                if next_sub_key in node.keys:
1173
 
                    value, refs = node.keys[next_sub_key]
 
1202
                if next_sub_key in node:
 
1203
                    value, refs = node[next_sub_key]
1174
1204
                    if self.node_ref_lists:
1175
1205
                        yield (self, next_sub_key, value, refs)
1176
1206
                    else:
1244
1274
            # sub_keys is all of the keys we are looking for that should exist
1245
1275
            # on this page, if they aren't here, then they won't be found
1246
1276
            node = nodes[node_index]
1247
 
            node_keys = node.keys
1248
1277
            parents_to_check = set()
1249
1278
            for next_sub_key in sub_keys:
1250
 
                if next_sub_key not in node_keys:
 
1279
                if next_sub_key not in node:
1251
1280
                    # This one is just not present in the index at all
1252
1281
                    missing_keys.add(next_sub_key)
1253
1282
                else:
1254
 
                    value, refs = node_keys[next_sub_key]
 
1283
                    value, refs = node[next_sub_key]
1255
1284
                    parent_keys = refs[ref_list_num]
1256
1285
                    parent_map[next_sub_key] = parent_keys
1257
1286
                    parents_to_check.update(parent_keys)
1264
1293
            while parents_to_check:
1265
1294
                next_parents_to_check = set()
1266
1295
                for key in parents_to_check:
1267
 
                    if key in node_keys:
1268
 
                        value, refs = node_keys[key]
 
1296
                    if key in node:
 
1297
                        value, refs = node[key]
1269
1298
                        parent_keys = refs[ref_list_num]
1270
1299
                        parent_map[key] = parent_keys
1271
1300
                        next_parents_to_check.update(parent_keys)
1333
1362
            self._get_root_node()
1334
1363
        # TODO: only access nodes that can satisfy the prefixes we are looking
1335
1364
        # for. For now, to meet API usage (as this function is not used by
1336
 
        # current bzrlib) just suck the entire index and iterate in memory.
 
1365
        # current breezy) just suck the entire index and iterate in memory.
1337
1366
        nodes = {}
1338
1367
        if self.node_ref_lists:
1339
1368
            if self._key_length == 1:
1401
1430
                while dicts:
1402
1431
                    key_dict = dicts.pop(-1)
1403
1432
                    # can't be empty or would not exist
1404
 
                    item, value = key_dict.iteritems().next()
1405
 
                    if type(value) == dict:
 
1433
                    item, value = next(key_dict.iteritems())
 
1434
                    if isinstance(value, dict):
1406
1435
                        # push keys
1407
1436
                        dicts.extend(key_dict.itervalues())
1408
1437
                    else:
1471
1500
        if not options_line.startswith(_OPTION_ROW_LENGTHS):
1472
1501
            raise errors.BadIndexOptions(self)
1473
1502
        try:
1474
 
            self._row_lengths = map(int, [length for length in
 
1503
            self._row_lengths = [int(length) for length in
1475
1504
                options_line[len(_OPTION_ROW_LENGTHS):].split(',')
1476
 
                if len(length)])
 
1505
                if length]
1477
1506
        except ValueError:
1478
1507
            raise errors.BadIndexOptions(self)
1479
1508
        self._compute_row_offsets()
1545
1574
                    continue
1546
1575
            bytes = zlib.decompress(data)
1547
1576
            if bytes.startswith(_LEAF_FLAG):
1548
 
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
 
1577
                node = self._leaf_factory(bytes, self._key_length,
 
1578
                                          self.node_ref_lists)
1549
1579
            elif bytes.startswith(_INTERNAL_FLAG):
1550
1580
                node = _InternalNode(bytes)
1551
1581
            else:
1570
1600
            pass
1571
1601
 
1572
1602
 
 
1603
_gcchk_factory = _LeafNode
 
1604
 
1573
1605
try:
1574
 
    from bzrlib import _btree_serializer_pyx as _btree_serializer
1575
 
except ImportError, e:
 
1606
    from breezy import _btree_serializer_pyx as _btree_serializer
 
1607
    _gcchk_factory = _btree_serializer._parse_into_chk
 
1608
except ImportError as e:
1576
1609
    osutils.failed_to_load_extension(e)
1577
 
    from bzrlib import _btree_serializer_py as _btree_serializer
 
1610
    from breezy import _btree_serializer_py as _btree_serializer