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