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