sbase

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

find.c (26495B)


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