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