expand.c revision 164003 
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 * 4. Neither the name of the University nor the names of its contributors
17 *    may be used to endorse or promote products derived from this software
18 *    without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 */
32
33#ifndef lint
34#if 0
35static char sccsid[] = "@(#)expand.c	8.5 (Berkeley) 5/15/95";
36#endif
37#endif /* not lint */
38#include <sys/cdefs.h>
39__FBSDID("$FreeBSD: head/bin/sh/expand.c 164003 2006-11-05 18:36:05Z stefanf $");
40
41#include <sys/types.h>
42#include <sys/time.h>
43#include <sys/stat.h>
44#include <errno.h>
45#include <dirent.h>
46#include <unistd.h>
47#include <pwd.h>
48#include <stdlib.h>
49#include <limits.h>
50#include <stdio.h>
51#include <string.h>
52
53/*
54 * Routines to expand arguments to commands.  We have to deal with
55 * backquotes, shell variables, and file metacharacters.
56 */
57
58#include "shell.h"
59#include "main.h"
60#include "nodes.h"
61#include "eval.h"
62#include "expand.h"
63#include "syntax.h"
64#include "parser.h"
65#include "jobs.h"
66#include "options.h"
67#include "var.h"
68#include "input.h"
69#include "output.h"
70#include "memalloc.h"
71#include "error.h"
72#include "mystring.h"
73#include "arith.h"
74#include "show.h"
75
76/*
77 * Structure specifying which parts of the string should be searched
78 * for IFS characters.
79 */
80
81struct ifsregion {
82	struct ifsregion *next;	/* next region in list */
83	int begoff;		/* offset of start of region */
84	int endoff;		/* offset of end of region */
85	int nulonly;		/* search for nul bytes only */
86};
87
88
89STATIC char *expdest;			/* output of current string */
90STATIC struct nodelist *argbackq;	/* list of back quote expressions */
91STATIC struct ifsregion ifsfirst;	/* first struct in list of ifs regions */
92STATIC struct ifsregion *ifslastp;	/* last struct in list */
93STATIC struct arglist exparg;		/* holds expanded arg list */
94
95STATIC void argstr(char *, int);
96STATIC char *exptilde(char *, int);
97STATIC void expbackq(union node *, int, int);
98STATIC int subevalvar(char *, char *, int, int, int, int);
99STATIC char *evalvar(char *, int);
100STATIC int varisset(char *, int);
101STATIC void varvalue(char *, int, int);
102STATIC void recordregion(int, int, int);
103STATIC void removerecordregions(int);
104STATIC void ifsbreakup(char *, struct arglist *);
105STATIC void expandmeta(struct strlist *, int);
106STATIC void expmeta(char *, char *);
107STATIC void addfname(char *);
108STATIC struct strlist *expsort(struct strlist *);
109STATIC struct strlist *msort(struct strlist *, int);
110STATIC int pmatch(char *, char *, int);
111STATIC char *cvtnum(int, char *);
112STATIC int collate_range_cmp(int, int);
113
114STATIC int
115collate_range_cmp(int c1, int c2)
116{
117	static char s1[2], s2[2];
118
119	s1[0] = c1;
120	s2[0] = c2;
121	return (strcoll(s1, s2));
122}
123
124/*
125 * Expand shell variables and backquotes inside a here document.
126 *	union node *arg		the document
127 *	int fd;			where to write the expanded version
128 */
129
130void
131expandhere(union node *arg, int fd)
132{
133	herefd = fd;
134	expandarg(arg, (struct arglist *)NULL, 0);
135	xwrite(fd, stackblock(), expdest - stackblock());
136}
137
138
139/*
140 * Perform variable substitution and command substitution on an argument,
141 * placing the resulting list of arguments in arglist.  If EXP_FULL is true,
142 * perform splitting and file name expansion.  When arglist is NULL, perform
143 * here document expansion.
144 */
145
146void
147expandarg(union node *arg, struct arglist *arglist, int flag)
148{
149	struct strlist *sp;
150	char *p;
151
152	argbackq = arg->narg.backquote;
153	STARTSTACKSTR(expdest);
154	ifsfirst.next = NULL;
155	ifslastp = NULL;
156	argstr(arg->narg.text, flag);
157	if (arglist == NULL) {
158		return;			/* here document expanded */
159	}
160	STPUTC('\0', expdest);
161	p = grabstackstr(expdest);
162	exparg.lastp = &exparg.list;
163	/*
164	 * TODO - EXP_REDIR
165	 */
166	if (flag & EXP_FULL) {
167		ifsbreakup(p, &exparg);
168		*exparg.lastp = NULL;
169		exparg.lastp = &exparg.list;
170		expandmeta(exparg.list, flag);
171	} else {
172		if (flag & EXP_REDIR) /*XXX - for now, just remove escapes */
173			rmescapes(p);
174		sp = (struct strlist *)stalloc(sizeof (struct strlist));
175		sp->text = p;
176		*exparg.lastp = sp;
177		exparg.lastp = &sp->next;
178	}
179	while (ifsfirst.next != NULL) {
180		struct ifsregion *ifsp;
181		INTOFF;
182		ifsp = ifsfirst.next->next;
183		ckfree(ifsfirst.next);
184		ifsfirst.next = ifsp;
185		INTON;
186	}
187	*exparg.lastp = NULL;
188	if (exparg.list) {
189		*arglist->lastp = exparg.list;
190		arglist->lastp = exparg.lastp;
191	}
192}
193
194
195
196/*
197 * Perform variable and command substitution.  If EXP_FULL is set, output CTLESC
198 * characters to allow for further processing.  Otherwise treat
199 * $@ like $* since no splitting will be performed.
200 */
201
202STATIC void
203argstr(char *p, int flag)
204{
205	char c;
206	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);	/* do CTLESC */
207	int firsteq = 1;
208
209	if (*p == '~' && (flag & (EXP_TILDE | EXP_VARTILDE)))
210		p = exptilde(p, flag);
211	for (;;) {
212		switch (c = *p++) {
213		case '\0':
214		case CTLENDVAR: /* ??? */
215			goto breakloop;
216		case CTLQUOTEMARK:
217			/* "$@" syntax adherence hack */
218			if (p[0] == CTLVAR && p[2] == '@' && p[3] == '=')
219				break;
220			if ((flag & EXP_FULL) != 0)
221				STPUTC(c, expdest);
222			break;
223		case CTLESC:
224			if (quotes)
225				STPUTC(c, expdest);
226			c = *p++;
227			STPUTC(c, expdest);
228			break;
229		case CTLVAR:
230			p = evalvar(p, flag);
231			break;
232		case CTLBACKQ:
233		case CTLBACKQ|CTLQUOTE:
234			expbackq(argbackq->n, c & CTLQUOTE, flag);
235			argbackq = argbackq->next;
236			break;
237		case CTLENDARI:
238			expari(flag);
239			break;
240		case ':':
241		case '=':
242			/*
243			 * sort of a hack - expand tildes in variable
244			 * assignments (after the first '=' and after ':'s).
245			 */
246			STPUTC(c, expdest);
247			if (flag & EXP_VARTILDE && *p == '~') {
248				if (c == '=') {
249					if (firsteq)
250						firsteq = 0;
251					else
252						break;
253				}
254				p = exptilde(p, flag);
255			}
256			break;
257		default:
258			STPUTC(c, expdest);
259		}
260	}
261breakloop:;
262}
263
264STATIC char *
265exptilde(char *p, int flag)
266{
267	char c, *startp = p;
268	struct passwd *pw;
269	char *home;
270	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
271
272	while ((c = *p) != '\0') {
273		switch(c) {
274		case CTLESC:
275			return (startp);
276		case CTLQUOTEMARK:
277			return (startp);
278		case ':':
279			if (flag & EXP_VARTILDE)
280				goto done;
281			break;
282		case '/':
283			goto done;
284		}
285		p++;
286	}
287done:
288	*p = '\0';
289	if (*(startp+1) == '\0') {
290		if ((home = lookupvar("HOME")) == NULL)
291			goto lose;
292	} else {
293		if ((pw = getpwnam(startp+1)) == NULL)
294			goto lose;
295		home = pw->pw_dir;
296	}
297	if (*home == '\0')
298		goto lose;
299	*p = c;
300	while ((c = *home++) != '\0') {
301		if (quotes && SQSYNTAX[(int)c] == CCTL)
302			STPUTC(CTLESC, expdest);
303		STPUTC(c, expdest);
304	}
305	return (p);
306lose:
307	*p = c;
308	return (startp);
309}
310
311
312STATIC void
313removerecordregions(int endoff)
314{
315	if (ifslastp == NULL)
316		return;
317
318	if (ifsfirst.endoff > endoff) {
319		while (ifsfirst.next != NULL) {
320			struct ifsregion *ifsp;
321			INTOFF;
322			ifsp = ifsfirst.next->next;
323			ckfree(ifsfirst.next);
324			ifsfirst.next = ifsp;
325			INTON;
326		}
327		if (ifsfirst.begoff > endoff)
328			ifslastp = NULL;
329		else {
330			ifslastp = &ifsfirst;
331			ifsfirst.endoff = endoff;
332		}
333		return;
334	}
335
336	ifslastp = &ifsfirst;
337	while (ifslastp->next && ifslastp->next->begoff < endoff)
338		ifslastp=ifslastp->next;
339	while (ifslastp->next != NULL) {
340		struct ifsregion *ifsp;
341		INTOFF;
342		ifsp = ifslastp->next->next;
343		ckfree(ifslastp->next);
344		ifslastp->next = ifsp;
345		INTON;
346	}
347	if (ifslastp->endoff > endoff)
348		ifslastp->endoff = endoff;
349}
350
351/*
352 * Expand arithmetic expression.  Backup to start of expression,
353 * evaluate, place result in (backed up) result, adjust string position.
354 */
355void
356expari(int flag)
357{
358	char *p, *start;
359	int result;
360	int begoff;
361	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
362	int quoted;
363
364
365	/*
366	 * This routine is slightly over-complicated for
367	 * efficiency.  First we make sure there is
368	 * enough space for the result, which may be bigger
369	 * than the expression if we add exponentiation.  Next we
370	 * scan backwards looking for the start of arithmetic.  If the
371	 * next previous character is a CTLESC character, then we
372	 * have to rescan starting from the beginning since CTLESC
373	 * characters have to be processed left to right.
374	 */
375#if INT_MAX / 1000000000 >= 10 || INT_MIN / 1000000000 <= -10
376#error "integers with more than 10 digits are not supported"
377#endif
378	CHECKSTRSPACE(12 - 2, expdest);
379	USTPUTC('\0', expdest);
380	start = stackblock();
381	p = expdest - 2;
382	while (p >= start && *p != CTLARI)
383		--p;
384	if (p < start || *p != CTLARI)
385		error("missing CTLARI (shouldn't happen)");
386	if (p > start && *(p - 1) == CTLESC)
387		for (p = start; *p != CTLARI; p++)
388			if (*p == CTLESC)
389				p++;
390
391	if (p[1] == '"')
392		quoted=1;
393	else
394		quoted=0;
395	begoff = p - start;
396	removerecordregions(begoff);
397	if (quotes)
398		rmescapes(p+2);
399	result = arith(p+2);
400	fmtstr(p, 12, "%d", result);
401	while (*p++)
402		;
403	if (quoted == 0)
404		recordregion(begoff, p - 1 - start, 0);
405	result = expdest - p + 1;
406	STADJUST(-result, expdest);
407}
408
409
410/*
411 * Expand stuff in backwards quotes.
412 */
413
414STATIC void
415expbackq(union node *cmd, int quoted, int flag)
416{
417	struct backcmd in;
418	int i;
419	char buf[128];
420	char *p;
421	char *dest = expdest;
422	struct ifsregion saveifs, *savelastp;
423	struct nodelist *saveargbackq;
424	char lastc;
425	int startloc = dest - stackblock();
426	char const *syntax = quoted? DQSYNTAX : BASESYNTAX;
427	int saveherefd;
428	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
429	int nnl;
430
431	INTOFF;
432	saveifs = ifsfirst;
433	savelastp = ifslastp;
434	saveargbackq = argbackq;
435	saveherefd = herefd;
436	herefd = -1;
437	p = grabstackstr(dest);
438	evalbackcmd(cmd, &in);
439	ungrabstackstr(p, dest);
440	ifsfirst = saveifs;
441	ifslastp = savelastp;
442	argbackq = saveargbackq;
443	herefd = saveherefd;
444
445	p = in.buf;
446	lastc = '\0';
447	nnl = 0;
448	/* Don't copy trailing newlines */
449	for (;;) {
450		if (--in.nleft < 0) {
451			if (in.fd < 0)
452				break;
453			while ((i = read(in.fd, buf, sizeof buf)) < 0 && errno == EINTR);
454			TRACE(("expbackq: read returns %d\n", i));
455			if (i <= 0)
456				break;
457			p = buf;
458			in.nleft = i - 1;
459		}
460		lastc = *p++;
461		if (lastc != '\0') {
462			if (quotes && syntax[(int)lastc] == CCTL)
463				STPUTC(CTLESC, dest);
464			if (lastc == '\n') {
465				nnl++;
466			} else {
467				while (nnl > 0) {
468					nnl--;
469					STPUTC('\n', dest);
470				}
471				STPUTC(lastc, dest);
472			}
473		}
474	}
475
476	if (in.fd >= 0)
477		close(in.fd);
478	if (in.buf)
479		ckfree(in.buf);
480	if (in.jp)
481		exitstatus = waitforjob(in.jp, (int *)NULL);
482	if (quoted == 0)
483		recordregion(startloc, dest - stackblock(), 0);
484	TRACE(("evalbackq: size=%d: \"%.*s\"\n",
485		(dest - stackblock()) - startloc,
486		(dest - stackblock()) - startloc,
487		stackblock() + startloc));
488	expdest = dest;
489	INTON;
490}
491
492
493
494STATIC int
495subevalvar(char *p, char *str, int strloc, int subtype, int startloc,
496  int varflags)
497{
498	char *startp;
499	char *loc = NULL;
500	char *q;
501	int c = 0;
502	int saveherefd = herefd;
503	struct nodelist *saveargbackq = argbackq;
504	int amount;
505
506	herefd = -1;
507	argstr(p, 0);
508	STACKSTRNUL(expdest);
509	herefd = saveherefd;
510	argbackq = saveargbackq;
511	startp = stackblock() + startloc;
512	if (str == NULL)
513	    str = stackblock() + strloc;
514
515	switch (subtype) {
516	case VSASSIGN:
517		setvar(str, startp, 0);
518		amount = startp - expdest;
519		STADJUST(amount, expdest);
520		varflags &= ~VSNUL;
521		if (c != 0)
522			*loc = c;
523		return 1;
524
525	case VSQUESTION:
526		if (*p != CTLENDVAR) {
527			outfmt(&errout, "%s\n", startp);
528			error((char *)NULL);
529		}
530		error("%.*s: parameter %snot set", (int)(p - str - 1),
531		      str, (varflags & VSNUL) ? "null or "
532					      : nullstr);
533		return 0;
534
535	case VSTRIMLEFT:
536		for (loc = startp; loc < str; loc++) {
537			c = *loc;
538			*loc = '\0';
539			if (patmatch(str, startp, varflags & VSQUOTE)) {
540				*loc = c;
541				goto recordleft;
542			}
543			*loc = c;
544			if ((varflags & VSQUOTE) && *loc == CTLESC)
545				loc++;
546		}
547		return 0;
548
549	case VSTRIMLEFTMAX:
550		for (loc = str - 1; loc >= startp;) {
551			c = *loc;
552			*loc = '\0';
553			if (patmatch(str, startp, varflags & VSQUOTE)) {
554				*loc = c;
555				goto recordleft;
556			}
557			*loc = c;
558			loc--;
559			if ((varflags & VSQUOTE) && loc > startp &&
560			    *(loc - 1) == CTLESC) {
561				for (q = startp; q < loc; q++)
562					if (*q == CTLESC)
563						q++;
564				if (q > loc)
565					loc--;
566			}
567		}
568		return 0;
569
570	case VSTRIMRIGHT:
571		for (loc = str - 1; loc >= startp;) {
572			if (patmatch(str, loc, varflags & VSQUOTE)) {
573				amount = loc - expdest;
574				STADJUST(amount, expdest);
575				return 1;
576			}
577			loc--;
578			if ((varflags & VSQUOTE) && loc > startp &&
579			    *(loc - 1) == CTLESC) {
580				for (q = startp; q < loc; q++)
581					if (*q == CTLESC)
582						q++;
583				if (q > loc)
584					loc--;
585			}
586		}
587		return 0;
588
589	case VSTRIMRIGHTMAX:
590		for (loc = startp; loc < str - 1; loc++) {
591			if (patmatch(str, loc, varflags & VSQUOTE)) {
592				amount = loc - expdest;
593				STADJUST(amount, expdest);
594				return 1;
595			}
596			if ((varflags & VSQUOTE) && *loc == CTLESC)
597				loc++;
598		}
599		return 0;
600
601
602	default:
603		abort();
604	}
605
606recordleft:
607	amount = ((str - 1) - (loc - startp)) - expdest;
608	STADJUST(amount, expdest);
609	while (loc != str - 1)
610		*startp++ = *loc++;
611	return 1;
612}
613
614
615/*
616 * Expand a variable, and return a pointer to the next character in the
617 * input string.
618 */
619
620STATIC char *
621evalvar(char *p, int flag)
622{
623	int subtype;
624	int varflags;
625	char *var;
626	char *val;
627	int patloc;
628	int c;
629	int set;
630	int special;
631	int startloc;
632	int varlen;
633	int easy;
634	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
635
636	varflags = *p++;
637	subtype = varflags & VSTYPE;
638	var = p;
639	special = 0;
640	if (! is_name(*p))
641		special = 1;
642	p = strchr(p, '=') + 1;
643again: /* jump here after setting a variable with ${var=text} */
644	if (special) {
645		set = varisset(var, varflags & VSNUL);
646		val = NULL;
647	} else {
648		val = bltinlookup(var, 1);
649		if (val == NULL || ((varflags & VSNUL) && val[0] == '\0')) {
650			val = NULL;
651			set = 0;
652		} else
653			set = 1;
654	}
655	varlen = 0;
656	startloc = expdest - stackblock();
657	if (!set && uflag) {
658		switch (subtype) {
659		case VSNORMAL:
660		case VSTRIMLEFT:
661		case VSTRIMLEFTMAX:
662		case VSTRIMRIGHT:
663		case VSTRIMRIGHTMAX:
664		case VSLENGTH:
665			error("%.*s: parameter not set", (int)(p - var - 1),
666			    var);
667		}
668	}
669	if (set && subtype != VSPLUS) {
670		/* insert the value of the variable */
671		if (special) {
672			varvalue(var, varflags & VSQUOTE, flag & EXP_FULL);
673			if (subtype == VSLENGTH) {
674				varlen = expdest - stackblock() - startloc;
675				STADJUST(-varlen, expdest);
676			}
677		} else {
678			char const *syntax = (varflags & VSQUOTE) ? DQSYNTAX
679								  : BASESYNTAX;
680
681			if (subtype == VSLENGTH) {
682				for (;*val; val++)
683					varlen++;
684			}
685			else {
686				while (*val) {
687					if (quotes &&
688					    syntax[(int)*val] == CCTL)
689						STPUTC(CTLESC, expdest);
690					STPUTC(*val++, expdest);
691				}
692
693			}
694		}
695	}
696
697	if (subtype == VSPLUS)
698		set = ! set;
699
700	easy = ((varflags & VSQUOTE) == 0 ||
701		(*var == '@' && shellparam.nparam != 1));
702
703
704	switch (subtype) {
705	case VSLENGTH:
706		expdest = cvtnum(varlen, expdest);
707		goto record;
708
709	case VSNORMAL:
710		if (!easy)
711			break;
712record:
713		recordregion(startloc, expdest - stackblock(),
714			     varflags & VSQUOTE);
715		break;
716
717	case VSPLUS:
718	case VSMINUS:
719		if (!set) {
720			argstr(p, flag);
721			break;
722		}
723		if (easy)
724			goto record;
725		break;
726
727	case VSTRIMLEFT:
728	case VSTRIMLEFTMAX:
729	case VSTRIMRIGHT:
730	case VSTRIMRIGHTMAX:
731		if (!set)
732			break;
733		/*
734		 * Terminate the string and start recording the pattern
735		 * right after it
736		 */
737		STPUTC('\0', expdest);
738		patloc = expdest - stackblock();
739		if (subevalvar(p, NULL, patloc, subtype,
740			       startloc, varflags) == 0) {
741			int amount = (expdest - stackblock() - patloc) + 1;
742			STADJUST(-amount, expdest);
743		}
744		/* Remove any recorded regions beyond start of variable */
745		removerecordregions(startloc);
746		goto record;
747
748	case VSASSIGN:
749	case VSQUESTION:
750		if (!set) {
751			if (subevalvar(p, var, 0, subtype, startloc, varflags)) {
752				varflags &= ~VSNUL;
753				/*
754				 * Remove any recorded regions beyond
755				 * start of variable
756				 */
757				removerecordregions(startloc);
758				goto again;
759			}
760			break;
761		}
762		if (easy)
763			goto record;
764		break;
765
766	case VSERROR:
767		c = p - var - 1;
768		error("${%.*s%s}: Bad substitution", c, var,
769		    (c > 0 && *p != CTLENDVAR) ? "..." : "");
770
771	default:
772		abort();
773	}
774
775	if (subtype != VSNORMAL) {	/* skip to end of alternative */
776		int nesting = 1;
777		for (;;) {
778			if ((c = *p++) == CTLESC)
779				p++;
780			else if (c == CTLBACKQ || c == (CTLBACKQ|CTLQUOTE)) {
781				if (set)
782					argbackq = argbackq->next;
783			} else if (c == CTLVAR) {
784				if ((*p++ & VSTYPE) != VSNORMAL)
785					nesting++;
786			} else if (c == CTLENDVAR) {
787				if (--nesting == 0)
788					break;
789			}
790		}
791	}
792	return p;
793}
794
795
796
797/*
798 * Test whether a specialized variable is set.
799 */
800
801STATIC int
802varisset(char *name, int nulok)
803{
804
805	if (*name == '!')
806		return backgndpid != -1;
807	else if (*name == '@' || *name == '*') {
808		if (*shellparam.p == NULL)
809			return 0;
810
811		if (nulok) {
812			char **av;
813
814			for (av = shellparam.p; *av; av++)
815				if (**av != '\0')
816					return 1;
817			return 0;
818		}
819	} else if (is_digit(*name)) {
820		char *ap;
821		int num = atoi(name);
822
823		if (num > shellparam.nparam)
824			return 0;
825
826		if (num == 0)
827			ap = arg0;
828		else
829			ap = shellparam.p[num - 1];
830
831		if (nulok && (ap == NULL || *ap == '\0'))
832			return 0;
833	}
834	return 1;
835}
836
837
838
839/*
840 * Add the value of a specialized variable to the stack string.
841 */
842
843STATIC void
844varvalue(char *name, int quoted, int allow_split)
845{
846	int num;
847	char *p;
848	int i;
849	extern int oexitstatus;
850	char sep;
851	char **ap;
852	char const *syntax;
853
854#define STRTODEST(p) \
855	do {\
856	if (allow_split) { \
857		syntax = quoted? DQSYNTAX : BASESYNTAX; \
858		while (*p) { \
859			if (syntax[(int)*p] == CCTL) \
860				STPUTC(CTLESC, expdest); \
861			STPUTC(*p++, expdest); \
862		} \
863	} else \
864		while (*p) \
865			STPUTC(*p++, expdest); \
866	} while (0)
867
868
869	switch (*name) {
870	case '$':
871		num = rootpid;
872		goto numvar;
873	case '?':
874		num = oexitstatus;
875		goto numvar;
876	case '#':
877		num = shellparam.nparam;
878		goto numvar;
879	case '!':
880		num = backgndpid;
881numvar:
882		expdest = cvtnum(num, expdest);
883		break;
884	case '-':
885		for (i = 0 ; i < NOPTS ; i++) {
886			if (optlist[i].val)
887				STPUTC(optlist[i].letter, expdest);
888		}
889		break;
890	case '@':
891		if (allow_split && quoted) {
892			for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
893				STRTODEST(p);
894				if (*ap)
895					STPUTC('\0', expdest);
896			}
897			break;
898		}
899		/* FALLTHROUGH */
900	case '*':
901		if (ifsset())
902			sep = ifsval()[0];
903		else
904			sep = ' ';
905		for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
906			STRTODEST(p);
907			if (*ap && sep)
908				STPUTC(sep, expdest);
909		}
910		break;
911	case '0':
912		p = arg0;
913		STRTODEST(p);
914		break;
915	default:
916		if (is_digit(*name)) {
917			num = atoi(name);
918			if (num > 0 && num <= shellparam.nparam) {
919				p = shellparam.p[num - 1];
920				STRTODEST(p);
921			}
922		}
923		break;
924	}
925}
926
927
928
929/*
930 * Record the the fact that we have to scan this region of the
931 * string for IFS characters.
932 */
933
934STATIC void
935recordregion(int start, int end, int nulonly)
936{
937	struct ifsregion *ifsp;
938
939	if (ifslastp == NULL) {
940		ifsp = &ifsfirst;
941	} else {
942		ifsp = (struct ifsregion *)ckmalloc(sizeof (struct ifsregion));
943		ifslastp->next = ifsp;
944	}
945	ifslastp = ifsp;
946	ifslastp->next = NULL;
947	ifslastp->begoff = start;
948	ifslastp->endoff = end;
949	ifslastp->nulonly = nulonly;
950}
951
952
953
954/*
955 * Break the argument string into pieces based upon IFS and add the
956 * strings to the argument list.  The regions of the string to be
957 * searched for IFS characters have been stored by recordregion.
958 */
959STATIC void
960ifsbreakup(char *string, struct arglist *arglist)
961{
962	struct ifsregion *ifsp;
963	struct strlist *sp;
964	char *start;
965	char *p;
966	char *q;
967	char *ifs;
968	int ifsspc;
969	int nulonly;
970
971
972	start = string;
973	ifsspc = 0;
974	nulonly = 0;
975	if (ifslastp != NULL) {
976		ifsp = &ifsfirst;
977		do {
978			p = string + ifsp->begoff;
979			nulonly = ifsp->nulonly;
980			ifs = nulonly ? nullstr :
981				( ifsset() ? ifsval() : " \t\n" );
982			ifsspc = 0;
983			while (p < string + ifsp->endoff) {
984				q = p;
985				if (*p == CTLESC)
986					p++;
987				if (strchr(ifs, *p)) {
988					if (!nulonly)
989						ifsspc = (strchr(" \t\n", *p) != NULL);
990					/* Ignore IFS whitespace at start */
991					if (q == start && ifsspc) {
992						p++;
993						start = p;
994						continue;
995					}
996					*q = '\0';
997					sp = (struct strlist *)stalloc(sizeof *sp);
998					sp->text = start;
999					*arglist->lastp = sp;
1000					arglist->lastp = &sp->next;
1001					p++;
1002					if (!nulonly) {
1003						for (;;) {
1004							if (p >= string + ifsp->endoff) {
1005								break;
1006							}
1007							q = p;
1008							if (*p == CTLESC)
1009								p++;
1010							if (strchr(ifs, *p) == NULL ) {
1011								p = q;
1012								break;
1013							} else if (strchr(" \t\n",*p) == NULL) {
1014								if (ifsspc) {
1015									p++;
1016									ifsspc = 0;
1017								} else {
1018									p = q;
1019									break;
1020								}
1021							} else
1022								p++;
1023						}
1024					}
1025					start = p;
1026				} else
1027					p++;
1028			}
1029		} while ((ifsp = ifsp->next) != NULL);
1030		if (*start || (!ifsspc && start > string)) {
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
1051STATIC char *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 || lstat(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				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