← Commit list

bc54cffc8

Denis Vlasenko

2007-02-23

FAILED Duration: 13s

Subject

ash: cleanup part 9

Binary

No binary (build failed)

Architecture & Compiler Flags

Architecture: x86_64-linux-gnu Compiler: gcc (Ubuntu 11.4.0-1ubuntu1~22.04.3) 11.4.0

—

Build Log

(log yok)

Commit Diff GitHub →

shell/ash.c +2868 -2947

shell/ash.c+2868 -2947

@@ -326,7 +326,7 @@ onsig(int signo)
	}


-	/* ============ stdout/stderr output */
+	/* ============ Stdout/stderr output */

	static void
	outstr(const char p, FILE file)
@@ -2351,37 +2351,6 @@ pwdcmd(int argc, char **argv)
	/* ============ Unsorted yet */


-	/* expand.h */
-
-	struct arglist {
-	struct strlist *list;
-	struct strlist **lastp;
-	};
-
-	/*
-	* expandarg() flags
-	*/
-	#define EXP_FULL 0x1 /* perform word splitting & file globbing */
-	#define EXP_TILDE 0x2 /* do normal tilde expansion */
-	#define EXP_VARTILDE 0x4 /* expand tildes in an assignment */
-	#define EXP_REDIR 0x8 /* file glob for a redirection (1 match only) */
-	#define EXP_CASE 0x10 /* keeps quotes around for CASE pattern */
-	#define EXP_RECORD 0x20 /* need to record arguments for ifs breakup */
-	#define EXP_VARTILDE2 0x40 /* expand tildes after colons only */
-	#define EXP_WORD 0x80 /* expand word in parameter expansion */
-	#define EXP_QWORD 0x100 /* expand word in quoted parameter expansion */
-
-
-	static void expandarg(union node , struct arglist , int);
-	#define rmescapes(p) _rmescapes((p), 0)
-	static char _rmescapes(char , int);
-	static int casematch(union node , char );
-
-	#if ENABLE_ASH_MATH_SUPPORT
-	static void expari(int);
-	#endif
-
-
	/* parser.h */

	/* control characters in argument strings */
@@ -3210,8 +3179,6 @@ static int redirectsafe(union node *, int);
	static void clear_traps(void);
	static void setsignal(int);
	static int dotrap(void);
-	static void setinteractive(int);
-	static void exitshell(void) ATTRIBUTE_NORETURN;


	static int is_safe_applet(char *name)
@@ -3445,3289 +3412,3265 @@ unaliascmd(int argc, char **argv)
	#endif /* ASH_ALIAS */


-	/* ============ eval.c */
+	/* ============ Routines to expand arguments to commands
+	*
+	* We have to deal with backquotes, shell variables, and file metacharacters.
+	*/

-	/* flags in argument to evaltree */
-	#define EV_EXIT 01 /* exit after evaluating tree */
-	#define EV_TESTED 02 /* exit status is checked; ignore -e flag */
-	#define EV_BACKCMD 04 /* command executing within back quotes */
+	/*
+	* expandarg flags
+	*/
+	#define EXP_FULL 0x1 /* perform word splitting & file globbing */
+	#define EXP_TILDE 0x2 /* do normal tilde expansion */
+	#define EXP_VARTILDE 0x4 /* expand tildes in an assignment */
+	#define EXP_REDIR 0x8 /* file glob for a redirection (1 match only) */
+	#define EXP_CASE 0x10 /* keeps quotes around for CASE pattern */
+	#define EXP_RECORD 0x20 /* need to record arguments for ifs breakup */
+	#define EXP_VARTILDE2 0x40 /* expand tildes after colons only */
+	#define EXP_WORD 0x80 /* expand word in parameter expansion */
+	#define EXP_QWORD 0x100 /* expand word in quoted parameter expansion */
+	/*
+	* _rmescape() flags
+	*/
+	#define RMESCAPE_ALLOC 0x1 /* Allocate a new string */
+	#define RMESCAPE_GLOB 0x2 /* Add backslashes for glob */
+	#define RMESCAPE_QUOTED 0x4 /* Remove CTLESC unless in quotes */
+	#define RMESCAPE_GROW 0x8 /* Grow strings instead of stalloc */
+	#define RMESCAPE_HEAP 0x10 /* Malloc strings instead of stalloc */

-	/* forward declarations - evaluation is faily recursive business... */
-	static void evalloop(union node *, int);
-	static void evalfor(union node *, int);
-	static void evalcase(union node *, int);
-	static void evalsubshell(union node *, int);
-	static void expredir(union node *);
-	static void evalpipe(union node *, int);
-	static void evalcommand(union node *, int);
-	static int evalbltin(const struct builtincmd , int, char *);
-	static int evalfun(struct funcnode , int, char *, int);
-	static void prehash(union node *);
+	/*
+	* Structure specifying which parts of the string should be searched
+	* for IFS characters.
+	*/
+	struct ifsregion {
+	struct ifsregion next; / next region in list */
+	int begoff; /* offset of start of region */
+	int endoff; /* offset of end of region */
+	int nulonly; /* search for nul bytes only */
+	};
+
+	struct arglist {
+	struct strlist *list;
+	struct strlist **lastp;
+	};
+
+	/* output of current string */
+	static char *expdest;
+	/* list of back quote expressions */
+	static struct nodelist *argbackq;
+	/* first struct in list of ifs regions */
+	static struct ifsregion ifsfirst;
+	/* last struct in list */
+	static struct ifsregion *ifslastp;
+	/* holds expanded arg list */
+	static struct arglist exparg;

	/*
-	* Evaluate a parse tree. The value is left in the global variable
-	* exitstatus.
+	* Our own itoa().
	*/
-	static void
-	evaltree(union node *n, int flags)
+	static int
+	cvtnum(arith_t num)
	{
-	int checkexit = 0;
-	void (evalfn)(union node , int);
-	unsigned isor;
-	int status;
-	if (n == NULL) {
-	TRACE(("evaltree(NULL) called\n"));
-	goto out;
-	}
-	TRACE(("pid %d, evaltree(%p: %d, %d) called\n",
-	getpid(), n, n->type, flags));
-	switch (n->type) {
-	default:
-	#if DEBUG
-	out1fmt("Node type = %d\n", n->type);
-	fflush(stdout);
-	break;
-	#endif
-	case NNOT:
-	evaltree(n->nnot.com, EV_TESTED);
-	status = !exitstatus;
-	goto setstatus;
-	case NREDIR:
-	expredir(n->nredir.redirect);
-	status = redirectsafe(n->nredir.redirect, REDIR_PUSH);
-	if (!status) {
-	evaltree(n->nredir.n, flags & EV_TESTED);
-	status = exitstatus;
-	}
-	popredir(0);
-	goto setstatus;
-	case NCMD:
-	evalfn = evalcommand;
-	checkexit:
-	if (eflag && !(flags & EV_TESTED))
-	checkexit = ~0;
-	goto calleval;
-	case NFOR:
-	evalfn = evalfor;
-	goto calleval;
-	case NWHILE:
-	case NUNTIL:
-	evalfn = evalloop;
-	goto calleval;
-	case NSUBSHELL:
-	case NBACKGND:
-	evalfn = evalsubshell;
-	goto calleval;
-	case NPIPE:
-	evalfn = evalpipe;
-	goto checkexit;
-	case NCASE:
-	evalfn = evalcase;
-	goto calleval;
-	case NAND:
-	case NOR:
-	case NSEMI:
-	#if NAND + 1 != NOR
-	#error NAND + 1 != NOR
-	#endif
-	#if NOR + 1 != NSEMI
-	#error NOR + 1 != NSEMI
-	#endif
-	isor = n->type - NAND;
-	evaltree(
-	n->nbinary.ch1,
-	(flags \| ((isor >> 1) - 1)) & EV_TESTED
-	);
-	if (!exitstatus == isor)
-	break;
-	if (!evalskip) {
-	n = n->nbinary.ch2;
-	evaln:
-	evalfn = evaltree;
-	calleval:
-	evalfn(n, flags);
-	break;
-	}
-	break;
-	case NIF:
-	evaltree(n->nif.test, EV_TESTED);
-	if (evalskip)
-	break;
-	if (exitstatus == 0) {
-	n = n->nif.ifpart;
-	goto evaln;
-	} else if (n->nif.elsepart) {
-	n = n->nif.elsepart;
-	goto evaln;
-	}
-	goto success;
-	case NDEFUN:
-	defun(n->narg.text, n->narg.next);
-	success:
-	status = 0;
-	setstatus:
-	exitstatus = status;
-	break;
-	}
-	out:
-	if ((checkexit & exitstatus))
-	evalskip \|= SKIPEVAL;
-	else if (pendingsigs && dotrap())
-	goto exexit;
-
-	if (flags & EV_EXIT) {
-	exexit:
-	raise_exception(EXEXIT);
-	}
-	}
+	int len;

-	#if !defined(__alpha__) \|\| (defined(__GNUC__) && __GNUC__ >= 3)
-	static
+	expdest = makestrspace(32, expdest);
+	#if ENABLE_ASH_MATH_SUPPORT_64
+	len = fmtstr(expdest, 32, "%lld", (long long) num);
+	#else
+	len = fmtstr(expdest, 32, "%ld", num);
	#endif
-	void evaltreenr(union node *, int) __attribute__ ((alias("evaltree"),__noreturn__));
-
-	static int loopnest; /* current loop nesting level */
+	STADJUST(len, expdest);
+	return len;
+	}

-	static void
-	evalloop(union node *n, int flags)
+	static size_t
+	esclen(const char start, const char p)
	{
-	int status;
-
-	loopnest++;
-	status = 0;
-	flags &= EV_TESTED;
-	for (;;) {
-	int i;
+	size_t esc = 0;

-	evaltree(n->nbinary.ch1, EV_TESTED);
-	if (evalskip) {
-	skipping:
-	if (evalskip == SKIPCONT && --skipcount <= 0) {
-	evalskip = 0;
-	continue;
-	}
-	if (evalskip == SKIPBREAK && --skipcount <= 0)
-	evalskip = 0;
-	break;
-	}
-	i = exitstatus;
-	if (n->type != NWHILE)
-	i = !i;
-	if (i != 0)
-	break;
-	evaltree(n->nbinary.ch2, flags);
-	status = exitstatus;
-	if (evalskip)
-	goto skipping;
+	while (p > start && *--p == CTLESC) {
+	esc++;
	}
-	loopnest--;
-	exitstatus = status;
+	return esc;
	}

-	static void
-	evalfor(union node *n, int flags)
+	/*
+	* Remove any CTLESC characters from a string.
+	*/
+	static char *
+	_rmescapes(char *str, int flag)
	{
-	struct arglist arglist;
-	union node *argp;
-	struct strlist *sp;
-	struct stackmark smark;
+	char p, q, *r;
+	static const char qchars[] = { CTLESC, CTLQUOTEMARK, 0 };
+	unsigned inquotes;
+	int notescaped;
+	int globbing;

-	setstackmark(&smark);
-	arglist.lastp = &arglist.list;
-	for (argp = n->nfor.args; argp; argp = argp->narg.next) {
-	expandarg(argp, &arglist, EXP_FULL \| EXP_TILDE \| EXP_RECORD);
-	/* XXX */
-	if (evalskip)
-	goto out;
+	p = strpbrk(str, qchars);
+	if (!p) {
+	return str;
	}
-	*arglist.lastp = NULL;
+	q = p;
+	r = str;
+	if (flag & RMESCAPE_ALLOC) {
+	size_t len = p - str;
+	size_t fulllen = len + strlen(p) + 1;

-	exitstatus = 0;
-	loopnest++;
-	flags &= EV_TESTED;
-	for (sp = arglist.list; sp; sp = sp->next) {
-	setvar(n->nfor.var, sp->text, 0);
-	evaltree(n->nfor.body, flags);
-	if (evalskip) {
-	if (evalskip == SKIPCONT && --skipcount <= 0) {
-	evalskip = 0;
-	continue;
+	if (flag & RMESCAPE_GROW) {
+	r = makestrspace(fulllen, expdest);
+	} else if (flag & RMESCAPE_HEAP) {
+	r = ckmalloc(fulllen);
+	} else {
+	r = stalloc(fulllen);
+	}
+	q = r;
+	if (len > 0) {
+	q = memcpy(q, str, len) + len;
+	}
+	}
+	inquotes = (flag & RMESCAPE_QUOTED) ^ RMESCAPE_QUOTED;
+	globbing = flag & RMESCAPE_GLOB;
+	notescaped = globbing;
+	while (*p) {
+	if (*p == CTLQUOTEMARK) {
+	inquotes = ~inquotes;
+	p++;
+	notescaped = globbing;
+	continue;
+	}
+	if (*p == '\\') {
+	/* naked back slash */
+	notescaped = 0;
+	goto copy;
+	}
+	if (*p == CTLESC) {
+	p++;
+	if (notescaped && inquotes && *p != '/') {
+	*q++ = '\\';
	}
-	if (evalskip == SKIPBREAK && --skipcount <= 0)
-	evalskip = 0;
-	break;
	}
+	notescaped = globbing;
+	copy:
+	q++ = p++;
	}
-	loopnest--;
-	out:
-	popstackmark(&smark);
+	*q = '\0';
+	if (flag & RMESCAPE_GROW) {
+	expdest = r;
+	STADJUST(q - r + 1, expdest);
+	}
+	return r;
	}
+	#define rmescapes(p) _rmescapes((p), 0)

-	static void
-	evalcase(union node *n, int flags)
-	{
-	union node *cp;
-	union node *patp;
-	struct arglist arglist;
-	struct stackmark smark;
+	#define pmatch(a, b) !fnmatch((a), (b), 0)

-	setstackmark(&smark);
-	arglist.lastp = &arglist.list;
-	expandarg(n->ncase.expr, &arglist, EXP_TILDE);
-	exitstatus = 0;
-	for (cp = n->ncase.cases; cp && evalskip == 0; cp = cp->nclist.next) {
-	for (patp = cp->nclist.pattern; patp; patp = patp->narg.next) {
-	if (casematch(patp, arglist.list->text)) {
-	if (evalskip == 0) {
-	evaltree(cp->nclist.body, flags);
-	}
-	goto out;
-	}
-	}
+	/*
+	* Prepare a pattern for a expmeta (internal glob(3)) call.
+	*
+	* Returns an stalloced string.
+	*/
+	static char *
+	preglob(const char *pattern, int quoted, int flag)
+	{
+	flag \|= RMESCAPE_GLOB;
+	if (quoted) {
+	flag \|= RMESCAPE_QUOTED;
	}
-	out:
-	popstackmark(&smark);
+	return _rmescapes((char *)pattern, flag);
	}

	/*
-	* Kick off a subshell to evaluate a tree.
+	* Put a string on the stack.
	*/
	static void
-	evalsubshell(union node *n, int flags)
+	memtodest(const char *p, size_t len, int syntax, int quotes)
	{
-	struct job *jp;
-	int backgnd = (n->type == NBACKGND);
-	int status;
+	char *q = expdest;

-	expredir(n->nredir.redirect);
-	if (!backgnd && flags & EV_EXIT && !trap[0])
-	goto nofork;
-	INT_OFF;
-	jp = makejob(n, 1);
-	if (forkshell(jp, n, backgnd) == 0) {
-	INT_ON;
-	flags \|= EV_EXIT;
-	if (backgnd)
-	flags &=~ EV_TESTED;
-	nofork:
-	redirect(n->nredir.redirect, 0);
-	evaltreenr(n->nredir.n, flags);
-	/* never returns */
+	q = makestrspace(len * 2, q);
+
+	while (len--) {
+	int c = SC2INT(*p++);
+	if (!c)
+	continue;
+	if (quotes && (SIT(c, syntax) == CCTL \|\| SIT(c, syntax) == CBACK))
+	USTPUTC(CTLESC, q);
+	USTPUTC(c, q);
	}
-	status = 0;
-	if (! backgnd)
-	status = waitforjob(jp);
-	exitstatus = status;
-	INT_ON;
+
+	expdest = q;
+	}
+
+	static void
+	strtodest(const char *p, int syntax, int quotes)
+	{
+	memtodest(p, strlen(p), syntax, quotes);
	}

	/*
-	* Compute the names of the files in a redirection list.
+	* Record the fact that we have to scan this region of the
+	* string for IFS characters.
	*/
	static void
-	expredir(union node *n)
+	recordregion(int start, int end, int nulonly)
	{
-	union node *redir;
-
-	for (redir = n; redir; redir = redir->nfile.next) {
-	struct arglist fn;
+	struct ifsregion *ifsp;

-	memset(&fn, 0, sizeof(fn));
-	fn.lastp = &fn.list;
-	switch (redir->type) {
-	case NFROMTO:
-	case NFROM:
-	case NTO:
-	case NCLOBBER:
-	case NAPPEND:
-	expandarg(redir->nfile.fname, &fn, EXP_TILDE \| EXP_REDIR);
-	redir->nfile.expfname = fn.list->text;
-	break;
-	case NFROMFD:
-	case NTOFD:
-	if (redir->ndup.vname) {
-	expandarg(redir->ndup.vname, &fn, EXP_FULL \| EXP_TILDE);
-	if (fn.list == NULL)
-	ash_msg_and_raise_error("redir error");
-	fixredir(redir, fn.list->text, 1);
-	}
-	break;
-	}
+	if (ifslastp == NULL) {
+	ifsp = &ifsfirst;
+	} else {
+	INT_OFF;
+	ifsp = ckmalloc(sizeof(*ifsp));
+	ifsp->next = NULL;
+	ifslastp->next = ifsp;
+	INT_ON;
	}
+	ifslastp = ifsp;
+	ifslastp->begoff = start;
+	ifslastp->endoff = end;
+	ifslastp->nulonly = nulonly;
	}

-	/*
-	* Evaluate a pipeline. All the processes in the pipeline are children
-	* of the process creating the pipeline. (This differs from some versions
-	* of the shell, which make the last process in a pipeline the parent
-	* of all the rest.)
-	*/
	static void
-	evalpipe(union node *n, int flags)
+	removerecordregions(int endoff)
	{
-	struct job *jp;
-	struct nodelist *lp;
-	int pipelen;
-	int prevfd;
-	int pip[2];
+	if (ifslastp == NULL)
+	return;

-	TRACE(("evalpipe(0x%lx) called\n", (long)n));
-	pipelen = 0;
-	for (lp = n->npipe.cmdlist; lp; lp = lp->next)
-	pipelen++;
-	flags \|= EV_EXIT;
-	INT_OFF;
-	jp = makejob(n, pipelen);
-	prevfd = -1;
-	for (lp = n->npipe.cmdlist; lp; lp = lp->next) {
-	prehash(lp->n);
-	pip[1] = -1;
-	if (lp->next) {
-	if (pipe(pip) < 0) {
-	close(prevfd);
-	ash_msg_and_raise_error("Pipe call failed");
-	}
-	}
-	if (forkshell(jp, lp->n, n->npipe.backgnd) == 0) {
+	if (ifsfirst.endoff > endoff) {
+	while (ifsfirst.next != NULL) {
+	struct ifsregion *ifsp;
+	INT_OFF;
+	ifsp = ifsfirst.next->next;
+	free(ifsfirst.next);
+	ifsfirst.next = ifsp;
	INT_ON;
-	if (pip[1] >= 0) {
-	close(pip[0]);
-	}
-	if (prevfd > 0) {
-	dup2(prevfd, 0);
-	close(prevfd);
-	}
-	if (pip[1] > 1) {
-	dup2(pip[1], 1);
+	}
+	if (ifsfirst.begoff > endoff)
+	ifslastp = NULL;
+	else {
+	ifslastp = &ifsfirst;
+	ifsfirst.endoff = endoff;
+	}
+	return;
+	}
+
+	ifslastp = &ifsfirst;
+	while (ifslastp->next && ifslastp->next->begoff < endoff)
+	ifslastp=ifslastp->next;
+	while (ifslastp->next != NULL) {
+	struct ifsregion *ifsp;
+	INT_OFF;
+	ifsp = ifslastp->next->next;
+	free(ifslastp->next);
+	ifslastp->next = ifsp;
+	INT_ON;
+	}
+	if (ifslastp->endoff > endoff)
+	ifslastp->endoff = endoff;
+	}
+
+	static char *
+	exptilde(char startp, char p, int flag)
+	{
+	char c;
+	char *name;
+	struct passwd *pw;
+	const char *home;
+	int quotes = flag & (EXP_FULL \| EXP_CASE);
+	int startloc;
+
+	name = p + 1;
+
+	while ((c = *++p) != '\0') {
+	switch (c) {
+	case CTLESC:
+	return startp;
+	case CTLQUOTEMARK:
+	return startp;
+	case ':':
+	if (flag & EXP_VARTILDE)
+	goto done;
+	break;
+	case '/':
+	case CTLENDVAR:
+	goto done;
+	}
+	}
+	done:
+	*p = '\0';
+	if (*name == '\0') {
+	home = lookupvar(homestr);
+	} else {
+	pw = getpwnam(name);
+	if (pw == NULL)
+	goto lose;
+	home = pw->pw_dir;
+	}
+	if (!home \|\| !*home)
+	goto lose;
+	*p = c;
+	startloc = expdest - (char *)stackblock();
+	strtodest(home, SQSYNTAX, quotes);
+	recordregion(startloc, expdest - (char *)stackblock(), 0);
+	return p;
+	lose:
+	*p = c;
+	return startp;
+	}
+
+	/*
+	* Execute a command inside back quotes. If it's a builtin command, we
+	* want to save its output in a block obtained from malloc. Otherwise
+	* we fork off a subprocess and get the output of the command via a pipe.
+	* Should be called with interrupts off.
+	*/
+	struct backcmd { /* result of evalbackcmd */
+	int fd; /* file descriptor to read from */
+	char buf; / buffer */
+	int nleft; /* number of chars in buffer */
+	struct job jp; / job structure for command */
+	};
+
+	/* These forward decls are needed to use "eval" code for backticks handling: */
+	static int back_exitstatus; /* exit status of backquoted command */
+	#define EV_EXIT 01 /* exit after evaluating tree */
+	static void evaltree(union node *, int);
+
+	static void
+	evalbackcmd(union node n, struct backcmd result)
+	{
+	int saveherefd;
+
+	result->fd = -1;
+	result->buf = NULL;
+	result->nleft = 0;
+	result->jp = NULL;
+	if (n == NULL) {
+	goto out;
+	}
+
+	saveherefd = herefd;
+	herefd = -1;
+
+	{
+	int pip[2];
+	struct job *jp;
+
+	if (pipe(pip) < 0)
+	ash_msg_and_raise_error("Pipe call failed");
+	jp = makejob(n, 1);
+	if (forkshell(jp, n, FORK_NOJOB) == 0) {
+	FORCE_INT_ON;
+	close(pip[0]);
+	if (pip[1] != 1) {
+	close(1);
+	copyfd(pip[1], 1);
	close(pip[1]);
	}
-	evaltreenr(lp->n, flags);
-	/* never returns */
+	eflag = 0;
+	evaltree(n, EV_EXIT); /* actually evaltreenr... */
+	/* NOTREACHED */
	}
-	if (prevfd >= 0)
-	close(prevfd);
-	prevfd = pip[0];
	close(pip[1]);
+	result->fd = pip[0];
+	result->jp = jp;
	}
-	if (n->npipe.backgnd == 0) {
-	exitstatus = waitforjob(jp);
-	TRACE(("evalpipe: job done exit status %d\n", exitstatus));
-	}
-	INT_ON;
+	herefd = saveherefd;
+	out:
+	TRACE(("evalbackcmd done: fd=%d buf=0x%x nleft=%d jp=0x%x\n",
+	result->fd, result->buf, result->nleft, result->jp));
	}

-	#if ENABLE_ASH_CMDCMD
-	static char **
-	parse_command_args(char argv, const char path)
+	/*
+	* Expand stuff in backwards quotes.
+	*/
+	static void
+	expbackq(union node *cmd, int quoted, int quotes)
	{
-	char *cp, c;
+	struct backcmd in;
+	int i;
+	char buf[128];
+	char *p;
+	char *dest;
+	int startloc;
+	int syntax = quoted? DQSYNTAX : BASESYNTAX;
+	struct stackmark smark;
+
+	INT_OFF;
+	setstackmark(&smark);
+	dest = expdest;
+	startloc = dest - (char *)stackblock();
+	grabstackstr(dest);
+	evalbackcmd(cmd, &in);
+	popstackmark(&smark);

+	p = in.buf;
+	i = in.nleft;
+	if (i == 0)
+	goto read;
	for (;;) {
-	cp = *++argv;
-	if (!cp)
-	return 0;
-	if (*cp++ != '-')
-	break;
-	c = *cp++;
-	if (!c)
+	memtodest(p, i, syntax, quotes);
+	read:
+	if (in.fd < 0)
	break;
-	if (c == '-' && !*cp) {
-	argv++;
+	i = safe_read(in.fd, buf, sizeof(buf));
+	TRACE(("expbackq: read returns %d\n", i));
+	if (i <= 0)
	break;
-	}
-	do {
-	switch (c) {
-	case 'p':
-	*path = defpath;
-	break;
-	default:
-	/* run 'typecmd' for other options */
-	return 0;
-	}
-	c = *cp++;
-	} while (c);
+	p = buf;
	}
-	return argv;
+
+	if (in.buf)
+	free(in.buf);
+	if (in.fd >= 0) {
+	close(in.fd);
+	back_exitstatus = waitforjob(in.jp);
+	}
+	INT_ON;
+
+	/* Eat all trailing newlines */
+	dest = expdest;
+	for (; dest > (char *)stackblock() && dest[-1] == '\n';)
+	STUNPUTC(dest);
+	expdest = dest;
+
+	if (quoted == 0)
+	recordregion(startloc, dest - (char *)stackblock(), 0);
+	TRACE(("evalbackq: size=%d: \"%.*s\"\n",
+	(dest - (char *)stackblock()) - startloc,
+	(dest - (char *)stackblock()) - startloc,
+	stackblock() + startloc));
	}
-	#endif

-	/* Forward declarations for builtintab[] */
-	#if JOBS
-	static int fg_bgcmd(int, char **);
-	#endif
-	static int breakcmd(int, char **);
-	#if ENABLE_ASH_CMDCMD
-	static int commandcmd(int, char **);
-	#endif
-	static int dotcmd(int, char **);
-	static int evalcmd(int, char **);
-	#if ENABLE_ASH_BUILTIN_ECHO
-	static int echocmd(int, char **);
-	#endif
-	#if ENABLE_ASH_BUILTIN_TEST
-	static int testcmd(int, char **);
-	#endif
-	static int execcmd(int, char **);
-	static int exitcmd(int, char **);
-	static int exportcmd(int, char **);
-	static int falsecmd(int, char **);
-	#if ENABLE_ASH_GETOPTS
-	static int getoptscmd(int, char **);
-	#endif
-	static int hashcmd(int, char **);
-	#if !ENABLE_FEATURE_SH_EXTRA_QUIET
-	static int helpcmd(int argc, char **argv);
-	#endif
-	#if JOBS
-	static int jobscmd(int, char **);
-	#endif
	#if ENABLE_ASH_MATH_SUPPORT
-	static int letcmd(int, char **);
-	#endif
-	static int localcmd(int, char **);
-	static int pwdcmd(int, char **);
-	static int readcmd(int, char **);
-	static int returncmd(int, char **);
-	static int setcmd(int, char **);
-	static int shiftcmd(int, char **);
-	static int timescmd(int, char **);
-	static int trapcmd(int, char **);
-	static int truecmd(int, char **);
-	static int typecmd(int, char **);
-	static int umaskcmd(int, char **);
-	static int unsetcmd(int, char **);
-	static int waitcmd(int, char **);
-	static int ulimitcmd(int, char **);
-	#if JOBS
-	static int killcmd(int, char **);
-	#endif
-
-	#define BUILTIN_NOSPEC "0"
-	#define BUILTIN_SPECIAL "1"
-	#define BUILTIN_REGULAR "2"
-	#define BUILTIN_SPEC_REG "3"
-	#define BUILTIN_ASSIGN "4"
-	#define BUILTIN_SPEC_ASSG "5"
-	#define BUILTIN_REG_ASSG "6"
-	#define BUILTIN_SPEC_REG_ASSG "7"
-
-	#define IS_BUILTIN_SPECIAL(b) ((b)->name[0] & 1)
-	#define IS_BUILTIN_REGULAR(b) ((b)->name[0] & 2)
-	#define IS_BUILTIN_ASSIGN(b) ((b)->name[0] & 4)
-
-	/* make sure to keep these in proper order since it is searched via bsearch() */
-	static const struct builtincmd builtintab[] = {
-	{ BUILTIN_SPEC_REG ".", dotcmd },
-	{ BUILTIN_SPEC_REG ":", truecmd },
-	#if ENABLE_ASH_BUILTIN_TEST
-	{ BUILTIN_REGULAR "[", testcmd },
-	{ BUILTIN_REGULAR "[[", testcmd },
-	#endif
-	#if ENABLE_ASH_ALIAS
-	{ BUILTIN_REG_ASSG "alias", aliascmd },
-	#endif
-	#if JOBS
-	{ BUILTIN_REGULAR "bg", fg_bgcmd },
-	#endif
-	{ BUILTIN_SPEC_REG "break", breakcmd },
-	{ BUILTIN_REGULAR "cd", cdcmd },
-	{ BUILTIN_NOSPEC "chdir", cdcmd },
-	#if ENABLE_ASH_CMDCMD
-	{ BUILTIN_REGULAR "command", commandcmd },
-	#endif
-	{ BUILTIN_SPEC_REG "continue", breakcmd },
-	#if ENABLE_ASH_BUILTIN_ECHO
-	{ BUILTIN_REGULAR "echo", echocmd },
-	#endif
-	{ BUILTIN_SPEC_REG "eval", evalcmd },
-	{ BUILTIN_SPEC_REG "exec", execcmd },
-	{ BUILTIN_SPEC_REG "exit", exitcmd },
-	{ BUILTIN_SPEC_REG_ASSG "export", exportcmd },
-	{ BUILTIN_REGULAR "false", falsecmd },
-	#if JOBS
-	{ BUILTIN_REGULAR "fg", fg_bgcmd },
-	#endif
-	#if ENABLE_ASH_GETOPTS
-	{ BUILTIN_REGULAR "getopts", getoptscmd },
-	#endif
-	{ BUILTIN_NOSPEC "hash", hashcmd },
-	#if !ENABLE_FEATURE_SH_EXTRA_QUIET
-	{ BUILTIN_NOSPEC "help", helpcmd },
-	#endif
-	#if JOBS
-	{ BUILTIN_REGULAR "jobs", jobscmd },
-	{ BUILTIN_REGULAR "kill", killcmd },
-	#endif
-	#if ENABLE_ASH_MATH_SUPPORT
-	{ BUILTIN_NOSPEC "let", letcmd },
-	#endif
-	{ BUILTIN_ASSIGN "local", localcmd },
-	{ BUILTIN_NOSPEC "pwd", pwdcmd },
-	{ BUILTIN_REGULAR "read", readcmd },
-	{ BUILTIN_SPEC_REG_ASSG "readonly", exportcmd },
-	{ BUILTIN_SPEC_REG "return", returncmd },
-	{ BUILTIN_SPEC_REG "set", setcmd },
-	{ BUILTIN_SPEC_REG "shift", shiftcmd },
-	{ BUILTIN_SPEC_REG "source", dotcmd },
-	#if ENABLE_ASH_BUILTIN_TEST
-	{ BUILTIN_REGULAR "test", testcmd },
-	#endif
-	{ BUILTIN_SPEC_REG "times", timescmd },
-	{ BUILTIN_SPEC_REG "trap", trapcmd },
-	{ BUILTIN_REGULAR "true", truecmd },
-	{ BUILTIN_NOSPEC "type", typecmd },
-	{ BUILTIN_NOSPEC "ulimit", ulimitcmd },
-	{ BUILTIN_REGULAR "umask", umaskcmd },
-	#if ENABLE_ASH_ALIAS
-	{ BUILTIN_REGULAR "unalias", unaliascmd },
-	#endif
-	{ BUILTIN_SPEC_REG "unset", unsetcmd },
-	{ BUILTIN_REGULAR "wait", waitcmd },
-	};
-
-	#define NUMBUILTINS (sizeof(builtintab) / sizeof(builtintab[0]))
-
-	#define COMMANDCMD (builtintab + 5 + \
-	2 * ENABLE_ASH_BUILTIN_TEST + \
-	ENABLE_ASH_ALIAS + \
-	ENABLE_ASH_JOB_CONTROL)
-	#define EXECCMD (builtintab + 7 + \
-	2 * ENABLE_ASH_BUILTIN_TEST + \
-	ENABLE_ASH_ALIAS + \
-	ENABLE_ASH_JOB_CONTROL + \
-	ENABLE_ASH_CMDCMD + \
-	ENABLE_ASH_BUILTIN_ECHO)
-
	/*
-	* Execute a simple command.
+	* Expand arithmetic expression. Backup to start of expression,
+	* evaluate, place result in (backed up) result, adjust string position.
	*/
-	static int back_exitstatus; /* exit status of backquoted command */
-	static int
-	isassignment(const char *p)
-	{
-	const char *q = endofname(p);
-	if (p == q)
-	return 0;
-	return *q == '=';
-	}
-	static int
-	bltincmd(int argc, char **argv)
-	{
-	/* Preserve exitstatus of a previous possible redirection
-	* as POSIX mandates */
-	return back_exitstatus;
-	}
	static void
-	evalcommand(union node *cmd, int flags)
+	expari(int quotes)
	{
-	static const struct builtincmd bltin = {
-	"\0\0", bltincmd
-	};
-	struct stackmark smark;
-	union node *argp;
-	struct arglist arglist;
-	struct arglist varlist;
-	char **argv;
-	int argc;
-	const struct strlist *sp;
-	struct cmdentry cmdentry;
-	struct job *jp;
-	char *lastarg;
-	const char *path;
-	int spclbltin;
-	int cmd_is_exec;
-	int status;
-	char **nargv;
-	struct builtincmd *bcmd;
-	int pseudovarflag = 0;
-
-	/* First expand the arguments. */
-	TRACE(("evalcommand(0x%lx, %d) called\n", (long)cmd, flags));
-	setstackmark(&smark);
-	back_exitstatus = 0;
+	char p, start;
+	int begoff;
+	int flag;
+	int len;

-	cmdentry.cmdtype = CMDBUILTIN;
-	cmdentry.u.cmd = &bltin;
-	varlist.lastp = &varlist.list;
-	*varlist.lastp = NULL;
-	arglist.lastp = &arglist.list;
-	*arglist.lastp = NULL;
+	/* ifsfree(); */

-	argc = 0;
-	if (cmd->ncmd.args) {
-	bcmd = find_builtin(cmd->ncmd.args->narg.text);
-	pseudovarflag = bcmd && IS_BUILTIN_ASSIGN(bcmd);
-	}
+	/*
+	* This routine is slightly over-complicated for
+	* efficiency. Next we scan backwards looking for the
+	* start of arithmetic.
+	*/
+	start = stackblock();
+	p = expdest - 1;
+	*p = '\0';
+	p--;
+	do {
+	int esc;

-	for (argp = cmd->ncmd.args; argp; argp = argp->narg.next) {
-	struct strlist **spp;
+	while (*p != CTLARI) {
+	p--;
+	#if DEBUG
+	if (p < start) {
+	ash_msg_and_raise_error("missing CTLARI (shouldn't happen)");
+	}
+	#endif
+	}

-	spp = arglist.lastp;
-	if (pseudovarflag && isassignment(argp->narg.text))
-	expandarg(argp, &arglist, EXP_VARTILDE);
-	else
-	expandarg(argp, &arglist, EXP_FULL \| EXP_TILDE);
+	esc = esclen(start, p);
+	if (!(esc % 2)) {
+	break;
+	}

-	for (sp = *spp; sp; sp = sp->next)
-	argc++;
-	}
+	p -= esc + 1;
+	} while (1);

-	argv = nargv = stalloc(sizeof(char ) (argc + 1));
-	for (sp = arglist.list; sp; sp = sp->next) {
-	TRACE(("evalcommand arg: %s\n", sp->text));
-	*nargv++ = sp->text;
-	}
-	*nargv = NULL;
+	begoff = p - start;

-	lastarg = NULL;
-	if (iflag && funcnest == 0 && argc > 0)
-	lastarg = nargv[-1];
+	removerecordregions(begoff);

-	preverrout_fd = 2;
-	expredir(cmd->ncmd.redirect);
-	status = redirectsafe(cmd->ncmd.redirect, REDIR_PUSH\|REDIR_SAVEFD2);
+	flag = p[1];

-	path = vpath.text;
-	for (argp = cmd->ncmd.assign; argp; argp = argp->narg.next) {
-	struct strlist **spp;
-	char *p;
+	expdest = p;

-	spp = varlist.lastp;
-	expandarg(argp, &varlist, EXP_VARTILDE);
+	if (quotes)
+	rmescapes(p + 2);

-	/*
-	* Modify the command lookup path, if a PATH= assignment
-	* is present
-	*/
-	p = (*spp)->text;
-	if (varequal(p, path))
-	path = p;
-	}
+	len = cvtnum(dash_arith(p + 2));

-	/* Print the command if xflag is set. */
-	if (xflag) {
-	int n;
-	const char *p = " %s";
+	if (flag != '"')
+	recordregion(begoff, begoff + len, 0);
+	}
+	#endif

-	p++;
-	dprintf(preverrout_fd, p, expandstr(ps4val()));
+	/* argstr needs it */
+	static char evalvar(char p, int flag);

-	sp = varlist.list;
-	for (n = 0; n < 2; n++) {
-	while (sp) {
-	dprintf(preverrout_fd, p, sp->text);
-	sp = sp->next;
-	if (*p == '%') {
-	p--;
-	}
-	}
-	sp = arglist.list;
-	}
-	full_write(preverrout_fd, "\n", 1);
-	}
-
-	cmd_is_exec = 0;
-	spclbltin = -1;
-
-	/* Now locate the command. */
-	if (argc) {
-	const char *oldpath;
-	int cmd_flag = DO_ERR;
-
-	path += 5;
-	oldpath = path;
-	for (;;) {
-	find_command(argv[0], &cmdentry, cmd_flag, path);
-	if (cmdentry.cmdtype == CMDUNKNOWN) {
-	status = 127;
-	flush_stderr();
-	goto bail;
-	}
-
-	/* implement bltin and command here */
-	if (cmdentry.cmdtype != CMDBUILTIN)
-	break;
-	if (spclbltin < 0)
-	spclbltin = IS_BUILTIN_SPECIAL(cmdentry.u.cmd);
-	if (cmdentry.u.cmd == EXECCMD)
-	cmd_is_exec++;
-	#if ENABLE_ASH_CMDCMD
-	if (cmdentry.u.cmd == COMMANDCMD) {
-	path = oldpath;
-	nargv = parse_command_args(argv, &path);
-	if (!nargv)
-	break;
-	argc -= nargv - argv;
-	argv = nargv;
-	cmd_flag \|= DO_NOFUNC;
-	} else
+	/*
+	* Perform variable and command substitution. If EXP_FULL is set, output CTLESC
+	* characters to allow for further processing. Otherwise treat
+	* $@ like $* since no splitting will be performed.
+	*/
+	static void
+	argstr(char *p, int flag)
+	{
+	static const char spclchars[] = {
+	'=',
+	':',
+	CTLQUOTEMARK,
+	CTLENDVAR,
+	CTLESC,
+	CTLVAR,
+	CTLBACKQ,
+	CTLBACKQ \| CTLQUOTE,
+	#if ENABLE_ASH_MATH_SUPPORT
+	CTLENDARI,
	#endif
-	break;
-	}
-	}
+	0
+	};
+	const char *reject = spclchars;
+	int c;
+	int quotes = flag & (EXP_FULL \| EXP_CASE); /* do CTLESC */
+	int breakall = flag & EXP_WORD;
+	int inquotes;
+	size_t length;
+	int startloc;

-	if (status) {
-	/* We have a redirection error. */
-	if (spclbltin > 0)
-	raise_exception(EXERROR);
-	bail:
-	exitstatus = status;
-	goto out;
+	if (!(flag & EXP_VARTILDE)) {
+	reject += 2;
+	} else if (flag & EXP_VARTILDE2) {
+	reject++;
	}
+	inquotes = 0;
+	length = 0;
+	if (flag & EXP_TILDE) {
+	char *q;

-	/* Execute the command. */
-	switch (cmdentry.cmdtype) {
-	default:
-	/* Fork off a child process if necessary. */
-	if (!(flags & EV_EXIT) \|\| trap[0]) {
-	INT_OFF;
-	jp = makejob(cmd, 1);
-	if (forkshell(jp, cmd, FORK_FG) != 0) {
-	exitstatus = waitforjob(jp);
-	INT_ON;
-	break;
+	flag &= ~EXP_TILDE;
+	tilde:
+	q = p;
+	if (*q == CTLESC && (flag & EXP_QWORD))
+	q++;
+	if (*q == '~')
+	p = exptilde(p, q, flag);
+	}
+	start:
+	startloc = expdest - (char *)stackblock();
+	for (;;) {
+	length += strcspn(p + length, reject);
+	c = p[length];
+	if (c && (!(c & 0x80)
+	#if ENABLE_ASH_MATH_SUPPORT
+	\|\| c == CTLENDARI
+	#endif
+	)) {
+	/* c == '=' \|\| c == ':' \|\| c == CTLENDARI */
+	length++;
+	}
+	if (length > 0) {
+	int newloc;
+	expdest = stack_nputstr(p, length, expdest);
+	newloc = expdest - (char *)stackblock();
+	if (breakall && !inquotes && newloc > startloc) {
+	recordregion(startloc, newloc, 0);
	}
-	FORCE_INT_ON;
+	startloc = newloc;
	}
-	listsetvar(varlist.list, VEXPORT\|VSTACK);
-	shellexec(argv, path, cmdentry.u.index);
-	/* NOTREACHED */
+	p += length + 1;
+	length = 0;

-	case CMDBUILTIN:
-	cmdenviron = varlist.list;
-	if (cmdenviron) {
-	struct strlist *list = cmdenviron;
-	int i = VNOSET;
-	if (spclbltin > 0 \|\| argc == 0) {
-	i = 0;
-	if (cmd_is_exec && argc > 1)
-	i = VEXPORT;
+	switch (c) {
+	case '\0':
+	goto breakloop;
+	case '=':
+	if (flag & EXP_VARTILDE2) {
+	p--;
+	continue;
	}
-	listsetvar(list, i);
+	flag \|= EXP_VARTILDE2;
+	reject++;
+	/* fall through */
+	case ':':
+	/*
+	* sort of a hack - expand tildes in variable
+	* assignments (after the first '=' and after ':'s).
+	*/
+	if (*--p == '~') {
+	goto tilde;
+	}
+	continue;
	}
-	if (evalbltin(cmdentry.u.cmd, argc, argv)) {
-	int exit_status;
-	int i, j;
-
-	i = exception;
-	if (i == EXEXIT)
-	goto raise;
-
-	exit_status = 2;
-	j = 0;
-	if (i == EXINT)
-	j = SIGINT;
-	if (i == EXSIG)
-	j = pendingsigs;
-	if (j)
-	exit_status = j + 128;
-	exitstatus = exit_status;

-	if (i == EXINT \|\| spclbltin > 0) {
-	raise:
-	longjmp(exception_handler->loc, 1);
+	switch (c) {
+	case CTLENDVAR: /* ??? */
+	goto breakloop;
+	case CTLQUOTEMARK:
+	/* "$@" syntax adherence hack */
+	if (
+	!inquotes &&
+	!memcmp(p, dolatstr, 4) &&
+	(p[4] == CTLQUOTEMARK \|\| (
+	p[4] == CTLENDVAR &&
+	p[5] == CTLQUOTEMARK
+	))
+	) {
+	p = evalvar(p + 1, flag) + 1;
+	goto start;
	}
-	FORCE_INT_ON;
+	inquotes = !inquotes;
+	addquote:
+	if (quotes) {
+	p--;
+	length++;
+	startloc++;
+	}
+	break;
+	case CTLESC:
+	startloc++;
+	length++;
+	goto addquote;
+	case CTLVAR:
+	p = evalvar(p, flag);
+	goto start;
+	case CTLBACKQ:
+	c = 0;
+	case CTLBACKQ\|CTLQUOTE:
+	expbackq(argbackq->n, c, quotes);
+	argbackq = argbackq->next;
+	goto start;
+	#if ENABLE_ASH_MATH_SUPPORT
+	case CTLENDARI:
+	p--;
+	expari(quotes);
+	goto start;
+	#endif
	}
-	break;
-
-	case CMDFUNCTION:
-	listsetvar(varlist.list, 0);
-	if (evalfun(cmdentry.u.func, argc, argv, flags))
-	goto raise;
-	break;
	}
-
-	out:
-	popredir(cmd_is_exec);
-	if (lastarg)
-	/* dsl: I think this is intended to be used to support
-	* '_' in 'vi' command mode during line editing...
-	* However I implemented that within libedit itself.
-	*/
-	setvar("_", lastarg, 0);
-	popstackmark(&smark);
+	breakloop:
+	;
	}

-	static int
-	evalbltin(const struct builtincmd cmd, int argc, char *argv)
+	static char *
+	scanleft(char startp, char rmesc, char rmescend, char str, int quotes,
+	int zero)
	{
-	char *volatile savecmdname;
-	struct jmploc *volatile savehandler;
-	struct jmploc jmploc;
-	int i;
+	char *loc;
+	char *loc2;
+	char c;

-	savecmdname = commandname;
-	i = setjmp(jmploc.loc);
-	if (i)
-	goto cmddone;
-	savehandler = exception_handler;
-	exception_handler = &jmploc;
-	commandname = argv[0];
-	argptr = argv + 1;
-	optptr = NULL; /* initialize nextopt */
-	exitstatus = (*cmd->builtin)(argc, argv);
-	flush_stdout_stderr();
-	cmddone:
-	exitstatus \|= ferror(stdout);
-	clearerr(stdout);
-	commandname = savecmdname;
-	exsig = 0;
-	exception_handler = savehandler;
-
-	return i;
+	loc = startp;
+	loc2 = rmesc;
+	do {
+	int match;
+	const char *s = loc2;
+	c = *loc2;
+	if (zero) {
+	*loc2 = '\0';
+	s = rmesc;
+	}
+	match = pmatch(str, s);
+	*loc2 = c;
+	if (match)
+	return loc;
+	if (quotes && *loc == CTLESC)
+	loc++;
+	loc++;
+	loc2++;
+	} while (c);
+	return 0;
	}

-	static struct localvar *localvars;
-
-	/*
-	* Called after a function returns.
-	* Interrupts must be off.
-	*/
-	static void
-	poplocalvars(void)
+	static char *
+	scanright(char startp, char rmesc, char rmescend, char str, int quotes,
+	int zero)
	{
-	struct localvar *lvp;
-	struct var *vp;
+	int esc = 0;
+	char *loc;
+	char *loc2;

-	while ((lvp = localvars) != NULL) {
-	localvars = lvp->next;
-	vp = lvp->vp;
-	TRACE(("poplocalvar %s", vp ? vp->text : "-"));
-	if (vp == NULL) { /* $- saved */
-	memcpy(optlist, lvp->text, sizeof(optlist));
-	free((char*)lvp->text);
-	optschanged();
-	} else if ((lvp->flags & (VUNSET\|VSTRFIXED)) == VUNSET) {
-	unsetvar(vp->text);
-	} else {
-	if (vp->func)
-	(*vp->func)(strchrnul(lvp->text, '=') + 1);
-	if ((vp->flags & (VTEXTFIXED\|VSTACK)) == 0)
-	free((char*)vp->text);
-	vp->flags = lvp->flags;
-	vp->text = lvp->text;
+	for (loc = str - 1, loc2 = rmescend; loc >= startp; loc2--) {
+	int match;
+	char c = *loc2;
+	const char *s = loc2;
+	if (zero) {
+	*loc2 = '\0';
+	s = rmesc;
+	}
+	match = pmatch(str, s);
+	*loc2 = c;
+	if (match)
+	return loc;
+	loc--;
+	if (quotes) {
+	if (--esc < 0) {
+	esc = esclen(startp, loc);
+	}
+	if (esc % 2) {
+	esc--;
+	loc--;
+	}
	}
-	free(lvp);
	}
+	return 0;
	}

-	/*
-	* Free a parse tree.
-	*/
+	static void varunset(const char , const char , const char *, int) ATTRIBUTE_NORETURN;
	static void
-	freefunc(struct funcnode *f)
+	varunset(const char end, const char var, const char *umsg, int varflags)
	{
-	if (f && --f->count < 0)
-	free(f);
+	const char *msg;
+	const char *tail;
+
+	tail = nullstr;
+	msg = "parameter not set";
+	if (umsg) {
+	if (*end == CTLENDVAR) {
+	if (varflags & VSNUL)
+	tail = " or null";
+	} else
+	msg = umsg;
+	}
+	ash_msg_and_raise_error("%.*s: %s%s", end - var - 1, var, msg, tail);
	}

-	static int
-	evalfun(struct funcnode func, int argc, char *argv, int flags)
+	static const char *
+	subevalvar(char p, char str, int strloc, int subtype, int startloc, int varflags, int quotes)
	{
-	volatile struct shparam saveparam;
-	struct localvar *volatile savelocalvars;
-	struct jmploc *volatile savehandler;
-	struct jmploc jmploc;
-	int e;
+	char *startp;
+	char *loc;
+	int saveherefd = herefd;
+	struct nodelist *saveargbackq = argbackq;
+	int amount;
+	char rmesc, rmescend;
+	int zero;
+	char (scan)(char , char , char , char , int , int);

-	saveparam = shellparam;
-	savelocalvars = localvars;
-	e = setjmp(jmploc.loc);
-	if (e) {
-	goto funcdone;
+	herefd = -1;
+	argstr(p, subtype != VSASSIGN && subtype != VSQUESTION ? EXP_CASE : 0);
+	STPUTC('\0', expdest);
+	herefd = saveherefd;
+	argbackq = saveargbackq;
+	startp = stackblock() + startloc;
+
+	switch (subtype) {
+	case VSASSIGN:
+	setvar(str, startp, 0);
+	amount = startp - expdest;
+	STADJUST(amount, expdest);
+	return startp;
+
+	case VSQUESTION:
+	varunset(p, str, startp, varflags);
+	/* NOTREACHED */
	}
-	INT_OFF;
-	savehandler = exception_handler;
-	exception_handler = &jmploc;
-	localvars = NULL;
-	shellparam.malloc = 0;
-	func->count++;
-	funcnest++;
-	INT_ON;
-	shellparam.nparam = argc - 1;
-	shellparam.p = argv + 1;
-	#if ENABLE_ASH_GETOPTS
-	shellparam.optind = 1;
-	shellparam.optoff = -1;
+
+	subtype -= VSTRIMRIGHT;
+	#if DEBUG
+	if (subtype < 0 \|\| subtype > 3)
+	abort();
	#endif
-	evaltree(&func->n, flags & EV_TESTED);
-	funcdone:
-	INT_OFF;
-	funcnest--;
-	freefunc(func);
-	poplocalvars();
-	localvars = savelocalvars;
-	freeparam(&shellparam);
-	shellparam = saveparam;
-	exception_handler = savehandler;
-	INT_ON;
-	evalskip &= ~SKIPFUNC;
-	return e;
-	}

+	rmesc = startp;
+	rmescend = stackblock() + strloc;
+	if (quotes) {
+	rmesc = _rmescapes(startp, RMESCAPE_ALLOC \| RMESCAPE_GROW);
+	if (rmesc != startp) {
+	rmescend = expdest;
+	startp = stackblock() + startloc;
+	}
+	}
+	rmescend--;
+	str = stackblock() + strloc;
+	preglob(str, varflags & VSQUOTE, 0);
+
+	/* zero = subtype == VSTRIMLEFT \|\| subtype == VSTRIMLEFTMAX */
+	zero = subtype >> 1;
+	/* VSTRIMLEFT/VSTRIMRIGHTMAX -> scanleft */
+	scan = (subtype & 1) ^ zero ? scanleft : scanright;

-	static int
-	goodname(const char *p)
-	{
-	return !*endofname(p);
+	loc = scan(startp, rmesc, rmescend, str, quotes, zero);
+	if (loc) {
+	if (zero) {
+	memmove(startp, loc, str - loc);
+	loc = startp + (str - loc) - 1;
+	}
+	*loc = '\0';
+	amount = loc - expdest;
+	STADJUST(amount, expdest);
+	}
+	return loc;
	}

-
	/*
-	* Search for a command. This is called before we fork so that the
-	* location of the command will be available in the parent as well as
-	* the child. The check for "goodname" is an overly conservative
-	* check that the name will not be subject to expansion.
+	* Add the value of a specialized variable to the stack string.
	*/
-	static void
-	prehash(union node *n)
+	static ssize_t
+	varvalue(char *name, int varflags, int flags)
	{
-	struct cmdentry entry;
-
-	if (n->type == NCMD && n->ncmd.args && goodname(n->ncmd.args->narg.text))
-	find_command(n->ncmd.args->narg.text, &entry, 0, pathval());
-	}
-
+	int num;
+	char *p;
+	int i;
+	int sep = 0;
+	int sepq = 0;
+	ssize_t len = 0;
+	char **ap;
+	int syntax;
+	int quoted = varflags & VSQUOTE;
+	int subtype = varflags & VSTYPE;
+	int quotes = flags & (EXP_FULL \| EXP_CASE);

-	/*
-	* Builtin commands. Builtin commands whose functions are closely
-	* tied to evaluation are implemented here.
-	*/
+	if (quoted && (flags & EXP_FULL))
+	sep = 1 << CHAR_BIT;

-	/*
-	* Handle break and continue commands. Break, continue, and return are
-	* all handled by setting the evalskip flag. The evaluation routines
-	* above all check this flag, and if it is set they start skipping
-	* commands rather than executing them. The variable skipcount is
-	* the number of loops to break/continue, or the number of function
-	* levels to return. (The latter is always 1.) It should probably
-	* be an error to break out of more loops than exist, but it isn't
-	* in the standard shell so we don't make it one here.
-	*/
-
-	static int
-	breakcmd(int argc, char **argv)
-	{
-	int n = argc > 1 ? number(argv[1]) : 1;
+	syntax = quoted ? DQSYNTAX : BASESYNTAX;
+	switch (*name) {
+	case '$':
+	num = rootpid;
+	goto numvar;
+	case '?':
+	num = exitstatus;
+	goto numvar;
+	case '#':
+	num = shellparam.nparam;
+	goto numvar;
+	case '!':
+	num = backgndpid;
+	if (num == 0)
+	return -1;
+	numvar:
+	len = cvtnum(num);
+	break;
+	case '-':
+	p = makestrspace(NOPTS, expdest);
+	for (i = NOPTS - 1; i >= 0; i--) {
+	if (optlist[i]) {
+	USTPUTC(optletters(i), p);
+	len++;
+	}
+	}
+	expdest = p;
+	break;
+	case '@':
+	if (sep)
+	goto param;
+	/* fall through */
+	case '*':
+	sep = ifsset() ? SC2INT(ifsval()[0]) : ' ';
+	if (quotes && (SIT(sep, syntax) == CCTL \|\| SIT(sep, syntax) == CBACK))
+	sepq = 1;
+	param:
+	ap = shellparam.p;
+	if (!ap)
+	return -1;
+	while ((p = *ap++)) {
+	size_t partlen;

-	if (n <= 0)
-	ash_msg_and_raise_error(illnum, argv[1]);
-	if (n > loopnest)
-	n = loopnest;
-	if (n > 0) {
-	evalskip = (**argv == 'c')? SKIPCONT : SKIPBREAK;
-	skipcount = n;
-	}
-	return 0;
-	}
+	partlen = strlen(p);
+	len += partlen;

-	/*
-	* The return command.
-	*/
-	static int
-	returncmd(int argc, char **argv)
-	{
-	/*
-	* If called outside a function, do what ksh does;
-	* skip the rest of the file.
-	*/
-	evalskip = funcnest ? SKIPFUNC : SKIPFILE;
-	return argv[1] ? number(argv[1]) : exitstatus;
-	}
+	if (!(subtype == VSPLUS \|\| subtype == VSLENGTH))
+	memtodest(p, partlen, syntax, quotes);

-	static int
-	falsecmd(int argc, char **argv)
-	{
-	return 1;
-	}
+	if (*ap && sep) {
+	char *q;

-	static int
-	truecmd(int argc, char **argv)
-	{
-	return 0;
-	}
+	len++;
+	if (subtype == VSPLUS \|\| subtype == VSLENGTH) {
+	continue;
+	}
+	q = expdest;
+	if (sepq)
+	STPUTC(CTLESC, q);
+	STPUTC(sep, q);
+	expdest = q;
+	}
+	}
+	return len;
+	case '0':
+	case '1':
+	case '2':
+	case '3':
+	case '4':
+	case '5':
+	case '6':
+	case '7':
+	case '8':
+	case '9':
+	num = atoi(name);
+	if (num < 0 \|\| num > shellparam.nparam)
+	return -1;
+	p = num ? shellparam.p[num - 1] : arg0;
+	goto value;
+	default:
+	p = lookupvar(name);
+	value:
+	if (!p)
+	return -1;

-	static int
-	execcmd(int argc, char **argv)
-	{
-	if (argc > 1) {
-	iflag = 0; /* exit on error */
-	mflag = 0;
-	optschanged();
-	shellexec(argv + 1, pathval(), 0);
+	len = strlen(p);
+	if (!(subtype == VSPLUS \|\| subtype == VSLENGTH))
+	memtodest(p, len, syntax, quotes);
+	return len;
	}
-	return 0;
-	}

-
-	/* ============ Executing commands */
+	if (subtype == VSPLUS \|\| subtype == VSLENGTH)
+	STADJUST(-len, expdest);
+	return len;
+	}

	/*
-	* When commands are first encountered, they are entered in a hash table.
-	* This ensures that a full path search will not have to be done for them
-	* on each invocation.
-	*
-	* We should investigate converting to a linear search, even though that
-	* would make the command name "hash" a misnomer.
+	* Expand a variable, and return a pointer to the next character in the
+	* input string.
	*/
+	static char *
+	evalvar(char *p, int flag)
+	{
+	int subtype;
+	int varflags;
+	char *var;
+	int patloc;
+	int c;
+	int startloc;
+	ssize_t varlen;
+	int easy;
+	int quotes;
+	int quoted;

-	#define CMDTABLESIZE 31 /* should be prime */
-	#define ARB 1 /* actual size determined at run time */
+	quotes = flag & (EXP_FULL \| EXP_CASE);
+	varflags = *p++;
+	subtype = varflags & VSTYPE;
+	quoted = varflags & VSQUOTE;
+	var = p;
+	easy = (!quoted \|\| (*var == '@' && shellparam.nparam));
+	startloc = expdest - (char *)stackblock();
+	p = strchr(p, '=') + 1;

-	struct tblentry {
-	struct tblentry next; / next entry in hash chain */
-	union param param; /* definition of builtin function */
-	short cmdtype; /* index identifying command */
-	char rehash; /* if set, cd done since entry created */
-	char cmdname[ARB]; /* name of command */
-	};
+	again:
+	varlen = varvalue(var, varflags, flag);
+	if (varflags & VSNUL)
+	varlen--;

-	static struct tblentry *cmdtable[CMDTABLESIZE];
-	static int builtinloc = -1; /* index in path of %builtin, or -1 */
+	if (subtype == VSPLUS) {
+	varlen = -1 - varlen;
+	goto vsplus;
+	}

-	static void
-	tryexec(char cmd, char argv, char *envp)
-	{
-	int repeated = 0;
-	struct BB_applet *a;
-	int argc = 0;
-	char **c;
+	if (subtype == VSMINUS) {
+	vsplus:
+	if (varlen < 0) {
+	argstr(
+	p, flag \| EXP_TILDE \|
+	(quoted ? EXP_QWORD : EXP_WORD)
+	);
+	goto end;
+	}
+	if (easy)
+	goto record;
+	goto end;
+	}

-	if (strchr(cmd, '/') == NULL
-	&& (a = find_applet_by_name(cmd)) != NULL
-	&& is_safe_applet(cmd)
-	) {
-	c = argv;
-	while (*c != NULL) {
-	c++; argc++;
+	if (subtype == VSASSIGN \|\| subtype == VSQUESTION) {
+	if (varlen < 0) {
+	if (subevalvar(p, var, 0, subtype, startloc, varflags, 0)) {
+	varflags &= ~VSNUL;
+	/*
+	* Remove any recorded regions beyond
+	* start of variable
+	*/
+	removerecordregions(startloc);
+	goto again;
+	}
+	goto end;
	}
-	applet_name = cmd;
-	exit(a->main(argc, argv));
+	if (easy)
+	goto record;
+	goto end;
	}
-	#if ENABLE_FEATURE_SH_STANDALONE_SHELL
-	if (find_applet_by_name(cmd) != NULL) {
-	/* re-exec ourselves with the new arguments */
-	execve(CONFIG_BUSYBOX_EXEC_PATH, argv, envp);
-	/* If they called chroot or otherwise made the binary no longer
-	* executable, fall through */
+
+	if (varlen < 0 && uflag)
+	varunset(p, var, 0, 0);
+
+	if (subtype == VSLENGTH) {
+	cvtnum(varlen > 0 ? varlen : 0);
+	goto record;
	}
-	#endif

-	repeat:
-	#ifdef SYSV
-	do {
-	execve(cmd, argv, envp);
-	} while (errno == EINTR);
-	#else
-	execve(cmd, argv, envp);
+	if (subtype == VSNORMAL) {
+	if (!easy)
+	goto end;
+	record:
+	recordregion(startloc, expdest - (char *)stackblock(), quoted);
+	goto end;
+	}
+
+	#if DEBUG
+	switch (subtype) {
+	case VSTRIMLEFT:
+	case VSTRIMLEFTMAX:
+	case VSTRIMRIGHT:
+	case VSTRIMRIGHTMAX:
+	break;
+	default:
+	abort();
+	}
	#endif
-	if (repeated++) {
-	free(argv);
-	} else if (errno == ENOEXEC) {
-	char **ap;
-	char **new;

-	for (ap = argv; *ap; ap++)
-	;
-	ap = new = ckmalloc((ap - argv + 2) * sizeof(char *));
-	ap[1] = cmd;
-	ap = cmd = (char )DEFAULT_SHELL;
-	ap += 2;
-	argv++;
-	while ((ap++ = argv++))
-	;
-	argv = new;
-	goto repeat;
+	if (varlen >= 0) {
+	/*
+	* Terminate the string and start recording the pattern
+	* right after it
+	*/
+	STPUTC('\0', expdest);
+	patloc = expdest - (char *)stackblock();
+	if (subevalvar(p, NULL, patloc, subtype,
+	startloc, varflags, quotes) == 0) {
+	int amount = expdest - (
+	(char *)stackblock() + patloc - 1
+	);
+	STADJUST(-amount, expdest);
+	}
+	/* Remove any recorded regions beyond start of variable */
+	removerecordregions(startloc);
+	goto record;
+	}
+
+	end:
+	if (subtype != VSNORMAL) { /* skip to end of alternative */
+	int nesting = 1;
+	for (;;) {
+	c = *p++;
+	if (c == CTLESC)
+	p++;
+	else if (c == CTLBACKQ \|\| c == (CTLBACKQ\|CTLQUOTE)) {
+	if (varlen >= 0)
+	argbackq = argbackq->next;
+	} else if (c == CTLVAR) {
+	if ((*p++ & VSTYPE) != VSNORMAL)
+	nesting++;
+	} else if (c == CTLENDVAR) {
+	if (--nesting == 0)
+	break;
+	}
+	}
	}
+	return p;
	}

	/*
-	* Exec a program. Never returns. If you change this routine, you may
-	* have to change the find_command routine as well.
+	* Break the argument string into pieces based upon IFS and add the
+	* strings to the argument list. The regions of the string to be
+	* searched for IFS characters have been stored by recordregion.
	*/
-	#define environment() listvars(VEXPORT, VUNSET, 0)
-	static void shellexec(char *, const char , int) ATTRIBUTE_NORETURN;
	static void
-	shellexec(char *argv, const char path, int idx)
+	ifsbreakup(char string, struct arglist arglist)
	{
-	char *cmdname;
-	int e;
-	char **envp;
-	int exerrno;
+	struct ifsregion *ifsp;
+	struct strlist *sp;
+	char *start;
+	char *p;
+	char *q;
+	const char ifs, realifs;
+	int ifsspc;
+	int nulonly;

-	clearredir(1);
-	envp = environment();
-	if (strchr(argv[0], '/') \|\| is_safe_applet(argv[0])
-	#if ENABLE_FEATURE_SH_STANDALONE_SHELL
-	\|\| find_applet_by_name(argv[0])
-	#endif
-	) {
-	tryexec(argv[0], argv, envp);
-	e = errno;
-	} else {
-	e = ENOENT;
-	while ((cmdname = padvance(&path, argv[0])) != NULL) {
-	if (--idx < 0 && pathopt == NULL) {
-	tryexec(cmdname, argv, envp);
-	if (errno != ENOENT && errno != ENOTDIR)
-	e = errno;
-	}
-	stunalloc(cmdname);
-	}
+	start = string;
+	if (ifslastp != NULL) {
+	ifsspc = 0;
+	nulonly = 0;
+	realifs = ifsset() ? ifsval() : defifs;
+	ifsp = &ifsfirst;
+	do {
+	p = string + ifsp->begoff;
+	nulonly = ifsp->nulonly;
+	ifs = nulonly ? nullstr : realifs;
+	ifsspc = 0;
+	while (p < string + ifsp->endoff) {
+	q = p;
+	if (*p == CTLESC)
+	p++;
+	if (!strchr(ifs, *p)) {
+	p++;
+	continue;
+	}
+	if (!nulonly)
+	ifsspc = (strchr(defifs, *p) != NULL);
+	/* Ignore IFS whitespace at start */
+	if (q == start && ifsspc) {
+	p++;
+	start = p;
+	continue;
+	}
+	*q = '\0';
+	sp = stalloc(sizeof(*sp));
+	sp->text = start;
+	*arglist->lastp = sp;
+	arglist->lastp = &sp->next;
+	p++;
+	if (!nulonly) {
+	for (;;) {
+	if (p >= string + ifsp->endoff) {
+	break;
+	}
+	q = p;
+	if (*p == CTLESC)
+	p++;
+	if (strchr(ifs, *p) == NULL ) {
+	p = q;
+	break;
+	} else if (strchr(defifs, *p) == NULL) {
+	if (ifsspc) {
+	p++;
+	ifsspc = 0;
+	} else {
+	p = q;
+	break;
+	}
+	} else
+	p++;
+	}
+	}
+	start = p;
+	} /* while */
+	ifsp = ifsp->next;
+	} while (ifsp != NULL);
+	if (nulonly)
+	goto add;
	}

-	/* Map to POSIX errors */
-	switch (e) {
-	case EACCES:
-	exerrno = 126;
-	break;
-	case ENOENT:
-	exerrno = 127;
-	break;
-	default:
-	exerrno = 2;
-	break;
-	}
-	exitstatus = exerrno;
-	TRACE(("shellexec failed for %s, errno %d, suppressint %d\n",
-	argv[0], e, suppressint ));
-	ash_msg_and_raise(EXEXEC, "%s: %s", argv[0], errmsg(e, "not found"));
-	/* NOTREACHED */
+	if (!*start)
+	return;
+
+	add:
+	sp = stalloc(sizeof(*sp));
+	sp->text = start;
+	*arglist->lastp = sp;
+	arglist->lastp = &sp->next;
	}

	static void
-	printentry(struct tblentry *cmdp)
+	ifsfree(void)
	{
-	int idx;
-	const char *path;
-	char *name;
+	struct ifsregion *p;

-	idx = cmdp->param.index;
-	path = pathval();
+	INT_OFF;
+	p = ifsfirst.next;
	do {
-	name = padvance(&path, cmdp->cmdname);
-	stunalloc(name);
-	} while (--idx >= 0);
-	out1fmt("%s%s\n", name, (cmdp->rehash ? "*" : nullstr));
+	struct ifsregion *ifsp;
+	ifsp = p->next;
+	free(p);
+	p = ifsp;
+	} while (p);
+	ifslastp = NULL;
+	ifsfirst.next = NULL;
+	INT_ON;
	}

	/*
-	* Clear out command entries. The argument specifies the first entry in
-	* PATH which has changed.
+	* Add a file name to the list.
	*/
	static void
-	clearcmdentry(int firstchange)
+	addfname(const char *name)
	{
-	struct tblentry **tblp;
-	struct tblentry **pp;
-	struct tblentry *cmdp;
+	struct strlist *sp;

-	INT_OFF;
-	for (tblp = cmdtable; tblp < &cmdtable[CMDTABLESIZE]; tblp++) {
-	pp = tblp;
-	while ((cmdp = *pp) != NULL) {
-	if ((cmdp->cmdtype == CMDNORMAL &&
-	cmdp->param.index >= firstchange)
-	\|\| (cmdp->cmdtype == CMDBUILTIN &&
-	builtinloc >= firstchange)
-	) {
-	*pp = cmdp->next;
-	free(cmdp);
-	} else {
-	pp = &cmdp->next;
-	}
-	}
-	}
-	INT_ON;
+	sp = stalloc(sizeof(*sp));
+	sp->text = ststrdup(name);
+	*exparg.lastp = sp;
+	exparg.lastp = &sp->next;
	}

+	static char *expdir;
+
	/*
-	* Locate a command in the command hash table. If "add" is nonzero,
-	* add the command to the table if it is not already present. The
-	* variable "lastcmdentry" is set to point to the address of the link
-	* pointing to the entry, so that delete_cmd_entry can delete the
-	* entry.
-	*
-	* Interrupts must be off if called with add != 0.
+	* Do metacharacter (i.e. *, ?, [...]) expansion.
	*/
-	static struct tblentry **lastcmdentry;
-
-	static struct tblentry *
-	cmdlookup(const char *name, int add)
+	static void
+	expmeta(char enddir, char name)
	{
-	unsigned int hashval;
-	const char *p;
-	struct tblentry *cmdp;
-	struct tblentry **pp;
+	char *p;
+	const char *cp;
+	char *start;
+	char *endname;
+	int metaflag;
+	struct stat statb;
+	DIR *dirp;
+	struct dirent *dp;
+	int atend;
+	int matchdot;

-	p = name;
-	hashval = (unsigned char)*p << 4;
-	while (*p)
-	hashval += (unsigned char)*p++;
-	hashval &= 0x7FFF;
-	pp = &cmdtable[hashval % CMDTABLESIZE];
-	for (cmdp = *pp; cmdp; cmdp = cmdp->next) {
-	if (strcmp(cmdp->cmdname, name) == 0)
-	break;
-	pp = &cmdp->next;
+	metaflag = 0;
+	start = name;
+	for (p = name; *p; p++) {
+	if (p == '' \|\| *p == '?')
+	metaflag = 1;
+	else if (*p == '[') {
+	char *q = p + 1;
+	if (*q == '!')
+	q++;
+	for (;;) {
+	if (*q == '\\')
+	q++;
+	if (q == '/' \|\| q == '\0')
+	break;
+	if (*++q == ']') {
+	metaflag = 1;
+	break;
+	}
+	}
+	} else if (*p == '\\')
+	p++;
+	else if (*p == '/') {
+	if (metaflag)
+	goto out;
+	start = p + 1;
+	}
	}
-	if (add && cmdp == NULL) {
-	cmdp = *pp = ckmalloc(sizeof(struct tblentry) - ARB
-	+ strlen(name) + 1);
-	cmdp->next = NULL;
-	cmdp->cmdtype = CMDUNKNOWN;
-	strcpy(cmdp->cmdname, name);
+	out:
+	if (metaflag == 0) { /* we've reached the end of the file name */
+	if (enddir != expdir)
+	metaflag++;
+	p = name;
+	do {
+	if (*p == '\\')
+	p++;
+	enddir++ = p;
+	} while (*p++);
+	if (metaflag == 0 \|\| lstat(expdir, &statb) >= 0)
+	addfname(expdir);
+	return;
	}
-	lastcmdentry = pp;
-	return cmdp;
-	}
-
-	/*
-	* Delete the command entry returned on the last lookup.
-	*/
-	static void
-	delete_cmd_entry(void)
-	{
-	struct tblentry *cmdp;
-
-	INT_OFF;
-	cmdp = *lastcmdentry;
-	*lastcmdentry = cmdp->next;
-	if (cmdp->cmdtype == CMDFUNCTION)
-	freefunc(cmdp->param.func);
-	free(cmdp);
-	INT_ON;
-	}
-
-	/*
-	* Add a new command entry, replacing any existing command entry for
-	* the same name - except special builtins.
-	*/
-	static void
-	addcmdentry(char name, struct cmdentry entry)
-	{
-	struct tblentry *cmdp;
-
-	cmdp = cmdlookup(name, 1);
-	if (cmdp->cmdtype == CMDFUNCTION) {
-	freefunc(cmdp->param.func);
+	endname = p;
+	if (name < start) {
+	p = name;
+	do {
+	if (*p == '\\')
+	p++;
+	enddir++ = p++;
+	} while (p < start);
	}
-	cmdp->cmdtype = entry->cmdtype;
-	cmdp->param = entry->u;
-	cmdp->rehash = 0;
+	if (enddir == expdir) {
+	cp = ".";
+	} else if (enddir == expdir + 1 && *expdir == '/') {
+	cp = "/";
+	} else {
+	cp = expdir;
+	enddir[-1] = '\0';
+	}
+	dirp = opendir(cp);
+	if (dirp == NULL)
+	return;
+	if (enddir != expdir)
+	enddir[-1] = '/';
+	if (*endname == 0) {
+	atend = 1;
+	} else {
+	atend = 0;
+	*endname++ = '\0';
+	}
+	matchdot = 0;
+	p = start;
+	if (*p == '\\')
+	p++;
+	if (*p == '.')
+	matchdot++;
+	while (! intpending && (dp = readdir(dirp)) != NULL) {
+	if (dp->d_name[0] == '.' && ! matchdot)
+	continue;
+	if (pmatch(start, dp->d_name)) {
+	if (atend) {
+	strcpy(enddir, dp->d_name);
+	addfname(expdir);
+	} else {
+	for (p = enddir, cp = dp->d_name; (p++ = cp++) != '\0';)
+	continue;
+	p[-1] = '/';
+	expmeta(p, endname);
+	}
+	}
+	}
+	closedir(dirp);
+	if (! atend)
+	endname[-1] = '/';
	}

-	static int
-	hashcmd(int argc, char **argv)
+	static struct strlist *
+	msort(struct strlist *list, int len)
	{
-	struct tblentry **pp;
-	struct tblentry *cmdp;
-	int c;
-	struct cmdentry entry;
-	char *name;
+	struct strlist p, q = NULL;
+	struct strlist **lpp;
+	int half;
+	int n;

-	while ((c = nextopt("r")) != '\0') {
-	clearcmdentry(0);
-	return 0;
+	if (len <= 1)
+	return list;
+	half = len >> 1;
+	p = list;
+	for (n = half; --n >= 0; ) {
+	q = p;
+	p = p->next;
	}
-	if (*argptr == NULL) {
-	for (pp = cmdtable; pp < &cmdtable[CMDTABLESIZE]; pp++) {
-	for (cmdp = *pp; cmdp; cmdp = cmdp->next) {
-	if (cmdp->cmdtype == CMDNORMAL)
-	printentry(cmdp);
+	q->next = NULL; /* terminate first half of list */
+	q = msort(list, half); /* sort first half of list */
+	p = msort(p, len - half); /* sort second half */
+	lpp = &list;
+	for (;;) {
+	#if ENABLE_LOCALE_SUPPORT
+	if (strcoll(p->text, q->text) < 0)
+	#else
+	if (strcmp(p->text, q->text) < 0)
+	#endif
+	{
+	*lpp = p;
+	lpp = &p->next;
+	p = *lpp;
+	if (p == NULL) {
+	*lpp = q;
+	break;
+	}
+	} else {
+	*lpp = q;
+	lpp = &q->next;
+	q = *lpp;
+	if (q == NULL) {
+	*lpp = p;
+	break;
	}
	}
-	return 0;
-	}
-	c = 0;
-	while ((name = *argptr) != NULL) {
-	cmdp = cmdlookup(name, 0);
-	if (cmdp != NULL
-	&& (cmdp->cmdtype == CMDNORMAL
-	\|\| (cmdp->cmdtype == CMDBUILTIN && builtinloc >= 0)))
-	delete_cmd_entry();
-	find_command(name, &entry, DO_ERR, pathval());
-	if (entry.cmdtype == CMDUNKNOWN)
-	c = 1;
-	argptr++;
	}
-	return c;
+	return list;
	}

	/*
-	* Resolve a command name. If you change this routine, you may have to
-	* change the shellexec routine as well.
+	* Sort the results of file name expansion. It calculates the number of
+	* strings to sort and then calls msort (short for merge sort) to do the
+	* work.
	*/
-	static void
-	find_command(char name, struct cmdentry entry, int act, const char *path)
+	static struct strlist *
+	expsort(struct strlist *str)
	{
-	struct tblentry *cmdp;
-	int idx;
-	int prev;
-	char *fullname;
-	struct stat statb;
-	int e;
-	int updatetbl;
-	struct builtincmd *bcmd;
+	int len;
+	struct strlist *sp;

-	/* If name contains a slash, don't use PATH or hash table */
-	if (strchr(name, '/') != NULL) {
-	entry->u.index = -1;
-	if (act & DO_ABS) {
-	while (stat(name, &statb) < 0) {
-	#ifdef SYSV
-	if (errno == EINTR)
-	continue;
-	#endif
-	entry->cmdtype = CMDUNKNOWN;
-	return;
-	}
-	}
-	entry->cmdtype = CMDNORMAL;
-	return;
-	}
+	len = 0;
+	for (sp = str; sp; sp = sp->next)
+	len++;
+	return msort(str, len);
+	}

-	#if ENABLE_FEATURE_SH_STANDALONE_SHELL
-	if (find_applet_by_name(name)) {
-	entry->cmdtype = CMDNORMAL;
-	entry->u.index = -1;
-	return;
-	}
-	#endif
+	static void
+	expandmeta(struct strlist *str, int flag)
+	{
+	static const char metachars[] = {
+	'*', '?', '[', 0
+	};
+	/* TODO - EXP_REDIR */

-	if (is_safe_applet(name)) {
-	entry->cmdtype = CMDNORMAL;
-	entry->u.index = -1;
-	return;
-	}
+	while (str) {
+	struct strlist **savelastp;
+	struct strlist *sp;
+	char *p;

-	updatetbl = (path == pathval());
-	if (!updatetbl) {
-	act \|= DO_ALTPATH;
-	if (strstr(path, "%builtin") != NULL)
-	act \|= DO_ALTBLTIN;
-	}
+	if (fflag)
+	goto nometa;
+	if (!strpbrk(str->text, metachars))
+	goto nometa;
+	savelastp = exparg.lastp;

-	/* If name is in the table, check answer will be ok */
-	cmdp = cmdlookup(name, 0);
-	if (cmdp != NULL) {
-	int bit;
+	INT_OFF;
+	p = preglob(str->text, 0, RMESCAPE_ALLOC \| RMESCAPE_HEAP);
+	{
+	int i = strlen(str->text);
+	expdir = ckmalloc(i < 2048 ? 2048 : i); /* XXX */
+	}

-	switch (cmdp->cmdtype) {
-	default:
-	#if DEBUG
-	abort();
-	#endif
-	case CMDNORMAL:
-	bit = DO_ALTPATH;
-	break;
-	case CMDFUNCTION:
-	bit = DO_NOFUNC;
-	break;
-	case CMDBUILTIN:
-	bit = DO_ALTBLTIN;
-	break;
+	expmeta(expdir, p);
+	free(expdir);
+	if (p != str->text)
+	free(p);
+	INT_ON;
+	if (exparg.lastp == savelastp) {
+	/*
+	* no matches
+	*/
+	nometa:
+	*exparg.lastp = str;
+	rmescapes(str->text);
+	exparg.lastp = &str->next;
+	} else {
+	*exparg.lastp = NULL;
+	savelastp = sp = expsort(savelastp);
+	while (sp->next != NULL)
+	sp = sp->next;
+	exparg.lastp = &sp->next;
	}
-	if (act & bit) {
-	updatetbl = 0;
-	cmdp = NULL;
-	} else if (cmdp->rehash == 0)
-	/* if not invalidated by cd, we're done */
-	goto success;
+	str = str->next;
	}
+	}

-	/* If %builtin not in path, check for builtin next */
-	bcmd = find_builtin(name);
-	if (bcmd && (IS_BUILTIN_REGULAR(bcmd) \|\| (
-	act & DO_ALTPATH ? !(act & DO_ALTBLTIN) : builtinloc <= 0
-	)))
-	goto builtin_success;
+	/*
+	* Perform variable substitution and command substitution on an argument,
+	* placing the resulting list of arguments in arglist. If EXP_FULL is true,
+	* perform splitting and file name expansion. When arglist is NULL, perform
+	* here document expansion.
+	*/
+	static void
+	expandarg(union node arg, struct arglist arglist, int flag)
+	{
+	struct strlist *sp;
+	char *p;

-	/* We have to search path. */
-	prev = -1; /* where to start */
-	if (cmdp && cmdp->rehash) { /* doing a rehash */
-	if (cmdp->cmdtype == CMDBUILTIN)
-	prev = builtinloc;
-	else
-	prev = cmdp->param.index;
+	argbackq = arg->narg.backquote;
+	STARTSTACKSTR(expdest);
+	ifsfirst.next = NULL;
+	ifslastp = NULL;
+	argstr(arg->narg.text, flag);
+	p = _STPUTC('\0', expdest);
+	expdest = p - 1;
+	if (arglist == NULL) {
+	return; /* here document expanded */
	}
-
-	e = ENOENT;
-	idx = -1;
-	loop:
-	while ((fullname = padvance(&path, name)) != NULL) {
-	stunalloc(fullname);
-	idx++;
-	if (pathopt) {
-	if (prefix(pathopt, "builtin")) {
-	if (bcmd)
-	goto builtin_success;
-	continue;
-	} else if (!(act & DO_NOFUNC) &&
-	prefix(pathopt, "func")) {
-	/* handled below */
-	} else {
-	/* ignore unimplemented options */
-	continue;
-	}
-	}
-	/* if rehash, don't redo absolute path names */
-	if (fullname[0] == '/' && idx <= prev) {
-	if (idx < prev)
-	continue;
-	TRACE(("searchexec \"%s\": no change\n", name));
-	goto success;
-	}
-	while (stat(fullname, &statb) < 0) {
-	#ifdef SYSV
-	if (errno == EINTR)
-	continue;
-	#endif
-	if (errno != ENOENT && errno != ENOTDIR)
-	e = errno;
-	goto loop;
-	}
-	e = EACCES; /* if we fail, this will be the error */
-	if (!S_ISREG(statb.st_mode))
-	continue;
-	if (pathopt) { /* this is a %func directory */
-	stalloc(strlen(fullname) + 1);
-	readcmdfile(fullname);
-	cmdp = cmdlookup(name, 0);
-	if (cmdp == NULL \|\| cmdp->cmdtype != CMDFUNCTION)
-	ash_msg_and_raise_error("%s not defined in %s", name, fullname);
-	stunalloc(fullname);
-	goto success;
-	}
-	TRACE(("searchexec \"%s\" returns \"%s\"\n", name, fullname));
-	if (!updatetbl) {
-	entry->cmdtype = CMDNORMAL;
-	entry->u.index = idx;
-	return;
-	}
-	INT_OFF;
-	cmdp = cmdlookup(name, 1);
-	cmdp->cmdtype = CMDNORMAL;
-	cmdp->param.index = idx;
-	INT_ON;
-	goto success;
+	p = grabstackstr(p);
+	exparg.lastp = &exparg.list;
+	/*
+	* TODO - EXP_REDIR
+	*/
+	if (flag & EXP_FULL) {
+	ifsbreakup(p, &exparg);
+	*exparg.lastp = NULL;
+	exparg.lastp = &exparg.list;
+	expandmeta(exparg.list, flag);
+	} else {
+	if (flag & EXP_REDIR) /XXX - for now, just remove escapes /
+	rmescapes(p);
+	sp = stalloc(sizeof(*sp));
+	sp->text = p;
+	*exparg.lastp = sp;
+	exparg.lastp = &sp->next;
	}
-
-	/* We failed. If there was an entry for this command, delete it */
-	if (cmdp && updatetbl)
-	delete_cmd_entry();
-	if (act & DO_ERR)
-	ash_msg("%s: %s", name, errmsg(e, "not found"));
-	entry->cmdtype = CMDUNKNOWN;
-	return;
-
-	builtin_success:
-	if (!updatetbl) {
-	entry->cmdtype = CMDBUILTIN;
-	entry->u.cmd = bcmd;
-	return;
+	if (ifsfirst.next)
+	ifsfree();
+	*exparg.lastp = NULL;
+	if (exparg.list) {
+	*arglist->lastp = exparg.list;
+	arglist->lastp = exparg.lastp;
	}
-	INT_OFF;
-	cmdp = cmdlookup(name, 1);
-	cmdp->cmdtype = CMDBUILTIN;
-	cmdp->param.cmd = bcmd;
-	INT_ON;
-	success:
-	cmdp->rehash = 0;
-	entry->cmdtype = cmdp->cmdtype;
-	entry->u = cmdp->param;
	}

	/*
-	* Search the table of builtin commands.
+	* Expand shell variables and backquotes inside a here document.
	*/
-	static struct builtincmd *
-	find_builtin(const char *name)
+	static void
+	expandhere(union node *arg, int fd)
	{
-	struct builtincmd *bp;
-
-	bp = bsearch(
-	name, builtintab, NUMBUILTINS, sizeof(builtintab[0]),
-	pstrcmp
-	);
-	return bp;
-	}
+	herefd = fd;
+	expandarg(arg, (struct arglist *)NULL, 0);
+	full_write(fd, stackblock(), expdest - (char *)stackblock());
+	}

	/*
-	* Called when a cd is done. Marks all commands so the next time they
-	* are executed they will be rehashed.
+	* Returns true if the pattern matches the string.
	*/
-	static void
-	hashcd(void)
+	static int
+	patmatch(char pattern, const char string)
	{
-	struct tblentry **pp;
-	struct tblentry *cmdp;
-
-	for (pp = cmdtable; pp < &cmdtable[CMDTABLESIZE]; pp++) {
-	for (cmdp = *pp; cmdp; cmdp = cmdp->next) {
-	if (cmdp->cmdtype == CMDNORMAL \|\| (
-	cmdp->cmdtype == CMDBUILTIN &&
-	!(IS_BUILTIN_REGULAR(cmdp->param.cmd)) &&
-	builtinloc > 0
-	))
-	cmdp->rehash = 1;
-	}
-	}
+	return pmatch(preglob(pattern, 0, 0), string);
	}

	/*
-	* Fix command hash table when PATH changed.
-	* Called before PATH is changed. The argument is the new value of PATH;
-	* pathval() still returns the old value at this point.
-	* Called with interrupts off.
+	* See if a pattern matches in a case statement.
	*/
-	static void
-	changepath(const char *newval)
+	static int
+	casematch(union node pattern, char val)
	{
-	const char old, new;
-	int idx;
-	int firstchange;
-	int idx_bltin;
+	struct stackmark smark;
+	int result;

-	old = pathval();
-	new = newval;
-	firstchange = 9999; /* assume no change */
-	idx = 0;
-	idx_bltin = -1;
-	for (;;) {
-	if (old != new) {
-	firstchange = idx;
-	if ((old == '\0' && new == ':')
-	\|\| (old == ':' && new == '\0'))
-	firstchange++;
-	old = new; /* ignore subsequent differences */
-	}
-	if (*new == '\0')
-	break;
-	if (*new == '%' && idx_bltin < 0 && prefix(new + 1, "builtin"))
-	idx_bltin = idx;
-	if (*new == ':') {
-	idx++;
-	}
-	new++, old++;
-	}
-	if (builtinloc < 0 && idx_bltin >= 0)
-	builtinloc = idx_bltin; /* zap builtins */
-	if (builtinloc >= 0 && idx_bltin < 0)
-	firstchange = 0;
-	clearcmdentry(firstchange);
-	builtinloc = idx_bltin;
+	setstackmark(&smark);
+	argbackq = pattern->narg.backquote;
+	STARTSTACKSTR(expdest);
+	ifslastp = NULL;
+	argstr(pattern->narg.text, EXP_TILDE \| EXP_CASE);
+	STACKSTRNUL(expdest);
+	result = patmatch(stackblock(), val);
+	popstackmark(&smark);
+	return result;
	}


-	/*
-	* Make a copy of a parse tree.
-	*/
-	static struct funcnode *
-	copyfunc(union node *n)
-	{
-	struct funcnode *f;
-	size_t blocksize;
+	/* ============ eval.c */

-	funcblocksize = offsetof(struct funcnode, n);
-	funcstringsize = 0;
-	calcsize(n);
-	blocksize = funcblocksize;
-	f = ckmalloc(blocksize + funcstringsize);
-	funcblock = (char *) f + offsetof(struct funcnode, n);
-	funcstring = (char *) f + blocksize;
-	copynode(n);
-	f->count = 0;
-	return f;
-	}
+	/* flags in argument to evaltree */
+	#define EV_EXIT 01 /* exit after evaluating tree */
+	#define EV_TESTED 02 /* exit status is checked; ignore -e flag */
+	#define EV_BACKCMD 04 /* command executing within back quotes */
+
+	/* forward declarations - evaluation is fairly recursive business... */
+	static void evalloop(union node *, int);
+	static void evalfor(union node *, int);
+	static void evalcase(union node *, int);
+	static void evalsubshell(union node *, int);
+	static void expredir(union node *);
+	static void evalpipe(union node *, int);
+	static void evalcommand(union node *, int);
+	static int evalbltin(const struct builtincmd , int, char *);
+	static int evalfun(struct funcnode , int, char *, int);
+	static void prehash(union node *);

	/*
-	* Define a shell function.
+	* Evaluate a parse tree. The value is left in the global variable
+	* exitstatus.
	*/
	static void
-	defun(char name, union node func)
+	evaltree(union node *n, int flags)
	{
-	struct cmdentry entry;
+	int checkexit = 0;
+	void (evalfn)(union node , int);
+	unsigned isor;
+	int status;
+	if (n == NULL) {
+	TRACE(("evaltree(NULL) called\n"));
+	goto out;
+	}
+	TRACE(("pid %d, evaltree(%p: %d, %d) called\n",
+	getpid(), n, n->type, flags));
+	switch (n->type) {
+	default:
+	#if DEBUG
+	out1fmt("Node type = %d\n", n->type);
+	fflush(stdout);
+	break;
+	#endif
+	case NNOT:
+	evaltree(n->nnot.com, EV_TESTED);
+	status = !exitstatus;
+	goto setstatus;
+	case NREDIR:
+	expredir(n->nredir.redirect);
+	status = redirectsafe(n->nredir.redirect, REDIR_PUSH);
+	if (!status) {
+	evaltree(n->nredir.n, flags & EV_TESTED);
+	status = exitstatus;
+	}
+	popredir(0);
+	goto setstatus;
+	case NCMD:
+	evalfn = evalcommand;
+	checkexit:
+	if (eflag && !(flags & EV_TESTED))
+	checkexit = ~0;
+	goto calleval;
+	case NFOR:
+	evalfn = evalfor;
+	goto calleval;
+	case NWHILE:
+	case NUNTIL:
+	evalfn = evalloop;
+	goto calleval;
+	case NSUBSHELL:
+	case NBACKGND:
+	evalfn = evalsubshell;
+	goto calleval;
+	case NPIPE:
+	evalfn = evalpipe;
+	goto checkexit;
+	case NCASE:
+	evalfn = evalcase;
+	goto calleval;
+	case NAND:
+	case NOR:
+	case NSEMI:
+	#if NAND + 1 != NOR
+	#error NAND + 1 != NOR
+	#endif
+	#if NOR + 1 != NSEMI
+	#error NOR + 1 != NSEMI
+	#endif
+	isor = n->type - NAND;
+	evaltree(
+	n->nbinary.ch1,
+	(flags \| ((isor >> 1) - 1)) & EV_TESTED
+	);
+	if (!exitstatus == isor)
+	break;
+	if (!evalskip) {
+	n = n->nbinary.ch2;
+	evaln:
+	evalfn = evaltree;
+	calleval:
+	evalfn(n, flags);
+	break;
+	}
+	break;
+	case NIF:
+	evaltree(n->nif.test, EV_TESTED);
+	if (evalskip)
+	break;
+	if (exitstatus == 0) {
+	n = n->nif.ifpart;
+	goto evaln;
+	} else if (n->nif.elsepart) {
+	n = n->nif.elsepart;
+	goto evaln;
+	}
+	goto success;
+	case NDEFUN:
+	defun(n->narg.text, n->narg.next);
+	success:
+	status = 0;
+	setstatus:
+	exitstatus = status;
+	break;
+	}
+	out:
+	if ((checkexit & exitstatus))
+	evalskip \|= SKIPEVAL;
+	else if (pendingsigs && dotrap())
+	goto exexit;

-	INT_OFF;
-	entry.cmdtype = CMDFUNCTION;
-	entry.u.func = copyfunc(func);
-	addcmdentry(name, &entry);
-	INT_ON;
+	if (flags & EV_EXIT) {
+	exexit:
+	raise_exception(EXEXIT);
+	}
	}

-	/*
-	* Delete a function if it exists.
-	*/
+	#if !defined(__alpha__) \|\| (defined(__GNUC__) && __GNUC__ >= 3)
+	static
+	#endif
+	void evaltreenr(union node *, int) __attribute__ ((alias("evaltree"),__noreturn__));
+
+	static int loopnest; /* current loop nesting level */
+
	static void
-	unsetfunc(const char *name)
+	evalloop(union node *n, int flags)
	{
-	struct tblentry *cmdp;
-
-	cmdp = cmdlookup(name, 0);
-	if (cmdp!= NULL && cmdp->cmdtype == CMDFUNCTION)
-	delete_cmd_entry();
-	}
+	int status;

+	loopnest++;
+	status = 0;
+	flags &= EV_TESTED;
+	for (;;) {
+	int i;

-	/*
-	* Locate and print what a word is...
-	*/
-	#if ENABLE_ASH_CMDCMD
-	static int
-	describe_command(char *command, int describe_command_verbose)
-	#else
-	#define describe_command_verbose 1
-	static int
-	describe_command(char *command)
-	#endif
-	{
-	struct cmdentry entry;
-	struct tblentry *cmdp;
-	#if ENABLE_ASH_ALIAS
-	const struct alias *ap;
-	#endif
-	const char *path = pathval();
-
-	if (describe_command_verbose) {
-	out1str(command);
+	evaltree(n->nbinary.ch1, EV_TESTED);
+	if (evalskip) {
+	skipping:
+	if (evalskip == SKIPCONT && --skipcount <= 0) {
+	evalskip = 0;
+	continue;
+	}
+	if (evalskip == SKIPBREAK && --skipcount <= 0)
+	evalskip = 0;
+	break;
+	}
+	i = exitstatus;
+	if (n->type != NWHILE)
+	i = !i;
+	if (i != 0)
+	break;
+	evaltree(n->nbinary.ch2, flags);
+	status = exitstatus;
+	if (evalskip)
+	goto skipping;
	}
+	loopnest--;
+	exitstatus = status;
+	}

-	/* First look at the keywords */
-	if (findkwd(command)) {
-	out1str(describe_command_verbose ? " is a shell keyword" : command);
-	goto out;
-	}
+	static void
+	evalfor(union node *n, int flags)
+	{
+	struct arglist arglist;
+	union node *argp;
+	struct strlist *sp;
+	struct stackmark smark;

-	#if ENABLE_ASH_ALIAS
-	/* Then look at the aliases */
-	ap = lookupalias(command, 0);
-	if (ap != NULL) {
-	if (describe_command_verbose) {
-	out1fmt(" is an alias for %s", ap->val);
-	} else {
-	out1str("alias ");
-	printalias(ap);
-	return 0;
-	}
-	goto out;
-	}
-	#endif
-	/* Then check if it is a tracked alias */
-	cmdp = cmdlookup(command, 0);
-	if (cmdp != NULL) {
-	entry.cmdtype = cmdp->cmdtype;
-	entry.u = cmdp->param;
-	} else {
-	/* Finally use brute force */
-	find_command(command, &entry, DO_ABS, path);
+	setstackmark(&smark);
+	arglist.lastp = &arglist.list;
+	for (argp = n->nfor.args; argp; argp = argp->narg.next) {
+	expandarg(argp, &arglist, EXP_FULL \| EXP_TILDE \| EXP_RECORD);
+	/* XXX */
+	if (evalskip)
+	goto out;
	}
+	*arglist.lastp = NULL;

-	switch (entry.cmdtype) {
-	case CMDNORMAL: {
-	int j = entry.u.index;
-	char *p;
-	if (j == -1) {
-	p = command;
-	} else {
-	do {
-	p = padvance(&path, command);
-	stunalloc(p);
-	} while (--j >= 0);
-	}
-	if (describe_command_verbose) {
-	out1fmt(" is%s %s",
-	(cmdp ? " a tracked alias for" : nullstr), p
-	);
-	} else {
-	out1str(p);
+	exitstatus = 0;
+	loopnest++;
+	flags &= EV_TESTED;
+	for (sp = arglist.list; sp; sp = sp->next) {
+	setvar(n->nfor.var, sp->text, 0);
+	evaltree(n->nfor.body, flags);
+	if (evalskip) {
+	if (evalskip == SKIPCONT && --skipcount <= 0) {
+	evalskip = 0;
+	continue;
+	}
+	if (evalskip == SKIPBREAK && --skipcount <= 0)
+	evalskip = 0;
+	break;
	}
-	break;
	}
+	loopnest--;
+	out:
+	popstackmark(&smark);
+	}

-	case CMDFUNCTION:
-	if (describe_command_verbose) {
-	out1str(" is a shell function");
-	} else {
-	out1str(command);
-	}
-	break;
-
-	case CMDBUILTIN:
-	if (describe_command_verbose) {
-	out1fmt(" is a %sshell builtin",
-	IS_BUILTIN_SPECIAL(entry.u.cmd) ?
-	"special " : nullstr
-	);
-	} else {
-	out1str(command);
-	}
-	break;
+	static void
+	evalcase(union node *n, int flags)
+	{
+	union node *cp;
+	union node *patp;
+	struct arglist arglist;
+	struct stackmark smark;

-	default:
-	if (describe_command_verbose) {
-	out1str(": not found\n");
+	setstackmark(&smark);
+	arglist.lastp = &arglist.list;
+	expandarg(n->ncase.expr, &arglist, EXP_TILDE);
+	exitstatus = 0;
+	for (cp = n->ncase.cases; cp && evalskip == 0; cp = cp->nclist.next) {
+	for (patp = cp->nclist.pattern; patp; patp = patp->narg.next) {
+	if (casematch(patp, arglist.list->text)) {
+	if (evalskip == 0) {
+	evaltree(cp->nclist.body, flags);
+	}
+	goto out;
+	}
	}
-	return 127;
	}
	out:
-	outstr("\n", stdout);
-	return 0;
+	popstackmark(&smark);
	}

-	static int
-	typecmd(int argc, char **argv)
+	/*
+	* Kick off a subshell to evaluate a tree.
+	*/
+	static void
+	evalsubshell(union node *n, int flags)
	{
-	int i;
-	int err = 0;
+	struct job *jp;
+	int backgnd = (n->type == NBACKGND);
+	int status;

-	for (i = 1; i < argc; i++) {
-	#if ENABLE_ASH_CMDCMD
-	err \|= describe_command(argv[i], 1);
-	#else
-	err \|= describe_command(argv[i]);
-	#endif
+	expredir(n->nredir.redirect);
+	if (!backgnd && flags & EV_EXIT && !trap[0])
+	goto nofork;
+	INT_OFF;
+	jp = makejob(n, 1);
+	if (forkshell(jp, n, backgnd) == 0) {
+	INT_ON;
+	flags \|= EV_EXIT;
+	if (backgnd)
+	flags &=~ EV_TESTED;
+	nofork:
+	redirect(n->nredir.redirect, 0);
+	evaltreenr(n->nredir.n, flags);
+	/* never returns */
	}
-	return err;
+	status = 0;
+	if (! backgnd)
+	status = waitforjob(jp);
+	exitstatus = status;
+	INT_ON;
	}

-	#if ENABLE_ASH_CMDCMD
-	static int
-	commandcmd(int argc, char **argv)
+	/*
+	* Compute the names of the files in a redirection list.
+	*/
+	static void
+	expredir(union node *n)
	{
-	int c;
-	enum {
-	VERIFY_BRIEF = 1,
-	VERIFY_VERBOSE = 2,
-	} verify = 0;
+	union node *redir;

-	while ((c = nextopt("pvV")) != '\0')
-	if (c == 'V')
-	verify \|= VERIFY_VERBOSE;
-	else if (c == 'v')
-	verify \|= VERIFY_BRIEF;
-	#if DEBUG
-	else if (c != 'p')
-	abort();
-	#endif
-	if (verify)
-	return describe_command(*argptr, verify - VERIFY_BRIEF);
+	for (redir = n; redir; redir = redir->nfile.next) {
+	struct arglist fn;

-	return 0;
+	memset(&fn, 0, sizeof(fn));
+	fn.lastp = &fn.list;
+	switch (redir->type) {
+	case NFROMTO:
+	case NFROM:
+	case NTO:
+	case NCLOBBER:
+	case NAPPEND:
+	expandarg(redir->nfile.fname, &fn, EXP_TILDE \| EXP_REDIR);
+	redir->nfile.expfname = fn.list->text;
+	break;
+	case NFROMFD:
+	case NTOFD:
+	if (redir->ndup.vname) {
+	expandarg(redir->ndup.vname, &fn, EXP_FULL \| EXP_TILDE);
+	if (fn.list == NULL)
+	ash_msg_and_raise_error("redir error");
+	fixredir(redir, fn.list->text, 1);
+	}
+	break;
+	}
+	}
	}
-	#endif
-
-	/* expand.c */

	/*
-	* Routines to expand arguments to commands. We have to deal with
-	* backquotes, shell variables, and file metacharacters.
-	*/
-
-	/*
-	* _rmescape() flags
-	*/
-	#define RMESCAPE_ALLOC 0x1 /* Allocate a new string */
-	#define RMESCAPE_GLOB 0x2 /* Add backslashes for glob */
-	#define RMESCAPE_QUOTED 0x4 /* Remove CTLESC unless in quotes */
-	#define RMESCAPE_GROW 0x8 /* Grow strings instead of stalloc */
-	#define RMESCAPE_HEAP 0x10 /* Malloc strings instead of stalloc */
-
-	/*
-	* Structure specifying which parts of the string should be searched
-	* for IFS characters.
-	*/
-
-	struct ifsregion {
-	struct ifsregion next; / next region in list */
-	int begoff; /* offset of start of region */
-	int endoff; /* offset of end of region */
-	int nulonly; /* search for nul bytes only */
-	};
-
-	/* output of current string */
-	static char *expdest;
-	/* list of back quote expressions */
-	static struct nodelist *argbackq;
-	/* first struct in list of ifs regions */
-	static struct ifsregion ifsfirst;
-	/* last struct in list */
-	static struct ifsregion *ifslastp;
-	/* holds expanded arg list */
-	static struct arglist exparg;
-
-	static void argstr(char *, int);
-	static char exptilde(char , char *, int);
-	static void expbackq(union node *, int, int);
-	static const char subevalvar(char , char *, int, int, int, int, int);
-	static char evalvar(char , int);
-	static void strtodest(const char *, int, int);
-	static void memtodest(const char *p, size_t len, int syntax, int quotes);
-	static ssize_t varvalue(char *, int, int);
-	static void recordregion(int, int, int);
-	static void removerecordregions(int);
-	static void ifsbreakup(char , struct arglist );
-	static void ifsfree(void);
-	static void expandmeta(struct strlist *, int);
-	static int patmatch(char , const char );
-
-	static int cvtnum(arith_t);
-	static size_t esclen(const char , const char );
-	static char scanleft(char , char , char , char *, int, int);
-	static char scanright(char , char , char , char *, int, int);
-	static void varunset(const char , const char , const char *, int) ATTRIBUTE_NORETURN;
-
-
-	#define pmatch(a, b) !fnmatch((a), (b), 0)
-	/*
-	* Prepare a pattern for a expmeta (internal glob(3)) call.
-	*
-	* Returns an stalloced string.
+	* Evaluate a pipeline. All the processes in the pipeline are children
+	* of the process creating the pipeline. (This differs from some versions
+	* of the shell, which make the last process in a pipeline the parent
+	* of all the rest.)
	*/
-	static char *
-	preglob(const char *pattern, int quoted, int flag)
+	static void
+	evalpipe(union node *n, int flags)
	{
-	flag \|= RMESCAPE_GLOB;
-	if (quoted) {
-	flag \|= RMESCAPE_QUOTED;
+	struct job *jp;
+	struct nodelist *lp;
+	int pipelen;
+	int prevfd;
+	int pip[2];
+
+	TRACE(("evalpipe(0x%lx) called\n", (long)n));
+	pipelen = 0;
+	for (lp = n->npipe.cmdlist; lp; lp = lp->next)
+	pipelen++;
+	flags \|= EV_EXIT;
+	INT_OFF;
+	jp = makejob(n, pipelen);
+	prevfd = -1;
+	for (lp = n->npipe.cmdlist; lp; lp = lp->next) {
+	prehash(lp->n);
+	pip[1] = -1;
+	if (lp->next) {
+	if (pipe(pip) < 0) {
+	close(prevfd);
+	ash_msg_and_raise_error("Pipe call failed");
+	}
+	}
+	if (forkshell(jp, lp->n, n->npipe.backgnd) == 0) {
+	INT_ON;
+	if (pip[1] >= 0) {
+	close(pip[0]);
+	}
+	if (prevfd > 0) {
+	dup2(prevfd, 0);
+	close(prevfd);
+	}
+	if (pip[1] > 1) {
+	dup2(pip[1], 1);
+	close(pip[1]);
+	}
+	evaltreenr(lp->n, flags);
+	/* never returns */
+	}
+	if (prevfd >= 0)
+	close(prevfd);
+	prevfd = pip[0];
+	close(pip[1]);
	}
-	return _rmescapes((char *)pattern, flag);
+	if (n->npipe.backgnd == 0) {
+	exitstatus = waitforjob(jp);
+	TRACE(("evalpipe: job done exit status %d\n", exitstatus));
+	}
+	INT_ON;
	}

-
-	static size_t
-	esclen(const char start, const char p)
+	#if ENABLE_ASH_CMDCMD
+	static char **
+	parse_command_args(char argv, const char path)
	{
-	size_t esc = 0;
+	char *cp, c;

-	while (p > start && *--p == CTLESC) {
-	esc++;
+	for (;;) {
+	cp = *++argv;
+	if (!cp)
+	return 0;
+	if (*cp++ != '-')
+	break;
+	c = *cp++;
+	if (!c)
+	break;
+	if (c == '-' && !*cp) {
+	argv++;
+	break;
+	}
+	do {
+	switch (c) {
+	case 'p':
+	*path = defpath;
+	break;
+	default:
+	/* run 'typecmd' for other options */
+	return 0;
+	}
+	c = *cp++;
+	} while (c);
	}
-	return esc;
+	return argv;
	}
+	#endif

+	/* Forward declarations for builtintab[] */
+	#if JOBS
+	static int fg_bgcmd(int, char **);
+	#endif
+	static int breakcmd(int, char **);
+	#if ENABLE_ASH_CMDCMD
+	static int commandcmd(int, char **);
+	#endif
+	static int dotcmd(int, char **);
+	static int evalcmd(int, char **);
+	#if ENABLE_ASH_BUILTIN_ECHO
+	static int echocmd(int, char **);
+	#endif
+	#if ENABLE_ASH_BUILTIN_TEST
+	static int testcmd(int, char **);
+	#endif
+	static int execcmd(int, char **);
+	static int exitcmd(int, char **);
+	static int exportcmd(int, char **);
+	static int falsecmd(int, char **);
+	#if ENABLE_ASH_GETOPTS
+	static int getoptscmd(int, char **);
+	#endif
+	static int hashcmd(int, char **);
+	#if !ENABLE_FEATURE_SH_EXTRA_QUIET
+	static int helpcmd(int argc, char **argv);
+	#endif
+	#if JOBS
+	static int jobscmd(int, char **);
+	#endif
+	#if ENABLE_ASH_MATH_SUPPORT
+	static int letcmd(int, char **);
+	#endif
+	static int localcmd(int, char **);
+	static int pwdcmd(int, char **);
+	static int readcmd(int, char **);
+	static int returncmd(int, char **);
+	static int setcmd(int, char **);
+	static int shiftcmd(int, char **);
+	static int timescmd(int, char **);
+	static int trapcmd(int, char **);
+	static int truecmd(int, char **);
+	static int typecmd(int, char **);
+	static int umaskcmd(int, char **);
+	static int unsetcmd(int, char **);
+	static int waitcmd(int, char **);
+	static int ulimitcmd(int, char **);
+	#if JOBS
+	static int killcmd(int, char **);
+	#endif

-	/*
-	* Expand shell variables and backquotes inside a here document.
-	*/
-	static void
-	expandhere(union node *arg, int fd)
-	{
-	herefd = fd;
-	expandarg(arg, (struct arglist *)NULL, 0);
-	full_write(fd, stackblock(), expdest - (char *)stackblock());
-	}
+	#define BUILTIN_NOSPEC "0"
+	#define BUILTIN_SPECIAL "1"
+	#define BUILTIN_REGULAR "2"
+	#define BUILTIN_SPEC_REG "3"
+	#define BUILTIN_ASSIGN "4"
+	#define BUILTIN_SPEC_ASSG "5"
+	#define BUILTIN_REG_ASSG "6"
+	#define BUILTIN_SPEC_REG_ASSG "7"
+
+	#define IS_BUILTIN_SPECIAL(b) ((b)->name[0] & 1)
+	#define IS_BUILTIN_REGULAR(b) ((b)->name[0] & 2)
+	#define IS_BUILTIN_ASSIGN(b) ((b)->name[0] & 4)
+
+	/* make sure to keep these in proper order since it is searched via bsearch() */
+	static const struct builtincmd builtintab[] = {
+	{ BUILTIN_SPEC_REG ".", dotcmd },
+	{ BUILTIN_SPEC_REG ":", truecmd },
+	#if ENABLE_ASH_BUILTIN_TEST
+	{ BUILTIN_REGULAR "[", testcmd },
+	{ BUILTIN_REGULAR "[[", testcmd },
+	#endif
+	#if ENABLE_ASH_ALIAS
+	{ BUILTIN_REG_ASSG "alias", aliascmd },
+	#endif
+	#if JOBS
+	{ BUILTIN_REGULAR "bg", fg_bgcmd },
+	#endif
+	{ BUILTIN_SPEC_REG "break", breakcmd },
+	{ BUILTIN_REGULAR "cd", cdcmd },
+	{ BUILTIN_NOSPEC "chdir", cdcmd },
+	#if ENABLE_ASH_CMDCMD
+	{ BUILTIN_REGULAR "command", commandcmd },
+	#endif
+	{ BUILTIN_SPEC_REG "continue", breakcmd },
+	#if ENABLE_ASH_BUILTIN_ECHO
+	{ BUILTIN_REGULAR "echo", echocmd },
+	#endif
+	{ BUILTIN_SPEC_REG "eval", evalcmd },
+	{ BUILTIN_SPEC_REG "exec", execcmd },
+	{ BUILTIN_SPEC_REG "exit", exitcmd },
+	{ BUILTIN_SPEC_REG_ASSG "export", exportcmd },
+	{ BUILTIN_REGULAR "false", falsecmd },
+	#if JOBS
+	{ BUILTIN_REGULAR "fg", fg_bgcmd },
+	#endif
+	#if ENABLE_ASH_GETOPTS
+	{ BUILTIN_REGULAR "getopts", getoptscmd },
+	#endif
+	{ BUILTIN_NOSPEC "hash", hashcmd },
+	#if !ENABLE_FEATURE_SH_EXTRA_QUIET
+	{ BUILTIN_NOSPEC "help", helpcmd },
+	#endif
+	#if JOBS
+	{ BUILTIN_REGULAR "jobs", jobscmd },
+	{ BUILTIN_REGULAR "kill", killcmd },
+	#endif
+	#if ENABLE_ASH_MATH_SUPPORT
+	{ BUILTIN_NOSPEC "let", letcmd },
+	#endif
+	{ BUILTIN_ASSIGN "local", localcmd },
+	{ BUILTIN_NOSPEC "pwd", pwdcmd },
+	{ BUILTIN_REGULAR "read", readcmd },
+	{ BUILTIN_SPEC_REG_ASSG "readonly", exportcmd },
+	{ BUILTIN_SPEC_REG "return", returncmd },
+	{ BUILTIN_SPEC_REG "set", setcmd },
+	{ BUILTIN_SPEC_REG "shift", shiftcmd },
+	{ BUILTIN_SPEC_REG "source", dotcmd },
+	#if ENABLE_ASH_BUILTIN_TEST
+	{ BUILTIN_REGULAR "test", testcmd },
+	#endif
+	{ BUILTIN_SPEC_REG "times", timescmd },
+	{ BUILTIN_SPEC_REG "trap", trapcmd },
+	{ BUILTIN_REGULAR "true", truecmd },
+	{ BUILTIN_NOSPEC "type", typecmd },
+	{ BUILTIN_NOSPEC "ulimit", ulimitcmd },
+	{ BUILTIN_REGULAR "umask", umaskcmd },
+	#if ENABLE_ASH_ALIAS
+	{ BUILTIN_REGULAR "unalias", unaliascmd },
+	#endif
+	{ BUILTIN_SPEC_REG "unset", unsetcmd },
+	{ BUILTIN_REGULAR "wait", waitcmd },
+	};

+	#define NUMBUILTINS (sizeof(builtintab) / sizeof(builtintab[0]))
+
+	#define COMMANDCMD (builtintab + 5 + \
+	2 * ENABLE_ASH_BUILTIN_TEST + \
+	ENABLE_ASH_ALIAS + \
+	ENABLE_ASH_JOB_CONTROL)
+	#define EXECCMD (builtintab + 7 + \
+	2 * ENABLE_ASH_BUILTIN_TEST + \
+	ENABLE_ASH_ALIAS + \
+	ENABLE_ASH_JOB_CONTROL + \
+	ENABLE_ASH_CMDCMD + \
+	ENABLE_ASH_BUILTIN_ECHO)

	/*
-	* Perform variable substitution and command substitution on an argument,
-	* placing the resulting list of arguments in arglist. If EXP_FULL is true,
-	* perform splitting and file name expansion. When arglist is NULL, perform
-	* here document expansion.
+	* Execute a simple command.
	*/
+	static int back_exitstatus; /* exit status of backquoted command */
+	static int
+	isassignment(const char *p)
+	{
+	const char *q = endofname(p);
+	if (p == q)
+	return 0;
+	return *q == '=';
+	}
+	static int
+	bltincmd(int argc, char **argv)
+	{
+	/* Preserve exitstatus of a previous possible redirection
+	* as POSIX mandates */
+	return back_exitstatus;
+	}
	static void
-	expandarg(union node arg, struct arglist arglist, int flag)
+	evalcommand(union node *cmd, int flags)
	{
-	struct strlist *sp;
-	char *p;
+	static const struct builtincmd bltin = {
+	"\0\0", bltincmd
+	};
+	struct stackmark smark;
+	union node *argp;
+	struct arglist arglist;
+	struct arglist varlist;
+	char **argv;
+	int argc;
+	const struct strlist *sp;
+	struct cmdentry cmdentry;
+	struct job *jp;
+	char *lastarg;
+	const char *path;
+	int spclbltin;
+	int cmd_is_exec;
+	int status;
+	char **nargv;
+	struct builtincmd *bcmd;
+	int pseudovarflag = 0;

-	argbackq = arg->narg.backquote;
-	STARTSTACKSTR(expdest);
-	ifsfirst.next = NULL;
-	ifslastp = NULL;
-	argstr(arg->narg.text, flag);
-	p = _STPUTC('\0', expdest);
-	expdest = p - 1;
-	if (arglist == NULL) {
-	return; /* here document expanded */
-	}
-	p = grabstackstr(p);
-	exparg.lastp = &exparg.list;
-	/*
-	* TODO - EXP_REDIR
-	*/
-	if (flag & EXP_FULL) {
-	ifsbreakup(p, &exparg);
-	*exparg.lastp = NULL;
-	exparg.lastp = &exparg.list;
-	expandmeta(exparg.list, flag);
-	} else {
-	if (flag & EXP_REDIR) /XXX - for now, just remove escapes /
-	rmescapes(p);
-	sp = stalloc(sizeof(*sp));
-	sp->text = p;
-	*exparg.lastp = sp;
-	exparg.lastp = &sp->next;
-	}
-	if (ifsfirst.next)
-	ifsfree();
-	*exparg.lastp = NULL;
-	if (exparg.list) {
-	*arglist->lastp = exparg.list;
-	arglist->lastp = exparg.lastp;
+	/* First expand the arguments. */
+	TRACE(("evalcommand(0x%lx, %d) called\n", (long)cmd, flags));
+	setstackmark(&smark);
+	back_exitstatus = 0;
+
+	cmdentry.cmdtype = CMDBUILTIN;
+	cmdentry.u.cmd = &bltin;
+	varlist.lastp = &varlist.list;
+	*varlist.lastp = NULL;
+	arglist.lastp = &arglist.list;
+	*arglist.lastp = NULL;
+
+	argc = 0;
+	if (cmd->ncmd.args) {
+	bcmd = find_builtin(cmd->ncmd.args->narg.text);
+	pseudovarflag = bcmd && IS_BUILTIN_ASSIGN(bcmd);
	}
-	}

+	for (argp = cmd->ncmd.args; argp; argp = argp->narg.next) {
+	struct strlist **spp;

-	/*
-	* Perform variable and command substitution. If EXP_FULL is set, output CTLESC
-	* characters to allow for further processing. Otherwise treat
-	* $@ like $* since no splitting will be performed.
-	*/
-	static void
-	argstr(char *p, int flag)
-	{
-	static const char spclchars[] = {
-	'=',
-	':',
-	CTLQUOTEMARK,
-	CTLENDVAR,
-	CTLESC,
-	CTLVAR,
-	CTLBACKQ,
-	CTLBACKQ \| CTLQUOTE,
-	#if ENABLE_ASH_MATH_SUPPORT
-	CTLENDARI,
-	#endif
-	0
-	};
-	const char *reject = spclchars;
-	int c;
-	int quotes = flag & (EXP_FULL \| EXP_CASE); /* do CTLESC */
-	int breakall = flag & EXP_WORD;
-	int inquotes;
-	size_t length;
-	int startloc;
+	spp = arglist.lastp;
+	if (pseudovarflag && isassignment(argp->narg.text))
+	expandarg(argp, &arglist, EXP_VARTILDE);
+	else
+	expandarg(argp, &arglist, EXP_FULL \| EXP_TILDE);

-	if (!(flag & EXP_VARTILDE)) {
-	reject += 2;
-	} else if (flag & EXP_VARTILDE2) {
-	reject++;
+	for (sp = *spp; sp; sp = sp->next)
+	argc++;
	}
-	inquotes = 0;
-	length = 0;
-	if (flag & EXP_TILDE) {
-	char *q;

-	flag &= ~EXP_TILDE;
-	tilde:
-	q = p;
-	if (*q == CTLESC && (flag & EXP_QWORD))
-	q++;
-	if (*q == '~')
-	p = exptilde(p, q, flag);
+	argv = nargv = stalloc(sizeof(char ) (argc + 1));
+	for (sp = arglist.list; sp; sp = sp->next) {
+	TRACE(("evalcommand arg: %s\n", sp->text));
+	*nargv++ = sp->text;
	}
-	start:
-	startloc = expdest - (char *)stackblock();
-	for (;;) {
-	length += strcspn(p + length, reject);
-	c = p[length];
-	if (c && (!(c & 0x80)
-	#if ENABLE_ASH_MATH_SUPPORT
-	\|\| c == CTLENDARI
-	#endif
-	)) {
-	/* c == '=' \|\| c == ':' \|\| c == CTLENDARI */
-	length++;
-	}
-	if (length > 0) {
-	int newloc;
-	expdest = stack_nputstr(p, length, expdest);
-	newloc = expdest - (char *)stackblock();
-	if (breakall && !inquotes && newloc > startloc) {
-	recordregion(startloc, newloc, 0);
-	}
-	startloc = newloc;
-	}
-	p += length + 1;
-	length = 0;
+	*nargv = NULL;

-	switch (c) {
-	case '\0':
-	goto breakloop;
-	case '=':
-	if (flag & EXP_VARTILDE2) {
-	p--;
-	continue;
-	}
-	flag \|= EXP_VARTILDE2;
-	reject++;
-	/* fall through */
-	case ':':
-	/*
-	* sort of a hack - expand tildes in variable
-	* assignments (after the first '=' and after ':'s).
-	*/
-	if (*--p == '~') {
-	goto tilde;
-	}
-	continue;
-	}
+	lastarg = NULL;
+	if (iflag && funcnest == 0 && argc > 0)
+	lastarg = nargv[-1];

-	switch (c) {
-	case CTLENDVAR: /* ??? */
-	goto breakloop;
-	case CTLQUOTEMARK:
-	/* "$@" syntax adherence hack */
-	if (
-	!inquotes &&
-	!memcmp(p, dolatstr, 4) &&
-	(p[4] == CTLQUOTEMARK \|\| (
-	p[4] == CTLENDVAR &&
-	p[5] == CTLQUOTEMARK
-	))
-	) {
-	p = evalvar(p + 1, flag) + 1;
-	goto start;
-	}
-	inquotes = !inquotes;
-	addquote:
-	if (quotes) {
-	p--;
-	length++;
-	startloc++;
-	}
-	break;
-	case CTLESC:
-	startloc++;
-	length++;
-	goto addquote;
-	case CTLVAR:
-	p = evalvar(p, flag);
-	goto start;
-	case CTLBACKQ:
-	c = 0;
-	case CTLBACKQ\|CTLQUOTE:
-	expbackq(argbackq->n, c, quotes);
-	argbackq = argbackq->next;
-	goto start;
-	#if ENABLE_ASH_MATH_SUPPORT
-	case CTLENDARI:
-	p--;
-	expari(quotes);
-	goto start;
-	#endif
-	}
-	}
-	breakloop:
-	;
-	}
+	preverrout_fd = 2;
+	expredir(cmd->ncmd.redirect);
+	status = redirectsafe(cmd->ncmd.redirect, REDIR_PUSH\|REDIR_SAVEFD2);

-	static char *
-	exptilde(char startp, char p, int flag)
-	{
-	char c;
-	char *name;
-	struct passwd *pw;
-	const char *home;
-	int quotes = flag & (EXP_FULL \| EXP_CASE);
-	int startloc;
+	path = vpath.text;
+	for (argp = cmd->ncmd.assign; argp; argp = argp->narg.next) {
+	struct strlist **spp;
+	char *p;

-	name = p + 1;
+	spp = varlist.lastp;
+	expandarg(argp, &varlist, EXP_VARTILDE);

-	while ((c = *++p) != '\0') {
-	switch (c) {
-	case CTLESC:
-	return startp;
-	case CTLQUOTEMARK:
-	return startp;
-	case ':':
-	if (flag & EXP_VARTILDE)
-	goto done;
-	break;
-	case '/':
-	case CTLENDVAR:
-	goto done;
-	}
-	}
-	done:
-	*p = '\0';
-	if (*name == '\0') {
-	home = lookupvar(homestr);
-	} else {
-	pw = getpwnam(name);
-	if (pw == NULL)
-	goto lose;
-	home = pw->pw_dir;
+	/*
+	* Modify the command lookup path, if a PATH= assignment
+	* is present
+	*/
+	p = (*spp)->text;
+	if (varequal(p, path))
+	path = p;
	}
-	if (!home \|\| !*home)
-	goto lose;
-	*p = c;
-	startloc = expdest - (char *)stackblock();
-	strtodest(home, SQSYNTAX, quotes);
-	recordregion(startloc, expdest - (char *)stackblock(), 0);
-	return p;
-	lose:
-	*p = c;
-	return startp;
-	}

+	/* Print the command if xflag is set. */
+	if (xflag) {
+	int n;
+	const char *p = " %s";

-	static void
-	removerecordregions(int endoff)
-	{
-	if (ifslastp == NULL)
-	return;
-
-	if (ifsfirst.endoff > endoff) {
-	while (ifsfirst.next != NULL) {
-	struct ifsregion *ifsp;
-	INT_OFF;
-	ifsp = ifsfirst.next->next;
-	free(ifsfirst.next);
-	ifsfirst.next = ifsp;
-	INT_ON;
-	}
-	if (ifsfirst.begoff > endoff)
-	ifslastp = NULL;
-	else {
-	ifslastp = &ifsfirst;
-	ifsfirst.endoff = endoff;
+	p++;
+	dprintf(preverrout_fd, p, expandstr(ps4val()));
+
+	sp = varlist.list;
+	for (n = 0; n < 2; n++) {
+	while (sp) {
+	dprintf(preverrout_fd, p, sp->text);
+	sp = sp->next;
+	if (*p == '%') {
+	p--;
+	}
+	}
+	sp = arglist.list;
	}
-	return;
+	full_write(preverrout_fd, "\n", 1);
	}

-	ifslastp = &ifsfirst;
-	while (ifslastp->next && ifslastp->next->begoff < endoff)
-	ifslastp=ifslastp->next;
-	while (ifslastp->next != NULL) {
-	struct ifsregion *ifsp;
-	INT_OFF;
-	ifsp = ifslastp->next->next;
-	free(ifslastp->next);
-	ifslastp->next = ifsp;
-	INT_ON;
-	}
-	if (ifslastp->endoff > endoff)
-	ifslastp->endoff = endoff;
-	}
+	cmd_is_exec = 0;
+	spclbltin = -1;

+	/* Now locate the command. */
+	if (argc) {
+	const char *oldpath;
+	int cmd_flag = DO_ERR;

-	#if ENABLE_ASH_MATH_SUPPORT
-	/*
-	* Expand arithmetic expression. Backup to start of expression,
-	* evaluate, place result in (backed up) result, adjust string position.
-	*/
-	static void
-	expari(int quotes)
-	{
-	char p, start;
-	int begoff;
-	int flag;
-	int len;
+	path += 5;
+	oldpath = path;
+	for (;;) {
+	find_command(argv[0], &cmdentry, cmd_flag, path);
+	if (cmdentry.cmdtype == CMDUNKNOWN) {
+	status = 127;
+	flush_stderr();
+	goto bail;
+	}

-	/* ifsfree(); */
+	/* implement bltin and command here */
+	if (cmdentry.cmdtype != CMDBUILTIN)
+	break;
+	if (spclbltin < 0)
+	spclbltin = IS_BUILTIN_SPECIAL(cmdentry.u.cmd);
+	if (cmdentry.u.cmd == EXECCMD)
+	cmd_is_exec++;
+	#if ENABLE_ASH_CMDCMD
+	if (cmdentry.u.cmd == COMMANDCMD) {
+	path = oldpath;
+	nargv = parse_command_args(argv, &path);
+	if (!nargv)
+	break;
+	argc -= nargv - argv;
+	argv = nargv;
+	cmd_flag \|= DO_NOFUNC;
+	} else
+	#endif
+	break;
+	}
+	}

-	/*
-	* This routine is slightly over-complicated for
-	* efficiency. Next we scan backwards looking for the
-	* start of arithmetic.
-	*/
-	start = stackblock();
-	p = expdest - 1;
-	*p = '\0';
-	p--;
-	do {
-	int esc;
+	if (status) {
+	/* We have a redirection error. */
+	if (spclbltin > 0)
+	raise_exception(EXERROR);
+	bail:
+	exitstatus = status;
+	goto out;
+	}

-	while (*p != CTLARI) {
-	p--;
-	#if DEBUG
-	if (p < start) {
-	ash_msg_and_raise_error("missing CTLARI (shouldn't happen)");
+	/* Execute the command. */
+	switch (cmdentry.cmdtype) {
+	default:
+	/* Fork off a child process if necessary. */
+	if (!(flags & EV_EXIT) \|\| trap[0]) {
+	INT_OFF;
+	jp = makejob(cmd, 1);
+	if (forkshell(jp, cmd, FORK_FG) != 0) {
+	exitstatus = waitforjob(jp);
+	INT_ON;
+	break;
	}
-	#endif
+	FORCE_INT_ON;
	}
+	listsetvar(varlist.list, VEXPORT\|VSTACK);
+	shellexec(argv, path, cmdentry.u.index);
+	/* NOTREACHED */

-	esc = esclen(start, p);
-	if (!(esc % 2)) {
-	break;
+	case CMDBUILTIN:
+	cmdenviron = varlist.list;
+	if (cmdenviron) {
+	struct strlist *list = cmdenviron;
+	int i = VNOSET;
+	if (spclbltin > 0 \|\| argc == 0) {
+	i = 0;
+	if (cmd_is_exec && argc > 1)
+	i = VEXPORT;
+	}
+	listsetvar(list, i);
	}
+	if (evalbltin(cmdentry.u.cmd, argc, argv)) {
+	int exit_status;
+	int i, j;

-	p -= esc + 1;
-	} while (1);
+	i = exception;
+	if (i == EXEXIT)
+	goto raise;

-	begoff = p - start;
+	exit_status = 2;
+	j = 0;
+	if (i == EXINT)
+	j = SIGINT;
+	if (i == EXSIG)
+	j = pendingsigs;
+	if (j)
+	exit_status = j + 128;
+	exitstatus = exit_status;

-	removerecordregions(begoff);
+	if (i == EXINT \|\| spclbltin > 0) {
+	raise:
+	longjmp(exception_handler->loc, 1);
+	}
+	FORCE_INT_ON;
+	}
+	break;

-	flag = p[1];
+	case CMDFUNCTION:
+	listsetvar(varlist.list, 0);
+	if (evalfun(cmdentry.u.func, argc, argv, flags))
+	goto raise;
+	break;
+	}

-	expdest = p;
+	out:
+	popredir(cmd_is_exec);
+	if (lastarg)
+	/* dsl: I think this is intended to be used to support
+	* '_' in 'vi' command mode during line editing...
+	* However I implemented that within libedit itself.
+	*/
+	setvar("_", lastarg, 0);
+	popstackmark(&smark);
+	}

-	if (quotes)
-	rmescapes(p + 2);
+	static int
+	evalbltin(const struct builtincmd cmd, int argc, char *argv)
+	{
+	char *volatile savecmdname;
+	struct jmploc *volatile savehandler;
+	struct jmploc jmploc;
+	int i;

-	len = cvtnum(dash_arith(p + 2));
+	savecmdname = commandname;
+	i = setjmp(jmploc.loc);
+	if (i)
+	goto cmddone;
+	savehandler = exception_handler;
+	exception_handler = &jmploc;
+	commandname = argv[0];
+	argptr = argv + 1;
+	optptr = NULL; /* initialize nextopt */
+	exitstatus = (*cmd->builtin)(argc, argv);
+	flush_stdout_stderr();
+	cmddone:
+	exitstatus \|= ferror(stdout);
+	clearerr(stdout);
+	commandname = savecmdname;
+	exsig = 0;
+	exception_handler = savehandler;

-	if (flag != '"')
-	recordregion(begoff, begoff + len, 0);
+	return i;
	}
-	#endif

+	static struct localvar *localvars;

	/*
-	* Execute a command inside back quotes. If it's a builtin command, we
-	* want to save its output in a block obtained from malloc. Otherwise
-	* we fork off a subprocess and get the output of the command via a pipe.
-	* Should be called with interrupts off.
+	* Called after a function returns.
+	* Interrupts must be off.
	*/
-	struct backcmd { /* result of evalbackcmd */
-	int fd; /* file descriptor to read from */
-	char buf; / buffer */
-	int nleft; /* number of chars in buffer */
-	struct job jp; / job structure for command */
-	};
-
	static void
-	evalbackcmd(union node n, struct backcmd result)
+	poplocalvars(void)
	{
-	int saveherefd;
-
-	result->fd = -1;
-	result->buf = NULL;
-	result->nleft = 0;
-	result->jp = NULL;
-	if (n == NULL) {
-	goto out;
-	}
-
-	saveherefd = herefd;
-	herefd = -1;
-
-	{
-	int pip[2];
-	struct job *jp;
+	struct localvar *lvp;
+	struct var *vp;

-	if (pipe(pip) < 0)
-	ash_msg_and_raise_error("Pipe call failed");
-	jp = makejob(n, 1);
-	if (forkshell(jp, n, FORK_NOJOB) == 0) {
-	FORCE_INT_ON;
-	close(pip[0]);
-	if (pip[1] != 1) {
-	close(1);
-	copyfd(pip[1], 1);
-	close(pip[1]);
-	}
-	eflag = 0;
-	evaltreenr(n, EV_EXIT);
-	/* NOTREACHED */
+	while ((lvp = localvars) != NULL) {
+	localvars = lvp->next;
+	vp = lvp->vp;
+	TRACE(("poplocalvar %s", vp ? vp->text : "-"));
+	if (vp == NULL) { /* $- saved */
+	memcpy(optlist, lvp->text, sizeof(optlist));
+	free((char*)lvp->text);
+	optschanged();
+	} else if ((lvp->flags & (VUNSET\|VSTRFIXED)) == VUNSET) {
+	unsetvar(vp->text);
+	} else {
+	if (vp->func)
+	(*vp->func)(strchrnul(lvp->text, '=') + 1);
+	if ((vp->flags & (VTEXTFIXED\|VSTACK)) == 0)
+	free((char*)vp->text);
+	vp->flags = lvp->flags;
+	vp->text = lvp->text;
	}
-	close(pip[1]);
-	result->fd = pip[0];
-	result->jp = jp;
+	free(lvp);
	}
-	herefd = saveherefd;
-	out:
-	TRACE(("evalbackcmd done: fd=%d buf=0x%x nleft=%d jp=0x%x\n",
-	result->fd, result->buf, result->nleft, result->jp));
	}

	/*
-	* Expand stuff in backwards quotes.
+	* Free a parse tree.
	*/
	static void
-	expbackq(union node *cmd, int quoted, int quotes)
+	freefunc(struct funcnode *f)
	{
-	struct backcmd in;
-	int i;
-	char buf[128];
-	char *p;
-	char *dest;
-	int startloc;
-	int syntax = quoted? DQSYNTAX : BASESYNTAX;
-	struct stackmark smark;
-
-	INT_OFF;
-	setstackmark(&smark);
-	dest = expdest;
-	startloc = dest - (char *)stackblock();
-	grabstackstr(dest);
-	evalbackcmd(cmd, &in);
-	popstackmark(&smark);
+	if (f && --f->count < 0)
+	free(f);
+	}

-	p = in.buf;
-	i = in.nleft;
-	if (i == 0)
-	goto read;
-	for (;;) {
-	memtodest(p, i, syntax, quotes);
-	read:
-	if (in.fd < 0)
-	break;
-	i = safe_read(in.fd, buf, sizeof(buf));
-	TRACE(("expbackq: read returns %d\n", i));
-	if (i <= 0)
-	break;
-	p = buf;
-	}
+	static int
+	evalfun(struct funcnode func, int argc, char *argv, int flags)
+	{
+	volatile struct shparam saveparam;
+	struct localvar *volatile savelocalvars;
+	struct jmploc *volatile savehandler;
+	struct jmploc jmploc;
+	int e;

-	if (in.buf)
-	free(in.buf);
-	if (in.fd >= 0) {
-	close(in.fd);
-	back_exitstatus = waitforjob(in.jp);
+	saveparam = shellparam;
+	savelocalvars = localvars;
+	e = setjmp(jmploc.loc);
+	if (e) {
+	goto funcdone;
	}
+	INT_OFF;
+	savehandler = exception_handler;
+	exception_handler = &jmploc;
+	localvars = NULL;
+	shellparam.malloc = 0;
+	func->count++;
+	funcnest++;
+	INT_ON;
+	shellparam.nparam = argc - 1;
+	shellparam.p = argv + 1;
+	#if ENABLE_ASH_GETOPTS
+	shellparam.optind = 1;
+	shellparam.optoff = -1;
+	#endif
+	evaltree(&func->n, flags & EV_TESTED);
+	funcdone:
+	INT_OFF;
+	funcnest--;
+	freefunc(func);
+	poplocalvars();
+	localvars = savelocalvars;
+	freeparam(&shellparam);
+	shellparam = saveparam;
+	exception_handler = savehandler;
	INT_ON;
+	evalskip &= ~SKIPFUNC;
+	return e;
+	}

-	/* Eat all trailing newlines */
-	dest = expdest;
-	for (; dest > (char *)stackblock() && dest[-1] == '\n';)
-	STUNPUTC(dest);
-	expdest = dest;

-	if (quoted == 0)
-	recordregion(startloc, dest - (char *)stackblock(), 0);
-	TRACE(("evalbackq: size=%d: \"%.*s\"\n",
-	(dest - (char *)stackblock()) - startloc,
-	(dest - (char *)stackblock()) - startloc,
-	stackblock() + startloc));
+	static int
+	goodname(const char *p)
+	{
+	return !*endofname(p);
	}


-	static char *
-	scanleft(char startp, char rmesc, char rmescend, char str, int quotes,
-	int zero)
+	/*
+	* Search for a command. This is called before we fork so that the
+	* location of the command will be available in the parent as well as
+	* the child. The check for "goodname" is an overly conservative
+	* check that the name will not be subject to expansion.
+	*/
+	static void
+	prehash(union node *n)
	{
-	char *loc;
-	char *loc2;
-	char c;
+	struct cmdentry entry;

-	loc = startp;
-	loc2 = rmesc;
-	do {
-	int match;
-	const char *s = loc2;
-	c = *loc2;
-	if (zero) {
-	*loc2 = '\0';
-	s = rmesc;
-	}
-	match = pmatch(str, s);
-	*loc2 = c;
-	if (match)
-	return loc;
-	if (quotes && *loc == CTLESC)
-	loc++;
-	loc++;
-	loc2++;
-	} while (c);
-	return 0;
+	if (n->type == NCMD && n->ncmd.args && goodname(n->ncmd.args->narg.text))
+	find_command(n->ncmd.args->narg.text, &entry, 0, pathval());
	}


-	static char *
-	scanright(char startp, char rmesc, char rmescend, char str, int quotes,
-	int zero)
+	/*
+	* Builtin commands. Builtin commands whose functions are closely
+	* tied to evaluation are implemented here.
+	*/
+
+	/*
+	* Handle break and continue commands. Break, continue, and return are
+	* all handled by setting the evalskip flag. The evaluation routines
+	* above all check this flag, and if it is set they start skipping
+	* commands rather than executing them. The variable skipcount is
+	* the number of loops to break/continue, or the number of function
+	* levels to return. (The latter is always 1.) It should probably
+	* be an error to break out of more loops than exist, but it isn't
+	* in the standard shell so we don't make it one here.
+	*/
+
+	static int
+	breakcmd(int argc, char **argv)
	{
-	int esc = 0;
-	char *loc;
-	char *loc2;
+	int n = argc > 1 ? number(argv[1]) : 1;

-	for (loc = str - 1, loc2 = rmescend; loc >= startp; loc2--) {
-	int match;
-	char c = *loc2;
-	const char *s = loc2;
-	if (zero) {
-	*loc2 = '\0';
-	s = rmesc;
-	}
-	match = pmatch(str, s);
-	*loc2 = c;
-	if (match)
-	return loc;
-	loc--;
-	if (quotes) {
-	if (--esc < 0) {
-	esc = esclen(startp, loc);
-	}
-	if (esc % 2) {
-	esc--;
-	loc--;
-	}
-	}
+	if (n <= 0)
+	ash_msg_and_raise_error(illnum, argv[1]);
+	if (n > loopnest)
+	n = loopnest;
+	if (n > 0) {
+	evalskip = (**argv == 'c')? SKIPCONT : SKIPBREAK;
+	skipcount = n;
	}
	return 0;
	}

-	static const char *
-	subevalvar(char p, char str, int strloc, int subtype, int startloc, int varflags, int quotes)
+	/*
+	* The return command.
+	*/
+	static int
+	returncmd(int argc, char **argv)
	{
-	char *startp;
-	char *loc;
-	int saveherefd = herefd;
-	struct nodelist *saveargbackq = argbackq;
-	int amount;
-	char rmesc, rmescend;
-	int zero;
-	char (scan)(char , char , char , char , int , int);
-
-	herefd = -1;
-	argstr(p, subtype != VSASSIGN && subtype != VSQUESTION ? EXP_CASE : 0);
-	STPUTC('\0', expdest);
-	herefd = saveherefd;
-	argbackq = saveargbackq;
-	startp = stackblock() + startloc;
-
-	switch (subtype) {
-	case VSASSIGN:
-	setvar(str, startp, 0);
-	amount = startp - expdest;
-	STADJUST(amount, expdest);
-	return startp;
-
-	case VSQUESTION:
-	varunset(p, str, startp, varflags);
-	/* NOTREACHED */
-	}
-
-	subtype -= VSTRIMRIGHT;
-	#if DEBUG
-	if (subtype < 0 \|\| subtype > 3)
-	abort();
-	#endif
+	/*
+	* If called outside a function, do what ksh does;
+	* skip the rest of the file.
+	*/
+	evalskip = funcnest ? SKIPFUNC : SKIPFILE;
+	return argv[1] ? number(argv[1]) : exitstatus;
+	}

-	rmesc = startp;
-	rmescend = stackblock() + strloc;
-	if (quotes) {
-	rmesc = _rmescapes(startp, RMESCAPE_ALLOC \| RMESCAPE_GROW);
-	if (rmesc != startp) {
-	rmescend = expdest;
-	startp = stackblock() + startloc;
-	}
-	}
-	rmescend--;
-	str = stackblock() + strloc;
-	preglob(str, varflags & VSQUOTE, 0);
+	static int
+	falsecmd(int argc, char **argv)
+	{
+	return 1;
+	}

-	/* zero = subtype == VSTRIMLEFT \|\| subtype == VSTRIMLEFTMAX */
-	zero = subtype >> 1;
-	/* VSTRIMLEFT/VSTRIMRIGHTMAX -> scanleft */
-	scan = (subtype & 1) ^ zero ? scanleft : scanright;
+	static int
+	truecmd(int argc, char **argv)
+	{
+	return 0;
+	}

-	loc = scan(startp, rmesc, rmescend, str, quotes, zero);
-	if (loc) {
-	if (zero) {
-	memmove(startp, loc, str - loc);
-	loc = startp + (str - loc) - 1;
-	}
-	*loc = '\0';
-	amount = loc - expdest;
-	STADJUST(amount, expdest);
+	static int
+	execcmd(int argc, char **argv)
+	{
+	if (argc > 1) {
+	iflag = 0; /* exit on error */
+	mflag = 0;
+	optschanged();
+	shellexec(argv + 1, pathval(), 0);
	}
-	return loc;
+	return 0;
	}


+	/* ============ Executing commands */
+
	/*
-	* Expand a variable, and return a pointer to the next character in the
-	* input string.
+	* When commands are first encountered, they are entered in a hash table.
+	* This ensures that a full path search will not have to be done for them
+	* on each invocation.
+	*
+	* We should investigate converting to a linear search, even though that
+	* would make the command name "hash" a misnomer.
	*/
-	static char *
-	evalvar(char *p, int flag)
-	{
-	int subtype;
-	int varflags;
-	char *var;
-	int patloc;
-	int c;
-	int startloc;
-	ssize_t varlen;
-	int easy;
-	int quotes;
-	int quoted;

-	quotes = flag & (EXP_FULL \| EXP_CASE);
-	varflags = *p++;
-	subtype = varflags & VSTYPE;
-	quoted = varflags & VSQUOTE;
-	var = p;
-	easy = (!quoted \|\| (*var == '@' && shellparam.nparam));
-	startloc = expdest - (char *)stackblock();
-	p = strchr(p, '=') + 1;
+	#define CMDTABLESIZE 31 /* should be prime */
+	#define ARB 1 /* actual size determined at run time */

-	again:
-	varlen = varvalue(var, varflags, flag);
-	if (varflags & VSNUL)
-	varlen--;
+	struct tblentry {
+	struct tblentry next; / next entry in hash chain */
+	union param param; /* definition of builtin function */
+	short cmdtype; /* index identifying command */
+	char rehash; /* if set, cd done since entry created */
+	char cmdname[ARB]; /* name of command */
+	};

-	if (subtype == VSPLUS) {
-	varlen = -1 - varlen;
-	goto vsplus;
-	}
+	static struct tblentry *cmdtable[CMDTABLESIZE];
+	static int builtinloc = -1; /* index in path of %builtin, or -1 */

-	if (subtype == VSMINUS) {
-	vsplus:
-	if (varlen < 0) {
-	argstr(
-	p, flag \| EXP_TILDE \|
-	(quoted ? EXP_QWORD : EXP_WORD)
-	);
-	goto end;
-	}
-	if (easy)
-	goto record;
-	goto end;
-	}
+	static void
+	tryexec(char cmd, char argv, char *envp)
+	{
+	int repeated = 0;
+	struct BB_applet *a;
+	int argc = 0;
+	char **c;

-	if (subtype == VSASSIGN \|\| subtype == VSQUESTION) {
-	if (varlen < 0) {
-	if (subevalvar(p, var, 0, subtype, startloc, varflags, 0)) {
-	varflags &= ~VSNUL;
-	/*
-	* Remove any recorded regions beyond
-	* start of variable
-	*/
-	removerecordregions(startloc);
-	goto again;
-	}
-	goto end;
+	if (strchr(cmd, '/') == NULL
+	&& (a = find_applet_by_name(cmd)) != NULL
+	&& is_safe_applet(cmd)
+	) {
+	c = argv;
+	while (*c != NULL) {
+	c++; argc++;
	}
-	if (easy)
-	goto record;
-	goto end;
-	}
-
-	if (varlen < 0 && uflag)
-	varunset(p, var, 0, 0);
-
-	if (subtype == VSLENGTH) {
-	cvtnum(varlen > 0 ? varlen : 0);
-	goto record;
+	applet_name = cmd;
+	exit(a->main(argc, argv));
	}
-
-	if (subtype == VSNORMAL) {
-	if (!easy)
-	goto end;
-	record:
-	recordregion(startloc, expdest - (char *)stackblock(), quoted);
-	goto end;
+	#if ENABLE_FEATURE_SH_STANDALONE_SHELL
+	if (find_applet_by_name(cmd) != NULL) {
+	/* re-exec ourselves with the new arguments */
+	execve(CONFIG_BUSYBOX_EXEC_PATH, argv, envp);
+	/* If they called chroot or otherwise made the binary no longer
+	* executable, fall through */
	}
+	#endif

-	#if DEBUG
-	switch (subtype) {
-	case VSTRIMLEFT:
-	case VSTRIMLEFTMAX:
-	case VSTRIMRIGHT:
-	case VSTRIMRIGHTMAX:
-	break;
-	default:
-	abort();
-	}
+	repeat:
+	#ifdef SYSV
+	do {
+	execve(cmd, argv, envp);
+	} while (errno == EINTR);
+	#else
+	execve(cmd, argv, envp);
	#endif
+	if (repeated++) {
+	free(argv);
+	} else if (errno == ENOEXEC) {
+	char **ap;
+	char **new;

-	if (varlen >= 0) {
-	/*
-	* Terminate the string and start recording the pattern
-	* right after it
-	*/
-	STPUTC('\0', expdest);
-	patloc = expdest - (char *)stackblock();
-	if (subevalvar(p, NULL, patloc, subtype,
-	startloc, varflags, quotes) == 0) {
-	int amount = expdest - (
-	(char *)stackblock() + patloc - 1
-	);
-	STADJUST(-amount, expdest);
-	}
-	/* Remove any recorded regions beyond start of variable */
-	removerecordregions(startloc);
-	goto record;
+	for (ap = argv; *ap; ap++)
+	;
+	ap = new = ckmalloc((ap - argv + 2) * sizeof(char *));
+	ap[1] = cmd;
+	ap = cmd = (char )DEFAULT_SHELL;
+	ap += 2;
+	argv++;
+	while ((ap++ = argv++))
+	;
+	argv = new;
+	goto repeat;
	}
+	}

-	end:
-	if (subtype != VSNORMAL) { /* skip to end of alternative */
-	int nesting = 1;
-	for (;;) {
-	c = *p++;
-	if (c == CTLESC)
-	p++;
-	else if (c == CTLBACKQ \|\| c == (CTLBACKQ\|CTLQUOTE)) {
-	if (varlen >= 0)
-	argbackq = argbackq->next;
-	} else if (c == CTLVAR) {
-	if ((*p++ & VSTYPE) != VSNORMAL)
-	nesting++;
-	} else if (c == CTLENDVAR) {
-	if (--nesting == 0)
-	break;
+	/*
+	* Exec a program. Never returns. If you change this routine, you may
+	* have to change the find_command routine as well.
+	*/
+	#define environment() listvars(VEXPORT, VUNSET, 0)
+	static void shellexec(char *, const char , int) ATTRIBUTE_NORETURN;
+	static void
+	shellexec(char *argv, const char path, int idx)
+	{
+	char *cmdname;
+	int e;
+	char **envp;
+	int exerrno;
+
+	clearredir(1);
+	envp = environment();
+	if (strchr(argv[0], '/') \|\| is_safe_applet(argv[0])
+	#if ENABLE_FEATURE_SH_STANDALONE_SHELL
+	\|\| find_applet_by_name(argv[0])
+	#endif
+	) {
+	tryexec(argv[0], argv, envp);
+	e = errno;
+	} else {
+	e = ENOENT;
+	while ((cmdname = padvance(&path, argv[0])) != NULL) {
+	if (--idx < 0 && pathopt == NULL) {
+	tryexec(cmdname, argv, envp);
+	if (errno != ENOENT && errno != ENOTDIR)
+	e = errno;
	}
+	stunalloc(cmdname);
	}
	}
-	return p;
+
+	/* Map to POSIX errors */
+	switch (e) {
+	case EACCES:
+	exerrno = 126;
+	break;
+	case ENOENT:
+	exerrno = 127;
+	break;
+	default:
+	exerrno = 2;
+	break;
+	}
+	exitstatus = exerrno;
+	TRACE(("shellexec failed for %s, errno %d, suppressint %d\n",
+	argv[0], e, suppressint ));
+	ash_msg_and_raise(EXEXEC, "%s: %s", argv[0], errmsg(e, "not found"));
+	/* NOTREACHED */
	}

+	static void
+	printentry(struct tblentry *cmdp)
+	{
+	int idx;
+	const char *path;
+	char *name;
+
+	idx = cmdp->param.index;
+	path = pathval();
+	do {
+	name = padvance(&path, cmdp->cmdname);
+	stunalloc(name);
+	} while (--idx >= 0);
+	out1fmt("%s%s\n", name, (cmdp->rehash ? "*" : nullstr));
+	}

	/*
-	* Put a string on the stack.
+	* Clear out command entries. The argument specifies the first entry in
+	* PATH which has changed.
	*/
	static void
-	memtodest(const char *p, size_t len, int syntax, int quotes)
+	clearcmdentry(int firstchange)
	{
-	char *q = expdest;
-
-	q = makestrspace(len * 2, q);
+	struct tblentry **tblp;
+	struct tblentry **pp;
+	struct tblentry *cmdp;

-	while (len--) {
-	int c = SC2INT(*p++);
-	if (!c)
-	continue;
-	if (quotes && (SIT(c, syntax) == CCTL \|\| SIT(c, syntax) == CBACK))
-	USTPUTC(CTLESC, q);
-	USTPUTC(c, q);
+	INT_OFF;
+	for (tblp = cmdtable; tblp < &cmdtable[CMDTABLESIZE]; tblp++) {
+	pp = tblp;
+	while ((cmdp = *pp) != NULL) {
+	if ((cmdp->cmdtype == CMDNORMAL &&
+	cmdp->param.index >= firstchange)
+	\|\| (cmdp->cmdtype == CMDBUILTIN &&
+	builtinloc >= firstchange)
+	) {
+	*pp = cmdp->next;
+	free(cmdp);
+	} else {
+	pp = &cmdp->next;
+	}
+	}
	}
-
-	expdest = q;
+	INT_ON;
	}

+	/*
+	* Locate a command in the command hash table. If "add" is nonzero,
+	* add the command to the table if it is not already present. The
+	* variable "lastcmdentry" is set to point to the address of the link
+	* pointing to the entry, so that delete_cmd_entry can delete the
+	* entry.
+	*
+	* Interrupts must be off if called with add != 0.
+	*/
+	static struct tblentry **lastcmdentry;

-	static void
-	strtodest(const char *p, int syntax, int quotes)
+	static struct tblentry *
+	cmdlookup(const char *name, int add)
	{
-	memtodest(p, strlen(p), syntax, quotes);
+	unsigned int hashval;
+	const char *p;
+	struct tblentry *cmdp;
+	struct tblentry **pp;
+
+	p = name;
+	hashval = (unsigned char)*p << 4;
+	while (*p)
+	hashval += (unsigned char)*p++;
+	hashval &= 0x7FFF;
+	pp = &cmdtable[hashval % CMDTABLESIZE];
+	for (cmdp = *pp; cmdp; cmdp = cmdp->next) {
+	if (strcmp(cmdp->cmdname, name) == 0)
+	break;
+	pp = &cmdp->next;
+	}
+	if (add && cmdp == NULL) {
+	cmdp = *pp = ckmalloc(sizeof(struct tblentry) - ARB
+	+ strlen(name) + 1);
+	cmdp->next = NULL;
+	cmdp->cmdtype = CMDUNKNOWN;
+	strcpy(cmdp->cmdname, name);
+	}
+	lastcmdentry = pp;
+	return cmdp;
	}

+	/*
+	* Delete the command entry returned on the last lookup.
+	*/
+	static void
+	delete_cmd_entry(void)
+	{
+	struct tblentry *cmdp;
+
+	INT_OFF;
+	cmdp = *lastcmdentry;
+	*lastcmdentry = cmdp->next;
+	if (cmdp->cmdtype == CMDFUNCTION)
+	freefunc(cmdp->param.func);
+	free(cmdp);
+	INT_ON;
+	}

	/*
-	* Add the value of a specialized variable to the stack string.
+	* Add a new command entry, replacing any existing command entry for
+	* the same name - except special builtins.
	*/
-	static ssize_t
-	varvalue(char *name, int varflags, int flags)
+	static void
+	addcmdentry(char name, struct cmdentry entry)
	{
-	int num;
-	char *p;
-	int i;
-	int sep = 0;
-	int sepq = 0;
-	ssize_t len = 0;
-	char **ap;
-	int syntax;
-	int quoted = varflags & VSQUOTE;
-	int subtype = varflags & VSTYPE;
-	int quotes = flags & (EXP_FULL \| EXP_CASE);
+	struct tblentry *cmdp;

-	if (quoted && (flags & EXP_FULL))
-	sep = 1 << CHAR_BIT;
+	cmdp = cmdlookup(name, 1);
+	if (cmdp->cmdtype == CMDFUNCTION) {
+	freefunc(cmdp->param.func);
+	}
+	cmdp->cmdtype = entry->cmdtype;
+	cmdp->param = entry->u;
+	cmdp->rehash = 0;
+	}

-	syntax = quoted ? DQSYNTAX : BASESYNTAX;
-	switch (*name) {
-	case '$':
-	num = rootpid;
-	goto numvar;
-	case '?':
-	num = exitstatus;
-	goto numvar;
-	case '#':
-	num = shellparam.nparam;
-	goto numvar;
-	case '!':
-	num = backgndpid;
-	if (num == 0)
-	return -1;
-	numvar:
-	len = cvtnum(num);
-	break;
-	case '-':
-	p = makestrspace(NOPTS, expdest);
-	for (i = NOPTS - 1; i >= 0; i--) {
-	if (optlist[i]) {
-	USTPUTC(optletters(i), p);
-	len++;
+	static int
+	hashcmd(int argc, char **argv)
+	{
+	struct tblentry **pp;
+	struct tblentry *cmdp;
+	int c;
+	struct cmdentry entry;
+	char *name;
+
+	while ((c = nextopt("r")) != '\0') {
+	clearcmdentry(0);
+	return 0;
+	}
+	if (*argptr == NULL) {
+	for (pp = cmdtable; pp < &cmdtable[CMDTABLESIZE]; pp++) {
+	for (cmdp = *pp; cmdp; cmdp = cmdp->next) {
+	if (cmdp->cmdtype == CMDNORMAL)
+	printentry(cmdp);
	}
	}
-	expdest = p;
-	break;
-	case '@':
-	if (sep)
-	goto param;
-	/* fall through */
-	case '*':
-	sep = ifsset() ? SC2INT(ifsval()[0]) : ' ';
-	if (quotes && (SIT(sep, syntax) == CCTL \|\| SIT(sep, syntax) == CBACK))
-	sepq = 1;
-	param:
-	ap = shellparam.p;
-	if (!ap)
-	return -1;
-	while ((p = *ap++)) {
-	size_t partlen;
-
-	partlen = strlen(p);
-	len += partlen;
-
-	if (!(subtype == VSPLUS \|\| subtype == VSLENGTH))
-	memtodest(p, partlen, syntax, quotes);
+	return 0;
+	}
+	c = 0;
+	while ((name = *argptr) != NULL) {
+	cmdp = cmdlookup(name, 0);
+	if (cmdp != NULL
+	&& (cmdp->cmdtype == CMDNORMAL
+	\|\| (cmdp->cmdtype == CMDBUILTIN && builtinloc >= 0)))
+	delete_cmd_entry();
+	find_command(name, &entry, DO_ERR, pathval());
+	if (entry.cmdtype == CMDUNKNOWN)
+	c = 1;
+	argptr++;
+	}
+	return c;
+	}

-	if (*ap && sep) {
-	char *q;
+	/*
+	* Resolve a command name. If you change this routine, you may have to
+	* change the shellexec routine as well.
+	*/
+	static void
+	find_command(char name, struct cmdentry entry, int act, const char *path)
+	{
+	struct tblentry *cmdp;
+	int idx;
+	int prev;
+	char *fullname;
+	struct stat statb;
+	int e;
+	int updatetbl;
+	struct builtincmd *bcmd;

-	len++;
-	if (subtype == VSPLUS \|\| subtype == VSLENGTH) {
+	/* If name contains a slash, don't use PATH or hash table */
+	if (strchr(name, '/') != NULL) {
+	entry->u.index = -1;
+	if (act & DO_ABS) {
+	while (stat(name, &statb) < 0) {
+	#ifdef SYSV
+	if (errno == EINTR)
	continue;
-	}
-	q = expdest;
-	if (sepq)
-	STPUTC(CTLESC, q);
-	STPUTC(sep, q);
-	expdest = q;
+	#endif
+	entry->cmdtype = CMDUNKNOWN;
+	return;
	}
	}
-	return len;
-	case '0':
-	case '1':
-	case '2':
-	case '3':
-	case '4':
-	case '5':
-	case '6':
-	case '7':
-	case '8':
-	case '9':
-	num = atoi(name);
-	if (num < 0 \|\| num > shellparam.nparam)
-	return -1;
-	p = num ? shellparam.p[num - 1] : arg0;
-	goto value;
-	default:
-	p = lookupvar(name);
-	value:
-	if (!p)
-	return -1;
+	entry->cmdtype = CMDNORMAL;
+	return;
+	}

-	len = strlen(p);
-	if (!(subtype == VSPLUS \|\| subtype == VSLENGTH))
-	memtodest(p, len, syntax, quotes);
-	return len;
+	#if ENABLE_FEATURE_SH_STANDALONE_SHELL
+	if (find_applet_by_name(name)) {
+	entry->cmdtype = CMDNORMAL;
+	entry->u.index = -1;
+	return;
	}
+	#endif

-	if (subtype == VSPLUS \|\| subtype == VSLENGTH)
-	STADJUST(-len, expdest);
-	return len;
-	}
+	if (is_safe_applet(name)) {
+	entry->cmdtype = CMDNORMAL;
+	entry->u.index = -1;
+	return;
+	}

+	updatetbl = (path == pathval());
+	if (!updatetbl) {
+	act \|= DO_ALTPATH;
+	if (strstr(path, "%builtin") != NULL)
+	act \|= DO_ALTBLTIN;
+	}

-	/*
-	* Record the fact that we have to scan this region of the
-	* string for IFS characters.
-	*/
-	static void
-	recordregion(int start, int end, int nulonly)
-	{
-	struct ifsregion *ifsp;
+	/* If name is in the table, check answer will be ok */
+	cmdp = cmdlookup(name, 0);
+	if (cmdp != NULL) {
+	int bit;

-	if (ifslastp == NULL) {
-	ifsp = &ifsfirst;
-	} else {
-	INT_OFF;
-	ifsp = ckmalloc(sizeof(*ifsp));
-	ifsp->next = NULL;
-	ifslastp->next = ifsp;
-	INT_ON;
+	switch (cmdp->cmdtype) {
+	default:
+	#if DEBUG
+	abort();
+	#endif
+	case CMDNORMAL:
+	bit = DO_ALTPATH;
+	break;
+	case CMDFUNCTION:
+	bit = DO_NOFUNC;
+	break;
+	case CMDBUILTIN:
+	bit = DO_ALTBLTIN;
+	break;
+	}
+	if (act & bit) {
+	updatetbl = 0;
+	cmdp = NULL;
+	} else if (cmdp->rehash == 0)
+	/* if not invalidated by cd, we're done */
+	goto success;
	}
-	ifslastp = ifsp;
-	ifslastp->begoff = start;
-	ifslastp->endoff = end;
-	ifslastp->nulonly = nulonly;
-	}

+	/* If %builtin not in path, check for builtin next */
+	bcmd = find_builtin(name);
+	if (bcmd && (IS_BUILTIN_REGULAR(bcmd) \|\| (
+	act & DO_ALTPATH ? !(act & DO_ALTBLTIN) : builtinloc <= 0
+	)))
+	goto builtin_success;

-	/*
-	* Break the argument string into pieces based upon IFS and add the
-	* strings to the argument list. The regions of the string to be
-	* searched for IFS characters have been stored by recordregion.
-	*/
-	static void
-	ifsbreakup(char string, struct arglist arglist)
-	{
-	struct ifsregion *ifsp;
-	struct strlist *sp;
-	char *start;
-	char *p;
-	char *q;
-	const char ifs, realifs;
-	int ifsspc;
-	int nulonly;
+	/* We have to search path. */
+	prev = -1; /* where to start */
+	if (cmdp && cmdp->rehash) { /* doing a rehash */
+	if (cmdp->cmdtype == CMDBUILTIN)
+	prev = builtinloc;
+	else
+	prev = cmdp->param.index;
+	}

-	start = string;
-	if (ifslastp != NULL) {
-	ifsspc = 0;
-	nulonly = 0;
-	realifs = ifsset() ? ifsval() : defifs;
-	ifsp = &ifsfirst;
-	do {
-	p = string + ifsp->begoff;
-	nulonly = ifsp->nulonly;
-	ifs = nulonly ? nullstr : realifs;
-	ifsspc = 0;
-	while (p < string + ifsp->endoff) {
-	q = p;
-	if (*p == CTLESC)
-	p++;
-	if (!strchr(ifs, *p)) {
-	p++;
-	continue;
-	}
-	if (!nulonly)
-	ifsspc = (strchr(defifs, *p) != NULL);
-	/* Ignore IFS whitespace at start */
-	if (q == start && ifsspc) {
-	p++;
-	start = p;
-	continue;
-	}
-	*q = '\0';
-	sp = stalloc(sizeof(*sp));
-	sp->text = start;
-	*arglist->lastp = sp;
-	arglist->lastp = &sp->next;
-	p++;
-	if (!nulonly) {
-	for (;;) {
-	if (p >= string + ifsp->endoff) {
-	break;
-	}
-	q = p;
-	if (*p == CTLESC)
-	p++;
-	if (strchr(ifs, *p) == NULL ) {
-	p = q;
-	break;
-	} else if (strchr(defifs, *p) == NULL) {
-	if (ifsspc) {
-	p++;
-	ifsspc = 0;
-	} else {
-	p = q;
-	break;
-	}
-	} else
-	p++;
-	}
-	}
-	start = p;
-	} /* while */
-	ifsp = ifsp->next;
-	} while (ifsp != NULL);
-	if (nulonly)
-	goto add;
+	e = ENOENT;
+	idx = -1;
+	loop:
+	while ((fullname = padvance(&path, name)) != NULL) {
+	stunalloc(fullname);
+	idx++;
+	if (pathopt) {
+	if (prefix(pathopt, "builtin")) {
+	if (bcmd)
+	goto builtin_success;
+	continue;
+	} else if (!(act & DO_NOFUNC) &&
+	prefix(pathopt, "func")) {
+	/* handled below */
+	} else {
+	/* ignore unimplemented options */
+	continue;
+	}
+	}
+	/* if rehash, don't redo absolute path names */
+	if (fullname[0] == '/' && idx <= prev) {
+	if (idx < prev)
+	continue;
+	TRACE(("searchexec \"%s\": no change\n", name));
+	goto success;
+	}
+	while (stat(fullname, &statb) < 0) {
+	#ifdef SYSV
+	if (errno == EINTR)
+	continue;
+	#endif
+	if (errno != ENOENT && errno != ENOTDIR)
+	e = errno;
+	goto loop;
+	}
+	e = EACCES; /* if we fail, this will be the error */
+	if (!S_ISREG(statb.st_mode))
+	continue;
+	if (pathopt) { /* this is a %func directory */
+	stalloc(strlen(fullname) + 1);
+	readcmdfile(fullname);
+	cmdp = cmdlookup(name, 0);
+	if (cmdp == NULL \|\| cmdp->cmdtype != CMDFUNCTION)
+	ash_msg_and_raise_error("%s not defined in %s", name, fullname);
+	stunalloc(fullname);
+	goto success;
+	}
+	TRACE(("searchexec \"%s\" returns \"%s\"\n", name, fullname));
+	if (!updatetbl) {
+	entry->cmdtype = CMDNORMAL;
+	entry->u.index = idx;
+	return;
+	}
+	INT_OFF;
+	cmdp = cmdlookup(name, 1);
+	cmdp->cmdtype = CMDNORMAL;
+	cmdp->param.index = idx;
+	INT_ON;
+	goto success;
	}

-	if (!*start)
-	return;
-
-	add:
-	sp = stalloc(sizeof(*sp));
-	sp->text = start;
-	*arglist->lastp = sp;
-	arglist->lastp = &sp->next;
-	}
-
-	static void
-	ifsfree(void)
-	{
-	struct ifsregion *p;
+	/* We failed. If there was an entry for this command, delete it */
+	if (cmdp && updatetbl)
+	delete_cmd_entry();
+	if (act & DO_ERR)
+	ash_msg("%s: %s", name, errmsg(e, "not found"));
+	entry->cmdtype = CMDUNKNOWN;
+	return;

+	builtin_success:
+	if (!updatetbl) {
+	entry->cmdtype = CMDBUILTIN;
+	entry->u.cmd = bcmd;
+	return;
+	}
	INT_OFF;
-	p = ifsfirst.next;
-	do {
-	struct ifsregion *ifsp;
-	ifsp = p->next;
-	free(p);
-	p = ifsp;
-	} while (p);
-	ifslastp = NULL;
-	ifsfirst.next = NULL;
+	cmdp = cmdlookup(name, 1);
+	cmdp->cmdtype = CMDBUILTIN;
+	cmdp->param.cmd = bcmd;
	INT_ON;
+	success:
+	cmdp->rehash = 0;
+	entry->cmdtype = cmdp->cmdtype;
+	entry->u = cmdp->param;
	}

-	static void expmeta(char , char );
-	static struct strlist expsort(struct strlist );
-	static struct strlist msort(struct strlist , int);
-
-	static char *expdir;
-
-
-	static void
-	expandmeta(struct strlist *str, int flag)
+	/*
+	* Search the table of builtin commands.
+	*/
+	static struct builtincmd *
+	find_builtin(const char *name)
	{
-	static const char metachars[] = {
-	'*', '?', '[', 0
-	};
-	/* TODO - EXP_REDIR */
-
-	while (str) {
-	struct strlist **savelastp;
-	struct strlist *sp;
-	char *p;
-
-	if (fflag)
-	goto nometa;
-	if (!strpbrk(str->text, metachars))
-	goto nometa;
-	savelastp = exparg.lastp;
-
-	INT_OFF;
-	p = preglob(str->text, 0, RMESCAPE_ALLOC \| RMESCAPE_HEAP);
-	{
-	int i = strlen(str->text);
-	expdir = ckmalloc(i < 2048 ? 2048 : i); /* XXX */
-	}
+	struct builtincmd *bp;

-	expmeta(expdir, p);
-	free(expdir);
-	if (p != str->text)
-	free(p);
-	INT_ON;
-	if (exparg.lastp == savelastp) {
-	/*
-	* no matches
-	*/
-	nometa:
-	*exparg.lastp = str;
-	rmescapes(str->text);
-	exparg.lastp = &str->next;
-	} else {
-	*exparg.lastp = NULL;
-	savelastp = sp = expsort(savelastp);
-	while (sp->next != NULL)
-	sp = sp->next;
-	exparg.lastp = &sp->next;
-	}
-	str = str->next;
-	}
+	bp = bsearch(
+	name, builtintab, NUMBUILTINS, sizeof(builtintab[0]),
+	pstrcmp
+	);
+	return bp;
	}

-
	/*
-	* Add a file name to the list.
+	* Called when a cd is done. Marks all commands so the next time they
+	* are executed they will be rehashed.
	*/
	static void
-	addfname(const char *name)
+	hashcd(void)
	{
-	struct strlist *sp;
+	struct tblentry **pp;
+	struct tblentry *cmdp;

-	sp = stalloc(sizeof(*sp));
-	sp->text = ststrdup(name);
-	*exparg.lastp = sp;
-	exparg.lastp = &sp->next;
+	for (pp = cmdtable; pp < &cmdtable[CMDTABLESIZE]; pp++) {
+	for (cmdp = *pp; cmdp; cmdp = cmdp->next) {
+	if (cmdp->cmdtype == CMDNORMAL \|\| (
+	cmdp->cmdtype == CMDBUILTIN &&
+	!(IS_BUILTIN_REGULAR(cmdp->param.cmd)) &&
+	builtinloc > 0
+	))
+	cmdp->rehash = 1;
+	}
+	}
	}

-
	/*
-	* Do metacharacter (i.e. *, ?, [...]) expansion.
+	* Fix command hash table when PATH changed.
+	* Called before PATH is changed. The argument is the new value of PATH;
+	* pathval() still returns the old value at this point.
+	* Called with interrupts off.
	*/
	static void
-	expmeta(char enddir, char name)
+	changepath(const char *newval)
	{
-	char *p;
-	const char *cp;
-	char *start;
-	char *endname;
-	int metaflag;
-	struct stat statb;
-	DIR *dirp;
-	struct dirent *dp;
-	int atend;
-	int matchdot;
+	const char old, new;
+	int idx;
+	int firstchange;
+	int idx_bltin;

-	metaflag = 0;
-	start = name;
-	for (p = name; *p; p++) {
-	if (p == '' \|\| *p == '?')
-	metaflag = 1;
-	else if (*p == '[') {
-	char *q = p + 1;
-	if (*q == '!')
-	q++;
-	for (;;) {
-	if (*q == '\\')
-	q++;
-	if (q == '/' \|\| q == '\0')
-	break;
-	if (*++q == ']') {
-	metaflag = 1;
-	break;
-	}
-	}
-	} else if (*p == '\\')
-	p++;
-	else if (*p == '/') {
-	if (metaflag)
-	goto out;
-	start = p + 1;
-	}
-	}
-	out:
-	if (metaflag == 0) { /* we've reached the end of the file name */
-	if (enddir != expdir)
-	metaflag++;
-	p = name;
-	do {
-	if (*p == '\\')
-	p++;
-	enddir++ = p;
-	} while (*p++);
-	if (metaflag == 0 \|\| lstat(expdir, &statb) >= 0)
-	addfname(expdir);
-	return;
-	}
-	endname = p;
-	if (name < start) {
-	p = name;
-	do {
-	if (*p == '\\')
-	p++;
-	enddir++ = p++;
-	} while (p < start);
-	}
-	if (enddir == expdir) {
-	cp = ".";
-	} else if (enddir == expdir + 1 && *expdir == '/') {
-	cp = "/";
-	} else {
-	cp = expdir;
-	enddir[-1] = '\0';
-	}
-	dirp = opendir(cp);
-	if (dirp == NULL)
-	return;
-	if (enddir != expdir)
-	enddir[-1] = '/';
-	if (*endname == 0) {
-	atend = 1;
-	} else {
-	atend = 0;
-	*endname++ = '\0';
-	}
-	matchdot = 0;
-	p = start;
-	if (*p == '\\')
-	p++;
-	if (*p == '.')
-	matchdot++;
-	while (! intpending && (dp = readdir(dirp)) != NULL) {
-	if (dp->d_name[0] == '.' && ! matchdot)
-	continue;
-	if (pmatch(start, dp->d_name)) {
-	if (atend) {
-	strcpy(enddir, dp->d_name);
-	addfname(expdir);
-	} else {
-	for (p = enddir, cp = dp->d_name; (p++ = cp++) != '\0';)
-	continue;
-	p[-1] = '/';
-	expmeta(p, endname);
-	}
+	old = pathval();
+	new = newval;
+	firstchange = 9999; /* assume no change */
+	idx = 0;
+	idx_bltin = -1;
+	for (;;) {
+	if (old != new) {
+	firstchange = idx;
+	if ((old == '\0' && new == ':')
+	\|\| (old == ':' && new == '\0'))
+	firstchange++;
+	old = new; /* ignore subsequent differences */
+	}
+	if (*new == '\0')
+	break;
+	if (*new == '%' && idx_bltin < 0 && prefix(new + 1, "builtin"))
+	idx_bltin = idx;
+	if (*new == ':') {
+	idx++;
	}
+	new++, old++;
	}
-	closedir(dirp);
-	if (! atend)
-	endname[-1] = '/';
+	if (builtinloc < 0 && idx_bltin >= 0)
+	builtinloc = idx_bltin; /* zap builtins */
+	if (builtinloc >= 0 && idx_bltin < 0)
+	firstchange = 0;
+	clearcmdentry(firstchange);
+	builtinloc = idx_bltin;
	}


	/*
-	* Sort the results of file name expansion. It calculates the number of
-	* strings to sort and then calls msort (short for merge sort) to do the
-	* work.
+	* Make a copy of a parse tree.
	*/
-	static struct strlist *
-	expsort(struct strlist *str)
+	static struct funcnode *
+	copyfunc(union node *n)
	{
-	int len;
-	struct strlist *sp;
+	struct funcnode *f;
+	size_t blocksize;

-	len = 0;
-	for (sp = str; sp; sp = sp->next)
-	len++;
-	return msort(str, len);
+	funcblocksize = offsetof(struct funcnode, n);
+	funcstringsize = 0;
+	calcsize(n);
+	blocksize = funcblocksize;
+	f = ckmalloc(blocksize + funcstringsize);
+	funcblock = (char *) f + offsetof(struct funcnode, n);
+	funcstring = (char *) f + blocksize;
+	copynode(n);
+	f->count = 0;
+	return f;
	}

-
-	static struct strlist *
-	msort(struct strlist *list, int len)
+	/*
+	* Define a shell function.
+	*/
+	static void
+	defun(char name, union node func)
	{
-	struct strlist p, q = NULL;
-	struct strlist **lpp;
-	int half;
-	int n;
+	struct cmdentry entry;

-	if (len <= 1)
-	return list;
-	half = len >> 1;
-	p = list;
-	for (n = half; --n >= 0; ) {
-	q = p;
-	p = p->next;
-	}
-	q->next = NULL; /* terminate first half of list */
-	q = msort(list, half); /* sort first half of list */
-	p = msort(p, len - half); /* sort second half */
-	lpp = &list;
-	for (;;) {
-	#if ENABLE_LOCALE_SUPPORT
-	if (strcoll(p->text, q->text) < 0)
-	#else
-	if (strcmp(p->text, q->text) < 0)
-	#endif
-	{
-	*lpp = p;
-	lpp = &p->next;
-	p = *lpp;
-	if (p == NULL) {
-	*lpp = q;
-	break;
-	}
-	} else {
-	*lpp = q;
-	lpp = &q->next;
-	q = *lpp;
-	if (q == NULL) {
-	*lpp = p;
-	break;
-	}
-	}
-	}
-	return list;
+	INT_OFF;
+	entry.cmdtype = CMDFUNCTION;
+	entry.u.func = copyfunc(func);
+	addcmdentry(name, &entry);
+	INT_ON;
	}

-
	/*
-	* Returns true if the pattern matches the string.
+	* Delete a function if it exists.
	*/
-	static int patmatch(char pattern, const char string)
+	static void
+	unsetfunc(const char *name)
	{
-	return pmatch(preglob(pattern, 0, 0), string);
+	struct tblentry *cmdp;
+
+	cmdp = cmdlookup(name, 0);
+	if (cmdp!= NULL && cmdp->cmdtype == CMDFUNCTION)
+	delete_cmd_entry();
	}


	/*
-	* Remove any CTLESC characters from a string.
+	* Locate and print what a word is...
	*/
-	static char *
-	_rmescapes(char *str, int flag)
+	#if ENABLE_ASH_CMDCMD
+	static int
+	describe_command(char *command, int describe_command_verbose)
+	#else
+	#define describe_command_verbose 1
+	static int
+	describe_command(char *command)
+	#endif
	{
-	char p, q, *r;
-	static const char qchars[] = { CTLESC, CTLQUOTEMARK, 0 };
-	unsigned inquotes;
-	int notescaped;
-	int globbing;
+	struct cmdentry entry;
+	struct tblentry *cmdp;
+	#if ENABLE_ASH_ALIAS
+	const struct alias *ap;
+	#endif
+	const char *path = pathval();

-	p = strpbrk(str, qchars);
-	if (!p) {
-	return str;
+	if (describe_command_verbose) {
+	out1str(command);
	}
-	q = p;
-	r = str;
-	if (flag & RMESCAPE_ALLOC) {
-	size_t len = p - str;
-	size_t fulllen = len + strlen(p) + 1;

-	if (flag & RMESCAPE_GROW) {
-	r = makestrspace(fulllen, expdest);
-	} else if (flag & RMESCAPE_HEAP) {
-	r = ckmalloc(fulllen);
+	/* First look at the keywords */
+	if (findkwd(command)) {
+	out1str(describe_command_verbose ? " is a shell keyword" : command);
+	goto out;
+	}
+
+	#if ENABLE_ASH_ALIAS
+	/* Then look at the aliases */
+	ap = lookupalias(command, 0);
+	if (ap != NULL) {
+	if (describe_command_verbose) {
+	out1fmt(" is an alias for %s", ap->val);
	} else {
-	r = stalloc(fulllen);
-	}
-	q = r;
-	if (len > 0) {
-	q = memcpy(q, str, len) + len;
+	out1str("alias ");
+	printalias(ap);
+	return 0;
	}
+	goto out;
	}
-	inquotes = (flag & RMESCAPE_QUOTED) ^ RMESCAPE_QUOTED;
-	globbing = flag & RMESCAPE_GLOB;
-	notescaped = globbing;
-	while (*p) {
-	if (*p == CTLQUOTEMARK) {
-	inquotes = ~inquotes;
-	p++;
-	notescaped = globbing;
-	continue;
-	}
-	if (*p == '\\') {
-	/* naked back slash */
-	notescaped = 0;
-	goto copy;
+	#endif
+	/* Then check if it is a tracked alias */
+	cmdp = cmdlookup(command, 0);
+	if (cmdp != NULL) {
+	entry.cmdtype = cmdp->cmdtype;
+	entry.u = cmdp->param;
+	} else {
+	/* Finally use brute force */
+	find_command(command, &entry, DO_ABS, path);
+	}
+
+	switch (entry.cmdtype) {
+	case CMDNORMAL: {
+	int j = entry.u.index;
+	char *p;
+	if (j == -1) {
+	p = command;
+	} else {
+	do {
+	p = padvance(&path, command);
+	stunalloc(p);
+	} while (--j >= 0);
	}
-	if (*p == CTLESC) {
-	p++;
-	if (notescaped && inquotes && *p != '/') {
-	*q++ = '\\';
-	}
+	if (describe_command_verbose) {
+	out1fmt(" is%s %s",
+	(cmdp ? " a tracked alias for" : nullstr), p
+	);
+	} else {
+	out1str(p);
	}
-	notescaped = globbing;
-	copy:
-	q++ = p++;
-	}
-	*q = '\0';
-	if (flag & RMESCAPE_GROW) {
-	expdest = r;
-	STADJUST(q - r + 1, expdest);
+	break;
	}
-	return r;
-	}

+	case CMDFUNCTION:
+	if (describe_command_verbose) {
+	out1str(" is a shell function");
+	} else {
+	out1str(command);
+	}
+	break;

-	/*
-	* See if a pattern matches in a case statement.
-	*/
-	static int
-	casematch(union node pattern, char val)
-	{
-	struct stackmark smark;
-	int result;
-
-	setstackmark(&smark);
-	argbackq = pattern->narg.backquote;
-	STARTSTACKSTR(expdest);
-	ifslastp = NULL;
-	argstr(pattern->narg.text, EXP_TILDE \| EXP_CASE);
-	STACKSTRNUL(expdest);
-	result = patmatch(stackblock(), val);
-	popstackmark(&smark);
-	return result;
-	}
+	case CMDBUILTIN:
+	if (describe_command_verbose) {
+	out1fmt(" is a %sshell builtin",
+	IS_BUILTIN_SPECIAL(entry.u.cmd) ?
+	"special " : nullstr
+	);
+	} else {
+	out1str(command);
+	}
+	break;

+	default:
+	if (describe_command_verbose) {
+	out1str(": not found\n");
+	}
+	return 127;
+	}
+	out:
+	outstr("\n", stdout);
+	return 0;
+	}

-	/*
-	* Our own itoa().
-	*/
	static int
-	cvtnum(arith_t num)
+	typecmd(int argc, char **argv)
	{
-	int len;
+	int i;
+	int err = 0;

-	expdest = makestrspace(32, expdest);
-	#if ENABLE_ASH_MATH_SUPPORT_64
-	len = fmtstr(expdest, 32, "%lld", (long long) num);
+	for (i = 1; i < argc; i++) {
+	#if ENABLE_ASH_CMDCMD
+	err \|= describe_command(argv[i], 1);
	#else
-	len = fmtstr(expdest, 32, "%ld", num);
+	err \|= describe_command(argv[i]);
	#endif
-	STADJUST(len, expdest);
-	return len;
+	}
+	return err;
	}

-	static void varunset(const char , const char , const char *, int) ATTRIBUTE_NORETURN;
-	static void
-	varunset(const char end, const char var, const char *umsg, int varflags)
+	#if ENABLE_ASH_CMDCMD
+	static int
+	commandcmd(int argc, char **argv)
	{
-	const char *msg;
-	const char *tail;
+	int c;
+	enum {
+	VERIFY_BRIEF = 1,
+	VERIFY_VERBOSE = 2,
+	} verify = 0;

-	tail = nullstr;
-	msg = "parameter not set";
-	if (umsg) {
-	if (*end == CTLENDVAR) {
-	if (varflags & VSNUL)
-	tail = " or null";
-	} else
-	msg = umsg;
-	}
-	ash_msg_and_raise_error("%.*s: %s%s", end - var - 1, var, msg, tail);
+	while ((c = nextopt("pvV")) != '\0')
+	if (c == 'V')
+	verify \|= VERIFY_VERBOSE;
+	else if (c == 'v')
+	verify \|= VERIFY_BRIEF;
+	#if DEBUG
+	else if (c != 'p')
+	abort();
+	#endif
+	if (verify)
+	return describe_command(*argptr, verify - VERIFY_BRIEF);
+
+	return 0;
	}
+	#endif


	/* ============ input.c
@@ -6901,7 +6844,6 @@ preadbuffer(void)
	return SC2INT(*parsenextc++);
	}

-
	#define pgetc_as_macro() (--parsenleft >= 0? SC2INT(*parsenextc++) : preadbuffer())

	#if ENABLE_ASH_OPTIMIZE_FOR_SIZE
@@ -7142,7 +7084,7 @@ setinputstring(char *string)
	}


-	/* jobs.c */
+	/* ============ jobs.c */

	/* mode flags for set_curjob */
	#define CUR_DELETE 2
@@ -8500,12 +8442,11 @@ stoppedjobs(void)
	}


-	#if ENABLE_ASH_MAIL
-	/* mail.c */
-
-	/*
-	* Routines to check for mail. (Perhaps make part of main.c?)
+	/* ============ mail.c
+	*
+	* Routines to check for mail.
	*/
+	#if ENABLE_ASH_MAIL

	#define MAXMBOXES 10

@@ -8514,7 +8455,6 @@ static time_t mailtime[MAXMBOXES];
	/* Set if MAIL or MAILPATH is changed. */
	static int mail_var_path_changed;

-
	/*
	* Print appropriate message(s) if mail has arrived.
	* If mail_var_path_changed is set,
@@ -8561,15 +8501,16 @@ chkmail(void)
	popstackmark(&smark);
	}

-
	static void
	changemail(const char *val)
	{
	mail_var_path_changed++;
	}
-
	#endif /* ASH_MAIL */

+
+	/* ============ ??? */
+
	/*
	* Take commands from a file. To be compatible we should do a path
	* search for the file, which is necessary to find sub-commands.
@@ -8679,7 +8620,6 @@ calcsize(union node *n)
	};
	}

-
	static void
	sizenodelist(struct nodelist *lp)
	{
@@ -8690,7 +8630,6 @@ sizenodelist(struct nodelist *lp)
	}
	}

-
	static union node *
	copynode(union node *n)
	{
@@ -8780,7 +8719,6 @@ copynode(union node *n)
	return new;
	}

-
	static struct nodelist *
	copynodelist(struct nodelist *lp)
	{
@@ -8799,7 +8737,6 @@ copynodelist(struct nodelist *lp)
	return start;
	}

-
	static char *
	nodeckstrdup(char *s)
	{
@@ -8810,6 +8747,37 @@ nodeckstrdup(char *s)
	return rtn;
	}

+	/*
+	* Controls whether the shell is interactive or not.
+	*/
+	static void
+	setinteractive(int on)
+	{
+	static int is_interactive;
+
+	if (++on == is_interactive)
+	return;
+	is_interactive = on;
+	setsignal(SIGINT);
+	setsignal(SIGQUIT);
+	setsignal(SIGTERM);
+	#if !ENABLE_FEATURE_SH_EXTRA_QUIET
+	if (is_interactive > 1) {
+	/* Looks like they want an interactive shell */
+	static smallint do_banner;
+
+	if (!do_banner) {
+	out1fmt(
+	"\n\n"
+	"%s Built-in shell (ash)\n"
+	"Enter 'help' for a list of built-in commands."
+	"\n\n",
+	BB_BANNER);
+	do_banner = 1;
+	}
+	}
+	#endif
+	}

	#if ENABLE_FEATURE_EDITING_VI
	#define setvimode(on) do { \
@@ -8867,7 +8835,6 @@ setoption(int flag, int val)
	/* NOTREACHED */
	}

-
	/*
	* Process shell options. The global variable argptr contains a pointer
	* to the argument list; we advance it past the options.
@@ -8921,7 +8888,6 @@ options(int cmdline)
	}
	}

-
	/*
	* Set the shell parameters.
	*/
@@ -8948,7 +8914,6 @@ setparam(char **argv)
	#endif
	}

-
	/*
	* Free the list of positional parameters.
	*/
@@ -8964,7 +8929,6 @@ freeparam(volatile struct shparam *param)
	}
	}

-
	/*
	* The shift builtin command.
	*/
@@ -8995,7 +8959,6 @@ shiftcmd(int argc, char **argv)
	return 0;
	}

-
	/*
	* POSIX requires that 'set' (but not export or readonly) output the
	* variables in lexicographic order - by the locale's collating order (sigh).
@@ -9045,7 +9008,6 @@ setcmd(int argc, char **argv)
	return 0;
	}

-
	#if ENABLE_LOCALE_SUPPORT
	static void
	change_lc_all(const char *value)
@@ -9083,7 +9045,6 @@ change_random(const char *value)
	}
	#endif

-
	#if ENABLE_ASH_GETOPTS
	static int
	getopts(char optstr, char optvar, char *optfirst, int param_optind, int *optoff)
@@ -9173,7 +9134,6 @@ getopts(char optstr, char optvar, char *optfirst, int param_optind, int *opt
	return done;
	}

-
	/*
	* The getopts builtin. Shellparam.optnext points to the next argument
	* to be processed. Shellparam.optptr points to the next character to
@@ -10877,7 +10837,7 @@ readcmdfile(char *name)
	}


-	/* redir.c */
+	/* ============ redir.c */

	/*
	* Code for dealing with input/output redirection.
@@ -10948,7 +10908,6 @@ noclobberopen(const char *fname)
	return -1;
	}

-
	/*
	* Handle here documents. Normally we fork off a process to write the
	* data to a pipe. If the document is short, we can stuff the data in
@@ -11139,7 +11098,6 @@ redirect(union node *redir, int flags)
	preverrout_fd = sv->renamed[2];
	}

-
	/*
	* Undo the effects of the last redirection.
	*/
@@ -11186,7 +11144,6 @@ clearredir(int drop)
	}
	}

-
	/*
	* Copy a file descriptor to be >= to. Returns -1
	* if the source file descriptor is closed, EMPTY if there are no unused
@@ -11228,7 +11185,7 @@ redirectsafe(union node *redir, int flags)
	}


-	/* trap.c */
+	/* ============ trap.c */

	/*
	* The trap builtin.
@@ -11280,7 +11237,6 @@ trapcmd(int argc, char **argv)
	return 0;
	}

-
	/*
	* Clear traps on a fork.
	*/
@@ -11301,7 +11257,6 @@ clear_traps(void)
	}
	}

-
	/*
	* Set the signal handler for the specified signal. The routine figures
	* out what it should be set to.
@@ -11389,7 +11344,6 @@ setsignal(int signo)
	sigaction(signo, &act, 0);
	}

-
	/*
	* Called to execute a trap. Perhaps we should avoid entering new trap
	* handlers while we are executing a trap handler.
@@ -11424,37 +11378,8 @@ dotrap(void)
	return skip;
	}

-	/*
-	* Controls whether the shell is interactive or not.
-	*/
-	static void
-	setinteractive(int on)
-	{
-	static int is_interactive;
-
-	if (++on == is_interactive)
-	return;
-	is_interactive = on;
-	setsignal(SIGINT);
-	setsignal(SIGQUIT);
-	setsignal(SIGTERM);
-	#if !ENABLE_FEATURE_SH_EXTRA_QUIET
-	if (is_interactive > 1) {
-	/* Looks like they want an interactive shell */
-	static smallint do_banner;

-	if (!do_banner) {
-	out1fmt(
-	"\n\n"
-	"%s Built-in shell (ash)\n"
-	"Enter 'help' for a list of built-in commands."
-	"\n\n",
-	BB_BANNER);
-	do_banner = 1;
-	}
-	}
-	#endif
-	}
+	/* ============ Builtins */

	#if !ENABLE_FEATURE_SH_EXTRA_QUIET
	/*
@@ -11488,41 +11413,6 @@ helpcmd(int argc, char **argv)
	}
	#endif /* FEATURE_SH_EXTRA_QUIET */

-	/*
-	* Called to exit the shell.
-	*/
-	static void
-	exitshell(void)
-	{
-	struct jmploc loc;
-	char *p;
-	int status;
-
-	status = exitstatus;
-	TRACE(("pid %d, exitshell(%d)\n", getpid(), status));
-	if (setjmp(loc.loc)) {
-	if (exception == EXEXIT)
-	/* dash bug: it just does _exit(exitstatus) here
-	* but we have to do setjobctl(0) first!
-	* (bug is still not fixed in dash-0.5.3 - if you run dash
-	* under Midnight Commander, on exit from dash MC is backgrounded) */
-	status = exitstatus;
-	goto out;
-	}
-	exception_handler = &loc;
-	p = trap[0];
-	if (p) {
-	trap[0] = NULL;
-	evalstring(p, 0);
-	}
-	flush_stdout_stderr();
-	out:
-	setjobctl(0);
-	_exit(status);
-	/* NOTREACHED */
-	}
-
-
	/*
	* The export and readonly commands.
	*/
@@ -11559,7 +11449,6 @@ exportcmd(int argc, char **argv)
	return 0;
	}

-
	/*
	* Make a variable a local variable. When a variable is made local, it's
	* value and flags are saved in a localvar structure. The saved values
@@ -11607,7 +11496,6 @@ mklocal(char *name)
	INT_ON;
	}

-
	/*
	* The "local" command.
	*/
@@ -11623,7 +11511,6 @@ localcmd(int argc, char **argv)
	return 0;
	}

-
	/*
	* The unset builtin command. We unset the function before we unset the
	* variable to allow a function to be unset when there is a readonly variable
@@ -11713,7 +11600,6 @@ dash_arith(const char *s)
	return result;
	}

-
	/*
	* The let builtin. partial stolen from GNU Bash, the Bourne Again SHell.
	* Copyright (C) 1987, 1989, 1991 Free Software Foundation, Inc.
@@ -11737,9 +11623,9 @@ letcmd(int argc, char **argv)
	}
	#endif /* ASH_MATH_SUPPORT */

-	/* miscbltin.c */

-	/*
+	/* ============ miscbltin.c
+	*
	* Miscellaneous builtins.
	*/

@@ -11749,7 +11635,6 @@ letcmd(int argc, char **argv)
	typedef enum __rlimit_resource rlim_t;
	#endif

-
	/*
	* The read builtin. The -e option causes backslashes to escape the
	* following character.
@@ -11938,7 +11823,6 @@ readcmd(int argc, char **argv)
	return status;
	}

-
	static int
	umaskcmd(int argc, char **argv)
	{
@@ -12190,6 +12074,8 @@ ulimitcmd(int argc, char **argv)
	}


+	/* ============ Math support */
+
	#if ENABLE_ASH_MATH_SUPPORT

	/* Copyright (c) 2001 Aaron Lehmann <[email protected]>
@@ -12645,7 +12531,6 @@ static const char op_tokens[] = {
	/* ptr to ")" */
	#define endexpression &op_tokens[sizeof(op_tokens)-7]

-
	static arith_t
	arith(const char expr, int perrcode)
	{
@@ -12837,14 +12722,43 @@ arith(const char expr, int perrcode)
	#endif /* ASH_MATH_SUPPORT */


-	/* ============ main() and helpers
-	*
-	* Main routine. We initialize things, parse the arguments, execute
-	* profiles if we're a login shell, and then call cmdloop to execute
-	* commands. The setjmp call sets up the location to jump to when an
-	* exception occurs. When an exception occurs the variable "state"
-	* is used to figure out how far we had gotten.
+	/* ============ main() and helpers */
+
+	/*
+	* Called to exit the shell.
	*/
+	static void exitshell(void) ATTRIBUTE_NORETURN;
+	static void
+	exitshell(void)
+	{
+	struct jmploc loc;
+	char *p;
+	int status;
+
+	status = exitstatus;
+	TRACE(("pid %d, exitshell(%d)\n", getpid(), status));
+	if (setjmp(loc.loc)) {
+	if (exception == EXEXIT)
+	/* dash bug: it just does _exit(exitstatus) here
+	* but we have to do setjobctl(0) first!
+	* (bug is still not fixed in dash-0.5.3 - if you run dash
+	* under Midnight Commander, on exit from dash MC is backgrounded) */
+	status = exitstatus;
+	goto out;
+	}
+	exception_handler = &loc;
+	p = trap[0];
+	if (p) {
+	trap[0] = NULL;
+	evalstring(p, 0);
+	}
+	flush_stdout_stderr();
+	out:
+	setjobctl(0);
+	_exit(status);
+	/* NOTREACHED */
+	}
+
	static void
	init(void)
	{
@@ -12981,6 +12895,13 @@ static short profile_buf[16384];
	extern int etext();
	#endif

+	/*
+	* Main routine. We initialize things, parse the arguments, execute
+	* profiles if we're a login shell, and then call cmdloop to execute
+	* commands. The setjmp call sets up the location to jump to when an
+	* exception occurs. When an exception occurs the variable "state"
+	* is used to figure out how far we had gotten.
+	*/
	int ash_main(int argc, char **argv);
	int ash_main(int argc, char **argv)
	{