1 /* diff.c - compare files line by line
2 *
3 * Copyright 2014 Sandeep Sharma <sandeep.jack2756@gmail.com>
4 * Copyright 2014 Ashwini Kumar <ak.ashwini1981@gmail.com>
5 *
6 * See: http://cm.bell-labs.com/cm/cs/cstr/41.pdf
7
8 USE_DIFF(NEWTOY(diff, "<2>2B(ignore-blank-lines)d(minimal)b(ignore-space-change)ut(expand-tabs)w(ignore-all-space)i(ignore-case)T(initial-tab)s(report-identical-files)q(brief)a(text)L(label)*S(starting-file):N(new-file)r(recursive)U(unified)#<0=3", TOYFLAG_USR|TOYFLAG_BIN))
9
10 config DIFF
11 bool "diff"
12 default n
13 help
14 usage: diff [-abBdiNqrTstw] [-L LABEL] [-S FILE] [-U LINES] FILE1 FILE2
15
16 -a Treat all files as text
17 -b Ignore changes in the amount of whitespace
18 -B Ignore changes whose lines are all blank
19 -d Try hard to find a smaller set of changes
20 -i Ignore case differences
21 -L Use LABEL instead of the filename in the unified header
22 -N Treat absent files as empty
23 -q Output only whether files differ
24 -r Recurse
25 -S Start with FILE when comparing directories
26 -T Make tabs line up by prefixing a tab when necessary
27 -s Report when two files are the same
28 -t Expand tabs to spaces in output
29 -U Output LINES lines of context
30 -w Ignore all whitespace
31 */
32
33 #define FOR_diff
34 #include "toys.h"
35
36 GLOBALS(
37 long ct;
38 char *start;
39 struct arg_list *L_list;
40
41 int dir_num, size, is_binary, status, change, len[2];
42 int *offset[2];
43 )
44
45 #define MIN(x,y) ((x) < (y) ? (x) : (y))
46 #define MAX(x,y) ((x) > (y) ? (x) : (y))
47 #define IS_STDIN(s) ((s)[0] == '-' && !(s)[1])
48
49 struct v_vector {
50 unsigned serial:31;
51 unsigned last:1;
52 union {
53 unsigned hash;
54 unsigned p;
55 };
56 };
57
58 struct diff {
59 long a, b, c, d, prev, suff;
60 };
61
62 static struct dir {
63 char **list;
64 int nr_elm;
65 } dir[2];
66
67 struct candidate {
68 int a, b;
69 struct candidate *prev, *next;
70 };
71
72 static struct file {
73 FILE *fp;
74 int len;
75 } file[2];
76
77 enum {
78 SAME,
79 DIFFER,
80 };
81
82 enum {
83 empty = 1 << 9,
84 eol = 1 << 10,
85 eof = 1 << 11,
86 space = 1 << 12
87 };
88
comp(const void * a,const void * b)89 static int comp(const void *a, const void* b)
90 {
91 int i = ((struct v_vector *)a)->hash -
92 ((struct v_vector *)b)->hash;
93
94 if (!i) i = ((struct v_vector *)a)->serial -
95 ((struct v_vector *)b)->serial;
96 return i;
97 }
98
search(struct candidate ** K,int r,int k,int j)99 static int search (struct candidate **K, int r, int k, int j)
100 {
101 int low = r, upper = k, mid;
102
103 mid = (low + upper) / 2;
104 while (low <= mid) {
105 if (((struct candidate*)(K[mid]))->b < j &&
106 ((struct candidate*)(K[mid + 1]))->b > j)
107 return mid;
108
109 if (((struct candidate*)(K[mid]))->b < j) low = mid + 1;
110 else if (((struct candidate*)(K[mid]))->b > j) upper = mid - 1;
111 else return -1;
112
113 mid = (low + upper) / 2;
114 }
115 return -1;
116 }
117
new_candidate(int i,int j,struct candidate * prev)118 static struct candidate * new_candidate (int i, int j, struct candidate* prev)
119 {
120 struct candidate *c = xzalloc(sizeof(struct candidate));
121
122 c->a = i;
123 c->b = j;
124 c->prev = prev;
125 return c;
126 }
127
128
free_candidates(struct candidate * c)129 static void free_candidates(struct candidate *c)
130 {
131 struct candidate *t = c;
132
133 while ((t = c)) {
134 c = c->next;
135 free(t);
136 }
137 }
138 /*
139 * 1. Search K[r: k] for an element K[s] such that K[s]-> b < j and K[s + 1]->b > j
140 * 2. if found do
141 * 2.a. If K[s + 1]->b > j do K[r] = c; r = s+1 and c = candidate(i, j, K[s]) //we have a candidate
142 * 2.b. if s = k (fence reached move it further) do K[k + 2] = K[k + 1], k++
143 * 3. if E[p].last true break i.e we have reached at the end of an equiv class
144 * else p = p + 1 //keep traversing the equiv class.
145 * 4. K[r] = c //Save the sucessfully filled k-candidate.
146 */
do_merge(struct candidate ** K,int * k,int i,struct v_vector * E,int p)147 static void do_merge(struct candidate **K, int *k, int i,
148 struct v_vector *E, int p)
149 {
150 int r = 0, s, j;
151 struct candidate *pr = 0, *c = K[0];
152
153 while (1) {
154 j = E[p].serial;
155 s = search(K, r, *k, j);
156 if (s >= 0 && (((struct candidate*)(K[s]))->b < j &&
157 ((struct candidate*)(K[s + 1]))->b > j)) {
158
159 if (((struct candidate*)(K[s + 1]))->b > j) {
160 pr = K[s];
161 if (r && K[r]) c->next = K[r];
162 K[r] = c;
163 r = s + 1;
164 c = new_candidate(i , j, pr);
165 }
166 if (s == *k) {
167 K[*k + 2] = K[*k + 1];
168 *k = *k + 1;
169 break;
170 }
171 }
172 if (E[p].last) break;
173 else p = p + 1;
174 }
175 K[r] = c;
176 }
177
read_stdin()178 static FILE* read_stdin()
179 {
180 char tmp_name[] = "/tmp/diffXXXXXX";
181 int rd, wr, tmpfd = mkstemp(tmp_name);
182
183 if (tmpfd == -1) perror_exit("mkstemp");
184 unlink(tmp_name);
185
186 while (1) {
187 rd = xread(STDIN_FILENO, toybuf, sizeof(toybuf));
188
189 if (!rd) break;
190 if (rd < 0) perror_exit("read error");
191 wr = writeall(tmpfd, toybuf, rd);
192 if (wr < 0) perror_exit("write");
193 }
194 return fdopen(tmpfd, "r");
195 }
196
read_tok(FILE * fp,off_t * off,int tok)197 static int read_tok(FILE *fp, off_t *off, int tok)
198 {
199 int t = 0, is_space;
200
201 tok |= empty;
202 while (!(tok & eol)) {
203
204 t = fgetc(fp);
205 if (off && t != EOF) *off += 1;
206 is_space = isspace(t) || (t == EOF);
207 tok |= (t & (eof + eol)); //set tok eof+eol when t is eof
208
209 if (t == '\n') tok |= eol;
210 if (toys.optflags & FLAG_i)
211 if (t >= 'A' && t <= 'Z') t = tolower(t);
212
213 if (toys.optflags & FLAG_w && is_space) continue;
214
215 if (toys.optflags & FLAG_b) {
216 if (tok & space) {
217 if (is_space) continue;
218 tok &= ~space;
219 } else if (is_space) t = space + ' ';
220 }
221 tok &= ~(empty + 0xff); //remove empty and char too.
222 tok |= t; //add most recent char
223 break;
224 }
225
226 return tok;
227 }
228
bcomp(const void * a,const void * b)229 int bcomp(const void *a, const void *b)
230 {
231 struct v_vector *l = (struct v_vector*)a,
232 *r = (struct v_vector*)b;
233 int ret = l->hash - r->hash;
234
235 if (!ret) {
236 if ((r -1)->last) return 0;
237 else return -1;
238 }
239 return ret;
240 }
241 /* file[0] corresponds file 1 and file[1] correspond file 2.
242 * 1. calc hashes for both the files and store them in vector(v[0], v[1])
243 * 2. sort file[1] with hash as primary and serial as sec. key
244 * 3. Form the equivalance class of file[1] stored in e vector. It lists all the equivalence
245 * classes of lines in file[1], with e.last = true on the last element of each class.
246 * The elements are ordered by serial within classes.
247 * 4. Form the p vector stored in p_vector. p_vector[i], if non-zero, now points in e vector
248 * to the begining of the equiv class of lines in file[1] equivalent to line
249 * i in file[0].
250 * 5. Form the k-candidates as discribed in do_merge.
251 * 6. Create a vector J[i] = j, such that i'th line in file[0] is j'th line of
252 * file[1], i.e J comprises LCS
253 */
create_j_vector()254 static int * create_j_vector()
255 {
256 int tok, i, j, size = 100, k;
257 off_t off;
258 long hash;
259 int *p_vector, *J;
260 struct v_vector *v[2], *e;
261 struct candidate **kcand, *pr;
262
263 for (i = 0; i < 2; i++) {
264 tok = off = 0;
265 hash = 5831;
266 v[i] = xzalloc(size * sizeof(struct v_vector));
267 TT.offset[i] = xzalloc(size * sizeof(int));
268 file[i].len = 0;
269 fseek(file[i].fp, 0, SEEK_SET);
270
271 while (1) {
272 tok = read_tok(file[i].fp, &off, tok);
273 if (!(tok & empty)) {
274 hash = ((hash << 5) + hash) + (tok & 0xff);
275 continue;
276 }
277
278 if (size == ++file[i].len) {
279 size = size * 11 / 10;
280 v[i] = xrealloc(v[i], size*sizeof(struct v_vector));
281 TT.offset[i] = xrealloc(TT.offset[i], size*sizeof(int));
282 }
283
284 v[i][file[i].len].hash = hash & INT_MAX;
285 TT.offset[i][file[i].len] = off;
286 if ((tok & eof)) {
287 TT.offset[i][file[i].len] = ++off;
288 break;
289 }
290 hash = 5831; //next line
291 tok = 0;
292 }
293 if (TT.offset[i][file[i].len] - TT.offset[i][file[i].len - 1] == 1)
294 file[i].len--;
295 }
296
297 for (i = 0; i <= file[1].len; i++) v[1][i].serial = i;
298 qsort(v[1] + 1, file[1].len, sizeof(struct v_vector), comp);
299
300 e = v[1];
301 e[0].serial = 0;
302 e[0].last = 1;
303 for ( i = 1; i <= file[1].len; i++) {
304 if ((i == file[1].len) || (v[1][i].hash != v[1][i+1].hash)) e[i].last = 1;
305 else e[i].last = 0;
306 }
307
308 p_vector = xzalloc((file[0].len + 2) * sizeof(int));
309 for (i = 1; i <= file[0].len; i++) {
310 void *r = bsearch(&v[0][i], (e + 1), file[1].len, sizeof(e[0]), bcomp);
311 if (r) p_vector[i] = (struct v_vector*)r - e;
312 }
313
314 for (i = 1; i <= file[0].len; i++)
315 e[i].p = p_vector[i];
316 free(p_vector);
317
318 size = 100;
319 kcand = xzalloc(size * sizeof(struct candidate*));
320
321 kcand[0] = new_candidate(0 , 0, NULL);
322 kcand[1] = new_candidate(file[0].len+1, file[1].len+1, NULL); //the fence
323
324 k = 0; //last successfully filled k candidate.
325 for (i = 1; i <= file[0].len; i++) {
326
327 if (!e[i].p) continue;
328 if ((size - 2) == k) {
329 size = size * 11 / 10;
330 kcand = xrealloc(kcand, (size * sizeof(struct candidate*)));
331 }
332 do_merge(kcand, &k, i, e, e[i].p);
333 }
334 free(v[0]); //no need for v_vector now.
335 free(v[1]);
336
337 J = xzalloc((file[0].len + 2) * sizeof(int));
338
339 for (pr = kcand[k]; pr; pr = pr->prev)
340 J[pr->a] = pr->b;
341 J[file[0].len + 1] = file[1].len+1; //mark boundary
342
343 for (i = k + 1; i >= 0; i--) free_candidates(kcand[i]);
344 free(kcand);
345
346 for (i = 1; i <= file[0].len; i++) { // jackpot?
347 if (!J[i]) continue;
348
349 fseek(file[0].fp, TT.offset[0][i - 1], SEEK_SET);
350 fseek(file[1].fp, TT.offset[1][J[i] - 1], SEEK_SET);
351
352 for (j = J[i]; i <= file[0].len && J[i] == j; i++, j++) {
353 int tok0 = 0, tok1 = 0;
354
355 do {
356 tok0 = read_tok(file[0].fp, NULL, tok0);
357 tok1 = read_tok(file[1].fp, NULL, tok1);
358 if (((tok0 ^ tok1) & empty) || ((tok0 & 0xff) != (tok1 & 0xff)))
359 J[i] = 0;
360 } while (!(tok0 & tok1 & empty));
361 }
362 }
363 return J;
364 }
365
diff(char ** files)366 static int *diff(char **files)
367 {
368 size_t i ,j;
369 int s, t;
370 char *bufi, *bufj;
371
372 TT.is_binary = 0; //loop calls to diff
373 TT.status = SAME;
374
375 for (i = 0; i < 2; i++) {
376 if (IS_STDIN(files[i])) file[i].fp = read_stdin();
377 else file[i].fp = fopen(files[i], "r");
378
379 if (!file[i].fp){
380 perror_msg("%s",files[i]);
381 TT.status = 2;
382 return NULL; //return SAME
383 }
384 }
385
386 s = sizeof(toybuf)/2;
387 bufi = toybuf;
388 bufj = (toybuf + s);
389
390 fseek(file[0].fp, 0, SEEK_SET);
391 fseek(file[1].fp, 0, SEEK_SET);
392
393 if (toys.optflags & FLAG_a) return create_j_vector();
394
395 while (1) {
396 i = fread(bufi, 1, s, file[0].fp);
397 j = fread(bufj, 1, s, file[1].fp);
398
399 if (i != j) TT.status = DIFFER;
400
401 for (t = 0; t < i && !TT.is_binary; t++)
402 if (!bufi[t]) TT.is_binary = 1;
403 for (t = 0; t < j && !TT.is_binary; t++)
404 if (!bufj[t]) TT.is_binary = 1;
405
406 i = MIN(i, j);
407 for (t = 0; t < i; t++)
408 if (bufi[t] != bufj[t]) TT.status = DIFFER;
409
410 if (!i || !j) break;
411 }
412 if (TT.is_binary || (TT.status == SAME)) return NULL;
413 return create_j_vector();
414 }
415
print_diff(int a,int b,char c,int * off_set,FILE * fp)416 static void print_diff(int a, int b, char c, int *off_set, FILE *fp)
417 {
418 int i, j, cc, cl;
419
420 for (i = a; i <= b; i++) {
421 fseek(fp, off_set[i - 1], SEEK_SET);
422 putchar(c);
423 if (toys.optflags & FLAG_T) putchar('\t');
424 for (j = 0, cl = 0; j < (off_set[i] - off_set[i - 1]); j++) {
425 cc = fgetc(fp);
426 if (cc == EOF) {
427 printf("\n\\ No newline at end of file\n");
428 return;
429 }
430 if ((cc == '\t') && (toys.optflags & FLAG_t))
431 do putchar(' '); while (++cl & 7);
432 else {
433 putchar(cc); //xputc has calls to fflush, it hurts performance badly.
434 cl++;
435 }
436 }
437 }
438 }
439
concat_file_path(char * path,char * default_path)440 static char *concat_file_path(char *path, char *default_path)
441 {
442 char *final_path;
443
444 if ('/' == path[strlen(path) - 1]) {
445 while (*default_path == '/') ++default_path;
446 final_path = xmprintf("%s%s", path, default_path);
447 }
448 else if (*default_path != '/')
449 final_path = xmprintf("%s/%s", path, default_path);
450 else final_path = xmprintf("%s%s", path, default_path);
451 return final_path;
452 }
453
skip(struct dirtree * node)454 static int skip(struct dirtree *node)
455 {
456 int len = strlen(toys.optargs[TT.dir_num]), ret = 0;
457 char *tmp = NULL, *ptr, *f_path = dirtree_path(node, NULL);
458 struct stat st;
459
460 ptr = f_path;
461 ptr += len;
462 if (ptr[0]) {
463 tmp = concat_file_path(toys.optargs[1 - TT.dir_num], ptr);
464 if (tmp && !stat(tmp, &st)) ret = 0; //it is there on other side
465 else ret = 1; //not present on other side.
466 }
467 free(f_path);
468 if (tmp) free(tmp);
469 return ret; //add otherwise
470 }
471
add_to_list(struct dirtree * node)472 static void add_to_list(struct dirtree *node)
473 {
474 char *full_path;
475
476 dir[TT.dir_num].list = xrealloc(dir[TT.dir_num].list,
477 (TT.size + 1)*sizeof(char*));
478 TT.size++;
479 full_path = dirtree_path(node, NULL);
480 dir[TT.dir_num].list[TT.size - 1] = full_path;
481 }
482
list_dir(struct dirtree * node)483 static int list_dir (struct dirtree *node)
484 {
485 int ret = 0;
486
487 if (node->parent && !dirtree_notdotdot(node)) return 0;
488
489 if (S_ISDIR(node->st.st_mode) && !node->parent) { //add root dirs.
490 add_to_list(node);
491 return (DIRTREE_RECURSE|DIRTREE_SYMFOLLOW);
492 }
493
494 if (S_ISDIR(node->st.st_mode) && (toys.optflags & FLAG_r)) {
495 if (!(toys.optflags & FLAG_N)) ret = skip(node);
496 if (!ret) return (DIRTREE_RECURSE|DIRTREE_SYMFOLLOW);
497 else {
498 add_to_list(node); //only at one side.
499 return 0;
500 }
501 } else {
502 add_to_list(node);
503 return S_ISDIR(node->st.st_mode) ? 0 : (DIRTREE_RECURSE|DIRTREE_SYMFOLLOW);
504 }
505 }
506
cmp(const void * p1,const void * p2)507 static int cmp(const void *p1, const void *p2)
508 {
509 return strcmp(* (char * const *)p1, * (char * const *)p2);
510 }
511
do_diff(char ** files)512 static void do_diff(char **files)
513 {
514
515 long i = 1, size = 1, x = 0, change = 0, ignore_white,
516 start1, end1, start2, end2;
517 struct diff *d;
518 struct arg_list *llist = TT.L_list;
519 int *J;
520
521 TT.offset[0] = TT.offset[1] = NULL;
522 J = diff(files);
523
524 if (!J) return; //No need to compare, have to status only
525
526 d = xzalloc(size *sizeof(struct diff));
527 do {
528 ignore_white = 0;
529 for (d[x].a = i; d[x].a <= file[0].len; d[x].a++) {
530 if (J[d[x].a] != (J[d[x].a - 1] + 1)) break;
531 else continue;
532 }
533 d[x].c = (J[d[x].a - 1] + 1);
534
535 for (d[x].b = (d[x].a - 1); d[x].b <= file[0].len; d[x].b++) {
536 if (J[d[x].b + 1]) break;
537 else continue;
538 }
539 d[x].d = (J[d[x].b + 1] - 1);
540
541 if ((toys.optflags & FLAG_B)) {
542 if (d[x].a <= d[x].b) {
543 if ((TT.offset[0][d[x].b] - TT.offset[0][d[x].a - 1])
544 == (d[x].b - d[x].a + 1))
545 ignore_white = 1;
546 } else if (d[x].c <= d[x].d){
547 if ((TT.offset[1][d[x].d] - TT.offset[1][d[x].c - 1])
548 == (d[x].d - d[x].c + 1))
549 ignore_white = 1;
550 }
551 }
552
553 if ((d[x].a <= d[x].b || d[x].c <= d[x].d) && !ignore_white)
554 change = 1; //is we have diff ?
555
556 if (!ignore_white) d = xrealloc(d, (x + 2) *sizeof(struct diff));
557 i = d[x].b + 1;
558 if (i > file[0].len) break;
559 J[d[x].b] = d[x].d;
560 if (!ignore_white) x++;
561 } while (i <= file[0].len);
562
563 i = x+1;
564 TT.status = change; //update status, may change bcoz of -w etc.
565
566 if (!(toys.optflags & FLAG_q) && change) { //start of !FLAG_q
567
568 xprintf("--- %s\n", (toys.optflags & FLAG_L) ? llist->arg : files[0]);
569 if (((toys.optflags & FLAG_L) && !llist->next) || !(toys.optflags & FLAG_L))
570 xprintf("+++ %s\n", files[1]);
571 else {
572 while (llist->next) llist = llist->next;
573 xprintf("+++ %s\n", llist->arg);
574 }
575
576 struct diff *t, *ptr1 = d, *ptr2 = d;
577 while (i) {
578 long a,b;
579
580 if (TT.ct > file[0].len) TT.ct = file[0].len; //trim context to file len.
581 if (ptr1->b < ptr1->a && ptr1->d < ptr1->c) {
582 i--;
583 continue;
584 }
585 //Handle the context stuff
586 a = ptr1->a;
587 b = ptr1->b;
588
589 b = MIN(file[0].len, b);
590 if (i == x + 1) ptr1->suff = MAX(1,a - TT.ct);
591 else {
592 if ((ptr1 - 1)->prev >= (ptr1->a - TT.ct))
593 ptr1->suff = (ptr1 - 1)->prev + 1;
594 else ptr1->suff = ptr1->a - TT.ct;
595 }
596 calc_ct:
597 if (i > 1) {
598 if ((ptr2->b + TT.ct) >= (ptr2 + 1)->a) {
599 ptr2++;
600 i--;
601 goto calc_ct;
602 } else ptr2->prev = ptr2->b + TT.ct;
603 } else ptr2->prev = ptr2->b;
604 start1 = (ptr2->prev - ptr1->suff + 1);
605 end1 = (start1 == 1) ? -1 : start1;
606 start2 = MAX(1, ptr1->c - (ptr1->a - ptr1->suff));
607 end2 = ptr2->prev - ptr2->b + ptr2->d;
608
609 printf("@@ -%ld", start1 ? ptr1->suff: (ptr1->suff -1));
610 if (end1 != -1) printf(",%ld ", ptr2->prev-ptr1->suff + 1);
611 else putchar(' ');
612
613 printf("+%ld", (end2 - start2 + 1) ? start2: (start2 -1));
614 if ((end2 - start2 +1) != 1) printf(",%ld ", (end2 - start2 +1));
615 else putchar(' ');
616 printf("@@\n");
617
618 for (t = ptr1; t <= ptr2; t++) {
619 if (t== ptr1) print_diff(t->suff, t->a-1, ' ', TT.offset[0], file[0].fp);
620 print_diff(t->a, t->b, '-', TT.offset[0], file[0].fp);
621 print_diff(t->c, t->d, '+', TT.offset[1], file[1].fp);
622 if (t == ptr2)
623 print_diff(t->b+1, (t)->prev, ' ', TT.offset[0], file[0].fp);
624 else print_diff(t->b+1, (t+1)->a-1, ' ', TT.offset[0], file[0].fp);
625 }
626 ptr2++;
627 ptr1 = ptr2;
628 i--;
629 } //end of while
630 } //End of !FLAG_q
631 free(d);
632 free(J);
633 free(TT.offset[0]);
634 free(TT.offset[1]);
635 }
636
show_status(char ** files)637 static void show_status(char **files)
638 {
639 switch (TT.status) {
640 case SAME:
641 if (toys.optflags & FLAG_s)
642 printf("Files %s and %s are identical\n",files[0], files[1]);
643 break;
644 case DIFFER:
645 if ((toys.optflags & FLAG_q) || TT.is_binary)
646 printf("Files %s and %s differ\n",files[0], files[1]);
647 break;
648 }
649 }
650
create_empty_entry(int l,int r,int j)651 static void create_empty_entry(int l , int r, int j)
652 {
653 struct stat st[2];
654 char *f[2], *path[2];
655 int i;
656
657 if (j > 0 && (toys.optflags & FLAG_N)) {
658 path[0] = concat_file_path(dir[0].list[0], dir[1].list[r] + TT.len[1]);
659 f[0] = "/dev/null";
660 path[1] = f[1] = dir[1].list[r];
661 stat(f[1], &st[0]);
662 st[1] = st[0];
663 }
664 else if (j < 0 && (toys.optflags & FLAG_N)) {
665 path[1] = concat_file_path(dir[1].list[0], dir[0].list[l] + TT.len[0]);
666 f[1] = "/dev/null";
667 path[0] = f[0] = dir[0].list[l];
668 stat(f[0], &st[0]);
669 st[1] = st[0];
670 }
671
672 if (!j) {
673 for (i = 0; i < 2; i++) {
674 path[i] = f[i] = dir[i].list[!i ? l: r];
675 stat(f[i], &st[i]);
676 }
677 }
678
679 if (S_ISDIR(st[0].st_mode) && S_ISDIR(st[1].st_mode))
680 printf("Common subdirectories: %s and %s\n", path[0], path[1]);
681 else if (!S_ISREG(st[0].st_mode) && !S_ISDIR(st[0].st_mode))
682 printf("File %s is not a regular file or directory "
683 "and was skipped\n", path[0]);
684 else if (!S_ISREG(st[1].st_mode) && !S_ISDIR(st[1].st_mode))
685 printf("File %s is not a regular file or directory "
686 "and was skipped\n", path[1]);
687 else if (S_ISDIR(st[0].st_mode) != S_ISDIR(st[1].st_mode)) {
688 if (S_ISDIR(st[0].st_mode))
689 printf("File %s is a %s while file %s is a"
690 " %s\n", path[0], "directory", path[1], "regular file");
691 else
692 printf("File %s is a %s while file %s is a"
693 " %s\n", path[0], "regular file", path[1], "directory");
694 } else {
695 do_diff(f);
696 show_status(path);
697 if (file[0].fp) fclose(file[0].fp);
698 if (file[1].fp) fclose(file[1].fp);
699 }
700
701 if ((toys.optflags & FLAG_N) && j) {
702 if (j > 0) free(path[0]);
703 else free(path[1]);
704 }
705 }
706
diff_dir(int * start)707 static void diff_dir(int *start)
708 {
709 int l, r, j = 0;
710
711 l = start[0]; //left side file start
712 r = start[1]; //right side file start
713 while (l < dir[0].nr_elm && r < dir[1].nr_elm) {
714 if ((j = strcmp ((dir[0].list[l] + TT.len[0]),
715 (dir[1].list[r] + TT.len[1]))) && !(toys.optflags & FLAG_N)) {
716 if (j > 0) {
717 printf ("Only in %s: %s\n", dir[1].list[0], dir[1].list[r] + TT.len[1]);
718 free(dir[1].list[r]);
719 r++;
720 } else {
721 printf ("Only in %s: %s\n", dir[0].list[0], dir[0].list[l] + TT.len[0]);
722 free(dir[0].list[l]);
723 l++;
724 }
725 TT.status = DIFFER;
726 } else {
727 create_empty_entry(l, r, j); //create non empty dirs/files if -N.
728 if (j > 0) {
729 free(dir[1].list[r]);
730 r++;
731 } else if (j < 0) {
732 free(dir[0].list[l]);
733 l++;
734 } else {
735 free(dir[1].list[r]);
736 free(dir[0].list[l]);
737 l++;
738 r++;
739 }
740 }
741 }
742
743 if (l == dir[0].nr_elm) {
744 while (r < dir[1].nr_elm) {
745 if (!(toys.optflags & FLAG_N)) {
746 printf ("Only in %s: %s\n", dir[1].list[0], dir[1].list[r] + TT.len[1]);
747 TT.status = DIFFER;
748 } else create_empty_entry(l, r, 1);
749 free(dir[1].list[r]);
750 r++;
751 }
752 } else if (r == dir[1].nr_elm) {
753 while (l < dir[0].nr_elm) {
754 if (!(toys.optflags & FLAG_N)) {
755 printf ("Only in %s: %s\n", dir[0].list[0], dir[0].list[l] + TT.len[0]);
756 TT.status = DIFFER;
757 } else create_empty_entry(l, r, -1);
758 free(dir[0].list[l]);
759 l++;
760 }
761 }
762 free(dir[0].list[0]); //we are done, free root nodes too
763 free(dir[1].list[0]);
764 }
765
diff_main(void)766 void diff_main(void)
767 {
768 struct stat st[2];
769 int j = 0, k = 1, start[2] = {1, 1};
770 char *files[2];
771
772 for (j = 0; j < 2; j++) {
773 files[j] = toys.optargs[j];
774 if (IS_STDIN(files[j])) {
775 if (fstat(0, &st[j]) == -1)
776 perror_exit("can fstat %s", files[j]);
777 } else {
778 if (stat(files[j], &st[j]) == -1)
779 perror_exit("can't stat %s", files[j]);
780 }
781 }
782
783 if (IS_STDIN(files[0]) && IS_STDIN(files[1])) { //compat :(
784 show_status(files); //check ASAP
785 return;
786 }
787
788 if ((IS_STDIN(files[0]) || IS_STDIN(files[1]))
789 && (S_ISDIR(st[0].st_mode) || S_ISDIR(st[1].st_mode)))
790 error_exit("can't compare stdin to directory");
791
792 if ((st[0].st_ino == st[1].st_ino) //physicaly same device
793 &&(st[0].st_dev == st[1].st_dev)) {
794 show_status(files);
795 return ;
796 }
797
798 if (S_ISDIR(st[0].st_mode) && S_ISDIR(st[1].st_mode)) {
799 for (j = 0; j < 2; j++) {
800 memset(&dir[j], 0, sizeof(dir));
801 dirtree_handle_callback(dirtree_start(files[j], 1), list_dir);
802 dir[j].nr_elm = TT.size; //size updated in list_dir
803 qsort(&(dir[j].list[1]), (TT.size - 1), sizeof(char*), cmp);
804
805 TT.len[j] = strlen(dir[j].list[0]); //calc root node len
806 TT.len[j] += (dir[j].list[0][TT.len[j] -1] != '/');
807
808 if (toys.optflags & FLAG_S) {
809 while (k < TT.size && strcmp(dir[j].list[k] +
810 TT.len[j], TT.start) < 0) {
811 start[j] += 1;
812 k++;
813 }
814 }
815 TT.dir_num++;
816 TT.size = 0;
817 k = 1;
818 }
819 diff_dir(start);
820 free(dir[0].list); //free array
821 free(dir[1].list);
822 } else {
823 if (S_ISDIR(st[0].st_mode) || S_ISDIR(st[1].st_mode)) {
824 int d = S_ISDIR(st[0].st_mode);
825 char *slash = strrchr(files[d], '/');
826
827 files[1 - d] = concat_file_path(files[1 - d], slash ? slash + 1 : files[d]);
828 if ((stat(files[1 - d], &st[1 - d])) == -1)
829 perror_exit("%s", files[1 - d]);
830 }
831 do_diff(files);
832 show_status(files);
833 if (file[0].fp) fclose(file[0].fp);
834 if (file[1].fp) fclose(file[1].fp);
835 }
836 toys.exitval = TT.status; //exit status will be the status
837 }
838