xref: /freebsd/bin/sh/expand.c (revision cc3f4b99653c34ae64f8a1fddea370abefef680e)
1 /*-
2  * Copyright (c) 1991, 1993
3  *	The Regents of the University of California.  All rights reserved.
4  * Copyright (c) 1997-2005
5  *	Herbert Xu <herbert@gondor.apana.org.au>.  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  * 4. Neither the name of the University nor the names of its contributors
19  *    may be used to endorse or promote products derived from this software
20  *    without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  */
34 
35 #ifndef lint
36 #if 0
37 static char sccsid[] = "@(#)expand.c	8.5 (Berkeley) 5/15/95";
38 #endif
39 #endif /* not lint */
40 #include <sys/cdefs.h>
41 __FBSDID("$FreeBSD$");
42 
43 #include <sys/types.h>
44 #include <sys/time.h>
45 #include <sys/stat.h>
46 #include <dirent.h>
47 #include <errno.h>
48 #include <inttypes.h>
49 #include <limits.h>
50 #include <pwd.h>
51 #include <stdio.h>
52 #include <stdlib.h>
53 #include <string.h>
54 #include <unistd.h>
55 #include <wchar.h>
56 #include <wctype.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 "arith.h"
79 #include "show.h"
80 #include "builtins.h"
81 
82 /*
83  * Structure specifying which parts of the string should be searched
84  * for IFS characters.
85  */
86 
87 struct ifsregion {
88 	struct ifsregion *next;	/* next region in list */
89 	int begoff;		/* offset of start of region */
90 	int endoff;		/* offset of end of region */
91 	int inquotes;		/* search for nul bytes only */
92 };
93 
94 
95 static char *expdest;			/* output of current string */
96 static struct nodelist *argbackq;	/* list of back quote expressions */
97 static struct ifsregion ifsfirst;	/* first struct in list of ifs regions */
98 static struct ifsregion *ifslastp;	/* last struct in list */
99 static struct arglist exparg;		/* holds expanded arg list */
100 
101 static char *argstr(char *, int);
102 static char *exptilde(char *, int);
103 static char *expari(char *);
104 static void expbackq(union node *, int, int);
105 static int subevalvar(char *, char *, int, int, int, int, int);
106 static char *evalvar(char *, int);
107 static int varisset(const char *, int);
108 static void varvalue(const char *, int, int, int);
109 static void recordregion(int, int, int);
110 static void removerecordregions(int);
111 static void ifsbreakup(char *, struct arglist *);
112 static void expandmeta(struct strlist *, int);
113 static void expmeta(char *, char *);
114 static void addfname(char *);
115 static struct strlist *expsort(struct strlist *);
116 static struct strlist *msort(struct strlist *, int);
117 static int patmatch(const char *, const char *, int);
118 static char *cvtnum(int, char *);
119 static int collate_range_cmp(wchar_t, wchar_t);
120 
121 static int
122 collate_range_cmp(wchar_t c1, wchar_t c2)
123 {
124 	static wchar_t s1[2], s2[2];
125 
126 	s1[0] = c1;
127 	s2[0] = c2;
128 	return (wcscoll(s1, s2));
129 }
130 
131 static char *
132 stputs_quotes(const char *data, const char *syntax, char *p)
133 {
134 	while (*data) {
135 		CHECKSTRSPACE(2, p);
136 		if (syntax[(int)*data] == CCTL)
137 			USTPUTC(CTLESC, p);
138 		USTPUTC(*data++, p);
139 	}
140 	return (p);
141 }
142 #define STPUTS_QUOTES(data, syntax, p) p = stputs_quotes((data), syntax, p)
143 
144 /*
145  * Perform expansions on an argument, placing the resulting list of arguments
146  * in arglist.  Parameter expansion, command substitution and arithmetic
147  * expansion are always performed; additional expansions can be requested
148  * via flag (EXP_*).
149  * The result is left in the stack string.
150  * When arglist is NULL, perform here document expansion.
151  *
152  * Caution: this function uses global state and is not reentrant.
153  * However, a new invocation after an interrupted invocation is safe
154  * and will reset the global state for the new call.
155  */
156 void
157 expandarg(union node *arg, struct arglist *arglist, int flag)
158 {
159 	struct strlist *sp;
160 	char *p;
161 
162 	argbackq = arg->narg.backquote;
163 	STARTSTACKSTR(expdest);
164 	ifsfirst.next = NULL;
165 	ifslastp = NULL;
166 	argstr(arg->narg.text, flag);
167 	if (arglist == NULL) {
168 		STACKSTRNUL(expdest);
169 		return;			/* here document expanded */
170 	}
171 	STPUTC('\0', expdest);
172 	p = grabstackstr(expdest);
173 	exparg.lastp = &exparg.list;
174 	/*
175 	 * TODO - EXP_REDIR
176 	 */
177 	if (flag & EXP_FULL) {
178 		ifsbreakup(p, &exparg);
179 		*exparg.lastp = NULL;
180 		exparg.lastp = &exparg.list;
181 		expandmeta(exparg.list, flag);
182 	} else {
183 		if (flag & EXP_REDIR) /*XXX - for now, just remove escapes */
184 			rmescapes(p);
185 		sp = (struct strlist *)stalloc(sizeof (struct strlist));
186 		sp->text = p;
187 		*exparg.lastp = sp;
188 		exparg.lastp = &sp->next;
189 	}
190 	while (ifsfirst.next != NULL) {
191 		struct ifsregion *ifsp;
192 		INTOFF;
193 		ifsp = ifsfirst.next->next;
194 		ckfree(ifsfirst.next);
195 		ifsfirst.next = ifsp;
196 		INTON;
197 	}
198 	*exparg.lastp = NULL;
199 	if (exparg.list) {
200 		*arglist->lastp = exparg.list;
201 		arglist->lastp = exparg.lastp;
202 	}
203 }
204 
205 
206 
207 /*
208  * Perform parameter expansion, command substitution and arithmetic
209  * expansion, and tilde expansion if requested via EXP_TILDE/EXP_VARTILDE.
210  * Processing ends at a CTLENDVAR or CTLENDARI character as well as '\0'.
211  * This is used to expand word in ${var+word} etc.
212  * If EXP_FULL, EXP_CASE or EXP_REDIR are set, keep and/or generate CTLESC
213  * characters to allow for further processing.
214  * If EXP_FULL is set, also preserve CTLQUOTEMARK characters.
215  */
216 static char *
217 argstr(char *p, int flag)
218 {
219 	char c;
220 	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);	/* do CTLESC */
221 	int firsteq = 1;
222 	int split_lit;
223 	int lit_quoted;
224 
225 	split_lit = flag & EXP_SPLIT_LIT;
226 	lit_quoted = flag & EXP_LIT_QUOTED;
227 	flag &= ~(EXP_SPLIT_LIT | EXP_LIT_QUOTED);
228 	if (*p == '~' && (flag & (EXP_TILDE | EXP_VARTILDE)))
229 		p = exptilde(p, flag);
230 	for (;;) {
231 		CHECKSTRSPACE(2, expdest);
232 		switch (c = *p++) {
233 		case '\0':
234 			return (p - 1);
235 		case CTLENDVAR:
236 		case CTLENDARI:
237 			return (p);
238 		case CTLQUOTEMARK:
239 			lit_quoted = 1;
240 			/* "$@" syntax adherence hack */
241 			if (p[0] == CTLVAR && p[2] == '@' && p[3] == '=')
242 				break;
243 			if ((flag & EXP_FULL) != 0)
244 				USTPUTC(c, expdest);
245 			break;
246 		case CTLQUOTEEND:
247 			lit_quoted = 0;
248 			break;
249 		case CTLESC:
250 			if (quotes)
251 				USTPUTC(c, expdest);
252 			c = *p++;
253 			USTPUTC(c, expdest);
254 			if (split_lit && !lit_quoted)
255 				recordregion(expdest - stackblock() -
256 				    (quotes ? 2 : 1),
257 				    expdest - stackblock(), 0);
258 			break;
259 		case CTLVAR:
260 			p = evalvar(p, flag);
261 			break;
262 		case CTLBACKQ:
263 		case CTLBACKQ|CTLQUOTE:
264 			expbackq(argbackq->n, c & CTLQUOTE, flag);
265 			argbackq = argbackq->next;
266 			break;
267 		case CTLARI:
268 			p = expari(p);
269 			break;
270 		case ':':
271 		case '=':
272 			/*
273 			 * sort of a hack - expand tildes in variable
274 			 * assignments (after the first '=' and after ':'s).
275 			 */
276 			USTPUTC(c, expdest);
277 			if (split_lit && !lit_quoted)
278 				recordregion(expdest - stackblock() - 1,
279 				    expdest - stackblock(), 0);
280 			if (flag & EXP_VARTILDE && *p == '~' &&
281 			    (c != '=' || firsteq)) {
282 				if (c == '=')
283 					firsteq = 0;
284 				p = exptilde(p, flag);
285 			}
286 			break;
287 		default:
288 			USTPUTC(c, expdest);
289 			if (split_lit && !lit_quoted)
290 				recordregion(expdest - stackblock() - 1,
291 				    expdest - stackblock(), 0);
292 		}
293 	}
294 }
295 
296 /*
297  * Perform tilde expansion, placing the result in the stack string and
298  * returning the next position in the input string to process.
299  */
300 static char *
301 exptilde(char *p, int flag)
302 {
303 	char c, *startp = p;
304 	struct passwd *pw;
305 	char *home;
306 	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
307 
308 	while ((c = *p) != '\0') {
309 		switch(c) {
310 		case CTLESC: /* This means CTL* are always considered quoted. */
311 		case CTLVAR:
312 		case CTLBACKQ:
313 		case CTLBACKQ | CTLQUOTE:
314 		case CTLARI:
315 		case CTLENDARI:
316 		case CTLQUOTEMARK:
317 			return (startp);
318 		case ':':
319 			if (flag & EXP_VARTILDE)
320 				goto done;
321 			break;
322 		case '/':
323 		case CTLENDVAR:
324 			goto done;
325 		}
326 		p++;
327 	}
328 done:
329 	*p = '\0';
330 	if (*(startp+1) == '\0') {
331 		if ((home = lookupvar("HOME")) == NULL)
332 			goto lose;
333 	} else {
334 		if ((pw = getpwnam(startp+1)) == NULL)
335 			goto lose;
336 		home = pw->pw_dir;
337 	}
338 	if (*home == '\0')
339 		goto lose;
340 	*p = c;
341 	if (quotes)
342 		STPUTS_QUOTES(home, SQSYNTAX, expdest);
343 	else
344 		STPUTS(home, expdest);
345 	return (p);
346 lose:
347 	*p = c;
348 	return (startp);
349 }
350 
351 
352 static void
353 removerecordregions(int endoff)
354 {
355 	if (ifslastp == NULL)
356 		return;
357 
358 	if (ifsfirst.endoff > endoff) {
359 		while (ifsfirst.next != NULL) {
360 			struct ifsregion *ifsp;
361 			INTOFF;
362 			ifsp = ifsfirst.next->next;
363 			ckfree(ifsfirst.next);
364 			ifsfirst.next = ifsp;
365 			INTON;
366 		}
367 		if (ifsfirst.begoff > endoff)
368 			ifslastp = NULL;
369 		else {
370 			ifslastp = &ifsfirst;
371 			ifsfirst.endoff = endoff;
372 		}
373 		return;
374 	}
375 
376 	ifslastp = &ifsfirst;
377 	while (ifslastp->next && ifslastp->next->begoff < endoff)
378 		ifslastp=ifslastp->next;
379 	while (ifslastp->next != NULL) {
380 		struct ifsregion *ifsp;
381 		INTOFF;
382 		ifsp = ifslastp->next->next;
383 		ckfree(ifslastp->next);
384 		ifslastp->next = ifsp;
385 		INTON;
386 	}
387 	if (ifslastp->endoff > endoff)
388 		ifslastp->endoff = endoff;
389 }
390 
391 /*
392  * Expand arithmetic expression.
393  * Note that flag is not required as digits never require CTLESC characters.
394  */
395 static char *
396 expari(char *p)
397 {
398 	char *q, *start;
399 	arith_t result;
400 	int begoff;
401 	int quoted;
402 	int adj;
403 
404 	quoted = *p++ == '"';
405 	begoff = expdest - stackblock();
406 	p = argstr(p, 0);
407 	removerecordregions(begoff);
408 	STPUTC('\0', expdest);
409 	start = stackblock() + begoff;
410 
411 	q = grabstackstr(expdest);
412 	result = arith(start);
413 	ungrabstackstr(q, expdest);
414 
415 	start = stackblock() + begoff;
416 	adj = start - expdest;
417 	STADJUST(adj, expdest);
418 
419 	CHECKSTRSPACE((int)(DIGITS(result) + 1), expdest);
420 	fmtstr(expdest, DIGITS(result), ARITH_FORMAT_STR, result);
421 	adj = strlen(expdest);
422 	STADJUST(adj, expdest);
423 	if (!quoted)
424 		recordregion(begoff, expdest - stackblock(), 0);
425 	return p;
426 }
427 
428 
429 /*
430  * Perform command substitution.
431  */
432 static void
433 expbackq(union node *cmd, int quoted, int flag)
434 {
435 	struct backcmd in;
436 	int i;
437 	char buf[128];
438 	char *p;
439 	char *dest = expdest;
440 	struct ifsregion saveifs, *savelastp;
441 	struct nodelist *saveargbackq;
442 	char lastc;
443 	int startloc = dest - stackblock();
444 	char const *syntax = quoted? DQSYNTAX : BASESYNTAX;
445 	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
446 	size_t nnl;
447 
448 	INTOFF;
449 	saveifs = ifsfirst;
450 	savelastp = ifslastp;
451 	saveargbackq = argbackq;
452 	p = grabstackstr(dest);
453 	evalbackcmd(cmd, &in);
454 	ungrabstackstr(p, dest);
455 	ifsfirst = saveifs;
456 	ifslastp = savelastp;
457 	argbackq = saveargbackq;
458 
459 	p = in.buf;
460 	lastc = '\0';
461 	nnl = 0;
462 	/* Don't copy trailing newlines */
463 	for (;;) {
464 		if (--in.nleft < 0) {
465 			if (in.fd < 0)
466 				break;
467 			while ((i = read(in.fd, buf, sizeof buf)) < 0 && errno == EINTR);
468 			TRACE(("expbackq: read returns %d\n", i));
469 			if (i <= 0)
470 				break;
471 			p = buf;
472 			in.nleft = i - 1;
473 		}
474 		lastc = *p++;
475 		if (lastc != '\0') {
476 			if (lastc == '\n') {
477 				nnl++;
478 			} else {
479 				CHECKSTRSPACE(nnl + 2, dest);
480 				while (nnl > 0) {
481 					nnl--;
482 					USTPUTC('\n', dest);
483 				}
484 				if (quotes && syntax[(int)lastc] == CCTL)
485 					USTPUTC(CTLESC, dest);
486 				USTPUTC(lastc, dest);
487 			}
488 		}
489 	}
490 
491 	if (in.fd >= 0)
492 		close(in.fd);
493 	if (in.buf)
494 		ckfree(in.buf);
495 	if (in.jp)
496 		exitstatus = waitforjob(in.jp, (int *)NULL);
497 	if (quoted == 0)
498 		recordregion(startloc, dest - stackblock(), 0);
499 	TRACE(("expbackq: size=%td: \"%.*s\"\n",
500 		((dest - stackblock()) - startloc),
501 		(int)((dest - stackblock()) - startloc),
502 		stackblock() + startloc));
503 	expdest = dest;
504 	INTON;
505 }
506 
507 
508 
509 static int
510 subevalvar(char *p, char *str, int strloc, int subtype, int startloc,
511   int varflags, int quotes)
512 {
513 	char *startp;
514 	char *loc = NULL;
515 	char *q;
516 	int c = 0;
517 	struct nodelist *saveargbackq = argbackq;
518 	int amount;
519 
520 	argstr(p, (subtype == VSTRIMLEFT || subtype == VSTRIMLEFTMAX ||
521 	    subtype == VSTRIMRIGHT || subtype == VSTRIMRIGHTMAX ?
522 	    EXP_CASE : 0) | EXP_TILDE);
523 	STACKSTRNUL(expdest);
524 	argbackq = saveargbackq;
525 	startp = stackblock() + startloc;
526 	if (str == NULL)
527 	    str = stackblock() + strloc;
528 
529 	switch (subtype) {
530 	case VSASSIGN:
531 		setvar(str, startp, 0);
532 		amount = startp - expdest;
533 		STADJUST(amount, expdest);
534 		varflags &= ~VSNUL;
535 		return 1;
536 
537 	case VSQUESTION:
538 		if (*p != CTLENDVAR) {
539 			outfmt(out2, "%s\n", startp);
540 			error((char *)NULL);
541 		}
542 		error("%.*s: parameter %snot set", (int)(p - str - 1),
543 		      str, (varflags & VSNUL) ? "null or "
544 					      : nullstr);
545 		return 0;
546 
547 	case VSTRIMLEFT:
548 		for (loc = startp; loc < str; loc++) {
549 			c = *loc;
550 			*loc = '\0';
551 			if (patmatch(str, startp, quotes)) {
552 				*loc = c;
553 				goto recordleft;
554 			}
555 			*loc = c;
556 			if (quotes && *loc == CTLESC)
557 				loc++;
558 		}
559 		return 0;
560 
561 	case VSTRIMLEFTMAX:
562 		for (loc = str - 1; loc >= startp;) {
563 			c = *loc;
564 			*loc = '\0';
565 			if (patmatch(str, startp, quotes)) {
566 				*loc = c;
567 				goto recordleft;
568 			}
569 			*loc = c;
570 			loc--;
571 			if (quotes && loc > startp && *(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 VSTRIMRIGHT:
582 		for (loc = str - 1; loc >= startp;) {
583 			if (patmatch(str, loc, quotes)) {
584 				amount = loc - expdest;
585 				STADJUST(amount, expdest);
586 				return 1;
587 			}
588 			loc--;
589 			if (quotes && loc > startp && *(loc - 1) == CTLESC) {
590 				for (q = startp; q < loc; q++)
591 					if (*q == CTLESC)
592 						q++;
593 				if (q > loc)
594 					loc--;
595 			}
596 		}
597 		return 0;
598 
599 	case VSTRIMRIGHTMAX:
600 		for (loc = startp; loc < str - 1; loc++) {
601 			if (patmatch(str, loc, quotes)) {
602 				amount = loc - expdest;
603 				STADJUST(amount, expdest);
604 				return 1;
605 			}
606 			if (quotes && *loc == CTLESC)
607 				loc++;
608 		}
609 		return 0;
610 
611 
612 	default:
613 		abort();
614 	}
615 
616 recordleft:
617 	amount = ((str - 1) - (loc - startp)) - expdest;
618 	STADJUST(amount, expdest);
619 	while (loc != str - 1)
620 		*startp++ = *loc++;
621 	return 1;
622 }
623 
624 
625 /*
626  * Expand a variable, and return a pointer to the next character in the
627  * input string.
628  */
629 
630 static char *
631 evalvar(char *p, int flag)
632 {
633 	int subtype;
634 	int varflags;
635 	char *var;
636 	const char *val;
637 	int patloc;
638 	int c;
639 	int set;
640 	int special;
641 	int startloc;
642 	int varlen;
643 	int varlenb;
644 	int easy;
645 	int quotes = flag & (EXP_FULL | EXP_CASE | EXP_REDIR);
646 
647 	varflags = (unsigned char)*p++;
648 	subtype = varflags & VSTYPE;
649 	var = p;
650 	special = 0;
651 	if (! is_name(*p))
652 		special = 1;
653 	p = strchr(p, '=') + 1;
654 again: /* jump here after setting a variable with ${var=text} */
655 	if (varflags & VSLINENO) {
656 		set = 1;
657 		special = 1;
658 		val = NULL;
659 	} else if (special) {
660 		set = varisset(var, varflags & VSNUL);
661 		val = NULL;
662 	} else {
663 		val = bltinlookup(var, 1);
664 		if (val == NULL || ((varflags & VSNUL) && val[0] == '\0')) {
665 			val = NULL;
666 			set = 0;
667 		} else
668 			set = 1;
669 	}
670 	varlen = 0;
671 	startloc = expdest - stackblock();
672 	if (!set && uflag && *var != '@' && *var != '*') {
673 		switch (subtype) {
674 		case VSNORMAL:
675 		case VSTRIMLEFT:
676 		case VSTRIMLEFTMAX:
677 		case VSTRIMRIGHT:
678 		case VSTRIMRIGHTMAX:
679 		case VSLENGTH:
680 			error("%.*s: parameter not set", (int)(p - var - 1),
681 			    var);
682 		}
683 	}
684 	if (set && subtype != VSPLUS) {
685 		/* insert the value of the variable */
686 		if (special) {
687 			if (varflags & VSLINENO)
688 				STPUTBIN(var, p - var - 1, expdest);
689 			else
690 				varvalue(var, varflags & VSQUOTE, subtype, flag);
691 			if (subtype == VSLENGTH) {
692 				varlenb = expdest - stackblock() - startloc;
693 				varlen = varlenb;
694 				if (localeisutf8) {
695 					val = stackblock() + startloc;
696 					for (;val != expdest; val++)
697 						if ((*val & 0xC0) == 0x80)
698 							varlen--;
699 				}
700 				STADJUST(-varlenb, expdest);
701 			}
702 		} else {
703 			char const *syntax = (varflags & VSQUOTE) ? DQSYNTAX
704 								  : BASESYNTAX;
705 
706 			if (subtype == VSLENGTH) {
707 				for (;*val; val++)
708 					if (!localeisutf8 ||
709 					    (*val & 0xC0) != 0x80)
710 						varlen++;
711 			}
712 			else {
713 				if (quotes)
714 					STPUTS_QUOTES(val, syntax, expdest);
715 				else
716 					STPUTS(val, expdest);
717 
718 			}
719 		}
720 	}
721 
722 	if (subtype == VSPLUS)
723 		set = ! set;
724 
725 	easy = ((varflags & VSQUOTE) == 0 ||
726 		(*var == '@' && shellparam.nparam != 1));
727 
728 
729 	switch (subtype) {
730 	case VSLENGTH:
731 		expdest = cvtnum(varlen, expdest);
732 		goto record;
733 
734 	case VSNORMAL:
735 		if (!easy)
736 			break;
737 record:
738 		recordregion(startloc, expdest - stackblock(),
739 		    varflags & VSQUOTE || (ifsset() && ifsval()[0] == '\0' &&
740 		    (*var == '@' || *var == '*')));
741 		break;
742 
743 	case VSPLUS:
744 	case VSMINUS:
745 		if (!set) {
746 			argstr(p, flag | (flag & EXP_FULL ? EXP_SPLIT_LIT : 0) |
747 			    (varflags & VSQUOTE ? EXP_LIT_QUOTED : 0));
748 			break;
749 		}
750 		if (easy)
751 			goto record;
752 		break;
753 
754 	case VSTRIMLEFT:
755 	case VSTRIMLEFTMAX:
756 	case VSTRIMRIGHT:
757 	case VSTRIMRIGHTMAX:
758 		if (!set)
759 			break;
760 		/*
761 		 * Terminate the string and start recording the pattern
762 		 * right after it
763 		 */
764 		STPUTC('\0', expdest);
765 		patloc = expdest - stackblock();
766 		if (subevalvar(p, NULL, patloc, subtype,
767 		    startloc, varflags, quotes) == 0) {
768 			int amount = (expdest - stackblock() - patloc) + 1;
769 			STADJUST(-amount, expdest);
770 		}
771 		/* Remove any recorded regions beyond start of variable */
772 		removerecordregions(startloc);
773 		goto record;
774 
775 	case VSASSIGN:
776 	case VSQUESTION:
777 		if (!set) {
778 			if (subevalvar(p, var, 0, subtype, startloc, varflags,
779 			    quotes)) {
780 				varflags &= ~VSNUL;
781 				/*
782 				 * Remove any recorded regions beyond
783 				 * start of variable
784 				 */
785 				removerecordregions(startloc);
786 				goto again;
787 			}
788 			break;
789 		}
790 		if (easy)
791 			goto record;
792 		break;
793 
794 	case VSERROR:
795 		c = p - var - 1;
796 		error("${%.*s%s}: Bad substitution", c, var,
797 		    (c > 0 && *p != CTLENDVAR) ? "..." : "");
798 
799 	default:
800 		abort();
801 	}
802 
803 	if (subtype != VSNORMAL) {	/* skip to end of alternative */
804 		int nesting = 1;
805 		for (;;) {
806 			if ((c = *p++) == CTLESC)
807 				p++;
808 			else if (c == CTLBACKQ || c == (CTLBACKQ|CTLQUOTE)) {
809 				if (set)
810 					argbackq = argbackq->next;
811 			} else if (c == CTLVAR) {
812 				if ((*p++ & VSTYPE) != VSNORMAL)
813 					nesting++;
814 			} else if (c == CTLENDVAR) {
815 				if (--nesting == 0)
816 					break;
817 			}
818 		}
819 	}
820 	return p;
821 }
822 
823 
824 
825 /*
826  * Test whether a specialized variable is set.
827  */
828 
829 static int
830 varisset(const char *name, int nulok)
831 {
832 
833 	if (*name == '!')
834 		return backgndpidset();
835 	else if (*name == '@' || *name == '*') {
836 		if (*shellparam.p == NULL)
837 			return 0;
838 
839 		if (nulok) {
840 			char **av;
841 
842 			for (av = shellparam.p; *av; av++)
843 				if (**av != '\0')
844 					return 1;
845 			return 0;
846 		}
847 	} else if (is_digit(*name)) {
848 		char *ap;
849 		int num = atoi(name);
850 
851 		if (num > shellparam.nparam)
852 			return 0;
853 
854 		if (num == 0)
855 			ap = arg0;
856 		else
857 			ap = shellparam.p[num - 1];
858 
859 		if (nulok && (ap == NULL || *ap == '\0'))
860 			return 0;
861 	}
862 	return 1;
863 }
864 
865 static void
866 strtodest(const char *p, int flag, int subtype, int quoted)
867 {
868 	if (flag & (EXP_FULL | EXP_CASE) && subtype != VSLENGTH)
869 		STPUTS_QUOTES(p, quoted ? DQSYNTAX : BASESYNTAX, expdest);
870 	else
871 		STPUTS(p, expdest);
872 }
873 
874 /*
875  * Add the value of a specialized variable to the stack string.
876  */
877 
878 static void
879 varvalue(const char *name, int quoted, int subtype, int flag)
880 {
881 	int num;
882 	char *p;
883 	int i;
884 	char sep;
885 	char **ap;
886 
887 	switch (*name) {
888 	case '$':
889 		num = rootpid;
890 		goto numvar;
891 	case '?':
892 		num = oexitstatus;
893 		goto numvar;
894 	case '#':
895 		num = shellparam.nparam;
896 		goto numvar;
897 	case '!':
898 		num = backgndpidval();
899 numvar:
900 		expdest = cvtnum(num, expdest);
901 		break;
902 	case '-':
903 		for (i = 0 ; i < NOPTS ; i++) {
904 			if (optlist[i].val)
905 				STPUTC(optlist[i].letter, expdest);
906 		}
907 		break;
908 	case '@':
909 		if (flag & EXP_FULL && quoted) {
910 			for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
911 				strtodest(p, flag, subtype, quoted);
912 				if (*ap)
913 					STPUTC('\0', expdest);
914 			}
915 			break;
916 		}
917 		/* FALLTHROUGH */
918 	case '*':
919 		if (ifsset())
920 			sep = ifsval()[0];
921 		else
922 			sep = ' ';
923 		for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
924 			strtodest(p, flag, subtype, quoted);
925 			if (!*ap)
926 				break;
927 			if (sep || (flag & EXP_FULL && !quoted && **ap != '\0'))
928 				STPUTC(sep, expdest);
929 		}
930 		break;
931 	case '0':
932 		p = arg0;
933 		strtodest(p, flag, subtype, quoted);
934 		break;
935 	default:
936 		if (is_digit(*name)) {
937 			num = atoi(name);
938 			if (num > 0 && num <= shellparam.nparam) {
939 				p = shellparam.p[num - 1];
940 				strtodest(p, flag, subtype, quoted);
941 			}
942 		}
943 		break;
944 	}
945 }
946 
947 
948 
949 /*
950  * Record the fact that we have to scan this region of the
951  * string for IFS characters.
952  */
953 
954 static void
955 recordregion(int start, int end, int inquotes)
956 {
957 	struct ifsregion *ifsp;
958 
959 	INTOFF;
960 	if (ifslastp == NULL) {
961 		ifsp = &ifsfirst;
962 	} else {
963 		if (ifslastp->endoff == start
964 		    && ifslastp->inquotes == inquotes) {
965 			/* extend previous area */
966 			ifslastp->endoff = end;
967 			INTON;
968 			return;
969 		}
970 		ifsp = (struct ifsregion *)ckmalloc(sizeof (struct ifsregion));
971 		ifslastp->next = ifsp;
972 	}
973 	ifslastp = ifsp;
974 	ifslastp->next = NULL;
975 	ifslastp->begoff = start;
976 	ifslastp->endoff = end;
977 	ifslastp->inquotes = inquotes;
978 	INTON;
979 }
980 
981 
982 
983 /*
984  * Break the argument string into pieces based upon IFS and add the
985  * strings to the argument list.  The regions of the string to be
986  * searched for IFS characters have been stored by recordregion.
987  * CTLESC characters are preserved but have little effect in this pass
988  * other than escaping CTL* characters.  In particular, they do not escape
989  * IFS characters: that should be done with the ifsregion mechanism.
990  * CTLQUOTEMARK characters are used to preserve empty quoted strings.
991  * This pass treats them as a regular character, making the string non-empty.
992  * Later, they are removed along with the other CTL* characters.
993  */
994 static void
995 ifsbreakup(char *string, struct arglist *arglist)
996 {
997 	struct ifsregion *ifsp;
998 	struct strlist *sp;
999 	char *start;
1000 	char *p;
1001 	char *q;
1002 	const char *ifs;
1003 	const char *ifsspc;
1004 	int had_param_ch = 0;
1005 
1006 	start = string;
1007 
1008 	if (ifslastp == NULL) {
1009 		/* Return entire argument, IFS doesn't apply to any of it */
1010 		sp = (struct strlist *)stalloc(sizeof *sp);
1011 		sp->text = start;
1012 		*arglist->lastp = sp;
1013 		arglist->lastp = &sp->next;
1014 		return;
1015 	}
1016 
1017 	ifs = ifsset() ? ifsval() : " \t\n";
1018 
1019 	for (ifsp = &ifsfirst; ifsp != NULL; ifsp = ifsp->next) {
1020 		p = string + ifsp->begoff;
1021 		while (p < string + ifsp->endoff) {
1022 			q = p;
1023 			if (*p == CTLESC)
1024 				p++;
1025 			if (ifsp->inquotes) {
1026 				/* Only NULs (should be from "$@") end args */
1027 				had_param_ch = 1;
1028 				if (*p != 0) {
1029 					p++;
1030 					continue;
1031 				}
1032 				ifsspc = NULL;
1033 			} else {
1034 				if (!strchr(ifs, *p)) {
1035 					had_param_ch = 1;
1036 					p++;
1037 					continue;
1038 				}
1039 				ifsspc = strchr(" \t\n", *p);
1040 
1041 				/* Ignore IFS whitespace at start */
1042 				if (q == start && ifsspc != NULL) {
1043 					p++;
1044 					start = p;
1045 					continue;
1046 				}
1047 				had_param_ch = 0;
1048 			}
1049 
1050 			/* Save this argument... */
1051 			*q = '\0';
1052 			sp = (struct strlist *)stalloc(sizeof *sp);
1053 			sp->text = start;
1054 			*arglist->lastp = sp;
1055 			arglist->lastp = &sp->next;
1056 			p++;
1057 
1058 			if (ifsspc != NULL) {
1059 				/* Ignore further trailing IFS whitespace */
1060 				for (; p < string + ifsp->endoff; p++) {
1061 					q = p;
1062 					if (*p == CTLESC)
1063 						p++;
1064 					if (strchr(ifs, *p) == NULL) {
1065 						p = q;
1066 						break;
1067 					}
1068 					if (strchr(" \t\n", *p) == NULL) {
1069 						p++;
1070 						break;
1071 					}
1072 				}
1073 			}
1074 			start = p;
1075 		}
1076 	}
1077 
1078 	/*
1079 	 * Save anything left as an argument.
1080 	 * Traditionally we have treated 'IFS=':'; set -- x$IFS' as
1081 	 * generating 2 arguments, the second of which is empty.
1082 	 * Some recent clarification of the Posix spec say that it
1083 	 * should only generate one....
1084 	 */
1085 	if (had_param_ch || *start != 0) {
1086 		sp = (struct strlist *)stalloc(sizeof *sp);
1087 		sp->text = start;
1088 		*arglist->lastp = sp;
1089 		arglist->lastp = &sp->next;
1090 	}
1091 }
1092 
1093 
1094 static char expdir[PATH_MAX];
1095 #define expdir_end (expdir + sizeof(expdir))
1096 
1097 /*
1098  * Perform pathname generation and remove control characters.
1099  * At this point, the only control characters should be CTLESC and CTLQUOTEMARK.
1100  * The results are stored in the list exparg.
1101  */
1102 static void
1103 expandmeta(struct strlist *str, int flag __unused)
1104 {
1105 	char *p;
1106 	struct strlist **savelastp;
1107 	struct strlist *sp;
1108 	char c;
1109 	/* TODO - EXP_REDIR */
1110 
1111 	while (str) {
1112 		if (fflag)
1113 			goto nometa;
1114 		p = str->text;
1115 		for (;;) {			/* fast check for meta chars */
1116 			if ((c = *p++) == '\0')
1117 				goto nometa;
1118 			if (c == '*' || c == '?' || c == '[')
1119 				break;
1120 		}
1121 		savelastp = exparg.lastp;
1122 		INTOFF;
1123 		expmeta(expdir, str->text);
1124 		INTON;
1125 		if (exparg.lastp == savelastp) {
1126 			/*
1127 			 * no matches
1128 			 */
1129 nometa:
1130 			*exparg.lastp = str;
1131 			rmescapes(str->text);
1132 			exparg.lastp = &str->next;
1133 		} else {
1134 			*exparg.lastp = NULL;
1135 			*savelastp = sp = expsort(*savelastp);
1136 			while (sp->next != NULL)
1137 				sp = sp->next;
1138 			exparg.lastp = &sp->next;
1139 		}
1140 		str = str->next;
1141 	}
1142 }
1143 
1144 
1145 /*
1146  * Do metacharacter (i.e. *, ?, [...]) expansion.
1147  */
1148 
1149 static void
1150 expmeta(char *enddir, char *name)
1151 {
1152 	const char *p;
1153 	const char *q;
1154 	const char *start;
1155 	char *endname;
1156 	int metaflag;
1157 	struct stat statb;
1158 	DIR *dirp;
1159 	struct dirent *dp;
1160 	int atend;
1161 	int matchdot;
1162 	int esc;
1163 	int namlen;
1164 
1165 	metaflag = 0;
1166 	start = name;
1167 	for (p = name; esc = 0, *p; p += esc + 1) {
1168 		if (*p == '*' || *p == '?')
1169 			metaflag = 1;
1170 		else if (*p == '[') {
1171 			q = p + 1;
1172 			if (*q == '!' || *q == '^')
1173 				q++;
1174 			for (;;) {
1175 				while (*q == CTLQUOTEMARK)
1176 					q++;
1177 				if (*q == CTLESC)
1178 					q++;
1179 				if (*q == '/' || *q == '\0')
1180 					break;
1181 				if (*++q == ']') {
1182 					metaflag = 1;
1183 					break;
1184 				}
1185 			}
1186 		} else if (*p == '\0')
1187 			break;
1188 		else if (*p == CTLQUOTEMARK)
1189 			continue;
1190 		else {
1191 			if (*p == CTLESC)
1192 				esc++;
1193 			if (p[esc] == '/') {
1194 				if (metaflag)
1195 					break;
1196 				start = p + esc + 1;
1197 			}
1198 		}
1199 	}
1200 	if (metaflag == 0) {	/* we've reached the end of the file name */
1201 		if (enddir != expdir)
1202 			metaflag++;
1203 		for (p = name ; ; p++) {
1204 			if (*p == CTLQUOTEMARK)
1205 				continue;
1206 			if (*p == CTLESC)
1207 				p++;
1208 			*enddir++ = *p;
1209 			if (*p == '\0')
1210 				break;
1211 			if (enddir == expdir_end)
1212 				return;
1213 		}
1214 		if (metaflag == 0 || lstat(expdir, &statb) >= 0)
1215 			addfname(expdir);
1216 		return;
1217 	}
1218 	endname = name + (p - name);
1219 	if (start != name) {
1220 		p = name;
1221 		while (p < start) {
1222 			while (*p == CTLQUOTEMARK)
1223 				p++;
1224 			if (*p == CTLESC)
1225 				p++;
1226 			*enddir++ = *p++;
1227 			if (enddir == expdir_end)
1228 				return;
1229 		}
1230 	}
1231 	if (enddir == expdir) {
1232 		p = ".";
1233 	} else if (enddir == expdir + 1 && *expdir == '/') {
1234 		p = "/";
1235 	} else {
1236 		p = expdir;
1237 		enddir[-1] = '\0';
1238 	}
1239 	if ((dirp = opendir(p)) == NULL)
1240 		return;
1241 	if (enddir != expdir)
1242 		enddir[-1] = '/';
1243 	if (*endname == 0) {
1244 		atend = 1;
1245 	} else {
1246 		atend = 0;
1247 		*endname = '\0';
1248 		endname += esc + 1;
1249 	}
1250 	matchdot = 0;
1251 	p = start;
1252 	while (*p == CTLQUOTEMARK)
1253 		p++;
1254 	if (*p == CTLESC)
1255 		p++;
1256 	if (*p == '.')
1257 		matchdot++;
1258 	while (! int_pending() && (dp = readdir(dirp)) != NULL) {
1259 		if (dp->d_name[0] == '.' && ! matchdot)
1260 			continue;
1261 		if (patmatch(start, dp->d_name, 0)) {
1262 			namlen = dp->d_namlen;
1263 			if (enddir + namlen + 1 > expdir_end)
1264 				continue;
1265 			memcpy(enddir, dp->d_name, namlen + 1);
1266 			if (atend)
1267 				addfname(expdir);
1268 			else {
1269 				if (dp->d_type != DT_UNKNOWN &&
1270 				    dp->d_type != DT_DIR &&
1271 				    dp->d_type != DT_LNK)
1272 					continue;
1273 				if (enddir + namlen + 2 > expdir_end)
1274 					continue;
1275 				enddir[namlen] = '/';
1276 				enddir[namlen + 1] = '\0';
1277 				expmeta(enddir + namlen + 1, endname);
1278 			}
1279 		}
1280 	}
1281 	closedir(dirp);
1282 	if (! atend)
1283 		endname[-esc - 1] = esc ? CTLESC : '/';
1284 }
1285 
1286 
1287 /*
1288  * Add a file name to the list.
1289  */
1290 
1291 static void
1292 addfname(char *name)
1293 {
1294 	char *p;
1295 	struct strlist *sp;
1296 	size_t len;
1297 
1298 	len = strlen(name);
1299 	p = stalloc(len + 1);
1300 	memcpy(p, name, len + 1);
1301 	sp = (struct strlist *)stalloc(sizeof *sp);
1302 	sp->text = p;
1303 	*exparg.lastp = sp;
1304 	exparg.lastp = &sp->next;
1305 }
1306 
1307 
1308 /*
1309  * Sort the results of file name expansion.  It calculates the number of
1310  * strings to sort and then calls msort (short for merge sort) to do the
1311  * work.
1312  */
1313 
1314 static struct strlist *
1315 expsort(struct strlist *str)
1316 {
1317 	int len;
1318 	struct strlist *sp;
1319 
1320 	len = 0;
1321 	for (sp = str ; sp ; sp = sp->next)
1322 		len++;
1323 	return msort(str, len);
1324 }
1325 
1326 
1327 static struct strlist *
1328 msort(struct strlist *list, int len)
1329 {
1330 	struct strlist *p, *q = NULL;
1331 	struct strlist **lpp;
1332 	int half;
1333 	int n;
1334 
1335 	if (len <= 1)
1336 		return list;
1337 	half = len >> 1;
1338 	p = list;
1339 	for (n = half ; --n >= 0 ; ) {
1340 		q = p;
1341 		p = p->next;
1342 	}
1343 	q->next = NULL;			/* terminate first half of list */
1344 	q = msort(list, half);		/* sort first half of list */
1345 	p = msort(p, len - half);		/* sort second half */
1346 	lpp = &list;
1347 	for (;;) {
1348 		if (strcmp(p->text, q->text) < 0) {
1349 			*lpp = p;
1350 			lpp = &p->next;
1351 			if ((p = *lpp) == NULL) {
1352 				*lpp = q;
1353 				break;
1354 			}
1355 		} else {
1356 			*lpp = q;
1357 			lpp = &q->next;
1358 			if ((q = *lpp) == NULL) {
1359 				*lpp = p;
1360 				break;
1361 			}
1362 		}
1363 	}
1364 	return list;
1365 }
1366 
1367 
1368 
1369 static wchar_t
1370 get_wc(const char **p)
1371 {
1372 	wchar_t c;
1373 	int chrlen;
1374 
1375 	chrlen = mbtowc(&c, *p, 4);
1376 	if (chrlen == 0)
1377 		return 0;
1378 	else if (chrlen == -1)
1379 		c = 0;
1380 	else
1381 		*p += chrlen;
1382 	return c;
1383 }
1384 
1385 
1386 /*
1387  * See if a character matches a character class, starting at the first colon
1388  * of "[:class:]".
1389  * If a valid character class is recognized, a pointer to the next character
1390  * after the final closing bracket is stored into *end, otherwise a null
1391  * pointer is stored into *end.
1392  */
1393 static int
1394 match_charclass(const char *p, wchar_t chr, const char **end)
1395 {
1396 	char name[20];
1397 	const char *nameend;
1398 	wctype_t cclass;
1399 
1400 	*end = NULL;
1401 	p++;
1402 	nameend = strstr(p, ":]");
1403 	if (nameend == NULL || (size_t)(nameend - p) >= sizeof(name) ||
1404 	    nameend == p)
1405 		return 0;
1406 	memcpy(name, p, nameend - p);
1407 	name[nameend - p] = '\0';
1408 	*end = nameend + 2;
1409 	cclass = wctype(name);
1410 	/* An unknown class matches nothing but is valid nevertheless. */
1411 	if (cclass == 0)
1412 		return 0;
1413 	return iswctype(chr, cclass);
1414 }
1415 
1416 
1417 /*
1418  * Returns true if the pattern matches the string.
1419  */
1420 
1421 static int
1422 patmatch(const char *pattern, const char *string, int squoted)
1423 {
1424 	const char *p, *q, *end;
1425 	const char *bt_p, *bt_q;
1426 	char c;
1427 	wchar_t wc, wc2;
1428 
1429 	p = pattern;
1430 	q = string;
1431 	bt_p = NULL;
1432 	bt_q = NULL;
1433 	for (;;) {
1434 		switch (c = *p++) {
1435 		case '\0':
1436 			if (*q != '\0')
1437 				goto backtrack;
1438 			return 1;
1439 		case CTLESC:
1440 			if (squoted && *q == CTLESC)
1441 				q++;
1442 			if (*q++ != *p++)
1443 				goto backtrack;
1444 			break;
1445 		case CTLQUOTEMARK:
1446 			continue;
1447 		case '?':
1448 			if (squoted && *q == CTLESC)
1449 				q++;
1450 			if (*q == '\0')
1451 				return 0;
1452 			if (localeisutf8) {
1453 				wc = get_wc(&q);
1454 				/*
1455 				 * A '?' does not match invalid UTF-8 but a
1456 				 * '*' does, so backtrack.
1457 				 */
1458 				if (wc == 0)
1459 					goto backtrack;
1460 			} else
1461 				wc = (unsigned char)*q++;
1462 			break;
1463 		case '*':
1464 			c = *p;
1465 			while (c == CTLQUOTEMARK || c == '*')
1466 				c = *++p;
1467 			/*
1468 			 * If the pattern ends here, we know the string
1469 			 * matches without needing to look at the rest of it.
1470 			 */
1471 			if (c == '\0')
1472 				return 1;
1473 			/*
1474 			 * First try the shortest match for the '*' that
1475 			 * could work. We can forget any earlier '*' since
1476 			 * there is no way having it match more characters
1477 			 * can help us, given that we are already here.
1478 			 */
1479 			bt_p = p;
1480 			bt_q = q;
1481 			break;
1482 		case '[': {
1483 			const char *endp;
1484 			int invert, found;
1485 			wchar_t chr;
1486 
1487 			endp = p;
1488 			if (*endp == '!' || *endp == '^')
1489 				endp++;
1490 			for (;;) {
1491 				while (*endp == CTLQUOTEMARK)
1492 					endp++;
1493 				if (*endp == 0)
1494 					goto dft;		/* no matching ] */
1495 				if (*endp == CTLESC)
1496 					endp++;
1497 				if (*++endp == ']')
1498 					break;
1499 			}
1500 			invert = 0;
1501 			if (*p == '!' || *p == '^') {
1502 				invert++;
1503 				p++;
1504 			}
1505 			found = 0;
1506 			if (squoted && *q == CTLESC)
1507 				q++;
1508 			if (*q == '\0')
1509 				return 0;
1510 			if (localeisutf8) {
1511 				chr = get_wc(&q);
1512 				if (chr == 0)
1513 					goto backtrack;
1514 			} else
1515 				chr = (unsigned char)*q++;
1516 			c = *p++;
1517 			do {
1518 				if (c == CTLQUOTEMARK)
1519 					continue;
1520 				if (c == '[' && *p == ':') {
1521 					found |= match_charclass(p, chr, &end);
1522 					if (end != NULL)
1523 						p = end;
1524 				}
1525 				if (c == CTLESC)
1526 					c = *p++;
1527 				if (localeisutf8 && c & 0x80) {
1528 					p--;
1529 					wc = get_wc(&p);
1530 					if (wc == 0) /* bad utf-8 */
1531 						return 0;
1532 				} else
1533 					wc = (unsigned char)c;
1534 				if (*p == '-' && p[1] != ']') {
1535 					p++;
1536 					while (*p == CTLQUOTEMARK)
1537 						p++;
1538 					if (*p == CTLESC)
1539 						p++;
1540 					if (localeisutf8) {
1541 						wc2 = get_wc(&p);
1542 						if (wc2 == 0) /* bad utf-8 */
1543 							return 0;
1544 					} else
1545 						wc2 = (unsigned char)*p++;
1546 					if (   collate_range_cmp(chr, wc) >= 0
1547 					    && collate_range_cmp(chr, wc2) <= 0
1548 					   )
1549 						found = 1;
1550 				} else {
1551 					if (chr == wc)
1552 						found = 1;
1553 				}
1554 			} while ((c = *p++) != ']');
1555 			if (found == invert)
1556 				goto backtrack;
1557 			break;
1558 		}
1559 dft:	        default:
1560 			if (squoted && *q == CTLESC)
1561 				q++;
1562 			if (*q == '\0')
1563 				return 0;
1564 			if (*q++ == c)
1565 				break;
1566 backtrack:
1567 			/*
1568 			 * If we have a mismatch (other than hitting the end
1569 			 * of the string), go back to the last '*' seen and
1570 			 * have it match one additional character.
1571 			 */
1572 			if (bt_p == NULL)
1573 				return 0;
1574 			if (squoted && *bt_q == CTLESC)
1575 				bt_q++;
1576 			if (*bt_q == '\0')
1577 				return 0;
1578 			bt_q++;
1579 			p = bt_p;
1580 			q = bt_q;
1581 			break;
1582 		}
1583 	}
1584 }
1585 
1586 
1587 
1588 /*
1589  * Remove any CTLESC and CTLQUOTEMARK characters from a string.
1590  */
1591 
1592 void
1593 rmescapes(char *str)
1594 {
1595 	char *p, *q;
1596 
1597 	p = str;
1598 	while (*p != CTLESC && *p != CTLQUOTEMARK && *p != CTLQUOTEEND) {
1599 		if (*p++ == '\0')
1600 			return;
1601 	}
1602 	q = p;
1603 	while (*p) {
1604 		if (*p == CTLQUOTEMARK || *p == CTLQUOTEEND) {
1605 			p++;
1606 			continue;
1607 		}
1608 		if (*p == CTLESC)
1609 			p++;
1610 		*q++ = *p++;
1611 	}
1612 	*q = '\0';
1613 }
1614 
1615 
1616 
1617 /*
1618  * See if a pattern matches in a case statement.
1619  */
1620 
1621 int
1622 casematch(union node *pattern, const char *val)
1623 {
1624 	struct stackmark smark;
1625 	int result;
1626 	char *p;
1627 
1628 	setstackmark(&smark);
1629 	argbackq = pattern->narg.backquote;
1630 	STARTSTACKSTR(expdest);
1631 	ifslastp = NULL;
1632 	argstr(pattern->narg.text, EXP_TILDE | EXP_CASE);
1633 	STPUTC('\0', expdest);
1634 	p = grabstackstr(expdest);
1635 	result = patmatch(p, val, 0);
1636 	popstackmark(&smark);
1637 	return result;
1638 }
1639 
1640 /*
1641  * Our own itoa().
1642  */
1643 
1644 static char *
1645 cvtnum(int num, char *buf)
1646 {
1647 	char temp[32];
1648 	int neg = num < 0;
1649 	char *p = temp + 31;
1650 
1651 	temp[31] = '\0';
1652 
1653 	do {
1654 		*--p = num % 10 + '0';
1655 	} while ((num /= 10) != 0);
1656 
1657 	if (neg)
1658 		*--p = '-';
1659 
1660 	STPUTS(p, buf);
1661 	return buf;
1662 }
1663 
1664 /*
1665  * Do most of the work for wordexp(3).
1666  */
1667 
1668 int
1669 wordexpcmd(int argc, char **argv)
1670 {
1671 	size_t len;
1672 	int i;
1673 
1674 	out1fmt("%08x", argc - 1);
1675 	for (i = 1, len = 0; i < argc; i++)
1676 		len += strlen(argv[i]);
1677 	out1fmt("%08x", (int)len);
1678 	for (i = 1; i < argc; i++)
1679 		outbin(argv[i], strlen(argv[i]) + 1, out1);
1680         return (0);
1681 }
1682