xref: /freebsd/bin/sh/expand.c (revision 97bd480fe38abb5950359b9d864a62037b4ab5f7)
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 	if (ifslastp == NULL) {
960 		ifsp = &ifsfirst;
961 	} else {
962 		if (ifslastp->endoff == start
963 		    && ifslastp->inquotes == inquotes) {
964 			/* extend previous area */
965 			ifslastp->endoff = end;
966 			return;
967 		}
968 		ifsp = (struct ifsregion *)ckmalloc(sizeof (struct ifsregion));
969 		ifslastp->next = ifsp;
970 	}
971 	ifslastp = ifsp;
972 	ifslastp->next = NULL;
973 	ifslastp->begoff = start;
974 	ifslastp->endoff = end;
975 	ifslastp->inquotes = inquotes;
976 }
977 
978 
979 
980 /*
981  * Break the argument string into pieces based upon IFS and add the
982  * strings to the argument list.  The regions of the string to be
983  * searched for IFS characters have been stored by recordregion.
984  * CTLESC characters are preserved but have little effect in this pass
985  * other than escaping CTL* characters.  In particular, they do not escape
986  * IFS characters: that should be done with the ifsregion mechanism.
987  * CTLQUOTEMARK characters are used to preserve empty quoted strings.
988  * This pass treats them as a regular character, making the string non-empty.
989  * Later, they are removed along with the other CTL* characters.
990  */
991 static void
992 ifsbreakup(char *string, struct arglist *arglist)
993 {
994 	struct ifsregion *ifsp;
995 	struct strlist *sp;
996 	char *start;
997 	char *p;
998 	char *q;
999 	const char *ifs;
1000 	const char *ifsspc;
1001 	int had_param_ch = 0;
1002 
1003 	start = string;
1004 
1005 	if (ifslastp == NULL) {
1006 		/* Return entire argument, IFS doesn't apply to any of it */
1007 		sp = (struct strlist *)stalloc(sizeof *sp);
1008 		sp->text = start;
1009 		*arglist->lastp = sp;
1010 		arglist->lastp = &sp->next;
1011 		return;
1012 	}
1013 
1014 	ifs = ifsset() ? ifsval() : " \t\n";
1015 
1016 	for (ifsp = &ifsfirst; ifsp != NULL; ifsp = ifsp->next) {
1017 		p = string + ifsp->begoff;
1018 		while (p < string + ifsp->endoff) {
1019 			q = p;
1020 			if (*p == CTLESC)
1021 				p++;
1022 			if (ifsp->inquotes) {
1023 				/* Only NULs (should be from "$@") end args */
1024 				had_param_ch = 1;
1025 				if (*p != 0) {
1026 					p++;
1027 					continue;
1028 				}
1029 				ifsspc = NULL;
1030 			} else {
1031 				if (!strchr(ifs, *p)) {
1032 					had_param_ch = 1;
1033 					p++;
1034 					continue;
1035 				}
1036 				ifsspc = strchr(" \t\n", *p);
1037 
1038 				/* Ignore IFS whitespace at start */
1039 				if (q == start && ifsspc != NULL) {
1040 					p++;
1041 					start = p;
1042 					continue;
1043 				}
1044 				had_param_ch = 0;
1045 			}
1046 
1047 			/* Save this argument... */
1048 			*q = '\0';
1049 			sp = (struct strlist *)stalloc(sizeof *sp);
1050 			sp->text = start;
1051 			*arglist->lastp = sp;
1052 			arglist->lastp = &sp->next;
1053 			p++;
1054 
1055 			if (ifsspc != NULL) {
1056 				/* Ignore further trailing IFS whitespace */
1057 				for (; p < string + ifsp->endoff; p++) {
1058 					q = p;
1059 					if (*p == CTLESC)
1060 						p++;
1061 					if (strchr(ifs, *p) == NULL) {
1062 						p = q;
1063 						break;
1064 					}
1065 					if (strchr(" \t\n", *p) == NULL) {
1066 						p++;
1067 						break;
1068 					}
1069 				}
1070 			}
1071 			start = p;
1072 		}
1073 	}
1074 
1075 	/*
1076 	 * Save anything left as an argument.
1077 	 * Traditionally we have treated 'IFS=':'; set -- x$IFS' as
1078 	 * generating 2 arguments, the second of which is empty.
1079 	 * Some recent clarification of the Posix spec say that it
1080 	 * should only generate one....
1081 	 */
1082 	if (had_param_ch || *start != 0) {
1083 		sp = (struct strlist *)stalloc(sizeof *sp);
1084 		sp->text = start;
1085 		*arglist->lastp = sp;
1086 		arglist->lastp = &sp->next;
1087 	}
1088 }
1089 
1090 
1091 static char expdir[PATH_MAX];
1092 #define expdir_end (expdir + sizeof(expdir))
1093 
1094 /*
1095  * Perform pathname generation and remove control characters.
1096  * At this point, the only control characters should be CTLESC and CTLQUOTEMARK.
1097  * The results are stored in the list exparg.
1098  */
1099 static void
1100 expandmeta(struct strlist *str, int flag __unused)
1101 {
1102 	char *p;
1103 	struct strlist **savelastp;
1104 	struct strlist *sp;
1105 	char c;
1106 	/* TODO - EXP_REDIR */
1107 
1108 	while (str) {
1109 		if (fflag)
1110 			goto nometa;
1111 		p = str->text;
1112 		for (;;) {			/* fast check for meta chars */
1113 			if ((c = *p++) == '\0')
1114 				goto nometa;
1115 			if (c == '*' || c == '?' || c == '[')
1116 				break;
1117 		}
1118 		savelastp = exparg.lastp;
1119 		INTOFF;
1120 		expmeta(expdir, str->text);
1121 		INTON;
1122 		if (exparg.lastp == savelastp) {
1123 			/*
1124 			 * no matches
1125 			 */
1126 nometa:
1127 			*exparg.lastp = str;
1128 			rmescapes(str->text);
1129 			exparg.lastp = &str->next;
1130 		} else {
1131 			*exparg.lastp = NULL;
1132 			*savelastp = sp = expsort(*savelastp);
1133 			while (sp->next != NULL)
1134 				sp = sp->next;
1135 			exparg.lastp = &sp->next;
1136 		}
1137 		str = str->next;
1138 	}
1139 }
1140 
1141 
1142 /*
1143  * Do metacharacter (i.e. *, ?, [...]) expansion.
1144  */
1145 
1146 static void
1147 expmeta(char *enddir, char *name)
1148 {
1149 	const char *p;
1150 	const char *q;
1151 	const char *start;
1152 	char *endname;
1153 	int metaflag;
1154 	struct stat statb;
1155 	DIR *dirp;
1156 	struct dirent *dp;
1157 	int atend;
1158 	int matchdot;
1159 	int esc;
1160 	int namlen;
1161 
1162 	metaflag = 0;
1163 	start = name;
1164 	for (p = name; esc = 0, *p; p += esc + 1) {
1165 		if (*p == '*' || *p == '?')
1166 			metaflag = 1;
1167 		else if (*p == '[') {
1168 			q = p + 1;
1169 			if (*q == '!' || *q == '^')
1170 				q++;
1171 			for (;;) {
1172 				while (*q == CTLQUOTEMARK)
1173 					q++;
1174 				if (*q == CTLESC)
1175 					q++;
1176 				if (*q == '/' || *q == '\0')
1177 					break;
1178 				if (*++q == ']') {
1179 					metaflag = 1;
1180 					break;
1181 				}
1182 			}
1183 		} else if (*p == '\0')
1184 			break;
1185 		else if (*p == CTLQUOTEMARK)
1186 			continue;
1187 		else {
1188 			if (*p == CTLESC)
1189 				esc++;
1190 			if (p[esc] == '/') {
1191 				if (metaflag)
1192 					break;
1193 				start = p + esc + 1;
1194 			}
1195 		}
1196 	}
1197 	if (metaflag == 0) {	/* we've reached the end of the file name */
1198 		if (enddir != expdir)
1199 			metaflag++;
1200 		for (p = name ; ; p++) {
1201 			if (*p == CTLQUOTEMARK)
1202 				continue;
1203 			if (*p == CTLESC)
1204 				p++;
1205 			*enddir++ = *p;
1206 			if (*p == '\0')
1207 				break;
1208 			if (enddir == expdir_end)
1209 				return;
1210 		}
1211 		if (metaflag == 0 || lstat(expdir, &statb) >= 0)
1212 			addfname(expdir);
1213 		return;
1214 	}
1215 	endname = name + (p - name);
1216 	if (start != name) {
1217 		p = name;
1218 		while (p < start) {
1219 			while (*p == CTLQUOTEMARK)
1220 				p++;
1221 			if (*p == CTLESC)
1222 				p++;
1223 			*enddir++ = *p++;
1224 			if (enddir == expdir_end)
1225 				return;
1226 		}
1227 	}
1228 	if (enddir == expdir) {
1229 		p = ".";
1230 	} else if (enddir == expdir + 1 && *expdir == '/') {
1231 		p = "/";
1232 	} else {
1233 		p = expdir;
1234 		enddir[-1] = '\0';
1235 	}
1236 	if ((dirp = opendir(p)) == NULL)
1237 		return;
1238 	if (enddir != expdir)
1239 		enddir[-1] = '/';
1240 	if (*endname == 0) {
1241 		atend = 1;
1242 	} else {
1243 		atend = 0;
1244 		*endname = '\0';
1245 		endname += esc + 1;
1246 	}
1247 	matchdot = 0;
1248 	p = start;
1249 	while (*p == CTLQUOTEMARK)
1250 		p++;
1251 	if (*p == CTLESC)
1252 		p++;
1253 	if (*p == '.')
1254 		matchdot++;
1255 	while (! int_pending() && (dp = readdir(dirp)) != NULL) {
1256 		if (dp->d_name[0] == '.' && ! matchdot)
1257 			continue;
1258 		if (patmatch(start, dp->d_name, 0)) {
1259 			namlen = dp->d_namlen;
1260 			if (enddir + namlen + 1 > expdir_end)
1261 				continue;
1262 			memcpy(enddir, dp->d_name, namlen + 1);
1263 			if (atend)
1264 				addfname(expdir);
1265 			else {
1266 				if (dp->d_type != DT_UNKNOWN &&
1267 				    dp->d_type != DT_DIR &&
1268 				    dp->d_type != DT_LNK)
1269 					continue;
1270 				if (enddir + namlen + 2 > expdir_end)
1271 					continue;
1272 				enddir[namlen] = '/';
1273 				enddir[namlen + 1] = '\0';
1274 				expmeta(enddir + namlen + 1, endname);
1275 			}
1276 		}
1277 	}
1278 	closedir(dirp);
1279 	if (! atend)
1280 		endname[-esc - 1] = esc ? CTLESC : '/';
1281 }
1282 
1283 
1284 /*
1285  * Add a file name to the list.
1286  */
1287 
1288 static void
1289 addfname(char *name)
1290 {
1291 	char *p;
1292 	struct strlist *sp;
1293 	size_t len;
1294 
1295 	len = strlen(name);
1296 	p = stalloc(len + 1);
1297 	memcpy(p, name, len + 1);
1298 	sp = (struct strlist *)stalloc(sizeof *sp);
1299 	sp->text = p;
1300 	*exparg.lastp = sp;
1301 	exparg.lastp = &sp->next;
1302 }
1303 
1304 
1305 /*
1306  * Sort the results of file name expansion.  It calculates the number of
1307  * strings to sort and then calls msort (short for merge sort) to do the
1308  * work.
1309  */
1310 
1311 static struct strlist *
1312 expsort(struct strlist *str)
1313 {
1314 	int len;
1315 	struct strlist *sp;
1316 
1317 	len = 0;
1318 	for (sp = str ; sp ; sp = sp->next)
1319 		len++;
1320 	return msort(str, len);
1321 }
1322 
1323 
1324 static struct strlist *
1325 msort(struct strlist *list, int len)
1326 {
1327 	struct strlist *p, *q = NULL;
1328 	struct strlist **lpp;
1329 	int half;
1330 	int n;
1331 
1332 	if (len <= 1)
1333 		return list;
1334 	half = len >> 1;
1335 	p = list;
1336 	for (n = half ; --n >= 0 ; ) {
1337 		q = p;
1338 		p = p->next;
1339 	}
1340 	q->next = NULL;			/* terminate first half of list */
1341 	q = msort(list, half);		/* sort first half of list */
1342 	p = msort(p, len - half);		/* sort second half */
1343 	lpp = &list;
1344 	for (;;) {
1345 		if (strcmp(p->text, q->text) < 0) {
1346 			*lpp = p;
1347 			lpp = &p->next;
1348 			if ((p = *lpp) == NULL) {
1349 				*lpp = q;
1350 				break;
1351 			}
1352 		} else {
1353 			*lpp = q;
1354 			lpp = &q->next;
1355 			if ((q = *lpp) == NULL) {
1356 				*lpp = p;
1357 				break;
1358 			}
1359 		}
1360 	}
1361 	return list;
1362 }
1363 
1364 
1365 
1366 static wchar_t
1367 get_wc(const char **p)
1368 {
1369 	wchar_t c;
1370 	int chrlen;
1371 
1372 	chrlen = mbtowc(&c, *p, 4);
1373 	if (chrlen == 0)
1374 		return 0;
1375 	else if (chrlen == -1)
1376 		c = 0;
1377 	else
1378 		*p += chrlen;
1379 	return c;
1380 }
1381 
1382 
1383 /*
1384  * See if a character matches a character class, starting at the first colon
1385  * of "[:class:]".
1386  * If a valid character class is recognized, a pointer to the next character
1387  * after the final closing bracket is stored into *end, otherwise a null
1388  * pointer is stored into *end.
1389  */
1390 static int
1391 match_charclass(const char *p, wchar_t chr, const char **end)
1392 {
1393 	char name[20];
1394 	const char *nameend;
1395 	wctype_t cclass;
1396 
1397 	*end = NULL;
1398 	p++;
1399 	nameend = strstr(p, ":]");
1400 	if (nameend == NULL || (size_t)(nameend - p) >= sizeof(name) ||
1401 	    nameend == p)
1402 		return 0;
1403 	memcpy(name, p, nameend - p);
1404 	name[nameend - p] = '\0';
1405 	*end = nameend + 2;
1406 	cclass = wctype(name);
1407 	/* An unknown class matches nothing but is valid nevertheless. */
1408 	if (cclass == 0)
1409 		return 0;
1410 	return iswctype(chr, cclass);
1411 }
1412 
1413 
1414 /*
1415  * Returns true if the pattern matches the string.
1416  */
1417 
1418 static int
1419 patmatch(const char *pattern, const char *string, int squoted)
1420 {
1421 	const char *p, *q, *end;
1422 	const char *bt_p, *bt_q;
1423 	char c;
1424 	wchar_t wc, wc2;
1425 
1426 	p = pattern;
1427 	q = string;
1428 	bt_p = NULL;
1429 	bt_q = NULL;
1430 	for (;;) {
1431 		switch (c = *p++) {
1432 		case '\0':
1433 			if (*q != '\0')
1434 				goto backtrack;
1435 			return 1;
1436 		case CTLESC:
1437 			if (squoted && *q == CTLESC)
1438 				q++;
1439 			if (*q++ != *p++)
1440 				goto backtrack;
1441 			break;
1442 		case CTLQUOTEMARK:
1443 			continue;
1444 		case '?':
1445 			if (squoted && *q == CTLESC)
1446 				q++;
1447 			if (*q == '\0')
1448 				return 0;
1449 			if (localeisutf8) {
1450 				wc = get_wc(&q);
1451 				/*
1452 				 * A '?' does not match invalid UTF-8 but a
1453 				 * '*' does, so backtrack.
1454 				 */
1455 				if (wc == 0)
1456 					goto backtrack;
1457 			} else
1458 				wc = (unsigned char)*q++;
1459 			break;
1460 		case '*':
1461 			c = *p;
1462 			while (c == CTLQUOTEMARK || c == '*')
1463 				c = *++p;
1464 			/*
1465 			 * If the pattern ends here, we know the string
1466 			 * matches without needing to look at the rest of it.
1467 			 */
1468 			if (c == '\0')
1469 				return 1;
1470 			/*
1471 			 * First try the shortest match for the '*' that
1472 			 * could work. We can forget any earlier '*' since
1473 			 * there is no way having it match more characters
1474 			 * can help us, given that we are already here.
1475 			 */
1476 			bt_p = p;
1477 			bt_q = q;
1478 			break;
1479 		case '[': {
1480 			const char *endp;
1481 			int invert, found;
1482 			wchar_t chr;
1483 
1484 			endp = p;
1485 			if (*endp == '!' || *endp == '^')
1486 				endp++;
1487 			for (;;) {
1488 				while (*endp == CTLQUOTEMARK)
1489 					endp++;
1490 				if (*endp == 0)
1491 					goto dft;		/* no matching ] */
1492 				if (*endp == CTLESC)
1493 					endp++;
1494 				if (*++endp == ']')
1495 					break;
1496 			}
1497 			invert = 0;
1498 			if (*p == '!' || *p == '^') {
1499 				invert++;
1500 				p++;
1501 			}
1502 			found = 0;
1503 			if (squoted && *q == CTLESC)
1504 				q++;
1505 			if (*q == '\0')
1506 				return 0;
1507 			if (localeisutf8) {
1508 				chr = get_wc(&q);
1509 				if (chr == 0)
1510 					goto backtrack;
1511 			} else
1512 				chr = (unsigned char)*q++;
1513 			c = *p++;
1514 			do {
1515 				if (c == CTLQUOTEMARK)
1516 					continue;
1517 				if (c == '[' && *p == ':') {
1518 					found |= match_charclass(p, chr, &end);
1519 					if (end != NULL)
1520 						p = end;
1521 				}
1522 				if (c == CTLESC)
1523 					c = *p++;
1524 				if (localeisutf8 && c & 0x80) {
1525 					p--;
1526 					wc = get_wc(&p);
1527 					if (wc == 0) /* bad utf-8 */
1528 						return 0;
1529 				} else
1530 					wc = (unsigned char)c;
1531 				if (*p == '-' && p[1] != ']') {
1532 					p++;
1533 					while (*p == CTLQUOTEMARK)
1534 						p++;
1535 					if (*p == CTLESC)
1536 						p++;
1537 					if (localeisutf8) {
1538 						wc2 = get_wc(&p);
1539 						if (wc2 == 0) /* bad utf-8 */
1540 							return 0;
1541 					} else
1542 						wc2 = (unsigned char)*p++;
1543 					if (   collate_range_cmp(chr, wc) >= 0
1544 					    && collate_range_cmp(chr, wc2) <= 0
1545 					   )
1546 						found = 1;
1547 				} else {
1548 					if (chr == wc)
1549 						found = 1;
1550 				}
1551 			} while ((c = *p++) != ']');
1552 			if (found == invert)
1553 				goto backtrack;
1554 			break;
1555 		}
1556 dft:	        default:
1557 			if (squoted && *q == CTLESC)
1558 				q++;
1559 			if (*q == '\0')
1560 				return 0;
1561 			if (*q++ == c)
1562 				break;
1563 backtrack:
1564 			/*
1565 			 * If we have a mismatch (other than hitting the end
1566 			 * of the string), go back to the last '*' seen and
1567 			 * have it match one additional character.
1568 			 */
1569 			if (bt_p == NULL)
1570 				return 0;
1571 			if (squoted && *bt_q == CTLESC)
1572 				bt_q++;
1573 			if (*bt_q == '\0')
1574 				return 0;
1575 			bt_q++;
1576 			p = bt_p;
1577 			q = bt_q;
1578 			break;
1579 		}
1580 	}
1581 }
1582 
1583 
1584 
1585 /*
1586  * Remove any CTLESC and CTLQUOTEMARK characters from a string.
1587  */
1588 
1589 void
1590 rmescapes(char *str)
1591 {
1592 	char *p, *q;
1593 
1594 	p = str;
1595 	while (*p != CTLESC && *p != CTLQUOTEMARK && *p != CTLQUOTEEND) {
1596 		if (*p++ == '\0')
1597 			return;
1598 	}
1599 	q = p;
1600 	while (*p) {
1601 		if (*p == CTLQUOTEMARK || *p == CTLQUOTEEND) {
1602 			p++;
1603 			continue;
1604 		}
1605 		if (*p == CTLESC)
1606 			p++;
1607 		*q++ = *p++;
1608 	}
1609 	*q = '\0';
1610 }
1611 
1612 
1613 
1614 /*
1615  * See if a pattern matches in a case statement.
1616  */
1617 
1618 int
1619 casematch(union node *pattern, const char *val)
1620 {
1621 	struct stackmark smark;
1622 	int result;
1623 	char *p;
1624 
1625 	setstackmark(&smark);
1626 	argbackq = pattern->narg.backquote;
1627 	STARTSTACKSTR(expdest);
1628 	ifslastp = NULL;
1629 	argstr(pattern->narg.text, EXP_TILDE | EXP_CASE);
1630 	STPUTC('\0', expdest);
1631 	p = grabstackstr(expdest);
1632 	result = patmatch(p, val, 0);
1633 	popstackmark(&smark);
1634 	return result;
1635 }
1636 
1637 /*
1638  * Our own itoa().
1639  */
1640 
1641 static char *
1642 cvtnum(int num, char *buf)
1643 {
1644 	char temp[32];
1645 	int neg = num < 0;
1646 	char *p = temp + 31;
1647 
1648 	temp[31] = '\0';
1649 
1650 	do {
1651 		*--p = num % 10 + '0';
1652 	} while ((num /= 10) != 0);
1653 
1654 	if (neg)
1655 		*--p = '-';
1656 
1657 	STPUTS(p, buf);
1658 	return buf;
1659 }
1660 
1661 /*
1662  * Do most of the work for wordexp(3).
1663  */
1664 
1665 int
1666 wordexpcmd(int argc, char **argv)
1667 {
1668 	size_t len;
1669 	int i;
1670 
1671 	out1fmt("%08x", argc - 1);
1672 	for (i = 1, len = 0; i < argc; i++)
1673 		len += strlen(argv[i]);
1674 	out1fmt("%08x", (int)len);
1675 	for (i = 1; i < argc; i++)
1676 		outbin(argv[i], strlen(argv[i]) + 1, out1);
1677         return (0);
1678 }
1679