1
# Copyright (C) 2007-2011 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
from __future__ import absolute_import
22
from .lazy_import import lazy_import
24
lazy_import(globals(), """
37
from .i18n import gettext
44
def topo_iter_keys(vf, keys=None):
47
parents = vf.get_parent_map(keys)
48
return _topo_iter(parents, keys)
51
def topo_iter(vf, versions=None):
53
versions = vf.versions()
54
parents = vf.get_parent_map(versions)
55
return _topo_iter(parents, versions)
58
def _topo_iter(parents, versions):
62
def pending_parents(version):
63
if parents[version] is None:
65
return [v for v in parents[version] if v in versions and
67
for version_id in versions:
68
if parents[version_id] is None:
71
for parent_id in parents[version_id]:
72
descendants.setdefault(parent_id, []).append(version_id)
73
cur = [v for v in versions if len(pending_parents(v)) == 0]
76
for version_id in cur:
77
if version_id in seen:
79
if len(pending_parents(version_id)) != 0:
81
next.extend(descendants.get(version_id, []))
87
class MultiParent(object):
88
"""A multi-parent diff"""
92
def __init__(self, hunks=None):
99
return "MultiParent(%r)" % self.hunks
101
def __eq__(self, other):
102
if self.__class__ is not other.__class__:
104
return (self.hunks == other.hunks)
107
def from_lines(text, parents=(), left_blocks=None):
108
"""Produce a MultiParent from a list of lines and parents"""
110
matcher = patiencediff.PatienceSequenceMatcher(None, parent,
112
return matcher.get_matching_blocks()
114
if left_blocks is None:
115
left_blocks = compare(parents[0])
116
parent_comparisons = [left_blocks] + [compare(p) for p in
119
parent_comparisons = []
121
new_text = NewText([])
123
block_iter = [iter(i) for i in parent_comparisons]
124
diff = MultiParent([])
128
return next(block_iter[p])
129
except StopIteration:
131
cur_block = [next_block(p) for p, i in enumerate(block_iter)]
132
while cur_line < len(text):
134
for p, block in enumerate(cur_block):
138
while j + n <= cur_line:
139
block = cur_block[p] = next_block(p)
147
offset = cur_line - j
153
if best_match is None or n > best_match.num_lines:
154
best_match = ParentText(p, i, j, n)
155
if best_match is None:
156
new_text.lines.append(text[cur_line])
159
if len(new_text.lines) > 0:
160
diff.hunks.append(new_text)
161
new_text = NewText([])
162
diff.hunks.append(best_match)
163
cur_line += best_match.num_lines
164
if len(new_text.lines) > 0:
165
diff.hunks.append(new_text)
168
def get_matching_blocks(self, parent, parent_len):
169
for hunk in self.hunks:
170
if not isinstance(hunk, ParentText) or hunk.parent != parent:
172
yield (hunk.parent_pos, hunk.child_pos, hunk.num_lines)
173
yield parent_len, self.num_lines(), 0
175
def to_lines(self, parents=()):
176
"""Contruct a fulltext from this diff and its parents"""
177
mpvf = MultiMemoryVersionedFile()
178
for num, parent in enumerate(parents):
179
mpvf.add_version(BytesIO(parent).readlines(), num, [])
180
mpvf.add_diff(self, 'a', list(range(len(parents))))
181
return mpvf.get_line_list(['a'])[0]
184
def from_texts(cls, text, parents=()):
185
"""Produce a MultiParent from a text and list of parent text"""
186
return cls.from_lines(BytesIO(text).readlines(),
187
[BytesIO(p).readlines() for p in parents])
190
"""Yield text lines for a patch"""
191
for hunk in self.hunks:
192
for line in hunk.to_patch():
196
return len(b''.join(self.to_patch()))
198
def zipped_patch_len(self):
199
return len(gzip_string(self.to_patch()))
202
def from_patch(cls, text):
203
"""Create a MultiParent from its string form"""
204
return cls._from_patch(BytesIO(text))
207
def _from_patch(lines):
208
"""This is private because it is essential to split lines on \n only"""
209
line_iter = iter(lines)
214
cur_line = next(line_iter)
215
except StopIteration:
217
first_char = cur_line[0:1]
218
if first_char == b'i':
219
num_lines = int(cur_line.split(b' ')[1])
220
hunk_lines = [next(line_iter) for _ in range(num_lines)]
221
hunk_lines[-1] = hunk_lines[-1][:-1]
222
hunks.append(NewText(hunk_lines))
223
elif first_char == b'\n':
224
hunks[-1].lines[-1] += b'\n'
226
if not (first_char == b'c'):
227
raise AssertionError(first_char)
228
parent, parent_pos, child_pos, num_lines =\
229
[int(v) for v in cur_line.split(b' ')[1:]]
230
hunks.append(ParentText(parent, parent_pos, child_pos,
232
return MultiParent(hunks)
234
def range_iterator(self):
235
"""Iterate through the hunks, with range indicated
237
kind is "new" or "parent".
238
for "new", data is a list of lines.
239
for "parent", data is (parent, parent_start, parent_end)
240
:return: a generator of (start, end, kind, data)
243
for hunk in self.hunks:
244
if isinstance(hunk, NewText):
246
end = start + len(hunk.lines)
250
start = hunk.child_pos
251
end = start + hunk.num_lines
252
data = (hunk.parent, hunk.parent_pos, hunk.parent_pos +
254
yield start, end, kind, data
258
"""The number of lines in the output text"""
260
for hunk in reversed(self.hunks):
261
if isinstance(hunk, ParentText):
262
return hunk.child_pos + hunk.num_lines + extra_n
263
extra_n += len(hunk.lines)
266
def is_snapshot(self):
267
"""Return true of this hunk is effectively a fulltext"""
268
if len(self.hunks) != 1:
270
return (isinstance(self.hunks[0], NewText))
273
class NewText(object):
274
"""The contents of text that is introduced by this text"""
276
__slots__ = ['lines']
278
def __init__(self, lines):
281
def __eq__(self, other):
282
if self.__class__ is not other.__class__:
284
return (other.lines == self.lines)
287
return 'NewText(%r)' % self.lines
290
yield b'i %d\n' % len(self.lines)
291
for line in self.lines:
296
class ParentText(object):
297
"""A reference to text present in a parent text"""
299
__slots__ = ['parent', 'parent_pos', 'child_pos', 'num_lines']
301
def __init__(self, parent, parent_pos, child_pos, num_lines):
303
self.parent_pos = parent_pos
304
self.child_pos = child_pos
305
self.num_lines = num_lines
308
return {b'parent': self.parent,
309
b'parent_pos': self.parent_pos,
310
b'child_pos': self.child_pos,
311
b'num_lines': self.num_lines}
314
return ('ParentText(%(parent)r, %(parent_pos)r, %(child_pos)r,'
315
' %(num_lines)r)' % self._as_dict())
317
def __eq__(self, other):
318
if self.__class__ is not other.__class__:
320
return self._as_dict() == other._as_dict()
323
yield (b'c %(parent)d %(parent_pos)d %(child_pos)d %(num_lines)d\n'
327
class BaseVersionedFile(object):
328
"""Pseudo-VersionedFile skeleton for MultiParent"""
330
def __init__(self, snapshot_interval=25, max_snapshots=None):
333
self._snapshots = set()
334
self.snapshot_interval = snapshot_interval
335
self.max_snapshots = max_snapshots
338
return iter(self._parents)
340
def has_version(self, version):
341
return version in self._parents
343
def do_snapshot(self, version_id, parent_ids):
344
"""Determine whether to perform a snapshot for this version"""
345
if self.snapshot_interval is None:
347
if self.max_snapshots is not None and\
348
len(self._snapshots) == self.max_snapshots:
350
if len(parent_ids) == 0:
352
for ignored in range(self.snapshot_interval):
353
if len(parent_ids) == 0:
355
version_ids = parent_ids
357
for version_id in version_ids:
358
if version_id not in self._snapshots:
359
parent_ids.extend(self._parents[version_id])
363
def add_version(self, lines, version_id, parent_ids,
364
force_snapshot=None, single_parent=False):
365
"""Add a version to the versionedfile
367
:param lines: The list of lines to add. Must be split on '\n'.
368
:param version_id: The version_id of the version to add
369
:param force_snapshot: If true, force this version to be added as a
370
snapshot version. If false, force this version to be added as a
371
diff. If none, determine this automatically.
372
:param single_parent: If true, use a single parent, rather than
375
if force_snapshot is None:
376
do_snapshot = self.do_snapshot(version_id, parent_ids)
378
do_snapshot = force_snapshot
380
self._snapshots.add(version_id)
381
diff = MultiParent([NewText(lines)])
384
parent_lines = self.get_line_list(parent_ids[:1])
386
parent_lines = self.get_line_list(parent_ids)
387
diff = MultiParent.from_lines(lines, parent_lines)
388
if diff.is_snapshot():
389
self._snapshots.add(version_id)
390
self.add_diff(diff, version_id, parent_ids)
391
self._lines[version_id] = lines
393
def get_parents(self, version_id):
394
return self._parents[version_id]
396
def make_snapshot(self, version_id):
397
snapdiff = MultiParent([NewText(self.cache_version(version_id))])
398
self.add_diff(snapdiff, version_id, self._parents[version_id])
399
self._snapshots.add(version_id)
401
def import_versionedfile(self, vf, snapshots, no_cache=True,
402
single_parent=False, verify=False):
403
"""Import all revisions of a versionedfile
405
:param vf: The versionedfile to import
406
:param snapshots: If provided, the revisions to make snapshots of.
407
Otherwise, this will be auto-determined
408
:param no_cache: If true, clear the cache after every add.
409
:param single_parent: If true, omit all but one parent text, (but
410
retain parent metadata).
412
if not (no_cache or not verify):
414
revisions = set(vf.versions())
415
total = len(revisions)
416
with ui.ui_factory.nested_progress_bar() as pb:
417
while len(revisions) > 0:
419
for revision in revisions:
420
parents = vf.get_parents(revision)
421
if [p for p in parents if p not in self._parents] != []:
423
lines = [a + b' ' + l for a, l in
424
vf.annotate(revision)]
425
if snapshots is None:
426
force_snapshot = None
428
force_snapshot = (revision in snapshots)
429
self.add_version(lines, revision, parents, force_snapshot,
436
if not (lines == self.get_line_list([revision])[0]):
437
raise AssertionError()
439
pb.update(gettext('Importing revisions'),
440
(total - len(revisions)) + len(added), total)
441
revisions = [r for r in revisions if r not in added]
443
def select_snapshots(self, vf):
444
"""Determine which versions to add as snapshots"""
447
for version_id in topo_iter(vf):
448
potential_build_ancestors = set(vf.get_parents(version_id))
449
parents = vf.get_parents(version_id)
450
if len(parents) == 0:
451
snapshots.add(version_id)
452
build_ancestors[version_id] = set()
454
for parent in vf.get_parents(version_id):
455
potential_build_ancestors.update(build_ancestors[parent])
456
if len(potential_build_ancestors) > self.snapshot_interval:
457
snapshots.add(version_id)
458
build_ancestors[version_id] = set()
460
build_ancestors[version_id] = potential_build_ancestors
463
def select_by_size(self, num):
464
"""Select snapshots for minimum output size"""
465
num -= len(self._snapshots)
466
new_snapshots = self.get_size_ranking()[-num:]
467
return [v for n, v in new_snapshots]
469
def get_size_ranking(self):
470
"""Get versions ranked by size"""
472
for version_id in self.versions():
473
if version_id in self._snapshots:
475
diff_len = self.get_diff(version_id).patch_len()
476
snapshot_len = MultiParent([NewText(
477
self.cache_version(version_id))]).patch_len()
478
versions.append((snapshot_len - diff_len, version_id))
482
def import_diffs(self, vf):
483
"""Import the diffs from another pseudo-versionedfile"""
484
for version_id in vf.versions():
485
self.add_diff(vf.get_diff(version_id), version_id,
486
vf._parents[version_id])
488
def get_build_ranking(self):
489
"""Return revisions sorted by how much they reduce build complexity"""
492
for version_id in topo_iter(self):
493
could_avoid[version_id] = set()
494
if version_id not in self._snapshots:
495
for parent_id in self._parents[version_id]:
496
could_avoid[version_id].update(could_avoid[parent_id])
497
could_avoid[version_id].update(self._parents)
498
could_avoid[version_id].discard(version_id)
499
for avoid_id in could_avoid[version_id]:
500
referenced_by.setdefault(avoid_id, set()).add(version_id)
501
available_versions = list(self.versions())
503
while len(available_versions) > 0:
504
available_versions.sort(key=lambda x:
505
len(could_avoid[x]) *
506
len(referenced_by.get(x, [])))
507
selected = available_versions.pop()
508
ranking.append(selected)
509
for version_id in referenced_by[selected]:
510
could_avoid[version_id].difference_update(
511
could_avoid[selected])
512
for version_id in could_avoid[selected]:
513
referenced_by[version_id].difference_update(
514
referenced_by[selected]
518
def clear_cache(self):
521
def get_line_list(self, version_ids):
522
return [self.cache_version(v) for v in version_ids]
524
def cache_version(self, version_id):
526
return self._lines[version_id]
529
diff = self.get_diff(version_id)
531
reconstructor = _Reconstructor(self, self._lines, self._parents)
532
reconstructor.reconstruct_version(lines, version_id)
533
self._lines[version_id] = lines
537
class MultiMemoryVersionedFile(BaseVersionedFile):
538
"""Memory-backed pseudo-versionedfile"""
540
def __init__(self, snapshot_interval=25, max_snapshots=None):
541
BaseVersionedFile.__init__(self, snapshot_interval, max_snapshots)
544
def add_diff(self, diff, version_id, parent_ids):
545
self._diffs[version_id] = diff
546
self._parents[version_id] = parent_ids
548
def get_diff(self, version_id):
550
return self._diffs[version_id]
552
raise errors.RevisionNotPresent(version_id, self)
558
class MultiVersionedFile(BaseVersionedFile):
559
"""Disk-backed pseudo-versionedfile"""
561
def __init__(self, filename, snapshot_interval=25, max_snapshots=None):
562
BaseVersionedFile.__init__(self, snapshot_interval, max_snapshots)
563
self._filename = filename
564
self._diff_offset = {}
566
def get_diff(self, version_id):
567
start, count = self._diff_offset[version_id]
568
with open(self._filename + '.mpknit', 'rb') as infile:
570
sio = BytesIO(infile.read(count))
571
with gzip.GzipFile(None, mode='rb', fileobj=sio) as zip_file:
572
file_version_id = zip_file.readline()
573
content = zip_file.read()
574
return MultiParent.from_patch(content)
576
def add_diff(self, diff, version_id, parent_ids):
577
with open(self._filename + '.mpknit', 'ab') as outfile:
578
outfile.seek(0, 2) # workaround for windows bug:
579
# .tell() for files opened in 'ab' mode
580
# before any write returns 0
581
start = outfile.tell()
582
with gzip.GzipFile(None, mode='ab', fileobj=outfile) as zipfile:
583
zipfile.writelines(itertools.chain(
584
[b'version %s\n' % version_id], diff.to_patch()))
586
self._diff_offset[version_id] = (start, end - start)
587
self._parents[version_id] = parent_ids
591
os.unlink(self._filename + '.mpknit')
593
if e.errno != errno.ENOENT:
596
os.unlink(self._filename + '.mpidx')
598
if e.errno != errno.ENOENT:
602
open(self._filename + '.mpidx', 'wb').write(bencode.bencode(
603
(self._parents, list(self._snapshots), self._diff_offset)))
606
self._parents, snapshots, self._diff_offset = bencode.bdecode(
607
open(self._filename + '.mpidx', 'rb').read())
608
self._snapshots = set(snapshots)
611
class _Reconstructor(object):
612
"""Build a text from the diffs, ancestry graph and cached lines"""
614
def __init__(self, diffs, lines, parents):
617
self.parents = parents
620
def reconstruct(self, lines, parent_text, version_id):
621
"""Append the lines referred to by a ParentText to lines"""
622
parent_id = self.parents[version_id][parent_text.parent]
623
end = parent_text.parent_pos + parent_text.num_lines
624
return self._reconstruct(lines, parent_id, parent_text.parent_pos,
627
def _reconstruct(self, lines, req_version_id, req_start, req_end):
628
"""Append lines for the requested version_id range"""
629
# stack of pending range requests
630
if req_start == req_end:
632
pending_reqs = [(req_version_id, req_start, req_end)]
633
while len(pending_reqs) > 0:
634
req_version_id, req_start, req_end = pending_reqs.pop()
635
# lazily allocate cursors for versions
636
if req_version_id in self.lines:
637
lines.extend(self.lines[req_version_id][req_start:req_end])
640
start, end, kind, data, iterator = self.cursor[req_version_id]
642
iterator = self.diffs.get_diff(req_version_id).range_iterator()
643
start, end, kind, data = next(iterator)
644
if start > req_start:
645
iterator = self.diffs.get_diff(req_version_id).range_iterator()
646
start, end, kind, data = next(iterator)
648
# find the first hunk relevant to the request
649
while end <= req_start:
650
start, end, kind, data = next(iterator)
651
self.cursor[req_version_id] = start, end, kind, data, iterator
652
# if the hunk can't satisfy the whole request, split it in two,
653
# and leave the second half for later.
655
pending_reqs.append((req_version_id, end, req_end))
658
lines.extend(data[req_start - start: (req_end - start)])
660
# If the hunk is a ParentText, rewrite it as a range request
661
# for the parent, and make it the next pending request.
662
parent, parent_start, parent_end = data
663
new_version_id = self.parents[req_version_id][parent]
664
new_start = parent_start + req_start - start
665
new_end = parent_end + req_end - end
666
pending_reqs.append((new_version_id, new_start, new_end))
668
def reconstruct_version(self, lines, version_id):
669
length = self.diffs.get_diff(version_id).num_lines()
670
return self._reconstruct(lines, version_id, 0, length)
673
def gzip_string(lines):
675
with gzip.GzipFile(None, mode='wb', fileobj=sio) as data_file:
676
data_file.writelines(lines)
677
return sio.getvalue()
added
removed
breezy/multiparent.py
