toys/pending/diff.c

   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_t {
  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_t {
  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
  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
  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
 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
 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  */
 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
 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
 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
 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  */
 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
 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
 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
 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
 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
 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
 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
 507 static int cmp(const void *p1, const void *p2)
 508 {
 509    return strcmp(* (char * const *)p1, * (char * const *)p2);
 510 }
 511
 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
 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
 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
 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
 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(struct dir_t));
 801       dirtree_flagread(files[j], DIRTREE_SYMFOLLOW, 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 }