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