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 ..lazy_import import lazy_import
25
lazy_import(globals(), """
37
from breezy.bzr import (
41
from breezy.bzr import pack_repo
42
from breezy.i18n import gettext
45
from .btree_index import BTreeBuilder
46
from ..lru_cache import LRUSizeCache
47
from ..sixish import (
52
from .versionedfile import (
56
ChunkedContentFactory,
57
FulltextContentFactory,
58
VersionedFilesWithFallbacks,
61
# Minimum number of uncompressed bytes to try fetch at once when retrieving
62
# groupcompress blocks.
65
# osutils.sha_string('')
66
_null_sha1 = 'da39a3ee5e6b4b0d3255bfef95601890afd80709'
68
def sort_gc_optimal(parent_map):
69
"""Sort and group the keys in parent_map into groupcompress order.
71
groupcompress is defined (currently) as reverse-topological order, grouped
74
:return: A sorted-list of keys
76
# groupcompress ordering is approximately reverse topological,
77
# properly grouped by file-id.
79
for key, value in viewitems(parent_map):
80
if isinstance(key, str) or len(key) == 1:
85
per_prefix_map[prefix][key] = value
87
per_prefix_map[prefix] = {key: value}
90
for prefix in sorted(per_prefix_map):
91
present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
95
# The max zlib window size is 32kB, so if we set 'max_size' output of the
96
# decompressor to the requested bytes + 32kB, then we should guarantee
97
# num_bytes coming out.
98
_ZLIB_DECOMP_WINDOW = 32*1024
100
class GroupCompressBlock(object):
101
"""An object which maintains the internal structure of the compressed data.
103
This tracks the meta info (start of text, length, type, etc.)
106
# Group Compress Block v1 Zlib
107
GCB_HEADER = 'gcb1z\n'
108
# Group Compress Block v1 Lzma
109
GCB_LZ_HEADER = 'gcb1l\n'
110
GCB_KNOWN_HEADERS = (GCB_HEADER, GCB_LZ_HEADER)
113
# map by key? or just order in file?
114
self._compressor_name = None
115
self._z_content_chunks = None
116
self._z_content_decompressor = None
117
self._z_content_length = None
118
self._content_length = None
120
self._content_chunks = None
123
# This is the maximum number of bytes this object will reference if
124
# everything is decompressed. However, if we decompress less than
125
# everything... (this would cause some problems for LRUSizeCache)
126
return self._content_length + self._z_content_length
128
def _ensure_content(self, num_bytes=None):
129
"""Make sure that content has been expanded enough.
131
:param num_bytes: Ensure that we have extracted at least num_bytes of
132
content. If None, consume everything
134
if self._content_length is None:
135
raise AssertionError('self._content_length should never be None')
136
if num_bytes is None:
137
num_bytes = self._content_length
138
elif (self._content_length is not None
139
and num_bytes > self._content_length):
140
raise AssertionError(
141
'requested num_bytes (%d) > content length (%d)'
142
% (num_bytes, self._content_length))
143
# Expand the content if required
144
if self._content is None:
145
if self._content_chunks is not None:
146
self._content = ''.join(self._content_chunks)
147
self._content_chunks = None
148
if self._content is None:
149
# We join self._z_content_chunks here, because if we are
150
# decompressing, then it is *very* likely that we have a single
152
if self._z_content_chunks is None:
153
raise AssertionError('No content to decompress')
154
z_content = ''.join(self._z_content_chunks)
157
elif self._compressor_name == 'lzma':
158
# We don't do partial lzma decomp yet
160
self._content = pylzma.decompress(z_content)
161
elif self._compressor_name == 'zlib':
162
# Start a zlib decompressor
163
if num_bytes * 4 > self._content_length * 3:
164
# If we are requesting more that 3/4ths of the content,
165
# just extract the whole thing in a single pass
166
num_bytes = self._content_length
167
self._content = zlib.decompress(z_content)
169
self._z_content_decompressor = zlib.decompressobj()
170
# Seed the decompressor with the uncompressed bytes, so
171
# that the rest of the code is simplified
172
self._content = self._z_content_decompressor.decompress(
173
z_content, num_bytes + _ZLIB_DECOMP_WINDOW)
174
if not self._z_content_decompressor.unconsumed_tail:
175
self._z_content_decompressor = None
177
raise AssertionError('Unknown compressor: %r'
178
% self._compressor_name)
179
# Any bytes remaining to be decompressed will be in the decompressors
182
# Do we have enough bytes already?
183
if len(self._content) >= num_bytes:
185
# If we got this far, and don't have a decompressor, something is wrong
186
if self._z_content_decompressor is None:
187
raise AssertionError(
188
'No decompressor to decompress %d bytes' % num_bytes)
189
remaining_decomp = self._z_content_decompressor.unconsumed_tail
190
if not remaining_decomp:
191
raise AssertionError('Nothing left to decompress')
192
needed_bytes = num_bytes - len(self._content)
193
# We always set max_size to 32kB over the minimum needed, so that
194
# zlib will give us as much as we really want.
195
# TODO: If this isn't good enough, we could make a loop here,
196
# that keeps expanding the request until we get enough
197
self._content += self._z_content_decompressor.decompress(
198
remaining_decomp, needed_bytes + _ZLIB_DECOMP_WINDOW)
199
if len(self._content) < num_bytes:
200
raise AssertionError('%d bytes wanted, only %d available'
201
% (num_bytes, len(self._content)))
202
if not self._z_content_decompressor.unconsumed_tail:
203
# The stream is finished
204
self._z_content_decompressor = None
206
def _parse_bytes(self, bytes, pos):
207
"""Read the various lengths from the header.
209
This also populates the various 'compressed' buffers.
211
:return: The position in bytes just after the last newline
213
# At present, we have 2 integers for the compressed and uncompressed
214
# content. In base10 (ascii) 14 bytes can represent > 1TB, so to avoid
215
# checking too far, cap the search to 14 bytes.
216
pos2 = bytes.index('\n', pos, pos + 14)
217
self._z_content_length = int(bytes[pos:pos2])
219
pos2 = bytes.index('\n', pos, pos + 14)
220
self._content_length = int(bytes[pos:pos2])
222
if len(bytes) != (pos + self._z_content_length):
223
# XXX: Define some GCCorrupt error ?
224
raise AssertionError('Invalid bytes: (%d) != %d + %d' %
225
(len(bytes), pos, self._z_content_length))
226
self._z_content_chunks = (bytes[pos:],)
229
def _z_content(self):
230
"""Return z_content_chunks as a simple string.
232
Meant only to be used by the test suite.
234
if self._z_content_chunks is not None:
235
return ''.join(self._z_content_chunks)
239
def from_bytes(cls, bytes):
241
if bytes[:6] not in cls.GCB_KNOWN_HEADERS:
242
raise ValueError('bytes did not start with any of %r'
243
% (cls.GCB_KNOWN_HEADERS,))
244
# XXX: why not testing the whole header ?
246
out._compressor_name = 'zlib'
247
elif bytes[4] == 'l':
248
out._compressor_name = 'lzma'
250
raise ValueError('unknown compressor: %r' % (bytes,))
251
out._parse_bytes(bytes, 6)
254
def extract(self, key, start, end, sha1=None):
255
"""Extract the text for a specific key.
257
:param key: The label used for this content
258
:param sha1: TODO (should we validate only when sha1 is supplied?)
259
:return: The bytes for the content
261
if start == end == 0:
263
self._ensure_content(end)
264
# The bytes are 'f' or 'd' for the type, then a variable-length
265
# base128 integer for the content size, then the actual content
266
# We know that the variable-length integer won't be longer than 5
267
# bytes (it takes 5 bytes to encode 2^32)
268
c = self._content[start]
273
raise ValueError('Unknown content control code: %s'
276
content_len, len_len = decode_base128_int(
277
self._content[start + 1:start + 6])
278
content_start = start + 1 + len_len
279
if end != content_start + content_len:
280
raise ValueError('end != len according to field header'
281
' %s != %s' % (end, content_start + content_len))
283
bytes = self._content[content_start:end]
285
bytes = apply_delta_to_source(self._content, content_start, end)
288
def set_chunked_content(self, content_chunks, length):
289
"""Set the content of this block to the given chunks."""
290
# If we have lots of short lines, it is may be more efficient to join
291
# the content ahead of time. If the content is <10MiB, we don't really
292
# care about the extra memory consumption, so we can just pack it and
293
# be done. However, timing showed 18s => 17.9s for repacking 1k revs of
294
# mysql, which is below the noise margin
295
self._content_length = length
296
self._content_chunks = content_chunks
298
self._z_content_chunks = None
300
def set_content(self, content):
301
"""Set the content of this block."""
302
self._content_length = len(content)
303
self._content = content
304
self._z_content_chunks = None
306
def _create_z_content_from_chunks(self, chunks):
307
compressor = zlib.compressobj(zlib.Z_DEFAULT_COMPRESSION)
308
# Peak in this point is 1 fulltext, 1 compressed text, + zlib overhead
309
# (measured peak is maybe 30MB over the above...)
310
compressed_chunks = list(map(compressor.compress, chunks))
311
compressed_chunks.append(compressor.flush())
312
# Ignore empty chunks
313
self._z_content_chunks = [c for c in compressed_chunks if c]
314
self._z_content_length = sum(map(len, self._z_content_chunks))
316
def _create_z_content(self):
317
if self._z_content_chunks is not None:
319
if self._content_chunks is not None:
320
chunks = self._content_chunks
322
chunks = (self._content,)
323
self._create_z_content_from_chunks(chunks)
326
"""Create the byte stream as a series of 'chunks'"""
327
self._create_z_content()
328
header = self.GCB_HEADER
329
chunks = ['%s%d\n%d\n'
330
% (header, self._z_content_length, self._content_length),
332
chunks.extend(self._z_content_chunks)
333
total_len = sum(map(len, chunks))
334
return total_len, chunks
337
"""Encode the information into a byte stream."""
338
total_len, chunks = self.to_chunks()
339
return ''.join(chunks)
341
def _dump(self, include_text=False):
342
"""Take this block, and spit out a human-readable structure.
344
:param include_text: Inserts also include text bits, chose whether you
345
want this displayed in the dump or not.
346
:return: A dump of the given block. The layout is something like:
347
[('f', length), ('d', delta_length, text_length, [delta_info])]
348
delta_info := [('i', num_bytes, text), ('c', offset, num_bytes),
351
self._ensure_content()
354
while pos < self._content_length:
355
kind = self._content[pos]
357
if kind not in ('f', 'd'):
358
raise ValueError('invalid kind character: %r' % (kind,))
359
content_len, len_len = decode_base128_int(
360
self._content[pos:pos + 5])
362
if content_len + pos > self._content_length:
363
raise ValueError('invalid content_len %d for record @ pos %d'
364
% (content_len, pos - len_len - 1))
365
if kind == 'f': # Fulltext
367
text = self._content[pos:pos+content_len]
368
result.append(('f', content_len, text))
370
result.append(('f', content_len))
371
elif kind == 'd': # Delta
372
delta_content = self._content[pos:pos+content_len]
374
# The first entry in a delta is the decompressed length
375
decomp_len, delta_pos = decode_base128_int(delta_content)
376
result.append(('d', content_len, decomp_len, delta_info))
378
while delta_pos < content_len:
379
c = ord(delta_content[delta_pos])
383
delta_pos) = decode_copy_instruction(delta_content, c,
386
text = self._content[offset:offset+length]
387
delta_info.append(('c', offset, length, text))
389
delta_info.append(('c', offset, length))
390
measured_len += length
393
txt = delta_content[delta_pos:delta_pos+c]
396
delta_info.append(('i', c, txt))
399
if delta_pos != content_len:
400
raise ValueError('Delta consumed a bad number of bytes:'
401
' %d != %d' % (delta_pos, content_len))
402
if measured_len != decomp_len:
403
raise ValueError('Delta claimed fulltext was %d bytes, but'
404
' extraction resulted in %d bytes'
405
% (decomp_len, measured_len))
410
class _LazyGroupCompressFactory(object):
411
"""Yield content from a GroupCompressBlock on demand."""
413
def __init__(self, key, parents, manager, start, end, first):
414
"""Create a _LazyGroupCompressFactory
416
:param key: The key of just this record
417
:param parents: The parents of this key (possibly None)
418
:param gc_block: A GroupCompressBlock object
419
:param start: Offset of the first byte for this record in the
421
:param end: Offset of the byte just after the end of this record
422
(ie, bytes = content[start:end])
423
:param first: Is this the first Factory for the given block?
426
self.parents = parents
428
# Note: This attribute coupled with Manager._factories creates a
429
# reference cycle. Perhaps we would rather use a weakref(), or
430
# find an appropriate time to release the ref. After the first
431
# get_bytes_as call? After Manager.get_record_stream() returns
433
self._manager = manager
435
self.storage_kind = 'groupcompress-block'
437
self.storage_kind = 'groupcompress-block-ref'
443
return '%s(%s, first=%s)' % (self.__class__.__name__,
444
self.key, self._first)
446
def get_bytes_as(self, storage_kind):
447
if storage_kind == self.storage_kind:
449
# wire bytes, something...
450
return self._manager._wire_bytes()
453
if storage_kind in ('fulltext', 'chunked'):
454
if self._bytes is None:
455
# Grab and cache the raw bytes for this entry
456
# and break the ref-cycle with _manager since we don't need it
459
self._manager._prepare_for_extract()
460
except zlib.error as value:
461
raise errors.DecompressCorruption("zlib: " + str(value))
462
block = self._manager._block
463
self._bytes = block.extract(self.key, self._start, self._end)
464
# There are code paths that first extract as fulltext, and then
465
# extract as storage_kind (smart fetch). So we don't break the
466
# refcycle here, but instead in manager.get_record_stream()
467
if storage_kind == 'fulltext':
471
raise errors.UnavailableRepresentation(self.key, storage_kind,
475
class _LazyGroupContentManager(object):
476
"""This manages a group of _LazyGroupCompressFactory objects."""
478
_max_cut_fraction = 0.75 # We allow a block to be trimmed to 75% of
479
# current size, and still be considered
481
_full_block_size = 4*1024*1024
482
_full_mixed_block_size = 2*1024*1024
483
_full_enough_block_size = 3*1024*1024 # size at which we won't repack
484
_full_enough_mixed_block_size = 2*768*1024 # 1.5MB
486
def __init__(self, block, get_compressor_settings=None):
488
# We need to preserve the ordering
491
self._get_settings = get_compressor_settings
492
self._compressor_settings = None
494
def _get_compressor_settings(self):
495
if self._compressor_settings is not None:
496
return self._compressor_settings
498
if self._get_settings is not None:
499
settings = self._get_settings()
501
vf = GroupCompressVersionedFiles
502
settings = vf._DEFAULT_COMPRESSOR_SETTINGS
503
self._compressor_settings = settings
504
return self._compressor_settings
506
def add_factory(self, key, parents, start, end):
507
if not self._factories:
511
# Note that this creates a reference cycle....
512
factory = _LazyGroupCompressFactory(key, parents, self,
513
start, end, first=first)
514
# max() works here, but as a function call, doing a compare seems to be
515
# significantly faster, timeit says 250ms for max() and 100ms for the
517
if end > self._last_byte:
518
self._last_byte = end
519
self._factories.append(factory)
521
def get_record_stream(self):
522
"""Get a record for all keys added so far."""
523
for factory in self._factories:
525
# Break the ref-cycle
526
factory._bytes = None
527
factory._manager = None
528
# TODO: Consider setting self._factories = None after the above loop,
529
# as it will break the reference cycle
531
def _trim_block(self, last_byte):
532
"""Create a new GroupCompressBlock, with just some of the content."""
533
# None of the factories need to be adjusted, because the content is
534
# located in an identical place. Just that some of the unreferenced
535
# trailing bytes are stripped
536
trace.mutter('stripping trailing bytes from groupcompress block'
537
' %d => %d', self._block._content_length, last_byte)
538
new_block = GroupCompressBlock()
539
self._block._ensure_content(last_byte)
540
new_block.set_content(self._block._content[:last_byte])
541
self._block = new_block
543
def _make_group_compressor(self):
544
return GroupCompressor(self._get_compressor_settings())
546
def _rebuild_block(self):
547
"""Create a new GroupCompressBlock with only the referenced texts."""
548
compressor = self._make_group_compressor()
550
old_length = self._block._content_length
552
for factory in self._factories:
553
bytes = factory.get_bytes_as('fulltext')
554
(found_sha1, start_point, end_point,
555
type) = compressor.compress(factory.key, bytes, factory.sha1)
556
# Now update this factory with the new offsets, etc
557
factory.sha1 = found_sha1
558
factory._start = start_point
559
factory._end = end_point
560
self._last_byte = end_point
561
new_block = compressor.flush()
562
# TODO: Should we check that new_block really *is* smaller than the old
563
# block? It seems hard to come up with a method that it would
564
# expand, since we do full compression again. Perhaps based on a
565
# request that ends up poorly ordered?
566
# TODO: If the content would have expanded, then we would want to
567
# handle a case where we need to split the block.
568
# Now that we have a user-tweakable option
569
# (max_bytes_to_index), it is possible that one person set it
570
# to a very low value, causing poor compression.
571
delta = time.time() - tstart
572
self._block = new_block
573
trace.mutter('creating new compressed block on-the-fly in %.3fs'
574
' %d bytes => %d bytes', delta, old_length,
575
self._block._content_length)
577
def _prepare_for_extract(self):
578
"""A _LazyGroupCompressFactory is about to extract to fulltext."""
579
# We expect that if one child is going to fulltext, all will be. This
580
# helps prevent all of them from extracting a small amount at a time.
581
# Which in itself isn't terribly expensive, but resizing 2MB 32kB at a
582
# time (self._block._content) is a little expensive.
583
self._block._ensure_content(self._last_byte)
585
def _check_rebuild_action(self):
586
"""Check to see if our block should be repacked."""
589
for factory in self._factories:
590
total_bytes_used += factory._end - factory._start
591
if last_byte_used < factory._end:
592
last_byte_used = factory._end
593
# If we are using more than half of the bytes from the block, we have
594
# nothing else to check
595
if total_bytes_used * 2 >= self._block._content_length:
596
return None, last_byte_used, total_bytes_used
597
# We are using less than 50% of the content. Is the content we are
598
# using at the beginning of the block? If so, we can just trim the
599
# tail, rather than rebuilding from scratch.
600
if total_bytes_used * 2 > last_byte_used:
601
return 'trim', last_byte_used, total_bytes_used
603
# We are using a small amount of the data, and it isn't just packed
604
# nicely at the front, so rebuild the content.
605
# Note: This would be *nicer* as a strip-data-from-group, rather than
606
# building it up again from scratch
607
# It might be reasonable to consider the fulltext sizes for
608
# different bits when deciding this, too. As you may have a small
609
# fulltext, and a trivial delta, and you are just trading around
610
# for another fulltext. If we do a simple 'prune' you may end up
611
# expanding many deltas into fulltexts, as well.
612
# If we build a cheap enough 'strip', then we could try a strip,
613
# if that expands the content, we then rebuild.
614
return 'rebuild', last_byte_used, total_bytes_used
616
def check_is_well_utilized(self):
617
"""Is the current block considered 'well utilized'?
619
This heuristic asks if the current block considers itself to be a fully
620
developed group, rather than just a loose collection of data.
622
if len(self._factories) == 1:
623
# A block of length 1 could be improved by combining with other
624
# groups - don't look deeper. Even larger than max size groups
625
# could compress well with adjacent versions of the same thing.
627
action, last_byte_used, total_bytes_used = self._check_rebuild_action()
628
block_size = self._block._content_length
629
if total_bytes_used < block_size * self._max_cut_fraction:
630
# This block wants to trim itself small enough that we want to
631
# consider it under-utilized.
633
# TODO: This code is meant to be the twin of _insert_record_stream's
634
# 'start_new_block' logic. It would probably be better to factor
635
# out that logic into a shared location, so that it stays
637
# We currently assume a block is properly utilized whenever it is >75%
638
# of the size of a 'full' block. In normal operation, a block is
639
# considered full when it hits 4MB of same-file content. So any block
640
# >3MB is 'full enough'.
641
# The only time this isn't true is when a given block has large-object
642
# content. (a single file >4MB, etc.)
643
# Under these circumstances, we allow a block to grow to
644
# 2 x largest_content. Which means that if a given block had a large
645
# object, it may actually be under-utilized. However, given that this
646
# is 'pack-on-the-fly' it is probably reasonable to not repack large
647
# content blobs on-the-fly. Note that because we return False for all
648
# 1-item blobs, we will repack them; we may wish to reevaluate our
649
# treatment of large object blobs in the future.
650
if block_size >= self._full_enough_block_size:
652
# If a block is <3MB, it still may be considered 'full' if it contains
653
# mixed content. The current rule is 2MB of mixed content is considered
654
# full. So check to see if this block contains mixed content, and
655
# set the threshold appropriately.
657
for factory in self._factories:
658
prefix = factory.key[:-1]
659
if common_prefix is None:
660
common_prefix = prefix
661
elif prefix != common_prefix:
662
# Mixed content, check the size appropriately
663
if block_size >= self._full_enough_mixed_block_size:
666
# The content failed both the mixed check and the single-content check
667
# so obviously it is not fully utilized
668
# TODO: there is one other constraint that isn't being checked
669
# namely, that the entries in the block are in the appropriate
670
# order. For example, you could insert the entries in exactly
671
# reverse groupcompress order, and we would think that is ok.
672
# (all the right objects are in one group, and it is fully
673
# utilized, etc.) For now, we assume that case is rare,
674
# especially since we should always fetch in 'groupcompress'
678
def _check_rebuild_block(self):
679
action, last_byte_used, total_bytes_used = self._check_rebuild_action()
683
self._trim_block(last_byte_used)
684
elif action == 'rebuild':
685
self._rebuild_block()
687
raise ValueError('unknown rebuild action: %r' % (action,))
689
def _wire_bytes(self):
690
"""Return a byte stream suitable for transmitting over the wire."""
691
self._check_rebuild_block()
692
# The outer block starts with:
693
# 'groupcompress-block\n'
694
# <length of compressed key info>\n
695
# <length of uncompressed info>\n
696
# <length of gc block>\n
699
lines = ['groupcompress-block\n']
700
# The minimal info we need is the key, the start offset, and the
701
# parents. The length and type are encoded in the record itself.
702
# However, passing in the other bits makes it easier. The list of
703
# keys, and the start offset, the length
705
# 1 line with parents, '' for ()
706
# 1 line for start offset
707
# 1 line for end byte
709
for factory in self._factories:
710
key_bytes = '\x00'.join(factory.key)
711
parents = factory.parents
713
parent_bytes = 'None:'
715
parent_bytes = '\t'.join('\x00'.join(key) for key in parents)
716
record_header = '%s\n%s\n%d\n%d\n' % (
717
key_bytes, parent_bytes, factory._start, factory._end)
718
header_lines.append(record_header)
719
# TODO: Can we break the refcycle at this point and set
720
# factory._manager = None?
721
header_bytes = ''.join(header_lines)
723
header_bytes_len = len(header_bytes)
724
z_header_bytes = zlib.compress(header_bytes)
726
z_header_bytes_len = len(z_header_bytes)
727
block_bytes_len, block_chunks = self._block.to_chunks()
728
lines.append('%d\n%d\n%d\n' % (z_header_bytes_len, header_bytes_len,
730
lines.append(z_header_bytes)
731
lines.extend(block_chunks)
732
del z_header_bytes, block_chunks
733
# TODO: This is a point where we will double the memory consumption. To
734
# avoid this, we probably have to switch to a 'chunked' api
735
return ''.join(lines)
738
def from_bytes(cls, bytes):
739
# TODO: This does extra string copying, probably better to do it a
740
# different way. At a minimum this creates 2 copies of the
742
(storage_kind, z_header_len, header_len,
743
block_len, rest) = bytes.split('\n', 4)
745
if storage_kind != 'groupcompress-block':
746
raise ValueError('Unknown storage kind: %s' % (storage_kind,))
747
z_header_len = int(z_header_len)
748
if len(rest) < z_header_len:
749
raise ValueError('Compressed header len shorter than all bytes')
750
z_header = rest[:z_header_len]
751
header_len = int(header_len)
752
header = zlib.decompress(z_header)
753
if len(header) != header_len:
754
raise ValueError('invalid length for decompressed bytes')
756
block_len = int(block_len)
757
if len(rest) != z_header_len + block_len:
758
raise ValueError('Invalid length for block')
759
block_bytes = rest[z_header_len:]
761
# So now we have a valid GCB, we just need to parse the factories that
763
header_lines = header.split('\n')
765
last = header_lines.pop()
767
raise ValueError('header lines did not end with a trailing'
769
if len(header_lines) % 4 != 0:
770
raise ValueError('The header was not an even multiple of 4 lines')
771
block = GroupCompressBlock.from_bytes(block_bytes)
774
for start in range(0, len(header_lines), 4):
776
key = tuple(header_lines[start].split('\x00'))
777
parents_line = header_lines[start+1]
778
if parents_line == 'None:':
781
parents = tuple([tuple(segment.split('\x00'))
782
for segment in parents_line.split('\t')
784
start_offset = int(header_lines[start+2])
785
end_offset = int(header_lines[start+3])
786
result.add_factory(key, parents, start_offset, end_offset)
790
def network_block_to_records(storage_kind, bytes, line_end):
791
if storage_kind != 'groupcompress-block':
792
raise ValueError('Unknown storage kind: %s' % (storage_kind,))
793
manager = _LazyGroupContentManager.from_bytes(bytes)
794
return manager.get_record_stream()
797
class _CommonGroupCompressor(object):
799
def __init__(self, settings=None):
800
"""Create a GroupCompressor."""
805
self.labels_deltas = {}
806
self._delta_index = None # Set by the children
807
self._block = GroupCompressBlock()
811
self._settings = settings
813
def compress(self, key, bytes, expected_sha, nostore_sha=None, soft=False):
814
"""Compress lines with label key.
816
:param key: A key tuple. It is stored in the output
817
for identification of the text during decompression. If the last
818
element is 'None' it is replaced with the sha1 of the text -
820
:param bytes: The bytes to be compressed
821
:param expected_sha: If non-None, the sha the lines are believed to
822
have. During compression the sha is calculated; a mismatch will
824
:param nostore_sha: If the computed sha1 sum matches, we will raise
825
ExistingContent rather than adding the text.
826
:param soft: Do a 'soft' compression. This means that we require larger
827
ranges to match to be considered for a copy command.
829
:return: The sha1 of lines, the start and end offsets in the delta, and
830
the type ('fulltext' or 'delta').
832
:seealso VersionedFiles.add_lines:
834
if not bytes: # empty, like a dir entry, etc
835
if nostore_sha == _null_sha1:
836
raise errors.ExistingContent()
837
return _null_sha1, 0, 0, 'fulltext'
838
# we assume someone knew what they were doing when they passed it in
839
if expected_sha is not None:
842
sha1 = osutils.sha_string(bytes)
843
if nostore_sha is not None:
844
if sha1 == nostore_sha:
845
raise errors.ExistingContent()
847
key = key[:-1] + ('sha1:' + sha1,)
849
start, end, type = self._compress(key, bytes, len(bytes) / 2, soft)
850
return sha1, start, end, type
852
def _compress(self, key, bytes, max_delta_size, soft=False):
853
"""Compress lines with label key.
855
:param key: A key tuple. It is stored in the output for identification
856
of the text during decompression.
858
:param bytes: The bytes to be compressed
860
:param max_delta_size: The size above which we issue a fulltext instead
863
:param soft: Do a 'soft' compression. This means that we require larger
864
ranges to match to be considered for a copy command.
866
:return: The sha1 of lines, the start and end offsets in the delta, and
867
the type ('fulltext' or 'delta').
869
raise NotImplementedError(self._compress)
871
def extract(self, key):
872
"""Extract a key previously added to the compressor.
874
:param key: The key to extract.
875
:return: An iterable over bytes and the sha1.
877
(start_byte, start_chunk, end_byte, end_chunk) = self.labels_deltas[key]
878
delta_chunks = self.chunks[start_chunk:end_chunk]
879
stored_bytes = ''.join(delta_chunks)
880
if stored_bytes[0] == 'f':
881
fulltext_len, offset = decode_base128_int(stored_bytes[1:10])
882
data_len = fulltext_len + 1 + offset
883
if data_len != len(stored_bytes):
884
raise ValueError('Index claimed fulltext len, but stored bytes'
886
% (len(stored_bytes), data_len))
887
bytes = stored_bytes[offset + 1:]
889
# XXX: This is inefficient at best
890
source = ''.join(self.chunks[:start_chunk])
891
if stored_bytes[0] != 'd':
892
raise ValueError('Unknown content kind, bytes claim %s'
893
% (stored_bytes[0],))
894
delta_len, offset = decode_base128_int(stored_bytes[1:10])
895
data_len = delta_len + 1 + offset
896
if data_len != len(stored_bytes):
897
raise ValueError('Index claimed delta len, but stored bytes'
899
% (len(stored_bytes), data_len))
900
bytes = apply_delta(source, stored_bytes[offset + 1:])
901
bytes_sha1 = osutils.sha_string(bytes)
902
return bytes, bytes_sha1
905
"""Finish this group, creating a formatted stream.
907
After calling this, the compressor should no longer be used
909
self._block.set_chunked_content(self.chunks, self.endpoint)
911
self._delta_index = None
915
"""Call this if you want to 'revoke' the last compression.
917
After this, the data structures will be rolled back, but you cannot do
920
self._delta_index = None
921
del self.chunks[self._last[0]:]
922
self.endpoint = self._last[1]
926
"""Return the overall compression ratio."""
927
return float(self.input_bytes) / float(self.endpoint)
930
class PythonGroupCompressor(_CommonGroupCompressor):
932
def __init__(self, settings=None):
933
"""Create a GroupCompressor.
935
Used only if the pyrex version is not available.
937
super(PythonGroupCompressor, self).__init__(settings)
938
self._delta_index = LinesDeltaIndex([])
939
# The actual content is managed by LinesDeltaIndex
940
self.chunks = self._delta_index.lines
942
def _compress(self, key, bytes, max_delta_size, soft=False):
943
"""see _CommonGroupCompressor._compress"""
944
input_len = len(bytes)
945
new_lines = osutils.split_lines(bytes)
946
out_lines, index_lines = self._delta_index.make_delta(
947
new_lines, bytes_length=input_len, soft=soft)
948
delta_length = sum(map(len, out_lines))
949
if delta_length > max_delta_size:
950
# The delta is longer than the fulltext, insert a fulltext
952
out_lines = ['f', encode_base128_int(input_len)]
953
out_lines.extend(new_lines)
954
index_lines = [False, False]
955
index_lines.extend([True] * len(new_lines))
957
# this is a worthy delta, output it
960
# Update the delta_length to include those two encoded integers
961
out_lines[1] = encode_base128_int(delta_length)
963
start = self.endpoint
964
chunk_start = len(self.chunks)
965
self._last = (chunk_start, self.endpoint)
966
self._delta_index.extend_lines(out_lines, index_lines)
967
self.endpoint = self._delta_index.endpoint
968
self.input_bytes += input_len
969
chunk_end = len(self.chunks)
970
self.labels_deltas[key] = (start, chunk_start,
971
self.endpoint, chunk_end)
972
return start, self.endpoint, type
975
class PyrexGroupCompressor(_CommonGroupCompressor):
976
"""Produce a serialised group of compressed texts.
978
It contains code very similar to SequenceMatcher because of having a similar
979
task. However some key differences apply:
981
* there is no junk, we want a minimal edit not a human readable diff.
982
* we don't filter very common lines (because we don't know where a good
983
range will start, and after the first text we want to be emitting minmal
985
* we chain the left side, not the right side
986
* we incrementally update the adjacency matrix as new lines are provided.
987
* we look for matches in all of the left side, so the routine which does
988
the analagous task of find_longest_match does not need to filter on the
992
def __init__(self, settings=None):
993
super(PyrexGroupCompressor, self).__init__(settings)
994
max_bytes_to_index = self._settings.get('max_bytes_to_index', 0)
995
self._delta_index = DeltaIndex(max_bytes_to_index=max_bytes_to_index)
997
def _compress(self, key, bytes, max_delta_size, soft=False):
998
"""see _CommonGroupCompressor._compress"""
999
input_len = len(bytes)
1000
# By having action/label/sha1/len, we can parse the group if the index
1001
# was ever destroyed, we have the key in 'label', we know the final
1002
# bytes are valid from sha1, and we know where to find the end of this
1003
# record because of 'len'. (the delta record itself will store the
1004
# total length for the expanded record)
1005
# 'len: %d\n' costs approximately 1% increase in total data
1006
# Having the labels at all costs us 9-10% increase, 38% increase for
1007
# inventory pages, and 5.8% increase for text pages
1008
# new_chunks = ['label:%s\nsha1:%s\n' % (label, sha1)]
1009
if self._delta_index._source_offset != self.endpoint:
1010
raise AssertionError('_source_offset != endpoint'
1011
' somehow the DeltaIndex got out of sync with'
1012
' the output lines')
1013
delta = self._delta_index.make_delta(bytes, max_delta_size)
1016
enc_length = encode_base128_int(len(bytes))
1017
len_mini_header = 1 + len(enc_length)
1018
self._delta_index.add_source(bytes, len_mini_header)
1019
new_chunks = ['f', enc_length, bytes]
1022
enc_length = encode_base128_int(len(delta))
1023
len_mini_header = 1 + len(enc_length)
1024
new_chunks = ['d', enc_length, delta]
1025
self._delta_index.add_delta_source(delta, len_mini_header)
1027
start = self.endpoint
1028
chunk_start = len(self.chunks)
1029
# Now output these bytes
1030
self._output_chunks(new_chunks)
1031
self.input_bytes += input_len
1032
chunk_end = len(self.chunks)
1033
self.labels_deltas[key] = (start, chunk_start,
1034
self.endpoint, chunk_end)
1035
if not self._delta_index._source_offset == self.endpoint:
1036
raise AssertionError('the delta index is out of sync'
1037
'with the output lines %s != %s'
1038
% (self._delta_index._source_offset, self.endpoint))
1039
return start, self.endpoint, type
1041
def _output_chunks(self, new_chunks):
1042
"""Output some chunks.
1044
:param new_chunks: The chunks to output.
1046
self._last = (len(self.chunks), self.endpoint)
1047
endpoint = self.endpoint
1048
self.chunks.extend(new_chunks)
1049
endpoint += sum(map(len, new_chunks))
1050
self.endpoint = endpoint
1053
def make_pack_factory(graph, delta, keylength, inconsistency_fatal=True):
1054
"""Create a factory for creating a pack based groupcompress.
1056
This is only functional enough to run interface tests, it doesn't try to
1057
provide a full pack environment.
1059
:param graph: Store a graph.
1060
:param delta: Delta compress contents.
1061
:param keylength: How long should keys be.
1063
def factory(transport):
1068
graph_index = BTreeBuilder(reference_lists=ref_length,
1069
key_elements=keylength)
1070
stream = transport.open_write_stream('newpack')
1071
writer = pack.ContainerWriter(stream.write)
1073
index = _GCGraphIndex(graph_index, lambda:True, parents=parents,
1074
add_callback=graph_index.add_nodes,
1075
inconsistency_fatal=inconsistency_fatal)
1076
access = pack_repo._DirectPackAccess({})
1077
access.set_writer(writer, graph_index, (transport, 'newpack'))
1078
result = GroupCompressVersionedFiles(index, access, delta)
1079
result.stream = stream
1080
result.writer = writer
1085
def cleanup_pack_group(versioned_files):
1086
versioned_files.writer.end()
1087
versioned_files.stream.close()
1090
class _BatchingBlockFetcher(object):
1091
"""Fetch group compress blocks in batches.
1093
:ivar total_bytes: int of expected number of bytes needed to fetch the
1094
currently pending batch.
1097
def __init__(self, gcvf, locations, get_compressor_settings=None):
1099
self.locations = locations
1101
self.batch_memos = {}
1102
self.memos_to_get = []
1103
self.total_bytes = 0
1104
self.last_read_memo = None
1106
self._get_compressor_settings = get_compressor_settings
1108
def add_key(self, key):
1109
"""Add another to key to fetch.
1111
:return: The estimated number of bytes needed to fetch the batch so
1114
self.keys.append(key)
1115
index_memo, _, _, _ = self.locations[key]
1116
read_memo = index_memo[0:3]
1117
# Three possibilities for this read_memo:
1118
# - it's already part of this batch; or
1119
# - it's not yet part of this batch, but is already cached; or
1120
# - it's not yet part of this batch and will need to be fetched.
1121
if read_memo in self.batch_memos:
1122
# This read memo is already in this batch.
1123
return self.total_bytes
1125
cached_block = self.gcvf._group_cache[read_memo]
1127
# This read memo is new to this batch, and the data isn't cached
1129
self.batch_memos[read_memo] = None
1130
self.memos_to_get.append(read_memo)
1131
byte_length = read_memo[2]
1132
self.total_bytes += byte_length
1134
# This read memo is new to this batch, but cached.
1135
# Keep a reference to the cached block in batch_memos because it's
1136
# certain that we'll use it when this batch is processed, but
1137
# there's a risk that it would fall out of _group_cache between now
1139
self.batch_memos[read_memo] = cached_block
1140
return self.total_bytes
1142
def _flush_manager(self):
1143
if self.manager is not None:
1144
for factory in self.manager.get_record_stream():
1147
self.last_read_memo = None
1149
def yield_factories(self, full_flush=False):
1150
"""Yield factories for keys added since the last yield. They will be
1151
returned in the order they were added via add_key.
1153
:param full_flush: by default, some results may not be returned in case
1154
they can be part of the next batch. If full_flush is True, then
1155
all results are returned.
1157
if self.manager is None and not self.keys:
1159
# Fetch all memos in this batch.
1160
blocks = self.gcvf._get_blocks(self.memos_to_get)
1161
# Turn blocks into factories and yield them.
1162
memos_to_get_stack = list(self.memos_to_get)
1163
memos_to_get_stack.reverse()
1164
for key in self.keys:
1165
index_memo, _, parents, _ = self.locations[key]
1166
read_memo = index_memo[:3]
1167
if self.last_read_memo != read_memo:
1168
# We are starting a new block. If we have a
1169
# manager, we have found everything that fits for
1170
# now, so yield records
1171
for factory in self._flush_manager():
1173
# Now start a new manager.
1174
if memos_to_get_stack and memos_to_get_stack[-1] == read_memo:
1175
# The next block from _get_blocks will be the block we
1177
block_read_memo, block = next(blocks)
1178
if block_read_memo != read_memo:
1179
raise AssertionError(
1180
"block_read_memo out of sync with read_memo"
1181
"(%r != %r)" % (block_read_memo, read_memo))
1182
self.batch_memos[read_memo] = block
1183
memos_to_get_stack.pop()
1185
block = self.batch_memos[read_memo]
1186
self.manager = _LazyGroupContentManager(block,
1187
get_compressor_settings=self._get_compressor_settings)
1188
self.last_read_memo = read_memo
1189
start, end = index_memo[3:5]
1190
self.manager.add_factory(key, parents, start, end)
1192
for factory in self._flush_manager():
1195
self.batch_memos.clear()
1196
del self.memos_to_get[:]
1197
self.total_bytes = 0
1200
class GroupCompressVersionedFiles(VersionedFilesWithFallbacks):
1201
"""A group-compress based VersionedFiles implementation."""
1203
# This controls how the GroupCompress DeltaIndex works. Basically, we
1204
# compute hash pointers into the source blocks (so hash(text) => text).
1205
# However each of these references costs some memory in trade against a
1206
# more accurate match result. For very large files, they either are
1207
# pre-compressed and change in bulk whenever they change, or change in just
1208
# local blocks. Either way, 'improved resolution' is not very helpful,
1209
# versus running out of memory trying to track everything. The default max
1210
# gives 100% sampling of a 1MB file.
1211
_DEFAULT_MAX_BYTES_TO_INDEX = 1024 * 1024
1212
_DEFAULT_COMPRESSOR_SETTINGS = {'max_bytes_to_index':
1213
_DEFAULT_MAX_BYTES_TO_INDEX}
1215
def __init__(self, index, access, delta=True, _unadded_refs=None,
1217
"""Create a GroupCompressVersionedFiles object.
1219
:param index: The index object storing access and graph data.
1220
:param access: The access object storing raw data.
1221
:param delta: Whether to delta compress or just entropy compress.
1222
:param _unadded_refs: private parameter, don't use.
1223
:param _group_cache: private parameter, don't use.
1226
self._access = access
1228
if _unadded_refs is None:
1230
self._unadded_refs = _unadded_refs
1231
if _group_cache is None:
1232
_group_cache = LRUSizeCache(max_size=50*1024*1024)
1233
self._group_cache = _group_cache
1234
self._immediate_fallback_vfs = []
1235
self._max_bytes_to_index = None
1237
def without_fallbacks(self):
1238
"""Return a clone of this object without any fallbacks configured."""
1239
return GroupCompressVersionedFiles(self._index, self._access,
1240
self._delta, _unadded_refs=dict(self._unadded_refs),
1241
_group_cache=self._group_cache)
1243
def add_lines(self, key, parents, lines, parent_texts=None,
1244
left_matching_blocks=None, nostore_sha=None, random_id=False,
1245
check_content=True):
1246
"""Add a text to the store.
1248
:param key: The key tuple of the text to add.
1249
:param parents: The parents key tuples of the text to add.
1250
:param lines: A list of lines. Each line must be a bytestring. And all
1251
of them except the last must be terminated with \\n and contain no
1252
other \\n's. The last line may either contain no \\n's or a single
1253
terminating \\n. If the lines list does meet this constraint the
1254
add routine may error or may succeed - but you will be unable to
1255
read the data back accurately. (Checking the lines have been split
1256
correctly is expensive and extremely unlikely to catch bugs so it
1257
is not done at runtime unless check_content is True.)
1258
:param parent_texts: An optional dictionary containing the opaque
1259
representations of some or all of the parents of version_id to
1260
allow delta optimisations. VERY IMPORTANT: the texts must be those
1261
returned by add_lines or data corruption can be caused.
1262
:param left_matching_blocks: a hint about which areas are common
1263
between the text and its left-hand-parent. The format is
1264
the SequenceMatcher.get_matching_blocks format.
1265
:param nostore_sha: Raise ExistingContent and do not add the lines to
1266
the versioned file if the digest of the lines matches this.
1267
:param random_id: If True a random id has been selected rather than
1268
an id determined by some deterministic process such as a converter
1269
from a foreign VCS. When True the backend may choose not to check
1270
for uniqueness of the resulting key within the versioned file, so
1271
this should only be done when the result is expected to be unique
1273
:param check_content: If True, the lines supplied are verified to be
1274
bytestrings that are correctly formed lines.
1275
:return: The text sha1, the number of bytes in the text, and an opaque
1276
representation of the inserted version which can be provided
1277
back to future add_lines calls in the parent_texts dictionary.
1279
self._index._check_write_ok()
1280
self._check_add(key, lines, random_id, check_content)
1282
# The caller might pass None if there is no graph data, but kndx
1283
# indexes can't directly store that, so we give them
1284
# an empty tuple instead.
1286
# double handling for now. Make it work until then.
1287
length = sum(map(len, lines))
1288
record = ChunkedContentFactory(key, parents, None, lines)
1289
sha1 = list(self._insert_record_stream([record], random_id=random_id,
1290
nostore_sha=nostore_sha))[0]
1291
return sha1, length, None
1293
def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
1294
"""See VersionedFiles._add_text()."""
1295
self._index._check_write_ok()
1296
self._check_add(key, None, random_id, check_content=False)
1297
if text.__class__ is not str:
1298
raise errors.BzrBadParameterUnicode("text")
1300
# The caller might pass None if there is no graph data, but kndx
1301
# indexes can't directly store that, so we give them
1302
# an empty tuple instead.
1304
# double handling for now. Make it work until then.
1306
record = FulltextContentFactory(key, parents, None, text)
1307
sha1 = list(self._insert_record_stream([record], random_id=random_id,
1308
nostore_sha=nostore_sha))[0]
1309
return sha1, length, None
1311
def add_fallback_versioned_files(self, a_versioned_files):
1312
"""Add a source of texts for texts not present in this knit.
1314
:param a_versioned_files: A VersionedFiles object.
1316
self._immediate_fallback_vfs.append(a_versioned_files)
1318
def annotate(self, key):
1319
"""See VersionedFiles.annotate."""
1320
ann = annotate.Annotator(self)
1321
return ann.annotate_flat(key)
1323
def get_annotator(self):
1324
return annotate.Annotator(self)
1326
def check(self, progress_bar=None, keys=None):
1327
"""See VersionedFiles.check()."""
1330
for record in self.get_record_stream(keys, 'unordered', True):
1331
record.get_bytes_as('fulltext')
1333
return self.get_record_stream(keys, 'unordered', True)
1335
def clear_cache(self):
1336
"""See VersionedFiles.clear_cache()"""
1337
self._group_cache.clear()
1338
self._index._graph_index.clear_cache()
1339
self._index._int_cache.clear()
1341
def _check_add(self, key, lines, random_id, check_content):
1342
"""check that version_id and lines are safe to add."""
1343
version_id = key[-1]
1344
if version_id is not None:
1345
if osutils.contains_whitespace(version_id):
1346
raise errors.InvalidRevisionId(version_id, self)
1347
self.check_not_reserved_id(version_id)
1348
# TODO: If random_id==False and the key is already present, we should
1349
# probably check that the existing content is identical to what is
1350
# being inserted, and otherwise raise an exception. This would make
1351
# the bundle code simpler.
1353
self._check_lines_not_unicode(lines)
1354
self._check_lines_are_lines(lines)
1356
def get_parent_map(self, keys):
1357
"""Get a map of the graph parents of keys.
1359
:param keys: The keys to look up parents for.
1360
:return: A mapping from keys to parents. Absent keys are absent from
1363
return self._get_parent_map_with_sources(keys)[0]
1365
def _get_parent_map_with_sources(self, keys):
1366
"""Get a map of the parents of keys.
1368
:param keys: The keys to look up parents for.
1369
:return: A tuple. The first element is a mapping from keys to parents.
1370
Absent keys are absent from the mapping. The second element is a
1371
list with the locations each key was found in. The first element
1372
is the in-this-knit parents, the second the first fallback source,
1376
sources = [self._index] + self._immediate_fallback_vfs
1379
for source in sources:
1382
new_result = source.get_parent_map(missing)
1383
source_results.append(new_result)
1384
result.update(new_result)
1385
missing.difference_update(set(new_result))
1386
return result, source_results
1388
def _get_blocks(self, read_memos):
1389
"""Get GroupCompressBlocks for the given read_memos.
1391
:returns: a series of (read_memo, block) pairs, in the order they were
1395
for read_memo in read_memos:
1397
block = self._group_cache[read_memo]
1401
cached[read_memo] = block
1403
not_cached_seen = set()
1404
for read_memo in read_memos:
1405
if read_memo in cached:
1406
# Don't fetch what we already have
1408
if read_memo in not_cached_seen:
1409
# Don't try to fetch the same data twice
1411
not_cached.append(read_memo)
1412
not_cached_seen.add(read_memo)
1413
raw_records = self._access.get_raw_records(not_cached)
1414
for read_memo in read_memos:
1416
yield read_memo, cached[read_memo]
1418
# Read the block, and cache it.
1419
zdata = next(raw_records)
1420
block = GroupCompressBlock.from_bytes(zdata)
1421
self._group_cache[read_memo] = block
1422
cached[read_memo] = block
1423
yield read_memo, block
1425
def get_missing_compression_parent_keys(self):
1426
"""Return the keys of missing compression parents.
1428
Missing compression parents occur when a record stream was missing
1429
basis texts, or a index was scanned that had missing basis texts.
1431
# GroupCompress cannot currently reference texts that are not in the
1432
# group, so this is valid for now
1435
def get_record_stream(self, keys, ordering, include_delta_closure):
1436
"""Get a stream of records for keys.
1438
:param keys: The keys to include.
1439
:param ordering: Either 'unordered' or 'topological'. A topologically
1440
sorted stream has compression parents strictly before their
1442
:param include_delta_closure: If True then the closure across any
1443
compression parents will be included (in the opaque data).
1444
:return: An iterator of ContentFactory objects, each of which is only
1445
valid until the iterator is advanced.
1447
# keys might be a generator
1448
orig_keys = list(keys)
1452
if (not self._index.has_graph
1453
and ordering in ('topological', 'groupcompress')):
1454
# Cannot topological order when no graph has been stored.
1455
# but we allow 'as-requested' or 'unordered'
1456
ordering = 'unordered'
1458
remaining_keys = keys
1461
keys = set(remaining_keys)
1462
for content_factory in self._get_remaining_record_stream(keys,
1463
orig_keys, ordering, include_delta_closure):
1464
remaining_keys.discard(content_factory.key)
1465
yield content_factory
1467
except errors.RetryWithNewPacks as e:
1468
self._access.reload_or_raise(e)
1470
def _find_from_fallback(self, missing):
1471
"""Find whatever keys you can from the fallbacks.
1473
:param missing: A set of missing keys. This set will be mutated as keys
1474
are found from a fallback_vfs
1475
:return: (parent_map, key_to_source_map, source_results)
1476
parent_map the overall key => parent_keys
1477
key_to_source_map a dict from {key: source}
1478
source_results a list of (source: keys)
1481
key_to_source_map = {}
1483
for source in self._immediate_fallback_vfs:
1486
source_parents = source.get_parent_map(missing)
1487
parent_map.update(source_parents)
1488
source_parents = list(source_parents)
1489
source_results.append((source, source_parents))
1490
key_to_source_map.update((key, source) for key in source_parents)
1491
missing.difference_update(source_parents)
1492
return parent_map, key_to_source_map, source_results
1494
def _get_ordered_source_keys(self, ordering, parent_map, key_to_source_map):
1495
"""Get the (source, [keys]) list.
1497
The returned objects should be in the order defined by 'ordering',
1498
which can weave between different sources.
1500
:param ordering: Must be one of 'topological' or 'groupcompress'
1501
:return: List of [(source, [keys])] tuples, such that all keys are in
1502
the defined order, regardless of source.
1504
if ordering == 'topological':
1505
present_keys = tsort.topo_sort(parent_map)
1507
# ordering == 'groupcompress'
1508
# XXX: This only optimizes for the target ordering. We may need
1509
# to balance that with the time it takes to extract
1510
# ordering, by somehow grouping based on
1511
# locations[key][0:3]
1512
present_keys = sort_gc_optimal(parent_map)
1513
# Now group by source:
1515
current_source = None
1516
for key in present_keys:
1517
source = key_to_source_map.get(key, self)
1518
if source is not current_source:
1519
source_keys.append((source, []))
1520
current_source = source
1521
source_keys[-1][1].append(key)
1524
def _get_as_requested_source_keys(self, orig_keys, locations, unadded_keys,
1527
current_source = None
1528
for key in orig_keys:
1529
if key in locations or key in unadded_keys:
1531
elif key in key_to_source_map:
1532
source = key_to_source_map[key]
1535
if source is not current_source:
1536
source_keys.append((source, []))
1537
current_source = source
1538
source_keys[-1][1].append(key)
1541
def _get_io_ordered_source_keys(self, locations, unadded_keys,
1544
# This is the group the bytes are stored in, followed by the
1545
# location in the group
1546
return locations[key][0]
1547
# We don't have an ordering for keys in the in-memory object, but
1548
# lets process the in-memory ones first.
1549
present_keys = list(unadded_keys)
1550
present_keys.extend(sorted(locations, key=get_group))
1551
# Now grab all of the ones from other sources
1552
source_keys = [(self, present_keys)]
1553
source_keys.extend(source_result)
1556
def _get_remaining_record_stream(self, keys, orig_keys, ordering,
1557
include_delta_closure):
1558
"""Get a stream of records for keys.
1560
:param keys: The keys to include.
1561
:param ordering: one of 'unordered', 'topological', 'groupcompress' or
1563
:param include_delta_closure: If True then the closure across any
1564
compression parents will be included (in the opaque data).
1565
:return: An iterator of ContentFactory objects, each of which is only
1566
valid until the iterator is advanced.
1569
locations = self._index.get_build_details(keys)
1570
unadded_keys = set(self._unadded_refs).intersection(keys)
1571
missing = keys.difference(locations)
1572
missing.difference_update(unadded_keys)
1573
(fallback_parent_map, key_to_source_map,
1574
source_result) = self._find_from_fallback(missing)
1575
if ordering in ('topological', 'groupcompress'):
1576
# would be better to not globally sort initially but instead
1577
# start with one key, recurse to its oldest parent, then grab
1578
# everything in the same group, etc.
1579
parent_map = dict((key, details[2]) for key, details in
1580
viewitems(locations))
1581
for key in unadded_keys:
1582
parent_map[key] = self._unadded_refs[key]
1583
parent_map.update(fallback_parent_map)
1584
source_keys = self._get_ordered_source_keys(ordering, parent_map,
1586
elif ordering == 'as-requested':
1587
source_keys = self._get_as_requested_source_keys(orig_keys,
1588
locations, unadded_keys, key_to_source_map)
1590
# We want to yield the keys in a semi-optimal (read-wise) ordering.
1591
# Otherwise we thrash the _group_cache and destroy performance
1592
source_keys = self._get_io_ordered_source_keys(locations,
1593
unadded_keys, source_result)
1595
yield AbsentContentFactory(key)
1596
# Batch up as many keys as we can until either:
1597
# - we encounter an unadded ref, or
1598
# - we run out of keys, or
1599
# - the total bytes to retrieve for this batch > BATCH_SIZE
1600
batcher = _BatchingBlockFetcher(self, locations,
1601
get_compressor_settings=self._get_compressor_settings)
1602
for source, keys in source_keys:
1605
if key in self._unadded_refs:
1606
# Flush batch, then yield unadded ref from
1608
for factory in batcher.yield_factories(full_flush=True):
1610
bytes, sha1 = self._compressor.extract(key)
1611
parents = self._unadded_refs[key]
1612
yield FulltextContentFactory(key, parents, sha1, bytes)
1614
if batcher.add_key(key) > BATCH_SIZE:
1615
# Ok, this batch is big enough. Yield some results.
1616
for factory in batcher.yield_factories():
1619
for factory in batcher.yield_factories(full_flush=True):
1621
for record in source.get_record_stream(keys, ordering,
1622
include_delta_closure):
1624
for factory in batcher.yield_factories(full_flush=True):
1627
def get_sha1s(self, keys):
1628
"""See VersionedFiles.get_sha1s()."""
1630
for record in self.get_record_stream(keys, 'unordered', True):
1631
if record.sha1 != None:
1632
result[record.key] = record.sha1
1634
if record.storage_kind != 'absent':
1635
result[record.key] = osutils.sha_string(
1636
record.get_bytes_as('fulltext'))
1639
def insert_record_stream(self, stream):
1640
"""Insert a record stream into this container.
1642
:param stream: A stream of records to insert.
1644
:seealso VersionedFiles.get_record_stream:
1646
# XXX: Setting random_id=True makes
1647
# test_insert_record_stream_existing_keys fail for groupcompress and
1648
# groupcompress-nograph, this needs to be revisited while addressing
1649
# 'bzr branch' performance issues.
1650
for _ in self._insert_record_stream(stream, random_id=False):
1653
def _get_compressor_settings(self):
1654
if self._max_bytes_to_index is None:
1655
# TODO: VersionedFiles don't know about their containing
1656
# repository, so they don't have much of an idea about their
1657
# location. So for now, this is only a global option.
1658
c = config.GlobalConfig()
1659
val = c.get_user_option('bzr.groupcompress.max_bytes_to_index')
1663
except ValueError as e:
1664
trace.warning('Value for '
1665
'"bzr.groupcompress.max_bytes_to_index"'
1666
' %r is not an integer'
1670
val = self._DEFAULT_MAX_BYTES_TO_INDEX
1671
self._max_bytes_to_index = val
1672
return {'max_bytes_to_index': self._max_bytes_to_index}
1674
def _make_group_compressor(self):
1675
return GroupCompressor(self._get_compressor_settings())
1677
def _insert_record_stream(self, stream, random_id=False, nostore_sha=None,
1679
"""Internal core to insert a record stream into this container.
1681
This helper function has a different interface than insert_record_stream
1682
to allow add_lines to be minimal, but still return the needed data.
1684
:param stream: A stream of records to insert.
1685
:param nostore_sha: If the sha1 of a given text matches nostore_sha,
1686
raise ExistingContent, rather than committing the new text.
1687
:param reuse_blocks: If the source is streaming from
1688
groupcompress-blocks, just insert the blocks as-is, rather than
1689
expanding the texts and inserting again.
1690
:return: An iterator over the sha1 of the inserted records.
1691
:seealso insert_record_stream:
1695
def get_adapter(adapter_key):
1697
return adapters[adapter_key]
1699
adapter_factory = adapter_registry.get(adapter_key)
1700
adapter = adapter_factory(self)
1701
adapters[adapter_key] = adapter
1703
# This will go up to fulltexts for gc to gc fetching, which isn't
1705
self._compressor = self._make_group_compressor()
1706
self._unadded_refs = {}
1709
bytes_len, chunks = self._compressor.flush().to_chunks()
1710
self._compressor = self._make_group_compressor()
1711
# Note: At this point we still have 1 copy of the fulltext (in
1712
# record and the var 'bytes'), and this generates 2 copies of
1713
# the compressed text (one for bytes, one in chunks)
1714
# TODO: Push 'chunks' down into the _access api, so that we don't
1715
# have to double compressed memory here
1716
# TODO: Figure out how to indicate that we would be happy to free
1717
# the fulltext content at this point. Note that sometimes we
1718
# will want it later (streaming CHK pages), but most of the
1719
# time we won't (everything else)
1720
bytes = ''.join(chunks)
1722
index, start, length = self._access.add_raw_records(
1723
[(None, len(bytes))], bytes)[0]
1725
for key, reads, refs in keys_to_add:
1726
nodes.append((key, "%d %d %s" % (start, length, reads), refs))
1727
self._index.add_records(nodes, random_id=random_id)
1728
self._unadded_refs = {}
1732
max_fulltext_len = 0
1733
max_fulltext_prefix = None
1734
insert_manager = None
1737
# XXX: TODO: remove this, it is just for safety checking for now
1738
inserted_keys = set()
1739
reuse_this_block = reuse_blocks
1740
for record in stream:
1741
# Raise an error when a record is missing.
1742
if record.storage_kind == 'absent':
1743
raise errors.RevisionNotPresent(record.key, self)
1745
if record.key in inserted_keys:
1746
trace.note(gettext('Insert claimed random_id=True,'
1747
' but then inserted %r two times'), record.key)
1749
inserted_keys.add(record.key)
1751
# If the reuse_blocks flag is set, check to see if we can just
1752
# copy a groupcompress block as-is.
1753
# We only check on the first record (groupcompress-block) not
1754
# on all of the (groupcompress-block-ref) entries.
1755
# The reuse_this_block flag is then kept for as long as
1756
if record.storage_kind == 'groupcompress-block':
1757
# Check to see if we really want to re-use this block
1758
insert_manager = record._manager
1759
reuse_this_block = insert_manager.check_is_well_utilized()
1761
reuse_this_block = False
1762
if reuse_this_block:
1763
# We still want to reuse this block
1764
if record.storage_kind == 'groupcompress-block':
1765
# Insert the raw block into the target repo
1766
insert_manager = record._manager
1767
bytes = record._manager._block.to_bytes()
1768
_, start, length = self._access.add_raw_records(
1769
[(None, len(bytes))], bytes)[0]
1772
block_length = length
1773
if record.storage_kind in ('groupcompress-block',
1774
'groupcompress-block-ref'):
1775
if insert_manager is None:
1776
raise AssertionError('No insert_manager set')
1777
if insert_manager is not record._manager:
1778
raise AssertionError('insert_manager does not match'
1779
' the current record, we cannot be positive'
1780
' that the appropriate content was inserted.'
1782
value = "%d %d %d %d" % (block_start, block_length,
1783
record._start, record._end)
1784
nodes = [(record.key, value, (record.parents,))]
1785
# TODO: Consider buffering up many nodes to be added, not
1786
# sure how much overhead this has, but we're seeing
1787
# ~23s / 120s in add_records calls
1788
self._index.add_records(nodes, random_id=random_id)
1791
bytes = record.get_bytes_as('fulltext')
1792
except errors.UnavailableRepresentation:
1793
adapter_key = record.storage_kind, 'fulltext'
1794
adapter = get_adapter(adapter_key)
1795
bytes = adapter.get_bytes(record)
1796
if len(record.key) > 1:
1797
prefix = record.key[0]
1798
soft = (prefix == last_prefix)
1802
if max_fulltext_len < len(bytes):
1803
max_fulltext_len = len(bytes)
1804
max_fulltext_prefix = prefix
1805
(found_sha1, start_point, end_point,
1806
type) = self._compressor.compress(record.key,
1807
bytes, record.sha1, soft=soft,
1808
nostore_sha=nostore_sha)
1809
# delta_ratio = float(len(bytes)) / (end_point - start_point)
1810
# Check if we want to continue to include that text
1811
if (prefix == max_fulltext_prefix
1812
and end_point < 2 * max_fulltext_len):
1813
# As long as we are on the same file_id, we will fill at least
1814
# 2 * max_fulltext_len
1815
start_new_block = False
1816
elif end_point > 4*1024*1024:
1817
start_new_block = True
1818
elif (prefix is not None and prefix != last_prefix
1819
and end_point > 2*1024*1024):
1820
start_new_block = True
1822
start_new_block = False
1823
last_prefix = prefix
1825
self._compressor.pop_last()
1827
max_fulltext_len = len(bytes)
1828
(found_sha1, start_point, end_point,
1829
type) = self._compressor.compress(record.key, bytes,
1831
if record.key[-1] is None:
1832
key = record.key[:-1] + ('sha1:' + found_sha1,)
1835
self._unadded_refs[key] = record.parents
1837
as_st = static_tuple.StaticTuple.from_sequence
1838
if record.parents is not None:
1839
parents = as_st([as_st(p) for p in record.parents])
1842
refs = static_tuple.StaticTuple(parents)
1843
keys_to_add.append((key, '%d %d' % (start_point, end_point), refs))
1844
if len(keys_to_add):
1846
self._compressor = None
1848
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1849
"""Iterate over the lines in the versioned files from keys.
1851
This may return lines from other keys. Each item the returned
1852
iterator yields is a tuple of a line and a text version that that line
1853
is present in (not introduced in).
1855
Ordering of results is in whatever order is most suitable for the
1856
underlying storage format.
1858
If a progress bar is supplied, it may be used to indicate progress.
1859
The caller is responsible for cleaning up progress bars (because this
1863
* Lines are normalised by the underlying store: they will all have \n
1865
* Lines are returned in arbitrary order.
1867
:return: An iterator over (line, key).
1871
# we don't care about inclusions, the caller cares.
1872
# but we need to setup a list of records to visit.
1873
# we need key, position, length
1874
for key_idx, record in enumerate(self.get_record_stream(keys,
1875
'unordered', True)):
1876
# XXX: todo - optimise to use less than full texts.
1879
pb.update('Walking content', key_idx, total)
1880
if record.storage_kind == 'absent':
1881
raise errors.RevisionNotPresent(key, self)
1882
lines = osutils.split_lines(record.get_bytes_as('fulltext'))
1886
pb.update('Walking content', total, total)
1889
"""See VersionedFiles.keys."""
1890
if 'evil' in debug.debug_flags:
1891
trace.mutter_callsite(2, "keys scales with size of history")
1892
sources = [self._index] + self._immediate_fallback_vfs
1894
for source in sources:
1895
result.update(source.keys())
1899
class _GCBuildDetails(object):
1900
"""A blob of data about the build details.
1902
This stores the minimal data, which then allows compatibility with the old
1903
api, without taking as much memory.
1906
__slots__ = ('_index', '_group_start', '_group_end', '_basis_end',
1907
'_delta_end', '_parents')
1910
compression_parent = None
1912
def __init__(self, parents, position_info):
1913
self._parents = parents
1914
(self._index, self._group_start, self._group_end, self._basis_end,
1915
self._delta_end) = position_info
1918
return '%s(%s, %s)' % (self.__class__.__name__,
1919
self.index_memo, self._parents)
1922
def index_memo(self):
1923
return (self._index, self._group_start, self._group_end,
1924
self._basis_end, self._delta_end)
1927
def record_details(self):
1928
return static_tuple.StaticTuple(self.method, None)
1930
def __getitem__(self, offset):
1931
"""Compatibility thunk to act like a tuple."""
1933
return self.index_memo
1935
return self.compression_parent # Always None
1937
return self._parents
1939
return self.record_details
1941
raise IndexError('offset out of range')
1947
class _GCGraphIndex(object):
1948
"""Mapper from GroupCompressVersionedFiles needs into GraphIndex storage."""
1950
def __init__(self, graph_index, is_locked, parents=True,
1951
add_callback=None, track_external_parent_refs=False,
1952
inconsistency_fatal=True, track_new_keys=False):
1953
"""Construct a _GCGraphIndex on a graph_index.
1955
:param graph_index: An implementation of breezy.index.GraphIndex.
1956
:param is_locked: A callback, returns True if the index is locked and
1958
:param parents: If True, record knits parents, if not do not record
1960
:param add_callback: If not None, allow additions to the index and call
1961
this callback with a list of added GraphIndex nodes:
1962
[(node, value, node_refs), ...]
1963
:param track_external_parent_refs: As keys are added, keep track of the
1964
keys they reference, so that we can query get_missing_parents(),
1966
:param inconsistency_fatal: When asked to add records that are already
1967
present, and the details are inconsistent with the existing
1968
record, raise an exception instead of warning (and skipping the
1971
self._add_callback = add_callback
1972
self._graph_index = graph_index
1973
self._parents = parents
1974
self.has_graph = parents
1975
self._is_locked = is_locked
1976
self._inconsistency_fatal = inconsistency_fatal
1977
# GroupCompress records tend to have the same 'group' start + offset
1978
# repeated over and over, this creates a surplus of ints
1979
self._int_cache = {}
1980
if track_external_parent_refs:
1981
self._key_dependencies = _KeyRefs(
1982
track_new_keys=track_new_keys)
1984
self._key_dependencies = None
1986
def add_records(self, records, random_id=False):
1987
"""Add multiple records to the index.
1989
This function does not insert data into the Immutable GraphIndex
1990
backing the KnitGraphIndex, instead it prepares data for insertion by
1991
the caller and checks that it is safe to insert then calls
1992
self._add_callback with the prepared GraphIndex nodes.
1994
:param records: a list of tuples:
1995
(key, options, access_memo, parents).
1996
:param random_id: If True the ids being added were randomly generated
1997
and no check for existence will be performed.
1999
if not self._add_callback:
2000
raise errors.ReadOnlyError(self)
2001
# we hope there are no repositories with inconsistent parentage
2006
for (key, value, refs) in records:
2007
if not self._parents:
2011
raise errors.KnitCorrupt(self,
2012
"attempt to add node with parents "
2013
"in parentless index.")
2016
keys[key] = (value, refs)
2019
present_nodes = self._get_entries(keys)
2020
for (index, key, value, node_refs) in present_nodes:
2021
# Sometimes these are passed as a list rather than a tuple
2022
node_refs = static_tuple.as_tuples(node_refs)
2023
passed = static_tuple.as_tuples(keys[key])
2024
if node_refs != passed[1]:
2025
details = '%s %s %s' % (key, (value, node_refs), passed)
2026
if self._inconsistency_fatal:
2027
raise errors.KnitCorrupt(self, "inconsistent details"
2028
" in add_records: %s" %
2031
trace.warning("inconsistent details in skipped"
2032
" record: %s", details)
2038
for key, (value, node_refs) in viewitems(keys):
2039
result.append((key, value, node_refs))
2041
for key, (value, node_refs) in viewitems(keys):
2042
result.append((key, value))
2044
key_dependencies = self._key_dependencies
2045
if key_dependencies is not None:
2047
for key, value, refs in records:
2049
key_dependencies.add_references(key, parents)
2051
for key, value, refs in records:
2052
new_keys.add_key(key)
2053
self._add_callback(records)
2055
def _check_read(self):
2056
"""Raise an exception if reads are not permitted."""
2057
if not self._is_locked():
2058
raise errors.ObjectNotLocked(self)
2060
def _check_write_ok(self):
2061
"""Raise an exception if writes are not permitted."""
2062
if not self._is_locked():
2063
raise errors.ObjectNotLocked(self)
2065
def _get_entries(self, keys, check_present=False):
2066
"""Get the entries for keys.
2068
Note: Callers are responsible for checking that the index is locked
2069
before calling this method.
2071
:param keys: An iterable of index key tuples.
2076
for node in self._graph_index.iter_entries(keys):
2078
found_keys.add(node[1])
2080
# adapt parentless index to the rest of the code.
2081
for node in self._graph_index.iter_entries(keys):
2082
yield node[0], node[1], node[2], ()
2083
found_keys.add(node[1])
2085
missing_keys = keys.difference(found_keys)
2087
raise errors.RevisionNotPresent(missing_keys.pop(), self)
2089
def find_ancestry(self, keys):
2090
"""See CombinedGraphIndex.find_ancestry"""
2091
return self._graph_index.find_ancestry(keys, 0)
2093
def get_parent_map(self, keys):
2094
"""Get a map of the parents of keys.
2096
:param keys: The keys to look up parents for.
2097
:return: A mapping from keys to parents. Absent keys are absent from
2101
nodes = self._get_entries(keys)
2105
result[node[1]] = node[3][0]
2108
result[node[1]] = None
2111
def get_missing_parents(self):
2112
"""Return the keys of missing parents."""
2113
# Copied from _KnitGraphIndex.get_missing_parents
2114
# We may have false positives, so filter those out.
2115
self._key_dependencies.satisfy_refs_for_keys(
2116
self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
2117
return frozenset(self._key_dependencies.get_unsatisfied_refs())
2119
def get_build_details(self, keys):
2120
"""Get the various build details for keys.
2122
Ghosts are omitted from the result.
2124
:param keys: An iterable of keys.
2125
:return: A dict of key:
2126
(index_memo, compression_parent, parents, record_details).
2128
* index_memo: opaque structure to pass to read_records to extract
2130
* compression_parent: Content that this record is built upon, may
2132
* parents: Logical parents of this node
2133
* record_details: extra information about the content which needs
2134
to be passed to Factory.parse_record
2138
entries = self._get_entries(keys)
2139
for entry in entries:
2141
if not self._parents:
2144
parents = entry[3][0]
2145
details = _GCBuildDetails(parents, self._node_to_position(entry))
2146
result[key] = details
2150
"""Get all the keys in the collection.
2152
The keys are not ordered.
2155
return [node[1] for node in self._graph_index.iter_all_entries()]
2157
def _node_to_position(self, node):
2158
"""Convert an index value to position details."""
2159
bits = node[2].split(' ')
2160
# It would be nice not to read the entire gzip.
2161
# start and stop are put into _int_cache because they are very common.
2162
# They define the 'group' that an entry is in, and many groups can have
2163
# thousands of objects.
2164
# Branching Launchpad, for example, saves ~600k integers, at 12 bytes
2165
# each, or about 7MB. Note that it might be even more when you consider
2166
# how PyInt is allocated in separate slabs. And you can't return a slab
2167
# to the OS if even 1 int on it is in use. Note though that Python uses
2168
# a LIFO when re-using PyInt slots, which might cause more
2170
start = int(bits[0])
2171
start = self._int_cache.setdefault(start, start)
2173
stop = self._int_cache.setdefault(stop, stop)
2174
basis_end = int(bits[2])
2175
delta_end = int(bits[3])
2176
# We can't use StaticTuple here, because node[0] is a BTreeGraphIndex
2178
return (node[0], start, stop, basis_end, delta_end)
2180
def scan_unvalidated_index(self, graph_index):
2181
"""Inform this _GCGraphIndex that there is an unvalidated index.
2183
This allows this _GCGraphIndex to keep track of any missing
2184
compression parents we may want to have filled in to make those
2185
indices valid. It also allows _GCGraphIndex to track any new keys.
2187
:param graph_index: A GraphIndex
2189
key_dependencies = self._key_dependencies
2190
if key_dependencies is None:
2192
for node in graph_index.iter_all_entries():
2193
# Add parent refs from graph_index (and discard parent refs
2194
# that the graph_index has).
2195
key_dependencies.add_references(node[1], node[3][0])
2198
from ._groupcompress_py import (
2200
apply_delta_to_source,
2203
decode_copy_instruction,
2207
from ._groupcompress_pyx import (
2209
apply_delta_to_source,
2214
GroupCompressor = PyrexGroupCompressor
2215
except ImportError as e:
2216
osutils.failed_to_load_extension(e)
2217
GroupCompressor = PythonGroupCompressor
added
removed
breezy/bzr/groupcompress.py
