diff options
Diffstat (limited to 'websdk/mercurial/mpatch.py')
-rw-r--r-- | websdk/mercurial/mpatch.py | 118 |
1 files changed, 118 insertions, 0 deletions
diff --git a/websdk/mercurial/mpatch.py b/websdk/mercurial/mpatch.py new file mode 100644 index 0000000..760740d --- /dev/null +++ b/websdk/mercurial/mpatch.py @@ -0,0 +1,118 @@ +# mpatch.py - Python implementation of mpatch.c +# +# Copyright 2009 Matt Mackall <mpm@selenic.com> and others +# +# This software may be used and distributed according to the terms of the +# GNU General Public License version 2 or any later version. + +import struct +try: + from cStringIO import StringIO +except ImportError: + from StringIO import StringIO + +# 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): + if not bins: + return a + + 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 + + if not tl: + return a + + 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) + + # 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: + f = src.pop() + if f[0] > l: # do we need to split? + src.append((f[0] - l, f[1] + l)) + dst.append((l, f[1])) + return + dst.append(f) + l -= f[0] + + def collect(buf, list): + start = buf + for l, p in reversed(list): + move(buf, p, l) + 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: + m.seek(pos) + p1, p2, l = struct.unpack(">lll", m.read(12)) + pull(new, frags, p1 - last) # what didn't change + pull([], frags, p2 - p1) # what got deleted + new.append((l, pos + 12)) # what got added + pos += l + 12 + last = p2 + frags.extend(reversed(new)) # what was left at the end + + t = collect(b2, frags) + + m.seek(t[1]) + return m.read(t[0]) + +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: + raise ValueError("patch cannot be decoded") + + outlen += orig - last + return outlen |