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