From e9a910b33c7837b4b868e3abda18eb4810df7f02 Mon Sep 17 00:00:00 2001 From: Leah Rowe Date: Sat, 4 Oct 2025 09:14:33 +0100 Subject: config/git: import suckless sbase i currently use the output of sha512sum in several places of xbmk, which is a bit unreliable in case output changes. other cases where i use util outputs in variables are probably reliable, because i'm using mostly posix utilities in those. to mitigate this, i now import suckless sbase, which has a reasonable sha512sum implementation. *every* binary it builds is being placed in build.list, because i'll probably start using more of them. for example, i may start modifying the "date" implementation, adding the GNU-specific options that i need as mentioned on init.sh i'm importing it in util/ because the sha512sum util is needed for verifying project sources, so if sbase itself is a "project source", that means we can into a chicken and egg bootstrapping problem. this is sbase at revision: 055cc1ae1b3a13c3d8f25af0a4a3316590efcd48 Signed-off-by: Leah Rowe --- util/sbase/find.c | 1103 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1103 insertions(+) create mode 100644 util/sbase/find.c (limited to 'util/sbase/find.c') diff --git a/util/sbase/find.c b/util/sbase/find.c new file mode 100644 index 00000000..5bc1a1f1 --- /dev/null +++ b/util/sbase/find.c @@ -0,0 +1,1103 @@ +/* See LICENSE file for copyright and license details. */ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include + +#include "util.h" + +/* because putting integers in pointers is undefined by the standard */ +union extra { + void *p; + intmax_t i; +}; + +/* Argument passed into a primary's function */ +struct arg { + char *path; + struct stat *st; + union extra extra; +}; + +/* Information about each primary, for lookup table */ +struct pri_info { + char *name; + int (*func)(struct arg *arg); + char **(*getarg)(char **argv, union extra *extra); + void (*freearg)(union extra extra); + char narg; /* -xdev, -depth, -print don't take args but have getarg() */ +}; + +/* Information about operators, for lookup table */ +struct op_info { + char *name; /* string representation of op */ + char type; /* from tok.type */ + char prec; /* precedence */ + char nargs; /* number of arguments (unary or binary) */ + char lassoc; /* left associative */ +}; + +/* Token when lexing/parsing + * (although also used for the expression tree) */ +struct tok { + struct tok *left, *right; /* if (type == NOT) left = NULL */ + union extra extra; + union { + struct pri_info *pinfo; /* if (type == PRIM) */ + struct op_info *oinfo; + } u; + enum { + PRIM = 0, LPAR, RPAR, NOT, AND, OR, END + } type; +}; + +/* structures used for arg.extra.p and tok.extra.p */ +struct permarg { + mode_t mode; + char exact; +}; + +struct okarg { + char ***braces; + char **argv; +}; + +/* for all arguments that take a number + * +n, n, -n mean > n, == n, < n respectively */ +struct narg { + int (*cmp)(int a, int b); + int n; +}; + +struct sizearg { + struct narg n; + char bytes; /* size is in bytes, not 512 byte sectors */ +}; + +struct execarg { + union { + struct { + char ***braces; /* NULL terminated list of pointers into argv where {} were */ + } s; /* semicolon */ + struct { + size_t arglen; /* number of bytes in argv before files are added */ + size_t filelen; /* numer of bytes in file names added to argv */ + size_t first; /* index one past last arg, where first file goes */ + size_t next; /* index where next file goes */ + size_t cap; /* capacity of argv */ + } p; /* plus */ + } u; + char **argv; /* NULL terminated list of arguments (allocated if isplus) */ + char isplus; /* -exec + instead of -exec ; */ +}; + +/* used to find loops while recursing through directory structure */ +struct findhist { + struct findhist *next; + char *path; + dev_t dev; + ino_t ino; +}; + +/* Utility */ +static int spawn(char *argv[]); +static int do_stat(char *path, struct stat *sb, struct findhist *hist); + +/* Primaries */ +static int pri_name (struct arg *arg); +static int pri_path (struct arg *arg); +static int pri_nouser (struct arg *arg); +static int pri_nogroup(struct arg *arg); +static int pri_xdev (struct arg *arg); +static int pri_prune (struct arg *arg); +static int pri_perm (struct arg *arg); +static int pri_type (struct arg *arg); +static int pri_links (struct arg *arg); +static int pri_user (struct arg *arg); +static int pri_group (struct arg *arg); +static int pri_size (struct arg *arg); +static int pri_atime (struct arg *arg); +static int pri_ctime (struct arg *arg); +static int pri_mtime (struct arg *arg); +static int pri_exec (struct arg *arg); +static int pri_ok (struct arg *arg); +static int pri_print (struct arg *arg); +static int pri_print0 (struct arg *arg); +static int pri_newer (struct arg *arg); +static int pri_depth (struct arg *arg); + +/* Getargs */ +static char **get_name_arg (char *argv[], union extra *extra); +static char **get_path_arg (char *argv[], union extra *extra); +static char **get_xdev_arg (char *argv[], union extra *extra); +static char **get_perm_arg (char *argv[], union extra *extra); +static char **get_type_arg (char *argv[], union extra *extra); +static char **get_n_arg (char *argv[], union extra *extra); +static char **get_user_arg (char *argv[], union extra *extra); +static char **get_group_arg(char *argv[], union extra *extra); +static char **get_size_arg (char *argv[], union extra *extra); +static char **get_exec_arg (char *argv[], union extra *extra); +static char **get_ok_arg (char *argv[], union extra *extra); +static char **get_print_arg(char *argv[], union extra *extra); +static char **get_newer_arg(char *argv[], union extra *extra); +static char **get_depth_arg(char *argv[], union extra *extra); + +/* Freeargs */ +static void free_extra (union extra extra); +static void free_exec_arg(union extra extra); +static void free_ok_arg (union extra extra); + +/* Parsing/Building/Running */ +static void fill_narg(char *s, struct narg *n); +static struct pri_info *find_primary(char *name); +static struct op_info *find_op(char *name); +static void parse(int argc, char **argv); +static int eval(struct tok *tok, struct arg *arg); +static void find(char *path, struct findhist *hist); +static void usage(void); + +/* for comparisons with narg */ +static int cmp_gt(int a, int b) { return a > b; } +static int cmp_eq(int a, int b) { return a == b; } +static int cmp_lt(int a, int b) { return a < b; } + +/* order from find(1p), may want to alphabetize */ +static struct pri_info primaries[] = { + { "-name" , pri_name , get_name_arg , NULL , 1 }, + { "-path" , pri_path , get_path_arg , NULL , 1 }, + { "-nouser" , pri_nouser , NULL , NULL , 1 }, + { "-nogroup", pri_nogroup, NULL , NULL , 1 }, + { "-xdev" , pri_xdev , get_xdev_arg , NULL , 0 }, + { "-prune" , pri_prune , NULL , NULL , 1 }, + { "-perm" , pri_perm , get_perm_arg , free_extra , 1 }, + { "-type" , pri_type , get_type_arg , NULL , 1 }, + { "-links" , pri_links , get_n_arg , free_extra , 1 }, + { "-user" , pri_user , get_user_arg , NULL , 1 }, + { "-group" , pri_group , get_group_arg, NULL , 1 }, + { "-size" , pri_size , get_size_arg , free_extra , 1 }, + { "-atime" , pri_atime , get_n_arg , free_extra , 1 }, + { "-ctime" , pri_ctime , get_n_arg , free_extra , 1 }, + { "-mtime" , pri_mtime , get_n_arg , free_extra , 1 }, + { "-exec" , pri_exec , get_exec_arg , free_exec_arg, 1 }, + { "-ok" , pri_ok , get_ok_arg , free_ok_arg , 1 }, + { "-print" , pri_print , get_print_arg, NULL , 0 }, + { "-print0" , pri_print0 , get_print_arg, NULL , 0 }, + { "-newer" , pri_newer , get_newer_arg, NULL , 1 }, + { "-depth" , pri_depth , get_depth_arg, NULL , 0 }, + + { NULL, NULL, NULL, NULL, 0 } +}; + +static struct op_info ops[] = { + { "(" , LPAR, 0, 0, 0 }, /* parens are handled specially */ + { ")" , RPAR, 0, 0, 0 }, + { "!" , NOT , 3, 1, 0 }, + { "-a", AND , 2, 2, 1 }, + { "-o", OR , 1, 2, 1 }, + + { NULL, 0, 0, 0, 0 } +}; + +extern char **environ; + +static struct tok *toks; /* holds allocated array of all toks created while parsing */ +static struct tok *root; /* points to root of expression tree, inside toks array */ + +static struct timespec start; /* time find was started, used for -[acm]time */ + +static size_t envlen; /* number of bytes in environ, used to calculate against ARG_MAX */ +static size_t argmax; /* value of ARG_MAX retrieved using sysconf(3p) */ + +static struct { + char ret ; /* return value from main */ + char depth; /* -depth, directory contents before directory itself */ + char h ; /* -H, follow symlinks on command line */ + char l ; /* -L, follow all symlinks (command line and search) */ + char prune; /* hit -prune */ + char xdev ; /* -xdev, prune directories on different devices */ + char print; /* whether we will need -print when parsing */ +} gflags; + +/* + * Utility + */ +static int +spawn(char *argv[]) +{ + pid_t pid; + int status; + + /* flush stdout so that -print output always appears before + * any output from the command and does not get cut-off in + * the middle of a line. */ + fflush(stdout); + + switch((pid = fork())) { + case -1: + eprintf("fork:"); + case 0: + execvp(*argv, argv); + weprintf("exec %s failed:", *argv); + _exit(1); + } + + /* FIXME: proper course of action for waitpid() on EINTR? */ + waitpid(pid, &status, 0); + return status; +} + +static int +do_stat(char *path, struct stat *sb, struct findhist *hist) +{ + if (gflags.l || (gflags.h && !hist)) { + if (stat(path, sb) == 0) { + return 0; + } else if (errno != ENOENT && errno != ENOTDIR) { + return -1; + } + } + + return lstat(path, sb); +} + +/* + * Primaries + */ +static int +pri_name(struct arg *arg) +{ + int ret; + char *path; + + path = estrdup(arg->path); + ret = !fnmatch((char *)arg->extra.p, basename(path), 0); + free(path); + + return ret; +} + +static int +pri_path(struct arg *arg) +{ + return !fnmatch((char *)arg->extra.p, arg->path, 0); +} + +/* FIXME: what about errors? find(1p) literally just says + * "for which the getpwuid() function ... returns NULL" */ +static int +pri_nouser(struct arg *arg) +{ + return !getpwuid(arg->st->st_uid); +} + +static int +pri_nogroup(struct arg *arg) +{ + return !getgrgid(arg->st->st_gid); +} + +static int +pri_xdev(struct arg *arg) +{ + return 1; +} + +static int +pri_prune(struct arg *arg) +{ + return gflags.prune = 1; +} + +static int +pri_perm(struct arg *arg) +{ + struct permarg *p = (struct permarg *)arg->extra.p; + + return (arg->st->st_mode & 07777 & (p->exact ? -1U : p->mode)) == p->mode; +} + +static int +pri_type(struct arg *arg) +{ + switch ((char)arg->extra.i) { + default : return 0; /* impossible, but placate warnings */ + case 'b': return S_ISBLK (arg->st->st_mode); + case 'c': return S_ISCHR (arg->st->st_mode); + case 'd': return S_ISDIR (arg->st->st_mode); + case 'l': return S_ISLNK (arg->st->st_mode); + case 'p': return S_ISFIFO(arg->st->st_mode); + case 'f': return S_ISREG (arg->st->st_mode); + case 's': return S_ISSOCK(arg->st->st_mode); + } +} + +static int +pri_links(struct arg *arg) +{ + struct narg *n = arg->extra.p; + return n->cmp(arg->st->st_nlink, n->n); +} + +static int +pri_user(struct arg *arg) +{ + return arg->st->st_uid == (uid_t)arg->extra.i; +} + +static int +pri_group(struct arg *arg) +{ + return arg->st->st_gid == (gid_t)arg->extra.i; +} + +static int +pri_size(struct arg *arg) +{ + struct sizearg *s = arg->extra.p; + off_t size = arg->st->st_size; + + if (!s->bytes) + size = size / 512 + !!(size % 512); + + return s->n.cmp(size, s->n.n); +} + +/* FIXME: ignoring nanoseconds in atime, ctime, mtime */ +static int +pri_atime(struct arg *arg) +{ + struct narg *n = arg->extra.p; + return n->cmp((start.tv_sec - arg->st->st_atime) / 86400, n->n); +} + +static int +pri_ctime(struct arg *arg) +{ + struct narg *n = arg->extra.p; + return n->cmp((start.tv_sec - arg->st->st_ctime) / 86400, n->n); +} + +static int +pri_mtime(struct arg *arg) +{ + struct narg *n = arg->extra.p; + return n->cmp((start.tv_sec - arg->st->st_mtime) / 86400, n->n); +} + +static int +pri_exec(struct arg *arg) +{ + int status; + size_t len; + char **sp, ***brace; + struct execarg *e = arg->extra.p; + + if (e->isplus) { + len = strlen(arg->path) + 1; + + /* if we reached ARG_MAX, fork, exec, wait, free file names, reset list */ + if (len + e->u.p.arglen + e->u.p.filelen + envlen > argmax) { + e->argv[e->u.p.next] = NULL; + + status = spawn(e->argv); + gflags.ret = gflags.ret || status; + + for (sp = e->argv + e->u.p.first; *sp; sp++) + free(*sp); + + e->u.p.next = e->u.p.first; + e->u.p.filelen = 0; + } + + /* if we have too many files, realloc (with space for NULL termination) */ + if (e->u.p.next + 1 == e->u.p.cap) + e->argv = ereallocarray(e->argv, e->u.p.cap *= 2, sizeof(*e->argv)); + + e->argv[e->u.p.next++] = estrdup(arg->path); + e->u.p.filelen += len + sizeof(arg->path); + + return 1; + } else { + /* insert path everywhere user gave us {} */ + for (brace = e->u.s.braces; *brace; brace++) + **brace = arg->path; + + status = spawn(e->argv); + return !status; + } +} + +static int +pri_ok(struct arg *arg) +{ + int status, reply; + char ***brace, c; + struct okarg *o = arg->extra.p; + + fprintf(stderr, "%s: %s ? ", *o->argv, arg->path); + reply = fgetc(stdin); + + /* throw away rest of line */ + while ((c = fgetc(stdin)) != '\n' && c != EOF) + /* FIXME: what if the first character of the rest of the line is a null + * byte? */ + ; + + if (feof(stdin)) /* FIXME: ferror()? */ + clearerr(stdin); + + if (reply != 'y' && reply != 'Y') + return 0; + + /* insert filename everywhere user gave us {} */ + for (brace = o->braces; *brace; brace++) + **brace = arg->path; + + status = spawn(o->argv); + return !!status; +} + +static int +pri_print(struct arg *arg) +{ + if (puts(arg->path) == EOF) + eprintf("puts failed:"); + return 1; +} + +static int +pri_print0(struct arg *arg) +{ + if (fwrite(arg->path, strlen(arg->path) + 1, 1, stdout) != 1) + eprintf("fwrite failed:"); + return 1; +} + +/* FIXME: ignoring nanoseconds */ +static int +pri_newer(struct arg *arg) +{ + return arg->st->st_mtime > (time_t)arg->extra.i; +} + +static int +pri_depth(struct arg *arg) +{ + return 1; +} + +/* + * Getargs + * consume any arguments for given primary and fill extra + * return pointer to last argument, the pointer will be incremented in parse() + */ +static char ** +get_name_arg(char *argv[], union extra *extra) +{ + extra->p = *argv; + return argv; +} + +static char ** +get_path_arg(char *argv[], union extra *extra) +{ + extra->p = *argv; + return argv; +} + +static char ** +get_xdev_arg(char *argv[], union extra *extra) +{ + gflags.xdev = 1; + return argv; +} + +static char ** +get_perm_arg(char *argv[], union extra *extra) +{ + mode_t mask; + struct permarg *p = extra->p = emalloc(sizeof(*p)); + + if (**argv == '-') + (*argv)++; + else + p->exact = 1; + + mask = umask(0); + umask(mask); + + p->mode = parsemode(*argv, 0, mask); + + return argv; +} + +static char ** +get_type_arg(char *argv[], union extra *extra) +{ + if (!strchr("bcdlpfs", **argv)) + eprintf("invalid type %c for -type primary\n", **argv); + + extra->i = **argv; + return argv; +} + +static char ** +get_n_arg(char *argv[], union extra *extra) +{ + struct narg *n = extra->p = emalloc(sizeof(*n)); + fill_narg(*argv, n); + return argv; +} + +static char ** +get_user_arg(char *argv[], union extra *extra) +{ + char *end; + struct passwd *p = getpwnam(*argv); + + if (p) { + extra->i = p->pw_uid; + } else { + extra->i = strtol(*argv, &end, 10); + if (end == *argv || *end) + eprintf("unknown user '%s'\n", *argv); + } + return argv; +} + +static char ** +get_group_arg(char *argv[], union extra *extra) +{ + char *end; + struct group *g = getgrnam(*argv); + + if (g) { + extra->i = g->gr_gid; + } else { + extra->i = strtol(*argv, &end, 10); + if (end == *argv || *end) + eprintf("unknown group '%s'\n", *argv); + } + return argv; +} + +static char ** +get_size_arg(char *argv[], union extra *extra) +{ + char *p = *argv + strlen(*argv); + struct sizearg *s = extra->p = emalloc(sizeof(*s)); + /* if the number is followed by 'c', the size will by in bytes */ + if ((s->bytes = (p > *argv && *--p == 'c'))) + *p = '\0'; + + fill_narg(*argv, &s->n); + return argv; +} + +static char ** +get_exec_arg(char *argv[], union extra *extra) +{ + char **arg, **new, ***braces; + int nbraces = 0; + struct execarg *e = extra->p = emalloc(sizeof(*e)); + + for (arg = argv; *arg; arg++) + if (!strcmp(*arg, ";")) + break; + else if (arg > argv && !strcmp(*(arg - 1), "{}") && !strcmp(*arg, "+")) + break; + else if (!strcmp(*arg, "{}")) + nbraces++; + + if (!*arg) + eprintf("no terminating ; or {} + for -exec primary\n"); + + e->isplus = **arg == '+'; + *arg = NULL; + + if (e->isplus) { + *(arg - 1) = NULL; /* don't need the {} in there now */ + e->u.p.arglen = e->u.p.filelen = 0; + e->u.p.first = e->u.p.next = arg - argv - 1; + e->u.p.cap = (arg - argv) * 2; + e->argv = ereallocarray(NULL, e->u.p.cap, sizeof(*e->argv)); + + for (arg = argv, new = e->argv; *arg; arg++, new++) { + *new = *arg; + e->u.p.arglen += strlen(*arg) + 1 + sizeof(*arg); + } + arg++; /* due to our extra NULL */ + } else { + e->argv = argv; + e->u.s.braces = ereallocarray(NULL, ++nbraces, sizeof(*e->u.s.braces)); /* ++ for NULL */ + + for (arg = argv, braces = e->u.s.braces; *arg; arg++) + if (!strcmp(*arg, "{}")) + *braces++ = arg; + *braces = NULL; + } + gflags.print = 0; + return arg; +} + +static char ** +get_ok_arg(char *argv[], union extra *extra) +{ + char **arg, ***braces; + int nbraces = 0; + struct okarg *o = extra->p = emalloc(sizeof(*o)); + + for (arg = argv; *arg; arg++) + if (!strcmp(*arg, ";")) + break; + else if (!strcmp(*arg, "{}")) + nbraces++; + + if (!*arg) + eprintf("no terminating ; for -ok primary\n"); + *arg = NULL; + + o->argv = argv; + o->braces = ereallocarray(NULL, ++nbraces, sizeof(*o->braces)); + + for (arg = argv, braces = o->braces; *arg; arg++) + if (!strcmp(*arg, "{}")) + *braces++ = arg; + *braces = NULL; + + gflags.print = 0; + return arg; +} + +static char ** +get_print_arg(char *argv[], union extra *extra) +{ + gflags.print = 0; + return argv; +} + +/* FIXME: ignoring nanoseconds */ +static char ** +get_newer_arg(char *argv[], union extra *extra) +{ + struct stat st; + + if (do_stat(*argv, &st, NULL)) + eprintf("failed to stat '%s':", *argv); + + extra->i = st.st_mtime; + return argv; +} + +static char ** +get_depth_arg(char *argv[], union extra *extra) +{ + gflags.depth = 1; + return argv; +} + +/* + * Freeargs + */ +static void +free_extra(union extra extra) +{ + free(extra.p); +} + +static void +free_exec_arg(union extra extra) +{ + int status; + char **arg; + struct execarg *e = extra.p; + + if (!e->isplus) { + free(e->u.s.braces); + } else { + e->argv[e->u.p.next] = NULL; + + /* if we have files, do the last exec */ + if (e->u.p.first != e->u.p.next) { + status = spawn(e->argv); + gflags.ret = gflags.ret || status; + } + for (arg = e->argv + e->u.p.first; *arg; arg++) + free(*arg); + free(e->argv); + } + free(e); +} + +static void +free_ok_arg(union extra extra) +{ + struct okarg *o = extra.p; + + free(o->braces); + free(o); +} + +/* + * Parsing/Building/Running + */ +static void +fill_narg(char *s, struct narg *n) +{ + char *end; + + switch (*s) { + case '+': n->cmp = cmp_gt; s++; break; + case '-': n->cmp = cmp_lt; s++; break; + default : n->cmp = cmp_eq; break; + } + n->n = strtol(s, &end, 10); + if (end == s || *end) + eprintf("bad number '%s'\n", s); +} + +static struct pri_info * +find_primary(char *name) +{ + struct pri_info *p; + + for (p = primaries; p->name; p++) + if (!strcmp(name, p->name)) + return p; + return NULL; +} + +static struct op_info * +find_op(char *name) +{ + struct op_info *o; + + for (o = ops; o->name; o++) + if (!strcmp(name, o->name)) + return o; + return NULL; +} + +/* given the expression from the command line + * 1) convert arguments from strings to tok and place in an array duplicating + * the infix expression given, inserting "-a" where it was omitted + * 2) allocate an array to hold the correct number of tok, and convert from + * infix to rpn (using shunting-yard), add -a and -print if necessary + * 3) evaluate the rpn filling in left and right pointers to create an + * expression tree (tok are still all contained in the rpn array, just + * pointing at eachother) + */ +static void +parse(int argc, char **argv) +{ + struct tok *tok, *rpn, *out, **top, *infix, **stack; + struct op_info *op; + struct pri_info *pri; + char **arg; + int lasttype = -1; + size_t ntok = 0; + struct tok and = { .u.oinfo = find_op("-a"), .type = AND }; + + gflags.print = 1; + + /* convert argv to infix expression of tok, inserting in *tok */ + infix = ereallocarray(NULL, 2 * argc + 1, sizeof(*infix)); + for (arg = argv, tok = infix; *arg; arg++, tok++) { + pri = find_primary(*arg); + + if (pri) { /* token is a primary, fill out tok and get arguments */ + if (lasttype == PRIM || lasttype == RPAR) { + *tok++ = and; + ntok++; + } + if (pri->getarg) { + if (pri->narg && !*++arg) + eprintf("no argument for primary %s\n", pri->name); + arg = pri->getarg(arg, &tok->extra); + } + tok->u.pinfo = pri; + tok->type = PRIM; + } else if ((op = find_op(*arg))) { /* token is an operator */ + if (lasttype == LPAR && op->type == RPAR) + eprintf("empty parens\n"); + if ((lasttype == PRIM || lasttype == RPAR) && + (op->type == NOT || op->type == LPAR)) { /* need another implicit -a */ + *tok++ = and; + ntok++; + } + tok->type = op->type; + tok->u.oinfo = op; + } else { + /* token is neither primary nor operator, must be */ + if ((*arg)[0] == '-') /* an unsupported option */ + eprintf("unknown operand: %s\n", *arg); + else /* or a path in the wrong place */ + eprintf("paths must precede expression: %s\n", *arg); + } + if (tok->type != LPAR && tok->type != RPAR) + ntok++; /* won't have parens in rpn */ + lasttype = tok->type; + } + tok->type = END; + ntok++; + + if (gflags.print && (arg != argv)) /* need to add -a -print (not just -print) */ + gflags.print++; + + /* use shunting-yard to convert from infix to rpn + * https://en.wikipedia.org/wiki/Shunting-yard_algorithm + * read from infix, resulting rpn ends up in rpn, next position in rpn is out + * push operators onto stack, next position in stack is top */ + rpn = ereallocarray(NULL, ntok + gflags.print, sizeof(*rpn)); + stack = ereallocarray(NULL, argc + gflags.print, sizeof(*stack)); + for (tok = infix, out = rpn, top = stack; tok->type != END; tok++) { + switch (tok->type) { + case PRIM: *out++ = *tok; break; + case LPAR: *top++ = tok; break; + case RPAR: + while (top-- > stack && (*top)->type != LPAR) + *out++ = **top; + if (top < stack) + eprintf("extra )\n"); + break; + default: + /* this expression can be simplified, but I decided copy the + * verbage from the wikipedia page in order to more clearly explain + * what's going on */ + while (top-- > stack && + (( tok->u.oinfo->lassoc && tok->u.oinfo->prec <= (*top)->u.oinfo->prec) || + (!tok->u.oinfo->lassoc && tok->u.oinfo->prec < (*top)->u.oinfo->prec))) + *out++ = **top; + + /* top now points to either an operator we didn't pop, or stack[-1] + * either way we need to increment it before using it, then + * increment again so the stack works */ + top++; + *top++ = tok; + break; + } + } + while (top-- > stack) { + if ((*top)->type == LPAR) + eprintf("extra (\n"); + *out++ = **top; + } + + /* if there was no expression, use -print + * if there was an expression but no -print, -exec, or -ok, add -a -print + * in rpn, not infix */ + if (gflags.print) + *out++ = (struct tok){ .u.pinfo = find_primary("-print"), .type = PRIM }; + if (gflags.print == 2) + *out++ = and; + + out->type = END; + + /* rpn now holds all operators and arguments in reverse polish notation + * values are pushed onto stack, operators pop values off stack into left + * and right pointers, pushing operator node back onto stack + * could probably just do this during shunting-yard, but this is simpler + * code IMO */ + for (tok = rpn, top = stack; tok->type != END; tok++) { + if (tok->type == PRIM) { + *top++ = tok; + } else { + if (top - stack < tok->u.oinfo->nargs) + eprintf("insufficient arguments for operator %s\n", tok->u.oinfo->name); + tok->right = *--top; + tok->left = tok->u.oinfo->nargs == 2 ? *--top : NULL; + *top++ = tok; + } + } + if (--top != stack) + eprintf("extra arguments\n"); + + toks = rpn; + root = *top; + + free(infix); + free(stack); +} + +/* for a primary, run and return result + * for an operator evaluate the left side of the tree, decide whether or not to + * evaluate the right based on the short-circuit boolean logic, return result + * NOTE: operator NOT has NULL left side, expression on right side + */ +static int +eval(struct tok *tok, struct arg *arg) +{ + int ret; + + if (!tok) + return 0; + + if (tok->type == PRIM) { + arg->extra = tok->extra; + return tok->u.pinfo->func(arg); + } + + ret = eval(tok->left, arg); + + if ((tok->type == AND && ret) || (tok->type == OR && !ret) || tok->type == NOT) + ret = eval(tok->right, arg); + + return ret ^ (tok->type == NOT); +} + +/* evaluate path, if it's a directory iterate through directory entries and + * recurse + */ +static void +find(char *path, struct findhist *hist) +{ + struct stat st; + DIR *dir; + struct dirent *de; + struct findhist *f, cur; + size_t namelen, pathcap = 0, len; + struct arg arg = { path, &st, { NULL } }; + char *p, *pathbuf = NULL; + + len = strlen(path) + 2; /* \0 and '/' */ + + if (do_stat(path, &st, hist) < 0) { + weprintf("failed to stat %s:", path); + gflags.ret = 1; + return; + } + + gflags.prune = 0; + + /* don't eval now iff we will hit the eval at the bottom which means + * 1. we are a directory 2. we have -depth 3. we don't have -xdev or we are + * on same device (so most of the time we eval here) */ + if (!S_ISDIR(st.st_mode) || + !gflags.depth || + (gflags.xdev && hist && st.st_dev != hist->dev)) + eval(root, &arg); + + if (!S_ISDIR(st.st_mode) || + gflags.prune || + (gflags.xdev && hist && st.st_dev != hist->dev)) + return; + + for (f = hist; f; f = f->next) { + if (f->dev == st.st_dev && f->ino == st.st_ino) { + weprintf("loop detected '%s' is '%s'\n", path, f->path); + gflags.ret = 1; + return; + } + } + cur.next = hist; + cur.path = path; + cur.dev = st.st_dev; + cur.ino = st.st_ino; + + if (!(dir = opendir(path))) { + weprintf("failed to opendir %s:", path); + gflags.ret = 1; + /* should we just ignore this since we hit an error? */ + if (gflags.depth) + eval(root, &arg); + return; + } + + while (errno = 0, (de = readdir(dir))) { + if (!strcmp(de->d_name, ".") || !strcmp(de->d_name, "..")) + continue; + namelen = strlen(de->d_name); + if (len + namelen > pathcap) { + pathcap = len + namelen; + pathbuf = erealloc(pathbuf, pathcap); + } + p = pathbuf + estrlcpy(pathbuf, path, pathcap); + if (*--p != '/') + estrlcat(pathbuf, "/", pathcap); + estrlcat(pathbuf, de->d_name, pathcap); + find(pathbuf, &cur); + } + free(pathbuf); + if (errno) { + weprintf("readdir %s:", path); + gflags.ret = 1; + closedir(dir); + return; + } + closedir(dir); + + if (gflags.depth) + eval(root, &arg); +} + +static void +usage(void) +{ + eprintf("usage: %s [-H | -L] path ... [expression ...]\n", argv0); +} + +int +main(int argc, char **argv) +{ + char **paths; + int npaths; + struct tok *t; + + ARGBEGIN { + case 'H': + gflags.h = 1; + gflags.l = 0; + break; + case 'L': + gflags.l = 1; + gflags.h = 0; + break; + default: + usage(); + } ARGEND + + paths = argv; + + for (; *argv && **argv != '-' && strcmp(*argv, "!") && strcmp(*argv, "("); argv++) + ; + + if (!(npaths = argv - paths)) + eprintf("must specify a path\n"); + + parse(argc - npaths, argv); + + /* calculate number of bytes in environ for -exec {} + ARG_MAX avoidance + * libc implementation defined whether null bytes, pointers, and alignment + * are counted, so count them */ + for (argv = environ; *argv; argv++) + envlen += strlen(*argv) + 1 + sizeof(*argv); + + if ((argmax = sysconf(_SC_ARG_MAX)) == (size_t)-1) + argmax = _POSIX_ARG_MAX; + + if (clock_gettime(CLOCK_REALTIME, &start) < 0) + weprintf("clock_gettime() failed:"); + + while (npaths--) + find(*paths++, NULL); + + for (t = toks; t->type != END; t++) + if (t->type == PRIM && t->u.pinfo->freearg) + t->u.pinfo->freearg(t->extra); + free(toks); + + gflags.ret |= fshut(stdin, "") | fshut(stdout, ""); + + return gflags.ret; +} -- cgit v1.2.1