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