1/*	$OpenBSD: eval.c,v 1.67 2023/05/24 14:20:33 millert Exp $	*/
2
3/*
4 * Expansion - quoting, separation, substitution, globbing
5 */
6
7#include <sys/stat.h>
8
9#include <ctype.h>
10#include <dirent.h>
11#include <errno.h>
12#include <fcntl.h>
13#include <pwd.h>
14#include <stdio.h>
15#include <string.h>
16#include <unistd.h>
17
18#include "sh.h"
19
20/*
21 * string expansion
22 *
23 * first pass: quoting, IFS separation, ~, ${}, $() and $(()) substitution.
24 * second pass: alternation ({,}), filename expansion (*?[]).
25 */
26
27/* expansion generator state */
28typedef struct Expand {
29	/* int  type; */	/* see expand() */
30	const char *str;	/* string */
31	union {
32		const char **strv;/* string[] */
33		struct shf *shf;/* file */
34	} u;			/* source */
35	struct tbl *var;	/* variable in ${var..} */
36	short	split;		/* split "$@" / call waitlast $() */
37} Expand;
38
39#define	XBASE		0	/* scanning original */
40#define	XSUB		1	/* expanding ${} string */
41#define	XARGSEP		2	/* ifs0 between "$*" */
42#define	XARG		3	/* expanding $*, $@ */
43#define	XCOM		4	/* expanding $() */
44#define XNULLSUB	5	/* "$@" when $# is 0 (don't generate word) */
45#define XSUBMID		6	/* middle of expanding ${} */
46
47/* States used for field splitting */
48#define IFS_WORD	0	/* word has chars (or quotes) */
49#define IFS_WS		1	/* have seen IFS white-space */
50#define IFS_NWS		2	/* have seen IFS non-white-space */
51#define IFS_IWS		3	/* beginning of word, ignore IFS white-space */
52#define IFS_QUOTE	4	/* beg.w/quote, becomes IFS_WORD unless "$@" */
53
54static	int	varsub(Expand *, char *, char *, int *, int *);
55static	int	comsub(Expand *, char *);
56static	char   *trimsub(char *, char *, int);
57static	void	glob(char *, XPtrV *, int);
58static	void	globit(XString *, char **, char *, XPtrV *, int);
59static char	*maybe_expand_tilde(char *, XString *, char **, int);
60static	char   *tilde(char *);
61static	char   *homedir(char *);
62static void	alt_expand(XPtrV *, char *, char *, char *, int);
63
64static struct tbl *varcpy(struct tbl *);
65
66/* compile and expand word */
67char *
68substitute(const char *cp, int f)
69{
70	struct source *s, *sold;
71
72	if (disable_subst)
73		return str_save(cp, ATEMP);
74
75	sold = source;
76	s = pushs(SWSTR, ATEMP);
77	s->start = s->str = cp;
78	source = s;
79	if (yylex(ONEWORD) != LWORD)
80		internal_errorf("substitute");
81	source = sold;
82	afree(s, ATEMP);
83	return evalstr(yylval.cp, f);
84}
85
86/*
87 * expand arg-list
88 */
89char **
90eval(char **ap, int f)
91{
92	XPtrV w;
93
94	if (*ap == NULL)
95		return ap;
96	XPinit(w, 32);
97	XPput(w, NULL);		/* space for shell name */
98	while (*ap != NULL)
99		expand(*ap++, &w, f);
100	XPput(w, NULL);
101	return (char **) XPclose(w) + 1;
102}
103
104/*
105 * expand string
106 */
107char *
108evalstr(char *cp, int f)
109{
110	XPtrV w;
111
112	XPinit(w, 1);
113	expand(cp, &w, f);
114	cp = (XPsize(w) == 0) ? null : (char*) *XPptrv(w);
115	XPfree(w);
116	return cp;
117}
118
119/*
120 * expand string - return only one component
121 * used from iosetup to expand redirection files
122 */
123char *
124evalonestr(char *cp, int f)
125{
126	XPtrV w;
127
128	XPinit(w, 1);
129	expand(cp, &w, f);
130	switch (XPsize(w)) {
131	case 0:
132		cp = null;
133		break;
134	case 1:
135		cp = (char*) *XPptrv(w);
136		break;
137	default:
138		cp = evalstr(cp, f&~DOGLOB);
139		break;
140	}
141	XPfree(w);
142	return cp;
143}
144
145/* for nested substitution: ${var:=$var2} */
146typedef struct SubType {
147	short	stype;		/* [=+-?%#] action after expanded word */
148	short	base;		/* begin position of expanded word */
149	short	f;		/* saved value of f (DOPAT, etc) */
150	struct tbl *var;	/* variable for ${var..} */
151	short	quote;		/* saved value of quote (for ${..[%#]..}) */
152	struct SubType *prev;	/* old type */
153	struct SubType *next;	/* poped type (to avoid re-allocating) */
154} SubType;
155
156void
157expand(char *cp,	/* input word */
158    XPtrV *wp,		/* output words */
159    int f)		/* DO* flags */
160{
161	int c = 0;
162	int type;		/* expansion type */
163	int quote = 0;		/* quoted */
164	XString ds;		/* destination string */
165	char *dp, *sp;		/* dest., source */
166	int fdo, word;		/* second pass flags; have word */
167	int doblank;		/* field splitting of parameter/command subst */
168	Expand x = {
169		/* expansion variables */
170		NULL, { NULL }, NULL, 0
171	};
172	SubType st_head, *st;
173	int newlines = 0; /* For trailing newlines in COMSUB */
174	int saw_eq, tilde_ok;
175	int make_magic;
176	size_t len;
177
178	if (cp == NULL)
179		internal_errorf("expand(NULL)");
180	/* for alias, readonly, set, typeset commands */
181	if ((f & DOVACHECK) && is_wdvarassign(cp)) {
182		f &= ~(DOVACHECK|DOBLANK|DOGLOB|DOTILDE);
183		f |= DOASNTILDE;
184	}
185	if (Flag(FNOGLOB))
186		f &= ~DOGLOB;
187	if (Flag(FMARKDIRS))
188		f |= DOMARKDIRS;
189	if (Flag(FBRACEEXPAND) && (f & DOGLOB))
190		f |= DOBRACE_;
191
192	Xinit(ds, dp, 128, ATEMP);	/* init dest. string */
193	type = XBASE;
194	sp = cp;
195	fdo = 0;
196	saw_eq = 0;
197	tilde_ok = (f & (DOTILDE|DOASNTILDE)) ? 1 : 0; /* must be 1/0 */
198	doblank = 0;
199	make_magic = 0;
200	word = (f&DOBLANK) ? IFS_WS : IFS_WORD;
201
202	memset(&st_head, 0, sizeof(st_head));
203	st = &st_head;
204
205	while (1) {
206		Xcheck(ds, dp);
207
208		switch (type) {
209		case XBASE:	/* original prefixed string */
210			c = *sp++;
211			switch (c) {
212			case EOS:
213				c = 0;
214				break;
215			case CHAR:
216				c = *sp++;
217				break;
218			case QCHAR:
219				quote |= 2; /* temporary quote */
220				c = *sp++;
221				break;
222			case OQUOTE:
223				switch (word) {
224				case IFS_QUOTE:
225					/* """something */
226					word = IFS_WORD;
227					break;
228				case IFS_WORD:
229					break;
230				default:
231					word = IFS_QUOTE;
232					break;
233				}
234				tilde_ok = 0;
235				quote = 1;
236				continue;
237			case CQUOTE:
238				quote = 0;
239				continue;
240			case COMSUB:
241				tilde_ok = 0;
242				if (f & DONTRUNCOMMAND) {
243					word = IFS_WORD;
244					*dp++ = '$'; *dp++ = '(';
245					while (*sp != '\0') {
246						Xcheck(ds, dp);
247						*dp++ = *sp++;
248					}
249					*dp++ = ')';
250				} else {
251					type = comsub(&x, sp);
252					if (type == XCOM && (f&DOBLANK))
253						doblank++;
254					sp = strchr(sp, 0) + 1;
255					newlines = 0;
256				}
257				continue;
258			case EXPRSUB:
259				word = IFS_WORD;
260				tilde_ok = 0;
261				if (f & DONTRUNCOMMAND) {
262					*dp++ = '$'; *dp++ = '('; *dp++ = '(';
263					while (*sp != '\0') {
264						Xcheck(ds, dp);
265						*dp++ = *sp++;
266					}
267					*dp++ = ')'; *dp++ = ')';
268				} else {
269					struct tbl v;
270					char *p;
271
272					v.flag = DEFINED|ISSET|INTEGER;
273					v.type = 10; /* not default */
274					v.name[0] = '\0';
275					v_evaluate(&v, substitute(sp, 0),
276					    KSH_UNWIND_ERROR, true);
277					sp = strchr(sp, 0) + 1;
278					for (p = str_val(&v); *p; ) {
279						Xcheck(ds, dp);
280						*dp++ = *p++;
281					}
282				}
283				continue;
284			case OSUBST: /* ${{#}var{:}[=+-?#%]word} */
285			  /* format is:
286			   *   OSUBST [{x] plain-variable-part \0
287			   *     compiled-word-part CSUBST [}x]
288			   * This is where all syntax checking gets done...
289			   */
290			    {
291				char *varname = ++sp; /* skip the { or x (}) */
292				int stype;
293				int slen = 0;
294
295				sp = strchr(sp, '\0') + 1; /* skip variable */
296				type = varsub(&x, varname, sp, &stype, &slen);
297				if (type < 0) {
298					char endc;
299					char *str, *end;
300
301					sp = varname - 2; /* restore sp */
302					end = (char *) wdscan(sp, CSUBST);
303					/* ({) the } or x is already skipped */
304					endc = *end;
305					*end = EOS;
306					str = snptreef(NULL, 64, "%S", sp);
307					*end = endc;
308					errorf("%s: bad substitution", str);
309				}
310				if (f&DOBLANK)
311					doblank++;
312				tilde_ok = 0;
313				if (word == IFS_QUOTE && type != XNULLSUB)
314					word = IFS_WORD;
315				if (type == XBASE) {	/* expand? */
316					if (!st->next) {
317						SubType *newst;
318
319						newst = alloc(
320						    sizeof(SubType), ATEMP);
321						newst->next = NULL;
322						newst->prev = st;
323						st->next = newst;
324					}
325					st = st->next;
326					st->stype = stype;
327					st->base = Xsavepos(ds, dp);
328					st->f = f;
329					st->var = varcpy(x.var);
330					st->quote = quote;
331					/* skip qualifier(s) */
332					if (stype)
333						sp += slen;
334					switch (stype & 0x7f) {
335					case '#':
336					case '%':
337						/* ! DOBLANK,DOBRACE_,DOTILDE */
338						f = DOPAT | (f&DONTRUNCOMMAND) |
339						    DOTEMP_;
340						quote = 0;
341						/* Prepend open pattern (so |
342						 * in a trim will work as
343						 * expected)
344						 */
345						*dp++ = MAGIC;
346						*dp++ = '@' + 0x80U;
347						break;
348					case '=':
349						/* Enabling tilde expansion
350						 * after :'s here is
351						 * non-standard ksh, but is
352						 * consistent with rules for
353						 * other assignments.  Not
354						 * sure what POSIX thinks of
355						 * this.
356						 * Not doing tilde expansion
357						 * for integer variables is a
358						 * non-POSIX thing - makes
359						 * sense though, since ~ is
360						 * a arithmetic operator.
361						 */
362						if (!(x.var->flag & INTEGER))
363							f |= DOASNTILDE|DOTILDE;
364						f |= DOTEMP_;
365						/* These will be done after the
366						 * value has been assigned.
367						 */
368						f &= ~(DOBLANK|DOGLOB|DOBRACE_);
369						tilde_ok = 1;
370						break;
371					case '?':
372						f &= ~DOBLANK;
373						f |= DOTEMP_;
374						/* FALLTHROUGH */
375					default:
376						/* '-' '+' '?' */
377						if (quote)
378							word = IFS_WORD;
379						else if (dp == Xstring(ds, dp))
380							word = IFS_IWS;
381						/* Enable tilde expansion */
382						tilde_ok = 1;
383						f |= DOTILDE;
384					}
385				} else
386					/* skip word */
387					sp = (char *) wdscan(sp, CSUBST);
388				continue;
389			    }
390			case CSUBST: /* only get here if expanding word */
391				sp++; /* ({) skip the } or x */
392				tilde_ok = 0;	/* in case of ${unset:-} */
393				*dp = '\0';
394				quote = st->quote;
395				f = st->f;
396				if (f&DOBLANK)
397					doblank--;
398				switch (st->stype&0x7f) {
399				case '#':
400				case '%':
401					/* Append end-pattern */
402					*dp++ = MAGIC; *dp++ = ')'; *dp = '\0';
403					dp = Xrestpos(ds, dp, st->base);
404					/* Must use st->var since calling
405					 * global would break things
406					 * like x[i+=1].
407					 */
408					x.str = trimsub(str_val(st->var),
409						dp, st->stype);
410					if (x.str[0] != '\0') {
411						word = IFS_IWS;
412						type = XSUB;
413					} else if (quote) {
414						word = IFS_WORD;
415						type = XSUB;
416					} else {
417						if (dp == Xstring(ds, dp))
418							word = IFS_IWS;
419						type = XNULLSUB;
420					}
421					if (f&DOBLANK)
422						doblank++;
423					st = st->prev;
424					continue;
425				case '=':
426					/* Restore our position and substitute
427					 * the value of st->var (may not be
428					 * the assigned value in the presence
429					 * of integer/right-adj/etc attributes).
430					 */
431					dp = Xrestpos(ds, dp, st->base);
432					/* Must use st->var since calling
433					 * global would cause with things
434					 * like x[i+=1] to be evaluated twice.
435					 */
436					/* Note: not exported by FEXPORT
437					 * in at&t ksh.
438					 */
439					/* XXX POSIX says readonly is only
440					 * fatal for special builtins (setstr
441					 * does readonly check).
442					 */
443					len = strlen(dp) + 1;
444					setstr(st->var,
445					    debunk(alloc(len, ATEMP),
446					    dp, len), KSH_UNWIND_ERROR);
447					x.str = str_val(st->var);
448					type = XSUB;
449					if (f&DOBLANK)
450						doblank++;
451					st = st->prev;
452					if (quote || !*x.str)
453						word = IFS_WORD;
454					else
455						word = IFS_IWS;
456					continue;
457				case '?':
458				    {
459					char *s = Xrestpos(ds, dp, st->base);
460
461					errorf("%s: %s", st->var->name,
462					    dp == s ?
463					    "parameter null or not set" :
464					    (debunk(s, s, strlen(s) + 1), s));
465				    }
466				}
467				st = st->prev;
468				type = XBASE;
469				continue;
470
471			case OPAT: /* open pattern: *(foo|bar) */
472				/* Next char is the type of pattern */
473				make_magic = 1;
474				c = *sp++ + 0x80;
475				break;
476
477			case SPAT: /* pattern separator (|) */
478				make_magic = 1;
479				c = '|';
480				break;
481
482			case CPAT: /* close pattern */
483				make_magic = 1;
484				c = /*(*/ ')';
485				break;
486			}
487			break;
488
489		case XNULLSUB:
490			/* Special case for "$@" (and "${foo[@]}") - no
491			 * word is generated if $# is 0 (unless there is
492			 * other stuff inside the quotes).
493			 */
494			type = XBASE;
495			if (f&DOBLANK) {
496				doblank--;
497				if (dp == Xstring(ds, dp) && word != IFS_WORD)
498					word = IFS_IWS;
499			}
500			continue;
501
502		case XSUB:
503		case XSUBMID:
504			if ((c = *x.str++) == 0) {
505				type = XBASE;
506				if (f&DOBLANK)
507					doblank--;
508				continue;
509			}
510			break;
511
512		case XARGSEP:
513			type = XARG;
514			quote = 1;
515		case XARG:
516			if ((c = *x.str++) == '\0') {
517				/* force null words to be created so
518				 * set -- '' 2 ''; foo "$@" will do
519				 * the right thing
520				 */
521				if (quote && x.split)
522					word = IFS_WORD;
523				if ((x.str = *x.u.strv++) == NULL) {
524					type = XBASE;
525					if (f&DOBLANK)
526						doblank--;
527					continue;
528				}
529				c = ifs0;
530				if (c == 0) {
531					if (quote && !x.split)
532						continue;
533					if (!quote && word == IFS_WS)
534						continue;
535					/* this is so we don't terminate */
536					c = ' ';
537					/* now force-emit a word */
538					goto emit_word;
539				}
540				if (quote && x.split) {
541					/* terminate word for "$@" */
542					type = XARGSEP;
543					quote = 0;
544				}
545			}
546			break;
547
548		case XCOM:
549			if (x.u.shf == NULL)	/* $(< ...) failed, fake EOF */
550				c = EOF;
551			else if (newlines) {		/* Spit out saved nl's */
552				c = '\n';
553				--newlines;
554			} else {
555				while ((c = shf_getc(x.u.shf)) == 0 || c == '\n')
556				    if (c == '\n')
557					    newlines++;	/* Save newlines */
558				if (newlines && c != EOF) {
559					shf_ungetc(c, x.u.shf);
560					c = '\n';
561					--newlines;
562				}
563			}
564			if (c == EOF) {
565				newlines = 0;
566				if (x.u.shf != NULL)
567					shf_close(x.u.shf);
568				if (x.split)
569					subst_exstat = waitlast();
570				else
571					subst_exstat = (x.u.shf == NULL);
572				type = XBASE;
573				if (f&DOBLANK)
574					doblank--;
575				continue;
576			}
577			break;
578		}
579
580		/* check for end of word or IFS separation */
581		if (c == 0 || (!quote && (f & DOBLANK) && doblank &&
582		    !make_magic && ctype(c, C_IFS))) {
583			/* How words are broken up:
584			 *		   |       value of c
585			 *	  word	   |	ws	nws	0
586			 *	-----------------------------------
587			 *	IFS_WORD	w/WS	w/NWS	w
588			 *	IFS_WS		-/WS	w/NWS	-
589			 *	IFS_NWS		-/NWS	w/NWS	-
590			 *	IFS_IWS		-/WS	w/NWS	-
591			 *   (w means generate a word)
592			 */
593			if ((word == IFS_WORD) || (word == IFS_QUOTE) || (c &&
594			    (word == IFS_IWS || word == IFS_NWS) &&
595			    !ctype(c, C_IFSWS))) {
596 				char *p;
597 emit_word:
598				*dp++ = '\0';
599				p = Xclose(ds, dp);
600				if (fdo & DOBRACE_)
601					/* also does globbing */
602					alt_expand(wp, p, p,
603					    p + Xlength(ds, (dp - 1)),
604					    fdo | (f & DOMARKDIRS));
605				else if (fdo & DOGLOB)
606					glob(p, wp, f & DOMARKDIRS);
607				else if ((f & DOPAT) || !(fdo & DOMAGIC_))
608					XPput(*wp, p);
609				else
610					XPput(*wp, debunk(p, p, strlen(p) + 1));
611				fdo = 0;
612				saw_eq = 0;
613				tilde_ok = (f & (DOTILDE|DOASNTILDE)) ? 1 : 0;
614				if (c != 0)
615					Xinit(ds, dp, 128, ATEMP);
616			}
617			if (c == 0)
618				goto done;
619			if (word != IFS_NWS)
620				word = ctype(c, C_IFSWS) ? IFS_WS : IFS_NWS;
621		} else {
622			if (type == XSUB) {
623				if (word == IFS_NWS &&
624				    Xlength(ds, dp) == 0) {
625					char *p;
626
627					if ((p = strdup("")) == NULL)
628						internal_errorf("unable "
629						    "to allocate memory");
630					XPput(*wp, p);
631				}
632				type = XSUBMID;
633			}
634
635			/* age tilde_ok info - ~ code tests second bit */
636			tilde_ok <<= 1;
637			/* mark any special second pass chars */
638			if (!quote)
639				switch (c) {
640				case '[':
641				case '!':
642				case '-':
643				case ']':
644					/* For character classes - doesn't hurt
645					 * to have magic !,-,]'s outside of
646					 * [...] expressions.
647					 */
648					if (f & (DOPAT | DOGLOB)) {
649						fdo |= DOMAGIC_;
650						if (c == '[')
651							fdo |= f & DOGLOB;
652						*dp++ = MAGIC;
653					}
654					break;
655				case '*':
656				case '?':
657					if (f & (DOPAT | DOGLOB)) {
658						fdo |= DOMAGIC_ | (f & DOGLOB);
659						*dp++ = MAGIC;
660					}
661					break;
662				case OBRACE:
663				case ',':
664				case CBRACE:
665					if ((f & DOBRACE_) && (c == OBRACE ||
666					    (fdo & DOBRACE_))) {
667						fdo |= DOBRACE_|DOMAGIC_;
668						*dp++ = MAGIC;
669					}
670					break;
671				case '=':
672					/* Note first unquoted = for ~ */
673					if (!(f & DOTEMP_) && !saw_eq) {
674						saw_eq = 1;
675						tilde_ok = 1;
676					}
677					break;
678				case ':': /* : */
679					/* Note unquoted : for ~ */
680					if (!(f & DOTEMP_) && (f & DOASNTILDE))
681						tilde_ok = 1;
682					break;
683				case '~':
684					/* tilde_ok is reset whenever
685					 * any of ' " $( $(( ${ } are seen.
686					 * Note that tilde_ok must be preserved
687					 * through the sequence ${A=a=}~
688					 */
689					if (type == XBASE &&
690					    (f & (DOTILDE|DOASNTILDE)) &&
691					    (tilde_ok & 2)) {
692						char *p, *dp_x;
693
694						dp_x = dp;
695						p = maybe_expand_tilde(sp,
696						    &ds, &dp_x,
697						    f & DOASNTILDE);
698						if (p) {
699							if (dp != dp_x)
700								word = IFS_WORD;
701							dp = dp_x;
702							sp = p;
703							continue;
704						}
705					}
706					break;
707				}
708			else
709				quote &= ~2; /* undo temporary */
710
711			if (make_magic) {
712				make_magic = 0;
713				fdo |= DOMAGIC_ | (f & DOGLOB);
714				*dp++ = MAGIC;
715			} else if (ISMAGIC(c)) {
716				fdo |= DOMAGIC_;
717				*dp++ = MAGIC;
718			}
719			*dp++ = c; /* save output char */
720			word = IFS_WORD;
721		}
722	}
723
724done:
725	for (st = &st_head; st != NULL; st = st->next) {
726		if (st->var == NULL || (st->var->flag & RDONLY) == 0)
727			continue;
728
729		afree(st->var, ATEMP);
730	}
731}
732
733/*
734 * Prepare to generate the string returned by ${} substitution.
735 */
736static int
737varsub(Expand *xp, char *sp, char *word,
738    int *stypep,	/* becomes qualifier type */
739    int *slenp)		/* " " len (=, :=, etc.) valid iff *stypep != 0 */
740{
741	int c;
742	int state;	/* next state: XBASE, XARG, XSUB, XNULLSUB */
743	int stype;	/* substitution type */
744	int slen;
745	char *p;
746	struct tbl *vp;
747	int zero_ok = 0;
748
749	if (sp[0] == '\0')	/* Bad variable name */
750		return -1;
751
752	xp->var = NULL;
753
754	/* ${#var}, string length or array size */
755	if (sp[0] == '#' && (c = sp[1]) != '\0') {
756		/* Can't have any modifiers for ${#...} */
757		if (*word != CSUBST)
758			return -1;
759		sp++;
760		/* Check for size of array */
761		if ((p=strchr(sp,'[')) && (p[1]=='*'||p[1]=='@') && p[2]==']') {
762			int n = 0;
763
764			vp = global(arrayname(sp));
765			if (vp->flag & (ISSET|ARRAY))
766				zero_ok = 1;
767			for (; vp; vp = vp->u.array)
768				if (vp->flag & ISSET)
769					n++;
770			c = n; /* ksh88/ksh93 go for number, not max index */
771		} else if (c == '*' || c == '@')
772			c = genv->loc->argc;
773		else {
774			p = str_val(global(sp));
775			zero_ok = p != null;
776			c = strlen(p);
777		}
778		if (Flag(FNOUNSET) && c == 0 && !zero_ok)
779			errorf("%s: parameter not set", sp);
780		*stypep = 0; /* unqualified variable/string substitution */
781		xp->str = str_save(u64ton((uint64_t)c, 10), ATEMP);
782		return XSUB;
783	}
784
785	/* Check for qualifiers in word part */
786	stype = 0;
787	c = word[slen = 0] == CHAR ? word[1] : 0;
788	if (c == ':') {
789		slen += 2;
790		stype = 0x80;
791		c = word[slen + 0] == CHAR ? word[slen + 1] : 0;
792	}
793	if (ctype(c, C_SUBOP1)) {
794		slen += 2;
795		stype |= c;
796	} else if (ctype(c, C_SUBOP2)) { /* Note: ksh88 allows :%, :%%, etc */
797		slen += 2;
798		stype = c;
799		if (word[slen + 0] == CHAR && c == word[slen + 1]) {
800			stype |= 0x80;
801			slen += 2;
802		}
803	} else if (stype)	/* : is not ok */
804		return -1;
805	if (!stype && *word != CSUBST)
806		return -1;
807	*stypep = stype;
808	*slenp = slen;
809
810	c = sp[0];
811	if (c == '*' || c == '@') {
812		switch (stype & 0x7f) {
813		case '=':	/* can't assign to a vector */
814		case '%':	/* can't trim a vector (yet) */
815		case '#':
816			return -1;
817		}
818		if (genv->loc->argc == 0) {
819			xp->str = null;
820			xp->var = global(sp);
821			state = c == '@' ? XNULLSUB : XSUB;
822		} else {
823			xp->u.strv = (const char **) genv->loc->argv + 1;
824			xp->str = *xp->u.strv++;
825			xp->split = c == '@'; /* $@ */
826			state = XARG;
827		}
828		zero_ok = 1;	/* exempt "$@" and "$*" from 'set -u' */
829	} else {
830		if ((p=strchr(sp,'[')) && (p[1]=='*'||p[1]=='@') && p[2]==']') {
831			XPtrV wv;
832
833			switch (stype & 0x7f) {
834			case '=':	/* can't assign to a vector */
835			case '%':	/* can't trim a vector (yet) */
836			case '#':
837			case '?':
838				return -1;
839			}
840			XPinit(wv, 32);
841			vp = global(arrayname(sp));
842			for (; vp; vp = vp->u.array) {
843				if (!(vp->flag&ISSET))
844					continue;
845				XPput(wv, str_val(vp));
846			}
847			if (XPsize(wv) == 0) {
848				xp->str = null;
849				state = p[1] == '@' ? XNULLSUB : XSUB;
850				XPfree(wv);
851			} else {
852				XPput(wv, 0);
853				xp->u.strv = (const char **) XPptrv(wv);
854				xp->str = *xp->u.strv++;
855				xp->split = p[1] == '@'; /* ${foo[@]} */
856				state = XARG;
857			}
858		} else {
859			/* Can't assign things like $! or $1 */
860			if ((stype & 0x7f) == '=' &&
861			    (ctype(*sp, C_VAR1) || digit(*sp)))
862				return -1;
863			xp->var = global(sp);
864			xp->str = str_val(xp->var);
865			state = XSUB;
866		}
867	}
868
869	c = stype&0x7f;
870	/* test the compiler's code generator */
871	if (ctype(c, C_SUBOP2) ||
872	    (((stype&0x80) ? *xp->str=='\0' : xp->str==null) ? /* undef? */
873	    c == '=' || c == '-' || c == '?' : c == '+'))
874		state = XBASE;	/* expand word instead of variable value */
875	if (Flag(FNOUNSET) && xp->str == null && !zero_ok &&
876	    (ctype(c, C_SUBOP2) || (state != XBASE && c != '+')))
877		errorf("%s: parameter not set", sp);
878	return state;
879}
880
881/*
882 * Run the command in $(...) and read its output.
883 */
884static int
885comsub(Expand *xp, char *cp)
886{
887	Source *s, *sold;
888	struct op *t;
889	struct shf *shf;
890
891	s = pushs(SSTRING, ATEMP);
892	s->start = s->str = cp;
893	sold = source;
894	t = compile(s);
895	afree(s, ATEMP);
896	source = sold;
897
898	if (t == NULL)
899		return XBASE;
900
901	if (t != NULL && t->type == TCOM && /* $(<file) */
902	    *t->args == NULL && *t->vars == NULL && t->ioact != NULL) {
903		struct ioword *io = *t->ioact;
904		char *name;
905
906		if ((io->flag&IOTYPE) != IOREAD)
907			errorf("funny $() command: %s",
908			    snptreef(NULL, 32, "%R", io));
909		shf = shf_open(name = evalstr(io->name, DOTILDE), O_RDONLY, 0,
910			SHF_MAPHI|SHF_CLEXEC);
911		if (shf == NULL)
912			warningf(!Flag(FTALKING),
913			    "%s: %s", name, strerror(errno));
914		xp->split = 0;	/* no waitlast() */
915	} else {
916		int ofd1, pv[2];
917		openpipe(pv);
918		shf = shf_fdopen(pv[0], SHF_RD, NULL);
919		ofd1 = savefd(1);
920		if (pv[1] != 1) {
921			ksh_dup2(pv[1], 1, false);
922			close(pv[1]);
923		}
924		execute(t, XFORK|XXCOM|XPIPEO, NULL);
925		restfd(1, ofd1);
926		startlast();
927		xp->split = 1;	/* waitlast() */
928	}
929
930	xp->u.shf = shf;
931	return XCOM;
932}
933
934/*
935 * perform #pattern and %pattern substitution in ${}
936 */
937
938static char *
939trimsub(char *str, char *pat, int how)
940{
941	char *end = strchr(str, 0);
942	char *p, c;
943
944	switch (how&0xff) {	/* UCHAR_MAX maybe? */
945	case '#':		/* shortest at beginning */
946		for (p = str; p <= end; p++) {
947			c = *p; *p = '\0';
948			if (gmatch(str, pat, false)) {
949				*p = c;
950				return p;
951			}
952			*p = c;
953		}
954		break;
955	case '#'|0x80:	/* longest match at beginning */
956		for (p = end; p >= str; p--) {
957			c = *p; *p = '\0';
958			if (gmatch(str, pat, false)) {
959				*p = c;
960				return p;
961			}
962			*p = c;
963		}
964		break;
965	case '%':		/* shortest match at end */
966		for (p = end; p >= str; p--) {
967			if (gmatch(p, pat, false))
968				return str_nsave(str, p - str, ATEMP);
969		}
970		break;
971	case '%'|0x80:	/* longest match at end */
972		for (p = str; p <= end; p++) {
973			if (gmatch(p, pat, false))
974				return str_nsave(str, p - str, ATEMP);
975		}
976		break;
977	}
978
979	return str;		/* no match, return string */
980}
981
982/*
983 * glob
984 * Name derived from V6's /etc/glob, the program that expanded filenames.
985 */
986
987/* XXX cp not const 'cause slashes are temporarily replaced with nulls... */
988static void
989glob(char *cp, XPtrV *wp, int markdirs)
990{
991	int oldsize = XPsize(*wp);
992
993	if (glob_str(cp, wp, markdirs) == 0)
994		XPput(*wp, debunk(cp, cp, strlen(cp) + 1));
995	else
996		qsortp(XPptrv(*wp) + oldsize, (size_t)(XPsize(*wp) - oldsize),
997			xstrcmp);
998}
999
1000#define GF_NONE		0
1001#define GF_EXCHECK	BIT(0)		/* do existence check on file */
1002#define GF_GLOBBED	BIT(1)		/* some globbing has been done */
1003#define GF_MARKDIR	BIT(2)		/* add trailing / to directories */
1004
1005/* Apply file globbing to cp and store the matching files in wp.  Returns
1006 * the number of matches found.
1007 */
1008int
1009glob_str(char *cp, XPtrV *wp, int markdirs)
1010{
1011	int oldsize = XPsize(*wp);
1012	XString xs;
1013	char *xp;
1014
1015	Xinit(xs, xp, 256, ATEMP);
1016	globit(&xs, &xp, cp, wp, markdirs ? GF_MARKDIR : GF_NONE);
1017	Xfree(xs, xp);
1018
1019	return XPsize(*wp) - oldsize;
1020}
1021
1022static void
1023globit(XString *xs,	/* dest string */
1024    char **xpp,		/* ptr to dest end */
1025    char *sp,		/* source path */
1026    XPtrV *wp,		/* output list */
1027    int check)		/* GF_* flags */
1028{
1029	char *np;		/* next source component */
1030	char *xp = *xpp;
1031	char *se;
1032	char odirsep;
1033
1034	/* This to allow long expansions to be interrupted */
1035	intrcheck();
1036
1037	if (sp == NULL) {	/* end of source path */
1038		/* We only need to check if the file exists if a pattern
1039		 * is followed by a non-pattern (eg, foo*x/bar; no check
1040		 * is needed for foo* since the match must exist) or if
1041		 * any patterns were expanded and the markdirs option is set.
1042		 * Symlinks make things a bit tricky...
1043		 */
1044		if ((check & GF_EXCHECK) ||
1045		    ((check & GF_MARKDIR) && (check & GF_GLOBBED))) {
1046#define stat_check()	(stat_done ? stat_done : \
1047			    (stat_done = stat(Xstring(*xs, xp), &statb) == -1 \
1048				? -1 : 1))
1049			struct stat lstatb, statb;
1050			int stat_done = 0;	 /* -1: failed, 1 ok */
1051
1052			if (lstat(Xstring(*xs, xp), &lstatb) == -1)
1053				return;
1054			/* special case for systems which strip trailing
1055			 * slashes from regular files (eg, /etc/passwd/).
1056			 * SunOS 4.1.3 does this...
1057			 */
1058			if ((check & GF_EXCHECK) && xp > Xstring(*xs, xp) &&
1059			    xp[-1] == '/' && !S_ISDIR(lstatb.st_mode) &&
1060			    (!S_ISLNK(lstatb.st_mode) ||
1061			    stat_check() < 0 || !S_ISDIR(statb.st_mode)))
1062				return;
1063			/* Possibly tack on a trailing / if there isn't already
1064			 * one and if the file is a directory or a symlink to a
1065			 * directory
1066			 */
1067			if (((check & GF_MARKDIR) && (check & GF_GLOBBED)) &&
1068			    xp > Xstring(*xs, xp) && xp[-1] != '/' &&
1069			    (S_ISDIR(lstatb.st_mode) ||
1070			    (S_ISLNK(lstatb.st_mode) && stat_check() > 0 &&
1071			    S_ISDIR(statb.st_mode)))) {
1072				*xp++ = '/';
1073				*xp = '\0';
1074			}
1075		}
1076		XPput(*wp, str_nsave(Xstring(*xs, xp), Xlength(*xs, xp), ATEMP));
1077		return;
1078	}
1079
1080	if (xp > Xstring(*xs, xp))
1081		*xp++ = '/';
1082	while (*sp == '/') {
1083		Xcheck(*xs, xp);
1084		*xp++ = *sp++;
1085	}
1086	np = strchr(sp, '/');
1087	if (np != NULL) {
1088		se = np;
1089		odirsep = *np;	/* don't assume '/', can be multiple kinds */
1090		*np++ = '\0';
1091	} else {
1092		odirsep = '\0'; /* keep gcc quiet */
1093		se = sp + strlen(sp);
1094	}
1095
1096
1097	/* Check if sp needs globbing - done to avoid pattern checks for strings
1098	 * containing MAGIC characters, open ['s without the matching close ],
1099	 * etc. (otherwise opendir() will be called which may fail because the
1100	 * directory isn't readable - if no globbing is needed, only execute
1101	 * permission should be required (as per POSIX)).
1102	 */
1103	if (!has_globbing(sp, se)) {
1104		XcheckN(*xs, xp, se - sp + 1);
1105		debunk(xp, sp, Xnleft(*xs, xp));
1106		xp += strlen(xp);
1107		*xpp = xp;
1108		globit(xs, xpp, np, wp, check);
1109	} else {
1110		DIR *dirp;
1111		struct dirent *d;
1112		char *name;
1113		int len;
1114		int prefix_len;
1115
1116		*xp = '\0';
1117		prefix_len = Xlength(*xs, xp);
1118		dirp = opendir(prefix_len ? Xstring(*xs, xp) : ".");
1119		if (dirp == NULL)
1120			goto Nodir;
1121		while ((d = readdir(dirp)) != NULL) {
1122			name = d->d_name;
1123			if (name[0] == '.' &&
1124			    (name[1] == 0 || (name[1] == '.' && name[2] == 0)))
1125				continue; /* always ignore . and .. */
1126			if ((*name == '.' && *sp != '.') ||
1127			    !gmatch(name, sp, true))
1128				continue;
1129
1130			len = strlen(d->d_name) + 1;
1131			XcheckN(*xs, xp, len);
1132			memcpy(xp, name, len);
1133			*xpp = xp + len - 1;
1134			globit(xs, xpp, np, wp,
1135				(check & GF_MARKDIR) | GF_GLOBBED
1136				| (np ? GF_EXCHECK : GF_NONE));
1137			xp = Xstring(*xs, xp) + prefix_len;
1138		}
1139		closedir(dirp);
1140	  Nodir:;
1141	}
1142
1143	if (np != NULL)
1144		*--np = odirsep;
1145}
1146
1147/* remove MAGIC from string */
1148char *
1149debunk(char *dp, const char *sp, size_t dlen)
1150{
1151	char *d, *s;
1152
1153	if ((s = strchr(sp, MAGIC))) {
1154		size_t slen = s - sp;
1155		if (slen >= dlen)
1156			return dp;
1157		memcpy(dp, sp, slen);
1158		for (d = dp + slen; *s && (d < dp + dlen); s++)
1159			if (!ISMAGIC(*s) || !(*++s & 0x80) ||
1160			    !strchr("*+?@! ", *s & 0x7f))
1161				*d++ = *s;
1162			else {
1163				/* extended pattern operators: *+?@! */
1164				if ((*s & 0x7f) != ' ')
1165					*d++ = *s & 0x7f;
1166				if (d < dp + dlen)
1167					*d++ = '(';
1168			}
1169		*d = '\0';
1170	} else if (dp != sp)
1171		strlcpy(dp, sp, dlen);
1172	return dp;
1173}
1174
1175/* Check if p is an unquoted name, possibly followed by a / or :.  If so
1176 * puts the expanded version in *dcp,dp and returns a pointer in p just
1177 * past the name, otherwise returns 0.
1178 */
1179static char *
1180maybe_expand_tilde(char *p, XString *dsp, char **dpp, int isassign)
1181{
1182	XString ts;
1183	char *dp = *dpp;
1184	char *tp, *r;
1185
1186	Xinit(ts, tp, 16, ATEMP);
1187	/* : only for DOASNTILDE form */
1188	while (p[0] == CHAR && p[1] != '/' && (!isassign || p[1] != ':'))
1189	{
1190		Xcheck(ts, tp);
1191		*tp++ = p[1];
1192		p += 2;
1193	}
1194	*tp = '\0';
1195	r = (p[0] == EOS || p[0] == CHAR || p[0] == CSUBST) ?
1196	    tilde(Xstring(ts, tp)) : NULL;
1197	Xfree(ts, tp);
1198	if (r) {
1199		while (*r) {
1200			Xcheck(*dsp, dp);
1201			if (ISMAGIC(*r))
1202				*dp++ = MAGIC;
1203			*dp++ = *r++;
1204		}
1205		*dpp = dp;
1206		r = p;
1207	}
1208	return r;
1209}
1210
1211/*
1212 * tilde expansion
1213 *
1214 * based on a version by Arnold Robbins
1215 */
1216
1217static char *
1218tilde(char *cp)
1219{
1220	char *dp;
1221
1222	if (cp[0] == '\0')
1223		dp = str_val(global("HOME"));
1224	else if (cp[0] == '+' && cp[1] == '\0')
1225		dp = str_val(global("PWD"));
1226	else if (cp[0] == '-' && cp[1] == '\0')
1227		dp = str_val(global("OLDPWD"));
1228	else
1229		dp = homedir(cp);
1230	/* If HOME, PWD or OLDPWD are not set, don't expand ~ */
1231	if (dp == null)
1232		dp = NULL;
1233	return dp;
1234}
1235
1236/*
1237 * map userid to user's home directory.
1238 * note that 4.3's getpw adds more than 6K to the shell,
1239 * and the YP version probably adds much more.
1240 * we might consider our own version of getpwnam() to keep the size down.
1241 */
1242
1243static char *
1244homedir(char *name)
1245{
1246	struct tbl *ap;
1247
1248	ap = ktenter(&homedirs, name, hash(name));
1249	if (!(ap->flag & ISSET)) {
1250		struct passwd *pw;
1251
1252		pw = getpwnam(name);
1253		if (pw == NULL)
1254			return NULL;
1255		ap->val.s = str_save(pw->pw_dir, APERM);
1256		ap->flag |= DEFINED|ISSET|ALLOC;
1257	}
1258	return ap->val.s;
1259}
1260
1261static void
1262alt_expand(XPtrV *wp, char *start, char *exp_start, char *end, int fdo)
1263{
1264	int count = 0;
1265	char *brace_start, *brace_end, *comma = NULL;
1266	char *field_start;
1267	char *p;
1268
1269	/* search for open brace */
1270	for (p = exp_start; (p = strchr(p, MAGIC)) && p[1] != OBRACE; p += 2)
1271		;
1272	brace_start = p;
1273
1274	/* find matching close brace, if any */
1275	if (p) {
1276		comma = NULL;
1277		count = 1;
1278		for (p += 2; *p && count; p++) {
1279			if (ISMAGIC(*p)) {
1280				if (*++p == OBRACE)
1281					count++;
1282				else if (*p == CBRACE)
1283					--count;
1284				else if (*p == ',' && count == 1)
1285					comma = p;
1286			}
1287		}
1288	}
1289	/* no valid expansions... */
1290	if (!p || count != 0) {
1291		/* Note that given a{{b,c} we do not expand anything (this is
1292		 * what at&t ksh does.  This may be changed to do the {b,c}
1293		 * expansion. }
1294		 */
1295		if (fdo & DOGLOB)
1296			glob(start, wp, fdo & DOMARKDIRS);
1297		else
1298			XPput(*wp, debunk(start, start, end - start));
1299		return;
1300	}
1301	brace_end = p;
1302	if (!comma) {
1303		alt_expand(wp, start, brace_end, end, fdo);
1304		return;
1305	}
1306
1307	/* expand expression */
1308	field_start = brace_start + 2;
1309	count = 1;
1310	for (p = brace_start + 2; p != brace_end; p++) {
1311		if (ISMAGIC(*p)) {
1312			if (*++p == OBRACE)
1313				count++;
1314			else if ((*p == CBRACE && --count == 0) ||
1315			    (*p == ',' && count == 1)) {
1316				char *new;
1317				int l1, l2, l3;
1318
1319				l1 = brace_start - start;
1320				l2 = (p - 1) - field_start;
1321				l3 = end - brace_end;
1322				new = alloc(l1 + l2 + l3 + 1, ATEMP);
1323				memcpy(new, start, l1);
1324				memcpy(new + l1, field_start, l2);
1325				memcpy(new + l1 + l2, brace_end, l3);
1326				new[l1 + l2 + l3] = '\0';
1327				alt_expand(wp, new, new + l1,
1328				    new + l1 + l2 + l3, fdo);
1329				field_start = p + 1;
1330			}
1331		}
1332	}
1333	return;
1334}
1335
1336/*
1337 * Copy the given variable if it's flagged as read-only.
1338 * Such variables have static storage and only one can therefore be referenced
1339 * at a time.
1340 * This is necessary in order to allow variable expansion expressions to refer
1341 * to multiple read-only variables.
1342 */
1343static struct tbl *
1344varcpy(struct tbl *vp)
1345{
1346	struct tbl *cpy;
1347
1348	if (vp == NULL || (vp->flag & RDONLY) == 0)
1349		return vp;
1350
1351	cpy = alloc(sizeof(struct tbl), ATEMP);
1352	memcpy(cpy, vp, sizeof(struct tbl));
1353	return cpy;
1354}
1355