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