← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/groupcompress.py

  • Committer: Robert Collins
  • Date: 2010-05-06 07:48:22 UTC
  • mto: This revision was merged to the branch mainline in revision 5223.
  • Revision ID: robertc@robertcollins.net-20100506074822-0bsgf2j4h8jx0xkk
Added ``bzrlib.tests.matchers`` as a place to put matchers, along with
our first in-tree matcher. See the module docstring for details.
(Robert Collins)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/groupcompress.py
1
 
# Copyright (C) 2008, 2009 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
16
16
 
17
17
"""Core compression logic for compressing streams of related files."""
18
18
 
19
 
from itertools import izip
20
 
from cStringIO import StringIO
21
19
import time
22
20
import zlib
23
21
try:
28
26
from bzrlib import (
29
27
    annotate,
30
28
    debug,
31
 
    diff,
32
29
    errors,
33
30
    graph as _mod_graph,
 
31
    knit,
34
32
    osutils,
35
33
    pack,
36
 
    patiencediff,
 
34
    static_tuple,
37
35
    trace,
38
36
    )
39
 
from bzrlib.graph import Graph
40
 
from bzrlib.knit import _DirectPackAccess
41
37
from bzrlib.btree_index import BTreeBuilder
42
38
from bzrlib.lru_cache import LRUSizeCache
43
39
from bzrlib.tsort import topo_sort
49
45
    VersionedFiles,
50
46
    )
51
47
 
 
48
# Minimum number of uncompressed bytes to try fetch at once when retrieving
 
49
# groupcompress blocks.
 
50
BATCH_SIZE = 2**16
 
51
 
52
52
_USE_LZMA = False and (pylzma is not None)
53
53
 
54
54
# osutils.sha_string('')
55
55
_null_sha1 = 'da39a3ee5e6b4b0d3255bfef95601890afd80709'
56
56
 
57
 
 
58
57
def sort_gc_optimal(parent_map):
59
58
    """Sort and group the keys in parent_map into groupcompress order.
60
59
 
66
65
    # groupcompress ordering is approximately reverse topological,
67
66
    # properly grouped by file-id.
68
67
    per_prefix_map = {}
69
 
    for item in parent_map.iteritems():
70
 
        key = item[0]
 
68
    for key, value in parent_map.iteritems():
71
69
        if isinstance(key, str) or len(key) == 1:
72
70
            prefix = ''
73
71
        else:
74
72
            prefix = key[0]
75
73
        try:
76
 
            per_prefix_map[prefix].append(item)
 
74
            per_prefix_map[prefix][key] = value
77
75
        except KeyError:
78
 
            per_prefix_map[prefix] = [item]
 
76
            per_prefix_map[prefix] = {key: value}
79
77
 
80
78
    present_keys = []
81
79
    for prefix in sorted(per_prefix_map):
108
106
        self._z_content_length = None
109
107
        self._content_length = None
110
108
        self._content = None
 
109
        self._content_chunks = None
111
110
 
112
111
    def __len__(self):
113
112
        # This is the maximum number of bytes this object will reference if
121
120
        :param num_bytes: Ensure that we have extracted at least num_bytes of
122
121
            content. If None, consume everything
123
122
        """
124
 
        # TODO: If we re-use the same content block at different times during
125
 
        #       get_record_stream(), it is possible that the first pass will
126
 
        #       get inserted, triggering an extract/_ensure_content() which
127
 
        #       will get rid of _z_content. And then the next use of the block
128
 
        #       will try to access _z_content (to send it over the wire), and
129
 
        #       fail because it is already extracted. Consider never releasing
130
 
        #       _z_content because of this.
 
123
        if self._content_length is None:
 
124
            raise AssertionError('self._content_length should never be None')
131
125
        if num_bytes is None:
132
126
            num_bytes = self._content_length
133
127
        elif (self._content_length is not None
137
131
                % (num_bytes, self._content_length))
138
132
        # Expand the content if required
139
133
        if self._content is None:
 
134
            if self._content_chunks is not None:
 
135
                self._content = ''.join(self._content_chunks)
 
136
                self._content_chunks = None
 
137
        if self._content is None:
140
138
            if self._z_content is None:
141
139
                raise AssertionError('No content to decompress')
142
140
            if self._z_content == '':
146
144
                self._content = pylzma.decompress(self._z_content)
147
145
            elif self._compressor_name == 'zlib':
148
146
                # Start a zlib decompressor
149
 
                if num_bytes is None:
 
147
                if num_bytes * 4 > self._content_length * 3:
 
148
                    # If we are requesting more that 3/4ths of the content,
 
149
                    # just extract the whole thing in a single pass
 
150
                    num_bytes = self._content_length
150
151
                    self._content = zlib.decompress(self._z_content)
151
152
                else:
152
153
                    self._z_content_decompressor = zlib.decompressobj()
154
155
                    # that the rest of the code is simplified
155
156
                    self._content = self._z_content_decompressor.decompress(
156
157
                        self._z_content, num_bytes + _ZLIB_DECOMP_WINDOW)
 
158
                    if not self._z_content_decompressor.unconsumed_tail:
 
159
                        self._z_content_decompressor = None
157
160
            else:
158
161
                raise AssertionError('Unknown compressor: %r'
159
162
                                     % self._compressor_name)
161
164
        # 'unconsumed_tail'
162
165
 
163
166
        # Do we have enough bytes already?
164
 
        if num_bytes is not None and len(self._content) >= num_bytes:
165
 
            return
166
 
        if num_bytes is None and self._z_content_decompressor is None:
167
 
            # We must have already decompressed everything
 
167
        if len(self._content) >= num_bytes:
168
168
            return
169
169
        # If we got this far, and don't have a decompressor, something is wrong
170
170
        if self._z_content_decompressor is None:
171
171
            raise AssertionError(
172
172
                'No decompressor to decompress %d bytes' % num_bytes)
173
173
        remaining_decomp = self._z_content_decompressor.unconsumed_tail
174
 
        if num_bytes is None:
175
 
            if remaining_decomp:
176
 
                # We don't know how much is left, but we'll decompress it all
177
 
                self._content += self._z_content_decompressor.decompress(
178
 
                    remaining_decomp)
179
 
                # Note: There's what I consider a bug in zlib.decompressobj
180
 
                #       If you pass back in the entire unconsumed_tail, only
181
 
                #       this time you don't pass a max-size, it doesn't
182
 
                #       change the unconsumed_tail back to None/''.
183
 
                #       However, we know we are done with the whole stream
184
 
                self._z_content_decompressor = None
185
 
            # XXX: Why is this the only place in this routine we set this?
186
 
            self._content_length = len(self._content)
187
 
        else:
188
 
            if not remaining_decomp:
189
 
                raise AssertionError('Nothing left to decompress')
190
 
            needed_bytes = num_bytes - len(self._content)
191
 
            # We always set max_size to 32kB over the minimum needed, so that
192
 
            # zlib will give us as much as we really want.
193
 
            # TODO: If this isn't good enough, we could make a loop here,
194
 
            #       that keeps expanding the request until we get enough
195
 
            self._content += self._z_content_decompressor.decompress(
196
 
                remaining_decomp, needed_bytes + _ZLIB_DECOMP_WINDOW)
197
 
            if len(self._content) < num_bytes:
198
 
                raise AssertionError('%d bytes wanted, only %d available'
199
 
                                     % (num_bytes, len(self._content)))
200
 
            if not self._z_content_decompressor.unconsumed_tail:
201
 
                # The stream is finished
202
 
                self._z_content_decompressor = None
 
174
        if not remaining_decomp:
 
175
            raise AssertionError('Nothing left to decompress')
 
176
        needed_bytes = num_bytes - len(self._content)
 
177
        # We always set max_size to 32kB over the minimum needed, so that
 
178
        # zlib will give us as much as we really want.
 
179
        # TODO: If this isn't good enough, we could make a loop here,
 
180
        #       that keeps expanding the request until we get enough
 
181
        self._content += self._z_content_decompressor.decompress(
 
182
            remaining_decomp, needed_bytes + _ZLIB_DECOMP_WINDOW)
 
183
        if len(self._content) < num_bytes:
 
184
            raise AssertionError('%d bytes wanted, only %d available'
 
185
                                 % (num_bytes, len(self._content)))
 
186
        if not self._z_content_decompressor.unconsumed_tail:
 
187
            # The stream is finished
 
188
            self._z_content_decompressor = None
203
189
 
204
190
    def _parse_bytes(self, bytes, pos):
205
191
        """Read the various lengths from the header.
273
259
            bytes = apply_delta_to_source(self._content, content_start, end)
274
260
        return bytes
275
261
 
 
262
    def set_chunked_content(self, content_chunks, length):
 
263
        """Set the content of this block to the given chunks."""
 
264
        # If we have lots of short lines, it is may be more efficient to join
 
265
        # the content ahead of time. If the content is <10MiB, we don't really
 
266
        # care about the extra memory consumption, so we can just pack it and
 
267
        # be done. However, timing showed 18s => 17.9s for repacking 1k revs of
 
268
        # mysql, which is below the noise margin
 
269
        self._content_length = length
 
270
        self._content_chunks = content_chunks
 
271
        self._content = None
 
272
        self._z_content = None
 
273
 
276
274
    def set_content(self, content):
277
275
        """Set the content of this block."""
278
276
        self._content_length = len(content)
279
277
        self._content = content
280
278
        self._z_content = None
281
279
 
 
280
    def _create_z_content_using_lzma(self):
 
281
        if self._content_chunks is not None:
 
282
            self._content = ''.join(self._content_chunks)
 
283
            self._content_chunks = None
 
284
        if self._content is None:
 
285
            raise AssertionError('Nothing to compress')
 
286
        self._z_content = pylzma.compress(self._content)
 
287
        self._z_content_length = len(self._z_content)
 
288
 
 
289
    def _create_z_content_from_chunks(self):
 
290
        compressor = zlib.compressobj(zlib.Z_DEFAULT_COMPRESSION)
 
291
        compressed_chunks = map(compressor.compress, self._content_chunks)
 
292
        compressed_chunks.append(compressor.flush())
 
293
        self._z_content = ''.join(compressed_chunks)
 
294
        self._z_content_length = len(self._z_content)
 
295
 
 
296
    def _create_z_content(self):
 
297
        if self._z_content is not None:
 
298
            return
 
299
        if _USE_LZMA:
 
300
            self._create_z_content_using_lzma()
 
301
            return
 
302
        if self._content_chunks is not None:
 
303
            self._create_z_content_from_chunks()
 
304
            return
 
305
        self._z_content = zlib.compress(self._content)
 
306
        self._z_content_length = len(self._z_content)
 
307
 
282
308
    def to_bytes(self):
283
309
        """Encode the information into a byte stream."""
284
 
        compress = zlib.compress
285
 
        if _USE_LZMA:
286
 
            compress = pylzma.compress
287
 
        if self._z_content is None:
288
 
            if self._content is None:
289
 
                raise AssertionError('Nothing to compress')
290
 
            self._z_content = compress(self._content)
291
 
            self._z_content_length = len(self._z_content)
 
310
        self._create_z_content()
292
311
        if _USE_LZMA:
293
312
            header = self.GCB_LZ_HEADER
294
313
        else:
299
318
                 ]
300
319
        return ''.join(chunks)
301
320
 
 
321
    def _dump(self, include_text=False):
 
322
        """Take this block, and spit out a human-readable structure.
 
323
 
 
324
        :param include_text: Inserts also include text bits, chose whether you
 
325
            want this displayed in the dump or not.
 
326
        :return: A dump of the given block. The layout is something like:
 
327
            [('f', length), ('d', delta_length, text_length, [delta_info])]
 
328
            delta_info := [('i', num_bytes, text), ('c', offset, num_bytes),
 
329
            ...]
 
330
        """
 
331
        self._ensure_content()
 
332
        result = []
 
333
        pos = 0
 
334
        while pos < self._content_length:
 
335
            kind = self._content[pos]
 
336
            pos += 1
 
337
            if kind not in ('f', 'd'):
 
338
                raise ValueError('invalid kind character: %r' % (kind,))
 
339
            content_len, len_len = decode_base128_int(
 
340
                                self._content[pos:pos + 5])
 
341
            pos += len_len
 
342
            if content_len + pos > self._content_length:
 
343
                raise ValueError('invalid content_len %d for record @ pos %d'
 
344
                                 % (content_len, pos - len_len - 1))
 
345
            if kind == 'f': # Fulltext
 
346
                if include_text:
 
347
                    text = self._content[pos:pos+content_len]
 
348
                    result.append(('f', content_len, text))
 
349
                else:
 
350
                    result.append(('f', content_len))
 
351
            elif kind == 'd': # Delta
 
352
                delta_content = self._content[pos:pos+content_len]
 
353
                delta_info = []
 
354
                # The first entry in a delta is the decompressed length
 
355
                decomp_len, delta_pos = decode_base128_int(delta_content)
 
356
                result.append(('d', content_len, decomp_len, delta_info))
 
357
                measured_len = 0
 
358
                while delta_pos < content_len:
 
359
                    c = ord(delta_content[delta_pos])
 
360
                    delta_pos += 1
 
361
                    if c & 0x80: # Copy
 
362
                        (offset, length,
 
363
                         delta_pos) = decode_copy_instruction(delta_content, c,
 
364
                                                              delta_pos)
 
365
                        if include_text:
 
366
                            text = self._content[offset:offset+length]
 
367
                            delta_info.append(('c', offset, length, text))
 
368
                        else:
 
369
                            delta_info.append(('c', offset, length))
 
370
                        measured_len += length
 
371
                    else: # Insert
 
372
                        if include_text:
 
373
                            txt = delta_content[delta_pos:delta_pos+c]
 
374
                        else:
 
375
                            txt = ''
 
376
                        delta_info.append(('i', c, txt))
 
377
                        measured_len += c
 
378
                        delta_pos += c
 
379
                if delta_pos != content_len:
 
380
                    raise ValueError('Delta consumed a bad number of bytes:'
 
381
                                     ' %d != %d' % (delta_pos, content_len))
 
382
                if measured_len != decomp_len:
 
383
                    raise ValueError('Delta claimed fulltext was %d bytes, but'
 
384
                                     ' extraction resulted in %d bytes'
 
385
                                     % (decomp_len, measured_len))
 
386
            pos += content_len
 
387
        return result
 
388
 
302
389
 
303
390
class _LazyGroupCompressFactory(object):
304
391
    """Yield content from a GroupCompressBlock on demand."""
354
441
                # There are code paths that first extract as fulltext, and then
355
442
                # extract as storage_kind (smart fetch). So we don't break the
356
443
                # refcycle here, but instead in manager.get_record_stream()
357
 
                # self._manager = None
358
444
            if storage_kind == 'fulltext':
359
445
                return self._bytes
360
446
            else:
366
452
class _LazyGroupContentManager(object):
367
453
    """This manages a group of _LazyGroupCompressFactory objects."""
368
454
 
 
455
    _max_cut_fraction = 0.75 # We allow a block to be trimmed to 75% of
 
456
                             # current size, and still be considered
 
457
                             # resuable
 
458
    _full_block_size = 4*1024*1024
 
459
    _full_mixed_block_size = 2*1024*1024
 
460
    _full_enough_block_size = 3*1024*1024 # size at which we won't repack
 
461
    _full_enough_mixed_block_size = 2*768*1024 # 1.5MB
 
462
 
369
463
    def __init__(self, block):
370
464
        self._block = block
371
465
        # We need to preserve the ordering
443
537
        # time (self._block._content) is a little expensive.
444
538
        self._block._ensure_content(self._last_byte)
445
539
 
446
 
    def _check_rebuild_block(self):
 
540
    def _check_rebuild_action(self):
447
541
        """Check to see if our block should be repacked."""
448
542
        total_bytes_used = 0
449
543
        last_byte_used = 0
450
544
        for factory in self._factories:
451
545
            total_bytes_used += factory._end - factory._start
452
 
            last_byte_used = max(last_byte_used, factory._end)
453
 
        # If we are using most of the bytes from the block, we have nothing
454
 
        # else to check (currently more that 1/2)
 
546
            if last_byte_used < factory._end:
 
547
                last_byte_used = factory._end
 
548
        # If we are using more than half of the bytes from the block, we have
 
549
        # nothing else to check
455
550
        if total_bytes_used * 2 >= self._block._content_length:
456
 
            return
457
 
        # Can we just strip off the trailing bytes? If we are going to be
458
 
        # transmitting more than 50% of the front of the content, go ahead
 
551
            return None, last_byte_used, total_bytes_used
 
552
        # We are using less than 50% of the content. Is the content we are
 
553
        # using at the beginning of the block? If so, we can just trim the
 
554
        # tail, rather than rebuilding from scratch.
459
555
        if total_bytes_used * 2 > last_byte_used:
460
 
            self._trim_block(last_byte_used)
461
 
            return
 
556
            return 'trim', last_byte_used, total_bytes_used
462
557
 
463
558
        # We are using a small amount of the data, and it isn't just packed
464
559
        # nicely at the front, so rebuild the content.
471
566
        #       expanding many deltas into fulltexts, as well.
472
567
        #       If we build a cheap enough 'strip', then we could try a strip,
473
568
        #       if that expands the content, we then rebuild.
474
 
        self._rebuild_block()
 
569
        return 'rebuild', last_byte_used, total_bytes_used
 
570
 
 
571
    def check_is_well_utilized(self):
 
572
        """Is the current block considered 'well utilized'?
 
573
 
 
574
        This heuristic asks if the current block considers itself to be a fully
 
575
        developed group, rather than just a loose collection of data.
 
576
        """
 
577
        if len(self._factories) == 1:
 
578
            # A block of length 1 could be improved by combining with other
 
579
            # groups - don't look deeper. Even larger than max size groups
 
580
            # could compress well with adjacent versions of the same thing.
 
581
            return False
 
582
        action, last_byte_used, total_bytes_used = self._check_rebuild_action()
 
583
        block_size = self._block._content_length
 
584
        if total_bytes_used < block_size * self._max_cut_fraction:
 
585
            # This block wants to trim itself small enough that we want to
 
586
            # consider it under-utilized.
 
587
            return False
 
588
        # TODO: This code is meant to be the twin of _insert_record_stream's
 
589
        #       'start_new_block' logic. It would probably be better to factor
 
590
        #       out that logic into a shared location, so that it stays
 
591
        #       together better
 
592
        # We currently assume a block is properly utilized whenever it is >75%
 
593
        # of the size of a 'full' block. In normal operation, a block is
 
594
        # considered full when it hits 4MB of same-file content. So any block
 
595
        # >3MB is 'full enough'.
 
596
        # The only time this isn't true is when a given block has large-object
 
597
        # content. (a single file >4MB, etc.)
 
598
        # Under these circumstances, we allow a block to grow to
 
599
        # 2 x largest_content.  Which means that if a given block had a large
 
600
        # object, it may actually be under-utilized. However, given that this
 
601
        # is 'pack-on-the-fly' it is probably reasonable to not repack large
 
602
        # content blobs on-the-fly. Note that because we return False for all
 
603
        # 1-item blobs, we will repack them; we may wish to reevaluate our
 
604
        # treatment of large object blobs in the future.
 
605
        if block_size >= self._full_enough_block_size:
 
606
            return True
 
607
        # If a block is <3MB, it still may be considered 'full' if it contains
 
608
        # mixed content. The current rule is 2MB of mixed content is considered
 
609
        # full. So check to see if this block contains mixed content, and
 
610
        # set the threshold appropriately.
 
611
        common_prefix = None
 
612
        for factory in self._factories:
 
613
            prefix = factory.key[:-1]
 
614
            if common_prefix is None:
 
615
                common_prefix = prefix
 
616
            elif prefix != common_prefix:
 
617
                # Mixed content, check the size appropriately
 
618
                if block_size >= self._full_enough_mixed_block_size:
 
619
                    return True
 
620
                break
 
621
        # The content failed both the mixed check and the single-content check
 
622
        # so obviously it is not fully utilized
 
623
        # TODO: there is one other constraint that isn't being checked
 
624
        #       namely, that the entries in the block are in the appropriate
 
625
        #       order. For example, you could insert the entries in exactly
 
626
        #       reverse groupcompress order, and we would think that is ok.
 
627
        #       (all the right objects are in one group, and it is fully
 
628
        #       utilized, etc.) For now, we assume that case is rare,
 
629
        #       especially since we should always fetch in 'groupcompress'
 
630
        #       order.
 
631
        return False
 
632
 
 
633
    def _check_rebuild_block(self):
 
634
        action, last_byte_used, total_bytes_used = self._check_rebuild_action()
 
635
        if action is None:
 
636
            return
 
637
        if action == 'trim':
 
638
            self._trim_block(last_byte_used)
 
639
        elif action == 'rebuild':
 
640
            self._rebuild_block()
 
641
        else:
 
642
            raise ValueError('unknown rebuild action: %r' % (action,))
475
643
 
476
644
    def _wire_bytes(self):
477
645
        """Return a byte stream suitable for transmitting over the wire."""
686
854
 
687
855
        After calling this, the compressor should no longer be used
688
856
        """
689
 
        content = ''.join(self.chunks)
 
857
        # TODO: this causes us to 'bloat' to 2x the size of content in the
 
858
        #       group. This has an impact for 'commit' of large objects.
 
859
        #       One possibility is to use self._content_chunks, and be lazy and
 
860
        #       only fill out self._content as a full string when we actually
 
861
        #       need it. That would at least drop the peak memory consumption
 
862
        #       for 'commit' down to ~1x the size of the largest file, at a
 
863
        #       cost of increased complexity within this code. 2x is still <<
 
864
        #       3x the size of the largest file, so we are doing ok.
 
865
        self._block.set_chunked_content(self.chunks, self.endpoint)
690
866
        self.chunks = None
691
867
        self._delta_index = None
692
 
        self._block.set_content(content)
693
868
        return self._block
694
869
 
695
870
    def pop_last(self):
743
918
        # Before insertion
744
919
        start = self.endpoint
745
920
        chunk_start = len(self.chunks)
 
921
        self._last = (chunk_start, self.endpoint)
746
922
        self._delta_index.extend_lines(out_lines, index_lines)
747
923
        self.endpoint = self._delta_index.endpoint
748
924
        self.input_bytes += input_len
828
1004
        self.endpoint = endpoint
829
1005
 
830
1006
 
831
 
def make_pack_factory(graph, delta, keylength):
 
1007
def make_pack_factory(graph, delta, keylength, inconsistency_fatal=True):
832
1008
    """Create a factory for creating a pack based groupcompress.
833
1009
 
834
1010
    This is only functional enough to run interface tests, it doesn't try to
849
1025
        writer = pack.ContainerWriter(stream.write)
850
1026
        writer.begin()
851
1027
        index = _GCGraphIndex(graph_index, lambda:True, parents=parents,
852
 
            add_callback=graph_index.add_nodes)
853
 
        access = _DirectPackAccess({})
 
1028
            add_callback=graph_index.add_nodes,
 
1029
            inconsistency_fatal=inconsistency_fatal)
 
1030
        access = knit._DirectPackAccess({})
854
1031
        access.set_writer(writer, graph_index, (transport, 'newpack'))
855
1032
        result = GroupCompressVersionedFiles(index, access, delta)
856
1033
        result.stream = stream
864
1041
    versioned_files.stream.close()
865
1042
 
866
1043
 
 
1044
class _BatchingBlockFetcher(object):
 
1045
    """Fetch group compress blocks in batches.
 
1046
    
 
1047
    :ivar total_bytes: int of expected number of bytes needed to fetch the
 
1048
        currently pending batch.
 
1049
    """
 
1050
 
 
1051
    def __init__(self, gcvf, locations):
 
1052
        self.gcvf = gcvf
 
1053
        self.locations = locations
 
1054
        self.keys = []
 
1055
        self.batch_memos = {}
 
1056
        self.memos_to_get = []
 
1057
        self.total_bytes = 0
 
1058
        self.last_read_memo = None
 
1059
        self.manager = None
 
1060
 
 
1061
    def add_key(self, key):
 
1062
        """Add another to key to fetch.
 
1063
        
 
1064
        :return: The estimated number of bytes needed to fetch the batch so
 
1065
            far.
 
1066
        """
 
1067
        self.keys.append(key)
 
1068
        index_memo, _, _, _ = self.locations[key]
 
1069
        read_memo = index_memo[0:3]
 
1070
        # Three possibilities for this read_memo:
 
1071
        #  - it's already part of this batch; or
 
1072
        #  - it's not yet part of this batch, but is already cached; or
 
1073
        #  - it's not yet part of this batch and will need to be fetched.
 
1074
        if read_memo in self.batch_memos:
 
1075
            # This read memo is already in this batch.
 
1076
            return self.total_bytes
 
1077
        try:
 
1078
            cached_block = self.gcvf._group_cache[read_memo]
 
1079
        except KeyError:
 
1080
            # This read memo is new to this batch, and the data isn't cached
 
1081
            # either.
 
1082
            self.batch_memos[read_memo] = None
 
1083
            self.memos_to_get.append(read_memo)
 
1084
            byte_length = read_memo[2]
 
1085
            self.total_bytes += byte_length
 
1086
        else:
 
1087
            # This read memo is new to this batch, but cached.
 
1088
            # Keep a reference to the cached block in batch_memos because it's
 
1089
            # certain that we'll use it when this batch is processed, but
 
1090
            # there's a risk that it would fall out of _group_cache between now
 
1091
            # and then.
 
1092
            self.batch_memos[read_memo] = cached_block
 
1093
        return self.total_bytes
 
1094
        
 
1095
    def _flush_manager(self):
 
1096
        if self.manager is not None:
 
1097
            for factory in self.manager.get_record_stream():
 
1098
                yield factory
 
1099
            self.manager = None
 
1100
            self.last_read_memo = None
 
1101
 
 
1102
    def yield_factories(self, full_flush=False):
 
1103
        """Yield factories for keys added since the last yield.  They will be
 
1104
        returned in the order they were added via add_key.
 
1105
        
 
1106
        :param full_flush: by default, some results may not be returned in case
 
1107
            they can be part of the next batch.  If full_flush is True, then
 
1108
            all results are returned.
 
1109
        """
 
1110
        if self.manager is None and not self.keys:
 
1111
            return
 
1112
        # Fetch all memos in this batch.
 
1113
        blocks = self.gcvf._get_blocks(self.memos_to_get)
 
1114
        # Turn blocks into factories and yield them.
 
1115
        memos_to_get_stack = list(self.memos_to_get)
 
1116
        memos_to_get_stack.reverse()
 
1117
        for key in self.keys:
 
1118
            index_memo, _, parents, _ = self.locations[key]
 
1119
            read_memo = index_memo[:3]
 
1120
            if self.last_read_memo != read_memo:
 
1121
                # We are starting a new block. If we have a
 
1122
                # manager, we have found everything that fits for
 
1123
                # now, so yield records
 
1124
                for factory in self._flush_manager():
 
1125
                    yield factory
 
1126
                # Now start a new manager.
 
1127
                if memos_to_get_stack and memos_to_get_stack[-1] == read_memo:
 
1128
                    # The next block from _get_blocks will be the block we
 
1129
                    # need.
 
1130
                    block_read_memo, block = blocks.next()
 
1131
                    if block_read_memo != read_memo:
 
1132
                        raise AssertionError(
 
1133
                            "block_read_memo out of sync with read_memo"
 
1134
                            "(%r != %r)" % (block_read_memo, read_memo))
 
1135
                    self.batch_memos[read_memo] = block
 
1136
                    memos_to_get_stack.pop()
 
1137
                else:
 
1138
                    block = self.batch_memos[read_memo]
 
1139
                self.manager = _LazyGroupContentManager(block)
 
1140
                self.last_read_memo = read_memo
 
1141
            start, end = index_memo[3:5]
 
1142
            self.manager.add_factory(key, parents, start, end)
 
1143
        if full_flush:
 
1144
            for factory in self._flush_manager():
 
1145
                yield factory
 
1146
        del self.keys[:]
 
1147
        self.batch_memos.clear()
 
1148
        del self.memos_to_get[:]
 
1149
        self.total_bytes = 0
 
1150
 
 
1151
 
867
1152
class GroupCompressVersionedFiles(VersionedFiles):
868
1153
    """A group-compress based VersionedFiles implementation."""
869
1154
 
870
 
    def __init__(self, index, access, delta=True):
 
1155
    def __init__(self, index, access, delta=True, _unadded_refs=None):
871
1156
        """Create a GroupCompressVersionedFiles object.
872
1157
 
873
1158
        :param index: The index object storing access and graph data.
874
1159
        :param access: The access object storing raw data.
875
1160
        :param delta: Whether to delta compress or just entropy compress.
 
1161
        :param _unadded_refs: private parameter, don't use.
876
1162
        """
877
1163
        self._index = index
878
1164
        self._access = access
879
1165
        self._delta = delta
880
 
        self._unadded_refs = {}
 
1166
        if _unadded_refs is None:
 
1167
            _unadded_refs = {}
 
1168
        self._unadded_refs = _unadded_refs
881
1169
        self._group_cache = LRUSizeCache(max_size=50*1024*1024)
882
1170
        self._fallback_vfs = []
883
1171
 
 
1172
    def without_fallbacks(self):
 
1173
        """Return a clone of this object without any fallbacks configured."""
 
1174
        return GroupCompressVersionedFiles(self._index, self._access,
 
1175
            self._delta, _unadded_refs=dict(self._unadded_refs))
 
1176
 
884
1177
    def add_lines(self, key, parents, lines, parent_texts=None,
885
1178
        left_matching_blocks=None, nostore_sha=None, random_id=False,
886
1179
        check_content=True):
931
1224
                                               nostore_sha=nostore_sha))[0]
932
1225
        return sha1, length, None
933
1226
 
 
1227
    def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
 
1228
        """See VersionedFiles._add_text()."""
 
1229
        self._index._check_write_ok()
 
1230
        self._check_add(key, None, random_id, check_content=False)
 
1231
        if text.__class__ is not str:
 
1232
            raise errors.BzrBadParameterUnicode("text")
 
1233
        if parents is None:
 
1234
            # The caller might pass None if there is no graph data, but kndx
 
1235
            # indexes can't directly store that, so we give them
 
1236
            # an empty tuple instead.
 
1237
            parents = ()
 
1238
        # double handling for now. Make it work until then.
 
1239
        length = len(text)
 
1240
        record = FulltextContentFactory(key, parents, None, text)
 
1241
        sha1 = list(self._insert_record_stream([record], random_id=random_id,
 
1242
                                               nostore_sha=nostore_sha))[0]
 
1243
        return sha1, length, None
 
1244
 
934
1245
    def add_fallback_versioned_files(self, a_versioned_files):
935
1246
        """Add a source of texts for texts not present in this knit.
936
1247
 
940
1251
 
941
1252
    def annotate(self, key):
942
1253
        """See VersionedFiles.annotate."""
943
 
        graph = Graph(self)
944
 
        parent_map = self.get_parent_map([key])
945
 
        if not parent_map:
946
 
            raise errors.RevisionNotPresent(key, self)
947
 
        if parent_map[key] is not None:
948
 
            search = graph._make_breadth_first_searcher([key])
949
 
            keys = set()
950
 
            while True:
951
 
                try:
952
 
                    present, ghosts = search.next_with_ghosts()
953
 
                except StopIteration:
954
 
                    break
955
 
                keys.update(present)
956
 
            parent_map = self.get_parent_map(keys)
957
 
        else:
958
 
            keys = [key]
959
 
            parent_map = {key:()}
960
 
        head_cache = _mod_graph.FrozenHeadsCache(graph)
961
 
        parent_cache = {}
962
 
        reannotate = annotate.reannotate
963
 
        for record in self.get_record_stream(keys, 'topological', True):
964
 
            key = record.key
965
 
            chunks = osutils.chunks_to_lines(record.get_bytes_as('chunked'))
966
 
            parent_lines = [parent_cache[parent] for parent in parent_map[key]]
967
 
            parent_cache[key] = list(
968
 
                reannotate(parent_lines, chunks, key, None, head_cache))
969
 
        return parent_cache[key]
970
 
 
971
 
    def check(self, progress_bar=None):
 
1254
        ann = annotate.Annotator(self)
 
1255
        return ann.annotate_flat(key)
 
1256
 
 
1257
    def get_annotator(self):
 
1258
        return annotate.Annotator(self)
 
1259
 
 
1260
    def check(self, progress_bar=None, keys=None):
972
1261
        """See VersionedFiles.check()."""
973
 
        keys = self.keys()
974
 
        for record in self.get_record_stream(keys, 'unordered', True):
975
 
            record.get_bytes_as('fulltext')
 
1262
        if keys is None:
 
1263
            keys = self.keys()
 
1264
            for record in self.get_record_stream(keys, 'unordered', True):
 
1265
                record.get_bytes_as('fulltext')
 
1266
        else:
 
1267
            return self.get_record_stream(keys, 'unordered', True)
 
1268
 
 
1269
    def clear_cache(self):
 
1270
        """See VersionedFiles.clear_cache()"""
 
1271
        self._group_cache.clear()
 
1272
        self._index._graph_index.clear_cache()
 
1273
        self._index._int_cache.clear()
976
1274
 
977
1275
    def _check_add(self, key, lines, random_id, check_content):
978
1276
        """check that version_id and lines are safe to add."""
989
1287
            self._check_lines_not_unicode(lines)
990
1288
            self._check_lines_are_lines(lines)
991
1289
 
 
1290
    def get_known_graph_ancestry(self, keys):
 
1291
        """Get a KnownGraph instance with the ancestry of keys."""
 
1292
        # Note that this is identical to
 
1293
        # KnitVersionedFiles.get_known_graph_ancestry, but they don't share
 
1294
        # ancestry.
 
1295
        parent_map, missing_keys = self._index.find_ancestry(keys)
 
1296
        for fallback in self._fallback_vfs:
 
1297
            if not missing_keys:
 
1298
                break
 
1299
            (f_parent_map, f_missing_keys) = fallback._index.find_ancestry(
 
1300
                                                missing_keys)
 
1301
            parent_map.update(f_parent_map)
 
1302
            missing_keys = f_missing_keys
 
1303
        kg = _mod_graph.KnownGraph(parent_map)
 
1304
        return kg
 
1305
 
992
1306
    def get_parent_map(self, keys):
993
1307
        """Get a map of the graph parents of keys.
994
1308
 
1021
1335
            missing.difference_update(set(new_result))
1022
1336
        return result, source_results
1023
1337
 
1024
 
    def _get_block(self, index_memo):
1025
 
        read_memo = index_memo[0:3]
1026
 
        # get the group:
1027
 
        try:
1028
 
            block = self._group_cache[read_memo]
1029
 
        except KeyError:
1030
 
            # read the group
1031
 
            zdata = self._access.get_raw_records([read_memo]).next()
1032
 
            # decompress - whole thing - this is not a bug, as it
1033
 
            # permits caching. We might want to store the partially
1034
 
            # decompresed group and decompress object, so that recent
1035
 
            # texts are not penalised by big groups.
1036
 
            block = GroupCompressBlock.from_bytes(zdata)
1037
 
            self._group_cache[read_memo] = block
1038
 
        # cheapo debugging:
1039
 
        # print len(zdata), len(plain)
1040
 
        # parse - requires split_lines, better to have byte offsets
1041
 
        # here (but not by much - we only split the region for the
1042
 
        # recipe, and we often want to end up with lines anyway.
1043
 
        return block
 
1338
    def _get_blocks(self, read_memos):
 
1339
        """Get GroupCompressBlocks for the given read_memos.
 
1340
 
 
1341
        :returns: a series of (read_memo, block) pairs, in the order they were
 
1342
            originally passed.
 
1343
        """
 
1344
        cached = {}
 
1345
        for read_memo in read_memos:
 
1346
            try:
 
1347
                block = self._group_cache[read_memo]
 
1348
            except KeyError:
 
1349
                pass
 
1350
            else:
 
1351
                cached[read_memo] = block
 
1352
        not_cached = []
 
1353
        not_cached_seen = set()
 
1354
        for read_memo in read_memos:
 
1355
            if read_memo in cached:
 
1356
                # Don't fetch what we already have
 
1357
                continue
 
1358
            if read_memo in not_cached_seen:
 
1359
                # Don't try to fetch the same data twice
 
1360
                continue
 
1361
            not_cached.append(read_memo)
 
1362
            not_cached_seen.add(read_memo)
 
1363
        raw_records = self._access.get_raw_records(not_cached)
 
1364
        for read_memo in read_memos:
 
1365
            try:
 
1366
                yield read_memo, cached[read_memo]
 
1367
            except KeyError:
 
1368
                # Read the block, and cache it.
 
1369
                zdata = raw_records.next()
 
1370
                block = GroupCompressBlock.from_bytes(zdata)
 
1371
                self._group_cache[read_memo] = block
 
1372
                cached[read_memo] = block
 
1373
                yield read_memo, block
1044
1374
 
1045
1375
    def get_missing_compression_parent_keys(self):
1046
1376
        """Return the keys of missing compression parents.
1212
1542
                unadded_keys, source_result)
1213
1543
        for key in missing:
1214
1544
            yield AbsentContentFactory(key)
1215
 
        manager = None
1216
 
        last_read_memo = None
1217
 
        # TODO: This works fairly well at batching up existing groups into a
1218
 
        #       streamable format, and possibly allowing for taking one big
1219
 
        #       group and splitting it when it isn't fully utilized.
1220
 
        #       However, it doesn't allow us to find under-utilized groups and
1221
 
        #       combine them into a bigger group on the fly.
1222
 
        #       (Consider the issue with how chk_map inserts texts
1223
 
        #       one-at-a-time.) This could be done at insert_record_stream()
1224
 
        #       time, but it probably would decrease the number of
1225
 
        #       bytes-on-the-wire for fetch.
 
1545
        # Batch up as many keys as we can until either:
 
1546
        #  - we encounter an unadded ref, or
 
1547
        #  - we run out of keys, or
 
1548
        #  - the total bytes to retrieve for this batch > BATCH_SIZE
 
1549
        batcher = _BatchingBlockFetcher(self, locations)
1226
1550
        for source, keys in source_keys:
1227
1551
            if source is self:
1228
1552
                for key in keys:
1229
1553
                    if key in self._unadded_refs:
1230
 
                        if manager is not None:
1231
 
                            for factory in manager.get_record_stream():
1232
 
                                yield factory
1233
 
                            last_read_memo = manager = None
 
1554
                        # Flush batch, then yield unadded ref from
 
1555
                        # self._compressor.
 
1556
                        for factory in batcher.yield_factories(full_flush=True):
 
1557
                            yield factory
1234
1558
                        bytes, sha1 = self._compressor.extract(key)
1235
1559
                        parents = self._unadded_refs[key]
1236
1560
                        yield FulltextContentFactory(key, parents, sha1, bytes)
1237
 
                    else:
1238
 
                        index_memo, _, parents, (method, _) = locations[key]
1239
 
                        read_memo = index_memo[0:3]
1240
 
                        if last_read_memo != read_memo:
1241
 
                            # We are starting a new block. If we have a
1242
 
                            # manager, we have found everything that fits for
1243
 
                            # now, so yield records
1244
 
                            if manager is not None:
1245
 
                                for factory in manager.get_record_stream():
1246
 
                                    yield factory
1247
 
                            # Now start a new manager
1248
 
                            block = self._get_block(index_memo)
1249
 
                            manager = _LazyGroupContentManager(block)
1250
 
                            last_read_memo = read_memo
1251
 
                        start, end = index_memo[3:5]
1252
 
                        manager.add_factory(key, parents, start, end)
 
1561
                        continue
 
1562
                    if batcher.add_key(key) > BATCH_SIZE:
 
1563
                        # Ok, this batch is big enough.  Yield some results.
 
1564
                        for factory in batcher.yield_factories():
 
1565
                            yield factory
1253
1566
            else:
1254
 
                if manager is not None:
1255
 
                    for factory in manager.get_record_stream():
1256
 
                        yield factory
1257
 
                    last_read_memo = manager = None
 
1567
                for factory in batcher.yield_factories(full_flush=True):
 
1568
                    yield factory
1258
1569
                for record in source.get_record_stream(keys, ordering,
1259
1570
                                                       include_delta_closure):
1260
1571
                    yield record
1261
 
        if manager is not None:
1262
 
            for factory in manager.get_record_stream():
1263
 
                yield factory
 
1572
        for factory in batcher.yield_factories(full_flush=True):
 
1573
            yield factory
1264
1574
 
1265
1575
    def get_sha1s(self, keys):
1266
1576
        """See VersionedFiles.get_sha1s()."""
1321
1631
        keys_to_add = []
1322
1632
        def flush():
1323
1633
            bytes = self._compressor.flush().to_bytes()
 
1634
            self._compressor = GroupCompressor()
1324
1635
            index, start, length = self._access.add_raw_records(
1325
1636
                [(None, len(bytes))], bytes)[0]
1326
1637
            nodes = []
1329
1640
            self._index.add_records(nodes, random_id=random_id)
1330
1641
            self._unadded_refs = {}
1331
1642
            del keys_to_add[:]
1332
 
            self._compressor = GroupCompressor()
1333
1643
 
1334
1644
        last_prefix = None
1335
1645
        max_fulltext_len = 0
1339
1649
        block_length = None
1340
1650
        # XXX: TODO: remove this, it is just for safety checking for now
1341
1651
        inserted_keys = set()
 
1652
        reuse_this_block = reuse_blocks
1342
1653
        for record in stream:
1343
1654
            # Raise an error when a record is missing.
1344
1655
            if record.storage_kind == 'absent':
1352
1663
            if reuse_blocks:
1353
1664
                # If the reuse_blocks flag is set, check to see if we can just
1354
1665
                # copy a groupcompress block as-is.
 
1666
                # We only check on the first record (groupcompress-block) not
 
1667
                # on all of the (groupcompress-block-ref) entries.
 
1668
                # The reuse_this_block flag is then kept for as long as
 
1669
                if record.storage_kind == 'groupcompress-block':
 
1670
                    # Check to see if we really want to re-use this block
 
1671
                    insert_manager = record._manager
 
1672
                    reuse_this_block = insert_manager.check_is_well_utilized()
 
1673
            else:
 
1674
                reuse_this_block = False
 
1675
            if reuse_this_block:
 
1676
                # We still want to reuse this block
1355
1677
                if record.storage_kind == 'groupcompress-block':
1356
1678
                    # Insert the raw block into the target repo
1357
1679
                    insert_manager = record._manager
1358
 
                    insert_manager._check_rebuild_block()
1359
1680
                    bytes = record._manager._block.to_bytes()
1360
1681
                    _, start, length = self._access.add_raw_records(
1361
1682
                        [(None, len(bytes))], bytes)[0]
1366
1687
                                           'groupcompress-block-ref'):
1367
1688
                    if insert_manager is None:
1368
1689
                        raise AssertionError('No insert_manager set')
 
1690
                    if insert_manager is not record._manager:
 
1691
                        raise AssertionError('insert_manager does not match'
 
1692
                            ' the current record, we cannot be positive'
 
1693
                            ' that the appropriate content was inserted.'
 
1694
                            )
1369
1695
                    value = "%d %d %d %d" % (block_start, block_length,
1370
1696
                                             record._start, record._end)
1371
1697
                    nodes = [(record.key, value, (record.parents,))]
1421
1747
                key = record.key
1422
1748
            self._unadded_refs[key] = record.parents
1423
1749
            yield found_sha1
1424
 
            keys_to_add.append((key, '%d %d' % (start_point, end_point),
1425
 
                (record.parents,)))
 
1750
            as_st = static_tuple.StaticTuple.from_sequence
 
1751
            if record.parents is not None:
 
1752
                parents = as_st([as_st(p) for p in record.parents])
 
1753
            else:
 
1754
                parents = None
 
1755
            refs = static_tuple.StaticTuple(parents)
 
1756
            keys_to_add.append((key, '%d %d' % (start_point, end_point), refs))
1426
1757
        if len(keys_to_add):
1427
1758
            flush()
1428
1759
        self._compressor = None
1448
1779
 
1449
1780
        :return: An iterator over (line, key).
1450
1781
        """
1451
 
        if pb is None:
1452
 
            pb = progress.DummyProgress()
1453
1782
        keys = set(keys)
1454
1783
        total = len(keys)
1455
1784
        # we don't care about inclusions, the caller cares.
1459
1788
            'unordered', True)):
1460
1789
            # XXX: todo - optimise to use less than full texts.
1461
1790
            key = record.key
1462
 
            pb.update('Walking content', key_idx, total)
 
1791
            if pb is not None:
 
1792
                pb.update('Walking content', key_idx, total)
1463
1793
            if record.storage_kind == 'absent':
1464
1794
                raise errors.RevisionNotPresent(key, self)
1465
1795
            lines = osutils.split_lines(record.get_bytes_as('fulltext'))
1466
1796
            for line in lines:
1467
1797
                yield line, key
1468
 
        pb.update('Walking content', total, total)
 
1798
        if pb is not None:
 
1799
            pb.update('Walking content', total, total)
1469
1800
 
1470
1801
    def keys(self):
1471
1802
        """See VersionedFiles.keys."""
1482
1813
    """Mapper from GroupCompressVersionedFiles needs into GraphIndex storage."""
1483
1814
 
1484
1815
    def __init__(self, graph_index, is_locked, parents=True,
1485
 
        add_callback=None):
 
1816
        add_callback=None, track_external_parent_refs=False,
 
1817
        inconsistency_fatal=True, track_new_keys=False):
1486
1818
        """Construct a _GCGraphIndex on a graph_index.
1487
1819
 
1488
1820
        :param graph_index: An implementation of bzrlib.index.GraphIndex.
1493
1825
        :param add_callback: If not None, allow additions to the index and call
1494
1826
            this callback with a list of added GraphIndex nodes:
1495
1827
            [(node, value, node_refs), ...]
 
1828
        :param track_external_parent_refs: As keys are added, keep track of the
 
1829
            keys they reference, so that we can query get_missing_parents(),
 
1830
            etc.
 
1831
        :param inconsistency_fatal: When asked to add records that are already
 
1832
            present, and the details are inconsistent with the existing
 
1833
            record, raise an exception instead of warning (and skipping the
 
1834
            record).
1496
1835
        """
1497
1836
        self._add_callback = add_callback
1498
1837
        self._graph_index = graph_index
1499
1838
        self._parents = parents
1500
1839
        self.has_graph = parents
1501
1840
        self._is_locked = is_locked
 
1841
        self._inconsistency_fatal = inconsistency_fatal
 
1842
        # GroupCompress records tend to have the same 'group' start + offset
 
1843
        # repeated over and over, this creates a surplus of ints
 
1844
        self._int_cache = {}
 
1845
        if track_external_parent_refs:
 
1846
            self._key_dependencies = knit._KeyRefs(
 
1847
                track_new_keys=track_new_keys)
 
1848
        else:
 
1849
            self._key_dependencies = None
1502
1850
 
1503
1851
    def add_records(self, records, random_id=False):
1504
1852
        """Add multiple records to the index.
1525
1873
                if refs:
1526
1874
                    for ref in refs:
1527
1875
                        if ref:
1528
 
                            raise KnitCorrupt(self,
 
1876
                            raise errors.KnitCorrupt(self,
1529
1877
                                "attempt to add node with parents "
1530
1878
                                "in parentless index.")
1531
1879
                    refs = ()
1535
1883
        if not random_id:
1536
1884
            present_nodes = self._get_entries(keys)
1537
1885
            for (index, key, value, node_refs) in present_nodes:
1538
 
                if node_refs != keys[key][1]:
1539
 
                    raise errors.KnitCorrupt(self, "inconsistent details in add_records"
1540
 
                        ": %s %s" % ((value, node_refs), keys[key]))
 
1886
                # Sometimes these are passed as a list rather than a tuple
 
1887
                node_refs = static_tuple.as_tuples(node_refs)
 
1888
                passed = static_tuple.as_tuples(keys[key])
 
1889
                if node_refs != passed[1]:
 
1890
                    details = '%s %s %s' % (key, (value, node_refs), passed)
 
1891
                    if self._inconsistency_fatal:
 
1892
                        raise errors.KnitCorrupt(self, "inconsistent details"
 
1893
                                                 " in add_records: %s" %
 
1894
                                                 details)
 
1895
                    else:
 
1896
                        trace.warning("inconsistent details in skipped"
 
1897
                                      " record: %s", details)
1541
1898
                del keys[key]
1542
1899
                changed = True
1543
1900
        if changed:
1549
1906
                for key, (value, node_refs) in keys.iteritems():
1550
1907
                    result.append((key, value))
1551
1908
            records = result
 
1909
        key_dependencies = self._key_dependencies
 
1910
        if key_dependencies is not None:
 
1911
            if self._parents:
 
1912
                for key, value, refs in records:
 
1913
                    parents = refs[0]
 
1914
                    key_dependencies.add_references(key, parents)
 
1915
            else:
 
1916
                for key, value, refs in records:
 
1917
                    new_keys.add_key(key)
1552
1918
        self._add_callback(records)
1553
1919
 
1554
1920
    def _check_read(self):
1583
1949
        if check_present:
1584
1950
            missing_keys = keys.difference(found_keys)
1585
1951
            if missing_keys:
1586
 
                raise RevisionNotPresent(missing_keys.pop(), self)
 
1952
                raise errors.RevisionNotPresent(missing_keys.pop(), self)
 
1953
 
 
1954
    def find_ancestry(self, keys):
 
1955
        """See CombinedGraphIndex.find_ancestry"""
 
1956
        return self._graph_index.find_ancestry(keys, 0)
1587
1957
 
1588
1958
    def get_parent_map(self, keys):
1589
1959
        """Get a map of the parents of keys.
1603
1973
                result[node[1]] = None
1604
1974
        return result
1605
1975
 
 
1976
    def get_missing_parents(self):
 
1977
        """Return the keys of missing parents."""
 
1978
        # Copied from _KnitGraphIndex.get_missing_parents
 
1979
        # We may have false positives, so filter those out.
 
1980
        self._key_dependencies.satisfy_refs_for_keys(
 
1981
            self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
 
1982
        return frozenset(self._key_dependencies.get_unsatisfied_refs())
 
1983
 
1606
1984
    def get_build_details(self, keys):
1607
1985
        """Get the various build details for keys.
1608
1986
 
1648
2026
        """Convert an index value to position details."""
1649
2027
        bits = node[2].split(' ')
1650
2028
        # It would be nice not to read the entire gzip.
 
2029
        # start and stop are put into _int_cache because they are very common.
 
2030
        # They define the 'group' that an entry is in, and many groups can have
 
2031
        # thousands of objects.
 
2032
        # Branching Launchpad, for example, saves ~600k integers, at 12 bytes
 
2033
        # each, or about 7MB. Note that it might be even more when you consider
 
2034
        # how PyInt is allocated in separate slabs. And you can't return a slab
 
2035
        # to the OS if even 1 int on it is in use. Note though that Python uses
 
2036
        # a LIFO when re-using PyInt slots, which probably causes more
 
2037
        # fragmentation.
1651
2038
        start = int(bits[0])
 
2039
        start = self._int_cache.setdefault(start, start)
1652
2040
        stop = int(bits[1])
 
2041
        stop = self._int_cache.setdefault(stop, stop)
1653
2042
        basis_end = int(bits[2])
1654
2043
        delta_end = int(bits[3])
1655
 
        return node[0], start, stop, basis_end, delta_end
 
2044
        # We can't use StaticTuple here, because node[0] is a BTreeGraphIndex
 
2045
        # instance...
 
2046
        return (node[0], start, stop, basis_end, delta_end)
 
2047
 
 
2048
    def scan_unvalidated_index(self, graph_index):
 
2049
        """Inform this _GCGraphIndex that there is an unvalidated index.
 
2050
 
 
2051
        This allows this _GCGraphIndex to keep track of any missing
 
2052
        compression parents we may want to have filled in to make those
 
2053
        indices valid.  It also allows _GCGraphIndex to track any new keys.
 
2054
 
 
2055
        :param graph_index: A GraphIndex
 
2056
        """
 
2057
        key_dependencies = self._key_dependencies
 
2058
        if key_dependencies is None:
 
2059
            return
 
2060
        for node in graph_index.iter_all_entries():
 
2061
            # Add parent refs from graph_index (and discard parent refs
 
2062
            # that the graph_index has).
 
2063
            key_dependencies.add_references(node[1], node[3][0])
1656
2064
 
1657
2065
 
1658
2066
from bzrlib._groupcompress_py import (
1660
2068
    apply_delta_to_source,
1661
2069
    encode_base128_int,
1662
2070
    decode_base128_int,
 
2071
    decode_copy_instruction,
1663
2072
    LinesDeltaIndex,
1664
2073
    )
1665
2074
try:
1671
2080
        decode_base128_int,
1672
2081
        )
1673
2082
    GroupCompressor = PyrexGroupCompressor
1674
 
except ImportError:
 
2083
except ImportError, e:
 
2084
    osutils.failed_to_load_extension(e)
1675
2085
    GroupCompressor = PythonGroupCompressor
1676
2086