xref: /freebsd/bin/sh/expand.c (revision 1e413cf93298b5b97441a21d9a50fdcd0ee9945e)
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
35 static char sccsid[] = "@(#)expand.c	8.5 (Berkeley) 5/15/95";
36 #endif
37 #endif /* not lint */
38 #include <sys/cdefs.h>
39 __FBSDID("$FreeBSD$");
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 
81 struct 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 
89 STATIC char *expdest;			/* output of current string */
90 STATIC struct nodelist *argbackq;	/* list of back quote expressions */
91 STATIC struct ifsregion ifsfirst;	/* first struct in list of ifs regions */
92 STATIC struct ifsregion *ifslastp;	/* last struct in list */
93 STATIC struct arglist exparg;		/* holds expanded arg list */
94 
95 STATIC void argstr(char *, int);
96 STATIC char *exptilde(char *, int);
97 STATIC void expbackq(union node *, int, int);
98 STATIC int subevalvar(char *, char *, int, int, int, int);
99 STATIC char *evalvar(char *, int);
100 STATIC int varisset(char *, int);
101 STATIC void varvalue(char *, int, int, int);
102 STATIC void recordregion(int, int, int);
103 STATIC void removerecordregions(int);
104 STATIC void ifsbreakup(char *, struct arglist *);
105 STATIC void expandmeta(struct strlist *, int);
106 STATIC void expmeta(char *, char *);
107 STATIC void addfname(char *);
108 STATIC struct strlist *expsort(struct strlist *);
109 STATIC struct strlist *msort(struct strlist *, int);
110 STATIC int pmatch(char *, char *, int);
111 STATIC char *cvtnum(int, char *);
112 STATIC int collate_range_cmp(int, int);
113 
114 STATIC int
115 collate_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 
130 void
131 expandhere(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 
146 void
147 expandarg(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 
202 STATIC void
203 argstr(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 	}
261 breakloop:;
262 }
263 
264 STATIC char *
265 exptilde(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 	}
287 done:
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);
306 lose:
307 	*p = c;
308 	return (startp);
309 }
310 
311 
312 STATIC void
313 removerecordregions(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  */
355 void
356 expari(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 
414 STATIC void
415 expbackq(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 
494 STATIC int
495 subevalvar(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 
606 recordleft:
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 
620 STATIC char *
621 evalvar(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 = (unsigned char)*p++;
637 	subtype = varflags & VSTYPE;
638 	var = p;
639 	special = 0;
640 	if (! is_name(*p))
641 		special = 1;
642 	p = strchr(p, '=') + 1;
643 again: /* 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, subtype, flag);
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;
712 record:
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 	case VSERROR:
767 		c = p - var - 1;
768 		error("${%.*s%s}: Bad substitution", c, var,
769 		    (c > 0 && *p != CTLENDVAR) ? "..." : "");
770 
771 	default:
772 		abort();
773 	}
774 
775 	if (subtype != VSNORMAL) {	/* skip to end of alternative */
776 		int nesting = 1;
777 		for (;;) {
778 			if ((c = *p++) == CTLESC)
779 				p++;
780 			else if (c == CTLBACKQ || c == (CTLBACKQ|CTLQUOTE)) {
781 				if (set)
782 					argbackq = argbackq->next;
783 			} else if (c == CTLVAR) {
784 				if ((*p++ & VSTYPE) != VSNORMAL)
785 					nesting++;
786 			} else if (c == CTLENDVAR) {
787 				if (--nesting == 0)
788 					break;
789 			}
790 		}
791 	}
792 	return p;
793 }
794 
795 
796 
797 /*
798  * Test whether a specialized variable is set.
799  */
800 
801 STATIC int
802 varisset(char *name, int nulok)
803 {
804 
805 	if (*name == '!')
806 		return backgndpid != -1;
807 	else if (*name == '@' || *name == '*') {
808 		if (*shellparam.p == NULL)
809 			return 0;
810 
811 		if (nulok) {
812 			char **av;
813 
814 			for (av = shellparam.p; *av; av++)
815 				if (**av != '\0')
816 					return 1;
817 			return 0;
818 		}
819 	} else if (is_digit(*name)) {
820 		char *ap;
821 		int num = atoi(name);
822 
823 		if (num > shellparam.nparam)
824 			return 0;
825 
826 		if (num == 0)
827 			ap = arg0;
828 		else
829 			ap = shellparam.p[num - 1];
830 
831 		if (nulok && (ap == NULL || *ap == '\0'))
832 			return 0;
833 	}
834 	return 1;
835 }
836 
837 
838 
839 /*
840  * Add the value of a specialized variable to the stack string.
841  */
842 
843 STATIC void
844 varvalue(char *name, int quoted, int subtype, int flag)
845 {
846 	int num;
847 	char *p;
848 	int i;
849 	extern int oexitstatus;
850 	char sep;
851 	char **ap;
852 	char const *syntax;
853 
854 #define STRTODEST(p) \
855 	do {\
856 	if (flag & (EXP_FULL | EXP_CASE) && subtype != VSLENGTH) { \
857 		syntax = quoted? DQSYNTAX : BASESYNTAX; \
858 		while (*p) { \
859 			if (syntax[(int)*p] == CCTL) \
860 				STPUTC(CTLESC, expdest); \
861 			STPUTC(*p++, expdest); \
862 		} \
863 	} else \
864 		while (*p) \
865 			STPUTC(*p++, expdest); \
866 	} while (0)
867 
868 
869 	switch (*name) {
870 	case '$':
871 		num = rootpid;
872 		goto numvar;
873 	case '?':
874 		num = oexitstatus;
875 		goto numvar;
876 	case '#':
877 		num = shellparam.nparam;
878 		goto numvar;
879 	case '!':
880 		num = backgndpid;
881 numvar:
882 		expdest = cvtnum(num, expdest);
883 		break;
884 	case '-':
885 		for (i = 0 ; i < NOPTS ; i++) {
886 			if (optlist[i].val)
887 				STPUTC(optlist[i].letter, expdest);
888 		}
889 		break;
890 	case '@':
891 		if (flag & EXP_FULL && quoted) {
892 			for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
893 				STRTODEST(p);
894 				if (*ap)
895 					STPUTC('\0', expdest);
896 			}
897 			break;
898 		}
899 		/* FALLTHROUGH */
900 	case '*':
901 		if (ifsset())
902 			sep = ifsval()[0];
903 		else
904 			sep = ' ';
905 		for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
906 			STRTODEST(p);
907 			if (*ap && sep)
908 				STPUTC(sep, expdest);
909 		}
910 		break;
911 	case '0':
912 		p = arg0;
913 		STRTODEST(p);
914 		break;
915 	default:
916 		if (is_digit(*name)) {
917 			num = atoi(name);
918 			if (num > 0 && num <= shellparam.nparam) {
919 				p = shellparam.p[num - 1];
920 				STRTODEST(p);
921 			}
922 		}
923 		break;
924 	}
925 }
926 
927 
928 
929 /*
930  * Record the the fact that we have to scan this region of the
931  * string for IFS characters.
932  */
933 
934 STATIC void
935 recordregion(int start, int end, int nulonly)
936 {
937 	struct ifsregion *ifsp;
938 
939 	if (ifslastp == NULL) {
940 		ifsp = &ifsfirst;
941 	} else {
942 		ifsp = (struct ifsregion *)ckmalloc(sizeof (struct ifsregion));
943 		ifslastp->next = ifsp;
944 	}
945 	ifslastp = ifsp;
946 	ifslastp->next = NULL;
947 	ifslastp->begoff = start;
948 	ifslastp->endoff = end;
949 	ifslastp->nulonly = nulonly;
950 }
951 
952 
953 
954 /*
955  * Break the argument string into pieces based upon IFS and add the
956  * strings to the argument list.  The regions of the string to be
957  * searched for IFS characters have been stored by recordregion.
958  */
959 STATIC void
960 ifsbreakup(char *string, struct arglist *arglist)
961 {
962 	struct ifsregion *ifsp;
963 	struct strlist *sp;
964 	char *start;
965 	char *p;
966 	char *q;
967 	char *ifs;
968 	int ifsspc;
969 	int nulonly;
970 
971 
972 	start = string;
973 	ifsspc = 0;
974 	nulonly = 0;
975 	if (ifslastp != NULL) {
976 		ifsp = &ifsfirst;
977 		do {
978 			p = string + ifsp->begoff;
979 			nulonly = ifsp->nulonly;
980 			ifs = nulonly ? nullstr :
981 				( ifsset() ? ifsval() : " \t\n" );
982 			ifsspc = 0;
983 			while (p < string + ifsp->endoff) {
984 				q = p;
985 				if (*p == CTLESC)
986 					p++;
987 				if (strchr(ifs, *p)) {
988 					if (!nulonly)
989 						ifsspc = (strchr(" \t\n", *p) != NULL);
990 					/* Ignore IFS whitespace at start */
991 					if (q == start && ifsspc) {
992 						p++;
993 						start = p;
994 						continue;
995 					}
996 					*q = '\0';
997 					sp = (struct strlist *)stalloc(sizeof *sp);
998 					sp->text = start;
999 					*arglist->lastp = sp;
1000 					arglist->lastp = &sp->next;
1001 					p++;
1002 					if (!nulonly) {
1003 						for (;;) {
1004 							if (p >= string + ifsp->endoff) {
1005 								break;
1006 							}
1007 							q = p;
1008 							if (*p == CTLESC)
1009 								p++;
1010 							if (strchr(ifs, *p) == NULL ) {
1011 								p = q;
1012 								break;
1013 							} else if (strchr(" \t\n",*p) == NULL) {
1014 								if (ifsspc) {
1015 									p++;
1016 									ifsspc = 0;
1017 								} else {
1018 									p = q;
1019 									break;
1020 								}
1021 							} else
1022 								p++;
1023 						}
1024 					}
1025 					start = p;
1026 				} else
1027 					p++;
1028 			}
1029 		} while ((ifsp = ifsp->next) != NULL);
1030 		if (*start || (!ifsspc && start > string)) {
1031 			sp = (struct strlist *)stalloc(sizeof *sp);
1032 			sp->text = start;
1033 			*arglist->lastp = sp;
1034 			arglist->lastp = &sp->next;
1035 		}
1036 	} else {
1037 		sp = (struct strlist *)stalloc(sizeof *sp);
1038 		sp->text = start;
1039 		*arglist->lastp = sp;
1040 		arglist->lastp = &sp->next;
1041 	}
1042 }
1043 
1044 
1045 
1046 /*
1047  * Expand shell metacharacters.  At this point, the only control characters
1048  * should be escapes.  The results are stored in the list exparg.
1049  */
1050 
1051 STATIC char *expdir;
1052 
1053 
1054 STATIC void
1055 expandmeta(struct strlist *str, int flag __unused)
1056 {
1057 	char *p;
1058 	struct strlist **savelastp;
1059 	struct strlist *sp;
1060 	char c;
1061 	/* TODO - EXP_REDIR */
1062 
1063 	while (str) {
1064 		if (fflag)
1065 			goto nometa;
1066 		p = str->text;
1067 		for (;;) {			/* fast check for meta chars */
1068 			if ((c = *p++) == '\0')
1069 				goto nometa;
1070 			if (c == '*' || c == '?' || c == '[' || c == '!')
1071 				break;
1072 		}
1073 		savelastp = exparg.lastp;
1074 		INTOFF;
1075 		if (expdir == NULL) {
1076 			int i = strlen(str->text);
1077 			expdir = ckmalloc(i < 2048 ? 2048 : i); /* XXX */
1078 		}
1079 
1080 		expmeta(expdir, str->text);
1081 		ckfree(expdir);
1082 		expdir = NULL;
1083 		INTON;
1084 		if (exparg.lastp == savelastp) {
1085 			/*
1086 			 * no matches
1087 			 */
1088 nometa:
1089 			*exparg.lastp = str;
1090 			rmescapes(str->text);
1091 			exparg.lastp = &str->next;
1092 		} else {
1093 			*exparg.lastp = NULL;
1094 			*savelastp = sp = expsort(*savelastp);
1095 			while (sp->next != NULL)
1096 				sp = sp->next;
1097 			exparg.lastp = &sp->next;
1098 		}
1099 		str = str->next;
1100 	}
1101 }
1102 
1103 
1104 /*
1105  * Do metacharacter (i.e. *, ?, [...]) expansion.
1106  */
1107 
1108 STATIC void
1109 expmeta(char *enddir, char *name)
1110 {
1111 	char *p;
1112 	char *q;
1113 	char *start;
1114 	char *endname;
1115 	int metaflag;
1116 	struct stat statb;
1117 	DIR *dirp;
1118 	struct dirent *dp;
1119 	int atend;
1120 	int matchdot;
1121 
1122 	metaflag = 0;
1123 	start = name;
1124 	for (p = name ; ; p++) {
1125 		if (*p == '*' || *p == '?')
1126 			metaflag = 1;
1127 		else if (*p == '[') {
1128 			q = p + 1;
1129 			if (*q == '!' || *q == '^')
1130 				q++;
1131 			for (;;) {
1132 				while (*q == CTLQUOTEMARK)
1133 					q++;
1134 				if (*q == CTLESC)
1135 					q++;
1136 				if (*q == '/' || *q == '\0')
1137 					break;
1138 				if (*++q == ']') {
1139 					metaflag = 1;
1140 					break;
1141 				}
1142 			}
1143 		} else if (*p == '!' && p[1] == '!'	&& (p == name || p[-1] == '/')) {
1144 			metaflag = 1;
1145 		} else if (*p == '\0')
1146 			break;
1147 		else if (*p == CTLQUOTEMARK)
1148 			continue;
1149 		else if (*p == CTLESC)
1150 			p++;
1151 		if (*p == '/') {
1152 			if (metaflag)
1153 				break;
1154 			start = p + 1;
1155 		}
1156 	}
1157 	if (metaflag == 0) {	/* we've reached the end of the file name */
1158 		if (enddir != expdir)
1159 			metaflag++;
1160 		for (p = name ; ; p++) {
1161 			if (*p == CTLQUOTEMARK)
1162 				continue;
1163 			if (*p == CTLESC)
1164 				p++;
1165 			*enddir++ = *p;
1166 			if (*p == '\0')
1167 				break;
1168 		}
1169 		if (metaflag == 0 || lstat(expdir, &statb) >= 0)
1170 			addfname(expdir);
1171 		return;
1172 	}
1173 	endname = p;
1174 	if (start != name) {
1175 		p = name;
1176 		while (p < start) {
1177 			while (*p == CTLQUOTEMARK)
1178 				p++;
1179 			if (*p == CTLESC)
1180 				p++;
1181 			*enddir++ = *p++;
1182 		}
1183 	}
1184 	if (enddir == expdir) {
1185 		p = ".";
1186 	} else if (enddir == expdir + 1 && *expdir == '/') {
1187 		p = "/";
1188 	} else {
1189 		p = expdir;
1190 		enddir[-1] = '\0';
1191 	}
1192 	if ((dirp = opendir(p)) == NULL)
1193 		return;
1194 	if (enddir != expdir)
1195 		enddir[-1] = '/';
1196 	if (*endname == 0) {
1197 		atend = 1;
1198 	} else {
1199 		atend = 0;
1200 		*endname++ = '\0';
1201 	}
1202 	matchdot = 0;
1203 	p = start;
1204 	while (*p == CTLQUOTEMARK)
1205 		p++;
1206 	if (*p == CTLESC)
1207 		p++;
1208 	if (*p == '.')
1209 		matchdot++;
1210 	while (! int_pending() && (dp = readdir(dirp)) != NULL) {
1211 		if (dp->d_name[0] == '.' && ! matchdot)
1212 			continue;
1213 		if (patmatch(start, dp->d_name, 0)) {
1214 			if (atend) {
1215 				scopy(dp->d_name, enddir);
1216 				addfname(expdir);
1217 			} else {
1218 				for (p = enddir, q = dp->d_name;
1219 				     (*p++ = *q++) != '\0';)
1220 					continue;
1221 				p[-1] = '/';
1222 				expmeta(p, endname);
1223 			}
1224 		}
1225 	}
1226 	closedir(dirp);
1227 	if (! atend)
1228 		endname[-1] = '/';
1229 }
1230 
1231 
1232 /*
1233  * Add a file name to the list.
1234  */
1235 
1236 STATIC void
1237 addfname(char *name)
1238 {
1239 	char *p;
1240 	struct strlist *sp;
1241 
1242 	p = stalloc(strlen(name) + 1);
1243 	scopy(name, p);
1244 	sp = (struct strlist *)stalloc(sizeof *sp);
1245 	sp->text = p;
1246 	*exparg.lastp = sp;
1247 	exparg.lastp = &sp->next;
1248 }
1249 
1250 
1251 /*
1252  * Sort the results of file name expansion.  It calculates the number of
1253  * strings to sort and then calls msort (short for merge sort) to do the
1254  * work.
1255  */
1256 
1257 STATIC struct strlist *
1258 expsort(struct strlist *str)
1259 {
1260 	int len;
1261 	struct strlist *sp;
1262 
1263 	len = 0;
1264 	for (sp = str ; sp ; sp = sp->next)
1265 		len++;
1266 	return msort(str, len);
1267 }
1268 
1269 
1270 STATIC struct strlist *
1271 msort(struct strlist *list, int len)
1272 {
1273 	struct strlist *p, *q = NULL;
1274 	struct strlist **lpp;
1275 	int half;
1276 	int n;
1277 
1278 	if (len <= 1)
1279 		return list;
1280 	half = len >> 1;
1281 	p = list;
1282 	for (n = half ; --n >= 0 ; ) {
1283 		q = p;
1284 		p = p->next;
1285 	}
1286 	q->next = NULL;			/* terminate first half of list */
1287 	q = msort(list, half);		/* sort first half of list */
1288 	p = msort(p, len - half);		/* sort second half */
1289 	lpp = &list;
1290 	for (;;) {
1291 		if (strcmp(p->text, q->text) < 0) {
1292 			*lpp = p;
1293 			lpp = &p->next;
1294 			if ((p = *lpp) == NULL) {
1295 				*lpp = q;
1296 				break;
1297 			}
1298 		} else {
1299 			*lpp = q;
1300 			lpp = &q->next;
1301 			if ((q = *lpp) == NULL) {
1302 				*lpp = p;
1303 				break;
1304 			}
1305 		}
1306 	}
1307 	return list;
1308 }
1309 
1310 
1311 
1312 /*
1313  * Returns true if the pattern matches the string.
1314  */
1315 
1316 int
1317 patmatch(char *pattern, char *string, int squoted)
1318 {
1319 #ifdef notdef
1320 	if (pattern[0] == '!' && pattern[1] == '!')
1321 		return 1 - pmatch(pattern + 2, string);
1322 	else
1323 #endif
1324 		return pmatch(pattern, string, squoted);
1325 }
1326 
1327 
1328 STATIC int
1329 pmatch(char *pattern, char *string, int squoted)
1330 {
1331 	char *p, *q;
1332 	char c;
1333 
1334 	p = pattern;
1335 	q = string;
1336 	for (;;) {
1337 		switch (c = *p++) {
1338 		case '\0':
1339 			goto breakloop;
1340 		case CTLESC:
1341 			if (squoted && *q == CTLESC)
1342 				q++;
1343 			if (*q++ != *p++)
1344 				return 0;
1345 			break;
1346 		case CTLQUOTEMARK:
1347 			continue;
1348 		case '?':
1349 			if (squoted && *q == CTLESC)
1350 				q++;
1351 			if (*q++ == '\0')
1352 				return 0;
1353 			break;
1354 		case '*':
1355 			c = *p;
1356 			while (c == CTLQUOTEMARK || c == '*')
1357 				c = *++p;
1358 			if (c != CTLESC &&  c != CTLQUOTEMARK &&
1359 			    c != '?' && c != '*' && c != '[') {
1360 				while (*q != c) {
1361 					if (squoted && *q == CTLESC &&
1362 					    q[1] == c)
1363 						break;
1364 					if (*q == '\0')
1365 						return 0;
1366 					if (squoted && *q == CTLESC)
1367 						q++;
1368 					q++;
1369 				}
1370 			}
1371 			do {
1372 				if (pmatch(p, q, squoted))
1373 					return 1;
1374 				if (squoted && *q == CTLESC)
1375 					q++;
1376 			} while (*q++ != '\0');
1377 			return 0;
1378 		case '[': {
1379 			char *endp;
1380 			int invert, found;
1381 			char chr;
1382 
1383 			endp = p;
1384 			if (*endp == '!' || *endp == '^')
1385 				endp++;
1386 			for (;;) {
1387 				while (*endp == CTLQUOTEMARK)
1388 					endp++;
1389 				if (*endp == '\0')
1390 					goto dft;		/* no matching ] */
1391 				if (*endp == CTLESC)
1392 					endp++;
1393 				if (*++endp == ']')
1394 					break;
1395 			}
1396 			invert = 0;
1397 			if (*p == '!' || *p == '^') {
1398 				invert++;
1399 				p++;
1400 			}
1401 			found = 0;
1402 			chr = *q++;
1403 			if (squoted && chr == CTLESC)
1404 				chr = *q++;
1405 			if (chr == '\0')
1406 				return 0;
1407 			c = *p++;
1408 			do {
1409 				if (c == CTLQUOTEMARK)
1410 					continue;
1411 				if (c == CTLESC)
1412 					c = *p++;
1413 				if (*p == '-' && p[1] != ']') {
1414 					p++;
1415 					while (*p == CTLQUOTEMARK)
1416 						p++;
1417 					if (*p == CTLESC)
1418 						p++;
1419 					if (   collate_range_cmp(chr, c) >= 0
1420 					    && collate_range_cmp(chr, *p) <= 0
1421 					   )
1422 						found = 1;
1423 					p++;
1424 				} else {
1425 					if (chr == c)
1426 						found = 1;
1427 				}
1428 			} while ((c = *p++) != ']');
1429 			if (found == invert)
1430 				return 0;
1431 			break;
1432 		}
1433 dft:	        default:
1434 			if (squoted && *q == CTLESC)
1435 				q++;
1436 			if (*q++ != c)
1437 				return 0;
1438 			break;
1439 		}
1440 	}
1441 breakloop:
1442 	if (*q != '\0')
1443 		return 0;
1444 	return 1;
1445 }
1446 
1447 
1448 
1449 /*
1450  * Remove any CTLESC characters from a string.
1451  */
1452 
1453 void
1454 rmescapes(char *str)
1455 {
1456 	char *p, *q;
1457 
1458 	p = str;
1459 	while (*p != CTLESC && *p != CTLQUOTEMARK) {
1460 		if (*p++ == '\0')
1461 			return;
1462 	}
1463 	q = p;
1464 	while (*p) {
1465 		if (*p == CTLQUOTEMARK) {
1466 			p++;
1467 			continue;
1468 		}
1469 		if (*p == CTLESC)
1470 			p++;
1471 		*q++ = *p++;
1472 	}
1473 	*q = '\0';
1474 }
1475 
1476 
1477 
1478 /*
1479  * See if a pattern matches in a case statement.
1480  */
1481 
1482 int
1483 casematch(union node *pattern, char *val)
1484 {
1485 	struct stackmark smark;
1486 	int result;
1487 	char *p;
1488 
1489 	setstackmark(&smark);
1490 	argbackq = pattern->narg.backquote;
1491 	STARTSTACKSTR(expdest);
1492 	ifslastp = NULL;
1493 	argstr(pattern->narg.text, EXP_TILDE | EXP_CASE);
1494 	STPUTC('\0', expdest);
1495 	p = grabstackstr(expdest);
1496 	result = patmatch(p, val, 0);
1497 	popstackmark(&smark);
1498 	return result;
1499 }
1500 
1501 /*
1502  * Our own itoa().
1503  */
1504 
1505 STATIC char *
1506 cvtnum(int num, char *buf)
1507 {
1508 	char temp[32];
1509 	int neg = num < 0;
1510 	char *p = temp + 31;
1511 
1512 	temp[31] = '\0';
1513 
1514 	do {
1515 		*--p = num % 10 + '0';
1516 	} while ((num /= 10) != 0);
1517 
1518 	if (neg)
1519 		*--p = '-';
1520 
1521 	while (*p)
1522 		STPUTC(*p++, buf);
1523 	return buf;
1524 }
1525 
1526 /*
1527  * Do most of the work for wordexp(3).
1528  */
1529 
1530 int
1531 wordexpcmd(int argc, char **argv)
1532 {
1533 	size_t len;
1534 	int i;
1535 
1536 	out1fmt("%08x", argc - 1);
1537 	for (i = 1, len = 0; i < argc; i++)
1538 		len += strlen(argv[i]);
1539 	out1fmt("%08x", (int)len);
1540 	for (i = 1; i < argc; i++) {
1541 		out1str(argv[i]);
1542 		out1c('\0');
1543 	}
1544         return (0);
1545 }
1546