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