« back to all changes in this revision
Viewing changes to bzrlib/knit.py
- browse files at revision 2474.1.23
- compare with another revision
- download diff
- download tarball
- view history from revision 2474.1.23
- Committer: John Arbash Meinel
- Date: 2007-05-04 18:59:36 UTC
- mto: This revision was merged to the branch mainline in revision 2643.
- Revision ID: john@arbash-meinel.com-20070504185936-1mjdoqmtz74xe5mg
A C implementation of _fields_to_entry_0_parents drops the time from 400ms to 330ms for a 21k-entry tree
- files added:
- bzrlib/bundle/common.py
- bzrlib/bundle/old
- bzrlib/compiled
- bzrlib/tests/compiled
- files removed:
- bzrlib/_dirstate_helpers_c.h
- bzrlib/help_topics
- bzrlib/help_topics/en
- bzrlib/tests/commands
- bzrlib/tests/inventory_implementations
- bzrlib/util/tests
- doc/developers
- doc/en
- doc/en/admin-guide
- doc/en/developer-guide
- doc/en/mini-tutorial
- doc/en/quick-reference
- doc/en/release-notes
- doc/en/tutorials
- doc/en/user-guide
- doc/en/user-guide/images
- doc/en/user-reference
- files renamed:
- doc/developers/HACKING.txt => HACKING
- bzrlib/_dirstate_helpers_c.pyx => bzrlib/compiled/dirstate_helpers.pyx
- bzrlib/deprecated_graph.py => bzrlib/graph.py
- bzrlib/help_topics/__init__.py => bzrlib/help_topics.py
- bzrlib/_patiencediff_py.py => bzrlib/patiencediff.py
- bzrlib/plugins/launchpad/lp_directory.py => bzrlib/plugins/launchpad/lp_indirect.py
- bzrlib/plugins/launchpad/test_lp_directory.py => bzrlib/plugins/launchpad/test_lp_indirect.py
- bzrlib/tests/http_utils.py => bzrlib/tests/HTTPTestUtil.py
- bzrlib/tests/http_server.py => bzrlib/tests/HttpServer.py
- bzrlib/tests/blackbox/test_send.py => bzrlib/tests/blackbox/test_bundle.py
- bzrlib/tests/test__dirstate_helpers.py => bzrlib/tests/compiled/test_dirstate_helpers.py
- bzrlib/tests/test_deprecated_graph.py => bzrlib/tests/test_graph.py
- bzrlib/tests/test_revisionspec.py => bzrlib/tests/test_revisionnamespaces.py
- doc/en/tutorials/centralized_workflow.txt => doc/centralized_workflow.txt
- bzrlib/help_topics/en/configuration.txt => doc/configuration.txt
- doc/en/user-guide/http_smart_server.txt => doc/http_smart_server.txt
- doc/en/user-guide/index.txt => doc/index.txt
- doc/en/user-guide/plugins.txt => doc/plugins.txt
- doc/en/user-guide/server.txt => doc/server.txt
- doc/en/user-guide/setting_up_email.txt => doc/setting_up_email.txt
- doc/en/user-guide/specifying_revisions.txt => doc/specifying_revisions.txt
- doc/en/tutorials/tutorial.txt => doc/tutorial.txt
- doc/en/user-guide/using_aliases.txt => doc/using_aliases.txt
- doc/en/user-guide/version_info.txt => doc/version_info.txt
- files modified:
- .bzrignore
added
removed
bzrlib/knit.py
1
# Copyright (C) 2005, 2006, 2007 Canonical Ltd
1
# Copyright (C) 2005, 2006 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
62
62
63
63
from copy import copy
64
64
from cStringIO import StringIO
65
import difflib
65
66
from itertools import izip, chain
66
67
import operator
67
68
import os
68
69
import sys
69
70
import warnings
70
from zlib import Z_DEFAULT_COMPRESSION
71
71
72
72
import bzrlib
73
from bzrlib.lazy_import import lazy_import
74
lazy_import(globals(), """
75
from bzrlib import (
76
annotate,
77
graph as _mod_graph,
78
lru_cache,
79
pack,
80
trace,
81
)
82
""")
83
73
from bzrlib import (
84
74
cache_utf8,
85
debug,
86
diff,
87
75
errors,
88
76
osutils,
89
77
patiencediff,
90
78
progress,
91
merge,
92
79
ui,
93
80
)
94
81
from bzrlib.errors import (
101
88
RevisionNotPresent,
102
89
RevisionAlreadyPresent,
103
90
)
104
from bzrlib.graph import Graph
91
from bzrlib.tuned_gzip import GzipFile
92
from bzrlib.trace import mutter
105
93
from bzrlib.osutils import (
106
94
contains_whitespace,
107
95
contains_linebreaks,
108
sha_string,
109
96
sha_strings,
110
97
)
111
from bzrlib.symbol_versioning import (
112
DEPRECATED_PARAMETER,
113
deprecated_method,
114
deprecated_passed,
115
one_four,
116
)
98
from bzrlib.symbol_versioning import DEPRECATED_PARAMETER, deprecated_passed
117
99
from bzrlib.tsort import topo_sort
118
from bzrlib.tuned_gzip import GzipFile, bytes_to_gzip
119
100
import bzrlib.ui
101
import bzrlib.weave
120
102
from bzrlib.versionedfile import VersionedFile, InterVersionedFile
121
import bzrlib.weave
122
103
123
104
124
105
# TODO: Split out code specific to this format into an associated object.
141
122
class KnitContent(object):
142
123
"""Content of a knit version to which deltas can be applied."""
143
124
144
def __init__(self):
145
self._should_strip_eol = False
125
def __init__(self, lines):
126
self._lines = lines
127
128
def annotate_iter(self):
129
"""Yield tuples of (origin, text) for each content line."""
130
return iter(self._lines)
146
131
147
132
def annotate(self):
148
133
"""Return a list of (origin, text) tuples."""
149
134
return list(self.annotate_iter())
150
135
151
def apply_delta(self, delta, new_version_id):
152
"""Apply delta to this object to become new_version_id."""
153
raise NotImplementedError(self.apply_delta)
154
155
def cleanup_eol(self, copy_on_mutate=True):
156
if self._should_strip_eol:
157
if copy_on_mutate:
158
self._lines = self._lines[:]
159
self.strip_last_line_newline()
160
161
136
def line_delta_iter(self, new_lines):
162
137
"""Generate line-based delta from this content to new_lines."""
163
138
new_texts = new_lines.text()
164
139
old_texts = self.text()
165
s = patiencediff.PatienceSequenceMatcher(None, old_texts, new_texts)
140
s = KnitSequenceMatcher(None, old_texts, new_texts)
166
141
for tag, i1, i2, j1, j2 in s.get_opcodes():
167
142
if tag == 'equal':
168
143
continue
172
147
def line_delta(self, new_lines):
173
148
return list(self.line_delta_iter(new_lines))
174
149
175
@staticmethod
176
def get_line_delta_blocks(knit_delta, source, target):
177
"""Extract SequenceMatcher.get_matching_blocks() from a knit delta"""
178
target_len = len(target)
179
s_pos = 0
180
t_pos = 0
181
for s_begin, s_end, t_len, new_text in knit_delta:
182
true_n = s_begin - s_pos
183
n = true_n
184
if n > 0:
185
# knit deltas do not provide reliable info about whether the
186
# last line of a file matches, due to eol handling.
187
if source[s_pos + n -1] != target[t_pos + n -1]:
188
n-=1
189
if n > 0:
190
yield s_pos, t_pos, n
191
t_pos += t_len + true_n
192
s_pos = s_end
193
n = target_len - t_pos
194
if n > 0:
195
if source[s_pos + n -1] != target[t_pos + n -1]:
196
n-=1
197
if n > 0:
198
yield s_pos, t_pos, n
199
yield s_pos + (target_len - t_pos), target_len, 0
200
201
202
class AnnotatedKnitContent(KnitContent):
203
"""Annotated content."""
204
205
def __init__(self, lines):
206
KnitContent.__init__(self)
207
self._lines = lines
208
209
def annotate_iter(self):
210
"""Yield tuples of (origin, text) for each content line."""
211
return iter(self._lines)
212
213
def apply_delta(self, delta, new_version_id):
214
"""Apply delta to this object to become new_version_id."""
215
offset = 0
216
lines = self._lines
217
for start, end, count, delta_lines in delta:
218
lines[offset+start:offset+end] = delta_lines
219
offset = offset + (start - end) + count
220
221
def strip_last_line_newline(self):
222
line = self._lines[-1][1].rstrip('\n')
223
self._lines[-1] = (self._lines[-1][0], line)
224
self._should_strip_eol = False
225
226
def text(self):
227
try:
228
lines = [text for origin, text in self._lines]
229
except ValueError, e:
230
# most commonly (only?) caused by the internal form of the knit
231
# missing annotation information because of a bug - see thread
232
# around 20071015
233
raise KnitCorrupt(self,
234
"line in annotated knit missing annotation information: %s"
235
% (e,))
236
237
if self._should_strip_eol:
238
anno, line = lines[-1]
239
lines[-1] = (anno, line.rstrip('\n'))
240
return lines
241
242
def copy(self):
243
return AnnotatedKnitContent(self._lines[:])
244
245
246
class PlainKnitContent(KnitContent):
247
"""Unannotated content.
248
249
When annotate[_iter] is called on this content, the same version is reported
250
for all lines. Generally, annotate[_iter] is not useful on PlainKnitContent
251
objects.
252
"""
253
254
def __init__(self, lines, version_id):
255
KnitContent.__init__(self)
256
self._lines = lines
257
self._version_id = version_id
258
259
def annotate_iter(self):
260
"""Yield tuples of (origin, text) for each content line."""
261
for line in self._lines:
262
yield self._version_id, line
263
264
def apply_delta(self, delta, new_version_id):
265
"""Apply delta to this object to become new_version_id."""
266
offset = 0
267
lines = self._lines
268
for start, end, count, delta_lines in delta:
269
lines[offset+start:offset+end] = delta_lines
270
offset = offset + (start - end) + count
271
self._version_id = new_version_id
272
273
def copy(self):
274
return PlainKnitContent(self._lines[:], self._version_id)
275
276
def strip_last_line_newline(self):
277
self._lines[-1] = self._lines[-1].rstrip('\n')
278
self._should_strip_eol = False
279
280
def text(self):
281
lines = self._lines
282
if self._should_strip_eol:
283
lines = lines[:]
284
lines[-1] = lines[-1].rstrip('\n')
285
return lines
150
def text(self):
151
return [text for origin, text in self._lines]
152
153
def copy(self):
154
return KnitContent(self._lines[:])
286
155
287
156
288
157
class _KnitFactory(object):
289
"""Base class for common Factory functions."""
290
291
def parse_record(self, version_id, record, record_details,
292
base_content, copy_base_content=True):
293
"""Parse a record into a full content object.
294
295
:param version_id: The official version id for this content
296
:param record: The data returned by read_records_iter()
297
:param record_details: Details about the record returned by
298
get_build_details
299
:param base_content: If get_build_details returns a compression_parent,
300
you must return a base_content here, else use None
301
:param copy_base_content: When building from the base_content, decide
302
you can either copy it and return a new object, or modify it in
303
place.
304
:return: (content, delta) A Content object and possibly a line-delta,
305
delta may be None
306
"""
307
method, noeol = record_details
308
if method == 'line-delta':
309
assert base_content is not None
310
if copy_base_content:
311
content = base_content.copy()
312
else:
313
content = base_content
314
delta = self.parse_line_delta(record, version_id)
315
content.apply_delta(delta, version_id)
316
else:
317
content = self.parse_fulltext(record, version_id)
318
delta = None
319
content._should_strip_eol = noeol
320
return (content, delta)
158
"""Base factory for creating content objects."""
159
160
def make(self, lines, version_id):
161
num_lines = len(lines)
162
return KnitContent(zip([version_id] * num_lines, lines))
321
163
322
164
323
165
class KnitAnnotateFactory(_KnitFactory):
325
167
326
168
annotated = True
327
169
328
def make(self, lines, version_id):
329
num_lines = len(lines)
330
return AnnotatedKnitContent(zip([version_id] * num_lines, lines))
331
332
170
def parse_fulltext(self, content, version_id):
333
171
"""Convert fulltext to internal representation
334
172
342
180
# Figure out a way to not require the overhead of turning the
343
181
# list back into tuples.
344
182
lines = [tuple(line.split(' ', 1)) for line in content]
345
return AnnotatedKnitContent(lines)
183
return KnitContent(lines)
346
184
347
185
def parse_line_delta_iter(self, lines):
348
186
return iter(self.parse_line_delta(lines))
349
187
350
def parse_line_delta(self, lines, version_id, plain=False):
188
def parse_line_delta(self, lines, version_id):
351
189
"""Convert a line based delta into internal representation.
352
190
353
191
line delta is in the form of:
356
194
revid(utf8) newline\n
357
195
internal representation is
358
196
(start, end, count, [1..count tuples (revid, newline)])
359
360
:param plain: If True, the lines are returned as a plain
361
list without annotations, not as a list of (origin, content) tuples, i.e.
362
(start, end, count, [1..count newline])
363
197
"""
364
198
result = []
365
199
lines = iter(lines)
371
205
return cache.setdefault(origin, origin), text
372
206
373
207
# walk through the lines parsing.
374
# Note that the plain test is explicitly pulled out of the
375
# loop to minimise any performance impact
376
if plain:
377
for header in lines:
378
start, end, count = [int(n) for n in header.split(',')]
379
contents = [next().split(' ', 1)[1] for i in xrange(count)]
380
result.append((start, end, count, contents))
381
else:
382
for header in lines:
383
start, end, count = [int(n) for n in header.split(',')]
384
contents = [tuple(next().split(' ', 1)) for i in xrange(count)]
385
result.append((start, end, count, contents))
208
for header in lines:
209
start, end, count = [int(n) for n in header.split(',')]
210
contents = [tuple(next().split(' ', 1)) for i in xrange(count)]
211
result.append((start, end, count, contents))
386
212
return result
387
213
388
214
def get_fulltext_content(self, lines):
427
253
for origin, text in lines)
428
254
return out
429
255
430
def annotate_iter(self, knit, version_id):
431
content = knit._get_content(version_id)
432
return content.annotate_iter()
433
434
256
435
257
class KnitPlainFactory(_KnitFactory):
436
258
"""Factory for creating plain Content objects."""
437
259
438
260
annotated = False
439
261
440
def make(self, lines, version_id):
441
return PlainKnitContent(lines, version_id)
442
443
262
def parse_fulltext(self, content, version_id):
444
263
"""This parses an unannotated fulltext.
445
264
455
274
header = lines[cur]
456
275
cur += 1
457
276
start, end, c = [int(n) for n in header.split(',')]
458
yield start, end, c, lines[cur:cur+c]
277
yield start, end, c, zip([version_id] * c, lines[cur:cur+c])
459
278
cur += c
460
279
461
280
def parse_line_delta(self, lines, version_id):
486
305
out = []
487
306
for start, end, c, lines in delta:
488
307
out.append('%d,%d,%d\n' % (start, end, c))
489
out.extend(lines)
308
out.extend([text for origin, text in lines])
490
309
return out
491
310
492
def annotate_iter(self, knit, version_id):
493
annotator = _KnitAnnotator(knit)
494
return iter(annotator.annotate(version_id))
495
496
311
497
312
def make_empty_knit(transport, relpath):
498
313
"""Construct a empty knit at the specified location."""
499
314
k = KnitVersionedFile(transport, relpath, 'w', KnitPlainFactory)
315
k._data._open_file()
500
316
501
317
502
318
class KnitVersionedFile(VersionedFile):
515
331
"""
516
332
517
333
def __init__(self, relpath, transport, file_mode=None, access_mode=None,
518
factory=None, delta=True, create=False, create_parent_dir=False,
519
delay_create=False, dir_mode=None, index=None, access_method=None):
334
factory=None, basis_knit=DEPRECATED_PARAMETER, delta=True,
335
create=False, create_parent_dir=False, delay_create=False,
336
dir_mode=None):
520
337
"""Construct a knit at location specified by relpath.
521
338
522
339
:param create: If not True, only open an existing knit.
525
342
hash-prefixes that may not exist yet)
526
343
:param delay_create: The calling code is aware that the knit won't
527
344
actually be created until the first data is stored.
528
:param index: An index to use for the knit.
529
345
"""
346
if deprecated_passed(basis_knit):
347
warnings.warn("KnitVersionedFile.__(): The basis_knit parameter is"
348
" deprecated as of bzr 0.9.",
349
DeprecationWarning, stacklevel=2)
530
350
if access_mode is None:
531
351
access_mode = 'w'
532
352
super(KnitVersionedFile, self).__init__(access_mode)
539
359
540
360
self._max_delta_chain = 200
541
361
542
if index is None:
543
self._index = _KnitIndex(transport, relpath + INDEX_SUFFIX,
544
access_mode, create=create, file_mode=file_mode,
545
create_parent_dir=create_parent_dir, delay_create=delay_create,
546
dir_mode=dir_mode)
547
else:
548
self._index = index
549
if access_method is None:
550
_access = _KnitAccess(transport, relpath + DATA_SUFFIX, file_mode, dir_mode,
551
((create and not len(self)) and delay_create), create_parent_dir)
552
else:
553
_access = access_method
554
if create and not len(self) and not delay_create:
555
_access.create()
556
self._data = _KnitData(_access)
362
self._index = _KnitIndex(transport, relpath + INDEX_SUFFIX,
363
access_mode, create=create, file_mode=file_mode,
364
create_parent_dir=create_parent_dir, delay_create=delay_create,
365
dir_mode=dir_mode)
366
self._data = _KnitData(transport, relpath + DATA_SUFFIX,
367
access_mode, create=create and not len(self), file_mode=file_mode,
368
create_parent_dir=create_parent_dir, delay_create=delay_create,
369
dir_mode=dir_mode)
557
370
558
371
def __repr__(self):
559
return '%s(%s)' % (self.__class__.__name__,
372
return '%s(%s)' % (self.__class__.__name__,
560
373
self.transport.abspath(self.filename))
561
374
562
375
def _check_should_delta(self, first_parents):
576
389
for count in xrange(self._max_delta_chain):
577
390
parent = delta_parents[0]
578
391
method = self._index.get_method(parent)
579
index, pos, size = self._index.get_position(parent)
392
pos, size = self._index.get_position(parent)
580
393
if method == 'fulltext':
581
394
fulltext_size = size
582
395
break
583
396
delta_size += size
584
delta_parents = self._index.get_parent_map([parent])[parent]
397
delta_parents = self._index.get_parents(parent)
585
398
else:
586
399
# We couldn't find a fulltext, so we must create a new one
587
400
return False
588
401
589
402
return fulltext_size > delta_size
590
403
404
def _add_delta(self, version_id, parents, delta_parent, sha1, noeol, delta):
405
"""See VersionedFile._add_delta()."""
406
self._check_add(version_id, []) # should we check the lines ?
407
self._check_versions_present(parents)
408
present_parents = []
409
ghosts = []
410
parent_texts = {}
411
for parent in parents:
412
if not self.has_version(parent):
413
ghosts.append(parent)
414
else:
415
present_parents.append(parent)
416
417
if delta_parent is None:
418
# reconstitute as full text.
419
assert len(delta) == 1 or len(delta) == 0
420
if len(delta):
421
assert delta[0][0] == 0
422
assert delta[0][1] == 0, delta[0][1]
423
return super(KnitVersionedFile, self)._add_delta(version_id,
424
parents,
425
delta_parent,
426
sha1,
427
noeol,
428
delta)
429
430
digest = sha1
431
432
options = []
433
if noeol:
434
options.append('no-eol')
435
436
if delta_parent is not None:
437
# determine the current delta chain length.
438
# To speed the extract of texts the delta chain is limited
439
# to a fixed number of deltas. This should minimize both
440
# I/O and the time spend applying deltas.
441
# The window was changed to a maximum of 200 deltas, but also added
442
# was a check that the total compressed size of the deltas is
443
# smaller than the compressed size of the fulltext.
444
if not self._check_should_delta([delta_parent]):
445
# We don't want a delta here, just do a normal insertion.
446
return super(KnitVersionedFile, self)._add_delta(version_id,
447
parents,
448
delta_parent,
449
sha1,
450
noeol,
451
delta)
452
453
options.append('line-delta')
454
store_lines = self.factory.lower_line_delta(delta)
455
456
where, size = self._data.add_record(version_id, digest, store_lines)
457
self._index.add_version(version_id, options, where, size, parents)
458
591
459
def _add_raw_records(self, records, data):
592
460
"""Add all the records 'records' with data pre-joined in 'data'.
593
461
597
465
the preceding records sizes.
598
466
"""
599
467
# write all the data
600
raw_record_sizes = [record[3] for record in records]
601
positions = self._data.add_raw_records(raw_record_sizes, data)
468
pos = self._data.add_raw_record(data)
602
469
offset = 0
603
470
index_entries = []
604
for (version_id, options, parents, size), access_memo in zip(
605
records, positions):
606
index_entries.append((version_id, options, access_memo, parents))
471
for (version_id, options, parents, size) in records:
472
index_entries.append((version_id, options, pos+offset,
473
size, parents))
607
474
if self._data._do_cache:
608
475
self._data._cache[version_id] = data[offset:offset+size]
609
476
offset += size
632
499
# move the copied index into place
633
500
transport.move(name + INDEX_SUFFIX + '.tmp', name + INDEX_SUFFIX)
634
501
635
def get_data_stream(self, required_versions):
636
"""Get a data stream for the specified versions.
637
638
Versions may be returned in any order, not necessarily the order
639
specified. They are returned in a partial order by compression
640
parent, so that the deltas can be applied as the data stream is
641
inserted; however note that compression parents will not be sent
642
unless they were specifically requested, as the client may already
643
have them.
644
645
:param required_versions: The exact set of versions to be extracted.
646
Unlike some other knit methods, this is not used to generate a
647
transitive closure, rather it is used precisely as given.
502
def create_empty(self, name, transport, mode=None):
503
return KnitVersionedFile(name, transport, factory=self.factory,
504
delta=self.delta, create=True)
505
506
def _fix_parents(self, version_id, new_parents):
507
"""Fix the parents list for version.
648
508
649
:returns: format_signature, list of (version, options, length, parents),
650
reader_callable.
509
This is done by appending a new version to the index
510
with identical data except for the parents list.
511
the parents list must be a superset of the current
512
list.
651
513
"""
652
required_version_set = frozenset(required_versions)
653
version_index = {}
654
# list of revisions that can just be sent without waiting for their
655
# compression parent
656
ready_to_send = []
657
# map from revision to the children based on it
658
deferred = {}
659
# first, read all relevant index data, enough to sort into the right
660
# order to return
661
for version_id in required_versions:
662
options = self._index.get_options(version_id)
663
parents = self._index.get_parents_with_ghosts(version_id)
664
index_memo = self._index.get_position(version_id)
665
version_index[version_id] = (index_memo, options, parents)
666
if ('line-delta' in options
667
and parents[0] in required_version_set):
668
# must wait until the parent has been sent
669
deferred.setdefault(parents[0], []). \
670
append(version_id)
671
else:
672
# either a fulltext, or a delta whose parent the client did
673
# not ask for and presumably already has
674
ready_to_send.append(version_id)
675
# build a list of results to return, plus instructions for data to
676
# read from the file
677
copy_queue_records = []
678
temp_version_list = []
679
while ready_to_send:
680
# XXX: pushing and popping lists may be a bit inefficient
681
version_id = ready_to_send.pop(0)
682
(index_memo, options, parents) = version_index[version_id]
683
copy_queue_records.append((version_id, index_memo))
684
none, data_pos, data_size = index_memo
685
temp_version_list.append((version_id, options, data_size,
686
parents))
687
if version_id in deferred:
688
# now we can send all the children of this revision - we could
689
# put them in anywhere, but we hope that sending them soon
690
# after the fulltext will give good locality in the receiver
691
ready_to_send[:0] = deferred.pop(version_id)
692
assert len(deferred) == 0, \
693
"Still have compressed child versions waiting to be sent"
694
# XXX: The stream format is such that we cannot stream it - we have to
695
# know the length of all the data a-priori.
696
raw_datum = []
697
result_version_list = []
698
for (version_id, raw_data), \
699
(version_id2, options, _, parents) in \
700
izip(self._data.read_records_iter_raw(copy_queue_records),
701
temp_version_list):
702
assert version_id == version_id2, \
703
'logic error, inconsistent results'
704
raw_datum.append(raw_data)
705
result_version_list.append(
706
(version_id, options, len(raw_data), parents))
707
# provide a callback to get data incrementally.
708
pseudo_file = StringIO(''.join(raw_datum))
709
def read(length):
710
if length is None:
711
return pseudo_file.read()
712
else:
713
return pseudo_file.read(length)
714
return (self.get_format_signature(), result_version_list, read)
715
716
def _extract_blocks(self, version_id, source, target):
717
if self._index.get_method(version_id) != 'line-delta':
718
return None
719
parent, sha1, noeol, delta = self.get_delta(version_id)
720
return KnitContent.get_line_delta_blocks(delta, source, target)
514
current_values = self._index._cache[version_id]
515
assert set(current_values[4]).difference(set(new_parents)) == set()
516
self._index.add_version(version_id,
517
current_values[1],
518
current_values[2],
519
current_values[3],
520
new_parents)
721
521
722
522
def get_delta(self, version_id):
723
523
"""Get a delta for constructing version from some other version."""
524
version_id = osutils.safe_revision_id(version_id)
724
525
self.check_not_reserved_id(version_id)
725
parents = self.get_parent_map([version_id])[version_id]
526
if not self.has_version(version_id):
527
raise RevisionNotPresent(version_id, self.filename)
528
529
parents = self.get_parents(version_id)
726
530
if len(parents):
727
531
parent = parents[0]
728
532
else:
729
533
parent = None
730
index_memo = self._index.get_position(version_id)
731
data, sha1 = self._data.read_records(((version_id, index_memo),))[version_id]
534
data_pos, data_size = self._index.get_position(version_id)
535
data, sha1 = self._data.read_records(((version_id, data_pos, data_size),))[version_id]
732
536
noeol = 'no-eol' in self._index.get_options(version_id)
733
537
if 'fulltext' == self._index.get_method(version_id):
734
538
new_content = self.factory.parse_fulltext(data, version_id)
738
542
else:
739
543
old_texts = []
740
544
new_texts = new_content.text()
741
delta_seq = patiencediff.PatienceSequenceMatcher(None, old_texts,
742
new_texts)
545
delta_seq = KnitSequenceMatcher(None, old_texts, new_texts)
743
546
return parent, sha1, noeol, self._make_line_delta(delta_seq, new_content)
744
547
else:
745
548
delta = self.factory.parse_line_delta(data, version_id)
746
549
return parent, sha1, noeol, delta
747
748
def get_format_signature(self):
749
"""See VersionedFile.get_format_signature()."""
750
if self.factory.annotated:
751
annotated_part = "annotated"
752
else:
753
annotated_part = "plain"
754
return "knit-%s" % (annotated_part,)
755
550
756
@deprecated_method(one_four)
757
551
def get_graph_with_ghosts(self):
758
552
"""See VersionedFile.get_graph_with_ghosts()."""
759
return self.get_parent_map(self.versions())
553
graph_items = self._index.get_graph()
554
return dict(graph_items)
760
555
761
556
def get_sha1(self, version_id):
762
return self.get_sha1s([version_id])[0]
763
764
def get_sha1s(self, version_ids):
765
557
"""See VersionedFile.get_sha1()."""
766
record_map = self._get_record_map(version_ids)
767
# record entry 2 is the 'digest'.
768
return [record_map[v][2] for v in version_ids]
558
version_id = osutils.safe_revision_id(version_id)
559
record_map = self._get_record_map([version_id])
560
method, content, digest, next = record_map[version_id]
561
return digest
769
562
770
563
@staticmethod
771
564
def get_suffixes():
772
565
"""See VersionedFile.get_suffixes()."""
773
566
return [DATA_SUFFIX, INDEX_SUFFIX]
774
567
775
@deprecated_method(one_four)
776
568
def has_ghost(self, version_id):
777
569
"""True if there is a ghost reference in the file to version_id."""
570
version_id = osutils.safe_revision_id(version_id)
778
571
# maybe we have it
779
572
if self.has_version(version_id):
780
573
return False
781
574
# optimisable if needed by memoising the _ghosts set.
782
items = self.get_parent_map(self.versions())
783
for parents in items.itervalues():
575
items = self._index.get_graph()
576
for node, parents in items:
784
577
for parent in parents:
785
if parent == version_id and parent not in items:
786
return True
578
if parent not in self._index._cache:
579
if parent == version_id:
580
return True
787
581
return False
788
582
789
def insert_data_stream(self, (format, data_list, reader_callable)):
790
"""Insert knit records from a data stream into this knit.
791
792
If a version in the stream is already present in this knit, it will not
793
be inserted a second time. It will be checked for consistency with the
794
stored version however, and may cause a KnitCorrupt error to be raised
795
if the data in the stream disagrees with the already stored data.
796
797
:seealso: get_data_stream
798
"""
799
if format != self.get_format_signature():
800
if 'knit' in debug.debug_flags:
801
trace.mutter(
802
'incompatible format signature inserting to %r', self)
803
source = self._knit_from_datastream(
804
(format, data_list, reader_callable))
805
self.join(source)
806
return
807
808
for version_id, options, length, parents in data_list:
809
if self.has_version(version_id):
810
# First check: the list of parents.
811
my_parents = self.get_parents_with_ghosts(version_id)
812
if tuple(my_parents) != tuple(parents):
813
# XXX: KnitCorrupt is not quite the right exception here.
814
raise KnitCorrupt(
815
self.filename,
816
'parents list %r from data stream does not match '
817
'already recorded parents %r for %s'
818
% (parents, my_parents, version_id))
819
820
# Also check the SHA-1 of the fulltext this content will
821
# produce.
822
raw_data = reader_callable(length)
823
my_fulltext_sha1 = self.get_sha1(version_id)
824
df, rec = self._data._parse_record_header(version_id, raw_data)
825
stream_fulltext_sha1 = rec[3]
826
if my_fulltext_sha1 != stream_fulltext_sha1:
827
# Actually, we don't know if it's this knit that's corrupt,
828
# or the data stream we're trying to insert.
829
raise KnitCorrupt(
830
self.filename, 'sha-1 does not match %s' % version_id)
831
else:
832
if 'line-delta' in options:
833
# Make sure that this knit record is actually useful: a
834
# line-delta is no use unless we have its parent.
835
# Fetching from a broken repository with this problem
836
# shouldn't break the target repository.
837
#
838
# See https://bugs.launchpad.net/bzr/+bug/164443
839
if not self._index.has_version(parents[0]):
840
raise KnitCorrupt(
841
self.filename,
842
'line-delta from stream '
843
'for version %s '
844
'references '
845
'missing parent %s\n'
846
'Try running "bzr check" '
847
'on the source repository, and "bzr reconcile" '
848
'if necessary.' %
849
(version_id, parents[0]))
850
self._add_raw_records(
851
[(version_id, options, parents, length)],
852
reader_callable(length))
853
854
def _knit_from_datastream(self, (format, data_list, reader_callable)):
855
"""Create a knit object from a data stream.
856
857
This method exists to allow conversion of data streams that do not
858
match the signature of this knit. Generally it will be slower and use
859
more memory to use this method to insert data, but it will work.
860
861
:seealso: get_data_stream for details on datastreams.
862
:return: A knit versioned file which can be used to join the datastream
863
into self.
864
"""
865
if format == "knit-plain":
866
factory = KnitPlainFactory()
867
elif format == "knit-annotated":
868
factory = KnitAnnotateFactory()
869
else:
870
raise errors.KnitDataStreamUnknown(format)
871
index = _StreamIndex(data_list, self._index)
872
access = _StreamAccess(reader_callable, index, self, factory)
873
return KnitVersionedFile(self.filename, self.transport,
874
factory=factory, index=index, access_method=access)
875
876
583
def versions(self):
877
584
"""See VersionedFile.versions."""
878
if 'evil' in debug.debug_flags:
879
trace.mutter_callsite(2, "versions scales with size of history")
880
585
return self._index.get_versions()
881
586
882
587
def has_version(self, version_id):
883
588
"""See VersionedFile.has_version."""
884
if 'evil' in debug.debug_flags:
885
trace.mutter_callsite(2, "has_version is a LBYL scenario")
589
version_id = osutils.safe_revision_id(version_id)
886
590
return self._index.has_version(version_id)
887
591
888
592
__contains__ = has_version
889
593
890
594
def _merge_annotations(self, content, parents, parent_texts={},
891
delta=None, annotated=None,
892
left_matching_blocks=None):
595
delta=None, annotated=None):
893
596
"""Merge annotations for content. This is done by comparing
894
597
the annotations based on changed to the text.
895
598
"""
896
if left_matching_blocks is not None:
897
delta_seq = diff._PrematchedMatcher(left_matching_blocks)
898
else:
599
if annotated:
899
600
delta_seq = None
900
if annotated:
901
601
for parent_id in parents:
902
602
merge_content = self._get_content(parent_id, parent_texts)
903
if (parent_id == parents[0] and delta_seq is not None):
904
seq = delta_seq
905
else:
906
seq = patiencediff.PatienceSequenceMatcher(
907
None, merge_content.text(), content.text())
603
seq = patiencediff.PatienceSequenceMatcher(
604
None, merge_content.text(), content.text())
605
if delta_seq is None:
606
# setup a delta seq to reuse.
607
delta_seq = seq
908
608
for i, j, n in seq.get_matching_blocks():
909
609
if n == 0:
910
610
continue
911
# this appears to copy (origin, text) pairs across to the
912
# new content for any line that matches the last-checked
913
# parent.
611
# this appears to copy (origin, text) pairs across to the new
612
# content for any line that matches the last-checked parent.
613
# FIXME: save the sequence control data for delta compression
614
# against the most relevant parent rather than rediffing.
914
615
content._lines[j:j+n] = merge_content._lines[i:i+n]
915
616
if delta:
916
if delta_seq is None:
617
if not annotated:
917
618
reference_content = self._get_content(parents[0], parent_texts)
918
619
new_texts = content.text()
919
620
old_texts = reference_content.text()
935
636
936
637
This data is intended to be used for retrieving the knit records.
937
638
938
A dict of version_id to (record_details, index_memo, next, parents) is
639
A dict of version_id to (method, data_pos, data_size, next) is
939
640
returned.
940
641
method is the way referenced data should be applied.
941
index_memo is the handle to pass to the data access to actually get the
942
data
642
data_pos is the position of the data in the knit.
643
data_size is the size of the data in the knit.
943
644
next is the build-parent of the version, or None for fulltexts.
944
parents is the version_ids of the parents of this version
945
645
"""
946
646
component_data = {}
947
pending_components = version_ids
948
while pending_components:
949
build_details = self._index.get_build_details(pending_components)
950
current_components = set(pending_components)
951
pending_components = set()
952
for version_id, details in build_details.iteritems():
953
(index_memo, compression_parent, parents,
954
record_details) = details
955
method = record_details[0]
956
if compression_parent is not None:
957
pending_components.add(compression_parent)
958
component_data[version_id] = (record_details, index_memo,
959
compression_parent)
960
missing = current_components.difference(build_details)
961
if missing:
962
raise errors.RevisionNotPresent(missing.pop(), self.filename)
647
for version_id in version_ids:
648
cursor = version_id
649
650
while cursor is not None and cursor not in component_data:
651
method = self._index.get_method(cursor)
652
if method == 'fulltext':
653
next = None
654
else:
655
next = self.get_parents(cursor)[0]
656
data_pos, data_size = self._index.get_position(cursor)
657
component_data[cursor] = (method, data_pos, data_size, next)
658
cursor = next
963
659
return component_data
964
660
965
661
def _get_content(self, version_id, parent_texts={}):
966
662
"""Returns a content object that makes up the specified
967
663
version."""
664
if not self.has_version(version_id):
665
raise RevisionNotPresent(version_id, self.filename)
666
968
667
cached_version = parent_texts.get(version_id, None)
969
668
if cached_version is not None:
970
if not self.has_version(version_id):
971
raise RevisionNotPresent(version_id, self.filename)
972
669
return cached_version
973
670
974
671
text_map, contents_map = self._get_content_maps([version_id])
978
675
"""Check that all specified versions are present."""
979
676
self._index.check_versions_present(version_ids)
980
677
981
def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts,
982
nostore_sha, random_id, check_content, left_matching_blocks):
678
def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts):
983
679
"""See VersionedFile.add_lines_with_ghosts()."""
984
self._check_add(version_id, lines, random_id, check_content)
985
return self._add(version_id, lines, parents, self.delta,
986
parent_texts, left_matching_blocks, nostore_sha, random_id)
680
self._check_add(version_id, lines)
681
return self._add(version_id, lines[:], parents, self.delta, parent_texts)
987
682
988
def _add_lines(self, version_id, parents, lines, parent_texts,
989
left_matching_blocks, nostore_sha, random_id, check_content):
683
def _add_lines(self, version_id, parents, lines, parent_texts):
990
684
"""See VersionedFile.add_lines."""
991
self._check_add(version_id, lines, random_id, check_content)
685
self._check_add(version_id, lines)
992
686
self._check_versions_present(parents)
993
return self._add(version_id, lines[:], parents, self.delta,
994
parent_texts, left_matching_blocks, nostore_sha, random_id)
687
return self._add(version_id, lines[:], parents, self.delta, parent_texts)
995
688
996
def _check_add(self, version_id, lines, random_id, check_content):
689
def _check_add(self, version_id, lines):
997
690
"""check that version_id and lines are safe to add."""
691
assert self.writable, "knit is not opened for write"
692
### FIXME escape. RBC 20060228
998
693
if contains_whitespace(version_id):
999
694
raise InvalidRevisionId(version_id, self.filename)
1000
695
self.check_not_reserved_id(version_id)
1001
# Technically this could be avoided if we are happy to allow duplicate
1002
# id insertion when other things than bzr core insert texts, but it
1003
# seems useful for folk using the knit api directly to have some safety
1004
# blanket that we can disable.
1005
if not random_id and self.has_version(version_id):
696
if self.has_version(version_id):
1006
697
raise RevisionAlreadyPresent(version_id, self.filename)
1007
if check_content:
1008
self._check_lines_not_unicode(lines)
1009
self._check_lines_are_lines(lines)
698
self._check_lines_not_unicode(lines)
699
self._check_lines_are_lines(lines)
1010
700
1011
def _add(self, version_id, lines, parents, delta, parent_texts,
1012
left_matching_blocks, nostore_sha, random_id):
701
def _add(self, version_id, lines, parents, delta, parent_texts):
1013
702
"""Add a set of lines on top of version specified by parents.
1014
703
1015
704
If delta is true, compress the text as a line-delta against
1017
706
1018
707
Any versions not present will be converted into ghosts.
1019
708
"""
1020
# first thing, if the content is something we don't need to store, find
1021
# that out.
1022
line_bytes = ''.join(lines)
1023
digest = sha_string(line_bytes)
1024
if nostore_sha == digest:
1025
raise errors.ExistingContent
709
# 461 0 6546.0390 43.9100 bzrlib.knit:489(_add)
710
# +400 0 889.4890 418.9790 +bzrlib.knit:192(lower_fulltext)
711
# +461 0 1364.8070 108.8030 +bzrlib.knit:996(add_record)
712
# +461 0 193.3940 41.5720 +bzrlib.knit:898(add_version)
713
# +461 0 134.0590 18.3810 +bzrlib.osutils:361(sha_strings)
714
# +461 0 36.3420 15.4540 +bzrlib.knit:146(make)
715
# +1383 0 8.0370 8.0370 +<len>
716
# +61 0 13.5770 7.9190 +bzrlib.knit:199(lower_line_delta)
717
# +61 0 963.3470 7.8740 +bzrlib.knit:427(_get_content)
718
# +61 0 973.9950 5.2950 +bzrlib.knit:136(line_delta)
719
# +61 0 1918.1800 5.2640 +bzrlib.knit:359(_merge_annotations)
1026
720
1027
721
present_parents = []
722
ghosts = []
1028
723
if parent_texts is None:
1029
724
parent_texts = {}
1030
725
for parent in parents:
1031
if self.has_version(parent):
726
if not self.has_version(parent):
727
ghosts.append(parent)
728
else:
1032
729
present_parents.append(parent)
1033
730
1034
# can only compress against the left most present parent.
1035
if (delta and
1036
(len(present_parents) == 0 or
1037
present_parents[0] != parents[0])):
731
if delta and not len(present_parents):
1038
732
delta = False
1039
733
1040
text_length = len(line_bytes)
734
digest = sha_strings(lines)
1041
735
options = []
1042
736
if lines:
1043
737
if lines[-1][-1] != '\n':
1044
# copy the contents of lines.
1045
lines = lines[:]
1046
738
options.append('no-eol')
1047
739
lines[-1] = lines[-1] + '\n'
1048
line_bytes += '\n'
1049
740
1050
if delta:
741
if len(present_parents) and delta:
1051
742
# To speed the extract of texts the delta chain is limited
1052
743
# to a fixed number of deltas. This should minimize both
1053
744
# I/O and the time spend applying deltas.
1054
745
delta = self._check_should_delta(present_parents)
1055
746
1056
747
assert isinstance(version_id, str)
1057
content = self.factory.make(lines, version_id)
748
lines = self.factory.make(lines, version_id)
1058
749
if delta or (self.factory.annotated and len(present_parents) > 0):
1059
# Merge annotations from parent texts if needed.
1060
delta_hunks = self._merge_annotations(content, present_parents,
1061
parent_texts, delta, self.factory.annotated,
1062
left_matching_blocks)
750
# Merge annotations from parent texts if so is needed.
751
delta_hunks = self._merge_annotations(lines, present_parents, parent_texts,
752
delta, self.factory.annotated)
1063
753
1064
754
if delta:
1065
755
options.append('line-delta')
1066
756
store_lines = self.factory.lower_line_delta(delta_hunks)
1067
size, bytes = self._data._record_to_data(version_id, digest,
1068
store_lines)
1069
757
else:
1070
758
options.append('fulltext')
1071
# isinstance is slower and we have no hierarchy.
1072
if self.factory.__class__ == KnitPlainFactory:
1073
# Use the already joined bytes saving iteration time in
1074
# _record_to_data.
1075
size, bytes = self._data._record_to_data(version_id, digest,
1076
lines, [line_bytes])
1077
else:
1078
# get mixed annotation + content and feed it into the
1079
# serialiser.
1080
store_lines = self.factory.lower_fulltext(content)
1081
size, bytes = self._data._record_to_data(version_id, digest,
1082
store_lines)
759
store_lines = self.factory.lower_fulltext(lines)
1083
760
1084
access_memo = self._data.add_raw_records([size], bytes)[0]
1085
self._index.add_versions(
1086
((version_id, options, access_memo, parents),),
1087
random_id=random_id)
1088
return digest, text_length, content
761
where, size = self._data.add_record(version_id, digest, store_lines)
762
self._index.add_version(version_id, options, where, size, parents)
763
return lines
1089
764
1090
765
def check(self, progress_bar=None):
1091
766
"""See VersionedFile.check()."""
1103
778
def _get_record_map(self, version_ids):
1104
779
"""Produce a dictionary of knit records.
1105
780
1106
:return: {version_id:(record, record_details, digest, next)}
1107
record
1108
data returned from read_records
1109
record_details
1110
opaque information to pass to parse_record
1111
digest
1112
SHA1 digest of the full text after all steps are done
1113
next
1114
build-parent of the version, i.e. the leftmost ancestor.
1115
Will be None if the record is not a delta.
781
The keys are version_ids, the values are tuples of (method, content,
782
digest, next).
783
method is the way the content should be applied.
784
content is a KnitContent object.
785
digest is the SHA1 digest of this version id after all steps are done
786
next is the build-parent of the version, i.e. the leftmost ancestor.
787
If the method is fulltext, next will be None.
1116
788
"""
1117
789
position_map = self._get_components_positions(version_ids)
1118
# c = component_id, r = record_details, i_m = index_memo, n = next
1119
records = [(c, i_m) for c, (r, i_m, n)
1120
in position_map.iteritems()]
790
# c = component_id, m = method, p = position, s = size, n = next
791
records = [(c, p, s) for c, (m, p, s, n) in position_map.iteritems()]
1121
792
record_map = {}
1122
for component_id, record, digest in \
793
for component_id, content, digest in \
1123
794
self._data.read_records_iter(records):
1124
(record_details, index_memo, next) = position_map[component_id]
1125
record_map[component_id] = record, record_details, digest, next
1126
795
method, position, size, next = position_map[component_id]
796
record_map[component_id] = method, content, digest, next
797
1127
798
return record_map
1128
799
1129
800
def get_text(self, version_id):
1135
806
1136
807
def get_line_list(self, version_ids):
1137
808
"""Return the texts of listed versions as a list of strings."""
809
version_ids = [osutils.safe_revision_id(v) for v in version_ids]
1138
810
for version_id in version_ids:
1139
811
self.check_not_reserved_id(version_id)
1140
812
text_map, content_map = self._get_content_maps(version_ids)
1141
813
return [text_map[v] for v in version_ids]
1142
814
1143
_get_lf_split_line_list = get_line_list
1144
1145
815
def _get_content_maps(self, version_ids):
1146
816
"""Produce maps of text and KnitContents
1147
817
1149
819
the requested versions and content_map contains the KnitContents.
1150
820
Both dicts take version_ids as their keys.
1151
821
"""
1152
# FUTURE: This function could be improved for the 'extract many' case
1153
# by tracking each component and only doing the copy when the number of
1154
# children than need to apply delta's to it is > 1 or it is part of the
1155
# final output.
1156
version_ids = list(version_ids)
1157
multiple_versions = len(version_ids) != 1
822
for version_id in version_ids:
823
if not self.has_version(version_id):
824
raise RevisionNotPresent(version_id, self.filename)
1158
825
record_map = self._get_record_map(version_ids)
1159
826
1160
827
text_map = {}
1164
831
components = []
1165
832
cursor = version_id
1166
833
while cursor is not None:
1167
record, record_details, digest, next = record_map[cursor]
1168
components.append((cursor, record, record_details, digest))
834
method, data, digest, next = record_map[cursor]
835
components.append((cursor, method, data, digest))
1169
836
if cursor in content_map:
1170
837
break
1171
838
cursor = next
1172
839
1173
840
content = None
1174
for (component_id, record, record_details,
1175
digest) in reversed(components):
841
for component_id, method, data, digest in reversed(components):
1176
842
if component_id in content_map:
1177
843
content = content_map[component_id]
1178
844
else:
1179
content, delta = self.factory.parse_record(version_id,
1180
record, record_details, content,
1181
copy_base_content=multiple_versions)
1182
if multiple_versions:
1183
content_map[component_id] = content
845
if method == 'fulltext':
846
assert content is None
847
content = self.factory.parse_fulltext(data, version_id)
848
elif method == 'line-delta':
849
delta = self.factory.parse_line_delta(data, version_id)
850
content = content.copy()
851
content._lines = self._apply_delta(content._lines,
852
delta)
853
content_map[component_id] = content
1184
854
1185
content.cleanup_eol(copy_on_mutate=multiple_versions)
855
if 'no-eol' in self._index.get_options(version_id):
856
content = content.copy()
857
line = content._lines[-1][1].rstrip('\n')
858
content._lines[-1] = (content._lines[-1][0], line)
1186
859
final_content[version_id] = content
1187
860
1188
861
# digest here is the digest from the last applied component.
1189
862
text = content.text()
1190
actual_sha = sha_strings(text)
1191
if actual_sha != digest:
1192
raise KnitCorrupt(self.filename,
1193
'\n sha-1 %s'
1194
'\n of reconstructed text does not match'
1195
'\n expected %s'
1196
'\n for version %s' %
1197
(actual_sha, digest, version_id))
1198
text_map[version_id] = text
1199
return text_map, final_content
863
if sha_strings(text) != digest:
864
raise KnitCorrupt(self.filename,
865
'sha-1 does not match %s' % version_id)
866
867
text_map[version_id] = text
868
return text_map, final_content
1200
869
1201
870
def iter_lines_added_or_present_in_versions(self, version_ids=None,
1202
871
pb=None):
1203
872
"""See VersionedFile.iter_lines_added_or_present_in_versions()."""
1204
873
if version_ids is None:
1205
874
version_ids = self.versions()
875
else:
876
version_ids = [osutils.safe_revision_id(v) for v in version_ids]
1206
877
if pb is None:
1207
878
pb = progress.DummyProgress()
1208
879
# we don't care about inclusions, the caller cares.
1217
888
# get a in-component-order queue:
1218
889
for version_id in self.versions():
1219
890
if version_id in requested_versions:
1220
index_memo = self._index.get_position(version_id)
1221
version_id_records.append((version_id, index_memo))
891
data_pos, length = self._index.get_position(version_id)
892
version_id_records.append((version_id, data_pos, length))
1222
893
1223
894
total = len(version_id_records)
1224
895
for version_idx, (version_id, data, sha_value) in \
1231
902
line_iterator = self.factory.get_fulltext_content(data)
1232
903
else:
1233
904
line_iterator = self.factory.get_linedelta_content(data)
1234
# XXX: It might be more efficient to yield (version_id,
1235
# line_iterator) in the future. However for now, this is a simpler
1236
# change to integrate into the rest of the codebase. RBC 20071110
1237
905
for line in line_iterator:
1238
yield line, version_id
906
yield line
1239
907
1240
908
pb.update('Walking content.', total, total)
1241
909
1242
def iter_parents(self, version_ids):
1243
"""Iterate through the parents for many version ids.
1244
1245
:param version_ids: An iterable yielding version_ids.
1246
:return: An iterator that yields (version_id, parents). Requested
1247
version_ids not present in the versioned file are simply skipped.
1248
The order is undefined, allowing for different optimisations in
1249
the underlying implementation.
1250
"""
1251
return self._index.iter_parents(version_ids)
1252
1253
910
def num_versions(self):
1254
911
"""See VersionedFile.num_versions()."""
1255
912
return self._index.num_versions()
1258
915
1259
916
def annotate_iter(self, version_id):
1260
917
"""See VersionedFile.annotate_iter."""
1261
return self.factory.annotate_iter(self, version_id)
1262
1263
def get_parent_map(self, version_ids):
1264
"""See VersionedFile.get_parent_map."""
1265
return self._index.get_parent_map(version_ids)
1266
1267
def get_ancestry(self, versions, topo_sorted=True):
918
version_id = osutils.safe_revision_id(version_id)
919
content = self._get_content(version_id)
920
for origin, text in content.annotate_iter():
921
yield origin, text
922
923
def get_parents(self, version_id):
924
"""See VersionedFile.get_parents."""
925
# perf notes:
926
# optimism counts!
927
# 52554 calls in 1264 872 internal down from 3674
928
version_id = osutils.safe_revision_id(version_id)
929
try:
930
return self._index.get_parents(version_id)
931
except KeyError:
932
raise RevisionNotPresent(version_id, self.filename)
933
934
def get_parents_with_ghosts(self, version_id):
935
"""See VersionedFile.get_parents."""
936
version_id = osutils.safe_revision_id(version_id)
937
try:
938
return self._index.get_parents_with_ghosts(version_id)
939
except KeyError:
940
raise RevisionNotPresent(version_id, self.filename)
941
942
def get_ancestry(self, versions):
1268
943
"""See VersionedFile.get_ancestry."""
1269
944
if isinstance(versions, basestring):
1270
945
versions = [versions]
1271
946
if not versions:
1272
947
return []
1273
return self._index.get_ancestry(versions, topo_sorted)
948
versions = [osutils.safe_revision_id(v) for v in versions]
949
return self._index.get_ancestry(versions)
1274
950
1275
951
def get_ancestry_with_ghosts(self, versions):
1276
952
"""See VersionedFile.get_ancestry_with_ghosts."""
1278
954
versions = [versions]
1279
955
if not versions:
1280
956
return []
957
versions = [osutils.safe_revision_id(v) for v in versions]
1281
958
return self._index.get_ancestry_with_ghosts(versions)
1282
959
960
#@deprecated_method(zero_eight)
961
def walk(self, version_ids):
962
"""See VersionedFile.walk."""
963
# We take the short path here, and extract all relevant texts
964
# and put them in a weave and let that do all the work. Far
965
# from optimal, but is much simpler.
966
# FIXME RB 20060228 this really is inefficient!
967
from bzrlib.weave import Weave
968
969
w = Weave(self.filename)
970
ancestry = self.get_ancestry(version_ids)
971
sorted_graph = topo_sort(self._index.get_graph())
972
version_list = [vid for vid in sorted_graph if vid in ancestry]
973
974
for version_id in version_list:
975
lines = self.get_lines(version_id)
976
w.add_lines(version_id, self.get_parents(version_id), lines)
977
978
for lineno, insert_id, dset, line in w.walk(version_ids):
979
yield lineno, insert_id, dset, line
980
1283
981
def plan_merge(self, ver_a, ver_b):
1284
982
"""See VersionedFile.plan_merge."""
1285
ancestors_b = set(self.get_ancestry(ver_b, topo_sorted=False))
1286
ancestors_a = set(self.get_ancestry(ver_a, topo_sorted=False))
983
ver_a = osutils.safe_revision_id(ver_a)
984
ver_b = osutils.safe_revision_id(ver_b)
985
ancestors_b = set(self.get_ancestry(ver_b))
986
def status_a(revision, text):
987
if revision in ancestors_b:
988
return 'killed-b', text
989
else:
990
return 'new-a', text
991
992
ancestors_a = set(self.get_ancestry(ver_a))
993
def status_b(revision, text):
994
if revision in ancestors_a:
995
return 'killed-a', text
996
else:
997
return 'new-b', text
998
1287
999
annotated_a = self.annotate(ver_a)
1288
1000
annotated_b = self.annotate(ver_b)
1289
return merge._plan_annotate_merge(annotated_a, annotated_b,
1290
ancestors_a, ancestors_b)
1001
plain_a = [t for (a, t) in annotated_a]
1002
plain_b = [t for (a, t) in annotated_b]
1003
blocks = KnitSequenceMatcher(None, plain_a, plain_b).get_matching_blocks()
1004
a_cur = 0
1005
b_cur = 0
1006
for ai, bi, l in blocks:
1007
# process all mismatched sections
1008
# (last mismatched section is handled because blocks always
1009
# includes a 0-length last block)
1010
for revision, text in annotated_a[a_cur:ai]:
1011
yield status_a(revision, text)
1012
for revision, text in annotated_b[b_cur:bi]:
1013
yield status_b(revision, text)
1014
1015
# and now the matched section
1016
a_cur = ai + l
1017
b_cur = bi + l
1018
for text_a, text_b in zip(plain_a[ai:a_cur], plain_b[bi:b_cur]):
1019
assert text_a == text_b
1020
yield "unchanged", text_a
1291
1021
1292
1022
1293
1023
class _KnitComponentFile(object):
1317
1047
raise KnitHeaderError(badline=line,
1318
1048
filename=self._transport.abspath(self._filename))
1319
1049
1050
def commit(self):
1051
"""Commit is a nop."""
1052
1320
1053
def __repr__(self):
1321
1054
return '%s(%s)' % (self.__class__.__name__, self._filename)
1322
1055
1417
1150
try:
1418
1151
# _load_data may raise NoSuchFile if the target knit is
1419
1152
# completely empty.
1420
_load_data(self, fp)
1153
self._load_data(fp)
1421
1154
finally:
1422
1155
fp.close()
1423
1156
except NoSuchFile:
1429
1162
self._transport.put_bytes_non_atomic(
1430
1163
self._filename, self.HEADER, mode=self._file_mode)
1431
1164
1432
def get_ancestry(self, versions, topo_sorted=True):
1165
def _load_data(self, fp):
1166
cache = self._cache
1167
history = self._history
1168
1169
self.check_header(fp)
1170
# readlines reads the whole file at once:
1171
# bad for transports like http, good for local disk
1172
# we save 60 ms doing this one change (
1173
# from calling readline each time to calling
1174
# readlines once.
1175
# probably what we want for nice behaviour on
1176
# http is a incremental readlines that yields, or
1177
# a check for local vs non local indexes,
1178
history_top = len(history) - 1
1179
for line in fp.readlines():
1180
rec = line.split()
1181
if len(rec) < 5 or rec[-1] != ':':
1182
# corrupt line.
1183
# FIXME: in the future we should determine if its a
1184
# short write - and ignore it
1185
# or a different failure, and raise. RBC 20060407
1186
continue
1187
1188
parents = []
1189
for value in rec[4:-1]:
1190
if value[0] == '.':
1191
# uncompressed reference
1192
parent_id = value[1:]
1193
else:
1194
parent_id = history[int(value)]
1195
parents.append(parent_id)
1196
1197
version_id, options, pos, size = rec[:4]
1198
version_id = version_id
1199
1200
# See self._cache_version
1201
# only want the _history index to reference the 1st
1202
# index entry for version_id
1203
if version_id not in cache:
1204
history_top += 1
1205
index = history_top
1206
history.append(version_id)
1207
else:
1208
index = cache[version_id][5]
1209
cache[version_id] = (version_id,
1210
options.split(','),
1211
int(pos),
1212
int(size),
1213
parents,
1214
index)
1215
# end self._cache_version
1216
1217
def get_graph(self):
1218
return [(vid, idx[4]) for vid, idx in self._cache.iteritems()]
1219
1220
def get_ancestry(self, versions):
1433
1221
"""See VersionedFile.get_ancestry."""
1434
1222
# get a graph of all the mentioned versions:
1435
1223
graph = {}
1445
1233
# if not completed and not a ghost
1446
1234
pending.update([p for p in parents if p not in graph])
1447
1235
graph[version] = parents
1448
if not topo_sorted:
1449
return graph.keys()
1450
1236
return topo_sort(graph.items())
1451
1237
1452
1238
def get_ancestry_with_ghosts(self, versions):
1469
1255
graph[version] = parents
1470
1256
return topo_sort(graph.items())
1471
1257
1472
def get_build_details(self, version_ids):
1473
"""Get the method, index_memo and compression parent for version_ids.
1474
1475
Ghosts are omitted from the result.
1476
1477
:param version_ids: An iterable of version_ids.
1478
:return: A dict of version_id:(index_memo, compression_parent,
1479
parents, record_details).
1480
index_memo
1481
opaque structure to pass to read_records to extract the raw
1482
data
1483
compression_parent
1484
Content that this record is built upon, may be None
1485
parents
1486
Logical parents of this node
1487
record_details
1488
extra information about the content which needs to be passed to
1489
Factory.parse_record
1490
"""
1491
result = {}
1492
for version_id in version_ids:
1493
if version_id not in self._cache:
1494
# ghosts are omitted
1495
continue
1496
method = self.get_method(version_id)
1497
parents = self.get_parents_with_ghosts(version_id)
1498
if method == 'fulltext':
1499
compression_parent = None
1500
else:
1501
compression_parent = parents[0]
1502
noeol = 'no-eol' in self.get_options(version_id)
1503
index_memo = self.get_position(version_id)
1504
result[version_id] = (index_memo, compression_parent,
1505
parents, (method, noeol))
1506
return result
1507
1508
def iter_parents(self, version_ids):
1509
"""Iterate through the parents for many version ids.
1510
1511
:param version_ids: An iterable yielding version_ids.
1512
:return: An iterator that yields (version_id, parents). Requested
1513
version_ids not present in the versioned file are simply skipped.
1514
The order is undefined, allowing for different optimisations in
1515
the underlying implementation.
1516
"""
1517
parent_map = self.get_parent_map(version_ids)
1518
parent_map_set = set(parent_map)
1519
unknown_existence = set()
1520
for parents in parent_map.itervalues():
1521
unknown_existence.update(parents)
1522
unknown_existence.difference_update(parent_map_set)
1523
present_parents = set(self.get_parent_map(unknown_existence))
1524
present_parents.update(parent_map_set)
1525
for version_id, parents in parent_map.iteritems():
1526
parents = tuple(parent for parent in parents
1527
if parent in present_parents)
1528
yield version_id, parents
1529
1530
1258
def num_versions(self):
1531
1259
return len(self._history)
1532
1260
1533
1261
__len__ = num_versions
1534
1262
1535
1263
def get_versions(self):
1536
"""Get all the versions in the file. not topologically sorted."""
1537
1264
return self._history
1538
1265
1266
def idx_to_name(self, idx):
1267
return self._history[idx]
1268
1269
def lookup(self, version_id):
1270
assert version_id in self._cache
1271
return self._cache[version_id][5]
1272
1539
1273
def _version_list_to_index(self, versions):
1540
1274
result_list = []
1541
1275
cache = self._cache
1548
1282
result_list.append('.' + version)
1549
1283
return ' '.join(result_list)
1550
1284
1551
def add_version(self, version_id, options, index_memo, parents):
1285
def add_version(self, version_id, options, pos, size, parents):
1552
1286
"""Add a version record to the index."""
1553
self.add_versions(((version_id, options, index_memo, parents),))
1287
self.add_versions(((version_id, options, pos, size, parents),))
1554
1288
1555
def add_versions(self, versions, random_id=False):
1289
def add_versions(self, versions):
1556
1290
"""Add multiple versions to the index.
1557
1291
1558
1292
:param versions: a list of tuples:
1559
1293
(version_id, options, pos, size, parents).
1560
:param random_id: If True the ids being added were randomly generated
1561
and no check for existence will be performed.
1562
1294
"""
1563
1295
lines = []
1564
1296
orig_history = self._history[:]
1565
1297
orig_cache = self._cache.copy()
1566
1298
1567
1299
try:
1568
for version_id, options, (index, pos, size), parents in versions:
1300
for version_id, options, pos, size, parents in versions:
1569
1301
line = "\n%s %s %s %s %s :" % (version_id,
1570
1302
','.join(options),
1571
1303
pos,
1574
1306
assert isinstance(line, str), \
1575
1307
'content must be utf-8 encoded: %r' % (line,)
1576
1308
lines.append(line)
1577
self._cache_version(version_id, options, pos, size, tuple(parents))
1309
self._cache_version(version_id, options, pos, size, parents)
1578
1310
if not self._need_to_create:
1579
1311
self._transport.append_bytes(self._filename, ''.join(lines))
1580
1312
else:
1598
1330
return version_id in self._cache
1599
1331
1600
1332
def get_position(self, version_id):
1601
"""Return details needed to access the version.
1602
1603
.kndx indices do not support split-out data, so return None for the
1604
index field.
1605
1606
:return: a tuple (None, data position, size) to hand to the access
1607
logic to get the record.
1608
"""
1333
"""Return data position and size of specified version."""
1609
1334
entry = self._cache[version_id]
1610
return None, entry[2], entry[3]
1335
return entry[2], entry[3]
1611
1336
1612
1337
def get_method(self, version_id):
1613
1338
"""Return compression method of specified version."""
1614
try:
1615
options = self._cache[version_id][1]
1616
except KeyError:
1617
raise RevisionNotPresent(version_id, self._filename)
1339
options = self._cache[version_id][1]
1618
1340
if 'fulltext' in options:
1619
1341
return 'fulltext'
1620
1342
else:
1623
1345
return 'line-delta'
1624
1346
1625
1347
def get_options(self, version_id):
1626
"""Return a list representing options.
1627
1628
e.g. ['foo', 'bar']
1629
"""
1630
1348
return self._cache[version_id][1]
1631
1349
1632
def get_parent_map(self, version_ids):
1633
"""Passed through to by KnitVersionedFile.get_parent_map."""
1634
result = {}
1635
for version_id in version_ids:
1636
try:
1637
result[version_id] = tuple(self._cache[version_id][4])
1638
except KeyError:
1639
pass
1640
return result
1350
def get_parents(self, version_id):
1351
"""Return parents of specified version ignoring ghosts."""
1352
return [parent for parent in self._cache[version_id][4]
1353
if parent in self._cache]
1641
1354
1642
1355
def get_parents_with_ghosts(self, version_id):
1643
1356
"""Return parents of specified version with ghosts."""
1644
try:
1645
return self.get_parent_map([version_id])[version_id]
1646
except KeyError:
1647
raise RevisionNotPresent(version_id, self)
1357
return self._cache[version_id][4]
1648
1358
1649
1359
def check_versions_present(self, version_ids):
1650
1360
"""Check that all specified versions are present."""
1654
1364
raise RevisionNotPresent(version_id, self._filename)
1655
1365
1656
1366
1657
class KnitGraphIndex(object):
1658
"""A knit index that builds on GraphIndex."""
1659
1660
def __init__(self, graph_index, deltas=False, parents=True, add_callback=None):
1661
"""Construct a KnitGraphIndex on a graph_index.
1662
1663
:param graph_index: An implementation of bzrlib.index.GraphIndex.
1664
:param deltas: Allow delta-compressed records.
1665
:param add_callback: If not None, allow additions to the index and call
1666
this callback with a list of added GraphIndex nodes:
1667
[(node, value, node_refs), ...]
1668
:param parents: If True, record knits parents, if not do not record
1669
parents.
1670
"""
1671
self._graph_index = graph_index
1672
self._deltas = deltas
1673
self._add_callback = add_callback
1674
self._parents = parents
1675
if deltas and not parents:
1676
raise KnitCorrupt(self, "Cannot do delta compression without "
1677
"parent tracking.")
1678
1679
def _get_entries(self, keys, check_present=False):
1680
"""Get the entries for keys.
1681
1682
:param keys: An iterable of index keys, - 1-tuples.
1683
"""
1684
keys = set(keys)
1685
found_keys = set()
1686
if self._parents:
1687
for node in self._graph_index.iter_entries(keys):
1688
yield node
1689
found_keys.add(node[1])
1690
else:
1691
# adapt parentless index to the rest of the code.
1692
for node in self._graph_index.iter_entries(keys):
1693
yield node[0], node[1], node[2], ()
1694
found_keys.add(node[1])
1695
if check_present:
1696
missing_keys = keys.difference(found_keys)
1697
if missing_keys:
1698
raise RevisionNotPresent(missing_keys.pop(), self)
1699
1700
def _present_keys(self, version_ids):
1701
return set([
1702
node[1] for node in self._get_entries(version_ids)])
1703
1704
def _parentless_ancestry(self, versions):
1705
"""Honour the get_ancestry API for parentless knit indices."""
1706
wanted_keys = self._version_ids_to_keys(versions)
1707
present_keys = self._present_keys(wanted_keys)
1708
missing = set(wanted_keys).difference(present_keys)
1709
if missing:
1710
raise RevisionNotPresent(missing.pop(), self)
1711
return list(self._keys_to_version_ids(present_keys))
1712
1713
def get_ancestry(self, versions, topo_sorted=True):
1714
"""See VersionedFile.get_ancestry."""
1715
if not self._parents:
1716
return self._parentless_ancestry(versions)
1717
# XXX: This will do len(history) index calls - perhaps
1718
# it should be altered to be a index core feature?
1719
# get a graph of all the mentioned versions:
1720
graph = {}
1721
ghosts = set()
1722
versions = self._version_ids_to_keys(versions)
1723
pending = set(versions)
1724
while pending:
1725
# get all pending nodes
1726
this_iteration = pending
1727
new_nodes = self._get_entries(this_iteration)
1728
found = set()
1729
pending = set()
1730
for (index, key, value, node_refs) in new_nodes:
1731
# dont ask for ghosties - otherwise
1732
# we we can end up looping with pending
1733
# being entirely ghosted.
1734
graph[key] = [parent for parent in node_refs[0]
1735
if parent not in ghosts]
1736
# queue parents
1737
for parent in graph[key]:
1738
# dont examine known nodes again
1739
if parent in graph:
1740
continue
1741
pending.add(parent)
1742
found.add(key)
1743
ghosts.update(this_iteration.difference(found))
1744
if versions.difference(graph):
1745
raise RevisionNotPresent(versions.difference(graph).pop(), self)
1746
if topo_sorted:
1747
result_keys = topo_sort(graph.items())
1748
else:
1749
result_keys = graph.iterkeys()
1750
return [key[0] for key in result_keys]
1751
1752
def get_ancestry_with_ghosts(self, versions):
1753
"""See VersionedFile.get_ancestry."""
1754
if not self._parents:
1755
return self._parentless_ancestry(versions)
1756
# XXX: This will do len(history) index calls - perhaps
1757
# it should be altered to be a index core feature?
1758
# get a graph of all the mentioned versions:
1759
graph = {}
1760
versions = self._version_ids_to_keys(versions)
1761
pending = set(versions)
1762
while pending:
1763
# get all pending nodes
1764
this_iteration = pending
1765
new_nodes = self._get_entries(this_iteration)
1766
pending = set()
1767
for (index, key, value, node_refs) in new_nodes:
1768
graph[key] = node_refs[0]
1769
# queue parents
1770
for parent in graph[key]:
1771
# dont examine known nodes again
1772
if parent in graph:
1773
continue
1774
pending.add(parent)
1775
missing_versions = this_iteration.difference(graph)
1776
missing_needed = versions.intersection(missing_versions)
1777
if missing_needed:
1778
raise RevisionNotPresent(missing_needed.pop(), self)
1779
for missing_version in missing_versions:
1780
# add a key, no parents
1781
graph[missing_version] = []
1782
pending.discard(missing_version) # don't look for it
1783
result_keys = topo_sort(graph.items())
1784
return [key[0] for key in result_keys]
1785
1786
def get_build_details(self, version_ids):
1787
"""Get the method, index_memo and compression parent for version_ids.
1788
1789
Ghosts are omitted from the result.
1790
1791
:param version_ids: An iterable of version_ids.
1792
:return: A dict of version_id:(index_memo, compression_parent,
1793
parents, record_details).
1794
index_memo
1795
opaque structure to pass to read_records to extract the raw
1796
data
1797
compression_parent
1798
Content that this record is built upon, may be None
1799
parents
1800
Logical parents of this node
1801
record_details
1802
extra information about the content which needs to be passed to
1803
Factory.parse_record
1804
"""
1805
result = {}
1806
entries = self._get_entries(self._version_ids_to_keys(version_ids), True)
1807
for entry in entries:
1808
version_id = self._keys_to_version_ids((entry[1],))[0]
1809
if not self._parents:
1810
parents = ()
1811
else:
1812
parents = self._keys_to_version_ids(entry[3][0])
1813
if not self._deltas:
1814
compression_parent = None
1815
else:
1816
compression_parent_key = self._compression_parent(entry)
1817
if compression_parent_key:
1818
compression_parent = self._keys_to_version_ids(
1819
(compression_parent_key,))[0]
1820
else:
1821
compression_parent = None
1822
noeol = (entry[2][0] == 'N')
1823
if compression_parent:
1824
method = 'line-delta'
1825
else:
1826
method = 'fulltext'
1827
result[version_id] = (self._node_to_position(entry),
1828
compression_parent, parents,
1829
(method, noeol))
1830
return result
1831
1832
def _compression_parent(self, an_entry):
1833
# return the key that an_entry is compressed against, or None
1834
# Grab the second parent list (as deltas implies parents currently)
1835
compression_parents = an_entry[3][1]
1836
if not compression_parents:
1837
return None
1838
assert len(compression_parents) == 1
1839
return compression_parents[0]
1840
1841
def _get_method(self, node):
1842
if not self._deltas:
1843
return 'fulltext'
1844
if self._compression_parent(node):
1845
return 'line-delta'
1846
else:
1847
return 'fulltext'
1848
1849
def iter_parents(self, version_ids):
1850
"""Iterate through the parents for many version ids.
1851
1852
:param version_ids: An iterable yielding version_ids.
1853
:return: An iterator that yields (version_id, parents). Requested
1854
version_ids not present in the versioned file are simply skipped.
1855
The order is undefined, allowing for different optimisations in
1856
the underlying implementation.
1857
"""
1858
if self._parents:
1859
all_nodes = set(self._get_entries(self._version_ids_to_keys(version_ids)))
1860
all_parents = set()
1861
present_parents = set()
1862
for node in all_nodes:
1863
all_parents.update(node[3][0])
1864
# any node we are querying must be present
1865
present_parents.add(node[1])
1866
unknown_parents = all_parents.difference(present_parents)
1867
present_parents.update(self._present_keys(unknown_parents))
1868
for node in all_nodes:
1869
parents = []
1870
for parent in node[3][0]:
1871
if parent in present_parents:
1872
parents.append(parent[0])
1873
yield node[1][0], tuple(parents)
1874
else:
1875
for node in self._get_entries(self._version_ids_to_keys(version_ids)):
1876
yield node[1][0], ()
1877
1878
def num_versions(self):
1879
return len(list(self._graph_index.iter_all_entries()))
1880
1881
__len__ = num_versions
1882
1883
def get_versions(self):
1884
"""Get all the versions in the file. not topologically sorted."""
1885
return [node[1][0] for node in self._graph_index.iter_all_entries()]
1886
1887
def has_version(self, version_id):
1888
"""True if the version is in the index."""
1889
return len(self._present_keys(self._version_ids_to_keys([version_id]))) == 1
1890
1891
def _keys_to_version_ids(self, keys):
1892
return tuple(key[0] for key in keys)
1893
1894
def get_position(self, version_id):
1895
"""Return details needed to access the version.
1896
1897
:return: a tuple (index, data position, size) to hand to the access
1898
logic to get the record.
1899
"""
1900
node = self._get_node(version_id)
1901
return self._node_to_position(node)
1902
1903
def _node_to_position(self, node):
1904
"""Convert an index value to position details."""
1905
bits = node[2][1:].split(' ')
1906
return node[0], int(bits[0]), int(bits[1])
1907
1908
def get_method(self, version_id):
1909
"""Return compression method of specified version."""
1910
return self._get_method(self._get_node(version_id))
1911
1912
def _get_node(self, version_id):
1913
try:
1914
return list(self._get_entries(self._version_ids_to_keys([version_id])))[0]
1915
except IndexError:
1916
raise RevisionNotPresent(version_id, self)
1917
1918
def get_options(self, version_id):
1919
"""Return a list representing options.
1920
1921
e.g. ['foo', 'bar']
1922
"""
1923
node = self._get_node(version_id)
1924
options = [self._get_method(node)]
1925
if node[2][0] == 'N':
1926
options.append('no-eol')
1927
return options
1928
1929
def get_parent_map(self, version_ids):
1930
"""Passed through to by KnitVersionedFile.get_parent_map."""
1931
nodes = self._get_entries(self._version_ids_to_keys(version_ids))
1932
result = {}
1933
if self._parents:
1934
for node in nodes:
1935
result[node[1][0]] = self._keys_to_version_ids(node[3][0])
1936
else:
1937
for node in nodes:
1938
result[node[1][0]] = ()
1939
return result
1940
1941
def get_parents_with_ghosts(self, version_id):
1942
"""Return parents of specified version with ghosts."""
1943
try:
1944
return self.get_parent_map([version_id])[version_id]
1945
except KeyError:
1946
raise RevisionNotPresent(version_id, self)
1947
1948
def check_versions_present(self, version_ids):
1949
"""Check that all specified versions are present."""
1950
keys = self._version_ids_to_keys(version_ids)
1951
present = self._present_keys(keys)
1952
missing = keys.difference(present)
1953
if missing:
1954
raise RevisionNotPresent(missing.pop(), self)
1955
1956
def add_version(self, version_id, options, access_memo, parents):
1957
"""Add a version record to the index."""
1958
return self.add_versions(((version_id, options, access_memo, parents),))
1959
1960
def add_versions(self, versions, random_id=False):
1961
"""Add multiple versions to the index.
1962
1963
This function does not insert data into the Immutable GraphIndex
1964
backing the KnitGraphIndex, instead it prepares data for insertion by
1965
the caller and checks that it is safe to insert then calls
1966
self._add_callback with the prepared GraphIndex nodes.
1967
1968
:param versions: a list of tuples:
1969
(version_id, options, pos, size, parents).
1970
:param random_id: If True the ids being added were randomly generated
1971
and no check for existence will be performed.
1972
"""
1973
if not self._add_callback:
1974
raise errors.ReadOnlyError(self)
1975
# we hope there are no repositories with inconsistent parentage
1976
# anymore.
1977
# check for dups
1978
1979
keys = {}
1980
for (version_id, options, access_memo, parents) in versions:
1981
index, pos, size = access_memo
1982
key = (version_id, )
1983
parents = tuple((parent, ) for parent in parents)
1984
if 'no-eol' in options:
1985
value = 'N'
1986
else:
1987
value = ' '
1988
value += "%d %d" % (pos, size)
1989
if not self._deltas:
1990
if 'line-delta' in options:
1991
raise KnitCorrupt(self, "attempt to add line-delta in non-delta knit")
1992
if self._parents:
1993
if self._deltas:
1994
if 'line-delta' in options:
1995
node_refs = (parents, (parents[0],))
1996
else:
1997
node_refs = (parents, ())
1998
else:
1999
node_refs = (parents, )
2000
else:
2001
if parents:
2002
raise KnitCorrupt(self, "attempt to add node with parents "
2003
"in parentless index.")
2004
node_refs = ()
2005
keys[key] = (value, node_refs)
2006
if not random_id:
2007
present_nodes = self._get_entries(keys)
2008
for (index, key, value, node_refs) in present_nodes:
2009
if (value, node_refs) != keys[key]:
2010
raise KnitCorrupt(self, "inconsistent details in add_versions"
2011
": %s %s" % ((value, node_refs), keys[key]))
2012
del keys[key]
2013
result = []
2014
if self._parents:
2015
for key, (value, node_refs) in keys.iteritems():
2016
result.append((key, value, node_refs))
2017
else:
2018
for key, (value, node_refs) in keys.iteritems():
2019
result.append((key, value))
2020
self._add_callback(result)
2021
2022
def _version_ids_to_keys(self, version_ids):
2023
return set((version_id, ) for version_id in version_ids)
2024
2025
2026
class _KnitAccess(object):
2027
"""Access to knit records in a .knit file."""
2028
2029
def __init__(self, transport, filename, _file_mode, _dir_mode,
2030
_need_to_create, _create_parent_dir):
2031
"""Create a _KnitAccess for accessing and inserting data.
2032
2033
:param transport: The transport the .knit is located on.
2034
:param filename: The filename of the .knit.
2035
"""
2036
self._transport = transport
2037
self._filename = filename
2038
self._file_mode = _file_mode
2039
self._dir_mode = _dir_mode
2040
self._need_to_create = _need_to_create
2041
self._create_parent_dir = _create_parent_dir
2042
2043
def add_raw_records(self, sizes, raw_data):
2044
"""Add raw knit bytes to a storage area.
2045
2046
The data is spooled to whereever the access method is storing data.
2047
2048
:param sizes: An iterable containing the size of each raw data segment.
2049
:param raw_data: A bytestring containing the data.
2050
:return: A list of memos to retrieve the record later. Each memo is a
2051
tuple - (index, pos, length), where the index field is always None
2052
for the .knit access method.
2053
"""
2054
assert type(raw_data) == str, \
2055
'data must be plain bytes was %s' % type(raw_data)
2056
if not self._need_to_create:
2057
base = self._transport.append_bytes(self._filename, raw_data)
2058
else:
2059
self._transport.put_bytes_non_atomic(self._filename, raw_data,
2060
create_parent_dir=self._create_parent_dir,
2061
mode=self._file_mode,
2062
dir_mode=self._dir_mode)
2063
self._need_to_create = False
2064
base = 0
2065
result = []
2066
for size in sizes:
2067
result.append((None, base, size))
2068
base += size
2069
return result
2070
2071
def create(self):
2072
"""IFF this data access has its own storage area, initialise it.
2073
2074
:return: None.
2075
"""
2076
self._transport.put_bytes_non_atomic(self._filename, '',
2077
mode=self._file_mode)
2078
2079
def open_file(self):
2080
"""IFF this data access can be represented as a single file, open it.
2081
2082
For knits that are not mapped to a single file on disk this will
2083
always return None.
2084
2085
:return: None or a file handle.
2086
"""
2087
try:
2088
return self._transport.get(self._filename)
2089
except NoSuchFile:
2090
pass
2091
return None
2092
2093
def get_raw_records(self, memos_for_retrieval):
2094
"""Get the raw bytes for a records.
2095
2096
:param memos_for_retrieval: An iterable containing the (index, pos,
2097
length) memo for retrieving the bytes. The .knit method ignores
2098
the index as there is always only a single file.
2099
:return: An iterator over the bytes of the records.
2100
"""
2101
read_vector = [(pos, size) for (index, pos, size) in memos_for_retrieval]
2102
for pos, data in self._transport.readv(self._filename, read_vector):
2103
yield data
2104
2105
2106
class _PackAccess(object):
2107
"""Access to knit records via a collection of packs."""
2108
2109
def __init__(self, index_to_packs, writer=None):
2110
"""Create a _PackAccess object.
2111
2112
:param index_to_packs: A dict mapping index objects to the transport
2113
and file names for obtaining data.
2114
:param writer: A tuple (pack.ContainerWriter, write_index) which
2115
contains the pack to write, and the index that reads from it will
2116
be associated with.
2117
"""
2118
if writer:
2119
self.container_writer = writer[0]
2120
self.write_index = writer[1]
2121
else:
2122
self.container_writer = None
2123
self.write_index = None
2124
self.indices = index_to_packs
2125
2126
def add_raw_records(self, sizes, raw_data):
2127
"""Add raw knit bytes to a storage area.
2128
2129
The data is spooled to the container writer in one bytes-record per
2130
raw data item.
2131
2132
:param sizes: An iterable containing the size of each raw data segment.
2133
:param raw_data: A bytestring containing the data.
2134
:return: A list of memos to retrieve the record later. Each memo is a
2135
tuple - (index, pos, length), where the index field is the
2136
write_index object supplied to the PackAccess object.
2137
"""
2138
assert type(raw_data) == str, \
2139
'data must be plain bytes was %s' % type(raw_data)
2140
result = []
2141
offset = 0
2142
for size in sizes:
2143
p_offset, p_length = self.container_writer.add_bytes_record(
2144
raw_data[offset:offset+size], [])
2145
offset += size
2146
result.append((self.write_index, p_offset, p_length))
2147
return result
2148
2149
def create(self):
2150
"""Pack based knits do not get individually created."""
2151
2152
def get_raw_records(self, memos_for_retrieval):
2153
"""Get the raw bytes for a records.
2154
2155
:param memos_for_retrieval: An iterable containing the (index, pos,
2156
length) memo for retrieving the bytes. The Pack access method
2157
looks up the pack to use for a given record in its index_to_pack
2158
map.
2159
:return: An iterator over the bytes of the records.
2160
"""
2161
# first pass, group into same-index requests
2162
request_lists = []
2163
current_index = None
2164
for (index, offset, length) in memos_for_retrieval:
2165
if current_index == index:
2166
current_list.append((offset, length))
2167
else:
2168
if current_index is not None:
2169
request_lists.append((current_index, current_list))
2170
current_index = index
2171
current_list = [(offset, length)]
2172
# handle the last entry
2173
if current_index is not None:
2174
request_lists.append((current_index, current_list))
2175
for index, offsets in request_lists:
2176
transport, path = self.indices[index]
2177
reader = pack.make_readv_reader(transport, path, offsets)
2178
for names, read_func in reader.iter_records():
2179
yield read_func(None)
2180
2181
def open_file(self):
2182
"""Pack based knits have no single file."""
2183
return None
2184
2185
def set_writer(self, writer, index, (transport, packname)):
2186
"""Set a writer to use for adding data."""
2187
if index is not None:
2188
self.indices[index] = (transport, packname)
2189
self.container_writer = writer
2190
self.write_index = index
2191
2192
2193
class _StreamAccess(object):
2194
"""A Knit Access object that provides data from a datastream.
2195
2196
It also provides a fallback to present as unannotated data, annotated data
2197
from a *backing* access object.
2198
2199
This is triggered by a index_memo which is pointing to a different index
2200
than this was constructed with, and is used to allow extracting full
2201
unannotated texts for insertion into annotated knits.
2202
"""
2203
2204
def __init__(self, reader_callable, stream_index, backing_knit,
2205
orig_factory):
2206
"""Create a _StreamAccess object.
2207
2208
:param reader_callable: The reader_callable from the datastream.
2209
This is called to buffer all the data immediately, for
2210
random access.
2211
:param stream_index: The index the data stream this provides access to
2212
which will be present in native index_memo's.
2213
:param backing_knit: The knit object that will provide access to
2214
annotated texts which are not available in the stream, so as to
2215
create unannotated texts.
2216
:param orig_factory: The original content factory used to generate the
2217
stream. This is used for checking whether the thunk code for
2218
supporting _copy_texts will generate the correct form of data.
2219
"""
2220
self.data = reader_callable(None)
2221
self.stream_index = stream_index
2222
self.backing_knit = backing_knit
2223
self.orig_factory = orig_factory
2224
2225
def get_raw_records(self, memos_for_retrieval):
2226
"""Get the raw bytes for a records.
2227
2228
:param memos_for_retrieval: An iterable of memos from the
2229
_StreamIndex object identifying bytes to read; for these classes
2230
they are (from_backing_knit, index, start, end) and can point to
2231
either the backing knit or streamed data.
2232
:return: An iterator yielding a byte string for each record in
2233
memos_for_retrieval.
2234
"""
2235
# use a generator for memory friendliness
2236
for from_backing_knit, version_id, start, end in memos_for_retrieval:
2237
if not from_backing_knit:
2238
assert version_id is self.stream_index
2239
yield self.data[start:end]
2240
continue
2241
# we have been asked to thunk. This thunking only occurs when
2242
# we are obtaining plain texts from an annotated backing knit
2243
# so that _copy_texts will work.
2244
# We could improve performance here by scanning for where we need
2245
# to do this and using get_line_list, then interleaving the output
2246
# as desired. However, for now, this is sufficient.
2247
if self.orig_factory.__class__ != KnitPlainFactory:
2248
raise errors.KnitCorrupt(
2249
self, 'Bad thunk request %r cannot be backed by %r' %
2250
(version_id, self.orig_factory))
2251
lines = self.backing_knit.get_lines(version_id)
2252
line_bytes = ''.join(lines)
2253
digest = sha_string(line_bytes)
2254
# the packed form of the fulltext always has a trailing newline,
2255
# even if the actual text does not, unless the file is empty. the
2256
# record options including the noeol flag are passed through by
2257
# _StreamIndex, so this is safe.
2258
if lines:
2259
if lines[-1][-1] != '\n':
2260
lines[-1] = lines[-1] + '\n'
2261
line_bytes += '\n'
2262
# We want plain data, because we expect to thunk only to allow text
2263
# extraction.
2264
size, bytes = self.backing_knit._data._record_to_data(version_id,
2265
digest, lines, line_bytes)
2266
yield bytes
2267
2268
2269
class _StreamIndex(object):
2270
"""A Knit Index object that uses the data map from a datastream."""
2271
2272
def __init__(self, data_list, backing_index):
2273
"""Create a _StreamIndex object.
2274
2275
:param data_list: The data_list from the datastream.
2276
:param backing_index: The index which will supply values for nodes
2277
referenced outside of this stream.
2278
"""
2279
self.data_list = data_list
2280
self.backing_index = backing_index
2281
self._by_version = {}
2282
pos = 0
2283
for key, options, length, parents in data_list:
2284
self._by_version[key] = options, (pos, pos + length), parents
2285
pos += length
2286
2287
def get_ancestry(self, versions, topo_sorted):
2288
"""Get an ancestry list for versions."""
2289
if topo_sorted:
2290
# Not needed for basic joins
2291
raise NotImplementedError(self.get_ancestry)
2292
# get a graph of all the mentioned versions:
2293
# Little ugly - basically copied from KnitIndex, but don't want to
2294
# accidentally incorporate too much of that index's code.
2295
ancestry = set()
2296
pending = set(versions)
2297
cache = self._by_version
2298
while pending:
2299
version = pending.pop()
2300
# trim ghosts
2301
try:
2302
parents = [p for p in cache[version][2] if p in cache]
2303
except KeyError:
2304
raise RevisionNotPresent(version, self)
2305
# if not completed and not a ghost
2306
pending.update([p for p in parents if p not in ancestry])
2307
ancestry.add(version)
2308
return list(ancestry)
2309
2310
def get_build_details(self, version_ids):
2311
"""Get the method, index_memo and compression parent for version_ids.
2312
2313
Ghosts are omitted from the result.
2314
2315
:param version_ids: An iterable of version_ids.
2316
:return: A dict of version_id:(index_memo, compression_parent,
2317
parents, record_details).
2318
index_memo
2319
opaque memo that can be passed to _StreamAccess.read_records
2320
to extract the raw data; for these classes it is
2321
(from_backing_knit, index, start, end)
2322
compression_parent
2323
Content that this record is built upon, may be None
2324
parents
2325
Logical parents of this node
2326
record_details
2327
extra information about the content which needs to be passed to
2328
Factory.parse_record
2329
"""
2330
result = {}
2331
for version_id in version_ids:
2332
try:
2333
method = self.get_method(version_id)
2334
except errors.RevisionNotPresent:
2335
# ghosts are omitted
2336
continue
2337
parent_ids = self.get_parents_with_ghosts(version_id)
2338
noeol = ('no-eol' in self.get_options(version_id))
2339
index_memo = self.get_position(version_id)
2340
from_backing_knit = index_memo[0]
2341
if from_backing_knit:
2342
# texts retrieved from the backing knit are always full texts
2343
method = 'fulltext'
2344
if method == 'fulltext':
2345
compression_parent = None
2346
else:
2347
compression_parent = parent_ids[0]
2348
result[version_id] = (index_memo, compression_parent,
2349
parent_ids, (method, noeol))
2350
return result
2351
2352
def get_method(self, version_id):
2353
"""Return compression method of specified version."""
2354
options = self.get_options(version_id)
2355
if 'fulltext' in options:
2356
return 'fulltext'
2357
elif 'line-delta' in options:
2358
return 'line-delta'
2359
else:
2360
raise errors.KnitIndexUnknownMethod(self, options)
2361
2362
def get_options(self, version_id):
2363
"""Return a list representing options.
2364
2365
e.g. ['foo', 'bar']
2366
"""
2367
try:
2368
return self._by_version[version_id][0]
2369
except KeyError:
2370
options = list(self.backing_index.get_options(version_id))
2371
if 'fulltext' in options:
2372
pass
2373
elif 'line-delta' in options:
2374
# Texts from the backing knit are always returned from the stream
2375
# as full texts
2376
options.remove('line-delta')
2377
options.append('fulltext')
2378
else:
2379
raise errors.KnitIndexUnknownMethod(self, options)
2380
return tuple(options)
2381
2382
def get_parent_map(self, version_ids):
2383
"""Passed through to by KnitVersionedFile.get_parent_map."""
2384
result = {}
2385
pending_ids = set()
2386
for version_id in version_ids:
2387
try:
2388
result[version_id] = self._by_version[version_id][2]
2389
except KeyError:
2390
pending_ids.add(version_id)
2391
result.update(self.backing_index.get_parent_map(pending_ids))
2392
return result
2393
2394
def get_parents_with_ghosts(self, version_id):
2395
"""Return parents of specified version with ghosts."""
2396
try:
2397
return self.get_parent_map([version_id])[version_id]
2398
except KeyError:
2399
raise RevisionNotPresent(version_id, self)
2400
2401
def get_position(self, version_id):
2402
"""Return details needed to access the version.
2403
2404
_StreamAccess has the data as a big array, so we return slice
2405
coordinates into that (as index_memo's are opaque outside the
2406
index and matching access class).
2407
2408
:return: a tuple (from_backing_knit, index, start, end) that can
2409
be passed e.g. to get_raw_records.
2410
If from_backing_knit is False, index will be self, otherwise it
2411
will be a version id.
2412
"""
2413
try:
2414
start, end = self._by_version[version_id][1]
2415
return False, self, start, end
2416
except KeyError:
2417
# Signal to the access object to handle this from the backing knit.
2418
return (True, version_id, None, None)
2419
2420
def get_versions(self):
2421
"""Get all the versions in the stream."""
2422
return self._by_version.keys()
2423
2424
def iter_parents(self, version_ids):
2425
"""Iterate through the parents for many version ids.
2426
2427
:param version_ids: An iterable yielding version_ids.
2428
:return: An iterator that yields (version_id, parents). Requested
2429
version_ids not present in the versioned file are simply skipped.
2430
The order is undefined, allowing for different optimisations in
2431
the underlying implementation.
2432
"""
2433
result = []
2434
for version in version_ids:
2435
try:
2436
result.append((version, self._by_version[version][2]))
2437
except KeyError:
2438
pass
2439
return result
2440
2441
2442
class _KnitData(object):
2443
"""Manage extraction of data from a KnitAccess, caching and decompressing.
2444
2445
The KnitData class provides the logic for parsing and using knit records,
2446
making use of an access method for the low level read and write operations.
2447
"""
2448
2449
def __init__(self, access):
2450
"""Create a KnitData object.
2451
2452
:param access: The access method to use. Access methods such as
2453
_KnitAccess manage the insertion of raw records and the subsequent
2454
retrieval of the same.
2455
"""
2456
self._access = access
1367
class _KnitData(_KnitComponentFile):
1368
"""Contents of the knit data file"""
1369
1370
def __init__(self, transport, filename, mode, create=False, file_mode=None,
1371
create_parent_dir=False, delay_create=False,
1372
dir_mode=None):
1373
_KnitComponentFile.__init__(self, transport, filename, mode,
1374
file_mode=file_mode,
1375
create_parent_dir=create_parent_dir,
1376
dir_mode=dir_mode)
2457
1377
self._checked = False
2458
1378
# TODO: jam 20060713 conceptually, this could spill to disk
2459
1379
# if the cached size gets larger than a certain amount
2461
1381
# a simple dictionary
2462
1382
self._cache = {}
2463
1383
self._do_cache = False
1384
if create:
1385
if delay_create:
1386
self._need_to_create = create
1387
else:
1388
self._transport.put_bytes_non_atomic(self._filename, '',
1389
mode=self._file_mode)
2464
1390
2465
1391
def enable_cache(self):
2466
1392
"""Enable caching of reads."""
2472
1398
self._cache = {}
2473
1399
2474
1400
def _open_file(self):
2475
return self._access.open_file()
1401
try:
1402
return self._transport.get(self._filename)
1403
except NoSuchFile:
1404
pass
1405
return None
2476
1406
2477
def _record_to_data(self, version_id, digest, lines, dense_lines=None):
1407
def _record_to_data(self, version_id, digest, lines):
2478
1408
"""Convert version_id, digest, lines into a raw data block.
2479
1409
2480
:param dense_lines: The bytes of lines but in a denser form. For
2481
instance, if lines is a list of 1000 bytestrings each ending in \n,
2482
dense_lines may be a list with one line in it, containing all the
2483
1000's lines and their \n's. Using dense_lines if it is already
2484
known is a win because the string join to create bytes in this
2485
function spends less time resizing the final string.
2486
1410
:return: (len, a StringIO instance with the raw data ready to read.)
2487
1411
"""
2488
# Note: using a string copy here increases memory pressure with e.g.
2489
# ISO's, but it is about 3 seconds faster on a 1.2Ghz intel machine
2490
# when doing the initial commit of a mozilla tree. RBC 20070921
2491
bytes = ''.join(chain(
1412
sio = StringIO()
1413
data_file = GzipFile(None, mode='wb', fileobj=sio)
1414
1415
assert isinstance(version_id, str)
1416
data_file.writelines(chain(
2492
1417
["version %s %d %s\n" % (version_id,
2493
1418
len(lines),
2494
1419
digest)],
2495
dense_lines or lines,
1420
lines,
2496
1421
["end %s\n" % version_id]))
2497
assert bytes.__class__ == str
2498
compressed_bytes = bytes_to_gzip(bytes)
2499
return len(compressed_bytes), compressed_bytes
2500
2501
def add_raw_records(self, sizes, raw_data):
1422
data_file.close()
1423
length= sio.tell()
1424
1425
sio.seek(0)
1426
return length, sio
1427
1428
def add_raw_record(self, raw_data):
2502
1429
"""Append a prepared record to the data file.
2503
1430
2504
:param sizes: An iterable containing the size of each raw data segment.
2505
:param raw_data: A bytestring containing the data.
2506
:return: a list of index data for the way the data was stored.
2507
See the access method add_raw_records documentation for more
2508
details.
1431
:return: the offset in the data file raw_data was written.
2509
1432
"""
2510
return self._access.add_raw_records(sizes, raw_data)
1433
assert isinstance(raw_data, str), 'data must be plain bytes'
1434
if not self._need_to_create:
1435
return self._transport.append_bytes(self._filename, raw_data)
1436
else:
1437
self._transport.put_bytes_non_atomic(self._filename, raw_data,
1438
create_parent_dir=self._create_parent_dir,
1439
mode=self._file_mode,
1440
dir_mode=self._dir_mode)
1441
self._need_to_create = False
1442
return 0
2511
1443
1444
def add_record(self, version_id, digest, lines):
1445
"""Write new text record to disk. Returns the position in the
1446
file where it was written."""
1447
size, sio = self._record_to_data(version_id, digest, lines)
1448
# write to disk
1449
if not self._need_to_create:
1450
start_pos = self._transport.append_file(self._filename, sio)
1451
else:
1452
self._transport.put_file_non_atomic(self._filename, sio,
1453
create_parent_dir=self._create_parent_dir,
1454
mode=self._file_mode,
1455
dir_mode=self._dir_mode)
1456
self._need_to_create = False
1457
start_pos = 0
1458
if self._do_cache:
1459
self._cache[version_id] = sio.getvalue()
1460
return start_pos, size
1461
2512
1462
def _parse_record_header(self, version_id, raw_data):
2513
1463
"""Parse a record header for consistency.
2514
1464
2519
1469
try:
2520
1470
rec = self._check_header(version_id, df.readline())
2521
1471
except Exception, e:
2522
raise KnitCorrupt(self._access,
1472
raise KnitCorrupt(self._filename,
2523
1473
"While reading {%s} got %s(%s)"
2524
1474
% (version_id, e.__class__.__name__, str(e)))
2525
1475
return df, rec
2527
1477
def _check_header(self, version_id, line):
2528
1478
rec = line.split()
2529
1479
if len(rec) != 4:
2530
raise KnitCorrupt(self._access,
1480
raise KnitCorrupt(self._filename,
2531
1481
'unexpected number of elements in record header')
2532
1482
if rec[1] != version_id:
2533
raise KnitCorrupt(self._access,
1483
raise KnitCorrupt(self._filename,
2534
1484
'unexpected version, wanted %r, got %r'
2535
1485
% (version_id, rec[1]))
2536
1486
return rec
2545
1495
try:
2546
1496
record_contents = df.readlines()
2547
1497
except Exception, e:
2548
raise KnitCorrupt(self._access,
1498
raise KnitCorrupt(self._filename,
2549
1499
"While reading {%s} got %s(%s)"
2550
1500
% (version_id, e.__class__.__name__, str(e)))
2551
1501
header = record_contents.pop(0)
2553
1503
2554
1504
last_line = record_contents.pop()
2555
1505
if len(record_contents) != int(rec[2]):
2556
raise KnitCorrupt(self._access,
1506
raise KnitCorrupt(self._filename,
2557
1507
'incorrect number of lines %s != %s'
2558
1508
' for version {%s}'
2559
1509
% (len(record_contents), int(rec[2]),
2560
1510
version_id))
2561
1511
if last_line != 'end %s\n' % rec[1]:
2562
raise KnitCorrupt(self._access,
1512
raise KnitCorrupt(self._filename,
2563
1513
'unexpected version end line %r, wanted %r'
2564
1514
% (last_line, version_id))
2565
1515
df.close()
2577
1527
# grab the disk data needed.
2578
1528
if self._cache:
2579
1529
# Don't check _cache if it is empty
2580
needed_offsets = [index_memo for version_id, index_memo
1530
needed_offsets = [(pos, size) for version_id, pos, size
2581
1531
in records
2582
1532
if version_id not in self._cache]
2583
1533
else:
2584
needed_offsets = [index_memo for version_id, index_memo
1534
needed_offsets = [(pos, size) for version_id, pos, size
2585
1535
in records]
2586
1536
2587
raw_records = self._access.get_raw_records(needed_offsets)
1537
raw_records = self._transport.readv(self._filename, needed_offsets)
2588
1538
2589
for version_id, index_memo in records:
1539
for version_id, pos, size in records:
2590
1540
if version_id in self._cache:
2591
1541
# This data has already been validated
2592
1542
data = self._cache[version_id]
2593
1543
else:
2594
data = raw_records.next()
1544
pos, data = raw_records.next()
2595
1545
if self._do_cache:
2596
1546
self._cache[version_id] = data
2597
1547
2636
1586
2637
1587
# The transport optimizes the fetching as well
2638
1588
# (ie, reads continuous ranges.)
2639
raw_data = self._access.get_raw_records(
2640
[index_memo for version_id, index_memo in needed_records])
1589
readv_response = self._transport.readv(self._filename,
1590
[(pos, size) for version_id, pos, size in needed_records])
2641
1591
2642
for (version_id, index_memo), data in \
2643
izip(iter(needed_records), raw_data):
1592
for (version_id, pos, size), (pos, data) in \
1593
izip(iter(needed_records), readv_response):
2644
1594
content, digest = self._parse_record(version_id, data)
2645
1595
if self._do_cache:
2646
1596
self._cache[version_id] = data
2670
1620
except AttributeError:
2671
1621
return False
2672
1622
2673
def _copy_texts(self, pb, msg, version_ids, ignore_missing=False):
2674
"""Copy texts to the target by extracting and adding them one by one.
2675
2676
see join() for the parameter definitions.
2677
"""
2678
version_ids = self._get_source_version_ids(version_ids, ignore_missing)
2679
# --- the below is factorable out with VersionedFile.join, but wait for
2680
# VersionedFiles, it may all be simpler then.
2681
graph = Graph(self.source)
2682
search = graph._make_breadth_first_searcher(version_ids)
2683
transitive_ids = set()
2684
map(transitive_ids.update, list(search))
2685
parent_map = self.source.get_parent_map(transitive_ids)
2686
order = topo_sort(parent_map.items())
2687
2688
def size_of_content(content):
2689
return sum(len(line) for line in content.text())
2690
# Cache at most 10MB of parent texts
2691
parent_cache = lru_cache.LRUSizeCache(max_size=10*1024*1024,
2692
compute_size=size_of_content)
2693
# TODO: jam 20071116 It would be nice to have a streaming interface to
2694
# get multiple texts from a source. The source could be smarter
2695
# about how it handled intermediate stages.
2696
# get_line_list() or make_mpdiffs() seem like a possibility, but
2697
# at the moment they extract all full texts into memory, which
2698
# causes us to store more than our 3x fulltext goal.
2699
# Repository.iter_files_bytes() may be another possibility
2700
to_process = [version for version in order
2701
if version not in self.target]
2702
total = len(to_process)
2703
pb = ui.ui_factory.nested_progress_bar()
2704
try:
2705
for index, version in enumerate(to_process):
2706
pb.update('Converting versioned data', index, total)
2707
sha1, num_bytes, parent_text = self.target.add_lines(version,
2708
self.source.get_parents_with_ghosts(version),
2709
self.source.get_lines(version),
2710
parent_texts=parent_cache)
2711
parent_cache[version] = parent_text
2712
finally:
2713
pb.finished()
2714
return total
2715
2716
1623
def join(self, pb=None, msg=None, version_ids=None, ignore_missing=False):
2717
1624
"""See InterVersionedFile.join."""
2718
1625
assert isinstance(self.source, KnitVersionedFile)
2719
1626
assert isinstance(self.target, KnitVersionedFile)
2720
1627
2721
# If the source and target are mismatched w.r.t. annotations vs
2722
# plain, the data needs to be converted accordingly
2723
if self.source.factory.annotated == self.target.factory.annotated:
2724
converter = None
2725
elif self.source.factory.annotated:
2726
converter = self._anno_to_plain_converter
2727
else:
2728
# We're converting from a plain to an annotated knit. Copy them
2729
# across by full texts.
2730
return self._copy_texts(pb, msg, version_ids, ignore_missing)
2731
2732
1628
version_ids = self._get_source_version_ids(version_ids, ignore_missing)
1629
2733
1630
if not version_ids:
2734
1631
return 0
2735
1632
2739
1636
if None in version_ids:
2740
1637
version_ids.remove(None)
2741
1638
2742
self.source_ancestry = set(self.source.get_ancestry(version_ids,
2743
topo_sorted=False))
1639
self.source_ancestry = set(self.source.get_ancestry(version_ids))
2744
1640
this_versions = set(self.target._index.get_versions())
2745
# XXX: For efficiency we should not look at the whole index,
2746
# we only need to consider the referenced revisions - they
2747
# must all be present, or the method must be full-text.
2748
# TODO, RBC 20070919
2749
1641
needed_versions = self.source_ancestry - this_versions
1642
cross_check_versions = self.source_ancestry.intersection(this_versions)
1643
mismatched_versions = set()
1644
for version in cross_check_versions:
1645
# scan to include needed parents.
1646
n1 = set(self.target.get_parents_with_ghosts(version))
1647
n2 = set(self.source.get_parents_with_ghosts(version))
1648
if n1 != n2:
1649
# FIXME TEST this check for cycles being introduced works
1650
# the logic is we have a cycle if in our graph we are an
1651
# ancestor of any of the n2 revisions.
1652
for parent in n2:
1653
if parent in n1:
1654
# safe
1655
continue
1656
else:
1657
parent_ancestors = self.source.get_ancestry(parent)
1658
if version in parent_ancestors:
1659
raise errors.GraphCycleError([parent, version])
1660
# ensure this parent will be available later.
1661
new_parents = n2.difference(n1)
1662
needed_versions.update(new_parents.difference(this_versions))
1663
mismatched_versions.add(version)
2750
1664
2751
if not needed_versions:
1665
if not needed_versions and not mismatched_versions:
2752
1666
return 0
2753
full_list = topo_sort(
2754
self.source.get_parent_map(self.source.versions()))
1667
full_list = topo_sort(self.source.get_graph())
2755
1668
2756
1669
version_list = [i for i in full_list if (not self.target.has_version(i)
2757
1670
and i in needed_versions)]
2772
1685
assert (self.target.has_version(parent) or
2773
1686
parent in copy_set or
2774
1687
not self.source.has_version(parent))
2775
index_memo = self.source._index.get_position(version_id)
2776
copy_queue_records.append((version_id, index_memo))
1688
data_pos, data_size = self.source._index.get_position(version_id)
1689
copy_queue_records.append((version_id, data_pos, data_size))
2777
1690
copy_queue.append((version_id, options, parents))
2778
1691
copy_set.add(version_id)
2779
1692
2789
1702
assert version_id == version_id2, 'logic error, inconsistent results'
2790
1703
count = count + 1
2791
1704
pb.update("Joining knit", count, total)
2792
if converter:
2793
size, raw_data = converter(raw_data, version_id, options,
2794
parents)
2795
else:
2796
size = len(raw_data)
2797
raw_records.append((version_id, options, parents, size))
1705
raw_records.append((version_id, options, parents, len(raw_data)))
2798
1706
raw_datum.append(raw_data)
2799
1707
self.target._add_raw_records(raw_records, ''.join(raw_datum))
1708
1709
for version in mismatched_versions:
1710
# FIXME RBC 20060309 is this needed?
1711
n1 = set(self.target.get_parents_with_ghosts(version))
1712
n2 = set(self.source.get_parents_with_ghosts(version))
1713
# write a combined record to our history preserving the current
1714
# parents as first in the list
1715
new_parents = self.target.get_parents_with_ghosts(version) + list(n2.difference(n1))
1716
self.target.fix_parents(version, new_parents)
2800
1717
return count
2801
1718
finally:
2802
1719
pb.finished()
2803
1720
2804
def _anno_to_plain_converter(self, raw_data, version_id, options,
2805
parents):
2806
"""Convert annotated content to plain content."""
2807
data, digest = self.source._data._parse_record(version_id, raw_data)
2808
if 'fulltext' in options:
2809
content = self.source.factory.parse_fulltext(data, version_id)
2810
lines = self.target.factory.lower_fulltext(content)
2811
else:
2812
delta = self.source.factory.parse_line_delta(data, version_id,
2813
plain=True)
2814
lines = self.target.factory.lower_line_delta(delta)
2815
return self.target._data._record_to_data(version_id, digest, lines)
2816
2817
1721
2818
1722
InterVersionedFile.register_optimiser(InterKnit)
2819
1723
2850
1754
self.source_ancestry = set(self.source.get_ancestry(version_ids))
2851
1755
this_versions = set(self.target._index.get_versions())
2852
1756
needed_versions = self.source_ancestry - this_versions
1757
cross_check_versions = self.source_ancestry.intersection(this_versions)
1758
mismatched_versions = set()
1759
for version in cross_check_versions:
1760
# scan to include needed parents.
1761
n1 = set(self.target.get_parents_with_ghosts(version))
1762
n2 = set(self.source.get_parents(version))
1763
# if all of n2's parents are in n1, then its fine.
1764
if n2.difference(n1):
1765
# FIXME TEST this check for cycles being introduced works
1766
# the logic is we have a cycle if in our graph we are an
1767
# ancestor of any of the n2 revisions.
1768
for parent in n2:
1769
if parent in n1:
1770
# safe
1771
continue
1772
else:
1773
parent_ancestors = self.source.get_ancestry(parent)
1774
if version in parent_ancestors:
1775
raise errors.GraphCycleError([parent, version])
1776
# ensure this parent will be available later.
1777
new_parents = n2.difference(n1)
1778
needed_versions.update(new_parents.difference(this_versions))
1779
mismatched_versions.add(version)
2853
1780
2854
if not needed_versions:
1781
if not needed_versions and not mismatched_versions:
2855
1782
return 0
2856
full_list = topo_sort(
2857
self.source.get_parent_map(self.source.versions()))
1783
full_list = topo_sort(self.source.get_graph())
2858
1784
2859
1785
version_list = [i for i in full_list if (not self.target.has_version(i)
2860
1786
and i in needed_versions)]
2862
1788
# do the join:
2863
1789
count = 0
2864
1790
total = len(version_list)
2865
parent_map = self.source.get_parent_map(version_list)
2866
1791
for version_id in version_list:
2867
1792
pb.update("Converting to knit", count, total)
2868
parents = parent_map[version_id]
1793
parents = self.source.get_parents(version_id)
2869
1794
# check that its will be a consistent copy:
2870
1795
for parent in parents:
2871
1796
# if source has the parent, we must already have it
2873
1798
self.target.add_lines(
2874
1799
version_id, parents, self.source.get_lines(version_id))
2875
1800
count = count + 1
1801
1802
for version in mismatched_versions:
1803
# FIXME RBC 20060309 is this needed?
1804
n1 = set(self.target.get_parents_with_ghosts(version))
1805
n2 = set(self.source.get_parents(version))
1806
# write a combined record to our history preserving the current
1807
# parents as first in the list
1808
new_parents = self.target.get_parents_with_ghosts(version) + list(n2.difference(n1))
1809
self.target.fix_parents(version, new_parents)
2876
1810
return count
2877
1811
finally:
2878
1812
pb.finished()
2881
1815
InterVersionedFile.register_optimiser(WeaveToKnit)
2882
1816
2883
1817
2884
# Deprecated, use PatienceSequenceMatcher instead
2885
KnitSequenceMatcher = patiencediff.PatienceSequenceMatcher
2886
2887
2888
def annotate_knit(knit, revision_id):
2889
"""Annotate a knit with no cached annotations.
2890
2891
This implementation is for knits with no cached annotations.
2892
It will work for knits with cached annotations, but this is not
2893
recommended.
1818
class KnitSequenceMatcher(difflib.SequenceMatcher):
1819
"""Knit tuned sequence matcher.
1820
1821
This is based on profiling of difflib which indicated some improvements
1822
for our usage pattern.
2894
1823
"""
2895
annotator = _KnitAnnotator(knit)
2896
return iter(annotator.annotate(revision_id))
2897
2898
2899
class _KnitAnnotator(object):
2900
"""Build up the annotations for a text."""
2901
2902
def __init__(self, knit):
2903
self._knit = knit
2904
2905
# Content objects, differs from fulltexts because of how final newlines
2906
# are treated by knits. the content objects here will always have a
2907
# final newline
2908
self._fulltext_contents = {}
2909
2910
# Annotated lines of specific revisions
2911
self._annotated_lines = {}
2912
2913
# Track the raw data for nodes that we could not process yet.
2914
# This maps the revision_id of the base to a list of children that will
2915
# annotated from it.
2916
self._pending_children = {}
2917
2918
# Nodes which cannot be extracted
2919
self._ghosts = set()
2920
2921
# Track how many children this node has, so we know if we need to keep
2922
# it
2923
self._annotate_children = {}
2924
self._compression_children = {}
2925
2926
self._all_build_details = {}
2927
# The children => parent revision_id graph
2928
self._revision_id_graph = {}
2929
2930
self._heads_provider = None
2931
2932
self._nodes_to_keep_annotations = set()
2933
self._generations_until_keep = 100
2934
2935
def set_generations_until_keep(self, value):
2936
"""Set the number of generations before caching a node.
2937
2938
Setting this to -1 will cache every merge node, setting this higher
2939
will cache fewer nodes.
2940
"""
2941
self._generations_until_keep = value
2942
2943
def _add_fulltext_content(self, revision_id, content_obj):
2944
self._fulltext_contents[revision_id] = content_obj
2945
# TODO: jam 20080305 It might be good to check the sha1digest here
2946
return content_obj.text()
2947
2948
def _check_parents(self, child, nodes_to_annotate):
2949
"""Check if all parents have been processed.
2950
2951
:param child: A tuple of (rev_id, parents, raw_content)
2952
:param nodes_to_annotate: If child is ready, add it to
2953
nodes_to_annotate, otherwise put it back in self._pending_children
2954
"""
2955
for parent_id in child[1]:
2956
if (parent_id not in self._annotated_lines):
2957
# This parent is present, but another parent is missing
2958
self._pending_children.setdefault(parent_id,
2959
[]).append(child)
2960
break
2961
else:
2962
# This one is ready to be processed
2963
nodes_to_annotate.append(child)
2964
2965
def _add_annotation(self, revision_id, fulltext, parent_ids,
2966
left_matching_blocks=None):
2967
"""Add an annotation entry.
2968
2969
All parents should already have been annotated.
2970
:return: A list of children that now have their parents satisfied.
2971
"""
2972
a = self._annotated_lines
2973
annotated_parent_lines = [a[p] for p in parent_ids]
2974
annotated_lines = list(annotate.reannotate(annotated_parent_lines,
2975
fulltext, revision_id, left_matching_blocks,
2976
heads_provider=self._get_heads_provider()))
2977
self._annotated_lines[revision_id] = annotated_lines
2978
for p in parent_ids:
2979
ann_children = self._annotate_children[p]
2980
ann_children.remove(revision_id)
2981
if (not ann_children
2982
and p not in self._nodes_to_keep_annotations):
2983
del self._annotated_lines[p]
2984
del self._all_build_details[p]
2985
if p in self._fulltext_contents:
2986
del self._fulltext_contents[p]
2987
# Now that we've added this one, see if there are any pending
2988
# deltas to be done, certainly this parent is finished
2989
nodes_to_annotate = []
2990
for child in self._pending_children.pop(revision_id, []):
2991
self._check_parents(child, nodes_to_annotate)
2992
return nodes_to_annotate
2993
2994
def _get_build_graph(self, revision_id):
2995
"""Get the graphs for building texts and annotations.
2996
2997
The data you need for creating a full text may be different than the
2998
data you need to annotate that text. (At a minimum, you need both
2999
parents to create an annotation, but only need 1 parent to generate the
3000
fulltext.)
3001
3002
:return: A list of (revision_id, index_memo) records, suitable for
3003
passing to read_records_iter to start reading in the raw data fro/
3004
the pack file.
3005
"""
3006
if revision_id in self._annotated_lines:
3007
# Nothing to do
3008
return []
3009
pending = set([revision_id])
3010
records = []
3011
generation = 0
3012
kept_generation = 0
3013
while pending:
3014
# get all pending nodes
3015
generation += 1
3016
this_iteration = pending
3017
build_details = self._knit._index.get_build_details(this_iteration)
3018
self._all_build_details.update(build_details)
3019
# new_nodes = self._knit._index._get_entries(this_iteration)
3020
pending = set()
3021
for rev_id, details in build_details.iteritems():
3022
(index_memo, compression_parent, parents,
3023
record_details) = details
3024
self._revision_id_graph[rev_id] = parents
3025
records.append((rev_id, index_memo))
3026
# Do we actually need to check _annotated_lines?
3027
pending.update(p for p in parents
3028
if p not in self._all_build_details)
3029
if compression_parent:
3030
self._compression_children.setdefault(compression_parent,
3031
[]).append(rev_id)
3032
if parents:
3033
for parent in parents:
3034
self._annotate_children.setdefault(parent,
3035
[]).append(rev_id)
3036
num_gens = generation - kept_generation
3037
if ((num_gens >= self._generations_until_keep)
3038
and len(parents) > 1):
3039
kept_generation = generation
3040
self._nodes_to_keep_annotations.add(rev_id)
3041
3042
missing_versions = this_iteration.difference(build_details.keys())
3043
self._ghosts.update(missing_versions)
3044
for missing_version in missing_versions:
3045
# add a key, no parents
3046
self._revision_id_graph[missing_version] = ()
3047
pending.discard(missing_version) # don't look for it
3048
# XXX: This should probably be a real exception, as it is a data
3049
# inconsistency
3050
assert not self._ghosts.intersection(self._compression_children), \
3051
"We cannot have nodes which have a compression parent of a ghost."
3052
# Cleanout anything that depends on a ghost so that we don't wait for
3053
# the ghost to show up
3054
for node in self._ghosts:
3055
if node in self._annotate_children:
3056
# We won't be building this node
3057
del self._annotate_children[node]
3058
# Generally we will want to read the records in reverse order, because
3059
# we find the parent nodes after the children
3060
records.reverse()
3061
return records
3062
3063
def _annotate_records(self, records):
3064
"""Build the annotations for the listed records."""
3065
# We iterate in the order read, rather than a strict order requested
3066
# However, process what we can, and put off to the side things that
3067
# still need parents, cleaning them up when those parents are
3068
# processed.
3069
for (rev_id, record,
3070
digest) in self._knit._data.read_records_iter(records):
3071
if rev_id in self._annotated_lines:
3072
continue
3073
parent_ids = self._revision_id_graph[rev_id]
3074
parent_ids = [p for p in parent_ids if p not in self._ghosts]
3075
details = self._all_build_details[rev_id]
3076
(index_memo, compression_parent, parents,
3077
record_details) = details
3078
nodes_to_annotate = []
3079
# TODO: Remove the punning between compression parents, and
3080
# parent_ids, we should be able to do this without assuming
3081
# the build order
3082
if len(parent_ids) == 0:
3083
# There are no parents for this node, so just add it
3084
# TODO: This probably needs to be decoupled
3085
assert compression_parent is None
3086
fulltext_content, delta = self._knit.factory.parse_record(
3087
rev_id, record, record_details, None)
3088
fulltext = self._add_fulltext_content(rev_id, fulltext_content)
3089
nodes_to_annotate.extend(self._add_annotation(rev_id, fulltext,
3090
parent_ids, left_matching_blocks=None))
1824
1825
def find_longest_match(self, alo, ahi, blo, bhi):
1826
"""Find longest matching block in a[alo:ahi] and b[blo:bhi].
1827
1828
If isjunk is not defined:
1829
1830
Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
1831
alo <= i <= i+k <= ahi
1832
blo <= j <= j+k <= bhi
1833
and for all (i',j',k') meeting those conditions,
1834
k >= k'
1835
i <= i'
1836
and if i == i', j <= j'
1837
1838
In other words, of all maximal matching blocks, return one that
1839
starts earliest in a, and of all those maximal matching blocks that
1840
start earliest in a, return the one that starts earliest in b.
1841
1842
>>> s = SequenceMatcher(None, " abcd", "abcd abcd")
1843
>>> s.find_longest_match(0, 5, 0, 9)
1844
(0, 4, 5)
1845
1846
If isjunk is defined, first the longest matching block is
1847
determined as above, but with the additional restriction that no
1848
junk element appears in the block. Then that block is extended as
1849
far as possible by matching (only) junk elements on both sides. So
1850
the resulting block never matches on junk except as identical junk
1851
happens to be adjacent to an "interesting" match.
1852
1853
Here's the same example as before, but considering blanks to be
1854
junk. That prevents " abcd" from matching the " abcd" at the tail
1855
end of the second sequence directly. Instead only the "abcd" can
1856
match, and matches the leftmost "abcd" in the second sequence:
1857
1858
>>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
1859
>>> s.find_longest_match(0, 5, 0, 9)
1860
(1, 0, 4)
1861
1862
If no blocks match, return (alo, blo, 0).
1863
1864
>>> s = SequenceMatcher(None, "ab", "c")
1865
>>> s.find_longest_match(0, 2, 0, 1)
1866
(0, 0, 0)
1867
"""
1868
1869
# CAUTION: stripping common prefix or suffix would be incorrect.
1870
# E.g.,
1871
# ab
1872
# acab
1873
# Longest matching block is "ab", but if common prefix is
1874
# stripped, it's "a" (tied with "b"). UNIX(tm) diff does so
1875
# strip, so ends up claiming that ab is changed to acab by
1876
# inserting "ca" in the middle. That's minimal but unintuitive:
1877
# "it's obvious" that someone inserted "ac" at the front.
1878
# Windiff ends up at the same place as diff, but by pairing up
1879
# the unique 'b's and then matching the first two 'a's.
1880
1881
a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.isbjunk
1882
besti, bestj, bestsize = alo, blo, 0
1883
# find longest junk-free match
1884
# during an iteration of the loop, j2len[j] = length of longest
1885
# junk-free match ending with a[i-1] and b[j]
1886
j2len = {}
1887
# nothing = []
1888
b2jget = b2j.get
1889
for i in xrange(alo, ahi):
1890
# look at all instances of a[i] in b; note that because
1891
# b2j has no junk keys, the loop is skipped if a[i] is junk
1892
j2lenget = j2len.get
1893
newj2len = {}
1894
1895
# changing b2j.get(a[i], nothing) to a try:KeyError pair produced the
1896
# following improvement
1897
# 704 0 4650.5320 2620.7410 bzrlib.knit:1336(find_longest_match)
1898
# +326674 0 1655.1210 1655.1210 +<method 'get' of 'dict' objects>
1899
# +76519 0 374.6700 374.6700 +<method 'has_key' of 'dict' objects>
1900
# to
1901
# 704 0 3733.2820 2209.6520 bzrlib.knit:1336(find_longest_match)
1902
# +211400 0 1147.3520 1147.3520 +<method 'get' of 'dict' objects>
1903
# +76519 0 376.2780 376.2780 +<method 'has_key' of 'dict' objects>
1904
1905
try:
1906
js = b2j[a[i]]
1907
except KeyError:
1908
pass
3091
1909
else:
3092
child = (rev_id, parent_ids, record)
3093
# Check if all the parents are present
3094
self._check_parents(child, nodes_to_annotate)
3095
while nodes_to_annotate:
3096
# Should we use a queue here instead of a stack?
3097
(rev_id, parent_ids, record) = nodes_to_annotate.pop()
3098
(index_memo, compression_parent, parents,
3099
record_details) = self._all_build_details[rev_id]
3100
if compression_parent is not None:
3101
comp_children = self._compression_children[compression_parent]
3102
assert rev_id in comp_children
3103
# If there is only 1 child, it is safe to reuse this
3104
# content
3105
reuse_content = (len(comp_children) == 1
3106
and compression_parent not in
3107
self._nodes_to_keep_annotations)
3108
if reuse_content:
3109
# Remove it from the cache since it will be changing
3110
parent_fulltext_content = self._fulltext_contents.pop(compression_parent)
3111
# Make sure to copy the fulltext since it might be
3112
# modified
3113
parent_fulltext = list(parent_fulltext_content.text())
3114
else:
3115
parent_fulltext_content = self._fulltext_contents[compression_parent]
3116
parent_fulltext = parent_fulltext_content.text()
3117
comp_children.remove(rev_id)
3118
fulltext_content, delta = self._knit.factory.parse_record(
3119
rev_id, record, record_details,
3120
parent_fulltext_content,
3121
copy_base_content=(not reuse_content))
3122
fulltext = self._add_fulltext_content(rev_id,
3123
fulltext_content)
3124
blocks = KnitContent.get_line_delta_blocks(delta,
3125
parent_fulltext, fulltext)
3126
else:
3127
fulltext_content = self._knit.factory.parse_fulltext(
3128
record, rev_id)
3129
fulltext = self._add_fulltext_content(rev_id,
3130
fulltext_content)
3131
blocks = None
3132
nodes_to_annotate.extend(
3133
self._add_annotation(rev_id, fulltext, parent_ids,
3134
left_matching_blocks=blocks))
3135
3136
def _get_heads_provider(self):
3137
"""Create a heads provider for resolving ancestry issues."""
3138
if self._heads_provider is not None:
3139
return self._heads_provider
3140
parent_provider = _mod_graph.DictParentsProvider(
3141
self._revision_id_graph)
3142
graph_obj = _mod_graph.Graph(parent_provider)
3143
head_cache = _mod_graph.FrozenHeadsCache(graph_obj)
3144
self._heads_provider = head_cache
3145
return head_cache
3146
3147
def annotate(self, revision_id):
3148
"""Return the annotated fulltext at the given revision.
3149
3150
:param revision_id: The revision id for this file
3151
"""
3152
records = self._get_build_graph(revision_id)
3153
if revision_id in self._ghosts:
3154
raise errors.RevisionNotPresent(revision_id, self._knit)
3155
self._annotate_records(records)
3156
return self._annotated_lines[revision_id]
3157
3158
3159
try:
3160
from bzrlib._knit_load_data_c import _load_data_c as _load_data
3161
except ImportError:
3162
from bzrlib._knit_load_data_py import _load_data_py as _load_data
1910
for j in js:
1911
# a[i] matches b[j]
1912
if j >= blo:
1913
if j >= bhi:
1914
break
1915
k = newj2len[j] = 1 + j2lenget(-1 + j, 0)
1916
if k > bestsize:
1917
besti, bestj, bestsize = 1 + i-k, 1 + j-k, k
1918
j2len = newj2len
1919
1920
# Extend the best by non-junk elements on each end. In particular,
1921
# "popular" non-junk elements aren't in b2j, which greatly speeds
1922
# the inner loop above, but also means "the best" match so far
1923
# doesn't contain any junk *or* popular non-junk elements.
1924
while besti > alo and bestj > blo and \
1925
not isbjunk(b[bestj-1]) and \
1926
a[besti-1] == b[bestj-1]:
1927
besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
1928
while besti+bestsize < ahi and bestj+bestsize < bhi and \
1929
not isbjunk(b[bestj+bestsize]) and \
1930
a[besti+bestsize] == b[bestj+bestsize]:
1931
bestsize += 1
1932
1933
# Now that we have a wholly interesting match (albeit possibly
1934
# empty!), we may as well suck up the matching junk on each
1935
# side of it too. Can't think of a good reason not to, and it
1936
# saves post-processing the (possibly considerable) expense of
1937
# figuring out what to do with it. In the case of an empty
1938
# interesting match, this is clearly the right thing to do,
1939
# because no other kind of match is possible in the regions.
1940
while besti > alo and bestj > blo and \
1941
isbjunk(b[bestj-1]) and \
1942
a[besti-1] == b[bestj-1]:
1943
besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
1944
while besti+bestsize < ahi and bestj+bestsize < bhi and \
1945
isbjunk(b[bestj+bestsize]) and \
1946
a[besti+bestsize] == b[bestj+bestsize]:
1947
bestsize = bestsize + 1
1948
1949
return besti, bestj, bestsize
Loggerhead is a web-based interface for Breezy
Version: 2.0.1