/* ff.c --- functional find: NetBSD find(1) semantics, one letter per switch
 *
 * Walks each path and evaluates an expression for every node, as find(1)
 * does. -v writes the cksh line, inode links . size mdate name, and -k
 * sorts what is printed by those columns with the key grammar of srt(1)
 * and cksh(1). Requirements and decision record: plan-ff.md.
 *
 * Dependency posture: none beyond libc. On Linux, -u and -g names resolve
 * through getent(1) at a fixed path, never getpwnam(3): a static glibc
 * binary cannot load NSS modules reliably, and /etc/passwd alone is not the
 * user database under LDAP, sssd or systemd-homed. No getent is an error.
 * The directory walker is owned rather than fts(3): musl ships no fts, and
 * here every directory is opened with openat(2) relative to its parent's
 * descriptor and verified by dev/ino against the stat taken while listing,
 * so no path is re-resolved after it was checked. -x (execdir) and -delete
 * act through that verified parent descriptor for the same reason. No
 * setlocale() call is made. Static on Linux and NetBSD; Darwin links
 * libSystem only.
 *
 * Deliberate departures from find: -r is unanchored ERE; -s counts bytes with
 * exact comparison; time primaries compare age in seconds; -d is a global
 * walk bound; {} substitutes only as a whole argument; names printed to a
 * terminal have control bytes escaped. See --help, DIFFERENCES.
 *
 * Reversals of r0.6, recorded here and in plan-ff.md section 12:
 *   - -k takes a list of columns, joined or as the next word, and the
 *     columns it does not name follow left to right (was: -k[r][N], one
 *     field, then the fields after it); -krN is retired for -kNr
 *   - repeated -k accumulate (was: the last one wins)
 *   - column 3 is a null column: -k3 orders by the others (was: walk
 *     order, nothing held)
 *   - -Z ends -v lines too (was: -f and the default print only)
 *   - a negative mdate prints as signed hex (was two's complement)
 *   - --help on a terminal goes through mandoc or nroff (was: the text
 *     through $PAGER); the pager warning 6ab7ff4e is gone
 *
 * revision 6af927be 20261114 193214 PST Sat --- r0.7 key list -k5,4 with
 *          the grammar of srt and cksh; -k joined, as the next word, or
 *          last in a group; -kNr, x a no-op on numeric columns; named
 *          columns then the rest; -Z NUL on every record; signed mdate;
 *          column 6 keyed as printed; --help as a man page on a terminal,
 *          --man its source; --version, --fn, --bin, --zero-terminated;
 *          manual on the cksh model
 * revision 6ae4ea00 20261030 120328 PDT Fri --- r0.6 -r always ERE, -E
 *          retired; --help through $PAGER on a terminal
 * revision 6adcb748 20261024 064856 PDT Sat --- r0.5 -mode is the
 *          permission query (was -k); -k[r][N] sorts printed records
 * revision 6abc5da8 20260929 175400 PDT Tue --- r0.4 -0 true, -1 false,
 *          -Z NUL output, -y same node; -w sign apart; -delete refuses an
 *          operand ending in .. or the root directory whole
 * revision 6abb42b9 20260928 214649 PDT Mon --- r0.3 -w when, -i hex, -V,
 *          grouped examples; Darwin test fixes
 * revision 6ab89f43 20260926 214451 PDT Sat --- r0.2 permission query,
 *          -not, "not" diagnostics
 * original 6ab7fec8 20260926 102008 PDT Sat --- r0.1 owned openat walker,
 *          one-letter grammar, -x/-j/-delete, getent ids, tty escaping,
 *          status bitmask, chkerr/chkwrn diagnostics; companion
 *          ff.fn.bash translates to the native find; model cksh
 *
 * (c) 2026 George Georgalis <george@iuxta.com> Unlimited use with attribution.
 */

/* each enables FNM_CASEFOLD, statx or st_birthtime on its own platform */
#define _GNU_SOURCE		/* glibc, musl */
#define _DARWIN_C_SOURCE	/* Darwin */
#define _NETBSD_SOURCE		/* NetBSD */

#include <sys/types.h>
#include <sys/resource.h>
#include <sys/stat.h>
#include <sys/wait.h>
#include <dirent.h>
#include <errno.h>
#include <fcntl.h>
#include <fnmatch.h>
#if !defined(__linux__)
#include <grp.h>
#endif
#include <inttypes.h>
#include <limits.h>
#if !defined(__linux__)
#include <pwd.h>
#endif
#include <regex.h>
#include <signal.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

/* exit status bits; 1 and 2 are fatal, the rest accumulate */
#define ST_USAGE  1	/* invalid option or expression */
#define ST_ENV    2	/* memory, stdout, fork/pipe, unsafe PATH for -x */
#define ST_NODE   4	/* cannot stat, open, read or delete a node */
#define ST_EXEC   8	/* exec failed, or a + batch exited nonzero */
#define ST_LOOP  16	/* filesystem or symlink loop */
#define ST_RACE  32	/* node changed between listing and opening */

#define FDCAP 64	/* most directory descriptors held open at once */

#ifndef FNM_CASEFOLD
#error "fnmatch lacks FNM_CASEFOLD; -I needs it"
#endif

#if defined(__APPLE__)
#define MTIM(s) ((s)->st_mtimespec)
#else
#define MTIM(s) ((s)->st_mtim)
#endif

#define FF_REV "ff r0.7 6af927be"

static const char *prog = "ff";
static int status;

/* options */
static int opt_I, opt_H, opt_L, opt_D, opt_S, opt_X, opt_Z, opt_V;
static long mindepth = 0, maxdepth = LONG_MAX;

static time_t now;
static int esc_out, esc_err;	/* escape names: stdout/stderr is a tty */
static int quitting, need_stat;
static int deleting;		/* -delete in the expression: refuse_operand */
#define NCOL 6		/* columns of the -v line: inode links . size mdate name */
static int opt_k;		/* -k given: records are held and sorted */
static int kcol[NCOL], krev[NCOL], nk;	/* -k list as given */
static int ord[NCOL], rev[NCOL];	/* resolved comparison order */

/* ---------------------------------------------------------------- output */

/* bytes of one printable UTF-8 sequence at p, 0 when *p must be escaped */
static size_t
u8len(const unsigned char *p, const unsigned char *e)
{
	unsigned c = *p;
	unsigned long cp;
	size_t n, i;

	if (c >= 0x20 && c < 0x7f)
		return 1;
	if (c < 0xc2 || c > 0xf4)	/* C0, DEL, stray continuation, overlong */
		return 0;
	n = c < 0xe0 ? 2 : c < 0xf0 ? 3 : 4;
	if ((size_t)(e - p) < n)
		return 0;
	cp = c & (0x3fu >> (n - 1));
	for (i = 1; i < n; i++) {
		if ((p[i] & 0xc0) != 0x80)
			return 0;
		cp = cp << 6 | (p[i] & 0x3f);
	}
	if ((n == 3 && cp < 0x800) || (n == 4 && cp < 0x10000) ||
	    cp > 0x10ffff || (cp >= 0xd800 && cp <= 0xdfff) ||
	    (cp >= 0x80 && cp <= 0x9f))	/* C1 controls: CSI is 0x9b */
		return 0;
	return n;
}

static void *xrealloc(void *, size_t);

/* -k: records held until the walk ends, each keyed by its node's stat;
 * name is column 6 as printed: the path, and on a -v line its indicator */
struct rec {
	uintmax_t ino, nlink, size;
	intmax_t mtime;
	size_t name, text, len;	/* offsets into ob: raw path, record bytes */
	size_t seq;		/* walk order, the last tie break */
};
static char *ob;
static size_t oblen, obcap;
static struct rec *rv;
static size_t nrv, caprv;

/* bytes to f, or to the record buffer when f is NULL */
static void
put(FILE *f, const void *p, size_t n)
{
	if (f != NULL) {
		(void)fwrite(p, 1, n, f);
		return;
	}
	while (oblen + n > obcap) {
		obcap = obcap ? obcap * 2 : 65536;
		ob = xrealloc(ob, obcap);
	}
	memcpy(ob + oblen, p, n);
	oblen += n;
}

/* a name, raw or with unsafe bytes as \ooo */
static void
putname(FILE *f, const char *s, int esc)
{
	const unsigned char *p = (const unsigned char *)s, *e;
	char o[5];
	size_t n;

	if (!esc) {
		put(f, s, strlen(s));
		return;
	}
	for (e = p + strlen(s); p < e; p += n)
		if ((n = u8len(p, e)) != 0)
			put(f, p, n);
		else {
			(void)snprintf(o, sizeof o, "\\%03o", *p);
			put(f, o, 4);
			n = 1;
		}
}

/*
 * Diagnostics, formatted as the shell chkerr (">>> ") and chkwrn ("^^^ ")
 * functions: "ff : what 'name'[: why] (tag)". The hex tag names the message;
 * usage messages and tags are identical in ff.fn.bash.
 */
static void
msg(const char *lvl, const char *what, const char *name, const char *why,
    const char *tag)
{
	/* stderr failure has nowhere else to go */
	(void)fprintf(stderr, "%s%s : %s", lvl, prog, what);
	if (name) {
		(void)fputs(" '", stderr);
		putname(stderr, name, esc_err);
		(void)fputc('\'', stderr);
	}
	if (why)
		(void)fprintf(stderr, ": %s", why);
	(void)fprintf(stderr, " (%s)\n", tag);
}
#define ERR(w, n, y, t) msg(">>> ", (w), (n), (y), (t))
#define WRN(w, n, y, t) msg("^^^ ", (w), (n), (y), (t))

static void
die(int st, const char *what, const char *name, const char *why, const char *tag)
{
	ERR(what, name, why, tag);
	exit(st);
}

/* usage error: status 1 before any walk */
static void
bad(const char *what, const char *arg, const char *tag)
{
	ERR(what, arg, NULL, tag);
	exit(ST_USAGE);
}

static void *
xrealloc(void *p, size_t n)
{
	if ((p = realloc(p, n ? n : 1)) == NULL)
		die(ST_ENV, "out of memory", NULL, NULL, "6ab7ff20");
	return p;
}

static char *
xstrdup(const char *s)
{
	size_t n = strlen(s) + 1;

	return memcpy(xrealloc(NULL, n), s, n);
}

static void
xflush(void)
{
	if (fflush(stdout) == EOF || ferror(stdout))
		die(ST_ENV, "write error on stdout", NULL, strerror(errno), "6ab7ff21");
}

/* ------------------------------------------------------------ expression */

enum {
	N_TRUE, N_AND, N_OR, N_NOT,
	N_NAME, N_PATH, N_REGEX, N_TYPE, N_SIZE, N_TIME, N_NEWER, N_PERM,
	N_USER, N_GROUP, N_EMPTY, N_LINKS, N_INUM, N_PRUNE, N_FALSE, N_SAME,
	N_PRINT, N_LS, N_EXEC, N_EXECDIR, N_DELETE, N_QUIT
};

struct batch {			/* pending {} + arguments */
	char **v;
	size_t n, cap, bytes;
	size_t level;		/* -x: directory level the names live in */
	unsigned long gen;	/* -x: that level's generation */
};

struct kq {			/* one -mode symbolic clause */
	int sign;		/* '+' has, '-' lacks */
	int any;		/* no class named: + holds for some class */
	int dir;		/* X: only a directory satisfies */
	mode_t bits[3];		/* per class u g o; 0 when not participating */
};

struct node {
	int type, l, r;
	int cmp;		/* '+', '-' or 0 */
	uintmax_t num, unit;	/* compared value; time unit in seconds */
	int tsel;		/* time: 'm' 'a' 'c' 'b' */
	unsigned tmask;		/* type letters */
	mode_t mode;		/* -mode octal */
	struct kq *kq;		/* -mode symbolic clauses, all must hold */
	int nkq;
	const char *pat;
	regex_t re;
	struct timespec ref;	/* -w file: reference mtime */
	int hexw;		/* -w HEX: num is epoch seconds, not ref */
	dev_t dev;		/* -y: reference device, inode in num */
	char **argv;		/* exec template, argc words */
	int argc, plus;
	struct batch b;
};

static struct node *nd;
static int nnd;
static char **tok;		/* expression tokens */
/* path operands; file scope, as tok, so the array stays reachable when
 * bad() or die() exits from inside the parser (LeakSanitizer reported it) */
static char **paths;
static int ntok, ti;
static int root = -1;
static size_t argmax;		/* bytes for one exec argument list */

static int
mk(int type, int l, int r)
{
	nd = xrealloc(nd, (size_t)(nnd + 1) * sizeof *nd);
	memset(&nd[nnd], 0, sizeof *nd);
	nd[nnd].type = type;
	nd[nnd].l = l;
	nd[nnd].r = r;
	return nnd++;
}

/* [+-]digits: sign to *cmp, value to *v; pointer past the digits or NULL */
static const char *
num(const char *s, int *cmp, uintmax_t *v)
{
	uintmax_t x = 0;

	*cmp = 0;
	if (*s == '+' || *s == '-')
		*cmp = *s++;
	if (*s < '0' || *s > '9')
		return NULL;
	for (; *s >= '0' && *s <= '9'; s++) {
		if (x > (UINTMAX_MAX - (uintmax_t)(*s - '0')) / 10)
			return NULL;
		x = x * 10 + (uintmax_t)(*s - '0');
	}
	*v = x;
	return s;
}

/* [+-]hex digits, 1-16 of them, no 0x: sign to *cmp, value to *v; 0 if not */
static int
hexnum(const char *s, int *cmp, uintmax_t *v)
{
	const char *d;
	uintmax_t x = 0;

	*cmp = 0;
	if (*s == '+' || *s == '-')
		*cmp = *s++;
	for (d = s; *s && strchr("0123456789abcdefABCDEF", *s); s++)
		x = x << 4 | (uintmax_t)(*s <= '9' ? *s - '0' : (*s | 040) - 'a' + 10);
	if (*s != '\0' || s == d || s - d > 16)
		return 0;
	*v = x;
	return 1;
}

/* unit suffix: at most one character from units, else error */
static uintmax_t
suffix(const char *p, const char *units, const uintmax_t *mult,
    uintmax_t dflt, const char *what, const char *arg, const char *tag)
{
	const char *u = NULL;

	if (*p == '\0')
		return dflt;
	if (p[1] != '\0' || (u = strchr(units, *p)) == NULL)
		bad(what, arg, tag);
	return mult[u - units];
}

static uintmax_t
mul(uintmax_t a, uintmax_t b, const char *what, const char *arg, const char *tag)
{
	if (b && a > UINTMAX_MAX / b)
		bad(what, arg, tag);
	return a * b;
}

/*
 * -mode: octal is exact, +N a superset (every bit, maybe more), -N a
 * subset (no bit outside, maybe fewer). Symbolic is a query, not chmod:
 * clauses [ugoa]*[+-]?[rwxXst]+ joined by commas; + has, - lacks, no sign
 * means +. Named classes must each satisfy a clause; with none, + holds
 * for some class and - for none. s is setuid (u) or setgid (g); t is the
 * sticky bit (o); X is x that only a directory satisfies.
 */
static void
parse_perm(struct node *n, const char *a)
{
	static const mode_t rwx[3][3] = {	/* r w x per class */
		{ 0400, 0200, 0100 }, { 040, 020, 010 }, { 04, 02, 01 } };
	static const mode_t sbit[3] = { 04000, 02000, 0 }, tbit[3] = { 0, 0, 01000 };
	const char *p = a, *d;
	unsigned who, c;
	struct kq *q;

	n->cmp = (*p == '+' || *p == '-') && p[1] >= '0' && p[1] <= '7' ? *p++ : 0;
	if (*p >= '0' && *p <= '7') {
		for (d = p; *p >= '0' && *p <= '7' && p - d < 4; p++)
			n->mode = (mode_t)(n->mode << 3 | (mode_t)(*p - '0'));
		if (*p != '\0')
			bad("-mode: bad mode", a, "6ab7ff11");
		return;
	}
	for (;;) {
		n->kq = xrealloc(n->kq, (size_t)(n->nkq + 1) * sizeof *n->kq);
		q = &n->kq[n->nkq++];
		memset(q, 0, sizeof *q);
		for (who = 0; *p && strchr("ugoa", *p); p++)
			who |= *p == 'u' ? 1 : *p == 'g' ? 2 : *p == 'o' ? 4 : 8;
		q->any = who == 0;
		q->sign = *p == '+' || *p == '-' ? *p++ : '+';
		if (!strchr("rwxXst", *p) || *p == '\0')
			bad("-mode: bad mode", a, "6ab7ff11");
		for (; *p && strchr("rwxXst", *p); p++)
			for (c = 0; c < 3; c++) {
				if (!(who & 8) && who && !(who & 1u << c))
					continue;
				if (*p == 's' || *p == 't') {
					/* named classes must each own the bit */
					if (who && !(who & 8) &&
					    !(*p == 's' ? sbit[c] : tbit[c]))
						bad("-mode: s is for u or g, t is for o, not",
						    a, "6ab7ff46");
					q->bits[c] |= *p == 's' ? sbit[c] : tbit[c];
				} else {
					q->bits[c] |= rwx[c][*p == 'r' ? 0 : *p == 'w' ? 1 : 2];
					q->dir |= *p == 'X';
				}
			}
		if (*p == '\0')
			break;
		if (*p++ != ',' || *p == '\0')
			bad("-mode: bad mode", a, "6ab7ff11");
	}
}

#if defined(__linux__)
/* id field of "getent passwd|group name": name:pw:id:... ; the host's own
 * dynamically linked getent consults NSS as configured, which this binary
 * may not. Exit 2 from getent is "no such key". */
static uintmax_t
getent_id(const char *db, const char *s, const char *what, const char *tag)
{
	static const char *const bin[] = { "/usr/bin/getent", "/bin/getent" };
	char buf[4096], *p, *av[5];
	const char *q;
	size_t n = 0, i, len = strlen(s);
	int pfd[2], st, cmp;
	uintmax_t v = 0;
	ssize_t r;
	pid_t pid;

	for (i = 0; i < sizeof bin / sizeof *bin && access(bin[i], X_OK); i++)
		;
	if (i == sizeof bin / sizeof *bin)
		die(ST_ENV, "no getent, use a numeric id for", s, NULL, "6ab7ff22");
	av[0] = (char *)"getent";
	av[1] = (char *)db;
	av[2] = (char *)"--";
	av[3] = (char *)s;
	av[4] = NULL;
	xflush();
	if (pipe(pfd) == -1)
		die(ST_ENV, "pipe", NULL, strerror(errno), "6ab7ff23");
	if ((pid = fork()) == -1)
		die(ST_ENV, "fork", NULL, strerror(errno), "6ab7ff24");
	if (pid == 0) {
		int nul = open("/dev/null", O_RDWR);

		(void)close(pfd[0]);
		if (dup2(pfd[1], 1) == -1 || (nul >= 0 && dup2(nul, 2) == -1))
			_exit(127);
		(void)execv(bin[i], av);
		_exit(127);
	}
	(void)close(pfd[1]);
	while (n < sizeof buf - 1 &&
	    ((r = read(pfd[0], buf + n, sizeof buf - 1 - n)) > 0 ||
	    (r == -1 && errno == EINTR)))
		n += r > 0 ? (size_t)r : 0;
	(void)close(pfd[0]);
	while (waitpid(pid, &st, 0) == -1)
		if (errno != EINTR)
			die(ST_ENV, "waitpid", NULL, strerror(errno), "6ab7ff25");
	buf[n] = '\0';
	if (WIFEXITED(st) && WEXITSTATUS(st) == 2)
		bad(what, s, tag);
	if (!WIFEXITED(st) || WEXITSTATUS(st) != 0)
		die(ST_ENV, "getent failed resolving", s, NULL, "6ab7ff26");
	/* first line must name s exactly, then two fields to the id */
	if (strncmp(buf, s, len) || buf[len] != ':' ||
	    (p = strchr(buf + len + 1, ':')) == NULL ||
	    (q = num(p + 1, &cmp, &v)) == NULL || cmp || *q != ':')
		die(ST_ENV, "unexpected getent output for", s, NULL, "6ab7ff27");
	return v;
}
#endif

static uintmax_t
parse_id(const char *s, int user)
{
	uintmax_t v;
	const char *p;
	int cmp;

	if ((p = num(s, &cmp, &v)) != NULL && *p == '\0' && cmp == 0)
		;
	else if (*s == '\0' || *s == '-' || strpbrk(s, ":\n"))
		bad(user ? "-u: no such user" : "-g: no such group", s,
		    user ? "6ab7ff12" : "6ab7ff13");
	else {
#if defined(__linux__)
		v = getent_id(user ? "passwd" : "group", s,
		    user ? "-u: no such user" : "-g: no such group",
		    user ? "6ab7ff12" : "6ab7ff13");
#else
		struct passwd *pw;
		struct group *gr;

		if (user) {
			if ((pw = getpwnam(s)) == NULL)
				bad("-u: no such user", s, "6ab7ff12");
			v = pw->pw_uid;
		} else {
			if ((gr = getgrnam(s)) == NULL)
				bad("-g: no such group", s, "6ab7ff13");
			v = gr->gr_gid;
		}
#endif
	}
	if (v > (user ? (uintmax_t)(uid_t)-1 : (uintmax_t)(gid_t)-1))
		bad(user ? "-u: id out of range" : "-g: id out of range", s,
		    user ? "6ab7ff14" : "6ab7ff15");
	return v;
}

static int
is_prim(const char *s, const char *list)
{
	char k[3] = { 0, 0, 0 };

	if (s[0] != '-' || s[1] == '\0' || s[2] != '\0')
		return 0;
	k[0] = s[1];
	return strstr(list, k) != NULL;
}

#define P_ARG  "nprtdsmacbwugliy"	/* primaries taking one argument */
#define P_NONE "ezfvq01"		/* primaries taking none; -0 true, -1 false */
#define P_EXEC "xj"			/* primaries taking cmd ... ; or + */

static int
takes_arg(const char *s)
{
	return is_prim(s, P_ARG) || !strcmp(s, "-mode");
}

static int
is_exprtok(const char *s)
{
	return !strcmp(s, "!") || !strcmp(s, "-not") || !strcmp(s, "(") || !strcmp(s, ")") ||
	    !strcmp(s, "-o") || !strcmp(s, "-delete") || takes_arg(s) ||
	    is_prim(s, P_NONE) || is_prim(s, P_EXEC);
}

static int parse_or(void);

static const char *
arg1(void)
{
	return tok[ti++];	/* presence checked by the pre-pass */
}

static int
primary(void)
{
	static const uintmax_t szm[] = { 1, 1024, 1024, 1048576, 1048576,
	    1073741824, 1073741824, 1099511627776ULL, 1099511627776ULL };
	static const uintmax_t tm[] = { 1, 60, 3600, 86400, 604800 };
	const char *t = tok[ti++], *a, *p;
	char tw[40];		/* time rule naming its primary */
	struct stat sb;
	uintmax_t v;
	int n, cmp, i, fl;

	if (!strcmp(t, "-delete")) {
		opt_D = 1;
		return mk(N_DELETE, -1, -1);
	}
	if (!strcmp(t, "-mode")) {
		n = mk(N_PERM, -1, -1);
		parse_perm(&nd[n], arg1());
		need_stat = 1;
		return n;
	}
	switch (t[1]) {
	case '0': case '1':	/* true, false */
		return mk(t[1] == '0' ? N_TRUE : N_FALSE, -1, -1);
	case 'y':		/* the same node: device and inode */
		n = mk(N_SAME, -1, -1);
		a = arg1();
		if ((opt_H || opt_L ? stat(a, &sb) : lstat(a, &sb)) == -1)
			bad("-y: cannot stat", a, "6ab7ff48");
		nd[n].dev = sb.st_dev;
		nd[n].num = (uintmax_t)sb.st_ino;
		need_stat = 1;
		return n;
	case 'n': case 'p':
		n = mk(t[1] == 'n' ? N_NAME : N_PATH, -1, -1);
		nd[n].pat = arg1();
		return n;
	case 'r':
		n = mk(N_REGEX, -1, -1);
		a = arg1();
		/* always ERE (r10): -E retired; -n and -p stay glob */
		fl = REG_NOSUB | REG_EXTENDED | (opt_I ? REG_ICASE : 0);
		if ((i = regcomp(&nd[n].re, a, fl)) != 0) {
			char m[128];

			(void)regerror(i, &nd[n].re, m, sizeof m);
			ERR("-r: bad regular expression", a, m, "6ab7ff09");
			exit(ST_USAGE);
		}
		return n;
	case 't':
		n = mk(N_TYPE, -1, -1);
		for (a = p = arg1(); *p; p++) {
			const char *q = strchr("fdlpsbc", *p);

			if (q == NULL)
				bad("-t: types are f d l p s b c, not", a, "6ab7ff0a");
			nd[n].tmask |= 1u << (q - "fdlpsbc");
		}
		if (*a == '\0')
			bad("-t: types are f d l p s b c, not", a, "6ab7ff0a");
		return n;
	case 'd': {
		long lo, hi;

		a = arg1();
		if ((p = num(a, &cmp, &v)) == NULL || *p || v > LONG_MAX - 1)
			bad("-d: depth is [+-]N, not", a, "6ab7ff0b");
		lo = cmp == '+' ? (long)v + 1 : cmp == '-' ? 0 : (long)v;
		hi = cmp == '-' ? (long)v - 1 : cmp == '+' ? LONG_MAX : (long)v;
		if (lo > mindepth)
			mindepth = lo;
		if (hi < maxdepth)
			maxdepth = hi;
		return mk(N_TRUE, -1, -1);
	}
	case 's':
		n = mk(N_SIZE, -1, -1);
		a = arg1();
		if ((p = num(a, &nd[n].cmp, &v)) == NULL)
			bad("-s: size is [+-]N[ckMGT], not", a, "6ab7ff0c");
		nd[n].num = mul(v, suffix(p, "ckKmMgGtT", szm, 1,
		    "-s: size is [+-]N[ckMGT], not", a, "6ab7ff0c"),
		    "-s: size overflows", a, "6ab7ff0d");
		need_stat = 1;
		return n;
	case 'm': case 'a': case 'c': case 'b':
		n = mk(N_TIME, -1, -1);
		nd[n].tsel = t[1];
		a = arg1();
		(void)snprintf(tw, sizeof tw, "-%c: time is [+-]N[smhdw], not", t[1]);
		if ((p = num(a, &nd[n].cmp, &v)) == NULL)
			bad(tw, a, "6ab7ff0e");
		nd[n].unit = suffix(p, "smhdw", tm, 86400, tw, a, "6ab7ff0e");
		nd[n].num = v;
		(void)mul(v, nd[n].unit, "time overflows", a, "6ab7ff0f");
		if (v * nd[n].unit > (uintmax_t)INTMAX_MAX)
			bad("time overflows", a, "6ab7ff0f");
		need_stat = 1;
		return n;
	case 'w':
		/* when: [+-][ ]([.][.]/file|HEX); a file begins with ./ ../ or /,
		 * so no word is both a file and a hex time. A lone sign word
		 * takes the next word, kept whole by the pre-pass; diagnostics
		 * then name that word. */
		n = mk(N_NEWER, -1, -1);
		a = arg1();
		nd[n].cmp = *a == '+' || *a == '-' ? *a : 0;
		p = a + (nd[n].cmp != 0);
		if (nd[n].cmp && *p == '\0')
			a = p = arg1();
		if (*p == '+' || *p == '-')	/* one sign only */
			bad("-w: file is [.][.]/file, time is HEX, not", a, "6ab7ff4b");
		if (*p == '/' || !strncmp(p, "./", 2) || !strncmp(p, "../", 3)) {
			if ((opt_H || opt_L ? stat(p, &sb) : lstat(p, &sb)) == -1)
				bad("-w: cannot stat", p, "6ab7ff10");
			nd[n].ref = MTIM(&sb);
		} else if (hexnum(p, &cmp, &nd[n].num)) {
			if (nd[n].num > (uintmax_t)INTMAX_MAX)
				bad("time overflows", a, "6ab7ff0f");
			nd[n].hexw = 1;
		} else
			bad("-w: file is [.][.]/file, time is HEX, not", a, "6ab7ff4b");
		need_stat = 1;
		return n;
	case 'u': case 'g':
		n = mk(t[1] == 'u' ? N_USER : N_GROUP, -1, -1);
		nd[n].num = parse_id(arg1(), t[1] == 'u');
		need_stat = 1;
		return n;
	case 'l':
		n = mk(N_LINKS, -1, -1);
		a = arg1();
		if ((p = num(a, &nd[n].cmp, &nd[n].num)) == NULL || *p)
			bad("-l: links is [+-]N, not", a, "6ab7ff16");
		need_stat = 1;
		return n;
	case 'i':	/* hex, as ff -v and cksh print the inode */
		n = mk(N_INUM, -1, -1);
		a = arg1();
		if (!hexnum(a, &nd[n].cmp, &nd[n].num))
			bad("-i: inode is [+-]HEX, not", a, "6ab7ff17");
		need_stat = 1;
		return n;
	case 'e':
		need_stat = 1;
		return mk(N_EMPTY, -1, -1);
	case 'z':
		return mk(N_PRUNE, -1, -1);
	case 'f':
		return mk(N_PRINT, -1, -1);
	case 'v':
		need_stat = 1;
		return mk(N_LS, -1, -1);
	case 'q':
		return mk(N_QUIT, -1, -1);
	case 'x': case 'j':
		n = mk(t[1] == 'x' ? N_EXECDIR : N_EXEC, -1, -1);
		nd[n].argv = &tok[ti];
		while (strcmp(tok[ti], ";") &&
		    !(!strcmp(tok[ti], "+") && !strcmp(tok[ti - 1], "{}")))
			ti++;
		nd[n].argc = (int)(&tok[ti] - nd[n].argv);
		nd[n].plus = tok[ti++][0] == '+';
		if (nd[n].argc == 0 || (nd[n].plus && nd[n].argc == 1))
			bad("missing command after", t, "6ab7ff18");
		for (i = 0; i < nd[n].argc; i++) {
			if (strstr(nd[n].argv[i], "{}") && strcmp(nd[n].argv[i], "{}"))
				bad("{} must be a whole argument, not", nd[n].argv[i], "6ab7ff19");
			if (nd[n].plus && i < nd[n].argc - 1 &&
			    !strcmp(nd[n].argv[i], "{}"))
				bad("with +, {} may appear only once, last, in", t, "6ab7ff1a");
			if (i == 0 && !strcmp(nd[n].argv[i], "{}"))
				bad("{} cannot be the command of", t, "6ab7ff1b");
		}
		if (t[1] == 'x' && strchr(nd[n].argv[0], '/') && nd[n].argv[0][0] != '/')
			bad("-x: command must be absolute or found in PATH, not", nd[n].argv[0], "6ab7ff1c");
		return n;
	}
	bad("unknown primary", t, "6ab7ff03");
	return -1;
}

static int
parse_not(void)
{
	int n;

	if (ti >= ntok)
		bad("expression ends early, after", ntok ? tok[ntok - 1] : NULL, "6ab7ff06");
	if (!strcmp(tok[ti], "!") || !strcmp(tok[ti], "-not")) {
		ti++;
		n = parse_not();
		return mk(N_NOT, n, -1);
	}
	if (!strcmp(tok[ti], "(")) {
		ti++;
		if (ti < ntok && !strcmp(tok[ti], ")"))
			bad("empty ( )", NULL, "6ab7ff07");
		n = parse_or();
		if (ti >= ntok || strcmp(tok[ti], ")"))
			bad("missing )", NULL, "6ab7ff08");
		ti++;
		return n;
	}
	if (!strcmp(tok[ti], ")") || !strcmp(tok[ti], "-o"))
		bad("unexpected", tok[ti], "6ab7ff05");
	return primary();
}

static int
parse_and(void)
{
	int l = parse_not();

	while (ti < ntok && strcmp(tok[ti], "-o") && strcmp(tok[ti], ")"))
		l = mk(N_AND, l, parse_not());
	return l;
}

static int
parse_or(void)
{
	int l = parse_and();

	while (ti < ntok && !strcmp(tok[ti], "-o")) {
		ti++;
		l = mk(N_OR, l, parse_and());
	}
	return l;
}

/* -x runs commands in walked directories: a relative PATH element would
 * let a file planted there run instead */
static void
check_path(void)
{
	const char *p = getenv("PATH"), *q;

	if (p == NULL || *p == '\0')
		die(ST_ENV, "-x: PATH is empty", NULL, NULL, "6ab7ff28");
	for (;;) {
		q = strchr(p, ':');
		if (*p != '/')
			die(ST_ENV, "-x: refusing a relative or empty element in PATH", getenv("PATH"), NULL, "6ab7ff29");
		if (q == NULL)
			break;
		p = q + 1;
	}
}

/* ------------------------------------------------------------------ walk */

struct ent {
	const char *path;	/* as printed */
	const char *base;	/* last component */
	size_t depth;
	int dtype;		/* DT_* hint when st is not loaded */
	int have_st, prune;
	struct stat st;
};

struct level {			/* one open directory of the walk */
	char *name;		/* component; the operand path at level 0 */
	dev_t dev;
	ino_t ino;
	int fd, follow;
	unsigned long gen;
};

static struct level *lv;
static size_t nlv, caplv;
static int nopen, fdcap = FDCAP;	/* fdcap shrinks under a low RLIMIT_NOFILE */
static unsigned long gens;
static dev_t rootdev;

static char *pb;		/* path buffer */
static size_t pblen, pbcap;

/* close the shallowest held descriptors, never levels keep-1 and keep */
static void
trim(size_t keep)
{
	size_t i;

	for (i = 0; nopen > fdcap && i + 1 < keep; i++)
		if (lv[i].fd >= 0) {
			(void)close(lv[i].fd);
			lv[i].fd = -1;
			nopen--;
		}
}

/* descriptor for level d, reopened from the nearest held ancestor and
 * verified by dev/ino: a directory renamed or swapped for a symlink since
 * it was listed is refused, not followed */
static int
ensure_fd(size_t d, const char *shown)
{
	struct level *L = &lv[d];
	struct stat sb;
	int pfd, fd;

	if (L->fd >= 0)
		return L->fd;
	pfd = d ? ensure_fd(d - 1, NULL) : AT_FDCWD;
	if (d && pfd < 0)
		return -1;
	L = &lv[d];
	if (shown == NULL)
		shown = L->name;
	fd = openat(pfd, L->name, O_RDONLY | O_DIRECTORY | O_CLOEXEC |
	    (L->follow ? 0 : O_NOFOLLOW));
	if (fd == -1) {
		ERR("cannot open", shown, strerror(errno), "6ab7ff30");
		status |= errno == ELOOP || errno == ENOTDIR ? ST_RACE : ST_NODE;
		return -1;
	}
	if (fstat(fd, &sb) == -1 || sb.st_dev != L->dev || sb.st_ino != L->ino) {
		(void)close(fd);
		ERR("changed during walk, skipped", shown, NULL, "6ab7ff31");
		status |= ST_RACE;
		return -1;
	}
	L->fd = fd;
	nopen++;
	trim(d);
	return fd;
}

/* stat an entry by the symlink policy; -1 after warning */
static int
load(struct ent *e)
{
	int follow = opt_L || (opt_H && e->depth == 0);
	int pfd = e->depth ? ensure_fd(e->depth - 1, NULL) : AT_FDCWD;
	const char *nm = e->depth ? e->base : e->path;

	if (e->have_st)
		return 0;
	if (pfd < 0 && e->depth)
		return -1;
	if (fstatat(pfd, nm, &e->st, follow ? 0 : AT_SYMLINK_NOFOLLOW) == -1) {
		int err = errno;

		if (!follow ||
		    fstatat(pfd, nm, &e->st, AT_SYMLINK_NOFOLLOW) == -1) {
			ERR("cannot stat", e->path, strerror(err), "6ab7ff32");
			status |= ST_NODE;
			return -1;
		}
		if (err == ELOOP) {	/* dangling is fine, a loop is reported */
			WRN("symlink loop", e->path, strerror(err), "6ab7ff33");
			status |= ST_LOOP;
		}
	}
	e->have_st = 1;
	return 0;
}

static int
etype(const struct ent *e)
{
	mode_t m = e->st.st_mode;

	if (!e->have_st)
		switch (e->dtype) {
		case DT_REG: return 'f';
		case DT_DIR: return 'd';
		case DT_LNK: return 'l';
		case DT_FIFO: return 'p';
		case DT_SOCK: return 's';
		case DT_BLK: return 'b';
		case DT_CHR: return 'c';
		default: return '?';
		}
	return S_ISREG(m) ? 'f' : S_ISDIR(m) ? 'd' : S_ISLNK(m) ? 'l' :
	    S_ISFIFO(m) ? 'p' : S_ISSOCK(m) ? 's' : S_ISBLK(m) ? 'b' :
	    S_ISCHR(m) ? 'c' : '?';
}

/* dirname and ./basename of an operand, for -x at depth 0 */
static void
split_operand(const char *path, char **dir, char **arg)
{
	char *d = xstrdup(path), *s;
	size_t n = strlen(d);

	while (n > 1 && d[n - 1] == '/')
		d[--n] = '\0';
	s = strrchr(d, '/');
	if (s == NULL || !strcmp(d, "/")) {
		*arg = xrealloc(NULL, n + 3);
		(void)snprintf(*arg, n + 3, "%s%s", strcmp(d, "/") ? "./" : "", d);
		free(d);
		*dir = xstrdup(s ? "/" : ".");
		return;
	}
	*arg = xrealloc(NULL, strlen(s + 1) + 3);
	(void)snprintf(*arg, strlen(s + 1) + 3, "./%s", s + 1);
	if (s == d)
		s[1] = '\0';
	else
		*s = '\0';
	*dir = d;
}

/* ------------------------------------------------------------------ exec */

/* fork and exec av; child enters dirfd or dir first. Returns the wait
 * status, or -1 when the command could not be run (reported here) */
static int
run(char *const *av, int dirfd, const char *dir)
{
	int pfd[2], st, err = 0;
	ssize_t r;
	pid_t pid;

	xflush();
	if (pipe(pfd) == -1)
		die(ST_ENV, "pipe", NULL, strerror(errno), "6ab7ff23");
	(void)fcntl(pfd[1], F_SETFD, FD_CLOEXEC);
	if ((pid = fork()) == -1)
		die(ST_ENV, "fork", NULL, strerror(errno), "6ab7ff24");
	if (pid == 0) {
		(void)close(pfd[0]);
		if ((dirfd >= 0 && fchdir(dirfd) == -1) ||
		    (dir && chdir(dir) == -1)) {
			err = errno;
			r = write(pfd[1], &err, sizeof err);
			_exit(126 + (int)(r & 0));
		}
		(void)execvp(av[0], av);
		err = errno;
		r = write(pfd[1], &err, sizeof err);
		_exit(127 + (int)(r & 0));
	}
	(void)close(pfd[1]);
	while ((r = read(pfd[0], &err, sizeof err)) == -1 && errno == EINTR)
		;
	(void)close(pfd[0]);
	while (waitpid(pid, &st, 0) == -1)
		if (errno != EINTR)
			die(ST_ENV, "waitpid", NULL, strerror(errno), "6ab7ff25");
	if (r == (ssize_t)sizeof err) {
		ERR("cannot execute", av[0], strerror(err), "6ab7ff34");
		status |= ST_EXEC;
		return -1;
	}
	return st;
}

static int
exited0(int st)
{
	return st != -1 && WIFEXITED(st) && WEXITSTATUS(st) == 0;
}

static void
flush_batch(struct node *n)
{
	struct batch *b = &n->b;
	char **av;
	size_t i;
	int fd = -1, st;

	if (b->n == 0)
		return;
	av = xrealloc(NULL, ((size_t)n->argc + b->n) * sizeof *av);
	for (i = 0; i < (size_t)n->argc - 1; i++)
		av[i] = n->argv[i];
	memcpy(av + i, b->v, b->n * sizeof *av);
	av[i + b->n] = NULL;
	if (n->type == N_EXECDIR)
		fd = ensure_fd(b->level, NULL);
	if (n->type == N_EXEC || fd >= 0) {
		st = run(av, fd, NULL);
		if (st != -1 && !exited0(st))
			status |= ST_EXEC;
	}
	for (i = 0; i < b->n; i++)
		free(b->v[i]);
	free(av);
	b->n = b->bytes = 0;
}

static void
flush_all(int execdir_level_only, size_t level)
{
	int i;

	for (i = 0; i < nnd; i++)
		if ((nd[i].type == N_EXEC || nd[i].type == N_EXECDIR) &&
		    nd[i].plus && (!execdir_level_only ||
		    (nd[i].type == N_EXECDIR && nd[i].b.level == level)))
			flush_batch(&nd[i]);
}

static int
do_exec(struct node *n, struct ent *e)
{
	char **av, *arg, *dir = NULL;
	struct batch *b = &n->b;
	size_t sz;
	int i, st, fd = -1;

	if (n->type == N_EXEC)
		arg = xstrdup(e->path);
	else if (e->depth == 0)
		split_operand(e->path, &dir, &arg);
	else {
		sz = strlen(e->base) + 3;
		arg = xrealloc(NULL, sz);
		(void)snprintf(arg, sz, "./%s", e->base);
	}
	if (n->plus && dir == NULL) {
		sz = strlen(arg) + 1 + sizeof(char *);
		if (b->n && (b->bytes + sz > argmax || (n->type == N_EXECDIR &&
		    (b->level != e->depth - 1 || b->gen != lv[e->depth - 1].gen))))
			flush_batch(n);
		if (b->n == b->cap) {
			b->cap = b->cap ? b->cap * 2 : 64;
			b->v = xrealloc(b->v, b->cap * sizeof *b->v);
		}
		if (n->type == N_EXECDIR) {
			b->level = e->depth - 1;
			b->gen = lv[b->level].gen;
		}
		b->v[b->n++] = arg;
		b->bytes += sz;
		return 1;
	}
	av = xrealloc(NULL, ((size_t)n->argc + 1) * sizeof *av);
	for (i = 0; i < n->argc; i++)
		av[i] = strcmp(n->argv[i], "{}") ? n->argv[i] : arg;
	av[i] = NULL;
	if (n->type == N_EXECDIR && e->depth)
		fd = ensure_fd(e->depth - 1, NULL);
	st = n->type == N_EXECDIR && e->depth && fd < 0 ? -1 : run(av, fd, dir);
	if (n->plus && st != -1 && !exited0(st))
		status |= ST_EXEC;
	free(av);
	free(arg);
	free(dir);
	return n->plus ? 1 : exited0(st);
}

/* ------------------------------------------------------------ predicates */

static int
p_perm(struct node *n, struct ent *e)
{
	mode_t m = e->st.st_mode & 07777, all;
	struct kq *q;
	int i, c, some;

	if (n->kq == NULL)
		return n->cmp == '+' ? (m & n->mode) == n->mode :
		    n->cmp == '-' ? (m & ~n->mode) == 0 : m == n->mode;
	for (i = 0; i < n->nkq; i++) {
		q = &n->kq[i];
		if (q->dir && !S_ISDIR(e->st.st_mode))
			return 0;
		all = q->bits[0] | q->bits[1] | q->bits[2];
		if (q->sign == '-') {
			if (m & all)
				return 0;
		} else if (!q->any) {
			if ((m & all) != all)
				return 0;
		} else {
			/* some participating class has every one of its bits */
			for (c = some = 0; c < 3 && !some; c++)
				some = q->bits[c] && (m & q->bits[c]) == q->bits[c];
			if (!some)
				return 0;
		}
	}
	return 1;
}

static int
cmpnum(int cmp, uintmax_t have, uintmax_t want)
{
	return cmp == '+' ? have > want : cmp == '-' ? have < want : have == want;
}

static int
p_time(struct node *n, struct ent *e)
{
	intmax_t age, t;
#if !(defined(__APPLE__) || defined(__NetBSD__) || defined(__FreeBSD__))
	static int warned_btime;	/* -b cannot be answered: warn once */
#endif

	if (n->tsel == 'm')
		t = e->st.st_mtime;
	else if (n->tsel == 'a')
		t = e->st.st_atime;
	else if (n->tsel == 'c')
		t = e->st.st_ctime;
	else {
#if defined(__APPLE__) || defined(__NetBSD__) || defined(__FreeBSD__)
		t = e->st.st_birthtime;
		if (t <= 0)
			return 0;
#elif defined(__linux__) && defined(STATX_BTIME)
		struct statx sx;
		int pfd = e->depth ? ensure_fd(e->depth - 1, NULL) : AT_FDCWD;

		if (pfd < 0 && e->depth)
			return 0;
		if (statx(pfd, e->depth ? e->base : e->path,
		    opt_L || (opt_H && !e->depth) ? 0 : AT_SYMLINK_NOFOLLOW,
		    STATX_BTIME, &sx) == -1 || !(sx.stx_mask & STATX_BTIME)) {
			if (!warned_btime++)
				WRN("birth time unavailable, -b is false", e->path, NULL, "6ab7ff35");
			return 0;
		}
		t = sx.stx_btime.tv_sec;
#else
		if (!warned_btime++)
			WRN("birth time unsupported on this platform", NULL, NULL, "6ab7ff36");
		return 0;
#endif
	}
	age = (intmax_t)now - t;
	if (n->cmp == '+')
		return age > (intmax_t)(n->num * n->unit);
	if (n->cmp == '-')
		return age < (intmax_t)(n->num * n->unit);
	return age >= 0 && (uintmax_t)age / n->unit == n->num;
}

static int
p_empty(struct ent *e)
{
	struct dirent *de;
	struct stat sb;
	DIR *dp;
	int fd, pfd, r = 1;

	if (etype(e) == 'f')
		return e->st.st_size == 0;
	if (etype(e) != 'd')
		return 0;
	pfd = e->depth ? ensure_fd(e->depth - 1, NULL) : AT_FDCWD;
	if (pfd < 0 && e->depth)
		return 0;
	fd = openat(pfd, e->depth ? e->base : e->path, O_RDONLY | O_DIRECTORY |
	    O_CLOEXEC | (opt_L || (opt_H && !e->depth) ? 0 : O_NOFOLLOW));
	if (fd == -1) {
		ERR("cannot open", e->path, strerror(errno), "6ab7ff30");
		status |= ST_NODE;
		return 0;
	}
	if (fstat(fd, &sb) == -1 || sb.st_dev != e->st.st_dev ||
	    sb.st_ino != e->st.st_ino || (dp = fdopendir(fd)) == NULL) {
		(void)close(fd);
		ERR("changed during walk, skipped", e->path, NULL, "6ab7ff31");
		status |= ST_RACE;
		return 0;
	}
	while ((de = readdir(dp)) != NULL)
		if (strcmp(de->d_name, ".") && strcmp(de->d_name, "..")) {
			r = 0;
			break;
		}
	(void)closedir(dp);
	return r;
}

static int
p_delete(struct ent *e)
{
	struct stat sb;
	const char *b = e->base;

	if (e->depth == 0) {
		/* find skips . silently; .. and / never get here, their
		 * operands were refused whole (refuse_operand) */
		if (!strcmp(b, "."))
			return 1;
		if (lstat(e->path, &sb) == -1 ||
		    unlinkat(AT_FDCWD, e->path, S_ISDIR(sb.st_mode) ? AT_REMOVEDIR : 0)) {
			ERR("cannot delete", e->path, strerror(errno), "6ab7ff38");
			status |= ST_NODE;
			return 0;
		}
		return 1;
	}
	if (ensure_fd(e->depth - 1, NULL) < 0)
		return 0;
	if (unlinkat(lv[e->depth - 1].fd, b, etype(e) == 'd' ? AT_REMOVEDIR : 0)) {
		ERR("cannot delete", e->path, strerror(errno), "6ab7ff38");
		status |= ST_NODE;
		return 0;
	}
	return 1;
}

/* where a record goes: stdout, or under -k a new held record. ind is the
 * -v indicator: column 6 is the name as printed, so it joins the key */
static FILE *
rec_open(struct ent *e, const char *ind)
{
	struct rec *r;

	if (!opt_k)
		return stdout;
	if (nrv == caprv) {
		caprv = caprv ? caprv * 2 : 1024;
		rv = xrealloc(rv, caprv * sizeof *rv);
	}
	r = &rv[nrv];
	r->ino = (uintmax_t)e->st.st_ino;
	r->nlink = (uintmax_t)e->st.st_nlink;
	r->size = (uintmax_t)e->st.st_size;
	r->mtime = (intmax_t)e->st.st_mtime;
	r->name = oblen;
	put(NULL, e->path, strlen(e->path));
	put(NULL, ind, strlen(ind) + 1);
	r->text = oblen;
	r->seq = nrv;
	return NULL;
}

static void
rec_close(void)
{
	if (opt_k) {
		rv[nrv].len = oblen - rv[nrv].text;
		nrv++;
	}
}

/* every record ends in newline, or under -Z in NUL; -Z names are raw */
static void
p_print(struct ent *e)
{
	FILE *f = rec_open(e, "");

	putname(f, e->path, esc_out && !opt_Z);
	put(f, opt_Z ? "" : "\n", 1);
	rec_close();
}

/* the cksh line: a negative mdate is signed hex, as cksh writes it, so
 * srt -x orders it before 0 */
static void
p_ls(struct ent *e)
{
	int t = etype(e);
	const char *ind = t == 'd' ? "/" : t == 'l' ? "@" : t == 'p' ? "|" :
	    t == 's' ? "=" : "";
	FILE *f = rec_open(e, ind);
	intmax_t mt = (intmax_t)e->st.st_mtime;
	char b[96], m[24];

	if (mt < 0)
		(void)snprintf(m, sizeof m, "-%07jx", (uintmax_t)(-(mt + 1)) + 1);
	else
		(void)snprintf(m, sizeof m, "%08jx", (uintmax_t)mt);
	(void)snprintf(b, sizeof b, "%8jx %2jx . %8jx %s ",
	    (uintmax_t)e->st.st_ino, (uintmax_t)e->st.st_nlink,
	    (uintmax_t)e->st.st_size, m);
	put(f, b, strlen(b));
	putname(f, e->path, esc_out && !opt_Z);
	put(f, ind, strlen(ind));
	put(f, opt_Z ? "" : "\n", 1);
	rec_close();
}

/* ---- sort: the named columns, then the rest left to right ------------- */

static int
cmp_col(const struct rec *x, const struct rec *y, int j)
{
	switch (j) {
	case 1: return (x->ino > y->ino) - (x->ino < y->ino);
	case 2: return (x->nlink > y->nlink) - (x->nlink < y->nlink);
	case 4: return (x->size > y->size) - (x->size < y->size);
	case 5: return (x->mtime > y->mtime) - (x->mtime < y->mtime);
	case 6: return strcmp(ob + x->name, ob + y->name);
	}
	return 0;	/* 3: a dot in every record, a null column */
}

static int
cmp_rec(const void *a, const void *b)
{
	const struct rec *x = a, *y = b;
	int i, c;

	for (i = 0; i < NCOL; i++) {
		c = cmp_col(x, y, ord[i]);
		if (c)
			return rev[i] ? -c : c;
	}
	return (x->seq > y->seq) - (x->seq < y->seq);	/* stable, as srt */
}

/*
 * Resolve -k into ord[] and rev[]. Named columns first, in the order
 * given, then the columns not named, left to right, ascending; a bare
 * -k names none, and then the name leads.
 */
static void
resolve(void)
{
	int seen[NCOL + 1] = { 0 }, i, j, n = 0;

	for (i = 0; i < nk; i++) {
		ord[n] = kcol[i];
		rev[n++] = krev[i];
		seen[kcol[i]] = 1;
	}
	if (nk == 0) {
		ord[n] = 6;
		rev[n++] = 0;
		seen[6] = 1;
	}
	for (j = 1; j <= NCOL; j++)
		if (!seen[j]) {
			ord[n] = j;
			rev[n++] = 0;
		}
}

static void
rec_flush(void)
{
	size_t i;

	if (nrv > 1) {
		resolve();
		qsort(rv, nrv, sizeof *rv, cmp_rec);
	}
	for (i = 0; i < nrv; i++)
		put(stdout, ob + rv[i].text, rv[i].len);
}

static int
eval(int i, struct ent *e)
{
	struct node *n = &nd[i];
	int f;

	switch (n->type) {
	case N_TRUE: return 1;
	case N_AND: return eval(n->l, e) && !quitting && eval(n->r, e);
	case N_OR: return eval(n->l, e) || (!quitting && eval(n->r, e));
	case N_NOT: return !eval(n->l, e);
	case N_NAME: case N_PATH:
		f = opt_I ? FNM_CASEFOLD : 0;
		return fnmatch(n->pat, n->type == N_NAME ? e->base : e->path, f) == 0;
	case N_REGEX: return regexec(&n->re, e->path, 0, NULL, 0) == 0;
	case N_TYPE:
		f = etype(e);
		return f != '?' && (n->tmask >> (strchr("fdlpsbc", f) - "fdlpsbc") & 1);
	case N_SIZE: return cmpnum(n->cmp, (uintmax_t)e->st.st_size, n->num);
	case N_TIME: return p_time(n, e);
	case N_NEWER:
		/* HEX compares whole seconds, a file the full timestamp */
		f = n->hexw ? ((intmax_t)MTIM(&e->st).tv_sec > (intmax_t)n->num) -
		    ((intmax_t)MTIM(&e->st).tv_sec < (intmax_t)n->num) :
		    MTIM(&e->st).tv_sec != n->ref.tv_sec ?
		    (MTIM(&e->st).tv_sec > n->ref.tv_sec ? 1 : -1) :
		    (MTIM(&e->st).tv_nsec > n->ref.tv_nsec) -
		    (MTIM(&e->st).tv_nsec < n->ref.tv_nsec);
		return n->cmp == '+' ? f > 0 : n->cmp == '-' ? f < 0 : f == 0;
	case N_FALSE: return 0;
	case N_SAME:
		return e->st.st_dev == n->dev && (uintmax_t)e->st.st_ino == n->num;
	case N_PERM: return p_perm(n, e);
	case N_USER: return (uintmax_t)e->st.st_uid == n->num;
	case N_GROUP: return (uintmax_t)e->st.st_gid == n->num;
	case N_EMPTY: return p_empty(e);
	case N_LINKS: return cmpnum(n->cmp, (uintmax_t)e->st.st_nlink, n->num);
	case N_INUM: return cmpnum(n->cmp, (uintmax_t)e->st.st_ino, n->num);
	case N_PRUNE: e->prune = 1; return 1;
	case N_PRINT: p_print(e); return 1;
	case N_LS: p_ls(e); return 1;
	case N_EXEC: case N_EXECDIR: return do_exec(n, e);
	case N_DELETE: return p_delete(e);
	case N_QUIT: quitting = 1; return 1;
	}
	return 0;
}

/* ---------------------------------------------------------------- walker */

static const char *sortbase;

static int
cmp_off(const void *a, const void *b)
{
	return strcmp(sortbase + *(const size_t *)a, sortbase + *(const size_t *)b);
}

static void visit(struct ent *e);

static void
walk_dir(struct ent *e)
{
	size_t d = e->depth, i, n = 0, capn = 0, blen = 0, bcap = 0, old;
	size_t *off = NULL, len;
	unsigned char *typ = NULL;
	char *buf = NULL;
	struct dirent *de;
	struct ent c;
	DIR *dp;
	int fd, dfd;

	if (d + 1 > caplv) {
		caplv = caplv ? caplv * 2 : 32;
		lv = xrealloc(lv, caplv * sizeof *lv);
	}
	lv[d].name = xstrdup(d ? e->base : e->path);
	lv[d].dev = e->st.st_dev;
	lv[d].ino = e->st.st_ino;
	lv[d].fd = -1;
	lv[d].follow = opt_L || (opt_H && d == 0);
	lv[d].gen = ++gens;
	nlv = d + 1;
	if ((fd = ensure_fd(d, e->path)) < 0) {
		free(lv[d].name);
		nlv = d;
		return;
	}
	/* list everything first: the directory stays consistent for -S and
	 * the walk never holds a DIR stream across recursion */
	if ((dfd = fcntl(fd, F_DUPFD_CLOEXEC, 0)) == -1 ||
	    (dp = fdopendir(dfd)) == NULL) {
		ERR("cannot read", e->path, strerror(errno), "6ab7ff39");
		status |= ST_NODE;
		goto done;
	}
	for (errno = 0; (de = readdir(dp)) != NULL; errno = 0) {
		if (!strcmp(de->d_name, ".") || !strcmp(de->d_name, ".."))
			continue;
		len = strlen(de->d_name) + 1;
		while (blen + len > bcap) {
			bcap = bcap ? bcap * 2 : 4096;
			buf = xrealloc(buf, bcap);
		}
		if (n == capn) {
			capn = capn ? capn * 2 : 64;
			off = xrealloc(off, capn * sizeof *off);
			typ = xrealloc(typ, capn);
		}
		memcpy(buf + blen, de->d_name, len);
		off[n] = blen;
		typ[n] = de->d_type;
		n++;
		blen += len;
	}
	if (errno) {
		ERR("cannot read", e->path, strerror(errno), "6ab7ff39");
		status |= ST_NODE;
	}
	(void)closedir(dp);
	if (opt_S && n > 1) {
		unsigned char *t2 = xrealloc(NULL, bcap ? bcap : 1);

		/* sort offsets; carry types through a name-indexed scratch */
		for (i = 0; i < n; i++)
			t2[off[i]] = typ[i];
		sortbase = buf;
		qsort(off, n, sizeof *off, cmp_off);
		for (i = 0; i < n; i++)
			typ[i] = t2[off[i]];
		free(t2);
	}
	for (i = 0; i < n && !quitting; i++) {
		old = pblen;
		len = strlen(buf + off[i]);
		while (pblen + len + 2 > pbcap) {
			pbcap *= 2;
			pb = xrealloc(pb, pbcap);
		}
		if (pblen == 0 || pb[pblen - 1] != '/')
			pb[pblen++] = '/';
		memcpy(pb + pblen, buf + off[i], len + 1);
		memset(&c, 0, sizeof c);
		c.path = pb;
		c.base = pb + pblen;
		pblen += len;
		c.depth = d + 1;
		c.dtype = typ[i];
		if (need_stat || opt_X || c.dtype == DT_DIR ||
		    c.dtype == DT_UNKNOWN || (opt_L && c.dtype == DT_LNK))
			if (load(&c) == -1) {
				pblen = old;
				pb[pblen] = '\0';
				continue;
			}
		visit(&c);
		pblen = old;
		pb[pblen] = '\0';
	}
done:
	flush_all(1, d);
	free(buf);
	free(off);
	free(typ);
	if (lv[d].fd >= 0) {
		(void)close(lv[d].fd);
		nopen--;
	}
	free(lv[d].name);
	nlv = d;
}

static void
visit(struct ent *e)
{
	long dp = (long)e->depth;
	int in = dp >= mindepth && dp <= maxdepth;
	size_t i;

	/* a directory that is its own ancestor closes a loop (-L, bind
	 * mounts): reported and skipped, not tested, as fts FTS_DC in find */
	if (e->have_st && S_ISDIR(e->st.st_mode))
		for (i = 0; i < e->depth && i < nlv; i++)
			if (lv[i].dev == e->st.st_dev && lv[i].ino == e->st.st_ino) {
				WRN("filesystem loop, skipped", e->path, NULL, "6ab7ff3a");
				status |= ST_LOOP;
				return;
			}

	if (!opt_D && in)
		(void)eval(root, e);
	if (quitting)
		return;
	if (e->have_st && S_ISDIR(e->st.st_mode) && !e->prune &&
	    dp < maxdepth && !(opt_X && e->st.st_dev != rootdev)) {
		size_t bo = (size_t)(e->base - e->path);

		walk_dir(e);	/* pb may have moved */
		if (e->depth)
			e->base = pb + bo;
		e->path = pb;
	}
	if (opt_D && in && !quitting)
		(void)eval(root, e);
}

/*
 * -delete refuses an operand whole, before any walk below it: one whose last
 * component is .., or the root directory by identity (/ // /. /usr/.., or .
 * run from /; with -H a symlink to /). Refusing only the node, as find does,
 * would still empty it in post-order.
 */
static int
refuse_operand(const char *path, const char *base)
{
	struct stat sb, rs;

	if (!strcmp(base, ".."))
		return 1;
	return (opt_H ? stat(path, &sb) : lstat(path, &sb)) == 0 &&
	    stat("/", &rs) == 0 && sb.st_dev == rs.st_dev && sb.st_ino == rs.st_ino;
}

static void
walk_operand(const char *path)
{
	struct ent e;
	char *base, *s;
	size_t n;

	/* basename as find reports it: trailing slashes ignored */
	base = xstrdup(path);
	for (n = strlen(base); n > 1 && base[n - 1] == '/'; )
		base[--n] = '\0';
	s = strrchr(base, '/');
	memset(&e, 0, sizeof e);
	e.base = s && s[1] ? s + 1 : base;
	if (deleting && refuse_operand(path, e.base)) {
		ERR("refusing to delete", path, NULL, "6ab7ff37");
		status |= ST_NODE;
		free(base);
		return;
	}
	n = strlen(path);
	if (n + 2 > pbcap) {
		pbcap = n + 256;
		pb = xrealloc(pb, pbcap);
	}
	memcpy(pb, path, n + 1);
	pblen = n;
	e.path = pb;
	if (load(&e) == 0) {
		rootdev = e.st.st_dev;
		visit(&e);
	}
	free(base);
}

/* ------------------------------------------------------------------ help */

static const char usage_text[] =
"Usage: ff [-IHLDSXZV] [-k [col[r][,col[r]]...]] [--] [path ...] [expression]\n"
"       ff -h | --help | --man | --version   (--fn | --bin: --help)\n"
"  options  -I ignore case for -n -p -r  -H/-L follow symlinks\n"
"           -D post-order  -S sorted  -X one filesystem  -Z NUL records\n"
"           -V show the native find command (ff.fn.bash)\n"
"  sort     -k5,4 by column 5, then 4, then the remaining columns in\n"
"           order; columns as -v writes them: 1 inode 2 links 3 .\n"
"           4 size 5 mdate 6 name; no -v needed.  -k alone: by name\n"
"           -k5r  r reverses that column\n"
"  tests    -n glob  -p glob  -r ERE  -t fdlpsbc  -d [+-]N  -s [+-]N[ckMGT]\n"
"           -m -a -c -b [+-]N[smhdw]  -w [+-][ ]([.][.]/file|HEX)\n"
"           -u user  -g group  -l [+-]N  -i [+-]HEX  -y file (same node)  -e\n"
"           -mode [+-]bits  -z (prune)  -0 (true)  -1 (false)\n"
"  actions  -f print  -v cksh line  -x cmd {} ;|+  (in entry's dir)\n"
"           -j cmd {} ;|+  (full path)  -delete  -q quit\n"
"  logic    ( )  ! or -not  juxtaposition = and  -o or\n"
"  -h this summary, --help the manual\n";

/* chunks below the C99 4095 byte literal limit, joined on output */
static const char *const manual[] = {
"NAME\n"
"\n"
"    ff - functional find: walk file trees, one letter per switch\n"
"\n"
"SYNOPSIS\n"
"\n"
"    ff [-IHLDSXZV] [-k [col[r][,col[r]]...]] [--] [path ...] [expression]\n"
"    ff -h | --help | --man | --version\n"
"    ff --fn ... | ff --bin ...\n"
"\n"
"DESCRIPTION\n"
"\n"
"    ff walks each path (default .) and evaluates the expression for every\n"
"    node, as find(1) does, with one letter per switch. Options are\n"
"    uppercase, and -k, and global; they may appear anywhere except as\n"
"    the argument of a primary. Primaries are lowercase, the digits 0 and\n"
"    1, or -mode and -delete. With no action in the expression, each node\n"
"    for which it is true is printed.\n"
"\n"
"    Printed paths are the operand, then / and each name below it. Output\n"
"    is raw bytes when stdout is not a terminal or -Z is given. On a\n"
"    terminal, C0 and C1 control characters, DEL and bytes that are not\n"
"    valid UTF-8 print as \\ooo octal escapes, so a crafted name cannot\n"
"    drive the terminal; names in diagnostics follow the same rule.\n"
"\n"
"    Directories are opened relative to their verified parent descriptor,\n"
"    never by re-resolving a path; a directory swapped for another node\n"
"    between listing and opening is reported and skipped.\n"
"\n"
"OPTIONS\n"
"\n"
"    -I     case-insensitive -n, -p and -r\n"
"    -H     follow symlinks named as path operands\n"
"    -L     follow all symlinks; loops are reported, not followed\n"
"    -D     post-order: a directory is tested after its contents\n"
"    -S     sorted walk: each directory's names in bytewise order\n"
"    -X     do not descend into directories on other filesystems\n"
"    -Z, --zero-terminated\n"
"           end every record with NUL, not newline: the names from -f\n"
"           and the default print, and the lines of -v. Names are then\n"
"           written as they are, even to a terminal. It is the -Z of\n"
"           cksh and of srt.\n"
"    -k [col[r][,col[r]]...]\n"
"           sort what ff prints, by the columns of the -v line. See\n"
"           KEYS.\n"
"    --     end of options: following words are paths, even with a\n"
"           leading -, until a primary or operator\n"
"    -V     ff.fn.bash only: print the native find command to stderr\n"
"           before running it; helpful to extend a command to an OS find\n"
"           specific implementation. The binary notes this and runs.\n"
"           Given to the function, -V keeps the function, as --fn does.\n"
"    -h     short usage\n"
"    --help this manual. When standard output is a terminal it is shown\n"
"           as a man page, with its headings in bold, through the\n"
"           formatter of the host: mandoc, else nroff with a pager\n"
"           (PAGER, else less, else more). Where neither is found the\n"
"           text is shown through the pager alone. To a pipe or a file\n"
"           it is written plain.\n"
"    --man  the manual as man page source; ff.1 is this output\n"
"    --version\n"
"           print the revision\n"
"    --fn, --bin\n"
"           choose between the two forms of ff, the binary and the bash\n"
"           function. --fn allows only the function: it then never hands\n"
"           over to a binary, and the binary, given --fn, stops with an\n"
"           error. --bin allows only the binary: the function hands over\n"
"           to the binary on PATH and stops with an error if there is\n"
"           none; the binary accepts --bin and does nothing. See BASH\n"
"           FUNCTION.\n"
"\n"
"    The list of -k may be joined to it (-k5,4) or be the next word\n"
"    (-k 5,4). The next word is taken as the list only when it reads as\n"
"    one, a column number first; any other word leaves -k alone, which\n"
"    sorts by name, so\n"
"        ff -k .        ff -k src -t f        ff . -t f -k\n"
"    sort by name. For a path named like a list, write ./5. A word that\n"
"    begins with - is never the list: in -k -1 the -1 is the primary.\n"
"    -k may end a group of options, -Sk5 or -Zk.\n"
"\n"
"    Retired: -krN (write -kNr).\n"
"\n"
"KEYS\n"
"\n"
,
"    The columns are those of the -v line, counted as words, as $1, $2\n"
"    ... are in awk:\n"
"\n"
"           inode lk hash     size    mdate name\n"
"          1cc01d  1 .           3 5e0bd2c0 t/a\n"
"          1cc01c  2 .        1000 5e0bd2c0 t/d/\n"
"          1cc01f  1 .           1 5e0bd2c0 t/l@\n"
"\n"
"    The heading is shown for reference; ff does not write it.\n"
"\n"
"      1 inode  inode number\n"
"      2 lk     hard link count\n"
"      3 hash   a dot: ff reads no file. cksh writes its hash here,\n"
"               shake256-N of the content, shake256-6 unless told\n"
"               otherwise; ff keeps the column so that the two agree\n"
"               on where each of the others is\n"
"      4 size   size in bytes\n"
"      5 mdate  modification time in seconds since the epoch; a time\n"
"               before 1970 is written with a minus sign, -12cf8700\n"
"      6 name   the path, and on a -v line an indicator in the manner\n"
"               of ls -F: / directory  @ symlink  | fifo  = socket\n"
"\n"
"    Numbers are lowercase hexadecimal. Widths are not significant: a\n"
"    value wider than its column moves the rest of that line and\n"
"    nothing else. The name begins at column 6 and runs to the end of\n"
"    the record, blanks included:\n"
"        awk '{print substr($0, index($0,$6))}'\n"
"\n"
"    -k [col[r][,col[r]]...]\n"
"        Sort by the named columns in the order given, then by the\n"
"        remaining columns left to right. -k5,4 compares in column\n"
"        order 5,4,1,2,3,6. -k5 -k4 is the same as -k5,4. Naming a\n"
"        column twice is an error. Columns are 1 to 6; counting from\n"
"        the end (-k-1) is not accepted.\n"
"\n"
"        -k with no list names no column, and sorts by name: column\n"
"        6, then 1 to 5.\n"
"\n"
"        The columns need not be printed. Every record, from -f, -v\n"
"        or the default print, is keyed by the stat of its node, so\n"
"        ff -k5 orders bare names by time, as ls -t orders names\n"
"        without -l. -v is needed only to see the columns.\n"
"\n"
"        ff knows the type of each column. Inode, links, size and\n"
"        mdate compare as numbers, by value, whatever their width.\n"
"        The name compares as bytes, as it is printed, to the end of\n"
"        the record, and no locale is consulted. Column 3 is a dot in\n"
"        every record, a null column: it compares equal, so a key on\n"
"        it orders nothing and the next column decides.\n"
"\n"
"        Records equal in every column keep the order of the walk.\n"
"\n"
"        Records are held until the walk ends. What -x and -j\n"
"        commands write is not sorted, and after -q the records\n"
"        printed so far are.\n"
"\n"
"    Letters. r after a column reverses that column. x is accepted\n"
"    on columns 1, 2, 4 and 5 and changes nothing: it is the letter\n"
"    srt needs there, so a list written for srt can be given to ff.\n"
"    Any other letter is refused, since the types are fixed. No\n"
"    option reverses every column, -r being a primary: write r on\n"
"    each column to be reversed.\n"
"        ff -k5r          newest first; within one second, ascending\n"
"        ff -k5r,4r,6r    newest first, then largest, then name down\n"
"\n"
"    The same order from srt. ff -k5,4,6 . -v writes what\n"
"        ff . -v | srt -k5x,4x,6,1x,2x,3\n"
"    writes: every column named, each numeric column marked x, the\n"
"    dot and the name as text. In general, give srt the ff list, then\n"
"    the remaining columns, with x on 1, 2, 4 and 5.\n"
"\n"
"PRIMARIES\n"
"\n"
"    N           decimal: +N more than N, -N less than N, N exactly.\n"
"    HEX         hexadecimal without 0x, as ff -v prints it.\n"
"    -n glob     last component of the examined pathname matches glob\n"
"    -p glob     examined pathname matches glob\n"
"                The special shell pattern characters [ ] * and ? may be\n"
"                used, and \\ makes the next one literal. A leading . is\n"
"                not special, and in -p * and ? also match /. Quote the\n"
,
"                pattern so the shell does not expand it first.\n"
"    -r ere      path contains a match for the extended regular expression\n"
"                ere; unanchored, add ^ and $. See REGULAR EXPRESSIONS.\n"
"    -t types    type is any of: f file, d directory, l symlink, p fifo,\n"
"                s socket, b block, c character device; -t fl is f or l\n"
"    -d N        walk bound, global wherever it appears; operands are\n"
"                depth 0.  -d -2: operands and their entries;\n"
"                -d +0: everything below the operands; -d 1: entries only\n"
"    -s N[ckMGT] size in bytes compared exactly; k M G T are 1024-based\n"
"    -m N[smhdw] modified: age in seconds against N units, default d.\n"
"                -m -2h under 2 hours; -m +7 over 7 days; -m 7 from 7 up\n"
"                to 8 days\n"
"    -a -c -b    the same for access, status change and birth time;\n"
"                -b is false where the filesystem records no birth time\n"
"    -w [+-][ ]([.][.]/file|HEX)\n"
"                when: modified after (+), before (-) or at the same time\n"
"                as file's mtime, or as HEX epoch seconds (the -v mdate).\n"
"                A file begins with ./ ../ or /, so no word is both a file\n"
"                and a time. A file compares the full timestamp, HEX\n"
"                whole seconds. The sign may stand apart as its own word:\n"
"                -w + ./file is -w +./file. find -newer file is -w +./file.\n"
"    -y file     the same node as file: same device and inode\n"
"    -mode bits  permission bits. Octal, all twelve bits:\n"
"                  0755     exactly 0755\n"
"                  +0755    at least 0755: every bit of it, maybe more\n"
"                  -0755    at most 0755: no bit outside it, maybe fewer\n"
"                Symbolic, clauses [ugoa][+-][rwxXst] joined by commas,\n"
"                all of which must hold. + has, - lacks; a clause with\n"
"                no sign means +. u owner, g group, o other, a all\n"
"                three; each named class must satisfy the clause. With\n"
"                no class, + holds when some class has the bits and -\n"
"                when no class has any of them.\n"
"                X is x that only a directory satisfies (search); a\n"
"                clause with X is false for anything else. s is setuid\n"
"                with u, setgid with g, either with no class, both with\n"
"                a; t is the sticky (/tmp) bit, alone or with o.\n"
"                With no class, each class is tested with only the bits\n"
"                it can hold, so -mode +rs holds when other has r,\n"
"                since other has no s; name the class to need both:\n"
"                -mode u+rs.\n"
"                  -mode u+x        owner may execute\n"
"                  -mode x          someone may execute (same as +x)\n"
"                  -mode -x         no one may execute\n"
"                  -mode o-X        directories others may not search\n"
"                  -mode o-r        others may not read\n"
"                  -mode w          someone may write\n"
"                  -mode o+w        world writable\n"
"                  -mode go-w       neither group nor other may write\n"
"                  -not -mode go-w  group or other may write\n"
"                  -mode u+s        setuid\n"
"                  -mode g+s        setgid\n"
"                  -mode +s         setuid or setgid\n"
"                  -mode +t         sticky\n"
"                Either of two bits in one class: -mode u+r -o -mode u+x\n"
"    -u user     owner, name or number;  -g group  group, name or number\n"
"    -l [+-]N    link count\n"
"    -i [+-]HEX  inode number, hex as ff -v prints it\n"
"    -e          empty regular file or directory\n"
"    -z          prune: do not descend into this directory; true\n"
"    -0          always true;  -1  always false\n"
"\n"
"ACTIONS\n"
"\n"
"    -f          print the path; explicit form for use with -o\n"
,
"    -v          print a cksh line: inode links . size mdate name, hex,\n"
"                the same as cksh -n0 -x0 on that name; see KEYS\n"
"    -x cmd ... ;       run cmd inside the directory holding the node, {}\n"
"                       as ./name; true when cmd exits 0\n"
"    -x cmd ... {} +    the same, many names per run, per directory\n"
"    -j cmd ... ;       run cmd from the current directory, {} as the path\n"
"    -j cmd ... {} +    the same, many paths per run\n"
"    -delete     remove the node; implies -D; refused with -L. An operand\n"
"                ending in .., or that is the root directory (/, /., or .\n"
"                run from /), is refused whole and not walked (4); an\n"
"                operand . is walked and kept itself, as find does\n"
"    -q          stop the walk; pending + batches still run\n"
"\n"
"OPERATORS\n"
"\n"
"    expr expr       and: the right side is evaluated only when the\n"
"                    left is true\n"
"    expr -o expr    or: the right side is evaluated only when the left\n"
"                    is false, so its actions see only nodes the left\n"
"                    rejected\n"
"    ! expr          not; -not expr is the same\n"
"    ( expr )        grouping\n"
"    -not binds tightest, then and, then -o.\n"
"    The shell treats ( ) ; * and sometimes ! as its own syntax, so\n"
"    escape them with a backslash or quote them: \\( \\) \\; '*.c'.\n"
"      ff . -n '*.c' -o -n '*.h' -t f          .c of any type, or .h files\n"
"      ff . \\( -n '*.c' -o -n '*.h' \\) -t f    .c and .h files only\n"
"      ff . -mode u+r -o -mode u+x             owner may read or execute\n"
"    With no action in the expression, a node is printed when the whole\n"
"    expression is true. Once any action appears (-f -v -x -j -delete\n"
"    -q), only actions print. Prune directories by name and print the\n"
"    files that are not RCS (,v) or backup (~) files:\n"
"      ff . \\( -n .git -o -n tmp \\) -z -t f -o -t f -not -r ',v$|~$'\n"
"    -z is true, so the -t f after it makes that side false for the\n"
"    pruned directories; -z -1 does the same. Options such as -I\n"
"    may appear anywhere, even after -not.\n"
"\n"
"REGULAR EXPRESSIONS\n"
"\n"
"    -r takes a POSIX extended regular expression (ERE), the dialect of\n"
"    grep -E and find -E, compiled by the C library's regcomp(3) and\n"
"    matched anywhere in the path; anchor it with ^ and $. -I ignores case.\n"
"      c            a character not listed below matches itself\n"
"      .            any one character, / included: d.e matches d/e\n"
"      [abc]        one of a b c; [a-z] a range; [^abc] none of them;\n"
"                   ] first and - last are literal, and \\ is literal inside\n"
"      [[:digit:]]  a class, inside brackets: alpha digit alnum upper lower\n"
"                   space punct xdigit; [[:digit:]_] adds _\n"
"      ^  $         start and end of the path\n"
"      x*  x+  x?   zero or more, one or more, zero or one of x\n"
"      x{n}         n of x;  x{n,}  n or more;  x{n,m}  n to m\n"
"      (re)         group, for a repeat or an alternation\n"
"      re|re        either side; lowest precedence: ^a|b$ is (^a)|(b$)\n"
"      \\c           c itself, for c any of . [ ( ) { * + ? | ^ $ \\\n"
"                   (] and } alone are already literal)\n"
"    \\ before any other character is undefined in ERE: \\d \\w \\s are not\n"
"    portable, so write [[:digit:]] [[:alnum:]_] [[:space:]].\n"
"    Differences from basic regular expressions (BRE: find -regex, grep,\n"
"    sed), read as ERE here:\n"
"      ERE          BRE          meaning in ERE\n"
"      (re)         \\(re\\)       group\n"
"      x{n,m}       x\\{n,m\\}     interval\n"
"      + ? |        none         one or more, zero or one, alternation\n"
"      \\( \\) \\{     ( ) {        the characters themselves\n"
"      \\1           \\1           back-reference: defined for BRE only; in\n"
"                                ERE a C library extension that varies by\n"
,
"                                platform, refused by ff.fn.bash (2)\n"
"    Glob, for -n and -p, is a different language: glob * and ? are .*\n"
"    and . here, and a glob must match the whole name, not a part of it.\n"
"      ff . -r '\\.(c|h)$'                   C sources and headers\n"
"      ff . -r '/[0-9]{4}-[0-9]{2}-[^/]*$'  names that begin YYYY-MM-\n"
"      ff -I . -r '/readme(\\.md)?$'         readme, README.md, any case\n"
"\n"
"EXEC\n"
"\n"
"    Commands run by fork and exec, never through a shell. {} is replaced\n"
"    only when it is a whole argument. With +, {} must be last and appear\n"
"    once. -x changes into the node's directory through the descriptor the\n"
"    walk verified, so the path above the node cannot be swapped between\n"
"    test and use; -x refuses to run when PATH holds a relative or empty\n"
"    element, since a file planted in the walked directory would run.\n"
"    -j passes the full path, which is exposed to that race, as find\n"
"    -exec is; use it when the command needs whole paths.\n"
"\n"
"BASH FUNCTION\n"
"\n"
"    ff.fn.bash defines a shell function named ff, for hosts where the\n"
"    binary is not installed. When a binary named ff is on PATH the\n"
"    function runs it, unless --fn or -V is given; with --bin it runs\n"
"    the binary or stops with status 2. Sourcing the file defines that\n"
"    one name and nothing else.\n"
"\n"
"    The function translates the ff grammar into an argument list for\n"
"    the find of the host, BSD or GNU, and runs it; -V shows that\n"
"    command. It takes the same grammar and writes the same bytes.\n"
"    Where it differs:\n"
"      - What the native find cannot express is status 2, with a\n"
"        message that names the binary: -b on GNU find; -m -a -c in\n"
"        seconds that are not whole minutes; a back-reference in -r;\n"
"        -v with another action; -S with -x -j -delete or -q on GNU\n"
"        find; a path that begins with -.\n"
"      - -k orders its records with sort -z -s; a sort without them\n"
"        is status 2.\n"
"      - A failure of the native find is status 4, whatever it was;\n"
"        bits 8, 16 and 32 are not reported.\n"
"      - Walk diagnostics are those of the native find.\n"
"      - It runs stat(1) for each record of -v and -k and is slower.\n"
"      - A bash before 5.1 run as sh, in POSIX mode, has no process\n"
"        substitution, which the translator needs: there the function\n"
"        still hands over to a binary, and without one is status 2.\n"
"\n"
"ENVIRONMENT\n"
"\n"
"    PAGER      pager for --help.\n"
"    PATH       -x refuses a relative or empty element; the function\n"
"               looks here for the binary.\n"
"    LANG and LC_* are not consulted for order: names compare as bytes.\n"
"\n"
"EXIT STATUS\n"
"\n"
"    A bitmask. 1 and 2 are fatal; the others accumulate as the walk\n"
"    continues.\n"
"       0  success\n"
"       1  invalid option or expression\n"
"       2  environment: memory, stdout, fork, unsafe PATH for -x\n"
"       4  cannot stat, open, read or delete a node; subtree skipped\n"
"       8  a command could not run, or a + batch exited nonzero\n"
"      16  filesystem or symlink loop\n"
"      32  node changed between listing and opening; skipped\n"
"    A -x or -j ... ; command that exits nonzero is only false.\n"
"\n"
"    On stderr, errors as '>>> ff : ...' and warnings as '^^^ ff : ...',\n"
"    each ending in a hex tag naming the message.\n"
"\n"
"DIFFERENCES\n"
"\n"
"    From NetBSD find: one-letter switches; -r is always ERE, as find -E\n"
"    -regex, with no option to choose BRE, and unanchored; -s is bytes\n"
"    with no rounding; times compare seconds, not rounded days; -d is a\n"
"    global bound; {} is never replaced inside a larger word; names are\n"
"    escaped on a terminal; -I replaces -iname, -ipath and -iregex;\n"
"    -w is when, before, after or at (find -newer is -w +./file); -i\n"
"    reads hex, as ff -v prints the inode; -0 -1 -y are find -true\n"
"    -false -samefile, and -Z is -print0;\n"
,
"    -mode is not find -perm: symbolic modes are queries, not chmod\n"
"    arithmetic, and octal +N (at least) and -N (at most) read the\n"
"    opposite way to find -perm -N; -k sorts what find leaves to sort(1).\n"
"\n"
"EXAMPLES\n"
"\n"
"  Options\n"
"\n"
"    ff -S src -t f                      files in sorted walk order\n"
"    ff -L . -t d                        directories, following symlinks\n"
"    ff -H lib -d 0 -v                   the directory a lib symlink names\n"
"    ff -X / -d -2 -t d                  top directories, root filesystem\n"
"    ff -I . -n '*.jpg'                  .jpg .JPG .Jpg\n"
"    ff -D src                           each directory after its contents\n"
"    ff -Z . -t f -s +1M | xargs -0 ls -l   large files, any names\n"
"    ff -V . -n '*.h'                    ff.fn.bash: show the find command\n"
"\n"
"  Sort\n"
"\n"
"    ff -k . -t f                        files by name\n"
"    ff -k5 . -t f -m -1                 changed within a day, oldest first\n"
"    ff -k5r . -t f                      newest first, names only\n"
"    ff -k4r,6 . -t f -v                 cksh lines, largest first, then name\n"
"    ff -k5,4 . -t f -v                  by time, then size, then the rest\n"
"    ff -Sk . -t f                       -S and -k in one word\n"
"    ff . -t f -v | srt -k5x,4x,6,1x,2x,3\n"
"                                        what ff -k5,4,6 . -t f -v writes\n"
"    ff . -t f | cksh -k5,4              the same files, with their hashes\n"
"    ff -Z . -t f | cksh -Z | srt -Z -k5x,4x\n"
"                                        NUL records end to end: any name\n"
"\n"
"  Primaries\n"
"\n"
"    ff . -n '[A-Z]*.[ch]'               capitalized C sources and headers\n"
"    ff . -p '*/test/*' -t f             files below any test directory\n"
"    ff . -r '\\.orig$' -o -r '\\.rej$'    patch leftovers\n"
"    ff . -r '/(src|lib)/[^/]*\\.c$'      C files directly in src or lib\n"
"    ff . -t lp                          symlinks and fifos\n"
"    ff . -d 1 -t d                      subdirectories, one level\n"
"    ff . -t f -s +100M                  files over 100 MiB\n"
"    ff . -t f -m -30m                   modified in the last 30 minutes\n"
"    ff . -t f -a +365                   not read for a year\n"
"    ff . -t f -c -1 -o -b -1            changed or born within a day\n"
"    ff . -w +./Makefile -n '*.c'        sources newer than Makefile\n"
"    ff . -w -6abb2e78                   modified before that second\n"
"    ff . -w - ./Makefile -n '*.c'       sources older, the sign apart\n"
"    ff . -t f -mode o+w                 world-writable files\n"
"    ff / -X -t f -mode +s               setuid or setgid files\n"
"    ff . -u root -o -g 0                owned by root or by group 0\n"
"    ff . -t f -l +1 -v                  hard-linked files, with inodes\n"
"    ff . -i 1cc01d                      the node -v showed as 1cc01d\n"
"    ff . -y notes.txt                   notes.txt and its hard links\n"
"    ff . -e                             empty files and directories\n"
"\n"
"  Actions\n"
"\n"
"    ff . -n core -t f -f -q             the first core file, then stop\n"
"    ff . -n '*.o' -delete               remove objects\n"
"    ff build -d +0 -t d -e -delete      remove empty directories below\n"
"                                        build, and those left empty\n"
"\n"
"  Exec\n"
"\n"
"    ff . -n '*.sh' -x sh -n {} \\;       syntax-check each script\n"
"    ff . -t f -x grep -l TODO {} +      grep per directory, race safe\n"
"    ff . -t f -j wc -l {} +             line counts with full paths\n"
"    ff . -t f -j grep -q TODO {} \\; -f  a command as a test\n"
"    ff . -n '*.log' -x sh -c 'f=\"$1\"; gzip -- \"$f\" && echo \"$f.gz\"' - {} \\;\n"
"                                        compress each log, name the result\n"
"    ff . -t f -j sh -c 'for f; do wc -c <\"$f\"; done' - {} +\n"
"                                        one shell for many paths\n"
"\n"
"  Operators\n"
"\n"
"    ff . \\( -n '*.c' -o -n '*.h' \\) -not -p '*/vendor/*'\n"
,
"                                        C files outside vendor trees\n"
"    ff . \\( -n .git -o -n tmp \\) -z -1 -o -t f\n"
"                                        files, pruning two directory names\n"
"    ff . -t f \\( -j grep -q TODO {} \\; -j echo todo: {} \\; -o -0 \\) -f\n"
"                                        every file, TODO files marked first\n"
"    ff . -t f -not -mode u+w -f -o -t d -e -f\n"
"                                        read-only files and empty directories\n"
"\n"
"NOTES\n"
"\n"
"    -u and -g resolve names on Linux by running getent from /usr/bin or\n"
"    /bin, so a static binary sees the same users as the host; without\n"
"    getent a name is an error (2) and a numeric id still works. Other\n"
"    platforms use the C library.\n"
"    Names are compared as bytes: no Unicode normalization, so on Darwin\n"
"    HFS+ a precomposed pattern does not match a decomposed name.\n"
"\n"
"SEE ALSO\n"
"\n"
"    cksh(1), srt(1), find(1)\n"
"\n"
"REVISION\n"
"\n"
"    r0.7.\n"
};

/*
 * The manual as man page source. A line of capitals is a section (.SH);
 * a line indented by exactly two blanks is a sub-heading (.SS); all else
 * is kept as it stands, unfilled. The blank line after a heading is
 * dropped, since the macros space for themselves.
 */
static void
roff(FILE *f)
{
	size_t i, total = 0;
	char *buf, *l, *e;
	int n = 0, s = 0, b = 0;

	for (i = 0; i < sizeof manual / sizeof *manual; i++)
		total += strlen(manual[i]);
	buf = xrealloc(NULL, total + 1);
	buf[0] = '\0';
	for (i = 0, l = buf; i < sizeof manual / sizeof *manual; i++) {
		(void)strcpy(l, manual[i]);
		l += strlen(manual[i]);
	}
	(void)fputs(".TH FF 1\n", f);
	for (l = buf; *l; l = e + 1) {
		const char *p;
		int head;

		e = strchr(l, '\n');	/* every manual line ends in one */
		*e = '\0';
		head = *l >= 'A' && *l <= 'Z';
		for (p = l; head && *p; p++)
			head = (*p >= 'A' && *p <= 'Z') || *p == ' ';
		if (head) {
			b = 0;
			(void)fprintf(f, "%s.SH \"%s\"\n.nf\n", n++ ? ".fi\n" : "", l);
			s = 1;
			continue;
		}
		if (s) {
			s = 0;
			if (*l == '\0')
				continue;
		}
		if (*l == '\0') {
			b++;
			continue;
		}
		if (l[0] == ' ' && l[1] == ' ' && l[2] != ' ') {
			b = 0;
			(void)fprintf(f, ".SS \"%s\"\n.nf\n", l + 2);
			s = 1;
			continue;
		}
		for (; b > 0; b--)
			(void)putc('\n', f);
		if (*l == '.' || *l == '\'')
			(void)fputs("\\&", f);
		for (p = l; *p; p++)
			if (*p == '\\')
				(void)fputs("\\e", f);
			else
				(void)putc(*p, f);
		(void)putc('\n', f);
	}
	(void)fputs(".fi\n", f);
	free(buf);
}

static void
plain(FILE *f)
{
	size_t i;

	for (i = 0; i < sizeof manual / sizeof *manual; i++)
		(void)fputs(manual[i], f);
}

/* feed text to a command line; 1 when it ran and ended with status 0 */
static int
feed(const char *cmd, void (*text)(FILE *))
{
	FILE *p;
	int st;

	xflush();
	if (!(p = popen(cmd, "w")))
		return 0;
	text(p);
	st = pclose(p);
	return st != -1 && WIFEXITED(st) && WEXITSTATUS(st) == 0;
}

/*
 * -h writes the usage. --help, on a terminal: the man page source through
 * the formatter of the host, so headings come out bold as man(1) shows
 * them; else the plain text through a pager (PAGER, less, more); else, and
 * to anything but a terminal, plain. The formatter is asked for by name and
 * never through man(1), which on a host without its pages can answer with a
 * notice and status 0. popen(3) runs these by /bin/sh -c, as man(1) does:
 * PAGER is the user's own configuration, unlike -x and -j words, which
 * never pass through a shell. SIGPIPE is ignored so a reader quit early
 * ends the write quietly; a pager that cannot run (126, 127) is passed
 * over, so --help never ends with nothing shown.
 */
static void
put_help(int full)
{
	static const char *const fmt[] = {
		"command -v mandoc >/dev/null 2>&1 || exit 127;"
		" exec mandoc -a 2>/dev/null",
		"command -v nroff >/dev/null 2>&1 || exit 127;"
		" nroff -c -man </dev/null >/dev/null 2>&1 || exit 127;"
		" p=${PAGER:-}; [ -n \"$p\" ] || {"
		" command -v less >/dev/null 2>&1 && p=less || p=more; };"
		" nroff -c -man 2>/dev/null | sh -c \"$p\"",
	};
	const char *try[3];
	size_t i;

	if (!full) {
		(void)fputs(usage_text, stdout);
		xflush();
		exit(0);
	}
	try[0] = getenv("PAGER"); try[1] = "less"; try[2] = "more";
	if (isatty(STDOUT_FILENO)) {
		(void)signal(SIGPIPE, SIG_IGN);	/* reader may quit early */
		for (i = 0; i < sizeof fmt / sizeof *fmt; i++)
			if (feed(fmt[i], roff))
				exit(0);
		for (i = 0; i < 3; i++) {
			FILE *p;
			int st;

			if (!try[i] || !try[i][0])
				continue;
			xflush();
			if (!(p = popen(try[i], "w")))
				continue;
			plain(p);
			st = pclose(p);
			if (st != -1 && WIFEXITED(st) && WEXITSTATUS(st) != 127 &&
			    WEXITSTATUS(st) != 126)
				exit(0);
		}
	}
	plain(stdout);
	xflush();
	exit(0);
}

/* ------------------------------------------------------------------ main */

static int
is_optword(const char *s)
{
	size_t n;

	if (s[0] != '-' || s[1] == '\0')
		return 0;
	n = strspn(s + 1, "IHLDSXZV");
	return s[1 + n] == '\0' || s[1 + n] == 'k';
}

static int
isdig(int c)
{
	return c >= '0' && c <= '9';
}

/*
 * Does the word after a bare -k read as its list? A column list in the
 * widest sense srt gives it, col[letters][,col[letters]]..., so a list
 * that ff refuses is still reported as a list and not walked as a path.
 * A word that begins with - never is: -0 and -1 are primaries.
 */
static int
reads_as_list(const char *s)
{
	for (;;) {
		if (!isdig(*s))
			return 0;
		while (isdig(*s))
			s++;
		while (*s && strchr("dfgHinrvx", *s))
			s++;
		if (*s == '\0')
			return 1;
		if (*s++ != ',')
			return 0;
	}
}

/* -k list: col[r|x...][,col...]; appends to kcol[], krev[] */
static void
parse_keys(const char *arg)
{
	const char *s = arg;
	int col, r, i;

	if (*s == 'r')
		bad("-krN is not accepted, write -kNr; got -k", arg, "6ab7ff4f");
	for (;;) {
		if (*s == '-')
			bad("-k counts columns 1-6 from the left only, got", arg,
			    "6ab7ff50");
		if (*s < '1' || *s > '6' || isdig(s[1]))
			bad("-k requires columns 1-6, got", arg, "6ab7ff4c");
		col = *s++ - '0';
		r = 0;
		for (; *s && *s != ','; s++) {
			if (*s == 'r')
				r = 1;
			else if (*s == 'x' && (col == 3 || col == 6))
				bad("-k letter x is for the numeric columns"
				    " 1 2 4 5; columns 3 and 6 are text, got",
				    arg, "6ab7ff51");
			else if (*s != 'x')
				bad("-k accepts the letters r and x only:"
				    " column types are fixed, got", arg, "6ab7ff52");
		}
		for (i = 0; i < nk; i++)
			if (kcol[i] == col)
				bad("-k names a column twice, got", arg, "6ab7ff53");
		kcol[nk] = col;
		krev[nk++] = r;
		if (*s == '\0')
			return;
		s++;	/* the comma */
		if (*s == '\0')
			bad("-k requires columns 1-6, got", arg, "6ab7ff4c");
	}
}

static int
has_action(int i)
{
	if (i < 0)
		return 0;
	switch (nd[i].type) {
	case N_AND: case N_OR: return has_action(nd[i].l) || has_action(nd[i].r);
	case N_NOT: return has_action(nd[i].l);
	case N_PRINT: case N_LS: case N_EXEC: case N_EXECDIR:
	case N_DELETE: case N_QUIT: return 1;
	}
	return 0;
}

int
main(int argc, char **argv)
{
	int i, npaths = 0, endopt = 0, inexpr = 0, useenv = 0;

	const char *a, *p;
	long am;
	extern char **environ;
	char **ep;

	paths = xrealloc(NULL, (size_t)argc * sizeof *paths);
	tok = xrealloc(NULL, (size_t)argc * sizeof *tok);
	esc_err = isatty(2);
	/* pre-pass: options anywhere, paths before the expression, and
	 * primary arguments and exec words kept whole */
	for (i = 1; i < argc; i++) {
		a = argv[i];
		if (!endopt && is_optword(a)) {
			for (p = a + 1; *p && *p != 'k'; p++)
				switch (*p) {
				case 'I': opt_I = 1; break;
				case 'H': opt_H = 1; opt_L = 0; break;
				case 'L': opt_L = 1; opt_H = 0; break;
				case 'D': opt_D = 1; break;
				case 'S': opt_S = 1; break;
				case 'X': opt_X = 1; break;
				case 'Z': opt_Z = 1; break;
				case 'V': opt_V = 1; break;
				}
			if (*p == 'k') {	/* last in the word; the rest is its list */
				opt_k = 1;
				if (p[1])
					parse_keys(p + 1);
				else if (i + 1 < argc && reads_as_list(argv[i + 1]))
					parse_keys(argv[++i]);
			}
			continue;
		}
		if (!endopt && !strcmp(a, "--zero-terminated")) {
			opt_Z = 1;
			continue;
		}
		if (!endopt && !strcmp(a, "--bin"))
			continue;	/* this is the binary */
		if (!endopt && !strcmp(a, "--fn"))
			die(ST_USAGE, "--fn allows only the bash function"
			    " (ff.fn.bash); this is the binary", NULL, NULL, "6ab7ff54");
		if (!endopt && !inexpr && !strcmp(a, "--")) {
			endopt = 1;
			continue;
		}
		if (!endopt && !inexpr && !strcmp(a, "-h"))
			put_help(0);
		if (!endopt && !inexpr && !strcmp(a, "--help"))
			put_help(1);
		if (!endopt && !inexpr && !strcmp(a, "--man")) {
			roff(stdout);
			xflush();
			exit(0);
		}
		if (!endopt && !inexpr && !strcmp(a, "--version")) {
			(void)puts(FF_REV);
			xflush();
			exit(0);
		}
		if (!inexpr && !is_exprtok(a)) {
			if (a[0] == '-' && !endopt)
				bad("unknown option", a, "6ab7ff01");
			paths[npaths++] = argv[i];
			continue;
		}
		inexpr = 1;
		tok[ntok++] = argv[i];
		if (takes_arg(a)) {
			if (++i >= argc)
				bad("missing argument for", a, "6ab7ff02");
			tok[ntok++] = argv[i];
			/* -w + file: a lone sign keeps the next word as well */
			if (a[1] == 'w' && (!strcmp(argv[i], "+") || !strcmp(argv[i], "-"))) {
				if (++i >= argc)
					bad("missing argument for", a, "6ab7ff02");
				tok[ntok++] = argv[i];
			}
		} else if (is_prim(a, P_EXEC)) {
			for (i++; i < argc; i++) {
				tok[ntok++] = argv[i];
				if (!strcmp(argv[i], ";") || (!strcmp(argv[i], "+") &&
				    !strcmp(argv[i - 1], "{}")))
					break;
			}
			if (i >= argc)
				bad("missing ; or {} + after", a, "6ab7ff1d");
		} else if (!is_exprtok(a))
			bad(a[0] == '-' ? "unknown primary" : "unexpected word", a,
			    a[0] == '-' ? "6ab7ff03" : "6ab7ff04");
	}
	if (ntok) {
		root = parse_or();
		if (ti < ntok)
			bad("unexpected", tok[ti], "6ab7ff05");
	}
	if (opt_k)
		need_stat = 1;	/* every record is keyed by its stat */
	if (!has_action(root))
		root = root < 0 ? mk(N_PRINT, -1, -1) :
		    mk(N_AND, root, mk(N_PRINT, -1, -1));
	for (i = 0; i < nnd; i++)
		if (nd[i].type == N_DELETE) {
			if (opt_L)
				bad("-delete is refused with -L", NULL, "6ab7ff1e");
			deleting = 1;
		}
	for (i = 0; i < nnd; i++)
		if (nd[i].type == N_EXECDIR && !strchr(nd[i].argv[0], '/'))
			useenv = 2;
	if (useenv == 2)
		check_path();
	if (opt_V)	/* only the translator has a native command to show */
		WRN("-V: the native find command is printed by ff.fn.bash", NULL,
		    NULL, "6ab7ff47");

	/* exec argument budget: ARG_MAX less the environment and headroom */
	am = sysconf(_SC_ARG_MAX);
	argmax = am > 0 ? (size_t)am : 65536;
	for (ep = environ; ep && *ep; ep++)
		argmax -= argmax > strlen(*ep) + 1 + sizeof *ep ?
		    strlen(*ep) + 1 + sizeof *ep : 0;
	argmax = argmax > 4096 + 2048 ? argmax - 4096 : 2048;
	if (argmax > 262144)
		argmax = 262144;

	/* half the descriptor limit, leaving room for stdio, -e and exec pipes */
	{
		struct rlimit rl;

		if (getrlimit(RLIMIT_NOFILE, &rl) == 0 && rl.rlim_cur != RLIM_INFINITY &&
		    rl.rlim_cur / 2 < (rlim_t)fdcap + 8)
			fdcap = rl.rlim_cur / 2 > 12 ? (int)(rl.rlim_cur / 2) - 8 : 4;
	}
	esc_out = isatty(1);
	now = time(NULL);
	pbcap = 256;
	pb = xrealloc(NULL, pbcap);
	if (npaths == 0)
		paths[npaths++] = ".";
	for (i = 0; i < npaths && !quitting; i++) {
		if (paths[i][0] == '\0') {
			ERR("empty path", NULL, NULL, "6ab7ff3b");
			status |= ST_NODE;
			continue;
		}
		walk_operand(paths[i]);
	}
	flush_all(0, 0);
	rec_flush();
	xflush();
	return status;
}
