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>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 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 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 40 GLOBALS( 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 54 struct v_vector { 55 unsigned serial:31; 56 unsigned last:1; 57 union { 58 unsigned hash; 59 unsigned p; 60 }; 61 }; 62 63 struct diff { 64 long a, b, c, d, prev, suff; 65 }; 66 67 static struct dir_t { 68 char **list; 69 int nr_elm; 70 } dir[2]; 71 72 struct candidate { 73 int a, b; 74 struct candidate *prev, *next; 75 }; 76 77 static struct file_t { 78 FILE *fp; 79 int len; 80 } file[2]; 81 82 enum { 83 SAME, 84 DIFFER, 85 }; 86 87 enum { 88 empty = 1 << 9, 89 eol = 1 << 10, 90 eof = 1 << 11, 91 space = 1 << 12 92 }; 93 94 static 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 104 static 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 123 static 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 134 static 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 */ 152 static 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 183 static 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 195 static 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 237 int 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 */ 262 static 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 374 static 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 424 static 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 455 static 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 469 static 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 487 static 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 498 static 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 522 static 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 528 char *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 576 static 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 587 static 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 } 673 calc_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 717 static 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 731 static 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 787 static 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 846 void 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