]>
Commit | Line | Data |
---|---|---|
3443546f LT |
1 | /* |
2 | * LibXDiff by Davide Libenzi ( File Differential Library ) | |
3 | * Copyright (C) 2003 Davide Libenzi | |
4 | * | |
5 | * This library is free software; you can redistribute it and/or | |
6 | * modify it under the terms of the GNU Lesser General Public | |
7 | * License as published by the Free Software Foundation; either | |
8 | * version 2.1 of the License, or (at your option) any later version. | |
9 | * | |
10 | * This library is distributed in the hope that it will be useful, | |
11 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
13 | * Lesser General Public License for more details. | |
14 | * | |
15 | * You should have received a copy of the GNU Lesser General Public | |
48425792 TZ |
16 | * License along with this library; if not, see |
17 | * <http://www.gnu.org/licenses/>. | |
3443546f LT |
18 | * |
19 | * Davide Libenzi <davidel@xmailserver.org> | |
20 | * | |
21 | */ | |
22 | ||
6942efcf TR |
23 | #include <limits.h> |
24 | #include <assert.h> | |
3443546f LT |
25 | #include "xinclude.h" |
26 | ||
27 | ||
28 | ||
3443546f | 29 | |
ca557aff DL |
30 | long xdl_bogosqrt(long n) { |
31 | long i; | |
32 | ||
33 | /* | |
34 | * Classical integer square root approximation using shifts. | |
35 | */ | |
36 | for (i = 1; n > 0; n >>= 2) | |
37 | i <<= 1; | |
38 | ||
39 | return i; | |
40 | } | |
41 | ||
42 | ||
3443546f LT |
43 | int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize, |
44 | xdemitcb_t *ecb) { | |
d281786f | 45 | int i = 2; |
621c53cc | 46 | mmbuffer_t mb[3]; |
3443546f LT |
47 | |
48 | mb[0].ptr = (char *) pre; | |
49 | mb[0].size = psize; | |
50 | mb[1].ptr = (char *) rec; | |
51 | mb[1].size = size; | |
d281786f JH |
52 | if (size > 0 && rec[size - 1] != '\n') { |
53 | mb[2].ptr = (char *) "\n\\ No newline at end of file\n"; | |
621c53cc | 54 | mb[2].size = strlen(mb[2].ptr); |
d281786f | 55 | i++; |
621c53cc | 56 | } |
611e42a5 | 57 | if (ecb->out_line(ecb->priv, mb, i) < 0) { |
3443546f LT |
58 | |
59 | return -1; | |
60 | } | |
61 | ||
62 | return 0; | |
63 | } | |
64 | ||
65 | void *xdl_mmfile_first(mmfile_t *mmf, long *size) | |
66 | { | |
67 | *size = mmf->size; | |
68 | return mmf->ptr; | |
69 | } | |
70 | ||
71 | ||
3443546f LT |
72 | long xdl_mmfile_size(mmfile_t *mmf) |
73 | { | |
74 | return mmf->size; | |
75 | } | |
76 | ||
77 | ||
78 | int xdl_cha_init(chastore_t *cha, long isize, long icount) { | |
79 | ||
80 | cha->head = cha->tail = NULL; | |
81 | cha->isize = isize; | |
82 | cha->nsize = icount * isize; | |
83 | cha->ancur = cha->sncur = NULL; | |
84 | cha->scurr = 0; | |
85 | ||
86 | return 0; | |
87 | } | |
88 | ||
89 | ||
90 | void xdl_cha_free(chastore_t *cha) { | |
91 | chanode_t *cur, *tmp; | |
92 | ||
93 | for (cur = cha->head; (tmp = cur) != NULL;) { | |
94 | cur = cur->next; | |
95 | xdl_free(tmp); | |
96 | } | |
97 | } | |
98 | ||
99 | ||
100 | void *xdl_cha_alloc(chastore_t *cha) { | |
101 | chanode_t *ancur; | |
102 | void *data; | |
103 | ||
104 | if (!(ancur = cha->ancur) || ancur->icurr == cha->nsize) { | |
105 | if (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) { | |
106 | ||
107 | return NULL; | |
108 | } | |
109 | ancur->icurr = 0; | |
110 | ancur->next = NULL; | |
111 | if (cha->tail) | |
112 | cha->tail->next = ancur; | |
113 | if (!cha->head) | |
114 | cha->head = ancur; | |
115 | cha->tail = ancur; | |
116 | cha->ancur = ancur; | |
117 | } | |
118 | ||
119 | data = (char *) ancur + sizeof(chanode_t) + ancur->icurr; | |
120 | ancur->icurr += cha->isize; | |
121 | ||
122 | return data; | |
123 | } | |
124 | ||
86abba80 | 125 | long xdl_guess_lines(mmfile_t *mf, long sample) { |
3443546f LT |
126 | long nl = 0, size, tsize = 0; |
127 | char const *data, *cur, *top; | |
128 | ||
129 | if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) { | |
739864b1 | 130 | for (top = data + size; nl < sample && cur < top; ) { |
3443546f LT |
131 | nl++; |
132 | if (!(cur = memchr(cur, '\n', top - cur))) | |
133 | cur = top; | |
134 | else | |
135 | cur++; | |
136 | } | |
137 | tsize += (long) (cur - data); | |
138 | } | |
139 | ||
140 | if (nl && tsize) | |
141 | nl = xdl_mmfile_size(mf) / (tsize / nl); | |
142 | ||
143 | return nl + 1; | |
144 | } | |
145 | ||
36617af7 AP |
146 | int xdl_blankline(const char *line, long size, long flags) |
147 | { | |
148 | long i; | |
149 | ||
150 | if (!(flags & XDF_WHITESPACE_FLAGS)) | |
151 | return (size <= 1); | |
152 | ||
153 | for (i = 0; i < size && XDL_ISSPACE(line[i]); i++) | |
154 | ; | |
155 | ||
156 | return (i == size); | |
157 | } | |
158 | ||
e9282f02 JH |
159 | /* |
160 | * Have we eaten everything on the line, except for an optional | |
161 | * CR at the very end? | |
162 | */ | |
163 | static int ends_with_optional_cr(const char *l, long s, long i) | |
164 | { | |
165 | int complete = s && l[s-1] == '\n'; | |
166 | ||
167 | if (complete) | |
168 | s--; | |
169 | if (s == i) | |
170 | return 1; | |
171 | /* do not ignore CR at the end of an incomplete line */ | |
172 | if (complete && s == i + 1 && l[i] == '\r') | |
173 | return 1; | |
174 | return 0; | |
175 | } | |
176 | ||
0d21efa5 JS |
177 | int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags) |
178 | { | |
179 | int i1, i2; | |
180 | ||
b4cf0f17 DR |
181 | if (s1 == s2 && !memcmp(l1, l2, s1)) |
182 | return 1; | |
3b5ef0e2 | 183 | if (!(flags & XDF_WHITESPACE_FLAGS)) |
b4cf0f17 | 184 | return 0; |
3b5ef0e2 JH |
185 | |
186 | i1 = 0; | |
187 | i2 = 0; | |
188 | ||
189 | /* | |
190 | * -w matches everything that matches with -b, and -b in turn | |
e9282f02 JH |
191 | * matches everything that matches with --ignore-space-at-eol, |
192 | * which in turn matches everything that matches with --ignore-cr-at-eol. | |
3b5ef0e2 JH |
193 | * |
194 | * Each flavor of ignoring needs different logic to skip whitespaces | |
195 | * while we have both sides to compare. | |
196 | */ | |
0d21efa5 | 197 | if (flags & XDF_IGNORE_WHITESPACE) { |
3b5ef0e2 JH |
198 | goto skip_ws; |
199 | while (i1 < s1 && i2 < s2) { | |
200 | if (l1[i1++] != l2[i2++]) | |
2344d47f | 201 | return 0; |
3b5ef0e2 | 202 | skip_ws: |
349362cc | 203 | while (i1 < s1 && XDL_ISSPACE(l1[i1])) |
3b5ef0e2 | 204 | i1++; |
349362cc | 205 | while (i2 < s2 && XDL_ISSPACE(l2[i2])) |
3b5ef0e2 | 206 | i2++; |
0d21efa5 | 207 | } |
0d21efa5 | 208 | } else if (flags & XDF_IGNORE_WHITESPACE_CHANGE) { |
3b5ef0e2 | 209 | while (i1 < s1 && i2 < s2) { |
349362cc | 210 | if (XDL_ISSPACE(l1[i1]) && XDL_ISSPACE(l2[i2])) { |
3b5ef0e2 | 211 | /* Skip matching spaces and try again */ |
349362cc | 212 | while (i1 < s1 && XDL_ISSPACE(l1[i1])) |
859f9c45 | 213 | i1++; |
349362cc | 214 | while (i2 < s2 && XDL_ISSPACE(l2[i2])) |
859f9c45 | 215 | i2++; |
3b5ef0e2 | 216 | continue; |
859f9c45 | 217 | } |
3b5ef0e2 JH |
218 | if (l1[i1++] != l2[i2++]) |
219 | return 0; | |
220 | } | |
221 | } else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL) { | |
044fb190 JS |
222 | while (i1 < s1 && i2 < s2 && l1[i1] == l2[i2]) { |
223 | i1++; | |
224 | i2++; | |
225 | } | |
e9282f02 JH |
226 | } else if (flags & XDF_IGNORE_CR_AT_EOL) { |
227 | /* Find the first difference and see how the line ends */ | |
228 | while (i1 < s1 && i2 < s2 && l1[i1] == l2[i2]) { | |
229 | i1++; | |
230 | i2++; | |
231 | } | |
232 | return (ends_with_optional_cr(l1, s1, i1) && | |
233 | ends_with_optional_cr(l2, s2, i2)); | |
3b5ef0e2 JH |
234 | } |
235 | ||
236 | /* | |
237 | * After running out of one side, the remaining side must have | |
238 | * nothing but whitespace for the lines to match. Note that | |
239 | * ignore-whitespace-at-eol case may break out of the loop | |
240 | * while there still are characters remaining on both lines. | |
241 | */ | |
242 | if (i1 < s1) { | |
349362cc | 243 | while (i1 < s1 && XDL_ISSPACE(l1[i1])) |
859f9c45 | 244 | i1++; |
3b5ef0e2 JH |
245 | if (s1 != i1) |
246 | return 0; | |
247 | } | |
248 | if (i2 < s2) { | |
349362cc | 249 | while (i2 < s2 && XDL_ISSPACE(l2[i2])) |
859f9c45 | 250 | i2++; |
3b5ef0e2 JH |
251 | return (s2 == i2); |
252 | } | |
253 | return 1; | |
0d21efa5 | 254 | } |
3443546f | 255 | |
824f782c JS |
256 | static unsigned long xdl_hash_record_with_whitespace(char const **data, |
257 | char const *top, long flags) { | |
3443546f LT |
258 | unsigned long ha = 5381; |
259 | char const *ptr = *data; | |
e9282f02 | 260 | int cr_at_eol_only = (flags & XDF_WHITESPACE_FLAGS) == XDF_IGNORE_CR_AT_EOL; |
3443546f LT |
261 | |
262 | for (; ptr < top && *ptr != '\n'; ptr++) { | |
e9282f02 JH |
263 | if (cr_at_eol_only) { |
264 | /* do not ignore CR at the end of an incomplete line */ | |
265 | if (*ptr == '\r' && | |
266 | (ptr + 1 < top && ptr[1] == '\n')) | |
267 | continue; | |
268 | } | |
269 | else if (XDL_ISSPACE(*ptr)) { | |
859f9c45 | 270 | const char *ptr2 = ptr; |
78ed710f | 271 | int at_eol; |
349362cc | 272 | while (ptr + 1 < top && XDL_ISSPACE(ptr[1]) |
2344d47f | 273 | && ptr[1] != '\n') |
0d21efa5 | 274 | ptr++; |
78ed710f | 275 | at_eol = (top <= ptr + 1 || ptr[1] == '\n'); |
6d12acef KC |
276 | if (flags & XDF_IGNORE_WHITESPACE) |
277 | ; /* already handled */ | |
278 | else if (flags & XDF_IGNORE_WHITESPACE_CHANGE | |
78ed710f | 279 | && !at_eol) { |
0d21efa5 JS |
280 | ha += (ha << 5); |
281 | ha ^= (unsigned long) ' '; | |
282 | } | |
6d12acef | 283 | else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL |
78ed710f | 284 | && !at_eol) { |
859f9c45 JS |
285 | while (ptr2 != ptr + 1) { |
286 | ha += (ha << 5); | |
287 | ha ^= (unsigned long) *ptr2; | |
288 | ptr2++; | |
289 | } | |
290 | } | |
0d21efa5 JS |
291 | continue; |
292 | } | |
3443546f LT |
293 | ha += (ha << 5); |
294 | ha ^= (unsigned long) *ptr; | |
295 | } | |
296 | *data = ptr < top ? ptr + 1: ptr; | |
297 | ||
298 | return ha; | |
299 | } | |
300 | ||
824f782c JS |
301 | unsigned long xdl_hash_record(char const **data, char const *top, long flags) { |
302 | unsigned long ha = 5381; | |
303 | char const *ptr = *data; | |
304 | ||
305 | if (flags & XDF_WHITESPACE_FLAGS) | |
306 | return xdl_hash_record_with_whitespace(data, top, flags); | |
307 | ||
308 | for (; ptr < top && *ptr != '\n'; ptr++) { | |
309 | ha += (ha << 5); | |
310 | ha ^= (unsigned long) *ptr; | |
311 | } | |
312 | *data = ptr < top ? ptr + 1: ptr; | |
313 | ||
314 | return ha; | |
315 | } | |
316 | ||
3443546f LT |
317 | unsigned int xdl_hashbits(unsigned int size) { |
318 | unsigned int val = 1, bits = 0; | |
319 | ||
320 | for (; val < size && bits < CHAR_BIT * sizeof(unsigned int); val <<= 1, bits++); | |
321 | return bits ? bits: 1; | |
322 | } | |
323 | ||
324 | ||
325 | int xdl_num_out(char *out, long val) { | |
326 | char *ptr, *str = out; | |
327 | char buf[32]; | |
328 | ||
329 | ptr = buf + sizeof(buf) - 1; | |
330 | *ptr = '\0'; | |
331 | if (val < 0) { | |
332 | *--ptr = '-'; | |
333 | val = -val; | |
334 | } | |
335 | for (; val && ptr > buf; val /= 10) | |
336 | *--ptr = "0123456789"[val % 10]; | |
337 | if (*ptr) | |
338 | for (; *ptr; ptr++, str++) | |
339 | *str = *ptr; | |
340 | else | |
341 | *str++ = '0'; | |
342 | *str = '\0'; | |
343 | ||
344 | return str - out; | |
345 | } | |
346 | ||
611e42a5 JK |
347 | static int xdl_format_hunk_hdr(long s1, long c1, long s2, long c2, |
348 | const char *func, long funclen, | |
349 | xdemitcb_t *ecb) { | |
3443546f LT |
350 | int nb = 0; |
351 | mmbuffer_t mb; | |
352 | char buf[128]; | |
353 | ||
354 | memcpy(buf, "@@ -", 4); | |
355 | nb += 4; | |
356 | ||
ca557aff | 357 | nb += xdl_num_out(buf + nb, c1 ? s1: s1 - 1); |
3443546f | 358 | |
3ce8f089 JH |
359 | if (c1 != 1) { |
360 | memcpy(buf + nb, ",", 1); | |
361 | nb += 1; | |
3443546f | 362 | |
3ce8f089 JH |
363 | nb += xdl_num_out(buf + nb, c1); |
364 | } | |
3443546f LT |
365 | |
366 | memcpy(buf + nb, " +", 2); | |
367 | nb += 2; | |
368 | ||
ca557aff | 369 | nb += xdl_num_out(buf + nb, c2 ? s2: s2 - 1); |
3443546f | 370 | |
3ce8f089 JH |
371 | if (c2 != 1) { |
372 | memcpy(buf + nb, ",", 1); | |
373 | nb += 1; | |
3443546f | 374 | |
3ce8f089 JH |
375 | nb += xdl_num_out(buf + nb, c2); |
376 | } | |
3443546f | 377 | |
acb72577 MW |
378 | memcpy(buf + nb, " @@", 3); |
379 | nb += 3; | |
380 | if (func && funclen) { | |
381 | buf[nb++] = ' '; | |
382 | if (funclen > sizeof(buf) - nb - 1) | |
383 | funclen = sizeof(buf) - nb - 1; | |
384 | memcpy(buf + nb, func, funclen); | |
385 | nb += funclen; | |
386 | } | |
387 | buf[nb++] = '\n'; | |
3443546f LT |
388 | |
389 | mb.ptr = buf; | |
390 | mb.size = nb; | |
611e42a5 | 391 | if (ecb->out_line(ecb->priv, &mb, 1) < 0) |
3443546f | 392 | return -1; |
611e42a5 JK |
393 | return 0; |
394 | } | |
3443546f | 395 | |
611e42a5 JK |
396 | int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, |
397 | const char *func, long funclen, | |
398 | xdemitcb_t *ecb) { | |
399 | if (!ecb->out_hunk) | |
400 | return xdl_format_hunk_hdr(s1, c1, s2, c2, func, funclen, ecb); | |
401 | if (ecb->out_hunk(ecb->priv, | |
402 | c1 ? s1 : s1 - 1, c1, | |
403 | c2 ? s2 : s2 - 1, c2, | |
404 | func, funclen) < 0) | |
405 | return -1; | |
3443546f LT |
406 | return 0; |
407 | } | |
1d26b252 TRC |
408 | |
409 | int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp, | |
410 | int line1, int count1, int line2, int count2) | |
411 | { | |
412 | /* | |
413 | * This probably does not work outside Git, since | |
414 | * we have a very simple mmfile structure. | |
415 | * | |
416 | * Note: ideally, we would reuse the prepared environment, but | |
417 | * the libxdiff interface does not (yet) allow for diffing only | |
418 | * ranges of lines instead of the whole files. | |
419 | */ | |
420 | mmfile_t subfile1, subfile2; | |
421 | xdfenv_t env; | |
422 | ||
423 | subfile1.ptr = (char *)diff_env->xdf1.recs[line1 - 1]->ptr; | |
424 | subfile1.size = diff_env->xdf1.recs[line1 + count1 - 2]->ptr + | |
425 | diff_env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr; | |
426 | subfile2.ptr = (char *)diff_env->xdf2.recs[line2 - 1]->ptr; | |
427 | subfile2.size = diff_env->xdf2.recs[line2 + count2 - 2]->ptr + | |
428 | diff_env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr; | |
429 | if (xdl_do_diff(&subfile1, &subfile2, xpp, &env) < 0) | |
430 | return -1; | |
431 | ||
432 | memcpy(diff_env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1); | |
433 | memcpy(diff_env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2); | |
434 | ||
435 | xdl_free_env(&env); | |
436 | ||
437 | return 0; | |
438 | } |