1/* See LICENSE file for copyright and license details. */
2#include "config.h"
3#include "diffutil.h"
4#include "util.h"
5
6#include <ctype.h>
7#include <stdio.h>
8#include <stdlib.h>
9#include <string.h>
10#include <unistd.h>
11
12struct region {
13 size_t from;
14 size_t to;
15};
16
17struct pair_hunk {
18 struct region old;
19 struct region new;
20};
21
22enum hunk_kind {
23 HUNK_NONE,
24 HUNK_TYPE1,
25 HUNK_TYPE2,
26 HUNK_TYPE3,
27};
28
29struct three_hunk {
30 enum hunk_kind kind;
31 struct region r1;
32 struct region r2;
33 struct region r3;
34 int dup;
35};
36
37static int aflag;
38static int Tflag;
39static int eflag;
40static int Eflag;
41static int xflag;
42static int Xflag;
43static int Aflag;
44static int mflag;
45static int iflag;
46static int strip_cr;
47static char *labels[3];
48static int nlabels;
49
50static void
51usage(void)
52{
53 eprintf("usage: %s [-3aAeEimTxX] [-L label] file1 file2 file3\n", argv0);
54}
55
56static void
57convert_hunks(const struct diffhunks *in, struct pair_hunk **out, size_t *outn)
58{
59 size_t i;
60 struct pair_hunk *p;
61
62 p = ecalloc(in->n + 1, sizeof(*p));
63 for (i = 0; i < in->n; i++) {
64 p[i].old.from = in->v[i].old.from;
65 p[i].old.to = in->v[i].old.to;
66 p[i].new.from = in->v[i].new.from;
67 p[i].new.to = in->v[i].new.to;
68 }
69 *out = p;
70 *outn = in->n;
71}
72
73static int
74region_same(
75 const struct difffile *a, struct region *ra, const struct difffile *b, struct region *rb
76)
77{
78 size_t i;
79 if (ra->to - ra->from != rb->to - rb->from)
80 return 0;
81 for (i = 0; i < ra->to - ra->from; i++) {
82 if (a->lines[ra->from + i].len != b->lines[rb->from + i].len)
83 return 0;
84 if (memcmp(a->lines[ra->from + i].data, b->lines[rb->from + i].data, a->lines[ra->from + i].len)
85 != 0)
86 return 0;
87 }
88 return 1;
89}
90
91static int
92merge_hunks(
93 const struct difffile *f1,
94 const struct difffile *f2,
95 const struct difffile *f3,
96 const struct pair_hunk *d13,
97 size_t n13,
98 const struct pair_hunk *d23,
99 size_t n23,
100 struct three_hunk **out,
101 size_t *outn
102)
103{
104 struct three_hunk *hs;
105 size_t i, j, k, cap;
106 int have1, have2;
107 size_t a1, a2, b1, b2;
108
109 cap = n13 + n23 + 4;
110 hs = ecalloc(cap, sizeof(*hs));
111 k = 0;
112 i = j = 0;
113
114 while (i < n13 || j < n23) {
115 have1 = i < n13;
116 have2 = j < n23;
117 a1 = have1 ? d13[i].new.from : 0;
118 a2 = have1 ? d13[i].new.to : 0;
119 b1 = have2 ? d23[j].old.from : 0;
120 b2 = have2 ? d23[j].old.to : 0;
121
122 if (have1 && (!have2 || a2 <= b1)) {
123 if (k + 1 >= cap) {
124 cap *= 2;
125 hs = erealloc(hs, cap * sizeof(*hs));
126 }
127 hs[k].kind = HUNK_TYPE1;
128 hs[k].r1.from = d13[i].old.from;
129 hs[k].r1.to = d13[i].old.to;
130 hs[k].r2.from = d13[i].new.from;
131 hs[k].r2.to = d13[i].new.to;
132 hs[k].r3.from = d13[i].new.from;
133 hs[k].r3.to = d13[i].new.to;
134 hs[k].dup = 0;
135 k++;
136 i++;
137 continue;
138 }
139 if (have2 && (!have1 || b2 < a1)) {
140 if (k + 1 >= cap) {
141 cap *= 2;
142 hs = erealloc(hs, cap * sizeof(*hs));
143 }
144 hs[k].kind = HUNK_TYPE2;
145 hs[k].r1.from = d23[j].old.from;
146 hs[k].r1.to = d23[j].old.to;
147 hs[k].r2.from = d23[j].old.from;
148 hs[k].r2.to = d23[j].old.to;
149 hs[k].r3.from = d23[j].new.from;
150 hs[k].r3.to = d23[j].new.to;
151 hs[k].dup = 0;
152 k++;
153 j++;
154 continue;
155 }
156 {
157 struct region r2;
158 size_t extra_pre, extra_post;
159
160 r2.from = a1 < b1 ? a1 : b1;
161 r2.to = a2 > b2 ? a2 : b2;
162 extra_pre = (a1 > b1) ? (a1 - b1) : (b1 - a1);
163 extra_post = (a2 > b2) ? (a2 - b2) : (b2 - a2);
164 if (k + 1 >= cap) {
165 cap *= 2;
166 hs = erealloc(hs, cap * sizeof(*hs));
167 }
168 hs[k].kind = HUNK_TYPE3;
169 hs[k].r2 = r2;
170 if (a1 >= b1) {
171 hs[k].r1.from = d13[i].old.from - extra_pre;
172 hs[k].r1.to = d13[i].old.to + extra_post;
173 } else {
174 hs[k].r1.from = d13[i].old.from;
175 hs[k].r1.to = d13[i].old.to + (extra_pre + extra_post);
176 }
177 if (b1 >= a1) {
178 hs[k].r3.from = d23[j].new.from - extra_pre;
179 hs[k].r3.to = d23[j].new.to + extra_post;
180 } else {
181 hs[k].r3.from = d23[j].new.from;
182 hs[k].r3.to = d23[j].new.to + (extra_pre + extra_post);
183 }
184 hs[k].dup = region_same(f1, &hs[k].r1, f3, &hs[k].r3);
185 k++;
186 i++;
187 j++;
188 }
189 }
190 *out = hs;
191 *outn = k;
192 (void)f1;
193 (void)f2;
194 (void)f3;
195 return 0;
196}
197
198static void
199print_lines(const struct difffile *f, size_t from, size_t to)
200{
201 size_t i;
202 for (i = from; i < to; i++) {
203 fwrite(f->lines[i].data, 1, f->lines[i].len, stdout);
204 fputc('\n', stdout);
205 }
206}
207
208static void
209print_range_cmd(FILE *out, size_t from, size_t to, char op)
210{
211 if (to <= from) {
212 fprintf(out, "%zua\n", from == 0 ? 0 : from);
213 } else {
214 fprintf(out, "%zu", from + 1);
215 if (to - from > 1)
216 fprintf(out, ",%zu", to);
217 fprintf(out, "%c\n", op);
218 }
219}
220
221static int
222format_normal(
223 const struct three_hunk *hs,
224 size_t n,
225 const struct difffile *f1,
226 const struct difffile *f2,
227 const struct difffile *f3
228)
229{
230 size_t i;
231 for (i = 0; i < n; i++) {
232 const struct three_hunk *h = &hs[i];
233 const char *tag = "";
234 if (h->kind == HUNK_TYPE1)
235 tag = "1";
236 else if (h->kind == HUNK_TYPE2)
237 tag = "2";
238 else if (h->kind == HUNK_TYPE3)
239 tag = h->dup ? "3" : "";
240 printf("====%s\n", tag);
241 if (h->kind == HUNK_TYPE1) {
242 printf("1:%zu", h->r1.from + 1);
243 if (h->r1.to - h->r1.from > 1)
244 printf(",%zu", h->r1.to);
245 printf("a\n");
246 printf("3:%zu", h->r3.from + 1);
247 if (h->r3.to - h->r3.from > 1)
248 printf(",%zu", h->r3.to);
249 printf("a\n");
250 print_lines(f1, h->r1.from, h->r1.to);
251 } else if (h->kind == HUNK_TYPE2) {
252 printf("2:%zu", h->r2.from + 1);
253 if (h->r2.to - h->r2.from > 1)
254 printf(",%zu", h->r2.to);
255 printf("a\n");
256 printf("3:%zu", h->r3.from + 1);
257 if (h->r3.to - h->r3.from > 1)
258 printf(",%zu", h->r3.to);
259 printf("a\n");
260 print_lines(f3, h->r3.from, h->r3.to);
261 } else {
262 printf("1:%zu", h->r1.from + 1);
263 if (h->r1.to - h->r1.from > 1)
264 printf(",%zu", h->r1.to);
265 printf("c\n");
266 printf("2:%zu", h->r2.from + 1);
267 if (h->r2.to - h->r2.from > 1)
268 printf(",%zu", h->r2.to);
269 printf("c\n");
270 printf("3:%zu", h->r3.from + 1);
271 if (h->r3.to - h->r3.from > 1)
272 printf(",%zu", h->r3.to);
273 printf("c\n");
274 print_lines(f1, h->r1.from, h->r1.to);
275 print_lines(f3, h->r3.from, h->r3.to);
276 }
277 }
278 (void)f2;
279 return 0;
280}
281
282static int
283format_ed(
284 const struct three_hunk *hs,
285 size_t n,
286 int overlap_only,
287 int show_all,
288 const struct difffile *f2,
289 const struct difffile *f3
290)
291{
292 size_t i;
293 for (i = n; i > 0; i--) {
294 const struct three_hunk *h = &hs[i - 1];
295
296 if (h->kind == HUNK_TYPE1) {
297 if (h->r1.to == h->r1.from) {
298 print_range_cmd(stdout, h->r2.from, h->r2.from, 'a');
299 print_lines(f2, h->r2.from, h->r2.from);
300 printf(".\n");
301 } else {
302 print_range_cmd(stdout, h->r2.from, h->r2.to, 'c');
303 print_lines(f2, h->r1.from, h->r1.to);
304 printf(".\n");
305 }
306 continue;
307 }
308 if (h->kind == HUNK_TYPE2) {
309 print_range_cmd(stdout, h->r2.from, h->r2.to, 'c');
310 print_lines(f3, h->r3.from, h->r3.to);
311 printf(".\n");
312 continue;
313 }
314 if (h->dup) {
315 print_range_cmd(stdout, h->r2.from, h->r2.to, 'c');
316 print_lines(f2, h->r1.from, h->r1.to);
317 printf(".\n");
318 continue;
319 }
320 if (overlap_only)
321 continue;
322 if (show_all) {
323 print_range_cmd(stdout, h->r2.from, h->r2.to, 'c');
324 print_lines(f3, h->r3.from, h->r3.to);
325 printf(".\n");
326 }
327 }
328 return 0;
329}
330
331#if FEATURE_DIFF3_MERGE
332static int
333format_merge(
334 const struct three_hunk *hs,
335 size_t n,
336 const struct difffile *f1,
337 const struct difffile *f2,
338 const struct difffile *f3
339)
340{
341 size_t i, j;
342 size_t cursor;
343 const char *l1, *l2, *l3;
344
345 l1 = nlabels >= 1 ? labels[0] : "file1";
346 l2 = nlabels >= 2 ? labels[1] : "file2";
347 l3 = nlabels >= 3 ? labels[2] : "file3";
348 cursor = 0;
349 for (i = 0; i < n; i++) {
350 const struct three_hunk *h = &hs[i];
351 for (j = cursor; j < h->r2.from; j++) {
352 fwrite(f2->lines[j].data, 1, f2->lines[j].len, stdout);
353 fputc('\n', stdout);
354 }
355 cursor = h->r2.to;
356 if (h->kind == HUNK_TYPE1) {
357 print_lines(f1, h->r1.from, h->r1.to);
358 } else if (h->kind == HUNK_TYPE2) {
359 print_lines(f3, h->r3.from, h->r3.to);
360 } else if (h->dup) {
361 print_lines(f1, h->r1.from, h->r1.to);
362 } else {
363 printf("<<<<<<< %s\n", l1);
364 print_lines(f1, h->r1.from, h->r1.to);
365 printf("||||||| %s\n", l2);
366 print_lines(f2, h->r2.from, h->r2.to);
367 printf("=======\n");
368 print_lines(f3, h->r3.from, h->r3.to);
369 printf(">>>>>>> %s\n", l3);
370 }
371 }
372 for (j = cursor; j < f2->nlines; j++) {
373 fwrite(f2->lines[j].data, 1, f2->lines[j].len, stdout);
374 fputc('\n', stdout);
375 }
376 return 0;
377}
378#endif
379
380// ?man diff3: three-way file comparison
381// ?man arguments: file1 file2 file3
382// ?man compare three files line by line and show the differences
383int
384main(int argc, char *argv[])
385{
386 struct difffile f1, f2, f3;
387 struct pair_hunk *d13, *d23;
388 size_t n13, n23;
389 struct three_hunk *hs;
390 size_t nhunks;
391 struct diffhunks raw13, raw23;
392 struct diffopts opts;
393 int ret, conflicts;
394
395 ARGBEGIN
396 {
397 case '3':
398 // ?man -3: like -A but skip overlapping changes
399 Aflag = 1;
400 break;
401 case 'a':
402 // ?man -a: treat all files as text
403 aflag = 1;
404 break;
405 case 'A':
406 // ?man -A: emit ed script with all changes including overlaps
407 Aflag = 1;
408 break;
409 case 'e':
410 // ?man -e: emit ed script to apply non-overlapping changes
411 eflag = 1;
412 break;
413 case 'E':
414 // ?man -E: like -e but include overlap markers
415 Eflag = 1;
416 break;
417#if FEATURE_DIFF3_MERGE
418 case 'i':
419 // ?man -i: ignore case when comparing lines
420 iflag = 1;
421 break;
422 case 'L':
423 // ?man -L:label: use label in place of file name in merge output
424 if (nlabels >= 3)
425 usage();
426 labels[nlabels++] = EARGF(usage());
427 break;
428 case 'm':
429 // ?man -m: emit merged output with conflict markers
430 mflag = 1;
431 break;
432 case 'T':
433 // ?man -T: prefix output lines with a tab
434 Tflag = 1;
435 break;
436#endif
437 case 'x':
438 // ?man -x: emit ed script for overlapping changes only
439 xflag = 1;
440 break;
441 case 'X':
442 // ?man -X: emit ed script for overlapping changes with markers
443 Xflag = 1;
444 break;
445 default:
446 usage();
447 }
448 ARGEND
449
450 if (argc != 3)
451 usage();
452
453 if (diff_load(&f1, argv[0]) < 0)
454 return 2;
455 if (diff_load(&f2, argv[1]) < 0) {
456 diff_free(&f1);
457 return 2;
458 }
459 if (diff_load(&f3, argv[2]) < 0) {
460 diff_free(&f1);
461 diff_free(&f2);
462 return 2;
463 }
464
465 memset(&opts, 0, sizeof(opts));
466 opts.format = DIFF_NORMAL;
467 opts.ignore_case = iflag;
468 opts.strip_cr = strip_cr;
469 opts.context = 3;
470
471 if (diff_compute(&raw13, &f1, &f2, &opts) < 0 || diff_compute(&raw23, &f2, &f3, &opts) < 0) {
472 diff_free(&f1);
473 diff_free(&f2);
474 diff_free(&f3);
475 return 2;
476 }
477 convert_hunks(&raw13, &d13, &n13);
478 convert_hunks(&raw23, &d23, &n23);
479
480 if (merge_hunks(&f1, &f2, &f3, d13, n13, d23, n23, &hs, &nhunks) < 0) {
481 diff_hunks_free(&raw13);
482 diff_hunks_free(&raw23);
483 free(d13);
484 free(d23);
485 diff_free(&f1);
486 diff_free(&f2);
487 diff_free(&f3);
488 return 2;
489 }
490
491 ret = 0;
492 conflicts = 0;
493 if (nhunks == 0) {
494 ret = 0;
495 } else {
496#if FEATURE_DIFF3_MERGE
497 if (mflag) {
498 size_t i;
499 for (i = 0; i < nhunks; i++)
500 if (hs[i].kind == HUNK_TYPE3 && !hs[i].dup)
501 conflicts++;
502 format_merge(hs, nhunks, &f1, &f2, &f3);
503 ret = conflicts ? 1 : 0;
504 } else
505#endif
506 if (eflag || Eflag) {
507 format_ed(hs, nhunks, Eflag && !eflag, 0, &f2, &f3);
508 ret = 1;
509 } else if (xflag) {
510 format_ed(hs, nhunks, 1, 0, &f2, &f3);
511 ret = 1;
512 } else if (Xflag) {
513 format_ed(hs, nhunks, 0, 1, &f2, &f3);
514 ret = 1;
515 } else if (Aflag) {
516 format_ed(hs, nhunks, 0, 1, &f2, &f3);
517 ret = 1;
518 } else {
519 format_normal(hs, nhunks, &f1, &f2, &f3);
520 ret = 1;
521 }
522 }
523
524 if (fshut(stdout, "<stdout>"))
525 ret = 2;
526
527 diff_hunks_free(&raw13);
528 diff_hunks_free(&raw23);
529 free(d13);
530 free(d23);
531 free(hs);
532 diff_free(&f1);
533 diff_free(&f2);
534 diff_free(&f3);
535 return ret;
536}
