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