Introduction
Introduction Statistics Contact Development Disclaimer Help
find.c - sbase - suckless unix tools
git clone git://git.suckless.org/sbase
Log
Files
Refs
README
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 g…
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 point…
92 } s; /* semicolon */
93 struct {
94 size_t arglen; /* number of bytes in argv befor…
95 size_t filelen; /* numer of bytes in file names …
96 size_t first; /* index one past last arg, wher…
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 …
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 wh…
215 static struct tok *root; /* points to root of expression tree, inside to…
216
217 static struct timespec start; /* time find was started, used for -[acm]t…
218
219 static size_t envlen; /* number of bytes in environ, used to calculate a…
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 itsel…
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)) =…
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 na…
410 if (len + e->u.p.arglen + e->u.p.filelen + envlen > argm…
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 NU…
424 if (e->u.p.next + 1 == e->u.p.cap)
425 e->argv = ereallocarray(e->argv, e->u.p.cap *= 2…
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…
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 p…
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), "{}") && !str…
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->arg…
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…
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 duplic…
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 f…
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 a…
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…
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 operat…
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)) { /* …
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 b…
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: …
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…
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 …
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 deci…
876 * verbage from the wikipedia page in order to m…
877 * what's going on */
878 while (top-- > stack &&
879 (( tok->u.oinfo->lassoc && tok->u.oinfo->…
880 (!tok->u.oinfo->lassoc && tok->u.oinfo->…
881 *out++ = **top;
882
883 /* top now points to either an operator we didn'…
884 * either way we need to increment it before usi…
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 …
899 * in rpn, not infix */
900 if (gflags.print)
901 *out++ = (struct tok){ .u.pinfo = find_primary("-print")…
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 n…
908 * values are pushed onto stack, operators pop values off stack …
909 * and right pointers, pushing operator node back onto stack
910 * could probably just do this during shunting-yard, but this is…
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 oper…
918 tok->right = *--top;
919 tok->left = tok->u.oinfo->nargs == 2 ? *--top :…
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…
935 * evaluate the right based on the short-circuit boolean logic, return r…
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) || to…
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 …
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 m…
984 * 1. we are a directory 2. we have -depth 3. we don't have -xde…
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…
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(*a…
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 a…
1081 * libc implementation defined whether null bytes, pointers, and…
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 }
You are viewing proxied material from suckless.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.