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