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
19
1
from bzrlib.lazy_import import lazy_import
21
3
lazy_import(globals(), """
26
7
from StringIO import StringIO
28
9
from bzrlib import (
14
from bzrlib.util import bencode
37
def topo_iter_keys(vf, keys=None):
40
parents = vf.get_parent_map(keys)
41
return _topo_iter(parents, keys)
43
def topo_iter(vf, versions=None):
45
versions = vf.versions()
46
parents = vf.get_parent_map(versions)
47
return _topo_iter(parents, versions)
49
def _topo_iter(parents, versions):
16
from bzrlib.tuned_gzip import GzipFile
52
def pending_parents(version):
53
if parents[version] is None:
55
return [v for v in parents[version] if v in versions and
57
for version_id in versions:
58
if parents[version_id] is None:
61
for parent_id in parents[version_id]:
22
for version_id in vf.versions():
23
for parent_id in vf.get_parents(version_id):
62
24
descendants.setdefault(parent_id, []).append(version_id)
63
cur = [v for v in versions if len(pending_parents(v)) == 0]
25
cur = [v for v in vf.versions() if len(vf.get_parents(v)) == 0]
64
26
while len(cur) > 0:
66
28
for version_id in cur:
67
29
if version_id in seen:
69
if len(pending_parents(version_id)) != 0:
31
parents = vf.get_parents(version_id)
32
if not seen.issuperset(parents):
71
34
next.extend(descendants.get(version_id, []))
94
54
return (self.hunks == other.hunks)
97
def from_lines(text, parents=(), left_blocks=None):
57
def from_lines(text, parents=()):
98
58
"""Produce a MultiParent from a list of lines and parents"""
99
59
def compare(parent):
100
60
matcher = patiencediff.PatienceSequenceMatcher(None, parent,
102
62
return matcher.get_matching_blocks()
104
if left_blocks is None:
105
left_blocks = compare(parents[0])
106
parent_comparisons = [left_blocks] + [compare(p) for p in
109
parent_comparisons = []
63
parent_comparisons = [compare(p) for p in parents]
111
65
new_text = NewText([])
154
108
diff.hunks.append(new_text)
157
def get_matching_blocks(self, parent, parent_len):
158
for hunk in self.hunks:
159
if not isinstance(hunk, ParentText) or hunk.parent != parent:
161
yield (hunk.parent_pos, hunk.child_pos, hunk.num_lines)
162
yield parent_len, self.num_lines(), 0
164
def to_lines(self, parents=()):
165
"""Contruct a fulltext from this diff and its parents"""
166
mpvf = MultiMemoryVersionedFile()
167
for num, parent in enumerate(parents):
168
mpvf.add_version(StringIO(parent).readlines(), num, [])
169
mpvf.add_diff(self, 'a', range(len(parents)))
170
return mpvf.get_line_list(['a'])[0]
173
112
def from_texts(cls, text, parents=()):
174
113
"""Produce a MultiParent from a text and list of parent text"""
175
return cls.from_lines(StringIO(text).readlines(),
176
[StringIO(p).readlines() for p in parents])
114
return cls.from_lines(text.splitlines(True),
115
[p.splitlines(True) for p in parents])
178
117
def to_patch(self):
179
118
"""Yield text lines for a patch"""
187
126
def zipped_patch_len(self):
188
127
return len(gzip_string(self.to_patch()))
191
def from_patch(cls, text):
192
"""Create a MultiParent from its string form"""
193
return cls._from_patch(StringIO(text))
196
def _from_patch(lines):
197
"""This is private because it is essential to split lines on \n only"""
130
def from_patch(lines):
131
"""Produce a MultiParent from a sequence of lines"""
198
132
line_iter = iter(lines)
211
145
elif cur_line[0] == '\n':
212
146
hunks[-1].lines[-1] += '\n'
214
if not (cur_line[0] == 'c'):
215
raise AssertionError(cur_line[0])
148
assert cur_line[0] == 'c', cur_line[0]
216
149
parent, parent_pos, child_pos, num_lines =\
217
150
[int(v) for v in cur_line.split(' ')[1:]]
218
151
hunks.append(ParentText(parent, parent_pos, child_pos,
284
213
class ParentText(object):
285
214
"""A reference to text present in a parent text"""
287
__slots__ = ['parent', 'parent_pos', 'child_pos', 'num_lines']
289
216
def __init__(self, parent, parent_pos, child_pos, num_lines):
290
217
self.parent = parent
291
218
self.parent_pos = parent_pos
292
219
self.child_pos = child_pos
293
220
self.num_lines = num_lines
296
return dict(parent=self.parent, parent_pos=self.parent_pos,
297
child_pos=self.child_pos, num_lines=self.num_lines)
299
222
def __repr__(self):
300
return ('ParentText(%(parent)r, %(parent_pos)r, %(child_pos)r,'
301
' %(num_lines)r)' % self._as_dict())
223
return 'ParentText(%(parent)r, %(parent_pos)r, %(child_pos)r,'\
224
' %(num_lines)r)' % self.__dict__
303
226
def __eq__(self, other):
304
if self.__class__ is not other.__class__:
227
if self.__class__ != other.__class__:
306
return self._as_dict() == other._as_dict()
229
return (self.__dict__ == other.__dict__)
308
231
def to_patch(self):
309
yield ('c %(parent)d %(parent_pos)d %(child_pos)d %(num_lines)d\n'
232
yield 'c %(parent)d %(parent_pos)d %(child_pos)d %(num_lines)d\n'\
313
236
class BaseVersionedFile(object):
314
"""Pseudo-VersionedFile skeleton for MultiParent"""
237
"""VersionedFile skeleton for MultiParent"""
316
239
def __init__(self, snapshot_interval=25, max_snapshots=None):
323
246
def versions(self):
324
247
return iter(self._parents)
326
def has_version(self, version):
327
return version in self._parents
329
249
def do_snapshot(self, version_id, parent_ids):
330
"""Determine whether to perform a snapshot for this version"""
331
250
if self.snapshot_interval is None:
333
252
if self.max_snapshots is not None and\
349
268
def add_version(self, lines, version_id, parent_ids,
350
269
force_snapshot=None, single_parent=False):
351
"""Add a version to the versionedfile
353
:param lines: The list of lines to add. Must be split on '\n'.
354
:param version_id: The version_id of the version to add
355
:param force_snapshot: If true, force this version to be added as a
356
snapshot version. If false, force this version to be added as a
357
diff. If none, determine this automatically.
358
:param single_parent: If true, use a single parent, rather than
361
270
if force_snapshot is None:
362
271
do_snapshot = self.do_snapshot(version_id, parent_ids)
420
328
self.clear_cache()
423
if not (lines == self.get_line_list([revision])[0]):
424
raise AssertionError()
331
assert lines == self.get_line_list([revision])[0]
425
332
self.clear_cache()
426
pb.update(gettext('Importing revisions'),
333
pb.update('Importing revisions',
427
334
(total - len(revisions)) + len(added), total)
428
335
revisions = [r for r in revisions if r not in added]
432
339
def select_snapshots(self, vf):
433
"""Determine which versions to add as snapshots"""
434
340
build_ancestors = {}
436
342
snapshots = set()
469
374
versions.append((snapshot_len - diff_len, version_id))
377
return [v for n, v in versions]
473
379
def import_diffs(self, vf):
474
"""Import the diffs from another pseudo-versionedfile"""
475
380
for version_id in vf.versions():
476
381
self.add_diff(vf.get_diff(version_id), version_id,
477
382
vf._parents[version_id])
479
384
def get_build_ranking(self):
480
"""Return revisions sorted by how much they reduce build complexity"""
482
386
referenced_by = {}
483
387
for version_id in topo_iter(self):
520
424
diff = self.get_diff(version_id)
522
reconstructor = _Reconstructor(self, self._lines, self._parents)
426
reconstructor = _Reconstructor(self, self._lines,
523
428
reconstructor.reconstruct_version(lines, version_id)
524
429
self._lines[version_id] = lines
528
433
class MultiMemoryVersionedFile(BaseVersionedFile):
529
"""Memory-backed pseudo-versionedfile"""
531
435
def __init__(self, snapshot_interval=25, max_snapshots=None):
532
436
BaseVersionedFile.__init__(self, snapshot_interval, max_snapshots)
537
441
self._parents[version_id] = parent_ids
539
443
def get_diff(self, version_id):
541
return self._diffs[version_id]
543
raise errors.RevisionNotPresent(version_id, self)
444
return self._diffs[version_id]
545
446
def destroy(self):
549
450
class MultiVersionedFile(BaseVersionedFile):
550
"""Disk-backed pseudo-versionedfile"""
552
452
def __init__(self, filename, snapshot_interval=25, max_snapshots=None):
553
453
BaseVersionedFile.__init__(self, snapshot_interval, max_snapshots)
562
462
sio = StringIO(infile.read(count))
565
zip_file = gzip.GzipFile(None, mode='rb', fileobj=sio)
465
zip_file = GzipFile(None, mode='rb', fileobj=sio)
567
467
file_version_id = zip_file.readline()
568
content = zip_file.read()
569
return MultiParent.from_patch(content)
468
return MultiParent.from_patch(zip_file.readlines())
573
472
def add_diff(self, diff, version_id, parent_ids):
574
473
outfile = open(self._filename + '.mpknit', 'ab')
576
outfile.seek(0, 2) # workaround for windows bug:
577
# .tell() for files opened in 'ab' mode
578
# before any write returns 0
579
475
start = outfile.tell()
581
zipfile = gzip.GzipFile(None, mode='ab', fileobj=outfile)
477
zipfile = GzipFile(None, mode='ab', fileobj=outfile)
582
478
zipfile.writelines(itertools.chain(
583
479
['version %s\n' % version_id], diff.to_patch()))
630
526
def _reconstruct(self, lines, req_version_id, req_start, req_end):
631
527
"""Append lines for the requested version_id range"""
632
528
# stack of pending range requests
633
if req_start == req_end:
635
529
pending_reqs = [(req_version_id, req_start, req_end)]
636
530
while len(pending_reqs) > 0:
637
531
req_version_id, req_start, req_end = pending_reqs.pop()
638
532
# lazily allocate cursors for versions
639
if req_version_id in self.lines:
640
lines.extend(self.lines[req_version_id][req_start:req_end])
643
534
start, end, kind, data, iterator = self.cursor[req_version_id]