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