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