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