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