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