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
main(argc,argv)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
readin(name,dd)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
number(lc)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
digit(c)178 digit(c)
179 {
180 return(c>='0'&&c<='9');
181 }
182
getchange(b)183 getchange(b)
184 FILE *b;
185 {
186 while(getline(b))
187 if(digit(line[0]))
188 return(1);
189 return(0);
190 }
191
getline(b)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
merge(m1,m2)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
separate(s)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 */
skip(i,from,pr)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
repos(nchar)415 repos(nchar)
416 {
417 register i;
418 for(i=0;i<2;i++)
419 (void)fseek(fp[i], (long)-nchar, 1);
420 }
421
trouble()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 */
edscript(n)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