]> git.ipfire.org Git - thirdparty/git.git/blame - xdiff/xutils.c
Merge branch 'dl/reset-doc-no-wrt-abbrev'
[thirdparty/git.git] / xdiff / xutils.c
CommitLineData
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
30long 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
43int 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
65void *xdl_mmfile_first(mmfile_t *mmf, long *size)
66{
67 *size = mmf->size;
68 return mmf->ptr;
69}
70
71
3443546f
LT
72long xdl_mmfile_size(mmfile_t *mmf)
73{
74 return mmf->size;
75}
76
77
78int 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
90void 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
100void *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 125long 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
146int 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 */
163static 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
177int 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
256static 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
301unsigned 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
317unsigned 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
325int 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
347static 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
396int 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
409int 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}