1 /*- 2 * Copyright (c) 1991, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * %sccs.include.proprietary.c% 6 */ 7 8 #ifndef lint 9 static char copyright[] = 10 "@(#) Copyright (c) 1991, 1993\n\ 11 The Regents of the University of California. All rights reserved.\n"; 12 #endif /* not lint */ 13 14 #ifndef lint 15 static char sccsid[] = "@(#)diff3.c 8.1 (Berkeley) 06/06/93"; 16 #endif /* not lint */ 17 18 #include <stdio.h> 19 20 /* diff3 - 3-way differential file comparison*/ 21 22 /* diff3 [-ex3EX] d13 d23 f1 f2 f3 [m1 m3] 23 * 24 * d13 = diff report on f1 vs f3 25 * d23 = diff report on f2 vs f3 26 * f1, f2, f3 the 3 files 27 * if changes in f1 overlap with changes in f3, m1 and m3 are used 28 * to mark the overlaps; otherwise, the file names f1 and f3 are used 29 * (only for options E and X). 30 */ 31 32 struct range {int from,to; }; 33 /* from is first in range of changed lines 34 * to is last+1 35 * from=to=line after point of insertion 36 * for added lines 37 */ 38 struct diff {struct range old, new;}; 39 40 #define NC 200 41 struct diff d13[NC]; 42 struct diff d23[NC]; 43 /* de is used to gather editing scripts, 44 * that are later spewed out in reverse order. 45 * its first element must be all zero 46 * the "new" component of de contains line positions 47 * or byte positions depending on when you look(!?) 48 * array overlap indicates which sections in de correspond to 49 * lines that are different in all three files. 50 */ 51 struct diff de[NC]; 52 char overlap[NC]; 53 int overlapcnt =0; 54 55 char line[256]; 56 FILE *fp[3]; 57 /* the number of the last-read line in each file 58 * is kept in cline[0-2] 59 */ 60 int cline[3]; 61 /* the latest known correspondence between line 62 * numbers of the 3 files is stored in last[1-3] 63 */ 64 int last[4]; 65 int eflag; 66 int oflag; /* indicates whether to mark overlaps (-E or -X)*/ 67 int debug = 0; 68 char f1mark[40], f3mark[40]; /*markers for -E and -X*/ 69 70 71 main(argc,argv) 72 char **argv; 73 { 74 register i,m,n; 75 eflag=0; oflag=0; 76 if(*argv[1]=='-') { 77 switch(argv[1][1]) { 78 default: 79 eflag = 3; 80 break; 81 case '3': 82 eflag = 2; 83 break; 84 case 'x': 85 eflag = 1; 86 break; 87 case 'E': 88 eflag = 3; 89 oflag = 1; 90 break; 91 case 'X': 92 oflag = eflag = 1; 93 break; 94 } 95 argv++; 96 argc--; 97 } 98 if(argc<6) { 99 fprintf(stderr,"diff3: arg count\n"); 100 exit(1); 101 } 102 if (oflag) { 103 (void)sprintf(f1mark,"<<<<<<< %s",argc>=7?argv[6]:argv[3]); 104 (void)sprintf(f3mark,">>>>>>> %s",argc>=8?argv[7]:argv[5]); 105 } 106 107 m = readin(argv[1],d13); 108 n = readin(argv[2],d23); 109 for(i=0;i<=2;i++) 110 if((fp[i] = fopen(argv[i+3],"r")) == NULL) { 111 printf("diff3: can't open %s\n",argv[i+3]); 112 exit(1); 113 } 114 merge(m,n); 115 } 116 117 /*pick up the line numbers of allcahnges from 118 * one change file 119 * (this puts the numbers in a vector, which is not 120 * strictly necessary, since the vector is processed 121 * in one sequential pass. The vector could be optimized 122 * out of existence) 123 */ 124 125 readin(name,dd) 126 char *name; 127 struct diff *dd; 128 { 129 register i; 130 int a,b,c,d; 131 char kind; 132 char *p; 133 fp[0] = fopen(name,"r"); 134 for(i=0;getchange(fp[0]);i++) { 135 if(i>=NC) { 136 fprintf(stderr,"diff3: too many changes\n"); 137 exit(0); 138 } 139 p = line; 140 a = b = number(&p); 141 if(*p==',') { 142 p++; 143 b = number(&p); 144 } 145 kind = *p++; 146 c = d = number(&p); 147 if(*p==',') { 148 p++; 149 d = number(&p); 150 } 151 if(kind=='a') 152 a++; 153 if(kind=='d') 154 c++; 155 b++; 156 d++; 157 dd[i].old.from = a; 158 dd[i].old.to = b; 159 dd[i].new.from = c; 160 dd[i].new.to = d; 161 } 162 dd[i].old.from = dd[i-1].old.to; 163 dd[i].new.from = dd[i-1].new.to; 164 (void)fclose(fp[0]); 165 return(i); 166 } 167 168 number(lc) 169 char **lc; 170 { 171 register nn; 172 nn = 0; 173 while(digit(**lc)) 174 nn = nn*10 + *(*lc)++ - '0'; 175 return(nn); 176 } 177 178 digit(c) 179 { 180 return(c>='0'&&c<='9'); 181 } 182 183 getchange(b) 184 FILE *b; 185 { 186 while(getline(b)) 187 if(digit(line[0])) 188 return(1); 189 return(0); 190 } 191 192 getline(b) 193 FILE *b; 194 { 195 register i, c; 196 for(i=0;i<sizeof(line)-1;i++) { 197 c = getc(b); 198 if(c==EOF) 199 break; 200 line[i] = c; 201 if(c=='\n') { 202 line[++i] = 0; 203 return(i); 204 } 205 } 206 return(0); 207 } 208 209 merge(m1,m2) 210 { 211 register struct diff *d1, *d2, *d3; 212 int dup; 213 int j; 214 int t1,t2; 215 d1 = d13; 216 d2 = d23; 217 j = 0; 218 for(;(t1 = d1<d13+m1) | (t2 = d2<d23+m2);) { 219 if(debug) { 220 printf("%d,%d=%d,%d %d,%d=%d,%d\n", 221 d1->old.from,d1->old.to, 222 d1->new.from,d1->new.to, 223 d2->old.from,d2->old.to, 224 d2->new.from,d2->new.to); 225 } 226 /* first file is different from others*/ 227 if(!t2||t1&&d1->new.to < d2->new.from) { 228 /* stuff peculiar to 1st file */ 229 if(eflag==0) { 230 separate("1"); 231 change(1,&d1->old,0); 232 keep(2,&d1->new); 233 change(3,&d1->new,0); 234 } 235 d1++; 236 continue; 237 } 238 /* second file is different from others*/ 239 if(!t1||t2&&d2->new.to < d1->new.from) { 240 if(eflag==0) { 241 separate("2"); 242 keep(1,&d2->new); 243 change(2,&d2->old,0); 244 change(3,&d2->new,0); 245 } 246 d2++; 247 continue; 248 } 249 /* merge overlapping changes in first file 250 * this happens after extension see below*/ 251 if(d1+1<d13+m1 && 252 d1->new.to>=d1[1].new.from) { 253 d1[1].old.from = d1->old.from; 254 d1[1].new.from = d1->new.from; 255 d1++; 256 continue; 257 } 258 /* merge overlapping changes in second*/ 259 if(d2+1<d23+m2 && 260 d2->new.to>=d2[1].new.from) { 261 d2[1].old.from = d2->old.from; 262 d2[1].new.from = d2->new.from; 263 d2++; 264 continue; 265 } 266 /* stuff peculiar to third file or different in all*/ 267 if(d1->new.from==d2->new.from&& 268 d1->new.to==d2->new.to) { 269 dup = duplicate(&d1->old,&d2->old); 270 /* dup=0 means all files differ 271 * dup =1 meands files 1&2 identical*/ 272 if(eflag==0) { 273 separate(dup?"3":""); 274 change(1,&d1->old,dup); 275 change(2,&d2->old,0); 276 d3 = d1->old.to>d1->old.from?d1:d2; 277 change(3,&d3->new,0); 278 } else 279 j = edit(d1,dup,j); 280 d1++; 281 d2++; 282 continue; 283 } 284 /* overlapping changes from file1 & 2 285 * extend changes appropriately to 286 * make them coincide*/ 287 if(d1->new.from<d2->new.from) { 288 d2->old.from -= d2->new.from-d1->new.from; 289 d2->new.from = d1->new.from; 290 } 291 else if(d2->new.from<d1->new.from) { 292 d1->old.from -= d1->new.from-d2->new.from; 293 d1->new.from = d2->new.from; 294 } 295 if(d1->new.to >d2->new.to) { 296 d2->old.to += d1->new.to - d2->new.to; 297 d2->new.to = d1->new.to; 298 } 299 else if(d2->new.to >d1->new.to) { 300 d1->old.to += d2->new.to - d1->new.to; 301 d1->new.to = d2->new.to; 302 } 303 } 304 if(eflag) 305 edscript(j); 306 } 307 308 separate(s) 309 char *s; 310 { 311 printf("====%s\n",s); 312 } 313 314 /* the range of ines rold.from thru rold.to in file i 315 * is to be changed. it is to be printed only if 316 * it does not duplicate something to be printed later 317 */ 318 change(i,rold,dup) 319 struct range *rold; 320 { 321 printf("%d:",i); 322 last[i] = rold->to; 323 prange(rold); 324 if(dup) 325 return; 326 if(debug) 327 return; 328 i--; 329 (void)skip(i,rold->from,(char *)0); 330 (void)skip(i,rold->to," "); 331 } 332 333 /* print the range of line numbers, rold.from thru rold.to 334 * as n1,n2 or n1 335 */ 336 prange(rold) 337 struct range *rold; 338 { 339 if(rold->to<=rold->from) 340 printf("%da\n",rold->from-1); 341 else { 342 printf("%d",rold->from); 343 if(rold->to > rold->from+1) 344 printf(",%d",rold->to-1); 345 printf("c\n"); 346 } 347 } 348 349 /* no difference was reported by diff between file 1(or 2) 350 * and file 3, and an artificial dummy difference (trange) 351 * must be ginned up to correspond to the change reported 352 * in the other file 353 */ 354 keep(i,rnew) 355 struct range *rnew; 356 { 357 register delta; 358 struct range trange; 359 delta = last[3] - last[i]; 360 trange.from = rnew->from - delta; 361 trange.to = rnew->to - delta; 362 change(i,&trange,1); 363 } 364 365 /* skip to just befor line number from in file i 366 * if "pr" is nonzero, print all skipped stuff 367 * w with string pr as a prefix 368 */ 369 skip(i,from,pr) 370 char *pr; 371 { 372 register j,n; 373 for(n=0;cline[i]<from-1;n+=j) { 374 if((j=getline(fp[i]))==0) 375 trouble(); 376 if(pr) 377 printf("%s%s",pr,line); 378 cline[i]++; 379 } 380 return(n); 381 } 382 383 /* return 1 or 0 according as the old range 384 * (in file 1) contains exactly the same data 385 * as the new range (in file 2) 386 */ 387 duplicate(r1,r2) 388 struct range *r1, *r2; 389 { 390 register c,d; 391 register nchar; 392 int nline; 393 if(r1->to-r1->from != r2->to-r2->from) 394 return(0); 395 (void)skip(0,r1->from,(char *)0); 396 (void)skip(1,r2->from,(char *)0); 397 nchar = 0; 398 for(nline=0;nline<r1->to-r1->from;nline++) { 399 do { 400 c = getc(fp[0]); 401 d = getc(fp[1]); 402 if(c== -1||d== -1) 403 trouble(); 404 nchar++; 405 if(c!=d) { 406 repos(nchar); 407 return(0); 408 } 409 } while(c!= '\n'); 410 } 411 repos(nchar); 412 return(1); 413 } 414 415 repos(nchar) 416 { 417 register i; 418 for(i=0;i<2;i++) 419 (void)fseek(fp[i], (long)-nchar, 1); 420 } 421 422 trouble() 423 { 424 fprintf(stderr,"diff3: logic error\n"); 425 abort(); 426 } 427 428 /* collect an editing script for later regurgitation 429 */ 430 edit(diff,dup,j) 431 struct diff *diff; 432 { 433 if(((dup+1)&eflag)==0) 434 return(j); 435 j++; 436 overlap[j] = !dup; 437 if (!dup) overlapcnt++; 438 de[j].old.from = diff->old.from; 439 de[j].old.to = diff->old.to; 440 de[j].new.from = de[j-1].new.to 441 +skip(2,diff->new.from,(char *)0); 442 de[j].new.to = de[j].new.from 443 +skip(2,diff->new.to,(char *)0); 444 return(j); 445 } 446 447 /* regurgitate */ 448 edscript(n) 449 { 450 register j,k; 451 char block[BUFSIZ]; 452 for(n=n;n>0;n--) { 453 if (!oflag || !overlap[n]) 454 prange(&de[n].old); 455 else 456 printf("%da\n=======\n", de[n].old.to -1); 457 (void)fseek(fp[2], (long)de[n].new.from, 0); 458 for(k=de[n].new.to-de[n].new.from;k>0;k-= j) { 459 j = k>BUFSIZ?BUFSIZ:k; 460 if(fread(block,1,j,fp[2])!=j) 461 trouble(); 462 (void)fwrite(block, 1, j, stdout); 463 } 464 if (!oflag || !overlap[n]) 465 printf(".\n"); 466 else { 467 printf("%s\n.\n",f3mark); 468 printf("%da\n%s\n.\n",de[n].old.from-1,f1mark); 469 } 470 } 471 exit(overlapcnt); 472 } 473