← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

terminal_width can now returns None.

* bzrlib/win32utils.py:
(get_console_size): Fix typo in comment.

* bzrlib/ui/text.py:
(TextProgressView._show_line): Handle the no terminal present case.

* bzrlib/tests/test_osutils.py:
(TestTerminalWidth): Update tests.

* bzrlib/tests/blackbox/test_too_much.py:
Fix some imports.
(OldTests.test_bzr): Handle the no terminal present case.

* bzrlib/tests/__init__.py:
(VerboseTestResult.report_test_start): Handle the no terminal
present case.

* bzrlib/status.py:
(show_pending_merges): Handle the no terminal present case.
(show_pending_merges.show_log_message): Factor out some
code. Handle the no terminal present case.

* bzrlib/osutils.py:
(terminal_width): Return None if no precise value can be found.

* bzrlib/log.py:
(LineLogFormatter.__init__): Handle the no terminal present case.
(LineLogFormatter.truncate): Accept None as max_len meaning no
truncation.
(LineLogFormatter.log_string): 

* bzrlib/help.py:
(_help_commands_to_text): Handle the no terminal present case.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
1
 
# Copyright (C) 2008-2011 Canonical Ltd
 
1
# Copyright (C) 2008 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
18
18
"""B+Tree indices"""
19
19
 
20
20
import cStringIO
21
 
 
22
 
from bzrlib.lazy_import import lazy_import
23
 
lazy_import(globals(), """
24
 
import bisect
 
21
from bisect import bisect_right
25
22
import math
26
23
import tempfile
27
24
import zlib
28
 
""")
29
25
 
30
26
from bzrlib import (
31
27
    chunk_writer,
35
31
    index,
36
32
    lru_cache,
37
33
    osutils,
38
 
    static_tuple,
39
34
    trace,
40
 
    transport,
41
35
    )
42
36
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
 
37
from bzrlib.transport import get_transport
43
38
 
44
39
 
45
40
_BTSIGNATURE = "B+Tree Graph Index 2\n"
162
157
        :param references: An iterable of iterables of keys. Each is a
163
158
            reference to another key.
164
159
        :param value: The value to associate with the key. It may be any
165
 
            bytes as long as it does not contain \\0 or \\n.
 
160
            bytes as long as it does not contain \0 or \n.
166
161
        """
167
 
        # Ensure that 'key' is a StaticTuple
168
 
        key = static_tuple.StaticTuple.from_sequence(key).intern()
169
162
        # we don't care about absent_references
170
163
        node_refs, _ = self._check_key_ref_value(key, references, value)
171
164
        if key in self._nodes:
172
165
            raise errors.BadIndexDuplicateKey(key, self)
173
 
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
 
166
        self._nodes[key] = (node_refs, value)
 
167
        self._keys.add(key)
174
168
        if self._nodes_by_key is not None and self._key_length > 1:
175
169
            self._update_nodes_by_key(key, value, node_refs)
176
 
        if len(self._nodes) < self._spill_at:
 
170
        if len(self._keys) < self._spill_at:
177
171
            return
178
172
        self._spill_mem_keys_to_disk()
179
173
 
197
191
            new_backing_file, size = self._spill_mem_keys_without_combining()
198
192
        # Note: The transport here isn't strictly needed, because we will use
199
193
        #       direct access to the new_backing._file object
200
 
        new_backing = BTreeGraphIndex(transport.get_transport('.'),
201
 
                                      '<temp>', size)
 
194
        new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)
202
195
        # GC will clean up the file
203
196
        new_backing._file = new_backing_file
204
197
        if self._combine_backing_indices:
209
202
                self._backing_indices[backing_pos] = None
210
203
        else:
211
204
            self._backing_indices.append(new_backing)
 
205
        self._keys = set()
212
206
        self._nodes = {}
213
207
        self._nodes_by_key = None
214
208
 
416
410
            # Special case the first node as it may be prefixed
417
411
            node = row.spool.read(_PAGE_SIZE)
418
412
            result.write(node[reserved:])
419
 
            if len(node) == _PAGE_SIZE:
420
 
                result.write("\x00" * (reserved - position))
 
413
            result.write("\x00" * (reserved - position))
421
414
            position = 0 # Only the root row actually has an offset
422
415
            copied_len = osutils.pumpfile(row.spool, result)
423
416
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
468
461
            efficient order for the index (keys iteration order in this case).
469
462
        """
470
463
        keys = set(keys)
471
 
        # Note: We don't use keys.intersection() here. If you read the C api,
472
 
        #       set.intersection(other) special cases when other is a set and
473
 
        #       will iterate the smaller of the two and lookup in the other.
474
 
        #       It does *not* do this for any other type (even dict, unlike
475
 
        #       some other set functions.) Since we expect keys is generally <<
476
 
        #       self._nodes, it is faster to iterate over it in a list
477
 
        #       comprehension
478
 
        nodes = self._nodes
479
 
        local_keys = [key for key in keys if key in nodes]
 
464
        local_keys = keys.intersection(self._keys)
480
465
        if self.reference_lists:
481
466
            for key in local_keys:
482
 
                node = nodes[key]
 
467
                node = self._nodes[key]
483
468
                yield self, key, node[1], node[0]
484
469
        else:
485
470
            for key in local_keys:
486
 
                node = nodes[key]
 
471
                node = self._nodes[key]
487
472
                yield self, key, node[1]
488
473
        # Find things that are in backing indices that have not been handled
489
474
        # yet.
572
557
                    else:
573
558
                        # yield keys
574
559
                        for value in key_dict.itervalues():
575
 
                            yield (self, ) + tuple(value)
 
560
                            yield (self, ) + value
576
561
            else:
577
562
                yield (self, ) + key_dict
578
563
 
599
584
 
600
585
        For InMemoryGraphIndex the estimate is exact.
601
586
        """
602
 
        return len(self._nodes) + sum(backing.key_count() for backing in
 
587
        return len(self._keys) + sum(backing.key_count() for backing in
603
588
            self._backing_indices if backing is not None)
604
589
 
605
590
    def validate(self):
606
591
        """In memory index's have no known corruption at the moment."""
607
592
 
608
593
 
609
 
class _LeafNode(dict):
 
594
class _LeafNode(object):
610
595
    """A leaf node for a serialised B+Tree index."""
611
596
 
612
 
    __slots__ = ('min_key', 'max_key', '_keys')
 
597
    __slots__ = ('keys', 'min_key', 'max_key')
613
598
 
614
599
    def __init__(self, bytes, key_length, ref_list_length):
615
600
        """Parse bytes to create a leaf node object."""
621
606
            self.max_key = key_list[-1][0]
622
607
        else:
623
608
            self.min_key = self.max_key = None
624
 
        super(_LeafNode, self).__init__(key_list)
625
 
        self._keys = dict(self)
626
 
 
627
 
    def all_items(self):
628
 
        """Return a sorted list of (key, (value, refs)) items"""
629
 
        items = self.items()
630
 
        items.sort()
631
 
        return items
632
 
 
633
 
    def all_keys(self):
634
 
        """Return a sorted list of all keys."""
635
 
        keys = self.keys()
636
 
        keys.sort()
637
 
        return keys
 
609
        self.keys = dict(key_list)
638
610
 
639
611
 
640
612
class _InternalNode(object):
650
622
    def _parse_lines(self, lines):
651
623
        nodes = []
652
624
        self.offset = int(lines[1][7:])
653
 
        as_st = static_tuple.StaticTuple.from_sequence
654
625
        for line in lines[2:]:
655
626
            if line == '':
656
627
                break
657
 
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
 
628
            nodes.append(tuple(map(intern, line.split('\0'))))
658
629
        return nodes
659
630
 
660
631
 
665
636
    memory except when very large walks are done.
666
637
    """
667
638
 
668
 
    def __init__(self, transport, name, size, unlimited_cache=False,
669
 
                 offset=0):
 
639
    def __init__(self, transport, name, size, unlimited_cache=False):
670
640
        """Create a B+Tree index object on the index name.
671
641
 
672
642
        :param transport: The transport to read data for the index from.
679
649
        :param unlimited_cache: If set to True, then instead of using an
680
650
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
681
651
            cache all leaf nodes.
682
 
        :param offset: The start of the btree index data isn't byte 0 of the
683
 
            file. Instead it starts at some point later.
684
652
        """
685
653
        self._transport = transport
686
654
        self._name = name
688
656
        self._file = None
689
657
        self._recommended_pages = self._compute_recommended_pages()
690
658
        self._root_node = None
691
 
        self._base_offset = offset
692
 
        self._leaf_factory = _LeafNode
693
659
        # Default max size is 100,000 leave values
694
660
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
695
661
        if unlimited_cache:
885
851
            new_tips = next_tips
886
852
        return final_offsets
887
853
 
888
 
    def clear_cache(self):
889
 
        """Clear out any cached/memoized values.
890
 
 
891
 
        This can be called at any time, but generally it is used when we have
892
 
        extracted some information, but don't expect to be requesting any more
893
 
        from this index.
894
 
        """
895
 
        # Note that we don't touch self._root_node or self._internal_node_cache
896
 
        # We don't expect either of those to be big, and it can save
897
 
        # round-trips in the future. We may re-evaluate this if InternalNode
898
 
        # memory starts to be an issue.
899
 
        self._leaf_node_cache.clear()
900
 
 
901
854
    def external_references(self, ref_list_num):
902
855
        if self._root_node is None:
903
856
            self._get_root_node()
968
921
        """Cache directly from key => value, skipping the btree."""
969
922
        if self._leaf_value_cache is not None:
970
923
            for node in nodes.itervalues():
971
 
                for key, value in node.all_items():
 
924
                for key, value in node.keys.iteritems():
972
925
                    if key in self._leaf_value_cache:
973
926
                        # Don't add the rest of the keys, we've seen this node
974
927
                        # before.
998
951
        if self._row_offsets[-1] == 1:
999
952
            # There is only the root node, and we read that via key_count()
1000
953
            if self.node_ref_lists:
1001
 
                for key, (value, refs) in self._root_node.all_items():
 
954
                for key, (value, refs) in sorted(self._root_node.keys.items()):
1002
955
                    yield (self, key, value, refs)
1003
956
            else:
1004
 
                for key, (value, refs) in self._root_node.all_items():
 
957
                for key, (value, refs) in sorted(self._root_node.keys.items()):
1005
958
                    yield (self, key, value)
1006
959
            return
1007
960
        start_of_leaves = self._row_offsets[-2]
1017
970
        # for spilling index builds to disk.
1018
971
        if self.node_ref_lists:
1019
972
            for _, node in nodes:
1020
 
                for key, (value, refs) in node.all_items():
 
973
                for key, (value, refs) in sorted(node.keys.items()):
1021
974
                    yield (self, key, value, refs)
1022
975
        else:
1023
976
            for _, node in nodes:
1024
 
                for key, (value, refs) in node.all_items():
 
977
                for key, (value, refs) in sorted(node.keys.items()):
1025
978
                    yield (self, key, value)
1026
979
 
1027
980
    @staticmethod
1051
1004
        # iter_steps = len(in_keys) + len(fixed_keys)
1052
1005
        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1053
1006
        if len(in_keys) == 1: # Bisect will always be faster for M = 1
1054
 
            return [(bisect.bisect_right(fixed_keys, in_keys[0]), in_keys)]
 
1007
            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
1055
1008
        # elif bisect_steps < iter_steps:
1056
1009
        #     offsets = {}
1057
1010
        #     for key in in_keys:
1188
1141
                continue
1189
1142
            node = nodes[node_index]
1190
1143
            for next_sub_key in sub_keys:
1191
 
                if next_sub_key in node:
1192
 
                    value, refs = node[next_sub_key]
 
1144
                if next_sub_key in node.keys:
 
1145
                    value, refs = node.keys[next_sub_key]
1193
1146
                    if self.node_ref_lists:
1194
1147
                        yield (self, next_sub_key, value, refs)
1195
1148
                    else:
1263
1216
            # sub_keys is all of the keys we are looking for that should exist
1264
1217
            # on this page, if they aren't here, then they won't be found
1265
1218
            node = nodes[node_index]
 
1219
            node_keys = node.keys
1266
1220
            parents_to_check = set()
1267
1221
            for next_sub_key in sub_keys:
1268
 
                if next_sub_key not in node:
 
1222
                if next_sub_key not in node_keys:
1269
1223
                    # This one is just not present in the index at all
1270
1224
                    missing_keys.add(next_sub_key)
1271
1225
                else:
1272
 
                    value, refs = node[next_sub_key]
 
1226
                    value, refs = node_keys[next_sub_key]
1273
1227
                    parent_keys = refs[ref_list_num]
1274
1228
                    parent_map[next_sub_key] = parent_keys
1275
1229
                    parents_to_check.update(parent_keys)
1282
1236
            while parents_to_check:
1283
1237
                next_parents_to_check = set()
1284
1238
                for key in parents_to_check:
1285
 
                    if key in node:
1286
 
                        value, refs = node[key]
 
1239
                    if key in node_keys:
 
1240
                        value, refs = node_keys[key]
1287
1241
                        parent_keys = refs[ref_list_num]
1288
1242
                        parent_map[key] = parent_keys
1289
1243
                        next_parents_to_check.update(parent_keys)
1516
1470
        # list of (offset, length) regions of the file that should, evenually
1517
1471
        # be read in to data_ranges, either from 'bytes' or from the transport
1518
1472
        ranges = []
1519
 
        base_offset = self._base_offset
1520
1473
        for index in nodes:
1521
 
            offset = (index * _PAGE_SIZE)
 
1474
            offset = index * _PAGE_SIZE
1522
1475
            size = _PAGE_SIZE
1523
1476
            if index == 0:
1524
1477
                # Root node - special case
1528
1481
                    # The only case where we don't know the size, is for very
1529
1482
                    # small indexes. So we read the whole thing
1530
1483
                    bytes = self._transport.get_bytes(self._name)
1531
 
                    num_bytes = len(bytes)
1532
 
                    self._size = num_bytes - base_offset
 
1484
                    self._size = len(bytes)
1533
1485
                    # the whole thing should be parsed out of 'bytes'
1534
 
                    ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
1535
 
                        for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
 
1486
                    ranges.append((0, len(bytes)))
1536
1487
                    break
1537
1488
            else:
1538
1489
                if offset > self._size:
1540
1491
                                         ' of the file %s > %s'
1541
1492
                                         % (offset, self._size))
1542
1493
                size = min(size, self._size - offset)
1543
 
            ranges.append((base_offset + offset, size))
 
1494
            ranges.append((offset, size))
1544
1495
        if not ranges:
1545
1496
            return
1546
1497
        elif bytes is not None:
1547
1498
            # already have the whole file
1548
 
            data_ranges = [(start, bytes[start:start+size])
1549
 
                           for start, size in ranges]
 
1499
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
 
1500
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
1550
1501
        elif self._file is None:
1551
1502
            data_ranges = self._transport.readv(self._name, ranges)
1552
1503
        else:
1555
1506
                self._file.seek(offset)
1556
1507
                data_ranges.append((offset, self._file.read(size)))
1557
1508
        for offset, data in data_ranges:
1558
 
            offset -= base_offset
1559
1509
            if offset == 0:
1560
1510
                # extract the header
1561
1511
                offset, data = self._parse_header_from_bytes(data)
1563
1513
                    continue
1564
1514
            bytes = zlib.decompress(data)
1565
1515
            if bytes.startswith(_LEAF_FLAG):
1566
 
                node = self._leaf_factory(bytes, self._key_length,
1567
 
                                          self.node_ref_lists)
 
1516
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
1568
1517
            elif bytes.startswith(_INTERNAL_FLAG):
1569
1518
                node = _InternalNode(bytes)
1570
1519
            else:
1589
1538
            pass
1590
1539
 
1591
1540
 
1592
 
_gcchk_factory = _LeafNode
1593
 
 
1594
1541
try:
1595
1542
    from bzrlib import _btree_serializer_pyx as _btree_serializer
1596
 
    _gcchk_factory = _btree_serializer._parse_into_chk
1597
1543
except ImportError, e:
1598
1544
    osutils.failed_to_load_extension(e)
1599
1545
    from bzrlib import _btree_serializer_py as _btree_serializer