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