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(), """
36
from breezy.bzr import (
42
from breezy.i18n import gettext
48
from .btree_index import BTreeBuilder
49
from ..lru_cache import LRUSizeCache
50
from ..sixish import (
56
from .versionedfile import (
60
ChunkedContentFactory,
61
FulltextContentFactory,
62
VersionedFilesWithFallbacks,
65
# Minimum number of uncompressed bytes to try fetch at once when retrieving
66
# groupcompress blocks.
69
# osutils.sha_string('')
70
_null_sha1 = b'da39a3ee5e6b4b0d3255bfef95601890afd80709'
72
def sort_gc_optimal(parent_map):
73
"""Sort and group the keys in parent_map into groupcompress order.
75
groupcompress is defined (currently) as reverse-topological order, grouped
78
:return: A sorted-list of keys
80
# groupcompress ordering is approximately reverse topological,
81
# properly grouped by file-id.
83
for key, value in viewitems(parent_map):
84
if isinstance(key, bytes) or len(key) == 1:
89
per_prefix_map[prefix][key] = value
91
per_prefix_map[prefix] = {key: value}
94
for prefix in sorted(per_prefix_map):
95
present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
99
class DecompressCorruption(errors.BzrError):
101
_fmt = "Corruption while decompressing repository file%(orig_error)s"
103
def __init__(self, orig_error=None):
104
if orig_error is not None:
105
self.orig_error = ", %s" % (orig_error,)
108
errors.BzrError.__init__(self)
111
# The max zlib window size is 32kB, so if we set 'max_size' output of the
112
# decompressor to the requested bytes + 32kB, then we should guarantee
113
# num_bytes coming out.
114
_ZLIB_DECOMP_WINDOW = 32*1024
116
class GroupCompressBlock(object):
117
"""An object which maintains the internal structure of the compressed data.
119
This tracks the meta info (start of text, length, type, etc.)
122
# Group Compress Block v1 Zlib
123
GCB_HEADER = b'gcb1z\n'
124
# Group Compress Block v1 Lzma
125
GCB_LZ_HEADER = b'gcb1l\n'
126
GCB_KNOWN_HEADERS = (GCB_HEADER, GCB_LZ_HEADER)
129
# map by key? or just order in file?
130
self._compressor_name = None
131
self._z_content_chunks = None
132
self._z_content_decompressor = None
133
self._z_content_length = None
134
self._content_length = None
136
self._content_chunks = None
139
# This is the maximum number of bytes this object will reference if
140
# everything is decompressed. However, if we decompress less than
141
# everything... (this would cause some problems for LRUSizeCache)
142
return self._content_length + self._z_content_length
144
def _ensure_content(self, num_bytes=None):
145
"""Make sure that content has been expanded enough.
147
:param num_bytes: Ensure that we have extracted at least num_bytes of
148
content. If None, consume everything
150
if self._content_length is None:
151
raise AssertionError('self._content_length should never be None')
152
if num_bytes is None:
153
num_bytes = self._content_length
154
elif (self._content_length is not None
155
and num_bytes > self._content_length):
156
raise AssertionError(
157
'requested num_bytes (%d) > content length (%d)'
158
% (num_bytes, self._content_length))
159
# Expand the content if required
160
if self._content is None:
161
if self._content_chunks is not None:
162
self._content = b''.join(self._content_chunks)
163
self._content_chunks = None
164
if self._content is None:
165
# We join self._z_content_chunks here, because if we are
166
# decompressing, then it is *very* likely that we have a single
168
if self._z_content_chunks is None:
169
raise AssertionError('No content to decompress')
170
z_content = b''.join(self._z_content_chunks)
173
elif self._compressor_name == 'lzma':
174
# We don't do partial lzma decomp yet
176
self._content = pylzma.decompress(z_content)
177
elif self._compressor_name == 'zlib':
178
# Start a zlib decompressor
179
if num_bytes * 4 > self._content_length * 3:
180
# If we are requesting more that 3/4ths of the content,
181
# just extract the whole thing in a single pass
182
num_bytes = self._content_length
183
self._content = zlib.decompress(z_content)
185
self._z_content_decompressor = zlib.decompressobj()
186
# Seed the decompressor with the uncompressed bytes, so
187
# that the rest of the code is simplified
188
self._content = self._z_content_decompressor.decompress(
189
z_content, num_bytes + _ZLIB_DECOMP_WINDOW)
190
if not self._z_content_decompressor.unconsumed_tail:
191
self._z_content_decompressor = None
193
raise AssertionError('Unknown compressor: %r'
194
% self._compressor_name)
195
# Any bytes remaining to be decompressed will be in the decompressors
198
# Do we have enough bytes already?
199
if len(self._content) >= num_bytes:
201
# If we got this far, and don't have a decompressor, something is wrong
202
if self._z_content_decompressor is None:
203
raise AssertionError(
204
'No decompressor to decompress %d bytes' % num_bytes)
205
remaining_decomp = self._z_content_decompressor.unconsumed_tail
206
if not remaining_decomp:
207
raise AssertionError('Nothing left to decompress')
208
needed_bytes = num_bytes - len(self._content)
209
# We always set max_size to 32kB over the minimum needed, so that
210
# zlib will give us as much as we really want.
211
# TODO: If this isn't good enough, we could make a loop here,
212
# that keeps expanding the request until we get enough
213
self._content += self._z_content_decompressor.decompress(
214
remaining_decomp, needed_bytes + _ZLIB_DECOMP_WINDOW)
215
if len(self._content) < num_bytes:
216
raise AssertionError('%d bytes wanted, only %d available'
217
% (num_bytes, len(self._content)))
218
if not self._z_content_decompressor.unconsumed_tail:
219
# The stream is finished
220
self._z_content_decompressor = None
222
def _parse_bytes(self, data, pos):
223
"""Read the various lengths from the header.
225
This also populates the various 'compressed' buffers.
227
:return: The position in bytes just after the last newline
229
# At present, we have 2 integers for the compressed and uncompressed
230
# content. In base10 (ascii) 14 bytes can represent > 1TB, so to avoid
231
# checking too far, cap the search to 14 bytes.
232
pos2 = data.index(b'\n', pos, pos + 14)
233
self._z_content_length = int(data[pos:pos2])
235
pos2 = data.index(b'\n', pos, pos + 14)
236
self._content_length = int(data[pos:pos2])
238
if len(data) != (pos + self._z_content_length):
239
# XXX: Define some GCCorrupt error ?
240
raise AssertionError('Invalid bytes: (%d) != %d + %d' %
241
(len(data), pos, self._z_content_length))
242
self._z_content_chunks = (data[pos:],)
245
def _z_content(self):
246
"""Return z_content_chunks as a simple string.
248
Meant only to be used by the test suite.
250
if self._z_content_chunks is not None:
251
return b''.join(self._z_content_chunks)
255
def from_bytes(cls, bytes):
258
if header not in cls.GCB_KNOWN_HEADERS:
259
raise ValueError('bytes did not start with any of %r'
260
% (cls.GCB_KNOWN_HEADERS,))
261
if header == cls.GCB_HEADER:
262
out._compressor_name = 'zlib'
263
elif header == cls.GCB_LZ_HEADER:
264
out._compressor_name = 'lzma'
266
raise ValueError('unknown compressor: %r' % (header,))
267
out._parse_bytes(bytes, 6)
270
def extract(self, key, start, end, sha1=None):
271
"""Extract the text for a specific key.
273
:param key: The label used for this content
274
:param sha1: TODO (should we validate only when sha1 is supplied?)
275
:return: The bytes for the content
277
if start == end == 0:
279
self._ensure_content(end)
280
# The bytes are 'f' or 'd' for the type, then a variable-length
281
# base128 integer for the content size, then the actual content
282
# We know that the variable-length integer won't be longer than 5
283
# bytes (it takes 5 bytes to encode 2^32)
284
c = self._content[start:start + 1]
289
raise ValueError('Unknown content control code: %s'
292
content_len, len_len = decode_base128_int(
293
self._content[start + 1:start + 6])
294
content_start = start + 1 + len_len
295
if end != content_start + content_len:
296
raise ValueError('end != len according to field header'
297
' %s != %s' % (end, content_start + content_len))
299
return self._content[content_start:end]
300
# Must be type delta as checked above
301
return apply_delta_to_source(self._content, content_start, end)
303
def set_chunked_content(self, content_chunks, length):
304
"""Set the content of this block to the given chunks."""
305
# If we have lots of short lines, it is may be more efficient to join
306
# the content ahead of time. If the content is <10MiB, we don't really
307
# care about the extra memory consumption, so we can just pack it and
308
# be done. However, timing showed 18s => 17.9s for repacking 1k revs of
309
# mysql, which is below the noise margin
310
self._content_length = length
311
self._content_chunks = content_chunks
313
self._z_content_chunks = None
315
def set_content(self, content):
316
"""Set the content of this block."""
317
self._content_length = len(content)
318
self._content = content
319
self._z_content_chunks = None
321
def _create_z_content_from_chunks(self, chunks):
322
compressor = zlib.compressobj(zlib.Z_DEFAULT_COMPRESSION)
323
# Peak in this point is 1 fulltext, 1 compressed text, + zlib overhead
324
# (measured peak is maybe 30MB over the above...)
325
compressed_chunks = list(map(compressor.compress, chunks))
326
compressed_chunks.append(compressor.flush())
327
# Ignore empty chunks
328
self._z_content_chunks = [c for c in compressed_chunks if c]
329
self._z_content_length = sum(map(len, self._z_content_chunks))
331
def _create_z_content(self):
332
if self._z_content_chunks is not None:
334
if self._content_chunks is not None:
335
chunks = self._content_chunks
337
chunks = (self._content,)
338
self._create_z_content_from_chunks(chunks)
341
"""Create the byte stream as a series of 'chunks'"""
342
self._create_z_content()
343
header = self.GCB_HEADER
344
chunks = [b'%s%d\n%d\n'
345
% (header, self._z_content_length, self._content_length),
347
chunks.extend(self._z_content_chunks)
348
total_len = sum(map(len, chunks))
349
return total_len, chunks
352
"""Encode the information into a byte stream."""
353
total_len, chunks = self.to_chunks()
354
return b''.join(chunks)
356
def _dump(self, include_text=False):
357
"""Take this block, and spit out a human-readable structure.
359
:param include_text: Inserts also include text bits, chose whether you
360
want this displayed in the dump or not.
361
:return: A dump of the given block. The layout is something like:
362
[('f', length), ('d', delta_length, text_length, [delta_info])]
363
delta_info := [('i', num_bytes, text), ('c', offset, num_bytes),
366
self._ensure_content()
369
while pos < self._content_length:
370
kind = self._content[pos:pos + 1]
372
if kind not in (b'f', b'd'):
373
raise ValueError('invalid kind character: %r' % (kind,))
374
content_len, len_len = decode_base128_int(
375
self._content[pos:pos + 5])
377
if content_len + pos > self._content_length:
378
raise ValueError('invalid content_len %d for record @ pos %d'
379
% (content_len, pos - len_len - 1))
380
if kind == b'f': # Fulltext
382
text = self._content[pos:pos+content_len]
383
result.append((b'f', content_len, text))
385
result.append((b'f', content_len))
386
elif kind == b'd': # Delta
387
delta_content = self._content[pos:pos+content_len]
389
# The first entry in a delta is the decompressed length
390
decomp_len, delta_pos = decode_base128_int(delta_content)
391
result.append((b'd', content_len, decomp_len, delta_info))
393
while delta_pos < content_len:
394
c = indexbytes(delta_content, delta_pos)
398
delta_pos) = decode_copy_instruction(delta_content, c,
401
text = self._content[offset:offset+length]
402
delta_info.append((b'c', offset, length, text))
404
delta_info.append((b'c', offset, length))
405
measured_len += length
408
txt = delta_content[delta_pos:delta_pos+c]
411
delta_info.append((b'i', c, txt))
414
if delta_pos != content_len:
415
raise ValueError('Delta consumed a bad number of bytes:'
416
' %d != %d' % (delta_pos, content_len))
417
if measured_len != decomp_len:
418
raise ValueError('Delta claimed fulltext was %d bytes, but'
419
' extraction resulted in %d bytes'
420
% (decomp_len, measured_len))
425
class _LazyGroupCompressFactory(object):
426
"""Yield content from a GroupCompressBlock on demand."""
428
def __init__(self, key, parents, manager, start, end, first):
429
"""Create a _LazyGroupCompressFactory
431
:param key: The key of just this record
432
:param parents: The parents of this key (possibly None)
433
:param gc_block: A GroupCompressBlock object
434
:param start: Offset of the first byte for this record in the
436
:param end: Offset of the byte just after the end of this record
437
(ie, bytes = content[start:end])
438
:param first: Is this the first Factory for the given block?
441
self.parents = parents
443
# Note: This attribute coupled with Manager._factories creates a
444
# reference cycle. Perhaps we would rather use a weakref(), or
445
# find an appropriate time to release the ref. After the first
446
# get_bytes_as call? After Manager.get_record_stream() returns
448
self._manager = manager
450
self.storage_kind = 'groupcompress-block'
452
self.storage_kind = 'groupcompress-block-ref'
458
return '%s(%s, first=%s)' % (self.__class__.__name__,
459
self.key, self._first)
461
def get_bytes_as(self, storage_kind):
462
if storage_kind == self.storage_kind:
464
# wire bytes, something...
465
return self._manager._wire_bytes()
468
if storage_kind in ('fulltext', 'chunked'):
469
if self._bytes is None:
470
# Grab and cache the raw bytes for this entry
471
# and break the ref-cycle with _manager since we don't need it
474
self._manager._prepare_for_extract()
475
except zlib.error as value:
476
raise DecompressCorruption("zlib: " + str(value))
477
block = self._manager._block
478
self._bytes = block.extract(self.key, self._start, self._end)
479
# There are code paths that first extract as fulltext, and then
480
# extract as storage_kind (smart fetch). So we don't break the
481
# refcycle here, but instead in manager.get_record_stream()
482
if storage_kind == 'fulltext':
486
raise errors.UnavailableRepresentation(self.key, storage_kind,
490
class _LazyGroupContentManager(object):
491
"""This manages a group of _LazyGroupCompressFactory objects."""
493
_max_cut_fraction = 0.75 # We allow a block to be trimmed to 75% of
494
# current size, and still be considered
496
_full_block_size = 4*1024*1024
497
_full_mixed_block_size = 2*1024*1024
498
_full_enough_block_size = 3*1024*1024 # size at which we won't repack
499
_full_enough_mixed_block_size = 2*768*1024 # 1.5MB
501
def __init__(self, block, get_compressor_settings=None):
503
# We need to preserve the ordering
506
self._get_settings = get_compressor_settings
507
self._compressor_settings = None
509
def _get_compressor_settings(self):
510
if self._compressor_settings is not None:
511
return self._compressor_settings
513
if self._get_settings is not None:
514
settings = self._get_settings()
516
vf = GroupCompressVersionedFiles
517
settings = vf._DEFAULT_COMPRESSOR_SETTINGS
518
self._compressor_settings = settings
519
return self._compressor_settings
521
def add_factory(self, key, parents, start, end):
522
if not self._factories:
526
# Note that this creates a reference cycle....
527
factory = _LazyGroupCompressFactory(key, parents, self,
528
start, end, first=first)
529
# max() works here, but as a function call, doing a compare seems to be
530
# significantly faster, timeit says 250ms for max() and 100ms for the
532
if end > self._last_byte:
533
self._last_byte = end
534
self._factories.append(factory)
536
def get_record_stream(self):
537
"""Get a record for all keys added so far."""
538
for factory in self._factories:
540
# Break the ref-cycle
541
factory._bytes = None
542
factory._manager = None
543
# TODO: Consider setting self._factories = None after the above loop,
544
# as it will break the reference cycle
546
def _trim_block(self, last_byte):
547
"""Create a new GroupCompressBlock, with just some of the content."""
548
# None of the factories need to be adjusted, because the content is
549
# located in an identical place. Just that some of the unreferenced
550
# trailing bytes are stripped
551
trace.mutter('stripping trailing bytes from groupcompress block'
552
' %d => %d', self._block._content_length, last_byte)
553
new_block = GroupCompressBlock()
554
self._block._ensure_content(last_byte)
555
new_block.set_content(self._block._content[:last_byte])
556
self._block = new_block
558
def _make_group_compressor(self):
559
return GroupCompressor(self._get_compressor_settings())
561
def _rebuild_block(self):
562
"""Create a new GroupCompressBlock with only the referenced texts."""
563
compressor = self._make_group_compressor()
565
old_length = self._block._content_length
567
for factory in self._factories:
568
bytes = factory.get_bytes_as('fulltext')
569
(found_sha1, start_point, end_point,
570
type) = compressor.compress(factory.key, bytes, factory.sha1)
571
# Now update this factory with the new offsets, etc
572
factory.sha1 = found_sha1
573
factory._start = start_point
574
factory._end = end_point
575
self._last_byte = end_point
576
new_block = compressor.flush()
577
# TODO: Should we check that new_block really *is* smaller than the old
578
# block? It seems hard to come up with a method that it would
579
# expand, since we do full compression again. Perhaps based on a
580
# request that ends up poorly ordered?
581
# TODO: If the content would have expanded, then we would want to
582
# handle a case where we need to split the block.
583
# Now that we have a user-tweakable option
584
# (max_bytes_to_index), it is possible that one person set it
585
# to a very low value, causing poor compression.
586
delta = time.time() - tstart
587
self._block = new_block
588
trace.mutter('creating new compressed block on-the-fly in %.3fs'
589
' %d bytes => %d bytes', delta, old_length,
590
self._block._content_length)
592
def _prepare_for_extract(self):
593
"""A _LazyGroupCompressFactory is about to extract to fulltext."""
594
# We expect that if one child is going to fulltext, all will be. This
595
# helps prevent all of them from extracting a small amount at a time.
596
# Which in itself isn't terribly expensive, but resizing 2MB 32kB at a
597
# time (self._block._content) is a little expensive.
598
self._block._ensure_content(self._last_byte)
600
def _check_rebuild_action(self):
601
"""Check to see if our block should be repacked."""
604
for factory in self._factories:
605
total_bytes_used += factory._end - factory._start
606
if last_byte_used < factory._end:
607
last_byte_used = factory._end
608
# If we are using more than half of the bytes from the block, we have
609
# nothing else to check
610
if total_bytes_used * 2 >= self._block._content_length:
611
return None, last_byte_used, total_bytes_used
612
# We are using less than 50% of the content. Is the content we are
613
# using at the beginning of the block? If so, we can just trim the
614
# tail, rather than rebuilding from scratch.
615
if total_bytes_used * 2 > last_byte_used:
616
return 'trim', last_byte_used, total_bytes_used
618
# We are using a small amount of the data, and it isn't just packed
619
# nicely at the front, so rebuild the content.
620
# Note: This would be *nicer* as a strip-data-from-group, rather than
621
# building it up again from scratch
622
# It might be reasonable to consider the fulltext sizes for
623
# different bits when deciding this, too. As you may have a small
624
# fulltext, and a trivial delta, and you are just trading around
625
# for another fulltext. If we do a simple 'prune' you may end up
626
# expanding many deltas into fulltexts, as well.
627
# If we build a cheap enough 'strip', then we could try a strip,
628
# if that expands the content, we then rebuild.
629
return 'rebuild', last_byte_used, total_bytes_used
631
def check_is_well_utilized(self):
632
"""Is the current block considered 'well utilized'?
634
This heuristic asks if the current block considers itself to be a fully
635
developed group, rather than just a loose collection of data.
637
if len(self._factories) == 1:
638
# A block of length 1 could be improved by combining with other
639
# groups - don't look deeper. Even larger than max size groups
640
# could compress well with adjacent versions of the same thing.
642
action, last_byte_used, total_bytes_used = self._check_rebuild_action()
643
block_size = self._block._content_length
644
if total_bytes_used < block_size * self._max_cut_fraction:
645
# This block wants to trim itself small enough that we want to
646
# consider it under-utilized.
648
# TODO: This code is meant to be the twin of _insert_record_stream's
649
# 'start_new_block' logic. It would probably be better to factor
650
# out that logic into a shared location, so that it stays
652
# We currently assume a block is properly utilized whenever it is >75%
653
# of the size of a 'full' block. In normal operation, a block is
654
# considered full when it hits 4MB of same-file content. So any block
655
# >3MB is 'full enough'.
656
# The only time this isn't true is when a given block has large-object
657
# content. (a single file >4MB, etc.)
658
# Under these circumstances, we allow a block to grow to
659
# 2 x largest_content. Which means that if a given block had a large
660
# object, it may actually be under-utilized. However, given that this
661
# is 'pack-on-the-fly' it is probably reasonable to not repack large
662
# content blobs on-the-fly. Note that because we return False for all
663
# 1-item blobs, we will repack them; we may wish to reevaluate our
664
# treatment of large object blobs in the future.
665
if block_size >= self._full_enough_block_size:
667
# If a block is <3MB, it still may be considered 'full' if it contains
668
# mixed content. The current rule is 2MB of mixed content is considered
669
# full. So check to see if this block contains mixed content, and
670
# set the threshold appropriately.
672
for factory in self._factories:
673
prefix = factory.key[:-1]
674
if common_prefix is None:
675
common_prefix = prefix
676
elif prefix != common_prefix:
677
# Mixed content, check the size appropriately
678
if block_size >= self._full_enough_mixed_block_size:
681
# The content failed both the mixed check and the single-content check
682
# so obviously it is not fully utilized
683
# TODO: there is one other constraint that isn't being checked
684
# namely, that the entries in the block are in the appropriate
685
# order. For example, you could insert the entries in exactly
686
# reverse groupcompress order, and we would think that is ok.
687
# (all the right objects are in one group, and it is fully
688
# utilized, etc.) For now, we assume that case is rare,
689
# especially since we should always fetch in 'groupcompress'
693
def _check_rebuild_block(self):
694
action, last_byte_used, total_bytes_used = self._check_rebuild_action()
698
self._trim_block(last_byte_used)
699
elif action == 'rebuild':
700
self._rebuild_block()
702
raise ValueError('unknown rebuild action: %r' % (action,))
704
def _wire_bytes(self):
705
"""Return a byte stream suitable for transmitting over the wire."""
706
self._check_rebuild_block()
707
# The outer block starts with:
708
# 'groupcompress-block\n'
709
# <length of compressed key info>\n
710
# <length of uncompressed info>\n
711
# <length of gc block>\n
714
lines = [b'groupcompress-block\n']
715
# The minimal info we need is the key, the start offset, and the
716
# parents. The length and type are encoded in the record itself.
717
# However, passing in the other bits makes it easier. The list of
718
# keys, and the start offset, the length
720
# 1 line with parents, '' for ()
721
# 1 line for start offset
722
# 1 line for end byte
724
for factory in self._factories:
725
key_bytes = b'\x00'.join(factory.key)
726
parents = factory.parents
728
parent_bytes = b'None:'
730
parent_bytes = b'\t'.join(b'\x00'.join(key) for key in parents)
731
record_header = b'%s\n%s\n%d\n%d\n' % (
732
key_bytes, parent_bytes, factory._start, factory._end)
733
header_lines.append(record_header)
734
# TODO: Can we break the refcycle at this point and set
735
# factory._manager = None?
736
header_bytes = b''.join(header_lines)
738
header_bytes_len = len(header_bytes)
739
z_header_bytes = zlib.compress(header_bytes)
741
z_header_bytes_len = len(z_header_bytes)
742
block_bytes_len, block_chunks = self._block.to_chunks()
743
lines.append(b'%d\n%d\n%d\n' % (
744
z_header_bytes_len, header_bytes_len, block_bytes_len))
745
lines.append(z_header_bytes)
746
lines.extend(block_chunks)
747
del z_header_bytes, block_chunks
748
# TODO: This is a point where we will double the memory consumption. To
749
# avoid this, we probably have to switch to a 'chunked' api
750
return b''.join(lines)
753
def from_bytes(cls, bytes):
754
# TODO: This does extra string copying, probably better to do it a
755
# different way. At a minimum this creates 2 copies of the
757
(storage_kind, z_header_len, header_len,
758
block_len, rest) = bytes.split(b'\n', 4)
760
if storage_kind != b'groupcompress-block':
761
raise ValueError('Unknown storage kind: %s' % (storage_kind,))
762
z_header_len = int(z_header_len)
763
if len(rest) < z_header_len:
764
raise ValueError('Compressed header len shorter than all bytes')
765
z_header = rest[:z_header_len]
766
header_len = int(header_len)
767
header = zlib.decompress(z_header)
768
if len(header) != header_len:
769
raise ValueError('invalid length for decompressed bytes')
771
block_len = int(block_len)
772
if len(rest) != z_header_len + block_len:
773
raise ValueError('Invalid length for block')
774
block_bytes = rest[z_header_len:]
776
# So now we have a valid GCB, we just need to parse the factories that
778
header_lines = header.split(b'\n')
780
last = header_lines.pop()
782
raise ValueError('header lines did not end with a trailing'
784
if len(header_lines) % 4 != 0:
785
raise ValueError('The header was not an even multiple of 4 lines')
786
block = GroupCompressBlock.from_bytes(block_bytes)
789
for start in range(0, len(header_lines), 4):
791
key = tuple(header_lines[start].split(b'\x00'))
792
parents_line = header_lines[start+1]
793
if parents_line == b'None:':
796
parents = tuple([tuple(segment.split(b'\x00'))
797
for segment in parents_line.split(b'\t')
799
start_offset = int(header_lines[start+2])
800
end_offset = int(header_lines[start+3])
801
result.add_factory(key, parents, start_offset, end_offset)
805
def network_block_to_records(storage_kind, bytes, line_end):
806
if storage_kind != 'groupcompress-block':
807
raise ValueError('Unknown storage kind: %s' % (storage_kind,))
808
manager = _LazyGroupContentManager.from_bytes(bytes)
809
return manager.get_record_stream()
812
class _CommonGroupCompressor(object):
814
def __init__(self, settings=None):
815
"""Create a GroupCompressor."""
820
self.labels_deltas = {}
821
self._delta_index = None # Set by the children
822
self._block = GroupCompressBlock()
826
self._settings = settings
828
def compress(self, key, bytes, expected_sha, nostore_sha=None, soft=False):
829
"""Compress lines with label key.
831
:param key: A key tuple. It is stored in the output
832
for identification of the text during decompression. If the last
833
element is b'None' it is replaced with the sha1 of the text -
835
:param bytes: The bytes to be compressed
836
:param expected_sha: If non-None, the sha the lines are believed to
837
have. During compression the sha is calculated; a mismatch will
839
:param nostore_sha: If the computed sha1 sum matches, we will raise
840
ExistingContent rather than adding the text.
841
:param soft: Do a 'soft' compression. This means that we require larger
842
ranges to match to be considered for a copy command.
844
:return: The sha1 of lines, the start and end offsets in the delta, and
845
the type ('fulltext' or 'delta').
847
:seealso VersionedFiles.add_lines:
849
if not bytes: # empty, like a dir entry, etc
850
if nostore_sha == _null_sha1:
851
raise errors.ExistingContent()
852
return _null_sha1, 0, 0, 'fulltext'
853
# we assume someone knew what they were doing when they passed it in
854
if expected_sha is not None:
857
sha1 = osutils.sha_string(bytes)
858
if nostore_sha is not None:
859
if sha1 == nostore_sha:
860
raise errors.ExistingContent()
862
key = key[:-1] + (b'sha1:' + sha1,)
864
start, end, type = self._compress(key, bytes, len(bytes) / 2, soft)
865
return sha1, start, end, type
867
def _compress(self, key, bytes, max_delta_size, soft=False):
868
"""Compress lines with label key.
870
:param key: A key tuple. It is stored in the output for identification
871
of the text during decompression.
873
:param bytes: The bytes to be compressed
875
:param max_delta_size: The size above which we issue a fulltext instead
878
:param soft: Do a 'soft' compression. This means that we require larger
879
ranges to match to be considered for a copy command.
881
:return: The sha1 of lines, the start and end offsets in the delta, and
882
the type ('fulltext' or 'delta').
884
raise NotImplementedError(self._compress)
886
def extract(self, key):
887
"""Extract a key previously added to the compressor.
889
:param key: The key to extract.
890
:return: An iterable over bytes and the sha1.
892
(start_byte, start_chunk, end_byte, end_chunk) = self.labels_deltas[key]
893
delta_chunks = self.chunks[start_chunk:end_chunk]
894
stored_bytes = b''.join(delta_chunks)
895
kind = stored_bytes[:1]
897
fulltext_len, offset = decode_base128_int(stored_bytes[1:10])
898
data_len = fulltext_len + 1 + offset
899
if data_len != len(stored_bytes):
900
raise ValueError('Index claimed fulltext len, but stored bytes'
902
% (len(stored_bytes), data_len))
903
data = stored_bytes[offset + 1:]
906
raise ValueError('Unknown content kind, bytes claim %s' % kind)
907
# XXX: This is inefficient at best
908
source = b''.join(self.chunks[:start_chunk])
909
delta_len, offset = decode_base128_int(stored_bytes[1:10])
910
data_len = delta_len + 1 + offset
911
if data_len != len(stored_bytes):
912
raise ValueError('Index claimed delta len, but stored bytes'
914
% (len(stored_bytes), data_len))
915
data = apply_delta(source, stored_bytes[offset + 1:])
916
data_sha1 = osutils.sha_string(data)
917
return data, data_sha1
920
"""Finish this group, creating a formatted stream.
922
After calling this, the compressor should no longer be used
924
self._block.set_chunked_content(self.chunks, self.endpoint)
926
self._delta_index = None
930
"""Call this if you want to 'revoke' the last compression.
932
After this, the data structures will be rolled back, but you cannot do
935
self._delta_index = None
936
del self.chunks[self._last[0]:]
937
self.endpoint = self._last[1]
941
"""Return the overall compression ratio."""
942
return float(self.input_bytes) / float(self.endpoint)
945
class PythonGroupCompressor(_CommonGroupCompressor):
947
def __init__(self, settings=None):
948
"""Create a GroupCompressor.
950
Used only if the pyrex version is not available.
952
super(PythonGroupCompressor, self).__init__(settings)
953
self._delta_index = LinesDeltaIndex([])
954
# The actual content is managed by LinesDeltaIndex
955
self.chunks = self._delta_index.lines
957
def _compress(self, key, bytes, max_delta_size, soft=False):
958
"""see _CommonGroupCompressor._compress"""
959
input_len = len(bytes)
960
new_lines = osutils.split_lines(bytes)
961
out_lines, index_lines = self._delta_index.make_delta(
962
new_lines, bytes_length=input_len, soft=soft)
963
delta_length = sum(map(len, out_lines))
964
if delta_length > max_delta_size:
965
# The delta is longer than the fulltext, insert a fulltext
967
out_lines = [b'f', encode_base128_int(input_len)]
968
out_lines.extend(new_lines)
969
index_lines = [False, False]
970
index_lines.extend([True] * len(new_lines))
972
# this is a worthy delta, output it
975
# Update the delta_length to include those two encoded integers
976
out_lines[1] = encode_base128_int(delta_length)
978
start = self.endpoint
979
chunk_start = len(self.chunks)
980
self._last = (chunk_start, self.endpoint)
981
self._delta_index.extend_lines(out_lines, index_lines)
982
self.endpoint = self._delta_index.endpoint
983
self.input_bytes += input_len
984
chunk_end = len(self.chunks)
985
self.labels_deltas[key] = (start, chunk_start,
986
self.endpoint, chunk_end)
987
return start, self.endpoint, type
990
class PyrexGroupCompressor(_CommonGroupCompressor):
991
"""Produce a serialised group of compressed texts.
993
It contains code very similar to SequenceMatcher because of having a similar
994
task. However some key differences apply:
996
* there is no junk, we want a minimal edit not a human readable diff.
997
* we don't filter very common lines (because we don't know where a good
998
range will start, and after the first text we want to be emitting minmal
1000
* we chain the left side, not the right side
1001
* we incrementally update the adjacency matrix as new lines are provided.
1002
* we look for matches in all of the left side, so the routine which does
1003
the analagous task of find_longest_match does not need to filter on the
1007
def __init__(self, settings=None):
1008
super(PyrexGroupCompressor, self).__init__(settings)
1009
max_bytes_to_index = self._settings.get('max_bytes_to_index', 0)
1010
self._delta_index = DeltaIndex(max_bytes_to_index=max_bytes_to_index)
1012
def _compress(self, key, bytes, max_delta_size, soft=False):
1013
"""see _CommonGroupCompressor._compress"""
1014
input_len = len(bytes)
1015
# By having action/label/sha1/len, we can parse the group if the index
1016
# was ever destroyed, we have the key in 'label', we know the final
1017
# bytes are valid from sha1, and we know where to find the end of this
1018
# record because of 'len'. (the delta record itself will store the
1019
# total length for the expanded record)
1020
# 'len: %d\n' costs approximately 1% increase in total data
1021
# Having the labels at all costs us 9-10% increase, 38% increase for
1022
# inventory pages, and 5.8% increase for text pages
1023
# new_chunks = ['label:%s\nsha1:%s\n' % (label, sha1)]
1024
if self._delta_index._source_offset != self.endpoint:
1025
raise AssertionError('_source_offset != endpoint'
1026
' somehow the DeltaIndex got out of sync with'
1027
' the output lines')
1028
delta = self._delta_index.make_delta(bytes, max_delta_size)
1031
enc_length = encode_base128_int(len(bytes))
1032
len_mini_header = 1 + len(enc_length)
1033
self._delta_index.add_source(bytes, len_mini_header)
1034
new_chunks = [b'f', enc_length, bytes]
1037
enc_length = encode_base128_int(len(delta))
1038
len_mini_header = 1 + len(enc_length)
1039
new_chunks = [b'd', enc_length, delta]
1040
self._delta_index.add_delta_source(delta, len_mini_header)
1042
start = self.endpoint
1043
chunk_start = len(self.chunks)
1044
# Now output these bytes
1045
self._output_chunks(new_chunks)
1046
self.input_bytes += input_len
1047
chunk_end = len(self.chunks)
1048
self.labels_deltas[key] = (start, chunk_start,
1049
self.endpoint, chunk_end)
1050
if not self._delta_index._source_offset == self.endpoint:
1051
raise AssertionError('the delta index is out of sync'
1052
'with the output lines %s != %s'
1053
% (self._delta_index._source_offset, self.endpoint))
1054
return start, self.endpoint, type
1056
def _output_chunks(self, new_chunks):
1057
"""Output some chunks.
1059
:param new_chunks: The chunks to output.
1061
self._last = (len(self.chunks), self.endpoint)
1062
endpoint = self.endpoint
1063
self.chunks.extend(new_chunks)
1064
endpoint += sum(map(len, new_chunks))
1065
self.endpoint = endpoint
1068
def make_pack_factory(graph, delta, keylength, inconsistency_fatal=True):
1069
"""Create a factory for creating a pack based groupcompress.
1071
This is only functional enough to run interface tests, it doesn't try to
1072
provide a full pack environment.
1074
:param graph: Store a graph.
1075
:param delta: Delta compress contents.
1076
:param keylength: How long should keys be.
1078
def factory(transport):
1083
graph_index = BTreeBuilder(reference_lists=ref_length,
1084
key_elements=keylength)
1085
stream = transport.open_write_stream('newpack')
1086
writer = pack.ContainerWriter(stream.write)
1088
index = _GCGraphIndex(graph_index, lambda:True, parents=parents,
1089
add_callback=graph_index.add_nodes,
1090
inconsistency_fatal=inconsistency_fatal)
1091
access = pack_repo._DirectPackAccess({})
1092
access.set_writer(writer, graph_index, (transport, 'newpack'))
1093
result = GroupCompressVersionedFiles(index, access, delta)
1094
result.stream = stream
1095
result.writer = writer
1100
def cleanup_pack_group(versioned_files):
1101
versioned_files.writer.end()
1102
versioned_files.stream.close()
1105
class _BatchingBlockFetcher(object):
1106
"""Fetch group compress blocks in batches.
1108
:ivar total_bytes: int of expected number of bytes needed to fetch the
1109
currently pending batch.
1112
def __init__(self, gcvf, locations, get_compressor_settings=None):
1114
self.locations = locations
1116
self.batch_memos = {}
1117
self.memos_to_get = []
1118
self.total_bytes = 0
1119
self.last_read_memo = None
1121
self._get_compressor_settings = get_compressor_settings
1123
def add_key(self, key):
1124
"""Add another to key to fetch.
1126
:return: The estimated number of bytes needed to fetch the batch so
1129
self.keys.append(key)
1130
index_memo, _, _, _ = self.locations[key]
1131
read_memo = index_memo[0:3]
1132
# Three possibilities for this read_memo:
1133
# - it's already part of this batch; or
1134
# - it's not yet part of this batch, but is already cached; or
1135
# - it's not yet part of this batch and will need to be fetched.
1136
if read_memo in self.batch_memos:
1137
# This read memo is already in this batch.
1138
return self.total_bytes
1140
cached_block = self.gcvf._group_cache[read_memo]
1142
# This read memo is new to this batch, and the data isn't cached
1144
self.batch_memos[read_memo] = None
1145
self.memos_to_get.append(read_memo)
1146
byte_length = read_memo[2]
1147
self.total_bytes += byte_length
1149
# This read memo is new to this batch, but cached.
1150
# Keep a reference to the cached block in batch_memos because it's
1151
# certain that we'll use it when this batch is processed, but
1152
# there's a risk that it would fall out of _group_cache between now
1154
self.batch_memos[read_memo] = cached_block
1155
return self.total_bytes
1157
def _flush_manager(self):
1158
if self.manager is not None:
1159
for factory in self.manager.get_record_stream():
1162
self.last_read_memo = None
1164
def yield_factories(self, full_flush=False):
1165
"""Yield factories for keys added since the last yield. They will be
1166
returned in the order they were added via add_key.
1168
:param full_flush: by default, some results may not be returned in case
1169
they can be part of the next batch. If full_flush is True, then
1170
all results are returned.
1172
if self.manager is None and not self.keys:
1174
# Fetch all memos in this batch.
1175
blocks = self.gcvf._get_blocks(self.memos_to_get)
1176
# Turn blocks into factories and yield them.
1177
memos_to_get_stack = list(self.memos_to_get)
1178
memos_to_get_stack.reverse()
1179
for key in self.keys:
1180
index_memo, _, parents, _ = self.locations[key]
1181
read_memo = index_memo[:3]
1182
if self.last_read_memo != read_memo:
1183
# We are starting a new block. If we have a
1184
# manager, we have found everything that fits for
1185
# now, so yield records
1186
for factory in self._flush_manager():
1188
# Now start a new manager.
1189
if memos_to_get_stack and memos_to_get_stack[-1] == read_memo:
1190
# The next block from _get_blocks will be the block we
1192
block_read_memo, block = next(blocks)
1193
if block_read_memo != read_memo:
1194
raise AssertionError(
1195
"block_read_memo out of sync with read_memo"
1196
"(%r != %r)" % (block_read_memo, read_memo))
1197
self.batch_memos[read_memo] = block
1198
memos_to_get_stack.pop()
1200
block = self.batch_memos[read_memo]
1201
self.manager = _LazyGroupContentManager(block,
1202
get_compressor_settings=self._get_compressor_settings)
1203
self.last_read_memo = read_memo
1204
start, end = index_memo[3:5]
1205
self.manager.add_factory(key, parents, start, end)
1207
for factory in self._flush_manager():
1210
self.batch_memos.clear()
1211
del self.memos_to_get[:]
1212
self.total_bytes = 0
1215
class GroupCompressVersionedFiles(VersionedFilesWithFallbacks):
1216
"""A group-compress based VersionedFiles implementation."""
1218
# This controls how the GroupCompress DeltaIndex works. Basically, we
1219
# compute hash pointers into the source blocks (so hash(text) => text).
1220
# However each of these references costs some memory in trade against a
1221
# more accurate match result. For very large files, they either are
1222
# pre-compressed and change in bulk whenever they change, or change in just
1223
# local blocks. Either way, 'improved resolution' is not very helpful,
1224
# versus running out of memory trying to track everything. The default max
1225
# gives 100% sampling of a 1MB file.
1226
_DEFAULT_MAX_BYTES_TO_INDEX = 1024 * 1024
1227
_DEFAULT_COMPRESSOR_SETTINGS = {'max_bytes_to_index':
1228
_DEFAULT_MAX_BYTES_TO_INDEX}
1230
def __init__(self, index, access, delta=True, _unadded_refs=None,
1232
"""Create a GroupCompressVersionedFiles object.
1234
:param index: The index object storing access and graph data.
1235
:param access: The access object storing raw data.
1236
:param delta: Whether to delta compress or just entropy compress.
1237
:param _unadded_refs: private parameter, don't use.
1238
:param _group_cache: private parameter, don't use.
1241
self._access = access
1243
if _unadded_refs is None:
1245
self._unadded_refs = _unadded_refs
1246
if _group_cache is None:
1247
_group_cache = LRUSizeCache(max_size=50*1024*1024)
1248
self._group_cache = _group_cache
1249
self._immediate_fallback_vfs = []
1250
self._max_bytes_to_index = None
1252
def without_fallbacks(self):
1253
"""Return a clone of this object without any fallbacks configured."""
1254
return GroupCompressVersionedFiles(self._index, self._access,
1255
self._delta, _unadded_refs=dict(self._unadded_refs),
1256
_group_cache=self._group_cache)
1258
def add_lines(self, key, parents, lines, parent_texts=None,
1259
left_matching_blocks=None, nostore_sha=None, random_id=False,
1260
check_content=True):
1261
"""Add a text to the store.
1263
:param key: The key tuple of the text to add.
1264
:param parents: The parents key tuples of the text to add.
1265
:param lines: A list of lines. Each line must be a bytestring. And all
1266
of them except the last must be terminated with \\n and contain no
1267
other \\n's. The last line may either contain no \\n's or a single
1268
terminating \\n. If the lines list does meet this constraint the
1269
add routine may error or may succeed - but you will be unable to
1270
read the data back accurately. (Checking the lines have been split
1271
correctly is expensive and extremely unlikely to catch bugs so it
1272
is not done at runtime unless check_content is True.)
1273
:param parent_texts: An optional dictionary containing the opaque
1274
representations of some or all of the parents of version_id to
1275
allow delta optimisations. VERY IMPORTANT: the texts must be those
1276
returned by add_lines or data corruption can be caused.
1277
:param left_matching_blocks: a hint about which areas are common
1278
between the text and its left-hand-parent. The format is
1279
the SequenceMatcher.get_matching_blocks format.
1280
:param nostore_sha: Raise ExistingContent and do not add the lines to
1281
the versioned file if the digest of the lines matches this.
1282
:param random_id: If True a random id has been selected rather than
1283
an id determined by some deterministic process such as a converter
1284
from a foreign VCS. When True the backend may choose not to check
1285
for uniqueness of the resulting key within the versioned file, so
1286
this should only be done when the result is expected to be unique
1288
:param check_content: If True, the lines supplied are verified to be
1289
bytestrings that are correctly formed lines.
1290
:return: The text sha1, the number of bytes in the text, and an opaque
1291
representation of the inserted version which can be provided
1292
back to future add_lines calls in the parent_texts dictionary.
1294
self._index._check_write_ok()
1295
self._check_add(key, lines, random_id, check_content)
1297
# The caller might pass None if there is no graph data, but kndx
1298
# indexes can't directly store that, so we give them
1299
# an empty tuple instead.
1301
# double handling for now. Make it work until then.
1302
length = sum(map(len, lines))
1303
record = ChunkedContentFactory(key, parents, None, lines)
1304
sha1 = list(self._insert_record_stream([record], random_id=random_id,
1305
nostore_sha=nostore_sha))[0]
1306
return sha1, length, None
1308
def add_fallback_versioned_files(self, a_versioned_files):
1309
"""Add a source of texts for texts not present in this knit.
1311
:param a_versioned_files: A VersionedFiles object.
1313
self._immediate_fallback_vfs.append(a_versioned_files)
1315
def annotate(self, key):
1316
"""See VersionedFiles.annotate."""
1317
ann = annotate.Annotator(self)
1318
return ann.annotate_flat(key)
1320
def get_annotator(self):
1321
return annotate.Annotator(self)
1323
def check(self, progress_bar=None, keys=None):
1324
"""See VersionedFiles.check()."""
1327
for record in self.get_record_stream(keys, 'unordered', True):
1328
record.get_bytes_as('fulltext')
1330
return self.get_record_stream(keys, 'unordered', True)
1332
def clear_cache(self):
1333
"""See VersionedFiles.clear_cache()"""
1334
self._group_cache.clear()
1335
self._index._graph_index.clear_cache()
1336
self._index._int_cache.clear()
1338
def _check_add(self, key, lines, random_id, check_content):
1339
"""check that version_id and lines are safe to add."""
1340
version_id = key[-1]
1341
if version_id is not None:
1342
if osutils.contains_whitespace(version_id):
1343
raise errors.InvalidRevisionId(version_id, self)
1344
self.check_not_reserved_id(version_id)
1345
# TODO: If random_id==False and the key is already present, we should
1346
# probably check that the existing content is identical to what is
1347
# being inserted, and otherwise raise an exception. This would make
1348
# the bundle code simpler.
1350
self._check_lines_not_unicode(lines)
1351
self._check_lines_are_lines(lines)
1353
def get_parent_map(self, keys):
1354
"""Get a map of the graph parents of keys.
1356
:param keys: The keys to look up parents for.
1357
:return: A mapping from keys to parents. Absent keys are absent from
1360
return self._get_parent_map_with_sources(keys)[0]
1362
def _get_parent_map_with_sources(self, keys):
1363
"""Get a map of the parents of keys.
1365
:param keys: The keys to look up parents for.
1366
:return: A tuple. The first element is a mapping from keys to parents.
1367
Absent keys are absent from the mapping. The second element is a
1368
list with the locations each key was found in. The first element
1369
is the in-this-knit parents, the second the first fallback source,
1373
sources = [self._index] + self._immediate_fallback_vfs
1376
for source in sources:
1379
new_result = source.get_parent_map(missing)
1380
source_results.append(new_result)
1381
result.update(new_result)
1382
missing.difference_update(set(new_result))
1383
return result, source_results
1385
def _get_blocks(self, read_memos):
1386
"""Get GroupCompressBlocks for the given read_memos.
1388
:returns: a series of (read_memo, block) pairs, in the order they were
1392
for read_memo in read_memos:
1394
block = self._group_cache[read_memo]
1398
cached[read_memo] = block
1400
not_cached_seen = set()
1401
for read_memo in read_memos:
1402
if read_memo in cached:
1403
# Don't fetch what we already have
1405
if read_memo in not_cached_seen:
1406
# Don't try to fetch the same data twice
1408
not_cached.append(read_memo)
1409
not_cached_seen.add(read_memo)
1410
raw_records = self._access.get_raw_records(not_cached)
1411
for read_memo in read_memos:
1413
yield read_memo, cached[read_memo]
1415
# Read the block, and cache it.
1416
zdata = next(raw_records)
1417
block = GroupCompressBlock.from_bytes(zdata)
1418
self._group_cache[read_memo] = block
1419
cached[read_memo] = block
1420
yield read_memo, block
1422
def get_missing_compression_parent_keys(self):
1423
"""Return the keys of missing compression parents.
1425
Missing compression parents occur when a record stream was missing
1426
basis texts, or a index was scanned that had missing basis texts.
1428
# GroupCompress cannot currently reference texts that are not in the
1429
# group, so this is valid for now
1432
def get_record_stream(self, keys, ordering, include_delta_closure):
1433
"""Get a stream of records for keys.
1435
:param keys: The keys to include.
1436
:param ordering: Either 'unordered' or 'topological'. A topologically
1437
sorted stream has compression parents strictly before their
1439
:param include_delta_closure: If True then the closure across any
1440
compression parents will be included (in the opaque data).
1441
:return: An iterator of ContentFactory objects, each of which is only
1442
valid until the iterator is advanced.
1444
# keys might be a generator
1445
orig_keys = list(keys)
1449
if (not self._index.has_graph
1450
and ordering in ('topological', 'groupcompress')):
1451
# Cannot topological order when no graph has been stored.
1452
# but we allow 'as-requested' or 'unordered'
1453
ordering = 'unordered'
1455
remaining_keys = keys
1458
keys = set(remaining_keys)
1459
for content_factory in self._get_remaining_record_stream(keys,
1460
orig_keys, ordering, include_delta_closure):
1461
remaining_keys.discard(content_factory.key)
1462
yield content_factory
1464
except errors.RetryWithNewPacks as e:
1465
self._access.reload_or_raise(e)
1467
def _find_from_fallback(self, missing):
1468
"""Find whatever keys you can from the fallbacks.
1470
:param missing: A set of missing keys. This set will be mutated as keys
1471
are found from a fallback_vfs
1472
:return: (parent_map, key_to_source_map, source_results)
1473
parent_map the overall key => parent_keys
1474
key_to_source_map a dict from {key: source}
1475
source_results a list of (source: keys)
1478
key_to_source_map = {}
1480
for source in self._immediate_fallback_vfs:
1483
source_parents = source.get_parent_map(missing)
1484
parent_map.update(source_parents)
1485
source_parents = list(source_parents)
1486
source_results.append((source, source_parents))
1487
key_to_source_map.update((key, source) for key in source_parents)
1488
missing.difference_update(source_parents)
1489
return parent_map, key_to_source_map, source_results
1491
def _get_ordered_source_keys(self, ordering, parent_map, key_to_source_map):
1492
"""Get the (source, [keys]) list.
1494
The returned objects should be in the order defined by 'ordering',
1495
which can weave between different sources.
1497
:param ordering: Must be one of 'topological' or 'groupcompress'
1498
:return: List of [(source, [keys])] tuples, such that all keys are in
1499
the defined order, regardless of source.
1501
if ordering == 'topological':
1502
present_keys = tsort.topo_sort(parent_map)
1504
# ordering == 'groupcompress'
1505
# XXX: This only optimizes for the target ordering. We may need
1506
# to balance that with the time it takes to extract
1507
# ordering, by somehow grouping based on
1508
# locations[key][0:3]
1509
present_keys = sort_gc_optimal(parent_map)
1510
# Now group by source:
1512
current_source = None
1513
for key in present_keys:
1514
source = key_to_source_map.get(key, self)
1515
if source is not current_source:
1516
source_keys.append((source, []))
1517
current_source = source
1518
source_keys[-1][1].append(key)
1521
def _get_as_requested_source_keys(self, orig_keys, locations, unadded_keys,
1524
current_source = None
1525
for key in orig_keys:
1526
if key in locations or key in unadded_keys:
1528
elif key in key_to_source_map:
1529
source = key_to_source_map[key]
1532
if source is not current_source:
1533
source_keys.append((source, []))
1534
current_source = source
1535
source_keys[-1][1].append(key)
1538
def _get_io_ordered_source_keys(self, locations, unadded_keys,
1541
# This is the group the bytes are stored in, followed by the
1542
# location in the group
1543
return locations[key][0]
1544
# We don't have an ordering for keys in the in-memory object, but
1545
# lets process the in-memory ones first.
1546
present_keys = list(unadded_keys)
1547
present_keys.extend(sorted(locations, key=get_group))
1548
# Now grab all of the ones from other sources
1549
source_keys = [(self, present_keys)]
1550
source_keys.extend(source_result)
1553
def _get_remaining_record_stream(self, keys, orig_keys, ordering,
1554
include_delta_closure):
1555
"""Get a stream of records for keys.
1557
:param keys: The keys to include.
1558
:param ordering: one of 'unordered', 'topological', 'groupcompress' or
1560
:param include_delta_closure: If True then the closure across any
1561
compression parents will be included (in the opaque data).
1562
:return: An iterator of ContentFactory objects, each of which is only
1563
valid until the iterator is advanced.
1566
locations = self._index.get_build_details(keys)
1567
unadded_keys = set(self._unadded_refs).intersection(keys)
1568
missing = keys.difference(locations)
1569
missing.difference_update(unadded_keys)
1570
(fallback_parent_map, key_to_source_map,
1571
source_result) = self._find_from_fallback(missing)
1572
if ordering in ('topological', 'groupcompress'):
1573
# would be better to not globally sort initially but instead
1574
# start with one key, recurse to its oldest parent, then grab
1575
# everything in the same group, etc.
1576
parent_map = dict((key, details[2]) for key, details in
1577
viewitems(locations))
1578
for key in unadded_keys:
1579
parent_map[key] = self._unadded_refs[key]
1580
parent_map.update(fallback_parent_map)
1581
source_keys = self._get_ordered_source_keys(ordering, parent_map,
1583
elif ordering == 'as-requested':
1584
source_keys = self._get_as_requested_source_keys(orig_keys,
1585
locations, unadded_keys, key_to_source_map)
1587
# We want to yield the keys in a semi-optimal (read-wise) ordering.
1588
# Otherwise we thrash the _group_cache and destroy performance
1589
source_keys = self._get_io_ordered_source_keys(locations,
1590
unadded_keys, source_result)
1592
yield AbsentContentFactory(key)
1593
# Batch up as many keys as we can until either:
1594
# - we encounter an unadded ref, or
1595
# - we run out of keys, or
1596
# - the total bytes to retrieve for this batch > BATCH_SIZE
1597
batcher = _BatchingBlockFetcher(self, locations,
1598
get_compressor_settings=self._get_compressor_settings)
1599
for source, keys in source_keys:
1602
if key in self._unadded_refs:
1603
# Flush batch, then yield unadded ref from
1605
for factory in batcher.yield_factories(full_flush=True):
1607
bytes, sha1 = self._compressor.extract(key)
1608
parents = self._unadded_refs[key]
1609
yield FulltextContentFactory(key, parents, sha1, bytes)
1611
if batcher.add_key(key) > BATCH_SIZE:
1612
# Ok, this batch is big enough. Yield some results.
1613
for factory in batcher.yield_factories():
1616
for factory in batcher.yield_factories(full_flush=True):
1618
for record in source.get_record_stream(keys, ordering,
1619
include_delta_closure):
1621
for factory in batcher.yield_factories(full_flush=True):
1624
def get_sha1s(self, keys):
1625
"""See VersionedFiles.get_sha1s()."""
1627
for record in self.get_record_stream(keys, 'unordered', True):
1628
if record.sha1 != None:
1629
result[record.key] = record.sha1
1631
if record.storage_kind != 'absent':
1632
result[record.key] = osutils.sha_string(
1633
record.get_bytes_as('fulltext'))
1636
def insert_record_stream(self, stream):
1637
"""Insert a record stream into this container.
1639
:param stream: A stream of records to insert.
1641
:seealso VersionedFiles.get_record_stream:
1643
# XXX: Setting random_id=True makes
1644
# test_insert_record_stream_existing_keys fail for groupcompress and
1645
# groupcompress-nograph, this needs to be revisited while addressing
1646
# 'bzr branch' performance issues.
1647
for _ in self._insert_record_stream(stream, random_id=False):
1650
def _get_compressor_settings(self):
1651
if self._max_bytes_to_index is None:
1652
# TODO: VersionedFiles don't know about their containing
1653
# repository, so they don't have much of an idea about their
1654
# location. So for now, this is only a global option.
1655
c = config.GlobalConfig()
1656
val = c.get_user_option('bzr.groupcompress.max_bytes_to_index')
1660
except ValueError as e:
1661
trace.warning('Value for '
1662
'"bzr.groupcompress.max_bytes_to_index"'
1663
' %r is not an integer'
1667
val = self._DEFAULT_MAX_BYTES_TO_INDEX
1668
self._max_bytes_to_index = val
1669
return {'max_bytes_to_index': self._max_bytes_to_index}
1671
def _make_group_compressor(self):
1672
return GroupCompressor(self._get_compressor_settings())
1674
def _insert_record_stream(self, stream, random_id=False, nostore_sha=None,
1676
"""Internal core to insert a record stream into this container.
1678
This helper function has a different interface than insert_record_stream
1679
to allow add_lines to be minimal, but still return the needed data.
1681
:param stream: A stream of records to insert.
1682
:param nostore_sha: If the sha1 of a given text matches nostore_sha,
1683
raise ExistingContent, rather than committing the new text.
1684
:param reuse_blocks: If the source is streaming from
1685
groupcompress-blocks, just insert the blocks as-is, rather than
1686
expanding the texts and inserting again.
1687
:return: An iterator over the sha1 of the inserted records.
1688
:seealso insert_record_stream:
1692
def get_adapter(adapter_key):
1694
return adapters[adapter_key]
1696
adapter_factory = adapter_registry.get(adapter_key)
1697
adapter = adapter_factory(self)
1698
adapters[adapter_key] = adapter
1700
# This will go up to fulltexts for gc to gc fetching, which isn't
1702
self._compressor = self._make_group_compressor()
1703
self._unadded_refs = {}
1706
bytes_len, chunks = self._compressor.flush().to_chunks()
1707
self._compressor = self._make_group_compressor()
1708
# Note: At this point we still have 1 copy of the fulltext (in
1709
# record and the var 'bytes'), and this generates 2 copies of
1710
# the compressed text (one for bytes, one in chunks)
1711
# TODO: Push 'chunks' down into the _access api, so that we don't
1712
# have to double compressed memory here
1713
# TODO: Figure out how to indicate that we would be happy to free
1714
# the fulltext content at this point. Note that sometimes we
1715
# will want it later (streaming CHK pages), but most of the
1716
# time we won't (everything else)
1717
data = b''.join(chunks)
1719
index, start, length = self._access.add_raw_records(
1720
[(None, len(data))], data)[0]
1722
for key, reads, refs in keys_to_add:
1723
nodes.append((key, b"%d %d %s" % (start, length, reads), refs))
1724
self._index.add_records(nodes, random_id=random_id)
1725
self._unadded_refs = {}
1729
max_fulltext_len = 0
1730
max_fulltext_prefix = None
1731
insert_manager = None
1734
# XXX: TODO: remove this, it is just for safety checking for now
1735
inserted_keys = set()
1736
reuse_this_block = reuse_blocks
1737
for record in stream:
1738
# Raise an error when a record is missing.
1739
if record.storage_kind == 'absent':
1740
raise errors.RevisionNotPresent(record.key, self)
1742
if record.key in inserted_keys:
1743
trace.note(gettext('Insert claimed random_id=True,'
1744
' but then inserted %r two times'), record.key)
1746
inserted_keys.add(record.key)
1748
# If the reuse_blocks flag is set, check to see if we can just
1749
# copy a groupcompress block as-is.
1750
# We only check on the first record (groupcompress-block) not
1751
# on all of the (groupcompress-block-ref) entries.
1752
# The reuse_this_block flag is then kept for as long as
1753
if record.storage_kind == 'groupcompress-block':
1754
# Check to see if we really want to re-use this block
1755
insert_manager = record._manager
1756
reuse_this_block = insert_manager.check_is_well_utilized()
1758
reuse_this_block = False
1759
if reuse_this_block:
1760
# We still want to reuse this block
1761
if record.storage_kind == 'groupcompress-block':
1762
# Insert the raw block into the target repo
1763
insert_manager = record._manager
1764
bytes = record._manager._block.to_bytes()
1765
_, start, length = self._access.add_raw_records(
1766
[(None, len(bytes))], bytes)[0]
1769
block_length = length
1770
if record.storage_kind in ('groupcompress-block',
1771
'groupcompress-block-ref'):
1772
if insert_manager is None:
1773
raise AssertionError('No insert_manager set')
1774
if insert_manager is not record._manager:
1775
raise AssertionError('insert_manager does not match'
1776
' the current record, we cannot be positive'
1777
' that the appropriate content was inserted.'
1779
value = b"%d %d %d %d" % (block_start, block_length,
1780
record._start, record._end)
1781
nodes = [(record.key, value, (record.parents,))]
1782
# TODO: Consider buffering up many nodes to be added, not
1783
# sure how much overhead this has, but we're seeing
1784
# ~23s / 120s in add_records calls
1785
self._index.add_records(nodes, random_id=random_id)
1788
bytes = record.get_bytes_as('fulltext')
1789
except errors.UnavailableRepresentation:
1790
adapter_key = record.storage_kind, 'fulltext'
1791
adapter = get_adapter(adapter_key)
1792
bytes = adapter.get_bytes(record)
1793
if len(record.key) > 1:
1794
prefix = record.key[0]
1795
soft = (prefix == last_prefix)
1799
if max_fulltext_len < len(bytes):
1800
max_fulltext_len = len(bytes)
1801
max_fulltext_prefix = prefix
1802
(found_sha1, start_point, end_point,
1803
type) = self._compressor.compress(record.key,
1804
bytes, record.sha1, soft=soft,
1805
nostore_sha=nostore_sha)
1806
# delta_ratio = float(len(bytes)) / (end_point - start_point)
1807
# Check if we want to continue to include that text
1808
if (prefix == max_fulltext_prefix
1809
and end_point < 2 * max_fulltext_len):
1810
# As long as we are on the same file_id, we will fill at least
1811
# 2 * max_fulltext_len
1812
start_new_block = False
1813
elif end_point > 4*1024*1024:
1814
start_new_block = True
1815
elif (prefix is not None and prefix != last_prefix
1816
and end_point > 2*1024*1024):
1817
start_new_block = True
1819
start_new_block = False
1820
last_prefix = prefix
1822
self._compressor.pop_last()
1824
max_fulltext_len = len(bytes)
1825
(found_sha1, start_point, end_point,
1826
type) = self._compressor.compress(record.key, bytes,
1828
if record.key[-1] is None:
1829
key = record.key[:-1] + (b'sha1:' + found_sha1,)
1832
self._unadded_refs[key] = record.parents
1834
as_st = static_tuple.StaticTuple.from_sequence
1835
if record.parents is not None:
1836
parents = as_st([as_st(p) for p in record.parents])
1839
refs = static_tuple.StaticTuple(parents)
1841
(key, b'%d %d' % (start_point, end_point), refs))
1842
if len(keys_to_add):
1844
self._compressor = None
1846
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1847
"""Iterate over the lines in the versioned files from keys.
1849
This may return lines from other keys. Each item the returned
1850
iterator yields is a tuple of a line and a text version that that line
1851
is present in (not introduced in).
1853
Ordering of results is in whatever order is most suitable for the
1854
underlying storage format.
1856
If a progress bar is supplied, it may be used to indicate progress.
1857
The caller is responsible for cleaning up progress bars (because this
1861
* Lines are normalised by the underlying store: they will all have \n
1863
* Lines are returned in arbitrary order.
1865
:return: An iterator over (line, key).
1869
# we don't care about inclusions, the caller cares.
1870
# but we need to setup a list of records to visit.
1871
# we need key, position, length
1872
for key_idx, record in enumerate(self.get_record_stream(keys,
1873
'unordered', True)):
1874
# XXX: todo - optimise to use less than full texts.
1877
pb.update('Walking content', key_idx, total)
1878
if record.storage_kind == 'absent':
1879
raise errors.RevisionNotPresent(key, self)
1880
lines = osutils.split_lines(record.get_bytes_as('fulltext'))
1884
pb.update('Walking content', total, total)
1887
"""See VersionedFiles.keys."""
1888
if 'evil' in debug.debug_flags:
1889
trace.mutter_callsite(2, "keys scales with size of history")
1890
sources = [self._index] + self._immediate_fallback_vfs
1892
for source in sources:
1893
result.update(source.keys())
1897
class _GCBuildDetails(object):
1898
"""A blob of data about the build details.
1900
This stores the minimal data, which then allows compatibility with the old
1901
api, without taking as much memory.
1904
__slots__ = ('_index', '_group_start', '_group_end', '_basis_end',
1905
'_delta_end', '_parents')
1908
compression_parent = None
1910
def __init__(self, parents, position_info):
1911
self._parents = parents
1912
(self._index, self._group_start, self._group_end, self._basis_end,
1913
self._delta_end) = position_info
1916
return '%s(%s, %s)' % (self.__class__.__name__,
1917
self.index_memo, self._parents)
1920
def index_memo(self):
1921
return (self._index, self._group_start, self._group_end,
1922
self._basis_end, self._delta_end)
1925
def record_details(self):
1926
return static_tuple.StaticTuple(self.method, None)
1928
def __getitem__(self, offset):
1929
"""Compatibility thunk to act like a tuple."""
1931
return self.index_memo
1933
return self.compression_parent # Always None
1935
return self._parents
1937
return self.record_details
1939
raise IndexError('offset out of range')
1945
class _GCGraphIndex(object):
1946
"""Mapper from GroupCompressVersionedFiles needs into GraphIndex storage."""
1948
def __init__(self, graph_index, is_locked, parents=True,
1949
add_callback=None, track_external_parent_refs=False,
1950
inconsistency_fatal=True, track_new_keys=False):
1951
"""Construct a _GCGraphIndex on a graph_index.
1953
:param graph_index: An implementation of breezy.index.GraphIndex.
1954
:param is_locked: A callback, returns True if the index is locked and
1956
:param parents: If True, record knits parents, if not do not record
1958
:param add_callback: If not None, allow additions to the index and call
1959
this callback with a list of added GraphIndex nodes:
1960
[(node, value, node_refs), ...]
1961
:param track_external_parent_refs: As keys are added, keep track of the
1962
keys they reference, so that we can query get_missing_parents(),
1964
:param inconsistency_fatal: When asked to add records that are already
1965
present, and the details are inconsistent with the existing
1966
record, raise an exception instead of warning (and skipping the
1969
self._add_callback = add_callback
1970
self._graph_index = graph_index
1971
self._parents = parents
1972
self.has_graph = parents
1973
self._is_locked = is_locked
1974
self._inconsistency_fatal = inconsistency_fatal
1975
# GroupCompress records tend to have the same 'group' start + offset
1976
# repeated over and over, this creates a surplus of ints
1977
self._int_cache = {}
1978
if track_external_parent_refs:
1979
self._key_dependencies = _KeyRefs(
1980
track_new_keys=track_new_keys)
1982
self._key_dependencies = None
1984
def add_records(self, records, random_id=False):
1985
"""Add multiple records to the index.
1987
This function does not insert data into the Immutable GraphIndex
1988
backing the KnitGraphIndex, instead it prepares data for insertion by
1989
the caller and checks that it is safe to insert then calls
1990
self._add_callback with the prepared GraphIndex nodes.
1992
:param records: a list of tuples:
1993
(key, options, access_memo, parents).
1994
:param random_id: If True the ids being added were randomly generated
1995
and no check for existence will be performed.
1997
if not self._add_callback:
1998
raise errors.ReadOnlyError(self)
1999
# we hope there are no repositories with inconsistent parentage
2004
for (key, value, refs) in records:
2005
if not self._parents:
2009
raise knit.KnitCorrupt(self,
2010
"attempt to add node with parents "
2011
"in parentless index.")
2014
keys[key] = (value, refs)
2017
present_nodes = self._get_entries(keys)
2018
for (index, key, value, node_refs) in present_nodes:
2019
# Sometimes these are passed as a list rather than a tuple
2020
node_refs = static_tuple.as_tuples(node_refs)
2021
passed = static_tuple.as_tuples(keys[key])
2022
if node_refs != passed[1]:
2023
details = '%s %s %s' % (key, (value, node_refs), passed)
2024
if self._inconsistency_fatal:
2025
raise knit.KnitCorrupt(self, "inconsistent details"
2026
" in add_records: %s" %
2029
trace.warning("inconsistent details in skipped"
2030
" record: %s", details)
2036
for key, (value, node_refs) in viewitems(keys):
2037
result.append((key, value, node_refs))
2039
for key, (value, node_refs) in viewitems(keys):
2040
result.append((key, value))
2042
key_dependencies = self._key_dependencies
2043
if key_dependencies is not None:
2045
for key, value, refs in records:
2047
key_dependencies.add_references(key, parents)
2049
for key, value, refs in records:
2050
new_keys.add_key(key)
2051
self._add_callback(records)
2053
def _check_read(self):
2054
"""Raise an exception if reads are not permitted."""
2055
if not self._is_locked():
2056
raise errors.ObjectNotLocked(self)
2058
def _check_write_ok(self):
2059
"""Raise an exception if writes are not permitted."""
2060
if not self._is_locked():
2061
raise errors.ObjectNotLocked(self)
2063
def _get_entries(self, keys, check_present=False):
2064
"""Get the entries for keys.
2066
Note: Callers are responsible for checking that the index is locked
2067
before calling this method.
2069
:param keys: An iterable of index key tuples.
2074
for node in self._graph_index.iter_entries(keys):
2076
found_keys.add(node[1])
2078
# adapt parentless index to the rest of the code.
2079
for node in self._graph_index.iter_entries(keys):
2080
yield node[0], node[1], node[2], ()
2081
found_keys.add(node[1])
2083
missing_keys = keys.difference(found_keys)
2085
raise errors.RevisionNotPresent(missing_keys.pop(), self)
2087
def find_ancestry(self, keys):
2088
"""See CombinedGraphIndex.find_ancestry"""
2089
return self._graph_index.find_ancestry(keys, 0)
2091
def get_parent_map(self, keys):
2092
"""Get a map of the parents of keys.
2094
:param keys: The keys to look up parents for.
2095
:return: A mapping from keys to parents. Absent keys are absent from
2099
nodes = self._get_entries(keys)
2103
result[node[1]] = node[3][0]
2106
result[node[1]] = None
2109
def get_missing_parents(self):
2110
"""Return the keys of missing parents."""
2111
# Copied from _KnitGraphIndex.get_missing_parents
2112
# We may have false positives, so filter those out.
2113
self._key_dependencies.satisfy_refs_for_keys(
2114
self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
2115
return frozenset(self._key_dependencies.get_unsatisfied_refs())
2117
def get_build_details(self, keys):
2118
"""Get the various build details for keys.
2120
Ghosts are omitted from the result.
2122
:param keys: An iterable of keys.
2123
:return: A dict of key:
2124
(index_memo, compression_parent, parents, record_details).
2126
* index_memo: opaque structure to pass to read_records to extract
2128
* compression_parent: Content that this record is built upon, may
2130
* parents: Logical parents of this node
2131
* record_details: extra information about the content which needs
2132
to be passed to Factory.parse_record
2136
entries = self._get_entries(keys)
2137
for entry in entries:
2139
if not self._parents:
2142
parents = entry[3][0]
2143
details = _GCBuildDetails(parents, self._node_to_position(entry))
2144
result[key] = details
2148
"""Get all the keys in the collection.
2150
The keys are not ordered.
2153
return [node[1] for node in self._graph_index.iter_all_entries()]
2155
def _node_to_position(self, node):
2156
"""Convert an index value to position details."""
2157
bits = node[2].split(b' ')
2158
# It would be nice not to read the entire gzip.
2159
# start and stop are put into _int_cache because they are very common.
2160
# They define the 'group' that an entry is in, and many groups can have
2161
# thousands of objects.
2162
# Branching Launchpad, for example, saves ~600k integers, at 12 bytes
2163
# each, or about 7MB. Note that it might be even more when you consider
2164
# how PyInt is allocated in separate slabs. And you can't return a slab
2165
# to the OS if even 1 int on it is in use. Note though that Python uses
2166
# a LIFO when re-using PyInt slots, which might cause more
2168
start = int(bits[0])
2169
start = self._int_cache.setdefault(start, start)
2171
stop = self._int_cache.setdefault(stop, stop)
2172
basis_end = int(bits[2])
2173
delta_end = int(bits[3])
2174
# We can't use StaticTuple here, because node[0] is a BTreeGraphIndex
2176
return (node[0], start, stop, basis_end, delta_end)
2178
def scan_unvalidated_index(self, graph_index):
2179
"""Inform this _GCGraphIndex that there is an unvalidated index.
2181
This allows this _GCGraphIndex to keep track of any missing
2182
compression parents we may want to have filled in to make those
2183
indices valid. It also allows _GCGraphIndex to track any new keys.
2185
:param graph_index: A GraphIndex
2187
key_dependencies = self._key_dependencies
2188
if key_dependencies is None:
2190
for node in graph_index.iter_all_entries():
2191
# Add parent refs from graph_index (and discard parent refs
2192
# that the graph_index has).
2193
key_dependencies.add_references(node[1], node[3][0])
2196
from ._groupcompress_py import (
2198
apply_delta_to_source,
2201
decode_copy_instruction,
2205
from ._groupcompress_pyx import (
2207
apply_delta_to_source,
2212
GroupCompressor = PyrexGroupCompressor
2213
except ImportError as e:
2214
osutils.failed_to_load_extension(e)
2215
GroupCompressor = PythonGroupCompressor
added
removed
breezy/bzr/groupcompress.py
