find.c (27161B)
1 /* See LICENSE file for copyright and license details. */ 2 #include <dirent.h> 3 #include <errno.h> 4 #include <fnmatch.h> 5 #include <grp.h> 6 #include <libgen.h> 7 #include <pwd.h> 8 #include <stdint.h> 9 #include <stdio.h> 10 #include <stdlib.h> 11 #include <string.h> 12 #include <time.h> 13 #include <unistd.h> 14 15 #include <sys/stat.h> 16 #include <sys/wait.h> 17 18 #include "util.h" 19 20 /* because putting integers in pointers is undefined by the standard */ 21 union extra { 22 void *p; 23 intmax_t i; 24 }; 25 26 /* Argument passed into a primary's function */ 27 struct arg { 28 char *path; 29 struct stat *st; 30 union extra extra; 31 }; 32 33 /* Information about each primary, for lookup table */ 34 struct pri_info { 35 char *name; 36 int (*func)(struct arg *arg); 37 char **(*getarg)(char **argv, union extra *extra); 38 void (*freearg)(union extra extra); 39 char narg; /* -xdev, -depth, -print don't take args but have getarg() */ 40 }; 41 42 /* Information about operators, for lookup table */ 43 struct op_info { 44 char *name; /* string representation of op */ 45 char type; /* from tok.type */ 46 char prec; /* precedence */ 47 char nargs; /* number of arguments (unary or binary) */ 48 char lassoc; /* left associative */ 49 }; 50 51 /* Token when lexing/parsing 52 * (although also used for the expression tree) */ 53 struct tok { 54 struct tok *left, *right; /* if (type == NOT) left = NULL */ 55 union extra extra; 56 union { 57 struct pri_info *pinfo; /* if (type == PRIM) */ 58 struct op_info *oinfo; 59 } u; 60 enum { 61 PRIM = 0, LPAR, RPAR, NOT, AND, OR, END 62 } type; 63 }; 64 65 /* structures used for arg.extra.p and tok.extra.p */ 66 struct permarg { 67 mode_t mode; 68 char exact; 69 }; 70 71 struct okarg { 72 char ***braces; 73 char **argv; 74 }; 75 76 /* for all arguments that take a number 77 * +n, n, -n mean > n, == n, < n respectively */ 78 struct narg { 79 int (*cmp)(int a, int b); 80 int n; 81 }; 82 83 struct sizearg { 84 struct narg n; 85 char bytes; /* size is in bytes, not 512 byte sectors */ 86 }; 87 88 struct execarg { 89 union { 90 struct { 91 char ***braces; /* NULL terminated list of pointers into argv where {} were */ 92 } s; /* semicolon */ 93 struct { 94 size_t arglen; /* number of bytes in argv before files are added */ 95 size_t filelen; /* numer of bytes in file names added to argv */ 96 size_t first; /* index one past last arg, where first file goes */ 97 size_t next; /* index where next file goes */ 98 size_t cap; /* capacity of argv */ 99 } p; /* plus */ 100 } u; 101 char **argv; /* NULL terminated list of arguments (allocated if isplus) */ 102 char isplus; /* -exec + instead of -exec ; */ 103 }; 104 105 /* used to find loops while recursing through directory structure */ 106 struct findhist { 107 struct findhist *next; 108 char *path; 109 dev_t dev; 110 ino_t ino; 111 }; 112 113 /* Utility */ 114 static int spawn(char *argv[]); 115 static int do_stat(char *path, struct stat *sb, struct findhist *hist); 116 117 /* Primaries */ 118 static int pri_name (struct arg *arg); 119 static int pri_path (struct arg *arg); 120 static int pri_nouser (struct arg *arg); 121 static int pri_nogroup(struct arg *arg); 122 static int pri_xdev (struct arg *arg); 123 static int pri_prune (struct arg *arg); 124 static int pri_perm (struct arg *arg); 125 static int pri_type (struct arg *arg); 126 static int pri_links (struct arg *arg); 127 static int pri_user (struct arg *arg); 128 static int pri_group (struct arg *arg); 129 static int pri_size (struct arg *arg); 130 static int pri_atime (struct arg *arg); 131 static int pri_ctime (struct arg *arg); 132 static int pri_mtime (struct arg *arg); 133 static int pri_exec (struct arg *arg); 134 static int pri_ok (struct arg *arg); 135 static int pri_print (struct arg *arg); 136 static int pri_print0 (struct arg *arg); 137 static int pri_newer (struct arg *arg); 138 static int pri_depth (struct arg *arg); 139 140 /* Getargs */ 141 static char **get_name_arg (char *argv[], union extra *extra); 142 static char **get_path_arg (char *argv[], union extra *extra); 143 static char **get_xdev_arg (char *argv[], union extra *extra); 144 static char **get_perm_arg (char *argv[], union extra *extra); 145 static char **get_type_arg (char *argv[], union extra *extra); 146 static char **get_n_arg (char *argv[], union extra *extra); 147 static char **get_user_arg (char *argv[], union extra *extra); 148 static char **get_group_arg(char *argv[], union extra *extra); 149 static char **get_size_arg (char *argv[], union extra *extra); 150 static char **get_exec_arg (char *argv[], union extra *extra); 151 static char **get_ok_arg (char *argv[], union extra *extra); 152 static char **get_print_arg(char *argv[], union extra *extra); 153 static char **get_newer_arg(char *argv[], union extra *extra); 154 static char **get_depth_arg(char *argv[], union extra *extra); 155 156 /* Freeargs */ 157 static void free_extra (union extra extra); 158 static void free_exec_arg(union extra extra); 159 static void free_ok_arg (union extra extra); 160 161 /* Parsing/Building/Running */ 162 static void fill_narg(char *s, struct narg *n); 163 static struct pri_info *find_primary(char *name); 164 static struct op_info *find_op(char *name); 165 static void parse(int argc, char **argv); 166 static int eval(struct tok *tok, struct arg *arg); 167 static void find(char *path, struct findhist *hist); 168 static void usage(void); 169 170 /* for comparisons with narg */ 171 static int cmp_gt(int a, int b) { return a > b; } 172 static int cmp_eq(int a, int b) { return a == b; } 173 static int cmp_lt(int a, int b) { return a < b; } 174 175 /* order from find(1p), may want to alphabetize */ 176 static struct pri_info primaries[] = { 177 { "-name" , pri_name , get_name_arg , NULL , 1 }, 178 { "-path" , pri_path , get_path_arg , NULL , 1 }, 179 { "-nouser" , pri_nouser , NULL , NULL , 1 }, 180 { "-nogroup", pri_nogroup, NULL , NULL , 1 }, 181 { "-xdev" , pri_xdev , get_xdev_arg , NULL , 0 }, 182 { "-prune" , pri_prune , NULL , NULL , 1 }, 183 { "-perm" , pri_perm , get_perm_arg , free_extra , 1 }, 184 { "-type" , pri_type , get_type_arg , NULL , 1 }, 185 { "-links" , pri_links , get_n_arg , free_extra , 1 }, 186 { "-user" , pri_user , get_user_arg , NULL , 1 }, 187 { "-group" , pri_group , get_group_arg, NULL , 1 }, 188 { "-size" , pri_size , get_size_arg , free_extra , 1 }, 189 { "-atime" , pri_atime , get_n_arg , free_extra , 1 }, 190 { "-ctime" , pri_ctime , get_n_arg , free_extra , 1 }, 191 { "-mtime" , pri_mtime , get_n_arg , free_extra , 1 }, 192 { "-exec" , pri_exec , get_exec_arg , free_exec_arg, 1 }, 193 { "-ok" , pri_ok , get_ok_arg , free_ok_arg , 1 }, 194 { "-print" , pri_print , get_print_arg, NULL , 0 }, 195 { "-print0" , pri_print0 , get_print_arg, NULL , 0 }, 196 { "-newer" , pri_newer , get_newer_arg, NULL , 1 }, 197 { "-depth" , pri_depth , get_depth_arg, NULL , 0 }, 198 199 { NULL, NULL, NULL, NULL, 0 } 200 }; 201 202 static struct op_info ops[] = { 203 { "(" , LPAR, 0, 0, 0 }, /* parens are handled specially */ 204 { ")" , RPAR, 0, 0, 0 }, 205 { "!" , NOT , 3, 1, 0 }, 206 { "-a", AND , 2, 2, 1 }, 207 { "-o", OR , 1, 2, 1 }, 208 209 { NULL, 0, 0, 0, 0 } 210 }; 211 212 extern char **environ; 213 214 static struct tok *toks; /* holds allocated array of all toks created while parsing */ 215 static struct tok *root; /* points to root of expression tree, inside toks array */ 216 217 static struct timespec start; /* time find was started, used for -[acm]time */ 218 219 static size_t envlen; /* number of bytes in environ, used to calculate against ARG_MAX */ 220 static size_t argmax; /* value of ARG_MAX retrieved using sysconf(3p) */ 221 222 static struct { 223 char ret ; /* return value from main */ 224 char depth; /* -depth, directory contents before directory itself */ 225 char h ; /* -H, follow symlinks on command line */ 226 char l ; /* -L, follow all symlinks (command line and search) */ 227 char prune; /* hit -prune */ 228 char xdev ; /* -xdev, prune directories on different devices */ 229 char print; /* whether we will need -print when parsing */ 230 } gflags; 231 232 /* 233 * Utility 234 */ 235 static int 236 spawn(char *argv[]) 237 { 238 pid_t pid; 239 int status; 240 241 /* flush stdout so that -print output always appears before 242 * any output from the command and does not get cut-off in 243 * the middle of a line. */ 244 fflush(stdout); 245 246 switch((pid = fork())) { 247 case -1: 248 eprintf("fork:"); 249 case 0: 250 execvp(*argv, argv); 251 weprintf("exec %s failed:", *argv); 252 _exit(1); 253 } 254 255 /* FIXME: proper course of action for waitpid() on EINTR? */ 256 waitpid(pid, &status, 0); 257 return status; 258 } 259 260 static int 261 do_stat(char *path, struct stat *sb, struct findhist *hist) 262 { 263 if (gflags.l || (gflags.h && !hist)) { 264 if (stat(path, sb) == 0) { 265 return 0; 266 } else if (errno != ENOENT && errno != ENOTDIR) { 267 return -1; 268 } 269 } 270 271 return lstat(path, sb); 272 } 273 274 /* 275 * Primaries 276 */ 277 static int 278 pri_name(struct arg *arg) 279 { 280 int ret; 281 char *path; 282 283 path = estrdup(arg->path); 284 ret = !fnmatch((char *)arg->extra.p, basename(path), 0); 285 free(path); 286 287 return ret; 288 } 289 290 static int 291 pri_path(struct arg *arg) 292 { 293 return !fnmatch((char *)arg->extra.p, arg->path, 0); 294 } 295 296 /* FIXME: what about errors? find(1p) literally just says 297 * "for which the getpwuid() function ... returns NULL" */ 298 static int 299 pri_nouser(struct arg *arg) 300 { 301 return !getpwuid(arg->st->st_uid); 302 } 303 304 static int 305 pri_nogroup(struct arg *arg) 306 { 307 return !getgrgid(arg->st->st_gid); 308 } 309 310 static int 311 pri_xdev(struct arg *arg) 312 { 313 return 1; 314 } 315 316 static int 317 pri_prune(struct arg *arg) 318 { 319 return gflags.prune = 1; 320 } 321 322 static int 323 pri_perm(struct arg *arg) 324 { 325 struct permarg *p = (struct permarg *)arg->extra.p; 326 327 return (arg->st->st_mode & 07777 & (p->exact ? -1U : p->mode)) == p->mode; 328 } 329 330 static int 331 pri_type(struct arg *arg) 332 { 333 switch ((char)arg->extra.i) { 334 default : return 0; /* impossible, but placate warnings */ 335 case 'b': return S_ISBLK (arg->st->st_mode); 336 case 'c': return S_ISCHR (arg->st->st_mode); 337 case 'd': return S_ISDIR (arg->st->st_mode); 338 case 'l': return S_ISLNK (arg->st->st_mode); 339 case 'p': return S_ISFIFO(arg->st->st_mode); 340 case 'f': return S_ISREG (arg->st->st_mode); 341 case 's': return S_ISSOCK(arg->st->st_mode); 342 } 343 } 344 345 static int 346 pri_links(struct arg *arg) 347 { 348 struct narg *n = arg->extra.p; 349 return n->cmp(arg->st->st_nlink, n->n); 350 } 351 352 static int 353 pri_user(struct arg *arg) 354 { 355 return arg->st->st_uid == (uid_t)arg->extra.i; 356 } 357 358 static int 359 pri_group(struct arg *arg) 360 { 361 return arg->st->st_gid == (gid_t)arg->extra.i; 362 } 363 364 static int 365 pri_size(struct arg *arg) 366 { 367 struct sizearg *s = arg->extra.p; 368 off_t size = arg->st->st_size; 369 370 if (!s->bytes) 371 size = size / 512 + !!(size % 512); 372 373 return s->n.cmp(size, s->n.n); 374 } 375 376 /* FIXME: ignoring nanoseconds in atime, ctime, mtime */ 377 static int 378 pri_atime(struct arg *arg) 379 { 380 struct narg *n = arg->extra.p; 381 return n->cmp((start.tv_sec - arg->st->st_atime) / 86400, n->n); 382 } 383 384 static int 385 pri_ctime(struct arg *arg) 386 { 387 struct narg *n = arg->extra.p; 388 return n->cmp((start.tv_sec - arg->st->st_ctime) / 86400, n->n); 389 } 390 391 static int 392 pri_mtime(struct arg *arg) 393 { 394 struct narg *n = arg->extra.p; 395 return n->cmp((start.tv_sec - arg->st->st_mtime) / 86400, n->n); 396 } 397 398 static int 399 pri_exec(struct arg *arg) 400 { 401 int status; 402 size_t len; 403 char **sp, ***brace; 404 struct execarg *e = arg->extra.p; 405 406 if (e->isplus) { 407 len = strlen(arg->path) + 1; 408 409 /* if we reached ARG_MAX, fork, exec, wait, free file names, reset list */ 410 if (len + e->u.p.arglen + e->u.p.filelen + envlen > argmax) { 411 e->argv[e->u.p.next] = NULL; 412 413 status = spawn(e->argv); 414 gflags.ret = gflags.ret || status; 415 416 for (sp = e->argv + e->u.p.first; *sp; sp++) 417 free(*sp); 418 419 e->u.p.next = e->u.p.first; 420 e->u.p.filelen = 0; 421 } 422 423 /* if we have too many files, realloc (with space for NULL termination) */ 424 if (e->u.p.next + 1 == e->u.p.cap) 425 e->argv = ereallocarray(e->argv, e->u.p.cap *= 2, sizeof(*e->argv)); 426 427 e->argv[e->u.p.next++] = estrdup(arg->path); 428 e->u.p.filelen += len + sizeof(arg->path); 429 430 return 1; 431 } else { 432 /* insert path everywhere user gave us {} */ 433 for (brace = e->u.s.braces; *brace; brace++) 434 **brace = arg->path; 435 436 status = spawn(e->argv); 437 return !!status; 438 } 439 } 440 441 static int 442 pri_ok(struct arg *arg) 443 { 444 int status, reply; 445 char ***brace, c; 446 struct okarg *o = arg->extra.p; 447 448 fprintf(stderr, "%s: %s ? ", *o->argv, arg->path); 449 reply = fgetc(stdin); 450 451 /* throw away rest of line */ 452 while ((c = fgetc(stdin)) != '\n' && c != EOF) 453 /* FIXME: what if the first character of the rest of the line is a null 454 * byte? */ 455 ; 456 457 if (feof(stdin)) /* FIXME: ferror()? */ 458 clearerr(stdin); 459 460 if (reply != 'y' && reply != 'Y') 461 return 0; 462 463 /* insert filename everywhere user gave us {} */ 464 for (brace = o->braces; *brace; brace++) 465 **brace = arg->path; 466 467 status = spawn(o->argv); 468 return !!status; 469 } 470 471 static int 472 pri_print(struct arg *arg) 473 { 474 if (puts(arg->path) == EOF) 475 eprintf("puts failed:"); 476 return 1; 477 } 478 479 static int 480 pri_print0(struct arg *arg) 481 { 482 if (fwrite(arg->path, strlen(arg->path) + 1, 1, stdout) != 1) 483 eprintf("fwrite failed:"); 484 return 1; 485 } 486 487 /* FIXME: ignoring nanoseconds */ 488 static int 489 pri_newer(struct arg *arg) 490 { 491 return arg->st->st_mtime > (time_t)arg->extra.i; 492 } 493 494 static int 495 pri_depth(struct arg *arg) 496 { 497 return 1; 498 } 499 500 /* 501 * Getargs 502 * consume any arguments for given primary and fill extra 503 * return pointer to last argument, the pointer will be incremented in parse() 504 */ 505 static char ** 506 get_name_arg(char *argv[], union extra *extra) 507 { 508 extra->p = *argv; 509 return argv; 510 } 511 512 static char ** 513 get_path_arg(char *argv[], union extra *extra) 514 { 515 extra->p = *argv; 516 return argv; 517 } 518 519 static char ** 520 get_xdev_arg(char *argv[], union extra *extra) 521 { 522 gflags.xdev = 1; 523 return argv; 524 } 525 526 static char ** 527 get_perm_arg(char *argv[], union extra *extra) 528 { 529 mode_t mask; 530 struct permarg *p = extra->p = emalloc(sizeof(*p)); 531 532 if (**argv == '-') 533 (*argv)++; 534 else 535 p->exact = 1; 536 537 mask = umask(0); 538 umask(mask); 539 540 p->mode = parsemode(*argv, 0, mask); 541 542 return argv; 543 } 544 545 static char ** 546 get_type_arg(char *argv[], union extra *extra) 547 { 548 if (!strchr("bcdlpfs", **argv)) 549 eprintf("invalid type %c for -type primary\n", **argv); 550 551 extra->i = **argv; 552 return argv; 553 } 554 555 static char ** 556 get_n_arg(char *argv[], union extra *extra) 557 { 558 struct narg *n = extra->p = emalloc(sizeof(*n)); 559 fill_narg(*argv, n); 560 return argv; 561 } 562 563 static char ** 564 get_user_arg(char *argv[], union extra *extra) 565 { 566 char *end; 567 struct passwd *p = getpwnam(*argv); 568 569 if (p) { 570 extra->i = p->pw_uid; 571 } else { 572 extra->i = strtol(*argv, &end, 10); 573 if (end == *argv || *end) 574 eprintf("unknown user '%s'\n", *argv); 575 } 576 return argv; 577 } 578 579 static char ** 580 get_group_arg(char *argv[], union extra *extra) 581 { 582 char *end; 583 struct group *g = getgrnam(*argv); 584 585 if (g) { 586 extra->i = g->gr_gid; 587 } else { 588 extra->i = strtol(*argv, &end, 10); 589 if (end == *argv || *end) 590 eprintf("unknown group '%s'\n", *argv); 591 } 592 return argv; 593 } 594 595 static char ** 596 get_size_arg(char *argv[], union extra *extra) 597 { 598 char *p = *argv + strlen(*argv); 599 struct sizearg *s = extra->p = emalloc(sizeof(*s)); 600 /* if the number is followed by 'c', the size will by in bytes */ 601 if ((s->bytes = (p > *argv && *--p == 'c'))) 602 *p = '\0'; 603 604 fill_narg(*argv, &s->n); 605 return argv; 606 } 607 608 static char ** 609 get_exec_arg(char *argv[], union extra *extra) 610 { 611 char **arg, **new, ***braces; 612 int nbraces = 0; 613 struct execarg *e = extra->p = emalloc(sizeof(*e)); 614 615 for (arg = argv; *arg; arg++) 616 if (!strcmp(*arg, ";")) 617 break; 618 else if (arg > argv && !strcmp(*(arg - 1), "{}") && !strcmp(*arg, "+")) 619 break; 620 else if (!strcmp(*arg, "{}")) 621 nbraces++; 622 623 if (!*arg) 624 eprintf("no terminating ; or {} + for -exec primary\n"); 625 626 e->isplus = **arg == '+'; 627 *arg = NULL; 628 629 if (e->isplus) { 630 *(arg - 1) = NULL; /* don't need the {} in there now */ 631 e->u.p.arglen = e->u.p.filelen = 0; 632 e->u.p.first = e->u.p.next = arg - argv - 1; 633 e->u.p.cap = (arg - argv) * 2; 634 e->argv = ereallocarray(NULL, e->u.p.cap, sizeof(*e->argv)); 635 636 for (arg = argv, new = e->argv; *arg; arg++, new++) { 637 *new = *arg; 638 e->u.p.arglen += strlen(*arg) + 1 + sizeof(*arg); 639 } 640 arg++; /* due to our extra NULL */ 641 } else { 642 e->argv = argv; 643 e->u.s.braces = ereallocarray(NULL, ++nbraces, sizeof(*e->u.s.braces)); /* ++ for NULL */ 644 645 for (arg = argv, braces = e->u.s.braces; *arg; arg++) 646 if (!strcmp(*arg, "{}")) 647 *braces++ = arg; 648 *braces = NULL; 649 } 650 gflags.print = 0; 651 return arg; 652 } 653 654 static char ** 655 get_ok_arg(char *argv[], union extra *extra) 656 { 657 char **arg, ***braces; 658 int nbraces = 0; 659 struct okarg *o = extra->p = emalloc(sizeof(*o)); 660 661 for (arg = argv; *arg; arg++) 662 if (!strcmp(*arg, ";")) 663 break; 664 else if (!strcmp(*arg, "{}")) 665 nbraces++; 666 667 if (!*arg) 668 eprintf("no terminating ; for -ok primary\n"); 669 *arg = NULL; 670 671 o->argv = argv; 672 o->braces = ereallocarray(NULL, ++nbraces, sizeof(*o->braces)); 673 674 for (arg = argv, braces = o->braces; *arg; arg++) 675 if (!strcmp(*arg, "{}")) 676 *braces++ = arg; 677 *braces = NULL; 678 679 gflags.print = 0; 680 return arg; 681 } 682 683 static char ** 684 get_print_arg(char *argv[], union extra *extra) 685 { 686 gflags.print = 0; 687 return argv; 688 } 689 690 /* FIXME: ignoring nanoseconds */ 691 static char ** 692 get_newer_arg(char *argv[], union extra *extra) 693 { 694 struct stat st; 695 696 if (do_stat(*argv, &st, NULL)) 697 eprintf("failed to stat '%s':", *argv); 698 699 extra->i = st.st_mtime; 700 return argv; 701 } 702 703 static char ** 704 get_depth_arg(char *argv[], union extra *extra) 705 { 706 gflags.depth = 1; 707 return argv; 708 } 709 710 /* 711 * Freeargs 712 */ 713 static void 714 free_extra(union extra extra) 715 { 716 free(extra.p); 717 } 718 719 static void 720 free_exec_arg(union extra extra) 721 { 722 int status; 723 char **arg; 724 struct execarg *e = extra.p; 725 726 if (!e->isplus) { 727 free(e->u.s.braces); 728 } else { 729 e->argv[e->u.p.next] = NULL; 730 731 /* if we have files, do the last exec */ 732 if (e->u.p.first != e->u.p.next) { 733 status = spawn(e->argv); 734 gflags.ret = gflags.ret || status; 735 } 736 for (arg = e->argv + e->u.p.first; *arg; arg++) 737 free(*arg); 738 free(e->argv); 739 } 740 free(e); 741 } 742 743 static void 744 free_ok_arg(union extra extra) 745 { 746 struct okarg *o = extra.p; 747 748 free(o->braces); 749 free(o); 750 } 751 752 /* 753 * Parsing/Building/Running 754 */ 755 static void 756 fill_narg(char *s, struct narg *n) 757 { 758 char *end; 759 760 switch (*s) { 761 case '+': n->cmp = cmp_gt; s++; break; 762 case '-': n->cmp = cmp_lt; s++; break; 763 default : n->cmp = cmp_eq; break; 764 } 765 n->n = strtol(s, &end, 10); 766 if (end == s || *end) 767 eprintf("bad number '%s'\n", s); 768 } 769 770 static struct pri_info * 771 find_primary(char *name) 772 { 773 struct pri_info *p; 774 775 for (p = primaries; p->name; p++) 776 if (!strcmp(name, p->name)) 777 return p; 778 return NULL; 779 } 780 781 static struct op_info * 782 find_op(char *name) 783 { 784 struct op_info *o; 785 786 for (o = ops; o->name; o++) 787 if (!strcmp(name, o->name)) 788 return o; 789 return NULL; 790 } 791 792 /* given the expression from the command line 793 * 1) convert arguments from strings to tok and place in an array duplicating 794 * the infix expression given, inserting "-a" where it was omitted 795 * 2) allocate an array to hold the correct number of tok, and convert from 796 * infix to rpn (using shunting-yard), add -a and -print if necessary 797 * 3) evaluate the rpn filling in left and right pointers to create an 798 * expression tree (tok are still all contained in the rpn array, just 799 * pointing at eachother) 800 */ 801 static void 802 parse(int argc, char **argv) 803 { 804 struct tok *tok, *rpn, *out, **top, *infix, **stack; 805 struct op_info *op; 806 struct pri_info *pri; 807 char **arg; 808 int lasttype = -1; 809 size_t ntok = 0; 810 struct tok and = { .u.oinfo = find_op("-a"), .type = AND }; 811 812 gflags.print = 1; 813 814 /* convert argv to infix expression of tok, inserting in *tok */ 815 infix = ereallocarray(NULL, 2 * argc + 1, sizeof(*infix)); 816 for (arg = argv, tok = infix; *arg; arg++, tok++) { 817 pri = find_primary(*arg); 818 819 if (pri) { /* token is a primary, fill out tok and get arguments */ 820 if (lasttype == PRIM || lasttype == RPAR) { 821 *tok++ = and; 822 ntok++; 823 } 824 if (pri->getarg) { 825 if (pri->narg && !*++arg) 826 eprintf("no argument for primary %s\n", pri->name); 827 arg = pri->getarg(arg, &tok->extra); 828 } 829 tok->u.pinfo = pri; 830 tok->type = PRIM; 831 } else if ((op = find_op(*arg))) { /* token is an operator */ 832 if (lasttype == LPAR && op->type == RPAR) 833 eprintf("empty parens\n"); 834 if ((lasttype == PRIM || lasttype == RPAR) && 835 (op->type == NOT || op->type == LPAR)) { /* need another implicit -a */ 836 *tok++ = and; 837 ntok++; 838 } 839 tok->type = op->type; 840 tok->u.oinfo = op; 841 } else { 842 /* token is neither primary nor operator, must be */ 843 if ((*arg)[0] == '-') /* an unsupported option */ 844 eprintf("unknown operand: %s\n", *arg); 845 else /* or a path in the wrong place */ 846 eprintf("paths must precede expression: %s\n", *arg); 847 } 848 if (tok->type != LPAR && tok->type != RPAR) 849 ntok++; /* won't have parens in rpn */ 850 lasttype = tok->type; 851 } 852 tok->type = END; 853 ntok++; 854 855 if (gflags.print && (arg != argv)) /* need to add -a -print (not just -print) */ 856 gflags.print++; 857 858 /* use shunting-yard to convert from infix to rpn 859 * https://en.wikipedia.org/wiki/Shunting-yard_algorithm 860 * read from infix, resulting rpn ends up in rpn, next position in rpn is out 861 * push operators onto stack, next position in stack is top */ 862 rpn = ereallocarray(NULL, ntok + gflags.print, sizeof(*rpn)); 863 stack = ereallocarray(NULL, argc + gflags.print, sizeof(*stack)); 864 for (tok = infix, out = rpn, top = stack; tok->type != END; tok++) { 865 switch (tok->type) { 866 case PRIM: *out++ = *tok; break; 867 case LPAR: *top++ = tok; break; 868 case RPAR: 869 while (top-- > stack && (*top)->type != LPAR) 870 *out++ = **top; 871 if (top < stack) 872 eprintf("extra )\n"); 873 break; 874 default: 875 /* this expression can be simplified, but I decided copy the 876 * verbage from the wikipedia page in order to more clearly explain 877 * what's going on */ 878 while (top-- > stack && 879 (( tok->u.oinfo->lassoc && tok->u.oinfo->prec <= (*top)->u.oinfo->prec) || 880 (!tok->u.oinfo->lassoc && tok->u.oinfo->prec < (*top)->u.oinfo->prec))) 881 *out++ = **top; 882 883 /* top now points to either an operator we didn't pop, or stack[-1] 884 * either way we need to increment it before using it, then 885 * increment again so the stack works */ 886 top++; 887 *top++ = tok; 888 break; 889 } 890 } 891 while (top-- > stack) { 892 if ((*top)->type == LPAR) 893 eprintf("extra (\n"); 894 *out++ = **top; 895 } 896 897 /* if there was no expression, use -print 898 * if there was an expression but no -print, -exec, or -ok, add -a -print 899 * in rpn, not infix */ 900 if (gflags.print) 901 *out++ = (struct tok){ .u.pinfo = find_primary("-print"), .type = PRIM }; 902 if (gflags.print == 2) 903 *out++ = and; 904 905 out->type = END; 906 907 /* rpn now holds all operators and arguments in reverse polish notation 908 * values are pushed onto stack, operators pop values off stack into left 909 * and right pointers, pushing operator node back onto stack 910 * could probably just do this during shunting-yard, but this is simpler 911 * code IMO */ 912 for (tok = rpn, top = stack; tok->type != END; tok++) { 913 if (tok->type == PRIM) { 914 *top++ = tok; 915 } else { 916 if (top - stack < tok->u.oinfo->nargs) 917 eprintf("insufficient arguments for operator %s\n", tok->u.oinfo->name); 918 tok->right = *--top; 919 tok->left = tok->u.oinfo->nargs == 2 ? *--top : NULL; 920 *top++ = tok; 921 } 922 } 923 if (--top != stack) 924 eprintf("extra arguments\n"); 925 926 toks = rpn; 927 root = *top; 928 929 free(infix); 930 free(stack); 931 } 932 933 /* for a primary, run and return result 934 * for an operator evaluate the left side of the tree, decide whether or not to 935 * evaluate the right based on the short-circuit boolean logic, return result 936 * NOTE: operator NOT has NULL left side, expression on right side 937 */ 938 static int 939 eval(struct tok *tok, struct arg *arg) 940 { 941 int ret; 942 943 if (!tok) 944 return 0; 945 946 if (tok->type == PRIM) { 947 arg->extra = tok->extra; 948 return tok->u.pinfo->func(arg); 949 } 950 951 ret = eval(tok->left, arg); 952 953 if ((tok->type == AND && ret) || (tok->type == OR && !ret) || tok->type == NOT) 954 ret = eval(tok->right, arg); 955 956 return ret ^ (tok->type == NOT); 957 } 958 959 /* evaluate path, if it's a directory iterate through directory entries and 960 * recurse 961 */ 962 static void 963 find(char *path, struct findhist *hist) 964 { 965 struct stat st; 966 DIR *dir; 967 struct dirent *de; 968 struct findhist *f, cur; 969 size_t namelen, pathcap = 0, len; 970 struct arg arg = { path, &st, { NULL } }; 971 char *p, *pathbuf = NULL; 972 973 len = strlen(path) + 2; /* \0 and '/' */ 974 975 if (do_stat(path, &st, hist) < 0) { 976 weprintf("failed to stat %s:", path); 977 gflags.ret = 1; 978 return; 979 } 980 981 gflags.prune = 0; 982 983 /* don't eval now iff we will hit the eval at the bottom which means 984 * 1. we are a directory 2. we have -depth 3. we don't have -xdev or we are 985 * on same device (so most of the time we eval here) */ 986 if (!S_ISDIR(st.st_mode) || 987 !gflags.depth || 988 (gflags.xdev && hist && st.st_dev != hist->dev)) 989 eval(root, &arg); 990 991 if (!S_ISDIR(st.st_mode) || 992 gflags.prune || 993 (gflags.xdev && hist && st.st_dev != hist->dev)) 994 return; 995 996 for (f = hist; f; f = f->next) { 997 if (f->dev == st.st_dev && f->ino == st.st_ino) { 998 weprintf("loop detected '%s' is '%s'\n", path, f->path); 999 gflags.ret = 1; 1000 return; 1001 } 1002 } 1003 cur.next = hist; 1004 cur.path = path; 1005 cur.dev = st.st_dev; 1006 cur.ino = st.st_ino; 1007 1008 if (!(dir = opendir(path))) { 1009 weprintf("failed to opendir %s:", path); 1010 gflags.ret = 1; 1011 /* should we just ignore this since we hit an error? */ 1012 if (gflags.depth) 1013 eval(root, &arg); 1014 return; 1015 } 1016 1017 while (errno = 0, (de = readdir(dir))) { 1018 if (!strcmp(de->d_name, ".") || !strcmp(de->d_name, "..")) 1019 continue; 1020 namelen = strlen(de->d_name); 1021 if (len + namelen > pathcap) { 1022 pathcap = len + namelen; 1023 pathbuf = erealloc(pathbuf, pathcap); 1024 } 1025 p = pathbuf + estrlcpy(pathbuf, path, pathcap); 1026 if (*--p != '/') 1027 estrlcat(pathbuf, "/", pathcap); 1028 estrlcat(pathbuf, de->d_name, pathcap); 1029 find(pathbuf, &cur); 1030 } 1031 free(pathbuf); 1032 if (errno) { 1033 weprintf("readdir %s:", path); 1034 gflags.ret = 1; 1035 closedir(dir); 1036 return; 1037 } 1038 closedir(dir); 1039 1040 if (gflags.depth) 1041 eval(root, &arg); 1042 } 1043 1044 static void 1045 usage(void) 1046 { 1047 eprintf("usage: %s [-H | -L] path ... [expression ...]\n", argv0); 1048 } 1049 1050 int 1051 main(int argc, char **argv) 1052 { 1053 char **paths; 1054 int npaths; 1055 struct tok *t; 1056 1057 ARGBEGIN { 1058 case 'H': 1059 gflags.h = 1; 1060 gflags.l = 0; 1061 break; 1062 case 'L': 1063 gflags.l = 1; 1064 gflags.h = 0; 1065 break; 1066 default: 1067 usage(); 1068 } ARGEND 1069 1070 paths = argv; 1071 1072 for (; *argv && **argv != '-' && strcmp(*argv, "!") && strcmp(*argv, "("); argv++) 1073 ; 1074 1075 if (!(npaths = argv - paths)) 1076 eprintf("must specify a path\n"); 1077 1078 parse(argc - npaths, argv); 1079 1080 /* calculate number of bytes in environ for -exec {} + ARG_MAX avoidance 1081 * libc implementation defined whether null bytes, pointers, and alignment 1082 * are counted, so count them */ 1083 for (argv = environ; *argv; argv++) 1084 envlen += strlen(*argv) + 1 + sizeof(*argv); 1085 1086 if ((argmax = sysconf(_SC_ARG_MAX)) == (size_t)-1) 1087 argmax = _POSIX_ARG_MAX; 1088 1089 if (clock_gettime(CLOCK_REALTIME, &start) < 0) 1090 weprintf("clock_gettime() failed:"); 1091 1092 while (npaths--) 1093 find(*paths++, NULL); 1094 1095 for (t = toks; t->type != END; t++) 1096 if (t->type == PRIM && t->u.pinfo->freearg) 1097 t->u.pinfo->freearg(t->extra); 1098 free(toks); 1099 1100 gflags.ret |= fshut(stdin, "<stdin>") | fshut(stdout, "<stdout>"); 1101 1102 return gflags.ret; 1103 }