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