1 /* $OpenBSD: diff3prog.c,v 1.21 2021/04/13 14:20:23 stsp Exp $ */
2
3 /*
4 * Copyright (C) Caldera International Inc. 2001-2002.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code and documentation must retain the above
11 * copyright notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. All advertising materials mentioning features or use of this software
16 * must display the following acknowledgement:
17 * This product includes software developed or owned by Caldera
18 * International, Inc.
19 * 4. Neither the name of Caldera International, Inc. nor the names of other
20 * contributors may be used to endorse or promote products derived from
21 * this software without specific prior written permission.
22 *
23 * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
24 * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR
25 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
26 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
27 * IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE FOR ANY DIRECT,
28 * INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
29 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
30 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
32 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
33 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34 * POSSIBILITY OF SUCH DAMAGE.
35 */
36 /*-
37 * Copyright (c) 1991, 1993
38 * The Regents of the University of California. All rights reserved.
39 *
40 * Redistribution and use in source and binary forms, with or without
41 * modification, are permitted provided that the following conditions
42 * are met:
43 * 1. Redistributions of source code must retain the above copyright
44 * notice, this list of conditions and the following disclaimer.
45 * 2. Redistributions in binary form must reproduce the above copyright
46 * notice, this list of conditions and the following disclaimer in the
47 * documentation and/or other materials provided with the distribution.
48 * 3. Neither the name of the University nor the names of its contributors
49 * may be used to endorse or promote products derived from this software
50 * without specific prior written permission.
51 *
52 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
53 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
54 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
55 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
56 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
57 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
58 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
59 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
60 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
61 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
62 * SUCH DAMAGE.
63 *
64 * @(#)diff3.c 8.1 (Berkeley) 6/6/93
65 */
66
67 #include <ctype.h>
68 #include <err.h>
69 #include <stdio.h>
70 #include <stdlib.h>
71 #include <string.h>
72 #include <unistd.h>
73
74 /* diff3 - 3-way differential file comparison */
75
76 /* diff3 [-ex3EX] d13 d23 f1 f2 f3 [m1 m3]
77 *
78 * d13 = diff report on f1 vs f3
79 * d23 = diff report on f2 vs f3
80 * f1, f2, f3 the 3 files
81 * if changes in f1 overlap with changes in f3, m1 and m3 are used
82 * to mark the overlaps; otherwise, the file names f1 and f3 are used
83 * (only for options E and X).
84 */
85
86 /*
87 * "from" is first in range of changed lines; "to" is last+1
88 * from=to=line after point of insertion for added lines.
89 */
90 struct range {
91 int from;
92 int to;
93 };
94 struct diff {
95 struct range old;
96 struct range new;
97 };
98
99 size_t szchanges;
100
101 struct diff *d13;
102 struct diff *d23;
103 /*
104 * "de" is used to gather editing scripts. These are later spewed out in
105 * reverse order. Its first element must be all zero, the "new" component
106 * of "de" contains line positions or byte positions depending on when you
107 * look (!?). Array overlap indicates which sections in "de" correspond to
108 * lines that are different in all three files.
109 */
110 struct diff *de;
111 char *overlap;
112 int overlapcnt;
113 FILE *fp[3];
114 int cline[3]; /* # of the last-read line in each file (0-2) */
115 /*
116 * the latest known correspondence between line numbers of the 3 files
117 * is stored in last[1-3];
118 */
119 int last[4];
120 int eflag;
121 int oflag; /* indicates whether to mark overlaps (-E or -X)*/
122 int debug = 0;
123 char f1mark[40], f3mark[40]; /* markers for -E and -X */
124
125 int duplicate(struct range *, struct range *);
126 int edit(struct diff *, int, int);
127 char *getchange(FILE *);
128 char *get_line(FILE *, size_t *);
129 int number(char **);
130 int readin(char *, struct diff **);
131 int skip(int, int, const char *);
132 void change(int, struct range *, int);
133 void keep(int, struct range *);
134 void merge(int, int);
135 void prange(struct range *);
136 void repos(int);
137 void separate(const char *);
138 void edscript(int);
139 void trouble(void);
140 void increase(void);
141 void usage(void);
142
143 int
main(int argc,char ** argv)144 main(int argc, char **argv)
145 {
146 int ch, i, m, n;
147
148 eflag = 0;
149 oflag = 0;
150 while ((ch = getopt(argc, argv, "EeXx3")) != -1) {
151 switch (ch) {
152 case 'E':
153 eflag = 3;
154 oflag = 1;
155 break;
156 case 'e':
157 eflag = 3;
158 break;
159 case 'X':
160 oflag = eflag = 1;
161 break;
162 case 'x':
163 eflag = 1;
164 break;
165 case '3':
166 eflag = 2;
167 break;
168 }
169 }
170 argc -= optind;
171 argv += optind;
172 /* XXX - argc usage seems wrong here */
173 if (argc < 5)
174 usage();
175
176 if (oflag) {
177 (void)snprintf(f1mark, sizeof(f1mark), "<<<<<<< %s",
178 argc >= 6 ? argv[5] : argv[2]);
179 (void)snprintf(f3mark, sizeof(f3mark), ">>>>>>> %s",
180 argc >= 7 ? argv[6] : argv[4]);
181 }
182
183 increase();
184 m = readin(argv[0], &d13);
185 n = readin(argv[1], &d23);
186 for (i = 0; i <= 2; i++) {
187 if ((fp[i] = fopen(argv[i + 2], "r")) == NULL)
188 err(EXIT_FAILURE, "can't open %s", argv[i + 2]);
189 }
190 merge(m, n);
191 exit(EXIT_SUCCESS);
192 }
193
194 /*
195 * Pick up the line numbers of all changes from one change file.
196 * (This puts the numbers in a vector, which is not strictly necessary,
197 * since the vector is processed in one sequential pass.
198 * The vector could be optimized out of existence)
199 */
200 int
readin(char * name,struct diff ** dd)201 readin(char *name, struct diff **dd)
202 {
203 int a, b, c, d;
204 size_t i;
205 char kind, *p;
206
207 fp[0] = fopen(name, "r");
208 if (fp[0] == NULL)
209 err(EXIT_FAILURE, "can't open %s", name);
210 for (i=0; (p = getchange(fp[0])); i++) {
211 if (i >= szchanges - 1)
212 increase();
213 a = b = number(&p);
214 if (*p == ',') {
215 p++;
216 b = number(&p);
217 }
218 kind = *p++;
219 c = d = number(&p);
220 if (*p==',') {
221 p++;
222 d = number(&p);
223 }
224 if (kind == 'a')
225 a++;
226 if (kind == 'd')
227 c++;
228 b++;
229 d++;
230 (*dd)[i].old.from = a;
231 (*dd)[i].old.to = b;
232 (*dd)[i].new.from = c;
233 (*dd)[i].new.to = d;
234 }
235 if (i) {
236 (*dd)[i].old.from = (*dd)[i-1].old.to;
237 (*dd)[i].new.from = (*dd)[i-1].new.to;
238 }
239 (void)fclose(fp[0]);
240 return (i);
241 }
242
243 int
number(char ** lc)244 number(char **lc)
245 {
246 int nn;
247 nn = 0;
248 while (isdigit((unsigned char)(**lc)))
249 nn = nn*10 + *(*lc)++ - '0';
250 return (nn);
251 }
252
253 char *
getchange(FILE * b)254 getchange(FILE *b)
255 {
256 char *line;
257
258 while ((line = get_line(b, NULL))) {
259 if (isdigit((unsigned char)line[0]))
260 return (line);
261 }
262 return (NULL);
263 }
264
265 char *
get_line(FILE * b,size_t * n)266 get_line(FILE *b, size_t *n)
267 {
268 char *cp;
269 size_t len;
270 static char *buf;
271 static size_t bufsize;
272
273 if ((cp = fgetln(b, &len)) == NULL)
274 return (NULL);
275
276 if (cp[len - 1] != '\n')
277 len++;
278 if (len + 1 > bufsize) {
279 do {
280 bufsize += 1024;
281 } while (len + 1 > bufsize);
282 if ((buf = realloc(buf, bufsize)) == NULL)
283 err(EXIT_FAILURE, NULL);
284 }
285 memcpy(buf, cp, len - 1);
286 buf[len - 1] = '\n';
287 buf[len] = '\0';
288 if (n != NULL)
289 *n = len;
290 return (buf);
291 }
292
293 void
merge(int m1,int m2)294 merge(int m1, int m2)
295 {
296 struct diff *d1, *d2, *d3;
297 int dup, j, t1, t2;
298
299 d1 = d13;
300 d2 = d23;
301 j = 0;
302 for (;;) {
303 t1 = (d1 < d13 + m1);
304 t2 = (d2 < d23 + m2);
305 if (!t1 && !t2)
306 break;
307
308 if (debug) {
309 printf("%d,%d=%d,%d %d,%d=%d,%d\n",
310 d1->old.from,d1->old.to,
311 d1->new.from,d1->new.to,
312 d2->old.from,d2->old.to,
313 d2->new.from,d2->new.to);
314 }
315 /* first file is different from others */
316 if (!t2 || (t1 && d1->new.to < d2->new.from)) {
317 /* stuff peculiar to 1st file */
318 if (eflag==0) {
319 separate("1");
320 change(1, &d1->old, 0);
321 keep(2, &d1->new);
322 change(3, &d1->new, 0);
323 }
324 d1++;
325 continue;
326 }
327 /* second file is different from others */
328 if (!t1 || (t2 && d2->new.to < d1->new.from)) {
329 if (eflag==0) {
330 separate("2");
331 keep(1, &d2->new);
332 change(2, &d2->old, 0);
333 change(3, &d2->new, 0);
334 }
335 d2++;
336 continue;
337 }
338 /*
339 * Merge overlapping changes in first file
340 * this happens after extension (see below).
341 */
342 if (d1 + 1 < d13 + m1 && d1->new.to >= d1[1].new.from) {
343 d1[1].old.from = d1->old.from;
344 d1[1].new.from = d1->new.from;
345 d1++;
346 continue;
347 }
348
349 /* merge overlapping changes in second */
350 if (d2 + 1 < d23 + m2 && d2->new.to >= d2[1].new.from) {
351 d2[1].old.from = d2->old.from;
352 d2[1].new.from = d2->new.from;
353 d2++;
354 continue;
355 }
356 /* stuff peculiar to third file or different in all */
357 if (d1->new.from == d2->new.from && d1->new.to == d2->new.to) {
358 dup = duplicate(&d1->old,&d2->old);
359 /*
360 * dup = 0 means all files differ
361 * dup = 1 means files 1 and 2 identical
362 */
363 if (eflag==0) {
364 separate(dup ? "3" : "");
365 change(1, &d1->old, dup);
366 change(2, &d2->old, 0);
367 d3 = d1->old.to > d1->old.from ? d1 : d2;
368 change(3, &d3->new, 0);
369 } else
370 j = edit(d1, dup, j);
371 d1++;
372 d2++;
373 continue;
374 }
375 /*
376 * Overlapping changes from file 1 and 2; extend changes
377 * appropriately to make them coincide.
378 */
379 if (d1->new.from < d2->new.from) {
380 d2->old.from -= d2->new.from-d1->new.from;
381 d2->new.from = d1->new.from;
382 } else if (d2->new.from < d1->new.from) {
383 d1->old.from -= d1->new.from-d2->new.from;
384 d1->new.from = d2->new.from;
385 }
386 if (d1->new.to > d2->new.to) {
387 d2->old.to += d1->new.to - d2->new.to;
388 d2->new.to = d1->new.to;
389 } else if (d2->new.to > d1->new.to) {
390 d1->old.to += d2->new.to - d1->new.to;
391 d1->new.to = d2->new.to;
392 }
393 }
394 if (eflag)
395 edscript(j);
396 }
397
398 void
separate(const char * s)399 separate(const char *s)
400 {
401 printf("====%s\n", s);
402 }
403
404 /*
405 * The range of lines rold.from thru rold.to in file i is to be changed.
406 * It is to be printed only if it does not duplicate something to be
407 * printed later.
408 */
409 void
change(int i,struct range * rold,int dup)410 change(int i, struct range *rold, int dup)
411 {
412 printf("%d:", i);
413 last[i] = rold->to;
414 prange(rold);
415 if (dup || debug)
416 return;
417 i--;
418 (void)skip(i, rold->from, NULL);
419 (void)skip(i, rold->to, " ");
420 }
421
422 /*
423 * print the range of line numbers, rold.from thru rold.to, as n1,n2 or n1
424 */
425 void
prange(struct range * rold)426 prange(struct range *rold)
427 {
428 if (rold->to <= rold->from)
429 printf("%da\n", rold->from - 1);
430 else {
431 printf("%d", rold->from);
432 if (rold->to > rold->from+1)
433 printf(",%d", rold->to - 1);
434 printf("c\n");
435 }
436 }
437
438 /*
439 * No difference was reported by diff between file 1 (or 2) and file 3,
440 * and an artificial dummy difference (trange) must be ginned up to
441 * correspond to the change reported in the other file.
442 */
443 void
keep(int i,struct range * rnew)444 keep(int i, struct range *rnew)
445 {
446 int delta;
447 struct range trange;
448
449 delta = last[3] - last[i];
450 trange.from = rnew->from - delta;
451 trange.to = rnew->to - delta;
452 change(i, &trange, 1);
453 }
454
455 /*
456 * skip to just before line number from in file "i". If "pr" is non-NULL,
457 * print all skipped stuff with string pr as a prefix.
458 */
459 int
skip(int i,int from,const char * pr)460 skip(int i, int from, const char *pr)
461 {
462 size_t j, n;
463 char *line;
464
465 for (n = 0; cline[i] < from - 1; n += j) {
466 if ((line = get_line(fp[i], &j)) == NULL)
467 trouble();
468 if (pr != NULL)
469 printf("%s%s", pr, line);
470 cline[i]++;
471 }
472 return ((int) n);
473 }
474
475 /*
476 * Return 1 or 0 according as the old range (in file 1) contains exactly
477 * the same data as the new range (in file 2).
478 */
479 int
duplicate(struct range * r1,struct range * r2)480 duplicate(struct range *r1, struct range *r2)
481 {
482 int c,d;
483 int nchar;
484 int nline;
485
486 if (r1->to-r1->from != r2->to-r2->from)
487 return (0);
488 (void)skip(0, r1->from, NULL);
489 (void)skip(1, r2->from, NULL);
490 nchar = 0;
491 for (nline=0; nline < r1->to - r1->from; nline++) {
492 do {
493 c = getc(fp[0]);
494 d = getc(fp[1]);
495 if (c == -1 && d == -1)
496 break;
497 if (c == -1 || d== -1)
498 trouble();
499 nchar++;
500 if (c != d) {
501 repos(nchar);
502 return (0);
503 }
504 } while (c != '\n');
505 }
506 repos(nchar);
507 return (1);
508 }
509
510 void
repos(int nchar)511 repos(int nchar)
512 {
513 int i;
514
515 for (i = 0; i < 2; i++)
516 (void)fseek(fp[i], (long)-nchar, SEEK_CUR);
517 }
518
519 void
trouble(void)520 trouble(void)
521 {
522 errx(EXIT_FAILURE, "logic error");
523 }
524
525 /*
526 * collect an editing script for later regurgitation
527 */
528 int
edit(struct diff * diff,int dup,int j)529 edit(struct diff *diff, int dup, int j)
530 {
531 if (((dup + 1) & eflag) == 0)
532 return (j);
533 j++;
534 overlap[j] = !dup;
535 if (!dup)
536 overlapcnt++;
537 de[j].old.from = diff->old.from;
538 de[j].old.to = diff->old.to;
539 de[j].new.from = de[j-1].new.to + skip(2, diff->new.from, NULL);
540 de[j].new.to = de[j].new.from + skip(2, diff->new.to, NULL);
541 return (j);
542 }
543
544 /* regurgitate */
545 void
edscript(int n)546 edscript(int n)
547 {
548 int k;
549 size_t j;
550 char block[BUFSIZ];
551
552 for (; n > 0; n--) {
553 if (!oflag || !overlap[n])
554 prange(&de[n].old);
555 else
556 printf("%da\n=======\n", de[n].old.to -1);
557 (void)fseek(fp[2], (long)de[n].new.from, SEEK_SET);
558 for (k = de[n].new.to-de[n].new.from; k > 0; k-= j) {
559 size_t r;
560 j = k > BUFSIZ ? BUFSIZ : k;
561 r = fread(block, 1, j, fp[2]);
562 if (r == 0) {
563 if (feof(fp[2]))
564 break;
565 trouble();
566 }
567 if (r != j)
568 j = r;
569 (void)fwrite(block, 1, j, stdout);
570 }
571 if (!oflag || !overlap[n])
572 printf(".\n");
573 else {
574 printf("%s\n.\n", f3mark);
575 printf("%da\n%s\n.\n", de[n].old.from - 1, f1mark);
576 }
577 }
578 exit(overlapcnt);
579 }
580
581 void
increase(void)582 increase(void)
583 {
584 struct diff *p;
585 char *q;
586 size_t newsz, incr;
587
588 /* are the memset(3) calls needed? */
589 newsz = szchanges == 0 ? 64 : 2 * szchanges;
590 incr = newsz - szchanges;
591
592 p = reallocarray(d13, newsz, sizeof(struct diff));
593 if (p == NULL)
594 err(1, NULL);
595 memset(p + szchanges, 0, incr * sizeof(struct diff));
596 d13 = p;
597 p = reallocarray(d23, newsz, sizeof(struct diff));
598 if (p == NULL)
599 err(1, NULL);
600 memset(p + szchanges, 0, incr * sizeof(struct diff));
601 d23 = p;
602 p = reallocarray(de, newsz, sizeof(struct diff));
603 if (p == NULL)
604 err(1, NULL);
605 memset(p + szchanges, 0, incr * sizeof(struct diff));
606 de = p;
607 q = reallocarray(overlap, newsz, sizeof(char));
608 if (q == NULL)
609 err(1, NULL);
610 memset(q + szchanges, 0, incr * sizeof(char));
611 overlap = q;
612 szchanges = newsz;
613 }
614
615
616 void
usage(void)617 usage(void)
618 {
619 //extern char *__progname;
620
621 fprintf(stderr, "usage: %s [-exEX3] /tmp/d3a.?????????? "
622 "/tmp/d3b.?????????? file1 file2 file3\n", "diff3");
623 exit(EXIT_FAILURE);
624 }
625