mpatch.py
118 lines
| 3.2 KiB
| text/x-python
|
PythonLexer
Martin Geisler
|
r7699 | # mpatch.py - Python implementation of mpatch.c | ||
# | ||||
# Copyright 2009 Matt Mackall <mpm@selenic.com> and others | ||||
# | ||||
Martin Geisler
|
r8225 | # This software may be used and distributed according to the terms of the | ||
Matt Mackall
|
r10263 | # GNU General Public License version 2 or any later version. | ||
Martin Geisler
|
r7699 | |||
Martin Geisler
|
r7775 | import struct | ||
try: | ||||
from cStringIO import StringIO | ||||
except ImportError: | ||||
from StringIO import StringIO | ||||
Martin Geisler
|
r7699 | |||
# This attempts to apply a series of patches in time proportional to | ||||
# the total size of the patches, rather than patches * len(text). This | ||||
# means rather than shuffling strings around, we shuffle around | ||||
# pointers to fragments with fragment lists. | ||||
# | ||||
# When the fragment lists get too long, we collapse them. To do this | ||||
# efficiently, we do all our operations inside a buffer created by | ||||
# mmap and simply use memmove. This avoids creating a bunch of large | ||||
# temporary string buffers. | ||||
def patches(a, bins): | ||||
Matt Mackall
|
r10282 | if not bins: | ||
return a | ||||
Martin Geisler
|
r7699 | |||
plens = [len(x) for x in bins] | ||||
pl = sum(plens) | ||||
bl = len(a) + pl | ||||
tl = bl + bl + pl # enough for the patches and two working texts | ||||
b1, b2 = 0, bl | ||||
Matt Mackall
|
r10282 | if not tl: | ||
return a | ||||
Martin Geisler
|
r7699 | |||
Martin Geisler
|
r7775 | m = StringIO() | ||
def move(dest, src, count): | ||||
"""move count bytes from src to dest | ||||
The file pointer is left at the end of dest. | ||||
""" | ||||
m.seek(src) | ||||
buf = m.read(count) | ||||
m.seek(dest) | ||||
m.write(buf) | ||||
Martin Geisler
|
r7699 | |||
# load our original text | ||||
m.write(a) | ||||
frags = [(len(a), b1)] | ||||
# copy all the patches into our segment so we can memmove from them | ||||
pos = b2 + bl | ||||
m.seek(pos) | ||||
for p in bins: m.write(p) | ||||
def pull(dst, src, l): # pull l bytes from src | ||||
while l: | ||||
Dan Villiom Podlaski Christiansen
|
r14065 | f = src.pop() | ||
Martin Geisler
|
r7699 | if f[0] > l: # do we need to split? | ||
Dan Villiom Podlaski Christiansen
|
r14065 | src.append((f[0] - l, f[1] + l)) | ||
Martin Geisler
|
r7699 | dst.append((l, f[1])) | ||
return | ||||
dst.append(f) | ||||
l -= f[0] | ||||
def collect(buf, list): | ||||
start = buf | ||||
Dan Villiom Podlaski Christiansen
|
r14065 | for l, p in reversed(list): | ||
Martin Geisler
|
r7775 | move(buf, p, l) | ||
Martin Geisler
|
r7699 | buf += l | ||
return (buf - start, start) | ||||
for plen in plens: | ||||
# if our list gets too long, execute it | ||||
if len(frags) > 128: | ||||
b2, b1 = b1, b2 | ||||
frags = [collect(b1, frags)] | ||||
new = [] | ||||
end = pos + plen | ||||
last = 0 | ||||
while pos < end: | ||||
Martin Geisler
|
r7775 | m.seek(pos) | ||
p1, p2, l = struct.unpack(">lll", m.read(12)) | ||||
Martin Geisler
|
r7699 | pull(new, frags, p1 - last) # what didn't change | ||
pull([], frags, p2 - p1) # what got deleted | ||||
Brodie Rao
|
r16683 | new.append((l, pos + 12)) # what got added | ||
Martin Geisler
|
r7699 | pos += l + 12 | ||
last = p2 | ||||
Brodie Rao
|
r16683 | frags.extend(reversed(new)) # what was left at the end | ||
Martin Geisler
|
r7699 | |||
t = collect(b2, frags) | ||||
Martin Geisler
|
r7775 | m.seek(t[1]) | ||
return m.read(t[0]) | ||||
Martin Geisler
|
r7699 | |||
def patchedsize(orig, delta): | ||||
outlen, last, bin = 0, 0, 0 | ||||
binend = len(delta) | ||||
data = 12 | ||||
while data <= binend: | ||||
decode = delta[bin:bin + 12] | ||||
start, end, length = struct.unpack(">lll", decode) | ||||
if start > end: | ||||
break | ||||
bin = data + length | ||||
data = bin + 12 | ||||
outlen += start - last | ||||
last = end | ||||
outlen += length | ||||
if bin != binend: | ||||
Matt Mackall
|
r11122 | raise ValueError("patch cannot be decoded") | ||
Martin Geisler
|
r7699 | |||
outlen += orig - last | ||||
return outlen | ||||