1
from bzrlib.lazy_import import lazy_import
3
lazy_import(globals(), """
7
from StringIO import StringIO
14
from bzrlib.util import bencode
16
from bzrlib.tuned_gzip import GzipFile
19
def topo_iter(vf, versions=None):
23
versions = vf.versions()
24
def pending_parents(version):
25
return [v for v in vf.get_parents(version) if v in versions and
27
for version_id in versions:
28
for parent_id in vf.get_parents(version_id):
29
descendants.setdefault(parent_id, []).append(version_id)
30
cur = [v for v in versions if len(pending_parents(v)) == 0]
33
for version_id in cur:
34
if version_id in seen:
36
if len(pending_parents(version_id)) != 0:
38
next.extend(descendants.get(version_id, []))
42
assert len(seen) == len(versions)
45
class MultiParent(object):
47
def __init__(self, hunks=None):
54
return "MultiParent(%r)" % self.hunks
56
def __eq__(self, other):
57
if self.__class__ is not other.__class__:
59
return (self.hunks == other.hunks)
62
def from_lines(text, parents=(), left_blocks=None):
63
"""Produce a MultiParent from a list of lines and parents"""
65
matcher = patiencediff.PatienceSequenceMatcher(None, parent,
67
return matcher.get_matching_blocks()
69
if left_blocks is None:
70
left_blocks = compare(parents[0])
71
parent_comparisons = [left_blocks] + [compare(p) for p in
74
parent_comparisons = []
76
new_text = NewText([])
78
block_iter = [iter(i) for i in parent_comparisons]
79
diff = MultiParent([])
82
return block_iter[p].next()
85
cur_block = [next_block(p) for p, i in enumerate(block_iter)]
86
while cur_line < len(text):
88
for p, block in enumerate(cur_block):
92
while j + n < cur_line:
93
block = cur_block[p] = next_block(p)
101
offset = cur_line - j
107
if best_match is None or n > best_match.num_lines:
108
best_match = ParentText(p, i, j, n)
109
if best_match is None:
110
new_text.lines.append(text[cur_line])
113
if len(new_text.lines) > 0:
114
diff.hunks.append(new_text)
115
new_text = NewText([])
116
diff.hunks.append(best_match)
117
cur_line += best_match.num_lines
118
if len(new_text.lines) > 0:
119
diff.hunks.append(new_text)
123
def from_texts(cls, text, parents=()):
124
"""Produce a MultiParent from a text and list of parent text"""
125
return cls.from_lines(text.splitlines(True),
126
[p.splitlines(True) for p in parents])
129
"""Yield text lines for a patch"""
130
for hunk in self.hunks:
131
for line in hunk.to_patch():
135
return len(''.join(self.to_patch()))
137
def zipped_patch_len(self):
138
return len(gzip_string(self.to_patch()))
141
def from_patch(cls, text):
142
return cls._from_patch(StringIO(text))
145
def _from_patch(lines):
146
"""This is private because it is essential to split lines on \n only"""
147
line_iter = iter(lines)
152
cur_line = line_iter.next()
153
except StopIteration:
155
if cur_line[0] == 'i':
156
num_lines = int(cur_line.split(' ')[1])
157
hunk_lines = [line_iter.next() for x in xrange(num_lines)]
158
hunk_lines[-1] = hunk_lines[-1][:-1]
159
hunks.append(NewText(hunk_lines))
160
elif cur_line[0] == '\n':
161
hunks[-1].lines[-1] += '\n'
163
assert cur_line[0] == 'c', cur_line[0]
164
parent, parent_pos, child_pos, num_lines =\
165
[int(v) for v in cur_line.split(' ')[1:]]
166
hunks.append(ParentText(parent, parent_pos, child_pos,
168
return MultiParent(hunks)
170
def range_iterator(self):
171
"""Iterate through the hunks, with range indicated
173
kind is "new" or "parent".
174
for "new", data is a list of lines.
175
for "parent", data is (parent, parent_start, parent_end)
176
:return: a generator of (start, end, kind, data)
179
for hunk in self.hunks:
180
if isinstance(hunk, NewText):
182
end = start + len(hunk.lines)
186
start = hunk.child_pos
187
end = start + hunk.num_lines
188
data = (hunk.parent, hunk.parent_pos, hunk.parent_pos +
190
yield start, end, kind, data
195
for hunk in reversed(self.hunks):
196
if isinstance(hunk, ParentText):
197
return hunk.child_pos + hunk.num_lines + extra_n
198
extra_n += len(hunk.lines)
201
def is_snapshot(self):
202
if len(self.hunks) != 1:
204
return (isinstance(self.hunks[0], NewText))
207
class NewText(object):
208
"""The contents of text that is introduced by this text"""
210
def __init__(self, lines):
213
def __eq__(self, other):
214
if self.__class__ is not other.__class__:
216
return (other.lines == self.lines)
219
return 'NewText(%r)' % self.lines
222
yield 'i %d\n' % len(self.lines)
223
for line in self.lines:
228
class ParentText(object):
229
"""A reference to text present in a parent text"""
231
def __init__(self, parent, parent_pos, child_pos, num_lines):
233
self.parent_pos = parent_pos
234
self.child_pos = child_pos
235
self.num_lines = num_lines
238
return 'ParentText(%(parent)r, %(parent_pos)r, %(child_pos)r,'\
239
' %(num_lines)r)' % self.__dict__
241
def __eq__(self, other):
242
if self.__class__ != other.__class__:
244
return (self.__dict__ == other.__dict__)
247
yield 'c %(parent)d %(parent_pos)d %(child_pos)d %(num_lines)d\n'\
251
class BaseVersionedFile(object):
252
"""VersionedFile skeleton for MultiParent"""
254
def __init__(self, snapshot_interval=25, max_snapshots=None):
257
self._snapshots = set()
258
self.snapshot_interval = snapshot_interval
259
self.max_snapshots = max_snapshots
262
return iter(self._parents)
264
def has_version(self, version):
265
return version in self._parents
267
def do_snapshot(self, version_id, parent_ids):
268
if self.snapshot_interval is None:
270
if self.max_snapshots is not None and\
271
len(self._snapshots) == self.max_snapshots:
273
if len(parent_ids) == 0:
275
for ignored in xrange(self.snapshot_interval):
276
if len(parent_ids) == 0:
278
version_ids = parent_ids
280
for version_id in version_ids:
281
if version_id not in self._snapshots:
282
parent_ids.extend(self._parents[version_id])
286
def add_version(self, lines, version_id, parent_ids,
287
force_snapshot=None, single_parent=False):
288
if force_snapshot is None:
289
do_snapshot = self.do_snapshot(version_id, parent_ids)
291
do_snapshot = force_snapshot
293
self._snapshots.add(version_id)
294
diff = MultiParent([NewText(lines)])
297
parent_lines = self.get_line_list(parent_ids[:1])
299
parent_lines = self.get_line_list(parent_ids)
300
diff = MultiParent.from_lines(lines, parent_lines)
301
if diff.is_snapshot():
302
self._snapshots.add(version_id)
303
self.add_diff(diff, version_id, parent_ids)
304
self._lines[version_id] = lines
306
def get_parents(self, version_id):
307
return self._parents[version_id]
309
def make_snapshot(self, version_id):
310
snapdiff = MultiParent([NewText(self.cache_version(version_id))])
311
self.add_diff(snapdiff, version_id, self._parents[version_id])
312
self._snapshots.add(version_id)
314
def import_versionedfile(self, vf, snapshots, no_cache=True,
315
single_parent=False, verify=False):
316
"""Import all revisions of a versionedfile
318
:param vf: The versionedfile to import
319
:param snapshots: If provided, the revisions to make snapshots of.
320
Otherwise, this will be auto-determined
321
:param no_cache: If true, clear the cache after every add.
322
:param single_parent: If true, omit all but one parent text, (but
323
retain parent metadata).
325
assert no_cache or not verify
326
revisions = set(vf.versions())
327
total = len(revisions)
328
pb = ui.ui_factory.nested_progress_bar()
330
while len(revisions) > 0:
332
for revision in revisions:
333
parents = vf.get_parents(revision)
334
if [p for p in parents if p not in self._parents] != []:
336
lines = [a + ' ' + l for a, l in
337
vf.annotate_iter(revision)]
338
if snapshots is None:
339
force_snapshot = None
341
force_snapshot = (revision in snapshots)
342
self.add_version(lines, revision, parents, force_snapshot,
349
assert lines == self.get_line_list([revision])[0]
351
pb.update('Importing revisions',
352
(total - len(revisions)) + len(added), total)
353
revisions = [r for r in revisions if r not in added]
357
def select_snapshots(self, vf):
361
for version_id in topo_iter(vf):
362
potential_build_ancestors = set(vf.get_parents(version_id))
363
parents = vf.get_parents(version_id)
364
if len(parents) == 0:
365
snapshots.add(version_id)
366
build_ancestors[version_id] = set()
368
for parent in vf.get_parents(version_id):
369
potential_build_ancestors.update(build_ancestors[parent])
370
if len(potential_build_ancestors) > self.snapshot_interval:
371
snapshots.add(version_id)
372
build_ancestors[version_id] = set()
374
build_ancestors[version_id] = potential_build_ancestors
377
def select_by_size(self, num):
378
"""Select snapshots for minimum output size"""
379
num -= len(self._snapshots)
380
new_snapshots = self.get_size_ranking()[-num:]
381
return [v for n, v in new_snapshots]
383
def get_size_ranking(self):
385
new_snapshots = set()
386
for version_id in self.versions():
387
if version_id in self._snapshots:
389
diff_len = self.get_diff(version_id).patch_len()
390
snapshot_len = MultiParent([NewText(
391
self.cache_version(version_id))]).patch_len()
392
versions.append((snapshot_len - diff_len, version_id))
395
return [v for n, v in versions]
397
def import_diffs(self, vf):
398
for version_id in vf.versions():
399
self.add_diff(vf.get_diff(version_id), version_id,
400
vf._parents[version_id])
402
def get_build_ranking(self):
405
for version_id in topo_iter(self):
406
could_avoid[version_id] = set()
407
if version_id not in self._snapshots:
408
for parent_id in self._parents[version_id]:
409
could_avoid[version_id].update(could_avoid[parent_id])
410
could_avoid[version_id].update(self._parents)
411
could_avoid[version_id].discard(version_id)
412
for avoid_id in could_avoid[version_id]:
413
referenced_by.setdefault(avoid_id, set()).add(version_id)
414
available_versions = list(self.versions())
416
while len(available_versions) > 0:
417
available_versions.sort(key=lambda x:
418
len(could_avoid[x]) *
419
len(referenced_by.get(x, [])))
420
selected = available_versions.pop()
421
ranking.append(selected)
422
for version_id in referenced_by[selected]:
423
could_avoid[version_id].difference_update(
424
could_avoid[selected])
425
for version_id in could_avoid[selected]:
426
referenced_by[version_id].difference_update(
427
referenced_by[selected]
431
def clear_cache(self):
434
def get_line_list(self, version_ids):
435
return [self.cache_version(v) for v in version_ids]
437
def cache_version(self, version_id):
439
return self._lines[version_id]
442
diff = self.get_diff(version_id)
444
reconstructor = _Reconstructor(self, self._lines,
446
reconstructor.reconstruct_version(lines, version_id)
447
self._lines[version_id] = lines
451
class MultiMemoryVersionedFile(BaseVersionedFile):
453
def __init__(self, snapshot_interval=25, max_snapshots=None):
454
BaseVersionedFile.__init__(self, snapshot_interval, max_snapshots)
457
def add_diff(self, diff, version_id, parent_ids):
458
self._diffs[version_id] = diff
459
self._parents[version_id] = parent_ids
461
def get_diff(self, version_id):
462
return self._diffs[version_id]
468
class MultiVersionedFile(BaseVersionedFile):
470
def __init__(self, filename, snapshot_interval=25, max_snapshots=None):
471
BaseVersionedFile.__init__(self, snapshot_interval, max_snapshots)
472
self._filename = filename
473
self._diff_offset = {}
475
def get_diff(self, version_id):
476
start, count = self._diff_offset[version_id]
477
infile = open(self._filename + '.mpknit', 'rb')
480
sio = StringIO(infile.read(count))
483
zip_file = GzipFile(None, mode='rb', fileobj=sio)
485
file_version_id = zip_file.readline()
486
return MultiParent.from_patch(zip_file.read())
490
def add_diff(self, diff, version_id, parent_ids):
491
outfile = open(self._filename + '.mpknit', 'ab')
493
start = outfile.tell()
495
zipfile = GzipFile(None, mode='ab', fileobj=outfile)
496
zipfile.writelines(itertools.chain(
497
['version %s\n' % version_id], diff.to_patch()))
503
self._diff_offset[version_id] = (start, end-start)
504
self._parents[version_id] = parent_ids
508
os.unlink(self._filename + '.mpknit')
510
if e.errno != errno.ENOENT:
513
os.unlink(self._filename + '.mpidx')
515
if e.errno != errno.ENOENT:
519
open(self._filename + '.mpidx', 'wb').write(bencode.bencode(
520
(self._parents, list(self._snapshots), self._diff_offset)))
523
self._parents, snapshots, self._diff_offset = bencode.bdecode(
524
open(self._filename + '.mpidx', 'rb').read())
525
self._snapshots = set(snapshots)
528
class _Reconstructor(object):
529
"""Build a text from the diffs, ancestry graph and cached lines"""
531
def __init__(self, diffs, lines, parents):
534
self.parents = parents
537
def reconstruct(self, lines, parent_text, version_id):
538
"""Append the lines referred to by a ParentText to lines"""
539
parent_id = self.parents[version_id][parent_text.parent]
540
end = parent_text.parent_pos + parent_text.num_lines
541
return self._reconstruct(lines, parent_id, parent_text.parent_pos,
544
def _reconstruct(self, lines, req_version_id, req_start, req_end):
545
"""Append lines for the requested version_id range"""
546
# stack of pending range requests
547
if req_start == req_end:
549
pending_reqs = [(req_version_id, req_start, req_end)]
550
while len(pending_reqs) > 0:
551
req_version_id, req_start, req_end = pending_reqs.pop()
552
# lazily allocate cursors for versions
554
start, end, kind, data, iterator = self.cursor[req_version_id]
556
iterator = self.diffs.get_diff(req_version_id).range_iterator()
557
start, end, kind, data = iterator.next()
558
if start > req_start:
559
iterator = self.diffs.get_diff(req_version_id).range_iterator()
560
start, end, kind, data = iterator.next()
562
# find the first hunk relevant to the request
563
while end <= req_start:
564
start, end, kind, data = iterator.next()
565
self.cursor[req_version_id] = start, end, kind, data, iterator
566
# if the hunk can't satisfy the whole request, split it in two,
567
# and leave the second half for later.
569
pending_reqs.append((req_version_id, end, req_end))
572
lines.extend(data[req_start - start: (req_end - start)])
574
# If the hunk is a ParentText, rewrite it as a range request
575
# for the parent, and make it the next pending request.
576
parent, parent_start, parent_end = data
577
new_version_id = self.parents[req_version_id][parent]
578
new_start = parent_start + req_start - start
579
new_end = parent_end + req_end - end
580
pending_reqs.append((new_version_id, new_start, new_end))
582
def reconstruct_version(self, lines, version_id):
583
length = self.diffs.get_diff(version_id).num_lines()
584
return self._reconstruct(lines, version_id, 0, length)
587
def gzip_string(lines):
589
data_file = GzipFile(None, mode='wb', fileobj=sio)
590
data_file.writelines(lines)
592
return sio.getvalue()
added
removed
bzrlib/multiparent.py
