expand.c revision 3044 
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$
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	if (lastc == '\n') {
406		STUNPUTC(dest);
407	}
408	if (in.fd >= 0)
409		close(in.fd);
410	if (in.buf)
411		ckfree(in.buf);
412	if (in.jp)
413		exitstatus = waitforjob(in.jp);
414	if (quoted == 0)
415		recordregion(startloc, dest - stackblock(), 0);
416	TRACE(("evalbackq: size=%d: \"%.*s\"\n",
417		(dest - stackblock()) - startloc,
418		(dest - stackblock()) - startloc,
419		stackblock() + startloc));
420	expdest = dest;
421	INTON;
422}
423
424
425
426/*
427 * Expand a variable, and return a pointer to the next character in the
428 * input string.
429 */
430
431STATIC char *
432evalvar(p, flag)
433	char *p;
434	{
435	int subtype;
436	int varflags;
437	char *var;
438	char *val;
439	int c;
440	int set;
441	int special;
442	int startloc;
443	int quotes = flag & (EXP_FULL | EXP_CASE);
444
445	varflags = *p++;
446	subtype = varflags & VSTYPE;
447	var = p;
448	special = 0;
449	if (! is_name(*p))
450		special = 1;
451	p = strchr(p, '=') + 1;
452again: /* jump here after setting a variable with ${var=text} */
453	if (special) {
454		set = varisset(*var);
455		val = NULL;
456	} else {
457		val = lookupvar(var);
458		if (val == NULL || (varflags & VSNUL) && val[0] == '\0') {
459			val = NULL;
460			set = 0;
461		} else
462			set = 1;
463	}
464	startloc = expdest - stackblock();
465	if (set && subtype != VSPLUS) {
466		/* insert the value of the variable */
467		if (special) {
468			varvalue(*var, varflags & VSQUOTE, flag & EXP_FULL);
469		} else {
470			char const *syntax = (varflags & VSQUOTE)? DQSYNTAX : BASESYNTAX;
471
472			while (*val) {
473				if (quotes && syntax[*val] == CCTL)
474					STPUTC(CTLESC, expdest);
475				STPUTC(*val++, expdest);
476			}
477		}
478	}
479	if (subtype == VSPLUS)
480		set = ! set;
481	if (((varflags & VSQUOTE) == 0 || (*var == '@' && shellparam.nparam != 1))
482	 && (set || subtype == VSNORMAL))
483		recordregion(startloc, expdest - stackblock(), varflags & VSQUOTE);
484	if (! set && subtype != VSNORMAL) {
485		if (subtype == VSPLUS || subtype == VSMINUS) {
486			argstr(p, flag);
487		} else {
488			char *startp;
489			int saveherefd = herefd;
490			struct nodelist *saveargbackq = argbackq;
491			herefd = -1;
492			argstr(p, 0);
493			STACKSTRNUL(expdest);
494			herefd = saveherefd;
495			argbackq = saveargbackq;
496			startp = stackblock() + startloc;
497			if (subtype == VSASSIGN) {
498				setvar(var, startp, 0);
499				STADJUST(startp - expdest, expdest);
500				varflags &=~ VSNUL;
501				goto again;
502			}
503			/* subtype == VSQUESTION */
504			if (*p != CTLENDVAR) {
505				outfmt(&errout, "%s\n", startp);
506				error((char *)NULL);
507			}
508			error("%.*s: parameter %snot set", p - var - 1,
509				var, (varflags & VSNUL)? "null or " : nullstr);
510		}
511	}
512	if (subtype != VSNORMAL) {	/* skip to end of alternative */
513		int nesting = 1;
514		for (;;) {
515			if ((c = *p++) == CTLESC)
516				p++;
517			else if (c == CTLBACKQ || c == (CTLBACKQ|CTLQUOTE)) {
518				if (set)
519					argbackq = argbackq->next;
520			} else if (c == CTLVAR) {
521				if ((*p++ & VSTYPE) != VSNORMAL)
522					nesting++;
523			} else if (c == CTLENDVAR) {
524				if (--nesting == 0)
525					break;
526			}
527		}
528	}
529	return p;
530}
531
532
533
534/*
535 * Test whether a specialized variable is set.
536 */
537
538STATIC int
539varisset(name)
540	char name;
541	{
542	char **ap;
543
544	if (name == '!') {
545		if (backgndpid == -1)
546			return 0;
547	} else if (name == '@' || name == '*') {
548		if (*shellparam.p == NULL)
549			return 0;
550	} else if ((unsigned)(name -= '1') <= '9' - '1') {
551		ap = shellparam.p;
552		do {
553			if (*ap++ == NULL)
554				return 0;
555		} while (--name >= 0);
556	}
557	return 1;
558}
559
560
561
562/*
563 * Add the value of a specialized variable to the stack string.
564 */
565
566STATIC void
567varvalue(name, quoted, allow_split)
568	char name;
569	{
570	int num;
571	char temp[32];
572	char *p;
573	int i;
574	extern int exitstatus;
575	char sep;
576	char **ap;
577	char const *syntax;
578
579#define STRTODEST(p) \
580	do {\
581	if (allow_split) { \
582		syntax = quoted? DQSYNTAX : BASESYNTAX; \
583		while (*p) { \
584			if (syntax[*p] == CCTL) \
585				STPUTC(CTLESC, expdest); \
586			STPUTC(*p++, expdest); \
587		} \
588	} else \
589		while (*p) \
590			STPUTC(*p++, expdest); \
591	} while (0)
592
593
594	switch (name) {
595	case '$':
596		num = rootpid;
597		goto numvar;
598	case '?':
599		num = exitstatus;
600		goto numvar;
601	case '#':
602		num = shellparam.nparam;
603		goto numvar;
604	case '!':
605		num = backgndpid;
606numvar:
607		p = temp + 31;
608		temp[31] = '\0';
609		do {
610			*--p = num % 10 + '0';
611		} while ((num /= 10) != 0);
612		while (*p)
613			STPUTC(*p++, expdest);
614		break;
615	case '-':
616		for (i = 0 ; i < NOPTS ; i++) {
617			if (optlist[i].val)
618				STPUTC(optlist[i].letter, expdest);
619		}
620		break;
621	case '@':
622		if (allow_split) {
623			sep = '\0';
624			goto allargs;
625		}
626		/* fall through */
627	case '*':
628		sep = ' ';
629allargs:
630		for (ap = shellparam.p ; (p = *ap++) != NULL ; ) {
631			STRTODEST(p);
632			if (*ap)
633				STPUTC(sep, expdest);
634		}
635		break;
636	case '0':
637		p = arg0;
638		STRTODEST(p);
639		break;
640	default:
641		if ((unsigned)(name -= '1') <= '9' - '1') {
642			p = shellparam.p[name];
643			STRTODEST(p);
644		}
645		break;
646	}
647}
648
649
650
651/*
652 * Record the the fact that we have to scan this region of the
653 * string for IFS characters.
654 */
655
656STATIC void
657recordregion(start, end, nulonly) {
658	register struct ifsregion *ifsp;
659
660	if (ifslastp == NULL) {
661		ifsp = &ifsfirst;
662	} else {
663		ifsp = (struct ifsregion *)ckmalloc(sizeof (struct ifsregion));
664		ifslastp->next = ifsp;
665	}
666	ifslastp = ifsp;
667	ifslastp->next = NULL;
668	ifslastp->begoff = start;
669	ifslastp->endoff = end;
670	ifslastp->nulonly = nulonly;
671}
672
673
674
675/*
676 * Break the argument string into pieces based upon IFS and add the
677 * strings to the argument list.  The regions of the string to be
678 * searched for IFS characters have been stored by recordregion.
679 */
680
681STATIC void
682ifsbreakup(string, arglist)
683	char *string;
684	struct arglist *arglist;
685	{
686	struct ifsregion *ifsp;
687	struct strlist *sp;
688	char *start;
689	register char *p;
690	char *q;
691	char *ifs;
692
693	start = string;
694	if (ifslastp != NULL) {
695		ifsp = &ifsfirst;
696		do {
697			p = string + ifsp->begoff;
698			ifs = ifsp->nulonly? nullstr : ifsval();
699			while (p < string + ifsp->endoff) {
700				q = p;
701				if (*p == CTLESC)
702					p++;
703				if (strchr(ifs, *p++)) {
704					if (q > start || *ifs != ' ') {
705						*q = '\0';
706						sp = (struct strlist *)stalloc(sizeof *sp);
707						sp->text = start;
708						*arglist->lastp = sp;
709						arglist->lastp = &sp->next;
710					}
711					if (*ifs == ' ') {
712						for (;;) {
713							if (p >= string + ifsp->endoff)
714								break;
715							q = p;
716							if (*p == CTLESC)
717								p++;
718							if (strchr(ifs, *p++) == NULL) {
719								p = q;
720								break;
721							}
722						}
723					}
724					start = p;
725				}
726			}
727		} while ((ifsp = ifsp->next) != NULL);
728		if (*start || (*ifs != ' ' && start > string)) {
729			sp = (struct strlist *)stalloc(sizeof *sp);
730			sp->text = start;
731			*arglist->lastp = sp;
732			arglist->lastp = &sp->next;
733		}
734	} else {
735		sp = (struct strlist *)stalloc(sizeof *sp);
736		sp->text = start;
737		*arglist->lastp = sp;
738		arglist->lastp = &sp->next;
739	}
740}
741
742
743
744/*
745 * Expand shell metacharacters.  At this point, the only control characters
746 * should be escapes.  The results are stored in the list exparg.
747 */
748
749char *expdir;
750
751
752STATIC void
753expandmeta(str, flag)
754	struct strlist *str;
755	{
756	char *p;
757	struct strlist **savelastp;
758	struct strlist *sp;
759	char c;
760	/* TODO - EXP_REDIR */
761
762	while (str) {
763		if (fflag)
764			goto nometa;
765		p = str->text;
766		for (;;) {			/* fast check for meta chars */
767			if ((c = *p++) == '\0')
768				goto nometa;
769			if (c == '*' || c == '?' || c == '[' || c == '!')
770				break;
771		}
772		savelastp = exparg.lastp;
773		INTOFF;
774		if (expdir == NULL) {
775			int i = strlen(str->text);
776			expdir = ckmalloc(i < 2048 ? 2048 : i); /* XXX */
777		}
778
779		expmeta(expdir, str->text);
780		ckfree(expdir);
781		expdir = NULL;
782		INTON;
783		if (exparg.lastp == savelastp) {
784			/*
785			 * no matches
786			 */
787nometa:
788			*exparg.lastp = str;
789			rmescapes(str->text);
790			exparg.lastp = &str->next;
791		} else {
792			*exparg.lastp = NULL;
793			*savelastp = sp = expsort(*savelastp);
794			while (sp->next != NULL)
795				sp = sp->next;
796			exparg.lastp = &sp->next;
797		}
798		str = str->next;
799	}
800}
801
802
803/*
804 * Do metacharacter (i.e. *, ?, [...]) expansion.
805 */
806
807STATIC void
808expmeta(enddir, name)
809	char *enddir;
810	char *name;
811	{
812	register char *p;
813	char *q;
814	char *start;
815	char *endname;
816	int metaflag;
817	struct stat statb;
818	DIR *dirp;
819	struct dirent *dp;
820	int atend;
821	int matchdot;
822
823	metaflag = 0;
824	start = name;
825	for (p = name ; ; p++) {
826		if (*p == '*' || *p == '?')
827			metaflag = 1;
828		else if (*p == '[') {
829			q = p + 1;
830			if (*q == '!')
831				q++;
832			for (;;) {
833				if (*q == CTLESC)
834					q++;
835				if (*q == '/' || *q == '\0')
836					break;
837				if (*++q == ']') {
838					metaflag = 1;
839					break;
840				}
841			}
842		} else if (*p == '!' && p[1] == '!'	&& (p == name || p[-1] == '/')) {
843			metaflag = 1;
844		} else if (*p == '\0')
845			break;
846		else if (*p == CTLESC)
847			p++;
848		if (*p == '/') {
849			if (metaflag)
850				break;
851			start = p + 1;
852		}
853	}
854	if (metaflag == 0) {	/* we've reached the end of the file name */
855		if (enddir != expdir)
856			metaflag++;
857		for (p = name ; ; p++) {
858			if (*p == CTLESC)
859				p++;
860			*enddir++ = *p;
861			if (*p == '\0')
862				break;
863		}
864		if (metaflag == 0 || stat(expdir, &statb) >= 0)
865			addfname(expdir);
866		return;
867	}
868	endname = p;
869	if (start != name) {
870		p = name;
871		while (p < start) {
872			if (*p == CTLESC)
873				p++;
874			*enddir++ = *p++;
875		}
876	}
877	if (enddir == expdir) {
878		p = ".";
879	} else if (enddir == expdir + 1 && *expdir == '/') {
880		p = "/";
881	} else {
882		p = expdir;
883		enddir[-1] = '\0';
884	}
885	if ((dirp = opendir(p)) == NULL)
886		return;
887	if (enddir != expdir)
888		enddir[-1] = '/';
889	if (*endname == 0) {
890		atend = 1;
891	} else {
892		atend = 0;
893		*endname++ = '\0';
894	}
895	matchdot = 0;
896	if (start[0] == '.' || start[0] == CTLESC && start[1] == '.')
897		matchdot++;
898	while (! int_pending() && (dp = readdir(dirp)) != NULL) {
899		if (dp->d_name[0] == '.' && ! matchdot)
900			continue;
901		if (patmatch(start, dp->d_name)) {
902			if (atend) {
903				scopy(dp->d_name, enddir);
904				addfname(expdir);
905			} else {
906				char *q;
907				for (p = enddir, q = dp->d_name ; *p++ = *q++ ;);
908				p[-1] = '/';
909				expmeta(p, endname);
910			}
911		}
912	}
913	closedir(dirp);
914	if (! atend)
915		endname[-1] = '/';
916}
917
918
919/*
920 * Add a file name to the list.
921 */
922
923STATIC void
924addfname(name)
925	char *name;
926	{
927	char *p;
928	struct strlist *sp;
929
930	p = stalloc(strlen(name) + 1);
931	scopy(name, p);
932	sp = (struct strlist *)stalloc(sizeof *sp);
933	sp->text = p;
934	*exparg.lastp = sp;
935	exparg.lastp = &sp->next;
936}
937
938
939/*
940 * Sort the results of file name expansion.  It calculates the number of
941 * strings to sort and then calls msort (short for merge sort) to do the
942 * work.
943 */
944
945STATIC struct strlist *
946expsort(str)
947	struct strlist *str;
948	{
949	int len;
950	struct strlist *sp;
951
952	len = 0;
953	for (sp = str ; sp ; sp = sp->next)
954		len++;
955	return msort(str, len);
956}
957
958
959STATIC struct strlist *
960msort(list, len)
961	struct strlist *list;
962	{
963	struct strlist *p, *q;
964	struct strlist **lpp;
965	int half;
966	int n;
967
968	if (len <= 1)
969		return list;
970	half = len >> 1;
971	p = list;
972	for (n = half ; --n >= 0 ; ) {
973		q = p;
974		p = p->next;
975	}
976	q->next = NULL;			/* terminate first half of list */
977	q = msort(list, half);		/* sort first half of list */
978	p = msort(p, len - half);		/* sort second half */
979	lpp = &list;
980	for (;;) {
981		if (strcmp(p->text, q->text) < 0) {
982			*lpp = p;
983			lpp = &p->next;
984			if ((p = *lpp) == NULL) {
985				*lpp = q;
986				break;
987			}
988		} else {
989			*lpp = q;
990			lpp = &q->next;
991			if ((q = *lpp) == NULL) {
992				*lpp = p;
993				break;
994			}
995		}
996	}
997	return list;
998}
999
1000
1001
1002/*
1003 * Returns true if the pattern matches the string.
1004 */
1005
1006int
1007patmatch(pattern, string)
1008	char *pattern;
1009	char *string;
1010	{
1011#ifdef notdef
1012	if (pattern[0] == '!' && pattern[1] == '!')
1013		return 1 - pmatch(pattern + 2, string);
1014	else
1015#endif
1016		return pmatch(pattern, string);
1017}
1018
1019
1020STATIC int
1021pmatch(pattern, string)
1022	char *pattern;
1023	char *string;
1024	{
1025	register char *p, *q;
1026	register char c;
1027
1028	p = pattern;
1029	q = string;
1030	for (;;) {
1031		switch (c = *p++) {
1032		case '\0':
1033			goto breakloop;
1034		case CTLESC:
1035			if (*q++ != *p++)
1036				return 0;
1037			break;
1038		case '?':
1039			if (*q++ == '\0')
1040				return 0;
1041			break;
1042		case '*':
1043			c = *p;
1044			if (c != CTLESC && c != '?' && c != '*' && c != '[') {
1045				while (*q != c) {
1046					if (*q == '\0')
1047						return 0;
1048					q++;
1049				}
1050			}
1051			do {
1052				if (pmatch(p, q))
1053					return 1;
1054			} while (*q++ != '\0');
1055			return 0;
1056		case '[': {
1057			char *endp;
1058			int invert, found;
1059			char chr;
1060
1061			endp = p;
1062			if (*endp == '!')
1063				endp++;
1064			for (;;) {
1065				if (*endp == '\0')
1066					goto dft;		/* no matching ] */
1067				if (*endp == CTLESC)
1068					endp++;
1069				if (*++endp == ']')
1070					break;
1071			}
1072			invert = 0;
1073			if (*p == '!') {
1074				invert++;
1075				p++;
1076			}
1077			found = 0;
1078			chr = *q++;
1079			c = *p++;
1080			do {
1081				if (c == CTLESC)
1082					c = *p++;
1083				if (*p == '-' && p[1] != ']') {
1084					p++;
1085					if (*p == CTLESC)
1086						p++;
1087					if (chr >= c && chr <= *p)
1088						found = 1;
1089					p++;
1090				} else {
1091					if (chr == c)
1092						found = 1;
1093				}
1094			} while ((c = *p++) != ']');
1095			if (found == invert)
1096				return 0;
1097			break;
1098		}
1099dft:	        default:
1100			if (*q++ != c)
1101				return 0;
1102			break;
1103		}
1104	}
1105breakloop:
1106	if (*q != '\0')
1107		return 0;
1108	return 1;
1109}
1110
1111
1112
1113/*
1114 * Remove any CTLESC characters from a string.
1115 */
1116
1117void
1118rmescapes(str)
1119	char *str;
1120	{
1121	register char *p, *q;
1122
1123	p = str;
1124	while (*p != CTLESC) {
1125		if (*p++ == '\0')
1126			return;
1127	}
1128	q = p;
1129	while (*p) {
1130		if (*p == CTLESC)
1131			p++;
1132		*q++ = *p++;
1133	}
1134	*q = '\0';
1135}
1136
1137
1138
1139/*
1140 * See if a pattern matches in a case statement.
1141 */
1142
1143int
1144casematch(pattern, val)
1145	union node *pattern;
1146	char *val;
1147	{
1148	struct stackmark smark;
1149	int result;
1150	char *p;
1151
1152	setstackmark(&smark);
1153	argbackq = pattern->narg.backquote;
1154	STARTSTACKSTR(expdest);
1155	ifslastp = NULL;
1156	argstr(pattern->narg.text, EXP_TILDE | EXP_CASE);
1157	STPUTC('\0', expdest);
1158	p = grabstackstr(expdest);
1159	result = patmatch(p, val);
1160	popstackmark(&smark);
1161	return result;
1162}
1163