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