annotate mercurial/pure/mpatch.py @ 9409:57157a224037

highlight: move code from module top-level into extsetup
author Martin Geisler <mg@lazybytes.net>
date Fri, 28 Aug 2009 22:14:04 +0200
parents 46293a0c7e9f
children 25e572394f5c
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
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