1
# Copyright (C) 2008-2011 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
"""Core compression logic for compressing streams of related files."""
19
from __future__ import absolute_import
24
from bzrlib.lazy_import import lazy_import
25
lazy_import(globals(), """
39
from bzrlib.repofmt import pack_repo
40
from bzrlib.i18n import gettext
43
from bzrlib.btree_index import BTreeBuilder
44
from bzrlib.lru_cache import LRUSizeCache
45
from bzrlib.versionedfile import (
49
ChunkedContentFactory,
50
FulltextContentFactory,
51
VersionedFilesWithFallbacks,
54
# Minimum number of uncompressed bytes to try fetch at once when retrieving
55
# groupcompress blocks.
58
# osutils.sha_string('')
59
_null_sha1 = 'da39a3ee5e6b4b0d3255bfef95601890afd80709'
61
def sort_gc_optimal(parent_map):
62
"""Sort and group the keys in parent_map into groupcompress order.
64
groupcompress is defined (currently) as reverse-topological order, grouped
67
:return: A sorted-list of keys
69
# groupcompress ordering is approximately reverse topological,
70
# properly grouped by file-id.
72
for key, value in parent_map.iteritems():
73
if isinstance(key, str) or len(key) == 1:
78
per_prefix_map[prefix][key] = value
80
per_prefix_map[prefix] = {key: value}
83
for prefix in sorted(per_prefix_map):
84
present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
88
# The max zlib window size is 32kB, so if we set 'max_size' output of the
89
# decompressor to the requested bytes + 32kB, then we should guarantee
90
# num_bytes coming out.
91
_ZLIB_DECOMP_WINDOW = 32*1024
93
class GroupCompressBlock(object):
94
"""An object which maintains the internal structure of the compressed data.
96
This tracks the meta info (start of text, length, type, etc.)
99
# Group Compress Block v1 Zlib
100
GCB_HEADER = 'gcb1z\n'
101
# Group Compress Block v1 Lzma
102
GCB_LZ_HEADER = 'gcb1l\n'
103
GCB_KNOWN_HEADERS = (GCB_HEADER, GCB_LZ_HEADER)
106
# map by key? or just order in file?
107
self._compressor_name = None
108
self._z_content_chunks = None
109
self._z_content_decompressor = None
110
self._z_content_length = None
111
self._content_length = None
113
self._content_chunks = None
116
# This is the maximum number of bytes this object will reference if
117
# everything is decompressed. However, if we decompress less than
118
# everything... (this would cause some problems for LRUSizeCache)
119
return self._content_length + self._z_content_length
121
def _ensure_content(self, num_bytes=None):
122
"""Make sure that content has been expanded enough.
124
:param num_bytes: Ensure that we have extracted at least num_bytes of
125
content. If None, consume everything
127
if self._content_length is None:
128
raise AssertionError('self._content_length should never be None')
129
if num_bytes is None:
130
num_bytes = self._content_length
131
elif (self._content_length is not None
132
and num_bytes > self._content_length):
133
raise AssertionError(
134
'requested num_bytes (%d) > content length (%d)'
135
% (num_bytes, self._content_length))
136
# Expand the content if required
137
if self._content is None:
138
if self._content_chunks is not None:
139
self._content = ''.join(self._content_chunks)
140
self._content_chunks = None
141
if self._content is None:
142
# We join self._z_content_chunks here, because if we are
143
# decompressing, then it is *very* likely that we have a single
145
if self._z_content_chunks is None:
146
raise AssertionError('No content to decompress')
147
z_content = ''.join(self._z_content_chunks)
150
elif self._compressor_name == 'lzma':
151
# We don't do partial lzma decomp yet
153
self._content = pylzma.decompress(z_content)
154
elif self._compressor_name == 'zlib':
155
# Start a zlib decompressor
156
if num_bytes * 4 > self._content_length * 3:
157
# If we are requesting more that 3/4ths of the content,
158
# just extract the whole thing in a single pass
159
num_bytes = self._content_length
160
self._content = zlib.decompress(z_content)
162
self._z_content_decompressor = zlib.decompressobj()
163
# Seed the decompressor with the uncompressed bytes, so
164
# that the rest of the code is simplified
165
self._content = self._z_content_decompressor.decompress(
166
z_content, num_bytes + _ZLIB_DECOMP_WINDOW)
167
if not self._z_content_decompressor.unconsumed_tail:
168
self._z_content_decompressor = None
170
raise AssertionError('Unknown compressor: %r'
171
% self._compressor_name)
172
# Any bytes remaining to be decompressed will be in the decompressors
175
# Do we have enough bytes already?
176
if len(self._content) >= num_bytes:
178
# If we got this far, and don't have a decompressor, something is wrong
179
if self._z_content_decompressor is None:
180
raise AssertionError(
181
'No decompressor to decompress %d bytes' % num_bytes)
182
remaining_decomp = self._z_content_decompressor.unconsumed_tail
183
if not remaining_decomp:
184
raise AssertionError('Nothing left to decompress')
185
needed_bytes = num_bytes - len(self._content)
186
# We always set max_size to 32kB over the minimum needed, so that
187
# zlib will give us as much as we really want.
188
# TODO: If this isn't good enough, we could make a loop here,
189
# that keeps expanding the request until we get enough
190
self._content += self._z_content_decompressor.decompress(
191
remaining_decomp, needed_bytes + _ZLIB_DECOMP_WINDOW)
192
if len(self._content) < num_bytes:
193
raise AssertionError('%d bytes wanted, only %d available'
194
% (num_bytes, len(self._content)))
195
if not self._z_content_decompressor.unconsumed_tail:
196
# The stream is finished
197
self._z_content_decompressor = None
199
def _parse_bytes(self, bytes, pos):
200
"""Read the various lengths from the header.
202
This also populates the various 'compressed' buffers.
204
:return: The position in bytes just after the last newline
206
# At present, we have 2 integers for the compressed and uncompressed
207
# content. In base10 (ascii) 14 bytes can represent > 1TB, so to avoid
208
# checking too far, cap the search to 14 bytes.
209
pos2 = bytes.index('\n', pos, pos + 14)
210
self._z_content_length = int(bytes[pos:pos2])
212
pos2 = bytes.index('\n', pos, pos + 14)
213
self._content_length = int(bytes[pos:pos2])
215
if len(bytes) != (pos + self._z_content_length):
216
# XXX: Define some GCCorrupt error ?
217
raise AssertionError('Invalid bytes: (%d) != %d + %d' %
218
(len(bytes), pos, self._z_content_length))
219
self._z_content_chunks = (bytes[pos:],)
222
def _z_content(self):
223
"""Return z_content_chunks as a simple string.
225
Meant only to be used by the test suite.
227
if self._z_content_chunks is not None:
228
return ''.join(self._z_content_chunks)
232
def from_bytes(cls, bytes):
234
if bytes[:6] not in cls.GCB_KNOWN_HEADERS:
235
raise ValueError('bytes did not start with any of %r'
236
% (cls.GCB_KNOWN_HEADERS,))
237
# XXX: why not testing the whole header ?
239
out._compressor_name = 'zlib'
240
elif bytes[4] == 'l':
241
out._compressor_name = 'lzma'
243
raise ValueError('unknown compressor: %r' % (bytes,))
244
out._parse_bytes(bytes, 6)
247
def extract(self, key, start, end, sha1=None):
248
"""Extract the text for a specific key.
250
:param key: The label used for this content
251
:param sha1: TODO (should we validate only when sha1 is supplied?)
252
:return: The bytes for the content
254
if start == end == 0:
256
self._ensure_content(end)
257
# The bytes are 'f' or 'd' for the type, then a variable-length
258
# base128 integer for the content size, then the actual content
259
# We know that the variable-length integer won't be longer than 5
260
# bytes (it takes 5 bytes to encode 2^32)
261
c = self._content[start]
266
raise ValueError('Unknown content control code: %s'
269
content_len, len_len = decode_base128_int(
270
self._content[start + 1:start + 6])
271
content_start = start + 1 + len_len
272
if end != content_start + content_len:
273
raise ValueError('end != len according to field header'
274
' %s != %s' % (end, content_start + content_len))
276
bytes = self._content[content_start:end]
278
bytes = apply_delta_to_source(self._content, content_start, end)
281
def set_chunked_content(self, content_chunks, length):
282
"""Set the content of this block to the given chunks."""
283
# If we have lots of short lines, it is may be more efficient to join
284
# the content ahead of time. If the content is <10MiB, we don't really
285
# care about the extra memory consumption, so we can just pack it and
286
# be done. However, timing showed 18s => 17.9s for repacking 1k revs of
287
# mysql, which is below the noise margin
288
self._content_length = length
289
self._content_chunks = content_chunks
291
self._z_content_chunks = None
293
def set_content(self, content):
294
"""Set the content of this block."""
295
self._content_length = len(content)
296
self._content = content
297
self._z_content_chunks = None
299
def _create_z_content_from_chunks(self, chunks):
300
compressor = zlib.compressobj(zlib.Z_DEFAULT_COMPRESSION)
301
# Peak in this point is 1 fulltext, 1 compressed text, + zlib overhead
302
# (measured peak is maybe 30MB over the above...)
303
compressed_chunks = map(compressor.compress, chunks)
304
compressed_chunks.append(compressor.flush())
305
# Ignore empty chunks
306
self._z_content_chunks = [c for c in compressed_chunks if c]
307
self._z_content_length = sum(map(len, self._z_content_chunks))
309
def _create_z_content(self):
310
if self._z_content_chunks is not None:
312
if self._content_chunks is not None:
313
chunks = self._content_chunks
315
chunks = (self._content,)
316
self._create_z_content_from_chunks(chunks)
319
"""Create the byte stream as a series of 'chunks'"""
320
self._create_z_content()
321
header = self.GCB_HEADER
322
chunks = ['%s%d\n%d\n'
323
% (header, self._z_content_length, self._content_length),
325
chunks.extend(self._z_content_chunks)
326
total_len = sum(map(len, chunks))
327
return total_len, chunks
330
"""Encode the information into a byte stream."""
331
total_len, chunks = self.to_chunks()
332
return ''.join(chunks)
334
def _dump(self, include_text=False):
335
"""Take this block, and spit out a human-readable structure.
337
:param include_text: Inserts also include text bits, chose whether you
338
want this displayed in the dump or not.
339
:return: A dump of the given block. The layout is something like:
340
[('f', length), ('d', delta_length, text_length, [delta_info])]
341
delta_info := [('i', num_bytes, text), ('c', offset, num_bytes),
344
self._ensure_content()
347
while pos < self._content_length:
348
kind = self._content[pos]
350
if kind not in ('f', 'd'):
351
raise ValueError('invalid kind character: %r' % (kind,))
352
content_len, len_len = decode_base128_int(
353
self._content[pos:pos + 5])
355
if content_len + pos > self._content_length:
356
raise ValueError('invalid content_len %d for record @ pos %d'
357
% (content_len, pos - len_len - 1))
358
if kind == 'f': # Fulltext
360
text = self._content[pos:pos+content_len]
361
result.append(('f', content_len, text))
363
result.append(('f', content_len))
364
elif kind == 'd': # Delta
365
delta_content = self._content[pos:pos+content_len]
367
# The first entry in a delta is the decompressed length
368
decomp_len, delta_pos = decode_base128_int(delta_content)
369
result.append(('d', content_len, decomp_len, delta_info))
371
while delta_pos < content_len:
372
c = ord(delta_content[delta_pos])
376
delta_pos) = decode_copy_instruction(delta_content, c,
379
text = self._content[offset:offset+length]
380
delta_info.append(('c', offset, length, text))
382
delta_info.append(('c', offset, length))
383
measured_len += length
386
txt = delta_content[delta_pos:delta_pos+c]
389
delta_info.append(('i', c, txt))
392
if delta_pos != content_len:
393
raise ValueError('Delta consumed a bad number of bytes:'
394
' %d != %d' % (delta_pos, content_len))
395
if measured_len != decomp_len:
396
raise ValueError('Delta claimed fulltext was %d bytes, but'
397
' extraction resulted in %d bytes'
398
% (decomp_len, measured_len))
403
class _LazyGroupCompressFactory(object):
404
"""Yield content from a GroupCompressBlock on demand."""
406
def __init__(self, key, parents, manager, start, end, first):
407
"""Create a _LazyGroupCompressFactory
409
:param key: The key of just this record
410
:param parents: The parents of this key (possibly None)
411
:param gc_block: A GroupCompressBlock object
412
:param start: Offset of the first byte for this record in the
414
:param end: Offset of the byte just after the end of this record
415
(ie, bytes = content[start:end])
416
:param first: Is this the first Factory for the given block?
419
self.parents = parents
421
# Note: This attribute coupled with Manager._factories creates a
422
# reference cycle. Perhaps we would rather use a weakref(), or
423
# find an appropriate time to release the ref. After the first
424
# get_bytes_as call? After Manager.get_record_stream() returns
426
self._manager = manager
428
self.storage_kind = 'groupcompress-block'
430
self.storage_kind = 'groupcompress-block-ref'
436
return '%s(%s, first=%s)' % (self.__class__.__name__,
437
self.key, self._first)
439
def get_bytes_as(self, storage_kind):
440
if storage_kind == self.storage_kind:
442
# wire bytes, something...
443
return self._manager._wire_bytes()
446
if storage_kind in ('fulltext', 'chunked'):
447
if self._bytes is None:
448
# Grab and cache the raw bytes for this entry
449
# and break the ref-cycle with _manager since we don't need it
452
self._manager._prepare_for_extract()
453
except zlib.error as value:
454
raise errors.DecompressCorruption("zlib: " + str(value))
455
block = self._manager._block
456
self._bytes = block.extract(self.key, self._start, self._end)
457
# There are code paths that first extract as fulltext, and then
458
# extract as storage_kind (smart fetch). So we don't break the
459
# refcycle here, but instead in manager.get_record_stream()
460
if storage_kind == 'fulltext':
464
raise errors.UnavailableRepresentation(self.key, storage_kind,
468
class _LazyGroupContentManager(object):
469
"""This manages a group of _LazyGroupCompressFactory objects."""
471
_max_cut_fraction = 0.75 # We allow a block to be trimmed to 75% of
472
# current size, and still be considered
474
_full_block_size = 4*1024*1024
475
_full_mixed_block_size = 2*1024*1024
476
_full_enough_block_size = 3*1024*1024 # size at which we won't repack
477
_full_enough_mixed_block_size = 2*768*1024 # 1.5MB
479
def __init__(self, block, get_compressor_settings=None):
481
# We need to preserve the ordering
484
self._get_settings = get_compressor_settings
485
self._compressor_settings = None
487
def _get_compressor_settings(self):
488
if self._compressor_settings is not None:
489
return self._compressor_settings
491
if self._get_settings is not None:
492
settings = self._get_settings()
494
vf = GroupCompressVersionedFiles
495
settings = vf._DEFAULT_COMPRESSOR_SETTINGS
496
self._compressor_settings = settings
497
return self._compressor_settings
499
def add_factory(self, key, parents, start, end):
500
if not self._factories:
504
# Note that this creates a reference cycle....
505
factory = _LazyGroupCompressFactory(key, parents, self,
506
start, end, first=first)
507
# max() works here, but as a function call, doing a compare seems to be
508
# significantly faster, timeit says 250ms for max() and 100ms for the
510
if end > self._last_byte:
511
self._last_byte = end
512
self._factories.append(factory)
514
def get_record_stream(self):
515
"""Get a record for all keys added so far."""
516
for factory in self._factories:
518
# Break the ref-cycle
519
factory._bytes = None
520
factory._manager = None
521
# TODO: Consider setting self._factories = None after the above loop,
522
# as it will break the reference cycle
524
def _trim_block(self, last_byte):
525
"""Create a new GroupCompressBlock, with just some of the content."""
526
# None of the factories need to be adjusted, because the content is
527
# located in an identical place. Just that some of the unreferenced
528
# trailing bytes are stripped
529
trace.mutter('stripping trailing bytes from groupcompress block'
530
' %d => %d', self._block._content_length, last_byte)
531
new_block = GroupCompressBlock()
532
self._block._ensure_content(last_byte)
533
new_block.set_content(self._block._content[:last_byte])
534
self._block = new_block
536
def _make_group_compressor(self):
537
return GroupCompressor(self._get_compressor_settings())
539
def _rebuild_block(self):
540
"""Create a new GroupCompressBlock with only the referenced texts."""
541
compressor = self._make_group_compressor()
543
old_length = self._block._content_length
545
for factory in self._factories:
546
bytes = factory.get_bytes_as('fulltext')
547
(found_sha1, start_point, end_point,
548
type) = compressor.compress(factory.key, bytes, factory.sha1)
549
# Now update this factory with the new offsets, etc
550
factory.sha1 = found_sha1
551
factory._start = start_point
552
factory._end = end_point
553
self._last_byte = end_point
554
new_block = compressor.flush()
555
# TODO: Should we check that new_block really *is* smaller than the old
556
# block? It seems hard to come up with a method that it would
557
# expand, since we do full compression again. Perhaps based on a
558
# request that ends up poorly ordered?
559
# TODO: If the content would have expanded, then we would want to
560
# handle a case where we need to split the block.
561
# Now that we have a user-tweakable option
562
# (max_bytes_to_index), it is possible that one person set it
563
# to a very low value, causing poor compression.
564
delta = time.time() - tstart
565
self._block = new_block
566
trace.mutter('creating new compressed block on-the-fly in %.3fs'
567
' %d bytes => %d bytes', delta, old_length,
568
self._block._content_length)
570
def _prepare_for_extract(self):
571
"""A _LazyGroupCompressFactory is about to extract to fulltext."""
572
# We expect that if one child is going to fulltext, all will be. This
573
# helps prevent all of them from extracting a small amount at a time.
574
# Which in itself isn't terribly expensive, but resizing 2MB 32kB at a
575
# time (self._block._content) is a little expensive.
576
self._block._ensure_content(self._last_byte)
578
def _check_rebuild_action(self):
579
"""Check to see if our block should be repacked."""
582
for factory in self._factories:
583
total_bytes_used += factory._end - factory._start
584
if last_byte_used < factory._end:
585
last_byte_used = factory._end
586
# If we are using more than half of the bytes from the block, we have
587
# nothing else to check
588
if total_bytes_used * 2 >= self._block._content_length:
589
return None, last_byte_used, total_bytes_used
590
# We are using less than 50% of the content. Is the content we are
591
# using at the beginning of the block? If so, we can just trim the
592
# tail, rather than rebuilding from scratch.
593
if total_bytes_used * 2 > last_byte_used:
594
return 'trim', last_byte_used, total_bytes_used
596
# We are using a small amount of the data, and it isn't just packed
597
# nicely at the front, so rebuild the content.
598
# Note: This would be *nicer* as a strip-data-from-group, rather than
599
# building it up again from scratch
600
# It might be reasonable to consider the fulltext sizes for
601
# different bits when deciding this, too. As you may have a small
602
# fulltext, and a trivial delta, and you are just trading around
603
# for another fulltext. If we do a simple 'prune' you may end up
604
# expanding many deltas into fulltexts, as well.
605
# If we build a cheap enough 'strip', then we could try a strip,
606
# if that expands the content, we then rebuild.
607
return 'rebuild', last_byte_used, total_bytes_used
609
def check_is_well_utilized(self):
610
"""Is the current block considered 'well utilized'?
612
This heuristic asks if the current block considers itself to be a fully
613
developed group, rather than just a loose collection of data.
615
if len(self._factories) == 1:
616
# A block of length 1 could be improved by combining with other
617
# groups - don't look deeper. Even larger than max size groups
618
# could compress well with adjacent versions of the same thing.
620
action, last_byte_used, total_bytes_used = self._check_rebuild_action()
621
block_size = self._block._content_length
622
if total_bytes_used < block_size * self._max_cut_fraction:
623
# This block wants to trim itself small enough that we want to
624
# consider it under-utilized.
626
# TODO: This code is meant to be the twin of _insert_record_stream's
627
# 'start_new_block' logic. It would probably be better to factor
628
# out that logic into a shared location, so that it stays
630
# We currently assume a block is properly utilized whenever it is >75%
631
# of the size of a 'full' block. In normal operation, a block is
632
# considered full when it hits 4MB of same-file content. So any block
633
# >3MB is 'full enough'.
634
# The only time this isn't true is when a given block has large-object
635
# content. (a single file >4MB, etc.)
636
# Under these circumstances, we allow a block to grow to
637
# 2 x largest_content. Which means that if a given block had a large
638
# object, it may actually be under-utilized. However, given that this
639
# is 'pack-on-the-fly' it is probably reasonable to not repack large
640
# content blobs on-the-fly. Note that because we return False for all
641
# 1-item blobs, we will repack them; we may wish to reevaluate our
642
# treatment of large object blobs in the future.
643
if block_size >= self._full_enough_block_size:
645
# If a block is <3MB, it still may be considered 'full' if it contains
646
# mixed content. The current rule is 2MB of mixed content is considered
647
# full. So check to see if this block contains mixed content, and
648
# set the threshold appropriately.
650
for factory in self._factories:
651
prefix = factory.key[:-1]
652
if common_prefix is None:
653
common_prefix = prefix
654
elif prefix != common_prefix:
655
# Mixed content, check the size appropriately
656
if block_size >= self._full_enough_mixed_block_size:
659
# The content failed both the mixed check and the single-content check
660
# so obviously it is not fully utilized
661
# TODO: there is one other constraint that isn't being checked
662
# namely, that the entries in the block are in the appropriate
663
# order. For example, you could insert the entries in exactly
664
# reverse groupcompress order, and we would think that is ok.
665
# (all the right objects are in one group, and it is fully
666
# utilized, etc.) For now, we assume that case is rare,
667
# especially since we should always fetch in 'groupcompress'
671
def _check_rebuild_block(self):
672
action, last_byte_used, total_bytes_used = self._check_rebuild_action()
676
self._trim_block(last_byte_used)
677
elif action == 'rebuild':
678
self._rebuild_block()
680
raise ValueError('unknown rebuild action: %r' % (action,))
682
def _wire_bytes(self):
683
"""Return a byte stream suitable for transmitting over the wire."""
684
self._check_rebuild_block()
685
# The outer block starts with:
686
# 'groupcompress-block\n'
687
# <length of compressed key info>\n
688
# <length of uncompressed info>\n
689
# <length of gc block>\n
692
lines = ['groupcompress-block\n']
693
# The minimal info we need is the key, the start offset, and the
694
# parents. The length and type are encoded in the record itself.
695
# However, passing in the other bits makes it easier. The list of
696
# keys, and the start offset, the length
698
# 1 line with parents, '' for ()
699
# 1 line for start offset
700
# 1 line for end byte
702
for factory in self._factories:
703
key_bytes = '\x00'.join(factory.key)
704
parents = factory.parents
706
parent_bytes = 'None:'
708
parent_bytes = '\t'.join('\x00'.join(key) for key in parents)
709
record_header = '%s\n%s\n%d\n%d\n' % (
710
key_bytes, parent_bytes, factory._start, factory._end)
711
header_lines.append(record_header)
712
# TODO: Can we break the refcycle at this point and set
713
# factory._manager = None?
714
header_bytes = ''.join(header_lines)
716
header_bytes_len = len(header_bytes)
717
z_header_bytes = zlib.compress(header_bytes)
719
z_header_bytes_len = len(z_header_bytes)
720
block_bytes_len, block_chunks = self._block.to_chunks()
721
lines.append('%d\n%d\n%d\n' % (z_header_bytes_len, header_bytes_len,
723
lines.append(z_header_bytes)
724
lines.extend(block_chunks)
725
del z_header_bytes, block_chunks
726
# TODO: This is a point where we will double the memory consumption. To
727
# avoid this, we probably have to switch to a 'chunked' api
728
return ''.join(lines)
731
def from_bytes(cls, bytes):
732
# TODO: This does extra string copying, probably better to do it a
733
# different way. At a minimum this creates 2 copies of the
735
(storage_kind, z_header_len, header_len,
736
block_len, rest) = bytes.split('\n', 4)
738
if storage_kind != 'groupcompress-block':
739
raise ValueError('Unknown storage kind: %s' % (storage_kind,))
740
z_header_len = int(z_header_len)
741
if len(rest) < z_header_len:
742
raise ValueError('Compressed header len shorter than all bytes')
743
z_header = rest[:z_header_len]
744
header_len = int(header_len)
745
header = zlib.decompress(z_header)
746
if len(header) != header_len:
747
raise ValueError('invalid length for decompressed bytes')
749
block_len = int(block_len)
750
if len(rest) != z_header_len + block_len:
751
raise ValueError('Invalid length for block')
752
block_bytes = rest[z_header_len:]
754
# So now we have a valid GCB, we just need to parse the factories that
756
header_lines = header.split('\n')
758
last = header_lines.pop()
760
raise ValueError('header lines did not end with a trailing'
762
if len(header_lines) % 4 != 0:
763
raise ValueError('The header was not an even multiple of 4 lines')
764
block = GroupCompressBlock.from_bytes(block_bytes)
767
for start in xrange(0, len(header_lines), 4):
769
key = tuple(header_lines[start].split('\x00'))
770
parents_line = header_lines[start+1]
771
if parents_line == 'None:':
774
parents = tuple([tuple(segment.split('\x00'))
775
for segment in parents_line.split('\t')
777
start_offset = int(header_lines[start+2])
778
end_offset = int(header_lines[start+3])
779
result.add_factory(key, parents, start_offset, end_offset)
783
def network_block_to_records(storage_kind, bytes, line_end):
784
if storage_kind != 'groupcompress-block':
785
raise ValueError('Unknown storage kind: %s' % (storage_kind,))
786
manager = _LazyGroupContentManager.from_bytes(bytes)
787
return manager.get_record_stream()
790
class _CommonGroupCompressor(object):
792
def __init__(self, settings=None):
793
"""Create a GroupCompressor."""
798
self.labels_deltas = {}
799
self._delta_index = None # Set by the children
800
self._block = GroupCompressBlock()
804
self._settings = settings
806
def compress(self, key, bytes, expected_sha, nostore_sha=None, soft=False):
807
"""Compress lines with label key.
809
:param key: A key tuple. It is stored in the output
810
for identification of the text during decompression. If the last
811
element is 'None' it is replaced with the sha1 of the text -
813
:param bytes: The bytes to be compressed
814
:param expected_sha: If non-None, the sha the lines are believed to
815
have. During compression the sha is calculated; a mismatch will
817
:param nostore_sha: If the computed sha1 sum matches, we will raise
818
ExistingContent rather than adding the text.
819
:param soft: Do a 'soft' compression. This means that we require larger
820
ranges to match to be considered for a copy command.
822
:return: The sha1 of lines, the start and end offsets in the delta, and
823
the type ('fulltext' or 'delta').
825
:seealso VersionedFiles.add_lines:
827
if not bytes: # empty, like a dir entry, etc
828
if nostore_sha == _null_sha1:
829
raise errors.ExistingContent()
830
return _null_sha1, 0, 0, 'fulltext'
831
# we assume someone knew what they were doing when they passed it in
832
if expected_sha is not None:
835
sha1 = osutils.sha_string(bytes)
836
if nostore_sha is not None:
837
if sha1 == nostore_sha:
838
raise errors.ExistingContent()
840
key = key[:-1] + ('sha1:' + sha1,)
842
start, end, type = self._compress(key, bytes, len(bytes) / 2, soft)
843
return sha1, start, end, type
845
def _compress(self, key, bytes, max_delta_size, soft=False):
846
"""Compress lines with label key.
848
:param key: A key tuple. It is stored in the output for identification
849
of the text during decompression.
851
:param bytes: The bytes to be compressed
853
:param max_delta_size: The size above which we issue a fulltext instead
856
:param soft: Do a 'soft' compression. This means that we require larger
857
ranges to match to be considered for a copy command.
859
:return: The sha1 of lines, the start and end offsets in the delta, and
860
the type ('fulltext' or 'delta').
862
raise NotImplementedError(self._compress)
864
def extract(self, key):
865
"""Extract a key previously added to the compressor.
867
:param key: The key to extract.
868
:return: An iterable over bytes and the sha1.
870
(start_byte, start_chunk, end_byte, end_chunk) = self.labels_deltas[key]
871
delta_chunks = self.chunks[start_chunk:end_chunk]
872
stored_bytes = ''.join(delta_chunks)
873
if stored_bytes[0] == 'f':
874
fulltext_len, offset = decode_base128_int(stored_bytes[1:10])
875
data_len = fulltext_len + 1 + offset
876
if data_len != len(stored_bytes):
877
raise ValueError('Index claimed fulltext len, but stored bytes'
879
% (len(stored_bytes), data_len))
880
bytes = stored_bytes[offset + 1:]
882
# XXX: This is inefficient at best
883
source = ''.join(self.chunks[:start_chunk])
884
if stored_bytes[0] != 'd':
885
raise ValueError('Unknown content kind, bytes claim %s'
886
% (stored_bytes[0],))
887
delta_len, offset = decode_base128_int(stored_bytes[1:10])
888
data_len = delta_len + 1 + offset
889
if data_len != len(stored_bytes):
890
raise ValueError('Index claimed delta len, but stored bytes'
892
% (len(stored_bytes), data_len))
893
bytes = apply_delta(source, stored_bytes[offset + 1:])
894
bytes_sha1 = osutils.sha_string(bytes)
895
return bytes, bytes_sha1
898
"""Finish this group, creating a formatted stream.
900
After calling this, the compressor should no longer be used
902
self._block.set_chunked_content(self.chunks, self.endpoint)
904
self._delta_index = None
908
"""Call this if you want to 'revoke' the last compression.
910
After this, the data structures will be rolled back, but you cannot do
913
self._delta_index = None
914
del self.chunks[self._last[0]:]
915
self.endpoint = self._last[1]
919
"""Return the overall compression ratio."""
920
return float(self.input_bytes) / float(self.endpoint)
923
class PythonGroupCompressor(_CommonGroupCompressor):
925
def __init__(self, settings=None):
926
"""Create a GroupCompressor.
928
Used only if the pyrex version is not available.
930
super(PythonGroupCompressor, self).__init__(settings)
931
self._delta_index = LinesDeltaIndex([])
932
# The actual content is managed by LinesDeltaIndex
933
self.chunks = self._delta_index.lines
935
def _compress(self, key, bytes, max_delta_size, soft=False):
936
"""see _CommonGroupCompressor._compress"""
937
input_len = len(bytes)
938
new_lines = osutils.split_lines(bytes)
939
out_lines, index_lines = self._delta_index.make_delta(
940
new_lines, bytes_length=input_len, soft=soft)
941
delta_length = sum(map(len, out_lines))
942
if delta_length > max_delta_size:
943
# The delta is longer than the fulltext, insert a fulltext
945
out_lines = ['f', encode_base128_int(input_len)]
946
out_lines.extend(new_lines)
947
index_lines = [False, False]
948
index_lines.extend([True] * len(new_lines))
950
# this is a worthy delta, output it
953
# Update the delta_length to include those two encoded integers
954
out_lines[1] = encode_base128_int(delta_length)
956
start = self.endpoint
957
chunk_start = len(self.chunks)
958
self._last = (chunk_start, self.endpoint)
959
self._delta_index.extend_lines(out_lines, index_lines)
960
self.endpoint = self._delta_index.endpoint
961
self.input_bytes += input_len
962
chunk_end = len(self.chunks)
963
self.labels_deltas[key] = (start, chunk_start,
964
self.endpoint, chunk_end)
965
return start, self.endpoint, type
968
class PyrexGroupCompressor(_CommonGroupCompressor):
969
"""Produce a serialised group of compressed texts.
971
It contains code very similar to SequenceMatcher because of having a similar
972
task. However some key differences apply:
974
* there is no junk, we want a minimal edit not a human readable diff.
975
* we don't filter very common lines (because we don't know where a good
976
range will start, and after the first text we want to be emitting minmal
978
* we chain the left side, not the right side
979
* we incrementally update the adjacency matrix as new lines are provided.
980
* we look for matches in all of the left side, so the routine which does
981
the analagous task of find_longest_match does not need to filter on the
985
def __init__(self, settings=None):
986
super(PyrexGroupCompressor, self).__init__(settings)
987
max_bytes_to_index = self._settings.get('max_bytes_to_index', 0)
988
self._delta_index = DeltaIndex(max_bytes_to_index=max_bytes_to_index)
990
def _compress(self, key, bytes, max_delta_size, soft=False):
991
"""see _CommonGroupCompressor._compress"""
992
input_len = len(bytes)
993
# By having action/label/sha1/len, we can parse the group if the index
994
# was ever destroyed, we have the key in 'label', we know the final
995
# bytes are valid from sha1, and we know where to find the end of this
996
# record because of 'len'. (the delta record itself will store the
997
# total length for the expanded record)
998
# 'len: %d\n' costs approximately 1% increase in total data
999
# Having the labels at all costs us 9-10% increase, 38% increase for
1000
# inventory pages, and 5.8% increase for text pages
1001
# new_chunks = ['label:%s\nsha1:%s\n' % (label, sha1)]
1002
if self._delta_index._source_offset != self.endpoint:
1003
raise AssertionError('_source_offset != endpoint'
1004
' somehow the DeltaIndex got out of sync with'
1005
' the output lines')
1006
delta = self._delta_index.make_delta(bytes, max_delta_size)
1009
enc_length = encode_base128_int(len(bytes))
1010
len_mini_header = 1 + len(enc_length)
1011
self._delta_index.add_source(bytes, len_mini_header)
1012
new_chunks = ['f', enc_length, bytes]
1015
enc_length = encode_base128_int(len(delta))
1016
len_mini_header = 1 + len(enc_length)
1017
new_chunks = ['d', enc_length, delta]
1018
self._delta_index.add_delta_source(delta, len_mini_header)
1020
start = self.endpoint
1021
chunk_start = len(self.chunks)
1022
# Now output these bytes
1023
self._output_chunks(new_chunks)
1024
self.input_bytes += input_len
1025
chunk_end = len(self.chunks)
1026
self.labels_deltas[key] = (start, chunk_start,
1027
self.endpoint, chunk_end)
1028
if not self._delta_index._source_offset == self.endpoint:
1029
raise AssertionError('the delta index is out of sync'
1030
'with the output lines %s != %s'
1031
% (self._delta_index._source_offset, self.endpoint))
1032
return start, self.endpoint, type
1034
def _output_chunks(self, new_chunks):
1035
"""Output some chunks.
1037
:param new_chunks: The chunks to output.
1039
self._last = (len(self.chunks), self.endpoint)
1040
endpoint = self.endpoint
1041
self.chunks.extend(new_chunks)
1042
endpoint += sum(map(len, new_chunks))
1043
self.endpoint = endpoint
1046
def make_pack_factory(graph, delta, keylength, inconsistency_fatal=True):
1047
"""Create a factory for creating a pack based groupcompress.
1049
This is only functional enough to run interface tests, it doesn't try to
1050
provide a full pack environment.
1052
:param graph: Store a graph.
1053
:param delta: Delta compress contents.
1054
:param keylength: How long should keys be.
1056
def factory(transport):
1061
graph_index = BTreeBuilder(reference_lists=ref_length,
1062
key_elements=keylength)
1063
stream = transport.open_write_stream('newpack')
1064
writer = pack.ContainerWriter(stream.write)
1066
index = _GCGraphIndex(graph_index, lambda:True, parents=parents,
1067
add_callback=graph_index.add_nodes,
1068
inconsistency_fatal=inconsistency_fatal)
1069
access = pack_repo._DirectPackAccess({})
1070
access.set_writer(writer, graph_index, (transport, 'newpack'))
1071
result = GroupCompressVersionedFiles(index, access, delta)
1072
result.stream = stream
1073
result.writer = writer
1078
def cleanup_pack_group(versioned_files):
1079
versioned_files.writer.end()
1080
versioned_files.stream.close()
1083
class _BatchingBlockFetcher(object):
1084
"""Fetch group compress blocks in batches.
1086
:ivar total_bytes: int of expected number of bytes needed to fetch the
1087
currently pending batch.
1090
def __init__(self, gcvf, locations, get_compressor_settings=None):
1092
self.locations = locations
1094
self.batch_memos = {}
1095
self.memos_to_get = []
1096
self.total_bytes = 0
1097
self.last_read_memo = None
1099
self._get_compressor_settings = get_compressor_settings
1101
def add_key(self, key):
1102
"""Add another to key to fetch.
1104
:return: The estimated number of bytes needed to fetch the batch so
1107
self.keys.append(key)
1108
index_memo, _, _, _ = self.locations[key]
1109
read_memo = index_memo[0:3]
1110
# Three possibilities for this read_memo:
1111
# - it's already part of this batch; or
1112
# - it's not yet part of this batch, but is already cached; or
1113
# - it's not yet part of this batch and will need to be fetched.
1114
if read_memo in self.batch_memos:
1115
# This read memo is already in this batch.
1116
return self.total_bytes
1118
cached_block = self.gcvf._group_cache[read_memo]
1120
# This read memo is new to this batch, and the data isn't cached
1122
self.batch_memos[read_memo] = None
1123
self.memos_to_get.append(read_memo)
1124
byte_length = read_memo[2]
1125
self.total_bytes += byte_length
1127
# This read memo is new to this batch, but cached.
1128
# Keep a reference to the cached block in batch_memos because it's
1129
# certain that we'll use it when this batch is processed, but
1130
# there's a risk that it would fall out of _group_cache between now
1132
self.batch_memos[read_memo] = cached_block
1133
return self.total_bytes
1135
def _flush_manager(self):
1136
if self.manager is not None:
1137
for factory in self.manager.get_record_stream():
1140
self.last_read_memo = None
1142
def yield_factories(self, full_flush=False):
1143
"""Yield factories for keys added since the last yield. They will be
1144
returned in the order they were added via add_key.
1146
:param full_flush: by default, some results may not be returned in case
1147
they can be part of the next batch. If full_flush is True, then
1148
all results are returned.
1150
if self.manager is None and not self.keys:
1152
# Fetch all memos in this batch.
1153
blocks = self.gcvf._get_blocks(self.memos_to_get)
1154
# Turn blocks into factories and yield them.
1155
memos_to_get_stack = list(self.memos_to_get)
1156
memos_to_get_stack.reverse()
1157
for key in self.keys:
1158
index_memo, _, parents, _ = self.locations[key]
1159
read_memo = index_memo[:3]
1160
if self.last_read_memo != read_memo:
1161
# We are starting a new block. If we have a
1162
# manager, we have found everything that fits for
1163
# now, so yield records
1164
for factory in self._flush_manager():
1166
# Now start a new manager.
1167
if memos_to_get_stack and memos_to_get_stack[-1] == read_memo:
1168
# The next block from _get_blocks will be the block we
1170
block_read_memo, block = blocks.next()
1171
if block_read_memo != read_memo:
1172
raise AssertionError(
1173
"block_read_memo out of sync with read_memo"
1174
"(%r != %r)" % (block_read_memo, read_memo))
1175
self.batch_memos[read_memo] = block
1176
memos_to_get_stack.pop()
1178
block = self.batch_memos[read_memo]
1179
self.manager = _LazyGroupContentManager(block,
1180
get_compressor_settings=self._get_compressor_settings)
1181
self.last_read_memo = read_memo
1182
start, end = index_memo[3:5]
1183
self.manager.add_factory(key, parents, start, end)
1185
for factory in self._flush_manager():
1188
self.batch_memos.clear()
1189
del self.memos_to_get[:]
1190
self.total_bytes = 0
1193
class GroupCompressVersionedFiles(VersionedFilesWithFallbacks):
1194
"""A group-compress based VersionedFiles implementation."""
1196
# This controls how the GroupCompress DeltaIndex works. Basically, we
1197
# compute hash pointers into the source blocks (so hash(text) => text).
1198
# However each of these references costs some memory in trade against a
1199
# more accurate match result. For very large files, they either are
1200
# pre-compressed and change in bulk whenever they change, or change in just
1201
# local blocks. Either way, 'improved resolution' is not very helpful,
1202
# versus running out of memory trying to track everything. The default max
1203
# gives 100% sampling of a 1MB file.
1204
_DEFAULT_MAX_BYTES_TO_INDEX = 1024 * 1024
1205
_DEFAULT_COMPRESSOR_SETTINGS = {'max_bytes_to_index':
1206
_DEFAULT_MAX_BYTES_TO_INDEX}
1208
def __init__(self, index, access, delta=True, _unadded_refs=None,
1210
"""Create a GroupCompressVersionedFiles object.
1212
:param index: The index object storing access and graph data.
1213
:param access: The access object storing raw data.
1214
:param delta: Whether to delta compress or just entropy compress.
1215
:param _unadded_refs: private parameter, don't use.
1216
:param _group_cache: private parameter, don't use.
1219
self._access = access
1221
if _unadded_refs is None:
1223
self._unadded_refs = _unadded_refs
1224
if _group_cache is None:
1225
_group_cache = LRUSizeCache(max_size=50*1024*1024)
1226
self._group_cache = _group_cache
1227
self._immediate_fallback_vfs = []
1228
self._max_bytes_to_index = None
1230
def without_fallbacks(self):
1231
"""Return a clone of this object without any fallbacks configured."""
1232
return GroupCompressVersionedFiles(self._index, self._access,
1233
self._delta, _unadded_refs=dict(self._unadded_refs),
1234
_group_cache=self._group_cache)
1236
def add_lines(self, key, parents, lines, parent_texts=None,
1237
left_matching_blocks=None, nostore_sha=None, random_id=False,
1238
check_content=True):
1239
"""Add a text to the store.
1241
:param key: The key tuple of the text to add.
1242
:param parents: The parents key tuples of the text to add.
1243
:param lines: A list of lines. Each line must be a bytestring. And all
1244
of them except the last must be terminated with \\n and contain no
1245
other \\n's. The last line may either contain no \\n's or a single
1246
terminating \\n. If the lines list does meet this constraint the
1247
add routine may error or may succeed - but you will be unable to
1248
read the data back accurately. (Checking the lines have been split
1249
correctly is expensive and extremely unlikely to catch bugs so it
1250
is not done at runtime unless check_content is True.)
1251
:param parent_texts: An optional dictionary containing the opaque
1252
representations of some or all of the parents of version_id to
1253
allow delta optimisations. VERY IMPORTANT: the texts must be those
1254
returned by add_lines or data corruption can be caused.
1255
:param left_matching_blocks: a hint about which areas are common
1256
between the text and its left-hand-parent. The format is
1257
the SequenceMatcher.get_matching_blocks format.
1258
:param nostore_sha: Raise ExistingContent and do not add the lines to
1259
the versioned file if the digest of the lines matches this.
1260
:param random_id: If True a random id has been selected rather than
1261
an id determined by some deterministic process such as a converter
1262
from a foreign VCS. When True the backend may choose not to check
1263
for uniqueness of the resulting key within the versioned file, so
1264
this should only be done when the result is expected to be unique
1266
:param check_content: If True, the lines supplied are verified to be
1267
bytestrings that are correctly formed lines.
1268
:return: The text sha1, the number of bytes in the text, and an opaque
1269
representation of the inserted version which can be provided
1270
back to future add_lines calls in the parent_texts dictionary.
1272
self._index._check_write_ok()
1273
self._check_add(key, lines, random_id, check_content)
1275
# The caller might pass None if there is no graph data, but kndx
1276
# indexes can't directly store that, so we give them
1277
# an empty tuple instead.
1279
# double handling for now. Make it work until then.
1280
length = sum(map(len, lines))
1281
record = ChunkedContentFactory(key, parents, None, lines)
1282
sha1 = list(self._insert_record_stream([record], random_id=random_id,
1283
nostore_sha=nostore_sha))[0]
1284
return sha1, length, None
1286
def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
1287
"""See VersionedFiles._add_text()."""
1288
self._index._check_write_ok()
1289
self._check_add(key, None, random_id, check_content=False)
1290
if text.__class__ is not str:
1291
raise errors.BzrBadParameterUnicode("text")
1293
# The caller might pass None if there is no graph data, but kndx
1294
# indexes can't directly store that, so we give them
1295
# an empty tuple instead.
1297
# double handling for now. Make it work until then.
1299
record = FulltextContentFactory(key, parents, None, text)
1300
sha1 = list(self._insert_record_stream([record], random_id=random_id,
1301
nostore_sha=nostore_sha))[0]
1302
return sha1, length, None
1304
def add_fallback_versioned_files(self, a_versioned_files):
1305
"""Add a source of texts for texts not present in this knit.
1307
:param a_versioned_files: A VersionedFiles object.
1309
self._immediate_fallback_vfs.append(a_versioned_files)
1311
def annotate(self, key):
1312
"""See VersionedFiles.annotate."""
1313
ann = annotate.Annotator(self)
1314
return ann.annotate_flat(key)
1316
def get_annotator(self):
1317
return annotate.Annotator(self)
1319
def check(self, progress_bar=None, keys=None):
1320
"""See VersionedFiles.check()."""
1323
for record in self.get_record_stream(keys, 'unordered', True):
1324
record.get_bytes_as('fulltext')
1326
return self.get_record_stream(keys, 'unordered', True)
1328
def clear_cache(self):
1329
"""See VersionedFiles.clear_cache()"""
1330
self._group_cache.clear()
1331
self._index._graph_index.clear_cache()
1332
self._index._int_cache.clear()
1334
def _check_add(self, key, lines, random_id, check_content):
1335
"""check that version_id and lines are safe to add."""
1336
version_id = key[-1]
1337
if version_id is not None:
1338
if osutils.contains_whitespace(version_id):
1339
raise errors.InvalidRevisionId(version_id, self)
1340
self.check_not_reserved_id(version_id)
1341
# TODO: If random_id==False and the key is already present, we should
1342
# probably check that the existing content is identical to what is
1343
# being inserted, and otherwise raise an exception. This would make
1344
# the bundle code simpler.
1346
self._check_lines_not_unicode(lines)
1347
self._check_lines_are_lines(lines)
1349
def get_parent_map(self, keys):
1350
"""Get a map of the graph parents of keys.
1352
:param keys: The keys to look up parents for.
1353
:return: A mapping from keys to parents. Absent keys are absent from
1356
return self._get_parent_map_with_sources(keys)[0]
1358
def _get_parent_map_with_sources(self, keys):
1359
"""Get a map of the parents of keys.
1361
:param keys: The keys to look up parents for.
1362
:return: A tuple. The first element is a mapping from keys to parents.
1363
Absent keys are absent from the mapping. The second element is a
1364
list with the locations each key was found in. The first element
1365
is the in-this-knit parents, the second the first fallback source,
1369
sources = [self._index] + self._immediate_fallback_vfs
1372
for source in sources:
1375
new_result = source.get_parent_map(missing)
1376
source_results.append(new_result)
1377
result.update(new_result)
1378
missing.difference_update(set(new_result))
1379
return result, source_results
1381
def _get_blocks(self, read_memos):
1382
"""Get GroupCompressBlocks for the given read_memos.
1384
:returns: a series of (read_memo, block) pairs, in the order they were
1388
for read_memo in read_memos:
1390
block = self._group_cache[read_memo]
1394
cached[read_memo] = block
1396
not_cached_seen = set()
1397
for read_memo in read_memos:
1398
if read_memo in cached:
1399
# Don't fetch what we already have
1401
if read_memo in not_cached_seen:
1402
# Don't try to fetch the same data twice
1404
not_cached.append(read_memo)
1405
not_cached_seen.add(read_memo)
1406
raw_records = self._access.get_raw_records(not_cached)
1407
for read_memo in read_memos:
1409
yield read_memo, cached[read_memo]
1411
# Read the block, and cache it.
1412
zdata = raw_records.next()
1413
block = GroupCompressBlock.from_bytes(zdata)
1414
self._group_cache[read_memo] = block
1415
cached[read_memo] = block
1416
yield read_memo, block
1418
def get_missing_compression_parent_keys(self):
1419
"""Return the keys of missing compression parents.
1421
Missing compression parents occur when a record stream was missing
1422
basis texts, or a index was scanned that had missing basis texts.
1424
# GroupCompress cannot currently reference texts that are not in the
1425
# group, so this is valid for now
1428
def get_record_stream(self, keys, ordering, include_delta_closure):
1429
"""Get a stream of records for keys.
1431
:param keys: The keys to include.
1432
:param ordering: Either 'unordered' or 'topological'. A topologically
1433
sorted stream has compression parents strictly before their
1435
:param include_delta_closure: If True then the closure across any
1436
compression parents will be included (in the opaque data).
1437
:return: An iterator of ContentFactory objects, each of which is only
1438
valid until the iterator is advanced.
1440
# keys might be a generator
1441
orig_keys = list(keys)
1445
if (not self._index.has_graph
1446
and ordering in ('topological', 'groupcompress')):
1447
# Cannot topological order when no graph has been stored.
1448
# but we allow 'as-requested' or 'unordered'
1449
ordering = 'unordered'
1451
remaining_keys = keys
1454
keys = set(remaining_keys)
1455
for content_factory in self._get_remaining_record_stream(keys,
1456
orig_keys, ordering, include_delta_closure):
1457
remaining_keys.discard(content_factory.key)
1458
yield content_factory
1460
except errors.RetryWithNewPacks, e:
1461
self._access.reload_or_raise(e)
1463
def _find_from_fallback(self, missing):
1464
"""Find whatever keys you can from the fallbacks.
1466
:param missing: A set of missing keys. This set will be mutated as keys
1467
are found from a fallback_vfs
1468
:return: (parent_map, key_to_source_map, source_results)
1469
parent_map the overall key => parent_keys
1470
key_to_source_map a dict from {key: source}
1471
source_results a list of (source: keys)
1474
key_to_source_map = {}
1476
for source in self._immediate_fallback_vfs:
1479
source_parents = source.get_parent_map(missing)
1480
parent_map.update(source_parents)
1481
source_parents = list(source_parents)
1482
source_results.append((source, source_parents))
1483
key_to_source_map.update((key, source) for key in source_parents)
1484
missing.difference_update(source_parents)
1485
return parent_map, key_to_source_map, source_results
1487
def _get_ordered_source_keys(self, ordering, parent_map, key_to_source_map):
1488
"""Get the (source, [keys]) list.
1490
The returned objects should be in the order defined by 'ordering',
1491
which can weave between different sources.
1493
:param ordering: Must be one of 'topological' or 'groupcompress'
1494
:return: List of [(source, [keys])] tuples, such that all keys are in
1495
the defined order, regardless of source.
1497
if ordering == 'topological':
1498
present_keys = tsort.topo_sort(parent_map)
1500
# ordering == 'groupcompress'
1501
# XXX: This only optimizes for the target ordering. We may need
1502
# to balance that with the time it takes to extract
1503
# ordering, by somehow grouping based on
1504
# locations[key][0:3]
1505
present_keys = sort_gc_optimal(parent_map)
1506
# Now group by source:
1508
current_source = None
1509
for key in present_keys:
1510
source = key_to_source_map.get(key, self)
1511
if source is not current_source:
1512
source_keys.append((source, []))
1513
current_source = source
1514
source_keys[-1][1].append(key)
1517
def _get_as_requested_source_keys(self, orig_keys, locations, unadded_keys,
1520
current_source = None
1521
for key in orig_keys:
1522
if key in locations or key in unadded_keys:
1524
elif key in key_to_source_map:
1525
source = key_to_source_map[key]
1528
if source is not current_source:
1529
source_keys.append((source, []))
1530
current_source = source
1531
source_keys[-1][1].append(key)
1534
def _get_io_ordered_source_keys(self, locations, unadded_keys,
1537
# This is the group the bytes are stored in, followed by the
1538
# location in the group
1539
return locations[key][0]
1540
present_keys = sorted(locations.iterkeys(), key=get_group)
1541
# We don't have an ordering for keys in the in-memory object, but
1542
# lets process the in-memory ones first.
1543
present_keys = list(unadded_keys) + present_keys
1544
# Now grab all of the ones from other sources
1545
source_keys = [(self, present_keys)]
1546
source_keys.extend(source_result)
1549
def _get_remaining_record_stream(self, keys, orig_keys, ordering,
1550
include_delta_closure):
1551
"""Get a stream of records for keys.
1553
:param keys: The keys to include.
1554
:param ordering: one of 'unordered', 'topological', 'groupcompress' or
1556
:param include_delta_closure: If True then the closure across any
1557
compression parents will be included (in the opaque data).
1558
:return: An iterator of ContentFactory objects, each of which is only
1559
valid until the iterator is advanced.
1562
locations = self._index.get_build_details(keys)
1563
unadded_keys = set(self._unadded_refs).intersection(keys)
1564
missing = keys.difference(locations)
1565
missing.difference_update(unadded_keys)
1566
(fallback_parent_map, key_to_source_map,
1567
source_result) = self._find_from_fallback(missing)
1568
if ordering in ('topological', 'groupcompress'):
1569
# would be better to not globally sort initially but instead
1570
# start with one key, recurse to its oldest parent, then grab
1571
# everything in the same group, etc.
1572
parent_map = dict((key, details[2]) for key, details in
1573
locations.iteritems())
1574
for key in unadded_keys:
1575
parent_map[key] = self._unadded_refs[key]
1576
parent_map.update(fallback_parent_map)
1577
source_keys = self._get_ordered_source_keys(ordering, parent_map,
1579
elif ordering == 'as-requested':
1580
source_keys = self._get_as_requested_source_keys(orig_keys,
1581
locations, unadded_keys, key_to_source_map)
1583
# We want to yield the keys in a semi-optimal (read-wise) ordering.
1584
# Otherwise we thrash the _group_cache and destroy performance
1585
source_keys = self._get_io_ordered_source_keys(locations,
1586
unadded_keys, source_result)
1588
yield AbsentContentFactory(key)
1589
# Batch up as many keys as we can until either:
1590
# - we encounter an unadded ref, or
1591
# - we run out of keys, or
1592
# - the total bytes to retrieve for this batch > BATCH_SIZE
1593
batcher = _BatchingBlockFetcher(self, locations,
1594
get_compressor_settings=self._get_compressor_settings)
1595
for source, keys in source_keys:
1598
if key in self._unadded_refs:
1599
# Flush batch, then yield unadded ref from
1601
for factory in batcher.yield_factories(full_flush=True):
1603
bytes, sha1 = self._compressor.extract(key)
1604
parents = self._unadded_refs[key]
1605
yield FulltextContentFactory(key, parents, sha1, bytes)
1607
if batcher.add_key(key) > BATCH_SIZE:
1608
# Ok, this batch is big enough. Yield some results.
1609
for factory in batcher.yield_factories():
1612
for factory in batcher.yield_factories(full_flush=True):
1614
for record in source.get_record_stream(keys, ordering,
1615
include_delta_closure):
1617
for factory in batcher.yield_factories(full_flush=True):
1620
def get_sha1s(self, keys):
1621
"""See VersionedFiles.get_sha1s()."""
1623
for record in self.get_record_stream(keys, 'unordered', True):
1624
if record.sha1 != None:
1625
result[record.key] = record.sha1
1627
if record.storage_kind != 'absent':
1628
result[record.key] = osutils.sha_string(
1629
record.get_bytes_as('fulltext'))
1632
def insert_record_stream(self, stream):
1633
"""Insert a record stream into this container.
1635
:param stream: A stream of records to insert.
1637
:seealso VersionedFiles.get_record_stream:
1639
# XXX: Setting random_id=True makes
1640
# test_insert_record_stream_existing_keys fail for groupcompress and
1641
# groupcompress-nograph, this needs to be revisited while addressing
1642
# 'bzr branch' performance issues.
1643
for _ in self._insert_record_stream(stream, random_id=False):
1646
def _get_compressor_settings(self):
1647
if self._max_bytes_to_index is None:
1648
# TODO: VersionedFiles don't know about their containing
1649
# repository, so they don't have much of an idea about their
1650
# location. So for now, this is only a global option.
1651
c = config.GlobalConfig()
1652
val = c.get_user_option('bzr.groupcompress.max_bytes_to_index')
1656
except ValueError, e:
1657
trace.warning('Value for '
1658
'"bzr.groupcompress.max_bytes_to_index"'
1659
' %r is not an integer'
1663
val = self._DEFAULT_MAX_BYTES_TO_INDEX
1664
self._max_bytes_to_index = val
1665
return {'max_bytes_to_index': self._max_bytes_to_index}
1667
def _make_group_compressor(self):
1668
return GroupCompressor(self._get_compressor_settings())
1670
def _insert_record_stream(self, stream, random_id=False, nostore_sha=None,
1672
"""Internal core to insert a record stream into this container.
1674
This helper function has a different interface than insert_record_stream
1675
to allow add_lines to be minimal, but still return the needed data.
1677
:param stream: A stream of records to insert.
1678
:param nostore_sha: If the sha1 of a given text matches nostore_sha,
1679
raise ExistingContent, rather than committing the new text.
1680
:param reuse_blocks: If the source is streaming from
1681
groupcompress-blocks, just insert the blocks as-is, rather than
1682
expanding the texts and inserting again.
1683
:return: An iterator over the sha1 of the inserted records.
1684
:seealso insert_record_stream:
1688
def get_adapter(adapter_key):
1690
return adapters[adapter_key]
1692
adapter_factory = adapter_registry.get(adapter_key)
1693
adapter = adapter_factory(self)
1694
adapters[adapter_key] = adapter
1696
# This will go up to fulltexts for gc to gc fetching, which isn't
1698
self._compressor = self._make_group_compressor()
1699
self._unadded_refs = {}
1702
bytes_len, chunks = self._compressor.flush().to_chunks()
1703
self._compressor = self._make_group_compressor()
1704
# Note: At this point we still have 1 copy of the fulltext (in
1705
# record and the var 'bytes'), and this generates 2 copies of
1706
# the compressed text (one for bytes, one in chunks)
1707
# TODO: Push 'chunks' down into the _access api, so that we don't
1708
# have to double compressed memory here
1709
# TODO: Figure out how to indicate that we would be happy to free
1710
# the fulltext content at this point. Note that sometimes we
1711
# will want it later (streaming CHK pages), but most of the
1712
# time we won't (everything else)
1713
bytes = ''.join(chunks)
1715
index, start, length = self._access.add_raw_records(
1716
[(None, len(bytes))], bytes)[0]
1718
for key, reads, refs in keys_to_add:
1719
nodes.append((key, "%d %d %s" % (start, length, reads), refs))
1720
self._index.add_records(nodes, random_id=random_id)
1721
self._unadded_refs = {}
1725
max_fulltext_len = 0
1726
max_fulltext_prefix = None
1727
insert_manager = None
1730
# XXX: TODO: remove this, it is just for safety checking for now
1731
inserted_keys = set()
1732
reuse_this_block = reuse_blocks
1733
for record in stream:
1734
# Raise an error when a record is missing.
1735
if record.storage_kind == 'absent':
1736
raise errors.RevisionNotPresent(record.key, self)
1738
if record.key in inserted_keys:
1739
trace.note(gettext('Insert claimed random_id=True,'
1740
' but then inserted %r two times'), record.key)
1742
inserted_keys.add(record.key)
1744
# If the reuse_blocks flag is set, check to see if we can just
1745
# copy a groupcompress block as-is.
1746
# We only check on the first record (groupcompress-block) not
1747
# on all of the (groupcompress-block-ref) entries.
1748
# The reuse_this_block flag is then kept for as long as
1749
if record.storage_kind == 'groupcompress-block':
1750
# Check to see if we really want to re-use this block
1751
insert_manager = record._manager
1752
reuse_this_block = insert_manager.check_is_well_utilized()
1754
reuse_this_block = False
1755
if reuse_this_block:
1756
# We still want to reuse this block
1757
if record.storage_kind == 'groupcompress-block':
1758
# Insert the raw block into the target repo
1759
insert_manager = record._manager
1760
bytes = record._manager._block.to_bytes()
1761
_, start, length = self._access.add_raw_records(
1762
[(None, len(bytes))], bytes)[0]
1765
block_length = length
1766
if record.storage_kind in ('groupcompress-block',
1767
'groupcompress-block-ref'):
1768
if insert_manager is None:
1769
raise AssertionError('No insert_manager set')
1770
if insert_manager is not record._manager:
1771
raise AssertionError('insert_manager does not match'
1772
' the current record, we cannot be positive'
1773
' that the appropriate content was inserted.'
1775
value = "%d %d %d %d" % (block_start, block_length,
1776
record._start, record._end)
1777
nodes = [(record.key, value, (record.parents,))]
1778
# TODO: Consider buffering up many nodes to be added, not
1779
# sure how much overhead this has, but we're seeing
1780
# ~23s / 120s in add_records calls
1781
self._index.add_records(nodes, random_id=random_id)
1784
bytes = record.get_bytes_as('fulltext')
1785
except errors.UnavailableRepresentation:
1786
adapter_key = record.storage_kind, 'fulltext'
1787
adapter = get_adapter(adapter_key)
1788
bytes = adapter.get_bytes(record)
1789
if len(record.key) > 1:
1790
prefix = record.key[0]
1791
soft = (prefix == last_prefix)
1795
if max_fulltext_len < len(bytes):
1796
max_fulltext_len = len(bytes)
1797
max_fulltext_prefix = prefix
1798
(found_sha1, start_point, end_point,
1799
type) = self._compressor.compress(record.key,
1800
bytes, record.sha1, soft=soft,
1801
nostore_sha=nostore_sha)
1802
# delta_ratio = float(len(bytes)) / (end_point - start_point)
1803
# Check if we want to continue to include that text
1804
if (prefix == max_fulltext_prefix
1805
and end_point < 2 * max_fulltext_len):
1806
# As long as we are on the same file_id, we will fill at least
1807
# 2 * max_fulltext_len
1808
start_new_block = False
1809
elif end_point > 4*1024*1024:
1810
start_new_block = True
1811
elif (prefix is not None and prefix != last_prefix
1812
and end_point > 2*1024*1024):
1813
start_new_block = True
1815
start_new_block = False
1816
last_prefix = prefix
1818
self._compressor.pop_last()
1820
max_fulltext_len = len(bytes)
1821
(found_sha1, start_point, end_point,
1822
type) = self._compressor.compress(record.key, bytes,
1824
if record.key[-1] is None:
1825
key = record.key[:-1] + ('sha1:' + found_sha1,)
1828
self._unadded_refs[key] = record.parents
1830
as_st = static_tuple.StaticTuple.from_sequence
1831
if record.parents is not None:
1832
parents = as_st([as_st(p) for p in record.parents])
1835
refs = static_tuple.StaticTuple(parents)
1836
keys_to_add.append((key, '%d %d' % (start_point, end_point), refs))
1837
if len(keys_to_add):
1839
self._compressor = None
1841
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1842
"""Iterate over the lines in the versioned files from keys.
1844
This may return lines from other keys. Each item the returned
1845
iterator yields is a tuple of a line and a text version that that line
1846
is present in (not introduced in).
1848
Ordering of results is in whatever order is most suitable for the
1849
underlying storage format.
1851
If a progress bar is supplied, it may be used to indicate progress.
1852
The caller is responsible for cleaning up progress bars (because this
1856
* Lines are normalised by the underlying store: they will all have \n
1858
* Lines are returned in arbitrary order.
1860
:return: An iterator over (line, key).
1864
# we don't care about inclusions, the caller cares.
1865
# but we need to setup a list of records to visit.
1866
# we need key, position, length
1867
for key_idx, record in enumerate(self.get_record_stream(keys,
1868
'unordered', True)):
1869
# XXX: todo - optimise to use less than full texts.
1872
pb.update('Walking content', key_idx, total)
1873
if record.storage_kind == 'absent':
1874
raise errors.RevisionNotPresent(key, self)
1875
lines = osutils.split_lines(record.get_bytes_as('fulltext'))
1879
pb.update('Walking content', total, total)
1882
"""See VersionedFiles.keys."""
1883
if 'evil' in debug.debug_flags:
1884
trace.mutter_callsite(2, "keys scales with size of history")
1885
sources = [self._index] + self._immediate_fallback_vfs
1887
for source in sources:
1888
result.update(source.keys())
1892
class _GCBuildDetails(object):
1893
"""A blob of data about the build details.
1895
This stores the minimal data, which then allows compatibility with the old
1896
api, without taking as much memory.
1899
__slots__ = ('_index', '_group_start', '_group_end', '_basis_end',
1900
'_delta_end', '_parents')
1903
compression_parent = None
1905
def __init__(self, parents, position_info):
1906
self._parents = parents
1907
(self._index, self._group_start, self._group_end, self._basis_end,
1908
self._delta_end) = position_info
1911
return '%s(%s, %s)' % (self.__class__.__name__,
1912
self.index_memo, self._parents)
1915
def index_memo(self):
1916
return (self._index, self._group_start, self._group_end,
1917
self._basis_end, self._delta_end)
1920
def record_details(self):
1921
return static_tuple.StaticTuple(self.method, None)
1923
def __getitem__(self, offset):
1924
"""Compatibility thunk to act like a tuple."""
1926
return self.index_memo
1928
return self.compression_parent # Always None
1930
return self._parents
1932
return self.record_details
1934
raise IndexError('offset out of range')
1940
class _GCGraphIndex(object):
1941
"""Mapper from GroupCompressVersionedFiles needs into GraphIndex storage."""
1943
def __init__(self, graph_index, is_locked, parents=True,
1944
add_callback=None, track_external_parent_refs=False,
1945
inconsistency_fatal=True, track_new_keys=False):
1946
"""Construct a _GCGraphIndex on a graph_index.
1948
:param graph_index: An implementation of bzrlib.index.GraphIndex.
1949
:param is_locked: A callback, returns True if the index is locked and
1951
:param parents: If True, record knits parents, if not do not record
1953
:param add_callback: If not None, allow additions to the index and call
1954
this callback with a list of added GraphIndex nodes:
1955
[(node, value, node_refs), ...]
1956
:param track_external_parent_refs: As keys are added, keep track of the
1957
keys they reference, so that we can query get_missing_parents(),
1959
:param inconsistency_fatal: When asked to add records that are already
1960
present, and the details are inconsistent with the existing
1961
record, raise an exception instead of warning (and skipping the
1964
self._add_callback = add_callback
1965
self._graph_index = graph_index
1966
self._parents = parents
1967
self.has_graph = parents
1968
self._is_locked = is_locked
1969
self._inconsistency_fatal = inconsistency_fatal
1970
# GroupCompress records tend to have the same 'group' start + offset
1971
# repeated over and over, this creates a surplus of ints
1972
self._int_cache = {}
1973
if track_external_parent_refs:
1974
self._key_dependencies = _KeyRefs(
1975
track_new_keys=track_new_keys)
1977
self._key_dependencies = None
1979
def add_records(self, records, random_id=False):
1980
"""Add multiple records to the index.
1982
This function does not insert data into the Immutable GraphIndex
1983
backing the KnitGraphIndex, instead it prepares data for insertion by
1984
the caller and checks that it is safe to insert then calls
1985
self._add_callback with the prepared GraphIndex nodes.
1987
:param records: a list of tuples:
1988
(key, options, access_memo, parents).
1989
:param random_id: If True the ids being added were randomly generated
1990
and no check for existence will be performed.
1992
if not self._add_callback:
1993
raise errors.ReadOnlyError(self)
1994
# we hope there are no repositories with inconsistent parentage
1999
for (key, value, refs) in records:
2000
if not self._parents:
2004
raise errors.KnitCorrupt(self,
2005
"attempt to add node with parents "
2006
"in parentless index.")
2009
keys[key] = (value, refs)
2012
present_nodes = self._get_entries(keys)
2013
for (index, key, value, node_refs) in present_nodes:
2014
# Sometimes these are passed as a list rather than a tuple
2015
node_refs = static_tuple.as_tuples(node_refs)
2016
passed = static_tuple.as_tuples(keys[key])
2017
if node_refs != passed[1]:
2018
details = '%s %s %s' % (key, (value, node_refs), passed)
2019
if self._inconsistency_fatal:
2020
raise errors.KnitCorrupt(self, "inconsistent details"
2021
" in add_records: %s" %
2024
trace.warning("inconsistent details in skipped"
2025
" record: %s", details)
2031
for key, (value, node_refs) in keys.iteritems():
2032
result.append((key, value, node_refs))
2034
for key, (value, node_refs) in keys.iteritems():
2035
result.append((key, value))
2037
key_dependencies = self._key_dependencies
2038
if key_dependencies is not None:
2040
for key, value, refs in records:
2042
key_dependencies.add_references(key, parents)
2044
for key, value, refs in records:
2045
new_keys.add_key(key)
2046
self._add_callback(records)
2048
def _check_read(self):
2049
"""Raise an exception if reads are not permitted."""
2050
if not self._is_locked():
2051
raise errors.ObjectNotLocked(self)
2053
def _check_write_ok(self):
2054
"""Raise an exception if writes are not permitted."""
2055
if not self._is_locked():
2056
raise errors.ObjectNotLocked(self)
2058
def _get_entries(self, keys, check_present=False):
2059
"""Get the entries for keys.
2061
Note: Callers are responsible for checking that the index is locked
2062
before calling this method.
2064
:param keys: An iterable of index key tuples.
2069
for node in self._graph_index.iter_entries(keys):
2071
found_keys.add(node[1])
2073
# adapt parentless index to the rest of the code.
2074
for node in self._graph_index.iter_entries(keys):
2075
yield node[0], node[1], node[2], ()
2076
found_keys.add(node[1])
2078
missing_keys = keys.difference(found_keys)
2080
raise errors.RevisionNotPresent(missing_keys.pop(), self)
2082
def find_ancestry(self, keys):
2083
"""See CombinedGraphIndex.find_ancestry"""
2084
return self._graph_index.find_ancestry(keys, 0)
2086
def get_parent_map(self, keys):
2087
"""Get a map of the parents of keys.
2089
:param keys: The keys to look up parents for.
2090
:return: A mapping from keys to parents. Absent keys are absent from
2094
nodes = self._get_entries(keys)
2098
result[node[1]] = node[3][0]
2101
result[node[1]] = None
2104
def get_missing_parents(self):
2105
"""Return the keys of missing parents."""
2106
# Copied from _KnitGraphIndex.get_missing_parents
2107
# We may have false positives, so filter those out.
2108
self._key_dependencies.satisfy_refs_for_keys(
2109
self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
2110
return frozenset(self._key_dependencies.get_unsatisfied_refs())
2112
def get_build_details(self, keys):
2113
"""Get the various build details for keys.
2115
Ghosts are omitted from the result.
2117
:param keys: An iterable of keys.
2118
:return: A dict of key:
2119
(index_memo, compression_parent, parents, record_details).
2121
* index_memo: opaque structure to pass to read_records to extract
2123
* compression_parent: Content that this record is built upon, may
2125
* parents: Logical parents of this node
2126
* record_details: extra information about the content which needs
2127
to be passed to Factory.parse_record
2131
entries = self._get_entries(keys)
2132
for entry in entries:
2134
if not self._parents:
2137
parents = entry[3][0]
2138
details = _GCBuildDetails(parents, self._node_to_position(entry))
2139
result[key] = details
2143
"""Get all the keys in the collection.
2145
The keys are not ordered.
2148
return [node[1] for node in self._graph_index.iter_all_entries()]
2150
def _node_to_position(self, node):
2151
"""Convert an index value to position details."""
2152
bits = node[2].split(' ')
2153
# It would be nice not to read the entire gzip.
2154
# start and stop are put into _int_cache because they are very common.
2155
# They define the 'group' that an entry is in, and many groups can have
2156
# thousands of objects.
2157
# Branching Launchpad, for example, saves ~600k integers, at 12 bytes
2158
# each, or about 7MB. Note that it might be even more when you consider
2159
# how PyInt is allocated in separate slabs. And you can't return a slab
2160
# to the OS if even 1 int on it is in use. Note though that Python uses
2161
# a LIFO when re-using PyInt slots, which might cause more
2163
start = int(bits[0])
2164
start = self._int_cache.setdefault(start, start)
2166
stop = self._int_cache.setdefault(stop, stop)
2167
basis_end = int(bits[2])
2168
delta_end = int(bits[3])
2169
# We can't use StaticTuple here, because node[0] is a BTreeGraphIndex
2171
return (node[0], start, stop, basis_end, delta_end)
2173
def scan_unvalidated_index(self, graph_index):
2174
"""Inform this _GCGraphIndex that there is an unvalidated index.
2176
This allows this _GCGraphIndex to keep track of any missing
2177
compression parents we may want to have filled in to make those
2178
indices valid. It also allows _GCGraphIndex to track any new keys.
2180
:param graph_index: A GraphIndex
2182
key_dependencies = self._key_dependencies
2183
if key_dependencies is None:
2185
for node in graph_index.iter_all_entries():
2186
# Add parent refs from graph_index (and discard parent refs
2187
# that the graph_index has).
2188
key_dependencies.add_references(node[1], node[3][0])
2191
from bzrlib._groupcompress_py import (
2193
apply_delta_to_source,
2196
decode_copy_instruction,
2200
from bzrlib._groupcompress_pyx import (
2202
apply_delta_to_source,
2207
GroupCompressor = PyrexGroupCompressor
2208
except ImportError, e:
2209
osutils.failed_to_load_extension(e)
2210
GroupCompressor = PythonGroupCompressor
added
removed
bzrlib/groupcompress.py
