1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License (the "License"). 6 * You may not use this file except in compliance with the License. 7 * 8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9 * or http://www.opensolaris.org/os/licensing. 10 * See the License for the specific language governing permissions 11 * and limitations under the License. 12 * 13 * When distributing Covered Code, include this CDDL HEADER in each 14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15 * If applicable, add the following below this CDDL HEADER, with the 16 * fields enclosed by brackets "[]" replaced with your own identifying 17 * information: Portions Copyright [yyyy] [name of copyright owner] 18 * 19 * CDDL HEADER END 20 */ 21 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */ 22 /* All Rights Reserved */ 23 24 25 /* 26 * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 27 * Use is subject to license terms. 28 */ 29 30 #pragma ident "%Z%%M% %I% %E% SMI" 31 32 #include <stdio.h> 33 #include <stdlib.h> 34 #include <unistd.h> 35 #include <limits.h> 36 #include <sys/param.h> 37 #include <errno.h> 38 # 39 40 /* 41 * diff3 - 3-way differential file comparison 42 */ 43 44 /* 45 * diff3 [-ex3EX] d13 d23 f1 f2 f3 [m1 m3] 46 * 47 * d13 = diff report on f1 vs f3 48 * d23 = diff report on f2 vs f3 49 * f1, f2, f3 the 3 files 50 * if changes in f1 overlap with changes in f3, m1 and m3 are used 51 * to mark the overlaps; otherwise, the file names f1 and f3 are used 52 * (only for options E and X). 53 */ 54 55 struct range {int from, to; }; 56 /* 57 * from is first in range of changed lines 58 * to is last+1 59 * from = to = line after point of insertion 60 * for added lines 61 */ 62 struct diff {struct range old, new; }; 63 64 #define NC 4096 65 /* 66 * de is used to gather editing scripts, 67 * that are later spewed out in reverse order. 68 * its first element must be all zero 69 * the "new" component of de contains line positions 70 * or byte positions depending on when you look(!?) 71 */ 72 static struct diff d13[NC]; 73 static struct diff d23[NC]; 74 75 /* 76 * array overlap indicates which sections in de correspond to 77 * lines that are different in all three files. 78 */ 79 80 static struct diff de[NC]; 81 static char overlap[NC]; 82 static int overlapcnt = 0; 83 84 static char line[LINE_MAX+1]; 85 static FILE *fp[3]; 86 /* 87 * the number of the last-read line in each file 88 * is kept in cline[0-2] 89 */ 90 static int cline[3]; 91 /* 92 * the latest known correspondence between line 93 * numbers of the 3 files is stored in last[1-3] 94 */ 95 static int last[4]; 96 static int eflag; 97 static int oflag; /* indicates whether to mark overlaps (-E or -X) */ 98 static int debug = 0; 99 /* markers for -E and -X: */ 100 static char f1mark[8+MAXPATHLEN], f3mark[8+MAXPATHLEN]; 101 /* Need space for "<<<<<<< " or ">>>>>>> " plus filename */ 102 static int save_err; /* saves errno */ 103 104 static int readin(char *name, struct diff *dd); 105 static int number(char **lc); 106 static int digit(int c); 107 static int getchange(FILE *b); 108 static int getline(FILE *b); 109 static void merge(int m1, int m2); 110 static void separate(char *s); 111 static void change(int i, struct range *rold, int dup); 112 static void prange(struct range *rold); 113 static void keep(int i, struct range *rnew); 114 static int skip(int i, int from, char *pr); 115 static int duplicate(struct range *r1, struct range *r2); 116 static void repos(int nchar); 117 static void trouble(); 118 static int edit(struct diff *diff, int dup, int j); 119 static void edscript(int n); 120 static void usage(); 121 122 int 123 main(int argc, char **argv) 124 { 125 int i, m, n; 126 eflag = 0; 127 oflag = 0; 128 if ((argc > 1) && (*argv[1] == '-')) { 129 switch (argv[1][1]) { 130 case 'e': 131 eflag = 3; 132 break; 133 case '3': 134 eflag = 2; 135 break; 136 case 'x': 137 eflag = 1; 138 break; 139 case 'E': 140 eflag = 3; 141 oflag = 1; 142 break; 143 case 'X': 144 oflag = eflag = 1; 145 break; 146 default: 147 usage(); 148 break; 149 } 150 argv++; 151 argc--; 152 } 153 if (argc < 6) 154 usage(); 155 if (oflag) { 156 (void) snprintf(f1mark, sizeof (f1mark), "<<<<<<< %s", 157 argc >= 7 ? argv[6] : argv[3]); 158 (void) snprintf(f3mark, sizeof (f3mark), ">>>>>>> %s", 159 argc >= 8 ? argv[7] : argv[5]); 160 } 161 162 m = readin(argv[1], d13); 163 n = readin(argv[2], d23); 164 for (i = 0; i <= 2; i++) 165 if ((fp[i] = fopen(argv[i+3], "r")) == NULL) { 166 save_err = errno; 167 (void) fprintf(stderr, "diff3: can't open %s: ", 168 argv[i+3]); 169 errno = save_err; 170 perror(""); 171 exit(1); 172 } 173 merge(m, n); 174 return (0); 175 } 176 177 /* 178 * pick up the line numbers of all changes from 179 * one change file 180 * (this puts the numbers in a vector, which is not 181 * strictly necessary, since the vector is processed 182 * in one sequential pass. The vector could be optimized 183 * out of existence) 184 */ 185 186 static int 187 readin(char *name, struct diff *dd) 188 { 189 int i; 190 int a, b, c, d; 191 char kind; 192 char *p; 193 if ((fp[0] = fopen(name, "r")) == NULL) { 194 save_err = errno; 195 (void) fprintf(stderr, "diff3: can't open %s: ", name); 196 errno = save_err; 197 perror(""); 198 exit(1); 199 } 200 for (i = 0; getchange(fp[0]); i++) { 201 if (i >= NC) { 202 (void) fprintf(stderr, "diff3: too many changes\n"); 203 exit(0); 204 } 205 p = line; 206 a = b = number(&p); 207 if (*p == ',') { 208 p++; 209 b = number(&p); 210 } 211 kind = *p++; 212 c = d = number(&p); 213 if (*p == ',') { 214 p++; 215 d = number(&p); 216 } 217 if (kind == 'a') 218 a++; 219 if (kind == 'd') 220 c++; 221 b++; 222 d++; 223 dd[i].old.from = a; 224 dd[i].old.to = b; 225 dd[i].new.from = c; 226 dd[i].new.to = d; 227 } 228 dd[i].old.from = dd[i-1].old.to; 229 dd[i].new.from = dd[i-1].new.to; 230 (void) fclose(fp[0]); 231 return (i); 232 } 233 234 static int 235 number(char **lc) 236 { 237 int nn; 238 nn = 0; 239 while (digit(**lc)) 240 nn = nn*10 + *(*lc)++ - '0'; 241 return (nn); 242 } 243 244 static int 245 digit(int c) 246 { 247 return (c >= '0' && c <= '9'); 248 } 249 250 static int 251 getchange(FILE *b) 252 { 253 while (getline(b)) 254 if (digit(line[0])) 255 return (1); 256 return (0); 257 } 258 259 static int 260 getline(FILE *b) 261 { 262 int i, c; 263 for (i = 0; i < sizeof (line)-1; i++) { 264 c = getc(b); 265 if (c == EOF) { 266 line[i] = 0; 267 return (i); 268 } 269 line[i] = c; 270 if (c == '\n') { 271 line[++i] = 0; 272 return (i); 273 } 274 } 275 return (0); 276 } 277 278 static void 279 merge(int m1, int m2) 280 { 281 struct diff *d1, *d2, *d3; 282 int dup; 283 int j; 284 int t1, t2; 285 d1 = d13; 286 d2 = d23; 287 j = 0; 288 for (; (t1 = d1 < d13+m1) | (t2 = d2 < d23+m2); ) { 289 if (debug) { 290 (void) printf("%d,%d=%d,%d %d,%d=%d,%d\n", 291 d1->old.from, d1->old.to, 292 d1->new.from, d1->new.to, 293 d2->old.from, d2->old.to, 294 d2->new.from, d2->new.to); 295 } 296 297 /* first file is different from others */ 298 if (!t2 || t1 && d1->new.to < d2->new.from) { 299 /* stuff peculiar to 1st file */ 300 if (eflag == 0) { 301 separate("1"); 302 change(1, &d1->old, 0); 303 keep(2, &d1->new); 304 change(3, &d1->new, 0); 305 } 306 d1++; 307 continue; 308 } 309 310 /* second file is different from others */ 311 if (!t1 || t2 && d2->new.to < d1->new.from) { 312 if (eflag == 0) { 313 separate("2"); 314 keep(1, &d2->new); 315 change(2, &d2->old, 0); 316 change(3, &d2->new, 0); 317 } 318 d2++; 319 continue; 320 } 321 /* 322 * merge overlapping changes in first file 323 * this happens after extension see below 324 */ 325 if (d1+1 < d13+m1 && d1->new.to >= d1[1].new.from) { 326 d1[1].old.from = d1->old.from; 327 d1[1].new.from = d1->new.from; 328 d1++; 329 continue; 330 } 331 332 /* merge overlapping changes in second */ 333 if (d2+1 < d23+m2 && d2->new.to >= d2[1].new.from) { 334 d2[1].old.from = d2->old.from; 335 d2[1].new.from = d2->new.from; 336 d2++; 337 continue; 338 } 339 340 /* stuff peculiar to third file or different in all */ 341 if (d1->new.from == d2->new.from && d1->new.to == d2->new.to) { 342 dup = duplicate(&d1->old, &d2->old); 343 /* 344 * dup = 0 means all files differ 345 * dup = 1 meands files 1&2 identical 346 */ 347 if (eflag == 0) { 348 separate(dup?"3":""); 349 change(1, &d1->old, dup); 350 change(2, &d2->old, 0); 351 d3 = d1->old.to > d1->old.from ? d1 : d2; 352 change(3, &d3->new, 0); 353 } else 354 j = edit(d1, dup, j); 355 d1++; 356 d2++; 357 continue; 358 } 359 /* 360 * overlapping changes from file1 & 2 361 * extend changes appropriately to 362 * make them coincide 363 */ 364 if (d1->new.from < d2->new.from) { 365 d2->old.from -= d2->new.from-d1->new.from; 366 d2->new.from = d1->new.from; 367 } else if (d2->new.from < d1->new.from) { 368 d1->old.from -= d1->new.from-d2->new.from; 369 d1->new.from = d2->new.from; 370 } 371 372 if (d1->new.to > d2->new.to) { 373 d2->old.to += d1->new.to - d2->new.to; 374 d2->new.to = d1->new.to; 375 } else if (d2->new.to > d1->new.to) { 376 d1->old.to += d2->new.to - d1->new.to; 377 d1->new.to = d2->new.to; 378 } 379 } 380 if (eflag) { 381 edscript(j); 382 if (j) 383 (void) printf("w\nq\n"); 384 } 385 } 386 387 static void 388 separate(char *s) 389 { 390 (void) printf("====%s\n", s); 391 } 392 393 /* 394 * the range of ines rold.from thru rold.to in file i 395 * is to be changed. it is to be printed only if 396 * it does not duplicate something to be printed later 397 */ 398 static void 399 change(int i, struct range *rold, int dup) 400 { 401 (void) printf("%d:", i); 402 last[i] = rold->to; 403 prange(rold); 404 if (dup) 405 return; 406 if (debug) 407 return; 408 i--; 409 (void) skip(i, rold->from, (char *)0); 410 (void) skip(i, rold->to, " "); 411 } 412 413 /* 414 * print the range of line numbers, rold.from thru rold.to 415 * as n1, n2 or n1 416 */ 417 static void 418 prange(struct range *rold) 419 { 420 if (rold->to <= rold->from) 421 (void) printf("%da\n", rold->from-1); 422 else { 423 (void) printf("%d", rold->from); 424 if (rold->to > rold->from+1) 425 (void) printf(",%d", rold->to-1); 426 (void) printf("c\n"); 427 } 428 } 429 430 /* 431 * no difference was reported by diff between file 1(or 2) 432 * and file 3, and an artificial dummy difference (trange) 433 * must be ginned up to correspond to the change reported 434 * in the other file 435 */ 436 static void 437 keep(int i, struct range *rnew) 438 { 439 int delta; 440 struct range trange; 441 delta = last[3] - last[i]; 442 trange.from = rnew->from - delta; 443 trange.to = rnew->to - delta; 444 change(i, &trange, 1); 445 } 446 447 /* 448 * skip to just befor line number from in file i 449 * if "pr" is nonzero, print all skipped stuff 450 * with string pr as a prefix 451 */ 452 static int 453 skip(int i, int from, char *pr) 454 { 455 int j, n; 456 for (n = 0; cline[i] < from-1; n += j) { 457 if ((j = getline(fp[i])) == 0) 458 trouble(); 459 if (pr) 460 (void) printf("%s%s", pr, line); 461 cline[i]++; 462 } 463 return (n); 464 } 465 466 /* 467 * return 1 or 0 according as the old range 468 * (in file 1) contains exactly the same data 469 * as the new range (in file 2) 470 */ 471 static int 472 duplicate(struct range *r1, struct range *r2) 473 { 474 int c, d; 475 int nchar; 476 int nline; 477 if (r1->to-r1->from != r2->to-r2->from) 478 return (0); 479 (void) skip(0, r1->from, (char *)0); 480 (void) skip(1, r2->from, (char *)0); 481 nchar = 0; 482 for (nline = 0; nline < r1->to-r1->from; nline++) { 483 do { 484 c = getc(fp[0]); 485 d = getc(fp[1]); 486 if (c == -1 || d == -1) 487 trouble(); 488 nchar++; 489 if (c != d) { 490 repos(nchar); 491 return (0); 492 } 493 } while (c != '\n'); 494 } 495 repos(nchar); 496 return (1); 497 } 498 499 static void 500 repos(int nchar) 501 { 502 int i; 503 for (i = 0; i < 2; i++) 504 (void) fseek(fp[i], (long)-nchar, 1); 505 } 506 507 static void 508 trouble() 509 { 510 (void) fprintf(stderr, "diff3: logic error\n"); 511 abort(); 512 } 513 514 /* 515 * collect an editing script for later regurgitation 516 */ 517 static int 518 edit(struct diff *diff, int dup, int j) 519 { 520 if (((dup+1)&eflag) == 0) 521 return (j); 522 j++; 523 overlap[j] = !dup; 524 if (!dup) overlapcnt++; 525 de[j].old.from = diff->old.from; 526 de[j].old.to = diff->old.to; 527 de[j].new.from = de[j-1].new.to + skip(2, diff->new.from, (char *)0); 528 de[j].new.to = de[j].new.from + skip(2, diff->new.to, (char *)0); 529 return (j); 530 } 531 532 /* regurgitate */ 533 static void 534 edscript(int n) 535 { 536 int j, k; 537 char block[BUFSIZ]; 538 539 for (n = n; n > 0; n--) { 540 if (!oflag || !overlap[n]) 541 prange(&de[n].old); 542 else 543 (void) printf("%da\n=======\n", de[n].old.to -1); 544 (void) fseek(fp[2], (long)de[n].new.from, 0); 545 for (k = de[n].new.to-de[n].new.from; k > 0; k -= j) { 546 j = k > BUFSIZ?BUFSIZ:k; 547 if (fread(block, 1, j, fp[2]) != j) 548 trouble(); 549 (void) fwrite(block, 1, j, stdout); 550 } 551 if (!oflag || !overlap[n]) 552 (void) printf(".\n"); 553 else { 554 (void) printf("%s\n.\n", f3mark); 555 (void) printf("%da\n%s\n.\n", de[n].old.from-1, f1mark); 556 } 557 } 558 } 559 560 static void 561 usage() 562 { 563 (void) fprintf(stderr, 564 "\tusage: diff3prog [-ex3EX] d13 d23 f1 f2 f3 [m1 m2]\n"); 565 exit(1); 566 } 567