mercurial/pure/mpatch.py
author Martin Geisler <mg@lazybytes.net>
Sun, 26 Apr 2009 01:08:54 +0200
changeset 8225 46293a0c7e9f
parent 7775 5280c39778b6
child 10263 25e572394f5c
permissions -rw-r--r--
updated license to be explicit about GPL version 2
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
7699
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
     1
# mpatch.py - Python implementation of mpatch.c
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
     2
#
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
     3
# Copyright 2009 Matt Mackall <mpm@selenic.com> and others
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
     4
#
8225
46293a0c7e9f updated license to be explicit about GPL version 2
Martin Geisler <mg@lazybytes.net>
parents: 7775
diff changeset
     5
# This software may be used and distributed according to the terms of the
46293a0c7e9f updated license to be explicit about GPL version 2
Martin Geisler <mg@lazybytes.net>
parents: 7775
diff changeset
     6
# GNU General Public License version 2, incorporated herein by reference.
7699
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
     7
7775
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
     8
import struct
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
     9
try:
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    10
    from cStringIO import StringIO
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    11
except ImportError:
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    12
    from StringIO import StringIO
7699
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    13
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    14
# This attempts to apply a series of patches in time proportional to
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    15
# the total size of the patches, rather than patches * len(text). This
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    16
# means rather than shuffling strings around, we shuffle around
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    17
# pointers to fragments with fragment lists.
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    18
#
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    19
# When the fragment lists get too long, we collapse them. To do this
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    20
# efficiently, we do all our operations inside a buffer created by
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    21
# mmap and simply use memmove. This avoids creating a bunch of large
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    22
# temporary string buffers.
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    23
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    24
def patches(a, bins):
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    25
    if not bins: return a
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    26
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    27
    plens = [len(x) for x in bins]
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    28
    pl = sum(plens)
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    29
    bl = len(a) + pl
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    30
    tl = bl + bl + pl # enough for the patches and two working texts
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    31
    b1, b2 = 0, bl
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    32
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    33
    if not tl: return a
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    34
7775
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    35
    m = StringIO()
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    36
    def move(dest, src, count):
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    37
        """move count bytes from src to dest
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    38
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    39
        The file pointer is left at the end of dest.
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    40
        """
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    41
        m.seek(src)
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    42
        buf = m.read(count)
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    43
        m.seek(dest)
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    44
        m.write(buf)
7699
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    45
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    46
    # load our original text
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    47
    m.write(a)
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    48
    frags = [(len(a), b1)]
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    49
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    50
    # copy all the patches into our segment so we can memmove from them
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    51
    pos = b2 + bl
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    52
    m.seek(pos)
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    53
    for p in bins: m.write(p)
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    54
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    55
    def pull(dst, src, l): # pull l bytes from src
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    56
        while l:
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    57
            f = src.pop(0)
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    58
            if f[0] > l: # do we need to split?
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    59
                src.insert(0, (f[0] - l, f[1] + l))
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    60
                dst.append((l, f[1]))
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    61
                return
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    62
            dst.append(f)
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    63
            l -= f[0]
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    64
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    65
    def collect(buf, list):
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    66
        start = buf
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    67
        for l, p in list:
7775
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    68
            move(buf, p, l)
7699
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    69
            buf += l
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    70
        return (buf - start, start)
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    71
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    72
    for plen in plens:
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    73
        # if our list gets too long, execute it
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    74
        if len(frags) > 128:
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    75
            b2, b1 = b1, b2
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    76
            frags = [collect(b1, frags)]
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    77
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    78
        new = []
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    79
        end = pos + plen
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    80
        last = 0
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    81
        while pos < end:
7775
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    82
            m.seek(pos)
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    83
            p1, p2, l = struct.unpack(">lll", m.read(12))
7699
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    84
            pull(new, frags, p1 - last) # what didn't change
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    85
            pull([], frags, p2 - p1)    # what got deleted
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    86
            new.append((l, pos + 12))        # what got added
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    87
            pos += l + 12
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    88
            last = p2
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    89
        frags = new + frags                    # what was left at the end
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    90
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    91
    t = collect(b2, frags)
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    92
7775
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    93
    m.seek(t[1])
5280c39778b6 pure/mpatch: use StringIO instead of mmap (issue1493)
Martin Geisler <mg@daimi.au.dk>
parents: 7699
diff changeset
    94
    return m.read(t[0])
7699
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    95
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    96
def patchedsize(orig, delta):
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    97
    outlen, last, bin = 0, 0, 0
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    98
    binend = len(delta)
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
    99
    data = 12
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   100
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   101
    while data <= binend:
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   102
        decode = delta[bin:bin + 12]
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   103
        start, end, length = struct.unpack(">lll", decode)
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   104
        if start > end:
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   105
            break
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   106
        bin = data + length
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   107
        data = bin + 12
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   108
        outlen += start - last
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   109
        last = end
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   110
        outlen += length
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   111
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   112
    if bin != binend:
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   113
        raise Exception("patch cannot be decoded")
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   114
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   115
    outlen += orig - last
fac054f84600 pure Python implementation of mpatch.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
   116
    return outlen