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

  • Committer: Martin
  • Date: 2017-06-05 20:48:31 UTC
  • mto: This revision was merged to the branch mainline in revision 6658.
  • Revision ID: gzlist@googlemail.com-20170605204831-20accykspjcrx0a8
Apply 2to3 dict fixer and clean up resulting mess using view helpers

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/chk_map.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
37
37
 
38
38
"""
39
39
 
 
40
from __future__ import absolute_import
 
41
 
40
42
import heapq
41
43
import threading
42
44
 
43
 
from bzrlib import lazy_import
 
45
from . import lazy_import
44
46
lazy_import.lazy_import(globals(), """
45
 
from bzrlib import (
 
47
from breezy import (
46
48
    errors,
47
 
    versionedfile,
48
49
    )
49
50
""")
50
 
from bzrlib import (
 
51
from . import (
 
52
    errors,
51
53
    lru_cache,
52
54
    osutils,
53
55
    registry,
54
56
    static_tuple,
55
57
    trace,
56
58
    )
57
 
from bzrlib.static_tuple import StaticTuple
 
59
from .sixish import (
 
60
    viewitems,
 
61
    viewvalues,
 
62
    )
 
63
from .static_tuple import StaticTuple
58
64
 
59
65
# approx 4MB
60
66
# If each line is 50 bytes, and you have 255 internal pages, with 255-way fan
90
96
_INTERESTING_NEW_SIZE = 50
91
97
# If a ChildNode shrinks by more than this amount, we check for a remap
92
98
_INTERESTING_SHRINKAGE_LIMIT = 20
93
 
# If we delete more than this many nodes applying a delta, we check for a remap
94
 
_INTERESTING_DELETES_LIMIT = 5
95
99
 
96
100
 
97
101
def _search_key_plain(key):
135
139
            into the map; if old_key is not None, then the old mapping
136
140
            of old_key is removed.
137
141
        """
138
 
        delete_count = 0
 
142
        has_deletes = False
139
143
        # Check preconditions first.
140
144
        as_st = StaticTuple.from_sequence
141
 
        new_items = set([as_st(key) for (old, key, value) in delta
142
 
                         if key is not None and old is None])
 
145
        new_items = {as_st(key) for (old, key, value) in delta
 
146
                         if key is not None and old is None}
143
147
        existing_new = list(self.iteritems(key_filter=new_items))
144
148
        if existing_new:
145
149
            raise errors.InconsistentDeltaDelta(delta,
148
152
        for old, new, value in delta:
149
153
            if old is not None and old != new:
150
154
                self.unmap(old, check_remap=False)
151
 
                delete_count += 1
 
155
                has_deletes = True
152
156
        for old, new, value in delta:
153
157
            if new is not None:
154
158
                self.map(new, value)
155
 
        if delete_count > _INTERESTING_DELETES_LIMIT:
156
 
            trace.mutter("checking remap as %d deletions", delete_count)
 
159
        if has_deletes:
157
160
            self._check_remap()
158
161
        return self._save()
159
162
 
160
163
    def _ensure_root(self):
161
164
        """Ensure that the root node is an object not a key."""
162
 
        if type(self._root_node) is StaticTuple:
 
165
        if isinstance(self._root_node, StaticTuple):
163
166
            # Demand-load the root
164
167
            self._root_node = self._get_node(self._root_node)
165
168
 
173
176
        :param node: A tuple key or node object.
174
177
        :return: A node object.
175
178
        """
176
 
        if type(node) is StaticTuple:
 
179
        if isinstance(node, StaticTuple):
177
180
            bytes = self._read_bytes(node)
178
181
            return _deserialise(bytes, node,
179
182
                search_key_func=self._search_key_func)
210
213
                key_str = ' None'
211
214
        result.append('%s%r %s%s' % (indent, prefix, node.__class__.__name__,
212
215
                                     key_str))
213
 
        if type(node) is InternalNode:
 
216
        if isinstance(node, InternalNode):
214
217
            # Trigger all child nodes to get loaded
215
218
            list(node._iter_nodes(self._store))
216
 
            for prefix, sub in sorted(node._items.iteritems()):
 
219
            for prefix, sub in sorted(viewitems(node._items)):
217
220
                result.extend(self._dump_tree_node(sub, prefix, indent + '  ',
218
221
                                                   include_keys=include_keys))
219
222
        else:
220
 
            for key, value in sorted(node._items.iteritems()):
 
223
            for key, value in sorted(viewitems(node._items)):
221
224
                # Don't use prefix nor indent here to line up when used in
222
225
                # tests in conjunction with assertEqualDiff
223
226
                result.append('      %r %r' % (tuple(key), value))
244
247
        root_key = klass._create_directly(store, initial_value,
245
248
            maximum_size=maximum_size, key_width=key_width,
246
249
            search_key_func=search_key_func)
247
 
        if type(root_key) is not StaticTuple:
 
250
        if not isinstance(root_key, StaticTuple):
248
251
            raise AssertionError('we got a %s instead of a StaticTuple'
249
252
                                 % (type(root_key),))
250
253
        return root_key
256
259
        result._root_node.set_maximum_size(maximum_size)
257
260
        result._root_node._key_width = key_width
258
261
        delta = []
259
 
        for key, value in initial_value.items():
 
262
        for key, value in viewitems(initial_value):
260
263
            delta.append((None, key, value))
261
264
        root_key = result.apply_delta(delta)
262
265
        return root_key
268
271
        node.set_maximum_size(maximum_size)
269
272
        node._key_width = key_width
270
273
        as_st = StaticTuple.from_sequence
271
 
        node._items = dict([(as_st(key), val) for key, val
272
 
                                               in initial_value.iteritems()])
273
 
        node._raw_size = sum([node._key_value_len(key, value)
274
 
                              for key,value in node._items.iteritems()])
 
274
        node._items = dict((as_st(key), val)
 
275
            for key, val in viewitems(initial_value))
 
276
        node._raw_size = sum(node._key_value_len(key, value)
 
277
            for key, value in viewitems(node._items))
275
278
        node._len = len(node._items)
276
279
        node._compute_search_prefix()
277
280
        node._compute_serialised_prefix()
332
335
        def process_node(node, path, a_map, pending):
333
336
            # take a node and expand it
334
337
            node = a_map._get_node(node)
335
 
            if type(node) == LeafNode:
 
338
            if isinstance(node, LeafNode):
336
339
                path = (node._key, path)
337
 
                for key, value in node._items.items():
 
340
                for key, value in viewitems(node._items):
338
341
                    # For a LeafNode, the key is a serialized_key, rather than
339
342
                    # a search_key, but the heap is using search_keys
340
343
                    search_key = node._search_key_func(key)
342
345
            else:
343
346
                # type(node) == InternalNode
344
347
                path = (node._key, path)
345
 
                for prefix, child in node._items.items():
 
348
                for prefix, child in viewitems(node._items):
346
349
                    heapq.heappush(pending, (prefix, None, child, path))
347
350
        def process_common_internal_nodes(self_node, basis_node):
348
 
            self_items = set(self_node._items.items())
349
 
            basis_items = set(basis_node._items.items())
 
351
            self_items = set(viewitems(self_node._items))
 
352
            basis_items = set(viewitems(basis_node._items))
350
353
            path = (self_node._key, None)
351
354
            for prefix, child in self_items - basis_items:
352
355
                heapq.heappush(self_pending, (prefix, None, child, path))
354
357
            for prefix, child in basis_items - self_items:
355
358
                heapq.heappush(basis_pending, (prefix, None, child, path))
356
359
        def process_common_leaf_nodes(self_node, basis_node):
357
 
            self_items = set(self_node._items.items())
358
 
            basis_items = set(basis_node._items.items())
 
360
            self_items = set(viewitems(self_node._items))
 
361
            basis_items = set(viewitems(basis_node._items))
359
362
            path = (self_node._key, None)
360
363
            for key, value in self_items - basis_items:
361
364
                prefix = self._search_key_func(key)
370
373
            # time?
371
374
            self_node = self._get_node(self_node)
372
375
            basis_node = basis._get_node(basis_node)
373
 
            if (type(self_node) == InternalNode
374
 
                and type(basis_node) == InternalNode):
 
376
            if (isinstance(self_node, InternalNode)
 
377
                and isinstance(basis_node, InternalNode)):
375
378
                # Matching internal nodes
376
379
                process_common_internal_nodes(self_node, basis_node)
377
 
            elif (type(self_node) == LeafNode
378
 
                  and type(basis_node) == LeafNode):
 
380
            elif (isinstance(self_node, LeafNode)
 
381
                  and isinstance(basis_node, LeafNode)):
379
382
                process_common_leaf_nodes(self_node, basis_node)
380
383
            else:
381
384
                process_node(self_node, self_path, self, self_pending)
390
393
            # A better implementation would probably have a reverse map
391
394
            # back to the children of a node, and jump straight to it when
392
395
            # a common node is detected, the proceed to remove the already
393
 
            # pending children. bzrlib.graph has a searcher module with a
 
396
            # pending children. breezy.graph has a searcher module with a
394
397
            # similar problem.
395
398
            while key_path is not None:
396
399
                key, key_path = key_path
520
523
 
521
524
    def key(self):
522
525
        """Return the key for this map."""
523
 
        if type(self._root_node) is StaticTuple:
 
526
        if isinstance(self._root_node, StaticTuple):
524
527
            return self._root_node
525
528
        else:
526
529
            return self._root_node._key
551
554
 
552
555
    def _node_key(self, node):
553
556
        """Get the key for a node whether it's a tuple or node."""
554
 
        if type(node) is tuple:
 
557
        if isinstance(node, tuple):
555
558
            node = StaticTuple.from_sequence(node)
556
 
        if type(node) is StaticTuple:
 
559
        if isinstance(node, StaticTuple):
557
560
            return node
558
561
        else:
559
562
            return node._key
562
565
        """remove key from the map."""
563
566
        key = StaticTuple.from_sequence(key)
564
567
        self._ensure_root()
565
 
        if type(self._root_node) is InternalNode:
 
568
        if isinstance(self._root_node, InternalNode):
566
569
            unmapped = self._root_node.unmap(self._store, key,
567
570
                check_remap=check_remap)
568
571
        else:
572
575
    def _check_remap(self):
573
576
        """Check if nodes can be collapsed."""
574
577
        self._ensure_root()
575
 
        if type(self._root_node) is InternalNode:
576
 
            self._root_node._check_remap(self._store)
 
578
        if isinstance(self._root_node, InternalNode):
 
579
            self._root_node = self._root_node._check_remap(self._store)
577
580
 
578
581
    def _save(self):
579
582
        """Save the map completely.
580
583
 
581
584
        :return: The key of the root node.
582
585
        """
583
 
        if type(self._root_node) is StaticTuple:
 
586
        if isinstance(self._root_node, StaticTuple):
584
587
            # Already saved.
585
588
            return self._root_node
586
589
        keys = list(self._root_node.serialise(self._store))
767
770
                        pass
768
771
                else:
769
772
                    # Short items, we need to match based on a prefix
770
 
                    length_filter = filters.setdefault(len(key), set())
771
 
                    length_filter.add(key)
 
773
                    filters.setdefault(len(key), set()).add(key)
772
774
            if filters:
773
 
                filters = filters.items()
774
 
                for item in self._items.iteritems():
775
 
                    for length, length_filter in filters:
 
775
                filters_itemview = viewitems(filters)
 
776
                for item in viewitems(self._items):
 
777
                    for length, length_filter in filters_itemview:
776
778
                        if item[0][:length] in length_filter:
777
779
                            yield item
778
780
                            break
779
781
        else:
780
 
            for item in self._items.iteritems():
 
782
            for item in viewitems(self._items):
781
783
                yield item
782
784
 
783
785
    def _key_value_len(self, key, value):
839
841
        common_prefix = self._search_prefix
840
842
        split_at = len(common_prefix) + 1
841
843
        result = {}
842
 
        for key, value in self._items.iteritems():
 
844
        for key, value in viewitems(self._items):
843
845
            search_key = self._search_key(key)
844
846
            prefix = search_key[:split_at]
845
847
            # TODO: Generally only 1 key can be exactly the right length,
872
874
                for split, node in node_details:
873
875
                    new_node.add_node(split, node)
874
876
                result[prefix] = new_node
875
 
        return common_prefix, result.items()
 
877
        return common_prefix, list(viewitems(result))
876
878
 
877
879
    def map(self, store, key, value):
878
880
        """Map key to value."""
907
909
        else:
908
910
            lines.append('%s\n' % (self._common_serialised_prefix,))
909
911
            prefix_len = len(self._common_serialised_prefix)
910
 
        for key, value in sorted(self._items.items()):
 
912
        for key, value in sorted(viewitems(self._items)):
911
913
            # Always add a final newline
912
914
            value_lines = osutils.chunks_to_lines([value + '\n'])
913
915
            serialized = "%s\x00%s\n" % (self._serialise_key(key),
923
925
        bytes = ''.join(lines)
924
926
        if len(bytes) != self._current_size():
925
927
            raise AssertionError('Invalid _current_size')
926
 
        _get_cache().add(self._key, bytes)
 
928
        _get_cache()[self._key] = bytes
927
929
        return [self._key]
928
930
 
929
931
    def refs(self):
1072
1074
            # yielding all nodes, yield whatever we have, and queue up a read
1073
1075
            # for whatever we are missing
1074
1076
            shortcut = True
1075
 
            for prefix, node in self._items.iteritems():
 
1077
            for prefix, node in viewitems(self._items):
1076
1078
                if node.__class__ is StaticTuple:
1077
1079
                    keys[node] = (prefix, None)
1078
1080
                else:
1148
1150
            else:
1149
1151
                # The slow way. We walk every item in self._items, and check to
1150
1152
                # see if there are any matches
1151
 
                length_filters = length_filters.items()
1152
 
                for prefix, node in self._items.iteritems():
 
1153
                length_filters_itemview = viewitems(length_filters)
 
1154
                for prefix, node in viewitems(self._items):
1153
1155
                    node_key_filter = []
1154
 
                    for length, length_filter in length_filters:
 
1156
                    for length, length_filter in length_filters_itemview:
1155
1157
                        sub_prefix = prefix[:length]
1156
1158
                        if sub_prefix in length_filter:
1157
1159
                            node_key_filter.extend(prefix_to_keys[sub_prefix])
1196
1198
                    prefix, node_key_filter = keys[record.key]
1197
1199
                    node_and_filters.append((node, node_key_filter))
1198
1200
                    self._items[prefix] = node
1199
 
                    _get_cache().add(record.key, bytes)
 
1201
                    _get_cache()[record.key] = bytes
1200
1202
                for info in node_and_filters:
1201
1203
                    yield info
1202
1204
 
1229
1231
            # new child needed:
1230
1232
            child = self._new_child(search_key, LeafNode)
1231
1233
        old_len = len(child)
1232
 
        if type(child) is LeafNode:
 
1234
        if isinstance(child, LeafNode):
1233
1235
            old_size = child._current_size()
1234
1236
        else:
1235
1237
            old_size = None
1241
1243
            self._items[search_key] = child
1242
1244
            self._key = None
1243
1245
            new_node = self
1244
 
            if type(child) is LeafNode:
 
1246
            if isinstance(child, LeafNode):
1245
1247
                if old_size is None:
1246
1248
                    # The old node was an InternalNode which means it has now
1247
1249
                    # collapsed, so we need to check if it will chain to a
1293
1295
        :param store: A VersionedFiles honouring the CHK extensions.
1294
1296
        :return: An iterable of the keys inserted by this operation.
1295
1297
        """
1296
 
        for node in self._items.itervalues():
1297
 
            if type(node) is StaticTuple:
 
1298
        for node in viewvalues(self._items):
 
1299
            if isinstance(node, StaticTuple):
1298
1300
                # Never deserialised.
1299
1301
                continue
1300
1302
            if node._key is not None:
1310
1312
            raise AssertionError("_search_prefix should not be None")
1311
1313
        lines.append('%s\n' % (self._search_prefix,))
1312
1314
        prefix_len = len(self._search_prefix)
1313
 
        for prefix, node in sorted(self._items.items()):
1314
 
            if type(node) is StaticTuple:
 
1315
        for prefix, node in sorted(viewitems(self._items)):
 
1316
            if isinstance(node, StaticTuple):
1315
1317
                key = node[0]
1316
1318
            else:
1317
1319
                key = node._key[0]
1322
1324
            lines.append(serialised[prefix_len:])
1323
1325
        sha1, _, _ = store.add_lines((None,), (), lines)
1324
1326
        self._key = StaticTuple("sha1:" + sha1,).intern()
1325
 
        _get_cache().add(self._key, ''.join(lines))
 
1327
        _get_cache()[self._key] = ''.join(lines)
1326
1328
        yield self._key
1327
1329
 
1328
1330
    def _search_key(self, key):
1343
1345
            prefix for reaching node.
1344
1346
        """
1345
1347
        if offset >= self._node_width:
1346
 
            for node in self._items.values():
 
1348
            for node in valueview(self._items):
1347
1349
                for result in node._split(offset):
1348
1350
                    yield result
1349
 
            return
1350
 
        for key, node in self._items.items():
1351
 
            pass
1352
1351
 
1353
1352
    def refs(self):
1354
1353
        """Return the references to other CHK's held by this node."""
1355
1354
        if self._key is None:
1356
1355
            raise AssertionError("unserialised nodes have no refs.")
1357
1356
        refs = []
1358
 
        for value in self._items.itervalues():
1359
 
            if type(value) is StaticTuple:
 
1357
        for value in viewvalues(self._items):
 
1358
            if isinstance(value, StaticTuple):
1360
1359
                refs.append(value)
1361
1360
            else:
1362
1361
                refs.append(value.key())
1372
1371
        return self._search_prefix
1373
1372
 
1374
1373
    def unmap(self, store, key, check_remap=True):
1375
 
        """Remove key from this node and it's children."""
 
1374
        """Remove key from this node and its children."""
1376
1375
        if not len(self._items):
1377
1376
            raise AssertionError("can't unmap in an empty InternalNode.")
1378
1377
        children = [node for node, _
1394
1393
            self._items[search_key] = unmapped
1395
1394
        if len(self._items) == 1:
1396
1395
            # this node is no longer needed:
1397
 
            return self._items.values()[0]
1398
 
        if type(unmapped) is InternalNode:
 
1396
            return list(viewvalues(self._items))[0]
 
1397
        if isinstance(unmapped, InternalNode):
1399
1398
            return self
1400
1399
        if check_remap:
1401
1400
            return self._check_remap(store)
1441
1440
        #   c) With 255-way fan out, we don't want to read all 255 and destroy
1442
1441
        #      the page cache, just to determine that we really don't need it.
1443
1442
        for node, _ in self._iter_nodes(store, batch_size=16):
1444
 
            if type(node) is InternalNode:
 
1443
            if isinstance(node, InternalNode):
1445
1444
                # Without looking at any leaf nodes, we are sure
1446
1445
                return self
1447
 
            for key, value in node._items.iteritems():
 
1446
            for key, value in viewitems(node._items):
1448
1447
                if new_leaf._map_no_split(key, value):
1449
1448
                    return self
1450
1449
        trace.mutter("remap generated a new LeafNode")
1526
1525
            bytes = record.get_bytes_as('fulltext')
1527
1526
            node = _deserialise(bytes, record.key,
1528
1527
                                search_key_func=self._search_key_func)
1529
 
            if type(node) is InternalNode:
 
1528
            if isinstance(node, InternalNode):
1530
1529
                # Note we don't have to do node.refs() because we know that
1531
1530
                # there are no children that have been pushed into this node
1532
1531
                # Note: Using as_st() here seemed to save 1.2MB, which would
1533
1532
                #       indicate that we keep 100k prefix_refs around while
1534
1533
                #       processing. They *should* be shorter lived than that...
1535
1534
                #       It does cost us ~10s of processing time
1536
 
                #prefix_refs = [as_st(item) for item in node._items.iteritems()]
1537
 
                prefix_refs = node._items.items()
 
1535
                prefix_refs = list(viewitems(node._items))
1538
1536
                items = []
1539
1537
            else:
1540
1538
                prefix_refs = []
1541
1539
                # Note: We don't use a StaticTuple here. Profiling showed a
1542
1540
                #       minor memory improvement (0.8MB out of 335MB peak 0.2%)
1543
1541
                #       But a significant slowdown (15s / 145s, or 10%)
1544
 
                items = node._items.items()
 
1542
                items = list(viewitems(node._items))
1545
1543
            yield record, node, prefix_refs, items
1546
1544
 
1547
1545
    def _read_old_roots(self):
1571
1569
        # handled the interesting ones
1572
1570
        for prefix, ref in old_chks_to_enqueue:
1573
1571
            not_interesting = True
1574
 
            for i in xrange(len(prefix), 0, -1):
 
1572
            for i in range(len(prefix), 0, -1):
1575
1573
                if prefix[:i] in new_prefixes:
1576
1574
                    not_interesting = False
1577
1575
                    break
1631
1629
        # 'ab', then we also need to include 'a'.) So expand the
1632
1630
        # new_prefixes to include all shorter prefixes
1633
1631
        for prefix in list(new_prefixes):
1634
 
            new_prefixes.update([prefix[:i] for i in xrange(1, len(prefix))])
 
1632
            new_prefixes.update([prefix[:i] for i in range(1, len(prefix))])
1635
1633
        self._enqueue_old(new_prefixes, old_chks_to_enqueue)
1636
1634
 
1637
1635
    def _flush_new_queue(self):
1726
1724
 
1727
1725
 
1728
1726
try:
1729
 
    from bzrlib._chk_map_pyx import (
 
1727
    from breezy._chk_map_pyx import (
 
1728
        _bytes_to_text_key,
1730
1729
        _search_key_16,
1731
1730
        _search_key_255,
1732
1731
        _deserialise_leaf_node,
1733
1732
        _deserialise_internal_node,
1734
1733
        )
1735
 
except ImportError, e:
 
1734
except ImportError as e:
1736
1735
    osutils.failed_to_load_extension(e)
1737
 
    from bzrlib._chk_map_py import (
 
1736
    from breezy._chk_map_py import (
 
1737
        _bytes_to_text_key,
1738
1738
        _search_key_16,
1739
1739
        _search_key_255,
1740
1740
        _deserialise_leaf_node,
1750
1750
    This generally shouldn't be used in production code, but it can be helpful
1751
1751
    to debug problems.
1752
1752
    """
1753
 
    if type(key) is not StaticTuple:
 
1753
    if not isinstance(key, StaticTuple):
1754
1754
        raise TypeError('key %r is not StaticTuple but %s' % (key, type(key)))
1755
1755
    if len(key) != 1:
1756
1756
        raise ValueError('key %r should have length 1, not %d' % (key, len(key),))
1757
 
    if type(key[0]) is not str:
 
1757
    if not isinstance(key[0], str):
1758
1758
        raise TypeError('key %r should hold a str, not %r'
1759
1759
                        % (key, type(key[0])))
1760
1760
    if not key[0].startswith('sha1:'):