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 } |