expand.c revision 25905 
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 *	$Id: expand.c,v 1.17 1997/04/28 03:28:43 steve Exp $
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 *, int));
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	char *p;
214	int flag;
215{
216	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	while (ifsfirst.next != NULL) {
329		struct ifsregion *ifsp;
330		INTOFF;
331		ifsp = ifsfirst.next->next;
332		ckfree(ifsfirst.next);
333		ifsfirst.next = ifsp;
334		INTON;
335	}
336	ifslastp = NULL;
337
338	/*
339	 * This routine is slightly over-compilcated for
340	 * efficiency.  First we make sure there is
341	 * enough space for the result, which may be bigger
342	 * than the expression if we add exponentation.  Next we
343	 * scan backwards looking for the start of arithmetic.  If the
344	 * next previous character is a CTLESC character, then we
345	 * have to rescan starting from the beginning since CTLESC
346	 * characters have to be processed left to right.
347	 */
348#if INT_MAX / 1000000000 >= 10 || INT_MIN / 1000000000 <= -10
349#error "integers with more than 10 digits are not supported"
350#endif
351	CHECKSTRSPACE(12 - 2, expdest);
352	USTPUTC('\0', expdest);
353	start = stackblock();
354	p = expdest;
355	while (*p != CTLARI && p >= start)
356		--p;
357	if (*p != CTLARI)
358		error("missing CTLARI (shouldn't happen)");
359	if (p > start && *(p-1) == CTLESC)
360		for (p = start; *p != CTLARI; p++)
361			if (*p == CTLESC)
362				p++;
363	if (quotes)
364		rmescapes(p+1);
365	result = arith(p+1);
366	fmtstr(p, 12, "%d", result);
367	while (*p++)
368		;
369	result = expdest - p + 1;
370	STADJUST(-result, expdest);
371}
372
373
374/*
375 * Expand stuff in backwards quotes.
376 */
377
378STATIC void
379expbackq(cmd, quoted, flag)
380	union node *cmd;
381	int quoted;
382	int flag;
383{
384	struct backcmd in;
385	int i;
386	char buf[128];
387	char *p;
388	char *dest = expdest;
389	struct ifsregion saveifs, *savelastp;
390	struct nodelist *saveargbackq;
391	char lastc;
392	int startloc = dest - stackblock();
393	char const *syntax = quoted? DQSYNTAX : BASESYNTAX;
394	int saveherefd;
395	int quotes = flag & (EXP_FULL | EXP_CASE);
396
397	INTOFF;
398	saveifs = ifsfirst;
399	savelastp = ifslastp;
400	saveargbackq = argbackq;
401	saveherefd = herefd;
402	herefd = -1;
403	p = grabstackstr(dest);
404	evalbackcmd(cmd, &in);
405	ungrabstackstr(p, dest);
406	ifsfirst = saveifs;
407	ifslastp = savelastp;
408	argbackq = saveargbackq;
409	herefd = saveherefd;
410
411	p = in.buf;
412	lastc = '\0';
413	for (;;) {
414		if (--in.nleft < 0) {
415			if (in.fd < 0)
416				break;
417			while ((i = read(in.fd, buf, sizeof buf)) < 0 && errno == EINTR);
418			TRACE(("expbackq: read returns %d\n", i));
419			if (i <= 0)
420				break;
421			p = buf;
422			in.nleft = i - 1;
423		}
424		lastc = *p++;
425		if (lastc != '\0') {
426			if (quotes && syntax[lastc] == CCTL)
427				STPUTC(CTLESC, dest);
428			STPUTC(lastc, dest);
429		}
430	}
431
432	/* Eat all trailing newlines */
433	for (p--; lastc == '\n'; lastc = *--p)
434		STUNPUTC(dest);
435
436	if (in.fd >= 0)
437		close(in.fd);
438	if (in.buf)
439		ckfree(in.buf);
440	if (in.jp)
441		exitstatus = waitforjob(in.jp);
442	if (quoted == 0)
443		recordregion(startloc, dest - stackblock(), 0);
444	TRACE(("evalbackq: size=%d: \"%.*s\"\n",
445		(dest - stackblock()) - startloc,
446		(dest - stackblock()) - startloc,
447		stackblock() + startloc));
448	expdest = dest;
449	INTON;
450}
451
452
453
454STATIC int
455subevalvar(p, str, strloc, subtype, startloc, varflags)
456	char *p;
457	char *str;
458	int strloc;
459	int subtype;
460	int startloc;
461	int varflags;
462{
463	char *startp;
464	char *loc = NULL;
465	int c = 0;
466	int saveherefd = herefd;
467	struct nodelist *saveargbackq = argbackq;
468	int amount;
469
470	herefd = -1;
471	argstr(p, 0);
472	STACKSTRNUL(expdest);
473	herefd = saveherefd;
474	argbackq = saveargbackq;
475	startp = stackblock() + startloc;
476	if (str == NULL)
477	    str = stackblock() + strloc;
478
479	switch (subtype) {
480	case VSASSIGN:
481		setvar(str, startp, 0);
482		amount = startp - expdest;
483		STADJUST(amount, expdest);
484		varflags &= ~VSNUL;
485		if (c != 0)
486			*loc = c;
487		return 1;
488
489	case VSQUESTION:
490		if (*p != CTLENDVAR) {
491			outfmt(&errout, "%s\n", startp);
492			error((char *)NULL);
493		}
494		error("%.*s: parameter %snot set", p - str - 1,
495		      str, (varflags & VSNUL) ? "null or "
496					      : nullstr);
497		return 0;
498
499	case VSTRIMLEFT:
500		for (loc = startp; loc < str; loc++) {
501			c = *loc;
502			*loc = '\0';
503			if (patmatch(str, startp)) {
504				*loc = c;
505				goto recordleft;
506			}
507			*loc = c;
508		}
509		return 0;
510
511	case VSTRIMLEFTMAX:
512		for (loc = str - 1; loc >= startp; loc--) {
513			c = *loc;
514			*loc = '\0';
515			if (patmatch(str, startp)) {
516				*loc = c;
517				goto recordleft;
518			}
519			*loc = c;
520		}
521		return 0;
522
523	case VSTRIMRIGHT:
524		for (loc = str - 1; loc >= startp; loc--) {
525			if (patmatch(str, loc)) {
526				amount = loc - expdest;
527				STADJUST(amount, expdest);
528				return 1;
529			}
530		}
531		return 0;
532
533	case VSTRIMRIGHTMAX:
534		for (loc = startp; loc < str - 1; loc++) {
535			if (patmatch(str, loc)) {
536				amount = loc - expdest;
537				STADJUST(amount, expdest);
538				return 1;
539			}
540		}
541		return 0;
542
543
544	default:
545		abort();
546	}
547
548recordleft:
549	amount = ((str - 1) - (loc - startp)) - expdest;
550	STADJUST(amount, expdest);
551	while (loc != str - 1)
552		*startp++ = *loc++;
553	return 1;
554}
555
556
557/*
558 * Expand a variable, and return a pointer to the next character in the
559 * input string.
560 */
561
562STATIC char *
563evalvar(p, flag)
564	char *p;
565	int flag;
566{
567	int subtype;
568	int varflags;
569	char *var;
570	char *val;
571	char *pat;
572	int c;
573	int set;
574	int special;
575	int startloc;
576	int varlen;
577	int easy;
578	int quotes = flag & (EXP_FULL | EXP_CASE);
579
580	varflags = *p++;
581	subtype = varflags & VSTYPE;
582	var = p;
583	special = 0;
584	if (! is_name(*p))
585		special = 1;
586	p = strchr(p, '=') + 1;
587again: /* jump here after setting a variable with ${var=text} */
588	if (special) {
589		set = varisset(var, varflags & VSNUL);
590		val = NULL;
591	} else {
592		val = lookupvar(var);
593		if (val == NULL || ((varflags & VSNUL) && val[0] == '\0')) {
594			val = NULL;
595			set = 0;
596		} else
597			set = 1;
598	}
599	varlen = 0;
600	startloc = expdest - stackblock();
601	if (set && subtype != VSPLUS) {
602		/* insert the value of the variable */
603		if (special) {
604			varvalue(var, varflags & VSQUOTE, flag & EXP_FULL);
605			if (subtype == VSLENGTH) {
606				varlen = expdest - stackblock() - startloc;
607				STADJUST(-varlen, expdest);
608			}
609		} else {
610			char const *syntax = (varflags & VSQUOTE) ? DQSYNTAX
611								  : BASESYNTAX;
612
613			if (subtype == VSLENGTH) {
614				for (;*val; val++)
615					varlen++;
616			}
617			else {
618				while (*val) {
619					if (quotes && syntax[*val] == CCTL)
620						STPUTC(CTLESC, expdest);
621					STPUTC(*val++, expdest);
622				}
623
624			}
625		}
626	}
627
628	if (subtype == VSPLUS)
629		set = ! set;
630
631	easy = ((varflags & VSQUOTE) == 0 ||
632		(*var == '@' && shellparam.nparam != 1));
633
634
635	switch (subtype) {
636	case VSLENGTH:
637		expdest = cvtnum(varlen, expdest);
638		goto record;
639
640	case VSNORMAL:
641		if (!easy)
642			break;
643record:
644		recordregion(startloc, expdest - stackblock(),
645			     varflags & VSQUOTE);
646		break;
647
648	case VSPLUS:
649	case VSMINUS:
650		if (!set) {
651			argstr(p, flag);
652			break;
653		}
654		if (easy)
655			goto record;
656		break;
657
658	case VSTRIMLEFT:
659	case VSTRIMLEFTMAX:
660	case VSTRIMRIGHT:
661	case VSTRIMRIGHTMAX:
662		if (!set)
663			break;
664		/*
665		 * Terminate the string and start recording the pattern
666		 * right after it
667		 */
668		STPUTC('\0', expdest);
669		pat = expdest;
670		if (subevalvar(p, NULL, expdest - stackblock(), subtype,
671			       startloc, varflags))
672			goto record;
673		else {
674			int amount = (expdest - pat) + 1;
675			STADJUST(-amount, expdest);
676		}
677		break;
678
679	case VSASSIGN:
680	case VSQUESTION:
681		if (!set) {
682			if (subevalvar(p, var, 0, subtype, startloc, varflags)) {
683				varflags &= ~VSNUL;
684				goto again;
685			}
686			break;
687		}
688		if (easy)
689			goto record;
690		break;
691
692	default:
693		abort();
694	}
695
696	if (subtype != VSNORMAL) {	/* skip to end of alternative */
697		int nesting = 1;
698		for (;;) {
699			if ((c = *p++) == CTLESC)
700				p++;
701			else if (c == CTLBACKQ || c == (CTLBACKQ|CTLQUOTE)) {
702				if (set)
703					argbackq = argbackq->next;
704			} else if (c == CTLVAR) {
705				if ((*p++ & VSTYPE) != VSNORMAL)
706					nesting++;
707			} else if (c == CTLENDVAR) {
708				if (--nesting == 0)
709					break;
710			}
711		}
712	}
713	return p;
714}
715
716
717
718/*
719 * Test whether a specialized variable is set.
720 */
721
722STATIC int
723varisset(name, nulok)
724	char *name;
725	int nulok;
726{
727
728	if (*name == '!')
729		return backgndpid != -1;
730	else if (*name == '@' || *name == '*') {
731		if (*shellparam.p == NULL)
732			return 0;
733
734		if (nulok) {
735			char **av;
736
737			for (av = shellparam.p; *av; av++)
738				if (**av != '\0')
739					return 1;
740			return 0;
741		}
742	} else if (is_digit(*name)) {
743		char *ap;
744		int num = atoi(name);
745
746		if (num > shellparam.nparam)
747			return 0;
748
749		if (num == 0)
750			ap = arg0;
751		else
752			ap = shellparam.p[num - 1];
753
754		if (nulok && (ap == NULL || *ap == '\0'))
755			return 0;
756	}
757	return 1;
758}
759
760
761
762/*
763 * Add the value of a specialized variable to the stack string.
764 */
765
766STATIC void
767varvalue(name, quoted, allow_split)
768	char *name;
769	int quoted;
770	int allow_split;
771{
772	int num;
773	char *p;
774	int i;
775	extern int oexitstatus;
776	char sep;
777	char **ap;
778	char const *syntax;
779
780#define STRTODEST(p) \
781	do {\
782	if (allow_split) { \
783		syntax = quoted? DQSYNTAX : BASESYNTAX; \
784		while (*p) { \
785			if (syntax[*p] == CCTL) \
786				STPUTC(CTLESC, expdest); \
787			STPUTC(*p++, expdest); \
788		} \
789	} else \
790		while (*p) \
791			STPUTC(*p++, expdest); \
792	} while (0)
793
794
795	switch (*name) {
796	case '$':
797		num = rootpid;
798		goto numvar;
799	case '?':
800		num = oexitstatus;
801		goto numvar;
802	case '#':
803		num = shellparam.nparam;
804		goto numvar;
805	case '!':
806		num = backgndpid;
807numvar:
808		expdest = cvtnum(num, expdest);
809		break;
810	case '-':
811		for (i = 0 ; i < NOPTS ; i++) {
812			if (optlist[i].val)
813				STPUTC(optlist[i].letter, expdest);
814		}
815		break;
816	case '@':
817		if (allow_split) {
818			sep = '\0';
819			goto allargs;
820		}
821		/* fall through */
822	case '*':
823		sep = ' ';
824allargs:
825		for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
826			STRTODEST(p);
827			if (*ap)
828				STPUTC(sep, expdest);
829		}
830		break;
831	case '0':
832		p = arg0;
833		STRTODEST(p);
834		break;
835	default:
836		if (is_digit(*name)) {
837			num = atoi(name);
838			if (num > 0 && num <= shellparam.nparam) {
839				p = shellparam.p[num - 1];
840				STRTODEST(p);
841			}
842		}
843		break;
844	}
845}
846
847
848
849/*
850 * Record the the fact that we have to scan this region of the
851 * string for IFS characters.
852 */
853
854STATIC void
855recordregion(start, end, nulonly)
856	int start;
857	int end;
858	int nulonly;
859{
860	struct ifsregion *ifsp;
861
862	if (ifslastp == NULL) {
863		ifsp = &ifsfirst;
864	} else {
865		ifsp = (struct ifsregion *)ckmalloc(sizeof (struct ifsregion));
866		ifslastp->next = ifsp;
867	}
868	ifslastp = ifsp;
869	ifslastp->next = NULL;
870	ifslastp->begoff = start;
871	ifslastp->endoff = end;
872	ifslastp->nulonly = nulonly;
873}
874
875
876
877/*
878 * Break the argument string into pieces based upon IFS and add the
879 * strings to the argument list.  The regions of the string to be
880 * searched for IFS characters have been stored by recordregion.
881 */
882STATIC void
883ifsbreakup(string, arglist)
884	char *string;
885	struct arglist *arglist;
886	{
887	struct ifsregion *ifsp;
888	struct strlist *sp;
889	char *start;
890	char *p;
891	char *q;
892	char *ifs;
893	int ifsspc;
894
895
896	start = string;
897	if (ifslastp != NULL) {
898		ifsp = &ifsfirst;
899		do {
900			p = string + ifsp->begoff;
901			ifs = ifsp->nulonly? nullstr : ifsval();
902			ifsspc = strchr(ifs, ' ') != NULL;
903			while (p < string + ifsp->endoff) {
904				q = p;
905				if (*p == CTLESC)
906					p++;
907				if (strchr(ifs, *p++)) {
908					if (q > start || !ifsspc) {
909						*q = '\0';
910						sp = (struct strlist *)stalloc(sizeof *sp);
911						sp->text = start;
912						*arglist->lastp = sp;
913						arglist->lastp = &sp->next;
914					}
915					if (ifsspc) {
916						for (;;) {
917							if (p >= string + ifsp->endoff)
918								break;
919							q = p;
920							if (*p == CTLESC)
921								p++;
922							if (strchr(ifs, *p++) == NULL) {
923								p = q;
924								break;
925							}
926						}
927					}
928					start = p;
929				}
930			}
931		} while ((ifsp = ifsp->next) != NULL);
932		if (*start || (!ifsspc && start > string)) {
933			sp = (struct strlist *)stalloc(sizeof *sp);
934			sp->text = start;
935			*arglist->lastp = sp;
936			arglist->lastp = &sp->next;
937		}
938	} else {
939		sp = (struct strlist *)stalloc(sizeof *sp);
940		sp->text = start;
941		*arglist->lastp = sp;
942		arglist->lastp = &sp->next;
943	}
944}
945
946
947
948/*
949 * Expand shell metacharacters.  At this point, the only control characters
950 * should be escapes.  The results are stored in the list exparg.
951 */
952
953char *expdir;
954
955
956STATIC void
957expandmeta(str, flag)
958	struct strlist *str;
959	int flag __unused;
960{
961	char *p;
962	struct strlist **savelastp;
963	struct strlist *sp;
964	char c;
965	/* TODO - EXP_REDIR */
966
967	while (str) {
968		if (fflag)
969			goto nometa;
970		p = str->text;
971		for (;;) {			/* fast check for meta chars */
972			if ((c = *p++) == '\0')
973				goto nometa;
974			if (c == '*' || c == '?' || c == '[' || c == '!')
975				break;
976		}
977		savelastp = exparg.lastp;
978		INTOFF;
979		if (expdir == NULL) {
980			int i = strlen(str->text);
981			expdir = ckmalloc(i < 2048 ? 2048 : i); /* XXX */
982		}
983
984		expmeta(expdir, str->text);
985		ckfree(expdir);
986		expdir = NULL;
987		INTON;
988		if (exparg.lastp == savelastp) {
989			/*
990			 * no matches
991			 */
992nometa:
993			*exparg.lastp = str;
994			rmescapes(str->text);
995			exparg.lastp = &str->next;
996		} else {
997			*exparg.lastp = NULL;
998			*savelastp = sp = expsort(*savelastp);
999			while (sp->next != NULL)
1000				sp = sp->next;
1001			exparg.lastp = &sp->next;
1002		}
1003		str = str->next;
1004	}
1005}
1006
1007
1008/*
1009 * Do metacharacter (i.e. *, ?, [...]) expansion.
1010 */
1011
1012STATIC void
1013expmeta(enddir, name)
1014	char *enddir;
1015	char *name;
1016	{
1017	char *p;
1018	char *q;
1019	char *start;
1020	char *endname;
1021	int metaflag;
1022	struct stat statb;
1023	DIR *dirp;
1024	struct dirent *dp;
1025	int atend;
1026	int matchdot;
1027
1028	metaflag = 0;
1029	start = name;
1030	for (p = name ; ; p++) {
1031		if (*p == '*' || *p == '?')
1032			metaflag = 1;
1033		else if (*p == '[') {
1034			q = p + 1;
1035			if (*q == '!')
1036				q++;
1037			for (;;) {
1038				if (*q == CTLESC)
1039					q++;
1040				if (*q == '/' || *q == '\0')
1041					break;
1042				if (*++q == ']') {
1043					metaflag = 1;
1044					break;
1045				}
1046			}
1047		} else if (*p == '!' && p[1] == '!'	&& (p == name || p[-1] == '/')) {
1048			metaflag = 1;
1049		} else if (*p == '\0')
1050			break;
1051		else if (*p == CTLESC)
1052			p++;
1053		if (*p == '/') {
1054			if (metaflag)
1055				break;
1056			start = p + 1;
1057		}
1058	}
1059	if (metaflag == 0) {	/* we've reached the end of the file name */
1060		if (enddir != expdir)
1061			metaflag++;
1062		for (p = name ; ; p++) {
1063			if (*p == CTLESC)
1064				p++;
1065			*enddir++ = *p;
1066			if (*p == '\0')
1067				break;
1068		}
1069		if (metaflag == 0 || stat(expdir, &statb) >= 0)
1070			addfname(expdir);
1071		return;
1072	}
1073	endname = p;
1074	if (start != name) {
1075		p = name;
1076		while (p < start) {
1077			if (*p == CTLESC)
1078				p++;
1079			*enddir++ = *p++;
1080		}
1081	}
1082	if (enddir == expdir) {
1083		p = ".";
1084	} else if (enddir == expdir + 1 && *expdir == '/') {
1085		p = "/";
1086	} else {
1087		p = expdir;
1088		enddir[-1] = '\0';
1089	}
1090	if ((dirp = opendir(p)) == NULL)
1091		return;
1092	if (enddir != expdir)
1093		enddir[-1] = '/';
1094	if (*endname == 0) {
1095		atend = 1;
1096	} else {
1097		atend = 0;
1098		*endname++ = '\0';
1099	}
1100	matchdot = 0;
1101	if (start[0] == '.' || (start[0] == CTLESC && start[1] == '.'))
1102		matchdot++;
1103	while (! int_pending() && (dp = readdir(dirp)) != NULL) {
1104		if (dp->d_name[0] == '.' && ! matchdot)
1105			continue;
1106		if (patmatch(start, dp->d_name)) {
1107			if (atend) {
1108				scopy(dp->d_name, enddir);
1109				addfname(expdir);
1110			} else {
1111				char *q;
1112				for (p = enddir, q = dp->d_name;
1113				     (*p++ = *q++) != '\0';)
1114					continue;
1115				p[-1] = '/';
1116				expmeta(p, endname);
1117			}
1118		}
1119	}
1120	closedir(dirp);
1121	if (! atend)
1122		endname[-1] = '/';
1123}
1124
1125
1126/*
1127 * Add a file name to the list.
1128 */
1129
1130STATIC void
1131addfname(name)
1132	char *name;
1133	{
1134	char *p;
1135	struct strlist *sp;
1136
1137	p = stalloc(strlen(name) + 1);
1138	scopy(name, p);
1139	sp = (struct strlist *)stalloc(sizeof *sp);
1140	sp->text = p;
1141	*exparg.lastp = sp;
1142	exparg.lastp = &sp->next;
1143}
1144
1145
1146/*
1147 * Sort the results of file name expansion.  It calculates the number of
1148 * strings to sort and then calls msort (short for merge sort) to do the
1149 * work.
1150 */
1151
1152STATIC struct strlist *
1153expsort(str)
1154	struct strlist *str;
1155	{
1156	int len;
1157	struct strlist *sp;
1158
1159	len = 0;
1160	for (sp = str ; sp ; sp = sp->next)
1161		len++;
1162	return msort(str, len);
1163}
1164
1165
1166STATIC struct strlist *
1167msort(list, len)
1168	struct strlist *list;
1169	int len;
1170{
1171	struct strlist *p, *q = NULL;
1172	struct strlist **lpp;
1173	int half;
1174	int n;
1175
1176	if (len <= 1)
1177		return list;
1178	half = len >> 1;
1179	p = list;
1180	for (n = half ; --n >= 0 ; ) {
1181		q = p;
1182		p = p->next;
1183	}
1184	q->next = NULL;			/* terminate first half of list */
1185	q = msort(list, half);		/* sort first half of list */
1186	p = msort(p, len - half);		/* sort second half */
1187	lpp = &list;
1188	for (;;) {
1189		if (strcmp(p->text, q->text) < 0) {
1190			*lpp = p;
1191			lpp = &p->next;
1192			if ((p = *lpp) == NULL) {
1193				*lpp = q;
1194				break;
1195			}
1196		} else {
1197			*lpp = q;
1198			lpp = &q->next;
1199			if ((q = *lpp) == NULL) {
1200				*lpp = p;
1201				break;
1202			}
1203		}
1204	}
1205	return list;
1206}
1207
1208
1209
1210/*
1211 * Returns true if the pattern matches the string.
1212 */
1213
1214int
1215patmatch(pattern, string)
1216	char *pattern;
1217	char *string;
1218	{
1219#ifdef notdef
1220	if (pattern[0] == '!' && pattern[1] == '!')
1221		return 1 - pmatch(pattern + 2, string);
1222	else
1223#endif
1224		return pmatch(pattern, string);
1225}
1226
1227
1228STATIC int
1229pmatch(pattern, string)
1230	char *pattern;
1231	char *string;
1232	{
1233	char *p, *q;
1234	char c;
1235
1236	p = pattern;
1237	q = string;
1238	for (;;) {
1239		switch (c = *p++) {
1240		case '\0':
1241			goto breakloop;
1242		case CTLESC:
1243			if (*q++ != *p++)
1244				return 0;
1245			break;
1246		case '?':
1247			if (*q++ == '\0')
1248				return 0;
1249			break;
1250		case '*':
1251			c = *p;
1252			if (c != CTLESC && c != '?' && c != '*' && c != '[') {
1253				while (*q != c) {
1254					if (*q == '\0')
1255						return 0;
1256					q++;
1257				}
1258			}
1259			do {
1260				if (pmatch(p, q))
1261					return 1;
1262			} while (*q++ != '\0');
1263			return 0;
1264		case '[': {
1265			char *endp;
1266			int invert, found;
1267			char chr;
1268
1269			endp = p;
1270			if (*endp == '!')
1271				endp++;
1272			for (;;) {
1273				if (*endp == '\0')
1274					goto dft;		/* no matching ] */
1275				if (*endp == CTLESC)
1276					endp++;
1277				if (*++endp == ']')
1278					break;
1279			}
1280			invert = 0;
1281			if (*p == '!') {
1282				invert++;
1283				p++;
1284			}
1285			found = 0;
1286			chr = *q++;
1287			if (chr == '\0')
1288				return 0;
1289			c = *p++;
1290			do {
1291				if (c == CTLESC)
1292					c = *p++;
1293				if (*p == '-' && p[1] != ']') {
1294					p++;
1295					if (*p == CTLESC)
1296						p++;
1297					if (   collate_range_cmp(chr, c) >= 0
1298					    && collate_range_cmp(chr, *p) <= 0
1299					   )
1300						found = 1;
1301					p++;
1302				} else {
1303					if (chr == c)
1304						found = 1;
1305				}
1306			} while ((c = *p++) != ']');
1307			if (found == invert)
1308				return 0;
1309			break;
1310		}
1311dft:	        default:
1312			if (*q++ != c)
1313				return 0;
1314			break;
1315		}
1316	}
1317breakloop:
1318	if (*q != '\0')
1319		return 0;
1320	return 1;
1321}
1322
1323
1324
1325/*
1326 * Remove any CTLESC characters from a string.
1327 */
1328
1329void
1330rmescapes(str)
1331	char *str;
1332	{
1333	char *p, *q;
1334
1335	p = str;
1336	while (*p != CTLESC) {
1337		if (*p++ == '\0')
1338			return;
1339	}
1340	q = p;
1341	while (*p) {
1342		if (*p == CTLESC)
1343			p++;
1344		*q++ = *p++;
1345	}
1346	*q = '\0';
1347}
1348
1349
1350
1351/*
1352 * See if a pattern matches in a case statement.
1353 */
1354
1355int
1356casematch(pattern, val)
1357	union node *pattern;
1358	char *val;
1359	{
1360	struct stackmark smark;
1361	int result;
1362	char *p;
1363
1364	setstackmark(&smark);
1365	argbackq = pattern->narg.backquote;
1366	STARTSTACKSTR(expdest);
1367	ifslastp = NULL;
1368	argstr(pattern->narg.text, EXP_TILDE | EXP_CASE);
1369	STPUTC('\0', expdest);
1370	p = grabstackstr(expdest);
1371	result = patmatch(p, val);
1372	popstackmark(&smark);
1373	return result;
1374}
1375
1376/*
1377 * Our own itoa().
1378 */
1379
1380STATIC char *
1381cvtnum(num, buf)
1382	int num;
1383	char *buf;
1384	{
1385	char temp[32];
1386	int neg = num < 0;
1387	char *p = temp + 31;
1388
1389	temp[31] = '\0';
1390
1391	do {
1392		*--p = num % 10 + '0';
1393	} while ((num /= 10) != 0);
1394
1395	if (neg)
1396		*--p = '-';
1397
1398	while (*p)
1399		STPUTC(*p++, buf);
1400	return buf;
1401}
1402