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