1/* See LICENSE file for copyright and license details. */
2#include "../diffutil.h"
3#include "../text.h"
4#include "../util.h"
5
6#include <ctype.h>
7#include <stdio.h>
8#include <stdlib.h>
9#include <string.h>
10
11static int
12read_all(FILE *fp, char **out, size_t *outlen, const char *path)
13{
14 char buf[8192];
15 char *data;
16 size_t cap, len;
17 ssize_t n;
18
19 data = NULL;
20 cap = len = 0;
21 while ((n = fread(buf, 1, sizeof(buf), fp)) > 0) {
22 if (len + (size_t)n > cap) {
23 cap = (len + (size_t)n) * 2 + 64;
24 data = erealloc(data, cap);
25 }
26 memcpy(data + len, buf, (size_t)n);
27 len += (size_t)n;
28 }
29 if (ferror(fp)) {
30 weprintf("read %s:", path);
31 free(data);
32 return -1;
33 }
34 if (!data) {
35 data = emalloc(1);
36 data[0] = '\0';
37 } else if (len == cap) {
38 data = erealloc(data, cap + 1);
39 data[len] = '\0';
40 }
41 *out = data;
42 *outlen = len;
43 return 0;
44}
45
46static void
47split_lines(struct diffline **out, size_t *outn, char *data, size_t len)
48{
49 struct diffline *lines;
50 size_t i, n, start;
51
52 n = 0;
53 for (i = 0; i < len; i++)
54 if (data[i] == '\n')
55 n++;
56 if (len > 0 && (len == 0 || data[len - 1] != '\n'))
57 n++;
58 if (n == 0) {
59 *out = NULL;
60 *outn = 0;
61 return;
62 }
63 lines = ecalloc(n, sizeof(*lines));
64 i = 0;
65 start = 0;
66 for (n = 0; n < (size_t)len; n++) {
67 if (data[n] == '\n') {
68 lines[i].data = data + start;
69 lines[i].len = n - start;
70 i++;
71 start = n + 1;
72 }
73 }
74 if (start < len) {
75 lines[i].data = data + start;
76 lines[i].len = len - start;
77 i++;
78 }
79 *out = lines;
80 *outn = i;
81}
82
83int
84diff_load(struct difffile *df, const char *path)
85{
86 FILE *fp;
87 char *data;
88 size_t len;
89
90 if (!strcmp(path, "-")) {
91 fp = stdin;
92 } else if (!(fp = fopen(path, "r"))) {
93 weprintf("open %s:", path);
94 return -1;
95 }
96 if (read_all(fp, &data, &len, path) < 0) {
97 if (fp != stdin)
98 fclose(fp);
99 return -1;
100 }
101 if (fp != stdin)
102 fclose(fp);
103 df->lines = NULL;
104 df->nlines = 0;
105 if (len == 0) {
106 df->lines = ecalloc(1, sizeof(*df->lines));
107 df->lines[0].data = data;
108 df->lines[0].len = 0;
109 df->nlines = 0;
110 return 0;
111 }
112 split_lines(&df->lines, &df->nlines, data, len);
113 {
114 struct diffline *grown;
115 grown = erealloc(df->lines, (df->nlines + 1) * sizeof(*grown));
116 grown[df->nlines].data = data;
117 grown[df->nlines].len = 0;
118 df->lines = grown;
119 }
120 return 0;
121}
122
123void
124diff_free(struct difffile *df)
125{
126 char *base;
127
128 if (!df->lines)
129 return;
130 if (df->nlines == 0) {
131 free(df->lines[0].data);
132 free(df->lines);
133 df->lines = NULL;
134 df->nlines = 0;
135 return;
136 }
137 base = df->lines[df->nlines].data;
138 free(base);
139 free(df->lines);
140 df->lines = NULL;
141 df->nlines = 0;
142}
143
144static int
145lines_equal(const struct diffline *a, const struct diffline *b, const struct diffopts *opts)
146{
147 size_t i, j;
148
149 if (opts && opts->ignore_blanks) {
150 i = j = 0;
151 while (i < a->len && j < b->len) {
152 while (i < a->len && isspace((unsigned char)a->data[i]))
153 i++;
154 while (j < b->len && isspace((unsigned char)b->data[j]))
155 j++;
156 if (i >= a->len || j >= b->len)
157 break;
158 if (opts->ignore_case) {
159 if (tolower((unsigned char)a->data[i]) != tolower((unsigned char)b->data[j]))
160 return 0;
161 } else if (a->data[i] != b->data[j]) {
162 return 0;
163 }
164 i++;
165 j++;
166 }
167 while (i < a->len && isspace((unsigned char)a->data[i]))
168 i++;
169 while (j < b->len && isspace((unsigned char)b->data[j]))
170 j++;
171 return i == a->len && j == b->len;
172 }
173
174 if (opts && opts->ignore_case) {
175 if (a->len != b->len)
176 return 0;
177 for (i = 0; i < a->len; i++) {
178 if (tolower((unsigned char)a->data[i]) != tolower((unsigned char)b->data[i]))
179 return 0;
180 }
181 return 1;
182 }
183
184 if (a->len != b->len)
185 return 0;
186 return memcmp(a->data, b->data, a->len) == 0;
187}
188
189struct lcs_cell {
190 int diag;
191 int up;
192 int left;
193};
194
195int
196diff_compute(
197 struct diffhunks *hunks,
198 const struct difffile *old,
199 const struct difffile *new,
200 const struct diffopts *opts
201)
202{
203 struct lcs_cell *c;
204 size_t n, m, i, j, k, cap;
205 struct diffhunk *h;
206 int *xs, *ys;
207 size_t hfrom, hto, vfrom, vto;
208 struct diffopts default_opts;
209
210 if (!opts) {
211 memset(&default_opts, 0, sizeof(default_opts));
212 default_opts.context = 3;
213 opts = &default_opts;
214 }
215
216 n = old->nlines;
217 m = new->nlines;
218
219 if (n == 0 && m == 0) {
220 hunks->v = NULL;
221 hunks->n = 0;
222 return 0;
223 }
224
225 c = ecalloc((n + 1) * (m + 1), sizeof(*c));
226 for (i = 0; i <= n; i++) {
227 for (j = 0; j <= m; j++) {
228 if (i == 0 && j == 0) {
229 c[i * (m + 1) + j].diag = 0;
230 continue;
231 }
232 if (i > 0 && j > 0 && lines_equal(&old->lines[i - 1], &new->lines[j - 1], opts)) {
233 c[i * (m + 1) + j].diag = c[(i - 1) * (m + 1) + (j - 1)].diag + 1;
234 c[i * (m + 1) + j].up = 0;
235 c[i * (m + 1) + j].left = 0;
236 continue;
237 }
238 if (i > 0 && (j == 0 || c[(i - 1) * (m + 1) + j].diag >= c[i * (m + 1) + (j - 1)].diag)) {
239 c[i * (m + 1) + j].diag = c[(i - 1) * (m + 1) + j].diag;
240 c[i * (m + 1) + j].up = 1;
241 c[i * (m + 1) + j].left = 0;
242 } else {
243 c[i * (m + 1) + j].diag = c[i * (m + 1) + (j - 1)].diag;
244 c[i * (m + 1) + j].up = 0;
245 c[i * (m + 1) + j].left = 1;
246 }
247 }
248 }
249
250 cap = n + m + 16;
251 xs = ecalloc(cap, sizeof(*xs));
252 ys = ecalloc(cap, sizeof(*ys));
253 k = 0;
254 i = n;
255 j = m;
256 while (i > 0 || j > 0) {
257 if (i > 0 && j > 0 && lines_equal(&old->lines[i - 1], &new->lines[j - 1], opts)) {
258 xs[k] = 0;
259 ys[k] = 0;
260 i--;
261 j--;
262 } else if (i > 0 && c[i * (m + 1) + j].up) {
263 xs[k] = 1;
264 ys[k] = 0;
265 i--;
266 } else {
267 xs[k] = 0;
268 ys[k] = 2;
269 j--;
270 }
271 k++;
272 }
273 hunks->v = NULL;
274 hunks->n = 0;
275 h = NULL;
276 i = 0;
277 j = 0;
278 {
279 size_t step, idx;
280 int op;
281 step = k;
282 while (step > 0) {
283 idx = step - 1;
284 op = xs[idx] | ys[idx];
285 if (op == 0) {
286 step--;
287 i++;
288 j++;
289 continue;
290 }
291 hfrom = i;
292 vfrom = j;
293 hto = i;
294 vto = j;
295 while (step > 0) {
296 idx = step - 1;
297 op = xs[idx] | ys[idx];
298 if (op == 0)
299 break;
300 if (xs[idx] == 1)
301 hto++;
302 if (ys[idx] == 2)
303 vto++;
304 step--;
305 }
306 i = hto;
307 j = vto;
308 hunks->v = erealloc(hunks->v, (hunks->n + 1) * sizeof(*h));
309 h = &hunks->v[hunks->n];
310 h->old.from = hfrom;
311 h->old.to = hto;
312 h->new.from = vfrom;
313 h->new.to = vto;
314 hunks->n++;
315 }
316 }
317 free(c);
318 free(xs);
319 free(ys);
320 return 0;
321}
322
323void
324diff_hunks_free(struct diffhunks *hunks)
325{
326 if (!hunks)
327 return;
328 free(hunks->v);
329 hunks->v = NULL;
330 hunks->n = 0;
331}
332
333int
334diff_looks_binary(const struct difffile *df)
335{
336 size_t i, scan;
337
338 scan = 4096;
339 for (i = 0; i < df->nlines && scan > 0; i++) {
340 size_t take = df->lines[i].len < scan ? df->lines[i].len : scan;
341 if (memchr(df->lines[i].data, '\0', take))
342 return 1;
343 scan -= take;
344 }
345 return 0;
346}
347
348static void
349print_range(FILE *out, size_t from, size_t to)
350{
351 if (to - from <= 1)
352 fprintf(out, "%zu", from + 1);
353 else
354 fprintf(out, "%zu,%zu", from + 1, to);
355}
356
357static void
358print_lines(FILE *out, const struct diffline *lines, size_t from, size_t to, char prefix)
359{
360 size_t i;
361 for (i = from; i < to; i++) {
362 fputc(prefix, out);
363 fwrite(lines[i].data, 1, lines[i].len, out);
364 fputc('\n', out);
365 }
366}
367
368static int
369format_normal(
370 FILE *out, const struct diffhunks *hunks, const struct difffile *old, const struct difffile *new
371)
372{
373 size_t i;
374 for (i = 0; i < hunks->n; i++) {
375 struct diffhunk *h = &hunks->v[i];
376 size_t oldn = h->old.to - h->old.from;
377 size_t newn = h->new.to - h->new.from;
378 char oc;
379
380 oc = oldn == 0 ? 'a' : (newn == 0 ? 'd' : 'c');
381 print_range(out, h->old.from, h->old.to);
382 fputc(oc, out);
383 print_range(out, h->new.from, h->new.to);
384 fputc('\n', out);
385 if (oldn && newn) {
386 print_lines(out, old->lines, h->old.from, h->old.to, '<');
387 fprintf(out, "---\n");
388 print_lines(out, new->lines, h->new.from, h->new.to, '>');
389 } else if (oldn) {
390 print_lines(out, old->lines, h->old.from, h->old.to, '<');
391 } else {
392 print_lines(out, new->lines, h->new.from, h->new.to, '>');
393 }
394 }
395 return 0;
396}
397
398static void
399emit_unified_hunk(
400 FILE *out,
401 const struct diffhunk *h,
402 const struct difffile *old,
403 const struct difffile *new,
404 size_t ctx
405)
406{
407 size_t oldfrom, oldto, newfrom, newto;
408 size_t i;
409
410 oldfrom = h->old.from < ctx ? 0 : h->old.from - ctx;
411 oldto = h->old.to + ctx;
412 if (oldto > old->nlines)
413 oldto = old->nlines;
414 newfrom = h->new.from < ctx ? 0 : h->new.from - ctx;
415 newto = h->new.to + ctx;
416 if (newto > new->nlines)
417 newto = new->nlines;
418
419 if (oldto - oldfrom <= 1)
420 fprintf(out, "@@ -%zu +%zu,%zu @@\n", oldfrom + 1, newfrom + 1, newto - newfrom);
421 else if (newto - newfrom <= 1)
422 fprintf(out, "@@ -%zu,%zu +%zu @@\n", oldfrom + 1, oldto - oldfrom, newfrom + 1);
423 else
424 fprintf(
425 out, "@@ -%zu,%zu +%zu,%zu @@\n", oldfrom + 1, oldto - oldfrom, newfrom + 1, newto - newfrom
426 );
427
428 for (i = oldfrom; i < h->old.from; i++) {
429 fputc(' ', out);
430 fwrite(old->lines[i].data, 1, old->lines[i].len, out);
431 fputc('\n', out);
432 }
433 print_lines(out, old->lines, h->old.from, h->old.to, '-');
434 print_lines(out, new->lines, h->new.from, h->new.to, '+');
435 for (i = h->old.to; i < oldto; i++) {
436 fputc(' ', out);
437 fwrite(old->lines[i].data, 1, old->lines[i].len, out);
438 fputc('\n', out);
439 }
440}
441
442static int
443format_unified(
444 FILE *out,
445 const struct diffhunks *hunks,
446 const struct difffile *old,
447 const struct difffile *new,
448 const char *oldlabel,
449 const char *newlabel,
450 size_t ctx
451)
452{
453 size_t i;
454 if (oldlabel)
455 fprintf(out, "--- %s\n", oldlabel);
456 if (newlabel)
457 fprintf(out, "+++ %s\n", newlabel);
458 for (i = 0; i < hunks->n; i++)
459 emit_unified_hunk(out, &hunks->v[i], old, new, ctx);
460 return 0;
461}
462
463static void
464emit_context_hunk(
465 FILE *out,
466 const struct diffhunk *h,
467 const struct difffile *old,
468 const struct difffile *new,
469 size_t ctx
470)
471{
472 size_t oldfrom, oldto, newfrom, newto;
473 size_t i;
474
475 oldfrom = h->old.from < ctx ? 0 : h->old.from - ctx;
476 oldto = h->old.to + ctx;
477 if (oldto > old->nlines)
478 oldto = old->nlines;
479 newfrom = h->new.from < ctx ? 0 : h->new.from - ctx;
480 newto = h->new.to + ctx;
481 if (newto > new->nlines)
482 newto = new->nlines;
483
484 fprintf(out, "***************\n");
485 if (oldto - oldfrom <= 1)
486 fprintf(out, "*** %zu ****\n", oldfrom + 1);
487 else
488 fprintf(out, "*** %zu,%zu ****\n", oldfrom + 1, oldto - oldfrom);
489 for (i = oldfrom; i < h->old.from; i++) {
490 fputc(' ', out);
491 fwrite(old->lines[i].data, 1, old->lines[i].len, out);
492 fputc('\n', out);
493 }
494 print_lines(out, old->lines, h->old.from, h->old.to, '-');
495 for (i = h->old.to; i < oldto; i++) {
496 fputc(' ', out);
497 fwrite(old->lines[i].data, 1, old->lines[i].len, out);
498 fputc('\n', out);
499 }
500 if (newto - newfrom <= 1)
501 fprintf(out, "--- %zu ----\n", newfrom + 1);
502 else
503 fprintf(out, "--- %zu,%zu ----\n", newfrom + 1, newto - newfrom);
504 for (i = newfrom; i < h->new.from; i++) {
505 fputc(' ', out);
506 fwrite(new->lines[i].data, 1, new->lines[i].len, out);
507 fputc('\n', out);
508 }
509 print_lines(out, new->lines, h->new.from, h->new.to, '+');
510 for (i = h->new.to; i < newto; i++) {
511 fputc(' ', out);
512 fwrite(new->lines[i].data, 1, new->lines[i].len, out);
513 fputc('\n', out);
514 }
515}
516
517static int
518format_context(
519 FILE *out,
520 const struct diffhunks *hunks,
521 const struct difffile *old,
522 const struct difffile *new,
523 const char *oldlabel,
524 const char *newlabel,
525 size_t ctx
526)
527{
528 size_t i;
529 if (oldlabel)
530 fprintf(out, "*** %s\n", oldlabel);
531 if (newlabel)
532 fprintf(out, "--- %s\n", newlabel);
533 for (i = 0; i < hunks->n; i++)
534 emit_context_hunk(out, &hunks->v[i], old, new, ctx);
535 return 0;
536}
537
538static int
539format_ed(
540 FILE *out, const struct diffhunks *hunks, const struct difffile *old, const struct difffile *new
541)
542{
543 size_t i;
544 (void)old;
545 for (i = 0; i < hunks->n; i++) {
546 struct diffhunk *h = &hunks->v[i];
547 size_t oldn = h->old.to - h->old.from;
548 size_t newn = h->new.to - h->new.from;
549 char op;
550
551 op = oldn == 0 ? 'a' : (newn == 0 ? 'd' : 'c');
552 print_range(out, h->old.from, h->old.to);
553 fputc(op, out);
554 fputc('\n', out);
555 if (op == 'a' || op == 'c') {
556 size_t j;
557 for (j = h->new.from; j < h->new.to; j++) {
558 if (new->lines[j].len == 1 && new->lines[j].data[0] == '.')
559 fprintf(out, "..\n");
560 else if (new->lines[j].len == 0)
561 fprintf(out, ".\n");
562 else {
563 fwrite(new->lines[j].data, 1, new->lines[j].len, out);
564 fputc('\n', out);
565 }
566 }
567 fprintf(out, ".\n");
568 }
569 }
570 return 0;
571}
572
573int
574diff_format(
575 FILE *out,
576 const struct diffhunks *hunks,
577 const struct difffile *old,
578 const struct difffile *new,
579 const char *oldlabel,
580 const char *newlabel,
581 const struct diffopts *opts
582)
583{
584 struct diffopts default_opts;
585 size_t ctx;
586
587 if (!opts) {
588 memset(&default_opts, 0, sizeof(default_opts));
589 default_opts.context = 3;
590 opts = &default_opts;
591 }
592 ctx = opts->context ? opts->context : 3;
593 switch (opts->format) {
594 case DIFF_NORMAL:
595 return format_normal(out, hunks, old, new);
596 case DIFF_UNIFIED:
597 return format_unified(out, hunks, old, new, oldlabel, newlabel, ctx);
598 case DIFF_CONTEXT:
599 return format_context(out, hunks, old, new, oldlabel, newlabel, ctx);
600 case DIFF_ED:
601 case DIFF_RCSED:
602 return format_ed(out, hunks, old, new);
603 case DIFF_BRIEF:
604 if (hunks->n > 0)
605 return 1;
606 return 0;
607 }
608 return 0;
609}
