xref: /csrg-svn/bin/sh/expand.c (revision 69469)
147116Sbostic /*-
260698Sbostic  * Copyright (c) 1991, 1993
360698Sbostic  *	The Regents of the University of California.  All rights reserved.
447116Sbostic  *
547116Sbostic  * This code is derived from software contributed to Berkeley by
647116Sbostic  * Kenneth Almquist.
747116Sbostic  *
847116Sbostic  * %sccs.include.redist.c%
947116Sbostic  */
1047116Sbostic 
1147116Sbostic #ifndef lint
12*69469Schristos static char sccsid[] = "@(#)expand.c	8.5 (Berkeley) 05/14/95";
1347116Sbostic #endif /* not lint */
1447116Sbostic 
1569272Schristos #include <sys/types.h>
1669272Schristos #include <sys/time.h>
1769272Schristos #include <sys/stat.h>
1869272Schristos #include <errno.h>
1969272Schristos #include <dirent.h>
2069272Schristos #include <unistd.h>
2169272Schristos #include <pwd.h>
2269272Schristos #include <stdlib.h>
2369272Schristos 
2447116Sbostic /*
2547116Sbostic  * Routines to expand arguments to commands.  We have to deal with
2647116Sbostic  * backquotes, shell variables, and file metacharacters.
2747116Sbostic  */
2847116Sbostic 
2947116Sbostic #include "shell.h"
3047116Sbostic #include "main.h"
3147116Sbostic #include "nodes.h"
3247116Sbostic #include "eval.h"
3347116Sbostic #include "expand.h"
3447116Sbostic #include "syntax.h"
3547116Sbostic #include "parser.h"
3647116Sbostic #include "jobs.h"
3747116Sbostic #include "options.h"
3847116Sbostic #include "var.h"
3947116Sbostic #include "input.h"
4047116Sbostic #include "output.h"
4147116Sbostic #include "memalloc.h"
4247116Sbostic #include "error.h"
4347116Sbostic #include "mystring.h"
4469272Schristos #include "arith.h"
4569272Schristos #include "show.h"
4647116Sbostic 
4747116Sbostic /*
4847116Sbostic  * Structure specifying which parts of the string should be searched
4947116Sbostic  * for IFS characters.
5047116Sbostic  */
5147116Sbostic 
5247116Sbostic struct ifsregion {
5347116Sbostic 	struct ifsregion *next;	/* next region in list */
5447116Sbostic 	int begoff;		/* offset of start of region */
5547116Sbostic 	int endoff;		/* offset of end of region */
5647116Sbostic 	int nulonly;		/* search for nul bytes only */
5747116Sbostic };
5847116Sbostic 
5947116Sbostic 
6047116Sbostic char *expdest;			/* output of current string */
6147116Sbostic struct nodelist *argbackq;	/* list of back quote expressions */
6247116Sbostic struct ifsregion ifsfirst;	/* first struct in list of ifs regions */
6347116Sbostic struct ifsregion *ifslastp;	/* last struct in list */
6447116Sbostic struct arglist exparg;		/* holds expanded arg list */
6547116Sbostic 
6669272Schristos STATIC void argstr __P((char *, int));
6769272Schristos STATIC char *exptilde __P((char *, int));
6869272Schristos STATIC void expbackq __P((union node *, int, int));
6969272Schristos STATIC int subevalvar __P((char *, char *, int, int, int));
7069272Schristos STATIC char *evalvar __P((char *, int));
7169272Schristos STATIC int varisset __P((int));
7269272Schristos STATIC void varvalue __P((int, int, int));
7369272Schristos STATIC void recordregion __P((int, int, int));
7469272Schristos STATIC void ifsbreakup __P((char *, struct arglist *));
7569272Schristos STATIC void expandmeta __P((struct strlist *, int));
7669272Schristos STATIC void expmeta __P((char *, char *));
7769272Schristos STATIC void addfname __P((char *));
7869272Schristos STATIC struct strlist *expsort __P((struct strlist *));
7969272Schristos STATIC struct strlist *msort __P((struct strlist *, int));
8069272Schristos STATIC int pmatch __P((char *, char *));
8169272Schristos STATIC char *cvtnum __P((int, char *));
8247116Sbostic 
8347116Sbostic /*
8447116Sbostic  * Expand shell variables and backquotes inside a here document.
8547116Sbostic  */
8647116Sbostic 
8747116Sbostic void
expandhere(arg,fd)8847116Sbostic expandhere(arg, fd)
8947116Sbostic 	union node *arg;	/* the document */
9047116Sbostic 	int fd;			/* where to write the expanded version */
9147116Sbostic 	{
9247116Sbostic 	herefd = fd;
9347116Sbostic 	expandarg(arg, (struct arglist *)NULL, 0);
9447116Sbostic 	xwrite(fd, stackblock(), expdest - stackblock());
9547116Sbostic }
9647116Sbostic 
9747116Sbostic 
9847116Sbostic /*
9947116Sbostic  * Perform variable substitution and command substitution on an argument,
10055787Smarc  * placing the resulting list of arguments in arglist.  If EXP_FULL is true,
10147116Sbostic  * perform splitting and file name expansion.  When arglist is NULL, perform
10247116Sbostic  * here document expansion.
10347116Sbostic  */
10447116Sbostic 
10547116Sbostic void
expandarg(arg,arglist,flag)10653299Smarc expandarg(arg, arglist, flag)
10747116Sbostic 	union node *arg;
10847116Sbostic 	struct arglist *arglist;
10969272Schristos 	int flag;
11069272Schristos {
11147116Sbostic 	struct strlist *sp;
11247116Sbostic 	char *p;
11347116Sbostic 
11447116Sbostic 	argbackq = arg->narg.backquote;
11547116Sbostic 	STARTSTACKSTR(expdest);
11647116Sbostic 	ifsfirst.next = NULL;
11747116Sbostic 	ifslastp = NULL;
11853299Smarc 	argstr(arg->narg.text, flag);
11954315Smarc 	if (arglist == NULL) {
12047116Sbostic 		return;			/* here document expanded */
12154315Smarc 	}
12247116Sbostic 	STPUTC('\0', expdest);
12347116Sbostic 	p = grabstackstr(expdest);
12447116Sbostic 	exparg.lastp = &exparg.list;
12553299Smarc 	/*
12653299Smarc 	 * TODO - EXP_REDIR
12753299Smarc 	 */
12853299Smarc 	if (flag & EXP_FULL) {
12947116Sbostic 		ifsbreakup(p, &exparg);
13047116Sbostic 		*exparg.lastp = NULL;
13147116Sbostic 		exparg.lastp = &exparg.list;
13253299Smarc 		expandmeta(exparg.list, flag);
13347116Sbostic 	} else {
13454315Smarc 		if (flag & EXP_REDIR) /*XXX - for now, just remove escapes */
13554315Smarc 			rmescapes(p);
13647116Sbostic 		sp = (struct strlist *)stalloc(sizeof (struct strlist));
13747116Sbostic 		sp->text = p;
13847116Sbostic 		*exparg.lastp = sp;
13947116Sbostic 		exparg.lastp = &sp->next;
14047116Sbostic 	}
14147116Sbostic 	while (ifsfirst.next != NULL) {
14247116Sbostic 		struct ifsregion *ifsp;
14347116Sbostic 		INTOFF;
14447116Sbostic 		ifsp = ifsfirst.next->next;
14547116Sbostic 		ckfree(ifsfirst.next);
14647116Sbostic 		ifsfirst.next = ifsp;
14747116Sbostic 		INTON;
14847116Sbostic 	}
14947116Sbostic 	*exparg.lastp = NULL;
15047116Sbostic 	if (exparg.list) {
15147116Sbostic 		*arglist->lastp = exparg.list;
15247116Sbostic 		arglist->lastp = exparg.lastp;
15347116Sbostic 	}
15447116Sbostic }
15547116Sbostic 
15647116Sbostic 
15747116Sbostic 
15847116Sbostic /*
15955787Smarc  * Perform variable and command substitution.  If EXP_FULL is set, output CTLESC
16055787Smarc  * characters to allow for further processing.  Otherwise treat
16147116Sbostic  * $@ like $* since no splitting will be performed.
16247116Sbostic  */
16347116Sbostic 
16447116Sbostic STATIC void
argstr(p,flag)16553299Smarc argstr(p, flag)
16647116Sbostic 	register char *p;
16769272Schristos 	int flag;
16869272Schristos {
16955787Smarc 	register char c;
17055787Smarc 	int quotes = flag & (EXP_FULL | EXP_CASE);	/* do CTLESC */
17155799Smarc 	int firsteq = 1;
17247116Sbostic 
17353299Smarc 	if (*p == '~' && (flag & (EXP_TILDE | EXP_VARTILDE)))
17455787Smarc 		p = exptilde(p, flag);
17547116Sbostic 	for (;;) {
17647116Sbostic 		switch (c = *p++) {
17747116Sbostic 		case '\0':
17853276Smarc 		case CTLENDVAR: /* ??? */
17947116Sbostic 			goto breakloop;
18047116Sbostic 		case CTLESC:
18155787Smarc 			if (quotes)
18247116Sbostic 				STPUTC(c, expdest);
18347116Sbostic 			c = *p++;
18447116Sbostic 			STPUTC(c, expdest);
18547116Sbostic 			break;
18647116Sbostic 		case CTLVAR:
18753299Smarc 			p = evalvar(p, flag);
18847116Sbostic 			break;
18947116Sbostic 		case CTLBACKQ:
19047116Sbostic 		case CTLBACKQ|CTLQUOTE:
19155787Smarc 			expbackq(argbackq->n, c & CTLQUOTE, flag);
19247116Sbostic 			argbackq = argbackq->next;
19347116Sbostic 			break;
19453276Smarc 		case CTLENDARI:
19555787Smarc 			expari(flag);
19653276Smarc 			break;
19753299Smarc 		case ':':
19855799Smarc 		case '=':
19955799Smarc 			/*
20055799Smarc 			 * sort of a hack - expand tildes in variable
20155799Smarc 			 * assignments (after the first '=' and after ':'s).
20255799Smarc 			 */
20354315Smarc 			STPUTC(c, expdest);
20455799Smarc 			if (flag & EXP_VARTILDE && *p == '~') {
20555799Smarc 				if (c == '=') {
20655799Smarc 					if (firsteq)
20755799Smarc 						firsteq = 0;
20855799Smarc 					else
20955799Smarc 						break;
21055799Smarc 				}
21155787Smarc 				p = exptilde(p, flag);
21255799Smarc 			}
21354315Smarc 			break;
21447116Sbostic 		default:
21547116Sbostic 			STPUTC(c, expdest);
21647116Sbostic 		}
21747116Sbostic 	}
21847116Sbostic breakloop:;
21947116Sbostic }
22047116Sbostic 
22153299Smarc STATIC char *
exptilde(p,flag)22255787Smarc exptilde(p, flag)
22353299Smarc 	char *p;
22469272Schristos 	int flag;
22569272Schristos {
22653299Smarc 	char c, *startp = p;
22753299Smarc 	struct passwd *pw;
22853299Smarc 	char *home;
22955787Smarc 	int quotes = flag & (EXP_FULL | EXP_CASE);
23053299Smarc 
23169272Schristos 	while ((c = *p) != '\0') {
23253299Smarc 		switch(c) {
23353299Smarc 		case CTLESC:
23453299Smarc 			return (startp);
23553299Smarc 		case ':':
23655787Smarc 			if (flag & EXP_VARTILDE)
23753299Smarc 				goto done;
23853299Smarc 			break;
23953299Smarc 		case '/':
24053299Smarc 			goto done;
24153299Smarc 		}
24253299Smarc 		p++;
24353299Smarc 	}
24453299Smarc done:
24553299Smarc 	*p = '\0';
24653299Smarc 	if (*(startp+1) == '\0') {
24753299Smarc 		if ((home = lookupvar("HOME")) == NULL)
24853299Smarc 			goto lose;
24953299Smarc 	} else {
25053299Smarc 		if ((pw = getpwnam(startp+1)) == NULL)
25153299Smarc 			goto lose;
25253299Smarc 		home = pw->pw_dir;
25353299Smarc 	}
25453299Smarc 	if (*home == '\0')
25553299Smarc 		goto lose;
25653299Smarc 	*p = c;
25769272Schristos 	while ((c = *home++) != '\0') {
25855787Smarc 		if (quotes && SQSYNTAX[c] == CCTL)
25953299Smarc 			STPUTC(CTLESC, expdest);
26053299Smarc 		STPUTC(c, expdest);
26153299Smarc 	}
26253299Smarc 	return (p);
26353299Smarc lose:
26453299Smarc 	*p = c;
26553299Smarc 	return (startp);
26653299Smarc }
26753299Smarc 
26853299Smarc 
26953276Smarc /*
27053276Smarc  * Expand arithmetic expression.  Backup to start of expression,
27153276Smarc  * evaluate, place result in (backed up) result, adjust string position.
27253276Smarc  */
27355787Smarc void
expari(flag)27455787Smarc expari(flag)
27569272Schristos 	int flag;
27669272Schristos {
27755243Smarc 	char *p, *start;
27853276Smarc 	int result;
27955787Smarc 	int quotes = flag & (EXP_FULL | EXP_CASE);
28047116Sbostic 
28153276Smarc 	/*
28253276Smarc 	 * This routine is slightly over-compilcated for
28353276Smarc 	 * efficiency.  First we make sure there is
28453276Smarc 	 * enough space for the result, which may be bigger
28553276Smarc 	 * than the expression if we add exponentation.  Next we
28653276Smarc 	 * scan backwards looking for the start of arithmetic.  If the
28753276Smarc 	 * next previous character is a CTLESC character, then we
28853276Smarc 	 * have to rescan starting from the beginning since CTLESC
28953276Smarc 	 * characters have to be processed left to right.
29053276Smarc 	 */
29153276Smarc 	CHECKSTRSPACE(8, expdest);
29255243Smarc 	USTPUTC('\0', expdest);
29355243Smarc 	start = stackblock();
29453276Smarc 	p = expdest;
29553276Smarc 	while (*p != CTLARI && p >= start)
29653276Smarc 		--p;
29753276Smarc 	if (*p != CTLARI)
29853276Smarc 		error("missing CTLARI (shouldn't happen)");
29953276Smarc 	if (p > start && *(p-1) == CTLESC)
30053276Smarc 		for (p = start; *p != CTLARI; p++)
30153276Smarc 			if (*p == CTLESC)
30253276Smarc 				p++;
30355787Smarc 	if (quotes)
30455787Smarc 		rmescapes(p+1);
30553276Smarc 	result = arith(p+1);
30653276Smarc 	fmtstr(p, 10, "%d", result);
30753276Smarc 	while (*p++)
30853276Smarc 		;
30953276Smarc 	result = expdest - p + 1;
31053276Smarc 	STADJUST(-result, expdest);
31153276Smarc }
31253276Smarc 
31353276Smarc 
31447116Sbostic /*
31547116Sbostic  * Expand stuff in backwards quotes.
31647116Sbostic  */
31747116Sbostic 
31847116Sbostic STATIC void
expbackq(cmd,quoted,flag)31955787Smarc expbackq(cmd, quoted, flag)
32047116Sbostic 	union node *cmd;
32169272Schristos 	int quoted;
32269272Schristos 	int flag;
32369272Schristos {
32447116Sbostic 	struct backcmd in;
32547116Sbostic 	int i;
32647116Sbostic 	char buf[128];
32747116Sbostic 	char *p;
32847116Sbostic 	char *dest = expdest;
32947116Sbostic 	struct ifsregion saveifs, *savelastp;
33047116Sbostic 	struct nodelist *saveargbackq;
33147116Sbostic 	char lastc;
33247116Sbostic 	int startloc = dest - stackblock();
33347116Sbostic 	char const *syntax = quoted? DQSYNTAX : BASESYNTAX;
33447116Sbostic 	int saveherefd;
33555787Smarc 	int quotes = flag & (EXP_FULL | EXP_CASE);
33647116Sbostic 
33747116Sbostic 	INTOFF;
33847116Sbostic 	saveifs = ifsfirst;
33947116Sbostic 	savelastp = ifslastp;
34047116Sbostic 	saveargbackq = argbackq;
34147116Sbostic 	saveherefd = herefd;
34247116Sbostic 	herefd = -1;
34347116Sbostic 	p = grabstackstr(dest);
34447116Sbostic 	evalbackcmd(cmd, &in);
34547116Sbostic 	ungrabstackstr(p, dest);
34647116Sbostic 	ifsfirst = saveifs;
34747116Sbostic 	ifslastp = savelastp;
34847116Sbostic 	argbackq = saveargbackq;
34947116Sbostic 	herefd = saveherefd;
35047116Sbostic 
35147116Sbostic 	p = in.buf;
35247116Sbostic 	lastc = '\0';
35347116Sbostic 	for (;;) {
35447116Sbostic 		if (--in.nleft < 0) {
35547116Sbostic 			if (in.fd < 0)
35647116Sbostic 				break;
35747116Sbostic 			while ((i = read(in.fd, buf, sizeof buf)) < 0 && errno == EINTR);
35847116Sbostic 			TRACE(("expbackq: read returns %d\n", i));
35947116Sbostic 			if (i <= 0)
36047116Sbostic 				break;
36147116Sbostic 			p = buf;
36247116Sbostic 			in.nleft = i - 1;
36347116Sbostic 		}
36447116Sbostic 		lastc = *p++;
36547116Sbostic 		if (lastc != '\0') {
36655787Smarc 			if (quotes && syntax[lastc] == CCTL)
36747116Sbostic 				STPUTC(CTLESC, dest);
36847116Sbostic 			STPUTC(lastc, dest);
36947116Sbostic 		}
37047116Sbostic 	}
37169272Schristos 
37269272Schristos 	/* Eat all trailing newlines */
37369272Schristos 	for (p--; lastc == '\n'; lastc = *--p)
37447116Sbostic 		STUNPUTC(dest);
37569272Schristos 
37647116Sbostic 	if (in.fd >= 0)
37747116Sbostic 		close(in.fd);
37847116Sbostic 	if (in.buf)
37947116Sbostic 		ckfree(in.buf);
38047116Sbostic 	if (in.jp)
38159176Storek 		exitstatus = waitforjob(in.jp);
38247116Sbostic 	if (quoted == 0)
38347116Sbostic 		recordregion(startloc, dest - stackblock(), 0);
38447116Sbostic 	TRACE(("evalbackq: size=%d: \"%.*s\"\n",
38547116Sbostic 		(dest - stackblock()) - startloc,
38647116Sbostic 		(dest - stackblock()) - startloc,
38747116Sbostic 		stackblock() + startloc));
38847116Sbostic 	expdest = dest;
38947116Sbostic 	INTON;
39047116Sbostic }
39147116Sbostic 
39247116Sbostic 
39347116Sbostic 
39469090Sbostic STATIC int
subevalvar(p,str,subtype,startloc,varflags)39569090Sbostic subevalvar(p, str, subtype, startloc, varflags)
39669090Sbostic 	char *p;
39769090Sbostic 	char *str;
39869090Sbostic 	int subtype;
39969090Sbostic 	int startloc;
40069090Sbostic 	int varflags;
40169090Sbostic {
40269090Sbostic 
40369090Sbostic 	char *startp;
40469090Sbostic 	char *loc;
40569090Sbostic 	int c = 0;
40669090Sbostic 	int saveherefd = herefd;
40769090Sbostic 	struct nodelist *saveargbackq = argbackq;
40869090Sbostic 	herefd = -1;
40969090Sbostic 	argstr(p, 0);
41069090Sbostic 	STACKSTRNUL(expdest);
41169090Sbostic 	herefd = saveherefd;
41269090Sbostic 	argbackq = saveargbackq;
41369090Sbostic 	startp = stackblock() + startloc;
41469090Sbostic 
41569090Sbostic 	switch (subtype) {
41669090Sbostic 	case VSASSIGN:
41769090Sbostic 		setvar(str, startp, 0);
41869090Sbostic 		STADJUST(startp - expdest, expdest);
41969090Sbostic 		varflags &= ~VSNUL;
42069090Sbostic 		if (c != 0)
42169090Sbostic 			*loc = c;
42269090Sbostic 		return 1;
42369090Sbostic 
42469090Sbostic 	case VSQUESTION:
42569090Sbostic 		if (*p != CTLENDVAR) {
42669090Sbostic 			outfmt(&errout, "%s\n", startp);
42769090Sbostic 			error((char *)NULL);
42869090Sbostic 		}
42969090Sbostic 		error("%.*s: parameter %snot set", p - str - 1,
43069090Sbostic 		      str, (varflags & VSNUL) ? "null or "
43169090Sbostic 					      : nullstr);
43269090Sbostic 		return 0;
43369090Sbostic 
43469090Sbostic 	case VSTRIMLEFT:
43569090Sbostic 		for (loc = startp; loc < str - 1; loc++) {
43669090Sbostic 			c = *loc;
43769090Sbostic 			*loc = '\0';
43869090Sbostic 			if (patmatch(str, startp)) {
43969090Sbostic 				*loc = c;
44069090Sbostic 				goto recordleft;
44169090Sbostic 			}
44269090Sbostic 			*loc = c;
44369090Sbostic 		}
44469090Sbostic 		return 0;
44569090Sbostic 
44669090Sbostic 	case VSTRIMLEFTMAX:
44769090Sbostic 		for (loc = str - 1; loc >= startp; loc--) {
44869090Sbostic 			c = *loc;
44969090Sbostic 			*loc = '\0';
45069090Sbostic 			if (patmatch(str, startp)) {
45169090Sbostic 				*loc = c;
45269090Sbostic 				goto recordleft;
45369090Sbostic 			}
45469090Sbostic 			*loc = c;
45569090Sbostic 		}
45669090Sbostic 		return 0;
45769090Sbostic 
45869090Sbostic 	case VSTRIMRIGHT:
45969090Sbostic 		for (loc = str - 1; loc >= startp; loc--) {
46069090Sbostic 			if (patmatch(str, loc)) {
46169090Sbostic 				expdest = loc;
46269090Sbostic 				return 1;
46369090Sbostic 			}
46469090Sbostic 		}
46569090Sbostic 		return 0;
46669090Sbostic 
46769090Sbostic 	case VSTRIMRIGHTMAX:
46869090Sbostic 		for (loc = startp; loc < str - 1; loc++) {
46969090Sbostic 			if (patmatch(str, loc)) {
47069090Sbostic 				expdest = loc;
47169090Sbostic 				return 1;
47269090Sbostic 			}
47369090Sbostic 		}
47469090Sbostic 		return 0;
47569090Sbostic 
47669090Sbostic 
47769090Sbostic 	default:
47869090Sbostic 		abort();
47969090Sbostic 	}
48069090Sbostic 
48169090Sbostic recordleft:
48269090Sbostic 	expdest = (str - 1) - (loc - startp);
48369090Sbostic 	while (loc != str - 1)
48469090Sbostic 		*startp++ = *loc++;
48569090Sbostic 	return 1;
48669090Sbostic }
48769090Sbostic 
48869090Sbostic 
48947116Sbostic /*
49047116Sbostic  * Expand a variable, and return a pointer to the next character in the
49147116Sbostic  * input string.
49247116Sbostic  */
49347116Sbostic 
49447116Sbostic STATIC char *
evalvar(p,flag)49553299Smarc evalvar(p, flag)
49647116Sbostic 	char *p;
49769272Schristos 	int flag;
49869272Schristos {
49947116Sbostic 	int subtype;
50053299Smarc 	int varflags;
50147116Sbostic 	char *var;
50247116Sbostic 	char *val;
50369090Sbostic 	char *pat;
50447116Sbostic 	int c;
50547116Sbostic 	int set;
50647116Sbostic 	int special;
50747116Sbostic 	int startloc;
50869090Sbostic 	int varlen;
50969090Sbostic 	int easy;
51055787Smarc 	int quotes = flag & (EXP_FULL | EXP_CASE);
51147116Sbostic 
51253299Smarc 	varflags = *p++;
51353299Smarc 	subtype = varflags & VSTYPE;
51447116Sbostic 	var = p;
51547116Sbostic 	special = 0;
51647116Sbostic 	if (! is_name(*p))
51747116Sbostic 		special = 1;
51847116Sbostic 	p = strchr(p, '=') + 1;
51947116Sbostic again: /* jump here after setting a variable with ${var=text} */
52047116Sbostic 	if (special) {
52147116Sbostic 		set = varisset(*var);
52247116Sbostic 		val = NULL;
52347116Sbostic 	} else {
52447116Sbostic 		val = lookupvar(var);
52569272Schristos 		if (val == NULL || ((varflags & VSNUL) && val[0] == '\0')) {
52647116Sbostic 			val = NULL;
52747116Sbostic 			set = 0;
52847116Sbostic 		} else
52947116Sbostic 			set = 1;
53047116Sbostic 	}
53169090Sbostic 	varlen = 0;
53247116Sbostic 	startloc = expdest - stackblock();
53347116Sbostic 	if (set && subtype != VSPLUS) {
53447116Sbostic 		/* insert the value of the variable */
53547116Sbostic 		if (special) {
53669090Sbostic 			char *exp, *oexpdest = expdest;
53753299Smarc 			varvalue(*var, varflags & VSQUOTE, flag & EXP_FULL);
53869090Sbostic 			if (subtype == VSLENGTH) {
53969090Sbostic 				for (exp = oexpdest;exp != expdest; exp++)
54069090Sbostic 					varlen++;
54169090Sbostic 				expdest = oexpdest;
54269090Sbostic 			}
54347116Sbostic 		} else {
54469090Sbostic 			char const *syntax = (varflags & VSQUOTE) ? DQSYNTAX
54569090Sbostic 								  : BASESYNTAX;
54647116Sbostic 
54769090Sbostic 			if (subtype == VSLENGTH) {
54869090Sbostic 				for (;*val; val++)
54969090Sbostic 					varlen++;
55047116Sbostic 			}
55169090Sbostic 			else {
55269090Sbostic 				while (*val) {
55369090Sbostic 					if (quotes && syntax[*val] == CCTL)
55469090Sbostic 						STPUTC(CTLESC, expdest);
55569090Sbostic 					STPUTC(*val++, expdest);
55669090Sbostic 				}
55769090Sbostic 
55869090Sbostic 			}
55947116Sbostic 		}
56047116Sbostic 	}
56169090Sbostic 
56247116Sbostic 	if (subtype == VSPLUS)
56347116Sbostic 		set = ! set;
56469090Sbostic 
56569090Sbostic 	easy = ((varflags & VSQUOTE) == 0 ||
56669090Sbostic 		(*var == '@' && shellparam.nparam != 1));
56769090Sbostic 
56869090Sbostic 
56969090Sbostic 	switch (subtype) {
57069090Sbostic 	case VSLENGTH:
57169090Sbostic 		expdest = cvtnum(varlen, expdest);
57269090Sbostic 		goto record;
57369090Sbostic 
57469090Sbostic 	case VSNORMAL:
57569090Sbostic 		if (!easy)
57669090Sbostic 			break;
57769090Sbostic record:
57869090Sbostic 		recordregion(startloc, expdest - stackblock(),
57969090Sbostic 			     varflags & VSQUOTE);
58069090Sbostic 		break;
58169090Sbostic 
58269090Sbostic 	case VSPLUS:
58369090Sbostic 	case VSMINUS:
58469090Sbostic 		if (!set) {
58553299Smarc 			argstr(p, flag);
58669090Sbostic 			break;
58769090Sbostic 		}
58869090Sbostic 		if (easy)
58969090Sbostic 			goto record;
59069090Sbostic 		break;
59169090Sbostic 
59269090Sbostic 	case VSTRIMLEFT:
59369090Sbostic 	case VSTRIMLEFTMAX:
59469090Sbostic 	case VSTRIMRIGHT:
59569090Sbostic 	case VSTRIMRIGHTMAX:
59669090Sbostic 		if (!set)
59769090Sbostic 			break;
59869090Sbostic 		/*
59969090Sbostic 		 * Terminate the string and start recording the pattern
60069090Sbostic 		 * right after it
60169090Sbostic 		 */
60269090Sbostic 		STPUTC('\0', expdest);
60369090Sbostic 		pat = expdest;
60469090Sbostic 		if (subevalvar(p, pat, subtype, startloc, varflags))
60569090Sbostic 			goto record;
60669090Sbostic 		break;
60769090Sbostic 
60869090Sbostic 	case VSASSIGN:
60969090Sbostic 	case VSQUESTION:
61069090Sbostic 		if (!set) {
61169090Sbostic 			if (subevalvar(p, var, subtype, startloc, varflags))
61247116Sbostic 				goto again;
61369090Sbostic 			break;
61447116Sbostic 		}
61569090Sbostic 		if (easy)
61669090Sbostic 			goto record;
61769090Sbostic 		break;
61869090Sbostic 
61969090Sbostic 	default:
62069090Sbostic 		abort();
62147116Sbostic 	}
62269090Sbostic 
62347116Sbostic 	if (subtype != VSNORMAL) {	/* skip to end of alternative */
62447116Sbostic 		int nesting = 1;
62547116Sbostic 		for (;;) {
62647116Sbostic 			if ((c = *p++) == CTLESC)
62747116Sbostic 				p++;
62847116Sbostic 			else if (c == CTLBACKQ || c == (CTLBACKQ|CTLQUOTE)) {
62947116Sbostic 				if (set)
63047116Sbostic 					argbackq = argbackq->next;
63147116Sbostic 			} else if (c == CTLVAR) {
63247116Sbostic 				if ((*p++ & VSTYPE) != VSNORMAL)
63347116Sbostic 					nesting++;
63447116Sbostic 			} else if (c == CTLENDVAR) {
63547116Sbostic 				if (--nesting == 0)
63647116Sbostic 					break;
63747116Sbostic 			}
63847116Sbostic 		}
63947116Sbostic 	}
64047116Sbostic 	return p;
64147116Sbostic }
64247116Sbostic 
64347116Sbostic 
64447116Sbostic 
64547116Sbostic /*
64647116Sbostic  * Test whether a specialized variable is set.
64747116Sbostic  */
64847116Sbostic 
64947116Sbostic STATIC int
varisset(name)65047116Sbostic varisset(name)
65147116Sbostic 	char name;
65247116Sbostic 	{
65347116Sbostic 	char **ap;
65447116Sbostic 
65547116Sbostic 	if (name == '!') {
65647116Sbostic 		if (backgndpid == -1)
65747116Sbostic 			return 0;
65847116Sbostic 	} else if (name == '@' || name == '*') {
65947116Sbostic 		if (*shellparam.p == NULL)
66047116Sbostic 			return 0;
66147116Sbostic 	} else if ((unsigned)(name -= '1') <= '9' - '1') {
66247116Sbostic 		ap = shellparam.p;
66347116Sbostic 		do {
66447116Sbostic 			if (*ap++ == NULL)
66547116Sbostic 				return 0;
66647116Sbostic 		} while (--name >= 0);
66747116Sbostic 	}
66847116Sbostic 	return 1;
66947116Sbostic }
67047116Sbostic 
67147116Sbostic 
67247116Sbostic 
67347116Sbostic /*
67447116Sbostic  * Add the value of a specialized variable to the stack string.
67547116Sbostic  */
67647116Sbostic 
67747116Sbostic STATIC void
varvalue(name,quoted,allow_split)67847116Sbostic varvalue(name, quoted, allow_split)
67947116Sbostic 	char name;
68069272Schristos 	int quoted;
68169272Schristos 	int allow_split;
68269272Schristos {
68347116Sbostic 	int num;
68447116Sbostic 	char *p;
68547116Sbostic 	int i;
686*69469Schristos 	extern int oexitstatus;
68747116Sbostic 	char sep;
68847116Sbostic 	char **ap;
68947116Sbostic 	char const *syntax;
69047116Sbostic 
69154315Smarc #define STRTODEST(p) \
69254315Smarc 	do {\
69354315Smarc 	if (allow_split) { \
69454315Smarc 		syntax = quoted? DQSYNTAX : BASESYNTAX; \
69554315Smarc 		while (*p) { \
69654315Smarc 			if (syntax[*p] == CCTL) \
69754315Smarc 				STPUTC(CTLESC, expdest); \
69854315Smarc 			STPUTC(*p++, expdest); \
69954315Smarc 		} \
70054315Smarc 	} else \
70154315Smarc 		while (*p) \
70254315Smarc 			STPUTC(*p++, expdest); \
70354315Smarc 	} while (0)
70454315Smarc 
70554315Smarc 
70647116Sbostic 	switch (name) {
70747116Sbostic 	case '$':
70847116Sbostic 		num = rootpid;
70947116Sbostic 		goto numvar;
71047116Sbostic 	case '?':
711*69469Schristos 		num = oexitstatus;
71247116Sbostic 		goto numvar;
71347116Sbostic 	case '#':
71447116Sbostic 		num = shellparam.nparam;
71547116Sbostic 		goto numvar;
71647116Sbostic 	case '!':
71747116Sbostic 		num = backgndpid;
71847116Sbostic numvar:
71969090Sbostic 		expdest = cvtnum(num, expdest);
72047116Sbostic 		break;
72147116Sbostic 	case '-':
72255243Smarc 		for (i = 0 ; i < NOPTS ; i++) {
72355243Smarc 			if (optlist[i].val)
72455243Smarc 				STPUTC(optlist[i].letter, expdest);
72547116Sbostic 		}
72647116Sbostic 		break;
72747116Sbostic 	case '@':
72847116Sbostic 		if (allow_split) {
72947116Sbostic 			sep = '\0';
73047116Sbostic 			goto allargs;
73147116Sbostic 		}
73247116Sbostic 		/* fall through */
73347116Sbostic 	case '*':
73447116Sbostic 		sep = ' ';
73547116Sbostic allargs:
73647116Sbostic 		for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
73754315Smarc 			STRTODEST(p);
73847116Sbostic 			if (*ap)
73947116Sbostic 				STPUTC(sep, expdest);
74047116Sbostic 		}
74147116Sbostic 		break;
74247116Sbostic 	case '0':
74347116Sbostic 		p = arg0;
74454315Smarc 		STRTODEST(p);
74547116Sbostic 		break;
74647116Sbostic 	default:
74747116Sbostic 		if ((unsigned)(name -= '1') <= '9' - '1') {
74847116Sbostic 			p = shellparam.p[name];
74954315Smarc 			STRTODEST(p);
75047116Sbostic 		}
75147116Sbostic 		break;
75247116Sbostic 	}
75347116Sbostic }
75447116Sbostic 
75547116Sbostic 
75647116Sbostic 
75747116Sbostic /*
75847116Sbostic  * Record the the fact that we have to scan this region of the
75947116Sbostic  * string for IFS characters.
76047116Sbostic  */
76147116Sbostic 
76247116Sbostic STATIC void
recordregion(start,end,nulonly)76369272Schristos recordregion(start, end, nulonly)
76469272Schristos 	int start;
76569272Schristos 	int end;
76669272Schristos 	int nulonly;
76769272Schristos {
76847116Sbostic 	register struct ifsregion *ifsp;
76947116Sbostic 
77047116Sbostic 	if (ifslastp == NULL) {
77147116Sbostic 		ifsp = &ifsfirst;
77247116Sbostic 	} else {
77347116Sbostic 		ifsp = (struct ifsregion *)ckmalloc(sizeof (struct ifsregion));
77447116Sbostic 		ifslastp->next = ifsp;
77547116Sbostic 	}
77647116Sbostic 	ifslastp = ifsp;
77747116Sbostic 	ifslastp->next = NULL;
77847116Sbostic 	ifslastp->begoff = start;
77947116Sbostic 	ifslastp->endoff = end;
78047116Sbostic 	ifslastp->nulonly = nulonly;
78147116Sbostic }
78247116Sbostic 
78347116Sbostic 
78447116Sbostic 
78547116Sbostic /*
78647116Sbostic  * Break the argument string into pieces based upon IFS and add the
78747116Sbostic  * strings to the argument list.  The regions of the string to be
78847116Sbostic  * searched for IFS characters have been stored by recordregion.
78947116Sbostic  */
79047116Sbostic STATIC void
ifsbreakup(string,arglist)79147116Sbostic ifsbreakup(string, arglist)
79247116Sbostic 	char *string;
79347116Sbostic 	struct arglist *arglist;
79447116Sbostic 	{
79547116Sbostic 	struct ifsregion *ifsp;
79647116Sbostic 	struct strlist *sp;
79747116Sbostic 	char *start;
79847116Sbostic 	register char *p;
79947116Sbostic 	char *q;
80047116Sbostic 	char *ifs;
80169272Schristos 	int ifsspc;
80247116Sbostic 
80369272Schristos 
80447116Sbostic 	start = string;
80547116Sbostic 	if (ifslastp != NULL) {
80647116Sbostic 		ifsp = &ifsfirst;
80747116Sbostic 		do {
80847116Sbostic 			p = string + ifsp->begoff;
80947116Sbostic 			ifs = ifsp->nulonly? nullstr : ifsval();
81069272Schristos 			ifsspc = strchr(ifs, ' ') != NULL;
81147116Sbostic 			while (p < string + ifsp->endoff) {
81247116Sbostic 				q = p;
81347116Sbostic 				if (*p == CTLESC)
81447116Sbostic 					p++;
81547116Sbostic 				if (strchr(ifs, *p++)) {
81669272Schristos 					if (q > start || !ifsspc) {
81747116Sbostic 						*q = '\0';
81847116Sbostic 						sp = (struct strlist *)stalloc(sizeof *sp);
81947116Sbostic 						sp->text = start;
82047116Sbostic 						*arglist->lastp = sp;
82147116Sbostic 						arglist->lastp = &sp->next;
82247116Sbostic 					}
82369272Schristos 					if (ifsspc) {
82447116Sbostic 						for (;;) {
82547116Sbostic 							if (p >= string + ifsp->endoff)
82647116Sbostic 								break;
82747116Sbostic 							q = p;
82847116Sbostic 							if (*p == CTLESC)
82947116Sbostic 								p++;
83047116Sbostic 							if (strchr(ifs, *p++) == NULL) {
83147116Sbostic 								p = q;
83247116Sbostic 								break;
83347116Sbostic 							}
83447116Sbostic 						}
83547116Sbostic 					}
83647116Sbostic 					start = p;
83747116Sbostic 				}
83847116Sbostic 			}
83947116Sbostic 		} while ((ifsp = ifsp->next) != NULL);
84069272Schristos 		if (*start || (!ifsspc && start > string)) {
84147116Sbostic 			sp = (struct strlist *)stalloc(sizeof *sp);
84247116Sbostic 			sp->text = start;
84347116Sbostic 			*arglist->lastp = sp;
84447116Sbostic 			arglist->lastp = &sp->next;
84547116Sbostic 		}
84647116Sbostic 	} else {
84747116Sbostic 		sp = (struct strlist *)stalloc(sizeof *sp);
84847116Sbostic 		sp->text = start;
84947116Sbostic 		*arglist->lastp = sp;
85047116Sbostic 		arglist->lastp = &sp->next;
85147116Sbostic 	}
85247116Sbostic }
85347116Sbostic 
85447116Sbostic 
85547116Sbostic 
85647116Sbostic /*
85747116Sbostic  * Expand shell metacharacters.  At this point, the only control characters
85847116Sbostic  * should be escapes.  The results are stored in the list exparg.
85947116Sbostic  */
86047116Sbostic 
86147116Sbostic char *expdir;
86247116Sbostic 
86347116Sbostic 
86447116Sbostic STATIC void
expandmeta(str,flag)86553299Smarc expandmeta(str, flag)
86647116Sbostic 	struct strlist *str;
86769272Schristos 	int flag;
86869272Schristos {
86947116Sbostic 	char *p;
87047116Sbostic 	struct strlist **savelastp;
87147116Sbostic 	struct strlist *sp;
87247116Sbostic 	char c;
87353299Smarc 	/* TODO - EXP_REDIR */
87447116Sbostic 
87547116Sbostic 	while (str) {
87647116Sbostic 		if (fflag)
87747116Sbostic 			goto nometa;
87847116Sbostic 		p = str->text;
87947116Sbostic 		for (;;) {			/* fast check for meta chars */
88047116Sbostic 			if ((c = *p++) == '\0')
88147116Sbostic 				goto nometa;
88247116Sbostic 			if (c == '*' || c == '?' || c == '[' || c == '!')
88347116Sbostic 				break;
88447116Sbostic 		}
88547116Sbostic 		savelastp = exparg.lastp;
88647116Sbostic 		INTOFF;
88755272Smarc 		if (expdir == NULL) {
88855272Smarc 			int i = strlen(str->text);
88955272Smarc 			expdir = ckmalloc(i < 2048 ? 2048 : i); /* XXX */
89055272Smarc 		}
89155272Smarc 
89247116Sbostic 		expmeta(expdir, str->text);
89347116Sbostic 		ckfree(expdir);
89447116Sbostic 		expdir = NULL;
89547116Sbostic 		INTON;
89647116Sbostic 		if (exparg.lastp == savelastp) {
89753299Smarc 			/*
89853299Smarc 			 * no matches
89953299Smarc 			 */
90047116Sbostic nometa:
90155243Smarc 			*exparg.lastp = str;
90255243Smarc 			rmescapes(str->text);
90355243Smarc 			exparg.lastp = &str->next;
90447116Sbostic 		} else {
90547116Sbostic 			*exparg.lastp = NULL;
90647116Sbostic 			*savelastp = sp = expsort(*savelastp);
90747116Sbostic 			while (sp->next != NULL)
90847116Sbostic 				sp = sp->next;
90947116Sbostic 			exparg.lastp = &sp->next;
91047116Sbostic 		}
91147116Sbostic 		str = str->next;
91247116Sbostic 	}
91347116Sbostic }
91447116Sbostic 
91547116Sbostic 
91647116Sbostic /*
91747116Sbostic  * Do metacharacter (i.e. *, ?, [...]) expansion.
91847116Sbostic  */
91947116Sbostic 
92047116Sbostic STATIC void
expmeta(enddir,name)92147116Sbostic expmeta(enddir, name)
92247116Sbostic 	char *enddir;
92347116Sbostic 	char *name;
92447116Sbostic 	{
92547116Sbostic 	register char *p;
92647116Sbostic 	char *q;
92747116Sbostic 	char *start;
92847116Sbostic 	char *endname;
92947116Sbostic 	int metaflag;
93047116Sbostic 	struct stat statb;
93147116Sbostic 	DIR *dirp;
93247116Sbostic 	struct dirent *dp;
93347116Sbostic 	int atend;
93447116Sbostic 	int matchdot;
93547116Sbostic 
93647116Sbostic 	metaflag = 0;
93747116Sbostic 	start = name;
93847116Sbostic 	for (p = name ; ; p++) {
93947116Sbostic 		if (*p == '*' || *p == '?')
94047116Sbostic 			metaflag = 1;
94147116Sbostic 		else if (*p == '[') {
94247116Sbostic 			q = p + 1;
94347116Sbostic 			if (*q == '!')
94447116Sbostic 				q++;
94547116Sbostic 			for (;;) {
94647116Sbostic 				if (*q == CTLESC)
94747116Sbostic 					q++;
94847116Sbostic 				if (*q == '/' || *q == '\0')
94947116Sbostic 					break;
95047116Sbostic 				if (*++q == ']') {
95147116Sbostic 					metaflag = 1;
95247116Sbostic 					break;
95347116Sbostic 				}
95447116Sbostic 			}
95547116Sbostic 		} else if (*p == '!' && p[1] == '!'	&& (p == name || p[-1] == '/')) {
95647116Sbostic 			metaflag = 1;
95747116Sbostic 		} else if (*p == '\0')
95847116Sbostic 			break;
95947116Sbostic 		else if (*p == CTLESC)
96047116Sbostic 			p++;
96147116Sbostic 		if (*p == '/') {
96247116Sbostic 			if (metaflag)
96347116Sbostic 				break;
96447116Sbostic 			start = p + 1;
96547116Sbostic 		}
96647116Sbostic 	}
96747116Sbostic 	if (metaflag == 0) {	/* we've reached the end of the file name */
96847116Sbostic 		if (enddir != expdir)
96947116Sbostic 			metaflag++;
97047116Sbostic 		for (p = name ; ; p++) {
97147116Sbostic 			if (*p == CTLESC)
97247116Sbostic 				p++;
97347116Sbostic 			*enddir++ = *p;
97447116Sbostic 			if (*p == '\0')
97547116Sbostic 				break;
97647116Sbostic 		}
97747116Sbostic 		if (metaflag == 0 || stat(expdir, &statb) >= 0)
97847116Sbostic 			addfname(expdir);
97947116Sbostic 		return;
98047116Sbostic 	}
98147116Sbostic 	endname = p;
98247116Sbostic 	if (start != name) {
98347116Sbostic 		p = name;
98447116Sbostic 		while (p < start) {
98547116Sbostic 			if (*p == CTLESC)
98647116Sbostic 				p++;
98747116Sbostic 			*enddir++ = *p++;
98847116Sbostic 		}
98947116Sbostic 	}
99047116Sbostic 	if (enddir == expdir) {
99147116Sbostic 		p = ".";
99247116Sbostic 	} else if (enddir == expdir + 1 && *expdir == '/') {
99347116Sbostic 		p = "/";
99447116Sbostic 	} else {
99547116Sbostic 		p = expdir;
99647116Sbostic 		enddir[-1] = '\0';
99747116Sbostic 	}
99847116Sbostic 	if ((dirp = opendir(p)) == NULL)
99947116Sbostic 		return;
100047116Sbostic 	if (enddir != expdir)
100147116Sbostic 		enddir[-1] = '/';
100247116Sbostic 	if (*endname == 0) {
100347116Sbostic 		atend = 1;
100447116Sbostic 	} else {
100547116Sbostic 		atend = 0;
100647116Sbostic 		*endname++ = '\0';
100747116Sbostic 	}
100847116Sbostic 	matchdot = 0;
100969272Schristos 	if (start[0] == '.' || (start[0] == CTLESC && start[1] == '.'))
101047116Sbostic 		matchdot++;
101147116Sbostic 	while (! int_pending() && (dp = readdir(dirp)) != NULL) {
101247116Sbostic 		if (dp->d_name[0] == '.' && ! matchdot)
101347116Sbostic 			continue;
101447116Sbostic 		if (patmatch(start, dp->d_name)) {
101547116Sbostic 			if (atend) {
101647116Sbostic 				scopy(dp->d_name, enddir);
101747116Sbostic 				addfname(expdir);
101847116Sbostic 			} else {
101947116Sbostic 				char *q;
102069272Schristos 				for (p = enddir, q = dp->d_name;
102169272Schristos 				     (*p++ = *q++) != '\0';)
102269272Schristos 					continue;
102347116Sbostic 				p[-1] = '/';
102447116Sbostic 				expmeta(p, endname);
102547116Sbostic 			}
102647116Sbostic 		}
102747116Sbostic 	}
102847116Sbostic 	closedir(dirp);
102947116Sbostic 	if (! atend)
103047116Sbostic 		endname[-1] = '/';
103147116Sbostic }
103247116Sbostic 
103347116Sbostic 
103447116Sbostic /*
103547116Sbostic  * Add a file name to the list.
103647116Sbostic  */
103747116Sbostic 
103847116Sbostic STATIC void
addfname(name)103947116Sbostic addfname(name)
104047116Sbostic 	char *name;
104147116Sbostic 	{
104247116Sbostic 	char *p;
104347116Sbostic 	struct strlist *sp;
104447116Sbostic 
104547116Sbostic 	p = stalloc(strlen(name) + 1);
104647116Sbostic 	scopy(name, p);
104747116Sbostic 	sp = (struct strlist *)stalloc(sizeof *sp);
104847116Sbostic 	sp->text = p;
104947116Sbostic 	*exparg.lastp = sp;
105047116Sbostic 	exparg.lastp = &sp->next;
105147116Sbostic }
105247116Sbostic 
105347116Sbostic 
105447116Sbostic /*
105547116Sbostic  * Sort the results of file name expansion.  It calculates the number of
105647116Sbostic  * strings to sort and then calls msort (short for merge sort) to do the
105747116Sbostic  * work.
105847116Sbostic  */
105947116Sbostic 
106047116Sbostic STATIC struct strlist *
expsort(str)106147116Sbostic expsort(str)
106247116Sbostic 	struct strlist *str;
106347116Sbostic 	{
106447116Sbostic 	int len;
106547116Sbostic 	struct strlist *sp;
106647116Sbostic 
106747116Sbostic 	len = 0;
106847116Sbostic 	for (sp = str ; sp ; sp = sp->next)
106947116Sbostic 		len++;
107047116Sbostic 	return msort(str, len);
107147116Sbostic }
107247116Sbostic 
107347116Sbostic 
107447116Sbostic STATIC struct strlist *
msort(list,len)107547116Sbostic msort(list, len)
107647116Sbostic 	struct strlist *list;
107769272Schristos 	int len;
107869272Schristos {
107947116Sbostic 	struct strlist *p, *q;
108047116Sbostic 	struct strlist **lpp;
108147116Sbostic 	int half;
108247116Sbostic 	int n;
108347116Sbostic 
108447116Sbostic 	if (len <= 1)
108547116Sbostic 		return list;
108647116Sbostic 	half = len >> 1;
108747116Sbostic 	p = list;
108847116Sbostic 	for (n = half ; --n >= 0 ; ) {
108947116Sbostic 		q = p;
109047116Sbostic 		p = p->next;
109147116Sbostic 	}
109247116Sbostic 	q->next = NULL;			/* terminate first half of list */
109347116Sbostic 	q = msort(list, half);		/* sort first half of list */
109447116Sbostic 	p = msort(p, len - half);		/* sort second half */
109547116Sbostic 	lpp = &list;
109647116Sbostic 	for (;;) {
109747116Sbostic 		if (strcmp(p->text, q->text) < 0) {
109847116Sbostic 			*lpp = p;
109947116Sbostic 			lpp = &p->next;
110047116Sbostic 			if ((p = *lpp) == NULL) {
110147116Sbostic 				*lpp = q;
110247116Sbostic 				break;
110347116Sbostic 			}
110447116Sbostic 		} else {
110547116Sbostic 			*lpp = q;
110647116Sbostic 			lpp = &q->next;
110747116Sbostic 			if ((q = *lpp) == NULL) {
110847116Sbostic 				*lpp = p;
110947116Sbostic 				break;
111047116Sbostic 			}
111147116Sbostic 		}
111247116Sbostic 	}
111347116Sbostic 	return list;
111447116Sbostic }
111547116Sbostic 
111647116Sbostic 
111747116Sbostic 
111847116Sbostic /*
111947116Sbostic  * Returns true if the pattern matches the string.
112047116Sbostic  */
112147116Sbostic 
112247116Sbostic int
patmatch(pattern,string)112347116Sbostic patmatch(pattern, string)
112447116Sbostic 	char *pattern;
112547116Sbostic 	char *string;
112647116Sbostic 	{
112755787Smarc #ifdef notdef
112847116Sbostic 	if (pattern[0] == '!' && pattern[1] == '!')
112947116Sbostic 		return 1 - pmatch(pattern + 2, string);
113047116Sbostic 	else
113155787Smarc #endif
113247116Sbostic 		return pmatch(pattern, string);
113347116Sbostic }
113447116Sbostic 
113547116Sbostic 
113647116Sbostic STATIC int
pmatch(pattern,string)113747116Sbostic pmatch(pattern, string)
113847116Sbostic 	char *pattern;
113947116Sbostic 	char *string;
114047116Sbostic 	{
114147116Sbostic 	register char *p, *q;
114247116Sbostic 	register char c;
114347116Sbostic 
114447116Sbostic 	p = pattern;
114547116Sbostic 	q = string;
114647116Sbostic 	for (;;) {
114747116Sbostic 		switch (c = *p++) {
114847116Sbostic 		case '\0':
114947116Sbostic 			goto breakloop;
115047116Sbostic 		case CTLESC:
115147116Sbostic 			if (*q++ != *p++)
115247116Sbostic 				return 0;
115347116Sbostic 			break;
115447116Sbostic 		case '?':
115547116Sbostic 			if (*q++ == '\0')
115647116Sbostic 				return 0;
115747116Sbostic 			break;
115847116Sbostic 		case '*':
115947116Sbostic 			c = *p;
116047116Sbostic 			if (c != CTLESC && c != '?' && c != '*' && c != '[') {
116147116Sbostic 				while (*q != c) {
116247116Sbostic 					if (*q == '\0')
116347116Sbostic 						return 0;
116447116Sbostic 					q++;
116547116Sbostic 				}
116647116Sbostic 			}
116747116Sbostic 			do {
116847116Sbostic 				if (pmatch(p, q))
116947116Sbostic 					return 1;
117047116Sbostic 			} while (*q++ != '\0');
117147116Sbostic 			return 0;
117247116Sbostic 		case '[': {
117347116Sbostic 			char *endp;
117447116Sbostic 			int invert, found;
117547116Sbostic 			char chr;
117647116Sbostic 
117747116Sbostic 			endp = p;
117847116Sbostic 			if (*endp == '!')
117947116Sbostic 				endp++;
118047116Sbostic 			for (;;) {
118147116Sbostic 				if (*endp == '\0')
118247116Sbostic 					goto dft;		/* no matching ] */
118347116Sbostic 				if (*endp == CTLESC)
118447116Sbostic 					endp++;
118547116Sbostic 				if (*++endp == ']')
118647116Sbostic 					break;
118747116Sbostic 			}
118847116Sbostic 			invert = 0;
118947116Sbostic 			if (*p == '!') {
119047116Sbostic 				invert++;
119147116Sbostic 				p++;
119247116Sbostic 			}
119347116Sbostic 			found = 0;
119447116Sbostic 			chr = *q++;
119569272Schristos 			if (chr == '\0')
119669272Schristos 				return 0;
119747116Sbostic 			c = *p++;
119847116Sbostic 			do {
119947116Sbostic 				if (c == CTLESC)
120047116Sbostic 					c = *p++;
120147116Sbostic 				if (*p == '-' && p[1] != ']') {
120247116Sbostic 					p++;
120347116Sbostic 					if (*p == CTLESC)
120447116Sbostic 						p++;
120547116Sbostic 					if (chr >= c && chr <= *p)
120647116Sbostic 						found = 1;
120747116Sbostic 					p++;
120847116Sbostic 				} else {
120947116Sbostic 					if (chr == c)
121047116Sbostic 						found = 1;
121147116Sbostic 				}
121247116Sbostic 			} while ((c = *p++) != ']');
121347116Sbostic 			if (found == invert)
121447116Sbostic 				return 0;
121547116Sbostic 			break;
121647116Sbostic 		}
121755787Smarc dft:	        default:
121847116Sbostic 			if (*q++ != c)
121947116Sbostic 				return 0;
122047116Sbostic 			break;
122147116Sbostic 		}
122247116Sbostic 	}
122347116Sbostic breakloop:
122447116Sbostic 	if (*q != '\0')
122547116Sbostic 		return 0;
122647116Sbostic 	return 1;
122747116Sbostic }
122847116Sbostic 
122947116Sbostic 
123047116Sbostic 
123147116Sbostic /*
123247116Sbostic  * Remove any CTLESC characters from a string.
123347116Sbostic  */
123447116Sbostic 
123547116Sbostic void
rmescapes(str)123647116Sbostic rmescapes(str)
123747116Sbostic 	char *str;
123847116Sbostic 	{
123947116Sbostic 	register char *p, *q;
124047116Sbostic 
124147116Sbostic 	p = str;
124247116Sbostic 	while (*p != CTLESC) {
124347116Sbostic 		if (*p++ == '\0')
124447116Sbostic 			return;
124547116Sbostic 	}
124647116Sbostic 	q = p;
124747116Sbostic 	while (*p) {
124847116Sbostic 		if (*p == CTLESC)
124947116Sbostic 			p++;
125047116Sbostic 		*q++ = *p++;
125147116Sbostic 	}
125247116Sbostic 	*q = '\0';
125347116Sbostic }
125447116Sbostic 
125547116Sbostic 
125647116Sbostic 
125747116Sbostic /*
125847116Sbostic  * See if a pattern matches in a case statement.
125947116Sbostic  */
126047116Sbostic 
126147116Sbostic int
casematch(pattern,val)126247116Sbostic casematch(pattern, val)
126347116Sbostic 	union node *pattern;
126447116Sbostic 	char *val;
126547116Sbostic 	{
126647116Sbostic 	struct stackmark smark;
126747116Sbostic 	int result;
126847116Sbostic 	char *p;
126947116Sbostic 
127047116Sbostic 	setstackmark(&smark);
127147116Sbostic 	argbackq = pattern->narg.backquote;
127247116Sbostic 	STARTSTACKSTR(expdest);
127347116Sbostic 	ifslastp = NULL;
127455787Smarc 	argstr(pattern->narg.text, EXP_TILDE | EXP_CASE);
127547116Sbostic 	STPUTC('\0', expdest);
127647116Sbostic 	p = grabstackstr(expdest);
127747116Sbostic 	result = patmatch(p, val);
127847116Sbostic 	popstackmark(&smark);
127947116Sbostic 	return result;
128047116Sbostic }
128169090Sbostic 
128269090Sbostic /*
128369090Sbostic  * Our own itoa().
128469090Sbostic  */
128569090Sbostic 
128669090Sbostic STATIC char *
cvtnum(num,buf)128769090Sbostic cvtnum(num, buf)
128869090Sbostic 	int num;
128969090Sbostic 	char *buf;
129069090Sbostic 	{
129169090Sbostic 	char temp[32];
129269090Sbostic 	int neg = num < 0;
129369090Sbostic 	char *p = temp + 31;
129469090Sbostic 
129569090Sbostic 	temp[31] = '\0';
129669090Sbostic 
129769090Sbostic 	do {
129869090Sbostic 		*--p = num % 10 + '0';
129969090Sbostic 	} while ((num /= 10) != 0);
130069090Sbostic 
130169090Sbostic 	if (neg)
130269090Sbostic 		*--p = '-';
130369090Sbostic 
130469090Sbostic 	while (*p)
130569090Sbostic 		STPUTC(*p++, buf);
130669090Sbostic 	return buf;
130769090Sbostic }
1308