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