1 #!/usr/bin/python |
1 #!/usr/bin/python |
2 import difflib, struct, mmap |
2 import difflib, struct, mmap, mpatchs |
3 |
|
4 devzero = file("/dev/zero") |
|
5 |
3 |
6 def unidiff(a, ad, b, bd, fn): |
4 def unidiff(a, ad, b, bd, fn): |
7 if not a and not b: return "" |
5 if not a and not b: return "" |
8 a = a.splitlines(1) |
6 a = a.splitlines(1) |
9 b = b.splitlines(1) |
7 b = b.splitlines(1) |
61 pos += 12 |
59 pos += 12 |
62 t.append(bin[pos:pos + l]) |
60 t.append(bin[pos:pos + l]) |
63 pos += l |
61 pos += l |
64 return "".join(t) |
62 return "".join(t) |
65 |
63 |
66 # This attempts to apply a series of patches in time proportional to |
|
67 # the total size of the patches, rather than patches * len(text). This |
|
68 # means rather than shuffling strings around, we shuffle around |
|
69 # pointers to fragments with fragment lists. |
|
70 # |
|
71 # When the fragment lists get too long, we collapse them. To do this |
|
72 # efficiently, we do all our operations inside a buffer created by |
|
73 # mmap and simply use memmove. This avoids creating a bunch of large |
|
74 # temporary string buffers. |
|
75 |
|
76 def patches(a, bins): |
|
77 if not bins: return a |
|
78 |
|
79 plens = [len(x) for x in bins] |
|
80 pl = sum(plens) |
|
81 bl = len(a) + pl |
|
82 tl = bl + bl + pl # enough for the patches and two working texts |
|
83 b1, b2 = 0, bl |
|
84 |
|
85 if not tl: return a |
|
86 |
|
87 m = mmap.mmap(devzero.fileno(), tl, mmap.MAP_PRIVATE) |
|
88 |
|
89 # load our original text |
|
90 m.write(a) |
|
91 frags = [(len(a), b1)] |
|
92 |
|
93 # copy all the patches into our segment so we can memmove from them |
|
94 pos = b2 + bl |
|
95 m.seek(pos) |
|
96 for p in bins: m.write(p) |
|
97 |
|
98 def pull(dst, src, l): # pull l bytes from src |
|
99 while l: |
|
100 f = src.pop(0) |
|
101 if f[0] > l: # do we need to split? |
|
102 src.insert(0, (f[0] - l, f[1] + l)) |
|
103 dst.append((l, f[1])) |
|
104 return |
|
105 dst.append(f) |
|
106 l -= f[0] |
|
107 |
|
108 def collect(buf, list): |
|
109 start = buf |
|
110 for l, p in list: |
|
111 m.move(buf, p, l) |
|
112 buf += l |
|
113 return (buf - start, start) |
|
114 |
|
115 for plen in plens: |
|
116 # if our list gets too long, execute it |
|
117 if len(frags) > 128: |
|
118 b2, b1 = b1, b2 |
|
119 frags = [collect(b1, frags)] |
|
120 |
|
121 new = [] |
|
122 end = pos + plen |
|
123 last = 0 |
|
124 while pos < end: |
|
125 p1, p2, l = struct.unpack(">lll", m[pos:pos + 12]) |
|
126 pull(new, frags, p1 - last) # what didn't change |
|
127 pull([], frags, p2 - p1) # what got deleted |
|
128 new.append((l, pos + 12)) # what got added |
|
129 pos += l + 12 |
|
130 last = p2 |
|
131 frags = new + frags # what was left at the end |
|
132 |
|
133 t = collect(b2, frags) |
|
134 |
|
135 return m[t[1]:t[1] + t[0]] |
|
136 |
|
137 def patch(a, bin): |
64 def patch(a, bin): |
138 return patches(a, [bin]) |
65 return patches(a, [bin]) |
139 |
|
140 try: |
|
141 import mpatch |
|
142 patches = mpatch.patches |
|
143 except: |
|
144 pass |
|