expand.c revision 108286 
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 108286 2002-12-26 14:28:54Z tjr $");
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);
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);
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);
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", 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);
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", p - var - 1, var);
670		}
671	}
672	if (set && subtype != VSPLUS) {
673		/* insert the value of the variable */
674		if (special) {
675			varvalue(var, varflags & VSQUOTE, flag & EXP_FULL);
676			if (subtype == VSLENGTH) {
677				varlen = expdest - stackblock() - startloc;
678				STADJUST(-varlen, expdest);
679			}
680		} else {
681			char const *syntax = (varflags & VSQUOTE) ? DQSYNTAX
682								  : BASESYNTAX;
683
684			if (subtype == VSLENGTH) {
685				for (;*val; val++)
686					varlen++;
687			}
688			else {
689				while (*val) {
690					if (quotes &&
691					    syntax[(int)*val] == CCTL)
692						STPUTC(CTLESC, expdest);
693					STPUTC(*val++, expdest);
694				}
695
696			}
697		}
698	}
699
700	if (subtype == VSPLUS)
701		set = ! set;
702
703	easy = ((varflags & VSQUOTE) == 0 ||
704		(*var == '@' && shellparam.nparam != 1));
705
706
707	switch (subtype) {
708	case VSLENGTH:
709		expdest = cvtnum(varlen, expdest);
710		goto record;
711
712	case VSNORMAL:
713		if (!easy)
714			break;
715record:
716		recordregion(startloc, expdest - stackblock(),
717			     varflags & VSQUOTE);
718		break;
719
720	case VSPLUS:
721	case VSMINUS:
722		if (!set) {
723			argstr(p, flag);
724			break;
725		}
726		if (easy)
727			goto record;
728		break;
729
730	case VSTRIMLEFT:
731	case VSTRIMLEFTMAX:
732	case VSTRIMRIGHT:
733	case VSTRIMRIGHTMAX:
734		if (!set)
735			break;
736		/*
737		 * Terminate the string and start recording the pattern
738		 * right after it
739		 */
740		STPUTC('\0', expdest);
741		patloc = expdest - stackblock();
742		if (subevalvar(p, NULL, patloc, subtype,
743			       startloc, varflags) == 0) {
744			int amount = (expdest - stackblock() - patloc) + 1;
745			STADJUST(-amount, expdest);
746		}
747		/* Remove any recorded regions beyond start of variable */
748		removerecordregions(startloc);
749		goto record;
750
751	case VSASSIGN:
752	case VSQUESTION:
753		if (!set) {
754			if (subevalvar(p, var, 0, subtype, startloc, varflags)) {
755				varflags &= ~VSNUL;
756				/*
757				 * Remove any recorded regions beyond
758				 * start of variable
759				 */
760				removerecordregions(startloc);
761				goto again;
762			}
763			break;
764		}
765		if (easy)
766			goto record;
767		break;
768
769	default:
770		abort();
771	}
772
773	if (subtype != VSNORMAL) {	/* skip to end of alternative */
774		int nesting = 1;
775		for (;;) {
776			if ((c = *p++) == CTLESC)
777				p++;
778			else if (c == CTLBACKQ || c == (CTLBACKQ|CTLQUOTE)) {
779				if (set)
780					argbackq = argbackq->next;
781			} else if (c == CTLVAR) {
782				if ((*p++ & VSTYPE) != VSNORMAL)
783					nesting++;
784			} else if (c == CTLENDVAR) {
785				if (--nesting == 0)
786					break;
787			}
788		}
789	}
790	return p;
791}
792
793
794
795/*
796 * Test whether a specialized variable is set.
797 */
798
799STATIC int
800varisset(char *name, int nulok)
801{
802
803	if (*name == '!')
804		return backgndpid != -1;
805	else if (*name == '@' || *name == '*') {
806		if (*shellparam.p == NULL)
807			return 0;
808
809		if (nulok) {
810			char **av;
811
812			for (av = shellparam.p; *av; av++)
813				if (**av != '\0')
814					return 1;
815			return 0;
816		}
817	} else if (is_digit(*name)) {
818		char *ap;
819		int num = atoi(name);
820
821		if (num > shellparam.nparam)
822			return 0;
823
824		if (num == 0)
825			ap = arg0;
826		else
827			ap = shellparam.p[num - 1];
828
829		if (nulok && (ap == NULL || *ap == '\0'))
830			return 0;
831	}
832	return 1;
833}
834
835
836
837/*
838 * Add the value of a specialized variable to the stack string.
839 */
840
841STATIC void
842varvalue(char *name, int quoted, int allow_split)
843{
844	int num;
845	char *p;
846	int i;
847	extern int oexitstatus;
848	char sep;
849	char **ap;
850	char const *syntax;
851
852#define STRTODEST(p) \
853	do {\
854	if (allow_split) { \
855		syntax = quoted? DQSYNTAX : BASESYNTAX; \
856		while (*p) { \
857			if (syntax[(int)*p] == CCTL) \
858				STPUTC(CTLESC, expdest); \
859			STPUTC(*p++, expdest); \
860		} \
861	} else \
862		while (*p) \
863			STPUTC(*p++, expdest); \
864	} while (0)
865
866
867	switch (*name) {
868	case '$':
869		num = rootpid;
870		goto numvar;
871	case '?':
872		num = oexitstatus;
873		goto numvar;
874	case '#':
875		num = shellparam.nparam;
876		goto numvar;
877	case '!':
878		num = backgndpid;
879numvar:
880		expdest = cvtnum(num, expdest);
881		break;
882	case '-':
883		for (i = 0 ; i < NOPTS ; i++) {
884			if (optlist[i].val)
885				STPUTC(optlist[i].letter, expdest);
886		}
887		break;
888	case '@':
889		if (allow_split && quoted) {
890			for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
891				STRTODEST(p);
892				if (*ap)
893					STPUTC('\0', expdest);
894			}
895			break;
896		}
897		/* FALLTHROUGH */
898	case '*':
899		if (ifsset() != 0)
900			sep = ifsval()[0];
901		else
902			sep = ' ';
903		for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
904			STRTODEST(p);
905			if (*ap && sep)
906				STPUTC(sep, expdest);
907		}
908		break;
909	case '0':
910		p = arg0;
911		STRTODEST(p);
912		break;
913	default:
914		if (is_digit(*name)) {
915			num = atoi(name);
916			if (num > 0 && num <= shellparam.nparam) {
917				p = shellparam.p[num - 1];
918				STRTODEST(p);
919			}
920		}
921		break;
922	}
923}
924
925
926
927/*
928 * Record the the fact that we have to scan this region of the
929 * string for IFS characters.
930 */
931
932STATIC void
933recordregion(int start, int end, int nulonly)
934{
935	struct ifsregion *ifsp;
936
937	if (ifslastp == NULL) {
938		ifsp = &ifsfirst;
939	} else {
940		ifsp = (struct ifsregion *)ckmalloc(sizeof (struct ifsregion));
941		ifslastp->next = ifsp;
942	}
943	ifslastp = ifsp;
944	ifslastp->next = NULL;
945	ifslastp->begoff = start;
946	ifslastp->endoff = end;
947	ifslastp->nulonly = nulonly;
948}
949
950
951
952/*
953 * Break the argument string into pieces based upon IFS and add the
954 * strings to the argument list.  The regions of the string to be
955 * searched for IFS characters have been stored by recordregion.
956 */
957STATIC void
958ifsbreakup(char *string, struct arglist *arglist)
959{
960	struct ifsregion *ifsp;
961	struct strlist *sp;
962	char *start;
963	char *p;
964	char *q;
965	char *ifs;
966	int ifsspc;
967	int nulonly;
968
969
970	start = string;
971	ifsspc = 0;
972	nulonly = 0;
973	if (ifslastp != NULL) {
974		ifsp = &ifsfirst;
975		do {
976			p = string + ifsp->begoff;
977			nulonly = ifsp->nulonly;
978			ifs = nulonly ? nullstr :
979				( ifsset() ? ifsval() : " \t\n" );
980			ifsspc = 0;
981			while (p < string + ifsp->endoff) {
982				q = p;
983				if (*p == CTLESC)
984					p++;
985				if (strchr(ifs, *p)) {
986					if (!nulonly)
987						ifsspc = (strchr(" \t\n", *p) != NULL);
988					/* Ignore IFS whitespace at start */
989					if (q == start && ifsspc) {
990						p++;
991						start = p;
992						continue;
993					}
994					*q = '\0';
995					sp = (struct strlist *)stalloc(sizeof *sp);
996					sp->text = start;
997					*arglist->lastp = sp;
998					arglist->lastp = &sp->next;
999					p++;
1000					if (!nulonly) {
1001						for (;;) {
1002							if (p >= string + ifsp->endoff) {
1003								break;
1004							}
1005							q = p;
1006							if (*p == CTLESC)
1007								p++;
1008							if (strchr(ifs, *p) == NULL ) {
1009								p = q;
1010								break;
1011							} else if (strchr(" \t\n",*p) == NULL) {
1012								if (ifsspc) {
1013									p++;
1014									ifsspc = 0;
1015								} else {
1016									p = q;
1017									break;
1018								}
1019							} else
1020								p++;
1021						}
1022					}
1023					start = p;
1024				} else
1025					p++;
1026			}
1027		} while ((ifsp = ifsp->next) != NULL);
1028		if (*start || (!ifsspc && start > string &&
1029			(nulonly || 1))) {
1030			sp = (struct strlist *)stalloc(sizeof *sp);
1031			sp->text = start;
1032			*arglist->lastp = sp;
1033			arglist->lastp = &sp->next;
1034		}
1035	} else {
1036		sp = (struct strlist *)stalloc(sizeof *sp);
1037		sp->text = start;
1038		*arglist->lastp = sp;
1039		arglist->lastp = &sp->next;
1040	}
1041}
1042
1043
1044
1045/*
1046 * Expand shell metacharacters.  At this point, the only control characters
1047 * should be escapes.  The results are stored in the list exparg.
1048 */
1049
1050char *expdir;
1051
1052
1053STATIC void
1054expandmeta(struct strlist *str, int flag __unused)
1055{
1056	char *p;
1057	struct strlist **savelastp;
1058	struct strlist *sp;
1059	char c;
1060	/* TODO - EXP_REDIR */
1061
1062	while (str) {
1063		if (fflag)
1064			goto nometa;
1065		p = str->text;
1066		for (;;) {			/* fast check for meta chars */
1067			if ((c = *p++) == '\0')
1068				goto nometa;
1069			if (c == '*' || c == '?' || c == '[' || c == '!')
1070				break;
1071		}
1072		savelastp = exparg.lastp;
1073		INTOFF;
1074		if (expdir == NULL) {
1075			int i = strlen(str->text);
1076			expdir = ckmalloc(i < 2048 ? 2048 : i); /* XXX */
1077		}
1078
1079		expmeta(expdir, str->text);
1080		ckfree(expdir);
1081		expdir = NULL;
1082		INTON;
1083		if (exparg.lastp == savelastp) {
1084			/*
1085			 * no matches
1086			 */
1087nometa:
1088			*exparg.lastp = str;
1089			rmescapes(str->text);
1090			exparg.lastp = &str->next;
1091		} else {
1092			*exparg.lastp = NULL;
1093			*savelastp = sp = expsort(*savelastp);
1094			while (sp->next != NULL)
1095				sp = sp->next;
1096			exparg.lastp = &sp->next;
1097		}
1098		str = str->next;
1099	}
1100}
1101
1102
1103/*
1104 * Do metacharacter (i.e. *, ?, [...]) expansion.
1105 */
1106
1107STATIC void
1108expmeta(char *enddir, char *name)
1109{
1110	char *p;
1111	char *q;
1112	char *start;
1113	char *endname;
1114	int metaflag;
1115	struct stat statb;
1116	DIR *dirp;
1117	struct dirent *dp;
1118	int atend;
1119	int matchdot;
1120
1121	metaflag = 0;
1122	start = name;
1123	for (p = name ; ; p++) {
1124		if (*p == '*' || *p == '?')
1125			metaflag = 1;
1126		else if (*p == '[') {
1127			q = p + 1;
1128			if (*q == '!' || *q == '^')
1129				q++;
1130			for (;;) {
1131				while (*q == CTLQUOTEMARK)
1132					q++;
1133				if (*q == CTLESC)
1134					q++;
1135				if (*q == '/' || *q == '\0')
1136					break;
1137				if (*++q == ']') {
1138					metaflag = 1;
1139					break;
1140				}
1141			}
1142		} else if (*p == '!' && p[1] == '!'	&& (p == name || p[-1] == '/')) {
1143			metaflag = 1;
1144		} else if (*p == '\0')
1145			break;
1146		else if (*p == CTLQUOTEMARK)
1147			continue;
1148		else if (*p == CTLESC)
1149			p++;
1150		if (*p == '/') {
1151			if (metaflag)
1152				break;
1153			start = p + 1;
1154		}
1155	}
1156	if (metaflag == 0) {	/* we've reached the end of the file name */
1157		if (enddir != expdir)
1158			metaflag++;
1159		for (p = name ; ; p++) {
1160			if (*p == CTLQUOTEMARK)
1161				continue;
1162			if (*p == CTLESC)
1163				p++;
1164			*enddir++ = *p;
1165			if (*p == '\0')
1166				break;
1167		}
1168		if (metaflag == 0 || stat(expdir, &statb) >= 0)
1169			addfname(expdir);
1170		return;
1171	}
1172	endname = p;
1173	if (start != name) {
1174		p = name;
1175		while (p < start) {
1176			while (*p == CTLQUOTEMARK)
1177				p++;
1178			if (*p == CTLESC)
1179				p++;
1180			*enddir++ = *p++;
1181		}
1182	}
1183	if (enddir == expdir) {
1184		p = ".";
1185	} else if (enddir == expdir + 1 && *expdir == '/') {
1186		p = "/";
1187	} else {
1188		p = expdir;
1189		enddir[-1] = '\0';
1190	}
1191	if ((dirp = opendir(p)) == NULL)
1192		return;
1193	if (enddir != expdir)
1194		enddir[-1] = '/';
1195	if (*endname == 0) {
1196		atend = 1;
1197	} else {
1198		atend = 0;
1199		*endname++ = '\0';
1200	}
1201	matchdot = 0;
1202	p = start;
1203	while (*p == CTLQUOTEMARK)
1204		p++;
1205	if (*p == CTLESC)
1206		p++;
1207	if (*p == '.')
1208		matchdot++;
1209	while (! int_pending() && (dp = readdir(dirp)) != NULL) {
1210		if (dp->d_name[0] == '.' && ! matchdot)
1211			continue;
1212		if (patmatch(start, dp->d_name, 0)) {
1213			if (atend) {
1214				scopy(dp->d_name, enddir);
1215				addfname(expdir);
1216			} else {
1217				char *q;
1218				for (p = enddir, q = dp->d_name;
1219				     (*p++ = *q++) != '\0';)
1220					continue;
1221				p[-1] = '/';
1222				expmeta(p, endname);
1223			}
1224		}
1225	}
1226	closedir(dirp);
1227	if (! atend)
1228		endname[-1] = '/';
1229}
1230
1231
1232/*
1233 * Add a file name to the list.
1234 */
1235
1236STATIC void
1237addfname(char *name)
1238{
1239	char *p;
1240	struct strlist *sp;
1241
1242	p = stalloc(strlen(name) + 1);
1243	scopy(name, p);
1244	sp = (struct strlist *)stalloc(sizeof *sp);
1245	sp->text = p;
1246	*exparg.lastp = sp;
1247	exparg.lastp = &sp->next;
1248}
1249
1250
1251/*
1252 * Sort the results of file name expansion.  It calculates the number of
1253 * strings to sort and then calls msort (short for merge sort) to do the
1254 * work.
1255 */
1256
1257STATIC struct strlist *
1258expsort(struct strlist *str)
1259{
1260	int len;
1261	struct strlist *sp;
1262
1263	len = 0;
1264	for (sp = str ; sp ; sp = sp->next)
1265		len++;
1266	return msort(str, len);
1267}
1268
1269
1270STATIC struct strlist *
1271msort(struct strlist *list, int len)
1272{
1273	struct strlist *p, *q = NULL;
1274	struct strlist **lpp;
1275	int half;
1276	int n;
1277
1278	if (len <= 1)
1279		return list;
1280	half = len >> 1;
1281	p = list;
1282	for (n = half ; --n >= 0 ; ) {
1283		q = p;
1284		p = p->next;
1285	}
1286	q->next = NULL;			/* terminate first half of list */
1287	q = msort(list, half);		/* sort first half of list */
1288	p = msort(p, len - half);		/* sort second half */
1289	lpp = &list;
1290	for (;;) {
1291		if (strcmp(p->text, q->text) < 0) {
1292			*lpp = p;
1293			lpp = &p->next;
1294			if ((p = *lpp) == NULL) {
1295				*lpp = q;
1296				break;
1297			}
1298		} else {
1299			*lpp = q;
1300			lpp = &q->next;
1301			if ((q = *lpp) == NULL) {
1302				*lpp = p;
1303				break;
1304			}
1305		}
1306	}
1307	return list;
1308}
1309
1310
1311
1312/*
1313 * Returns true if the pattern matches the string.
1314 */
1315
1316int
1317patmatch(char *pattern, char *string, int squoted)
1318{
1319#ifdef notdef
1320	if (pattern[0] == '!' && pattern[1] == '!')
1321		return 1 - pmatch(pattern + 2, string);
1322	else
1323#endif
1324		return pmatch(pattern, string, squoted);
1325}
1326
1327
1328STATIC int
1329pmatch(char *pattern, char *string, int squoted)
1330{
1331	char *p, *q;
1332	char c;
1333
1334	p = pattern;
1335	q = string;
1336	for (;;) {
1337		switch (c = *p++) {
1338		case '\0':
1339			goto breakloop;
1340		case CTLESC:
1341			if (squoted && *q == CTLESC)
1342				q++;
1343			if (*q++ != *p++)
1344				return 0;
1345			break;
1346		case CTLQUOTEMARK:
1347			continue;
1348		case '?':
1349			if (squoted && *q == CTLESC)
1350				q++;
1351			if (*q++ == '\0')
1352				return 0;
1353			break;
1354		case '*':
1355			c = *p;
1356			while (c == CTLQUOTEMARK || c == '*')
1357				c = *++p;
1358			if (c != CTLESC &&  c != CTLQUOTEMARK &&
1359			    c != '?' && c != '*' && c != '[') {
1360				while (*q != c) {
1361					if (squoted && *q == CTLESC &&
1362					    q[1] == c)
1363						break;
1364					if (*q == '\0')
1365						return 0;
1366					if (squoted && *q == CTLESC)
1367						q++;
1368					q++;
1369				}
1370			}
1371			do {
1372				if (pmatch(p, q, squoted))
1373					return 1;
1374				if (squoted && *q == CTLESC)
1375					q++;
1376			} while (*q++ != '\0');
1377			return 0;
1378		case '[': {
1379			char *endp;
1380			int invert, found;
1381			char chr;
1382
1383			endp = p;
1384			if (*endp == '!' || *endp == '^')
1385				endp++;
1386			for (;;) {
1387				while (*endp == CTLQUOTEMARK)
1388					endp++;
1389				if (*endp == '\0')
1390					goto dft;		/* no matching ] */
1391				if (*endp == CTLESC)
1392					endp++;
1393				if (*++endp == ']')
1394					break;
1395			}
1396			invert = 0;
1397			if (*p == '!' || *p == '^') {
1398				invert++;
1399				p++;
1400			}
1401			found = 0;
1402			chr = *q++;
1403			if (squoted && chr == CTLESC)
1404				chr = *q++;
1405			if (chr == '\0')
1406				return 0;
1407			c = *p++;
1408			do {
1409				if (c == CTLQUOTEMARK)
1410					continue;
1411				if (c == CTLESC)
1412					c = *p++;
1413				if (*p == '-' && p[1] != ']') {
1414					p++;
1415					while (*p == CTLQUOTEMARK)
1416						p++;
1417					if (*p == CTLESC)
1418						p++;
1419					if (   collate_range_cmp(chr, c) >= 0
1420					    && collate_range_cmp(chr, *p) <= 0
1421					   )
1422						found = 1;
1423					p++;
1424				} else {
1425					if (chr == c)
1426						found = 1;
1427				}
1428			} while ((c = *p++) != ']');
1429			if (found == invert)
1430				return 0;
1431			break;
1432		}
1433dft:	        default:
1434			if (squoted && *q == CTLESC)
1435				q++;
1436			if (*q++ != c)
1437				return 0;
1438			break;
1439		}
1440	}
1441breakloop:
1442	if (*q != '\0')
1443		return 0;
1444	return 1;
1445}
1446
1447
1448
1449/*
1450 * Remove any CTLESC characters from a string.
1451 */
1452
1453void
1454rmescapes(char *str)
1455{
1456	char *p, *q;
1457
1458	p = str;
1459	while (*p != CTLESC && *p != CTLQUOTEMARK) {
1460		if (*p++ == '\0')
1461			return;
1462	}
1463	q = p;
1464	while (*p) {
1465		if (*p == CTLQUOTEMARK) {
1466			p++;
1467			continue;
1468		}
1469		if (*p == CTLESC)
1470			p++;
1471		*q++ = *p++;
1472	}
1473	*q = '\0';
1474}
1475
1476
1477
1478/*
1479 * See if a pattern matches in a case statement.
1480 */
1481
1482int
1483casematch(union node *pattern, char *val)
1484{
1485	struct stackmark smark;
1486	int result;
1487	char *p;
1488
1489	setstackmark(&smark);
1490	argbackq = pattern->narg.backquote;
1491	STARTSTACKSTR(expdest);
1492	ifslastp = NULL;
1493	argstr(pattern->narg.text, EXP_TILDE | EXP_CASE);
1494	STPUTC('\0', expdest);
1495	p = grabstackstr(expdest);
1496	result = patmatch(p, val, 0);
1497	popstackmark(&smark);
1498	return result;
1499}
1500
1501/*
1502 * Our own itoa().
1503 */
1504
1505STATIC char *
1506cvtnum(int num, char *buf)
1507{
1508	char temp[32];
1509	int neg = num < 0;
1510	char *p = temp + 31;
1511
1512	temp[31] = '\0';
1513
1514	do {
1515		*--p = num % 10 + '0';
1516	} while ((num /= 10) != 0);
1517
1518	if (neg)
1519		*--p = '-';
1520
1521	while (*p)
1522		STPUTC(*p++, buf);
1523	return buf;
1524}
1525
1526/*
1527 * Do most of the work for wordexp(3).
1528 */
1529
1530int
1531wordexpcmd(int argc, char **argv)
1532{
1533	size_t len;
1534	int i;
1535
1536	out1fmt("%08x", argc - 1);
1537	for (i = 1, len = 0; i < argc; i++)
1538		len += strlen(argv[i]);
1539	out1fmt("%08x", (int)len);
1540	for (i = 1; i < argc; i++) {
1541		out1str(argv[i]);
1542		out1c('\0');
1543	}
1544        return (0);
1545}
1546