← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

Fix #531967 by creating helpers for PathConflicts when a deletion
is involved.

* bzrlib/tests/test_conflicts.py:
(TestParametrizedResolveConflicts.mirror_scenarios): Renamed from
multiply_scenarios to make the intent clearer. Turned into a
classmethod too for the same reason.
(TestParametrizedResolveConflicts.scenarios): Now a classmethod.

* bzrlib/merge.py:
(Merge3Merger._merge_names): 'name conflict' and 'parent conflict'
can (and must) be handled in the same way. If a deletion is
involved we create an unversioned copy of the rejected item so the
user can restore that easily.
(Merge3Merger.cook_conflicts): Get rid of 'name conflict', 'parent
conflict' distinction and just create PathConflicts with a file_id
to address bug #531967.

* bzrlib/conflicts.py:
(PathConflict.associated_filenames): Helpers exist only when a
deletion is involved.
(PathConflict._resolve): We may have to version one path
again. This may happen when a deletion have occurred.
(PathConflict.action_take_this, PathConflict.action_take_other):
As a special case, we may have an helper to use when deletion was
involved.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
1
 
# Copyright (C) 2008 Canonical Ltd
 
1
# Copyright (C) 2008, 2009, 2010 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
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
#
17
17
 
18
18
"""B+Tree indices"""
19
19
 
20
 
import array
21
 
import bisect
 
20
import cStringIO
22
21
from bisect import bisect_right
23
 
from copy import deepcopy
24
22
import math
25
 
import struct
26
23
import tempfile
27
24
import zlib
28
25
 
30
27
    chunk_writer,
31
28
    debug,
32
29
    errors,
 
30
    fifo_cache,
33
31
    index,
34
32
    lru_cache,
35
33
    osutils,
 
34
    static_tuple,
36
35
    trace,
37
36
    )
38
37
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
63
62
    def __init__(self):
64
63
        """Create a _BuilderRow."""
65
64
        self.nodes = 0
66
 
        self.spool = tempfile.TemporaryFile()
 
65
        self.spool = None# tempfile.TemporaryFile(prefix='bzr-index-row-')
67
66
        self.writer = None
68
67
 
69
68
    def finish_node(self, pad=True):
70
69
        byte_lines, _, padding = self.writer.finish()
71
70
        if self.nodes == 0:
 
71
            self.spool = cStringIO.StringIO()
72
72
            # padded note:
73
73
            self.spool.write("\x00" * _RESERVED_HEADER_BYTES)
 
74
        elif self.nodes == 1:
 
75
            # We got bigger than 1 node, switch to a temp file
 
76
            spool = tempfile.TemporaryFile(prefix='bzr-index-row-')
 
77
            spool.write(self.spool.getvalue())
 
78
            self.spool = spool
74
79
        skipped_bytes = 0
75
80
        if not pad and padding:
76
81
            del byte_lines[-1]
155
160
        :param value: The value to associate with the key. It may be any
156
161
            bytes as long as it does not contain \0 or \n.
157
162
        """
 
163
        # Ensure that 'key' is a StaticTuple
 
164
        key = static_tuple.StaticTuple.from_sequence(key).intern()
158
165
        # we don't care about absent_references
159
166
        node_refs, _ = self._check_key_ref_value(key, references, value)
160
167
        if key in self._nodes:
161
168
            raise errors.BadIndexDuplicateKey(key, self)
162
 
        self._nodes[key] = (node_refs, value)
163
 
        self._keys.add(key)
 
169
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
164
170
        if self._nodes_by_key is not None and self._key_length > 1:
165
171
            self._update_nodes_by_key(key, value, node_refs)
166
 
        if len(self._keys) < self._spill_at:
 
172
        if len(self._nodes) < self._spill_at:
167
173
            return
168
174
        self._spill_mem_keys_to_disk()
169
175
 
180
186
        combine mem with the first and second indexes, creating a new one of
181
187
        size 4x. On the fifth create a single new one, etc.
182
188
        """
 
189
        if self._combine_backing_indices:
 
190
            (new_backing_file, size,
 
191
             backing_pos) = self._spill_mem_keys_and_combine()
 
192
        else:
 
193
            new_backing_file, size = self._spill_mem_keys_without_combining()
 
194
        # Note: The transport here isn't strictly needed, because we will use
 
195
        #       direct access to the new_backing._file object
 
196
        new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)
 
197
        # GC will clean up the file
 
198
        new_backing._file = new_backing_file
 
199
        if self._combine_backing_indices:
 
200
            if len(self._backing_indices) == backing_pos:
 
201
                self._backing_indices.append(None)
 
202
            self._backing_indices[backing_pos] = new_backing
 
203
            for backing_pos in range(backing_pos):
 
204
                self._backing_indices[backing_pos] = None
 
205
        else:
 
206
            self._backing_indices.append(new_backing)
 
207
        self._nodes = {}
 
208
        self._nodes_by_key = None
 
209
 
 
210
    def _spill_mem_keys_without_combining(self):
 
211
        return self._write_nodes(self._iter_mem_nodes(), allow_optimize=False)
 
212
 
 
213
    def _spill_mem_keys_and_combine(self):
183
214
        iterators_to_combine = [self._iter_mem_nodes()]
184
215
        pos = -1
185
216
        for pos, backing in enumerate(self._backing_indices):
189
220
            iterators_to_combine.append(backing.iter_all_entries())
190
221
        backing_pos = pos + 1
191
222
        new_backing_file, size = \
192
 
            self._write_nodes(self._iter_smallest(iterators_to_combine))
193
 
        dir_path, base_name = osutils.split(new_backing_file.name)
194
 
        # Note: The transport here isn't strictly needed, because we will use
195
 
        #       direct access to the new_backing._file object
196
 
        new_backing = BTreeGraphIndex(get_transport(dir_path),
197
 
                                      base_name, size)
198
 
        # GC will clean up the file
199
 
        new_backing._file = new_backing_file
200
 
        if len(self._backing_indices) == backing_pos:
201
 
            self._backing_indices.append(None)
202
 
        self._backing_indices[backing_pos] = new_backing
203
 
        for pos in range(backing_pos):
204
 
            self._backing_indices[pos] = None
205
 
        self._keys = set()
206
 
        self._nodes = {}
207
 
        self._nodes_by_key = None
 
223
            self._write_nodes(self._iter_smallest(iterators_to_combine),
 
224
                              allow_optimize=False)
 
225
        return new_backing_file, size, backing_pos
208
226
 
209
227
    def add_nodes(self, nodes):
210
228
        """Add nodes to the index.
262
280
            except StopIteration:
263
281
                current_values[pos] = None
264
282
 
265
 
    def _add_key(self, string_key, line, rows):
 
283
    def _add_key(self, string_key, line, rows, allow_optimize=True):
266
284
        """Add a key to the current chunk.
267
285
 
268
286
        :param string_key: The key to add.
269
287
        :param line: The fully serialised key and value.
 
288
        :param allow_optimize: If set to False, prevent setting the optimize
 
289
            flag when writing out. This is used by the _spill_mem_keys_to_disk
 
290
            functionality.
270
291
        """
271
292
        if rows[-1].writer is None:
272
293
            # opening a new leaf chunk;
277
298
                    length = _PAGE_SIZE
278
299
                    if internal_row.nodes == 0:
279
300
                        length -= _RESERVED_HEADER_BYTES # padded
 
301
                    if allow_optimize:
 
302
                        optimize_for_size = self._optimize_for_size
 
303
                    else:
 
304
                        optimize_for_size = False
280
305
                    internal_row.writer = chunk_writer.ChunkWriter(length, 0,
281
 
                        optimize_for_size=self._optimize_for_size)
 
306
                        optimize_for_size=optimize_for_size)
282
307
                    internal_row.writer.write(_INTERNAL_FLAG)
283
308
                    internal_row.writer.write(_INTERNAL_OFFSET +
284
309
                        str(rows[pos + 1].nodes) + "\n")
296
321
            new_row = True
297
322
            for row in reversed(rows[:-1]):
298
323
                # Mark the start of the next node in the node above. If it
299
 
                # doesn't fit then propogate upwards until we find one that
 
324
                # doesn't fit then propagate upwards until we find one that
300
325
                # it does fit into.
301
326
                if row.writer.write(key_line):
302
327
                    row.finish_node()
322
347
                new_row.writer.write(_INTERNAL_OFFSET +
323
348
                    str(rows[1].nodes - 1) + "\n")
324
349
                new_row.writer.write(key_line)
325
 
            self._add_key(string_key, line, rows)
 
350
            self._add_key(string_key, line, rows, allow_optimize=allow_optimize)
326
351
 
327
 
    def _write_nodes(self, node_iterator):
 
352
    def _write_nodes(self, node_iterator, allow_optimize=True):
328
353
        """Write node_iterator out as a B+Tree.
329
354
 
330
355
        :param node_iterator: An iterator of sorted nodes. Each node should
331
356
            match the output given by iter_all_entries.
 
357
        :param allow_optimize: If set to False, prevent setting the optimize
 
358
            flag when writing out. This is used by the _spill_mem_keys_to_disk
 
359
            functionality.
332
360
        :return: A file handle for a temporary file containing a B+Tree for
333
361
            the nodes.
334
362
        """
344
372
        self.row_lengths = []
345
373
        # Loop over all nodes adding them to the bottom row
346
374
        # (rows[-1]). When we finish a chunk in a row,
347
 
        # propogate the key that didn't fit (comes after the chunk) to the
 
375
        # propagate the key that didn't fit (comes after the chunk) to the
348
376
        # row above, transitively.
349
377
        for node in node_iterator:
350
378
            if key_count == 0:
353
381
            key_count += 1
354
382
            string_key, line = _btree_serializer._flatten_node(node,
355
383
                                    self.reference_lists)
356
 
            self._add_key(string_key, line, rows)
 
384
            self._add_key(string_key, line, rows, allow_optimize=allow_optimize)
357
385
        for row in reversed(rows):
358
386
            pad = (type(row) != _LeafBuilderRow)
359
387
            row.finish_node(pad=pad)
360
 
        result = tempfile.NamedTemporaryFile()
361
388
        lines = [_BTSIGNATURE]
362
389
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
363
390
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
364
391
        lines.append(_OPTION_LEN + str(key_count) + '\n')
365
392
        row_lengths = [row.nodes for row in rows]
366
393
        lines.append(_OPTION_ROW_LENGTHS + ','.join(map(str, row_lengths)) + '\n')
 
394
        if row_lengths and row_lengths[-1] > 1:
 
395
            result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
 
396
        else:
 
397
            result = cStringIO.StringIO()
367
398
        result.writelines(lines)
368
399
        position = sum(map(len, lines))
369
400
        root_row = True
380
411
            # Special case the first node as it may be prefixed
381
412
            node = row.spool.read(_PAGE_SIZE)
382
413
            result.write(node[reserved:])
383
 
            result.write("\x00" * (reserved - position))
 
414
            if len(node) == _PAGE_SIZE:
 
415
                result.write("\x00" * (reserved - position))
384
416
            position = 0 # Only the root row actually has an offset
385
417
            copied_len = osutils.pumpfile(row.spool, result)
386
418
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
405
437
    def iter_all_entries(self):
406
438
        """Iterate over all keys within the index
407
439
 
408
 
        :return: An iterable of (index, key, reference_lists, value). There is no
409
 
            defined order for the result iteration - it will be in the most
 
440
        :return: An iterable of (index, key, value, reference_lists). There is
 
441
            no defined order for the result iteration - it will be in the most
410
442
            efficient order for the index (in this case dictionary hash order).
411
443
        """
412
444
        if 'evil' in debug.debug_flags:
431
463
            efficient order for the index (keys iteration order in this case).
432
464
        """
433
465
        keys = set(keys)
434
 
        local_keys = keys.intersection(self._keys)
 
466
        # Note: We don't use keys.intersection() here. If you read the C api,
 
467
        #       set.intersection(other) special cases when other is a set and
 
468
        #       will iterate the smaller of the two and lookup in the other.
 
469
        #       It does *not* do this for any other type (even dict, unlike
 
470
        #       some other set functions.) Since we expect keys is generally <<
 
471
        #       self._nodes, it is faster to iterate over it in a list
 
472
        #       comprehension
 
473
        nodes = self._nodes
 
474
        local_keys = [key for key in keys if key in nodes]
435
475
        if self.reference_lists:
436
476
            for key in local_keys:
437
 
                node = self._nodes[key]
 
477
                node = nodes[key]
438
478
                yield self, key, node[1], node[0]
439
479
        else:
440
480
            for key in local_keys:
441
 
                node = self._nodes[key]
 
481
                node = nodes[key]
442
482
                yield self, key, node[1]
443
483
        # Find things that are in backing indices that have not been handled
444
484
        # yet.
554
594
 
555
595
        For InMemoryGraphIndex the estimate is exact.
556
596
        """
557
 
        return len(self._keys) + sum(backing.key_count() for backing in
 
597
        return len(self._nodes) + sum(backing.key_count() for backing in
558
598
            self._backing_indices if backing is not None)
559
599
 
560
600
    def validate(self):
564
604
class _LeafNode(object):
565
605
    """A leaf node for a serialised B+Tree index."""
566
606
 
 
607
    __slots__ = ('keys', 'min_key', 'max_key')
 
608
 
567
609
    def __init__(self, bytes, key_length, ref_list_length):
568
610
        """Parse bytes to create a leaf node object."""
569
611
        # splitlines mangles the \r delimiters.. don't use it.
570
 
        self.keys = dict(_btree_serializer._parse_leaf_lines(bytes,
571
 
            key_length, ref_list_length))
 
612
        key_list = _btree_serializer._parse_leaf_lines(bytes,
 
613
            key_length, ref_list_length)
 
614
        if key_list:
 
615
            self.min_key = key_list[0][0]
 
616
            self.max_key = key_list[-1][0]
 
617
        else:
 
618
            self.min_key = self.max_key = None
 
619
        self.keys = dict(key_list)
572
620
 
573
621
 
574
622
class _InternalNode(object):
575
623
    """An internal node for a serialised B+Tree index."""
576
624
 
 
625
    __slots__ = ('keys', 'offset')
 
626
 
577
627
    def __init__(self, bytes):
578
628
        """Parse bytes to create an internal node object."""
579
629
        # splitlines mangles the \r delimiters.. don't use it.
582
632
    def _parse_lines(self, lines):
583
633
        nodes = []
584
634
        self.offset = int(lines[1][7:])
 
635
        as_st = static_tuple.StaticTuple.from_sequence
585
636
        for line in lines[2:]:
586
637
            if line == '':
587
638
                break
588
 
            nodes.append(tuple(line.split('\0')))
 
639
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
589
640
        return nodes
590
641
 
591
642
 
596
647
    memory except when very large walks are done.
597
648
    """
598
649
 
599
 
    def __init__(self, transport, name, size):
 
650
    def __init__(self, transport, name, size, unlimited_cache=False):
600
651
        """Create a B+Tree index object on the index name.
601
652
 
602
653
        :param transport: The transport to read data for the index from.
606
657
            the initial read (to read the root node header) can be done
607
658
            without over-reading even on empty indices, and on small indices
608
659
            allows single-IO to read the entire index.
 
660
        :param unlimited_cache: If set to True, then instead of using an
 
661
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
 
662
            cache all leaf nodes.
609
663
        """
610
664
        self._transport = transport
611
665
        self._name = name
615
669
        self._root_node = None
616
670
        # Default max size is 100,000 leave values
617
671
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
618
 
        self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
619
 
        self._internal_node_cache = lru_cache.LRUCache()
 
672
        if unlimited_cache:
 
673
            self._leaf_node_cache = {}
 
674
            self._internal_node_cache = {}
 
675
        else:
 
676
            self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
 
677
            # We use a FIFO here just to prevent possible blowout. However, a
 
678
            # 300k record btree has only 3k leaf nodes, and only 20 internal
 
679
            # nodes. A value of 100 scales to ~100*100*100 = 1M records.
 
680
            self._internal_node_cache = fifo_cache.FIFOCache(100)
620
681
        self._key_count = None
621
682
        self._row_lengths = None
622
683
        self._row_offsets = None # Start of each row, [-1] is the end
654
715
                if start_of_leaves is None:
655
716
                    start_of_leaves = self._row_offsets[-2]
656
717
                if node_pos < start_of_leaves:
657
 
                    self._internal_node_cache.add(node_pos, node)
 
718
                    self._internal_node_cache[node_pos] = node
658
719
                else:
659
 
                    self._leaf_node_cache.add(node_pos, node)
 
720
                    self._leaf_node_cache[node_pos] = node
660
721
            found[node_pos] = node
661
722
        return found
662
723
 
801
862
            new_tips = next_tips
802
863
        return final_offsets
803
864
 
 
865
    def clear_cache(self):
 
866
        """Clear out any cached/memoized values.
 
867
 
 
868
        This can be called at any time, but generally it is used when we have
 
869
        extracted some information, but don't expect to be requesting any more
 
870
        from this index.
 
871
        """
 
872
        # Note that we don't touch self._root_node or self._internal_node_cache
 
873
        # We don't expect either of those to be big, and it can save
 
874
        # round-trips in the future. We may re-evaluate this if InternalNode
 
875
        # memory starts to be an issue.
 
876
        self._leaf_node_cache.clear()
 
877
 
 
878
    def external_references(self, ref_list_num):
 
879
        if self._root_node is None:
 
880
            self._get_root_node()
 
881
        if ref_list_num + 1 > self.node_ref_lists:
 
882
            raise ValueError('No ref list %d, index has %d ref lists'
 
883
                % (ref_list_num, self.node_ref_lists))
 
884
        keys = set()
 
885
        refs = set()
 
886
        for node in self.iter_all_entries():
 
887
            keys.add(node[1])
 
888
            refs.update(node[3][ref_list_num])
 
889
        return refs - keys
 
890
 
804
891
    def _find_layer_first_and_end(self, offset):
805
892
        """Find the start/stop nodes for the layer corresponding to offset.
806
893
 
996
1083
            output.append(cur_out)
997
1084
        return output
998
1085
 
 
1086
    def _walk_through_internal_nodes(self, keys):
 
1087
        """Take the given set of keys, and find the corresponding LeafNodes.
 
1088
 
 
1089
        :param keys: An unsorted iterable of keys to search for
 
1090
        :return: (nodes, index_and_keys)
 
1091
            nodes is a dict mapping {index: LeafNode}
 
1092
            keys_at_index is a list of tuples of [(index, [keys for Leaf])]
 
1093
        """
 
1094
        # 6 seconds spent in miss_torture using the sorted() line.
 
1095
        # Even with out of order disk IO it seems faster not to sort it when
 
1096
        # large queries are being made.
 
1097
        keys_at_index = [(0, sorted(keys))]
 
1098
 
 
1099
        for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
 
1100
            node_indexes = [idx for idx, s_keys in keys_at_index]
 
1101
            nodes = self._get_internal_nodes(node_indexes)
 
1102
 
 
1103
            next_nodes_and_keys = []
 
1104
            for node_index, sub_keys in keys_at_index:
 
1105
                node = nodes[node_index]
 
1106
                positions = self._multi_bisect_right(sub_keys, node.keys)
 
1107
                node_offset = next_row_start + node.offset
 
1108
                next_nodes_and_keys.extend([(node_offset + pos, s_keys)
 
1109
                                           for pos, s_keys in positions])
 
1110
            keys_at_index = next_nodes_and_keys
 
1111
        # We should now be at the _LeafNodes
 
1112
        node_indexes = [idx for idx, s_keys in keys_at_index]
 
1113
 
 
1114
        # TODO: We may *not* want to always read all the nodes in one
 
1115
        #       big go. Consider setting a max size on this.
 
1116
        nodes = self._get_leaf_nodes(node_indexes)
 
1117
        return nodes, keys_at_index
 
1118
 
999
1119
    def iter_entries(self, keys):
1000
1120
        """Iterate over keys within the index.
1001
1121
 
1039
1159
        needed_keys = keys
1040
1160
        if not needed_keys:
1041
1161
            return
1042
 
        # 6 seconds spent in miss_torture using the sorted() line.
1043
 
        # Even with out of order disk IO it seems faster not to sort it when
1044
 
        # large queries are being made.
1045
 
        needed_keys = sorted(needed_keys)
1046
 
 
1047
 
        nodes_and_keys = [(0, needed_keys)]
1048
 
 
1049
 
        for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1050
 
            node_indexes = [idx for idx, s_keys in nodes_and_keys]
1051
 
            nodes = self._get_internal_nodes(node_indexes)
1052
 
 
1053
 
            next_nodes_and_keys = []
1054
 
            for node_index, sub_keys in nodes_and_keys:
1055
 
                node = nodes[node_index]
1056
 
                positions = self._multi_bisect_right(sub_keys, node.keys)
1057
 
                node_offset = next_row_start + node.offset
1058
 
                next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1059
 
                                           for pos, s_keys in positions])
1060
 
            nodes_and_keys = next_nodes_and_keys
1061
 
        # We should now be at the _LeafNodes
1062
 
        node_indexes = [idx for idx, s_keys in nodes_and_keys]
1063
 
 
1064
 
        # TODO: We may *not* want to always read all the nodes in one
1065
 
        #       big go. Consider setting a max size on this.
1066
 
 
1067
 
        nodes = self._get_leaf_nodes(node_indexes)
 
1162
        nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
1068
1163
        for node_index, sub_keys in nodes_and_keys:
1069
1164
            if not sub_keys:
1070
1165
                continue
1077
1172
                    else:
1078
1173
                        yield (self, next_sub_key, value)
1079
1174
 
 
1175
    def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
 
1176
        """Find the parent_map information for the set of keys.
 
1177
 
 
1178
        This populates the parent_map dict and missing_keys set based on the
 
1179
        queried keys. It also can fill out an arbitrary number of parents that
 
1180
        it finds while searching for the supplied keys.
 
1181
 
 
1182
        It is unlikely that you want to call this directly. See
 
1183
        "CombinedGraphIndex.find_ancestry()" for a more appropriate API.
 
1184
 
 
1185
        :param keys: A keys whose ancestry we want to return
 
1186
            Every key will either end up in 'parent_map' or 'missing_keys'.
 
1187
        :param ref_list_num: This index in the ref_lists is the parents we
 
1188
            care about.
 
1189
        :param parent_map: {key: parent_keys} for keys that are present in this
 
1190
            index. This may contain more entries than were in 'keys', that are
 
1191
            reachable ancestors of the keys requested.
 
1192
        :param missing_keys: keys which are known to be missing in this index.
 
1193
            This may include parents that were not directly requested, but we
 
1194
            were able to determine that they are not present in this index.
 
1195
        :return: search_keys    parents that were found but not queried to know
 
1196
            if they are missing or present. Callers can re-query this index for
 
1197
            those keys, and they will be placed into parent_map or missing_keys
 
1198
        """
 
1199
        if not self.key_count():
 
1200
            # We use key_count() to trigger reading the root node and
 
1201
            # determining info about this BTreeGraphIndex
 
1202
            # If we don't have any keys, then everything is missing
 
1203
            missing_keys.update(keys)
 
1204
            return set()
 
1205
        if ref_list_num >= self.node_ref_lists:
 
1206
            raise ValueError('No ref list %d, index has %d ref lists'
 
1207
                % (ref_list_num, self.node_ref_lists))
 
1208
 
 
1209
        # The main trick we are trying to accomplish is that when we find a
 
1210
        # key listing its parents, we expect that the parent key is also likely
 
1211
        # to sit on the same page. Allowing us to expand parents quickly
 
1212
        # without suffering the full stack of bisecting, etc.
 
1213
        nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
 
1214
 
 
1215
        # These are parent keys which could not be immediately resolved on the
 
1216
        # page where the child was present. Note that we may already be
 
1217
        # searching for that key, and it may actually be present [or known
 
1218
        # missing] on one of the other pages we are reading.
 
1219
        # TODO:
 
1220
        #   We could try searching for them in the immediate previous or next
 
1221
        #   page. If they occur "later" we could put them in a pending lookup
 
1222
        #   set, and then for each node we read thereafter we could check to
 
1223
        #   see if they are present.
 
1224
        #   However, we don't know the impact of keeping this list of things
 
1225
        #   that I'm going to search for every node I come across from here on
 
1226
        #   out.
 
1227
        #   It doesn't handle the case when the parent key is missing on a
 
1228
        #   page that we *don't* read. So we already have to handle being
 
1229
        #   re-entrant for that.
 
1230
        #   Since most keys contain a date string, they are more likely to be
 
1231
        #   found earlier in the file than later, but we would know that right
 
1232
        #   away (key < min_key), and wouldn't keep searching it on every other
 
1233
        #   page that we read.
 
1234
        #   Mostly, it is an idea, one which should be benchmarked.
 
1235
        parents_not_on_page = set()
 
1236
 
 
1237
        for node_index, sub_keys in nodes_and_keys:
 
1238
            if not sub_keys:
 
1239
                continue
 
1240
            # sub_keys is all of the keys we are looking for that should exist
 
1241
            # on this page, if they aren't here, then they won't be found
 
1242
            node = nodes[node_index]
 
1243
            node_keys = node.keys
 
1244
            parents_to_check = set()
 
1245
            for next_sub_key in sub_keys:
 
1246
                if next_sub_key not in node_keys:
 
1247
                    # This one is just not present in the index at all
 
1248
                    missing_keys.add(next_sub_key)
 
1249
                else:
 
1250
                    value, refs = node_keys[next_sub_key]
 
1251
                    parent_keys = refs[ref_list_num]
 
1252
                    parent_map[next_sub_key] = parent_keys
 
1253
                    parents_to_check.update(parent_keys)
 
1254
            # Don't look for things we've already found
 
1255
            parents_to_check = parents_to_check.difference(parent_map)
 
1256
            # this can be used to test the benefit of having the check loop
 
1257
            # inlined.
 
1258
            # parents_not_on_page.update(parents_to_check)
 
1259
            # continue
 
1260
            while parents_to_check:
 
1261
                next_parents_to_check = set()
 
1262
                for key in parents_to_check:
 
1263
                    if key in node_keys:
 
1264
                        value, refs = node_keys[key]
 
1265
                        parent_keys = refs[ref_list_num]
 
1266
                        parent_map[key] = parent_keys
 
1267
                        next_parents_to_check.update(parent_keys)
 
1268
                    else:
 
1269
                        # This parent either is genuinely missing, or should be
 
1270
                        # found on another page. Perf test whether it is better
 
1271
                        # to check if this node should fit on this page or not.
 
1272
                        # in the 'everything-in-one-pack' scenario, this *not*
 
1273
                        # doing the check is 237ms vs 243ms.
 
1274
                        # So slightly better, but I assume the standard 'lots
 
1275
                        # of packs' is going to show a reasonable improvement
 
1276
                        # from the check, because it avoids 'going around
 
1277
                        # again' for everything that is in another index
 
1278
                        # parents_not_on_page.add(key)
 
1279
                        # Missing for some reason
 
1280
                        if key < node.min_key:
 
1281
                            # in the case of bzr.dev, 3.4k/5.3k misses are
 
1282
                            # 'earlier' misses (65%)
 
1283
                            parents_not_on_page.add(key)
 
1284
                        elif key > node.max_key:
 
1285
                            # This parent key would be present on a different
 
1286
                            # LeafNode
 
1287
                            parents_not_on_page.add(key)
 
1288
                        else:
 
1289
                            # assert key != node.min_key and key != node.max_key
 
1290
                            # If it was going to be present, it would be on
 
1291
                            # *this* page, so mark it missing.
 
1292
                            missing_keys.add(key)
 
1293
                parents_to_check = next_parents_to_check.difference(parent_map)
 
1294
                # Might want to do another .difference() from missing_keys
 
1295
        # parents_not_on_page could have been found on a different page, or be
 
1296
        # known to be missing. So cull out everything that has already been
 
1297
        # found.
 
1298
        search_keys = parents_not_on_page.difference(
 
1299
            parent_map).difference(missing_keys)
 
1300
        return search_keys
 
1301
 
1080
1302
    def iter_entries_prefix(self, keys):
1081
1303
        """Iterate over keys within the index using prefix matching.
1082
1304
 
1341
1563
 
1342
1564
 
1343
1565
try:
1344
 
    from bzrlib import _btree_serializer_c as _btree_serializer
1345
 
except ImportError:
 
1566
    from bzrlib import _btree_serializer_pyx as _btree_serializer
 
1567
except ImportError, e:
 
1568
    osutils.failed_to_load_extension(e)
1346
1569
    from bzrlib import _btree_serializer_py as _btree_serializer