expand.c revision 118374 
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 118374 2003-08-03 04:28:10Z ache $");
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
93STATIC char *expdest;			/* output of current string */
94STATIC struct nodelist *argbackq;	/* list of back quote expressions */
95STATIC struct ifsregion ifsfirst;	/* first struct in list of ifs regions */
96STATIC struct ifsregion *ifslastp;	/* last struct in list */
97STATIC struct 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
123	s1[0] = c1;
124	s2[0] = c2;
125	return (strcoll(s1, s2));
126}
127
128/*
129 * Expand shell variables and backquotes inside a here document.
130 *	union node *arg		the document
131 *	int fd;			where to write the expanded version
132 */
133
134void
135expandhere(union node *arg, int fd)
136{
137	herefd = fd;
138	expandarg(arg, (struct arglist *)NULL, 0);
139	xwrite(fd, stackblock(), expdest - stackblock());
140}
141
142
143/*
144 * Perform variable substitution and command substitution on an argument,
145 * placing the resulting list of arguments in arglist.  If EXP_FULL is true,
146 * perform splitting and file name expansion.  When arglist is NULL, perform
147 * here document expansion.
148 */
149
150void
151expandarg(union node *arg, struct arglist *arglist, int flag)
152{
153	struct strlist *sp;
154	char *p;
155
156	argbackq = arg->narg.backquote;
157	STARTSTACKSTR(expdest);
158	ifsfirst.next = NULL;
159	ifslastp = NULL;
160	argstr(arg->narg.text, flag);
161	if (arglist == NULL) {
162		return;			/* here document expanded */
163	}
164	STPUTC('\0', expdest);
165	p = grabstackstr(expdest);
166	exparg.lastp = &exparg.list;
167	/*
168	 * TODO - EXP_REDIR
169	 */
170	if (flag & EXP_FULL) {
171		ifsbreakup(p, &exparg);
172		*exparg.lastp = NULL;
173		exparg.lastp = &exparg.list;
174		expandmeta(exparg.list, flag);
175	} else {
176		if (flag & EXP_REDIR) /*XXX - for now, just remove escapes */
177			rmescapes(p);
178		sp = (struct strlist *)stalloc(sizeof (struct strlist));
179		sp->text = p;
180		*exparg.lastp = sp;
181		exparg.lastp = &sp->next;
182	}
183	while (ifsfirst.next != NULL) {
184		struct ifsregion *ifsp;
185		INTOFF;
186		ifsp = ifsfirst.next->next;
187		ckfree(ifsfirst.next);
188		ifsfirst.next = ifsp;
189		INTON;
190	}
191	*exparg.lastp = NULL;
192	if (exparg.list) {
193		*arglist->lastp = exparg.list;
194		arglist->lastp = exparg.lastp;
195	}
196}
197
198
199
200/*
201 * Perform variable and command substitution.  If EXP_FULL is set, output CTLESC
202 * characters to allow for further processing.  Otherwise treat
203 * $@ like $* since no splitting will be performed.
204 */
205
206STATIC void
207argstr(char *p, int flag)
208{
209	char c;
210	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);	/* do CTLESC */
211	int firsteq = 1;
212
213	if (*p == '~' && (flag & (EXP_TILDE | EXP_VARTILDE)))
214		p = exptilde(p, flag);
215	for (;;) {
216		switch (c = *p++) {
217		case '\0':
218		case CTLENDVAR: /* ??? */
219			goto breakloop;
220		case CTLQUOTEMARK:
221			/* "$@" syntax adherence hack */
222			if (p[0] == CTLVAR && p[2] == '@' && p[3] == '=')
223				break;
224			if ((flag & EXP_FULL) != 0)
225				STPUTC(c, expdest);
226			break;
227		case CTLESC:
228			if (quotes)
229				STPUTC(c, expdest);
230			c = *p++;
231			STPUTC(c, expdest);
232			break;
233		case CTLVAR:
234			p = evalvar(p, flag);
235			break;
236		case CTLBACKQ:
237		case CTLBACKQ|CTLQUOTE:
238			expbackq(argbackq->n, c & CTLQUOTE, flag);
239			argbackq = argbackq->next;
240			break;
241		case CTLENDARI:
242			expari(flag);
243			break;
244		case ':':
245		case '=':
246			/*
247			 * sort of a hack - expand tildes in variable
248			 * assignments (after the first '=' and after ':'s).
249			 */
250			STPUTC(c, expdest);
251			if (flag & EXP_VARTILDE && *p == '~') {
252				if (c == '=') {
253					if (firsteq)
254						firsteq = 0;
255					else
256						break;
257				}
258				p = exptilde(p, flag);
259			}
260			break;
261		default:
262			STPUTC(c, expdest);
263		}
264	}
265breakloop:;
266}
267
268STATIC char *
269exptilde(char *p, int flag)
270{
271	char c, *startp = p;
272	struct passwd *pw;
273	char *home;
274	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
275
276	while ((c = *p) != '\0') {
277		switch(c) {
278		case CTLESC:
279			return (startp);
280		case CTLQUOTEMARK:
281			return (startp);
282		case ':':
283			if (flag & EXP_VARTILDE)
284				goto done;
285			break;
286		case '/':
287			goto done;
288		}
289		p++;
290	}
291done:
292	*p = '\0';
293	if (*(startp+1) == '\0') {
294		if ((home = lookupvar("HOME")) == NULL)
295			goto lose;
296	} else {
297		if ((pw = getpwnam(startp+1)) == NULL)
298			goto lose;
299		home = pw->pw_dir;
300	}
301	if (*home == '\0')
302		goto lose;
303	*p = c;
304	while ((c = *home++) != '\0') {
305		if (quotes && SQSYNTAX[(int)c] == CCTL)
306			STPUTC(CTLESC, expdest);
307		STPUTC(c, expdest);
308	}
309	return (p);
310lose:
311	*p = c;
312	return (startp);
313}
314
315
316STATIC void
317removerecordregions(int endoff)
318{
319	if (ifslastp == NULL)
320		return;
321
322	if (ifsfirst.endoff > endoff) {
323		while (ifsfirst.next != NULL) {
324			struct ifsregion *ifsp;
325			INTOFF;
326			ifsp = ifsfirst.next->next;
327			ckfree(ifsfirst.next);
328			ifsfirst.next = ifsp;
329			INTON;
330		}
331		if (ifsfirst.begoff > endoff)
332			ifslastp = NULL;
333		else {
334			ifslastp = &ifsfirst;
335			ifsfirst.endoff = endoff;
336		}
337		return;
338	}
339
340	ifslastp = &ifsfirst;
341	while (ifslastp->next && ifslastp->next->begoff < endoff)
342		ifslastp=ifslastp->next;
343	while (ifslastp->next != NULL) {
344		struct ifsregion *ifsp;
345		INTOFF;
346		ifsp = ifslastp->next->next;
347		ckfree(ifslastp->next);
348		ifslastp->next = ifsp;
349		INTON;
350	}
351	if (ifslastp->endoff > endoff)
352		ifslastp->endoff = endoff;
353}
354
355/*
356 * Expand arithmetic expression.  Backup to start of expression,
357 * evaluate, place result in (backed up) result, adjust string position.
358 */
359void
360expari(int flag)
361{
362	char *p, *start;
363	int result;
364	int begoff;
365	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
366	int quoted;
367
368
369	/*
370	 * This routine is slightly over-complicated for
371	 * efficiency.  First we make sure there is
372	 * enough space for the result, which may be bigger
373	 * than the expression if we add exponentiation.  Next we
374	 * scan backwards looking for the start of arithmetic.  If the
375	 * next previous character is a CTLESC character, then we
376	 * have to rescan starting from the beginning since CTLESC
377	 * characters have to be processed left to right.
378	 */
379#if INT_MAX / 1000000000 >= 10 || INT_MIN / 1000000000 <= -10
380#error "integers with more than 10 digits are not supported"
381#endif
382	CHECKSTRSPACE(12 - 2, expdest);
383	USTPUTC('\0', expdest);
384	start = stackblock();
385	p = expdest - 2;
386	while (p >= start && *p != CTLARI)
387		--p;
388	if (p < start || *p != CTLARI)
389		error("missing CTLARI (shouldn't happen)");
390	if (p > start && *(p - 1) == CTLESC)
391		for (p = start; *p != CTLARI; p++)
392			if (*p == CTLESC)
393				p++;
394
395	if (p[1] == '"')
396		quoted=1;
397	else
398		quoted=0;
399	begoff = p - start;
400	removerecordregions(begoff);
401	if (quotes)
402		rmescapes(p+2);
403	result = arith(p+2);
404	fmtstr(p, 12, "%d", result);
405	while (*p++)
406		;
407	if (quoted == 0)
408		recordregion(begoff, p - 1 - start, 0);
409	result = expdest - p + 1;
410	STADJUST(-result, expdest);
411}
412
413
414/*
415 * Expand stuff in backwards quotes.
416 */
417
418STATIC void
419expbackq(union node *cmd, int quoted, int flag)
420{
421	struct backcmd in;
422	int i;
423	char buf[128];
424	char *p;
425	char *dest = expdest;
426	struct ifsregion saveifs, *savelastp;
427	struct nodelist *saveargbackq;
428	char lastc;
429	int startloc = dest - stackblock();
430	char const *syntax = quoted? DQSYNTAX : BASESYNTAX;
431	int saveherefd;
432	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
433	int nnl;
434
435	INTOFF;
436	saveifs = ifsfirst;
437	savelastp = ifslastp;
438	saveargbackq = argbackq;
439	saveherefd = herefd;
440	herefd = -1;
441	p = grabstackstr(dest);
442	evalbackcmd(cmd, &in);
443	ungrabstackstr(p, dest);
444	ifsfirst = saveifs;
445	ifslastp = savelastp;
446	argbackq = saveargbackq;
447	herefd = saveherefd;
448
449	p = in.buf;
450	lastc = '\0';
451	nnl = 0;
452	/* Don't copy trailing newlines */
453	for (;;) {
454		if (--in.nleft < 0) {
455			if (in.fd < 0)
456				break;
457			while ((i = read(in.fd, buf, sizeof buf)) < 0 && errno == EINTR);
458			TRACE(("expbackq: read returns %d\n", i));
459			if (i <= 0)
460				break;
461			p = buf;
462			in.nleft = i - 1;
463		}
464		lastc = *p++;
465		if (lastc != '\0') {
466			if (quotes && syntax[(int)lastc] == CCTL)
467				STPUTC(CTLESC, dest);
468			if (lastc == '\n') {
469				nnl++;
470			} else {
471				while (nnl > 0) {
472					nnl--;
473					STPUTC('\n', dest);
474				}
475				STPUTC(lastc, dest);
476			}
477		}
478	}
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
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 || 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