sbase

suckless unix tools
git clone git://git.2f30.org/sbase.git
Log | Files | Refs | README | LICENSE

find.c (26537B)


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