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