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