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