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."""
26
from bzrlib.lazy_import import lazy_import
27
lazy_import(globals(), """
40
from bzrlib.repofmt import pack_repo
43
from bzrlib.btree_index import BTreeBuilder
44
from bzrlib.lru_cache import LRUSizeCache
45
from bzrlib.versionedfile import (
49
ChunkedContentFactory,
50
FulltextContentFactory,
51
VersionedFilesWithFallbacks,
54
# Minimum number of uncompressed bytes to try fetch at once when retrieving
55
# groupcompress blocks.
58
_USE_LZMA = False and (pylzma is not None)
60
# osutils.sha_string('')
61
_null_sha1 = 'da39a3ee5e6b4b0d3255bfef95601890afd80709'
63
def sort_gc_optimal(parent_map):
64
"""Sort and group the keys in parent_map into groupcompress order.
66
groupcompress is defined (currently) as reverse-topological order, grouped
69
:return: A sorted-list of keys
71
# groupcompress ordering is approximately reverse topological,
72
# properly grouped by file-id.
74
for key, value in parent_map.iteritems():
75
if isinstance(key, str) or len(key) == 1:
80
per_prefix_map[prefix][key] = value
82
per_prefix_map[prefix] = {key: value}
85
for prefix in sorted(per_prefix_map):
86
present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
90
# The max zlib window size is 32kB, so if we set 'max_size' output of the
91
# decompressor to the requested bytes + 32kB, then we should guarantee
92
# num_bytes coming out.
93
_ZLIB_DECOMP_WINDOW = 32*1024
95
class GroupCompressBlock(object):
96
"""An object which maintains the internal structure of the compressed data.
98
This tracks the meta info (start of text, length, type, etc.)
101
# Group Compress Block v1 Zlib
102
GCB_HEADER = 'gcb1z\n'
103
# Group Compress Block v1 Lzma
104
GCB_LZ_HEADER = 'gcb1l\n'
105
GCB_KNOWN_HEADERS = (GCB_HEADER, GCB_LZ_HEADER)
108
# map by key? or just order in file?
109
self._compressor_name = None
110
self._z_content_chunks = None
111
self._z_content_decompressor = None
112
self._z_content_length = None
113
self._content_length = None
115
self._content_chunks = None
118
# This is the maximum number of bytes this object will reference if
119
# everything is decompressed. However, if we decompress less than
120
# everything... (this would cause some problems for LRUSizeCache)
121
return self._content_length + self._z_content_length
123
def _ensure_content(self, num_bytes=None):
124
"""Make sure that content has been expanded enough.
126
:param num_bytes: Ensure that we have extracted at least num_bytes of
127
content. If None, consume everything
129
if self._content_length is None:
130
raise AssertionError('self._content_length should never be None')
131
if num_bytes is None:
132
num_bytes = self._content_length
133
elif (self._content_length is not None
134
and num_bytes > self._content_length):
135
raise AssertionError(
136
'requested num_bytes (%d) > content length (%d)'
137
% (num_bytes, self._content_length))
138
# Expand the content if required
139
if self._content is None:
140
if self._content_chunks is not None:
141
self._content = ''.join(self._content_chunks)
142
self._content_chunks = None
143
if self._content is None:
144
# We join self._z_content_chunks here, because if we are
145
# decompressing, then it is *very* likely that we have a single
147
if self._z_content_chunks is None:
148
raise AssertionError('No content to decompress')
149
z_content = ''.join(self._z_content_chunks)
152
elif self._compressor_name == 'lzma':
153
# We don't do partial lzma decomp yet
154
self._content = pylzma.decompress(z_content)
155
elif self._compressor_name == 'zlib':
156
# Start a zlib decompressor
157
if num_bytes * 4 > self._content_length * 3:
158
# If we are requesting more that 3/4ths of the content,
159
# just extract the whole thing in a single pass
160
num_bytes = self._content_length
161
self._content = zlib.decompress(z_content)
163
self._z_content_decompressor = zlib.decompressobj()
164
# Seed the decompressor with the uncompressed bytes, so
165
# that the rest of the code is simplified
166
self._content = self._z_content_decompressor.decompress(
167
z_content, num_bytes + _ZLIB_DECOMP_WINDOW)
168
if not self._z_content_decompressor.unconsumed_tail:
169
self._z_content_decompressor = None
171
raise AssertionError('Unknown compressor: %r'
172
% self._compressor_name)
173
# Any bytes remaining to be decompressed will be in the decompressors
176
# Do we have enough bytes already?
177
if len(self._content) >= num_bytes:
179
# If we got this far, and don't have a decompressor, something is wrong
180
if self._z_content_decompressor is None:
181
raise AssertionError(
182
'No decompressor to decompress %d bytes' % num_bytes)
183
remaining_decomp = self._z_content_decompressor.unconsumed_tail
184
if not remaining_decomp:
185
raise AssertionError('Nothing left to decompress')
186
needed_bytes = num_bytes - len(self._content)
187
# We always set max_size to 32kB over the minimum needed, so that
188
# zlib will give us as much as we really want.
189
# TODO: If this isn't good enough, we could make a loop here,
190
# that keeps expanding the request until we get enough
191
self._content += self._z_content_decompressor.decompress(
192
remaining_decomp, needed_bytes + _ZLIB_DECOMP_WINDOW)
193
if len(self._content) < num_bytes:
194
raise AssertionError('%d bytes wanted, only %d available'
195
% (num_bytes, len(self._content)))
196
if not self._z_content_decompressor.unconsumed_tail:
197
# The stream is finished
198
self._z_content_decompressor = None
200
def _parse_bytes(self, bytes, pos):
201
"""Read the various lengths from the header.
203
This also populates the various 'compressed' buffers.
205
:return: The position in bytes just after the last newline
207
# At present, we have 2 integers for the compressed and uncompressed
208
# content. In base10 (ascii) 14 bytes can represent > 1TB, so to avoid
209
# checking too far, cap the search to 14 bytes.
210
pos2 = bytes.index('\n', pos, pos + 14)
211
self._z_content_length = int(bytes[pos:pos2])
213
pos2 = bytes.index('\n', pos, pos + 14)
214
self._content_length = int(bytes[pos:pos2])
216
if len(bytes) != (pos + self._z_content_length):
217
# XXX: Define some GCCorrupt error ?
218
raise AssertionError('Invalid bytes: (%d) != %d + %d' %
219
(len(bytes), pos, self._z_content_length))
220
self._z_content_chunks = (bytes[pos:],)
223
def _z_content(self):
224
"""Return z_content_chunks as a simple string.
226
Meant only to be used by the test suite.
228
if self._z_content_chunks is not None:
229
return ''.join(self._z_content_chunks)
233
def from_bytes(cls, bytes):
235
if bytes[:6] not in cls.GCB_KNOWN_HEADERS:
236
raise ValueError('bytes did not start with any of %r'
237
% (cls.GCB_KNOWN_HEADERS,))
238
# XXX: why not testing the whole header ?
240
out._compressor_name = 'zlib'
241
elif bytes[4] == 'l':
242
out._compressor_name = 'lzma'
244
raise ValueError('unknown compressor: %r' % (bytes,))
245
out._parse_bytes(bytes, 6)
248
def extract(self, key, start, end, sha1=None):
249
"""Extract the text for a specific key.
251
:param key: The label used for this content
252
:param sha1: TODO (should we validate only when sha1 is supplied?)
253
:return: The bytes for the content
255
if start == end == 0:
257
self._ensure_content(end)
258
# The bytes are 'f' or 'd' for the type, then a variable-length
259
# base128 integer for the content size, then the actual content
260
# We know that the variable-length integer won't be longer than 5
261
# bytes (it takes 5 bytes to encode 2^32)
262
c = self._content[start]
267
raise ValueError('Unknown content control code: %s'
270
content_len, len_len = decode_base128_int(
271
self._content[start + 1:start + 6])
272
content_start = start + 1 + len_len
273
if end != content_start + content_len:
274
raise ValueError('end != len according to field header'
275
' %s != %s' % (end, content_start + content_len))
277
bytes = self._content[content_start:end]
279
bytes = apply_delta_to_source(self._content, content_start, end)
282
def set_chunked_content(self, content_chunks, length):
283
"""Set the content of this block to the given chunks."""
284
# If we have lots of short lines, it is may be more efficient to join
285
# the content ahead of time. If the content is <10MiB, we don't really
286
# care about the extra memory consumption, so we can just pack it and
287
# be done. However, timing showed 18s => 17.9s for repacking 1k revs of
288
# mysql, which is below the noise margin
289
self._content_length = length
290
self._content_chunks = content_chunks
292
self._z_content_chunks = None
294
def set_content(self, content):
295
"""Set the content of this block."""
296
self._content_length = len(content)
297
self._content = content
298
self._z_content_chunks = None
300
def _create_z_content_using_lzma(self):
301
if self._content_chunks is not None:
302
self._content = ''.join(self._content_chunks)
303
self._content_chunks = None
304
if self._content is None:
305
raise AssertionError('Nothing to compress')
306
z_content = pylzma.compress(self._content)
307
self._z_content_chunks = (z_content,)
308
self._z_content_length = len(z_content)
310
def _create_z_content_from_chunks(self, chunks):
311
compressor = zlib.compressobj(zlib.Z_DEFAULT_COMPRESSION)
312
# Peak in this point is 1 fulltext, 1 compressed text, + zlib overhead
313
# (measured peak is maybe 30MB over the above...)
314
compressed_chunks = map(compressor.compress, chunks)
315
compressed_chunks.append(compressor.flush())
316
# Ignore empty chunks
317
self._z_content_chunks = [c for c in compressed_chunks if c]
318
self._z_content_length = sum(map(len, self._z_content_chunks))
320
def _create_z_content(self):
321
if self._z_content_chunks is not None:
324
self._create_z_content_using_lzma()
326
if self._content_chunks is not None:
327
chunks = self._content_chunks
329
chunks = (self._content,)
330
self._create_z_content_from_chunks(chunks)
333
"""Create the byte stream as a series of 'chunks'"""
334
self._create_z_content()
336
header = self.GCB_LZ_HEADER
338
header = self.GCB_HEADER
339
chunks = ['%s%d\n%d\n'
340
% (header, self._z_content_length, self._content_length),
342
chunks.extend(self._z_content_chunks)
343
total_len = sum(map(len, chunks))
344
return total_len, chunks
347
"""Encode the information into a byte stream."""
348
total_len, chunks = self.to_chunks()
349
return ''.join(chunks)
351
def _dump(self, include_text=False):
352
"""Take this block, and spit out a human-readable structure.
354
:param include_text: Inserts also include text bits, chose whether you
355
want this displayed in the dump or not.
356
:return: A dump of the given block. The layout is something like:
357
[('f', length), ('d', delta_length, text_length, [delta_info])]
358
delta_info := [('i', num_bytes, text), ('c', offset, num_bytes),
361
self._ensure_content()
364
while pos < self._content_length:
365
kind = self._content[pos]
367
if kind not in ('f', 'd'):
368
raise ValueError('invalid kind character: %r' % (kind,))
369
content_len, len_len = decode_base128_int(
370
self._content[pos:pos + 5])
372
if content_len + pos > self._content_length:
373
raise ValueError('invalid content_len %d for record @ pos %d'
374
% (content_len, pos - len_len - 1))
375
if kind == 'f': # Fulltext
377
text = self._content[pos:pos+content_len]
378
result.append(('f', content_len, text))
380
result.append(('f', content_len))
381
elif kind == 'd': # Delta
382
delta_content = self._content[pos:pos+content_len]
384
# The first entry in a delta is the decompressed length
385
decomp_len, delta_pos = decode_base128_int(delta_content)
386
result.append(('d', content_len, decomp_len, delta_info))
388
while delta_pos < content_len:
389
c = ord(delta_content[delta_pos])
393
delta_pos) = decode_copy_instruction(delta_content, c,
396
text = self._content[offset:offset+length]
397
delta_info.append(('c', offset, length, text))
399
delta_info.append(('c', offset, length))
400
measured_len += length
403
txt = delta_content[delta_pos:delta_pos+c]
406
delta_info.append(('i', c, txt))
409
if delta_pos != content_len:
410
raise ValueError('Delta consumed a bad number of bytes:'
411
' %d != %d' % (delta_pos, content_len))
412
if measured_len != decomp_len:
413
raise ValueError('Delta claimed fulltext was %d bytes, but'
414
' extraction resulted in %d bytes'
415
% (decomp_len, measured_len))
420
class _LazyGroupCompressFactory(object):
421
"""Yield content from a GroupCompressBlock on demand."""
423
def __init__(self, key, parents, manager, start, end, first):
424
"""Create a _LazyGroupCompressFactory
426
:param key: The key of just this record
427
:param parents: The parents of this key (possibly None)
428
:param gc_block: A GroupCompressBlock object
429
:param start: Offset of the first byte for this record in the
431
:param end: Offset of the byte just after the end of this record
432
(ie, bytes = content[start:end])
433
:param first: Is this the first Factory for the given block?
436
self.parents = parents
438
# Note: This attribute coupled with Manager._factories creates a
439
# reference cycle. Perhaps we would rather use a weakref(), or
440
# find an appropriate time to release the ref. After the first
441
# get_bytes_as call? After Manager.get_record_stream() returns
443
self._manager = manager
445
self.storage_kind = 'groupcompress-block'
447
self.storage_kind = 'groupcompress-block-ref'
453
return '%s(%s, first=%s)' % (self.__class__.__name__,
454
self.key, self._first)
456
def get_bytes_as(self, storage_kind):
457
if storage_kind == self.storage_kind:
459
# wire bytes, something...
460
return self._manager._wire_bytes()
463
if storage_kind in ('fulltext', 'chunked'):
464
if self._bytes is None:
465
# Grab and cache the raw bytes for this entry
466
# and break the ref-cycle with _manager since we don't need it
468
self._manager._prepare_for_extract()
469
block = self._manager._block
470
self._bytes = block.extract(self.key, self._start, self._end)
471
# There are code paths that first extract as fulltext, and then
472
# extract as storage_kind (smart fetch). So we don't break the
473
# refcycle here, but instead in manager.get_record_stream()
474
if storage_kind == 'fulltext':
478
raise errors.UnavailableRepresentation(self.key, storage_kind,
482
class _LazyGroupContentManager(object):
483
"""This manages a group of _LazyGroupCompressFactory objects."""
485
_max_cut_fraction = 0.75 # We allow a block to be trimmed to 75% of
486
# current size, and still be considered
488
_full_block_size = 4*1024*1024
489
_full_mixed_block_size = 2*1024*1024
490
_full_enough_block_size = 3*1024*1024 # size at which we won't repack
491
_full_enough_mixed_block_size = 2*768*1024 # 1.5MB
493
def __init__(self, block):
495
# We need to preserve the ordering
499
def add_factory(self, key, parents, start, end):
500
if not self._factories:
504
# Note that this creates a reference cycle....
505
factory = _LazyGroupCompressFactory(key, parents, self,
506
start, end, first=first)
507
# max() works here, but as a function call, doing a compare seems to be
508
# significantly faster, timeit says 250ms for max() and 100ms for the
510
if end > self._last_byte:
511
self._last_byte = end
512
self._factories.append(factory)
514
def get_record_stream(self):
515
"""Get a record for all keys added so far."""
516
for factory in self._factories:
518
# Break the ref-cycle
519
factory._bytes = None
520
factory._manager = None
521
# TODO: Consider setting self._factories = None after the above loop,
522
# as it will break the reference cycle
524
def _trim_block(self, last_byte):
525
"""Create a new GroupCompressBlock, with just some of the content."""
526
# None of the factories need to be adjusted, because the content is
527
# located in an identical place. Just that some of the unreferenced
528
# trailing bytes are stripped
529
trace.mutter('stripping trailing bytes from groupcompress block'
530
' %d => %d', self._block._content_length, last_byte)
531
new_block = GroupCompressBlock()
532
self._block._ensure_content(last_byte)
533
new_block.set_content(self._block._content[:last_byte])
534
self._block = new_block
536
def _rebuild_block(self):
537
"""Create a new GroupCompressBlock with only the referenced texts."""
538
compressor = GroupCompressor()
540
old_length = self._block._content_length
542
for factory in self._factories:
543
bytes = factory.get_bytes_as('fulltext')
544
(found_sha1, start_point, end_point,
545
type) = compressor.compress(factory.key, bytes, factory.sha1)
546
# Now update this factory with the new offsets, etc
547
factory.sha1 = found_sha1
548
factory._start = start_point
549
factory._end = end_point
550
self._last_byte = end_point
551
new_block = compressor.flush()
552
# TODO: Should we check that new_block really *is* smaller than the old
553
# block? It seems hard to come up with a method that it would
554
# expand, since we do full compression again. Perhaps based on a
555
# request that ends up poorly ordered?
556
delta = time.time() - tstart
557
self._block = new_block
558
trace.mutter('creating new compressed block on-the-fly in %.3fs'
559
' %d bytes => %d bytes', delta, old_length,
560
self._block._content_length)
562
def _prepare_for_extract(self):
563
"""A _LazyGroupCompressFactory is about to extract to fulltext."""
564
# We expect that if one child is going to fulltext, all will be. This
565
# helps prevent all of them from extracting a small amount at a time.
566
# Which in itself isn't terribly expensive, but resizing 2MB 32kB at a
567
# time (self._block._content) is a little expensive.
568
self._block._ensure_content(self._last_byte)
570
def _check_rebuild_action(self):
571
"""Check to see if our block should be repacked."""
574
for factory in self._factories:
575
total_bytes_used += factory._end - factory._start
576
if last_byte_used < factory._end:
577
last_byte_used = factory._end
578
# If we are using more than half of the bytes from the block, we have
579
# nothing else to check
580
if total_bytes_used * 2 >= self._block._content_length:
581
return None, last_byte_used, total_bytes_used
582
# We are using less than 50% of the content. Is the content we are
583
# using at the beginning of the block? If so, we can just trim the
584
# tail, rather than rebuilding from scratch.
585
if total_bytes_used * 2 > last_byte_used:
586
return 'trim', last_byte_used, total_bytes_used
588
# We are using a small amount of the data, and it isn't just packed
589
# nicely at the front, so rebuild the content.
590
# Note: This would be *nicer* as a strip-data-from-group, rather than
591
# building it up again from scratch
592
# It might be reasonable to consider the fulltext sizes for
593
# different bits when deciding this, too. As you may have a small
594
# fulltext, and a trivial delta, and you are just trading around
595
# for another fulltext. If we do a simple 'prune' you may end up
596
# expanding many deltas into fulltexts, as well.
597
# If we build a cheap enough 'strip', then we could try a strip,
598
# if that expands the content, we then rebuild.
599
return 'rebuild', last_byte_used, total_bytes_used
601
def check_is_well_utilized(self):
602
"""Is the current block considered 'well utilized'?
604
This heuristic asks if the current block considers itself to be a fully
605
developed group, rather than just a loose collection of data.
607
if len(self._factories) == 1:
608
# A block of length 1 could be improved by combining with other
609
# groups - don't look deeper. Even larger than max size groups
610
# could compress well with adjacent versions of the same thing.
612
action, last_byte_used, total_bytes_used = self._check_rebuild_action()
613
block_size = self._block._content_length
614
if total_bytes_used < block_size * self._max_cut_fraction:
615
# This block wants to trim itself small enough that we want to
616
# consider it under-utilized.
618
# TODO: This code is meant to be the twin of _insert_record_stream's
619
# 'start_new_block' logic. It would probably be better to factor
620
# out that logic into a shared location, so that it stays
622
# We currently assume a block is properly utilized whenever it is >75%
623
# of the size of a 'full' block. In normal operation, a block is
624
# considered full when it hits 4MB of same-file content. So any block
625
# >3MB is 'full enough'.
626
# The only time this isn't true is when a given block has large-object
627
# content. (a single file >4MB, etc.)
628
# Under these circumstances, we allow a block to grow to
629
# 2 x largest_content. Which means that if a given block had a large
630
# object, it may actually be under-utilized. However, given that this
631
# is 'pack-on-the-fly' it is probably reasonable to not repack large
632
# content blobs on-the-fly. Note that because we return False for all
633
# 1-item blobs, we will repack them; we may wish to reevaluate our
634
# treatment of large object blobs in the future.
635
if block_size >= self._full_enough_block_size:
637
# If a block is <3MB, it still may be considered 'full' if it contains
638
# mixed content. The current rule is 2MB of mixed content is considered
639
# full. So check to see if this block contains mixed content, and
640
# set the threshold appropriately.
642
for factory in self._factories:
643
prefix = factory.key[:-1]
644
if common_prefix is None:
645
common_prefix = prefix
646
elif prefix != common_prefix:
647
# Mixed content, check the size appropriately
648
if block_size >= self._full_enough_mixed_block_size:
651
# The content failed both the mixed check and the single-content check
652
# so obviously it is not fully utilized
653
# TODO: there is one other constraint that isn't being checked
654
# namely, that the entries in the block are in the appropriate
655
# order. For example, you could insert the entries in exactly
656
# reverse groupcompress order, and we would think that is ok.
657
# (all the right objects are in one group, and it is fully
658
# utilized, etc.) For now, we assume that case is rare,
659
# especially since we should always fetch in 'groupcompress'
663
def _check_rebuild_block(self):
664
action, last_byte_used, total_bytes_used = self._check_rebuild_action()
668
self._trim_block(last_byte_used)
669
elif action == 'rebuild':
670
self._rebuild_block()
672
raise ValueError('unknown rebuild action: %r' % (action,))
674
def _wire_bytes(self):
675
"""Return a byte stream suitable for transmitting over the wire."""
676
self._check_rebuild_block()
677
# The outer block starts with:
678
# 'groupcompress-block\n'
679
# <length of compressed key info>\n
680
# <length of uncompressed info>\n
681
# <length of gc block>\n
684
lines = ['groupcompress-block\n']
685
# The minimal info we need is the key, the start offset, and the
686
# parents. The length and type are encoded in the record itself.
687
# However, passing in the other bits makes it easier. The list of
688
# keys, and the start offset, the length
690
# 1 line with parents, '' for ()
691
# 1 line for start offset
692
# 1 line for end byte
694
for factory in self._factories:
695
key_bytes = '\x00'.join(factory.key)
696
parents = factory.parents
698
parent_bytes = 'None:'
700
parent_bytes = '\t'.join('\x00'.join(key) for key in parents)
701
record_header = '%s\n%s\n%d\n%d\n' % (
702
key_bytes, parent_bytes, factory._start, factory._end)
703
header_lines.append(record_header)
704
# TODO: Can we break the refcycle at this point and set
705
# factory._manager = None?
706
header_bytes = ''.join(header_lines)
708
header_bytes_len = len(header_bytes)
709
z_header_bytes = zlib.compress(header_bytes)
711
z_header_bytes_len = len(z_header_bytes)
712
block_bytes_len, block_chunks = self._block.to_chunks()
713
lines.append('%d\n%d\n%d\n' % (z_header_bytes_len, header_bytes_len,
715
lines.append(z_header_bytes)
716
lines.extend(block_chunks)
717
del z_header_bytes, block_chunks
718
# TODO: This is a point where we will double the memory consumption. To
719
# avoid this, we probably have to switch to a 'chunked' api
720
return ''.join(lines)
723
def from_bytes(cls, bytes):
724
# TODO: This does extra string copying, probably better to do it a
725
# different way. At a minimum this creates 2 copies of the
727
(storage_kind, z_header_len, header_len,
728
block_len, rest) = bytes.split('\n', 4)
730
if storage_kind != 'groupcompress-block':
731
raise ValueError('Unknown storage kind: %s' % (storage_kind,))
732
z_header_len = int(z_header_len)
733
if len(rest) < z_header_len:
734
raise ValueError('Compressed header len shorter than all bytes')
735
z_header = rest[:z_header_len]
736
header_len = int(header_len)
737
header = zlib.decompress(z_header)
738
if len(header) != header_len:
739
raise ValueError('invalid length for decompressed bytes')
741
block_len = int(block_len)
742
if len(rest) != z_header_len + block_len:
743
raise ValueError('Invalid length for block')
744
block_bytes = rest[z_header_len:]
746
# So now we have a valid GCB, we just need to parse the factories that
748
header_lines = header.split('\n')
750
last = header_lines.pop()
752
raise ValueError('header lines did not end with a trailing'
754
if len(header_lines) % 4 != 0:
755
raise ValueError('The header was not an even multiple of 4 lines')
756
block = GroupCompressBlock.from_bytes(block_bytes)
759
for start in xrange(0, len(header_lines), 4):
761
key = tuple(header_lines[start].split('\x00'))
762
parents_line = header_lines[start+1]
763
if parents_line == 'None:':
766
parents = tuple([tuple(segment.split('\x00'))
767
for segment in parents_line.split('\t')
769
start_offset = int(header_lines[start+2])
770
end_offset = int(header_lines[start+3])
771
result.add_factory(key, parents, start_offset, end_offset)
775
def network_block_to_records(storage_kind, bytes, line_end):
776
if storage_kind != 'groupcompress-block':
777
raise ValueError('Unknown storage kind: %s' % (storage_kind,))
778
manager = _LazyGroupContentManager.from_bytes(bytes)
779
return manager.get_record_stream()
782
class _CommonGroupCompressor(object):
785
"""Create a GroupCompressor."""
790
self.labels_deltas = {}
791
self._delta_index = None # Set by the children
792
self._block = GroupCompressBlock()
794
def compress(self, key, bytes, expected_sha, nostore_sha=None, soft=False):
795
"""Compress lines with label key.
797
:param key: A key tuple. It is stored in the output
798
for identification of the text during decompression. If the last
799
element is 'None' it is replaced with the sha1 of the text -
801
:param bytes: The bytes to be compressed
802
:param expected_sha: If non-None, the sha the lines are believed to
803
have. During compression the sha is calculated; a mismatch will
805
:param nostore_sha: If the computed sha1 sum matches, we will raise
806
ExistingContent rather than adding the text.
807
:param soft: Do a 'soft' compression. This means that we require larger
808
ranges to match to be considered for a copy command.
810
:return: The sha1 of lines, the start and end offsets in the delta, and
811
the type ('fulltext' or 'delta').
813
:seealso VersionedFiles.add_lines:
815
if not bytes: # empty, like a dir entry, etc
816
if nostore_sha == _null_sha1:
817
raise errors.ExistingContent()
818
return _null_sha1, 0, 0, 'fulltext'
819
# we assume someone knew what they were doing when they passed it in
820
if expected_sha is not None:
823
sha1 = osutils.sha_string(bytes)
824
if nostore_sha is not None:
825
if sha1 == nostore_sha:
826
raise errors.ExistingContent()
828
key = key[:-1] + ('sha1:' + sha1,)
830
start, end, type = self._compress(key, bytes, len(bytes) / 2, soft)
831
return sha1, start, end, type
833
def _compress(self, key, bytes, max_delta_size, soft=False):
834
"""Compress lines with label key.
836
:param key: A key tuple. It is stored in the output for identification
837
of the text during decompression.
839
:param bytes: The bytes to be compressed
841
:param max_delta_size: The size above which we issue a fulltext instead
844
:param soft: Do a 'soft' compression. This means that we require larger
845
ranges to match to be considered for a copy command.
847
:return: The sha1 of lines, the start and end offsets in the delta, and
848
the type ('fulltext' or 'delta').
850
raise NotImplementedError(self._compress)
852
def extract(self, key):
853
"""Extract a key previously added to the compressor.
855
:param key: The key to extract.
856
:return: An iterable over bytes and the sha1.
858
(start_byte, start_chunk, end_byte, end_chunk) = self.labels_deltas[key]
859
delta_chunks = self.chunks[start_chunk:end_chunk]
860
stored_bytes = ''.join(delta_chunks)
861
if stored_bytes[0] == 'f':
862
fulltext_len, offset = decode_base128_int(stored_bytes[1:10])
863
data_len = fulltext_len + 1 + offset
864
if data_len != len(stored_bytes):
865
raise ValueError('Index claimed fulltext len, but stored bytes'
867
% (len(stored_bytes), data_len))
868
bytes = stored_bytes[offset + 1:]
870
# XXX: This is inefficient at best
871
source = ''.join(self.chunks[:start_chunk])
872
if stored_bytes[0] != 'd':
873
raise ValueError('Unknown content kind, bytes claim %s'
874
% (stored_bytes[0],))
875
delta_len, offset = decode_base128_int(stored_bytes[1:10])
876
data_len = delta_len + 1 + offset
877
if data_len != len(stored_bytes):
878
raise ValueError('Index claimed delta len, but stored bytes'
880
% (len(stored_bytes), data_len))
881
bytes = apply_delta(source, stored_bytes[offset + 1:])
882
bytes_sha1 = osutils.sha_string(bytes)
883
return bytes, bytes_sha1
886
"""Finish this group, creating a formatted stream.
888
After calling this, the compressor should no longer be used
890
self._block.set_chunked_content(self.chunks, self.endpoint)
892
self._delta_index = None
896
"""Call this if you want to 'revoke' the last compression.
898
After this, the data structures will be rolled back, but you cannot do
901
self._delta_index = None
902
del self.chunks[self._last[0]:]
903
self.endpoint = self._last[1]
907
"""Return the overall compression ratio."""
908
return float(self.input_bytes) / float(self.endpoint)
911
class PythonGroupCompressor(_CommonGroupCompressor):
914
"""Create a GroupCompressor.
916
Used only if the pyrex version is not available.
918
super(PythonGroupCompressor, self).__init__()
919
self._delta_index = LinesDeltaIndex([])
920
# The actual content is managed by LinesDeltaIndex
921
self.chunks = self._delta_index.lines
923
def _compress(self, key, bytes, max_delta_size, soft=False):
924
"""see _CommonGroupCompressor._compress"""
925
input_len = len(bytes)
926
new_lines = osutils.split_lines(bytes)
927
out_lines, index_lines = self._delta_index.make_delta(
928
new_lines, bytes_length=input_len, soft=soft)
929
delta_length = sum(map(len, out_lines))
930
if delta_length > max_delta_size:
931
# The delta is longer than the fulltext, insert a fulltext
933
out_lines = ['f', encode_base128_int(input_len)]
934
out_lines.extend(new_lines)
935
index_lines = [False, False]
936
index_lines.extend([True] * len(new_lines))
938
# this is a worthy delta, output it
941
# Update the delta_length to include those two encoded integers
942
out_lines[1] = encode_base128_int(delta_length)
944
start = self.endpoint
945
chunk_start = len(self.chunks)
946
self._last = (chunk_start, self.endpoint)
947
self._delta_index.extend_lines(out_lines, index_lines)
948
self.endpoint = self._delta_index.endpoint
949
self.input_bytes += input_len
950
chunk_end = len(self.chunks)
951
self.labels_deltas[key] = (start, chunk_start,
952
self.endpoint, chunk_end)
953
return start, self.endpoint, type
956
class PyrexGroupCompressor(_CommonGroupCompressor):
957
"""Produce a serialised group of compressed texts.
959
It contains code very similar to SequenceMatcher because of having a similar
960
task. However some key differences apply:
961
- there is no junk, we want a minimal edit not a human readable diff.
962
- we don't filter very common lines (because we don't know where a good
963
range will start, and after the first text we want to be emitting minmal
965
- we chain the left side, not the right side
966
- we incrementally update the adjacency matrix as new lines are provided.
967
- we look for matches in all of the left side, so the routine which does
968
the analagous task of find_longest_match does not need to filter on the
973
super(PyrexGroupCompressor, self).__init__()
974
self._delta_index = DeltaIndex()
976
def _compress(self, key, bytes, max_delta_size, soft=False):
977
"""see _CommonGroupCompressor._compress"""
978
input_len = len(bytes)
979
# By having action/label/sha1/len, we can parse the group if the index
980
# was ever destroyed, we have the key in 'label', we know the final
981
# bytes are valid from sha1, and we know where to find the end of this
982
# record because of 'len'. (the delta record itself will store the
983
# total length for the expanded record)
984
# 'len: %d\n' costs approximately 1% increase in total data
985
# Having the labels at all costs us 9-10% increase, 38% increase for
986
# inventory pages, and 5.8% increase for text pages
987
# new_chunks = ['label:%s\nsha1:%s\n' % (label, sha1)]
988
if self._delta_index._source_offset != self.endpoint:
989
raise AssertionError('_source_offset != endpoint'
990
' somehow the DeltaIndex got out of sync with'
992
delta = self._delta_index.make_delta(bytes, max_delta_size)
995
enc_length = encode_base128_int(len(bytes))
996
len_mini_header = 1 + len(enc_length)
997
self._delta_index.add_source(bytes, len_mini_header)
998
new_chunks = ['f', enc_length, bytes]
1001
enc_length = encode_base128_int(len(delta))
1002
len_mini_header = 1 + len(enc_length)
1003
new_chunks = ['d', enc_length, delta]
1004
self._delta_index.add_delta_source(delta, len_mini_header)
1006
start = self.endpoint
1007
chunk_start = len(self.chunks)
1008
# Now output these bytes
1009
self._output_chunks(new_chunks)
1010
self.input_bytes += input_len
1011
chunk_end = len(self.chunks)
1012
self.labels_deltas[key] = (start, chunk_start,
1013
self.endpoint, chunk_end)
1014
if not self._delta_index._source_offset == self.endpoint:
1015
raise AssertionError('the delta index is out of sync'
1016
'with the output lines %s != %s'
1017
% (self._delta_index._source_offset, self.endpoint))
1018
return start, self.endpoint, type
1020
def _output_chunks(self, new_chunks):
1021
"""Output some chunks.
1023
:param new_chunks: The chunks to output.
1025
self._last = (len(self.chunks), self.endpoint)
1026
endpoint = self.endpoint
1027
self.chunks.extend(new_chunks)
1028
endpoint += sum(map(len, new_chunks))
1029
self.endpoint = endpoint
1032
def make_pack_factory(graph, delta, keylength, inconsistency_fatal=True):
1033
"""Create a factory for creating a pack based groupcompress.
1035
This is only functional enough to run interface tests, it doesn't try to
1036
provide a full pack environment.
1038
:param graph: Store a graph.
1039
:param delta: Delta compress contents.
1040
:param keylength: How long should keys be.
1042
def factory(transport):
1047
graph_index = BTreeBuilder(reference_lists=ref_length,
1048
key_elements=keylength)
1049
stream = transport.open_write_stream('newpack')
1050
writer = pack.ContainerWriter(stream.write)
1052
index = _GCGraphIndex(graph_index, lambda:True, parents=parents,
1053
add_callback=graph_index.add_nodes,
1054
inconsistency_fatal=inconsistency_fatal)
1055
access = pack_repo._DirectPackAccess({})
1056
access.set_writer(writer, graph_index, (transport, 'newpack'))
1057
result = GroupCompressVersionedFiles(index, access, delta)
1058
result.stream = stream
1059
result.writer = writer
1064
def cleanup_pack_group(versioned_files):
1065
versioned_files.writer.end()
1066
versioned_files.stream.close()
1069
class _BatchingBlockFetcher(object):
1070
"""Fetch group compress blocks in batches.
1072
:ivar total_bytes: int of expected number of bytes needed to fetch the
1073
currently pending batch.
1076
def __init__(self, gcvf, locations):
1078
self.locations = locations
1080
self.batch_memos = {}
1081
self.memos_to_get = []
1082
self.total_bytes = 0
1083
self.last_read_memo = None
1086
def add_key(self, key):
1087
"""Add another to key to fetch.
1089
:return: The estimated number of bytes needed to fetch the batch so
1092
self.keys.append(key)
1093
index_memo, _, _, _ = self.locations[key]
1094
read_memo = index_memo[0:3]
1095
# Three possibilities for this read_memo:
1096
# - it's already part of this batch; or
1097
# - it's not yet part of this batch, but is already cached; or
1098
# - it's not yet part of this batch and will need to be fetched.
1099
if read_memo in self.batch_memos:
1100
# This read memo is already in this batch.
1101
return self.total_bytes
1103
cached_block = self.gcvf._group_cache[read_memo]
1105
# This read memo is new to this batch, and the data isn't cached
1107
self.batch_memos[read_memo] = None
1108
self.memos_to_get.append(read_memo)
1109
byte_length = read_memo[2]
1110
self.total_bytes += byte_length
1112
# This read memo is new to this batch, but cached.
1113
# Keep a reference to the cached block in batch_memos because it's
1114
# certain that we'll use it when this batch is processed, but
1115
# there's a risk that it would fall out of _group_cache between now
1117
self.batch_memos[read_memo] = cached_block
1118
return self.total_bytes
1120
def _flush_manager(self):
1121
if self.manager is not None:
1122
for factory in self.manager.get_record_stream():
1125
self.last_read_memo = None
1127
def yield_factories(self, full_flush=False):
1128
"""Yield factories for keys added since the last yield. They will be
1129
returned in the order they were added via add_key.
1131
:param full_flush: by default, some results may not be returned in case
1132
they can be part of the next batch. If full_flush is True, then
1133
all results are returned.
1135
if self.manager is None and not self.keys:
1137
# Fetch all memos in this batch.
1138
blocks = self.gcvf._get_blocks(self.memos_to_get)
1139
# Turn blocks into factories and yield them.
1140
memos_to_get_stack = list(self.memos_to_get)
1141
memos_to_get_stack.reverse()
1142
for key in self.keys:
1143
index_memo, _, parents, _ = self.locations[key]
1144
read_memo = index_memo[:3]
1145
if self.last_read_memo != read_memo:
1146
# We are starting a new block. If we have a
1147
# manager, we have found everything that fits for
1148
# now, so yield records
1149
for factory in self._flush_manager():
1151
# Now start a new manager.
1152
if memos_to_get_stack and memos_to_get_stack[-1] == read_memo:
1153
# The next block from _get_blocks will be the block we
1155
block_read_memo, block = blocks.next()
1156
if block_read_memo != read_memo:
1157
raise AssertionError(
1158
"block_read_memo out of sync with read_memo"
1159
"(%r != %r)" % (block_read_memo, read_memo))
1160
self.batch_memos[read_memo] = block
1161
memos_to_get_stack.pop()
1163
block = self.batch_memos[read_memo]
1164
self.manager = _LazyGroupContentManager(block)
1165
self.last_read_memo = read_memo
1166
start, end = index_memo[3:5]
1167
self.manager.add_factory(key, parents, start, end)
1169
for factory in self._flush_manager():
1172
self.batch_memos.clear()
1173
del self.memos_to_get[:]
1174
self.total_bytes = 0
1177
class GroupCompressVersionedFiles(VersionedFilesWithFallbacks):
1178
"""A group-compress based VersionedFiles implementation."""
1180
def __init__(self, index, access, delta=True, _unadded_refs=None,
1182
"""Create a GroupCompressVersionedFiles object.
1184
:param index: The index object storing access and graph data.
1185
:param access: The access object storing raw data.
1186
:param delta: Whether to delta compress or just entropy compress.
1187
:param _unadded_refs: private parameter, don't use.
1188
:param _group_cache: private parameter, don't use.
1191
self._access = access
1193
if _unadded_refs is None:
1195
self._unadded_refs = _unadded_refs
1196
if _group_cache is None:
1197
_group_cache = LRUSizeCache(max_size=50*1024*1024)
1198
self._group_cache = _group_cache
1199
self._immediate_fallback_vfs = []
1201
def without_fallbacks(self):
1202
"""Return a clone of this object without any fallbacks configured."""
1203
return GroupCompressVersionedFiles(self._index, self._access,
1204
self._delta, _unadded_refs=dict(self._unadded_refs),
1205
_group_cache=self._group_cache)
1207
def add_lines(self, key, parents, lines, parent_texts=None,
1208
left_matching_blocks=None, nostore_sha=None, random_id=False,
1209
check_content=True):
1210
"""Add a text to the store.
1212
:param key: The key tuple of the text to add.
1213
:param parents: The parents key tuples of the text to add.
1214
:param lines: A list of lines. Each line must be a bytestring. And all
1215
of them except the last must be terminated with \n and contain no
1216
other \n's. The last line may either contain no \n's or a single
1217
terminating \n. If the lines list does meet this constraint the add
1218
routine may error or may succeed - but you will be unable to read
1219
the data back accurately. (Checking the lines have been split
1220
correctly is expensive and extremely unlikely to catch bugs so it
1221
is not done at runtime unless check_content is True.)
1222
:param parent_texts: An optional dictionary containing the opaque
1223
representations of some or all of the parents of version_id to
1224
allow delta optimisations. VERY IMPORTANT: the texts must be those
1225
returned by add_lines or data corruption can be caused.
1226
:param left_matching_blocks: a hint about which areas are common
1227
between the text and its left-hand-parent. The format is
1228
the SequenceMatcher.get_matching_blocks format.
1229
:param nostore_sha: Raise ExistingContent and do not add the lines to
1230
the versioned file if the digest of the lines matches this.
1231
:param random_id: If True a random id has been selected rather than
1232
an id determined by some deterministic process such as a converter
1233
from a foreign VCS. When True the backend may choose not to check
1234
for uniqueness of the resulting key within the versioned file, so
1235
this should only be done when the result is expected to be unique
1237
:param check_content: If True, the lines supplied are verified to be
1238
bytestrings that are correctly formed lines.
1239
:return: The text sha1, the number of bytes in the text, and an opaque
1240
representation of the inserted version which can be provided
1241
back to future add_lines calls in the parent_texts dictionary.
1243
self._index._check_write_ok()
1244
self._check_add(key, lines, random_id, check_content)
1246
# The caller might pass None if there is no graph data, but kndx
1247
# indexes can't directly store that, so we give them
1248
# an empty tuple instead.
1250
# double handling for now. Make it work until then.
1251
length = sum(map(len, lines))
1252
record = ChunkedContentFactory(key, parents, None, lines)
1253
sha1 = list(self._insert_record_stream([record], random_id=random_id,
1254
nostore_sha=nostore_sha))[0]
1255
return sha1, length, None
1257
def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
1258
"""See VersionedFiles._add_text()."""
1259
self._index._check_write_ok()
1260
self._check_add(key, None, random_id, check_content=False)
1261
if text.__class__ is not str:
1262
raise errors.BzrBadParameterUnicode("text")
1264
# The caller might pass None if there is no graph data, but kndx
1265
# indexes can't directly store that, so we give them
1266
# an empty tuple instead.
1268
# double handling for now. Make it work until then.
1270
record = FulltextContentFactory(key, parents, None, text)
1271
sha1 = list(self._insert_record_stream([record], random_id=random_id,
1272
nostore_sha=nostore_sha))[0]
1273
return sha1, length, None
1275
def add_fallback_versioned_files(self, a_versioned_files):
1276
"""Add a source of texts for texts not present in this knit.
1278
:param a_versioned_files: A VersionedFiles object.
1280
self._immediate_fallback_vfs.append(a_versioned_files)
1282
def annotate(self, key):
1283
"""See VersionedFiles.annotate."""
1284
ann = annotate.Annotator(self)
1285
return ann.annotate_flat(key)
1287
def get_annotator(self):
1288
return annotate.Annotator(self)
1290
def check(self, progress_bar=None, keys=None):
1291
"""See VersionedFiles.check()."""
1294
for record in self.get_record_stream(keys, 'unordered', True):
1295
record.get_bytes_as('fulltext')
1297
return self.get_record_stream(keys, 'unordered', True)
1299
def clear_cache(self):
1300
"""See VersionedFiles.clear_cache()"""
1301
self._group_cache.clear()
1302
self._index._graph_index.clear_cache()
1303
self._index._int_cache.clear()
1305
def _check_add(self, key, lines, random_id, check_content):
1306
"""check that version_id and lines are safe to add."""
1307
version_id = key[-1]
1308
if version_id is not None:
1309
if osutils.contains_whitespace(version_id):
1310
raise errors.InvalidRevisionId(version_id, self)
1311
self.check_not_reserved_id(version_id)
1312
# TODO: If random_id==False and the key is already present, we should
1313
# probably check that the existing content is identical to what is
1314
# being inserted, and otherwise raise an exception. This would make
1315
# the bundle code simpler.
1317
self._check_lines_not_unicode(lines)
1318
self._check_lines_are_lines(lines)
1320
def get_known_graph_ancestry(self, keys):
1321
"""Get a KnownGraph instance with the ancestry of keys."""
1322
# Note that this is identical to
1323
# KnitVersionedFiles.get_known_graph_ancestry, but they don't share
1325
parent_map, missing_keys = self._index.find_ancestry(keys)
1326
for fallback in self._transitive_fallbacks():
1327
if not missing_keys:
1329
(f_parent_map, f_missing_keys) = fallback._index.find_ancestry(
1331
parent_map.update(f_parent_map)
1332
missing_keys = f_missing_keys
1333
kg = _mod_graph.KnownGraph(parent_map)
1336
def get_parent_map(self, keys):
1337
"""Get a map of the graph parents of keys.
1339
:param keys: The keys to look up parents for.
1340
:return: A mapping from keys to parents. Absent keys are absent from
1343
return self._get_parent_map_with_sources(keys)[0]
1345
def _get_parent_map_with_sources(self, keys):
1346
"""Get a map of the parents of keys.
1348
:param keys: The keys to look up parents for.
1349
:return: A tuple. The first element is a mapping from keys to parents.
1350
Absent keys are absent from the mapping. The second element is a
1351
list with the locations each key was found in. The first element
1352
is the in-this-knit parents, the second the first fallback source,
1356
sources = [self._index] + self._immediate_fallback_vfs
1359
for source in sources:
1362
new_result = source.get_parent_map(missing)
1363
source_results.append(new_result)
1364
result.update(new_result)
1365
missing.difference_update(set(new_result))
1366
return result, source_results
1368
def _get_blocks(self, read_memos):
1369
"""Get GroupCompressBlocks for the given read_memos.
1371
:returns: a series of (read_memo, block) pairs, in the order they were
1375
for read_memo in read_memos:
1377
block = self._group_cache[read_memo]
1381
cached[read_memo] = block
1383
not_cached_seen = set()
1384
for read_memo in read_memos:
1385
if read_memo in cached:
1386
# Don't fetch what we already have
1388
if read_memo in not_cached_seen:
1389
# Don't try to fetch the same data twice
1391
not_cached.append(read_memo)
1392
not_cached_seen.add(read_memo)
1393
raw_records = self._access.get_raw_records(not_cached)
1394
for read_memo in read_memos:
1396
yield read_memo, cached[read_memo]
1398
# Read the block, and cache it.
1399
zdata = raw_records.next()
1400
block = GroupCompressBlock.from_bytes(zdata)
1401
self._group_cache[read_memo] = block
1402
cached[read_memo] = block
1403
yield read_memo, block
1405
def get_missing_compression_parent_keys(self):
1406
"""Return the keys of missing compression parents.
1408
Missing compression parents occur when a record stream was missing
1409
basis texts, or a index was scanned that had missing basis texts.
1411
# GroupCompress cannot currently reference texts that are not in the
1412
# group, so this is valid for now
1415
def get_record_stream(self, keys, ordering, include_delta_closure):
1416
"""Get a stream of records for keys.
1418
:param keys: The keys to include.
1419
:param ordering: Either 'unordered' or 'topological'. A topologically
1420
sorted stream has compression parents strictly before their
1422
:param include_delta_closure: If True then the closure across any
1423
compression parents will be included (in the opaque data).
1424
:return: An iterator of ContentFactory objects, each of which is only
1425
valid until the iterator is advanced.
1427
# keys might be a generator
1428
orig_keys = list(keys)
1432
if (not self._index.has_graph
1433
and ordering in ('topological', 'groupcompress')):
1434
# Cannot topological order when no graph has been stored.
1435
# but we allow 'as-requested' or 'unordered'
1436
ordering = 'unordered'
1438
remaining_keys = keys
1441
keys = set(remaining_keys)
1442
for content_factory in self._get_remaining_record_stream(keys,
1443
orig_keys, ordering, include_delta_closure):
1444
remaining_keys.discard(content_factory.key)
1445
yield content_factory
1447
except errors.RetryWithNewPacks, e:
1448
self._access.reload_or_raise(e)
1450
def _find_from_fallback(self, missing):
1451
"""Find whatever keys you can from the fallbacks.
1453
:param missing: A set of missing keys. This set will be mutated as keys
1454
are found from a fallback_vfs
1455
:return: (parent_map, key_to_source_map, source_results)
1456
parent_map the overall key => parent_keys
1457
key_to_source_map a dict from {key: source}
1458
source_results a list of (source: keys)
1461
key_to_source_map = {}
1463
for source in self._immediate_fallback_vfs:
1466
source_parents = source.get_parent_map(missing)
1467
parent_map.update(source_parents)
1468
source_parents = list(source_parents)
1469
source_results.append((source, source_parents))
1470
key_to_source_map.update((key, source) for key in source_parents)
1471
missing.difference_update(source_parents)
1472
return parent_map, key_to_source_map, source_results
1474
def _get_ordered_source_keys(self, ordering, parent_map, key_to_source_map):
1475
"""Get the (source, [keys]) list.
1477
The returned objects should be in the order defined by 'ordering',
1478
which can weave between different sources.
1479
:param ordering: Must be one of 'topological' or 'groupcompress'
1480
:return: List of [(source, [keys])] tuples, such that all keys are in
1481
the defined order, regardless of source.
1483
if ordering == 'topological':
1484
present_keys = tsort.topo_sort(parent_map)
1486
# ordering == 'groupcompress'
1487
# XXX: This only optimizes for the target ordering. We may need
1488
# to balance that with the time it takes to extract
1489
# ordering, by somehow grouping based on
1490
# locations[key][0:3]
1491
present_keys = sort_gc_optimal(parent_map)
1492
# Now group by source:
1494
current_source = None
1495
for key in present_keys:
1496
source = key_to_source_map.get(key, self)
1497
if source is not current_source:
1498
source_keys.append((source, []))
1499
current_source = source
1500
source_keys[-1][1].append(key)
1503
def _get_as_requested_source_keys(self, orig_keys, locations, unadded_keys,
1506
current_source = None
1507
for key in orig_keys:
1508
if key in locations or key in unadded_keys:
1510
elif key in key_to_source_map:
1511
source = key_to_source_map[key]
1514
if source is not current_source:
1515
source_keys.append((source, []))
1516
current_source = source
1517
source_keys[-1][1].append(key)
1520
def _get_io_ordered_source_keys(self, locations, unadded_keys,
1523
# This is the group the bytes are stored in, followed by the
1524
# location in the group
1525
return locations[key][0]
1526
present_keys = sorted(locations.iterkeys(), key=get_group)
1527
# We don't have an ordering for keys in the in-memory object, but
1528
# lets process the in-memory ones first.
1529
present_keys = list(unadded_keys) + present_keys
1530
# Now grab all of the ones from other sources
1531
source_keys = [(self, present_keys)]
1532
source_keys.extend(source_result)
1535
def _get_remaining_record_stream(self, keys, orig_keys, ordering,
1536
include_delta_closure):
1537
"""Get a stream of records for keys.
1539
:param keys: The keys to include.
1540
:param ordering: one of 'unordered', 'topological', 'groupcompress' or
1542
:param include_delta_closure: If True then the closure across any
1543
compression parents will be included (in the opaque data).
1544
:return: An iterator of ContentFactory objects, each of which is only
1545
valid until the iterator is advanced.
1548
locations = self._index.get_build_details(keys)
1549
unadded_keys = set(self._unadded_refs).intersection(keys)
1550
missing = keys.difference(locations)
1551
missing.difference_update(unadded_keys)
1552
(fallback_parent_map, key_to_source_map,
1553
source_result) = self._find_from_fallback(missing)
1554
if ordering in ('topological', 'groupcompress'):
1555
# would be better to not globally sort initially but instead
1556
# start with one key, recurse to its oldest parent, then grab
1557
# everything in the same group, etc.
1558
parent_map = dict((key, details[2]) for key, details in
1559
locations.iteritems())
1560
for key in unadded_keys:
1561
parent_map[key] = self._unadded_refs[key]
1562
parent_map.update(fallback_parent_map)
1563
source_keys = self._get_ordered_source_keys(ordering, parent_map,
1565
elif ordering == 'as-requested':
1566
source_keys = self._get_as_requested_source_keys(orig_keys,
1567
locations, unadded_keys, key_to_source_map)
1569
# We want to yield the keys in a semi-optimal (read-wise) ordering.
1570
# Otherwise we thrash the _group_cache and destroy performance
1571
source_keys = self._get_io_ordered_source_keys(locations,
1572
unadded_keys, source_result)
1574
yield AbsentContentFactory(key)
1575
# Batch up as many keys as we can until either:
1576
# - we encounter an unadded ref, or
1577
# - we run out of keys, or
1578
# - the total bytes to retrieve for this batch > BATCH_SIZE
1579
batcher = _BatchingBlockFetcher(self, locations)
1580
for source, keys in source_keys:
1583
if key in self._unadded_refs:
1584
# Flush batch, then yield unadded ref from
1586
for factory in batcher.yield_factories(full_flush=True):
1588
bytes, sha1 = self._compressor.extract(key)
1589
parents = self._unadded_refs[key]
1590
yield FulltextContentFactory(key, parents, sha1, bytes)
1592
if batcher.add_key(key) > BATCH_SIZE:
1593
# Ok, this batch is big enough. Yield some results.
1594
for factory in batcher.yield_factories():
1597
for factory in batcher.yield_factories(full_flush=True):
1599
for record in source.get_record_stream(keys, ordering,
1600
include_delta_closure):
1602
for factory in batcher.yield_factories(full_flush=True):
1605
def get_sha1s(self, keys):
1606
"""See VersionedFiles.get_sha1s()."""
1608
for record in self.get_record_stream(keys, 'unordered', True):
1609
if record.sha1 != None:
1610
result[record.key] = record.sha1
1612
if record.storage_kind != 'absent':
1613
result[record.key] = osutils.sha_string(
1614
record.get_bytes_as('fulltext'))
1617
def insert_record_stream(self, stream):
1618
"""Insert a record stream into this container.
1620
:param stream: A stream of records to insert.
1622
:seealso VersionedFiles.get_record_stream:
1624
# XXX: Setting random_id=True makes
1625
# test_insert_record_stream_existing_keys fail for groupcompress and
1626
# groupcompress-nograph, this needs to be revisited while addressing
1627
# 'bzr branch' performance issues.
1628
for _ in self._insert_record_stream(stream, random_id=False):
1631
def _insert_record_stream(self, stream, random_id=False, nostore_sha=None,
1633
"""Internal core to insert a record stream into this container.
1635
This helper function has a different interface than insert_record_stream
1636
to allow add_lines to be minimal, but still return the needed data.
1638
:param stream: A stream of records to insert.
1639
:param nostore_sha: If the sha1 of a given text matches nostore_sha,
1640
raise ExistingContent, rather than committing the new text.
1641
:param reuse_blocks: If the source is streaming from
1642
groupcompress-blocks, just insert the blocks as-is, rather than
1643
expanding the texts and inserting again.
1644
:return: An iterator over the sha1 of the inserted records.
1645
:seealso insert_record_stream:
1649
def get_adapter(adapter_key):
1651
return adapters[adapter_key]
1653
adapter_factory = adapter_registry.get(adapter_key)
1654
adapter = adapter_factory(self)
1655
adapters[adapter_key] = adapter
1657
# This will go up to fulltexts for gc to gc fetching, which isn't
1659
self._compressor = GroupCompressor()
1660
self._unadded_refs = {}
1663
bytes_len, chunks = self._compressor.flush().to_chunks()
1664
self._compressor = GroupCompressor()
1665
# Note: At this point we still have 1 copy of the fulltext (in
1666
# record and the var 'bytes'), and this generates 2 copies of
1667
# the compressed text (one for bytes, one in chunks)
1668
# TODO: Push 'chunks' down into the _access api, so that we don't
1669
# have to double compressed memory here
1670
# TODO: Figure out how to indicate that we would be happy to free
1671
# the fulltext content at this point. Note that sometimes we
1672
# will want it later (streaming CHK pages), but most of the
1673
# time we won't (everything else)
1674
bytes = ''.join(chunks)
1676
index, start, length = self._access.add_raw_records(
1677
[(None, len(bytes))], bytes)[0]
1679
for key, reads, refs in keys_to_add:
1680
nodes.append((key, "%d %d %s" % (start, length, reads), refs))
1681
self._index.add_records(nodes, random_id=random_id)
1682
self._unadded_refs = {}
1686
max_fulltext_len = 0
1687
max_fulltext_prefix = None
1688
insert_manager = None
1691
# XXX: TODO: remove this, it is just for safety checking for now
1692
inserted_keys = set()
1693
reuse_this_block = reuse_blocks
1694
for record in stream:
1695
# Raise an error when a record is missing.
1696
if record.storage_kind == 'absent':
1697
raise errors.RevisionNotPresent(record.key, self)
1699
if record.key in inserted_keys:
1700
trace.note('Insert claimed random_id=True,'
1701
' but then inserted %r two times', record.key)
1703
inserted_keys.add(record.key)
1705
# If the reuse_blocks flag is set, check to see if we can just
1706
# copy a groupcompress block as-is.
1707
# We only check on the first record (groupcompress-block) not
1708
# on all of the (groupcompress-block-ref) entries.
1709
# The reuse_this_block flag is then kept for as long as
1710
if record.storage_kind == 'groupcompress-block':
1711
# Check to see if we really want to re-use this block
1712
insert_manager = record._manager
1713
reuse_this_block = insert_manager.check_is_well_utilized()
1715
reuse_this_block = False
1716
if reuse_this_block:
1717
# We still want to reuse this block
1718
if record.storage_kind == 'groupcompress-block':
1719
# Insert the raw block into the target repo
1720
insert_manager = record._manager
1721
bytes = record._manager._block.to_bytes()
1722
_, start, length = self._access.add_raw_records(
1723
[(None, len(bytes))], bytes)[0]
1726
block_length = length
1727
if record.storage_kind in ('groupcompress-block',
1728
'groupcompress-block-ref'):
1729
if insert_manager is None:
1730
raise AssertionError('No insert_manager set')
1731
if insert_manager is not record._manager:
1732
raise AssertionError('insert_manager does not match'
1733
' the current record, we cannot be positive'
1734
' that the appropriate content was inserted.'
1736
value = "%d %d %d %d" % (block_start, block_length,
1737
record._start, record._end)
1738
nodes = [(record.key, value, (record.parents,))]
1739
# TODO: Consider buffering up many nodes to be added, not
1740
# sure how much overhead this has, but we're seeing
1741
# ~23s / 120s in add_records calls
1742
self._index.add_records(nodes, random_id=random_id)
1745
bytes = record.get_bytes_as('fulltext')
1746
except errors.UnavailableRepresentation:
1747
adapter_key = record.storage_kind, 'fulltext'
1748
adapter = get_adapter(adapter_key)
1749
bytes = adapter.get_bytes(record)
1750
if len(record.key) > 1:
1751
prefix = record.key[0]
1752
soft = (prefix == last_prefix)
1756
if max_fulltext_len < len(bytes):
1757
max_fulltext_len = len(bytes)
1758
max_fulltext_prefix = prefix
1759
(found_sha1, start_point, end_point,
1760
type) = self._compressor.compress(record.key,
1761
bytes, record.sha1, soft=soft,
1762
nostore_sha=nostore_sha)
1763
# delta_ratio = float(len(bytes)) / (end_point - start_point)
1764
# Check if we want to continue to include that text
1765
if (prefix == max_fulltext_prefix
1766
and end_point < 2 * max_fulltext_len):
1767
# As long as we are on the same file_id, we will fill at least
1768
# 2 * max_fulltext_len
1769
start_new_block = False
1770
elif end_point > 4*1024*1024:
1771
start_new_block = True
1772
elif (prefix is not None and prefix != last_prefix
1773
and end_point > 2*1024*1024):
1774
start_new_block = True
1776
start_new_block = False
1777
last_prefix = prefix
1779
self._compressor.pop_last()
1781
max_fulltext_len = len(bytes)
1782
(found_sha1, start_point, end_point,
1783
type) = self._compressor.compress(record.key, bytes,
1785
if record.key[-1] is None:
1786
key = record.key[:-1] + ('sha1:' + found_sha1,)
1789
self._unadded_refs[key] = record.parents
1791
as_st = static_tuple.StaticTuple.from_sequence
1792
if record.parents is not None:
1793
parents = as_st([as_st(p) for p in record.parents])
1796
refs = static_tuple.StaticTuple(parents)
1797
keys_to_add.append((key, '%d %d' % (start_point, end_point), refs))
1798
if len(keys_to_add):
1800
self._compressor = None
1802
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1803
"""Iterate over the lines in the versioned files from keys.
1805
This may return lines from other keys. Each item the returned
1806
iterator yields is a tuple of a line and a text version that that line
1807
is present in (not introduced in).
1809
Ordering of results is in whatever order is most suitable for the
1810
underlying storage format.
1812
If a progress bar is supplied, it may be used to indicate progress.
1813
The caller is responsible for cleaning up progress bars (because this
1817
* Lines are normalised by the underlying store: they will all have \n
1819
* Lines are returned in arbitrary order.
1821
:return: An iterator over (line, key).
1825
# we don't care about inclusions, the caller cares.
1826
# but we need to setup a list of records to visit.
1827
# we need key, position, length
1828
for key_idx, record in enumerate(self.get_record_stream(keys,
1829
'unordered', True)):
1830
# XXX: todo - optimise to use less than full texts.
1833
pb.update('Walking content', key_idx, total)
1834
if record.storage_kind == 'absent':
1835
raise errors.RevisionNotPresent(key, self)
1836
lines = osutils.split_lines(record.get_bytes_as('fulltext'))
1840
pb.update('Walking content', total, total)
1843
"""See VersionedFiles.keys."""
1844
if 'evil' in debug.debug_flags:
1845
trace.mutter_callsite(2, "keys scales with size of history")
1846
sources = [self._index] + self._immediate_fallback_vfs
1848
for source in sources:
1849
result.update(source.keys())
1853
class _GCBuildDetails(object):
1854
"""A blob of data about the build details.
1856
This stores the minimal data, which then allows compatibility with the old
1857
api, without taking as much memory.
1860
__slots__ = ('_index', '_group_start', '_group_end', '_basis_end',
1861
'_delta_end', '_parents')
1864
compression_parent = None
1866
def __init__(self, parents, position_info):
1867
self._parents = parents
1868
(self._index, self._group_start, self._group_end, self._basis_end,
1869
self._delta_end) = position_info
1872
return '%s(%s, %s)' % (self.__class__.__name__,
1873
self.index_memo, self._parents)
1876
def index_memo(self):
1877
return (self._index, self._group_start, self._group_end,
1878
self._basis_end, self._delta_end)
1881
def record_details(self):
1882
return static_tuple.StaticTuple(self.method, None)
1884
def __getitem__(self, offset):
1885
"""Compatibility thunk to act like a tuple."""
1887
return self.index_memo
1889
return self.compression_parent # Always None
1891
return self._parents
1893
return self.record_details
1895
raise IndexError('offset out of range')
1901
class _GCGraphIndex(object):
1902
"""Mapper from GroupCompressVersionedFiles needs into GraphIndex storage."""
1904
def __init__(self, graph_index, is_locked, parents=True,
1905
add_callback=None, track_external_parent_refs=False,
1906
inconsistency_fatal=True, track_new_keys=False):
1907
"""Construct a _GCGraphIndex on a graph_index.
1909
:param graph_index: An implementation of bzrlib.index.GraphIndex.
1910
:param is_locked: A callback, returns True if the index is locked and
1912
:param parents: If True, record knits parents, if not do not record
1914
:param add_callback: If not None, allow additions to the index and call
1915
this callback with a list of added GraphIndex nodes:
1916
[(node, value, node_refs), ...]
1917
:param track_external_parent_refs: As keys are added, keep track of the
1918
keys they reference, so that we can query get_missing_parents(),
1920
:param inconsistency_fatal: When asked to add records that are already
1921
present, and the details are inconsistent with the existing
1922
record, raise an exception instead of warning (and skipping the
1925
self._add_callback = add_callback
1926
self._graph_index = graph_index
1927
self._parents = parents
1928
self.has_graph = parents
1929
self._is_locked = is_locked
1930
self._inconsistency_fatal = inconsistency_fatal
1931
# GroupCompress records tend to have the same 'group' start + offset
1932
# repeated over and over, this creates a surplus of ints
1933
self._int_cache = {}
1934
if track_external_parent_refs:
1935
self._key_dependencies = _KeyRefs(
1936
track_new_keys=track_new_keys)
1938
self._key_dependencies = None
1940
def add_records(self, records, random_id=False):
1941
"""Add multiple records to the index.
1943
This function does not insert data into the Immutable GraphIndex
1944
backing the KnitGraphIndex, instead it prepares data for insertion by
1945
the caller and checks that it is safe to insert then calls
1946
self._add_callback with the prepared GraphIndex nodes.
1948
:param records: a list of tuples:
1949
(key, options, access_memo, parents).
1950
:param random_id: If True the ids being added were randomly generated
1951
and no check for existence will be performed.
1953
if not self._add_callback:
1954
raise errors.ReadOnlyError(self)
1955
# we hope there are no repositories with inconsistent parentage
1960
for (key, value, refs) in records:
1961
if not self._parents:
1965
raise errors.KnitCorrupt(self,
1966
"attempt to add node with parents "
1967
"in parentless index.")
1970
keys[key] = (value, refs)
1973
present_nodes = self._get_entries(keys)
1974
for (index, key, value, node_refs) in present_nodes:
1975
# Sometimes these are passed as a list rather than a tuple
1976
node_refs = static_tuple.as_tuples(node_refs)
1977
passed = static_tuple.as_tuples(keys[key])
1978
if node_refs != passed[1]:
1979
details = '%s %s %s' % (key, (value, node_refs), passed)
1980
if self._inconsistency_fatal:
1981
raise errors.KnitCorrupt(self, "inconsistent details"
1982
" in add_records: %s" %
1985
trace.warning("inconsistent details in skipped"
1986
" record: %s", details)
1992
for key, (value, node_refs) in keys.iteritems():
1993
result.append((key, value, node_refs))
1995
for key, (value, node_refs) in keys.iteritems():
1996
result.append((key, value))
1998
key_dependencies = self._key_dependencies
1999
if key_dependencies is not None:
2001
for key, value, refs in records:
2003
key_dependencies.add_references(key, parents)
2005
for key, value, refs in records:
2006
new_keys.add_key(key)
2007
self._add_callback(records)
2009
def _check_read(self):
2010
"""Raise an exception if reads are not permitted."""
2011
if not self._is_locked():
2012
raise errors.ObjectNotLocked(self)
2014
def _check_write_ok(self):
2015
"""Raise an exception if writes are not permitted."""
2016
if not self._is_locked():
2017
raise errors.ObjectNotLocked(self)
2019
def _get_entries(self, keys, check_present=False):
2020
"""Get the entries for keys.
2022
Note: Callers are responsible for checking that the index is locked
2023
before calling this method.
2025
:param keys: An iterable of index key tuples.
2030
for node in self._graph_index.iter_entries(keys):
2032
found_keys.add(node[1])
2034
# adapt parentless index to the rest of the code.
2035
for node in self._graph_index.iter_entries(keys):
2036
yield node[0], node[1], node[2], ()
2037
found_keys.add(node[1])
2039
missing_keys = keys.difference(found_keys)
2041
raise errors.RevisionNotPresent(missing_keys.pop(), self)
2043
def find_ancestry(self, keys):
2044
"""See CombinedGraphIndex.find_ancestry"""
2045
return self._graph_index.find_ancestry(keys, 0)
2047
def get_parent_map(self, keys):
2048
"""Get a map of the parents of keys.
2050
:param keys: The keys to look up parents for.
2051
:return: A mapping from keys to parents. Absent keys are absent from
2055
nodes = self._get_entries(keys)
2059
result[node[1]] = node[3][0]
2062
result[node[1]] = None
2065
def get_missing_parents(self):
2066
"""Return the keys of missing parents."""
2067
# Copied from _KnitGraphIndex.get_missing_parents
2068
# We may have false positives, so filter those out.
2069
self._key_dependencies.satisfy_refs_for_keys(
2070
self.get_parent_map(self._key_dependencies.get_unsatisfied_refs()))
2071
return frozenset(self._key_dependencies.get_unsatisfied_refs())
2073
def get_build_details(self, keys):
2074
"""Get the various build details for keys.
2076
Ghosts are omitted from the result.
2078
:param keys: An iterable of keys.
2079
:return: A dict of key:
2080
(index_memo, compression_parent, parents, record_details).
2082
opaque structure to pass to read_records to extract the raw
2085
Content that this record is built upon, may be None
2087
Logical parents of this node
2089
extra information about the content which needs to be passed to
2090
Factory.parse_record
2094
entries = self._get_entries(keys)
2095
for entry in entries:
2097
if not self._parents:
2100
parents = entry[3][0]
2101
details = _GCBuildDetails(parents, self._node_to_position(entry))
2102
result[key] = details
2106
"""Get all the keys in the collection.
2108
The keys are not ordered.
2111
return [node[1] for node in self._graph_index.iter_all_entries()]
2113
def _node_to_position(self, node):
2114
"""Convert an index value to position details."""
2115
bits = node[2].split(' ')
2116
# It would be nice not to read the entire gzip.
2117
# start and stop are put into _int_cache because they are very common.
2118
# They define the 'group' that an entry is in, and many groups can have
2119
# thousands of objects.
2120
# Branching Launchpad, for example, saves ~600k integers, at 12 bytes
2121
# each, or about 7MB. Note that it might be even more when you consider
2122
# how PyInt is allocated in separate slabs. And you can't return a slab
2123
# to the OS if even 1 int on it is in use. Note though that Python uses
2124
# a LIFO when re-using PyInt slots, which might cause more
2126
start = int(bits[0])
2127
start = self._int_cache.setdefault(start, start)
2129
stop = self._int_cache.setdefault(stop, stop)
2130
basis_end = int(bits[2])
2131
delta_end = int(bits[3])
2132
# We can't use StaticTuple here, because node[0] is a BTreeGraphIndex
2134
return (node[0], start, stop, basis_end, delta_end)
2136
def scan_unvalidated_index(self, graph_index):
2137
"""Inform this _GCGraphIndex that there is an unvalidated index.
2139
This allows this _GCGraphIndex to keep track of any missing
2140
compression parents we may want to have filled in to make those
2141
indices valid. It also allows _GCGraphIndex to track any new keys.
2143
:param graph_index: A GraphIndex
2145
key_dependencies = self._key_dependencies
2146
if key_dependencies is None:
2148
for node in graph_index.iter_all_entries():
2149
# Add parent refs from graph_index (and discard parent refs
2150
# that the graph_index has).
2151
key_dependencies.add_references(node[1], node[3][0])
2154
from bzrlib._groupcompress_py import (
2156
apply_delta_to_source,
2159
decode_copy_instruction,
2163
from bzrlib._groupcompress_pyx import (
2165
apply_delta_to_source,
2170
GroupCompressor = PyrexGroupCompressor
2171
except ImportError, e:
2172
osutils.failed_to_load_extension(e)
2173
GroupCompressor = PythonGroupCompressor
added
removed
bzrlib/groupcompress.py
