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