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