expand.c revision 206147 
1/*-
2 * Copyright (c) 1991, 1993
3 *	The Regents of the University of California.  All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Kenneth Almquist.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 * 4. Neither the name of the University nor the names of its contributors
17 *    may be used to endorse or promote products derived from this software
18 *    without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 */
32
33#ifndef lint
34#if 0
35static char sccsid[] = "@(#)expand.c	8.5 (Berkeley) 5/15/95";
36#endif
37#endif /* not lint */
38#include <sys/cdefs.h>
39__FBSDID("$FreeBSD: head/bin/sh/expand.c 206147 2010-04-03 21:07:50Z jilles $");
40
41#include <sys/types.h>
42#include <sys/time.h>
43#include <sys/stat.h>
44#include <errno.h>
45#include <dirent.h>
46#include <unistd.h>
47#include <pwd.h>
48#include <stdlib.h>
49#include <limits.h>
50#include <stdio.h>
51#include <string.h>
52
53/*
54 * Routines to expand arguments to commands.  We have to deal with
55 * backquotes, shell variables, and file metacharacters.
56 */
57
58#include "shell.h"
59#include "main.h"
60#include "nodes.h"
61#include "eval.h"
62#include "expand.h"
63#include "syntax.h"
64#include "parser.h"
65#include "jobs.h"
66#include "options.h"
67#include "var.h"
68#include "input.h"
69#include "output.h"
70#include "memalloc.h"
71#include "error.h"
72#include "mystring.h"
73#include "arith.h"
74#include "show.h"
75
76/*
77 * Structure specifying which parts of the string should be searched
78 * for IFS characters.
79 */
80
81struct ifsregion {
82	struct ifsregion *next;	/* next region in list */
83	int begoff;		/* offset of start of region */
84	int endoff;		/* offset of end of region */
85	int inquotes;		/* search for nul bytes only */
86};
87
88
89STATIC char *expdest;			/* output of current string */
90STATIC struct nodelist *argbackq;	/* list of back quote expressions */
91STATIC struct ifsregion ifsfirst;	/* first struct in list of ifs regions */
92STATIC struct ifsregion *ifslastp;	/* last struct in list */
93STATIC struct arglist exparg;		/* holds expanded arg list */
94
95STATIC void argstr(char *, int);
96STATIC char *exptilde(char *, int);
97STATIC void expbackq(union node *, int, int);
98STATIC int subevalvar(char *, char *, int, int, int, int);
99STATIC char *evalvar(char *, int);
100STATIC int varisset(char *, int);
101STATIC void varvalue(char *, int, int, int);
102STATIC void recordregion(int, int, int);
103STATIC void removerecordregions(int);
104STATIC void ifsbreakup(char *, struct arglist *);
105STATIC void expandmeta(struct strlist *, int);
106STATIC void expmeta(char *, char *);
107STATIC void addfname(char *);
108STATIC struct strlist *expsort(struct strlist *);
109STATIC struct strlist *msort(struct strlist *, int);
110STATIC int pmatch(const char *, const char *, int);
111STATIC char *cvtnum(int, char *);
112STATIC int collate_range_cmp(int, int);
113
114STATIC int
115collate_range_cmp(int c1, int c2)
116{
117	static char s1[2], s2[2];
118
119	s1[0] = c1;
120	s2[0] = c2;
121	return (strcoll(s1, s2));
122}
123
124/*
125 * Expand shell variables and backquotes inside a here document.
126 *	union node *arg		the document
127 *	int fd;			where to write the expanded version
128 */
129
130void
131expandhere(union node *arg, int fd)
132{
133	herefd = fd;
134	expandarg(arg, (struct arglist *)NULL, 0);
135	xwrite(fd, stackblock(), expdest - stackblock());
136}
137
138
139/*
140 * Perform variable substitution and command substitution on an argument,
141 * placing the resulting list of arguments in arglist.  If EXP_FULL is true,
142 * perform splitting and file name expansion.  When arglist is NULL, perform
143 * here document expansion.
144 */
145
146void
147expandarg(union node *arg, struct arglist *arglist, int flag)
148{
149	struct strlist *sp;
150	char *p;
151
152	argbackq = arg->narg.backquote;
153	STARTSTACKSTR(expdest);
154	ifsfirst.next = NULL;
155	ifslastp = NULL;
156	argstr(arg->narg.text, flag);
157	if (arglist == NULL) {
158		return;			/* here document expanded */
159	}
160	STPUTC('\0', expdest);
161	p = grabstackstr(expdest);
162	exparg.lastp = &exparg.list;
163	/*
164	 * TODO - EXP_REDIR
165	 */
166	if (flag & EXP_FULL) {
167		ifsbreakup(p, &exparg);
168		*exparg.lastp = NULL;
169		exparg.lastp = &exparg.list;
170		expandmeta(exparg.list, flag);
171	} else {
172		if (flag & EXP_REDIR) /*XXX - for now, just remove escapes */
173			rmescapes(p);
174		sp = (struct strlist *)stalloc(sizeof (struct strlist));
175		sp->text = p;
176		*exparg.lastp = sp;
177		exparg.lastp = &sp->next;
178	}
179	while (ifsfirst.next != NULL) {
180		struct ifsregion *ifsp;
181		INTOFF;
182		ifsp = ifsfirst.next->next;
183		ckfree(ifsfirst.next);
184		ifsfirst.next = ifsp;
185		INTON;
186	}
187	*exparg.lastp = NULL;
188	if (exparg.list) {
189		*arglist->lastp = exparg.list;
190		arglist->lastp = exparg.lastp;
191	}
192}
193
194
195
196/*
197 * Perform variable and command substitution.  If EXP_FULL is set, output CTLESC
198 * characters to allow for further processing.  Otherwise treat
199 * $@ like $* since no splitting will be performed.
200 */
201
202STATIC void
203argstr(char *p, int flag)
204{
205	char c;
206	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);	/* do CTLESC */
207	int firsteq = 1;
208
209	if (*p == '~' && (flag & (EXP_TILDE | EXP_VARTILDE)))
210		p = exptilde(p, flag);
211	for (;;) {
212		switch (c = *p++) {
213		case '\0':
214		case CTLENDVAR: /* ??? */
215			goto breakloop;
216		case CTLQUOTEMARK:
217			/* "$@" syntax adherence hack */
218			if (p[0] == CTLVAR && p[2] == '@' && p[3] == '=')
219				break;
220			if ((flag & EXP_FULL) != 0)
221				STPUTC(c, expdest);
222			break;
223		case CTLESC:
224			if (quotes)
225				STPUTC(c, expdest);
226			c = *p++;
227			STPUTC(c, expdest);
228			break;
229		case CTLVAR:
230			p = evalvar(p, flag);
231			break;
232		case CTLBACKQ:
233		case CTLBACKQ|CTLQUOTE:
234			expbackq(argbackq->n, c & CTLQUOTE, flag);
235			argbackq = argbackq->next;
236			break;
237		case CTLENDARI:
238			expari(flag);
239			break;
240		case ':':
241		case '=':
242			/*
243			 * sort of a hack - expand tildes in variable
244			 * assignments (after the first '=' and after ':'s).
245			 */
246			STPUTC(c, expdest);
247			if (flag & EXP_VARTILDE && *p == '~') {
248				if (c == '=') {
249					if (firsteq)
250						firsteq = 0;
251					else
252						break;
253				}
254				p = exptilde(p, flag);
255			}
256			break;
257		default:
258			STPUTC(c, expdest);
259		}
260	}
261breakloop:;
262}
263
264STATIC char *
265exptilde(char *p, int flag)
266{
267	char c, *startp = p;
268	struct passwd *pw;
269	char *home;
270	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
271
272	while ((c = *p) != '\0') {
273		switch(c) {
274		case CTLESC: /* This means CTL* are always considered quoted. */
275		case CTLVAR:
276		case CTLENDVAR:
277		case CTLBACKQ:
278		case CTLBACKQ | CTLQUOTE:
279		case CTLARI:
280		case CTLENDARI:
281		case CTLQUOTEMARK:
282			return (startp);
283		case ':':
284			if (flag & EXP_VARTILDE)
285				goto done;
286			break;
287		case '/':
288			goto done;
289		}
290		p++;
291	}
292done:
293	*p = '\0';
294	if (*(startp+1) == '\0') {
295		if ((home = lookupvar("HOME")) == NULL)
296			goto lose;
297	} else {
298		if ((pw = getpwnam(startp+1)) == NULL)
299			goto lose;
300		home = pw->pw_dir;
301	}
302	if (*home == '\0')
303		goto lose;
304	*p = c;
305	while ((c = *home++) != '\0') {
306		if (quotes && SQSYNTAX[(int)c] == CCTL)
307			STPUTC(CTLESC, expdest);
308		STPUTC(c, expdest);
309	}
310	return (p);
311lose:
312	*p = c;
313	return (startp);
314}
315
316
317STATIC void
318removerecordregions(int endoff)
319{
320	if (ifslastp == NULL)
321		return;
322
323	if (ifsfirst.endoff > endoff) {
324		while (ifsfirst.next != NULL) {
325			struct ifsregion *ifsp;
326			INTOFF;
327			ifsp = ifsfirst.next->next;
328			ckfree(ifsfirst.next);
329			ifsfirst.next = ifsp;
330			INTON;
331		}
332		if (ifsfirst.begoff > endoff)
333			ifslastp = NULL;
334		else {
335			ifslastp = &ifsfirst;
336			ifsfirst.endoff = endoff;
337		}
338		return;
339	}
340
341	ifslastp = &ifsfirst;
342	while (ifslastp->next && ifslastp->next->begoff < endoff)
343		ifslastp=ifslastp->next;
344	while (ifslastp->next != NULL) {
345		struct ifsregion *ifsp;
346		INTOFF;
347		ifsp = ifslastp->next->next;
348		ckfree(ifslastp->next);
349		ifslastp->next = ifsp;
350		INTON;
351	}
352	if (ifslastp->endoff > endoff)
353		ifslastp->endoff = endoff;
354}
355
356/*
357 * Expand arithmetic expression.  Backup to start of expression,
358 * evaluate, place result in (backed up) result, adjust string position.
359 */
360void
361expari(int flag)
362{
363	char *p, *start;
364	arith_t result;
365	int begoff;
366	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
367	int quoted;
368
369
370	/*
371	 * This routine is slightly over-complicated for
372	 * efficiency.  First we make sure there is
373	 * enough space for the result, which may be bigger
374	 * than the expression if we add exponentiation.  Next we
375	 * scan backwards looking for the start of arithmetic.  If the
376	 * next previous character is a CTLESC character, then we
377	 * have to rescan starting from the beginning since CTLESC
378	 * characters have to be processed left to right.
379	 */
380	CHECKSTRSPACE(DIGITS(result) - 2, expdest);
381	USTPUTC('\0', expdest);
382	start = stackblock();
383	p = expdest - 2;
384	while (p >= start && *p != CTLARI)
385		--p;
386	if (p < start || *p != CTLARI)
387		error("missing CTLARI (shouldn't happen)");
388	if (p > start && *(p - 1) == CTLESC)
389		for (p = start; *p != CTLARI; p++)
390			if (*p == CTLESC)
391				p++;
392
393	if (p[1] == '"')
394		quoted=1;
395	else
396		quoted=0;
397	begoff = p - start;
398	removerecordregions(begoff);
399	if (quotes)
400		rmescapes(p+2);
401	result = arith(p+2);
402	fmtstr(p, DIGITS(result), ARITH_FORMAT_STR, result);
403	while (*p++)
404		;
405	if (quoted == 0)
406		recordregion(begoff, p - 1 - start, 0);
407	result = expdest - p + 1;
408	STADJUST(-result, expdest);
409}
410
411
412/*
413 * Expand stuff in backwards quotes.
414 */
415
416STATIC void
417expbackq(union node *cmd, int quoted, int flag)
418{
419	struct backcmd in;
420	int i;
421	char buf[128];
422	char *p;
423	char *dest = expdest;
424	struct ifsregion saveifs, *savelastp;
425	struct nodelist *saveargbackq;
426	char lastc;
427	int startloc = dest - stackblock();
428	char const *syntax = quoted? DQSYNTAX : BASESYNTAX;
429	int saveherefd;
430	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
431	int nnl;
432
433	INTOFF;
434	saveifs = ifsfirst;
435	savelastp = ifslastp;
436	saveargbackq = argbackq;
437	saveherefd = herefd;
438	herefd = -1;
439	p = grabstackstr(dest);
440	evalbackcmd(cmd, &in);
441	ungrabstackstr(p, dest);
442	ifsfirst = saveifs;
443	ifslastp = savelastp;
444	argbackq = saveargbackq;
445	herefd = saveherefd;
446
447	p = in.buf;
448	lastc = '\0';
449	nnl = 0;
450	/* Don't copy trailing newlines */
451	for (;;) {
452		if (--in.nleft < 0) {
453			if (in.fd < 0)
454				break;
455			while ((i = read(in.fd, buf, sizeof buf)) < 0 && errno == EINTR);
456			TRACE(("expbackq: read returns %d\n", i));
457			if (i <= 0)
458				break;
459			p = buf;
460			in.nleft = i - 1;
461		}
462		lastc = *p++;
463		if (lastc != '\0') {
464			if (quotes && syntax[(int)lastc] == CCTL)
465				STPUTC(CTLESC, dest);
466			if (lastc == '\n') {
467				nnl++;
468			} else {
469				while (nnl > 0) {
470					nnl--;
471					STPUTC('\n', dest);
472				}
473				STPUTC(lastc, dest);
474			}
475		}
476	}
477
478	if (in.fd >= 0)
479		close(in.fd);
480	if (in.buf)
481		ckfree(in.buf);
482	if (in.jp)
483		exitstatus = waitforjob(in.jp, (int *)NULL);
484	if (quoted == 0)
485		recordregion(startloc, dest - stackblock(), 0);
486	TRACE(("evalbackq: size=%d: \"%.*s\"\n",
487		(dest - stackblock()) - startloc,
488		(dest - stackblock()) - startloc,
489		stackblock() + startloc));
490	expdest = dest;
491	INTON;
492}
493
494
495
496STATIC int
497subevalvar(char *p, char *str, int strloc, int subtype, int startloc,
498  int varflags)
499{
500	char *startp;
501	char *loc = NULL;
502	char *q;
503	int c = 0;
504	int saveherefd = herefd;
505	struct nodelist *saveargbackq = argbackq;
506	int amount;
507
508	herefd = -1;
509	argstr(p, subtype == VSTRIMLEFT || subtype == VSTRIMLEFTMAX ||
510	    subtype == VSTRIMRIGHT || subtype == VSTRIMRIGHTMAX ?
511	    EXP_CASE : 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(out2, "%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 = (unsigned char)*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 (varflags & VSLINENO) {
649		set = 1;
650		special = 0;
651		val = var;
652		p[-1] = '\0';	/* temporarily overwrite '=' to have \0
653				   terminated string */
654	} else if (special) {
655		set = varisset(var, varflags & VSNUL);
656		val = NULL;
657	} else {
658		val = bltinlookup(var, 1);
659		if (val == NULL || ((varflags & VSNUL) && val[0] == '\0')) {
660			val = NULL;
661			set = 0;
662		} else
663			set = 1;
664	}
665	varlen = 0;
666	startloc = expdest - stackblock();
667	if (!set && uflag && *var != '@' && *var != '*') {
668		switch (subtype) {
669		case VSNORMAL:
670		case VSTRIMLEFT:
671		case VSTRIMLEFTMAX:
672		case VSTRIMRIGHT:
673		case VSTRIMRIGHTMAX:
674		case VSLENGTH:
675			error("%.*s: parameter not set", (int)(p - var - 1),
676			    var);
677		}
678	}
679	if (set && subtype != VSPLUS) {
680		/* insert the value of the variable */
681		if (special) {
682			varvalue(var, varflags & VSQUOTE, subtype, flag);
683			if (subtype == VSLENGTH) {
684				varlen = expdest - stackblock() - startloc;
685				STADJUST(-varlen, expdest);
686			}
687		} else {
688			char const *syntax = (varflags & VSQUOTE) ? DQSYNTAX
689								  : BASESYNTAX;
690
691			if (subtype == VSLENGTH) {
692				for (;*val; val++)
693					varlen++;
694			}
695			else {
696				while (*val) {
697					if (quotes &&
698					    syntax[(int)*val] == CCTL)
699						STPUTC(CTLESC, expdest);
700					STPUTC(*val++, expdest);
701				}
702
703			}
704		}
705	}
706
707	if (subtype == VSPLUS)
708		set = ! set;
709
710	easy = ((varflags & VSQUOTE) == 0 ||
711		(*var == '@' && shellparam.nparam != 1));
712
713
714	switch (subtype) {
715	case VSLENGTH:
716		expdest = cvtnum(varlen, expdest);
717		goto record;
718
719	case VSNORMAL:
720		if (!easy)
721			break;
722record:
723		recordregion(startloc, expdest - stackblock(),
724			     varflags & VSQUOTE);
725		break;
726
727	case VSPLUS:
728	case VSMINUS:
729		if (!set) {
730			argstr(p, flag);
731			break;
732		}
733		if (easy)
734			goto record;
735		break;
736
737	case VSTRIMLEFT:
738	case VSTRIMLEFTMAX:
739	case VSTRIMRIGHT:
740	case VSTRIMRIGHTMAX:
741		if (!set)
742			break;
743		/*
744		 * Terminate the string and start recording the pattern
745		 * right after it
746		 */
747		STPUTC('\0', expdest);
748		patloc = expdest - stackblock();
749		if (subevalvar(p, NULL, patloc, subtype,
750			       startloc, varflags) == 0) {
751			int amount = (expdest - stackblock() - patloc) + 1;
752			STADJUST(-amount, expdest);
753		}
754		/* Remove any recorded regions beyond start of variable */
755		removerecordregions(startloc);
756		goto record;
757
758	case VSASSIGN:
759	case VSQUESTION:
760		if (!set) {
761			if (subevalvar(p, var, 0, subtype, startloc, varflags)) {
762				varflags &= ~VSNUL;
763				/*
764				 * Remove any recorded regions beyond
765				 * start of variable
766				 */
767				removerecordregions(startloc);
768				goto again;
769			}
770			break;
771		}
772		if (easy)
773			goto record;
774		break;
775
776	case VSERROR:
777		c = p - var - 1;
778		error("${%.*s%s}: Bad substitution", c, var,
779		    (c > 0 && *p != CTLENDVAR) ? "..." : "");
780
781	default:
782		abort();
783	}
784	p[-1] = '=';	/* recover overwritten '=' */
785
786	if (subtype != VSNORMAL) {	/* skip to end of alternative */
787		int nesting = 1;
788		for (;;) {
789			if ((c = *p++) == CTLESC)
790				p++;
791			else if (c == CTLBACKQ || c == (CTLBACKQ|CTLQUOTE)) {
792				if (set)
793					argbackq = argbackq->next;
794			} else if (c == CTLVAR) {
795				if ((*p++ & VSTYPE) != VSNORMAL)
796					nesting++;
797			} else if (c == CTLENDVAR) {
798				if (--nesting == 0)
799					break;
800			}
801		}
802	}
803	return p;
804}
805
806
807
808/*
809 * Test whether a specialized variable is set.
810 */
811
812STATIC int
813varisset(char *name, int nulok)
814{
815
816	if (*name == '!')
817		return backgndpid != -1;
818	else if (*name == '@' || *name == '*') {
819		if (*shellparam.p == NULL)
820			return 0;
821
822		if (nulok) {
823			char **av;
824
825			for (av = shellparam.p; *av; av++)
826				if (**av != '\0')
827					return 1;
828			return 0;
829		}
830	} else if (is_digit(*name)) {
831		char *ap;
832		int num = atoi(name);
833
834		if (num > shellparam.nparam)
835			return 0;
836
837		if (num == 0)
838			ap = arg0;
839		else
840			ap = shellparam.p[num - 1];
841
842		if (nulok && (ap == NULL || *ap == '\0'))
843			return 0;
844	}
845	return 1;
846}
847
848
849
850/*
851 * Add the value of a specialized variable to the stack string.
852 */
853
854STATIC void
855varvalue(char *name, int quoted, int subtype, int flag)
856{
857	int num;
858	char *p;
859	int i;
860	char sep;
861	char **ap;
862	char const *syntax;
863
864#define STRTODEST(p) \
865	do {\
866	if (flag & (EXP_FULL | EXP_CASE) && subtype != VSLENGTH) { \
867		syntax = quoted? DQSYNTAX : BASESYNTAX; \
868		while (*p) { \
869			if (syntax[(int)*p] == CCTL) \
870				STPUTC(CTLESC, expdest); \
871			STPUTC(*p++, expdest); \
872		} \
873	} else \
874		while (*p) \
875			STPUTC(*p++, expdest); \
876	} while (0)
877
878
879	switch (*name) {
880	case '$':
881		num = rootpid;
882		goto numvar;
883	case '?':
884		num = oexitstatus;
885		goto numvar;
886	case '#':
887		num = shellparam.nparam;
888		goto numvar;
889	case '!':
890		num = backgndpid;
891numvar:
892		expdest = cvtnum(num, expdest);
893		break;
894	case '-':
895		for (i = 0 ; i < NOPTS ; i++) {
896			if (optlist[i].val)
897				STPUTC(optlist[i].letter, expdest);
898		}
899		break;
900	case '@':
901		if (flag & EXP_FULL && quoted) {
902			for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
903				STRTODEST(p);
904				if (*ap)
905					STPUTC('\0', expdest);
906			}
907			break;
908		}
909		/* FALLTHROUGH */
910	case '*':
911		if (ifsset())
912			sep = ifsval()[0];
913		else
914			sep = ' ';
915		for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
916			STRTODEST(p);
917			if (*ap && sep)
918				STPUTC(sep, expdest);
919		}
920		break;
921	case '0':
922		p = arg0;
923		STRTODEST(p);
924		break;
925	default:
926		if (is_digit(*name)) {
927			num = atoi(name);
928			if (num > 0 && num <= shellparam.nparam) {
929				p = shellparam.p[num - 1];
930				STRTODEST(p);
931			}
932		}
933		break;
934	}
935}
936
937
938
939/*
940 * Record the the fact that we have to scan this region of the
941 * string for IFS characters.
942 */
943
944STATIC void
945recordregion(int start, int end, int inquotes)
946{
947	struct ifsregion *ifsp;
948
949	if (ifslastp == NULL) {
950		ifsp = &ifsfirst;
951	} else {
952		if (ifslastp->endoff == start
953		    && ifslastp->inquotes == inquotes) {
954			/* extend previous area */
955			ifslastp->endoff = end;
956			return;
957		}
958		ifsp = (struct ifsregion *)ckmalloc(sizeof (struct ifsregion));
959		ifslastp->next = ifsp;
960	}
961	ifslastp = ifsp;
962	ifslastp->next = NULL;
963	ifslastp->begoff = start;
964	ifslastp->endoff = end;
965	ifslastp->inquotes = inquotes;
966}
967
968
969
970/*
971 * Break the argument string into pieces based upon IFS and add the
972 * strings to the argument list.  The regions of the string to be
973 * searched for IFS characters have been stored by recordregion.
974 */
975STATIC void
976ifsbreakup(char *string, struct arglist *arglist)
977{
978	struct ifsregion *ifsp;
979	struct strlist *sp;
980	char *start;
981	char *p;
982	char *q;
983	const char *ifs;
984	const char *ifsspc;
985	int had_param_ch = 0;
986
987	start = string;
988
989	if (ifslastp == NULL) {
990		/* Return entire argument, IFS doesn't apply to any of it */
991		sp = (struct strlist *)stalloc(sizeof *sp);
992		sp->text = start;
993		*arglist->lastp = sp;
994		arglist->lastp = &sp->next;
995		return;
996	}
997
998	ifs = ifsset() ? ifsval() : " \t\n";
999
1000	for (ifsp = &ifsfirst; ifsp != NULL; ifsp = ifsp->next) {
1001		p = string + ifsp->begoff;
1002		while (p < string + ifsp->endoff) {
1003			q = p;
1004			if (*p == CTLESC)
1005				p++;
1006			if (ifsp->inquotes) {
1007				/* Only NULs (should be from "$@") end args */
1008				had_param_ch = 1;
1009				if (*p != 0) {
1010					p++;
1011					continue;
1012				}
1013				ifsspc = NULL;
1014			} else {
1015				if (!strchr(ifs, *p)) {
1016					had_param_ch = 1;
1017					p++;
1018					continue;
1019				}
1020				ifsspc = strchr(" \t\n", *p);
1021
1022				/* Ignore IFS whitespace at start */
1023				if (q == start && ifsspc != NULL) {
1024					p++;
1025					start = p;
1026					continue;
1027				}
1028				had_param_ch = 0;
1029			}
1030
1031			/* Save this argument... */
1032			*q = '\0';
1033			sp = (struct strlist *)stalloc(sizeof *sp);
1034			sp->text = start;
1035			*arglist->lastp = sp;
1036			arglist->lastp = &sp->next;
1037			p++;
1038
1039			if (ifsspc != NULL) {
1040				/* Ignore further trailing IFS whitespace */
1041				for (; p < string + ifsp->endoff; p++) {
1042					q = p;
1043					if (*p == CTLESC)
1044						p++;
1045					if (strchr(ifs, *p) == NULL) {
1046						p = q;
1047						break;
1048					}
1049					if (strchr(" \t\n", *p) == NULL) {
1050						p++;
1051						break;
1052					}
1053				}
1054			}
1055			start = p;
1056		}
1057	}
1058
1059	/*
1060	 * Save anything left as an argument.
1061	 * Traditionally we have treated 'IFS=':'; set -- x$IFS' as
1062	 * generating 2 arguments, the second of which is empty.
1063	 * Some recent clarification of the Posix spec say that it
1064	 * should only generate one....
1065	 */
1066	if (had_param_ch || *start != 0) {
1067		sp = (struct strlist *)stalloc(sizeof *sp);
1068		sp->text = start;
1069		*arglist->lastp = sp;
1070		arglist->lastp = &sp->next;
1071	}
1072}
1073
1074
1075
1076/*
1077 * Expand shell metacharacters.  At this point, the only control characters
1078 * should be escapes.  The results are stored in the list exparg.
1079 */
1080
1081STATIC char *expdir;
1082
1083
1084STATIC void
1085expandmeta(struct strlist *str, int flag __unused)
1086{
1087	char *p;
1088	struct strlist **savelastp;
1089	struct strlist *sp;
1090	char c;
1091	/* TODO - EXP_REDIR */
1092
1093	while (str) {
1094		if (fflag)
1095			goto nometa;
1096		p = str->text;
1097		for (;;) {			/* fast check for meta chars */
1098			if ((c = *p++) == '\0')
1099				goto nometa;
1100			if (c == '*' || c == '?' || c == '[' || c == '!')
1101				break;
1102		}
1103		savelastp = exparg.lastp;
1104		INTOFF;
1105		if (expdir == NULL) {
1106			int i = strlen(str->text);
1107			expdir = ckmalloc(i < 2048 ? 2048 : i); /* XXX */
1108		}
1109
1110		expmeta(expdir, str->text);
1111		ckfree(expdir);
1112		expdir = NULL;
1113		INTON;
1114		if (exparg.lastp == savelastp) {
1115			/*
1116			 * no matches
1117			 */
1118nometa:
1119			*exparg.lastp = str;
1120			rmescapes(str->text);
1121			exparg.lastp = &str->next;
1122		} else {
1123			*exparg.lastp = NULL;
1124			*savelastp = sp = expsort(*savelastp);
1125			while (sp->next != NULL)
1126				sp = sp->next;
1127			exparg.lastp = &sp->next;
1128		}
1129		str = str->next;
1130	}
1131}
1132
1133
1134/*
1135 * Do metacharacter (i.e. *, ?, [...]) expansion.
1136 */
1137
1138STATIC void
1139expmeta(char *enddir, char *name)
1140{
1141	char *p;
1142	char *q;
1143	char *start;
1144	char *endname;
1145	int metaflag;
1146	struct stat statb;
1147	DIR *dirp;
1148	struct dirent *dp;
1149	int atend;
1150	int matchdot;
1151
1152	metaflag = 0;
1153	start = name;
1154	for (p = name ; ; p++) {
1155		if (*p == '*' || *p == '?')
1156			metaflag = 1;
1157		else if (*p == '[') {
1158			q = p + 1;
1159			if (*q == '!' || *q == '^')
1160				q++;
1161			for (;;) {
1162				while (*q == CTLQUOTEMARK)
1163					q++;
1164				if (*q == CTLESC)
1165					q++;
1166				if (*q == '/' || *q == '\0')
1167					break;
1168				if (*++q == ']') {
1169					metaflag = 1;
1170					break;
1171				}
1172			}
1173		} else if (*p == '!' && p[1] == '!'	&& (p == name || p[-1] == '/')) {
1174			metaflag = 1;
1175		} else if (*p == '\0')
1176			break;
1177		else if (*p == CTLQUOTEMARK)
1178			continue;
1179		else if (*p == CTLESC)
1180			p++;
1181		if (*p == '/') {
1182			if (metaflag)
1183				break;
1184			start = p + 1;
1185		}
1186	}
1187	if (metaflag == 0) {	/* we've reached the end of the file name */
1188		if (enddir != expdir)
1189			metaflag++;
1190		for (p = name ; ; p++) {
1191			if (*p == CTLQUOTEMARK)
1192				continue;
1193			if (*p == CTLESC)
1194				p++;
1195			*enddir++ = *p;
1196			if (*p == '\0')
1197				break;
1198		}
1199		if (metaflag == 0 || lstat(expdir, &statb) >= 0)
1200			addfname(expdir);
1201		return;
1202	}
1203	endname = p;
1204	if (start != name) {
1205		p = name;
1206		while (p < start) {
1207			while (*p == CTLQUOTEMARK)
1208				p++;
1209			if (*p == CTLESC)
1210				p++;
1211			*enddir++ = *p++;
1212		}
1213	}
1214	if (enddir == expdir) {
1215		p = ".";
1216	} else if (enddir == expdir + 1 && *expdir == '/') {
1217		p = "/";
1218	} else {
1219		p = expdir;
1220		enddir[-1] = '\0';
1221	}
1222	if ((dirp = opendir(p)) == NULL)
1223		return;
1224	if (enddir != expdir)
1225		enddir[-1] = '/';
1226	if (*endname == 0) {
1227		atend = 1;
1228	} else {
1229		atend = 0;
1230		*endname++ = '\0';
1231	}
1232	matchdot = 0;
1233	p = start;
1234	while (*p == CTLQUOTEMARK)
1235		p++;
1236	if (*p == CTLESC)
1237		p++;
1238	if (*p == '.')
1239		matchdot++;
1240	while (! int_pending() && (dp = readdir(dirp)) != NULL) {
1241		if (dp->d_name[0] == '.' && ! matchdot)
1242			continue;
1243		if (patmatch(start, dp->d_name, 0)) {
1244			if (atend) {
1245				scopy(dp->d_name, enddir);
1246				addfname(expdir);
1247			} else {
1248				for (p = enddir, q = dp->d_name;
1249				     (*p++ = *q++) != '\0';)
1250					continue;
1251				p[-1] = '/';
1252				expmeta(p, endname);
1253			}
1254		}
1255	}
1256	closedir(dirp);
1257	if (! atend)
1258		endname[-1] = '/';
1259}
1260
1261
1262/*
1263 * Add a file name to the list.
1264 */
1265
1266STATIC void
1267addfname(char *name)
1268{
1269	char *p;
1270	struct strlist *sp;
1271
1272	p = stalloc(strlen(name) + 1);
1273	scopy(name, p);
1274	sp = (struct strlist *)stalloc(sizeof *sp);
1275	sp->text = p;
1276	*exparg.lastp = sp;
1277	exparg.lastp = &sp->next;
1278}
1279
1280
1281/*
1282 * Sort the results of file name expansion.  It calculates the number of
1283 * strings to sort and then calls msort (short for merge sort) to do the
1284 * work.
1285 */
1286
1287STATIC struct strlist *
1288expsort(struct strlist *str)
1289{
1290	int len;
1291	struct strlist *sp;
1292
1293	len = 0;
1294	for (sp = str ; sp ; sp = sp->next)
1295		len++;
1296	return msort(str, len);
1297}
1298
1299
1300STATIC struct strlist *
1301msort(struct strlist *list, int len)
1302{
1303	struct strlist *p, *q = NULL;
1304	struct strlist **lpp;
1305	int half;
1306	int n;
1307
1308	if (len <= 1)
1309		return list;
1310	half = len >> 1;
1311	p = list;
1312	for (n = half ; --n >= 0 ; ) {
1313		q = p;
1314		p = p->next;
1315	}
1316	q->next = NULL;			/* terminate first half of list */
1317	q = msort(list, half);		/* sort first half of list */
1318	p = msort(p, len - half);		/* sort second half */
1319	lpp = &list;
1320	for (;;) {
1321		if (strcmp(p->text, q->text) < 0) {
1322			*lpp = p;
1323			lpp = &p->next;
1324			if ((p = *lpp) == NULL) {
1325				*lpp = q;
1326				break;
1327			}
1328		} else {
1329			*lpp = q;
1330			lpp = &q->next;
1331			if ((q = *lpp) == NULL) {
1332				*lpp = p;
1333				break;
1334			}
1335		}
1336	}
1337	return list;
1338}
1339
1340
1341
1342/*
1343 * Returns true if the pattern matches the string.
1344 */
1345
1346int
1347patmatch(const char *pattern, const char *string, int squoted)
1348{
1349#ifdef notdef
1350	if (pattern[0] == '!' && pattern[1] == '!')
1351		return 1 - pmatch(pattern + 2, string);
1352	else
1353#endif
1354		return pmatch(pattern, string, squoted);
1355}
1356
1357
1358STATIC int
1359pmatch(const char *pattern, const char *string, int squoted)
1360{
1361	const char *p, *q;
1362	char c;
1363
1364	p = pattern;
1365	q = string;
1366	for (;;) {
1367		switch (c = *p++) {
1368		case '\0':
1369			goto breakloop;
1370		case CTLESC:
1371			if (squoted && *q == CTLESC)
1372				q++;
1373			if (*q++ != *p++)
1374				return 0;
1375			break;
1376		case CTLQUOTEMARK:
1377			continue;
1378		case '?':
1379			if (squoted && *q == CTLESC)
1380				q++;
1381			if (*q++ == '\0')
1382				return 0;
1383			break;
1384		case '*':
1385			c = *p;
1386			while (c == CTLQUOTEMARK || c == '*')
1387				c = *++p;
1388			if (c != CTLESC &&  c != CTLQUOTEMARK &&
1389			    c != '?' && c != '*' && c != '[') {
1390				while (*q != c) {
1391					if (squoted && *q == CTLESC &&
1392					    q[1] == c)
1393						break;
1394					if (*q == '\0')
1395						return 0;
1396					if (squoted && *q == CTLESC)
1397						q++;
1398					q++;
1399				}
1400			}
1401			do {
1402				if (pmatch(p, q, squoted))
1403					return 1;
1404				if (squoted && *q == CTLESC)
1405					q++;
1406			} while (*q++ != '\0');
1407			return 0;
1408		case '[': {
1409			const char *endp;
1410			int invert, found;
1411			char chr;
1412
1413			endp = p;
1414			if (*endp == '!' || *endp == '^')
1415				endp++;
1416			for (;;) {
1417				while (*endp == CTLQUOTEMARK)
1418					endp++;
1419				if (*endp == '\0')
1420					goto dft;		/* no matching ] */
1421				if (*endp == CTLESC)
1422					endp++;
1423				if (*++endp == ']')
1424					break;
1425			}
1426			invert = 0;
1427			if (*p == '!' || *p == '^') {
1428				invert++;
1429				p++;
1430			}
1431			found = 0;
1432			chr = *q++;
1433			if (squoted && chr == CTLESC)
1434				chr = *q++;
1435			if (chr == '\0')
1436				return 0;
1437			c = *p++;
1438			do {
1439				if (c == CTLQUOTEMARK)
1440					continue;
1441				if (c == CTLESC)
1442					c = *p++;
1443				if (*p == '-' && p[1] != ']') {
1444					p++;
1445					while (*p == CTLQUOTEMARK)
1446						p++;
1447					if (*p == CTLESC)
1448						p++;
1449					if (   collate_range_cmp(chr, c) >= 0
1450					    && collate_range_cmp(chr, *p) <= 0
1451					   )
1452						found = 1;
1453					p++;
1454				} else {
1455					if (chr == c)
1456						found = 1;
1457				}
1458			} while ((c = *p++) != ']');
1459			if (found == invert)
1460				return 0;
1461			break;
1462		}
1463dft:	        default:
1464			if (squoted && *q == CTLESC)
1465				q++;
1466			if (*q++ != c)
1467				return 0;
1468			break;
1469		}
1470	}
1471breakloop:
1472	if (*q != '\0')
1473		return 0;
1474	return 1;
1475}
1476
1477
1478
1479/*
1480 * Remove any CTLESC characters from a string.
1481 */
1482
1483void
1484rmescapes(char *str)
1485{
1486	char *p, *q;
1487
1488	p = str;
1489	while (*p != CTLESC && *p != CTLQUOTEMARK) {
1490		if (*p++ == '\0')
1491			return;
1492	}
1493	q = p;
1494	while (*p) {
1495		if (*p == CTLQUOTEMARK) {
1496			p++;
1497			continue;
1498		}
1499		if (*p == CTLESC)
1500			p++;
1501		*q++ = *p++;
1502	}
1503	*q = '\0';
1504}
1505
1506
1507
1508/*
1509 * See if a pattern matches in a case statement.
1510 */
1511
1512int
1513casematch(union node *pattern, const char *val)
1514{
1515	struct stackmark smark;
1516	int result;
1517	char *p;
1518
1519	setstackmark(&smark);
1520	argbackq = pattern->narg.backquote;
1521	STARTSTACKSTR(expdest);
1522	ifslastp = NULL;
1523	argstr(pattern->narg.text, EXP_TILDE | EXP_CASE);
1524	STPUTC('\0', expdest);
1525	p = grabstackstr(expdest);
1526	result = patmatch(p, val, 0);
1527	popstackmark(&smark);
1528	return result;
1529}
1530
1531/*
1532 * Our own itoa().
1533 */
1534
1535STATIC char *
1536cvtnum(int num, char *buf)
1537{
1538	char temp[32];
1539	int neg = num < 0;
1540	char *p = temp + 31;
1541
1542	temp[31] = '\0';
1543
1544	do {
1545		*--p = num % 10 + '0';
1546	} while ((num /= 10) != 0);
1547
1548	if (neg)
1549		*--p = '-';
1550
1551	while (*p)
1552		STPUTC(*p++, buf);
1553	return buf;
1554}
1555
1556/*
1557 * Do most of the work for wordexp(3).
1558 */
1559
1560int
1561wordexpcmd(int argc, char **argv)
1562{
1563	size_t len;
1564	int i;
1565
1566	out1fmt("%08x", argc - 1);
1567	for (i = 1, len = 0; i < argc; i++)
1568		len += strlen(argv[i]);
1569	out1fmt("%08x", (int)len);
1570	for (i = 1; i < argc; i++) {
1571		out1str(argv[i]);
1572		out1c('\0');
1573	}
1574        return (0);
1575}
1576