1
# Copyright (C) 2007 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
from bzrlib.lazy_import import lazy_import
19
lazy_import(globals(), """
23
from StringIO import StringIO
31
from bzrlib.util import bencode
33
from bzrlib.tuned_gzip import GzipFile
36
def topo_iter(vf, versions=None):
40
versions = vf.versions()
41
parents = vf.get_parent_map(versions)
42
def pending_parents(version):
43
return [v for v in parents[version] if v in versions and
45
for version_id in versions:
46
for parent_id in parents[version_id]:
47
descendants.setdefault(parent_id, []).append(version_id)
48
cur = [v for v in versions if len(pending_parents(v)) == 0]
51
for version_id in cur:
52
if version_id in seen:
54
if len(pending_parents(version_id)) != 0:
56
next.extend(descendants.get(version_id, []))
60
assert len(seen) == len(versions)
63
class MultiParent(object):
64
"""A multi-parent diff"""
66
def __init__(self, hunks=None):
73
return "MultiParent(%r)" % self.hunks
75
def __eq__(self, other):
76
if self.__class__ is not other.__class__:
78
return (self.hunks == other.hunks)
81
def from_lines(text, parents=(), left_blocks=None):
82
"""Produce a MultiParent from a list of lines and parents"""
84
matcher = patiencediff.PatienceSequenceMatcher(None, parent,
86
return matcher.get_matching_blocks()
88
if left_blocks is None:
89
left_blocks = compare(parents[0])
90
parent_comparisons = [left_blocks] + [compare(p) for p in
93
parent_comparisons = []
95
new_text = NewText([])
97
block_iter = [iter(i) for i in parent_comparisons]
98
diff = MultiParent([])
101
return block_iter[p].next()
102
except StopIteration:
104
cur_block = [next_block(p) for p, i in enumerate(block_iter)]
105
while cur_line < len(text):
107
for p, block in enumerate(cur_block):
111
while j + n <= cur_line:
112
block = cur_block[p] = next_block(p)
120
offset = cur_line - j
126
if best_match is None or n > best_match.num_lines:
127
best_match = ParentText(p, i, j, n)
128
if best_match is None:
129
new_text.lines.append(text[cur_line])
132
if len(new_text.lines) > 0:
133
diff.hunks.append(new_text)
134
new_text = NewText([])
135
diff.hunks.append(best_match)
136
cur_line += best_match.num_lines
137
if len(new_text.lines) > 0:
138
diff.hunks.append(new_text)
141
def get_matching_blocks(self, parent, parent_len):
142
for hunk in self.hunks:
143
if not isinstance(hunk, ParentText) or hunk.parent != parent:
145
yield (hunk.parent_pos, hunk.child_pos, hunk.num_lines)
146
yield parent_len, self.num_lines(), 0
148
def to_lines(self, parents=()):
149
"""Contruct a fulltext from this diff and its parents"""
150
mpvf = MultiMemoryVersionedFile()
151
for num, parent in enumerate(parents):
152
mpvf.add_version(StringIO(parent).readlines(), num, [])
153
mpvf.add_diff(self, 'a', range(len(parents)))
154
return mpvf.get_line_list(['a'])[0]
157
def from_texts(cls, text, parents=()):
158
"""Produce a MultiParent from a text and list of parent text"""
159
return cls.from_lines(StringIO(text).readlines(),
160
[StringIO(p).readlines() for p in parents])
163
"""Yield text lines for a patch"""
164
for hunk in self.hunks:
165
for line in hunk.to_patch():
169
return len(''.join(self.to_patch()))
171
def zipped_patch_len(self):
172
return len(gzip_string(self.to_patch()))
175
def from_patch(cls, text):
176
"""Create a MultiParent from its string form"""
177
return cls._from_patch(StringIO(text))
180
def _from_patch(lines):
181
"""This is private because it is essential to split lines on \n only"""
182
line_iter = iter(lines)
187
cur_line = line_iter.next()
188
except StopIteration:
190
if cur_line[0] == 'i':
191
num_lines = int(cur_line.split(' ')[1])
192
hunk_lines = [line_iter.next() for x in xrange(num_lines)]
193
hunk_lines[-1] = hunk_lines[-1][:-1]
194
hunks.append(NewText(hunk_lines))
195
elif cur_line[0] == '\n':
196
hunks[-1].lines[-1] += '\n'
198
assert cur_line[0] == 'c', cur_line[0]
199
parent, parent_pos, child_pos, num_lines =\
200
[int(v) for v in cur_line.split(' ')[1:]]
201
hunks.append(ParentText(parent, parent_pos, child_pos,
203
return MultiParent(hunks)
205
def range_iterator(self):
206
"""Iterate through the hunks, with range indicated
208
kind is "new" or "parent".
209
for "new", data is a list of lines.
210
for "parent", data is (parent, parent_start, parent_end)
211
:return: a generator of (start, end, kind, data)
214
for hunk in self.hunks:
215
if isinstance(hunk, NewText):
217
end = start + len(hunk.lines)
221
start = hunk.child_pos
222
end = start + hunk.num_lines
223
data = (hunk.parent, hunk.parent_pos, hunk.parent_pos +
225
yield start, end, kind, data
229
"""The number of lines in the output text"""
231
for hunk in reversed(self.hunks):
232
if isinstance(hunk, ParentText):
233
return hunk.child_pos + hunk.num_lines + extra_n
234
extra_n += len(hunk.lines)
237
def is_snapshot(self):
238
"""Return true of this hunk is effectively a fulltext"""
239
if len(self.hunks) != 1:
241
return (isinstance(self.hunks[0], NewText))
244
class NewText(object):
245
"""The contents of text that is introduced by this text"""
247
def __init__(self, lines):
250
def __eq__(self, other):
251
if self.__class__ is not other.__class__:
253
return (other.lines == self.lines)
256
return 'NewText(%r)' % self.lines
259
yield 'i %d\n' % len(self.lines)
260
for line in self.lines:
265
class ParentText(object):
266
"""A reference to text present in a parent text"""
268
def __init__(self, parent, parent_pos, child_pos, num_lines):
270
self.parent_pos = parent_pos
271
self.child_pos = child_pos
272
self.num_lines = num_lines
275
return 'ParentText(%(parent)r, %(parent_pos)r, %(child_pos)r,'\
276
' %(num_lines)r)' % self.__dict__
278
def __eq__(self, other):
279
if self.__class__ != other.__class__:
281
return (self.__dict__ == other.__dict__)
284
yield 'c %(parent)d %(parent_pos)d %(child_pos)d %(num_lines)d\n'\
288
class BaseVersionedFile(object):
289
"""Pseudo-VersionedFile skeleton for MultiParent"""
291
def __init__(self, snapshot_interval=25, max_snapshots=None):
294
self._snapshots = set()
295
self.snapshot_interval = snapshot_interval
296
self.max_snapshots = max_snapshots
299
return iter(self._parents)
301
def has_version(self, version):
302
return version in self._parents
304
def do_snapshot(self, version_id, parent_ids):
305
"""Determine whether to perform a a snapshot for this version"""
306
if self.snapshot_interval is None:
308
if self.max_snapshots is not None and\
309
len(self._snapshots) == self.max_snapshots:
311
if len(parent_ids) == 0:
313
for ignored in xrange(self.snapshot_interval):
314
if len(parent_ids) == 0:
316
version_ids = parent_ids
318
for version_id in version_ids:
319
if version_id not in self._snapshots:
320
parent_ids.extend(self._parents[version_id])
324
def add_version(self, lines, version_id, parent_ids,
325
force_snapshot=None, single_parent=False):
326
"""Add a version to the versionedfile
328
:param lines: The list of lines to add. Must be split on '\n'.
329
:param version_id: The version_id of the version to add
330
:param force_snapshot: If true, force this version to be added as a
331
snapshot version. If false, force this version to be added as a
332
diff. If none, determine this automatically.
333
:param single_parent: If true, use a single parent, rather than
336
if force_snapshot is None:
337
do_snapshot = self.do_snapshot(version_id, parent_ids)
339
do_snapshot = force_snapshot
341
self._snapshots.add(version_id)
342
diff = MultiParent([NewText(lines)])
345
parent_lines = self.get_line_list(parent_ids[:1])
347
parent_lines = self.get_line_list(parent_ids)
348
diff = MultiParent.from_lines(lines, parent_lines)
349
if diff.is_snapshot():
350
self._snapshots.add(version_id)
351
self.add_diff(diff, version_id, parent_ids)
352
self._lines[version_id] = lines
354
def get_parents(self, version_id):
355
return self._parents[version_id]
357
def make_snapshot(self, version_id):
358
snapdiff = MultiParent([NewText(self.cache_version(version_id))])
359
self.add_diff(snapdiff, version_id, self._parents[version_id])
360
self._snapshots.add(version_id)
362
def import_versionedfile(self, vf, snapshots, no_cache=True,
363
single_parent=False, verify=False):
364
"""Import all revisions of a versionedfile
366
:param vf: The versionedfile to import
367
:param snapshots: If provided, the revisions to make snapshots of.
368
Otherwise, this will be auto-determined
369
:param no_cache: If true, clear the cache after every add.
370
:param single_parent: If true, omit all but one parent text, (but
371
retain parent metadata).
373
assert no_cache or not verify
374
revisions = set(vf.versions())
375
total = len(revisions)
376
pb = ui.ui_factory.nested_progress_bar()
378
while len(revisions) > 0:
380
for revision in revisions:
381
parents = vf.get_parents(revision)
382
if [p for p in parents if p not in self._parents] != []:
384
lines = [a + ' ' + l for a, l in
385
vf.annotate_iter(revision)]
386
if snapshots is None:
387
force_snapshot = None
389
force_snapshot = (revision in snapshots)
390
self.add_version(lines, revision, parents, force_snapshot,
397
assert lines == self.get_line_list([revision])[0]
399
pb.update('Importing revisions',
400
(total - len(revisions)) + len(added), total)
401
revisions = [r for r in revisions if r not in added]
405
def select_snapshots(self, vf):
406
"""Determine which versions to add as snapshots"""
410
for version_id in topo_iter(vf):
411
potential_build_ancestors = set(vf.get_parents(version_id))
412
parents = vf.get_parents(version_id)
413
if len(parents) == 0:
414
snapshots.add(version_id)
415
build_ancestors[version_id] = set()
417
for parent in vf.get_parents(version_id):
418
potential_build_ancestors.update(build_ancestors[parent])
419
if len(potential_build_ancestors) > self.snapshot_interval:
420
snapshots.add(version_id)
421
build_ancestors[version_id] = set()
423
build_ancestors[version_id] = potential_build_ancestors
426
def select_by_size(self, num):
427
"""Select snapshots for minimum output size"""
428
num -= len(self._snapshots)
429
new_snapshots = self.get_size_ranking()[-num:]
430
return [v for n, v in new_snapshots]
432
def get_size_ranking(self):
433
"""Get versions ranked by size"""
435
new_snapshots = set()
436
for version_id in self.versions():
437
if version_id in self._snapshots:
439
diff_len = self.get_diff(version_id).patch_len()
440
snapshot_len = MultiParent([NewText(
441
self.cache_version(version_id))]).patch_len()
442
versions.append((snapshot_len - diff_len, version_id))
446
def import_diffs(self, vf):
447
"""Import the diffs from another pseudo-versionedfile"""
448
for version_id in vf.versions():
449
self.add_diff(vf.get_diff(version_id), version_id,
450
vf._parents[version_id])
452
def get_build_ranking(self):
453
"""Return revisions sorted by how much they reduce build complexity"""
456
for version_id in topo_iter(self):
457
could_avoid[version_id] = set()
458
if version_id not in self._snapshots:
459
for parent_id in self._parents[version_id]:
460
could_avoid[version_id].update(could_avoid[parent_id])
461
could_avoid[version_id].update(self._parents)
462
could_avoid[version_id].discard(version_id)
463
for avoid_id in could_avoid[version_id]:
464
referenced_by.setdefault(avoid_id, set()).add(version_id)
465
available_versions = list(self.versions())
467
while len(available_versions) > 0:
468
available_versions.sort(key=lambda x:
469
len(could_avoid[x]) *
470
len(referenced_by.get(x, [])))
471
selected = available_versions.pop()
472
ranking.append(selected)
473
for version_id in referenced_by[selected]:
474
could_avoid[version_id].difference_update(
475
could_avoid[selected])
476
for version_id in could_avoid[selected]:
477
referenced_by[version_id].difference_update(
478
referenced_by[selected]
482
def clear_cache(self):
485
def get_line_list(self, version_ids):
486
return [self.cache_version(v) for v in version_ids]
488
def cache_version(self, version_id):
490
return self._lines[version_id]
493
diff = self.get_diff(version_id)
495
reconstructor = _Reconstructor(self, self._lines, self._parents)
496
reconstructor.reconstruct_version(lines, version_id)
497
self._lines[version_id] = lines
501
class MultiMemoryVersionedFile(BaseVersionedFile):
502
"""Memory-backed pseudo-versionedfile"""
504
def __init__(self, snapshot_interval=25, max_snapshots=None):
505
BaseVersionedFile.__init__(self, snapshot_interval, max_snapshots)
508
def add_diff(self, diff, version_id, parent_ids):
509
self._diffs[version_id] = diff
510
self._parents[version_id] = parent_ids
512
def get_diff(self, version_id):
514
return self._diffs[version_id]
516
raise errors.RevisionNotPresent(version_id, self)
522
class MultiVersionedFile(BaseVersionedFile):
523
"""Disk-backed pseudo-versionedfile"""
525
def __init__(self, filename, snapshot_interval=25, max_snapshots=None):
526
BaseVersionedFile.__init__(self, snapshot_interval, max_snapshots)
527
self._filename = filename
528
self._diff_offset = {}
530
def get_diff(self, version_id):
531
start, count = self._diff_offset[version_id]
532
infile = open(self._filename + '.mpknit', 'rb')
535
sio = StringIO(infile.read(count))
538
zip_file = GzipFile(None, mode='rb', fileobj=sio)
540
file_version_id = zip_file.readline()
541
return MultiParent.from_patch(zip_file.read())
545
def add_diff(self, diff, version_id, parent_ids):
546
outfile = open(self._filename + '.mpknit', 'ab')
548
outfile.seek(0, 2) # workaround for windows bug:
549
# .tell() for files opened in 'ab' mode
550
# before any write returns 0
551
start = outfile.tell()
553
zipfile = GzipFile(None, mode='ab', fileobj=outfile)
554
zipfile.writelines(itertools.chain(
555
['version %s\n' % version_id], diff.to_patch()))
561
self._diff_offset[version_id] = (start, end-start)
562
self._parents[version_id] = parent_ids
566
os.unlink(self._filename + '.mpknit')
568
if e.errno != errno.ENOENT:
571
os.unlink(self._filename + '.mpidx')
573
if e.errno != errno.ENOENT:
577
open(self._filename + '.mpidx', 'wb').write(bencode.bencode(
578
(self._parents, list(self._snapshots), self._diff_offset)))
581
self._parents, snapshots, self._diff_offset = bencode.bdecode(
582
open(self._filename + '.mpidx', 'rb').read())
583
self._snapshots = set(snapshots)
586
class _Reconstructor(object):
587
"""Build a text from the diffs, ancestry graph and cached lines"""
589
def __init__(self, diffs, lines, parents):
592
self.parents = parents
595
def reconstruct(self, lines, parent_text, version_id):
596
"""Append the lines referred to by a ParentText to lines"""
597
parent_id = self.parents[version_id][parent_text.parent]
598
end = parent_text.parent_pos + parent_text.num_lines
599
return self._reconstruct(lines, parent_id, parent_text.parent_pos,
602
def _reconstruct(self, lines, req_version_id, req_start, req_end):
603
"""Append lines for the requested version_id range"""
604
# stack of pending range requests
605
if req_start == req_end:
607
pending_reqs = [(req_version_id, req_start, req_end)]
608
while len(pending_reqs) > 0:
609
req_version_id, req_start, req_end = pending_reqs.pop()
610
# lazily allocate cursors for versions
611
if req_version_id in self.lines:
612
lines.extend(self.lines[req_version_id][req_start:req_end])
615
start, end, kind, data, iterator = self.cursor[req_version_id]
617
iterator = self.diffs.get_diff(req_version_id).range_iterator()
618
start, end, kind, data = iterator.next()
619
if start > req_start:
620
iterator = self.diffs.get_diff(req_version_id).range_iterator()
621
start, end, kind, data = iterator.next()
623
# find the first hunk relevant to the request
624
while end <= req_start:
625
start, end, kind, data = iterator.next()
626
self.cursor[req_version_id] = start, end, kind, data, iterator
627
# if the hunk can't satisfy the whole request, split it in two,
628
# and leave the second half for later.
630
pending_reqs.append((req_version_id, end, req_end))
633
lines.extend(data[req_start - start: (req_end - start)])
635
# If the hunk is a ParentText, rewrite it as a range request
636
# for the parent, and make it the next pending request.
637
parent, parent_start, parent_end = data
638
new_version_id = self.parents[req_version_id][parent]
639
new_start = parent_start + req_start - start
640
new_end = parent_end + req_end - end
641
pending_reqs.append((new_version_id, new_start, new_end))
643
def reconstruct_version(self, lines, version_id):
644
length = self.diffs.get_diff(version_id).num_lines()
645
return self._reconstruct(lines, version_id, 0, length)
648
def gzip_string(lines):
650
data_file = GzipFile(None, mode='wb', fileobj=sio)
651
data_file.writelines(lines)
653
return sio.getvalue()
added
removed
bzrlib/multiparent.py
