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