1/*	$NetBSD: expand.c,v 1.86.4.1 2013/02/02 15:43:27 sborrill Exp $	*/
2
3/*-
4 * Copyright (c) 1991, 1993
5 *	The Regents of the University of California.  All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Kenneth Almquist.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 *    notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of the University nor the names of its contributors
19 *    may be used to endorse or promote products derived from this software
20 *    without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 */
34
35#include <sys/cdefs.h>
36#ifndef lint
37#if 0
38static char sccsid[] = "@(#)expand.c	8.5 (Berkeley) 5/15/95";
39#else
40__RCSID("$NetBSD: expand.c,v 1.86.4.1 2013/02/02 15:43:27 sborrill Exp $");
41#endif
42#endif /* not lint */
43
44#include <sys/types.h>
45#include <sys/time.h>
46#include <sys/stat.h>
47#include <errno.h>
48#include <dirent.h>
49#include <unistd.h>
50#include <pwd.h>
51#include <stdlib.h>
52#include <stdio.h>
53
54/*
55 * Routines to expand arguments to commands.  We have to deal with
56 * backquotes, shell variables, and file metacharacters.
57 */
58
59#include "shell.h"
60#include "main.h"
61#include "nodes.h"
62#include "eval.h"
63#include "expand.h"
64#include "syntax.h"
65#include "parser.h"
66#include "jobs.h"
67#include "options.h"
68#include "builtins.h"
69#include "var.h"
70#include "input.h"
71#include "output.h"
72#include "memalloc.h"
73#include "error.h"
74#include "mystring.h"
75#include "show.h"
76
77/*
78 * Structure specifying which parts of the string should be searched
79 * for IFS characters.
80 */
81
82struct ifsregion {
83	struct ifsregion *next;	/* next region in list */
84	int begoff;		/* offset of start of region */
85	int endoff;		/* offset of end of region */
86	int inquotes;		/* search for nul bytes only */
87};
88
89
90char *expdest;			/* output of current string */
91struct nodelist *argbackq;	/* list of back quote expressions */
92struct ifsregion ifsfirst;	/* first struct in list of ifs regions */
93struct ifsregion *ifslastp;	/* last struct in list */
94struct arglist exparg;		/* holds expanded arg list */
95
96STATIC void argstr(char *, int);
97STATIC char *exptilde(char *, int);
98STATIC void expbackq(union node *, int, int);
99STATIC int subevalvar(char *, char *, int, int, int, int);
100STATIC char *evalvar(char *, int);
101STATIC int varisset(char *, int);
102STATIC void varvalue(char *, int, int, int);
103STATIC void recordregion(int, int, int);
104STATIC void removerecordregions(int);
105STATIC void ifsbreakup(char *, struct arglist *);
106STATIC void ifsfree(void);
107STATIC void expandmeta(struct strlist *, int);
108STATIC void expmeta(char *, char *);
109STATIC void addfname(char *);
110STATIC struct strlist *expsort(struct strlist *);
111STATIC struct strlist *msort(struct strlist *, int);
112STATIC int pmatch(char *, char *, int);
113STATIC char *cvtnum(int, char *);
114
115/*
116 * Expand shell variables and backquotes inside a here document.
117 */
118
119void
120expandhere(union node *arg, int fd)
121{
122	herefd = fd;
123	expandarg(arg, NULL, 0);
124	xwrite(fd, stackblock(), expdest - stackblock());
125}
126
127
128/*
129 * Perform variable substitution and command substitution on an argument,
130 * placing the resulting list of arguments in arglist.  If EXP_FULL is true,
131 * perform splitting and file name expansion.  When arglist is NULL, perform
132 * here document expansion.
133 */
134
135void
136expandarg(union node *arg, struct arglist *arglist, int flag)
137{
138	struct strlist *sp;
139	char *p;
140
141	argbackq = arg->narg.backquote;
142	STARTSTACKSTR(expdest);
143	ifsfirst.next = NULL;
144	ifslastp = NULL;
145	argstr(arg->narg.text, flag);
146	if (arglist == NULL) {
147		return;			/* here document expanded */
148	}
149	STPUTC('\0', expdest);
150	p = grabstackstr(expdest);
151	exparg.lastp = &exparg.list;
152	/*
153	 * TODO - EXP_REDIR
154	 */
155	if (flag & EXP_FULL) {
156		ifsbreakup(p, &exparg);
157		*exparg.lastp = NULL;
158		exparg.lastp = &exparg.list;
159		expandmeta(exparg.list, flag);
160	} else {
161		if (flag & EXP_REDIR) /*XXX - for now, just remove escapes */
162			rmescapes(p);
163		sp = (struct strlist *)stalloc(sizeof (struct strlist));
164		sp->text = p;
165		*exparg.lastp = sp;
166		exparg.lastp = &sp->next;
167	}
168	ifsfree();
169	*exparg.lastp = NULL;
170	if (exparg.list) {
171		*arglist->lastp = exparg.list;
172		arglist->lastp = exparg.lastp;
173	}
174}
175
176
177
178/*
179 * Perform variable and command substitution.
180 * If EXP_FULL is set, output CTLESC characters to allow for further processing.
181 * Otherwise treat $@ like $* since no splitting will be performed.
182 */
183
184STATIC void
185argstr(char *p, int flag)
186{
187	char c;
188	int quotes = flag & (EXP_FULL | EXP_CASE);	/* do CTLESC */
189	int firsteq = 1;
190	const char *ifs = NULL;
191	int ifs_split = EXP_IFS_SPLIT;
192
193	if (flag & EXP_IFS_SPLIT)
194		ifs = ifsset() ? ifsval() : " \t\n";
195
196	if (*p == '~' && (flag & (EXP_TILDE | EXP_VARTILDE)))
197		p = exptilde(p, flag);
198	for (;;) {
199		switch (c = *p++) {
200		case '\0':
201		case CTLENDVAR: /* end of expanding yyy in ${xxx-yyy} */
202			return;
203		case CTLQUOTEMARK:
204			/* "$@" syntax adherence hack */
205			if (p[0] == CTLVAR && p[2] == '@' && p[3] == '=')
206				break;
207			if ((flag & EXP_FULL) != 0)
208				STPUTC(c, expdest);
209			ifs_split = 0;
210			break;
211		case CTLQUOTEEND:
212			ifs_split = EXP_IFS_SPLIT;
213			break;
214		case CTLESC:
215			if (quotes)
216				STPUTC(c, expdest);
217			c = *p++;
218			STPUTC(c, expdest);
219			break;
220		case CTLVAR:
221			p = evalvar(p, (flag & ~EXP_IFS_SPLIT) | (flag & ifs_split));
222			break;
223		case CTLBACKQ:
224		case CTLBACKQ|CTLQUOTE:
225			expbackq(argbackq->n, c & CTLQUOTE, flag);
226			argbackq = argbackq->next;
227			break;
228		case CTLENDARI:
229			expari(flag);
230			break;
231		case ':':
232		case '=':
233			/*
234			 * sort of a hack - expand tildes in variable
235			 * assignments (after the first '=' and after ':'s).
236			 */
237			STPUTC(c, expdest);
238			if (flag & EXP_VARTILDE && *p == '~') {
239				if (c == '=') {
240					if (firsteq)
241						firsteq = 0;
242					else
243						break;
244				}
245				p = exptilde(p, flag);
246			}
247			break;
248		default:
249			STPUTC(c, expdest);
250			if (flag & ifs_split && strchr(ifs, c) != NULL) {
251				/* We need to get the output split here... */
252				recordregion(expdest - stackblock() - 1,
253						expdest - stackblock(), 0);
254			}
255			break;
256		}
257	}
258}
259
260STATIC char *
261exptilde(char *p, int flag)
262{
263	char c, *startp = p;
264	struct passwd *pw;
265	const char *home;
266	int quotes = flag & (EXP_FULL | EXP_CASE);
267
268	while ((c = *p) != '\0') {
269		switch(c) {
270		case CTLESC:
271			return (startp);
272		case CTLQUOTEMARK:
273			return (startp);
274		case ':':
275			if (flag & EXP_VARTILDE)
276				goto done;
277			break;
278		case '/':
279			goto done;
280		}
281		p++;
282	}
283done:
284	*p = '\0';
285	if (*(startp+1) == '\0') {
286		if ((home = lookupvar("HOME")) == NULL)
287			goto lose;
288	} else {
289		if ((pw = getpwnam(startp+1)) == NULL)
290			goto lose;
291		home = pw->pw_dir;
292	}
293	if (*home == '\0')
294		goto lose;
295	*p = c;
296	while ((c = *home++) != '\0') {
297		if (quotes && SQSYNTAX[(int)c] == CCTL)
298			STPUTC(CTLESC, expdest);
299		STPUTC(c, expdest);
300	}
301	return (p);
302lose:
303	*p = c;
304	return (startp);
305}
306
307
308STATIC void
309removerecordregions(int endoff)
310{
311	if (ifslastp == NULL)
312		return;
313
314	if (ifsfirst.endoff > endoff) {
315		while (ifsfirst.next != NULL) {
316			struct ifsregion *ifsp;
317			INTOFF;
318			ifsp = ifsfirst.next->next;
319			ckfree(ifsfirst.next);
320			ifsfirst.next = ifsp;
321			INTON;
322		}
323		if (ifsfirst.begoff > endoff)
324			ifslastp = NULL;
325		else {
326			ifslastp = &ifsfirst;
327			ifsfirst.endoff = endoff;
328		}
329		return;
330	}
331
332	ifslastp = &ifsfirst;
333	while (ifslastp->next && ifslastp->next->begoff < endoff)
334		ifslastp=ifslastp->next;
335	while (ifslastp->next != NULL) {
336		struct ifsregion *ifsp;
337		INTOFF;
338		ifsp = ifslastp->next->next;
339		ckfree(ifslastp->next);
340		ifslastp->next = ifsp;
341		INTON;
342	}
343	if (ifslastp->endoff > endoff)
344		ifslastp->endoff = endoff;
345}
346
347
348/*
349 * Expand arithmetic expression.  Backup to start of expression,
350 * evaluate, place result in (backed up) result, adjust string position.
351 */
352void
353expari(int flag)
354{
355	char *p, *start;
356	intmax_t result;
357	int adjustment;
358	int begoff;
359	int quotes = flag & (EXP_FULL | EXP_CASE);
360	int quoted;
361
362	/*	ifsfree(); */
363
364	/*
365	 * This routine is slightly over-complicated for
366	 * efficiency.  First we make sure there is
367	 * enough space for the result, which may be bigger
368	 * than the expression if we add exponentation.  Next we
369	 * scan backwards looking for the start of arithmetic.  If the
370	 * next previous character is a CTLESC character, then we
371	 * have to rescan starting from the beginning since CTLESC
372	 * characters have to be processed left to right.
373	 */
374/* SPACE_NEEDED is enough for all digits, plus possible "-", plus 2 (why?) */
375#define SPACE_NEEDED ((sizeof(intmax_t) * CHAR_BIT + 2) / 3 + 1 + 2)
376	CHECKSTRSPACE((int)(SPACE_NEEDED - 2), expdest);
377	USTPUTC('\0', expdest);
378	start = stackblock();
379	p = expdest - 1;
380	while (*p != CTLARI && p >= start)
381		--p;
382	if (*p != CTLARI)
383		error("missing CTLARI (shouldn't happen)");
384	if (p > start && *(p-1) == CTLESC)
385		for (p = start; *p != CTLARI; p++)
386			if (*p == CTLESC)
387				p++;
388
389	if (p[1] == '"')
390		quoted=1;
391	else
392		quoted=0;
393	begoff = p - start;
394	removerecordregions(begoff);
395	if (quotes)
396		rmescapes(p+2);
397	result = arith(p+2);
398	fmtstr(p, SPACE_NEEDED, "%"PRIdMAX, result);
399
400	while (*p++)
401		;
402
403	if (quoted == 0)
404		recordregion(begoff, p - 1 - start, 0);
405	adjustment = expdest - p + 1;
406	STADJUST(-adjustment, expdest);
407}
408
409
410/*
411 * Expand stuff in backwards quotes.
412 */
413
414STATIC void
415expbackq(union node *cmd, int quoted, int flag)
416{
417	struct backcmd in;
418	int i;
419	char buf[128];
420	char *p;
421	char *dest = expdest;
422	struct ifsregion saveifs, *savelastp;
423	struct nodelist *saveargbackq;
424	char lastc;
425	int startloc = dest - stackblock();
426	char const *syntax = quoted? DQSYNTAX : BASESYNTAX;
427	int saveherefd;
428	int quotes = flag & (EXP_FULL | EXP_CASE);
429	int nnl;
430
431	INTOFF;
432	saveifs = ifsfirst;
433	savelastp = ifslastp;
434	saveargbackq = argbackq;
435	saveherefd = herefd;
436	herefd = -1;
437	p = grabstackstr(dest);
438	evalbackcmd(cmd, &in);
439	ungrabstackstr(p, dest);
440	ifsfirst = saveifs;
441	ifslastp = savelastp;
442	argbackq = saveargbackq;
443	herefd = saveherefd;
444
445	p = in.buf;
446	lastc = '\0';
447	nnl = 0;
448	for (;;) {
449		if (--in.nleft < 0) {
450			if (in.fd < 0)
451				break;
452			while ((i = read(in.fd, buf, sizeof buf)) < 0 && errno == EINTR);
453			TRACE(("expbackq: read returns %d\n", i));
454			if (i <= 0)
455				break;
456			p = buf;
457			in.nleft = i - 1;
458		}
459		lastc = *p++;
460		if (lastc != '\0') {
461			if (lastc == '\n')
462				nnl++;
463			else {
464				CHECKSTRSPACE(nnl + 2, dest);
465				while (nnl > 0) {
466					nnl--;
467					USTPUTC('\n', dest);
468				}
469				if (quotes && syntax[(int)lastc] == CCTL)
470					USTPUTC(CTLESC, dest);
471				USTPUTC(lastc, dest);
472			}
473		}
474	}
475
476	if (in.fd >= 0)
477		close(in.fd);
478	if (in.buf)
479		ckfree(in.buf);
480	if (in.jp)
481		back_exitstatus = waitforjob(in.jp);
482	if (quoted == 0)
483		recordregion(startloc, dest - stackblock(), 0);
484	TRACE(("evalbackq: size=%d: \"%.*s\"\n",
485		(int)((dest - stackblock()) - startloc),
486		(int)((dest - stackblock()) - startloc),
487		stackblock() + startloc));
488	expdest = dest;
489	INTON;
490}
491
492
493
494STATIC int
495subevalvar(char *p, char *str, int strloc, int subtype, int startloc, int varflags)
496{
497	char *startp;
498	char *loc = NULL;
499	char *q;
500	int c = 0;
501	int saveherefd = herefd;
502	struct nodelist *saveargbackq = argbackq;
503	int amount, how;
504
505	herefd = -1;
506	switch (subtype) {
507	case VSTRIMLEFT:
508	case VSTRIMLEFTMAX:
509	case VSTRIMRIGHT:
510	case VSTRIMRIGHTMAX:
511		how = (varflags & VSQUOTE) ? 0 : EXP_CASE;
512		break;
513	default:
514		how = 0;
515		break;
516	}
517	argstr(p, how);
518	STACKSTRNUL(expdest);
519	herefd = saveherefd;
520	argbackq = saveargbackq;
521	startp = stackblock() + startloc;
522	if (str == NULL)
523	    str = stackblock() + strloc;
524
525	switch (subtype) {
526	case VSASSIGN:
527		setvar(str, startp, 0);
528		amount = startp - expdest;
529		STADJUST(amount, expdest);
530		varflags &= ~VSNUL;
531		return 1;
532
533	case VSQUESTION:
534		if (*p != CTLENDVAR) {
535			outfmt(&errout, "%s\n", startp);
536			error(NULL);
537		}
538		error("%.*s: parameter %snot set",
539		      (int)(p - str - 1),
540		      str, (varflags & VSNUL) ? "null or "
541					      : nullstr);
542		/* NOTREACHED */
543
544	case VSTRIMLEFT:
545		for (loc = startp; loc < str; loc++) {
546			c = *loc;
547			*loc = '\0';
548			if (patmatch(str, startp, varflags & VSQUOTE))
549				goto recordleft;
550			*loc = c;
551			if ((varflags & VSQUOTE) && *loc == CTLESC)
552			        loc++;
553		}
554		return 0;
555
556	case VSTRIMLEFTMAX:
557		for (loc = str - 1; loc >= startp;) {
558			c = *loc;
559			*loc = '\0';
560			if (patmatch(str, startp, varflags & VSQUOTE))
561				goto recordleft;
562			*loc = c;
563			loc--;
564			if ((varflags & VSQUOTE) && loc > startp &&
565			    *(loc - 1) == CTLESC) {
566				for (q = startp; q < loc; q++)
567					if (*q == CTLESC)
568						q++;
569				if (q > loc)
570					loc--;
571			}
572		}
573		return 0;
574
575	case VSTRIMRIGHT:
576	        for (loc = str - 1; loc >= startp;) {
577			if (patmatch(str, loc, varflags & VSQUOTE))
578				goto recordright;
579			loc--;
580			if ((varflags & VSQUOTE) && loc > startp &&
581			    *(loc - 1) == CTLESC) {
582				for (q = startp; q < loc; q++)
583					if (*q == CTLESC)
584						q++;
585				if (q > loc)
586					loc--;
587			}
588		}
589		return 0;
590
591	case VSTRIMRIGHTMAX:
592		for (loc = startp; loc < str - 1; loc++) {
593			if (patmatch(str, loc, varflags & VSQUOTE))
594				goto recordright;
595			if ((varflags & VSQUOTE) && *loc == CTLESC)
596			        loc++;
597		}
598		return 0;
599
600	default:
601		abort();
602	}
603
604recordleft:
605	*loc = c;
606	amount = ((str - 1) - (loc - startp)) - expdest;
607	STADJUST(amount, expdest);
608	while (loc != str - 1)
609		*startp++ = *loc++;
610	return 1;
611
612recordright:
613	amount = loc - expdest;
614	STADJUST(amount, expdest);
615	STPUTC('\0', expdest);
616	STADJUST(-1, expdest);
617	return 1;
618}
619
620
621/*
622 * Expand a variable, and return a pointer to the next character in the
623 * input string.
624 */
625
626STATIC char *
627evalvar(char *p, int flag)
628{
629	int subtype;
630	int varflags;
631	char *var;
632	char *val;
633	int patloc;
634	int c;
635	int set;
636	int special;
637	int startloc;
638	int varlen;
639	int apply_ifs;
640	int quotes = flag & (EXP_FULL | EXP_CASE);
641
642	varflags = (unsigned char)*p++;
643	subtype = varflags & VSTYPE;
644	var = p;
645	special = !is_name(*p);
646	p = strchr(p, '=') + 1;
647
648again: /* jump here after setting a variable with ${var=text} */
649	if (special) {
650		set = varisset(var, varflags & VSNUL);
651		val = NULL;
652	} else {
653		val = lookupvar(var);
654		if (val == NULL || ((varflags & VSNUL) && val[0] == '\0')) {
655			val = NULL;
656			set = 0;
657		} else
658			set = 1;
659	}
660
661	varlen = 0;
662	startloc = expdest - stackblock();
663
664	if (!set && uflag) {
665		switch (subtype) {
666		case VSNORMAL:
667		case VSTRIMLEFT:
668		case VSTRIMLEFTMAX:
669		case VSTRIMRIGHT:
670		case VSTRIMRIGHTMAX:
671		case VSLENGTH:
672			error("%.*s: parameter not set",
673			    (int)(p - var - 1), var);
674			/* NOTREACHED */
675		}
676	}
677
678	if (set && subtype != VSPLUS) {
679		/* insert the value of the variable */
680		if (special) {
681			varvalue(var, varflags & VSQUOTE, subtype, flag);
682			if (subtype == VSLENGTH) {
683				varlen = expdest - stackblock() - startloc;
684				STADJUST(-varlen, expdest);
685			}
686		} else {
687			char const *syntax = (varflags & VSQUOTE) ? DQSYNTAX
688								  : BASESYNTAX;
689
690			if (subtype == VSLENGTH) {
691				for (;*val; val++)
692					varlen++;
693			} else {
694				while (*val) {
695					if (quotes && syntax[(int)*val] == CCTL)
696						STPUTC(CTLESC, expdest);
697					STPUTC(*val++, expdest);
698				}
699
700			}
701		}
702	}
703
704
705	if (flag & EXP_IN_QUOTES)
706		apply_ifs = 0;
707	else if (varflags & VSQUOTE) {
708		if  (*var == '@' && shellparam.nparam != 1)
709		    apply_ifs = 1;
710		else {
711		    /*
712		     * Mark so that we don't apply IFS if we recurse through
713		     * here expanding $bar from "${foo-$bar}".
714		     */
715		    flag |= EXP_IN_QUOTES;
716		    apply_ifs = 0;
717		}
718	} else
719		apply_ifs = 1;
720
721	switch (subtype) {
722	case VSLENGTH:
723		expdest = cvtnum(varlen, expdest);
724		break;
725
726	case VSNORMAL:
727		break;
728
729	case VSPLUS:
730		set = !set;
731		/* FALLTHROUGH */
732	case VSMINUS:
733		if (!set) {
734		        argstr(p, flag | (apply_ifs ? EXP_IFS_SPLIT : 0));
735			/*
736			 * ${x-a b c} doesn't get split, but removing the
737			 * 'apply_ifs = 0' apparently breaks ${1+"$@"}..
738			 * ${x-'a b' c} should generate 2 args.
739			 */
740			/* We should have marked stuff already */
741			apply_ifs = 0;
742		}
743		break;
744
745	case VSTRIMLEFT:
746	case VSTRIMLEFTMAX:
747	case VSTRIMRIGHT:
748	case VSTRIMRIGHTMAX:
749		if (!set)
750			break;
751		/*
752		 * Terminate the string and start recording the pattern
753		 * right after it
754		 */
755		STPUTC('\0', expdest);
756		patloc = expdest - stackblock();
757		if (subevalvar(p, NULL, patloc, subtype,
758			       startloc, varflags) == 0) {
759			int amount = (expdest - stackblock() - patloc) + 1;
760			STADJUST(-amount, expdest);
761		}
762		/* Remove any recorded regions beyond start of variable */
763		removerecordregions(startloc);
764		apply_ifs = 1;
765		break;
766
767	case VSASSIGN:
768	case VSQUESTION:
769		if (set)
770			break;
771		if (subevalvar(p, var, 0, subtype, startloc, varflags)) {
772			varflags &= ~VSNUL;
773			/*
774			 * Remove any recorded regions beyond
775			 * start of variable
776			 */
777			removerecordregions(startloc);
778			goto again;
779		}
780		apply_ifs = 0;
781		break;
782
783	default:
784		abort();
785	}
786
787	if (apply_ifs)
788		recordregion(startloc, expdest - stackblock(),
789			     varflags & VSQUOTE);
790
791	if (subtype != VSNORMAL) {	/* skip to end of alternative */
792		int nesting = 1;
793		for (;;) {
794			if ((c = *p++) == CTLESC)
795				p++;
796			else if (c == CTLBACKQ || c == (CTLBACKQ|CTLQUOTE)) {
797				if (set)
798					argbackq = argbackq->next;
799			} else if (c == CTLVAR) {
800				if ((*p++ & VSTYPE) != VSNORMAL)
801					nesting++;
802			} else if (c == CTLENDVAR) {
803				if (--nesting == 0)
804					break;
805			}
806		}
807	}
808	return p;
809}
810
811
812
813/*
814 * Test whether a specialized variable is set.
815 */
816
817STATIC int
818varisset(char *name, int nulok)
819{
820	if (*name == '!')
821		return backgndpid != -1;
822	else if (*name == '@' || *name == '*') {
823		if (*shellparam.p == NULL)
824			return 0;
825
826		if (nulok) {
827			char **av;
828
829			for (av = shellparam.p; *av; av++)
830				if (**av != '\0')
831					return 1;
832			return 0;
833		}
834	} else if (is_digit(*name)) {
835		char *ap;
836		int num = atoi(name);
837
838		if (num > shellparam.nparam)
839			return 0;
840
841		if (num == 0)
842			ap = arg0;
843		else
844			ap = shellparam.p[num - 1];
845
846		if (nulok && (ap == NULL || *ap == '\0'))
847			return 0;
848	}
849	return 1;
850}
851
852
853
854/*
855 * Add the value of a specialized variable to the stack string.
856 */
857
858STATIC void
859varvalue(char *name, int quoted, int subtype, int flag)
860{
861	int num;
862	char *p;
863	int i;
864	char sep;
865	char **ap;
866	char const *syntax;
867
868#define STRTODEST(p) \
869	do {\
870	if (flag & (EXP_FULL | EXP_CASE) && subtype != VSLENGTH) { \
871		syntax = quoted? DQSYNTAX : BASESYNTAX; \
872		while (*p) { \
873			if (syntax[(int)*p] == CCTL) \
874				STPUTC(CTLESC, expdest); \
875			STPUTC(*p++, expdest); \
876		} \
877	} else \
878		while (*p) \
879			STPUTC(*p++, expdest); \
880	} while (0)
881
882
883	switch (*name) {
884	case '$':
885		num = rootpid;
886		goto numvar;
887	case '?':
888		num = exitstatus;
889		goto numvar;
890	case '#':
891		num = shellparam.nparam;
892		goto numvar;
893	case '!':
894		num = backgndpid;
895numvar:
896		expdest = cvtnum(num, expdest);
897		break;
898	case '-':
899		for (i = 0; optlist[i].name; i++) {
900			if (optlist[i].val && optlist[i].letter)
901				STPUTC(optlist[i].letter, expdest);
902		}
903		break;
904	case '@':
905		if (flag & EXP_FULL && quoted) {
906			for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
907				STRTODEST(p);
908				if (*ap)
909					/* A NUL separates args inside "" */
910					STPUTC('\0', expdest);
911			}
912			break;
913		}
914		/* fall through */
915	case '*':
916		if (ifsset() != 0)
917			sep = ifsval()[0];
918		else
919			sep = ' ';
920		for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
921			STRTODEST(p);
922			if (*ap && sep)
923				STPUTC(sep, expdest);
924		}
925		break;
926	case '0':
927		p = arg0;
928		STRTODEST(p);
929		break;
930	default:
931		if (is_digit(*name)) {
932			num = atoi(name);
933			if (num > 0 && num <= shellparam.nparam) {
934				p = shellparam.p[num - 1];
935				STRTODEST(p);
936			}
937		}
938		break;
939	}
940}
941
942
943
944/*
945 * Record the fact that we have to scan this region of the
946 * string for IFS characters.
947 */
948
949STATIC void
950recordregion(int start, int end, int inquotes)
951{
952	struct ifsregion *ifsp;
953
954	if (ifslastp == NULL) {
955		ifsp = &ifsfirst;
956	} else {
957		if (ifslastp->endoff == start
958		    && ifslastp->inquotes == inquotes) {
959			/* extend previous area */
960			ifslastp->endoff = end;
961			return;
962		}
963		ifsp = (struct ifsregion *)ckmalloc(sizeof (struct ifsregion));
964		ifslastp->next = ifsp;
965	}
966	ifslastp = ifsp;
967	ifslastp->next = NULL;
968	ifslastp->begoff = start;
969	ifslastp->endoff = end;
970	ifslastp->inquotes = inquotes;
971}
972
973
974
975/*
976 * Break the argument string into pieces based upon IFS and add the
977 * strings to the argument list.  The regions of the string to be
978 * searched for IFS characters have been stored by recordregion.
979 */
980STATIC void
981ifsbreakup(char *string, struct arglist *arglist)
982{
983	struct ifsregion *ifsp;
984	struct strlist *sp;
985	char *start;
986	char *p;
987	char *q;
988	const char *ifs;
989	const char *ifsspc;
990	int had_param_ch = 0;
991
992	start = string;
993
994	if (ifslastp == NULL) {
995		/* Return entire argument, IFS doesn't apply to any of it */
996		sp = (struct strlist *)stalloc(sizeof *sp);
997		sp->text = start;
998		*arglist->lastp = sp;
999		arglist->lastp = &sp->next;
1000		return;
1001	}
1002
1003	ifs = ifsset() ? ifsval() : " \t\n";
1004
1005	for (ifsp = &ifsfirst; ifsp != NULL; ifsp = ifsp->next) {
1006		p = string + ifsp->begoff;
1007		while (p < string + ifsp->endoff) {
1008			had_param_ch = 1;
1009			q = p;
1010			if (*p == CTLESC)
1011				p++;
1012			if (ifsp->inquotes) {
1013				/* Only NULs (should be from "$@") end args */
1014				if (*p != 0) {
1015					p++;
1016					continue;
1017				}
1018				ifsspc = NULL;
1019			} else {
1020				if (!strchr(ifs, *p)) {
1021					p++;
1022					continue;
1023				}
1024				had_param_ch = 0;
1025				ifsspc = strchr(" \t\n", *p);
1026
1027				/* Ignore IFS whitespace at start */
1028				if (q == start && ifsspc != NULL) {
1029					p++;
1030					start = p;
1031					continue;
1032				}
1033			}
1034
1035			/* Save this argument... */
1036			*q = '\0';
1037			sp = (struct strlist *)stalloc(sizeof *sp);
1038			sp->text = start;
1039			*arglist->lastp = sp;
1040			arglist->lastp = &sp->next;
1041			p++;
1042
1043			if (ifsspc != NULL) {
1044				/* Ignore further trailing IFS whitespace */
1045				for (; p < string + ifsp->endoff; p++) {
1046					q = p;
1047					if (*p == CTLESC)
1048						p++;
1049					if (strchr(ifs, *p) == NULL) {
1050						p = q;
1051						break;
1052					}
1053					if (strchr(" \t\n", *p) == NULL) {
1054						p++;
1055						break;
1056					}
1057				}
1058			}
1059			start = p;
1060		}
1061	}
1062
1063	/*
1064	 * Save anything left as an argument.
1065	 * Traditionally we have treated 'IFS=':'; set -- x$IFS' as
1066	 * generating 2 arguments, the second of which is empty.
1067	 * Some recent clarification of the Posix spec say that it
1068	 * should only generate one....
1069	 */
1070	if (had_param_ch || *start != 0) {
1071		sp = (struct strlist *)stalloc(sizeof *sp);
1072		sp->text = start;
1073		*arglist->lastp = sp;
1074		arglist->lastp = &sp->next;
1075	}
1076}
1077
1078STATIC void
1079ifsfree(void)
1080{
1081	while (ifsfirst.next != NULL) {
1082		struct ifsregion *ifsp;
1083		INTOFF;
1084		ifsp = ifsfirst.next->next;
1085		ckfree(ifsfirst.next);
1086		ifsfirst.next = ifsp;
1087		INTON;
1088	}
1089	ifslastp = NULL;
1090	ifsfirst.next = NULL;
1091}
1092
1093
1094
1095/*
1096 * Expand shell metacharacters.  At this point, the only control characters
1097 * should be escapes.  The results are stored in the list exparg.
1098 */
1099
1100char *expdir;
1101
1102
1103STATIC void
1104expandmeta(struct strlist *str, int flag)
1105{
1106	char *p;
1107	struct strlist **savelastp;
1108	struct strlist *sp;
1109	char c;
1110	/* TODO - EXP_REDIR */
1111
1112	while (str) {
1113		if (fflag)
1114			goto nometa;
1115		p = str->text;
1116		for (;;) {			/* fast check for meta chars */
1117			if ((c = *p++) == '\0')
1118				goto nometa;
1119			if (c == '*' || c == '?' || c == '[' || c == '!')
1120				break;
1121		}
1122		savelastp = exparg.lastp;
1123		INTOFF;
1124		if (expdir == NULL) {
1125			int i = strlen(str->text);
1126			expdir = ckmalloc(i < 2048 ? 2048 : i); /* XXX */
1127		}
1128
1129		expmeta(expdir, str->text);
1130		ckfree(expdir);
1131		expdir = NULL;
1132		INTON;
1133		if (exparg.lastp == savelastp) {
1134			/*
1135			 * no matches
1136			 */
1137nometa:
1138			*exparg.lastp = str;
1139			rmescapes(str->text);
1140			exparg.lastp = &str->next;
1141		} else {
1142			*exparg.lastp = NULL;
1143			*savelastp = sp = expsort(*savelastp);
1144			while (sp->next != NULL)
1145				sp = sp->next;
1146			exparg.lastp = &sp->next;
1147		}
1148		str = str->next;
1149	}
1150}
1151
1152
1153/*
1154 * Do metacharacter (i.e. *, ?, [...]) expansion.
1155 */
1156
1157STATIC void
1158expmeta(char *enddir, char *name)
1159{
1160	char *p;
1161	const char *cp;
1162	char *q;
1163	char *start;
1164	char *endname;
1165	int metaflag;
1166	struct stat statb;
1167	DIR *dirp;
1168	struct dirent *dp;
1169	int atend;
1170	int matchdot;
1171
1172	metaflag = 0;
1173	start = name;
1174	for (p = name ; ; p++) {
1175		if (*p == '*' || *p == '?')
1176			metaflag = 1;
1177		else if (*p == '[') {
1178			q = p + 1;
1179			if (*q == '!')
1180				q++;
1181			for (;;) {
1182				while (*q == CTLQUOTEMARK)
1183					q++;
1184				if (*q == CTLESC)
1185					q++;
1186				if (*q == '/' || *q == '\0')
1187					break;
1188				if (*++q == ']') {
1189					metaflag = 1;
1190					break;
1191				}
1192			}
1193		} else if (*p == '!' && p[1] == '!'	&& (p == name || p[-1] == '/')) {
1194			metaflag = 1;
1195		} else if (*p == '\0')
1196			break;
1197		else if (*p == CTLQUOTEMARK)
1198			continue;
1199		else if (*p == CTLESC)
1200			p++;
1201		if (*p == '/') {
1202			if (metaflag)
1203				break;
1204			start = p + 1;
1205		}
1206	}
1207	if (metaflag == 0) {	/* we've reached the end of the file name */
1208		if (enddir != expdir)
1209			metaflag++;
1210		for (p = name ; ; p++) {
1211			if (*p == CTLQUOTEMARK)
1212				continue;
1213			if (*p == CTLESC)
1214				p++;
1215			*enddir++ = *p;
1216			if (*p == '\0')
1217				break;
1218		}
1219		if (metaflag == 0 || lstat(expdir, &statb) >= 0)
1220			addfname(expdir);
1221		return;
1222	}
1223	endname = p;
1224	if (start != name) {
1225		p = name;
1226		while (p < start) {
1227			while (*p == CTLQUOTEMARK)
1228				p++;
1229			if (*p == CTLESC)
1230				p++;
1231			*enddir++ = *p++;
1232		}
1233	}
1234	if (enddir == expdir) {
1235		cp = ".";
1236	} else if (enddir == expdir + 1 && *expdir == '/') {
1237		cp = "/";
1238	} else {
1239		cp = expdir;
1240		enddir[-1] = '\0';
1241	}
1242	if ((dirp = opendir(cp)) == NULL)
1243		return;
1244	if (enddir != expdir)
1245		enddir[-1] = '/';
1246	if (*endname == 0) {
1247		atend = 1;
1248	} else {
1249		atend = 0;
1250		*endname++ = '\0';
1251	}
1252	matchdot = 0;
1253	p = start;
1254	while (*p == CTLQUOTEMARK)
1255		p++;
1256	if (*p == CTLESC)
1257		p++;
1258	if (*p == '.')
1259		matchdot++;
1260	while (! int_pending() && (dp = readdir(dirp)) != NULL) {
1261		if (dp->d_name[0] == '.' && ! matchdot)
1262			continue;
1263		if (patmatch(start, dp->d_name, 0)) {
1264			if (atend) {
1265				scopy(dp->d_name, enddir);
1266				addfname(expdir);
1267			} else {
1268				for (p = enddir, cp = dp->d_name;
1269				     (*p++ = *cp++) != '\0';)
1270					continue;
1271				p[-1] = '/';
1272				expmeta(p, endname);
1273			}
1274		}
1275	}
1276	closedir(dirp);
1277	if (! atend)
1278		endname[-1] = '/';
1279}
1280
1281
1282/*
1283 * Add a file name to the list.
1284 */
1285
1286STATIC void
1287addfname(char *name)
1288{
1289	char *p;
1290	struct strlist *sp;
1291
1292	p = stalloc(strlen(name) + 1);
1293	scopy(name, p);
1294	sp = (struct strlist *)stalloc(sizeof *sp);
1295	sp->text = p;
1296	*exparg.lastp = sp;
1297	exparg.lastp = &sp->next;
1298}
1299
1300
1301/*
1302 * Sort the results of file name expansion.  It calculates the number of
1303 * strings to sort and then calls msort (short for merge sort) to do the
1304 * work.
1305 */
1306
1307STATIC struct strlist *
1308expsort(struct strlist *str)
1309{
1310	int len;
1311	struct strlist *sp;
1312
1313	len = 0;
1314	for (sp = str ; sp ; sp = sp->next)
1315		len++;
1316	return msort(str, len);
1317}
1318
1319
1320STATIC struct strlist *
1321msort(struct strlist *list, int len)
1322{
1323	struct strlist *p, *q = NULL;
1324	struct strlist **lpp;
1325	int half;
1326	int n;
1327
1328	if (len <= 1)
1329		return list;
1330	half = len >> 1;
1331	p = list;
1332	for (n = half ; --n >= 0 ; ) {
1333		q = p;
1334		p = p->next;
1335	}
1336	q->next = NULL;			/* terminate first half of list */
1337	q = msort(list, half);		/* sort first half of list */
1338	p = msort(p, len - half);		/* sort second half */
1339	lpp = &list;
1340	for (;;) {
1341		if (strcmp(p->text, q->text) < 0) {
1342			*lpp = p;
1343			lpp = &p->next;
1344			if ((p = *lpp) == NULL) {
1345				*lpp = q;
1346				break;
1347			}
1348		} else {
1349			*lpp = q;
1350			lpp = &q->next;
1351			if ((q = *lpp) == NULL) {
1352				*lpp = p;
1353				break;
1354			}
1355		}
1356	}
1357	return list;
1358}
1359
1360
1361
1362/*
1363 * Returns true if the pattern matches the string.
1364 */
1365
1366int
1367patmatch(char *pattern, char *string, int squoted)
1368{
1369#ifdef notdef
1370	if (pattern[0] == '!' && pattern[1] == '!')
1371		return 1 - pmatch(pattern + 2, string);
1372	else
1373#endif
1374		return pmatch(pattern, string, squoted);
1375}
1376
1377
1378STATIC int
1379pmatch(char *pattern, char *string, int squoted)
1380{
1381	char *p, *q;
1382	char c;
1383
1384	p = pattern;
1385	q = string;
1386	for (;;) {
1387		switch (c = *p++) {
1388		case '\0':
1389			goto breakloop;
1390		case CTLESC:
1391			if (squoted && *q == CTLESC)
1392				q++;
1393			if (*q++ != *p++)
1394				return 0;
1395			break;
1396		case CTLQUOTEMARK:
1397			continue;
1398		case '?':
1399			if (squoted && *q == CTLESC)
1400				q++;
1401			if (*q++ == '\0')
1402				return 0;
1403			break;
1404		case '*':
1405			c = *p;
1406			while (c == CTLQUOTEMARK || c == '*')
1407				c = *++p;
1408			if (c != CTLESC &&  c != CTLQUOTEMARK &&
1409			    c != '?' && c != '*' && c != '[') {
1410				while (*q != c) {
1411					if (squoted && *q == CTLESC &&
1412					    q[1] == c)
1413						break;
1414					if (*q == '\0')
1415						return 0;
1416					if (squoted && *q == CTLESC)
1417						q++;
1418					q++;
1419				}
1420			}
1421			do {
1422				if (pmatch(p, q, squoted))
1423					return 1;
1424				if (squoted && *q == CTLESC)
1425					q++;
1426			} while (*q++ != '\0');
1427			return 0;
1428		case '[': {
1429			char *endp;
1430			int invert, found;
1431			char chr;
1432
1433			endp = p;
1434			if (*endp == '!')
1435				endp++;
1436			for (;;) {
1437				while (*endp == CTLQUOTEMARK)
1438					endp++;
1439				if (*endp == '\0')
1440					goto dft;		/* no matching ] */
1441				if (*endp == CTLESC)
1442					endp++;
1443				if (*++endp == ']')
1444					break;
1445			}
1446			invert = 0;
1447			if (*p == '!') {
1448				invert++;
1449				p++;
1450			}
1451			found = 0;
1452			chr = *q++;
1453			if (squoted && chr == CTLESC)
1454				chr = *q++;
1455			if (chr == '\0')
1456				return 0;
1457			c = *p++;
1458			do {
1459				if (c == CTLQUOTEMARK)
1460					continue;
1461				if (c == CTLESC)
1462					c = *p++;
1463				if (*p == '-' && p[1] != ']') {
1464					p++;
1465					while (*p == CTLQUOTEMARK)
1466						p++;
1467					if (*p == CTLESC)
1468						p++;
1469					if (chr >= c && chr <= *p)
1470						found = 1;
1471					p++;
1472				} else {
1473					if (chr == c)
1474						found = 1;
1475				}
1476			} while ((c = *p++) != ']');
1477			if (found == invert)
1478				return 0;
1479			break;
1480		}
1481dft:	        default:
1482			if (squoted && *q == CTLESC)
1483				q++;
1484			if (*q++ != c)
1485				return 0;
1486			break;
1487		}
1488	}
1489breakloop:
1490	if (*q != '\0')
1491		return 0;
1492	return 1;
1493}
1494
1495
1496
1497/*
1498 * Remove any CTLESC characters from a string.
1499 */
1500
1501void
1502rmescapes(char *str)
1503{
1504	char *p, *q;
1505
1506	p = str;
1507	while (*p != CTLESC && *p != CTLQUOTEMARK) {
1508		if (*p++ == '\0')
1509			return;
1510	}
1511	q = p;
1512	while (*p) {
1513		if (*p == CTLQUOTEMARK) {
1514			p++;
1515			continue;
1516		}
1517		if (*p == CTLESC)
1518			p++;
1519		*q++ = *p++;
1520	}
1521	*q = '\0';
1522}
1523
1524
1525
1526/*
1527 * See if a pattern matches in a case statement.
1528 */
1529
1530int
1531casematch(union node *pattern, char *val)
1532{
1533	struct stackmark smark;
1534	int result;
1535	char *p;
1536
1537	setstackmark(&smark);
1538	argbackq = pattern->narg.backquote;
1539	STARTSTACKSTR(expdest);
1540	ifslastp = NULL;
1541	argstr(pattern->narg.text, EXP_TILDE | EXP_CASE);
1542	STPUTC('\0', expdest);
1543	p = grabstackstr(expdest);
1544	result = patmatch(p, val, 0);
1545	popstackmark(&smark);
1546	return result;
1547}
1548
1549/*
1550 * Our own itoa().
1551 */
1552
1553STATIC char *
1554cvtnum(int num, char *buf)
1555{
1556	char temp[32];
1557	int neg = num < 0;
1558	char *p = temp + 31;
1559
1560	temp[31] = '\0';
1561
1562	do {
1563		*--p = num % 10 + '0';
1564	} while ((num /= 10) != 0);
1565
1566	if (neg)
1567		*--p = '-';
1568
1569	while (*p)
1570		STPUTC(*p++, buf);
1571	return buf;
1572}
1573
1574/*
1575 * Do most of the work for wordexp(3).
1576 */
1577
1578int
1579wordexpcmd(int argc, char **argv)
1580{
1581	size_t len;
1582	int i;
1583
1584	out1fmt("%d", argc - 1);
1585	out1c('\0');
1586	for (i = 1, len = 0; i < argc; i++)
1587		len += strlen(argv[i]);
1588	out1fmt("%zu", len);
1589	out1c('\0');
1590	for (i = 1; i < argc; i++) {
1591		out1str(argv[i]);
1592		out1c('\0');
1593	}
1594	return (0);
1595}
1596