1/* See LICENSE file for copyright and license details. */
2
3#include "config.h"
4#include "util.h"
5#include "wexec.h"
6
7#include <dirent.h>
8#include <errno.h>
9#include <fnmatch.h>
10#include <grp.h>
11#include <libgen.h>
12#include <pwd.h>
13#include <regex.h>
14#include <stdint.h>
15#include <stdio.h>
16#include <stdlib.h>
17#include <string.h>
18#include <sys/stat.h>
19#include <sys/wait.h>
20#include <time.h>
21#include <unistd.h>
22
23/* because putting integers in pointers is undefined by the standard */
24union extra {
25 void *p;
26 intmax_t i;
27};
28
29/* Argument passed into a primary's function */
30struct arg {
31 char *path;
32 struct stat *st;
33 union extra extra;
34};
35
36/* Information about each primary, for lookup table */
37struct pri_info {
38 char *name;
39 int (*func)(struct arg *arg);
40 char **(*getarg)(char **argv, union extra *extra);
41 void (*freearg)(union extra extra);
42 char narg; /* -xdev, -depth, -print don't take args but have getarg() */
43};
44
45/* Information about operators, for lookup table */
46struct op_info {
47 char *name; /* string representation of op */
48 char type; /* from tok.type */
49 char prec; /* precedence */
50 char nargs; /* number of arguments (unary or binary) */
51 char lassoc; /* left associative */
52};
53
54/* Token when lexing/parsing
55 * (although also used for the expression tree) */
56struct tok {
57 struct tok *left, *right; /* if (type == NOT) left = NULL */
58 union extra extra;
59 union {
60 struct pri_info *pinfo; /* if (type == PRIM) */
61 struct op_info *oinfo;
62 } u;
63 enum { PRIM = 0, LPAR, RPAR, NOT, AND, OR, END } type;
64};
65
66/* structures used for arg.extra.p and tok.extra.p */
67struct permarg {
68 mode_t mode;
69 char exact;
70};
71
72struct okarg {
73 char ***braces;
74 char **argv;
75};
76
77/* for all arguments that take a number
78 * +n, n, -n mean > n, == n, < n respectively */
79struct narg {
80 int (*cmp)(int a, int b);
81 int n;
82};
83
84struct sizearg {
85 struct narg n;
86 char bytes; /* size is in bytes, not 512 byte sectors */
87};
88
89struct execarg {
90 union {
91 struct {
92 char ***braces; /* NULL terminated list of pointers into
93 argv where {} were */
94 } s; /* semicolon */
95 struct {
96 size_t arglen; /* number of bytes in argv before files
97 are added */
98 size_t filelen; /* numer of bytes in file names added to
99 argv */
100 size_t first; /* index one past last arg, where first
101 file goes */
102 size_t next; /* index where next file goes */
103 size_t cap; /* capacity of argv */
104 } p; /* plus */
105 } u;
106 char **argv; /* NULL terminated list of arguments (allocated if isplus)
107 */
108 char isplus; /* -exec + instead of -exec ; */
109};
110
111/* used to find loops while recursing through directory structure */
112struct findhist {
113 struct findhist *next;
114 char *path;
115 dev_t dev;
116 ino_t ino;
117};
118
119/* Utility */
120static int spawn(char *argv[]);
121static int do_stat(char *path, struct stat *sb, struct findhist *hist);
122
123/* Primaries */
124static int pri_name(struct arg *arg);
125#if FEATURE_FIND_INAME
126static int pri_iname(struct arg *arg);
127#endif
128#if FEATURE_FIND_IPATH
129static int pri_ipath(struct arg *arg);
130#endif
131#if FEATURE_FIND_REGEX
132static int pri_regex(struct arg *arg);
133static char **get_regex_arg(char *argv[], union extra *extra);
134static void free_regex_arg(union extra extra);
135#endif
136#if FEATURE_FIND_INUM
137static int pri_inum(struct arg *arg);
138static char **get_inum_arg(char *argv[], union extra *extra);
139#endif
140#if FEATURE_FIND_SAMEFILE
141static int pri_samefile(struct arg *arg);
142static char **get_samefile_arg(char *argv[], union extra *extra);
143#endif
144#if FEATURE_FIND_MAXDEPTH
145static int pri_maxdepth(struct arg *arg);
146static char **get_maxdepth_arg(char *argv[], union extra *extra);
147#endif
148#if FEATURE_FIND_MINDEPTH
149static int pri_mindepth(struct arg *arg);
150static char **get_mindepth_arg(char *argv[], union extra *extra);
151#endif
152#if FEATURE_FIND_DELETE
153static int pri_delete(struct arg *arg);
154static char **get_delete_arg(char *argv[], union extra *extra);
155#endif
156#if FEATURE_FIND_QUIT
157static int pri_quit(struct arg *arg);
158static char **get_quit_arg(char *argv[], union extra *extra);
159#endif
160#if FEATURE_FIND_EMPTY
161static int pri_empty(struct arg *arg);
162#endif
163#if FEATURE_FIND_MMIN
164static int pri_mmin(struct arg *arg);
165#endif
166#if FEATURE_FIND_AMIN
167static int pri_amin(struct arg *arg);
168#endif
169#if FEATURE_FIND_CMIN
170static int pri_cmin(struct arg *arg);
171#endif
172static int pri_path(struct arg *arg);
173static int pri_nouser(struct arg *arg);
174static int pri_nogroup(struct arg *arg);
175static int pri_xdev(struct arg *arg);
176static int pri_prune(struct arg *arg);
177static int pri_perm(struct arg *arg);
178static int pri_type(struct arg *arg);
179static int pri_links(struct arg *arg);
180static int pri_user(struct arg *arg);
181static int pri_group(struct arg *arg);
182static int pri_size(struct arg *arg);
183static int pri_atime(struct arg *arg);
184static int pri_ctime(struct arg *arg);
185static int pri_mtime(struct arg *arg);
186static int pri_exec(struct arg *arg);
187static int pri_ok(struct arg *arg);
188static int pri_print(struct arg *arg);
189#if FEATURE_FIND_PRINT0
190static int pri_print0(struct arg *arg);
191#endif
192static int pri_newer(struct arg *arg);
193static int pri_depth(struct arg *arg);
194
195/* Getargs */
196static char **get_name_arg(char *argv[], union extra *extra);
197static char **get_path_arg(char *argv[], union extra *extra);
198static char **get_xdev_arg(char *argv[], union extra *extra);
199static char **get_perm_arg(char *argv[], union extra *extra);
200static char **get_type_arg(char *argv[], union extra *extra);
201static char **get_n_arg(char *argv[], union extra *extra);
202static char **get_user_arg(char *argv[], union extra *extra);
203static char **get_group_arg(char *argv[], union extra *extra);
204static char **get_size_arg(char *argv[], union extra *extra);
205static char **get_exec_arg(char *argv[], union extra *extra);
206static char **get_ok_arg(char *argv[], union extra *extra);
207static char **get_print_arg(char *argv[], union extra *extra);
208static char **get_newer_arg(char *argv[], union extra *extra);
209static char **get_depth_arg(char *argv[], union extra *extra);
210
211/* Freeargs */
212static void free_extra(union extra extra);
213static void free_exec_arg(union extra extra);
214static void free_ok_arg(union extra extra);
215
216/* Parsing/Building/Running */
217static void fill_narg(char *s, struct narg *n);
218static struct pri_info *find_primary(char *name);
219static struct op_info *find_op(char *name);
220static void parse(int argc, char **argv);
221static int eval(struct tok *tok, struct arg *arg);
222static void find(char *path, struct findhist *hist);
223static void usage(void);
224
225/* for comparisons with narg */
226static int
227cmp_gt(int a, int b)
228{
229 return a > b;
230}
231static int
232cmp_eq(int a, int b)
233{
234 return a == b;
235}
236static int
237cmp_lt(int a, int b)
238{
239 return a < b;
240}
241
242/* order from find(1p), may want to alphabetize */
243static struct pri_info primaries[] = {
244#if FEATURE_FIND_INAME
245 {"-iname", pri_iname, get_name_arg, NULL, 1},
246#endif
247#if FEATURE_FIND_IPATH
248 {"-ipath", pri_ipath, get_path_arg, NULL, 1},
249#endif
250#if FEATURE_FIND_REGEX
251 {"-regex", pri_regex, get_regex_arg, free_regex_arg, 1},
252#endif
253#if FEATURE_FIND_INUM
254 {"-inum", pri_inum, get_inum_arg, NULL, 1},
255#endif
256#if FEATURE_FIND_SAMEFILE
257 {"-samefile", pri_samefile, get_samefile_arg, free_extra, 1},
258#endif
259#if FEATURE_FIND_MAXDEPTH
260 {"-maxdepth", pri_maxdepth, get_maxdepth_arg, NULL, 1},
261#endif
262#if FEATURE_FIND_MINDEPTH
263 {"-mindepth", pri_mindepth, get_mindepth_arg, NULL, 1},
264#endif
265#if FEATURE_FIND_DELETE
266 {"-delete", pri_delete, get_delete_arg, NULL, 0},
267#endif
268#if FEATURE_FIND_QUIT
269 {"-quit", pri_quit, get_quit_arg, NULL, 0},
270#endif
271#if FEATURE_FIND_MMIN
272 {"-mmin", pri_mmin, get_n_arg, free_extra, 1},
273#endif
274#if FEATURE_FIND_AMIN
275 {"-amin", pri_amin, get_n_arg, free_extra, 1},
276#endif
277#if FEATURE_FIND_CMIN
278 {"-cmin", pri_cmin, get_n_arg, free_extra, 1},
279#endif
280#if FEATURE_FIND_EMPTY
281 {"-empty", pri_empty, NULL, NULL, 1},
282#endif
283 {"-name", pri_name, get_name_arg, NULL, 1},
284 {"-path", pri_path, get_path_arg, NULL, 1},
285 {"-nouser", pri_nouser, NULL, NULL, 1},
286 {"-nogroup", pri_nogroup, NULL, NULL, 1},
287 {"-xdev", pri_xdev, get_xdev_arg, NULL, 0},
288 {"-prune", pri_prune, NULL, NULL, 1},
289 {"-perm", pri_perm, get_perm_arg, free_extra, 1},
290 {"-type", pri_type, get_type_arg, NULL, 1},
291 {"-links", pri_links, get_n_arg, free_extra, 1},
292 {"-user", pri_user, get_user_arg, NULL, 1},
293 {"-group", pri_group, get_group_arg, NULL, 1},
294 {"-size", pri_size, get_size_arg, free_extra, 1},
295 {"-atime", pri_atime, get_n_arg, free_extra, 1},
296 {"-ctime", pri_ctime, get_n_arg, free_extra, 1},
297 {"-mtime", pri_mtime, get_n_arg, free_extra, 1},
298 {"-exec", pri_exec, get_exec_arg, free_exec_arg, 1},
299 {"-ok", pri_ok, get_ok_arg, free_ok_arg, 1},
300 {"-print", pri_print, get_print_arg, NULL, 0},
301#if FEATURE_FIND_PRINT0
302 {"-print0", pri_print0, get_print_arg, NULL, 0},
303#endif
304 {"-newer", pri_newer, get_newer_arg, NULL, 1},
305 {"-depth", pri_depth, get_depth_arg, NULL, 0},
306
307 {NULL, NULL, NULL, NULL, 0}
308};
309
310static struct op_info ops[] = {
311 {"(", LPAR, 0, 0, 0}, /* parens are handled specially */
312 {")", RPAR, 0, 0, 0},
313 {"!", NOT, 3, 1, 0},
314 {"-a", AND, 2, 2, 1},
315 {"-o", OR, 1, 2, 1},
316
317 {NULL, 0, 0, 0, 0}
318};
319
320extern char **environ;
321
322static struct tok *toks; /* holds allocated array of all toks created while parsing */
323static struct tok *root; /* points to root of expression tree, inside toks array */
324
325static struct timespec start; /* time find was started, used for -[acm]time */
326
327static size_t envlen; /* number of bytes in environ, used to calculate against
328 ARG_MAX */
329static size_t argmax; /* value of ARG_MAX retrieved using sysconf(3p) */
330
331static struct {
332 char ret; /* return value from main */
333 char depth; /* -depth, directory contents before directory itself */
334 char h; /* -H, follow symlinks on command line */
335 char l; /* -L, follow all symlinks (command line and search) */
336 char prune; /* hit -prune */
337 char xdev; /* -xdev, prune directories on different devices */
338 char print; /* whether we will need -print when parsing */
339 char quit; /* quit execution immediately */
340 long maxdepth; /* max depth of recursion */
341 long mindepth; /* min depth of recursion */
342} gflags;
343
344/*
345 * Utility
346 */
347static int
348spawn(char *argv[])
349{
350 pid_t pid;
351 int status;
352
353 /* flush stdout so that -print output always appears before
354 * any output from the command and does not get cut-off in
355 * the middle of a line. */
356 fflush(stdout);
357
358 switch ((pid = fork())) {
359 case -1:
360 eprintf("fork:");
361 break;
362 case 0:
363 wexecvp_self(*argv, argv);
364 weprintf("exec %s failed:", *argv);
365 _exit(1);
366 }
367
368 while (waitpid(pid, &status, 0) < 0) {
369 if (errno != EINTR) {
370 status = -1;
371 break;
372 }
373 }
374 return status;
375}
376
377static int
378do_stat(char *path, struct stat *sb, struct findhist *hist)
379{
380 if (gflags.l || (gflags.h && !hist)) {
381 if (stat(path, sb) == 0) {
382 return 0;
383 } else if (errno != ENOENT && errno != ENOTDIR) {
384 return -1;
385 }
386 }
387
388 return lstat(path, sb);
389}
390
391/*
392 * Primaries
393 */
394static int
395pri_name(struct arg *arg)
396{
397 int ret;
398 char *path;
399
400 path = estrdup(arg->path);
401 ret = !fnmatch((char *)arg->extra.p, basename(path), 0);
402 free(path);
403
404 return ret;
405}
406
407static int
408pri_path(struct arg *arg)
409{
410 return !fnmatch((char *)arg->extra.p, arg->path, 0);
411}
412
413/* FIXME: what about errors? find(1p) literally just says
414 * "for which the getpwuid() function ... returns NULL" */
415static int
416pri_nouser(struct arg *arg)
417{
418 return !getpwuid(arg->st->st_uid);
419}
420
421static int
422pri_nogroup(struct arg *arg)
423{
424 return !getgrgid(arg->st->st_gid);
425}
426
427static int
428pri_xdev(struct arg *arg)
429{
430 (void)arg;
431 return 1;
432}
433
434static int
435pri_prune(struct arg *arg)
436{
437 (void)arg;
438 return gflags.prune = 1;
439}
440
441static int
442pri_perm(struct arg *arg)
443{
444 struct permarg *p = (struct permarg *)arg->extra.p;
445
446 return (arg->st->st_mode & 07777 & (p->exact ? -1U : p->mode)) == p->mode;
447}
448
449static int
450pri_type(struct arg *arg)
451{
452 switch ((char)arg->extra.i) {
453 default:
454 return 0; /* impossible, but placate warnings */
455 case 'b':
456 return S_ISBLK(arg->st->st_mode);
457 case 'c':
458 return S_ISCHR(arg->st->st_mode);
459 case 'd':
460 return S_ISDIR(arg->st->st_mode);
461 case 'l':
462 return S_ISLNK(arg->st->st_mode);
463 case 'p':
464 return S_ISFIFO(arg->st->st_mode);
465 case 'f':
466 return S_ISREG(arg->st->st_mode);
467 case 's':
468 return S_ISSOCK(arg->st->st_mode);
469 }
470}
471
472static int
473pri_links(struct arg *arg)
474{
475 struct narg *n = arg->extra.p;
476 return n->cmp(arg->st->st_nlink, n->n);
477}
478
479static int
480pri_user(struct arg *arg)
481{
482 return arg->st->st_uid == (uid_t)arg->extra.i;
483}
484
485static int
486pri_group(struct arg *arg)
487{
488 return arg->st->st_gid == (gid_t)arg->extra.i;
489}
490
491static int
492pri_size(struct arg *arg)
493{
494 struct sizearg *s = arg->extra.p;
495 off_t size = arg->st->st_size;
496
497 if (!s->bytes)
498 size = size / 512 + !!(size % 512);
499
500 return s->n.cmp(size, s->n.n);
501}
502
503/* FIXME: ignoring nanoseconds in atime, ctime, mtime */
504static int
505pri_atime(struct arg *arg)
506{
507 struct narg *n = arg->extra.p;
508 return n->cmp((start.tv_sec - arg->st->st_atime) / 86400, n->n);
509}
510
511static int
512pri_ctime(struct arg *arg)
513{
514 struct narg *n = arg->extra.p;
515 return n->cmp((start.tv_sec - arg->st->st_ctime) / 86400, n->n);
516}
517
518static int
519pri_mtime(struct arg *arg)
520{
521 struct narg *n = arg->extra.p;
522 return n->cmp((start.tv_sec - arg->st->st_mtime) / 86400, n->n);
523}
524
525static int
526pri_exec(struct arg *arg)
527{
528 int status;
529 size_t len;
530 char **sp, ***brace;
531 struct execarg *e = arg->extra.p;
532
533 if (e->isplus) {
534 len = strlen(arg->path) + 1;
535
536 /* if we reached ARG_MAX, fork, exec, wait, free file names,
537 * reset list */
538 if (len + e->u.p.arglen + e->u.p.filelen + envlen > argmax) {
539 e->argv[e->u.p.next] = NULL;
540
541 status = spawn(e->argv);
542 gflags.ret = gflags.ret || status;
543
544 for (sp = e->argv + e->u.p.first; *sp; sp++)
545 free(*sp);
546
547 e->u.p.next = e->u.p.first;
548 e->u.p.filelen = 0;
549 }
550
551 /* if we have too many files, realloc (with space for NULL
552 * termination) */
553 if (e->u.p.next + 1 == e->u.p.cap)
554 e->argv = ereallocarray(e->argv, e->u.p.cap *= 2, sizeof(*e->argv));
555
556 e->argv[e->u.p.next++] = estrdup(arg->path);
557 e->u.p.filelen += len + sizeof(arg->path);
558
559 return 1;
560 } else {
561 /* insert path everywhere user gave us {} */
562 for (brace = e->u.s.braces; *brace; brace++)
563 **brace = arg->path;
564
565 status = spawn(e->argv);
566 return !status;
567 }
568}
569
570static int
571pri_ok(struct arg *arg)
572{
573 int status, reply;
574 char ***brace, c;
575 struct okarg *o = arg->extra.p;
576
577 fprintf(stderr, "%s: %s ? ", *o->argv, arg->path);
578 reply = fgetc(stdin);
579
580 /* throw away rest of line */
581 while ((c = fgetc(stdin)) != '\n' && c != EOF)
582 /* FIXME: what if the first character of the rest of the line is
583 * a null byte? */
584 ;
585
586 if (feof(stdin) || ferror(stdin))
587 clearerr(stdin);
588
589 if (reply != 'y' && reply != 'Y')
590 return 0;
591
592 /* insert filename everywhere user gave us {} */
593 for (brace = o->braces; *brace; brace++)
594 **brace = arg->path;
595
596 status = spawn(o->argv);
597 return !!status;
598}
599
600static int
601pri_print(struct arg *arg)
602{
603 if (puts(arg->path) == EOF)
604 eprintf("puts failed:");
605 return 1;
606}
607
608#if FEATURE_FIND_PRINT0
609static int
610pri_print0(struct arg *arg)
611{
612 if (fwrite(arg->path, strlen(arg->path) + 1, 1, stdout) != 1)
613 eprintf("fwrite failed:");
614 return 1;
615}
616#endif
617
618/* FIXME: ignoring nanoseconds */
619static int
620pri_newer(struct arg *arg)
621{
622 return arg->st->st_mtime > (time_t)arg->extra.i;
623}
624
625static int
626pri_depth(struct arg *arg)
627{
628 (void)arg;
629 return 1;
630}
631
632/*
633 * Getargs
634 * consume any arguments for given primary and fill extra
635 * return pointer to last argument, the pointer will be incremented in parse()
636 */
637static char **
638get_name_arg(char *argv[], union extra *extra)
639{
640 extra->p = *argv;
641 return argv;
642}
643
644static char **
645get_path_arg(char *argv[], union extra *extra)
646{
647 extra->p = *argv;
648 return argv;
649}
650
651static char **
652get_xdev_arg(char *argv[], union extra *extra)
653{
654 (void)extra;
655 gflags.xdev = 1;
656 return argv;
657}
658
659static char **
660get_perm_arg(char *argv[], union extra *extra)
661{
662 mode_t mask;
663 struct permarg *p = extra->p = emalloc(sizeof(*p));
664
665 if (**argv == '-')
666 (*argv)++;
667 else
668 p->exact = 1;
669
670 mask = umask(0);
671 umask(mask);
672
673 p->mode = parsemode(*argv, 0, mask);
674
675 return argv;
676}
677
678static char **
679get_type_arg(char *argv[], union extra *extra)
680{
681 if (!strchr("bcdlpfs", **argv))
682 eprintf("invalid type %c for -type primary\n", **argv);
683
684 extra->i = **argv;
685 return argv;
686}
687
688static char **
689get_n_arg(char *argv[], union extra *extra)
690{
691 struct narg *n = extra->p = emalloc(sizeof(*n));
692 fill_narg(*argv, n);
693 return argv;
694}
695
696static char **
697get_user_arg(char *argv[], union extra *extra)
698{
699 char *end;
700 struct passwd *p = getpwnam(*argv);
701
702 if (p) {
703 extra->i = p->pw_uid;
704 } else {
705 extra->i = strtol(*argv, &end, 10);
706 if (end == *argv || *end)
707 eprintf("unknown user '%s'\n", *argv);
708 }
709 return argv;
710}
711
712static char **
713get_group_arg(char *argv[], union extra *extra)
714{
715 char *end;
716 struct group *g = getgrnam(*argv);
717
718 if (g) {
719 extra->i = g->gr_gid;
720 } else {
721 extra->i = strtol(*argv, &end, 10);
722 if (end == *argv || *end)
723 eprintf("unknown group '%s'\n", *argv);
724 }
725 return argv;
726}
727
728static char **
729get_size_arg(char *argv[], union extra *extra)
730{
731 char *p = *argv + strlen(*argv);
732 struct sizearg *s = extra->p = emalloc(sizeof(*s));
733 /* if the number is followed by 'c', the size will by in bytes */
734 if ((s->bytes = (p > *argv && *--p == 'c')))
735 *p = '\0';
736
737 fill_narg(*argv, &s->n);
738 return argv;
739}
740
741static char **
742get_exec_arg(char *argv[], union extra *extra)
743{
744 char **arg, **new, ***braces;
745 int nbraces = 0;
746 struct execarg *e = extra->p = emalloc(sizeof(*e));
747
748 for (arg = argv; *arg; arg++)
749 if (!strcmp(*arg, ";"))
750 break;
751 else if (arg > argv && !strcmp(*(arg - 1), "{}") && !strcmp(*arg, "+"))
752 break;
753 else if (!strcmp(*arg, "{}"))
754 nbraces++;
755
756 if (!*arg)
757 eprintf("no terminating ; or {} + for -exec primary\n");
758
759 e->isplus = **arg == '+';
760 *arg = NULL;
761
762 if (e->isplus) {
763 *(arg - 1) = NULL; /* don't need the {} in there now */
764 e->u.p.arglen = e->u.p.filelen = 0;
765 e->u.p.first = e->u.p.next = arg - argv - 1;
766 e->u.p.cap = (arg - argv) * 2;
767 e->argv = ereallocarray(NULL, e->u.p.cap, sizeof(*e->argv));
768
769 for (arg = argv, new = e->argv; *arg; arg++, new ++) {
770 *new = *arg;
771 e->u.p.arglen += strlen(*arg) + 1 + sizeof(*arg);
772 }
773 arg++; /* due to our extra NULL */
774 } else {
775 e->argv = argv;
776 e->u.s.braces = ereallocarray(NULL, ++nbraces, sizeof(*e->u.s.braces)); /* ++ for NULL */
777
778 for (arg = argv, braces = e->u.s.braces; *arg; arg++)
779 if (!strcmp(*arg, "{}"))
780 *braces++ = arg;
781 *braces = NULL;
782 }
783 gflags.print = 0;
784 return arg;
785}
786
787static char **
788get_ok_arg(char *argv[], union extra *extra)
789{
790 char **arg, ***braces;
791 int nbraces = 0;
792 struct okarg *o = extra->p = emalloc(sizeof(*o));
793
794 for (arg = argv; *arg; arg++)
795 if (!strcmp(*arg, ";"))
796 break;
797 else if (!strcmp(*arg, "{}"))
798 nbraces++;
799
800 if (!*arg)
801 eprintf("no terminating ; for -ok primary\n");
802 *arg = NULL;
803
804 o->argv = argv;
805 o->braces = ereallocarray(NULL, ++nbraces, sizeof(*o->braces));
806
807 for (arg = argv, braces = o->braces; *arg; arg++)
808 if (!strcmp(*arg, "{}"))
809 *braces++ = arg;
810 *braces = NULL;
811
812 gflags.print = 0;
813 return arg;
814}
815
816static char **
817get_print_arg(char *argv[], union extra *extra)
818{
819 (void)extra;
820 gflags.print = 0;
821 return argv;
822}
823
824/* FIXME: ignoring nanoseconds */
825static char **
826get_newer_arg(char *argv[], union extra *extra)
827{
828 struct stat st;
829
830 if (do_stat(*argv, &st, NULL))
831 eprintf("failed to stat '%s':", *argv);
832
833 extra->i = st.st_mtime;
834 return argv;
835}
836
837static char **
838get_depth_arg(char *argv[], union extra *extra)
839{
840 (void)extra;
841 gflags.depth = 1;
842 return argv;
843}
844
845/*
846 * Freeargs
847 */
848static void
849free_extra(union extra extra)
850{
851 free(extra.p);
852}
853
854static void
855free_exec_arg(union extra extra)
856{
857 int status;
858 char **arg;
859 struct execarg *e = extra.p;
860
861 if (!e->isplus) {
862 free(e->u.s.braces);
863 } else {
864 e->argv[e->u.p.next] = NULL;
865
866 /* if we have files, do the last exec */
867 if (e->u.p.first != e->u.p.next) {
868 status = spawn(e->argv);
869 gflags.ret = gflags.ret || status;
870 }
871 for (arg = e->argv + e->u.p.first; *arg; arg++)
872 free(*arg);
873 free(e->argv);
874 }
875 free(e);
876}
877
878static void
879free_ok_arg(union extra extra)
880{
881 struct okarg *o = extra.p;
882
883 free(o->braces);
884 free(o);
885}
886
887/*
888 * Parsing/Building/Running
889 */
890static void
891fill_narg(char *s, struct narg *n)
892{
893 char *end;
894
895 switch (*s) {
896 case '+':
897 n->cmp = cmp_gt;
898 s++;
899 break;
900 case '-':
901 n->cmp = cmp_lt;
902 s++;
903 break;
904 default:
905 n->cmp = cmp_eq;
906 break;
907 }
908 n->n = strtol(s, &end, 10);
909 if (end == s || *end)
910 eprintf("bad number '%s'\n", s);
911}
912
913static struct pri_info *
914find_primary(char *name)
915{
916 struct pri_info *p;
917
918 for (p = primaries; p->name; p++)
919 if (!strcmp(name, p->name))
920 return p;
921 return NULL;
922}
923
924static struct op_info *
925find_op(char *name)
926{
927 struct op_info *o;
928
929 for (o = ops; o->name; o++)
930 if (!strcmp(name, o->name))
931 return o;
932 return NULL;
933}
934
935/* given the expression from the command line
936 * 1) convert arguments from strings to tok and place in an array duplicating
937 * the infix expression given, inserting "-a" where it was omitted
938 * 2) allocate an array to hold the correct number of tok, and convert from
939 * infix to rpn (using shunting-yard), add -a and -print if necessary
940 * 3) evaluate the rpn filling in left and right pointers to create an
941 * expression tree (tok are still all contained in the rpn array, just
942 * pointing at eachother)
943 */
944static void
945parse(int argc, char **argv)
946{
947 struct tok *tok, *rpn, *out, **top, *infix, **stack;
948 struct op_info *op;
949 struct pri_info *pri;
950 char **arg;
951 int lasttype = -1;
952 size_t ntok = 0;
953 struct tok and = {.u.oinfo = find_op("-a"), .type = AND};
954
955 gflags.print = 1;
956
957 /* convert argv to infix expression of tok, inserting in *tok */
958 infix = ereallocarray(NULL, 2 * argc + 1, sizeof(*infix));
959 for (arg = argv, tok = infix; *arg; arg++, tok++) {
960 pri = find_primary(*arg);
961
962 if (pri) { /* token is a primary, fill out tok and get arguments
963 */
964 if (lasttype == PRIM || lasttype == RPAR) {
965 *tok++ = and;
966 ntok++;
967 }
968 if (pri->getarg) {
969 if (pri->narg && !*++arg)
970 eprintf("no argument for primary %s\n", pri->name);
971 arg = pri->getarg(arg, &tok->extra);
972 }
973 tok->u.pinfo = pri;
974 tok->type = PRIM;
975 } else if ((op = find_op(*arg))) { /* token is an operator */
976 if (lasttype == LPAR && op->type == RPAR)
977 eprintf("empty parens\n");
978 if ((lasttype == PRIM || lasttype == RPAR)
979 && (op->type == NOT || op->type == LPAR)) { /* need another implicit -a */
980 *tok++ = and;
981 ntok++;
982 }
983 tok->type = op->type;
984 tok->u.oinfo = op;
985 } else {
986 /* token is neither primary nor operator, must be */
987 if ((*arg)[0] == '-') /* an unsupported option */
988 eprintf("unknown operand: %s\n", *arg);
989 else /* or a path in the wrong place */
990 eprintf("paths must precede expression: %s\n", *arg);
991 }
992 if (tok->type != LPAR && tok->type != RPAR)
993 ntok++; /* won't have parens in rpn */
994 lasttype = tok->type;
995 }
996 tok->type = END;
997 ntok++;
998
999 if (gflags.print && (arg != argv)) /* need to add -a -print (not just -print) */
1000 gflags.print++;
1001
1002 /* use shunting-yard to convert from infix to rpn
1003 * https://en.wikipedia.org/wiki/Shunting-yard_algorithm
1004 * read from infix, resulting rpn ends up in rpn, next position in rpn
1005 * is out push operators onto stack, next position in stack is top */
1006 rpn = ereallocarray(NULL, ntok + gflags.print, sizeof(*rpn));
1007 stack = ereallocarray(NULL, argc + gflags.print, sizeof(*stack));
1008 for (tok = infix, out = rpn, top = stack; tok->type != END; tok++) {
1009 switch (tok->type) {
1010 case PRIM:
1011 *out++ = *tok;
1012 break;
1013 case LPAR:
1014 *top++ = tok;
1015 break;
1016 case RPAR:
1017 while (top-- > stack && (*top)->type != LPAR)
1018 *out++ = **top;
1019 if (top < stack)
1020 eprintf("extra )\n");
1021 break;
1022 default:
1023 /* this expression can be simplified, but I decided copy
1024 * the verbage from the wikipedia page in order to more
1025 * clearly explain what's going on */
1026 while (top-- > stack
1027 && ((tok->u.oinfo->lassoc && tok->u.oinfo->prec <= (*top)->u.oinfo->prec)
1028 || (!tok->u.oinfo->lassoc && tok->u.oinfo->prec < (*top)->u.oinfo->prec)))
1029 *out++ = **top;
1030
1031 /* top now points to either an operator we didn't pop,
1032 * or stack[-1] either way we need to increment it
1033 * before using it, then increment again so the stack
1034 * works */
1035 top++;
1036 *top++ = tok;
1037 break;
1038 }
1039 }
1040 while (top-- > stack) {
1041 if ((*top)->type == LPAR)
1042 eprintf("extra (\n");
1043 *out++ = **top;
1044 }
1045
1046 /* if there was no expression, use -print
1047 * if there was an expression but no -print, -exec, or -ok, add -a
1048 * -print in rpn, not infix */
1049 if (gflags.print)
1050 *out++ = (struct tok){.u.pinfo = find_primary("-print"), .type = PRIM};
1051 if (gflags.print == 2)
1052 *out++ = and;
1053
1054 out->type = END;
1055
1056 /* rpn now holds all operators and arguments in reverse polish notation
1057 * values are pushed onto stack, operators pop values off stack into
1058 * left and right pointers, pushing operator node back onto stack could
1059 * probably just do this during shunting-yard, but this is simpler code
1060 * IMO */
1061 for (tok = rpn, top = stack; tok->type != END; tok++) {
1062 if (tok->type == PRIM) {
1063 *top++ = tok;
1064 } else {
1065 if (top - stack < tok->u.oinfo->nargs)
1066 eprintf(
1067 "insufficient arguments for operator "
1068 "%s\n",
1069 tok->u.oinfo->name
1070 );
1071 tok->right = *--top;
1072 tok->left = tok->u.oinfo->nargs == 2 ? *--top : NULL;
1073 *top++ = tok;
1074 }
1075 }
1076 if (--top != stack)
1077 eprintf("extra arguments\n");
1078
1079 toks = rpn;
1080 root = *top;
1081
1082 free(infix);
1083 free(stack);
1084}
1085
1086/* for a primary, run and return result
1087 * for an operator evaluate the left side of the tree, decide whether or not to
1088 * evaluate the right based on the short-circuit boolean logic, return result
1089 * NOTE: operator NOT has NULL left side, expression on right side
1090 */
1091static int
1092eval(struct tok *tok, struct arg *arg)
1093{
1094 int ret;
1095
1096 if (!tok)
1097 return 0;
1098
1099 if (tok->type == PRIM) {
1100 arg->extra = tok->extra;
1101 return tok->u.pinfo->func(arg);
1102 }
1103
1104 ret = eval(tok->left, arg);
1105
1106 if ((tok->type == AND && ret) || (tok->type == OR && !ret) || tok->type == NOT)
1107 ret = eval(tok->right, arg);
1108
1109 return ret ^ (tok->type == NOT);
1110}
1111
1112/* evaluate path, if it's a directory iterate through directory entries and
1113 * recurse
1114 */
1115#if FEATURE_FIND_INAME
1116static int
1117pri_iname(struct arg *arg)
1118{
1119 int ret;
1120 char *path;
1121
1122 path = estrdup(arg->path);
1123 ret = !fnmatch((char *)arg->extra.p, basename(path), FNM_CASEFOLD);
1124 free(path);
1125
1126 return ret;
1127}
1128#endif
1129
1130#if FEATURE_FIND_IPATH
1131static int
1132pri_ipath(struct arg *arg)
1133{
1134 return !fnmatch((char *)arg->extra.p, arg->path, FNM_CASEFOLD);
1135}
1136#endif
1137
1138#if FEATURE_FIND_REGEX
1139static int
1140pri_regex(struct arg *arg)
1141{
1142 regex_t *re = arg->extra.p;
1143 regmatch_t match;
1144 if (regexec(re, arg->path, 1, &match, 0) == 0) {
1145 return match.rm_so == 0 && (size_t)match.rm_eo == strlen(arg->path);
1146 }
1147 return 0;
1148}
1149
1150static char **
1151get_regex_arg(char *argv[], union extra *extra)
1152{
1153 regex_t *re = emalloc(sizeof(*re));
1154 eregcomp(re, *argv, 0);
1155 extra->p = re;
1156 return argv;
1157}
1158
1159static void
1160free_regex_arg(union extra extra)
1161{
1162 regex_t *re = extra.p;
1163 regfree(re);
1164 free(re);
1165}
1166#endif
1167
1168#if FEATURE_FIND_INUM
1169static int
1170pri_inum(struct arg *arg)
1171{
1172 ino_t ino = (ino_t)arg->extra.i;
1173 return arg->st->st_ino == ino;
1174}
1175
1176static char **
1177get_inum_arg(char *argv[], union extra *extra)
1178{
1179 char *end;
1180 extra->i = strtol(*argv, &end, 10);
1181 if (end == *argv || *end)
1182 eprintf("bad number '%s'\n", *argv);
1183 return argv;
1184}
1185#endif
1186
1187#if FEATURE_FIND_SAMEFILE
1188struct SameFileArg {
1189 ino_t ino;
1190 dev_t dev;
1191};
1192
1193static int
1194pri_samefile(struct arg *arg)
1195{
1196 struct SameFileArg *s = arg->extra.p;
1197 return arg->st->st_ino == s->ino && arg->st->st_dev == s->dev;
1198}
1199
1200static char **
1201get_samefile_arg(char *argv[], union extra *extra)
1202{
1203 struct stat st;
1204 struct SameFileArg *s = emalloc(sizeof(*s));
1205 if (do_stat(*argv, &st, NULL))
1206 eprintf("failed to stat '%s':", *argv);
1207 s->ino = st.st_ino;
1208 s->dev = st.st_dev;
1209 extra->p = s;
1210 return argv;
1211}
1212#endif
1213
1214#if FEATURE_FIND_MAXDEPTH
1215static int
1216pri_maxdepth(struct arg *arg)
1217{
1218 (void)arg;
1219 return 1;
1220}
1221
1222static char **
1223get_maxdepth_arg(char *argv[], union extra *extra)
1224{
1225 (void)extra;
1226 char *end;
1227 gflags.maxdepth = strtol(*argv, &end, 10);
1228 if (end == *argv || *end || gflags.maxdepth < 0)
1229 eprintf("bad number '%s'\n", *argv);
1230 return argv;
1231}
1232#endif
1233
1234#if FEATURE_FIND_MINDEPTH
1235static int
1236pri_mindepth(struct arg *arg)
1237{
1238 (void)arg;
1239 return 1;
1240}
1241
1242static char **
1243get_mindepth_arg(char *argv[], union extra *extra)
1244{
1245 (void)extra;
1246 char *end;
1247 gflags.mindepth = strtol(*argv, &end, 10);
1248 if (end == *argv || *end || gflags.mindepth < 0)
1249 eprintf("bad number '%s'\n", *argv);
1250 return argv;
1251}
1252#endif
1253
1254#if FEATURE_FIND_DELETE
1255static int
1256pri_delete(struct arg *arg)
1257{
1258 if (remove(arg->path) < 0) {
1259 weprintf("remove %s failed:", arg->path);
1260 gflags.ret = 1;
1261 return 0;
1262 }
1263 return 1;
1264}
1265
1266static char **
1267get_delete_arg(char *argv[], union extra *extra)
1268{
1269 (void)extra;
1270 gflags.depth = 1;
1271 gflags.print = 0;
1272 return argv;
1273}
1274#endif
1275
1276#if FEATURE_FIND_QUIT
1277static int
1278pri_quit(struct arg *arg)
1279{
1280 (void)arg;
1281 gflags.quit = 1;
1282 return 1;
1283}
1284
1285static char **
1286get_quit_arg(char *argv[], union extra *extra)
1287{
1288 (void)extra;
1289 gflags.print = 0;
1290 return argv;
1291}
1292#endif
1293
1294#if FEATURE_FIND_EMPTY
1295static int
1296pri_empty(struct arg *arg)
1297{
1298 DIR *dir;
1299 struct dirent *de;
1300 int empty = 1;
1301
1302 if (S_ISREG(arg->st->st_mode)) {
1303 return arg->st->st_size == 0;
1304 } else if (S_ISDIR(arg->st->st_mode)) {
1305 dir = opendir(arg->path);
1306 if (!dir)
1307 return 0;
1308 while ((de = readdir(dir))) {
1309 if (strcmp(de->d_name, ".") && strcmp(de->d_name, "..")) {
1310 empty = 0;
1311 break;
1312 }
1313 }
1314 closedir(dir);
1315 return empty;
1316 }
1317 return 0;
1318}
1319#endif
1320
1321#if FEATURE_FIND_MMIN
1322static int
1323pri_mmin(struct arg *arg)
1324{
1325 struct narg *n = arg->extra.p;
1326 return n->cmp((start.tv_sec - arg->st->st_mtime) / 60, n->n);
1327}
1328#endif
1329
1330#if FEATURE_FIND_AMIN
1331static int
1332pri_amin(struct arg *arg)
1333{
1334 struct narg *n = arg->extra.p;
1335 return n->cmp((start.tv_sec - arg->st->st_atime) / 60, n->n);
1336}
1337#endif
1338
1339#if FEATURE_FIND_CMIN
1340static int
1341pri_cmin(struct arg *arg)
1342{
1343 struct narg *n = arg->extra.p;
1344 return n->cmp((start.tv_sec - arg->st->st_ctime) / 60, n->n);
1345}
1346#endif
1347
1348static int
1349get_depth(struct findhist *hist)
1350{
1351 int d = 0;
1352 while (hist) {
1353 d++;
1354 hist = hist->next;
1355 }
1356 return d;
1357}
1358
1359static void
1360find(char *path, struct findhist *hist)
1361{
1362 struct stat st;
1363 DIR *dir;
1364 struct dirent *de;
1365 struct findhist *f, cur;
1366 size_t namelen, pathcap = 0, len;
1367 struct arg arg = {path, &st, {NULL}};
1368 char *p, *pathbuf = NULL;
1369 int depth = get_depth(hist);
1370
1371 if (gflags.quit)
1372 return;
1373
1374 len = strlen(path) + 2; /* \0 and '/' */
1375
1376 if (do_stat(path, &st, hist) < 0) {
1377 weprintf("failed to stat %s:", path);
1378 gflags.ret = 1;
1379 return;
1380 }
1381
1382 gflags.prune = 0;
1383
1384 if (gflags.maxdepth >= 0 && depth > gflags.maxdepth)
1385 return;
1386
1387 if (gflags.mindepth < 0 || depth >= gflags.mindepth) {
1388 /* don't eval now iff we will hit the eval at the bottom which
1389 * means
1390 * 1. we are a directory 2. we have -depth 3. we don't have
1391 * -xdev or we are on same device (so most of the time we eval
1392 * here) */
1393 if (!S_ISDIR(st.st_mode) || !gflags.depth || (gflags.xdev && hist && st.st_dev != hist->dev))
1394 eval(root, &arg);
1395 }
1396
1397 if (gflags.maxdepth >= 0 && depth >= gflags.maxdepth) {
1398 if (gflags.depth && (gflags.mindepth < 0 || depth >= gflags.mindepth)) {
1399 if (S_ISDIR(st.st_mode) && (!gflags.xdev || !hist || st.st_dev == hist->dev))
1400 eval(root, &arg);
1401 }
1402 return;
1403 }
1404
1405 if (!S_ISDIR(st.st_mode) || gflags.prune || (gflags.xdev && hist && st.st_dev != hist->dev))
1406 return;
1407
1408 for (f = hist; f; f = f->next) {
1409 if (f->dev == st.st_dev && f->ino == st.st_ino) {
1410 weprintf("loop detected '%s' is '%s'\n", path, f->path);
1411 gflags.ret = 1;
1412 return;
1413 }
1414 }
1415 cur.next = hist;
1416 cur.path = path;
1417 cur.dev = st.st_dev;
1418 cur.ino = st.st_ino;
1419
1420 if (!(dir = opendir(path))) {
1421 weprintf("failed to opendir %s:", path);
1422 gflags.ret = 1;
1423 /* should we just ignore this since we hit an error? */
1424 if (gflags.depth && (gflags.mindepth < 0 || depth >= gflags.mindepth))
1425 eval(root, &arg);
1426 return;
1427 }
1428
1429 while (errno = 0, (de = readdir(dir))) {
1430 if (gflags.quit)
1431 break;
1432 if (!strcmp(de->d_name, ".") || !strcmp(de->d_name, ".."))
1433 continue;
1434 namelen = strlen(de->d_name);
1435 if (len + namelen > pathcap) {
1436 pathcap = len + namelen;
1437 pathbuf = erealloc(pathbuf, pathcap);
1438 }
1439 p = pathbuf + estrlcpy(pathbuf, path, pathcap);
1440 if (*--p != '/')
1441 estrlcat(pathbuf, "/", pathcap);
1442 estrlcat(pathbuf, de->d_name, pathcap);
1443 find(pathbuf, &cur);
1444 }
1445 free(pathbuf);
1446 if (errno) {
1447 weprintf("readdir %s:", path);
1448 gflags.ret = 1;
1449 closedir(dir);
1450 return;
1451 }
1452 closedir(dir);
1453
1454 if (gflags.depth && (gflags.mindepth < 0 || depth >= gflags.mindepth))
1455 eval(root, &arg);
1456}
1457
1458static void
1459usage(void)
1460{
1461 eprintf("usage: %s [-H | -L] path ... [expression ...]\n", argv0);
1462}
1463
1464// ?man find: search for files
1465// ?man arguments: path ... [expression ...]
1466// ?man search for files in a directory hierarchy
1467int
1468main(int argc, char **argv)
1469{
1470 char **paths;
1471 int npaths;
1472 struct tok *t;
1473
1474 gflags.maxdepth = -1;
1475 gflags.mindepth = -1;
1476
1477 ARGBEGIN
1478 {
1479 // ?man -H: specify option flag
1480 case 'H':
1481 gflags.h = 1;
1482 gflags.l = 0;
1483 break;
1484 // ?man -L: specify option flag
1485 case 'L':
1486 gflags.l = 1;
1487 gflags.h = 0;
1488 break;
1489 default:
1490 usage();
1491 }
1492 ARGEND
1493
1494 paths = argv;
1495
1496 for (; *argv && **argv != '-' && strcmp(*argv, "!") && strcmp(*argv, "("); argv++)
1497 ;
1498
1499 if (!(npaths = argv - paths))
1500 eprintf("must specify a path\n");
1501
1502 parse(argc - npaths, argv);
1503
1504 /* calculate number of bytes in environ for -exec {} + ARG_MAX avoidance
1505 * libc implementation defined whether null bytes, pointers, and
1506 * alignment are counted, so count them */
1507 for (argv = environ; *argv; argv++)
1508 envlen += strlen(*argv) + 1 + sizeof(*argv);
1509
1510 if ((argmax = sysconf(_SC_ARG_MAX)) == (size_t)-1)
1511 argmax = _POSIX_ARG_MAX;
1512
1513 if (clock_gettime(CLOCK_REALTIME, &start) < 0)
1514 weprintf("clock_gettime() failed:");
1515
1516 while (npaths--)
1517 find(*paths++, NULL);
1518
1519 for (t = toks; t->type != END; t++)
1520 if (t->type == PRIM && t->u.pinfo->freearg)
1521 t->u.pinfo->freearg(t->extra);
1522 free(toks);
1523
1524 gflags.ret |= fshut(stdin, "<stdin>") | fshut(stdout, "<stdout>");
1525
1526 return gflags.ret;
1527}
