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