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."""
22
from bzrlib.lazy_import import lazy_import
23
lazy_import(globals(), """
37
from bzrlib.repofmt import pack_repo
38
from bzrlib.i18n import gettext
41
from bzrlib.btree_index import BTreeBuilder
42
from bzrlib.lru_cache import LRUSizeCache
43
from bzrlib.versionedfile import (
47
ChunkedContentFactory,
48
FulltextContentFactory,
49
VersionedFilesWithFallbacks,
52
# Minimum number of uncompressed bytes to try fetch at once when retrieving
53
# groupcompress blocks.
56
# osutils.sha_string('')
57
_null_sha1 = 'da39a3ee5e6b4b0d3255bfef95601890afd80709'
59
def sort_gc_optimal(parent_map):
60
"""Sort and group the keys in parent_map into groupcompress order.
62
groupcompress is defined (currently) as reverse-topological order, grouped
65
:return: A sorted-list of keys
67
# groupcompress ordering is approximately reverse topological,
68
# properly grouped by file-id.
70
for key, value in parent_map.iteritems():
71
if isinstance(key, str) or len(key) == 1:
76
per_prefix_map[prefix][key] = value
78
per_prefix_map[prefix] = {key: value}
81
for prefix in sorted(per_prefix_map):
82
present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
86
# The max zlib window size is 32kB, so if we set 'max_size' output of the
87
# decompressor to the requested bytes + 32kB, then we should guarantee
88
# num_bytes coming out.
89
_ZLIB_DECOMP_WINDOW = 32*1024
91
class GroupCompressBlock(object):
92
"""An object which maintains the internal structure of the compressed data.
94
This tracks the meta info (start of text, length, type, etc.)
97
# Group Compress Block v1 Zlib
98
GCB_HEADER = 'gcb1z\n'
99
# Group Compress Block v1 Lzma
100
GCB_LZ_HEADER = 'gcb1l\n'
101
GCB_KNOWN_HEADERS = (GCB_HEADER, GCB_LZ_HEADER)
104
# map by key? or just order in file?
105
self._compressor_name = None
106
self._z_content_chunks = None
107
self._z_content_decompressor = None
108
self._z_content_length = None
109
self._content_length = None
111
self._content_chunks = None
114
# This is the maximum number of bytes this object will reference if
115
# everything is decompressed. However, if we decompress less than
116
# everything... (this would cause some problems for LRUSizeCache)
117
return self._content_length + self._z_content_length
119
def _ensure_content(self, num_bytes=None):
120
"""Make sure that content has been expanded enough.
122
:param num_bytes: Ensure that we have extracted at least num_bytes of
123
content. If None, consume everything
125
if self._content_length is None:
126
raise AssertionError('self._content_length should never be None')
127
if num_bytes is None:
128
num_bytes = self._content_length
129
elif (self._content_length is not None
130
and num_bytes > self._content_length):
131
raise AssertionError(
132
'requested num_bytes (%d) > content length (%d)'
133
% (num_bytes, self._content_length))
134
# Expand the content if required
135
if self._content is None:
136
if self._content_chunks is not None:
137
self._content = ''.join(self._content_chunks)
138
self._content_chunks = None
139
if self._content is None:
140
# We join self._z_content_chunks here, because if we are
141
# decompressing, then it is *very* likely that we have a single
143
if self._z_content_chunks is None:
144
raise AssertionError('No content to decompress')
145
z_content = ''.join(self._z_content_chunks)
148
elif self._compressor_name == 'lzma':
149
# We don't do partial lzma decomp yet
151
self._content = pylzma.decompress(z_content)
152
elif self._compressor_name == 'zlib':
153
# Start a zlib decompressor
154
if num_bytes * 4 > self._content_length * 3:
155
# If we are requesting more that 3/4ths of the content,
156
# just extract the whole thing in a single pass
157
num_bytes = self._content_length
158
self._content = zlib.decompress(z_content)
160
self._z_content_decompressor = zlib.decompressobj()
161
# Seed the decompressor with the uncompressed bytes, so
162
# that the rest of the code is simplified
163
self._content = self._z_content_decompressor.decompress(
164
z_content, num_bytes + _ZLIB_DECOMP_WINDOW)
165
if not self._z_content_decompressor.unconsumed_tail:
166
self._z_content_decompressor = None
168
raise AssertionError('Unknown compressor: %r'
169
% self._compressor_name)
170
# Any bytes remaining to be decompressed will be in the decompressors
173
# Do we have enough bytes already?
174
if len(self._content) >= num_bytes:
176
# If we got this far, and don't have a decompressor, something is wrong
177
if self._z_content_decompressor is None:
178
raise AssertionError(
179
'No decompressor to decompress %d bytes' % num_bytes)
180
remaining_decomp = self._z_content_decompressor.unconsumed_tail
181
if not remaining_decomp:
182
raise AssertionError('Nothing left to decompress')
183
needed_bytes = num_bytes - len(self._content)
184
# We always set max_size to 32kB over the minimum needed, so that
185
# zlib will give us as much as we really want.
186
# TODO: If this isn't good enough, we could make a loop here,
187
# that keeps expanding the request until we get enough
188
self._content += self._z_content_decompressor.decompress(
189
remaining_decomp, needed_bytes + _ZLIB_DECOMP_WINDOW)
190
if len(self._content) < num_bytes:
191
raise AssertionError('%d bytes wanted, only %d available'
192
% (num_bytes, len(self._content)))
193
if not self._z_content_decompressor.unconsumed_tail:
194
# The stream is finished
195
self._z_content_decompressor = None
197
def _parse_bytes(self, bytes, pos):
198
"""Read the various lengths from the header.
200
This also populates the various 'compressed' buffers.
202
:return: The position in bytes just after the last newline
204
# At present, we have 2 integers for the compressed and uncompressed
205
# content. In base10 (ascii) 14 bytes can represent > 1TB, so to avoid
206
# checking too far, cap the search to 14 bytes.
207
pos2 = bytes.index('\n', pos, pos + 14)
208
self._z_content_length = int(bytes[pos:pos2])
210
pos2 = bytes.index('\n', pos, pos + 14)
211
self._content_length = int(bytes[pos:pos2])
213
if len(bytes) != (pos + self._z_content_length):
214
# XXX: Define some GCCorrupt error ?
215
raise AssertionError('Invalid bytes: (%d) != %d + %d' %
216
(len(bytes), pos, self._z_content_length))
217
self._z_content_chunks = (bytes[pos:],)
220
def _z_content(self):
221
"""Return z_content_chunks as a simple string.
223
Meant only to be used by the test suite.
225
if self._z_content_chunks is not None:
226
return ''.join(self._z_content_chunks)
230
def from_bytes(cls, bytes):
232
if bytes[:6] not in cls.GCB_KNOWN_HEADERS:
233
raise ValueError('bytes did not start with any of %r'
234
% (cls.GCB_KNOWN_HEADERS,))
235
# XXX: why not testing the whole header ?
237
out._compressor_name = 'zlib'
238
elif bytes[4] == 'l':
239
out._compressor_name = 'lzma'
241
raise ValueError('unknown compressor: %r' % (bytes,))
242
out._parse_bytes(bytes, 6)
245
def extract(self, key, start, end, sha1=None):
246
"""Extract the text for a specific key.
248
:param key: The label used for this content
249
:param sha1: TODO (should we validate only when sha1 is supplied?)
250
:return: The bytes for the content
252
if start == end == 0:
254
self._ensure_content(end)
255
# The bytes are 'f' or 'd' for the type, then a variable-length
256
# base128 integer for the content size, then the actual content
257
# We know that the variable-length integer won't be longer than 5
258
# bytes (it takes 5 bytes to encode 2^32)
259
c = self._content[start]
264
raise ValueError('Unknown content control code: %s'
267
content_len, len_len = decode_base128_int(
268
self._content[start + 1:start + 6])
269
content_start = start + 1 + len_len
270
if end != content_start + content_len:
271
raise ValueError('end != len according to field header'
272
' %s != %s' % (end, content_start + content_len))
274
bytes = self._content[content_start:end]
276
bytes = apply_delta_to_source(self._content, content_start, end)
279
def set_chunked_content(self, content_chunks, length):
280
"""Set the content of this block to the given chunks."""
281
# If we have lots of short lines, it is may be more efficient to join
282
# the content ahead of time. If the content is <10MiB, we don't really
283
# care about the extra memory consumption, so we can just pack it and
284
# be done. However, timing showed 18s => 17.9s for repacking 1k revs of
285
# mysql, which is below the noise margin
286
self._content_length = length
287
self._content_chunks = content_chunks
289
self._z_content_chunks = None
291
def set_content(self, content):
292
"""Set the content of this block."""
293
self._content_length = len(content)
294
self._content = content
295
self._z_content_chunks = None
297
def _create_z_content_from_chunks(self, chunks):
298
compressor = zlib.compressobj(zlib.Z_DEFAULT_COMPRESSION)
299
# Peak in this point is 1 fulltext, 1 compressed text, + zlib overhead
300
# (measured peak is maybe 30MB over the above...)
301
compressed_chunks = map(compressor.compress, chunks)
302
compressed_chunks.append(compressor.flush())
303
# Ignore empty chunks
304
self._z_content_chunks = [c for c in compressed_chunks if c]
305
self._z_content_length = sum(map(len, self._z_content_chunks))
307
def _create_z_content(self):
308
if self._z_content_chunks is not None:
310
if self._content_chunks is not None:
311
chunks = self._content_chunks
313
chunks = (self._content,)
314
self._create_z_content_from_chunks(chunks)
317
"""Create the byte stream as a series of 'chunks'"""
318
self._create_z_content()
319
header = self.GCB_HEADER
320
chunks = ['%s%d\n%d\n'
321
% (header, self._z_content_length, self._content_length),
323
chunks.extend(self._z_content_chunks)
324
total_len = sum(map(len, chunks))
325
return total_len, chunks
328
"""Encode the information into a byte stream."""
329
total_len, chunks = self.to_chunks()
330
return ''.join(chunks)
332
def _dump(self, include_text=False):
333
"""Take this block, and spit out a human-readable structure.
335
:param include_text: Inserts also include text bits, chose whether you
336
want this displayed in the dump or not.
337
:return: A dump of the given block. The layout is something like:
338
[('f', length), ('d', delta_length, text_length, [delta_info])]
339
delta_info := [('i', num_bytes, text), ('c', offset, num_bytes),
342
self._ensure_content()
345
while pos < self._content_length:
346
kind = self._content[pos]
348
if kind not in ('f', 'd'):
349
raise ValueError('invalid kind character: %r' % (kind,))
350
content_len, len_len = decode_base128_int(
351
self._content[pos:pos + 5])
353
if content_len + pos > self._content_length:
354
raise ValueError('invalid content_len %d for record @ pos %d'
355
% (content_len, pos - len_len - 1))
356
if kind == 'f': # Fulltext
358
text = self._content[pos:pos+content_len]
359
result.append(('f', content_len, text))
361
result.append(('f', content_len))
362
elif kind == 'd': # Delta
363
delta_content = self._content[pos:pos+content_len]
365
# The first entry in a delta is the decompressed length
366
decomp_len, delta_pos = decode_base128_int(delta_content)
367
result.append(('d', content_len, decomp_len, delta_info))
369
while delta_pos < content_len:
370
c = ord(delta_content[delta_pos])
374
delta_pos) = decode_copy_instruction(delta_content, c,
377
text = self._content[offset:offset+length]
378
delta_info.append(('c', offset, length, text))
380
delta_info.append(('c', offset, length))
381
measured_len += length
384
txt = delta_content[delta_pos:delta_pos+c]
387
delta_info.append(('i', c, txt))
390
if delta_pos != content_len:
391
raise ValueError('Delta consumed a bad number of bytes:'
392
' %d != %d' % (delta_pos, content_len))
393
if measured_len != decomp_len:
394
raise ValueError('Delta claimed fulltext was %d bytes, but'
395
' extraction resulted in %d bytes'
396
% (decomp_len, measured_len))
401
class _LazyGroupCompressFactory(object):
402
"""Yield content from a GroupCompressBlock on demand."""
404
def __init__(self, key, parents, manager, start, end, first):
405
"""Create a _LazyGroupCompressFactory
407
:param key: The key of just this record
408
:param parents: The parents of this key (possibly None)
409
:param gc_block: A GroupCompressBlock object
410
:param start: Offset of the first byte for this record in the
412
:param end: Offset of the byte just after the end of this record
413
(ie, bytes = content[start:end])
414
:param first: Is this the first Factory for the given block?
417
self.parents = parents
419
# Note: This attribute coupled with Manager._factories creates a
420
# reference cycle. Perhaps we would rather use a weakref(), or
421
# find an appropriate time to release the ref. After the first
422
# get_bytes_as call? After Manager.get_record_stream() returns
424
self._manager = manager
426
self.storage_kind = 'groupcompress-block'
428
self.storage_kind = 'groupcompress-block-ref'
434
return '%s(%s, first=%s)' % (self.__class__.__name__,
435
self.key, self._first)
437
def get_bytes_as(self, storage_kind):
438
if storage_kind == self.storage_kind:
440
# wire bytes, something...
441
return self._manager._wire_bytes()
444
if storage_kind in ('fulltext', 'chunked'):
445
if self._bytes is None:
446
# Grab and cache the raw bytes for this entry
447
# and break the ref-cycle with _manager since we don't need it
450
self._manager._prepare_for_extract()
451
except zlib.error as value:
452
raise errors.DecompressCorruption("zlib: " + str(value))
453
block = self._manager._block
454
self._bytes = block.extract(self.key, self._start, self._end)
455
# There are code paths that first extract as fulltext, and then
456
# extract as storage_kind (smart fetch). So we don't break the
457
# refcycle here, but instead in manager.get_record_stream()
458
if storage_kind == 'fulltext':
462
raise errors.UnavailableRepresentation(self.key, storage_kind,
466
class _LazyGroupContentManager(object):
467
"""This manages a group of _LazyGroupCompressFactory objects."""
469
_max_cut_fraction = 0.75 # We allow a block to be trimmed to 75% of
470
# current size, and still be considered
472
_full_block_size = 4*1024*1024
473
_full_mixed_block_size = 2*1024*1024
474
_full_enough_block_size = 3*1024*1024 # size at which we won't repack
475
_full_enough_mixed_block_size = 2*768*1024 # 1.5MB
477
def __init__(self, block, get_compressor_settings=None):
479
# We need to preserve the ordering
482
self._get_settings = get_compressor_settings
483
self._compressor_settings = None
485
def _get_compressor_settings(self):
486
if self._compressor_settings is not None:
487
return self._compressor_settings
489
if self._get_settings is not None:
490
settings = self._get_settings()
492
vf = GroupCompressVersionedFiles
493
settings = vf._DEFAULT_COMPRESSOR_SETTINGS
494
self._compressor_settings = settings
495
return self._compressor_settings
497
def add_factory(self, key, parents, start, end):
498
if not self._factories:
502
# Note that this creates a reference cycle....
503
factory = _LazyGroupCompressFactory(key, parents, self,
504
start, end, first=first)
505
# max() works here, but as a function call, doing a compare seems to be
506
# significantly faster, timeit says 250ms for max() and 100ms for the
508
if end > self._last_byte:
509
self._last_byte = end
510
self._factories.append(factory)
512
def get_record_stream(self):
513
"""Get a record for all keys added so far."""
514
for factory in self._factories:
516
# Break the ref-cycle
517
factory._bytes = None
518
factory._manager = None
519
# TODO: Consider setting self._factories = None after the above loop,
520
# as it will break the reference cycle
522
def _trim_block(self, last_byte):
523
"""Create a new GroupCompressBlock, with just some of the content."""
524
# None of the factories need to be adjusted, because the content is
525
# located in an identical place. Just that some of the unreferenced
526
# trailing bytes are stripped
527
trace.mutter('stripping trailing bytes from groupcompress block'
528
' %d => %d', self._block._content_length, last_byte)
529
new_block = GroupCompressBlock()
530
self._block._ensure_content(last_byte)
531
new_block.set_content(self._block._content[:last_byte])
532
self._block = new_block
534
def _make_group_compressor(self):
535
return GroupCompressor(self._get_compressor_settings())
537
def _rebuild_block(self):
538
"""Create a new GroupCompressBlock with only the referenced texts."""
539
compressor = self._make_group_compressor()
541
old_length = self._block._content_length
543
for factory in self._factories:
544
bytes = factory.get_bytes_as('fulltext')
545
(found_sha1, start_point, end_point,
546
type) = compressor.compress(factory.key, bytes, factory.sha1)
547
# Now update this factory with the new offsets, etc
548
factory.sha1 = found_sha1
549
factory._start = start_point
550
factory._end = end_point
551
self._last_byte = end_point
552
new_block = compressor.flush()
553
# TODO: Should we check that new_block really *is* smaller than the old
554
# block? It seems hard to come up with a method that it would
555
# expand, since we do full compression again. Perhaps based on a
556
# request that ends up poorly ordered?
557
# TODO: If the content would have expanded, then we would want to
558
# handle a case where we need to split the block.
559
# Now that we have a user-tweakable option
560
# (max_bytes_to_index), it is possible that one person set it
561
# to a very low value, causing poor compression.
562
delta = time.time() - tstart
563
self._block = new_block
564
trace.mutter('creating new compressed block on-the-fly in %.3fs'
565
' %d bytes => %d bytes', delta, old_length,
566
self._block._content_length)
568
def _prepare_for_extract(self):
569
"""A _LazyGroupCompressFactory is about to extract to fulltext."""
570
# We expect that if one child is going to fulltext, all will be. This
571
# helps prevent all of them from extracting a small amount at a time.
572
# Which in itself isn't terribly expensive, but resizing 2MB 32kB at a
573
# time (self._block._content) is a little expensive.
574
self._block._ensure_content(self._last_byte)
576
def _check_rebuild_action(self):
577
"""Check to see if our block should be repacked."""
580
for factory in self._factories:
581
total_bytes_used += factory._end - factory._start
582
if last_byte_used < factory._end:
583
last_byte_used = factory._end
584
# If we are using more than half of the bytes from the block, we have
585
# nothing else to check
586
if total_bytes_used * 2 >= self._block._content_length:
587
return None, last_byte_used, total_bytes_used
588
# We are using less than 50% of the content. Is the content we are
589
# using at the beginning of the block? If so, we can just trim the
590
# tail, rather than rebuilding from scratch.
591
if total_bytes_used * 2 > last_byte_used:
592
return 'trim', last_byte_used, total_bytes_used
594
# We are using a small amount of the data, and it isn't just packed
595
# nicely at the front, so rebuild the content.
596
# Note: This would be *nicer* as a strip-data-from-group, rather than
597
# building it up again from scratch
598
# It might be reasonable to consider the fulltext sizes for
599
# different bits when deciding this, too. As you may have a small
600
# fulltext, and a trivial delta, and you are just trading around
601
# for another fulltext. If we do a simple 'prune' you may end up
602
# expanding many deltas into fulltexts, as well.
603
# If we build a cheap enough 'strip', then we could try a strip,
604
# if that expands the content, we then rebuild.
605
return 'rebuild', last_byte_used, total_bytes_used
607
def check_is_well_utilized(self):
608
"""Is the current block considered 'well utilized'?
610
This heuristic asks if the current block considers itself to be a fully
611
developed group, rather than just a loose collection of data.
613
if len(self._factories) == 1:
614
# A block of length 1 could be improved by combining with other
615
# groups - don't look deeper. Even larger than max size groups
616
# could compress well with adjacent versions of the same thing.
618
action, last_byte_used, total_bytes_used = self._check_rebuild_action()
619
block_size = self._block._content_length
620
if total_bytes_used < block_size * self._max_cut_fraction:
621
# This block wants to trim itself small enough that we want to
622
# consider it under-utilized.
624
# TODO: This code is meant to be the twin of _insert_record_stream's
625
# 'start_new_block' logic. It would probably be better to factor
626
# out that logic into a shared location, so that it stays
628
# We currently assume a block is properly utilized whenever it is >75%
629
# of the size of a 'full' block. In normal operation, a block is
630
# considered full when it hits 4MB of same-file content. So any block
631
# >3MB is 'full enough'.
632
# The only time this isn't true is when a given block has large-object
633
# content. (a single file >4MB, etc.)
634
# Under these circumstances, we allow a block to grow to
635
# 2 x largest_content. Which means that if a given block had a large
636
# object, it may actually be under-utilized. However, given that this
637
# is 'pack-on-the-fly' it is probably reasonable to not repack large
638
# content blobs on-the-fly. Note that because we return False for all
639
# 1-item blobs, we will repack them; we may wish to reevaluate our
640
# treatment of large object blobs in the future.
641
if block_size >= self._full_enough_block_size:
643
# If a block is <3MB, it still may be considered 'full' if it contains
644
# mixed content. The current rule is 2MB of mixed content is considered
645
# full. So check to see if this block contains mixed content, and
646
# set the threshold appropriately.
648
for factory in self._factories:
649
prefix = factory.key[:-1]
650
if common_prefix is None:
651
common_prefix = prefix
652
elif prefix != common_prefix:
653
# Mixed content, check the size appropriately
654
if block_size >= self._full_enough_mixed_block_size:
657
# The content failed both the mixed check and the single-content check
658
# so obviously it is not fully utilized
659
# TODO: there is one other constraint that isn't being checked
660
# namely, that the entries in the block are in the appropriate
661
# order. For example, you could insert the entries in exactly
662
# reverse groupcompress order, and we would think that is ok.
663
# (all the right objects are in one group, and it is fully
664
# utilized, etc.) For now, we assume that case is rare,
665
# especially since we should always fetch in 'groupcompress'
669
def _check_rebuild_block(self):
670
action, last_byte_used, total_bytes_used = self._check_rebuild_action()
674
self._trim_block(last_byte_used)
675
elif action == 'rebuild':
676
self._rebuild_block()
678
raise ValueError('unknown rebuild action: %r' % (action,))
680
def _wire_bytes(self):
681
"""Return a byte stream suitable for transmitting over the wire."""
682
self._check_rebuild_block()
683
# The outer block starts with:
684
# 'groupcompress-block\n'
685
# <length of compressed key info>\n
686
# <length of uncompressed info>\n
687
# <length of gc block>\n
690
lines = ['groupcompress-block\n']
691
# The minimal info we need is the key, the start offset, and the
692
# parents. The length and type are encoded in the record itself.
693
# However, passing in the other bits makes it easier. The list of
694
# keys, and the start offset, the length
696
# 1 line with parents, '' for ()
697
# 1 line for start offset
698
# 1 line for end byte
700
for factory in self._factories:
701
key_bytes = '\x00'.join(factory.key)
702
parents = factory.parents
704
parent_bytes = 'None:'
706
parent_bytes = '\t'.join('\x00'.join(key) for key in parents)
707
record_header = '%s\n%s\n%d\n%d\n' % (
708
key_bytes, parent_bytes, factory._start, factory._end)
709
header_lines.append(record_header)
710
# TODO: Can we break the refcycle at this point and set
711
# factory._manager = None?
712
header_bytes = ''.join(header_lines)
714
header_bytes_len = len(header_bytes)
715
z_header_bytes = zlib.compress(header_bytes)
717
z_header_bytes_len = len(z_header_bytes)
718
block_bytes_len, block_chunks = self._block.to_chunks()
719
lines.append('%d\n%d\n%d\n' % (z_header_bytes_len, header_bytes_len,
721
lines.append(z_header_bytes)
722
lines.extend(block_chunks)
723
del z_header_bytes, block_chunks
724
# TODO: This is a point where we will double the memory consumption. To
725
# avoid this, we probably have to switch to a 'chunked' api
726
return ''.join(lines)
729
def from_bytes(cls, bytes):
730
# TODO: This does extra string copying, probably better to do it a
731
# different way. At a minimum this creates 2 copies of the
733
(storage_kind, z_header_len, header_len,
734
block_len, rest) = bytes.split('\n', 4)
736
if storage_kind != 'groupcompress-block':
737
raise ValueError('Unknown storage kind: %s' % (storage_kind,))
738
z_header_len = int(z_header_len)
739
if len(rest) < z_header_len:
740
raise ValueError('Compressed header len shorter than all bytes')
741
z_header = rest[:z_header_len]
742
header_len = int(header_len)
743
header = zlib.decompress(z_header)
744
if len(header) != header_len:
745
raise ValueError('invalid length for decompressed bytes')
747
block_len = int(block_len)
748
if len(rest) != z_header_len + block_len:
749
raise ValueError('Invalid length for block')
750
block_bytes = rest[z_header_len:]
752
# So now we have a valid GCB, we just need to parse the factories that
754
header_lines = header.split('\n')
756
last = header_lines.pop()
758
raise ValueError('header lines did not end with a trailing'
760
if len(header_lines) % 4 != 0:
761
raise ValueError('The header was not an even multiple of 4 lines')
762
block = GroupCompressBlock.from_bytes(block_bytes)
765
for start in xrange(0, len(header_lines), 4):
767
key = tuple(header_lines[start].split('\x00'))
768
parents_line = header_lines[start+1]
769
if parents_line == 'None:':
772
parents = tuple([tuple(segment.split('\x00'))
773
for segment in parents_line.split('\t')
775
start_offset = int(header_lines[start+2])
776
end_offset = int(header_lines[start+3])
777
result.add_factory(key, parents, start_offset, end_offset)
781
def network_block_to_records(storage_kind, bytes, line_end):
782
if storage_kind != 'groupcompress-block':
783
raise ValueError('Unknown storage kind: %s' % (storage_kind,))
784
manager = _LazyGroupContentManager.from_bytes(bytes)
785
return manager.get_record_stream()
788
class _CommonGroupCompressor(object):
790
def __init__(self, settings=None):
791
"""Create a GroupCompressor."""
796
self.labels_deltas = {}
797
self._delta_index = None # Set by the children
798
self._block = GroupCompressBlock()
802
self._settings = settings
804
def compress(self, key, bytes, expected_sha, nostore_sha=None, soft=False):
805
"""Compress lines with label key.
807
:param key: A key tuple. It is stored in the output
808
for identification of the text during decompression. If the last
809
element is 'None' it is replaced with the sha1 of the text -
811
:param bytes: The bytes to be compressed
812
:param expected_sha: If non-None, the sha the lines are believed to
813
have. During compression the sha is calculated; a mismatch will
815
:param nostore_sha: If the computed sha1 sum matches, we will raise
816
ExistingContent rather than adding the text.
817
:param soft: Do a 'soft' compression. This means that we require larger
818
ranges to match to be considered for a copy command.
820
:return: The sha1 of lines, the start and end offsets in the delta, and
821
the type ('fulltext' or 'delta').
823
:seealso VersionedFiles.add_lines:
825
if not bytes: # empty, like a dir entry, etc
826
if nostore_sha == _null_sha1:
827
raise errors.ExistingContent()
828
return _null_sha1, 0, 0, 'fulltext'
829
# we assume someone knew what they were doing when they passed it in
830
if expected_sha is not None:
833
sha1 = osutils.sha_string(bytes)
834
if nostore_sha is not None:
835
if sha1 == nostore_sha:
836
raise errors.ExistingContent()
838
key = key[:-1] + ('sha1:' + sha1,)
840
start, end, type = self._compress(key, bytes, len(bytes) / 2, soft)
841
return sha1, start, end, type
843
def _compress(self, key, bytes, max_delta_size, soft=False):
844
"""Compress lines with label key.
846
:param key: A key tuple. It is stored in the output for identification
847
of the text during decompression.
849
:param bytes: The bytes to be compressed
851
:param max_delta_size: The size above which we issue a fulltext instead
854
:param soft: Do a 'soft' compression. This means that we require larger
855
ranges to match to be considered for a copy command.
857
:return: The sha1 of lines, the start and end offsets in the delta, and
858
the type ('fulltext' or 'delta').
860
raise NotImplementedError(self._compress)
862
def extract(self, key):
863
"""Extract a key previously added to the compressor.
865
:param key: The key to extract.
866
:return: An iterable over bytes and the sha1.
868
(start_byte, start_chunk, end_byte, end_chunk) = self.labels_deltas[key]
869
delta_chunks = self.chunks[start_chunk:end_chunk]
870
stored_bytes = ''.join(delta_chunks)
871
if stored_bytes[0] == 'f':
872
fulltext_len, offset = decode_base128_int(stored_bytes[1:10])
873
data_len = fulltext_len + 1 + offset
874
if data_len != len(stored_bytes):
875
raise ValueError('Index claimed fulltext len, but stored bytes'
877
% (len(stored_bytes), data_len))
878
bytes = stored_bytes[offset + 1:]
880
# XXX: This is inefficient at best
881
source = ''.join(self.chunks[:start_chunk])
882
if stored_bytes[0] != 'd':
883
raise ValueError('Unknown content kind, bytes claim %s'
884
% (stored_bytes[0],))
885
delta_len, offset = decode_base128_int(stored_bytes[1:10])
886
data_len = delta_len + 1 + offset
887
if data_len != len(stored_bytes):
888
raise ValueError('Index claimed delta len, but stored bytes'
890
% (len(stored_bytes), data_len))
891
bytes = apply_delta(source, stored_bytes[offset + 1:])
892
bytes_sha1 = osutils.sha_string(bytes)
893
return bytes, bytes_sha1
896
"""Finish this group, creating a formatted stream.
898
After calling this, the compressor should no longer be used
900
self._block.set_chunked_content(self.chunks, self.endpoint)
902
self._delta_index = None
906
"""Call this if you want to 'revoke' the last compression.
908
After this, the data structures will be rolled back, but you cannot do
911
self._delta_index = None
912
del self.chunks[self._last[0]:]
913
self.endpoint = self._last[1]
917
"""Return the overall compression ratio."""
918
return float(self.input_bytes) / float(self.endpoint)
921
class PythonGroupCompressor(_CommonGroupCompressor):
923
def __init__(self, settings=None):
924
"""Create a GroupCompressor.
926
Used only if the pyrex version is not available.
928
super(PythonGroupCompressor, self).__init__(settings)
929
self._delta_index = LinesDeltaIndex([])
930
# The actual content is managed by LinesDeltaIndex
931
self.chunks = self._delta_index.lines
933
def _compress(self, key, bytes, max_delta_size, soft=False):
934
"""see _CommonGroupCompressor._compress"""
935
input_len = len(bytes)
936
new_lines = osutils.split_lines(bytes)
937
out_lines, index_lines = self._delta_index.make_delta(
938
new_lines, bytes_length=input_len, soft=soft)
939
delta_length = sum(map(len, out_lines))
940
if delta_length > max_delta_size:
941
# The delta is longer than the fulltext, insert a fulltext
943
out_lines = ['f', encode_base128_int(input_len)]
944
out_lines.extend(new_lines)
945
index_lines = [False, False]
946
index_lines.extend([True] * len(new_lines))
948
# this is a worthy delta, output it
951
# Update the delta_length to include those two encoded integers
952
out_lines[1] = encode_base128_int(delta_length)
954
start = self.endpoint
955
chunk_start = len(self.chunks)
956
self._last = (chunk_start, self.endpoint)
957
self._delta_index.extend_lines(out_lines, index_lines)
958
self.endpoint = self._delta_index.endpoint
959
self.input_bytes += input_len
960
chunk_end = len(self.chunks)
961
self.labels_deltas[key] = (start, chunk_start,
962
self.endpoint, chunk_end)
963
return start, self.endpoint, type
966
class PyrexGroupCompressor(_CommonGroupCompressor):
967
"""Produce a serialised group of compressed texts.
969
It contains code very similar to SequenceMatcher because of having a similar
970
task. However some key differences apply:
972
* there is no junk, we want a minimal edit not a human readable diff.
973
* we don't filter very common lines (because we don't know where a good
974
range will start, and after the first text we want to be emitting minmal
976
* we chain the left side, not the right side
977
* we incrementally update the adjacency matrix as new lines are provided.
978
* we look for matches in all of the left side, so the routine which does
979
the analagous task of find_longest_match does not need to filter on the
983
def __init__(self, settings=None):
984
super(PyrexGroupCompressor, self).__init__(settings)
985
max_bytes_to_index = self._settings.get('max_bytes_to_index', 0)
986
self._delta_index = DeltaIndex(max_bytes_to_index=max_bytes_to_index)
988
def _compress(self, key, bytes, max_delta_size, soft=False):
989
"""see _CommonGroupCompressor._compress"""
990
input_len = len(bytes)
991
# By having action/label/sha1/len, we can parse the group if the index
992
# was ever destroyed, we have the key in 'label', we know the final
993
# bytes are valid from sha1, and we know where to find the end of this
994
# record because of 'len'. (the delta record itself will store the
995
# total length for the expanded record)
996
# 'len: %d\n' costs approximately 1% increase in total data
997
# Having the labels at all costs us 9-10% increase, 38% increase for
998
# inventory pages, and 5.8% increase for text pages
999
# new_chunks = ['label:%s\nsha1:%s\n' % (label, sha1)]
1000
if self._delta_index._source_offset != self.endpoint:
1001
raise AssertionError('_source_offset != endpoint'
1002
' somehow the DeltaIndex got out of sync with'
1003
' the output lines')
1004
delta = self._delta_index.make_delta(bytes, max_delta_size)
1007
enc_length = encode_base128_int(len(bytes))
1008
len_mini_header = 1 + len(enc_length)
1009
self._delta_index.add_source(bytes, len_mini_header)
1010
new_chunks = ['f', enc_length, bytes]
1013
enc_length = encode_base128_int(len(delta))
1014
len_mini_header = 1 + len(enc_length)
1015
new_chunks = ['d', enc_length, delta]
1016
self._delta_index.add_delta_source(delta, len_mini_header)
1018
start = self.endpoint
1019
chunk_start = len(self.chunks)
1020
# Now output these bytes
1021
self._output_chunks(new_chunks)
1022
self.input_bytes += input_len
1023
chunk_end = len(self.chunks)
1024
self.labels_deltas[key] = (start, chunk_start,
1025
self.endpoint, chunk_end)
1026
if not self._delta_index._source_offset == self.endpoint:
1027
raise AssertionError('the delta index is out of sync'
1028
'with the output lines %s != %s'
1029
% (self._delta_index._source_offset, self.endpoint))
1030
return start, self.endpoint, type
1032
def _output_chunks(self, new_chunks):
1033
"""Output some chunks.
1035
:param new_chunks: The chunks to output.
1037
self._last = (len(self.chunks), self.endpoint)
1038
endpoint = self.endpoint
1039
self.chunks.extend(new_chunks)
1040
endpoint += sum(map(len, new_chunks))
1041
self.endpoint = endpoint
1044
def make_pack_factory(graph, delta, keylength, inconsistency_fatal=True):
1045
"""Create a factory for creating a pack based groupcompress.
1047
This is only functional enough to run interface tests, it doesn't try to
1048
provide a full pack environment.
1050
:param graph: Store a graph.
1051
:param delta: Delta compress contents.
1052
:param keylength: How long should keys be.
1054
def factory(transport):
1059
graph_index = BTreeBuilder(reference_lists=ref_length,
1060
key_elements=keylength)
1061
stream = transport.open_write_stream('newpack')
1062
writer = pack.ContainerWriter(stream.write)
1064
index = _GCGraphIndex(graph_index, lambda:True, parents=parents,
1065
add_callback=graph_index.add_nodes,
1066
inconsistency_fatal=inconsistency_fatal)
1067
access = pack_repo._DirectPackAccess({})
1068
access.set_writer(writer, graph_index, (transport, 'newpack'))
1069
result = GroupCompressVersionedFiles(index, access, delta)
1070
result.stream = stream
1071
result.writer = writer
1076
def cleanup_pack_group(versioned_files):
1077
versioned_files.writer.end()
1078
versioned_files.stream.close()
1081
class _BatchingBlockFetcher(object):
1082
"""Fetch group compress blocks in batches.
1084
:ivar total_bytes: int of expected number of bytes needed to fetch the
1085
currently pending batch.
1088
def __init__(self, gcvf, locations, get_compressor_settings=None):
1090
self.locations = locations
1092
self.batch_memos = {}
1093
self.memos_to_get = []
1094
self.total_bytes = 0
1095
self.last_read_memo = None
1097
self._get_compressor_settings = get_compressor_settings
1099
def add_key(self, key):
1100
"""Add another to key to fetch.
1102
:return: The estimated number of bytes needed to fetch the batch so
1105
self.keys.append(key)
1106
index_memo, _, _, _ = self.locations[key]
1107
read_memo = index_memo[0:3]
1108
# Three possibilities for this read_memo:
1109
# - it's already part of this batch; or
1110
# - it's not yet part of this batch, but is already cached; or
1111
# - it's not yet part of this batch and will need to be fetched.
1112
if read_memo in self.batch_memos:
1113
# This read memo is already in this batch.
1114
return self.total_bytes
1116
cached_block = self.gcvf._group_cache[read_memo]
1118
# This read memo is new to this batch, and the data isn't cached
1120
self.batch_memos[read_memo] = None
1121
self.memos_to_get.append(read_memo)
1122
byte_length = read_memo[2]
1123
self.total_bytes += byte_length
1125
# This read memo is new to this batch, but cached.
1126
# Keep a reference to the cached block in batch_memos because it's
1127
# certain that we'll use it when this batch is processed, but
1128
# there's a risk that it would fall out of _group_cache between now
1130
self.batch_memos[read_memo] = cached_block
1131
return self.total_bytes
1133
def _flush_manager(self):
1134
if self.manager is not None:
1135
for factory in self.manager.get_record_stream():
1138
self.last_read_memo = None
1140
def yield_factories(self, full_flush=False):
1141
"""Yield factories for keys added since the last yield. They will be
1142
returned in the order they were added via add_key.
1144
:param full_flush: by default, some results may not be returned in case
1145
they can be part of the next batch. If full_flush is True, then
1146
all results are returned.
1148
if self.manager is None and not self.keys:
1150
# Fetch all memos in this batch.
1151
blocks = self.gcvf._get_blocks(self.memos_to_get)
1152
# Turn blocks into factories and yield them.
1153
memos_to_get_stack = list(self.memos_to_get)
1154
memos_to_get_stack.reverse()
1155
for key in self.keys:
1156
index_memo, _, parents, _ = self.locations[key]
1157
read_memo = index_memo[:3]
1158
if self.last_read_memo != read_memo:
1159
# We are starting a new block. If we have a
1160
# manager, we have found everything that fits for
1161
# now, so yield records
1162
for factory in self._flush_manager():
1164
# Now start a new manager.
1165
if memos_to_get_stack and memos_to_get_stack[-1] == read_memo:
1166
# The next block from _get_blocks will be the block we
1168
block_read_memo, block = blocks.next()
1169
if block_read_memo != read_memo:
1170
raise AssertionError(
1171
"block_read_memo out of sync with read_memo"
1172
"(%r != %r)" % (block_read_memo, read_memo))
1173
self.batch_memos[read_memo] = block
1174
memos_to_get_stack.pop()
1176
block = self.batch_memos[read_memo]
1177
self.manager = _LazyGroupContentManager(block,
1178
get_compressor_settings=self._get_compressor_settings)
1179
self.last_read_memo = read_memo
1180
start, end = index_memo[3:5]
1181
self.manager.add_factory(key, parents, start, end)
1183
for factory in self._flush_manager():
1186
self.batch_memos.clear()
1187
del self.memos_to_get[:]
1188
self.total_bytes = 0
1191
class GroupCompressVersionedFiles(VersionedFilesWithFallbacks):
1192
"""A group-compress based VersionedFiles implementation."""
1194
# This controls how the GroupCompress DeltaIndex works. Basically, we
1195
# compute hash pointers into the source blocks (so hash(text) => text).
1196
# However each of these references costs some memory in trade against a
1197
# more accurate match result. For very large files, they either are
1198
# pre-compressed and change in bulk whenever they change, or change in just
1199
# local blocks. Either way, 'improved resolution' is not very helpful,
1200
# versus running out of memory trying to track everything. The default max
1201
# gives 100% sampling of a 1MB file.
1202
_DEFAULT_MAX_BYTES_TO_INDEX = 1024 * 1024
1203
_DEFAULT_COMPRESSOR_SETTINGS = {'max_bytes_to_index':
1204
_DEFAULT_MAX_BYTES_TO_INDEX}
1206
def __init__(self, index, access, delta=True, _unadded_refs=None,
1208
"""Create a GroupCompressVersionedFiles object.
1210
:param index: The index object storing access and graph data.
1211
:param access: The access object storing raw data.
1212
:param delta: Whether to delta compress or just entropy compress.
1213
:param _unadded_refs: private parameter, don't use.
1214
:param _group_cache: private parameter, don't use.
1217
self._access = access
1219
if _unadded_refs is None:
1221
self._unadded_refs = _unadded_refs
1222
if _group_cache is None:
1223
_group_cache = LRUSizeCache(max_size=50*1024*1024)
1224
self._group_cache = _group_cache
1225
self._immediate_fallback_vfs = []
1226
self._max_bytes_to_index = None
1228
def without_fallbacks(self):
1229
"""Return a clone of this object without any fallbacks configured."""
1230
return GroupCompressVersionedFiles(self._index, self._access,
1231
self._delta, _unadded_refs=dict(self._unadded_refs),
1232
_group_cache=self._group_cache)
1234
def add_lines(self, key, parents, lines, parent_texts=None,
1235
left_matching_blocks=None, nostore_sha=None, random_id=False,
1236
check_content=True):
1237
"""Add a text to the store.
1239
:param key: The key tuple of the text to add.
1240
:param parents: The parents key tuples of the text to add.
1241
:param lines: A list of lines. Each line must be a bytestring. And all
1242
of them except the last must be terminated with \\n and contain no
1243
other \\n's. The last line may either contain no \\n's or a single
1244
terminating \\n. If the lines list does meet this constraint the
1245
add routine may error or may succeed - but you will be unable to
1246
read the data back accurately. (Checking the lines have been split
1247
correctly is expensive and extremely unlikely to catch bugs so it
1248
is not done at runtime unless check_content is True.)
1249
:param parent_texts: An optional dictionary containing the opaque
1250
representations of some or all of the parents of version_id to
1251
allow delta optimisations. VERY IMPORTANT: the texts must be those
1252
returned by add_lines or data corruption can be caused.
1253
:param left_matching_blocks: a hint about which areas are common
1254
between the text and its left-hand-parent. The format is
1255
the SequenceMatcher.get_matching_blocks format.
1256
:param nostore_sha: Raise ExistingContent and do not add the lines to
1257
the versioned file if the digest of the lines matches this.
1258
:param random_id: If True a random id has been selected rather than
1259
an id determined by some deterministic process such as a converter
1260
from a foreign VCS. When True the backend may choose not to check
1261
for uniqueness of the resulting key within the versioned file, so
1262
this should only be done when the result is expected to be unique
1264
:param check_content: If True, the lines supplied are verified to be
1265
bytestrings that are correctly formed lines.
1266
:return: The text sha1, the number of bytes in the text, and an opaque
1267
representation of the inserted version which can be provided
1268
back to future add_lines calls in the parent_texts dictionary.
1270
self._index._check_write_ok()
1271
self._check_add(key, lines, random_id, check_content)
1273
# The caller might pass None if there is no graph data, but kndx
1274
# indexes can't directly store that, so we give them
1275
# an empty tuple instead.
1277
# double handling for now. Make it work until then.
1278
length = sum(map(len, lines))
1279
record = ChunkedContentFactory(key, parents, None, lines)
1280
sha1 = list(self._insert_record_stream([record], random_id=random_id,
1281
nostore_sha=nostore_sha))[0]
1282
return sha1, length, None
1284
def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
1285
"""See VersionedFiles._add_text()."""
1286
self._index._check_write_ok()
1287
self._check_add(key, None, random_id, check_content=False)
1288
if text.__class__ is not str:
1289
raise errors.BzrBadParameterUnicode("text")
1291
# The caller might pass None if there is no graph data, but kndx
1292
# indexes can't directly store that, so we give them
1293
# an empty tuple instead.
1295
# double handling for now. Make it work until then.
1297
record = FulltextContentFactory(key, parents, None, text)
1298
sha1 = list(self._insert_record_stream([record], random_id=random_id,
1299
nostore_sha=nostore_sha))[0]
1300
return sha1, length, None
1302
def add_fallback_versioned_files(self, a_versioned_files):
1303
"""Add a source of texts for texts not present in this knit.
1305
:param a_versioned_files: A VersionedFiles object.
1307
self._immediate_fallback_vfs.append(a_versioned_files)
1309
def annotate(self, key):
1310
"""See VersionedFiles.annotate."""
1311
ann = annotate.Annotator(self)
1312
return ann.annotate_flat(key)
1314
def get_annotator(self):
1315
return annotate.Annotator(self)
1317
def check(self, progress_bar=None, keys=None):
1318
"""See VersionedFiles.check()."""
1321
for record in self.get_record_stream(keys, 'unordered', True):
1322
record.get_bytes_as('fulltext')
1324
return self.get_record_stream(keys, 'unordered', True)
1326
def clear_cache(self):
1327
"""See VersionedFiles.clear_cache()"""
1328
self._group_cache.clear()
1329
self._index._graph_index.clear_cache()
1330
self._index._int_cache.clear()
1332
def _check_add(self, key, lines, random_id, check_content):
1333
"""check that version_id and lines are safe to add."""
1334
version_id = key[-1]
1335
if version_id is not None:
1336
if osutils.contains_whitespace(version_id):
1337
raise errors.InvalidRevisionId(version_id, self)
1338
self.check_not_reserved_id(version_id)
1339
# TODO: If random_id==False and the key is already present, we should
1340
# probably check that the existing content is identical to what is
1341
# being inserted, and otherwise raise an exception. This would make
1342
# the bundle code simpler.
1344
self._check_lines_not_unicode(lines)
1345
self._check_lines_are_lines(lines)
1347
def get_parent_map(self, keys):
1348
"""Get a map of the graph parents of keys.
1350
:param keys: The keys to look up parents for.
1351
:return: A mapping from keys to parents. Absent keys are absent from
1354
return self._get_parent_map_with_sources(keys)[0]
1356
def _get_parent_map_with_sources(self, keys):
1357
"""Get a map of the parents of keys.
1359
:param keys: The keys to look up parents for.
1360
:return: A tuple. The first element is a mapping from keys to parents.
1361
Absent keys are absent from the mapping. The second element is a
1362
list with the locations each key was found in. The first element
1363
is the in-this-knit parents, the second the first fallback source,
1367
sources = [self._index] + self._immediate_fallback_vfs
1370
for source in sources:
1373
new_result = source.get_parent_map(missing)
1374
source_results.append(new_result)
1375
result.update(new_result)
1376
missing.difference_update(set(new_result))
1377
return result, source_results
1379
def _get_blocks(self, read_memos):
1380
"""Get GroupCompressBlocks for the given read_memos.
1382
:returns: a series of (read_memo, block) pairs, in the order they were
1386
for read_memo in read_memos:
1388
block = self._group_cache[read_memo]
1392
cached[read_memo] = block
1394
not_cached_seen = set()
1395
for read_memo in read_memos:
1396
if read_memo in cached:
1397
# Don't fetch what we already have
1399
if read_memo in not_cached_seen:
1400
# Don't try to fetch the same data twice
1402
not_cached.append(read_memo)
1403
not_cached_seen.add(read_memo)
1404
raw_records = self._access.get_raw_records(not_cached)
1405
for read_memo in read_memos:
1407
yield read_memo, cached[read_memo]
1409
# Read the block, and cache it.
1410
zdata = raw_records.next()
1411
block = GroupCompressBlock.from_bytes(zdata)
1412
self._group_cache[read_memo] = block
1413
cached[read_memo] = block
1414
yield read_memo, block
1416
def get_missing_compression_parent_keys(self):
1417
"""Return the keys of missing compression parents.
1419
Missing compression parents occur when a record stream was missing
1420
basis texts, or a index was scanned that had missing basis texts.
1422
# GroupCompress cannot currently reference texts that are not in the
1423
# group, so this is valid for now
1426
def get_record_stream(self, keys, ordering, include_delta_closure):
1427
"""Get a stream of records for keys.
1429
:param keys: The keys to include.
1430
:param ordering: Either 'unordered' or 'topological'. A topologically
1431
sorted stream has compression parents strictly before their
1433
:param include_delta_closure: If True then the closure across any
1434
compression parents will be included (in the opaque data).
1435
:return: An iterator of ContentFactory objects, each of which is only
1436
valid until the iterator is advanced.
1438
# keys might be a generator
1439
orig_keys = list(keys)
1443
if (not self._index.has_graph
1444
and ordering in ('topological', 'groupcompress')):
1445
# Cannot topological order when no graph has been stored.
1446
# but we allow 'as-requested' or 'unordered'
1447
ordering = 'unordered'
1449
remaining_keys = keys
1452
keys = set(remaining_keys)
1453
for content_factory in self._get_remaining_record_stream(keys,
1454
orig_keys, ordering, include_delta_closure):
1455
remaining_keys.discard(content_factory.key)
1456
yield content_factory
1458
except errors.RetryWithNewPacks, e:
1459
self._access.reload_or_raise(e)
1461
def _find_from_fallback(self, missing):
1462
"""Find whatever keys you can from the fallbacks.
1464
:param missing: A set of missing keys. This set will be mutated as keys
1465
are found from a fallback_vfs
1466
:return: (parent_map, key_to_source_map, source_results)
1467
parent_map the overall key => parent_keys
1468
key_to_source_map a dict from {key: source}
1469
source_results a list of (source: keys)
1472
key_to_source_map = {}
1474
for source in self._immediate_fallback_vfs:
1477
source_parents = source.get_parent_map(missing)
1478
parent_map.update(source_parents)
1479
source_parents = list(source_parents)
1480
source_results.append((source, source_parents))
1481
key_to_source_map.update((key, source) for key in source_parents)
1482
missing.difference_update(source_parents)
1483
return parent_map, key_to_source_map, source_results
1485
def _get_ordered_source_keys(self, ordering, parent_map, key_to_source_map):
1486
"""Get the (source, [keys]) list.
1488
The returned objects should be in the order defined by 'ordering',
1489
which can weave between different sources.
1491
:param ordering: Must be one of 'topological' or 'groupcompress'
1492
:return: List of [(source, [keys])] tuples, such that all keys are in
1493
the defined order, regardless of source.
1495
if ordering == 'topological':
1496
present_keys = tsort.topo_sort(parent_map)
1498
# ordering == 'groupcompress'
1499
# XXX: This only optimizes for the target ordering. We may need
1500
# to balance that with the time it takes to extract
1501
# ordering, by somehow grouping based on
1502
# locations[key][0:3]
1503
present_keys = sort_gc_optimal(parent_map)
1504
# Now group by source:
1506
current_source = None
1507
for key in present_keys:
1508
source = key_to_source_map.get(key, self)
1509
if source is not current_source:
1510
source_keys.append((source, []))
1511
current_source = source
1512
source_keys[-1][1].append(key)
1515
def _get_as_requested_source_keys(self, orig_keys, locations, unadded_keys,
1518
current_source = None
1519
for key in orig_keys:
1520
if key in locations or key in unadded_keys:
1522
elif key in key_to_source_map:
1523
source = key_to_source_map[key]
1526
if source is not current_source:
1527
source_keys.append((source, []))
1528
current_source = source
1529
source_keys[-1][1].append(key)
1532
def _get_io_ordered_source_keys(self, locations, unadded_keys,
1535
# This is the group the bytes are stored in, followed by the
1536
# location in the group
1537
return locations[key][0]
1538
present_keys = sorted(locations.iterkeys(), key=get_group)
1539
# We don't have an ordering for keys in the in-memory object, but
1540
# lets process the in-memory ones first.
1541
present_keys = list(unadded_keys) + present_keys
1542
# Now grab all of the ones from other sources
1543
source_keys = [(self, present_keys)]
1544
source_keys.extend(source_result)
1547
def _get_remaining_record_stream(self, keys, orig_keys, ordering,
1548
include_delta_closure):
1549
"""Get a stream of records for keys.
1551
:param keys: The keys to include.
1552
:param ordering: one of 'unordered', 'topological', 'groupcompress' or
1554
:param include_delta_closure: If True then the closure across any
1555
compression parents will be included (in the opaque data).
1556
:return: An iterator of ContentFactory objects, each of which is only
1557
valid until the iterator is advanced.
1560
locations = self._index.get_build_details(keys)
1561
unadded_keys = set(self._unadded_refs).intersection(keys)
1562
missing = keys.difference(locations)
1563
missing.difference_update(unadded_keys)
1564
(fallback_parent_map, key_to_source_map,
1565
source_result) = self._find_from_fallback(missing)
1566
if ordering in ('topological', 'groupcompress'):
1567
# would be better to not globally sort initially but instead
1568
# start with one key, recurse to its oldest parent, then grab
1569
# everything in the same group, etc.
1570
parent_map = dict((key, details[2]) for key, details in
1571
locations.iteritems())
1572
for key in unadded_keys:
1573
parent_map[key] = self._unadded_refs[key]
1574
parent_map.update(fallback_parent_map)
1575
source_keys = self._get_ordered_source_keys(ordering, parent_map,
1577
elif ordering == 'as-requested':
1578
source_keys = self._get_as_requested_source_keys(orig_keys,
1579
locations, unadded_keys, key_to_source_map)
1581
# We want to yield the keys in a semi-optimal (read-wise) ordering.
1582
# Otherwise we thrash the _group_cache and destroy performance
1583
source_keys = self._get_io_ordered_source_keys(locations,
1584
unadded_keys, source_result)
1586
yield AbsentContentFactory(key)
1587
# Batch up as many keys as we can until either:
1588
# - we encounter an unadded ref, or
1589
# - we run out of keys, or
1590
# - the total bytes to retrieve for this batch > BATCH_SIZE
1591
batcher = _BatchingBlockFetcher(self, locations,
1592
get_compressor_settings=self._get_compressor_settings)
1593
for source, keys in source_keys:
1596
if key in self._unadded_refs:
1597
# Flush batch, then yield unadded ref from
1599
for factory in batcher.yield_factories(full_flush=True):
1601
bytes, sha1 = self._compressor.extract(key)
1602
parents = self._unadded_refs[key]
1603
yield FulltextContentFactory(key, parents, sha1, bytes)
1605
if batcher.add_key(key) > BATCH_SIZE:
1606
# Ok, this batch is big enough. Yield some results.
1607
for factory in batcher.yield_factories():
1610
for factory in batcher.yield_factories(full_flush=True):
1612
for record in source.get_record_stream(keys, ordering,
1613
include_delta_closure):
1615
for factory in batcher.yield_factories(full_flush=True):
1618
def get_sha1s(self, keys):
1619
"""See VersionedFiles.get_sha1s()."""
1621
for record in self.get_record_stream(keys, 'unordered', True):
1622
if record.sha1 != None:
1623
result[record.key] = record.sha1
1625
if record.storage_kind != 'absent':
1626
result[record.key] = osutils.sha_string(
1627
record.get_bytes_as('fulltext'))
1630
def insert_record_stream(self, stream):
1631
"""Insert a record stream into this container.
1633
:param stream: A stream of records to insert.
1635
:seealso VersionedFiles.get_record_stream:
1637
# XXX: Setting random_id=True makes
1638
# test_insert_record_stream_existing_keys fail for groupcompress and
1639
# groupcompress-nograph, this needs to be revisited while addressing
1640
# 'bzr branch' performance issues.
1641
for _ in self._insert_record_stream(stream, random_id=False):
1644
def _get_compressor_settings(self):
1645
if self._max_bytes_to_index is None:
1646
# TODO: VersionedFiles don't know about their containing
1647
# repository, so they don't have much of an idea about their
1648
# location. So for now, this is only a global option.
1649
c = config.GlobalConfig()
1650
val = c.get_user_option('bzr.groupcompress.max_bytes_to_index')
1654
except ValueError, e:
1655
trace.warning('Value for '
1656
'"bzr.groupcompress.max_bytes_to_index"'
1657
' %r is not an integer'
1661
val = self._DEFAULT_MAX_BYTES_TO_INDEX
1662
self._max_bytes_to_index = val
1663
return {'max_bytes_to_index': self._max_bytes_to_index}
1665
def _make_group_compressor(self):
1666
return GroupCompressor(self._get_compressor_settings())
1668
def _insert_record_stream(self, stream, random_id=False, nostore_sha=None,
1670
"""Internal core to insert a record stream into this container.
1672
This helper function has a different interface than insert_record_stream
1673
to allow add_lines to be minimal, but still return the needed data.
1675
:param stream: A stream of records to insert.
1676
:param nostore_sha: If the sha1 of a given text matches nostore_sha,
1677
raise ExistingContent, rather than committing the new text.
1678
:param reuse_blocks: If the source is streaming from
1679
groupcompress-blocks, just insert the blocks as-is, rather than
1680
expanding the texts and inserting again.
1681
:return: An iterator over the sha1 of the inserted records.
1682
:seealso insert_record_stream:
1686
def get_adapter(adapter_key):
1688
return adapters[adapter_key]
1690
adapter_factory = adapter_registry.get(adapter_key)
1691
adapter = adapter_factory(self)
1692
adapters[adapter_key] = adapter
1694
# This will go up to fulltexts for gc to gc fetching, which isn't
1696
self._compressor = self._make_group_compressor()
1697
self._unadded_refs = {}
1700
bytes_len, chunks = self._compressor.flush().to_chunks()
1701
self._compressor = self._make_group_compressor()
1702
# Note: At this point we still have 1 copy of the fulltext (in
1703
# record and the var 'bytes'), and this generates 2 copies of
1704
# the compressed text (one for bytes, one in chunks)
1705
# TODO: Push 'chunks' down into the _access api, so that we don't
1706
# have to double compressed memory here
1707
# TODO: Figure out how to indicate that we would be happy to free
1708
# the fulltext content at this point. Note that sometimes we
1709
# will want it later (streaming CHK pages), but most of the
1710
# time we won't (everything else)
1711
bytes = ''.join(chunks)
1713
index, start, length = self._access.add_raw_records(
1714
[(None, len(bytes))], bytes)[0]
1716
for key, reads, refs in keys_to_add:
1717
nodes.append((key, "%d %d %s" % (start, length, reads), refs))
1718
self._index.add_records(nodes, random_id=random_id)
1719
self._unadded_refs = {}
1723
max_fulltext_len = 0
1724
max_fulltext_prefix = None
1725
insert_manager = None
1728
# XXX: TODO: remove this, it is just for safety checking for now
1729
inserted_keys = set()
1730
reuse_this_block = reuse_blocks
1731
for record in stream:
1732
# Raise an error when a record is missing.
1733
if record.storage_kind == 'absent':
1734
raise errors.RevisionNotPresent(record.key, self)
1736
if record.key in inserted_keys:
1737
trace.note(gettext('Insert claimed random_id=True,'
1738
' but then inserted %r two times'), record.key)
1740
inserted_keys.add(record.key)
1742
# If the reuse_blocks flag is set, check to see if we can just
1743
# copy a groupcompress block as-is.
1744
# We only check on the first record (groupcompress-block) not
1745
# on all of the (groupcompress-block-ref) entries.
1746
# The reuse_this_block flag is then kept for as long as
1747
if record.storage_kind == 'groupcompress-block':
1748
# Check to see if we really want to re-use this block
1749
insert_manager = record._manager
1750
reuse_this_block = insert_manager.check_is_well_utilized()
1752
reuse_this_block = False
1753
if reuse_this_block:
1754
# We still want to reuse this block
1755
if record.storage_kind == 'groupcompress-block':
1756
# Insert the raw block into the target repo
1757
insert_manager = record._manager
1758
bytes = record._manager._block.to_bytes()
1759
_, start, length = self._access.add_raw_records(
1760
[(None, len(bytes))], bytes)[0]
1763
block_length = length
1764
if record.storage_kind in ('groupcompress-block',
1765
'groupcompress-block-ref'):
1766
if insert_manager is None:
1767
raise AssertionError('No insert_manager set')
1768
if insert_manager is not record._manager:
1769
raise AssertionError('insert_manager does not match'
1770
' the current record, we cannot be positive'
1771
' that the appropriate content was inserted.'
1773
value = "%d %d %d %d" % (block_start, block_length,
1774
record._start, record._end)
1775
nodes = [(record.key, value, (record.parents,))]
1776
# TODO: Consider buffering up many nodes to be added, not
1777
# sure how much overhead this has, but we're seeing
1778
# ~23s / 120s in add_records calls
1779
self._index.add_records(nodes, random_id=random_id)
1782
bytes = record.get_bytes_as('fulltext')
1783
except errors.UnavailableRepresentation:
1784
adapter_key = record.storage_kind, 'fulltext'
1785
adapter = get_adapter(adapter_key)
1786
bytes = adapter.get_bytes(record)
1787
if len(record.key) > 1:
1788
prefix = record.key[0]
1789
soft = (prefix == last_prefix)
1793
if max_fulltext_len < len(bytes):
1794
max_fulltext_len = len(bytes)
1795
max_fulltext_prefix = prefix
1796
(found_sha1, start_point, end_point,
1797
type) = self._compressor.compress(record.key,
1798
bytes, record.sha1, soft=soft,
1799
nostore_sha=nostore_sha)
1800
# delta_ratio = float(len(bytes)) / (end_point - start_point)
1801
# Check if we want to continue to include that text
1802
if (prefix == max_fulltext_prefix
1803
and end_point < 2 * max_fulltext_len):
1804
# As long as we are on the same file_id, we will fill at least
1805
# 2 * max_fulltext_len
1806
start_new_block = False
1807
elif end_point > 4*1024*1024:
1808
start_new_block = True
1809
elif (prefix is not None and prefix != last_prefix
1810
and end_point > 2*1024*1024):
1811
start_new_block = True
1813
start_new_block = False
1814
last_prefix = prefix
1816
self._compressor.pop_last()
1818
max_fulltext_len = len(bytes)
1819
(found_sha1, start_point, end_point,
1820
type) = self._compressor.compress(record.key, bytes,
1822
if record.key[-1] is None:
1823
key = record.key[:-1] + ('sha1:' + found_sha1,)
1826
self._unadded_refs[key] = record.parents
1828
as_st = static_tuple.StaticTuple.from_sequence
1829
if record.parents is not None:
1830
parents = as_st([as_st(p) for p in record.parents])
1833
refs = static_tuple.StaticTuple(parents)
1834
keys_to_add.append((key, '%d %d' % (start_point, end_point), refs))
1835
if len(keys_to_add):
1837
self._compressor = None
1839
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1840
"""Iterate over the lines in the versioned files from keys.
1842
This may return lines from other keys. Each item the returned
1843
iterator yields is a tuple of a line and a text version that that line
1844
is present in (not introduced in).
1846
Ordering of results is in whatever order is most suitable for the
1847
underlying storage format.
1849
If a progress bar is supplied, it may be used to indicate progress.
1850
The caller is responsible for cleaning up progress bars (because this
1854
* Lines are normalised by the underlying store: they will all have \n
1856
* Lines are returned in arbitrary order.
1858
:return: An iterator over (line, key).
1862
# we don't care about inclusions, the caller cares.
1863
# but we need to setup a list of records to visit.
1864
# we need key, position, length
1865
for key_idx, record in enumerate(self.get_record_stream(keys,
1866
'unordered', True)):
1867
# XXX: todo - optimise to use less than full texts.
1870
pb.update('Walking content', key_idx, total)
1871
if record.storage_kind == 'absent':
1872
raise errors.RevisionNotPresent(key, self)
1873
lines = osutils.split_lines(record.get_bytes_as('fulltext'))
1877
pb.update('Walking content', total, total)
1880
"""See VersionedFiles.keys."""
1881
if 'evil' in debug.debug_flags:
1882
trace.mutter_callsite(2, "keys scales with size of history")
1883
sources = [self._index] + self._immediate_fallback_vfs
1885
for source in sources:
1886
result.update(source.keys())
1890
class _GCBuildDetails(object):
1891
"""A blob of data about the build details.
1893
This stores the minimal data, which then allows compatibility with the old
1894
api, without taking as much memory.
1897
__slots__ = ('_index', '_group_start', '_group_end', '_basis_end',
1898
'_delta_end', '_parents')
1901
compression_parent = None
1903
def __init__(self, parents, position_info):
1904
self._parents = parents
1905
(self._index, self._group_start, self._group_end, self._basis_end,
1906
self._delta_end) = position_info
1909
return '%s(%s, %s)' % (self.__class__.__name__,
1910
self.index_memo, self._parents)
1913
def index_memo(self):
1914
return (self._index, self._group_start, self._group_end,
1915
self._basis_end, self._delta_end)
1918
def record_details(self):
1919
return static_tuple.StaticTuple(self.method, None)
1921
def __getitem__(self, offset):
1922
"""Compatibility thunk to act like a tuple."""
1924
return self.index_memo
1926
return self.compression_parent # Always None
1928
return self._parents
1930
return self.record_details
1932
raise IndexError('offset out of range')
1938
class _GCGraphIndex(object):
1939
"""Mapper from GroupCompressVersionedFiles needs into GraphIndex storage."""
1941
def __init__(self, graph_index, is_locked, parents=True,
1942
add_callback=None, track_external_parent_refs=False,
1943
inconsistency_fatal=True, track_new_keys=False):
1944
"""Construct a _GCGraphIndex on a graph_index.
1946
:param graph_index: An implementation of bzrlib.index.GraphIndex.
1947
:param is_locked: A callback, returns True if the index is locked and
1949
:param parents: If True, record knits parents, if not do not record
1951
:param add_callback: If not None, allow additions to the index and call
1952
this callback with a list of added GraphIndex nodes:
1953
[(node, value, node_refs), ...]
1954
:param track_external_parent_refs: As keys are added, keep track of the
1955
keys they reference, so that we can query get_missing_parents(),
1957
:param inconsistency_fatal: When asked to add records that are already
1958
present, and the details are inconsistent with the existing
1959
record, raise an exception instead of warning (and skipping the
1962
self._add_callback = add_callback
1963
self._graph_index = graph_index
1964
self._parents = parents
1965
self.has_graph = parents
1966
self._is_locked = is_locked
1967
self._inconsistency_fatal = inconsistency_fatal
1968
# GroupCompress records tend to have the same 'group' start + offset
1969
# repeated over and over, this creates a surplus of ints
1970
self._int_cache = {}
1971
if track_external_parent_refs:
1972
self._key_dependencies = _KeyRefs(
1973
track_new_keys=track_new_keys)
1975
self._key_dependencies = None
1977
def add_records(self, records, random_id=False):
1978
"""Add multiple records to the index.
1980
This function does not insert data into the Immutable GraphIndex
1981
backing the KnitGraphIndex, instead it prepares data for insertion by
1982
the caller and checks that it is safe to insert then calls
1983
self._add_callback with the prepared GraphIndex nodes.
1985
:param records: a list of tuples:
1986
(key, options, access_memo, parents).
1987
:param random_id: If True the ids being added were randomly generated
1988
and no check for existence will be performed.
1990
if not self._add_callback:
1991
raise errors.ReadOnlyError(self)
1992
# we hope there are no repositories with inconsistent parentage
1997
for (key, value, refs) in records:
1998
if not self._parents:
2002
raise errors.KnitCorrupt(self,
2003
"attempt to add node with parents "
2004
"in parentless index.")
2007
keys[key] = (value, refs)
2010
present_nodes = self._get_entries(keys)
2011
for (index, key, value, node_refs) in present_nodes:
2012
# Sometimes these are passed as a list rather than a tuple
2013
node_refs = static_tuple.as_tuples(node_refs)
2014
passed = static_tuple.as_tuples(keys[key])
2015
if node_refs != passed[1]:
2016
details = '%s %s %s' % (key, (value, node_refs), passed)
2017
if self._inconsistency_fatal:
2018
raise errors.KnitCorrupt(self, "inconsistent details"
2019
" in add_records: %s" %
2022
trace.warning("inconsistent details in skipped"
2023
" record: %s", details)
2029
for key, (value, node_refs) in keys.iteritems():
2030
result.append((key, value, node_refs))
2032
for key, (value, node_refs) in keys.iteritems():
2033
result.append((key, value))
2035
key_dependencies = self._key_dependencies
2036
if key_dependencies is not None:
2038
for key, value, refs in records:
2040
key_dependencies.add_references(key, parents)
2042
for key, value, refs in records:
2043
new_keys.add_key(key)
2044
self._add_callback(records)
2046
def _check_read(self):
2047
"""Raise an exception if reads are not permitted."""
2048
if not self._is_locked():
2049
raise errors.ObjectNotLocked(self)
2051
def _check_write_ok(self):
2052
"""Raise an exception if writes are not permitted."""
2053
if not self._is_locked():
2054
raise errors.ObjectNotLocked(self)
2056
def _get_entries(self, keys, check_present=False):
2057
"""Get the entries for keys.
2059
Note: Callers are responsible for checking that the index is locked
2060
before calling this method.
2062
:param keys: An iterable of index key tuples.
2067
for node in self._graph_index.iter_entries(keys):
2069
found_keys.add(node[1])
2071
# adapt parentless index to the rest of the code.
2072
for node in self._graph_index.iter_entries(keys):
2073
yield node[0], node[1], node[2], ()
2074
found_keys.add(node[1])
2076
missing_keys = keys.difference(found_keys)
2078
raise errors.RevisionNotPresent(missing_keys.pop(), self)
2080
def find_ancestry(self, keys):
2081
"""See CombinedGraphIndex.find_ancestry"""
2082
return self._graph_index.find_ancestry(keys, 0)
2084
def get_parent_map(self, keys):
2085
"""Get a map of the parents of keys.
2087
:param keys: The keys to look up parents for.
2088
:return: A mapping from keys to parents. Absent keys are absent from
2092
nodes = self._get_entries(keys)
2096
result[node[1]] = node[3][0]
2099
result[node[1]] = None
2102
def get_missing_parents(self):
2103
"""Return the keys of missing parents."""
2104
# Copied from _KnitGraphIndex.get_missing_parents
2105
# We may have false positives, so filter those out.
2106
self._key_dependencies.satisfy_refs_for_keys(
2107
self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
2108
return frozenset(self._key_dependencies.get_unsatisfied_refs())
2110
def get_build_details(self, keys):
2111
"""Get the various build details for keys.
2113
Ghosts are omitted from the result.
2115
:param keys: An iterable of keys.
2116
:return: A dict of key:
2117
(index_memo, compression_parent, parents, record_details).
2119
* index_memo: opaque structure to pass to read_records to extract
2121
* compression_parent: Content that this record is built upon, may
2123
* parents: Logical parents of this node
2124
* record_details: extra information about the content which needs
2125
to be passed to Factory.parse_record
2129
entries = self._get_entries(keys)
2130
for entry in entries:
2132
if not self._parents:
2135
parents = entry[3][0]
2136
details = _GCBuildDetails(parents, self._node_to_position(entry))
2137
result[key] = details
2141
"""Get all the keys in the collection.
2143
The keys are not ordered.
2146
return [node[1] for node in self._graph_index.iter_all_entries()]
2148
def _node_to_position(self, node):
2149
"""Convert an index value to position details."""
2150
bits = node[2].split(' ')
2151
# It would be nice not to read the entire gzip.
2152
# start and stop are put into _int_cache because they are very common.
2153
# They define the 'group' that an entry is in, and many groups can have
2154
# thousands of objects.
2155
# Branching Launchpad, for example, saves ~600k integers, at 12 bytes
2156
# each, or about 7MB. Note that it might be even more when you consider
2157
# how PyInt is allocated in separate slabs. And you can't return a slab
2158
# to the OS if even 1 int on it is in use. Note though that Python uses
2159
# a LIFO when re-using PyInt slots, which might cause more
2161
start = int(bits[0])
2162
start = self._int_cache.setdefault(start, start)
2164
stop = self._int_cache.setdefault(stop, stop)
2165
basis_end = int(bits[2])
2166
delta_end = int(bits[3])
2167
# We can't use StaticTuple here, because node[0] is a BTreeGraphIndex
2169
return (node[0], start, stop, basis_end, delta_end)
2171
def scan_unvalidated_index(self, graph_index):
2172
"""Inform this _GCGraphIndex that there is an unvalidated index.
2174
This allows this _GCGraphIndex to keep track of any missing
2175
compression parents we may want to have filled in to make those
2176
indices valid. It also allows _GCGraphIndex to track any new keys.
2178
:param graph_index: A GraphIndex
2180
key_dependencies = self._key_dependencies
2181
if key_dependencies is None:
2183
for node in graph_index.iter_all_entries():
2184
# Add parent refs from graph_index (and discard parent refs
2185
# that the graph_index has).
2186
key_dependencies.add_references(node[1], node[3][0])
2189
from bzrlib._groupcompress_py import (
2191
apply_delta_to_source,
2194
decode_copy_instruction,
2198
from bzrlib._groupcompress_pyx import (
2200
apply_delta_to_source,
2205
GroupCompressor = PyrexGroupCompressor
2206
except ImportError, e:
2207
osutils.failed_to_load_extension(e)
2208
GroupCompressor = PythonGroupCompressor
added
removed
bzrlib/groupcompress.py
