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