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."""
19
from itertools import izip
20
from cStringIO import StringIO
39
from bzrlib.graph import Graph
40
from bzrlib.knit import _DirectPackAccess
41
from bzrlib.btree_index import BTreeBuilder
42
from bzrlib.lru_cache import LRUSizeCache
43
from bzrlib.tsort import topo_sort
44
from bzrlib.versionedfile import (
47
ChunkedContentFactory,
48
FulltextContentFactory,
52
_USE_LZMA = False and (pylzma is not None)
54
# osutils.sha_string('')
55
_null_sha1 = 'da39a3ee5e6b4b0d3255bfef95601890afd80709'
58
def sort_gc_optimal(parent_map):
59
"""Sort and group the keys in parent_map into groupcompress order.
61
groupcompress is defined (currently) as reverse-topological order, grouped
64
:return: A sorted-list of keys
66
# groupcompress ordering is approximately reverse topological,
67
# properly grouped by file-id.
69
for item in parent_map.iteritems():
71
if isinstance(key, str) or len(key) == 1:
76
per_prefix_map[prefix].append(item)
78
per_prefix_map[prefix] = [item]
81
for prefix in sorted(per_prefix_map):
82
present_keys.extend(reversed(topo_sort(per_prefix_map[prefix])))
86
# The max zlib window size is 32kB, so if we set 'max_size' output of the
87
# decompressor to the requested bytes + 32kB, then we should guarantee
88
# num_bytes coming out.
89
_ZLIB_DECOMP_WINDOW = 32*1024
91
class GroupCompressBlock(object):
92
"""An object which maintains the internal structure of the compressed data.
94
This tracks the meta info (start of text, length, type, etc.)
97
# Group Compress Block v1 Zlib
98
GCB_HEADER = 'gcb1z\n'
99
# Group Compress Block v1 Lzma
100
GCB_LZ_HEADER = 'gcb1l\n'
101
GCB_KNOWN_HEADERS = (GCB_HEADER, GCB_LZ_HEADER)
104
# map by key? or just order in file?
105
self._compressor_name = None
106
self._z_content = None
107
self._z_content_decompressor = None
108
self._z_content_length = None
109
self._content_length = None
113
# This is the maximum number of bytes this object will reference if
114
# everything is decompressed. However, if we decompress less than
115
# everything... (this would cause some problems for LRUSizeCache)
116
return self._content_length + self._z_content_length
118
def _ensure_content(self, num_bytes=None):
119
"""Make sure that content has been expanded enough.
121
:param num_bytes: Ensure that we have extracted at least num_bytes of
122
content. If None, consume everything
124
# TODO: If we re-use the same content block at different times during
125
# get_record_stream(), it is possible that the first pass will
126
# get inserted, triggering an extract/_ensure_content() which
127
# will get rid of _z_content. And then the next use of the block
128
# will try to access _z_content (to send it over the wire), and
129
# fail because it is already extracted. Consider never releasing
130
# _z_content because of this.
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._z_content is None:
141
raise AssertionError('No content to decompress')
142
if self._z_content == '':
144
elif self._compressor_name == 'lzma':
145
# We don't do partial lzma decomp yet
146
self._content = pylzma.decompress(self._z_content)
147
elif self._compressor_name == 'zlib':
148
# Start a zlib decompressor
149
if num_bytes is None:
150
self._content = zlib.decompress(self._z_content)
152
self._z_content_decompressor = zlib.decompressobj()
153
# Seed the decompressor with the uncompressed bytes, so
154
# that the rest of the code is simplified
155
self._content = self._z_content_decompressor.decompress(
156
self._z_content, num_bytes + _ZLIB_DECOMP_WINDOW)
158
raise AssertionError('Unknown compressor: %r'
159
% self._compressor_name)
160
# Any bytes remaining to be decompressed will be in the decompressors
163
# Do we have enough bytes already?
164
if num_bytes is not None and len(self._content) >= num_bytes:
166
if num_bytes is None and self._z_content_decompressor is None:
167
# We must have already decompressed everything
169
# If we got this far, and don't have a decompressor, something is wrong
170
if self._z_content_decompressor is None:
171
raise AssertionError(
172
'No decompressor to decompress %d bytes' % num_bytes)
173
remaining_decomp = self._z_content_decompressor.unconsumed_tail
174
if num_bytes is None:
176
# We don't know how much is left, but we'll decompress it all
177
self._content += self._z_content_decompressor.decompress(
179
# Note: There's what I consider a bug in zlib.decompressobj
180
# If you pass back in the entire unconsumed_tail, only
181
# this time you don't pass a max-size, it doesn't
182
# change the unconsumed_tail back to None/''.
183
# However, we know we are done with the whole stream
184
self._z_content_decompressor = None
185
# XXX: Why is this the only place in this routine we set this?
186
self._content_length = len(self._content)
188
if not remaining_decomp:
189
raise AssertionError('Nothing left to decompress')
190
needed_bytes = num_bytes - len(self._content)
191
# We always set max_size to 32kB over the minimum needed, so that
192
# zlib will give us as much as we really want.
193
# TODO: If this isn't good enough, we could make a loop here,
194
# that keeps expanding the request until we get enough
195
self._content += self._z_content_decompressor.decompress(
196
remaining_decomp, needed_bytes + _ZLIB_DECOMP_WINDOW)
197
if len(self._content) < num_bytes:
198
raise AssertionError('%d bytes wanted, only %d available'
199
% (num_bytes, len(self._content)))
200
if not self._z_content_decompressor.unconsumed_tail:
201
# The stream is finished
202
self._z_content_decompressor = None
204
def _parse_bytes(self, bytes, pos):
205
"""Read the various lengths from the header.
207
This also populates the various 'compressed' buffers.
209
:return: The position in bytes just after the last newline
211
# At present, we have 2 integers for the compressed and uncompressed
212
# content. In base10 (ascii) 14 bytes can represent > 1TB, so to avoid
213
# checking too far, cap the search to 14 bytes.
214
pos2 = bytes.index('\n', pos, pos + 14)
215
self._z_content_length = int(bytes[pos:pos2])
217
pos2 = bytes.index('\n', pos, pos + 14)
218
self._content_length = int(bytes[pos:pos2])
220
if len(bytes) != (pos + self._z_content_length):
221
# XXX: Define some GCCorrupt error ?
222
raise AssertionError('Invalid bytes: (%d) != %d + %d' %
223
(len(bytes), pos, self._z_content_length))
224
self._z_content = bytes[pos:]
227
def from_bytes(cls, bytes):
229
if bytes[:6] not in cls.GCB_KNOWN_HEADERS:
230
raise ValueError('bytes did not start with any of %r'
231
% (cls.GCB_KNOWN_HEADERS,))
232
# XXX: why not testing the whole header ?
234
out._compressor_name = 'zlib'
235
elif bytes[4] == 'l':
236
out._compressor_name = 'lzma'
238
raise ValueError('unknown compressor: %r' % (bytes,))
239
out._parse_bytes(bytes, 6)
242
def extract(self, key, start, end, sha1=None):
243
"""Extract the text for a specific key.
245
:param key: The label used for this content
246
:param sha1: TODO (should we validate only when sha1 is supplied?)
247
:return: The bytes for the content
249
if start == end == 0:
251
self._ensure_content(end)
252
# The bytes are 'f' or 'd' for the type, then a variable-length
253
# base128 integer for the content size, then the actual content
254
# We know that the variable-length integer won't be longer than 5
255
# bytes (it takes 5 bytes to encode 2^32)
256
c = self._content[start]
261
raise ValueError('Unknown content control code: %s'
264
content_len, len_len = decode_base128_int(
265
self._content[start + 1:start + 6])
266
content_start = start + 1 + len_len
267
if end != content_start + content_len:
268
raise ValueError('end != len according to field header'
269
' %s != %s' % (end, content_start + content_len))
271
bytes = self._content[content_start:end]
273
bytes = apply_delta_to_source(self._content, content_start, end)
276
def set_content(self, content):
277
"""Set the content of this block."""
278
self._content_length = len(content)
279
self._content = content
280
self._z_content = None
283
"""Encode the information into a byte stream."""
284
compress = zlib.compress
286
compress = pylzma.compress
287
if self._z_content is None:
288
if self._content is None:
289
raise AssertionError('Nothing to compress')
290
self._z_content = compress(self._content)
291
self._z_content_length = len(self._z_content)
293
header = self.GCB_LZ_HEADER
295
header = self.GCB_HEADER
297
'%d\n%d\n' % (self._z_content_length, self._content_length),
300
return ''.join(chunks)
303
class _LazyGroupCompressFactory(object):
304
"""Yield content from a GroupCompressBlock on demand."""
306
def __init__(self, key, parents, manager, start, end, first):
307
"""Create a _LazyGroupCompressFactory
309
:param key: The key of just this record
310
:param parents: The parents of this key (possibly None)
311
:param gc_block: A GroupCompressBlock object
312
:param start: Offset of the first byte for this record in the
314
:param end: Offset of the byte just after the end of this record
315
(ie, bytes = content[start:end])
316
:param first: Is this the first Factory for the given block?
319
self.parents = parents
321
# Note: This attribute coupled with Manager._factories creates a
322
# reference cycle. Perhaps we would rather use a weakref(), or
323
# find an appropriate time to release the ref. After the first
324
# get_bytes_as call? After Manager.get_record_stream() returns
326
self._manager = manager
328
self.storage_kind = 'groupcompress-block'
330
self.storage_kind = 'groupcompress-block-ref'
336
return '%s(%s, first=%s)' % (self.__class__.__name__,
337
self.key, self._first)
339
def get_bytes_as(self, storage_kind):
340
if storage_kind == self.storage_kind:
342
# wire bytes, something...
343
return self._manager._wire_bytes()
346
if storage_kind in ('fulltext', 'chunked'):
347
if self._bytes is None:
348
# Grab and cache the raw bytes for this entry
349
# and break the ref-cycle with _manager since we don't need it
351
self._manager._prepare_for_extract()
352
block = self._manager._block
353
self._bytes = block.extract(self.key, self._start, self._end)
354
# There are code paths that first extract as fulltext, and then
355
# extract as storage_kind (smart fetch). So we don't break the
356
# refcycle here, but instead in manager.get_record_stream()
357
# self._manager = None
358
if storage_kind == 'fulltext':
362
raise errors.UnavailableRepresentation(self.key, storage_kind,
366
class _LazyGroupContentManager(object):
367
"""This manages a group of _LazyGroupCompressFactory objects."""
369
def __init__(self, block):
371
# We need to preserve the ordering
375
def add_factory(self, key, parents, start, end):
376
if not self._factories:
380
# Note that this creates a reference cycle....
381
factory = _LazyGroupCompressFactory(key, parents, self,
382
start, end, first=first)
383
# max() works here, but as a function call, doing a compare seems to be
384
# significantly faster, timeit says 250ms for max() and 100ms for the
386
if end > self._last_byte:
387
self._last_byte = end
388
self._factories.append(factory)
390
def get_record_stream(self):
391
"""Get a record for all keys added so far."""
392
for factory in self._factories:
394
# Break the ref-cycle
395
factory._bytes = None
396
factory._manager = None
397
# TODO: Consider setting self._factories = None after the above loop,
398
# as it will break the reference cycle
400
def _trim_block(self, last_byte):
401
"""Create a new GroupCompressBlock, with just some of the content."""
402
# None of the factories need to be adjusted, because the content is
403
# located in an identical place. Just that some of the unreferenced
404
# trailing bytes are stripped
405
trace.mutter('stripping trailing bytes from groupcompress block'
406
' %d => %d', self._block._content_length, last_byte)
407
new_block = GroupCompressBlock()
408
self._block._ensure_content(last_byte)
409
new_block.set_content(self._block._content[:last_byte])
410
self._block = new_block
412
def _rebuild_block(self):
413
"""Create a new GroupCompressBlock with only the referenced texts."""
414
compressor = GroupCompressor()
416
old_length = self._block._content_length
418
for factory in self._factories:
419
bytes = factory.get_bytes_as('fulltext')
420
(found_sha1, start_point, end_point,
421
type) = compressor.compress(factory.key, bytes, factory.sha1)
422
# Now update this factory with the new offsets, etc
423
factory.sha1 = found_sha1
424
factory._start = start_point
425
factory._end = end_point
426
self._last_byte = end_point
427
new_block = compressor.flush()
428
# TODO: Should we check that new_block really *is* smaller than the old
429
# block? It seems hard to come up with a method that it would
430
# expand, since we do full compression again. Perhaps based on a
431
# request that ends up poorly ordered?
432
delta = time.time() - tstart
433
self._block = new_block
434
trace.mutter('creating new compressed block on-the-fly in %.3fs'
435
' %d bytes => %d bytes', delta, old_length,
436
self._block._content_length)
438
def _prepare_for_extract(self):
439
"""A _LazyGroupCompressFactory is about to extract to fulltext."""
440
# We expect that if one child is going to fulltext, all will be. This
441
# helps prevent all of them from extracting a small amount at a time.
442
# Which in itself isn't terribly expensive, but resizing 2MB 32kB at a
443
# time (self._block._content) is a little expensive.
444
self._block._ensure_content(self._last_byte)
446
def _check_rebuild_block(self):
447
"""Check to see if our block should be repacked."""
450
for factory in self._factories:
451
total_bytes_used += factory._end - factory._start
452
last_byte_used = max(last_byte_used, factory._end)
453
# If we are using most of the bytes from the block, we have nothing
454
# else to check (currently more that 1/2)
455
if total_bytes_used * 2 >= self._block._content_length:
457
# Can we just strip off the trailing bytes? If we are going to be
458
# transmitting more than 50% of the front of the content, go ahead
459
if total_bytes_used * 2 > last_byte_used:
460
self._trim_block(last_byte_used)
463
# We are using a small amount of the data, and it isn't just packed
464
# nicely at the front, so rebuild the content.
465
# Note: This would be *nicer* as a strip-data-from-group, rather than
466
# building it up again from scratch
467
# It might be reasonable to consider the fulltext sizes for
468
# different bits when deciding this, too. As you may have a small
469
# fulltext, and a trivial delta, and you are just trading around
470
# for another fulltext. If we do a simple 'prune' you may end up
471
# expanding many deltas into fulltexts, as well.
472
# If we build a cheap enough 'strip', then we could try a strip,
473
# if that expands the content, we then rebuild.
474
self._rebuild_block()
476
def _wire_bytes(self):
477
"""Return a byte stream suitable for transmitting over the wire."""
478
self._check_rebuild_block()
479
# The outer block starts with:
480
# 'groupcompress-block\n'
481
# <length of compressed key info>\n
482
# <length of uncompressed info>\n
483
# <length of gc block>\n
486
lines = ['groupcompress-block\n']
487
# The minimal info we need is the key, the start offset, and the
488
# parents. The length and type are encoded in the record itself.
489
# However, passing in the other bits makes it easier. The list of
490
# keys, and the start offset, the length
492
# 1 line with parents, '' for ()
493
# 1 line for start offset
494
# 1 line for end byte
496
for factory in self._factories:
497
key_bytes = '\x00'.join(factory.key)
498
parents = factory.parents
500
parent_bytes = 'None:'
502
parent_bytes = '\t'.join('\x00'.join(key) for key in parents)
503
record_header = '%s\n%s\n%d\n%d\n' % (
504
key_bytes, parent_bytes, factory._start, factory._end)
505
header_lines.append(record_header)
506
# TODO: Can we break the refcycle at this point and set
507
# factory._manager = None?
508
header_bytes = ''.join(header_lines)
510
header_bytes_len = len(header_bytes)
511
z_header_bytes = zlib.compress(header_bytes)
513
z_header_bytes_len = len(z_header_bytes)
514
block_bytes = self._block.to_bytes()
515
lines.append('%d\n%d\n%d\n' % (z_header_bytes_len, header_bytes_len,
517
lines.append(z_header_bytes)
518
lines.append(block_bytes)
519
del z_header_bytes, block_bytes
520
return ''.join(lines)
523
def from_bytes(cls, bytes):
524
# TODO: This does extra string copying, probably better to do it a
526
(storage_kind, z_header_len, header_len,
527
block_len, rest) = bytes.split('\n', 4)
529
if storage_kind != 'groupcompress-block':
530
raise ValueError('Unknown storage kind: %s' % (storage_kind,))
531
z_header_len = int(z_header_len)
532
if len(rest) < z_header_len:
533
raise ValueError('Compressed header len shorter than all bytes')
534
z_header = rest[:z_header_len]
535
header_len = int(header_len)
536
header = zlib.decompress(z_header)
537
if len(header) != header_len:
538
raise ValueError('invalid length for decompressed bytes')
540
block_len = int(block_len)
541
if len(rest) != z_header_len + block_len:
542
raise ValueError('Invalid length for block')
543
block_bytes = rest[z_header_len:]
545
# So now we have a valid GCB, we just need to parse the factories that
547
header_lines = header.split('\n')
549
last = header_lines.pop()
551
raise ValueError('header lines did not end with a trailing'
553
if len(header_lines) % 4 != 0:
554
raise ValueError('The header was not an even multiple of 4 lines')
555
block = GroupCompressBlock.from_bytes(block_bytes)
558
for start in xrange(0, len(header_lines), 4):
560
key = tuple(header_lines[start].split('\x00'))
561
parents_line = header_lines[start+1]
562
if parents_line == 'None:':
565
parents = tuple([tuple(segment.split('\x00'))
566
for segment in parents_line.split('\t')
568
start_offset = int(header_lines[start+2])
569
end_offset = int(header_lines[start+3])
570
result.add_factory(key, parents, start_offset, end_offset)
574
def network_block_to_records(storage_kind, bytes, line_end):
575
if storage_kind != 'groupcompress-block':
576
raise ValueError('Unknown storage kind: %s' % (storage_kind,))
577
manager = _LazyGroupContentManager.from_bytes(bytes)
578
return manager.get_record_stream()
581
class _CommonGroupCompressor(object):
584
"""Create a GroupCompressor."""
589
self.labels_deltas = {}
590
self._delta_index = None # Set by the children
591
self._block = GroupCompressBlock()
593
def compress(self, key, bytes, expected_sha, nostore_sha=None, soft=False):
594
"""Compress lines with label key.
596
:param key: A key tuple. It is stored in the output
597
for identification of the text during decompression. If the last
598
element is 'None' it is replaced with the sha1 of the text -
600
:param bytes: The bytes to be compressed
601
:param expected_sha: If non-None, the sha the lines are believed to
602
have. During compression the sha is calculated; a mismatch will
604
:param nostore_sha: If the computed sha1 sum matches, we will raise
605
ExistingContent rather than adding the text.
606
:param soft: Do a 'soft' compression. This means that we require larger
607
ranges to match to be considered for a copy command.
609
:return: The sha1 of lines, the start and end offsets in the delta, and
610
the type ('fulltext' or 'delta').
612
:seealso VersionedFiles.add_lines:
614
if not bytes: # empty, like a dir entry, etc
615
if nostore_sha == _null_sha1:
616
raise errors.ExistingContent()
617
return _null_sha1, 0, 0, 'fulltext'
618
# we assume someone knew what they were doing when they passed it in
619
if expected_sha is not None:
622
sha1 = osutils.sha_string(bytes)
623
if nostore_sha is not None:
624
if sha1 == nostore_sha:
625
raise errors.ExistingContent()
627
key = key[:-1] + ('sha1:' + sha1,)
629
start, end, type = self._compress(key, bytes, len(bytes) / 2, soft)
630
return sha1, start, end, type
632
def _compress(self, key, bytes, max_delta_size, soft=False):
633
"""Compress lines with label key.
635
:param key: A key tuple. It is stored in the output for identification
636
of the text during decompression.
638
:param bytes: The bytes to be compressed
640
:param max_delta_size: The size above which we issue a fulltext instead
643
:param soft: Do a 'soft' compression. This means that we require larger
644
ranges to match to be considered for a copy command.
646
:return: The sha1 of lines, the start and end offsets in the delta, and
647
the type ('fulltext' or 'delta').
649
raise NotImplementedError(self._compress)
651
def extract(self, key):
652
"""Extract a key previously added to the compressor.
654
:param key: The key to extract.
655
:return: An iterable over bytes and the sha1.
657
(start_byte, start_chunk, end_byte, end_chunk) = self.labels_deltas[key]
658
delta_chunks = self.chunks[start_chunk:end_chunk]
659
stored_bytes = ''.join(delta_chunks)
660
if stored_bytes[0] == 'f':
661
fulltext_len, offset = decode_base128_int(stored_bytes[1:10])
662
data_len = fulltext_len + 1 + offset
663
if data_len != len(stored_bytes):
664
raise ValueError('Index claimed fulltext len, but stored bytes'
666
% (len(stored_bytes), data_len))
667
bytes = stored_bytes[offset + 1:]
669
# XXX: This is inefficient at best
670
source = ''.join(self.chunks[:start_chunk])
671
if stored_bytes[0] != 'd':
672
raise ValueError('Unknown content kind, bytes claim %s'
673
% (stored_bytes[0],))
674
delta_len, offset = decode_base128_int(stored_bytes[1:10])
675
data_len = delta_len + 1 + offset
676
if data_len != len(stored_bytes):
677
raise ValueError('Index claimed delta len, but stored bytes'
679
% (len(stored_bytes), data_len))
680
bytes = apply_delta(source, stored_bytes[offset + 1:])
681
bytes_sha1 = osutils.sha_string(bytes)
682
return bytes, bytes_sha1
685
"""Finish this group, creating a formatted stream.
687
After calling this, the compressor should no longer be used
689
content = ''.join(self.chunks)
691
self._delta_index = None
692
self._block.set_content(content)
696
"""Call this if you want to 'revoke' the last compression.
698
After this, the data structures will be rolled back, but you cannot do
701
self._delta_index = None
702
del self.chunks[self._last[0]:]
703
self.endpoint = self._last[1]
707
"""Return the overall compression ratio."""
708
return float(self.input_bytes) / float(self.endpoint)
711
class PythonGroupCompressor(_CommonGroupCompressor):
714
"""Create a GroupCompressor.
716
Used only if the pyrex version is not available.
718
super(PythonGroupCompressor, self).__init__()
719
self._delta_index = LinesDeltaIndex([])
720
# The actual content is managed by LinesDeltaIndex
721
self.chunks = self._delta_index.lines
723
def _compress(self, key, bytes, max_delta_size, soft=False):
724
"""see _CommonGroupCompressor._compress"""
725
input_len = len(bytes)
726
new_lines = osutils.split_lines(bytes)
727
out_lines, index_lines = self._delta_index.make_delta(
728
new_lines, bytes_length=input_len, soft=soft)
729
delta_length = sum(map(len, out_lines))
730
if delta_length > max_delta_size:
731
# The delta is longer than the fulltext, insert a fulltext
733
out_lines = ['f', encode_base128_int(input_len)]
734
out_lines.extend(new_lines)
735
index_lines = [False, False]
736
index_lines.extend([True] * len(new_lines))
738
# this is a worthy delta, output it
741
# Update the delta_length to include those two encoded integers
742
out_lines[1] = encode_base128_int(delta_length)
744
start = self.endpoint
745
chunk_start = len(self.chunks)
746
self._last = (chunk_start, self.endpoint)
747
self._delta_index.extend_lines(out_lines, index_lines)
748
self.endpoint = self._delta_index.endpoint
749
self.input_bytes += input_len
750
chunk_end = len(self.chunks)
751
self.labels_deltas[key] = (start, chunk_start,
752
self.endpoint, chunk_end)
753
return start, self.endpoint, type
756
class PyrexGroupCompressor(_CommonGroupCompressor):
757
"""Produce a serialised group of compressed texts.
759
It contains code very similar to SequenceMatcher because of having a similar
760
task. However some key differences apply:
761
- there is no junk, we want a minimal edit not a human readable diff.
762
- we don't filter very common lines (because we don't know where a good
763
range will start, and after the first text we want to be emitting minmal
765
- we chain the left side, not the right side
766
- we incrementally update the adjacency matrix as new lines are provided.
767
- we look for matches in all of the left side, so the routine which does
768
the analagous task of find_longest_match does not need to filter on the
773
super(PyrexGroupCompressor, self).__init__()
774
self._delta_index = DeltaIndex()
776
def _compress(self, key, bytes, max_delta_size, soft=False):
777
"""see _CommonGroupCompressor._compress"""
778
input_len = len(bytes)
779
# By having action/label/sha1/len, we can parse the group if the index
780
# was ever destroyed, we have the key in 'label', we know the final
781
# bytes are valid from sha1, and we know where to find the end of this
782
# record because of 'len'. (the delta record itself will store the
783
# total length for the expanded record)
784
# 'len: %d\n' costs approximately 1% increase in total data
785
# Having the labels at all costs us 9-10% increase, 38% increase for
786
# inventory pages, and 5.8% increase for text pages
787
# new_chunks = ['label:%s\nsha1:%s\n' % (label, sha1)]
788
if self._delta_index._source_offset != self.endpoint:
789
raise AssertionError('_source_offset != endpoint'
790
' somehow the DeltaIndex got out of sync with'
792
delta = self._delta_index.make_delta(bytes, max_delta_size)
795
enc_length = encode_base128_int(len(bytes))
796
len_mini_header = 1 + len(enc_length)
797
self._delta_index.add_source(bytes, len_mini_header)
798
new_chunks = ['f', enc_length, bytes]
801
enc_length = encode_base128_int(len(delta))
802
len_mini_header = 1 + len(enc_length)
803
new_chunks = ['d', enc_length, delta]
804
self._delta_index.add_delta_source(delta, len_mini_header)
806
start = self.endpoint
807
chunk_start = len(self.chunks)
808
# Now output these bytes
809
self._output_chunks(new_chunks)
810
self.input_bytes += input_len
811
chunk_end = len(self.chunks)
812
self.labels_deltas[key] = (start, chunk_start,
813
self.endpoint, chunk_end)
814
if not self._delta_index._source_offset == self.endpoint:
815
raise AssertionError('the delta index is out of sync'
816
'with the output lines %s != %s'
817
% (self._delta_index._source_offset, self.endpoint))
818
return start, self.endpoint, type
820
def _output_chunks(self, new_chunks):
821
"""Output some chunks.
823
:param new_chunks: The chunks to output.
825
self._last = (len(self.chunks), self.endpoint)
826
endpoint = self.endpoint
827
self.chunks.extend(new_chunks)
828
endpoint += sum(map(len, new_chunks))
829
self.endpoint = endpoint
832
def make_pack_factory(graph, delta, keylength):
833
"""Create a factory for creating a pack based groupcompress.
835
This is only functional enough to run interface tests, it doesn't try to
836
provide a full pack environment.
838
:param graph: Store a graph.
839
:param delta: Delta compress contents.
840
:param keylength: How long should keys be.
842
def factory(transport):
847
graph_index = BTreeBuilder(reference_lists=ref_length,
848
key_elements=keylength)
849
stream = transport.open_write_stream('newpack')
850
writer = pack.ContainerWriter(stream.write)
852
index = _GCGraphIndex(graph_index, lambda:True, parents=parents,
853
add_callback=graph_index.add_nodes)
854
access = _DirectPackAccess({})
855
access.set_writer(writer, graph_index, (transport, 'newpack'))
856
result = GroupCompressVersionedFiles(index, access, delta)
857
result.stream = stream
858
result.writer = writer
863
def cleanup_pack_group(versioned_files):
864
versioned_files.writer.end()
865
versioned_files.stream.close()
868
class GroupCompressVersionedFiles(VersionedFiles):
869
"""A group-compress based VersionedFiles implementation."""
871
def __init__(self, index, access, delta=True):
872
"""Create a GroupCompressVersionedFiles object.
874
:param index: The index object storing access and graph data.
875
:param access: The access object storing raw data.
876
:param delta: Whether to delta compress or just entropy compress.
879
self._access = access
881
self._unadded_refs = {}
882
self._group_cache = LRUSizeCache(max_size=50*1024*1024)
883
self._fallback_vfs = []
885
def add_lines(self, key, parents, lines, parent_texts=None,
886
left_matching_blocks=None, nostore_sha=None, random_id=False,
888
"""Add a text to the store.
890
:param key: The key tuple of the text to add.
891
:param parents: The parents key tuples of the text to add.
892
:param lines: A list of lines. Each line must be a bytestring. And all
893
of them except the last must be terminated with \n and contain no
894
other \n's. The last line may either contain no \n's or a single
895
terminating \n. If the lines list does meet this constraint the add
896
routine may error or may succeed - but you will be unable to read
897
the data back accurately. (Checking the lines have been split
898
correctly is expensive and extremely unlikely to catch bugs so it
899
is not done at runtime unless check_content is True.)
900
:param parent_texts: An optional dictionary containing the opaque
901
representations of some or all of the parents of version_id to
902
allow delta optimisations. VERY IMPORTANT: the texts must be those
903
returned by add_lines or data corruption can be caused.
904
:param left_matching_blocks: a hint about which areas are common
905
between the text and its left-hand-parent. The format is
906
the SequenceMatcher.get_matching_blocks format.
907
:param nostore_sha: Raise ExistingContent and do not add the lines to
908
the versioned file if the digest of the lines matches this.
909
:param random_id: If True a random id has been selected rather than
910
an id determined by some deterministic process such as a converter
911
from a foreign VCS. When True the backend may choose not to check
912
for uniqueness of the resulting key within the versioned file, so
913
this should only be done when the result is expected to be unique
915
:param check_content: If True, the lines supplied are verified to be
916
bytestrings that are correctly formed lines.
917
:return: The text sha1, the number of bytes in the text, and an opaque
918
representation of the inserted version which can be provided
919
back to future add_lines calls in the parent_texts dictionary.
921
self._index._check_write_ok()
922
self._check_add(key, lines, random_id, check_content)
924
# The caller might pass None if there is no graph data, but kndx
925
# indexes can't directly store that, so we give them
926
# an empty tuple instead.
928
# double handling for now. Make it work until then.
929
length = sum(map(len, lines))
930
record = ChunkedContentFactory(key, parents, None, lines)
931
sha1 = list(self._insert_record_stream([record], random_id=random_id,
932
nostore_sha=nostore_sha))[0]
933
return sha1, length, None
935
def add_fallback_versioned_files(self, a_versioned_files):
936
"""Add a source of texts for texts not present in this knit.
938
:param a_versioned_files: A VersionedFiles object.
940
self._fallback_vfs.append(a_versioned_files)
942
def annotate(self, key):
943
"""See VersionedFiles.annotate."""
945
parent_map = self.get_parent_map([key])
947
raise errors.RevisionNotPresent(key, self)
948
if parent_map[key] is not None:
949
search = graph._make_breadth_first_searcher([key])
953
present, ghosts = search.next_with_ghosts()
954
except StopIteration:
957
parent_map = self.get_parent_map(keys)
960
parent_map = {key:()}
961
head_cache = _mod_graph.FrozenHeadsCache(graph)
963
reannotate = annotate.reannotate
964
for record in self.get_record_stream(keys, 'topological', True):
966
chunks = osutils.chunks_to_lines(record.get_bytes_as('chunked'))
967
parent_lines = [parent_cache[parent] for parent in parent_map[key]]
968
parent_cache[key] = list(
969
reannotate(parent_lines, chunks, key, None, head_cache))
970
return parent_cache[key]
972
def check(self, progress_bar=None):
973
"""See VersionedFiles.check()."""
975
for record in self.get_record_stream(keys, 'unordered', True):
976
record.get_bytes_as('fulltext')
978
def _check_add(self, key, lines, random_id, check_content):
979
"""check that version_id and lines are safe to add."""
981
if version_id is not None:
982
if osutils.contains_whitespace(version_id):
983
raise errors.InvalidRevisionId(version_id, self)
984
self.check_not_reserved_id(version_id)
985
# TODO: If random_id==False and the key is already present, we should
986
# probably check that the existing content is identical to what is
987
# being inserted, and otherwise raise an exception. This would make
988
# the bundle code simpler.
990
self._check_lines_not_unicode(lines)
991
self._check_lines_are_lines(lines)
993
def get_parent_map(self, keys):
994
"""Get a map of the graph parents of keys.
996
:param keys: The keys to look up parents for.
997
:return: A mapping from keys to parents. Absent keys are absent from
1000
return self._get_parent_map_with_sources(keys)[0]
1002
def _get_parent_map_with_sources(self, keys):
1003
"""Get a map of the parents of keys.
1005
:param keys: The keys to look up parents for.
1006
:return: A tuple. The first element is a mapping from keys to parents.
1007
Absent keys are absent from the mapping. The second element is a
1008
list with the locations each key was found in. The first element
1009
is the in-this-knit parents, the second the first fallback source,
1013
sources = [self._index] + self._fallback_vfs
1016
for source in sources:
1019
new_result = source.get_parent_map(missing)
1020
source_results.append(new_result)
1021
result.update(new_result)
1022
missing.difference_update(set(new_result))
1023
return result, source_results
1025
def _get_block(self, index_memo):
1026
read_memo = index_memo[0:3]
1029
block = self._group_cache[read_memo]
1032
zdata = self._access.get_raw_records([read_memo]).next()
1033
# decompress - whole thing - this is not a bug, as it
1034
# permits caching. We might want to store the partially
1035
# decompresed group and decompress object, so that recent
1036
# texts are not penalised by big groups.
1037
block = GroupCompressBlock.from_bytes(zdata)
1038
self._group_cache[read_memo] = block
1040
# print len(zdata), len(plain)
1041
# parse - requires split_lines, better to have byte offsets
1042
# here (but not by much - we only split the region for the
1043
# recipe, and we often want to end up with lines anyway.
1046
def get_missing_compression_parent_keys(self):
1047
"""Return the keys of missing compression parents.
1049
Missing compression parents occur when a record stream was missing
1050
basis texts, or a index was scanned that had missing basis texts.
1052
# GroupCompress cannot currently reference texts that are not in the
1053
# group, so this is valid for now
1056
def get_record_stream(self, keys, ordering, include_delta_closure):
1057
"""Get a stream of records for keys.
1059
:param keys: The keys to include.
1060
:param ordering: Either 'unordered' or 'topological'. A topologically
1061
sorted stream has compression parents strictly before their
1063
:param include_delta_closure: If True then the closure across any
1064
compression parents will be included (in the opaque data).
1065
:return: An iterator of ContentFactory objects, each of which is only
1066
valid until the iterator is advanced.
1068
# keys might be a generator
1069
orig_keys = list(keys)
1073
if (not self._index.has_graph
1074
and ordering in ('topological', 'groupcompress')):
1075
# Cannot topological order when no graph has been stored.
1076
# but we allow 'as-requested' or 'unordered'
1077
ordering = 'unordered'
1079
remaining_keys = keys
1082
keys = set(remaining_keys)
1083
for content_factory in self._get_remaining_record_stream(keys,
1084
orig_keys, ordering, include_delta_closure):
1085
remaining_keys.discard(content_factory.key)
1086
yield content_factory
1088
except errors.RetryWithNewPacks, e:
1089
self._access.reload_or_raise(e)
1091
def _find_from_fallback(self, missing):
1092
"""Find whatever keys you can from the fallbacks.
1094
:param missing: A set of missing keys. This set will be mutated as keys
1095
are found from a fallback_vfs
1096
:return: (parent_map, key_to_source_map, source_results)
1097
parent_map the overall key => parent_keys
1098
key_to_source_map a dict from {key: source}
1099
source_results a list of (source: keys)
1102
key_to_source_map = {}
1104
for source in self._fallback_vfs:
1107
source_parents = source.get_parent_map(missing)
1108
parent_map.update(source_parents)
1109
source_parents = list(source_parents)
1110
source_results.append((source, source_parents))
1111
key_to_source_map.update((key, source) for key in source_parents)
1112
missing.difference_update(source_parents)
1113
return parent_map, key_to_source_map, source_results
1115
def _get_ordered_source_keys(self, ordering, parent_map, key_to_source_map):
1116
"""Get the (source, [keys]) list.
1118
The returned objects should be in the order defined by 'ordering',
1119
which can weave between different sources.
1120
:param ordering: Must be one of 'topological' or 'groupcompress'
1121
:return: List of [(source, [keys])] tuples, such that all keys are in
1122
the defined order, regardless of source.
1124
if ordering == 'topological':
1125
present_keys = topo_sort(parent_map)
1127
# ordering == 'groupcompress'
1128
# XXX: This only optimizes for the target ordering. We may need
1129
# to balance that with the time it takes to extract
1130
# ordering, by somehow grouping based on
1131
# locations[key][0:3]
1132
present_keys = sort_gc_optimal(parent_map)
1133
# Now group by source:
1135
current_source = None
1136
for key in present_keys:
1137
source = key_to_source_map.get(key, self)
1138
if source is not current_source:
1139
source_keys.append((source, []))
1140
current_source = source
1141
source_keys[-1][1].append(key)
1144
def _get_as_requested_source_keys(self, orig_keys, locations, unadded_keys,
1147
current_source = None
1148
for key in orig_keys:
1149
if key in locations or key in unadded_keys:
1151
elif key in key_to_source_map:
1152
source = key_to_source_map[key]
1155
if source is not current_source:
1156
source_keys.append((source, []))
1157
current_source = source
1158
source_keys[-1][1].append(key)
1161
def _get_io_ordered_source_keys(self, locations, unadded_keys,
1164
# This is the group the bytes are stored in, followed by the
1165
# location in the group
1166
return locations[key][0]
1167
present_keys = sorted(locations.iterkeys(), key=get_group)
1168
# We don't have an ordering for keys in the in-memory object, but
1169
# lets process the in-memory ones first.
1170
present_keys = list(unadded_keys) + present_keys
1171
# Now grab all of the ones from other sources
1172
source_keys = [(self, present_keys)]
1173
source_keys.extend(source_result)
1176
def _get_remaining_record_stream(self, keys, orig_keys, ordering,
1177
include_delta_closure):
1178
"""Get a stream of records for keys.
1180
:param keys: The keys to include.
1181
:param ordering: one of 'unordered', 'topological', 'groupcompress' or
1183
:param include_delta_closure: If True then the closure across any
1184
compression parents will be included (in the opaque data).
1185
:return: An iterator of ContentFactory objects, each of which is only
1186
valid until the iterator is advanced.
1189
locations = self._index.get_build_details(keys)
1190
unadded_keys = set(self._unadded_refs).intersection(keys)
1191
missing = keys.difference(locations)
1192
missing.difference_update(unadded_keys)
1193
(fallback_parent_map, key_to_source_map,
1194
source_result) = self._find_from_fallback(missing)
1195
if ordering in ('topological', 'groupcompress'):
1196
# would be better to not globally sort initially but instead
1197
# start with one key, recurse to its oldest parent, then grab
1198
# everything in the same group, etc.
1199
parent_map = dict((key, details[2]) for key, details in
1200
locations.iteritems())
1201
for key in unadded_keys:
1202
parent_map[key] = self._unadded_refs[key]
1203
parent_map.update(fallback_parent_map)
1204
source_keys = self._get_ordered_source_keys(ordering, parent_map,
1206
elif ordering == 'as-requested':
1207
source_keys = self._get_as_requested_source_keys(orig_keys,
1208
locations, unadded_keys, key_to_source_map)
1210
# We want to yield the keys in a semi-optimal (read-wise) ordering.
1211
# Otherwise we thrash the _group_cache and destroy performance
1212
source_keys = self._get_io_ordered_source_keys(locations,
1213
unadded_keys, source_result)
1215
yield AbsentContentFactory(key)
1217
last_read_memo = None
1218
# TODO: This works fairly well at batching up existing groups into a
1219
# streamable format, and possibly allowing for taking one big
1220
# group and splitting it when it isn't fully utilized.
1221
# However, it doesn't allow us to find under-utilized groups and
1222
# combine them into a bigger group on the fly.
1223
# (Consider the issue with how chk_map inserts texts
1224
# one-at-a-time.) This could be done at insert_record_stream()
1225
# time, but it probably would decrease the number of
1226
# bytes-on-the-wire for fetch.
1227
for source, keys in source_keys:
1230
if key in self._unadded_refs:
1231
if manager is not None:
1232
for factory in manager.get_record_stream():
1234
last_read_memo = manager = None
1235
bytes, sha1 = self._compressor.extract(key)
1236
parents = self._unadded_refs[key]
1237
yield FulltextContentFactory(key, parents, sha1, bytes)
1239
index_memo, _, parents, (method, _) = locations[key]
1240
read_memo = index_memo[0:3]
1241
if last_read_memo != read_memo:
1242
# We are starting a new block. If we have a
1243
# manager, we have found everything that fits for
1244
# now, so yield records
1245
if manager is not None:
1246
for factory in manager.get_record_stream():
1248
# Now start a new manager
1249
block = self._get_block(index_memo)
1250
manager = _LazyGroupContentManager(block)
1251
last_read_memo = read_memo
1252
start, end = index_memo[3:5]
1253
manager.add_factory(key, parents, start, end)
1255
if manager is not None:
1256
for factory in manager.get_record_stream():
1258
last_read_memo = manager = None
1259
for record in source.get_record_stream(keys, ordering,
1260
include_delta_closure):
1262
if manager is not None:
1263
for factory in manager.get_record_stream():
1266
def get_sha1s(self, keys):
1267
"""See VersionedFiles.get_sha1s()."""
1269
for record in self.get_record_stream(keys, 'unordered', True):
1270
if record.sha1 != None:
1271
result[record.key] = record.sha1
1273
if record.storage_kind != 'absent':
1274
result[record.key] = osutils.sha_string(
1275
record.get_bytes_as('fulltext'))
1278
def insert_record_stream(self, stream):
1279
"""Insert a record stream into this container.
1281
:param stream: A stream of records to insert.
1283
:seealso VersionedFiles.get_record_stream:
1285
# XXX: Setting random_id=True makes
1286
# test_insert_record_stream_existing_keys fail for groupcompress and
1287
# groupcompress-nograph, this needs to be revisited while addressing
1288
# 'bzr branch' performance issues.
1289
for _ in self._insert_record_stream(stream, random_id=False):
1292
def _insert_record_stream(self, stream, random_id=False, nostore_sha=None,
1294
"""Internal core to insert a record stream into this container.
1296
This helper function has a different interface than insert_record_stream
1297
to allow add_lines to be minimal, but still return the needed data.
1299
:param stream: A stream of records to insert.
1300
:param nostore_sha: If the sha1 of a given text matches nostore_sha,
1301
raise ExistingContent, rather than committing the new text.
1302
:param reuse_blocks: If the source is streaming from
1303
groupcompress-blocks, just insert the blocks as-is, rather than
1304
expanding the texts and inserting again.
1305
:return: An iterator over the sha1 of the inserted records.
1306
:seealso insert_record_stream:
1310
def get_adapter(adapter_key):
1312
return adapters[adapter_key]
1314
adapter_factory = adapter_registry.get(adapter_key)
1315
adapter = adapter_factory(self)
1316
adapters[adapter_key] = adapter
1318
# This will go up to fulltexts for gc to gc fetching, which isn't
1320
self._compressor = GroupCompressor()
1321
self._unadded_refs = {}
1324
bytes = self._compressor.flush().to_bytes()
1325
index, start, length = self._access.add_raw_records(
1326
[(None, len(bytes))], bytes)[0]
1328
for key, reads, refs in keys_to_add:
1329
nodes.append((key, "%d %d %s" % (start, length, reads), refs))
1330
self._index.add_records(nodes, random_id=random_id)
1331
self._unadded_refs = {}
1333
self._compressor = GroupCompressor()
1336
max_fulltext_len = 0
1337
max_fulltext_prefix = None
1338
insert_manager = None
1341
# XXX: TODO: remove this, it is just for safety checking for now
1342
inserted_keys = set()
1343
for record in stream:
1344
# Raise an error when a record is missing.
1345
if record.storage_kind == 'absent':
1346
raise errors.RevisionNotPresent(record.key, self)
1348
if record.key in inserted_keys:
1349
trace.note('Insert claimed random_id=True,'
1350
' but then inserted %r two times', record.key)
1352
inserted_keys.add(record.key)
1354
# If the reuse_blocks flag is set, check to see if we can just
1355
# copy a groupcompress block as-is.
1356
if record.storage_kind == 'groupcompress-block':
1357
# Insert the raw block into the target repo
1358
insert_manager = record._manager
1359
insert_manager._check_rebuild_block()
1360
bytes = record._manager._block.to_bytes()
1361
_, start, length = self._access.add_raw_records(
1362
[(None, len(bytes))], bytes)[0]
1365
block_length = length
1366
if record.storage_kind in ('groupcompress-block',
1367
'groupcompress-block-ref'):
1368
if insert_manager is None:
1369
raise AssertionError('No insert_manager set')
1370
value = "%d %d %d %d" % (block_start, block_length,
1371
record._start, record._end)
1372
nodes = [(record.key, value, (record.parents,))]
1373
# TODO: Consider buffering up many nodes to be added, not
1374
# sure how much overhead this has, but we're seeing
1375
# ~23s / 120s in add_records calls
1376
self._index.add_records(nodes, random_id=random_id)
1379
bytes = record.get_bytes_as('fulltext')
1380
except errors.UnavailableRepresentation:
1381
adapter_key = record.storage_kind, 'fulltext'
1382
adapter = get_adapter(adapter_key)
1383
bytes = adapter.get_bytes(record)
1384
if len(record.key) > 1:
1385
prefix = record.key[0]
1386
soft = (prefix == last_prefix)
1390
if max_fulltext_len < len(bytes):
1391
max_fulltext_len = len(bytes)
1392
max_fulltext_prefix = prefix
1393
(found_sha1, start_point, end_point,
1394
type) = self._compressor.compress(record.key,
1395
bytes, record.sha1, soft=soft,
1396
nostore_sha=nostore_sha)
1397
# delta_ratio = float(len(bytes)) / (end_point - start_point)
1398
# Check if we want to continue to include that text
1399
if (prefix == max_fulltext_prefix
1400
and end_point < 2 * max_fulltext_len):
1401
# As long as we are on the same file_id, we will fill at least
1402
# 2 * max_fulltext_len
1403
start_new_block = False
1404
elif end_point > 4*1024*1024:
1405
start_new_block = True
1406
elif (prefix is not None and prefix != last_prefix
1407
and end_point > 2*1024*1024):
1408
start_new_block = True
1410
start_new_block = False
1411
last_prefix = prefix
1413
self._compressor.pop_last()
1415
max_fulltext_len = len(bytes)
1416
(found_sha1, start_point, end_point,
1417
type) = self._compressor.compress(record.key, bytes,
1419
if record.key[-1] is None:
1420
key = record.key[:-1] + ('sha1:' + found_sha1,)
1423
self._unadded_refs[key] = record.parents
1425
keys_to_add.append((key, '%d %d' % (start_point, end_point),
1427
if len(keys_to_add):
1429
self._compressor = None
1431
def iter_lines_added_or_present_in_keys(self, keys, pb=None):
1432
"""Iterate over the lines in the versioned files from keys.
1434
This may return lines from other keys. Each item the returned
1435
iterator yields is a tuple of a line and a text version that that line
1436
is present in (not introduced in).
1438
Ordering of results is in whatever order is most suitable for the
1439
underlying storage format.
1441
If a progress bar is supplied, it may be used to indicate progress.
1442
The caller is responsible for cleaning up progress bars (because this
1446
* Lines are normalised by the underlying store: they will all have \n
1448
* Lines are returned in arbitrary order.
1450
:return: An iterator over (line, key).
1453
pb = progress.DummyProgress()
1456
# we don't care about inclusions, the caller cares.
1457
# but we need to setup a list of records to visit.
1458
# we need key, position, length
1459
for key_idx, record in enumerate(self.get_record_stream(keys,
1460
'unordered', True)):
1461
# XXX: todo - optimise to use less than full texts.
1463
pb.update('Walking content', key_idx, total)
1464
if record.storage_kind == 'absent':
1465
raise errors.RevisionNotPresent(key, self)
1466
lines = osutils.split_lines(record.get_bytes_as('fulltext'))
1469
pb.update('Walking content', total, total)
1472
"""See VersionedFiles.keys."""
1473
if 'evil' in debug.debug_flags:
1474
trace.mutter_callsite(2, "keys scales with size of history")
1475
sources = [self._index] + self._fallback_vfs
1477
for source in sources:
1478
result.update(source.keys())
1482
class _GCGraphIndex(object):
1483
"""Mapper from GroupCompressVersionedFiles needs into GraphIndex storage."""
1485
def __init__(self, graph_index, is_locked, parents=True,
1487
"""Construct a _GCGraphIndex on a graph_index.
1489
:param graph_index: An implementation of bzrlib.index.GraphIndex.
1490
:param is_locked: A callback, returns True if the index is locked and
1492
:param parents: If True, record knits parents, if not do not record
1494
:param add_callback: If not None, allow additions to the index and call
1495
this callback with a list of added GraphIndex nodes:
1496
[(node, value, node_refs), ...]
1498
self._add_callback = add_callback
1499
self._graph_index = graph_index
1500
self._parents = parents
1501
self.has_graph = parents
1502
self._is_locked = is_locked
1504
def add_records(self, records, random_id=False):
1505
"""Add multiple records to the index.
1507
This function does not insert data into the Immutable GraphIndex
1508
backing the KnitGraphIndex, instead it prepares data for insertion by
1509
the caller and checks that it is safe to insert then calls
1510
self._add_callback with the prepared GraphIndex nodes.
1512
:param records: a list of tuples:
1513
(key, options, access_memo, parents).
1514
:param random_id: If True the ids being added were randomly generated
1515
and no check for existence will be performed.
1517
if not self._add_callback:
1518
raise errors.ReadOnlyError(self)
1519
# we hope there are no repositories with inconsistent parentage
1524
for (key, value, refs) in records:
1525
if not self._parents:
1529
raise KnitCorrupt(self,
1530
"attempt to add node with parents "
1531
"in parentless index.")
1534
keys[key] = (value, refs)
1537
present_nodes = self._get_entries(keys)
1538
for (index, key, value, node_refs) in present_nodes:
1539
if node_refs != keys[key][1]:
1540
raise errors.KnitCorrupt(self, "inconsistent details in add_records"
1541
": %s %s" % ((value, node_refs), keys[key]))
1547
for key, (value, node_refs) in keys.iteritems():
1548
result.append((key, value, node_refs))
1550
for key, (value, node_refs) in keys.iteritems():
1551
result.append((key, value))
1553
self._add_callback(records)
1555
def _check_read(self):
1556
"""Raise an exception if reads are not permitted."""
1557
if not self._is_locked():
1558
raise errors.ObjectNotLocked(self)
1560
def _check_write_ok(self):
1561
"""Raise an exception if writes are not permitted."""
1562
if not self._is_locked():
1563
raise errors.ObjectNotLocked(self)
1565
def _get_entries(self, keys, check_present=False):
1566
"""Get the entries for keys.
1568
Note: Callers are responsible for checking that the index is locked
1569
before calling this method.
1571
:param keys: An iterable of index key tuples.
1576
for node in self._graph_index.iter_entries(keys):
1578
found_keys.add(node[1])
1580
# adapt parentless index to the rest of the code.
1581
for node in self._graph_index.iter_entries(keys):
1582
yield node[0], node[1], node[2], ()
1583
found_keys.add(node[1])
1585
missing_keys = keys.difference(found_keys)
1587
raise RevisionNotPresent(missing_keys.pop(), self)
1589
def get_parent_map(self, keys):
1590
"""Get a map of the parents of keys.
1592
:param keys: The keys to look up parents for.
1593
:return: A mapping from keys to parents. Absent keys are absent from
1597
nodes = self._get_entries(keys)
1601
result[node[1]] = node[3][0]
1604
result[node[1]] = None
1607
def get_build_details(self, keys):
1608
"""Get the various build details for keys.
1610
Ghosts are omitted from the result.
1612
:param keys: An iterable of keys.
1613
:return: A dict of key:
1614
(index_memo, compression_parent, parents, record_details).
1616
opaque structure to pass to read_records to extract the raw
1619
Content that this record is built upon, may be None
1621
Logical parents of this node
1623
extra information about the content which needs to be passed to
1624
Factory.parse_record
1628
entries = self._get_entries(keys)
1629
for entry in entries:
1631
if not self._parents:
1634
parents = entry[3][0]
1636
result[key] = (self._node_to_position(entry),
1637
None, parents, (method, None))
1641
"""Get all the keys in the collection.
1643
The keys are not ordered.
1646
return [node[1] for node in self._graph_index.iter_all_entries()]
1648
def _node_to_position(self, node):
1649
"""Convert an index value to position details."""
1650
bits = node[2].split(' ')
1651
# It would be nice not to read the entire gzip.
1652
start = int(bits[0])
1654
basis_end = int(bits[2])
1655
delta_end = int(bits[3])
1656
return node[0], start, stop, basis_end, delta_end
1659
from bzrlib._groupcompress_py import (
1661
apply_delta_to_source,
1667
from bzrlib._groupcompress_pyx import (
1669
apply_delta_to_source,
1674
GroupCompressor = PyrexGroupCompressor
1676
GroupCompressor = PythonGroupCompressor
added
removed
bzrlib/groupcompress.py
