/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#pragma ident	"%Z%%M%	%I%	%E% SMI"

/*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
/*	  All Rights Reserved  	*/


/*	Parts of this product may be derived from		*/
/*	Mortice Kern Systems Inc. and Berkeley 4.3 BSD systems.	*/
/*	licensed from  Mortice Kern Systems Inc. and 		*/
/*	the University of California.				*/

/*
 * Copyright 1985, 1990 by Mortice Kern Systems Inc.  All rights reserved.
 */

#include <stdio.h>
#include <errno.h>
#include <pwd.h>
#include <grp.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/param.h>
#include <sys/acl.h>
#include <limits.h>
#include <unistd.h>
#include <stdlib.h>
#include <locale.h>
#include <string.h>
#include <strings.h>
#include <libgen.h>
#include <ctype.h>
#include <wait.h>
#include <fnmatch.h>
#include <langinfo.h>
#include <ftw.h>

#define	A_DAY		(long)(60*60*24)	/* a day full of seconds */
#define	A_MIN		(long)(60)
#define	BLKSIZ		512
#define	round(x, s)	(((x)+(s)-1)&~((s)-1))
#ifndef FTW_SLN
#define	FTW_SLN		7
#endif
#define	LINEBUF_SIZE		LINE_MAX	/* input or output lines */
#define	REMOTE_FS		"/etc/dfs/fstypes"
#define	N_FSTYPES		20
#define	SHELL_MAXARGS		253	/* see doexec() for description */

/*
 * This is the list of operations
 * F_USER and F_GROUP are named to avoid conflict with USER and GROUP defined
 * in sys/acl.h
 */

enum Command
{
	PRINT, DEPTH, LOCAL, MOUNT, ATIME, MTIME, CTIME, NEWER,
	NAME, F_USER, F_GROUP, INUM, SIZE, LINKS, PERM, EXEC, OK, CPIO, NCPIO,
	TYPE, AND, OR, NOT, LPAREN, RPAREN, CSIZE, VARARGS, FOLLOW,
	PRUNE, NOUSER, NOGRP, FSTYPE, LS, XATTR, ACL, MMIN, AMIN, CMIN
};

enum Type
{
	Unary, Id, Num, Str, Exec, Cpio, Op
};

struct Args
{
	char		name[10];
	enum Command	action;
	enum Type	type;
};

/*
 * Except for pathnames, these are the only legal arguments
 */
static struct Args commands[] =
{
	"!",		NOT,	Op,
	"(",		LPAREN,	Unary,
	")",		RPAREN,	Unary,
	"-a",		AND,	Op,
	"-amin",	AMIN,	Num,
	"-atime",	ATIME,	Num,
	"-cpio",	CPIO,	Cpio,
	"-cmin",	CMIN,	Num,
	"-ctime",	CTIME,	Num,
	"-depth",	DEPTH,	Unary,
	"-exec",	EXEC,	Exec,
	"-follow",	FOLLOW, Unary,
	"-group",	F_GROUP,	Num,
	"-inum",	INUM,	Num,
	"-links",	LINKS,	Num,
	"-local",	LOCAL,	Unary,
	"-mount",	MOUNT,	Unary,
	"-mmin",	MMIN,	Num,
	"-mtime",	MTIME,	Num,
	"-name",	NAME,	Str,
	"-ncpio",	NCPIO,  Cpio,
	"-newer",	NEWER,	Str,
	"-o",		OR,	Op,
	"-ok",		OK,	Exec,
	"-perm",	PERM,	Num,
	"-print",	PRINT,	Unary,
	"-size",	SIZE,	Num,
	"-type",	TYPE,	Num,
	"-xdev",	MOUNT,	Unary,
	"-user",	F_USER,	Num,
	"-prune",	PRUNE,	Unary,
	"-nouser",	NOUSER,	Unary,
	"-nogroup",	NOGRP,	Unary,
	"-fstype",	FSTYPE,	Str,
	"-ls",		LS,	Unary,
	"-xattr",	XATTR,	Unary,
	"-acl",		ACL,	Unary,
	NULL,		0,	0
};

union Item
{
	struct Node	*np;
	struct Arglist	*vp;
	time_t		t;
	char		*cp;
	char		**ap;
	long		l;
	int		i;
	long long	ll;
};

struct Node
{
	struct Node	*next;
	enum Command	action;
	enum Type	type;
	union Item	first;
	union Item	second;
};

/* if no -print, -exec or -ok replace "expression" with "(expression) -print" */
static	struct	Node PRINT_NODE = { 0, PRINT, 0, 0};
static	struct	Node LPAREN_NODE = { 0, LPAREN, 0, 0};


/*
 * Prototype variable size arglist buffer
 */

struct Arglist
{
	struct Arglist	*next;
	char		*end;
	char		*nextstr;
	char		**firstvar;
	char		**nextvar;
	char		*arglist[1];
};


static int		compile();
static int		execute();
static int		doexec(char *, char **, int *);
static struct Args	*lookup();
static int		ok();
static void		usage(void)	__NORETURN;
static struct Arglist	*varargs();
static int		list();
static char		*getgroup();
static FILE		*cmdopen();
static int		cmdclose();
static char		*getshell();
static void 		init_remote_fs();
static char		*getname();
static int		readmode();
static mode_t		getmode();
static char		*gettail();


static int		walkflags = FTW_CHDIR|FTW_PHYS|FTW_ANYERR;
static struct Node	*savetnode;
static struct Node	*topnode;
static struct Node	*freenode;	/* next free node we may use later */
static char		*cpio[] = { "cpio", "-o", 0 };
static char		*ncpio[] = { "cpio", "-oc", 0 };
static char		*cpiol[] = { "cpio", "-oL", 0 };
static char		*ncpiol[] = { "cpio", "-ocL", 0 };
static time_t		now;
static FILE		*output;
static char		*dummyarg = (char *)-1;
static int		lastval;
static int		varsize;
static struct Arglist	*lastlist;
static char		*cmdname;
static char		*remote_fstypes[N_FSTYPES+1];
static int		fstype_index = 0;
static int		action_expression = 0;	/* -print, -exec, or -ok */
static int		error = 0;
static int		paren_cnt = 0;	/* keeps track of parentheses */
static int		hflag = 0;
static int		lflag = 0;
/* set when doexec()-invoked utility returns non-zero */
static int		exec_exitcode = 0;
extern char		**environ;

int
main(int argc, char **argv)
{
	char *cp;
	int c;
	int paths;
	char *cwdpath;

	(void) setlocale(LC_ALL, "");
#if !defined(TEXT_DOMAIN)	/* Should be defined by cc -D */
#define	TEXT_DOMAIN "SYS_TEST"	/* Use this only if it weren't */
#endif
	(void) textdomain(TEXT_DOMAIN);

	cmdname = argv[0];
	if (time(&now) == (time_t)(-1)) {
		(void) fprintf(stderr, gettext("%s: time() %s\n"),
			cmdname, strerror(errno));
		exit(1);
	}
	while ((c = getopt(argc, argv, "HL")) != -1) {
		switch (c) {
		case 'H':
			hflag = 1;
			lflag = 0;
			break;
		case 'L':
			hflag = 0;
			lflag = 1;
			break;
		case '?':
			usage();
			break;
		}
	}

	argc -= optind;
	argv += optind;

	if (argc < 1) {
		(void) fprintf(stderr,
		    gettext("%s: insufficient number of arguments\n"), cmdname);
		usage();
	}

	for (paths = 0; (cp = argv[paths]) != 0; ++paths) {
		if (*cp == '-')
			break;
		else if ((*cp == '!' || *cp == '(') && *(cp+1) == 0)
			break;
	}

	if (paths == 0) /* no path-list */
		usage();

	output = stdout;

	/* lflag is the same as -follow */
	if (lflag)
		walkflags &= ~FTW_PHYS;

	/* allocate enough space for the compiler */
	topnode = malloc((argc + 1) * sizeof (struct Node));
	savetnode = malloc((argc + 1) * sizeof (struct Node));
	(void) memset(topnode, 0, (argc + 1) * sizeof (struct Node));
	(void) memset(savetnode, 0, (argc + 1) * sizeof (struct Node));

	if (compile(argv + paths, topnode, &action_expression) == 0) {
		/* no expression, default to -print */
		(void) memcpy(topnode, &PRINT_NODE, sizeof (struct Node));
	} else if (!action_expression) {
		/*
		 * if no action expression, insert an LPAREN node above topnode,
		 * with a PRINT node as its next node
		 */
		struct Node *savenode;

		if (freenode == NULL) {
			(void) fprintf(stderr, gettext("%s: can't append -print"
				" implicitly; try explicit -print option\n"),
				cmdname);
			exit(1);
		}
		savenode = topnode;
		topnode = freenode++;
		(void) memcpy(topnode, &LPAREN_NODE, sizeof (struct Node));
		topnode->next = freenode;
		topnode->first.np = savenode;
		(void) memcpy(topnode->next, &PRINT_NODE, sizeof (struct Node));
	}
	(void) memcpy(savetnode, topnode, ((argc + 1) * sizeof (struct Node)));

	while (paths--) {
		char *curpath;
		struct stat sb;

		curpath = *(argv++);

		/*
		 * If -H is specified, it means we walk the first
		 * level (pathname on command line) logically, following
		 * symlinks, but lower levels are walked physically.
		 * We use our own secret interface to nftw() to change
		 * the from stat to lstat after the top level is walked.
		 */
		if (hflag) {
			if (stat(curpath, &sb) < 0 && errno == ENOENT)
				walkflags &= ~FTW_HOPTION;
			else
				walkflags |= FTW_HOPTION;
		}

		/*
		 * We need this check as nftw needs a CWD and we have no
		 * way of returning back from that code with a meaningful
		 * error related to this
		 */
		if ((cwdpath = getcwd(NULL, PATH_MAX)) == NULL) {
			(void) fprintf(stderr,
				gettext("%s : cannot get the current working "
					"directory\n"), cmdname);
			exit(1);
		} else
			free(cwdpath);


		if (nftw(curpath, execute, 1000, walkflags)) {
			(void) fprintf(stderr,
			    gettext("%s: cannot open %s: %s\n"),
			    cmdname, curpath, strerror(errno));
			error = 1;
		}

		if (paths > 1)
			(void) memcpy(topnode, savetnode,
			    ((argc + 1) * sizeof (struct Node)));
	}

	/* execute any remaining variable length lists */
	while (lastlist) {
		if (lastlist->end != lastlist->nextstr) {
			*lastlist->nextvar = 0;
			(void) doexec((char *)0, lastlist->arglist,
			    &exec_exitcode);
		}
		lastlist = lastlist->next;
	}
	if (output != stdout)
		return (cmdclose(output));
	return ((exec_exitcode != 0) ? exec_exitcode : error);
}

/*
 * compile the arguments
 */

static int
compile(argv, np, actionp)
char **argv;
struct Node *np;
int *actionp;
{
	char *b;
	char **av;
	struct Node *oldnp = topnode;
	struct Args *argp;
	char **com;
	int i;
	enum Command wasop = PRINT;

	for (av = argv; *av && (argp = lookup(*av)); av++) {
		np->next = 0;
		np->action = argp->action;
		np->type = argp->type;
		np->second.i = 0;
		if (argp->type == Op) {
			if (wasop == NOT || (wasop && np->action != NOT)) {
				(void) fprintf(stderr,
				gettext("%s: operand follows operand\n"),
						cmdname);
				exit(1);
			}
			if (np->action != NOT && oldnp == 0)
				goto err;
			wasop = argp->action;
		} else {
			wasop = PRINT;
			if (argp->type != Unary) {
				if (!(b = *++av)) {
					(void) fprintf(stderr,
					gettext("%s: incomplete statement\n"),
							cmdname);
					exit(1);
				}
				if (argp->type == Num) {
					if ((argp->action != PERM) ||
					    (*b != '+')) {
						if (*b == '+' || *b == '-') {
							np->second.i = *b;
							b++;
						}
					}
				}
			}
		}
		switch (argp->action) {
		case AND:
			break;
		case NOT:
			break;
		case OR:
			np->first.np = topnode;
			topnode = np;
			oldnp->next = 0;
			break;

		case LPAREN: {
			struct Node *save = topnode;
			topnode = np+1;
			paren_cnt++;
			i = compile(++av, topnode, actionp);
			np->first.np = topnode;
			topnode = save;
			av += i;
			oldnp = np;
			np += i + 1;
			oldnp->next = np;
			continue;
		}

		case RPAREN:
			if (paren_cnt <= 0) {
				(void) fprintf(stderr,
				    gettext("%s: unmatched ')'\n"),
				    cmdname);
				exit(1);
			}
			paren_cnt--;
			if (oldnp == 0)
				goto err;
			if (oldnp->type == Op) {
				(void) fprintf(stderr,
				    gettext("%s: cannot immediately"
				    " follow an operand with ')'\n"),
				    cmdname);
				exit(1);
			}
			oldnp->next = 0;
			return (av-argv);

		case FOLLOW:
			walkflags &= ~FTW_PHYS;
			break;
		case MOUNT:
			walkflags |= FTW_MOUNT;
			break;
		case DEPTH:
			walkflags |= FTW_DEPTH;
			break;

		case LOCAL:
			np->first.l = 0L;
			np->first.ll = 0LL;
			np->second.i = '+';
			/*
			 * Make it compatible to df -l for
			 * future enhancement. So, anything
			 * that is not remote, then it is
			 * local.
			 */
			init_remote_fs();
			break;

		case SIZE:
			if (b[strlen(b)-1] == 'c')
				np->action = CSIZE;
			/*FALLTHROUGH*/
		case INUM:
			np->first.ll = atoll(b);
			break;

		case CMIN:
		case CTIME:
		case MMIN:
		case MTIME:
		case AMIN:
		case ATIME:
		case LINKS:
			np->first.l = atol(b);
			break;

		case F_USER:
		case F_GROUP: {
			struct	passwd	*pw;
			struct	group *gr;
			i = -1;
			if (argp->action == F_USER) {
				if ((pw = getpwnam(b)) != 0)
					i = (int)pw->pw_uid;
			} else {
				if ((gr = getgrnam(b)) != 0)
					i = (int)gr->gr_gid;
			}
			if (i == -1) {
				if (fnmatch("[0-9][0-9][0-9]*", b, 0) &&
						fnmatch("[0-9][0-9]", b, 0) &&
						fnmatch("[0-9]", b, 0)) {
					(void) fprintf(stderr, gettext(
					    "%s: cannot find %s name\n"),
						cmdname, *av);
					exit(1);
				}
				i = atoi(b);
			}
			np->first.l = i;
			break;
		}

		case EXEC:
		case OK:
			walkflags &= ~FTW_CHDIR;
			np->first.ap = av;
			(*actionp)++;
			for (;;) {
				if ((b = *av) == 0) {
					(void) fprintf(stderr,
					gettext("%s: incomplete statement\n"),
						cmdname);
					exit(1);
				}
				if (strcmp(b, ";") == 0) {
					*av = 0;
					break;
				} else if (strcmp(b, "{}") == 0)
					*av = dummyarg;
				else if (strcmp(b, "+") == 0 &&
					av[-1] == dummyarg &&
					np->action == EXEC) {
					av[-1] = 0;
					np->first.vp = varargs(np->first.ap);
					np->action = VARARGS;
					break;
				}
				av++;
			}
			break;

		case NAME:
			np->first.cp = b;
			break;
		case PERM:
			if (*b == '-')
				++b;

			if (readmode(b) != NULL) {
				(void) fprintf(stderr, gettext(
				    "find: -perm: Bad permission string\n"));
				usage();
			}
			np->first.l = (long)getmode((mode_t)0);
			break;
		case TYPE:
			i = *b;
			np->first.l =
			    i == 'd' ? S_IFDIR :
			    i == 'b' ? S_IFBLK :
			    i == 'c' ? S_IFCHR :
#ifdef S_IFIFO
			    i == 'p' ? S_IFIFO :
#endif
			    i == 'f' ? S_IFREG :
#ifdef S_IFLNK
			    i == 'l' ? S_IFLNK :
#endif
#ifdef S_IFSOCK
			    i == 's' ? S_IFSOCK :
#endif
#ifdef S_IFDOOR
			    i == 'D' ? S_IFDOOR :
#endif
			    0;
			break;

		case CPIO:
			if (walkflags & FTW_PHYS)
				com = cpio;
			else
				com = cpiol;
			goto common;

		case NCPIO: {
			FILE *fd;

			if (walkflags & FTW_PHYS)
				com = ncpio;
			else
				com = ncpiol;
		common:
			/* set up cpio */
			if ((fd = fopen(b, "w")) == NULL) {
				(void) fprintf(stderr,
					gettext("%s: cannot create %s\n"),
					cmdname, b);
				exit(1);
			}

			np->first.l = (long)cmdopen("cpio", com, "w", fd);
			(void) fclose(fd);
			walkflags |= FTW_DEPTH;
			np->action = CPIO;
		}
			/*FALLTHROUGH*/
		case PRINT:
			(*actionp)++;
			break;

		case NEWER: {
			struct stat statb;
			if (stat(b, &statb) < 0) {
				(void) fprintf(stderr,
					gettext("%s: cannot access %s\n"),
					cmdname, b);
				exit(1);
			}
			np->first.l = statb.st_mtime;
			np->second.i = '+';
			break;
		}

		case PRUNE:
		case NOUSER:
		case NOGRP:
			break;
		case FSTYPE:
			np->first.cp = b;
			break;
		case LS:
			(*actionp)++;
			break;
		case XATTR:
			break;
		case ACL:
			break;
		}

		oldnp = np++;
		oldnp->next = np;
	}

	if ((*av) || (wasop))
		goto err;

	if (paren_cnt != 0) {
		(void) fprintf(stderr, gettext("%s: unmatched '('\n"),
		cmdname);
		exit(1);
	}

	/* just before returning, save next free node from the list */
	freenode = oldnp->next;
	oldnp->next = 0;
	return (av-argv);
err:
	if (*av)
		(void) fprintf(stderr,
		    gettext("%s: bad option %s\n"), cmdname, *av);
	else
		(void) fprintf(stderr, gettext("%s: bad option\n"), cmdname);
	usage();
	/*NOTREACHED*/
}

/*
 * print out a usage message
 */

static void
usage(void)
{
	(void) fprintf(stderr,
	    gettext("%s: [-H | -L] path-list predicate-list\n"), cmdname);
	exit(1);
}

/*
 * This is the function that gets executed at each node
 */

static int
execute(name, statb, type, state)
char *name;
struct stat *statb;
int type;
struct FTW *state;
{
	struct Node *np = topnode;
	int val;
	time_t t;
	long l;
	long long ll;
	int not = 1;
	char *filename;

	if (type == FTW_NS) {
		(void) fprintf(stderr, gettext("%s: stat() error %s: %s\n"),
			cmdname, name, strerror(errno));
		error = 1;
		return (0);
	} else if (type == FTW_DNR) {
		(void) fprintf(stderr, gettext("%s: cannot read dir %s: %s\n"),
			cmdname, name, strerror(errno));
		error = 1;
		return (0);
	} else if (type == FTW_SLN && lflag == 0) {
		(void) fprintf(stderr,
			gettext("%s: cannot follow symbolic link %s: %s\n"),
			cmdname, name, strerror(errno));
		error = 1;
		return (0);
	}

	while (np) {
		switch (np->action) {
		case NOT:
			not = !not;
			np = np->next;
			continue;

		case AND:
			np = np->next;
			continue;

		case OR:
			if (np->first.np == np) {
				/*
				 * handle naked OR (no term on left hand side)
				 */
				(void) fprintf(stderr,
				    gettext("%s: invalid -o construction\n"),
				    cmdname);
				exit(2);
			}
			/* FALLTHROUGH */
		case LPAREN: {
			struct Node *save = topnode;
			topnode = np->first.np;
			(void) execute(name, statb, type, state);
			val = lastval;
			topnode = save;
			if (np->action == OR) {
				if (val)
					return (0);
				val = 1;
			}
			break;
		}

		case LOCAL: {
			int	nremfs;
			val = 1;
			/*
			 * If file system type matches the remote
			 * file system type, then it is not local.
			 */
			for (nremfs = 0; nremfs < fstype_index; nremfs++) {
				if (strcmp(remote_fstypes[nremfs],
						statb->st_fstype) == 0) {
					val = 0;
					break;
				}
			}
			break;
		}

		case TYPE:
			l = (long)statb->st_mode&S_IFMT;
			goto num;

		case PERM:
			l = (long)statb->st_mode&07777;
			if (np->second.i == '-')
				val = ((l&np->first.l) == np->first.l);
			else
				val = (l == np->first.l);
			break;

		case INUM:
			ll = (long long)statb->st_ino;
			goto llnum;
		case NEWER:
			l = statb->st_mtime;
			goto num;
		case ATIME:
			t = statb->st_atime;
			goto days;
		case CTIME:
			t = statb->st_ctime;
			goto days;
		case MTIME:
			t = statb->st_mtime;
		days:
			l = (now-t)/A_DAY;
			goto num;
		case MMIN:
			t = statb->st_mtime;
			goto mins;
		case AMIN:
			t = statb->st_atime;
			goto mins;
		case CMIN:
			t = statb->st_ctime;
			goto mins;
		mins:
			l = (now-t)/A_MIN;
			goto num;
		case CSIZE:
			ll = (long long)statb->st_size;
			goto llnum;
		case SIZE:
			ll = (long long)round(statb->st_size, BLKSIZ)/BLKSIZ;
			goto llnum;
		case F_USER:
			l = (long)statb->st_uid;
			goto num;
		case F_GROUP:
			l = (long)statb->st_gid;
			goto num;
		case LINKS:
			l = (long)statb->st_nlink;
			goto num;
		llnum:
			if (np->second.i == '+')
				val = (ll > np->first.ll);
			else if (np->second.i == '-')
				val = (ll < np->first.ll);
			else
				val = (ll == np->first.ll);
			break;
		num:
			if (np->second.i == '+')
				val = (l > np->first.l);
			else if (np->second.i == '-')
				val = (l < np->first.l);
			else
				val = (l == np->first.l);
			break;
		case OK:
			val = ok(name, np->first.ap);
			break;
		case EXEC:
			val = doexec(name, np->first.ap, NULL);
			break;

		case VARARGS: {
			struct Arglist *ap = np->first.vp;
			char *cp;
			cp = ap->nextstr - (strlen(name)+1);
			if (cp >= (char *)(ap->nextvar+3)) {
				/* there is room just copy the name */
				val = 1;
				(void) strcpy(cp, name);
				*ap->nextvar++ = cp;
				ap->nextstr = cp;
			} else {
				/* no more room, exec command */
				*ap->nextvar++ = name;
				*ap->nextvar = 0;
				val = 1;
				(void) doexec((char *)0, ap->arglist,
				    &exec_exitcode);
				ap->nextstr = ap->end;
				ap->nextvar = ap->firstvar;
			}
			break;
		}

		case DEPTH:
		case MOUNT:
		case FOLLOW:
			val = 1;
			break;

		case NAME: {
			/*
			 * XPG4 find should not treat a leading '.' in a
			 * filename specially for pattern matching.
			 * /usr/bin/find  will not pattern match a leading
			 * '.' in a filename, unless '.' is explicitly
			 * specified.
			 */
#ifdef XPG4
			val = !fnmatch(np->first.cp,
			    name+state->base, 0);
#else
			val = !fnmatch(np->first.cp,
			    name+state->base, FNM_PERIOD);
#endif
			break;
		}

		case PRUNE:
			if (type == FTW_D)
				state->quit = FTW_PRUNE;
			val = 1;
			break;
		case NOUSER:
			val = ((getpwuid(statb->st_uid)) == 0);
			break;
		case NOGRP:
			val = ((getgrgid(statb->st_gid)) == 0);
			break;
		case FSTYPE:
			val = (strcmp(np->first.cp, statb->st_fstype) == 0);
			break;
		case CPIO:
			output = (FILE *)np->first.l;
			(void) fprintf(output, "%s\n", name);
			val = 1;
			break;
		case PRINT:
			(void) fprintf(stdout, "%s\n", name);
			val = 1;
			break;
		case LS:
			(void) list(name, statb);
			val = 1;
			break;
		case XATTR:
			filename = gettail(name);
			val = (pathconf(filename, _PC_XATTR_EXISTS) == 1);
			break;
		case ACL:
			/*
			 * Need to get the tail of the file name, since we have
			 * already chdir()ed into the directory (performed in
			 * nftw()) of the file
			 */
			filename = gettail(name);
			val = acl_trivial(name);
			break;
		}
		/*
		 * evaluate 'val' and 'not' (exclusive-or)
		 * if no inversion (not == 1), return only when val == 0
		 * (primary not true). Otherwise, invert the primary
		 * and return when the primary is true.
		 * 'Lastval' saves the last result (fail or pass) when
		 * returning back to the calling routine.
		 */
		if (val^not) {
			lastval = 0;
			return (0);
		}
		lastval = 1;
		not = 1;
		np = np->next;
	}
	return (0);
}

/*
 * code for the -ok option
 */

static int
ok(name, argv)
char *name;
char *argv[];
{
	int c, yes = 0;

	(void) fflush(stdout); 	/* to flush possible `-print' */

	if ((*argv != dummyarg) && (strcmp(*argv, name)))
		(void) fprintf(stderr, "< %s ... %s >?   ", *argv, name);
	else
		(void) fprintf(stderr, "< {} ... %s >?   ", name);

	(void) fflush(stderr);
	if ((c = tolower(getchar())) == *nl_langinfo(YESSTR))
		yes = 1;
	while (c != '\n')
		if (c == EOF)
			exit(2);
		else
			c = getchar();
	return (yes? doexec(name, argv, NULL): 0);
}

/*
 * execute argv with {} replaced by name
 *
 * Per XPG6, find must exit non-zero if an invocation through
 * -exec, punctuated by a plus sign, exits non-zero, so set
 * exitcode if we see a non-zero exit.
 * exitcode should be NULL when -exec or -ok is not punctuated
 * by a plus sign.
 */

static int
doexec(char *name, char *argv[], int *exitcode)
{
	char *cp;
	char **av = argv;
	char *newargs[1 + SHELL_MAXARGS + 1];
	int dummyseen = 0;
	int i, j, status, rc, r = 0;
	int exit_status = 0;
	pid_t pid, pid1;

	(void) fflush(stdout);	  /* to flush possible `-print' */
	if (name) {
		while (cp = *av++) {
			if (cp == dummyarg) {
				dummyseen = 1;
				av[-1] = name;
			}

		}
	}
	if (argv[0] == NULL)    /* null command line */
		return (r);

	if ((pid = fork()) == -1) {
		/* fork failed */
		if (exitcode != NULL)
			*exitcode = 1;
		return (0);
	}
	if (pid != 0) {
		/* parent */
		do {
			/* wait for child to exit */
			if ((rc = wait(&r)) == -1 && errno != EINTR) {
				(void) fprintf(stderr,
				    gettext("wait failed %s"), strerror(errno));

				if (exitcode != NULL)
					*exitcode = 1;
				return (0);
			}
		} while (rc != pid);
	} else {
		/* child */
		(void) execvp(argv[0], argv);
		if (errno != E2BIG)
			exit(1);

		/*
		 * We are in a situation where argv[0] points to a
		 * script without the interpreter line, e.g. #!/bin/sh.
		 * execvp() will execute either /usr/bin/sh or
		 * /usr/xpg4/bin/sh against the script, and you will be
		 * limited to SHELL_MAXARGS arguments. If you try to
		 * pass more than SHELL_MAXARGS arguments, execvp()
		 * fails with E2BIG.
		 * See usr/src/lib/libc/port/gen/execvp.c.
		 *
		 * In this situation, process the argument list by
		 * packets of SHELL_MAXARGS arguments with respect of
		 * the following rules:
		 * 1. the invocations have to complete before find exits
		 * 2. only one invocation can be running at a time
		 */

		i = 1;
		newargs[0] = argv[0];

		while (argv[i]) {
			j = 1;
			while (j <= SHELL_MAXARGS && argv[i]) {
				newargs[j++] = argv[i++];
			}
			newargs[j] = NULL;

			if ((pid1 = fork()) == -1) {
				/* fork failed */
				exit(1);
			}
			if (pid1 == 0) {
				/* child */
				(void) execvp(newargs[0], newargs);
				exit(1);
			}

			status = 0;

			do {
				/* wait for the child to exit */
				if ((rc = wait(&status)) == -1 &&
				    errno != EINTR) {
					(void) fprintf(stderr,
					    gettext("wait failed %s"),
					    strerror(errno));
					exit(1);
				}
			} while (rc != pid1);

			if (status)
				exit_status = 1;
		}
		/* all the invocations have completed */
		exit(exit_status);
	}

	if (name && dummyseen) {
		for (av = argv; cp = *av++; ) {
			if (cp == name)
				av[-1] = dummyarg;
		}
	}

	if (r && exitcode != NULL)
		*exitcode = 3; /* use to indicate error in cmd invocation */

	return (!r);
}


/*
 *  Table lookup routine
 */
static struct Args *
lookup(word)
char *word;
{
	struct Args *argp = commands;
	int second;
	if (word == 0 || *word == 0)
		return (0);
	second = word[1];
	while (*argp->name) {
		if (second == argp->name[1] && strcmp(word, argp->name) == 0)
			return (argp);
		argp++;
	}
	return (0);
}


/*
 * Get space for variable length argument list
 */

static struct Arglist *
varargs(com)
char **com;
{
	struct Arglist *ap;
	int n;
	char **ep;
	if (varsize == 0) {
		n = 2*sizeof (char **);
		for (ep = environ; *ep; ep++)
			n += (strlen(*ep)+sizeof (ep) + 1);
		varsize = sizeof (struct Arglist)+ARG_MAX-PATH_MAX-n-1;
	}
	ap = (struct Arglist *)malloc(varsize+1);
	ap->end = (char *)ap + varsize;
	ap->nextstr = ap->end;
	ap->nextvar = ap->arglist;
	while (*ap->nextvar++ = *com++);
	ap->nextvar--;
	ap->firstvar = ap->nextvar;
	ap->next = lastlist;
	lastlist = ap;
	return (ap);
}

/*
 * filter command support
 * fork and exec cmd(argv) according to mode:
 *
 *	"r"	with fp as stdin of cmd (default stdin), cmd stdout returned
 *	"w"	with fp as stdout of cmd (default stdout), cmd stdin returned
 */

#define	CMDERR	((1<<8)-1)	/* command error exit code		*/
#define	MAXCMDS	8		/* max # simultaneous cmdopen()'s	*/

static struct			/* info for each cmdopen()		*/
{
	FILE	*fp;		/* returned by cmdopen()		*/
	pid_t	pid;		/* pid used by cmdopen()		*/
} cmdproc[MAXCMDS];

static FILE *
cmdopen(cmd, argv, mode, fp)
char	*cmd;
char	**argv;
char	*mode;
FILE	*fp;
{
	int	proc;
	int	cmdfd;
	int	usrfd;
	int		pio[2];

	switch (*mode) {
	case 'r':
		cmdfd = 1;
		usrfd = 0;
		break;
	case 'w':
		cmdfd = 0;
		usrfd = 1;
		break;
	default:
		return (0);
	}

	for (proc = 0; proc < MAXCMDS; proc++)
		if (!cmdproc[proc].fp)
			break;
	if (proc >= MAXCMDS)
		return (0);

	if (pipe(pio))
		return (0);

	switch (cmdproc[proc].pid = fork()) {
	case -1:
		return (0);
	case 0:
		if (fp && fileno(fp) != usrfd) {
			(void) close(usrfd);
			if (dup2(fileno(fp), usrfd) != usrfd)
				_exit(CMDERR);
			(void) close(fileno(fp));
		}
		(void) close(cmdfd);
		if (dup2(pio[cmdfd], cmdfd) != cmdfd)
			_exit(CMDERR);
		(void) close(pio[cmdfd]);
		(void) close(pio[usrfd]);
		(void) execvp(cmd, argv);
		if (errno == ENOEXEC) {
			char	**p;
			char		**v;

			/*
			 * assume cmd is a shell script
			 */

			p = argv;
			while (*p++);
			if (v = (char **)malloc((p - argv + 1) *
					sizeof (char **))) {
				p = v;
				*p++ = cmd;
				if (*argv) argv++;
				while (*p++ = *argv++);
				(void) execv(getshell(), v);
			}
		}
		_exit(CMDERR);
		/*NOTREACHED*/
	default:
		(void) close(pio[cmdfd]);
		return (cmdproc[proc].fp = fdopen(pio[usrfd], mode));
	}
}

/*
 * close a stream opened by cmdopen()
 * -1 returned if cmdopen() had a problem
 * otherwise exit() status of command is returned
 */

static int
cmdclose(fp)
FILE	*fp;
{
	int	i;
	pid_t	p, pid;
	int		status;

	for (i = 0; i < MAXCMDS; i++)
		if (fp == cmdproc[i].fp) break;
	if (i >= MAXCMDS)
		return (-1);
	(void) fclose(fp);
	cmdproc[i].fp = 0;
	pid = cmdproc[i].pid;
	while ((p = wait(&status)) != pid && p != (pid_t)-1);
	if (p == pid) {
		status = (status >> 8) & CMDERR;
		if (status == CMDERR)
			status = -1;
	}
	else
		status = -1;
	return (status);
}

/*
 * return pointer to the full path name of the shell
 *
 * SHELL is read from the environment and must start with /
 *
 * if set-uid or set-gid then the executable and its containing
 * directory must not be writable by the real user
 *
 * /usr/bin/sh is returned by default
 */

char *
getshell()
{
	char	*s;
	char	*sh;
	uid_t	u;
	int	j;

	if (((sh = getenv("SHELL")) != 0) && *sh == '/') {
		if (u = getuid()) {
			if ((u != geteuid() || getgid() != getegid()) &&
					!access(sh, 2))
				goto defshell;
			s = strrchr(sh, '/');
			*s = 0;
			j = access(sh, 2);
			*s = '/';
			if (!j) goto defshell;
		}
		return (sh);
	}
defshell:
	return ("/usr/bin/sh");
}

/*
 * the following functions implement the added "-ls" option
 */

#include <utmpx.h>
#include <sys/mkdev.h>

struct		utmpx utmpx;
#define	NMAX	(sizeof (utmpx.ut_name))
#define	SCPYN(a, b)	(void) strncpy(a, b, NMAX)

#define	NUID	64
#define	NGID	64

static struct ncache {
	int	id;
	char	name[NMAX+1];
} nc[NUID], gc[NGID];

/*
 * This function assumes that the password file is hashed
 * (or some such) to allow fast access based on a name key.
 */
static char *
getname(uid_t uid)
{
	struct passwd *pw;
	int cp;

#if	(((NUID) & ((NUID) - 1)) != 0)
	cp = uid % (NUID);
#else
	cp = uid & ((NUID) - 1);
#endif
	if (uid >= 0 && nc[cp].id == uid && nc[cp].name[0])
		return (nc[cp].name);
	pw = getpwuid(uid);
	if (!pw)
		return (0);
	nc[cp].id = uid;
	SCPYN(nc[cp].name, pw->pw_name);
	return (nc[cp].name);
}

/*
 * This function assumes that the group file is hashed
 * (or some such) to allow fast access based on a name key.
 */
static char *
getgroup(gid_t gid)
{
	struct group *gr;
	int cp;

#if	(((NGID) & ((NGID) - 1)) != 0)
	cp = gid % (NGID);
#else
	cp = gid & ((NGID) - 1);
#endif
	if (gid >= 0 && gc[cp].id == gid && gc[cp].name[0])
		return (gc[cp].name);
	gr = getgrgid(gid);
	if (!gr)
		return (0);
	gc[cp].id = gid;
	SCPYN(gc[cp].name, gr->gr_name);
	return (gc[cp].name);
}

#define	permoffset(who)		((who) * 3)
#define	permission(who, type)	((type) >> permoffset(who))
#define	kbytes(bytes)		(((bytes) + 1023) / 1024)

static int
list(file, stp)
	char *file;
	struct stat *stp;
{
	char pmode[32], uname[32], gname[32], fsize[32], ftime[32];
	int trivial;

/*
 * Each line below contains the relevant permission (column 1) and character
 * shown when  the corresponding execute bit is either clear (column 2)
 * or set (column 3)
 * These permissions are as shown by ls(1b)
 */
	static long special[] = {	S_ISUID, 'S', 's',
					S_ISGID, 'S', 's',
					S_ISVTX, 'T', 't' };

	static time_t sixmonthsago = -1;
#ifdef	S_IFLNK
	char flink[MAXPATHLEN + 1];
#endif
	int who;
	char *cp;
	char *tailname;
	time_t now;
	long long ksize;

	if (file == NULL || stp == NULL)
		return (-1);

	(void) time(&now);
	if (sixmonthsago == -1)
		sixmonthsago = now - 6L*30L*24L*60L*60L;

	switch (stp->st_mode & S_IFMT) {
#ifdef	S_IFDIR
	case S_IFDIR:	/* directory */
		pmode[0] = 'd';
		break;
#endif
#ifdef	S_IFCHR
	case S_IFCHR:	/* character special */
		pmode[0] = 'c';
		break;
#endif
#ifdef	S_IFBLK
	case S_IFBLK:	/* block special */
		pmode[0] = 'b';
		break;
#endif
#ifdef	S_IFIFO
	case S_IFIFO:	/* fifo special */
		pmode[0] = 'p';
		break;
#endif
#ifdef	S_IFLNK
	case S_IFLNK:	/* symbolic link */
		pmode[0] = 'l';
		break;
#endif
#ifdef	S_IFSOCK
	case S_IFSOCK:	/* socket */
		pmode[0] = 's';
		break;
#endif
#ifdef	S_IFDOOR
	case S_IFDOOR:	/* door */
		pmode[0] = 'D';
		break;
#endif
#ifdef	S_IFREG
	case S_IFREG:	/* regular */
		pmode[0] = '-';
		break;
#endif
	default:
		pmode[0] = '?';
		break;
	}

	for (who = 0; who < 3; who++) {
		int is_exec =  stp->st_mode & permission(who, S_IEXEC)? 1 : 0;

		if (stp->st_mode & permission(who, S_IREAD))
			pmode[permoffset(who) + 1] = 'r';
		else
			pmode[permoffset(who) + 1] = '-';

		if (stp->st_mode & permission(who, S_IWRITE))
			pmode[permoffset(who) + 2] = 'w';
		else
			pmode[permoffset(who) + 2] = '-';

		if (stp->st_mode & special[who * 3])
			pmode[permoffset(who) + 3] =
				special[who * 3 + 1 + is_exec];
		else if (is_exec)
			pmode[permoffset(who) + 3] = 'x';
		else
			pmode[permoffset(who) + 3] = '-';
	}

	/*
	 * Need to get the tail of the file name, since we have
	 * already chdir()ed into the directory of the file
	 */

	tailname = gettail(file);

	trivial = acl_trivial(tailname);
	if (trivial == -1)
		trivial =  0;

	if (trivial == 1)
		pmode[permoffset(who) + 1] = '+';
	else
		pmode[permoffset(who) + 1] = ' ';

	pmode[permoffset(who) + 2] = '\0';

	/*
	 * Prepare uname and gname.  Always add a space afterwards
	 * to keep columns from running together.
	 */
	cp = getname(stp->st_uid);
	if (cp != NULL)
		(void) sprintf(uname, "%-8s ", cp);
	else
		(void) sprintf(uname, "%-8ld ", stp->st_uid);

	cp = getgroup(stp->st_gid);
	if (cp != NULL)
		(void) sprintf(gname, "%-8s ", cp);
	else
		(void) sprintf(gname, "%-8ld ", stp->st_gid);

	if (pmode[0] == 'b' || pmode[0] == 'c')
		(void) sprintf(fsize, "%3ld,%4ld",
			major(stp->st_rdev), minor(stp->st_rdev));
	else {
		(void) sprintf(fsize, (stp->st_size < 100000000) ?
			"%8lld" : "%lld", stp->st_size);
#ifdef	S_IFLNK
		if (pmode[0] == 'l') {


			who = readlink(tailname, flink, sizeof (flink) - 1);

			if (who >= 0)
				flink[who] = '\0';
			else
				flink[0] = '\0';
		}
#endif
	}

	cp = ctime(&stp->st_mtime);
	if (stp->st_mtime < sixmonthsago || stp->st_mtime > now)
		(void) sprintf(ftime, "%-7.7s %-4.4s", cp + 4, cp + 20);
	else
		(void) sprintf(ftime, "%-12.12s", cp + 4);

	(void) printf((stp->st_ino < 100000) ? "%5llu " :
		"%llu ", stp->st_ino);  /* inode #	*/
#ifdef	S_IFSOCK
	ksize = (long long) kbytes(ldbtob(stp->st_blocks)); /* kbytes */
#else
	ksize = (long long) kbytes(stp->st_size); /* kbytes */
#endif
	(void) printf((ksize < 10000) ? "%4lld " : "%lld ", ksize);
	(void) printf("%s %2ld %s%s%s %s %s%s%s\n",
		pmode,					/* protection	*/
		stp->st_nlink,				/* # of links	*/
		uname,					/* owner	*/
		gname,					/* group	*/
		fsize,					/* # of bytes	*/
		ftime,					/* modify time	*/
		file,					/* name		*/
#ifdef	S_IFLNK
		(pmode[0] == 'l') ? " -> " : "",
		(pmode[0] == 'l') ? flink  : ""		/* symlink	*/
#else
		"",
		""
#endif
);

	return (0);
}

static char *
new_string(char *s)
{
	char *p = strdup(s);

	if (p)
		return (p);
	(void) fprintf(stderr, gettext("%s: out of memory\n"), cmdname);
	exit(1);
	/*NOTREACHED*/
}

/*
 * Read remote file system types from REMOTE_FS into the
 * remote_fstypes array.
 */
static void
init_remote_fs()
{
	FILE    *fp;
	char    line_buf[LINEBUF_SIZE];

	if ((fp = fopen(REMOTE_FS, "r")) == NULL) {
		(void) fprintf(stderr,
			gettext("%s: Warning: can't open %s, ignored\n"),
				REMOTE_FS, cmdname);
		/* Use default string name for NFS */
		remote_fstypes[fstype_index++] = "nfs";
		return;
	}

	while (fgets(line_buf, sizeof (line_buf), fp) != NULL) {
		char buf[LINEBUF_SIZE];

		/* LINTED - unbounded string specifier */
		(void) sscanf(line_buf, "%s", buf);
		remote_fstypes[fstype_index++] = new_string(buf);

		if (fstype_index == N_FSTYPES)
			break;
	}
	(void) fclose(fp);
}

#define	NPERM	30			/* Largest machine */

/*
 * The PERM struct is the machine that builds permissions.  The p_special
 * field contains what permissions need to be checked at run-time in
 * getmode().  This is one of 'X', 'u', 'g', or 'o'.  It contains '\0' to
 * indicate normal processing.
 */
typedef	struct	PERMST	{
	ushort_t	p_who;		/* Range of permission (e.g. ugo) */
	ushort_t	p_perm;		/* Bits to turn on, off, assign */
	uchar_t		p_op;		/* Operation: + - = */
	uchar_t		p_special;	/* Special handling? */
}	PERMST;

#ifndef	S_ISVTX
#define	S_ISVTX	0			/* Not .1 */
#endif

/* Mask values */
#define	P_A	(S_ISUID|S_ISGID|S_ISVTX|S_IRWXU|S_IRWXG|S_IRWXO) /* allbits */
#define	P_U	(S_ISUID|S_ISVTX|S_IRWXU)		/* user */
#define	P_G	(S_ISGID|S_ISVTX|S_IRWXG)		/* group */
#define	P_O	(S_ISVTX|S_IRWXO)			/* other */

static	int	iswho(int c);
static	int	isop(int c);
static	int	isperm(PERMST *pp, int c);

static	PERMST	machine[NPERM];		/* Permission construction machine */
static	PERMST	*endp;			/* Last used PERM structure */

static	uint_t	nowho;			/* No who for this mode (DOS kludge) */

/*
 * Read an ASCII string containing the symbolic/octal mode and
 * compile an automaton that recognizes it.  The return value
 * is NULL if everything is OK, otherwise it is -1.
 */
static int
readmode(ascmode)
const char *ascmode;
{
	const char *amode = ascmode;
	PERMST *pp;
	int seen_X;

	nowho = 0;
	seen_X = 0;
	pp = &machine[0];
	if (*amode >= '0' && *amode <= '7') {
		int mode;

		mode = 0;
		while (*amode >= '0' && *amode <= '7')
			mode = (mode<<3) + *amode++ - '0';
		if (*amode != '\0')
			return (-1);
#if	S_ISUID != 04000 || S_ISGID != 02000 || \
	S_IRUSR != 0400 || S_IWUSR != 0200 || S_IXUSR != 0100 || \
	S_IRGRP != 0040 || S_IWGRP != 0020 || S_IXGRP != 0010 || \
	S_IROTH != 0004 || S_IWOTH != 0002 || S_IXOTH != 0001
		/*
		 * There is no requirement of the octal mode bits being
		 * the same as the S_ macros.
		 */
	{
		mode_t mapping[] = {
			S_IXOTH, S_IWOTH, S_IROTH,
			S_IXGRP, S_IWGRP, S_IRGRP,
			S_IXUSR, S_IWUSR, S_IRUSR,
			S_ISGID, S_ISUID,
			0
		};
		int i, newmode = 0;

		for (i = 0; mapping[i] != 0; i++)
			if (mode & (1<<i))
				newmode |= mapping[i];
		mode = newmode;
	}
#endif
		pp->p_who = P_A;
		pp->p_perm = mode;
		pp->p_op = '=';
	} else	for (;;) {
		int t;
		int who = 0;

		while ((t = iswho(*amode)) != 0) {
			++amode;
			who |= t;
		}
		if (who == 0) {
			mode_t currmask;
			(void) umask(currmask = umask((mode_t)0));

			/*
			 * If no who specified, must use contents of
			 * umask to determine which bits to flip.  This
			 * is POSIX/V7/BSD behaviour, but not SVID.
			 */
			who = (~currmask)&P_A;
			++nowho;
		} else
			nowho = 0;
	samewho:
		if (!isop(pp->p_op = *amode++))
			return (-1);
		pp->p_perm = 0;
		pp->p_special = 0;
		while ((t = isperm(pp, *amode)) != 0) {
			if (pp->p_special == 'X') {
				seen_X = 1;

				if (pp->p_perm != 0) {
					ushort_t op;

					/*
					 * Remember the 'who' for the previous
					 * transformation.
					 */
					pp->p_who = who;
					pp->p_special = 0;

					op = pp->p_op;

					/* Keep 'X' separate */
					++pp;
					pp->p_special = 'X';
					pp->p_op = op;
				}
			} else if (seen_X) {
				ushort_t op;

				/* Remember the 'who' for the X */
				pp->p_who = who;

				op = pp->p_op;

				/* Keep 'X' separate */
				++pp;
				pp->p_perm = 0;
				pp->p_special = 0;
				pp->p_op = op;
			}
			++amode;
			pp->p_perm |= t;
		}

		/*
		 * These returned 0, but were actually parsed, so
		 * don't look at them again.
		 */
		switch (pp->p_special) {
		case 'u':
		case 'g':
		case 'o':
			++amode;
			break;
		}
		pp->p_who = who;
		switch (*amode) {
		case '\0':
			break;

		case ',':
			++amode;
			++pp;
			continue;

		default:
			++pp;
			goto samewho;
		}
		break;
	}
	endp = pp;
	return (NULL);
}

/*
 * Given a character from the mode, return the associated
 * value as who (user designation) mask or 0 if this isn't valid.
 */
static int
iswho(c)
int c;
{
	switch (c) {
	case 'a':
		return (P_A);

	case 'u':
		return (P_U);

	case 'g':
		return (P_G);

	case 'o':
		return (P_O);

	default:
		return (0);
	}
	/* NOTREACHED */
}

/*
 * Return non-zero if this is a valid op code
 * in a symbolic mode.
 */
static int
isop(c)
int c;
{
	switch (c) {
	case '+':
	case '-':
	case '=':
		return (1);

	default:
		return (0);
	}
	/* NOTREACHED */
}

/*
 * Return the permission bits implied by this character or 0
 * if it isn't valid.  Also returns 0 when the pseudo-permissions 'u', 'g', or
 * 'o' are used, and sets pp->p_special to the one used.
 */
static int
isperm(pp, c)
PERMST *pp;
int c;
{
	switch (c) {
	case 'u':
	case 'g':
	case 'o':
		pp->p_special = c;
		return (0);

	case 'r':
		return (S_IRUSR|S_IRGRP|S_IROTH);

	case 'w':
		return (S_IWUSR|S_IWGRP|S_IWOTH);

	case 'x':
		return (S_IXUSR|S_IXGRP|S_IXOTH);

#if S_ISVTX != 0
	case 't':
		return (S_ISVTX);
#endif

	case 'X':
		pp->p_special = 'X';
		return (S_IXUSR|S_IXGRP|S_IXOTH);

#if S_ISVTX != 0
	case 'a':
		return (S_ISVTX);
#endif

	case 'h':
		return (S_ISUID);

	/*
	 * This change makes:
	 *	chmod +s file
	 * set the system bit on dos but means that
	 *	chmod u+s file
	 *	chmod g+s file
	 *	chmod a+s file
	 * are all like UNIX.
	 */
	case 's':
		return (nowho ? S_ISGID : S_ISGID|S_ISUID);

	default:
		return (0);
	}
	/* NOTREACHED */
}

/*
 * Execute the automaton that is created by readmode()
 * to generate the final mode that will be used.  This
 * code is passed a starting mode that is usually the original
 * mode of the file being changed (or 0).  Note that this mode must contain
 * the file-type bits as well, so that S_ISDIR will succeed on directories.
 */
static mode_t
getmode(mode_t startmode)
{
	PERMST *pp;
	mode_t temp;
	mode_t perm;

	for (pp = &machine[0]; pp <= endp; ++pp) {
		perm = (mode_t)0;
		/*
		 * For the special modes 'u', 'g' and 'o', the named portion
		 * of the mode refers to after the previous clause has been
		 * processed, while the 'X' mode refers to the contents of the
		 * mode before any clauses have been processed.
		 *
		 * References: P1003.2/D11.2, Section 4.7.7,
		 *  lines 2568-2570, 2578-2583
		 */
		switch (pp->p_special) {
		case 'u':
			temp = startmode & S_IRWXU;
			if (temp & (S_IRUSR|S_IRGRP|S_IROTH))
				perm |= ((S_IRUSR|S_IRGRP|S_IROTH) &
				    pp->p_who);
			if (temp & (S_IWUSR|S_IWGRP|S_IWOTH))
				perm |= ((S_IWUSR|S_IWGRP|S_IWOTH) & pp->p_who);
			if (temp & (S_IXUSR|S_IXGRP|S_IXOTH))
				perm |= ((S_IXUSR|S_IXGRP|S_IXOTH) & pp->p_who);
			break;

		case 'g':
			temp = startmode & S_IRWXG;
			if (temp & (S_IRUSR|S_IRGRP|S_IROTH))
				perm |= ((S_IRUSR|S_IRGRP|S_IROTH) & pp->p_who);
			if (temp & (S_IWUSR|S_IWGRP|S_IWOTH))
				perm |= ((S_IWUSR|S_IWGRP|S_IWOTH) & pp->p_who);
			if (temp & (S_IXUSR|S_IXGRP|S_IXOTH))
				perm |= ((S_IXUSR|S_IXGRP|S_IXOTH) & pp->p_who);
			break;

		case 'o':
			temp = startmode & S_IRWXO;
			if (temp & (S_IRUSR|S_IRGRP|S_IROTH))
				perm |= ((S_IRUSR|S_IRGRP|S_IROTH) & pp->p_who);
			if (temp & (S_IWUSR|S_IWGRP|S_IWOTH))
				perm |= ((S_IWUSR|S_IWGRP|S_IWOTH) & pp->p_who);
			if (temp & (S_IXUSR|S_IXGRP|S_IXOTH))
				perm |= ((S_IXUSR|S_IXGRP|S_IXOTH) & pp->p_who);
			break;

		case 'X':
			perm = pp->p_perm;
			break;

		default:
			perm = pp->p_perm;
			break;
		}
		switch (pp->p_op) {
		case '-':
			startmode &= ~(perm & pp->p_who);
			break;

		case '=':
			startmode &= ~pp->p_who;
			/* FALLTHROUGH */
		case '+':
			startmode |= (perm & pp->p_who);
			break;
		}
	}
	return (startmode);
}

/*
 * Returns the last component of a path name, unless it is
 * an absolute path, in which case it returns the whole path
 */
static char
*gettail(char *fname)
{
	char	*base = fname;

	if (*fname != '/') {
		if ((base = strrchr(fname, '/')) != NULL)
			base++;
		else
			base = fname;
	}
	return (base);
}