1
# Copyright (C) 2008, 2009 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."""
36
from bzrlib.btree_index import BTreeBuilder
37
from bzrlib.lru_cache import LRUSizeCache
38
from bzrlib.tsort import topo_sort
39
from bzrlib.versionedfile import (
42
ChunkedContentFactory,
43
FulltextContentFactory,
47
# Minimum number of uncompressed bytes to try fetch at once when retrieving
48
# groupcompress blocks.
51
_USE_LZMA = False and (pylzma is not None)
53
# osutils.sha_string('')
54
_null_sha1 = 'da39a3ee5e6b4b0d3255bfef95601890afd80709'
56
def sort_gc_optimal(parent_map):
57
"""Sort and group the keys in parent_map into groupcompress order.
59
groupcompress is defined (currently) as reverse-topological order, grouped
62
:return: A sorted-list of keys
64
# groupcompress ordering is approximately reverse topological,
65
# properly grouped by file-id.
67
for key, value in parent_map.iteritems():
68
if isinstance(key, str) or len(key) == 1:
73
per_prefix_map[prefix][key] = value
75
per_prefix_map[prefix] = {key: value}
78
for prefix in sorted(per_prefix_map):
79
present_keys.extend(reversed(topo_sort(per_prefix_map[prefix])))
83
# The max zlib window size is 32kB, so if we set 'max_size' output of the
84
# decompressor to the requested bytes + 32kB, then we should guarantee
85
# num_bytes coming out.
86
_ZLIB_DECOMP_WINDOW = 32*1024
88
class GroupCompressBlock(object):
89
"""An object which maintains the internal structure of the compressed data.
91
This tracks the meta info (start of text, length, type, etc.)
94
# Group Compress Block v1 Zlib
95
GCB_HEADER = 'gcb1z\n'
96
# Group Compress Block v1 Lzma
97
GCB_LZ_HEADER = 'gcb1l\n'
98
GCB_KNOWN_HEADERS = (GCB_HEADER, GCB_LZ_HEADER)
101
# map by key? or just order in file?
102
self._compressor_name = None
103
self._z_content = None
104
self._z_content_decompressor = None
105
self._z_content_length = None
106
self._content_length = None
108
self._content_chunks = None
111
# This is the maximum number of bytes this object will reference if
112
# everything is decompressed. However, if we decompress less than
113
# everything... (this would cause some problems for LRUSizeCache)
114
return self._content_length + self._z_content_length
116
def _ensure_content(self, num_bytes=None):
117
"""Make sure that content has been expanded enough.
119
:param num_bytes: Ensure that we have extracted at least num_bytes of
120
content. If None, consume everything
122
# TODO: If we re-use the same content block at different times during
123
# get_record_stream(), it is possible that the first pass will
124
# get inserted, triggering an extract/_ensure_content() which
125
# will get rid of _z_content. And then the next use of the block
126
# will try to access _z_content (to send it over the wire), and
127
# fail because it is already extracted. Consider never releasing
128
# _z_content because of this.
129
if num_bytes is None:
130
num_bytes = self._content_length
131
elif (self._content_length is not None
132
and num_bytes > self._content_length):
133
raise AssertionError(
134
'requested num_bytes (%d) > content length (%d)'
135
% (num_bytes, self._content_length))
136
# Expand the content if required
137
if self._content is None:
138
if self._content_chunks is not None:
139
self._content = ''.join(self._content_chunks)
140
self._content_chunks = None
141
if self._content is None:
142
if self._z_content is None:
143
raise AssertionError('No content to decompress')
144
if self._z_content == '':
146
elif self._compressor_name == 'lzma':
147
# We don't do partial lzma decomp yet
148
self._content = pylzma.decompress(self._z_content)
149
elif self._compressor_name == 'zlib':
150
# Start a zlib decompressor
151
if num_bytes is None:
152
self._content = zlib.decompress(self._z_content)
154
self._z_content_decompressor = zlib.decompressobj()
155
# Seed the decompressor with the uncompressed bytes, so
156
# that the rest of the code is simplified
157
self._content = self._z_content_decompressor.decompress(
158
self._z_content, num_bytes + _ZLIB_DECOMP_WINDOW)
160
raise AssertionError('Unknown compressor: %r'
161
% self._compressor_name)
162
# Any bytes remaining to be decompressed will be in the decompressors
165
# Do we have enough bytes already?
166
if num_bytes is not None and len(self._content) >= num_bytes:
168
if num_bytes is None and self._z_content_decompressor is None:
169
# We must have already decompressed everything
171
# If we got this far, and don't have a decompressor, something is wrong
172
if self._z_content_decompressor is None:
173
raise AssertionError(
174
'No decompressor to decompress %d bytes' % num_bytes)
175
remaining_decomp = self._z_content_decompressor.unconsumed_tail
176
if num_bytes is None:
178
# We don't know how much is left, but we'll decompress it all
179
self._content += self._z_content_decompressor.decompress(
181
# Note: There's what I consider a bug in zlib.decompressobj
182
# If you pass back in the entire unconsumed_tail, only
183
# this time you don't pass a max-size, it doesn't
184
# change the unconsumed_tail back to None/''.
185
# However, we know we are done with the whole stream
186
self._z_content_decompressor = None
187
# XXX: Why is this the only place in this routine we set this?
188
self._content_length = len(self._content)
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 = bytes[pos:]
229
def from_bytes(cls, bytes):
231
if bytes[:6] not in cls.GCB_KNOWN_HEADERS:
232
raise ValueError('bytes did not start with any of %r'
233
% (cls.GCB_KNOWN_HEADERS,))
234
# XXX: why not testing the whole header ?
236
out._compressor_name = 'zlib'
237
elif bytes[4] == 'l':
238
out._compressor_name = 'lzma'
240
raise ValueError('unknown compressor: %r' % (bytes,))
241
out._parse_bytes(bytes, 6)
244
def extract(self, key, start, end, sha1=None):
245
"""Extract the text for a specific key.
247
:param key: The label used for this content
248
:param sha1: TODO (should we validate only when sha1 is supplied?)
249
:return: The bytes for the content
251
if start == end == 0:
253
self._ensure_content(end)
254
# The bytes are 'f' or 'd' for the type, then a variable-length
255
# base128 integer for the content size, then the actual content
256
# We know that the variable-length integer won't be longer than 5
257
# bytes (it takes 5 bytes to encode 2^32)
258
c = self._content[start]
263
raise ValueError('Unknown content control code: %s'
266
content_len, len_len = decode_base128_int(
267
self._content[start + 1:start + 6])
268
content_start = start + 1 + len_len
269
if end != content_start + content_len:
270
raise ValueError('end != len according to field header'
271
' %s != %s' % (end, content_start + content_len))
273
bytes = self._content[content_start:end]
275
bytes = apply_delta_to_source(self._content, content_start, end)
278
def set_chunked_content(self, content_chunks, length):
279
"""Set the content of this block to the given chunks."""
280
# If we have lots of short lines, it is may be more efficient to join
281
# the content ahead of time. If the content is <10MiB, we don't really
282
# care about the extra memory consumption, so we can just pack it and
283
# be done. However, timing showed 18s => 17.9s for repacking 1k revs of
284
# mysql, which is below the noise margin
285
self._content_length = length
286
self._content_chunks = content_chunks
288
self._z_content = None
290
def set_content(self, content):
291
"""Set the content of this block."""
292
self._content_length = len(content)
293
self._content = content
294
self._z_content = None
296
def _create_z_content_using_lzma(self):
297
if self._content_chunks is not None:
298
self._content = ''.join(self._content_chunks)
299
self._content_chunks = None
300
if self._content is None:
301
raise AssertionError('Nothing to compress')
302
self._z_content = pylzma.compress(self._content)
303
self._z_content_length = len(self._z_content)
305
def _create_z_content_from_chunks(self):
306
compressor = zlib.compressobj(zlib.Z_DEFAULT_COMPRESSION)
307
compressed_chunks = map(compressor.compress, self._content_chunks)
308
compressed_chunks.append(compressor.flush())
309
self._z_content = ''.join(compressed_chunks)
310
self._z_content_length = len(self._z_content)
312
def _create_z_content(self):
313
if self._z_content is not None:
316
self._create_z_content_using_lzma()
318
if self._content_chunks is not None:
319
self._create_z_content_from_chunks()
321
self._z_content = zlib.compress(self._content)
322
self._z_content_length = len(self._z_content)
325
"""Encode the information into a byte stream."""
326
self._create_z_content()
328
header = self.GCB_LZ_HEADER
330
header = self.GCB_HEADER
332
'%d\n%d\n' % (self._z_content_length, self._content_length),
335
return ''.join(chunks)
337
def _dump(self, include_text=False):
338
"""Take this block, and spit out a human-readable structure.
340
:param include_text: Inserts also include text bits, chose whether you
341
want this displayed in the dump or not.
342
:return: A dump of the given block. The layout is something like:
343
[('f', length), ('d', delta_length, text_length, [delta_info])]
344
delta_info := [('i', num_bytes, text), ('c', offset, num_bytes),
347
self._ensure_content()
350
while pos < self._content_length:
351
kind = self._content[pos]
353
if kind not in ('f', 'd'):
354
raise ValueError('invalid kind character: %r' % (kind,))
355
content_len, len_len = decode_base128_int(
356
self._content[pos:pos + 5])
358
if content_len + pos > self._content_length:
359
raise ValueError('invalid content_len %d for record @ pos %d'
360
% (content_len, pos - len_len - 1))
361
if kind == 'f': # Fulltext
363
text = self._content[pos:pos+content_len]
364
result.append(('f', content_len, text))
366
result.append(('f', content_len))
367
elif kind == 'd': # Delta
368
delta_content = self._content[pos:pos+content_len]
370
# The first entry in a delta is the decompressed length
371
decomp_len, delta_pos = decode_base128_int(delta_content)
372
result.append(('d', content_len, decomp_len, delta_info))
374
while delta_pos < content_len:
375
c = ord(delta_content[delta_pos])
379
delta_pos) = decode_copy_instruction(delta_content, c,
382
text = self._content[offset:offset+length]
383
delta_info.append(('c', offset, length, text))
385
delta_info.append(('c', offset, length))
386
measured_len += length
389
txt = delta_content[delta_pos:delta_pos+c]
392
delta_info.append(('i', c, txt))
395
if delta_pos != content_len:
396
raise ValueError('Delta consumed a bad number of bytes:'
397
' %d != %d' % (delta_pos, content_len))
398
if measured_len != decomp_len:
399
raise ValueError('Delta claimed fulltext was %d bytes, but'
400
' extraction resulted in %d bytes'
401
% (decomp_len, measured_len))
406
class _LazyGroupCompressFactory(object):
407
"""Yield content from a GroupCompressBlock on demand."""
409
def __init__(self, key, parents, manager, start, end, first):
410
"""Create a _LazyGroupCompressFactory
412
:param key: The key of just this record
413
:param parents: The parents of this key (possibly None)
414
:param gc_block: A GroupCompressBlock object
415
:param start: Offset of the first byte for this record in the
417
:param end: Offset of the byte just after the end of this record
418
(ie, bytes = content[start:end])
419
:param first: Is this the first Factory for the given block?
422
self.parents = parents
424
# Note: This attribute coupled with Manager._factories creates a
425
# reference cycle. Perhaps we would rather use a weakref(), or
426
# find an appropriate time to release the ref. After the first
427
# get_bytes_as call? After Manager.get_record_stream() returns
429
self._manager = manager
431
self.storage_kind = 'groupcompress-block'
433
self.storage_kind = 'groupcompress-block-ref'
439
return '%s(%s, first=%s)' % (self.__class__.__name__,
440
self.key, self._first)
442
def get_bytes_as(self, storage_kind):
443
if storage_kind == self.storage_kind:
445
# wire bytes, something...
446
return self._manager._wire_bytes()
449
if storage_kind in ('fulltext', 'chunked'):
450
if self._bytes is None:
451
# Grab and cache the raw bytes for this entry
452
# and break the ref-cycle with _manager since we don't need it
454
self._manager._prepare_for_extract()
455
block = self._manager._block
456
self._bytes = block.extract(self.key, self._start, self._end)
457
# There are code paths that first extract as fulltext, and then
458
# extract as storage_kind (smart fetch). So we don't break the
459
# refcycle here, but instead in manager.get_record_stream()
460
# self._manager = None
461
if storage_kind == 'fulltext':
465
raise errors.UnavailableRepresentation(self.key, storage_kind,
469
class _LazyGroupContentManager(object):
470
"""This manages a group of _LazyGroupCompressFactory objects."""
472
def __init__(self, block):
474
# We need to preserve the ordering
478
def add_factory(self, key, parents, start, end):
479
if not self._factories:
483
# Note that this creates a reference cycle....
484
factory = _LazyGroupCompressFactory(key, parents, self,
485
start, end, first=first)
486
# max() works here, but as a function call, doing a compare seems to be
487
# significantly faster, timeit says 250ms for max() and 100ms for the
489
if end > self._last_byte:
490
self._last_byte = end
491
self._factories.append(factory)
493
def get_record_stream(self):
494
"""Get a record for all keys added so far."""
495
for factory in self._factories:
497
# Break the ref-cycle
498
factory._bytes = None
499
factory._manager = None
500
# TODO: Consider setting self._factories = None after the above loop,
501
# as it will break the reference cycle
503
def _trim_block(self, last_byte):
504
"""Create a new GroupCompressBlock, with just some of the content."""
505
# None of the factories need to be adjusted, because the content is
506
# located in an identical place. Just that some of the unreferenced
507
# trailing bytes are stripped
508
trace.mutter('stripping trailing bytes from groupcompress block'
509
' %d => %d', self._block._content_length, last_byte)
510
new_block = GroupCompressBlock()
511
self._block._ensure_content(last_byte)
512
new_block.set_content(self._block._content[:last_byte])
513
self._block = new_block
515
def _rebuild_block(self):
516
"""Create a new GroupCompressBlock with only the referenced texts."""
517
compressor = GroupCompressor()
519
old_length = self._block._content_length
521
for factory in self._factories:
522
bytes = factory.get_bytes_as('fulltext')
523
(found_sha1, start_point, end_point,
524
type) = compressor.compress(factory.key, bytes, factory.sha1)
525
# Now update this factory with the new offsets, etc
526
factory.sha1 = found_sha1
527
factory._start = start_point
528
factory._end = end_point
529
self._last_byte = end_point
530
new_block = compressor.flush()
531
# TODO: Should we check that new_block really *is* smaller than the old
532
# block? It seems hard to come up with a method that it would
533
# expand, since we do full compression again. Perhaps based on a
534
# request that ends up poorly ordered?
535
delta = time.time() - tstart
536
self._block = new_block
537
trace.mutter('creating new compressed block on-the-fly in %.3fs'
538
' %d bytes => %d bytes', delta, old_length,
539
self._block._content_length)
541
def _prepare_for_extract(self):
542
"""A _LazyGroupCompressFactory is about to extract to fulltext."""
543
# We expect that if one child is going to fulltext, all will be. This
544
# helps prevent all of them from extracting a small amount at a time.
545
# Which in itself isn't terribly expensive, but resizing 2MB 32kB at a
546
# time (self._block._content) is a little expensive.
547
self._block._ensure_content(self._last_byte)
549
def _check_rebuild_block(self):
550
"""Check to see if our block should be repacked."""
553
for factory in self._factories:
554
total_bytes_used += factory._end - factory._start
555
last_byte_used = max(last_byte_used, factory._end)
556
# If we are using most of the bytes from the block, we have nothing
557
# else to check (currently more that 1/2)
558
if total_bytes_used * 2 >= self._block._content_length:
560
# Can we just strip off the trailing bytes? If we are going to be
561
# transmitting more than 50% of the front of the content, go ahead
562
if total_bytes_used * 2 > last_byte_used:
563
self._trim_block(last_byte_used)
566
# We are using a small amount of the data, and it isn't just packed
567
# nicely at the front, so rebuild the content.
568
# Note: This would be *nicer* as a strip-data-from-group, rather than
569
# building it up again from scratch
570
# It might be reasonable to consider the fulltext sizes for
571
# different bits when deciding this, too. As you may have a small
572
# fulltext, and a trivial delta, and you are just trading around
573
# for another fulltext. If we do a simple 'prune' you may end up
574
# expanding many deltas into fulltexts, as well.
575
# If we build a cheap enough 'strip', then we could try a strip,
576
# if that expands the content, we then rebuild.
577
self._rebuild_block()
579
def _wire_bytes(self):
580
"""Return a byte stream suitable for transmitting over the wire."""
581
self._check_rebuild_block()
582
# The outer block starts with:
583
# 'groupcompress-block\n'
584
# <length of compressed key info>\n
585
# <length of uncompressed info>\n
586
# <length of gc block>\n
589
lines = ['groupcompress-block\n']
590
# The minimal info we need is the key, the start offset, and the
591
# parents. The length and type are encoded in the record itself.
592
# However, passing in the other bits makes it easier. The list of
593
# keys, and the start offset, the length
595
# 1 line with parents, '' for ()
596
# 1 line for start offset
597
# 1 line for end byte
599
for factory in self._factories:
600
key_bytes = '\x00'.join(factory.key)
601
parents = factory.parents
603
parent_bytes = 'None:'
605
parent_bytes = '\t'.join('\x00'.join(key) for key in parents)
606
record_header = '%s\n%s\n%d\n%d\n' % (
607
key_bytes, parent_bytes, factory._start, factory._end)
608
header_lines.append(record_header)
609
# TODO: Can we break the refcycle at this point and set
610
# factory._manager = None?
611
header_bytes = ''.join(header_lines)
613
header_bytes_len = len(header_bytes)
614
z_header_bytes = zlib.compress(header_bytes)
616
z_header_bytes_len = len(z_header_bytes)
617
block_bytes = self._block.to_bytes()
618
lines.append('%d\n%d\n%d\n' % (z_header_bytes_len, header_bytes_len,
620
lines.append(z_header_bytes)
621
lines.append(block_bytes)
622
del z_header_bytes, block_bytes
623
return ''.join(lines)
626
def from_bytes(cls, bytes):
627
# TODO: This does extra string copying, probably better to do it a
629
(storage_kind, z_header_len, header_len,
630
block_len, rest) = bytes.split('\n', 4)
632
if storage_kind != 'groupcompress-block':
633
raise ValueError('Unknown storage kind: %s' % (storage_kind,))
634
z_header_len = int(z_header_len)
635
if len(rest) < z_header_len:
636
raise ValueError('Compressed header len shorter than all bytes')
637
z_header = rest[:z_header_len]
638
header_len = int(header_len)
639
header = zlib.decompress(z_header)
640
if len(header) != header_len:
641
raise ValueError('invalid length for decompressed bytes')
643
block_len = int(block_len)
644
if len(rest) != z_header_len + block_len:
645
raise ValueError('Invalid length for block')
646
block_bytes = rest[z_header_len:]
648
# So now we have a valid GCB, we just need to parse the factories that
650
header_lines = header.split('\n')
652
last = header_lines.pop()
654
raise ValueError('header lines did not end with a trailing'
656
if len(header_lines) % 4 != 0:
657
raise ValueError('The header was not an even multiple of 4 lines')
658
block = GroupCompressBlock.from_bytes(block_bytes)
661
for start in xrange(0, len(header_lines), 4):
663
key = tuple(header_lines[start].split('\x00'))
664
parents_line = header_lines[start+1]
665
if parents_line == 'None:':
668
parents = tuple([tuple(segment.split('\x00'))
669
for segment in parents_line.split('\t')
671
start_offset = int(header_lines[start+2])
672
end_offset = int(header_lines[start+3])
673
result.add_factory(key, parents, start_offset, end_offset)
677
def network_block_to_records(storage_kind, bytes, line_end):
678
if storage_kind != 'groupcompress-block':
679
raise ValueError('Unknown storage kind: %s' % (storage_kind,))
680
manager = _LazyGroupContentManager.from_bytes(bytes)
681
return manager.get_record_stream()
684
class _CommonGroupCompressor(object):
687
"""Create a GroupCompressor."""
692
self.labels_deltas = {}
693
self._delta_index = None # Set by the children
694
self._block = GroupCompressBlock()
696
def compress(self, key, bytes, expected_sha, nostore_sha=None, soft=False):
697
"""Compress lines with label key.
699
:param key: A key tuple. It is stored in the output
700
for identification of the text during decompression. If the last
701
element is 'None' it is replaced with the sha1 of the text -
703
:param bytes: The bytes to be compressed
704
:param expected_sha: If non-None, the sha the lines are believed to
705
have. During compression the sha is calculated; a mismatch will
707
:param nostore_sha: If the computed sha1 sum matches, we will raise
708
ExistingContent rather than adding the text.
709
:param soft: Do a 'soft' compression. This means that we require larger
710
ranges to match to be considered for a copy command.
712
:return: The sha1 of lines, the start and end offsets in the delta, and
713
the type ('fulltext' or 'delta').
715
:seealso VersionedFiles.add_lines:
717
if not bytes: # empty, like a dir entry, etc
718
if nostore_sha == _null_sha1:
719
raise errors.ExistingContent()
720
return _null_sha1, 0, 0, 'fulltext'
721
# we assume someone knew what they were doing when they passed it in
722
if expected_sha is not None:
725
sha1 = osutils.sha_string(bytes)
726
if nostore_sha is not None:
727
if sha1 == nostore_sha:
728
raise errors.ExistingContent()
730
key = key[:-1] + ('sha1:' + sha1,)
732
start, end, type = self._compress(key, bytes, len(bytes) / 2, soft)
733
return sha1, start, end, type
735
def _compress(self, key, bytes, max_delta_size, soft=False):
736
"""Compress lines with label key.
738
:param key: A key tuple. It is stored in the output for identification
739
of the text during decompression.
741
:param bytes: The bytes to be compressed
743
:param max_delta_size: The size above which we issue a fulltext instead
746
:param soft: Do a 'soft' compression. This means that we require larger
747
ranges to match to be considered for a copy command.
749
:return: The sha1 of lines, the start and end offsets in the delta, and
750
the type ('fulltext' or 'delta').
752
raise NotImplementedError(self._compress)
754
def extract(self, key):
755
"""Extract a key previously added to the compressor.
757
:param key: The key to extract.
758
:return: An iterable over bytes and the sha1.
760
(start_byte, start_chunk, end_byte, end_chunk) = self.labels_deltas[key]
761
delta_chunks = self.chunks[start_chunk:end_chunk]
762
stored_bytes = ''.join(delta_chunks)
763
if stored_bytes[0] == 'f':
764
fulltext_len, offset = decode_base128_int(stored_bytes[1:10])
765
data_len = fulltext_len + 1 + offset
766
if data_len != len(stored_bytes):
767
raise ValueError('Index claimed fulltext len, but stored bytes'
769
% (len(stored_bytes), data_len))
770
bytes = stored_bytes[offset + 1:]
772
# XXX: This is inefficient at best
773
source = ''.join(self.chunks[:start_chunk])
774
if stored_bytes[0] != 'd':
775
raise ValueError('Unknown content kind, bytes claim %s'
776
% (stored_bytes[0],))
777
delta_len, offset = decode_base128_int(stored_bytes[1:10])
778
data_len = delta_len + 1 + offset
779
if data_len != len(stored_bytes):
780
raise ValueError('Index claimed delta len, but stored bytes'
782
% (len(stored_bytes), data_len))
783
bytes = apply_delta(source, stored_bytes[offset + 1:])
784
bytes_sha1 = osutils.sha_string(bytes)
785
return bytes, bytes_sha1
788
"""Finish this group, creating a formatted stream.
790
After calling this, the compressor should no longer be used
792
# TODO: this causes us to 'bloat' to 2x the size of content in the
793
# group. This has an impact for 'commit' of large objects.
794
# One possibility is to use self._content_chunks, and be lazy and
795
# only fill out self._content as a full string when we actually
796
# need it. That would at least drop the peak memory consumption
797
# for 'commit' down to ~1x the size of the largest file, at a
798
# cost of increased complexity within this code. 2x is still <<
799
# 3x the size of the largest file, so we are doing ok.
800
self._block.set_chunked_content(self.chunks, self.endpoint)
802
self._delta_index = None
806
"""Call this if you want to 'revoke' the last compression.
808
After this, the data structures will be rolled back, but you cannot do
811
self._delta_index = None
812
del self.chunks[self._last[0]:]
813
self.endpoint = self._last[1]
817
"""Return the overall compression ratio."""
818
return float(self.input_bytes) / float(self.endpoint)
821
class PythonGroupCompressor(_CommonGroupCompressor):
824
"""Create a GroupCompressor.
826
Used only if the pyrex version is not available.
828
super(PythonGroupCompressor, self).__init__()
829
self._delta_index = LinesDeltaIndex([])
830
# The actual content is managed by LinesDeltaIndex
831
self.chunks = self._delta_index.lines
833
def _compress(self, key, bytes, max_delta_size, soft=False):
834
"""see _CommonGroupCompressor._compress"""
835
input_len = len(bytes)
836
new_lines = osutils.split_lines(bytes)
837
out_lines, index_lines = self._delta_index.make_delta(
838
new_lines, bytes_length=input_len, soft=soft)
839
delta_length = sum(map(len, out_lines))
840
if delta_length > max_delta_size:
841
# The delta is longer than the fulltext, insert a fulltext
843
out_lines = ['f', encode_base128_int(input_len)]
844
out_lines.extend(new_lines)
845
index_lines = [False, False]
846
index_lines.extend([True] * len(new_lines))
848
# this is a worthy delta, output it
851
# Update the delta_length to include those two encoded integers
852
out_lines[1] = encode_base128_int(delta_length)
854
start = self.endpoint
855
chunk_start = len(self.chunks)
856
self._last = (chunk_start, self.endpoint)
857
self._delta_index.extend_lines(out_lines, index_lines)
858
self.endpoint = self._delta_index.endpoint
859
self.input_bytes += input_len
860
chunk_end = len(self.chunks)
861
self.labels_deltas[key] = (start, chunk_start,
862
self.endpoint, chunk_end)
863
return start, self.endpoint, type
866
class PyrexGroupCompressor(_CommonGroupCompressor):
867
"""Produce a serialised group of compressed texts.
869
It contains code very similar to SequenceMatcher because of having a similar
870
task. However some key differences apply:
871
- there is no junk, we want a minimal edit not a human readable diff.
872
- we don't filter very common lines (because we don't know where a good
873
range will start, and after the first text we want to be emitting minmal
875
- we chain the left side, not the right side
876
- we incrementally update the adjacency matrix as new lines are provided.
877
- we look for matches in all of the left side, so the routine which does
878
the analagous task of find_longest_match does not need to filter on the
883
super(PyrexGroupCompressor, self).__init__()
884
self._delta_index = DeltaIndex()
886
def _compress(self, key, bytes, max_delta_size, soft=False):
887
"""see _CommonGroupCompressor._compress"""
888
input_len = len(bytes)
889
# By having action/label/sha1/len, we can parse the group if the index
890
# was ever destroyed, we have the key in 'label', we know the final
891
# bytes are valid from sha1, and we know where to find the end of this
892
# record because of 'len'. (the delta record itself will store the
893
# total length for the expanded record)
894
# 'len: %d\n' costs approximately 1% increase in total data
895
# Having the labels at all costs us 9-10% increase, 38% increase for
896
# inventory pages, and 5.8% increase for text pages
897
# new_chunks = ['label:%s\nsha1:%s\n' % (label, sha1)]
898
if self._delta_index._source_offset != self.endpoint:
899
raise AssertionError('_source_offset != endpoint'
900
' somehow the DeltaIndex got out of sync with'
902
delta = self._delta_index.make_delta(bytes, max_delta_size)
905
enc_length = encode_base128_int(len(bytes))
906
len_mini_header = 1 + len(enc_length)
907
self._delta_index.add_source(bytes, len_mini_header)
908
new_chunks = ['f', enc_length, bytes]
911
enc_length = encode_base128_int(len(delta))
912
len_mini_header = 1 + len(enc_length)
913
new_chunks = ['d', enc_length, delta]
914
self._delta_index.add_delta_source(delta, len_mini_header)
916
start = self.endpoint
917
chunk_start = len(self.chunks)
918
# Now output these bytes
919
self._output_chunks(new_chunks)
920
self.input_bytes += input_len
921
chunk_end = len(self.chunks)
922
self.labels_deltas[key] = (start, chunk_start,
923
self.endpoint, chunk_end)
924
if not self._delta_index._source_offset == self.endpoint:
925
raise AssertionError('the delta index is out of sync'
926
'with the output lines %s != %s'
927
% (self._delta_index._source_offset, self.endpoint))
928
return start, self.endpoint, type
930
def _output_chunks(self, new_chunks):
931
"""Output some chunks.
933
:param new_chunks: The chunks to output.
935
self._last = (len(self.chunks), self.endpoint)
936
endpoint = self.endpoint
937
self.chunks.extend(new_chunks)
938
endpoint += sum(map(len, new_chunks))
939
self.endpoint = endpoint
942
def make_pack_factory(graph, delta, keylength, inconsistency_fatal=True):
943
"""Create a factory for creating a pack based groupcompress.
945
This is only functional enough to run interface tests, it doesn't try to
946
provide a full pack environment.
948
:param graph: Store a graph.
949
:param delta: Delta compress contents.
950
:param keylength: How long should keys be.
952
def factory(transport):
957
graph_index = BTreeBuilder(reference_lists=ref_length,
958
key_elements=keylength)
959
stream = transport.open_write_stream('newpack')
960
writer = pack.ContainerWriter(stream.write)
962
index = _GCGraphIndex(graph_index, lambda:True, parents=parents,
963
add_callback=graph_index.add_nodes,
964
inconsistency_fatal=inconsistency_fatal)
965
access = knit._DirectPackAccess({})
966
access.set_writer(writer, graph_index, (transport, 'newpack'))
967
result = GroupCompressVersionedFiles(index, access, delta)
968
result.stream = stream
969
result.writer = writer
974
def cleanup_pack_group(versioned_files):
975
versioned_files.writer.end()
976
versioned_files.stream.close()
979
class _BatchingBlockFetcher(object):
980
"""Fetch group compress blocks in batches.
982
:ivar total_bytes: int of expected number of bytes needed to fetch the
983
currently pending batch.
986
def __init__(self, gcvf, locations):
988
self.locations = locations
990
self.batch_memos = {}
991
self.memos_to_get = []
993
self.last_read_memo = None
996
def add_key(self, key):
997
"""Add another to key to fetch.
999
:return: The estimated number of bytes needed to fetch the batch so
1002
self.keys.append(key)
1003
index_memo, _, _, _ = self.locations[key]
1004
read_memo = index_memo[0:3]
1005
# Three possibilities for this read_memo:
1006
# - it's already part of this batch; or
1007
# - it's not yet part of this batch, but is already cached; or
1008
# - it's not yet part of this batch and will need to be fetched.
1009
if read_memo in self.batch_memos:
1010
# This read memo is already in this batch.
1011
return self.total_bytes
1013
cached_block = self.gcvf._group_cache[read_memo]
1015
# This read memo is new to this batch, and the data isn't cached
1017
self.batch_memos[read_memo] = None
1018
self.memos_to_get.append(read_memo)
1019
byte_length = read_memo[2]
1020
self.total_bytes += byte_length
1022
# This read memo is new to this batch, but cached.
1023
# Keep a reference to the cached block in batch_memos because it's
1024
# certain that we'll use it when this batch is processed, but
1025
# there's a risk that it would fall out of _group_cache between now
1027
self.batch_memos[read_memo] = cached_block
1028
return self.total_bytes
1030
def _flush_manager(self):
1031
if self.manager is not None:
1032
for factory in self.manager.get_record_stream():
1035
self.last_read_memo = None
1037
def yield_factories(self, full_flush=False):
1038
"""Yield factories for keys added since the last yield. They will be
1039
returned in the order they were added via add_key.
1041
:param full_flush: by default, some results may not be returned in case
1042
they can be part of the next batch. If full_flush is True, then
1043
all results are returned.
1045
if self.manager is None and not self.keys:
1047
# Fetch all memos in this batch.
1048
blocks = self.gcvf._get_blocks(self.memos_to_get)
1049
# Turn blocks into factories and yield them.
1050
memos_to_get_stack = list(self.memos_to_get)
1051
memos_to_get_stack.reverse()
1052
for key in self.keys:
1053
index_memo, _, parents, _ = self.locations[key]
1054
read_memo = index_memo[:3]
1055
if self.last_read_memo != read_memo:
1056
# We are starting a new block. If we have a
1057
# manager, we have found everything that fits for
1058
# now, so yield records
1059
for factory in self._flush_manager():
1061
# Now start a new manager.
1062
if memos_to_get_stack and memos_to_get_stack[-1] == read_memo:
1063
# The next block from _get_blocks will be the block we
1065
block_read_memo, block = blocks.next()
1066
if block_read_memo != read_memo:
1067
raise AssertionError(
1068
"block_read_memo out of sync with read_memo"
1069
"(%r != %r)" % (block_read_memo, read_memo))
1070
self.batch_memos[read_memo] = block
1071
memos_to_get_stack.pop()
1073
block = self.batch_memos[read_memo]
1074
self.manager = _LazyGroupContentManager(block)
1075
self.last_read_memo = read_memo
1076
start, end = index_memo[3:5]
1077
self.manager.add_factory(key, parents, start, end)
1079
for factory in self._flush_manager():
1082
self.batch_memos.clear()
1083
del self.memos_to_get[:]
1084
self.total_bytes = 0
1087
class GroupCompressVersionedFiles(VersionedFiles):
1088
"""A group-compress based VersionedFiles implementation."""
1090
def __init__(self, index, access, delta=True):
1091
"""Create a GroupCompressVersionedFiles object.
1093
:param index: The index object storing access and graph data.
1094
:param access: The access object storing raw data.
1095
:param delta: Whether to delta compress or just entropy compress.
1098
self._access = access
1100
self._unadded_refs = {}
1101
self._group_cache = LRUSizeCache(max_size=50*1024*1024)
1102
self._fallback_vfs = []
1104
def add_lines(self, key, parents, lines, parent_texts=None,
1105
left_matching_blocks=None, nostore_sha=None, random_id=False,
1106
check_content=True):
1107
"""Add a text to the store.
1109
:param key: The key tuple of the text to add.
1110
:param parents: The parents key tuples of the text to add.
1111
:param lines: A list of lines. Each line must be a bytestring. And all
1112
of them except the last must be terminated with \n and contain no
1113
other \n's. The last line may either contain no \n's or a single
1114
terminating \n. If the lines list does meet this constraint the add
1115
routine may error or may succeed - but you will be unable to read
1116
the data back accurately. (Checking the lines have been split
1117
correctly is expensive and extremely unlikely to catch bugs so it
1118
is not done at runtime unless check_content is True.)
1119
:param parent_texts: An optional dictionary containing the opaque
1120
representations of some or all of the parents of version_id to
1121
allow delta optimisations. VERY IMPORTANT: the texts must be those
1122
returned by add_lines or data corruption can be caused.
1123
:param left_matching_blocks: a hint about which areas are common
1124
between the text and its left-hand-parent. The format is
1125
the SequenceMatcher.get_matching_blocks format.
1126
:param nostore_sha: Raise ExistingContent and do not add the lines to
1127
the versioned file if the digest of the lines matches this.
1128
:param random_id: If True a random id has been selected rather than
1129
an id determined by some deterministic process such as a converter
1130
from a foreign VCS. When True the backend may choose not to check
1131
for uniqueness of the resulting key within the versioned file, so
1132
this should only be done when the result is expected to be unique
1134
:param check_content: If True, the lines supplied are verified to be
1135
bytestrings that are correctly formed lines.
1136
:return: The text sha1, the number of bytes in the text, and an opaque
1137
representation of the inserted version which can be provided
1138
back to future add_lines calls in the parent_texts dictionary.
1140
self._index._check_write_ok()
1141
self._check_add(key, lines, random_id, check_content)
1143
# The caller might pass None if there is no graph data, but kndx
1144
# indexes can't directly store that, so we give them
1145
# an empty tuple instead.
1147
# double handling for now. Make it work until then.
1148
length = sum(map(len, lines))
1149
record = ChunkedContentFactory(key, parents, None, lines)
1150
sha1 = list(self._insert_record_stream([record], random_id=random_id,
1151
nostore_sha=nostore_sha))[0]
1152
return sha1, length, None
1154
def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
1155
"""See VersionedFiles._add_text()."""
1156
self._index._check_write_ok()
1157
self._check_add(key, None, random_id, check_content=False)
1158
if text.__class__ is not str:
1159
raise errors.BzrBadParameterUnicode("text")
1161
# The caller might pass None if there is no graph data, but kndx
1162
# indexes can't directly store that, so we give them
1163
# an empty tuple instead.
1165
# double handling for now. Make it work until then.
1167
record = FulltextContentFactory(key, parents, None, text)
1168
sha1 = list(self._insert_record_stream([record], random_id=random_id,
1169
nostore_sha=nostore_sha))[0]
1170
return sha1, length, None
1172
def add_fallback_versioned_files(self, a_versioned_files):
1173
"""Add a source of texts for texts not present in this knit.
1175
:param a_versioned_files: A VersionedFiles object.
1177
self._fallback_vfs.append(a_versioned_files)
1179
def annotate(self, key):
1180
"""See VersionedFiles.annotate."""
1181
ann = annotate.Annotator(self)
1182
return ann.annotate_flat(key)
1184
def get_annotator(self):
1185
return annotate.Annotator(self)
1187
def check(self, progress_bar=None, keys=None):
1188
"""See VersionedFiles.check()."""
1191
for record in self.get_record_stream(keys, 'unordered', True):
1192
record.get_bytes_as('fulltext')
1194
return self.get_record_stream(keys, 'unordered', True)
1196
def _check_add(self, key, lines, random_id, check_content):
1197
"""check that version_id and lines are safe to add."""
1198
version_id = key[-1]
1199
if version_id is not None:
1200
if osutils.contains_whitespace(version_id):
1201
raise errors.InvalidRevisionId(version_id, self)
1202
self.check_not_reserved_id(version_id)
1203
# TODO: If random_id==False and the key is already present, we should
1204
# probably check that the existing content is identical to what is
1205
# being inserted, and otherwise raise an exception. This would make
1206
# the bundle code simpler.
1208
self._check_lines_not_unicode(lines)
1209
self._check_lines_are_lines(lines)
1211
def get_known_graph_ancestry(self, keys):
1212
"""Get a KnownGraph instance with the ancestry of keys."""
1213
# Note that this is identical to
1214
# KnitVersionedFiles.get_known_graph_ancestry, but they don't share
1216
parent_map, missing_keys = self._index._graph_index.find_ancestry(keys,
1218
for fallback in self._fallback_vfs:
1219
if not missing_keys:
1221
(f_parent_map, f_missing_keys) = fallback._index._graph_index.find_ancestry(
1223
parent_map.update(f_parent_map)
1224
missing_keys = f_missing_keys
1225
kg = _mod_graph.KnownGraph(parent_map)
1228
def get_parent_map(self, keys):
1229
"""Get a map of the graph parents of keys.
1231
:param keys: The keys to look up parents for.
1232
:return: A mapping from keys to parents. Absent keys are absent from
1235
return self._get_parent_map_with_sources(keys)[0]
1237
def _get_parent_map_with_sources(self, keys):
1238
"""Get a map of the parents of keys.
1240
:param keys: The keys to look up parents for.
1241
:return: A tuple. The first element is a mapping from keys to parents.
1242
Absent keys are absent from the mapping. The second element is a
1243
list with the locations each key was found in. The first element
1244
is the in-this-knit parents, the second the first fallback source,
1248
sources = [self._index] + self._fallback_vfs
1251
for source in sources:
1254
new_result = source.get_parent_map(missing)
1255
source_results.append(new_result)
1256
result.update(new_result)
1257
missing.difference_update(set(new_result))
1258
return result, source_results
1260
def _get_blocks(self, read_memos):
1261
"""Get GroupCompressBlocks for the given read_memos.
1263
:returns: a series of (read_memo, block) pairs, in the order they were
1267
for read_memo in read_memos:
1269
block = self._group_cache[read_memo]
1273
cached[read_memo] = block
1275
not_cached_seen = set()
1276
for read_memo in read_memos:
1277
if read_memo in cached:
1278
# Don't fetch what we already have
1280
if read_memo in not_cached_seen:
1281
# Don't try to fetch the same data twice
1283
not_cached.append(read_memo)
1284
not_cached_seen.add(read_memo)
1285
raw_records = self._access.get_raw_records(not_cached)
1286
for read_memo in read_memos:
1288
yield read_memo, cached[read_memo]
1290
# Read the block, and cache it.
1291
zdata = raw_records.next()
1292
block = GroupCompressBlock.from_bytes(zdata)
1293
self._group_cache[read_memo] = block
1294
cached[read_memo] = block
1295
yield read_memo, block
1297
def get_missing_compression_parent_keys(self):
1298
"""Return the keys of missing compression parents.
1300
Missing compression parents occur when a record stream was missing
1301
basis texts, or a index was scanned that had missing basis texts.
1303
# GroupCompress cannot currently reference texts that are not in the
1304
# group, so this is valid for now
1307
def get_record_stream(self, keys, ordering, include_delta_closure):
1308
"""Get a stream of records for keys.
1310
:param keys: The keys to include.
1311
:param ordering: Either 'unordered' or 'topological'. A topologically
1312
sorted stream has compression parents strictly before their
1314
:param include_delta_closure: If True then the closure across any
1315
compression parents will be included (in the opaque data).
1316
:return: An iterator of ContentFactory objects, each of which is only
1317
valid until the iterator is advanced.
1319
# keys might be a generator
1320
orig_keys = list(keys)
1324
if (not self._index.has_graph
1325
and ordering in ('topological', 'groupcompress')):
1326
# Cannot topological order when no graph has been stored.
1327
# but we allow 'as-requested' or 'unordered'
1328
ordering = 'unordered'
1330
remaining_keys = keys
1333
keys = set(remaining_keys)
1334
for content_factory in self._get_remaining_record_stream(keys,
1335
orig_keys, ordering, include_delta_closure):
1336
remaining_keys.discard(content_factory.key)
1337
yield content_factory
1339
except errors.RetryWithNewPacks, e:
1340
self._access.reload_or_raise(e)
1342
def _find_from_fallback(self, missing):
1343
"""Find whatever keys you can from the fallbacks.
1345
:param missing: A set of missing keys. This set will be mutated as keys
1346
are found from a fallback_vfs
1347
:return: (parent_map, key_to_source_map, source_results)
1348
parent_map the overall key => parent_keys
1349
key_to_source_map a dict from {key: source}
1350
source_results a list of (source: keys)
1353
key_to_source_map = {}
1355
for source in self._fallback_vfs:
1358
source_parents = source.get_parent_map(missing)
1359
parent_map.update(source_parents)
1360
source_parents = list(source_parents)
1361
source_results.append((source, source_parents))
1362
key_to_source_map.update((key, source) for key in source_parents)
1363
missing.difference_update(source_parents)
1364
return parent_map, key_to_source_map, source_results
1366
def _get_ordered_source_keys(self, ordering, parent_map, key_to_source_map):
1367
"""Get the (source, [keys]) list.
1369
The returned objects should be in the order defined by 'ordering',
1370
which can weave between different sources.
1371
:param ordering: Must be one of 'topological' or 'groupcompress'
1372
:return: List of [(source, [keys])] tuples, such that all keys are in
1373
the defined order, regardless of source.
1375
if ordering == 'topological':
1376
present_keys = topo_sort(parent_map)
1378
# ordering == 'groupcompress'
1379
# XXX: This only optimizes for the target ordering. We may need
1380
# to balance that with the time it takes to extract
1381
# ordering, by somehow grouping based on
1382
# locations[key][0:3]
1383
present_keys = sort_gc_optimal(parent_map)
1384
# Now group by source:
1386
current_source = None
1387
for key in present_keys:
1388
source = key_to_source_map.get(key, self)
1389
if source is not current_source:
1390
source_keys.append((source, []))
1391
current_source = source
1392
source_keys[-1][1].append(key)
1395
def _get_as_requested_source_keys(self, orig_keys, locations, unadded_keys,
1398
current_source = None
1399
for key in orig_keys:
1400
if key in locations or key in unadded_keys:
1402
elif key in key_to_source_map:
1403
source = key_to_source_map[key]
1406
if source is not current_source:
1407
source_keys.append((source, []))
1408
current_source = source
1409
source_keys[-1][1].append(key)
1412
def _get_io_ordered_source_keys(self, locations, unadded_keys,
1415
# This is the group the bytes are stored in, followed by the
1416
# location in the group
1417
return locations[key][0]
1418
present_keys = sorted(locations.iterkeys(), key=get_group)
1419
# We don't have an ordering for keys in the in-memory object, but
1420
# lets process the in-memory ones first.
1421
present_keys = list(unadded_keys) + present_keys
1422
# Now grab all of the ones from other sources
1423
source_keys = [(self, present_keys)]
1424
source_keys.extend(source_result)
1427
def _get_remaining_record_stream(self, keys, orig_keys, ordering,
1428
include_delta_closure):
1429
"""Get a stream of records for keys.
1431
:param keys: The keys to include.
1432
:param ordering: one of 'unordered', 'topological', 'groupcompress' or
1434
:param include_delta_closure: If True then the closure across any
1435
compression parents will be included (in the opaque data).
1436
:return: An iterator of ContentFactory objects, each of which is only
1437
valid until the iterator is advanced.
1440
locations = self._index.get_build_details(keys)
1441
unadded_keys = set(self._unadded_refs).intersection(keys)
1442
missing = keys.difference(locations)
1443
missing.difference_update(unadded_keys)
1444
(fallback_parent_map, key_to_source_map,
1445
source_result) = self._find_from_fallback(missing)
1446
if ordering in ('topological', 'groupcompress'):
1447
# would be better to not globally sort initially but instead
1448
# start with one key, recurse to its oldest parent, then grab
1449
# everything in the same group, etc.
1450
parent_map = dict((key, details[2]) for key, details in
1451
locations.iteritems())
1452
for key in unadded_keys:
1453
parent_map[key] = self._unadded_refs[key]
1454
parent_map.update(fallback_parent_map)
1455
source_keys = self._get_ordered_source_keys(ordering, parent_map,
1457
elif ordering == 'as-requested':
1458
source_keys = self._get_as_requested_source_keys(orig_keys,
1459
locations, unadded_keys, key_to_source_map)
1461
# We want to yield the keys in a semi-optimal (read-wise) ordering.
1462
# Otherwise we thrash the _group_cache and destroy performance
1463
source_keys = self._get_io_ordered_source_keys(locations,
1464
unadded_keys, source_result)
1466
yield AbsentContentFactory(key)
1467
# Batch up as many keys as we can until either:
1468
# - we encounter an unadded ref, or
1469
# - we run out of keys, or
1470
# - the total bytes to retrieve for this batch > BATCH_SIZE
1471
batcher = _BatchingBlockFetcher(self, locations)
1472
for source, keys in source_keys:
1475
if key in self._unadded_refs:
1476
# Flush batch, then yield unadded ref from
1478
for factory in batcher.yield_factories(full_flush=True):
1480
bytes, sha1 = self._compressor.extract(key)
1481
parents = self._unadded_refs[key]
1482
yield FulltextContentFactory(key, parents, sha1, bytes)
1484
if batcher.add_key(key) > BATCH_SIZE:
1485
# Ok, this batch is big enough. Yield some results.
1486
for factory in batcher.yield_factories():
1489
for factory in batcher.yield_factories(full_flush=True):
1491
for record in source.get_record_stream(keys, ordering,
1492
include_delta_closure):
1494
for factory in batcher.yield_factories(full_flush=True):
1497
def get_sha1s(self, keys):
1498
"""See VersionedFiles.get_sha1s()."""
1500
for record in self.get_record_stream(keys, 'unordered', True):
1501
if record.sha1 != None:
1502
result[record.key] = record.sha1
1504
if record.storage_kind != 'absent':
1505
result[record.key] = osutils.sha_string(
1506
record.get_bytes_as('fulltext'))
1509
def insert_record_stream(self, stream):
1510
"""Insert a record stream into this container.
1512
:param stream: A stream of records to insert.
1514
:seealso VersionedFiles.get_record_stream:
1516
# XXX: Setting random_id=True makes
1517
# test_insert_record_stream_existing_keys fail for groupcompress and
1518
# groupcompress-nograph, this needs to be revisited while addressing
1519
# 'bzr branch' performance issues.
1520
for _ in self._insert_record_stream(stream, random_id=False):
1523
def _insert_record_stream(self, stream, random_id=False, nostore_sha=None,
1525
"""Internal core to insert a record stream into this container.
1527
This helper function has a different interface than insert_record_stream
1528
to allow add_lines to be minimal, but still return the needed data.
1530
:param stream: A stream of records to insert.
1531
:param nostore_sha: If the sha1 of a given text matches nostore_sha,
1532
raise ExistingContent, rather than committing the new text.
1533
:param reuse_blocks: If the source is streaming from
1534
groupcompress-blocks, just insert the blocks as-is, rather than
1535
expanding the texts and inserting again.
1536
:return: An iterator over the sha1 of the inserted records.
1537
:seealso insert_record_stream:
1541
def get_adapter(adapter_key):
1543
return adapters[adapter_key]
1545
adapter_factory = adapter_registry.get(adapter_key)
1546
adapter = adapter_factory(self)
1547
adapters[adapter_key] = adapter
1549
# This will go up to fulltexts for gc to gc fetching, which isn't
1551
self._compressor = GroupCompressor()
1552
self._unadded_refs = {}
1555
bytes = self._compressor.flush().to_bytes()
1556
index, start, length = self._access.add_raw_records(
1557
[(None, len(bytes))], bytes)[0]
1559
for key, reads, refs in keys_to_add:
1560
nodes.append((key, "%d %d %s" % (start, length, reads), refs))
1561
self._index.add_records(nodes, random_id=random_id)
1562
self._unadded_refs = {}
1564
self._compressor = GroupCompressor()
1567
max_fulltext_len = 0
1568
max_fulltext_prefix = None
1569
insert_manager = None
1572
# XXX: TODO: remove this, it is just for safety checking for now
1573
inserted_keys = set()
1574
for record in stream:
1575
# Raise an error when a record is missing.
1576
if record.storage_kind == 'absent':
1577
raise errors.RevisionNotPresent(record.key, self)
1579
if record.key in inserted_keys:
1580
trace.note('Insert claimed random_id=True,'
1581
' but then inserted %r two times', record.key)
1583
inserted_keys.add(record.key)
1585
# If the reuse_blocks flag is set, check to see if we can just
1586
# copy a groupcompress block as-is.
1587
if record.storage_kind == 'groupcompress-block':
1588
# Insert the raw block into the target repo
1589
insert_manager = record._manager
1590
insert_manager._check_rebuild_block()
1591
bytes = record._manager._block.to_bytes()
1592
_, start, length = self._access.add_raw_records(
1593
[(None, len(bytes))], bytes)[0]
1596
block_length = length
1597
if record.storage_kind in ('groupcompress-block',
1598
'groupcompress-block-ref'):
1599
if insert_manager is None:
1600
raise AssertionError('No insert_manager set')
1601
value = "%d %d %d %d" % (block_start, block_length,
1602
record._start, record._end)
1603
nodes = [(record.key, value, (record.parents,))]
1604
# TODO: Consider buffering up many nodes to be added, not
1605
# sure how much overhead this has, but we're seeing
1606
# ~23s / 120s in add_records calls
1607
self._index.add_records(nodes, random_id=random_id)
1610
bytes = record.get_bytes_as('fulltext')
1611
except errors.UnavailableRepresentation:
1612
adapter_key = record.storage_kind, 'fulltext'
1613
adapter = get_adapter(adapter_key)
1614
bytes = adapter.get_bytes(record)
1615
if len(record.key) > 1:
1616
prefix = record.key[0]
1617
soft = (prefix == last_prefix)
1621
if max_fulltext_len < len(bytes):
1622
max_fulltext_len = len(bytes)
1623
max_fulltext_prefix = prefix
1624
(found_sha1, start_point, end_point,
1625
type) = self._compressor.compress(record.key,
1626
bytes, record.sha1, soft=soft,
1627
nostore_sha=nostore_sha)
1628
# delta_ratio = float(len(bytes)) / (end_point - start_point)
1629
# Check if we want to continue to include that text
1630
if (prefix == max_fulltext_prefix
1631
and end_point < 2 * max_fulltext_len):
1632
# As long as we are on the same file_id, we will fill at least
1633
# 2 * max_fulltext_len
1634
start_new_block = False
1635
elif end_point > 4*1024*1024:
1636
start_new_block = True
1637
elif (prefix is not None and prefix != last_prefix
1638
and end_point > 2*1024*1024):
1639
start_new_block = True
1641
start_new_block = False
1642
last_prefix = prefix
1644
self._compressor.pop_last()
1646
max_fulltext_len = len(bytes)
1647
(found_sha1, start_point, end_point,
1648
type) = self._compressor.compress(record.key, bytes,
1650
if record.key[-1] is None:
1651
key = record.key[:-1] + ('sha1:' + found_sha1,)
1654
self._unadded_refs[key] = record.parents
1656
keys_to_add.append((key, '%d %d' % (start_point, end_point),
1658
if len(keys_to_add):
1660
self._compressor = None
1662
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1663
"""Iterate over the lines in the versioned files from keys.
1665
This may return lines from other keys. Each item the returned
1666
iterator yields is a tuple of a line and a text version that that line
1667
is present in (not introduced in).
1669
Ordering of results is in whatever order is most suitable for the
1670
underlying storage format.
1672
If a progress bar is supplied, it may be used to indicate progress.
1673
The caller is responsible for cleaning up progress bars (because this
1677
* Lines are normalised by the underlying store: they will all have \n
1679
* Lines are returned in arbitrary order.
1681
:return: An iterator over (line, key).
1685
# we don't care about inclusions, the caller cares.
1686
# but we need to setup a list of records to visit.
1687
# we need key, position, length
1688
for key_idx, record in enumerate(self.get_record_stream(keys,
1689
'unordered', True)):
1690
# XXX: todo - optimise to use less than full texts.
1693
pb.update('Walking content', key_idx, total)
1694
if record.storage_kind == 'absent':
1695
raise errors.RevisionNotPresent(key, self)
1696
lines = osutils.split_lines(record.get_bytes_as('fulltext'))
1700
pb.update('Walking content', total, total)
1703
"""See VersionedFiles.keys."""
1704
if 'evil' in debug.debug_flags:
1705
trace.mutter_callsite(2, "keys scales with size of history")
1706
sources = [self._index] + self._fallback_vfs
1708
for source in sources:
1709
result.update(source.keys())
1713
class _GCGraphIndex(object):
1714
"""Mapper from GroupCompressVersionedFiles needs into GraphIndex storage."""
1716
def __init__(self, graph_index, is_locked, parents=True,
1717
add_callback=None, track_external_parent_refs=False,
1718
inconsistency_fatal=True):
1719
"""Construct a _GCGraphIndex on a graph_index.
1721
:param graph_index: An implementation of bzrlib.index.GraphIndex.
1722
:param is_locked: A callback, returns True if the index is locked and
1724
:param parents: If True, record knits parents, if not do not record
1726
:param add_callback: If not None, allow additions to the index and call
1727
this callback with a list of added GraphIndex nodes:
1728
[(node, value, node_refs), ...]
1729
:param track_external_parent_refs: As keys are added, keep track of the
1730
keys they reference, so that we can query get_missing_parents(),
1732
:param inconsistency_fatal: When asked to add records that are already
1733
present, and the details are inconsistent with the existing
1734
record, raise an exception instead of warning (and skipping the
1737
self._add_callback = add_callback
1738
self._graph_index = graph_index
1739
self._parents = parents
1740
self.has_graph = parents
1741
self._is_locked = is_locked
1742
self._inconsistency_fatal = inconsistency_fatal
1743
if track_external_parent_refs:
1744
self._key_dependencies = knit._KeyRefs()
1746
self._key_dependencies = None
1748
def add_records(self, records, random_id=False):
1749
"""Add multiple records to the index.
1751
This function does not insert data into the Immutable GraphIndex
1752
backing the KnitGraphIndex, instead it prepares data for insertion by
1753
the caller and checks that it is safe to insert then calls
1754
self._add_callback with the prepared GraphIndex nodes.
1756
:param records: a list of tuples:
1757
(key, options, access_memo, parents).
1758
:param random_id: If True the ids being added were randomly generated
1759
and no check for existence will be performed.
1761
if not self._add_callback:
1762
raise errors.ReadOnlyError(self)
1763
# we hope there are no repositories with inconsistent parentage
1768
for (key, value, refs) in records:
1769
if not self._parents:
1773
raise errors.KnitCorrupt(self,
1774
"attempt to add node with parents "
1775
"in parentless index.")
1778
keys[key] = (value, refs)
1781
present_nodes = self._get_entries(keys)
1782
for (index, key, value, node_refs) in present_nodes:
1783
if node_refs != keys[key][1]:
1784
details = '%s %s %s' % (key, (value, node_refs), keys[key])
1785
if self._inconsistency_fatal:
1786
raise errors.KnitCorrupt(self, "inconsistent details"
1787
" in add_records: %s" %
1790
trace.warning("inconsistent details in skipped"
1791
" record: %s", details)
1797
for key, (value, node_refs) in keys.iteritems():
1798
result.append((key, value, node_refs))
1800
for key, (value, node_refs) in keys.iteritems():
1801
result.append((key, value))
1803
key_dependencies = self._key_dependencies
1804
if key_dependencies is not None and self._parents:
1805
for key, value, refs in records:
1807
key_dependencies.add_references(key, parents)
1808
self._add_callback(records)
1810
def _check_read(self):
1811
"""Raise an exception if reads are not permitted."""
1812
if not self._is_locked():
1813
raise errors.ObjectNotLocked(self)
1815
def _check_write_ok(self):
1816
"""Raise an exception if writes are not permitted."""
1817
if not self._is_locked():
1818
raise errors.ObjectNotLocked(self)
1820
def _get_entries(self, keys, check_present=False):
1821
"""Get the entries for keys.
1823
Note: Callers are responsible for checking that the index is locked
1824
before calling this method.
1826
:param keys: An iterable of index key tuples.
1831
for node in self._graph_index.iter_entries(keys):
1833
found_keys.add(node[1])
1835
# adapt parentless index to the rest of the code.
1836
for node in self._graph_index.iter_entries(keys):
1837
yield node[0], node[1], node[2], ()
1838
found_keys.add(node[1])
1840
missing_keys = keys.difference(found_keys)
1842
raise errors.RevisionNotPresent(missing_keys.pop(), self)
1844
def get_parent_map(self, keys):
1845
"""Get a map of the parents of keys.
1847
:param keys: The keys to look up parents for.
1848
:return: A mapping from keys to parents. Absent keys are absent from
1852
nodes = self._get_entries(keys)
1856
result[node[1]] = node[3][0]
1859
result[node[1]] = None
1862
def get_missing_parents(self):
1863
"""Return the keys of missing parents."""
1864
# Copied from _KnitGraphIndex.get_missing_parents
1865
# We may have false positives, so filter those out.
1866
self._key_dependencies.add_keys(
1867
self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
1868
return frozenset(self._key_dependencies.get_unsatisfied_refs())
1870
def get_build_details(self, keys):
1871
"""Get the various build details for keys.
1873
Ghosts are omitted from the result.
1875
:param keys: An iterable of keys.
1876
:return: A dict of key:
1877
(index_memo, compression_parent, parents, record_details).
1879
opaque structure to pass to read_records to extract the raw
1882
Content that this record is built upon, may be None
1884
Logical parents of this node
1886
extra information about the content which needs to be passed to
1887
Factory.parse_record
1891
entries = self._get_entries(keys)
1892
for entry in entries:
1894
if not self._parents:
1897
parents = entry[3][0]
1899
result[key] = (self._node_to_position(entry),
1900
None, parents, (method, None))
1904
"""Get all the keys in the collection.
1906
The keys are not ordered.
1909
return [node[1] for node in self._graph_index.iter_all_entries()]
1911
def _node_to_position(self, node):
1912
"""Convert an index value to position details."""
1913
bits = node[2].split(' ')
1914
# It would be nice not to read the entire gzip.
1915
start = int(bits[0])
1917
basis_end = int(bits[2])
1918
delta_end = int(bits[3])
1919
return node[0], start, stop, basis_end, delta_end
1921
def scan_unvalidated_index(self, graph_index):
1922
"""Inform this _GCGraphIndex that there is an unvalidated index.
1924
This allows this _GCGraphIndex to keep track of any missing
1925
compression parents we may want to have filled in to make those
1928
:param graph_index: A GraphIndex
1930
if self._key_dependencies is not None:
1931
# Add parent refs from graph_index (and discard parent refs that
1932
# the graph_index has).
1933
add_refs = self._key_dependencies.add_references
1934
for node in graph_index.iter_all_entries():
1935
add_refs(node[1], node[3][0])
1939
from bzrlib._groupcompress_py import (
1941
apply_delta_to_source,
1944
decode_copy_instruction,
1948
from bzrlib._groupcompress_pyx import (
1950
apply_delta_to_source,
1955
GroupCompressor = PyrexGroupCompressor
1957
GroupCompressor = PythonGroupCompressor
added
removed
bzrlib/groupcompress.py
